db: rename FILTER_VALUE, LIMITED_VALUE, and ADDED_VALUE
[smatch.git] / smatch_states.c
blob46eb3804d6f162f70458a932fa3646fa0018ce2c
1 /*
2 * Copyright (C) 2006 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
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.
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.
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.
34 #include <stdlib.h>
35 #include <stdio.h>
36 #include "smatch.h"
37 #include "smatch_slist.h"
38 #include "smatch_extra.h"
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" };
46 static struct stree *cur_stree; /* current states */
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 */
52 static struct stree_stack *cond_true_stack; /* states affected by a branch */
53 static struct stree_stack *cond_false_stack;
55 static struct stree_stack *fake_cur_stree_stack;
56 static int read_only;
58 static struct stree_stack *break_stack;
59 static struct stree_stack *switch_stack;
60 static struct range_list_stack *remaining_cases;
61 static struct stree_stack *default_stack;
62 static struct stree_stack *continue_stack;
64 static struct named_stree_stack *goto_stack;
66 static struct ptr_list *backup;
68 int option_debug;
70 void __print_cur_stree(void)
72 __print_stree(cur_stree);
75 int unreachable(void)
77 if (!cur_stree)
78 return 1;
79 return 0;
82 struct sm_state *set_state(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
84 struct sm_state *ret;
86 if (!name)
87 return NULL;
89 if (read_only)
90 sm_msg("Smatch Internal Error: cur_stree is read only.");
92 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
93 struct smatch_state *s;
95 s = get_state(owner, name, sym);
96 if (!s)
97 sm_msg("new state. name='%s' [%s] %s",
98 name, check_name(owner), show_state(state));
99 else
100 sm_msg("state change name='%s' [%s] %s => %s",
101 name, check_name(owner), show_state(s),
102 show_state(state));
105 if (owner != -1 && unreachable())
106 return NULL;
108 if (fake_cur_stree_stack)
109 set_state_stree_stack(&fake_cur_stree_stack, owner, name, sym, state);
111 ret = set_state_stree(&cur_stree, owner, name, sym, state);
113 if (cond_true_stack) {
114 set_state_stree_stack(&cond_true_stack, owner, name, sym, state);
115 set_state_stree_stack(&cond_false_stack, owner, name, sym, state);
117 return ret;
120 struct sm_state *set_state_expr(int owner, struct expression *expr, struct smatch_state *state)
122 char *name;
123 struct symbol *sym;
124 struct sm_state *ret = NULL;
126 expr = strip_expr(expr);
127 name = expr_to_var_sym(expr, &sym);
128 if (!name || !sym)
129 goto free;
130 ret = set_state(owner, name, sym, state);
131 free:
132 free_string(name);
133 return ret;
136 void __swap_cur_stree(struct stree *stree)
138 free_stree(&cur_stree);
139 cur_stree = stree;
142 void __push_fake_cur_stree(void)
144 push_stree(&fake_cur_stree_stack, NULL);
145 __save_pre_cond_states();
148 struct stree *__pop_fake_cur_stree(void)
150 if (!fake_cur_stree_stack)
151 sm_msg("INTERNAL error: popping too many fake cur strees.");
152 __use_pre_cond_states();
153 return pop_stree(&fake_cur_stree_stack);
156 void __free_fake_cur_stree(void)
158 struct stree *stree;
160 stree = __pop_fake_cur_stree();
161 free_stree(&stree);
164 void __set_fake_cur_stree_fast(struct stree *stree)
166 push_stree(&pre_cond_stack, cur_stree);
167 cur_stree = stree;
168 read_only = 1;
171 void __pop_fake_cur_stree_fast(void)
173 cur_stree = pop_stree(&pre_cond_stack);
174 read_only = 0;
177 void __merge_stree_into_cur(struct stree *stree)
179 struct sm_state *sm;
180 struct sm_state *orig;
181 struct sm_state *merged;
183 FOR_EACH_SM(stree, sm) {
184 orig = get_sm_state(sm->owner, sm->name, sm->sym);
185 if (orig)
186 merged = merge_sm_states(orig, sm);
187 else
188 merged = sm;
189 __set_sm(merged);
190 } END_FOR_EACH_SM(sm);
193 void __set_sm(struct sm_state *sm)
195 if (read_only)
196 sm_msg("Smatch Internal Error: cur_stree is read only.");
198 if (option_debug ||
199 strcmp(check_name(sm->owner), option_debug_check) == 0) {
200 struct smatch_state *s;
202 s = get_state(sm->owner, sm->name, sm->sym);
203 if (!s)
204 sm_msg("new state. name='%s' [%s] %s",
205 sm->name, check_name(sm->owner),
206 show_state(sm->state));
207 else
208 sm_msg("state change name='%s' [%s] %s => %s",
209 sm->name, check_name(sm->owner), show_state(s),
210 show_state(sm->state));
213 if (unreachable())
214 return;
216 if (fake_cur_stree_stack)
217 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
219 overwrite_sm_state_stree(&cur_stree, sm);
221 if (cond_true_stack) {
222 overwrite_sm_state_stree_stack(&cond_true_stack, sm);
223 overwrite_sm_state_stree_stack(&cond_false_stack, sm);
227 struct smatch_state *get_state(int owner, const char *name, struct symbol *sym)
229 return get_state_stree(cur_stree, owner, name, sym);
232 struct smatch_state *get_state_expr(int owner, struct expression *expr)
234 char *name;
235 struct symbol *sym;
236 struct smatch_state *ret = NULL;
238 expr = strip_expr(expr);
239 name = expr_to_var_sym(expr, &sym);
240 if (!name || !sym)
241 goto free;
242 ret = get_state(owner, name, sym);
243 free:
244 free_string(name);
245 return ret;
248 struct state_list *get_possible_states(int owner, const char *name, struct symbol *sym)
250 struct sm_state *sms;
252 sms = get_sm_state_stree(cur_stree, owner, name, sym);
253 if (sms)
254 return sms->possible;
255 return NULL;
258 struct state_list *get_possible_states_expr(int owner, struct expression *expr)
260 char *name;
261 struct symbol *sym;
262 struct state_list *ret = NULL;
264 expr = strip_expr(expr);
265 name = expr_to_var_sym(expr, &sym);
266 if (!name || !sym)
267 goto free;
268 ret = get_possible_states(owner, name, sym);
269 free:
270 free_string(name);
271 return ret;
274 struct sm_state *get_sm_state(int owner, const char *name, struct symbol *sym)
276 return get_sm_state_stree(cur_stree, owner, name, sym);
279 struct sm_state *get_sm_state_expr(int owner, struct expression *expr)
281 char *name;
282 struct symbol *sym;
283 struct sm_state *ret = NULL;
285 expr = strip_expr(expr);
286 name = expr_to_var_sym(expr, &sym);
287 if (!name || !sym)
288 goto free;
289 ret = get_sm_state(owner, name, sym);
290 free:
291 free_string(name);
292 return ret;
295 void delete_state(int owner, const char *name, struct symbol *sym)
297 delete_state_stree(&cur_stree, owner, name, sym);
298 if (cond_true_stack) {
299 delete_state_stree_stack(&pre_cond_stack, owner, name, sym);
300 delete_state_stree_stack(&cond_true_stack, owner, name, sym);
301 delete_state_stree_stack(&cond_false_stack, owner, name, sym);
305 void delete_state_expr(int owner, struct expression *expr)
307 char *name;
308 struct symbol *sym;
310 expr = strip_expr(expr);
311 name = expr_to_var_sym(expr, &sym);
312 if (!name || !sym)
313 goto free;
314 delete_state(owner, name, sym);
315 free:
316 free_string(name);
319 struct stree *get_all_states_from_stree(int owner, struct stree *source)
321 struct stree *ret = NULL;
322 struct sm_state *tmp;
324 FOR_EACH_SM(source, tmp) {
325 if (tmp->owner == owner)
326 avl_insert(&ret, tmp);
327 } END_FOR_EACH_SM(tmp);
329 return ret;
332 struct stree *get_all_states_stree(int owner)
334 return get_all_states_from_stree(owner, cur_stree);
337 struct stree *__get_cur_stree(void)
339 return cur_stree;
342 int is_reachable(void)
344 if (cur_stree)
345 return 1;
346 return 0;
349 void set_true_false_states(int owner, const char *name, struct symbol *sym,
350 struct smatch_state *true_state,
351 struct smatch_state *false_state)
353 if (read_only)
354 sm_msg("Smatch Internal Error: cur_stree is read only.");
356 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
357 struct smatch_state *tmp;
359 tmp = get_state(owner, name, sym);
360 sm_msg("set_true_false '%s'. Was %s. Now T:%s F:%s\n",
361 name, show_state(tmp),
362 show_state(true_state), show_state(false_state));
365 if (unreachable())
366 return;
368 if (!cond_false_stack || !cond_true_stack) {
369 printf("Error: missing true/false stacks\n");
370 return;
373 if (true_state) {
374 set_state_stree(&cur_stree, owner, name, sym, true_state);
375 set_state_stree_stack(&cond_true_stack, owner, name, sym, true_state);
377 if (false_state)
378 set_state_stree_stack(&cond_false_stack, owner, name, sym, false_state);
381 void set_true_false_states_expr(int owner, struct expression *expr,
382 struct smatch_state *true_state,
383 struct smatch_state *false_state)
385 char *name;
386 struct symbol *sym;
388 expr = strip_expr(expr);
389 name = expr_to_var_sym(expr, &sym);
390 if (!name || !sym)
391 goto free;
392 set_true_false_states(owner, name, sym, true_state, false_state);
393 free:
394 free_string(name);
397 void __set_true_false_sm(struct sm_state *true_sm, struct sm_state *false_sm)
399 if (unreachable())
400 return;
402 if (!cond_false_stack || !cond_true_stack) {
403 printf("Error: missing true/false stacks\n");
404 return;
407 if (true_sm) {
408 overwrite_sm_state_stree(&cur_stree, true_sm);
409 overwrite_sm_state_stree_stack(&cond_true_stack, true_sm);
411 if (false_sm)
412 overwrite_sm_state_stree_stack(&cond_false_stack, false_sm);
415 void nullify_path(void)
417 free_stree(&cur_stree);
420 void __match_nullify_path_hook(const char *fn, struct expression *expr,
421 void *unused)
423 nullify_path();
427 * At the start of every function we mark the path
428 * as unnull. That way there is always at least one state
429 * in the cur_stree until nullify_path is called. This
430 * is used in merge_slist() for the first null check.
432 void __unnullify_path(void)
434 if (!cur_stree)
435 set_state(-1, "unnull_path", NULL, &true_state);
438 int __path_is_null(void)
440 if (cur_stree)
441 return 0;
442 return 1;
445 static void check_stree_stack_free(struct stree_stack **stack)
447 if (*stack) {
448 sm_msg("smatch internal error: stack not empty");
449 free_stack_and_strees(stack);
453 void save_all_states(void)
455 __add_ptr_list(&backup, cur_stree, 0);
456 cur_stree = NULL;
458 __add_ptr_list(&backup, true_stack, 0);
459 true_stack = NULL;
460 __add_ptr_list(&backup, false_stack, 0);
461 false_stack = NULL;
462 __add_ptr_list(&backup, pre_cond_stack, 0);
463 pre_cond_stack = NULL;
465 __add_ptr_list(&backup, cond_true_stack, 0);
466 cond_true_stack = NULL;
467 __add_ptr_list(&backup, cond_false_stack, 0);
468 cond_false_stack = NULL;
470 __add_ptr_list(&backup, fake_cur_stree_stack, 0);
471 fake_cur_stree_stack = NULL;
473 __add_ptr_list(&backup, break_stack, 0);
474 break_stack = NULL;
475 __add_ptr_list(&backup, switch_stack, 0);
476 switch_stack = NULL;
477 __add_ptr_list(&backup, remaining_cases, 0);
478 remaining_cases = NULL;
479 __add_ptr_list(&backup, default_stack, 0);
480 default_stack = NULL;
481 __add_ptr_list(&backup, continue_stack, 0);
482 continue_stack = NULL;
484 __add_ptr_list(&backup, goto_stack, 0);
485 goto_stack = NULL;
488 static void *pop_backup(void)
490 void *ret;
492 ret = last_ptr_list(backup);
493 delete_ptr_list_last(&backup);
494 return ret;
497 void restore_all_states(void)
499 goto_stack = pop_backup();
501 continue_stack = pop_backup();
502 default_stack = pop_backup();
503 remaining_cases = pop_backup();
504 switch_stack = pop_backup();
505 break_stack = pop_backup();
507 fake_cur_stree_stack = pop_backup();
509 cond_false_stack = pop_backup();
510 cond_true_stack = pop_backup();
512 pre_cond_stack = pop_backup();
513 false_stack = pop_backup();
514 true_stack = pop_backup();
516 cur_stree = pop_backup();
519 void free_goto_stack(void)
521 struct named_stree *named_stree;
523 FOR_EACH_PTR(goto_stack, named_stree) {
524 free_stree(&named_stree->stree);
525 } END_FOR_EACH_PTR(named_stree);
526 __free_ptr_list((struct ptr_list **)&goto_stack);
529 void clear_all_states(void)
531 nullify_path();
532 check_stree_stack_free(&true_stack);
533 check_stree_stack_free(&false_stack);
534 check_stree_stack_free(&pre_cond_stack);
535 check_stree_stack_free(&cond_true_stack);
536 check_stree_stack_free(&cond_false_stack);
537 check_stree_stack_free(&break_stack);
538 check_stree_stack_free(&switch_stack);
539 check_stree_stack_free(&continue_stack);
541 free_goto_stack();
543 free_every_single_sm_state();
546 void __push_cond_stacks(void)
548 push_stree(&cond_true_stack, NULL);
549 push_stree(&cond_false_stack, NULL);
552 struct stree *__copy_cond_true_states(void)
554 struct stree *ret;
556 ret = pop_stree(&cond_true_stack);
557 push_stree(&cond_true_stack, clone_stree(ret));
558 return ret;
561 struct stree *__copy_cond_false_states(void)
563 struct stree *ret;
565 ret = pop_stree(&cond_false_stack);
566 push_stree(&cond_false_stack, clone_stree(ret));
567 return ret;
570 struct stree *__pop_cond_true_stack(void)
572 return pop_stree(&cond_true_stack);
575 struct stree *__pop_cond_false_stack(void)
577 return pop_stree(&cond_false_stack);
581 * This combines the pre cond states with either the true or false states.
582 * For example:
583 * a = kmalloc() ; if (a !! foo(a)
584 * In the pre state a is possibly null. In the true state it is non null.
585 * In the false state it is null. Combine the pre and the false to get
586 * that when we call 'foo', 'a' is null.
588 static void __use_cond_stack(struct stree_stack **stack)
590 struct stree *stree;
592 free_stree(&cur_stree);
594 cur_stree = pop_stree(&pre_cond_stack);
595 push_stree(&pre_cond_stack, clone_stree(cur_stree));
597 stree = pop_stree(stack);
598 overwrite_stree(stree, &cur_stree);
599 push_stree(stack, stree);
602 void __use_pre_cond_states(void)
604 free_stree(&cur_stree);
605 cur_stree = pop_stree(&pre_cond_stack);
608 void __use_cond_true_states(void)
610 __use_cond_stack(&cond_true_stack);
613 void __use_cond_false_states(void)
615 __use_cond_stack(&cond_false_stack);
618 void __negate_cond_stacks(void)
620 struct stree *old_false, *old_true;
622 __use_cond_stack(&cond_false_stack);
623 old_false = pop_stree(&cond_false_stack);
624 old_true = pop_stree(&cond_true_stack);
625 push_stree(&cond_false_stack, old_true);
626 push_stree(&cond_true_stack, old_false);
629 void __and_cond_states(void)
631 and_stree_stack(&cond_true_stack);
632 or_stree_stack(&pre_cond_stack, cur_stree, &cond_false_stack);
635 void __or_cond_states(void)
637 or_stree_stack(&pre_cond_stack, cur_stree, &cond_true_stack);
638 and_stree_stack(&cond_false_stack);
641 void __save_pre_cond_states(void)
643 push_stree(&pre_cond_stack, clone_stree(cur_stree));
646 void __discard_pre_cond_states(void)
648 struct stree *tmp;
650 tmp = pop_stree(&pre_cond_stack);
651 free_stree(&tmp);
654 void __use_cond_states(void)
656 struct stree *pre, *pre_clone, *true_states, *false_states;
658 pre = pop_stree(&pre_cond_stack);
659 pre_clone = clone_stree(pre);
661 true_states = pop_stree(&cond_true_stack);
662 overwrite_stree(true_states, &pre);
663 free_stree(&true_states);
664 /* we use the true states right away */
665 free_stree(&cur_stree);
666 cur_stree = pre;
668 false_states = pop_stree(&cond_false_stack);
669 overwrite_stree(false_states, &pre_clone);
670 free_stree(&false_states);
671 push_stree(&false_stack, pre_clone);
674 void __push_true_states(void)
676 push_stree(&true_stack, clone_stree(cur_stree));
679 void __use_false_states(void)
681 free_stree(&cur_stree);
682 cur_stree = pop_stree(&false_stack);
685 void __discard_false_states(void)
687 struct stree *stree;
689 stree = pop_stree(&false_stack);
690 free_stree(&stree);
693 void __merge_false_states(void)
695 struct stree *stree;
697 stree = pop_stree(&false_stack);
698 merge_stree(&cur_stree, stree);
699 free_stree(&stree);
702 void __merge_true_states(void)
704 struct stree *stree;
706 stree = pop_stree(&true_stack);
707 merge_stree(&cur_stree, stree);
708 free_stree(&stree);
711 void __push_continues(void)
713 push_stree(&continue_stack, NULL);
716 void __discard_continues(void)
718 struct stree *stree;
720 stree = pop_stree(&continue_stack);
721 free_stree(&stree);
724 void __process_continues(void)
726 struct stree *stree;
728 stree = pop_stree(&continue_stack);
729 if (!stree)
730 stree = clone_stree(cur_stree);
731 else
732 merge_stree(&stree, cur_stree);
734 push_stree(&continue_stack, stree);
737 static int top_stree_empty(struct stree_stack **stack)
739 struct stree *tmp;
740 int empty = 0;
742 tmp = pop_stree(stack);
743 if (!tmp)
744 empty = 1;
745 push_stree(stack, tmp);
746 return empty;
749 /* a silly loop does this: while(i--) { return; } */
750 void __warn_on_silly_pre_loops(void)
752 if (!__path_is_null())
753 return;
754 if (!top_stree_empty(&continue_stack))
755 return;
756 if (!top_stree_empty(&break_stack))
757 return;
758 /* if the path was nullified before the loop, then we already
759 printed an error earlier */
760 if (top_stree_empty(&false_stack))
761 return;
762 sm_msg("info: loop could be replaced with if statement.");
765 void __merge_continues(void)
767 struct stree *stree;
769 stree = pop_stree(&continue_stack);
770 merge_stree(&cur_stree, stree);
771 free_stree(&stree);
774 void __push_breaks(void)
776 push_stree(&break_stack, NULL);
779 void __process_breaks(void)
781 struct stree *stree;
783 stree = pop_stree(&break_stack);
784 if (!stree)
785 stree = clone_stree(cur_stree);
786 else
787 merge_stree(&stree, cur_stree);
789 push_stree(&break_stack, stree);
792 int __has_breaks(void)
794 struct stree *stree;
795 int ret;
797 stree = pop_stree(&break_stack);
798 ret = !!stree;
799 push_stree(&break_stack, stree);
800 return ret;
803 void __merge_breaks(void)
805 struct stree *stree;
807 stree = pop_stree(&break_stack);
808 merge_stree(&cur_stree, stree);
809 free_stree(&stree);
812 void __use_breaks(void)
814 free_stree(&cur_stree);
815 cur_stree = pop_stree(&break_stack);
818 void __save_switch_states(struct expression *switch_expr)
820 push_rl(&remaining_cases, __get_implied_values(switch_expr));
821 push_stree(&switch_stack, clone_stree(cur_stree));
824 void __merge_switches(struct expression *switch_expr, struct expression *case_expr)
826 struct stree *stree;
827 struct stree *implied_stree;
829 stree = pop_stree(&switch_stack);
830 implied_stree = __implied_case_stree(switch_expr, case_expr, &remaining_cases, &stree);
831 merge_stree(&cur_stree, implied_stree);
832 free_stree(&implied_stree);
833 push_stree(&switch_stack, stree);
836 void __discard_switches(void)
838 struct stree *stree;
840 pop_rl(&remaining_cases);
841 stree = pop_stree(&switch_stack);
842 free_stree(&stree);
845 void __push_default(void)
847 push_stree(&default_stack, NULL);
850 void __set_default(void)
852 set_state_stree_stack(&default_stack, 0, "has_default", NULL, &true_state);
855 int __pop_default(void)
857 struct stree *stree;
859 stree = pop_stree(&default_stack);
860 if (stree) {
861 free_stree(&stree);
862 return 1;
864 return 0;
867 static struct named_stree *alloc_named_stree(const char *name, struct stree *stree)
869 struct named_stree *named_stree = __alloc_named_stree(0);
871 named_stree->name = (char *)name;
872 named_stree->stree = stree;
873 return named_stree;
876 void __save_gotos(const char *name)
878 struct stree **stree;
879 struct stree *clone;
881 stree = get_named_stree(goto_stack, name);
882 if (stree) {
883 merge_stree(stree, cur_stree);
884 return;
885 } else {
886 struct named_stree *named_stree;
888 clone = clone_stree(cur_stree);
889 named_stree = alloc_named_stree(name, clone);
890 add_ptr_list(&goto_stack, named_stree);
894 void __merge_gotos(const char *name)
896 struct stree **stree;
898 stree = get_named_stree(goto_stack, name);
899 if (stree)
900 merge_stree(&cur_stree, *stree);