nsz Git - cparser/blob - parser.c

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