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