db: add a comment
[smatch.git] / smatch_states.c
blob3811c28fe87b00bbdd77ec6327e7a5e60155cff3
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 struct state_list_stack *implied_pools;
58 int option_debug;
60 void __print_cur_slist(void)
62 __print_slist(cur_slist);
65 static int in_declarations_bit(void)
67 struct statement *tmp;
69 FOR_EACH_PTR_REVERSE(big_statement_stack, tmp) {
70 if (tmp->type == STMT_DECLARATION)
71 return 1;
72 return 0;
73 } END_FOR_EACH_PTR_REVERSE(tmp);
74 return 0;
77 int unreachable(void)
79 static int reset_warnings = 1;
81 if (cur_slist) {
82 reset_warnings = 1;
83 return 0;
86 if (in_declarations_bit())
87 return 1;
89 /* option spammy turns on a noisier version of this */
90 if (reset_warnings && !option_spammy)
91 sm_msg("info: ignoring unreachable code.");
92 reset_warnings = 0;
93 return 1;
96 struct sm_state *set_state(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
98 struct sm_state *ret;
100 if (!name)
101 return NULL;
103 if (option_debug) {
104 struct smatch_state *s;
106 s = get_state(owner, name, sym);
107 if (!s)
108 printf("%d new state. name='%s' [%s] %s\n",
109 get_lineno(), name, check_name(owner), show_state(state));
110 else
111 printf("%d state change name='%s' [%s] %s => %s\n",
112 get_lineno(), name, check_name(owner), show_state(s),
113 show_state(state));
116 if (owner != -1 && unreachable())
117 return NULL;
119 if (fake_cur_slist_stack)
120 set_state_stack(&fake_cur_slist_stack, owner, name, sym, state);
122 ret = set_state_slist(&cur_slist, owner, name, sym, state);
124 if (cond_true_stack) {
125 set_state_stack(&cond_true_stack, owner, name, sym, state);
126 set_state_stack(&cond_false_stack, owner, name, sym, state);
128 return ret;
131 struct sm_state *set_state_expr(int owner, struct expression *expr, struct smatch_state *state)
133 char *name;
134 struct symbol *sym;
135 struct sm_state *ret = NULL;
137 expr = strip_expr(expr);
138 name = get_variable_from_expr(expr, &sym);
139 if (!name || !sym)
140 goto free;
141 ret = set_state(owner, name, sym, state);
142 free:
143 free_string(name);
144 return ret;
147 void __push_fake_cur_slist()
149 push_slist(&fake_cur_slist_stack, NULL);
150 __save_pre_cond_states();
153 struct state_list *__pop_fake_cur_slist()
155 __use_pre_cond_states();
156 return pop_slist(&fake_cur_slist_stack);
159 void __merge_slist_into_cur(struct state_list *slist)
161 struct sm_state *sm;
162 struct sm_state *orig;
163 struct sm_state *merged;
165 FOR_EACH_PTR(slist, sm) {
166 orig = get_sm_state(sm->owner, sm->name, sm->sym);
167 if (orig)
168 merged = merge_sm_states(orig, sm);
169 else
170 merged = sm;
171 __set_sm(merged);
172 } END_FOR_EACH_PTR(sm);
175 void __set_sm(struct sm_state *sm)
177 if (option_debug) {
178 struct smatch_state *s;
180 s = get_state(sm->owner, sm->name, sm->sym);
181 if (!s)
182 printf("%d new state. name='%s' [%s] %s\n",
183 get_lineno(), sm->name, check_name(sm->owner),
184 show_state(sm->state));
185 else
186 printf("%d state change name='%s' [%s] %s => %s\n",
187 get_lineno(), sm->name, check_name(sm->owner), show_state(s),
188 show_state(sm->state));
191 if (unreachable())
192 return;
194 overwrite_sm_state(&cur_slist, sm);
196 if (cond_true_stack) {
197 overwrite_sm_state_stack(&cond_true_stack, sm);
198 overwrite_sm_state_stack(&cond_false_stack, sm);
202 struct smatch_state *get_state(int owner, const char *name, struct symbol *sym)
204 return get_state_slist(cur_slist, owner, name, sym);
207 struct smatch_state *get_state_expr(int owner, struct expression *expr)
209 char *name;
210 struct symbol *sym;
211 struct smatch_state *ret = NULL;
213 expr = strip_expr(expr);
214 name = get_variable_from_expr(expr, &sym);
215 if (!name || !sym)
216 goto free;
217 ret = get_state(owner, name, sym);
218 free:
219 free_string(name);
220 return ret;
223 struct state_list *get_possible_states(int owner, const char *name, struct symbol *sym)
225 struct sm_state *sms;
227 sms = get_sm_state_slist(cur_slist, owner, name, sym);
228 if (sms)
229 return sms->possible;
230 return NULL;
233 struct state_list *get_possible_states_expr(int owner, struct expression *expr)
235 char *name;
236 struct symbol *sym;
237 struct state_list *ret = NULL;
239 expr = strip_expr(expr);
240 name = get_variable_from_expr(expr, &sym);
241 if (!name || !sym)
242 goto free;
243 ret = get_possible_states(owner, name, sym);
244 free:
245 free_string(name);
246 return ret;
249 struct sm_state *get_sm_state(int owner, const char *name, struct symbol *sym)
251 return get_sm_state_slist(cur_slist, owner, name, sym);
254 struct sm_state *get_sm_state_expr(int owner, struct expression *expr)
256 char *name;
257 struct symbol *sym;
258 struct sm_state *ret = NULL;
260 expr = strip_expr(expr);
261 name = get_variable_from_expr(expr, &sym);
262 if (!name || !sym)
263 goto free;
264 ret = get_sm_state(owner, name, sym);
265 free:
266 free_string(name);
267 return ret;
270 void delete_state(int owner, const char *name, struct symbol *sym)
272 delete_state_slist(&cur_slist, owner, name, sym);
273 if (cond_true_stack) {
274 delete_state_stack(&pre_cond_stack, owner, name, sym);
275 delete_state_stack(&cond_true_stack, owner, name, sym);
276 delete_state_stack(&cond_false_stack, owner, name, sym);
280 void delete_state_expr(int owner, struct expression *expr)
282 char *name;
283 struct symbol *sym;
285 expr = strip_expr(expr);
286 name = get_variable_from_expr(expr, &sym);
287 if (!name || !sym)
288 goto free;
289 delete_state(owner, name, sym);
290 free:
291 free_string(name);
294 struct state_list *get_all_states(int owner)
296 struct state_list *slist = NULL;
297 struct sm_state *tmp;
299 FOR_EACH_PTR(cur_slist, tmp) {
300 if (tmp->owner == owner)
301 add_ptr_list(&slist, tmp);
302 } END_FOR_EACH_PTR(tmp);
304 return slist;
307 int is_reachable(void)
309 if (cur_slist)
310 return 1;
311 return 0;
314 struct state_list *__get_cur_slist(void)
316 return cur_slist;
319 void set_true_false_states(int owner, const char *name, struct symbol *sym,
320 struct smatch_state *true_state,
321 struct smatch_state *false_state)
323 if (option_debug) {
324 struct smatch_state *tmp;
326 tmp = get_state(owner, name, sym);
327 sm_debug("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
328 get_lineno(), name, show_state(tmp),
329 show_state(true_state), show_state(false_state));
332 if (unreachable())
333 return;
335 if (!cond_false_stack || !cond_true_stack) {
336 printf("Error: missing true/false stacks\n");
337 return;
340 if (true_state) {
341 set_state_slist(&cur_slist, owner, name, sym, true_state);
342 set_state_stack(&cond_true_stack, owner, name, sym, true_state);
344 if (false_state)
345 set_state_stack(&cond_false_stack, owner, name, sym, false_state);
348 void set_true_false_states_expr(int owner, struct expression *expr,
349 struct smatch_state *true_state,
350 struct smatch_state *false_state)
352 char *name;
353 struct symbol *sym;
355 expr = strip_expr(expr);
356 name = get_variable_from_expr(expr, &sym);
357 if (!name || !sym)
358 goto free;
359 set_true_false_states(owner, name, sym, true_state, false_state);
360 free:
361 free_string(name);
364 void __set_true_false_sm(struct sm_state *true_sm, struct sm_state *false_sm)
366 if (unreachable())
367 return;
369 if (!cond_false_stack || !cond_true_stack) {
370 printf("Error: missing true/false stacks\n");
371 return;
374 if (true_sm) {
375 overwrite_sm_state(&cur_slist, true_sm);
376 overwrite_sm_state_stack(&cond_true_stack, true_sm);
378 if (false_sm)
379 overwrite_sm_state_stack(&cond_false_stack, false_sm);
382 void nullify_path(void)
384 free_slist(&cur_slist);
387 void __match_nullify_path_hook(const char *fn, struct expression *expr,
388 void *unused)
390 nullify_path();
394 * At the start of every function we mark the path
395 * as unnull. That way there is always at least one state
396 * in the cur_slist until nullify_path is called. This
397 * is used in merge_slist() for the first null check.
399 void __unnullify_path(void)
401 set_state(-1, "unnull_path", NULL, &true_state);
404 int __path_is_null(void)
406 if (cur_slist)
407 return 0;
408 return 1;
411 static void check_stack_free(struct state_list_stack **stack)
413 if (*stack) {
414 sm_msg("smatch internal error: stack not empty");
415 free_stack_and_slists(stack);
419 void clear_all_states(void)
421 struct named_slist *named_slist;
423 nullify_path();
424 check_stack_free(&true_stack);
425 check_stack_free(&false_stack);
426 check_stack_free(&pre_cond_stack);
427 check_stack_free(&cond_true_stack);
428 check_stack_free(&cond_false_stack);
429 check_stack_free(&break_stack);
430 check_stack_free(&switch_stack);
431 check_stack_free(&continue_stack);
432 free_stack_and_slists(&implied_pools);
434 FOR_EACH_PTR(goto_stack, named_slist) {
435 free_slist(&named_slist->slist);
436 } END_FOR_EACH_PTR(named_slist);
437 __free_ptr_list((struct ptr_list **)&goto_stack);
438 free_every_single_sm_state();
441 void __push_cond_stacks(void)
443 push_slist(&cond_true_stack, NULL);
444 push_slist(&cond_false_stack, NULL);
447 struct state_list *__copy_cond_true_states(void)
449 struct state_list *ret;
451 ret = pop_slist(&cond_true_stack);
452 push_slist(&cond_true_stack, clone_slist(ret));
453 return ret;
456 struct state_list *__copy_cond_false_states(void)
458 struct state_list *ret;
460 ret = pop_slist(&cond_false_stack);
461 push_slist(&cond_false_stack, clone_slist(ret));
462 return ret;
465 struct state_list *__pop_cond_true_stack(void)
467 return pop_slist(&cond_true_stack);
470 struct state_list *__pop_cond_false_stack(void)
472 return pop_slist(&cond_false_stack);
476 * This combines the pre cond states with either the true or false states.
477 * For example:
478 * a = kmalloc() ; if (a !! foo(a)
479 * In the pre state a is possibly null. In the true state it is non null.
480 * In the false state it is null. Combine the pre and the false to get
481 * that when we call 'foo', 'a' is null.
483 static void __use_cond_stack(struct state_list_stack **stack)
485 struct state_list *slist;
487 free_slist(&cur_slist);
489 cur_slist = pop_slist(&pre_cond_stack);
490 push_slist(&pre_cond_stack, clone_slist(cur_slist));
492 slist = pop_slist(stack);
493 overwrite_slist(slist, &cur_slist);
494 push_slist(stack, slist);
497 void __use_pre_cond_states(void)
499 free_slist(&cur_slist);
500 cur_slist = pop_slist(&pre_cond_stack);
503 void __use_cond_true_states(void)
505 __use_cond_stack(&cond_true_stack);
508 void __use_cond_false_states(void)
510 __use_cond_stack(&cond_false_stack);
513 void __negate_cond_stacks(void)
515 struct state_list *old_false, *old_true;
517 __use_cond_stack(&cond_false_stack);
518 old_false = pop_slist(&cond_false_stack);
519 old_true = pop_slist(&cond_true_stack);
520 push_slist(&cond_false_stack, old_true);
521 push_slist(&cond_true_stack, old_false);
524 void __and_cond_states(void)
526 and_slist_stack(&cond_true_stack);
527 or_slist_stack(&pre_cond_stack, cur_slist, &cond_false_stack);
530 void __or_cond_states(void)
532 or_slist_stack(&pre_cond_stack, cur_slist, &cond_true_stack);
533 and_slist_stack(&cond_false_stack);
536 void __save_pre_cond_states(void)
538 push_slist(&pre_cond_stack, clone_slist(cur_slist));
541 void __discard_pre_cond_states(void)
543 struct state_list *tmp;
545 tmp = pop_slist(&pre_cond_stack);
546 free_slist(&tmp);
549 void __use_cond_states(void)
551 struct state_list *pre, *pre_clone, *true_states, *false_states;
553 pre = pop_slist(&pre_cond_stack);
554 pre_clone = clone_slist(pre);
556 true_states = pop_slist(&cond_true_stack);
557 overwrite_slist(true_states, &pre);
558 /* we use the true states right away */
559 free_slist(&cur_slist);
560 cur_slist = pre;
562 false_states = pop_slist(&cond_false_stack);
563 overwrite_slist(false_states, &pre_clone);
564 push_slist(&false_stack, pre_clone);
567 void __push_true_states(void)
569 push_slist(&true_stack, clone_slist(cur_slist));
572 void __use_false_states(void)
574 free_slist(&cur_slist);
575 cur_slist = pop_slist(&false_stack);
578 void __discard_false_states(void)
580 struct state_list *slist;
582 slist = pop_slist(&false_stack);
583 free_slist(&slist);
586 void __merge_false_states(void)
588 struct state_list *slist;
590 slist = pop_slist(&false_stack);
591 merge_slist(&cur_slist, slist);
592 free_slist(&slist);
595 void __merge_true_states(void)
597 struct state_list *slist;
599 slist = pop_slist(&true_stack);
600 merge_slist(&cur_slist, slist);
601 free_slist(&slist);
604 void __push_continues(void)
606 push_slist(&continue_stack, NULL);
609 void __discard_continues(void)
611 struct state_list *slist;
613 slist = pop_slist(&continue_stack);
614 free_slist(&slist);
617 void __process_continues(void)
619 struct state_list *slist;
621 slist = pop_slist(&continue_stack);
622 if (!slist)
623 slist = clone_slist(cur_slist);
624 else
625 merge_slist(&slist, cur_slist);
627 push_slist(&continue_stack, slist);
630 static int top_slist_empty(struct state_list_stack **stack)
632 struct state_list *tmp;
633 int empty = 0;
635 tmp = pop_slist(stack);
636 if (!tmp)
637 empty = 1;
638 push_slist(stack, tmp);
639 return empty;
642 /* a silly loop does this: while(i--) { return; } */
643 void __warn_on_silly_pre_loops(void)
645 if (!__path_is_null())
646 return;
647 if (!top_slist_empty(&continue_stack))
648 return;
649 if (!top_slist_empty(&break_stack))
650 return;
651 /* if the path was nullified before the loop, then we already
652 printed an error earlier */
653 if (top_slist_empty(&false_stack))
654 return;
655 sm_msg("info: loop could be replaced with if statement.");
658 void __merge_continues(void)
660 struct state_list *slist;
662 slist = pop_slist(&continue_stack);
663 merge_slist(&cur_slist, slist);
664 free_slist(&slist);
667 void __push_breaks(void)
669 push_slist(&break_stack, NULL);
672 void __process_breaks(void)
674 struct state_list *slist;
676 slist = pop_slist(&break_stack);
677 if (!slist)
678 slist = clone_slist(cur_slist);
679 else
680 merge_slist(&slist, cur_slist);
682 push_slist(&break_stack, slist);
685 void __merge_breaks(void)
687 struct state_list *slist;
689 slist = pop_slist(&break_stack);
690 merge_slist(&cur_slist, slist);
691 free_slist(&slist);
694 void __use_breaks(void)
696 free_slist(&cur_slist);
697 cur_slist = pop_slist(&break_stack);
700 void __save_switch_states(struct expression *switch_expr)
702 push_range_list(&remaining_cases, __get_implied_values(switch_expr));
703 push_slist(&switch_stack, clone_slist(cur_slist));
706 void __merge_switches(struct expression *switch_expr, struct expression *case_expr)
708 struct state_list *slist;
709 struct state_list *implied_slist;
711 slist = pop_slist(&switch_stack);
712 implied_slist = __implied_case_slist(switch_expr, case_expr, &remaining_cases, &slist);
713 merge_slist(&cur_slist, implied_slist);
714 free_slist(&implied_slist);
715 push_slist(&switch_stack, slist);
718 void __discard_switches(void)
720 struct state_list *slist;
722 pop_range_list(&remaining_cases);
723 slist = pop_slist(&switch_stack);
724 free_slist(&slist);
727 void __push_default(void)
729 push_slist(&default_stack, NULL);
732 void __set_default(void)
734 set_state_stack(&default_stack, 0, "has_default", NULL, &true_state);
737 int __pop_default(void)
739 struct state_list *slist;
741 slist = pop_slist(&default_stack);
742 if (slist) {
743 free_slist(&slist);
744 return 1;
746 return 0;
749 static struct named_slist *alloc_named_slist(const char *name, struct state_list *slist)
751 struct named_slist *named_slist = __alloc_named_slist(0);
753 named_slist->name = (char *)name;
754 named_slist->slist = slist;
755 return named_slist;
758 void __save_gotos(const char *name)
760 struct state_list **slist;
761 struct state_list *clone;
763 slist = get_slist_from_named_stack(goto_stack, name);
764 if (slist) {
765 clone = clone_slist(cur_slist);
766 merge_slist(slist, clone);
767 free_slist(&clone);
768 return;
769 } else {
770 struct named_slist *named_slist;
772 clone = clone_slist(cur_slist);
773 named_slist = alloc_named_slist(name, clone);
774 add_ptr_list(&goto_stack, named_slist);
778 void __merge_gotos(const char *name)
780 struct state_list **slist;
782 slist = get_slist_from_named_stack(goto_stack, name);
783 if (slist)
784 merge_slist(&cur_slist, *slist);