nsz Git - cparser/blob - parser.c

   1 #include <config.h>
   2
   3 #include <assert.h>
   4 #include <stdarg.h>
   5 #include <stdbool.h>
   6
   7 #include "diagnostic.h"
   8 #include "format_check.h"
   9 #include "parser.h"
  10 #include "lexer.h"
  11 #include "token_t.h"
  12 #include "types.h"
  13 #include "type_t.h"
  14 #include "type_hash.h"
  15 #include "ast_t.h"
  16 #include "lang_features.h"
  17 #include "adt/bitfiddle.h"
  18 #include "adt/error.h"
  19 #include "adt/array.h"
  20
  21 //#define PRINT_TOKENS
  22 //#define ABORT_ON_ERROR
  23 #define MAX_LOOKAHEAD 2
  24
  25 typedef struct {
  26         declaration_t *old_declaration;
  27         symbol_t      *symbol;
  28         unsigned short namespc;
  29 } stack_entry_t;
  30
  31 typedef struct declaration_specifiers_t  declaration_specifiers_t;
  32 struct declaration_specifiers_t {
  33         source_position_t  source_position;
  34         unsigned char      storage_class;
  35         bool               is_inline;
  36         decl_modifiers_t   decl_modifiers;
  37         type_t            *type;
  38 };
  39
  40 typedef declaration_t* (*parsed_declaration_func) (declaration_t *declaration);
  41
  42 static token_t             token;
  43 static token_t             lookahead_buffer[MAX_LOOKAHEAD];
  44 static int                 lookahead_bufpos;
  45 static stack_entry_t      *environment_stack = NULL;
  46 static stack_entry_t      *label_stack       = NULL;
  47 static context_t          *global_context    = NULL;
  48 static context_t          *context           = NULL;
  49 static declaration_t      *last_declaration  = NULL;
  50 static declaration_t      *current_function  = NULL;
  51 static switch_statement_t *current_switch    = NULL;
  52 static statement_t        *current_loop      = NULL;
  53 static goto_statement_t   *goto_first        = NULL;
  54 static goto_statement_t   *goto_last         = NULL;
  55 static struct obstack  temp_obst;
  56
  57 /** The current source position. */
  58 #define HERE token.source_position
  59
  60 static type_t *type_valist;
  61
  62 static statement_t *parse_compound_statement(void);
  63 static statement_t *parse_statement(void);
  64
  65 static expression_t *parse_sub_expression(unsigned precedence);
  66 static expression_t *parse_expression(void);
  67 static type_t       *parse_typename(void);
  68
  69 static void parse_compound_type_entries(void);
  70 static declaration_t *parse_declarator(
  71                 const declaration_specifiers_t *specifiers, bool may_be_abstract);
  72 static declaration_t *record_declaration(declaration_t *declaration);
  73
  74 static void semantic_comparison(binary_expression_t *expression);
  75
  76 #define STORAGE_CLASSES     \
  77         case T_typedef:         \
  78         case T_extern:          \
  79         case T_static:          \
  80         case T_auto:            \
  81         case T_register:
  82
  83 #define TYPE_QUALIFIERS     \
  84         case T_const:           \
  85         case T_restrict:        \
  86         case T_volatile:        \
  87         case T_inline:          \
  88         case T_forceinline:
  89
  90 #ifdef PROVIDE_COMPLEX
  91 #define COMPLEX_SPECIFIERS  \
  92         case T__Complex:
  93 #define IMAGINARY_SPECIFIERS \
  94         case T__Imaginary:
  95 #else
  96 #define COMPLEX_SPECIFIERS
  97 #define IMAGINARY_SPECIFIERS
  98 #endif
  99
 100 #define TYPE_SPECIFIERS       \
 101         case T_void:              \
 102         case T_char:              \
 103         case T_short:             \
 104         case T_int:               \
 105         case T_long:              \
 106         case T_float:             \
 107         case T_double:            \
 108         case T_signed:            \
 109         case T_unsigned:          \
 110         case T__Bool:             \
 111         case T_struct:            \
 112         case T_union:             \
 113         case T_enum:              \
 114         case T___typeof__:        \
 115         case T___builtin_va_list: \
 116         COMPLEX_SPECIFIERS        \
 117         IMAGINARY_SPECIFIERS
 118
 119 #define DECLARATION_START   \
 120         STORAGE_CLASSES         \
 121         TYPE_QUALIFIERS         \
 122         TYPE_SPECIFIERS
 123
 124 #define TYPENAME_START      \
 125         TYPE_QUALIFIERS         \
 126         TYPE_SPECIFIERS
 127
 128 /**
 129  * Allocate an AST node with given size and
 130  * initialize all fields with zero.
 131  */
 132 static void *allocate_ast_zero(size_t size)
 133 {
 134         void *res = allocate_ast(size);
 135         memset(res, 0, size);
 136         return res;
 137 }
 138
 139 static declaration_t *allocate_declaration_zero(void)
 140 {
 141         return allocate_ast_zero(sizeof(*allocate_declaration_zero()));
 142 }
 143
 144 /**
 145  * Returns the size of a statement node.
 146  *
 147  * @param kind  the statement kind
 148  */
 149 static size_t get_statement_struct_size(statement_kind_t kind)
 150 {
 151         static const size_t sizes[] = {
 152                 [STATEMENT_COMPOUND]    = sizeof(compound_statement_t),
 153                 [STATEMENT_RETURN]      = sizeof(return_statement_t),
 154                 [STATEMENT_DECLARATION] = sizeof(declaration_statement_t),
 155                 [STATEMENT_IF]          = sizeof(if_statement_t),
 156                 [STATEMENT_SWITCH]      = sizeof(switch_statement_t),
 157                 [STATEMENT_EXPRESSION]  = sizeof(expression_statement_t),
 158                 [STATEMENT_CONTINUE]    = sizeof(statement_base_t),
 159                 [STATEMENT_BREAK]       = sizeof(statement_base_t),
 160                 [STATEMENT_GOTO]        = sizeof(goto_statement_t),
 161                 [STATEMENT_LABEL]       = sizeof(label_statement_t),
 162                 [STATEMENT_CASE_LABEL]  = sizeof(case_label_statement_t),
 163                 [STATEMENT_WHILE]       = sizeof(while_statement_t),
 164                 [STATEMENT_DO_WHILE]    = sizeof(do_while_statement_t),
 165                 [STATEMENT_FOR]         = sizeof(for_statement_t),
 166                 [STATEMENT_ASM]         = sizeof(asm_statement_t)
 167         };
 168         assert(kind <= sizeof(sizes) / sizeof(sizes[0]));
 169         assert(sizes[kind] != 0);
 170         return sizes[kind];
 171 }
 172
 173 /**
 174  * Allocate a statement node of given kind and initialize all
 175  * fields with zero.
 176  */
 177 static statement_t *allocate_statement_zero(statement_kind_t kind)
 178 {
 179         size_t       size = get_statement_struct_size(kind);
 180         statement_t *res  = allocate_ast_zero(size);
 181
 182         res->base.kind = kind;
 183         return res;
 184 }
 185
 186 /**
 187  * Returns the size of an expression node.
 188  *
 189  * @param kind  the expression kind
 190  */
 191 static size_t get_expression_struct_size(expression_kind_t kind)
 192 {
 193         static const size_t sizes[] = {
 194                 [EXPR_INVALID]             = sizeof(expression_base_t),
 195                 [EXPR_REFERENCE]           = sizeof(reference_expression_t),
 196                 [EXPR_CONST]               = sizeof(const_expression_t),
 197                 [EXPR_STRING_LITERAL]      = sizeof(string_literal_expression_t),
 198                 [EXPR_WIDE_STRING_LITERAL] = sizeof(wide_string_literal_expression_t),
 199                 [EXPR_CALL]                = sizeof(call_expression_t),
 200                 [EXPR_UNARY_FIRST]         = sizeof(unary_expression_t),
 201                 [EXPR_BINARY_FIRST]        = sizeof(binary_expression_t),
 202                 [EXPR_CONDITIONAL]         = sizeof(conditional_expression_t),
 203                 [EXPR_SELECT]              = sizeof(select_expression_t),
 204                 [EXPR_ARRAY_ACCESS]        = sizeof(array_access_expression_t),
 205                 [EXPR_SIZEOF]              = sizeof(sizeof_expression_t),
 206                 [EXPR_CLASSIFY_TYPE]       = sizeof(classify_type_expression_t),
 207                 [EXPR_FUNCTION]            = sizeof(string_literal_expression_t),
 208                 [EXPR_PRETTY_FUNCTION]     = sizeof(string_literal_expression_t),
 209                 [EXPR_BUILTIN_SYMBOL]      = sizeof(builtin_symbol_expression_t),
 210                 [EXPR_BUILTIN_CONSTANT_P]  = sizeof(builtin_constant_expression_t),
 211                 [EXPR_BUILTIN_PREFETCH]    = sizeof(builtin_prefetch_expression_t),
 212                 [EXPR_OFFSETOF]            = sizeof(offsetof_expression_t),
 213                 [EXPR_VA_START]            = sizeof(va_start_expression_t),
 214                 [EXPR_VA_ARG]              = sizeof(va_arg_expression_t),
 215                 [EXPR_STATEMENT]           = sizeof(statement_expression_t),
 216         };
 217         if(kind >= EXPR_UNARY_FIRST && kind <= EXPR_UNARY_LAST) {
 218                 return sizes[EXPR_UNARY_FIRST];
 219         }
 220         if(kind >= EXPR_BINARY_FIRST && kind <= EXPR_BINARY_LAST) {
 221                 return sizes[EXPR_BINARY_FIRST];
 222         }
 223         assert(kind <= sizeof(sizes) / sizeof(sizes[0]));
 224         assert(sizes[kind] != 0);
 225         return sizes[kind];
 226 }
 227
 228 /**
 229  * Allocate an expression node of given kind and initialize all
 230  * fields with zero.
 231  */
 232 static expression_t *allocate_expression_zero(expression_kind_t kind)
 233 {
 234         size_t        size = get_expression_struct_size(kind);
 235         expression_t *res  = allocate_ast_zero(size);
 236
 237         res->base.kind = kind;
 238         return res;
 239 }
 240
 241 /**
 242  * Returns the size of a type node.
 243  *
 244  * @param kind  the type kind
 245  */
 246 static size_t get_type_struct_size(type_kind_t kind)
 247 {
 248         static const size_t sizes[] = {
 249                 [TYPE_ATOMIC]          = sizeof(atomic_type_t),
 250                 [TYPE_BITFIELD]        = sizeof(bitfield_type_t),
 251                 [TYPE_COMPOUND_STRUCT] = sizeof(compound_type_t),
 252                 [TYPE_COMPOUND_UNION]  = sizeof(compound_type_t),
 253                 [TYPE_ENUM]            = sizeof(enum_type_t),
 254                 [TYPE_FUNCTION]        = sizeof(function_type_t),
 255                 [TYPE_POINTER]         = sizeof(pointer_type_t),
 256                 [TYPE_ARRAY]           = sizeof(array_type_t),
 257                 [TYPE_BUILTIN]         = sizeof(builtin_type_t),
 258                 [TYPE_TYPEDEF]         = sizeof(typedef_type_t),
 259                 [TYPE_TYPEOF]          = sizeof(typeof_type_t),
 260         };
 261         assert(sizeof(sizes) / sizeof(sizes[0]) == (int) TYPE_TYPEOF + 1);
 262         assert(kind <= TYPE_TYPEOF);
 263         assert(sizes[kind] != 0);
 264         return sizes[kind];
 265 }
 266
 267 /**
 268  * Allocate a type node of given kind and initialize all
 269  * fields with zero.
 270  */
 271 static type_t *allocate_type_zero(type_kind_t kind)
 272 {
 273         size_t  size = get_type_struct_size(kind);
 274         type_t *res  = obstack_alloc(type_obst, size);
 275         memset(res, 0, size);
 276
 277         res->base.kind = kind;
 278         return res;
 279 }
 280
 281 /**
 282  * Returns the size of an initializer node.
 283  *
 284  * @param kind  the initializer kind
 285  */
 286 static size_t get_initializer_size(initializer_kind_t kind)
 287 {
 288         static const size_t sizes[] = {
 289                 [INITIALIZER_VALUE]       = sizeof(initializer_value_t),
 290                 [INITIALIZER_STRING]      = sizeof(initializer_string_t),
 291                 [INITIALIZER_WIDE_STRING] = sizeof(initializer_wide_string_t),
 292                 [INITIALIZER_LIST]        = sizeof(initializer_list_t)
 293         };
 294         assert(kind < sizeof(sizes) / sizeof(*sizes));
 295         assert(sizes[kind] != 0);
 296         return sizes[kind];
 297 }
 298
 299 /**
 300  * Allocate an initializer node of given kind and initialize all
 301  * fields with zero.
 302  */
 303 static initializer_t *allocate_initializer_zero(initializer_kind_t kind)
 304 {
 305         initializer_t *result = allocate_ast_zero(get_initializer_size(kind));
 306         result->kind          = kind;
 307
 308         return result;
 309 }
 310
 311 /**
 312  * Free a type from the type obstack.
 313  */
 314 static void free_type(void *type)
 315 {
 316         obstack_free(type_obst, type);
 317 }
 318
 319 /**
 320  * Returns the index of the top element of the environment stack.
 321  */
 322 static size_t environment_top(void)
 323 {
 324         return ARR_LEN(environment_stack);
 325 }
 326
 327 /**
 328  * Returns the index of the top element of the label stack.
 329  */
 330 static size_t label_top(void)
 331 {
 332         return ARR_LEN(label_stack);
 333 }
 334
 335
 336 /**
 337  * Return the next token.
 338  */
 339 static inline void next_token(void)
 340 {
 341         token                              = lookahead_buffer[lookahead_bufpos];
 342         lookahead_buffer[lookahead_bufpos] = lexer_token;
 343         lexer_next_token();
 344
 345         lookahead_bufpos = (lookahead_bufpos+1) % MAX_LOOKAHEAD;
 346
 347 #ifdef PRINT_TOKENS
 348         print_token(stderr, &token);
 349         fprintf(stderr, "\n");
 350 #endif
 351 }
 352
 353 /**
 354  * Return the next token with a given lookahead.
 355  */
 356 static inline const token_t *look_ahead(int num)
 357 {
 358         assert(num > 0 && num <= MAX_LOOKAHEAD);
 359         int pos = (lookahead_bufpos+num-1) % MAX_LOOKAHEAD;
 360         return &lookahead_buffer[pos];
 361 }
 362
 363 #define eat(token_type)  do { assert(token.type == token_type); next_token(); } while(0)
 364
 365 /**
 366  * Report a parse error because an expected token was not found.
 367  */
 368 static void parse_error_expected(const char *message, ...)
 369 {
 370         if(message != NULL) {
 371                 errorf(HERE, "%s", message);
 372         }
 373         va_list ap;
 374         va_start(ap, message);
 375         errorf(HERE, "got '%K', expected %#k", &token, &ap, ", ");
 376         va_end(ap);
 377 }
 378
 379 /**
 380  * Report a type error.
 381  */
 382 static void type_error(const char *msg, const source_position_t source_position,
 383                        type_t *type)
 384 {
 385         errorf(source_position, "%s, but found type '%T'", msg, type);
 386 }
 387
 388 /**
 389  * Report an incompatible type.
 390  */
 391 static void type_error_incompatible(const char *msg,
 392                 const source_position_t source_position, type_t *type1, type_t *type2)
 393 {
 394         errorf(source_position, "%s, incompatible types: '%T' - '%T'", msg, type1, type2);
 395 }
 396
 397 /**
 398  * Eat an complete block, ie. '{ ... }'.
 399  */
 400 static void eat_block(void)
 401 {
 402         if(token.type == '{')
 403                 next_token();
 404
 405         while(token.type != '}') {
 406                 if(token.type == T_EOF)
 407                         return;
 408                 if(token.type == '{') {
 409                         eat_block();
 410                         continue;
 411                 }
 412                 next_token();
 413         }
 414         eat('}');
 415 }
 416
 417 /**
 418  * Eat a statement until an ';' token.
 419  */
 420 static void eat_statement(void)
 421 {
 422         while(token.type != ';') {
 423                 if(token.type == T_EOF)
 424                         return;
 425                 if(token.type == '}')
 426                         return;
 427                 if(token.type == '{') {
 428                         eat_block();
 429                         continue;
 430                 }
 431                 next_token();
 432         }
 433         eat(';');
 434 }
 435
 436 /**
 437  * Eat a parenthesed term, ie. '( ... )'.
 438  */
 439 static void eat_paren(void)
 440 {
 441         if(token.type == '(')
 442                 next_token();
 443
 444         while(token.type != ')') {
 445                 if(token.type == T_EOF)
 446                         return;
 447                 if(token.type == ')' || token.type == ';' || token.type == '}') {
 448                         return;
 449                 }
 450                 if(token.type == '(') {
 451                         eat_paren();
 452                         continue;
 453                 }
 454                 if(token.type == '{') {
 455                         eat_block();
 456                         continue;
 457                 }
 458                 next_token();
 459         }
 460         eat(')');
 461 }
 462
 463 #define expect(expected)                           \
 464     if(UNLIKELY(token.type != (expected))) {       \
 465         parse_error_expected(NULL, (expected), 0); \
 466         eat_statement();                           \
 467         return NULL;                               \
 468     }                                              \
 469     next_token();
 470
 471 #define expect_block(expected)                     \
 472     if(UNLIKELY(token.type != (expected))) {       \
 473         parse_error_expected(NULL, (expected), 0); \
 474         eat_block();                               \
 475         return NULL;                               \
 476     }                                              \
 477     next_token();
 478
 479 #define expect_void(expected)                      \
 480     if(UNLIKELY(token.type != (expected))) {       \
 481         parse_error_expected(NULL, (expected), 0); \
 482         eat_statement();                           \
 483         return;                                    \
 484     }                                              \
 485     next_token();
 486
 487 static void set_context(context_t *new_context)
 488 {
 489         context = new_context;
 490
 491         last_declaration = new_context->declarations;
 492         if(last_declaration != NULL) {
 493                 while(last_declaration->next != NULL) {
 494                         last_declaration = last_declaration->next;
 495                 }
 496         }
 497 }
 498
 499 /**
 500  * Search a symbol in a given namespace and returns its declaration or
 501  * NULL if this symbol was not found.
 502  */
 503 static declaration_t *get_declaration(const symbol_t *const symbol, const namespace_t namespc)
 504 {
 505         declaration_t *declaration = symbol->declaration;
 506         for( ; declaration != NULL; declaration = declaration->symbol_next) {
 507                 if(declaration->namespc == namespc)
 508                         return declaration;
 509         }
 510
 511         return NULL;
 512 }
 513
 514 /**
 515  * pushs an environment_entry on the environment stack and links the
 516  * corresponding symbol to the new entry
 517  */
 518 static void stack_push(stack_entry_t **stack_ptr, declaration_t *declaration)
 519 {
 520         symbol_t    *symbol    = declaration->symbol;
 521         namespace_t  namespc = (namespace_t)declaration->namespc;
 522
 523         /* remember old declaration */
 524         stack_entry_t entry;
 525         entry.symbol          = symbol;
 526         entry.old_declaration = symbol->declaration;
 527         entry.namespc         = (unsigned short) namespc;
 528         ARR_APP1(stack_entry_t, *stack_ptr, entry);
 529
 530         /* replace/add declaration into declaration list of the symbol */
 531         if(symbol->declaration == NULL) {
 532                 symbol->declaration = declaration;
 533         } else {
 534                 declaration_t *iter_last = NULL;
 535                 declaration_t *iter      = symbol->declaration;
 536                 for( ; iter != NULL; iter_last = iter, iter = iter->symbol_next) {
 537                         /* replace an entry? */
 538                         if(iter->namespc == namespc) {
 539                                 if(iter_last == NULL) {
 540                                         symbol->declaration = declaration;
 541                                 } else {
 542                                         iter_last->symbol_next = declaration;
 543                                 }
 544                                 declaration->symbol_next = iter->symbol_next;
 545                                 break;
 546                         }
 547                 }
 548                 if(iter == NULL) {
 549                         assert(iter_last->symbol_next == NULL);
 550                         iter_last->symbol_next = declaration;
 551                 }
 552         }
 553 }
 554
 555 static void environment_push(declaration_t *declaration)
 556 {
 557         assert(declaration->source_position.input_name != NULL);
 558         assert(declaration->parent_context != NULL);
 559         stack_push(&environment_stack, declaration);
 560 }
 561
 562 static void label_push(declaration_t *declaration)
 563 {
 564         declaration->parent_context = &current_function->context;
 565         stack_push(&label_stack, declaration);
 566 }
 567
 568 /**
 569  * pops symbols from the environment stack until @p new_top is the top element
 570  */
 571 static void stack_pop_to(stack_entry_t **stack_ptr, size_t new_top)
 572 {
 573         stack_entry_t *stack = *stack_ptr;
 574         size_t         top   = ARR_LEN(stack);
 575         size_t         i;
 576
 577         assert(new_top <= top);
 578         if(new_top == top)
 579                 return;
 580
 581         for(i = top; i > new_top; --i) {
 582                 stack_entry_t *entry = &stack[i - 1];
 583
 584                 declaration_t *old_declaration = entry->old_declaration;
 585                 symbol_t      *symbol          = entry->symbol;
 586                 namespace_t    namespc         = (namespace_t)entry->namespc;
 587
 588                 /* replace/remove declaration */
 589                 declaration_t *declaration = symbol->declaration;
 590                 assert(declaration != NULL);
 591                 if(declaration->namespc == namespc) {
 592                         if(old_declaration == NULL) {
 593                                 symbol->declaration = declaration->symbol_next;
 594                         } else {
 595                                 symbol->declaration = old_declaration;
 596                         }
 597                 } else {
 598                         declaration_t *iter_last = declaration;
 599                         declaration_t *iter      = declaration->symbol_next;
 600                         for( ; iter != NULL; iter_last = iter, iter = iter->symbol_next) {
 601                                 /* replace an entry? */
 602                                 if(iter->namespc == namespc) {
 603                                         assert(iter_last != NULL);
 604                                         iter_last->symbol_next = old_declaration;
 605                                         old_declaration->symbol_next = iter->symbol_next;
 606                                         break;
 607                                 }
 608                         }
 609                         assert(iter != NULL);
 610                 }
 611         }
 612
 613         ARR_SHRINKLEN(*stack_ptr, (int) new_top);
 614 }
 615
 616 static void environment_pop_to(size_t new_top)
 617 {
 618         stack_pop_to(&environment_stack, new_top);
 619 }
 620
 621 static void label_pop_to(size_t new_top)
 622 {
 623         stack_pop_to(&label_stack, new_top);
 624 }
 625
 626
 627 static int get_rank(const type_t *type)
 628 {
 629         assert(!is_typeref(type));
 630         /* The C-standard allows promoting to int or unsigned int (see § 7.2.2
 631          * and esp. footnote 108). However we can't fold constants (yet), so we
 632          * can't decide whether unsigned int is possible, while int always works.
 633          * (unsigned int would be preferable when possible... for stuff like
 634          *  struct { enum { ... } bla : 4; } ) */
 635         if(type->kind == TYPE_ENUM)
 636                 return ATOMIC_TYPE_INT;
 637
 638         assert(type->kind == TYPE_ATOMIC);
 639         const atomic_type_t *atomic_type = &type->atomic;
 640         atomic_type_kind_t   atype       = atomic_type->akind;
 641         return atype;
 642 }
 643
 644 static type_t *promote_integer(type_t *type)
 645 {
 646         if(type->kind == TYPE_BITFIELD)
 647                 return promote_integer(type->bitfield.base);
 648
 649         if(get_rank(type) < ATOMIC_TYPE_INT)
 650                 type = type_int;
 651
 652         return type;
 653 }
 654
 655 /**
 656  * Create a cast expression.
 657  *
 658  * @param expression  the expression to cast
 659  * @param dest_type   the destination type
 660  */
 661 static expression_t *create_cast_expression(expression_t *expression,
 662                                             type_t *dest_type)
 663 {
 664         expression_t *cast = allocate_expression_zero(EXPR_UNARY_CAST_IMPLICIT);
 665
 666         cast->unary.value   = expression;
 667         cast->base.datatype = dest_type;
 668
 669         return cast;
 670 }
 671
 672 /**
 673  * Check if a given expression represents the 0 pointer constant.
 674  */
 675 static bool is_null_pointer_constant(const expression_t *expression)
 676 {
 677         /* skip void* cast */
 678         if(expression->kind == EXPR_UNARY_CAST
 679                         || expression->kind == EXPR_UNARY_CAST_IMPLICIT) {
 680                 expression = expression->unary.value;
 681         }
 682
 683         /* TODO: not correct yet, should be any constant integer expression
 684          * which evaluates to 0 */
 685         if (expression->kind != EXPR_CONST)
 686                 return false;
 687
 688         type_t *const type = skip_typeref(expression->base.datatype);
 689         if (!is_type_integer(type))
 690                 return false;
 691
 692         return expression->conste.v.int_value == 0;
 693 }
 694
 695 /**
 696  * Create an implicit cast expression.
 697  *
 698  * @param expression  the expression to cast
 699  * @param dest_type   the destination type
 700  */
 701 static expression_t *create_implicit_cast(expression_t *expression,
 702                                           type_t *dest_type)
 703 {
 704         type_t *source_type = expression->base.datatype;
 705
 706         if(source_type == NULL)
 707                 return expression;
 708
 709         source_type = skip_typeref(source_type);
 710         dest_type   = skip_typeref(dest_type);
 711
 712         if(source_type == dest_type)
 713                 return expression;
 714
 715         switch (dest_type->kind) {
 716                 case TYPE_ENUM:
 717                         /* TODO warning for implicitly converting to enum */
 718                 case TYPE_BITFIELD:
 719                 case TYPE_ATOMIC:
 720                         if (source_type->kind != TYPE_ATOMIC &&
 721                                         source_type->kind != TYPE_ENUM &&
 722                                         source_type->kind != TYPE_BITFIELD) {
 723                                 panic("casting of non-atomic types not implemented yet");
 724                         }
 725
 726                         if(is_type_floating(dest_type) && !is_type_scalar(source_type)) {
 727                                 type_error_incompatible("can't cast types",
 728                                                 expression->base.source_position, source_type,
 729                                                 dest_type);
 730                                 return expression;
 731                         }
 732
 733                         return create_cast_expression(expression, dest_type);
 734
 735                 case TYPE_POINTER:
 736                         switch (source_type->kind) {
 737                                 case TYPE_ATOMIC:
 738                                         if (is_null_pointer_constant(expression)) {
 739                                                 return create_cast_expression(expression, dest_type);
 740                                         }
 741                                         break;
 742
 743                                 case TYPE_POINTER:
 744                                         if (pointers_compatible(source_type, dest_type)) {
 745                                                 return create_cast_expression(expression, dest_type);
 746                                         }
 747                                         break;
 748
 749                                 case TYPE_ARRAY: {
 750                                         array_type_t   *array_type   = &source_type->array;
 751                                         pointer_type_t *pointer_type = &dest_type->pointer;
 752                                         if (types_compatible(array_type->element_type,
 753                                                                                  pointer_type->points_to)) {
 754                                                 return create_cast_expression(expression, dest_type);
 755                                         }
 756                                         break;
 757                                 }
 758
 759                                 default:
 760                                         panic("casting of non-atomic types not implemented yet");
 761                         }
 762
 763                         type_error_incompatible("can't implicitly cast types",
 764                                         expression->base.source_position, source_type, dest_type);
 765                         return expression;
 766
 767                 default:
 768                         panic("casting of non-atomic types not implemented yet");
 769         }
 770 }
 771
 772 /** Implements the rules from § 6.5.16.1 */
 773 static void semantic_assign(type_t *orig_type_left, expression_t **right,
 774                             const char *context)
 775 {
 776         type_t *orig_type_right = (*right)->base.datatype;
 777
 778         if(orig_type_right == NULL)
 779                 return;
 780
 781         type_t *const type_left  = skip_typeref(orig_type_left);
 782         type_t *const type_right = skip_typeref(orig_type_right);
 783
 784         if ((is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) ||
 785             (is_type_pointer(type_left) && is_null_pointer_constant(*right)) ||
 786             (is_type_atomic(type_left, ATOMIC_TYPE_BOOL)
 787                 && is_type_pointer(type_right))) {
 788                 *right = create_implicit_cast(*right, type_left);
 789                 return;
 790         }
 791
 792         if (is_type_pointer(type_left) && is_type_pointer(type_right)) {
 793                 pointer_type_t *pointer_type_left  = &type_left->pointer;
 794                 pointer_type_t *pointer_type_right = &type_right->pointer;
 795                 type_t         *points_to_left     = pointer_type_left->points_to;
 796                 type_t         *points_to_right    = pointer_type_right->points_to;
 797
 798                 points_to_left  = skip_typeref(points_to_left);
 799                 points_to_right = skip_typeref(points_to_right);
 800
 801                 /* the left type has all qualifiers from the right type */
 802                 unsigned missing_qualifiers
 803                         = points_to_right->base.qualifiers & ~points_to_left->base.qualifiers;
 804                 if(missing_qualifiers != 0) {
 805                         errorf(HERE, "destination type '%T' in %s from type '%T' lacks qualifiers '%Q' in pointed-to type", type_left, context, type_right, missing_qualifiers);
 806                         return;
 807                 }
 808
 809                 points_to_left  = get_unqualified_type(points_to_left);
 810                 points_to_right = get_unqualified_type(points_to_right);
 811
 812                 if(!is_type_atomic(points_to_left, ATOMIC_TYPE_VOID)
 813                                 && !is_type_atomic(points_to_right, ATOMIC_TYPE_VOID)
 814                                 && !types_compatible(points_to_left, points_to_right)) {
 815                         goto incompatible_assign_types;
 816                 }
 817
 818                 *right = create_implicit_cast(*right, type_left);
 819                 return;
 820         }
 821
 822         if (is_type_compound(type_left)
 823                         && types_compatible(type_left, type_right)) {
 824                 *right = create_implicit_cast(*right, type_left);
 825                 return;
 826         }
 827
 828 incompatible_assign_types:
 829         /* TODO: improve error message */
 830         errorf(HERE, "incompatible types in %s: '%T' <- '%T'",
 831                context, orig_type_left, orig_type_right);
 832 }
 833
 834 static expression_t *parse_constant_expression(void)
 835 {
 836         /* start parsing at precedence 7 (conditional expression) */
 837         expression_t *result = parse_sub_expression(7);
 838
 839         if(!is_constant_expression(result)) {
 840                 errorf(result->base.source_position, "expression '%E' is not constant\n", result);
 841         }
 842
 843         return result;
 844 }
 845
 846 static expression_t *parse_assignment_expression(void)
 847 {
 848         /* start parsing at precedence 2 (assignment expression) */
 849         return parse_sub_expression(2);
 850 }
 851
 852 static type_t *make_global_typedef(const char *name, type_t *type)
 853 {
 854         symbol_t *const symbol       = symbol_table_insert(name);
 855
 856         declaration_t *const declaration = allocate_declaration_zero();
 857         declaration->namespc         = NAMESPACE_NORMAL;
 858         declaration->storage_class   = STORAGE_CLASS_TYPEDEF;
 859         declaration->type            = type;
 860         declaration->symbol          = symbol;
 861         declaration->source_position = builtin_source_position;
 862
 863         record_declaration(declaration);
 864
 865         type_t *typedef_type               = allocate_type_zero(TYPE_TYPEDEF);
 866         typedef_type->typedeft.declaration = declaration;
 867
 868         return typedef_type;
 869 }
 870
 871 static string_t parse_string_literals(void)
 872 {
 873         assert(token.type == T_STRING_LITERAL);
 874         string_t result = token.v.string;
 875
 876         next_token();
 877
 878         while (token.type == T_STRING_LITERAL) {
 879                 result = concat_strings(&result, &token.v.string);
 880                 next_token();
 881         }
 882
 883         return result;
 884 }
 885
 886 static void parse_attributes(void)
 887 {
 888         while(true) {
 889                 switch(token.type) {
 890                 case T___attribute__: {
 891                         next_token();
 892
 893                         expect_void('(');
 894                         int depth = 1;
 895                         while(depth > 0) {
 896                                 switch(token.type) {
 897                                 case T_EOF:
 898                                         errorf(HERE, "EOF while parsing attribute");
 899                                         break;
 900                                 case '(':
 901                                         next_token();
 902                                         depth++;
 903                                         break;
 904                                 case ')':
 905                                         next_token();
 906                                         depth--;
 907                                         break;
 908                                 default:
 909                                         next_token();
 910                                 }
 911                         }
 912                         break;
 913                 }
 914                 case T_asm:
 915                         next_token();
 916                         expect_void('(');
 917                         if(token.type != T_STRING_LITERAL) {
 918                                 parse_error_expected("while parsing assembler attribute",
 919                                                      T_STRING_LITERAL);
 920                                 eat_paren();
 921                                 break;
 922                         } else {
 923                                 parse_string_literals();
 924                         }
 925                         expect_void(')');
 926                         break;
 927                 default:
 928                         goto attributes_finished;
 929                 }
 930         }
 931
 932 attributes_finished:
 933         ;
 934 }
 935
 936 #if 0
 937 static designator_t *parse_designation(void)
 938 {
 939         if(token.type != '[' && token.type != '.')
 940                 return NULL;
 941
 942         designator_t *result = NULL;
 943         designator_t *last   = NULL;
 944
 945         while(1) {
 946                 designator_t *designator;
 947                 switch(token.type) {
 948                 case '[':
 949                         designator = allocate_ast_zero(sizeof(designator[0]));
 950                         next_token();
 951                         designator->array_access = parse_constant_expression();
 952                         expect(']');
 953                         break;
 954                 case '.':
 955                         designator = allocate_ast_zero(sizeof(designator[0]));
 956                         next_token();
 957                         if(token.type != T_IDENTIFIER) {
 958                                 parse_error_expected("while parsing designator",
 959                                                      T_IDENTIFIER, 0);
 960                                 return NULL;
 961                         }
 962                         designator->symbol = token.v.symbol;
 963                         next_token();
 964                         break;
 965                 default:
 966                         expect('=');
 967                         return result;
 968                 }
 969
 970                 assert(designator != NULL);
 971                 if(last != NULL) {
 972                         last->next = designator;
 973                 } else {
 974                         result = designator;
 975                 }
 976                 last = designator;
 977         }
 978 }
 979 #endif
 980
 981 static initializer_t *initializer_from_string(array_type_t *type,
 982                                               const string_t *const string)
 983 {
 984         /* TODO: check len vs. size of array type */
 985         (void) type;
 986
 987         initializer_t *initializer = allocate_initializer_zero(INITIALIZER_STRING);
 988         initializer->string.string = *string;
 989
 990         return initializer;
 991 }
 992
 993 static initializer_t *initializer_from_wide_string(array_type_t *const type,
 994                                                    wide_string_t *const string)
 995 {
 996         /* TODO: check len vs. size of array type */
 997         (void) type;
 998
 999         initializer_t *const initializer =
1000                 allocate_initializer_zero(INITIALIZER_WIDE_STRING);
1001         initializer->wide_string.string = *string;
1002
1003         return initializer;
1004 }
1005
1006 static initializer_t *initializer_from_expression(type_t *type,
1007                                                   expression_t *expression)
1008 {
1009         /* TODO check that expression is a constant expression */
1010
1011         /* § 6.7.8.14/15 char array may be initialized by string literals */
1012         type_t *const expr_type = expression->base.datatype;
1013         if (is_type_array(type) && expr_type->kind == TYPE_POINTER) {
1014                 array_type_t *const array_type   = &type->array;
1015                 type_t       *const element_type = skip_typeref(array_type->element_type);
1016
1017                 if (element_type->kind == TYPE_ATOMIC) {
1018                         switch (expression->kind) {
1019                                 case EXPR_STRING_LITERAL:
1020                                         if (element_type->atomic.akind == ATOMIC_TYPE_CHAR) {
1021                                                 return initializer_from_string(array_type,
1022                                                         &expression->string.value);
1023                                         }
1024
1025                                 case EXPR_WIDE_STRING_LITERAL: {
1026                                         type_t *bare_wchar_type = skip_typeref(type_wchar_t);
1027                                         if (get_unqualified_type(element_type) == bare_wchar_type) {
1028                                                 return initializer_from_wide_string(array_type,
1029                                                         &expression->wide_string.value);
1030                                         }
1031                                 }
1032
1033                                 default:
1034                                         break;
1035                         }
1036                 }
1037         }
1038
1039         type_t *expression_type = skip_typeref(expression->base.datatype);
1040         if(is_type_scalar(type) || types_compatible(type, expression_type)) {
1041                 semantic_assign(type, &expression, "initializer");
1042
1043                 initializer_t *result = allocate_initializer_zero(INITIALIZER_VALUE);
1044                 result->value.value   = expression;
1045
1046                 return result;
1047         }
1048
1049         return NULL;
1050 }
1051
1052 static initializer_t *parse_sub_initializer(type_t *type,
1053                                             expression_t *expression,
1054                                             type_t *expression_type);
1055
1056 static initializer_t *parse_sub_initializer_elem(type_t *type)
1057 {
1058         if(token.type == '{') {
1059                 return parse_sub_initializer(type, NULL, NULL);
1060         }
1061
1062         expression_t *expression      = parse_assignment_expression();
1063         type_t       *expression_type = skip_typeref(expression->base.datatype);
1064
1065         return parse_sub_initializer(type, expression, expression_type);
1066 }
1067
1068 static bool had_initializer_brace_warning;
1069
1070 static void skip_designator(void)
1071 {
1072         while(1) {
1073                 if(token.type == '.') {
1074                         next_token();
1075                         if(token.type == T_IDENTIFIER)
1076                                 next_token();
1077                 } else if(token.type == '[') {
1078                         next_token();
1079                         parse_constant_expression();
1080                         if(token.type == ']')
1081                                 next_token();
1082                 } else {
1083                         break;
1084                 }
1085         }
1086 }
1087
1088 static initializer_t *parse_sub_initializer(type_t *type,
1089                                             expression_t *expression,
1090                                             type_t *expression_type)
1091 {
1092         if(is_type_scalar(type)) {
1093                 /* there might be extra {} hierarchies */
1094                 if(token.type == '{') {
1095                         next_token();
1096                         if(!had_initializer_brace_warning) {
1097                                 warningf(HERE, "braces around scalar initializer");
1098                                 had_initializer_brace_warning = true;
1099                         }
1100                         initializer_t *result = parse_sub_initializer(type, NULL, NULL);
1101                         if(token.type == ',') {
1102                                 next_token();
1103                                 /* TODO: warn about excessive elements */
1104                         }
1105                         expect_block('}');
1106                         return result;
1107                 }
1108
1109                 if(expression == NULL) {
1110                         expression = parse_assignment_expression();
1111                 }
1112                 return initializer_from_expression(type, expression);
1113         }
1114
1115         /* does the expression match the currently looked at object to initialize */
1116         if(expression != NULL) {
1117                 initializer_t *result = initializer_from_expression(type, expression);
1118                 if(result != NULL)
1119                         return result;
1120         }
1121
1122         bool read_paren = false;
1123         if(token.type == '{') {
1124                 next_token();
1125                 read_paren = true;
1126         }
1127
1128         /* descend into subtype */
1129         initializer_t  *result = NULL;
1130         initializer_t **elems;
1131         if(is_type_array(type)) {
1132                 array_type_t *array_type   = &type->array;
1133                 type_t       *element_type = array_type->element_type;
1134                 element_type               = skip_typeref(element_type);
1135
1136                 if(token.type == '.') {
1137                         errorf(HERE,
1138                                "compound designator in initializer for array type '%T'",
1139                                type);
1140                         skip_designator();
1141                 }
1142
1143                 initializer_t *sub;
1144                 had_initializer_brace_warning = false;
1145                 if(expression == NULL) {
1146                         sub = parse_sub_initializer_elem(element_type);
1147                 } else {
1148                         sub = parse_sub_initializer(element_type, expression,
1149                                                     expression_type);
1150                 }
1151
1152                 /* didn't match the subtypes -> try the parent type */
1153                 if(sub == NULL) {
1154                         assert(!read_paren);
1155                         return NULL;
1156                 }
1157
1158                 elems = NEW_ARR_F(initializer_t*, 0);
1159                 ARR_APP1(initializer_t*, elems, sub);
1160
1161                 while(true) {
1162                         if(token.type == '}')
1163                                 break;
1164                         expect_block(',');
1165                         if(token.type == '}')
1166                                 break;
1167
1168                         sub = parse_sub_initializer_elem(element_type);
1169                         if(sub == NULL) {
1170                                 /* TODO error, do nicer cleanup */
1171                                 errorf(HERE, "member initializer didn't match");
1172                                 DEL_ARR_F(elems);
1173                                 return NULL;
1174                         }
1175                         ARR_APP1(initializer_t*, elems, sub);
1176                 }
1177         } else {
1178                 assert(is_type_compound(type));
1179                 compound_type_t *compound_type = &type->compound;
1180                 context_t       *context       = &compound_type->declaration->context;
1181
1182                 if(token.type == '[') {
1183                         errorf(HERE,
1184                                "array designator in initializer for compound type '%T'",
1185                                type);
1186                         skip_designator();
1187                 }
1188
1189                 declaration_t *first = context->declarations;
1190                 if(first == NULL)
1191                         return NULL;
1192                 type_t *first_type = first->type;
1193                 first_type         = skip_typeref(first_type);
1194
1195                 initializer_t *sub;
1196                 had_initializer_brace_warning = false;
1197                 if(expression == NULL) {
1198                         sub = parse_sub_initializer_elem(first_type);
1199                 } else {
1200                         sub = parse_sub_initializer(first_type, expression,expression_type);
1201                 }
1202
1203                 /* didn't match the subtypes -> try our parent type */
1204                 if(sub == NULL) {
1205                         assert(!read_paren);
1206                         return NULL;
1207                 }
1208
1209                 elems = NEW_ARR_F(initializer_t*, 0);
1210                 ARR_APP1(initializer_t*, elems, sub);
1211
1212                 declaration_t *iter  = first->next;
1213                 for( ; iter != NULL; iter = iter->next) {
1214                         if(iter->symbol == NULL)
1215                                 continue;
1216                         if(iter->namespc != NAMESPACE_NORMAL)
1217                                 continue;
1218
1219                         if(token.type == '}')
1220                                 break;
1221                         expect_block(',');
1222                         if(token.type == '}')
1223                                 break;
1224
1225                         type_t *iter_type = iter->type;
1226                         iter_type         = skip_typeref(iter_type);
1227
1228                         sub = parse_sub_initializer_elem(iter_type);
1229                         if(sub == NULL) {
1230                                 /* TODO error, do nicer cleanup */
1231                                 errorf(HERE, "member initializer didn't match");
1232                                 DEL_ARR_F(elems);
1233                                 return NULL;
1234                         }
1235                         ARR_APP1(initializer_t*, elems, sub);
1236                 }
1237         }
1238
1239         int    len        = ARR_LEN(elems);
1240         size_t elems_size = sizeof(initializer_t*) * len;
1241
1242         initializer_list_t *init = allocate_ast_zero(sizeof(init[0]) + elems_size);
1243
1244         init->initializer.kind = INITIALIZER_LIST;
1245         init->len              = len;
1246         memcpy(init->initializers, elems, elems_size);
1247         DEL_ARR_F(elems);
1248
1249         result = (initializer_t*) init;
1250
1251         if(read_paren) {
1252                 if(token.type == ',')
1253                         next_token();
1254                 expect('}');
1255         }
1256         return result;
1257 }
1258
1259 static initializer_t *parse_initializer(type_t *const orig_type)
1260 {
1261         initializer_t *result;
1262
1263         type_t *const type = skip_typeref(orig_type);
1264
1265         if(token.type != '{') {
1266                 expression_t  *expression  = parse_assignment_expression();
1267                 if (expression->base.datatype == NULL) {
1268                         /* something bad happens, don't produce further errors */
1269                         return NULL;
1270                 }
1271                 initializer_t *initializer = initializer_from_expression(type, expression);
1272                 if(initializer == NULL) {
1273                         errorf(HERE,
1274                                 "initializer expression '%E' of type '%T' is incompatible with type '%T'",
1275                                 expression, expression->base.datatype, orig_type);
1276                 }
1277                 return initializer;
1278         }
1279
1280         if(is_type_scalar(type)) {
1281                 /* § 6.7.8.11 */
1282                 eat('{');
1283
1284                 expression_t *expression = parse_assignment_expression();
1285                 result = initializer_from_expression(type, expression);
1286
1287                 if(token.type == ',')
1288                         next_token();
1289
1290                 expect('}');
1291                 return result;
1292         } else {
1293                 result = parse_sub_initializer(type, NULL, NULL);
1294         }
1295
1296         return result;
1297 }
1298
1299 static declaration_t *append_declaration(declaration_t *declaration);
1300
1301 static declaration_t *parse_compound_type_specifier(bool is_struct)
1302 {
1303         if(is_struct) {
1304                 eat(T_struct);
1305         } else {
1306                 eat(T_union);
1307         }
1308
1309         symbol_t      *symbol      = NULL;
1310         declaration_t *declaration = NULL;
1311
1312         if (token.type == T___attribute__) {
1313                 /* TODO */
1314                 parse_attributes();
1315         }
1316
1317         if(token.type == T_IDENTIFIER) {
1318                 symbol = token.v.symbol;
1319                 next_token();
1320
1321                 if(is_struct) {
1322                         declaration = get_declaration(symbol, NAMESPACE_STRUCT);
1323                 } else {
1324                         declaration = get_declaration(symbol, NAMESPACE_UNION);
1325                 }
1326         } else if(token.type != '{') {
1327                 if(is_struct) {
1328                         parse_error_expected("while parsing struct type specifier",
1329                                              T_IDENTIFIER, '{', 0);
1330                 } else {
1331                         parse_error_expected("while parsing union type specifier",
1332                                              T_IDENTIFIER, '{', 0);
1333                 }
1334
1335                 return NULL;
1336         }
1337
1338         if(declaration == NULL) {
1339                 declaration = allocate_declaration_zero();
1340                 declaration->namespc         =
1341                         (is_struct ? NAMESPACE_STRUCT : NAMESPACE_UNION);
1342                 declaration->source_position = token.source_position;
1343                 declaration->symbol          = symbol;
1344                 declaration->parent_context  = context;
1345                 if (symbol != NULL) {
1346                         environment_push(declaration);
1347                 }
1348                 append_declaration(declaration);
1349         }
1350
1351         if(token.type == '{') {
1352                 if(declaration->init.is_defined) {
1353                         assert(symbol != NULL);
1354                         errorf(HERE, "multiple definition of '%s %Y'",
1355                                is_struct ? "struct" : "union", symbol);
1356                         declaration->context.declarations = NULL;
1357                 }
1358                 declaration->init.is_defined = true;
1359
1360                 int         top          = environment_top();
1361                 context_t  *last_context = context;
1362                 set_context(&declaration->context);
1363
1364                 parse_compound_type_entries();
1365                 parse_attributes();
1366
1367                 assert(context == &declaration->context);
1368                 set_context(last_context);
1369                 environment_pop_to(top);
1370         }
1371
1372         return declaration;
1373 }
1374
1375 static void parse_enum_entries(type_t *const enum_type)
1376 {
1377         eat('{');
1378
1379         if(token.type == '}') {
1380                 next_token();
1381                 errorf(HERE, "empty enum not allowed");
1382                 return;
1383         }
1384
1385         do {
1386                 if(token.type != T_IDENTIFIER) {
1387                         parse_error_expected("while parsing enum entry", T_IDENTIFIER, 0);
1388                         eat_block();
1389                         return;
1390                 }
1391
1392                 declaration_t *const entry = allocate_declaration_zero();
1393                 entry->storage_class   = STORAGE_CLASS_ENUM_ENTRY;
1394                 entry->type            = enum_type;
1395                 entry->symbol          = token.v.symbol;
1396                 entry->source_position = token.source_position;
1397                 next_token();
1398
1399                 if(token.type == '=') {
1400                         next_token();
1401                         entry->init.enum_value = parse_constant_expression();
1402
1403                         /* TODO semantic */
1404                 }
1405
1406                 record_declaration(entry);
1407
1408                 if(token.type != ',')
1409                         break;
1410                 next_token();
1411         } while(token.type != '}');
1412
1413         expect_void('}');
1414 }
1415
1416 static type_t *parse_enum_specifier(void)
1417 {
1418         eat(T_enum);
1419
1420         declaration_t *declaration;
1421         symbol_t      *symbol;
1422
1423         if(token.type == T_IDENTIFIER) {
1424                 symbol = token.v.symbol;
1425                 next_token();
1426
1427                 declaration = get_declaration(symbol, NAMESPACE_ENUM);
1428         } else if(token.type != '{') {
1429                 parse_error_expected("while parsing enum type specifier",
1430                                      T_IDENTIFIER, '{', 0);
1431                 return NULL;
1432         } else {
1433                 declaration = NULL;
1434                 symbol      = NULL;
1435         }
1436
1437         if(declaration == NULL) {
1438                 declaration = allocate_declaration_zero();
1439                 declaration->namespc         = NAMESPACE_ENUM;
1440                 declaration->source_position = token.source_position;
1441                 declaration->symbol          = symbol;
1442                 declaration->parent_context  = context;
1443         }
1444
1445         type_t *const type      = allocate_type_zero(TYPE_ENUM);
1446         type->enumt.declaration = declaration;
1447
1448         if(token.type == '{') {
1449                 if(declaration->init.is_defined) {
1450                         errorf(HERE, "multiple definitions of enum %Y", symbol);
1451                 }
1452                 if (symbol != NULL) {
1453                         environment_push(declaration);
1454                 }
1455                 append_declaration(declaration);
1456                 declaration->init.is_defined = 1;
1457
1458                 parse_enum_entries(type);
1459                 parse_attributes();
1460         }
1461
1462         return type;
1463 }
1464
1465 /**
1466  * if a symbol is a typedef to another type, return true
1467  */
1468 static bool is_typedef_symbol(symbol_t *symbol)
1469 {
1470         const declaration_t *const declaration =
1471                 get_declaration(symbol, NAMESPACE_NORMAL);
1472         return
1473                 declaration != NULL &&
1474                 declaration->storage_class == STORAGE_CLASS_TYPEDEF;
1475 }
1476
1477 static type_t *parse_typeof(void)
1478 {
1479         eat(T___typeof__);
1480
1481         type_t *type;
1482
1483         expect('(');
1484
1485         expression_t *expression  = NULL;
1486
1487 restart:
1488         switch(token.type) {
1489         case T___extension__:
1490                 /* this can be a prefix to a typename or an expression */
1491                 /* we simply eat it now. */
1492                 do {
1493                         next_token();
1494                 } while(token.type == T___extension__);
1495                 goto restart;
1496
1497         case T_IDENTIFIER:
1498                 if(is_typedef_symbol(token.v.symbol)) {
1499                         type = parse_typename();
1500                 } else {
1501                         expression = parse_expression();
1502                         type       = expression->base.datatype;
1503                 }
1504                 break;
1505
1506         TYPENAME_START
1507                 type = parse_typename();
1508                 break;
1509
1510         default:
1511                 expression = parse_expression();
1512                 type       = expression->base.datatype;
1513                 break;
1514         }
1515
1516         expect(')');
1517
1518         type_t *typeof_type              = allocate_type_zero(TYPE_TYPEOF);
1519         typeof_type->typeoft.expression  = expression;
1520         typeof_type->typeoft.typeof_type = type;
1521
1522         return typeof_type;
1523 }
1524
1525 typedef enum {
1526         SPECIFIER_SIGNED    = 1 << 0,
1527         SPECIFIER_UNSIGNED  = 1 << 1,
1528         SPECIFIER_LONG      = 1 << 2,
1529         SPECIFIER_INT       = 1 << 3,
1530         SPECIFIER_DOUBLE    = 1 << 4,
1531         SPECIFIER_CHAR      = 1 << 5,
1532         SPECIFIER_SHORT     = 1 << 6,
1533         SPECIFIER_LONG_LONG = 1 << 7,
1534         SPECIFIER_FLOAT     = 1 << 8,
1535         SPECIFIER_BOOL      = 1 << 9,
1536         SPECIFIER_VOID      = 1 << 10,
1537 #ifdef PROVIDE_COMPLEX
1538         SPECIFIER_COMPLEX   = 1 << 11,
1539         SPECIFIER_IMAGINARY = 1 << 12,
1540 #endif
1541 } specifiers_t;
1542
1543 static type_t *create_builtin_type(symbol_t *const symbol,
1544                                    type_t *const real_type)
1545 {
1546         type_t *type            = allocate_type_zero(TYPE_BUILTIN);
1547         type->builtin.symbol    = symbol;
1548         type->builtin.real_type = real_type;
1549
1550         type_t *result = typehash_insert(type);
1551         if (type != result) {
1552                 free_type(type);
1553         }
1554
1555         return result;
1556 }
1557
1558 static type_t *get_typedef_type(symbol_t *symbol)
1559 {
1560         declaration_t *declaration = get_declaration(symbol, NAMESPACE_NORMAL);
1561         if(declaration == NULL
1562                         || declaration->storage_class != STORAGE_CLASS_TYPEDEF)
1563                 return NULL;
1564
1565         type_t *type               = allocate_type_zero(TYPE_TYPEDEF);
1566         type->typedeft.declaration = declaration;
1567
1568         return type;
1569 }
1570
1571 static void parse_declaration_specifiers(declaration_specifiers_t *specifiers)
1572 {
1573         type_t   *type            = NULL;
1574         unsigned  type_qualifiers = 0;
1575         unsigned  type_specifiers = 0;
1576         int       newtype         = 0;
1577
1578         specifiers->source_position = token.source_position;
1579
1580         while(true) {
1581                 switch(token.type) {
1582
1583                 /* storage class */
1584 #define MATCH_STORAGE_CLASS(token, class)                                \
1585                 case token:                                                      \
1586                         if(specifiers->storage_class != STORAGE_CLASS_NONE) {        \
1587                                 errorf(HERE, "multiple storage classes in declaration specifiers"); \
1588                         }                                                            \
1589                         specifiers->storage_class = class;                           \
1590                         next_token();                                                \
1591                         break;
1592
1593                 MATCH_STORAGE_CLASS(T_typedef,  STORAGE_CLASS_TYPEDEF)
1594                 MATCH_STORAGE_CLASS(T_extern,   STORAGE_CLASS_EXTERN)
1595                 MATCH_STORAGE_CLASS(T_static,   STORAGE_CLASS_STATIC)
1596                 MATCH_STORAGE_CLASS(T_auto,     STORAGE_CLASS_AUTO)
1597                 MATCH_STORAGE_CLASS(T_register, STORAGE_CLASS_REGISTER)
1598
1599                 case T___thread:
1600                         switch (specifiers->storage_class) {
1601                                 case STORAGE_CLASS_NONE:
1602                                         specifiers->storage_class = STORAGE_CLASS_THREAD;
1603                                         break;
1604
1605                                 case STORAGE_CLASS_EXTERN:
1606                                         specifiers->storage_class = STORAGE_CLASS_THREAD_EXTERN;
1607                                         break;
1608
1609                                 case STORAGE_CLASS_STATIC:
1610                                         specifiers->storage_class = STORAGE_CLASS_THREAD_STATIC;
1611                                         break;
1612
1613                                 default:
1614                                         errorf(HERE, "multiple storage classes in declaration specifiers");
1615                                         break;
1616                         }
1617                         next_token();
1618                         break;
1619
1620                 /* type qualifiers */
1621 #define MATCH_TYPE_QUALIFIER(token, qualifier)                          \
1622                 case token:                                                     \
1623                         type_qualifiers |= qualifier;                               \
1624                         next_token();                                               \
1625                         break;
1626
1627                 MATCH_TYPE_QUALIFIER(T_const,    TYPE_QUALIFIER_CONST);
1628                 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
1629                 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
1630
1631                 case T___extension__:
1632                         /* TODO */
1633                         next_token();
1634                         break;
1635
1636                 /* type specifiers */
1637 #define MATCH_SPECIFIER(token, specifier, name)                         \
1638                 case token:                                                     \
1639                         next_token();                                               \
1640                         if(type_specifiers & specifier) {                           \
1641                                 errorf(HERE, "multiple " name " type specifiers given"); \
1642                         } else {                                                    \
1643                                 type_specifiers |= specifier;                           \
1644                         }                                                           \
1645                         break;
1646
1647                 MATCH_SPECIFIER(T_void,       SPECIFIER_VOID,      "void")
1648                 MATCH_SPECIFIER(T_char,       SPECIFIER_CHAR,      "char")
1649                 MATCH_SPECIFIER(T_short,      SPECIFIER_SHORT,     "short")
1650                 MATCH_SPECIFIER(T_int,        SPECIFIER_INT,       "int")
1651                 MATCH_SPECIFIER(T_float,      SPECIFIER_FLOAT,     "float")
1652                 MATCH_SPECIFIER(T_double,     SPECIFIER_DOUBLE,    "double")
1653                 MATCH_SPECIFIER(T_signed,     SPECIFIER_SIGNED,    "signed")
1654                 MATCH_SPECIFIER(T_unsigned,   SPECIFIER_UNSIGNED,  "unsigned")
1655                 MATCH_SPECIFIER(T__Bool,      SPECIFIER_BOOL,      "_Bool")
1656 #ifdef PROVIDE_COMPLEX
1657                 MATCH_SPECIFIER(T__Complex,   SPECIFIER_COMPLEX,   "_Complex")
1658                 MATCH_SPECIFIER(T__Imaginary, SPECIFIER_IMAGINARY, "_Imaginary")
1659 #endif
1660                 case T_forceinline:
1661                         /* only in microsoft mode */
1662                         specifiers->decl_modifiers |= DM_FORCEINLINE;
1663
1664                 case T_inline:
1665                         next_token();
1666                         specifiers->is_inline = true;
1667                         break;
1668
1669                 case T_long:
1670                         next_token();
1671                         if(type_specifiers & SPECIFIER_LONG_LONG) {
1672                                 errorf(HERE, "multiple type specifiers given");
1673                         } else if(type_specifiers & SPECIFIER_LONG) {
1674                                 type_specifiers |= SPECIFIER_LONG_LONG;
1675                         } else {
1676                                 type_specifiers |= SPECIFIER_LONG;
1677                         }
1678                         break;
1679
1680                 /* TODO: if type != NULL for the following rules should issue
1681                  * an error */
1682                 case T_struct: {
1683                         type = allocate_type_zero(TYPE_COMPOUND_STRUCT);
1684
1685                         type->compound.declaration = parse_compound_type_specifier(true);
1686                         break;
1687                 }
1688                 case T_union: {
1689                         type = allocate_type_zero(TYPE_COMPOUND_STRUCT);
1690
1691                         type->compound.declaration = parse_compound_type_specifier(false);
1692                         break;
1693                 }
1694                 case T_enum:
1695                         type = parse_enum_specifier();
1696                         break;
1697                 case T___typeof__:
1698                         type = parse_typeof();
1699                         break;
1700                 case T___builtin_va_list:
1701                         type = duplicate_type(type_valist);
1702                         next_token();
1703                         break;
1704
1705                 case T___attribute__:
1706                         /* TODO */
1707                         parse_attributes();
1708                         break;
1709
1710                 case T_IDENTIFIER: {
1711                         type_t *typedef_type = get_typedef_type(token.v.symbol);
1712
1713                         if(typedef_type == NULL)
1714                                 goto finish_specifiers;
1715
1716                         next_token();
1717                         type = typedef_type;
1718                         break;
1719                 }
1720
1721                 /* function specifier */
1722                 default:
1723                         goto finish_specifiers;
1724                 }
1725         }
1726
1727 finish_specifiers:
1728
1729         if(type == NULL) {
1730                 atomic_type_kind_t atomic_type;
1731
1732                 /* match valid basic types */
1733                 switch(type_specifiers) {
1734                 case SPECIFIER_VOID:
1735                         atomic_type = ATOMIC_TYPE_VOID;
1736                         break;
1737                 case SPECIFIER_CHAR:
1738                         atomic_type = ATOMIC_TYPE_CHAR;
1739                         break;
1740                 case SPECIFIER_SIGNED | SPECIFIER_CHAR:
1741                         atomic_type = ATOMIC_TYPE_SCHAR;
1742                         break;
1743                 case SPECIFIER_UNSIGNED | SPECIFIER_CHAR:
1744                         atomic_type = ATOMIC_TYPE_UCHAR;
1745                         break;
1746                 case SPECIFIER_SHORT:
1747                 case SPECIFIER_SIGNED | SPECIFIER_SHORT:
1748                 case SPECIFIER_SHORT | SPECIFIER_INT:
1749                 case SPECIFIER_SIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
1750                         atomic_type = ATOMIC_TYPE_SHORT;
1751                         break;
1752                 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT:
1753                 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
1754                         atomic_type = ATOMIC_TYPE_USHORT;
1755                         break;
1756                 case SPECIFIER_INT:
1757                 case SPECIFIER_SIGNED:
1758                 case SPECIFIER_SIGNED | SPECIFIER_INT:
1759                         atomic_type = ATOMIC_TYPE_INT;
1760                         break;
1761                 case SPECIFIER_UNSIGNED:
1762                 case SPECIFIER_UNSIGNED | SPECIFIER_INT:
1763                         atomic_type = ATOMIC_TYPE_UINT;
1764                         break;
1765                 case SPECIFIER_LONG:
1766                 case SPECIFIER_SIGNED | SPECIFIER_LONG:
1767                 case SPECIFIER_LONG | SPECIFIER_INT:
1768                 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_INT:
1769                         atomic_type = ATOMIC_TYPE_LONG;
1770                         break;
1771                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG:
1772                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_INT:
1773                         atomic_type = ATOMIC_TYPE_ULONG;
1774                         break;
1775                 case SPECIFIER_LONG | SPECIFIER_LONG_LONG:
1776                 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG:
1777                 case SPECIFIER_LONG | SPECIFIER_LONG_LONG | SPECIFIER_INT:
1778                 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG
1779                         | SPECIFIER_INT:
1780                         atomic_type = ATOMIC_TYPE_LONGLONG;
1781                         break;
1782                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG:
1783                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG
1784                         | SPECIFIER_INT:
1785                         atomic_type = ATOMIC_TYPE_ULONGLONG;
1786                         break;
1787                 case SPECIFIER_FLOAT:
1788                         atomic_type = ATOMIC_TYPE_FLOAT;
1789                         break;
1790                 case SPECIFIER_DOUBLE:
1791                         atomic_type = ATOMIC_TYPE_DOUBLE;
1792                         break;
1793                 case SPECIFIER_LONG | SPECIFIER_DOUBLE:
1794                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE;
1795                         break;
1796                 case SPECIFIER_BOOL:
1797                         atomic_type = ATOMIC_TYPE_BOOL;
1798                         break;
1799 #ifdef PROVIDE_COMPLEX
1800                 case SPECIFIER_FLOAT | SPECIFIER_COMPLEX:
1801                         atomic_type = ATOMIC_TYPE_FLOAT_COMPLEX;
1802                         break;
1803                 case SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
1804                         atomic_type = ATOMIC_TYPE_DOUBLE_COMPLEX;
1805                         break;
1806                 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
1807                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE_COMPLEX;
1808                         break;
1809                 case SPECIFIER_FLOAT | SPECIFIER_IMAGINARY:
1810                         atomic_type = ATOMIC_TYPE_FLOAT_IMAGINARY;
1811                         break;
1812                 case SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
1813                         atomic_type = ATOMIC_TYPE_DOUBLE_IMAGINARY;
1814                         break;
1815                 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
1816                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY;
1817                         break;
1818 #endif
1819                 default:
1820                         /* invalid specifier combination, give an error message */
1821                         if(type_specifiers == 0) {
1822                                 if (! strict_mode) {
1823                                         warningf(HERE, "no type specifiers in declaration, using int");
1824                                         atomic_type = ATOMIC_TYPE_INT;
1825                                         break;
1826                                 } else {
1827                                         errorf(HERE, "no type specifiers given in declaration");
1828                                 }
1829                         } else if((type_specifiers & SPECIFIER_SIGNED) &&
1830                                   (type_specifiers & SPECIFIER_UNSIGNED)) {
1831                                 errorf(HERE, "signed and unsigned specifiers gives");
1832                         } else if(type_specifiers & (SPECIFIER_SIGNED | SPECIFIER_UNSIGNED)) {
1833                                 errorf(HERE, "only integer types can be signed or unsigned");
1834                         } else {
1835                                 errorf(HERE, "multiple datatypes in declaration");
1836                         }
1837                         atomic_type = ATOMIC_TYPE_INVALID;
1838                 }
1839
1840                 type               = allocate_type_zero(TYPE_ATOMIC);
1841                 type->atomic.akind = atomic_type;
1842                 newtype            = 1;
1843         } else {
1844                 if(type_specifiers != 0) {
1845                         errorf(HERE, "multiple datatypes in declaration");
1846                 }
1847         }
1848
1849         type->base.qualifiers = type_qualifiers;
1850
1851         type_t *result = typehash_insert(type);
1852         if(newtype && result != type) {
1853                 free_type(type);
1854         }
1855
1856         specifiers->type = result;
1857 }
1858
1859 static type_qualifiers_t parse_type_qualifiers(void)
1860 {
1861         type_qualifiers_t type_qualifiers = TYPE_QUALIFIER_NONE;
1862
1863         while(true) {
1864                 switch(token.type) {
1865                 /* type qualifiers */
1866                 MATCH_TYPE_QUALIFIER(T_const,    TYPE_QUALIFIER_CONST);
1867                 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
1868                 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
1869
1870                 default:
1871                         return type_qualifiers;
1872                 }
1873         }
1874 }
1875
1876 static declaration_t *parse_identifier_list(void)
1877 {
1878         declaration_t *declarations     = NULL;
1879         declaration_t *last_declaration = NULL;
1880         do {
1881                 declaration_t *const declaration = allocate_declaration_zero();
1882                 declaration->source_position = token.source_position;
1883                 declaration->symbol          = token.v.symbol;
1884                 next_token();
1885
1886                 if(last_declaration != NULL) {
1887                         last_declaration->next = declaration;
1888                 } else {
1889                         declarations = declaration;
1890                 }
1891                 last_declaration = declaration;
1892
1893                 if(token.type != ',')
1894                         break;
1895                 next_token();
1896         } while(token.type == T_IDENTIFIER);
1897
1898         return declarations;
1899 }
1900
1901 static void semantic_parameter(declaration_t *declaration)
1902 {
1903         /* TODO: improve error messages */
1904
1905         if(declaration->storage_class == STORAGE_CLASS_TYPEDEF) {
1906                 errorf(HERE, "typedef not allowed in parameter list");
1907         } else if(declaration->storage_class != STORAGE_CLASS_NONE
1908                         && declaration->storage_class != STORAGE_CLASS_REGISTER) {
1909                 errorf(HERE, "parameter may only have none or register storage class");
1910         }
1911
1912         type_t *orig_type = declaration->type;
1913         if(orig_type == NULL)
1914                 return;
1915         type_t *type = skip_typeref(orig_type);
1916
1917         /* Array as last part of a parameter type is just syntactic sugar.  Turn it
1918          * into a pointer. § 6.7.5.3 (7) */
1919         if (is_type_array(type)) {
1920                 const array_type_t *arr_type     = &type->array;
1921                 type_t             *element_type = arr_type->element_type;
1922
1923                 type = make_pointer_type(element_type, type->base.qualifiers);
1924
1925                 declaration->type = type;
1926         }
1927
1928         if(is_type_incomplete(type)) {
1929                 errorf(HERE, "incomplete type ('%T') not allowed for parameter '%Y'",
1930                        orig_type, declaration->symbol);
1931         }
1932 }
1933
1934 static declaration_t *parse_parameter(void)
1935 {
1936         declaration_specifiers_t specifiers;
1937         memset(&specifiers, 0, sizeof(specifiers));
1938
1939         parse_declaration_specifiers(&specifiers);
1940
1941         declaration_t *declaration = parse_declarator(&specifiers, /*may_be_abstract=*/true);
1942
1943         semantic_parameter(declaration);
1944
1945         return declaration;
1946 }
1947
1948 static declaration_t *parse_parameters(function_type_t *type)
1949 {
1950         if(token.type == T_IDENTIFIER) {
1951                 symbol_t *symbol = token.v.symbol;
1952                 if(!is_typedef_symbol(symbol)) {
1953                         type->kr_style_parameters = true;
1954                         return parse_identifier_list();
1955                 }
1956         }
1957
1958         if(token.type == ')') {
1959                 type->unspecified_parameters = 1;
1960                 return NULL;
1961         }
1962         if(token.type == T_void && look_ahead(1)->type == ')') {
1963                 next_token();
1964                 return NULL;
1965         }
1966
1967         declaration_t        *declarations = NULL;
1968         declaration_t        *declaration;
1969         declaration_t        *last_declaration = NULL;
1970         function_parameter_t *parameter;
1971         function_parameter_t *last_parameter = NULL;
1972
1973         while(true) {
1974                 switch(token.type) {
1975                 case T_DOTDOTDOT:
1976                         next_token();
1977                         type->variadic = 1;
1978                         return declarations;
1979
1980                 case T_IDENTIFIER:
1981                 case T___extension__:
1982                 DECLARATION_START
1983                         declaration = parse_parameter();
1984
1985                         parameter       = obstack_alloc(type_obst, sizeof(parameter[0]));
1986                         memset(parameter, 0, sizeof(parameter[0]));
1987                         parameter->type = declaration->type;
1988
1989                         if(last_parameter != NULL) {
1990                                 last_declaration->next = declaration;
1991                                 last_parameter->next   = parameter;
1992                         } else {
1993                                 type->parameters = parameter;
1994                                 declarations     = declaration;
1995                         }
1996                         last_parameter   = parameter;
1997                         last_declaration = declaration;
1998                         break;
1999
2000                 default:
2001                         return declarations;
2002                 }
2003                 if(token.type != ',')
2004                         return declarations;
2005                 next_token();
2006         }
2007 }
2008
2009 typedef enum {
2010         CONSTRUCT_INVALID,
2011         CONSTRUCT_POINTER,
2012         CONSTRUCT_FUNCTION,
2013         CONSTRUCT_ARRAY
2014 } construct_type_type_t;
2015
2016 typedef struct construct_type_t construct_type_t;
2017 struct construct_type_t {
2018         construct_type_type_t  type;
2019         construct_type_t      *next;
2020 };
2021
2022 typedef struct parsed_pointer_t parsed_pointer_t;
2023 struct parsed_pointer_t {
2024         construct_type_t  construct_type;
2025         type_qualifiers_t type_qualifiers;
2026 };
2027
2028 typedef struct construct_function_type_t construct_function_type_t;
2029 struct construct_function_type_t {
2030         construct_type_t  construct_type;
2031         type_t           *function_type;
2032 };
2033
2034 typedef struct parsed_array_t parsed_array_t;
2035 struct parsed_array_t {
2036         construct_type_t  construct_type;
2037         type_qualifiers_t type_qualifiers;
2038         bool              is_static;
2039         bool              is_variable;
2040         expression_t     *size;
2041 };
2042
2043 typedef struct construct_base_type_t construct_base_type_t;
2044 struct construct_base_type_t {
2045         construct_type_t  construct_type;
2046         type_t           *type;
2047 };
2048
2049 static construct_type_t *parse_pointer_declarator(void)
2050 {
2051         eat('*');
2052
2053         parsed_pointer_t *pointer = obstack_alloc(&temp_obst, sizeof(pointer[0]));
2054         memset(pointer, 0, sizeof(pointer[0]));
2055         pointer->construct_type.type = CONSTRUCT_POINTER;
2056         pointer->type_qualifiers     = parse_type_qualifiers();
2057
2058         return (construct_type_t*) pointer;
2059 }
2060
2061 static construct_type_t *parse_array_declarator(void)
2062 {
2063         eat('[');
2064
2065         parsed_array_t *array = obstack_alloc(&temp_obst, sizeof(array[0]));
2066         memset(array, 0, sizeof(array[0]));
2067         array->construct_type.type = CONSTRUCT_ARRAY;
2068
2069         if(token.type == T_static) {
2070                 array->is_static = true;
2071                 next_token();
2072         }
2073
2074         type_qualifiers_t type_qualifiers = parse_type_qualifiers();
2075         if(type_qualifiers != 0) {
2076                 if(token.type == T_static) {
2077                         array->is_static = true;
2078                         next_token();
2079                 }
2080         }
2081         array->type_qualifiers = type_qualifiers;
2082
2083         if(token.type == '*' && look_ahead(1)->type == ']') {
2084                 array->is_variable = true;
2085                 next_token();
2086         } else if(token.type != ']') {
2087                 array->size = parse_assignment_expression();
2088         }
2089
2090         expect(']');
2091
2092         return (construct_type_t*) array;
2093 }
2094
2095 static construct_type_t *parse_function_declarator(declaration_t *declaration)
2096 {
2097         eat('(');
2098
2099         type_t *type = allocate_type_zero(TYPE_FUNCTION);
2100
2101         declaration_t *parameters = parse_parameters(&type->function);
2102         if(declaration != NULL) {
2103                 declaration->context.declarations = parameters;
2104         }
2105
2106         construct_function_type_t *construct_function_type =
2107                 obstack_alloc(&temp_obst, sizeof(construct_function_type[0]));
2108         memset(construct_function_type, 0, sizeof(construct_function_type[0]));
2109         construct_function_type->construct_type.type = CONSTRUCT_FUNCTION;
2110         construct_function_type->function_type       = type;
2111
2112         expect(')');
2113
2114         return (construct_type_t*) construct_function_type;
2115 }
2116
2117 static construct_type_t *parse_inner_declarator(declaration_t *declaration,
2118                 bool may_be_abstract)
2119 {
2120         /* construct a single linked list of construct_type_t's which describe
2121          * how to construct the final declarator type */
2122         construct_type_t *first = NULL;
2123         construct_type_t *last  = NULL;
2124
2125         /* pointers */
2126         while(token.type == '*') {
2127                 construct_type_t *type = parse_pointer_declarator();
2128
2129                 if(last == NULL) {
2130                         first = type;
2131                         last  = type;
2132                 } else {
2133                         last->next = type;
2134                         last       = type;
2135                 }
2136         }
2137
2138         /* TODO: find out if this is correct */
2139         parse_attributes();
2140
2141         construct_type_t *inner_types = NULL;
2142
2143         switch(token.type) {
2144         case T_IDENTIFIER:
2145                 if(declaration == NULL) {
2146                         errorf(HERE, "no identifier expected in typename");
2147                 } else {
2148                         declaration->symbol          = token.v.symbol;
2149                         declaration->source_position = token.source_position;
2150                 }
2151                 next_token();
2152                 break;
2153         case '(':
2154                 next_token();
2155                 inner_types = parse_inner_declarator(declaration, may_be_abstract);
2156                 expect(')');
2157                 break;
2158         default:
2159                 if(may_be_abstract)
2160                         break;
2161                 parse_error_expected("while parsing declarator", T_IDENTIFIER, '(', 0);
2162                 /* avoid a loop in the outermost scope, because eat_statement doesn't
2163                  * eat '}' */
2164                 if(token.type == '}' && current_function == NULL) {
2165                         next_token();
2166                 } else {
2167                         eat_statement();
2168                 }
2169                 return NULL;
2170         }
2171
2172         construct_type_t *p = last;
2173
2174         while(true) {
2175                 construct_type_t *type;
2176                 switch(token.type) {
2177                 case '(':
2178                         type = parse_function_declarator(declaration);
2179                         break;
2180                 case '[':
2181                         type = parse_array_declarator();
2182                         break;
2183                 default:
2184                         goto declarator_finished;
2185                 }
2186
2187                 /* insert in the middle of the list (behind p) */
2188                 if(p != NULL) {
2189                         type->next = p->next;
2190                         p->next    = type;
2191                 } else {
2192                         type->next = first;
2193                         first      = type;
2194                 }
2195                 if(last == p) {
2196                         last = type;
2197                 }
2198         }
2199
2200 declarator_finished:
2201         parse_attributes();
2202
2203         /* append inner_types at the end of the list, we don't to set last anymore
2204          * as it's not needed anymore */
2205         if(last == NULL) {
2206                 assert(first == NULL);
2207                 first = inner_types;
2208         } else {
2209                 last->next = inner_types;
2210         }
2211
2212         return first;
2213 }
2214
2215 static type_t *construct_declarator_type(construct_type_t *construct_list,
2216                                          type_t *type)
2217 {
2218         construct_type_t *iter = construct_list;
2219         for( ; iter != NULL; iter = iter->next) {
2220                 switch(iter->type) {
2221                 case CONSTRUCT_INVALID:
2222                         panic("invalid type construction found");
2223                 case CONSTRUCT_FUNCTION: {
2224                         construct_function_type_t *construct_function_type
2225                                 = (construct_function_type_t*) iter;
2226
2227                         type_t *function_type = construct_function_type->function_type;
2228
2229                         function_type->function.return_type = type;
2230
2231                         type = function_type;
2232                         break;
2233                 }
2234
2235                 case CONSTRUCT_POINTER: {
2236                         parsed_pointer_t *parsed_pointer = (parsed_pointer_t*) iter;
2237                         type_t           *pointer_type   = allocate_type_zero(TYPE_POINTER);
2238                         pointer_type->pointer.points_to  = type;
2239                         pointer_type->base.qualifiers    = parsed_pointer->type_qualifiers;
2240
2241                         type = pointer_type;
2242                         break;
2243                 }
2244
2245                 case CONSTRUCT_ARRAY: {
2246                         parsed_array_t *parsed_array  = (parsed_array_t*) iter;
2247                         type_t         *array_type    = allocate_type_zero(TYPE_ARRAY);
2248
2249                         array_type->base.qualifiers    = parsed_array->type_qualifiers;
2250                         array_type->array.element_type = type;
2251                         array_type->array.is_static    = parsed_array->is_static;
2252                         array_type->array.is_variable  = parsed_array->is_variable;
2253                         array_type->array.size         = parsed_array->size;
2254
2255                         type = array_type;
2256                         break;
2257                 }
2258                 }
2259
2260                 type_t *hashed_type = typehash_insert(type);
2261                 if(hashed_type != type) {
2262                         /* the function type was constructed earlier freeing it here will
2263                          * destroy other types... */
2264                         if(iter->type != CONSTRUCT_FUNCTION) {
2265                                 free_type(type);
2266                         }
2267                         type = hashed_type;
2268                 }
2269         }
2270
2271         return type;
2272 }
2273
2274 static declaration_t *parse_declarator(
2275                 const declaration_specifiers_t *specifiers, bool may_be_abstract)
2276 {
2277         declaration_t *const declaration = allocate_declaration_zero();
2278         declaration->storage_class  = specifiers->storage_class;
2279         declaration->modifiers      = specifiers->decl_modifiers;
2280         declaration->is_inline      = specifiers->is_inline;
2281
2282         construct_type_t *construct_type
2283                 = parse_inner_declarator(declaration, may_be_abstract);
2284         type_t *const type = specifiers->type;
2285         declaration->type = construct_declarator_type(construct_type, type);
2286
2287         if(construct_type != NULL) {
2288                 obstack_free(&temp_obst, construct_type);
2289         }
2290
2291         return declaration;
2292 }
2293
2294 static type_t *parse_abstract_declarator(type_t *base_type)
2295 {
2296         construct_type_t *construct_type = parse_inner_declarator(NULL, 1);
2297
2298         type_t *result = construct_declarator_type(construct_type, base_type);
2299         if(construct_type != NULL) {
2300                 obstack_free(&temp_obst, construct_type);
2301         }
2302
2303         return result;
2304 }
2305
2306 static declaration_t *append_declaration(declaration_t* const declaration)
2307 {
2308         if (last_declaration != NULL) {
2309                 last_declaration->next = declaration;
2310         } else {
2311                 context->declarations = declaration;
2312         }
2313         last_declaration = declaration;
2314         return declaration;
2315 }
2316
2317 static declaration_t *internal_record_declaration(
2318         declaration_t *const declaration,
2319         const bool is_function_definition)
2320 {
2321         const symbol_t *const symbol  = declaration->symbol;
2322         const namespace_t     namespc = (namespace_t)declaration->namespc;
2323
2324         const type_t *const type = skip_typeref(declaration->type);
2325         if (is_type_function(type) && type->function.unspecified_parameters) {
2326                 warningf(declaration->source_position,
2327                          "function declaration '%#T' is not a prototype",
2328                          type, declaration->symbol);
2329         }
2330
2331         declaration_t *const previous_declaration = get_declaration(symbol, namespc);
2332         assert(declaration != previous_declaration);
2333         if (previous_declaration != NULL
2334                         && previous_declaration->parent_context == context) {
2335                 /* can happen for K&R style declarations */
2336                 if(previous_declaration->type == NULL) {
2337                         previous_declaration->type = declaration->type;
2338                 }
2339
2340                 const type_t *const prev_type = skip_typeref(previous_declaration->type);
2341                 if (!types_compatible(type, prev_type)) {
2342                         errorf(declaration->source_position,
2343                                 "declaration '%#T' is incompatible with previous declaration '%#T'",
2344                                 type, symbol, previous_declaration->type, symbol);
2345                         errorf(previous_declaration->source_position, "previous declaration of '%Y' was here", symbol);
2346                 } else {
2347                         unsigned old_storage_class = previous_declaration->storage_class;
2348                         unsigned new_storage_class = declaration->storage_class;
2349
2350                         /* pretend no storage class means extern for function declarations
2351                          * (except if the previous declaration is neither none nor extern) */
2352                         if (is_type_function(type)) {
2353                                 switch (old_storage_class) {
2354                                         case STORAGE_CLASS_NONE:
2355                                                 old_storage_class = STORAGE_CLASS_EXTERN;
2356
2357                                         case STORAGE_CLASS_EXTERN:
2358                                                 if (new_storage_class == STORAGE_CLASS_NONE && !is_function_definition) {
2359                                                         new_storage_class = STORAGE_CLASS_EXTERN;
2360                                                 }
2361                                                 break;
2362
2363                                         default: break;
2364                                 }
2365                         }
2366
2367                         if (old_storage_class == STORAGE_CLASS_EXTERN &&
2368                             new_storage_class == STORAGE_CLASS_EXTERN) {
2369 warn_redundant_declaration:
2370                                         warningf(declaration->source_position, "redundant declaration for '%Y'", symbol);
2371                                         warningf(previous_declaration->source_position, "previous declaration of '%Y' was here", symbol);
2372                         } else if (current_function == NULL) {
2373                                 if (old_storage_class != STORAGE_CLASS_STATIC &&
2374                                     new_storage_class == STORAGE_CLASS_STATIC) {
2375                                         errorf(declaration->source_position, "static declaration of '%Y' follows non-static declaration", symbol);
2376                                         errorf(previous_declaration->source_position, "previous declaration of '%Y' was here", symbol);
2377                                 } else {
2378                                         if (old_storage_class != STORAGE_CLASS_EXTERN) {
2379                                                 goto warn_redundant_declaration;
2380                                         }
2381                                         if (new_storage_class == STORAGE_CLASS_NONE) {
2382                                                 previous_declaration->storage_class = STORAGE_CLASS_NONE;
2383                                         }
2384                                 }
2385                         } else {
2386                                 if (old_storage_class == new_storage_class) {
2387                                         errorf(declaration->source_position, "redeclaration of '%Y'", symbol);
2388                                 } else {
2389                                         errorf(declaration->source_position, "redeclaration of '%Y' with different linkage", symbol);
2390                                 }
2391                                 errorf(previous_declaration->source_position, "previous declaration of '%Y' was here", symbol);
2392                         }
2393                 }
2394                 return previous_declaration;
2395         }
2396
2397         assert(declaration->parent_context == NULL);
2398         assert(declaration->symbol != NULL);
2399         assert(context != NULL);
2400
2401         declaration->parent_context = context;
2402
2403         environment_push(declaration);
2404         return append_declaration(declaration);
2405 }
2406
2407 static declaration_t *record_declaration(declaration_t *declaration)
2408 {
2409         return internal_record_declaration(declaration, false);
2410 }
2411
2412 static declaration_t *record_function_definition(declaration_t *const declaration)
2413 {
2414         return internal_record_declaration(declaration, true);
2415 }
2416
2417 static void parser_error_multiple_definition(declaration_t *declaration,
2418                 const source_position_t source_position)
2419 {
2420         errorf(source_position, "multiple definition of symbol '%Y'",
2421                declaration->symbol);
2422         errorf(declaration->source_position,
2423                "this is the location of the previous definition.");
2424 }
2425
2426 static bool is_declaration_specifier(const token_t *token,
2427                                      bool only_type_specifiers)
2428 {
2429         switch(token->type) {
2430                 TYPE_SPECIFIERS
2431                         return true;
2432                 case T_IDENTIFIER:
2433                         return is_typedef_symbol(token->v.symbol);
2434
2435                 case T___extension__:
2436                 STORAGE_CLASSES
2437                 TYPE_QUALIFIERS
2438                         return !only_type_specifiers;
2439
2440                 default:
2441                         return false;
2442         }
2443 }
2444
2445 static void parse_init_declarator_rest(declaration_t *declaration)
2446 {
2447         eat('=');
2448
2449         type_t *orig_type = declaration->type;
2450         type_t *type      = NULL;
2451         if(orig_type != NULL)
2452                 type = skip_typeref(orig_type);
2453
2454         if(declaration->init.initializer != NULL) {
2455                 parser_error_multiple_definition(declaration, token.source_position);
2456         }
2457
2458         initializer_t *initializer = parse_initializer(type);
2459
2460         /* § 6.7.5 (22)  array initializers for arrays with unknown size determine
2461          * the array type size */
2462         if(type != NULL && is_type_array(type) && initializer != NULL) {
2463                 array_type_t *array_type = &type->array;
2464
2465                 if(array_type->size == NULL) {
2466                         expression_t *cnst = allocate_expression_zero(EXPR_CONST);
2467
2468                         cnst->base.datatype = type_size_t;
2469
2470                         switch (initializer->kind) {
2471                                 case INITIALIZER_LIST: {
2472                                         initializer_list_t *const list = &initializer->list;
2473                                         cnst->conste.v.int_value = list->len;
2474                                         break;
2475                                 }
2476
2477                                 case INITIALIZER_STRING: {
2478                                         initializer_string_t *const string = &initializer->string;
2479                                         cnst->conste.v.int_value = string->string.size;
2480                                         break;
2481                                 }
2482
2483                                 case INITIALIZER_WIDE_STRING: {
2484                                         initializer_wide_string_t *const string = &initializer->wide_string;
2485                                         cnst->conste.v.int_value = string->string.size;
2486                                         break;
2487                                 }
2488
2489                                 default:
2490                                         panic("invalid initializer type");
2491                         }
2492
2493                         array_type->size = cnst;
2494                 }
2495         }
2496
2497         if(type != NULL && is_type_function(type)) {
2498                 errorf(declaration->source_position,
2499                        "initializers not allowed for function types at declator '%Y' (type '%T')",
2500                        declaration->symbol, orig_type);
2501         } else {
2502                 declaration->init.initializer = initializer;
2503         }
2504 }
2505
2506 /* parse rest of a declaration without any declarator */
2507 static void parse_anonymous_declaration_rest(
2508                 const declaration_specifiers_t *specifiers,
2509                 parsed_declaration_func finished_declaration)
2510 {
2511         eat(';');
2512
2513         declaration_t *const declaration = allocate_declaration_zero();
2514         declaration->type            = specifiers->type;
2515         declaration->storage_class   = specifiers->storage_class;
2516         declaration->source_position = specifiers->source_position;
2517
2518         if (declaration->storage_class != STORAGE_CLASS_NONE) {
2519                 warningf(declaration->source_position, "useless storage class in empty declaration");
2520         }
2521
2522         type_t *type = declaration->type;
2523         switch (type->kind) {
2524                 case TYPE_COMPOUND_STRUCT:
2525                 case TYPE_COMPOUND_UNION: {
2526                         const compound_type_t *compound_type = &type->compound;
2527                         if (compound_type->declaration->symbol == NULL) {
2528                                 warningf(declaration->source_position, "unnamed struct/union that defines no instances");
2529                         }
2530                         break;
2531                 }
2532
2533                 case TYPE_ENUM:
2534                         break;
2535
2536                 default:
2537                         warningf(declaration->source_position, "empty declaration");
2538                         break;
2539         }
2540
2541         finished_declaration(declaration);
2542 }
2543
2544 static void parse_declaration_rest(declaration_t *ndeclaration,
2545                 const declaration_specifiers_t *specifiers,
2546                 parsed_declaration_func finished_declaration)
2547 {
2548         while(true) {
2549                 declaration_t *declaration = finished_declaration(ndeclaration);
2550
2551                 type_t *orig_type = declaration->type;
2552                 type_t *type      = skip_typeref(orig_type);
2553
2554                 if(type->kind != TYPE_FUNCTION && declaration->is_inline) {
2555                         warningf(declaration->source_position,
2556                                  "variable '%Y' declared 'inline'\n", declaration->symbol);
2557                 }
2558
2559                 if(token.type == '=') {
2560                         parse_init_declarator_rest(declaration);
2561                 }
2562
2563                 if(token.type != ',')
2564                         break;
2565                 eat(',');
2566
2567                 ndeclaration = parse_declarator(specifiers, /*may_be_abstract=*/false);
2568         }
2569         expect_void(';');
2570 }
2571
2572 static declaration_t *finished_kr_declaration(declaration_t *declaration)
2573 {
2574         symbol_t *symbol  = declaration->symbol;
2575         if(symbol == NULL) {
2576                 errorf(HERE, "anonymous declaration not valid as function parameter");
2577                 return declaration;
2578         }
2579         namespace_t namespc = (namespace_t) declaration->namespc;
2580         if(namespc != NAMESPACE_NORMAL) {
2581                 return record_declaration(declaration);
2582         }
2583
2584         declaration_t *previous_declaration = get_declaration(symbol, namespc);
2585         if(previous_declaration == NULL ||
2586                         previous_declaration->parent_context != context) {
2587                 errorf(HERE, "expected declaration of a function parameter, found '%Y'",
2588                        symbol);
2589                 return declaration;
2590         }
2591
2592         if(previous_declaration->type == NULL) {
2593                 previous_declaration->type           = declaration->type;
2594                 previous_declaration->storage_class  = declaration->storage_class;
2595                 previous_declaration->parent_context = context;
2596                 return previous_declaration;
2597         } else {
2598                 return record_declaration(declaration);
2599         }
2600 }
2601
2602 static void parse_declaration(parsed_declaration_func finished_declaration)
2603 {
2604         declaration_specifiers_t specifiers;
2605         memset(&specifiers, 0, sizeof(specifiers));
2606         parse_declaration_specifiers(&specifiers);
2607
2608         if(token.type == ';') {
2609                 parse_anonymous_declaration_rest(&specifiers, finished_declaration);
2610         } else {
2611                 declaration_t *declaration = parse_declarator(&specifiers, /*may_be_abstract=*/false);
2612                 parse_declaration_rest(declaration, &specifiers, finished_declaration);
2613         }
2614 }
2615
2616 static void parse_kr_declaration_list(declaration_t *declaration)
2617 {
2618         type_t *type = skip_typeref(declaration->type);
2619         if(!is_type_function(type))
2620                 return;
2621
2622         if(!type->function.kr_style_parameters)
2623                 return;
2624
2625         /* push function parameters */
2626         int         top          = environment_top();
2627         context_t  *last_context = context;
2628         set_context(&declaration->context);
2629
2630         declaration_t *parameter = declaration->context.declarations;
2631         for( ; parameter != NULL; parameter = parameter->next) {
2632                 assert(parameter->parent_context == NULL);
2633                 parameter->parent_context = context;
2634                 environment_push(parameter);
2635         }
2636
2637         /* parse declaration list */
2638         while(is_declaration_specifier(&token, false)) {
2639                 parse_declaration(finished_kr_declaration);
2640         }
2641
2642         /* pop function parameters */
2643         assert(context == &declaration->context);
2644         set_context(last_context);
2645         environment_pop_to(top);
2646
2647         /* update function type */
2648         type_t *new_type = duplicate_type(type);
2649         new_type->function.kr_style_parameters = false;
2650
2651         function_parameter_t *parameters     = NULL;
2652         function_parameter_t *last_parameter = NULL;
2653
2654         declaration_t *parameter_declaration = declaration->context.declarations;
2655         for( ; parameter_declaration != NULL;
2656                         parameter_declaration = parameter_declaration->next) {
2657                 type_t *parameter_type = parameter_declaration->type;
2658                 if(parameter_type == NULL) {
2659                         if (strict_mode) {
2660                                 errorf(HERE, "no type specified for function parameter '%Y'",
2661                                        parameter_declaration->symbol);
2662                         } else {
2663                                 warningf(HERE, "no type specified for function parameter '%Y', using int",
2664                                          parameter_declaration->symbol);
2665                                 parameter_type              = type_int;
2666                                 parameter_declaration->type = parameter_type;
2667                         }
2668                 }
2669
2670                 semantic_parameter(parameter_declaration);
2671                 parameter_type = parameter_declaration->type;
2672
2673                 function_parameter_t *function_parameter
2674                         = obstack_alloc(type_obst, sizeof(function_parameter[0]));
2675                 memset(function_parameter, 0, sizeof(function_parameter[0]));
2676
2677                 function_parameter->type = parameter_type;
2678                 if(last_parameter != NULL) {
2679                         last_parameter->next = function_parameter;
2680                 } else {
2681                         parameters = function_parameter;
2682                 }
2683                 last_parameter = function_parameter;
2684         }
2685         new_type->function.parameters = parameters;
2686
2687         type = typehash_insert(new_type);
2688         if(type != new_type) {
2689                 obstack_free(type_obst, new_type);
2690         }
2691
2692         declaration->type = type;
2693 }
2694
2695 /**
2696  * Check if all labels are defined in the current function.
2697  */
2698 static void check_for_missing_labels(void)
2699 {
2700         bool first_err = true;
2701         for (const goto_statement_t *goto_statement = goto_first;
2702              goto_statement != NULL;
2703              goto_statement = goto_statement->next) {
2704                  const declaration_t *label = goto_statement->label;
2705
2706                  if (label->source_position.input_name == NULL) {
2707                          if (first_err) {
2708                                  first_err = false;
2709                                  diagnosticf("%s: In function '%Y':\n",
2710                                          current_function->source_position.input_name,
2711                                          current_function->symbol);
2712                          }
2713                          errorf(goto_statement->statement.source_position,
2714                                  "label '%Y' used but not defined", label->symbol);
2715                  }
2716         }
2717         goto_first = goto_last = NULL;
2718 }
2719
2720 static void parse_external_declaration(void)
2721 {
2722         /* function-definitions and declarations both start with declaration
2723          * specifiers */
2724         declaration_specifiers_t specifiers;
2725         memset(&specifiers, 0, sizeof(specifiers));
2726         parse_declaration_specifiers(&specifiers);
2727
2728         /* must be a declaration */
2729         if(token.type == ';') {
2730                 parse_anonymous_declaration_rest(&specifiers, append_declaration);
2731                 return;
2732         }
2733
2734         /* declarator is common to both function-definitions and declarations */
2735         declaration_t *ndeclaration = parse_declarator(&specifiers, /*may_be_abstract=*/false);
2736
2737         /* must be a declaration */
2738         if(token.type == ',' || token.type == '=' || token.type == ';') {
2739                 parse_declaration_rest(ndeclaration, &specifiers, record_declaration);
2740                 return;
2741         }
2742
2743         /* must be a function definition */
2744         parse_kr_declaration_list(ndeclaration);
2745
2746         if(token.type != '{') {
2747                 parse_error_expected("while parsing function definition", '{', 0);
2748                 eat_statement();
2749                 return;
2750         }
2751
2752         type_t *type = ndeclaration->type;
2753         if(type == NULL) {
2754                 eat_block();
2755                 return;
2756         }
2757
2758         /* note that we don't skip typerefs: the standard doesn't allow them here
2759          * (so we can't use is_type_function here) */
2760         if(type->kind != TYPE_FUNCTION) {
2761                 errorf(HERE, "declarator '%#T' has a body but is not a function type",
2762                        type, ndeclaration->symbol);
2763                 eat_block();
2764                 return;
2765         }
2766
2767         /* § 6.7.5.3 (14) a function definition with () means no
2768          * parameters (and not unspecified parameters) */
2769         if(type->function.unspecified_parameters) {
2770                 type_t *duplicate = duplicate_type(type);
2771                 duplicate->function.unspecified_parameters = false;
2772
2773                 type = typehash_insert(duplicate);
2774                 if(type != duplicate) {
2775                         obstack_free(type_obst, duplicate);
2776                 }
2777                 ndeclaration->type = type;
2778         }
2779
2780         declaration_t *const declaration = record_function_definition(ndeclaration);
2781         if(ndeclaration != declaration) {
2782                 declaration->context = ndeclaration->context;
2783         }
2784         type = skip_typeref(declaration->type);
2785
2786         /* push function parameters and switch context */
2787         int         top          = environment_top();
2788         context_t  *last_context = context;
2789         set_context(&declaration->context);
2790
2791         declaration_t *parameter = declaration->context.declarations;
2792         for( ; parameter != NULL; parameter = parameter->next) {
2793                 if(parameter->parent_context == &ndeclaration->context) {
2794                         parameter->parent_context = context;
2795                 }
2796                 assert(parameter->parent_context == NULL
2797                                 || parameter->parent_context == context);
2798                 parameter->parent_context = context;
2799                 environment_push(parameter);
2800         }
2801
2802         if(declaration->init.statement != NULL) {
2803                 parser_error_multiple_definition(declaration, token.source_position);
2804                 eat_block();
2805                 goto end_of_parse_external_declaration;
2806         } else {
2807                 /* parse function body */
2808                 int            label_stack_top      = label_top();
2809                 declaration_t *old_current_function = current_function;
2810                 current_function                    = declaration;
2811
2812                 declaration->init.statement = parse_compound_statement();
2813                 check_for_missing_labels();
2814
2815                 assert(current_function == declaration);
2816                 current_function = old_current_function;
2817                 label_pop_to(label_stack_top);
2818         }
2819
2820 end_of_parse_external_declaration:
2821         assert(context == &declaration->context);
2822         set_context(last_context);
2823         environment_pop_to(top);
2824 }
2825
2826 static type_t *make_bitfield_type(type_t *base, expression_t *size)
2827 {
2828         type_t *type        = allocate_type_zero(TYPE_BITFIELD);
2829         type->bitfield.base = base;
2830         type->bitfield.size = size;
2831
2832         return type;
2833 }
2834
2835 static void parse_struct_declarators(const declaration_specifiers_t *specifiers)
2836 {
2837         /* TODO: check constraints for struct declarations (in specifiers) */
2838         while(1) {
2839                 declaration_t *declaration;
2840
2841                 if(token.type == ':') {
2842                         next_token();
2843
2844                         type_t *base_type = specifiers->type;
2845                         expression_t *size = parse_constant_expression();
2846
2847                         type_t *type = make_bitfield_type(base_type, size);
2848
2849                         declaration = allocate_declaration_zero();
2850                         declaration->namespc         = NAMESPACE_NORMAL;
2851                         declaration->storage_class   = STORAGE_CLASS_NONE;
2852                         declaration->source_position = token.source_position;
2853                         declaration->modifiers       = specifiers->decl_modifiers;
2854                         declaration->type            = type;
2855                 } else {
2856                         declaration = parse_declarator(specifiers,/*may_be_abstract=*/true);
2857
2858                         if(token.type == ':') {
2859                                 next_token();
2860                                 expression_t *size = parse_constant_expression();
2861
2862                                 type_t *type = make_bitfield_type(declaration->type, size);
2863                                 declaration->type = type;
2864                         }
2865                 }
2866                 record_declaration(declaration);
2867
2868                 if(token.type != ',')
2869                         break;
2870                 next_token();
2871         }
2872         expect_void(';');
2873 }
2874
2875 static void parse_compound_type_entries(void)
2876 {
2877         eat('{');
2878
2879         while(token.type != '}' && token.type != T_EOF) {
2880                 declaration_specifiers_t specifiers;
2881                 memset(&specifiers, 0, sizeof(specifiers));
2882                 parse_declaration_specifiers(&specifiers);
2883
2884                 parse_struct_declarators(&specifiers);
2885         }
2886         if(token.type == T_EOF) {
2887                 errorf(HERE, "EOF while parsing struct");
2888         }
2889         next_token();
2890 }
2891
2892 static type_t *parse_typename(void)
2893 {
2894         declaration_specifiers_t specifiers;
2895         memset(&specifiers, 0, sizeof(specifiers));
2896         parse_declaration_specifiers(&specifiers);
2897         if(specifiers.storage_class != STORAGE_CLASS_NONE) {
2898                 /* TODO: improve error message, user does probably not know what a
2899                  * storage class is...
2900                  */
2901                 errorf(HERE, "typename may not have a storage class");
2902         }
2903
2904         type_t *result = parse_abstract_declarator(specifiers.type);
2905
2906         return result;
2907 }
2908
2909
2910
2911
2912 typedef expression_t* (*parse_expression_function) (unsigned precedence);
2913 typedef expression_t* (*parse_expression_infix_function) (unsigned precedence,
2914                                                           expression_t *left);
2915
2916 typedef struct expression_parser_function_t expression_parser_function_t;
2917 struct expression_parser_function_t {
2918         unsigned                         precedence;
2919         parse_expression_function        parser;
2920         unsigned                         infix_precedence;
2921         parse_expression_infix_function  infix_parser;
2922 };
2923
2924 expression_parser_function_t expression_parsers[T_LAST_TOKEN];
2925
2926 /**
2927  * Creates a new invalid expression.
2928  */
2929 static expression_t *create_invalid_expression(void)
2930 {
2931         expression_t *expression         = allocate_expression_zero(EXPR_INVALID);
2932         expression->base.source_position = token.source_position;
2933         return expression;
2934 }
2935
2936 /**
2937  * Prints an error message if an expression was expected but not read
2938  */
2939 static expression_t *expected_expression_error(void)
2940 {
2941         /* skip the error message if the error token was read */
2942         if (token.type != T_ERROR) {
2943                 errorf(HERE, "expected expression, got token '%K'", &token);
2944         }
2945         next_token();
2946
2947         return create_invalid_expression();
2948 }
2949
2950 /**
2951  * Parse a string constant.
2952  */
2953 static expression_t *parse_string_const(void)
2954 {
2955         expression_t *cnst  = allocate_expression_zero(EXPR_STRING_LITERAL);
2956         cnst->base.datatype = type_string;
2957         cnst->string.value  = parse_string_literals();
2958
2959         return cnst;
2960 }
2961
2962 /**
2963  * Parse a wide string constant.
2964  */
2965 static expression_t *parse_wide_string_const(void)
2966 {
2967         expression_t *const cnst = allocate_expression_zero(EXPR_WIDE_STRING_LITERAL);
2968         cnst->base.datatype      = type_wchar_t_ptr;
2969         cnst->wide_string.value  = token.v.wide_string; /* TODO concatenate */
2970         next_token();
2971         return cnst;
2972 }
2973
2974 /**
2975  * Parse an integer constant.
2976  */
2977 static expression_t *parse_int_const(void)
2978 {
2979         expression_t *cnst       = allocate_expression_zero(EXPR_CONST);
2980         cnst->base.datatype      = token.datatype;
2981         cnst->conste.v.int_value = token.v.intvalue;
2982
2983         next_token();
2984
2985         return cnst;
2986 }
2987
2988 /**
2989  * Parse a float constant.
2990  */
2991 static expression_t *parse_float_const(void)
2992 {
2993         expression_t *cnst         = allocate_expression_zero(EXPR_CONST);
2994         cnst->base.datatype        = token.datatype;
2995         cnst->conste.v.float_value = token.v.floatvalue;
2996
2997         next_token();
2998
2999         return cnst;
3000 }
3001
3002 static declaration_t *create_implicit_function(symbol_t *symbol,
3003                 const source_position_t source_position)
3004 {
3005         type_t *ntype                          = allocate_type_zero(TYPE_FUNCTION);
3006         ntype->function.return_type            = type_int;
3007         ntype->function.unspecified_parameters = true;
3008
3009         type_t *type = typehash_insert(ntype);
3010         if(type != ntype) {
3011                 free_type(ntype);
3012         }
3013
3014         declaration_t *const declaration = allocate_declaration_zero();
3015         declaration->storage_class   = STORAGE_CLASS_EXTERN;
3016         declaration->type            = type;
3017         declaration->symbol          = symbol;
3018         declaration->source_position = source_position;
3019         declaration->parent_context  = global_context;
3020
3021         context_t *old_context = context;
3022         set_context(global_context);
3023
3024         environment_push(declaration);
3025         /* prepend the declaration to the global declarations list */
3026         declaration->next     = context->declarations;
3027         context->declarations = declaration;
3028
3029         assert(context == global_context);
3030         set_context(old_context);
3031
3032         return declaration;
3033 }
3034
3035 /**
3036  * Creates a return_type (func)(argument_type) function type if not
3037  * already exists.
3038  *
3039  * @param return_type    the return type
3040  * @param argument_type  the argument type
3041  */
3042 static type_t *make_function_1_type(type_t *return_type, type_t *argument_type)
3043 {
3044         function_parameter_t *parameter
3045                 = obstack_alloc(type_obst, sizeof(parameter[0]));
3046         memset(parameter, 0, sizeof(parameter[0]));
3047         parameter->type = argument_type;
3048
3049         type_t *type               = allocate_type_zero(TYPE_FUNCTION);
3050         type->function.return_type = return_type;
3051         type->function.parameters  = parameter;
3052
3053         type_t *result = typehash_insert(type);
3054         if(result != type) {
3055                 free_type(type);
3056         }
3057
3058         return result;
3059 }
3060
3061 /**
3062  * Creates a function type for some function like builtins.
3063  *
3064  * @param symbol   the symbol describing the builtin
3065  */
3066 static type_t *get_builtin_symbol_type(symbol_t *symbol)
3067 {
3068         switch(symbol->ID) {
3069         case T___builtin_alloca:
3070                 return make_function_1_type(type_void_ptr, type_size_t);
3071         case T___builtin_nan:
3072                 return make_function_1_type(type_double, type_string);
3073         case T___builtin_nanf:
3074                 return make_function_1_type(type_float, type_string);
3075         case T___builtin_nand:
3076                 return make_function_1_type(type_long_double, type_string);
3077         case T___builtin_va_end:
3078                 return make_function_1_type(type_void, type_valist);
3079         default:
3080                 panic("not implemented builtin symbol found");
3081         }
3082 }
3083
3084 /**
3085  * Performs automatic type cast as described in § 6.3.2.1.
3086  *
3087  * @param orig_type  the original type
3088  */
3089 static type_t *automatic_type_conversion(type_t *orig_type)
3090 {
3091         if(orig_type == NULL)
3092                 return NULL;
3093
3094         type_t *type = skip_typeref(orig_type);
3095         if(is_type_array(type)) {
3096                 array_type_t *array_type   = &type->array;
3097                 type_t       *element_type = array_type->element_type;
3098                 unsigned      qualifiers   = array_type->type.qualifiers;
3099
3100                 return make_pointer_type(element_type, qualifiers);
3101         }
3102
3103         if(is_type_function(type)) {
3104                 return make_pointer_type(orig_type, TYPE_QUALIFIER_NONE);
3105         }
3106
3107         return orig_type;
3108 }
3109
3110 /**
3111  * reverts the automatic casts of array to pointer types and function
3112  * to function-pointer types as defined § 6.3.2.1
3113  */
3114 type_t *revert_automatic_type_conversion(const expression_t *expression)
3115 {
3116         if(expression->base.datatype == NULL)
3117                 return NULL;
3118
3119         switch(expression->kind) {
3120         case EXPR_REFERENCE: {
3121                 const reference_expression_t *ref = &expression->reference;
3122                 return ref->declaration->type;
3123         }
3124         case EXPR_SELECT: {
3125                 const select_expression_t *select = &expression->select;
3126                 return select->compound_entry->type;
3127         }
3128         case EXPR_UNARY_DEREFERENCE: {
3129                 expression_t   *value        = expression->unary.value;
3130                 type_t         *type         = skip_typeref(value->base.datatype);
3131                 pointer_type_t *pointer_type = &type->pointer;
3132
3133                 return pointer_type->points_to;
3134         }
3135         case EXPR_BUILTIN_SYMBOL: {
3136                 const builtin_symbol_expression_t *builtin
3137                         = &expression->builtin_symbol;
3138                 return get_builtin_symbol_type(builtin->symbol);
3139         }
3140         case EXPR_ARRAY_ACCESS: {
3141                 const array_access_expression_t *array_access
3142                         = &expression->array_access;
3143                 const expression_t *array_ref = array_access->array_ref;
3144                 type_t *type_left  = skip_typeref(array_ref->base.datatype);
3145                 assert(is_type_pointer(type_left));
3146                 pointer_type_t *pointer_type = &type_left->pointer;
3147                 return pointer_type->points_to;
3148         }
3149
3150         default:
3151                 break;
3152         }
3153
3154         return expression->base.datatype;
3155 }
3156
3157 static expression_t *parse_reference(void)
3158 {
3159         expression_t *expression = allocate_expression_zero(EXPR_REFERENCE);
3160
3161         reference_expression_t *ref = &expression->reference;
3162         ref->symbol = token.v.symbol;
3163
3164         declaration_t *declaration = get_declaration(ref->symbol, NAMESPACE_NORMAL);
3165
3166         source_position_t source_position = token.source_position;
3167         next_token();
3168
3169         if(declaration == NULL) {
3170                 if (! strict_mode && token.type == '(') {
3171                         /* an implicitly defined function */
3172                         warningf(HERE, "implicit declaration of function '%Y'",
3173                                  ref->symbol);
3174
3175                         declaration = create_implicit_function(ref->symbol,
3176                                                                source_position);
3177                 } else {
3178                         errorf(HERE, "unknown symbol '%Y' found.", ref->symbol);
3179                         return expression;
3180                 }
3181         }
3182
3183         type_t *type         = declaration->type;
3184
3185         /* we always do the auto-type conversions; the & and sizeof parser contains
3186          * code to revert this! */
3187         type = automatic_type_conversion(type);
3188
3189         ref->declaration         = declaration;
3190         ref->expression.datatype = type;
3191
3192         return expression;
3193 }
3194
3195 static void check_cast_allowed(expression_t *expression, type_t *dest_type)
3196 {
3197         (void) expression;
3198         (void) dest_type;
3199         /* TODO check if explicit cast is allowed and issue warnings/errors */
3200 }
3201
3202 static expression_t *parse_cast(void)
3203 {
3204         expression_t *cast = allocate_expression_zero(EXPR_UNARY_CAST);
3205
3206         cast->base.source_position = token.source_position;
3207
3208         type_t *type  = parse_typename();
3209
3210         expect(')');
3211         expression_t *value = parse_sub_expression(20);
3212
3213         check_cast_allowed(value, type);
3214
3215         cast->base.datatype = type;
3216         cast->unary.value   = value;
3217
3218         return cast;
3219 }
3220
3221 static expression_t *parse_statement_expression(void)
3222 {
3223         expression_t *expression = allocate_expression_zero(EXPR_STATEMENT);
3224
3225         statement_t *statement          = parse_compound_statement();
3226         expression->statement.statement = statement;
3227         if(statement == NULL) {
3228                 expect(')');
3229                 return NULL;
3230         }
3231
3232         assert(statement->kind == STATEMENT_COMPOUND);
3233         compound_statement_t *compound_statement = &statement->compound;
3234
3235         /* find last statement and use it's type */
3236         const statement_t *last_statement = NULL;
3237         const statement_t *iter           = compound_statement->statements;
3238         for( ; iter != NULL; iter = iter->base.next) {
3239                 last_statement = iter;
3240         }
3241
3242         if(last_statement->kind == STATEMENT_EXPRESSION) {
3243                 const expression_statement_t *expression_statement
3244                         = &last_statement->expression;
3245                 expression->base.datatype
3246                         = expression_statement->expression->base.datatype;
3247         } else {
3248                 expression->base.datatype = type_void;
3249         }
3250
3251         expect(')');
3252
3253         return expression;
3254 }
3255
3256 static expression_t *parse_brace_expression(void)
3257 {
3258         eat('(');
3259
3260         switch(token.type) {
3261         case '{':
3262                 /* gcc extension: a statement expression */
3263                 return parse_statement_expression();
3264
3265         TYPE_QUALIFIERS
3266         TYPE_SPECIFIERS
3267                 return parse_cast();
3268         case T_IDENTIFIER:
3269                 if(is_typedef_symbol(token.v.symbol)) {
3270                         return parse_cast();
3271                 }
3272         }
3273
3274         expression_t *result = parse_expression();
3275         expect(')');
3276
3277         return result;
3278 }
3279
3280 static expression_t *parse_function_keyword(void)
3281 {
3282         next_token();
3283         /* TODO */
3284
3285         if (current_function == NULL) {
3286                 errorf(HERE, "'__func__' used outside of a function");
3287         }
3288
3289         string_literal_expression_t *expression
3290                 = allocate_ast_zero(sizeof(expression[0]));
3291
3292         expression->expression.kind     = EXPR_FUNCTION;
3293         expression->expression.datatype = type_string;
3294
3295         return (expression_t*) expression;
3296 }
3297
3298 static expression_t *parse_pretty_function_keyword(void)
3299 {
3300         eat(T___PRETTY_FUNCTION__);
3301         /* TODO */
3302
3303         if (current_function == NULL) {
3304                 errorf(HERE, "'__PRETTY_FUNCTION__' used outside of a function");
3305         }
3306
3307         string_literal_expression_t *expression
3308                 = allocate_ast_zero(sizeof(expression[0]));
3309
3310         expression->expression.kind     = EXPR_PRETTY_FUNCTION;
3311         expression->expression.datatype = type_string;
3312
3313         return (expression_t*) expression;
3314 }
3315
3316 static designator_t *parse_designator(void)
3317 {
3318         designator_t *result = allocate_ast_zero(sizeof(result[0]));
3319
3320         if(token.type != T_IDENTIFIER) {
3321                 parse_error_expected("while parsing member designator",
3322                                      T_IDENTIFIER, 0);
3323                 eat_paren();
3324                 return NULL;
3325         }
3326         result->symbol = token.v.symbol;
3327         next_token();
3328
3329         designator_t *last_designator = result;
3330         while(true) {
3331                 if(token.type == '.') {
3332                         next_token();
3333                         if(token.type != T_IDENTIFIER) {
3334                                 parse_error_expected("while parsing member designator",
3335                                                      T_IDENTIFIER, 0);
3336                                 eat_paren();
3337                                 return NULL;
3338                         }
3339                         designator_t *designator = allocate_ast_zero(sizeof(result[0]));
3340                         designator->symbol       = token.v.symbol;
3341                         next_token();
3342
3343                         last_designator->next = designator;
3344                         last_designator       = designator;
3345                         continue;
3346                 }
3347                 if(token.type == '[') {
3348                         next_token();
3349                         designator_t *designator = allocate_ast_zero(sizeof(result[0]));
3350                         designator->array_access = parse_expression();
3351                         if(designator->array_access == NULL) {
3352                                 eat_paren();
3353                                 return NULL;
3354                         }
3355                         expect(']');
3356
3357                         last_designator->next = designator;
3358                         last_designator       = designator;
3359                         continue;
3360                 }
3361                 break;
3362         }
3363
3364         return result;
3365 }
3366
3367 static expression_t *parse_offsetof(void)
3368 {
3369         eat(T___builtin_offsetof);
3370
3371         expression_t *expression  = allocate_expression_zero(EXPR_OFFSETOF);
3372         expression->base.datatype = type_size_t;
3373
3374         expect('(');
3375         expression->offsetofe.type = parse_typename();
3376         expect(',');
3377         expression->offsetofe.designator = parse_designator();
3378         expect(')');
3379
3380         return expression;
3381 }
3382
3383 static expression_t *parse_va_start(void)
3384 {
3385         eat(T___builtin_va_start);
3386
3387         expression_t *expression = allocate_expression_zero(EXPR_VA_START);
3388
3389         expect('(');
3390         expression->va_starte.ap = parse_assignment_expression();
3391         expect(',');
3392         expression_t *const expr = parse_assignment_expression();
3393         if (expr->kind == EXPR_REFERENCE) {
3394                 declaration_t *const decl = expr->reference.declaration;
3395                 if (decl->parent_context == &current_function->context &&
3396                     decl->next == NULL) {
3397                         expression->va_starte.parameter = decl;
3398                         expect(')');
3399                         return expression;
3400                 }
3401         }
3402         errorf(expr->base.source_position, "second argument of 'va_start' must be last parameter of the current function");
3403
3404         return create_invalid_expression();
3405 }
3406
3407 static expression_t *parse_va_arg(void)
3408 {
3409         eat(T___builtin_va_arg);
3410
3411         expression_t *expression = allocate_expression_zero(EXPR_VA_ARG);
3412
3413         expect('(');
3414         expression->va_arge.ap = parse_assignment_expression();
3415         expect(',');
3416         expression->base.datatype = parse_typename();
3417         expect(')');
3418
3419         return expression;
3420 }
3421
3422 static expression_t *parse_builtin_symbol(void)
3423 {
3424         expression_t *expression = allocate_expression_zero(EXPR_BUILTIN_SYMBOL);
3425
3426         symbol_t *symbol = token.v.symbol;
3427
3428         expression->builtin_symbol.symbol = symbol;
3429         next_token();
3430
3431         type_t *type = get_builtin_symbol_type(symbol);
3432         type = automatic_type_conversion(type);
3433
3434         expression->base.datatype = type;
3435         return expression;
3436 }
3437
3438 static expression_t *parse_builtin_constant(void)
3439 {
3440         eat(T___builtin_constant_p);
3441
3442         expression_t *expression = allocate_expression_zero(EXPR_BUILTIN_CONSTANT_P);
3443
3444         expect('(');
3445         expression->builtin_constant.value = parse_assignment_expression();
3446         expect(')');
3447         expression->base.datatype = type_int;
3448
3449         return expression;
3450 }
3451
3452 static expression_t *parse_builtin_prefetch(void)
3453 {
3454         eat(T___builtin_prefetch);
3455
3456         expression_t *expression = allocate_expression_zero(EXPR_BUILTIN_PREFETCH);
3457
3458         expect('(');
3459         expression->builtin_prefetch.adr = parse_assignment_expression();
3460         if (token.type == ',') {
3461                 next_token();
3462                 expression->builtin_prefetch.rw = parse_assignment_expression();
3463         }
3464         if (token.type == ',') {
3465                 next_token();
3466                 expression->builtin_prefetch.locality = parse_assignment_expression();
3467         }
3468         expect(')');
3469         expression->base.datatype = type_void;
3470
3471         return expression;
3472 }
3473
3474 static expression_t *parse_compare_builtin(void)
3475 {
3476         expression_t *expression;
3477
3478         switch(token.type) {
3479         case T___builtin_isgreater:
3480                 expression = allocate_expression_zero(EXPR_BINARY_ISGREATER);
3481                 break;
3482         case T___builtin_isgreaterequal:
3483                 expression = allocate_expression_zero(EXPR_BINARY_ISGREATEREQUAL);
3484                 break;
3485         case T___builtin_isless:
3486                 expression = allocate_expression_zero(EXPR_BINARY_ISLESS);
3487                 break;
3488         case T___builtin_islessequal:
3489                 expression = allocate_expression_zero(EXPR_BINARY_ISLESSEQUAL);
3490                 break;
3491         case T___builtin_islessgreater:
3492                 expression = allocate_expression_zero(EXPR_BINARY_ISLESSGREATER);
3493                 break;
3494         case T___builtin_isunordered:
3495                 expression = allocate_expression_zero(EXPR_BINARY_ISUNORDERED);
3496                 break;
3497         default:
3498                 panic("invalid compare builtin found");
3499                 break;
3500         }
3501         next_token();
3502
3503         expect('(');
3504         expression->binary.left = parse_assignment_expression();
3505         expect(',');
3506         expression->binary.right = parse_assignment_expression();
3507         expect(')');
3508
3509         type_t *orig_type_left  = expression->binary.left->base.datatype;
3510         type_t *orig_type_right = expression->binary.right->base.datatype;
3511         if(orig_type_left == NULL || orig_type_right == NULL)
3512                 return expression;
3513
3514         type_t *type_left  = skip_typeref(orig_type_left);
3515         type_t *type_right = skip_typeref(orig_type_right);
3516         if(!is_type_floating(type_left) && !is_type_floating(type_right)) {
3517                 type_error_incompatible("invalid operands in comparison",
3518                                         token.source_position, type_left, type_right);
3519         } else {
3520                 semantic_comparison(&expression->binary);
3521         }
3522
3523         return expression;
3524 }
3525
3526 static expression_t *parse_builtin_expect(void)
3527 {
3528         eat(T___builtin_expect);
3529
3530         expression_t *expression
3531                 = allocate_expression_zero(EXPR_BINARY_BUILTIN_EXPECT);
3532
3533         expect('(');
3534         expression->binary.left = parse_assignment_expression();
3535         expect(',');
3536         expression->binary.right = parse_constant_expression();
3537         expect(')');
3538
3539         expression->base.datatype = expression->binary.left->base.datatype;
3540
3541         return expression;
3542 }
3543
3544 static expression_t *parse_assume(void) {
3545         eat(T_assume);
3546
3547         expression_t *expression
3548                 = allocate_expression_zero(EXPR_UNARY_ASSUME);
3549
3550         expect('(');
3551         expression->unary.value = parse_assignment_expression();
3552         expect(')');
3553
3554         expression->base.datatype = type_void;
3555         return expression;
3556 }
3557
3558 static expression_t *parse_alignof(void) {
3559         eat(T___alignof__);
3560
3561         expression_t *expression
3562                 = allocate_expression_zero(EXPR_ALIGNOF);
3563
3564         expect('(');
3565         expression->alignofe.type = parse_typename();
3566         expect(')');
3567
3568         expression->base.datatype = type_size_t;
3569         return expression;
3570 }
3571
3572 static expression_t *parse_primary_expression(void)
3573 {
3574         switch(token.type) {
3575         case T_INTEGER:
3576                 return parse_int_const();
3577         case T_FLOATINGPOINT:
3578                 return parse_float_const();
3579         case T_STRING_LITERAL:
3580                 return parse_string_const();
3581         case T_WIDE_STRING_LITERAL:
3582                 return parse_wide_string_const();
3583         case T_IDENTIFIER:
3584                 return parse_reference();
3585         case T___FUNCTION__:
3586         case T___func__:
3587                 return parse_function_keyword();
3588         case T___PRETTY_FUNCTION__:
3589                 return parse_pretty_function_keyword();
3590         case T___builtin_offsetof:
3591                 return parse_offsetof();
3592         case T___builtin_va_start:
3593                 return parse_va_start();
3594         case T___builtin_va_arg:
3595                 return parse_va_arg();
3596         case T___builtin_expect:
3597                 return parse_builtin_expect();
3598         case T___builtin_nanf:
3599         case T___builtin_alloca:
3600         case T___builtin_va_end:
3601                 return parse_builtin_symbol();
3602         case T___builtin_isgreater:
3603         case T___builtin_isgreaterequal:
3604         case T___builtin_isless:
3605         case T___builtin_islessequal:
3606         case T___builtin_islessgreater:
3607         case T___builtin_isunordered:
3608                 return parse_compare_builtin();
3609         case T___builtin_constant_p:
3610                 return parse_builtin_constant();
3611         case T___builtin_prefetch:
3612                 return parse_builtin_prefetch();
3613         case T___alignof__:
3614                 return parse_alignof();
3615         case T_assume:
3616                 return parse_assume();
3617
3618         case '(':
3619                 return parse_brace_expression();
3620         }
3621
3622         errorf(HERE, "unexpected token '%K'", &token);
3623         eat_statement();
3624
3625         return create_invalid_expression();
3626 }
3627
3628 /**
3629  * Check if the expression has the character type and issue a warning then.
3630  */
3631 static void check_for_char_index_type(const expression_t *expression) {
3632         type_t *type      = expression->base.datatype;
3633         type_t *base_type = skip_typeref(type);
3634
3635         if (base_type->base.kind == TYPE_ATOMIC) {
3636                 if (base_type->atomic.akind == ATOMIC_TYPE_CHAR) {
3637                         warningf(expression->base.source_position,
3638                                 "array subscript has type '%T'", type);
3639                 }
3640         }
3641 }
3642
3643 static expression_t *parse_array_expression(unsigned precedence,
3644                                             expression_t *left)
3645 {
3646         (void) precedence;
3647
3648         eat('[');
3649
3650         expression_t *inside = parse_expression();
3651
3652         array_access_expression_t *array_access
3653                 = allocate_ast_zero(sizeof(array_access[0]));
3654
3655         array_access->expression.kind = EXPR_ARRAY_ACCESS;
3656
3657         type_t *type_left   = left->base.datatype;
3658         type_t *type_inside = inside->base.datatype;
3659         type_t *return_type = NULL;
3660
3661         if(type_left != NULL && type_inside != NULL) {
3662                 type_left   = skip_typeref(type_left);
3663                 type_inside = skip_typeref(type_inside);
3664
3665                 if(is_type_pointer(type_left)) {
3666                         pointer_type_t *pointer = &type_left->pointer;
3667                         return_type             = pointer->points_to;
3668                         array_access->array_ref = left;
3669                         array_access->index     = inside;
3670                         check_for_char_index_type(inside);
3671                 } else if(is_type_pointer(type_inside)) {
3672                         pointer_type_t *pointer = &type_inside->pointer;
3673                         return_type             = pointer->points_to;
3674                         array_access->array_ref = inside;
3675                         array_access->index     = left;
3676                         array_access->flipped   = true;
3677                         check_for_char_index_type(left);
3678                 } else {
3679                         errorf(HERE, "array access on object with non-pointer types '%T', '%T'", type_left, type_inside);
3680                 }
3681         } else {
3682                 array_access->array_ref = left;
3683                 array_access->index     = inside;
3684         }
3685
3686         if(token.type != ']') {
3687                 parse_error_expected("Problem while parsing array access", ']', 0);
3688                 return (expression_t*) array_access;
3689         }
3690         next_token();
3691
3692         return_type = automatic_type_conversion(return_type);
3693         array_access->expression.datatype = return_type;
3694
3695         return (expression_t*) array_access;
3696 }
3697
3698 static expression_t *parse_sizeof(unsigned precedence)
3699 {
3700         eat(T_sizeof);
3701
3702         sizeof_expression_t *sizeof_expression
3703                 = allocate_ast_zero(sizeof(sizeof_expression[0]));
3704         sizeof_expression->expression.kind     = EXPR_SIZEOF;
3705         sizeof_expression->expression.datatype = type_size_t;
3706
3707         if(token.type == '(' && is_declaration_specifier(look_ahead(1), true)) {
3708                 next_token();
3709                 sizeof_expression->type = parse_typename();
3710                 expect(')');
3711         } else {
3712                 expression_t *expression  = parse_sub_expression(precedence);
3713                 expression->base.datatype = revert_automatic_type_conversion(expression);
3714
3715                 sizeof_expression->type            = expression->base.datatype;
3716                 sizeof_expression->size_expression = expression;
3717         }
3718
3719         return (expression_t*) sizeof_expression;
3720 }
3721
3722 static expression_t *parse_select_expression(unsigned precedence,
3723                                              expression_t *compound)
3724 {
3725         (void) precedence;
3726         assert(token.type == '.' || token.type == T_MINUSGREATER);
3727
3728         bool is_pointer = (token.type == T_MINUSGREATER);
3729         next_token();
3730
3731         expression_t *select    = allocate_expression_zero(EXPR_SELECT);
3732         select->select.compound = compound;
3733
3734         if(token.type != T_IDENTIFIER) {
3735                 parse_error_expected("while parsing select", T_IDENTIFIER, 0);
3736                 return select;
3737         }
3738         symbol_t *symbol      = token.v.symbol;
3739         select->select.symbol = symbol;
3740         next_token();
3741
3742         type_t *orig_type = compound->base.datatype;
3743         if(orig_type == NULL)
3744                 return create_invalid_expression();
3745
3746         type_t *type = skip_typeref(orig_type);
3747
3748         type_t *type_left = type;
3749         if(is_pointer) {
3750                 if(type->kind != TYPE_POINTER) {
3751                         errorf(HERE, "left hand side of '->' is not a pointer, but '%T'", orig_type);
3752                         return create_invalid_expression();
3753                 }
3754                 pointer_type_t *pointer_type = &type->pointer;
3755                 type_left                    = pointer_type->points_to;
3756         }
3757         type_left = skip_typeref(type_left);
3758
3759         if(type_left->kind != TYPE_COMPOUND_STRUCT
3760                         && type_left->kind != TYPE_COMPOUND_UNION) {
3761                 errorf(HERE, "request for member '%Y' in something not a struct or "
3762                        "union, but '%T'", symbol, type_left);
3763                 return create_invalid_expression();
3764         }
3765
3766         compound_type_t *compound_type = &type_left->compound;
3767         declaration_t   *declaration   = compound_type->declaration;
3768
3769         if(!declaration->init.is_defined) {
3770                 errorf(HERE, "request for member '%Y' of incomplete type '%T'",
3771                        symbol, type_left);
3772                 return create_invalid_expression();
3773         }
3774
3775         declaration_t *iter = declaration->context.declarations;
3776         for( ; iter != NULL; iter = iter->next) {
3777                 if(iter->symbol == symbol) {
3778                         break;
3779                 }
3780         }
3781         if(iter == NULL) {
3782                 errorf(HERE, "'%T' has no member named '%Y'", orig_type, symbol);
3783                 return create_invalid_expression();
3784         }
3785
3786         /* we always do the auto-type conversions; the & and sizeof parser contains
3787          * code to revert this! */
3788         type_t *expression_type = automatic_type_conversion(iter->type);
3789
3790         select->select.compound_entry = iter;
3791         select->base.datatype         = expression_type;
3792
3793         if(expression_type->kind == TYPE_BITFIELD) {
3794                 expression_t *extract
3795                         = allocate_expression_zero(EXPR_UNARY_BITFIELD_EXTRACT);
3796                 extract->unary.value   = select;
3797                 extract->base.datatype = expression_type->bitfield.base;
3798
3799                 return extract;
3800         }
3801
3802         return select;
3803 }
3804
3805 /**
3806  * Parse a call expression, ie. expression '( ... )'.
3807  *
3808  * @param expression  the function address
3809  */
3810 static expression_t *parse_call_expression(unsigned precedence,
3811                                            expression_t *expression)
3812 {
3813         (void) precedence;
3814         expression_t *result = allocate_expression_zero(EXPR_CALL);
3815
3816         call_expression_t *call = &result->call;
3817         call->function          = expression;
3818
3819         function_type_t *function_type = NULL;
3820         type_t          *orig_type     = expression->base.datatype;
3821         if(orig_type != NULL) {
3822                 type_t *type  = skip_typeref(orig_type);
3823
3824                 if(is_type_pointer(type)) {
3825                         pointer_type_t *pointer_type = &type->pointer;
3826
3827                         type = skip_typeref(pointer_type->points_to);
3828
3829                         if (is_type_function(type)) {
3830                                 function_type             = &type->function;
3831                                 call->expression.datatype = function_type->return_type;
3832                         }
3833                 }
3834                 if(function_type == NULL) {
3835                         errorf(HERE, "called object '%E' (type '%T') is not a pointer to a function", expression, orig_type);
3836
3837                         function_type             = NULL;
3838                         call->expression.datatype = NULL;
3839                 }
3840         }
3841
3842         /* parse arguments */
3843         eat('(');
3844
3845         if(token.type != ')') {
3846                 call_argument_t *last_argument = NULL;
3847
3848                 while(true) {
3849                         call_argument_t *argument = allocate_ast_zero(sizeof(argument[0]));
3850
3851                         argument->expression = parse_assignment_expression();
3852                         if(last_argument == NULL) {
3853                                 call->arguments = argument;
3854                         } else {
3855                                 last_argument->next = argument;
3856                         }
3857                         last_argument = argument;
3858
3859                         if(token.type != ',')
3860                                 break;
3861                         next_token();
3862                 }
3863         }
3864         expect(')');
3865
3866         if(function_type != NULL) {
3867                 function_parameter_t *parameter = function_type->parameters;
3868                 call_argument_t      *argument  = call->arguments;
3869                 for( ; parameter != NULL && argument != NULL;
3870                                 parameter = parameter->next, argument = argument->next) {
3871                         type_t *expected_type = parameter->type;
3872                         /* TODO report context in error messages */
3873                         argument->expression = create_implicit_cast(argument->expression,
3874                                                                     expected_type);
3875                 }
3876                 /* too few parameters */
3877                 if(parameter != NULL) {
3878                         errorf(HERE, "too few arguments to function '%E'", expression);
3879                 } else if(argument != NULL) {
3880                         /* too many parameters */
3881                         if(!function_type->variadic
3882                                         && !function_type->unspecified_parameters) {
3883                                 errorf(HERE, "too many arguments to function '%E'", expression);
3884                         } else {
3885                                 /* do default promotion */
3886                                 for( ; argument != NULL; argument = argument->next) {
3887                                         type_t *type = argument->expression->base.datatype;
3888
3889                                         if(type == NULL)
3890                                                 continue;
3891
3892                                         type = skip_typeref(type);
3893                                         if(is_type_integer(type)) {
3894                                                 type = promote_integer(type);
3895                                         } else if(type == type_float) {
3896                                                 type = type_double;
3897                                         }
3898
3899                                         argument->expression
3900                                                 = create_implicit_cast(argument->expression, type);
3901                                 }
3902
3903                                 check_format(&result->call);
3904                         }
3905                 } else {
3906                         check_format(&result->call);
3907                 }
3908         }
3909
3910         return result;
3911 }
3912
3913 static type_t *semantic_arithmetic(type_t *type_left, type_t *type_right);
3914
3915 static bool same_compound_type(const type_t *type1, const type_t *type2)
3916 {
3917         if(!is_type_compound(type1))
3918                 return false;
3919         if(type1->kind != type2->kind)
3920                 return false;
3921
3922         const compound_type_t *compound1 = &type1->compound;
3923         const compound_type_t *compound2 = &type2->compound;
3924
3925         return compound1->declaration == compound2->declaration;
3926 }
3927
3928 /**
3929  * Parse a conditional expression, ie. 'expression ? ... : ...'.
3930  *
3931  * @param expression  the conditional expression
3932  */
3933 static expression_t *parse_conditional_expression(unsigned precedence,
3934                                                   expression_t *expression)
3935 {
3936         eat('?');
3937
3938         expression_t *result = allocate_expression_zero(EXPR_CONDITIONAL);
3939
3940         conditional_expression_t *conditional = &result->conditional;
3941         conditional->condition = expression;
3942
3943         /* 6.5.15.2 */
3944         type_t *condition_type_orig = expression->base.datatype;
3945         if(condition_type_orig != NULL) {
3946                 type_t *condition_type = skip_typeref(condition_type_orig);
3947                 if(condition_type != NULL && !is_type_scalar(condition_type)) {
3948                         type_error("expected a scalar type in conditional condition",
3949                                    expression->base.source_position, condition_type_orig);
3950                 }
3951         }
3952
3953         expression_t *true_expression = parse_expression();
3954         expect(':');
3955         expression_t *false_expression = parse_sub_expression(precedence);
3956
3957         conditional->true_expression  = true_expression;
3958         conditional->false_expression = false_expression;
3959
3960         type_t *orig_true_type  = true_expression->base.datatype;
3961         type_t *orig_false_type = false_expression->base.datatype;
3962         if(orig_true_type == NULL || orig_false_type == NULL)
3963                 return result;
3964
3965         type_t *true_type  = skip_typeref(orig_true_type);
3966         type_t *false_type = skip_typeref(orig_false_type);
3967
3968         /* 6.5.15.3 */
3969         type_t *result_type = NULL;
3970         if (is_type_arithmetic(true_type) && is_type_arithmetic(false_type)) {
3971                 result_type = semantic_arithmetic(true_type, false_type);
3972
3973                 true_expression  = create_implicit_cast(true_expression, result_type);
3974                 false_expression = create_implicit_cast(false_expression, result_type);
3975
3976                 conditional->true_expression     = true_expression;
3977                 conditional->false_expression    = false_expression;
3978                 conditional->expression.datatype = result_type;
3979         } else if (same_compound_type(true_type, false_type)
3980                         || (is_type_atomic(true_type, ATOMIC_TYPE_VOID) &&
3981                                 is_type_atomic(false_type, ATOMIC_TYPE_VOID))) {
3982                 /* just take 1 of the 2 types */
3983                 result_type = true_type;
3984         } else if (is_type_pointer(true_type) && is_type_pointer(false_type)
3985                         && pointers_compatible(true_type, false_type)) {
3986                 /* ok */
3987                 result_type = true_type;
3988         } else {
3989                 /* TODO */
3990                 type_error_incompatible("while parsing conditional",
3991                                         expression->base.source_position, true_type,
3992                                         false_type);
3993         }
3994
3995         conditional->expression.datatype = result_type;
3996         return result;
3997 }
3998
3999 /**
4000  * Parse an extension expression.
4001  */
4002 static expression_t *parse_extension(unsigned precedence)
4003 {
4004         eat(T___extension__);
4005
4006         /* TODO enable extensions */
4007         expression_t *expression = parse_sub_expression(precedence);
4008         /* TODO disable extensions */
4009         return expression;
4010 }
4011
4012 static expression_t *parse_builtin_classify_type(const unsigned precedence)
4013 {
4014         eat(T___builtin_classify_type);
4015
4016         expression_t *result  = allocate_expression_zero(EXPR_CLASSIFY_TYPE);
4017         result->base.datatype = type_int;
4018
4019         expect('(');
4020         expression_t *expression = parse_sub_expression(precedence);
4021         expect(')');
4022         result->classify_type.type_expression = expression;
4023
4024         return result;
4025 }
4026
4027 static void semantic_incdec(unary_expression_t *expression)
4028 {
4029         type_t *orig_type = expression->value->base.datatype;
4030         if(orig_type == NULL)
4031                 return;
4032
4033         type_t *type = skip_typeref(orig_type);
4034         if(!is_type_arithmetic(type) && type->kind != TYPE_POINTER) {
4035                 /* TODO: improve error message */
4036                 errorf(HERE, "operation needs an arithmetic or pointer type");
4037                 return;
4038         }
4039
4040         expression->expression.datatype = orig_type;
4041 }
4042
4043 static void semantic_unexpr_arithmetic(unary_expression_t *expression)
4044 {
4045         type_t *orig_type = expression->value->base.datatype;
4046         if(orig_type == NULL)
4047                 return;
4048
4049         type_t *type = skip_typeref(orig_type);
4050         if(!is_type_arithmetic(type)) {
4051                 /* TODO: improve error message */
4052                 errorf(HERE, "operation needs an arithmetic type");
4053                 return;
4054         }
4055
4056         expression->expression.datatype = orig_type;
4057 }
4058
4059 static void semantic_unexpr_scalar(unary_expression_t *expression)
4060 {
4061         type_t *orig_type = expression->value->base.datatype;
4062         if(orig_type == NULL)
4063                 return;
4064
4065         type_t *type = skip_typeref(orig_type);
4066         if (!is_type_scalar(type)) {
4067                 errorf(HERE, "operand of ! must be of scalar type");
4068                 return;
4069         }
4070
4071         expression->expression.datatype = orig_type;
4072 }
4073
4074 static void semantic_unexpr_integer(unary_expression_t *expression)
4075 {
4076         type_t *orig_type = expression->value->base.datatype;
4077         if(orig_type == NULL)
4078                 return;
4079
4080         type_t *type = skip_typeref(orig_type);
4081         if (!is_type_integer(type)) {
4082                 errorf(HERE, "operand of ~ must be of integer type");
4083                 return;
4084         }
4085
4086         expression->expression.datatype = orig_type;
4087 }
4088
4089 static void semantic_dereference(unary_expression_t *expression)
4090 {
4091         type_t *orig_type = expression->value->base.datatype;
4092         if(orig_type == NULL)
4093                 return;
4094
4095         type_t *type = skip_typeref(orig_type);
4096         if(!is_type_pointer(type)) {
4097                 errorf(HERE, "Unary '*' needs pointer or arrray type, but type '%T' given", orig_type);
4098                 return;
4099         }
4100
4101         pointer_type_t *pointer_type = &type->pointer;
4102         type_t         *result_type  = pointer_type->points_to;
4103
4104         result_type = automatic_type_conversion(result_type);
4105         expression->expression.datatype = result_type;
4106 }
4107
4108 /**
4109  * Check the semantic of the address taken expression.
4110  */
4111 static void semantic_take_addr(unary_expression_t *expression)
4112 {
4113         expression_t *value  = expression->value;
4114         value->base.datatype = revert_automatic_type_conversion(value);
4115
4116         type_t *orig_type = value->base.datatype;
4117         if(orig_type == NULL)
4118                 return;
4119
4120         if(value->kind == EXPR_REFERENCE) {
4121                 reference_expression_t *reference   = (reference_expression_t*) value;
4122                 declaration_t          *declaration = reference->declaration;
4123                 if(declaration != NULL) {
4124                         if (declaration->storage_class == STORAGE_CLASS_REGISTER) {
4125                                 errorf(expression->expression.source_position,
4126                                         "address of register variable '%Y' requested",
4127                                         declaration->symbol);
4128                         }
4129                         declaration->address_taken = 1;
4130                 }
4131         }
4132
4133         expression->expression.datatype = make_pointer_type(orig_type, TYPE_QUALIFIER_NONE);
4134 }
4135
4136 #define CREATE_UNARY_EXPRESSION_PARSER(token_type, unexpression_type, sfunc)   \
4137 static expression_t *parse_##unexpression_type(unsigned precedence)            \
4138 {                                                                              \
4139         eat(token_type);                                                           \
4140                                                                                    \
4141         expression_t *unary_expression                                             \
4142                 = allocate_expression_zero(unexpression_type);                         \
4143         unary_expression->base.source_position = HERE;                             \
4144         unary_expression->unary.value = parse_sub_expression(precedence);          \
4145                                                                                    \
4146         sfunc(&unary_expression->unary);                                           \
4147                                                                                    \
4148         return unary_expression;                                                   \
4149 }
4150
4151 CREATE_UNARY_EXPRESSION_PARSER('-', EXPR_UNARY_NEGATE,
4152                                semantic_unexpr_arithmetic)
4153 CREATE_UNARY_EXPRESSION_PARSER('+', EXPR_UNARY_PLUS,
4154                                semantic_unexpr_arithmetic)
4155 CREATE_UNARY_EXPRESSION_PARSER('!', EXPR_UNARY_NOT,
4156                                semantic_unexpr_scalar)
4157 CREATE_UNARY_EXPRESSION_PARSER('*', EXPR_UNARY_DEREFERENCE,
4158                                semantic_dereference)
4159 CREATE_UNARY_EXPRESSION_PARSER('&', EXPR_UNARY_TAKE_ADDRESS,
4160                                semantic_take_addr)
4161 CREATE_UNARY_EXPRESSION_PARSER('~', EXPR_UNARY_BITWISE_NEGATE,
4162                                semantic_unexpr_integer)
4163 CREATE_UNARY_EXPRESSION_PARSER(T_PLUSPLUS,   EXPR_UNARY_PREFIX_INCREMENT,
4164                                semantic_incdec)
4165 CREATE_UNARY_EXPRESSION_PARSER(T_MINUSMINUS, EXPR_UNARY_PREFIX_DECREMENT,
4166                                semantic_incdec)
4167
4168 #define CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(token_type, unexpression_type, \
4169                                                sfunc)                         \
4170 static expression_t *parse_##unexpression_type(unsigned precedence,           \
4171                                                expression_t *left)            \
4172 {                                                                             \
4173         (void) precedence;                                                        \
4174         eat(token_type);                                                          \
4175                                                                               \
4176         expression_t *unary_expression                                            \
4177                 = allocate_expression_zero(unexpression_type);                        \
4178         unary_expression->unary.value = left;                                     \
4179                                                                                   \
4180         sfunc(&unary_expression->unary);                                          \
4181                                                                               \
4182         return unary_expression;                                                  \
4183 }
4184
4185 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_PLUSPLUS,
4186                                        EXPR_UNARY_POSTFIX_INCREMENT,
4187                                        semantic_incdec)
4188 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_MINUSMINUS,
4189                                        EXPR_UNARY_POSTFIX_DECREMENT,
4190                                        semantic_incdec)
4191
4192 static type_t *semantic_arithmetic(type_t *type_left, type_t *type_right)
4193 {
4194         /* TODO: handle complex + imaginary types */
4195
4196         /* § 6.3.1.8 Usual arithmetic conversions */
4197         if(type_left == type_long_double || type_right == type_long_double) {
4198                 return type_long_double;
4199         } else if(type_left == type_double || type_right == type_double) {
4200                 return type_double;
4201         } else if(type_left == type_float || type_right == type_float) {
4202                 return type_float;
4203         }
4204
4205         type_right = promote_integer(type_right);
4206         type_left  = promote_integer(type_left);
4207
4208         if(type_left == type_right)
4209                 return type_left;
4210
4211         bool signed_left  = is_type_signed(type_left);
4212         bool signed_right = is_type_signed(type_right);
4213         int  rank_left    = get_rank(type_left);
4214         int  rank_right   = get_rank(type_right);
4215         if(rank_left < rank_right) {
4216                 if(signed_left == signed_right || !signed_right) {
4217                         return type_right;
4218                 } else {
4219                         return type_left;
4220                 }
4221         } else {
4222                 if(signed_left == signed_right || !signed_left) {
4223                         return type_left;
4224                 } else {
4225                         return type_right;
4226                 }
4227         }
4228 }
4229
4230 /**
4231  * Check the semantic restrictions for a binary expression.
4232  */
4233 static void semantic_binexpr_arithmetic(binary_expression_t *expression)
4234 {
4235         expression_t *left       = expression->left;
4236         expression_t *right      = expression->right;
4237         type_t       *orig_type_left  = left->base.datatype;
4238         type_t       *orig_type_right = right->base.datatype;
4239
4240         if(orig_type_left == NULL || orig_type_right == NULL)
4241                 return;
4242
4243         type_t *type_left  = skip_typeref(orig_type_left);
4244         type_t *type_right = skip_typeref(orig_type_right);
4245
4246         if(!is_type_arithmetic(type_left) || !is_type_arithmetic(type_right)) {
4247                 /* TODO: improve error message */
4248                 errorf(HERE, "operation needs arithmetic types");
4249                 return;
4250         }
4251
4252         type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
4253         expression->left  = create_implicit_cast(left, arithmetic_type);
4254         expression->right = create_implicit_cast(right, arithmetic_type);
4255         expression->expression.datatype = arithmetic_type;
4256 }
4257
4258 static void semantic_shift_op(binary_expression_t *expression)
4259 {
4260         expression_t *left       = expression->left;
4261         expression_t *right      = expression->right;
4262         type_t       *orig_type_left  = left->base.datatype;
4263         type_t       *orig_type_right = right->base.datatype;
4264
4265         if(orig_type_left == NULL || orig_type_right == NULL)
4266                 return;
4267
4268         type_t *type_left  = skip_typeref(orig_type_left);
4269         type_t *type_right = skip_typeref(orig_type_right);
4270
4271         if(!is_type_integer(type_left) || !is_type_integer(type_right)) {
4272                 /* TODO: improve error message */
4273                 errorf(HERE, "operation needs integer types");
4274                 return;
4275         }
4276
4277         type_left  = promote_integer(type_left);
4278         type_right = promote_integer(type_right);
4279
4280         expression->left  = create_implicit_cast(left, type_left);
4281         expression->right = create_implicit_cast(right, type_right);
4282         expression->expression.datatype = type_left;
4283 }
4284
4285 static void semantic_add(binary_expression_t *expression)
4286 {
4287         expression_t *left            = expression->left;
4288         expression_t *right           = expression->right;
4289         type_t       *orig_type_left  = left->base.datatype;
4290         type_t       *orig_type_right = right->base.datatype;
4291
4292         if(orig_type_left == NULL || orig_type_right == NULL)
4293                 return;
4294
4295         type_t *type_left  = skip_typeref(orig_type_left);
4296         type_t *type_right = skip_typeref(orig_type_right);
4297
4298         /* § 5.6.5 */
4299         if(is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) {
4300                 type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
4301                 expression->left  = create_implicit_cast(left, arithmetic_type);
4302                 expression->right = create_implicit_cast(right, arithmetic_type);
4303                 expression->expression.datatype = arithmetic_type;
4304                 return;
4305         } else if(is_type_pointer(type_left) && is_type_integer(type_right)) {
4306                 expression->expression.datatype = type_left;
4307         } else if(is_type_pointer(type_right) && is_type_integer(type_left)) {
4308                 expression->expression.datatype = type_right;
4309         } else {
4310                 errorf(HERE, "invalid operands to binary + ('%T', '%T')", orig_type_left, orig_type_right);
4311         }
4312 }
4313
4314 static void semantic_sub(binary_expression_t *expression)
4315 {
4316         expression_t *left            = expression->left;
4317         expression_t *right           = expression->right;
4318         type_t       *orig_type_left  = left->base.datatype;
4319         type_t       *orig_type_right = right->base.datatype;
4320
4321         if(orig_type_left == NULL || orig_type_right == NULL)
4322                 return;
4323
4324         type_t       *type_left       = skip_typeref(orig_type_left);
4325         type_t       *type_right      = skip_typeref(orig_type_right);
4326
4327         /* § 5.6.5 */
4328         if(is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) {
4329                 type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
4330                 expression->left  = create_implicit_cast(left, arithmetic_type);
4331                 expression->right = create_implicit_cast(right, arithmetic_type);
4332                 expression->expression.datatype = arithmetic_type;
4333                 return;
4334         } else if(is_type_pointer(type_left) && is_type_integer(type_right)) {
4335                 expression->expression.datatype = type_left;
4336         } else if(is_type_pointer(type_left) && is_type_pointer(type_right)) {
4337                 if(!pointers_compatible(type_left, type_right)) {
4338                         errorf(HERE, "pointers to incompatible objects to binary - ('%T', '%T')", orig_type_left, orig_type_right);
4339                 } else {
4340                         expression->expression.datatype = type_ptrdiff_t;
4341                 }
4342         } else {
4343                 errorf(HERE, "invalid operands to binary - ('%T', '%T')", orig_type_left, orig_type_right);
4344         }
4345 }
4346
4347 static void semantic_comparison(binary_expression_t *expression)
4348 {
4349         expression_t *left            = expression->left;
4350         expression_t *right           = expression->right;
4351         type_t       *orig_type_left  = left->base.datatype;
4352         type_t       *orig_type_right = right->base.datatype;
4353
4354         if(orig_type_left == NULL || orig_type_right == NULL)
4355                 return;
4356
4357         type_t *type_left  = skip_typeref(orig_type_left);
4358         type_t *type_right = skip_typeref(orig_type_right);
4359
4360         /* TODO non-arithmetic types */
4361         if(is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) {
4362                 type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
4363                 expression->left  = create_implicit_cast(left, arithmetic_type);
4364                 expression->right = create_implicit_cast(right, arithmetic_type);
4365                 expression->expression.datatype = arithmetic_type;
4366         } else if (is_type_pointer(type_left) && is_type_pointer(type_right)) {
4367                 /* TODO check compatibility */
4368         } else if (is_type_pointer(type_left)) {
4369                 expression->right = create_implicit_cast(right, type_left);
4370         } else if (is_type_pointer(type_right)) {
4371                 expression->left = create_implicit_cast(left, type_right);
4372         } else {
4373                 type_error_incompatible("invalid operands in comparison",
4374                                         token.source_position, type_left, type_right);
4375         }
4376         expression->expression.datatype = type_int;
4377 }
4378
4379 static void semantic_arithmetic_assign(binary_expression_t *expression)
4380 {
4381         expression_t *left            = expression->left;
4382         expression_t *right           = expression->right;
4383         type_t       *orig_type_left  = left->base.datatype;
4384         type_t       *orig_type_right = right->base.datatype;
4385
4386         if(orig_type_left == NULL || orig_type_right == NULL)
4387                 return;
4388
4389         type_t *type_left  = skip_typeref(orig_type_left);
4390         type_t *type_right = skip_typeref(orig_type_right);
4391
4392         if(!is_type_arithmetic(type_left) || !is_type_arithmetic(type_right)) {
4393                 /* TODO: improve error message */
4394                 errorf(HERE, "operation needs arithmetic types");
4395                 return;
4396         }
4397
4398         /* combined instructions are tricky. We can't create an implicit cast on
4399          * the left side, because we need the uncasted form for the store.
4400          * The ast2firm pass has to know that left_type must be right_type
4401          * for the arithmetic operation and create a cast by itself */
4402         type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
4403         expression->right       = create_implicit_cast(right, arithmetic_type);
4404         expression->expression.datatype = type_left;
4405 }
4406
4407 static void semantic_arithmetic_addsubb_assign(binary_expression_t *expression)
4408 {
4409         expression_t *left            = expression->left;
4410         expression_t *right           = expression->right;
4411         type_t       *orig_type_left  = left->base.datatype;
4412         type_t       *orig_type_right = right->base.datatype;
4413
4414         if(orig_type_left == NULL || orig_type_right == NULL)
4415                 return;
4416
4417         type_t *type_left  = skip_typeref(orig_type_left);
4418         type_t *type_right = skip_typeref(orig_type_right);
4419
4420         if (is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) {
4421                 /* combined instructions are tricky. We can't create an implicit cast on
4422                  * the left side, because we need the uncasted form for the store.
4423                  * The ast2firm pass has to know that left_type must be right_type
4424                  * for the arithmetic operation and create a cast by itself */
4425                 type_t *const arithmetic_type = semantic_arithmetic(type_left, type_right);
4426                 expression->right = create_implicit_cast(right, arithmetic_type);
4427                 expression->expression.datatype = type_left;
4428         } else if (is_type_pointer(type_left) && is_type_integer(type_right)) {
4429                 expression->expression.datatype = type_left;
4430         } else {
4431                 errorf(HERE, "incompatible types '%T' and '%T' in assignment", orig_type_left, orig_type_right);
4432                 return;
4433         }
4434 }
4435
4436 /**
4437  * Check the semantic restrictions of a logical expression.
4438  */
4439 static void semantic_logical_op(binary_expression_t *expression)
4440 {
4441         expression_t *left            = expression->left;
4442         expression_t *right           = expression->right;
4443         type_t       *orig_type_left  = left->base.datatype;
4444         type_t       *orig_type_right = right->base.datatype;
4445
4446         if(orig_type_left == NULL || orig_type_right == NULL)
4447                 return;
4448
4449         type_t *type_left  = skip_typeref(orig_type_left);
4450         type_t *type_right = skip_typeref(orig_type_right);
4451
4452         if (!is_type_scalar(type_left) || !is_type_scalar(type_right)) {
4453                 /* TODO: improve error message */
4454                 errorf(HERE, "operation needs scalar types");
4455                 return;
4456         }
4457
4458         expression->expression.datatype = type_int;
4459 }
4460
4461 /**
4462  * Checks if a compound type has constant fields.
4463  */
4464 static bool has_const_fields(const compound_type_t *type)
4465 {
4466         const context_t     *context = &type->declaration->context;
4467         const declaration_t *declaration = context->declarations;
4468
4469         for (; declaration != NULL; declaration = declaration->next) {
4470                 if (declaration->namespc != NAMESPACE_NORMAL)
4471                         continue;
4472
4473                 const type_t *decl_type = skip_typeref(declaration->type);
4474                 if (decl_type->base.qualifiers & TYPE_QUALIFIER_CONST)
4475                         return true;
4476         }
4477         /* TODO */
4478         return false;
4479 }
4480
4481 /**
4482  * Check the semantic restrictions of a binary assign expression.
4483  */
4484 static void semantic_binexpr_assign(binary_expression_t *expression)
4485 {
4486         expression_t *left           = expression->left;
4487         type_t       *orig_type_left = left->base.datatype;
4488
4489         if(orig_type_left == NULL)
4490                 return;
4491
4492         type_t *type_left = revert_automatic_type_conversion(left);
4493         type_left         = skip_typeref(orig_type_left);
4494
4495         /* must be a modifiable lvalue */
4496         if (is_type_array(type_left)) {
4497                 errorf(HERE, "cannot assign to arrays ('%E')", left);
4498                 return;
4499         }
4500         if(type_left->base.qualifiers & TYPE_QUALIFIER_CONST) {
4501                 errorf(HERE, "assignment to readonly location '%E' (type '%T')", left,
4502                        orig_type_left);
4503                 return;
4504         }
4505         if(is_type_incomplete(type_left)) {
4506                 errorf(HERE,
4507                        "left-hand side of assignment '%E' has incomplete type '%T'",
4508                        left, orig_type_left);
4509                 return;
4510         }
4511         if(is_type_compound(type_left) && has_const_fields(&type_left->compound)) {
4512                 errorf(HERE, "cannot assign to '%E' because compound type '%T' has readonly fields",
4513                        left, orig_type_left);
4514                 return;
4515         }
4516
4517         semantic_assign(orig_type_left, &expression->right, "assignment");
4518
4519         expression->expression.datatype = orig_type_left;
4520 }
4521
4522 static void semantic_comma(binary_expression_t *expression)
4523 {
4524         expression->expression.datatype = expression->right->base.datatype;
4525 }
4526
4527 #define CREATE_BINEXPR_PARSER(token_type, binexpression_type, sfunc, lr)  \
4528 static expression_t *parse_##binexpression_type(unsigned precedence,      \
4529                                                 expression_t *left)       \
4530 {                                                                         \
4531         eat(token_type);                                                      \
4532                                                                           \
4533         expression_t *right = parse_sub_expression(precedence + lr);          \
4534                                                                           \
4535         expression_t *binexpr = allocate_expression_zero(binexpression_type); \
4536         binexpr->binary.left  = left;                                         \
4537         binexpr->binary.right = right;                                        \
4538         sfunc(&binexpr->binary);                                              \
4539                                                                           \
4540         return binexpr;                                                       \
4541 }
4542
4543 CREATE_BINEXPR_PARSER(',', EXPR_BINARY_COMMA,    semantic_comma, 1)
4544 CREATE_BINEXPR_PARSER('*', EXPR_BINARY_MUL,      semantic_binexpr_arithmetic, 1)
4545 CREATE_BINEXPR_PARSER('/', EXPR_BINARY_DIV,      semantic_binexpr_arithmetic, 1)
4546 CREATE_BINEXPR_PARSER('%', EXPR_BINARY_MOD,      semantic_binexpr_arithmetic, 1)
4547 CREATE_BINEXPR_PARSER('+', EXPR_BINARY_ADD,      semantic_add, 1)
4548 CREATE_BINEXPR_PARSER('-', EXPR_BINARY_SUB,      semantic_sub, 1)
4549 CREATE_BINEXPR_PARSER('<', EXPR_BINARY_LESS,     semantic_comparison, 1)
4550 CREATE_BINEXPR_PARSER('>', EXPR_BINARY_GREATER,  semantic_comparison, 1)
4551 CREATE_BINEXPR_PARSER('=', EXPR_BINARY_ASSIGN,   semantic_binexpr_assign, 0)
4552
4553 CREATE_BINEXPR_PARSER(T_EQUALEQUAL,           EXPR_BINARY_EQUAL,
4554                       semantic_comparison, 1)
4555 CREATE_BINEXPR_PARSER(T_EXCLAMATIONMARKEQUAL, EXPR_BINARY_NOTEQUAL,
4556                       semantic_comparison, 1)
4557 CREATE_BINEXPR_PARSER(T_LESSEQUAL,            EXPR_BINARY_LESSEQUAL,
4558                       semantic_comparison, 1)
4559 CREATE_BINEXPR_PARSER(T_GREATEREQUAL,         EXPR_BINARY_GREATEREQUAL,
4560                       semantic_comparison, 1)
4561
4562 CREATE_BINEXPR_PARSER('&', EXPR_BINARY_BITWISE_AND,
4563                       semantic_binexpr_arithmetic, 1)
4564 CREATE_BINEXPR_PARSER('|', EXPR_BINARY_BITWISE_OR,
4565                       semantic_binexpr_arithmetic, 1)
4566 CREATE_BINEXPR_PARSER('^', EXPR_BINARY_BITWISE_XOR,
4567                       semantic_binexpr_arithmetic, 1)
4568 CREATE_BINEXPR_PARSER(T_ANDAND, EXPR_BINARY_LOGICAL_AND,
4569                       semantic_logical_op, 1)
4570 CREATE_BINEXPR_PARSER(T_PIPEPIPE, EXPR_BINARY_LOGICAL_OR,
4571                       semantic_logical_op, 1)
4572 CREATE_BINEXPR_PARSER(T_LESSLESS, EXPR_BINARY_SHIFTLEFT,
4573                       semantic_shift_op, 1)
4574 CREATE_BINEXPR_PARSER(T_GREATERGREATER, EXPR_BINARY_SHIFTRIGHT,
4575                       semantic_shift_op, 1)
4576 CREATE_BINEXPR_PARSER(T_PLUSEQUAL, EXPR_BINARY_ADD_ASSIGN,
4577                       semantic_arithmetic_addsubb_assign, 0)
4578 CREATE_BINEXPR_PARSER(T_MINUSEQUAL, EXPR_BINARY_SUB_ASSIGN,
4579                       semantic_arithmetic_addsubb_assign, 0)
4580 CREATE_BINEXPR_PARSER(T_ASTERISKEQUAL, EXPR_BINARY_MUL_ASSIGN,
4581                       semantic_arithmetic_assign, 0)
4582 CREATE_BINEXPR_PARSER(T_SLASHEQUAL, EXPR_BINARY_DIV_ASSIGN,
4583                       semantic_arithmetic_assign, 0)
4584 CREATE_BINEXPR_PARSER(T_PERCENTEQUAL, EXPR_BINARY_MOD_ASSIGN,
4585                       semantic_arithmetic_assign, 0)
4586 CREATE_BINEXPR_PARSER(T_LESSLESSEQUAL, EXPR_BINARY_SHIFTLEFT_ASSIGN,
4587                       semantic_arithmetic_assign, 0)
4588 CREATE_BINEXPR_PARSER(T_GREATERGREATEREQUAL, EXPR_BINARY_SHIFTRIGHT_ASSIGN,
4589                       semantic_arithmetic_assign, 0)
4590 CREATE_BINEXPR_PARSER(T_ANDEQUAL, EXPR_BINARY_BITWISE_AND_ASSIGN,
4591                       semantic_arithmetic_assign, 0)
4592 CREATE_BINEXPR_PARSER(T_PIPEEQUAL, EXPR_BINARY_BITWISE_OR_ASSIGN,
4593                       semantic_arithmetic_assign, 0)
4594 CREATE_BINEXPR_PARSER(T_CARETEQUAL, EXPR_BINARY_BITWISE_XOR_ASSIGN,
4595                       semantic_arithmetic_assign, 0)
4596
4597 static expression_t *parse_sub_expression(unsigned precedence)
4598 {
4599         if(token.type < 0) {
4600                 return expected_expression_error();
4601         }
4602
4603         expression_parser_function_t *parser
4604                 = &expression_parsers[token.type];
4605         source_position_t             source_position = token.source_position;
4606         expression_t                 *left;
4607
4608         if(parser->parser != NULL) {
4609                 left = parser->parser(parser->precedence);
4610         } else {
4611                 left = parse_primary_expression();
4612         }
4613         assert(left != NULL);
4614         left->base.source_position = source_position;
4615
4616         while(true) {
4617                 if(token.type < 0) {
4618                         return expected_expression_error();
4619                 }
4620
4621                 parser = &expression_parsers[token.type];
4622                 if(parser->infix_parser == NULL)
4623                         break;
4624                 if(parser->infix_precedence < precedence)
4625                         break;
4626
4627                 left = parser->infix_parser(parser->infix_precedence, left);
4628
4629                 assert(left != NULL);
4630                 assert(left->kind != EXPR_UNKNOWN);
4631                 left->base.source_position = source_position;
4632         }
4633
4634         return left;
4635 }
4636
4637 /**
4638  * Parse an expression.
4639  */
4640 static expression_t *parse_expression(void)
4641 {
4642         return parse_sub_expression(1);
4643 }
4644
4645 /**
4646  * Register a parser for a prefix-like operator with given precedence.
4647  *
4648  * @param parser      the parser function
4649  * @param token_type  the token type of the prefix token
4650  * @param precedence  the precedence of the operator
4651  */
4652 static void register_expression_parser(parse_expression_function parser,
4653                                        int token_type, unsigned precedence)
4654 {
4655         expression_parser_function_t *entry = &expression_parsers[token_type];
4656
4657         if(entry->parser != NULL) {
4658                 diagnosticf("for token '%k'\n", (token_type_t)token_type);
4659                 panic("trying to register multiple expression parsers for a token");
4660         }
4661         entry->parser     = parser;
4662         entry->precedence = precedence;
4663 }
4664
4665 /**
4666  * Register a parser for an infix operator with given precedence.
4667  *
4668  * @param parser      the parser function
4669  * @param token_type  the token type of the infix operator
4670  * @param precedence  the precedence of the operator
4671  */
4672 static void register_infix_parser(parse_expression_infix_function parser,
4673                 int token_type, unsigned precedence)
4674 {
4675         expression_parser_function_t *entry = &expression_parsers[token_type];
4676
4677         if(entry->infix_parser != NULL) {
4678                 diagnosticf("for token '%k'\n", (token_type_t)token_type);
4679                 panic("trying to register multiple infix expression parsers for a "
4680                       "token");
4681         }
4682         entry->infix_parser     = parser;
4683         entry->infix_precedence = precedence;
4684 }
4685
4686 /**
4687  * Initialize the expression parsers.
4688  */
4689 static void init_expression_parsers(void)
4690 {
4691         memset(&expression_parsers, 0, sizeof(expression_parsers));
4692
4693         register_infix_parser(parse_array_expression,         '[',              30);
4694         register_infix_parser(parse_call_expression,          '(',              30);
4695         register_infix_parser(parse_select_expression,        '.',              30);
4696         register_infix_parser(parse_select_expression,        T_MINUSGREATER,   30);
4697         register_infix_parser(parse_EXPR_UNARY_POSTFIX_INCREMENT,
4698                                                               T_PLUSPLUS,       30);
4699         register_infix_parser(parse_EXPR_UNARY_POSTFIX_DECREMENT,
4700                                                               T_MINUSMINUS,     30);
4701
4702         register_infix_parser(parse_EXPR_BINARY_MUL,          '*',              16);
4703         register_infix_parser(parse_EXPR_BINARY_DIV,          '/',              16);
4704         register_infix_parser(parse_EXPR_BINARY_MOD,          '%',              16);
4705         register_infix_parser(parse_EXPR_BINARY_SHIFTLEFT,    T_LESSLESS,       16);
4706         register_infix_parser(parse_EXPR_BINARY_SHIFTRIGHT,   T_GREATERGREATER, 16);
4707         register_infix_parser(parse_EXPR_BINARY_ADD,          '+',              15);
4708         register_infix_parser(parse_EXPR_BINARY_SUB,          '-',              15);
4709         register_infix_parser(parse_EXPR_BINARY_LESS,         '<',              14);
4710         register_infix_parser(parse_EXPR_BINARY_GREATER,      '>',              14);
4711         register_infix_parser(parse_EXPR_BINARY_LESSEQUAL,    T_LESSEQUAL,      14);
4712         register_infix_parser(parse_EXPR_BINARY_GREATEREQUAL, T_GREATEREQUAL,   14);
4713         register_infix_parser(parse_EXPR_BINARY_EQUAL,        T_EQUALEQUAL,     13);
4714         register_infix_parser(parse_EXPR_BINARY_NOTEQUAL,
4715                                                     T_EXCLAMATIONMARKEQUAL, 13);
4716         register_infix_parser(parse_EXPR_BINARY_BITWISE_AND,  '&',              12);
4717         register_infix_parser(parse_EXPR_BINARY_BITWISE_XOR,  '^',              11);
4718         register_infix_parser(parse_EXPR_BINARY_BITWISE_OR,   '|',              10);
4719         register_infix_parser(parse_EXPR_BINARY_LOGICAL_AND,  T_ANDAND,          9);
4720         register_infix_parser(parse_EXPR_BINARY_LOGICAL_OR,   T_PIPEPIPE,        8);
4721         register_infix_parser(parse_conditional_expression,   '?',               7);
4722         register_infix_parser(parse_EXPR_BINARY_ASSIGN,       '=',               2);
4723         register_infix_parser(parse_EXPR_BINARY_ADD_ASSIGN,   T_PLUSEQUAL,       2);
4724         register_infix_parser(parse_EXPR_BINARY_SUB_ASSIGN,   T_MINUSEQUAL,      2);
4725         register_infix_parser(parse_EXPR_BINARY_MUL_ASSIGN,   T_ASTERISKEQUAL,   2);
4726         register_infix_parser(parse_EXPR_BINARY_DIV_ASSIGN,   T_SLASHEQUAL,      2);
4727         register_infix_parser(parse_EXPR_BINARY_MOD_ASSIGN,   T_PERCENTEQUAL,    2);
4728         register_infix_parser(parse_EXPR_BINARY_SHIFTLEFT_ASSIGN,
4729                                                                 T_LESSLESSEQUAL, 2);
4730         register_infix_parser(parse_EXPR_BINARY_SHIFTRIGHT_ASSIGN,
4731                                                           T_GREATERGREATEREQUAL, 2);
4732         register_infix_parser(parse_EXPR_BINARY_BITWISE_AND_ASSIGN,
4733                                                                      T_ANDEQUAL, 2);
4734         register_infix_parser(parse_EXPR_BINARY_BITWISE_OR_ASSIGN,
4735                                                                     T_PIPEEQUAL, 2);
4736         register_infix_parser(parse_EXPR_BINARY_BITWISE_XOR_ASSIGN,
4737                                                                    T_CARETEQUAL, 2);
4738
4739         register_infix_parser(parse_EXPR_BINARY_COMMA,        ',',               1);
4740
4741         register_expression_parser(parse_EXPR_UNARY_NEGATE,           '-',      25);
4742         register_expression_parser(parse_EXPR_UNARY_PLUS,             '+',      25);
4743         register_expression_parser(parse_EXPR_UNARY_NOT,              '!',      25);
4744         register_expression_parser(parse_EXPR_UNARY_BITWISE_NEGATE,   '~',      25);
4745         register_expression_parser(parse_EXPR_UNARY_DEREFERENCE,      '*',      25);
4746         register_expression_parser(parse_EXPR_UNARY_TAKE_ADDRESS,     '&',      25);
4747         register_expression_parser(parse_EXPR_UNARY_PREFIX_INCREMENT,
4748                                                                   T_PLUSPLUS,   25);
4749         register_expression_parser(parse_EXPR_UNARY_PREFIX_DECREMENT,
4750                                                                   T_MINUSMINUS, 25);
4751         register_expression_parser(parse_sizeof,                  T_sizeof,     25);
4752         register_expression_parser(parse_extension,            T___extension__, 25);
4753         register_expression_parser(parse_builtin_classify_type,
4754                                                      T___builtin_classify_type, 25);
4755 }
4756
4757 /**
4758  * Parse a asm statement constraints specification.
4759  */
4760 static asm_constraint_t *parse_asm_constraints(void)
4761 {
4762         asm_constraint_t *result = NULL;
4763         asm_constraint_t *last   = NULL;
4764
4765         while(token.type == T_STRING_LITERAL || token.type == '[') {
4766                 asm_constraint_t *constraint = allocate_ast_zero(sizeof(constraint[0]));
4767                 memset(constraint, 0, sizeof(constraint[0]));
4768
4769                 if(token.type == '[') {
4770                         eat('[');
4771                         if(token.type != T_IDENTIFIER) {
4772                                 parse_error_expected("while parsing asm constraint",
4773                                                      T_IDENTIFIER, 0);
4774                                 return NULL;
4775                         }
4776                         constraint->symbol = token.v.symbol;
4777
4778                         expect(']');
4779                 }
4780
4781                 constraint->constraints = parse_string_literals();
4782                 expect('(');
4783                 constraint->expression = parse_expression();
4784                 expect(')');
4785
4786                 if(last != NULL) {
4787                         last->next = constraint;
4788                 } else {
4789                         result = constraint;
4790                 }
4791                 last = constraint;
4792
4793                 if(token.type != ',')
4794                         break;
4795                 eat(',');
4796         }
4797
4798         return result;
4799 }
4800
4801 /**
4802  * Parse a asm statement clobber specification.
4803  */
4804 static asm_clobber_t *parse_asm_clobbers(void)
4805 {
4806         asm_clobber_t *result = NULL;
4807         asm_clobber_t *last   = NULL;
4808
4809         while(token.type == T_STRING_LITERAL) {
4810                 asm_clobber_t *clobber = allocate_ast_zero(sizeof(clobber[0]));
4811                 clobber->clobber       = parse_string_literals();
4812
4813                 if(last != NULL) {
4814                         last->next = clobber;
4815                 } else {
4816                         result = clobber;
4817                 }
4818                 last = clobber;
4819
4820                 if(token.type != ',')
4821                         break;
4822                 eat(',');
4823         }
4824
4825         return result;
4826 }
4827
4828 /**
4829  * Parse an asm statement.
4830  */
4831 static statement_t *parse_asm_statement(void)
4832 {
4833         eat(T_asm);
4834
4835         statement_t *statement          = allocate_statement_zero(STATEMENT_ASM);
4836         statement->base.source_position = token.source_position;
4837
4838         asm_statement_t *asm_statement = &statement->asms;
4839
4840         if(token.type == T_volatile) {
4841                 next_token();
4842                 asm_statement->is_volatile = true;
4843         }
4844
4845         expect('(');
4846         asm_statement->asm_text = parse_string_literals();
4847
4848         if(token.type != ':')
4849                 goto end_of_asm;
4850         eat(':');
4851
4852         asm_statement->inputs = parse_asm_constraints();
4853         if(token.type != ':')
4854                 goto end_of_asm;
4855         eat(':');
4856
4857         asm_statement->outputs = parse_asm_constraints();
4858         if(token.type != ':')
4859                 goto end_of_asm;
4860         eat(':');
4861
4862         asm_statement->clobbers = parse_asm_clobbers();
4863
4864 end_of_asm:
4865         expect(')');
4866         expect(';');
4867         return statement;
4868 }
4869
4870 /**
4871  * Parse a case statement.
4872  */
4873 static statement_t *parse_case_statement(void)
4874 {
4875         eat(T_case);
4876
4877         statement_t *statement = allocate_statement_zero(STATEMENT_CASE_LABEL);
4878
4879         statement->base.source_position  = token.source_position;
4880         statement->case_label.expression = parse_expression();
4881
4882         expect(':');
4883
4884         if (! is_constant_expression(statement->case_label.expression)) {
4885                 errorf(statement->base.source_position,
4886                         "case label does not reduce to an integer constant");
4887         } else {
4888                 /* TODO: check if the case label is already known */
4889                 if (current_switch != NULL) {
4890                         /* link all cases into the switch statement */
4891                         if (current_switch->last_case == NULL) {
4892                                 current_switch->first_case =
4893                                 current_switch->last_case  = &statement->case_label;
4894                         } else {
4895                                 current_switch->last_case->next = &statement->case_label;
4896                         }
4897                 } else {
4898                         errorf(statement->base.source_position,
4899                                 "case label not within a switch statement");
4900                 }
4901         }
4902         statement->case_label.label_statement = parse_statement();
4903
4904         return statement;
4905 }
4906
4907 /**
4908  * Finds an existing default label of a switch statement.
4909  */
4910 static case_label_statement_t *
4911 find_default_label(const switch_statement_t *statement)
4912 {
4913         for (case_label_statement_t *label = statement->first_case;
4914              label != NULL;
4915                  label = label->next) {
4916                 if (label->expression == NULL)
4917                         return label;
4918         }
4919         return NULL;
4920 }
4921
4922 /**
4923  * Parse a default statement.
4924  */
4925 static statement_t *parse_default_statement(void)
4926 {
4927         eat(T_default);
4928
4929         statement_t *statement = allocate_statement_zero(STATEMENT_CASE_LABEL);
4930
4931         statement->base.source_position = token.source_position;
4932
4933         expect(':');
4934         if (current_switch != NULL) {
4935                 const case_label_statement_t *def_label = find_default_label(current_switch);
4936                 if (def_label != NULL) {
4937                         errorf(HERE, "multiple default labels in one switch");
4938                         errorf(def_label->statement.source_position,
4939                                 "this is the first default label");
4940                 } else {
4941                         /* link all cases into the switch statement */
4942                         if (current_switch->last_case == NULL) {
4943                                 current_switch->first_case =
4944                                         current_switch->last_case  = &statement->case_label;
4945                         } else {
4946                                 current_switch->last_case->next = &statement->case_label;
4947                         }
4948                 }
4949         } else {
4950                 errorf(statement->base.source_position,
4951                         "'default' label not within a switch statement");
4952         }
4953         statement->label.label_statement = parse_statement();
4954
4955         return statement;
4956 }
4957
4958 /**
4959  * Return the declaration for a given label symbol or create a new one.
4960  */
4961 static declaration_t *get_label(symbol_t *symbol)
4962 {
4963         declaration_t *candidate = get_declaration(symbol, NAMESPACE_LABEL);
4964         assert(current_function != NULL);
4965         /* if we found a label in the same function, then we already created the
4966          * declaration */
4967         if(candidate != NULL
4968                         && candidate->parent_context == &current_function->context) {
4969                 return candidate;
4970         }
4971
4972         /* otherwise we need to create a new one */
4973         declaration_t *const declaration = allocate_declaration_zero();
4974         declaration->namespc       = NAMESPACE_LABEL;
4975         declaration->symbol        = symbol;
4976
4977         label_push(declaration);
4978
4979         return declaration;
4980 }
4981
4982 /**
4983  * Parse a label statement.
4984  */
4985 static statement_t *parse_label_statement(void)
4986 {
4987         assert(token.type == T_IDENTIFIER);
4988         symbol_t *symbol = token.v.symbol;
4989         next_token();
4990
4991         declaration_t *label = get_label(symbol);
4992
4993         /* if source position is already set then the label is defined twice,
4994          * otherwise it was just mentioned in a goto so far */
4995         if(label->source_position.input_name != NULL) {
4996                 errorf(HERE, "duplicate label '%Y'", symbol);
4997                 errorf(label->source_position, "previous definition of '%Y' was here",
4998                        symbol);
4999         } else {
5000                 label->source_position = token.source_position;
5001         }
5002
5003         label_statement_t *label_statement = allocate_ast_zero(sizeof(label[0]));
5004
5005         label_statement->statement.kind            = STATEMENT_LABEL;
5006         label_statement->statement.source_position = token.source_position;
5007         label_statement->label                     = label;
5008
5009         eat(':');
5010
5011         if(token.type == '}') {
5012                 /* TODO only warn? */
5013                 errorf(HERE, "label at end of compound statement");
5014                 return (statement_t*) label_statement;
5015         } else {
5016                 label_statement->label_statement = parse_statement();
5017         }
5018
5019         return (statement_t*) label_statement;
5020 }
5021
5022 /**
5023  * Parse an if statement.
5024  */
5025 static statement_t *parse_if(void)
5026 {
5027         eat(T_if);
5028
5029         if_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5030         statement->statement.kind            = STATEMENT_IF;
5031         statement->statement.source_position = token.source_position;
5032
5033         expect('(');
5034         statement->condition = parse_expression();
5035         expect(')');
5036
5037         statement->true_statement = parse_statement();
5038         if(token.type == T_else) {
5039                 next_token();
5040                 statement->false_statement = parse_statement();
5041         }
5042
5043         return (statement_t*) statement;
5044 }
5045
5046 /**
5047  * Parse a switch statement.
5048  */
5049 static statement_t *parse_switch(void)
5050 {
5051         eat(T_switch);
5052
5053         switch_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5054         statement->statement.kind            = STATEMENT_SWITCH;
5055         statement->statement.source_position = token.source_position;
5056
5057         expect('(');
5058         expression_t *const expr = parse_expression();
5059         type_t       *const type = promote_integer(skip_typeref(expr->base.datatype));
5060         statement->expression = create_implicit_cast(expr, type);
5061         expect(')');
5062
5063         switch_statement_t *rem = current_switch;
5064         current_switch  = statement;
5065         statement->body = parse_statement();
5066         current_switch  = rem;
5067
5068         return (statement_t*) statement;
5069 }
5070
5071 static statement_t *parse_loop_body(statement_t *const loop)
5072 {
5073         statement_t *const rem = current_loop;
5074         current_loop = loop;
5075         statement_t *const body = parse_statement();
5076         current_loop = rem;
5077         return body;
5078 }
5079
5080 /**
5081  * Parse a while statement.
5082  */
5083 static statement_t *parse_while(void)
5084 {
5085         eat(T_while);
5086
5087         while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5088         statement->statement.kind            = STATEMENT_WHILE;
5089         statement->statement.source_position = token.source_position;
5090
5091         expect('(');
5092         statement->condition = parse_expression();
5093         expect(')');
5094
5095         statement->body = parse_loop_body((statement_t*)statement);
5096
5097         return (statement_t*) statement;
5098 }
5099
5100 /**
5101  * Parse a do statement.
5102  */
5103 static statement_t *parse_do(void)
5104 {
5105         eat(T_do);
5106
5107         do_while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5108         statement->statement.kind            = STATEMENT_DO_WHILE;
5109         statement->statement.source_position = token.source_position;
5110
5111         statement->body = parse_loop_body((statement_t*)statement);
5112         expect(T_while);
5113         expect('(');
5114         statement->condition = parse_expression();
5115         expect(')');
5116         expect(';');
5117
5118         return (statement_t*) statement;
5119 }
5120
5121 /**
5122  * Parse a for statement.
5123  */
5124 static statement_t *parse_for(void)
5125 {
5126         eat(T_for);
5127
5128         for_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5129         statement->statement.kind            = STATEMENT_FOR;
5130         statement->statement.source_position = token.source_position;
5131
5132         expect('(');
5133
5134         int         top          = environment_top();
5135         context_t  *last_context = context;
5136         set_context(&statement->context);
5137
5138         if(token.type != ';') {
5139                 if(is_declaration_specifier(&token, false)) {
5140                         parse_declaration(record_declaration);
5141                 } else {
5142                         statement->initialisation = parse_expression();
5143                         expect(';');
5144                 }
5145         } else {
5146                 expect(';');
5147         }
5148
5149         if(token.type != ';') {
5150                 statement->condition = parse_expression();
5151         }
5152         expect(';');
5153         if(token.type != ')') {
5154                 statement->step = parse_expression();
5155         }
5156         expect(')');
5157         statement->body = parse_loop_body((statement_t*)statement);
5158
5159         assert(context == &statement->context);
5160         set_context(last_context);
5161         environment_pop_to(top);
5162
5163         return (statement_t*) statement;
5164 }
5165
5166 /**
5167  * Parse a goto statement.
5168  */
5169 static statement_t *parse_goto(void)
5170 {
5171         eat(T_goto);
5172
5173         if(token.type != T_IDENTIFIER) {
5174                 parse_error_expected("while parsing goto", T_IDENTIFIER, 0);
5175                 eat_statement();
5176                 return NULL;
5177         }
5178         symbol_t *symbol = token.v.symbol;
5179         next_token();
5180
5181         declaration_t *label = get_label(symbol);
5182
5183         goto_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5184
5185         statement->statement.kind            = STATEMENT_GOTO;
5186         statement->statement.source_position = token.source_position;
5187
5188         statement->label = label;
5189
5190         /* remember the goto's in a list for later checking */
5191         if (goto_last == NULL) {
5192                 goto_first = goto_last = statement;
5193         } else {
5194                 goto_last->next = statement;
5195         }
5196
5197         expect(';');
5198
5199         return (statement_t*) statement;
5200 }
5201
5202 /**
5203  * Parse a continue statement.
5204  */
5205 static statement_t *parse_continue(void)
5206 {
5207         statement_t *statement;
5208         if (current_loop == NULL) {
5209                 errorf(HERE, "continue statement not within loop");
5210                 statement = NULL;
5211         } else {
5212                 statement = allocate_statement_zero(STATEMENT_CONTINUE);
5213
5214                 statement->base.source_position = token.source_position;
5215         }
5216
5217         eat(T_continue);
5218         expect(';');
5219
5220         return statement;
5221 }
5222
5223 /**
5224  * Parse a break statement.
5225  */
5226 static statement_t *parse_break(void)
5227 {
5228         statement_t *statement;
5229         if (current_switch == NULL && current_loop == NULL) {
5230                 errorf(HERE, "break statement not within loop or switch");
5231                 statement = NULL;
5232         } else {
5233                 statement = allocate_statement_zero(STATEMENT_BREAK);
5234
5235                 statement->base.source_position = token.source_position;
5236         }
5237
5238         eat(T_break);
5239         expect(';');
5240
5241         return statement;
5242 }
5243
5244 /**
5245  * Check if a given declaration represents a local variable.
5246  */
5247 static bool is_local_var_declaration(const declaration_t *declaration) {
5248         switch ((storage_class_tag_t) declaration->storage_class) {
5249         case STORAGE_CLASS_NONE:
5250         case STORAGE_CLASS_AUTO:
5251         case STORAGE_CLASS_REGISTER: {
5252                 const type_t *type = skip_typeref(declaration->type);
5253                 if(is_type_function(type)) {
5254                         return false;
5255                 } else {
5256                         return true;
5257                 }
5258         }
5259         default:
5260                 return false;
5261         }
5262 }
5263
5264 /**
5265  * Check if a given expression represents a local variable.
5266  */
5267 static bool is_local_variable(const expression_t *expression)
5268 {
5269         if (expression->base.kind != EXPR_REFERENCE) {
5270                 return false;
5271         }
5272         const declaration_t *declaration = expression->reference.declaration;
5273         return is_local_var_declaration(declaration);
5274 }
5275
5276 /**
5277  * Parse a return statement.
5278  */
5279 static statement_t *parse_return(void)
5280 {
5281         eat(T_return);
5282
5283         return_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5284
5285         statement->statement.kind            = STATEMENT_RETURN;
5286         statement->statement.source_position = token.source_position;
5287
5288         assert(is_type_function(current_function->type));
5289         function_type_t *function_type = &current_function->type->function;
5290         type_t          *return_type   = function_type->return_type;
5291
5292         expression_t *return_value = NULL;
5293         if(token.type != ';') {
5294                 return_value = parse_expression();
5295         }
5296         expect(';');
5297
5298         if(return_type == NULL)
5299                 return (statement_t*) statement;
5300         if(return_value != NULL && return_value->base.datatype == NULL)
5301                 return (statement_t*) statement;
5302
5303         return_type = skip_typeref(return_type);
5304
5305         if(return_value != NULL) {
5306                 type_t *return_value_type = skip_typeref(return_value->base.datatype);
5307
5308                 if(is_type_atomic(return_type, ATOMIC_TYPE_VOID)
5309                                 && !is_type_atomic(return_value_type, ATOMIC_TYPE_VOID)) {
5310                         warningf(statement->statement.source_position,
5311                                 "'return' with a value, in function returning void");
5312                         return_value = NULL;
5313                 } else {
5314                         if(return_type != NULL) {
5315                                 semantic_assign(return_type, &return_value, "'return'");
5316                         }
5317                 }
5318                 /* check for returning address of a local var */
5319                 if (return_value->base.kind == EXPR_UNARY_TAKE_ADDRESS) {
5320                         const expression_t *expression = return_value->unary.value;
5321                         if (is_local_variable(expression)) {
5322                                 warningf(statement->statement.source_position,
5323                                         "function returns address of local variable");
5324                         }
5325                 }
5326         } else {
5327                 if(!is_type_atomic(return_type, ATOMIC_TYPE_VOID)) {
5328                         warningf(statement->statement.source_position,
5329                                 "'return' without value, in function returning non-void");
5330                 }
5331         }
5332         statement->return_value = return_value;
5333
5334         return (statement_t*) statement;
5335 }
5336
5337 /**
5338  * Parse a declaration statement.
5339  */
5340 static statement_t *parse_declaration_statement(void)
5341 {
5342         statement_t *statement = allocate_statement_zero(STATEMENT_DECLARATION);
5343
5344         statement->base.source_position = token.source_position;
5345
5346         declaration_t *before = last_declaration;
5347         parse_declaration(record_declaration);
5348
5349         if(before == NULL) {
5350                 statement->declaration.declarations_begin = context->declarations;
5351         } else {
5352                 statement->declaration.declarations_begin = before->next;
5353         }
5354         statement->declaration.declarations_end = last_declaration;
5355
5356         return statement;
5357 }
5358
5359 /**
5360  * Parse an expression statement, ie. expr ';'.
5361  */
5362 static statement_t *parse_expression_statement(void)
5363 {
5364         statement_t *statement = allocate_statement_zero(STATEMENT_EXPRESSION);
5365
5366         statement->base.source_position  = token.source_position;
5367         statement->expression.expression = parse_expression();
5368
5369         expect(';');
5370
5371         return statement;
5372 }
5373
5374 /**
5375  * Parse a statement.
5376  */
5377 static statement_t *parse_statement(void)
5378 {
5379         statement_t   *statement = NULL;
5380
5381         /* declaration or statement */
5382         switch(token.type) {
5383         case T_asm:
5384                 statement = parse_asm_statement();
5385                 break;
5386
5387         case T_case:
5388                 statement = parse_case_statement();
5389                 break;
5390
5391         case T_default:
5392                 statement = parse_default_statement();
5393                 break;
5394
5395         case '{':
5396                 statement = parse_compound_statement();
5397                 break;
5398
5399         case T_if:
5400                 statement = parse_if();
5401                 break;
5402
5403         case T_switch:
5404                 statement = parse_switch();
5405                 break;
5406
5407         case T_while:
5408                 statement = parse_while();
5409                 break;
5410
5411         case T_do:
5412                 statement = parse_do();
5413                 break;
5414
5415         case T_for:
5416                 statement = parse_for();
5417                 break;
5418
5419         case T_goto:
5420                 statement = parse_goto();
5421                 break;
5422
5423         case T_continue:
5424                 statement = parse_continue();
5425                 break;
5426
5427         case T_break:
5428                 statement = parse_break();
5429                 break;
5430
5431         case T_return:
5432                 statement = parse_return();
5433                 break;
5434
5435         case ';':
5436                 next_token();
5437                 statement = NULL;
5438                 break;
5439
5440         case T_IDENTIFIER:
5441                 if(look_ahead(1)->type == ':') {
5442                         statement = parse_label_statement();
5443                         break;
5444                 }
5445
5446                 if(is_typedef_symbol(token.v.symbol)) {
5447                         statement = parse_declaration_statement();
5448                         break;
5449                 }
5450
5451                 statement = parse_expression_statement();
5452                 break;
5453
5454         case T___extension__:
5455                 /* this can be a prefix to a declaration or an expression statement */
5456                 /* we simply eat it now and parse the rest with tail recursion */
5457                 do {
5458                         next_token();
5459                 } while(token.type == T___extension__);
5460                 statement = parse_statement();
5461                 break;
5462
5463         DECLARATION_START
5464                 statement = parse_declaration_statement();
5465                 break;
5466
5467         default:
5468                 statement = parse_expression_statement();
5469                 break;
5470         }
5471
5472         assert(statement == NULL
5473                         || statement->base.source_position.input_name != NULL);
5474
5475         return statement;
5476 }
5477
5478 /**
5479  * Parse a compound statement.
5480  */
5481 static statement_t *parse_compound_statement(void)
5482 {
5483         compound_statement_t *compound_statement
5484                 = allocate_ast_zero(sizeof(compound_statement[0]));
5485         compound_statement->statement.kind            = STATEMENT_COMPOUND;
5486         compound_statement->statement.source_position = token.source_position;
5487
5488         eat('{');
5489
5490         int        top          = environment_top();
5491         context_t *last_context = context;
5492         set_context(&compound_statement->context);
5493
5494         statement_t *last_statement = NULL;
5495
5496         while(token.type != '}' && token.type != T_EOF) {
5497                 statement_t *statement = parse_statement();
5498                 if(statement == NULL)
5499                         continue;
5500
5501                 if(last_statement != NULL) {
5502                         last_statement->base.next = statement;
5503                 } else {
5504                         compound_statement->statements = statement;
5505                 }
5506
5507                 while(statement->base.next != NULL)
5508                         statement = statement->base.next;
5509
5510                 last_statement = statement;
5511         }
5512
5513         if(token.type == '}') {
5514                 next_token();
5515         } else {
5516                 errorf(compound_statement->statement.source_position, "end of file while looking for closing '}'");
5517         }
5518
5519         assert(context == &compound_statement->context);
5520         set_context(last_context);
5521         environment_pop_to(top);
5522
5523         return (statement_t*) compound_statement;
5524 }
5525
5526 /**
5527  * Initialize builtin types.
5528  */
5529 static void initialize_builtin_types(void)
5530 {
5531         type_intmax_t    = make_global_typedef("__intmax_t__",      type_long_long);
5532         type_size_t      = make_global_typedef("__SIZE_TYPE__",     type_unsigned_long);
5533         type_ssize_t     = make_global_typedef("__SSIZE_TYPE__",    type_long);
5534         type_ptrdiff_t   = make_global_typedef("__PTRDIFF_TYPE__",  type_long);
5535         type_uintmax_t   = make_global_typedef("__uintmax_t__",     type_unsigned_long_long);
5536         type_uptrdiff_t  = make_global_typedef("__UPTRDIFF_TYPE__", type_unsigned_long);
5537         type_wchar_t     = make_global_typedef("__WCHAR_TYPE__",    type_int);
5538         type_wint_t      = make_global_typedef("__WINT_TYPE__",     type_int);
5539
5540         type_intmax_t_ptr  = make_pointer_type(type_intmax_t,  TYPE_QUALIFIER_NONE);
5541         type_ptrdiff_t_ptr = make_pointer_type(type_ptrdiff_t, TYPE_QUALIFIER_NONE);
5542         type_ssize_t_ptr   = make_pointer_type(type_ssize_t,   TYPE_QUALIFIER_NONE);
5543         type_wchar_t_ptr   = make_pointer_type(type_wchar_t,   TYPE_QUALIFIER_NONE);
5544 }
5545
5546 /**
5547  * Parse a translation unit.
5548  */
5549 static translation_unit_t *parse_translation_unit(void)
5550 {
5551         translation_unit_t *unit = allocate_ast_zero(sizeof(unit[0]));
5552
5553         assert(global_context == NULL);
5554         global_context = &unit->context;
5555
5556         assert(context == NULL);
5557         set_context(&unit->context);
5558
5559         initialize_builtin_types();
5560
5561         while(token.type != T_EOF) {
5562                 if (token.type == ';') {
5563                         /* TODO error in strict mode */
5564                         warningf(HERE, "stray ';' outside of function");
5565                         next_token();
5566                 } else {
5567                         parse_external_declaration();
5568                 }
5569         }
5570
5571         assert(context == &unit->context);
5572         context          = NULL;
5573         last_declaration = NULL;
5574
5575         assert(global_context == &unit->context);
5576         global_context = NULL;
5577
5578         return unit;
5579 }
5580
5581 /**
5582  * Parse the input.
5583  *
5584  * @return  the translation unit or NULL if errors occurred.
5585  */
5586 translation_unit_t *parse(void)
5587 {
5588         environment_stack = NEW_ARR_F(stack_entry_t, 0);
5589         label_stack       = NEW_ARR_F(stack_entry_t, 0);
5590         diagnostic_count  = 0;
5591         error_count       = 0;
5592         warning_count     = 0;
5593
5594         type_set_output(stderr);
5595         ast_set_output(stderr);
5596
5597         lookahead_bufpos = 0;
5598         for(int i = 0; i < MAX_LOOKAHEAD + 2; ++i) {
5599                 next_token();
5600         }
5601         translation_unit_t *unit = parse_translation_unit();
5602
5603         DEL_ARR_F(environment_stack);
5604         DEL_ARR_F(label_stack);
5605
5606         if(error_count > 0)
5607                 return NULL;
5608
5609         return unit;
5610 }
5611
5612 /**
5613  * Initialize the parser.
5614  */
5615 void init_parser(void)
5616 {
5617         init_expression_parsers();
5618         obstack_init(&temp_obst);
5619
5620         symbol_t *const va_list_sym = symbol_table_insert("__builtin_va_list");
5621         type_valist = create_builtin_type(va_list_sym, type_void_ptr);
5622 }
5623
5624 /**
5625  * Terminate the parser.
5626  */
5627 void exit_parser(void)
5628 {
5629         obstack_free(&temp_obst, NULL);
5630 }