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 static void split_conditions(struct expression *expr);
  55
  56 static int is_logical_and(struct expression *expr)
  57 {
  58         if (expr->op == SPECIAL_LOGICAL_AND)
  59                 return 1;
  60         return 0;
  61 }
  62
  63 static int handle_zero_comparisons(struct expression *expr)
  64 {
  65         struct expression *tmp = NULL;
  66
  67         // if left is zero or right is zero
  68         if (is_zero(expr->left))
  69                 tmp = expr->right;
  70         else if (is_zero(expr->right))
  71                 tmp = expr->left;
  72         else
  73                 return 0;
  74
  75         // "if (foo != 0)" is the same as "if (foo)"
  76         if (expr->op == SPECIAL_NOTEQUAL) {
  77                 split_conditions(tmp);
  78                 return 1;
  79         }
  80
  81         // "if (foo == 0)" is the same as "if (!foo)"
  82         if (expr->op == SPECIAL_EQUAL) {
  83                 split_conditions(tmp);
  84                 __negate_cond_stacks();
  85                 return 1;
  86         }
  87
  88         return 0;
  89 }
  90
  91 /*
  92  * This function is for handling calls to likely/unlikely
  93  */
  94
  95 static int ignore_builtin_expect(struct expression *expr)
  96 {
  97         if (sym_name_is("__builtin_expect", expr->fn)) {
  98                 split_conditions(first_ptr_list((struct ptr_list *) expr->args));
  99                 return 1;
 100         }
 101         if (sym_name_is("__builtin_constant_p", expr->fn)) {
 102                 split_conditions(first_ptr_list((struct ptr_list *) expr->args));
 103                 return 1;
 104         }
 105         return 0;
 106 }
 107
 108 /*
 109  * handle_compound_stmt() is for: foo = ({blah; blah; blah; 1})
 110  */
 111
 112 static void handle_compound_stmt(struct statement *stmt)
 113 {
 114         struct expression *expr = NULL;
 115         struct statement *last;
 116         struct statement *s;
 117
 118         last = last_ptr_list((struct ptr_list *)stmt->stmts);
 119         if (last->type != STMT_EXPRESSION) {
 120                 last = NULL;
 121         } else {
 122                 expr = last->expression;
 123         }
 124         FOR_EACH_PTR(stmt->stmts, s) {
 125                 if (s != last)
 126                         __split_statements(s);
 127         } END_FOR_EACH_PTR(s);
 128         split_conditions(expr);
 129         return;
 130 }
 131
 132 static int handle_preop(struct expression *expr)
 133 {
 134         struct statement *stmt;
 135
 136         if (expr->op == '!') {
 137                 split_conditions(expr->unop);
 138                 __negate_cond_stacks();
 139                 return 1;
 140         }
 141         stmt = get_block_thing(expr);
 142         if (stmt) {
 143                 handle_compound_stmt(stmt);
 144                 return 1;
 145         }
 146         return 0;
 147 }
 148
 149 static void handle_logical(struct expression *expr)
 150 {
 151         /*
 152          * If we come to an "and" expr then:
 153          * We split the left side.
 154          * We keep all the current states.
 155          * We split the right side.
 156          * We keep all the states from both true sides.
 157          *
 158          * If it's an "or" expr then:
 159          * We save the current slist.
 160          * We split the left side.
 161          * We use the false states for the right side.
 162          * We split the right side.
 163          * We save all the states that are the same on both sides.
 164          */
 165
 166         split_conditions(expr->left);
 167
 168         if (!is_logical_and(expr))
 169                 __use_cond_false_states();
 170
 171         __push_cond_stacks();
 172
 173         __save_pre_cond_states();
 174         split_conditions(expr->right);
 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 void move_cur_to_tf(int tf)
 186 {
 187         struct state_list *fake;
 188         struct sm_state *sm;
 189
 190         fake = __pop_fake_cur_slist();
 191         FOR_EACH_PTR(fake, sm) {
 192                 if (tf)
 193                         __set_true_false_sm(sm, NULL);
 194                 else
 195                         __set_true_false_sm(NULL, sm);
 196         } END_FOR_EACH_PTR(sm);
 197         free_slist(&fake);
 198 }
 199
 200
 201 /*
 202  * handle_select()
 203  * if ((aaa()?bbb():ccc())) { ...
 204  *
 205  * This is almost the same as:
 206  * if ((aaa() && bbb()) || (!aaa() && ccc())) { ...
 207  *
 208  * It's a bit complicated because we shouldn't pass aaa()
 209  * to the clients more than once.
 210  */
 211
 212 static void handle_select(struct expression *expr)
 213 {
 214         split_conditions(expr->conditional);
 215
 216         __save_false_states_on_pre_cond_stack();
 217
 218         __push_fake_cur_slist();
 219         if (implied_condition_true(expr->cond_true)) {
 220                 __split_expr(expr->cond_true);
 221         } else {
 222                 __push_cond_stacks();
 223                 split_conditions(expr->cond_true);
 224                 __and_cond_states();
 225         }
 226         move_cur_to_tf(TRUE);
 227
 228         __push_fake_cur_slist();
 229         if (implied_condition_false(expr->cond_false)) {
 230                 __split_expr(expr->cond_false);
 231                 __discard_pre_cond_states();
 232                 move_cur_to_tf(FALSE);
 233                 return;
 234         }
 235
 236         __use_pre_cond_states();
 237
 238         __save_pre_cond_states();
 239         __push_cond_stacks();
 240         split_conditions(expr->cond_false);
 241         move_cur_to_tf(FALSE);
 242         __or_cond_states();
 243         __discard_pre_cond_states();
 244
 245         __use_cond_true_states();
 246 }
 247
 248 static void split_conditions(struct expression *expr)
 249 {
 250
 251         sm_debug("%d in split_conditions type=%d\n", get_lineno(), expr->type);
 252
 253         expr = strip_expr(expr);
 254         if (!expr)
 255                 return;
 256
 257         switch (expr->type) {
 258         case EXPR_LOGICAL:
 259                 handle_logical(expr);
 260                 return;
 261         case EXPR_COMPARE:
 262                 if (handle_zero_comparisons(expr))
 263                         return;
 264                 break;
 265         case EXPR_CALL:
 266                 if (ignore_builtin_expect(expr))
 267                         return;
 268                 break;
 269         case EXPR_PREOP:
 270                 if (handle_preop(expr))
 271                         return;
 272                 break;
 273         case EXPR_CONDITIONAL:
 274         case EXPR_SELECT:
 275                 handle_select(expr);
 276                 return;
 277         }
 278
 279         /* fixme: this should be in smatch_flow.c
 280            but because of the funny stuff we do with conditions
 281            it's awkward to put it there.  We would need to
 282            call CONDITION_HOOK in smatch_flow as well.
 283         */
 284         push_expression(&big_expression_stack, expr);
 285         if (expr->type == EXPR_COMPARE) {
 286                 if (expr->left->type != EXPR_POSTOP)
 287                         __split_expr(expr->left);
 288                 if (expr->right->type != EXPR_POSTOP)
 289                         __split_expr(expr->right);
 290         } else if (expr->type != EXPR_POSTOP) {
 291                 __split_expr(expr);
 292         }
 293         __pass_to_client(expr, CONDITION_HOOK);
 294         if (expr->type == EXPR_COMPARE) {
 295                 if (expr->left->type == EXPR_POSTOP)
 296                         __split_expr(expr->left);
 297                 if (expr->right->type == EXPR_POSTOP)
 298                         __split_expr(expr->right);
 299         } else if (expr->type == EXPR_POSTOP) {
 300                 __split_expr(expr);
 301         }
 302         pop_expression(&big_expression_stack);
 303 }
 304
 305 static int inside_condition;
 306 void __split_whole_condition(struct expression *expr)
 307 {
 308         sm_debug("%d in __split_whole_condition\n", get_lineno());
 309         inside_condition++;
 310         __save_pre_cond_states();
 311         __push_cond_stacks();
 312         /* it's a hack, but it's sometimes handy to have this stuff
 313            on the big_expression_stack.  */
 314         push_expression(&big_expression_stack, expr);
 315         if (expr)
 316                 split_conditions(expr);
 317         __use_cond_states();
 318         __pass_to_client(expr, WHOLE_CONDITION_HOOK);
 319         pop_expression(&big_expression_stack);
 320         inside_condition--;
 321         sm_debug("%d done __split_whole_condition\n", get_lineno());
 322 }
 323
 324 static int is_condition_assign(struct expression *expr)
 325 {
 326         struct expression *right;
 327
 328         right = strip_expr(expr->right);
 329         switch(right->type) {
 330         case EXPR_LOGICAL:
 331         case EXPR_COMPARE:
 332                 break;
 333         case EXPR_PREOP:
 334                 if (right->op == '!')
 335                         break;
 336                 return 0;
 337         default:
 338                 return 0;
 339         }
 340         return 1;
 341 }
 342
 343 int __handle_condition_assigns(struct expression *expr)
 344 {
 345         struct expression *right;
 346
 347         right = strip_expr(expr->right);
 348         if (!is_condition_assign(expr))
 349                 return 0;
 350
 351         sm_debug("%d in __handle_condition_assigns\n", get_lineno());
 352         inside_condition++;
 353         __save_pre_cond_states();
 354         __push_cond_stacks();
 355         /* it's a hack, but it's sometimes handy to have this stuff
 356            on the big_expression_stack.  */
 357         push_expression(&big_expression_stack, right);
 358         split_conditions(right);
 359         set_true_false_states_expr(SMATCH_EXTRA, expr->left, alloc_extra_state(1), alloc_extra_state(0));
 360         __use_cond_states();
 361         __pass_to_client(right, WHOLE_CONDITION_HOOK);
 362         pop_expression(&big_expression_stack);
 363         inside_condition--;
 364         sm_debug("%d done __handle_condition_assigns\n", get_lineno());
 365
 366         __push_true_states();
 367         __use_false_states();
 368         __merge_true_states();
 369         return 1;
 370 }
 371
 372 int in_condition(void)
 373 {
 374         return inside_condition;
 375 }