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