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