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