1 /*
2 * Copyright (C) 2010 Dan Carpenter.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 */
17
18 /*
19 * smatch_equiv.c is for tracking how variables are the same
20 *
21 * if (a == b) {
22 * Or
23 * x = y;
24 *
25 * When a variable gets modified all the old relationships are
26 * deleted. remove_equiv(expr);
27 *
28 */
29
30 #include "smatch.h"
31 #include "smatch_slist.h"
32 #include "smatch_extra.h"
33
34 ALLOCATOR(relation, "related variables");
35
36 static struct relation *alloc_relation(const char *name, struct symbol *sym)
37 {
38 struct relation *tmp;
39
40 tmp = __alloc_relation(0);
41 tmp->name = alloc_string(name);
42 tmp->sym = sym;
43 return tmp;
44 }
45
46 struct related_list *clone_related_list(struct related_list *related)
47 {
48 struct relation *rel;
49 struct related_list *to_list = NULL;
50
51 FOR_EACH_PTR(related, rel) {
52 add_ptr_list(&to_list, rel);
53 } END_FOR_EACH_PTR(rel);
54
55 return to_list;
56 }
57
58 static int cmp_relation(struct relation *a, struct relation *b)
59 {
60 int ret;
61
62 if (a == b)
63 return 0;
64
65 if (a->sym > b->sym)
66 return -1;
67 if (a->sym < b->sym)
68 return 1;
69
70 ret = strcmp(a->name, b->name);
71 if (ret)
72 return ret;
73
74 return 0;
75 }
76
77 struct related_list *get_shared_relations(struct related_list *one,
78 struct related_list *two)
79 {
80 struct related_list *ret = NULL;
81 struct relation *one_rel;
82 struct relation *two_rel;
83
84 PREPARE_PTR_LIST(one, one_rel);
85 PREPARE_PTR_LIST(two, two_rel);
86 for (;;) {
87 if (!one_rel || !two_rel)
88 break;
89 if (cmp_relation(one_rel, two_rel) < 0) {
90 NEXT_PTR_LIST(one_rel);
91 } else if (cmp_relation(one_rel, two_rel) == 0) {
92 add_ptr_list(&ret, one_rel);
93 NEXT_PTR_LIST(one_rel);
94 NEXT_PTR_LIST(two_rel);
95 } else {
96 NEXT_PTR_LIST(two_rel);
97 }
98 }
99 FINISH_PTR_LIST(two_rel);
100 FINISH_PTR_LIST(one_rel);
101
102 return ret;
103 }
104
105 static void add_related(struct related_list **rlist, const char *name, struct symbol *sym)
106 {
107 struct relation *rel;
108 struct relation *new;
109 struct relation tmp = {
110 .name = (char *)name,
111 .sym = sym
112 };
113
114 FOR_EACH_PTR(*rlist, rel) {
115 if (cmp_relation(rel, &tmp) < 0)
116 continue;
117 if (cmp_relation(rel, &tmp) == 0)
118 return;
119 new = alloc_relation(name, sym);
120 INSERT_CURRENT(new, rel);
121 return;
122 } END_FOR_EACH_PTR(rel);
123 new = alloc_relation(name, sym);
124 add_ptr_list(rlist, new);
125 }
126
127 static struct related_list *del_related(struct smatch_state *state, const char *name, struct symbol *sym)
128 {
129 struct relation *tmp;
130 struct relation remove = {
131 .name = (char *)name,
132 .sym = sym,
133 };
134 struct related_list *ret = NULL;
135
136 FOR_EACH_PTR(estate_related(state), tmp) {
137 if (cmp_relation(tmp, &remove) != 0)
138 add_ptr_list(&ret, tmp);
139 } END_FOR_EACH_PTR(tmp);
140
141 return ret;
142 }
143
144 void remove_from_equiv(const char *name, struct symbol *sym)
145 {
146 struct sm_state *orig_sm;
147 struct relation *rel;
148 struct smatch_state *state;
149 struct related_list *to_update;
150
151 orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
152 if (!orig_sm || !get_dinfo(orig_sm->state)->related)
153 return;
154
155 state = clone_estate(orig_sm->state);
156 to_update = del_related(state, name, sym);
157
158 FOR_EACH_PTR(to_update, rel) {
159 struct sm_state *old_sm, *new_sm;
160
161 old_sm = get_sm_state(SMATCH_EXTRA, rel->name, rel->sym);
162 if (!old_sm)
163 continue;
164
165 new_sm = clone_sm(old_sm);
166 get_dinfo(new_sm->state)->related = to_update;
167 __set_sm(new_sm);
168 } END_FOR_EACH_PTR(rel);
169 }
170
171 void remove_from_equiv_expr(struct expression *expr)
172 {
173 char *name;
174 struct symbol *sym;
175
176 name = expr_to_var_sym(expr, &sym);
177 if (!name || !sym)
178 goto free;
179 remove_from_equiv(name, sym);
180 free:
181 free_string(name);
182 }
183
184 void set_related(struct smatch_state *estate, struct related_list *rlist)
185 {
186 if (!estate_related(estate) && !rlist)
187 return;
188 get_dinfo(estate)->related = rlist;
189 }
190
191 /*
192 * set_equiv() is only used for assignments where we set one variable
193 * equal to the other. a = b;. It's not used for if conditions where
194 * a == b.
195 */
196 void set_equiv(struct expression *left, struct expression *right)
197 {
198 struct sm_state *right_sm, *left_sm, *other_sm;
199 struct relation *rel;
200 char *left_name;
201 struct symbol *left_sym;
202 struct related_list *rlist;
203 char *other_name;
204 struct symbol *other_sym;
205
206 left_name = expr_to_var_sym(left, &left_sym);
207 if (!left_name || !left_sym)
208 goto free;
209
210 other_name = get_other_name_sym(left_name, left_sym, &other_sym);
211
212 right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
213 if (!right_sm) {
214 struct range_list *rl;
215
216 if (!get_implied_rl(right, &rl))
217 rl = alloc_whole_rl(get_type(right));
218 right_sm = set_state_expr(SMATCH_EXTRA, right, alloc_estate_rl(rl));
219 }
220 if (!right_sm)
221 goto free;
222
223 /* This block is because we want to preserve the implications. */
224 left_sm = clone_sm(right_sm);
225 left_sm->name = alloc_string(left_name);
226 left_sm->sym = left_sym;
227 left_sm->state = clone_estate_cast(get_type(left), right_sm->state);
228 /* FIXME: The expression we're passing is wrong */
229 set_extra_mod_helper(left_name, left_sym, left, left_sm->state);
230 __set_sm(left_sm);
231
232 if (other_name && other_sym) {
233 other_sm = clone_sm(right_sm);
234 other_sm->name = alloc_string(other_name);
235 other_sm->sym = other_sym;
236 other_sm->state = clone_estate_cast(get_type(left), left_sm->state);
237 set_extra_mod_helper(other_name, other_sym, NULL, other_sm->state);
238 __set_sm(other_sm);
239 }
240
241 rlist = clone_related_list(estate_related(right_sm->state));
242 add_related(&rlist, right_sm->name, right_sm->sym);
243 add_related(&rlist, left_name, left_sym);
244 if (other_name && other_sym)
245 add_related(&rlist, other_name, other_sym);
246
247 FOR_EACH_PTR(rlist, rel) {
248 struct sm_state *old_sm, *new_sm;
249
250 old_sm = get_sm_state(SMATCH_EXTRA, rel->name, rel->sym);
251 if (!old_sm) /* shouldn't happen */
252 continue;
253 new_sm = clone_sm(old_sm);
254 new_sm->state = clone_estate(old_sm->state);
255 get_dinfo(new_sm->state)->related = rlist;
256 __set_sm(new_sm);
257 } END_FOR_EACH_PTR(rel);
258 free:
259 free_string(left_name);
260 }
261
262 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
263 {
264 struct relation *rel;
265 struct smatch_state *estate;
266
267 estate = get_state_expr(SMATCH_EXTRA, expr);
268
269 if (!estate)
270 return;
271
272 FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
273 set_state(id, rel->name, rel->sym, state);
274 } END_FOR_EACH_PTR(rel);
275 }