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         struct symbol *type;
 805
 806         if (!get_implied_rl(left, &rl_left))
 807                 return 1;
 808         if (!get_implied_rl(right, &rl_right))
 809                 return 1;
 810
 811         type = rl_type(rl_left);
 812         if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
 813                 type = rl_type(rl_right);
 814         if (type_positive_bits(type) < 31)
 815                 type = &int_ctype;
 816
 817         rl_left = cast_rl(type, rl_left);
 818         rl_right = cast_rl(type, rl_right);
 819
 820         FOR_EACH_PTR(rl_left, tmp_left) {
 821                 FOR_EACH_PTR(rl_right, tmp_right) {
 822                         if (true_comparison_range(tmp_left, comparison, tmp_right))
 823                                 return 1;
 824                 } END_FOR_EACH_PTR(tmp_right);
 825         } END_FOR_EACH_PTR(tmp_left);
 826         return 0;
 827 }
 828
 829 int possibly_false(struct expression *left, int comparison, struct expression *right)
 830 {
 831         struct range_list *rl_left, *rl_right;
 832         struct data_range *tmp_left, *tmp_right;
 833         struct symbol *type;
 834
 835         if (!get_implied_rl(left, &rl_left))
 836                 return 1;
 837         if (!get_implied_rl(right, &rl_right))
 838                 return 1;
 839
 840         type = rl_type(rl_left);
 841         if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
 842                 type = rl_type(rl_right);
 843         if (type_positive_bits(type) < 31)
 844                 type = &int_ctype;
 845
 846         rl_left = cast_rl(type, rl_left);
 847         rl_right = cast_rl(type, rl_right);
 848
 849         FOR_EACH_PTR(rl_left, tmp_left) {
 850                 FOR_EACH_PTR(rl_right, tmp_right) {
 851                         if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
 852                                 return 1;
 853                 } END_FOR_EACH_PTR(tmp_right);
 854         } END_FOR_EACH_PTR(tmp_left);
 855         return 0;
 856 }
 857
 858 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 859 {
 860         struct data_range *left_tmp, *right_tmp;
 861
 862         if (!left_ranges || !right_ranges)
 863                 return 1;
 864
 865         FOR_EACH_PTR(left_ranges, left_tmp) {
 866                 FOR_EACH_PTR(right_ranges, right_tmp) {
 867                         if (true_comparison_range(left_tmp, comparison, right_tmp))
 868                                 return 1;
 869                 } END_FOR_EACH_PTR(right_tmp);
 870         } END_FOR_EACH_PTR(left_tmp);
 871         return 0;
 872 }
 873
 874 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 875 {
 876         struct data_range *left_tmp, *right_tmp;
 877
 878         if (!left_ranges || !right_ranges)
 879                 return 1;
 880
 881         FOR_EACH_PTR(left_ranges, left_tmp) {
 882                 FOR_EACH_PTR(right_ranges, right_tmp) {
 883                         if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
 884                                 return 1;
 885                 } END_FOR_EACH_PTR(right_tmp);
 886         } END_FOR_EACH_PTR(left_tmp);
 887         return 0;
 888 }
 889
 890 /* FIXME: the _rl here stands for right left so really it should be _lr */
 891 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
 892 {
 893         if (left)
 894                 return possibly_true_rl(a, comparison, b);
 895         else
 896                 return possibly_true_rl(b, comparison, a);
 897 }
 898
 899 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
 900 {
 901         if (left)
 902                 return possibly_false_rl(a, comparison, b);
 903         else
 904                 return possibly_false_rl(b, comparison, a);
 905 }
 906
 907 int rl_has_sval(struct range_list *rl, sval_t sval)
 908 {
 909         struct data_range *tmp;
 910
 911         FOR_EACH_PTR(rl, tmp) {
 912                 if (sval_cmp(tmp->min, sval) <= 0 &&
 913                     sval_cmp(tmp->max, sval) >= 0)
 914                         return 1;
 915         } END_FOR_EACH_PTR(tmp);
 916         return 0;
 917 }
 918
 919 void tack_on(struct range_list **list, struct data_range *drange)
 920 {
 921         add_ptr_list(list, drange);
 922 }
 923
 924 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
 925 {
 926         add_ptr_list(rl_stack, rl);
 927 }
 928
 929 struct range_list *pop_rl(struct range_list_stack **rl_stack)
 930 {
 931         struct range_list *rl;
 932
 933         rl = last_ptr_list((struct ptr_list *)*rl_stack);
 934         delete_ptr_list_last((struct ptr_list **)rl_stack);
 935         return rl;
 936 }
 937
 938 struct range_list *top_rl(struct range_list_stack *rl_stack)
 939 {
 940         struct range_list *rl;
 941
 942         rl = last_ptr_list((struct ptr_list *)rl_stack);
 943         return rl;
 944 }
 945
 946 void filter_top_rl(struct range_list_stack **rl_stack, sval_t sval)
 947 {
 948         struct range_list *rl;
 949
 950         rl = pop_rl(rl_stack);
 951         rl = remove_range(rl, sval, sval);
 952         push_rl(rl_stack, rl);
 953 }
 954
 955 static int sval_too_big(struct symbol *type, sval_t sval)
 956 {
 957         if (type_bits(type) == 64)
 958                 return 0;
 959         if (sval.uvalue > ((1ULL << type_bits(type)) - 1))
 960                 return 1;
 961         return 0;
 962 }
 963
 964 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
 965 {
 966         /* If we're just adding a number, cast it and add it */
 967         if (sval_cmp(min, max) == 0) {
 968                 add_range(rl, sval_cast(type, min), sval_cast(type, max));
 969                 return;
 970         }
 971
 972         /* If the range is within the type range then add it */
 973         if (sval_fits(type, min) && sval_fits(type, max)) {
 974                 add_range(rl, sval_cast(type, min), sval_cast(type, max));
 975                 return;
 976         }
 977
 978         /*
 979          * If the range we are adding has more bits than the range type then
 980          * add the whole range type.  Eg:
 981          * 0x8000000000000000 - 0xf000000000000000 -> cast to int
 982          * This isn't totally the right thing to do.  We could be more granular.
 983          */
 984         if (sval_too_big(type, min) || sval_too_big(type, max)) {
 985                 add_range(rl, sval_type_min(type), sval_type_max(type));
 986                 return;
 987         }
 988
 989         /* Cast negative values to high positive values */
 990         if (sval_is_negative(min) && type_unsigned(type)) {
 991                 if (sval_is_positive(max)) {
 992                         if (sval_too_high(type, max)) {
 993                                 add_range(rl, sval_type_min(type), sval_type_max(type));
 994                                 return;
 995                         }
 996                         add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
 997                         max = sval_type_max(type);
 998                 } else {
 999                         max = sval_cast(type, max);
1000                 }
1001                 min = sval_cast(type, min);
1002                 add_range(rl, min, max);
1003         }
1004
1005         /* Cast high positive numbers to negative */
1006         if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
1007                 if (!sval_is_negative(sval_cast(type, min))) {
1008                         add_range(rl, sval_cast(type, min), sval_type_max(type));
1009                         min = sval_type_min(type);
1010                 } else {
1011                         min = sval_cast(type, min);
1012                 }
1013                 max = sval_cast(type, max);
1014                 add_range(rl, min, max);
1015         }
1016
1017         add_range(rl, min, max);
1018         return;
1019 }
1020
1021 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1022 {
1023         struct data_range *tmp;
1024         struct range_list *ret = NULL;
1025         sval_t min, max;
1026
1027         if (!rl)
1028                 return NULL;
1029
1030         if (!type || type == rl_type(rl))
1031                 return rl;
1032
1033         FOR_EACH_PTR(rl, tmp) {
1034                 min = tmp->min;
1035                 max = tmp->max;
1036                 if (type_bits(type) < type_bits(rl_type(rl))) {
1037                         min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1038                         max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1039                 }
1040                 if (sval_cmp(min, max) > 0) {
1041                         min = sval_cast(type, min);
1042                         max = sval_cast(type, max);
1043                 }
1044                 add_range_t(type, &ret, min, max);
1045         } END_FOR_EACH_PTR(tmp);
1046
1047         return ret;
1048 }
1049
1050 static int rl_is_sane(struct range_list *rl)
1051 {
1052         struct data_range *tmp;
1053         struct symbol *type;
1054
1055         type = rl_type(rl);
1056         FOR_EACH_PTR(rl, tmp) {
1057                 if (!sval_fits(type, tmp->min))
1058                         return 0;
1059                 if (!sval_fits(type, tmp->max))
1060                         return 0;
1061                 if (sval_cmp(tmp->min, tmp->max) > 0)
1062                         return 0;
1063         } END_FOR_EACH_PTR(tmp);
1064
1065         return 1;
1066 }
1067
1068 static int rl_type_consistent(struct range_list *rl)
1069 {
1070         struct data_range *tmp;
1071         struct symbol *type;
1072
1073         type = rl_type(rl);
1074         FOR_EACH_PTR(rl, tmp) {
1075                 if (type != tmp->min.type || type != tmp->max.type)
1076                         return 0;
1077         } END_FOR_EACH_PTR(tmp);
1078         return 1;
1079 }
1080
1081 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1082 {
1083         struct data_range *tmp;
1084         struct range_list *ret = NULL;
1085
1086         if (!rl)
1087                 return NULL;
1088
1089         if (!type)
1090                 return rl;
1091         if (!rl_is_sane(rl))
1092                 return alloc_whole_rl(type);
1093         if (type == rl_type(rl) && rl_type_consistent(rl))
1094                 return rl;
1095
1096         FOR_EACH_PTR(rl, tmp) {
1097                 add_range_t(type, &ret, tmp->min, tmp->max);
1098         } END_FOR_EACH_PTR(tmp);
1099
1100         if (!ret)
1101                 return alloc_whole_rl(type);
1102
1103         return ret;
1104 }
1105
1106 struct range_list *rl_invert(struct range_list *orig)
1107 {
1108         struct range_list *ret = NULL;
1109         struct data_range *tmp;
1110         sval_t gap_min, abs_max, sval;
1111
1112         if (!orig)
1113                 return NULL;
1114
1115         gap_min = sval_type_min(rl_min(orig).type);
1116         abs_max = sval_type_max(rl_max(orig).type);
1117
1118         FOR_EACH_PTR(orig, tmp) {
1119                 if (sval_cmp(tmp->min, gap_min) > 0) {
1120                         sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
1121                         add_range(&ret, gap_min, sval);
1122                 }
1123                 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
1124                 if (sval_cmp(tmp->max, abs_max) == 0)
1125                         gap_min = abs_max;
1126         } END_FOR_EACH_PTR(tmp);
1127
1128         if (sval_cmp(gap_min, abs_max) < 0)
1129                 add_range(&ret, gap_min, abs_max);
1130
1131         return ret;
1132 }
1133
1134 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1135 {
1136         struct data_range *tmp;
1137
1138         FOR_EACH_PTR(filter, tmp) {
1139                 rl = remove_range(rl, tmp->min, tmp->max);
1140         } END_FOR_EACH_PTR(tmp);
1141
1142         return rl;
1143 }
1144
1145 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1146 {
1147         struct range_list *one_orig;
1148         struct range_list *two_orig;
1149         struct range_list *ret;
1150         struct symbol *ret_type;
1151         struct symbol *small_type;
1152         struct symbol *large_type;
1153
1154         if (!two)
1155                 return NULL;
1156         if (!one)
1157                 return NULL;
1158
1159         one_orig = one;
1160         two_orig = two;
1161
1162         ret_type = rl_type(one);
1163         small_type = rl_type(one);
1164         large_type = rl_type(two);
1165
1166         if (type_bits(rl_type(two)) < type_bits(small_type)) {
1167                 small_type = rl_type(two);
1168                 large_type = rl_type(one);
1169         }
1170
1171         one = cast_rl(large_type, one);
1172         two = cast_rl(large_type, two);
1173
1174         ret = one;
1175         one = rl_invert(one);
1176         two = rl_invert(two);
1177
1178         ret = rl_filter(ret, one);
1179         ret = rl_filter(ret, two);
1180
1181         one = cast_rl(small_type, one_orig);
1182         two = cast_rl(small_type, two_orig);
1183
1184         one = rl_invert(one);
1185         two = rl_invert(two);
1186
1187         ret = cast_rl(small_type, ret);
1188         ret = rl_filter(ret, one);
1189         ret = rl_filter(ret, two);
1190
1191         return cast_rl(ret_type, ret);
1192 }
1193
1194 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1195 {
1196         sval_t zero;
1197         sval_t max;
1198
1199         max = rl_max(right);
1200         if (sval_is_max(max))
1201                 return left;
1202         if (max.value == 0)
1203                 return NULL;
1204         max.value--;
1205         if (sval_is_negative(max))
1206                 return NULL;
1207         if (sval_cmp(rl_max(left), max) < 0)
1208                 return left;
1209         zero = max;
1210         zero.value = 0;
1211         return alloc_rl(zero, max);
1212 }
1213
1214 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1215 {
1216         sval_t min, max;
1217
1218         if (sval_is_max(rl_max(left)))
1219                 return NULL;
1220         if (sval_is_max(rl_max(right)))
1221                 return NULL;
1222
1223         if (sval_is_negative(rl_min(left)))
1224                 return NULL;
1225         if (sval_cmp_val(rl_min(right), 0) <= 0)
1226                 return NULL;
1227
1228         max = sval_binop(rl_max(left), '/', rl_min(right));
1229         min = sval_binop(rl_min(left), '/', rl_max(right));
1230
1231         return alloc_rl(min, max);
1232 }
1233
1234 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1235 {
1236         sval_t min, max;
1237
1238         if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1239                 return NULL;
1240         min = sval_binop(rl_min(left), op, rl_min(right));
1241
1242         if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1243                 return NULL;
1244         max = sval_binop(rl_max(left), op, rl_max(right));
1245
1246         return alloc_rl(min, max);
1247 }
1248
1249 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1250 {
1251         struct symbol *cast_type;
1252         sval_t left_sval, right_sval;
1253         struct range_list *ret = NULL;
1254
1255         cast_type = rl_type(left);
1256         if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
1257                 cast_type = rl_type(right);
1258         if (sval_type_max(cast_type).uvalue < INT_MAX)
1259                 cast_type = &int_ctype;
1260
1261         left = cast_rl(cast_type, left);
1262         right = cast_rl(cast_type, right);
1263
1264         if (!left || !right)
1265                 return alloc_whole_rl(cast_type);
1266
1267         if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
1268                 sval_t val = sval_binop(left_sval, op, right_sval);
1269                 return alloc_rl(val, val);
1270         }
1271
1272         switch (op) {
1273         case '%':
1274                 ret = handle_mod_rl(left, right);
1275                 break;
1276         case '/':
1277                 ret = handle_divide_rl(left, right);
1278                 break;
1279         case '*':
1280         case '+':
1281                 ret = handle_add_mult_rl(left, op, right);
1282                 break;
1283
1284         /* FIXME:  Do the rest as well */
1285         case '-':
1286         case '|':
1287         case '&':
1288         case SPECIAL_RIGHTSHIFT:
1289         case SPECIAL_LEFTSHIFT:
1290         case '^':
1291                 break;
1292         }
1293
1294         if (!ret)
1295                 ret = alloc_whole_rl(cast_type);
1296         return ret;
1297 }
1298
1299 void free_rl(struct range_list **rlist)
1300 {
1301         __free_ptr_list((struct ptr_list **)rlist);
1302 }
1303
1304 static void free_single_dinfo(struct data_info *dinfo)
1305 {
1306         free_rl(&dinfo->value_ranges);
1307 }
1308
1309 static void free_dinfos(struct allocation_blob *blob)
1310 {
1311         unsigned int size = sizeof(struct data_info);
1312         unsigned int offset = 0;
1313
1314         while (offset < blob->offset) {
1315                 free_single_dinfo((struct data_info *)(blob->data + offset));
1316                 offset += size;
1317         }
1318 }
1319
1320 void free_data_info_allocs(void)
1321 {
1322         struct allocator_struct *desc = &data_info_allocator;
1323         struct allocation_blob *blob = desc->blobs;
1324
1325         desc->blobs = NULL;
1326         desc->allocations = 0;
1327         desc->total_bytes = 0;
1328         desc->useful_bytes = 0;
1329         desc->freelist = NULL;
1330         while (blob) {
1331                 struct allocation_blob *next = blob->next;
1332                 free_dinfos(blob);
1333                 blob_free(blob, desc->chunking);
1334                 blob = next;
1335         }
1336         clear_data_range_alloc();
1337 }
1338