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_void_pointer(struct expression *expr)
 344 {
 345         struct symbol *type;
 346
 347         type = get_type(expr);
 348         if (!type || type->type != SYM_PTR)
 349                 return 0;
 350         type = get_real_base_type(type);
 351         if (type == &void_ctype)
 352                 return 1;
 353         return 0;
 354 }
 355
 356 int is_char_pointer(struct expression *expr)
 357 {
 358         struct symbol *type;
 359
 360         type = get_type(expr);
 361         if (!type || type->type != SYM_PTR)
 362                 return 0;
 363         type = get_real_base_type(type);
 364         if (type == &char_ctype)
 365                 return 1;
 366         return 0;
 367 }
 368
 369 int is_static(struct expression *expr)
 370 {
 371         char *name;
 372         struct symbol *sym;
 373         int ret = 0;
 374
 375         name = expr_to_str_sym(expr, &sym);
 376         if (!name || !sym)
 377                 goto free;
 378
 379         if (sym->ctype.modifiers & MOD_STATIC)
 380                 ret = 1;
 381 free:
 382         free_string(name);
 383         return ret;
 384 }
 385
 386 int types_equiv(struct symbol *one, struct symbol *two)
 387 {
 388         if (!one && !two)
 389                 return 1;
 390         if (!one || !two)
 391                 return 0;
 392         if (one->type != two->type)
 393                 return 0;
 394         if (one->type == SYM_PTR)
 395                 return types_equiv(get_real_base_type(one), get_real_base_type(two));
 396         if (type_positive_bits(one) != type_positive_bits(two))
 397                 return 0;
 398         return 1;
 399 }
 400
 401 int fn_static(void)
 402 {
 403         return !!(cur_func_sym->ctype.modifiers & MOD_STATIC);
 404 }
 405
 406 const char *global_static()
 407 {
 408         if (cur_func_sym->ctype.modifiers & MOD_STATIC)
 409                 return "static";
 410         else
 411                 return "global";
 412 }
 413
 414 struct symbol *cur_func_return_type(void)
 415 {
 416         struct symbol *sym;
 417
 418         sym = get_real_base_type(cur_func_sym);
 419         if (!sym || sym->type != SYM_FN)
 420                 return NULL;
 421         sym = get_real_base_type(sym);
 422         return sym;
 423 }
 424
 425 struct symbol *get_arg_type(struct expression *fn, int arg)
 426 {
 427         struct symbol *fn_type;
 428         struct symbol *tmp;
 429         struct symbol *arg_type;
 430         int i;
 431
 432         fn_type = get_type(fn);
 433         if (!fn_type)
 434                 return NULL;
 435         if (fn_type->type == SYM_PTR)
 436                 fn_type = get_real_base_type(fn_type);
 437         if (fn_type->type != SYM_FN)
 438                 return NULL;
 439
 440         i = 0;
 441         FOR_EACH_PTR(fn_type->arguments, tmp) {
 442                 arg_type = get_real_base_type(tmp);
 443                 if (i == arg) {
 444                         return arg_type;
 445                 }
 446                 i++;
 447         } END_FOR_EACH_PTR(tmp);
 448
 449         return NULL;
 450 }
 451
 452 static struct symbol *get_member_from_string(struct symbol_list *symbol_list, char *name)
 453 {
 454         struct symbol *tmp, *sub;
 455         int chunk_len;
 456
 457         if (strncmp(name, ".", 1) == 0)
 458                 name += 1;
 459         if (strncmp(name, "->", 2) == 0)
 460                 name += 2;
 461
 462         FOR_EACH_PTR(symbol_list, tmp) {
 463                 if (!tmp->ident) {
 464                         sub = get_real_base_type(tmp);
 465                         sub = get_member_from_string(sub->symbol_list, name);
 466                         if (sub)
 467                                 return sub;
 468                         continue;
 469                 }
 470
 471                 if (strcmp(tmp->ident->name, name) == 0)
 472                         return tmp;
 473
 474                 chunk_len = strlen(tmp->ident->name);
 475                 if (strncmp(tmp->ident->name, name, chunk_len) == 0 &&
 476                     (name[chunk_len] == '.' || name[chunk_len] == '-')) {
 477                         sub = get_real_base_type(tmp);
 478                         return get_member_from_string(sub->symbol_list, name + chunk_len);
 479                 }
 480
 481         } END_FOR_EACH_PTR(tmp);
 482
 483         return NULL;
 484 }
 485
 486 struct symbol *get_member_type_from_key(struct expression *expr, char *key)
 487 {
 488         struct symbol *sym;
 489         char *name;
 490
 491         if (strcmp(key, "$$") == 0)
 492                 return get_type(expr);
 493
 494         if (strcmp(key, "*$$") == 0) {
 495                 sym = get_type(expr);
 496                 if (!sym || sym->type != SYM_PTR)
 497                         return NULL;
 498                 return get_real_base_type(sym);
 499         }
 500
 501         name = expr_to_str_sym(expr, &sym);
 502         free_string(name);
 503         if (!sym)
 504                 return NULL;
 505         sym = get_real_base_type(sym);
 506         if (sym->type == SYM_PTR)
 507                 sym = get_real_base_type(sym);
 508
 509         key = key + 2;
 510         sym = get_member_from_string(sym->symbol_list, key);
 511         if (!sym)
 512                 return NULL;
 513         return get_real_base_type(sym);
 514 }