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