xref: /illumos-gate/usr/src/tools/smatch/src/smatch_equiv.c (revision efe51d0cc2398b9ac179568b63a44e4bf295b8e2)
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 
alloc_relation(const char * name,struct symbol * sym)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 
clone_related_list(struct related_list * related)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 
cmp_relation(struct relation * a,struct relation * b)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 
get_shared_relations(struct related_list * one,struct related_list * two)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 
add_related(struct related_list ** rlist,const char * name,struct symbol * sym)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 
del_related(struct smatch_state * state,const char * name,struct symbol * sym)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 
remove_from_equiv(const char * name,struct symbol * sym)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 
remove_from_equiv_expr(struct expression * expr)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 
set_related(struct smatch_state * estate,struct related_list * rlist)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  */
set_equiv(struct expression * left,struct expression * right)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 
set_equiv_state_expr(int id,struct expression * expr,struct smatch_state * state)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 }
276