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
);
90 struct related_list
*get_shared_relations(struct related_list
*one
,
91 struct related_list
*two
)
93 struct related_list
*ret
= NULL
;
94 struct relation
*one_rel
;
95 struct relation
*two_rel
;
97 PREPARE_PTR_LIST(one
, one_rel
);
98 PREPARE_PTR_LIST(two
, two_rel
);
100 if (!one_rel
|| !two_rel
)
102 if (cmp_relation(one_rel
, two_rel
) < 0) {
103 NEXT_PTR_LIST(one_rel
);
104 } else if (cmp_relation(one_rel
, two_rel
) == 0) {
105 add_ptr_list(&ret
, one_rel
);
106 NEXT_PTR_LIST(one_rel
);
107 NEXT_PTR_LIST(two_rel
);
109 NEXT_PTR_LIST(two_rel
);
112 FINISH_PTR_LIST(two_rel
);
113 FINISH_PTR_LIST(one_rel
);
118 static void debug_addition(struct related_list
*rlist
, int op
, const char *name
)
120 struct relation
*tmp
;
122 if (!option_debug_related
)
127 FOR_EACH_PTR(rlist
, tmp
) {
128 sm_printf("%s %s ", show_special(tmp
->op
), tmp
->name
);
129 } END_FOR_EACH_PTR(tmp
);
130 sm_printf(") <-- %s %s\n", show_special(op
), name
);
133 static void add_related(struct related_list
**rlist
, int op
, const char *name
, struct symbol
*sym
)
135 struct relation
*rel
;
136 struct relation
*new;
137 struct relation tmp
= {
139 .name
= (char *)name
,
143 debug_addition(*rlist
, op
, name
);
145 FOR_EACH_PTR(*rlist
, rel
) {
146 if (cmp_relation(rel
, &tmp
) < 0)
148 if (cmp_relation(rel
, &tmp
) == 0)
150 new = alloc_relation(op
, name
, sym
);
151 INSERT_CURRENT(new, rel
);
153 } END_FOR_EACH_PTR(rel
);
154 new = alloc_relation(op
, name
, sym
);
155 add_ptr_list(rlist
, new);
158 void del_related(struct smatch_state
*state
, int op
, const char *name
, struct symbol
*sym
)
160 struct relation
*tmp
;
162 FOR_EACH_PTR(estate_related(state
), tmp
) {
163 if (tmp
->sym
< sym
|| strcmp(tmp
->name
, name
) < 0)
165 if (tmp
->sym
== sym
&& !strcmp(tmp
->name
, name
)) {
166 DELETE_CURRENT_PTR(tmp
);
170 } END_FOR_EACH_PTR(tmp
);
173 static void del_equiv(struct smatch_state
*state
, const char *name
, struct symbol
*sym
)
175 del_related(state
, SPECIAL_EQUAL
, name
, sym
);
178 void remove_from_equiv(const char *name
, struct symbol
*sym
)
180 struct sm_state
*orig_sm
;
181 struct relation
*rel
;
182 struct smatch_state
*state
;
183 struct related_list
*to_update
;
185 // FIXME equiv => related
186 orig_sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
187 if (!orig_sm
|| !get_dinfo(orig_sm
->state
)->related
)
190 state
= clone_estate(orig_sm
->state
);
191 del_equiv(state
, name
, sym
);
192 to_update
= get_dinfo(state
)->related
;
193 if (ptr_list_size((struct ptr_list
*)get_dinfo(state
)->related
) == 1)
194 get_dinfo(state
)->related
= NULL
;
196 FOR_EACH_PTR(to_update
, rel
) {
197 struct sm_state
*new_sm
;
199 new_sm
= clone_sm(orig_sm
);
200 new_sm
->name
= rel
->name
;
201 new_sm
->sym
= rel
->sym
;
202 new_sm
->state
= state
;
204 } END_FOR_EACH_PTR(rel
);
207 void remove_from_equiv_expr(struct expression
*expr
)
212 name
= get_variable_from_expr(expr
, &sym
);
215 remove_from_equiv(name
, sym
);
221 * set_equiv() is only used for assignments where we set one variable
222 * equal to the other. a = b;. It's not used for if conditions where
225 void set_equiv(struct expression
*left
, struct expression
*right
)
227 struct sm_state
*right_sm
;
228 struct smatch_state
*state
;
229 struct relation
*rel
;
231 struct symbol
*left_sym
;
232 struct related_list
*rlist
;
234 left_name
= get_variable_from_expr(left
, &left_sym
);
235 if (!left_name
|| !left_sym
)
238 right_sm
= get_sm_state_expr(SMATCH_EXTRA
, right
);
240 right_sm
= set_state_expr(SMATCH_EXTRA
, right
, extra_undefined());
244 remove_from_equiv(left_name
, left_sym
);
246 rlist
= clone_related_list(estate_related(right_sm
->state
));
247 add_related(&rlist
, SPECIAL_EQUAL
, right_sm
->name
, right_sm
->sym
);
248 add_related(&rlist
, SPECIAL_EQUAL
, left_name
, left_sym
);
250 state
= clone_estate(right_sm
->state
);
251 get_dinfo(state
)->related
= rlist
;
253 FOR_EACH_PTR(rlist
, rel
) {
254 struct sm_state
*new_sm
;
256 new_sm
= clone_sm(right_sm
);
257 new_sm
->name
= rel
->name
;
258 new_sm
->sym
= rel
->sym
;
259 new_sm
->state
= state
;
261 } END_FOR_EACH_PTR(rel
);
263 free_string(left_name
);
266 void set_equiv_state_expr(int id
, struct expression
*expr
, struct smatch_state
*state
)
268 struct relation
*rel
;
269 struct smatch_state
*estate
;
271 estate
= get_state_expr(SMATCH_EXTRA
, expr
);
276 FOR_EACH_PTR(get_dinfo(estate
)->related
, rel
) {
277 if (rel
->op
!= SPECIAL_EQUAL
)
279 set_state(id
, rel
->name
, rel
->sym
, state
);
280 } END_FOR_EACH_PTR(rel
);