smatch_extra.c

   1 /*
   2  * sparse/smatch_extra.c
   3  *
   4  * Copyright (C) 2008 Dan Carpenter.
   5  *
   6  *  Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include <stdlib.h>
  11 #include "parse.h"
  12 #include "smatch.h"
  13
  14 static int my_id;
  15
  16 static int _zero = 0;
  17 static int _one = 1;
  18
  19 static struct smatch_state zero = {
  20         .name = "zero",
  21         .data = &_zero,
  22 };
  23
  24 static struct smatch_state one = {
  25         .name = "one",
  26         .data = &_one,
  27 };
  28
  29 static struct smatch_state *alloc_state(int val)
  30 {
  31         struct smatch_state *state;
  32
  33         if (val == 0)
  34                 return &zero;
  35         if (val == 1)
  36                 return &one;
  37         if (val == UNDEFINED)
  38                 return &undefined;
  39
  40         state = malloc(sizeof(*state));
  41         state->name = "value";
  42         state->data = malloc(sizeof(int));
  43         *(int *)state->data = val;
  44         return state;
  45 }
  46
  47 static void match_function_call_after(struct expression *expr)
  48 {
  49         struct expression *tmp;
  50         struct symbol *sym;
  51         char *name;
  52         int i = 0;
  53
  54         FOR_EACH_PTR(expr->args, tmp) {
  55                 if (tmp->op == '&') {
  56                         name = get_variable_from_expr(tmp->unop, &sym);
  57                         if (name) {
  58                                 set_state(name, my_id, sym, &undefined);
  59                         }
  60                         free_string(name);
  61                 }
  62                 i++;
  63         } END_FOR_EACH_PTR(tmp);
  64 }
  65
  66 static void match_assign(struct expression *expr)
  67 {
  68         struct expression *left;
  69         struct symbol *sym;
  70         char *name;
  71
  72         left = strip_expr(expr->left);
  73         name = get_variable_from_expr(left, &sym);
  74         if (!name)
  75                 return;
  76         set_state(name, my_id, sym, alloc_state(get_value(expr->right)));
  77         free_string(name);
  78 }
  79
  80 static void undef_expr(struct expression *expr)
  81 {
  82         struct symbol *sym;
  83         char *name;
  84
  85         name = get_variable_from_expr(expr->unop, &sym);
  86         if (!name)
  87                 return;
  88         if (!get_state(name, my_id, sym)) {
  89                 free_string(name);
  90                 return;
  91         }
  92         set_state(name, my_id, sym, &undefined);
  93         free_string(name);
  94 }
  95
  96 static void match_declarations(struct symbol *sym)
  97 {
  98         const char *name;
  99
 100         if (sym->ident) {
 101                 name = sym->ident->name;
 102                 if (sym->initializer) {
 103                         set_state(name, my_id, sym, alloc_state(get_value(sym->initializer)));
 104                 } else {
 105                         set_state(name, my_id, sym, &undefined);
 106                 }
 107         }
 108 }
 109
 110 static void match_function_def(struct symbol *sym)
 111 {
 112         struct symbol *arg;
 113
 114         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 115                 if (!arg->ident) {
 116                         continue;
 117                 }
 118                 set_state(arg->ident->name, my_id, arg, &undefined);
 119         } END_FOR_EACH_PTR(arg);
 120 }
 121
 122 static void match_unop(struct expression *expr)
 123 {
 124         struct symbol *sym;
 125         char *name;
 126         const char *tmp;
 127
 128
 129         name = get_variable_from_expr(expr->unop, &sym);
 130         if (!name)
 131                 return;
 132
 133         tmp = show_special(expr->op);
 134         if ((!strcmp(tmp, "--")) || (!strcmp(tmp, "++")))
 135                 set_state(name, my_id, sym, &undefined);
 136         free_string(name);
 137 }
 138
 139 static int expr_to_val(struct expression *expr)
 140 {
 141         struct smatch_state *state;
 142         int val;
 143         struct symbol *sym;
 144         char *name;
 145
 146         val = get_value(expr);
 147         if (val != UNDEFINED)
 148                 return val;
 149
 150         name = get_variable_from_expr(expr, &sym);
 151         if (!name)
 152                 return UNDEFINED;
 153         state = get_state(name, my_id, sym);
 154         free_string(name);
 155         if (!state || !state->data)
 156                 return UNDEFINED;
 157         return *(int *)state->data;
 158 }
 159
 160 int true_comparison(int left, int comparison, int right)
 161 {
 162         switch(comparison){
 163         case '<':
 164         case SPECIAL_UNSIGNED_LT:
 165                 if (left < right)
 166                         return 1;
 167                 return 0;
 168         case SPECIAL_UNSIGNED_LTE:
 169         case SPECIAL_LTE:
 170                 if (left < right)
 171                         return 1;
 172         case SPECIAL_EQUAL:
 173                 if (left == right)
 174                         return 1;
 175                 return 0;
 176         case SPECIAL_UNSIGNED_GTE:
 177         case SPECIAL_GTE:
 178                 if (left == right)
 179                         return 1;
 180         case '>':
 181         case SPECIAL_UNSIGNED_GT:
 182                 if (left > right)
 183                         return 1;
 184                 return 0;
 185         case SPECIAL_NOTEQUAL:
 186                 if (left != right)
 187                         return 1;
 188                 return 0;
 189         default:
 190                 smatch_msg("unhandled comparison %d\n", comparison);
 191                 return UNDEFINED;
 192         }
 193         return 0;
 194 }
 195
 196 static int do_comparison(struct expression *expr)
 197 {
 198         int left, right, ret;
 199
 200         if ((left = expr_to_val(expr->left)) == UNDEFINED)
 201                 return UNDEFINED;
 202
 203         if ((right = expr_to_val(expr->right)) == UNDEFINED)
 204                 return UNDEFINED;
 205
 206         ret = true_comparison(left, expr->op, right);
 207         if (ret == 1) {
 208                 SM_DEBUG("%d known condition: %d %s %d => true\n",
 209                         get_lineno(), left, show_special(expr->op), right);
 210         } else if (ret == 0) {
 211                 SM_DEBUG("%d known condition: %d %s %d => false\n",
 212                         get_lineno(), left, show_special(expr->op), right);
 213         }
 214         return ret;
 215 }
 216
 217 int last_stmt_val(struct statement *stmt)
 218 {
 219         struct expression *expr;
 220
 221         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 222         if (stmt->type != STMT_EXPRESSION)
 223                 return UNDEFINED;
 224         expr = stmt->expression;
 225         return get_value(expr);
 226 }
 227
 228 static int variable_non_zero(struct expression *expr)
 229 {
 230         char *name;
 231         struct symbol *sym;
 232         struct smatch_state *state;
 233         int ret = UNDEFINED;
 234
 235         name = get_variable_from_expr(expr, &sym);
 236         if (!name || !sym)
 237                 goto exit;
 238         state = get_state(name, my_id, sym);
 239         if (!state || !state->data)
 240                 goto exit;
 241         ret = true_comparison(*(int *)state->data, SPECIAL_NOTEQUAL, 0);
 242 exit:
 243         free_string(name);
 244         return ret;
 245 }
 246
 247 int known_condition_true(struct expression *expr)
 248 {
 249         struct statement *stmt;
 250         int tmp;
 251
 252         if (!expr)
 253                 return 0;
 254
 255         tmp = get_value(expr);
 256         if (tmp && tmp != UNDEFINED)
 257                 return 1;
 258
 259         expr = strip_expr(expr);
 260         switch(expr->type) {
 261         case EXPR_COMPARE:
 262                 if (do_comparison(expr) == 1)
 263                         return 1;
 264                 break;
 265         case EXPR_PREOP:
 266                 if (expr->op == '!') {
 267                         if (known_condition_false(expr->unop))
 268                                 return 1;
 269                         break;
 270                 }
 271                 stmt = get_block_thing(expr);
 272                 if (stmt && (last_stmt_val(stmt) == 1))
 273                         return 1;
 274                 break;
 275         default:
 276                 if (variable_non_zero(expr) == 1)
 277                         return 1;
 278                 break;
 279         }
 280         return 0;
 281 }
 282
 283 int known_condition_false(struct expression *expr)
 284 {
 285         struct statement *stmt;
 286         struct expression *tmp;
 287
 288         if (!expr)
 289                 return 0;
 290
 291         if (is_zero(expr))
 292                 return 1;
 293
 294         switch(expr->type) {
 295         case EXPR_COMPARE:
 296                 if (do_comparison(expr) == 0)
 297                         return 1;
 298         case EXPR_PREOP:
 299                 if (expr->op == '!') {
 300                         if (known_condition_true(expr->unop))
 301                                 return 1;
 302                         break;
 303                 }
 304                 stmt = get_block_thing(expr);
 305                 if (stmt && (last_stmt_val(stmt) == 0))
 306                         return 1;
 307                 tmp = strip_expr(expr);
 308                 if (tmp != expr)
 309                         return known_condition_false(tmp);
 310                 break;
 311         default:
 312                 if (variable_non_zero(expr) == 0)
 313                         return 1;
 314                 break;
 315         }
 316         return 0;
 317 }
 318
 319 void register_smatch_extra(int id)
 320 {
 321         my_id = id;
 322         add_hook(&undef_expr, OP_HOOK);
 323         add_hook(&match_function_def, FUNC_DEF_HOOK);
 324         add_hook(&match_function_call_after, FUNCTION_CALL_AFTER_HOOK);
 325         add_hook(&match_assign, ASSIGNMENT_AFTER_HOOK);
 326         add_hook(&match_declarations, DECLARATION_HOOK);
 327         add_hook(&match_unop, OP_HOOK);
 328 }