smatch_ranges.c

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