nsz Git - cparser/blob - parser.c

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