parse.c

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