nsz Git - cparser/blob - parser.c

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