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 = '%s'%s",
45 check_name(sm
->owner
), sm
->name
, show_state(sm
->state
),
46 sm
->merged
? " [merged]" : "");
47 if (pos
> sizeof(buf
))
50 if (ptr_list_size((struct ptr_list
*)sm
->possible
) == 1)
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
, ")");
72 for (i
= 0; i
< 3; i
++)
73 buf
[sizeof(buf
) - 2 - i
] = '.';
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 /* NULL states go at the end to simplify merge_slist */
91 int cmp_tracker(const struct sm_state
*a
, const struct sm_state
*b
)
102 if (a
->owner
< b
->owner
)
104 if (a
->owner
> b
->owner
)
107 ret
= strcmp(a
->name
, b
->name
);
113 if (!b
->sym
&& a
->sym
)
115 if (!a
->sym
&& b
->sym
)
126 void allocate_dynamic_states_array(int num_checks
)
128 dynamic_states
= calloc(num_checks
+ 1, sizeof(int));
131 void set_dynamic_states(unsigned short owner
)
133 dynamic_states
[owner
] = true;
136 bool has_dynamic_states(unsigned short owner
)
138 if (owner
>= num_checks
)
140 return dynamic_states
[owner
];
143 static int cmp_possible_sm(const struct sm_state
*a
, const struct sm_state
*b
, int preserve
)
150 if (!has_dynamic_states(a
->owner
)) {
151 if (a
->state
> b
->state
)
153 if (a
->state
< b
->state
)
158 if (a
->owner
== SMATCH_EXTRA
) {
160 * In Smatch extra you can have borrowed implications.
162 * FIXME: review how borrowed implications work and if they
163 * are the best way. See also smatch_implied.c.
166 ret
= cmp_tracker(a
, b
);
171 * We want to preserve leaf states. They're use to split
172 * returns in smatch_db.c.
176 if (a
->merged
&& !b
->merged
)
182 if (!a
->state
->name
|| !b
->state
->name
)
185 return strcmp(a
->state
->name
, b
->state
->name
);
188 struct sm_state
*alloc_sm_state(int owner
, const char *name
,
189 struct symbol
*sym
, struct smatch_state
*state
)
191 struct sm_state
*sm_state
= __alloc_sm_state(0);
195 sm_state
->name
= alloc_sname(name
);
196 sm_state
->owner
= owner
;
198 sm_state
->state
= state
;
199 sm_state
->line
= get_lineno();
200 sm_state
->merged
= 0;
201 sm_state
->pool
= NULL
;
202 sm_state
->left
= NULL
;
203 sm_state
->right
= NULL
;
204 sm_state
->possible
= NULL
;
205 add_ptr_list(&sm_state
->possible
, sm_state
);
209 static struct sm_state
*alloc_state_no_name(int owner
, const char *name
,
211 struct smatch_state
*state
)
213 struct sm_state
*tmp
;
215 tmp
= alloc_sm_state(owner
, NULL
, sym
, state
);
220 int too_many_possible(struct sm_state
*sm
)
222 if (ptr_list_size((struct ptr_list
*)sm
->possible
) >= 100)
227 void add_possible_sm(struct sm_state
*to
, struct sm_state
*new)
229 struct sm_state
*tmp
;
233 if (too_many_possible(to
))
236 FOR_EACH_PTR(to
->possible
, tmp
) {
237 cmp
= cmp_possible_sm(tmp
, new, preserve
);
243 INSERT_CURRENT(new, tmp
);
246 } END_FOR_EACH_PTR(tmp
);
247 add_ptr_list(&to
->possible
, new);
250 static void copy_possibles(struct sm_state
*to
, struct sm_state
*one
, struct sm_state
*two
)
252 struct sm_state
*large
= one
;
253 struct sm_state
*small
= two
;
254 struct sm_state
*tmp
;
257 * We spend a lot of time copying the possible lists. I've tried to
258 * optimize the process a bit.
262 if (ptr_list_size((struct ptr_list
*)two
->possible
) >
263 ptr_list_size((struct ptr_list
*)one
->possible
)) {
268 to
->possible
= clone_slist(large
->possible
);
269 add_possible_sm(to
, to
);
270 FOR_EACH_PTR(small
->possible
, tmp
) {
271 add_possible_sm(to
, tmp
);
272 } END_FOR_EACH_PTR(tmp
);
275 char *alloc_sname(const char *str
)
281 tmp
= __alloc_sname(strlen(str
) + 1);
286 static struct symbol
*oom_func
;
287 static int oom_limit
= 3000000; /* Start with a 3GB limit */
288 int out_of_memory(void)
294 * I decided to use 50M here based on trial and error.
295 * It works out OK for the kernel and so it should work
296 * for most other projects as well.
298 if (sm_state_counter
* sizeof(struct sm_state
) >= 100000000)
302 * We're reading from statm to figure out how much memory we
303 * are using. The problem is that at the end of the function
304 * we release the memory, so that it can be re-used but it
305 * stays in cache, it's not released to the OS. So then if
306 * we allocate memory for different purposes we can easily
307 * hit the 3GB limit on the next function, so that's why I give
308 * the next function an extra 100MB to work with.
311 if (get_mem_kb() > oom_limit
) {
312 oom_func
= cur_func_sym
;
314 sm_perror("OOM: %luKb sm_state_count = %d", get_mem_kb(), sm_state_counter
);
322 int low_on_memory(void)
324 if (sm_state_counter
* sizeof(struct sm_state
) >= 25000000)
329 static void free_sm_state(struct sm_state
*sm
)
331 free_slist(&sm
->possible
);
333 * fixme. Free the actual state.
334 * Right now we leave it until the end of the function
335 * because we don't want to double free it.
336 * Use the freelist to not double free things
340 static void free_all_sm_states(struct allocation_blob
*blob
)
342 unsigned int size
= sizeof(struct sm_state
);
343 unsigned int offset
= 0;
345 while (offset
< blob
->offset
) {
346 free_sm_state((struct sm_state
*)(blob
->data
+ offset
));
351 /* At the end of every function we free all the sm_states */
352 void free_every_single_sm_state(void)
354 struct allocator_struct
*desc
= &sm_state_allocator
;
355 struct allocation_blob
*blob
= desc
->blobs
;
358 desc
->allocations
= 0;
359 desc
->total_bytes
= 0;
360 desc
->useful_bytes
= 0;
361 desc
->freelist
= NULL
;
363 struct allocation_blob
*next
= blob
->next
;
364 free_all_sm_states(blob
);
365 blob_free(blob
, desc
->chunking
);
369 clear_smatch_state_alloc();
371 free_stack_and_strees(&all_pools
);
372 sm_state_counter
= 0;
379 unsigned long get_pool_count(void)
381 return ptr_list_size((struct ptr_list
*)all_pools
);
384 struct sm_state
*clone_sm(struct sm_state
*s
)
386 struct sm_state
*ret
;
388 ret
= alloc_state_no_name(s
->owner
, s
->name
, s
->sym
, s
->state
);
389 ret
->merged
= s
->merged
;
391 /* clone_sm() doesn't copy the pools. Each state needs to have
393 ret
->possible
= clone_slist(s
->possible
);
395 ret
->right
= s
->right
;
399 int is_merged(struct sm_state
*sm
)
404 int is_leaf(struct sm_state
*sm
)
409 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
411 struct sm_state
*tmp
;
413 FOR_EACH_PTR(slist
, tmp
) {
414 if (tmp
->state
== state
)
416 } END_FOR_EACH_PTR(tmp
);
420 struct state_list
*clone_slist(struct state_list
*from_slist
)
423 struct state_list
*to_slist
= NULL
;
425 FOR_EACH_PTR(from_slist
, sm
) {
426 add_ptr_list(&to_slist
, sm
);
427 } END_FOR_EACH_PTR(sm
);
431 static struct smatch_state
*merge_states(int owner
, const char *name
,
433 struct smatch_state
*state1
,
434 struct smatch_state
*state2
)
436 struct smatch_state
*ret
;
438 if (state1
== state2
)
440 else if (__has_merge_function(owner
))
441 ret
= __client_merge_function(owner
, state1
, state2
);
442 else if (state1
== &ghost
)
444 else if (state2
== &ghost
)
446 else if (!state1
|| !state2
)
453 struct sm_state
*merge_sm_states(struct sm_state
*one
, struct sm_state
*two
)
455 struct smatch_state
*s
;
456 struct sm_state
*result
;
459 if (one
->state
->data
&& !has_dynamic_states(one
->owner
))
460 sm_msg("dynamic state: %s", show_sm(one
));
464 if (out_of_memory()) {
466 sm_warning("Function too hairy. No more merges.");
471 s
= merge_states(one
->owner
, one
->name
, one
->sym
, one
->state
, two
->state
);
472 result
= alloc_state_no_name(one
->owner
, one
->name
, one
->sym
, s
);
477 copy_possibles(result
, one
, two
);
480 * The ->line information is used by deref_check where we complain about
481 * checking pointers that have already been dereferenced. Let's say we
482 * dereference a pointer on both the true and false paths and then merge
483 * the states here. The result state is &derefed, but the ->line number
484 * is on the line where the pointer is merged not where it was
487 * So in that case, let's just pick one dereference and set the ->line
492 if (result
->state
== one
->state
)
493 result
->line
= one
->line
;
494 if (result
->state
== two
->state
)
495 result
->line
= two
->line
;
497 if (debug_on(check_name(one
->owner
), one
->name
)) {
498 struct sm_state
*tmp
;
501 printf("%s:%d %s() merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
502 get_filename(), get_lineno(), get_function(),
503 check_name(one
->owner
), one
->name
,
504 show_state(one
->state
), one
->line
,
505 show_state(two
->state
), two
->line
,
508 FOR_EACH_PTR(result
->possible
, tmp
) {
511 printf("%s", show_state(tmp
->state
));
512 } END_FOR_EACH_PTR(tmp
);
519 struct sm_state
*get_sm_state_stree(struct stree
*stree
, int owner
, const char *name
,
522 struct tracker tracker
= {
524 .name
= (char *)name
,
532 return avl_lookup(stree
, (struct sm_state
*)&tracker
);
535 struct smatch_state
*get_state_stree(struct stree
*stree
,
536 int owner
, const char *name
,
541 sm
= get_sm_state_stree(stree
, owner
, name
, sym
);
547 /* FIXME: this is almost exactly the same as set_sm_state_slist() */
548 void overwrite_sm_state_stree(struct stree
**stree
, struct sm_state
*new)
550 avl_insert(stree
, new);
553 void overwrite_sm_state_stree_stack(struct stree_stack
**stack
,
558 stree
= pop_stree(stack
);
559 overwrite_sm_state_stree(&stree
, sm
);
560 push_stree(stack
, stree
);
563 struct sm_state
*set_state_stree(struct stree
**stree
, int owner
, const char *name
,
564 struct symbol
*sym
, struct smatch_state
*state
)
566 struct sm_state
*new = alloc_sm_state(owner
, name
, sym
, state
);
568 avl_insert(stree
, new);
572 void set_state_stree_perm(struct stree
**stree
, int owner
, const char *name
,
573 struct symbol
*sym
, struct smatch_state
*state
)
577 sm
= malloc(sizeof(*sm
) + strlen(name
) + 1);
578 memset(sm
, 0, sizeof(*sm
));
580 sm
->name
= (char *)(sm
+ 1);
581 strcpy((char *)sm
->name
, name
);
585 overwrite_sm_state_stree(stree
, sm
);
588 void delete_state_stree(struct stree
**stree
, int owner
, const char *name
,
591 struct tracker tracker
= {
593 .name
= (char *)name
,
597 avl_remove(stree
, (struct sm_state
*)&tracker
);
600 void delete_state_stree_stack(struct stree_stack
**stack
, int owner
, const char *name
,
605 stree
= pop_stree(stack
);
606 delete_state_stree(&stree
, owner
, name
, sym
);
607 push_stree(stack
, stree
);
610 void push_stree(struct stree_stack
**stack
, struct stree
*stree
)
612 add_ptr_list(stack
, stree
);
615 struct stree
*pop_stree(struct stree_stack
**stack
)
619 stree
= last_ptr_list((struct ptr_list
*)*stack
);
620 delete_ptr_list_last((struct ptr_list
**)stack
);
624 struct stree
*top_stree(struct stree_stack
*stack
)
626 return last_ptr_list((struct ptr_list
*)stack
);
629 void free_slist(struct state_list
**slist
)
631 __free_ptr_list((struct ptr_list
**)slist
);
634 void free_stree_stack(struct stree_stack
**stack
)
636 __free_ptr_list((struct ptr_list
**)stack
);
639 void free_stack_and_strees(struct stree_stack
**stree_stack
)
643 FOR_EACH_PTR(*stree_stack
, stree
) {
645 } END_FOR_EACH_PTR(stree
);
646 free_stree_stack(stree_stack
);
649 struct sm_state
*set_state_stree_stack(struct stree_stack
**stack
, int owner
, const char *name
,
650 struct symbol
*sym
, struct smatch_state
*state
)
655 stree
= pop_stree(stack
);
656 sm
= set_state_stree(&stree
, owner
, name
, sym
, state
);
657 push_stree(stack
, stree
);
663 * get_sm_state_stack() gets the state for the top slist on the stack.
665 struct sm_state
*get_sm_state_stree_stack(struct stree_stack
*stack
,
666 int owner
, const char *name
,
670 struct sm_state
*ret
;
672 stree
= pop_stree(&stack
);
673 ret
= get_sm_state_stree(stree
, owner
, name
, sym
);
674 push_stree(&stack
, stree
);
678 struct smatch_state
*get_state_stree_stack(struct stree_stack
*stack
,
679 int owner
, const char *name
,
684 sm
= get_sm_state_stree_stack(stack
, owner
, name
, sym
);
690 static void match_states_stree(struct stree
**one
, struct stree
**two
)
692 struct smatch_state
*tmp_state
;
694 struct state_list
*add_to_one
= NULL
;
695 struct state_list
*add_to_two
= NULL
;
699 __set_cur_stree_readonly();
701 avl_iter_begin(&one_iter
, *one
, FORWARD
);
702 avl_iter_begin(&two_iter
, *two
, FORWARD
);
705 if (!one_iter
.sm
&& !two_iter
.sm
)
707 if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) < 0) {
708 __set_fake_cur_stree_fast(*two
);
709 __in_unmatched_hook
++;
710 tmp_state
= __client_unmatched_state_function(one_iter
.sm
);
711 __in_unmatched_hook
--;
712 __pop_fake_cur_stree_fast();
713 sm
= alloc_state_no_name(one_iter
.sm
->owner
, one_iter
.sm
->name
,
714 one_iter
.sm
->sym
, tmp_state
);
715 add_ptr_list(&add_to_two
, sm
);
716 avl_iter_next(&one_iter
);
717 } else if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) == 0) {
718 avl_iter_next(&one_iter
);
719 avl_iter_next(&two_iter
);
721 __set_fake_cur_stree_fast(*one
);
722 __in_unmatched_hook
++;
723 tmp_state
= __client_unmatched_state_function(two_iter
.sm
);
724 __in_unmatched_hook
--;
725 __pop_fake_cur_stree_fast();
726 sm
= alloc_state_no_name(two_iter
.sm
->owner
, two_iter
.sm
->name
,
727 two_iter
.sm
->sym
, tmp_state
);
728 add_ptr_list(&add_to_one
, sm
);
729 avl_iter_next(&two_iter
);
733 __set_cur_stree_writable();
735 FOR_EACH_PTR(add_to_one
, sm
) {
737 } END_FOR_EACH_PTR(sm
);
739 FOR_EACH_PTR(add_to_two
, sm
) {
741 } END_FOR_EACH_PTR(sm
);
743 free_slist(&add_to_one
);
744 free_slist(&add_to_two
);
747 static void call_pre_merge_hooks(struct stree
**one
, struct stree
**two
)
749 struct sm_state
*sm
, *cur
;
752 __in_unmatched_hook
++;
754 __set_fake_cur_stree_fast(*one
);
755 __push_fake_cur_stree();
756 FOR_EACH_SM(*two
, sm
) {
757 cur
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
760 call_pre_merge_hook(cur
, sm
);
761 } END_FOR_EACH_SM(sm
);
762 new = __pop_fake_cur_stree();
763 overwrite_stree(new, one
);
765 __pop_fake_cur_stree_fast();
767 __set_fake_cur_stree_fast(*two
);
768 __push_fake_cur_stree();
769 FOR_EACH_SM(*one
, sm
) {
770 cur
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
773 call_pre_merge_hook(cur
, sm
);
774 } END_FOR_EACH_SM(sm
);
775 new = __pop_fake_cur_stree();
776 overwrite_stree(new, two
);
778 __pop_fake_cur_stree_fast();
780 __in_unmatched_hook
--;
783 static void clone_pool_havers_stree(struct stree
**stree
)
785 struct sm_state
*sm
, *tmp
;
786 struct state_list
*slist
= NULL
;
788 FOR_EACH_SM(*stree
, sm
) {
791 add_ptr_list(&slist
, tmp
);
793 } END_FOR_EACH_SM(sm
);
795 FOR_EACH_PTR(slist
, sm
) {
796 avl_insert(stree
, sm
);
797 } END_FOR_EACH_PTR(sm
);
805 * merge_slist() is called whenever paths merge, such as after
806 * an if statement. It takes the two slists and creates one.
808 static void __merge_stree(struct stree
**to
, struct stree
*stree
, int add_pool
)
810 struct stree
*results
= NULL
;
811 struct stree
*implied_one
= NULL
;
812 struct stree
*implied_two
= NULL
;
815 struct sm_state
*one
, *two
, *res
;
820 /* merging a null and nonnull path gives you only the nonnull path */
827 *to
= clone_stree(stree
);
831 implied_one
= clone_stree(*to
);
832 implied_two
= clone_stree(stree
);
834 match_states_stree(&implied_one
, &implied_two
);
835 call_pre_merge_hooks(&implied_one
, &implied_two
);
838 clone_pool_havers_stree(&implied_one
);
839 clone_pool_havers_stree(&implied_two
);
841 set_stree_id(&implied_one
, ++__stree_id
);
842 set_stree_id(&implied_two
, ++__stree_id
);
843 if (implied_one
->base_stree
)
844 set_stree_id(&implied_one
->base_stree
, ++__stree_id
);
845 if (implied_two
->base_stree
)
846 set_stree_id(&implied_two
->base_stree
, ++__stree_id
);
849 push_stree(&all_pools
, implied_one
);
850 push_stree(&all_pools
, implied_two
);
852 avl_iter_begin(&one_iter
, implied_one
, FORWARD
);
853 avl_iter_begin(&two_iter
, implied_two
, FORWARD
);
856 if (!one_iter
.sm
|| !two_iter
.sm
)
863 avl_insert(&results
, one
);
868 one
->pool
= implied_one
;
869 if (implied_one
->base_stree
)
870 one
->pool
= implied_one
->base_stree
;
871 two
->pool
= implied_two
;
872 if (implied_two
->base_stree
)
873 two
->pool
= implied_two
->base_stree
;
875 res
= merge_sm_states(one
, two
);
876 add_possible_sm(res
, one
);
877 add_possible_sm(res
, two
);
878 avl_insert(&results
, res
);
880 avl_iter_next(&one_iter
);
881 avl_iter_next(&two_iter
);
888 void merge_stree(struct stree
**to
, struct stree
*stree
)
890 __merge_stree(to
, stree
, 1);
893 void merge_stree_no_pools(struct stree
**to
, struct stree
*stree
)
895 __merge_stree(to
, stree
, 0);
899 * This is unfortunately a bit subtle... The problem is that if a
900 * state is set on one fake stree but not the other then we should
901 * look up the the original state and use that as the unset state.
902 * Fortunately, after you pop your fake stree then the cur_slist should
903 * reflect the original state.
905 void merge_fake_stree(struct stree
**to
, struct stree
*stree
)
907 struct stree
*one
= *to
;
908 struct stree
*two
= stree
;
910 struct state_list
*add_to_one
= NULL
;
911 struct state_list
*add_to_two
= NULL
;
920 *to
= clone_stree(stree
);
924 avl_iter_begin(&one_iter
, one
, FORWARD
);
925 avl_iter_begin(&two_iter
, two
, FORWARD
);
928 if (!one_iter
.sm
&& !two_iter
.sm
)
930 if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) < 0) {
931 sm
= get_sm_state(one_iter
.sm
->owner
, one_iter
.sm
->name
,
934 add_ptr_list(&add_to_two
, sm
);
935 avl_iter_next(&one_iter
);
936 } else if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) == 0) {
937 avl_iter_next(&one_iter
);
938 avl_iter_next(&two_iter
);
940 sm
= get_sm_state(two_iter
.sm
->owner
, two_iter
.sm
->name
,
943 add_ptr_list(&add_to_one
, sm
);
944 avl_iter_next(&two_iter
);
948 FOR_EACH_PTR(add_to_one
, sm
) {
949 avl_insert(&one
, sm
);
950 } END_FOR_EACH_PTR(sm
);
952 FOR_EACH_PTR(add_to_two
, sm
) {
953 avl_insert(&two
, sm
);
954 } END_FOR_EACH_PTR(sm
);
956 one
->base_stree
= clone_stree(__get_cur_stree());
957 FOR_EACH_SM(one
, sm
) {
958 avl_insert(&one
->base_stree
, sm
);
959 } END_FOR_EACH_SM(sm
);
961 two
->base_stree
= clone_stree(__get_cur_stree());
962 FOR_EACH_SM(two
, sm
) {
963 avl_insert(&two
->base_stree
, sm
);
964 } END_FOR_EACH_SM(sm
);
966 free_slist(&add_to_one
);
967 free_slist(&add_to_two
);
969 __merge_stree(&one
, two
, 1);
975 * filter_slist() removes any sm states "slist" holds in common with "filter"
977 void filter_stree(struct stree
**stree
, struct stree
*filter
)
979 struct stree
*results
= NULL
;
983 avl_iter_begin(&one_iter
, *stree
, FORWARD
);
984 avl_iter_begin(&two_iter
, filter
, FORWARD
);
986 /* FIXME: This should probably be re-written with trees in mind */
989 if (!one_iter
.sm
&& !two_iter
.sm
)
991 if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) < 0) {
992 avl_insert(&results
, one_iter
.sm
);
993 avl_iter_next(&one_iter
);
994 } else if (cmp_tracker(one_iter
.sm
, two_iter
.sm
) == 0) {
995 if (one_iter
.sm
!= two_iter
.sm
)
996 avl_insert(&results
, one_iter
.sm
);
997 avl_iter_next(&one_iter
);
998 avl_iter_next(&two_iter
);
1000 avl_iter_next(&two_iter
);
1010 * and_slist_stack() pops the top two slists, overwriting the one with
1011 * the other and pushing it back on the stack.
1013 void and_stree_stack(struct stree_stack
**stack
)
1015 struct sm_state
*tmp
;
1016 struct stree
*right_stree
= pop_stree(stack
);
1018 FOR_EACH_SM(right_stree
, tmp
) {
1019 overwrite_sm_state_stree_stack(stack
, tmp
);
1020 } END_FOR_EACH_SM(tmp
);
1021 free_stree(&right_stree
);
1025 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
1026 * It pops the two slists from the top of the stack and merges them
1027 * together in a way that preserves the things they have in common
1028 * but creates a merged state for most of the rest.
1029 * You could have code that had: if (foo || foo) { foo->baz;
1030 * It's this function which ensures smatch does the right thing.
1032 void or_stree_stack(struct stree_stack
**pre_conds
,
1033 struct stree
*cur_stree
,
1034 struct stree_stack
**stack
)
1038 struct stree
*pre_stree
;
1040 struct stree
*tmp_stree
;
1042 new = pop_stree(stack
);
1043 old
= pop_stree(stack
);
1045 pre_stree
= pop_stree(pre_conds
);
1046 push_stree(pre_conds
, clone_stree(pre_stree
));
1048 res
= clone_stree(pre_stree
);
1049 overwrite_stree(old
, &res
);
1051 tmp_stree
= clone_stree(cur_stree
);
1052 overwrite_stree(new, &tmp_stree
);
1054 merge_stree(&res
, tmp_stree
);
1055 filter_stree(&res
, pre_stree
);
1057 push_stree(stack
, res
);
1058 free_stree(&tmp_stree
);
1059 free_stree(&pre_stree
);
1065 * get_named_stree() is only used for gotos.
1067 struct stree
**get_named_stree(struct named_stree_stack
*stack
,
1071 struct named_stree
*tmp
;
1073 FOR_EACH_PTR(stack
, tmp
) {
1074 if (tmp
->sym
== sym
&&
1075 strcmp(tmp
->name
, name
) == 0)
1077 } END_FOR_EACH_PTR(tmp
);
1081 /* FIXME: These parameters are in a different order from expected */
1082 void overwrite_stree(struct stree
*from
, struct stree
**to
)
1084 struct sm_state
*tmp
;
1086 FOR_EACH_SM(from
, tmp
) {
1087 overwrite_sm_state_stree(to
, tmp
);
1088 } END_FOR_EACH_SM(tmp
);