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