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