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_dinfo.c has helper functions for handling data_info structs
20  *
21  */
22 
23 #include <stdlib.h>
24 #ifndef __USE_ISOC99
25 #define __USE_ISOC99
26 #endif
27 #include <limits.h>
28 #include "parse.h"
29 #include "smatch.h"
30 #include "smatch_slist.h"
31 #include "smatch_extra.h"
32 
33 struct smatch_state *merge_estates(struct smatch_state *s1, struct smatch_state *s2)
34 {
35 	struct smatch_state *tmp;
36 	struct range_list *value_ranges;
37 	struct related_list *rlist;
38 
39 	if (estates_equiv(s1, s2))
40 		return s1;
41 
42 	value_ranges = rl_union(estate_rl(s1), estate_rl(s2));
43 	tmp = alloc_estate_rl(value_ranges);
44 	rlist = get_shared_relations(estate_related(s1), estate_related(s2));
45 	set_related(tmp, rlist);
46 	if (estate_has_hard_max(s1) && estate_has_hard_max(s2))
47 		estate_set_hard_max(tmp);
48 
49 	estate_set_fuzzy_max(tmp, sval_max(estate_get_fuzzy_max(s1), estate_get_fuzzy_max(s2)));
50 
51 	return tmp;
52 }
53 
54 struct data_info *get_dinfo(struct smatch_state *state)
55 {
56 	if (!state)
57 		return NULL;
58 	return (struct data_info *)state->data;
59 }
60 
61 struct range_list *estate_rl(struct smatch_state *state)
62 {
63 	if (!state)
64 		return NULL;
65 	return get_dinfo(state)->value_ranges;
66 }
67 
68 struct related_list *estate_related(struct smatch_state *state)
69 {
70 	if (!state)
71 		return NULL;
72 	return get_dinfo(state)->related;
73 }
74 
75 sval_t estate_get_fuzzy_max(struct smatch_state *state)
76 {
77 	sval_t empty = {};
78 
79 	if (!state || !get_dinfo(state))
80 		return empty;
81 	return get_dinfo(state)->fuzzy_max;
82 }
83 
84 int estate_has_fuzzy_max(struct smatch_state *state)
85 {
86 	if (estate_get_fuzzy_max(state).type)
87 		return 1;
88 	return 0;
89 }
90 
91 void estate_set_fuzzy_max(struct smatch_state *state, sval_t fuzzy_max)
92 {
93 	if (!rl_has_sval(estate_rl(state), fuzzy_max))
94 		return;
95 	get_dinfo(state)->fuzzy_max = fuzzy_max;
96 }
97 
98 void estate_copy_fuzzy_max(struct smatch_state *new, struct smatch_state *old)
99 {
100 	if (!estate_has_fuzzy_max(old))
101 		return;
102 	estate_set_fuzzy_max(new, estate_get_fuzzy_max(old));
103 }
104 
105 void estate_clear_fuzzy_max(struct smatch_state *state)
106 {
107 	sval_t empty = {};
108 
109 	get_dinfo(state)->fuzzy_max = empty;
110 }
111 
112 int estate_has_hard_max(struct smatch_state *state)
113 {
114 	if (!state)
115 		return 0;
116 	return get_dinfo(state)->hard_max;
117 }
118 
119 void estate_set_hard_max(struct smatch_state *state)
120 {
121 	get_dinfo(state)->hard_max = 1;
122 }
123 
124 void estate_clear_hard_max(struct smatch_state *state)
125 {
126 	get_dinfo(state)->hard_max = 0;
127 }
128 
129 int estate_get_hard_max(struct smatch_state *state, sval_t *sval)
130 {
131 	if (!state || !get_dinfo(state)->hard_max || !estate_rl(state))
132 		return 0;
133 	*sval = rl_max(estate_rl(state));
134 	return 1;
135 }
136 
137 sval_t estate_min(struct smatch_state *state)
138 {
139 	return rl_min(estate_rl(state));
140 }
141 
142 sval_t estate_max(struct smatch_state *state)
143 {
144 	return rl_max(estate_rl(state));
145 }
146 
147 struct symbol *estate_type(struct smatch_state *state)
148 {
149 	return rl_max(estate_rl(state)).type;
150 }
151 
152 static int rlists_equiv(struct related_list *one, struct related_list *two)
153 {
154 	struct relation *one_rel;
155 	struct relation *two_rel;
156 
157 	PREPARE_PTR_LIST(one, one_rel);
158 	PREPARE_PTR_LIST(two, two_rel);
159 	for (;;) {
160 		if (!one_rel && !two_rel)
161 			return 1;
162 		if (!one_rel || !two_rel)
163 			return 0;
164 		if (one_rel->sym != two_rel->sym)
165 			return 0;
166 		if (strcmp(one_rel->name, two_rel->name))
167 			return 0;
168 		NEXT_PTR_LIST(one_rel);
169 		NEXT_PTR_LIST(two_rel);
170 	}
171 	FINISH_PTR_LIST(two_rel);
172 	FINISH_PTR_LIST(one_rel);
173 
174 	return 1;
175 }
176 
177 int estates_equiv(struct smatch_state *one, struct smatch_state *two)
178 {
179 	if (!one || !two)
180 		return 0;
181 	if (one == two)
182 		return 1;
183 	if (!rlists_equiv(estate_related(one), estate_related(two)))
184 		return 0;
185 	if (strcmp(one->name, two->name) == 0)
186 		return 1;
187 	return 0;
188 }
189 
190 int estate_is_whole(struct smatch_state *state)
191 {
192 	return is_whole_rl(estate_rl(state));
193 }
194 
195 int estate_is_empty(struct smatch_state *state)
196 {
197 	return state && !estate_rl(state);
198 }
199 
200 int estate_is_unknown(struct smatch_state *state)
201 {
202 	if (!estate_is_whole(state))
203 		return 0;
204 	if (estate_related(state))
205 		return 0;
206 	if (estate_has_fuzzy_max(state))
207 		return 0;
208 	return 1;
209 }
210 
211 int estate_get_single_value(struct smatch_state *state, sval_t *sval)
212 {
213 	sval_t min, max;
214 
215 	min = rl_min(estate_rl(state));
216 	max = rl_max(estate_rl(state));
217 	if (sval_cmp(min, max) != 0)
218 		return 0;
219 	*sval = min;
220 	return 1;
221 }
222 
223 static struct data_info *alloc_dinfo(void)
224 {
225 	struct data_info *ret;
226 
227 	ret = __alloc_data_info(0);
228 	memset(ret, 0, sizeof(*ret));
229 	return ret;
230 }
231 
232 static struct data_info *alloc_dinfo_range(sval_t min, sval_t max)
233 {
234 	struct data_info *ret;
235 
236 	ret = alloc_dinfo();
237 	add_range(&ret->value_ranges, min, max);
238 	return ret;
239 }
240 
241 static struct data_info *alloc_dinfo_range_list(struct range_list *rl)
242 {
243 	struct data_info *ret;
244 
245 	ret = alloc_dinfo();
246 	ret->value_ranges = rl;
247 	return ret;
248 }
249 
250 static struct data_info *clone_dinfo(struct data_info *dinfo)
251 {
252 	struct data_info *ret;
253 
254 	ret = alloc_dinfo();
255 	ret->related = clone_related_list(dinfo->related);
256 	ret->value_ranges = clone_rl(dinfo->value_ranges);
257 	ret->hard_max = dinfo->hard_max;
258 	ret->fuzzy_max = dinfo->fuzzy_max;
259 	return ret;
260 }
261 
262 struct smatch_state *clone_estate(struct smatch_state *state)
263 {
264 	struct smatch_state *ret;
265 
266 	if (!state)
267 		return NULL;
268 
269 	ret = __alloc_smatch_state(0);
270 	ret->name = state->name;
271 	ret->data = clone_dinfo(get_dinfo(state));
272 	return ret;
273 }
274 
275 struct smatch_state *alloc_estate_empty(void)
276 {
277 	struct smatch_state *state;
278 	struct data_info *dinfo;
279 
280 	dinfo = alloc_dinfo();
281 	state = __alloc_smatch_state(0);
282 	state->data = dinfo;
283 	state->name = "";
284 	return state;
285 }
286 
287 struct smatch_state *alloc_estate_whole(struct symbol *type)
288 {
289 	return alloc_estate_rl(alloc_whole_rl(type));
290 }
291 
292 struct smatch_state *extra_empty(void)
293 {
294 	struct smatch_state *ret;
295 
296 	ret = __alloc_smatch_state(0);
297 	ret->name = "empty";
298 	ret->data = alloc_dinfo();
299 	return ret;
300 }
301 
302 struct smatch_state *alloc_estate_sval(sval_t sval)
303 {
304 	struct smatch_state *state;
305 
306 	state = __alloc_smatch_state(0);
307 	state->data = alloc_dinfo_range(sval, sval);
308 	state->name = show_rl(get_dinfo(state)->value_ranges);
309 	estate_set_hard_max(state);
310 	estate_set_fuzzy_max(state, sval);
311 	return state;
312 }
313 
314 struct smatch_state *alloc_estate_range(sval_t min, sval_t max)
315 {
316 	struct smatch_state *state;
317 
318 	state = __alloc_smatch_state(0);
319 	state->data = alloc_dinfo_range(min, max);
320 	state->name = show_rl(get_dinfo(state)->value_ranges);
321 	return state;
322 }
323 
324 struct smatch_state *alloc_estate_rl(struct range_list *rl)
325 {
326 	struct smatch_state *state;
327 
328 	if (!rl)
329 		return extra_empty();
330 
331 	state = __alloc_smatch_state(0);
332 	state->data = alloc_dinfo_range_list(rl);
333 	state->name = show_rl(rl);
334 	return state;
335 }
336 
337 struct smatch_state *clone_estate_cast(struct symbol *type, struct smatch_state *state)
338 {
339 	struct smatch_state *ret;
340 	struct data_info *dinfo;
341 
342 	if (!state)
343 		return NULL;
344 
345 	dinfo = alloc_dinfo();
346 	dinfo->value_ranges = clone_rl(cast_rl(type, estate_rl(state)));
347 
348 	ret = __alloc_smatch_state(0);
349 	ret->name = show_rl(dinfo->value_ranges);
350 	ret->data = dinfo;
351 
352 	return ret;
353 }
354 
355 struct smatch_state *get_implied_estate(struct expression *expr)
356 {
357 	struct smatch_state *state;
358 	struct range_list *rl;
359 
360 	state = get_state_expr(SMATCH_EXTRA, expr);
361 	if (state)
362 		return state;
363 	if (!get_implied_rl(expr, &rl))
364 		rl = alloc_whole_rl(get_type(expr));
365 	return alloc_estate_rl(rl);
366 }
367 
368 struct smatch_state *estate_filter_range(struct smatch_state *orig,
369 				 sval_t filter_min, sval_t filter_max)
370 {
371 	struct range_list *rl;
372 	struct smatch_state *state;
373 
374 	if (!orig)
375 		orig = alloc_estate_whole(filter_min.type);
376 
377 	rl = remove_range(estate_rl(orig), filter_min, filter_max);
378 	state = alloc_estate_rl(rl);
379 	if (estate_has_hard_max(orig))
380 		estate_set_hard_max(state);
381 	if (estate_has_fuzzy_max(orig))
382 		estate_set_fuzzy_max(state, estate_get_fuzzy_max(orig));
383 	return state;
384 }
385 
386 struct smatch_state *estate_filter_sval(struct smatch_state *orig, sval_t sval)
387 {
388 	return estate_filter_range(orig, sval, sval);
389 }
390 
391 /*
392  * One of the complications is that smatch tries to free a bunch of data at the
393  * end of every function.
394  */
395 struct data_info *clone_dinfo_perm(struct data_info *dinfo)
396 {
397 	struct data_info *ret;
398 
399 	ret = malloc(sizeof(*ret));
400 	memset(ret, 0, sizeof(*ret));
401 	ret->related = NULL;
402 	ret->value_ranges = clone_rl_permanent(dinfo->value_ranges);
403 	ret->hard_max = 0;
404 	ret->fuzzy_max = dinfo->fuzzy_max;
405 	return ret;
406 }
407 
408 struct smatch_state *clone_estate_perm(struct smatch_state *state)
409 {
410 	struct smatch_state *ret;
411 
412 	ret = malloc(sizeof(*ret));
413 	ret->name = alloc_string(state->name);
414 	ret->data = clone_dinfo_perm(get_dinfo(state));
415 	return ret;
416 }
417 
418 
419