smatch_ranges.c

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