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 #include "smatch_slist.h"
  25
  26 struct symbol *get_real_base_type(struct symbol *sym)
  27 {
  28         struct symbol *ret;
  29
  30         if (!sym)
  31                 return NULL;
  32         ret = get_base_type(sym);
  33         if (!ret)
  34                 return NULL;
  35         if (ret->type == SYM_RESTRICT || ret->type == SYM_NODE)
  36                 return get_real_base_type(ret);
  37         return ret;
  38 }
  39
  40 int type_bytes(struct symbol *type)
  41 {
  42         int bits;
  43
  44         if (type && type->type == SYM_ARRAY)
  45                 return array_bytes(type);
  46
  47         bits = type_bits(type);
  48         if (bits < 0)
  49                 return 0;
  50         return bits_to_bytes(bits);
  51 }
  52
  53 int array_bytes(struct symbol *type)
  54 {
  55         if (!type || type->type != SYM_ARRAY)
  56                 return 0;
  57         return bits_to_bytes(type->bit_size);
  58 }
  59
  60 static struct symbol *get_binop_type(struct expression *expr)
  61 {
  62         struct symbol *left, *right;
  63
  64         left = get_type(expr->left);
  65         if (!left)
  66                 return NULL;
  67
  68         if (expr->op == SPECIAL_LEFTSHIFT ||
  69             expr->op == SPECIAL_RIGHTSHIFT) {
  70                 if (type_positive_bits(left) < 31)
  71                         return &int_ctype;
  72                 return left;
  73         }
  74         if (left->type == SYM_PTR || left->type == SYM_ARRAY)
  75                 return left;
  76
  77         right = get_type(expr->right);
  78         if (!right)
  79                 return NULL;
  80
  81         if (right->type == SYM_PTR || right->type == SYM_ARRAY)
  82                 return right;
  83
  84         if (type_positive_bits(left) < 31 && type_positive_bits(right) < 31)
  85                 return &int_ctype;
  86
  87         if (type_positive_bits(left) > type_positive_bits(right))
  88                 return left;
  89         return right;
  90 }
  91
  92 static struct symbol *get_type_symbol(struct expression *expr)
  93 {
  94         if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
  95                 return NULL;
  96
  97         return get_real_base_type(expr->symbol);
  98 }
  99
 100 static struct symbol *get_member_symbol(struct symbol_list *symbol_list, struct ident *member)
 101 {
 102         struct symbol *tmp, *sub;
 103
 104         FOR_EACH_PTR(symbol_list, tmp) {
 105                 if (!tmp->ident) {
 106                         sub = get_real_base_type(tmp);
 107                         sub = get_member_symbol(sub->symbol_list, member);
 108                         if (sub)
 109                                 return sub;
 110                         continue;
 111                 }
 112                 if (tmp->ident == member)
 113                         return tmp;
 114         } END_FOR_EACH_PTR(tmp);
 115
 116         return NULL;
 117 }
 118
 119 static struct symbol *get_symbol_from_deref(struct expression *expr)
 120 {
 121         struct ident *member;
 122         struct symbol *sym;
 123
 124         if (!expr || expr->type != EXPR_DEREF)
 125                 return NULL;
 126
 127         member = expr->member;
 128         sym = get_type(expr->deref);
 129         if (!sym) {
 130                 // sm_msg("could not find struct type");
 131                 return NULL;
 132         }
 133         if (sym->type == SYM_PTR)
 134                 sym = get_real_base_type(sym);
 135         sym = get_member_symbol(sym->symbol_list, member);
 136         if (!sym)
 137                 return NULL;
 138         return get_real_base_type(sym);
 139 }
 140
 141 static struct symbol *get_return_type(struct expression *expr)
 142 {
 143         struct symbol *tmp;
 144
 145         tmp = get_type(expr->fn);
 146         if (!tmp)
 147                 return NULL;
 148         /* this is to handle __builtin_constant_p() */
 149         if (tmp->type != SYM_FN)
 150                 tmp = get_base_type(tmp);
 151         return get_real_base_type(tmp);
 152 }
 153
 154 static struct symbol *get_expr_stmt_type(struct statement *stmt)
 155 {
 156         if (stmt->type != STMT_COMPOUND)
 157                 return NULL;
 158         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 159         if (stmt->type == STMT_LABEL)
 160                 stmt = stmt->label_statement;
 161         if (stmt->type != STMT_EXPRESSION)
 162                 return NULL;
 163         return get_type(stmt->expression);
 164 }
 165
 166 static struct symbol *get_select_type(struct expression *expr)
 167 {
 168         struct symbol *one, *two;
 169
 170         one = get_type(expr->cond_true);
 171         two = get_type(expr->cond_false);
 172         if (!one || !two)
 173                 return NULL;
 174         /*
 175          * This is a hack.  If the types are not equiv then we
 176          * really don't know the type.  But I think guessing is
 177          *  probably Ok here.
 178          */
 179         if (type_positive_bits(one) > type_positive_bits(two))
 180                 return one;
 181         return two;
 182 }
 183
 184 struct symbol *get_pointer_type(struct expression *expr)
 185 {
 186         struct symbol *sym;
 187
 188         sym = get_type(expr);
 189         if (!sym)
 190                 return NULL;
 191         if (sym->type == SYM_NODE) {
 192                 sym = get_real_base_type(sym);
 193                 if (!sym)
 194                         return NULL;
 195         }
 196         if (sym->type != SYM_PTR && sym->type != SYM_ARRAY)
 197                 return NULL;
 198         return get_real_base_type(sym);
 199 }
 200
 201 static struct symbol *fake_pointer_sym(struct expression *expr)
 202 {
 203         struct symbol *sym;
 204         struct symbol *base;
 205
 206         sym = alloc_symbol(expr->pos, SYM_PTR);
 207         expr = expr->unop;
 208         base = get_type(expr);
 209         if (!base)
 210                 return NULL;
 211         sym->ctype.base_type = base;
 212         return sym;
 213 }
 214
 215 struct symbol *get_type(struct expression *expr)
 216 {
 217         struct symbol *ret;
 218
 219         expr = strip_parens(expr);
 220         if (!expr)
 221                 return NULL;
 222
 223         if (expr->ctype)
 224                 return expr->ctype;
 225
 226         switch (expr->type) {
 227         case EXPR_STRING:
 228                 ret = &string_ctype;
 229                 break;
 230         case EXPR_SYMBOL:
 231                 ret = get_type_symbol(expr);
 232                 break;
 233         case EXPR_DEREF:
 234                 ret = get_symbol_from_deref(expr);
 235                 break;
 236         case EXPR_PREOP:
 237         case EXPR_POSTOP:
 238                 if (expr->op == '&')
 239                         ret = fake_pointer_sym(expr);
 240                 else if (expr->op == '*')
 241                         ret = get_pointer_type(expr->unop);
 242                 else
 243                         ret = get_type(expr->unop);
 244                 break;
 245         case EXPR_ASSIGNMENT:
 246                 ret = get_type(expr->left);
 247                 break;
 248         case EXPR_CAST:
 249         case EXPR_FORCE_CAST:
 250         case EXPR_IMPLIED_CAST:
 251                 ret = get_real_base_type(expr->cast_type);
 252                 break;
 253         case EXPR_COMPARE:
 254         case EXPR_BINOP:
 255                 ret = get_binop_type(expr);
 256                 break;
 257         case EXPR_CALL:
 258                 ret = get_return_type(expr);
 259                 break;
 260         case EXPR_STATEMENT:
 261                 ret = get_expr_stmt_type(expr->statement);
 262                 break;
 263         case EXPR_CONDITIONAL:
 264         case EXPR_SELECT:
 265                 ret = get_select_type(expr);
 266                 break;
 267         case EXPR_SIZEOF:
 268                 ret = &ulong_ctype;
 269                 break;
 270         case EXPR_LOGICAL:
 271                 ret = &int_ctype;
 272                 break;
 273         default:
 274                 return NULL;
 275         }
 276
 277         if (ret && ret->type == SYM_TYPEOF)
 278                 ret = get_type(ret->initializer);
 279
 280         expr->ctype = ret;
 281         return ret;
 282 }
 283
 284 int type_signed(struct symbol *base_type)
 285 {
 286         if (!base_type)
 287                 return 0;
 288         if (base_type->ctype.modifiers & MOD_SIGNED)
 289                 return 1;
 290         return 0;
 291 }
 292
 293 int expr_unsigned(struct expression *expr)
 294 {
 295         struct symbol *sym;
 296
 297         sym = get_type(expr);
 298         if (!sym)
 299                 return 0;
 300         if (type_unsigned(sym))
 301                 return 1;
 302         return 0;
 303 }
 304
 305 int expr_signed(struct expression *expr)
 306 {
 307         struct symbol *sym;
 308
 309         sym = get_type(expr);
 310         if (!sym)
 311                 return 0;
 312         if (type_signed(sym))
 313                 return 1;
 314         return 0;
 315 }
 316
 317 int returns_unsigned(struct symbol *sym)
 318 {
 319         if (!sym)
 320                 return 0;
 321         sym = get_base_type(sym);
 322         if (!sym || sym->type != SYM_FN)
 323                 return 0;
 324         sym = get_base_type(sym);
 325         return type_unsigned(sym);
 326 }
 327
 328 int is_pointer(struct expression *expr)
 329 {
 330         struct symbol *sym;
 331
 332         sym = get_type(expr);
 333         if (!sym)
 334                 return 0;
 335         if (sym == &string_ctype)
 336                 return 0;
 337         if (sym->type == SYM_PTR)
 338                 return 1;
 339         return 0;
 340 }
 341
 342 int returns_pointer(struct symbol *sym)
 343 {
 344         if (!sym)
 345                 return 0;
 346         sym = get_base_type(sym);
 347         if (!sym || sym->type != SYM_FN)
 348                 return 0;
 349         sym = get_base_type(sym);
 350         if (sym->type == SYM_PTR)
 351                 return 1;
 352         return 0;
 353 }
 354
 355 sval_t sval_type_max(struct symbol *base_type)
 356 {
 357         sval_t ret;
 358
 359         if (!base_type || !type_bits(base_type))
 360                 base_type = &llong_ctype;
 361         ret.type = base_type;
 362
 363         ret.value = (~0ULL) >> (64 - type_positive_bits(base_type));
 364         return ret;
 365 }
 366
 367 sval_t sval_type_min(struct symbol *base_type)
 368 {
 369         sval_t ret;
 370
 371         if (!base_type || !type_bits(base_type))
 372                 base_type = &llong_ctype;
 373         ret.type = base_type;
 374
 375         if (type_unsigned(base_type)) {
 376                 ret.value = 0;
 377                 return ret;
 378         }
 379
 380         ret.value = (~0ULL) << type_positive_bits(base_type);
 381
 382         return ret;
 383 }
 384
 385 int nr_bits(struct expression *expr)
 386 {
 387         struct symbol *type;
 388
 389         type = get_type(expr);
 390         if (!type)
 391                 return 0;
 392         return type_bits(type);
 393 }
 394
 395 int is_void_pointer(struct expression *expr)
 396 {
 397         struct symbol *type;
 398
 399         type = get_type(expr);
 400         if (!type || type->type != SYM_PTR)
 401                 return 0;
 402         type = get_real_base_type(type);
 403         if (type == &void_ctype)
 404                 return 1;
 405         return 0;
 406 }
 407
 408 int is_char_pointer(struct expression *expr)
 409 {
 410         struct symbol *type;
 411
 412         type = get_type(expr);
 413         if (!type || type->type != SYM_PTR)
 414                 return 0;
 415         type = get_real_base_type(type);
 416         if (type == &char_ctype)
 417                 return 1;
 418         return 0;
 419 }
 420
 421 int is_string(struct expression *expr)
 422 {
 423         expr = strip_expr(expr);
 424         if (!expr || expr->type != EXPR_STRING)
 425                 return 0;
 426         if (expr->string)
 427                 return 1;
 428         return 0;
 429 }
 430
 431 int is_static(struct expression *expr)
 432 {
 433         char *name;
 434         struct symbol *sym;
 435         int ret = 0;
 436
 437         name = expr_to_str_sym(expr, &sym);
 438         if (!name || !sym)
 439                 goto free;
 440
 441         if (sym->ctype.modifiers & MOD_STATIC)
 442                 ret = 1;
 443 free:
 444         free_string(name);
 445         return ret;
 446 }
 447
 448 int is_local_variable(struct expression *expr)
 449 {
 450         struct symbol *sym;
 451         char *name;
 452
 453         name = expr_to_var_sym(expr, &sym);
 454         free_string(name);
 455         if (!sym || !sym->scope || !sym->scope->token)
 456                 return 0;
 457         if (cmp_pos(sym->scope->token->pos, cur_func_sym->pos) < 0)
 458                 return 0;
 459         if (is_static(expr))
 460                 return 0;
 461         return 1;
 462 }
 463
 464 int types_equiv(struct symbol *one, struct symbol *two)
 465 {
 466         if (!one && !two)
 467                 return 1;
 468         if (!one || !two)
 469                 return 0;
 470         if (one->type != two->type)
 471                 return 0;
 472         if (one->type == SYM_PTR)
 473                 return types_equiv(get_real_base_type(one), get_real_base_type(two));
 474         if (type_positive_bits(one) != type_positive_bits(two))
 475                 return 0;
 476         return 1;
 477 }
 478
 479 int fn_static(void)
 480 {
 481         return !!(cur_func_sym->ctype.modifiers & MOD_STATIC);
 482 }
 483
 484 const char *global_static(void)
 485 {
 486         if (cur_func_sym->ctype.modifiers & MOD_STATIC)
 487                 return "static";
 488         else
 489                 return "global";
 490 }
 491
 492 struct symbol *cur_func_return_type(void)
 493 {
 494         struct symbol *sym;
 495
 496         sym = get_real_base_type(cur_func_sym);
 497         if (!sym || sym->type != SYM_FN)
 498                 return NULL;
 499         sym = get_real_base_type(sym);
 500         return sym;
 501 }
 502
 503 struct symbol *get_arg_type(struct expression *fn, int arg)
 504 {
 505         struct symbol *fn_type;
 506         struct symbol *tmp;
 507         struct symbol *arg_type;
 508         int i;
 509
 510         fn_type = get_type(fn);
 511         if (!fn_type)
 512                 return NULL;
 513         if (fn_type->type == SYM_PTR)
 514                 fn_type = get_real_base_type(fn_type);
 515         if (fn_type->type != SYM_FN)
 516                 return NULL;
 517
 518         i = 0;
 519         FOR_EACH_PTR(fn_type->arguments, tmp) {
 520                 arg_type = get_real_base_type(tmp);
 521                 if (i == arg) {
 522                         return arg_type;
 523                 }
 524                 i++;
 525         } END_FOR_EACH_PTR(tmp);
 526
 527         return NULL;
 528 }
 529
 530 static struct symbol *get_member_from_string(struct symbol_list *symbol_list, char *name)
 531 {
 532         struct symbol *tmp, *sub;
 533         int chunk_len;
 534
 535         if (strncmp(name, ".", 1) == 0)
 536                 name += 1;
 537         if (strncmp(name, "->", 2) == 0)
 538                 name += 2;
 539
 540         FOR_EACH_PTR(symbol_list, tmp) {
 541                 if (!tmp->ident) {
 542                         sub = get_real_base_type(tmp);
 543                         sub = get_member_from_string(sub->symbol_list, name);
 544                         if (sub)
 545                                 return sub;
 546                         continue;
 547                 }
 548
 549                 if (strcmp(tmp->ident->name, name) == 0)
 550                         return tmp;
 551
 552                 chunk_len = strlen(tmp->ident->name);
 553                 if (strncmp(tmp->ident->name, name, chunk_len) == 0 &&
 554                     (name[chunk_len] == '.' || name[chunk_len] == '-')) {
 555                         sub = get_real_base_type(tmp);
 556                         return get_member_from_string(sub->symbol_list, name + chunk_len);
 557                 }
 558
 559         } END_FOR_EACH_PTR(tmp);
 560
 561         return NULL;
 562 }
 563
 564 struct symbol *get_member_type_from_key(struct expression *expr, char *key)
 565 {
 566         struct symbol *sym;
 567
 568         if (strcmp(key, "$") == 0)
 569                 return get_type(expr);
 570
 571         if (strcmp(key, "*$") == 0) {
 572                 sym = get_type(expr);
 573                 if (!sym || sym->type != SYM_PTR)
 574                         return NULL;
 575                 return get_real_base_type(sym);
 576         }
 577
 578         sym = get_type(expr);
 579         if (!sym)
 580                 return NULL;
 581         if (sym->type == SYM_PTR)
 582                 sym = get_real_base_type(sym);
 583
 584         key = key + 1;
 585         sym = get_member_from_string(sym->symbol_list, key);
 586         if (!sym)
 587                 return NULL;
 588         return get_real_base_type(sym);
 589 }
 590
 591 int is_struct(struct expression *expr)
 592 {
 593         struct symbol *type;
 594
 595         type = get_type(expr);
 596         if (type && type->type == SYM_STRUCT)
 597                 return 1;
 598         return 0;
 599 }
 600
 601 static struct {
 602         struct symbol *sym;
 603         const char *name;
 604 } base_types[] = {
 605         {&bool_ctype, "bool"},
 606         {&void_ctype, "void"},
 607         {&type_ctype, "type"},
 608         {&char_ctype, "char"},
 609         {&schar_ctype, "schar"},
 610         {&uchar_ctype, "uchar"},
 611         {&short_ctype, "short"},
 612         {&sshort_ctype, "sshort"},
 613         {&ushort_ctype, "ushort"},
 614         {&int_ctype, "int"},
 615         {&sint_ctype, "sint"},
 616         {&uint_ctype, "uint"},
 617         {&long_ctype, "long"},
 618         {&slong_ctype, "slong"},
 619         {&ulong_ctype, "ulong"},
 620         {&llong_ctype, "llong"},
 621         {&sllong_ctype, "sllong"},
 622         {&ullong_ctype, "ullong"},
 623         {&lllong_ctype, "lllong"},
 624         {&slllong_ctype, "slllong"},
 625         {&ulllong_ctype, "ulllong"},
 626         {&float_ctype, "float"},
 627         {&double_ctype, "double"},
 628         {&ldouble_ctype, "ldouble"},
 629         {&string_ctype, "string"},
 630         {&ptr_ctype, "ptr"},
 631         {&lazy_ptr_ctype, "lazy_ptr"},
 632         {&incomplete_ctype, "incomplete"},
 633         {&label_ctype, "label"},
 634         {&bad_ctype, "bad"},
 635         {&null_ctype, "null"},
 636 };
 637
 638 static const char *base_type_str(struct symbol *sym)
 639 {
 640         int i;
 641
 642         for (i = 0; i < ARRAY_SIZE(base_types); i++) {
 643                 if (sym == base_types[i].sym)
 644                         return base_types[i].name;
 645         }
 646         return "<unknown>";
 647 }
 648
 649 static int type_str_helper(char *buf, int size, struct symbol *type)
 650 {
 651         int n;
 652
 653         if (!type)
 654                 return snprintf(buf, size, "<unknown>");
 655
 656         if (type->type == SYM_BASETYPE) {
 657                 return snprintf(buf, size, base_type_str(type));
 658         } else if (type->type == SYM_PTR) {
 659                 type = get_real_base_type(type);
 660                 n = type_str_helper(buf, size, type);
 661                 if (n > size)
 662                         return n;
 663                 return n + snprintf(buf + n, size - n, "*");
 664         } else if (type->type == SYM_ARRAY) {
 665                 type = get_real_base_type(type);
 666                 n = type_str_helper(buf, size, type);
 667                 if (n > size)
 668                         return n;
 669                 return n + snprintf(buf + n, size - n, "[]");
 670         } else if (type->type == SYM_STRUCT) {
 671                 return snprintf(buf, size, "struct %s", type->ident ? type->ident->name : "");
 672         } else if (type->type == SYM_UNION) {
 673                 if (type->ident)
 674                         return snprintf(buf, size, "union %s", type->ident->name);
 675                 else
 676                         return snprintf(buf, size, "anonymous union");
 677         } else if (type->type == SYM_FN) {
 678                 struct symbol *arg, *return_type, *arg_type;
 679                 int i;
 680
 681                 return_type = get_real_base_type(type);
 682                 n = type_str_helper(buf, size, return_type);
 683                 if (n > size)
 684                         return n;
 685                 n += snprintf(buf + n, size - n, "(*)(");
 686                 if (n > size)
 687                         return n;
 688
 689                 i = 0;
 690                 FOR_EACH_PTR(type->arguments, arg) {
 691                         if (i++)
 692                                 n += snprintf(buf + n, size - n, ", ");
 693                         if (n > size)
 694                                 return n;
 695                         arg_type = get_real_base_type(arg);
 696                         n += type_str_helper(buf + n, size - n, arg_type);
 697                         if (n > size)
 698                                 return n;
 699                 } END_FOR_EACH_PTR(arg);
 700
 701                 return n + snprintf(buf + n, size - n, ")");
 702         } else if (type->type == SYM_NODE) {
 703                 n = snprintf(buf, size, "node {");
 704                 if (n > size)
 705                         return n;
 706                 type = get_real_base_type(type);
 707                 n += type_str_helper(buf + n, size - n, type);
 708                 if (n > size)
 709                         return n;
 710                 return n + snprintf(buf + n, size - n, "}");
 711         } else {
 712                 return snprintf(buf, size, "<type %d>", type->type);
 713         }
 714 }
 715
 716 char *type_to_str(struct symbol *type)
 717 {
 718         static char buf[256];
 719
 720         buf[0] = '\0';
 721         type_str_helper(buf, sizeof(buf), type);
 722         return buf;
 723 }