buf_size, strlen: don't use strlen() to determine the buf size
[smatch.git] / smatch_implied.c
blob2d2352180bc79d027962b677a5654bba00593405
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. [stree %d]\n", s->name, show_state(s->state),
100 s->line, get_stree_id(s->pool));
101 } else if (isfalse) {
102 printf("'%s = %s' from %d is false. [stree %d]\n", s->name, show_state(s->state),
103 s->line, get_stree_id(s->pool));
104 } else {
105 printf("'%s = %s' from %d could be true or false. [stree %d]\n", s->name,
106 show_state(s->state), s->line, get_stree_id(s->pool));
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 void add_pool(struct stree_stack **pools, struct stree *new)
116 struct stree *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 stree_stack **true_stack,
138 struct stree_stack **false_stack)
140 struct sm_state *s;
141 int istrue;
142 int isfalse;
143 struct symbol *type;
144 struct range_list *var_rl;
146 if (!sm_state->pool)
147 return;
149 if (is_implied(sm_state)) {
150 s = get_sm_state_stree(sm_state->pool,
151 sm_state->owner, sm_state->name,
152 sm_state->sym);
153 } else {
154 s = sm_state;
157 if (!s) {
158 if (option_debug_implied || option_debug)
159 sm_msg("%s from %d, has borrowed implications.",
160 sm_state->name, sm_state->line);
161 return;
164 type = estate_type(sm_state->state);
165 if (type_positive_bits(rl_type(vals)) > type_positive_bits(type))
166 type = rl_type(vals);
167 if (type_positive_bits(type) < 31)
168 type = &int_ctype;
169 var_rl = cast_rl(type, estate_rl(s->state));
170 vals = cast_rl(type, vals);
172 if (lr == LEFT) {
173 istrue = !possibly_false_rl(var_rl, comparison, vals);
174 isfalse = !possibly_true_rl(var_rl, comparison, vals);
175 } else {
176 istrue = !possibly_false_rl(vals, comparison, var_rl);
177 isfalse = !possibly_true_rl(vals, comparison, var_rl);
180 print_debug_tf(s, istrue, isfalse);
182 if (istrue)
183 add_pool(true_stack, s->pool);
185 if (isfalse)
186 add_pool(false_stack, s->pool);
189 static int pool_in_pools(struct stree *pool,
190 struct stree_stack *pools)
192 struct stree *tmp;
194 FOR_EACH_PTR(pools, tmp) {
195 if (tmp == pool)
196 return 1;
197 if (tmp > pool)
198 return 0;
199 } END_FOR_EACH_PTR(tmp);
200 return 0;
203 static int is_checked(struct state_list *checked, struct sm_state *sm)
205 struct sm_state *tmp;
207 FOR_EACH_PTR(checked, tmp) {
208 if (tmp == sm)
209 return 1;
210 } END_FOR_EACH_PTR(tmp);
211 return 0;
215 * separate_pools():
216 * Example code: if (foo == 99) {
218 * Say 'foo' is a merged state that has many possible values. It is the combination
219 * of merges. separate_pools() iterates through the pools recursively and calls
220 * do_compare() for each time 'foo' was set.
222 static void separate_pools(struct sm_state *sm_state, int comparison, struct range_list *vals,
223 int lr,
224 struct stree_stack **true_stack,
225 struct stree_stack **false_stack,
226 struct state_list **checked)
228 int free_checked = 0;
229 struct state_list *checked_states = NULL;
231 if (!sm_state)
232 return;
235 Sometimes the implications are just too big to deal with
236 so we bail. Theoretically, bailing out here can cause more false
237 positives but won't hide actual bugs.
239 if (sm_state->nr_children > 4000) {
240 if (option_debug || option_debug_implied) {
241 static char buf[1028];
242 snprintf(buf, sizeof(buf), "debug: separate_pools: nr_children over 4000 (%d). (%s %s)",
243 sm_state->nr_children, sm_state->name, show_state(sm_state->state));
244 implied_debug_msg = buf;
246 return;
249 if (checked == NULL) {
250 checked = &checked_states;
251 free_checked = 1;
253 if (is_checked(*checked, sm_state))
254 return;
255 add_ptr_list(checked, sm_state);
257 do_compare(sm_state, comparison, vals, lr, true_stack, false_stack);
259 separate_pools(sm_state->left, comparison, vals, lr, true_stack, false_stack, checked);
260 separate_pools(sm_state->right, comparison, vals, lr, true_stack, false_stack, checked);
261 if (free_checked)
262 free_slist(checked);
265 struct sm_state *filter_pools(struct sm_state *sm,
266 struct stree_stack *remove_stack,
267 struct stree_stack *keep_stack,
268 int *modified)
270 struct sm_state *ret = NULL;
271 struct sm_state *left;
272 struct sm_state *right;
273 int removed = 0;
275 if (!sm)
276 return NULL;
278 if (sm->nr_children > 4000) {
279 if (option_debug || option_debug_implied) {
280 static char buf[1028];
281 snprintf(buf, sizeof(buf), "debug: %s: nr_children over 4000 (%d). (%s %s)",
282 __func__, sm->nr_children, sm->name, show_state(sm->state));
283 implied_debug_msg = buf;
285 return NULL;
288 if (pool_in_pools(sm->pool, remove_stack)) {
289 DIMPLIED("removed %s from %d [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
290 *modified = 1;
291 return NULL;
294 if (!is_merged(sm) || pool_in_pools(sm->pool, keep_stack)) {
295 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
296 return sm;
299 DIMPLIED("checking %s from %d (%d) [stree %d] left = %s [stree %d] right = %s [stree %d]\n",
300 show_sm(sm), sm->line, sm->nr_children, get_stree_id(sm->pool),
301 sm->left ? show_sm(sm->left) : "<none>", sm->left ? get_stree_id(sm->left->pool) : -1,
302 sm->right ? show_sm(sm->right) : "<none>", sm->right ? get_stree_id(sm->right->pool) : -1);
303 left = filter_pools(sm->left, remove_stack, keep_stack, &removed);
304 right = filter_pools(sm->right, remove_stack, keep_stack, &removed);
305 if (!removed) {
306 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
307 return sm;
309 *modified = 1;
310 if (!left && !right) {
311 DIMPLIED("removed %s from %d <none> [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
312 return NULL;
315 if (!left) {
316 ret = clone_sm(right);
317 ret->merged = 1;
318 ret->right = right;
319 ret->left = NULL;
320 ret->pool = sm->pool;
321 } else if (!right) {
322 ret = clone_sm(left);
323 ret->merged = 1;
324 ret->left = left;
325 ret->right = NULL;
326 ret->pool = sm->pool;
327 } else {
328 ret = merge_sm_states(left, right);
329 ret->pool = sm->pool;
331 ret->implied = 1;
332 DIMPLIED("partial %s => ", show_sm(sm));
333 DIMPLIED("%s from %d [stree %d]\n", show_sm(ret), sm->line, get_stree_id(sm->pool));
334 return ret;
337 static int highest_stree_id(struct sm_state *sm)
339 int left = 0;
340 int right = 0;
342 if (!sm->left && !sm->right)
343 return 0;
345 if (sm->left)
346 left = get_stree_id(sm->left->pool);
347 if (sm->right)
348 right = get_stree_id(sm->right->pool);
350 if (right > left)
351 return right;
352 return left;
355 static struct stree *filter_stack(struct sm_state *gate_sm,
356 struct stree *pre_stree,
357 struct stree_stack *remove_stack,
358 struct stree_stack *keep_stack)
360 struct stree *ret = NULL;
361 struct sm_state *tmp;
362 struct sm_state *filtered_sm;
363 int modified;
365 if (!remove_stack)
366 return NULL;
368 FOR_EACH_SM(pre_stree, tmp) {
369 if (highest_stree_id(tmp) < highest_stree_id(gate_sm)) {
370 DIMPLIED("skipping %s. set before. %d vs %d\n",
371 tmp->name, highest_stree_id(tmp),
372 highest_stree_id(gate_sm));
373 continue;
375 modified = 0;
376 filtered_sm = filter_pools(tmp, remove_stack, keep_stack, &modified);
377 if (filtered_sm && modified) {
378 /* the assignments here are for borrowed implications */
379 filtered_sm->name = tmp->name;
380 filtered_sm->sym = tmp->sym;
381 avl_insert(&ret, filtered_sm);
382 if (out_of_memory())
383 return NULL;
386 } END_FOR_EACH_SM(tmp);
387 return ret;
390 static void separate_and_filter(struct sm_state *sm_state, int comparison, struct range_list *vals,
391 int lr,
392 struct stree *pre_stree,
393 struct stree **true_states,
394 struct stree **false_states)
396 struct stree_stack *true_stack = NULL;
397 struct stree_stack *false_stack = NULL;
398 struct timeval time_before;
399 struct timeval time_after;
401 gettimeofday(&time_before, NULL);
403 if (!is_merged(sm_state)) {
404 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state->name);
405 return;
408 if (option_debug_implied || option_debug) {
409 if (lr == LEFT)
410 sm_msg("checking implications: (%s %s %s)",
411 sm_state->name, show_special(comparison), show_rl(vals));
412 else
413 sm_msg("checking implications: (%s %s %s)",
414 show_rl(vals), show_special(comparison), sm_state->name);
417 separate_pools(sm_state, comparison, vals, lr, &true_stack, &false_stack, NULL);
419 DIMPLIED("filtering true stack.\n");
420 *true_states = filter_stack(sm_state, pre_stree, false_stack, true_stack);
421 DIMPLIED("filtering false stack.\n");
422 *false_states = filter_stack(sm_state, pre_stree, true_stack, false_stack);
423 free_stree_stack(&true_stack);
424 free_stree_stack(&false_stack);
425 if (option_debug_implied || option_debug) {
426 printf("These are the implied states for the true path:\n");
427 __print_stree(*true_states);
428 printf("These are the implied states for the false path:\n");
429 __print_stree(*false_states);
432 gettimeofday(&time_after, NULL);
433 if (time_after.tv_sec - time_before.tv_sec > 7)
434 __bail_on_rest_of_function = 1;
437 static struct expression *get_left_most_expr(struct expression *expr)
439 expr = strip_expr(expr);
440 if (expr->type == EXPR_ASSIGNMENT)
441 return get_left_most_expr(expr->left);
442 return expr;
445 static int is_merged_expr(struct expression *expr)
447 struct sm_state *sm;
448 sval_t dummy;
450 if (get_value(expr, &dummy))
451 return 0;
452 sm = get_sm_state_expr(SMATCH_EXTRA, expr);
453 if (!sm)
454 return 0;
455 if (is_merged(sm))
456 return 1;
457 return 0;
460 static void delete_equiv_stree(struct stree **stree, const char *name, struct symbol *sym)
462 struct smatch_state *state;
463 struct relation *rel;
465 state = get_state(SMATCH_EXTRA, name, sym);
466 if (!estate_related(state)) {
467 delete_state_stree(stree, SMATCH_EXTRA, name, sym);
468 return;
471 FOR_EACH_PTR(estate_related(state), rel) {
472 delete_state_stree(stree, SMATCH_EXTRA, rel->name, rel->sym);
473 } END_FOR_EACH_PTR(rel);
476 static void handle_comparison(struct expression *expr,
477 struct stree **implied_true,
478 struct stree **implied_false)
480 struct sm_state *sm = NULL;
481 struct range_list *ranges = NULL;
482 struct expression *left;
483 struct expression *right;
484 int lr;
486 left = get_left_most_expr(expr->left);
487 right = get_left_most_expr(expr->right);
489 if (is_merged_expr(left)) {
490 lr = LEFT;
491 sm = get_sm_state_expr(SMATCH_EXTRA, left);
492 get_implied_rl(right, &ranges);
493 } else if (is_merged_expr(right)) {
494 lr = RIGHT;
495 sm = get_sm_state_expr(SMATCH_EXTRA, right);
496 get_implied_rl(left, &ranges);
499 if (!ranges || !sm) {
500 free_rl(&ranges);
501 return;
504 separate_and_filter(sm, expr->op, ranges, lr, __get_cur_stree(), implied_true, implied_false);
505 free_rl(&ranges);
506 delete_equiv_stree(implied_true, sm->name, sm->sym);
507 delete_equiv_stree(implied_false, sm->name, sm->sym);
510 static void handle_zero_comparison(struct expression *expr,
511 struct stree **implied_true,
512 struct stree **implied_false)
514 struct symbol *sym;
515 char *name;
516 struct sm_state *sm;
518 if (expr->type == EXPR_POSTOP)
519 expr = strip_expr(expr->unop);
521 if (expr->type == EXPR_ASSIGNMENT) {
522 /* most of the time ->pools will be empty here because we
523 just set the state, but if have assigned a conditional
524 function there are implications. */
525 expr = expr->left;
528 name = expr_to_var_sym(expr, &sym);
529 if (!name || !sym)
530 goto free;
531 sm = get_sm_state(SMATCH_EXTRA, name, sym);
532 if (!sm)
533 goto free;
535 separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(0), LEFT, __get_cur_stree(), implied_true, implied_false);
536 delete_equiv_stree(implied_true, name, sym);
537 delete_equiv_stree(implied_false, name, sym);
538 free:
539 free_string(name);
542 static int handled_by_implied_hook(struct expression *expr,
543 struct stree **implied_true,
544 struct stree **implied_false)
546 struct stree_stack *true_stack = NULL;
547 struct stree_stack *false_stack = NULL;
548 struct stree *pre_stree;
549 struct sm_state *sm;
551 sm = comparison_implication_hook(expr, &true_stack, &false_stack);
552 if (!sm)
553 sm = stored_condition_implication_hook(expr, &true_stack, &false_stack);
554 if (!sm)
555 return 0;
557 pre_stree = clone_stree(__get_cur_stree());
559 *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
560 *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
562 free_stree(&pre_stree);
563 free_stree_stack(&true_stack);
564 free_stree_stack(&false_stack);
566 return 1;
569 static void get_tf_states(struct expression *expr,
570 struct stree **implied_true,
571 struct stree **implied_false)
573 if (handled_by_implied_hook(expr, implied_true, implied_false))
574 return;
576 if (expr->type == EXPR_COMPARE)
577 handle_comparison(expr, implied_true, implied_false);
578 else
579 handle_zero_comparison(expr, implied_true, implied_false);
582 static struct stree *saved_implied_true;
583 static struct stree *saved_implied_false;
585 static void save_implications_hook(struct expression *expr)
587 if (option_no_implied)
588 return;
589 get_tf_states(expr, &saved_implied_true, &saved_implied_false);
592 static void set_implied_states(struct expression *expr)
594 struct sm_state *sm;
596 FOR_EACH_SM(saved_implied_true, sm) {
597 if (!get_state_stree(saved_implied_false, sm->owner, sm->name, sm->sym)) {
598 struct sm_state *orig;
600 orig = get_sm_state(sm->owner, sm->name, sm->sym);
601 set_state_stree(&saved_implied_false, sm->owner, sm->name, sm->sym, orig->state);
603 } END_FOR_EACH_SM(sm);
605 FOR_EACH_SM(saved_implied_false, sm) {
606 if (!get_state_stree(saved_implied_true, sm->owner, sm->name, sm->sym)) {
607 struct sm_state *orig;
609 orig = get_sm_state(sm->owner, sm->name, sm->sym);
610 set_state_stree(&saved_implied_true, sm->owner, sm->name, sm->sym, orig->state);
612 } END_FOR_EACH_SM(sm);
614 FOR_EACH_SM(saved_implied_true, sm) {
615 __set_true_false_sm(sm, NULL);
616 } END_FOR_EACH_SM(sm);
617 free_stree(&saved_implied_true);
619 FOR_EACH_SM(saved_implied_false, sm) {
620 __set_true_false_sm(NULL, sm);
621 } END_FOR_EACH_SM(sm);
622 free_stree(&saved_implied_false);
625 struct range_list *__get_implied_values(struct expression *switch_expr)
627 char *name;
628 struct symbol *sym;
629 struct smatch_state *state;
630 struct range_list *ret = NULL;
632 name = expr_to_var_sym(switch_expr, &sym);
633 if (!name || !sym)
634 goto free;
635 state = get_state(SMATCH_EXTRA, name, sym);
636 if (!state)
637 goto free;
638 ret = clone_rl(estate_rl(state));
639 free:
640 free_string(name);
641 if (!ret) {
642 struct symbol *type;
644 type = get_type(switch_expr);
645 ret = alloc_rl(sval_type_min(type), sval_type_max(type));
647 return ret;
650 struct stree *__implied_case_stree(struct expression *switch_expr,
651 struct expression *case_expr,
652 struct range_list_stack **remaining_cases,
653 struct stree **raw_stree)
655 char *name = NULL;
656 struct symbol *sym;
657 struct sm_state *sm;
658 struct stree *true_states = NULL;
659 struct stree *false_states = NULL;
660 struct stree *extra_states = NULL;
661 struct stree *ret = clone_stree(*raw_stree);
662 sval_t sval;
663 struct range_list *vals = NULL;
665 name = expr_to_var_sym(switch_expr, &sym);
666 if (!name || !sym)
667 goto free;
668 sm = get_sm_state_stree(*raw_stree, SMATCH_EXTRA, name, sym);
670 if (case_expr) {
671 if (get_value(case_expr, &sval)) {
672 filter_top_rl(remaining_cases, sval);
673 add_range(&vals, sval, sval);
674 } else {
675 vals = clone_rl(top_rl(*remaining_cases));
677 } else {
678 vals = top_rl(*remaining_cases);
681 if (sm)
682 separate_and_filter(sm, SPECIAL_EQUAL, vals, LEFT, *raw_stree, &true_states, &false_states);
684 __push_fake_cur_stree();
685 __unnullify_path();
686 set_extra_nomod(name, sym, alloc_estate_rl(vals));
687 extra_states = __pop_fake_cur_stree();
688 overwrite_stree(extra_states, &true_states);
689 overwrite_stree(true_states, &ret);
690 free_stree(&extra_states);
691 free_stree(&true_states);
692 free_stree(&false_states);
693 free:
694 free_string(name);
695 return ret;
698 static void match_end_func(struct symbol *sym)
700 if (__inline_fn)
701 return;
702 implied_debug_msg = NULL;
705 static int sm_state_in_slist(struct sm_state *sm, struct state_list *slist)
707 struct sm_state *tmp;
709 FOR_EACH_PTR(slist, tmp) {
710 if (tmp == sm)
711 return 1;
712 } END_FOR_EACH_PTR(tmp);
713 return 0;
717 * The situation is we have a SMATCH_EXTRA state and we want to break it into
718 * each of the ->possible states and find the implications of each. The caller
719 * has to use __push_fake_cur_stree() to preserve the correct states so they
720 * can be restored later.
722 void overwrite_states_using_pool(struct sm_state *sm)
724 struct sm_state *old;
725 struct sm_state *new;
727 if (!sm->pool)
728 return;
730 FOR_EACH_SM(sm->pool, old) {
731 new = get_sm_state(old->owner, old->name, old->sym);
732 if (!new) /* the variable went out of scope */
733 continue;
734 if (sm_state_in_slist(old, new->possible))
735 set_state(old->owner, old->name, old->sym, old->state);
736 } END_FOR_EACH_SM(old);
739 void __extra_match_condition(struct expression *expr);
740 void __comparison_match_condition(struct expression *expr);
741 void __stored_condition(struct expression *expr);
742 void register_implications(int id)
744 add_hook(&save_implications_hook, CONDITION_HOOK);
745 add_hook(&set_implied_states, CONDITION_HOOK);
746 add_hook(&__extra_match_condition, CONDITION_HOOK);
747 add_hook(&__comparison_match_condition, CONDITION_HOOK);
748 add_hook(&__stored_condition, CONDITION_HOOK);
749 add_hook(&match_end_func, END_FUNC_HOOK);