smatch_type.c

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