states: remove unused check_stack_free() function
[smatch.git] / smatch_implied.c
blobb5d4d3d5747a56d07097619fb666b1f79a5fda7b
1 /*
2 * Copyright (C) 2008 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 * Imagine we have this code:
20 * foo = 1;
21 * if (bar)
22 * foo = 99;
23 * else
24 * frob();
25 * // <-- point #1
26 * if (foo == 99) // <-- point #2
27 * bar->baz; // <-- point #3
30 * At point #3 bar is non null and can be dereferenced.
32 * It's smatch_implied.c which sets bar to non null at point #2.
34 * At point #1 merge_slist() stores the list of states from both
35 * the true and false paths. On the true path foo == 99 and on
36 * the false path foo == 1. merge_slist() sets their pool
37 * list to show the other states which were there when foo == 99.
39 * When it comes to the if (foo == 99) the smatch implied hook
40 * looks for all the pools where foo was not 99. It makes a list
41 * of those.
43 * Then for bar (and all the other states) it says, ok bar is a
44 * merged state that came from these previous states. We'll
45 * chop out all the states where it came from a pool where
46 * foo != 99 and merge it all back together.
48 * That is the implied state of bar.
50 * merge_slist() sets up ->pool. An sm_state only has one ->pool and
51 * that is the pool where it was first set. The my pool gets set when
52 * code paths merge. States that have been set since the last merge do
53 * not have a ->pool.
54 * merge_sm_state() sets ->left and ->right. (These are the states which were
55 * merged to form the current state.)
56 * a pool: a pool is an slist that has been merged with another slist.
59 #include <sys/time.h>
60 #include <time.h>
61 #include "smatch.h"
62 #include "smatch_slist.h"
63 #include "smatch_extra.h"
65 char *implied_debug_msg;
66 #define DIMPLIED(msg...) do { if (option_debug_implied) printf(msg); } while (0)
68 int option_debug_implied = 0;
69 int option_no_implied = 0;
71 #define RIGHT 0
72 #define LEFT 1
75 * tmp_range_list():
76 * It messes things up to free range list allocations. This helper fuction
77 * lets us reuse memory instead of doing new allocations.
79 static struct range_list *tmp_range_list(long long num)
81 static struct range_list *my_list = NULL;
82 static struct data_range *my_range;
84 __free_ptr_list((struct ptr_list **)&my_list);
85 my_range = alloc_range(ll_to_sval(num), ll_to_sval(num));
86 add_ptr_list(&my_list, my_range);
87 return my_list;
90 static void print_debug_tf(struct sm_state *s, int istrue, int isfalse)
92 if (!option_debug_implied && !option_debug)
93 return;
95 if (istrue && isfalse) {
96 printf("'%s = %s' from %d does not exist.\n", s->name,
97 show_state(s->state), s->line);
98 } else if (istrue) {
99 printf("'%s = %s' from %d is true.\n", s->name, show_state(s->state),
100 s->line);
101 } else if (isfalse) {
102 printf("'%s = %s' from %d is false.\n", s->name, show_state(s->state),
103 s->line);
104 } else {
105 printf("'%s = %s' from %d could be true or false.\n", s->name,
106 show_state(s->state), s->line);
111 * add_pool() adds a slist to *pools. If the slist has already been
112 * added earlier then it doesn't get added a second time.
114 static void add_pool(struct state_list_stack **pools, struct state_list *new)
116 struct state_list *tmp;
118 FOR_EACH_PTR(*pools, tmp) {
119 if (tmp < new)
120 continue;
121 else if (tmp == new) {
122 return;
123 } else {
124 INSERT_CURRENT(new, tmp);
125 return;
127 } END_FOR_EACH_PTR(tmp);
128 add_ptr_list(pools, new);
132 * If 'foo' == 99 add it that pool to the true pools. If it's false, add it to
133 * the false pools. If we're not sure, then we don't add it to either.
135 static void do_compare(struct sm_state *sm_state, int comparison, struct range_list *vals,
136 int lr,
137 struct state_list_stack **true_stack,
138 struct state_list_stack **false_stack)
140 struct sm_state *s;
141 int istrue;
142 int isfalse;
144 if (!sm_state->pool)
145 return;
147 if (is_implied(sm_state)) {
148 s = get_sm_state_slist(sm_state->pool,
149 sm_state->owner, sm_state->name,
150 sm_state->sym);
151 } else {
152 s = sm_state;
155 if (!s) {
156 if (option_debug_implied || option_debug)
157 sm_msg("%s from %d, has borrowed implications.",
158 sm_state->name, sm_state->line);
159 return;
162 if (lr == LEFT) {
163 istrue = !possibly_false_rl(estate_rl(s->state), comparison, vals);
164 isfalse = !possibly_true_rl(estate_rl(s->state), comparison, vals);
165 } else {
166 istrue = !possibly_false_rl(vals, comparison, estate_rl(s->state));
167 isfalse = !possibly_true_rl(vals, comparison, estate_rl(s->state));
170 print_debug_tf(s, istrue, isfalse);
172 if (istrue)
173 add_pool(true_stack, s->pool);
175 if (isfalse)
176 add_pool(false_stack, s->pool);
179 static int pool_in_pools(struct state_list *pool,
180 struct state_list_stack *pools)
182 struct state_list *tmp;
184 FOR_EACH_PTR(pools, tmp) {
185 if (tmp == pool)
186 return 1;
187 if (tmp > pool)
188 return 0;
189 } END_FOR_EACH_PTR(tmp);
190 return 0;
193 static int is_checked(struct state_list *checked, struct sm_state *sm)
195 struct sm_state *tmp;
197 FOR_EACH_PTR(checked, tmp) {
198 if (tmp == sm)
199 return 1;
200 } END_FOR_EACH_PTR(tmp);
201 return 0;
205 * separate_pools():
206 * Example code: if (foo == 99) {
208 * Say 'foo' is a merged state that has many possible values. It is the combination
209 * of merges. separate_pools() iterates through the pools recursively and calls
210 * do_compare() for each time 'foo' was set.
212 static void separate_pools(struct sm_state *sm_state, int comparison, struct range_list *vals,
213 int lr,
214 struct state_list_stack **true_stack,
215 struct state_list_stack **false_stack,
216 struct state_list **checked)
218 int free_checked = 0;
219 struct state_list *checked_states = NULL;
221 if (!sm_state)
222 return;
225 Sometimes the implications are just too big to deal with
226 so we bail. Theoretically, bailing out here can cause more false
227 positives but won't hide actual bugs.
229 if (sm_state->nr_children > 4000) {
230 static char buf[1028];
231 snprintf(buf, sizeof(buf), "debug: separate_pools: nr_children over 4000 (%d). (%s %s)",
232 sm_state->nr_children, sm_state->name, show_state(sm_state->state));
233 implied_debug_msg = buf;
234 return;
237 if (checked == NULL) {
238 checked = &checked_states;
239 free_checked = 1;
241 if (is_checked(*checked, sm_state))
242 return;
243 add_ptr_list(checked, sm_state);
245 do_compare(sm_state, comparison, vals, lr, true_stack, false_stack);
247 separate_pools(sm_state->left, comparison, vals, lr, true_stack, false_stack, checked);
248 separate_pools(sm_state->right, comparison, vals, lr, true_stack, false_stack, checked);
249 if (free_checked)
250 free_slist(checked);
253 struct sm_state *remove_pools(struct sm_state *sm,
254 struct state_list_stack *pools, int *modified)
256 struct sm_state *ret = NULL;
257 struct sm_state *left;
258 struct sm_state *right;
259 int removed = 0;
261 if (!sm)
262 return NULL;
264 if (sm->nr_children > 4000) {
265 static char buf[1028];
266 snprintf(buf, sizeof(buf), "debug: remove_pools: nr_children over 4000 (%d). (%s %s)",
267 sm->nr_children, sm->name, show_state(sm->state));
268 implied_debug_msg = buf;
269 return NULL;
272 if (pool_in_pools(sm->pool, pools)) {
273 DIMPLIED("removed %s from %d\n", show_sm(sm), sm->line);
274 *modified = 1;
275 return NULL;
278 if (!is_merged(sm)) {
279 DIMPLIED("kept %s from %d\n", show_sm(sm), sm->line);
280 return sm;
283 DIMPLIED("checking %s from %d (%d)\n", show_sm(sm), sm->line, sm->nr_children);
284 left = remove_pools(sm->left, pools, &removed);
285 right = remove_pools(sm->right, pools, &removed);
286 if (!removed) {
287 DIMPLIED("kept %s from %d\n", show_sm(sm), sm->line);
288 return sm;
290 *modified = 1;
291 if (!left && !right) {
292 DIMPLIED("removed %s from %d <none>\n", show_sm(sm), sm->line);
293 return NULL;
296 if (!left) {
297 ret = clone_sm(right);
298 ret->merged = 1;
299 ret->right = right;
300 ret->left = NULL;
301 ret->pool = sm->pool;
302 } else if (!right) {
303 ret = clone_sm(left);
304 ret->merged = 1;
305 ret->left = left;
306 ret->right = NULL;
307 ret->pool = sm->pool;
308 } else {
309 ret = merge_sm_states(left, right);
310 ret->pool = sm->pool;
312 ret->implied = 1;
313 DIMPLIED("partial %s => ", show_sm(sm));
314 DIMPLIED("%s from %d\n", show_sm(ret), sm->line);
315 return ret;
318 static int highest_slist_id(struct sm_state *sm)
320 int left = 0;
321 int right = 0;
323 if (!sm->left && !sm->right)
324 return 0;
326 if (sm->left)
327 left = get_slist_id(sm->left->pool);
328 if (sm->right)
329 right = get_slist_id(sm->right->pool);
331 if (right > left)
332 return right;
333 return left;
336 static struct state_list *filter_stack(struct sm_state *gate_sm,
337 struct state_list *pre_list,
338 struct state_list_stack *stack)
340 struct state_list *ret = NULL;
341 struct sm_state *tmp;
342 struct sm_state *filtered_sm;
343 int modified;
345 if (!stack)
346 return NULL;
348 FOR_EACH_PTR(pre_list, tmp) {
349 if (highest_slist_id(tmp) < highest_slist_id(gate_sm)) {
350 DIMPLIED("skipping %s. set before. %d vs %d",
351 tmp->name, highest_slist_id(tmp),
352 highest_slist_id(gate_sm));
353 continue;
355 modified = 0;
356 filtered_sm = remove_pools(tmp, stack, &modified);
357 if (filtered_sm && modified) {
358 filtered_sm->name = tmp->name;
359 filtered_sm->sym = tmp->sym;
360 add_ptr_list(&ret, filtered_sm);
361 if (out_of_memory())
362 return NULL;
365 } END_FOR_EACH_PTR(tmp);
366 return ret;
369 static void separate_and_filter(struct sm_state *sm_state, int comparison, struct range_list *vals,
370 int lr,
371 struct state_list *pre_list,
372 struct state_list **true_states,
373 struct state_list **false_states)
375 struct state_list_stack *true_stack = NULL;
376 struct state_list_stack *false_stack = NULL;
377 struct timeval time_before;
378 struct timeval time_after;
380 gettimeofday(&time_before, NULL);
382 if (!is_merged(sm_state)) {
383 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state->name);
384 return;
387 if (option_debug_implied || option_debug) {
388 if (lr == LEFT)
389 sm_msg("checking implications: (%s %s %s)",
390 sm_state->name, show_special(comparison), show_rl(vals));
391 else
392 sm_msg("checking implications: (%s %s %s)",
393 show_rl(vals), show_special(comparison), sm_state->name);
396 separate_pools(sm_state, comparison, vals, lr, &true_stack, &false_stack, NULL);
398 DIMPLIED("filtering true stack.\n");
399 *true_states = filter_stack(sm_state, pre_list, false_stack);
400 DIMPLIED("filtering false stack.\n");
401 *false_states = filter_stack(sm_state, pre_list, true_stack);
402 free_stack(&true_stack);
403 free_stack(&false_stack);
404 if (option_debug_implied || option_debug) {
405 printf("These are the implied states for the true path:\n");
406 __print_slist(*true_states);
407 printf("These are the implied states for the false path:\n");
408 __print_slist(*false_states);
411 gettimeofday(&time_after, NULL);
412 if (time_after.tv_sec - time_before.tv_sec > 7)
413 __bail_on_rest_of_function = 1;
416 static struct expression *get_left_most_expr(struct expression *expr)
418 expr = strip_expr(expr);
419 if (expr->type == EXPR_ASSIGNMENT)
420 return get_left_most_expr(expr->left);
421 return expr;
424 static int is_merged_expr(struct expression *expr)
426 struct sm_state *sm;
427 sval_t dummy;
429 if (get_value(expr, &dummy))
430 return 0;
431 sm = get_sm_state_expr(SMATCH_EXTRA, expr);
432 if (!sm)
433 return 0;
434 if (is_merged(sm))
435 return 1;
436 return 0;
439 static void delete_equiv_slist(struct state_list **slist, const char *name, struct symbol *sym)
441 struct smatch_state *state;
442 struct relation *rel;
444 state = get_state(SMATCH_EXTRA, name, sym);
445 if (!estate_related(state)) {
446 delete_state_slist(slist, SMATCH_EXTRA, name, sym);
447 return;
450 FOR_EACH_PTR(estate_related(state), rel) {
451 delete_state_slist(slist, SMATCH_EXTRA, rel->name, rel->sym);
452 } END_FOR_EACH_PTR(rel);
455 static void handle_comparison(struct expression *expr,
456 struct state_list **implied_true,
457 struct state_list **implied_false)
459 struct sm_state *sm = NULL;
460 struct range_list *ranges = NULL;
461 struct expression *left;
462 struct expression *right;
463 int lr;
465 left = get_left_most_expr(expr->left);
466 right = get_left_most_expr(expr->right);
468 if (is_merged_expr(left)) {
469 lr = LEFT;
470 sm = get_sm_state_expr(SMATCH_EXTRA, left);
471 get_implied_rl(right, &ranges);
472 } else if (is_merged_expr(right)) {
473 lr = RIGHT;
474 sm = get_sm_state_expr(SMATCH_EXTRA, right);
475 get_implied_rl(left, &ranges);
478 if (!ranges || !sm) {
479 free_rl(&ranges);
480 return;
483 separate_and_filter(sm, expr->op, ranges, lr, __get_cur_slist(), implied_true, implied_false);
484 free_rl(&ranges);
485 delete_equiv_slist(implied_true, sm->name, sm->sym);
486 delete_equiv_slist(implied_false, sm->name, sm->sym);
489 static void handle_zero_comparison(struct expression *expr,
490 struct state_list **implied_true,
491 struct state_list **implied_false)
493 struct symbol *sym;
494 char *name;
495 struct sm_state *sm;
497 if (expr->type == EXPR_POSTOP)
498 expr = strip_expr(expr->unop);
500 if (expr->type == EXPR_ASSIGNMENT) {
501 /* most of the time ->pools will be empty here because we
502 just set the state, but if have assigned a conditional
503 function there are implications. */
504 expr = expr->left;
507 name = expr_to_var_sym(expr, &sym);
508 if (!name || !sym)
509 goto free;
510 sm = get_sm_state(SMATCH_EXTRA, name, sym);
511 if (!sm)
512 goto free;
514 separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(0), LEFT, __get_cur_slist(), implied_true, implied_false);
515 delete_equiv_slist(implied_true, name, sym);
516 delete_equiv_slist(implied_false, name, sym);
517 free:
518 free_string(name);
521 static void get_tf_states(struct expression *expr,
522 struct state_list **implied_true,
523 struct state_list **implied_false)
525 if (expr->type == EXPR_COMPARE)
526 handle_comparison(expr, implied_true, implied_false);
527 else
528 handle_zero_comparison(expr, implied_true, implied_false);
531 static void implied_states_hook(struct expression *expr)
533 struct sm_state *sm;
534 struct state_list *implied_true = NULL;
535 struct state_list *implied_false = NULL;
537 if (option_no_implied)
538 return;
540 get_tf_states(expr, &implied_true, &implied_false);
542 FOR_EACH_PTR(implied_true, sm) {
543 __set_true_false_sm(sm, NULL);
544 } END_FOR_EACH_PTR(sm);
545 free_slist(&implied_true);
547 FOR_EACH_PTR(implied_false, sm) {
548 __set_true_false_sm(NULL, sm);
549 } END_FOR_EACH_PTR(sm);
550 free_slist(&implied_false);
553 struct range_list *__get_implied_values(struct expression *switch_expr)
555 char *name;
556 struct symbol *sym;
557 struct smatch_state *state;
558 struct range_list *ret = NULL;
560 name = expr_to_var_sym(switch_expr, &sym);
561 if (!name || !sym)
562 goto free;
563 state = get_state(SMATCH_EXTRA, name, sym);
564 if (!state)
565 goto free;
566 ret = clone_rl(estate_rl(state));
567 free:
568 free_string(name);
569 if (!ret) {
570 struct symbol *type;
572 type = get_type(switch_expr);
573 ret = alloc_rl(sval_type_min(type), sval_type_max(type));
575 return ret;
578 struct state_list *__implied_case_slist(struct expression *switch_expr,
579 struct expression *case_expr,
580 struct range_list_stack **remaining_cases,
581 struct AVL **raw_stree)
583 char *name = NULL;
584 struct symbol *sym;
585 struct sm_state *sm;
586 struct state_list *true_states = NULL;
587 struct state_list *false_states = NULL;
588 struct state_list *extra_states = NULL;
589 struct state_list *ret = clone_slist(stree_to_slist(*raw_stree));
590 sval_t sval;
591 struct range_list *vals = NULL;
593 name = expr_to_var_sym(switch_expr, &sym);
594 if (!name || !sym)
595 goto free;
596 sm = get_sm_state_stree(*raw_stree, SMATCH_EXTRA, name, sym);
598 if (case_expr) {
599 if (get_value(case_expr, &sval)) {
600 filter_top_rl(remaining_cases, sval);
601 add_range(&vals, sval, sval);
602 } else {
603 vals = clone_rl(top_rl(*remaining_cases));
605 } else {
606 vals = top_rl(*remaining_cases);
609 if (sm)
610 separate_and_filter(sm, SPECIAL_EQUAL, vals, LEFT, stree_to_slist(*raw_stree), &true_states, &false_states);
612 __push_fake_cur_slist();
613 __unnullify_path();
614 set_extra_nomod(name, sym, alloc_estate_rl(vals));
615 extra_states = stree_to_slist(__pop_fake_cur_slist());
616 overwrite_slist(extra_states, &true_states);
617 overwrite_slist(true_states, &ret);
618 free_slist(&extra_states);
619 free_slist(&true_states);
620 free_slist(&false_states);
621 free:
622 free_string(name);
623 return ret;
626 static void match_end_func(struct symbol *sym)
628 if (__inline_fn)
629 return;
630 implied_debug_msg = NULL;
633 static int sm_state_in_slist(struct sm_state *sm, struct state_list *slist)
635 struct sm_state *tmp;
637 FOR_EACH_PTR(slist, tmp) {
638 if (tmp == sm)
639 return 1;
640 } END_FOR_EACH_PTR(tmp);
641 return 0;
645 * The situation is we have a SMATCH_EXTRA state and we want to break it into
646 * each of the ->possible states and find the implications of each. The caller
647 * has to use __push_fake_cur_slist() to preserve the correct states so they
648 * can be restored later.
650 void overwrite_states_using_pool(struct sm_state *sm)
652 struct sm_state *old;
653 struct sm_state *new;
655 if (!sm->pool)
656 return;
658 FOR_EACH_PTR(sm->pool, old) {
659 new = get_sm_state(old->owner, old->name, old->sym);
660 if (!new) /* the variable went out of scope */
661 continue;
662 if (sm_state_in_slist(old, new->possible))
663 set_state(old->owner, old->name, old->sym, old->state);
664 } END_FOR_EACH_PTR(old);
667 void __extra_match_condition(struct expression *expr);
668 void register_implications(int id)
670 add_hook(&implied_states_hook, CONDITION_HOOK);
671 add_hook(&__extra_match_condition, CONDITION_HOOK);
672 add_hook(&match_end_func, END_FUNC_HOOK);