smatch_type.c

   1 /*
   2  * sparse/smatch_types.c
   3  *
   4  * Copyright (C) 2009 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * The idea here is that you have an expression and you
  12  * want to know what the type is for that.
  13  */
  14
  15 #include "smatch.h"
  16
  17 struct symbol *get_real_base_type(struct symbol *sym)
  18 {
  19         struct symbol *ret;
  20
  21         ret = get_base_type(sym);
  22         if (ret && ret->type == SYM_RESTRICT)
  23                 return get_real_base_type(ret);
  24         return ret;
  25 }
  26
  27 int type_bits(struct symbol *type)
  28 {
  29         if (!type)
  30                 return 0;
  31         return type->bit_size;
  32 }
  33
  34 int type_positive_bits(struct symbol *type)
  35 {
  36         if (!type)
  37                 return 0;
  38         if (type_unsigned(type))
  39                 return type_bits(type);
  40         return type_bits(type) - 1;
  41 }
  42
  43 static struct symbol *get_binop_type(struct expression *expr)
  44 {
  45         struct symbol *left, *right;
  46
  47         left = get_type(expr->left);
  48         right = get_type(expr->right);
  49
  50         if (!left || !right)
  51                 return NULL;
  52
  53         if (left->type == SYM_PTR || left->type == SYM_ARRAY)
  54                 return left;
  55         if (right->type == SYM_PTR || right->type == SYM_ARRAY)
  56                 return right;
  57
  58         if (expr->op == SPECIAL_LEFTSHIFT ||
  59             expr->op == SPECIAL_RIGHTSHIFT) {
  60                 if (type_positive_bits(left) < 31)
  61                         return &int_ctype;
  62                 return left;
  63         }
  64
  65         if (type_positive_bits(left) < 31 && type_positive_bits(right) < 31)
  66                 return &int_ctype;
  67
  68         if (type_positive_bits(left) > type_positive_bits(right))
  69                 return left;
  70         return right;
  71 }
  72
  73 static struct symbol *get_type_symbol(struct expression *expr)
  74 {
  75         if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
  76                 return NULL;
  77
  78         return get_real_base_type(expr->symbol);
  79 }
  80
  81 static struct symbol *get_member_symbol(struct symbol_list *symbol_list, struct ident *member)
  82 {
  83         struct symbol *tmp;
  84
  85         FOR_EACH_PTR(symbol_list, tmp) {
  86                 if (!tmp->ident) {
  87                         tmp = get_real_base_type(tmp);
  88                         tmp = get_member_symbol(tmp->symbol_list, member);
  89                         if (tmp)
  90                                 return tmp;
  91                         continue;
  92                 }
  93                 if (tmp->ident == member)
  94                         return tmp;
  95         } END_FOR_EACH_PTR(tmp);
  96
  97         return NULL;
  98 }
  99
 100 static struct symbol *get_symbol_from_deref(struct expression *expr)
 101 {
 102         struct ident *member;
 103         struct symbol *sym;
 104
 105         if (!expr || expr->type != EXPR_DEREF)
 106                 return NULL;
 107
 108         member = expr->member;
 109         sym = get_type(expr->deref);
 110         if (!sym) {
 111                 // sm_msg("could not find struct type");
 112                 return NULL;
 113         }
 114         if (sym->type == SYM_PTR)
 115                 sym = get_real_base_type(sym);
 116         sym = get_member_symbol(sym->symbol_list, member);
 117         if (!sym)
 118                 return NULL;
 119         return get_real_base_type(sym);
 120 }
 121
 122 static struct symbol *get_return_type(struct expression *expr)
 123 {
 124         struct symbol *tmp;
 125
 126         tmp = get_type(expr->fn);
 127         if (!tmp)
 128                 return NULL;
 129         return get_real_base_type(tmp);
 130 }
 131
 132 static struct symbol *get_expr_stmt_type(struct statement *stmt)
 133 {
 134         if (stmt->type != STMT_COMPOUND)
 135                 return NULL;
 136         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 137         if (!stmt || stmt->type != STMT_EXPRESSION)
 138                 return NULL;
 139         return get_type(stmt->expression);
 140 }
 141
 142 static struct symbol *get_select_type(struct expression *expr)
 143 {
 144         struct symbol *one, *two;
 145
 146         one = get_type(expr->cond_true);
 147         two = get_type(expr->cond_false);
 148         if (!one || !two)
 149                 return NULL;
 150         /*
 151          * This is a hack.  If the types are not equiv then we
 152          * really don't know the type.  But I think guessing is
 153          *  probably Ok here.
 154          */
 155         if (type_positive_bits(one) > type_positive_bits(two))
 156                 return one;
 157         return two;
 158 }
 159
 160 struct symbol *get_pointer_type(struct expression *expr)
 161 {
 162         struct symbol *sym;
 163
 164         sym = get_type(expr);
 165         if (!sym || (sym->type != SYM_PTR && sym->type != SYM_ARRAY))
 166                 return NULL;
 167         return get_real_base_type(sym);
 168 }
 169
 170 static struct symbol *fake_pointer_sym(struct expression *expr)
 171 {
 172         struct symbol *sym;
 173         struct symbol *base;
 174
 175         sym = alloc_symbol(expr->pos, SYM_PTR);
 176         expr = expr->unop;
 177         base = get_type(expr);
 178         if (!base)
 179                 return NULL;
 180         sym->ctype.base_type = base;
 181         return sym;
 182 }
 183
 184 struct symbol *get_type(struct expression *expr)
 185 {
 186         if (!expr)
 187                 return NULL;
 188         expr = strip_parens(expr);
 189
 190         switch (expr->type) {
 191         case EXPR_SYMBOL:
 192                 return get_type_symbol(expr);
 193         case EXPR_DEREF:
 194                 return get_symbol_from_deref(expr);
 195         case EXPR_PREOP:
 196         case EXPR_POSTOP:
 197                 if (expr->op == '&')
 198                         return fake_pointer_sym(expr);
 199                 if (expr->op == '*')
 200                         return get_pointer_type(expr->unop);
 201                 return get_type(expr->unop);
 202         case EXPR_ASSIGNMENT:
 203                 return get_type(expr->left);
 204         case EXPR_CAST:
 205         case EXPR_FORCE_CAST:
 206         case EXPR_IMPLIED_CAST:
 207                 return get_real_base_type(expr->cast_type);
 208         case EXPR_COMPARE:
 209         case EXPR_BINOP:
 210                 return get_binop_type(expr);
 211         case EXPR_CALL:
 212                 return get_return_type(expr);
 213         case EXPR_STATEMENT:
 214                 return get_expr_stmt_type(expr->statement);
 215         case EXPR_CONDITIONAL:
 216         case EXPR_SELECT:
 217                 return get_select_type(expr);
 218         case EXPR_SIZEOF:
 219                 return &ulong_ctype;
 220         case EXPR_LOGICAL:
 221                 return &int_ctype;
 222         default:
 223 //              sm_msg("unhandled type %d", expr->type);
 224                 return expr->ctype;
 225         }
 226         return NULL;
 227 }
 228
 229 int type_unsigned(struct symbol *base_type)
 230 {
 231         if (!base_type)
 232                 return 0;
 233         if (base_type->ctype.modifiers & MOD_UNSIGNED)
 234                 return 1;
 235         return 0;
 236 }
 237
 238 int type_signed(struct symbol *base_type)
 239 {
 240         if (!base_type)
 241                 return 0;
 242         if (base_type->ctype.modifiers & MOD_UNSIGNED)
 243                 return 0;
 244         return 1;
 245 }
 246
 247 int expr_unsigned(struct expression *expr)
 248 {
 249         struct symbol *sym;
 250
 251         sym = get_type(expr);
 252         if (!sym)
 253                 return 0;
 254         if (type_unsigned(sym))
 255                 return 1;
 256         return 0;
 257 }
 258
 259 int returns_unsigned(struct symbol *sym)
 260 {
 261         if (!sym)
 262                 return 0;
 263         sym = get_base_type(sym);
 264         if (!sym || sym->type != SYM_FN)
 265                 return 0;
 266         sym = get_base_type(sym);
 267         return type_unsigned(sym);
 268 }
 269
 270 int is_pointer(struct expression *expr)
 271 {
 272         struct symbol *sym;
 273
 274         sym = get_type(expr);
 275         if (!sym)
 276                 return 0;
 277         if (sym->type == SYM_PTR)
 278                 return 1;
 279         return 0;
 280 }
 281
 282 int returns_pointer(struct symbol *sym)
 283 {
 284         if (!sym)
 285                 return 0;
 286         sym = get_base_type(sym);
 287         if (!sym || sym->type != SYM_FN)
 288                 return 0;
 289         sym = get_base_type(sym);
 290         if (sym->type == SYM_PTR)
 291                 return 1;
 292         return 0;
 293 }
 294
 295 sval_t sval_type_max(struct symbol *base_type)
 296 {
 297         sval_t ret;
 298
 299         ret.value = (~0ULL) >> 1;
 300         ret.type = base_type;
 301
 302         if (!base_type || !base_type->bit_size)
 303                 return ret;
 304
 305         ret.value = (~0ULL) >> (64 - type_positive_bits(base_type));
 306         return ret;
 307 }
 308
 309 sval_t sval_type_min(struct symbol *base_type)
 310 {
 311         sval_t ret;
 312
 313         if (!base_type || !base_type->bit_size)
 314                 base_type = &llong_ctype;
 315         ret.type = base_type;
 316
 317         if (type_unsigned(base_type)) {
 318                 ret.value = 0;
 319                 return ret;
 320         }
 321
 322         ret.value = (~0ULL) << type_positive_bits(base_type);
 323
 324         return ret;
 325 }
 326
 327 int nr_bits(struct expression *expr)
 328 {
 329         struct symbol *type;
 330
 331         type = get_type(expr);
 332         if (!type)
 333                 return 0;
 334         return type_bits(type);
 335 }
 336
 337 int is_static(struct expression *expr)
 338 {
 339         char *name;
 340         struct symbol *sym;
 341         int ret = 0;
 342
 343         name = get_variable_from_expr_complex(expr, &sym);
 344         if (!name || !sym)
 345                 goto free;
 346
 347         if (sym->ctype.modifiers & MOD_STATIC)
 348                 ret = 1;
 349 free:
 350         free_string(name);
 351         return ret;
 352 }
 353
 354 int types_equiv(struct symbol *one, struct symbol *two)
 355 {
 356         if (!one && !two)
 357                 return 1;
 358         if (!one || !two)
 359                 return 0;
 360         if (one->type != two->type)
 361                 return 0;
 362         if (one->type == SYM_PTR)
 363                 return types_equiv(get_real_base_type(one), get_real_base_type(two));
 364         if (type_positive_bits(one) != type_positive_bits(two))
 365                 return 0;
 366         return 1;
 367 }
 368
 369 const char *global_static()
 370 {
 371         if (cur_func_sym->ctype.modifiers & MOD_STATIC)
 372                 return "static";
 373         else
 374                 return "global";
 375 }
 376
 377 struct symbol *cur_func_return_type(void)
 378 {
 379         struct symbol *sym;
 380
 381         sym = get_real_base_type(cur_func_sym);
 382         if (!sym || sym->type != SYM_FN)
 383                 return NULL;
 384         sym = get_real_base_type(sym);
 385         return sym;
 386 }