2 * sparse/smatch_constraints.c
4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
11 * smatch_constraints.c is for tracking how variables are related
17 * This is stored in a field in the smatch_extra dinfo.
19 * Normally the way that variables become related is through a
20 * condition and you say: add_constraint_expr(left, '<', right);
21 * The other way it can happen is if you have an assignment:
22 * set_equiv(left, right);
24 * One two variables "a" and "b" are related if then if we find
25 * that "a" is greater than 0 we need to update "b".
27 * When a variable gets modified all the old relationships are
28 * deleted. remove_contraints(expr);
30 * Also we need an is_true_constraint(left, '<', right) and
31 * is_false_constraint (left, '<', right). This is used by
37 #include "smatch_slist.h"
38 #include "smatch_extra.h"
40 ALLOCATOR(relation
, "related variables");
42 static struct relation
*alloc_relation(int op
, const char *name
, struct symbol
*sym
)
46 tmp
= __alloc_relation(0);
48 tmp
->name
= alloc_string(name
);
53 struct related_list
*clone_related_list(struct related_list
*related
)
56 struct related_list
*to_list
= NULL
;
58 FOR_EACH_PTR(related
, rel
) {
59 add_ptr_list(&to_list
, rel
);
60 } END_FOR_EACH_PTR(rel
);
65 static int cmp_relation(struct relation
*a
, struct relation
*b
)
82 ret
= strcmp(a
->name
, b
->name
);
89 struct related_list
*get_shared_relations(struct related_list
*one
,
90 struct related_list
*two
)
92 struct related_list
*ret
= NULL
;
93 struct relation
*one_rel
;
94 struct relation
*two_rel
;
96 PREPARE_PTR_LIST(one
, one_rel
);
97 PREPARE_PTR_LIST(two
, two_rel
);
99 if (!one_rel
|| !two_rel
)
101 if (cmp_relation(one_rel
, two_rel
) < 0) {
102 NEXT_PTR_LIST(one_rel
);
103 } else if (cmp_relation(one_rel
, two_rel
) == 0) {
104 add_ptr_list(&ret
, one_rel
);
105 NEXT_PTR_LIST(one_rel
);
106 NEXT_PTR_LIST(two_rel
);
108 NEXT_PTR_LIST(two_rel
);
111 FINISH_PTR_LIST(two_rel
);
112 FINISH_PTR_LIST(one_rel
);
117 static void debug_addition(struct related_list
*rlist
, int op
, const char *name
)
119 struct relation
*tmp
;
121 if (!option_debug_related
)
126 FOR_EACH_PTR(rlist
, tmp
) {
127 sm_printf("%s %s ", show_special(tmp
->op
), tmp
->name
);
128 } END_FOR_EACH_PTR(tmp
);
129 sm_printf(") <-- %s %s\n", show_special(op
), name
);
132 static void add_related(struct related_list
**rlist
, int op
, const char *name
, struct symbol
*sym
)
134 struct relation
*rel
;
135 struct relation
*new;
136 struct relation tmp
= {
138 .name
= (char *)name
,
142 debug_addition(*rlist
, op
, name
);
144 FOR_EACH_PTR(*rlist
, rel
) {
145 if (cmp_relation(rel
, &tmp
) < 0)
147 if (cmp_relation(rel
, &tmp
) == 0)
149 new = alloc_relation(op
, name
, sym
);
150 INSERT_CURRENT(new, rel
);
152 } END_FOR_EACH_PTR(rel
);
153 new = alloc_relation(op
, name
, sym
);
154 add_ptr_list(rlist
, new);
157 void del_related(struct smatch_state
*state
, int op
, const char *name
, struct symbol
*sym
)
159 struct relation
*tmp
;
160 struct relation remove
= {
162 .name
= (char *)name
,
166 FOR_EACH_PTR(estate_related(state
), tmp
) {
167 if (cmp_relation(tmp
, &remove
) < 0)
169 if (cmp_relation(tmp
, &remove
) == 0) {
170 DELETE_CURRENT_PTR(tmp
);
174 } END_FOR_EACH_PTR(tmp
);
177 static void del_equiv(struct smatch_state
*state
, const char *name
, struct symbol
*sym
)
179 del_related(state
, SPECIAL_EQUAL
, name
, sym
);
182 void remove_from_equiv(const char *name
, struct symbol
*sym
)
184 struct sm_state
*orig_sm
;
185 struct relation
*rel
;
186 struct smatch_state
*state
;
187 struct related_list
*to_update
;
189 // FIXME equiv => related
190 orig_sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
191 if (!orig_sm
|| !get_dinfo(orig_sm
->state
)->related
)
194 state
= clone_estate(orig_sm
->state
);
195 del_equiv(state
, name
, sym
);
196 to_update
= get_dinfo(state
)->related
;
197 if (ptr_list_size((struct ptr_list
*)get_dinfo(state
)->related
) == 1)
198 get_dinfo(state
)->related
= NULL
;
200 FOR_EACH_PTR(to_update
, rel
) {
201 struct sm_state
*new_sm
;
204 * The trick here is that we want to preserve the implications
205 * otherwise we could just call:
206 * set_state(SMATCH_EXTRA, rel->name, rel->sym, state);
209 orig_sm
= get_sm_state(SMATCH_EXTRA
, rel
->name
, rel
->sym
);
210 new_sm
= clone_sm(orig_sm
);
211 new_sm
->state
= state
;
213 } END_FOR_EACH_PTR(rel
);
216 void remove_from_equiv_expr(struct expression
*expr
)
221 name
= get_variable_from_expr(expr
, &sym
);
224 remove_from_equiv(name
, sym
);
229 void set_related(struct smatch_state
*estate
, struct related_list
*rlist
)
231 if (!estate_related(estate
) && !rlist
)
233 get_dinfo(estate
)->related
= rlist
;
237 * set_equiv() is only used for assignments where we set one variable
238 * equal to the other. a = b;. It's not used for if conditions where
241 void set_equiv(struct expression
*left
, struct expression
*right
)
243 struct sm_state
*right_sm
;
244 struct smatch_state
*state
;
245 struct relation
*rel
;
247 struct symbol
*left_sym
;
248 struct related_list
*rlist
;
250 left_name
= get_variable_from_expr(left
, &left_sym
);
251 if (!left_name
|| !left_sym
)
254 right_sm
= get_sm_state_expr(SMATCH_EXTRA
, right
);
256 right_sm
= set_state_expr(SMATCH_EXTRA
, right
, extra_undefined(get_type(right
)));
260 remove_from_equiv(left_name
, left_sym
);
262 rlist
= clone_related_list(estate_related(right_sm
->state
));
263 add_related(&rlist
, SPECIAL_EQUAL
, right_sm
->name
, right_sm
->sym
);
264 add_related(&rlist
, SPECIAL_EQUAL
, left_name
, left_sym
);
266 state
= clone_estate(right_sm
->state
);
267 get_dinfo(state
)->related
= rlist
;
269 FOR_EACH_PTR(rlist
, rel
) {
270 struct sm_state
*new_sm
;
272 new_sm
= clone_sm(right_sm
);
273 new_sm
->name
= rel
->name
;
274 new_sm
->sym
= rel
->sym
;
275 new_sm
->state
= state
;
277 } END_FOR_EACH_PTR(rel
);
279 free_string(left_name
);
282 void set_equiv_state_expr(int id
, struct expression
*expr
, struct smatch_state
*state
)
284 struct relation
*rel
;
285 struct smatch_state
*estate
;
287 estate
= get_state_expr(SMATCH_EXTRA
, expr
);
292 FOR_EACH_PTR(get_dinfo(estate
)->related
, rel
) {
293 if (rel
->op
!= SPECIAL_EQUAL
)
295 set_state(id
, rel
->name
, rel
->sym
, state
);
296 } END_FOR_EACH_PTR(rel
);