buf_size, strlen: don't use strlen() to determine the buf size
[smatch.git] / smatch_ranges.c
blob0556bb40c65b1facea7d053de0c8e33a2123eea3
1 /*
2 * Copyright (C) 2009 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
18 #include "parse.h"
19 #include "smatch.h"
20 #include "smatch_extra.h"
21 #include "smatch_slist.h"
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);
28 char *show_rl(struct range_list *list)
30 struct data_range *tmp;
31 char full[256];
32 int i = 0;
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;
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);
50 static int sval_too_big(struct symbol *type, sval_t sval)
52 if (type_bits(type) == 64)
53 return 0;
54 if (sval.uvalue > ((1ULL << type_bits(type)) - 1))
55 return 1;
56 return 0;
59 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
61 /* If we're just adding a number, cast it and add it */
62 if (sval_cmp(min, max) == 0) {
63 add_range(rl, sval_cast(type, min), sval_cast(type, max));
64 return;
67 /* If the range is within the type range then add it */
68 if (sval_fits(type, min) && sval_fits(type, max)) {
69 add_range(rl, sval_cast(type, min), sval_cast(type, max));
70 return;
74 * If the range we are adding has more bits than the range type then
75 * add the whole range type. Eg:
76 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
77 * This isn't totally the right thing to do. We could be more granular.
79 if (sval_too_big(type, min) || sval_too_big(type, max)) {
80 add_range(rl, sval_type_min(type), sval_type_max(type));
81 return;
84 /* Cast negative values to high positive values */
85 if (sval_is_negative(min) && type_unsigned(type)) {
86 if (sval_is_positive(max)) {
87 if (sval_too_high(type, max)) {
88 add_range(rl, sval_type_min(type), sval_type_max(type));
89 return;
91 add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
92 max = sval_type_max(type);
93 } else {
94 max = sval_cast(type, max);
96 min = sval_cast(type, min);
97 add_range(rl, min, max);
100 /* Cast high positive numbers to negative */
101 if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
102 if (!sval_is_negative(sval_cast(type, min))) {
103 add_range(rl, sval_cast(type, min), sval_type_max(type));
104 min = sval_type_min(type);
105 } else {
106 min = sval_cast(type, min);
108 max = sval_cast(type, max);
109 add_range(rl, min, max);
112 add_range(rl, sval_cast(type, min), sval_cast(type, max));
113 return;
116 static int str_to_comparison_arg_helper(const char *str,
117 struct expression *call, int *comparison,
118 struct expression **arg, char **endp)
120 int param;
121 char *c = (char *)str;
123 if (*c != '[')
124 return 0;
125 c++;
127 if (*c == '<') {
128 c++;
129 if (*c == '=') {
130 *comparison = SPECIAL_LTE;
131 c++;
132 } else {
133 *comparison = '<';
135 } else if (*c == '=') {
136 c++;
137 c++;
138 *comparison = SPECIAL_EQUAL;
139 } else if (*c == '>') {
140 c++;
141 if (*c == '=') {
142 *comparison = SPECIAL_GTE;
143 c++;
144 } else {
145 *comparison = '>';
147 } else if (*c == '!') {
148 c++;
149 c++;
150 *comparison = SPECIAL_NOTEQUAL;
151 } else {
152 return 0;
155 if (*c != '$')
156 return 0;
157 c++;
159 param = strtoll(c, &c, 10);
160 c++; /* skip the ']' character */
161 if (endp)
162 *endp = (char *)c;
164 if (!call)
165 return 0;
166 *arg = get_argument_from_call_expr(call->args, param);
167 if (!*arg)
168 return 0;
169 return 1;
172 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
174 while (1) {
175 if (!*str)
176 return 0;
177 if (*str == '[')
178 break;
179 str++;
181 return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
184 static int get_val_from_key(int use_max, struct symbol *type, char *c, struct expression *call, char **endp, sval_t *sval)
186 struct expression *arg;
187 int comparison;
188 sval_t ret, tmp;
190 if (use_max)
191 ret = sval_type_max(type);
192 else
193 ret = sval_type_min(type);
195 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp)) {
196 *sval = ret;
197 return 0;
200 if (use_max && get_implied_max(arg, &tmp)) {
201 ret = tmp;
202 if (comparison == '<') {
203 tmp.value = 1;
204 ret = sval_binop(ret, '-', tmp);
207 if (!use_max && get_implied_min(arg, &tmp)) {
208 ret = tmp;
209 if (comparison == '>') {
210 tmp.value = 1;
211 ret = sval_binop(ret, '+', tmp);
215 *sval = ret;
216 return 1;
219 static sval_t add_one(sval_t sval)
221 sval.value++;
222 return sval;
225 static sval_t sub_one(sval_t sval)
227 sval.value--;
228 return sval;
231 void filter_by_comparison(struct range_list **rl, int comparison, struct range_list *right)
233 struct range_list *left_orig = *rl;
234 struct range_list *right_orig = right;
235 struct range_list *ret_rl = *rl;
236 struct symbol *cast_type;
237 sval_t min, max;
239 cast_type = rl_type(left_orig);
240 if (sval_type_max(rl_type(left_orig)).uvalue < sval_type_max(rl_type(right_orig)).uvalue)
241 cast_type = rl_type(right_orig);
242 if (sval_type_max(cast_type).uvalue < INT_MAX)
243 cast_type = &int_ctype;
245 min = sval_type_min(cast_type);
246 max = sval_type_max(cast_type);
247 left_orig = cast_rl(cast_type, left_orig);
248 right_orig = cast_rl(cast_type, right_orig);
250 switch (comparison) {
251 case '<':
252 case SPECIAL_UNSIGNED_LT:
253 ret_rl = remove_range(left_orig, rl_max(right_orig), max);
254 break;
255 case SPECIAL_LTE:
256 case SPECIAL_UNSIGNED_LTE:
257 if (!sval_is_max(rl_max(right_orig)))
258 ret_rl = remove_range(left_orig, add_one(rl_max(right_orig)), max);
259 break;
260 case SPECIAL_EQUAL:
261 if (!sval_is_max(rl_max(right_orig)))
262 ret_rl = remove_range(ret_rl, add_one(rl_max(right_orig)), max);
263 if (!sval_is_min(rl_min(right_orig)))
264 ret_rl = remove_range(ret_rl, min, sub_one(rl_min(right_orig)));
265 break;
266 case SPECIAL_GTE:
267 case SPECIAL_UNSIGNED_GTE:
268 if (!sval_is_min(rl_min(right_orig)))
269 ret_rl = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
270 break;
271 case '>':
272 case SPECIAL_UNSIGNED_GT:
273 ret_rl = remove_range(left_orig, min, rl_min(right_orig));
274 break;
275 case SPECIAL_NOTEQUAL:
276 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
277 ret_rl = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
278 break;
279 default:
280 sm_msg("internal error: unhandled comparison %s", show_special(comparison));
281 return;
284 *rl = cast_rl(rl_type(*rl), ret_rl);
287 static struct range_list *filter_by_comparison_call(char *c, struct expression *call, char **endp, struct range_list *start_rl)
289 struct expression *arg;
290 struct range_list *right_orig;
291 int comparison;
293 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
294 return NULL;
296 if (!get_implied_rl(arg, &right_orig))
297 return NULL;
299 filter_by_comparison(&start_rl, comparison, right_orig);
300 return start_rl;
303 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, char *c, char **endp)
305 char *start = c;
306 sval_t ret;
308 if (!strncmp(start, "max", 3)) {
309 ret = sval_type_max(type);
310 c += 3;
311 } else if (!strncmp(start, "u64max", 6)) {
312 ret = sval_type_val(type, ULLONG_MAX);
313 c += 6;
314 } else if (!strncmp(start, "s64max", 6)) {
315 ret = sval_type_val(type, LLONG_MAX);
316 c += 6;
317 } else if (!strncmp(start, "u32max", 6)) {
318 ret = sval_type_val(type, UINT_MAX);
319 c += 6;
320 } else if (!strncmp(start, "s32max", 6)) {
321 ret = sval_type_val(type, INT_MAX);
322 c += 6;
323 } else if (!strncmp(start, "u16max", 6)) {
324 ret = sval_type_val(type, USHRT_MAX);
325 c += 6;
326 } else if (!strncmp(start, "s16max", 6)) {
327 ret = sval_type_val(type, SHRT_MAX);
328 c += 6;
329 } else if (!strncmp(start, "min", 3)) {
330 ret = sval_type_min(type);
331 c += 3;
332 } else if (!strncmp(start, "s64min", 6)) {
333 ret = sval_type_val(type, LLONG_MIN);
334 c += 6;
335 } else if (!strncmp(start, "s32min", 6)) {
336 ret = sval_type_val(type, INT_MIN);
337 c += 6;
338 } else if (!strncmp(start, "s16min", 6)) {
339 ret = sval_type_val(type, SHRT_MIN);
340 c += 6;
341 } else if (!strncmp(start, "long_min", 8)) {
342 ret = sval_type_val(type, LONG_MIN);
343 c += 8;
344 } else if (!strncmp(start, "long_max", 8)) {
345 ret = sval_type_val(type, LONG_MAX);
346 c += 8;
347 } else if (!strncmp(start, "ulong_max", 9)) {
348 ret = sval_type_val(type, ULONG_MAX);
349 c += 8;
350 } else if (!strncmp(start, "ptr_max", 7)) {
351 ret = sval_type_val(type, valid_ptr_max);
352 c += 8;
353 } else if (start[0] == '[') {
354 /* this parses [==p0] comparisons */
355 get_val_from_key(1, type, start, call, &c, &ret);
356 } else {
357 ret = sval_type_val(type, strtoll(start, &c, 10));
359 *endp = c;
360 return ret;
363 static char *jump_to_call_math(char *value)
365 char *c = value;
367 while (*c && *c != '[')
368 c++;
370 if (!*c)
371 return NULL;
372 c++;
373 if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
374 return NULL;
376 return c;
379 static void str_to_rl_helper(struct expression *call, struct symbol *type, char *str, char **endp, struct range_list **rl)
381 struct range_list *rl_tmp = NULL;
382 sval_t min, max;
383 char *c;
385 min = sval_type_min(type);
386 max = sval_type_max(type);
387 c = str;
388 while (*c != '\0' && *c != '[') {
389 if (*c == '(')
390 c++;
391 min = parse_val(0, call, type, c, &c);
392 max = min;
393 if (*c == ')')
394 c++;
395 if (*c == '\0' || *c == '[') {
396 add_range_t(type, &rl_tmp, min, min);
397 break;
399 if (*c == ',') {
400 add_range_t(type, &rl_tmp, min, min);
401 c++;
402 continue;
404 if (*c != '-') {
405 sm_msg("debug XXX: trouble parsing %s c = %s", str, c);
406 break;
408 c++;
409 if (*c == '(')
410 c++;
411 max = parse_val(1, call, type, c, &c);
412 add_range_t(type, &rl_tmp, min, max);
413 if (*c == ')')
414 c++;
415 if (*c == ',')
416 c++;
419 *rl = rl_tmp;
420 *endp = c;
423 static void str_to_dinfo(struct expression *call, struct symbol *type, char *value, struct data_info *dinfo)
425 struct range_list *math_rl;
426 char *call_math;
427 char *c;
428 struct range_list *rl = NULL;
430 if (!type)
431 type = &llong_ctype;
433 if (strcmp(value, "empty") == 0)
434 return;
436 if (strncmp(value, "[==$", 4) == 0) {
437 struct expression *arg;
438 int comparison;
440 if (!str_to_comparison_arg(value, call, &comparison, &arg))
441 return;
442 if (!get_implied_rl(arg, &rl))
443 return;
444 goto cast;
447 str_to_rl_helper(call, type, value, &c, &rl);
448 if (*c == '\0')
449 goto cast;
451 call_math = jump_to_call_math(value);
452 if (call_math && parse_call_math_rl(call, call_math, &math_rl)) {
453 rl = rl_intersection(rl, math_rl);
454 goto cast;
458 * For now if we already tried to handle the call math and couldn't
459 * figure it out then bail.
461 if (jump_to_call_math(c) == c + 1)
462 goto cast;
464 rl = filter_by_comparison_call(c, call, &c, rl);
466 cast:
467 rl = cast_rl(type, rl);
468 dinfo->value_ranges = rl;
471 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
473 struct data_info dinfo = {};
475 str_to_dinfo(NULL, type, value, &dinfo);
476 *rl = dinfo.value_ranges;
479 void call_results_to_rl(struct expression *expr, struct symbol *type, char *value, struct range_list **rl)
481 struct data_info dinfo = {};
483 str_to_dinfo(strip_expr(expr), type, value, &dinfo);
484 *rl = dinfo.value_ranges;
487 int is_whole_rl(struct range_list *rl)
489 struct data_range *drange;
491 if (ptr_list_empty(rl))
492 return 0;
493 drange = first_ptr_list((struct ptr_list *)rl);
494 if (sval_is_min(drange->min) && sval_is_max(drange->max))
495 return 1;
496 return 0;
499 sval_t rl_min(struct range_list *rl)
501 struct data_range *drange;
502 sval_t ret;
504 ret.type = &llong_ctype;
505 ret.value = LLONG_MIN;
506 if (ptr_list_empty(rl))
507 return ret;
508 drange = first_ptr_list((struct ptr_list *)rl);
509 return drange->min;
512 sval_t rl_max(struct range_list *rl)
514 struct data_range *drange;
515 sval_t ret;
517 ret.type = &llong_ctype;
518 ret.value = LLONG_MAX;
519 if (ptr_list_empty(rl))
520 return ret;
521 drange = last_ptr_list((struct ptr_list *)rl);
522 return drange->max;
525 int rl_to_sval(struct range_list *rl, sval_t *sval)
527 sval_t min, max;
529 if (!rl)
530 return 0;
532 min = rl_min(rl);
533 max = rl_max(rl);
534 if (sval_cmp(min, max) != 0)
535 return 0;
536 *sval = min;
537 return 1;
540 struct symbol *rl_type(struct range_list *rl)
542 if (!rl)
543 return NULL;
544 return rl_min(rl).type;
547 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
549 struct data_range *ret;
551 if (perm)
552 ret = __alloc_perm_data_range(0);
553 else
554 ret = __alloc_data_range(0);
555 ret->min = min;
556 ret->max = max;
557 return ret;
560 struct data_range *alloc_range(sval_t min, sval_t max)
562 return alloc_range_helper_sval(min, max, 0);
565 struct data_range *alloc_range_perm(sval_t min, sval_t max)
567 return alloc_range_helper_sval(min, max, 1);
570 struct range_list *alloc_rl(sval_t min, sval_t max)
572 struct range_list *rl = NULL;
574 if (sval_cmp(min, max) > 0)
575 return alloc_whole_rl(min.type);
577 add_range(&rl, min, max);
578 return rl;
581 struct range_list *alloc_whole_rl(struct symbol *type)
583 if (!type || type_positive_bits(type) < 0)
584 type = &llong_ctype;
585 if (type->type == SYM_ARRAY)
586 type = &ptr_ctype;
588 return alloc_rl(sval_type_min(type), sval_type_max(type));
591 void add_range(struct range_list **list, sval_t min, sval_t max)
593 struct data_range *tmp = NULL;
594 struct data_range *new = NULL;
595 int check_next = 0;
597 if (sval_cmp(min, max) > 0) {
598 min = sval_type_min(min.type);
599 max = sval_type_max(min.type);
603 * FIXME: This has a problem merging a range_list like: min-0,3-max
604 * with a range like 1-2. You end up with min-2,3-max instead of
605 * just min-max.
607 FOR_EACH_PTR(*list, tmp) {
608 if (check_next) {
609 /* Sometimes we overlap with more than one range
610 so we have to delete or modify the next range. */
611 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
612 /* join 2 ranges here */
613 new->max = tmp->max;
614 DELETE_CURRENT_PTR(tmp);
615 return;
618 /* Doesn't overlap with the next one. */
619 if (sval_cmp(max, tmp->min) < 0)
620 return;
622 if (sval_cmp(max, tmp->max) <= 0) {
623 /* Partially overlaps the next one. */
624 new->max = tmp->max;
625 DELETE_CURRENT_PTR(tmp);
626 return;
627 } else {
628 /* Completely overlaps the next one. */
629 DELETE_CURRENT_PTR(tmp);
630 /* there could be more ranges to delete */
631 continue;
634 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
635 /* join 2 ranges into a big range */
636 new = alloc_range(min, tmp->max);
637 REPLACE_CURRENT_PTR(tmp, new);
638 return;
640 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
641 new = alloc_range(min, max);
642 INSERT_CURRENT(new, tmp);
643 return;
645 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
646 if (sval_cmp(max, tmp->max) < 0)
647 max = tmp->max;
648 else
649 check_next = 1;
650 new = alloc_range(min, max);
651 REPLACE_CURRENT_PTR(tmp, new);
652 if (!check_next)
653 return;
654 continue;
656 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
657 return;
658 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
659 min = tmp->min;
660 new = alloc_range(min, max);
661 REPLACE_CURRENT_PTR(tmp, new);
662 check_next = 1;
663 continue;
665 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
666 /* join 2 ranges into a big range */
667 new = alloc_range(tmp->min, max);
668 REPLACE_CURRENT_PTR(tmp, new);
669 check_next = 1;
670 continue;
672 /* the new range is entirely above the existing ranges */
673 } END_FOR_EACH_PTR(tmp);
674 if (check_next)
675 return;
676 new = alloc_range(min, max);
677 add_ptr_list(list, new);
680 struct range_list *clone_rl(struct range_list *list)
682 struct data_range *tmp;
683 struct range_list *ret = NULL;
685 FOR_EACH_PTR(list, tmp) {
686 add_ptr_list(&ret, tmp);
687 } END_FOR_EACH_PTR(tmp);
688 return ret;
691 struct range_list *clone_rl_permanent(struct range_list *list)
693 struct data_range *tmp;
694 struct data_range *new;
695 struct range_list *ret = NULL;
697 FOR_EACH_PTR(list, tmp) {
698 new = alloc_range_perm(tmp->min, tmp->max);
699 add_ptr_list(&ret, new);
700 } END_FOR_EACH_PTR(tmp);
701 return ret;
704 struct range_list *rl_union(struct range_list *one, struct range_list *two)
706 struct data_range *tmp;
707 struct range_list *ret = NULL;
709 FOR_EACH_PTR(one, tmp) {
710 add_range(&ret, tmp->min, tmp->max);
711 } END_FOR_EACH_PTR(tmp);
712 FOR_EACH_PTR(two, tmp) {
713 add_range(&ret, tmp->min, tmp->max);
714 } END_FOR_EACH_PTR(tmp);
715 return ret;
718 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
720 struct data_range *tmp;
721 struct range_list *ret = NULL;
723 FOR_EACH_PTR(list, tmp) {
724 if (sval_cmp(tmp->max, min) < 0) {
725 add_range(&ret, tmp->min, tmp->max);
726 continue;
728 if (sval_cmp(tmp->min, max) > 0) {
729 add_range(&ret, tmp->min, tmp->max);
730 continue;
732 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
733 continue;
734 if (sval_cmp(tmp->min, min) >= 0) {
735 max.value++;
736 add_range(&ret, max, tmp->max);
737 } else if (sval_cmp(tmp->max, max) <= 0) {
738 min.value--;
739 add_range(&ret, tmp->min, min);
740 } else {
741 min.value--;
742 max.value++;
743 add_range(&ret, tmp->min, min);
744 add_range(&ret, max, tmp->max);
746 } END_FOR_EACH_PTR(tmp);
747 return ret;
750 int ranges_equiv(struct data_range *one, struct data_range *two)
752 if (!one && !two)
753 return 1;
754 if (!one || !two)
755 return 0;
756 if (sval_cmp(one->min, two->min) != 0)
757 return 0;
758 if (sval_cmp(one->max, two->max) != 0)
759 return 0;
760 return 1;
763 int rl_equiv(struct range_list *one, struct range_list *two)
765 struct data_range *one_range;
766 struct data_range *two_range;
768 if (one == two)
769 return 1;
771 PREPARE_PTR_LIST(one, one_range);
772 PREPARE_PTR_LIST(two, two_range);
773 for (;;) {
774 if (!one_range && !two_range)
775 return 1;
776 if (!ranges_equiv(one_range, two_range))
777 return 0;
778 NEXT_PTR_LIST(one_range);
779 NEXT_PTR_LIST(two_range);
781 FINISH_PTR_LIST(two_range);
782 FINISH_PTR_LIST(one_range);
784 return 1;
787 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
789 switch (comparison) {
790 case '<':
791 case SPECIAL_UNSIGNED_LT:
792 if (sval_cmp(left->min, right->max) < 0)
793 return 1;
794 return 0;
795 case SPECIAL_UNSIGNED_LTE:
796 case SPECIAL_LTE:
797 if (sval_cmp(left->min, right->max) <= 0)
798 return 1;
799 return 0;
800 case SPECIAL_EQUAL:
801 if (sval_cmp(left->max, right->min) < 0)
802 return 0;
803 if (sval_cmp(left->min, right->max) > 0)
804 return 0;
805 return 1;
806 case SPECIAL_UNSIGNED_GTE:
807 case SPECIAL_GTE:
808 if (sval_cmp(left->max, right->min) >= 0)
809 return 1;
810 return 0;
811 case '>':
812 case SPECIAL_UNSIGNED_GT:
813 if (sval_cmp(left->max, right->min) > 0)
814 return 1;
815 return 0;
816 case SPECIAL_NOTEQUAL:
817 if (sval_cmp(left->min, left->max) != 0)
818 return 1;
819 if (sval_cmp(right->min, right->max) != 0)
820 return 1;
821 if (sval_cmp(left->min, right->min) != 0)
822 return 1;
823 return 0;
824 default:
825 sm_msg("unhandled comparison %d\n", comparison);
826 return 0;
828 return 0;
831 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
833 if (left)
834 return true_comparison_range(var, comparison, val);
835 else
836 return true_comparison_range(val, comparison, var);
839 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
841 switch (comparison) {
842 case '<':
843 case SPECIAL_UNSIGNED_LT:
844 if (sval_cmp(left->max, right->min) >= 0)
845 return 1;
846 return 0;
847 case SPECIAL_UNSIGNED_LTE:
848 case SPECIAL_LTE:
849 if (sval_cmp(left->max, right->min) > 0)
850 return 1;
851 return 0;
852 case SPECIAL_EQUAL:
853 if (sval_cmp(left->min, left->max) != 0)
854 return 1;
855 if (sval_cmp(right->min, right->max) != 0)
856 return 1;
857 if (sval_cmp(left->min, right->min) != 0)
858 return 1;
859 return 0;
860 case SPECIAL_UNSIGNED_GTE:
861 case SPECIAL_GTE:
862 if (sval_cmp(left->min, right->max) < 0)
863 return 1;
864 return 0;
865 case '>':
866 case SPECIAL_UNSIGNED_GT:
867 if (sval_cmp(left->min, right->max) <= 0)
868 return 1;
869 return 0;
870 case SPECIAL_NOTEQUAL:
871 if (sval_cmp(left->max, right->min) < 0)
872 return 0;
873 if (sval_cmp(left->min, right->max) > 0)
874 return 0;
875 return 1;
876 default:
877 sm_msg("unhandled comparison %d\n", comparison);
878 return 0;
880 return 0;
883 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
885 if (left)
886 return false_comparison_range_sval(var, comparison, val);
887 else
888 return false_comparison_range_sval(val, comparison, var);
891 int possibly_true(struct expression *left, int comparison, struct expression *right)
893 struct range_list *rl_left, *rl_right;
894 struct data_range *tmp_left, *tmp_right;
895 struct symbol *type;
897 if (!get_implied_rl(left, &rl_left))
898 return 1;
899 if (!get_implied_rl(right, &rl_right))
900 return 1;
902 type = rl_type(rl_left);
903 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
904 type = rl_type(rl_right);
905 if (type_positive_bits(type) < 31)
906 type = &int_ctype;
908 rl_left = cast_rl(type, rl_left);
909 rl_right = cast_rl(type, rl_right);
911 FOR_EACH_PTR(rl_left, tmp_left) {
912 FOR_EACH_PTR(rl_right, tmp_right) {
913 if (true_comparison_range(tmp_left, comparison, tmp_right))
914 return 1;
915 } END_FOR_EACH_PTR(tmp_right);
916 } END_FOR_EACH_PTR(tmp_left);
917 return 0;
920 int possibly_false(struct expression *left, int comparison, struct expression *right)
922 struct range_list *rl_left, *rl_right;
923 struct data_range *tmp_left, *tmp_right;
924 struct symbol *type;
926 if (!get_implied_rl(left, &rl_left))
927 return 1;
928 if (!get_implied_rl(right, &rl_right))
929 return 1;
931 type = rl_type(rl_left);
932 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
933 type = rl_type(rl_right);
934 if (type_positive_bits(type) < 31)
935 type = &int_ctype;
937 rl_left = cast_rl(type, rl_left);
938 rl_right = cast_rl(type, rl_right);
940 FOR_EACH_PTR(rl_left, tmp_left) {
941 FOR_EACH_PTR(rl_right, tmp_right) {
942 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
943 return 1;
944 } END_FOR_EACH_PTR(tmp_right);
945 } END_FOR_EACH_PTR(tmp_left);
946 return 0;
949 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
951 struct data_range *left_tmp, *right_tmp;
952 struct symbol *type;
954 if (!left_ranges || !right_ranges)
955 return 1;
957 type = rl_type(left_ranges);
958 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
959 type = rl_type(right_ranges);
960 if (type_positive_bits(type) < 31)
961 type = &int_ctype;
963 left_ranges = cast_rl(type, left_ranges);
964 right_ranges = cast_rl(type, right_ranges);
966 FOR_EACH_PTR(left_ranges, left_tmp) {
967 FOR_EACH_PTR(right_ranges, right_tmp) {
968 if (true_comparison_range(left_tmp, comparison, right_tmp))
969 return 1;
970 } END_FOR_EACH_PTR(right_tmp);
971 } END_FOR_EACH_PTR(left_tmp);
972 return 0;
975 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
977 struct data_range *left_tmp, *right_tmp;
978 struct symbol *type;
980 if (!left_ranges || !right_ranges)
981 return 1;
983 type = rl_type(left_ranges);
984 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
985 type = rl_type(right_ranges);
986 if (type_positive_bits(type) < 31)
987 type = &int_ctype;
989 left_ranges = cast_rl(type, left_ranges);
990 right_ranges = cast_rl(type, right_ranges);
992 FOR_EACH_PTR(left_ranges, left_tmp) {
993 FOR_EACH_PTR(right_ranges, right_tmp) {
994 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
995 return 1;
996 } END_FOR_EACH_PTR(right_tmp);
997 } END_FOR_EACH_PTR(left_tmp);
998 return 0;
1001 /* FIXME: the _rl here stands for right left so really it should be _lr */
1002 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1004 if (left)
1005 return possibly_true_rl(a, comparison, b);
1006 else
1007 return possibly_true_rl(b, comparison, a);
1010 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1012 if (left)
1013 return possibly_false_rl(a, comparison, b);
1014 else
1015 return possibly_false_rl(b, comparison, a);
1018 int rl_has_sval(struct range_list *rl, sval_t sval)
1020 struct data_range *tmp;
1022 FOR_EACH_PTR(rl, tmp) {
1023 if (sval_cmp(tmp->min, sval) <= 0 &&
1024 sval_cmp(tmp->max, sval) >= 0)
1025 return 1;
1026 } END_FOR_EACH_PTR(tmp);
1027 return 0;
1030 void tack_on(struct range_list **list, struct data_range *drange)
1032 add_ptr_list(list, drange);
1035 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
1037 add_ptr_list(rl_stack, rl);
1040 struct range_list *pop_rl(struct range_list_stack **rl_stack)
1042 struct range_list *rl;
1044 rl = last_ptr_list((struct ptr_list *)*rl_stack);
1045 delete_ptr_list_last((struct ptr_list **)rl_stack);
1046 return rl;
1049 struct range_list *top_rl(struct range_list_stack *rl_stack)
1051 struct range_list *rl;
1053 rl = last_ptr_list((struct ptr_list *)rl_stack);
1054 return rl;
1057 void filter_top_rl(struct range_list_stack **rl_stack, sval_t sval)
1059 struct range_list *rl;
1061 rl = pop_rl(rl_stack);
1062 rl = remove_range(rl, sval, sval);
1063 push_rl(rl_stack, rl);
1066 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1068 struct data_range *tmp;
1069 struct range_list *ret = NULL;
1070 sval_t min, max;
1072 if (!rl)
1073 return NULL;
1075 if (!type || type == rl_type(rl))
1076 return rl;
1078 FOR_EACH_PTR(rl, tmp) {
1079 min = tmp->min;
1080 max = tmp->max;
1081 if (type_bits(type) < type_bits(rl_type(rl))) {
1082 min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1083 max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1085 if (sval_cmp(min, max) > 0) {
1086 min = sval_cast(type, min);
1087 max = sval_cast(type, max);
1089 add_range_t(type, &ret, min, max);
1090 } END_FOR_EACH_PTR(tmp);
1092 return ret;
1095 static int rl_is_sane(struct range_list *rl)
1097 struct data_range *tmp;
1098 struct symbol *type;
1100 type = rl_type(rl);
1101 FOR_EACH_PTR(rl, tmp) {
1102 if (!sval_fits(type, tmp->min))
1103 return 0;
1104 if (!sval_fits(type, tmp->max))
1105 return 0;
1106 if (sval_cmp(tmp->min, tmp->max) > 0)
1107 return 0;
1108 } END_FOR_EACH_PTR(tmp);
1110 return 1;
1113 static int rl_type_consistent(struct range_list *rl)
1115 struct data_range *tmp;
1116 struct symbol *type;
1118 type = rl_type(rl);
1119 FOR_EACH_PTR(rl, tmp) {
1120 if (type != tmp->min.type || type != tmp->max.type)
1121 return 0;
1122 } END_FOR_EACH_PTR(tmp);
1123 return 1;
1126 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1128 struct data_range *tmp;
1129 struct range_list *ret = NULL;
1131 if (!rl)
1132 return NULL;
1134 if (!type)
1135 return rl;
1136 if (!rl_is_sane(rl))
1137 return alloc_whole_rl(type);
1138 if (type == rl_type(rl) && rl_type_consistent(rl))
1139 return rl;
1141 FOR_EACH_PTR(rl, tmp) {
1142 add_range_t(type, &ret, tmp->min, tmp->max);
1143 } END_FOR_EACH_PTR(tmp);
1145 if (!ret)
1146 return alloc_whole_rl(type);
1148 return ret;
1151 struct range_list *rl_invert(struct range_list *orig)
1153 struct range_list *ret = NULL;
1154 struct data_range *tmp;
1155 sval_t gap_min, abs_max, sval;
1157 if (!orig)
1158 return NULL;
1160 gap_min = sval_type_min(rl_min(orig).type);
1161 abs_max = sval_type_max(rl_max(orig).type);
1163 FOR_EACH_PTR(orig, tmp) {
1164 if (sval_cmp(tmp->min, gap_min) > 0) {
1165 sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
1166 add_range(&ret, gap_min, sval);
1168 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
1169 if (sval_cmp(tmp->max, abs_max) == 0)
1170 gap_min = abs_max;
1171 } END_FOR_EACH_PTR(tmp);
1173 if (sval_cmp(gap_min, abs_max) < 0)
1174 add_range(&ret, gap_min, abs_max);
1176 return ret;
1179 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1181 struct data_range *tmp;
1183 FOR_EACH_PTR(filter, tmp) {
1184 rl = remove_range(rl, tmp->min, tmp->max);
1185 } END_FOR_EACH_PTR(tmp);
1187 return rl;
1190 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1192 struct range_list *one_orig;
1193 struct range_list *two_orig;
1194 struct range_list *ret;
1195 struct symbol *ret_type;
1196 struct symbol *small_type;
1197 struct symbol *large_type;
1199 if (!two)
1200 return NULL;
1201 if (!one)
1202 return NULL;
1204 one_orig = one;
1205 two_orig = two;
1207 ret_type = rl_type(one);
1208 small_type = rl_type(one);
1209 large_type = rl_type(two);
1211 if (type_bits(rl_type(two)) < type_bits(small_type)) {
1212 small_type = rl_type(two);
1213 large_type = rl_type(one);
1216 one = cast_rl(large_type, one);
1217 two = cast_rl(large_type, two);
1219 ret = one;
1220 one = rl_invert(one);
1221 two = rl_invert(two);
1223 ret = rl_filter(ret, one);
1224 ret = rl_filter(ret, two);
1226 one = cast_rl(small_type, one_orig);
1227 two = cast_rl(small_type, two_orig);
1229 one = rl_invert(one);
1230 two = rl_invert(two);
1232 ret = cast_rl(small_type, ret);
1233 ret = rl_filter(ret, one);
1234 ret = rl_filter(ret, two);
1236 return cast_rl(ret_type, ret);
1239 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1241 sval_t zero;
1242 sval_t max;
1244 max = rl_max(right);
1245 if (sval_is_max(max))
1246 return left;
1247 if (max.value == 0)
1248 return NULL;
1249 max.value--;
1250 if (sval_is_negative(max))
1251 return NULL;
1252 if (sval_cmp(rl_max(left), max) < 0)
1253 return left;
1254 zero = max;
1255 zero.value = 0;
1256 return alloc_rl(zero, max);
1259 static struct range_list *get_neg_rl(struct range_list *rl)
1261 struct data_range *tmp;
1262 struct range_list *ret = NULL;
1264 if (!rl)
1265 return NULL;
1266 if (sval_is_positive(rl_min(rl)))
1267 return NULL;
1269 FOR_EACH_PTR(rl, tmp) {
1270 if (sval_is_positive(tmp->min))
1271 return ret;
1272 if (sval_is_positive(tmp->max)) {
1273 tmp->max.value = -1;
1274 add_range(&ret, tmp->min, tmp->max);
1275 return ret;
1277 add_range(&ret, tmp->min, tmp->max);
1278 } END_FOR_EACH_PTR(tmp);
1280 return ret;
1283 static struct range_list *get_pos_rl(struct range_list *rl)
1285 struct data_range *tmp;
1286 struct range_list *ret = NULL;
1288 if (!rl)
1289 return NULL;
1290 if (sval_is_negative(rl_max(rl)))
1291 return NULL;
1293 FOR_EACH_PTR(rl, tmp) {
1294 if (sval_is_negative(tmp->max))
1295 continue;
1296 if (sval_is_positive(tmp->min)) {
1297 add_range(&ret, tmp->min, tmp->max);
1298 continue;
1300 tmp->min.value = 0;
1301 add_range(&ret, tmp->min, tmp->max);
1302 } END_FOR_EACH_PTR(tmp);
1304 return ret;
1307 static struct range_list *divide_rl_helper(struct range_list *left, struct range_list *right)
1309 sval_t right_min, right_max;
1310 sval_t min, max;
1312 if (!left || !right)
1313 return NULL;
1315 /* let's assume we never divide by zero */
1316 right_min = rl_min(right);
1317 right_max = rl_max(right);
1318 if (right_min.value == 0 && right_max.value == 0)
1319 return NULL;
1320 if (right_min.value == 0)
1321 right_min.value = 1;
1322 if (right_max.value == 0)
1323 right_max.value = -1;
1325 max = sval_binop(rl_max(left), '/', right_min);
1326 min = sval_binop(rl_min(left), '/', right_max);
1328 return alloc_rl(min, max);
1331 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1333 struct range_list *left_neg, *left_pos, *right_neg, *right_pos;
1334 struct range_list *neg_neg, *neg_pos, *pos_neg, *pos_pos;
1335 struct range_list *ret;
1337 if (is_whole_rl(left) || is_whole_rl(right))
1338 return NULL;
1340 left_neg = get_neg_rl(left);
1341 left_pos = get_pos_rl(left);
1342 right_neg = get_neg_rl(right);
1343 right_pos = get_pos_rl(right);
1345 neg_neg = divide_rl_helper(left_neg, right_neg);
1346 neg_pos = divide_rl_helper(left_neg, right_pos);
1347 pos_neg = divide_rl_helper(left_pos, right_neg);
1348 pos_pos = divide_rl_helper(left_pos, right_pos);
1350 ret = rl_union(neg_neg, neg_pos);
1351 ret = rl_union(ret, pos_neg);
1352 return rl_union(ret, pos_pos);
1355 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1357 sval_t min, max;
1359 if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1360 return NULL;
1361 min = sval_binop(rl_min(left), op, rl_min(right));
1363 if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1364 return NULL;
1365 max = sval_binop(rl_max(left), op, rl_max(right));
1367 return alloc_rl(min, max);
1370 static unsigned long long sval_fls_mask(sval_t sval)
1372 unsigned long long uvalue = sval.uvalue;
1373 unsigned long long high_bit = 0;
1375 while (uvalue) {
1376 uvalue >>= 1;
1377 high_bit++;
1380 if (high_bit == 0)
1381 return 0;
1383 return ((unsigned long long)-1) >> (64 - high_bit);
1386 static unsigned long long rl_bits_always_set(struct range_list *rl)
1388 return sval_fls_mask(rl_min(rl));
1391 static unsigned long long rl_bits_maybe_set(struct range_list *rl)
1393 return sval_fls_mask(rl_max(rl));
1396 static struct range_list *handle_OR_rl(struct range_list *left, struct range_list *right)
1398 unsigned long long left_min, left_max, right_min, right_max;
1399 sval_t min, max;
1400 sval_t sval;
1402 if ((rl_to_sval(left, &sval) || rl_to_sval(right, &sval)) &&
1403 !sval_binop_overflows(rl_max(left), '+', rl_max(right)))
1404 return rl_binop(left, '+', right);
1406 left_min = rl_bits_always_set(left);
1407 left_max = rl_bits_maybe_set(left);
1408 right_min = rl_bits_always_set(right);
1409 right_max = rl_bits_maybe_set(right);
1411 min.type = max.type = &ullong_ctype;
1412 min.uvalue = left_min | right_min;
1413 max.uvalue = left_max | right_max;
1415 return cast_rl(rl_type(left), alloc_rl(min, max));
1418 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1420 struct symbol *cast_type;
1421 sval_t left_sval, right_sval;
1422 struct range_list *ret = NULL;
1424 cast_type = rl_type(left);
1425 if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
1426 cast_type = rl_type(right);
1427 if (sval_type_max(cast_type).uvalue < INT_MAX)
1428 cast_type = &int_ctype;
1430 left = cast_rl(cast_type, left);
1431 right = cast_rl(cast_type, right);
1433 if (!left || !right)
1434 return alloc_whole_rl(cast_type);
1436 if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
1437 sval_t val = sval_binop(left_sval, op, right_sval);
1438 return alloc_rl(val, val);
1441 switch (op) {
1442 case '%':
1443 ret = handle_mod_rl(left, right);
1444 break;
1445 case '/':
1446 ret = handle_divide_rl(left, right);
1447 break;
1448 case '*':
1449 case '+':
1450 ret = handle_add_mult_rl(left, op, right);
1451 break;
1452 case '|':
1453 ret = handle_OR_rl(left, right);
1454 break;
1456 /* FIXME: Do the rest as well */
1457 case '-':
1458 case '&':
1459 case SPECIAL_RIGHTSHIFT:
1460 case SPECIAL_LEFTSHIFT:
1461 case '^':
1462 break;
1465 if (!ret)
1466 ret = alloc_whole_rl(cast_type);
1467 return ret;
1470 void free_rl(struct range_list **rlist)
1472 __free_ptr_list((struct ptr_list **)rlist);
1475 static void free_single_dinfo(struct data_info *dinfo)
1477 free_rl(&dinfo->value_ranges);
1480 static void free_dinfos(struct allocation_blob *blob)
1482 unsigned int size = sizeof(struct data_info);
1483 unsigned int offset = 0;
1485 while (offset < blob->offset) {
1486 free_single_dinfo((struct data_info *)(blob->data + offset));
1487 offset += size;
1491 void free_data_info_allocs(void)
1493 struct allocator_struct *desc = &data_info_allocator;
1494 struct allocation_blob *blob = desc->blobs;
1496 desc->blobs = NULL;
1497 desc->allocations = 0;
1498 desc->total_bytes = 0;
1499 desc->useful_bytes = 0;
1500 desc->freelist = NULL;
1501 while (blob) {
1502 struct allocation_blob *next = blob->next;
1503 free_dinfos(blob);
1504 blob_free(blob, desc->chunking);
1505 blob = next;
1507 clear_data_range_alloc();