nsz Git - cparser/blob - type.c

   1 /*
   2  * This file is part of cparser.
   3  * Copyright (C) 2007-2008 Matthias Braun <matze@braunis.de>
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  18  * 02111-1307, USA.
  19  */
  20 #include <config.h>
  21
  22 #include <stdio.h>
  23 #include <assert.h>
  24
  25 #include "type_t.h"
  26 #include "types.h"
  27 #include "entity_t.h"
  28 #include "symbol_t.h"
  29 #include "type_hash.h"
  30 #include "adt/error.h"
  31 #include "adt/util.h"
  32 #include "lang_features.h"
  33 #include "warning.h"
  34 #include "diagnostic.h"
  35
  36 static struct obstack   _type_obst;
  37 static FILE            *out;
  38 struct obstack         *type_obst                 = &_type_obst;
  39 static int              type_visited              = 0;
  40 static bool             print_implicit_array_size = false;
  41
  42 static void intern_print_type_pre(const type_t *type);
  43 static void intern_print_type_post(const type_t *type);
  44
  45 typedef struct atomic_type_properties_t atomic_type_properties_t;
  46 struct atomic_type_properties_t {
  47         unsigned   size;              /**< type size in bytes */
  48         unsigned   alignment;         /**< type alignment in bytes */
  49         unsigned   flags;             /**< type flags from atomic_type_flag_t */
  50 };
  51
  52 /**
  53  * Properties of atomic types.
  54  */
  55 static atomic_type_properties_t atomic_type_properties[ATOMIC_TYPE_LAST+1] = {
  56         //ATOMIC_TYPE_INVALID = 0,
  57         [ATOMIC_TYPE_VOID] = {
  58                 .size       = 0,
  59                 .alignment  = 0,
  60                 .flags      = ATOMIC_TYPE_FLAG_NONE
  61         },
  62         [ATOMIC_TYPE_WCHAR_T] = {
  63                 .size       = (unsigned)-1,
  64                 .alignment  = (unsigned)-1,
  65                 /* signed flag will be set when known */
  66                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC,
  67         },
  68         [ATOMIC_TYPE_CHAR] = {
  69                 .size       = 1,
  70                 .alignment  = 1,
  71                 /* signed flag will be set when known */
  72                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC,
  73         },
  74         [ATOMIC_TYPE_SCHAR] = {
  75                 .size       = 1,
  76                 .alignment  = 1,
  77                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC
  78                               | ATOMIC_TYPE_FLAG_SIGNED,
  79         },
  80         [ATOMIC_TYPE_UCHAR] = {
  81                 .size       = 1,
  82                 .alignment  = 1,
  83                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC,
  84         },
  85         [ATOMIC_TYPE_SHORT] = {
  86                 .size       = 2,
  87                 .alignment  = 2,
  88                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC
  89                               | ATOMIC_TYPE_FLAG_SIGNED
  90         },
  91         [ATOMIC_TYPE_USHORT] = {
  92                 .size       = 2,
  93                 .alignment  = 2,
  94                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC,
  95         },
  96         [ATOMIC_TYPE_INT] = {
  97                 .size       = (unsigned) -1,
  98                 .alignment  = (unsigned) -1,
  99                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC
 100                               | ATOMIC_TYPE_FLAG_SIGNED,
 101         },
 102         [ATOMIC_TYPE_UINT] = {
 103                 .size       = (unsigned) -1,
 104                 .alignment  = (unsigned) -1,
 105                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC,
 106         },
 107         [ATOMIC_TYPE_LONG] = {
 108                 .size       = (unsigned) -1,
 109                 .alignment  = (unsigned) -1,
 110                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC
 111                               | ATOMIC_TYPE_FLAG_SIGNED,
 112         },
 113         [ATOMIC_TYPE_ULONG] = {
 114                 .size       = (unsigned) -1,
 115                 .alignment  = (unsigned) -1,
 116                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC,
 117         },
 118         [ATOMIC_TYPE_LONGLONG] = {
 119                 .size       = (unsigned) -1,
 120                 .alignment  = (unsigned) -1,
 121                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC
 122                               | ATOMIC_TYPE_FLAG_SIGNED,
 123         },
 124         [ATOMIC_TYPE_ULONGLONG] = {
 125                 .size       = (unsigned) -1,
 126                 .alignment  = (unsigned) -1,
 127                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC,
 128         },
 129         [ATOMIC_TYPE_BOOL] = {
 130                 .size       = (unsigned) -1,
 131                 .alignment  = (unsigned) -1,
 132                 .flags      = ATOMIC_TYPE_FLAG_INTEGER | ATOMIC_TYPE_FLAG_ARITHMETIC,
 133         },
 134         [ATOMIC_TYPE_FLOAT] = {
 135                 .size       = 4,
 136                 .alignment  = (unsigned) -1,
 137                 .flags      = ATOMIC_TYPE_FLAG_FLOAT | ATOMIC_TYPE_FLAG_ARITHMETIC
 138                               | ATOMIC_TYPE_FLAG_SIGNED,
 139         },
 140         [ATOMIC_TYPE_DOUBLE] = {
 141                 .size       = 8,
 142                 .alignment  = (unsigned) -1,
 143                 .flags      = ATOMIC_TYPE_FLAG_FLOAT | ATOMIC_TYPE_FLAG_ARITHMETIC
 144                               | ATOMIC_TYPE_FLAG_SIGNED,
 145         },
 146         [ATOMIC_TYPE_LONG_DOUBLE] = {
 147                 .size       = 12,
 148                 .alignment  = (unsigned) -1,
 149                 .flags      = ATOMIC_TYPE_FLAG_FLOAT | ATOMIC_TYPE_FLAG_ARITHMETIC
 150                               | ATOMIC_TYPE_FLAG_SIGNED,
 151         },
 152         /* complex and imaginary types are set in init_types */
 153 };
 154
 155 void init_types(void)
 156 {
 157         obstack_init(type_obst);
 158
 159         atomic_type_properties_t *props = atomic_type_properties;
 160
 161         if (char_is_signed) {
 162                 props[ATOMIC_TYPE_CHAR].flags |= ATOMIC_TYPE_FLAG_SIGNED;
 163         }
 164
 165         unsigned int_size   = machine_size < 32 ? 2 : 4;
 166         unsigned long_size  = machine_size < 64 ? 4 : 8;
 167         unsigned llong_size = machine_size < 32 ? 4 : 8;
 168
 169         props[ATOMIC_TYPE_INT].size            = int_size;
 170         props[ATOMIC_TYPE_INT].alignment       = int_size;
 171         props[ATOMIC_TYPE_UINT].size           = int_size;
 172         props[ATOMIC_TYPE_UINT].alignment      = int_size;
 173         props[ATOMIC_TYPE_LONG].size           = long_size;
 174         props[ATOMIC_TYPE_LONG].alignment      = long_size;
 175         props[ATOMIC_TYPE_ULONG].size          = long_size;
 176         props[ATOMIC_TYPE_ULONG].alignment     = long_size;
 177         props[ATOMIC_TYPE_LONGLONG].size       = llong_size;
 178         props[ATOMIC_TYPE_LONGLONG].alignment  = llong_size;
 179         props[ATOMIC_TYPE_ULONGLONG].size      = llong_size;
 180         props[ATOMIC_TYPE_ULONGLONG].alignment = llong_size;
 181
 182         /* TODO: backend specific, need a way to query the backend for this.
 183          * The following are good settings for x86 */
 184         props[ATOMIC_TYPE_FLOAT].alignment       = 4;
 185         props[ATOMIC_TYPE_DOUBLE].alignment      = 4;
 186         props[ATOMIC_TYPE_LONG_DOUBLE].alignment = 4;
 187         props[ATOMIC_TYPE_LONGLONG].alignment    = 4;
 188         props[ATOMIC_TYPE_ULONGLONG].alignment   = 4;
 189
 190         /* TODO: make this configurable for platforms which do not use byte sized
 191          * bools. */
 192         props[ATOMIC_TYPE_BOOL] = props[ATOMIC_TYPE_UCHAR];
 193
 194         props[ATOMIC_TYPE_WCHAR_T] = props[wchar_atomic_kind];
 195 }
 196
 197 void exit_types(void)
 198 {
 199         obstack_free(type_obst, NULL);
 200 }
 201
 202 void type_set_output(FILE *stream)
 203 {
 204         out = stream;
 205 }
 206
 207 void inc_type_visited(void)
 208 {
 209         type_visited++;
 210 }
 211
 212 void print_type_qualifiers(type_qualifiers_t qualifiers)
 213 {
 214         int first = 1;
 215         if (qualifiers & TYPE_QUALIFIER_CONST) {
 216                 fputs(" const" + first,    out);
 217                 first = 0;
 218         }
 219         if (qualifiers & TYPE_QUALIFIER_VOLATILE) {
 220                 fputs(" volatile" + first, out);
 221                 first = 0;
 222         }
 223         if (qualifiers & TYPE_QUALIFIER_RESTRICT) {
 224                 fputs(" restrict" + first, out);
 225                 first = 0;
 226         }
 227 }
 228
 229 const char *get_atomic_kind_name(atomic_type_kind_t kind)
 230 {
 231         switch(kind) {
 232         case ATOMIC_TYPE_INVALID: break;
 233         case ATOMIC_TYPE_VOID:        return "void";
 234         case ATOMIC_TYPE_WCHAR_T:     return "wchar_t";
 235         case ATOMIC_TYPE_BOOL:        return c_mode & _CXX ? "bool" : "_Bool";
 236         case ATOMIC_TYPE_CHAR:        return "char";
 237         case ATOMIC_TYPE_SCHAR:       return "signed char";
 238         case ATOMIC_TYPE_UCHAR:       return "unsigned char";
 239         case ATOMIC_TYPE_INT:         return "int";
 240         case ATOMIC_TYPE_UINT:        return "unsigned int";
 241         case ATOMIC_TYPE_SHORT:       return "short";
 242         case ATOMIC_TYPE_USHORT:      return "unsigned short";
 243         case ATOMIC_TYPE_LONG:        return "long";
 244         case ATOMIC_TYPE_ULONG:       return "unsigned long";
 245         case ATOMIC_TYPE_LONGLONG:    return "long long";
 246         case ATOMIC_TYPE_ULONGLONG:   return "unsigned long long";
 247         case ATOMIC_TYPE_LONG_DOUBLE: return "long double";
 248         case ATOMIC_TYPE_FLOAT:       return "float";
 249         case ATOMIC_TYPE_DOUBLE:      return "double";
 250         }
 251         return "INVALIDATOMIC";
 252 }
 253
 254 /**
 255  * Prints the name of an atomic type kinds.
 256  *
 257  * @param kind  The type kind.
 258  */
 259 static void print_atomic_kinds(atomic_type_kind_t kind)
 260 {
 261         const char *s = get_atomic_kind_name(kind);
 262         fputs(s, out);
 263 }
 264
 265 /**
 266  * Prints the name of an atomic type.
 267  *
 268  * @param type  The type.
 269  */
 270 static void print_atomic_type(const atomic_type_t *type)
 271 {
 272         print_type_qualifiers(type->base.qualifiers);
 273         if (type->base.qualifiers != 0)
 274                 fputc(' ', out);
 275         print_atomic_kinds(type->akind);
 276 }
 277
 278 /**
 279  * Prints the name of a complex type.
 280  *
 281  * @param type  The type.
 282  */
 283 static
 284 void print_complex_type(const complex_type_t *type)
 285 {
 286         int empty = type->base.qualifiers == 0;
 287         print_type_qualifiers(type->base.qualifiers);
 288         fputs(" _Complex " + empty, out);
 289         print_atomic_kinds(type->akind);
 290 }
 291
 292 /**
 293  * Prints the name of an imaginary type.
 294  *
 295  * @param type  The type.
 296  */
 297 static
 298 void print_imaginary_type(const imaginary_type_t *type)
 299 {
 300         int empty = type->base.qualifiers == 0;
 301         print_type_qualifiers(type->base.qualifiers);
 302         fputs(" _Imaginary " + empty, out);
 303         print_atomic_kinds(type->akind);
 304 }
 305
 306 /**
 307  * Print the first part (the prefix) of a type.
 308  *
 309  * @param type   The type to print.
 310  */
 311 static void print_function_type_pre(const function_type_t *type)
 312 {
 313         switch (type->linkage) {
 314                 case LINKAGE_INVALID:
 315                         break;
 316
 317                 case LINKAGE_C:
 318                         if (c_mode & _CXX)
 319                                 fputs("extern \"C\" ",   out);
 320                         break;
 321
 322                 case LINKAGE_CXX:
 323                         if (!(c_mode & _CXX))
 324                                 fputs("extern \"C++\" ", out);
 325                         break;
 326         }
 327
 328         print_type_qualifiers(type->base.qualifiers);
 329         if (type->base.qualifiers != 0)
 330                 fputc(' ', out);
 331
 332         intern_print_type_pre(type->return_type);
 333
 334         switch (type->calling_convention) {
 335         case CC_CDECL:    fputs("__cdecl ",    out); break;
 336         case CC_STDCALL:  fputs("__stdcall ",  out); break;
 337         case CC_FASTCALL: fputs("__fastcall ", out); break;
 338         case CC_THISCALL: fputs("__thiscall ", out); break;
 339         case CC_DEFAULT:  break;
 340         }
 341 }
 342
 343 /**
 344  * Print the second part (the postfix) of a type.
 345  *
 346  * @param type   The type to print.
 347  */
 348 static void print_function_type_post(const function_type_t *type,
 349                                      const scope_t *parameters)
 350 {
 351         fputc('(', out);
 352         bool first = true;
 353         if (parameters == NULL) {
 354                 function_parameter_t *parameter = type->parameters;
 355                 for( ; parameter != NULL; parameter = parameter->next) {
 356                         if (first) {
 357                                 first = false;
 358                         } else {
 359                                 fputs(", ", out);
 360                         }
 361                         print_type(parameter->type);
 362                 }
 363         } else {
 364                 entity_t *parameter = parameters->entities;
 365                 for (; parameter != NULL; parameter = parameter->base.next) {
 366                         if (parameter->kind != ENTITY_PARAMETER)
 367                                 continue;
 368
 369                         if (first) {
 370                                 first = false;
 371                         } else {
 372                                 fputs(", ", out);
 373                         }
 374                         const type_t *const type = parameter->declaration.type;
 375                         if (type == NULL) {
 376                                 fputs(parameter->base.symbol->string, out);
 377                         } else {
 378                                 print_type_ext(type, parameter->base.symbol, NULL);
 379                         }
 380                 }
 381         }
 382         if (type->variadic) {
 383                 if (first) {
 384                         first = false;
 385                 } else {
 386                         fputs(", ", out);
 387                 }
 388                 fputs("...", out);
 389         }
 390         if (first && !type->unspecified_parameters) {
 391                 fputs("void", out);
 392         }
 393         fputc(')', out);
 394
 395         intern_print_type_post(type->return_type);
 396 }
 397
 398 /**
 399  * Prints the prefix part of a pointer type.
 400  *
 401  * @param type   The pointer type.
 402  */
 403 static void print_pointer_type_pre(const pointer_type_t *type)
 404 {
 405         type_t const *const points_to = type->points_to;
 406         intern_print_type_pre(points_to);
 407         if (points_to->kind == TYPE_ARRAY || points_to->kind == TYPE_FUNCTION)
 408                 fputs(" (", out);
 409         variable_t *const variable = type->base_variable;
 410         if (variable != NULL) {
 411                 fputs(" __based(", out);
 412                 fputs(variable->base.base.symbol->string, out);
 413                 fputs(") ", out);
 414         }
 415         fputc('*', out);
 416         type_qualifiers_t const qual = type->base.qualifiers;
 417         if (qual != 0)
 418                 fputc(' ', out);
 419         print_type_qualifiers(qual);
 420 }
 421
 422 /**
 423  * Prints the postfix part of a pointer type.
 424  *
 425  * @param type   The pointer type.
 426  */
 427 static void print_pointer_type_post(const pointer_type_t *type)
 428 {
 429         type_t const *const points_to = type->points_to;
 430         if (points_to->kind == TYPE_ARRAY || points_to->kind == TYPE_FUNCTION)
 431                 fputc(')', out);
 432         intern_print_type_post(points_to);
 433 }
 434
 435 /**
 436  * Prints the prefix part of a reference type.
 437  *
 438  * @param type   The reference type.
 439  */
 440 static void print_reference_type_pre(const reference_type_t *type)
 441 {
 442         type_t const *const refers_to = type->refers_to;
 443         intern_print_type_pre(refers_to);
 444         if (refers_to->kind == TYPE_ARRAY || refers_to->kind == TYPE_FUNCTION)
 445                 fputs(" (", out);
 446         fputc('&', out);
 447 }
 448
 449 /**
 450  * Prints the postfix part of a reference type.
 451  *
 452  * @param type   The reference type.
 453  */
 454 static void print_reference_type_post(const reference_type_t *type)
 455 {
 456         type_t const *const refers_to = type->refers_to;
 457         if (refers_to->kind == TYPE_ARRAY || refers_to->kind == TYPE_FUNCTION)
 458                 fputc(')', out);
 459         intern_print_type_post(refers_to);
 460 }
 461
 462 /**
 463  * Prints the prefix part of an array type.
 464  *
 465  * @param type   The array type.
 466  */
 467 static void print_array_type_pre(const array_type_t *type)
 468 {
 469         intern_print_type_pre(type->element_type);
 470 }
 471
 472 /**
 473  * Prints the postfix part of an array type.
 474  *
 475  * @param type   The array type.
 476  */
 477 static void print_array_type_post(const array_type_t *type)
 478 {
 479         fputc('[', out);
 480         if (type->is_static) {
 481                 fputs("static ", out);
 482         }
 483         print_type_qualifiers(type->base.qualifiers);
 484         if (type->base.qualifiers != 0)
 485                 fputc(' ', out);
 486         if (type->size_expression != NULL
 487                         && (print_implicit_array_size || !type->has_implicit_size)) {
 488                 print_expression(type->size_expression);
 489         }
 490         fputc(']', out);
 491         intern_print_type_post(type->element_type);
 492 }
 493
 494 /**
 495  * Prints the postfix part of a bitfield type.
 496  *
 497  * @param type   The array type.
 498  */
 499 static void print_bitfield_type_post(const bitfield_type_t *type)
 500 {
 501         fputs(" : ", out);
 502         print_expression(type->size_expression);
 503         intern_print_type_post(type->base_type);
 504 }
 505
 506 /**
 507  * Prints an enum definition.
 508  *
 509  * @param declaration  The enum's type declaration.
 510  */
 511 void print_enum_definition(const enum_t *enume)
 512 {
 513         fputs("{\n", out);
 514
 515         change_indent(1);
 516
 517         entity_t *entry = enume->base.next;
 518         for( ; entry != NULL && entry->kind == ENTITY_ENUM_VALUE;
 519                entry = entry->base.next) {
 520
 521                 print_indent();
 522                 fputs(entry->base.symbol->string, out);
 523                 if (entry->enum_value.value != NULL) {
 524                         fputs(" = ", out);
 525
 526                         /* skip the implicit cast */
 527                         expression_t *expression = entry->enum_value.value;
 528                         if (expression->kind == EXPR_UNARY_CAST_IMPLICIT) {
 529                                 expression = expression->unary.value;
 530                         }
 531                         print_expression(expression);
 532                 }
 533                 fputs(",\n", out);
 534         }
 535
 536         change_indent(-1);
 537         print_indent();
 538         fputc('}', out);
 539 }
 540
 541 /**
 542  * Prints an enum type.
 543  *
 544  * @param type  The enum type.
 545  */
 546 static void print_type_enum(const enum_type_t *type)
 547 {
 548         int empty = type->base.qualifiers == 0;
 549         print_type_qualifiers(type->base.qualifiers);
 550         fputs(" enum " + empty, out);
 551
 552         enum_t   *enume  = type->enume;
 553         symbol_t *symbol = enume->base.symbol;
 554         if (symbol != NULL) {
 555                 fputs(symbol->string, out);
 556         } else {
 557                 print_enum_definition(enume);
 558         }
 559 }
 560
 561 /**
 562  * Print the compound part of a compound type.
 563  */
 564 void print_compound_definition(const compound_t *compound)
 565 {
 566         fputs("{\n", out);
 567         change_indent(1);
 568
 569         entity_t *entity = compound->members.entities;
 570         for( ; entity != NULL; entity = entity->base.next) {
 571                 if (entity->kind != ENTITY_COMPOUND_MEMBER)
 572                         continue;
 573
 574                 print_indent();
 575                 print_entity(entity);
 576                 fputc('\n', out);
 577         }
 578
 579         change_indent(-1);
 580         print_indent();
 581         fputc('}', out);
 582         if (compound->modifiers & DM_TRANSPARENT_UNION) {
 583                 fputs("__attribute__((__transparent_union__))", out);
 584         }
 585 }
 586
 587 /**
 588  * Prints a compound type.
 589  *
 590  * @param type  The compound type.
 591  */
 592 static void print_compound_type(const compound_type_t *type)
 593 {
 594         int empty = type->base.qualifiers == 0;
 595         print_type_qualifiers(type->base.qualifiers);
 596
 597         if (type->base.kind == TYPE_COMPOUND_STRUCT) {
 598                 fputs(" struct " + empty, out);
 599         } else {
 600                 assert(type->base.kind == TYPE_COMPOUND_UNION);
 601                 fputs(" union " + empty, out);
 602         }
 603
 604         compound_t *compound = type->compound;
 605         symbol_t   *symbol   = compound->base.symbol;
 606         if (symbol != NULL) {
 607                 fputs(symbol->string, out);
 608         } else {
 609                 print_compound_definition(compound);
 610         }
 611 }
 612
 613 /**
 614  * Prints the prefix part of a typedef type.
 615  *
 616  * @param type   The typedef type.
 617  */
 618 static void print_typedef_type_pre(const typedef_type_t *const type)
 619 {
 620         print_type_qualifiers(type->base.qualifiers);
 621         if (type->base.qualifiers != 0)
 622                 fputc(' ', out);
 623         fputs(type->typedefe->base.symbol->string, out);
 624 }
 625
 626 /**
 627  * Prints the prefix part of a typeof type.
 628  *
 629  * @param type   The typeof type.
 630  */
 631 static void print_typeof_type_pre(const typeof_type_t *const type)
 632 {
 633         fputs("typeof(", out);
 634         if (type->expression != NULL) {
 635                 print_expression(type->expression);
 636         } else {
 637                 print_type(type->typeof_type);
 638         }
 639         fputc(')', out);
 640 }
 641
 642 /**
 643  * Prints the prefix part of a type.
 644  *
 645  * @param type   The type.
 646  */
 647 static void intern_print_type_pre(const type_t *const type)
 648 {
 649         switch(type->kind) {
 650         case TYPE_ERROR:
 651                 fputs("<error>", out);
 652                 return;
 653         case TYPE_INVALID:
 654                 fputs("<invalid>", out);
 655                 return;
 656         case TYPE_ENUM:
 657                 print_type_enum(&type->enumt);
 658                 return;
 659         case TYPE_ATOMIC:
 660                 print_atomic_type(&type->atomic);
 661                 return;
 662         case TYPE_COMPLEX:
 663                 print_complex_type(&type->complex);
 664                 return;
 665         case TYPE_IMAGINARY:
 666                 print_imaginary_type(&type->imaginary);
 667                 return;
 668         case TYPE_COMPOUND_STRUCT:
 669         case TYPE_COMPOUND_UNION:
 670                 print_compound_type(&type->compound);
 671                 return;
 672         case TYPE_BUILTIN:
 673                 fputs(type->builtin.symbol->string, out);
 674                 return;
 675         case TYPE_FUNCTION:
 676                 print_function_type_pre(&type->function);
 677                 return;
 678         case TYPE_POINTER:
 679                 print_pointer_type_pre(&type->pointer);
 680                 return;
 681         case TYPE_REFERENCE:
 682                 print_reference_type_pre(&type->reference);
 683                 return;
 684         case TYPE_BITFIELD:
 685                 intern_print_type_pre(type->bitfield.base_type);
 686                 return;
 687         case TYPE_ARRAY:
 688                 print_array_type_pre(&type->array);
 689                 return;
 690         case TYPE_TYPEDEF:
 691                 print_typedef_type_pre(&type->typedeft);
 692                 return;
 693         case TYPE_TYPEOF:
 694                 print_typeof_type_pre(&type->typeoft);
 695                 return;
 696         }
 697         fputs("unknown", out);
 698 }
 699
 700 /**
 701  * Prints the postfix part of a type.
 702  *
 703  * @param type   The type.
 704  */
 705 static void intern_print_type_post(const type_t *const type)
 706 {
 707         switch(type->kind) {
 708         case TYPE_FUNCTION:
 709                 print_function_type_post(&type->function, NULL);
 710                 return;
 711         case TYPE_POINTER:
 712                 print_pointer_type_post(&type->pointer);
 713                 return;
 714         case TYPE_REFERENCE:
 715                 print_reference_type_post(&type->reference);
 716                 return;
 717         case TYPE_ARRAY:
 718                 print_array_type_post(&type->array);
 719                 return;
 720         case TYPE_BITFIELD:
 721                 print_bitfield_type_post(&type->bitfield);
 722                 return;
 723         case TYPE_ERROR:
 724         case TYPE_INVALID:
 725         case TYPE_ATOMIC:
 726         case TYPE_COMPLEX:
 727         case TYPE_IMAGINARY:
 728         case TYPE_ENUM:
 729         case TYPE_COMPOUND_STRUCT:
 730         case TYPE_COMPOUND_UNION:
 731         case TYPE_BUILTIN:
 732         case TYPE_TYPEOF:
 733         case TYPE_TYPEDEF:
 734                 break;
 735         }
 736 }
 737
 738 /**
 739  * Prints a type.
 740  *
 741  * @param type   The type.
 742  */
 743 void print_type(const type_t *const type)
 744 {
 745         print_type_ext(type, NULL, NULL);
 746 }
 747
 748 void print_type_ext(const type_t *const type, const symbol_t *symbol,
 749                     const scope_t *parameters)
 750 {
 751         if (type == NULL) {
 752                 fputs("nil type", out);
 753                 return;
 754         }
 755
 756         intern_print_type_pre(type);
 757         if (symbol != NULL) {
 758                 fputc(' ', out);
 759                 fputs(symbol->string, out);
 760         }
 761         if (type->kind == TYPE_FUNCTION) {
 762                 print_function_type_post(&type->function, parameters);
 763         } else {
 764                 intern_print_type_post(type);
 765         }
 766 }
 767
 768 /**
 769  * Return the size of a type AST node.
 770  *
 771  * @param type  The type.
 772  */
 773 static size_t get_type_struct_size(const type_t *type)
 774 {
 775         switch(type->kind) {
 776         case TYPE_ATOMIC:          return sizeof(atomic_type_t);
 777         case TYPE_COMPLEX:         return sizeof(complex_type_t);
 778         case TYPE_IMAGINARY:       return sizeof(imaginary_type_t);
 779         case TYPE_COMPOUND_STRUCT:
 780         case TYPE_COMPOUND_UNION:  return sizeof(compound_type_t);
 781         case TYPE_ENUM:            return sizeof(enum_type_t);
 782         case TYPE_FUNCTION:        return sizeof(function_type_t);
 783         case TYPE_POINTER:         return sizeof(pointer_type_t);
 784         case TYPE_REFERENCE:       return sizeof(reference_type_t);
 785         case TYPE_ARRAY:           return sizeof(array_type_t);
 786         case TYPE_BUILTIN:         return sizeof(builtin_type_t);
 787         case TYPE_TYPEDEF:         return sizeof(typedef_type_t);
 788         case TYPE_TYPEOF:          return sizeof(typeof_type_t);
 789         case TYPE_BITFIELD:        return sizeof(bitfield_type_t);
 790         case TYPE_ERROR:           panic("error type found");
 791         case TYPE_INVALID:         panic("invalid type found");
 792         }
 793         panic("unknown type found");
 794 }
 795
 796 /**
 797  * Duplicates a type.
 798  *
 799  * @param type  The type to copy.
 800  * @return A copy of the type.
 801  *
 802  * @note This does not produce a deep copy!
 803  */
 804 type_t *duplicate_type(const type_t *type)
 805 {
 806         size_t size = get_type_struct_size(type);
 807
 808         type_t *copy = obstack_alloc(type_obst, size);
 809         memcpy(copy, type, size);
 810         copy->base.firm_type = NULL;
 811
 812         return copy;
 813 }
 814
 815 /**
 816  * Returns the unqualified type of a given type.
 817  *
 818  * @param type  The type.
 819  * @returns The unqualified type.
 820  */
 821 type_t *get_unqualified_type(type_t *type)
 822 {
 823         assert(!is_typeref(type));
 824
 825         if (type->base.qualifiers == TYPE_QUALIFIER_NONE)
 826                 return type;
 827
 828         type_t *unqualified_type          = duplicate_type(type);
 829         unqualified_type->base.qualifiers = TYPE_QUALIFIER_NONE;
 830
 831         return identify_new_type(unqualified_type);
 832 }
 833
 834 type_t *get_qualified_type(type_t *orig_type, type_qualifiers_t const qual)
 835 {
 836         type_t *type = skip_typeref(orig_type);
 837
 838         type_t *copy;
 839         if (is_type_array(type)) {
 840                 /* For array types the element type has to be adjusted */
 841                 type_t *element_type      = type->array.element_type;
 842                 type_t *qual_element_type = get_qualified_type(element_type, qual);
 843
 844                 if (qual_element_type == element_type)
 845                         return orig_type;
 846
 847                 copy                     = duplicate_type(type);
 848                 copy->array.element_type = qual_element_type;
 849         } else if (is_type_valid(type)) {
 850                 if ((type->base.qualifiers & qual) == qual)
 851                         return orig_type;
 852
 853                 copy                   = duplicate_type(type);
 854                 copy->base.qualifiers |= qual;
 855         } else {
 856                 return type;
 857         }
 858
 859         return identify_new_type(copy);
 860 }
 861
 862 /**
 863  * Check if a type is valid.
 864  *
 865  * @param type  The type to check.
 866  * @return true if type represents a valid type.
 867  */
 868 bool type_valid(const type_t *type)
 869 {
 870         return type->kind != TYPE_INVALID;
 871 }
 872
 873 static bool test_atomic_type_flag(atomic_type_kind_t kind,
 874                                   atomic_type_flag_t flag)
 875 {
 876         assert(kind <= ATOMIC_TYPE_LAST);
 877         return (atomic_type_properties[kind].flags & flag) != 0;
 878 }
 879
 880 /**
 881  * Returns true if the given type is an integer type.
 882  *
 883  * @param type  The type to check.
 884  * @return True if type is an integer type.
 885  */
 886 bool is_type_integer(const type_t *type)
 887 {
 888         assert(!is_typeref(type));
 889
 890         if (type->kind == TYPE_ENUM)
 891                 return true;
 892         if (type->kind == TYPE_BITFIELD)
 893                 return true;
 894
 895         if (type->kind != TYPE_ATOMIC)
 896                 return false;
 897
 898         return test_atomic_type_flag(type->atomic.akind, ATOMIC_TYPE_FLAG_INTEGER);
 899 }
 900
 901 /**
 902  * Returns true if the given type is an enum type.
 903  *
 904  * @param type  The type to check.
 905  * @return True if type is an enum type.
 906  */
 907 bool is_type_enum(const type_t *type)
 908 {
 909         assert(!is_typeref(type));
 910         return type->kind == TYPE_ENUM;
 911 }
 912
 913 /**
 914  * Returns true if the given type is an floating point type.
 915  *
 916  * @param type  The type to check.
 917  * @return True if type is a floating point type.
 918  */
 919 bool is_type_float(const type_t *type)
 920 {
 921         assert(!is_typeref(type));
 922
 923         if (type->kind != TYPE_ATOMIC)
 924                 return false;
 925
 926         return test_atomic_type_flag(type->atomic.akind, ATOMIC_TYPE_FLAG_FLOAT);
 927 }
 928
 929 /**
 930  * Returns true if the given type is an complex type.
 931  *
 932  * @param type  The type to check.
 933  * @return True if type is a complex type.
 934  */
 935 bool is_type_complex(const type_t *type)
 936 {
 937         assert(!is_typeref(type));
 938
 939         if (type->kind != TYPE_ATOMIC)
 940                 return false;
 941
 942         return test_atomic_type_flag(type->atomic.akind, ATOMIC_TYPE_FLAG_COMPLEX);
 943 }
 944
 945 /**
 946  * Returns true if the given type is a signed type.
 947  *
 948  * @param type  The type to check.
 949  * @return True if type is a signed type.
 950  */
 951 bool is_type_signed(const type_t *type)
 952 {
 953         assert(!is_typeref(type));
 954
 955         /* enum types are int for now */
 956         if (type->kind == TYPE_ENUM)
 957                 return true;
 958         if (type->kind == TYPE_BITFIELD)
 959                 return is_type_signed(type->bitfield.base_type);
 960
 961         if (type->kind != TYPE_ATOMIC)
 962                 return false;
 963
 964         return test_atomic_type_flag(type->atomic.akind, ATOMIC_TYPE_FLAG_SIGNED);
 965 }
 966
 967 /**
 968  * Returns true if the given type represents an arithmetic type.
 969  *
 970  * @param type  The type to check.
 971  * @return True if type represents an arithmetic type.
 972  */
 973 bool is_type_arithmetic(const type_t *type)
 974 {
 975         assert(!is_typeref(type));
 976
 977         switch(type->kind) {
 978         case TYPE_BITFIELD:
 979         case TYPE_ENUM:
 980                 return true;
 981         case TYPE_ATOMIC:
 982                 return test_atomic_type_flag(type->atomic.akind, ATOMIC_TYPE_FLAG_ARITHMETIC);
 983         case TYPE_COMPLEX:
 984                 return test_atomic_type_flag(type->complex.akind, ATOMIC_TYPE_FLAG_ARITHMETIC);
 985         case TYPE_IMAGINARY:
 986                 return test_atomic_type_flag(type->imaginary.akind, ATOMIC_TYPE_FLAG_ARITHMETIC);
 987         default:
 988                 return false;
 989         }
 990 }
 991
 992 /**
 993  * Returns true if the given type is an integer or float type.
 994  *
 995  * @param type  The type to check.
 996  * @return True if type is an integer or float type.
 997  */
 998 bool is_type_real(const type_t *type)
 999 {
1000         /* 6.2.5 (17) */
1001         return is_type_integer(type) || is_type_float(type);
1002 }
1003
1004 /**
1005  * Returns true if the given type represents a scalar type.
1006  *
1007  * @param type  The type to check.
1008  * @return True if type represents a scalar type.
1009  */
1010 bool is_type_scalar(const type_t *type)
1011 {
1012         assert(!is_typeref(type));
1013
1014         switch (type->kind) {
1015                 case TYPE_POINTER: return true;
1016                 case TYPE_BUILTIN: return is_type_scalar(type->builtin.real_type);
1017                 default:           break;
1018         }
1019
1020         return is_type_arithmetic(type);
1021 }
1022
1023 /**
1024  * Check if a given type is incomplete.
1025  *
1026  * @param type  The type to check.
1027  * @return True if the given type is incomplete (ie. just forward).
1028  */
1029 bool is_type_incomplete(const type_t *type)
1030 {
1031         assert(!is_typeref(type));
1032
1033         switch(type->kind) {
1034         case TYPE_COMPOUND_STRUCT:
1035         case TYPE_COMPOUND_UNION: {
1036                 const compound_type_t *compound_type = &type->compound;
1037                 return !compound_type->compound->complete;
1038         }
1039         case TYPE_ENUM:
1040                 return false;
1041
1042         case TYPE_ARRAY:
1043                 return type->array.size_expression == NULL
1044                         && !type->array.size_constant;
1045
1046         case TYPE_ATOMIC:
1047                 return type->atomic.akind == ATOMIC_TYPE_VOID;
1048
1049         case TYPE_COMPLEX:
1050                 return type->complex.akind == ATOMIC_TYPE_VOID;
1051
1052         case TYPE_IMAGINARY:
1053                 return type->imaginary.akind == ATOMIC_TYPE_VOID;
1054
1055         case TYPE_BITFIELD:
1056         case TYPE_FUNCTION:
1057         case TYPE_POINTER:
1058         case TYPE_REFERENCE:
1059         case TYPE_BUILTIN:
1060         case TYPE_ERROR:
1061                 return false;
1062
1063         case TYPE_TYPEDEF:
1064         case TYPE_TYPEOF:
1065                 panic("is_type_incomplete called without typerefs skipped");
1066         case TYPE_INVALID:
1067                 break;
1068         }
1069
1070         panic("invalid type found");
1071 }
1072
1073 bool is_type_object(const type_t *type)
1074 {
1075         return !is_type_function(type) && !is_type_incomplete(type);
1076 }
1077
1078 bool is_builtin_va_list(type_t *type)
1079 {
1080         type_t *tp = skip_typeref(type);
1081
1082         return tp->kind == type_valist->kind &&
1083                tp->builtin.symbol == type_valist->builtin.symbol;
1084 }
1085
1086 /**
1087  * Check if two function types are compatible.
1088  */
1089 static bool function_types_compatible(const function_type_t *func1,
1090                                       const function_type_t *func2)
1091 {
1092         const type_t* const ret1 = skip_typeref(func1->return_type);
1093         const type_t* const ret2 = skip_typeref(func2->return_type);
1094         if (!types_compatible(ret1, ret2))
1095                 return false;
1096
1097         if (func1->linkage != func2->linkage)
1098                 return false;
1099
1100         if (func1->calling_convention != func2->calling_convention)
1101                 return false;
1102
1103         /* can parameters be compared? */
1104         if (func1->unspecified_parameters || func2->unspecified_parameters)
1105                 return true;
1106
1107         if (func1->variadic != func2->variadic)
1108                 return false;
1109
1110         /* TODO: handling of unspecified parameters not correct yet */
1111
1112         /* all argument types must be compatible */
1113         function_parameter_t *parameter1 = func1->parameters;
1114         function_parameter_t *parameter2 = func2->parameters;
1115         for ( ; parameter1 != NULL && parameter2 != NULL;
1116                         parameter1 = parameter1->next, parameter2 = parameter2->next) {
1117                 type_t *parameter1_type = skip_typeref(parameter1->type);
1118                 type_t *parameter2_type = skip_typeref(parameter2->type);
1119
1120                 parameter1_type = get_unqualified_type(parameter1_type);
1121                 parameter2_type = get_unqualified_type(parameter2_type);
1122
1123                 if (!types_compatible(parameter1_type, parameter2_type))
1124                         return false;
1125         }
1126         /* same number of arguments? */
1127         if (parameter1 != NULL || parameter2 != NULL)
1128                 return false;
1129
1130         return true;
1131 }
1132
1133 /**
1134  * Check if two array types are compatible.
1135  */
1136 static bool array_types_compatible(const array_type_t *array1,
1137                                    const array_type_t *array2)
1138 {
1139         type_t *element_type1 = skip_typeref(array1->element_type);
1140         type_t *element_type2 = skip_typeref(array2->element_type);
1141         if (!types_compatible(element_type1, element_type2))
1142                 return false;
1143
1144         if (!array1->size_constant || !array2->size_constant)
1145                 return true;
1146
1147         return array1->size == array2->size;
1148 }
1149
1150 /**
1151  * Check if two types are compatible.
1152  */
1153 bool types_compatible(const type_t *type1, const type_t *type2)
1154 {
1155         assert(!is_typeref(type1));
1156         assert(!is_typeref(type2));
1157
1158         /* shortcut: the same type is always compatible */
1159         if (type1 == type2)
1160                 return true;
1161
1162         if (!is_type_valid(type1) || !is_type_valid(type2))
1163                 return true;
1164
1165         if (type1->base.qualifiers != type2->base.qualifiers)
1166                 return false;
1167         if (type1->kind != type2->kind)
1168                 return false;
1169
1170         switch (type1->kind) {
1171         case TYPE_FUNCTION:
1172                 return function_types_compatible(&type1->function, &type2->function);
1173         case TYPE_ATOMIC:
1174                 return type1->atomic.akind == type2->atomic.akind;
1175         case TYPE_COMPLEX:
1176                 return type1->complex.akind == type2->complex.akind;
1177         case TYPE_IMAGINARY:
1178                 return type1->imaginary.akind == type2->imaginary.akind;
1179         case TYPE_ARRAY:
1180                 return array_types_compatible(&type1->array, &type2->array);
1181
1182         case TYPE_POINTER: {
1183                 const type_t *const to1 = skip_typeref(type1->pointer.points_to);
1184                 const type_t *const to2 = skip_typeref(type2->pointer.points_to);
1185                 return types_compatible(to1, to2);
1186         }
1187
1188         case TYPE_REFERENCE: {
1189                 const type_t *const to1 = skip_typeref(type1->reference.refers_to);
1190                 const type_t *const to2 = skip_typeref(type2->reference.refers_to);
1191                 return types_compatible(to1, to2);
1192         }
1193
1194         case TYPE_COMPOUND_STRUCT:
1195         case TYPE_COMPOUND_UNION: {
1196
1197
1198                 break;
1199         }
1200         case TYPE_ENUM:
1201         case TYPE_BUILTIN:
1202                 /* TODO: not implemented */
1203                 break;
1204
1205         case TYPE_BITFIELD:
1206                 /* not sure if this makes sense or is even needed, implement it if you
1207                  * really need it! */
1208                 panic("type compatibility check for bitfield type");
1209
1210         case TYPE_ERROR:
1211                 /* Hmm, the error type should be compatible to all other types */
1212                 return true;
1213         case TYPE_INVALID:
1214                 panic("invalid type found in compatible types");
1215         case TYPE_TYPEDEF:
1216         case TYPE_TYPEOF:
1217                 panic("typerefs not skipped in compatible types?!?");
1218         }
1219
1220         /* TODO: incomplete */
1221         return false;
1222 }
1223
1224 /**
1225  * Skip all typerefs and return the underlying type.
1226  */
1227 type_t *skip_typeref(type_t *type)
1228 {
1229         type_qualifiers_t qualifiers = TYPE_QUALIFIER_NONE;
1230
1231         while (true) {
1232                 switch (type->kind) {
1233                 case TYPE_ERROR:
1234                         return type;
1235                 case TYPE_TYPEDEF: {
1236                         qualifiers |= type->base.qualifiers;
1237
1238                         const typedef_type_t *typedef_type = &type->typedeft;
1239                         if (typedef_type->resolved_type != NULL) {
1240                                 type = typedef_type->resolved_type;
1241                                 break;
1242                         }
1243                         type = typedef_type->typedefe->type;
1244                         continue;
1245                 }
1246                 case TYPE_TYPEOF:
1247                         qualifiers |= type->base.qualifiers;
1248                         type        = type->typeoft.typeof_type;
1249                         continue;
1250                 default:
1251                         break;
1252                 }
1253                 break;
1254         }
1255
1256         if (qualifiers != TYPE_QUALIFIER_NONE) {
1257                 type_t *const copy = duplicate_type(type);
1258
1259                 /* for const with typedefed array type the element type has to be
1260                  * adjusted */
1261                 if (is_type_array(copy)) {
1262                         type_t *element_type           = copy->array.element_type;
1263                         element_type                   = duplicate_type(element_type);
1264                         element_type->base.qualifiers |= qualifiers;
1265                         copy->array.element_type       = element_type;
1266                 } else {
1267                         copy->base.qualifiers |= qualifiers;
1268                 }
1269
1270                 type = identify_new_type(copy);
1271         }
1272
1273         return type;
1274 }
1275
1276 unsigned get_type_size(type_t *type)
1277 {
1278         switch (type->kind) {
1279         case TYPE_INVALID:
1280                 break;
1281         case TYPE_ERROR:
1282                 return 0;
1283         case TYPE_ATOMIC:
1284                 return get_atomic_type_size(type->atomic.akind);
1285         case TYPE_COMPLEX:
1286                 return get_atomic_type_size(type->complex.akind) * 2;
1287         case TYPE_IMAGINARY:
1288                 return get_atomic_type_size(type->imaginary.akind);
1289         case TYPE_COMPOUND_UNION:
1290                 layout_union_type(&type->compound);
1291                 return type->compound.compound->size;
1292         case TYPE_COMPOUND_STRUCT:
1293                 layout_struct_type(&type->compound);
1294                 return type->compound.compound->size;
1295         case TYPE_ENUM:
1296                 return get_atomic_type_size(type->enumt.akind);
1297         case TYPE_FUNCTION:
1298                 return 0; /* non-const (but "address-const") */
1299         case TYPE_REFERENCE:
1300         case TYPE_POINTER:
1301                 /* TODO: make configurable by backend */
1302                 return 4;
1303         case TYPE_ARRAY: {
1304                 /* TODO: correct if element_type is aligned? */
1305                 il_size_t element_size = get_type_size(type->array.element_type);
1306                 return type->array.size * element_size;
1307         }
1308         case TYPE_BITFIELD:
1309                 return 0;
1310         case TYPE_BUILTIN:
1311                 return get_type_size(type->builtin.real_type);
1312         case TYPE_TYPEDEF:
1313                 return get_type_size(type->typedeft.typedefe->type);
1314         case TYPE_TYPEOF:
1315                 if (type->typeoft.typeof_type) {
1316                         return get_type_size(type->typeoft.typeof_type);
1317                 } else {
1318                         return get_type_size(type->typeoft.expression->base.type);
1319                 }
1320         }
1321         panic("invalid type in get_type_size");
1322 }
1323
1324 unsigned get_type_alignment(type_t *type)
1325 {
1326         switch (type->kind) {
1327         case TYPE_INVALID:
1328                 break;
1329         case TYPE_ERROR:
1330                 return 0;
1331         case TYPE_ATOMIC:
1332                 return get_atomic_type_alignment(type->atomic.akind);
1333         case TYPE_COMPLEX:
1334                 return get_atomic_type_alignment(type->complex.akind);
1335         case TYPE_IMAGINARY:
1336                 return get_atomic_type_alignment(type->imaginary.akind);
1337         case TYPE_COMPOUND_UNION:
1338                 layout_union_type(&type->compound);
1339                 return type->compound.compound->alignment;
1340         case TYPE_COMPOUND_STRUCT:
1341                 layout_struct_type(&type->compound);
1342                 return type->compound.compound->alignment;
1343         case TYPE_ENUM:
1344                 return get_atomic_type_alignment(type->enumt.akind);
1345         case TYPE_FUNCTION:
1346                 /* what is correct here? */
1347                 return 4;
1348         case TYPE_REFERENCE:
1349         case TYPE_POINTER:
1350                 /* TODO: make configurable by backend */
1351                 return 4;
1352         case TYPE_ARRAY:
1353                 return get_type_alignment(type->array.element_type);
1354         case TYPE_BITFIELD:
1355                 return 0;
1356         case TYPE_BUILTIN:
1357                 return get_type_alignment(type->builtin.real_type);
1358         case TYPE_TYPEDEF: {
1359                 il_alignment_t alignment
1360                         = get_type_alignment(type->typedeft.typedefe->type);
1361                 if (type->typedeft.typedefe->alignment > alignment)
1362                         alignment = type->typedeft.typedefe->alignment;
1363
1364                 return alignment;
1365         }
1366         case TYPE_TYPEOF:
1367                 if (type->typeoft.typeof_type) {
1368                         return get_type_alignment(type->typeoft.typeof_type);
1369                 } else {
1370                         return get_type_alignment(type->typeoft.expression->base.type);
1371                 }
1372         }
1373         panic("invalid type in get_type_alignment");
1374 }
1375
1376 decl_modifiers_t get_type_modifiers(const type_t *type)
1377 {
1378         switch(type->kind) {
1379         case TYPE_INVALID:
1380         case TYPE_ERROR:
1381                 break;
1382         case TYPE_COMPOUND_STRUCT:
1383         case TYPE_COMPOUND_UNION:
1384                 return type->compound.compound->modifiers;
1385         case TYPE_FUNCTION:
1386                 return type->function.modifiers;
1387         case TYPE_ENUM:
1388         case TYPE_ATOMIC:
1389         case TYPE_COMPLEX:
1390         case TYPE_IMAGINARY:
1391         case TYPE_REFERENCE:
1392         case TYPE_POINTER:
1393         case TYPE_BITFIELD:
1394         case TYPE_ARRAY:
1395                 return 0;
1396         case TYPE_BUILTIN:
1397                 return get_type_modifiers(type->builtin.real_type);
1398         case TYPE_TYPEDEF: {
1399                 decl_modifiers_t modifiers = type->typedeft.typedefe->modifiers;
1400                 modifiers |= get_type_modifiers(type->typedeft.typedefe->type);
1401                 return modifiers;
1402         }
1403         case TYPE_TYPEOF:
1404                 if (type->typeoft.typeof_type) {
1405                         return get_type_modifiers(type->typeoft.typeof_type);
1406                 } else {
1407                         return get_type_modifiers(type->typeoft.expression->base.type);
1408                 }
1409         }
1410         panic("invalid type found in get_type_modifiers");
1411 }
1412
1413 type_qualifiers_t get_type_qualifier(const type_t *type, bool skip_array_type)
1414 {
1415         type_qualifiers_t qualifiers = TYPE_QUALIFIER_NONE;
1416
1417         while (true) {
1418                 switch (type->base.kind) {
1419                 case TYPE_ERROR:
1420                         return TYPE_QUALIFIER_NONE;
1421                 case TYPE_TYPEDEF:
1422                         qualifiers |= type->base.qualifiers;
1423                         const typedef_type_t *typedef_type = &type->typedeft;
1424                         if (typedef_type->resolved_type != NULL)
1425                                 type = typedef_type->resolved_type;
1426                         else
1427                                 type = typedef_type->typedefe->type;
1428                         continue;
1429                 case TYPE_TYPEOF:
1430                         type = type->typeoft.typeof_type;
1431                         continue;
1432                 case TYPE_ARRAY:
1433                         if (skip_array_type) {
1434                                 type = type->array.element_type;
1435                                 continue;
1436                         }
1437                         break;
1438                 default:
1439                         break;
1440                 }
1441                 break;
1442         }
1443         return type->base.qualifiers | qualifiers;
1444 }
1445
1446 unsigned get_atomic_type_size(atomic_type_kind_t kind)
1447 {
1448         assert(kind <= ATOMIC_TYPE_LAST);
1449         return atomic_type_properties[kind].size;
1450 }
1451
1452 unsigned get_atomic_type_alignment(atomic_type_kind_t kind)
1453 {
1454         assert(kind <= ATOMIC_TYPE_LAST);
1455         return atomic_type_properties[kind].alignment;
1456 }
1457
1458 unsigned get_atomic_type_flags(atomic_type_kind_t kind)
1459 {
1460         assert(kind <= ATOMIC_TYPE_LAST);
1461         return atomic_type_properties[kind].flags;
1462 }
1463
1464 atomic_type_kind_t get_intptr_kind(void)
1465 {
1466         if (machine_size <= 32)
1467                 return ATOMIC_TYPE_INT;
1468         else if (machine_size <= 64)
1469                 return ATOMIC_TYPE_LONG;
1470         else
1471                 return ATOMIC_TYPE_LONGLONG;
1472 }
1473
1474 atomic_type_kind_t get_uintptr_kind(void)
1475 {
1476         if (machine_size <= 32)
1477                 return ATOMIC_TYPE_UINT;
1478         else if (machine_size <= 64)
1479                 return ATOMIC_TYPE_ULONG;
1480         else
1481                 return ATOMIC_TYPE_ULONGLONG;
1482 }
1483
1484 /**
1485  * Find the atomic type kind representing a given size (signed).
1486  */
1487 atomic_type_kind_t find_signed_int_atomic_type_kind_for_size(unsigned size)
1488 {
1489         static atomic_type_kind_t kinds[32];
1490
1491         assert(size < 32);
1492         atomic_type_kind_t kind = kinds[size];
1493         if (kind == ATOMIC_TYPE_INVALID) {
1494                 static const atomic_type_kind_t possible_kinds[] = {
1495                         ATOMIC_TYPE_SCHAR,
1496                         ATOMIC_TYPE_SHORT,
1497                         ATOMIC_TYPE_INT,
1498                         ATOMIC_TYPE_LONG,
1499                         ATOMIC_TYPE_LONGLONG
1500                 };
1501                 for (size_t i = 0; i < lengthof(possible_kinds); ++i) {
1502                         if (get_atomic_type_size(possible_kinds[i]) == size) {
1503                                 kind = possible_kinds[i];
1504                                 break;
1505                         }
1506                 }
1507                 kinds[size] = kind;
1508         }
1509         return kind;
1510 }
1511
1512 /**
1513  * Find the atomic type kind representing a given size (signed).
1514  */
1515 atomic_type_kind_t find_unsigned_int_atomic_type_kind_for_size(unsigned size)
1516 {
1517         static atomic_type_kind_t kinds[32];
1518
1519         assert(size < 32);
1520         atomic_type_kind_t kind = kinds[size];
1521         if (kind == ATOMIC_TYPE_INVALID) {
1522                 static const atomic_type_kind_t possible_kinds[] = {
1523                         ATOMIC_TYPE_UCHAR,
1524                         ATOMIC_TYPE_USHORT,
1525                         ATOMIC_TYPE_UINT,
1526                         ATOMIC_TYPE_ULONG,
1527                         ATOMIC_TYPE_ULONGLONG
1528                 };
1529                 for (size_t i = 0; i < lengthof(possible_kinds); ++i) {
1530                         if (get_atomic_type_size(possible_kinds[i]) == size) {
1531                                 kind = possible_kinds[i];
1532                                 break;
1533                         }
1534                 }
1535                 kinds[size] = kind;
1536         }
1537         return kind;
1538 }
1539
1540 /**
1541  * Hash the given type and return the "singleton" version
1542  * of it.
1543  */
1544 type_t *identify_new_type(type_t *type)
1545 {
1546         type_t *result = typehash_insert(type);
1547         if (result != type) {
1548                 obstack_free(type_obst, type);
1549         }
1550         return result;
1551 }
1552
1553 /**
1554  * Creates a new atomic type.
1555  *
1556  * @param akind       The kind of the atomic type.
1557  * @param qualifiers  Type qualifiers for the new type.
1558  */
1559 type_t *make_atomic_type(atomic_type_kind_t akind, type_qualifiers_t qualifiers)
1560 {
1561         type_t *type = obstack_alloc(type_obst, sizeof(atomic_type_t));
1562         memset(type, 0, sizeof(atomic_type_t));
1563
1564         type->kind            = TYPE_ATOMIC;
1565         type->base.qualifiers = qualifiers;
1566         type->atomic.akind    = akind;
1567
1568         return identify_new_type(type);
1569 }
1570
1571 /**
1572  * Creates a new complex type.
1573  *
1574  * @param akind       The kind of the atomic type.
1575  * @param qualifiers  Type qualifiers for the new type.
1576  */
1577 type_t *make_complex_type(atomic_type_kind_t akind, type_qualifiers_t qualifiers)
1578 {
1579         type_t *type = obstack_alloc(type_obst, sizeof(complex_type_t));
1580         memset(type, 0, sizeof(complex_type_t));
1581
1582         type->kind            = TYPE_COMPLEX;
1583         type->base.qualifiers = qualifiers;
1584         type->complex.akind   = akind;
1585
1586         return identify_new_type(type);
1587 }
1588
1589 /**
1590  * Creates a new imaginary type.
1591  *
1592  * @param akind       The kind of the atomic type.
1593  * @param qualifiers  Type qualifiers for the new type.
1594  */
1595 type_t *make_imaginary_type(atomic_type_kind_t akind, type_qualifiers_t qualifiers)
1596 {
1597         type_t *type = obstack_alloc(type_obst, sizeof(imaginary_type_t));
1598         memset(type, 0, sizeof(imaginary_type_t));
1599
1600         type->kind            = TYPE_IMAGINARY;
1601         type->base.qualifiers = qualifiers;
1602         type->imaginary.akind = akind;
1603
1604         return identify_new_type(type);
1605 }
1606
1607 /**
1608  * Creates a new pointer type.
1609  *
1610  * @param points_to   The points-to type for the new type.
1611  * @param qualifiers  Type qualifiers for the new type.
1612  */
1613 type_t *make_pointer_type(type_t *points_to, type_qualifiers_t qualifiers)
1614 {
1615         type_t *type = obstack_alloc(type_obst, sizeof(pointer_type_t));
1616         memset(type, 0, sizeof(pointer_type_t));
1617
1618         type->kind                  = TYPE_POINTER;
1619         type->base.qualifiers       = qualifiers;
1620         type->pointer.points_to     = points_to;
1621         type->pointer.base_variable = NULL;
1622
1623         return identify_new_type(type);
1624 }
1625
1626 /**
1627  * Creates a new reference type.
1628  *
1629  * @param refers_to   The referred-to type for the new type.
1630  */
1631 type_t *make_reference_type(type_t *refers_to)
1632 {
1633         type_t *type = obstack_alloc(type_obst, sizeof(reference_type_t));
1634         memset(type, 0, sizeof(reference_type_t));
1635
1636         type->kind                = TYPE_REFERENCE;
1637         type->base.qualifiers     = 0;
1638         type->reference.refers_to = refers_to;
1639
1640         return identify_new_type(type);
1641 }
1642
1643 /**
1644  * Creates a new based pointer type.
1645  *
1646  * @param points_to   The points-to type for the new type.
1647  * @param qualifiers  Type qualifiers for the new type.
1648  * @param variable    The based variable
1649  */
1650 type_t *make_based_pointer_type(type_t *points_to,
1651                                                                 type_qualifiers_t qualifiers, variable_t *variable)
1652 {
1653         type_t *type = obstack_alloc(type_obst, sizeof(pointer_type_t));
1654         memset(type, 0, sizeof(pointer_type_t));
1655
1656         type->kind                  = TYPE_POINTER;
1657         type->base.qualifiers       = qualifiers;
1658         type->pointer.points_to     = points_to;
1659         type->pointer.base_variable = variable;
1660
1661         return identify_new_type(type);
1662 }
1663
1664
1665 type_t *make_array_type(type_t *element_type, size_t size,
1666                         type_qualifiers_t qualifiers)
1667 {
1668         type_t *type = obstack_alloc(type_obst, sizeof(array_type_t));
1669         memset(type, 0, sizeof(array_type_t));
1670
1671         type->kind                = TYPE_ARRAY;
1672         type->base.qualifiers     = qualifiers;
1673         type->array.element_type  = element_type;
1674         type->array.size          = size;
1675         type->array.size_constant = true;
1676
1677         return identify_new_type(type);
1678 }
1679
1680 static entity_t *pack_bitfield_members(il_size_t *size, bool packed,
1681                                        type_t *type, size_t offset,
1682                                                                            entity_t *first)
1683 {
1684         /* TODO: packed handling */
1685         type_t *base_type      = skip_typeref(type->bitfield.base_type);
1686         size_t  remaining_bits = get_type_size(base_type) * BITS_PER_BYTE;
1687         size_t  bit_offset     = 0;
1688
1689         entity_t *member;
1690         for (member = first; member != NULL; member = member->base.next) {
1691                 /* TODO: make this an assert */
1692                 if (member->kind != ENTITY_COMPOUND_MEMBER)
1693                         continue;
1694
1695                 type_t *member_type = member->declaration.type;
1696                 if (member_type->kind != TYPE_BITFIELD)
1697                         break;
1698                 size_t bit_size = member_type->bitfield.bit_size;
1699                 if (!packed) {
1700                         if (base_type != NULL
1701                             && skip_typeref(member_type->bitfield.base_type) != base_type)
1702                                 break;
1703                         if (bit_size > remaining_bits)
1704                                 break;
1705                 }
1706
1707                 member->compound_member.offset     = offset;
1708                 member->compound_member.bit_offset = bit_offset;
1709
1710                 bit_offset += bit_size;
1711
1712                 /* 0-size members end current bucket. multiple 0-size buckets
1713                  * seem to not start-end multiple buckets */
1714                 if (bit_size == 0) {
1715                         remaining_bits = 0;
1716                 } else {
1717                         remaining_bits -= bit_size;
1718                 }
1719         }
1720         assert(member != first);
1721
1722         *size += (bit_offset + (BITS_PER_BYTE-1)) / BITS_PER_BYTE;
1723
1724         return member;
1725 }
1726
1727 /**
1728  * Finish the construction of a struct type by calculating its size, offsets,
1729  * alignment.
1730  */
1731 void layout_struct_type(compound_type_t *type)
1732 {
1733         assert(type->compound != NULL);
1734
1735         compound_t *compound = type->compound;
1736         if (!compound->complete)
1737                 return;
1738         if (type->compound->layouted)
1739                 return;
1740
1741         il_size_t      offset;
1742         il_size_t      size      = 0;
1743         il_alignment_t alignment = compound->alignment;
1744         bool           need_pad  = false;
1745
1746         entity_t *entry = compound->members.entities;
1747         while (entry != NULL) {
1748                 if (entry->kind != ENTITY_COMPOUND_MEMBER) {
1749                         entry = entry->base.next;
1750                         continue;
1751                 }
1752
1753                 type_t *m_type  = entry->declaration.type;
1754                 type_t *skipped = skip_typeref(m_type);
1755                 if (! is_type_valid(skipped)) {
1756                         entry = entry->base.next;
1757                         continue;
1758                 }
1759
1760                 type_t *base_type = m_type;
1761                 if (skipped->kind == TYPE_BITFIELD) {
1762                         base_type = m_type->bitfield.base_type;
1763                 }
1764
1765                 il_alignment_t m_alignment = get_type_alignment(base_type);
1766                 il_size_t      m_size      = get_type_size(base_type);
1767                 if (m_alignment > alignment)
1768                         alignment = m_alignment;
1769
1770                 if (compound->packed) {
1771                         offset = size;
1772                 } else {
1773                         offset = (size + m_alignment - 1) & -m_alignment;
1774                 }
1775
1776                 if (offset > size)
1777                         need_pad = true;
1778
1779                 if (skipped->kind == TYPE_BITFIELD) {
1780                         entry = pack_bitfield_members(&size, compound->packed,
1781                                                       m_type, offset, entry);
1782                 } else {
1783                         entry->compound_member.offset = offset;
1784                         size                          = offset + m_size;
1785
1786                         entry = entry->base.next;
1787                 }
1788         }
1789
1790         if (!compound->packed) {
1791                 offset = (size + alignment - 1) & -alignment;
1792                 if (offset > size)
1793                         need_pad = true;
1794         } else {
1795                 offset = size;
1796         }
1797
1798         if (need_pad) {
1799                 if (warning.padded) {
1800                         warningf(&compound->base.source_position, "'%T' needs padding",
1801                                  type);
1802                 }
1803         } else if (compound->packed && warning.packed) {
1804                 warningf(&compound->base.source_position,
1805                          "superfluous packed attribute on '%T'", type);
1806         }
1807
1808         compound->size      = offset;
1809         compound->alignment = alignment;
1810         compound->layouted  = true;
1811 }
1812
1813 /**
1814  * Finish the construction of an union type by calculating
1815  * its size and alignment.
1816  */
1817 void layout_union_type(compound_type_t *type)
1818 {
1819         assert(type->compound != NULL);
1820
1821         compound_t *compound = type->compound;
1822         if (! compound->complete)
1823                 return;
1824
1825         il_size_t      size      = 0;
1826         il_alignment_t alignment = compound->alignment;
1827
1828         entity_t *entry = compound->members.entities;
1829         for (; entry != NULL; entry = entry->base.next) {
1830                 if (entry->kind != ENTITY_COMPOUND_MEMBER)
1831                         continue;
1832
1833                 type_t *m_type = entry->declaration.type;
1834                 if (! is_type_valid(skip_typeref(m_type)))
1835                         continue;
1836
1837                 entry->compound_member.offset = 0;
1838                 il_size_t m_size = get_type_size(m_type);
1839                 if (m_size > size)
1840                         size = m_size;
1841                 il_alignment_t m_alignment = get_type_alignment(m_type);
1842                 if (m_alignment > alignment)
1843                         alignment = m_alignment;
1844         }
1845         size = (size + alignment - 1) & -alignment;
1846
1847         compound->size      = size;
1848         compound->alignment = alignment;
1849 }
1850
1851 /**
1852  * Debug helper. Prints the given type to stdout.
1853  */
1854 static __attribute__((unused))
1855 void dbg_type(const type_t *type)
1856 {
1857         FILE *old_out = out;
1858         out = stderr;
1859         print_type(type);
1860         puts("\n");
1861         fflush(stderr);
1862         out = old_out;
1863 }