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:
19 * if (foo == 1) // <-- point #3
20 * bar->baz; // <-- point #4
22 * Currently (Oct 2008) in smatch when we merge bar states
23 * null and nonnull, at point #2, the state becomes undefined.
24 * As a result we get an error at point #3.
26 * The idea behind "implied state pools" is to fix that.
28 * The implied pools get created in merge_slist(). Whatever
29 * is unique to one slist being merged gets put into a pool.
31 * If we set a state that removes it from all pools.
33 * When we come to an if statement where "foo" has some pools
34 * associated we take all the pools where "foo == 1" and keep
35 * all the states that are consistent across those pools.
37 * The point of doing this is to turn an undefined state into
38 * a defined state. This hopefully gets rid of some false positives.
39 * What it doesn't do is find new errors that were
42 * There are quite a few implementation details I haven't figured
43 * out. How do you create implied state pools inside a
44 * complex condition? How do you determine what is implied
45 * from a complex condition? The initial patch is extremely rudimentary...
49 #include "smatch_slist.h"
54 int debug_implied_states
= 0;
55 int option_no_implied
= 0;
57 static struct state_list
*filter_stack(struct state_list_stack
*stack
)
59 struct state_list
*tmp
;
60 struct state_list
*ret
= NULL
;
63 FOR_EACH_PTR(stack
, tmp
) {
65 ret
= clone_states_in_pool(tmp
, __get_cur_slist());
66 if (debug_implied_states
) {
67 printf("The first implied pool is:\n");
71 filter(&ret
, tmp
, __get_cur_slist());
72 DIMPLIED("filtered\n");
74 } END_FOR_EACH_PTR(tmp
);
78 static void get_eq_neq(struct sm_state
*sm_state
, int comparison
, int num
,
79 int left
, struct state_list
**true_states
,
80 struct state_list
**false_states
)
82 struct state_list
*list
;
83 struct smatch_state
*s
;
84 struct state_list_stack
*true_stack
= NULL
;
85 struct state_list_stack
*false_stack
= NULL
;
88 FOR_EACH_PTR(sm_state
->my_pools
, list
) {
89 s
= get_state_slist(list
, sm_state
->name
, sm_state
->owner
,
91 if (s
== &undefined
|| !s
->data
) {
92 free_stack(&true_stack
);
93 free_stack(&false_stack
);
94 DIMPLIED("%d '%s' is undefined\n", get_lineno(),
99 tf
= true_comparison(*(int *)s
->data
, comparison
, num
);
101 tf
= true_comparison(num
, comparison
, *(int *)s
->data
);
103 push_slist(&true_stack
, list
);
105 push_slist(&false_stack
, list
);
107 } END_FOR_EACH_PTR(list
);
108 *true_states
= filter_stack(true_stack
);
109 *false_states
= filter_stack(false_stack
);
110 free_stack(&true_stack
);
111 free_stack(&false_stack
);
114 static void handle_comparison(struct expression
*expr
,
115 struct state_list
**implied_true
,
116 struct state_list
**implied_false
)
120 struct sm_state
*state
;
124 value
= get_value(expr
->left
);
125 if (value
== UNDEFINED
) {
126 value
= get_value(expr
->right
);
127 if (value
== UNDEFINED
)
132 name
= get_variable_from_expr(expr
->left
, &sym
);
134 name
= get_variable_from_expr(expr
->right
, &sym
);
139 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
143 if (!state
->my_pools
) {
144 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state
->name
);
147 get_eq_neq(state
, expr
->op
, value
, left
, implied_true
, implied_false
);
150 static void get_tf_states(struct expression
*expr
,
151 struct state_list
**implied_true
,
152 struct state_list
**implied_false
)
156 struct sm_state
*state
;
158 if (expr
->type
== EXPR_COMPARE
) {
159 handle_comparison(expr
, implied_true
, implied_false
);
163 name
= get_variable_from_expr(expr
, &sym
);
168 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
172 if (!state
->my_pools
) {
173 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state
->name
);
176 get_eq_neq(state
, SPECIAL_NOTEQUAL
, 0, 1, implied_true
, implied_false
);
179 static void implied_states_hook(struct expression
*expr
)
181 struct sm_state
*state
;
182 struct state_list
*implied_true
= NULL
;
183 struct state_list
*implied_false
= NULL
;
185 if (option_no_implied
)
188 get_tf_states(expr
, &implied_true
, &implied_false
);
190 FOR_EACH_PTR(implied_true
, state
) {
191 __set_true_false_sm(state
, NULL
);
192 } END_FOR_EACH_PTR(state
);
193 free_slist(&implied_true
);
195 FOR_EACH_PTR(implied_false
, state
) {
196 __set_true_false_sm(NULL
, state
);
197 } END_FOR_EACH_PTR(state
);
198 free_slist(&implied_false
);
201 void register_implications(int id
)
203 add_hook(&implied_states_hook
, CONDITION_HOOK
);