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"
50 #include "smatch_extra.h"
55 int debug_implied_states
= 0;
56 int option_no_implied
= 0;
58 static int pool_in_pools(struct state_list_stack
*pools
,
59 struct state_list
*pool
)
61 struct state_list
*tmp
;
63 FOR_EACH_PTR(pools
, tmp
) {
66 } END_FOR_EACH_PTR(tmp
);
70 static struct state_list
*clone_states_in_pool(struct state_list
*pool
,
71 struct state_list
*cur_slist
)
73 struct sm_state
*state
;
74 struct sm_state
*cur_state
;
76 struct state_list
*to_slist
= NULL
;
78 FOR_EACH_PTR(pool
, state
) {
79 cur_state
= get_sm_state_slist(cur_slist
, state
->name
,
80 state
->owner
, state
->sym
);
83 if (state
== cur_state
)
85 if (pool_in_pools(cur_state
->all_pools
, pool
)) {
86 tmp
= clone_state(state
);
87 add_ptr_list(&to_slist
, tmp
);
89 } END_FOR_EACH_PTR(state
);
94 * merge_implied() takes an implied state and another possibly implied state
95 * from another pool. It checks that the second pool is reachable from
96 * cur_slist then merges the two states and returns the result.
98 static struct sm_state
*merge_implied(struct sm_state
*one
,
100 struct state_list
*pool
,
101 struct state_list
*cur_slist
)
103 struct sm_state
*cur_state
;
105 cur_state
= get_sm_state_slist(cur_slist
, two
->name
, two
->owner
,
108 return NULL
; /* this can't actually happen */
109 if (!pool_in_pools(cur_state
->all_pools
, pool
))
111 return merge_sm_states(one
, two
);
115 * filter() is used to find what states are the same across
116 * a series of slists.
117 * It takes a **slist and a *filter.
118 * It removes everything from **slist that isn't in *filter.
119 * The reason you would want to do this is if you want to
120 * know what other states are true if one state is true. (smatch_implied).
122 static void filter(struct state_list
**slist
, struct state_list
*filter
,
123 struct state_list
*cur_slist
)
125 struct sm_state
*s_one
, *s_two
;
126 struct state_list
*results
= NULL
;
127 struct sm_state
*tmp
;
129 PREPARE_PTR_LIST(*slist
, s_one
);
130 PREPARE_PTR_LIST(filter
, s_two
);
132 if (!s_one
|| !s_two
)
134 if (cmp_tracker(s_one
, s_two
) < 0) {
135 DIMPLIED("removed %s\n", s_one
->name
);
136 NEXT_PTR_LIST(s_one
);
137 } else if (cmp_tracker(s_one
, s_two
) == 0) {
138 tmp
= merge_implied(s_one
, s_two
, filter
, cur_slist
);
140 add_ptr_list(&results
, tmp
);
142 DIMPLIED("removed %s\n", s_one
->name
);
143 NEXT_PTR_LIST(s_one
);
144 NEXT_PTR_LIST(s_two
);
146 NEXT_PTR_LIST(s_two
);
149 FINISH_PTR_LIST(s_two
);
150 FINISH_PTR_LIST(s_one
);
156 static struct state_list
*filter_stack(struct state_list_stack
*stack
)
158 struct state_list
*tmp
;
159 struct state_list
*ret
= NULL
;
162 FOR_EACH_PTR(stack
, tmp
) {
164 ret
= clone_states_in_pool(tmp
, __get_cur_slist());
165 if (debug_implied_states
) {
166 printf("The first implied pool is:\n");
170 filter(&ret
, tmp
, __get_cur_slist());
171 DIMPLIED("filtered\n");
173 } END_FOR_EACH_PTR(tmp
);
177 static void get_eq_neq(struct sm_state
*sm_state
, int comparison
, int num
,
178 int left
, struct state_list
**true_states
,
179 struct state_list
**false_states
)
181 struct state_list
*list
;
183 struct state_list_stack
*true_stack
= NULL
;
184 struct state_list_stack
*false_stack
= NULL
;
187 DIMPLIED("%d checking implications: (%s %s %d)\n", get_lineno(),
188 sm_state
->name
, show_special(comparison
), num
);
190 DIMPLIED("%d checking implications: (%d %s %s)\n", get_lineno(),
191 num
, show_special(comparison
), sm_state
->name
);
193 FOR_EACH_PTR(sm_state
->my_pools
, list
) {
194 s
= get_sm_state_slist(list
, sm_state
->name
, sm_state
->owner
,
196 if (possibly_true(comparison
,
197 (struct data_info
*)s
->state
->data
, num
,
199 DIMPLIED("'%s' from %d is true.\n", s
->name
, s
->line
);
200 push_slist(&true_stack
, list
);
202 if (possibly_false(comparison
,
203 (struct data_info
*)s
->state
->data
, num
,
205 DIMPLIED("'%s' from %d is false.\n", s
->name
, s
->line
);
206 push_slist(&false_stack
, list
);
208 } END_FOR_EACH_PTR(list
);
209 DIMPLIED("filtering true stack.\n");
210 *true_states
= filter_stack(true_stack
);
211 DIMPLIED("filtering false stack.\n");
212 *false_states
= filter_stack(false_stack
);
213 free_stack(&true_stack
);
214 free_stack(&false_stack
);
215 if (debug_implied_states
|| debug_states
) {
216 printf("These are the implied states for the true path:\n");
217 __print_slist(*true_states
);
218 printf("These are the implied states for the false path:\n");
219 __print_slist(*false_states
);
223 static void handle_comparison(struct expression
*expr
,
224 struct state_list
**implied_true
,
225 struct state_list
**implied_false
)
229 struct sm_state
*state
;
233 value
= get_value(expr
->left
);
234 if (value
== UNDEFINED
) {
235 value
= get_value(expr
->right
);
236 if (value
== UNDEFINED
)
241 name
= get_variable_from_expr(expr
->left
, &sym
);
243 name
= get_variable_from_expr(expr
->right
, &sym
);
248 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
252 if (!state
->my_pools
) {
253 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state
->name
);
256 get_eq_neq(state
, expr
->op
, value
, left
, implied_true
, implied_false
);
259 static void get_tf_states(struct expression
*expr
,
260 struct state_list
**implied_true
,
261 struct state_list
**implied_false
)
265 struct sm_state
*state
;
267 if (expr
->type
== EXPR_COMPARE
) {
268 handle_comparison(expr
, implied_true
, implied_false
);
272 name
= get_variable_from_expr(expr
, &sym
);
277 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
281 if (!state
->my_pools
) {
282 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state
->name
);
285 get_eq_neq(state
, SPECIAL_NOTEQUAL
, 0, 1, implied_true
, implied_false
);
288 static void implied_states_hook(struct expression
*expr
)
290 struct sm_state
*state
;
291 struct state_list
*implied_true
= NULL
;
292 struct state_list
*implied_false
= NULL
;
294 if (option_no_implied
)
297 get_tf_states(expr
, &implied_true
, &implied_false
);
299 FOR_EACH_PTR(implied_true
, state
) {
300 __set_true_false_sm(state
, NULL
);
301 } END_FOR_EACH_PTR(state
);
302 free_slist(&implied_true
);
304 FOR_EACH_PTR(implied_false
, state
) {
305 __set_true_false_sm(NULL
, state
);
306 } END_FOR_EACH_PTR(state
);
307 free_slist(&implied_false
);
310 void get_implications(char *name
, struct symbol
*sym
, int comparison
, int num
,
311 struct state_list
**true_states
,
312 struct state_list
**false_states
)
316 sm
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
319 if (slist_has_state(sm
->possible
, &undefined
))
321 get_eq_neq(sm
, comparison
, num
, 1, true_states
, false_states
);
324 void register_implications(int id
)
326 add_hook(&implied_states_hook
, CONDITION_HOOK
);