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