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