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