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 struct smatch_state
*alloc_state(struct expression
*expr
, int is_true
)
142 struct smatch_state
*state
;
144 state
= __alloc_smatch_state(0);
146 state
->name
= alloc_sname("true");
148 state
->name
= alloc_sname("false");
153 static void store_all_links(struct expression
*expr
, struct expression
*condition
)
155 struct var_sym_list
*vsl
;
160 expr
= strip_expr(expr
);
164 vsl
= expr_to_vsl(expr
);
165 FOR_EACH_PTR(vsl
, vs
) {
166 save_link_var_sym(vs
->var
, vs
->sym
, condition
);
167 } END_FOR_EACH_PTR(vs
);
169 var
= expr_to_known_chunk_sym(expr
, &sym
);
171 var
= expr_to_var_sym(expr
, &sym
);
174 save_link_var_sym(var
, sym
, condition
);
179 static int condition_too_complicated(struct expression
*expr
)
181 if (get_complication_score(expr
) > 2)
186 void __stored_condition(struct expression
*expr
)
188 struct smatch_state
*true_state
, *false_state
;
189 struct range_list
*rl
;
193 if (get_implied_value(expr
, &val
))
196 if (get_implied_rl(expr
, &rl
) &&
197 !rl_has_sval(rl
, int_zero
))
200 if (condition_too_complicated(expr
))
203 name
= expr_to_str(expr
);
206 true_state
= alloc_state(expr
, TRUE
);
207 false_state
= alloc_state(expr
, FALSE
);
208 set_true_false_states(my_id
, name
, NULL
, true_state
, false_state
);
209 store_all_links(expr
, expr
);
213 struct smatch_state
*get_stored_condition(struct expression
*expr
)
215 struct smatch_state
*state
;
218 name
= expr_to_str(expr
);
222 state
= get_state(my_id
, name
, NULL
);
227 struct expression_list
*get_conditions(struct expression
*expr
)
229 struct smatch_state
*state
;
231 state
= get_state_expr(link_id
, expr
);
237 void register_stored_conditions(int id
)
240 set_dynamic_states(my_id
);
243 void register_stored_conditions_links(int id
)
246 db_ignore_states(link_id
);
247 set_dynamic_states(link_id
);
248 add_merge_hook(link_id
, &merge_links
);
249 add_modification_hook(link_id
, &match_link_modify
);
252 #define RECURSE_LIMIT 50
254 static void filter_by_sm(struct sm_state
*sm
,
255 struct state_list
**true_stack
,
256 struct state_list
**false_stack
,
262 if ((*recurse_cnt
)++ > RECURSE_LIMIT
)
265 if (strcmp(sm
->state
->name
, "true") == 0) {
266 add_ptr_list(true_stack
, sm
);
267 } else if (strcmp(sm
->state
->name
, "false") == 0) {
268 add_ptr_list(false_stack
, sm
);
272 filter_by_sm(sm
->left
, true_stack
, false_stack
, recurse_cnt
);
273 filter_by_sm(sm
->right
, true_stack
, false_stack
, recurse_cnt
);
277 struct sm_state
*stored_condition_implication_hook(struct expression
*expr
,
278 struct state_list
**true_stack
,
279 struct state_list
**false_stack
)
284 struct state_list
*tmp_true
= NULL
;
285 struct state_list
*tmp_false
= NULL
;
286 struct sm_state
*tmp
;
288 expr
= strip_expr(expr
);
290 name
= expr_to_str(expr
);
294 sm
= get_sm_state(my_id
, name
, NULL
);
301 filter_by_sm(sm
, &tmp_true
, &tmp_false
, &recurse_cnt
);
302 if (!tmp_true
&& !tmp_false
)
304 if (recurse_cnt
> RECURSE_LIMIT
) {
309 FOR_EACH_PTR(tmp_true
, tmp
) {
310 add_ptr_list(true_stack
, tmp
);
311 } END_FOR_EACH_PTR(tmp
);
313 FOR_EACH_PTR(tmp_false
, tmp
) {
314 add_ptr_list(false_stack
, tmp
);
315 } END_FOR_EACH_PTR(tmp
);
318 free_slist(&tmp_true
);
319 free_slist(&tmp_false
);