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