?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
conditions: handle comma condtions
[smatch.git] / smatch_ranges.c
blob6bd27a9159a547ad16b84de8ccd31e2f34d104ee
1 /*
2 * Copyright (C) 2009 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 #include "parse.h"
19 #include "smatch.h"
20 #include "smatch_extra.h"
21 #include "smatch_slist.h"
22
23 ALLOCATOR(data_info, "smatch extra data");
24 ALLOCATOR(data_range, "data range");
25 __DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
26 "permanent ranges", perm_data_range);
27
28 char *show_rl(struct range_list *list)
29 {
30 struct data_range *tmp;
31 char full[256];
32 int i = 0;
33
34 full[0] = '\0';
35 full[255] = '\0';
36 FOR_EACH_PTR(list, tmp) {
37 if (i++)
38 strncat(full, ",", 254 - strlen(full));
39 if (sval_cmp(tmp->min, tmp->max) == 0) {
40 strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
41 continue;
42 }
43 strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
44 strncat(full, "-", 254 - strlen(full));
45 strncat(full, sval_to_str(tmp->max), 254 - strlen(full));
46 } END_FOR_EACH_PTR(tmp);
47 return alloc_sname(full);
48 }
49
50 static int str_to_comparison_arg_helper(const char *str,
51 struct expression *call, int *comparison,
52 struct expression **arg, char **endp)
53 {
54 int param;
55 char *c = (char *)str;
56
57 if (*c != '[')
58 return 0;
59 c++;
60
61 if (*c == '<') {
62 c++;
63 if (*c == '=') {
64 *comparison = SPECIAL_LTE;
65 c++;
66 } else {
67 *comparison = '<';
68 }
69 } else if (*c == '=') {
70 c++;
71 c++;
72 *comparison = SPECIAL_EQUAL;
73 } else if (*c == '>') {
74 c++;
75 if (*c == '=') {
76 *comparison = SPECIAL_GTE;
77 c++;
78 } else {
79 *comparison = '>';
80 }
81 } else if (*c == '!') {
82 c++;
83 c++;
84 *comparison = SPECIAL_NOTEQUAL;
85 } else {
86 return 0;
87 }
88
89 if (*c != '$')
90 return 0;
91 c++;
92
93 param = strtoll(c, &c, 10);
94 c++; /* skip the ']' character */
95 if (endp)
96 *endp = (char *)c;
97
98 if (!call)
99 return 0;
100 *arg = get_argument_from_call_expr(call->args, param);
101 if (!*arg)
102 return 0;
103 return 1;
104 }
105
106 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
107 {
108 while (1) {
109 if (!*str)
110 return 0;
111 if (*str == '[')
112 break;
113 str++;
114 }
115 return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
116 }
117
118 static int get_val_from_key(int use_max, struct symbol *type, char *c, struct expression *call, char **endp, sval_t *sval)
119 {
120 struct expression *arg;
121 int comparison;
122 sval_t ret, tmp;
123
124 if (use_max)
125 ret = sval_type_max(type);
126 else
127 ret = sval_type_min(type);
128
129 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp)) {
130 *sval = ret;
131 return 0;
132 }
133
134 if (use_max && get_implied_max(arg, &tmp)) {
135 ret = tmp;
136 if (comparison == '<') {
137 tmp.value = 1;
138 ret = sval_binop(ret, '-', tmp);
139 }
140 }
141 if (!use_max && get_implied_min(arg, &tmp)) {
142 ret = tmp;
143 if (comparison == '>') {
144 tmp.value = 1;
145 ret = sval_binop(ret, '+', tmp);
146 }
147 }
148
149 *sval = ret;
150 return 1;
151 }
152
153 static sval_t add_one(sval_t sval)
154 {
155 sval.value++;
156 return sval;
157 }
158
159 static sval_t sub_one(sval_t sval)
160 {
161 sval.value--;
162 return sval;
163 }
164
165 void filter_by_comparison(struct range_list **rl, int comparison, struct range_list *right)
166 {
167 struct range_list *left_orig = *rl;
168 struct range_list *right_orig = right;
169 struct range_list *ret_rl = *rl;
170 struct symbol *cast_type;
171 sval_t min, max;
172
173 cast_type = rl_type(left_orig);
174 if (sval_type_max(rl_type(left_orig)).uvalue < sval_type_max(rl_type(right_orig)).uvalue)
175 cast_type = rl_type(right_orig);
176 if (sval_type_max(cast_type).uvalue < INT_MAX)
177 cast_type = &int_ctype;
178
179 min = sval_type_min(cast_type);
180 max = sval_type_max(cast_type);
181 left_orig = cast_rl(cast_type, left_orig);
182 right_orig = cast_rl(cast_type, right_orig);
183
184 switch (comparison) {
185 case '<':
186 case SPECIAL_UNSIGNED_LT:
187 ret_rl = remove_range(left_orig, rl_max(right_orig), max);
188 break;
189 case SPECIAL_LTE:
190 case SPECIAL_UNSIGNED_LTE:
191 if (!sval_is_max(rl_max(right_orig)))
192 ret_rl = remove_range(left_orig, add_one(rl_max(right_orig)), max);
193 break;
194 case SPECIAL_EQUAL:
195 if (!sval_is_max(rl_max(right_orig)))
196 ret_rl = remove_range(ret_rl, add_one(rl_max(right_orig)), max);
197 if (!sval_is_min(rl_min(right_orig)))
198 ret_rl = remove_range(ret_rl, min, sub_one(rl_min(right_orig)));
199 break;
200 case SPECIAL_GTE:
201 case SPECIAL_UNSIGNED_GTE:
202 if (!sval_is_min(rl_min(right_orig)))
203 ret_rl = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
204 break;
205 case '>':
206 case SPECIAL_UNSIGNED_GT:
207 ret_rl = remove_range(left_orig, min, rl_min(right_orig));
208 break;
209 case SPECIAL_NOTEQUAL:
210 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
211 ret_rl = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
212 break;
213 default:
214 sm_msg("internal error: unhandled comparison %s", show_special(comparison));
215 return;
216 }
217
218 *rl = cast_rl(rl_type(*rl), ret_rl);
219 }
220
221 static struct range_list *filter_by_comparison_call(char *c, struct expression *call, char **endp, struct range_list *start_rl)
222 {
223 struct expression *arg;
224 struct range_list *right_orig;
225 int comparison;
226
227 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
228 return 0;
229
230 if (!get_implied_rl(arg, &right_orig))
231 return 0;
232
233 filter_by_comparison(&start_rl, comparison, right_orig);
234 return start_rl;
235 }
236
237 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, char *c, char **endp)
238 {
239 char *start = c;
240 sval_t ret;
241
242 if (!strncmp(start, "max", 3)) {
243 ret = sval_type_max(type);
244 c += 3;
245 } else if (!strncmp(start, "u64max", 6)) {
246 ret = sval_type_val(type, ULLONG_MAX);
247 c += 6;
248 } else if (!strncmp(start, "s64max", 6)) {
249 ret = sval_type_val(type, LLONG_MAX);
250 c += 6;
251 } else if (!strncmp(start, "u32max", 6)) {
252 ret = sval_type_val(type, UINT_MAX);
253 c += 6;
254 } else if (!strncmp(start, "s32max", 6)) {
255 ret = sval_type_val(type, INT_MAX);
256 c += 6;
257 } else if (!strncmp(start, "u16max", 6)) {
258 ret = sval_type_val(type, USHRT_MAX);
259 c += 6;
260 } else if (!strncmp(start, "s16max", 6)) {
261 ret = sval_type_val(type, SHRT_MAX);
262 c += 6;
263 } else if (!strncmp(start, "min", 3)) {
264 ret = sval_type_min(type);
265 c += 3;
266 } else if (!strncmp(start, "s64min", 6)) {
267 ret = sval_type_val(type, LLONG_MIN);
268 c += 6;
269 } else if (!strncmp(start, "s32min", 6)) {
270 ret = sval_type_val(type, INT_MIN);
271 c += 6;
272 } else if (!strncmp(start, "s16min", 6)) {
273 ret = sval_type_val(type, SHRT_MIN);
274 c += 6;
275 } else if (!strncmp(start, "long_min", 8)) {
276 ret = sval_type_val(type, LONG_MIN);
277 c += 8;
278 } else if (!strncmp(start, "long_max", 8)) {
279 ret = sval_type_val(type, LONG_MAX);
280 c += 8;
281 } else if (!strncmp(start, "ulong_max", 9)) {
282 ret = sval_type_val(type, ULONG_MAX);
283 c += 8;
284 } else if (!strncmp(start, "ptr_max", 7)) {
285 ret = sval_type_val(type, valid_ptr_max);
286 c += 8;
287 } else if (start[0] == '[') {
288 /* this parses [==p0] comparisons */
289 get_val_from_key(1, type, start, call, &c, &ret);
290 } else {
291 ret = sval_type_val(type, strtoll(start, &c, 10));
292 }
293 *endp = c;
294 return ret;
295 }
296
297 static char *jump_to_call_math(char *value)
298 {
299 char *c = value;
300
301 while (*c && *c != '[')
302 c++;
303
304 if (!*c)
305 return NULL;
306 c++;
307 if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
308 return NULL;
309
310 return c;
311 }
312
313 static void str_to_rl_helper(struct expression *call, struct symbol *type, char *value, struct range_list **rl)
314 {
315 sval_t min, max;
316 char *call_math;
317 char *c;
318
319 if (!type)
320 type = &llong_ctype;
321 *rl = NULL;
322
323 if (strcmp(value, "empty") == 0)
324 return;
325
326 if (strncmp(value, "[==$", 4) == 0) {
327 struct expression *arg;
328 int comparison;
329
330 if (!str_to_comparison_arg(value, call, &comparison, &arg))
331 return;
332 if (!get_implied_rl(arg, rl))
333 return;
334 goto cast;
335 }
336
337 call_math = jump_to_call_math(value);
338 if (call_math && parse_call_math_rl(call, call_math, rl))
339 goto cast;
340
341 min = sval_type_min(type);
342 max = sval_type_max(type);
343 c = value;
344 while (*c != '\0' && *c != '[') {
345 if (*c == '(')
346 c++;
347 min = parse_val(0, call, type, c, &c);
348 max = min;
349 if (*c == ')')
350 c++;
351 if (*c == '\0' || *c == '[') {
352 add_range(rl, min, min);
353 break;
354 }
355 if (*c == ',') {
356 add_range(rl, min, min);
357 c++;
358 continue;
359 }
360 if (*c != '-') {
361 sm_msg("debug XXX: trouble parsing %s c = %s", value, c);
362 break;
363 }
364 c++;
365 if (*c == '(')
366 c++;
367 max = parse_val(1, call, type, c, &c);
368 add_range(rl, min, max);
369 if (*c == ')')
370 c++;
371 if (*c == ',')
372 c++;
373 }
374
375 if (*c == '\0')
376 goto cast;
377
378 /*
379 * For now if we already tried to handle the call math and couldn't
380 * figure it out then bail.
381 */
382 if (jump_to_call_math(c) == c + 1)
383 goto cast;
384
385
386 *rl = filter_by_comparison_call(c, call, &c, *rl);
387
388 cast:
389 *rl = cast_rl(type, *rl);
390 }
391
392 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
393 {
394 return str_to_rl_helper(NULL, type, value, rl);
395 }
396
397 void call_results_to_rl(struct expression *expr, struct symbol *type, char *value, struct range_list **rl)
398 {
399 return str_to_rl_helper(strip_expr(expr), type, value, rl);
400 }
401
402 int is_whole_rl(struct range_list *rl)
403 {
404 struct data_range *drange;
405
406 if (ptr_list_empty(rl))
407 return 0;
408 drange = first_ptr_list((struct ptr_list *)rl);
409 if (sval_is_min(drange->min) && sval_is_max(drange->max))
410 return 1;
411 return 0;
412 }
413
414 sval_t rl_min(struct range_list *rl)
415 {
416 struct data_range *drange;
417 sval_t ret;
418
419 ret.type = &llong_ctype;
420 ret.value = LLONG_MIN;
421 if (ptr_list_empty(rl))
422 return ret;
423 drange = first_ptr_list((struct ptr_list *)rl);
424 return drange->min;
425 }
426
427 sval_t rl_max(struct range_list *rl)
428 {
429 struct data_range *drange;
430 sval_t ret;
431
432 ret.type = &llong_ctype;
433 ret.value = LLONG_MAX;
434 if (ptr_list_empty(rl))
435 return ret;
436 drange = last_ptr_list((struct ptr_list *)rl);
437 return drange->max;
438 }
439
440 int rl_to_sval(struct range_list *rl, sval_t *sval)
441 {
442 sval_t min, max;
443
444 if (!rl)
445 return 0;
446
447 min = rl_min(rl);
448 max = rl_max(rl);
449 if (sval_cmp(min, max) != 0)
450 return 0;
451 *sval = min;
452 return 1;
453 }
454
455 struct symbol *rl_type(struct range_list *rl)
456 {
457 if (!rl)
458 return NULL;
459 return rl_min(rl).type;
460 }
461
462 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
463 {
464 struct data_range *ret;
465
466 if (perm)
467 ret = __alloc_perm_data_range(0);
468 else
469 ret = __alloc_data_range(0);
470 ret->min = min;
471 ret->max = max;
472 return ret;
473 }
474
475 struct data_range *alloc_range(sval_t min, sval_t max)
476 {
477 return alloc_range_helper_sval(min, max, 0);
478 }
479
480 struct data_range *alloc_range_perm(sval_t min, sval_t max)
481 {
482 return alloc_range_helper_sval(min, max, 1);
483 }
484
485 struct range_list *alloc_rl(sval_t min, sval_t max)
486 {
487 struct range_list *rl = NULL;
488
489 if (sval_cmp(min, max) > 0)
490 return alloc_whole_rl(min.type);
491
492 add_range(&rl, min, max);
493 return rl;
494 }
495
496 struct range_list *alloc_whole_rl(struct symbol *type)
497 {
498 if (!type || type_positive_bits(type) < 0)
499 type = &llong_ctype;
500 if (type->type == SYM_ARRAY)
501 type = &ptr_ctype;
502
503 return alloc_rl(sval_type_min(type), sval_type_max(type));
504 }
505
506 void add_range(struct range_list **list, sval_t min, sval_t max)
507 {
508 struct data_range *tmp = NULL;
509 struct data_range *new = NULL;
510 int check_next = 0;
511
512 /*
513 * FIXME: This has a problem merging a range_list like: min-0,3-max
514 * with a range like 1-2. You end up with min-2,3-max instead of
515 * just min-max.
516 */
517 FOR_EACH_PTR(*list, tmp) {
518 if (check_next) {
519 /* Sometimes we overlap with more than one range
520 so we have to delete or modify the next range. */
521 if (max.value + 1 == tmp->min.value) {
522 /* join 2 ranges here */
523 new->max = tmp->max;
524 DELETE_CURRENT_PTR(tmp);
525 return;
526 }
527
528 /* Doesn't overlap with the next one. */
529 if (sval_cmp(max, tmp->min) < 0)
530 return;
531 /* Partially overlaps with the next one. */
532 if (sval_cmp(max, tmp->max) < 0) {
533 tmp->min.value = max.value + 1;
534 return;
535 }
536 /* Completely overlaps with the next one. */
537 if (sval_cmp(max, tmp->max) >= 0) {
538 DELETE_CURRENT_PTR(tmp);
539 /* there could be more ranges to delete */
540 continue;
541 }
542 }
543 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
544 /* join 2 ranges into a big range */
545 new = alloc_range(min, tmp->max);
546 REPLACE_CURRENT_PTR(tmp, new);
547 return;
548 }
549 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
550 new = alloc_range(min, max);
551 INSERT_CURRENT(new, tmp);
552 return;
553 }
554 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
555 if (sval_cmp(max, tmp->max) < 0)
556 max = tmp->max;
557 else
558 check_next = 1;
559 new = alloc_range(min, max);
560 REPLACE_CURRENT_PTR(tmp, new);
561 if (!check_next)
562 return;
563 continue;
564 }
565 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
566 return;
567 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
568 min = tmp->min;
569 new = alloc_range(min, max);
570 REPLACE_CURRENT_PTR(tmp, new);
571 check_next = 1;
572 continue;
573 }
574 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
575 /* join 2 ranges into a big range */
576 new = alloc_range(tmp->min, max);
577 REPLACE_CURRENT_PTR(tmp, new);
578 check_next = 1;
579 continue;
580 }
581 /* the new range is entirely above the existing ranges */
582 } END_FOR_EACH_PTR(tmp);
583 if (check_next)
584 return;
585 new = alloc_range(min, max);
586 add_ptr_list(list, new);
587 }
588
589 struct range_list *clone_rl(struct range_list *list)
590 {
591 struct data_range *tmp;
592 struct range_list *ret = NULL;
593
594 FOR_EACH_PTR(list, tmp) {
595 add_ptr_list(&ret, tmp);
596 } END_FOR_EACH_PTR(tmp);
597 return ret;
598 }
599
600 struct range_list *clone_rl_permanent(struct range_list *list)
601 {
602 struct data_range *tmp;
603 struct data_range *new;
604 struct range_list *ret = NULL;
605
606 FOR_EACH_PTR(list, tmp) {
607 new = alloc_range_perm(tmp->min, tmp->max);
608 add_ptr_list(&ret, new);
609 } END_FOR_EACH_PTR(tmp);
610 return ret;
611 }
612
613 struct range_list *rl_union(struct range_list *one, struct range_list *two)
614 {
615 struct data_range *tmp;
616 struct range_list *ret = NULL;
617
618 FOR_EACH_PTR(one, tmp) {
619 add_range(&ret, tmp->min, tmp->max);
620 } END_FOR_EACH_PTR(tmp);
621 FOR_EACH_PTR(two, tmp) {
622 add_range(&ret, tmp->min, tmp->max);
623 } END_FOR_EACH_PTR(tmp);
624 return ret;
625 }
626
627 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
628 {
629 struct data_range *tmp;
630 struct range_list *ret = NULL;
631
632 FOR_EACH_PTR(list, tmp) {
633 if (sval_cmp(tmp->max, min) < 0) {
634 add_range(&ret, tmp->min, tmp->max);
635 continue;
636 }
637 if (sval_cmp(tmp->min, max) > 0) {
638 add_range(&ret, tmp->min, tmp->max);
639 continue;
640 }
641 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
642 continue;
643 if (sval_cmp(tmp->min, min) >= 0) {
644 max.value++;
645 add_range(&ret, max, tmp->max);
646 } else if (sval_cmp(tmp->max, max) <= 0) {
647 min.value--;
648 add_range(&ret, tmp->min, min);
649 } else {
650 min.value--;
651 max.value++;
652 add_range(&ret, tmp->min, min);
653 add_range(&ret, max, tmp->max);
654 }
655 } END_FOR_EACH_PTR(tmp);
656 return ret;
657 }
658
659 int ranges_equiv(struct data_range *one, struct data_range *two)
660 {
661 if (!one && !two)
662 return 1;
663 if (!one || !two)
664 return 0;
665 if (sval_cmp(one->min, two->min) != 0)
666 return 0;
667 if (sval_cmp(one->max, two->max) != 0)
668 return 0;
669 return 1;
670 }
671
672 int rl_equiv(struct range_list *one, struct range_list *two)
673 {
674 struct data_range *one_range;
675 struct data_range *two_range;
676
677 if (one == two)
678 return 1;
679
680 PREPARE_PTR_LIST(one, one_range);
681 PREPARE_PTR_LIST(two, two_range);
682 for (;;) {
683 if (!one_range && !two_range)
684 return 1;
685 if (!ranges_equiv(one_range, two_range))
686 return 0;
687 NEXT_PTR_LIST(one_range);
688 NEXT_PTR_LIST(two_range);
689 }
690 FINISH_PTR_LIST(two_range);
691 FINISH_PTR_LIST(one_range);
692
693 return 1;
694 }
695
696 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
697 {
698 switch (comparison) {
699 case '<':
700 case SPECIAL_UNSIGNED_LT:
701 if (sval_cmp(left->min, right->max) < 0)
702 return 1;
703 return 0;
704 case SPECIAL_UNSIGNED_LTE:
705 case SPECIAL_LTE:
706 if (sval_cmp(left->min, right->max) <= 0)
707 return 1;
708 return 0;
709 case SPECIAL_EQUAL:
710 if (sval_cmp(left->max, right->min) < 0)
711 return 0;
712 if (sval_cmp(left->min, right->max) > 0)
713 return 0;
714 return 1;
715 case SPECIAL_UNSIGNED_GTE:
716 case SPECIAL_GTE:
717 if (sval_cmp(left->max, right->min) >= 0)
718 return 1;
719 return 0;
720 case '>':
721 case SPECIAL_UNSIGNED_GT:
722 if (sval_cmp(left->max, right->min) > 0)
723 return 1;
724 return 0;
725 case SPECIAL_NOTEQUAL:
726 if (sval_cmp(left->min, left->max) != 0)
727 return 1;
728 if (sval_cmp(right->min, right->max) != 0)
729 return 1;
730 if (sval_cmp(left->min, right->min) != 0)
731 return 1;
732 return 0;
733 default:
734 sm_msg("unhandled comparison %d\n", comparison);
735 return 0;
736 }
737 return 0;
738 }
739
740 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
741 {
742 if (left)
743 return true_comparison_range(var, comparison, val);
744 else
745 return true_comparison_range(val, comparison, var);
746 }
747
748 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
749 {
750 switch (comparison) {
751 case '<':
752 case SPECIAL_UNSIGNED_LT:
753 if (sval_cmp(left->max, right->min) >= 0)
754 return 1;
755 return 0;
756 case SPECIAL_UNSIGNED_LTE:
757 case SPECIAL_LTE:
758 if (sval_cmp(left->max, right->min) > 0)
759 return 1;
760 return 0;
761 case SPECIAL_EQUAL:
762 if (sval_cmp(left->min, left->max) != 0)
763 return 1;
764 if (sval_cmp(right->min, right->max) != 0)
765 return 1;
766 if (sval_cmp(left->min, right->min) != 0)
767 return 1;
768 return 0;
769 case SPECIAL_UNSIGNED_GTE:
770 case SPECIAL_GTE:
771 if (sval_cmp(left->min, right->max) < 0)
772 return 1;
773 return 0;
774 case '>':
775 case SPECIAL_UNSIGNED_GT:
776 if (sval_cmp(left->min, right->max) <= 0)
777 return 1;
778 return 0;
779 case SPECIAL_NOTEQUAL:
780 if (sval_cmp(left->max, right->min) < 0)
781 return 0;
782 if (sval_cmp(left->min, right->max) > 0)
783 return 0;
784 return 1;
785 default:
786 sm_msg("unhandled comparison %d\n", comparison);
787 return 0;
788 }
789 return 0;
790 }
791
792 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
793 {
794 if (left)
795 return false_comparison_range_sval(var, comparison, val);
796 else
797 return false_comparison_range_sval(val, comparison, var);
798 }
799
800 int possibly_true(struct expression *left, int comparison, struct expression *right)
801 {
802 struct range_list *rl_left, *rl_right;
803 struct data_range *tmp_left, *tmp_right;
804
805 if (!get_implied_rl(left, &rl_left))
806 return 1;
807 if (!get_implied_rl(right, &rl_right))
808 return 1;
809
810 FOR_EACH_PTR(rl_left, tmp_left) {
811 FOR_EACH_PTR(rl_right, tmp_right) {
812 if (true_comparison_range(tmp_left, comparison, tmp_right))
813 return 1;
814 } END_FOR_EACH_PTR(tmp_right);
815 } END_FOR_EACH_PTR(tmp_left);
816 return 0;
817 }
818
819 int possibly_false(struct expression *left, int comparison, struct expression *right)
820 {
821 struct range_list *rl_left, *rl_right;
822 struct data_range *tmp_left, *tmp_right;
823
824 if (!get_implied_rl(left, &rl_left))
825 return 1;
826 if (!get_implied_rl(right, &rl_right))
827 return 1;
828
829 FOR_EACH_PTR(rl_left, tmp_left) {
830 FOR_EACH_PTR(rl_right, tmp_right) {
831 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
832 return 1;
833 } END_FOR_EACH_PTR(tmp_right);
834 } END_FOR_EACH_PTR(tmp_left);
835 return 0;
836 }
837
838 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
839 {
840 struct data_range *left_tmp, *right_tmp;
841
842 if (!left_ranges || !right_ranges)
843 return 1;
844
845 FOR_EACH_PTR(left_ranges, left_tmp) {
846 FOR_EACH_PTR(right_ranges, right_tmp) {
847 if (true_comparison_range(left_tmp, comparison, right_tmp))
848 return 1;
849 } END_FOR_EACH_PTR(right_tmp);
850 } END_FOR_EACH_PTR(left_tmp);
851 return 0;
852 }
853
854 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
855 {
856 struct data_range *left_tmp, *right_tmp;
857
858 if (!left_ranges || !right_ranges)
859 return 1;
860
861 FOR_EACH_PTR(left_ranges, left_tmp) {
862 FOR_EACH_PTR(right_ranges, right_tmp) {
863 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
864 return 1;
865 } END_FOR_EACH_PTR(right_tmp);
866 } END_FOR_EACH_PTR(left_tmp);
867 return 0;
868 }
869
870 /* FIXME: the _rl here stands for right left so really it should be _lr */
871 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
872 {
873 if (left)
874 return possibly_true_rl(a, comparison, b);
875 else
876 return possibly_true_rl(b, comparison, a);
877 }
878
879 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
880 {
881 if (left)
882 return possibly_false_rl(a, comparison, b);
883 else
884 return possibly_false_rl(b, comparison, a);
885 }
886
887 int rl_has_sval(struct range_list *rl, sval_t sval)
888 {
889 struct data_range *tmp;
890
891 FOR_EACH_PTR(rl, tmp) {
892 if (sval_cmp(tmp->min, sval) <= 0 &&
893 sval_cmp(tmp->max, sval) >= 0)
894 return 1;
895 } END_FOR_EACH_PTR(tmp);
896 return 0;
897 }
898
899 void tack_on(struct range_list **list, struct data_range *drange)
900 {
901 add_ptr_list(list, drange);
902 }
903
904 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
905 {
906 add_ptr_list(rl_stack, rl);
907 }
908
909 struct range_list *pop_rl(struct range_list_stack **rl_stack)
910 {
911 struct range_list *rl;
912
913 rl = last_ptr_list((struct ptr_list *)*rl_stack);
914 delete_ptr_list_last((struct ptr_list **)rl_stack);
915 return rl;
916 }
917
918 struct range_list *top_rl(struct range_list_stack *rl_stack)
919 {
920 struct range_list *rl;
921
922 rl = last_ptr_list((struct ptr_list *)rl_stack);
923 return rl;
924 }
925
926 void filter_top_rl(struct range_list_stack **rl_stack, sval_t sval)
927 {
928 struct range_list *rl;
929
930 rl = pop_rl(rl_stack);
931 rl = remove_range(rl, sval, sval);
932 push_rl(rl_stack, rl);
933 }
934
935 static int sval_too_big(struct symbol *type, sval_t sval)
936 {
937 if (type_bits(type) == 64)
938 return 0;
939 if (sval.uvalue > ((1ULL << type_bits(type)) - 1))
940 return 1;
941 return 0;
942 }
943
944 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
945 {
946 /* If we're just adding a number, cast it and add it */
947 if (sval_cmp(min, max) == 0) {
948 add_range(rl, sval_cast(type, min), sval_cast(type, max));
949 return;
950 }
951
952 /* If the range is within the type range then add it */
953 if (sval_fits(type, min) && sval_fits(type, max)) {
954 add_range(rl, sval_cast(type, min), sval_cast(type, max));
955 return;
956 }
957
958 /*
959 * If the range we are adding has more bits than the range type then
960 * add the whole range type. Eg:
961 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
962 * This isn't totally the right thing to do. We could be more granular.
963 */
964 if (sval_too_big(type, min) || sval_too_big(type, max)) {
965 add_range(rl, sval_type_min(type), sval_type_max(type));
966 return;
967 }
968
969 /* Cast negative values to high positive values */
970 if (sval_is_negative(min) && type_unsigned(type)) {
971 if (sval_is_positive(max)) {
972 if (sval_too_high(type, max)) {
973 add_range(rl, sval_type_min(type), sval_type_max(type));
974 return;
975 }
976 add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
977 max = sval_type_max(type);
978 } else {
979 max = sval_cast(type, max);
980 }
981 min = sval_cast(type, min);
982 add_range(rl, min, max);
983 }
984
985 /* Cast high positive numbers to negative */
986 if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
987 if (!sval_is_negative(sval_cast(type, min))) {
988 add_range(rl, sval_cast(type, min), sval_type_max(type));
989 min = sval_type_min(type);
990 } else {
991 min = sval_cast(type, min);
992 }
993 max = sval_cast(type, max);
994 add_range(rl, min, max);
995 }
996
997 return;
998 }
999
1000 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1001 {
1002 struct data_range *tmp;
1003 struct range_list *ret = NULL;
1004 sval_t min, max;
1005
1006 if (!rl)
1007 return NULL;
1008
1009 if (!type || type == rl_type(rl))
1010 return rl;
1011
1012 FOR_EACH_PTR(rl, tmp) {
1013 min = tmp->min;
1014 max = tmp->max;
1015 if (type_bits(type) < type_bits(rl_type(rl))) {
1016 min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1017 max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1018 }
1019 if (sval_cmp(min, max) > 0) {
1020 min = sval_cast(type, min);
1021 max = sval_cast(type, max);
1022 }
1023 add_range_t(type, &ret, min, max);
1024 } END_FOR_EACH_PTR(tmp);
1025
1026 return ret;
1027 }
1028
1029 static int rl_is_sane(struct range_list *rl)
1030 {
1031 struct data_range *tmp;
1032 struct symbol *type;
1033
1034 type = rl_type(rl);
1035 FOR_EACH_PTR(rl, tmp) {
1036 if (!sval_fits(type, tmp->min))
1037 return 0;
1038 if (!sval_fits(type, tmp->max))
1039 return 0;
1040 if (sval_cmp(tmp->min, tmp->max) > 0)
1041 return 0;
1042 } END_FOR_EACH_PTR(tmp);
1043
1044 return 1;
1045 }
1046
1047 static int rl_type_consistent(struct range_list *rl)
1048 {
1049 struct data_range *tmp;
1050 struct symbol *type;
1051
1052 type = rl_type(rl);
1053 FOR_EACH_PTR(rl, tmp) {
1054 if (type != tmp->min.type || type != tmp->max.type)
1055 return 0;
1056 } END_FOR_EACH_PTR(tmp);
1057 return 1;
1058 }
1059
1060 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1061 {
1062 struct data_range *tmp;
1063 struct range_list *ret = NULL;
1064
1065 if (!rl)
1066 return NULL;
1067
1068 if (!type)
1069 return rl;
1070 if (!rl_is_sane(rl))
1071 return alloc_whole_rl(type);
1072 if (type == rl_type(rl) && rl_type_consistent(rl))
1073 return rl;
1074
1075 FOR_EACH_PTR(rl, tmp) {
1076 add_range_t(type, &ret, tmp->min, tmp->max);
1077 } END_FOR_EACH_PTR(tmp);
1078
1079 if (!ret)
1080 return alloc_whole_rl(type);
1081
1082 return ret;
1083 }
1084
1085 struct range_list *rl_invert(struct range_list *orig)
1086 {
1087 struct range_list *ret = NULL;
1088 struct data_range *tmp;
1089 sval_t gap_min, abs_max, sval;
1090
1091 if (!orig)
1092 return NULL;
1093
1094 gap_min = sval_type_min(rl_min(orig).type);
1095 abs_max = sval_type_max(rl_max(orig).type);
1096
1097 FOR_EACH_PTR(orig, tmp) {
1098 if (sval_cmp(tmp->min, gap_min) > 0) {
1099 sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
1100 add_range(&ret, gap_min, sval);
1101 }
1102 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
1103 if (sval_cmp(tmp->max, abs_max) == 0)
1104 gap_min = abs_max;
1105 } END_FOR_EACH_PTR(tmp);
1106
1107 if (sval_cmp(gap_min, abs_max) < 0)
1108 add_range(&ret, gap_min, abs_max);
1109
1110 return ret;
1111 }
1112
1113 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1114 {
1115 struct data_range *tmp;
1116
1117 FOR_EACH_PTR(filter, tmp) {
1118 rl = remove_range(rl, tmp->min, tmp->max);
1119 } END_FOR_EACH_PTR(tmp);
1120
1121 return rl;
1122 }
1123
1124 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1125 {
1126 struct range_list *one_orig;
1127 struct range_list *two_orig;
1128 struct range_list *ret;
1129 struct symbol *ret_type;
1130 struct symbol *small_type;
1131 struct symbol *large_type;
1132
1133 if (!two)
1134 return NULL;
1135 if (!one)
1136 return NULL;
1137
1138 one_orig = one;
1139 two_orig = two;
1140
1141 ret_type = rl_type(one);
1142 small_type = rl_type(one);
1143 large_type = rl_type(two);
1144
1145 if (type_bits(rl_type(two)) < type_bits(small_type)) {
1146 small_type = rl_type(two);
1147 large_type = rl_type(one);
1148 }
1149
1150 one = cast_rl(large_type, one);
1151 two = cast_rl(large_type, two);
1152
1153 ret = one;
1154 one = rl_invert(one);
1155 two = rl_invert(two);
1156
1157 ret = rl_filter(ret, one);
1158 ret = rl_filter(ret, two);
1159
1160 one = cast_rl(small_type, one_orig);
1161 two = cast_rl(small_type, two_orig);
1162
1163 one = rl_invert(one);
1164 two = rl_invert(two);
1165
1166 ret = cast_rl(small_type, ret);
1167 ret = rl_filter(ret, one);
1168 ret = rl_filter(ret, two);
1169
1170 return cast_rl(ret_type, ret);
1171 }
1172
1173 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1174 {
1175 sval_t zero;
1176 sval_t max;
1177
1178 max = rl_max(right);
1179 if (sval_is_max(max))
1180 return left;
1181 if (max.value == 0)
1182 return NULL;
1183 max.value--;
1184 if (sval_is_negative(max))
1185 return NULL;
1186 if (sval_cmp(rl_max(left), max) < 0)
1187 return left;
1188 zero = max;
1189 zero.value = 0;
1190 return alloc_rl(zero, max);
1191 }
1192
1193 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1194 {
1195 sval_t min, max;
1196
1197 if (sval_is_max(rl_max(left)))
1198 return NULL;
1199 if (sval_is_max(rl_max(right)))
1200 return NULL;
1201
1202 if (sval_is_negative(rl_min(left)))
1203 return NULL;
1204 if (sval_cmp_val(rl_min(right), 0) <= 0)
1205 return NULL;
1206
1207 max = sval_binop(rl_max(left), '/', rl_min(right));
1208 min = sval_binop(rl_min(left), '/', rl_max(right));
1209
1210 return alloc_rl(min, max);
1211 }
1212
1213 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1214 {
1215 sval_t min, max;
1216
1217 if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1218 return NULL;
1219 min = sval_binop(rl_min(left), op, rl_min(right));
1220
1221 if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1222 return NULL;
1223 max = sval_binop(rl_max(left), op, rl_max(right));
1224
1225 return alloc_rl(min, max);
1226 }
1227
1228 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1229 {
1230 struct symbol *cast_type;
1231 sval_t left_sval, right_sval;
1232 struct range_list *ret = NULL;
1233
1234 cast_type = rl_type(left);
1235 if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
1236 cast_type = rl_type(right);
1237 if (sval_type_max(cast_type).uvalue < INT_MAX)
1238 cast_type = &int_ctype;
1239
1240 left = cast_rl(cast_type, left);
1241 right = cast_rl(cast_type, right);
1242
1243 if (!left || !right)
1244 return alloc_whole_rl(cast_type);
1245
1246 if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
1247 sval_t val = sval_binop(left_sval, op, right_sval);
1248 return alloc_rl(val, val);
1249 }
1250
1251 switch (op) {
1252 case '%':
1253 ret = handle_mod_rl(left, right);
1254 break;
1255 case '/':
1256 ret = handle_divide_rl(left, right);
1257 break;
1258 case '*':
1259 case '+':
1260 ret = handle_add_mult_rl(left, op, right);
1261 break;
1262
1263 /* FIXME: Do the rest as well */
1264 case '-':
1265 case '|':
1266 case '&':
1267 case SPECIAL_RIGHTSHIFT:
1268 case SPECIAL_LEFTSHIFT:
1269 case '^':
1270 break;
1271 }
1272
1273 if (!ret)
1274 ret = alloc_whole_rl(cast_type);
1275 return ret;
1276 }
1277
1278 void free_rl(struct range_list **rlist)
1279 {
1280 __free_ptr_list((struct ptr_list **)rlist);
1281 }
1282
1283 static void free_single_dinfo(struct data_info *dinfo)
1284 {
1285 free_rl(&dinfo->value_ranges);
1286 }
1287
1288 static void free_dinfos(struct allocation_blob *blob)
1289 {
1290 unsigned int size = sizeof(struct data_info);
1291 unsigned int offset = 0;
1292
1293 while (offset < blob->offset) {
1294 free_single_dinfo((struct data_info *)(blob->data + offset));
1295 offset += size;
1296 }
1297 }
1298
1299 void free_data_info_allocs(void)
1300 {
1301 struct allocator_struct *desc = &data_info_allocator;
1302 struct allocation_blob *blob = desc->blobs;
1303
1304 desc->blobs = NULL;
1305 desc->allocations = 0;
1306 desc->total_bytes = 0;
1307 desc->useful_bytes = 0;
1308 desc->freelist = NULL;
1309 while (blob) {
1310 struct allocation_blob *next = blob->next;
1311 free_dinfos(blob);
1312 blob_free(blob, desc->chunking);
1313 blob = next;
1314 }
1315 clear_data_range_alloc();
1316 }
1317
Static analysis for C