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