smatch_conditions.c

   1 /*
   2  * Copyright (C) 2006,2008 Dan Carpenter.
   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 simplest type of condition is
  20  * if (a) { ...
  21  *
  22  * The next simplest kind of conditions is
  23  * if (a && b) { c;
  24  * In that case 'a' is true when we get to 'b' and both are true
  25  * when we get to c.
  26  *
  27  * Or's are a little more complicated.
  28  * if (a || b) { c;
  29  * We know 'a' is not true when we get to 'b' but it may be true
  30  * when we get to c.
  31  *
  32  * If we mix and's and or's that's even more complicated.
  33  * if (a && b && c || a && d) { d ;
  34  * 'a' is true when we evaluate 'b', and 'd'.
  35  * 'b' is true when we evaluate 'c' but otherwise we don't.
  36  *
  37  * The other thing that complicates matters is if we negate
  38  * some if conditions.
  39  * if (!a) { ...
  40  * Smatch has passes the un-negated version to the client and flip
  41  * the true and false values internally.  This makes it easier
  42  * to write checks.
  43  *
  44  * And negations can be part of a compound.
  45  * if (a && !(b || c)) { d;
  46  * In that situation we multiply the negative through to simplify
  47  * stuff so that we can remove the parens like this:
  48  * if (a && !b && !c) { d;
  49  *
  50  * One other thing is that:
  51  * if ((a) != 0){ ...
  52  * that's basically the same as testing for just 'a' and we simplify
  53  * comparisons with zero before passing it to the script.
  54  *
  55  */
  56
  57 #include "smatch.h"
  58 #include "smatch_slist.h"
  59 #include "smatch_extra.h"
  60 #include "smatch_expression_stacks.h"
  61
  62 extern int __expr_stmt_count;
  63
  64 static void split_conditions(struct expression *expr);
  65
  66 static int is_logical_and(struct expression *expr)
  67 {
  68         if (expr->op == SPECIAL_LOGICAL_AND)
  69                 return 1;
  70         return 0;
  71 }
  72
  73 static int handle_zero_comparisons(struct expression *expr)
  74 {
  75         struct expression *tmp = NULL;
  76
  77         // if left is zero or right is zero
  78         if (is_zero(expr->left))
  79                 tmp = expr->right;
  80         else if (is_zero(expr->right))
  81                 tmp = expr->left;
  82         else
  83                 return 0;
  84
  85         // "if (foo != 0)" is the same as "if (foo)"
  86         if (expr->op == SPECIAL_NOTEQUAL) {
  87                 split_conditions(tmp);
  88                 return 1;
  89         }
  90
  91         // "if (foo == 0)" is the same as "if (!foo)"
  92         if (expr->op == SPECIAL_EQUAL) {
  93                 split_conditions(tmp);
  94                 __negate_cond_stacks();
  95                 return 1;
  96         }
  97
  98         return 0;
  99 }
 100
 101 /*
 102  * This function is for handling calls to likely/unlikely
 103  */
 104
 105 static int ignore_builtin_expect(struct expression *expr)
 106 {
 107         if (sym_name_is("__builtin_expect", expr->fn)) {
 108                 split_conditions(first_ptr_list((struct ptr_list *) expr->args));
 109                 return 1;
 110         }
 111         return 0;
 112 }
 113
 114 /*
 115  * handle_compound_stmt() is for: foo = ({blah; blah; blah; 1})
 116  */
 117
 118 static void handle_compound_stmt(struct statement *stmt)
 119 {
 120         struct expression *expr = NULL;
 121         struct statement *last;
 122         struct statement *s;
 123
 124         last = last_ptr_list((struct ptr_list *)stmt->stmts);
 125         if (last->type != STMT_EXPRESSION)
 126                 last = NULL;
 127         else
 128                 expr = last->expression;
 129
 130         FOR_EACH_PTR(stmt->stmts, s) {
 131                 if (s != last)
 132                         __split_stmt(s);
 133         } END_FOR_EACH_PTR(s);
 134         split_conditions(expr);
 135         return;
 136 }
 137
 138 static int handle_preop(struct expression *expr)
 139 {
 140         struct statement *stmt;
 141
 142         if (expr->op == '!') {
 143                 split_conditions(expr->unop);
 144                 __negate_cond_stacks();
 145                 return 1;
 146         }
 147         stmt = get_expression_statement(expr);
 148         if (stmt) {
 149                 handle_compound_stmt(stmt);
 150                 return 1;
 151         }
 152         return 0;
 153 }
 154
 155 static void handle_logical(struct expression *expr)
 156 {
 157         /*
 158          * If we come to an "and" expr then:
 159          * We split the left side.
 160          * We keep all the current states.
 161          * We split the right side.
 162          * We keep all the states from both true sides.
 163          *
 164          * If it's an "or" expr then:
 165          * We save the current slist.
 166          * We split the left side.
 167          * We use the false states for the right side.
 168          * We split the right side.
 169          * We save all the states that are the same on both sides.
 170          */
 171
 172         split_conditions(expr->left);
 173         __process_post_op_stack();
 174
 175         if (!is_logical_and(expr))
 176                 __use_cond_false_states();
 177
 178         __push_cond_stacks();
 179
 180         __save_pre_cond_states();
 181         split_conditions(expr->right);
 182         __process_post_op_stack();
 183         __discard_pre_cond_states();
 184
 185         if (is_logical_and(expr))
 186                 __and_cond_states();
 187         else
 188                 __or_cond_states();
 189
 190         __use_cond_true_states();
 191 }
 192
 193 static struct stree *combine_strees(struct stree *orig, struct stree *fake, struct stree *new)
 194 {
 195         struct stree *ret = NULL;
 196
 197         overwrite_stree(orig, &ret);
 198         overwrite_stree(fake, &ret);
 199         overwrite_stree(new, &ret);
 200         free_stree(&new);
 201
 202         return ret;
 203 }
 204
 205 /*
 206  * handle_select()
 207  * if ((aaa()?bbb():ccc())) { ...
 208  *
 209  * This is almost the same as:
 210  * if ((aaa() && bbb()) || (!aaa() && ccc())) { ...
 211  *
 212  * It's a bit complicated because we shouldn't pass aaa()
 213  * to the clients more than once.
 214  */
 215
 216 static void handle_select(struct expression *expr)
 217 {
 218         struct stree *a_T = NULL;
 219         struct stree *a_F = NULL;
 220         struct stree *a_T_b_T = NULL;
 221         struct stree *a_T_b_F = NULL;
 222         struct stree *a_T_b_fake = NULL;
 223         struct stree *a_F_c_T = NULL;
 224         struct stree *a_F_c_F = NULL;
 225         struct stree *a_F_c_fake = NULL;
 226         struct stree *tmp;
 227         struct sm_state *sm;
 228
 229         /*
 230          * Imagine we have this:  if (a ? b : c) { ...
 231          *
 232          * The condition is true if "a" is true and "b" is true or
 233          * "a" is false and "c" is true.  It's false if "a" is true
 234          * and "b" is false or "a" is false and "c" is false.
 235          *
 236          * The variable name "a_T_b_T" stands for "a true b true" etc.
 237          *
 238          * But if we know "b" is true then we can simpilify things.
 239          * The condition is true if "a" is true or if "a" is false and
 240          * "c" is true.  The only way the condition can be false is if
 241          * "a" is false and "c" is false.
 242          *
 243          * The remaining thing is the "a_T_b_fake".  When we simplify
 244          * the equations we have to take into consideration that other
 245          * states may have changed that don't play into the true false
 246          * equation.  Take the following example:
 247          * if ({
 248          *         (flags) = __raw_local_irq_save();
 249          *         _spin_trylock(lock) ? 1 :
 250          *                 ({ raw_local_irq_restore(flags);  0; });
 251          *    })
 252          * Smatch has to record that the irq flags were restored on the
 253          * false path.
 254          *
 255          */
 256
 257         __save_pre_cond_states();
 258
 259         split_conditions(expr->conditional);
 260
 261         a_T = __copy_cond_true_states();
 262         a_F = __copy_cond_false_states();
 263
 264         __push_cond_stacks();
 265         __push_fake_cur_stree();
 266         split_conditions(expr->cond_true);
 267         __process_post_op_stack();
 268         a_T_b_fake = __pop_fake_cur_stree();
 269         a_T_b_T = combine_strees(a_T, a_T_b_fake, __pop_cond_true_stack());
 270         a_T_b_F = combine_strees(a_T, a_T_b_fake, __pop_cond_false_stack());
 271
 272         __use_cond_false_states();
 273
 274         __push_cond_stacks();
 275         __push_fake_cur_stree();
 276         split_conditions(expr->cond_false);
 277         a_F_c_fake = __pop_fake_cur_stree();
 278         a_F_c_T = combine_strees(a_F, a_F_c_fake, __pop_cond_true_stack());
 279         a_F_c_F = combine_strees(a_F, a_F_c_fake, __pop_cond_false_stack());
 280
 281         /* We have to restore the pre condition states so that
 282            implied_condition_true() will use the right cur_stree */
 283         __use_pre_cond_states();
 284
 285         if (implied_condition_true(expr->cond_true)) {
 286                 free_stree(&a_T_b_T);
 287                 free_stree(&a_T_b_F);
 288                 a_T_b_T = clone_stree(a_T);
 289                 overwrite_stree(a_T_b_fake, &a_T_b_T);
 290         }
 291         if (implied_condition_false(expr->cond_true)) {
 292                 free_stree(&a_T_b_T);
 293                 free_stree(&a_T_b_F);
 294                 a_T_b_F = clone_stree(a_T);
 295                 overwrite_stree(a_T_b_fake, &a_T_b_F);
 296         }
 297         if (implied_condition_true(expr->cond_false)) {
 298                 free_stree(&a_F_c_T);
 299                 free_stree(&a_F_c_F);
 300                 a_F_c_T = clone_stree(a_F);
 301                 overwrite_stree(a_F_c_fake, &a_F_c_T);
 302         }
 303         if (implied_condition_false(expr->cond_false)) {
 304                 free_stree(&a_F_c_T);
 305                 free_stree(&a_F_c_F);
 306                 a_F_c_F = clone_stree(a_F);
 307                 overwrite_stree(a_F_c_fake, &a_F_c_F);
 308         }
 309
 310         merge_stree(&a_T_b_T, a_F_c_T);
 311         merge_stree(&a_T_b_F, a_F_c_F);
 312
 313         tmp = __pop_cond_true_stack();
 314         free_stree(&tmp);
 315         tmp = __pop_cond_false_stack();
 316         free_stree(&tmp);
 317
 318         __push_cond_stacks();
 319         FOR_EACH_SM(a_T_b_T, sm) {
 320                 __set_true_false_sm(sm, NULL);
 321         } END_FOR_EACH_SM(sm);
 322         FOR_EACH_SM(a_T_b_F, sm) {
 323                 __set_true_false_sm(NULL, sm);
 324         } END_FOR_EACH_SM(sm);
 325
 326         free_stree(&a_T_b_fake);
 327         free_stree(&a_F_c_fake);
 328         free_stree(&a_F_c_T);
 329         free_stree(&a_F_c_F);
 330         free_stree(&a_T_b_T);
 331         free_stree(&a_T_b_F);
 332         free_stree(&a_T);
 333         free_stree(&a_F);
 334 }
 335
 336 static void handle_comma(struct expression *expr)
 337 {
 338         __split_expr(expr->left);
 339         split_conditions(expr->right);
 340 }
 341
 342 static int make_op_unsigned(int op)
 343 {
 344         switch (op) {
 345         case '<':
 346                 return SPECIAL_UNSIGNED_LT;
 347         case SPECIAL_LTE:
 348                 return SPECIAL_UNSIGNED_LTE;
 349         case '>':
 350                 return SPECIAL_UNSIGNED_GT;
 351         case SPECIAL_GTE:
 352                 return SPECIAL_UNSIGNED_GTE;
 353         }
 354         return op;
 355 }
 356
 357 static void hackup_unsigned_compares(struct expression *expr)
 358 {
 359         if (expr->type != EXPR_COMPARE)
 360                 return;
 361
 362         if (type_unsigned(get_type(expr)))
 363                 expr->op = make_op_unsigned(expr->op);
 364 }
 365
 366 static void split_conditions(struct expression *expr)
 367 {
 368         if (option_debug) {
 369                 char *cond = expr_to_str(expr);
 370
 371                 sm_msg("%d in split_conditions (%s)", get_lineno(), cond);
 372                 free_string(cond);
 373         }
 374
 375         expr = strip_expr(expr);
 376         if (!expr)
 377                 return;
 378
 379         switch (expr->type) {
 380         case EXPR_LOGICAL:
 381                 __pass_to_client(expr, LOGIC_HOOK);
 382                 handle_logical(expr);
 383                 return;
 384         case EXPR_COMPARE:
 385                 hackup_unsigned_compares(expr);
 386                 if (handle_zero_comparisons(expr))
 387                         return;
 388                 break;
 389         case EXPR_CALL:
 390                 if (ignore_builtin_expect(expr))
 391                         return;
 392                 break;
 393         case EXPR_PREOP:
 394                 if (handle_preop(expr))
 395                         return;
 396                 break;
 397         case EXPR_CONDITIONAL:
 398         case EXPR_SELECT:
 399                 handle_select(expr);
 400                 return;
 401         case EXPR_COMMA:
 402                 handle_comma(expr);
 403                 return;
 404         }
 405
 406         /* fixme: this should be in smatch_flow.c
 407            but because of the funny stuff we do with conditions
 408            it's awkward to put it there.  We would need to
 409            call CONDITION_HOOK in smatch_flow as well.
 410         */
 411         push_expression(&big_expression_stack, expr);
 412         if (expr->type == EXPR_COMPARE) {
 413                 if (expr->left->type != EXPR_POSTOP)
 414                         __split_expr(expr->left);
 415                 if (expr->right->type != EXPR_POSTOP)
 416                         __split_expr(expr->right);
 417         } else if (expr->type != EXPR_POSTOP) {
 418                 __split_expr(expr);
 419         }
 420         __pass_to_client(expr, CONDITION_HOOK);
 421         if (expr->type == EXPR_COMPARE) {
 422                 if (expr->left->type == EXPR_POSTOP)
 423                         __split_expr(expr->left);
 424                 if (expr->right->type == EXPR_POSTOP)
 425                         __split_expr(expr->right);
 426         } else if (expr->type == EXPR_POSTOP) {
 427                 __split_expr(expr);
 428         }
 429         __process_post_op_stack();
 430         pop_expression(&big_expression_stack);
 431 }
 432
 433 static int inside_condition;
 434 void __split_whole_condition(struct expression *expr)
 435 {
 436         sm_debug("%d in __split_whole_condition\n", get_lineno());
 437         inside_condition++;
 438         __save_pre_cond_states();
 439         __push_cond_stacks();
 440         /* it's a hack, but it's sometimes handy to have this stuff
 441            on the big_expression_stack.  */
 442         push_expression(&big_expression_stack, expr);
 443         if (expr)
 444                 split_conditions(expr);
 445         __use_cond_states();
 446         __pass_to_client(expr, WHOLE_CONDITION_HOOK);
 447         pop_expression(&big_expression_stack);
 448         inside_condition--;
 449         sm_debug("%d done __split_whole_condition\n", get_lineno());
 450 }
 451
 452 void __handle_logic(struct expression *expr)
 453 {
 454         sm_debug("%d in __handle_logic\n", get_lineno());
 455         inside_condition++;
 456         __save_pre_cond_states();
 457         __push_cond_stacks();
 458         /* it's a hack, but it's sometimes handy to have this stuff
 459            on the big_expression_stack.  */
 460         push_expression(&big_expression_stack, expr);
 461         if (expr)
 462                 split_conditions(expr);
 463         __use_cond_states();
 464         __pass_to_client(expr, WHOLE_CONDITION_HOOK);
 465         pop_expression(&big_expression_stack);
 466         __merge_false_states();
 467         inside_condition--;
 468         sm_debug("%d done __handle_logic\n", get_lineno());
 469 }
 470
 471 int is_condition(struct expression *expr)
 472 {
 473
 474         expr = strip_expr(expr);
 475         if (!expr)
 476                 return 0;
 477
 478         switch (expr->type) {
 479         case EXPR_LOGICAL:
 480         case EXPR_COMPARE:
 481                 return 1;
 482         case EXPR_PREOP:
 483                 if (expr->op == '!')
 484                         return 1;
 485         }
 486         return 0;
 487 }
 488
 489 int __handle_condition_assigns(struct expression *expr)
 490 {
 491         struct expression *right;
 492
 493         right = strip_expr(expr->right);
 494         if (!is_condition(expr->right))
 495                 return 0;
 496
 497         sm_debug("%d in __handle_condition_assigns\n", get_lineno());
 498         inside_condition++;
 499         __save_pre_cond_states();
 500         __push_cond_stacks();
 501         /* it's a hack, but it's sometimes handy to have this stuff
 502            on the big_expression_stack.  */
 503         push_expression(&big_expression_stack, right);
 504         split_conditions(right);
 505         __use_cond_states();
 506         set_extra_expr_mod(expr->left, alloc_estate_sval(sval_type_val(get_type(expr->left), 1)));
 507         __pass_to_client(right, WHOLE_CONDITION_HOOK);
 508         pop_expression(&big_expression_stack);
 509         inside_condition--;
 510         sm_debug("%d done __handle_condition_assigns\n", get_lineno());
 511
 512         __push_true_states();
 513         __use_false_states();
 514         set_extra_expr_mod(expr->left, alloc_estate_sval(sval_type_val(get_type(expr->left), 0)));
 515         __merge_true_states();
 516         __pass_to_client(expr, ASSIGNMENT_HOOK);
 517         return 1;
 518 }
 519
 520 static int is_select_assign(struct expression *expr)
 521 {
 522         struct expression *right;
 523
 524         if (expr->op != '=')
 525                 return 0;
 526         right = strip_expr(expr->right);
 527         if (right->type == EXPR_CONDITIONAL)
 528                 return 1;
 529         if (right->type == EXPR_SELECT)
 530                 return 1;
 531         return 0;
 532 }
 533
 534 static void set_fake_assign(struct expression *new,
 535                         struct expression *left, int op, struct expression *right)
 536 {
 537
 538         new->pos = left->pos;
 539         new->op = op;
 540         new->type = EXPR_ASSIGNMENT;
 541         new->left = left;
 542         new->right = right;
 543 }
 544
 545 int __handle_select_assigns(struct expression *expr)
 546 {
 547         struct expression *right;
 548         struct stree *final_states = NULL;
 549         struct sm_state *sm;
 550         int is_true;
 551         int is_false;
 552
 553         if (!is_select_assign(expr))
 554                 return 0;
 555         sm_debug("%d in __handle_ternary_assigns\n", get_lineno());
 556         right = strip_expr(expr->right);
 557
 558         is_true = implied_condition_true(right->conditional);
 559         is_false = implied_condition_false(right->conditional);
 560
 561         /* hah hah.  the ultra fake out */
 562         __save_pre_cond_states();
 563         __split_whole_condition(right->conditional);
 564
 565         if (!is_false) {
 566                 struct expression fake_expr;
 567
 568                 if (right->cond_true)
 569                         set_fake_assign(&fake_expr, expr->left, expr->op, right->cond_true);
 570                 else
 571                         set_fake_assign(&fake_expr, expr->left, expr->op, right->conditional);
 572                 __split_expr(&fake_expr);
 573                 final_states = clone_stree(__get_cur_stree());
 574         }
 575
 576         __use_false_states();
 577         if (!is_true) {
 578                 struct expression fake_expr;
 579
 580                 set_fake_assign(&fake_expr, expr->left, expr->op, right->cond_false);
 581                 __split_expr(&fake_expr);
 582                 merge_stree(&final_states, __get_cur_stree());
 583         }
 584
 585         __use_pre_cond_states();
 586
 587         FOR_EACH_SM(final_states, sm) {
 588                 __set_sm(sm);
 589         } END_FOR_EACH_SM(sm);
 590
 591         free_stree(&final_states);
 592
 593         sm_debug("%d done __handle_ternary_assigns\n", get_lineno());
 594
 595         return 1;
 596 }
 597
 598 static struct statement *split_then_return_last(struct statement *stmt)
 599 {
 600         struct statement *tmp;
 601         struct statement *last_stmt;
 602
 603         last_stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 604         if (!last_stmt)
 605                 return NULL;
 606
 607         __push_scope_hooks();
 608         FOR_EACH_PTR(stmt->stmts, tmp) {
 609                 if (tmp == last_stmt)
 610                         return last_stmt;
 611                 __split_stmt(tmp);
 612         } END_FOR_EACH_PTR(tmp);
 613         return NULL;
 614 }
 615
 616 int __handle_expr_statement_assigns(struct expression *expr)
 617 {
 618         struct expression *right;
 619         struct statement *stmt;
 620
 621         right = expr->right;
 622         if (right->type == EXPR_PREOP && right->op == '(')
 623                 right = right->unop;
 624         if (right->type != EXPR_STATEMENT)
 625                 return 0;
 626
 627         __expr_stmt_count++;
 628         stmt = right->statement;
 629         if (stmt->type == STMT_COMPOUND) {
 630                 struct statement *last_stmt;
 631                 struct expression fake_assign;
 632                 struct expression fake_expr_stmt;
 633
 634                 last_stmt = split_then_return_last(stmt);
 635                 if (!last_stmt) {
 636                         __expr_stmt_count--;
 637                         return 0;
 638                 }
 639
 640                 fake_expr_stmt.pos = last_stmt->pos;
 641                 fake_expr_stmt.type = EXPR_STATEMENT;
 642                 fake_expr_stmt.statement = last_stmt;
 643
 644                 fake_assign.pos = last_stmt->pos;
 645                 fake_assign.op = expr->op;
 646                 fake_assign.type = EXPR_ASSIGNMENT;
 647                 fake_assign.left = expr->left;
 648                 fake_assign.right = &fake_expr_stmt;
 649
 650                 __split_expr(&fake_assign);
 651
 652                 __call_scope_hooks();
 653         } else if (stmt->type == STMT_EXPRESSION) {
 654                 struct expression fake_assign;
 655
 656                 fake_assign.pos = stmt->pos;
 657                 fake_assign.op = expr->op;
 658                 fake_assign.type = EXPR_ASSIGNMENT;
 659                 fake_assign.left = expr->left;
 660                 fake_assign.right = stmt->expression;
 661
 662                 __split_expr(&fake_assign);
 663
 664         } else {
 665                 __split_stmt(stmt);
 666         }
 667         __expr_stmt_count--;
 668         return 1;
 669 }
 670
 671 int in_condition(void)
 672 {
 673         return inside_condition;
 674 }