parse.c

   1 /*
   2  * Stupid C parser, version 1e-6.
   3  *
   4  * Let's see how hard this is to do.
   5  *
   6  * Copyright (C) 2003 Transmeta Corp.
   7  *
   8  *  Licensed under the Open Software License version 1.1
   9  */
  10
  11 #include <stdarg.h>
  12 #include <stdlib.h>
  13 #include <stdio.h>
  14 #include <string.h>
  15 #include <ctype.h>
  16 #include <unistd.h>
  17 #include <fcntl.h>
  18
  19 #include "lib.h"
  20 #include "token.h"
  21 #include "parse.h"
  22 #include "symbol.h"
  23 #include "scope.h"
  24 #include "expression.h"
  25
  26 static struct token *statement(struct token *token, struct statement **tree);
  27 static struct token *external_declaration(struct token *token, struct symbol_list **list);
  28
  29 struct statement *alloc_statement(struct position pos, int type)
  30 {
  31         struct statement *stmt = __alloc_statement(0);
  32         stmt->type = type;
  33         stmt->pos = pos;
  34         return stmt;
  35 }
  36
  37 static struct token *struct_declaration_list(struct token *token, struct symbol_list **list);
  38
  39 static struct symbol * indirect(struct position pos, struct ctype *ctype, int type)
  40 {
  41         struct symbol *sym = alloc_symbol(pos, type);
  42
  43         sym->ctype.base_type = ctype->base_type;
  44         sym->ctype.modifiers = ctype->modifiers & ~MOD_STORAGE;
  45
  46         ctype->base_type = sym;
  47         ctype->modifiers &= MOD_STORAGE;
  48         return sym;
  49 }
  50
  51 static struct symbol *lookup_or_create_symbol(enum namespace ns, enum type type, struct token *token)
  52 {
  53         struct symbol *sym = lookup_symbol(token->ident, ns);
  54         if (!sym) {
  55                 sym = alloc_symbol(token->pos, type);
  56                 sym->ident = token->ident;
  57                 bind_symbol(sym, token->ident, ns);
  58         }
  59         return sym;
  60 }
  61
  62 /*
  63  * NOTE! NS_LABEL is not just a different namespace,
  64  * it also ends up using function scope instead of the
  65  * regular symbol scope.
  66  */
  67 static struct symbol *label_symbol(struct token *token)
  68 {
  69         return lookup_or_create_symbol(NS_LABEL, SYM_LABEL, token);
  70 }
  71
  72 struct token *struct_union_enum_specifier(enum namespace ns, enum type type,
  73         struct token *token, struct ctype *ctype,
  74         struct token *(*parse)(struct token *, struct symbol *))
  75 {
  76         struct symbol *sym;
  77
  78         ctype->modifiers = 0;
  79         if (token_type(token) == TOKEN_IDENT) {
  80                 sym = lookup_or_create_symbol(ns, type, token);
  81                 token = token->next;
  82                 ctype->base_type = sym;
  83                 if (match_op(token, '{')) {
  84                         token = parse(token->next, sym);
  85                         token = expect(token, '}', "at end of struct-union-enum-specifier");
  86                 }
  87                 return token;
  88         }
  89
  90         // private struct/union/enum type
  91         if (!match_op(token, '{')) {
  92                 warn(token->pos, "expected declaration");
  93                 ctype->base_type = &bad_type;
  94                 return token;
  95         }
  96
  97         sym = alloc_symbol(token->pos, type);
  98         token = parse(token->next, sym);
  99         ctype->base_type = sym;
 100         return expect(token, '}', "at end of specifier");
 101 }
 102
 103 static struct token *parse_struct_declaration(struct token *token, struct symbol *sym)
 104 {
 105         return struct_declaration_list(token, &sym->symbol_list);
 106 }
 107
 108 struct token *struct_or_union_specifier(enum type type, struct token *token, struct ctype *ctype)
 109 {
 110         return struct_union_enum_specifier(NS_STRUCT, type, token, ctype, parse_struct_declaration);
 111 }
 112
 113 static struct token *parse_enum_declaration(struct token *token, struct symbol *parent)
 114 {
 115         int nextval = 0;
 116         while (token_type(token) == TOKEN_IDENT) {
 117                 struct token *next = token->next;
 118                 struct symbol *sym;
 119
 120                 sym = alloc_symbol(token->pos, SYM_NODE);
 121                 bind_symbol(sym, token->ident, NS_SYMBOL);
 122                 sym->ctype.base_type = parent;
 123
 124                 if (match_op(next, '=')) {
 125                         struct expression *expr;
 126                         next = constant_expression(next->next, &expr);
 127                         nextval = get_expression_value(expr);
 128                 }
 129                 sym->value = nextval;
 130
 131                 token = next;
 132                 if (!match_op(token, ','))
 133                         break;
 134                 token = token->next;
 135                 nextval = nextval + 1;
 136         }
 137         return token;
 138 }
 139
 140 struct token *enum_specifier(struct token *token, struct ctype *ctype)
 141 {
 142         return struct_union_enum_specifier(NS_ENUM, SYM_ENUM, token, ctype, parse_enum_declaration);
 143 }
 144
 145 struct token *typeof_specifier(struct token *token, struct ctype *ctype)
 146 {
 147         struct symbol *sym;
 148
 149         if (!match_op(token, '(')) {
 150                 warn(token->pos, "expected '(' after typeof");
 151                 return token;
 152         }
 153         if (lookup_type(token->next)) {
 154                 token = typename(token->next, &sym);
 155                 *ctype = sym->ctype;
 156         } else {
 157                 struct symbol *typeof_sym = alloc_symbol(token->pos, SYM_TYPEOF);
 158                 token = parse_expression(token->next, &typeof_sym->initializer);
 159
 160                 ctype->modifiers = 0;
 161                 ctype->base_type = typeof_sym;
 162         }
 163         return expect(token, ')', "after typeof");
 164 }
 165
 166 static void handle_attribute(struct ctype *ctype, struct ident *attribute, struct expression *expr)
 167 {
 168         if (match_string_ident(attribute, "packed")) {
 169                 ctype->alignment = 1;
 170                 return;
 171         }
 172         if (match_string_ident(attribute, "aligned")) {
 173                 ctype->alignment = get_expression_value(expr);
 174                 return;
 175         }
 176         if (match_string_ident(attribute, "nocast")) {
 177                 ctype->modifiers |= MOD_NOCAST;
 178                 return;
 179         }
 180         if (match_string_ident(attribute, "noderef")) {
 181                 ctype->modifiers |= MOD_NODEREF;
 182                 return;
 183         }
 184         if (match_string_ident(attribute, "address_space")) {
 185                 ctype->as = get_expression_value(expr);
 186                 return;
 187         }
 188         if (match_string_ident(attribute, "context")) {
 189                 if (expr->type == EXPR_COMMA) {
 190                         int mask = get_expression_value(expr->left);
 191                         int value = get_expression_value(expr->right);
 192                         if (value & ~mask) {
 193                                 warn(expr->pos, "nonsense attribute types");
 194                                 return;
 195                         }
 196                         ctype->contextmask |= mask;
 197                         ctype->context |= value;
 198                         return;
 199                 }
 200         }
 201 }
 202
 203
 204 struct token *attribute_specifier(struct token *token, struct ctype *ctype)
 205 {
 206         ctype->modifiers = 0;
 207         token = expect(token, '(', "after attribute");
 208         token = expect(token, '(', "after attribute");
 209
 210         for (;;) {
 211                 struct ident *attribute_name;
 212                 struct expression *attribute_expr;
 213
 214                 if (eof_token(token))
 215                         break;
 216                 if (match_op(token, ';'))
 217                         break;
 218                 if (token_type(token) != TOKEN_IDENT)
 219                         break;
 220                 attribute_name = token->ident;
 221                 token = token->next;
 222                 attribute_expr = NULL;
 223                 if (match_op(token, '('))
 224                         token = parens_expression(token, &attribute_expr, "in attribute");
 225                 handle_attribute(ctype, attribute_name, attribute_expr);
 226                 if (!match_op(token, ','))
 227                         break;
 228                 token = token->next;
 229         }
 230
 231         token = expect(token, ')', "after attribute");
 232         token = expect(token, ')', "after attribute");
 233         return token;
 234 }
 235
 236 #define MOD_SPECIALBITS (MOD_STRUCTOF | MOD_UNIONOF | MOD_ENUMOF | MOD_ATTRIBUTE | MOD_TYPEOF)
 237 #define MOD_SPECIFIER (MOD_CHAR | MOD_SHORT | MOD_LONG | MOD_LONGLONG | MOD_SIGNED | MOD_UNSIGNED)
 238
 239 struct symbol * ctype_integer(unsigned int spec)
 240 {
 241         static struct symbol *const integer_ctypes[][2] = {
 242                 { &llong_ctype, &ullong_ctype },
 243                 { &long_ctype,  &ulong_ctype  },
 244                 { &short_ctype, &ushort_ctype },
 245                 { &char_ctype,  &uchar_ctype  },
 246                 { &int_ctype,   &uint_ctype   },
 247         };
 248         struct symbol *const (*ctype)[2];
 249
 250         ctype = integer_ctypes;
 251         if (!(spec & MOD_LONGLONG)) {
 252                 ctype++;
 253                 if (!(spec & MOD_LONG)) {
 254                         ctype++;
 255                         if (!(spec & MOD_SHORT)) {
 256                                 ctype++;
 257                                 if (!(spec & MOD_CHAR))
 258                                         ctype++;
 259                         }
 260                 }
 261         }
 262         return ctype[0][(spec & MOD_UNSIGNED) != 0];
 263 }
 264
 265 struct symbol * ctype_fp(unsigned int spec)
 266 {
 267         if (spec & MOD_LONGLONG)
 268                 return &ldouble_ctype;
 269         if (spec & MOD_LONG)
 270                 return &double_ctype;
 271         return &float_ctype;
 272 }
 273
 274 static void apply_ctype(struct position pos, struct ctype *thistype, struct ctype *ctype)
 275 {
 276         unsigned long mod = thistype->modifiers;
 277
 278         if (mod) {
 279                 unsigned long old = ctype->modifiers;
 280                 unsigned long extra = 0, dup;
 281
 282                 if (mod & old & MOD_LONG) {
 283                         extra = MOD_LONGLONG | MOD_LONG;
 284                         mod &= ~MOD_LONG;
 285                         old &= ~MOD_LONG;
 286                 }
 287                 dup = (mod & old) | (extra & old) | (extra & mod);
 288                 if (dup)
 289                         warn(pos, "Just how %sdo you want this type to be?",
 290                                 modifier_string(dup));
 291                 ctype->modifiers = old | mod | extra;
 292         }
 293
 294         /* Context mask and value */
 295         if ((ctype->context ^ thistype->context) & (ctype->contextmask & thistype->contextmask)) {
 296                 warn(pos, "inconsistend attribute types");
 297                 thistype->context = 0;
 298                 thistype->contextmask = 0;
 299         }
 300         ctype->context |= thistype->context;
 301         ctype->contextmask |= thistype->contextmask;
 302
 303         /* Alignment */
 304         if (thistype->alignment & (thistype->alignment-1)) {
 305                 warn(pos, "I don't like non-power-of-2 alignments");
 306                 thistype->alignment = 0;
 307         }
 308         if (thistype->alignment > ctype->alignment)
 309                 ctype->alignment = thistype->alignment;
 310
 311         /* Address space */
 312         ctype->as = thistype->as;
 313 }
 314
 315
 316 static struct token *declaration_specifiers(struct token *next, struct ctype *ctype, int qual)
 317 {
 318         struct token *token;
 319
 320         while ( (token = next) != NULL ) {
 321                 struct ctype thistype;
 322                 struct ident *ident;
 323                 struct symbol *s, *type;
 324                 unsigned long mod;
 325
 326                 next = token->next;
 327                 if (token_type(token) != TOKEN_IDENT)
 328                         break;
 329                 ident = token->ident;
 330
 331                 s = lookup_symbol(ident, NS_TYPEDEF);
 332                 if (!s)
 333                         break;
 334                 thistype = s->ctype;
 335                 mod = thistype.modifiers;
 336                 if (qual && (mod & ~(MOD_ATTRIBUTE | MOD_CONST | MOD_VOLATILE)))
 337                         break;
 338                 if (mod & MOD_SPECIALBITS) {
 339                         if (mod & MOD_STRUCTOF)
 340                                 next = struct_or_union_specifier(SYM_STRUCT, next, &thistype);
 341                         else if (mod & MOD_UNIONOF)
 342                                 next = struct_or_union_specifier(SYM_UNION, next, &thistype);
 343                         else if (mod & MOD_ENUMOF)
 344                                 next = enum_specifier(next, &thistype);
 345                         else if (mod & MOD_ATTRIBUTE)
 346                                 next = attribute_specifier(next, &thistype);
 347                         else if (mod & MOD_TYPEOF)
 348                                 next = typeof_specifier(next, &thistype);
 349                         mod = thistype.modifiers;
 350                 }
 351                 type = thistype.base_type;
 352                 if (type) {
 353                         if (qual)
 354                                 break;
 355                         if (type != ctype->base_type) {
 356                                 if (ctype->base_type) {
 357                                         warn(token->pos, "Strange mix of types");
 358                                         continue;
 359                                 }
 360                                 ctype->base_type = type;
 361                         }
 362                 }
 363
 364                 apply_ctype(token->pos, &thistype, ctype);
 365         }
 366
 367         /* Turn the "virtual types" into real types with real sizes etc */
 368         if (!ctype->base_type && (ctype->modifiers & MOD_SPECIFIER))
 369                 ctype->base_type = &int_type;
 370
 371         if (ctype->base_type == &int_type) {
 372                 ctype->base_type = ctype_integer(ctype->modifiers & MOD_SPECIFIER);
 373                 ctype->modifiers &= ~MOD_SPECIFIER;
 374                 return token;
 375         }
 376         if (ctype->base_type == &fp_type) {
 377                 ctype->base_type = ctype_fp(ctype->modifiers & MOD_SPECIFIER);
 378                 ctype->modifiers &= ~MOD_SPECIFIER;
 379                 return token;
 380         }
 381         return token;
 382 }
 383
 384 static struct token *abstract_array_declarator(struct token *token, struct symbol *sym)
 385 {
 386         struct expression *expr = NULL;
 387
 388         token = parse_expression(token, &expr);
 389         if (expr)
 390                 sym->array_size = get_expression_value(expr);
 391         else
 392                 sym->array_size = -1;
 393         return token;
 394 }
 395
 396 static struct token *parameter_type_list(struct token *, struct symbol *);
 397 static struct token *declarator(struct token *token, struct symbol **tree, struct ident **p);
 398
 399 static struct token *direct_declarator(struct token *token, struct symbol **tree, struct ident **p)
 400 {
 401         struct ctype *ctype = &(*tree)->ctype;
 402
 403         if (p && token_type(token) == TOKEN_IDENT) {
 404                 *p = token->ident;
 405                 token = token->next;
 406         }
 407
 408         for (;;) {
 409                 if (match_ident(token, &__attribute___ident) || match_ident(token, &__attribute_ident)) {
 410                         struct ctype thistype = { 0, };
 411                         token = attribute_specifier(token->next, &thistype);
 412                         apply_ctype(token->pos, &thistype, ctype);
 413                         continue;
 414                 }
 415                 if (token_type(token) != TOKEN_SPECIAL)
 416                         return token;
 417
 418                 /*
 419                  * This can be either a parameter list or a grouping.
 420                  * For the direct (non-abstract) case, we know if must be
 421                  * a paramter list if we already saw the identifier.
 422                  * For the abstract case, we know if must be a parameter
 423                  * list if it is empty or starts with a type.
 424                  */
 425                 if (token->special == '(') {
 426                         struct symbol *sym;
 427                         struct token *next = token->next;
 428                         int fn = (p && *p) || match_op(next, ')') || lookup_type(next);
 429
 430                         if (!fn) {
 431                                 struct symbol *base_type = ctype->base_type;
 432                                 token = declarator(next, tree, p);
 433                                 token = expect(token, ')', "in nested declarator");
 434                                 while (ctype->base_type != base_type)
 435                                         ctype = &ctype->base_type->ctype;
 436                                 p = NULL;
 437                                 continue;
 438                         }
 439
 440                         sym = indirect(token->pos, ctype, SYM_FN);
 441                         token = parameter_type_list(next, sym);
 442                         token = expect(token, ')', "in function declarator");
 443                         continue;
 444                 }
 445                 if (token->special == '[') {
 446                         struct symbol *array = indirect(token->pos, ctype, SYM_ARRAY);
 447                         token = abstract_array_declarator(token->next, array);
 448                         token = expect(token, ']', "in abstract_array_declarator");
 449                         ctype = &array->ctype;
 450                         continue;
 451                 }
 452                 if (token->special == ':') {
 453                         struct symbol *bitfield;
 454                         struct expression *expr;
 455                         bitfield = indirect(token->pos, ctype, SYM_BITFIELD);
 456                         token = conditional_expression(token->next, &expr);
 457                         bitfield->fieldwidth = get_expression_value(expr);
 458                         continue;
 459                 }
 460                 break;
 461         }
 462         if (p) {
 463                 (*tree)->ident = *p;
 464         }
 465         return token;
 466 }
 467
 468 static struct token *pointer(struct token *token, struct ctype *ctype)
 469 {
 470         unsigned long modifiers;
 471         struct symbol *base_type;
 472
 473         modifiers = ctype->modifiers & ~(MOD_TYPEDEF | MOD_ATTRIBUTE);
 474         base_type = ctype->base_type;
 475         ctype->modifiers = modifiers;
 476
 477         while (match_op(token,'*')) {
 478                 struct symbol *ptr = alloc_symbol(token->pos, SYM_PTR);
 479                 ptr->ctype.modifiers = modifiers & ~MOD_STORAGE;
 480                 ptr->ctype.as = ctype->as;
 481                 ptr->ctype.context = ctype->context;
 482                 ptr->ctype.contextmask = ctype->contextmask;
 483                 ptr->ctype.base_type = base_type;
 484
 485                 base_type = ptr;
 486                 ctype->modifiers = modifiers & MOD_STORAGE;
 487                 ctype->base_type = base_type;
 488                 ctype->as = 0;
 489                 ctype->context = 0;
 490                 ctype->contextmask = 0;
 491
 492                 token = declaration_specifiers(token->next, ctype, 1);
 493         }
 494         return token;
 495 }
 496
 497 static struct token *declarator(struct token *token, struct symbol **tree, struct ident **p)
 498 {
 499         token = pointer(token, &(*tree)->ctype);
 500         return direct_declarator(token, tree, p);
 501 }
 502
 503 static struct token *struct_declaration_list(struct token *token, struct symbol_list **list)
 504 {
 505         while (!match_op(token, '}')) {
 506                 struct ctype ctype = {0, };
 507
 508                 token = declaration_specifiers(token, &ctype, 0);
 509                 for (;;) {
 510                         struct ident *ident = NULL;
 511                         struct symbol *decl = alloc_symbol(token->pos, SYM_NODE);
 512                         decl->ctype = ctype;
 513                         token = pointer(token, &decl->ctype);
 514                         token = direct_declarator(token, &decl, &ident);
 515                         if (match_op(token, ':')) {
 516                                 struct expression *expr;
 517                                 token = parse_expression(token->next, &expr);
 518                         }
 519                         add_symbol(list, decl);
 520                         if (!match_op(token, ','))
 521                                 break;
 522                         token = token->next;
 523                 }
 524                 if (!match_op(token, ';'))
 525                         break;
 526                 token = token->next;
 527         }
 528         return token;
 529 }
 530
 531 static struct token *parameter_declaration(struct token *token, struct symbol **tree)
 532 {
 533         struct ident *ident = NULL;
 534         struct symbol *sym;
 535         struct ctype ctype = { 0, };
 536
 537         token = declaration_specifiers(token, &ctype, 0);
 538         sym = alloc_symbol(token->pos, SYM_NODE);
 539         sym->ctype = ctype;
 540         *tree = sym;
 541         token = pointer(token, &sym->ctype);
 542         token = direct_declarator(token, tree, &ident);
 543         return token;
 544 }
 545
 546 struct token *typename(struct token *token, struct symbol **p)
 547 {
 548         struct symbol *sym = alloc_symbol(token->pos, SYM_NODE);
 549         *p = sym;
 550         token = declaration_specifiers(token, &sym->ctype, 0);
 551         return declarator(token, &sym, NULL);
 552 }
 553
 554 struct token *expression_statement(struct token *token, struct expression **tree)
 555 {
 556         token = parse_expression(token, tree);
 557         return expect(token, ';', "at end of statement");
 558 }
 559
 560 static struct token *parse_asm_operands(struct token *token, struct statement *stmt)
 561 {
 562         struct expression *expr;
 563
 564         /* Allow empty operands */
 565         if (match_op(token->next, ':') || match_op(token->next, ')'))
 566                 return token->next;
 567         do {
 568                 token = primary_expression(token->next, &expr);
 569                 token = parens_expression(token, &expr, "in asm parameter");
 570         } while (match_op(token, ','));
 571         return token;
 572 }
 573
 574 static struct token *parse_asm_clobbers(struct token *token, struct statement *stmt)
 575 {
 576         struct expression *expr;
 577
 578         do {
 579                 token = primary_expression(token->next, &expr);
 580         } while (match_op(token, ','));
 581         return token;
 582 }
 583
 584 /* Make a statement out of an expression */
 585 static struct statement *make_statement(struct expression *expr)
 586 {
 587         struct statement *stmt;
 588
 589         if (!expr)
 590                 return NULL;
 591         stmt = alloc_statement(expr->pos, STMT_EXPRESSION);
 592         stmt->expression = expr;
 593         return stmt;
 594 }
 595
 596 /*
 597  * All iterators have two symbols associated with them:
 598  * the "continue" and "break" symbols, which are targets
 599  * for continue and break statements respectively.
 600  *
 601  * They are in a special name-space, but they follow
 602  * all the normal visibility rules, so nested iterators
 603  * automatically work right.
 604  */
 605 static void start_iterator(struct statement *stmt)
 606 {
 607         struct symbol *cont, *brk;
 608
 609         start_symbol_scope();
 610         cont = alloc_symbol(stmt->pos, SYM_NODE);
 611         cont->ident = &continue_ident;
 612         bind_symbol(cont, &continue_ident, NS_ITERATOR);
 613         brk = alloc_symbol(stmt->pos, SYM_NODE);
 614         brk->ident = &break_ident;
 615         bind_symbol(brk, &break_ident, NS_ITERATOR);
 616
 617         stmt->type = STMT_ITERATOR;
 618         stmt->iterator_break = brk;
 619         stmt->iterator_continue = cont;
 620 }
 621
 622 static void end_iterator(struct statement *stmt)
 623 {
 624         end_symbol_scope();
 625 }
 626
 627 /*
 628  * A "switch()" statement, like an iterator, has a
 629  * the "break" symbol associated with it. It works
 630  * exactly like the iterator break - it's the target
 631  * for any break-statements in scope, and means that
 632  * "break" handling doesn't even need to know whether
 633  * it's breaking out of an iterator or a switch.
 634  *
 635  * In addition, the "case" symbol is a marker for the
 636  * case/default statements to find the switch statement
 637  * that they are associated with.
 638  */
 639 static void start_switch(struct statement *stmt)
 640 {
 641         struct symbol *brk, *switch_case;
 642
 643         start_symbol_scope();
 644         brk = alloc_symbol(stmt->pos, SYM_NODE);
 645         brk->ident = &break_ident;
 646         bind_symbol(brk, &break_ident, NS_ITERATOR);
 647
 648         switch_case = alloc_symbol(stmt->pos, SYM_NODE);
 649         switch_case->ident = &case_ident;
 650         bind_symbol(switch_case, &case_ident, NS_ITERATOR);
 651         switch_case->stmt = stmt;
 652
 653         stmt->type = STMT_SWITCH;
 654         stmt->switch_break = brk;
 655         stmt->switch_case = switch_case;
 656 }
 657
 658 static void end_switch(struct statement *stmt)
 659 {
 660         if (!stmt->switch_case->symbol_list)
 661                 warn(stmt->pos, "switch with no cases");
 662         end_symbol_scope();
 663 }
 664
 665 static void add_case_statement(struct statement *stmt)
 666 {
 667         struct symbol *target = lookup_symbol(&case_ident, NS_ITERATOR);
 668         struct symbol *sym;
 669
 670         if (!target) {
 671                 warn(stmt->pos, "not in switch scope");
 672                 return;
 673         }
 674         sym = alloc_symbol(stmt->pos, SYM_NODE);
 675         add_symbol(&target->symbol_list, sym);
 676         sym->stmt = stmt;
 677         stmt->case_label = sym;
 678 }
 679
 680 static struct token *parse_for_statement(struct token *token, struct statement *stmt)
 681 {
 682         struct symbol_list *syms;
 683         struct expression *e1, *e2, *e3;
 684         struct statement *iterator;
 685
 686         start_iterator(stmt);
 687         token = expect(token->next, '(', "after 'for'");
 688
 689         syms = NULL;
 690         e1 = NULL;
 691         /* C99 variable declaration? */
 692         if (lookup_type(token)) {
 693                 token = external_declaration(token, &syms);
 694         } else {
 695                 token = parse_expression(token, &e1);
 696                 token = expect(token, ';', "in 'for'");
 697         }
 698         token = parse_expression(token, &e2);
 699         token = expect(token, ';', "in 'for'");
 700         token = parse_expression(token, &e3);
 701         token = expect(token, ')', "in 'for'");
 702         token = statement(token, &iterator);
 703
 704         stmt->iterator_syms = syms;
 705         stmt->iterator_pre_statement = make_statement(e1);
 706         stmt->iterator_pre_condition = e2;
 707         stmt->iterator_post_statement = make_statement(e3);
 708         stmt->iterator_post_condition = e2;
 709         stmt->iterator_statement = iterator;
 710         end_iterator(stmt);
 711
 712         return token;
 713 }
 714
 715 struct token *parse_while_statement(struct token *token, struct statement *stmt)
 716 {
 717         struct expression *expr;
 718         struct statement *iterator;
 719
 720         start_iterator(stmt);
 721         token = parens_expression(token->next, &expr, "after 'while'");
 722         token = statement(token, &iterator);
 723
 724         stmt->iterator_pre_condition = expr;
 725         stmt->iterator_post_condition = expr;
 726         stmt->iterator_statement = iterator;
 727         end_iterator(stmt);
 728
 729         return token;
 730 }
 731
 732 struct token *parse_do_statement(struct token *token, struct statement *stmt)
 733 {
 734         struct expression *expr;
 735         struct statement *iterator;
 736
 737         start_iterator(stmt);
 738         token = statement(token->next, &iterator);
 739         if (token_type(token) == TOKEN_IDENT && token->ident == &while_ident)
 740                 token = token->next;
 741         else
 742                 warn(token->pos, "expected 'while' after 'do'");
 743         token = parens_expression(token, &expr, "after 'do-while'");
 744
 745         stmt->iterator_post_condition = expr;
 746         stmt->iterator_statement = iterator;
 747         end_iterator(stmt);
 748
 749         return expect(token, ';', "after statement");
 750 }
 751
 752 static struct token *statement(struct token *token, struct statement **tree)
 753 {
 754         struct statement *stmt = alloc_statement(token->pos, STMT_NONE);
 755
 756         *tree = stmt;
 757         if (token_type(token) == TOKEN_IDENT) {
 758                 if (token->ident == &if_ident) {
 759                         stmt->type = STMT_IF;
 760                         token = parens_expression(token->next, &stmt->if_conditional, "after if");
 761                         token = statement(token, &stmt->if_true);
 762                         if (token_type(token) != TOKEN_IDENT)
 763                                 return token;
 764                         if (token->ident != &else_ident)
 765                                 return token;
 766                         return statement(token->next, &stmt->if_false);
 767                 }
 768                 if (token->ident == &return_ident) {
 769                         stmt->type = STMT_RETURN;
 770                         return expression_statement(token->next, &stmt->expression);
 771                 }
 772                 if (token->ident == &break_ident || token->ident == &continue_ident) {
 773                         struct symbol *target = lookup_symbol(token->ident, NS_ITERATOR);
 774                         stmt->type = STMT_GOTO;
 775                         stmt->goto_label = target;
 776                         if (!target)
 777                                 warn(stmt->pos, "break/continue not in iterator scope");
 778                         return expect(token->next, ';', "at end of statement");
 779                 }
 780                 if (token->ident == &default_ident) {
 781                         token = token->next;
 782                         goto default_statement;
 783                 }
 784                 if (token->ident == &case_ident) {
 785                         token = parse_expression(token->next, &stmt->case_expression);
 786                         if (match_op(token, SPECIAL_ELLIPSIS))
 787                                 token = parse_expression(token->next, &stmt->case_to);
 788 default_statement:
 789                         stmt->type = STMT_CASE;
 790                         token = expect(token, ':', "after default/case");
 791                         add_case_statement(stmt);
 792                         return statement(token, &stmt->case_statement);
 793                 }
 794                 if (token->ident == &switch_ident) {
 795                         stmt->type = STMT_SWITCH;
 796                         start_switch(stmt);
 797                         token = parens_expression(token->next, &stmt->switch_expression, "after 'switch'");
 798                         token = statement(token, &stmt->switch_statement);
 799                         end_switch(stmt);
 800                         return token;
 801                 }
 802                 if (token->ident == &for_ident)
 803                         return parse_for_statement(token, stmt);
 804
 805                 if (token->ident == &while_ident)
 806                         return parse_while_statement(token, stmt);
 807
 808                 if (token->ident == &do_ident)
 809                         return parse_do_statement(token, stmt);
 810
 811                 if (token->ident == &goto_ident) {
 812                         stmt->type = STMT_GOTO;
 813                         token = token->next;
 814                         if (token_type(token) == TOKEN_IDENT) {
 815                                 stmt->goto_label = label_symbol(token);
 816                                 token = token->next;
 817                         } else
 818                                 warn(token->pos, "invalid label");
 819                         return expect(token, ';', "at end of statement");
 820                 }
 821                 if (token->ident == &asm_ident || token->ident == &__asm___ident || token->ident == &__asm_ident) {
 822                         struct expression *expr;
 823                         stmt->type = STMT_ASM;
 824                         token = token->next;
 825                         if (token_type(token) == TOKEN_IDENT) {
 826                                 if (token->ident == &__volatile___ident || token->ident == &volatile_ident)
 827                                         token = token->next;
 828                         }
 829                         token = expect(token, '(', "after asm");
 830                         token = parse_expression(token->next, &expr);
 831                         if (match_op(token, ':'))
 832                                 token = parse_asm_operands(token, stmt);
 833                         if (match_op(token, ':'))
 834                                 token = parse_asm_operands(token, stmt);
 835                         if (match_op(token, ':'))
 836                                 token = parse_asm_clobbers(token, stmt);
 837                         token = expect(token, ')', "after asm");
 838                         return expect(token, ';', "at end of asm-statement");
 839                 }
 840                 if (match_op(token->next, ':')) {
 841                         stmt->type = STMT_LABEL;
 842                         stmt->label_identifier = label_symbol(token);
 843                         return statement(token->next->next, &stmt->label_statement);
 844                 }
 845         }
 846
 847         if (match_op(token, '{')) {
 848                 stmt->type = STMT_COMPOUND;
 849                 start_symbol_scope();
 850                 token = compound_statement(token->next, stmt);
 851                 end_symbol_scope();
 852
 853                 return expect(token, '}', "at end of compound statement");
 854         }
 855
 856         stmt->type = STMT_EXPRESSION;
 857         return expression_statement(token, &stmt->expression);
 858 }
 859
 860 struct token * statement_list(struct token *token, struct statement_list **list)
 861 {
 862         for (;;) {
 863                 struct statement * stmt;
 864                 if (eof_token(token))
 865                         break;
 866                 if (match_op(token, '}'))
 867                         break;
 868                 token = statement(token, &stmt);
 869                 add_statement(list, stmt);
 870         }
 871         return token;
 872 }
 873
 874 static struct token *parameter_type_list(struct token *token, struct symbol *fn)
 875 {
 876         struct symbol_list **list = &fn->arguments;
 877         for (;;) {
 878                 struct symbol *sym = alloc_symbol(token->pos, SYM_NODE);
 879
 880                 if (match_op(token, SPECIAL_ELLIPSIS)) {
 881                         fn->variadic = 1;
 882                         token = token->next;
 883                         break;
 884                 }
 885
 886                 token = parameter_declaration(token, &sym);
 887                 /* Special case: (void) */
 888                 if (!*list && !sym->ident && sym->ctype.base_type == &void_ctype)
 889                         break;
 890                 add_symbol(list, sym);
 891                 if (!match_op(token, ','))
 892                         break;
 893                 token = token->next;
 894
 895         }
 896         return token;
 897 }
 898
 899 struct token *compound_statement(struct token *token, struct statement *stmt)
 900 {
 901         while (!eof_token(token)) {
 902                 if (!lookup_type(token))
 903                         break;
 904                 token = external_declaration(token, &stmt->syms);
 905         }
 906         token = statement_list(token, &stmt->stmts);
 907         return token;
 908 }
 909
 910 static struct expression *identifier_expression(struct token *token)
 911 {
 912         struct expression *expr = alloc_expression(token->pos, EXPR_IDENTIFIER);
 913         expr->expr_ident = token->ident;
 914         return expr;
 915 }
 916
 917 static struct expression *index_expression(struct expression *from, struct expression *to)
 918 {
 919         int idx_from, idx_to;
 920         struct expression *expr = alloc_expression(from->pos, EXPR_INDEX);
 921
 922         idx_from = get_expression_value(from);
 923         idx_to = idx_from;
 924         if (to) {
 925                 idx_to = get_expression_value(to);
 926                 if (idx_to < idx_from || idx_from < 0)
 927                         warn(from->pos, "nonsense array initializer index range");
 928         }
 929         expr->idx_from = idx_from;
 930         expr->idx_to = idx_to;
 931         return expr;
 932 }
 933
 934 static struct token *initializer_list(struct expression_list **list, struct token *token)
 935 {
 936         for (;;) {
 937                 struct token *next = token->next;
 938                 struct expression *expr;
 939
 940                 if (match_op(token, '.') && (token_type(next) == TOKEN_IDENT) && match_op(next->next, '=')) {
 941                         add_expression(list, identifier_expression(next));
 942                         token = next->next->next;
 943                 } else if ((token_type(token) == TOKEN_IDENT) && match_op(next, ':')) {
 944                         add_expression(list, identifier_expression(token));
 945                         token = next->next;
 946                 } else if (match_op(token, '[')) {
 947                         struct expression *from = NULL, *to = NULL;
 948                         token = constant_expression(token->next, &from);
 949                         if (match_op(token, SPECIAL_ELLIPSIS))
 950                                 token = constant_expression(token->next, &to);
 951                         add_expression(list, index_expression(from, to));
 952                         token = expect(token, ']', "at end of initializer index");
 953                         token = expect(token, '=', "at end of initializer index");
 954                 }
 955
 956                 expr = NULL;
 957                 token = initializer(&expr, token);
 958                 if (!expr)
 959                         break;
 960                 add_expression(list, expr);
 961                 if (!match_op(token, ','))
 962                         break;
 963                 token = token->next;
 964         }
 965         return token;
 966 }
 967
 968 struct token *initializer(struct expression **tree, struct token *token)
 969 {
 970         if (match_op(token, '{')) {
 971                 struct expression *expr = alloc_expression(token->pos, EXPR_INITIALIZER);
 972                 *tree = expr;
 973                 token = initializer_list(&expr->expr_list, token->next);
 974                 return expect(token, '}', "at end of initializer");
 975         }
 976         return assignment_expression(token, tree);
 977 }
 978
 979 static void declare_argument(struct symbol *sym, void *data, int flags)
 980 {
 981         struct symbol *decl = data;
 982
 983         if (!sym->ident) {
 984                 warn(decl->pos, "no identifier for function argument");
 985                 return;
 986         }
 987         bind_symbol(sym, sym->ident, NS_SYMBOL);
 988 }
 989
 990 static struct token *external_declaration(struct token *token, struct symbol_list **list)
 991 {
 992         struct ident *ident = NULL;
 993         struct symbol *decl;
 994         struct ctype ctype = { 0, };
 995         struct symbol *base_type;
 996         int is_typedef;
 997
 998         /* Parse declaration-specifiers, if any */
 999         token = declaration_specifiers(token, &ctype, 0);
1000         decl = alloc_symbol(token->pos, SYM_NODE);
1001         decl->ctype = ctype;
1002         token = pointer(token, &decl->ctype);
1003         token = declarator(token, &decl, &ident);
1004
1005         /* Just a type declaration? */
1006         if (!ident)
1007                 return expect(token, ';', "end of type declaration");
1008
1009         decl->ident = ident;
1010
1011         /* type define declaration? */
1012         is_typedef = (ctype.modifiers & MOD_TYPEDEF) != 0;
1013         bind_symbol(decl, ident, is_typedef ? NS_TYPEDEF: NS_SYMBOL);
1014
1015         base_type = decl->ctype.base_type;
1016         if (!is_typedef && base_type && base_type->type == SYM_FN) {
1017                 if (match_op(token, '{')) {
1018                         if (decl->ctype.modifiers & MOD_EXTERN) {
1019                                 if (!(decl->ctype.modifiers & MOD_INLINE))
1020                                         warn(decl->pos, "function with external linkage has definition");
1021                         }
1022                         if (!(decl->ctype.modifiers & MOD_STATIC))
1023                                 decl->ctype.modifiers |= MOD_EXTERN;
1024                         base_type->stmt = alloc_statement(token->pos, STMT_COMPOUND);
1025                         start_function_scope();
1026                         symbol_iterate(base_type->arguments, declare_argument, decl);
1027                         token = compound_statement(token->next, base_type->stmt);
1028                         end_function_scope();
1029                         if (!(decl->ctype.modifiers & MOD_INLINE))
1030                                 add_symbol(list, decl);
1031                         check_declaration(decl);
1032                         return expect(token, '}', "at end of function");
1033                 }
1034                 if (!(decl->ctype.modifiers & MOD_STATIC))
1035                         decl->ctype.modifiers |= MOD_EXTERN;
1036         }
1037
1038         for (;;) {
1039                 if (!is_typedef && match_op(token, '=')) {
1040                         if (decl->ctype.modifiers & MOD_EXTERN) {
1041                                 warn(decl->pos, "symbol with external linkage has initializer");
1042                                 decl->ctype.modifiers &= ~MOD_EXTERN;
1043                         }
1044                         token = initializer(&decl->initializer, token->next);
1045                 }
1046                 if (!is_typedef && !(decl->ctype.modifiers & (MOD_EXTERN | MOD_INLINE)))
1047                         add_symbol(list, decl);
1048                 check_declaration(decl);
1049
1050                 if (!match_op(token, ','))
1051                         break;
1052
1053                 ident = NULL;
1054                 decl = alloc_symbol(token->pos, SYM_NODE);
1055                 decl->ctype = ctype;
1056                 token = pointer(token, &decl->ctype);
1057                 token = declarator(token->next, &decl, &ident);
1058                 if (!ident) {
1059                         warn(token->pos, "expected identifier name in type definition");
1060                         return token;
1061                 }
1062
1063                 bind_symbol(decl, ident, is_typedef ? NS_TYPEDEF: NS_SYMBOL);
1064
1065                 /* Function declarations are automatically extern unless specifically static */
1066                 base_type = decl->ctype.base_type;
1067                 if (!is_typedef && base_type && base_type->type == SYM_FN) {
1068                         if (!(decl->ctype.modifiers & MOD_STATIC))
1069                                 decl->ctype.modifiers |= MOD_EXTERN;
1070                 }
1071         }
1072         return expect(token, ';', "at end of declaration");
1073 }
1074
1075 void translation_unit(struct token *token, struct symbol_list **list)
1076 {
1077         while (!eof_token(token))
1078                 token = external_declaration(token, list);
1079         // They aren't needed any more
1080         clear_token_alloc();
1081 }