db: prevent slow downs splitting returns apart
[smatch.git] / smatch_slist.c
blobbbcef6700967ba4f4234c80f7c38bda710837415
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->pool = NULL;
167 sm_state->left = NULL;
168 sm_state->right = NULL;
169 sm_state->nr_children = 1;
170 sm_state->possible = NULL;
171 add_ptr_list(&sm_state->possible, sm_state);
172 return sm_state;
175 static struct sm_state *alloc_state_no_name(int owner, const char *name,
176 struct symbol *sym,
177 struct smatch_state *state)
179 struct sm_state *tmp;
181 tmp = alloc_sm_state(owner, NULL, sym, state);
182 tmp->name = name;
183 return tmp;
186 int too_many_possible(struct sm_state *sm)
188 if (ptr_list_size((struct ptr_list *)sm->possible) >= 100)
189 return 1;
190 return 0;
193 void add_possible_sm(struct sm_state *to, struct sm_state *new)
195 struct sm_state *tmp;
196 int preserve = 1;
198 if (too_many_possible(to))
199 preserve = 0;
201 FOR_EACH_PTR(to->possible, tmp) {
202 if (cmp_sm_states(tmp, new, preserve) < 0)
203 continue;
204 else if (cmp_sm_states(tmp, new, preserve) == 0) {
205 return;
206 } else {
207 INSERT_CURRENT(new, tmp);
208 return;
210 } END_FOR_EACH_PTR(tmp);
211 add_ptr_list(&to->possible, new);
214 static void copy_possibles(struct sm_state *to, struct sm_state *from)
216 struct sm_state *tmp;
218 FOR_EACH_PTR(from->possible, tmp) {
219 add_possible_sm(to, tmp);
220 } END_FOR_EACH_PTR(tmp);
223 char *alloc_sname(const char *str)
225 char *tmp;
227 if (!str)
228 return NULL;
229 tmp = __alloc_sname(strlen(str) + 1);
230 strcpy(tmp, str);
231 return tmp;
234 int out_of_memory(void)
237 * I decided to use 50M here based on trial and error.
238 * It works out OK for the kernel and so it should work
239 * for most other projects as well.
241 if (sm_state_counter * sizeof(struct sm_state) >= 50000000)
242 return 1;
243 return 0;
246 int low_on_memory(void)
248 if (sm_state_counter * sizeof(struct sm_state) >= 25000000)
249 return 1;
250 return 0;
253 static void free_sm_state(struct sm_state *sm)
255 free_slist(&sm->possible);
257 * fixme. Free the actual state.
258 * Right now we leave it until the end of the function
259 * because we don't want to double free it.
260 * Use the freelist to not double free things
264 static void free_all_sm_states(struct allocation_blob *blob)
266 unsigned int size = sizeof(struct sm_state);
267 unsigned int offset = 0;
269 while (offset < blob->offset) {
270 free_sm_state((struct sm_state *)(blob->data + offset));
271 offset += size;
275 /* At the end of every function we free all the sm_states */
276 void free_every_single_sm_state(void)
278 struct allocator_struct *desc = &sm_state_allocator;
279 struct allocation_blob *blob = desc->blobs;
281 desc->blobs = NULL;
282 desc->allocations = 0;
283 desc->total_bytes = 0;
284 desc->useful_bytes = 0;
285 desc->freelist = NULL;
286 while (blob) {
287 struct allocation_blob *next = blob->next;
288 free_all_sm_states(blob);
289 blob_free(blob, desc->chunking);
290 blob = next;
292 clear_sname_alloc();
293 clear_smatch_state_alloc();
295 free_stack_and_strees(&all_pools);
296 sm_state_counter = 0;
299 struct sm_state *clone_sm(struct sm_state *s)
301 struct sm_state *ret;
303 ret = alloc_state_no_name(s->owner, s->name, s->sym, s->state);
304 ret->merged = s->merged;
305 ret->line = s->line;
306 /* clone_sm() doesn't copy the pools. Each state needs to have
307 only one pool. */
308 ret->possible = clone_slist(s->possible);
309 ret->left = s->left;
310 ret->right = s->right;
311 ret->nr_children = s->nr_children;
312 return ret;
315 int is_merged(struct sm_state *sm)
317 return sm->merged;
320 int is_leaf(struct sm_state *sm)
322 return !sm->merged;
325 int slist_has_state(struct state_list *slist, struct smatch_state *state)
327 struct sm_state *tmp;
329 FOR_EACH_PTR(slist, tmp) {
330 if (tmp->state == state)
331 return 1;
332 } END_FOR_EACH_PTR(tmp);
333 return 0;
336 struct state_list *clone_slist(struct state_list *from_slist)
338 struct sm_state *sm;
339 struct state_list *to_slist = NULL;
341 FOR_EACH_PTR(from_slist, sm) {
342 add_ptr_list(&to_slist, sm);
343 } END_FOR_EACH_PTR(sm);
344 return to_slist;
347 static struct smatch_state *merge_states(int owner, const char *name,
348 struct symbol *sym,
349 struct smatch_state *state1,
350 struct smatch_state *state2)
352 struct smatch_state *ret;
354 if (state1 == state2)
355 ret = state1;
356 else if (__has_merge_function(owner))
357 ret = __client_merge_function(owner, state1, state2);
358 else if (state1 == &ghost)
359 ret = state2;
360 else if (state2 == &ghost)
361 ret = state1;
362 else if (!state1 || !state2)
363 ret = &undefined;
364 else
365 ret = &merged;
366 return ret;
369 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
371 struct smatch_state *s;
372 struct sm_state *result;
374 if (one == two)
375 return one;
376 s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
377 result = alloc_state_no_name(one->owner, one->name, one->sym, s);
378 result->merged = 1;
379 result->left = one;
380 result->right = two;
381 result->nr_children = one->nr_children + two->nr_children;
382 copy_possibles(result, one);
383 copy_possibles(result, two);
386 * The ->line information is used by deref_check where we complain about
387 * checking pointers that have already been dereferenced. Let's say we
388 * dereference a pointer on both the true and false paths and then merge
389 * the states here. The result state is &derefed, but the ->line number
390 * is on the line where the pointer is merged not where it was
391 * dereferenced..
393 * So in that case, let's just pick one dereference and set the ->line
394 * to point at it.
398 if (result->state == one->state)
399 result->line = one->line;
400 if (result->state == two->state)
401 result->line = two->line;
403 if (option_debug ||
404 strcmp(check_name(one->owner), option_debug_check) == 0) {
405 struct sm_state *tmp;
406 int i = 0;
408 printf("%s:%d %s() merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
409 get_filename(), get_lineno(), get_function(),
410 check_name(one->owner), one->name,
411 show_state(one->state), one->line,
412 show_state(two->state), two->line,
413 show_state(s));
415 FOR_EACH_PTR(result->possible, tmp) {
416 if (i++)
417 printf(", ");
418 printf("%s", show_state(tmp->state));
419 } END_FOR_EACH_PTR(tmp);
420 printf(")\n");
423 return result;
426 struct sm_state *get_sm_state_stree(struct stree *stree, int owner, const char *name,
427 struct symbol *sym)
429 struct tracker tracker = {
430 .owner = owner,
431 .name = (char *)name,
432 .sym = sym,
435 if (!name)
436 return NULL;
439 return avl_lookup(stree, (struct sm_state *)&tracker);
442 struct smatch_state *get_state_stree(struct stree *stree,
443 int owner, const char *name,
444 struct symbol *sym)
446 struct sm_state *sm;
448 sm = get_sm_state_stree(stree, owner, name, sym);
449 if (sm)
450 return sm->state;
451 return NULL;
454 /* FIXME: this is almost exactly the same as set_sm_state_slist() */
455 void overwrite_sm_state_stree(struct stree **stree, struct sm_state *new)
457 avl_insert(stree, new);
460 void overwrite_sm_state_stree_stack(struct stree_stack **stack,
461 struct sm_state *sm)
463 struct stree *stree;
465 stree = pop_stree(stack);
466 overwrite_sm_state_stree(&stree, sm);
467 push_stree(stack, stree);
470 struct sm_state *set_state_stree(struct stree **stree, int owner, const char *name,
471 struct symbol *sym, struct smatch_state *state)
473 struct sm_state *new = alloc_sm_state(owner, name, sym, state);
475 avl_insert(stree, new);
476 return new;
479 void set_state_stree_perm(struct stree **stree, int owner, const char *name,
480 struct symbol *sym, struct smatch_state *state)
482 struct sm_state *sm;
484 sm = malloc(sizeof(*sm) + strlen(name) + 1);
485 memset(sm, 0, sizeof(*sm));
486 sm->owner = owner;
487 sm->name = (char *)(sm + 1);
488 strcpy((char *)sm->name, name);
489 sm->sym = sym;
490 sm->state = state;
492 overwrite_sm_state_stree(stree, sm);
495 void delete_state_stree(struct stree **stree, int owner, const char *name,
496 struct symbol *sym)
498 struct tracker tracker = {
499 .owner = owner,
500 .name = (char *)name,
501 .sym = sym,
504 avl_remove(stree, (struct sm_state *)&tracker);
507 void delete_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
508 struct symbol *sym)
510 struct stree *stree;
512 stree = pop_stree(stack);
513 delete_state_stree(&stree, owner, name, sym);
514 push_stree(stack, stree);
517 void push_stree(struct stree_stack **stack, struct stree *stree)
519 add_ptr_list(stack, stree);
522 struct stree *pop_stree(struct stree_stack **stack)
524 struct stree *stree;
526 stree = last_ptr_list((struct ptr_list *)*stack);
527 delete_ptr_list_last((struct ptr_list **)stack);
528 return stree;
531 struct stree *top_stree(struct stree_stack *stack)
533 return last_ptr_list((struct ptr_list *)stack);
536 void free_slist(struct state_list **slist)
538 __free_ptr_list((struct ptr_list **)slist);
541 void free_stree_stack(struct stree_stack **stack)
543 __free_ptr_list((struct ptr_list **)stack);
546 void free_stack_and_strees(struct stree_stack **stree_stack)
548 struct stree *stree;
550 FOR_EACH_PTR(*stree_stack, stree) {
551 free_stree(&stree);
552 } END_FOR_EACH_PTR(stree);
553 free_stree_stack(stree_stack);
556 struct sm_state *set_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
557 struct symbol *sym, struct smatch_state *state)
559 struct stree *stree;
560 struct sm_state *sm;
562 stree = pop_stree(stack);
563 sm = set_state_stree(&stree, owner, name, sym, state);
564 push_stree(stack, stree);
566 return sm;
570 * get_sm_state_stack() gets the state for the top slist on the stack.
572 struct sm_state *get_sm_state_stree_stack(struct stree_stack *stack,
573 int owner, const char *name,
574 struct symbol *sym)
576 struct stree *stree;
577 struct sm_state *ret;
579 stree = pop_stree(&stack);
580 ret = get_sm_state_stree(stree, owner, name, sym);
581 push_stree(&stack, stree);
582 return ret;
585 struct smatch_state *get_state_stree_stack(struct stree_stack *stack,
586 int owner, const char *name,
587 struct symbol *sym)
589 struct sm_state *sm;
591 sm = get_sm_state_stree_stack(stack, owner, name, sym);
592 if (sm)
593 return sm->state;
594 return NULL;
597 static void match_states_stree(struct stree **one, struct stree **two)
599 struct smatch_state *tmp_state;
600 struct sm_state *sm;
601 struct state_list *add_to_one = NULL;
602 struct state_list *add_to_two = NULL;
603 AvlIter one_iter;
604 AvlIter two_iter;
606 avl_iter_begin(&one_iter, *one, FORWARD);
607 avl_iter_begin(&two_iter, *two, FORWARD);
609 for (;;) {
610 if (!one_iter.sm && !two_iter.sm)
611 break;
612 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
613 __set_fake_cur_stree_fast(*two);
614 tmp_state = __client_unmatched_state_function(one_iter.sm);
615 __pop_fake_cur_stree_fast();
616 sm = alloc_state_no_name(one_iter.sm->owner, one_iter.sm->name,
617 one_iter.sm->sym, tmp_state);
618 add_ptr_list(&add_to_two, sm);
619 avl_iter_next(&one_iter);
620 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
621 avl_iter_next(&one_iter);
622 avl_iter_next(&two_iter);
623 } else {
624 __set_fake_cur_stree_fast(*one);
625 tmp_state = __client_unmatched_state_function(two_iter.sm);
626 __pop_fake_cur_stree_fast();
627 sm = alloc_state_no_name(two_iter.sm->owner, two_iter.sm->name,
628 two_iter.sm->sym, tmp_state);
629 add_ptr_list(&add_to_one, sm);
630 avl_iter_next(&two_iter);
634 FOR_EACH_PTR(add_to_one, sm) {
635 avl_insert(one, sm);
636 } END_FOR_EACH_PTR(sm);
638 FOR_EACH_PTR(add_to_two, sm) {
639 avl_insert(two, sm);
640 } END_FOR_EACH_PTR(sm);
642 free_slist(&add_to_one);
643 free_slist(&add_to_two);
646 static void call_pre_merge_hooks(struct stree **one, struct stree **two)
648 struct sm_state *sm;
650 save_all_states();
652 __swap_cur_stree(*one);
653 FOR_EACH_SM(*two, sm) {
654 call_pre_merge_hook(sm);
655 } END_FOR_EACH_SM(sm);
656 *one = clone_stree(__get_cur_stree());
658 __swap_cur_stree(*two);
659 FOR_EACH_SM(*one, sm) {
660 call_pre_merge_hook(sm);
661 } END_FOR_EACH_SM(sm);
662 *two = clone_stree(__get_cur_stree());
664 restore_all_states();
667 static void clone_pool_havers_stree(struct stree **stree)
669 struct sm_state *sm, *tmp;
670 struct state_list *slist = NULL;
672 FOR_EACH_SM(*stree, sm) {
673 if (sm->pool) {
674 tmp = clone_sm(sm);
675 add_ptr_list(&slist, tmp);
677 } END_FOR_EACH_SM(sm);
679 FOR_EACH_PTR(slist, sm) {
680 avl_insert(stree, sm);
681 } END_FOR_EACH_PTR(sm);
683 free_slist(&slist);
686 int __stree_id;
689 * merge_slist() is called whenever paths merge, such as after
690 * an if statement. It takes the two slists and creates one.
692 static void __merge_stree(struct stree **to, struct stree *stree, int add_pool)
694 struct stree *results = NULL;
695 struct stree *implied_one = NULL;
696 struct stree *implied_two = NULL;
697 AvlIter one_iter;
698 AvlIter two_iter;
699 struct sm_state *tmp_sm;
701 if (out_of_memory())
702 return;
704 /* merging a null and nonnull path gives you only the nonnull path */
705 if (!stree)
706 return;
707 if (*to == stree)
708 return;
710 if (!*to) {
711 *to = clone_stree(stree);
712 return;
715 implied_one = clone_stree(*to);
716 implied_two = clone_stree(stree);
718 match_states_stree(&implied_one, &implied_two);
719 call_pre_merge_hooks(&implied_one, &implied_two);
721 if (add_pool) {
722 clone_pool_havers_stree(&implied_one);
723 clone_pool_havers_stree(&implied_two);
725 set_stree_id(&implied_one, ++__stree_id);
726 set_stree_id(&implied_two, ++__stree_id);
727 if (implied_one->base_stree)
728 set_stree_id(&implied_one->base_stree, ++__stree_id);
729 if (implied_two->base_stree)
730 set_stree_id(&implied_two->base_stree, ++__stree_id);
733 push_stree(&all_pools, implied_one);
734 push_stree(&all_pools, implied_two);
736 avl_iter_begin(&one_iter, implied_one, FORWARD);
737 avl_iter_begin(&two_iter, implied_two, FORWARD);
739 for (;;) {
740 if (!one_iter.sm || !two_iter.sm)
741 break;
742 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
743 sm_msg("error: Internal smatch error.");
744 avl_iter_next(&one_iter);
745 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
746 if (add_pool && one_iter.sm != two_iter.sm) {
747 one_iter.sm->pool = implied_one;
748 if (implied_one->base_stree)
749 one_iter.sm->pool = implied_one->base_stree;
750 two_iter.sm->pool = implied_two;
751 if (implied_two->base_stree)
752 two_iter.sm->pool = implied_two->base_stree;
754 tmp_sm = merge_sm_states(one_iter.sm, two_iter.sm);
755 add_possible_sm(tmp_sm, one_iter.sm);
756 add_possible_sm(tmp_sm, two_iter.sm);
757 avl_insert(&results, tmp_sm);
758 avl_iter_next(&one_iter);
759 avl_iter_next(&two_iter);
760 } else {
761 sm_msg("error: Internal smatch error.");
762 avl_iter_next(&two_iter);
766 free_stree(to);
767 *to = results;
770 void merge_stree(struct stree **to, struct stree *stree)
772 __merge_stree(to, stree, 1);
775 void merge_stree_no_pools(struct stree **to, struct stree *stree)
777 __merge_stree(to, stree, 0);
781 * This is unfortunately a bit subtle... The problem is that if a
782 * state is set on one fake stree but not the other then we should
783 * look up the the original state and use that as the unset state.
784 * Fortunately, after you pop your fake stree then the cur_slist should
785 * reflect the original state.
787 void merge_fake_stree(struct stree **to, struct stree *stree)
789 struct stree *one = *to;
790 struct stree *two = stree;
791 struct sm_state *sm;
792 struct state_list *add_to_one = NULL;
793 struct state_list *add_to_two = NULL;
794 AvlIter one_iter;
795 AvlIter two_iter;
797 if (!stree)
798 return;
799 if (*to == stree)
800 return;
801 if (!*to) {
802 *to = clone_stree(stree);
803 return;
806 avl_iter_begin(&one_iter, one, FORWARD);
807 avl_iter_begin(&two_iter, two, FORWARD);
809 for (;;) {
810 if (!one_iter.sm && !two_iter.sm)
811 break;
812 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
813 sm = get_sm_state(one_iter.sm->owner, one_iter.sm->name,
814 one_iter.sm->sym);
815 if (sm)
816 add_ptr_list(&add_to_two, sm);
817 avl_iter_next(&one_iter);
818 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
819 avl_iter_next(&one_iter);
820 avl_iter_next(&two_iter);
821 } else {
822 sm = get_sm_state(two_iter.sm->owner, two_iter.sm->name,
823 two_iter.sm->sym);
824 if (sm)
825 add_ptr_list(&add_to_one, sm);
826 avl_iter_next(&two_iter);
830 FOR_EACH_PTR(add_to_one, sm) {
831 avl_insert(&one, sm);
832 } END_FOR_EACH_PTR(sm);
834 FOR_EACH_PTR(add_to_two, sm) {
835 avl_insert(&two, sm);
836 } END_FOR_EACH_PTR(sm);
838 one->base_stree = clone_stree(__get_cur_stree());
839 FOR_EACH_SM(one, sm) {
840 avl_insert(&one->base_stree, sm);
841 } END_FOR_EACH_SM(sm);
843 two->base_stree = clone_stree(__get_cur_stree());
844 FOR_EACH_SM(two, sm) {
845 avl_insert(&two->base_stree, sm);
846 } END_FOR_EACH_SM(sm);
848 free_slist(&add_to_one);
849 free_slist(&add_to_two);
851 __merge_stree(&one, two, 1);
853 *to = one;
857 * filter_slist() removes any sm states "slist" holds in common with "filter"
859 void filter_stree(struct stree **stree, struct stree *filter)
861 struct stree *results = NULL;
862 AvlIter one_iter;
863 AvlIter two_iter;
865 avl_iter_begin(&one_iter, *stree, FORWARD);
866 avl_iter_begin(&two_iter, filter, FORWARD);
868 /* FIXME: This should probably be re-written with trees in mind */
870 for (;;) {
871 if (!one_iter.sm && !two_iter.sm)
872 break;
873 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
874 avl_insert(&results, one_iter.sm);
875 avl_iter_next(&one_iter);
876 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
877 if (one_iter.sm != two_iter.sm)
878 avl_insert(&results, one_iter.sm);
879 avl_iter_next(&one_iter);
880 avl_iter_next(&two_iter);
881 } else {
882 avl_iter_next(&two_iter);
886 free_stree(stree);
887 *stree = results;
892 * and_slist_stack() pops the top two slists, overwriting the one with
893 * the other and pushing it back on the stack.
895 void and_stree_stack(struct stree_stack **stack)
897 struct sm_state *tmp;
898 struct stree *right_stree = pop_stree(stack);
900 FOR_EACH_SM(right_stree, tmp) {
901 overwrite_sm_state_stree_stack(stack, tmp);
902 } END_FOR_EACH_SM(tmp);
903 free_stree(&right_stree);
907 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
908 * It pops the two slists from the top of the stack and merges them
909 * together in a way that preserves the things they have in common
910 * but creates a merged state for most of the rest.
911 * You could have code that had: if (foo || foo) { foo->baz;
912 * It's this function which ensures smatch does the right thing.
914 void or_stree_stack(struct stree_stack **pre_conds,
915 struct stree *cur_stree,
916 struct stree_stack **stack)
918 struct stree *new;
919 struct stree *old;
920 struct stree *pre_stree;
921 struct stree *res;
922 struct stree *tmp_stree;
924 new = pop_stree(stack);
925 old = pop_stree(stack);
927 pre_stree = pop_stree(pre_conds);
928 push_stree(pre_conds, clone_stree(pre_stree));
930 res = clone_stree(pre_stree);
931 overwrite_stree(old, &res);
933 tmp_stree = clone_stree(cur_stree);
934 overwrite_stree(new, &tmp_stree);
936 merge_stree(&res, tmp_stree);
937 filter_stree(&res, pre_stree);
939 push_stree(stack, res);
940 free_stree(&tmp_stree);
941 free_stree(&pre_stree);
942 free_stree(&new);
943 free_stree(&old);
947 * get_named_stree() is only used for gotos.
949 struct stree **get_named_stree(struct named_stree_stack *stack,
950 const char *name,
951 struct symbol *sym)
953 struct named_stree *tmp;
955 FOR_EACH_PTR(stack, tmp) {
956 if (tmp->sym == sym &&
957 strcmp(tmp->name, name) == 0)
958 return &tmp->stree;
959 } END_FOR_EACH_PTR(tmp);
960 return NULL;
963 /* FIXME: These parameters are in a different order from expected */
964 void overwrite_stree(struct stree *from, struct stree **to)
966 struct sm_state *tmp;
968 FOR_EACH_SM(from, tmp) {
969 overwrite_sm_state_stree(to, tmp);
970 } END_FOR_EACH_SM(tmp);