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