flow: handle EXPR_OFFSETOF and EXPR_ALIGNOF
[smatch.git] / smatch_constraints.c
blob54ce9ab4ee6ad930e3ba35ecceddc4155e42a7f0
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;
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);
99 for (;;) {
100 if (!one_rel || !two_rel)
101 break;
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);
108 } else {
109 NEXT_PTR_LIST(two_rel);
112 FINISH_PTR_LIST(two_rel);
113 FINISH_PTR_LIST(one_rel);
115 return ret;
118 static void debug_addition(struct related_list *rlist, int op, const char *name)
120 struct relation *tmp;
122 if (!option_debug_related)
123 return;
125 sm_prefix();
126 sm_printf("(");
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 = {
138 .op = op,
139 .name = (char *)name,
140 .sym = sym
143 debug_addition(*rlist, op, name);
145 FOR_EACH_PTR(*rlist, rel) {
146 if (cmp_relation(rel, &tmp) < 0)
147 continue;
148 if (cmp_relation(rel, &tmp) == 0)
149 return;
150 new = alloc_relation(op, name, sym);
151 INSERT_CURRENT(new, rel);
152 return;
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)
164 continue;
165 if (tmp->sym == sym && !strcmp(tmp->name, name)) {
166 DELETE_CURRENT_PTR(tmp);
167 continue;
169 return;
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)
188 return;
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;
203 __set_sm(new_sm);
204 } END_FOR_EACH_PTR(rel);
207 void remove_from_equiv_expr(struct expression *expr)
209 char *name;
210 struct symbol *sym;
212 name = get_variable_from_expr(expr, &sym);
213 if (!name || !sym)
214 goto free;
215 remove_from_equiv(name, sym);
216 free:
217 free_string(name);
220 void set_related(struct smatch_state **estate, struct related_list *rlist)
222 if (!estate_related(*estate) && !rlist)
223 return;
224 if (*estate == &estate_undefined)
225 *estate = clone_estate(&estate_undefined);
226 get_dinfo(*estate)->related = rlist;
230 * set_equiv() is only used for assignments where we set one variable
231 * equal to the other. a = b;. It's not used for if conditions where
232 * a == b.
234 void set_equiv(struct expression *left, struct expression *right)
236 struct sm_state *right_sm;
237 struct smatch_state *state;
238 struct relation *rel;
239 char *left_name;
240 struct symbol *left_sym;
241 struct related_list *rlist;
243 left_name = get_variable_from_expr(left, &left_sym);
244 if (!left_name || !left_sym)
245 goto free;
247 right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
248 if (!right_sm)
249 right_sm = set_state_expr(SMATCH_EXTRA, right, extra_undefined());
250 if (!right_sm)
251 return;
253 remove_from_equiv(left_name, left_sym);
255 rlist = clone_related_list(estate_related(right_sm->state));
256 add_related(&rlist, SPECIAL_EQUAL, right_sm->name, right_sm->sym);
257 add_related(&rlist, SPECIAL_EQUAL, left_name, left_sym);
259 state = clone_estate(right_sm->state);
260 get_dinfo(state)->related = rlist;
262 FOR_EACH_PTR(rlist, rel) {
263 struct sm_state *new_sm;
265 new_sm = clone_sm(right_sm);
266 new_sm->name = rel->name;
267 new_sm->sym = rel->sym;
268 new_sm->state = state;
269 __set_sm(new_sm);
270 } END_FOR_EACH_PTR(rel);
271 free:
272 free_string(left_name);
275 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
277 struct relation *rel;
278 struct smatch_state *estate;
280 estate = get_state_expr(SMATCH_EXTRA, expr);
282 if (!estate)
283 return;
285 FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
286 if (rel->op != SPECIAL_EQUAL)
287 continue;
288 set_state(id, rel->name, rel->sym, state);
289 } END_FOR_EACH_PTR(rel);