2 * sparse/smatch_implied.c
4 * Copyright (C) 2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
11 * Imagine we have this code:
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 my_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
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 ->my_pool. An sm_state only has one ->my_pool and
43 * that is the pool where it was first set. Implied states sometimes have a
44 * my_pool to reflect that the code flowed through that path.
45 * merge_sm_state() sets ->left and ->right. (These are the states which were
46 * merged to form the current state.)
47 * If an sm_state is not the same on both sides of a merge, it
48 * gets a ->my_pool set for both sides. The result is a merged
49 * state that has it's ->left and ->right pointers set. Merged states
50 * do not immediately have any my_pool set, but maybe will later
51 * when they themselves are merged.
52 * A pool is a list of all the states that were set at the time.
56 #include "smatch_slist.h"
57 #include "smatch_extra.h"
59 int debug_implied_states
= 0;
60 int option_no_implied
= 0;
62 static int print_once
= 0;
64 static struct range_list
*my_list
= NULL
;
65 static struct data_range
*my_range
;
67 static struct range_list
*tmp_range_list(long num
)
69 __free_ptr_list((struct ptr_list
**)&my_list
);
70 my_range
= alloc_range(num
, num
);
73 add_ptr_list(&my_list
, my_range
);
77 static int pool_in_pools(struct state_list
*pool
,
78 struct state_list_stack
*pools
)
80 struct state_list
*tmp
;
82 FOR_EACH_PTR(pools
, tmp
) {
87 } END_FOR_EACH_PTR(tmp
);
91 struct sm_state
*remove_my_pools(struct sm_state
*sm
,
92 struct state_list_stack
*pools
, int *modified
)
94 struct sm_state
*ret
= NULL
;
95 struct sm_state
*left
;
96 struct sm_state
*right
;
102 if (sm
->nr_children
> 5000) {
104 smatch_msg("debug: remove_my_pools %s nr_children %d",
105 sm
->name
, sm
->nr_children
);
110 if (pool_in_pools(sm
->my_pool
, pools
)) {
111 DIMPLIED("removed %s = %s from %d\n", sm
->name
,
112 show_state(sm
->state
), sm
->line
);
117 if (!is_merged(sm
)) {
118 DIMPLIED("kept %s = %s from %d\n", sm
->name
, show_state(sm
->state
),
123 DIMPLIED("checking %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
124 left
= remove_my_pools(sm
->left
, pools
, &removed
);
125 right
= remove_my_pools(sm
->right
, pools
, &removed
);
127 DIMPLIED("kept %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
131 if (!left
&& !right
) {
132 DIMPLIED("removed %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
137 ret
= clone_state(right
);
141 ret
->my_pool
= sm
->my_pool
;
143 ret
= clone_state(left
);
147 ret
->my_pool
= sm
->my_pool
;
149 ret
= merge_sm_states(left
, right
);
150 ret
->my_pool
= sm
->my_pool
;
153 DIMPLIED("partial %s = %s from %d\n", sm
->name
, show_state(sm
->state
), sm
->line
);
157 static struct state_list
*filter_stack(struct state_list
*pre_list
,
158 struct state_list_stack
*stack
)
160 struct state_list
*ret
= NULL
;
161 struct sm_state
*tmp
;
162 struct sm_state
*filtered_state
;
169 FOR_EACH_PTR(pre_list
, tmp
) {
171 filtered_state
= remove_my_pools(tmp
, stack
, &modified
);
172 if (filtered_state
&& modified
) {
173 add_ptr_list(&ret
, filtered_state
);
174 if ((counter
++)%10 && out_of_memory())
178 } END_FOR_EACH_PTR(tmp
);
182 static int is_checked(struct state_list
*checked
, struct sm_state
*sm
)
184 struct sm_state
*tmp
;
186 FOR_EACH_PTR(checked
, tmp
) {
189 } END_FOR_EACH_PTR(tmp
);
193 static void separate_pools(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
195 struct state_list_stack
**true_stack
,
196 struct state_list_stack
**false_stack
,
197 struct state_list
**checked
)
201 int free_checked
= 0;
202 struct state_list
*checked_states
= NULL
;
208 Sometimes the implications are just too big to deal with
209 so we bail. Theoretically, implications only get rid of
210 false positives and don't affect actual bugs.
212 if (sm_state
->nr_children
> 5000) {
214 smatch_msg("debug: seperate_pools %s nr_children %d",
215 sm_state
->name
, sm_state
->nr_children
);
220 if (checked
== NULL
) {
221 checked
= &checked_states
;
224 if (is_checked(*checked
, sm_state
)) {
227 add_ptr_list(checked
, sm_state
);
229 if (sm_state
->my_pool
) {
230 if (is_implied(sm_state
)) {
231 s
= get_sm_state_slist(sm_state
->my_pool
,
232 sm_state
->name
, sm_state
->owner
,
238 istrue
= !possibly_false_range_list(comparison
,
239 (struct data_info
*)s
->state
->data
,
241 isfalse
= !possibly_true_range_list(comparison
,
242 (struct data_info
*)s
->state
->data
,
245 if (debug_implied_states
|| debug_states
) {
246 if (istrue
&& isfalse
) {
247 printf("'%s = %s' from %d does not exist.\n",
248 s
->name
, show_state(s
->state
),
251 printf("'%s = %s' from %d is true.\n",
252 s
->name
, show_state(s
->state
),
254 } else if (isfalse
) {
255 printf("'%s = %s' from %d is false.\n",
256 s
->name
, show_state(s
->state
),
259 printf("'%s = %s' from %d could be true or "
261 show_state(s
->state
), s
->line
);
265 add_pool(true_stack
, s
->my_pool
);
268 add_pool(false_stack
, s
->my_pool
);
271 separate_pools(sm_state
->left
, comparison
, vals
, left
, true_stack
, false_stack
, checked
);
272 separate_pools(sm_state
->right
, comparison
, vals
, left
, true_stack
, false_stack
, checked
);
277 static void get_eq_neq(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
279 struct state_list
*pre_list
,
280 struct state_list
**true_states
,
281 struct state_list
**false_states
)
283 struct state_list_stack
*true_stack
= NULL
;
284 struct state_list_stack
*false_stack
= NULL
;
286 if (debug_implied_states
|| debug_states
) {
288 smatch_msg("checking implications: (%s %s %s)",
289 sm_state
->name
, show_special(comparison
), show_ranges(vals
));
291 smatch_msg("checking implications: (%s %s %s)",
292 show_ranges(vals
), show_special(comparison
), sm_state
->name
);
295 separate_pools(sm_state
, comparison
, vals
, left
, &true_stack
, &false_stack
, NULL
);
297 DIMPLIED("filtering true stack.\n");
298 *true_states
= filter_stack(pre_list
, false_stack
);
299 DIMPLIED("filtering false stack.\n");
300 *false_states
= filter_stack(pre_list
, true_stack
);
301 free_stack(&true_stack
);
302 free_stack(&false_stack
);
303 if (debug_implied_states
|| debug_states
) {
304 printf("These are the implied states for the true path:\n");
305 __print_slist(*true_states
);
306 printf("These are the implied states for the false path:\n");
307 __print_slist(*false_states
);
311 static char *get_implication_variable(struct expression
*expr
, struct symbol
**symp
)
313 expr
= strip_expr(expr
);
314 if (expr
->type
== EXPR_ASSIGNMENT
)
315 return get_implication_variable(expr
->left
, symp
);
316 return get_variable_from_expr(expr
, symp
);
319 static void handle_comparison(struct expression
*expr
,
320 struct state_list
**implied_true
,
321 struct state_list
**implied_false
)
325 struct sm_state
*state
;
329 value
= get_value(expr
->left
);
330 if (value
== UNDEFINED
) {
331 value
= get_value(expr
->right
);
332 if (value
== UNDEFINED
)
337 name
= get_implication_variable(expr
->left
, &sym
);
339 name
= get_implication_variable(expr
->right
, &sym
);
342 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
345 if (!is_merged(state
)) {
346 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), state
->name
);
349 get_eq_neq(state
, expr
->op
, tmp_range_list(value
), left
, __get_cur_slist(), implied_true
, implied_false
);
350 delete_state_slist(implied_true
, name
, SMATCH_EXTRA
, sym
);
351 delete_state_slist(implied_false
, name
, SMATCH_EXTRA
, sym
);
356 static void get_tf_states(struct expression
*expr
,
357 struct state_list
**implied_true
,
358 struct state_list
**implied_false
)
362 struct sm_state
*state
;
364 if (expr
->type
== EXPR_COMPARE
) {
365 handle_comparison(expr
, implied_true
, implied_false
);
368 if (expr
->type
== EXPR_ASSIGNMENT
) {
369 /* most of the time ->my_pools will be empty here because we
370 just set the state, but if have assigned a conditional
371 function there are implications. */
375 name
= get_variable_from_expr(expr
, &sym
);
378 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
381 if (!is_merged(state
)) {
382 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state
->name
);
385 get_eq_neq(state
, SPECIAL_NOTEQUAL
, tmp_range_list(0), 1, __get_cur_slist(), implied_true
, implied_false
);
386 delete_state_slist(implied_true
, name
, SMATCH_EXTRA
, sym
);
387 delete_state_slist(implied_false
, name
, SMATCH_EXTRA
, sym
);
392 static void implied_states_hook(struct expression
*expr
)
394 struct sm_state
*state
;
395 struct state_list
*implied_true
= NULL
;
396 struct state_list
*implied_false
= NULL
;
398 if (option_no_implied
)
401 get_tf_states(expr
, &implied_true
, &implied_false
);
403 FOR_EACH_PTR(implied_true
, state
) {
404 __set_true_false_sm(state
, NULL
);
405 } END_FOR_EACH_PTR(state
);
406 free_slist(&implied_true
);
408 FOR_EACH_PTR(implied_false
, state
) {
409 __set_true_false_sm(NULL
, state
);
410 } END_FOR_EACH_PTR(state
);
411 free_slist(&implied_false
);
414 struct range_list
*__get_implied_values(struct expression
*switch_expr
)
418 struct smatch_state
*state
;
419 struct range_list
*ret
= NULL
;
421 name
= get_variable_from_expr(switch_expr
, &sym
);
424 state
= get_state(name
, SMATCH_EXTRA
, sym
);
427 ret
= clone_range_list(((struct data_info
*)state
->data
)->value_ranges
);
431 add_range(&ret
, whole_range
.min
, whole_range
.max
);
435 void get_implications(char *name
, struct symbol
*sym
, int comparison
, int num
,
436 struct state_list
**true_states
,
437 struct state_list
**false_states
)
441 sm
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
444 if (slist_has_state(sm
->possible
, &undefined
))
446 get_eq_neq(sm
, comparison
, tmp_range_list(num
), 1, __get_cur_slist(), true_states
, false_states
);
449 struct state_list
*__implied_case_slist(struct expression
*switch_expr
,
450 struct expression
*case_expr
,
451 struct range_list_stack
**remaining_cases
,
452 struct state_list
**raw_slist
)
457 struct sm_state
*true_sm
;
458 struct state_list
*true_states
= NULL
;
459 struct state_list
*false_states
= NULL
;
460 struct state_list
*ret
= clone_slist(*raw_slist
);
462 struct data_range
*range
;
463 struct range_list
*vals
= NULL
;
465 name
= get_variable_from_expr(switch_expr
, &sym
);
468 sm
= get_sm_state_slist(*raw_slist
, name
, SMATCH_EXTRA
, sym
);
470 vals
= top_range_list(*remaining_cases
);
472 val
= get_value(case_expr
);
473 if (val
== UNDEFINED
) {
476 filter_top_range_list(remaining_cases
, val
);
477 range
= alloc_range(val
, val
);
478 add_ptr_list(&vals
, range
);
482 get_eq_neq(sm
, SPECIAL_EQUAL
, vals
, 1, *raw_slist
, &true_states
, &false_states
);
485 true_sm
= get_sm_state_slist(true_states
, name
, SMATCH_EXTRA
, sym
);
487 set_state_slist(&true_states
, name
, SMATCH_EXTRA
, sym
, alloc_extra_state_range_list(vals
));
488 overwrite_slist(true_states
, &ret
);
489 free_slist(&true_states
);
490 free_slist(&false_states
);
496 static void match_end_func(struct symbol
*sym
)
501 void __extra_match_condition(struct expression
*expr
);
502 void register_implications(int id
)
504 add_hook(&implied_states_hook
, CONDITION_HOOK
);
505 add_hook(&__extra_match_condition
, CONDITION_HOOK
);
506 add_hook(&match_end_func
, END_FUNC_HOOK
);