show_unreachable.sh: replace tabs with spaces
[smatch.git] / smatch_states.c
blobf141f056c0baa0e5d6f0acfa4d8f1c0c38712262
1 /*
2 * sparse/smatch_states.c
4 * Copyright (C) 2006 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
11 * You have a lists of states. kernel = locked, foo = NULL, ...
12 * When you hit an if {} else {} statement then you swap the list
13 * of states for a different list of states. The lists are stored
14 * on stacks.
16 * At the beginning of this file there are list of the stacks that
17 * we use. Each function in this file does something to one of
18 * of the stacks.
20 * So the smatch_flow.c understands code but it doesn't understand states.
21 * smatch_flow calls functions in this file. This file calls functions
22 * in smatch_slist.c which just has boring generic plumbing for handling
23 * state lists. But really it's this file where all the magic happens.
26 #include <stdlib.h>
27 #include <stdio.h>
28 #include "smatch.h"
29 #include "smatch_slist.h"
30 #include "smatch_extra.h"
32 struct smatch_state undefined = { .name = "undefined" };
33 struct smatch_state merged = { .name = "merged" };
34 struct smatch_state true_state = { .name = "true" };
35 struct smatch_state false_state = { .name = "false" };
37 static struct state_list *cur_slist; /* current states */
39 static struct state_list_stack *true_stack; /* states after a t/f branch */
40 static struct state_list_stack *false_stack;
41 static struct state_list_stack *pre_cond_stack; /* states before a t/f branch */
43 static struct state_list_stack *cond_true_stack; /* states affected by a branch */
44 static struct state_list_stack *cond_false_stack;
46 static struct state_list_stack *fake_cur_slist_stack;
48 static struct state_list_stack *break_stack;
49 static struct state_list_stack *switch_stack;
50 static struct range_list_stack *remaining_cases;
51 static struct state_list_stack *default_stack;
52 static struct state_list_stack *continue_stack;
54 static struct named_stack *goto_stack;
56 static struct ptr_list *backup;
58 struct state_list_stack *implied_pools;
60 int option_debug;
62 void __print_cur_slist(void)
64 __print_slist(cur_slist);
67 static int in_declarations_bit(void)
69 struct statement *tmp;
71 FOR_EACH_PTR_REVERSE(big_statement_stack, tmp) {
72 if (tmp->type == STMT_DECLARATION)
73 return 1;
74 return 0;
75 } END_FOR_EACH_PTR_REVERSE(tmp);
76 return 0;
79 int unreachable(void)
81 static int reset_warnings = 1;
83 if (cur_slist) {
84 reset_warnings = 1;
85 return 0;
88 if (in_declarations_bit())
89 return 1;
91 /* option spammy turns on a noisier version of this */
92 if (reset_warnings && !option_spammy)
93 sm_msg("info: ignoring unreachable code.");
94 reset_warnings = 0;
95 return 1;
98 struct sm_state *set_state(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
100 struct sm_state *ret;
102 if (!name)
103 return NULL;
105 if (option_debug) {
106 struct smatch_state *s;
108 s = get_state(owner, name, sym);
109 if (!s)
110 printf("%d new state. name='%s' [%s] %s\n",
111 get_lineno(), name, check_name(owner), show_state(state));
112 else
113 printf("%d state change name='%s' [%s] %s => %s\n",
114 get_lineno(), name, check_name(owner), show_state(s),
115 show_state(state));
118 if (owner != -1 && unreachable())
119 return NULL;
121 if (fake_cur_slist_stack)
122 set_state_stack(&fake_cur_slist_stack, owner, name, sym, state);
124 ret = set_state_slist(&cur_slist, owner, name, sym, state);
126 if (cond_true_stack) {
127 set_state_stack(&cond_true_stack, owner, name, sym, state);
128 set_state_stack(&cond_false_stack, owner, name, sym, state);
130 return ret;
133 struct sm_state *set_state_expr(int owner, struct expression *expr, struct smatch_state *state)
135 char *name;
136 struct symbol *sym;
137 struct sm_state *ret = NULL;
139 expr = strip_expr(expr);
140 name = expr_to_var_sym(expr, &sym);
141 if (!name || !sym)
142 goto free;
143 ret = set_state(owner, name, sym, state);
144 free:
145 free_string(name);
146 return ret;
149 void __push_fake_cur_slist()
151 push_slist(&fake_cur_slist_stack, NULL);
152 __save_pre_cond_states();
155 struct state_list *__pop_fake_cur_slist()
157 __use_pre_cond_states();
158 return pop_slist(&fake_cur_slist_stack);
161 void __merge_slist_into_cur(struct state_list *slist)
163 struct sm_state *sm;
164 struct sm_state *orig;
165 struct sm_state *merged;
167 FOR_EACH_PTR(slist, sm) {
168 orig = get_sm_state(sm->owner, sm->name, sm->sym);
169 if (orig)
170 merged = merge_sm_states(orig, sm);
171 else
172 merged = sm;
173 __set_sm(merged);
174 } END_FOR_EACH_PTR(sm);
177 void __set_sm(struct sm_state *sm)
179 if (option_debug) {
180 struct smatch_state *s;
182 s = get_state(sm->owner, sm->name, sm->sym);
183 if (!s)
184 printf("%d new state. name='%s' [%s] %s\n",
185 get_lineno(), sm->name, check_name(sm->owner),
186 show_state(sm->state));
187 else
188 printf("%d state change name='%s' [%s] %s => %s\n",
189 get_lineno(), sm->name, check_name(sm->owner), show_state(s),
190 show_state(sm->state));
193 if (unreachable())
194 return;
196 if (fake_cur_slist_stack)
197 overwrite_sm_state_stack(&fake_cur_slist_stack, sm);
199 overwrite_sm_state(&cur_slist, sm);
201 if (cond_true_stack) {
202 overwrite_sm_state_stack(&cond_true_stack, sm);
203 overwrite_sm_state_stack(&cond_false_stack, sm);
207 struct smatch_state *get_state(int owner, const char *name, struct symbol *sym)
209 return get_state_slist(cur_slist, owner, name, sym);
212 struct smatch_state *get_state_expr(int owner, struct expression *expr)
214 char *name;
215 struct symbol *sym;
216 struct smatch_state *ret = NULL;
218 expr = strip_expr(expr);
219 name = expr_to_var_sym(expr, &sym);
220 if (!name || !sym)
221 goto free;
222 ret = get_state(owner, name, sym);
223 free:
224 free_string(name);
225 return ret;
228 struct state_list *get_possible_states(int owner, const char *name, struct symbol *sym)
230 struct sm_state *sms;
232 sms = get_sm_state_slist(cur_slist, owner, name, sym);
233 if (sms)
234 return sms->possible;
235 return NULL;
238 struct state_list *get_possible_states_expr(int owner, struct expression *expr)
240 char *name;
241 struct symbol *sym;
242 struct state_list *ret = NULL;
244 expr = strip_expr(expr);
245 name = expr_to_var_sym(expr, &sym);
246 if (!name || !sym)
247 goto free;
248 ret = get_possible_states(owner, name, sym);
249 free:
250 free_string(name);
251 return ret;
254 struct sm_state *get_sm_state(int owner, const char *name, struct symbol *sym)
256 return get_sm_state_slist(cur_slist, owner, name, sym);
259 struct sm_state *get_sm_state_expr(int owner, struct expression *expr)
261 char *name;
262 struct symbol *sym;
263 struct sm_state *ret = NULL;
265 expr = strip_expr(expr);
266 name = expr_to_var_sym(expr, &sym);
267 if (!name || !sym)
268 goto free;
269 ret = get_sm_state(owner, name, sym);
270 free:
271 free_string(name);
272 return ret;
275 void delete_state(int owner, const char *name, struct symbol *sym)
277 delete_state_slist(&cur_slist, owner, name, sym);
278 if (cond_true_stack) {
279 delete_state_stack(&pre_cond_stack, owner, name, sym);
280 delete_state_stack(&cond_true_stack, owner, name, sym);
281 delete_state_stack(&cond_false_stack, owner, name, sym);
285 void delete_state_expr(int owner, struct expression *expr)
287 char *name;
288 struct symbol *sym;
290 expr = strip_expr(expr);
291 name = expr_to_var_sym(expr, &sym);
292 if (!name || !sym)
293 goto free;
294 delete_state(owner, name, sym);
295 free:
296 free_string(name);
299 struct state_list *get_all_states_slist(int owner, struct state_list *source)
301 struct state_list *slist = NULL;
302 struct sm_state *tmp;
304 FOR_EACH_PTR(source, tmp) {
305 if (tmp->owner == owner)
306 add_ptr_list(&slist, tmp);
307 } END_FOR_EACH_PTR(tmp);
309 return slist;
312 struct state_list *get_all_states(int owner)
314 struct state_list *slist = NULL;
315 struct sm_state *tmp;
317 FOR_EACH_PTR(cur_slist, tmp) {
318 if (tmp->owner == owner)
319 add_ptr_list(&slist, tmp);
320 } END_FOR_EACH_PTR(tmp);
322 return slist;
325 int is_reachable(void)
327 if (cur_slist)
328 return 1;
329 return 0;
332 struct state_list *__get_cur_slist(void)
334 return cur_slist;
337 void set_true_false_states(int owner, const char *name, struct symbol *sym,
338 struct smatch_state *true_state,
339 struct smatch_state *false_state)
341 if (option_debug) {
342 struct smatch_state *tmp;
344 tmp = get_state(owner, name, sym);
345 sm_debug("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
346 get_lineno(), name, show_state(tmp),
347 show_state(true_state), show_state(false_state));
350 if (unreachable())
351 return;
353 if (!cond_false_stack || !cond_true_stack) {
354 printf("Error: missing true/false stacks\n");
355 return;
358 if (true_state) {
359 set_state_slist(&cur_slist, owner, name, sym, true_state);
360 set_state_stack(&cond_true_stack, owner, name, sym, true_state);
362 if (false_state)
363 set_state_stack(&cond_false_stack, owner, name, sym, false_state);
366 void set_true_false_states_expr(int owner, struct expression *expr,
367 struct smatch_state *true_state,
368 struct smatch_state *false_state)
370 char *name;
371 struct symbol *sym;
373 expr = strip_expr(expr);
374 name = expr_to_var_sym(expr, &sym);
375 if (!name || !sym)
376 goto free;
377 set_true_false_states(owner, name, sym, true_state, false_state);
378 free:
379 free_string(name);
382 void __set_true_false_sm(struct sm_state *true_sm, struct sm_state *false_sm)
384 if (unreachable())
385 return;
387 if (!cond_false_stack || !cond_true_stack) {
388 printf("Error: missing true/false stacks\n");
389 return;
392 if (true_sm) {
393 overwrite_sm_state(&cur_slist, true_sm);
394 overwrite_sm_state_stack(&cond_true_stack, true_sm);
396 if (false_sm)
397 overwrite_sm_state_stack(&cond_false_stack, false_sm);
400 void nullify_path(void)
402 free_slist(&cur_slist);
405 void __match_nullify_path_hook(const char *fn, struct expression *expr,
406 void *unused)
408 nullify_path();
412 * At the start of every function we mark the path
413 * as unnull. That way there is always at least one state
414 * in the cur_slist until nullify_path is called. This
415 * is used in merge_slist() for the first null check.
417 void __unnullify_path(void)
419 set_state(-1, "unnull_path", NULL, &true_state);
422 int __path_is_null(void)
424 if (cur_slist)
425 return 0;
426 return 1;
429 static void check_stack_free(struct state_list_stack **stack)
431 if (*stack) {
432 sm_msg("smatch internal error: stack not empty");
433 free_stack_and_slists(stack);
437 void save_all_states(void)
439 __add_ptr_list(&backup, cur_slist, 0);
441 __add_ptr_list(&backup, true_stack, 0);
442 __add_ptr_list(&backup, false_stack, 0);
443 __add_ptr_list(&backup, pre_cond_stack, 0);
445 __add_ptr_list(&backup, cond_true_stack, 0);
446 __add_ptr_list(&backup, cond_false_stack, 0);
448 __add_ptr_list(&backup, fake_cur_slist_stack, 0);
450 __add_ptr_list(&backup, break_stack, 0);
451 __add_ptr_list(&backup, switch_stack, 0);
452 __add_ptr_list(&backup, remaining_cases, 0);
453 __add_ptr_list(&backup, default_stack, 0);
454 __add_ptr_list(&backup, continue_stack, 0);
456 __add_ptr_list(&backup, goto_stack, 0);
459 void nullify_all_states(void)
461 cur_slist = NULL;
463 true_stack = NULL;
464 false_stack = NULL;
465 pre_cond_stack = NULL;
467 cond_true_stack = NULL;
468 cond_false_stack = NULL;
470 fake_cur_slist_stack = NULL;
472 break_stack = NULL;
473 switch_stack = NULL;
474 remaining_cases = NULL;
475 default_stack = NULL;
476 continue_stack = NULL;
478 goto_stack = NULL;
481 static void *pop_backup(void)
483 void *ret;
485 ret = last_ptr_list(backup);
486 delete_ptr_list_last(&backup);
487 return ret;
490 void restore_all_states(void)
492 goto_stack = pop_backup();
494 continue_stack = pop_backup();
495 default_stack = pop_backup();
496 remaining_cases = pop_backup();
497 switch_stack = pop_backup();
498 break_stack = pop_backup();
500 fake_cur_slist_stack = pop_backup();
502 cond_false_stack = pop_backup();
503 cond_true_stack = pop_backup();
505 pre_cond_stack = pop_backup();
506 false_stack = pop_backup();
507 true_stack = pop_backup();
509 cur_slist = pop_backup();
512 void clear_all_states(void)
514 struct named_slist *named_slist;
516 nullify_path();
517 check_stack_free(&true_stack);
518 check_stack_free(&false_stack);
519 check_stack_free(&pre_cond_stack);
520 check_stack_free(&cond_true_stack);
521 check_stack_free(&cond_false_stack);
522 check_stack_free(&break_stack);
523 check_stack_free(&switch_stack);
524 check_stack_free(&continue_stack);
525 free_stack_and_slists(&implied_pools);
527 FOR_EACH_PTR(goto_stack, named_slist) {
528 free_slist(&named_slist->slist);
529 } END_FOR_EACH_PTR(named_slist);
530 __free_ptr_list((struct ptr_list **)&goto_stack);
531 free_every_single_sm_state();
534 void __push_cond_stacks(void)
536 push_slist(&cond_true_stack, NULL);
537 push_slist(&cond_false_stack, NULL);
540 struct state_list *__copy_cond_true_states(void)
542 struct state_list *ret;
544 ret = pop_slist(&cond_true_stack);
545 push_slist(&cond_true_stack, clone_slist(ret));
546 return ret;
549 struct state_list *__copy_cond_false_states(void)
551 struct state_list *ret;
553 ret = pop_slist(&cond_false_stack);
554 push_slist(&cond_false_stack, clone_slist(ret));
555 return ret;
558 struct state_list *__pop_cond_true_stack(void)
560 return pop_slist(&cond_true_stack);
563 struct state_list *__pop_cond_false_stack(void)
565 return pop_slist(&cond_false_stack);
569 * This combines the pre cond states with either the true or false states.
570 * For example:
571 * a = kmalloc() ; if (a !! foo(a)
572 * In the pre state a is possibly null. In the true state it is non null.
573 * In the false state it is null. Combine the pre and the false to get
574 * that when we call 'foo', 'a' is null.
576 static void __use_cond_stack(struct state_list_stack **stack)
578 struct state_list *slist;
580 free_slist(&cur_slist);
582 cur_slist = pop_slist(&pre_cond_stack);
583 push_slist(&pre_cond_stack, clone_slist(cur_slist));
585 slist = pop_slist(stack);
586 overwrite_slist(slist, &cur_slist);
587 push_slist(stack, slist);
590 void __use_pre_cond_states(void)
592 free_slist(&cur_slist);
593 cur_slist = pop_slist(&pre_cond_stack);
596 void __use_cond_true_states(void)
598 __use_cond_stack(&cond_true_stack);
601 void __use_cond_false_states(void)
603 __use_cond_stack(&cond_false_stack);
606 void __negate_cond_stacks(void)
608 struct state_list *old_false, *old_true;
610 __use_cond_stack(&cond_false_stack);
611 old_false = pop_slist(&cond_false_stack);
612 old_true = pop_slist(&cond_true_stack);
613 push_slist(&cond_false_stack, old_true);
614 push_slist(&cond_true_stack, old_false);
617 void __and_cond_states(void)
619 and_slist_stack(&cond_true_stack);
620 or_slist_stack(&pre_cond_stack, cur_slist, &cond_false_stack);
623 void __or_cond_states(void)
625 or_slist_stack(&pre_cond_stack, cur_slist, &cond_true_stack);
626 and_slist_stack(&cond_false_stack);
629 void __save_pre_cond_states(void)
631 push_slist(&pre_cond_stack, clone_slist(cur_slist));
634 void __discard_pre_cond_states(void)
636 struct state_list *tmp;
638 tmp = pop_slist(&pre_cond_stack);
639 free_slist(&tmp);
642 void __use_cond_states(void)
644 struct state_list *pre, *pre_clone, *true_states, *false_states;
646 pre = pop_slist(&pre_cond_stack);
647 pre_clone = clone_slist(pre);
649 true_states = pop_slist(&cond_true_stack);
650 overwrite_slist(true_states, &pre);
651 /* we use the true states right away */
652 free_slist(&cur_slist);
653 cur_slist = pre;
655 false_states = pop_slist(&cond_false_stack);
656 overwrite_slist(false_states, &pre_clone);
657 push_slist(&false_stack, pre_clone);
660 void __push_true_states(void)
662 push_slist(&true_stack, clone_slist(cur_slist));
665 void __use_false_states(void)
667 free_slist(&cur_slist);
668 cur_slist = pop_slist(&false_stack);
671 void __discard_false_states(void)
673 struct state_list *slist;
675 slist = pop_slist(&false_stack);
676 free_slist(&slist);
679 void __merge_false_states(void)
681 struct state_list *slist;
683 slist = pop_slist(&false_stack);
684 merge_slist(&cur_slist, slist);
685 free_slist(&slist);
688 void __merge_true_states(void)
690 struct state_list *slist;
692 slist = pop_slist(&true_stack);
693 merge_slist(&cur_slist, slist);
694 free_slist(&slist);
697 void __push_continues(void)
699 push_slist(&continue_stack, NULL);
702 void __discard_continues(void)
704 struct state_list *slist;
706 slist = pop_slist(&continue_stack);
707 free_slist(&slist);
710 void __process_continues(void)
712 struct state_list *slist;
714 slist = pop_slist(&continue_stack);
715 if (!slist)
716 slist = clone_slist(cur_slist);
717 else
718 merge_slist(&slist, cur_slist);
720 push_slist(&continue_stack, slist);
723 static int top_slist_empty(struct state_list_stack **stack)
725 struct state_list *tmp;
726 int empty = 0;
728 tmp = pop_slist(stack);
729 if (!tmp)
730 empty = 1;
731 push_slist(stack, tmp);
732 return empty;
735 /* a silly loop does this: while(i--) { return; } */
736 void __warn_on_silly_pre_loops(void)
738 if (!__path_is_null())
739 return;
740 if (!top_slist_empty(&continue_stack))
741 return;
742 if (!top_slist_empty(&break_stack))
743 return;
744 /* if the path was nullified before the loop, then we already
745 printed an error earlier */
746 if (top_slist_empty(&false_stack))
747 return;
748 sm_msg("info: loop could be replaced with if statement.");
751 void __merge_continues(void)
753 struct state_list *slist;
755 slist = pop_slist(&continue_stack);
756 merge_slist(&cur_slist, slist);
757 free_slist(&slist);
760 void __push_breaks(void)
762 push_slist(&break_stack, NULL);
765 void __process_breaks(void)
767 struct state_list *slist;
769 slist = pop_slist(&break_stack);
770 if (!slist)
771 slist = clone_slist(cur_slist);
772 else
773 merge_slist(&slist, cur_slist);
775 push_slist(&break_stack, slist);
778 int __has_breaks(void)
780 struct state_list *slist;
781 int ret;
783 slist = pop_slist(&break_stack);
784 ret = !!slist;
785 push_slist(&break_stack, slist);
786 return ret;
789 void __merge_breaks(void)
791 struct state_list *slist;
793 slist = pop_slist(&break_stack);
794 merge_slist(&cur_slist, slist);
795 free_slist(&slist);
798 void __use_breaks(void)
800 free_slist(&cur_slist);
801 cur_slist = pop_slist(&break_stack);
804 void __save_switch_states(struct expression *switch_expr)
806 push_rl(&remaining_cases, __get_implied_values(switch_expr));
807 push_slist(&switch_stack, clone_slist(cur_slist));
810 void __merge_switches(struct expression *switch_expr, struct expression *case_expr)
812 struct state_list *slist;
813 struct state_list *implied_slist;
815 slist = pop_slist(&switch_stack);
816 implied_slist = __implied_case_slist(switch_expr, case_expr, &remaining_cases, &slist);
817 merge_slist(&cur_slist, implied_slist);
818 free_slist(&implied_slist);
819 push_slist(&switch_stack, slist);
822 void __discard_switches(void)
824 struct state_list *slist;
826 pop_rl(&remaining_cases);
827 slist = pop_slist(&switch_stack);
828 free_slist(&slist);
831 void __push_default(void)
833 push_slist(&default_stack, NULL);
836 void __set_default(void)
838 set_state_stack(&default_stack, 0, "has_default", NULL, &true_state);
841 int __pop_default(void)
843 struct state_list *slist;
845 slist = pop_slist(&default_stack);
846 if (slist) {
847 free_slist(&slist);
848 return 1;
850 return 0;
853 static struct named_slist *alloc_named_slist(const char *name, struct state_list *slist)
855 struct named_slist *named_slist = __alloc_named_slist(0);
857 named_slist->name = (char *)name;
858 named_slist->slist = slist;
859 return named_slist;
862 void __save_gotos(const char *name)
864 struct state_list **slist;
865 struct state_list *clone;
867 slist = get_slist_from_named_stack(goto_stack, name);
868 if (slist) {
869 clone = clone_slist(cur_slist);
870 merge_slist(slist, clone);
871 free_slist(&clone);
872 return;
873 } else {
874 struct named_slist *named_slist;
876 clone = clone_slist(cur_slist);
877 named_slist = alloc_named_slist(name, clone);
878 add_ptr_list(&goto_stack, named_slist);
882 void __merge_gotos(const char *name)
884 struct state_list **slist;
886 slist = get_slist_from_named_stack(goto_stack, name);
887 if (slist)
888 merge_slist(&cur_slist, *slist);