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