expressions: introduce compare_expression()
[smatch.git] / smatch_slist.c
blob947c35c7f9e0cd63ebb330726a0c105a808a879e
1 /*
2 * Copyright (C) 2008,2009 Dan Carpenter.
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.
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.
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
18 #include <stdlib.h>
19 #include <stdio.h>
20 #include "smatch.h"
21 #include "smatch_slist.h"
23 #undef CHECKORDER
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);
30 static int sm_state_counter;
32 static struct stree_stack *all_pools;
34 char *show_sm(struct sm_state *sm)
36 static char buf[256];
37 struct sm_state *tmp;
38 int pos;
39 int i;
41 pos = snprintf(buf, sizeof(buf), "[%s] '%s' = '%s'",
42 check_name(sm->owner), sm->name, show_state(sm->state));
43 if (pos > sizeof(buf))
44 goto truncate;
46 if (ptr_list_size((struct ptr_list *)sm->possible) == 1)
47 return buf;
49 pos += snprintf(buf + pos, sizeof(buf) - pos, " (");
50 if (pos > sizeof(buf))
51 goto truncate;
52 i = 0;
53 FOR_EACH_PTR(sm->possible, tmp) {
54 if (i++)
55 pos += snprintf(buf + pos, sizeof(buf) - pos, ", ");
56 if (pos > sizeof(buf))
57 goto truncate;
58 pos += snprintf(buf + pos, sizeof(buf) - pos, "%s",
59 show_state(tmp->state));
60 if (pos > sizeof(buf))
61 goto truncate;
62 } END_FOR_EACH_PTR(tmp);
63 snprintf(buf + pos, sizeof(buf) - pos, ")");
65 return buf;
67 truncate:
68 for (i = 0; i < 3; i++)
69 buf[sizeof(buf) - 2 - i] = '.';
70 return buf;
73 void __print_stree(struct stree *stree)
75 struct sm_state *sm;
77 printf("dumping stree at %d\n", get_lineno());
78 FOR_EACH_SM(stree, sm) {
79 printf("%s\n", show_sm(sm));
80 } END_FOR_EACH_SM(sm);
81 printf("---\n");
84 /* NULL states go at the end to simplify merge_slist */
85 int cmp_tracker(const struct sm_state *a, const struct sm_state *b)
87 int ret;
89 if (a == b)
90 return 0;
91 if (!b)
92 return -1;
93 if (!a)
94 return 1;
96 if (a->owner > b->owner)
97 return -1;
98 if (a->owner < b->owner)
99 return 1;
101 ret = strcmp(a->name, b->name);
102 if (ret < 0)
103 return -1;
104 if (ret > 0)
105 return 1;
107 if (!b->sym && a->sym)
108 return -1;
109 if (!a->sym && b->sym)
110 return 1;
111 if (a->sym > b->sym)
112 return -1;
113 if (a->sym < b->sym)
114 return 1;
116 return 0;
119 static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b, int preserve)
121 int ret;
123 ret = cmp_tracker(a, b);
124 if (ret)
125 return ret;
127 /* todo: add hook for smatch_extra.c */
128 if (a->state > b->state)
129 return -1;
130 if (a->state < b->state)
131 return 1;
132 /* This is obviously a massive disgusting hack but we need to preserve
133 * the unmerged states for smatch extra because we use them in
134 * smatch_db.c. Meanwhile if we preserve all the other unmerged states
135 * then it uses a lot of memory and we don't use it. Hence this hack.
137 * Also sometimes even just preserving every possible SMATCH_EXTRA state
138 * takes too much resources so we have to cap that. Capping is probably
139 * not often a problem in real life.
141 if (a->owner == SMATCH_EXTRA && preserve) {
142 if (a == b)
143 return 0;
144 if (a->merged == 1 && b->merged == 0)
145 return -1;
146 if (a->merged == 0)
147 return 1;
150 return 0;
153 struct sm_state *alloc_sm_state(int owner, const char *name,
154 struct symbol *sym, struct smatch_state *state)
156 struct sm_state *sm_state = __alloc_sm_state(0);
158 sm_state_counter++;
160 sm_state->name = alloc_sname(name);
161 sm_state->owner = owner;
162 sm_state->sym = sym;
163 sm_state->state = state;
164 sm_state->line = get_lineno();
165 sm_state->merged = 0;
166 sm_state->implied = 0;
167 sm_state->pool = NULL;
168 sm_state->left = NULL;
169 sm_state->right = NULL;
170 sm_state->nr_children = 1;
171 sm_state->possible = NULL;
172 add_ptr_list(&sm_state->possible, sm_state);
173 return sm_state;
176 static struct sm_state *alloc_state_no_name(int owner, const char *name,
177 struct symbol *sym,
178 struct smatch_state *state)
180 struct sm_state *tmp;
182 tmp = alloc_sm_state(owner, NULL, sym, state);
183 tmp->name = name;
184 return tmp;
187 int too_many_possible(struct sm_state *sm)
189 if (ptr_list_size((struct ptr_list *)sm->possible) >= 100)
190 return 1;
191 return 0;
194 void add_possible_sm(struct sm_state *to, struct sm_state *new)
196 struct sm_state *tmp;
197 int preserve = 1;
199 if (too_many_possible(to))
200 preserve = 0;
202 FOR_EACH_PTR(to->possible, tmp) {
203 if (cmp_sm_states(tmp, new, preserve) < 0)
204 continue;
205 else if (cmp_sm_states(tmp, new, preserve) == 0) {
206 return;
207 } else {
208 INSERT_CURRENT(new, tmp);
209 return;
211 } END_FOR_EACH_PTR(tmp);
212 add_ptr_list(&to->possible, new);
215 static void copy_possibles(struct sm_state *to, struct sm_state *from)
217 struct sm_state *tmp;
219 FOR_EACH_PTR(from->possible, tmp) {
220 add_possible_sm(to, tmp);
221 } END_FOR_EACH_PTR(tmp);
224 char *alloc_sname(const char *str)
226 char *tmp;
228 if (!str)
229 return NULL;
230 tmp = __alloc_sname(strlen(str) + 1);
231 strcpy(tmp, str);
232 return tmp;
235 int out_of_memory(void)
238 * I decided to use 50M here based on trial and error.
239 * It works out OK for the kernel and so it should work
240 * for most other projects as well.
242 if (sm_state_counter * sizeof(struct sm_state) >= 50000000)
243 return 1;
244 return 0;
247 int low_on_memory(void)
249 if (sm_state_counter * sizeof(struct sm_state) >= 25000000)
250 return 1;
251 return 0;
254 static void free_sm_state(struct sm_state *sm)
256 free_slist(&sm->possible);
258 * fixme. Free the actual state.
259 * Right now we leave it until the end of the function
260 * because we don't want to double free it.
261 * Use the freelist to not double free things
265 static void free_all_sm_states(struct allocation_blob *blob)
267 unsigned int size = sizeof(struct sm_state);
268 unsigned int offset = 0;
270 while (offset < blob->offset) {
271 free_sm_state((struct sm_state *)(blob->data + offset));
272 offset += size;
276 /* At the end of every function we free all the sm_states */
277 void free_every_single_sm_state(void)
279 struct allocator_struct *desc = &sm_state_allocator;
280 struct allocation_blob *blob = desc->blobs;
282 desc->blobs = NULL;
283 desc->allocations = 0;
284 desc->total_bytes = 0;
285 desc->useful_bytes = 0;
286 desc->freelist = NULL;
287 while (blob) {
288 struct allocation_blob *next = blob->next;
289 free_all_sm_states(blob);
290 blob_free(blob, desc->chunking);
291 blob = next;
293 clear_sname_alloc();
294 clear_smatch_state_alloc();
296 free_stack_and_strees(&all_pools);
297 sm_state_counter = 0;
300 struct sm_state *clone_sm(struct sm_state *s)
302 struct sm_state *ret;
304 ret = alloc_state_no_name(s->owner, s->name, s->sym, s->state);
305 ret->merged = s->merged;
306 ret->implied = s->implied;
307 ret->line = s->line;
308 /* clone_sm() doesn't copy the pools. Each state needs to have
309 only one pool. */
310 ret->possible = clone_slist(s->possible);
311 ret->left = s->left;
312 ret->right = s->right;
313 ret->nr_children = s->nr_children;
314 return ret;
317 int is_merged(struct sm_state *sm)
319 return sm->merged;
322 int is_implied(struct sm_state *sm)
324 return sm->implied;
327 int slist_has_state(struct state_list *slist, struct smatch_state *state)
329 struct sm_state *tmp;
331 FOR_EACH_PTR(slist, tmp) {
332 if (tmp->state == state)
333 return 1;
334 } END_FOR_EACH_PTR(tmp);
335 return 0;
338 struct state_list *clone_slist(struct state_list *from_slist)
340 struct sm_state *sm;
341 struct state_list *to_slist = NULL;
343 FOR_EACH_PTR(from_slist, sm) {
344 add_ptr_list(&to_slist, sm);
345 } END_FOR_EACH_PTR(sm);
346 return to_slist;
349 struct smatch_state *merge_states(int owner, const char *name,
350 struct symbol *sym,
351 struct smatch_state *state1,
352 struct smatch_state *state2)
354 struct smatch_state *ret;
356 if (state1 == state2)
357 ret = state1;
358 else if (__has_merge_function(owner))
359 ret = __client_merge_function(owner, state1, state2);
360 else if (state1 == &ghost)
361 ret = state2;
362 else if (state2 == &ghost)
363 ret = state1;
364 else if (!state1 || !state2)
365 ret = &undefined;
366 else
367 ret = &merged;
368 return ret;
371 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
373 struct smatch_state *s;
374 struct sm_state *result;
376 if (one == two)
377 return one;
378 s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
379 result = alloc_state_no_name(one->owner, one->name, one->sym, s);
380 result->merged = 1;
381 result->left = one;
382 result->right = two;
383 result->nr_children = one->nr_children + two->nr_children;
384 copy_possibles(result, one);
385 copy_possibles(result, two);
387 if (option_debug ||
388 strcmp(check_name(one->owner), option_debug_check) == 0) {
389 struct sm_state *tmp;
390 int i = 0;
392 printf("%s:%d %s() merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
393 get_filename(), get_lineno(), get_function(),
394 check_name(one->owner), one->name,
395 show_state(one->state), one->line,
396 show_state(two->state), two->line,
397 show_state(s));
399 FOR_EACH_PTR(result->possible, tmp) {
400 if (i++)
401 printf(", ");
402 printf("%s", show_state(tmp->state));
403 } END_FOR_EACH_PTR(tmp);
404 printf(")\n");
407 return result;
410 struct sm_state *get_sm_state_stree(struct stree *stree, int owner, const char *name,
411 struct symbol *sym)
413 struct tracker tracker = {
414 .owner = owner,
415 .name = (char *)name,
416 .sym = sym,
419 if (!name)
420 return NULL;
423 return avl_lookup(stree, (struct sm_state *)&tracker);
426 struct smatch_state *get_state_stree(struct stree *stree,
427 int owner, const char *name,
428 struct symbol *sym)
430 struct sm_state *sm;
432 sm = get_sm_state_stree(stree, owner, name, sym);
433 if (sm)
434 return sm->state;
435 return NULL;
438 /* FIXME: this is almost exactly the same as set_sm_state_slist() */
439 void overwrite_sm_state_stree(struct stree **stree, struct sm_state *new)
441 avl_insert(stree, new);
444 void overwrite_sm_state_stree_stack(struct stree_stack **stack,
445 struct sm_state *sm)
447 struct stree *stree;
449 stree = pop_stree(stack);
450 overwrite_sm_state_stree(&stree, sm);
451 push_stree(stack, stree);
454 void set_sm_state_stree_stack_if_not_already_set(struct stree_stack **stack,
455 struct sm_state *sm)
457 struct stree *stree;
459 stree = pop_stree(stack);
460 if (get_state_stree(stree, sm->owner, sm->name, sm->sym))
461 goto push;
462 overwrite_sm_state_stree(&stree, sm);
463 push:
464 push_stree(stack, stree);
467 struct sm_state *set_state_stree(struct stree **stree, int owner, const char *name,
468 struct symbol *sym, struct smatch_state *state)
470 struct sm_state *new = alloc_sm_state(owner, name, sym, state);
472 avl_insert(stree, new);
473 return new;
476 void set_state_stree_perm(struct stree **stree, int owner, const char *name,
477 struct symbol *sym, struct smatch_state *state)
479 struct sm_state *sm;
481 sm = malloc(sizeof(*sm) + strlen(name) + 1);
482 memset(sm, 0, sizeof(*sm));
483 sm->owner = owner;
484 sm->name = (char *)(sm + 1);
485 strcpy((char *)sm->name, name);
486 sm->sym = sym;
487 sm->state = state;
489 overwrite_sm_state_stree(stree, sm);
492 void delete_state_stree(struct stree **stree, int owner, const char *name,
493 struct symbol *sym)
495 struct tracker tracker = {
496 .owner = owner,
497 .name = (char *)name,
498 .sym = sym,
501 avl_remove(stree, (struct sm_state *)&tracker);
504 void delete_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
505 struct symbol *sym)
507 struct stree *stree;
509 stree = pop_stree(stack);
510 delete_state_stree(&stree, owner, name, sym);
511 push_stree(stack, stree);
514 void push_stree(struct stree_stack **stack, struct stree *stree)
516 add_ptr_list(stack, stree);
519 struct stree *pop_stree(struct stree_stack **stack)
521 struct stree *stree;
523 stree = last_ptr_list((struct ptr_list *)*stack);
524 delete_ptr_list_last((struct ptr_list **)stack);
525 return stree;
528 struct stree *top_stree(struct stree_stack *stack)
530 return last_ptr_list((struct ptr_list *)stack);
533 void free_slist(struct state_list **slist)
535 __free_ptr_list((struct ptr_list **)slist);
538 void free_stree_stack(struct stree_stack **stack)
540 __free_ptr_list((struct ptr_list **)stack);
543 void free_stack_and_strees(struct stree_stack **stree_stack)
545 struct stree *stree;
547 FOR_EACH_PTR(*stree_stack, stree) {
548 free_stree(&stree);
549 } END_FOR_EACH_PTR(stree);
550 free_stree_stack(stree_stack);
553 struct sm_state *set_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
554 struct symbol *sym, struct smatch_state *state)
556 struct stree *stree;
557 struct sm_state *sm;
559 stree = pop_stree(stack);
560 sm = set_state_stree(&stree, owner, name, sym, state);
561 push_stree(stack, stree);
563 return sm;
567 * get_sm_state_stack() gets the state for the top slist on the stack.
569 struct sm_state *get_sm_state_stree_stack(struct stree_stack *stack,
570 int owner, const char *name,
571 struct symbol *sym)
573 struct stree *stree;
574 struct sm_state *ret;
576 stree = pop_stree(&stack);
577 ret = get_sm_state_stree(stree, owner, name, sym);
578 push_stree(&stack, stree);
579 return ret;
582 struct smatch_state *get_state_stree_stack(struct stree_stack *stack,
583 int owner, const char *name,
584 struct symbol *sym)
586 struct sm_state *sm;
588 sm = get_sm_state_stree_stack(stack, owner, name, sym);
589 if (sm)
590 return sm->state;
591 return NULL;
594 static void match_states_stree(struct stree **one, struct stree **two)
596 struct smatch_state *tmp_state;
597 struct sm_state *sm;
598 struct state_list *add_to_one = NULL;
599 struct state_list *add_to_two = NULL;
600 AvlIter one_iter;
601 AvlIter two_iter;
603 avl_iter_begin(&one_iter, *one, FORWARD);
604 avl_iter_begin(&two_iter, *two, FORWARD);
606 for (;;) {
607 if (!one_iter.sm && !two_iter.sm)
608 break;
609 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
610 __set_fake_cur_stree_fast(*two);
611 tmp_state = __client_unmatched_state_function(one_iter.sm);
612 __pop_fake_cur_stree_fast();
613 sm = alloc_state_no_name(one_iter.sm->owner, one_iter.sm->name,
614 one_iter.sm->sym, tmp_state);
615 add_ptr_list(&add_to_two, sm);
616 avl_iter_next(&one_iter);
617 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
618 avl_iter_next(&one_iter);
619 avl_iter_next(&two_iter);
620 } else {
621 __set_fake_cur_stree_fast(*one);
622 tmp_state = __client_unmatched_state_function(two_iter.sm);
623 __pop_fake_cur_stree_fast();
624 sm = alloc_state_no_name(two_iter.sm->owner, two_iter.sm->name,
625 two_iter.sm->sym, tmp_state);
626 add_ptr_list(&add_to_one, sm);
627 avl_iter_next(&two_iter);
631 FOR_EACH_PTR(add_to_one, sm) {
632 avl_insert(one, sm);
633 } END_FOR_EACH_PTR(sm);
635 FOR_EACH_PTR(add_to_two, sm) {
636 avl_insert(two, sm);
637 } END_FOR_EACH_PTR(sm);
639 free_slist(&add_to_one);
640 free_slist(&add_to_two);
643 static void call_pre_merge_hooks(struct stree **one, struct stree **two)
645 struct sm_state *sm;
647 save_all_states();
649 __swap_cur_stree(*one);
650 FOR_EACH_SM(*two, sm) {
651 call_pre_merge_hook(sm);
652 } END_FOR_EACH_SM(sm);
653 *one = clone_stree(__get_cur_stree());
655 __swap_cur_stree(*two);
656 FOR_EACH_SM(*one, sm) {
657 call_pre_merge_hook(sm);
658 } END_FOR_EACH_SM(sm);
659 *two = clone_stree(__get_cur_stree());
661 restore_all_states();
664 static void clone_pool_havers_stree(struct stree **stree)
666 struct sm_state *sm, *tmp;
667 struct state_list *slist = NULL;
669 FOR_EACH_SM(*stree, sm) {
670 if (sm->pool) {
671 tmp = clone_sm(sm);
672 add_ptr_list(&slist, tmp);
674 } END_FOR_EACH_SM(sm);
676 FOR_EACH_PTR(slist, sm) {
677 avl_insert(stree, sm);
678 } END_FOR_EACH_PTR(sm);
680 free_slist(&slist);
683 int __stree_id;
686 * merge_slist() is called whenever paths merge, such as after
687 * an if statement. It takes the two slists and creates one.
689 static void __merge_stree(struct stree **to, struct stree *stree, int add_pool)
691 struct stree *results = NULL;
692 struct stree *implied_one = NULL;
693 struct stree *implied_two = NULL;
694 AvlIter one_iter;
695 AvlIter two_iter;
696 struct sm_state *tmp_sm;
698 if (out_of_memory())
699 return;
701 /* merging a null and nonnull path gives you only the nonnull path */
702 if (!stree)
703 return;
704 if (*to == stree)
705 return;
707 if (!*to) {
708 *to = clone_stree(stree);
709 return;
712 implied_one = clone_stree(*to);
713 implied_two = clone_stree(stree);
715 match_states_stree(&implied_one, &implied_two);
716 call_pre_merge_hooks(&implied_one, &implied_two);
718 if (add_pool) {
719 clone_pool_havers_stree(&implied_one);
720 clone_pool_havers_stree(&implied_two);
722 set_stree_id(&implied_one, ++__stree_id);
723 set_stree_id(&implied_two, ++__stree_id);
726 push_stree(&all_pools, implied_one);
727 push_stree(&all_pools, implied_two);
729 avl_iter_begin(&one_iter, implied_one, FORWARD);
730 avl_iter_begin(&two_iter, implied_two, FORWARD);
732 for (;;) {
733 if (!one_iter.sm && !two_iter.sm)
734 break;
735 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
736 sm_msg("error: Internal smatch error.");
737 avl_iter_next(&one_iter);
738 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
739 if (add_pool && one_iter.sm != two_iter.sm) {
740 one_iter.sm->pool = implied_one;
741 two_iter.sm->pool = implied_two;
743 tmp_sm = merge_sm_states(one_iter.sm, two_iter.sm);
744 add_possible_sm(tmp_sm, one_iter.sm);
745 add_possible_sm(tmp_sm, two_iter.sm);
746 avl_insert(&results, tmp_sm);
747 avl_iter_next(&one_iter);
748 avl_iter_next(&two_iter);
749 } else {
750 sm_msg("error: Internal smatch error.");
751 avl_iter_next(&two_iter);
755 free_stree(to);
756 *to = results;
759 void merge_stree(struct stree **to, struct stree *stree)
761 __merge_stree(to, stree, 1);
764 void merge_stree_no_pools(struct stree **to, struct stree *stree)
766 __merge_stree(to, stree, 0);
770 * This is unfortunately a bit subtle... The problem is that if a
771 * state is set on one fake stree but not the other then we should
772 * look up the the original state and use that as the unset state.
773 * Fortunately, after you pop your fake stree then the cur_slist should
774 * reflect the original state.
776 void merge_fake_stree(struct stree **to, struct stree *stree)
778 struct stree *one = *to;
779 struct stree *two = stree;
780 struct sm_state *sm;
781 struct state_list *add_to_one = NULL;
782 struct state_list *add_to_two = NULL;
783 AvlIter one_iter;
784 AvlIter two_iter;
786 if (!stree)
787 return;
788 if (*to == stree)
789 return;
790 if (!*to) {
791 *to = clone_stree(stree);
792 return;
795 avl_iter_begin(&one_iter, one, FORWARD);
796 avl_iter_begin(&two_iter, two, FORWARD);
798 for (;;) {
799 if (!one_iter.sm && !two_iter.sm)
800 break;
801 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
802 sm = get_sm_state(one_iter.sm->owner, one_iter.sm->name,
803 one_iter.sm->sym);
804 if (sm)
805 add_ptr_list(&add_to_two, sm);
806 avl_iter_next(&one_iter);
807 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
808 avl_iter_next(&one_iter);
809 avl_iter_next(&two_iter);
810 } else {
811 sm = get_sm_state(two_iter.sm->owner, two_iter.sm->name,
812 two_iter.sm->sym);
813 if (sm)
814 add_ptr_list(&add_to_one, sm);
815 avl_iter_next(&two_iter);
819 FOR_EACH_PTR(add_to_one, sm) {
820 avl_insert(&one, sm);
821 } END_FOR_EACH_PTR(sm);
823 FOR_EACH_PTR(add_to_two, sm) {
824 avl_insert(&two, sm);
825 } END_FOR_EACH_PTR(sm);
827 free_slist(&add_to_one);
828 free_slist(&add_to_two);
830 __merge_stree(&one, two, 1);
832 *to = one;
836 * filter_slist() removes any sm states "slist" holds in common with "filter"
838 void filter_stree(struct stree **stree, struct stree *filter)
840 struct stree *results = NULL;
841 AvlIter one_iter;
842 AvlIter two_iter;
844 avl_iter_begin(&one_iter, *stree, FORWARD);
845 avl_iter_begin(&two_iter, filter, FORWARD);
847 /* FIXME: This should probably be re-written with trees in mind */
849 for (;;) {
850 if (!one_iter.sm && !two_iter.sm)
851 break;
852 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
853 avl_insert(&results, one_iter.sm);
854 avl_iter_next(&one_iter);
855 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
856 if (one_iter.sm != two_iter.sm)
857 avl_insert(&results, one_iter.sm);
858 avl_iter_next(&one_iter);
859 avl_iter_next(&two_iter);
860 } else {
861 avl_iter_next(&two_iter);
865 free_stree(stree);
866 *stree = results;
871 * and_slist_stack() pops the top two slists, overwriting the one with
872 * the other and pushing it back on the stack.
874 void and_stree_stack(struct stree_stack **stack)
876 struct sm_state *tmp;
877 struct stree *right_stree = pop_stree(stack);
879 FOR_EACH_SM(right_stree, tmp) {
880 overwrite_sm_state_stree_stack(stack, tmp);
881 } END_FOR_EACH_SM(tmp);
882 free_stree(&right_stree);
886 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
887 * It pops the two slists from the top of the stack and merges them
888 * together in a way that preserves the things they have in common
889 * but creates a merged state for most of the rest.
890 * You could have code that had: if (foo || foo) { foo->baz;
891 * It's this function which ensures smatch does the right thing.
893 void or_stree_stack(struct stree_stack **pre_conds,
894 struct stree *cur_stree,
895 struct stree_stack **stack)
897 struct stree *new;
898 struct stree *old;
899 struct stree *pre_stree;
900 struct stree *res;
901 struct stree *tmp_stree;
903 new = pop_stree(stack);
904 old = pop_stree(stack);
906 pre_stree = pop_stree(pre_conds);
907 push_stree(pre_conds, clone_stree(pre_stree));
909 res = clone_stree(pre_stree);
910 overwrite_stree(old, &res);
912 tmp_stree = clone_stree(cur_stree);
913 overwrite_stree(new, &tmp_stree);
915 merge_stree(&res, tmp_stree);
916 filter_stree(&res, pre_stree);
918 push_stree(stack, res);
919 free_stree(&tmp_stree);
920 free_stree(&pre_stree);
921 free_stree(&new);
922 free_stree(&old);
926 * get_named_stree() is only used for gotos.
928 struct stree **get_named_stree(struct named_stree_stack *stack,
929 const char *name)
931 struct named_stree *tmp;
933 FOR_EACH_PTR(stack, tmp) {
934 if (!strcmp(tmp->name, name))
935 return &tmp->stree;
936 } END_FOR_EACH_PTR(tmp);
937 return NULL;
940 /* FIXME: These parameters are in a different order from expected */
941 void overwrite_stree(struct stree *from, struct stree **to)
943 struct sm_state *tmp;
945 FOR_EACH_SM(from, tmp) {
946 overwrite_sm_state_stree(to, tmp);
947 } END_FOR_EACH_SM(tmp);