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