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