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
;
203 new_sm
= clone_sm(orig_sm
);
204 new_sm
->name
= rel
->name
;
205 new_sm
->sym
= rel
->sym
;
206 new_sm
->state
= state
;
208 } END_FOR_EACH_PTR(rel
);
211 void remove_from_equiv_expr(struct expression
*expr
)
216 name
= get_variable_from_expr(expr
, &sym
);
219 remove_from_equiv(name
, sym
);
224 void set_related(struct smatch_state
*estate
, struct related_list
*rlist
)
226 if (!estate_related(estate
) && !rlist
)
228 get_dinfo(estate
)->related
= rlist
;
232 * set_equiv() is only used for assignments where we set one variable
233 * equal to the other. a = b;. It's not used for if conditions where
236 void set_equiv(struct expression
*left
, struct expression
*right
)
238 struct sm_state
*right_sm
;
239 struct smatch_state
*state
;
240 struct relation
*rel
;
242 struct symbol
*left_sym
;
243 struct related_list
*rlist
;
245 left_name
= get_variable_from_expr(left
, &left_sym
);
246 if (!left_name
|| !left_sym
)
249 right_sm
= get_sm_state_expr(SMATCH_EXTRA
, right
);
251 right_sm
= set_state_expr(SMATCH_EXTRA
, right
, alloc_estate_whole(get_type(right
)));
255 remove_from_equiv(left_name
, left_sym
);
257 rlist
= clone_related_list(estate_related(right_sm
->state
));
258 add_related(&rlist
, SPECIAL_EQUAL
, right_sm
->name
, right_sm
->sym
);
259 add_related(&rlist
, SPECIAL_EQUAL
, left_name
, left_sym
);
261 state
= clone_estate(right_sm
->state
);
262 get_dinfo(state
)->related
= rlist
;
264 FOR_EACH_PTR(rlist
, rel
) {
265 struct sm_state
*new_sm
;
267 new_sm
= clone_sm(right_sm
);
268 new_sm
->name
= rel
->name
;
269 new_sm
->sym
= rel
->sym
;
270 new_sm
->state
= state
;
272 } END_FOR_EACH_PTR(rel
);
274 free_string(left_name
);
277 void set_equiv_state_expr(int id
, struct expression
*expr
, struct smatch_state
*state
)
279 struct relation
*rel
;
280 struct smatch_state
*estate
;
282 estate
= get_state_expr(SMATCH_EXTRA
, expr
);
287 FOR_EACH_PTR(get_dinfo(estate
)->related
, rel
) {
288 if (rel
->op
!= SPECIAL_EQUAL
)
290 set_state(id
, rel
->name
, rel
->sym
, state
);
291 } END_FOR_EACH_PTR(rel
);