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         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_signed(struct symbol *base_type)
 289 {
 290         if (!base_type)
 291                 return 0;
 292         if (base_type->ctype.modifiers & MOD_SIGNED)
 293                 return 1;
 294         return 0;
 295 }
 296
 297 int expr_unsigned(struct expression *expr)
 298 {
 299         struct symbol *sym;
 300
 301         sym = get_type(expr);
 302         if (!sym)
 303                 return 0;
 304         if (type_unsigned(sym))
 305                 return 1;
 306         return 0;
 307 }
 308
 309 int expr_signed(struct expression *expr)
 310 {
 311         struct symbol *sym;
 312
 313         sym = get_type(expr);
 314         if (!sym)
 315                 return 0;
 316         if (type_signed(sym))
 317                 return 1;
 318         return 0;
 319 }
 320
 321 int returns_unsigned(struct symbol *sym)
 322 {
 323         if (!sym)
 324                 return 0;
 325         sym = get_base_type(sym);
 326         if (!sym || sym->type != SYM_FN)
 327                 return 0;
 328         sym = get_base_type(sym);
 329         return type_unsigned(sym);
 330 }
 331
 332 int is_pointer(struct expression *expr)
 333 {
 334         struct symbol *sym;
 335
 336         sym = get_type(expr);
 337         if (!sym)
 338                 return 0;
 339         if (sym == &string_ctype)
 340                 return 0;
 341         if (sym->type == SYM_PTR)
 342                 return 1;
 343         return 0;
 344 }
 345
 346 int returns_pointer(struct symbol *sym)
 347 {
 348         if (!sym)
 349                 return 0;
 350         sym = get_base_type(sym);
 351         if (!sym || sym->type != SYM_FN)
 352                 return 0;
 353         sym = get_base_type(sym);
 354         if (sym->type == SYM_PTR)
 355                 return 1;
 356         return 0;
 357 }
 358
 359 sval_t sval_type_max(struct symbol *base_type)
 360 {
 361         sval_t ret;
 362
 363         if (!base_type || !type_bits(base_type))
 364                 base_type = &llong_ctype;
 365         ret.type = base_type;
 366
 367         ret.value = (~0ULL) >> (64 - type_positive_bits(base_type));
 368         return ret;
 369 }
 370
 371 sval_t sval_type_min(struct symbol *base_type)
 372 {
 373         sval_t ret;
 374
 375         if (!base_type || !type_bits(base_type))
 376                 base_type = &llong_ctype;
 377         ret.type = base_type;
 378
 379         if (type_unsigned(base_type)) {
 380                 ret.value = 0;
 381                 return ret;
 382         }
 383
 384         ret.value = (~0ULL) << type_positive_bits(base_type);
 385
 386         return ret;
 387 }
 388
 389 int nr_bits(struct expression *expr)
 390 {
 391         struct symbol *type;
 392
 393         type = get_type(expr);
 394         if (!type)
 395                 return 0;
 396         return type_bits(type);
 397 }
 398
 399 int is_void_pointer(struct expression *expr)
 400 {
 401         struct symbol *type;
 402
 403         type = get_type(expr);
 404         if (!type || type->type != SYM_PTR)
 405                 return 0;
 406         type = get_real_base_type(type);
 407         if (type == &void_ctype)
 408                 return 1;
 409         return 0;
 410 }
 411
 412 int is_char_pointer(struct expression *expr)
 413 {
 414         struct symbol *type;
 415
 416         type = get_type(expr);
 417         if (!type || type->type != SYM_PTR)
 418                 return 0;
 419         type = get_real_base_type(type);
 420         if (type == &char_ctype)
 421                 return 1;
 422         return 0;
 423 }
 424
 425 int is_string(struct expression *expr)
 426 {
 427         expr = strip_expr(expr);
 428         if (!expr || expr->type != EXPR_STRING)
 429                 return 0;
 430         if (expr->string)
 431                 return 1;
 432         return 0;
 433 }
 434
 435 int is_static(struct expression *expr)
 436 {
 437         char *name;
 438         struct symbol *sym;
 439         int ret = 0;
 440
 441         name = expr_to_str_sym(expr, &sym);
 442         if (!name || !sym)
 443                 goto free;
 444
 445         if (sym->ctype.modifiers & MOD_STATIC)
 446                 ret = 1;
 447 free:
 448         free_string(name);
 449         return ret;
 450 }
 451
 452 int is_local_variable(struct expression *expr)
 453 {
 454         struct symbol *sym;
 455         char *name;
 456
 457         name = expr_to_var_sym(expr, &sym);
 458         free_string(name);
 459         if (!sym || !sym->scope || !sym->scope->token || !cur_func_sym)
 460                 return 0;
 461         if (cmp_pos(sym->scope->token->pos, cur_func_sym->pos) < 0)
 462                 return 0;
 463         if (is_static(expr))
 464                 return 0;
 465         return 1;
 466 }
 467
 468 int types_equiv(struct symbol *one, struct symbol *two)
 469 {
 470         if (!one && !two)
 471                 return 1;
 472         if (!one || !two)
 473                 return 0;
 474         if (one->type != two->type)
 475                 return 0;
 476         if (one->type == SYM_PTR)
 477                 return types_equiv(get_real_base_type(one), get_real_base_type(two));
 478         if (type_positive_bits(one) != type_positive_bits(two))
 479                 return 0;
 480         return 1;
 481 }
 482
 483 int fn_static(void)
 484 {
 485         return !!(cur_func_sym->ctype.modifiers & MOD_STATIC);
 486 }
 487
 488 const char *global_static(void)
 489 {
 490         if (cur_func_sym->ctype.modifiers & MOD_STATIC)
 491                 return "static";
 492         else
 493                 return "global";
 494 }
 495
 496 struct symbol *cur_func_return_type(void)
 497 {
 498         struct symbol *sym;
 499
 500         sym = get_real_base_type(cur_func_sym);
 501         if (!sym || sym->type != SYM_FN)
 502                 return NULL;
 503         sym = get_real_base_type(sym);
 504         return sym;
 505 }
 506
 507 struct symbol *get_arg_type(struct expression *fn, int arg)
 508 {
 509         struct symbol *fn_type;
 510         struct symbol *tmp;
 511         struct symbol *arg_type;
 512         int i;
 513
 514         fn_type = get_type(fn);
 515         if (!fn_type)
 516                 return NULL;
 517         if (fn_type->type == SYM_PTR)
 518                 fn_type = get_real_base_type(fn_type);
 519         if (fn_type->type != SYM_FN)
 520                 return NULL;
 521
 522         i = 0;
 523         FOR_EACH_PTR(fn_type->arguments, tmp) {
 524                 arg_type = get_real_base_type(tmp);
 525                 if (i == arg) {
 526                         return arg_type;
 527                 }
 528                 i++;
 529         } END_FOR_EACH_PTR(tmp);
 530
 531         return NULL;
 532 }
 533
 534 static struct symbol *get_member_from_string(struct symbol_list *symbol_list, const char *name)
 535 {
 536         struct symbol *tmp, *sub;
 537         int chunk_len;
 538
 539         if (strncmp(name, ".", 1) == 0)
 540                 name += 1;
 541         if (strncmp(name, "->", 2) == 0)
 542                 name += 2;
 543
 544         FOR_EACH_PTR(symbol_list, tmp) {
 545                 if (!tmp->ident) {
 546                         sub = get_real_base_type(tmp);
 547                         sub = get_member_from_string(sub->symbol_list, name);
 548                         if (sub)
 549                                 return sub;
 550                         continue;
 551                 }
 552
 553                 if (strcmp(tmp->ident->name, name) == 0)
 554                         return tmp;
 555
 556                 chunk_len = strlen(tmp->ident->name);
 557                 if (strncmp(tmp->ident->name, name, chunk_len) == 0 &&
 558                     (name[chunk_len] == '.' || name[chunk_len] == '-')) {
 559                         sub = get_real_base_type(tmp);
 560                         return get_member_from_string(sub->symbol_list, name + chunk_len);
 561                 }
 562
 563         } END_FOR_EACH_PTR(tmp);
 564
 565         return NULL;
 566 }
 567
 568 struct symbol *get_member_type_from_key(struct expression *expr, const char *key)
 569 {
 570         struct symbol *sym;
 571
 572         if (strcmp(key, "$") == 0)
 573                 return get_type(expr);
 574
 575         if (strcmp(key, "*$") == 0) {
 576                 sym = get_type(expr);
 577                 if (!sym || sym->type != SYM_PTR)
 578                         return NULL;
 579                 return get_real_base_type(sym);
 580         }
 581
 582         sym = get_type(expr);
 583         if (!sym)
 584                 return NULL;
 585         if (sym->type == SYM_PTR)
 586                 sym = get_real_base_type(sym);
 587
 588         key = key + 1;
 589         sym = get_member_from_string(sym->symbol_list, key);
 590         if (!sym)
 591                 return NULL;
 592         return get_real_base_type(sym);
 593 }
 594
 595 int is_struct(struct expression *expr)
 596 {
 597         struct symbol *type;
 598
 599         type = get_type(expr);
 600         if (type && type->type == SYM_STRUCT)
 601                 return 1;
 602         return 0;
 603 }
 604
 605 static struct {
 606         struct symbol *sym;
 607         const char *name;
 608 } base_types[] = {
 609         {&bool_ctype, "bool"},
 610         {&void_ctype, "void"},
 611         {&type_ctype, "type"},
 612         {&char_ctype, "char"},
 613         {&schar_ctype, "schar"},
 614         {&uchar_ctype, "uchar"},
 615         {&short_ctype, "short"},
 616         {&sshort_ctype, "sshort"},
 617         {&ushort_ctype, "ushort"},
 618         {&int_ctype, "int"},
 619         {&sint_ctype, "sint"},
 620         {&uint_ctype, "uint"},
 621         {&long_ctype, "long"},
 622         {&slong_ctype, "slong"},
 623         {&ulong_ctype, "ulong"},
 624         {&llong_ctype, "llong"},
 625         {&sllong_ctype, "sllong"},
 626         {&ullong_ctype, "ullong"},
 627         {&lllong_ctype, "lllong"},
 628         {&slllong_ctype, "slllong"},
 629         {&ulllong_ctype, "ulllong"},
 630         {&float_ctype, "float"},
 631         {&double_ctype, "double"},
 632         {&ldouble_ctype, "ldouble"},
 633         {&string_ctype, "string"},
 634         {&ptr_ctype, "ptr"},
 635         {&lazy_ptr_ctype, "lazy_ptr"},
 636         {&incomplete_ctype, "incomplete"},
 637         {&label_ctype, "label"},
 638         {&bad_ctype, "bad"},
 639         {&null_ctype, "null"},
 640 };
 641
 642 static const char *base_type_str(struct symbol *sym)
 643 {
 644         int i;
 645
 646         for (i = 0; i < ARRAY_SIZE(base_types); i++) {
 647                 if (sym == base_types[i].sym)
 648                         return base_types[i].name;
 649         }
 650         return "<unknown>";
 651 }
 652
 653 static int type_str_helper(char *buf, int size, struct symbol *type)
 654 {
 655         int n;
 656
 657         if (!type)
 658                 return snprintf(buf, size, "<unknown>");
 659
 660         if (type->type == SYM_BASETYPE) {
 661                 return snprintf(buf, size, base_type_str(type));
 662         } else if (type->type == SYM_PTR) {
 663                 type = get_real_base_type(type);
 664                 n = type_str_helper(buf, size, type);
 665                 if (n > size)
 666                         return n;
 667                 return n + snprintf(buf + n, size - n, "*");
 668         } else if (type->type == SYM_ARRAY) {
 669                 type = get_real_base_type(type);
 670                 n = type_str_helper(buf, size, type);
 671                 if (n > size)
 672                         return n;
 673                 return n + snprintf(buf + n, size - n, "[]");
 674         } else if (type->type == SYM_STRUCT) {
 675                 return snprintf(buf, size, "struct %s", type->ident ? type->ident->name : "");
 676         } else if (type->type == SYM_UNION) {
 677                 if (type->ident)
 678                         return snprintf(buf, size, "union %s", type->ident->name);
 679                 else
 680                         return snprintf(buf, size, "anonymous union");
 681         } else if (type->type == SYM_FN) {
 682                 struct symbol *arg, *return_type, *arg_type;
 683                 int i;
 684
 685                 return_type = get_real_base_type(type);
 686                 n = type_str_helper(buf, size, return_type);
 687                 if (n > size)
 688                         return n;
 689                 n += snprintf(buf + n, size - n, "(*)(");
 690                 if (n > size)
 691                         return n;
 692
 693                 i = 0;
 694                 FOR_EACH_PTR(type->arguments, arg) {
 695                         if (i++)
 696                                 n += snprintf(buf + n, size - n, ", ");
 697                         if (n > size)
 698                                 return n;
 699                         arg_type = get_real_base_type(arg);
 700                         n += type_str_helper(buf + n, size - n, arg_type);
 701                         if (n > size)
 702                                 return n;
 703                 } END_FOR_EACH_PTR(arg);
 704
 705                 return n + snprintf(buf + n, size - n, ")");
 706         } else if (type->type == SYM_NODE) {
 707                 n = snprintf(buf, size, "node {");
 708                 if (n > size)
 709                         return n;
 710                 type = get_real_base_type(type);
 711                 n += type_str_helper(buf + n, size - n, type);
 712                 if (n > size)
 713                         return n;
 714                 return n + snprintf(buf + n, size - n, "}");
 715         } else {
 716                 return snprintf(buf, size, "<type %d>", type->type);
 717         }
 718 }
 719
 720 char *type_to_str(struct symbol *type)
 721 {
 722         static char buf[256];
 723
 724         buf[0] = '\0';
 725         type_str_helper(buf, sizeof(buf), type);
 726         return buf;
 727 }