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