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         if (type->type == SYM_PTR)  /* Sparse doesn't set this for &pointers */
  32                 return bits_in_pointer;
  33         return type->bit_size;
  34 }
  35
  36 int type_positive_bits(struct symbol *type)
  37 {
  38         if (!type)
  39                 return 0;
  40         if (type_unsigned(type))
  41                 return type_bits(type);
  42         return type_bits(type) - 1;
  43 }
  44
  45 static struct symbol *get_binop_type(struct expression *expr)
  46 {
  47         struct symbol *left, *right;
  48
  49         left = get_type(expr->left);
  50         right = get_type(expr->right);
  51
  52         if (!left || !right)
  53                 return NULL;
  54
  55         if (left->type == SYM_PTR || left->type == SYM_ARRAY)
  56                 return left;
  57         if (right->type == SYM_PTR || right->type == SYM_ARRAY)
  58                 return right;
  59
  60         if (expr->op == SPECIAL_LEFTSHIFT ||
  61             expr->op == SPECIAL_RIGHTSHIFT) {
  62                 if (type_positive_bits(left) < 31)
  63                         return &int_ctype;
  64                 return left;
  65         }
  66
  67         if (type_positive_bits(left) < 31 && type_positive_bits(right) < 31)
  68                 return &int_ctype;
  69
  70         if (type_positive_bits(left) > type_positive_bits(right))
  71                 return left;
  72         return right;
  73 }
  74
  75 static struct symbol *get_type_symbol(struct expression *expr)
  76 {
  77         if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
  78                 return NULL;
  79
  80         return get_real_base_type(expr->symbol);
  81 }
  82
  83 static struct symbol *get_member_symbol(struct symbol_list *symbol_list, struct ident *member)
  84 {
  85         struct symbol *tmp, *sub;
  86
  87         FOR_EACH_PTR(symbol_list, tmp) {
  88                 if (!tmp->ident) {
  89                         sub = get_real_base_type(tmp);
  90                         sub = get_member_symbol(sub->symbol_list, member);
  91                         if (sub)
  92                                 return sub;
  93                         continue;
  94                 }
  95                 if (tmp->ident == member)
  96                         return tmp;
  97         } END_FOR_EACH_PTR(tmp);
  98
  99         return NULL;
 100 }
 101
 102 static struct symbol *get_symbol_from_deref(struct expression *expr)
 103 {
 104         struct ident *member;
 105         struct symbol *sym;
 106
 107         if (!expr || expr->type != EXPR_DEREF)
 108                 return NULL;
 109
 110         member = expr->member;
 111         sym = get_type(expr->deref);
 112         if (!sym) {
 113                 // sm_msg("could not find struct type");
 114                 return NULL;
 115         }
 116         if (sym->type == SYM_PTR)
 117                 sym = get_real_base_type(sym);
 118         sym = get_member_symbol(sym->symbol_list, member);
 119         if (!sym)
 120                 return NULL;
 121         return get_real_base_type(sym);
 122 }
 123
 124 static struct symbol *get_return_type(struct expression *expr)
 125 {
 126         struct symbol *tmp;
 127
 128         tmp = get_type(expr->fn);
 129         if (!tmp)
 130                 return NULL;
 131         return get_real_base_type(tmp);
 132 }
 133
 134 static struct symbol *get_expr_stmt_type(struct statement *stmt)
 135 {
 136         if (stmt->type != STMT_COMPOUND)
 137                 return NULL;
 138         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 139         if (!stmt || stmt->type != STMT_EXPRESSION)
 140                 return NULL;
 141         return get_type(stmt->expression);
 142 }
 143
 144 static struct symbol *get_select_type(struct expression *expr)
 145 {
 146         struct symbol *one, *two;
 147
 148         one = get_type(expr->cond_true);
 149         two = get_type(expr->cond_false);
 150         if (!one || !two)
 151                 return NULL;
 152         /*
 153          * This is a hack.  If the types are not equiv then we
 154          * really don't know the type.  But I think guessing is
 155          *  probably Ok here.
 156          */
 157         if (type_positive_bits(one) > type_positive_bits(two))
 158                 return one;
 159         return two;
 160 }
 161
 162 struct symbol *get_pointer_type(struct expression *expr)
 163 {
 164         struct symbol *sym;
 165
 166         sym = get_type(expr);
 167         if (!sym || (sym->type != SYM_PTR && sym->type != SYM_ARRAY))
 168                 return NULL;
 169         return get_real_base_type(sym);
 170 }
 171
 172 static struct symbol *fake_pointer_sym(struct expression *expr)
 173 {
 174         struct symbol *sym;
 175         struct symbol *base;
 176
 177         sym = alloc_symbol(expr->pos, SYM_PTR);
 178         expr = expr->unop;
 179         base = get_type(expr);
 180         if (!base)
 181                 return NULL;
 182         sym->ctype.base_type = base;
 183         return sym;
 184 }
 185
 186 struct symbol *get_type(struct expression *expr)
 187 {
 188         if (!expr)
 189                 return NULL;
 190         expr = strip_parens(expr);
 191
 192         switch (expr->type) {
 193         case EXPR_STRING:
 194                 return &string_ctype;
 195         case EXPR_SYMBOL:
 196                 return get_type_symbol(expr);
 197         case EXPR_DEREF:
 198                 return get_symbol_from_deref(expr);
 199         case EXPR_PREOP:
 200         case EXPR_POSTOP:
 201                 if (expr->op == '&')
 202                         return fake_pointer_sym(expr);
 203                 if (expr->op == '*')
 204                         return get_pointer_type(expr->unop);
 205                 return get_type(expr->unop);
 206         case EXPR_ASSIGNMENT:
 207                 return get_type(expr->left);
 208         case EXPR_CAST:
 209         case EXPR_FORCE_CAST:
 210         case EXPR_IMPLIED_CAST:
 211                 return get_real_base_type(expr->cast_type);
 212         case EXPR_COMPARE:
 213         case EXPR_BINOP:
 214                 return get_binop_type(expr);
 215         case EXPR_CALL:
 216                 return get_return_type(expr);
 217         case EXPR_STATEMENT:
 218                 return get_expr_stmt_type(expr->statement);
 219         case EXPR_CONDITIONAL:
 220         case EXPR_SELECT:
 221                 return get_select_type(expr);
 222         case EXPR_SIZEOF:
 223                 return &ulong_ctype;
 224         case EXPR_LOGICAL:
 225                 return &int_ctype;
 226         default:
 227 //              sm_msg("unhandled type %d", expr->type);
 228                 return expr->ctype;
 229         }
 230         return NULL;
 231 }
 232
 233 int type_unsigned(struct symbol *base_type)
 234 {
 235         if (!base_type)
 236                 return 0;
 237         if (base_type->ctype.modifiers & MOD_UNSIGNED)
 238                 return 1;
 239         return 0;
 240 }
 241
 242 int type_signed(struct symbol *base_type)
 243 {
 244         if (!base_type)
 245                 return 0;
 246         if (base_type->ctype.modifiers & MOD_UNSIGNED)
 247                 return 0;
 248         return 1;
 249 }
 250
 251 int expr_unsigned(struct expression *expr)
 252 {
 253         struct symbol *sym;
 254
 255         sym = get_type(expr);
 256         if (!sym)
 257                 return 0;
 258         if (type_unsigned(sym))
 259                 return 1;
 260         return 0;
 261 }
 262
 263 int returns_unsigned(struct symbol *sym)
 264 {
 265         if (!sym)
 266                 return 0;
 267         sym = get_base_type(sym);
 268         if (!sym || sym->type != SYM_FN)
 269                 return 0;
 270         sym = get_base_type(sym);
 271         return type_unsigned(sym);
 272 }
 273
 274 int is_pointer(struct expression *expr)
 275 {
 276         struct symbol *sym;
 277
 278         sym = get_type(expr);
 279         if (!sym)
 280                 return 0;
 281         if (sym == &string_ctype)
 282                 return 0;
 283         if (sym->type == SYM_PTR)
 284                 return 1;
 285         return 0;
 286 }
 287
 288 int returns_pointer(struct symbol *sym)
 289 {
 290         if (!sym)
 291                 return 0;
 292         sym = get_base_type(sym);
 293         if (!sym || sym->type != SYM_FN)
 294                 return 0;
 295         sym = get_base_type(sym);
 296         if (sym->type == SYM_PTR)
 297                 return 1;
 298         return 0;
 299 }
 300
 301 sval_t sval_type_max(struct symbol *base_type)
 302 {
 303         sval_t ret;
 304
 305         ret.value = (~0ULL) >> 1;
 306         ret.type = base_type;
 307
 308         if (!base_type || !base_type->bit_size)
 309                 return ret;
 310
 311         ret.value = (~0ULL) >> (64 - type_positive_bits(base_type));
 312         return ret;
 313 }
 314
 315 sval_t sval_type_min(struct symbol *base_type)
 316 {
 317         sval_t ret;
 318
 319         if (!base_type || !base_type->bit_size)
 320                 base_type = &llong_ctype;
 321         ret.type = base_type;
 322
 323         if (type_unsigned(base_type)) {
 324                 ret.value = 0;
 325                 return ret;
 326         }
 327
 328         ret.value = (~0ULL) << type_positive_bits(base_type);
 329
 330         return ret;
 331 }
 332
 333 int nr_bits(struct expression *expr)
 334 {
 335         struct symbol *type;
 336
 337         type = get_type(expr);
 338         if (!type)
 339                 return 0;
 340         return type_bits(type);
 341 }
 342
 343 int is_static(struct expression *expr)
 344 {
 345         char *name;
 346         struct symbol *sym;
 347         int ret = 0;
 348
 349         name = expr_to_str_sym(expr, &sym);
 350         if (!name || !sym)
 351                 goto free;
 352
 353         if (sym->ctype.modifiers & MOD_STATIC)
 354                 ret = 1;
 355 free:
 356         free_string(name);
 357         return ret;
 358 }
 359
 360 int types_equiv(struct symbol *one, struct symbol *two)
 361 {
 362         if (!one && !two)
 363                 return 1;
 364         if (!one || !two)
 365                 return 0;
 366         if (one->type != two->type)
 367                 return 0;
 368         if (one->type == SYM_PTR)
 369                 return types_equiv(get_real_base_type(one), get_real_base_type(two));
 370         if (type_positive_bits(one) != type_positive_bits(two))
 371                 return 0;
 372         return 1;
 373 }
 374
 375 const char *global_static()
 376 {
 377         if (cur_func_sym->ctype.modifiers & MOD_STATIC)
 378                 return "static";
 379         else
 380                 return "global";
 381 }
 382
 383 struct symbol *cur_func_return_type(void)
 384 {
 385         struct symbol *sym;
 386
 387         sym = get_real_base_type(cur_func_sym);
 388         if (!sym || sym->type != SYM_FN)
 389                 return NULL;
 390         sym = get_real_base_type(sym);
 391         return sym;
 392 }
 393
 394 struct symbol *get_arg_type(struct expression *fn, int arg)
 395 {
 396         struct symbol *fn_type;
 397         struct symbol *tmp;
 398         struct symbol *arg_type;
 399         int i;
 400
 401         fn_type = get_type(fn);
 402         if (!fn_type)
 403                 return NULL;
 404         if (fn_type->type == SYM_PTR)
 405                 fn_type = get_real_base_type(fn_type);
 406         if (fn_type->type != SYM_FN)
 407                 return NULL;
 408
 409         i = 0;
 410         FOR_EACH_PTR(fn_type->arguments, tmp) {
 411                 arg_type = get_real_base_type(tmp);
 412                 if (i == arg) {
 413                         return arg_type;
 414                 }
 415                 i++;
 416         } END_FOR_EACH_PTR(tmp);
 417
 418         return NULL;
 419 }
 420
 421 static struct symbol *get_member_from_string(struct symbol_list *symbol_list, char *name)
 422 {
 423         struct symbol *tmp, *sub;
 424         int chunk_len;
 425
 426         if (strncmp(name, ".", 1) == 0)
 427                 name += 1;
 428         if (strncmp(name, "->", 2) == 0)
 429                 name += 2;
 430
 431         FOR_EACH_PTR(symbol_list, tmp) {
 432                 if (!tmp->ident) {
 433                         sub = get_real_base_type(tmp);
 434                         sub = get_member_from_string(sub->symbol_list, name);
 435                         if (sub)
 436                                 return sub;
 437                         continue;
 438                 }
 439
 440                 if (strcmp(tmp->ident->name, name) == 0)
 441                         return tmp;
 442
 443                 chunk_len = strlen(tmp->ident->name);
 444                 if (strncmp(tmp->ident->name, name, chunk_len) == 0 &&
 445                     (name[chunk_len] == '.' || name[chunk_len] == '-')) {
 446                         sub = get_real_base_type(tmp);
 447                         return get_member_from_string(sub->symbol_list, name + chunk_len);
 448                 }
 449
 450         } END_FOR_EACH_PTR(tmp);
 451
 452         return NULL;
 453 }
 454
 455 struct symbol *get_member_type_from_key(struct expression *expr, char *key)
 456 {
 457         struct symbol *sym;
 458         char *name;
 459
 460         if (strcmp(key, "$$") == 0)
 461                 return get_type(expr);
 462
 463         if (strcmp(key, "*$$") == 0) {
 464                 sym = get_type(expr);
 465                 if (!sym || sym->type != SYM_PTR)
 466                         return NULL;
 467                 return get_real_base_type(sym);
 468         }
 469
 470         name = expr_to_str_sym(expr, &sym);
 471         free_string(name);
 472         if (!sym)
 473                 return NULL;
 474         sym = get_real_base_type(sym);
 475         if (sym->type == SYM_PTR)
 476                 sym = get_real_base_type(sym);
 477
 478         key = key + 2;
 479         sym = get_member_from_string(sym->symbol_list, key);
 480         if (!sym)
 481                 return NULL;
 482         return get_real_base_type(sym);
 483 }