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