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 * What are the implications if (foo == num) ...
61 static struct state_list_stack
*get_eq_neq(struct sm_state
*sm_state
,
64 struct state_list
*list
;
65 struct smatch_state
*s
;
66 struct state_list_stack
*ret
= NULL
;
68 FOR_EACH_PTR(sm_state
->my_pools
, list
) {
69 s
= get_state_slist(list
, sm_state
->name
, sm_state
->owner
,
71 if (s
== &undefined
) {
73 DIMPLIED("%d '%s' is undefined\n", get_lineno(),
77 if (s
->data
&& ((eq_neq
== EQUALS
&& *(int *)s
->data
== num
) ||
78 (eq_neq
== NOTEQUALS
&& *(int *)s
->data
!= num
))) {
79 DIMPLIED("added pool where %s is %s from line %d.\n",
80 sm_state
->name
, show_state(s
),
82 push_slist(&ret
, list
);
84 } END_FOR_EACH_PTR(list
);
88 static struct state_list
*filter_stack(struct state_list_stack
*stack
)
90 struct state_list
*tmp
;
91 struct state_list
*ret
= NULL
;
94 FOR_EACH_PTR(stack
, tmp
) {
96 ret
= clone_states_in_pool(tmp
, __get_cur_slist());
97 if (debug_implied_states
) {
98 printf("The first implied pool is:\n");
102 filter(&ret
, tmp
, __get_cur_slist());
103 DIMPLIED("filtered\n");
105 } END_FOR_EACH_PTR(tmp
);
109 void __implied_states_hook(struct expression
*expr
)
113 struct sm_state
*state
;
114 struct state_list_stack
*true_pools
;
115 struct state_list_stack
*false_pools
;
116 struct state_list
*implied_true
;
117 struct state_list
*implied_false
;
119 if (option_no_implied
)
122 name
= get_variable_from_expr(expr
, &sym
);
127 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
131 if (!state
->my_pools
) {
132 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state
->name
);
136 if (debug_implied_states
) {
137 printf("%s has the following possible states:\n", state
->name
);
138 __print_slist(state
->possible
);
141 DIMPLIED("Gettin the implied states for (%s != 0)\n", state
->name
);
142 true_pools
= get_eq_neq(state
, NOTEQUALS
, 0);
143 DIMPLIED("There are %s implied pools for (%s != 0).\n", (true_pools
?"some":"no"), state
->name
);
144 implied_true
= filter_stack(true_pools
);
145 if (implied_true
&& (debug_states
|| debug_implied_states
)) {
146 printf("Setting the following implied states for (%s != 0).\n",
148 __print_slist(implied_true
);
150 DIMPLIED("Gettin the implied states for (%s == 0)\n", state
->name
);
151 false_pools
= get_eq_neq(state
, EQUALS
, 0);
152 DIMPLIED("There are %s implied pools for (%s == 0).\n", (true_pools
?"some":"no"), state
->name
);
153 implied_false
= filter_stack(false_pools
);
154 if (implied_false
&& (debug_states
|| debug_implied_states
)) {
155 printf("Setting the following implied states for (%s == 0).\n",
157 __print_slist(implied_false
);
160 FOR_EACH_PTR(implied_true
, state
) {
161 __set_true_false_sm(state
, NULL
);
162 } END_FOR_EACH_PTR(state
);
163 free_stack(&true_pools
);
164 free_slist(&implied_true
);
166 FOR_EACH_PTR(implied_false
, state
) {
167 __set_true_false_sm(NULL
, state
);
168 } END_FOR_EACH_PTR(state
);
169 free_stack(&false_pools
);
170 free_slist(&implied_false
);
173 void register_implications(int id
)
175 add_hook(&__implied_states_hook
, CONDITION_HOOK
);