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
21 #include "smatch_slist.h"
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
);
32 static struct stree_stack
*all_pools
;
34 const char *show_sm(struct sm_state
*sm
)
44 pos
= snprintf(buf
, sizeof(buf
), "[%s] %s %p = '%s'%s",
45 check_name(sm
->owner
), sm
->name
, sm
->sym
, show_state(sm
->state
),
46 sm
->merged
? " [merged]" : "");
47 if (pos
> sizeof(buf
))
50 if (ptr_list_size((struct ptr_list
*)sm
->possible
) == 1)
51 return alloc_sname(buf
);
53 pos
+= snprintf(buf
+ pos
, sizeof(buf
) - pos
, " (");
54 if (pos
> sizeof(buf
))
57 FOR_EACH_PTR(sm
->possible
, tmp
) {
59 pos
+= snprintf(buf
+ pos
, sizeof(buf
) - pos
, ", ");
60 if (pos
> sizeof(buf
))
62 pos
+= snprintf(buf
+ pos
, sizeof(buf
) - pos
, "%s",
63 show_state(tmp
->state
));
64 if (pos
> sizeof(buf
))
66 } END_FOR_EACH_PTR(tmp
);
67 snprintf(buf
+ pos
, sizeof(buf
) - pos
, ")");
69 return alloc_sname(buf
);
72 for (i
= 0; i
< 3; i
++)
73 buf
[sizeof(buf
) - 2 - i
] = '.';
74 return alloc_sname(buf
);
77 void __print_stree(struct stree
*stree
)
82 sm_msg("dumping stree [%ld states]", stree_count(stree
));
83 FOR_EACH_SM(stree
, sm
) {
84 sm_printf("%s\n", show_sm(sm
));
85 } END_FOR_EACH_SM(sm
);
90 void __diff_stree(struct stree
*old
, struct stree
*new)
95 avl_iter_begin(&old_iter
, old
, FORWARD
);
96 avl_iter_begin(&new_iter
, new, FORWARD
);
99 if (!old_iter
.sm
&& !new_iter
.sm
)
101 if (cmp_tracker(old_iter
.sm
, new_iter
.sm
) < 0) {
102 sm_msg(" OLD: %s", show_sm(old_iter
.sm
));
103 sm_msg(" NEW: <none>");
104 avl_iter_next(&old_iter
);
108 if (cmp_tracker(old_iter
.sm
, new_iter
.sm
) > 0) {
109 sm_msg(" OLD: <none>");
110 sm_msg(" NEW: %s", show_sm(new_iter
.sm
));
111 avl_iter_next(&new_iter
);
115 if (old_iter
.sm
== new_iter
.sm
) {
116 sm_msg("SAME: %s", show_sm(old_iter
.sm
));
118 sm_msg(" OLD: %s", show_sm(old_iter
.sm
));
119 sm_msg(" NEW: %s", show_sm(new_iter
.sm
));
122 avl_iter_next(&old_iter
);
123 avl_iter_next(&new_iter
);
127 /* NULL states go at the end to simplify merge_slist */
128 int cmp_tracker(const struct sm_state
*a
, const struct sm_state
*b
)
139 if (a
->owner
< b
->owner
)
141 if (a
->owner
> b
->owner
)
144 ret
= strcmp(a
->name
, b
->name
);
150 if (!b
->sym
&& a
->sym
)
152 if (!a
->sym
&& b
->sym
)
163 void allocate_dynamic_states_array(int num_checks
)
165 dynamic_states
= calloc(num_checks
, sizeof(int));
168 void set_dynamic_states(unsigned short owner
)
170 dynamic_states
[owner
] = true;
173 bool has_dynamic_states(unsigned short owner
)
175 if (owner
>= num_checks
)
177 return dynamic_states
[owner
];
180 static int cmp_possible_sm(const struct sm_state
*a
, const struct sm_state
*b
, int preserve
)
187 if (!has_dynamic_states(a
->owner
)) {
188 if (a
->state
> b
->state
)
190 if (a
->state
< b
->state
)
195 if (a
->owner
== SMATCH_EXTRA
) {
197 * In Smatch extra you can have borrowed implications.
199 * FIXME: review how borrowed implications work and if they
200 * are the best way. See also smatch_implied.c.
203 ret
= cmp_tracker(a
, b
);
208 * We want to preserve leaf states. They're use to split
209 * returns in smatch_db.c.
213 if (a
->merged
&& !b
->merged
)
219 if (!a
->state
->name
|| !b
->state
->name
)
222 return strcmp(a
->state
->name
, b
->state
->name
);
225 struct sm_state
*alloc_sm_state(int owner
, const char *name
,
226 struct symbol
*sym
, struct smatch_state
*state
)
228 struct sm_state
*sm_state
= __alloc_sm_state(0);
232 sm_state
->name
= alloc_sname(name
);
233 sm_state
->owner
= owner
;
235 sm_state
->state
= state
;
236 sm_state
->line
= get_lineno();
237 sm_state
->merged
= 0;
238 sm_state
->pool
= NULL
;
239 sm_state
->left
= NULL
;
240 sm_state
->right
= NULL
;
241 sm_state
->possible
= NULL
;
242 add_ptr_list(&sm_state
->possible
, sm_state
);
246 static struct sm_state
*alloc_state_no_name(int owner
, const char *name
,
248 struct smatch_state
*state
)
250 struct sm_state
*tmp
;
252 tmp
= alloc_sm_state(owner
, NULL
, sym
, state
);
257 int too_many_possible(struct sm_state
*sm
)
259 if (ptr_list_size((struct ptr_list
*)sm
->possible
) >= 100)
264 void add_possible_sm(struct sm_state
*to
, struct sm_state
*new)
266 struct sm_state
*tmp
;
270 if (too_many_possible(to
))
273 FOR_EACH_PTR(to
->possible
, tmp
) {
274 cmp
= cmp_possible_sm(tmp
, new, preserve
);
280 INSERT_CURRENT(new, tmp
);
283 } END_FOR_EACH_PTR(tmp
);
284 add_ptr_list(&to
->possible
, new);
287 static void copy_possibles(struct sm_state
*to
, struct sm_state
*one
, struct sm_state
*two
)
289 struct sm_state
*large
= one
;
290 struct sm_state
*small
= two
;
291 struct sm_state
*tmp
;
294 * We spend a lot of time copying the possible lists. I've tried to
295 * optimize the process a bit.
299 if (ptr_list_size((struct ptr_list
*)two
->possible
) >
300 ptr_list_size((struct ptr_list
*)one
->possible
)) {
305 to
->possible
= clone_slist(large
->possible
);
306 add_possible_sm(to
, to
);
307 FOR_EACH_PTR(small
->possible
, tmp
) {
308 add_possible_sm(to
, tmp
);
309 } END_FOR_EACH_PTR(tmp
);
312 char *alloc_sname(const char *str
)
318 tmp
= __alloc_sname(strlen(str
) + 1);
323 static struct symbol
*oom_func
;
324 static int oom_limit
= 3000000; /* Start with a 3GB limit */
325 int out_of_memory(void)
331 * I decided to use 50M here based on trial and error.
332 * It works out OK for the kernel and so it should work
333 * for most other projects as well.
335 if (sm_state_counter
* sizeof(struct sm_state
) >= 100000000)
339 * We're reading from statm to figure out how much memory we
340 * are using. The problem is that at the end of the function
341 * we release the memory, so that it can be re-used but it
342 * stays in cache, it's not released to the OS. So then if
343 * we allocate memory for different purposes we can easily
344 * hit the 3GB limit on the next function, so that's why I give
345 * the next function an extra 100MB to work with.
348 if (get_mem_kb() > oom_limit
) {
349 oom_func
= cur_func_sym
;
351 sm_perror("OOM: %luKb sm_state_count = %d", get_mem_kb(), sm_state_counter
);
359 int low_on_memory(void)
361 if (sm_state_counter
* sizeof(struct sm_state
) >= 25000000)
366 static void free_sm_state(struct sm_state
*sm
)
368 free_slist(&sm
->possible
);
370 * fixme. Free the actual state.
371 * Right now we leave it until the end of the function
372 * because we don't want to double free it.
373 * Use the freelist to not double free things
377 static void free_all_sm_states(struct allocation_blob
*blob
)
379 unsigned int size
= sizeof(struct sm_state
);
380 unsigned int offset
= 0;
382 while (offset
< blob
->offset
) {
383 free_sm_state((struct sm_state
*)(blob
->data
+ offset
));
388 /* At the end of every function we free all the sm_states */
389 void free_every_single_sm_state(void)
391 struct allocator_struct
*desc
= &sm_state_allocator
;
392 struct allocation_blob
*blob
= desc
->blobs
;
395 desc
->allocations
= 0;
396 desc
->total_bytes
= 0;
397 desc
->useful_bytes
= 0;
398 desc
->freelist
= NULL
;
400 struct allocation_blob
*next
= blob
->next
;
401 free_all_sm_states(blob
);
402 blob_free(blob
, desc
->chunking
);
406 clear_smatch_state_alloc();
408 free_stack_and_strees(&all_pools
);
409 sm_state_counter
= 0;
416 unsigned long get_pool_count(void)
418 return ptr_list_size((struct ptr_list
*)all_pools
);
421 struct sm_state
*clone_sm(struct sm_state
*s
)
423 struct sm_state
*ret
;
425 ret
= alloc_state_no_name(s
->owner
, s
->name
, s
->sym
, s
->state
);
426 ret
->merged
= s
->merged
;
428 /* clone_sm() doesn't copy the pools. Each state needs to have
430 ret
->possible
= clone_slist(s
->possible
);
432 ret
->right
= s
->right
;
436 int is_merged(struct sm_state
*sm
)
441 int is_leaf(struct sm_state
*sm
)
450 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
452 struct sm_state
*tmp
;
454 FOR_EACH_PTR(slist
, tmp
) {
455 if (tmp
->state
== state
)
457 } END_FOR_EACH_PTR(tmp
);
461 struct state_list
*clone_slist(struct state_list
*from_slist
)
464 struct state_list
*to_slist
= NULL
;
466 FOR_EACH_PTR(from_slist
, sm
) {
467 add_ptr_list(&to_slist
, sm
);
468 } END_FOR_EACH_PTR(sm
);
472 static struct smatch_state
*merge_states(int owner
, const char *name
,
474 struct smatch_state
*state1
,
475 struct smatch_state
*state2
)
477 struct smatch_state
*ret
;
479 if (state1
== state2
)
481 else if (__has_merge_function(owner
))
482 ret
= __client_merge_function(owner
, state1
, state2
);
483 else if (!state1
|| !state2
)
490 struct sm_state
*merge_sm_states(struct sm_state
*one
, struct sm_state
*two
)
492 struct smatch_state
*s
;
493 struct sm_state
*result
;
496 if (one
->state
->data
&& !has_dynamic_states(one
->owner
))
497 sm_msg("dynamic state: %s", show_sm(one
));
501 if (out_of_memory()) {
503 sm_warning("Function too hairy. No more merges.");
508 s
= merge_states(one
->owner
, one
->name
, one
->sym
, one
->state
, two
->state
);
509 result
= alloc_state_no_name(one
->owner
, one
->name
, one
->sym
, s
);
514 copy_possibles(result
, one
, two
);
517 * The ->line information is used by deref_check where we complain about
518 * checking pointers that have already been dereferenced. Let's say we
519 * dereference a pointer on both the true and false paths and then merge
520 * the states here. The result state is &derefed, but the ->line number
521 * is on the line where the pointer is merged not where it was
524 * So in that case, let's just pick one dereference and set the ->line
529 if (result
->state
== one
->state
)
530 result
->line
= one
->line
;
531 if (result
->state
== two
->state
)
532 result
->line
= two
->line
;
534 if (debug_on(check_name(one
->owner
), one
->name
)) {
535 struct sm_state
*tmp
;
538 printf("%s:%d %s() merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
539 get_filename(), get_lineno(), get_function(),
540 check_name(one
->owner
), one
->name
,
541 show_state(one
->state
), one
->line
,
542 show_state(two
->state
), two
->line
,
545 FOR_EACH_PTR(result
->possible
, tmp
) {
548 printf("%s", show_state(tmp
->state
));
549 } END_FOR_EACH_PTR(tmp
);
556 struct sm_state
*get_sm_state_stree(struct stree
*stree
, int owner
, const char *name
,
559 struct tracker tracker
= {
561 .name
= (char *)name
,
568 return avl_lookup(stree
, (struct sm_state
*)&tracker
);
571 struct smatch_state
*get_state_stree(struct stree
*stree
,
572 int owner
, const char *name
,
577 sm
= get_sm_state_stree(stree
, owner
, name
, sym
);
583 /* FIXME: this is almost exactly the same as set_sm_state_slist() */
584 void overwrite_sm_state_stree(struct stree
**stree
, struct sm_state
*new)
586 avl_insert(stree
, new);
589 void overwrite_sm_state_stree_stack(struct stree_stack
**stack
,
594 stree
= pop_stree(stack
);
595 overwrite_sm_state_stree(&stree
, sm
);
596 push_stree(stack
, stree
);
599 struct sm_state
*set_state_stree(struct stree
**stree
, int owner
, const char *name
,
600 struct symbol
*sym
, struct smatch_state
*state
)
602 struct sm_state
*new = alloc_sm_state(owner
, name
, sym
, state
);
604 avl_insert(stree
, new);
608 void set_state_stree_perm(struct stree
**stree
, int owner
, const char *name
,
609 struct symbol
*sym
, struct smatch_state
*state
)
613 sm
= malloc(sizeof(*sm
) + strlen(name
) + 1);
614 memset(sm
, 0, sizeof(*sm
));
615 sm
->line
= get_lineno();
617 sm
->name
= (char *)(sm
+ 1);
618 strcpy((char *)sm
->name
, name
);
622 overwrite_sm_state_stree(stree
, sm
);
625 void delete_state_stree(struct stree
**stree
, int owner
, const char *name
,
628 struct tracker tracker
= {
630 .name
= (char *)name
,
634 avl_remove(stree
, (struct sm_state
*)&tracker
);
637 void delete_state_stree_stack(struct stree_stack
**stack
, int owner
, const char *name
,
642 stree
= pop_stree(stack
);
643 delete_state_stree(&stree
, owner
, name
, sym
);
644 push_stree(stack
, stree
);
647 void push_stree(struct stree_stack
**stack
, struct stree
*stree
)
649 add_ptr_list(stack
, stree
);
652 struct stree
*pop_stree(struct stree_stack
**stack
)
656 stree
= last_ptr_list((struct ptr_list
*)*stack
);
657 delete_ptr_list_last((struct ptr_list
**)stack
);
661 struct stree
*top_stree(struct stree_stack
*stack
)
663 return last_ptr_list((struct ptr_list
*)stack
);
666 void free_slist(struct state_list
**slist
)
668 __free_ptr_list((struct ptr_list
**)slist
);
671 void free_stree_stack(struct stree_stack
**stack
)
673 __free_ptr_list((struct ptr_list
**)stack
);
676 void free_stack_and_strees(struct stree_stack
**stree_stack
)
680 FOR_EACH_PTR(*stree_stack
, stree
) {
682 } END_FOR_EACH_PTR(stree
);
683 free_stree_stack(stree_stack
);
686 struct sm_state
*set_state_stree_stack(struct stree_stack
**stack
, int owner
, const char *name
,
687 struct symbol
*sym
, struct smatch_state
*state
)
692 stree
= pop_stree(stack
);
693 sm
= set_state_stree(&stree
, owner
, name
, sym
, state
);
694 push_stree(stack
, stree
);
700 * get_sm_state_stack() gets the state for the top slist on the stack.
702 struct sm_state
*get_sm_state_stree_stack(struct stree_stack
*stack
,
703 int owner
, const char *name
,
707 struct sm_state
*ret
;
709 stree
= pop_stree(&stack
);
710 ret
= get_sm_state_stree(stree
, owner
, name
, sym
);
711 push_stree(&stack
, stree
);
715 struct smatch_state
*get_state_stree_stack(struct stree_stack
*stack
,
716 int owner
, const char *name
,
721 sm
= get_sm_state_stree_stack(stack
, owner
, name
, sym
);
727 static void match_states_stree(struct stree
**one
, struct stree
**two
)
729 struct smatch_state
*tmp_state
;
731 struct state_list
*add_to_one
= NULL
;
732 struct state_list
*add_to_two
= NULL
;
736 __set_cur_stree_readonly();
738 avl_iter_begin(&one_iter
, *one
, FORWARD
);
739 avl_iter_begin(&two_iter
, *two
, FORWARD
);
742 if (!one_iter
.sm
&& !two_iter
.sm
)
744 if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) < 0) {
745 __set_fake_cur_stree_fast(*two
);
746 __in_unmatched_hook
++;
747 tmp_state
= __client_unmatched_state_function(one_iter
.sm
);
748 __in_unmatched_hook
--;
749 __pop_fake_cur_stree_fast();
750 sm
= alloc_state_no_name(one_iter
.sm
->owner
, one_iter
.sm
->name
,
751 one_iter
.sm
->sym
, tmp_state
);
752 add_ptr_list(&add_to_two
, sm
);
753 avl_iter_next(&one_iter
);
754 } else if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) == 0) {
755 avl_iter_next(&one_iter
);
756 avl_iter_next(&two_iter
);
758 __set_fake_cur_stree_fast(*one
);
759 __in_unmatched_hook
++;
760 tmp_state
= __client_unmatched_state_function(two_iter
.sm
);
761 __in_unmatched_hook
--;
762 __pop_fake_cur_stree_fast();
763 sm
= alloc_state_no_name(two_iter
.sm
->owner
, two_iter
.sm
->name
,
764 two_iter
.sm
->sym
, tmp_state
);
765 add_ptr_list(&add_to_one
, sm
);
766 avl_iter_next(&two_iter
);
770 __set_cur_stree_writable();
772 FOR_EACH_PTR(add_to_one
, sm
) {
774 } END_FOR_EACH_PTR(sm
);
776 FOR_EACH_PTR(add_to_two
, sm
) {
778 } END_FOR_EACH_PTR(sm
);
780 free_slist(&add_to_one
);
781 free_slist(&add_to_two
);
784 static void call_pre_merge_hooks(struct stree
**one
, struct stree
**two
)
786 struct sm_state
*sm
, *cur
;
789 __in_unmatched_hook
++;
791 __set_fake_cur_stree_fast(*one
);
792 __push_fake_cur_stree();
793 FOR_EACH_SM(*two
, sm
) {
794 cur
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
797 call_pre_merge_hook(cur
, sm
);
798 } END_FOR_EACH_SM(sm
);
799 new = __pop_fake_cur_stree();
800 overwrite_stree(new, one
);
802 __pop_fake_cur_stree_fast();
804 __set_fake_cur_stree_fast(*two
);
805 __push_fake_cur_stree();
806 FOR_EACH_SM(*one
, sm
) {
807 cur
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
810 call_pre_merge_hook(cur
, sm
);
811 } END_FOR_EACH_SM(sm
);
812 new = __pop_fake_cur_stree();
813 overwrite_stree(new, two
);
815 __pop_fake_cur_stree_fast();
817 __in_unmatched_hook
--;
820 static void clone_pool_havers_stree(struct stree
**stree
)
822 struct sm_state
*sm
, *tmp
;
823 struct state_list
*slist
= NULL
;
825 FOR_EACH_SM(*stree
, sm
) {
828 add_ptr_list(&slist
, tmp
);
830 } END_FOR_EACH_SM(sm
);
832 FOR_EACH_PTR(slist
, sm
) {
833 avl_insert(stree
, sm
);
834 } END_FOR_EACH_PTR(sm
);
842 * merge_slist() is called whenever paths merge, such as after
843 * an if statement. It takes the two slists and creates one.
845 static void __merge_stree(struct stree
**to
, struct stree
*stree
, int add_pool
)
847 struct stree
*results
= NULL
;
848 struct stree
*implied_one
= NULL
;
849 struct stree
*implied_two
= NULL
;
852 struct sm_state
*one
, *two
, *res
;
857 /* merging a null and nonnull path gives you only the nonnull path */
864 *to
= clone_stree(stree
);
868 implied_one
= clone_stree(*to
);
869 implied_two
= clone_stree(stree
);
871 match_states_stree(&implied_one
, &implied_two
);
872 call_pre_merge_hooks(&implied_one
, &implied_two
);
875 clone_pool_havers_stree(&implied_one
);
876 clone_pool_havers_stree(&implied_two
);
878 set_stree_id(&implied_one
, ++__stree_id
);
879 set_stree_id(&implied_two
, ++__stree_id
);
880 if (implied_one
->base_stree
)
881 set_stree_id(&implied_one
->base_stree
, ++__stree_id
);
882 if (implied_two
->base_stree
)
883 set_stree_id(&implied_two
->base_stree
, ++__stree_id
);
886 push_stree(&all_pools
, implied_one
);
887 push_stree(&all_pools
, implied_two
);
889 avl_iter_begin(&one_iter
, implied_one
, FORWARD
);
890 avl_iter_begin(&two_iter
, implied_two
, FORWARD
);
893 if (!one_iter
.sm
|| !two_iter
.sm
)
900 avl_insert(&results
, one
);
905 one
->pool
= implied_one
;
906 if (implied_one
->base_stree
)
907 one
->pool
= implied_one
->base_stree
;
908 two
->pool
= implied_two
;
909 if (implied_two
->base_stree
)
910 two
->pool
= implied_two
->base_stree
;
912 res
= merge_sm_states(one
, two
);
913 add_possible_sm(res
, one
);
914 add_possible_sm(res
, two
);
915 avl_insert(&results
, res
);
917 avl_iter_next(&one_iter
);
918 avl_iter_next(&two_iter
);
925 void merge_stree(struct stree
**to
, struct stree
*stree
)
927 __merge_stree(to
, stree
, 1);
930 void merge_stree_no_pools(struct stree
**to
, struct stree
*stree
)
932 __merge_stree(to
, stree
, 0);
936 * This is unfortunately a bit subtle... The problem is that if a
937 * state is set on one fake stree but not the other then we should
938 * look up the the original state and use that as the unset state.
939 * Fortunately, after you pop your fake stree then the cur_slist should
940 * reflect the original state.
942 void merge_fake_stree(struct stree
**to
, struct stree
*stree
)
944 struct stree
*one
= *to
;
945 struct stree
*two
= stree
;
947 struct state_list
*add_to_one
= NULL
;
948 struct state_list
*add_to_two
= NULL
;
957 *to
= clone_stree(stree
);
961 avl_iter_begin(&one_iter
, one
, FORWARD
);
962 avl_iter_begin(&two_iter
, two
, FORWARD
);
965 if (!one_iter
.sm
&& !two_iter
.sm
)
967 if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) < 0) {
968 sm
= get_sm_state(one_iter
.sm
->owner
, one_iter
.sm
->name
,
971 add_ptr_list(&add_to_two
, sm
);
972 avl_iter_next(&one_iter
);
973 } else if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) == 0) {
974 avl_iter_next(&one_iter
);
975 avl_iter_next(&two_iter
);
977 sm
= get_sm_state(two_iter
.sm
->owner
, two_iter
.sm
->name
,
980 add_ptr_list(&add_to_one
, sm
);
981 avl_iter_next(&two_iter
);
985 FOR_EACH_PTR(add_to_one
, sm
) {
986 avl_insert(&one
, sm
);
987 } END_FOR_EACH_PTR(sm
);
989 FOR_EACH_PTR(add_to_two
, sm
) {
990 avl_insert(&two
, sm
);
991 } END_FOR_EACH_PTR(sm
);
993 one
->base_stree
= clone_stree(__get_cur_stree());
994 FOR_EACH_SM(one
, sm
) {
995 avl_insert(&one
->base_stree
, sm
);
996 } END_FOR_EACH_SM(sm
);
998 two
->base_stree
= clone_stree(__get_cur_stree());
999 FOR_EACH_SM(two
, sm
) {
1000 avl_insert(&two
->base_stree
, sm
);
1001 } END_FOR_EACH_SM(sm
);
1003 free_slist(&add_to_one
);
1004 free_slist(&add_to_two
);
1006 __merge_stree(&one
, two
, 1);
1012 * filter_slist() removes any sm states "slist" holds in common with "filter"
1014 void filter_stree(struct stree
**stree
, struct stree
*filter
)
1016 struct stree
*results
= NULL
;
1020 avl_iter_begin(&one_iter
, *stree
, FORWARD
);
1021 avl_iter_begin(&two_iter
, filter
, FORWARD
);
1023 /* FIXME: This should probably be re-written with trees in mind */
1026 if (!one_iter
.sm
&& !two_iter
.sm
)
1028 if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) < 0) {
1029 avl_insert(&results
, one_iter
.sm
);
1030 avl_iter_next(&one_iter
);
1031 } else if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) == 0) {
1032 if (one_iter
.sm
!= two_iter
.sm
)
1033 avl_insert(&results
, one_iter
.sm
);
1034 avl_iter_next(&one_iter
);
1035 avl_iter_next(&two_iter
);
1037 avl_iter_next(&two_iter
);
1047 * and_slist_stack() pops the top two slists, overwriting the one with
1048 * the other and pushing it back on the stack.
1050 void and_stree_stack(struct stree_stack
**stack
)
1052 struct sm_state
*tmp
;
1053 struct stree
*right_stree
= pop_stree(stack
);
1055 FOR_EACH_SM(right_stree
, tmp
) {
1056 overwrite_sm_state_stree_stack(stack
, tmp
);
1057 } END_FOR_EACH_SM(tmp
);
1058 free_stree(&right_stree
);
1062 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
1063 * It pops the two slists from the top of the stack and merges them
1064 * together in a way that preserves the things they have in common
1065 * but creates a merged state for most of the rest.
1066 * You could have code that had: if (foo || foo) { foo->baz;
1067 * It's this function which ensures smatch does the right thing.
1069 void or_stree_stack(struct stree_stack
**pre_conds
,
1070 struct stree
*cur_stree
,
1071 struct stree_stack
**stack
)
1075 struct stree
*pre_stree
;
1077 struct stree
*tmp_stree
;
1079 new = pop_stree(stack
);
1080 old
= pop_stree(stack
);
1082 pre_stree
= pop_stree(pre_conds
);
1083 push_stree(pre_conds
, clone_stree(pre_stree
));
1085 res
= clone_stree(pre_stree
);
1086 overwrite_stree(old
, &res
);
1088 tmp_stree
= clone_stree(cur_stree
);
1089 overwrite_stree(new, &tmp_stree
);
1091 merge_stree(&res
, tmp_stree
);
1092 filter_stree(&res
, pre_stree
);
1094 push_stree(stack
, res
);
1095 free_stree(&tmp_stree
);
1096 free_stree(&pre_stree
);
1102 * get_named_stree() is only used for gotos.
1104 struct stree
**get_named_stree(struct named_stree_stack
*stack
,
1108 struct named_stree
*tmp
;
1110 FOR_EACH_PTR(stack
, tmp
) {
1111 if (tmp
->sym
== sym
&&
1112 strcmp(tmp
->name
, name
) == 0)
1114 } END_FOR_EACH_PTR(tmp
);
1118 /* FIXME: These parameters are in a different order from expected */
1119 void overwrite_stree(struct stree
*from
, struct stree
**to
)
1121 struct sm_state
*tmp
;
1123 FOR_EACH_SM(from
, tmp
) {
1124 overwrite_sm_state_stree(to
, tmp
);
1125 } END_FOR_EACH_SM(tmp
);