nsz Git - cparser/blob - parser.c

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