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;
58 * We want to find which states have been modified inside a branch.
59 * If you have 2 &merged states they could be different states really
60 * and maybe one or both were modified. We say it is unchanged if
61 * the ->state pointers are the same and they belong to the same pools.
62 * If they have been modified on both sides of a branch to the same thing,
63 * it's still OK to say they are the same, because that means they won't
64 * belong to any pools.
66 static int is_really_same(struct sm_state
*one
, struct sm_state
*two
)
68 struct state_list
*tmp1
;
69 struct state_list
*tmp2
;
71 if (one
->state
!= two
->state
)
74 PREPARE_PTR_LIST(one
->my_pools
, tmp1
);
75 PREPARE_PTR_LIST(two
->my_pools
, tmp2
);
81 } else if (tmp1
== tmp2
) {
88 FINISH_PTR_LIST(tmp2
);
89 FINISH_PTR_LIST(tmp1
);
93 static int pool_in_pools(struct state_list_stack
*pools
,
94 struct state_list
*pool
)
96 struct state_list
*tmp
;
98 FOR_EACH_PTR(pools
, tmp
) {
101 } END_FOR_EACH_PTR(tmp
);
105 static struct state_list
*clone_states_in_pool(struct state_list
*pool
,
106 struct state_list
*cur_slist
)
108 struct sm_state
*state
;
109 struct sm_state
*cur_state
;
110 struct sm_state
*tmp
;
111 struct state_list
*to_slist
= NULL
;
113 FOR_EACH_PTR(pool
, state
) {
114 cur_state
= get_sm_state_slist(cur_slist
, state
->name
,
115 state
->owner
, state
->sym
);
118 if (is_really_same(state
, cur_state
))
120 if (pool_in_pools(cur_state
->all_pools
, pool
)) {
121 tmp
= clone_state(state
);
122 add_ptr_list(&to_slist
, tmp
);
124 } END_FOR_EACH_PTR(state
);
129 * merge_implied() takes an implied state and another possibly implied state
130 * from another pool. It checks that the second pool is reachable from
131 * cur_slist then merges the two states and returns the result.
133 static struct sm_state
*merge_implied(struct sm_state
*one
,
134 struct sm_state
*two
,
135 struct state_list
*pool
,
136 struct state_list
*cur_slist
)
138 struct sm_state
*cur_state
;
140 cur_state
= get_sm_state_slist(cur_slist
, two
->name
, two
->owner
,
143 return NULL
; /* this can't actually happen */
144 if (!pool_in_pools(cur_state
->all_pools
, pool
))
146 return merge_sm_states(one
, two
);
150 * filter() is used to find what states are the same across
151 * a series of slists.
152 * It takes a **slist and a *filter.
153 * It removes everything from **slist that isn't in *filter.
154 * The reason you would want to do this is if you want to
155 * know what other states are true if one state is true. (smatch_implied).
157 static void filter(struct state_list
**slist
, struct state_list
*filter
,
158 struct state_list
*cur_slist
)
160 struct sm_state
*s_one
, *s_two
;
161 struct state_list
*results
= NULL
;
162 struct sm_state
*tmp
;
164 PREPARE_PTR_LIST(*slist
, s_one
);
165 PREPARE_PTR_LIST(filter
, s_two
);
167 if (!s_one
|| !s_two
)
169 if (cmp_tracker(s_one
, s_two
) < 0) {
170 DIMPLIED("removed %s\n", s_one
->name
);
171 NEXT_PTR_LIST(s_one
);
172 } else if (cmp_tracker(s_one
, s_two
) == 0) {
173 tmp
= merge_implied(s_one
, s_two
, filter
, cur_slist
);
175 add_ptr_list(&results
, tmp
);
177 DIMPLIED("removed %s\n", s_one
->name
);
178 NEXT_PTR_LIST(s_one
);
179 NEXT_PTR_LIST(s_two
);
181 NEXT_PTR_LIST(s_two
);
184 FINISH_PTR_LIST(s_two
);
185 FINISH_PTR_LIST(s_one
);
191 static struct state_list
*filter_stack(struct state_list_stack
*stack
)
193 struct state_list
*tmp
;
194 struct state_list
*ret
= NULL
;
197 FOR_EACH_PTR(stack
, tmp
) {
199 ret
= clone_states_in_pool(tmp
, __get_cur_slist());
200 if (debug_implied_states
) {
201 printf("The first implied pool is:\n");
205 filter(&ret
, tmp
, __get_cur_slist());
206 DIMPLIED("filtered\n");
208 } END_FOR_EACH_PTR(tmp
);
212 static void get_eq_neq(struct sm_state
*sm_state
, int comparison
, int num
,
213 int left
, struct state_list
**true_states
,
214 struct state_list
**false_states
)
216 struct state_list
*list
;
217 struct smatch_state
*s
;
218 struct state_list_stack
*true_stack
= NULL
;
219 struct state_list_stack
*false_stack
= NULL
;
223 DIMPLIED("checking implications: (%s %s %d)\n", sm_state
->name
,
224 show_special(comparison
), num
);
226 DIMPLIED("checking implications: (%d %s %s)\n", num
,
227 show_special(comparison
), sm_state
->name
);
229 FOR_EACH_PTR(sm_state
->my_pools
, list
) {
230 s
= get_state_slist(list
, sm_state
->name
, sm_state
->owner
,
233 free_stack(&true_stack
);
234 free_stack(&false_stack
);
235 DIMPLIED("'%s' is merged.\n", sm_state
->name
);
238 if (s
== &undefined
) {
239 DIMPLIED("'%s' from %d is undefined.\n",
240 sm_state
->name
, sm_state
->line
);
241 push_slist(&true_stack
, list
);
242 push_slist(&false_stack
, list
);
246 tf
= true_comparison(*(int *)s
->data
, comparison
, num
);
248 tf
= true_comparison(num
, comparison
, *(int *)s
->data
);
250 DIMPLIED("'%s' from %d is true.\n", sm_state
->name
,
252 push_slist(&true_stack
, list
);
254 DIMPLIED("'%s' from %d is false.\n", sm_state
->name
,
256 push_slist(&false_stack
, list
);
258 } END_FOR_EACH_PTR(list
);
259 DIMPLIED("filtering true stack.\n");
260 *true_states
= filter_stack(true_stack
);
261 DIMPLIED("filtering false stack.\n");
262 *false_states
= filter_stack(false_stack
);
263 free_stack(&true_stack
);
264 free_stack(&false_stack
);
265 if (debug_implied_states
) {
266 printf("These are the implied states for the true path:\n");
267 __print_slist(*true_states
);
268 printf("These are the implied states for the false path:\n");
269 __print_slist(*false_states
);
273 static void handle_comparison(struct expression
*expr
,
274 struct state_list
**implied_true
,
275 struct state_list
**implied_false
)
279 struct sm_state
*state
;
283 value
= get_value(expr
->left
);
284 if (value
== UNDEFINED
) {
285 value
= get_value(expr
->right
);
286 if (value
== UNDEFINED
)
291 name
= get_variable_from_expr(expr
->left
, &sym
);
293 name
= get_variable_from_expr(expr
->right
, &sym
);
298 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
302 if (!state
->my_pools
) {
303 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state
->name
);
306 get_eq_neq(state
, expr
->op
, value
, left
, implied_true
, implied_false
);
309 static void get_tf_states(struct expression
*expr
,
310 struct state_list
**implied_true
,
311 struct state_list
**implied_false
)
315 struct sm_state
*state
;
317 if (expr
->type
== EXPR_COMPARE
) {
318 handle_comparison(expr
, implied_true
, implied_false
);
322 name
= get_variable_from_expr(expr
, &sym
);
327 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
331 if (!state
->my_pools
) {
332 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state
->name
);
335 get_eq_neq(state
, SPECIAL_NOTEQUAL
, 0, 1, implied_true
, implied_false
);
338 static void implied_states_hook(struct expression
*expr
)
340 struct sm_state
*state
;
341 struct state_list
*implied_true
= NULL
;
342 struct state_list
*implied_false
= NULL
;
344 if (option_no_implied
)
347 get_tf_states(expr
, &implied_true
, &implied_false
);
349 FOR_EACH_PTR(implied_true
, state
) {
350 __set_true_false_sm(state
, NULL
);
351 } END_FOR_EACH_PTR(state
);
352 free_slist(&implied_true
);
354 FOR_EACH_PTR(implied_false
, state
) {
355 __set_true_false_sm(NULL
, state
);
356 } END_FOR_EACH_PTR(state
);
357 free_slist(&implied_false
);
360 void register_implications(int id
)
362 add_hook(&implied_states_hook
, CONDITION_HOOK
);