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