nsz Git - cparser/blob - parser.c

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