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