sval: make sval_cast() take a type
[smatch.git] / smatch_implied.c
blobe8781ecfb151229d982caec8ad603a047588d4dc
1 /*
2 * sparse/smatch_implied.c
4 * Copyright (C) 2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
11 * Imagine we have this code:
12 * foo = 1;
13 * if (bar)
14 * foo = 99;
15 * else
16 * frob();
17 * // <-- point #1
18 * if (foo == 99) // <-- point #2
19 * bar->baz; // <-- point #3
22 * At point #3 bar is non null and can be dereferenced.
24 * It's smatch_implied.c which sets bar to non null at point #2.
26 * At point #1 merge_slist() stores the list of states from both
27 * the true and false paths. On the true path foo == 99 and on
28 * the false path foo == 1. merge_slist() sets their pool
29 * list to show the other states which were there when foo == 99.
31 * When it comes to the if (foo == 99) the smatch implied hook
32 * looks for all the pools where foo was not 99. It makes a list
33 * of those.
35 * Then for bar (and all the other states) it says, ok bar is a
36 * merged state that came from these previous states. We'll
37 * chop out all the states where it came from a pool where
38 * foo != 99 and merge it all back together.
40 * That is the implied state of bar.
42 * merge_slist() sets up ->pool. An sm_state only has one ->pool and
43 * that is the pool where it was first set. The my pool gets set when
44 * code paths merge. States that have been set since the last merge do
45 * not have a ->pool.
46 * merge_sm_state() sets ->left and ->right. (These are the states which were
47 * merged to form the current state.)
48 * a pool: a pool is an slist that has been merged with another slist.
51 #include <sys/time.h>
52 #include <time.h>
53 #include "smatch.h"
54 #include "smatch_slist.h"
55 #include "smatch_extra.h"
57 char *implied_debug_msg;
58 #define DIMPLIED(msg...) do { if (option_debug_implied) printf(msg); } while (0)
60 int option_debug_implied = 0;
61 int option_no_implied = 0;
63 #define RIGHT 0
64 #define LEFT 1
67 * tmp_range_list():
68 * It messes things up to free range list allocations. This helper fuction
69 * lets us reuse memory instead of doing new allocations.
71 static struct range_list_sval *tmp_range_list(long long num)
73 static struct range_list_sval *my_list = NULL;
74 static struct data_range_sval *my_range;
76 __free_ptr_list((struct ptr_list **)&my_list);
77 my_range = alloc_range_sval(ll_to_sval(num), ll_to_sval(num));
78 add_ptr_list(&my_list, my_range);
79 return my_list;
82 static void print_debug_tf(struct sm_state *s, int istrue, int isfalse)
84 if (!option_debug_implied && !option_debug)
85 return;
87 if (istrue && isfalse) {
88 printf("'%s = %s' from %d does not exist.\n", s->name,
89 show_state(s->state), s->line);
90 } else if (istrue) {
91 printf("'%s = %s' from %d is true.\n", s->name, show_state(s->state),
92 s->line);
93 } else if (isfalse) {
94 printf("'%s = %s' from %d is false.\n", s->name, show_state(s->state),
95 s->line);
96 } else {
97 printf("'%s = %s' from %d could be true or false.\n", s->name,
98 show_state(s->state), s->line);
103 * add_pool() adds a slist to *pools. If the slist has already been
104 * added earlier then it doesn't get added a second time.
106 static void add_pool(struct state_list_stack **pools, struct state_list *new)
108 struct state_list *tmp;
110 FOR_EACH_PTR(*pools, tmp) {
111 if (tmp < new)
112 continue;
113 else if (tmp == new) {
114 return;
115 } else {
116 INSERT_CURRENT(new, tmp);
117 return;
119 } END_FOR_EACH_PTR(tmp);
120 add_ptr_list(pools, new);
124 * If 'foo' == 99 add it that pool to the true pools. If it's false, add it to
125 * the false pools. If we're not sure, then we don't add it to either.
127 static void do_compare(struct sm_state *sm_state, int comparison, struct range_list_sval *vals,
128 int lr,
129 struct state_list_stack **true_stack,
130 struct state_list_stack **false_stack)
132 struct sm_state *s;
133 int istrue;
134 int isfalse;
136 if (!sm_state->pool)
137 return;
139 if (is_implied(sm_state)) {
140 s = get_sm_state_slist(sm_state->pool,
141 sm_state->owner, sm_state->name,
142 sm_state->sym);
143 } else {
144 s = sm_state;
147 if (!s) {
148 if (option_debug_implied || option_debug)
149 sm_msg("%s from %d, has borrowed implications.",
150 sm_state->name, sm_state->line);
151 return;
154 if (lr == LEFT) {
155 istrue = !possibly_false_range_lists_sval(estate_ranges_sval(s->state), comparison, vals);
156 isfalse = !possibly_true_range_lists_sval(estate_ranges_sval(s->state), comparison, vals);
157 } else {
158 istrue = !possibly_false_range_lists_sval(vals, comparison, estate_ranges_sval(s->state));
159 isfalse = !possibly_true_range_lists_sval(vals, comparison, estate_ranges_sval(s->state));
162 print_debug_tf(s, istrue, isfalse);
164 if (istrue)
165 add_pool(true_stack, s->pool);
167 if (isfalse)
168 add_pool(false_stack, s->pool);
171 static int pool_in_pools(struct state_list *pool,
172 struct state_list_stack *pools)
174 struct state_list *tmp;
176 FOR_EACH_PTR(pools, tmp) {
177 if (tmp == pool)
178 return 1;
179 if (tmp > pool)
180 return 0;
181 } END_FOR_EACH_PTR(tmp);
182 return 0;
185 static int is_checked(struct state_list *checked, struct sm_state *sm)
187 struct sm_state *tmp;
189 FOR_EACH_PTR(checked, tmp) {
190 if (tmp == sm)
191 return 1;
192 } END_FOR_EACH_PTR(tmp);
193 return 0;
197 * separate_pools():
198 * Example code: if (foo == 99) {
200 * Say 'foo' is a merged state that has many possible values. It is the combination
201 * of merges. separate_pools() iterates through the pools recursively and calls
202 * do_compare() for each time 'foo' was set.
204 static void separate_pools(struct sm_state *sm_state, int comparison, struct range_list_sval *vals,
205 int lr,
206 struct state_list_stack **true_stack,
207 struct state_list_stack **false_stack,
208 struct state_list **checked)
210 int free_checked = 0;
211 struct state_list *checked_states = NULL;
213 if (!sm_state)
214 return;
217 Sometimes the implications are just too big to deal with
218 so we bail. Theoretically, bailing out here can cause more false
219 positives but won't hide actual bugs.
221 if (sm_state->nr_children > 4000) {
222 static char buf[1028];
223 snprintf(buf, sizeof(buf), "debug: separate_pools: nr_children over 4000 (%d). (%s %s)",
224 sm_state->nr_children, sm_state->name, show_state(sm_state->state));
225 implied_debug_msg = buf;
226 return;
229 if (checked == NULL) {
230 checked = &checked_states;
231 free_checked = 1;
233 if (is_checked(*checked, sm_state))
234 return;
235 add_ptr_list(checked, sm_state);
237 do_compare(sm_state, comparison, vals, lr, true_stack, false_stack);
239 separate_pools(sm_state->left, comparison, vals, lr, true_stack, false_stack, checked);
240 separate_pools(sm_state->right, comparison, vals, lr, true_stack, false_stack, checked);
241 if (free_checked)
242 free_slist(checked);
245 struct sm_state *remove_pools(struct sm_state *sm,
246 struct state_list_stack *pools, int *modified)
248 struct sm_state *ret = NULL;
249 struct sm_state *left;
250 struct sm_state *right;
251 int removed = 0;
253 if (!sm)
254 return NULL;
256 if (sm->nr_children > 4000) {
257 static char buf[1028];
258 snprintf(buf, sizeof(buf), "debug: remove_pools: nr_children over 4000 (%d). (%s %s)",
259 sm->nr_children, sm->name, show_state(sm->state));
260 implied_debug_msg = buf;
261 return NULL;
264 if (pool_in_pools(sm->pool, pools)) {
265 DIMPLIED("removed %s from %d\n", show_sm(sm), sm->line);
266 *modified = 1;
267 return NULL;
270 if (!is_merged(sm)) {
271 DIMPLIED("kept %s from %d\n", show_sm(sm), sm->line);
272 return sm;
275 DIMPLIED("checking %s from %d (%d)\n", show_sm(sm), sm->line, sm->nr_children);
276 left = remove_pools(sm->left, pools, &removed);
277 right = remove_pools(sm->right, pools, &removed);
278 if (!removed) {
279 DIMPLIED("kept %s from %d\n", show_sm(sm), sm->line);
280 return sm;
282 *modified = 1;
283 if (!left && !right) {
284 DIMPLIED("removed %s from %d <none>\n", show_sm(sm), sm->line);
285 return NULL;
288 if (!left) {
289 ret = clone_sm(right);
290 ret->merged = 1;
291 ret->right = right;
292 ret->left = NULL;
293 ret->pool = sm->pool;
294 } else if (!right) {
295 ret = clone_sm(left);
296 ret->merged = 1;
297 ret->left = left;
298 ret->right = NULL;
299 ret->pool = sm->pool;
300 } else {
301 ret = merge_sm_states(left, right);
302 ret->pool = sm->pool;
304 ret->implied = 1;
305 DIMPLIED("partial %s => ", show_sm(sm));
306 DIMPLIED("%s from %d\n", show_sm(ret), sm->line);
307 return ret;
310 static int highest_slist_id(struct sm_state *sm)
312 int left = 0;
313 int right = 0;
315 if (!sm->left && !sm->right)
316 return 0;
318 if (sm->left)
319 left = get_slist_id(sm->left->pool);
320 if (sm->right)
321 right = get_slist_id(sm->right->pool);
323 if (right > left)
324 return right;
325 return left;
328 static struct state_list *filter_stack(struct sm_state *gate_sm,
329 struct state_list *pre_list,
330 struct state_list_stack *stack)
332 struct state_list *ret = NULL;
333 struct sm_state *tmp;
334 struct sm_state *filtered_sm;
335 int modified;
337 if (!stack)
338 return NULL;
340 FOR_EACH_PTR(pre_list, tmp) {
341 if (highest_slist_id(tmp) < highest_slist_id(gate_sm)) {
342 DIMPLIED("skipping %s. set before. %d vs %d",
343 tmp->name, highest_slist_id(tmp),
344 highest_slist_id(gate_sm));
345 continue;
347 modified = 0;
348 filtered_sm = remove_pools(tmp, stack, &modified);
349 if (filtered_sm && modified) {
350 filtered_sm->name = tmp->name;
351 filtered_sm->sym = tmp->sym;
352 add_ptr_list(&ret, filtered_sm);
353 if (out_of_memory())
354 return NULL;
357 } END_FOR_EACH_PTR(tmp);
358 return ret;
361 static void separate_and_filter(struct sm_state *sm_state, int comparison, struct range_list_sval *vals,
362 int lr,
363 struct state_list *pre_list,
364 struct state_list **true_states,
365 struct state_list **false_states)
367 struct state_list_stack *true_stack = NULL;
368 struct state_list_stack *false_stack = NULL;
369 struct timeval time_before;
370 struct timeval time_after;
372 gettimeofday(&time_before, NULL);
374 if (!is_merged(sm_state)) {
375 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state->name);
376 return;
379 if (option_debug_implied || option_debug) {
380 if (lr == LEFT)
381 sm_msg("checking implications: (%s %s %s)",
382 sm_state->name, show_special(comparison), show_ranges_sval(vals));
383 else
384 sm_msg("checking implications: (%s %s %s)",
385 show_ranges_sval(vals), show_special(comparison), sm_state->name);
388 separate_pools(sm_state, comparison, vals, lr, &true_stack, &false_stack, NULL);
390 DIMPLIED("filtering true stack.\n");
391 *true_states = filter_stack(sm_state, pre_list, false_stack);
392 DIMPLIED("filtering false stack.\n");
393 *false_states = filter_stack(sm_state, pre_list, true_stack);
394 free_stack(&true_stack);
395 free_stack(&false_stack);
396 if (option_debug_implied || option_debug) {
397 printf("These are the implied states for the true path:\n");
398 __print_slist(*true_states);
399 printf("These are the implied states for the false path:\n");
400 __print_slist(*false_states);
403 gettimeofday(&time_after, NULL);
404 if (time_after.tv_sec - time_before.tv_sec > 7)
405 __bail_on_rest_of_function = 1;
408 static struct expression *get_left_most_expr(struct expression *expr)
410 expr = strip_expr(expr);
411 if (expr->type == EXPR_ASSIGNMENT)
412 return get_left_most_expr(expr->left);
413 return expr;
416 static int is_merged_expr(struct expression *expr)
418 struct sm_state *sm;
419 sval_t dummy;
421 if (get_value_sval(expr, &dummy))
422 return 0;
423 sm = get_sm_state_expr(SMATCH_EXTRA, expr);
424 if (!sm)
425 return 0;
426 if (is_merged(sm))
427 return 1;
428 return 0;
431 static void delete_equiv_slist(struct state_list **slist, const char *name, struct symbol *sym)
433 struct smatch_state *state;
434 struct relation *rel;
436 state = get_state(SMATCH_EXTRA, name, sym);
437 if (!estate_related(state)) {
438 delete_state_slist(slist, SMATCH_EXTRA, name, sym);
439 return;
442 FOR_EACH_PTR(estate_related(state), rel) {
443 delete_state_slist(slist, SMATCH_EXTRA, rel->name, rel->sym);
444 } END_FOR_EACH_PTR(rel);
447 static void handle_comparison(struct expression *expr,
448 struct state_list **implied_true,
449 struct state_list **implied_false)
451 struct sm_state *sm = NULL;
452 struct range_list_sval *ranges = NULL;
453 struct expression *left;
454 struct expression *right;
455 int lr;
457 left = get_left_most_expr(expr->left);
458 right = get_left_most_expr(expr->right);
460 if (is_merged_expr(left)) {
461 lr = LEFT;
462 sm = get_sm_state_expr(SMATCH_EXTRA, left);
463 get_implied_range_list_sval(right, &ranges);
464 } else if (is_merged_expr(right)) {
465 lr = RIGHT;
466 sm = get_sm_state_expr(SMATCH_EXTRA, right);
467 get_implied_range_list_sval(left, &ranges);
470 if (!ranges || !sm) {
471 free_range_list_sval(&ranges);
472 return;
475 separate_and_filter(sm, expr->op, ranges, lr, __get_cur_slist(), implied_true, implied_false);
476 free_range_list_sval(&ranges);
477 delete_equiv_slist(implied_true, sm->name, sm->sym);
478 delete_equiv_slist(implied_false, sm->name, sm->sym);
481 static void handle_zero_comparison(struct expression *expr,
482 struct state_list **implied_true,
483 struct state_list **implied_false)
485 struct symbol *sym;
486 char *name;
487 struct sm_state *sm;
489 if (expr->type == EXPR_POSTOP)
490 expr = strip_expr(expr->unop);
492 if (expr->type == EXPR_ASSIGNMENT) {
493 /* most of the time ->pools will be empty here because we
494 just set the state, but if have assigned a conditional
495 function there are implications. */
496 expr = expr->left;
499 name = get_variable_from_expr(expr, &sym);
500 if (!name || !sym)
501 goto free;
502 sm = get_sm_state(SMATCH_EXTRA, name, sym);
503 if (!sm)
504 goto free;
506 separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(0), LEFT, __get_cur_slist(), implied_true, implied_false);
507 delete_equiv_slist(implied_true, name, sym);
508 delete_equiv_slist(implied_false, name, sym);
509 free:
510 free_string(name);
513 static void get_tf_states(struct expression *expr,
514 struct state_list **implied_true,
515 struct state_list **implied_false)
517 if (expr->type == EXPR_COMPARE)
518 handle_comparison(expr, implied_true, implied_false);
519 else
520 handle_zero_comparison(expr, implied_true, implied_false);
523 static void implied_states_hook(struct expression *expr)
525 struct sm_state *sm;
526 struct state_list *implied_true = NULL;
527 struct state_list *implied_false = NULL;
529 if (option_no_implied)
530 return;
532 get_tf_states(expr, &implied_true, &implied_false);
534 FOR_EACH_PTR(implied_true, sm) {
535 __set_true_false_sm(sm, NULL);
536 } END_FOR_EACH_PTR(sm);
537 free_slist(&implied_true);
539 FOR_EACH_PTR(implied_false, sm) {
540 __set_true_false_sm(NULL, sm);
541 } END_FOR_EACH_PTR(sm);
542 free_slist(&implied_false);
545 struct range_list_sval *__get_implied_values(struct expression *switch_expr)
547 char *name;
548 struct symbol *sym;
549 struct smatch_state *state;
550 struct range_list_sval *ret = NULL;
552 name = get_variable_from_expr(switch_expr, &sym);
553 if (!name || !sym)
554 goto free;
555 state = get_state(SMATCH_EXTRA, name, sym);
556 if (!state)
557 goto free;
558 ret = clone_range_list_sval(estate_ranges_sval(state));
559 free:
560 free_string(name);
561 if (!ret)
562 add_range_sval(&ret, ll_to_sval(whole_range.min), ll_to_sval(whole_range.max)); // FIXME
563 return ret;
566 struct state_list *__implied_case_slist(struct expression *switch_expr,
567 struct expression *case_expr,
568 struct range_list_stack_sval **remaining_cases,
569 struct state_list **raw_slist)
571 char *name = NULL;
572 struct symbol *sym;
573 struct sm_state *sm;
574 struct sm_state *true_sm;
575 struct state_list *true_states = NULL;
576 struct state_list *false_states = NULL;
577 struct state_list *ret = clone_slist(*raw_slist);
578 sval_t sval;
579 struct range_list_sval *vals = NULL;
581 name = get_variable_from_expr(switch_expr, &sym);
582 if (!name || !sym)
583 goto free;
584 sm = get_sm_state_slist(*raw_slist, SMATCH_EXTRA, name, sym);
585 if (!case_expr) {
586 vals = top_range_list_sval(*remaining_cases);
587 } else {
588 if (!get_value_sval(case_expr, &sval))
589 goto free;
591 filter_top_range_list_sval(remaining_cases, sval);
592 add_range_sval(&vals, sval, sval);
594 if (sm)
595 separate_and_filter(sm, SPECIAL_EQUAL, vals, LEFT, *raw_slist, &true_states, &false_states);
597 true_sm = get_sm_state_slist(true_states, SMATCH_EXTRA, name, sym);
598 if (!true_sm)
599 set_state_slist(&true_states, SMATCH_EXTRA, name, sym, alloc_estate_range_list_sval(vals));
600 overwrite_slist(true_states, &ret);
601 free_slist(&true_states);
602 free_slist(&false_states);
603 free:
604 free_string(name);
605 return ret;
608 static void match_end_func(struct symbol *sym)
610 implied_debug_msg = NULL;
614 * get_implications() can be called by check_ scripts.
616 void get_implications(char *name, struct symbol *sym, int comparison, long long num,
617 struct state_list **true_states,
618 struct state_list **false_states)
620 struct sm_state *sm;
622 sm = get_sm_state(SMATCH_EXTRA, name, sym);
623 if (!sm)
624 return;
625 if (slist_has_state(sm->possible, &undefined))
626 return;
627 separate_and_filter(sm, comparison, tmp_range_list(num), LEFT, __get_cur_slist(), true_states, false_states);
630 void __extra_match_condition(struct expression *expr);
631 void register_implications(int id)
633 add_hook(&implied_states_hook, CONDITION_HOOK);
634 add_hook(&__extra_match_condition, CONDITION_HOOK);
635 add_hook(&match_end_func, END_FUNC_HOOK);