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                 return get_type_helper(strip_Generic(expr));
 347         case EXPR_COMMA:
 348                 return get_type_helper(expr->right);
 349         default:
 350                 return NULL;
 351         }
 352
 353         if (ret && ret->type == SYM_TYPEOF)
 354                 ret = get_type(ret->initializer);
 355
 356         expr->ctype = ret;
 357         return ret;
 358 }
 359
 360 static struct symbol *get_final_type_helper(struct expression *expr)
 361 {
 362         /*
 363          * The problem is that I wrote a bunch of Smatch to think that
 364          * you could do get_type() on an expression and it would give
 365          * you what the comparison was type promoted to.  This is wrong
 366          * but fixing it is a big of work...  Hence this horrible hack.
 367          *
 368          */
 369
 370         expr = strip_parens(expr);
 371         if (!expr)
 372                 return NULL;
 373
 374         if (expr->type == EXPR_COMPARE)
 375                 return &int_ctype;
 376         if (expr->type == EXPR_PREOP && expr->op == '!')
 377                 return &int_ctype;
 378
 379         return NULL;
 380 }
 381
 382 struct symbol *get_type(struct expression *expr)
 383 {
 384         return get_type_helper(expr);
 385 }
 386
 387 struct symbol *get_comparison_type(struct expression *expr)
 388 {
 389         /*
 390          * Eventually we will probably have to figure out how to make get_type()
 391          * return &int_ctype so let's create a helper function to transition to.
 392          */
 393         return get_type_helper(expr);
 394 }
 395
 396 struct symbol *get_final_type(struct expression *expr)
 397 {
 398         struct symbol *ret;
 399
 400         ret = get_final_type_helper(expr);
 401         if (ret)
 402                 return ret;
 403         return get_type_helper(expr);
 404 }
 405
 406 struct symbol *get_promoted_type(struct symbol *left, struct symbol *right)
 407 {
 408         struct symbol *ret = &int_ctype;
 409
 410         if (type_positive_bits(left) > type_positive_bits(ret))
 411                 ret = left;
 412         if (type_positive_bits(right) > type_positive_bits(ret))
 413                 ret = right;
 414
 415         if (type_is_ptr(left))
 416                 ret = left;
 417         if (type_is_ptr(right))
 418                 ret = right;
 419
 420         return ret;
 421 }
 422
 423 int type_signed(struct symbol *base_type)
 424 {
 425         if (!base_type)
 426                 return 0;
 427         if (base_type->ctype.modifiers & MOD_SIGNED)
 428                 return 1;
 429         return 0;
 430 }
 431
 432 int expr_unsigned(struct expression *expr)
 433 {
 434         struct symbol *sym;
 435
 436         sym = get_type(expr);
 437         if (!sym)
 438                 return 0;
 439         if (type_unsigned(sym))
 440                 return 1;
 441         return 0;
 442 }
 443
 444 int expr_signed(struct expression *expr)
 445 {
 446         struct symbol *sym;
 447
 448         sym = get_type(expr);
 449         if (!sym)
 450                 return 0;
 451         if (type_signed(sym))
 452                 return 1;
 453         return 0;
 454 }
 455
 456 int returns_unsigned(struct symbol *sym)
 457 {
 458         if (!sym)
 459                 return 0;
 460         sym = get_base_type(sym);
 461         if (!sym || sym->type != SYM_FN)
 462                 return 0;
 463         sym = get_base_type(sym);
 464         return type_unsigned(sym);
 465 }
 466
 467 int is_pointer(struct expression *expr)
 468 {
 469         return type_is_ptr(get_final_type(expr));
 470 }
 471
 472 bool is_void_ptr(struct symbol *type)
 473 {
 474         if (!type)
 475                 return false;
 476         if (type->type != SYM_PTR)
 477                 return false;
 478         type = get_real_base_type(type);
 479
 480         return types_equiv(type, &void_ctype);
 481 }
 482
 483 int returns_pointer(struct symbol *sym)
 484 {
 485         if (!sym)
 486                 return 0;
 487         sym = get_base_type(sym);
 488         if (!sym || sym->type != SYM_FN)
 489                 return 0;
 490         sym = get_base_type(sym);
 491         if (sym && sym->type == SYM_PTR)
 492                 return 1;
 493         return 0;
 494 }
 495
 496 static sval_t fp_max(struct symbol *type)
 497 {
 498         sval_t ret = { .type = type };
 499
 500         if (type == &float_ctype)
 501                 ret.fvalue = FLT_MAX;
 502         else if (type == &double_ctype)
 503                 ret.dvalue = DBL_MAX;
 504         else
 505                 ret.ldvalue = LDBL_MAX;
 506
 507         return ret;
 508 }
 509
 510 sval_t sval_type_max(struct symbol *base_type)
 511 {
 512         sval_t ret;
 513
 514         if (type_is_fp(base_type))
 515                 return fp_max(base_type);
 516
 517         if (!base_type || !type_bits(base_type))
 518                 base_type = &llong_ctype;
 519         ret.type = base_type;
 520
 521         ret.value = (~0ULL) >> (64 - type_positive_bits(base_type));
 522         return ret;
 523 }
 524
 525 static sval_t fp_min(struct symbol *type)
 526 {
 527         sval_t ret = { .type = type };
 528
 529         if (type == &float_ctype)
 530                 ret.fvalue = -FLT_MAX;
 531         else if (type == &double_ctype)
 532                 ret.dvalue = -DBL_MAX;
 533         else
 534                 ret.ldvalue = -LDBL_MAX;
 535
 536         return ret;
 537 }
 538
 539 sval_t sval_type_min(struct symbol *base_type)
 540 {
 541         sval_t ret;
 542
 543         if (type_is_fp(base_type))
 544                 return fp_min(base_type);
 545
 546         if (!base_type || !type_bits(base_type))
 547                 base_type = &llong_ctype;
 548         ret.type = base_type;
 549
 550         if (type_unsigned(base_type) || is_ptr_type(base_type)) {
 551                 ret.value = 0;
 552                 return ret;
 553         }
 554
 555         ret.value = (~0ULL) << type_positive_bits(base_type);
 556
 557         return ret;
 558 }
 559
 560 int nr_bits(struct expression *expr)
 561 {
 562         struct symbol *type;
 563
 564         type = get_type(expr);
 565         if (!type)
 566                 return 0;
 567         return type_bits(type);
 568 }
 569
 570 int is_void_pointer(struct expression *expr)
 571 {
 572         struct symbol *type;
 573
 574         type = get_type(expr);
 575         if (!type || type->type != SYM_PTR)
 576                 return 0;
 577         type = get_real_base_type(type);
 578         if (type == &void_ctype)
 579                 return 1;
 580         return 0;
 581 }
 582
 583 int is_char_pointer(struct expression *expr)
 584 {
 585         struct symbol *type;
 586
 587         type = get_type(expr);
 588         if (!type || type->type != SYM_PTR)
 589                 return 0;
 590         type = get_real_base_type(type);
 591         if (type == &char_ctype)
 592                 return 1;
 593         return 0;
 594 }
 595
 596 int is_string(struct expression *expr)
 597 {
 598         expr = strip_expr(expr);
 599         if (!expr || expr->type != EXPR_STRING)
 600                 return 0;
 601         if (expr->string)
 602                 return 1;
 603         return 0;
 604 }
 605
 606 bool is_struct_ptr(struct symbol *type)
 607 {
 608         if (!type || type->type != SYM_PTR)
 609                 return false;
 610         type = get_real_base_type(type);
 611         if (!type || type->type != SYM_STRUCT)
 612                 return false;
 613         return true;
 614 }
 615
 616 int is_static(struct expression *expr)
 617 {
 618         char *name;
 619         struct symbol *sym;
 620         int ret = 0;
 621
 622         name = expr_to_str_sym(expr, &sym);
 623         if (!name || !sym)
 624                 goto free;
 625
 626         if (sym->ctype.modifiers & MOD_STATIC)
 627                 ret = 1;
 628 free:
 629         free_string(name);
 630         return ret;
 631 }
 632
 633 static struct expression *get_symbol_expr(struct expression *expr)
 634 {
 635         if (!expr)
 636                 return NULL;
 637         while (expr && expr->type == EXPR_DEREF && expr->op == '.')
 638                 expr = strip_expr(expr->deref);
 639         return expr;
 640 }
 641
 642 bool is_local_variable(struct expression *expr)
 643 {
 644         struct symbol *sym;
 645
 646         expr = get_symbol_expr(expr);
 647         if (!expr || expr->type != EXPR_SYMBOL || !expr->symbol)
 648                 return false;
 649         sym = expr->symbol;
 650         if (!(sym->ctype.modifiers & MOD_TOPLEVEL))
 651                 return true;
 652         return false;
 653 }
 654
 655 int types_equiv(struct symbol *one, struct symbol *two)
 656 {
 657         if (!one && !two)
 658                 return 1;
 659         if (!one || !two)
 660                 return 0;
 661         if (one->type != two->type)
 662                 return 0;
 663         if (one->type == SYM_PTR)
 664                 return types_equiv(get_real_base_type(one), get_real_base_type(two));
 665         if (type_positive_bits(one) != type_positive_bits(two))
 666                 return 0;
 667         return 1;
 668 }
 669
 670 bool type_fits(struct symbol *type, struct symbol *test)
 671 {
 672         if (!type || !test)
 673                 return false;
 674
 675         if (type == test)
 676                 return true;
 677
 678         if (type_bits(test) > type_bits(type))
 679                 return false;
 680         if (type_signed(test) && !type_signed(type))
 681                 return false;
 682         if (type_positive_bits(test) > type_positive_bits(type))
 683                 return false;
 684         return true;
 685 }
 686
 687 int fn_static(void)
 688 {
 689         return !!(cur_func_sym->ctype.modifiers & MOD_STATIC);
 690 }
 691
 692 const char *global_static(void)
 693 {
 694         if (cur_func_sym->ctype.modifiers & MOD_STATIC)
 695                 return "static";
 696         else
 697                 return "global";
 698 }
 699
 700 struct symbol *cur_func_return_type(void)
 701 {
 702         struct symbol *sym;
 703
 704         sym = get_real_base_type(cur_func_sym);
 705         if (!sym || sym->type != SYM_FN)
 706                 return NULL;
 707         sym = get_real_base_type(sym);
 708         return sym;
 709 }
 710
 711 struct symbol *get_arg_type(struct expression *fn, int arg)
 712 {
 713         struct symbol *fn_type;
 714         struct symbol *tmp;
 715         struct symbol *arg_type;
 716         int i;
 717
 718         fn_type = get_type(fn);
 719         if (!fn_type)
 720                 return NULL;
 721         if (fn_type->type == SYM_PTR)
 722                 fn_type = get_real_base_type(fn_type);
 723         if (fn_type->type != SYM_FN)
 724                 return NULL;
 725
 726         i = 0;
 727         FOR_EACH_PTR(fn_type->arguments, tmp) {
 728                 arg_type = get_real_base_type(tmp);
 729                 if (i == arg) {
 730                         return arg_type;
 731                 }
 732                 i++;
 733         } END_FOR_EACH_PTR(tmp);
 734
 735         return NULL;
 736 }
 737
 738 static struct symbol *get_member_from_string(struct symbol_list *symbol_list, const char *name)
 739 {
 740         struct symbol *tmp, *sub;
 741         int chunk_len;
 742
 743         if (strncmp(name, ".", 1) == 0)
 744                 name += 1;
 745         else if (strncmp(name, "->", 2) == 0)
 746                 name += 2;
 747
 748         FOR_EACH_PTR(symbol_list, tmp) {
 749                 if (!tmp->ident) {
 750                         sub = get_real_base_type(tmp);
 751                         sub = get_member_from_string(sub->symbol_list, name);
 752                         if (sub)
 753                                 return sub;
 754                         continue;
 755                 }
 756
 757                 if (strcmp(tmp->ident->name, name) == 0)
 758                         return tmp;
 759
 760                 chunk_len = tmp->ident->len;
 761                 if (strncmp(tmp->ident->name, name, chunk_len) == 0 &&
 762                     (name[chunk_len] == '.' || name[chunk_len] == '-')) {
 763                         sub = get_real_base_type(tmp);
 764                         if (sub->type == SYM_PTR)
 765                                 sub = get_real_base_type(sub);
 766                         return get_member_from_string(sub->symbol_list, name + chunk_len);
 767                 }
 768
 769         } END_FOR_EACH_PTR(tmp);
 770
 771         return NULL;
 772 }
 773
 774 static struct symbol *get_type_from_container_of_key(struct expression *expr, const char *key)
 775 {
 776         char *new_key;
 777
 778         expr = map_container_of_to_simpler_expr_key(expr, key, &new_key);
 779         if (!expr)
 780                 return NULL;
 781         return get_member_type_from_key(expr, new_key);
 782 }
 783
 784 struct symbol *get_member_type_from_key(struct expression *expr, const char *key)
 785 {
 786         struct symbol *sym;
 787         int star = 0;
 788         int i;
 789
 790         if (strcmp(key, "$") == 0)
 791                 return get_type(expr);
 792
 793         if (strcmp(key, "*$") == 0) {
 794                 sym = get_type(expr);
 795                 if (!sym)
 796                         return NULL;
 797                 if (sym->type != SYM_PTR && sym->type != SYM_ARRAY)
 798                         return NULL;
 799                 return get_real_base_type(sym);
 800         }
 801
 802         if (strstr(key, "<~$"))
 803                 return get_type_from_container_of_key(expr, key);
 804
 805         sym = get_type(expr);
 806         if (!sym)
 807                 return NULL;
 808         if (sym->type == SYM_PTR)
 809                 sym = get_real_base_type(sym);
 810
 811         while (*key == '*') {
 812                 key++;
 813                 star++;
 814         }
 815
 816         if (*key != '$')
 817                 return NULL;
 818         key++;
 819
 820         sym = get_member_from_string(sym->symbol_list, key);
 821         if (!sym)
 822                 return NULL;
 823         if (sym->type == SYM_RESTRICT || sym->type == SYM_NODE)
 824                 sym = get_real_base_type(sym);
 825         for (i = 0; i < star; i++) {
 826                 if (!sym || sym->type != SYM_PTR)
 827                         return NULL;
 828                 sym = get_real_base_type(sym);
 829         }
 830         return sym;
 831 }
 832
 833 struct symbol *get_arg_type_from_key(struct expression *fn, int param, struct expression *arg, const char *key)
 834 {
 835         struct symbol *type;
 836
 837         if (!key)
 838                 return NULL;
 839         if (strcmp(key, "$") == 0)
 840                 return get_arg_type(fn, param);
 841         if (strcmp(key, "*$") == 0) {
 842                 type = get_arg_type(fn, param);
 843                 if (!type || type->type != SYM_PTR)
 844                         return NULL;
 845                 return get_real_base_type(type);
 846         }
 847         return get_member_type_from_key(arg, key);
 848 }
 849
 850 int is_struct(struct expression *expr)
 851 {
 852         struct symbol *type;
 853
 854         type = get_type(expr);
 855         if (type && type->type == SYM_STRUCT)
 856                 return 1;
 857         return 0;
 858 }
 859
 860 static struct {
 861         struct symbol *sym;
 862         const char *name;
 863 } base_types[] = {
 864         {&bool_ctype, "bool"},
 865         {&void_ctype, "void"},
 866         {&type_ctype, "type"},
 867         {&char_ctype, "char"},
 868         {&schar_ctype, "schar"},
 869         {&uchar_ctype, "uchar"},
 870         {&short_ctype, "short"},
 871         {&sshort_ctype, "sshort"},
 872         {&ushort_ctype, "ushort"},
 873         {&int_ctype, "int"},
 874         {&sint_ctype, "sint"},
 875         {&uint_ctype, "uint"},
 876         {&long_ctype, "long"},
 877         {&slong_ctype, "slong"},
 878         {&ulong_ctype, "ulong"},
 879         {&llong_ctype, "llong"},
 880         {&sllong_ctype, "sllong"},
 881         {&ullong_ctype, "ullong"},
 882         {&int128_ctype, "lllong"},
 883         {&sint128_ctype, "slllong"},
 884         {&uint128_ctype, "ulllong"},
 885         {&float_ctype, "float"},
 886         {&double_ctype, "double"},
 887         {&ldouble_ctype, "ldouble"},
 888         {&string_ctype, "string"},
 889         {&ptr_ctype, "ptr"},
 890         {&lazy_ptr_ctype, "lazy_ptr"},
 891         {&incomplete_ctype, "incomplete"},
 892         {&label_ctype, "label"},
 893         {&bad_ctype, "bad"},
 894         {&null_ctype, "null"},
 895 };
 896
 897 static const char *base_type_str(struct symbol *sym)
 898 {
 899         int i;
 900
 901         for (i = 0; i < ARRAY_SIZE(base_types); i++) {
 902                 if (sym == base_types[i].sym)
 903                         return base_types[i].name;
 904         }
 905         return "<unknown>";
 906 }
 907
 908 static int type_str_helper(char *buf, int size, struct symbol *type)
 909 {
 910         int n;
 911
 912         if (!type)
 913                 return snprintf(buf, size, "<null type>");
 914
 915         if (type->type == SYM_BASETYPE) {
 916                 return snprintf(buf, size, "%s", base_type_str(type));
 917         } else if (type->type == SYM_PTR) {
 918                 type = get_real_base_type(type);
 919                 n = type_str_helper(buf, size, type);
 920                 if (n > size)
 921                         return n;
 922                 return n + snprintf(buf + n, size - n, "*");
 923         } else if (type->type == SYM_ARRAY) {
 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_STRUCT) {
 930                 return snprintf(buf, size, "struct %s", type->ident ? type->ident->name : "");
 931         } else if (type->type == SYM_UNION) {
 932                 if (type->ident)
 933                         return snprintf(buf, size, "union %s", type->ident->name);
 934                 else
 935                         return snprintf(buf, size, "anonymous union");
 936         } else if (type->type == SYM_FN) {
 937                 struct symbol *arg, *return_type, *arg_type;
 938                 int i;
 939
 940                 return_type = get_real_base_type(type);
 941                 n = type_str_helper(buf, size, return_type);
 942                 if (n > size)
 943                         return n;
 944                 n += snprintf(buf + n, size - n, "(*)(");
 945                 if (n > size)
 946                         return n;
 947
 948                 i = 0;
 949                 FOR_EACH_PTR(type->arguments, arg) {
 950                         if (i++)
 951                                 n += snprintf(buf + n, size - n, ", ");
 952                         if (n > size)
 953                                 return n;
 954                         arg_type = get_real_base_type(arg);
 955                         n += type_str_helper(buf + n, size - n, arg_type);
 956                         if (n > size)
 957                                 return n;
 958                 } END_FOR_EACH_PTR(arg);
 959
 960                 return n + snprintf(buf + n, size - n, ")");
 961         } else if (type->type == SYM_NODE) {
 962                 n = snprintf(buf, size, "node {");
 963                 if (n > size)
 964                         return n;
 965                 type = get_real_base_type(type);
 966                 n += type_str_helper(buf + n, size - n, type);
 967                 if (n > size)
 968                         return n;
 969                 return n + snprintf(buf + n, size - n, "}");
 970         } else if (type->type == SYM_ENUM) {
 971                 return snprintf(buf, size, "enum %s", type->ident ? type->ident->name : "<unknown>");
 972         } else {
 973                 return snprintf(buf, size, "<type %d>", type->type);
 974         }
 975 }
 976
 977 char *type_to_str(struct symbol *type)
 978 {
 979         static char buf[256];
 980
 981         buf[0] = '\0';
 982         type_str_helper(buf, sizeof(buf), type);
 983         return alloc_sname(buf);
 984 }