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