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