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 get to 'b', 'c' and 'd'.
  27  * 'b' is true when we reach 'c' but otherwise we don't know.
  28  *
  29  * The other thing that complicates matters is if we negate
  30  * some if conditions.
  31  * if (!a) { ...
  32  * We pass the un-negated version to the client and flip the true
  33  * and false values internally.
  34  *
  35  * And negations can be part of a compound.
  36  * if (a && !(b || c)) { d;
  37  * In that situation we multiply the negative through to simplify
  38  * stuff so that we can remove the parens like this:
  39  * if (a && !b && !c) { d;
  40  *
  41  * One other thing is that:
  42  * if ((a) != 0){ ...
  43  * that's basically the same as testing for just 'a' so we simplify
  44  * it before passing it to the script.
  45  */
  46
  47 #include "smatch.h"
  48
  49 static void split_conditions(struct expression *expr);
  50
  51 static int is_logical_and(struct expression *expr)
  52 {
  53         if (expr->op == SPECIAL_LOGICAL_AND)
  54                 return 1;
  55         return 0;
  56 }
  57
  58 static int handle_zero_comparisons(struct expression *expr)
  59 {
  60         struct expression *tmp = NULL;
  61
  62         // if left is zero or right is zero
  63         if (is_zero(expr->left))
  64                 tmp = expr->right;
  65         else if (is_zero(expr->right))
  66                 tmp = expr->left;
  67         else
  68                 return 0;
  69
  70         // "if (foo != 0)" is the same as "if (foo)"
  71         if (expr->op == SPECIAL_NOTEQUAL) {
  72                 split_conditions(tmp);
  73                 return 1;
  74         }
  75
  76         // "if (foo == 0)" is the same as "if (!foo)"
  77         if (expr->op == SPECIAL_EQUAL) {
  78                 split_conditions(tmp);
  79                 __negate_cond_stacks();
  80                 return 1;
  81         }
  82
  83         return 0;
  84 }
  85
  86 /*
  87  * This function is for handling calls to likely/unlikely
  88  */
  89
  90 static int ignore_builtin_expect(struct expression *expr)
  91 {
  92         if (sym_name_is("__builtin_expect", expr->fn)) {
  93                 split_conditions(first_ptr_list((struct ptr_list *) expr->args));
  94                 return 1;
  95         }
  96         if (sym_name_is("__builtin_constant_p", expr->fn)) {
  97                 split_conditions(first_ptr_list((struct ptr_list *) expr->args));
  98                 return 1;
  99         }
 100         return 0;
 101 }
 102
 103 /*
 104  * handle_compound_stmt() is for: foo = ({blah; blah; blah; 1})
 105  */
 106
 107 static void handle_compound_stmt(struct statement *stmt)
 108 {
 109         struct expression *expr = NULL;
 110         struct statement *last;
 111         struct statement *s;
 112
 113         last = last_ptr_list((struct ptr_list *)stmt->stmts);
 114         if (last->type != STMT_EXPRESSION) {
 115                 last = NULL;
 116         } else {
 117                 expr = last->expression;
 118         }
 119         FOR_EACH_PTR(stmt->stmts, s) {
 120                 if (s != last)
 121                         __split_statements(s);
 122         } END_FOR_EACH_PTR(s);
 123         split_conditions(expr);
 124         return;
 125 }
 126
 127 static int handle_preop(struct expression *expr)
 128 {
 129         struct statement *stmt;
 130
 131         if (expr->op == '!') {
 132                 split_conditions(expr->unop);
 133                 __negate_cond_stacks();
 134                 return 1;
 135         }
 136         stmt = get_block_thing(expr);
 137         if (stmt) {
 138                 handle_compound_stmt(stmt);
 139                 return 1;
 140         }
 141         return 0;
 142 }
 143
 144 static void handle_logical(struct expression *expr)
 145 {
 146         /*
 147          * If we come to an "and" expr then:
 148          * We split the left side.
 149          * We keep all the current states.
 150          * We split the right side.
 151          * We keep all the states from both true sides.
 152          *
 153          * If it's an "or" expr then:
 154          * We save the current slist.
 155          * We split the left side.
 156          * We use the false states for the right side.
 157          * We split the right side.
 158          * We save all the states that are the same on both sides.
 159          */
 160
 161         split_conditions(expr->left);
 162
 163         if (!is_logical_and(expr))
 164                 __use_cond_false_states();
 165
 166         __save_pre_cond_states();
 167         __push_cond_stacks();
 168
 169         split_conditions(expr->right);
 170
 171         if (is_logical_and(expr)) {
 172                 __and_cond_states();
 173         } else {
 174                 __or_cond_states();
 175         }
 176
 177         __pop_pre_cond_states();
 178         __use_cond_true_states();
 179 }
 180
 181 static int handle_rostedt_if(struct expression *expr)
 182 {
 183         if (expr->type != EXPR_CALL)
 184                 return 0;
 185         if (!sym_name_is("__builtin_constant_p", expr->fn))
 186                 return 0;
 187         split_conditions(expr);
 188         return 1;
 189 }
 190
 191 static void handle_select(struct expression *expr)
 192 {
 193         /*
 194          * if ((aaa()?bbb():ccc())) { ...
 195          *
 196          * This is almost the same as:
 197          * if ((aaa() && bbb()) || (!aaa() && ccc())) { ...
 198          *
 199          * It's a bit complicated because we shouldn't pass aaa()
 200          * to the clients more than once.
 201          */
 202
 203         if (handle_rostedt_if(expr->conditional))
 204                 return;
 205
 206         split_conditions(expr->conditional);
 207
 208         __save_false_states_for_later();
 209
 210         if (implied_condition_true(expr->cond_true)) {
 211                 __split_expr(expr->cond_true);
 212         } else {
 213                 __push_cond_stacks();
 214                 split_conditions(expr->cond_true);
 215                 __and_cond_states();
 216         }
 217
 218         if (implied_condition_false(expr->cond_false)) {
 219                 __split_expr(expr->cond_false);
 220                 __pop_pre_cond_states();
 221                 return;
 222         }
 223
 224         __use_previously_stored_false_states();
 225
 226         __save_pre_cond_states();
 227         __push_cond_stacks();
 228         split_conditions(expr->cond_false);
 229         __or_cond_states();
 230         __pop_pre_cond_states();
 231
 232         __use_cond_true_states();
 233 }
 234
 235 static void split_conditions(struct expression *expr)
 236 {
 237
 238         sm_debug("%d in split_conditions type=%d\n", get_lineno(), expr->type);
 239
 240         expr = strip_expr(expr);
 241         if (!expr)
 242                 return;
 243
 244         switch(expr->type) {
 245         case EXPR_LOGICAL:
 246                 handle_logical(expr);
 247                 return;
 248         case EXPR_COMPARE:
 249                 if (handle_zero_comparisons(expr))
 250                         return;
 251                 break;
 252         case EXPR_CALL:
 253                 if (ignore_builtin_expect(expr))
 254                         return;
 255                 break;
 256         case EXPR_PREOP:
 257                 if (handle_preop(expr))
 258                         return;
 259                 break;
 260         case EXPR_CONDITIONAL:
 261         case EXPR_SELECT:
 262                 handle_select(expr);
 263                 return;
 264         }
 265
 266         /* fixme: this should be in smatch_flow.c
 267            but because of the funny stuff we do with conditions
 268            it's awkward to put it there.  We would need to
 269            call CONDITION_HOOK in smatch_flow as well.
 270         */
 271         if (expr->type == EXPR_COMPARE) {
 272                 if (expr->left->type != EXPR_POSTOP)
 273                         __split_expr(expr->left);
 274                 if (expr->right->type != EXPR_POSTOP)
 275                         __split_expr(expr->right);
 276         } else {
 277                 __split_expr(expr);
 278         }
 279         __pass_to_client(expr, CONDITION_HOOK);
 280         if (expr->type == EXPR_COMPARE) {
 281                 if (expr->left->type == EXPR_POSTOP)
 282                         __split_expr(expr->left);
 283                 if (expr->right->type == EXPR_POSTOP)
 284                         __split_expr(expr->right);
 285         }
 286 }
 287
 288 static int inside_condition;
 289 void __split_whole_condition(struct expression *expr)
 290 {
 291         sm_debug("%d in __split_whole_condition\n", get_lineno());
 292         inside_condition++;
 293         __save_pre_cond_states();
 294         __push_cond_stacks();
 295         if (expr)
 296                 split_conditions(expr);
 297         __use_cond_states();
 298         __pass_to_client(expr, WHOLE_CONDITION_HOOK);
 299         inside_condition--;
 300 }
 301
 302 int in_condition()
 303 {
 304         return inside_condition;
 305 }