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 static bool first_err = true;
2717
2718 /**
2719  * When called with first_err set, prints the name of the current function,
2720  * else does noting.
2721  */
2722 static void print_in_function(void) {
2723         if (first_err) {
2724                 first_err = false;
2725                 diagnosticf("%s: In function '%Y':\n",
2726                         current_function->source_position.input_name,
2727                         current_function->symbol);
2728         }
2729 }
2730
2731 /**
2732  * Check if all labels are defined in the current function.
2733  * Check if all labels are used in the current function.
2734  */
2735 static void check_labels(void)
2736 {
2737         for (const goto_statement_t *goto_statement = goto_first;
2738             goto_statement != NULL;
2739             goto_statement = goto_statement->next) {
2740                 declaration_t *label = goto_statement->label;
2741
2742                 label->used = true;
2743                 if (label->source_position.input_name == NULL) {
2744                         print_in_function();
2745                         errorf(goto_statement->statement.source_position,
2746                                 "label '%Y' used but not defined", label->symbol);
2747                  }
2748         }
2749         goto_first = goto_last = NULL;
2750
2751         if (warning.unused_label) {
2752                 for (const label_statement_t *label_statement = label_first;
2753                          label_statement != NULL;
2754                          label_statement = label_statement->next) {
2755                         const declaration_t *label = label_statement->label;
2756
2757                         if (! label->used) {
2758                                 print_in_function();
2759                                 warningf(label_statement->statement.source_position,
2760                                         "label '%Y' defined but not used", label->symbol);
2761                         }
2762                 }
2763         }
2764         label_first = label_last = NULL;
2765 }
2766
2767 /**
2768  * Check declarations of current_function for unused entities.
2769  */
2770 static void check_declarations(void)
2771 {
2772         if (warning.unused_parameter) {
2773                 const scope_t *scope = &current_function->scope;
2774
2775                 const declaration_t *parameter = scope->declarations;
2776                 for (; parameter != NULL; parameter = parameter->next) {
2777                         if (! parameter->used) {
2778                                 print_in_function();
2779                                 warningf(parameter->source_position,
2780                                         "unused parameter '%Y'", parameter->symbol);
2781                         }
2782                 }
2783         }
2784         if (warning.unused_variable) {
2785         }
2786 }
2787
2788 static void parse_external_declaration(void)
2789 {
2790         /* function-definitions and declarations both start with declaration
2791          * specifiers */
2792         declaration_specifiers_t specifiers;
2793         memset(&specifiers, 0, sizeof(specifiers));
2794         parse_declaration_specifiers(&specifiers);
2795
2796         /* must be a declaration */
2797         if(token.type == ';') {
2798                 parse_anonymous_declaration_rest(&specifiers, append_declaration);
2799                 return;
2800         }
2801
2802         /* declarator is common to both function-definitions and declarations */
2803         declaration_t *ndeclaration = parse_declarator(&specifiers, /*may_be_abstract=*/false);
2804
2805         /* must be a declaration */
2806         if(token.type == ',' || token.type == '=' || token.type == ';') {
2807                 parse_declaration_rest(ndeclaration, &specifiers, record_declaration);
2808                 return;
2809         }
2810
2811         /* must be a function definition */
2812         parse_kr_declaration_list(ndeclaration);
2813
2814         if(token.type != '{') {
2815                 parse_error_expected("while parsing function definition", '{', 0);
2816                 eat_statement();
2817                 return;
2818         }
2819
2820         type_t *type = ndeclaration->type;
2821
2822         /* note that we don't skip typerefs: the standard doesn't allow them here
2823          * (so we can't use is_type_function here) */
2824         if(type->kind != TYPE_FUNCTION) {
2825                 if (is_type_valid(type)) {
2826                         errorf(HERE, "declarator '%#T' has a body but is not a function type",
2827                                type, ndeclaration->symbol);
2828                 }
2829                 eat_block();
2830                 return;
2831         }
2832
2833         /* § 6.7.5.3 (14) a function definition with () means no
2834          * parameters (and not unspecified parameters) */
2835         if(type->function.unspecified_parameters) {
2836                 type_t *duplicate = duplicate_type(type);
2837                 duplicate->function.unspecified_parameters = false;
2838
2839                 type = typehash_insert(duplicate);
2840                 if(type != duplicate) {
2841                         obstack_free(type_obst, duplicate);
2842                 }
2843                 ndeclaration->type = type;
2844         }
2845
2846         declaration_t *const declaration = record_function_definition(ndeclaration);
2847         if(ndeclaration != declaration) {
2848                 declaration->scope = ndeclaration->scope;
2849         }
2850         type = skip_typeref(declaration->type);
2851
2852         /* push function parameters and switch scope */
2853         int       top        = environment_top();
2854         scope_t  *last_scope = scope;
2855         set_scope(&declaration->scope);
2856
2857         declaration_t *parameter = declaration->scope.declarations;
2858         for( ; parameter != NULL; parameter = parameter->next) {
2859                 if(parameter->parent_scope == &ndeclaration->scope) {
2860                         parameter->parent_scope = scope;
2861                 }
2862                 assert(parameter->parent_scope == NULL
2863                                 || parameter->parent_scope == scope);
2864                 parameter->parent_scope = scope;
2865                 environment_push(parameter);
2866         }
2867
2868         if(declaration->init.statement != NULL) {
2869                 parser_error_multiple_definition(declaration, token.source_position);
2870                 eat_block();
2871                 goto end_of_parse_external_declaration;
2872         } else {
2873                 /* parse function body */
2874                 int            label_stack_top      = label_top();
2875                 declaration_t *old_current_function = current_function;
2876                 current_function                    = declaration;
2877
2878                 declaration->init.statement = parse_compound_statement();
2879                 first_err = true;
2880                 check_labels();
2881                 check_declarations();
2882
2883                 assert(current_function == declaration);
2884                 current_function = old_current_function;
2885                 label_pop_to(label_stack_top);
2886         }
2887
2888 end_of_parse_external_declaration:
2889         assert(scope == &declaration->scope);
2890         set_scope(last_scope);
2891         environment_pop_to(top);
2892 }
2893
2894 static type_t *make_bitfield_type(type_t *base, expression_t *size)
2895 {
2896         type_t *type        = allocate_type_zero(TYPE_BITFIELD);
2897         type->bitfield.base = base;
2898         type->bitfield.size = size;
2899
2900         return type;
2901 }
2902
2903 static void parse_struct_declarators(const declaration_specifiers_t *specifiers)
2904 {
2905         /* TODO: check constraints for struct declarations (in specifiers) */
2906         while(1) {
2907                 declaration_t *declaration;
2908
2909                 if(token.type == ':') {
2910                         next_token();
2911
2912                         type_t *base_type = specifiers->type;
2913                         expression_t *size = parse_constant_expression();
2914
2915                         type_t *type = make_bitfield_type(base_type, size);
2916
2917                         declaration = allocate_declaration_zero();
2918                         declaration->namespc         = NAMESPACE_NORMAL;
2919                         declaration->storage_class   = STORAGE_CLASS_NONE;
2920                         declaration->source_position = token.source_position;
2921                         declaration->modifiers       = specifiers->decl_modifiers;
2922                         declaration->type            = type;
2923                 } else {
2924                         declaration = parse_declarator(specifiers,/*may_be_abstract=*/true);
2925
2926                         if(token.type == ':') {
2927                                 next_token();
2928                                 expression_t *size = parse_constant_expression();
2929
2930                                 type_t *type = make_bitfield_type(declaration->type, size);
2931                                 declaration->type = type;
2932                         }
2933                 }
2934                 record_declaration(declaration);
2935
2936                 if(token.type != ',')
2937                         break;
2938                 next_token();
2939         }
2940         expect_void(';');
2941 }
2942
2943 static void parse_compound_type_entries(void)
2944 {
2945         eat('{');
2946
2947         while(token.type != '}' && token.type != T_EOF) {
2948                 declaration_specifiers_t specifiers;
2949                 memset(&specifiers, 0, sizeof(specifiers));
2950                 parse_declaration_specifiers(&specifiers);
2951
2952                 parse_struct_declarators(&specifiers);
2953         }
2954         if(token.type == T_EOF) {
2955                 errorf(HERE, "EOF while parsing struct");
2956         }
2957         next_token();
2958 }
2959
2960 static type_t *parse_typename(void)
2961 {
2962         declaration_specifiers_t specifiers;
2963         memset(&specifiers, 0, sizeof(specifiers));
2964         parse_declaration_specifiers(&specifiers);
2965         if(specifiers.storage_class != STORAGE_CLASS_NONE) {
2966                 /* TODO: improve error message, user does probably not know what a
2967                  * storage class is...
2968                  */
2969                 errorf(HERE, "typename may not have a storage class");
2970         }
2971
2972         type_t *result = parse_abstract_declarator(specifiers.type);
2973
2974         return result;
2975 }
2976
2977
2978
2979
2980 typedef expression_t* (*parse_expression_function) (unsigned precedence);
2981 typedef expression_t* (*parse_expression_infix_function) (unsigned precedence,
2982                                                           expression_t *left);
2983
2984 typedef struct expression_parser_function_t expression_parser_function_t;
2985 struct expression_parser_function_t {
2986         unsigned                         precedence;
2987         parse_expression_function        parser;
2988         unsigned                         infix_precedence;
2989         parse_expression_infix_function  infix_parser;
2990 };
2991
2992 expression_parser_function_t expression_parsers[T_LAST_TOKEN];
2993
2994 /**
2995  * Creates a new invalid expression.
2996  */
2997 static expression_t *create_invalid_expression(void)
2998 {
2999         expression_t *expression         = allocate_expression_zero(EXPR_INVALID);
3000         expression->base.source_position = token.source_position;
3001         return expression;
3002 }
3003
3004 /**
3005  * Prints an error message if an expression was expected but not read
3006  */
3007 static expression_t *expected_expression_error(void)
3008 {
3009         /* skip the error message if the error token was read */
3010         if (token.type != T_ERROR) {
3011                 errorf(HERE, "expected expression, got token '%K'", &token);
3012         }
3013         next_token();
3014
3015         return create_invalid_expression();
3016 }
3017
3018 /**
3019  * Parse a string constant.
3020  */
3021 static expression_t *parse_string_const(void)
3022 {
3023         expression_t *cnst  = allocate_expression_zero(EXPR_STRING_LITERAL);
3024         cnst->base.datatype = type_string;
3025         cnst->string.value  = parse_string_literals();
3026
3027         return cnst;
3028 }
3029
3030 /**
3031  * Parse a wide string constant.
3032  */
3033 static expression_t *parse_wide_string_const(void)
3034 {
3035         expression_t *const cnst = allocate_expression_zero(EXPR_WIDE_STRING_LITERAL);
3036         cnst->base.datatype      = type_wchar_t_ptr;
3037         cnst->wide_string.value  = token.v.wide_string; /* TODO concatenate */
3038         next_token();
3039         return cnst;
3040 }
3041
3042 /**
3043  * Parse an integer constant.
3044  */
3045 static expression_t *parse_int_const(void)
3046 {
3047         expression_t *cnst       = allocate_expression_zero(EXPR_CONST);
3048         cnst->base.datatype      = token.datatype;
3049         cnst->conste.v.int_value = token.v.intvalue;
3050
3051         next_token();
3052
3053         return cnst;
3054 }
3055
3056 /**
3057  * Parse a float constant.
3058  */
3059 static expression_t *parse_float_const(void)
3060 {
3061         expression_t *cnst         = allocate_expression_zero(EXPR_CONST);
3062         cnst->base.datatype        = token.datatype;
3063         cnst->conste.v.float_value = token.v.floatvalue;
3064
3065         next_token();
3066
3067         return cnst;
3068 }
3069
3070 static declaration_t *create_implicit_function(symbol_t *symbol,
3071                 const source_position_t source_position)
3072 {
3073         type_t *ntype                          = allocate_type_zero(TYPE_FUNCTION);
3074         ntype->function.return_type            = type_int;
3075         ntype->function.unspecified_parameters = true;
3076
3077         type_t *type = typehash_insert(ntype);
3078         if(type != ntype) {
3079                 free_type(ntype);
3080         }
3081
3082         declaration_t *const declaration = allocate_declaration_zero();
3083         declaration->storage_class   = STORAGE_CLASS_EXTERN;
3084         declaration->type            = type;
3085         declaration->symbol          = symbol;
3086         declaration->source_position = source_position;
3087         declaration->parent_scope  = global_scope;
3088
3089         scope_t *old_scope = scope;
3090         set_scope(global_scope);
3091
3092         environment_push(declaration);
3093         /* prepends the declaration to the global declarations list */
3094         declaration->next   = scope->declarations;
3095         scope->declarations = declaration;
3096
3097         assert(scope == global_scope);
3098         set_scope(old_scope);
3099
3100         return declaration;
3101 }
3102
3103 /**
3104  * Creates a return_type (func)(argument_type) function type if not
3105  * already exists.
3106  *
3107  * @param return_type    the return type
3108  * @param argument_type  the argument type
3109  */
3110 static type_t *make_function_1_type(type_t *return_type, type_t *argument_type)
3111 {
3112         function_parameter_t *parameter
3113                 = obstack_alloc(type_obst, sizeof(parameter[0]));
3114         memset(parameter, 0, sizeof(parameter[0]));
3115         parameter->type = argument_type;
3116
3117         type_t *type               = allocate_type_zero(TYPE_FUNCTION);
3118         type->function.return_type = return_type;
3119         type->function.parameters  = parameter;
3120
3121         type_t *result = typehash_insert(type);
3122         if(result != type) {
3123                 free_type(type);
3124         }
3125
3126         return result;
3127 }
3128
3129 /**
3130  * Creates a function type for some function like builtins.
3131  *
3132  * @param symbol   the symbol describing the builtin
3133  */
3134 static type_t *get_builtin_symbol_type(symbol_t *symbol)
3135 {
3136         switch(symbol->ID) {
3137         case T___builtin_alloca:
3138                 return make_function_1_type(type_void_ptr, type_size_t);
3139         case T___builtin_nan:
3140                 return make_function_1_type(type_double, type_string);
3141         case T___builtin_nanf:
3142                 return make_function_1_type(type_float, type_string);
3143         case T___builtin_nand:
3144                 return make_function_1_type(type_long_double, type_string);
3145         case T___builtin_va_end:
3146                 return make_function_1_type(type_void, type_valist);
3147         default:
3148                 panic("not implemented builtin symbol found");
3149         }
3150 }
3151
3152 /**
3153  * Performs automatic type cast as described in § 6.3.2.1.
3154  *
3155  * @param orig_type  the original type
3156  */
3157 static type_t *automatic_type_conversion(type_t *orig_type)
3158 {
3159         type_t *type = skip_typeref(orig_type);
3160         if(is_type_array(type)) {
3161                 array_type_t *array_type   = &type->array;
3162                 type_t       *element_type = array_type->element_type;
3163                 unsigned      qualifiers   = array_type->type.qualifiers;
3164
3165                 return make_pointer_type(element_type, qualifiers);
3166         }
3167
3168         if(is_type_function(type)) {
3169                 return make_pointer_type(orig_type, TYPE_QUALIFIER_NONE);
3170         }
3171
3172         return orig_type;
3173 }
3174
3175 /**
3176  * reverts the automatic casts of array to pointer types and function
3177  * to function-pointer types as defined § 6.3.2.1
3178  */
3179 type_t *revert_automatic_type_conversion(const expression_t *expression)
3180 {
3181         switch (expression->kind) {
3182                 case EXPR_REFERENCE: return expression->reference.declaration->type;
3183                 case EXPR_SELECT:    return expression->select.compound_entry->type;
3184
3185                 case EXPR_UNARY_DEREFERENCE: {
3186                         const expression_t *const value = expression->unary.value;
3187                         type_t             *const type  = skip_typeref(value->base.datatype);
3188                         assert(is_type_pointer(type));
3189                         return type->pointer.points_to;
3190                 }
3191
3192                 case EXPR_BUILTIN_SYMBOL:
3193                         return get_builtin_symbol_type(expression->builtin_symbol.symbol);
3194
3195                 case EXPR_ARRAY_ACCESS: {
3196                         const expression_t *const array_ref = expression->array_access.array_ref;
3197                         type_t             *const type_left = skip_typeref(array_ref->base.datatype);
3198                         if (!is_type_valid(type_left))
3199                                 return type_left;
3200                         assert(is_type_pointer(type_left));
3201                         return type_left->pointer.points_to;
3202                 }
3203
3204                 default: break;
3205         }
3206
3207         return expression->base.datatype;
3208 }
3209
3210 static expression_t *parse_reference(void)
3211 {
3212         expression_t *expression = allocate_expression_zero(EXPR_REFERENCE);
3213
3214         reference_expression_t *ref = &expression->reference;
3215         ref->symbol = token.v.symbol;
3216
3217         declaration_t *declaration = get_declaration(ref->symbol, NAMESPACE_NORMAL);
3218
3219         source_position_t source_position = token.source_position;
3220         next_token();
3221
3222         if(declaration == NULL) {
3223                 if (! strict_mode && token.type == '(') {
3224                         /* an implicitly defined function */
3225                         if (warning.implicit_function_declaration) {
3226                                 warningf(HERE, "implicit declaration of function '%Y'",
3227                                         ref->symbol);
3228                         }
3229
3230                         declaration = create_implicit_function(ref->symbol,
3231                                                                source_position);
3232                 } else {
3233                         errorf(HERE, "unknown symbol '%Y' found.", ref->symbol);
3234                         return expression;
3235                 }
3236         }
3237
3238         type_t *type         = declaration->type;
3239
3240         /* we always do the auto-type conversions; the & and sizeof parser contains
3241          * code to revert this! */
3242         type = automatic_type_conversion(type);
3243
3244         ref->declaration         = declaration;
3245         ref->expression.datatype = type;
3246
3247         /* this declaration is used */
3248         declaration->used = true;
3249
3250         return expression;
3251 }
3252
3253 static void check_cast_allowed(expression_t *expression, type_t *dest_type)
3254 {
3255         (void) expression;
3256         (void) dest_type;
3257         /* TODO check if explicit cast is allowed and issue warnings/errors */
3258 }
3259
3260 static expression_t *parse_cast(void)
3261 {
3262         expression_t *cast = allocate_expression_zero(EXPR_UNARY_CAST);
3263
3264         cast->base.source_position = token.source_position;
3265
3266         type_t *type  = parse_typename();
3267
3268         expect(')');
3269         expression_t *value = parse_sub_expression(20);
3270
3271         check_cast_allowed(value, type);
3272
3273         cast->base.datatype = type;
3274         cast->unary.value   = value;
3275
3276         return cast;
3277 }
3278
3279 static expression_t *parse_statement_expression(void)
3280 {
3281         expression_t *expression = allocate_expression_zero(EXPR_STATEMENT);
3282
3283         statement_t *statement           = parse_compound_statement();
3284         expression->statement.statement  = statement;
3285         expression->base.source_position = statement->base.source_position;
3286
3287         /* find last statement and use its type */
3288         type_t *type = type_void;
3289         const statement_t *stmt = statement->compound.statements;
3290         if (stmt != NULL) {
3291                 while (stmt->base.next != NULL)
3292                         stmt = stmt->base.next;
3293
3294                 if (stmt->kind == STATEMENT_EXPRESSION) {
3295                         type = stmt->expression.expression->base.datatype;
3296                 }
3297         } else {
3298                 warningf(expression->base.source_position, "empty statement expression ({})");
3299         }
3300         expression->base.datatype = type;
3301
3302         expect(')');
3303
3304         return expression;
3305 }
3306
3307 static expression_t *parse_brace_expression(void)
3308 {
3309         eat('(');
3310
3311         switch(token.type) {
3312         case '{':
3313                 /* gcc extension: a statement expression */
3314                 return parse_statement_expression();
3315
3316         TYPE_QUALIFIERS
3317         TYPE_SPECIFIERS
3318                 return parse_cast();
3319         case T_IDENTIFIER:
3320                 if(is_typedef_symbol(token.v.symbol)) {
3321                         return parse_cast();
3322                 }
3323         }
3324
3325         expression_t *result = parse_expression();
3326         expect(')');
3327
3328         return result;
3329 }
3330
3331 static expression_t *parse_function_keyword(void)
3332 {
3333         next_token();
3334         /* TODO */
3335
3336         if (current_function == NULL) {
3337                 errorf(HERE, "'__func__' used outside of a function");
3338         }
3339
3340         string_literal_expression_t *expression
3341                 = allocate_ast_zero(sizeof(expression[0]));
3342
3343         expression->expression.kind     = EXPR_FUNCTION;
3344         expression->expression.datatype = type_string;
3345
3346         return (expression_t*) expression;
3347 }
3348
3349 static expression_t *parse_pretty_function_keyword(void)
3350 {
3351         eat(T___PRETTY_FUNCTION__);
3352         /* TODO */
3353
3354         if (current_function == NULL) {
3355                 errorf(HERE, "'__PRETTY_FUNCTION__' used outside of a function");
3356         }
3357
3358         string_literal_expression_t *expression
3359                 = allocate_ast_zero(sizeof(expression[0]));
3360
3361         expression->expression.kind     = EXPR_PRETTY_FUNCTION;
3362         expression->expression.datatype = type_string;
3363
3364         return (expression_t*) expression;
3365 }
3366
3367 static designator_t *parse_designator(void)
3368 {
3369         designator_t *result = allocate_ast_zero(sizeof(result[0]));
3370
3371         if(token.type != T_IDENTIFIER) {
3372                 parse_error_expected("while parsing member designator",
3373                                      T_IDENTIFIER, 0);
3374                 eat_paren();
3375                 return NULL;
3376         }
3377         result->symbol = token.v.symbol;
3378         next_token();
3379
3380         designator_t *last_designator = result;
3381         while(true) {
3382                 if(token.type == '.') {
3383                         next_token();
3384                         if(token.type != T_IDENTIFIER) {
3385                                 parse_error_expected("while parsing member designator",
3386                                                      T_IDENTIFIER, 0);
3387                                 eat_paren();
3388                                 return NULL;
3389                         }
3390                         designator_t *designator = allocate_ast_zero(sizeof(result[0]));
3391                         designator->symbol       = token.v.symbol;
3392                         next_token();
3393
3394                         last_designator->next = designator;
3395                         last_designator       = designator;
3396                         continue;
3397                 }
3398                 if(token.type == '[') {
3399                         next_token();
3400                         designator_t *designator = allocate_ast_zero(sizeof(result[0]));
3401                         designator->array_access = parse_expression();
3402                         if(designator->array_access == NULL) {
3403                                 eat_paren();
3404                                 return NULL;
3405                         }
3406                         expect(']');
3407
3408                         last_designator->next = designator;
3409                         last_designator       = designator;
3410                         continue;
3411                 }
3412                 break;
3413         }
3414
3415         return result;
3416 }
3417
3418 static expression_t *parse_offsetof(void)
3419 {
3420         eat(T___builtin_offsetof);
3421
3422         expression_t *expression  = allocate_expression_zero(EXPR_OFFSETOF);
3423         expression->base.datatype = type_size_t;
3424
3425         expect('(');
3426         expression->offsetofe.type = parse_typename();
3427         expect(',');
3428         expression->offsetofe.designator = parse_designator();
3429         expect(')');
3430
3431         return expression;
3432 }
3433
3434 static expression_t *parse_va_start(void)
3435 {
3436         eat(T___builtin_va_start);
3437
3438         expression_t *expression = allocate_expression_zero(EXPR_VA_START);
3439
3440         expect('(');
3441         expression->va_starte.ap = parse_assignment_expression();
3442         expect(',');
3443         expression_t *const expr = parse_assignment_expression();
3444         if (expr->kind == EXPR_REFERENCE) {
3445                 declaration_t *const decl = expr->reference.declaration;
3446                 if (decl->parent_scope == &current_function->scope &&
3447                     decl->next == NULL) {
3448                         expression->va_starte.parameter = decl;
3449                         expect(')');
3450                         return expression;
3451                 }
3452         }
3453         errorf(expr->base.source_position, "second argument of 'va_start' must be last parameter of the current function");
3454
3455         return create_invalid_expression();
3456 }
3457
3458 static expression_t *parse_va_arg(void)
3459 {
3460         eat(T___builtin_va_arg);
3461
3462         expression_t *expression = allocate_expression_zero(EXPR_VA_ARG);
3463
3464         expect('(');
3465         expression->va_arge.ap = parse_assignment_expression();
3466         expect(',');
3467         expression->base.datatype = parse_typename();
3468         expect(')');
3469
3470         return expression;
3471 }
3472
3473 static expression_t *parse_builtin_symbol(void)
3474 {
3475         expression_t *expression = allocate_expression_zero(EXPR_BUILTIN_SYMBOL);
3476
3477         symbol_t *symbol = token.v.symbol;
3478
3479         expression->builtin_symbol.symbol = symbol;
3480         next_token();
3481
3482         type_t *type = get_builtin_symbol_type(symbol);
3483         type = automatic_type_conversion(type);
3484
3485         expression->base.datatype = type;
3486         return expression;
3487 }
3488
3489 static expression_t *parse_builtin_constant(void)
3490 {
3491         eat(T___builtin_constant_p);
3492
3493         expression_t *expression = allocate_expression_zero(EXPR_BUILTIN_CONSTANT_P);
3494
3495         expect('(');
3496         expression->builtin_constant.value = parse_assignment_expression();
3497         expect(')');
3498         expression->base.datatype = type_int;
3499
3500         return expression;
3501 }
3502
3503 static expression_t *parse_builtin_prefetch(void)
3504 {
3505         eat(T___builtin_prefetch);
3506
3507         expression_t *expression = allocate_expression_zero(EXPR_BUILTIN_PREFETCH);
3508
3509         expect('(');
3510         expression->builtin_prefetch.adr = parse_assignment_expression();
3511         if (token.type == ',') {
3512                 next_token();
3513                 expression->builtin_prefetch.rw = parse_assignment_expression();
3514         }
3515         if (token.type == ',') {
3516                 next_token();
3517                 expression->builtin_prefetch.locality = parse_assignment_expression();
3518         }
3519         expect(')');
3520         expression->base.datatype = type_void;
3521
3522         return expression;
3523 }
3524
3525 static expression_t *parse_compare_builtin(void)
3526 {
3527         expression_t *expression;
3528
3529         switch(token.type) {
3530         case T___builtin_isgreater:
3531                 expression = allocate_expression_zero(EXPR_BINARY_ISGREATER);
3532                 break;
3533         case T___builtin_isgreaterequal:
3534                 expression = allocate_expression_zero(EXPR_BINARY_ISGREATEREQUAL);
3535                 break;
3536         case T___builtin_isless:
3537                 expression = allocate_expression_zero(EXPR_BINARY_ISLESS);
3538                 break;
3539         case T___builtin_islessequal:
3540                 expression = allocate_expression_zero(EXPR_BINARY_ISLESSEQUAL);
3541                 break;
3542         case T___builtin_islessgreater:
3543                 expression = allocate_expression_zero(EXPR_BINARY_ISLESSGREATER);
3544                 break;
3545         case T___builtin_isunordered:
3546                 expression = allocate_expression_zero(EXPR_BINARY_ISUNORDERED);
3547                 break;
3548         default:
3549                 panic("invalid compare builtin found");
3550                 break;
3551         }
3552         expression->base.source_position = HERE;
3553         next_token();
3554
3555         expect('(');
3556         expression->binary.left = parse_assignment_expression();
3557         expect(',');
3558         expression->binary.right = parse_assignment_expression();
3559         expect(')');
3560
3561         type_t *const orig_type_left  = expression->binary.left->base.datatype;
3562         type_t *const orig_type_right = expression->binary.right->base.datatype;
3563
3564         type_t *const type_left  = skip_typeref(orig_type_left);
3565         type_t *const type_right = skip_typeref(orig_type_right);
3566         if(!is_type_float(type_left) && !is_type_float(type_right)) {
3567                 if (is_type_valid(type_left) && is_type_valid(type_right)) {
3568                         type_error_incompatible("invalid operands in comparison",
3569                                 expression->base.source_position, orig_type_left, orig_type_right);
3570                 }
3571         } else {
3572                 semantic_comparison(&expression->binary);
3573         }
3574
3575         return expression;
3576 }
3577
3578 static expression_t *parse_builtin_expect(void)
3579 {
3580         eat(T___builtin_expect);
3581
3582         expression_t *expression
3583                 = allocate_expression_zero(EXPR_BINARY_BUILTIN_EXPECT);
3584
3585         expect('(');
3586         expression->binary.left = parse_assignment_expression();
3587         expect(',');
3588         expression->binary.right = parse_constant_expression();
3589         expect(')');
3590
3591         expression->base.datatype = expression->binary.left->base.datatype;
3592
3593         return expression;
3594 }
3595
3596 static expression_t *parse_assume(void) {
3597         eat(T_assume);
3598
3599         expression_t *expression
3600                 = allocate_expression_zero(EXPR_UNARY_ASSUME);
3601
3602         expect('(');
3603         expression->unary.value = parse_assignment_expression();
3604         expect(')');
3605
3606         expression->base.datatype = type_void;
3607         return expression;
3608 }
3609
3610 static expression_t *parse_alignof(void) {
3611         eat(T___alignof__);
3612
3613         expression_t *expression
3614                 = allocate_expression_zero(EXPR_ALIGNOF);
3615
3616         expect('(');
3617         expression->alignofe.type = parse_typename();
3618         expect(')');
3619
3620         expression->base.datatype = type_size_t;
3621         return expression;
3622 }
3623
3624 static expression_t *parse_primary_expression(void)
3625 {
3626         switch(token.type) {
3627         case T_INTEGER:
3628                 return parse_int_const();
3629         case T_FLOATINGPOINT:
3630                 return parse_float_const();
3631         case T_STRING_LITERAL:
3632                 return parse_string_const();
3633         case T_WIDE_STRING_LITERAL:
3634                 return parse_wide_string_const();
3635         case T_IDENTIFIER:
3636                 return parse_reference();
3637         case T___FUNCTION__:
3638         case T___func__:
3639                 return parse_function_keyword();
3640         case T___PRETTY_FUNCTION__:
3641                 return parse_pretty_function_keyword();
3642         case T___builtin_offsetof:
3643                 return parse_offsetof();
3644         case T___builtin_va_start:
3645                 return parse_va_start();
3646         case T___builtin_va_arg:
3647                 return parse_va_arg();
3648         case T___builtin_expect:
3649                 return parse_builtin_expect();
3650         case T___builtin_nanf:
3651         case T___builtin_alloca:
3652         case T___builtin_va_end:
3653                 return parse_builtin_symbol();
3654         case T___builtin_isgreater:
3655         case T___builtin_isgreaterequal:
3656         case T___builtin_isless:
3657         case T___builtin_islessequal:
3658         case T___builtin_islessgreater:
3659         case T___builtin_isunordered:
3660                 return parse_compare_builtin();
3661         case T___builtin_constant_p:
3662                 return parse_builtin_constant();
3663         case T___builtin_prefetch:
3664                 return parse_builtin_prefetch();
3665         case T___alignof__:
3666                 return parse_alignof();
3667         case T_assume:
3668                 return parse_assume();
3669
3670         case '(':
3671                 return parse_brace_expression();
3672         }
3673
3674         errorf(HERE, "unexpected token '%K'", &token);
3675         eat_statement();
3676
3677         return create_invalid_expression();
3678 }
3679
3680 /**
3681  * Check if the expression has the character type and issue a warning then.
3682  */
3683 static void check_for_char_index_type(const expression_t *expression) {
3684         type_t       *const type      = expression->base.datatype;
3685         const type_t *const base_type = skip_typeref(type);
3686
3687         if (is_type_atomic(base_type, ATOMIC_TYPE_CHAR) &&
3688                         warning.char_subscripts) {
3689                 warningf(expression->base.source_position,
3690                         "array subscript has type '%T'", type);
3691         }
3692 }
3693
3694 static expression_t *parse_array_expression(unsigned precedence,
3695                                             expression_t *left)
3696 {
3697         (void) precedence;
3698
3699         eat('[');
3700
3701         expression_t *inside = parse_expression();
3702
3703         array_access_expression_t *array_access
3704                 = allocate_ast_zero(sizeof(array_access[0]));
3705
3706         array_access->expression.kind = EXPR_ARRAY_ACCESS;
3707
3708         type_t *const orig_type_left   = left->base.datatype;
3709         type_t *const orig_type_inside = inside->base.datatype;
3710
3711         type_t *const type_left   = skip_typeref(orig_type_left);
3712         type_t *const type_inside = skip_typeref(orig_type_inside);
3713
3714         type_t *return_type;
3715         if (is_type_pointer(type_left)) {
3716                 return_type             = type_left->pointer.points_to;
3717                 array_access->array_ref = left;
3718                 array_access->index     = inside;
3719                 check_for_char_index_type(inside);
3720         } else if (is_type_pointer(type_inside)) {
3721                 return_type             = type_inside->pointer.points_to;
3722                 array_access->array_ref = inside;
3723                 array_access->index     = left;
3724                 array_access->flipped   = true;
3725                 check_for_char_index_type(left);
3726         } else {
3727                 if (is_type_valid(type_left) && is_type_valid(type_inside)) {
3728                         errorf(HERE,
3729                                 "array access on object with non-pointer types '%T', '%T'",
3730                                 orig_type_left, orig_type_inside);
3731                 }
3732                 return_type             = type_error_type;
3733                 array_access->array_ref = create_invalid_expression();
3734         }
3735
3736         if(token.type != ']') {
3737                 parse_error_expected("Problem while parsing array access", ']', 0);
3738                 return (expression_t*) array_access;
3739         }
3740         next_token();
3741
3742         return_type = automatic_type_conversion(return_type);
3743         array_access->expression.datatype = return_type;
3744
3745         return (expression_t*) array_access;
3746 }
3747
3748 static expression_t *parse_sizeof(unsigned precedence)
3749 {
3750         eat(T_sizeof);
3751
3752         sizeof_expression_t *sizeof_expression
3753                 = allocate_ast_zero(sizeof(sizeof_expression[0]));
3754         sizeof_expression->expression.kind     = EXPR_SIZEOF;
3755         sizeof_expression->expression.datatype = type_size_t;
3756
3757         if(token.type == '(' && is_declaration_specifier(look_ahead(1), true)) {
3758                 next_token();
3759                 sizeof_expression->type = parse_typename();
3760                 expect(')');
3761         } else {
3762                 expression_t *expression  = parse_sub_expression(precedence);
3763                 expression->base.datatype = revert_automatic_type_conversion(expression);
3764
3765                 sizeof_expression->type            = expression->base.datatype;
3766                 sizeof_expression->size_expression = expression;
3767         }
3768
3769         return (expression_t*) sizeof_expression;
3770 }
3771
3772 static expression_t *parse_select_expression(unsigned precedence,
3773                                              expression_t *compound)
3774 {
3775         (void) precedence;
3776         assert(token.type == '.' || token.type == T_MINUSGREATER);
3777
3778         bool is_pointer = (token.type == T_MINUSGREATER);
3779         next_token();
3780
3781         expression_t *select    = allocate_expression_zero(EXPR_SELECT);
3782         select->select.compound = compound;
3783
3784         if(token.type != T_IDENTIFIER) {
3785                 parse_error_expected("while parsing select", T_IDENTIFIER, 0);
3786                 return select;
3787         }
3788         symbol_t *symbol      = token.v.symbol;
3789         select->select.symbol = symbol;
3790         next_token();
3791
3792         type_t *const orig_type = compound->base.datatype;
3793         type_t *const type      = skip_typeref(orig_type);
3794
3795         type_t *type_left = type;
3796         if(is_pointer) {
3797                 if (!is_type_pointer(type)) {
3798                         if (is_type_valid(type)) {
3799                                 errorf(HERE, "left hand side of '->' is not a pointer, but '%T'", orig_type);
3800                         }
3801                         return create_invalid_expression();
3802                 }
3803                 type_left = type->pointer.points_to;
3804         }
3805         type_left = skip_typeref(type_left);
3806
3807         if (type_left->kind != TYPE_COMPOUND_STRUCT &&
3808             type_left->kind != TYPE_COMPOUND_UNION) {
3809                 if (is_type_valid(type_left)) {
3810                         errorf(HERE, "request for member '%Y' in something not a struct or "
3811                                "union, but '%T'", symbol, type_left);
3812                 }
3813                 return create_invalid_expression();
3814         }
3815
3816         declaration_t *const declaration = type_left->compound.declaration;
3817
3818         if(!declaration->init.is_defined) {
3819                 errorf(HERE, "request for member '%Y' of incomplete type '%T'",
3820                        symbol, type_left);
3821                 return create_invalid_expression();
3822         }
3823
3824         declaration_t *iter = declaration->scope.declarations;
3825         for( ; iter != NULL; iter = iter->next) {
3826                 if(iter->symbol == symbol) {
3827                         break;
3828                 }
3829         }
3830         if(iter == NULL) {
3831                 errorf(HERE, "'%T' has no member named '%Y'", orig_type, symbol);
3832                 return create_invalid_expression();
3833         }
3834
3835         /* we always do the auto-type conversions; the & and sizeof parser contains
3836          * code to revert this! */
3837         type_t *expression_type = automatic_type_conversion(iter->type);
3838
3839         select->select.compound_entry = iter;
3840         select->base.datatype         = expression_type;
3841
3842         if(expression_type->kind == TYPE_BITFIELD) {
3843                 expression_t *extract
3844                         = allocate_expression_zero(EXPR_UNARY_BITFIELD_EXTRACT);
3845                 extract->unary.value   = select;
3846                 extract->base.datatype = expression_type->bitfield.base;
3847
3848                 return extract;
3849         }
3850
3851         return select;
3852 }
3853
3854 /**
3855  * Parse a call expression, ie. expression '( ... )'.
3856  *
3857  * @param expression  the function address
3858  */
3859 static expression_t *parse_call_expression(unsigned precedence,
3860                                            expression_t *expression)
3861 {
3862         (void) precedence;
3863         expression_t *result = allocate_expression_zero(EXPR_CALL);
3864
3865         call_expression_t *call = &result->call;
3866         call->function          = expression;
3867
3868         type_t *const orig_type = expression->base.datatype;
3869         type_t *const type      = skip_typeref(orig_type);
3870
3871         function_type_t *function_type = NULL;
3872         if (is_type_pointer(type)) {
3873                 type_t *const to_type = skip_typeref(type->pointer.points_to);
3874
3875                 if (is_type_function(to_type)) {
3876                         function_type             = &to_type->function;
3877                         call->expression.datatype = function_type->return_type;
3878                 }
3879         }
3880
3881         if (function_type == NULL && is_type_valid(type)) {
3882                 errorf(HERE, "called object '%E' (type '%T') is not a pointer to a function", expression, orig_type);
3883         }
3884
3885         /* parse arguments */
3886         eat('(');
3887
3888         if(token.type != ')') {
3889                 call_argument_t *last_argument = NULL;
3890
3891                 while(true) {
3892                         call_argument_t *argument = allocate_ast_zero(sizeof(argument[0]));
3893
3894                         argument->expression = parse_assignment_expression();
3895                         if(last_argument == NULL) {
3896                                 call->arguments = argument;
3897                         } else {
3898                                 last_argument->next = argument;
3899                         }
3900                         last_argument = argument;
3901
3902                         if(token.type != ',')
3903                                 break;
3904                         next_token();
3905                 }
3906         }
3907         expect(')');
3908
3909         if(function_type != NULL) {
3910                 function_parameter_t *parameter = function_type->parameters;
3911                 call_argument_t      *argument  = call->arguments;
3912                 for( ; parameter != NULL && argument != NULL;
3913                                 parameter = parameter->next, argument = argument->next) {
3914                         type_t *expected_type = parameter->type;
3915                         /* TODO report scope in error messages */
3916                         expression_t *const arg_expr = argument->expression;
3917                         type_t       *const res_type = semantic_assign(expected_type, arg_expr, "function call");
3918                         if (res_type == NULL) {
3919                                 /* TODO improve error message */
3920                                 errorf(arg_expr->base.source_position,
3921                                         "Cannot call function with argument '%E' of type '%T' where type '%T' is expected",
3922                                         arg_expr, arg_expr->base.datatype, expected_type);
3923                         } else {
3924                                 argument->expression = create_implicit_cast(argument->expression, expected_type);
3925                         }
3926                 }
3927                 /* too few parameters */
3928                 if(parameter != NULL) {
3929                         errorf(HERE, "too few arguments to function '%E'", expression);
3930                 } else if(argument != NULL) {
3931                         /* too many parameters */
3932                         if(!function_type->variadic
3933                                         && !function_type->unspecified_parameters) {
3934                                 errorf(HERE, "too many arguments to function '%E'", expression);
3935                         } else {
3936                                 /* do default promotion */
3937                                 for( ; argument != NULL; argument = argument->next) {
3938                                         type_t *type = argument->expression->base.datatype;
3939
3940                                         type = skip_typeref(type);
3941                                         if(is_type_integer(type)) {
3942                                                 type = promote_integer(type);
3943                                         } else if(type == type_float) {
3944                                                 type = type_double;
3945                                         }
3946
3947                                         argument->expression
3948                                                 = create_implicit_cast(argument->expression, type);
3949                                 }
3950
3951                                 check_format(&result->call);
3952                         }
3953                 } else {
3954                         check_format(&result->call);
3955                 }
3956         }
3957
3958         return result;
3959 }
3960
3961 static type_t *semantic_arithmetic(type_t *type_left, type_t *type_right);
3962
3963 static bool same_compound_type(const type_t *type1, const type_t *type2)
3964 {
3965         return
3966                 is_type_compound(type1) &&
3967                 type1->kind == type2->kind &&
3968                 type1->compound.declaration == type2->compound.declaration;
3969 }
3970
3971 /**
3972  * Parse a conditional expression, ie. 'expression ? ... : ...'.
3973  *
3974  * @param expression  the conditional expression
3975  */
3976 static expression_t *parse_conditional_expression(unsigned precedence,
3977                                                   expression_t *expression)
3978 {
3979         eat('?');
3980
3981         expression_t *result = allocate_expression_zero(EXPR_CONDITIONAL);
3982
3983         conditional_expression_t *conditional = &result->conditional;
3984         conditional->condition = expression;
3985
3986         /* 6.5.15.2 */
3987         type_t *const condition_type_orig = expression->base.datatype;
3988         type_t *const condition_type      = skip_typeref(condition_type_orig);
3989         if (!is_type_scalar(condition_type) && is_type_valid(condition_type)) {
3990                 type_error("expected a scalar type in conditional condition",
3991                            expression->base.source_position, condition_type_orig);
3992         }
3993
3994         expression_t *true_expression = parse_expression();
3995         expect(':');
3996         expression_t *false_expression = parse_sub_expression(precedence);
3997
3998         conditional->true_expression  = true_expression;
3999         conditional->false_expression = false_expression;
4000
4001         type_t *const orig_true_type  = true_expression->base.datatype;
4002         type_t *const orig_false_type = false_expression->base.datatype;
4003         type_t *const true_type       = skip_typeref(orig_true_type);
4004         type_t *const false_type      = skip_typeref(orig_false_type);
4005
4006         /* 6.5.15.3 */
4007         type_t *result_type;
4008         if (is_type_arithmetic(true_type) && is_type_arithmetic(false_type)) {
4009                 result_type = semantic_arithmetic(true_type, false_type);
4010
4011                 true_expression  = create_implicit_cast(true_expression, result_type);
4012                 false_expression = create_implicit_cast(false_expression, result_type);
4013
4014                 conditional->true_expression     = true_expression;
4015                 conditional->false_expression    = false_expression;
4016                 conditional->expression.datatype = result_type;
4017         } else if (same_compound_type(true_type, false_type) || (
4018             is_type_atomic(true_type, ATOMIC_TYPE_VOID) &&
4019             is_type_atomic(false_type, ATOMIC_TYPE_VOID)
4020                 )) {
4021                 /* just take 1 of the 2 types */
4022                 result_type = true_type;
4023         } else if (is_type_pointer(true_type) && is_type_pointer(false_type)
4024                         && pointers_compatible(true_type, false_type)) {
4025                 /* ok */
4026                 result_type = true_type;
4027         } else {
4028                 /* TODO */
4029                 if (is_type_valid(true_type) && is_type_valid(false_type)) {
4030                         type_error_incompatible("while parsing conditional",
4031                                                 expression->base.source_position, true_type,
4032                                                 false_type);
4033                 }
4034                 result_type = type_error_type;
4035         }
4036
4037         conditional->expression.datatype = result_type;
4038         return result;
4039 }
4040
4041 /**
4042  * Parse an extension expression.
4043  */
4044 static expression_t *parse_extension(unsigned precedence)
4045 {
4046         eat(T___extension__);
4047
4048         /* TODO enable extensions */
4049         expression_t *expression = parse_sub_expression(precedence);
4050         /* TODO disable extensions */
4051         return expression;
4052 }
4053
4054 static expression_t *parse_builtin_classify_type(const unsigned precedence)
4055 {
4056         eat(T___builtin_classify_type);
4057
4058         expression_t *result  = allocate_expression_zero(EXPR_CLASSIFY_TYPE);
4059         result->base.datatype = type_int;
4060
4061         expect('(');
4062         expression_t *expression = parse_sub_expression(precedence);
4063         expect(')');
4064         result->classify_type.type_expression = expression;
4065
4066         return result;
4067 }
4068
4069 static void semantic_incdec(unary_expression_t *expression)
4070 {
4071         type_t *const orig_type = expression->value->base.datatype;
4072         type_t *const type      = skip_typeref(orig_type);
4073         /* TODO !is_type_real && !is_type_pointer */
4074         if(!is_type_arithmetic(type) && type->kind != TYPE_POINTER) {
4075                 if (is_type_valid(type)) {
4076                         /* TODO: improve error message */
4077                         errorf(HERE, "operation needs an arithmetic or pointer type");
4078                 }
4079                 return;
4080         }
4081
4082         expression->expression.datatype = orig_type;
4083 }
4084
4085 static void semantic_unexpr_arithmetic(unary_expression_t *expression)
4086 {
4087         type_t *const orig_type = expression->value->base.datatype;
4088         type_t *const type      = skip_typeref(orig_type);
4089         if(!is_type_arithmetic(type)) {
4090                 if (is_type_valid(type)) {
4091                         /* TODO: improve error message */
4092                         errorf(HERE, "operation needs an arithmetic type");
4093                 }
4094                 return;
4095         }
4096
4097         expression->expression.datatype = orig_type;
4098 }
4099
4100 static void semantic_unexpr_scalar(unary_expression_t *expression)
4101 {
4102         type_t *const orig_type = expression->value->base.datatype;
4103         type_t *const type      = skip_typeref(orig_type);
4104         if (!is_type_scalar(type)) {
4105                 if (is_type_valid(type)) {
4106                         errorf(HERE, "operand of ! must be of scalar type");
4107                 }
4108                 return;
4109         }
4110
4111         expression->expression.datatype = orig_type;
4112 }
4113
4114 static void semantic_unexpr_integer(unary_expression_t *expression)
4115 {
4116         type_t *const orig_type = expression->value->base.datatype;
4117         type_t *const type      = skip_typeref(orig_type);
4118         if (!is_type_integer(type)) {
4119                 if (is_type_valid(type)) {
4120                         errorf(HERE, "operand of ~ must be of integer type");
4121                 }
4122                 return;
4123         }
4124
4125         expression->expression.datatype = orig_type;
4126 }
4127
4128 static void semantic_dereference(unary_expression_t *expression)
4129 {
4130         type_t *const orig_type = expression->value->base.datatype;
4131         type_t *const type      = skip_typeref(orig_type);
4132         if(!is_type_pointer(type)) {
4133                 if (is_type_valid(type)) {
4134                         errorf(HERE, "Unary '*' needs pointer or arrray type, but type '%T' given", orig_type);
4135                 }
4136                 return;
4137         }
4138
4139         type_t *result_type = type->pointer.points_to;
4140         result_type = automatic_type_conversion(result_type);
4141         expression->expression.datatype = result_type;
4142 }
4143
4144 /**
4145  * Check the semantic of the address taken expression.
4146  */
4147 static void semantic_take_addr(unary_expression_t *expression)
4148 {
4149         expression_t *value  = expression->value;
4150         value->base.datatype = revert_automatic_type_conversion(value);
4151
4152         type_t *orig_type = value->base.datatype;
4153         if(!is_type_valid(orig_type))
4154                 return;
4155
4156         if(value->kind == EXPR_REFERENCE) {
4157                 declaration_t *const declaration = value->reference.declaration;
4158                 if(declaration != NULL) {
4159                         if (declaration->storage_class == STORAGE_CLASS_REGISTER) {
4160                                 errorf(expression->expression.source_position,
4161                                         "address of register variable '%Y' requested",
4162                                         declaration->symbol);
4163                         }
4164                         declaration->address_taken = 1;
4165                 }
4166         }
4167
4168         expression->expression.datatype = make_pointer_type(orig_type, TYPE_QUALIFIER_NONE);
4169 }
4170
4171 #define CREATE_UNARY_EXPRESSION_PARSER(token_type, unexpression_type, sfunc)   \
4172 static expression_t *parse_##unexpression_type(unsigned precedence)            \
4173 {                                                                              \
4174         eat(token_type);                                                           \
4175                                                                                    \
4176         expression_t *unary_expression                                             \
4177                 = allocate_expression_zero(unexpression_type);                         \
4178         unary_expression->base.source_position = HERE;                             \
4179         unary_expression->unary.value = parse_sub_expression(precedence);          \
4180                                                                                    \
4181         sfunc(&unary_expression->unary);                                           \
4182                                                                                    \
4183         return unary_expression;                                                   \
4184 }
4185
4186 CREATE_UNARY_EXPRESSION_PARSER('-', EXPR_UNARY_NEGATE,
4187                                semantic_unexpr_arithmetic)
4188 CREATE_UNARY_EXPRESSION_PARSER('+', EXPR_UNARY_PLUS,
4189                                semantic_unexpr_arithmetic)
4190 CREATE_UNARY_EXPRESSION_PARSER('!', EXPR_UNARY_NOT,
4191                                semantic_unexpr_scalar)
4192 CREATE_UNARY_EXPRESSION_PARSER('*', EXPR_UNARY_DEREFERENCE,
4193                                semantic_dereference)
4194 CREATE_UNARY_EXPRESSION_PARSER('&', EXPR_UNARY_TAKE_ADDRESS,
4195                                semantic_take_addr)
4196 CREATE_UNARY_EXPRESSION_PARSER('~', EXPR_UNARY_BITWISE_NEGATE,
4197                                semantic_unexpr_integer)
4198 CREATE_UNARY_EXPRESSION_PARSER(T_PLUSPLUS,   EXPR_UNARY_PREFIX_INCREMENT,
4199                                semantic_incdec)
4200 CREATE_UNARY_EXPRESSION_PARSER(T_MINUSMINUS, EXPR_UNARY_PREFIX_DECREMENT,
4201                                semantic_incdec)
4202
4203 #define CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(token_type, unexpression_type, \
4204                                                sfunc)                         \
4205 static expression_t *parse_##unexpression_type(unsigned precedence,           \
4206                                                expression_t *left)            \
4207 {                                                                             \
4208         (void) precedence;                                                        \
4209         eat(token_type);                                                          \
4210                                                                               \
4211         expression_t *unary_expression                                            \
4212                 = allocate_expression_zero(unexpression_type);                        \
4213         unary_expression->unary.value = left;                                     \
4214                                                                                   \
4215         sfunc(&unary_expression->unary);                                          \
4216                                                                               \
4217         return unary_expression;                                                  \
4218 }
4219
4220 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_PLUSPLUS,
4221                                        EXPR_UNARY_POSTFIX_INCREMENT,
4222                                        semantic_incdec)
4223 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_MINUSMINUS,
4224                                        EXPR_UNARY_POSTFIX_DECREMENT,
4225                                        semantic_incdec)
4226
4227 static type_t *semantic_arithmetic(type_t *type_left, type_t *type_right)
4228 {
4229         /* TODO: handle complex + imaginary types */
4230
4231         /* § 6.3.1.8 Usual arithmetic conversions */
4232         if(type_left == type_long_double || type_right == type_long_double) {
4233                 return type_long_double;
4234         } else if(type_left == type_double || type_right == type_double) {
4235                 return type_double;
4236         } else if(type_left == type_float || type_right == type_float) {
4237                 return type_float;
4238         }
4239
4240         type_right = promote_integer(type_right);
4241         type_left  = promote_integer(type_left);
4242
4243         if(type_left == type_right)
4244                 return type_left;
4245
4246         bool signed_left  = is_type_signed(type_left);
4247         bool signed_right = is_type_signed(type_right);
4248         int  rank_left    = get_rank(type_left);
4249         int  rank_right   = get_rank(type_right);
4250         if(rank_left < rank_right) {
4251                 if(signed_left == signed_right || !signed_right) {
4252                         return type_right;
4253                 } else {
4254                         return type_left;
4255                 }
4256         } else {
4257                 if(signed_left == signed_right || !signed_left) {
4258                         return type_left;
4259                 } else {
4260                         return type_right;
4261                 }
4262         }
4263 }
4264
4265 /**
4266  * Check the semantic restrictions for a binary expression.
4267  */
4268 static void semantic_binexpr_arithmetic(binary_expression_t *expression)
4269 {
4270         expression_t *const left            = expression->left;
4271         expression_t *const right           = expression->right;
4272         type_t       *const orig_type_left  = left->base.datatype;
4273         type_t       *const orig_type_right = right->base.datatype;
4274         type_t       *const type_left       = skip_typeref(orig_type_left);
4275         type_t       *const type_right      = skip_typeref(orig_type_right);
4276
4277         if(!is_type_arithmetic(type_left) || !is_type_arithmetic(type_right)) {
4278                 /* TODO: improve error message */
4279                 if (is_type_valid(type_left) && is_type_valid(type_right)) {
4280                         errorf(HERE, "operation needs arithmetic types");
4281                 }
4282                 return;
4283         }
4284
4285         type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
4286         expression->left  = create_implicit_cast(left, arithmetic_type);
4287         expression->right = create_implicit_cast(right, arithmetic_type);
4288         expression->expression.datatype = arithmetic_type;
4289 }
4290
4291 static void semantic_shift_op(binary_expression_t *expression)
4292 {
4293         expression_t *const left            = expression->left;
4294         expression_t *const right           = expression->right;
4295         type_t       *const orig_type_left  = left->base.datatype;
4296         type_t       *const orig_type_right = right->base.datatype;
4297         type_t       *      type_left       = skip_typeref(orig_type_left);
4298         type_t       *      type_right      = skip_typeref(orig_type_right);
4299
4300         if(!is_type_integer(type_left) || !is_type_integer(type_right)) {
4301                 /* TODO: improve error message */
4302                 if (is_type_valid(type_left) && is_type_valid(type_right)) {
4303                         errorf(HERE, "operation needs integer types");
4304                 }
4305                 return;
4306         }
4307
4308         type_left  = promote_integer(type_left);
4309         type_right = promote_integer(type_right);
4310
4311         expression->left  = create_implicit_cast(left, type_left);
4312         expression->right = create_implicit_cast(right, type_right);
4313         expression->expression.datatype = type_left;
4314 }
4315
4316 static void semantic_add(binary_expression_t *expression)
4317 {
4318         expression_t *const left            = expression->left;
4319         expression_t *const right           = expression->right;
4320         type_t       *const orig_type_left  = left->base.datatype;
4321         type_t       *const orig_type_right = right->base.datatype;
4322         type_t       *const type_left       = skip_typeref(orig_type_left);
4323         type_t       *const type_right      = skip_typeref(orig_type_right);
4324
4325         /* § 5.6.5 */
4326         if(is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) {
4327                 type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
4328                 expression->left  = create_implicit_cast(left, arithmetic_type);
4329                 expression->right = create_implicit_cast(right, arithmetic_type);
4330                 expression->expression.datatype = arithmetic_type;
4331                 return;
4332         } else if(is_type_pointer(type_left) && is_type_integer(type_right)) {
4333                 expression->expression.datatype = type_left;
4334         } else if(is_type_pointer(type_right) && is_type_integer(type_left)) {
4335                 expression->expression.datatype = type_right;
4336         } else if (is_type_valid(type_left) && is_type_valid(type_right)) {
4337                 errorf(HERE, "invalid operands to binary + ('%T', '%T')", orig_type_left, orig_type_right);
4338         }
4339 }
4340
4341 static void semantic_sub(binary_expression_t *expression)
4342 {
4343         expression_t *const left            = expression->left;
4344         expression_t *const right           = expression->right;
4345         type_t       *const orig_type_left  = left->base.datatype;
4346         type_t       *const orig_type_right = right->base.datatype;
4347         type_t       *const type_left       = skip_typeref(orig_type_left);
4348         type_t       *const type_right      = skip_typeref(orig_type_right);
4349
4350         /* § 5.6.5 */
4351         if(is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) {
4352                 type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
4353                 expression->left  = create_implicit_cast(left, arithmetic_type);
4354                 expression->right = create_implicit_cast(right, arithmetic_type);
4355                 expression->expression.datatype = arithmetic_type;
4356                 return;
4357         } else if(is_type_pointer(type_left) && is_type_integer(type_right)) {
4358                 expression->expression.datatype = type_left;
4359         } else if(is_type_pointer(type_left) && is_type_pointer(type_right)) {
4360                 if(!pointers_compatible(type_left, type_right)) {
4361                         errorf(HERE, "pointers to incompatible objects to binary '-' ('%T', '%T')", orig_type_left, orig_type_right);
4362                 } else {
4363                         expression->expression.datatype = type_ptrdiff_t;
4364                 }
4365         } else if (is_type_valid(type_left) && is_type_valid(type_right)) {
4366                 errorf(HERE, "invalid operands to binary '-' ('%T', '%T')", orig_type_left, orig_type_right);
4367         }
4368 }
4369
4370 /**
4371  * Check the semantics of comparison expressions.
4372  *
4373  * @param expression   The expression to check.
4374  */
4375 static void semantic_comparison(binary_expression_t *expression)
4376 {
4377         expression_t *left            = expression->left;
4378         expression_t *right           = expression->right;
4379         type_t       *orig_type_left  = left->base.datatype;
4380         type_t       *orig_type_right = right->base.datatype;
4381
4382         type_t *type_left  = skip_typeref(orig_type_left);
4383         type_t *type_right = skip_typeref(orig_type_right);
4384
4385         /* TODO non-arithmetic types */
4386         if(is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) {
4387                 type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
4388                 expression->left  = create_implicit_cast(left, arithmetic_type);
4389                 expression->right = create_implicit_cast(right, arithmetic_type);
4390                 expression->expression.datatype = arithmetic_type;
4391                 if (warning.float_equal &&
4392                     (expression->expression.kind == EXPR_BINARY_EQUAL ||
4393                      expression->expression.kind == EXPR_BINARY_NOTEQUAL) &&
4394                     is_type_float(arithmetic_type)) {
4395                         warningf(expression->expression.source_position,
4396                                  "comparing floating point with == or != is unsafe");
4397                 }
4398         } else if (is_type_pointer(type_left) && is_type_pointer(type_right)) {
4399                 /* TODO check compatibility */
4400         } else if (is_type_pointer(type_left)) {
4401                 expression->right = create_implicit_cast(right, type_left);
4402         } else if (is_type_pointer(type_right)) {
4403                 expression->left = create_implicit_cast(left, type_right);
4404         } else if (is_type_valid(type_left) && is_type_valid(type_right)) {
4405                 type_error_incompatible("invalid operands in comparison",
4406                                         expression->expression.source_position,
4407                                         type_left, type_right);
4408         }
4409         expression->expression.datatype = type_int;
4410 }
4411
4412 static void semantic_arithmetic_assign(binary_expression_t *expression)
4413 {
4414         expression_t *left            = expression->left;
4415         expression_t *right           = expression->right;
4416         type_t       *orig_type_left  = left->base.datatype;
4417         type_t       *orig_type_right = right->base.datatype;
4418
4419         type_t *type_left  = skip_typeref(orig_type_left);
4420         type_t *type_right = skip_typeref(orig_type_right);
4421
4422         if(!is_type_arithmetic(type_left) || !is_type_arithmetic(type_right)) {
4423                 /* TODO: improve error message */
4424                 if (is_type_valid(type_left) && is_type_valid(type_right)) {
4425                         errorf(HERE, "operation needs arithmetic types");
4426                 }
4427                 return;
4428         }
4429
4430         /* combined instructions are tricky. We can't create an implicit cast on
4431          * the left side, because we need the uncasted form for the store.
4432          * The ast2firm pass has to know that left_type must be right_type
4433          * for the arithmetic operation and create a cast by itself */
4434         type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
4435         expression->right       = create_implicit_cast(right, arithmetic_type);
4436         expression->expression.datatype = type_left;
4437 }
4438
4439 static void semantic_arithmetic_addsubb_assign(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_arithmetic(type_left) && is_type_arithmetic(type_right)) {
4449                 /* combined instructions are tricky. We can't create an implicit cast on
4450                  * the left side, because we need the uncasted form for the store.
4451                  * The ast2firm pass has to know that left_type must be right_type
4452                  * for the arithmetic operation and create a cast by itself */
4453                 type_t *const arithmetic_type = semantic_arithmetic(type_left, type_right);
4454                 expression->right = create_implicit_cast(right, arithmetic_type);
4455                 expression->expression.datatype = type_left;
4456         } else if (is_type_pointer(type_left) && is_type_integer(type_right)) {
4457                 expression->expression.datatype = type_left;
4458         } else if (is_type_valid(type_left) && is_type_valid(type_right)) {
4459                 errorf(HERE, "incompatible types '%T' and '%T' in assignment", orig_type_left, orig_type_right);
4460         }
4461 }
4462
4463 /**
4464  * Check the semantic restrictions of a logical expression.
4465  */
4466 static void semantic_logical_op(binary_expression_t *expression)
4467 {
4468         expression_t *const left            = expression->left;
4469         expression_t *const right           = expression->right;
4470         type_t       *const orig_type_left  = left->base.datatype;
4471         type_t       *const orig_type_right = right->base.datatype;
4472         type_t       *const type_left       = skip_typeref(orig_type_left);
4473         type_t       *const type_right      = skip_typeref(orig_type_right);
4474
4475         if (!is_type_scalar(type_left) || !is_type_scalar(type_right)) {
4476                 /* TODO: improve error message */
4477                 if (is_type_valid(type_left) && is_type_valid(type_right)) {
4478                         errorf(HERE, "operation needs scalar types");
4479                 }
4480                 return;
4481         }
4482
4483         expression->expression.datatype = type_int;
4484 }
4485
4486 /**
4487  * Checks if a compound type has constant fields.
4488  */
4489 static bool has_const_fields(const compound_type_t *type)
4490 {
4491         const scope_t       *scope       = &type->declaration->scope;
4492         const declaration_t *declaration = scope->declarations;
4493
4494         for (; declaration != NULL; declaration = declaration->next) {
4495                 if (declaration->namespc != NAMESPACE_NORMAL)
4496                         continue;
4497
4498                 const type_t *decl_type = skip_typeref(declaration->type);
4499                 if (decl_type->base.qualifiers & TYPE_QUALIFIER_CONST)
4500                         return true;
4501         }
4502         /* TODO */
4503         return false;
4504 }
4505
4506 /**
4507  * Check the semantic restrictions of a binary assign expression.
4508  */
4509 static void semantic_binexpr_assign(binary_expression_t *expression)
4510 {
4511         expression_t *left           = expression->left;
4512         type_t       *orig_type_left = left->base.datatype;
4513
4514         type_t *type_left = revert_automatic_type_conversion(left);
4515         type_left         = skip_typeref(orig_type_left);
4516
4517         /* must be a modifiable lvalue */
4518         if (is_type_array(type_left)) {
4519                 errorf(HERE, "cannot assign to arrays ('%E')", left);
4520                 return;
4521         }
4522         if(type_left->base.qualifiers & TYPE_QUALIFIER_CONST) {
4523                 errorf(HERE, "assignment to readonly location '%E' (type '%T')", left,
4524                        orig_type_left);
4525                 return;
4526         }
4527         if(is_type_incomplete(type_left)) {
4528                 errorf(HERE,
4529                        "left-hand side of assignment '%E' has incomplete type '%T'",
4530                        left, orig_type_left);
4531                 return;
4532         }
4533         if(is_type_compound(type_left) && has_const_fields(&type_left->compound)) {
4534                 errorf(HERE, "cannot assign to '%E' because compound type '%T' has readonly fields",
4535                        left, orig_type_left);
4536                 return;
4537         }
4538
4539         type_t *const res_type = semantic_assign(orig_type_left, expression->right,
4540                                                  "assignment");
4541         if (res_type == NULL) {
4542                 errorf(expression->expression.source_position,
4543                         "cannot assign to '%T' from '%T'",
4544                         orig_type_left, expression->right->base.datatype);
4545         } else {
4546                 expression->right = create_implicit_cast(expression->right, res_type);
4547         }
4548
4549         expression->expression.datatype = orig_type_left;
4550 }
4551
4552 static bool expression_has_effect(const expression_t *const expr)
4553 {
4554         switch (expr->kind) {
4555                 case EXPR_UNKNOWN:                   break;
4556                 case EXPR_INVALID:                   break;
4557                 case EXPR_REFERENCE:                 return false;
4558                 case EXPR_CONST:                     return false;
4559                 case EXPR_STRING_LITERAL:            return false;
4560                 case EXPR_WIDE_STRING_LITERAL:       return false;
4561                 case EXPR_CALL: {
4562                         const call_expression_t *const call = &expr->call;
4563                         if (call->function->kind != EXPR_BUILTIN_SYMBOL)
4564                                 return true;
4565
4566                         switch (call->function->builtin_symbol.symbol->ID) {
4567                                 case T___builtin_va_end: return true;
4568                                 default:                 return false;
4569                         }
4570                 }
4571                 case EXPR_CONDITIONAL: {
4572                         const conditional_expression_t *const cond = &expr->conditional;
4573                         return
4574                                 expression_has_effect(cond->true_expression) &&
4575                                 expression_has_effect(cond->false_expression);
4576                 }
4577                 case EXPR_SELECT:                    return false;
4578                 case EXPR_ARRAY_ACCESS:              return false;
4579                 case EXPR_SIZEOF:                    return false;
4580                 case EXPR_CLASSIFY_TYPE:             return false;
4581                 case EXPR_ALIGNOF:                   return false;
4582
4583                 case EXPR_FUNCTION:                  return false;
4584                 case EXPR_PRETTY_FUNCTION:           return false;
4585                 case EXPR_BUILTIN_SYMBOL:            break; /* handled in EXPR_CALL */
4586                 case EXPR_BUILTIN_CONSTANT_P:        return false;
4587                 case EXPR_BUILTIN_PREFETCH:          return true;
4588                 case EXPR_OFFSETOF:                  return false;
4589                 case EXPR_VA_START:                  return true;
4590                 case EXPR_VA_ARG:                    return true;
4591                 case EXPR_STATEMENT:                 return true; // TODO
4592
4593                 case EXPR_UNARY_NEGATE:              return false;
4594                 case EXPR_UNARY_PLUS:                return false;
4595                 case EXPR_UNARY_BITWISE_NEGATE:      return false;
4596                 case EXPR_UNARY_NOT:                 return false;
4597                 case EXPR_UNARY_DEREFERENCE:         return false;
4598                 case EXPR_UNARY_TAKE_ADDRESS:        return false;
4599                 case EXPR_UNARY_POSTFIX_INCREMENT:   return true;
4600                 case EXPR_UNARY_POSTFIX_DECREMENT:   return true;
4601                 case EXPR_UNARY_PREFIX_INCREMENT:    return true;
4602                 case EXPR_UNARY_PREFIX_DECREMENT:    return true;
4603                 case EXPR_UNARY_CAST:
4604                         return is_type_atomic(expr->base.datatype, ATOMIC_TYPE_VOID);
4605                 case EXPR_UNARY_CAST_IMPLICIT:       return true;
4606                 case EXPR_UNARY_ASSUME:              return true;
4607                 case EXPR_UNARY_BITFIELD_EXTRACT:    return false;
4608
4609                 case EXPR_BINARY_ADD:                return false;
4610                 case EXPR_BINARY_SUB:                return false;
4611                 case EXPR_BINARY_MUL:                return false;
4612                 case EXPR_BINARY_DIV:                return false;
4613                 case EXPR_BINARY_MOD:                return false;
4614                 case EXPR_BINARY_EQUAL:              return false;
4615                 case EXPR_BINARY_NOTEQUAL:           return false;
4616                 case EXPR_BINARY_LESS:               return false;
4617                 case EXPR_BINARY_LESSEQUAL:          return false;
4618                 case EXPR_BINARY_GREATER:            return false;
4619                 case EXPR_BINARY_GREATEREQUAL:       return false;
4620                 case EXPR_BINARY_BITWISE_AND:        return false;
4621                 case EXPR_BINARY_BITWISE_OR:         return false;
4622                 case EXPR_BINARY_BITWISE_XOR:        return false;
4623                 case EXPR_BINARY_SHIFTLEFT:          return false;
4624                 case EXPR_BINARY_SHIFTRIGHT:         return false;
4625                 case EXPR_BINARY_ASSIGN:             return true;
4626                 case EXPR_BINARY_MUL_ASSIGN:         return true;
4627                 case EXPR_BINARY_DIV_ASSIGN:         return true;
4628                 case EXPR_BINARY_MOD_ASSIGN:         return true;
4629                 case EXPR_BINARY_ADD_ASSIGN:         return true;
4630                 case EXPR_BINARY_SUB_ASSIGN:         return true;
4631                 case EXPR_BINARY_SHIFTLEFT_ASSIGN:   return true;
4632                 case EXPR_BINARY_SHIFTRIGHT_ASSIGN:  return true;
4633                 case EXPR_BINARY_BITWISE_AND_ASSIGN: return true;
4634                 case EXPR_BINARY_BITWISE_XOR_ASSIGN: return true;
4635                 case EXPR_BINARY_BITWISE_OR_ASSIGN:  return true;
4636                 case EXPR_BINARY_LOGICAL_AND:
4637                 case EXPR_BINARY_LOGICAL_OR:
4638                 case EXPR_BINARY_COMMA:
4639                         return expression_has_effect(expr->binary.right);
4640
4641                 case EXPR_BINARY_BUILTIN_EXPECT:     return true;
4642                 case EXPR_BINARY_ISGREATER:          return false;
4643                 case EXPR_BINARY_ISGREATEREQUAL:     return false;
4644                 case EXPR_BINARY_ISLESS:             return false;
4645                 case EXPR_BINARY_ISLESSEQUAL:        return false;
4646                 case EXPR_BINARY_ISLESSGREATER:      return false;
4647                 case EXPR_BINARY_ISUNORDERED:        return false;
4648         }
4649
4650         panic("unexpected statement");
4651 }
4652
4653 static void semantic_comma(binary_expression_t *expression)
4654 {
4655         if (warning.unused_value) {
4656                 const expression_t *const left = expression->left;
4657                 if (!expression_has_effect(left)) {
4658                         warningf(left->base.source_position, "left-hand operand of comma expression has no effect");
4659                 }
4660         }
4661         expression->expression.datatype = expression->right->base.datatype;
4662 }
4663
4664 #define CREATE_BINEXPR_PARSER(token_type, binexpression_type, sfunc, lr)  \
4665 static expression_t *parse_##binexpression_type(unsigned precedence,      \
4666                                                 expression_t *left)       \
4667 {                                                                         \
4668         eat(token_type);                                                      \
4669         source_position_t pos = HERE;                                         \
4670                                                                           \
4671         expression_t *right = parse_sub_expression(precedence + lr);          \
4672                                                                           \
4673         expression_t *binexpr = allocate_expression_zero(binexpression_type); \
4674         binexpr->base.source_position = pos;                                  \
4675         binexpr->binary.left  = left;                                         \
4676         binexpr->binary.right = right;                                        \
4677         sfunc(&binexpr->binary);                                              \
4678                                                                           \
4679         return binexpr;                                                       \
4680 }
4681
4682 CREATE_BINEXPR_PARSER(',', EXPR_BINARY_COMMA,    semantic_comma, 1)
4683 CREATE_BINEXPR_PARSER('*', EXPR_BINARY_MUL,      semantic_binexpr_arithmetic, 1)
4684 CREATE_BINEXPR_PARSER('/', EXPR_BINARY_DIV,      semantic_binexpr_arithmetic, 1)
4685 CREATE_BINEXPR_PARSER('%', EXPR_BINARY_MOD,      semantic_binexpr_arithmetic, 1)
4686 CREATE_BINEXPR_PARSER('+', EXPR_BINARY_ADD,      semantic_add, 1)
4687 CREATE_BINEXPR_PARSER('-', EXPR_BINARY_SUB,      semantic_sub, 1)
4688 CREATE_BINEXPR_PARSER('<', EXPR_BINARY_LESS,     semantic_comparison, 1)
4689 CREATE_BINEXPR_PARSER('>', EXPR_BINARY_GREATER,  semantic_comparison, 1)
4690 CREATE_BINEXPR_PARSER('=', EXPR_BINARY_ASSIGN,   semantic_binexpr_assign, 0)
4691
4692 CREATE_BINEXPR_PARSER(T_EQUALEQUAL,           EXPR_BINARY_EQUAL,
4693                       semantic_comparison, 1)
4694 CREATE_BINEXPR_PARSER(T_EXCLAMATIONMARKEQUAL, EXPR_BINARY_NOTEQUAL,
4695                       semantic_comparison, 1)
4696 CREATE_BINEXPR_PARSER(T_LESSEQUAL,            EXPR_BINARY_LESSEQUAL,
4697                       semantic_comparison, 1)
4698 CREATE_BINEXPR_PARSER(T_GREATEREQUAL,         EXPR_BINARY_GREATEREQUAL,
4699                       semantic_comparison, 1)
4700
4701 CREATE_BINEXPR_PARSER('&', EXPR_BINARY_BITWISE_AND,
4702                       semantic_binexpr_arithmetic, 1)
4703 CREATE_BINEXPR_PARSER('|', EXPR_BINARY_BITWISE_OR,
4704                       semantic_binexpr_arithmetic, 1)
4705 CREATE_BINEXPR_PARSER('^', EXPR_BINARY_BITWISE_XOR,
4706                       semantic_binexpr_arithmetic, 1)
4707 CREATE_BINEXPR_PARSER(T_ANDAND, EXPR_BINARY_LOGICAL_AND,
4708                       semantic_logical_op, 1)
4709 CREATE_BINEXPR_PARSER(T_PIPEPIPE, EXPR_BINARY_LOGICAL_OR,
4710                       semantic_logical_op, 1)
4711 CREATE_BINEXPR_PARSER(T_LESSLESS, EXPR_BINARY_SHIFTLEFT,
4712                       semantic_shift_op, 1)
4713 CREATE_BINEXPR_PARSER(T_GREATERGREATER, EXPR_BINARY_SHIFTRIGHT,
4714                       semantic_shift_op, 1)
4715 CREATE_BINEXPR_PARSER(T_PLUSEQUAL, EXPR_BINARY_ADD_ASSIGN,
4716                       semantic_arithmetic_addsubb_assign, 0)
4717 CREATE_BINEXPR_PARSER(T_MINUSEQUAL, EXPR_BINARY_SUB_ASSIGN,
4718                       semantic_arithmetic_addsubb_assign, 0)
4719 CREATE_BINEXPR_PARSER(T_ASTERISKEQUAL, EXPR_BINARY_MUL_ASSIGN,
4720                       semantic_arithmetic_assign, 0)
4721 CREATE_BINEXPR_PARSER(T_SLASHEQUAL, EXPR_BINARY_DIV_ASSIGN,
4722                       semantic_arithmetic_assign, 0)
4723 CREATE_BINEXPR_PARSER(T_PERCENTEQUAL, EXPR_BINARY_MOD_ASSIGN,
4724                       semantic_arithmetic_assign, 0)
4725 CREATE_BINEXPR_PARSER(T_LESSLESSEQUAL, EXPR_BINARY_SHIFTLEFT_ASSIGN,
4726                       semantic_arithmetic_assign, 0)
4727 CREATE_BINEXPR_PARSER(T_GREATERGREATEREQUAL, EXPR_BINARY_SHIFTRIGHT_ASSIGN,
4728                       semantic_arithmetic_assign, 0)
4729 CREATE_BINEXPR_PARSER(T_ANDEQUAL, EXPR_BINARY_BITWISE_AND_ASSIGN,
4730                       semantic_arithmetic_assign, 0)
4731 CREATE_BINEXPR_PARSER(T_PIPEEQUAL, EXPR_BINARY_BITWISE_OR_ASSIGN,
4732                       semantic_arithmetic_assign, 0)
4733 CREATE_BINEXPR_PARSER(T_CARETEQUAL, EXPR_BINARY_BITWISE_XOR_ASSIGN,
4734                       semantic_arithmetic_assign, 0)
4735
4736 static expression_t *parse_sub_expression(unsigned precedence)
4737 {
4738         if(token.type < 0) {
4739                 return expected_expression_error();
4740         }
4741
4742         expression_parser_function_t *parser
4743                 = &expression_parsers[token.type];
4744         source_position_t             source_position = token.source_position;
4745         expression_t                 *left;
4746
4747         if(parser->parser != NULL) {
4748                 left = parser->parser(parser->precedence);
4749         } else {
4750                 left = parse_primary_expression();
4751         }
4752         assert(left != NULL);
4753         left->base.source_position = source_position;
4754
4755         while(true) {
4756                 if(token.type < 0) {
4757                         return expected_expression_error();
4758                 }
4759
4760                 parser = &expression_parsers[token.type];
4761                 if(parser->infix_parser == NULL)
4762                         break;
4763                 if(parser->infix_precedence < precedence)
4764                         break;
4765
4766                 left = parser->infix_parser(parser->infix_precedence, left);
4767
4768                 assert(left != NULL);
4769                 assert(left->kind != EXPR_UNKNOWN);
4770                 left->base.source_position = source_position;
4771         }
4772
4773         return left;
4774 }
4775
4776 /**
4777  * Parse an expression.
4778  */
4779 static expression_t *parse_expression(void)
4780 {
4781         return parse_sub_expression(1);
4782 }
4783
4784 /**
4785  * Register a parser for a prefix-like operator with given precedence.
4786  *
4787  * @param parser      the parser function
4788  * @param token_type  the token type of the prefix token
4789  * @param precedence  the precedence of the operator
4790  */
4791 static void register_expression_parser(parse_expression_function parser,
4792                                        int token_type, unsigned precedence)
4793 {
4794         expression_parser_function_t *entry = &expression_parsers[token_type];
4795
4796         if(entry->parser != NULL) {
4797                 diagnosticf("for token '%k'\n", (token_type_t)token_type);
4798                 panic("trying to register multiple expression parsers for a token");
4799         }
4800         entry->parser     = parser;
4801         entry->precedence = precedence;
4802 }
4803
4804 /**
4805  * Register a parser for an infix operator with given precedence.
4806  *
4807  * @param parser      the parser function
4808  * @param token_type  the token type of the infix operator
4809  * @param precedence  the precedence of the operator
4810  */
4811 static void register_infix_parser(parse_expression_infix_function parser,
4812                 int token_type, unsigned precedence)
4813 {
4814         expression_parser_function_t *entry = &expression_parsers[token_type];
4815
4816         if(entry->infix_parser != NULL) {
4817                 diagnosticf("for token '%k'\n", (token_type_t)token_type);
4818                 panic("trying to register multiple infix expression parsers for a "
4819                       "token");
4820         }
4821         entry->infix_parser     = parser;
4822         entry->infix_precedence = precedence;
4823 }
4824
4825 /**
4826  * Initialize the expression parsers.
4827  */
4828 static void init_expression_parsers(void)
4829 {
4830         memset(&expression_parsers, 0, sizeof(expression_parsers));
4831
4832         register_infix_parser(parse_array_expression,         '[',              30);
4833         register_infix_parser(parse_call_expression,          '(',              30);
4834         register_infix_parser(parse_select_expression,        '.',              30);
4835         register_infix_parser(parse_select_expression,        T_MINUSGREATER,   30);
4836         register_infix_parser(parse_EXPR_UNARY_POSTFIX_INCREMENT,
4837                                                               T_PLUSPLUS,       30);
4838         register_infix_parser(parse_EXPR_UNARY_POSTFIX_DECREMENT,
4839                                                               T_MINUSMINUS,     30);
4840
4841         register_infix_parser(parse_EXPR_BINARY_MUL,          '*',              16);
4842         register_infix_parser(parse_EXPR_BINARY_DIV,          '/',              16);
4843         register_infix_parser(parse_EXPR_BINARY_MOD,          '%',              16);
4844         register_infix_parser(parse_EXPR_BINARY_SHIFTLEFT,    T_LESSLESS,       16);
4845         register_infix_parser(parse_EXPR_BINARY_SHIFTRIGHT,   T_GREATERGREATER, 16);
4846         register_infix_parser(parse_EXPR_BINARY_ADD,          '+',              15);
4847         register_infix_parser(parse_EXPR_BINARY_SUB,          '-',              15);
4848         register_infix_parser(parse_EXPR_BINARY_LESS,         '<',              14);
4849         register_infix_parser(parse_EXPR_BINARY_GREATER,      '>',              14);
4850         register_infix_parser(parse_EXPR_BINARY_LESSEQUAL,    T_LESSEQUAL,      14);
4851         register_infix_parser(parse_EXPR_BINARY_GREATEREQUAL, T_GREATEREQUAL,   14);
4852         register_infix_parser(parse_EXPR_BINARY_EQUAL,        T_EQUALEQUAL,     13);
4853         register_infix_parser(parse_EXPR_BINARY_NOTEQUAL,
4854                                                     T_EXCLAMATIONMARKEQUAL, 13);
4855         register_infix_parser(parse_EXPR_BINARY_BITWISE_AND,  '&',              12);
4856         register_infix_parser(parse_EXPR_BINARY_BITWISE_XOR,  '^',              11);
4857         register_infix_parser(parse_EXPR_BINARY_BITWISE_OR,   '|',              10);
4858         register_infix_parser(parse_EXPR_BINARY_LOGICAL_AND,  T_ANDAND,          9);
4859         register_infix_parser(parse_EXPR_BINARY_LOGICAL_OR,   T_PIPEPIPE,        8);
4860         register_infix_parser(parse_conditional_expression,   '?',               7);
4861         register_infix_parser(parse_EXPR_BINARY_ASSIGN,       '=',               2);
4862         register_infix_parser(parse_EXPR_BINARY_ADD_ASSIGN,   T_PLUSEQUAL,       2);
4863         register_infix_parser(parse_EXPR_BINARY_SUB_ASSIGN,   T_MINUSEQUAL,      2);
4864         register_infix_parser(parse_EXPR_BINARY_MUL_ASSIGN,   T_ASTERISKEQUAL,   2);
4865         register_infix_parser(parse_EXPR_BINARY_DIV_ASSIGN,   T_SLASHEQUAL,      2);
4866         register_infix_parser(parse_EXPR_BINARY_MOD_ASSIGN,   T_PERCENTEQUAL,    2);
4867         register_infix_parser(parse_EXPR_BINARY_SHIFTLEFT_ASSIGN,
4868                                                                 T_LESSLESSEQUAL, 2);
4869         register_infix_parser(parse_EXPR_BINARY_SHIFTRIGHT_ASSIGN,
4870                                                           T_GREATERGREATEREQUAL, 2);
4871         register_infix_parser(parse_EXPR_BINARY_BITWISE_AND_ASSIGN,
4872                                                                      T_ANDEQUAL, 2);
4873         register_infix_parser(parse_EXPR_BINARY_BITWISE_OR_ASSIGN,
4874                                                                     T_PIPEEQUAL, 2);
4875         register_infix_parser(parse_EXPR_BINARY_BITWISE_XOR_ASSIGN,
4876                                                                    T_CARETEQUAL, 2);
4877
4878         register_infix_parser(parse_EXPR_BINARY_COMMA,        ',',               1);
4879
4880         register_expression_parser(parse_EXPR_UNARY_NEGATE,           '-',      25);
4881         register_expression_parser(parse_EXPR_UNARY_PLUS,             '+',      25);
4882         register_expression_parser(parse_EXPR_UNARY_NOT,              '!',      25);
4883         register_expression_parser(parse_EXPR_UNARY_BITWISE_NEGATE,   '~',      25);
4884         register_expression_parser(parse_EXPR_UNARY_DEREFERENCE,      '*',      25);
4885         register_expression_parser(parse_EXPR_UNARY_TAKE_ADDRESS,     '&',      25);
4886         register_expression_parser(parse_EXPR_UNARY_PREFIX_INCREMENT,
4887                                                                   T_PLUSPLUS,   25);
4888         register_expression_parser(parse_EXPR_UNARY_PREFIX_DECREMENT,
4889                                                                   T_MINUSMINUS, 25);
4890         register_expression_parser(parse_sizeof,                  T_sizeof,     25);
4891         register_expression_parser(parse_extension,            T___extension__, 25);
4892         register_expression_parser(parse_builtin_classify_type,
4893                                                      T___builtin_classify_type, 25);
4894 }
4895
4896 /**
4897  * Parse a asm statement constraints specification.
4898  */
4899 static asm_constraint_t *parse_asm_constraints(void)
4900 {
4901         asm_constraint_t *result = NULL;
4902         asm_constraint_t *last   = NULL;
4903
4904         while(token.type == T_STRING_LITERAL || token.type == '[') {
4905                 asm_constraint_t *constraint = allocate_ast_zero(sizeof(constraint[0]));
4906                 memset(constraint, 0, sizeof(constraint[0]));
4907
4908                 if(token.type == '[') {
4909                         eat('[');
4910                         if(token.type != T_IDENTIFIER) {
4911                                 parse_error_expected("while parsing asm constraint",
4912                                                      T_IDENTIFIER, 0);
4913                                 return NULL;
4914                         }
4915                         constraint->symbol = token.v.symbol;
4916
4917                         expect(']');
4918                 }
4919
4920                 constraint->constraints = parse_string_literals();
4921                 expect('(');
4922                 constraint->expression = parse_expression();
4923                 expect(')');
4924
4925                 if(last != NULL) {
4926                         last->next = constraint;
4927                 } else {
4928                         result = constraint;
4929                 }
4930                 last = constraint;
4931
4932                 if(token.type != ',')
4933                         break;
4934                 eat(',');
4935         }
4936
4937         return result;
4938 }
4939
4940 /**
4941  * Parse a asm statement clobber specification.
4942  */
4943 static asm_clobber_t *parse_asm_clobbers(void)
4944 {
4945         asm_clobber_t *result = NULL;
4946         asm_clobber_t *last   = NULL;
4947
4948         while(token.type == T_STRING_LITERAL) {
4949                 asm_clobber_t *clobber = allocate_ast_zero(sizeof(clobber[0]));
4950                 clobber->clobber       = parse_string_literals();
4951
4952                 if(last != NULL) {
4953                         last->next = clobber;
4954                 } else {
4955                         result = clobber;
4956                 }
4957                 last = clobber;
4958
4959                 if(token.type != ',')
4960                         break;
4961                 eat(',');
4962         }
4963
4964         return result;
4965 }
4966
4967 /**
4968  * Parse an asm statement.
4969  */
4970 static statement_t *parse_asm_statement(void)
4971 {
4972         eat(T_asm);
4973
4974         statement_t *statement          = allocate_statement_zero(STATEMENT_ASM);
4975         statement->base.source_position = token.source_position;
4976
4977         asm_statement_t *asm_statement = &statement->asms;
4978
4979         if(token.type == T_volatile) {
4980                 next_token();
4981                 asm_statement->is_volatile = true;
4982         }
4983
4984         expect('(');
4985         asm_statement->asm_text = parse_string_literals();
4986
4987         if(token.type != ':')
4988                 goto end_of_asm;
4989         eat(':');
4990
4991         asm_statement->inputs = parse_asm_constraints();
4992         if(token.type != ':')
4993                 goto end_of_asm;
4994         eat(':');
4995
4996         asm_statement->outputs = parse_asm_constraints();
4997         if(token.type != ':')
4998                 goto end_of_asm;
4999         eat(':');
5000
5001         asm_statement->clobbers = parse_asm_clobbers();
5002
5003 end_of_asm:
5004         expect(')');
5005         expect(';');
5006         return statement;
5007 }
5008
5009 /**
5010  * Parse a case statement.
5011  */
5012 static statement_t *parse_case_statement(void)
5013 {
5014         eat(T_case);
5015
5016         statement_t *statement = allocate_statement_zero(STATEMENT_CASE_LABEL);
5017
5018         statement->base.source_position  = token.source_position;
5019         statement->case_label.expression = parse_expression();
5020
5021         expect(':');
5022
5023         if (! is_constant_expression(statement->case_label.expression)) {
5024                 errorf(statement->base.source_position,
5025                         "case label does not reduce to an integer constant");
5026         } else {
5027                 /* TODO: check if the case label is already known */
5028                 if (current_switch != NULL) {
5029                         /* link all cases into the switch statement */
5030                         if (current_switch->last_case == NULL) {
5031                                 current_switch->first_case =
5032                                 current_switch->last_case  = &statement->case_label;
5033                         } else {
5034                                 current_switch->last_case->next = &statement->case_label;
5035                         }
5036                 } else {
5037                         errorf(statement->base.source_position,
5038                                 "case label not within a switch statement");
5039                 }
5040         }
5041         statement->case_label.label_statement = parse_statement();
5042
5043         return statement;
5044 }
5045
5046 /**
5047  * Finds an existing default label of a switch statement.
5048  */
5049 static case_label_statement_t *
5050 find_default_label(const switch_statement_t *statement)
5051 {
5052         for (case_label_statement_t *label = statement->first_case;
5053              label != NULL;
5054                  label = label->next) {
5055                 if (label->expression == NULL)
5056                         return label;
5057         }
5058         return NULL;
5059 }
5060
5061 /**
5062  * Parse a default statement.
5063  */
5064 static statement_t *parse_default_statement(void)
5065 {
5066         eat(T_default);
5067
5068         statement_t *statement = allocate_statement_zero(STATEMENT_CASE_LABEL);
5069
5070         statement->base.source_position = token.source_position;
5071
5072         expect(':');
5073         if (current_switch != NULL) {
5074                 const case_label_statement_t *def_label = find_default_label(current_switch);
5075                 if (def_label != NULL) {
5076                         errorf(HERE, "multiple default labels in one switch");
5077                         errorf(def_label->statement.source_position,
5078                                 "this is the first default label");
5079                 } else {
5080                         /* link all cases into the switch statement */
5081                         if (current_switch->last_case == NULL) {
5082                                 current_switch->first_case =
5083                                         current_switch->last_case  = &statement->case_label;
5084                         } else {
5085                                 current_switch->last_case->next = &statement->case_label;
5086                         }
5087                 }
5088         } else {
5089                 errorf(statement->base.source_position,
5090                         "'default' label not within a switch statement");
5091         }
5092         statement->label.label_statement = parse_statement();
5093
5094         return statement;
5095 }
5096
5097 /**
5098  * Return the declaration for a given label symbol or create a new one.
5099  */
5100 static declaration_t *get_label(symbol_t *symbol)
5101 {
5102         declaration_t *candidate = get_declaration(symbol, NAMESPACE_LABEL);
5103         assert(current_function != NULL);
5104         /* if we found a label in the same function, then we already created the
5105          * declaration */
5106         if(candidate != NULL
5107                         && candidate->parent_scope == &current_function->scope) {
5108                 return candidate;
5109         }
5110
5111         /* otherwise we need to create a new one */
5112         declaration_t *const declaration = allocate_declaration_zero();
5113         declaration->namespc       = NAMESPACE_LABEL;
5114         declaration->symbol        = symbol;
5115
5116         label_push(declaration);
5117
5118         return declaration;
5119 }
5120
5121 /**
5122  * Parse a label statement.
5123  */
5124 static statement_t *parse_label_statement(void)
5125 {
5126         assert(token.type == T_IDENTIFIER);
5127         symbol_t *symbol = token.v.symbol;
5128         next_token();
5129
5130         declaration_t *label = get_label(symbol);
5131
5132         /* if source position is already set then the label is defined twice,
5133          * otherwise it was just mentioned in a goto so far */
5134         if(label->source_position.input_name != NULL) {
5135                 errorf(HERE, "duplicate label '%Y'", symbol);
5136                 errorf(label->source_position, "previous definition of '%Y' was here",
5137                        symbol);
5138         } else {
5139                 label->source_position = token.source_position;
5140         }
5141
5142         label_statement_t *label_statement = allocate_ast_zero(sizeof(label[0]));
5143
5144         label_statement->statement.kind            = STATEMENT_LABEL;
5145         label_statement->statement.source_position = token.source_position;
5146         label_statement->label                     = label;
5147
5148         eat(':');
5149
5150         if(token.type == '}') {
5151                 /* TODO only warn? */
5152                 errorf(HERE, "label at end of compound statement");
5153                 return (statement_t*) label_statement;
5154         } else {
5155                 if (token.type == ';') {
5156                         /* eat an empty statement here, to avoid the warning about an empty
5157                          * after a label.  label:; is commonly used to have a label before
5158                          * a }. */
5159                         next_token();
5160                 } else {
5161                         label_statement->label_statement = parse_statement();
5162                 }
5163         }
5164
5165         /* remember the labels's in a list for later checking */
5166         if (label_last == NULL) {
5167                 label_first = label_last = label_statement;
5168         } else {
5169                 label_last->next = label_statement;
5170         }
5171
5172         return (statement_t*) label_statement;
5173 }
5174
5175 /**
5176  * Parse an if statement.
5177  */
5178 static statement_t *parse_if(void)
5179 {
5180         eat(T_if);
5181
5182         if_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5183         statement->statement.kind            = STATEMENT_IF;
5184         statement->statement.source_position = token.source_position;
5185
5186         expect('(');
5187         statement->condition = parse_expression();
5188         expect(')');
5189
5190         statement->true_statement = parse_statement();
5191         if(token.type == T_else) {
5192                 next_token();
5193                 statement->false_statement = parse_statement();
5194         }
5195
5196         return (statement_t*) statement;
5197 }
5198
5199 /**
5200  * Parse a switch statement.
5201  */
5202 static statement_t *parse_switch(void)
5203 {
5204         eat(T_switch);
5205
5206         switch_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5207         statement->statement.kind            = STATEMENT_SWITCH;
5208         statement->statement.source_position = token.source_position;
5209
5210         expect('(');
5211         expression_t *const expr = parse_expression();
5212         type_t       *      type = skip_typeref(expr->base.datatype);
5213         if (is_type_integer(type)) {
5214                 type = promote_integer(type);
5215         } else if (is_type_valid(type)) {
5216                 errorf(expr->base.source_position, "switch quantity is not an integer, but '%T'", type);
5217                 type = type_error_type;
5218         }
5219         statement->expression = create_implicit_cast(expr, type);
5220         expect(')');
5221
5222         switch_statement_t *rem = current_switch;
5223         current_switch  = statement;
5224         statement->body = parse_statement();
5225         current_switch  = rem;
5226
5227         if (warning.switch_default && find_default_label(statement) == NULL) {
5228                 warningf(statement->statement.source_position, "switch has no default case");
5229         }
5230
5231         return (statement_t*) statement;
5232 }
5233
5234 static statement_t *parse_loop_body(statement_t *const loop)
5235 {
5236         statement_t *const rem = current_loop;
5237         current_loop = loop;
5238         statement_t *const body = parse_statement();
5239         current_loop = rem;
5240         return body;
5241 }
5242
5243 /**
5244  * Parse a while statement.
5245  */
5246 static statement_t *parse_while(void)
5247 {
5248         eat(T_while);
5249
5250         while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5251         statement->statement.kind            = STATEMENT_WHILE;
5252         statement->statement.source_position = token.source_position;
5253
5254         expect('(');
5255         statement->condition = parse_expression();
5256         expect(')');
5257
5258         statement->body = parse_loop_body((statement_t*)statement);
5259
5260         return (statement_t*) statement;
5261 }
5262
5263 /**
5264  * Parse a do statement.
5265  */
5266 static statement_t *parse_do(void)
5267 {
5268         eat(T_do);
5269
5270         do_while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5271         statement->statement.kind            = STATEMENT_DO_WHILE;
5272         statement->statement.source_position = token.source_position;
5273
5274         statement->body = parse_loop_body((statement_t*)statement);
5275         expect(T_while);
5276         expect('(');
5277         statement->condition = parse_expression();
5278         expect(')');
5279         expect(';');
5280
5281         return (statement_t*) statement;
5282 }
5283
5284 /**
5285  * Parse a for statement.
5286  */
5287 static statement_t *parse_for(void)
5288 {
5289         eat(T_for);
5290
5291         for_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5292         statement->statement.kind            = STATEMENT_FOR;
5293         statement->statement.source_position = token.source_position;
5294
5295         expect('(');
5296
5297         int      top        = environment_top();
5298         scope_t *last_scope = scope;
5299         set_scope(&statement->scope);
5300
5301         if(token.type != ';') {
5302                 if(is_declaration_specifier(&token, false)) {
5303                         parse_declaration(record_declaration);
5304                 } else {
5305                         statement->initialisation = parse_expression();
5306                         expect(';');
5307                 }
5308         } else {
5309                 expect(';');
5310         }
5311
5312         if(token.type != ';') {
5313                 statement->condition = parse_expression();
5314         }
5315         expect(';');
5316         if(token.type != ')') {
5317                 statement->step = parse_expression();
5318         }
5319         expect(')');
5320         statement->body = parse_loop_body((statement_t*)statement);
5321
5322         assert(scope == &statement->scope);
5323         set_scope(last_scope);
5324         environment_pop_to(top);
5325
5326         return (statement_t*) statement;
5327 }
5328
5329 /**
5330  * Parse a goto statement.
5331  */
5332 static statement_t *parse_goto(void)
5333 {
5334         eat(T_goto);
5335
5336         if(token.type != T_IDENTIFIER) {
5337                 parse_error_expected("while parsing goto", T_IDENTIFIER, 0);
5338                 eat_statement();
5339                 return NULL;
5340         }
5341         symbol_t *symbol = token.v.symbol;
5342         next_token();
5343
5344         declaration_t *label = get_label(symbol);
5345
5346         goto_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5347
5348         statement->statement.kind            = STATEMENT_GOTO;
5349         statement->statement.source_position = token.source_position;
5350
5351         statement->label = label;
5352
5353         /* remember the goto's in a list for later checking */
5354         if (goto_last == NULL) {
5355                 goto_first = goto_last = statement;
5356         } else {
5357                 goto_last->next = statement;
5358         }
5359
5360         expect(';');
5361
5362         return (statement_t*) statement;
5363 }
5364
5365 /**
5366  * Parse a continue statement.
5367  */
5368 static statement_t *parse_continue(void)
5369 {
5370         statement_t *statement;
5371         if (current_loop == NULL) {
5372                 errorf(HERE, "continue statement not within loop");
5373                 statement = NULL;
5374         } else {
5375                 statement = allocate_statement_zero(STATEMENT_CONTINUE);
5376
5377                 statement->base.source_position = token.source_position;
5378         }
5379
5380         eat(T_continue);
5381         expect(';');
5382
5383         return statement;
5384 }
5385
5386 /**
5387  * Parse a break statement.
5388  */
5389 static statement_t *parse_break(void)
5390 {
5391         statement_t *statement;
5392         if (current_switch == NULL && current_loop == NULL) {
5393                 errorf(HERE, "break statement not within loop or switch");
5394                 statement = NULL;
5395         } else {
5396                 statement = allocate_statement_zero(STATEMENT_BREAK);
5397
5398                 statement->base.source_position = token.source_position;
5399         }
5400
5401         eat(T_break);
5402         expect(';');
5403
5404         return statement;
5405 }
5406
5407 /**
5408  * Check if a given declaration represents a local variable.
5409  */
5410 static bool is_local_var_declaration(const declaration_t *declaration) {
5411         switch ((storage_class_tag_t) declaration->storage_class) {
5412         case STORAGE_CLASS_NONE:
5413         case STORAGE_CLASS_AUTO:
5414         case STORAGE_CLASS_REGISTER: {
5415                 const type_t *type = skip_typeref(declaration->type);
5416                 if(is_type_function(type)) {
5417                         return false;
5418                 } else {
5419                         return true;
5420                 }
5421         }
5422         default:
5423                 return false;
5424         }
5425 }
5426
5427 /**
5428  * Check if a given expression represents a local variable.
5429  */
5430 static bool is_local_variable(const expression_t *expression)
5431 {
5432         if (expression->base.kind != EXPR_REFERENCE) {
5433                 return false;
5434         }
5435         const declaration_t *declaration = expression->reference.declaration;
5436         return is_local_var_declaration(declaration);
5437 }
5438
5439 /**
5440  * Parse a return statement.
5441  */
5442 static statement_t *parse_return(void)
5443 {
5444         eat(T_return);
5445
5446         return_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
5447
5448         statement->statement.kind            = STATEMENT_RETURN;
5449         statement->statement.source_position = token.source_position;
5450
5451         expression_t *return_value = NULL;
5452         if(token.type != ';') {
5453                 return_value = parse_expression();
5454         }
5455         expect(';');
5456
5457         const type_t *const func_type = current_function->type;
5458         assert(is_type_function(func_type));
5459         type_t *const return_type = skip_typeref(func_type->function.return_type);
5460
5461         if(return_value != NULL) {
5462                 type_t *return_value_type = skip_typeref(return_value->base.datatype);
5463
5464                 if(is_type_atomic(return_type, ATOMIC_TYPE_VOID)
5465                                 && !is_type_atomic(return_value_type, ATOMIC_TYPE_VOID)) {
5466                         warningf(statement->statement.source_position,
5467                                 "'return' with a value, in function returning void");
5468                         return_value = NULL;
5469                 } else {
5470                         type_t *const res_type = semantic_assign(return_type,
5471                                 return_value, "'return'");
5472                         if (res_type == NULL) {
5473                                 errorf(statement->statement.source_position,
5474                                         "cannot return something of type '%T' in function returning '%T'",
5475                                         return_value->base.datatype, return_type);
5476                         } else {
5477                                 return_value = create_implicit_cast(return_value, res_type);
5478                         }
5479                 }
5480                 /* check for returning address of a local var */
5481                 if (return_value->base.kind == EXPR_UNARY_TAKE_ADDRESS) {
5482                         const expression_t *expression = return_value->unary.value;
5483                         if (is_local_variable(expression)) {
5484                                 warningf(statement->statement.source_position,
5485                                         "function returns address of local variable");
5486                         }
5487                 }
5488         } else {
5489                 if(!is_type_atomic(return_type, ATOMIC_TYPE_VOID)) {
5490                         warningf(statement->statement.source_position,
5491                                 "'return' without value, in function returning non-void");
5492                 }
5493         }
5494         statement->return_value = return_value;
5495
5496         return (statement_t*) statement;
5497 }
5498
5499 /**
5500  * Parse a declaration statement.
5501  */
5502 static statement_t *parse_declaration_statement(void)
5503 {
5504         statement_t *statement = allocate_statement_zero(STATEMENT_DECLARATION);
5505
5506         statement->base.source_position = token.source_position;
5507
5508         declaration_t *before = last_declaration;
5509         parse_declaration(record_declaration);
5510
5511         if(before == NULL) {
5512                 statement->declaration.declarations_begin = scope->declarations;
5513         } else {
5514                 statement->declaration.declarations_begin = before->next;
5515         }
5516         statement->declaration.declarations_end = last_declaration;
5517
5518         return statement;
5519 }
5520
5521 /**
5522  * Parse an expression statement, ie. expr ';'.
5523  */
5524 static statement_t *parse_expression_statement(void)
5525 {
5526         statement_t *statement = allocate_statement_zero(STATEMENT_EXPRESSION);
5527
5528         statement->base.source_position  = token.source_position;
5529         expression_t *const expr         = parse_expression();
5530         statement->expression.expression = expr;
5531
5532         if (warning.unused_value  && !expression_has_effect(expr)) {
5533                 warningf(expr->base.source_position, "statement has no effect");
5534         }
5535
5536         expect(';');
5537
5538         return statement;
5539 }
5540
5541 /**
5542  * Parse a statement.
5543  */
5544 static statement_t *parse_statement(void)
5545 {
5546         statement_t   *statement = NULL;
5547
5548         /* declaration or statement */
5549         switch(token.type) {
5550         case T_asm:
5551                 statement = parse_asm_statement();
5552                 break;
5553
5554         case T_case:
5555                 statement = parse_case_statement();
5556                 break;
5557
5558         case T_default:
5559                 statement = parse_default_statement();
5560                 break;
5561
5562         case '{':
5563                 statement = parse_compound_statement();
5564                 break;
5565
5566         case T_if:
5567                 statement = parse_if();
5568                 break;
5569
5570         case T_switch:
5571                 statement = parse_switch();
5572                 break;
5573
5574         case T_while:
5575                 statement = parse_while();
5576                 break;
5577
5578         case T_do:
5579                 statement = parse_do();
5580                 break;
5581
5582         case T_for:
5583                 statement = parse_for();
5584                 break;
5585
5586         case T_goto:
5587                 statement = parse_goto();
5588                 break;
5589
5590         case T_continue:
5591                 statement = parse_continue();
5592                 break;
5593
5594         case T_break:
5595                 statement = parse_break();
5596                 break;
5597
5598         case T_return:
5599                 statement = parse_return();
5600                 break;
5601
5602         case ';':
5603                 if (warning.empty_statement) {
5604                         warningf(HERE, "statement is empty");
5605                 }
5606                 next_token();
5607                 statement = NULL;
5608                 break;
5609
5610         case T_IDENTIFIER:
5611                 if(look_ahead(1)->type == ':') {
5612                         statement = parse_label_statement();
5613                         break;
5614                 }
5615
5616                 if(is_typedef_symbol(token.v.symbol)) {
5617                         statement = parse_declaration_statement();
5618                         break;
5619                 }
5620
5621                 statement = parse_expression_statement();
5622                 break;
5623
5624         case T___extension__:
5625                 /* this can be a prefix to a declaration or an expression statement */
5626                 /* we simply eat it now and parse the rest with tail recursion */
5627                 do {
5628                         next_token();
5629                 } while(token.type == T___extension__);
5630                 statement = parse_statement();
5631                 break;
5632
5633         DECLARATION_START
5634                 statement = parse_declaration_statement();
5635                 break;
5636
5637         default:
5638                 statement = parse_expression_statement();
5639                 break;
5640         }
5641
5642         assert(statement == NULL
5643                         || statement->base.source_position.input_name != NULL);
5644
5645         return statement;
5646 }
5647
5648 /**
5649  * Parse a compound statement.
5650  */
5651 static statement_t *parse_compound_statement(void)
5652 {
5653         compound_statement_t *const compound_statement
5654                 = allocate_ast_zero(sizeof(compound_statement[0]));
5655         compound_statement->statement.kind            = STATEMENT_COMPOUND;
5656         compound_statement->statement.source_position = token.source_position;
5657
5658         eat('{');
5659
5660         int      top        = environment_top();
5661         scope_t *last_scope = scope;
5662         set_scope(&compound_statement->scope);
5663
5664         statement_t *last_statement = NULL;
5665
5666         while(token.type != '}' && token.type != T_EOF) {
5667                 statement_t *statement = parse_statement();
5668                 if(statement == NULL)
5669                         continue;
5670
5671                 if(last_statement != NULL) {
5672                         last_statement->base.next = statement;
5673                 } else {
5674                         compound_statement->statements = statement;
5675                 }
5676
5677                 while(statement->base.next != NULL)
5678                         statement = statement->base.next;
5679
5680                 last_statement = statement;
5681         }
5682
5683         if(token.type == '}') {
5684                 next_token();
5685         } else {
5686                 errorf(compound_statement->statement.source_position, "end of file while looking for closing '}'");
5687         }
5688
5689         assert(scope == &compound_statement->scope);
5690         set_scope(last_scope);
5691         environment_pop_to(top);
5692
5693         return (statement_t*) compound_statement;
5694 }
5695
5696 /**
5697  * Initialize builtin types.
5698  */
5699 static void initialize_builtin_types(void)
5700 {
5701         type_intmax_t    = make_global_typedef("__intmax_t__",      type_long_long);
5702         type_size_t      = make_global_typedef("__SIZE_TYPE__",     type_unsigned_long);
5703         type_ssize_t     = make_global_typedef("__SSIZE_TYPE__",    type_long);
5704         type_ptrdiff_t   = make_global_typedef("__PTRDIFF_TYPE__",  type_long);
5705         type_uintmax_t   = make_global_typedef("__uintmax_t__",     type_unsigned_long_long);
5706         type_uptrdiff_t  = make_global_typedef("__UPTRDIFF_TYPE__", type_unsigned_long);
5707         type_wchar_t     = make_global_typedef("__WCHAR_TYPE__",    type_int);
5708         type_wint_t      = make_global_typedef("__WINT_TYPE__",     type_int);
5709
5710         type_intmax_t_ptr  = make_pointer_type(type_intmax_t,  TYPE_QUALIFIER_NONE);
5711         type_ptrdiff_t_ptr = make_pointer_type(type_ptrdiff_t, TYPE_QUALIFIER_NONE);
5712         type_ssize_t_ptr   = make_pointer_type(type_ssize_t,   TYPE_QUALIFIER_NONE);
5713         type_wchar_t_ptr   = make_pointer_type(type_wchar_t,   TYPE_QUALIFIER_NONE);
5714 }
5715
5716 /**
5717  * Check for unused functions in the given scope.
5718  */
5719 static void check_unused_functions(const scope_t *scope) {
5720         bool first_err = true;
5721         const declaration_t *declaration = scope->declarations;
5722
5723         for (; declaration != NULL; declaration = declaration->next) {
5724                 if (! declaration->used) {
5725                         if (declaration->storage_class == STORAGE_CLASS_STATIC) {
5726                                 const type_t *type = declaration->type;
5727
5728                                 if (is_type_function(type)) {
5729                                         if (first_err) {
5730                                                 first_err = false;
5731                                                 diagnosticf("%s: At top level:\n",
5732                                                         declaration->source_position.input_name);
5733                                         }
5734                                         warningf(declaration->source_position,
5735                                                 "'%Y' defined but not used",
5736                                                 declaration->symbol);
5737                                 }
5738                         }
5739                 }
5740         }
5741 }
5742
5743 /**
5744  * Parse a translation unit.
5745  */
5746 static translation_unit_t *parse_translation_unit(void)
5747 {
5748         translation_unit_t *unit = allocate_ast_zero(sizeof(unit[0]));
5749
5750         assert(global_scope == NULL);
5751         global_scope = &unit->scope;
5752
5753         assert(scope == NULL);
5754         set_scope(&unit->scope);
5755
5756         initialize_builtin_types();
5757
5758         while(token.type != T_EOF) {
5759                 if (token.type == ';') {
5760                         /* TODO error in strict mode */
5761                         warningf(HERE, "stray ';' outside of function");
5762                         next_token();
5763                 } else {
5764                         parse_external_declaration();
5765                 }
5766         }
5767
5768         assert(scope == &unit->scope);
5769         scope          = NULL;
5770         last_declaration = NULL;
5771
5772         assert(global_scope == &unit->scope);
5773         if (warning.unused_function) {
5774                 check_unused_functions(global_scope);
5775         }
5776         global_scope = NULL;
5777
5778         return unit;
5779 }
5780
5781 /**
5782  * Parse the input.
5783  *
5784  * @return  the translation unit or NULL if errors occurred.
5785  */
5786 translation_unit_t *parse(void)
5787 {
5788         environment_stack = NEW_ARR_F(stack_entry_t, 0);
5789         label_stack       = NEW_ARR_F(stack_entry_t, 0);
5790         diagnostic_count  = 0;
5791         error_count       = 0;
5792         warning_count     = 0;
5793
5794         type_set_output(stderr);
5795         ast_set_output(stderr);
5796
5797         lookahead_bufpos = 0;
5798         for(int i = 0; i < MAX_LOOKAHEAD + 2; ++i) {
5799                 next_token();
5800         }
5801         translation_unit_t *unit = parse_translation_unit();
5802
5803         DEL_ARR_F(environment_stack);
5804         DEL_ARR_F(label_stack);
5805
5806         if(error_count > 0)
5807                 return NULL;
5808
5809         return unit;
5810 }
5811
5812 /**
5813  * Initialize the parser.
5814  */
5815 void init_parser(void)
5816 {
5817         init_expression_parsers();
5818         obstack_init(&temp_obst);
5819
5820         symbol_t *const va_list_sym = symbol_table_insert("__builtin_va_list");
5821         type_valist = create_builtin_type(va_list_sym, type_void_ptr);
5822 }
5823
5824 /**
5825  * Terminate the parser.
5826  */
5827 void exit_parser(void)
5828 {
5829         obstack_free(&temp_obst, NULL);
5830 }