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