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->bit_size;
  40         return type->bit_size - 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         if (types_equiv(one, two))
 151                 return one;
 152         return NULL;
 153 }
 154
 155 struct symbol *get_pointer_type(struct expression *expr)
 156 {
 157         struct symbol *sym;
 158
 159         sym = get_type(expr);
 160         if (!sym || (sym->type != SYM_PTR && sym->type != SYM_ARRAY))
 161                 return NULL;
 162         return get_real_base_type(sym);
 163 }
 164
 165 static struct symbol *fake_pointer_sym(struct expression *expr)
 166 {
 167         struct symbol *sym;
 168         struct symbol *base;
 169
 170         sym = alloc_symbol(expr->pos, SYM_PTR);
 171         expr = expr->unop;
 172         base = get_type(expr);
 173         if (!base)
 174                 return NULL;
 175         sym->ctype.base_type = base;
 176         return sym;
 177 }
 178
 179 struct symbol *get_type(struct expression *expr)
 180 {
 181         if (!expr)
 182                 return NULL;
 183         expr = strip_parens(expr);
 184
 185         switch (expr->type) {
 186         case EXPR_SYMBOL:
 187                 return get_type_symbol(expr);
 188         case EXPR_DEREF:
 189                 return get_symbol_from_deref(expr);
 190         case EXPR_PREOP:
 191         case EXPR_POSTOP:
 192                 if (expr->op == '&')
 193                         return fake_pointer_sym(expr);
 194                 if (expr->op == '*')
 195                         return get_pointer_type(expr->unop);
 196                 return get_type(expr->unop);
 197         case EXPR_ASSIGNMENT:
 198                 return get_type(expr->left);
 199         case EXPR_CAST:
 200         case EXPR_FORCE_CAST:
 201         case EXPR_IMPLIED_CAST:
 202                 return get_real_base_type(expr->cast_type);
 203         case EXPR_COMPARE:
 204         case EXPR_BINOP:
 205                 return get_binop_type(expr);
 206         case EXPR_CALL:
 207                 return get_return_type(expr);
 208         case EXPR_STATEMENT:
 209                 return get_expr_stmt_type(expr->statement);
 210         case EXPR_CONDITIONAL:
 211         case EXPR_SELECT:
 212                 return get_select_type(expr);
 213         case EXPR_SIZEOF:
 214                 return &ulong_ctype;
 215         case EXPR_LOGICAL:
 216                 return &int_ctype;
 217         default:
 218 //              sm_msg("unhandled type %d", expr->type);
 219                 return expr->ctype;
 220         }
 221         return NULL;
 222 }
 223
 224 int type_unsigned(struct symbol *base_type)
 225 {
 226         if (!base_type)
 227                 return 0;
 228         if (base_type->ctype.modifiers & MOD_UNSIGNED)
 229                 return 1;
 230         return 0;
 231 }
 232
 233 int type_signed(struct symbol *base_type)
 234 {
 235         if (!base_type)
 236                 return 0;
 237         if (base_type->ctype.modifiers & MOD_UNSIGNED)
 238                 return 0;
 239         return 1;
 240 }
 241
 242 int expr_unsigned(struct expression *expr)
 243 {
 244         struct symbol *sym;
 245
 246         sym = get_type(expr);
 247         if (!sym)
 248                 return 0;
 249         if (type_unsigned(sym))
 250                 return 1;
 251         return 0;
 252 }
 253
 254 int returns_unsigned(struct symbol *sym)
 255 {
 256         if (!sym)
 257                 return 0;
 258         sym = get_base_type(sym);
 259         if (!sym || sym->type != SYM_FN)
 260                 return 0;
 261         sym = get_base_type(sym);
 262         return type_unsigned(sym);
 263 }
 264
 265 int is_pointer(struct expression *expr)
 266 {
 267         struct symbol *sym;
 268
 269         sym = get_type(expr);
 270         if (!sym)
 271                 return 0;
 272         if (sym->type == SYM_PTR)
 273                 return 1;
 274         return 0;
 275 }
 276
 277 int returns_pointer(struct symbol *sym)
 278 {
 279         if (!sym)
 280                 return 0;
 281         sym = get_base_type(sym);
 282         if (!sym || sym->type != SYM_FN)
 283                 return 0;
 284         sym = get_base_type(sym);
 285         if (sym->type == SYM_PTR)
 286                 return 1;
 287         return 0;
 288 }
 289
 290 sval_t sval_type_max(struct symbol *base_type)
 291 {
 292         sval_t ret;
 293
 294         ret.value = (~0ULL) >> 1;
 295         ret.type = base_type;
 296
 297         if (!base_type || !base_type->bit_size)
 298                 return ret;
 299
 300         if (type_unsigned(base_type))
 301                 ret.value = (~0ULL) >> (64 - base_type->bit_size);
 302         else
 303                 ret.value = (~0ULL) >> (64 - (base_type->bit_size - 1));
 304
 305         return ret;
 306 }
 307
 308 sval_t sval_type_min(struct symbol *base_type)
 309 {
 310         sval_t ret;
 311
 312         if (!base_type || !base_type->bit_size)
 313                 base_type = &llong_ctype;
 314         ret.type = base_type;
 315
 316         if (type_unsigned(base_type)) {
 317                 ret.value = 0;
 318                 return ret;
 319         }
 320
 321         ret.value = (~0ULL) << (base_type->bit_size - 1);
 322
 323         return ret;
 324 }
 325
 326 int nr_bits(struct expression *expr)
 327 {
 328         struct symbol *type;
 329
 330         type = get_type(expr);
 331         if (!type)
 332                 return 0;
 333         return type->bit_size;
 334 }
 335
 336 int is_static(struct expression *expr)
 337 {
 338         char *name;
 339         struct symbol *sym;
 340         int ret = 0;
 341
 342         name = get_variable_from_expr_complex(expr, &sym);
 343         if (!name || !sym)
 344                 goto free;
 345
 346         if (sym->ctype.modifiers & MOD_STATIC)
 347                 ret = 1;
 348 free:
 349         free_string(name);
 350         return ret;
 351 }
 352
 353 int types_equiv(struct symbol *one, struct symbol *two)
 354 {
 355         if (!one && !two)
 356                 return 1;
 357         if (!one || !two)
 358                 return 0;
 359         if (one->type != two->type)
 360                 return 0;
 361         if (one->type == SYM_PTR)
 362                 return types_equiv(get_real_base_type(one), get_real_base_type(two));
 363         if (type_positive_bits(one) != type_positive_bits(two))
 364                 return 0;
 365         return 1;
 366 }
 367
 368 const char *global_static()
 369 {
 370         if (cur_func_sym->ctype.modifiers & MOD_STATIC)
 371                 return "static";
 372         else
 373                 return "global";
 374 }
 375
 376 struct symbol *cur_func_return_type(void)
 377 {
 378         struct symbol *sym;
 379
 380         sym = get_real_base_type(cur_func_sym);
 381         if (!sym || sym->type != SYM_FN)
 382                 return NULL;
 383         sym = get_real_base_type(sym);
 384         return sym;
 385 }