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