nsz Git - cparser/blob - parser.c

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