1 /*
   2  * Copyright (C) 2012 Oracle.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17 
  18 /*
  19  * The point here is to store the relationships between two variables.
  20  * Ie:  y > x.
  21  * To do that we create a state with the two variables in alphabetical order:
  22  * ->name = "x vs y" and the state would be "<".  On the false path the state
  23  * would be ">=".
  24  *
  25  * Part of the trick of it is that if x or y is modified then we need to reset
  26  * the state.  We need to keep a list of all the states which depend on x and
  27  * all the states which depend on y.  The link_id code handles this.
  28  *
  29  */
  30 
  31 #include "smatch.h"
  32 #include "smatch_extra.h"
  33 #include "smatch_slist.h"
  34 
  35 static int compare_id;
  36 static int link_id;
  37 static int inc_dec_id;
  38 static int inc_dec_link_id;
  39 
  40 static void add_comparison(struct expression *left, int comparison, struct expression *right);
  41 
  42 /* for handling for loops */
  43 STATE(start);
  44 STATE(incremented);
  45 
  46 ALLOCATOR(compare_data, "compare data");
  47 
  48 static struct symbol *vsl_to_sym(struct var_sym_list *vsl)
  49 {
  50         struct var_sym *vs;
  51 
  52         if (!vsl)
  53                 return NULL;
  54         if (ptr_list_size((struct ptr_list *)vsl) != 1)
  55                 return NULL;
  56         vs = first_ptr_list((struct ptr_list *)vsl);
  57         return vs->sym;
  58 }
  59 
  60 struct smatch_state *alloc_compare_state(
  61                 struct expression *left,
  62                 const char *left_var, struct var_sym_list *left_vsl,
  63                 int comparison,
  64                 struct expression *right,
  65                 const char *right_var, struct var_sym_list *right_vsl)
  66 {
  67         struct smatch_state *state;
  68         struct compare_data *data;
  69 
  70         state = __alloc_smatch_state(0);
  71         state->name = alloc_sname(show_special(comparison));
  72         data = __alloc_compare_data(0);
  73         data->left = left;
  74         data->left_var = alloc_sname(left_var);
  75         data->left_vsl = clone_var_sym_list(left_vsl);
  76         data->comparison = comparison;
  77         data->right = right;
  78         data->right_var = alloc_sname(right_var);
  79         data->right_vsl = clone_var_sym_list(right_vsl);
  80         state->data = data;
  81         return state;
  82 }
  83 
  84 int state_to_comparison(struct smatch_state *state)
  85 {
  86         if (!state || !state->data)
  87                 return 0;
  88         return ((struct compare_data *)state->data)->comparison;
  89 }
  90 
  91 /*
  92  * flip_comparison() reverses the op left and right.  So "x >= y" becomes "y <= x".
  93  */
  94 int flip_comparison(int op)
  95 {
  96         switch (op) {
  97         case 0:
  98                 return 0;
  99         case '<':
 100                 return '>';
 101         case SPECIAL_UNSIGNED_LT:
 102                 return SPECIAL_UNSIGNED_GT;
 103         case SPECIAL_LTE:
 104                 return SPECIAL_GTE;
 105         case SPECIAL_UNSIGNED_LTE:
 106                 return SPECIAL_UNSIGNED_GTE;
 107         case SPECIAL_EQUAL:
 108                 return SPECIAL_EQUAL;
 109         case SPECIAL_NOTEQUAL:
 110                 return SPECIAL_NOTEQUAL;
 111         case SPECIAL_GTE:
 112                 return SPECIAL_LTE;
 113         case SPECIAL_UNSIGNED_GTE:
 114                 return SPECIAL_UNSIGNED_LTE;
 115         case '>':
 116                 return '<';
 117         case SPECIAL_UNSIGNED_GT:
 118                 return SPECIAL_UNSIGNED_LT;
 119         default:
 120                 sm_perror("unhandled comparison %d", op);
 121                 return op;
 122         }
 123 }
 124 
 125 int negate_comparison(int op)
 126 {
 127         switch (op) {
 128         case 0:
 129                 return 0;
 130         case '<':
 131                 return SPECIAL_GTE;
 132         case SPECIAL_UNSIGNED_LT:
 133                 return SPECIAL_UNSIGNED_GTE;
 134         case SPECIAL_LTE:
 135                 return '>';
 136         case SPECIAL_UNSIGNED_LTE:
 137                 return SPECIAL_UNSIGNED_GT;
 138         case SPECIAL_EQUAL:
 139                 return SPECIAL_NOTEQUAL;
 140         case SPECIAL_NOTEQUAL:
 141                 return SPECIAL_EQUAL;
 142         case SPECIAL_GTE:
 143                 return '<';
 144         case SPECIAL_UNSIGNED_GTE:
 145                 return SPECIAL_UNSIGNED_LT;
 146         case '>':
 147                 return SPECIAL_LTE;
 148         case SPECIAL_UNSIGNED_GT:
 149                 return SPECIAL_UNSIGNED_LTE;
 150         default:
 151                 sm_perror("unhandled comparison %d", op);
 152                 return op;
 153         }
 154 }
 155 
 156 static int rl_comparison(struct range_list *left_rl, struct range_list *right_rl)
 157 {
 158         sval_t left_min, left_max, right_min, right_max;
 159         struct symbol *type = &int_ctype;
 160 
 161         if (!left_rl || !right_rl)
 162                 return 0;
 163 
 164         if (type_positive_bits(rl_type(left_rl)) > type_positive_bits(type))
 165                 type = rl_type(left_rl);
 166         if (type_positive_bits(rl_type(right_rl)) > type_positive_bits(type))
 167                 type = rl_type(right_rl);
 168 
 169         left_rl = cast_rl(type, left_rl);
 170         right_rl = cast_rl(type, right_rl);
 171 
 172         left_min = rl_min(left_rl);
 173         left_max = rl_max(left_rl);
 174         right_min = rl_min(right_rl);
 175         right_max = rl_max(right_rl);
 176 
 177         if (left_min.value == left_max.value &&
 178             right_min.value == right_max.value &&
 179             left_min.value == right_min.value)
 180                 return SPECIAL_EQUAL;
 181 
 182         if (sval_cmp(left_max, right_min) < 0)
 183                 return '<';
 184         if (sval_cmp(left_max, right_min) == 0)
 185                 return SPECIAL_LTE;
 186         if (sval_cmp(left_min, right_max) > 0)
 187                 return '>';
 188         if (sval_cmp(left_min, right_max) == 0)
 189                 return SPECIAL_GTE;
 190 
 191         return 0;
 192 }
 193 
 194 static int comparison_from_extra(struct expression *a, struct expression *b)
 195 {
 196         struct range_list *left, *right;
 197 
 198         if (!get_implied_rl(a, &left))
 199                 return 0;
 200         if (!get_implied_rl(b, &right))
 201                 return 0;
 202 
 203         return rl_comparison(left, right);
 204 }
 205 
 206 static struct range_list *get_orig_rl(struct var_sym_list *vsl)
 207 {
 208         struct symbol *sym;
 209         struct smatch_state *state;
 210 
 211         if (!vsl)
 212                 return NULL;
 213         sym = vsl_to_sym(vsl);
 214         if (!sym || !sym->ident)
 215                 return NULL;
 216         state = get_orig_estate(sym->ident->name, sym);
 217         return estate_rl(state);
 218 }
 219 
 220 static struct smatch_state *unmatched_comparison(struct sm_state *sm)
 221 {
 222         struct compare_data *data = sm->state->data;
 223         struct range_list *left_rl, *right_rl;
 224         int op;
 225 
 226         if (!data)
 227                 return &undefined;
 228 
 229         if (strstr(data->left_var, " orig"))
 230                 left_rl = get_orig_rl(data->left_vsl);
 231         else if (!get_implied_rl_var_sym(data->left_var, vsl_to_sym(data->left_vsl), &left_rl))
 232                 return &undefined;
 233 
 234         if (strstr(data->right_var, " orig"))
 235                 right_rl = get_orig_rl(data->right_vsl);
 236         else if (!get_implied_rl_var_sym(data->right_var, vsl_to_sym(data->right_vsl), &right_rl))
 237                 return &undefined;
 238 
 239         op = rl_comparison(left_rl, right_rl);
 240         if (op)
 241                 return alloc_compare_state(
 242                                 data->left, data->left_var, data->left_vsl,
 243                                 op,
 244                                 data->right, data->right_var, data->right_vsl);
 245 
 246         return &undefined;
 247 }
 248 
 249 /* remove_unsigned_from_comparison() is obviously a hack. */
 250 int remove_unsigned_from_comparison(int op)
 251 {
 252         switch (op) {
 253         case SPECIAL_UNSIGNED_LT:
 254                 return '<';
 255         case SPECIAL_UNSIGNED_LTE:
 256                 return SPECIAL_LTE;
 257         case SPECIAL_UNSIGNED_GTE:
 258                 return SPECIAL_GTE;
 259         case SPECIAL_UNSIGNED_GT:
 260                 return '>';
 261         default:
 262                 return op;
 263         }
 264 }
 265 
 266 /*
 267  * This is for when you merge states "a < b" and "a == b", the result is that
 268  * we can say for sure, "a <= b" after the merge.
 269  */
 270 int merge_comparisons(int one, int two)
 271 {
 272         int LT, EQ, GT;
 273 
 274         if (!one || !two)
 275                 return 0;
 276 
 277         one = remove_unsigned_from_comparison(one);
 278         two = remove_unsigned_from_comparison(two);
 279 
 280         if (one == two)
 281                 return one;
 282 
 283         LT = EQ = GT = 0;
 284 
 285         switch (one) {
 286         case '<':
 287                 LT = 1;
 288                 break;
 289         case SPECIAL_LTE:
 290                 LT = 1;
 291                 EQ = 1;
 292                 break;
 293         case SPECIAL_EQUAL:
 294                 EQ = 1;
 295                 break;
 296         case SPECIAL_GTE:
 297                 GT = 1;
 298                 EQ = 1;
 299                 break;
 300         case '>':
 301                 GT = 1;
 302         }
 303 
 304         switch (two) {
 305         case '<':
 306                 LT = 1;
 307                 break;
 308         case SPECIAL_LTE:
 309                 LT = 1;
 310                 EQ = 1;
 311                 break;
 312         case SPECIAL_EQUAL:
 313                 EQ = 1;
 314                 break;
 315         case SPECIAL_GTE:
 316                 GT = 1;
 317                 EQ = 1;
 318                 break;
 319         case '>':
 320                 GT = 1;
 321         }
 322 
 323         if (LT && EQ && GT)
 324                 return 0;
 325         if (LT && EQ)
 326                 return SPECIAL_LTE;
 327         if (LT && GT)
 328                 return SPECIAL_NOTEQUAL;
 329         if (LT)
 330                 return '<';
 331         if (EQ && GT)
 332                 return SPECIAL_GTE;
 333         if (GT)
 334                 return '>';
 335         return 0;
 336 }
 337 
 338 /*
 339  * This is for if you have "a < b" and "b <= c".  Or in other words,
 340  * "a < b <= c".  You would call this like get_combined_comparison('<', '<=').
 341  * The return comparison would be '<'.
 342  *
 343  * This function is different from merge_comparisons(), for example:
 344  * merge_comparison('<', '==') returns '<='
 345  * get_combined_comparison('<', '==') returns '<'
 346  */
 347 int combine_comparisons(int left_compare, int right_compare)
 348 {
 349         int LT, EQ, GT;
 350 
 351         left_compare = remove_unsigned_from_comparison(left_compare);
 352         right_compare = remove_unsigned_from_comparison(right_compare);
 353 
 354         LT = EQ = GT = 0;
 355 
 356         switch (left_compare) {
 357         case '<':
 358                 LT++;
 359                 break;
 360         case SPECIAL_LTE:
 361                 LT++;
 362                 EQ++;
 363                 break;
 364         case SPECIAL_EQUAL:
 365                 return right_compare;
 366         case SPECIAL_GTE:
 367                 GT++;
 368                 EQ++;
 369                 break;
 370         case '>':
 371                 GT++;
 372         }
 373 
 374         switch (right_compare) {
 375         case '<':
 376                 LT++;
 377                 break;
 378         case SPECIAL_LTE:
 379                 LT++;
 380                 EQ++;
 381                 break;
 382         case SPECIAL_EQUAL:
 383                 return left_compare;
 384         case SPECIAL_GTE:
 385                 GT++;
 386                 EQ++;
 387                 break;
 388         case '>':
 389                 GT++;
 390         }
 391 
 392         if (LT == 2) {
 393                 if (EQ == 2)
 394                         return SPECIAL_LTE;
 395                 return '<';
 396         }
 397 
 398         if (GT == 2) {
 399                 if (EQ == 2)
 400                         return SPECIAL_GTE;
 401                 return '>';
 402         }
 403         return 0;
 404 }
 405 
 406 int filter_comparison(int orig, int op)
 407 {
 408         if (orig == op)
 409                 return orig;
 410 
 411         orig = remove_unsigned_from_comparison(orig);
 412         op = remove_unsigned_from_comparison(op);
 413 
 414         switch (orig) {
 415         case 0:
 416                 return op;
 417         case '<':
 418                 switch (op) {
 419                 case '<':
 420                 case SPECIAL_LTE:
 421                 case SPECIAL_NOTEQUAL:
 422                         return '<';
 423                 }
 424                 return 0;
 425         case SPECIAL_LTE:
 426                 switch (op) {
 427                 case '<':
 428                 case SPECIAL_LTE:
 429                 case SPECIAL_EQUAL:
 430                         return op;
 431                 case SPECIAL_NOTEQUAL:
 432                         return '<';
 433                 }
 434                 return 0;
 435         case SPECIAL_EQUAL:
 436                 switch (op) {
 437                 case SPECIAL_LTE:
 438                 case SPECIAL_EQUAL:
 439                 case SPECIAL_GTE:
 440                 case SPECIAL_UNSIGNED_LTE:
 441                 case SPECIAL_UNSIGNED_GTE:
 442                         return SPECIAL_EQUAL;
 443                 }
 444                 return 0;
 445         case SPECIAL_NOTEQUAL:
 446                 switch (op) {
 447                 case '<':
 448                 case SPECIAL_LTE:
 449                         return '<';
 450                 case SPECIAL_UNSIGNED_LT:
 451                 case SPECIAL_UNSIGNED_LTE:
 452                         return SPECIAL_UNSIGNED_LT;
 453                 case SPECIAL_NOTEQUAL:
 454                         return op;
 455                 case '>':
 456                 case SPECIAL_GTE:
 457                         return '>';
 458                 case SPECIAL_UNSIGNED_GT:
 459                 case SPECIAL_UNSIGNED_GTE:
 460                         return SPECIAL_UNSIGNED_GT;
 461                 }
 462                 return 0;
 463         case SPECIAL_GTE:
 464                 switch (op) {
 465                 case SPECIAL_LTE:
 466                         return SPECIAL_EQUAL;
 467                 case '>':
 468                 case SPECIAL_GTE:
 469                 case SPECIAL_EQUAL:
 470                         return op;
 471                 case SPECIAL_NOTEQUAL:
 472                         return '>';
 473                 }
 474                 return 0;
 475         case '>':
 476                 switch (op) {
 477                 case '>':
 478                 case SPECIAL_GTE:
 479                 case SPECIAL_NOTEQUAL:
 480                         return '>';
 481                 }
 482                 return 0;
 483         case SPECIAL_UNSIGNED_LT:
 484                 switch (op) {
 485                 case SPECIAL_UNSIGNED_LT:
 486                 case SPECIAL_UNSIGNED_LTE:
 487                 case SPECIAL_NOTEQUAL:
 488                         return SPECIAL_UNSIGNED_LT;
 489                 }
 490                 return 0;
 491         case SPECIAL_UNSIGNED_LTE:
 492                 switch (op) {
 493                 case SPECIAL_UNSIGNED_LT:
 494                 case SPECIAL_UNSIGNED_LTE:
 495                 case SPECIAL_EQUAL:
 496                         return op;
 497                 case SPECIAL_NOTEQUAL:
 498                         return SPECIAL_UNSIGNED_LT;
 499                 case SPECIAL_UNSIGNED_GTE:
 500                         return SPECIAL_EQUAL;
 501                 }
 502                 return 0;
 503         case SPECIAL_UNSIGNED_GTE:
 504                 switch (op) {
 505                 case SPECIAL_UNSIGNED_LTE:
 506                         return SPECIAL_EQUAL;
 507                 case SPECIAL_NOTEQUAL:
 508                         return SPECIAL_UNSIGNED_GT;
 509                 case SPECIAL_EQUAL:
 510                 case SPECIAL_UNSIGNED_GTE:
 511                 case SPECIAL_UNSIGNED_GT:
 512                         return op;
 513                 }
 514                 return 0;
 515         case SPECIAL_UNSIGNED_GT:
 516                 switch (op) {
 517                 case SPECIAL_UNSIGNED_GT:
 518                 case SPECIAL_UNSIGNED_GTE:
 519                 case SPECIAL_NOTEQUAL:
 520                         return SPECIAL_UNSIGNED_GT;
 521                 }
 522                 return 0;
 523         }
 524         return 0;
 525 }
 526 
 527 static void pre_merge_hook(struct sm_state *sm)
 528 {
 529         struct compare_data *data = sm->state->data;
 530         int other;
 531 
 532         if (!data)
 533                 return;
 534         other = get_comparison(data->left, data->right);
 535         if (!other)
 536                 return;
 537 
 538         set_state(compare_id, sm->name, NULL,
 539                   alloc_compare_state(data->left, data->left_var, data->left_vsl,
 540                                       other,
 541                                       data->right, data->right_var, data->right_vsl));
 542 }
 543 
 544 struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
 545 {
 546         struct compare_data *data = s1->data;
 547         int op;
 548 
 549         op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
 550         if (op)
 551                 return alloc_compare_state(
 552                                 data->left, data->left_var, data->left_vsl,
 553                                 op,
 554                                 data->right, data->right_var, data->right_vsl);
 555         return &undefined;
 556 }
 557 
 558 static struct smatch_state *alloc_link_state(struct string_list *links)
 559 {
 560         struct smatch_state *state;
 561         static char buf[256];
 562         char *tmp;
 563         int i;
 564 
 565         state = __alloc_smatch_state(0);
 566 
 567         i = 0;
 568         FOR_EACH_PTR(links, tmp) {
 569                 if (!i++) {
 570                         snprintf(buf, sizeof(buf), "%s", tmp);
 571                 } else {
 572                         append(buf, ", ", sizeof(buf));
 573                         append(buf, tmp, sizeof(buf));
 574                 }
 575         } END_FOR_EACH_PTR(tmp);
 576 
 577         state->name = alloc_sname(buf);
 578         state->data = links;
 579         return state;
 580 }
 581 
 582 static void save_start_states(struct statement *stmt)
 583 {
 584         struct symbol *param;
 585         char orig[64];
 586         char state_name[128];
 587         struct smatch_state *state;
 588         struct string_list *links;
 589         char *link;
 590 
 591         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
 592                 struct var_sym_list *left_vsl = NULL;
 593                 struct var_sym_list *right_vsl = NULL;
 594 
 595                 if (!param->ident)
 596                         continue;
 597                 snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
 598                 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
 599                 add_var_sym(&left_vsl, param->ident->name, param);
 600                 add_var_sym(&right_vsl, orig, param);
 601                 state = alloc_compare_state(
 602                                 NULL, param->ident->name, left_vsl,
 603                                 SPECIAL_EQUAL,
 604                                 NULL, alloc_sname(orig), right_vsl);
 605                 set_state(compare_id, state_name, NULL, state);
 606 
 607                 link = alloc_sname(state_name);
 608                 links = NULL;
 609                 insert_string(&links, link);
 610                 state = alloc_link_state(links);
 611                 set_state(link_id, param->ident->name, param, state);
 612         } END_FOR_EACH_PTR(param);
 613 }
 614 
 615 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
 616 {
 617         struct smatch_state *ret;
 618         struct string_list *links;
 619 
 620         links = combine_string_lists(s1->data, s2->data);
 621         ret = alloc_link_state(links);
 622         return ret;
 623 }
 624 
 625 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
 626 {
 627         struct smatch_state *old_state, *new_state;
 628         struct string_list *links;
 629         char *new;
 630 
 631         old_state = get_state(link_id, var, sym);
 632         if (old_state)
 633                 links = clone_str_list(old_state->data);
 634         else
 635                 links = NULL;
 636 
 637         new = alloc_sname(link);
 638         insert_string(&links, new);
 639 
 640         new_state = alloc_link_state(links);
 641         set_state(link_id, var, sym, new_state);
 642 }
 643 
 644 static void match_inc(struct sm_state *sm)
 645 {
 646         struct string_list *links;
 647         struct smatch_state *state, *new;
 648         struct compare_data *data;
 649         char *tmp;
 650         int flip;
 651         int op;
 652 
 653         links = sm->state->data;
 654 
 655         FOR_EACH_PTR(links, tmp) {
 656                 state = get_state(compare_id, tmp, NULL);
 657                 if (!state)
 658                         continue;
 659                 data = state->data;
 660                 if (!data)
 661                         continue;
 662 
 663                 flip = 0;
 664                 if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 ||
 665                     tmp[strlen(sm->name)] != ' ')
 666                         flip = 1;
 667 
 668                 op = state_to_comparison(state);
 669 
 670                 switch (flip ? flip_comparison(op) : op) {
 671                 case SPECIAL_EQUAL:
 672                 case SPECIAL_GTE:
 673                 case SPECIAL_UNSIGNED_GTE:
 674                 case '>':
 675                 case SPECIAL_UNSIGNED_GT:
 676                         new = alloc_compare_state(
 677                                         data->left, data->left_var, data->left_vsl,
 678                                         flip ? '<' : '>',
 679                                         data->right, data->right_var, data->right_vsl);
 680                         set_state(compare_id, tmp, NULL, new);
 681                         break;
 682                 case '<':
 683                 case SPECIAL_UNSIGNED_LT:
 684                         new = alloc_compare_state(
 685                                         data->left, data->left_var, data->left_vsl,
 686                                         flip ? SPECIAL_GTE : SPECIAL_LTE,
 687                                         data->right, data->right_var, data->right_vsl);
 688                         set_state(compare_id, tmp, NULL, new);
 689                         break;
 690                 default:
 691                         set_state(compare_id, tmp, NULL, &undefined);
 692                 }
 693         } END_FOR_EACH_PTR(tmp);
 694 }
 695 
 696 static void match_dec(struct sm_state *sm)
 697 {
 698         struct string_list *links;
 699         struct smatch_state *state;
 700         char *tmp;
 701 
 702         links = sm->state->data;
 703 
 704         FOR_EACH_PTR(links, tmp) {
 705                 state = get_state(compare_id, tmp, NULL);
 706 
 707                 switch (state_to_comparison(state)) {
 708                 case SPECIAL_EQUAL:
 709                 case SPECIAL_LTE:
 710                 case SPECIAL_UNSIGNED_LTE:
 711                 case '<':
 712                 case SPECIAL_UNSIGNED_LT: {
 713                         struct compare_data *data = state->data;
 714                         struct smatch_state *new;
 715 
 716                         new = alloc_compare_state(
 717                                         data->left, data->left_var, data->left_vsl,
 718                                         '<',
 719                                         data->right, data->right_var, data->right_vsl);
 720                         set_state(compare_id, tmp, NULL, new);
 721                         break;
 722                         }
 723                 default:
 724                         set_state(compare_id, tmp, NULL, &undefined);
 725                 }
 726         } END_FOR_EACH_PTR(tmp);
 727 }
 728 
 729 static void match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
 730 {
 731         /*
 732          * if (foo > bar) then ++foo is also > bar.
 733          */
 734         if (!mod_expr)
 735                 return;
 736         if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
 737                 return;
 738 
 739         if (mod_expr->op == SPECIAL_INCREMENT)
 740                 match_inc(sm);
 741         else if (mod_expr->op == SPECIAL_DECREMENT)
 742                 match_dec(sm);
 743 }
 744 
 745 static int is_self_assign(struct expression *expr)
 746 {
 747         if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
 748                 return 0;
 749         return expr_equiv(expr->left, expr->right);
 750 }
 751 
 752 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
 753 {
 754         struct string_list *links;
 755         char *tmp;
 756 
 757         if (mod_expr && is_self_assign(mod_expr))
 758                 return;
 759 
 760         /* handled by match_inc_dec() */
 761         if (mod_expr &&
 762             ((mod_expr->type == EXPR_PREOP || mod_expr->type == EXPR_POSTOP) &&
 763              (mod_expr->op == SPECIAL_INCREMENT || mod_expr->op == SPECIAL_DECREMENT)))
 764                 return;
 765 
 766         links = sm->state->data;
 767 
 768         FOR_EACH_PTR(links, tmp) {
 769                 set_state(compare_id, tmp, NULL, &undefined);
 770         } END_FOR_EACH_PTR(tmp);
 771         set_state(link_id, sm->name, sm->sym, &undefined);
 772 }
 773 
 774 static void match_preop(struct expression *expr)
 775 {
 776         struct expression *parent;
 777         struct range_list *left, *right;
 778         int op;
 779 
 780         /*
 781          * This is an important special case.  Say you have:
 782          *
 783          *      if (++j == limit)
 784          *
 785          * Assume that we know the range of limit is higher than the start
 786          * value for "j".  Then the first thing that we process is the ++j.  We
 787          * have not comparison states set up so it doesn't get caught by the
 788          * modification hook.  But it does get caught by smatch_extra which sets
 789          * j to unknown then we parse the "j == limit" and sets false to != but
 790          * really we want false to be <.
 791          *
 792          * So what we do is we set j < limit here, then the match_modify catches
 793          * it and we do a match_inc_dec().
 794          *
 795          */
 796 
 797         if (expr->type != EXPR_PREOP ||
 798             (expr->op != SPECIAL_INCREMENT && expr->op != SPECIAL_DECREMENT))
 799                 return;
 800 
 801         parent = expr_get_parent_expr(expr);
 802         if (!parent)
 803                 return;
 804         if (parent->type != EXPR_COMPARE || parent->op != SPECIAL_EQUAL)
 805                 return;
 806         if (parent->left != expr)
 807                 return;
 808 
 809         if (!get_implied_rl(expr->unop, &left) ||
 810            !get_implied_rl(parent->right, &right))
 811                 return;
 812 
 813         op = rl_comparison(left, right);
 814         if (!op)
 815                 return;
 816 
 817         add_comparison(expr->unop, op, parent->right);
 818 }
 819 
 820 static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym)
 821 {
 822         expr = strip_expr(expr);
 823         if (!expr)
 824                 return NULL;
 825         if (sym)
 826                 *sym = NULL;
 827 
 828         if (expr->type == EXPR_PREOP &&
 829             (expr->op == SPECIAL_INCREMENT ||
 830              expr->op == SPECIAL_DECREMENT))
 831                 expr = strip_expr(expr->unop);
 832 
 833         if (expr->type == EXPR_CALL) {
 834                 char buf[64];
 835 
 836                 snprintf(buf, sizeof(buf), "return %p", expr);
 837                 return alloc_string(buf);
 838         }
 839 
 840         return expr_to_chunk_sym_vsl(expr, sym, NULL);
 841 }
 842 
 843 static char *chunk_to_var(struct expression *expr)
 844 {
 845         return chunk_to_var_sym(expr, NULL);
 846 }
 847 
 848 static struct smatch_state *get_state_chunk(int owner, struct expression *expr)
 849 {
 850         char *name;
 851         struct symbol *sym;
 852         struct smatch_state *ret;
 853 
 854         name = chunk_to_var_sym(expr, &sym);
 855         if (!name)
 856                 return NULL;
 857 
 858         ret = get_state(owner, name, sym);
 859         free_string(name);
 860         return ret;
 861 }
 862 
 863 static void save_link(struct expression *expr, char *link)
 864 {
 865         char *var;
 866         struct symbol *sym;
 867 
 868         expr = strip_expr(expr);
 869         if (expr->type == EXPR_BINOP) {
 870                 char *chunk;
 871 
 872                 chunk = chunk_to_var(expr);
 873                 if (!chunk)
 874                         return;
 875 
 876                 save_link(expr->left, link);
 877                 save_link(expr->right, link);
 878                 save_link_var_sym(chunk, NULL, link);
 879                 return;
 880         }
 881 
 882         var = chunk_to_var_sym(expr, &sym);
 883         if (!var)
 884                 return;
 885 
 886         save_link_var_sym(var, sym, link);
 887         free_string(var);
 888 }
 889 
 890 static int get_orig_comparison(struct stree *pre_stree, const char *left, const char *right)
 891 {
 892         struct smatch_state *state;
 893         struct compare_data *data;
 894         int flip = 0;
 895         char state_name[256];
 896 
 897         if (strcmp(left, right) > 0) {
 898                 const char *tmp = right;
 899 
 900                 flip = 1;
 901                 right = left;
 902                 left = tmp;
 903         }
 904 
 905         snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
 906         state = get_state_stree(pre_stree, compare_id, state_name, NULL);
 907         if (!state || !state->data)
 908                 return 0;
 909         data = state->data;
 910         if (flip)
 911                 return flip_comparison(data->comparison);
 912         return data->comparison;
 913 
 914 }
 915 
 916 static int have_common_var_sym(struct var_sym_list *left_vsl, struct var_sym_list *right_vsl)
 917 {
 918         struct var_sym *tmp;
 919 
 920         FOR_EACH_PTR(left_vsl, tmp) {
 921                 if (in_var_sym_list(right_vsl, tmp->var, tmp->sym))
 922                         return 1;
 923         } END_FOR_EACH_PTR(tmp);
 924 
 925         return 0;
 926 }
 927 
 928 /*
 929  * The idea here is that we take a comparison "a < b" and then we look at all
 930  * the things which "b" is compared against "b < c" and we say that that implies
 931  * a relationship "a < c".
 932  *
 933  * The names here about because the comparisons are organized like this
 934  * "a < b < c".
 935  *
 936  */
 937 static void update_tf_links(struct stree *pre_stree,
 938                             struct expression *left_expr,
 939                             const char *left_var, struct var_sym_list *left_vsl,
 940                             int left_comparison, int left_false_comparison,
 941                             const char *mid_var, struct var_sym_list *mid_vsl,
 942                             struct string_list *links)
 943 {
 944         struct smatch_state *state;
 945         struct smatch_state *true_state, *false_state;
 946         struct compare_data *data;
 947         struct expression *right_expr;
 948         const char *right_var;
 949         struct var_sym_list *right_vsl;
 950         int orig_comparison;
 951         int right_comparison;
 952         int true_comparison;
 953         int false_comparison;
 954         char *tmp;
 955         char state_name[256];
 956         struct var_sym *vs;
 957 
 958         FOR_EACH_PTR(links, tmp) {
 959                 state = get_state_stree(pre_stree, compare_id, tmp, NULL);
 960                 if (!state || !state->data)
 961                         continue;
 962                 data = state->data;
 963                 right_comparison = data->comparison;
 964                 right_expr = data->right;
 965                 right_var = data->right_var;
 966                 right_vsl = data->right_vsl;
 967                 if (strcmp(mid_var, right_var) == 0) {
 968                         right_expr = data->left;
 969                         right_var = data->left_var;
 970                         right_vsl = data->left_vsl;
 971                         right_comparison = flip_comparison(right_comparison);
 972                 }
 973                 if (have_common_var_sym(left_vsl, right_vsl))
 974                         continue;
 975 
 976                 orig_comparison = get_orig_comparison(pre_stree, left_var, right_var);
 977 
 978                 true_comparison = combine_comparisons(left_comparison, right_comparison);
 979                 false_comparison = combine_comparisons(left_false_comparison, right_comparison);
 980 
 981                 true_comparison = filter_comparison(orig_comparison, true_comparison);
 982                 false_comparison = filter_comparison(orig_comparison, false_comparison);
 983 
 984                 if (strcmp(left_var, right_var) > 0) {
 985                         struct expression *tmp_expr = left_expr;
 986                         const char *tmp_var = left_var;
 987                         struct var_sym_list *tmp_vsl = left_vsl;
 988 
 989                         left_expr = right_expr;
 990                         left_var = right_var;
 991                         left_vsl = right_vsl;
 992                         right_expr = tmp_expr;
 993                         right_var = tmp_var;
 994                         right_vsl = tmp_vsl;
 995                         true_comparison = flip_comparison(true_comparison);
 996                         false_comparison = flip_comparison(false_comparison);
 997                 }
 998 
 999                 if (!true_comparison && !false_comparison)
1000                         continue;
1001 
1002                 if (true_comparison)
1003                         true_state = alloc_compare_state(
1004                                         left_expr, left_var, left_vsl,
1005                                         true_comparison,
1006                                         right_expr, right_var, right_vsl);
1007                 else
1008                         true_state = NULL;
1009                 if (false_comparison)
1010                         false_state = alloc_compare_state(
1011                                         left_expr, left_var, left_vsl,
1012                                         false_comparison,
1013                                         right_expr, right_var, right_vsl);
1014                 else
1015                         false_state = NULL;
1016 
1017                 snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
1018                 set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
1019                 FOR_EACH_PTR(left_vsl, vs) {
1020                         save_link_var_sym(vs->var, vs->sym, state_name);
1021                 } END_FOR_EACH_PTR(vs);
1022                 FOR_EACH_PTR(right_vsl, vs) {
1023                         save_link_var_sym(vs->var, vs->sym, state_name);
1024                 } END_FOR_EACH_PTR(vs);
1025                 if (!vsl_to_sym(left_vsl))
1026                         save_link_var_sym(left_var, NULL, state_name);
1027                 if (!vsl_to_sym(right_vsl))
1028                         save_link_var_sym(right_var, NULL, state_name);
1029         } END_FOR_EACH_PTR(tmp);
1030 }
1031 
1032 static void update_tf_data(struct stree *pre_stree,
1033                 struct expression *left_expr,
1034                 const char *left_name, struct var_sym_list *left_vsl,
1035                 struct expression *right_expr,
1036                 const char *right_name, struct var_sym_list *right_vsl,
1037                 int true_comparison, int false_comparison)
1038 {
1039         struct smatch_state *state;
1040 
1041         state = get_state_stree(pre_stree, link_id, right_name, vsl_to_sym(right_vsl));
1042         if (state)
1043                 update_tf_links(pre_stree, left_expr, left_name, left_vsl, true_comparison, false_comparison, right_name, right_vsl, state->data);
1044 
1045         state = get_state_stree(pre_stree, link_id, left_name, vsl_to_sym(left_vsl));
1046         if (state)
1047                 update_tf_links(pre_stree, right_expr, right_name, right_vsl, flip_comparison(true_comparison), flip_comparison(false_comparison), left_name, left_vsl, state->data);
1048 }
1049 
1050 static void iter_modify(struct sm_state *sm, struct expression *mod_expr)
1051 {
1052         if (sm->state != &start ||
1053             !mod_expr ||
1054             (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP) ||
1055             mod_expr->op != SPECIAL_INCREMENT)
1056                 set_state(inc_dec_id, sm->name, sm->sym, &undefined);
1057         else
1058                 set_state(inc_dec_id, sm->name, sm->sym, &incremented);
1059 }
1060 
1061 static void handle_for_loops(struct expression *expr, char *state_name, struct smatch_state *false_state)
1062 {
1063         sval_t sval;
1064         char *iter_name, *cap_name;
1065         struct symbol *iter_sym, *cap_sym;
1066         struct compare_data *data;
1067 
1068         if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
1069                 return;
1070 
1071         if (!__cur_stmt || !__prev_stmt)
1072                 return;
1073         if (__cur_stmt->type != STMT_ITERATOR)
1074                 return;
1075         if (__cur_stmt->iterator_pre_condition != expr)
1076                 return;
1077 
1078         /* literals are handled in smatch_extra.c */
1079         if (get_value(expr->right, &sval))
1080                 return;
1081 
1082         /* First time checking the condition */
1083         if (__prev_stmt == __cur_stmt->iterator_pre_statement) {
1084                 if (!get_implied_value(expr->left, &sval) ||
1085                     sval.value != 0)
1086                         return;
1087 
1088                 iter_name = expr_to_var_sym(expr->left, &iter_sym);
1089                 cap_name = expr_to_var_sym(expr->right, &cap_sym);
1090                 if (!iter_name || !cap_name || !iter_sym || !cap_sym) {
1091                         free_string(iter_name);
1092                         free_string(cap_name);
1093                         return;
1094                 }
1095 
1096                 set_state(inc_dec_id, iter_name, iter_sym, &start);
1097                 store_link(inc_dec_link_id, cap_name, cap_sym, iter_name, iter_sym);
1098 
1099                 free_string(iter_name);
1100                 free_string(cap_name);
1101                 return;
1102         }
1103 
1104         /* Second time checking the condtion */
1105         if (__prev_stmt != __cur_stmt->iterator_post_statement)
1106                 return;
1107 
1108         if (get_state_chunk(inc_dec_id, expr->left) != &incremented)
1109                 return;
1110 
1111         data = false_state->data;
1112         false_state = alloc_compare_state(
1113                         data->left, data->left_var, data->left_vsl,
1114                         SPECIAL_EQUAL,
1115                         data->right, data->right_var, data->right_vsl);
1116 
1117         set_true_false_states(compare_id, state_name, NULL, NULL, false_state);
1118 }
1119 
1120 static int is_plus_one(struct expression *expr)
1121 {
1122         sval_t sval;
1123 
1124         if (expr->type != EXPR_BINOP || expr->op != '+')
1125                 return 0;
1126         if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1127                 return 0;
1128         return 1;
1129 }
1130 
1131 static int is_minus_one(struct expression *expr)
1132 {
1133         sval_t sval;
1134 
1135         if (expr->type != EXPR_BINOP || expr->op != '-')
1136                 return 0;
1137         if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1138                 return 0;
1139         return 1;
1140 }
1141 
1142 static void move_plus_to_minus_helper(struct expression **left_p, struct expression **right_p)
1143 {
1144         struct expression *left = *left_p;
1145         struct expression *right = *right_p;
1146 
1147         /*
1148          * These two are basically equivalent: "foo + 1 != bar" and
1149          * "foo != bar - 1".  There are issues with signedness and integer
1150          * overflows.  There are also issues with type as well.  But let's
1151          * pretend we can ignore all that stuff for now.
1152          *
1153          */
1154 
1155         if (!is_plus_one(left))
1156                 return;
1157 
1158         *left_p = left->left;
1159         *right_p = binop_expression(right, '-', left->right);
1160 }
1161 
1162 static void move_plus_to_minus(struct expression **left_p, struct expression **right_p)
1163 {
1164         if (is_plus_one(*left_p) && is_plus_one(*right_p))
1165                 return;
1166 
1167         move_plus_to_minus_helper(left_p, right_p);
1168         move_plus_to_minus_helper(right_p, left_p);
1169 }
1170 
1171 static void handle_comparison(struct expression *left_expr, int op, struct expression *right_expr, char **_state_name, struct smatch_state **_false_state)
1172 {
1173         char *left = NULL;
1174         char *right = NULL;
1175         struct symbol *left_sym, *right_sym;
1176         struct var_sym_list *left_vsl = NULL;
1177         struct var_sym_list *right_vsl = NULL;
1178         int false_op;
1179         int orig_comparison;
1180         struct smatch_state *true_state, *false_state;
1181         static char state_name[256];
1182         struct stree *pre_stree;
1183         sval_t sval;
1184 
1185         if (!left_expr || !right_expr)
1186                 return;
1187 
1188         left_expr = strip_parens(left_expr);
1189         right_expr = strip_parens(right_expr);
1190 
1191         while (left_expr->type == EXPR_ASSIGNMENT)
1192                 left_expr = strip_parens(left_expr->left);
1193         while (right_expr->type == EXPR_ASSIGNMENT)
1194                 right_expr = strip_parens(right_expr->left);
1195 
1196         false_op = negate_comparison(op);
1197 
1198         move_plus_to_minus(&left_expr, &right_expr);
1199 
1200         if (op == SPECIAL_UNSIGNED_LT &&
1201             get_implied_value(left_expr, &sval) &&
1202             sval.value == 0)
1203                 false_op = SPECIAL_EQUAL;
1204 
1205         if (op == SPECIAL_UNSIGNED_GT &&
1206             get_implied_value(right_expr, &sval) &&
1207             sval.value == 0)
1208                 false_op = SPECIAL_EQUAL;
1209 
1210         left = chunk_to_var_sym(left_expr, &left_sym);
1211         if (!left)
1212                 goto free;
1213         if (left_sym)
1214                 add_var_sym(&left_vsl, left, left_sym);
1215         else
1216                 left_vsl = expr_to_vsl(left_expr);
1217         right = chunk_to_var_sym(right_expr, &right_sym);
1218         if (!right)
1219                 goto free;
1220         if (right_sym)
1221                 add_var_sym(&right_vsl, right, right_sym);
1222         else
1223                 right_vsl = expr_to_vsl(right_expr);
1224 
1225         if (strcmp(left, right) > 0) {
1226                 char *tmp_name = left;
1227                 struct var_sym_list *tmp_vsl = left_vsl;
1228                 struct expression *tmp_expr = left_expr;
1229 
1230                 left = right;
1231                 left_vsl = right_vsl;
1232                 left_expr = right_expr;
1233                 right = tmp_name;
1234                 right_vsl = tmp_vsl;
1235                 right_expr = tmp_expr;
1236                 op = flip_comparison(op);
1237                 false_op = flip_comparison(false_op);
1238         }
1239 
1240         orig_comparison = get_comparison(left_expr, right_expr);
1241         op = filter_comparison(orig_comparison, op);
1242         false_op = filter_comparison(orig_comparison, false_op);
1243 
1244         snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
1245         true_state = alloc_compare_state(
1246                         left_expr, left, left_vsl,
1247                         op,
1248                         right_expr, right, right_vsl);
1249         false_state = alloc_compare_state(
1250                         left_expr, left, left_vsl,
1251                         false_op,
1252                         right_expr, right, right_vsl);
1253 
1254         pre_stree = clone_stree(__get_cur_stree());
1255         update_tf_data(pre_stree, left_expr, left, left_vsl, right_expr, right, right_vsl, op, false_op);
1256         free_stree(&pre_stree);
1257 
1258         set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
1259         __compare_param_limit_hook(left_expr, right_expr, state_name, true_state, false_state);
1260         save_link(left_expr, state_name);
1261         save_link(right_expr, state_name);
1262 
1263         if (_false_state)
1264                 *_false_state = false_state;
1265         if (_state_name)
1266                 *_state_name = state_name;
1267 free:
1268         free_string(left);
1269         free_string(right);
1270 }
1271 
1272 void __comparison_match_condition(struct expression *expr)
1273 {
1274         struct expression *left, *right, *new_left, *new_right, *tmp;
1275         struct smatch_state *false_state = NULL;
1276         char *state_name = NULL;
1277         int redo, count;
1278 
1279         if (expr->type != EXPR_COMPARE)
1280                 return;
1281 
1282         handle_comparison(expr->left, expr->op, expr->right, &state_name, &false_state);
1283         if (false_state && state_name)
1284                 handle_for_loops(expr, state_name, false_state);
1285 
1286         left = strip_parens(expr->left);
1287         right = strip_parens(expr->right);
1288 
1289         if (left->type == EXPR_BINOP && left->op == '+') {
1290                 new_left = left->left;
1291                 new_right = binop_expression(right, '-', left->right);
1292                 handle_comparison(new_left, expr->op, new_right, NULL, NULL);
1293 
1294                 new_left = left->right;
1295                 new_right = binop_expression(right, '-', left->left);
1296                 handle_comparison(new_left, expr->op, new_right, NULL, NULL);
1297         }
1298 
1299 
1300         redo = 0;
1301         left = strip_parens(expr->left);
1302         right = strip_parens(expr->right);
1303         if (get_last_expr_from_expression_stmt(expr->left)) {
1304                 left = get_last_expr_from_expression_stmt(expr->left);
1305                 redo = 1;
1306         }
1307         if (get_last_expr_from_expression_stmt(expr->right)) {
1308                 right = get_last_expr_from_expression_stmt(expr->right);
1309                 redo = 1;
1310         }
1311 
1312         if (!redo)
1313                 return;
1314 
1315         count = 0;
1316         while ((tmp = get_assigned_expr(left))) {
1317                 if (count++ > 3)
1318                         break;
1319                 left = strip_expr(tmp);
1320         }
1321         count = 0;
1322         while ((tmp = get_assigned_expr(right))) {
1323                 if (count++ > 3)
1324                         break;
1325                 right = strip_expr(tmp);
1326         }
1327 
1328         handle_comparison(left, expr->op, right, NULL, NULL);
1329 }
1330 
1331 static void add_comparison_var_sym(
1332                 struct expression *left_expr,
1333                 const char *left_name, struct var_sym_list *left_vsl,
1334                 int comparison,
1335                 struct expression *right_expr,
1336                 const char *right_name, struct var_sym_list *right_vsl)
1337 {
1338         struct smatch_state *state;
1339         struct var_sym *vs;
1340         char state_name[256];
1341 
1342         if (strcmp(left_name, right_name) > 0) {
1343                 struct expression *tmp_expr = left_expr;
1344                 const char *tmp_name = left_name;
1345                 struct var_sym_list *tmp_vsl = left_vsl;
1346 
1347                 left_expr = right_expr;
1348                 left_name = right_name;
1349                 left_vsl = right_vsl;
1350                 right_expr = tmp_expr;
1351                 right_name = tmp_name;
1352                 right_vsl = tmp_vsl;
1353                 comparison = flip_comparison(comparison);
1354         }
1355         snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1356         state = alloc_compare_state(
1357                         left_expr, left_name, left_vsl,
1358                         comparison,
1359                         right_expr, right_name, right_vsl);
1360 
1361         set_state(compare_id, state_name, NULL, state);
1362 
1363         FOR_EACH_PTR(left_vsl, vs) {
1364                 save_link_var_sym(vs->var, vs->sym, state_name);
1365         } END_FOR_EACH_PTR(vs);
1366         FOR_EACH_PTR(right_vsl, vs) {
1367                 save_link_var_sym(vs->var, vs->sym, state_name);
1368         } END_FOR_EACH_PTR(vs);
1369 }
1370 
1371 static void add_comparison(struct expression *left, int comparison, struct expression *right)
1372 {
1373         char *left_name = NULL;
1374         char *right_name = NULL;
1375         struct symbol *left_sym, *right_sym;
1376         struct var_sym_list *left_vsl, *right_vsl;
1377         struct smatch_state *state;
1378         char state_name[256];
1379 
1380         left_name = chunk_to_var_sym(left, &left_sym);
1381         if (!left_name)
1382                 goto free;
1383         left_vsl = expr_to_vsl(left);
1384         right_name = chunk_to_var_sym(right, &right_sym);
1385         if (!right_name)
1386                 goto free;
1387         right_vsl = expr_to_vsl(right);
1388 
1389         if (strcmp(left_name, right_name) > 0) {
1390                 struct expression *tmp_expr = left;
1391                 struct symbol *tmp_sym = left_sym;
1392                 char *tmp_name = left_name;
1393                 struct var_sym_list *tmp_vsl = left_vsl;
1394 
1395                 left = right;
1396                 left_name = right_name;
1397                 left_sym = right_sym;
1398                 left_vsl = right_vsl;
1399                 right = tmp_expr;
1400                 right_name = tmp_name;
1401                 right_sym = tmp_sym;
1402                 right_vsl = tmp_vsl;
1403                 comparison = flip_comparison(comparison);
1404         }
1405         snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1406         state = alloc_compare_state(
1407                         left, left_name, left_vsl,
1408                         comparison,
1409                         right, right_name, right_vsl);
1410 
1411         set_state(compare_id, state_name, NULL, state);
1412         save_link(left, state_name);
1413         save_link(right, state_name);
1414 
1415 free:
1416         free_string(left_name);
1417         free_string(right_name);
1418 }
1419 
1420 static void match_assign_add(struct expression *expr)
1421 {
1422         struct expression *right;
1423         struct expression *r_left, *r_right;
1424         sval_t left_tmp, right_tmp;
1425 
1426         right = strip_expr(expr->right);
1427         r_left = strip_expr(right->left);
1428         r_right = strip_expr(right->right);
1429 
1430         get_absolute_min(r_left, &left_tmp);
1431         get_absolute_min(r_right, &right_tmp);
1432 
1433         if (left_tmp.value > 0)
1434                 add_comparison(expr->left, '>', r_right);
1435         else if (left_tmp.value == 0)
1436                 add_comparison(expr->left, SPECIAL_GTE, r_right);
1437 
1438         if (right_tmp.value > 0)
1439                 add_comparison(expr->left, '>', r_left);
1440         else if (right_tmp.value == 0)
1441                 add_comparison(expr->left, SPECIAL_GTE, r_left);
1442 }
1443 
1444 static void match_assign_sub(struct expression *expr)
1445 {
1446         struct expression *right;
1447         struct expression *r_left, *r_right;
1448         int comparison;
1449         sval_t min;
1450 
1451         right = strip_expr(expr->right);
1452         r_left = strip_expr(right->left);
1453         r_right = strip_expr(right->right);
1454 
1455         if (get_absolute_min(r_right, &min) && sval_is_negative(min))
1456                 return;
1457 
1458         comparison = get_comparison(r_left, r_right);
1459 
1460         switch (comparison) {
1461         case '>':
1462         case SPECIAL_GTE:
1463                 if (implied_not_equal(r_right, 0))
1464                         add_comparison(expr->left, '>', r_left);
1465                 else
1466                         add_comparison(expr->left, SPECIAL_GTE, r_left);
1467                 return;
1468         }
1469 }
1470 
1471 static void match_assign_divide(struct expression *expr)
1472 {
1473         struct expression *right;
1474         struct expression *r_left, *r_right;
1475         sval_t min;
1476 
1477         right = strip_expr(expr->right);
1478         r_left = strip_expr(right->left);
1479         r_right = strip_expr(right->right);
1480         if (!get_implied_min(r_right, &min) || min.value <= 1)
1481                 return;
1482 
1483         add_comparison(expr->left, '<', r_left);
1484 }
1485 
1486 static void match_binop_assign(struct expression *expr)
1487 {
1488         struct expression *right;
1489 
1490         right = strip_expr(expr->right);
1491         if (right->op == '+')
1492                 match_assign_add(expr);
1493         if (right->op == '-')
1494                 match_assign_sub(expr);
1495         if (right->op == '/')
1496                 match_assign_divide(expr);
1497 }
1498 
1499 static void copy_comparisons(struct expression *left, struct expression *right)
1500 {
1501         struct string_list *links;
1502         struct smatch_state *state;
1503         struct compare_data *data;
1504         struct symbol *left_sym, *right_sym;
1505         char *left_var = NULL;
1506         char *right_var = NULL;
1507         struct var_sym_list *left_vsl;
1508         struct expression *expr;
1509         const char *var;
1510         struct var_sym_list *vsl;
1511         int comparison;
1512         char *tmp;
1513 
1514         left_var = chunk_to_var_sym(left, &left_sym);
1515         if (!left_var)
1516                 goto done;
1517         left_vsl = expr_to_vsl(left);
1518         right_var = chunk_to_var_sym(right, &right_sym);
1519         if (!right_var)
1520                 goto done;
1521 
1522         state = get_state(link_id, right_var, right_sym);
1523         if (!state)
1524                 return;
1525         links = state->data;
1526 
1527         FOR_EACH_PTR(links, tmp) {
1528                 state = get_state(compare_id, tmp, NULL);
1529                 if (!state || !state->data)
1530                         continue;
1531                 data = state->data;
1532                 comparison = data->comparison;
1533                 expr = data->right;
1534                 var = data->right_var;
1535                 vsl = data->right_vsl;
1536                 if (strcmp(var, right_var) == 0) {
1537                         expr = data->left;
1538                         var = data->left_var;
1539                         vsl = data->left_vsl;
1540                         comparison = flip_comparison(comparison);
1541                 }
1542                 /* n = copy_from_user(dest, src, n); leads to n <= n which is nonsense */
1543                 if (strcmp(left_var, var) == 0)
1544                         continue;
1545                 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1546         } END_FOR_EACH_PTR(tmp);
1547 
1548 done:
1549         free_string(right_var);
1550 }
1551 
1552 static void match_assign(struct expression *expr)
1553 {
1554         struct expression *right;
1555 
1556         if (expr->op != '=')
1557                 return;
1558         if (__in_fake_assign || outside_of_function())
1559                 return;
1560 
1561         if (is_struct(expr->left))
1562                 return;
1563 
1564         if (is_self_assign(expr))
1565                 return;
1566 
1567         copy_comparisons(expr->left, expr->right);
1568         add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
1569 
1570         right = strip_expr(expr->right);
1571         if (right->type == EXPR_BINOP)
1572                 match_binop_assign(expr);
1573 }
1574 
1575 int get_comparison_strings(const char *one, const char *two)
1576 {
1577         char buf[256];
1578         struct smatch_state *state;
1579         int invert = 0;
1580         int ret = 0;
1581 
1582         if (!one || !two)
1583                 return 0;
1584 
1585         if (strcmp(one, two) == 0)
1586                 return SPECIAL_EQUAL;
1587 
1588         if (strcmp(one, two) > 0) {
1589                 const char *tmp = one;
1590 
1591                 one = two;
1592                 two = tmp;
1593                 invert = 1;
1594         }
1595 
1596         snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1597         state = get_state(compare_id, buf, NULL);
1598         if (state)
1599                 ret = state_to_comparison(state);
1600 
1601         if (invert)
1602                 ret = flip_comparison(ret);
1603 
1604         return ret;
1605 }
1606 
1607 int get_comparison(struct expression *a, struct expression *b)
1608 {
1609         char *one = NULL;
1610         char *two = NULL;
1611         int ret = 0;
1612 
1613         if (!a || !b)
1614                 return 0;
1615 
1616         a = strip_parens(a);
1617         b = strip_parens(b);
1618 
1619         move_plus_to_minus(&a, &b);
1620 
1621         one = chunk_to_var(a);
1622         if (!one)
1623                 goto free;
1624         two = chunk_to_var(b);
1625         if (!two)
1626                 goto free;
1627 
1628         ret = get_comparison_strings(one, two);
1629         if (ret)
1630                 goto free;
1631 
1632         if (is_plus_one(a) || is_minus_one(a)) {
1633                 free_string(one);
1634                 one = chunk_to_var(a->left);
1635                 ret = get_comparison_strings(one, two);
1636         } else if (is_plus_one(b) || is_minus_one(b)) {
1637                 free_string(two);
1638                 two = chunk_to_var(b->left);
1639                 ret = get_comparison_strings(one, two);
1640         }
1641 
1642         if (!ret)
1643                 goto free;
1644 
1645         if ((is_plus_one(a) || is_minus_one(b)) && ret == '<')
1646                 ret = SPECIAL_LTE;
1647         else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>')
1648                 ret = SPECIAL_GTE;
1649         else
1650                 ret = 0;
1651 
1652 free:
1653         free_string(one);
1654         free_string(two);
1655 
1656         if (!ret)
1657                 return comparison_from_extra(a, b);
1658         return ret;
1659 }
1660 
1661 int possible_comparison(struct expression *a, int comparison, struct expression *b)
1662 {
1663         char *one = NULL;
1664         char *two = NULL;
1665         int ret = 0;
1666         char buf[256];
1667         struct sm_state *sm;
1668         int saved;
1669 
1670         one = chunk_to_var(a);
1671         if (!one)
1672                 goto free;
1673         two = chunk_to_var(b);
1674         if (!two)
1675                 goto free;
1676 
1677 
1678         if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1679                 ret = 1;
1680                 goto free;
1681         }
1682 
1683         if (strcmp(one, two) > 0) {
1684                 char *tmp = one;
1685 
1686                 one = two;
1687                 two = tmp;
1688                 comparison = flip_comparison(comparison);
1689         }
1690 
1691         snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1692         sm = get_sm_state(compare_id, buf, NULL);
1693         if (!sm)
1694                 goto free;
1695 
1696         FOR_EACH_PTR(sm->possible, sm) {
1697                 if (!sm->state->data)
1698                         continue;
1699                 saved = ((struct compare_data *)sm->state->data)->comparison;
1700                 if (saved == comparison)
1701                         ret = 1;
1702                 if (comparison == SPECIAL_EQUAL &&
1703                     (saved == SPECIAL_LTE ||
1704                      saved == SPECIAL_GTE ||
1705                      saved == SPECIAL_UNSIGNED_LTE ||
1706                      saved == SPECIAL_UNSIGNED_GTE))
1707                         ret = 1;
1708                 if (ret == 1)
1709                         goto free;
1710         } END_FOR_EACH_PTR(sm);
1711 
1712         return ret;
1713 free:
1714         free_string(one);
1715         free_string(two);
1716         return ret;
1717 }
1718 
1719 struct state_list *get_all_comparisons(struct expression *expr)
1720 {
1721         struct smatch_state *state;
1722         struct string_list *links;
1723         struct state_list *ret = NULL;
1724         struct sm_state *sm;
1725         char *tmp;
1726 
1727         state = get_state_chunk(link_id, expr);
1728         if (!state)
1729                 return NULL;
1730         links = state->data;
1731 
1732         FOR_EACH_PTR(links, tmp) {
1733                 sm = get_sm_state(compare_id, tmp, NULL);
1734                 if (!sm)
1735                         continue;
1736                 // FIXME have to compare name with vsl
1737                 add_ptr_list(&ret, sm);
1738         } END_FOR_EACH_PTR(tmp);
1739 
1740         return ret;
1741 }
1742 
1743 struct state_list *get_all_possible_equal_comparisons(struct expression *expr)
1744 {
1745         struct smatch_state *state;
1746         struct string_list *links;
1747         struct state_list *ret = NULL;
1748         struct sm_state *sm;
1749         char *tmp;
1750 
1751         state = get_state_chunk(link_id, expr);
1752         if (!state)
1753                 return NULL;
1754         links = state->data;
1755 
1756         FOR_EACH_PTR(links, tmp) {
1757                 sm = get_sm_state(compare_id, tmp, NULL);
1758                 if (!sm)
1759                         continue;
1760                 if (!strchr(sm->state->name, '='))
1761                         continue;
1762                 if (strcmp(sm->state->name, "!=") == 0)
1763                         continue;
1764                 add_ptr_list(&ret, sm);
1765         } END_FOR_EACH_PTR(tmp);
1766 
1767         return ret;
1768 }
1769 
1770 struct state_list *get_all_possible_not_equal_comparisons(struct expression *expr)
1771 {
1772         struct smatch_state *state;
1773         struct string_list *links;
1774         struct state_list *ret = NULL;
1775         struct sm_state *sm;
1776         struct sm_state *possible;
1777         char *link;
1778 
1779         return NULL;
1780 
1781         state = get_state_chunk(link_id, expr);
1782         if (!state)
1783                 return NULL;
1784         links = state->data;
1785 
1786         FOR_EACH_PTR(links, link) {
1787                 sm = get_sm_state(compare_id, link, NULL);
1788                 if (!sm)
1789                         continue;
1790                 FOR_EACH_PTR(sm->possible, possible) {
1791                         if (strcmp(possible->state->name, "!=") != 0)
1792                                 continue;
1793                         add_ptr_list(&ret, sm);
1794                         break;
1795                 } END_FOR_EACH_PTR(link);
1796         } END_FOR_EACH_PTR(link);
1797 
1798         return ret;
1799 }
1800 
1801 static void update_links_from_call(struct expression *left,
1802                                    int left_compare,
1803                                    struct expression *right)
1804 {
1805         struct string_list *links;
1806         struct smatch_state *state;
1807         struct compare_data *data;
1808         struct symbol *left_sym, *right_sym;
1809         char *left_var = NULL;
1810         char *right_var = NULL;
1811         struct var_sym_list *left_vsl;
1812         struct expression *expr;
1813         const char *var;
1814         struct var_sym_list *vsl;
1815         int comparison;
1816         char *tmp;
1817 
1818         left_var = chunk_to_var_sym(left, &left_sym);
1819         if (!left_var)
1820                 goto done;
1821         left_vsl = expr_to_vsl(left);
1822         right_var = chunk_to_var_sym(right, &right_sym);
1823         if (!right_var)
1824                 goto done;
1825 
1826         state = get_state(link_id, right_var, right_sym);
1827         if (!state)
1828                 return;
1829         links = state->data;
1830 
1831         FOR_EACH_PTR(links, tmp) {
1832                 state = get_state(compare_id, tmp, NULL);
1833                 if (!state || !state->data)
1834                         continue;
1835                 data = state->data;
1836                 comparison = data->comparison;
1837                 expr = data->right;
1838                 var = data->right_var;
1839                 vsl = data->right_vsl;
1840                 if (strcmp(var, right_var) == 0) {
1841                         expr = data->left;
1842                         var = data->left_var;
1843                         vsl = data->left_vsl;
1844                         comparison = flip_comparison(comparison);
1845                 }
1846                 comparison = combine_comparisons(left_compare, comparison);
1847                 if (!comparison)
1848                         continue;
1849                 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1850         } END_FOR_EACH_PTR(tmp);
1851 
1852 done:
1853         free_string(right_var);
1854 }
1855 
1856 void __add_return_comparison(struct expression *call, const char *range)
1857 {
1858         struct expression *arg;
1859         int comparison;
1860         char buf[4];
1861 
1862         if (!str_to_comparison_arg(range, call, &comparison, &arg))
1863                 return;
1864         snprintf(buf, sizeof(buf), "%s", show_special(comparison));
1865         update_links_from_call(call, comparison, arg);
1866         add_comparison(call, comparison, arg);
1867 }
1868 
1869 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
1870 {
1871         copy_comparisons(expr, call);
1872 }
1873 
1874 static char *get_mask_comparison(struct expression *expr, int ignore)
1875 {
1876         struct expression *tmp, *right;
1877         int count, param;
1878         char buf[256];
1879 
1880         /* The return value for "return foo & param;" is <= param */
1881 
1882         count = 0;
1883         while ((tmp = get_assigned_expr(expr))) {
1884                 expr = strip_expr(tmp);
1885                 if (count++ > 4)
1886                         break;
1887         }
1888 
1889         if (expr->type != EXPR_BINOP || expr->op != '&')
1890                 return NULL;
1891 
1892         right = strip_expr(expr->right);
1893         param = get_param_num(right);
1894         if (param < 0 || param == ignore)
1895                 return NULL;
1896 
1897         snprintf(buf, sizeof(buf), "[<=$%d]", param);
1898         return alloc_sname(buf);
1899 }
1900 
1901 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with, int ignore)
1902 {
1903         struct symbol *param;
1904         char *var = NULL;
1905         char buf[256];
1906         char *ret_str = NULL;
1907         int compare;
1908         int i;
1909 
1910         if (!expr)
1911                 return NULL;
1912 
1913         var = chunk_to_var(expr);
1914         if (!var)
1915                 goto try_mask;
1916 
1917         i = -1;
1918         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1919                 i++;
1920                 if (i == ignore)
1921                         continue;
1922                 if (!param->ident)
1923                         continue;
1924                 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1925                 compare = get_comparison_strings(var, buf);
1926                 if (!compare)
1927                         continue;
1928                 if (show_special(compare)[0] != starts_with)
1929                         continue;
1930                 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1931                 ret_str = alloc_sname(buf);
1932                 break;
1933         } END_FOR_EACH_PTR(param);
1934 
1935         free_string(var);
1936         if (!ret_str)
1937                 goto try_mask;
1938 
1939         return ret_str;
1940 
1941 try_mask:
1942         if (starts_with == '<')
1943                 ret_str = get_mask_comparison(expr, ignore);
1944         return ret_str;
1945 }
1946 
1947 char *name_sym_to_param_comparison(const char *name, struct symbol *sym)
1948 {
1949         struct symbol *param;
1950         char buf[256];
1951         int compare;
1952         int i;
1953 
1954         i = -1;
1955         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1956                 i++;
1957                 if (!param->ident)
1958                         continue;
1959                 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1960                 compare = get_comparison_strings(name, buf);
1961                 if (!compare)
1962                         continue;
1963                 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1964                 return alloc_sname(buf);
1965         } END_FOR_EACH_PTR(param);
1966 
1967         return NULL;
1968 }
1969 
1970 char *expr_equal_to_param(struct expression *expr, int ignore)
1971 {
1972         return range_comparison_to_param_helper(expr, '=', ignore);
1973 }
1974 
1975 char *expr_lte_to_param(struct expression *expr, int ignore)
1976 {
1977         return range_comparison_to_param_helper(expr, '<', ignore);
1978 }
1979 
1980 char *expr_param_comparison(struct expression *expr, int ignore)
1981 {
1982         struct symbol *param;
1983         char *var = NULL;
1984         char buf[256];
1985         char *ret_str = NULL;
1986         int compare;
1987         int i;
1988 
1989         var = chunk_to_var(expr);
1990         if (!var)
1991                 goto free;
1992 
1993         i = -1;
1994         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1995                 i++;
1996                 if (i == ignore)
1997                         continue;
1998                 if (!param->ident)
1999                         continue;
2000                 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
2001                 compare = get_comparison_strings(var, buf);
2002                 if (!compare)
2003                         continue;
2004                 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
2005                 ret_str = alloc_sname(buf);
2006                 break;
2007         } END_FOR_EACH_PTR(param);
2008 
2009 free:
2010         free_string(var);
2011         return ret_str;
2012 }
2013 
2014 char *get_printed_param_name(struct expression *call, const char *param_name, struct symbol *param_sym)
2015 {
2016         struct expression *arg;
2017         char *name;
2018         struct symbol *sym;
2019         static char buf[256];
2020         int len;
2021         int i;
2022 
2023         i = -1;
2024         FOR_EACH_PTR(call->args, arg) {
2025                 i++;
2026 
2027                 name = expr_to_var_sym(arg, &sym);
2028                 if (!name || !sym)
2029                         continue;
2030                 if (sym != param_sym)
2031                         continue;
2032 
2033                 len = strlen(name);
2034                 if (strncmp(name, param_name, len) != 0)
2035                         continue;
2036                 if (param_name[len] == '\0') {
2037                         snprintf(buf, sizeof(buf), "$%d", i);
2038                         return buf;
2039                 }
2040                 if (param_name[len] != '-')
2041                         continue;
2042                 snprintf(buf, sizeof(buf), "$%d%s", i, param_name + len);
2043                 return buf;
2044         } END_FOR_EACH_PTR(arg);
2045 
2046         return NULL;
2047 }
2048 
2049 static void match_call_info(struct expression *expr)
2050 {
2051         struct expression *arg;
2052         struct smatch_state *state;
2053         struct sm_state *sm;
2054         struct compare_data *data;
2055         int comparison;
2056         struct string_list *links;
2057         char *arg_name;
2058         const char *right_name;
2059         char *link;
2060         char info_buf[256];
2061         int i;
2062 
2063         i = -1;
2064         FOR_EACH_PTR(expr->args, arg) {
2065                 i++;
2066 
2067                 state = get_state_chunk(link_id, arg);
2068                 if (!state)
2069                         continue;
2070 
2071                 links = state->data;
2072                 FOR_EACH_PTR(links, link) {
2073                         struct var_sym_list *right_vsl;
2074                         struct var_sym *right_vs;
2075 
2076 
2077                         if (strstr(link, " orig"))
2078                                 continue;
2079                         sm = get_sm_state(compare_id, link, NULL);
2080                         if (!sm)
2081                                 continue;
2082                         data = sm->state->data;
2083                         if (!data || !data->comparison)
2084                                 continue;
2085                         arg_name = expr_to_var(arg);
2086                         if (!arg_name)
2087                                 continue;
2088 
2089                         right_vsl = NULL;
2090                         if (strcmp(data->left_var, arg_name) == 0) {
2091                                 comparison = data->comparison;
2092                                 right_name = data->right_var;
2093                                 right_vsl = data->right_vsl;
2094                         } else if (strcmp(data->right_var, arg_name) == 0) {
2095                                 comparison = flip_comparison(data->comparison);
2096                                 right_name = data->left_var;
2097                                 right_vsl = data->left_vsl;
2098                         }
2099                         if (!right_vsl || ptr_list_size((struct ptr_list *)right_vsl) != 1)
2100                                 goto free;
2101 
2102                         right_vs = first_ptr_list((struct ptr_list *)right_vsl);
2103                         if (strcmp(right_vs->var, right_name) != 0)
2104                                 goto free;
2105                         right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym);
2106                         if (!right_name)
2107                                 goto free;
2108                         snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(comparison), right_name);
2109                         sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf);
2110 
2111 free:
2112                         free_string(arg_name);
2113                 } END_FOR_EACH_PTR(link);
2114         } END_FOR_EACH_PTR(arg);
2115 }
2116 
2117 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm)
2118 {
2119         struct sm_state *compare_sm;
2120         struct string_list *links;
2121         char *link;
2122         struct compare_data *data;
2123         struct var_sym *left, *right;
2124         static char info_buf[256];
2125         const char *right_name;
2126 
2127         if (strstr(printed_name, " orig"))
2128                 return;
2129 
2130         links = link_sm->state->data;
2131         FOR_EACH_PTR(links, link) {
2132                 compare_sm = get_sm_state(compare_id, link, NULL);
2133                 if (!compare_sm)
2134                         continue;
2135                 data = compare_sm->state->data;
2136                 if (!data || !data->comparison)
2137                         continue;
2138 
2139                 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2140                     ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2141                         continue;
2142                 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2143                 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2144                 if (left->sym == right->sym &&
2145                     strcmp(left->var, right->var) == 0)
2146                         continue;
2147                 /*
2148                  * Both parameters link to this comparison so only
2149                  * record the first one.
2150                  */
2151                 if (left->sym != link_sm->sym ||
2152                     strcmp(left->var, link_sm->name) != 0)
2153                         continue;
2154 
2155                 right_name = get_printed_param_name(call, right->var, right->sym);
2156                 if (!right_name)
2157                         continue;
2158                 snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_name);
2159                 sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf);
2160         } END_FOR_EACH_PTR(link);
2161 }
2162 
2163 static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr)
2164 {
2165         char *name;
2166         const char *tmp_name;
2167         struct symbol *sym;
2168         int param;
2169         char info_buf[256];
2170 
2171         /*
2172          * TODO: This only prints == comparisons. That's probably the most
2173          * useful comparison because == max has lots of implications.  But it
2174          * would be good to capture the rest as well.
2175          *
2176          * This information is already in the DB but it's in the parameter math
2177          * bits and it's awkward to use it.  This is is the simpler, possibly
2178          * cleaner way, but not necessarily the best, I don't know.
2179          */
2180 
2181         if (!expr)
2182                 return;
2183         name = expr_to_var_sym(expr, &sym);
2184         if (!name || !sym)
2185                 goto free;
2186 
2187         param = get_param_num_from_sym(sym);
2188         if (param < 0)
2189                 goto free;
2190         if (param_was_set_var_sym(name, sym))
2191                 goto free;
2192 
2193         tmp_name = get_param_name_var_sym(name, sym);
2194         if (!tmp_name)
2195                 goto free;
2196 
2197         snprintf(info_buf, sizeof(info_buf), "== $%d%s", param, tmp_name + 1);
2198         sql_insert_return_states(return_id, return_ranges,
2199                                 PARAM_COMPARE, -1, "$", info_buf);
2200 free:
2201         free_string(name);
2202 }
2203 
2204 static void print_return_comparison(int return_id, char *return_ranges, struct expression *expr)
2205 {
2206         struct sm_state *tmp;
2207         struct string_list *links;
2208         char *link;
2209         struct sm_state *sm;
2210         struct compare_data *data;
2211         struct var_sym *left, *right;
2212         int left_param, right_param;
2213         char left_buf[256];
2214         char right_buf[256];
2215         char info_buf[258];
2216         const char *tmp_name;
2217 
2218         print_return_value_comparison(return_id, return_ranges, expr);
2219 
2220         FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) {
2221                 if (get_param_num_from_sym(tmp->sym) < 0)
2222                         continue;
2223                 links = tmp->state->data;
2224                 FOR_EACH_PTR(links, link) {
2225                         sm = get_sm_state(compare_id, link, NULL);
2226                         if (!sm)
2227                                 continue;
2228                         data = sm->state->data;
2229                         if (!data || !data->comparison)
2230                                 continue;
2231                         if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2232                             ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2233                                 continue;
2234                         left = first_ptr_list((struct ptr_list *)data->left_vsl);
2235                         right = first_ptr_list((struct ptr_list *)data->right_vsl);
2236                         if (left->sym == right->sym &&
2237                             strcmp(left->var, right->var) == 0)
2238                                 continue;
2239                         /*
2240                          * Both parameters link to this comparison so only
2241                          * record the first one.
2242                          */
2243                         if (left->sym != tmp->sym ||
2244                             strcmp(left->var, tmp->name) != 0)
2245                                 continue;
2246 
2247                         if (strstr(right->var, " orig"))
2248                                 continue;
2249 
2250                         left_param = get_param_num_from_sym(left->sym);
2251                         right_param = get_param_num_from_sym(right->sym);
2252                         if (left_param < 0 || right_param < 0)
2253                                 continue;
2254 
2255                         tmp_name = get_param_name_var_sym(left->var, left->sym);
2256                         if (!tmp_name)
2257                                 continue;
2258                         snprintf(left_buf, sizeof(left_buf), "%s", tmp_name);
2259 
2260                         tmp_name = get_param_name_var_sym(right->var, right->sym);
2261                         if (!tmp_name || tmp_name[0] != '$')
2262                                 continue;
2263                         snprintf(right_buf, sizeof(right_buf), "$%d%s", right_param, tmp_name + 1);
2264 
2265                         /*
2266                          * FIXME: this should reject $ type variables (as
2267                          * opposed to $->foo type).  Those should come from
2268                          * smatch_param_compare_limit.c.
2269                          */
2270 
2271                         snprintf(info_buf, sizeof(info_buf), "%s %s", show_special(data->comparison), right_buf);
2272                         sql_insert_return_states(return_id, return_ranges,
2273                                         PARAM_COMPARE, left_param, left_buf, info_buf);
2274                 } END_FOR_EACH_PTR(link);
2275 
2276         } END_FOR_EACH_SM(tmp);
2277 }
2278 
2279 static int parse_comparison(char **value, int *op)
2280 {
2281 
2282         *op = **value;
2283 
2284         switch (*op) {
2285         case '<':
2286                 (*value)++;
2287                 if (**value == '=') {
2288                         (*value)++;
2289                         *op = SPECIAL_LTE;
2290                 }
2291                 break;
2292         case '=':
2293                 (*value)++;
2294                 (*value)++;
2295                 *op = SPECIAL_EQUAL;
2296                 break;
2297         case '!':
2298                 (*value)++;
2299                 (*value)++;
2300                 *op = SPECIAL_NOTEQUAL;
2301                 break;
2302         case '>':
2303                 (*value)++;
2304                 if (**value == '=') {
2305                         (*value)++;
2306                         *op = SPECIAL_GTE;
2307                 }
2308                 break;
2309         default:
2310                 return 0;
2311         }
2312 
2313         if (**value != ' ') {
2314                 sm_perror("parsing comparison.  %s", *value);
2315                 return 0;
2316         }
2317 
2318         (*value)++;
2319         return 1;
2320 }
2321 
2322 static int split_op_param_key(char *value, int *op, int *param, char **key)
2323 {
2324         static char buf[256];
2325         char *p;
2326 
2327         if (!parse_comparison(&value, op))
2328                 return 0;
2329 
2330         snprintf(buf, sizeof(buf), value);
2331 
2332         p = buf;
2333         if (*p++ != '$')
2334                 return 0;
2335 
2336         *param = atoi(p);
2337         if (*param < 0 || *param > 99)
2338                 return 0;
2339         p++;
2340         if (*param > 9)
2341                 p++;
2342         p--;
2343         *p = '$';
2344         *key = p;
2345 
2346         return 1;
2347 }
2348 
2349 static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value)
2350 {
2351         struct expression *left_arg, *right_arg;
2352         char *left_name = NULL;
2353         struct symbol *left_sym;
2354         char *right_name = NULL;
2355         struct symbol *right_sym;
2356         int op;
2357         int right_param;
2358         char *right_key;
2359         struct var_sym_list *left_vsl = NULL, *right_vsl = NULL;
2360 
2361         if (left_param == -1) {
2362                 if (expr->type != EXPR_ASSIGNMENT)
2363                         return;
2364                 left_arg = strip_expr(expr->left);
2365 
2366                 while (expr->type == EXPR_ASSIGNMENT)
2367                         expr = strip_expr(expr->right);
2368                 if (expr->type != EXPR_CALL)
2369                         return;
2370         } else {
2371                 while (expr->type == EXPR_ASSIGNMENT)
2372                         expr = strip_expr(expr->right);
2373                 if (expr->type != EXPR_CALL)
2374                         return;
2375 
2376                 left_arg = get_argument_from_call_expr(expr->args, left_param);
2377                 if (!left_arg)
2378                         return;
2379         }
2380 
2381         if (!split_op_param_key(value, &op, &right_param, &right_key))
2382                 return;
2383 
2384         right_arg = get_argument_from_call_expr(expr->args, right_param);
2385         if (!right_arg)
2386                 return;
2387 
2388         left_name = get_variable_from_key(left_arg, key, &left_sym);
2389         if (!left_name || !left_sym)
2390                 goto free;
2391 
2392         right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2393         if (!right_name || !right_sym)
2394                 goto free;
2395 
2396         add_var_sym(&left_vsl, left_name, left_sym);
2397         add_var_sym(&right_vsl, right_name, right_sym);
2398 
2399         add_comparison_var_sym(NULL, left_name, left_vsl, op, NULL, right_name, right_vsl);
2400 
2401 free:
2402         free_string(left_name);
2403         free_string(right_name);
2404 }
2405 
2406 int param_compare_limit_is_impossible(struct expression *expr, int left_param, char *left_key, char *value)
2407 {
2408         struct smatch_state *state;
2409         char *left_name = NULL;
2410         char *right_name = NULL;
2411         struct symbol *left_sym, *right_sym;
2412         struct expression *left_arg, *right_arg;
2413         int op, state_op;
2414         int right_param;
2415         char *right_key;
2416         int ret = 0;
2417         char buf[256];
2418 
2419         while (expr->type == EXPR_ASSIGNMENT)
2420                 expr = strip_expr(expr->right);
2421         if (expr->type != EXPR_CALL)
2422                 return 0;
2423 
2424         if (!split_op_param_key(value, &op, &right_param, &right_key))
2425                 return 0;
2426 
2427         left_arg = get_argument_from_call_expr(expr->args, left_param);
2428         if (!left_arg)
2429                 return 0;
2430 
2431         right_arg = get_argument_from_call_expr(expr->args, right_param);
2432         if (!right_arg)
2433                 return 0;
2434 
2435         left_name = get_variable_from_key(left_arg, left_key, &left_sym);
2436         right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2437         if (!left_name || !right_name)
2438                 goto free;
2439 
2440         snprintf(buf, sizeof(buf), "%s vs %s", left_name, right_name);
2441         state = get_state(compare_id, buf, NULL);
2442         if (!state)
2443                 goto free;
2444         state_op = state_to_comparison(state);
2445         if (!state_op)
2446                 goto free;
2447 
2448         if (!filter_comparison(remove_unsigned_from_comparison(state_op), op))
2449                 ret = 1;
2450 free:
2451         free_string(left_name);
2452         free_string(right_name);
2453         return ret;
2454 }
2455 
2456 int impossibly_high_comparison(struct expression *expr)
2457 {
2458         struct smatch_state *link_state;
2459         struct sm_state *sm;
2460         struct string_list *links;
2461         char *link;
2462         struct compare_data *data;
2463 
2464         link_state = get_state_expr(link_id, expr);
2465         if (!link_state) {
2466                 if (expr->type == EXPR_BINOP &&
2467                     (impossibly_high_comparison(expr->left) ||
2468                      impossibly_high_comparison(expr->right)))
2469                         return 1;
2470                 return 0;
2471         }
2472 
2473         links = link_state->data;
2474         FOR_EACH_PTR(links, link) {
2475                 sm = get_sm_state(compare_id, link, NULL);
2476                 if (!sm)
2477                         continue;
2478                 data = sm->state->data;
2479                 if (!data)
2480                         continue;
2481                 if (!possibly_true(data->left, data->comparison, data->right))
2482                         return 1;
2483         } END_FOR_EACH_PTR(link);
2484 
2485         return 0;
2486 }
2487 
2488 static void free_data(struct symbol *sym)
2489 {
2490         if (__inline_fn)
2491                 return;
2492         clear_compare_data_alloc();
2493 }
2494 
2495 void register_comparison(int id)
2496 {
2497         compare_id = id;
2498         add_hook(&save_start_states, AFTER_DEF_HOOK);
2499         add_unmatched_state_hook(compare_id, unmatched_comparison);
2500         add_pre_merge_hook(compare_id, &pre_merge_hook);
2501         add_merge_hook(compare_id, &merge_compare_states);
2502         add_hook(&free_data, AFTER_FUNC_HOOK);
2503         add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2504         add_split_return_callback(&print_return_comparison);
2505 
2506         select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
2507         add_hook(&match_preop, OP_HOOK);
2508 }
2509 
2510 void register_comparison_late(int id)
2511 {
2512         add_hook(&match_assign, ASSIGNMENT_HOOK);
2513 }
2514 
2515 void register_comparison_links(int id)
2516 {
2517         link_id = id;
2518         add_merge_hook(link_id, &merge_links);
2519         add_modification_hook(link_id, &match_modify);
2520         add_modification_hook_late(link_id, match_inc_dec);
2521 
2522         add_member_info_callback(link_id, struct_member_callback);
2523 }
2524 
2525 void register_comparison_inc_dec(int id)
2526 {
2527         inc_dec_id = id;
2528         add_modification_hook_late(inc_dec_id, &iter_modify);
2529 }
2530 
2531 void register_comparison_inc_dec_links(int id)
2532 {
2533         inc_dec_link_id = id;
2534         set_up_link_functions(inc_dec_id, inc_dec_link_id);
2535 }
2536 
2537 static void filter_by_sm(struct sm_state *sm, int op,
2538                        struct state_list **true_stack,
2539                        struct state_list **false_stack)
2540 {
2541         struct compare_data *data;
2542         int istrue = 0;
2543         int isfalse = 0;
2544 
2545         if (!sm)
2546                 return;
2547         data = sm->state->data;
2548         if (!data) {
2549                 if (sm->merged) {
2550                         filter_by_sm(sm->left, op, true_stack, false_stack);
2551                         filter_by_sm(sm->right, op, true_stack, false_stack);
2552                 }
2553                 return;
2554         }
2555 
2556         if (data->comparison &&
2557             data->comparison == filter_comparison(data->comparison, op))
2558                 istrue = 1;
2559 
2560         if (data->comparison &&
2561             data->comparison == filter_comparison(data->comparison, negate_comparison(op)))
2562                 isfalse = 1;
2563 
2564         if (istrue)
2565                 add_ptr_list(true_stack, sm);
2566         if (isfalse)
2567                 add_ptr_list(false_stack, sm);
2568 
2569         if (sm->merged) {
2570                 filter_by_sm(sm->left, op, true_stack, false_stack);
2571                 filter_by_sm(sm->right, op, true_stack, false_stack);
2572         }
2573 }
2574 
2575 struct sm_state *comparison_implication_hook(struct expression *expr,
2576                                 struct state_list **true_stack,
2577                                 struct state_list **false_stack)
2578 {
2579         struct sm_state *sm;
2580         char *left, *right;
2581         int op;
2582         static char buf[256];
2583 
2584         if (expr->type != EXPR_COMPARE)
2585                 return NULL;
2586 
2587         op = expr->op;
2588 
2589         left = expr_to_var(expr->left);
2590         right = expr_to_var(expr->right);
2591         if (!left || !right) {
2592                 free_string(left);
2593                 free_string(right);
2594                 return NULL;
2595         }
2596 
2597         if (strcmp(left, right) > 0) {
2598                 char *tmp = left;
2599 
2600                 left = right;
2601                 right = tmp;
2602                 op = flip_comparison(op);
2603         }
2604 
2605         snprintf(buf, sizeof(buf), "%s vs %s", left, right);
2606         sm = get_sm_state(compare_id, buf, NULL);
2607         if (!sm)
2608                 return NULL;
2609         if (!sm->merged)
2610                 return NULL;
2611 
2612         filter_by_sm(sm, op, true_stack, false_stack);
2613         if (!*true_stack && !*false_stack)
2614                 return NULL;
2615 
2616         if (option_debug)
2617                 sm_msg("implications from comparison: (%s)", show_sm(sm));
2618 
2619         return sm;
2620 }