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
  52 static void split_conditions(struct expression *expr);
  53
  54 static int is_logical_and(struct expression *expr)
  55 {
  56         if (expr->op == SPECIAL_LOGICAL_AND)
  57                 return 1;
  58         return 0;
  59 }
  60
  61 static int handle_zero_comparisons(struct expression *expr)
  62 {
  63         struct expression *tmp = NULL;
  64
  65         // if left is zero or right is zero
  66         if (is_zero(expr->left))
  67                 tmp = expr->right;
  68         else if (is_zero(expr->right))
  69                 tmp = expr->left;
  70         else
  71                 return 0;
  72
  73         // "if (foo != 0)" is the same as "if (foo)"
  74         if (expr->op == SPECIAL_NOTEQUAL) {
  75                 split_conditions(tmp);
  76                 return 1;
  77         }
  78
  79         // "if (foo == 0)" is the same as "if (!foo)"
  80         if (expr->op == SPECIAL_EQUAL) {
  81                 split_conditions(tmp);
  82                 __negate_cond_stacks();
  83                 return 1;
  84         }
  85
  86         return 0;
  87 }
  88
  89 /*
  90  * This function is for handling calls to likely/unlikely
  91  */
  92
  93 static int ignore_builtin_expect(struct expression *expr)
  94 {
  95         if (sym_name_is("__builtin_expect", expr->fn)) {
  96                 split_conditions(first_ptr_list((struct ptr_list *) expr->args));
  97                 return 1;
  98         }
  99         if (sym_name_is("__builtin_constant_p", 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_statements(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_block_thing(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
 166         if (!is_logical_and(expr))
 167                 __use_cond_false_states();
 168
 169         __push_cond_stacks();
 170
 171         __save_pre_cond_states();
 172         split_conditions(expr->right);
 173         __pop_pre_cond_states();
 174
 175         if (is_logical_and(expr)) {
 176                 __and_cond_states();
 177         } else {
 178                 __or_cond_states();
 179         }
 180         __use_cond_true_states();
 181 }
 182
 183 static int handle_rostedt_if(struct expression *expr)
 184 {
 185         if (expr->type != EXPR_CALL)
 186                 return 0;
 187         if (!sym_name_is("__builtin_constant_p", expr->fn))
 188                 return 0;
 189         split_conditions(expr);
 190         return 1;
 191 }
 192
 193 static void move_cur_to_tf(int tf)
 194 {
 195         struct sm_state *sm;
 196
 197         FOR_EACH_PTR(__fake_cur_slist, sm) {
 198                 if (tf)
 199                         __set_true_false_sm(sm, NULL);
 200                 else
 201                         __set_true_false_sm(NULL, sm);
 202         } END_FOR_EACH_PTR(sm);
 203         free_slist(&__fake_cur_slist);
 204 }
 205
 206
 207 /*
 208  * handle_select()
 209  * if ((aaa()?bbb():ccc())) { ...
 210  *
 211  * This is almost the same as:
 212  * if ((aaa() && bbb()) || (!aaa() && ccc())) { ...
 213  *
 214  * It's a bit complicated because we shouldn't pass aaa()
 215  * to the clients more than once.
 216  */
 217
 218 static void handle_select(struct expression *expr)
 219 {
 220         if (handle_rostedt_if(expr->conditional))
 221                 return;
 222
 223         split_conditions(expr->conditional);
 224
 225         __save_false_states_for_later();
 226
 227         __fake_cur++;
 228         if (implied_condition_true(expr->cond_true)) {
 229                 __split_expr(expr->cond_true);
 230         } else {
 231                 __push_cond_stacks();
 232                 split_conditions(expr->cond_true);
 233                 __and_cond_states();
 234         }
 235         move_cur_to_tf(TRUE);
 236
 237         if (implied_condition_false(expr->cond_false)) {
 238                 __split_expr(expr->cond_false);
 239                 __pop_pre_cond_states();
 240                 move_cur_to_tf(FALSE);
 241                 __fake_cur--;
 242                 return;
 243         }
 244
 245         __use_previously_stored_false_states();
 246
 247         __save_pre_cond_states();
 248         __push_cond_stacks();
 249         split_conditions(expr->cond_false);
 250         move_cur_to_tf(FALSE);
 251         __fake_cur--;
 252         __or_cond_states();
 253         __pop_pre_cond_states();
 254
 255         __use_cond_true_states();
 256 }
 257
 258 static void split_conditions(struct expression *expr)
 259 {
 260
 261         sm_debug("%d in split_conditions type=%d\n", get_lineno(), expr->type);
 262
 263         expr = strip_expr(expr);
 264         if (!expr)
 265                 return;
 266
 267         switch(expr->type) {
 268         case EXPR_LOGICAL:
 269                 handle_logical(expr);
 270                 return;
 271         case EXPR_COMPARE:
 272                 if (handle_zero_comparisons(expr))
 273                         return;
 274                 break;
 275         case EXPR_CALL:
 276                 if (ignore_builtin_expect(expr))
 277                         return;
 278                 break;
 279         case EXPR_PREOP:
 280                 if (handle_preop(expr))
 281                         return;
 282                 break;
 283         case EXPR_CONDITIONAL:
 284         case EXPR_SELECT:
 285                 handle_select(expr);
 286                 return;
 287         }
 288
 289         /* fixme: this should be in smatch_flow.c
 290            but because of the funny stuff we do with conditions
 291            it's awkward to put it there.  We would need to
 292            call CONDITION_HOOK in smatch_flow as well.
 293         */
 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 {
 300                 __split_expr(expr);
 301         }
 302         __pass_to_client(expr, CONDITION_HOOK);
 303         if (expr->type == EXPR_COMPARE) {
 304                 if (expr->left->type == EXPR_POSTOP)
 305                         __split_expr(expr->left);
 306                 if (expr->right->type == EXPR_POSTOP)
 307                         __split_expr(expr->right);
 308         }
 309 }
 310
 311 static int inside_condition;
 312 void __split_whole_condition(struct expression *expr)
 313 {
 314         sm_debug("%d in __split_whole_condition\n", get_lineno());
 315         inside_condition++;
 316         __save_pre_cond_states();
 317         __push_cond_stacks();
 318         if (expr)
 319                 split_conditions(expr);
 320         __use_cond_states();
 321         __pass_to_client(expr, WHOLE_CONDITION_HOOK);
 322         inside_condition--;
 323 }
 324
 325 int in_condition()
 326 {
 327         return inside_condition;
 328 }