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