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