2 * Copyright (C) 2014 Oracle.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
19 * Keep a record of all the things we have tested for so that we know when we
20 * test for it again. For example, if we have code like this:
30 * That's the end goal at least. But actually implementing the flow of that
31 * requires quite a bit of work because if "foo" changes the condition needs to
32 * be retested and smatch_implications.c needs to be updated.
34 * For now, I just record the conditions and use it to see if we test for NULL
40 #include "smatch_extra.h"
41 #include "smatch_slist.h"
46 static struct smatch_state
*alloc_link_state(struct expression_list
*expr_list
)
48 struct expression
*tmp
;
49 struct smatch_state
*state
;
50 static char buf
[256] = "";
54 state
= __alloc_smatch_state(0);
56 FOR_EACH_PTR(expr_list
, tmp
) {
57 name
= expr_to_str(tmp
);
58 cnt
+= snprintf(buf
+ cnt
, sizeof(buf
) - cnt
, "%s%s",
59 cnt
? ", " : "", name
);
61 if (cnt
>= sizeof(buf
))
63 } END_FOR_EACH_PTR(tmp
);
66 state
->name
= alloc_sname(buf
);
67 state
->data
= expr_list
;
71 static struct expression_list
*clone_expression_list(struct expression_list
*list
)
73 struct expression_list
*ret
= NULL
;
74 struct expression
*expr
;
76 FOR_EACH_PTR(list
, expr
) {
77 add_ptr_list(&ret
, expr
);
78 } END_FOR_EACH_PTR(expr
);
83 static void insert_expression(struct expression_list
**list
, struct expression
*expr
)
85 struct expression
*tmp
;
87 FOR_EACH_PTR(*list
, tmp
) {
90 } END_FOR_EACH_PTR(tmp
);
92 add_ptr_list(list
, expr
);
95 static struct smatch_state
*merge_links(struct smatch_state
*s1
, struct smatch_state
*s2
)
97 struct expression_list
*list
, *expr_list
;
98 struct expression
*expr
;
100 expr_list
= clone_expression_list(s1
->data
);
103 FOR_EACH_PTR(list
, expr
) {
104 insert_expression(&expr_list
, expr
);
105 } END_FOR_EACH_PTR(expr
);
107 return alloc_link_state(expr_list
);
110 static void save_link_var_sym(const char *var
, struct symbol
*sym
, struct expression
*condition
)
112 struct smatch_state
*old_state
, *new_state
;
113 struct expression_list
*expr_list
;
115 old_state
= get_state(link_id
, var
, sym
);
116 expr_list
= clone_expression_list(old_state
? old_state
->data
: NULL
);
118 insert_expression(&expr_list
, condition
);
120 new_state
= alloc_link_state(expr_list
);
121 set_state(link_id
, var
, sym
, new_state
);
124 static void match_link_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
126 struct expression_list
*expr_list
;
127 struct expression
*tmp
;
130 expr_list
= sm
->state
->data
;
132 FOR_EACH_PTR(expr_list
, tmp
) {
133 name
= expr_to_str(tmp
);
134 set_state(my_id
, name
, NULL
, &undefined
);
136 } END_FOR_EACH_PTR(tmp
);
137 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
140 static void match_untracked(struct expression
*call
, int param
)
142 struct expression
*arg
;
147 * NOTE: I wrote this patch because of a misunderstanding. The
148 * untracked parameter wasn't a stored condition, it was something
149 * in smatch_extra and then we get the stored implication via an
150 * implication later... Ugh. That explanation is too complicated.
151 * I should just delete this code, but it feels more correct than
152 * the original code. Plus it was a lot of work to write it.
156 arg
= get_argument_from_call_expr(call
->args
, param
);
157 sym
= expr_to_sym(arg
);
161 FOR_EACH_MY_SM(link_id
, __get_cur_stree(), sm
) {
163 match_link_modify(sm
, NULL
);
164 } END_FOR_EACH_SM(sm
);
167 static struct smatch_state
*alloc_state(struct expression
*expr
, int is_true
)
169 struct smatch_state
*state
;
171 state
= __alloc_smatch_state(0);
173 state
->name
= alloc_sname("true");
175 state
->name
= alloc_sname("false");
180 static void store_all_links(struct expression
*expr
, struct expression
*condition
)
182 struct var_sym_list
*vsl
;
187 expr
= strip_expr(expr
);
191 vsl
= expr_to_vsl(expr
);
192 FOR_EACH_PTR(vsl
, vs
) {
193 save_link_var_sym(vs
->var
, vs
->sym
, condition
);
194 } END_FOR_EACH_PTR(vs
);
196 /* This is used to store "array[0]" from "if (array[0] == 1) " */
197 var
= expr_to_known_chunk_sym(expr
, &sym
);
200 save_link_var_sym(var
, sym
, condition
);
205 static int is_untracked_var_helper(struct expression
*expr
, void *unused
)
207 if (expr
->type
== EXPR_SYMBOL
)
208 return is_untracked(expr
);
212 static int condition_too_complicated(struct expression
*expr
)
214 if (get_complication_score(expr
) > 2)
216 if (recurse(expr
, is_untracked_var_helper
, NULL
, 0) == 1)
221 void __stored_condition(struct expression
*expr
)
223 struct smatch_state
*true_state
, *false_state
;
226 if (implied_condition_true(expr
) ||
227 implied_condition_false(expr
))
230 if (condition_too_complicated(expr
))
233 name
= expr_to_str(expr
);
236 true_state
= alloc_state(expr
, TRUE
);
237 false_state
= alloc_state(expr
, FALSE
);
239 set_true_false_states(my_id
, name
, NULL
, true_state
, false_state
);
240 store_all_links(expr
, expr
);
244 struct smatch_state
*get_stored_condition(struct expression
*expr
)
246 struct smatch_state
*state
;
249 name
= expr_to_str(expr
);
253 state
= get_state(my_id
, name
, NULL
);
258 struct expression_list
*get_conditions(struct expression
*expr
)
260 struct smatch_state
*state
;
262 state
= get_state_expr(link_id
, expr
);
268 void register_stored_conditions(int id
)
271 set_dynamic_states(my_id
);
274 void register_stored_conditions_links(int id
)
277 db_ignore_states(link_id
);
278 set_dynamic_states(link_id
);
279 add_merge_hook(link_id
, &merge_links
);
280 add_modification_hook(link_id
, &match_link_modify
);
281 add_untracked_param_hook(&match_untracked
);
284 #define RECURSE_LIMIT 50
286 static void filter_by_sm(struct sm_state
*sm
,
287 struct state_list
**true_stack
,
288 struct state_list
**false_stack
,
294 if ((*recurse_cnt
)++ > RECURSE_LIMIT
)
297 if (strcmp(sm
->state
->name
, "true") == 0) {
298 add_ptr_list(true_stack
, sm
);
299 } else if (strcmp(sm
->state
->name
, "false") == 0) {
300 add_ptr_list(false_stack
, sm
);
304 filter_by_sm(sm
->left
, true_stack
, false_stack
, recurse_cnt
);
305 filter_by_sm(sm
->right
, true_stack
, false_stack
, recurse_cnt
);
309 struct sm_state
*stored_condition_implication_hook(struct expression
*expr
,
310 struct state_list
**true_stack
,
311 struct state_list
**false_stack
)
316 struct state_list
*tmp_true
= NULL
;
317 struct state_list
*tmp_false
= NULL
;
318 struct sm_state
*tmp
;
320 expr
= strip_expr(expr
);
322 name
= expr_to_str(expr
);
326 sm
= get_sm_state(my_id
, name
, NULL
);
333 filter_by_sm(sm
, &tmp_true
, &tmp_false
, &recurse_cnt
);
334 if (!tmp_true
&& !tmp_false
)
336 if (recurse_cnt
> RECURSE_LIMIT
) {
341 FOR_EACH_PTR(tmp_true
, tmp
) {
342 add_ptr_list(true_stack
, tmp
);
343 } END_FOR_EACH_PTR(tmp
);
345 FOR_EACH_PTR(tmp_false
, tmp
) {
346 add_ptr_list(false_stack
, tmp
);
347 } END_FOR_EACH_PTR(tmp
);
350 free_slist(&tmp_true
);
351 free_slist(&tmp_false
);