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\n", sm_state
->name
,
81 push_slist(&ret
, list
);
83 } END_FOR_EACH_PTR(list
);
87 static struct state_list
*filter_stack(struct state_list_stack
*stack
)
89 struct state_list
*tmp
;
90 struct state_list
*ret
= NULL
;
93 FOR_EACH_PTR(stack
, tmp
) {
95 ret
= clone_states_in_pool(tmp
, __get_cur_slist());
96 if (debug_implied_states
) {
97 printf("The first implied pool is:\n");
101 filter(&ret
, tmp
, __get_cur_slist());
102 DIMPLIED("filtered\n");
104 } END_FOR_EACH_PTR(tmp
);
108 void __implied_states_hook(struct expression
*expr
)
112 struct sm_state
*state
;
113 struct state_list_stack
*true_pools
;
114 struct state_list_stack
*false_pools
;
115 struct state_list
*implied_true
;
116 struct state_list
*implied_false
;
118 if (option_no_implied
)
121 name
= get_variable_from_expr(expr
, &sym
);
126 state
= get_sm_state(name
, SMATCH_EXTRA
, sym
);
130 if (!state
->my_pools
) {
131 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state
->name
);
135 if (debug_implied_states
) {
136 printf("%s has the following possible states:\n", state
->name
);
137 __print_slist(state
->possible
);
140 DIMPLIED("Gettin the implied states for (%s != 0)\n", state
->name
);
141 true_pools
= get_eq_neq(state
, NOTEQUALS
, 0);
142 DIMPLIED("There are %s implied pools for (%s != 0).\n", (true_pools
?"some":"no"), state
->name
);
143 implied_true
= filter_stack(true_pools
);
144 if (implied_true
&& (debug_states
|| debug_implied_states
)) {
145 printf("Setting the following implied states for (%s != 0).\n",
147 __print_slist(implied_true
);
149 DIMPLIED("Gettin the implied states for (%s == 0)\n", state
->name
);
150 false_pools
= get_eq_neq(state
, EQUALS
, 0);
151 DIMPLIED("There are %s implied pools for (%s == 0).\n", (true_pools
?"some":"no"), state
->name
);
152 implied_false
= filter_stack(false_pools
);
153 if (implied_false
&& (debug_states
|| debug_implied_states
)) {
154 printf("Setting the following implied states for (%s == 0).\n",
156 __print_slist(implied_false
);
159 FOR_EACH_PTR(implied_true
, state
) {
160 __set_true_false_sm(state
, NULL
);
161 } END_FOR_EACH_PTR(state
);
162 free_stack(&true_pools
);
163 free_slist(&implied_true
);
165 FOR_EACH_PTR(implied_false
, state
) {
166 __set_true_false_sm(NULL
, state
);
167 } END_FOR_EACH_PTR(state
);
168 free_stack(&false_pools
);
169 free_slist(&implied_false
);
172 void register_implications(int id
)
174 add_hook(&__implied_states_hook
, CONDITION_HOOK
);