unreachable: silence "not actually initialized" false positives
[smatch.git] / smatch_states.c
blob4494ddc1d4ed2e38cba71a26674175342bf64932
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 merged = { .name = "merged" };
42 struct smatch_state true_state = { .name = "true" };
43 struct smatch_state false_state = { .name = "false" };
45 static struct stree *cur_stree; /* current states */
47 static struct stree_stack *true_stack; /* states after a t/f branch */
48 static struct stree_stack *false_stack;
49 static struct stree_stack *pre_cond_stack; /* states before a t/f branch */
51 static struct stree_stack *cond_true_stack; /* states affected by a branch */
52 static struct stree_stack *cond_false_stack;
54 static struct stree_stack *fake_cur_stree_stack;
55 static int read_only;
57 static struct stree_stack *break_stack;
58 static struct stree_stack *switch_stack;
59 static struct range_list_stack *remaining_cases;
60 static struct stree_stack *default_stack;
61 static struct stree_stack *continue_stack;
63 static struct named_stree_stack *goto_stack;
65 static struct ptr_list *backup;
67 int option_debug;
69 void __print_cur_stree(void)
71 __print_stree(cur_stree);
74 int unreachable(void)
76 if (!cur_stree)
77 return 1;
78 return 0;
81 struct sm_state *set_state(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
83 struct sm_state *ret;
85 if (!name)
86 return NULL;
88 if (read_only)
89 sm_msg("Smatch Internal Error: cur_stree is read only.");
91 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
92 struct smatch_state *s;
94 s = get_state(owner, name, sym);
95 if (!s)
96 printf("%d new state. name='%s' [%s] %s\n",
97 get_lineno(), name, check_name(owner), show_state(state));
98 else
99 printf("%d state change name='%s' [%s] %s => %s\n",
100 get_lineno(), name, check_name(owner), show_state(s),
101 show_state(state));
104 if (owner != -1 && unreachable())
105 return NULL;
107 if (fake_cur_stree_stack)
108 set_state_stree_stack(&fake_cur_stree_stack, owner, name, sym, state);
110 ret = set_state_stree(&cur_stree, owner, name, sym, state);
112 if (cond_true_stack) {
113 set_state_stree_stack(&cond_true_stack, owner, name, sym, state);
114 set_state_stree_stack(&cond_false_stack, owner, name, sym, state);
116 return ret;
119 struct sm_state *set_state_expr(int owner, struct expression *expr, struct smatch_state *state)
121 char *name;
122 struct symbol *sym;
123 struct sm_state *ret = NULL;
125 expr = strip_expr(expr);
126 name = expr_to_var_sym(expr, &sym);
127 if (!name || !sym)
128 goto free;
129 ret = set_state(owner, name, sym, state);
130 free:
131 free_string(name);
132 return ret;
135 void __push_fake_cur_stree()
137 push_stree(&fake_cur_stree_stack, NULL);
138 __save_pre_cond_states();
141 struct stree *__pop_fake_cur_stree()
143 __use_pre_cond_states();
144 return pop_stree(&fake_cur_stree_stack);
147 void __free_fake_cur_stree()
149 struct stree *stree;
151 __use_pre_cond_states();
152 stree = pop_stree(&fake_cur_stree_stack);
153 free_stree(&stree);
156 void __set_fake_cur_stree_fast(struct stree *stree)
158 push_stree(&pre_cond_stack, cur_stree);
159 cur_stree = stree;
160 read_only = 1;
163 void __pop_fake_cur_stree_fast()
165 cur_stree = pop_stree(&pre_cond_stack);
166 read_only = 0;
169 void __merge_stree_into_cur(struct stree *stree)
171 struct sm_state *sm;
172 struct sm_state *orig;
173 struct sm_state *merged;
175 FOR_EACH_SM(stree, sm) {
176 orig = get_sm_state(sm->owner, sm->name, sm->sym);
177 if (orig)
178 merged = merge_sm_states(orig, sm);
179 else
180 merged = sm;
181 __set_sm(merged);
182 } END_FOR_EACH_SM(sm);
185 void __set_sm(struct sm_state *sm)
187 if (read_only)
188 sm_msg("Smatch Internal Error: cur_stree is read only.");
190 if (option_debug ||
191 strcmp(check_name(sm->owner), option_debug_check) == 0) {
192 struct smatch_state *s;
194 s = get_state(sm->owner, sm->name, sm->sym);
195 if (!s)
196 printf("%d new state. name='%s' [%s] %s\n",
197 get_lineno(), sm->name, check_name(sm->owner),
198 show_state(sm->state));
199 else
200 printf("%d state change name='%s' [%s] %s => %s\n",
201 get_lineno(), sm->name, check_name(sm->owner), show_state(s),
202 show_state(sm->state));
205 if (unreachable())
206 return;
208 if (fake_cur_stree_stack)
209 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
211 overwrite_sm_state_stree(&cur_stree, sm);
213 if (cond_true_stack) {
214 overwrite_sm_state_stree_stack(&cond_true_stack, sm);
215 overwrite_sm_state_stree_stack(&cond_false_stack, sm);
219 struct smatch_state *get_state(int owner, const char *name, struct symbol *sym)
221 return get_state_stree(cur_stree, owner, name, sym);
224 struct smatch_state *get_state_expr(int owner, struct expression *expr)
226 char *name;
227 struct symbol *sym;
228 struct smatch_state *ret = NULL;
230 expr = strip_expr(expr);
231 name = expr_to_var_sym(expr, &sym);
232 if (!name || !sym)
233 goto free;
234 ret = get_state(owner, name, sym);
235 free:
236 free_string(name);
237 return ret;
240 struct state_list *get_possible_states(int owner, const char *name, struct symbol *sym)
242 struct sm_state *sms;
244 sms = get_sm_state_stree(cur_stree, owner, name, sym);
245 if (sms)
246 return sms->possible;
247 return NULL;
250 struct state_list *get_possible_states_expr(int owner, struct expression *expr)
252 char *name;
253 struct symbol *sym;
254 struct state_list *ret = NULL;
256 expr = strip_expr(expr);
257 name = expr_to_var_sym(expr, &sym);
258 if (!name || !sym)
259 goto free;
260 ret = get_possible_states(owner, name, sym);
261 free:
262 free_string(name);
263 return ret;
266 struct sm_state *get_sm_state(int owner, const char *name, struct symbol *sym)
268 return get_sm_state_stree(cur_stree, owner, name, sym);
271 struct sm_state *get_sm_state_expr(int owner, struct expression *expr)
273 char *name;
274 struct symbol *sym;
275 struct sm_state *ret = NULL;
277 expr = strip_expr(expr);
278 name = expr_to_var_sym(expr, &sym);
279 if (!name || !sym)
280 goto free;
281 ret = get_sm_state(owner, name, sym);
282 free:
283 free_string(name);
284 return ret;
287 void delete_state(int owner, const char *name, struct symbol *sym)
289 delete_state_stree(&cur_stree, owner, name, sym);
290 if (cond_true_stack) {
291 delete_state_stree_stack(&pre_cond_stack, owner, name, sym);
292 delete_state_stree_stack(&cond_true_stack, owner, name, sym);
293 delete_state_stree_stack(&cond_false_stack, owner, name, sym);
297 void delete_state_expr(int owner, struct expression *expr)
299 char *name;
300 struct symbol *sym;
302 expr = strip_expr(expr);
303 name = expr_to_var_sym(expr, &sym);
304 if (!name || !sym)
305 goto free;
306 delete_state(owner, name, sym);
307 free:
308 free_string(name);
311 struct stree *get_all_states_from_stree(int owner, struct stree *source)
313 struct stree *ret = NULL;
314 struct sm_state *tmp;
316 FOR_EACH_SM(source, tmp) {
317 if (tmp->owner == owner)
318 avl_insert(&ret, tmp);
319 } END_FOR_EACH_SM(tmp);
321 return ret;
324 struct stree *get_all_states_stree(int owner)
326 return get_all_states_from_stree(owner, cur_stree);
329 struct stree *__get_cur_stree(void)
331 return cur_stree;
334 int is_reachable(void)
336 if (cur_stree)
337 return 1;
338 return 0;
341 void set_true_false_states(int owner, const char *name, struct symbol *sym,
342 struct smatch_state *true_state,
343 struct smatch_state *false_state)
345 if (read_only)
346 sm_msg("Smatch Internal Error: cur_stree is read only.");
348 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
349 struct smatch_state *tmp;
351 tmp = get_state(owner, name, sym);
352 printf("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
353 get_lineno(), name, show_state(tmp),
354 show_state(true_state), show_state(false_state));
357 if (unreachable())
358 return;
360 if (!cond_false_stack || !cond_true_stack) {
361 printf("Error: missing true/false stacks\n");
362 return;
365 if (true_state) {
366 set_state_stree(&cur_stree, owner, name, sym, true_state);
367 set_state_stree_stack(&cond_true_stack, owner, name, sym, true_state);
369 if (false_state)
370 set_state_stree_stack(&cond_false_stack, owner, name, sym, false_state);
373 void set_true_false_states_expr(int owner, struct expression *expr,
374 struct smatch_state *true_state,
375 struct smatch_state *false_state)
377 char *name;
378 struct symbol *sym;
380 expr = strip_expr(expr);
381 name = expr_to_var_sym(expr, &sym);
382 if (!name || !sym)
383 goto free;
384 set_true_false_states(owner, name, sym, true_state, false_state);
385 free:
386 free_string(name);
389 void __set_true_false_sm(struct sm_state *true_sm, struct sm_state *false_sm)
391 if (unreachable())
392 return;
394 if (!cond_false_stack || !cond_true_stack) {
395 printf("Error: missing true/false stacks\n");
396 return;
399 if (true_sm) {
400 overwrite_sm_state_stree(&cur_stree, true_sm);
401 overwrite_sm_state_stree_stack(&cond_true_stack, true_sm);
403 if (false_sm)
404 overwrite_sm_state_stree_stack(&cond_false_stack, false_sm);
407 void nullify_path(void)
409 free_stree(&cur_stree);
412 void __match_nullify_path_hook(const char *fn, struct expression *expr,
413 void *unused)
415 nullify_path();
419 * At the start of every function we mark the path
420 * as unnull. That way there is always at least one state
421 * in the cur_stree until nullify_path is called. This
422 * is used in merge_slist() for the first null check.
424 void __unnullify_path(void)
426 if (!cur_stree)
427 set_state(-1, "unnull_path", NULL, &true_state);
430 int __path_is_null(void)
432 if (cur_stree)
433 return 0;
434 return 1;
437 static void check_stree_stack_free(struct stree_stack **stack)
439 if (*stack) {
440 sm_msg("smatch internal error: stack not empty");
441 free_stack_and_strees(stack);
445 void save_all_states(void)
447 __add_ptr_list(&backup, cur_stree, 0);
448 cur_stree = NULL;
450 __add_ptr_list(&backup, true_stack, 0);
451 true_stack = NULL;
452 __add_ptr_list(&backup, false_stack, 0);
453 false_stack = NULL;
454 __add_ptr_list(&backup, pre_cond_stack, 0);
455 pre_cond_stack = NULL;
457 __add_ptr_list(&backup, cond_true_stack, 0);
458 cond_true_stack = NULL;
459 __add_ptr_list(&backup, cond_false_stack, 0);
460 cond_false_stack = NULL;
462 __add_ptr_list(&backup, fake_cur_stree_stack, 0);
463 fake_cur_stree_stack = NULL;
465 __add_ptr_list(&backup, break_stack, 0);
466 break_stack = NULL;
467 __add_ptr_list(&backup, switch_stack, 0);
468 switch_stack = NULL;
469 __add_ptr_list(&backup, remaining_cases, 0);
470 remaining_cases = NULL;
471 __add_ptr_list(&backup, default_stack, 0);
472 default_stack = NULL;
473 __add_ptr_list(&backup, continue_stack, 0);
474 continue_stack = NULL;
476 __add_ptr_list(&backup, goto_stack, 0);
477 goto_stack = NULL;
480 static void *pop_backup(void)
482 void *ret;
484 ret = last_ptr_list(backup);
485 delete_ptr_list_last(&backup);
486 return ret;
489 void restore_all_states(void)
491 goto_stack = pop_backup();
493 continue_stack = pop_backup();
494 default_stack = pop_backup();
495 remaining_cases = pop_backup();
496 switch_stack = pop_backup();
497 break_stack = pop_backup();
499 fake_cur_stree_stack = pop_backup();
501 cond_false_stack = pop_backup();
502 cond_true_stack = pop_backup();
504 pre_cond_stack = pop_backup();
505 false_stack = pop_backup();
506 true_stack = pop_backup();
508 cur_stree = pop_backup();
511 void free_goto_stack(void)
513 struct named_stree *named_stree;
515 FOR_EACH_PTR(goto_stack, named_stree) {
516 free_stree(&named_stree->stree);
517 } END_FOR_EACH_PTR(named_stree);
518 __free_ptr_list((struct ptr_list **)&goto_stack);
521 void clear_all_states(void)
523 nullify_path();
524 check_stree_stack_free(&true_stack);
525 check_stree_stack_free(&false_stack);
526 check_stree_stack_free(&pre_cond_stack);
527 check_stree_stack_free(&cond_true_stack);
528 check_stree_stack_free(&cond_false_stack);
529 check_stree_stack_free(&break_stack);
530 check_stree_stack_free(&switch_stack);
531 check_stree_stack_free(&continue_stack);
533 free_goto_stack();
535 free_every_single_sm_state();
538 void __push_cond_stacks(void)
540 push_stree(&cond_true_stack, NULL);
541 push_stree(&cond_false_stack, NULL);
544 struct stree *__copy_cond_true_states(void)
546 struct stree *ret;
548 ret = pop_stree(&cond_true_stack);
549 push_stree(&cond_true_stack, clone_stree(ret));
550 return ret;
553 struct stree *__copy_cond_false_states(void)
555 struct stree *ret;
557 ret = pop_stree(&cond_false_stack);
558 push_stree(&cond_false_stack, clone_stree(ret));
559 return ret;
562 struct stree *__pop_cond_true_stack(void)
564 return pop_stree(&cond_true_stack);
567 struct stree *__pop_cond_false_stack(void)
569 return pop_stree(&cond_false_stack);
573 * This combines the pre cond states with either the true or false states.
574 * For example:
575 * a = kmalloc() ; if (a !! foo(a)
576 * In the pre state a is possibly null. In the true state it is non null.
577 * In the false state it is null. Combine the pre and the false to get
578 * that when we call 'foo', 'a' is null.
580 static void __use_cond_stack(struct stree_stack **stack)
582 struct stree *stree;
584 free_stree(&cur_stree);
586 cur_stree = pop_stree(&pre_cond_stack);
587 push_stree(&pre_cond_stack, clone_stree(cur_stree));
589 stree = pop_stree(stack);
590 overwrite_stree(stree, &cur_stree);
591 push_stree(stack, stree);
594 void __use_pre_cond_states(void)
596 free_stree(&cur_stree);
597 cur_stree = pop_stree(&pre_cond_stack);
600 void __use_cond_true_states(void)
602 __use_cond_stack(&cond_true_stack);
605 void __use_cond_false_states(void)
607 __use_cond_stack(&cond_false_stack);
610 void __negate_cond_stacks(void)
612 struct stree *old_false, *old_true;
614 __use_cond_stack(&cond_false_stack);
615 old_false = pop_stree(&cond_false_stack);
616 old_true = pop_stree(&cond_true_stack);
617 push_stree(&cond_false_stack, old_true);
618 push_stree(&cond_true_stack, old_false);
621 void __and_cond_states(void)
623 and_stree_stack(&cond_true_stack);
624 or_stree_stack(&pre_cond_stack, cur_stree, &cond_false_stack);
627 void __or_cond_states(void)
629 or_stree_stack(&pre_cond_stack, cur_stree, &cond_true_stack);
630 and_stree_stack(&cond_false_stack);
633 void __save_pre_cond_states(void)
635 push_stree(&pre_cond_stack, clone_stree(cur_stree));
638 void __discard_pre_cond_states(void)
640 struct stree *tmp;
642 tmp = pop_stree(&pre_cond_stack);
643 free_stree(&tmp);
646 void __use_cond_states(void)
648 struct stree *pre, *pre_clone, *true_states, *false_states;
650 pre = pop_stree(&pre_cond_stack);
651 pre_clone = clone_stree(pre);
653 true_states = pop_stree(&cond_true_stack);
654 overwrite_stree(true_states, &pre);
655 free_stree(&true_states);
656 /* we use the true states right away */
657 free_stree(&cur_stree);
658 cur_stree = pre;
660 false_states = pop_stree(&cond_false_stack);
661 overwrite_stree(false_states, &pre_clone);
662 free_stree(&false_states);
663 push_stree(&false_stack, pre_clone);
666 void __push_true_states(void)
668 push_stree(&true_stack, clone_stree(cur_stree));
671 void __use_false_states(void)
673 free_stree(&cur_stree);
674 cur_stree = pop_stree(&false_stack);
677 void __discard_false_states(void)
679 struct stree *stree;
681 stree = pop_stree(&false_stack);
682 free_stree(&stree);
685 void __merge_false_states(void)
687 struct stree *stree;
689 stree = pop_stree(&false_stack);
690 merge_stree(&cur_stree, stree);
691 free_stree(&stree);
694 void __merge_true_states(void)
696 struct stree *stree;
698 stree = pop_stree(&true_stack);
699 merge_stree(&cur_stree, stree);
700 free_stree(&stree);
703 void __push_continues(void)
705 push_stree(&continue_stack, NULL);
708 void __discard_continues(void)
710 struct stree *stree;
712 stree = pop_stree(&continue_stack);
713 free_stree(&stree);
716 void __process_continues(void)
718 struct stree *stree;
720 stree = pop_stree(&continue_stack);
721 if (!stree)
722 stree = clone_stree(cur_stree);
723 else
724 merge_stree(&stree, cur_stree);
726 push_stree(&continue_stack, stree);
729 static int top_stree_empty(struct stree_stack **stack)
731 struct stree *tmp;
732 int empty = 0;
734 tmp = pop_stree(stack);
735 if (!tmp)
736 empty = 1;
737 push_stree(stack, tmp);
738 return empty;
741 /* a silly loop does this: while(i--) { return; } */
742 void __warn_on_silly_pre_loops(void)
744 if (!__path_is_null())
745 return;
746 if (!top_stree_empty(&continue_stack))
747 return;
748 if (!top_stree_empty(&break_stack))
749 return;
750 /* if the path was nullified before the loop, then we already
751 printed an error earlier */
752 if (top_stree_empty(&false_stack))
753 return;
754 sm_msg("info: loop could be replaced with if statement.");
757 void __merge_continues(void)
759 struct stree *stree;
761 stree = pop_stree(&continue_stack);
762 merge_stree(&cur_stree, stree);
763 free_stree(&stree);
766 void __push_breaks(void)
768 push_stree(&break_stack, NULL);
771 void __process_breaks(void)
773 struct stree *stree;
775 stree = pop_stree(&break_stack);
776 if (!stree)
777 stree = clone_stree(cur_stree);
778 else
779 merge_stree(&stree, cur_stree);
781 push_stree(&break_stack, stree);
784 int __has_breaks(void)
786 struct stree *stree;
787 int ret;
789 stree = pop_stree(&break_stack);
790 ret = !!stree;
791 push_stree(&break_stack, stree);
792 return ret;
795 void __merge_breaks(void)
797 struct stree *stree;
799 stree = pop_stree(&break_stack);
800 merge_stree(&cur_stree, stree);
801 free_stree(&stree);
804 void __use_breaks(void)
806 free_stree(&cur_stree);
807 cur_stree = pop_stree(&break_stack);
810 void __save_switch_states(struct expression *switch_expr)
812 push_rl(&remaining_cases, __get_implied_values(switch_expr));
813 push_stree(&switch_stack, clone_stree(cur_stree));
816 void __merge_switches(struct expression *switch_expr, struct expression *case_expr)
818 struct stree *stree;
819 struct stree *implied_stree;
821 stree = pop_stree(&switch_stack);
822 implied_stree = __implied_case_stree(switch_expr, case_expr, &remaining_cases, &stree);
823 merge_stree(&cur_stree, implied_stree);
824 free_stree(&implied_stree);
825 push_stree(&switch_stack, stree);
828 void __discard_switches(void)
830 struct stree *stree;
832 pop_rl(&remaining_cases);
833 stree = pop_stree(&switch_stack);
834 free_stree(&stree);
837 void __push_default(void)
839 push_stree(&default_stack, NULL);
842 void __set_default(void)
844 set_state_stree_stack(&default_stack, 0, "has_default", NULL, &true_state);
847 int __pop_default(void)
849 struct stree *stree;
851 stree = pop_stree(&default_stack);
852 if (stree) {
853 free_stree(&stree);
854 return 1;
856 return 0;
859 static struct named_stree *alloc_named_stree(const char *name, struct stree *stree)
861 struct named_stree *named_stree = __alloc_named_stree(0);
863 named_stree->name = (char *)name;
864 named_stree->stree = stree;
865 return named_stree;
868 void __save_gotos(const char *name)
870 struct stree **stree;
871 struct stree *clone;
873 stree = get_named_stree(goto_stack, name);
874 if (stree) {
875 merge_stree(stree, cur_stree);
876 return;
877 } else {
878 struct named_stree *named_stree;
880 clone = clone_stree(cur_stree);
881 named_stree = alloc_named_stree(name, clone);
882 add_ptr_list(&goto_stack, named_stree);
886 void __merge_gotos(const char *name)
888 struct stree **stree;
890 stree = get_named_stree(goto_stack, name);
891 if (stree)
892 merge_stree(&cur_stree, *stree);