1 /*
2 * Copyright (C) 2008,2009 Dan Carpenter.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 */
17
18 #include <stdlib.h>
19 #include <stdio.h>
20 #include "smatch.h"
21 #include "smatch_slist.h"
22
23 #undef CHECKORDER
24
25 ALLOCATOR(smatch_state, "smatch state");
26 ALLOCATOR(sm_state, "sm state");
27 ALLOCATOR(named_stree, "named slist");
28 __DO_ALLOCATOR(char, 1, 4, "state names", sname);
29
30 int sm_state_counter;
31
32 static struct stree_stack *all_pools;
33
34 const char *show_sm(struct sm_state *sm)
35 {
36 static char buf[256];
37 struct sm_state *tmp;
38 int pos;
39 int i;
40
41 if (!sm)
42 return "<none>";
43
44 pos = snprintf(buf, sizeof(buf), "[%s] '%s' = '%s'",
45 check_name(sm->owner), sm->name, show_state(sm->state));
46 if (pos > sizeof(buf))
47 goto truncate;
48
49 if (ptr_list_size((struct ptr_list *)sm->possible) == 1)
50 return buf;
51
52 pos += snprintf(buf + pos, sizeof(buf) - pos, " (");
53 if (pos > sizeof(buf))
54 goto truncate;
55 i = 0;
56 FOR_EACH_PTR(sm->possible, tmp) {
57 if (i++)
58 pos += snprintf(buf + pos, sizeof(buf) - pos, ", ");
59 if (pos > sizeof(buf))
60 goto truncate;
61 pos += snprintf(buf + pos, sizeof(buf) - pos, "%s",
62 show_state(tmp->state));
63 if (pos > sizeof(buf))
64 goto truncate;
65 } END_FOR_EACH_PTR(tmp);
66 snprintf(buf + pos, sizeof(buf) - pos, ")");
67
68 return buf;
69
70 truncate:
71 for (i = 0; i < 3; i++)
72 buf[sizeof(buf) - 2 - i] = '.';
73 return buf;
74 }
75
76 void __print_stree(struct stree *stree)
77 {
78 struct sm_state *sm;
79
80 printf("dumping stree at %d [%ld states]\n", get_lineno(), stree_count(stree));
81 FOR_EACH_SM(stree, sm) {
82 printf("%s\n", show_sm(sm));
83 } END_FOR_EACH_SM(sm);
84 printf("---\n");
85 }
86
87 /* NULL states go at the end to simplify merge_slist */
88 int cmp_tracker(const struct sm_state *a, const struct sm_state *b)
89 {
90 int ret;
91
92 if (a == b)
93 return 0;
94 if (!b)
95 return -1;
96 if (!a)
97 return 1;
98
99 if (a->owner < b->owner)
100 return -1;
101 if (a->owner > b->owner)
102 return 1;
103
104 ret = strcmp(a->name, b->name);
105 if (ret < 0)
106 return -1;
107 if (ret > 0)
108 return 1;
109
110 if (!b->sym && a->sym)
111 return -1;
112 if (!a->sym && b->sym)
113 return 1;
114 if (a->sym < b->sym)
115 return -1;
116 if (a->sym > b->sym)
117 return 1;
118
119 return 0;
120 }
121
122 int *dynamic_states;
123 void allocate_dynamic_states_array(int num_checks)
124 {
125 dynamic_states = calloc(num_checks + 1, sizeof(int));
126 }
127
128 void set_dynamic_states(unsigned short owner)
129 {
130 dynamic_states[owner] = true;
131 }
132
133 bool has_dynamic_states(unsigned short owner)
134 {
135 if (owner >= num_checks)
136 return false;
137 return dynamic_states[owner];
138 }
139
140 static int cmp_possible_sm(const struct sm_state *a, const struct sm_state *b, int preserve)
141 {
142 int ret;
143
144 if (a == b)
145 return 0;
146
147 if (!has_dynamic_states(a->owner)) {
148 if (a->state > b->state)
149 return -1;
150 if (a->state < b->state)
151 return 1;
152 return 0;
153 }
154
155 if (a->owner == SMATCH_EXTRA) {
156 /*
157 * In Smatch extra you can have borrowed implications.
158 *
159 * FIXME: review how borrowed implications work and if they
160 * are the best way. See also smatch_implied.c.
161 *
162 */
163 ret = cmp_tracker(a, b);
164 if (ret)
165 return ret;
166
167 /*
168 * We want to preserve leaf states. They're use to split
169 * returns in smatch_db.c.
170 *
171 */
172 if (preserve) {
173 if (a->merged && !b->merged)
174 return -1;
175 if (!a->merged)
176 return 1;
177 }
178 }
179 if (!a->state->name || !b->state->name)
180 return 0;
181
182 return strcmp(a->state->name, b->state->name);
183 }
184
185 struct sm_state *alloc_sm_state(int owner, const char *name,
186 struct symbol *sym, struct smatch_state *state)
187 {
188 struct sm_state *sm_state = __alloc_sm_state(0);
189
190 sm_state_counter++;
191
192 sm_state->name = alloc_sname(name);
193 sm_state->owner = owner;
194 sm_state->sym = sym;
195 sm_state->state = state;
196 sm_state->line = get_lineno();
197 sm_state->merged = 0;
198 sm_state->pool = NULL;
199 sm_state->left = NULL;
200 sm_state->right = NULL;
201 sm_state->possible = NULL;
202 add_ptr_list(&sm_state->possible, sm_state);
203 return sm_state;
204 }
205
206 static struct sm_state *alloc_state_no_name(int owner, const char *name,
207 struct symbol *sym,
208 struct smatch_state *state)
209 {
210 struct sm_state *tmp;
211
212 tmp = alloc_sm_state(owner, NULL, sym, state);
213 tmp->name = name;
214 return tmp;
215 }
216
217 int too_many_possible(struct sm_state *sm)
218 {
219 if (ptr_list_size((struct ptr_list *)sm->possible) >= 100)
220 return 1;
221 return 0;
222 }
223
224 void add_possible_sm(struct sm_state *to, struct sm_state *new)
225 {
226 struct sm_state *tmp;
227 int preserve = 1;
228 int cmp;
229
230 if (too_many_possible(to))
231 preserve = 0;
232
233 FOR_EACH_PTR(to->possible, tmp) {
234 cmp = cmp_possible_sm(tmp, new, preserve);
235 if (cmp < 0)
236 continue;
237 else if (cmp == 0) {
238 return;
239 } else {
240 INSERT_CURRENT(new, tmp);
241 return;
242 }
243 } END_FOR_EACH_PTR(tmp);
244 add_ptr_list(&to->possible, new);
245 }
246
247 static void copy_possibles(struct sm_state *to, struct sm_state *one, struct sm_state *two)
248 {
249 struct sm_state *large = one;
250 struct sm_state *small = two;
251 struct sm_state *tmp;
252
253 /*
254 * We spend a lot of time copying the possible lists. I've tried to
255 * optimize the process a bit.
256 *
257 */
258
259 if (ptr_list_size((struct ptr_list *)two->possible) >
260 ptr_list_size((struct ptr_list *)one->possible)) {
261 large = two;
262 small = one;
263 }
264
265 to->possible = clone_slist(large->possible);
266 add_possible_sm(to, to);
267 FOR_EACH_PTR(small->possible, tmp) {
268 add_possible_sm(to, tmp);
269 } END_FOR_EACH_PTR(tmp);
270 }
271
272 char *alloc_sname(const char *str)
273 {
274 char *tmp;
275
276 if (!str)
277 return NULL;
278 tmp = __alloc_sname(strlen(str) + 1);
279 strcpy(tmp, str);
280 return tmp;
281 }
282
283 static struct symbol *oom_func;
284 static int oom_limit = 3000000; /* Start with a 3GB limit */
285 int out_of_memory(void)
286 {
287 if (oom_func)
288 return 1;
289
290 /*
291 * I decided to use 50M here based on trial and error.
292 * It works out OK for the kernel and so it should work
293 * for most other projects as well.
294 */
295 if (sm_state_counter * sizeof(struct sm_state) >= 100000000)
296 return 1;
297
298 /*
299 * We're reading from statm to figure out how much memory we
300 * are using. The problem is that at the end of the function
301 * we release the memory, so that it can be re-used but it
302 * stays in cache, it's not released to the OS. So then if
303 * we allocate memory for different purposes we can easily
304 * hit the 3GB limit on the next function, so that's why I give
305 * the next function an extra 100MB to work with.
306 *
307 */
308 if (get_mem_kb() > oom_limit) {
309 oom_func = cur_func_sym;
310 final_pass++;
311 sm_perror("OOM: %luKb sm_state_count = %d", get_mem_kb(), sm_state_counter);
312 final_pass--;
313 return 1;
314 }
315
316 return 0;
317 }
318
319 int low_on_memory(void)
320 {
321 if (sm_state_counter * sizeof(struct sm_state) >= 25000000)
322 return 1;
323 return 0;
324 }
325
326 static void free_sm_state(struct sm_state *sm)
327 {
328 free_slist(&sm->possible);
329 /*
330 * fixme. Free the actual state.
331 * Right now we leave it until the end of the function
332 * because we don't want to double free it.
333 * Use the freelist to not double free things
334 */
335 }
336
337 static void free_all_sm_states(struct allocation_blob *blob)
338 {
339 unsigned int size = sizeof(struct sm_state);
340 unsigned int offset = 0;
341
342 while (offset < blob->offset) {
343 free_sm_state((struct sm_state *)(blob->data + offset));
344 offset += size;
345 }
346 }
347
348 /* At the end of every function we free all the sm_states */
349 void free_every_single_sm_state(void)
350 {
351 struct allocator_struct *desc = &sm_state_allocator;
352 struct allocation_blob *blob = desc->blobs;
353
354 desc->blobs = NULL;
355 desc->allocations = 0;
356 desc->total_bytes = 0;
357 desc->useful_bytes = 0;
358 desc->freelist = NULL;
359 while (blob) {
360 struct allocation_blob *next = blob->next;
361 free_all_sm_states(blob);
362 blob_free(blob, desc->chunking);
363 blob = next;
364 }
365 clear_sname_alloc();
366 clear_smatch_state_alloc();
367
368 free_stack_and_strees(&all_pools);
369 sm_state_counter = 0;
370 if (oom_func) {
371 oom_limit += 100000;
372 oom_func = NULL;
373 }
374 }
375
376 unsigned long get_pool_count(void)
377 {
378 return ptr_list_size((struct ptr_list *)all_pools);
379 }
380
381 struct sm_state *clone_sm(struct sm_state *s)
382 {
383 struct sm_state *ret;
384
385 ret = alloc_state_no_name(s->owner, s->name, s->sym, s->state);
386 ret->merged = s->merged;
387 ret->line = s->line;
388 /* clone_sm() doesn't copy the pools. Each state needs to have
389 only one pool. */
390 ret->possible = clone_slist(s->possible);
391 ret->left = s->left;
392 ret->right = s->right;
393 return ret;
394 }
395
396 int is_merged(struct sm_state *sm)
397 {
398 return sm->merged;
399 }
400
401 int is_leaf(struct sm_state *sm)
402 {
403 return !sm->merged;
404 }
405
406 int slist_has_state(struct state_list *slist, struct smatch_state *state)
407 {
408 struct sm_state *tmp;
409
410 FOR_EACH_PTR(slist, tmp) {
411 if (tmp->state == state)
412 return 1;
413 } END_FOR_EACH_PTR(tmp);
414 return 0;
415 }
416
417 struct state_list *clone_slist(struct state_list *from_slist)
418 {
419 struct sm_state *sm;
420 struct state_list *to_slist = NULL;
421
422 FOR_EACH_PTR(from_slist, sm) {
423 add_ptr_list(&to_slist, sm);
424 } END_FOR_EACH_PTR(sm);
425 return to_slist;
426 }
427
428 static struct smatch_state *merge_states(int owner, const char *name,
429 struct symbol *sym,
430 struct smatch_state *state1,
431 struct smatch_state *state2)
432 {
433 struct smatch_state *ret;
434
435 if (state1 == state2)
436 ret = state1;
437 else if (__has_merge_function(owner))
438 ret = __client_merge_function(owner, state1, state2);
439 else if (state1 == &ghost)
440 ret = state2;
441 else if (state2 == &ghost)
442 ret = state1;
443 else if (!state1 || !state2)
444 ret = &undefined;
445 else
446 ret = &merged;
447 return ret;
448 }
449
450 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
451 {
452 struct smatch_state *s;
453 struct sm_state *result;
454 static int warned;
455
456 if (one == two)
457 return one;
458 if (out_of_memory()) {
459 if (!warned)
460 sm_warning("Function too hairy. No more merges.");
461 warned = 1;
462 return one;
463 }
464 warned = 0;
465 s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
466 result = alloc_state_no_name(one->owner, one->name, one->sym, s);
467 result->merged = 1;
468 result->left = one;
469 result->right = two;
470
471 copy_possibles(result, one, two);
472
473 /*
474 * The ->line information is used by deref_check where we complain about
475 * checking pointers that have already been dereferenced. Let's say we
476 * dereference a pointer on both the true and false paths and then merge
477 * the states here. The result state is &derefed, but the ->line number
478 * is on the line where the pointer is merged not where it was
479 * dereferenced..
480 *
481 * So in that case, let's just pick one dereference and set the ->line
482 * to point at it.
483 *
484 */
485
486 if (result->state == one->state)
487 result->line = one->line;
488 if (result->state == two->state)
489 result->line = two->line;
490
491 if (option_debug ||
492 strcmp(check_name(one->owner), option_debug_check) == 0) {
493 struct sm_state *tmp;
494 int i = 0;
495
496 printf("%s:%d %s() merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
497 get_filename(), get_lineno(), get_function(),
498 check_name(one->owner), one->name,
499 show_state(one->state), one->line,
500 show_state(two->state), two->line,
501 show_state(s));
502
503 FOR_EACH_PTR(result->possible, tmp) {
504 if (i++)
505 printf(", ");
506 printf("%s", show_state(tmp->state));
507 } END_FOR_EACH_PTR(tmp);
508 printf(")\n");
509 }
510
511 return result;
512 }
513
514 struct sm_state *get_sm_state_stree(struct stree *stree, int owner, const char *name,
515 struct symbol *sym)
516 {
517 struct tracker tracker = {
518 .owner = owner,
519 .name = (char *)name,
520 .sym = sym,
521 };
522
523 if (!name)
524 return NULL;
525
526
527 return avl_lookup(stree, (struct sm_state *)&tracker);
528 }
529
530 struct smatch_state *get_state_stree(struct stree *stree,
531 int owner, const char *name,
532 struct symbol *sym)
533 {
534 struct sm_state *sm;
535
536 sm = get_sm_state_stree(stree, owner, name, sym);
537 if (sm)
538 return sm->state;
539 return NULL;
540 }
541
542 /* FIXME: this is almost exactly the same as set_sm_state_slist() */
543 void overwrite_sm_state_stree(struct stree **stree, struct sm_state *new)
544 {
545 avl_insert(stree, new);
546 }
547
548 void overwrite_sm_state_stree_stack(struct stree_stack **stack,
549 struct sm_state *sm)
550 {
551 struct stree *stree;
552
553 stree = pop_stree(stack);
554 overwrite_sm_state_stree(&stree, sm);
555 push_stree(stack, stree);
556 }
557
558 struct sm_state *set_state_stree(struct stree **stree, int owner, const char *name,
559 struct symbol *sym, struct smatch_state *state)
560 {
561 struct sm_state *new = alloc_sm_state(owner, name, sym, state);
562
563 avl_insert(stree, new);
564 return new;
565 }
566
567 void set_state_stree_perm(struct stree **stree, int owner, const char *name,
568 struct symbol *sym, struct smatch_state *state)
569 {
570 struct sm_state *sm;
571
572 sm = malloc(sizeof(*sm) + strlen(name) + 1);
573 memset(sm, 0, sizeof(*sm));
574 sm->owner = owner;
575 sm->name = (char *)(sm + 1);
576 strcpy((char *)sm->name, name);
577 sm->sym = sym;
578 sm->state = state;
579
580 overwrite_sm_state_stree(stree, sm);
581 }
582
583 void delete_state_stree(struct stree **stree, int owner, const char *name,
584 struct symbol *sym)
585 {
586 struct tracker tracker = {
587 .owner = owner,
588 .name = (char *)name,
589 .sym = sym,
590 };
591
592 avl_remove(stree, (struct sm_state *)&tracker);
593 }
594
595 void delete_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
596 struct symbol *sym)
597 {
598 struct stree *stree;
599
600 stree = pop_stree(stack);
601 delete_state_stree(&stree, owner, name, sym);
602 push_stree(stack, stree);
603 }
604
605 void push_stree(struct stree_stack **stack, struct stree *stree)
606 {
607 add_ptr_list(stack, stree);
608 }
609
610 struct stree *pop_stree(struct stree_stack **stack)
611 {
612 struct stree *stree;
613
614 stree = last_ptr_list((struct ptr_list *)*stack);
615 delete_ptr_list_last((struct ptr_list **)stack);
616 return stree;
617 }
618
619 struct stree *top_stree(struct stree_stack *stack)
620 {
621 return last_ptr_list((struct ptr_list *)stack);
622 }
623
624 void free_slist(struct state_list **slist)
625 {
626 __free_ptr_list((struct ptr_list **)slist);
627 }
628
629 void free_stree_stack(struct stree_stack **stack)
630 {
631 __free_ptr_list((struct ptr_list **)stack);
632 }
633
634 void free_stack_and_strees(struct stree_stack **stree_stack)
635 {
636 struct stree *stree;
637
638 FOR_EACH_PTR(*stree_stack, stree) {
639 free_stree(&stree);
640 } END_FOR_EACH_PTR(stree);
641 free_stree_stack(stree_stack);
642 }
643
644 struct sm_state *set_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
645 struct symbol *sym, struct smatch_state *state)
646 {
647 struct stree *stree;
648 struct sm_state *sm;
649
650 stree = pop_stree(stack);
651 sm = set_state_stree(&stree, owner, name, sym, state);
652 push_stree(stack, stree);
653
654 return sm;
655 }
656
657 /*
658 * get_sm_state_stack() gets the state for the top slist on the stack.
659 */
660 struct sm_state *get_sm_state_stree_stack(struct stree_stack *stack,
661 int owner, const char *name,
662 struct symbol *sym)
663 {
664 struct stree *stree;
665 struct sm_state *ret;
666
667 stree = pop_stree(&stack);
668 ret = get_sm_state_stree(stree, owner, name, sym);
669 push_stree(&stack, stree);
670 return ret;
671 }
672
673 struct smatch_state *get_state_stree_stack(struct stree_stack *stack,
674 int owner, const char *name,
675 struct symbol *sym)
676 {
677 struct sm_state *sm;
678
679 sm = get_sm_state_stree_stack(stack, owner, name, sym);
680 if (sm)
681 return sm->state;
682 return NULL;
683 }
684
685 static void match_states_stree(struct stree **one, struct stree **two)
686 {
687 struct smatch_state *tmp_state;
688 struct sm_state *sm;
689 struct state_list *add_to_one = NULL;
690 struct state_list *add_to_two = NULL;
691 AvlIter one_iter;
692 AvlIter two_iter;
693
694 avl_iter_begin(&one_iter, *one, FORWARD);
695 avl_iter_begin(&two_iter, *two, FORWARD);
696
697 for (;;) {
698 if (!one_iter.sm && !two_iter.sm)
699 break;
700 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
701 __set_fake_cur_stree_fast(*two);
702 tmp_state = __client_unmatched_state_function(one_iter.sm);
703 __pop_fake_cur_stree_fast();
704 sm = alloc_state_no_name(one_iter.sm->owner, one_iter.sm->name,
705 one_iter.sm->sym, tmp_state);
706 add_ptr_list(&add_to_two, sm);
707 avl_iter_next(&one_iter);
708 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
709 avl_iter_next(&one_iter);
710 avl_iter_next(&two_iter);
711 } else {
712 __set_fake_cur_stree_fast(*one);
713 tmp_state = __client_unmatched_state_function(two_iter.sm);
714 __pop_fake_cur_stree_fast();
715 sm = alloc_state_no_name(two_iter.sm->owner, two_iter.sm->name,
716 two_iter.sm->sym, tmp_state);
717 add_ptr_list(&add_to_one, sm);
718 avl_iter_next(&two_iter);
719 }
720 }
721
722 FOR_EACH_PTR(add_to_one, sm) {
723 avl_insert(one, sm);
724 } END_FOR_EACH_PTR(sm);
725
726 FOR_EACH_PTR(add_to_two, sm) {
727 avl_insert(two, sm);
728 } END_FOR_EACH_PTR(sm);
729
730 free_slist(&add_to_one);
731 free_slist(&add_to_two);
732 }
733
734 static void call_pre_merge_hooks(struct stree **one, struct stree **two)
735 {
736 struct sm_state *sm, *other;
737
738 save_all_states();
739
740 __swap_cur_stree(*one);
741 FOR_EACH_SM(*two, sm) {
742 other = get_sm_state(sm->owner, sm->name, sm->sym);
743 if (other == sm)
744 continue;
745 call_pre_merge_hook(sm);
746 } END_FOR_EACH_SM(sm);
747 *one = clone_stree(__get_cur_stree());
748
749 __swap_cur_stree(*two);
750 FOR_EACH_SM(*one, sm) {
751 other = get_sm_state(sm->owner, sm->name, sm->sym);
752 if (other == sm)
753 continue;
754 call_pre_merge_hook(sm);
755 } END_FOR_EACH_SM(sm);
756 *two = clone_stree(__get_cur_stree());
757
758 restore_all_states();
759 }
760
761 static void clone_pool_havers_stree(struct stree **stree)
762 {
763 struct sm_state *sm, *tmp;
764 struct state_list *slist = NULL;
765
766 FOR_EACH_SM(*stree, sm) {
767 if (sm->pool) {
768 tmp = clone_sm(sm);
769 add_ptr_list(&slist, tmp);
770 }
771 } END_FOR_EACH_SM(sm);
772
773 FOR_EACH_PTR(slist, sm) {
774 avl_insert(stree, sm);
775 } END_FOR_EACH_PTR(sm);
776
777 free_slist(&slist);
778 }
779
780 int __stree_id;
781
782 /*
783 * merge_slist() is called whenever paths merge, such as after
784 * an if statement. It takes the two slists and creates one.
785 */
786 static void __merge_stree(struct stree **to, struct stree *stree, int add_pool)
787 {
788 struct stree *results = NULL;
789 struct stree *implied_one = NULL;
790 struct stree *implied_two = NULL;
791 AvlIter one_iter;
792 AvlIter two_iter;
793 struct sm_state *one, *two, *res;
794
795 if (out_of_memory())
796 return;
797
798 /* merging a null and nonnull path gives you only the nonnull path */
799 if (!stree)
800 return;
801 if (*to == stree)
802 return;
803
804 if (!*to) {
805 *to = clone_stree(stree);
806 return;
807 }
808
809 implied_one = clone_stree(*to);
810 implied_two = clone_stree(stree);
811
812 match_states_stree(&implied_one, &implied_two);
813 call_pre_merge_hooks(&implied_one, &implied_two);
814
815 if (add_pool) {
816 clone_pool_havers_stree(&implied_one);
817 clone_pool_havers_stree(&implied_two);
818
819 set_stree_id(&implied_one, ++__stree_id);
820 set_stree_id(&implied_two, ++__stree_id);
821 if (implied_one->base_stree)
822 set_stree_id(&implied_one->base_stree, ++__stree_id);
823 if (implied_two->base_stree)
824 set_stree_id(&implied_two->base_stree, ++__stree_id);
825 }
826
827 push_stree(&all_pools, implied_one);
828 push_stree(&all_pools, implied_two);
829
830 avl_iter_begin(&one_iter, implied_one, FORWARD);
831 avl_iter_begin(&two_iter, implied_two, FORWARD);
832
833 for (;;) {
834 if (!one_iter.sm || !two_iter.sm)
835 break;
836
837 one = one_iter.sm;
838 two = two_iter.sm;
839
840 if (one == two) {
841 avl_insert(&results, one);
842 goto next;
843 }
844
845 if (add_pool) {
846 one->pool = implied_one;
847 if (implied_one->base_stree)
848 one->pool = implied_one->base_stree;
849 two->pool = implied_two;
850 if (implied_two->base_stree)
851 two->pool = implied_two->base_stree;
852 }
853 res = merge_sm_states(one, two);
854 add_possible_sm(res, one);
855 add_possible_sm(res, two);
856 avl_insert(&results, res);
857 next:
858 avl_iter_next(&one_iter);
859 avl_iter_next(&two_iter);
860 }
861
862 free_stree(to);
863 *to = results;
864 }
865
866 void merge_stree(struct stree **to, struct stree *stree)
867 {
868 __merge_stree(to, stree, 1);
869 }
870
871 void merge_stree_no_pools(struct stree **to, struct stree *stree)
872 {
873 __merge_stree(to, stree, 0);
874 }
875
876 /*
877 * This is unfortunately a bit subtle... The problem is that if a
878 * state is set on one fake stree but not the other then we should
879 * look up the the original state and use that as the unset state.
880 * Fortunately, after you pop your fake stree then the cur_slist should
881 * reflect the original state.
882 */
883 void merge_fake_stree(struct stree **to, struct stree *stree)
884 {
885 struct stree *one = *to;
886 struct stree *two = stree;
887 struct sm_state *sm;
888 struct state_list *add_to_one = NULL;
889 struct state_list *add_to_two = NULL;
890 AvlIter one_iter;
891 AvlIter two_iter;
892
893 if (!stree)
894 return;
895 if (*to == stree)
896 return;
897 if (!*to) {
898 *to = clone_stree(stree);
899 return;
900 }
901
902 avl_iter_begin(&one_iter, one, FORWARD);
903 avl_iter_begin(&two_iter, two, FORWARD);
904
905 for (;;) {
906 if (!one_iter.sm && !two_iter.sm)
907 break;
908 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
909 sm = get_sm_state(one_iter.sm->owner, one_iter.sm->name,
910 one_iter.sm->sym);
911 if (sm)
912 add_ptr_list(&add_to_two, sm);
913 avl_iter_next(&one_iter);
914 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
915 avl_iter_next(&one_iter);
916 avl_iter_next(&two_iter);
917 } else {
918 sm = get_sm_state(two_iter.sm->owner, two_iter.sm->name,
919 two_iter.sm->sym);
920 if (sm)
921 add_ptr_list(&add_to_one, sm);
922 avl_iter_next(&two_iter);
923 }
924 }
925
926 FOR_EACH_PTR(add_to_one, sm) {
927 avl_insert(&one, sm);
928 } END_FOR_EACH_PTR(sm);
929
930 FOR_EACH_PTR(add_to_two, sm) {
931 avl_insert(&two, sm);
932 } END_FOR_EACH_PTR(sm);
933
934 one->base_stree = clone_stree(__get_cur_stree());
935 FOR_EACH_SM(one, sm) {
936 avl_insert(&one->base_stree, sm);
937 } END_FOR_EACH_SM(sm);
938
939 two->base_stree = clone_stree(__get_cur_stree());
940 FOR_EACH_SM(two, sm) {
941 avl_insert(&two->base_stree, sm);
942 } END_FOR_EACH_SM(sm);
943
944 free_slist(&add_to_one);
945 free_slist(&add_to_two);
946
947 __merge_stree(&one, two, 1);
948
949 *to = one;
950 }
951
952 /*
953 * filter_slist() removes any sm states "slist" holds in common with "filter"
954 */
955 void filter_stree(struct stree **stree, struct stree *filter)
956 {
957 struct stree *results = NULL;
958 AvlIter one_iter;
959 AvlIter two_iter;
960
961 avl_iter_begin(&one_iter, *stree, FORWARD);
962 avl_iter_begin(&two_iter, filter, FORWARD);
963
964 /* FIXME: This should probably be re-written with trees in mind */
965
966 for (;;) {
967 if (!one_iter.sm && !two_iter.sm)
968 break;
969 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
970 avl_insert(&results, one_iter.sm);
971 avl_iter_next(&one_iter);
972 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
973 if (one_iter.sm != two_iter.sm)
974 avl_insert(&results, one_iter.sm);
975 avl_iter_next(&one_iter);
976 avl_iter_next(&two_iter);
977 } else {
978 avl_iter_next(&two_iter);
979 }
980 }
981
982 free_stree(stree);
983 *stree = results;
984 }
985
986
987 /*
988 * and_slist_stack() pops the top two slists, overwriting the one with
989 * the other and pushing it back on the stack.
990 */
991 void and_stree_stack(struct stree_stack **stack)
992 {
993 struct sm_state *tmp;
994 struct stree *right_stree = pop_stree(stack);
995
996 FOR_EACH_SM(right_stree, tmp) {
997 overwrite_sm_state_stree_stack(stack, tmp);
998 } END_FOR_EACH_SM(tmp);
999 free_stree(&right_stree);
1000 }
1001
1002 /*
1003 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
1004 * It pops the two slists from the top of the stack and merges them
1005 * together in a way that preserves the things they have in common
1006 * but creates a merged state for most of the rest.
1007 * You could have code that had: if (foo || foo) { foo->baz;
1008 * It's this function which ensures smatch does the right thing.
1009 */
1010 void or_stree_stack(struct stree_stack **pre_conds,
1011 struct stree *cur_stree,
1012 struct stree_stack **stack)
1013 {
1014 struct stree *new;
1015 struct stree *old;
1016 struct stree *pre_stree;
1017 struct stree *res;
1018 struct stree *tmp_stree;
1019
1020 new = pop_stree(stack);
1021 old = pop_stree(stack);
1022
1023 pre_stree = pop_stree(pre_conds);
1024 push_stree(pre_conds, clone_stree(pre_stree));
1025
1026 res = clone_stree(pre_stree);
1027 overwrite_stree(old, &res);
1028
1029 tmp_stree = clone_stree(cur_stree);
1030 overwrite_stree(new, &tmp_stree);
1031
1032 merge_stree(&res, tmp_stree);
1033 filter_stree(&res, pre_stree);
1034
1035 push_stree(stack, res);
1036 free_stree(&tmp_stree);
1037 free_stree(&pre_stree);
1038 free_stree(&new);
1039 free_stree(&old);
1040 }
1041
1042 /*
1043 * get_named_stree() is only used for gotos.
1044 */
1045 struct stree **get_named_stree(struct named_stree_stack *stack,
1046 const char *name,
1047 struct symbol *sym)
1048 {
1049 struct named_stree *tmp;
1050
1051 FOR_EACH_PTR(stack, tmp) {
1052 if (tmp->sym == sym &&
1053 strcmp(tmp->name, name) == 0)
1054 return &tmp->stree;
1055 } END_FOR_EACH_PTR(tmp);
1056 return NULL;
1057 }
1058
1059 /* FIXME: These parameters are in a different order from expected */
1060 void overwrite_stree(struct stree *from, struct stree **to)
1061 {
1062 struct sm_state *tmp;
1063
1064 FOR_EACH_SM(from, tmp) {
1065 overwrite_sm_state_stree(to, tmp);
1066 } END_FOR_EACH_SM(tmp);
1067 }
1068