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