nsz Git - cparser/blob - parser.c

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