smatch_comparison.c

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