1 /*
2 * Copyright (C) 2006 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 /*
19 * You have a lists of states. kernel = locked, foo = NULL, ...
20 * When you hit an if {} else {} statement then you swap the list
21 * of states for a different list of states. The lists are stored
22 * on stacks.
23 *
24 * At the beginning of this file there are list of the stacks that
25 * we use. Each function in this file does something to one of
26 * of the stacks.
27 *
28 * So the smatch_flow.c understands code but it doesn't understand states.
29 * smatch_flow calls functions in this file. This file calls functions
30 * in smatch_slist.c which just has boring generic plumbing for handling
31 * state lists. But really it's this file where all the magic happens.
32 */
33
34 #include <stdlib.h>
35 #include <stdio.h>
36 #include "smatch.h"
37 #include "smatch_slist.h"
38 #include "smatch_extra.h"
39
40 struct smatch_state undefined = { .name = "undefined" };
41 struct smatch_state ghost = { .name = "ghost" };
42 struct smatch_state merged = { .name = "merged" };
43 struct smatch_state true_state = { .name = "true" };
44 struct smatch_state false_state = { .name = "false" };
45
46 static struct stree *cur_stree; /* current states */
47 static struct stree *fast_overlay;
48
49 static struct stree_stack *true_stack; /* states after a t/f branch */
50 static struct stree_stack *false_stack;
51 static struct stree_stack *pre_cond_stack; /* states before a t/f branch */
52
53 static struct stree_stack *cond_true_stack; /* states affected by a branch */
54 static struct stree_stack *cond_false_stack;
55
56 static struct stree_stack *fake_cur_stree_stack;
57 static int read_only;
58
59 static struct stree_stack *break_stack;
60 static struct stree_stack *fake_break_stack;
61 static struct stree_stack *switch_stack;
62 static struct range_list_stack *remaining_cases;
63 static struct stree_stack *default_stack;
64 static struct stree_stack *continue_stack;
65
66 static struct named_stree_stack *goto_stack;
67
68 static struct ptr_list *backup;
69
70 int option_debug;
71
72 void __print_cur_stree(void)
73 {
74 __print_stree(cur_stree);
75 }
76
77 bool __print_states(const char *owner)
78 {
79 struct sm_state *sm;
80 bool found = false;
81
82 if (!owner)
83 return false;
84
85 FOR_EACH_SM(__get_cur_stree(), sm) {
86 if (!strstr(check_name(sm->owner), owner))
87 continue;
88 sm_msg("%s", show_sm(sm));
89 found = true;
90 } END_FOR_EACH_SM(sm);
91
92 return found;
93 }
94
95 int unreachable(void)
96 {
97 if (!cur_stree)
98 return 1;
99 return 0;
100 }
101
102 void __set_cur_stree_readonly(void)
103 {
104 read_only++;
105 }
106
107 void __set_cur_stree_writable(void)
108 {
109 read_only--;
110 }
111
112 DECLARE_PTR_LIST(check_tracker_list, check_tracker_hook *);
113 static struct check_tracker_list **tracker_hooks;
114
115 void add_check_tracker(const char *check_name, check_tracker_hook *fn)
116 {
117 check_tracker_hook **p;
118 int owner;
119
120 owner = id_from_name(check_name);
121 if (!owner) {
122 printf("check not found. '%s'\n", check_name);
123 return;
124 }
125
126 p = malloc(sizeof(check_tracker_hook *));
127 *p = fn;
128 add_ptr_list(&tracker_hooks[owner], p);
129 }
130
131 static void call_tracker_hooks(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
132 {
133 struct check_tracker_list *hooks;
134 check_tracker_hook **fn;
135
136 if ((unsigned short)owner == USHRT_MAX)
137 return;
138
139 hooks = tracker_hooks[owner];
140 FOR_EACH_PTR(hooks, fn) {
141 (*fn)(owner, name, sym, state);
142 } END_FOR_EACH_PTR(fn);
143 }
144
145 void allocate_tracker_array(int num_checks)
146 {
147 tracker_hooks = malloc(num_checks * sizeof(void *));
148 memset(tracker_hooks, 0, num_checks * sizeof(void *));
149 }
150
151 struct sm_state *set_state(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
152 {
153 struct sm_state *ret;
154
155 if (!name || !state)
156 return NULL;
157
158 if (read_only)
159 sm_perror("cur_stree is read only.");
160
161 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
162 struct smatch_state *s;
163
164 s = __get_state(owner, name, sym);
165 if (!s)
166 sm_msg("%s new [%s] '%s' %s", __func__,
167 check_name(owner), name, show_state(state));
168 else
169 sm_msg("%s change [%s] '%s' %s => %s",
170 __func__, check_name(owner), name, show_state(s),
171 show_state(state));
172 }
173
174 call_tracker_hooks(owner, name, sym, state);
175
176 if (owner != -1 && unreachable())
177 return NULL;
178
179 if (fake_cur_stree_stack)
180 set_state_stree_stack(&fake_cur_stree_stack, owner, name, sym, state);
181
182 ret = set_state_stree(&cur_stree, owner, name, sym, state);
183
184 return ret;
185 }
186
187 struct sm_state *set_state_expr(int owner, struct expression *expr, struct smatch_state *state)
188 {
189 char *name;
190 struct symbol *sym;
191 struct sm_state *ret = NULL;
192
193 expr = strip_expr(expr);
194 name = expr_to_var_sym(expr, &sym);
195 if (!name || !sym)
196 goto free;
197 ret = set_state(owner, name, sym, state);
198 free:
199 free_string(name);
200 return ret;
201 }
202
203 struct stree *__swap_cur_stree(struct stree *stree)
204 {
205 struct stree *orig = cur_stree;
206
207 cur_stree = stree;
208 return orig;
209 }
210
211 void __push_fake_cur_stree(void)
212 {
213 push_stree(&fake_cur_stree_stack, NULL);
214 __save_pre_cond_states();
215 }
216
217 struct stree *__pop_fake_cur_stree(void)
218 {
219 if (!fake_cur_stree_stack)
220 sm_perror("popping too many fake cur strees.");
221 __use_pre_cond_states();
222 return pop_stree(&fake_cur_stree_stack);
223 }
224
225 void __free_fake_cur_stree(void)
226 {
227 struct stree *stree;
228
229 stree = __pop_fake_cur_stree();
230 free_stree(&stree);
231 }
232
233 void __set_fake_cur_stree_fast(struct stree *stree)
234 {
235 if (fast_overlay) {
236 sm_perror("cannot nest fast overlay");
237 return;
238 }
239 fast_overlay = stree;
240 set_fast_math_only();
241 }
242
243 void __pop_fake_cur_stree_fast(void)
244 {
245 fast_overlay = NULL;
246 clear_fast_math_only();
247 }
248
249 void __merge_stree_into_cur(struct stree *stree)
250 {
251 struct sm_state *sm;
252 struct sm_state *orig;
253 struct sm_state *merged;
254
255 FOR_EACH_SM(stree, sm) {
256 orig = get_sm_state(sm->owner, sm->name, sm->sym);
257 if (orig)
258 merged = merge_sm_states(orig, sm);
259 else
260 merged = sm;
261 __set_sm(merged);
262 } END_FOR_EACH_SM(sm);
263 }
264
265 void __set_sm(struct sm_state *sm)
266 {
267 if (read_only)
268 sm_perror("cur_stree is read only.");
269
270 if (option_debug ||
271 strcmp(check_name(sm->owner), option_debug_check) == 0) {
272 struct smatch_state *s;
273
274 s = __get_state(sm->owner, sm->name, sm->sym);
275 if (!s)
276 sm_msg("%s new %s", __func__, show_sm(sm));
277 else
278 sm_msg("%s change %s (was %s)", __func__, show_sm(sm),
279 show_state(s));
280 }
281
282 if (unreachable())
283 return;
284
285 if (fake_cur_stree_stack)
286 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
287
288 overwrite_sm_state_stree(&cur_stree, sm);
289 }
290
291 void __set_sm_cur_stree(struct sm_state *sm)
292 {
293 if (read_only)
294 sm_perror("cur_stree is read only.");
295
296 if (option_debug ||
297 strcmp(check_name(sm->owner), option_debug_check) == 0) {
298 struct smatch_state *s;
299
300 s = __get_state(sm->owner, sm->name, sm->sym);
301 if (!s)
302 sm_msg("%s new %s", __func__, show_sm(sm));
303 else
304 sm_msg("%s change %s (was %s)",
305 __func__, show_sm(sm), show_state(s));
306 }
307
308 if (unreachable())
309 return;
310
311 overwrite_sm_state_stree(&cur_stree, sm);
312 }
313
314 void __set_sm_fake_stree(struct sm_state *sm)
315 {
316 if (read_only)
317 sm_perror("cur_stree is read only.");
318
319 if (option_debug ||
320 strcmp(check_name(sm->owner), option_debug_check) == 0) {
321 struct smatch_state *s;
322
323 s = __get_state(sm->owner, sm->name, sm->sym);
324 if (!s)
325 sm_msg("%s new %s", __func__, show_sm(sm));
326 else
327 sm_msg("%s change %s (was %s)",
328 __func__, show_sm(sm), show_state(s));
329 }
330
331 if (unreachable())
332 return;
333
334 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
335 }
336
337
338 typedef void (get_state_hook)(int owner, const char *name, struct symbol *sym);
339 DECLARE_PTR_LIST(fn_list, get_state_hook *);
340 static struct fn_list *get_state_hooks;
341
342 void add_get_state_hook(get_state_hook *fn)
343 {
344 get_state_hook **p = malloc(sizeof(get_state_hook *));
345 *p = fn;
346 add_ptr_list(&get_state_hooks, p);
347 }
348
349 static void call_get_state_hooks(int owner, const char *name, struct symbol *sym)
350 {
351 static int recursion;
352 get_state_hook **fn;
353
354 if (recursion)
355 return;
356 recursion = 1;
357
358 FOR_EACH_PTR(get_state_hooks, fn) {
359 (*fn)(owner, name, sym);
360 } END_FOR_EACH_PTR(fn);
361
362 recursion = 0;
363 }
364
365 struct smatch_state *__get_state(int owner, const char *name, struct symbol *sym)
366 {
367 struct sm_state *sm;
368
369 sm = get_sm_state(owner, name, sym);
370 if (!sm)
371 return NULL;
372 return sm->state;
373 }
374
375 struct smatch_state *get_state(int owner, const char *name, struct symbol *sym)
376 {
377 call_get_state_hooks(owner, name, sym);
378
379 return __get_state(owner, name, sym);
380 }
381
382 struct smatch_state *get_state_expr(int owner, struct expression *expr)
383 {
384 char *name;
385 struct symbol *sym;
386 struct smatch_state *ret = NULL;
387
388 expr = strip_expr(expr);
389 name = expr_to_var_sym(expr, &sym);
390 if (!name || !sym)
391 goto free;
392 ret = get_state(owner, name, sym);
393 free:
394 free_string(name);
395 return ret;
396 }
397
398 struct state_list *get_possible_states(int owner, const char *name, struct symbol *sym)
399 {
400 struct sm_state *sms;
401
402 sms = get_sm_state_stree(cur_stree, owner, name, sym);
403 if (sms)
404 return sms->possible;
405 return NULL;
406 }
407
408 struct state_list *get_possible_states_expr(int owner, struct expression *expr)
409 {
410 char *name;
411 struct symbol *sym;
412 struct state_list *ret = NULL;
413
414 expr = strip_expr(expr);
415 name = expr_to_var_sym(expr, &sym);
416 if (!name || !sym)
417 goto free;
418 ret = get_possible_states(owner, name, sym);
419 free:
420 free_string(name);
421 return ret;
422 }
423
424 struct sm_state *get_sm_state(int owner, const char *name, struct symbol *sym)
425 {
426 struct sm_state *ret;
427
428 ret = get_sm_state_stree(fast_overlay, owner, name, sym);
429 if (ret)
430 return ret;
431
432 return get_sm_state_stree(cur_stree, owner, name, sym);
433 }
434
435 struct sm_state *get_sm_state_expr(int owner, struct expression *expr)
436 {
437 char *name;
438 struct symbol *sym;
439 struct sm_state *ret = NULL;
440
441 expr = strip_expr(expr);
442 name = expr_to_var_sym(expr, &sym);
443 if (!name || !sym)
444 goto free;
445 ret = get_sm_state(owner, name, sym);
446 free:
447 free_string(name);
448 return ret;
449 }
450
451 void delete_state(int owner, const char *name, struct symbol *sym)
452 {
453 delete_state_stree(&cur_stree, owner, name, sym);
454 if (cond_true_stack) {
455 delete_state_stree_stack(&pre_cond_stack, owner, name, sym);
456 delete_state_stree_stack(&cond_true_stack, owner, name, sym);
457 delete_state_stree_stack(&cond_false_stack, owner, name, sym);
458 }
459 }
460
461 void delete_state_expr(int owner, struct expression *expr)
462 {
463 char *name;
464 struct symbol *sym;
465
466 expr = strip_expr(expr);
467 name = expr_to_var_sym(expr, &sym);
468 if (!name || !sym)
469 goto free;
470 delete_state(owner, name, sym);
471 free:
472 free_string(name);
473 }
474
475 static void delete_all_states_stree_sym(struct stree **stree, struct symbol *sym)
476 {
477 struct state_list *slist = NULL;
478 struct sm_state *sm;
479
480 FOR_EACH_SM(*stree, sm) {
481 if (sm->sym == sym)
482 add_ptr_list(&slist, sm);
483 } END_FOR_EACH_SM(sm);
484
485 FOR_EACH_PTR(slist, sm) {
486 delete_state_stree(stree, sm->owner, sm->name, sm->sym);
487 } END_FOR_EACH_PTR(sm);
488
489 free_slist(&slist);
490 }
491
492 static void delete_all_states_stree_stack_sym(struct stree_stack **stack, struct symbol *sym)
493 {
494 struct stree *stree;
495
496 if (!*stack)
497 return;
498
499 stree = pop_stree(stack);
500 delete_all_states_stree_sym(&stree, sym);
501 push_stree(stack, stree);
502 }
503
504 void __delete_all_states_sym(struct symbol *sym)
505 {
506 delete_all_states_stree_sym(&cur_stree, sym);
507
508 delete_all_states_stree_stack_sym(&true_stack, sym);
509 delete_all_states_stree_stack_sym(&true_stack, sym);
510 delete_all_states_stree_stack_sym(&false_stack, sym);
511 delete_all_states_stree_stack_sym(&pre_cond_stack, sym);
512 delete_all_states_stree_stack_sym(&cond_true_stack, sym);
513 delete_all_states_stree_stack_sym(&cond_false_stack, sym);
514 delete_all_states_stree_stack_sym(&fake_cur_stree_stack, sym);
515 delete_all_states_stree_stack_sym(&break_stack, sym);
516 delete_all_states_stree_stack_sym(&fake_break_stack, sym);
517 delete_all_states_stree_stack_sym(&switch_stack, sym);
518 delete_all_states_stree_stack_sym(&continue_stack, sym);
519
520 /*
521 * deleting from the goto stack is problematic because we don't know
522 * if the label is in scope and also we need the value for --two-passes.
523 */
524 }
525
526 struct stree *get_all_states_from_stree(int owner, struct stree *source)
527 {
528 struct stree *ret = NULL;
529 struct sm_state *tmp;
530
531 FOR_EACH_SM(source, tmp) {
532 if (tmp->owner == owner)
533 avl_insert(&ret, tmp);
534 } END_FOR_EACH_SM(tmp);
535
536 return ret;
537 }
538
539 struct stree *get_all_states_stree(int owner)
540 {
541 return get_all_states_from_stree(owner, cur_stree);
542 }
543
544 struct stree *__get_cur_stree(void)
545 {
546 return cur_stree;
547 }
548
549 int is_reachable(void)
550 {
551 if (cur_stree)
552 return 1;
553 return 0;
554 }
555
556 void set_true_false_states(int owner, const char *name, struct symbol *sym,
557 struct smatch_state *true_state,
558 struct smatch_state *false_state)
559 {
560 if (read_only)
561 sm_perror("cur_stree is read only.");
562
563 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
564 struct smatch_state *tmp;
565
566 tmp = __get_state(owner, name, sym);
567 sm_msg("%s [%s] '%s'. Was %s. Now T:%s F:%s", __func__,
568 check_name(owner), name, show_state(tmp),
569 show_state(true_state), show_state(false_state));
570 }
571
572 if (unreachable())
573 return;
574
575 if (!cond_false_stack || !cond_true_stack) {
576 sm_perror("missing true/false stacks");
577 return;
578 }
579
580 if (true_state)
581 set_state_stree_stack(&cond_true_stack, owner, name, sym, true_state);
582 if (false_state)
583 set_state_stree_stack(&cond_false_stack, owner, name, sym, false_state);
584 }
585
586 void set_true_false_states_expr(int owner, struct expression *expr,
587 struct smatch_state *true_state,
588 struct smatch_state *false_state)
589 {
590 char *name;
591 struct symbol *sym;
592
593 expr = strip_expr(expr);
594 name = expr_to_var_sym(expr, &sym);
595 if (!name || !sym)
596 goto free;
597 set_true_false_states(owner, name, sym, true_state, false_state);
598 free:
599 free_string(name);
600 }
601
602 void __set_true_false_sm(struct sm_state *true_sm, struct sm_state *false_sm)
603 {
604 int owner;
605 const char *name;
606 struct symbol *sym;
607
608 if (!true_sm && !false_sm)
609 return;
610
611 if (unreachable())
612 return;
613
614 owner = true_sm ? true_sm->owner : false_sm->owner;
615 name = true_sm ? true_sm->name : false_sm->name;
616 sym = true_sm ? true_sm->sym : false_sm->sym;
617 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
618 struct smatch_state *tmp;
619
620 tmp = __get_state(owner, name, sym);
621 sm_msg("%s [%s] '%s'. Was %s. Now T:%s F:%s", __func__,
622 check_name(owner), name, show_state(tmp),
623 show_state(true_sm ? true_sm->state : NULL),
624 show_state(false_sm ? false_sm->state : NULL));
625 }
626
627 if (!cond_false_stack || !cond_true_stack) {
628 sm_perror("missing true/false stacks");
629 return;
630 }
631
632 if (true_sm)
633 overwrite_sm_state_stree_stack(&cond_true_stack, true_sm);
634 if (false_sm)
635 overwrite_sm_state_stree_stack(&cond_false_stack, false_sm);
636 }
637
638 void nullify_path(void)
639 {
640 if (fake_cur_stree_stack) {
641 __free_fake_cur_stree();
642 __push_fake_cur_stree();
643 }
644 free_stree(&cur_stree);
645 }
646
647 void __match_nullify_path_hook(const char *fn, struct expression *expr,
648 void *unused)
649 {
650 nullify_path();
651 }
652
653 /*
654 * At the start of every function we mark the path
655 * as unnull. That way there is always at least one state
656 * in the cur_stree until nullify_path is called. This
657 * is used in merge_slist() for the first null check.
658 */
659 void __unnullify_path(void)
660 {
661 if (!cur_stree)
662 set_state(-1, "unnull_path", NULL, &true_state);
663 }
664
665 int __path_is_null(void)
666 {
667 if (cur_stree)
668 return 0;
669 return 1;
670 }
671
672 static void check_stree_stack_free(struct stree_stack **stack)
673 {
674 if (*stack) {
675 sm_perror("stack not empty");
676 free_stack_and_strees(stack);
677 }
678 }
679
680 void save_all_states(void)
681 {
682 __add_ptr_list(&backup, cur_stree);
683 cur_stree = NULL;
684
685 __add_ptr_list(&backup, true_stack);
686 true_stack = NULL;
687 __add_ptr_list(&backup, false_stack);
688 false_stack = NULL;
689 __add_ptr_list(&backup, pre_cond_stack);
690 pre_cond_stack = NULL;
691
692 __add_ptr_list(&backup, cond_true_stack);
693 cond_true_stack = NULL;
694 __add_ptr_list(&backup, cond_false_stack);
695 cond_false_stack = NULL;
696
697 __add_ptr_list(&backup, fake_cur_stree_stack);
698 fake_cur_stree_stack = NULL;
699
700 __add_ptr_list(&backup, break_stack);
701 break_stack = NULL;
702 __add_ptr_list(&backup, fake_break_stack);
703 fake_break_stack = NULL;
704
705 __add_ptr_list(&backup, switch_stack);
706 switch_stack = NULL;
707 __add_ptr_list(&backup, remaining_cases);
708 remaining_cases = NULL;
709 __add_ptr_list(&backup, default_stack);
710 default_stack = NULL;
711 __add_ptr_list(&backup, continue_stack);
712 continue_stack = NULL;
713
714 __add_ptr_list(&backup, goto_stack);
715 goto_stack = NULL;
716 }
717
718 static void *pop_backup(void)
719 {
720 void *ret;
721
722 ret = last_ptr_list(backup);
723 delete_ptr_list_last(&backup);
724 return ret;
725 }
726
727 void restore_all_states(void)
728 {
729 goto_stack = pop_backup();
730
731 continue_stack = pop_backup();
732 default_stack = pop_backup();
733 remaining_cases = pop_backup();
734 switch_stack = pop_backup();
735 fake_break_stack = pop_backup();
736 break_stack = pop_backup();
737
738 fake_cur_stree_stack = pop_backup();
739
740 cond_false_stack = pop_backup();
741 cond_true_stack = pop_backup();
742
743 pre_cond_stack = pop_backup();
744 false_stack = pop_backup();
745 true_stack = pop_backup();
746
747 cur_stree = pop_backup();
748 }
749
750 void free_goto_stack(void)
751 {
752 struct named_stree *named_stree;
753
754 FOR_EACH_PTR(goto_stack, named_stree) {
755 free_stree(&named_stree->stree);
756 } END_FOR_EACH_PTR(named_stree);
757 __free_ptr_list((struct ptr_list **)&goto_stack);
758 }
759
760 void clear_all_states(void)
761 {
762 nullify_path();
763 check_stree_stack_free(&true_stack);
764 check_stree_stack_free(&false_stack);
765 check_stree_stack_free(&pre_cond_stack);
766 check_stree_stack_free(&cond_true_stack);
767 check_stree_stack_free(&cond_false_stack);
768 check_stree_stack_free(&break_stack);
769 check_stree_stack_free(&fake_break_stack);
770 check_stree_stack_free(&switch_stack);
771 check_stree_stack_free(&continue_stack);
772 check_stree_stack_free(&fake_cur_stree_stack);
773
774 free_goto_stack();
775
776 free_every_single_sm_state();
777 free_tmp_expressions();
778 }
779
780 void __push_cond_stacks(void)
781 {
782 push_stree(&cond_true_stack, NULL);
783 push_stree(&cond_false_stack, NULL);
784 __push_fake_cur_stree();
785 }
786
787 void __fold_in_set_states(void)
788 {
789 struct stree *new_states;
790 struct sm_state *sm;
791
792 new_states = __pop_fake_cur_stree();
793 FOR_EACH_SM(new_states, sm) {
794 __set_sm(sm);
795 __set_true_false_sm(sm, sm);
796 } END_FOR_EACH_SM(sm);
797 free_stree(&new_states);
798 }
799
800 void __free_set_states(void)
801 {
802 struct stree *new_states;
803
804 new_states = __pop_fake_cur_stree();
805 free_stree(&new_states);
806 }
807
808 struct stree *__copy_cond_true_states(void)
809 {
810 struct stree *ret;
811
812 ret = pop_stree(&cond_true_stack);
813 push_stree(&cond_true_stack, clone_stree(ret));
814 return ret;
815 }
816
817 struct stree *__copy_cond_false_states(void)
818 {
819 struct stree *ret;
820
821 ret = pop_stree(&cond_false_stack);
822 push_stree(&cond_false_stack, clone_stree(ret));
823 return ret;
824 }
825
826 struct stree *__pop_cond_true_stack(void)
827 {
828 return pop_stree(&cond_true_stack);
829 }
830
831 struct stree *__pop_cond_false_stack(void)
832 {
833 return pop_stree(&cond_false_stack);
834 }
835
836 /*
837 * This combines the pre cond states with either the true or false states.
838 * For example:
839 * a = kmalloc() ; if (a !! foo(a)
840 * In the pre state a is possibly null. In the true state it is non null.
841 * In the false state it is null. Combine the pre and the false to get
842 * that when we call 'foo', 'a' is null.
843 */
844 static void __use_cond_stack(struct stree_stack **stack)
845 {
846 struct stree *stree;
847
848 free_stree(&cur_stree);
849
850 cur_stree = pop_stree(&pre_cond_stack);
851 push_stree(&pre_cond_stack, clone_stree(cur_stree));
852
853 stree = pop_stree(stack);
854 overwrite_stree(stree, &cur_stree);
855 push_stree(stack, stree);
856 }
857
858 void __use_pre_cond_states(void)
859 {
860 free_stree(&cur_stree);
861 cur_stree = pop_stree(&pre_cond_stack);
862 }
863
864 void __use_cond_true_states(void)
865 {
866 __use_cond_stack(&cond_true_stack);
867 }
868
869 void __use_cond_false_states(void)
870 {
871 __use_cond_stack(&cond_false_stack);
872 }
873
874 void __negate_cond_stacks(void)
875 {
876 struct stree *old_false, *old_true;
877
878 old_false = pop_stree(&cond_false_stack);
879 old_true = pop_stree(&cond_true_stack);
880 push_stree(&cond_false_stack, old_true);
881 push_stree(&cond_true_stack, old_false);
882 }
883
884 void __and_cond_states(void)
885 {
886 and_stree_stack(&cond_true_stack);
887 or_stree_stack(&pre_cond_stack, cur_stree, &cond_false_stack);
888 }
889
890 void __or_cond_states(void)
891 {
892 or_stree_stack(&pre_cond_stack, cur_stree, &cond_true_stack);
893 and_stree_stack(&cond_false_stack);
894 }
895
896 void __save_pre_cond_states(void)
897 {
898 push_stree(&pre_cond_stack, clone_stree(cur_stree));
899 }
900
901 void __discard_pre_cond_states(void)
902 {
903 struct stree *tmp;
904
905 tmp = pop_stree(&pre_cond_stack);
906 free_stree(&tmp);
907 }
908
909 struct stree *__get_true_states(void)
910 {
911 return clone_stree(top_stree(cond_true_stack));
912 }
913
914 struct stree *__get_false_states(void)
915 {
916 return clone_stree(top_stree(cond_false_stack));
917 }
918
919 void __use_cond_states(void)
920 {
921 struct stree *pre, *pre_clone, *true_states, *false_states;
922
923 pre = pop_stree(&pre_cond_stack);
924 pre_clone = clone_stree(pre);
925
926 true_states = pop_stree(&cond_true_stack);
927 overwrite_stree(true_states, &pre);
928 free_stree(&true_states);
929 /* we use the true states right away */
930 free_stree(&cur_stree);
931 cur_stree = pre;
932
933 false_states = pop_stree(&cond_false_stack);
934 overwrite_stree(false_states, &pre_clone);
935 free_stree(&false_states);
936 push_stree(&false_stack, pre_clone);
937 }
938
939 void __push_true_states(void)
940 {
941 push_stree(&true_stack, clone_stree(cur_stree));
942 }
943
944 void __use_false_states(void)
945 {
946 free_stree(&cur_stree);
947 cur_stree = pop_stree(&false_stack);
948 }
949
950 void __discard_false_states(void)
951 {
952 struct stree *stree;
953
954 stree = pop_stree(&false_stack);
955 free_stree(&stree);
956 }
957
958 void __merge_false_states(void)
959 {
960 struct stree *stree;
961
962 stree = pop_stree(&false_stack);
963 merge_stree(&cur_stree, stree);
964 free_stree(&stree);
965 }
966
967 /*
968 * This function probably seemed common sensical when I wrote it but, oh wow,
969 * does it look subtle in retrospect. Say we set a state on one side of the if
970 * else path but not on the other, then what we should record in the fake stree
971 * is the merged state.
972 *
973 * This function relies on the fact that the we always set the cur_stree as well
974 * and we already have the infrastructure to merge things correctly into the
975 * cur_stree.
976 *
977 * So instead of merging fake strees together which is probably a lot of work,
978 * we just use it as a list of set states and look up the actual current values
979 * in the cur_stree.
980 *
981 */
982 static void update_stree_with_merged(struct stree **stree)
983 {
984 struct state_list *slist = NULL;
985 struct sm_state *sm, *new;
986
987 FOR_EACH_SM(*stree, sm) {
988 new = get_sm_state(sm->owner, sm->name, sm->sym);
989 if (!new) /* This can happen if we go out of scope */
990 continue;
991 add_ptr_list(&slist, new);
992 } END_FOR_EACH_SM(sm);
993
994 FOR_EACH_PTR(slist, sm) {
995 overwrite_sm_state_stree(stree, sm);
996 } END_FOR_EACH_PTR(sm);
997
998 free_slist(&slist);
999 }
1000
1001 static void update_fake_stree_with_merged(void)
1002 {
1003 struct stree *stree;
1004
1005 if (!fake_cur_stree_stack)
1006 return;
1007 stree = pop_stree(&fake_cur_stree_stack);
1008 update_stree_with_merged(&stree);
1009 push_stree(&fake_cur_stree_stack, stree);
1010 }
1011
1012 void __merge_true_states(void)
1013 {
1014 struct stree *stree;
1015
1016 stree = pop_stree(&true_stack);
1017 merge_stree(&cur_stree, stree);
1018 update_fake_stree_with_merged();
1019 free_stree(&stree);
1020 }
1021
1022 void __push_continues(void)
1023 {
1024 push_stree(&continue_stack, NULL);
1025 }
1026
1027 void __discard_continues(void)
1028 {
1029 struct stree *stree;
1030
1031 stree = pop_stree(&continue_stack);
1032 free_stree(&stree);
1033 }
1034
1035 void __process_continues(void)
1036 {
1037 struct stree *stree;
1038
1039 stree = pop_stree(&continue_stack);
1040 if (!stree)
1041 stree = clone_stree(cur_stree);
1042 else
1043 merge_stree(&stree, cur_stree);
1044
1045 push_stree(&continue_stack, stree);
1046 }
1047
1048 void __merge_continues(void)
1049 {
1050 struct stree *stree;
1051
1052 stree = pop_stree(&continue_stack);
1053 merge_stree(&cur_stree, stree);
1054 free_stree(&stree);
1055 }
1056
1057 void __push_breaks(void)
1058 {
1059 push_stree(&break_stack, NULL);
1060 if (fake_cur_stree_stack)
1061 push_stree(&fake_break_stack, NULL);
1062 }
1063
1064 void __process_breaks(void)
1065 {
1066 struct stree *stree;
1067
1068 stree = pop_stree(&break_stack);
1069 if (!stree)
1070 stree = clone_stree(cur_stree);
1071 else
1072 merge_stree(&stree, cur_stree);
1073 push_stree(&break_stack, stree);
1074
1075 if (!fake_cur_stree_stack)
1076 return;
1077
1078 stree = pop_stree(&fake_break_stack);
1079 if (!stree)
1080 stree = clone_stree(top_stree(fake_cur_stree_stack));
1081 else
1082 merge_stree(&stree, top_stree(fake_cur_stree_stack));
1083 push_stree(&fake_break_stack, stree);
1084 }
1085
1086 int __has_breaks(void)
1087 {
1088 struct stree *stree;
1089 int ret;
1090
1091 stree = pop_stree(&break_stack);
1092 ret = !!stree;
1093 push_stree(&break_stack, stree);
1094 return ret;
1095 }
1096
1097 void __merge_breaks(void)
1098 {
1099 struct stree *stree;
1100 struct sm_state *sm;
1101
1102 stree = pop_stree(&break_stack);
1103 merge_stree(&cur_stree, stree);
1104 free_stree(&stree);
1105
1106 if (!fake_cur_stree_stack)
1107 return;
1108
1109 stree = pop_stree(&fake_break_stack);
1110 update_stree_with_merged(&stree);
1111 FOR_EACH_SM(stree, sm) {
1112 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
1113 } END_FOR_EACH_SM(sm);
1114 free_stree(&stree);
1115 }
1116
1117 void __use_breaks(void)
1118 {
1119 struct stree *stree;
1120 struct sm_state *sm;
1121
1122 free_stree(&cur_stree);
1123 cur_stree = pop_stree(&break_stack);
1124
1125 if (!fake_cur_stree_stack)
1126 return;
1127 stree = pop_stree(&fake_break_stack);
1128 FOR_EACH_SM(stree, sm) {
1129 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
1130 } END_FOR_EACH_SM(sm);
1131 free_stree(&stree);
1132
1133
1134 }
1135
1136 void __save_switch_states(struct expression *switch_expr)
1137 {
1138 struct range_list *rl;
1139
1140 get_absolute_rl(switch_expr, &rl);
1141
1142 push_rl(&remaining_cases, rl);
1143 push_stree(&switch_stack, clone_stree(cur_stree));
1144 }
1145
1146 int have_remaining_cases(void)
1147 {
1148 return !!top_rl(remaining_cases);
1149 }
1150
1151 void __merge_switches(struct expression *switch_expr, struct range_list *case_rl)
1152 {
1153 struct stree *stree;
1154 struct stree *implied_stree;
1155
1156 stree = pop_stree(&switch_stack);
1157 if (!stree) {
1158 /*
1159 * If the cur_stree was NULL before the start of the switch
1160 * statement then we don't want to unnullify it.
1161 *
1162 */
1163 push_stree(&switch_stack, stree);
1164 return;
1165 }
1166 implied_stree = __implied_case_stree(switch_expr, case_rl, &remaining_cases, &stree);
1167 merge_stree(&cur_stree, implied_stree);
1168 free_stree(&implied_stree);
1169 push_stree(&switch_stack, stree);
1170 }
1171
1172 void __discard_switches(void)
1173 {
1174 struct stree *stree;
1175
1176 pop_rl(&remaining_cases);
1177 stree = pop_stree(&switch_stack);
1178 free_stree(&stree);
1179 }
1180
1181 void __push_default(void)
1182 {
1183 push_stree(&default_stack, NULL);
1184 }
1185
1186 void __set_default(void)
1187 {
1188 set_state_stree_stack(&default_stack, 0, "has_default", NULL, &true_state);
1189 }
1190
1191 int __pop_default(void)
1192 {
1193 struct stree *stree;
1194
1195 stree = pop_stree(&default_stack);
1196 if (stree) {
1197 free_stree(&stree);
1198 return 1;
1199 }
1200 return 0;
1201 }
1202
1203 static struct named_stree *alloc_named_stree(const char *name, struct symbol *sym, struct stree *stree)
1204 {
1205 struct named_stree *named_stree = __alloc_named_stree(0);
1206
1207 named_stree->name = (char *)name;
1208 named_stree->stree = stree;
1209 named_stree->sym = sym;
1210 return named_stree;
1211 }
1212
1213 void __save_gotos(const char *name, struct symbol *sym)
1214 {
1215 struct stree **stree;
1216 struct stree *clone;
1217
1218 stree = get_named_stree(goto_stack, name, sym);
1219 if (stree) {
1220 merge_stree(stree, cur_stree);
1221 return;
1222 } else {
1223 struct named_stree *named_stree;
1224
1225 clone = clone_stree(cur_stree);
1226 named_stree = alloc_named_stree(name, sym, clone);
1227 add_ptr_list(&goto_stack, named_stree);
1228 }
1229 }
1230
1231 void __merge_gotos(const char *name, struct symbol *sym)
1232 {
1233 struct stree **stree;
1234
1235 stree = get_named_stree(goto_stack, name, sym);
1236 if (stree)
1237 merge_stree(&cur_stree, *stree);
1238 }