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
  38 struct compare_data {
  39         const char *var1;
  40         struct var_sym_list *vsl1;
  41         int comparison;
  42         const char *var2;
  43         struct var_sym_list *vsl2;
  44 };
  45 ALLOCATOR(compare_data, "compare data");
  46
  47 int chunk_vsl_eq(const char *a, struct var_sym_list *a_vsl, const char *b, struct var_sym_list *b_vsl)
  48 {
  49         if (strcmp(a, b) == 0)
  50                 return 1;
  51         return 0;
  52 }
  53
  54 static struct symbol *vsl_to_sym(struct var_sym_list *vsl)
  55 {
  56         struct var_sym *vs;
  57
  58         if (!vsl)
  59                 return NULL;
  60         if (ptr_list_size((struct ptr_list *)vsl) != 1)
  61                 return NULL;
  62         vs = first_ptr_list((struct ptr_list *)vsl);
  63         return vs->sym;
  64 }
  65
  66 static struct smatch_state *alloc_compare_state(
  67                 const char *var1, struct var_sym_list *vsl1,
  68                 int comparison,
  69                 const char *var2, struct var_sym_list *vsl2)
  70 {
  71         struct smatch_state *state;
  72         struct compare_data *data;
  73
  74         state = __alloc_smatch_state(0);
  75         state->name = alloc_sname(show_special(comparison));
  76         data = __alloc_compare_data(0);
  77         data->var1 = alloc_sname(var1);
  78         data->vsl1 = clone_var_sym_list(vsl1);
  79         data->comparison = comparison;
  80         data->var2 = alloc_sname(var2);
  81         data->vsl2 = clone_var_sym_list(vsl2);
  82         state->data = data;
  83         return state;
  84 }
  85
  86 static int state_to_comparison(struct smatch_state *state)
  87 {
  88         if (!state || !state->data)
  89                 return 0;
  90         return ((struct compare_data *)state->data)->comparison;
  91 }
  92
  93 /*
  94  * flip_op() reverses the op left and right.  So "x >= y" becomes "y <= x".
  95  */
  96 static int flip_op(int op)
  97 {
  98         switch (op) {
  99         case 0:
 100                 return 0;
 101         case '<':
 102                 return '>';
 103         case SPECIAL_UNSIGNED_LT:
 104                 return SPECIAL_UNSIGNED_GT;
 105         case SPECIAL_LTE:
 106                 return SPECIAL_GTE;
 107         case SPECIAL_UNSIGNED_LTE:
 108                 return SPECIAL_UNSIGNED_GTE;
 109         case SPECIAL_EQUAL:
 110                 return SPECIAL_EQUAL;
 111         case SPECIAL_NOTEQUAL:
 112                 return SPECIAL_NOTEQUAL;
 113         case SPECIAL_GTE:
 114                 return SPECIAL_LTE;
 115         case SPECIAL_UNSIGNED_GTE:
 116                 return SPECIAL_UNSIGNED_LTE;
 117         case '>':
 118                 return '<';
 119         case SPECIAL_UNSIGNED_GT:
 120                 return SPECIAL_UNSIGNED_LT;
 121         default:
 122                 sm_msg("internal smatch bug.  unhandled comparison %d", op);
 123                 return op;
 124         }
 125 }
 126
 127 static int falsify_op(int op)
 128 {
 129         switch (op) {
 130         case 0:
 131                 return 0;
 132         case '<':
 133                 return SPECIAL_GTE;
 134         case SPECIAL_UNSIGNED_LT:
 135                 return SPECIAL_UNSIGNED_GTE;
 136         case SPECIAL_LTE:
 137                 return '>';
 138         case SPECIAL_UNSIGNED_LTE:
 139                 return SPECIAL_UNSIGNED_GT;
 140         case SPECIAL_EQUAL:
 141                 return SPECIAL_NOTEQUAL;
 142         case SPECIAL_NOTEQUAL:
 143                 return SPECIAL_EQUAL;
 144         case SPECIAL_GTE:
 145                 return '<';
 146         case SPECIAL_UNSIGNED_GTE:
 147                 return SPECIAL_UNSIGNED_LT;
 148         case '>':
 149                 return SPECIAL_LTE;
 150         case SPECIAL_UNSIGNED_GT:
 151                 return SPECIAL_UNSIGNED_LTE;
 152         default:
 153                 sm_msg("internal smatch bug.  unhandled comparison %d", op);
 154                 return op;
 155         }
 156 }
 157
 158 static int rl_comparison(struct range_list *left_rl, struct range_list *right_rl)
 159 {
 160         sval_t left_min, left_max, right_min, right_max;
 161
 162         if (!left_rl || !right_rl)
 163                 return 0;
 164
 165         left_min = rl_min(left_rl);
 166         left_max = rl_max(left_rl);
 167         right_min = rl_min(right_rl);
 168         right_max = rl_max(right_rl);
 169
 170         if (left_min.value == left_max.value &&
 171             right_min.value == right_max.value &&
 172             left_min.value == right_min.value)
 173                 return SPECIAL_EQUAL;
 174
 175         if (sval_cmp(left_max, right_min) < 0)
 176                 return '<';
 177         if (sval_cmp(left_max, right_min) == 0)
 178                 return SPECIAL_LTE;
 179         if (sval_cmp(left_min, right_max) > 0)
 180                 return '>';
 181         if (sval_cmp(left_min, right_max) == 0)
 182                 return SPECIAL_GTE;
 183
 184         return 0;
 185 }
 186
 187 static struct range_list *get_orig_rl(struct var_sym_list *vsl)
 188 {
 189         struct symbol *sym;
 190         struct smatch_state *state;
 191
 192         if (!vsl)
 193                 return NULL;
 194         sym = vsl_to_sym(vsl);
 195         if (!sym || !sym->ident)
 196                 return NULL;
 197         state = get_orig_estate(sym->ident->name, sym);
 198         return estate_rl(state);
 199 }
 200
 201 static struct smatch_state *unmatched_comparison(struct sm_state *sm)
 202 {
 203         struct compare_data *data = sm->state->data;
 204         struct range_list *left_rl, *right_rl;
 205         int op;
 206
 207         if (!data)
 208                 return &undefined;
 209
 210         if (strstr(data->var1, " orig"))
 211                 left_rl = get_orig_rl(data->vsl1);
 212         else if (!get_implied_rl_var_sym(data->var1, vsl_to_sym(data->vsl1), &left_rl))
 213                 return &undefined;
 214         if (strstr(data->var2, " orig"))
 215                 right_rl = get_orig_rl(data->vsl2);
 216         else if (!get_implied_rl_var_sym(data->var2, vsl_to_sym(data->vsl2), &right_rl))
 217                 return &undefined;
 218
 219
 220         op = rl_comparison(left_rl, right_rl);
 221         if (op)
 222                 return alloc_compare_state(data->var1, data->vsl1, op, data->var2, data->vsl2);
 223
 224         return &undefined;
 225 }
 226
 227 /* remove_unsigned_from_comparison() is obviously a hack. */
 228 static int remove_unsigned_from_comparison(int op)
 229 {
 230         switch (op) {
 231         case SPECIAL_UNSIGNED_LT:
 232                 return '<';
 233         case SPECIAL_UNSIGNED_LTE:
 234                 return SPECIAL_LTE;
 235         case SPECIAL_UNSIGNED_GTE:
 236                 return SPECIAL_GTE;
 237         case SPECIAL_UNSIGNED_GT:
 238                 return '>';
 239         default:
 240                 return op;
 241         }
 242 }
 243
 244 /*
 245  * This is for when you merge states "a < b" and "a == b", the result is that
 246  * we can say for sure, "a <= b" after the merge.
 247  */
 248 static int merge_comparisons(int one, int two)
 249 {
 250         int LT, EQ, GT;
 251
 252         one = remove_unsigned_from_comparison(one);
 253         two = remove_unsigned_from_comparison(two);
 254
 255         LT = EQ = GT = 0;
 256
 257         switch (one) {
 258         case '<':
 259                 LT = 1;
 260                 break;
 261         case SPECIAL_LTE:
 262                 LT = 1;
 263                 EQ = 1;
 264                 break;
 265         case SPECIAL_EQUAL:
 266                 EQ = 1;
 267                 break;
 268         case SPECIAL_GTE:
 269                 GT = 1;
 270                 EQ = 1;
 271                 break;
 272         case '>':
 273                 GT = 1;
 274         }
 275
 276         switch (two) {
 277         case '<':
 278                 LT = 1;
 279                 break;
 280         case SPECIAL_LTE:
 281                 LT = 1;
 282                 EQ = 1;
 283                 break;
 284         case SPECIAL_EQUAL:
 285                 EQ = 1;
 286                 break;
 287         case SPECIAL_GTE:
 288                 GT = 1;
 289                 EQ = 1;
 290                 break;
 291         case '>':
 292                 GT = 1;
 293         }
 294
 295         if (LT && EQ && GT)
 296                 return 0;
 297         if (LT && EQ)
 298                 return SPECIAL_LTE;
 299         if (LT && GT)
 300                 return SPECIAL_NOTEQUAL;
 301         if (LT)
 302                 return '<';
 303         if (EQ && GT)
 304                 return SPECIAL_GTE;
 305         if (GT)
 306                 return '>';
 307         return 0;
 308 }
 309
 310 /*
 311  * This is for if you have "a < b" and "b <= c".  Or in other words,
 312  * "a < b <= c".  You would call this like get_combined_comparison('<', '<=').
 313  * The return comparison would be '<'.
 314  *
 315  * This function is different from merge_comparisons(), for example:
 316  * merge_comparison('<', '==') returns '<='
 317  * get_combined_comparison('<', '==') returns '<'
 318  */
 319 static int combine_comparisons(int left_compare, int right_compare)
 320 {
 321         int LT, EQ, GT;
 322
 323         left_compare = remove_unsigned_from_comparison(left_compare);
 324         right_compare = remove_unsigned_from_comparison(right_compare);
 325
 326         LT = EQ = GT = 0;
 327
 328         switch (left_compare) {
 329         case '<':
 330                 LT++;
 331                 break;
 332         case SPECIAL_LTE:
 333                 LT++;
 334                 EQ++;
 335                 break;
 336         case SPECIAL_EQUAL:
 337                 return right_compare;
 338         case SPECIAL_GTE:
 339                 GT++;
 340                 EQ++;
 341                 break;
 342         case '>':
 343                 GT++;
 344         }
 345
 346         switch (right_compare) {
 347         case '<':
 348                 LT++;
 349                 break;
 350         case SPECIAL_LTE:
 351                 LT++;
 352                 EQ++;
 353                 break;
 354         case SPECIAL_EQUAL:
 355                 return left_compare;
 356         case SPECIAL_GTE:
 357                 GT++;
 358                 EQ++;
 359                 break;
 360         case '>':
 361                 GT++;
 362         }
 363
 364         if (LT == 2) {
 365                 if (EQ == 2)
 366                         return SPECIAL_LTE;
 367                 return '<';
 368         }
 369
 370         if (GT == 2) {
 371                 if (EQ == 2)
 372                         return SPECIAL_GTE;
 373                 return '>';
 374         }
 375         return 0;
 376 }
 377
 378 static struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
 379 {
 380         struct compare_data *data = s1->data;
 381         int op;
 382
 383         op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
 384         if (op)
 385                 return alloc_compare_state(data->var1, data->vsl1, op, data->var2, data->vsl2);
 386         return &undefined;
 387 }
 388
 389 static struct smatch_state *alloc_link_state(struct string_list *links)
 390 {
 391         struct smatch_state *state;
 392         static char buf[256];
 393         char *tmp;
 394         int i;
 395
 396         state = __alloc_smatch_state(0);
 397
 398         i = 0;
 399         FOR_EACH_PTR(links, tmp) {
 400                 if (!i++) {
 401                         snprintf(buf, sizeof(buf), "%s", tmp);
 402                 } else {
 403                         append(buf, ", ", sizeof(buf));
 404                         append(buf, tmp, sizeof(buf));
 405                 }
 406         } END_FOR_EACH_PTR(tmp);
 407
 408         state->name = alloc_sname(buf);
 409         state->data = links;
 410         return state;
 411 }
 412
 413 static void save_start_states(struct statement *stmt)
 414 {
 415         struct symbol *param;
 416         char orig[64];
 417         char state_name[128];
 418         struct smatch_state *state;
 419         struct string_list *links;
 420         char *link;
 421
 422         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
 423                 struct var_sym_list *vsl1 = NULL;
 424                 struct var_sym_list *vsl2 = NULL;
 425
 426                 if (!param->ident)
 427                         continue;
 428                 snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
 429                 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
 430                 add_var_sym(&vsl1, param->ident->name, param);
 431                 add_var_sym(&vsl2, orig, param);
 432                 state = alloc_compare_state(param->ident->name, vsl1, SPECIAL_EQUAL, alloc_sname(orig), vsl2);
 433                 set_state(compare_id, state_name, NULL, state);
 434
 435                 link = alloc_sname(state_name);
 436                 links = NULL;
 437                 insert_string(&links, link);
 438                 state = alloc_link_state(links);
 439                 set_state(link_id, param->ident->name, param, state);
 440         } END_FOR_EACH_PTR(param);
 441 }
 442
 443 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
 444 {
 445         struct smatch_state *ret;
 446         struct string_list *links;
 447
 448         links = combine_string_lists(s1->data, s2->data);
 449         ret = alloc_link_state(links);
 450         return ret;
 451 }
 452
 453 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
 454 {
 455         struct smatch_state *old_state, *new_state;
 456         struct string_list *links;
 457         char *new;
 458
 459         old_state = get_state(link_id, var, sym);
 460         if (old_state)
 461                 links = clone_str_list(old_state->data);
 462         else
 463                 links = NULL;
 464
 465         new = alloc_sname(link);
 466         insert_string(&links, new);
 467
 468         new_state = alloc_link_state(links);
 469         set_state(link_id, var, sym, new_state);
 470 }
 471
 472 static void match_inc(struct sm_state *sm)
 473 {
 474         struct string_list *links;
 475         struct smatch_state *state;
 476         char *tmp;
 477
 478         links = sm->state->data;
 479
 480         FOR_EACH_PTR(links, tmp) {
 481                 state = get_state(compare_id, tmp, NULL);
 482
 483                 switch (state_to_comparison(state)) {
 484                 case SPECIAL_EQUAL:
 485                 case SPECIAL_GTE:
 486                 case SPECIAL_UNSIGNED_GTE:
 487                 case '>':
 488                 case SPECIAL_UNSIGNED_GT: {
 489                         struct compare_data *data = state->data;
 490                         struct smatch_state *new;
 491
 492                         new = alloc_compare_state(data->var1, data->vsl1, '>', data->var2, data->vsl2);
 493                         set_state(compare_id, tmp, NULL, new);
 494                         break;
 495                         }
 496                 default:
 497                         set_state(compare_id, tmp, NULL, &undefined);
 498                 }
 499         } END_FOR_EACH_PTR(tmp);
 500 }
 501
 502 static void match_dec(struct sm_state *sm)
 503 {
 504         struct string_list *links;
 505         struct smatch_state *state;
 506         char *tmp;
 507
 508         links = sm->state->data;
 509
 510         FOR_EACH_PTR(links, tmp) {
 511                 state = get_state(compare_id, tmp, NULL);
 512
 513                 switch (state_to_comparison(state)) {
 514                 case SPECIAL_EQUAL:
 515                 case SPECIAL_LTE:
 516                 case SPECIAL_UNSIGNED_LTE:
 517                 case '<':
 518                 case SPECIAL_UNSIGNED_LT: {
 519                         struct compare_data *data = state->data;
 520                         struct smatch_state *new;
 521
 522                         new = alloc_compare_state(data->var1, data->vsl1, '<', data->var2, data->vsl2);
 523                         set_state(compare_id, tmp, NULL, new);
 524                         break;
 525                         }
 526                 default:
 527                         set_state(compare_id, tmp, NULL, &undefined);
 528                 }
 529         } END_FOR_EACH_PTR(tmp);
 530 }
 531
 532 static int match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
 533 {
 534         if (!mod_expr)
 535                 return 0;
 536         if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
 537                 return 0;
 538
 539         if (mod_expr->op == SPECIAL_INCREMENT) {
 540                 match_inc(sm);
 541                 return 1;
 542         }
 543         if (mod_expr->op == SPECIAL_DECREMENT) {
 544                 match_dec(sm);
 545                 return 1;
 546         }
 547         return 0;
 548 }
 549
 550 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
 551 {
 552         struct string_list *links;
 553         char *tmp;
 554
 555         /* Huh???  This needs a comment!  */
 556         if (match_inc_dec(sm, mod_expr))
 557                 return;
 558
 559         links = sm->state->data;
 560
 561         FOR_EACH_PTR(links, tmp) {
 562                 set_state(compare_id, tmp, NULL, &undefined);
 563         } END_FOR_EACH_PTR(tmp);
 564         set_state(link_id, sm->name, sm->sym, &undefined);
 565 }
 566
 567 static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym)
 568 {
 569         char *name, *left_name, *right_name;
 570         struct symbol *tmp;
 571         char buf[128];
 572
 573         expr = strip_expr(expr);
 574         if (!expr)
 575                 return NULL;
 576         if (sym)
 577                 *sym = NULL;
 578
 579         name = expr_to_var_sym(expr, &tmp);
 580         if (name && tmp) {
 581                 if (sym)
 582                         *sym = tmp;
 583                 return name;
 584         }
 585         if (name)
 586                 free_string(name);
 587
 588         if (expr->type != EXPR_BINOP)
 589                 return NULL;
 590         if (expr->op != '-' && expr->op != '+')
 591                 return NULL;
 592
 593         left_name = expr_to_var(expr->left);
 594         if (!left_name)
 595                 return NULL;
 596         right_name = expr_to_var(expr->right);
 597         if (!right_name) {
 598                 free_string(left_name);
 599                 return NULL;
 600         }
 601         snprintf(buf, sizeof(buf), "%s %s %s", left_name, show_special(expr->op), right_name);
 602         free_string(left_name);
 603         free_string(right_name);
 604         return alloc_string(buf);
 605 }
 606
 607 static char *chunk_to_var(struct expression *expr)
 608 {
 609         return chunk_to_var_sym(expr, NULL);
 610 }
 611
 612 static void save_link(struct expression *expr, char *link)
 613 {
 614         char *var;
 615         struct symbol *sym;
 616
 617         expr = strip_expr(expr);
 618         if (expr->type == EXPR_BINOP) {
 619                 char *chunk;
 620
 621                 chunk = chunk_to_var(expr);
 622                 if (!chunk)
 623                         return;
 624
 625                 save_link(expr->left, link);
 626                 save_link(expr->right, link);
 627                 save_link_var_sym(chunk, NULL, link);
 628                 return;
 629         }
 630
 631         var = expr_to_var_sym(expr, &sym);
 632         if (!var || !sym)
 633                 goto done;
 634
 635         save_link_var_sym(var, sym, link);
 636 done:
 637         free_string(var);
 638 }
 639
 640 static void update_tf_links(struct stree *pre_stree,
 641                             const char *left_var, struct var_sym_list *left_vsl,
 642                             int left_comparison,
 643                             const char *mid_var, struct var_sym_list *mid_vsl,
 644                             struct string_list *links)
 645 {
 646         struct smatch_state *state;
 647         struct smatch_state *true_state, *false_state;
 648         struct compare_data *data;
 649         const char *right_var;
 650         struct var_sym_list *right_vsl;
 651         int right_comparison;
 652         int true_comparison;
 653         int false_comparison;
 654         char *tmp;
 655         char state_name[256];
 656         struct var_sym *vs;
 657
 658         FOR_EACH_PTR(links, tmp) {
 659                 state = get_state_stree(pre_stree, compare_id, tmp, NULL);
 660                 if (!state || !state->data)
 661                         continue;
 662                 data = state->data;
 663                 right_comparison = data->comparison;
 664                 right_var = data->var2;
 665                 right_vsl = data->vsl2;
 666                 if (chunk_vsl_eq(mid_var, mid_vsl, right_var, right_vsl)) {
 667                         right_var = data->var1;
 668                         right_vsl = data->vsl1;
 669                         right_comparison = flip_op(right_comparison);
 670                 }
 671                 true_comparison = combine_comparisons(left_comparison, right_comparison);
 672                 false_comparison = combine_comparisons(falsify_op(left_comparison), right_comparison);
 673
 674                 if (strcmp(left_var, right_var) > 0) {
 675                         const char *tmp_var = left_var;
 676                         struct var_sym_list *tmp_vsl = left_vsl;
 677
 678                         left_var = right_var;
 679                         left_vsl = right_vsl;
 680                         right_var = tmp_var;
 681                         right_vsl = tmp_vsl;
 682                         true_comparison = flip_op(true_comparison);
 683                         false_comparison = flip_op(false_comparison);
 684                 }
 685
 686                 if (!true_comparison && !false_comparison)
 687                         continue;
 688
 689                 if (true_comparison)
 690                         true_state = alloc_compare_state(left_var, left_vsl, true_comparison, right_var, right_vsl);
 691                 else
 692                         true_state = NULL;
 693                 if (false_comparison)
 694                         false_state = alloc_compare_state(left_var, left_vsl, false_comparison, right_var, right_vsl);
 695                 else
 696                         false_state = NULL;
 697
 698                 snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
 699                 set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
 700                 FOR_EACH_PTR(left_vsl, vs) {
 701                         save_link_var_sym(vs->var, vs->sym, state_name);
 702                 } END_FOR_EACH_PTR(vs);
 703                 FOR_EACH_PTR(right_vsl, vs) {
 704                         save_link_var_sym(vs->var, vs->sym, state_name);
 705                 } END_FOR_EACH_PTR(vs);
 706                 if (!vsl_to_sym(left_vsl))
 707                         save_link_var_sym(left_var, NULL, state_name);
 708                 if (!vsl_to_sym(right_vsl))
 709                         save_link_var_sym(right_var, NULL, state_name);
 710         } END_FOR_EACH_PTR(tmp);
 711 }
 712
 713 static void update_tf_data(struct stree *pre_stree,
 714                 const char *left_name, struct symbol *left_sym,
 715                 const char *right_name, struct symbol *right_sym,
 716                 struct compare_data *tdata)
 717 {
 718         struct smatch_state *state;
 719
 720         state = get_state_stree(pre_stree, link_id, tdata->var2, vsl_to_sym(tdata->vsl2));
 721         if (state)
 722                 update_tf_links(pre_stree, tdata->var1, tdata->vsl1, tdata->comparison, tdata->var2, tdata->vsl2, state->data);
 723
 724         state = get_state_stree(pre_stree, link_id, tdata->var1, vsl_to_sym(tdata->vsl1));
 725         if (state)
 726                 update_tf_links(pre_stree, tdata->var2, tdata->vsl2, flip_op(tdata->comparison), tdata->var1, tdata->vsl1, state->data);
 727 }
 728
 729 static void match_compare(struct expression *expr)
 730 {
 731         char *left = NULL;
 732         char *right = NULL;
 733         struct symbol *left_sym, *right_sym;
 734         struct var_sym_list *left_vsl, *right_vsl;
 735         int op, false_op;
 736         struct smatch_state *true_state, *false_state;
 737         char state_name[256];
 738         struct stree *pre_stree;
 739
 740         if (expr->type != EXPR_COMPARE)
 741                 return;
 742         left = chunk_to_var_sym(expr->left, &left_sym);
 743         if (!left)
 744                 goto free;
 745         left_vsl = expr_to_vsl(expr->left);
 746         right = chunk_to_var_sym(expr->right, &right_sym);
 747         if (!right)
 748                 goto free;
 749         right_vsl = expr_to_vsl(expr->right);
 750
 751         if (strcmp(left, right) > 0) {
 752                 struct symbol *tmp_sym = left_sym;
 753                 char *tmp_name = left;
 754                 struct var_sym_list *tmp_vsl = left_vsl;
 755
 756                 left = right;
 757                 left_sym = right_sym;
 758                 left_vsl = right_vsl;
 759                 right = tmp_name;
 760                 right_sym = tmp_sym;
 761                 right_vsl = tmp_vsl;
 762                 op = flip_op(expr->op);
 763         } else {
 764                 op = expr->op;
 765         }
 766         false_op = falsify_op(op);
 767         snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
 768         true_state = alloc_compare_state(left, left_vsl, op, right, right_vsl);
 769         false_state = alloc_compare_state(left, left_vsl, false_op, right, right_vsl);
 770
 771         pre_stree = clone_stree(__get_cur_stree());
 772         update_tf_data(pre_stree, left, left_sym, right, right_sym, true_state->data);
 773         free_stree(&pre_stree);
 774
 775         set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
 776         save_link(expr->left, state_name);
 777         save_link(expr->right, state_name);
 778 free:
 779         free_string(left);
 780         free_string(right);
 781 }
 782
 783 static void add_comparison_var_sym(const char *left_name,
 784                 struct var_sym_list *left_vsl,
 785                 int comparison,
 786                 const char *right_name, struct var_sym_list *right_vsl)
 787 {
 788         struct smatch_state *state;
 789         struct var_sym *vs;
 790         char state_name[256];
 791
 792         if (strcmp(left_name, right_name) > 0) {
 793                 const char *tmp_name = left_name;
 794                 struct var_sym_list *tmp_vsl = left_vsl;
 795
 796                 left_name = right_name;
 797                 left_vsl = right_vsl;
 798                 right_name = tmp_name;
 799                 right_vsl = tmp_vsl;
 800                 comparison = flip_op(comparison);
 801         }
 802         snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
 803         state = alloc_compare_state(left_name, left_vsl, comparison, right_name, right_vsl);
 804
 805         set_state(compare_id, state_name, NULL, state);
 806
 807         FOR_EACH_PTR(left_vsl, vs) {
 808                 save_link_var_sym(vs->var, vs->sym, state_name);
 809         } END_FOR_EACH_PTR(vs);
 810         FOR_EACH_PTR(right_vsl, vs) {
 811                 save_link_var_sym(vs->var, vs->sym, state_name);
 812         } END_FOR_EACH_PTR(vs);
 813 }
 814
 815 static void add_comparison(struct expression *left, int comparison, struct expression *right)
 816 {
 817         char *left_name = NULL;
 818         char *right_name = NULL;
 819         struct symbol *left_sym, *right_sym;
 820         struct var_sym_list *left_vsl, *right_vsl;
 821         struct smatch_state *state;
 822         char state_name[256];
 823
 824         left_name = chunk_to_var_sym(left, &left_sym);
 825         if (!left_name)
 826                 goto free;
 827         left_vsl = expr_to_vsl(left);
 828         right_name = chunk_to_var_sym(right, &right_sym);
 829         if (!right_name)
 830                 goto free;
 831         right_vsl = expr_to_vsl(right);
 832
 833         if (strcmp(left_name, right_name) > 0) {
 834                 struct symbol *tmp_sym = left_sym;
 835                 char *tmp_name = left_name;
 836                 struct var_sym_list *tmp_vsl = left_vsl;
 837
 838                 left_name = right_name;
 839                 left_sym = right_sym;
 840                 left_vsl = right_vsl;
 841                 right_name = tmp_name;
 842                 right_sym = tmp_sym;
 843                 right_vsl = tmp_vsl;
 844                 comparison = flip_op(comparison);
 845         }
 846         snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
 847         state = alloc_compare_state(left_name, left_vsl, comparison, right_name, right_vsl);
 848
 849         set_state(compare_id, state_name, NULL, state);
 850         save_link(left, state_name);
 851         save_link(right, state_name);
 852
 853 free:
 854         free_string(left_name);
 855         free_string(right_name);
 856 }
 857
 858 static void match_assign_add(struct expression *expr)
 859 {
 860         struct expression *right;
 861         struct expression *r_left, *r_right;
 862         sval_t left_tmp, right_tmp;
 863
 864         right = strip_expr(expr->right);
 865         r_left = strip_expr(right->left);
 866         r_right = strip_expr(right->right);
 867
 868         get_absolute_min(r_left, &left_tmp);
 869         get_absolute_min(r_right, &right_tmp);
 870
 871         if (left_tmp.value > 0)
 872                 add_comparison(expr->left, '>', r_right);
 873         else if (left_tmp.value == 0)
 874                 add_comparison(expr->left, SPECIAL_GTE, r_right);
 875
 876         if (right_tmp.value > 0)
 877                 add_comparison(expr->left, '>', r_left);
 878         else if (right_tmp.value == 0)
 879                 add_comparison(expr->left, SPECIAL_GTE, r_left);
 880 }
 881
 882 static void match_assign_sub(struct expression *expr)
 883 {
 884         struct expression *right;
 885         struct expression *r_left, *r_right;
 886         int comparison;
 887         sval_t min;
 888
 889         right = strip_expr(expr->right);
 890         r_left = strip_expr(right->left);
 891         r_right = strip_expr(right->right);
 892
 893         if (get_absolute_min(r_right, &min) && sval_is_negative(min))
 894                 return;
 895
 896         comparison = get_comparison(r_left, r_right);
 897
 898         switch (comparison) {
 899         case '>':
 900         case SPECIAL_GTE:
 901                 if (implied_not_equal(r_right, 0))
 902                         add_comparison(expr->left, '>', r_left);
 903                 else
 904                         add_comparison(expr->left, SPECIAL_GTE, r_left);
 905                 return;
 906         }
 907 }
 908
 909 static void match_assign_divide(struct expression *expr)
 910 {
 911         struct expression *right;
 912         struct expression *r_left, *r_right;
 913         sval_t min;
 914
 915         right = strip_expr(expr->right);
 916         r_left = strip_expr(right->left);
 917         r_right = strip_expr(right->right);
 918         if (!get_implied_min(r_right, &min) || min.value <= 1)
 919                 return;
 920
 921         add_comparison(expr->left, '<', r_left);
 922 }
 923
 924 static void match_binop_assign(struct expression *expr)
 925 {
 926         struct expression *right;
 927
 928         right = strip_expr(expr->right);
 929         if (right->op == '+')
 930                 match_assign_add(expr);
 931         if (right->op == '-')
 932                 match_assign_sub(expr);
 933         if (right->op == '/')
 934                 match_assign_divide(expr);
 935 }
 936
 937 static void copy_comparisons(struct expression *left, struct expression *right)
 938 {
 939         struct string_list *links;
 940         struct smatch_state *state;
 941         struct compare_data *data;
 942         struct symbol *left_sym, *right_sym;
 943         char *left_var = NULL;
 944         char *right_var = NULL;
 945         struct var_sym_list *left_vsl;
 946         const char *var;
 947         struct var_sym_list *vsl;
 948         int comparison;
 949         char *tmp;
 950
 951         left_var = chunk_to_var_sym(left, &left_sym);
 952         if (!left_var)
 953                 goto done;
 954         left_vsl = expr_to_vsl(left);
 955         right_var = chunk_to_var_sym(right, &right_sym);
 956         if (!right_var)
 957                 goto done;
 958
 959         state = get_state(link_id, right_var, right_sym);
 960         if (!state)
 961                 return;
 962         links = state->data;
 963
 964         FOR_EACH_PTR(links, tmp) {
 965                 state = get_state(compare_id, tmp, NULL);
 966                 if (!state || !state->data)
 967                         continue;
 968                 data = state->data;
 969                 comparison = data->comparison;
 970                 var = data->var2;
 971                 vsl = data->vsl2;
 972                 if (chunk_vsl_eq(var, vsl, right_var, NULL)) {
 973                         var = data->var1;
 974                         vsl = data->vsl1;
 975                         comparison = flip_op(comparison);
 976                 }
 977                 add_comparison_var_sym(left_var, left_vsl, comparison, var, vsl);
 978         } END_FOR_EACH_PTR(tmp);
 979
 980 done:
 981         free_string(right_var);
 982 }
 983
 984 static void match_assign(struct expression *expr)
 985 {
 986         struct expression *right;
 987
 988         if (expr->op != '=')
 989                 return;
 990
 991         if (is_struct(expr->left))
 992                 return;
 993
 994         copy_comparisons(expr->left, expr->right);
 995         add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
 996
 997         right = strip_expr(expr->right);
 998         if (right->type == EXPR_BINOP)
 999                 match_binop_assign(expr);
1000 }
1001
1002 int get_comparison_strings(const char *one, const char *two)
1003 {
1004         char buf[256];
1005         struct smatch_state *state;
1006         int invert = 0;
1007         int ret = 0;
1008
1009         if (strcmp(one, two) > 0) {
1010                 const char *tmp = one;
1011
1012                 one = two;
1013                 two = tmp;
1014                 invert = 1;
1015         }
1016
1017         snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1018         state = get_state(compare_id, buf, NULL);
1019         if (state)
1020                 ret = state_to_comparison(state);
1021
1022         if (invert)
1023                 ret = flip_op(ret);
1024
1025         return ret;
1026 }
1027
1028 int get_comparison(struct expression *a, struct expression *b)
1029 {
1030         char *one = NULL;
1031         char *two = NULL;
1032         int ret = 0;
1033
1034         one = chunk_to_var(a);
1035         if (!one)
1036                 goto free;
1037         two = chunk_to_var(b);
1038         if (!two)
1039                 goto free;
1040
1041         ret = get_comparison_strings(one, two);
1042 free:
1043         free_string(one);
1044         free_string(two);
1045         return ret;
1046 }
1047
1048 static void update_links_from_call(struct expression *left,
1049                                    int left_compare,
1050                                    struct expression *right)
1051 {
1052         struct string_list *links;
1053         struct smatch_state *state;
1054         struct compare_data *data;
1055         struct symbol *left_sym, *right_sym;
1056         char *left_var = NULL;
1057         char *right_var = NULL;
1058         struct var_sym_list *left_vsl;
1059         const char *var;
1060         struct var_sym_list *vsl;
1061         int comparison;
1062         char *tmp;
1063
1064         left_var = chunk_to_var_sym(left, &left_sym);
1065         if (!left_var)
1066                 goto done;
1067         left_vsl = expr_to_vsl(left);
1068         right_var = chunk_to_var_sym(right, &right_sym);
1069         if (!right_var)
1070                 goto done;
1071
1072         state = get_state(link_id, right_var, right_sym);
1073         if (!state)
1074                 return;
1075         links = state->data;
1076
1077         FOR_EACH_PTR(links, tmp) {
1078                 state = get_state(compare_id, tmp, NULL);
1079                 if (!state || !state->data)
1080                         continue;
1081                 data = state->data;
1082                 comparison = data->comparison;
1083                 var = data->var2;
1084                 vsl = data->vsl2;
1085                 if (chunk_vsl_eq(var, vsl, right_var, NULL)) {
1086                         var = data->var1;
1087                         vsl = data->vsl1;
1088                         comparison = flip_op(comparison);
1089                 }
1090                 comparison = combine_comparisons(left_compare, comparison);
1091                 if (!comparison)
1092                         continue;
1093                 add_comparison_var_sym(left_var, left_vsl, comparison, var, vsl);
1094         } END_FOR_EACH_PTR(tmp);
1095
1096 done:
1097         free_string(right_var);
1098 }
1099
1100 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
1101 {
1102         struct expression *arg;
1103         int comparison;
1104         const char *c = range;
1105
1106         if (!str_to_comparison_arg(c, call, &comparison, &arg))
1107                 return;
1108         update_links_from_call(expr, comparison, arg);
1109         add_comparison(expr, comparison, arg);
1110 }
1111
1112 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with)
1113 {
1114         struct symbol *param;
1115         char *var = NULL;
1116         char buf[256];
1117         char *ret_str = NULL;
1118         int compare;
1119         int i;
1120
1121         var = chunk_to_var(expr);
1122         if (!var)
1123                 goto free;
1124
1125         i = -1;
1126         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1127                 i++;
1128                 if (!param->ident)
1129                         continue;
1130                 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1131                 compare = get_comparison_strings(var, buf);
1132                 if (!compare)
1133                         continue;
1134                 if (show_special(compare)[0] != starts_with)
1135                         continue;
1136                 snprintf(buf, sizeof(buf), "[%sp%d]", show_special(compare), i);
1137                 ret_str = alloc_sname(buf);
1138                 break;
1139         } END_FOR_EACH_PTR(param);
1140
1141 free:
1142         free_string(var);
1143         return ret_str;
1144 }
1145
1146 char *expr_equal_to_param(struct expression *expr)
1147 {
1148         return range_comparison_to_param_helper(expr, '=');
1149 }
1150
1151 char *expr_lte_to_param(struct expression *expr)
1152 {
1153         return range_comparison_to_param_helper(expr, '<');
1154 }
1155
1156 static void free_data(struct symbol *sym)
1157 {
1158         if (__inline_fn)
1159                 return;
1160         clear_compare_data_alloc();
1161 }
1162
1163 void register_comparison(int id)
1164 {
1165         compare_id = id;
1166         add_hook(&match_compare, CONDITION_HOOK);
1167         add_hook(&match_assign, ASSIGNMENT_HOOK);
1168         add_hook(&save_start_states, AFTER_DEF_HOOK);
1169         add_unmatched_state_hook(compare_id, unmatched_comparison);
1170         add_merge_hook(compare_id, &merge_compare_states);
1171         add_hook(&free_data, AFTER_FUNC_HOOK);
1172 }
1173
1174 void register_comparison_links(int id)
1175 {
1176         link_id = id;
1177         add_merge_hook(link_id, &merge_links);
1178         add_modification_hook(link_id, &match_modify);
1179 }