smatch_conditions.c

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