smatch_ranges.c

   1 /*
   2  * sparse/smatch_ranges.c
   3  *
   4  * Copyright (C) 2009 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include "parse.h"
  11 #include "smatch.h"
  12 #include "smatch_extra.h"
  13 #include "smatch_slist.h"
  14
  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
  20 char *show_rl(struct range_list *list)
  21 {
  22         struct data_range *tmp;
  23         char full[256];
  24         int i = 0;
  25
  26         full[0] = '\0';
  27         full[255] = '\0';
  28         FOR_EACH_PTR(list, tmp) {
  29                 if (i++)
  30                         strncat(full, ",", 254 - strlen(full));
  31                 if (sval_cmp(tmp->min, tmp->max) == 0) {
  32                         strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
  33                         continue;
  34                 }
  35                 strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
  36                 strncat(full, "-", 254 - strlen(full));
  37                 strncat(full, sval_to_str(tmp->max), 254 - strlen(full));
  38         } END_FOR_EACH_PTR(tmp);
  39         return alloc_sname(full);
  40 }
  41
  42 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg, char **endp)
  43 {
  44         int param;
  45         char *c = (char *)str;
  46
  47         if (*c != '[')
  48                 return 0;
  49         c++;
  50
  51         if (*c == '<') {
  52                 c++;
  53                 if (*c == '=') {
  54                         *comparison = SPECIAL_LTE;
  55                         c++;
  56                 } else {
  57                         *comparison = '<';
  58                 }
  59         } else if (*c == '=') {
  60                 c++;
  61                 c++;
  62                 *comparison = SPECIAL_EQUAL;
  63         } else if (*c == '>') {
  64                 c++;
  65                 if (*c == '=') {
  66                         *comparison = SPECIAL_GTE;
  67                         c++;
  68                 } else {
  69                         *comparison = '>';
  70                 }
  71         } else {
  72                 return 0;
  73         }
  74
  75         if (*c != 'p')
  76                 return 0;
  77         c++;
  78
  79         param = strtoll(c, &c, 10);
  80         c++; /* skip the ']' character */
  81         if (endp)
  82                 *endp = (char *)c;
  83
  84         if (!call)
  85                 return 0;
  86         *arg = get_argument_from_call_expr(call->args, param);
  87         if (!*arg)
  88                 return 0;
  89         return 1;
  90 }
  91
  92
  93 static sval_t get_val_from_key(int use_max, struct symbol *type, char *c, struct expression *call, char **endp)
  94 {
  95         struct expression *arg;
  96         int comparison;
  97         sval_t ret, tmp;
  98
  99         if (use_max)
 100                 ret = sval_type_max(type);
 101         else
 102                 ret = sval_type_min(type);
 103
 104         if (!str_to_comparison_arg(c, call, &comparison, &arg, endp))
 105                 return ret;
 106
 107         if (use_max && get_implied_max(arg, &tmp)) {
 108                 ret = tmp;
 109                 if (comparison == '<') {
 110                         tmp.value = 1;
 111                         ret = sval_binop(ret, '-', tmp);
 112                 }
 113         }
 114         if (!use_max && get_implied_min(arg, &tmp)) {
 115                 ret = tmp;
 116                 if (comparison == '>') {
 117                         tmp.value = 1;
 118                         ret = sval_binop(ret, '+', tmp);
 119                 }
 120         }
 121
 122         return ret;
 123 }
 124
 125 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, char *c, char **endp)
 126 {
 127         char *start = c;
 128         sval_t ret;
 129
 130         if (!strncmp(start, "max", 3)) {
 131                 ret = sval_type_max(type);
 132                 c += 3;
 133         } else if (!strncmp(start, "u64max", 6)) {
 134                 ret = sval_type_val(type, ULLONG_MAX);
 135                 c += 6;
 136         } else if (!strncmp(start, "s64max", 6)) {
 137                 ret = sval_type_val(type, LLONG_MAX);
 138                 c += 6;
 139         } else if (!strncmp(start, "u32max", 6)) {
 140                 ret = sval_type_val(type, UINT_MAX);
 141                 c += 6;
 142         } else if (!strncmp(start, "s32max", 6)) {
 143                 ret = sval_type_val(type, INT_MAX);
 144                 c += 6;
 145         } else if (!strncmp(start, "u16max", 6)) {
 146                 ret = sval_type_val(type, USHRT_MAX);
 147                 c += 6;
 148         } else if (!strncmp(start, "s16max", 6)) {
 149                 ret = sval_type_val(type, SHRT_MAX);
 150                 c += 6;
 151         } else if (!strncmp(start, "min", 3)) {
 152                 ret = sval_type_min(type);
 153                 c += 3;
 154         } else if (!strncmp(start, "s64min", 6)) {
 155                 ret = sval_type_val(type, LLONG_MIN);
 156                 c += 6;
 157         } else if (!strncmp(start, "s32min", 6)) {
 158                 ret = sval_type_val(type, INT_MIN);
 159                 c += 6;
 160         } else if (!strncmp(start, "s16min", 6)) {
 161                 ret = sval_type_val(type, SHRT_MIN);
 162                 c += 6;
 163         } else if (start[0] == '[') {
 164                 ret = get_val_from_key(1, type, start, call, &c);
 165         } else {
 166                 ret = sval_type_val(type, strtoll(start, &c, 10));
 167         }
 168         *endp = c;
 169         return ret;
 170 }
 171
 172 static void str_to_rl_helper(struct expression *call, struct symbol *type, char *value, struct range_list **rl)
 173 {
 174         sval_t min, max;
 175         char *c;
 176
 177         if (!type)
 178                 type = &llong_ctype;
 179         *rl = NULL;
 180
 181         if (value && strcmp(value, "empty") == 0)
 182                 return;
 183
 184         if (strncmp(value, "[==p", 4) == 0) {
 185                 struct expression *arg;
 186                 int comparison;
 187
 188                 if (!str_to_comparison_arg(value, call, &comparison, &arg, NULL))
 189                         goto out;
 190                 get_implied_rl(arg, rl);
 191                 goto out;
 192         }
 193
 194         c = value;
 195         while (*c) {
 196                 if (*c == '(')
 197                         c++;
 198                 min = parse_val(0, call, type, c, &c);
 199                 if (*c == ')')
 200                         c++;
 201                 if (!*c) {
 202                         add_range(rl, min, min);
 203                         break;
 204                 }
 205                 if (*c == ',') {
 206                         add_range(rl, min, min);
 207                         c++;
 208                         continue;
 209                 }
 210                 if (*c != '-') {
 211                         sm_msg("debug XXX: trouble parsing %s ", value);
 212                         break;
 213                 }
 214                 c++;
 215                 if (*c == '(')
 216                         c++;
 217                 max = parse_val(1, call, type, c, &c);
 218                 add_range(rl, min, max);
 219                 if (*c == ')')
 220                         c++;
 221                 if (!*c)
 222                         break;
 223                 if (*c != ',') {
 224                         sm_msg("debug YYY: trouble parsing %s %s", value, c);
 225                         break;
 226                 }
 227                 c++;
 228         }
 229
 230 out:
 231         *rl = cast_rl(type, *rl);
 232 }
 233
 234 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
 235 {
 236         return str_to_rl_helper(NULL, type, value, rl);
 237 }
 238
 239 void call_results_to_rl(struct expression *expr, struct symbol *type, char *value, struct range_list **rl)
 240 {
 241         return str_to_rl_helper(strip_expr(expr), type, value, rl);
 242 }
 243
 244 int is_whole_rl(struct range_list *rl)
 245 {
 246         struct data_range *drange;
 247
 248         if (ptr_list_empty(rl))
 249                 return 0;
 250         drange = first_ptr_list((struct ptr_list *)rl);
 251         if (sval_is_min(drange->min) && sval_is_max(drange->max))
 252                 return 1;
 253         return 0;
 254 }
 255
 256 sval_t rl_min(struct range_list *rl)
 257 {
 258         struct data_range *drange;
 259         sval_t ret;
 260
 261         ret.type = &llong_ctype;
 262         ret.value = LLONG_MIN;
 263         if (ptr_list_empty(rl))
 264                 return ret;
 265         drange = first_ptr_list((struct ptr_list *)rl);
 266         return drange->min;
 267 }
 268
 269 sval_t rl_max(struct range_list *rl)
 270 {
 271         struct data_range *drange;
 272         sval_t ret;
 273
 274         ret.type = &llong_ctype;
 275         ret.value = LLONG_MAX;
 276         if (ptr_list_empty(rl))
 277                 return ret;
 278         drange = last_ptr_list((struct ptr_list *)rl);
 279         return drange->max;
 280 }
 281
 282 int rl_to_sval(struct range_list *rl, sval_t *sval)
 283 {
 284         sval_t min, max;
 285
 286         if (!rl)
 287                 return 0;
 288
 289         min = rl_min(rl);
 290         max = rl_max(rl);
 291         if (sval_cmp(min, max) != 0)
 292                 return 0;
 293         *sval = min;
 294         return 1;
 295 }
 296
 297 struct symbol *rl_type(struct range_list *rl)
 298 {
 299         if (!rl)
 300                 return NULL;
 301         return rl_min(rl).type;
 302 }
 303
 304 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
 305 {
 306         struct data_range *ret;
 307
 308         if (perm)
 309                 ret = __alloc_perm_data_range(0);
 310         else
 311                 ret = __alloc_data_range(0);
 312         ret->min = min;
 313         ret->max = max;
 314         return ret;
 315 }
 316
 317 struct data_range *alloc_range(sval_t min, sval_t max)
 318 {
 319         return alloc_range_helper_sval(min, max, 0);
 320 }
 321
 322 struct data_range *alloc_range_perm(sval_t min, sval_t max)
 323 {
 324         return alloc_range_helper_sval(min, max, 1);
 325 }
 326
 327 struct range_list *alloc_rl(sval_t min, sval_t max)
 328 {
 329         struct range_list *rl = NULL;
 330
 331         if (sval_cmp(min, max) > 0)
 332                 return alloc_whole_rl(min.type);
 333
 334         add_range(&rl, min, max);
 335         return rl;
 336 }
 337
 338 struct range_list *alloc_whole_rl(struct symbol *type)
 339 {
 340         if (!type || type_positive_bits(type) < 0)
 341                 type = &llong_ctype;
 342
 343         return alloc_rl(sval_type_min(type), sval_type_max(type));
 344 }
 345
 346 void add_range(struct range_list **list, sval_t min, sval_t max)
 347 {
 348         struct data_range *tmp = NULL;
 349         struct data_range *new = NULL;
 350         int check_next = 0;
 351
 352         /*
 353          * FIXME:  This has a problem merging a range_list like: min-0,3-max
 354          * with a range like 1-2.  You end up with min-2,3-max instead of
 355          * just min-max.
 356          */
 357         FOR_EACH_PTR(*list, tmp) {
 358                 if (check_next) {
 359                         /* Sometimes we overlap with more than one range
 360                            so we have to delete or modify the next range. */
 361                         if (max.value + 1 == tmp->min.value) {
 362                                 /* join 2 ranges here */
 363                                 new->max = tmp->max;
 364                                 DELETE_CURRENT_PTR(tmp);
 365                                 return;
 366                         }
 367
 368                         /* Doesn't overlap with the next one. */
 369                         if (sval_cmp(max, tmp->min) < 0)
 370                                 return;
 371                         /* Partially overlaps with the next one. */
 372                         if (sval_cmp(max, tmp->max) < 0) {
 373                                 tmp->min.value = max.value + 1;
 374                                 return;
 375                         }
 376                         /* Completely overlaps with the next one. */
 377                         if (sval_cmp(max, tmp->max) >= 0) {
 378                                 DELETE_CURRENT_PTR(tmp);
 379                                 /* there could be more ranges to delete */
 380                                 continue;
 381                         }
 382                 }
 383                 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
 384                         /* join 2 ranges into a big range */
 385                         new = alloc_range(min, tmp->max);
 386                         REPLACE_CURRENT_PTR(tmp, new);
 387                         return;
 388                 }
 389                 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
 390                         new = alloc_range(min, max);
 391                         INSERT_CURRENT(new, tmp);
 392                         return;
 393                 }
 394                 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
 395                         if (sval_cmp(max, tmp->max) < 0)
 396                                 max = tmp->max;
 397                         else
 398                                 check_next = 1;
 399                         new = alloc_range(min, max);
 400                         REPLACE_CURRENT_PTR(tmp, new);
 401                         if (!check_next)
 402                                 return;
 403                         continue;
 404                 }
 405                 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
 406                         return;
 407                 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
 408                         min = tmp->min;
 409                         new = alloc_range(min, max);
 410                         REPLACE_CURRENT_PTR(tmp, new);
 411                         check_next = 1;
 412                         continue;
 413                 }
 414                 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
 415                         /* join 2 ranges into a big range */
 416                         new = alloc_range(tmp->min, max);
 417                         REPLACE_CURRENT_PTR(tmp, new);
 418                         check_next = 1;
 419                         continue;
 420                 }
 421                 /* the new range is entirely above the existing ranges */
 422         } END_FOR_EACH_PTR(tmp);
 423         if (check_next)
 424                 return;
 425         new = alloc_range(min, max);
 426         add_ptr_list(list, new);
 427 }
 428
 429 struct range_list *clone_rl(struct range_list *list)
 430 {
 431         struct data_range *tmp;
 432         struct range_list *ret = NULL;
 433
 434         FOR_EACH_PTR(list, tmp) {
 435                 add_ptr_list(&ret, tmp);
 436         } END_FOR_EACH_PTR(tmp);
 437         return ret;
 438 }
 439
 440 struct range_list *clone_rl_permanent(struct range_list *list)
 441 {
 442         struct data_range *tmp;
 443         struct data_range *new;
 444         struct range_list *ret = NULL;
 445
 446         FOR_EACH_PTR(list, tmp) {
 447                 new = alloc_range_perm(tmp->min, tmp->max);
 448                 add_ptr_list(&ret, new);
 449         } END_FOR_EACH_PTR(tmp);
 450         return ret;
 451 }
 452
 453 struct range_list *rl_union(struct range_list *one, struct range_list *two)
 454 {
 455         struct data_range *tmp;
 456         struct range_list *ret = NULL;
 457
 458         FOR_EACH_PTR(one, tmp) {
 459                 add_range(&ret, tmp->min, tmp->max);
 460         } END_FOR_EACH_PTR(tmp);
 461         FOR_EACH_PTR(two, tmp) {
 462                 add_range(&ret, tmp->min, tmp->max);
 463         } END_FOR_EACH_PTR(tmp);
 464         return ret;
 465 }
 466
 467 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
 468 {
 469         struct data_range *tmp;
 470         struct range_list *ret = NULL;
 471
 472         FOR_EACH_PTR(list, tmp) {
 473                 if (sval_cmp(tmp->max, min) < 0) {
 474                         add_range(&ret, tmp->min, tmp->max);
 475                         continue;
 476                 }
 477                 if (sval_cmp(tmp->min, max) > 0) {
 478                         add_range(&ret, tmp->min, tmp->max);
 479                         continue;
 480                 }
 481                 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
 482                         continue;
 483                 if (sval_cmp(tmp->min, min) >= 0) {
 484                         max.value++;
 485                         add_range(&ret, max, tmp->max);
 486                 } else if (sval_cmp(tmp->max, max) <= 0) {
 487                         min.value--;
 488                         add_range(&ret, tmp->min, min);
 489                 } else {
 490                         min.value--;
 491                         max.value++;
 492                         add_range(&ret, tmp->min, min);
 493                         add_range(&ret, max, tmp->max);
 494                 }
 495         } END_FOR_EACH_PTR(tmp);
 496         return ret;
 497 }
 498
 499 int ranges_equiv(struct data_range *one, struct data_range *two)
 500 {
 501         if (!one && !two)
 502                 return 1;
 503         if (!one || !two)
 504                 return 0;
 505         if (sval_cmp(one->min, two->min) != 0)
 506                 return 0;
 507         if (sval_cmp(one->max, two->max) != 0)
 508                 return 0;
 509         return 1;
 510 }
 511
 512 int rl_equiv(struct range_list *one, struct range_list *two)
 513 {
 514         struct data_range *one_range;
 515         struct data_range *two_range;
 516
 517         if (one == two)
 518                 return 1;
 519
 520         PREPARE_PTR_LIST(one, one_range);
 521         PREPARE_PTR_LIST(two, two_range);
 522         for (;;) {
 523                 if (!one_range && !two_range)
 524                         return 1;
 525                 if (!ranges_equiv(one_range, two_range))
 526                         return 0;
 527                 NEXT_PTR_LIST(one_range);
 528                 NEXT_PTR_LIST(two_range);
 529         }
 530         FINISH_PTR_LIST(two_range);
 531         FINISH_PTR_LIST(one_range);
 532
 533         return 1;
 534 }
 535
 536 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 537 {
 538         switch (comparison) {
 539         case '<':
 540         case SPECIAL_UNSIGNED_LT:
 541                 if (sval_cmp(left->min, right->max) < 0)
 542                         return 1;
 543                 return 0;
 544         case SPECIAL_UNSIGNED_LTE:
 545         case SPECIAL_LTE:
 546                 if (sval_cmp(left->min, right->max) <= 0)
 547                         return 1;
 548                 return 0;
 549         case SPECIAL_EQUAL:
 550                 if (sval_cmp(left->max, right->min) < 0)
 551                         return 0;
 552                 if (sval_cmp(left->min, right->max) > 0)
 553                         return 0;
 554                 return 1;
 555         case SPECIAL_UNSIGNED_GTE:
 556         case SPECIAL_GTE:
 557                 if (sval_cmp(left->max, right->min) >= 0)
 558                         return 1;
 559                 return 0;
 560         case '>':
 561         case SPECIAL_UNSIGNED_GT:
 562                 if (sval_cmp(left->max, right->min) > 0)
 563                         return 1;
 564                 return 0;
 565         case SPECIAL_NOTEQUAL:
 566                 if (sval_cmp(left->min, left->max) != 0)
 567                         return 1;
 568                 if (sval_cmp(right->min, right->max) != 0)
 569                         return 1;
 570                 if (sval_cmp(left->min, right->min) != 0)
 571                         return 1;
 572                 return 0;
 573         default:
 574                 sm_msg("unhandled comparison %d\n", comparison);
 575                 return 0;
 576         }
 577         return 0;
 578 }
 579
 580 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
 581 {
 582         if (left)
 583                 return true_comparison_range(var, comparison, val);
 584         else
 585                 return true_comparison_range(val, comparison, var);
 586 }
 587
 588 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
 589 {
 590         switch (comparison) {
 591         case '<':
 592         case SPECIAL_UNSIGNED_LT:
 593                 if (sval_cmp(left->max, right->min) >= 0)
 594                         return 1;
 595                 return 0;
 596         case SPECIAL_UNSIGNED_LTE:
 597         case SPECIAL_LTE:
 598                 if (sval_cmp(left->max, right->min) > 0)
 599                         return 1;
 600                 return 0;
 601         case SPECIAL_EQUAL:
 602                 if (sval_cmp(left->min, left->max) != 0)
 603                         return 1;
 604                 if (sval_cmp(right->min, right->max) != 0)
 605                         return 1;
 606                 if (sval_cmp(left->min, right->min) != 0)
 607                         return 1;
 608                 return 0;
 609         case SPECIAL_UNSIGNED_GTE:
 610         case SPECIAL_GTE:
 611                 if (sval_cmp(left->min, right->max) < 0)
 612                         return 1;
 613                 return 0;
 614         case '>':
 615         case SPECIAL_UNSIGNED_GT:
 616                 if (sval_cmp(left->min, right->max) <= 0)
 617                         return 1;
 618                 return 0;
 619         case SPECIAL_NOTEQUAL:
 620                 if (sval_cmp(left->max, right->min) < 0)
 621                         return 0;
 622                 if (sval_cmp(left->min, right->max) > 0)
 623                         return 0;
 624                 return 1;
 625         default:
 626                 sm_msg("unhandled comparison %d\n", comparison);
 627                 return 0;
 628         }
 629         return 0;
 630 }
 631
 632 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
 633 {
 634         if (left)
 635                 return false_comparison_range_sval(var, comparison, val);
 636         else
 637                 return false_comparison_range_sval(val, comparison, var);
 638 }
 639
 640 int possibly_true(struct expression *left, int comparison, struct expression *right)
 641 {
 642         struct range_list *rl_left, *rl_right;
 643         struct data_range *tmp_left, *tmp_right;
 644
 645         if (!get_implied_rl(left, &rl_left))
 646                 return 1;
 647         if (!get_implied_rl(right, &rl_right))
 648                 return 1;
 649
 650         FOR_EACH_PTR(rl_left, tmp_left) {
 651                 FOR_EACH_PTR(rl_right, tmp_right) {
 652                         if (true_comparison_range(tmp_left, comparison, tmp_right))
 653                                 return 1;
 654                 } END_FOR_EACH_PTR(tmp_right);
 655         } END_FOR_EACH_PTR(tmp_left);
 656         return 0;
 657 }
 658
 659 int possibly_false(struct expression *left, int comparison, struct expression *right)
 660 {
 661         struct range_list *rl_left, *rl_right;
 662         struct data_range *tmp_left, *tmp_right;
 663
 664         if (!get_implied_rl(left, &rl_left))
 665                 return 1;
 666         if (!get_implied_rl(right, &rl_right))
 667                 return 1;
 668
 669         FOR_EACH_PTR(rl_left, tmp_left) {
 670                 FOR_EACH_PTR(rl_right, tmp_right) {
 671                         if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
 672                                 return 1;
 673                 } END_FOR_EACH_PTR(tmp_right);
 674         } END_FOR_EACH_PTR(tmp_left);
 675         return 0;
 676 }
 677
 678 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 679 {
 680         struct data_range *left_tmp, *right_tmp;
 681
 682         if (!left_ranges || !right_ranges)
 683                 return 1;
 684
 685         FOR_EACH_PTR(left_ranges, left_tmp) {
 686                 FOR_EACH_PTR(right_ranges, right_tmp) {
 687                         if (true_comparison_range(left_tmp, comparison, right_tmp))
 688                                 return 1;
 689                 } END_FOR_EACH_PTR(right_tmp);
 690         } END_FOR_EACH_PTR(left_tmp);
 691         return 0;
 692 }
 693
 694 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 695 {
 696         struct data_range *left_tmp, *right_tmp;
 697
 698         if (!left_ranges || !right_ranges)
 699                 return 1;
 700
 701         FOR_EACH_PTR(left_ranges, left_tmp) {
 702                 FOR_EACH_PTR(right_ranges, right_tmp) {
 703                         if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
 704                                 return 1;
 705                 } END_FOR_EACH_PTR(right_tmp);
 706         } END_FOR_EACH_PTR(left_tmp);
 707         return 0;
 708 }
 709
 710 /* FIXME: the _rl here stands for right left so really it should be _lr */
 711 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
 712 {
 713         if (left)
 714                 return possibly_true_rl(a, comparison, b);
 715         else
 716                 return possibly_true_rl(b, comparison, a);
 717 }
 718
 719 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
 720 {
 721         if (left)
 722                 return possibly_false_rl(a, comparison, b);
 723         else
 724                 return possibly_false_rl(b, comparison, a);
 725 }
 726
 727 void tack_on(struct range_list **list, struct data_range *drange)
 728 {
 729         add_ptr_list(list, drange);
 730 }
 731
 732 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
 733 {
 734         add_ptr_list(rl_stack, rl);
 735 }
 736
 737 struct range_list *pop_rl(struct range_list_stack **rl_stack)
 738 {
 739         struct range_list *rl;
 740
 741         rl = last_ptr_list((struct ptr_list *)*rl_stack);
 742         delete_ptr_list_last((struct ptr_list **)rl_stack);
 743         return rl;
 744 }
 745
 746 struct range_list *top_rl(struct range_list_stack *rl_stack)
 747 {
 748         struct range_list *rl;
 749
 750         rl = last_ptr_list((struct ptr_list *)rl_stack);
 751         return rl;
 752 }
 753
 754 void filter_top_rl(struct range_list_stack **rl_stack, sval_t sval)
 755 {
 756         struct range_list *rl;
 757
 758         rl = pop_rl(rl_stack);
 759         rl = remove_range(rl, sval, sval);
 760         push_rl(rl_stack, rl);
 761 }
 762
 763 static int sval_too_big(struct symbol *type, sval_t sval)
 764 {
 765         if (type_bits(type) == 64)
 766                 return 0;
 767         if (sval.uvalue > ((1ULL << type_bits(type)) - 1))
 768                 return 1;
 769         return 0;
 770 }
 771
 772 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
 773 {
 774         /* If we're just adding a number, cast it and add it */
 775         if (sval_cmp(min, max) == 0) {
 776                 add_range(rl, sval_cast(type, min), sval_cast(type, max));
 777                 return;
 778         }
 779
 780         /* If the range is within the type range then add it */
 781         if (sval_fits(type, min) && sval_fits(type, max)) {
 782                 add_range(rl, sval_cast(type, min), sval_cast(type, max));
 783                 return;
 784         }
 785
 786         /*
 787          * If the range we are adding has more bits than the range type then
 788          * add the whole range type.  Eg:
 789          * 0x8000000000000000 - 0xf000000000000000 -> cast to int
 790          * This isn't totally the right thing to do.  We could be more granular.
 791          */
 792         if (sval_too_big(type, min) || sval_too_big(type, max)) {
 793                 add_range(rl, sval_type_min(type), sval_type_max(type));
 794                 return;
 795         }
 796
 797         /* Cast negative values to high positive values */
 798         if (sval_is_negative(min) && type_unsigned(type)) {
 799                 if (sval_is_positive(max)) {
 800                         if (sval_too_high(type, max)) {
 801                                 add_range(rl, sval_type_min(type), sval_type_max(type));
 802                                 return;
 803                         }
 804                         add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
 805                         max = sval_type_max(type);
 806                 } else {
 807                         max = sval_cast(type, max);
 808                 }
 809                 min = sval_cast(type, min);
 810                 add_range(rl, min, max);
 811         }
 812
 813         /* Cast high positive numbers to negative */
 814         if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
 815                 if (!sval_is_negative(sval_cast(type, min))) {
 816                         add_range(rl, sval_cast(type, min), sval_type_max(type));
 817                         min = sval_type_min(type);
 818                 } else {
 819                         min = sval_cast(type, min);
 820                 }
 821                 max = sval_cast(type, max);
 822                 add_range(rl, min, max);
 823         }
 824
 825         return;
 826 }
 827
 828 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
 829 {
 830         struct data_range *tmp;
 831         struct range_list *ret = NULL;
 832         sval_t min, max;
 833
 834         if (!rl)
 835                 return NULL;
 836
 837         if (!type || type == rl_type(rl))
 838                 return rl;
 839
 840         FOR_EACH_PTR(rl, tmp) {
 841                 min = tmp->min;
 842                 max = tmp->max;
 843                 if (type_bits(type) < type_bits(rl_type(rl))) {
 844                         min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
 845                         max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
 846                 }
 847                 if (sval_cmp(min, max) > 0) {
 848                         min = sval_cast(type, min);
 849                         max = sval_cast(type, max);
 850                 }
 851                 add_range_t(type, &ret, min, max);
 852         } END_FOR_EACH_PTR(tmp);
 853
 854         return ret;
 855 }
 856
 857 static int rl_is_sane(struct range_list *rl)
 858 {
 859         struct data_range *tmp;
 860         struct symbol *type;
 861
 862         type = rl_type(rl);
 863         FOR_EACH_PTR(rl, tmp) {
 864                 if (!sval_fits(type, tmp->min))
 865                         return 0;
 866                 if (!sval_fits(type, tmp->max))
 867                         return 0;
 868                 if (sval_cmp(tmp->min, tmp->max) > 0)
 869                         return 0;
 870         } END_FOR_EACH_PTR(tmp);
 871
 872         return 1;
 873 }
 874
 875 static int rl_type_consistent(struct range_list *rl)
 876 {
 877         struct data_range *tmp;
 878         struct symbol *type;
 879
 880         type = rl_type(rl);
 881         FOR_EACH_PTR(rl, tmp) {
 882                 if (type != tmp->min.type || type != tmp->max.type)
 883                         return 0;
 884         } END_FOR_EACH_PTR(tmp);
 885         return 1;
 886 }
 887
 888 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
 889 {
 890         struct data_range *tmp;
 891         struct range_list *ret = NULL;
 892
 893         if (!rl)
 894                 return NULL;
 895
 896         if (!type)
 897                 return rl;
 898         if (!rl_is_sane(rl))
 899                 return alloc_whole_rl(type);
 900         if (type == rl_type(rl) && rl_type_consistent(rl))
 901                 return rl;
 902
 903         FOR_EACH_PTR(rl, tmp) {
 904                 add_range_t(type, &ret, tmp->min, tmp->max);
 905         } END_FOR_EACH_PTR(tmp);
 906
 907         if (!ret)
 908                 return alloc_whole_rl(type);
 909
 910         return ret;
 911 }
 912
 913 struct range_list *rl_invert(struct range_list *orig)
 914 {
 915         struct range_list *ret = NULL;
 916         struct data_range *tmp;
 917         sval_t gap_min, abs_max, sval;
 918
 919         if (!orig)
 920                 return NULL;
 921
 922         gap_min = sval_type_min(rl_min(orig).type);
 923         abs_max = sval_type_max(rl_max(orig).type);
 924
 925         FOR_EACH_PTR(orig, tmp) {
 926                 if (sval_cmp(tmp->min, gap_min) > 0) {
 927                         sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
 928                         add_range(&ret, gap_min, sval);
 929                 }
 930                 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
 931                 if (sval_cmp(tmp->max, abs_max) == 0)
 932                         gap_min = abs_max;
 933         } END_FOR_EACH_PTR(tmp);
 934
 935         if (sval_cmp(gap_min, abs_max) < 0)
 936                 add_range(&ret, gap_min, abs_max);
 937
 938         return ret;
 939 }
 940
 941 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
 942 {
 943         struct data_range *tmp;
 944
 945         FOR_EACH_PTR(filter, tmp) {
 946                 rl = remove_range(rl, tmp->min, tmp->max);
 947         } END_FOR_EACH_PTR(tmp);
 948
 949         return rl;
 950 }
 951
 952 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
 953 {
 954         if (!two)
 955                 return NULL;
 956         two = rl_invert(two);
 957         return rl_filter(one, two);
 958 }
 959
 960 void free_rl(struct range_list **rlist)
 961 {
 962         __free_ptr_list((struct ptr_list **)rlist);
 963 }
 964
 965 static void free_single_dinfo(struct data_info *dinfo)
 966 {
 967         free_rl(&dinfo->value_ranges);
 968 }
 969
 970 static void free_dinfos(struct allocation_blob *blob)
 971 {
 972         unsigned int size = sizeof(struct data_info);
 973         unsigned int offset = 0;
 974
 975         while (offset < blob->offset) {
 976                 free_single_dinfo((struct data_info *)(blob->data + offset));
 977                 offset += size;
 978         }
 979 }
 980
 981 void free_data_info_allocs(void)
 982 {
 983         struct allocator_struct *desc = &data_info_allocator;
 984         struct allocation_blob *blob = desc->blobs;
 985
 986         desc->blobs = NULL;
 987         desc->allocations = 0;
 988         desc->total_bytes = 0;
 989         desc->useful_bytes = 0;
 990         desc->freelist = NULL;
 991         while (blob) {
 992                 struct allocation_blob *next = blob->next;
 993                 free_dinfos(blob);
 994                 blob_free(blob, desc->chunking);
 995                 blob = next;
 996         }
 997         clear_data_range_alloc();
 998 }
 999