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 <ctype.h>
  24 #include "smatch.h"
  25 #include "smatch_slist.h"
  26
  27 struct symbol *get_real_base_type(struct symbol *sym)
  28 {
  29         struct symbol *ret;
  30
  31         if (!sym)
  32                 return NULL;
  33         if (sym->type == SYM_BASETYPE)
  34                 return sym;
  35         ret = get_base_type(sym);
  36         if (!ret)
  37                 return NULL;
  38         if (ret->type == SYM_RESTRICT || ret->type == SYM_NODE)
  39                 return get_real_base_type(ret);
  40         return ret;
  41 }
  42
  43 int type_bytes(struct symbol *type)
  44 {
  45         int bits;
  46
  47         if (type && type->type == SYM_ARRAY)
  48                 return array_bytes(type);
  49
  50         bits = type_bits(type);
  51         if (bits < 0)
  52                 return 0;
  53         return bits_to_bytes(bits);
  54 }
  55
  56 int array_bytes(struct symbol *type)
  57 {
  58         if (!type || type->type != SYM_ARRAY)
  59                 return 0;
  60         if (!type->array_size)
  61                 return 0;
  62         return bits_to_bytes(type->bit_size);
  63 }
  64
  65 bool is_long(struct symbol *type)
  66 {
  67         if (type == &ulong_ctype || type == &long_ctype)
  68                 return true;
  69         return false;
  70 }
  71
  72 bool is_int(struct symbol *type)
  73 {
  74         if (type == &uint_ctype || type == &int_ctype)
  75                 return true;
  76         return false;
  77 }
  78
  79 static struct symbol *get_binop_type(struct expression *expr)
  80 {
  81         struct symbol *left, *right;
  82
  83         left = get_type(expr->left);
  84         if (!left)
  85                 return NULL;
  86
  87         if (expr->op == SPECIAL_LEFTSHIFT ||
  88             expr->op == SPECIAL_RIGHTSHIFT) {
  89                 if (type_positive_bits(left) < 31)
  90                         return &int_ctype;
  91                 return left;
  92         }
  93         right = get_type(expr->right);
  94         if (!right)
  95                 return NULL;
  96
  97         if (type_is_fp(left)) {
  98                 if (type_is_fp(right)) {
  99                         if (type_bits(left) > type_bits(right))
 100                                 return left;
 101                         return right;
 102                 }
 103                 return left;
 104         }
 105
 106         if (type_is_fp(right)) {
 107                 if (type_is_fp(left)) {
 108                         if (type_bits(right) > type_bits(left))
 109                                 return right;
 110                         return left;
 111                 }
 112                 return right;
 113         }
 114
 115         if (expr->op == '-' &&
 116             (is_ptr_type(left) && is_ptr_type(right)))
 117                 return ssize_t_ctype;
 118
 119         if (left->type == SYM_PTR || left->type == SYM_ARRAY)
 120                 return left;
 121         if (right->type == SYM_PTR || right->type == SYM_ARRAY)
 122                 return right;
 123
 124         if (type_positive_bits(left) < 31 && type_positive_bits(right) < 31)
 125                 return &int_ctype;
 126
 127         if (type_positive_bits(left) > type_positive_bits(right))
 128                 return left;
 129         if (is_long(left) && is_int(right))
 130                 return left;
 131         if (is_long(right) && is_int(left))
 132                 return right;
 133         return right;
 134 }
 135
 136 static struct symbol *get_type_symbol(struct expression *expr)
 137 {
 138         struct symbol *type;
 139
 140         if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
 141                 return NULL;
 142
 143         type = get_real_base_type(expr->symbol);
 144         if (type == &autotype_ctype)
 145                 return get_type(expr->symbol->initializer);
 146         return type;
 147 }
 148
 149 static struct symbol *get_member_symbol(struct symbol_list *symbol_list, struct ident *member)
 150 {
 151         struct symbol *tmp, *sub;
 152
 153         FOR_EACH_PTR(symbol_list, tmp) {
 154                 if (!tmp->ident) {
 155                         sub = get_real_base_type(tmp);
 156                         sub = get_member_symbol(sub->symbol_list, member);
 157                         if (sub)
 158                                 return sub;
 159                         continue;
 160                 }
 161                 if (tmp->ident == member)
 162                         return tmp;
 163         } END_FOR_EACH_PTR(tmp);
 164
 165         return NULL;
 166 }
 167
 168 static struct symbol *get_symbol_from_deref(struct expression *expr)
 169 {
 170         struct ident *member;
 171         struct symbol *sym;
 172
 173         if (!expr || expr->type != EXPR_DEREF)
 174                 return NULL;
 175
 176         member = expr->member;
 177         sym = get_type(expr->deref);
 178         if (!sym) {
 179                 // sm_msg("could not find struct type");
 180                 return NULL;
 181         }
 182         if (sym->type == SYM_PTR)
 183                 sym = get_real_base_type(sym);
 184         sym = get_member_symbol(sym->symbol_list, member);
 185         if (!sym)
 186                 return NULL;
 187         return get_real_base_type(sym);
 188 }
 189
 190 static struct symbol *handle__builtin_choose_expr(struct expression *expr)
 191 {
 192         struct expression *const_expr, *expr1, *expr2;
 193         sval_t sval;
 194
 195         const_expr = get_argument_from_call_expr(expr->args, 0);
 196         expr1 = get_argument_from_call_expr(expr->args, 1);
 197         expr2 = get_argument_from_call_expr(expr->args, 2);
 198
 199         if (!get_value(const_expr, &sval) || !expr1 || !expr2)
 200                 return NULL;
 201         if (sval.value)
 202                 return get_type(expr1);
 203         else
 204                 return get_type(expr2);
 205 }
 206
 207 static struct symbol *get_return_type(struct expression *expr)
 208 {
 209         struct symbol *tmp;
 210
 211         if (sym_name_is("__builtin_choose_expr", expr->fn))
 212                 return handle__builtin_choose_expr(expr);
 213
 214         tmp = get_type(expr->fn);
 215         if (!tmp)
 216                 return NULL;
 217         /* this is to handle __builtin_constant_p() */
 218         if (tmp->type != SYM_FN)
 219                 tmp = get_base_type(tmp);
 220         return get_real_base_type(tmp);
 221 }
 222
 223 static struct symbol *get_expr_stmt_type(struct statement *stmt)
 224 {
 225         if (stmt->type != STMT_COMPOUND)
 226                 return NULL;
 227         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 228         if (stmt->type == STMT_LABEL)
 229                 stmt = stmt->label_statement;
 230         if (stmt->type != STMT_EXPRESSION)
 231                 return NULL;
 232         return get_type(stmt->expression);
 233 }
 234
 235 static struct symbol *get_select_type(struct expression *expr)
 236 {
 237         struct symbol *one, *two;
 238
 239         one = get_type(expr->cond_true);
 240         two = get_type(expr->cond_false);
 241         if (!one || !two)
 242                 return NULL;
 243         /*
 244          * This is a hack.  If the types are not equiv then we
 245          * really don't know the type.  But I think guessing is
 246          *  probably Ok here.
 247          */
 248         if (type_positive_bits(one) > type_positive_bits(two))
 249                 return one;
 250         return two;
 251 }
 252
 253 struct symbol *get_pointer_type(struct expression *expr)
 254 {
 255         struct symbol *sym;
 256
 257         sym = get_type(expr);
 258         if (!sym)
 259                 return NULL;
 260         if (sym->type == SYM_NODE) {
 261                 sym = get_real_base_type(sym);
 262                 if (!sym)
 263                         return NULL;
 264         }
 265         if (sym->type != SYM_PTR && sym->type != SYM_ARRAY)
 266                 return NULL;
 267         return get_real_base_type(sym);
 268 }
 269
 270 static struct symbol *fake_pointer_sym(struct expression *expr)
 271 {
 272         struct symbol *sym;
 273         struct symbol *base;
 274
 275         sym = alloc_symbol(expr->pos, SYM_PTR);
 276         expr = expr->unop;
 277         base = get_type(expr);
 278         if (!base)
 279                 return NULL;
 280         sym->ctype.base_type = base;
 281         return sym;
 282 }
 283
 284 static struct symbol *get_type_helper(struct expression *expr)
 285 {
 286         struct symbol *ret;
 287
 288         expr = strip_parens(expr);
 289         if (!expr)
 290                 return NULL;
 291
 292         if (expr->ctype)
 293                 return expr->ctype;
 294
 295         switch (expr->type) {
 296         case EXPR_STRING:
 297                 ret = &string_ctype;
 298                 break;
 299         case EXPR_SYMBOL:
 300                 ret = get_type_symbol(expr);
 301                 break;
 302         case EXPR_DEREF:
 303                 ret = get_symbol_from_deref(expr);
 304                 break;
 305         case EXPR_PREOP:
 306         case EXPR_POSTOP:
 307                 if (expr->op == '&')
 308                         ret = fake_pointer_sym(expr);
 309                 else if (expr->op == '*')
 310                         ret = get_pointer_type(expr->unop);
 311                 else
 312                         ret = get_type(expr->unop);
 313                 break;
 314         case EXPR_ASSIGNMENT:
 315                 ret = get_type(expr->left);
 316                 break;
 317         case EXPR_CAST:
 318         case EXPR_FORCE_CAST:
 319         case EXPR_IMPLIED_CAST:
 320                 ret = get_real_base_type(expr->cast_type);
 321                 break;
 322         case EXPR_COMPARE:
 323         case EXPR_BINOP:
 324                 ret = get_binop_type(expr);
 325                 break;
 326         case EXPR_CALL:
 327                 ret = get_return_type(expr);
 328                 break;
 329         case EXPR_STATEMENT:
 330                 ret = get_expr_stmt_type(expr->statement);
 331                 break;
 332         case EXPR_CONDITIONAL:
 333         case EXPR_SELECT:
 334                 ret = get_select_type(expr);
 335                 break;
 336         case EXPR_SIZEOF:
 337                 ret = &ulong_ctype;
 338                 break;
 339         case EXPR_LOGICAL:
 340                 ret = &int_ctype;
 341                 break;
 342         case EXPR_OFFSETOF:
 343                 ret = &ulong_ctype;
 344                 break;
 345         case EXPR_GENERIC: {
 346                 struct expression *tmp;
 347
 348                 tmp = strip_Generic(expr);
 349                 if (tmp == expr)
 350                         return NULL;
 351                 return get_type_helper(tmp);
 352         }
 353         case EXPR_COMMA:
 354                 return get_type_helper(expr->right);
 355         default:
 356                 return NULL;
 357         }
 358
 359         if (ret && ret->type == SYM_TYPEOF)
 360                 ret = get_type(ret->initializer);
 361
 362         expr->ctype = ret;
 363         return ret;
 364 }
 365
 366 static struct symbol *get_final_type_helper(struct expression *expr)
 367 {
 368         /*
 369          * The problem is that I wrote a bunch of Smatch to think that
 370          * you could do get_type() on an expression and it would give
 371          * you what the comparison was type promoted to.  This is wrong
 372          * but fixing it is a big of work...  Hence this horrible hack.
 373          *
 374          */
 375
 376         expr = strip_parens(expr);
 377         if (!expr)
 378                 return NULL;
 379
 380         if (expr->type == EXPR_COMPARE)
 381                 return &int_ctype;
 382         if (expr->type == EXPR_PREOP && expr->op == '!')
 383                 return &int_ctype;
 384
 385         return NULL;
 386 }
 387
 388 struct symbol *get_type(struct expression *expr)
 389 {
 390         return get_type_helper(expr);
 391 }
 392
 393 struct symbol *get_comparison_type(struct expression *expr)
 394 {
 395         /*
 396          * Eventually we will probably have to figure out how to make get_type()
 397          * return &int_ctype so let's create a helper function to transition to.
 398          */
 399         return get_type_helper(expr);
 400 }
 401
 402 struct symbol *get_final_type(struct expression *expr)
 403 {
 404         struct symbol *ret;
 405
 406         ret = get_final_type_helper(expr);
 407         if (ret)
 408                 return ret;
 409         return get_type_helper(expr);
 410 }
 411
 412 struct symbol *get_promoted_type(struct symbol *left, struct symbol *right)
 413 {
 414         struct symbol *ret = &int_ctype;
 415
 416         if (type_positive_bits(left) > type_positive_bits(ret))
 417                 ret = left;
 418         if (type_positive_bits(right) > type_positive_bits(ret))
 419                 ret = right;
 420
 421         if (type_is_ptr(left))
 422                 ret = left;
 423         if (type_is_ptr(right))
 424                 ret = right;
 425
 426         return ret;
 427 }
 428
 429 int type_signed(struct symbol *base_type)
 430 {
 431         if (!base_type)
 432                 return 0;
 433         if (base_type->ctype.modifiers & MOD_SIGNED)
 434                 return 1;
 435         return 0;
 436 }
 437
 438 int expr_unsigned(struct expression *expr)
 439 {
 440         struct symbol *sym;
 441
 442         sym = get_type(expr);
 443         if (!sym)
 444                 return 0;
 445         if (type_unsigned(sym))
 446                 return 1;
 447         return 0;
 448 }
 449
 450 int expr_signed(struct expression *expr)
 451 {
 452         struct symbol *sym;
 453
 454         sym = get_type(expr);
 455         if (!sym)
 456                 return 0;
 457         if (type_signed(sym))
 458                 return 1;
 459         return 0;
 460 }
 461
 462 int returns_unsigned(struct symbol *sym)
 463 {
 464         if (!sym)
 465                 return 0;
 466         sym = get_base_type(sym);
 467         if (!sym || sym->type != SYM_FN)
 468                 return 0;
 469         sym = get_base_type(sym);
 470         return type_unsigned(sym);
 471 }
 472
 473 int is_pointer(struct expression *expr)
 474 {
 475         return type_is_ptr(get_final_type(expr));
 476 }
 477
 478 bool is_void_ptr(struct symbol *type)
 479 {
 480         if (!type)
 481                 return false;
 482         if (type->type != SYM_PTR)
 483                 return false;
 484         type = get_real_base_type(type);
 485
 486         return types_equiv(type, &void_ctype);
 487 }
 488
 489 int returns_pointer(struct symbol *sym)
 490 {
 491         if (!sym)
 492                 return 0;
 493         sym = get_base_type(sym);
 494         if (!sym || sym->type != SYM_FN)
 495                 return 0;
 496         sym = get_base_type(sym);
 497         if (sym && sym->type == SYM_PTR)
 498                 return 1;
 499         return 0;
 500 }
 501
 502 static sval_t fp_max(struct symbol *type)
 503 {
 504         sval_t ret = { .type = type };
 505
 506         if (type == &float_ctype)
 507                 ret.fvalue = FLT_MAX;
 508         else if (type == &double_ctype)
 509                 ret.dvalue = DBL_MAX;
 510         else
 511                 ret.ldvalue = LDBL_MAX;
 512
 513         return ret;
 514 }
 515
 516 sval_t sval_type_max(struct symbol *base_type)
 517 {
 518         sval_t ret;
 519
 520         if (type_is_fp(base_type))
 521                 return fp_max(base_type);
 522
 523         if (!base_type || !type_bits(base_type))
 524                 base_type = &llong_ctype;
 525         ret.type = base_type;
 526
 527         ret.value = (~0ULL) >> (64 - type_positive_bits(base_type));
 528         return ret;
 529 }
 530
 531 static sval_t fp_min(struct symbol *type)
 532 {
 533         sval_t ret = { .type = type };
 534
 535         if (type == &float_ctype)
 536                 ret.fvalue = -FLT_MAX;
 537         else if (type == &double_ctype)
 538                 ret.dvalue = -DBL_MAX;
 539         else
 540                 ret.ldvalue = -LDBL_MAX;
 541
 542         return ret;
 543 }
 544
 545 sval_t sval_type_min(struct symbol *base_type)
 546 {
 547         sval_t ret;
 548
 549         if (type_is_fp(base_type))
 550                 return fp_min(base_type);
 551
 552         if (!base_type || !type_bits(base_type))
 553                 base_type = &llong_ctype;
 554         ret.type = base_type;
 555
 556         if (type_unsigned(base_type) || is_ptr_type(base_type)) {
 557                 ret.value = 0;
 558                 return ret;
 559         }
 560
 561         ret.value = (~0ULL) << type_positive_bits(base_type);
 562
 563         return ret;
 564 }
 565
 566 int nr_bits(struct expression *expr)
 567 {
 568         struct symbol *type;
 569
 570         type = get_type(expr);
 571         if (!type)
 572                 return 0;
 573         return type_bits(type);
 574 }
 575
 576 int is_void_pointer(struct expression *expr)
 577 {
 578         struct symbol *type;
 579
 580         type = get_type(expr);
 581         if (!type || type->type != SYM_PTR)
 582                 return 0;
 583         type = get_real_base_type(type);
 584         if (type == &void_ctype)
 585                 return 1;
 586         return 0;
 587 }
 588
 589 int is_char_pointer(struct expression *expr)
 590 {
 591         struct symbol *type;
 592
 593         type = get_type(expr);
 594         if (!type || type->type != SYM_PTR)
 595                 return 0;
 596         type = get_real_base_type(type);
 597         if (type == &char_ctype)
 598                 return 1;
 599         return 0;
 600 }
 601
 602 int is_string(struct expression *expr)
 603 {
 604         expr = strip_expr(expr);
 605         if (!expr || expr->type != EXPR_STRING)
 606                 return 0;
 607         if (expr->string)
 608                 return 1;
 609         return 0;
 610 }
 611
 612 bool is_struct_ptr(struct symbol *type)
 613 {
 614         if (!type || type->type != SYM_PTR)
 615                 return false;
 616         type = get_real_base_type(type);
 617         if (!type || type->type != SYM_STRUCT)
 618                 return false;
 619         return true;
 620 }
 621
 622 int is_static(struct expression *expr)
 623 {
 624         char *name;
 625         struct symbol *sym;
 626         int ret = 0;
 627
 628         name = expr_to_str_sym(expr, &sym);
 629         if (!name || !sym)
 630                 goto free;
 631
 632         if (sym->ctype.modifiers & MOD_STATIC)
 633                 ret = 1;
 634 free:
 635         free_string(name);
 636         return ret;
 637 }
 638
 639 static struct expression *get_symbol_expr(struct expression *expr)
 640 {
 641         if (!expr)
 642                 return NULL;
 643         while (expr && expr->type == EXPR_DEREF && expr->op == '.')
 644                 expr = strip_expr(expr->deref);
 645         return expr;
 646 }
 647
 648 bool is_local_variable(struct expression *expr)
 649 {
 650         struct symbol *sym;
 651
 652         expr = get_symbol_expr(expr);
 653         if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
 654                 return false;
 655         sym = expr->symbol;
 656         if (!(sym->ctype.modifiers & MOD_TOPLEVEL))
 657                 return true;
 658         return false;
 659 }
 660
 661 int types_equiv(struct symbol *one, struct symbol *two)
 662 {
 663         if (!one && !two)
 664                 return 1;
 665         if (!one || !two)
 666                 return 0;
 667         if (one->type != two->type)
 668                 return 0;
 669         if (one->type == SYM_PTR)
 670                 return types_equiv(get_real_base_type(one), get_real_base_type(two));
 671         if (type_positive_bits(one) != type_positive_bits(two))
 672                 return 0;
 673         return 1;
 674 }
 675
 676 bool type_fits(struct symbol *type, struct symbol *test)
 677 {
 678         if (!type || !test)
 679                 return false;
 680
 681         if (type == test)
 682                 return true;
 683
 684         if (type_bits(test) > type_bits(type))
 685                 return false;
 686         if (type_signed(test) && !type_signed(type))
 687                 return false;
 688         if (type_positive_bits(test) > type_positive_bits(type))
 689                 return false;
 690         return true;
 691 }
 692
 693 int fn_static(void)
 694 {
 695         return !!(cur_func_sym->ctype.modifiers & MOD_STATIC);
 696 }
 697
 698 const char *global_static(void)
 699 {
 700         if (cur_func_sym->ctype.modifiers & MOD_STATIC)
 701                 return "static";
 702         else
 703                 return "global";
 704 }
 705
 706 struct symbol *cur_func_return_type(void)
 707 {
 708         struct symbol *sym;
 709
 710         sym = get_real_base_type(cur_func_sym);
 711         if (!sym || sym->type != SYM_FN)
 712                 return NULL;
 713         sym = get_real_base_type(sym);
 714         return sym;
 715 }
 716
 717 struct symbol *get_arg_type(struct expression *fn, int arg)
 718 {
 719         struct symbol *fn_type;
 720         struct symbol *tmp;
 721         struct symbol *arg_type;
 722         int i;
 723
 724         fn_type = get_type(fn);
 725         if (!fn_type)
 726                 return NULL;
 727         if (fn_type->type == SYM_PTR)
 728                 fn_type = get_real_base_type(fn_type);
 729         if (fn_type->type != SYM_FN)
 730                 return NULL;
 731
 732         i = 0;
 733         FOR_EACH_PTR(fn_type->arguments, tmp) {
 734                 arg_type = get_real_base_type(tmp);
 735                 if (i == arg) {
 736                         return arg_type;
 737                 }
 738                 i++;
 739         } END_FOR_EACH_PTR(tmp);
 740
 741         return NULL;
 742 }
 743
 744 static struct symbol *get_member_from_string(struct symbol_list *symbol_list, const char *name)
 745 {
 746         struct symbol *tmp, *sub;
 747         int chunk_len;
 748
 749         if (strncmp(name, ".", 1) == 0)
 750                 name += 1;
 751         else if (strncmp(name, "->", 2) == 0)
 752                 name += 2;
 753
 754         FOR_EACH_PTR(symbol_list, tmp) {
 755                 if (!tmp->ident) {
 756                         sub = get_real_base_type(tmp);
 757                         sub = get_member_from_string(sub->symbol_list, name);
 758                         if (sub)
 759                                 return sub;
 760                         continue;
 761                 }
 762
 763                 if (strcmp(tmp->ident->name, name) == 0)
 764                         return tmp;
 765
 766                 chunk_len = tmp->ident->len;
 767                 if (strncmp(tmp->ident->name, name, chunk_len) == 0 &&
 768                     (name[chunk_len] == '.' || name[chunk_len] == '-')) {
 769                         sub = get_real_base_type(tmp);
 770                         if (sub->type == SYM_PTR)
 771                                 sub = get_real_base_type(sub);
 772                         return get_member_from_string(sub->symbol_list, name + chunk_len);
 773                 }
 774
 775         } END_FOR_EACH_PTR(tmp);
 776
 777         return NULL;
 778 }
 779
 780 static struct symbol *get_type_from_container_of_key(struct expression *expr, const char *key)
 781 {
 782         char *new_key;
 783
 784         expr = map_container_of_to_simpler_expr_key(expr, key, &new_key);
 785         if (!expr)
 786                 return NULL;
 787         return get_member_type_from_key(expr, new_key);
 788 }
 789
 790 struct symbol *get_member_type_from_key(struct expression *expr, const char *key)
 791 {
 792         struct symbol *sym;
 793         int star = 0;
 794         int i;
 795
 796         if (strcmp(key, "$") == 0)
 797                 return get_type(expr);
 798
 799         if (strcmp(key, "*$") == 0) {
 800                 sym = get_type(expr);
 801                 if (!sym)
 802                         return NULL;
 803                 if (sym->type != SYM_PTR && sym->type != SYM_ARRAY)
 804                         return NULL;
 805                 return get_real_base_type(sym);
 806         }
 807
 808         if (strstr(key, "<~$"))
 809                 return get_type_from_container_of_key(expr, key);
 810
 811         sym = get_type(expr);
 812         if (!sym)
 813                 return NULL;
 814         if (sym->type == SYM_PTR)
 815                 sym = get_real_base_type(sym);
 816
 817         while (*key == '*') {
 818                 key++;
 819                 star++;
 820         }
 821
 822         if (*key != '$')
 823                 return NULL;
 824         key++;
 825
 826         sym = get_member_from_string(sym->symbol_list, key);
 827         if (!sym)
 828                 return NULL;
 829         if (sym->type == SYM_RESTRICT || sym->type == SYM_NODE)
 830                 sym = get_real_base_type(sym);
 831         for (i = 0; i < star; i++) {
 832                 if (!sym || sym->type != SYM_PTR)
 833                         return NULL;
 834                 sym = get_real_base_type(sym);
 835         }
 836         return sym;
 837 }
 838
 839 struct symbol *get_arg_type_from_key(struct expression *fn, int param, struct expression *arg, const char *key)
 840 {
 841         struct symbol *type;
 842
 843         if (!key)
 844                 return NULL;
 845         if (strcmp(key, "$") == 0)
 846                 return get_arg_type(fn, param);
 847         if (strcmp(key, "*$") == 0) {
 848                 type = get_arg_type(fn, param);
 849                 if (!type || type->type != SYM_PTR)
 850                         return NULL;
 851                 return get_real_base_type(type);
 852         }
 853         return get_member_type_from_key(arg, key);
 854 }
 855
 856 int is_struct(struct expression *expr)
 857 {
 858         struct symbol *type;
 859
 860         type = get_type(expr);
 861         if (type && type->type == SYM_STRUCT)
 862                 return 1;
 863         return 0;
 864 }
 865
 866 static struct {
 867         struct symbol *sym;
 868         const char *name;
 869 } base_types[] = {
 870         {&bool_ctype, "bool"},
 871         {&void_ctype, "void"},
 872         {&type_ctype, "type"},
 873         {&char_ctype, "char"},
 874         {&schar_ctype, "schar"},
 875         {&uchar_ctype, "uchar"},
 876         {&short_ctype, "short"},
 877         {&sshort_ctype, "sshort"},
 878         {&ushort_ctype, "ushort"},
 879         {&int_ctype, "int"},
 880         {&sint_ctype, "sint"},
 881         {&uint_ctype, "uint"},
 882         {&long_ctype, "long"},
 883         {&slong_ctype, "slong"},
 884         {&ulong_ctype, "ulong"},
 885         {&llong_ctype, "llong"},
 886         {&sllong_ctype, "sllong"},
 887         {&ullong_ctype, "ullong"},
 888         {&int128_ctype, "lllong"},
 889         {&sint128_ctype, "slllong"},
 890         {&uint128_ctype, "ulllong"},
 891         {&float_ctype, "float"},
 892         {&double_ctype, "double"},
 893         {&ldouble_ctype, "ldouble"},
 894         {&string_ctype, "string"},
 895         {&ptr_ctype, "ptr"},
 896         {&lazy_ptr_ctype, "lazy_ptr"},
 897         {&incomplete_ctype, "incomplete"},
 898         {&label_ctype, "label"},
 899         {&bad_ctype, "bad"},
 900         {&null_ctype, "null"},
 901 };
 902
 903 static const char *base_type_str(struct symbol *sym)
 904 {
 905         int i;
 906
 907         for (i = 0; i < ARRAY_SIZE(base_types); i++) {
 908                 if (sym == base_types[i].sym)
 909                         return base_types[i].name;
 910         }
 911         return "<unknown>";
 912 }
 913
 914 static int type_str_helper(char *buf, int size, struct symbol *type)
 915 {
 916         int n;
 917
 918         if (!type)
 919                 return snprintf(buf, size, "<null type>");
 920
 921         if (type->type == SYM_BASETYPE) {
 922                 return snprintf(buf, size, "%s", base_type_str(type));
 923         } else if (type->type == SYM_PTR) {
 924                 type = get_real_base_type(type);
 925                 n = type_str_helper(buf, size, type);
 926                 if (n > size)
 927                         return n;
 928                 return n + snprintf(buf + n, size - n, "*");
 929         } else if (type->type == SYM_ARRAY) {
 930                 type = get_real_base_type(type);
 931                 n = type_str_helper(buf, size, type);
 932                 if (n > size)
 933                         return n;
 934                 return n + snprintf(buf + n, size - n, "[]");
 935         } else if (type->type == SYM_STRUCT) {
 936                 return snprintf(buf, size, "struct %s", type->ident ? type->ident->name : "");
 937         } else if (type->type == SYM_UNION) {
 938                 if (type->ident)
 939                         return snprintf(buf, size, "union %s", type->ident->name);
 940                 else
 941                         return snprintf(buf, size, "anonymous union");
 942         } else if (type->type == SYM_FN) {
 943                 struct symbol *arg, *return_type, *arg_type;
 944                 int i;
 945
 946                 return_type = get_real_base_type(type);
 947                 n = type_str_helper(buf, size, return_type);
 948                 if (n > size)
 949                         return n;
 950                 n += snprintf(buf + n, size - n, "(*)(");
 951                 if (n > size)
 952                         return n;
 953
 954                 i = 0;
 955                 FOR_EACH_PTR(type->arguments, arg) {
 956                         if (i++)
 957                                 n += snprintf(buf + n, size - n, ", ");
 958                         if (n > size)
 959                                 return n;
 960                         arg_type = get_real_base_type(arg);
 961                         n += type_str_helper(buf + n, size - n, arg_type);
 962                         if (n > size)
 963                                 return n;
 964                 } END_FOR_EACH_PTR(arg);
 965
 966                 return n + snprintf(buf + n, size - n, ")");
 967         } else if (type->type == SYM_NODE) {
 968                 n = snprintf(buf, size, "node {");
 969                 if (n > size)
 970                         return n;
 971                 type = get_real_base_type(type);
 972                 n += type_str_helper(buf + n, size - n, type);
 973                 if (n > size)
 974                         return n;
 975                 return n + snprintf(buf + n, size - n, "}");
 976         } else if (type->type == SYM_ENUM) {
 977                 return snprintf(buf, size, "enum %s", type->ident ? type->ident->name : "<unknown>");
 978         } else {
 979                 return snprintf(buf, size, "<type %d>", type->type);
 980         }
 981 }
 982
 983 char *type_to_str(struct symbol *type)
 984 {
 985         static char buf[256];
 986
 987         buf[0] = '\0';
 988         type_str_helper(buf, sizeof(buf), type);
 989         return alloc_sname(buf);
 990 }