smatch_comparison.c

   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 /* for handling for loops */
  41 STATE(start);
  42 STATE(incremented);
  43
  44 ALLOCATOR(compare_data, "compare data");
  45
  46 static struct symbol *vsl_to_sym(struct var_sym_list *vsl)
  47 {
  48         struct var_sym *vs;
  49
  50         if (!vsl)
  51                 return NULL;
  52         if (ptr_list_size((struct ptr_list *)vsl) != 1)
  53                 return NULL;
  54         vs = first_ptr_list((struct ptr_list *)vsl);
  55         return vs->sym;
  56 }
  57
  58 static struct smatch_state *alloc_compare_state(
  59                 const char *var1, struct var_sym_list *vsl1,
  60                 int comparison,
  61                 const char *var2, struct var_sym_list *vsl2)
  62 {
  63         struct smatch_state *state;
  64         struct compare_data *data;
  65
  66         state = __alloc_smatch_state(0);
  67         state->name = alloc_sname(show_special(comparison));
  68         data = __alloc_compare_data(0);
  69         data->var1 = alloc_sname(var1);
  70         data->vsl1 = clone_var_sym_list(vsl1);
  71         data->comparison = comparison;
  72         data->var2 = alloc_sname(var2);
  73         data->vsl2 = clone_var_sym_list(vsl2);
  74         state->data = data;
  75         return state;
  76 }
  77
  78 static int state_to_comparison(struct smatch_state *state)
  79 {
  80         if (!state || !state->data)
  81                 return 0;
  82         return ((struct compare_data *)state->data)->comparison;
  83 }
  84
  85 /*
  86  * flip_comparison() reverses the op left and right.  So "x >= y" becomes "y <= x".
  87  */
  88 int flip_comparison(int op)
  89 {
  90         switch (op) {
  91         case 0:
  92                 return 0;
  93         case '<':
  94                 return '>';
  95         case SPECIAL_UNSIGNED_LT:
  96                 return SPECIAL_UNSIGNED_GT;
  97         case SPECIAL_LTE:
  98                 return SPECIAL_GTE;
  99         case SPECIAL_UNSIGNED_LTE:
 100                 return SPECIAL_UNSIGNED_GTE;
 101         case SPECIAL_EQUAL:
 102                 return SPECIAL_EQUAL;
 103         case SPECIAL_NOTEQUAL:
 104                 return SPECIAL_NOTEQUAL;
 105         case SPECIAL_GTE:
 106                 return SPECIAL_LTE;
 107         case SPECIAL_UNSIGNED_GTE:
 108                 return SPECIAL_UNSIGNED_LTE;
 109         case '>':
 110                 return '<';
 111         case SPECIAL_UNSIGNED_GT:
 112                 return SPECIAL_UNSIGNED_LT;
 113         default:
 114                 sm_msg("internal smatch bug.  unhandled comparison %d", op);
 115                 return op;
 116         }
 117 }
 118
 119 int negate_comparison(int op)
 120 {
 121         switch (op) {
 122         case 0:
 123                 return 0;
 124         case '<':
 125                 return SPECIAL_GTE;
 126         case SPECIAL_UNSIGNED_LT:
 127                 return SPECIAL_UNSIGNED_GTE;
 128         case SPECIAL_LTE:
 129                 return '>';
 130         case SPECIAL_UNSIGNED_LTE:
 131                 return SPECIAL_UNSIGNED_GT;
 132         case SPECIAL_EQUAL:
 133                 return SPECIAL_NOTEQUAL;
 134         case SPECIAL_NOTEQUAL:
 135                 return SPECIAL_EQUAL;
 136         case SPECIAL_GTE:
 137                 return '<';
 138         case SPECIAL_UNSIGNED_GTE:
 139                 return SPECIAL_UNSIGNED_LT;
 140         case '>':
 141                 return SPECIAL_LTE;
 142         case SPECIAL_UNSIGNED_GT:
 143                 return SPECIAL_UNSIGNED_LTE;
 144         default:
 145                 sm_msg("internal smatch bug.  unhandled comparison %d", op);
 146                 return op;
 147         }
 148 }
 149
 150 static int rl_comparison(struct range_list *left_rl, struct range_list *right_rl)
 151 {
 152         sval_t left_min, left_max, right_min, right_max;
 153
 154         if (!left_rl || !right_rl)
 155                 return 0;
 156
 157         left_min = rl_min(left_rl);
 158         left_max = rl_max(left_rl);
 159         right_min = rl_min(right_rl);
 160         right_max = rl_max(right_rl);
 161
 162         if (left_min.value == left_max.value &&
 163             right_min.value == right_max.value &&
 164             left_min.value == right_min.value)
 165                 return SPECIAL_EQUAL;
 166
 167         if (sval_cmp(left_max, right_min) < 0)
 168                 return '<';
 169         if (sval_cmp(left_max, right_min) == 0)
 170                 return SPECIAL_LTE;
 171         if (sval_cmp(left_min, right_max) > 0)
 172                 return '>';
 173         if (sval_cmp(left_min, right_max) == 0)
 174                 return SPECIAL_GTE;
 175
 176         return 0;
 177 }
 178
 179 static struct range_list *get_orig_rl(struct var_sym_list *vsl)
 180 {
 181         struct symbol *sym;
 182         struct smatch_state *state;
 183
 184         if (!vsl)
 185                 return NULL;
 186         sym = vsl_to_sym(vsl);
 187         if (!sym || !sym->ident)
 188                 return NULL;
 189         state = get_orig_estate(sym->ident->name, sym);
 190         return estate_rl(state);
 191 }
 192
 193 static struct smatch_state *unmatched_comparison(struct sm_state *sm)
 194 {
 195         struct compare_data *data = sm->state->data;
 196         struct range_list *left_rl, *right_rl;
 197         int op;
 198
 199         if (!data)
 200                 return &undefined;
 201
 202         if (strstr(data->var1, " orig"))
 203                 left_rl = get_orig_rl(data->vsl1);
 204         else if (!get_implied_rl_var_sym(data->var1, vsl_to_sym(data->vsl1), &left_rl))
 205                 return &undefined;
 206         if (strstr(data->var2, " orig"))
 207                 right_rl = get_orig_rl(data->vsl2);
 208         else if (!get_implied_rl_var_sym(data->var2, vsl_to_sym(data->vsl2), &right_rl))
 209                 return &undefined;
 210
 211
 212         op = rl_comparison(left_rl, right_rl);
 213         if (op)
 214                 return alloc_compare_state(data->var1, data->vsl1, op, data->var2, data->vsl2);
 215
 216         return &undefined;
 217 }
 218
 219 /* remove_unsigned_from_comparison() is obviously a hack. */
 220 static int remove_unsigned_from_comparison(int op)
 221 {
 222         switch (op) {
 223         case SPECIAL_UNSIGNED_LT:
 224                 return '<';
 225         case SPECIAL_UNSIGNED_LTE:
 226                 return SPECIAL_LTE;
 227         case SPECIAL_UNSIGNED_GTE:
 228                 return SPECIAL_GTE;
 229         case SPECIAL_UNSIGNED_GT:
 230                 return '>';
 231         default:
 232                 return op;
 233         }
 234 }
 235
 236 /*
 237  * This is for when you merge states "a < b" and "a == b", the result is that
 238  * we can say for sure, "a <= b" after the merge.
 239  */
 240 static int merge_comparisons(int one, int two)
 241 {
 242         int LT, EQ, GT;
 243
 244         one = remove_unsigned_from_comparison(one);
 245         two = remove_unsigned_from_comparison(two);
 246
 247         if (one == two)
 248                 return one;
 249
 250         LT = EQ = GT = 0;
 251
 252         switch (one) {
 253         case '<':
 254                 LT = 1;
 255                 break;
 256         case SPECIAL_LTE:
 257                 LT = 1;
 258                 EQ = 1;
 259                 break;
 260         case SPECIAL_EQUAL:
 261                 EQ = 1;
 262                 break;
 263         case SPECIAL_GTE:
 264                 GT = 1;
 265                 EQ = 1;
 266                 break;
 267         case '>':
 268                 GT = 1;
 269         }
 270
 271         switch (two) {
 272         case '<':
 273                 LT = 1;
 274                 break;
 275         case SPECIAL_LTE:
 276                 LT = 1;
 277                 EQ = 1;
 278                 break;
 279         case SPECIAL_EQUAL:
 280                 EQ = 1;
 281                 break;
 282         case SPECIAL_GTE:
 283                 GT = 1;
 284                 EQ = 1;
 285                 break;
 286         case '>':
 287                 GT = 1;
 288         }
 289
 290         if (LT && EQ && GT)
 291                 return 0;
 292         if (LT && EQ)
 293                 return SPECIAL_LTE;
 294         if (LT && GT)
 295                 return SPECIAL_NOTEQUAL;
 296         if (LT)
 297                 return '<';
 298         if (EQ && GT)
 299                 return SPECIAL_GTE;
 300         if (GT)
 301                 return '>';
 302         return 0;
 303 }
 304
 305 /*
 306  * This is for if you have "a < b" and "b <= c".  Or in other words,
 307  * "a < b <= c".  You would call this like get_combined_comparison('<', '<=').
 308  * The return comparison would be '<'.
 309  *
 310  * This function is different from merge_comparisons(), for example:
 311  * merge_comparison('<', '==') returns '<='
 312  * get_combined_comparison('<', '==') returns '<'
 313  */
 314 static int combine_comparisons(int left_compare, int right_compare)
 315 {
 316         int LT, EQ, GT;
 317
 318         left_compare = remove_unsigned_from_comparison(left_compare);
 319         right_compare = remove_unsigned_from_comparison(right_compare);
 320
 321         LT = EQ = GT = 0;
 322
 323         switch (left_compare) {
 324         case '<':
 325                 LT++;
 326                 break;
 327         case SPECIAL_LTE:
 328                 LT++;
 329                 EQ++;
 330                 break;
 331         case SPECIAL_EQUAL:
 332                 return right_compare;
 333         case SPECIAL_GTE:
 334                 GT++;
 335                 EQ++;
 336                 break;
 337         case '>':
 338                 GT++;
 339         }
 340
 341         switch (right_compare) {
 342         case '<':
 343                 LT++;
 344                 break;
 345         case SPECIAL_LTE:
 346                 LT++;
 347                 EQ++;
 348                 break;
 349         case SPECIAL_EQUAL:
 350                 return left_compare;
 351         case SPECIAL_GTE:
 352                 GT++;
 353                 EQ++;
 354                 break;
 355         case '>':
 356                 GT++;
 357         }
 358
 359         if (LT == 2) {
 360                 if (EQ == 2)
 361                         return SPECIAL_LTE;
 362                 return '<';
 363         }
 364
 365         if (GT == 2) {
 366                 if (EQ == 2)
 367                         return SPECIAL_GTE;
 368                 return '>';
 369         }
 370         return 0;
 371 }
 372
 373 static int filter_comparison(int orig, int op)
 374 {
 375         if (orig == op)
 376                 return orig;
 377
 378         switch (orig) {
 379         case 0:
 380                 return op;
 381         case '<':
 382                 switch (op) {
 383                 case '<':
 384                 case SPECIAL_LTE:
 385                 case SPECIAL_NOTEQUAL:
 386                         return '<';
 387                 }
 388                 return 0;
 389         case SPECIAL_LTE:
 390                 switch (op) {
 391                 case '<':
 392                 case SPECIAL_LTE:
 393                 case SPECIAL_EQUAL:
 394                         return op;
 395                 case SPECIAL_NOTEQUAL:
 396                         return '<';
 397                 }
 398                 return 0;
 399         case SPECIAL_EQUAL:
 400                 switch (op) {
 401                 case SPECIAL_LTE:
 402                 case SPECIAL_EQUAL:
 403                 case SPECIAL_GTE:
 404                 case SPECIAL_UNSIGNED_LTE:
 405                 case SPECIAL_UNSIGNED_GTE:
 406                         return SPECIAL_EQUAL;
 407                 }
 408                 return 0;
 409         case SPECIAL_NOTEQUAL:
 410                 switch (op) {
 411                 case '<':
 412                 case SPECIAL_LTE:
 413                         return '<';
 414                 case SPECIAL_UNSIGNED_LT:
 415                 case SPECIAL_UNSIGNED_LTE:
 416                         return SPECIAL_UNSIGNED_LT;
 417                 case SPECIAL_NOTEQUAL:
 418                         return op;
 419                 case '>':
 420                 case SPECIAL_GTE:
 421                         return '>';
 422                 case SPECIAL_UNSIGNED_GT:
 423                 case SPECIAL_UNSIGNED_GTE:
 424                         return SPECIAL_UNSIGNED_GT;
 425                 }
 426                 return 0;
 427         case SPECIAL_GTE:
 428                 switch (op) {
 429                 case SPECIAL_LTE:
 430                         return SPECIAL_EQUAL;
 431                 case '>':
 432                 case SPECIAL_GTE:
 433                 case SPECIAL_EQUAL:
 434                         return op;
 435                 case SPECIAL_NOTEQUAL:
 436                         return '>';
 437                 }
 438                 return 0;
 439         case '>':
 440                 switch (op) {
 441                 case '>':
 442                 case SPECIAL_GTE:
 443                 case SPECIAL_NOTEQUAL:
 444                         return '>';
 445                 }
 446                 return 0;
 447         case SPECIAL_UNSIGNED_LT:
 448                 switch (op) {
 449                 case SPECIAL_UNSIGNED_LT:
 450                 case SPECIAL_UNSIGNED_LTE:
 451                 case SPECIAL_NOTEQUAL:
 452                         return SPECIAL_UNSIGNED_LT;
 453                 }
 454                 return 0;
 455         case SPECIAL_UNSIGNED_LTE:
 456                 switch (op) {
 457                 case SPECIAL_UNSIGNED_LT:
 458                 case SPECIAL_UNSIGNED_LTE:
 459                 case SPECIAL_EQUAL:
 460                         return op;
 461                 case SPECIAL_NOTEQUAL:
 462                         return SPECIAL_UNSIGNED_LT;
 463                 case SPECIAL_UNSIGNED_GTE:
 464                         return SPECIAL_EQUAL;
 465                 }
 466                 return 0;
 467         case SPECIAL_UNSIGNED_GTE:
 468                 switch (op) {
 469                 case SPECIAL_UNSIGNED_LTE:
 470                         return SPECIAL_EQUAL;
 471                 case SPECIAL_NOTEQUAL:
 472                         return SPECIAL_UNSIGNED_GT;
 473                 case SPECIAL_EQUAL:
 474                 case SPECIAL_UNSIGNED_GTE:
 475                 case SPECIAL_UNSIGNED_GT:
 476                         return op;
 477                 }
 478                 return 0;
 479         case SPECIAL_UNSIGNED_GT:
 480                 switch (op) {
 481                 case SPECIAL_UNSIGNED_GT:
 482                 case SPECIAL_UNSIGNED_GTE:
 483                 case SPECIAL_NOTEQUAL:
 484                         return SPECIAL_UNSIGNED_GT;
 485                 }
 486                 return 0;
 487         }
 488         return 0;
 489 }
 490
 491 static struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
 492 {
 493         struct compare_data *data = s1->data;
 494         int op;
 495
 496         op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
 497         if (op)
 498                 return alloc_compare_state(data->var1, data->vsl1, op, data->var2, data->vsl2);
 499         return &undefined;
 500 }
 501
 502 static struct smatch_state *alloc_link_state(struct string_list *links)
 503 {
 504         struct smatch_state *state;
 505         static char buf[256];
 506         char *tmp;
 507         int i;
 508
 509         state = __alloc_smatch_state(0);
 510
 511         i = 0;
 512         FOR_EACH_PTR(links, tmp) {
 513                 if (!i++) {
 514                         snprintf(buf, sizeof(buf), "%s", tmp);
 515                 } else {
 516                         append(buf, ", ", sizeof(buf));
 517                         append(buf, tmp, sizeof(buf));
 518                 }
 519         } END_FOR_EACH_PTR(tmp);
 520
 521         state->name = alloc_sname(buf);
 522         state->data = links;
 523         return state;
 524 }
 525
 526 static void save_start_states(struct statement *stmt)
 527 {
 528         struct symbol *param;
 529         char orig[64];
 530         char state_name[128];
 531         struct smatch_state *state;
 532         struct string_list *links;
 533         char *link;
 534
 535         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
 536                 struct var_sym_list *vsl1 = NULL;
 537                 struct var_sym_list *vsl2 = NULL;
 538
 539                 if (!param->ident)
 540                         continue;
 541                 snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
 542                 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
 543                 add_var_sym(&vsl1, param->ident->name, param);
 544                 add_var_sym(&vsl2, orig, param);
 545                 state = alloc_compare_state(param->ident->name, vsl1, SPECIAL_EQUAL, alloc_sname(orig), vsl2);
 546                 set_state(compare_id, state_name, NULL, state);
 547
 548                 link = alloc_sname(state_name);
 549                 links = NULL;
 550                 insert_string(&links, link);
 551                 state = alloc_link_state(links);
 552                 set_state(link_id, param->ident->name, param, state);
 553         } END_FOR_EACH_PTR(param);
 554 }
 555
 556 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
 557 {
 558         struct smatch_state *ret;
 559         struct string_list *links;
 560
 561         links = combine_string_lists(s1->data, s2->data);
 562         ret = alloc_link_state(links);
 563         return ret;
 564 }
 565
 566 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
 567 {
 568         struct smatch_state *old_state, *new_state;
 569         struct string_list *links;
 570         char *new;
 571
 572         old_state = get_state(link_id, var, sym);
 573         if (old_state)
 574                 links = clone_str_list(old_state->data);
 575         else
 576                 links = NULL;
 577
 578         new = alloc_sname(link);
 579         insert_string(&links, new);
 580
 581         new_state = alloc_link_state(links);
 582         set_state(link_id, var, sym, new_state);
 583 }
 584
 585 static void match_inc(struct sm_state *sm)
 586 {
 587         struct string_list *links;
 588         struct smatch_state *state;
 589         char *tmp;
 590
 591         links = sm->state->data;
 592
 593         FOR_EACH_PTR(links, tmp) {
 594                 state = get_state(compare_id, tmp, NULL);
 595
 596                 switch (state_to_comparison(state)) {
 597                 case SPECIAL_EQUAL:
 598                 case SPECIAL_GTE:
 599                 case SPECIAL_UNSIGNED_GTE:
 600                 case '>':
 601                 case SPECIAL_UNSIGNED_GT: {
 602                         struct compare_data *data = state->data;
 603                         struct smatch_state *new;
 604
 605                         new = alloc_compare_state(data->var1, data->vsl1, '>', data->var2, data->vsl2);
 606                         set_state(compare_id, tmp, NULL, new);
 607                         break;
 608                 }
 609                 default:
 610                         set_state(compare_id, tmp, NULL, &undefined);
 611                 }
 612         } END_FOR_EACH_PTR(tmp);
 613 }
 614
 615 static void match_dec(struct sm_state *sm)
 616 {
 617         struct string_list *links;
 618         struct smatch_state *state;
 619         char *tmp;
 620
 621         links = sm->state->data;
 622
 623         FOR_EACH_PTR(links, tmp) {
 624                 state = get_state(compare_id, tmp, NULL);
 625
 626                 switch (state_to_comparison(state)) {
 627                 case SPECIAL_EQUAL:
 628                 case SPECIAL_LTE:
 629                 case SPECIAL_UNSIGNED_LTE:
 630                 case '<':
 631                 case SPECIAL_UNSIGNED_LT: {
 632                         struct compare_data *data = state->data;
 633                         struct smatch_state *new;
 634
 635                         new = alloc_compare_state(data->var1, data->vsl1, '<', data->var2, data->vsl2);
 636                         set_state(compare_id, tmp, NULL, new);
 637                         break;
 638                         }
 639                 default:
 640                         set_state(compare_id, tmp, NULL, &undefined);
 641                 }
 642         } END_FOR_EACH_PTR(tmp);
 643 }
 644
 645 static int match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
 646 {
 647         if (!mod_expr)
 648                 return 0;
 649         if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
 650                 return 0;
 651
 652         if (mod_expr->op == SPECIAL_INCREMENT) {
 653                 match_inc(sm);
 654                 return 1;
 655         }
 656         if (mod_expr->op == SPECIAL_DECREMENT) {
 657                 match_dec(sm);
 658                 return 1;
 659         }
 660         return 0;
 661 }
 662
 663 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
 664 {
 665         struct string_list *links;
 666         char *tmp;
 667
 668         /* Huh???  This needs a comment!  */
 669         if (match_inc_dec(sm, mod_expr))
 670                 return;
 671
 672         links = sm->state->data;
 673
 674         FOR_EACH_PTR(links, tmp) {
 675                 set_state(compare_id, tmp, NULL, &undefined);
 676         } END_FOR_EACH_PTR(tmp);
 677         set_state(link_id, sm->name, sm->sym, &undefined);
 678 }
 679
 680 static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym)
 681 {
 682         char *name, *left_name, *right_name;
 683         struct symbol *tmp;
 684         char buf[128];
 685
 686         expr = strip_expr(expr);
 687         if (!expr)
 688                 return NULL;
 689         if (sym)
 690                 *sym = NULL;
 691
 692         if (expr->type == EXPR_PREOP &&
 693             (expr->op == SPECIAL_INCREMENT ||
 694              expr->op == SPECIAL_DECREMENT))
 695                 expr = strip_expr(expr->unop);
 696
 697         name = expr_to_var_sym(expr, &tmp);
 698         if (name && tmp) {
 699                 if (sym)
 700                         *sym = tmp;
 701                 return name;
 702         }
 703         if (name)
 704                 free_string(name);
 705
 706         if (expr->type != EXPR_BINOP)
 707                 return NULL;
 708         if (expr->op != '-' && expr->op != '+')
 709                 return NULL;
 710
 711         left_name = expr_to_var(expr->left);
 712         if (!left_name)
 713                 return NULL;
 714         right_name = expr_to_var(expr->right);
 715         if (!right_name) {
 716                 free_string(left_name);
 717                 return NULL;
 718         }
 719         snprintf(buf, sizeof(buf), "%s %s %s", left_name, show_special(expr->op), right_name);
 720         free_string(left_name);
 721         free_string(right_name);
 722         return alloc_string(buf);
 723 }
 724
 725 static char *chunk_to_var(struct expression *expr)
 726 {
 727         return chunk_to_var_sym(expr, NULL);
 728 }
 729
 730 static void save_link(struct expression *expr, char *link)
 731 {
 732         char *var;
 733         struct symbol *sym;
 734
 735         expr = strip_expr(expr);
 736         if (expr->type == EXPR_BINOP) {
 737                 char *chunk;
 738
 739                 chunk = chunk_to_var(expr);
 740                 if (!chunk)
 741                         return;
 742
 743                 save_link(expr->left, link);
 744                 save_link(expr->right, link);
 745                 save_link_var_sym(chunk, NULL, link);
 746                 return;
 747         }
 748
 749         var = expr_to_var_sym(expr, &sym);
 750         if (!var || !sym)
 751                 goto done;
 752
 753         save_link_var_sym(var, sym, link);
 754 done:
 755         free_string(var);
 756 }
 757
 758 static int get_orig_comparison(struct stree *pre_stree, const char *left, const char *right)
 759 {
 760         struct smatch_state *state;
 761         struct compare_data *data;
 762         int flip = 0;
 763         char state_name[256];
 764
 765         if (strcmp(left, right) > 0) {
 766                 const char *tmp = right;
 767
 768                 flip = 1;
 769                 right = left;
 770                 left = tmp;
 771         }
 772
 773         snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
 774         state = get_state_stree(pre_stree, compare_id, state_name, NULL);
 775         if (!state || !state->data)
 776                 return 0;
 777         data = state->data;
 778         if (flip)
 779                 return flip_comparison(data->comparison);
 780         return data->comparison;
 781
 782 }
 783
 784 /*
 785  * The idea here is that we take a comparison "a < b" and then we look at all
 786  * the things which "b" is compared against "b < c" and we say that that implies
 787  * a relationship "a < c".
 788  *
 789  * The names here about because the comparisons are organized like this
 790  * "a < b < c".
 791  *
 792  */
 793 static void update_tf_links(struct stree *pre_stree,
 794                             const char *left_var, struct var_sym_list *left_vsl,
 795                             int left_comparison, int left_false_comparison,
 796                             const char *mid_var, struct var_sym_list *mid_vsl,
 797                             struct string_list *links)
 798 {
 799         struct smatch_state *state;
 800         struct smatch_state *true_state, *false_state;
 801         struct compare_data *data;
 802         const char *right_var;
 803         struct var_sym_list *right_vsl;
 804         int orig_comparison;
 805         int right_comparison;
 806         int true_comparison;
 807         int false_comparison;
 808         char *tmp;
 809         char state_name[256];
 810         struct var_sym *vs;
 811
 812         FOR_EACH_PTR(links, tmp) {
 813                 state = get_state_stree(pre_stree, compare_id, tmp, NULL);
 814                 if (!state || !state->data)
 815                         continue;
 816                 data = state->data;
 817                 right_comparison = data->comparison;
 818                 right_var = data->var2;
 819                 right_vsl = data->vsl2;
 820                 if (strcmp(mid_var, right_var) == 0) {
 821                         right_var = data->var1;
 822                         right_vsl = data->vsl1;
 823                         right_comparison = flip_comparison(right_comparison);
 824                 }
 825                 if (strcmp(left_var, right_var) == 0)
 826                         continue;
 827
 828                 orig_comparison = get_orig_comparison(pre_stree, left_var, right_var);
 829
 830                 true_comparison = combine_comparisons(left_comparison, right_comparison);
 831                 false_comparison = combine_comparisons(left_false_comparison, right_comparison);
 832
 833                 true_comparison = filter_comparison(orig_comparison, true_comparison);
 834                 false_comparison = filter_comparison(orig_comparison, false_comparison);
 835
 836                 if (strcmp(left_var, right_var) > 0) {
 837                         const char *tmp_var = left_var;
 838                         struct var_sym_list *tmp_vsl = left_vsl;
 839
 840                         left_var = right_var;
 841                         left_vsl = right_vsl;
 842                         right_var = tmp_var;
 843                         right_vsl = tmp_vsl;
 844                         true_comparison = flip_comparison(true_comparison);
 845                         false_comparison = flip_comparison(false_comparison);
 846                 }
 847
 848                 if (!true_comparison && !false_comparison)
 849                         continue;
 850
 851                 if (true_comparison)
 852                         true_state = alloc_compare_state(left_var, left_vsl, true_comparison, right_var, right_vsl);
 853                 else
 854                         true_state = NULL;
 855                 if (false_comparison)
 856                         false_state = alloc_compare_state(left_var, left_vsl, false_comparison, right_var, right_vsl);
 857                 else
 858                         false_state = NULL;
 859
 860                 snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
 861                 set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
 862                 FOR_EACH_PTR(left_vsl, vs) {
 863                         save_link_var_sym(vs->var, vs->sym, state_name);
 864                 } END_FOR_EACH_PTR(vs);
 865                 FOR_EACH_PTR(right_vsl, vs) {
 866                         save_link_var_sym(vs->var, vs->sym, state_name);
 867                 } END_FOR_EACH_PTR(vs);
 868                 if (!vsl_to_sym(left_vsl))
 869                         save_link_var_sym(left_var, NULL, state_name);
 870                 if (!vsl_to_sym(right_vsl))
 871                         save_link_var_sym(right_var, NULL, state_name);
 872         } END_FOR_EACH_PTR(tmp);
 873 }
 874
 875 static void update_tf_data(struct stree *pre_stree,
 876                 const char *left_name, struct var_sym_list *left_vsl,
 877                 const char *right_name, struct var_sym_list *right_vsl,
 878                 int true_comparison, int false_comparison)
 879 {
 880         struct smatch_state *state;
 881
 882         state = get_state_stree(pre_stree, link_id, right_name, vsl_to_sym(right_vsl));
 883         if (state)
 884                 update_tf_links(pre_stree, left_name, left_vsl, true_comparison, false_comparison, right_name, right_vsl, state->data);
 885
 886         state = get_state_stree(pre_stree, link_id, left_name, vsl_to_sym(left_vsl));
 887         if (state)
 888                 update_tf_links(pre_stree, right_name, right_vsl, flip_comparison(true_comparison), flip_comparison(false_comparison), left_name, left_vsl, state->data);
 889 }
 890
 891 static void iter_modify(struct sm_state *sm, struct expression *mod_expr)
 892 {
 893         if (sm->state != &start ||
 894             !mod_expr ||
 895             (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP) ||
 896             mod_expr->op != SPECIAL_INCREMENT)
 897                 set_state(inc_dec_id, sm->name, sm->sym, &undefined);
 898         else
 899                 set_state(inc_dec_id, sm->name, sm->sym, &incremented);
 900 }
 901
 902 static void handle_for_loops(struct expression *expr, char *state_name, struct smatch_state *false_state)
 903 {
 904         sval_t sval;
 905         char *iter_name, *cap_name;
 906         struct symbol *iter_sym, *cap_sym;
 907         struct compare_data *data;
 908
 909         if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
 910                 return;
 911
 912         if (!__cur_stmt || !__prev_stmt)
 913                 return;
 914         if (__cur_stmt->type != STMT_ITERATOR)
 915                 return;
 916         if (__cur_stmt->iterator_pre_condition != expr)
 917                 return;
 918
 919         /* literals are handled in smatch_extra.c */
 920         if (get_value(expr->right, &sval))
 921                 return;
 922
 923         /* First time checking the condition */
 924         if (__prev_stmt == __cur_stmt->iterator_pre_statement) {
 925                 if (!get_implied_value(expr->left, &sval) ||
 926                     sval.value != 0)
 927                         return;
 928
 929                 iter_name = expr_to_var_sym(expr->left, &iter_sym);
 930                 cap_name = expr_to_var_sym(expr->right, &cap_sym);
 931                 if (!iter_name || !cap_name || !iter_sym || !cap_sym) {
 932                         free_string(iter_name);
 933                         free_string(cap_name);
 934                         return;
 935                 }
 936
 937                 set_state(inc_dec_id, iter_name, iter_sym, &start);
 938                 store_link(inc_dec_link_id, cap_name, cap_sym, iter_name, iter_sym);
 939
 940                 free_string(iter_name);
 941                 free_string(cap_name);
 942                 return;
 943         }
 944
 945         /* Second time checking the condtion */
 946         if (__prev_stmt != __cur_stmt->iterator_post_statement)
 947                 return;
 948
 949         if (get_state_expr(inc_dec_id, expr->left) != &incremented)
 950                 return;
 951
 952         data = false_state->data;
 953         false_state = alloc_compare_state(data->var1, data->vsl1, SPECIAL_EQUAL, data->var2, data->vsl2);
 954
 955         set_true_false_states(compare_id, state_name, NULL, NULL, false_state);
 956 }
 957
 958 static void match_compare(struct expression *expr)
 959 {
 960         char *left = NULL;
 961         char *right = NULL;
 962         struct symbol *left_sym, *right_sym;
 963         struct var_sym_list *left_vsl, *right_vsl;
 964         int op, false_op;
 965         int orig_comparison;
 966         struct smatch_state *true_state, *false_state;
 967         char state_name[256];
 968         struct stree *pre_stree;
 969         sval_t sval;
 970
 971         if (expr->type != EXPR_COMPARE)
 972                 return;
 973
 974         op = expr->op;
 975         false_op = negate_comparison(op);
 976
 977         if (op == SPECIAL_UNSIGNED_LT &&
 978             get_implied_value(expr->left, &sval) &&
 979             sval.value == 0)
 980                 false_op = SPECIAL_EQUAL;
 981
 982         if (op == SPECIAL_UNSIGNED_GT &&
 983             get_implied_value(expr->right, &sval) &&
 984             sval.value == 0)
 985                 false_op = SPECIAL_EQUAL;
 986
 987         left = chunk_to_var_sym(expr->left, &left_sym);
 988         if (!left)
 989                 goto free;
 990         left_vsl = expr_to_vsl(expr->left);
 991         right = chunk_to_var_sym(expr->right, &right_sym);
 992         if (!right)
 993                 goto free;
 994         right_vsl = expr_to_vsl(expr->right);
 995
 996         if (strcmp(left, right) > 0) {
 997                 struct symbol *tmp_sym = left_sym;
 998                 char *tmp_name = left;
 999                 struct var_sym_list *tmp_vsl = left_vsl;
1000
1001                 left = right;
1002                 left_sym = right_sym;
1003                 left_vsl = right_vsl;
1004                 right = tmp_name;
1005                 right_sym = tmp_sym;
1006                 right_vsl = tmp_vsl;
1007                 op = flip_comparison(op);
1008                 false_op = flip_comparison(false_op);
1009         }
1010
1011         orig_comparison = get_comparison_strings(left, right);
1012         op = filter_comparison(orig_comparison, op);
1013         false_op = filter_comparison(orig_comparison, false_op);
1014
1015         snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
1016         true_state = alloc_compare_state(left, left_vsl, op, right, right_vsl);
1017         false_state = alloc_compare_state(left, left_vsl, false_op, right, right_vsl);
1018
1019         pre_stree = clone_stree(__get_cur_stree());
1020         update_tf_data(pre_stree, left, left_vsl, right, right_vsl, op, false_op);
1021         free_stree(&pre_stree);
1022
1023         set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
1024         save_link(expr->left, state_name);
1025         save_link(expr->right, state_name);
1026
1027         handle_for_loops(expr, state_name, false_state);
1028 free:
1029         free_string(left);
1030         free_string(right);
1031 }
1032
1033 static void add_comparison_var_sym(const char *left_name,
1034                 struct var_sym_list *left_vsl,
1035                 int comparison,
1036                 const char *right_name, struct var_sym_list *right_vsl)
1037 {
1038         struct smatch_state *state;
1039         struct var_sym *vs;
1040         char state_name[256];
1041
1042         if (strcmp(left_name, right_name) > 0) {
1043                 const char *tmp_name = left_name;
1044                 struct var_sym_list *tmp_vsl = left_vsl;
1045
1046                 left_name = right_name;
1047                 left_vsl = right_vsl;
1048                 right_name = tmp_name;
1049                 right_vsl = tmp_vsl;
1050                 comparison = flip_comparison(comparison);
1051         }
1052         snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1053         state = alloc_compare_state(left_name, left_vsl, comparison, right_name, right_vsl);
1054
1055         set_state(compare_id, state_name, NULL, state);
1056
1057         FOR_EACH_PTR(left_vsl, vs) {
1058                 save_link_var_sym(vs->var, vs->sym, state_name);
1059         } END_FOR_EACH_PTR(vs);
1060         FOR_EACH_PTR(right_vsl, vs) {
1061                 save_link_var_sym(vs->var, vs->sym, state_name);
1062         } END_FOR_EACH_PTR(vs);
1063 }
1064
1065 static void add_comparison(struct expression *left, int comparison, struct expression *right)
1066 {
1067         char *left_name = NULL;
1068         char *right_name = NULL;
1069         struct symbol *left_sym, *right_sym;
1070         struct var_sym_list *left_vsl, *right_vsl;
1071         struct smatch_state *state;
1072         char state_name[256];
1073
1074         left_name = chunk_to_var_sym(left, &left_sym);
1075         if (!left_name)
1076                 goto free;
1077         left_vsl = expr_to_vsl(left);
1078         right_name = chunk_to_var_sym(right, &right_sym);
1079         if (!right_name)
1080                 goto free;
1081         right_vsl = expr_to_vsl(right);
1082
1083         if (strcmp(left_name, right_name) > 0) {
1084                 struct symbol *tmp_sym = left_sym;
1085                 char *tmp_name = left_name;
1086                 struct var_sym_list *tmp_vsl = left_vsl;
1087
1088                 left_name = right_name;
1089                 left_sym = right_sym;
1090                 left_vsl = right_vsl;
1091                 right_name = tmp_name;
1092                 right_sym = tmp_sym;
1093                 right_vsl = tmp_vsl;
1094                 comparison = flip_comparison(comparison);
1095         }
1096         snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1097         state = alloc_compare_state(left_name, left_vsl, comparison, right_name, right_vsl);
1098
1099         set_state(compare_id, state_name, NULL, state);
1100         save_link(left, state_name);
1101         save_link(right, state_name);
1102
1103 free:
1104         free_string(left_name);
1105         free_string(right_name);
1106 }
1107
1108 static void match_assign_add(struct expression *expr)
1109 {
1110         struct expression *right;
1111         struct expression *r_left, *r_right;
1112         sval_t left_tmp, right_tmp;
1113
1114         right = strip_expr(expr->right);
1115         r_left = strip_expr(right->left);
1116         r_right = strip_expr(right->right);
1117
1118         get_absolute_min(r_left, &left_tmp);
1119         get_absolute_min(r_right, &right_tmp);
1120
1121         if (left_tmp.value > 0)
1122                 add_comparison(expr->left, '>', r_right);
1123         else if (left_tmp.value == 0)
1124                 add_comparison(expr->left, SPECIAL_GTE, r_right);
1125
1126         if (right_tmp.value > 0)
1127                 add_comparison(expr->left, '>', r_left);
1128         else if (right_tmp.value == 0)
1129                 add_comparison(expr->left, SPECIAL_GTE, r_left);
1130 }
1131
1132 static void match_assign_sub(struct expression *expr)
1133 {
1134         struct expression *right;
1135         struct expression *r_left, *r_right;
1136         int comparison;
1137         sval_t min;
1138
1139         right = strip_expr(expr->right);
1140         r_left = strip_expr(right->left);
1141         r_right = strip_expr(right->right);
1142
1143         if (get_absolute_min(r_right, &min) && sval_is_negative(min))
1144                 return;
1145
1146         comparison = get_comparison(r_left, r_right);
1147
1148         switch (comparison) {
1149         case '>':
1150         case SPECIAL_GTE:
1151                 if (implied_not_equal(r_right, 0))
1152                         add_comparison(expr->left, '>', r_left);
1153                 else
1154                         add_comparison(expr->left, SPECIAL_GTE, r_left);
1155                 return;
1156         }
1157 }
1158
1159 static void match_assign_divide(struct expression *expr)
1160 {
1161         struct expression *right;
1162         struct expression *r_left, *r_right;
1163         sval_t min;
1164
1165         right = strip_expr(expr->right);
1166         r_left = strip_expr(right->left);
1167         r_right = strip_expr(right->right);
1168         if (!get_implied_min(r_right, &min) || min.value <= 1)
1169                 return;
1170
1171         add_comparison(expr->left, '<', r_left);
1172 }
1173
1174 static void match_binop_assign(struct expression *expr)
1175 {
1176         struct expression *right;
1177
1178         right = strip_expr(expr->right);
1179         if (right->op == '+')
1180                 match_assign_add(expr);
1181         if (right->op == '-')
1182                 match_assign_sub(expr);
1183         if (right->op == '/')
1184                 match_assign_divide(expr);
1185 }
1186
1187 static void copy_comparisons(struct expression *left, struct expression *right)
1188 {
1189         struct string_list *links;
1190         struct smatch_state *state;
1191         struct compare_data *data;
1192         struct symbol *left_sym, *right_sym;
1193         char *left_var = NULL;
1194         char *right_var = NULL;
1195         struct var_sym_list *left_vsl;
1196         const char *var;
1197         struct var_sym_list *vsl;
1198         int comparison;
1199         char *tmp;
1200
1201         left_var = chunk_to_var_sym(left, &left_sym);
1202         if (!left_var)
1203                 goto done;
1204         left_vsl = expr_to_vsl(left);
1205         right_var = chunk_to_var_sym(right, &right_sym);
1206         if (!right_var)
1207                 goto done;
1208
1209         state = get_state(link_id, right_var, right_sym);
1210         if (!state)
1211                 return;
1212         links = state->data;
1213
1214         FOR_EACH_PTR(links, tmp) {
1215                 state = get_state(compare_id, tmp, NULL);
1216                 if (!state || !state->data)
1217                         continue;
1218                 data = state->data;
1219                 comparison = data->comparison;
1220                 var = data->var2;
1221                 vsl = data->vsl2;
1222                 if (strcmp(var, right_var) == 0) {
1223                         var = data->var1;
1224                         vsl = data->vsl1;
1225                         comparison = flip_comparison(comparison);
1226                 }
1227                 add_comparison_var_sym(left_var, left_vsl, comparison, var, vsl);
1228         } END_FOR_EACH_PTR(tmp);
1229
1230 done:
1231         free_string(right_var);
1232 }
1233
1234 static void match_assign(struct expression *expr)
1235 {
1236         struct expression *right;
1237
1238         if (expr->op != '=')
1239                 return;
1240         if (__in_fake_assign || outside_of_function())
1241                 return;
1242
1243         if (is_struct(expr->left))
1244                 return;
1245
1246         copy_comparisons(expr->left, expr->right);
1247         add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
1248
1249         right = strip_expr(expr->right);
1250         if (right->type == EXPR_BINOP)
1251                 match_binop_assign(expr);
1252 }
1253
1254 int get_comparison_strings(const char *one, const char *two)
1255 {
1256         char buf[256];
1257         struct smatch_state *state;
1258         int invert = 0;
1259         int ret = 0;
1260
1261         if (strcmp(one, two) == 0)
1262                 return SPECIAL_EQUAL;
1263
1264         if (strcmp(one, two) > 0) {
1265                 const char *tmp = one;
1266
1267                 one = two;
1268                 two = tmp;
1269                 invert = 1;
1270         }
1271
1272         snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1273         state = get_state(compare_id, buf, NULL);
1274         if (state)
1275                 ret = state_to_comparison(state);
1276
1277         if (invert)
1278                 ret = flip_comparison(ret);
1279
1280         return ret;
1281 }
1282
1283 int get_comparison(struct expression *a, struct expression *b)
1284 {
1285         char *one = NULL;
1286         char *two = NULL;
1287         int ret = 0;
1288
1289         one = chunk_to_var(a);
1290         if (!one)
1291                 goto free;
1292         two = chunk_to_var(b);
1293         if (!two)
1294                 goto free;
1295
1296         ret = get_comparison_strings(one, two);
1297 free:
1298         free_string(one);
1299         free_string(two);
1300         return ret;
1301 }
1302
1303 int possible_comparison(struct expression *a, int comparison, struct expression *b)
1304 {
1305         char *one = NULL;
1306         char *two = NULL;
1307         int ret = 0;
1308         char buf[256];
1309         struct sm_state *sm;
1310         int saved;
1311
1312         one = chunk_to_var(a);
1313         if (!one)
1314                 goto free;
1315         two = chunk_to_var(b);
1316         if (!two)
1317                 goto free;
1318
1319
1320         if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1321                 ret = 1;
1322                 goto free;
1323         }
1324
1325         if (strcmp(one, two) > 0) {
1326                 char *tmp = one;
1327
1328                 one = two;
1329                 two = tmp;
1330                 comparison = flip_comparison(comparison);
1331         }
1332
1333         snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1334         sm = get_sm_state(compare_id, buf, NULL);
1335         if (!sm)
1336                 goto free;
1337
1338         FOR_EACH_PTR(sm->possible, sm) {
1339                 if (!sm->state->data)
1340                         continue;
1341                 saved = ((struct compare_data *)sm->state->data)->comparison;
1342                 if (saved == comparison)
1343                         ret = 1;
1344                 if (comparison == SPECIAL_EQUAL &&
1345                     (saved == SPECIAL_LTE ||
1346                      saved == SPECIAL_GTE ||
1347                      saved == SPECIAL_UNSIGNED_LTE ||
1348                      saved == SPECIAL_UNSIGNED_GTE))
1349                         ret = 1;
1350                 if (ret == 1)
1351                         goto free;
1352         } END_FOR_EACH_PTR(sm);
1353
1354         return ret;
1355 free:
1356         free_string(one);
1357         free_string(two);
1358         return ret;
1359 }
1360
1361 struct state_list *get_all_comparisons(struct expression *expr)
1362 {
1363         struct smatch_state *state;
1364         struct string_list *links;
1365         struct state_list *ret = NULL;
1366         struct sm_state *sm;
1367         char *tmp;
1368
1369         state = get_state_expr(link_id, expr);
1370         if (!state)
1371                 return NULL;
1372         links = state->data;
1373
1374         FOR_EACH_PTR(links, tmp) {
1375                 sm = get_sm_state(compare_id, tmp, NULL);
1376                 if (!sm)
1377                         continue;
1378                 // FIXME have to compare name with vsl
1379                 add_ptr_list(&ret, sm);
1380         } END_FOR_EACH_PTR(tmp);
1381
1382         return ret;
1383 }
1384
1385 struct state_list *get_all_possible_equal_comparisons(struct expression *expr)
1386 {
1387         struct smatch_state *state;
1388         struct string_list *links;
1389         struct state_list *ret = NULL;
1390         struct sm_state *sm;
1391         char *tmp;
1392
1393         state = get_state_expr(link_id, expr);
1394         if (!state)
1395                 return NULL;
1396         links = state->data;
1397
1398         FOR_EACH_PTR(links, tmp) {
1399                 sm = get_sm_state(compare_id, tmp, NULL);
1400                 if (!sm)
1401                         continue;
1402                 if (!strchr(sm->state->name, '='))
1403                         continue;
1404                 if (strcmp(sm->state->name, "!=") == 0)
1405                         continue;
1406                 add_ptr_list(&ret, sm);
1407         } END_FOR_EACH_PTR(tmp);
1408
1409         return ret;
1410 }
1411
1412 static void update_links_from_call(struct expression *left,
1413                                    int left_compare,
1414                                    struct expression *right)
1415 {
1416         struct string_list *links;
1417         struct smatch_state *state;
1418         struct compare_data *data;
1419         struct symbol *left_sym, *right_sym;
1420         char *left_var = NULL;
1421         char *right_var = NULL;
1422         struct var_sym_list *left_vsl;
1423         const char *var;
1424         struct var_sym_list *vsl;
1425         int comparison;
1426         char *tmp;
1427
1428         left_var = chunk_to_var_sym(left, &left_sym);
1429         if (!left_var)
1430                 goto done;
1431         left_vsl = expr_to_vsl(left);
1432         right_var = chunk_to_var_sym(right, &right_sym);
1433         if (!right_var)
1434                 goto done;
1435
1436         state = get_state(link_id, right_var, right_sym);
1437         if (!state)
1438                 return;
1439         links = state->data;
1440
1441         FOR_EACH_PTR(links, tmp) {
1442                 state = get_state(compare_id, tmp, NULL);
1443                 if (!state || !state->data)
1444                         continue;
1445                 data = state->data;
1446                 comparison = data->comparison;
1447                 var = data->var2;
1448                 vsl = data->vsl2;
1449                 if (strcmp(var, right_var) == 0) {
1450                         var = data->var1;
1451                         vsl = data->vsl1;
1452                         comparison = flip_comparison(comparison);
1453                 }
1454                 comparison = combine_comparisons(left_compare, comparison);
1455                 if (!comparison)
1456                         continue;
1457                 add_comparison_var_sym(left_var, left_vsl, comparison, var, vsl);
1458         } END_FOR_EACH_PTR(tmp);
1459
1460 done:
1461         free_string(right_var);
1462 }
1463
1464 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
1465 {
1466         struct expression *arg;
1467         int comparison;
1468         const char *c = range;
1469
1470         if (!str_to_comparison_arg(c, call, &comparison, &arg))
1471                 return;
1472         update_links_from_call(expr, comparison, arg);
1473         add_comparison(expr, comparison, arg);
1474 }
1475
1476 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with, int ignore)
1477 {
1478         struct symbol *param;
1479         char *var = NULL;
1480         char buf[256];
1481         char *ret_str = NULL;
1482         int compare;
1483         int i;
1484
1485         var = chunk_to_var(expr);
1486         if (!var)
1487                 goto free;
1488
1489         i = -1;
1490         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1491                 i++;
1492                 if (i == ignore)
1493                         continue;
1494                 if (!param->ident)
1495                         continue;
1496                 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1497                 compare = get_comparison_strings(var, buf);
1498                 if (!compare)
1499                         continue;
1500                 if (show_special(compare)[0] != starts_with)
1501                         continue;
1502                 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1503                 ret_str = alloc_sname(buf);
1504                 break;
1505         } END_FOR_EACH_PTR(param);
1506
1507 free:
1508         free_string(var);
1509         return ret_str;
1510 }
1511
1512 char *expr_equal_to_param(struct expression *expr, int ignore)
1513 {
1514         return range_comparison_to_param_helper(expr, '=', ignore);
1515 }
1516
1517 char *expr_lte_to_param(struct expression *expr, int ignore)
1518 {
1519         return range_comparison_to_param_helper(expr, '<', ignore);
1520 }
1521
1522 char *expr_param_comparison(struct expression *expr, int ignore)
1523 {
1524         struct symbol *param;
1525         char *var = NULL;
1526         char buf[256];
1527         char *ret_str = NULL;
1528         int compare;
1529         int i;
1530
1531         var = chunk_to_var(expr);
1532         if (!var)
1533                 goto free;
1534
1535         i = -1;
1536         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1537                 i++;
1538                 if (i == ignore)
1539                         continue;
1540                 if (!param->ident)
1541                         continue;
1542                 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1543                 compare = get_comparison_strings(var, buf);
1544                 if (!compare)
1545                         continue;
1546                 snprintf(buf, sizeof(buf), "[%s$%d]", show_special(compare), i);
1547                 ret_str = alloc_sname(buf);
1548                 break;
1549         } END_FOR_EACH_PTR(param);
1550
1551 free:
1552         free_string(var);
1553         return ret_str;
1554 }
1555
1556 static void free_data(struct symbol *sym)
1557 {
1558         if (__inline_fn)
1559                 return;
1560         clear_compare_data_alloc();
1561 }
1562
1563 void register_comparison(int id)
1564 {
1565         compare_id = id;
1566         add_hook(&match_compare, CONDITION_HOOK);
1567         add_hook(&match_assign, ASSIGNMENT_HOOK);
1568         add_hook(&save_start_states, AFTER_DEF_HOOK);
1569         add_unmatched_state_hook(compare_id, unmatched_comparison);
1570         add_merge_hook(compare_id, &merge_compare_states);
1571         add_hook(&free_data, AFTER_FUNC_HOOK);
1572 }
1573
1574 void register_comparison_links(int id)
1575 {
1576         link_id = id;
1577         add_merge_hook(link_id, &merge_links);
1578         add_modification_hook(link_id, &match_modify);
1579 }
1580
1581 void register_comparison_inc_dec(int id)
1582 {
1583         inc_dec_id = id;
1584         add_modification_hook(inc_dec_id, &iter_modify);
1585 }
1586
1587 void register_comparison_inc_dec_links(int id)
1588 {
1589         inc_dec_link_id = id;
1590         set_up_link_functions(inc_dec_id, inc_dec_link_id);
1591 }