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