gen_no_return_funcs: always keep the default no return functions
[smatch.git] / smatch_states.c
blobcc99114f25250d9dab73b1539cb8208666b1163c
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 __use_default_modification_hook(owner, name);
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 = get_variable_from_expr(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 __set_sm(struct sm_state *sm)
163 if (option_debug) {
164 struct smatch_state *s;
166 s = get_state(sm->owner, sm->name, sm->sym);
167 if (!s)
168 printf("%d new state. name='%s' [%s] %s\n",
169 get_lineno(), sm->name, check_name(sm->owner),
170 show_state(sm->state));
171 else
172 printf("%d state change name='%s' [%s] %s => %s\n",
173 get_lineno(), sm->name, check_name(sm->owner), show_state(s),
174 show_state(sm->state));
177 if (unreachable())
178 return;
180 overwrite_sm_state(&cur_slist, sm);
182 if (cond_true_stack) {
183 overwrite_sm_state_stack(&cond_true_stack, sm);
184 overwrite_sm_state_stack(&cond_false_stack, sm);
188 struct smatch_state *get_state(int owner, const char *name, struct symbol *sym)
190 return get_state_slist(cur_slist, owner, name, sym);
193 struct smatch_state *get_state_expr(int owner, struct expression *expr)
195 char *name;
196 struct symbol *sym;
197 struct smatch_state *ret = NULL;
199 expr = strip_expr(expr);
200 name = get_variable_from_expr(expr, &sym);
201 if (!name || !sym)
202 goto free;
203 ret = get_state(owner, name, sym);
204 free:
205 free_string(name);
206 return ret;
209 struct state_list *get_possible_states(int owner, const char *name, struct symbol *sym)
211 struct sm_state *sms;
213 sms = get_sm_state_slist(cur_slist, owner, name, sym);
214 if (sms)
215 return sms->possible;
216 return NULL;
219 struct state_list *get_possible_states_expr(int owner, struct expression *expr)
221 char *name;
222 struct symbol *sym;
223 struct state_list *ret = NULL;
225 expr = strip_expr(expr);
226 name = get_variable_from_expr(expr, &sym);
227 if (!name || !sym)
228 goto free;
229 ret = get_possible_states(owner, name, sym);
230 free:
231 free_string(name);
232 return ret;
235 struct sm_state *get_sm_state(int owner, const char *name, struct symbol *sym)
237 return get_sm_state_slist(cur_slist, owner, name, sym);
240 struct sm_state *get_sm_state_expr(int owner, struct expression *expr)
242 char *name;
243 struct symbol *sym;
244 struct sm_state *ret = NULL;
246 expr = strip_expr(expr);
247 name = get_variable_from_expr(expr, &sym);
248 if (!name || !sym)
249 goto free;
250 ret = get_sm_state(owner, name, sym);
251 free:
252 free_string(name);
253 return ret;
256 void delete_state(int owner, const char *name, struct symbol *sym)
258 delete_state_slist(&cur_slist, owner, name, sym);
259 if (cond_true_stack) {
260 delete_state_stack(&pre_cond_stack, owner, name, sym);
261 delete_state_stack(&cond_true_stack, owner, name, sym);
262 delete_state_stack(&cond_false_stack, owner, name, sym);
266 void delete_state_expr(int owner, struct expression *expr)
268 char *name;
269 struct symbol *sym;
271 expr = strip_expr(expr);
272 name = get_variable_from_expr(expr, &sym);
273 if (!name || !sym)
274 goto free;
275 delete_state(owner, name, sym);
276 free:
277 free_string(name);
280 struct state_list *get_all_states(int owner)
282 struct state_list *slist = NULL;
283 struct sm_state *tmp;
285 FOR_EACH_PTR(cur_slist, tmp) {
286 if (tmp->owner == owner) {
287 add_ptr_list(&slist, tmp);
289 } END_FOR_EACH_PTR(tmp);
291 return slist;
294 int is_reachable(void)
296 if (cur_slist)
297 return 1;
298 return 0;
301 struct state_list *__get_cur_slist(void)
303 return cur_slist;
306 void set_true_false_states(int owner, const char *name, struct symbol *sym,
307 struct smatch_state *true_state,
308 struct smatch_state *false_state)
310 if (option_debug) {
311 struct smatch_state *tmp;
313 tmp = get_state(owner, name, sym);
314 sm_debug("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
315 get_lineno(), name, show_state(tmp),
316 show_state(true_state), show_state(false_state));
319 if (unreachable())
320 return;
322 if (!cond_false_stack || !cond_true_stack) {
323 printf("Error: missing true/false stacks\n");
324 return;
327 __use_default_modification_hook(owner, name);
329 if (true_state) {
330 set_state_slist(&cur_slist, owner, name, sym, true_state);
331 set_state_stack(&cond_true_stack, owner, name, sym, true_state);
333 if (false_state)
334 set_state_stack(&cond_false_stack, owner, name, sym, false_state);
337 void set_true_false_states_expr(int owner, struct expression *expr,
338 struct smatch_state *true_state,
339 struct smatch_state *false_state)
341 char *name;
342 struct symbol *sym;
344 expr = strip_expr(expr);
345 name = get_variable_from_expr(expr, &sym);
346 if (!name || !sym)
347 goto free;
348 set_true_false_states(owner, name, sym, true_state, false_state);
349 free:
350 free_string(name);
353 void __set_true_false_sm(struct sm_state *true_sm, struct sm_state *false_sm)
355 if (unreachable())
356 return;
358 if (!cond_false_stack || !cond_true_stack) {
359 printf("Error: missing true/false stacks\n");
360 return;
363 if (true_sm) {
364 overwrite_sm_state(&cur_slist, true_sm);
365 overwrite_sm_state_stack(&cond_true_stack, true_sm);
367 if (false_sm)
368 overwrite_sm_state_stack(&cond_false_stack, false_sm);
371 void nullify_path(void)
373 free_slist(&cur_slist);
376 void __match_nullify_path_hook(const char *fn, struct expression *expr,
377 void *unused)
379 nullify_path();
383 * At the start of every function we mark the path
384 * as unnull. That way there is always at least one state
385 * in the cur_slist until nullify_path is called. This
386 * is used in merge_slist() for the first null check.
388 void __unnullify_path(void)
390 set_state(-1, "unnull_path", NULL, &true_state);
393 int __path_is_null(void)
395 if (cur_slist)
396 return 0;
397 return 1;
400 static void check_stack_free(struct state_list_stack **stack)
402 if (*stack) {
403 sm_msg("smatch internal error: stack not empty");
404 free_stack_and_slists(stack);
408 void clear_all_states(void)
410 struct named_slist *named_slist;
412 nullify_path();
413 check_stack_free(&true_stack);
414 check_stack_free(&false_stack);
415 check_stack_free(&pre_cond_stack);
416 check_stack_free(&cond_true_stack);
417 check_stack_free(&cond_false_stack);
418 check_stack_free(&break_stack);
419 check_stack_free(&switch_stack);
420 check_stack_free(&continue_stack);
421 free_stack_and_slists(&implied_pools);
423 FOR_EACH_PTR(goto_stack, named_slist) {
424 free_slist(&named_slist->slist);
425 } END_FOR_EACH_PTR(named_slist);
426 __free_ptr_list((struct ptr_list **)&goto_stack);
427 free_every_single_sm_state();
430 void __push_cond_stacks(void)
432 push_slist(&cond_true_stack, NULL);
433 push_slist(&cond_false_stack, NULL);
436 struct state_list *__copy_cond_true_states(void)
438 struct state_list *ret;
440 ret = pop_slist(&cond_true_stack);
441 push_slist(&cond_true_stack, clone_slist(ret));
442 return ret;
445 struct state_list *__copy_cond_false_states(void)
447 struct state_list *ret;
449 ret = pop_slist(&cond_false_stack);
450 push_slist(&cond_false_stack, clone_slist(ret));
451 return ret;
454 struct state_list *__pop_cond_true_stack(void)
456 return pop_slist(&cond_true_stack);
459 struct state_list *__pop_cond_false_stack(void)
461 return pop_slist(&cond_false_stack);
465 * This combines the pre cond states with either the true or false states.
466 * For example:
467 * a = kmalloc() ; if (a !! foo(a)
468 * In the pre state a is possibly null. In the true state it is non null.
469 * In the false state it is null. Combine the pre and the false to get
470 * that when we call 'foo', 'a' is null.
472 static void __use_cond_stack(struct state_list_stack **stack)
474 struct state_list *slist;
476 free_slist(&cur_slist);
478 cur_slist = pop_slist(&pre_cond_stack);
479 push_slist(&pre_cond_stack, clone_slist(cur_slist));
481 slist = pop_slist(stack);
482 overwrite_slist(slist, &cur_slist);
483 push_slist(stack, slist);
486 void __use_pre_cond_states(void)
488 free_slist(&cur_slist);
489 cur_slist = pop_slist(&pre_cond_stack);
492 void __use_cond_true_states(void)
494 __use_cond_stack(&cond_true_stack);
497 void __use_cond_false_states(void)
499 __use_cond_stack(&cond_false_stack);
502 void __negate_cond_stacks(void)
504 struct state_list *old_false, *old_true;
506 __use_cond_stack(&cond_false_stack);
507 old_false = pop_slist(&cond_false_stack);
508 old_true = pop_slist(&cond_true_stack);
509 push_slist(&cond_false_stack, old_true);
510 push_slist(&cond_true_stack, old_false);
513 void __and_cond_states(void)
515 and_slist_stack(&cond_true_stack);
516 or_slist_stack(&pre_cond_stack, cur_slist, &cond_false_stack);
519 void __or_cond_states(void)
521 or_slist_stack(&pre_cond_stack, cur_slist, &cond_true_stack);
522 and_slist_stack(&cond_false_stack);
525 void __save_pre_cond_states(void)
527 push_slist(&pre_cond_stack, clone_slist(cur_slist));
530 void __discard_pre_cond_states(void)
532 struct state_list *tmp;
534 tmp = pop_slist(&pre_cond_stack);
535 free_slist(&tmp);
538 void __use_cond_states(void)
540 struct state_list *pre, *pre_clone, *true_states, *false_states;
542 pre = pop_slist(&pre_cond_stack);
543 pre_clone = clone_slist(pre);
545 true_states = pop_slist(&cond_true_stack);
546 overwrite_slist(true_states, &pre);
547 /* we use the true states right away */
548 free_slist(&cur_slist);
549 cur_slist = pre;
551 false_states = pop_slist(&cond_false_stack);
552 overwrite_slist(false_states, &pre_clone);
553 push_slist(&false_stack, pre_clone);
556 void __push_true_states(void)
558 push_slist(&true_stack, clone_slist(cur_slist));
561 void __use_false_states(void)
563 free_slist(&cur_slist);
564 cur_slist = pop_slist(&false_stack);
567 void __discard_false_states(void)
569 struct state_list *slist;
571 slist = pop_slist(&false_stack);
572 free_slist(&slist);
575 void __merge_false_states(void)
577 struct state_list *slist;
579 slist = pop_slist(&false_stack);
580 merge_slist(&cur_slist, slist);
581 free_slist(&slist);
584 void __merge_true_states(void)
586 struct state_list *slist;
588 slist = pop_slist(&true_stack);
589 merge_slist(&cur_slist, slist);
590 free_slist(&slist);
593 void __push_continues(void)
595 push_slist(&continue_stack, NULL);
598 void __discard_continues(void)
600 struct state_list *slist;
602 slist = pop_slist(&continue_stack);
603 free_slist(&slist);
606 void __process_continues(void)
608 struct state_list *slist;
610 slist = pop_slist(&continue_stack);
611 if (!slist) {
612 slist = clone_slist(cur_slist);
613 } else {
614 merge_slist(&slist, cur_slist);
616 push_slist(&continue_stack, slist);
619 static int top_slist_empty(struct state_list_stack **stack)
621 struct state_list *tmp;
622 int empty = 0;
624 tmp = pop_slist(stack);
625 if (!tmp)
626 empty = 1;
627 push_slist(stack, tmp);
628 return empty;
631 /* a silly loop does this: while(i--) { return; } */
632 void __warn_on_silly_pre_loops(void)
634 if (!__path_is_null())
635 return;
636 if (!top_slist_empty(&continue_stack))
637 return;
638 if (!top_slist_empty(&break_stack))
639 return;
640 /* if the path was nullified before the loop, then we already
641 printed an error earlier */
642 if (top_slist_empty(&false_stack))
643 return;
644 sm_msg("info: loop could be replaced with if statement.");
647 void __merge_continues(void)
649 struct state_list *slist;
651 slist = pop_slist(&continue_stack);
652 merge_slist(&cur_slist, slist);
653 free_slist(&slist);
656 void __push_breaks(void)
658 push_slist(&break_stack, NULL);
661 void __process_breaks(void)
663 struct state_list *slist;
665 slist = pop_slist(&break_stack);
666 if (!slist) {
667 slist = clone_slist(cur_slist);
668 } else {
669 merge_slist(&slist, cur_slist);
671 push_slist(&break_stack, slist);
674 void __merge_breaks(void)
676 struct state_list *slist;
678 slist = pop_slist(&break_stack);
679 merge_slist(&cur_slist, slist);
680 free_slist(&slist);
683 void __use_breaks(void)
685 free_slist(&cur_slist);
686 cur_slist = pop_slist(&break_stack);
689 void __save_switch_states(struct expression *switch_expr)
691 push_range_list(&remaining_cases, __get_implied_values(switch_expr));
692 push_slist(&switch_stack, clone_slist(cur_slist));
695 void __merge_switches(struct expression *switch_expr, struct expression *case_expr)
697 struct state_list *slist;
698 struct state_list *implied_slist;
700 slist = pop_slist(&switch_stack);
701 implied_slist = __implied_case_slist(switch_expr, case_expr, &remaining_cases, &slist);
702 merge_slist(&cur_slist, implied_slist);
703 free_slist(&implied_slist);
704 push_slist(&switch_stack, slist);
707 void __discard_switches(void)
709 struct state_list *slist;
711 pop_range_list(&remaining_cases);
712 slist = pop_slist(&switch_stack);
713 free_slist(&slist);
716 void __push_default(void)
718 push_slist(&default_stack, NULL);
721 void __set_default(void)
723 set_state_stack(&default_stack, 0, "has_default", NULL, &true_state);
726 int __pop_default(void)
728 struct state_list *slist;
730 slist = pop_slist(&default_stack);
731 if (slist) {
732 free_slist(&slist);
733 return 1;
735 return 0;
738 static struct named_slist *alloc_named_slist(const char *name, struct state_list *slist)
740 struct named_slist *named_slist = __alloc_named_slist(0);
742 named_slist->name = (char *)name;
743 named_slist->slist = slist;
744 return named_slist;
747 void __save_gotos(const char *name)
749 struct state_list **slist;
750 struct state_list *clone;
752 slist = get_slist_from_named_stack(goto_stack, name);
753 if (slist) {
754 clone = clone_slist(cur_slist);
755 merge_slist(slist, clone);
756 free_slist(&clone);
757 return;
758 } else {
759 struct named_slist *named_slist;
761 clone = clone_slist(cur_slist);
762 named_slist = alloc_named_slist(name, clone);
763 add_ptr_list(&goto_stack, named_slist);
767 void __merge_gotos(const char *name)
769 struct state_list **slist;
771 slist = get_slist_from_named_stack(goto_stack, name);
772 if (slist)
773 merge_slist(&cur_slist, *slist);