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