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