type: introduce type_to_str()
[smatch.git] / smatch_equiv.c
blob764657ab8be1a3e4b02c2f3dc23afe872d9f69d6
1 /*
2 * Copyright (C) 2010 Dan Carpenter.
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.
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.
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
19 * smatch_equiv.c is for tracking how variables are the same
21 * if (a == b) {
22 * Or
23 * x = y;
25 * When a variable gets modified all the old relationships are
26 * deleted. remove_equiv(expr);
30 #include "smatch.h"
31 #include "smatch_slist.h"
32 #include "smatch_extra.h"
34 ALLOCATOR(relation, "related variables");
36 static struct relation *alloc_relation(const char *name, struct symbol *sym)
38 struct relation *tmp;
40 tmp = __alloc_relation(0);
41 tmp->name = alloc_string(name);
42 tmp->sym = sym;
43 return tmp;
46 struct related_list *clone_related_list(struct related_list *related)
48 struct relation *rel;
49 struct related_list *to_list = NULL;
51 FOR_EACH_PTR(related, rel) {
52 add_ptr_list(&to_list, rel);
53 } END_FOR_EACH_PTR(rel);
55 return to_list;
58 static int cmp_relation(struct relation *a, struct relation *b)
60 int ret;
62 if (a == b)
63 return 0;
65 if (a->sym > b->sym)
66 return -1;
67 if (a->sym < b->sym)
68 return 1;
70 ret = strcmp(a->name, b->name);
71 if (ret)
72 return ret;
74 return 0;
77 struct related_list *get_shared_relations(struct related_list *one,
78 struct related_list *two)
80 struct related_list *ret = NULL;
81 struct relation *one_rel;
82 struct relation *two_rel;
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);
99 FINISH_PTR_LIST(two_rel);
100 FINISH_PTR_LIST(one_rel);
102 return ret;
105 static void debug_addition(struct related_list *rlist, const char *name)
107 struct relation *tmp;
109 if (!option_debug_related)
110 return;
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);
120 static void add_related(struct related_list **rlist, const char *name, struct symbol *sym)
122 struct relation *rel;
123 struct relation *new;
124 struct relation tmp = {
125 .name = (char *)name,
126 .sym = sym
129 debug_addition(*rlist, name);
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);
144 void del_related(struct smatch_state *state, const char *name, struct symbol *sym)
146 struct relation *tmp;
147 struct relation remove = {
148 .name = (char *)name,
149 .sym = sym,
152 FOR_EACH_PTR(estate_related(state), tmp) {
153 if (cmp_relation(tmp, &remove) < 0)
154 continue;
155 if (cmp_relation(tmp, &remove) == 0) {
156 DELETE_CURRENT_PTR(tmp);
157 return;
159 return;
160 } END_FOR_EACH_PTR(tmp);
163 static void del_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
165 del_related(state, name, sym);
168 void remove_from_equiv(const char *name, struct symbol *sym)
170 struct sm_state *orig_sm;
171 struct relation *rel;
172 struct smatch_state *state;
173 struct related_list *to_update;
175 // FIXME equiv => related
176 orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
177 if (!orig_sm || !get_dinfo(orig_sm->state)->related)
178 return;
180 state = clone_estate(orig_sm->state);
181 del_equiv(state, name, sym);
182 to_update = get_dinfo(state)->related;
183 if (ptr_list_size((struct ptr_list *)get_dinfo(state)->related) == 1)
184 get_dinfo(state)->related = NULL;
186 FOR_EACH_PTR(to_update, rel) {
187 struct sm_state *new_sm;
189 new_sm = clone_sm(orig_sm);
190 new_sm->name = rel->name;
191 new_sm->sym = rel->sym;
192 new_sm->state = state;
193 __set_sm(new_sm);
194 } END_FOR_EACH_PTR(rel);
197 void remove_from_equiv_expr(struct expression *expr)
199 char *name;
200 struct symbol *sym;
202 name = expr_to_var_sym(expr, &sym);
203 if (!name || !sym)
204 goto free;
205 remove_from_equiv(name, sym);
206 free:
207 free_string(name);
210 void set_related(struct smatch_state *estate, struct related_list *rlist)
212 if (!estate_related(estate) && !rlist)
213 return;
214 get_dinfo(estate)->related = rlist;
218 * set_equiv() is only used for assignments where we set one variable
219 * equal to the other. a = b;. It's not used for if conditions where
220 * a == b.
222 void set_equiv(struct expression *left, struct expression *right)
224 struct sm_state *right_sm;
225 struct smatch_state *state;
226 struct relation *rel;
227 char *left_name;
228 struct symbol *left_sym;
229 struct related_list *rlist;
231 left_name = expr_to_var_sym(left, &left_sym);
232 if (!left_name || !left_sym)
233 goto free;
235 right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
236 if (!right_sm)
237 right_sm = set_state_expr(SMATCH_EXTRA, right, alloc_estate_whole(get_type(right)));
238 if (!right_sm)
239 goto free;
241 remove_from_equiv(left_name, left_sym);
243 rlist = clone_related_list(estate_related(right_sm->state));
244 add_related(&rlist, right_sm->name, right_sm->sym);
245 add_related(&rlist, left_name, left_sym);
247 state = clone_estate(right_sm->state);
248 get_dinfo(state)->related = rlist;
250 call_extra_mod_hooks(left_name, left_sym, state);
252 FOR_EACH_PTR(rlist, rel) {
253 struct sm_state *new_sm;
255 new_sm = clone_sm(right_sm);
256 new_sm->name = rel->name;
257 new_sm->sym = rel->sym;
258 new_sm->state = state;
259 __set_sm(new_sm);
260 } END_FOR_EACH_PTR(rel);
261 free:
262 free_string(left_name);
265 void set_equiv_state_expr(int id, struct expression *expr, struct smatch_state *state)
267 struct relation *rel;
268 struct smatch_state *estate;
270 estate = get_state_expr(SMATCH_EXTRA, expr);
272 if (!estate)
273 return;
275 FOR_EACH_PTR(get_dinfo(estate)->related, rel) {
276 set_state(id, rel->name, rel->sym, state);
277 } END_FOR_EACH_PTR(rel);