nsz Git - cparser/blob - parser.c

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