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 debug_addition(struct related_list *rlist, const char *name)
106 {
107 struct relation *tmp;
108
109 if (!option_debug_related)
110 return;
111
112 sm_prefix();
113 sm_printf("(");
114 FOR_EACH_PTR(rlist, tmp) {
115 sm_printf("%s ", tmp->name);
116 } END_FOR_EACH_PTR(tmp);
117 sm_printf(") <-- %s\n", name);
118 }
119
120 static void add_related(struct related_list **rlist, const char *name, struct symbol *sym)
121 {
122 struct relation *rel;
123 struct relation *new;
124 struct relation tmp = {
125 .name = (char *)name,
126 .sym = sym
127 };
128
129 debug_addition(*rlist, name);
130
131 FOR_EACH_PTR(*rlist, rel) {
132 if (cmp_relation(rel, &tmp) < 0)
133 continue;
134 if (cmp_relation(rel, &tmp) == 0)
135 return;
136 new = alloc_relation(name, sym);
137 INSERT_CURRENT(new, rel);
138 return;
139 } END_FOR_EACH_PTR(rel);
140 new = alloc_relation(name, sym);
141 add_ptr_list(rlist, new);
142 }
143
144 static struct related_list *del_related(struct smatch_state *state, const char *name, struct symbol *sym)
145 {
146 struct relation *tmp;
147 struct relation remove = {
148 .name = (char *)name,
149 .sym = sym,
150 };
151 struct related_list *ret = NULL;
152
153 FOR_EACH_PTR(estate_related(state), tmp) {
154 if (cmp_relation(tmp, &remove) != 0)
155 add_ptr_list(&ret, tmp);
156 } END_FOR_EACH_PTR(tmp);
157
158 return ret;
159 }
160
161 void remove_from_equiv(const char *name, struct symbol *sym)
162 {
163 struct sm_state *orig_sm;
164 struct relation *rel;
165 struct smatch_state *state;
166 struct related_list *to_update;
167
168 orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
169 if (!orig_sm || !get_dinfo(orig_sm->state)->related)
170 return;
171
172 state = clone_estate(orig_sm->state);
173 to_update = del_related(state, name, sym);
174
175 FOR_EACH_PTR(to_update, rel) {
176 struct sm_state *old_sm, *new_sm;
177
178 old_sm = get_sm_state(SMATCH_EXTRA, rel->name, rel->sym);
179 if (!old_sm)
180 continue;
181
182 new_sm = clone_sm(old_sm);
183 get_dinfo(new_sm->state)->related = to_update;
184 __set_sm(new_sm);
185 } END_FOR_EACH_PTR(rel);
186 }
187
188 void remove_from_equiv_expr(struct expression *expr)
189 {
190 char *name;
191 struct symbol *sym;
192
193 name = expr_to_var_sym(expr, &sym);
194 if (!name || !sym)
195 goto free;
196 remove_from_equiv(name, sym);
197 free:
198 free_string(name);
199 }
200
201 void set_related(struct smatch_state *estate, struct related_list *rlist)
202 {
203 if (!estate_related(estate) && !rlist)
204 return;
205 get_dinfo(estate)->related = rlist;
206 }
207
208 /*
209 * set_equiv() is only used for assignments where we set one variable
210 * equal to the other. a = b;. It's not used for if conditions where
211 * a == b.
212 */
213 void set_equiv(struct expression *left, struct expression *right)
214 {
215 struct sm_state *right_sm, *left_sm;
216 struct relation *rel;
217 char *left_name;
218 struct symbol *left_sym;
219 struct related_list *rlist;
220
221 left_name = expr_to_var_sym(left, &left_sym);
222 if (!left_name || !left_sym)
223 goto free;
224
225 right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
226 if (!right_sm)
227 right_sm = set_state_expr(SMATCH_EXTRA, right, alloc_estate_whole(get_type(right)));
228 if (!right_sm)
229 goto free;
230
231 /* This block is because we want to preserve the implications. */
232 left_sm = clone_sm(right_sm);
233 left_sm->name = alloc_string(left_name);
234 left_sm->sym = left_sym;
235 left_sm->state = clone_estate_cast(get_type(left), right_sm->state);
236 set_extra_mod_helper(left_name, left_sym, left, left_sm->state);
237 __set_sm(left_sm);
238
239 rlist = clone_related_list(estate_related(right_sm->state));
240 add_related(&rlist, right_sm->name, right_sm->sym);
241 add_related(&rlist, left_name, left_sym);
242
243 FOR_EACH_PTR(rlist, rel) {
244 struct sm_state *old_sm, *new_sm;
245
246 old_sm = get_sm_state(SMATCH_EXTRA, rel->name, rel->sym);
247 if (!old_sm) /* shouldn't happen */
248 continue;
249 new_sm = clone_sm(old_sm);
250 new_sm->state = clone_estate(old_sm->state);
251 get_dinfo(new_sm->state)->related = rlist;
252 __set_sm(new_sm);
253 } END_FOR_EACH_PTR(rel);
254 free:
255 free_string(left_name);
256 }
257
258 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
259 {
260 struct relation *rel;
261 struct smatch_state *estate;
262
263 estate = get_state_expr(SMATCH_EXTRA, expr);
264
265 if (!estate)
266 return;
267
268 FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
269 set_state(id, rel->name, rel->sym, state);
270 } END_FOR_EACH_PTR(rel);
271 }