sval: update smatch_helper.c
[smatch.git] / smatch_constraints.c
blob0ed68224a48b88902800f1c07f2bf96d83b0dcaa
1 /*
2 * sparse/smatch_constraints.c
4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
11 * smatch_constraints.c is for tracking how variables are related
13 * if (a == b) {
14 * if (a > b) {
15 * if (a != b) {
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
32 * smatch_implied.
36 #include "smatch.h"
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)
44 struct relation *tmp;
46 tmp = __alloc_relation(0);
47 tmp->op = op;
48 tmp->name = alloc_string(name);
49 tmp->sym = sym;
50 return tmp;
53 struct related_list *clone_related_list(struct related_list *related)
55 struct relation *rel;
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);
62 return to_list;
65 static int cmp_relation(struct relation *a, struct relation *b)
67 int ret;
69 if (a == b)
70 return 0;
72 if (a->op > b->op)
73 return -1;
74 if (a->op < b->op)
75 return 1;
77 if (a->sym > b->sym)
78 return -1;
79 if (a->sym < b->sym)
80 return 1;
82 ret = strcmp(a->name, b->name);
83 if (ret)
84 return ret;
86 return 0;
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);
98 for (;;) {
99 if (!one_rel || !two_rel)
100 break;
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);
107 } else {
108 NEXT_PTR_LIST(two_rel);
111 FINISH_PTR_LIST(two_rel);
112 FINISH_PTR_LIST(one_rel);
114 return ret;
117 static void debug_addition(struct related_list *rlist, int op, const char *name)
119 struct relation *tmp;
121 if (!option_debug_related)
122 return;
124 sm_prefix();
125 sm_printf("(");
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 = {
137 .op = op,
138 .name = (char *)name,
139 .sym = sym
142 debug_addition(*rlist, op, name);
144 FOR_EACH_PTR(*rlist, rel) {
145 if (cmp_relation(rel, &tmp) < 0)
146 continue;
147 if (cmp_relation(rel, &tmp) == 0)
148 return;
149 new = alloc_relation(op, name, sym);
150 INSERT_CURRENT(new, rel);
151 return;
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;
161 FOR_EACH_PTR(estate_related(state), tmp) {
162 if (tmp->sym < sym || strcmp(tmp->name, name) < 0)
163 continue;
164 if (tmp->sym == sym && !strcmp(tmp->name, name)) {
165 DELETE_CURRENT_PTR(tmp);
166 continue;
168 return;
169 } END_FOR_EACH_PTR(tmp);
172 static void del_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
174 del_related(state, SPECIAL_EQUAL, name, sym);
177 void remove_from_equiv(const char *name, struct symbol *sym)
179 struct sm_state *orig_sm;
180 struct relation *rel;
181 struct smatch_state *state;
182 struct related_list *to_update;
184 // FIXME equiv => related
185 orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
186 if (!orig_sm || !get_dinfo(orig_sm->state)->related)
187 return;
189 state = clone_estate(orig_sm->state);
190 del_equiv(state, name, sym);
191 to_update = get_dinfo(state)->related;
192 if (ptr_list_size((struct ptr_list *)get_dinfo(state)->related) == 1)
193 get_dinfo(state)->related = NULL;
195 FOR_EACH_PTR(to_update, rel) {
196 struct sm_state *new_sm;
198 new_sm = clone_sm(orig_sm);
199 new_sm->name = rel->name;
200 new_sm->sym = rel->sym;
201 new_sm->state = state;
202 __set_sm(new_sm);
203 } END_FOR_EACH_PTR(rel);
206 void remove_from_equiv_expr(struct expression *expr)
208 char *name;
209 struct symbol *sym;
211 name = get_variable_from_expr(expr, &sym);
212 if (!name || !sym)
213 goto free;
214 remove_from_equiv(name, sym);
215 free:
216 free_string(name);
219 void set_related(struct smatch_state **estate, struct related_list *rlist)
221 if (!estate_related(*estate) && !rlist)
222 return;
223 if (*estate == &estate_undefined)
224 *estate = clone_estate(&estate_undefined);
225 get_dinfo(*estate)->related = rlist;
229 * set_equiv() is only used for assignments where we set one variable
230 * equal to the other. a = b;. It's not used for if conditions where
231 * a == b.
233 void set_equiv(struct expression *left, struct expression *right)
235 struct sm_state *right_sm;
236 struct smatch_state *state;
237 struct relation *rel;
238 char *left_name;
239 struct symbol *left_sym;
240 struct related_list *rlist;
242 left_name = get_variable_from_expr(left, &left_sym);
243 if (!left_name || !left_sym)
244 goto free;
246 right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
247 if (!right_sm)
248 right_sm = set_state_expr(SMATCH_EXTRA, right, extra_undefined());
249 if (!right_sm)
250 return;
252 remove_from_equiv(left_name, left_sym);
254 rlist = clone_related_list(estate_related(right_sm->state));
255 add_related(&rlist, SPECIAL_EQUAL, right_sm->name, right_sm->sym);
256 add_related(&rlist, SPECIAL_EQUAL, left_name, left_sym);
258 state = clone_estate(right_sm->state);
259 get_dinfo(state)->related = rlist;
261 FOR_EACH_PTR(rlist, rel) {
262 struct sm_state *new_sm;
264 new_sm = clone_sm(right_sm);
265 new_sm->name = rel->name;
266 new_sm->sym = rel->sym;
267 new_sm->state = state;
268 __set_sm(new_sm);
269 } END_FOR_EACH_PTR(rel);
270 free:
271 free_string(left_name);
274 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
276 struct relation *rel;
277 struct smatch_state *estate;
279 estate = get_state_expr(SMATCH_EXTRA, expr);
281 if (!estate)
282 return;
284 FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
285 if (rel->op != SPECIAL_EQUAL)
286 continue;
287 set_state(id, rel->name, rel->sym, state);
288 } END_FOR_EACH_PTR(rel);