sval: make sval_cast() take a type
[smatch.git] / smatch_ranges.c
blob2864145a7f319ca413e3fda96e7fea8ac8b0aed6
1 /*
2 * sparse/smatch_ranges.c
4 * Copyright (C) 2009 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
10 #include "parse.h"
11 #include "smatch.h"
12 #include "smatch_extra.h"
13 #include "smatch_slist.h"
15 ALLOCATOR(data_info, "smatch extra data");
16 ALLOCATOR(data_range, "data range");
17 __DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
18 "permanent ranges", perm_data_range);
19 ALLOCATOR(data_range_sval, "data range sval");
20 __DO_ALLOCATOR(struct data_range_sval, sizeof(struct data_range_sval), __alignof__(struct data_range_sval),
21 "permanent ranges sval", perm_data_range_sval);
23 struct data_range whole_range = {
24 .min = LLONG_MIN,
25 .max = LLONG_MAX,
28 char *show_ranges_sval(struct range_list_sval *list)
30 struct data_range_sval *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 void get_value_ranges_sval(char *value, struct range_list_sval **rl)
52 long long val1, val2;
53 char *start;
54 char *c;
56 *rl = NULL;
58 c = value;
59 while (*c) {
60 if (*c == '(')
61 c++;
62 start = c;
64 if (!strncmp(start, "max", 3)) {
65 val1 = LLONG_MAX;
66 c += 3;
67 } else if (!strncmp(start, "u64max", 6)) {
68 val1 = LLONG_MAX; // FIXME
69 c += 6;
70 } else if (!strncmp(start, "s64max", 6)) {
71 val1 = LLONG_MAX;
72 c += 6;
73 } else if (!strncmp(start, "u32max", 6)) {
74 val1 = UINT_MAX;
75 c += 6;
76 } else if (!strncmp(start, "s32max", 6)) {
77 val1 = INT_MAX;
78 c += 6;
79 } else if (!strncmp(start, "u16max", 6)) {
80 val1 = USHRT_MAX;
81 c += 6;
82 } else if (!strncmp(start, "s16max", 6)) {
83 val1 = SHRT_MAX;
84 c += 6;
85 } else if (!strncmp(start, "min", 3)) {
86 val1 = LLONG_MIN;
87 c += 3;
88 } else if (!strncmp(start, "s64min", 6)) {
89 val1 = LLONG_MIN;
90 c += 6;
91 } else if (!strncmp(start, "s32min", 6)) {
92 val1 = INT_MIN;
93 c += 6;
94 } else if (!strncmp(start, "s16min", 6)) {
95 val1 = SHRT_MIN;
96 c += 6;
97 } else {
98 while (*c && *c != ',' && *c != '-')
99 c++;
100 val1 = strtoll(start, &c, 10);
102 if (*c == ')')
103 c++;
104 if (!*c) {
105 add_range_sval(rl, ll_to_sval(val1), ll_to_sval(val1));
106 break;
108 if (*c == ',') {
109 add_range_sval(rl, ll_to_sval(val1), ll_to_sval(val1));
110 c++;
111 start = c;
112 continue;
114 c++; /* skip the dash in eg. 4-5 */
115 if (*c == '(')
116 c++;
117 start = c;
118 if (!strncmp(start, "max", 3)) {
119 val2 = LLONG_MAX;
120 c += 3;
121 } else {
123 while (*c && *c != ',' && *c != '-')
124 c++;
125 val2 = strtoll(start, &c, 10);
127 add_range_sval(rl, ll_to_sval(val1), ll_to_sval(val2));
128 if (!*c)
129 break;
130 if (*c == ')')
131 c++;
132 c++; /* skip the comma in eg: 4-5,7 */
136 static struct data_range range_zero = {
137 .min = 0,
138 .max = 0,
141 static struct data_range range_one = {
142 .min = 1,
143 .max = 1,
146 int is_whole_range_rl_sval(struct range_list_sval *rl)
148 struct data_range_sval *drange;
150 if (ptr_list_empty(rl))
151 return 1;
152 drange = first_ptr_list((struct ptr_list *)rl);
153 if (sval_is_min(drange->min) && sval_is_max(drange->max))
154 return 1;
155 return 0;
158 sval_t rl_min_sval(struct range_list_sval *rl)
160 struct data_range_sval *drange;
161 sval_t ret;
163 ret.type = &llong_ctype;
164 ret.value = LLONG_MIN;
165 if (ptr_list_empty(rl))
166 return ret;
167 drange = first_ptr_list((struct ptr_list *)rl);
168 return drange->min;
171 sval_t rl_max_sval(struct range_list_sval *rl)
173 struct data_range_sval *drange;
174 sval_t ret;
176 ret.type = &llong_ctype;
177 ret.value = LLONG_MAX;
178 if (ptr_list_empty(rl))
179 return ret;
180 drange = last_ptr_list((struct ptr_list *)rl);
181 return drange->max;
184 static struct data_range *alloc_range_helper(long long min, long long max, int perm)
186 struct data_range *ret;
188 if (min > max) {
189 // sm_msg("debug invalid range %lld to %lld", min, max);
190 min = whole_range.min;
191 max = whole_range.max;
193 if (min == whole_range.min && max == whole_range.max)
194 return &whole_range;
195 if (min == 0 && max == 0)
196 return &range_zero;
197 if (min == 1 && max == 1)
198 return &range_one;
200 if (perm)
201 ret = __alloc_perm_data_range(0);
202 else
203 ret = __alloc_data_range(0);
204 ret->min = min;
205 ret->max = max;
206 return ret;
209 static struct data_range_sval *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
211 struct data_range_sval *ret;
213 if (sval_cmp(min, max) > 0) {
214 // sm_msg("debug invalid range %lld to %lld", min, max);
215 min.value = LLONG_MIN; /* fixme: need a way to represent unknown svals */
216 max.value = LLONG_MAX;
219 if (perm)
220 ret = __alloc_perm_data_range_sval(0);
221 else
222 ret = __alloc_data_range_sval(0);
223 ret->min = min;
224 ret->max = max;
225 return ret;
228 struct data_range *alloc_range(long long min, long long max)
230 return alloc_range_helper(min, max, 0);
233 struct data_range_sval *alloc_range_sval(sval_t min, sval_t max)
235 return alloc_range_helper_sval(min, max, 0);
238 struct data_range_sval *drange_to_drange_sval(struct data_range *drange)
240 return alloc_range_helper_sval(ll_to_sval(drange->min), ll_to_sval(drange->max), 0);
243 struct data_range *drange_sval_to_drange(struct data_range_sval *drange)
245 return alloc_range_helper(sval_to_ll(drange->min), sval_to_ll(drange->max), 0);
248 struct data_range *alloc_range_perm(long long min, long long max)
250 return alloc_range_helper(min, max, 1);
253 struct data_range_sval *alloc_range_perm_sval(sval_t min, sval_t max)
255 return alloc_range_helper_sval(min, max, 1);
258 struct range_list_sval *alloc_range_list_sval(sval_t min, sval_t max)
260 struct range_list_sval *rl = NULL;
262 add_range_sval(&rl, min, max);
263 return rl;
266 struct range_list_sval *whole_range_list_sval(void)
268 return alloc_range_list_sval(ll_to_sval(whole_range.min), ll_to_sval(whole_range.max));
271 void add_range_sval(struct range_list_sval **list, sval_t min, sval_t max)
273 struct data_range_sval *tmp = NULL;
274 struct data_range_sval *new = NULL;
275 int check_next = 0;
278 * FIXME: This has a problem merging a range_list like: min-0,3-max
279 * with a range like 1-2. You end up with min-2,3-max instead of
280 * just min-max.
282 FOR_EACH_PTR(*list, tmp) {
283 if (check_next) {
284 /* Sometimes we overlap with more than one range
285 so we have to delete or modify the next range. */
286 if (max.value + 1 == tmp->min.value) {
287 /* join 2 ranges here */
288 new->max = tmp->max;
289 DELETE_CURRENT_PTR(tmp);
290 return;
293 /* Doesn't overlap with the next one. */
294 if (sval_cmp(max, tmp->min) < 0)
295 return;
296 /* Partially overlaps with the next one. */
297 if (sval_cmp(max, tmp->max) < 0) {
298 tmp->min.value = max.value + 1;
299 return;
301 /* Completely overlaps with the next one. */
302 if (sval_cmp(max, tmp->max) >= 0) {
303 DELETE_CURRENT_PTR(tmp);
304 /* there could be more ranges to delete */
305 continue;
308 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
309 /* join 2 ranges into a big range */
310 new = alloc_range_sval(min, tmp->max);
311 REPLACE_CURRENT_PTR(tmp, new);
312 return;
314 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
315 new = alloc_range_sval(min, max);
316 INSERT_CURRENT(new, tmp);
317 return;
319 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
320 if (sval_cmp(max, tmp->max) < 0)
321 max = tmp->max;
322 else
323 check_next = 1;
324 new = alloc_range_sval(min, max);
325 REPLACE_CURRENT_PTR(tmp, new);
326 if (!check_next)
327 return;
328 continue;
330 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
331 return;
332 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
333 min = tmp->min;
334 new = alloc_range_sval(min, max);
335 REPLACE_CURRENT_PTR(tmp, new);
336 check_next = 1;
337 continue;
339 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
340 /* join 2 ranges into a big range */
341 new = alloc_range_sval(tmp->min, max);
342 REPLACE_CURRENT_PTR(tmp, new);
343 check_next = 1;
344 continue;
346 /* the new range is entirely above the existing ranges */
347 } END_FOR_EACH_PTR(tmp);
348 if (check_next)
349 return;
350 new = alloc_range_sval(min, max);
351 add_ptr_list(list, new);
354 struct range_list_sval *clone_range_list_sval(struct range_list_sval *list)
356 struct data_range_sval *tmp;
357 struct range_list_sval *ret = NULL;
359 FOR_EACH_PTR(list, tmp) {
360 add_ptr_list(&ret, tmp);
361 } END_FOR_EACH_PTR(tmp);
362 return ret;
365 struct range_list_sval *clone_permanent_sval(struct range_list_sval *list)
367 struct data_range_sval *tmp;
368 struct data_range_sval *new;
369 struct range_list_sval *ret = NULL;
371 FOR_EACH_PTR(list, tmp) {
372 new = alloc_range_perm_sval(tmp->min, tmp->max);
373 add_ptr_list(&ret, new);
374 } END_FOR_EACH_PTR(tmp);
375 return ret;
378 struct range_list_sval *range_list_union_sval(struct range_list_sval *one, struct range_list_sval *two)
380 struct data_range_sval *tmp;
381 struct range_list_sval *ret = NULL;
383 FOR_EACH_PTR(one, tmp) {
384 add_range_sval(&ret, tmp->min, tmp->max);
385 } END_FOR_EACH_PTR(tmp);
386 FOR_EACH_PTR(two, tmp) {
387 add_range_sval(&ret, tmp->min, tmp->max);
388 } END_FOR_EACH_PTR(tmp);
389 return ret;
392 struct range_list_sval *remove_range_sval(struct range_list_sval *list, sval_t min, sval_t max)
394 struct data_range_sval *tmp;
395 struct range_list_sval *ret = NULL;
397 FOR_EACH_PTR(list, tmp) {
398 if (sval_cmp(tmp->max, min) < 0) {
399 add_range_sval(&ret, tmp->min, tmp->max);
400 continue;
402 if (sval_cmp(tmp->min, max) > 0) {
403 add_range_sval(&ret, tmp->min, tmp->max);
404 continue;
406 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
407 continue;
408 if (sval_cmp(tmp->min, min) >= 0) {
409 max.value++;
410 add_range_sval(&ret, max, tmp->max);
411 } else if (sval_cmp(tmp->max, max) <= 0) {
412 min.value--;
413 add_range_sval(&ret, tmp->min, min);
414 } else {
415 min.value--;
416 max.value++;
417 add_range_sval(&ret, tmp->min, min);
418 add_range_sval(&ret, max, tmp->max);
420 } END_FOR_EACH_PTR(tmp);
421 return ret;
424 int estate_get_single_value_sval(struct smatch_state *state, sval_t *sval)
426 sval_t min, max;
428 min = rl_min_sval(estate_ranges_sval(state));
429 max = rl_max_sval(estate_ranges_sval(state));
430 if (sval_cmp(min, max) != 0)
431 return 0;
432 *sval = min;
433 return 1;
436 int ranges_equiv_sval(struct data_range_sval *one, struct data_range_sval *two)
438 if (!one && !two)
439 return 1;
440 if (!one || !two)
441 return 0;
442 if (sval_cmp(one->min, two->min) != 0)
443 return 0;
444 if (sval_cmp(one->max, two->max) != 0)
445 return 0;
446 return 1;
449 int range_lists_equiv_sval(struct range_list_sval *one, struct range_list_sval *two)
451 struct data_range_sval *one_range;
452 struct data_range_sval *two_range;
454 PREPARE_PTR_LIST(one, one_range);
455 PREPARE_PTR_LIST(two, two_range);
456 for (;;) {
457 if (!one_range && !two_range)
458 return 1;
459 if (!ranges_equiv_sval(one_range, two_range))
460 return 0;
461 NEXT_PTR_LIST(one_range);
462 NEXT_PTR_LIST(two_range);
464 FINISH_PTR_LIST(two_range);
465 FINISH_PTR_LIST(one_range);
467 return 1;
470 int true_comparison_range_sval(struct data_range_sval *left, int comparison, struct data_range_sval *right)
472 switch (comparison) {
473 case '<':
474 case SPECIAL_UNSIGNED_LT:
475 if (sval_cmp(left->min, right->max) < 0)
476 return 1;
477 return 0;
478 case SPECIAL_UNSIGNED_LTE:
479 case SPECIAL_LTE:
480 if (sval_cmp(left->min, right->max) <= 0)
481 return 1;
482 return 0;
483 case SPECIAL_EQUAL:
484 if (sval_cmp(left->max, right->min) < 0)
485 return 0;
486 if (sval_cmp(left->min, right->max) > 0)
487 return 0;
488 return 1;
489 case SPECIAL_UNSIGNED_GTE:
490 case SPECIAL_GTE:
491 if (sval_cmp(left->max, right->min) >= 0)
492 return 1;
493 return 0;
494 case '>':
495 case SPECIAL_UNSIGNED_GT:
496 if (sval_cmp(left->max, right->min) > 0)
497 return 1;
498 return 0;
499 case SPECIAL_NOTEQUAL:
500 if (sval_cmp(left->min, left->max) != 0)
501 return 1;
502 if (sval_cmp(right->min, right->max) != 0)
503 return 1;
504 if (sval_cmp(left->min, right->min) != 0)
505 return 1;
506 return 0;
507 default:
508 sm_msg("unhandled comparison %d\n", comparison);
509 return 0;
511 return 0;
514 int true_comparison_range_lr_sval(int comparison, struct data_range_sval *var, struct data_range_sval *val, int left)
516 if (left)
517 return true_comparison_range_sval(var, comparison, val);
518 else
519 return true_comparison_range_sval(val, comparison, var);
522 static int false_comparison_range_sval(struct data_range_sval *left, int comparison, struct data_range_sval *right)
524 switch (comparison) {
525 case '<':
526 case SPECIAL_UNSIGNED_LT:
527 if (sval_cmp(left->max, right->min) >= 0)
528 return 1;
529 return 0;
530 case SPECIAL_UNSIGNED_LTE:
531 case SPECIAL_LTE:
532 if (sval_cmp(left->max, right->min) > 0)
533 return 1;
534 return 0;
535 case SPECIAL_EQUAL:
536 if (sval_cmp(left->min, left->max) != 0)
537 return 1;
538 if (sval_cmp(right->min, right->max) != 0)
539 return 1;
540 if (sval_cmp(left->min, right->min) != 0)
541 return 1;
542 return 0;
543 case SPECIAL_UNSIGNED_GTE:
544 case SPECIAL_GTE:
545 if (sval_cmp(left->min, right->max) < 0)
546 return 1;
547 return 0;
548 case '>':
549 case SPECIAL_UNSIGNED_GT:
550 if (sval_cmp(left->min, right->max) <= 0)
551 return 1;
552 return 0;
553 case SPECIAL_NOTEQUAL:
554 if (sval_cmp(left->max, right->min) < 0)
555 return 0;
556 if (sval_cmp(left->min, right->max) > 0)
557 return 0;
558 return 1;
559 default:
560 sm_msg("unhandled comparison %d\n", comparison);
561 return 0;
563 return 0;
566 int false_comparison_range_lr_sval(int comparison, struct data_range_sval *var, struct data_range_sval *val, int left)
568 if (left)
569 return false_comparison_range_sval(var, comparison, val);
570 else
571 return false_comparison_range_sval(val, comparison, var);
574 int possibly_true(struct expression *left, int comparison, struct expression *right)
576 struct range_list_sval *rl_left, *rl_right;
577 struct data_range_sval *tmp_left, *tmp_right;
579 if (!get_implied_range_list_sval(left, &rl_left))
580 return 1;
581 if (!get_implied_range_list_sval(right, &rl_right))
582 return 1;
584 FOR_EACH_PTR(rl_left, tmp_left) {
585 FOR_EACH_PTR(rl_right, tmp_right) {
586 if (true_comparison_range_sval(tmp_left, comparison, tmp_right))
587 return 1;
588 } END_FOR_EACH_PTR(tmp_right);
589 } END_FOR_EACH_PTR(tmp_left);
590 return 0;
593 int possibly_false(struct expression *left, int comparison, struct expression *right)
595 struct range_list_sval *rl_left, *rl_right;
596 struct data_range_sval *tmp_left, *tmp_right;
598 if (!get_implied_range_list_sval(left, &rl_left))
599 return 1;
600 if (!get_implied_range_list_sval(right, &rl_right))
601 return 1;
603 FOR_EACH_PTR(rl_left, tmp_left) {
604 FOR_EACH_PTR(rl_right, tmp_right) {
605 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
606 return 1;
607 } END_FOR_EACH_PTR(tmp_right);
608 } END_FOR_EACH_PTR(tmp_left);
609 return 0;
612 int possibly_true_range_lists_sval(struct range_list_sval *left_ranges, int comparison, struct range_list_sval *right_ranges)
614 struct data_range_sval *left_tmp, *right_tmp;
616 if (!left_ranges || !right_ranges)
617 return 1;
619 FOR_EACH_PTR(left_ranges, left_tmp) {
620 FOR_EACH_PTR(right_ranges, right_tmp) {
621 if (true_comparison_range_sval(left_tmp, comparison, right_tmp))
622 return 1;
623 } END_FOR_EACH_PTR(right_tmp);
624 } END_FOR_EACH_PTR(left_tmp);
625 return 0;
628 int possibly_false_range_lists_sval(struct range_list_sval *left_ranges, int comparison, struct range_list_sval *right_ranges)
630 struct data_range_sval *left_tmp, *right_tmp;
632 if (!left_ranges || !right_ranges)
633 return 1;
635 FOR_EACH_PTR(left_ranges, left_tmp) {
636 FOR_EACH_PTR(right_ranges, right_tmp) {
637 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
638 return 1;
639 } END_FOR_EACH_PTR(right_tmp);
640 } END_FOR_EACH_PTR(left_tmp);
641 return 0;
644 /* FIXME: the _rl here stands for right left so really it should be _lr */
645 int possibly_true_range_lists_rl_sval(int comparison, struct range_list_sval *a, struct range_list_sval *b, int left)
647 if (left)
648 return possibly_true_range_lists_sval(a, comparison, b);
649 else
650 return possibly_true_range_lists_sval(b, comparison, a);
653 int possibly_false_range_lists_rl_sval(int comparison, struct range_list_sval *a, struct range_list_sval *b, int left)
655 if (left)
656 return possibly_false_range_lists_sval(a, comparison, b);
657 else
658 return possibly_false_range_lists_sval(b, comparison, a);
661 void tack_on_sval(struct range_list_sval **list, struct data_range_sval *drange)
663 add_ptr_list(list, drange);
666 void push_range_list_sval(struct range_list_stack_sval **rl_stack, struct range_list_sval *rl)
668 add_ptr_list(rl_stack, rl);
671 struct range_list_sval *pop_range_list_sval(struct range_list_stack_sval **rl_stack)
673 struct range_list_sval *rl;
675 rl = last_ptr_list((struct ptr_list *)*rl_stack);
676 delete_ptr_list_last((struct ptr_list **)rl_stack);
677 return rl;
680 struct range_list_sval *top_range_list_sval(struct range_list_stack_sval *rl_stack)
682 struct range_list_sval *rl;
684 rl = last_ptr_list((struct ptr_list *)rl_stack);
685 return rl;
688 void filter_top_range_list_sval(struct range_list_stack_sval **rl_stack, sval_t sval)
690 struct range_list_sval *rl;
692 rl = pop_range_list_sval(rl_stack);
693 rl = remove_range_sval(rl, sval, sval);
694 push_range_list_sval(rl_stack, rl);
697 void free_range_list_sval(struct range_list_sval **rlist)
699 __free_ptr_list((struct ptr_list **)rlist);
702 static void free_single_dinfo(struct data_info *dinfo)
704 if (dinfo->type == DATA_RANGE)
705 free_range_list_sval(&dinfo->value_ranges);
708 static void free_dinfos(struct allocation_blob *blob)
710 unsigned int size = sizeof(struct data_info);
711 unsigned int offset = 0;
713 while (offset < blob->offset) {
714 free_single_dinfo((struct data_info *)(blob->data + offset));
715 offset += size;
719 void free_data_info_allocs(void)
721 struct allocator_struct *desc = &data_info_allocator;
722 struct allocation_blob *blob = desc->blobs;
724 desc->blobs = NULL;
725 desc->allocations = 0;
726 desc->total_bytes = 0;
727 desc->useful_bytes = 0;
728 desc->freelist = NULL;
729 while (blob) {
730 struct allocation_blob *next = blob->next;
731 free_dinfos(blob);
732 blob_free(blob, desc->chunking);
733 blob = next;
735 clear_data_range_alloc();
738 struct range_list_sval *range_list_to_sval(struct range_list *list)
740 struct data_range *tmp;
741 struct data_range_sval *tmp_sval;
742 struct range_list_sval *ret = NULL;
744 FOR_EACH_PTR(list, tmp) {
745 tmp_sval = drange_to_drange_sval(tmp);
746 add_ptr_list(&ret, tmp_sval);
747 } END_FOR_EACH_PTR(tmp);
748 return ret;
751 struct range_list *rl_sval_to_rl(struct range_list_sval *list)
753 struct data_range *tmp;
754 struct data_range_sval *tmp_sval;
755 struct range_list *ret = NULL;
757 FOR_EACH_PTR(list, tmp_sval) {
758 tmp = drange_sval_to_drange(tmp_sval);
759 add_ptr_list(&ret, tmp);
760 } END_FOR_EACH_PTR(tmp_sval);
761 return ret;