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