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