parser2.cpp

   1 #include "parser.h"
   2
   3 #include <cstring>
   4 #include <map>
   5
   6
   7 /*
   8  * have a tape stack for pushing assigning CST nodes to as they are completed
   9  * have a templated destructor wrapper serving double duty as a destructor + union discriminant
  10  * reset the stack on error, destroying everything as needed
  11  * on completion of some nodes (if, while, for, etc -- probably everything but expressions)
  12  * take all prior parameters and produce some kind of AST node
  13  * is there a way to convert from a pointer to a destructor impl to its size? need a size for traversing the stack
  14  *
  15  */
  16
  17 template<class T>
  18 void destructor(void *v) {
  19     reinterpret_cast<T *>(v)->~T();
  20 }
  21
  22 class stack_t {
  23     using byte = std::uint8_t;
  24     using destructor_t = void (&)(void *it);
  25
  26     struct entry_t {
  27         stack_t *owner;
  28         std::size_t size;
  29         std::size_t offset;
  30         destructor_t dtor;
  31
  32         entry_t() : entry_t(nullptr, static_cast<std::size_t>(0), static_cast<std::size_t>(0), destructor<nullptr_t>) {}
  33
  34         entry_t(stack_t *owner, std::size_t size, std::size_t offset, destructor_t dtor) : owner(owner),
  35                                                                                                  size(size),
  36                                                                                                  offset(offset),
  37                                                                                                  dtor(dtor) {}
  38
  39         ~entry_t() {
  40             auto self = this;
  41             printf("%p\n", self);
  42             auto &stack = owner->stack;
  43             auto ptr = &stack[offset];
  44             printf("DELETE AT %p with %p\n", &stack[offset], dtor);
  45             dtor(reinterpret_cast<void *>(ptr));
  46         }
  47     };
  48
  49     std::vector<entry_t> entries;
  50     std::vector<byte> stack;
  51
  52 public:
  53
  54     using size_t = struct {
  55         size_t entries;
  56         size_t stack;
  57     };
  58
  59     size_t size() {
  60         return {entries.size(), stack.size()};
  61     }
  62
  63     std::size_t sizeat(std::size_t i) {
  64         return entries[i].size;
  65     }
  66
  67     void resize(size_t sp) {
  68         entries.resize(sp.entries);
  69         stack.resize(sp.stack);
  70     }
  71
  72     template<class T>
  73     void push(T &&it) {
  74         auto size = sizeof(T);
  75         auto offset = stack.size();
  76         stack.resize(offset + size);
  77         new(&stack[offset]) T(std::move(it));
  78         auto &dtor = destructor<T>;
  79         printf("MADE AT %p with %p\n", &stack[offset], dtor);
  80         entries.emplace_back(this, size, offset, dtor);
  81     }
  82
  83     void pop() {
  84         auto size = entries.back().size;
  85         entries.pop_back();
  86         stack.resize(stack.size() - size);
  87     }
  88
  89 };
  90
  91 template<class T, class U = T>
  92 T exchange(T &obj, U &&new_value) {
  93     T old_value = std::move(obj);
  94     obj = std::forward<U>(new_value);
  95     return old_value;
  96 }
  97
  98 //void never() {
  99 //    struct test {
 100 //        std::uint8_t okay;
 101 //        std::uint8_t *x;
 102 //
 103 //        test() {
 104 //            this->x = new std::uint8_t;
 105 //            this->okay = 47;
 106 //            printf("allocated %p\n", this->x);
 107 //        }
 108 //
 109 //        test(test &&o) : x(exchange(o.x, nullptr)), okay(o.okay) {
 110 //            printf("stole from %p into %p\n", &o, this);
 111 //        }
 112 //
 113 //        ~test() {
 114 //            printf("bye %p\n", this);
 115 //            delete this->x;
 116 //        }
 117 //    };
 118 //    auto d2 = destructor<test>;
 119 //    printf("dtor %p\n", d2);
 120 //    {
 121 ////        auto it = test{};
 122 ////        printf("pushing: %p\n", &it);
 123 ////        stack.push(std::move(it));
 124 ////        stack.pop();
 125 //    }
 126 //    printf("over\n");
 127 //}
 128
 129 // fixme: register typedef'd types. this wouldn't matter if parameters required names
 130 //        defeated by a mere for (i = 0; i < n; ++i)
 131 //        `for\s*\(\s*([^\s]+)\s*=` -> `for (auto $1 =`
 132 // fixme: GenericCommand_rpn  --  operators in strings??? specifically "="??
 133 // fixme: HUD_ItemsTime
 134 // todo: template traits for each rule to enable prediction instead of backtracking
 135 // todo: commit to a rule if possible and disable backtracking
 136 // todo: store memo on heap
 137 // todo: parameterize expression parsing instead of separate rules
 138
 139 #define RVALUE(it) ((void) 0, (it))
 140
 141 namespace result {
 142
 143 #define OK() return Result::OK
 144 #define ERR(msg) return Result((std::string("") + __PRETTY_FUNCTION__ + ": " + msg), ctx.tok)
 145
 146     struct Result {
 147         static Result OK;
 148
 149         explicit Result(std::string error, Token t) : tok(t) {
 150             auto tokname = std::string(TokenName(t));
 151             auto tokval = std::to_string(t);
 152             this->error = std::move(error) + " -> " + tokname + " (" + tokval + ")";
 153         }
 154
 155         std::string error;
 156         Token tok;
 157
 158         operator bool() const {
 159             return Result::OK == *this;
 160         }
 161
 162         bool operator==(const Result &other) const {
 163             return error == other.error;
 164         }
 165     };
 166
 167     Result Result::OK = Result("", Token::NONE);
 168 }
 169
 170 using Result = result::Result;
 171
 172 /// lexer
 173
 174 #define LTOK() RVALUE(ctx.lex.tok)
 175 #define CTX() RVALUE(LTOK().ctx)
 176
 177 #define SOURCELOC() \
 178     RVALUE((std::string(CTX().file) + ":" + std::to_string(CTX().line) + ":" + std::to_string(CTX().column)).c_str())
 179
 180 #define STRING() RVALUE((LTOK().value).c_str())
 181 #define DEBUG(msg) RVALUE(ctx.debug((std::string("*** `") + STRING() + "`: " + msg).c_str()))
 182
 183 /// parser
 184
 185 struct memo_t {
 186     decltype(lex_file::tok) tok;
 187     /// XXX: hack
 188     decltype(lex_file::peek) peek;
 189     size_t peekpos;
 190     size_t line, column;
 191     size_t idx;
 192     stack_t::size_t sp;
 193 };
 194
 195 struct ctx_t {
 196     parser_t &parser;
 197     lex_file &lex;
 198     Token tok;
 199
 200     stack_t stack = {};
 201
 202     std::map<std::string, int> typedefs;
 203
 204     explicit ctx_t(parser_t &parser) : parser(parser), lex(*parser.lex) {
 205         tok = Token::NONE;
 206     }
 207
 208     memo_t memo() {
 209         auto idx = lex.file ? ftell(lex.file) : lex.open_string_pos;
 210         return memo_t{lex.tok, lex.peek, lex.peekpos, lex.line, lex.column, idx, stack.size()};
 211     }
 212
 213     void memo(memo_t memo) {
 214         lex.tok = memo.tok;
 215         tok = memo.tok.ttype;
 216         lex.peek = memo.peek;
 217         lex.peekpos = memo.peekpos;
 218         lex.line = memo.line;
 219         lex.column = memo.column;
 220         if (lex.file) {
 221             fseek(lex.file, memo.idx, SEEK_SET);
 222         } else if (lex.open_string) {
 223             lex.open_string_pos = memo.idx;
 224         }
 225         stack.resize(memo.sp);
 226     }
 227
 228     void next() {
 229         tok = lex_do(parser.lex);
 230         if (tok >= Token::ERROR) {
 231             error("lex error");
 232             tok = Token::NONE;
 233         }
 234     }
 235
 236     template<typename... Ts>
 237     inline void error(const char *fmt, const Ts &...ts) {
 238         return parseerror(parser, fmt, formatNormalize(ts)...);
 239     }
 240
 241     std::string indent = "";
 242
 243     void rule_enter(const char *rule) {
 244         auto &ctx = *this;
 245         debug((std::string(rule) + " : `" + STRING() + "`").c_str());
 246         indent += "  ";
 247     }
 248
 249     void rule_leave(const char *rule, Result &ret) {
 250         indent.resize(std::max(static_cast<size_t>(0), indent.size() - 2));
 251         if (ret) {
 252             debug((std::string(rule) + "::OK").c_str());
 253         } else {
 254             debug((std::string(rule) + "::ERR").c_str());
 255         }
 256     }
 257
 258     void debug(const char *msg) {
 259         printf("%s%s\n", indent.c_str(), msg);
 260     }
 261
 262 private:
 263     static void parseerror(parser_t &parser, const char *fmt, ...) {
 264         va_list ap;
 265         va_start(ap, fmt);
 266         vcompile_error(parser.lex->tok.ctx, fmt, ap);
 267         va_end(ap);
 268     }
 269 };
 270
 271 // entrypoint
 272
 273 static bool parser_compile(ctx_t &&ctx);
 274
 275 using Rule = Result(ctx_t &ctx);
 276
 277 namespace parse {
 278
 279     Result dummy_result() {
 280         return Result::OK;
 281     }
 282
 283     template<class G, class R>
 284     auto rule_do(ctx_t &ctx) -> decltype(R::act(ctx, {}, {}, static_cast<G *>(nullptr), 0), dummy_result()) {
 285         auto begin = ctx.stack.size();
 286         ctx.rule_enter(R::name);
 287         auto ret = R::call(ctx);
 288         ctx.rule_leave(R::name, ret);
 289         if (ret) {
 290             auto end = ctx.stack.size();
 291             end.stack -= ctx.stack.sizeat(end.entries -= 1);
 292             R::act(ctx, begin, end, static_cast<G *>(nullptr), 0);
 293         }
 294         return ret;
 295     }
 296
 297 #define RULE(rule) \
 298 struct rule##_traits { \
 299     static constexpr const char *name = #rule; \
 300     static Result call(ctx_t &ctx) { return impl_##rule##_fn(ctx); } \
 301     template<class G> static auto act(ctx_t &ctx, stack_t::size_t begin, stack_t::size_t end, G*, int) -> decltype(G::act_##rule(ctx, begin, end), void()) { G::act_##rule(ctx, begin, end); } \
 302     template<class G> static auto act(ctx_t&, stack_t::size_t, stack_t::size_t, G*, long) -> decltype(void()) { } \
 303 }; \
 304 static Result rule(ctx_t &ctx) { return parse::rule_do<grammar, rule##_traits>(ctx); } \
 305 static Result impl_##rule##_fn(ctx_t &ctx)
 306
 307 #define ACTION(rule) \
 308 static void act_##rule(ctx_t &ctx, stack_t::size_t begin, stack_t::size_t end)
 309
 310 #define TRY(...) do { \
 311     auto ret = __VA_ARGS__; \
 312     if (!ret) { \
 313         return ret; \
 314     } \
 315 } while (false)
 316
 317 #define PEEK() RVALUE(ctx.tok)
 318 #define ACCEPT(it) RVALUE(parse::accept(ctx, (it)))
 319
 320     bool accept(ctx_t &ctx, Token t) {
 321         if (PEEK() == t) {
 322             ctx.next();
 323             return true;
 324         }
 325         return false;
 326     }
 327
 328 #define EXPECT(tok) EXPECT_2(tok, "unexpected symbol, " + TokenName(tok) + " was expected")
 329 #define EXPECT_2(tok, msg) do { \
 330     if (!ACCEPT(tok)) ERR(msg); \
 331 } while (false)
 332
 333
 334 #define ACCEPT_IDENT(it) (parse::accept_ident(ctx, (it)))
 335
 336     bool accept_ident(ctx_t &ctx, const char *ident) {
 337         if (PEEK() == Token::IDENT && strcmp(STRING(), ident) == 0) {
 338             ctx.next();
 339             return true;
 340         }
 341         return false;
 342     }
 343 }
 344
 345 namespace utils {
 346
 347 #define BT() ERR("BT")
 348
 349 /// rule[0] rule[1..n]
 350 template<Rule... rules>
 351 Result seq(ctx_t &ctx) {
 352     auto list = {rules...};
 353     for (auto &rule : list) {
 354         TRY(rule(ctx));
 355     }
 356     OK();
 357 }
 358
 359 /// rule?
 360 #define OPT(...) ([&](ctx_t &) { \
 361     auto memo = ctx.memo(); \
 362     if (!__VA_ARGS__(ctx)) ctx.memo(memo); \
 363     OK(); \
 364 })
 365
 366 /// rule?
 367 template<Rule rule>
 368 Result opt(ctx_t &ctx) {
 369     return OPT(rule)(ctx);
 370 }
 371
 372 /// rule+
 373 #define CROSS(...) ([&](ctx_t &) { \
 374     TRY(__VA_ARGS__(ctx)); \
 375     for (;;) { \
 376         auto memo = ctx.memo(); \
 377         if (!__VA_ARGS__(ctx)) { \
 378             ctx.memo(memo); \
 379             break; \
 380         } \
 381     } \
 382     OK(); \
 383 })
 384
 385 /// rule+
 386 template<Rule rule>
 387 Result cross(ctx_t &ctx) {
 388     return CROSS(rule)(ctx);
 389 }
 390
 391 /// rule* == (rule+)?
 392 #define STAR(...) OPT(CROSS(__VA_ARGS__))
 393
 394 /// rule* == (rule+)?
 395 template<Rule rule>
 396 Result star(ctx_t &ctx) {
 397     return STAR(rule)(ctx);
 398 }
 399
 400 /// rule (s rule)*
 401 template<Rule rule, Rule s>
 402 Result sep(ctx_t &ctx) {
 403     TRY(rule(ctx));
 404     TRY(STAR(seq<s, rule>)(ctx));
 405     OK();
 406 }
 407
 408 /// rule[0] | rule[1..n]
 409 #define ALT(...) ([&](ctx_t &) { \
 410     auto memo = ctx.memo(); \
 411     auto list = {__VA_ARGS__}; \
 412     for (auto &rule : list) { \
 413         auto ret = rule(ctx); \
 414         if (ret) \
 415             OK(); \
 416         ctx.memo(memo); \
 417     } \
 418     BT(); \
 419 })
 420
 421 /// rule[0] | rule[1..n]
 422 template<Rule... rules>
 423 Result alt(ctx_t &ctx) {
 424     return ALT(rules...)(ctx);
 425 }
 426
 427 template<Token t>
 428 Result tok(ctx_t &ctx) {
 429     EXPECT(t);
 430     OK();
 431 }
 432
 433 template<Token t, char... chars>
 434 Result lit(ctx_t &ctx) {
 435     static char str_[] = {chars..., 0};
 436     const char *str = str_;
 437     if (PEEK() == t) {
 438         const char *s = STRING();
 439         auto diff = strcmp(str, s);
 440         ctx.next();
 441         if (!diff) OK();
 442     }
 443     BT();
 444 }
 445
 446 template<Rule next, Rule op>
 447 Result leftop(ctx_t &ctx) {
 448     return sep<next, op>(ctx);
 449 }
 450
 451 template<Rule rule, class Then>
 452 Result when(ctx_t &ctx) {
 453     auto ret = rule(ctx);
 454     if (ret) {
 455         (*static_cast<Then *>(nullptr))(ctx);
 456     }
 457     return ret;
 458 }
 459
 460 }
 461
 462 using namespace utils;
 463
 464 struct grammar {
 465
 466     static constexpr auto Void = lit<Token::TYPENAME, 'v', 'o', 'i', 'd'>;
 467     static constexpr auto Char = lit<Token::TYPENAME, 'c', 'h', 'a', 'r'>;
 468     static constexpr auto Int = lit<Token::TYPENAME, 'i', 'n', 't'>;
 469     static constexpr auto Float = lit<Token::TYPENAME, 'f', 'l', 'o', 'a', 't'>;
 470     static constexpr auto Vector = lit<Token::TYPENAME, 'v', 'e', 'c', 't', 'o', 'r'>;
 471     static constexpr auto String = lit<Token::TYPENAME, 's', 't', 'r', 'i', 'n', 'g'>;
 472     static constexpr auto Entity = lit<Token::TYPENAME, 'e', 'n', 't', 'i', 't', 'y'>;
 473
 474     static constexpr auto Enum = lit<Token::IDENT, 'e', 'n', 'u', 'm'>;
 475     static constexpr auto Typedef = lit<Token::IDENT, 't', 'y', 'p', 'e', 'd', 'e', 'f'>;
 476
 477     static constexpr auto Const = lit<Token::KEYWORD, 'c', 'o', 'n', 's', 't'>;
 478     static constexpr auto Extern = lit<Token::KEYWORD, 'e', 'x', 't', 'e', 'r', 'n'>;
 479     static constexpr auto Static = lit<Token::IDENT, 's', 't', 'a', 't', 'i', 'c'>;
 480     static constexpr auto Noref = lit<Token::IDENT, 'n', 'o', 'r', 'e', 'f'>;
 481     static constexpr auto Local = lit<Token::KEYWORD, 'l', 'o', 'c', 'a', 'l'>;
 482     static constexpr auto Var = lit<Token::IDENT, 'v', 'a', 'r'>;
 483
 484     static constexpr auto If = lit<Token::KEYWORD, 'i', 'f'>;
 485     static constexpr auto Else = lit<Token::KEYWORD, 'e', 'l', 's', 'e'>;
 486     static constexpr auto Switch = lit<Token::IDENT, 's', 'w', 'i', 't', 'c', 'h'>;
 487     static constexpr auto Case = lit<Token::IDENT, 'c', 'a', 's', 'e'>;
 488     static constexpr auto Default = lit<Token::KEYWORD, 'd', 'e', 'f', 'a', 'u', 'l', 't'>;
 489
 490     static constexpr auto While = lit<Token::KEYWORD, 'w', 'h', 'i', 'l', 'e'>;
 491     static constexpr auto Do = lit<Token::KEYWORD, 'd', 'o'>;
 492     static constexpr auto For = lit<Token::KEYWORD, 'f', 'o', 'r'>;
 493
 494     static constexpr auto Goto = lit<Token::IDENT, 'g', 'o', 't', 'o'>;
 495     static constexpr auto Continue = lit<Token::KEYWORD, 'c', 'o', 'n', 't', 'i', 'n', 'u', 'e'>;
 496     static constexpr auto Break = lit<Token::KEYWORD, 'b', 'r', 'e', 'a', 'k'>;
 497     static constexpr auto Return = lit<Token::KEYWORD, 'r', 'e', 't', 'u', 'r', 'n'>;
 498
 499     // declarations
 500
 501     /// : translationUnit? EOF
 502     RULE(compilationUnit) {
 503         TRY(OPT(translationUnit)(ctx));
 504         TRY(tok<Token::END>(ctx));
 505         OK();
 506     }
 507
 508     ACTION(compilationUnit) {
 509         printf("DONE!\n");
 510     }
 511
 512     /// : externalDeclaration+
 513     RULE(translationUnit) {
 514         TRY(CROSS(externalDeclaration)(ctx));
 515         OK();
 516     }
 517
 518     struct externalDeclaration_declaration {
 519     };
 520
 521     /// : pragma
 522     /// | functionDefinition
 523     /// | declaration
 524     /// | enumDeclaration
 525     /// | ';'
 526     RULE(externalDeclaration) {
 527         TRY(alt<
 528                 pragma,
 529                 functionDefinition,
 530                 declaration,
 531                 enumDeclaration,
 532                 tok<Token::SEMICOLON>
 533         >(ctx));
 534         OK();
 535     }
 536
 537     ACTION(declaration) {
 538         printf("START %d\n", begin);
 539         ctx.stack.push(externalDeclaration_declaration{});
 540     }
 541
 542     ACTION(externalDeclaration) {
 543
 544         printf("FINISH %d\n", begin);
 545     }
 546
 547     RULE(pragma) {
 548         EXPECT(Token::HASH);
 549         if (ACCEPT_IDENT("pragma")) {
 550             if (ACCEPT_IDENT("noref")) {
 551                 EXPECT(Token::INTCONST);
 552                 OK();
 553             }
 554             ERR("unknown pragma '" + STRING() + "'");
 555         }
 556         ERR("unknown pragma '" + STRING() + "'");
 557     }
 558
 559     /// : declarationSpecifiers? declarator compoundStatement
 560     /// | declarationSpecifiers? declarator '=' compoundStatement  # legacy
 561     RULE(functionDefinition) {
 562         TRY(OPT(declarationSpecifiers)(ctx));
 563         TRY(declarator(ctx));
 564         TRY(OPT(tok<Token::EQ>)(ctx)); // legacy
 565         TRY(compoundStatement(ctx));
 566         OK();
 567     }
 568
 569     /// : attribute* (storageClassSpecifier | typeQualifier)* typeSpecifier
 570     RULE(declarationSpecifiers) {
 571         TRY(STAR(attribute)(ctx));
 572         TRY(STAR(alt<storageClassSpecifier, typeQualifier>)(ctx));
 573         TRY(typeSpecifier(ctx));
 574         OK();
 575     }
 576
 577     struct attribute_alias {
 578     };
 579
 580     struct attribute_eraseable {
 581     };
 582
 583     struct attribute_accumulate {
 584     };
 585
 586     /// : '[[' X ']]'
 587     RULE(attribute) {
 588         EXPECT(Token::ATTRIBUTE_OPEN);
 589         if (ACCEPT_IDENT("alias")) {
 590             EXPECT(Token::PAREN_OPEN);
 591             TRY(CROSS(tok<Token::STRINGCONST>)(ctx));
 592             EXPECT(Token::PAREN_CLOSE);
 593             ctx.stack.push(attribute_alias{});
 594         } else if (ACCEPT_IDENT("eraseable")) {
 595             ctx.stack.push(attribute_eraseable{});
 596         } else if (ACCEPT_IDENT("accumulate")) {
 597             ctx.stack.push(attribute_accumulate{});
 598         } else {
 599             ERR("unknown attribute '" + STRING() + "'");
 600         }
 601         EXPECT(Token::ATTRIBUTE_CLOSE);
 602         OK();
 603     }
 604
 605     struct storageClass_typedef {
 606     };
 607
 608     /// : 'typedef'
 609     /// | 'extern'
 610     /// | 'static'
 611     /// | 'noref'
 612     /// | 'local'  # legacy
 613     /// | 'var'    # legacy
 614     RULE(storageClassSpecifier) {
 615         static auto handleTypedef = [](ctx_t &ctx) {
 616             ctx.stack.push(storageClass_typedef{});
 617         };
 618         TRY(alt<
 619                 when<Typedef, decltype(handleTypedef)>,
 620                 Extern,
 621                 Static,
 622                 Noref,
 623                 Local,
 624                 Var
 625         >(ctx));
 626         OK();
 627     }
 628
 629     /// : ('.' | '...')* directTypeSpecifier ('(' parameterTypeList ')')?
 630     RULE(typeSpecifier) {
 631         TRY(STAR(alt<tok<Token::DOT>, tok<Token::DOTS>>)(ctx));
 632         TRY(directTypeSpecifier(ctx));
 633         TRY(OPT(seq<tok<Token::PAREN_OPEN>, opt<parameterTypeList>, tok<Token::PAREN_CLOSE>>)(ctx));
 634         OK();
 635     }
 636
 637     /// : ('void' | 'char' | 'int' | 'float' | 'vector' | 'string' | 'entity')
 638     /// | typedefName
 639     RULE(directTypeSpecifier) {
 640         TRY(alt<
 641                 alt<
 642                         Void,
 643                         Char,
 644                         Int,
 645                         Float,
 646                         Vector,
 647                         String,
 648                         Entity
 649                 >,
 650                 typedefName
 651         >(ctx));
 652         OK();
 653     }
 654
 655     /// : Identifier
 656     RULE(typedefName) {
 657         if (ACCEPT(Token::TYPENAME)) {
 658             OK();
 659         }
 660         if (PEEK() == Token::IDENT) {
 661             auto typedefs = ctx.typedefs;
 662             auto td = typedefs.find(std::string(STRING()));
 663             if (td != typedefs.end()) {
 664                 ctx.next();
 665                 OK();
 666             }
 667         }
 668         BT();
 669     }
 670
 671     /// : 'const'
 672     RULE(typeQualifier) {
 673         TRY(Const(ctx));
 674         OK();
 675     }
 676
 677     /// : Identifier (
 678     ///     '[' assignmentExpression_15? ']'
 679     ///   | '(' parameterTypeList? ')'
 680     /// )*
 681     RULE(declarator) {
 682         TRY(tok<Token::IDENT>(ctx));
 683         TRY(star<alt<
 684                 seq<tok<Token::BRACKET_OPEN>, opt<assignmentExpression_15>, tok<Token::BRACKET_CLOSE>>,
 685                 seq<tok<Token::PAREN_OPEN>, opt<parameterTypeList>, tok<Token::PAREN_CLOSE>>
 686         >>(ctx));
 687         OK();
 688     }
 689
 690     /// : (
 691     ///     '[' assignmentExpression_15? ']'
 692     ///   | '(' parameterTypeList? ')'
 693     /// )+
 694     RULE(abstractDeclarator) {
 695         TRY(cross<alt<
 696                 seq<tok<Token::BRACKET_OPEN>, opt<assignmentExpression_15>, tok<Token::BRACKET_CLOSE>>,
 697                 seq<tok<Token::PAREN_OPEN>, opt<parameterTypeList>, tok<Token::PAREN_CLOSE>>
 698         >>(ctx));
 699         OK();
 700     }
 701
 702     /// : (parameterVarargDeclaration | parameterDeclaration) (',' (parameterVarargDeclaration | parameterDeclaration))*
 703     RULE(parameterTypeList) {
 704         TRY(sep<alt<parameterVarargDeclaration, parameterDeclaration>, tok<Token::COMMA>>(ctx));
 705         OK();
 706     }
 707
 708     /// : declarationSpecifiers (declarator | abstractDeclarator?)
 709     RULE(parameterDeclaration) {
 710         TRY(declarationSpecifiers(ctx));
 711         TRY(alt<
 712                 declarator,
 713                 opt<abstractDeclarator>
 714         >(ctx));
 715         OK();
 716     }
 717
 718     /// : declarationSpecifiers? '...' Identifier?
 719     RULE(parameterVarargDeclaration) {
 720         TRY(OPT(declarationSpecifiers)(ctx));
 721         TRY(tok<Token::DOTS>(ctx));
 722         TRY(OPT(tok<Token::IDENT>)(ctx));
 723         OK();
 724     }
 725
 726     /// : declarationSpecifiers initDeclaratorList? ';'
 727     RULE(declaration) {
 728         TRY(declarationSpecifiers(ctx));
 729         TRY(OPT(initDeclaratorList)(ctx));
 730         TRY(tok<Token::SEMICOLON>(ctx));
 731
 732         // we're done, might have to register a typedef
 733 //        auto typedefs = ctx.typedefs;
 734 //        auto td = typedefs.find(std::string(STRING()));
 735 //        if (td != typedefs.end()) {
 736 //            ctx.next();
 737 //            OK();
 738 //        }
 739         OK();
 740     }
 741
 742     /// : initDeclarator (',' initDeclarator)*
 743     RULE(initDeclaratorList) {
 744         TRY(sep<initDeclarator, tok<Token::COMMA>>(ctx));
 745         OK();
 746     }
 747
 748     /// : declarator ('=' initializer)?
 749     RULE(initDeclarator) {
 750         TRY(seq<declarator, opt<seq<tok<Token::EQ>, initializer>>>(ctx));
 751         OK();
 752     }
 753
 754     /// : assignmentExpression_15
 755     /// | '{' initializerList ','? '}'
 756     RULE(initializer) {
 757         TRY(alt<
 758                 assignmentExpression_15,
 759                 seq<tok<Token::BRACE_OPEN>, initializerList, opt<tok<Token::COMMA>>, tok<Token::BRACE_CLOSE>>
 760         >(ctx));
 761         OK();
 762     }
 763
 764     /// : initializer (',' initializer)*
 765     RULE(initializerList) {
 766         TRY(sep<initializer, tok<Token::COMMA>>(ctx));
 767         OK();
 768     }
 769
 770     /// : 'enum' '{' enumeratorList ','? '}'
 771     RULE(enumDeclaration) {
 772         TRY(Enum(ctx));
 773         TRY(tok<Token::BRACE_OPEN>(ctx));
 774         TRY(enumeratorList(ctx));
 775         TRY(OPT(tok<Token::COMMA>)(ctx));
 776         TRY(tok<Token::BRACE_CLOSE>(ctx));
 777         OK();
 778     }
 779
 780     /// : enumerator (',' enumerator)*
 781     RULE(enumeratorList) {
 782         TRY(sep<enumerator, tok<Token::COMMA>>(ctx));
 783         OK();
 784     }
 785
 786     /// : enumerationConstant ('=' constantExpression)?
 787     RULE(enumerator) {
 788         TRY(enumerationConstant(ctx));
 789         TRY(OPT(seq<tok<Token::EQ>, constantExpression>)(ctx));
 790         OK();
 791     }
 792
 793     /// : Identifier
 794     RULE(enumerationConstant) {
 795         TRY(tok<Token::IDENT>(ctx));
 796         OK();
 797     }
 798
 799     // statements
 800
 801     /// : labeledStatement
 802     /// | compoundStatement
 803     /// | expressionStatement
 804     /// | selectionStatement
 805     /// | iterationStatement
 806     /// | jumpStatement
 807     RULE(statement) {
 808         TRY(alt<
 809                 labeledStatement,
 810                 compoundStatement,
 811                 expressionStatement,
 812                 selectionStatement,
 813                 iterationStatement,
 814                 jumpStatement
 815         >(ctx));
 816         OK();
 817     }
 818
 819     /// : (
 820     ///     'case' constantExpression
 821     ///   | 'default'
 822     ///   |  Identifier
 823     ///   ) ':' statement
 824     ///   | ':' Identifier  # legacy
 825     RULE(labeledStatement) {
 826         constexpr auto legacy = seq<tok<Token::COLON>, tok<Token::IDENT>>;
 827         TRY(alt<
 828                 seq<alt<
 829                         seq<Case, constantExpression>,
 830                         Default,
 831                         tok<Token::IDENT>
 832                 >, tok<Token::COLON>, alt<statement, declaration>>, // declarations are an extension
 833                 legacy
 834         >(ctx));
 835         OK();
 836     }
 837
 838     /// : '{' blockItem* '}'
 839     RULE(compoundStatement) {
 840         TRY(tok<Token::BRACE_OPEN>(ctx));
 841         TRY(STAR(blockItem)(ctx));
 842         TRY(tok<Token::BRACE_CLOSE>(ctx));
 843         OK();
 844     }
 845
 846     /// : declaration
 847     /// | statement
 848     RULE(blockItem) {
 849         TRY(alt<declaration, statement>(ctx));
 850         OK();
 851     }
 852
 853     /// : expression? ';'
 854     RULE(expressionStatement) {
 855         TRY(OPT(expression)(ctx));
 856         TRY(tok<Token::SEMICOLON>(ctx));
 857         OK();
 858     }
 859
 860     /// : 'if' '(' expression ')' statement ('else' statement)?
 861     /// | 'switch' '(' expression ')' statement
 862     RULE(selectionStatement) {
 863         TRY(alt<
 864                 seq<If, tok<Token::PAREN_OPEN>, expression, tok<Token::PAREN_CLOSE>, statement, opt<seq<Else, statement>>>,
 865                 seq<Switch, tok<Token::PAREN_OPEN>, expression, tok<Token::PAREN_CLOSE>, statement>
 866         >(ctx));
 867         OK();
 868     }
 869
 870     /// : 'while' '(' expression ')' statement
 871     /// | 'do' statement 'while' '(' expression ')' ';'
 872     /// | 'for' '(' forCondition ')' statement
 873     RULE(iterationStatement) {
 874         TRY(alt<
 875                 seq<While, tok<Token::PAREN_OPEN>, expression, tok<Token::PAREN_CLOSE>, statement>,
 876                 seq<Do, statement, While, tok<Token::PAREN_OPEN>, expression, tok<Token::PAREN_CLOSE>, tok<Token::SEMICOLON>>,
 877                 seq<For, tok<Token::PAREN_OPEN>, forCondition, tok<Token::PAREN_CLOSE>, statement>
 878         >(ctx));
 879         OK();
 880     }
 881
 882     /// : (expression | forDeclaration)? ';' forExpression? ';' forExpression?
 883     RULE(forCondition) {
 884         /// : declarationSpecifiers initDeclaratorList?
 885         constexpr auto forDeclaration = seq<declarationSpecifiers, opt<initDeclaratorList>>;
 886
 887         TRY(opt<alt<forDeclaration, expression>>(ctx));
 888         TRY(tok<Token::SEMICOLON>(ctx));
 889         TRY(opt<expression>(ctx));
 890         TRY(tok<Token::SEMICOLON>(ctx));
 891         TRY(opt<expression>(ctx));
 892         OK();
 893     }
 894
 895     /// : 'goto' Identifier ';'
 896     /// | 'continue' ';'
 897     /// | 'break' ';'
 898     /// | 'return' expression? ';'
 899     RULE(jumpStatement) {
 900         TRY(alt<
 901                 seq<Goto, tok<Token::IDENT>, tok<Token::SEMICOLON>>,
 902                 seq<Continue, tok<Token::SEMICOLON>>,
 903                 seq<Break, tok<Token::SEMICOLON>>,
 904                 seq<Return, opt<expression>, tok<Token::SEMICOLON>>
 905         >(ctx));
 906         OK();
 907     }
 908
 909     // expressions
 910     // left associative unless specified otherwise
 911
 912     RULE(expression) {
 913         return commaExpression_16(ctx);
 914     }
 915
 916     /// assignmentExpression_15 (',' assignmentExpression_15)*
 917     RULE(commaExpression_16) {
 918         TRY(leftop<
 919                 assignmentExpression_15,
 920                 tok<Token::COMMA>
 921         >(ctx));
 922         OK();
 923     }
 924
 925     RULE(constantExpression) {
 926         return conditionalExpression(ctx);
 927     }
 928
 929     /// : postfixExpression_2 assignmentOperator assignmentExpression_15
 930     /// | conditionalExpression
 931     /// right associative
 932     RULE(assignmentExpression_15) {
 933         constexpr auto assignmentOperator = alt<
 934                 tok<Token::EQ>,
 935                 seq<alt<
 936                         tok<Token::MUL>,
 937                         tok<Token::DIV>,
 938                         tok<Token::MOD>,
 939                         tok<Token::ADD>,
 940                         tok<Token::SUB>,
 941                         tok<Token::OP_LSH>,
 942                         tok<Token::OP_RSH>,
 943                         tok<Token::AND>,
 944                         tok<Token::XOR>,
 945                         tok<Token::OR>
 946                 >, tok<Token::EQ>>
 947         >;
 948         TRY(alt<
 949                 seq<alt<postfixExpression_2, Return>, assignmentOperator, assignmentExpression_15>,
 950                 conditionalExpression
 951         >(ctx));
 952         OK();
 953     }
 954
 955     /// : logicalOrExpression_14 ('?' expression ':' expression)?
 956     /// right associative
 957     RULE(conditionalExpression) {
 958         TRY(logicalOrExpression_14(ctx));
 959         TRY(OPT(seq<tok<Token::QUESTION>, expression, tok<Token::COLON>, expression>)(ctx));
 960         OK();
 961     }
 962
 963     /// : logicalAndExpression_13 ('||' logicalAndExpression_13)*
 964     RULE(logicalOrExpression_14) {
 965         TRY(leftop<
 966                 logicalAndExpression_13,
 967                 seq<tok<Token::OR>, tok<Token::OR>>
 968         >(ctx));
 969         OK();
 970     }
 971
 972     /// : inclusiveOrExpression_12 ('&&' inclusiveOrExpression_12)*
 973     RULE(logicalAndExpression_13) {
 974         TRY(leftop<
 975                 inclusiveOrExpression_12,
 976                 tok<Token::OP_AND>
 977         >(ctx));
 978         OK();
 979     }
 980
 981     /// : exclusiveOrExpression_11 ('|' exclusiveOrExpression_11)*
 982     RULE(inclusiveOrExpression_12) {
 983         TRY(leftop<
 984                 exclusiveOrExpression_11,
 985                 tok<Token::OR>
 986         >(ctx));
 987         OK();
 988     }
 989
 990     /// : andExpression_10 ('^' andExpression_10)*
 991     RULE(exclusiveOrExpression_11) {
 992         TRY(leftop<
 993                 andExpression_10,
 994                 tok<Token::XOR>
 995         >(ctx));
 996         OK();
 997     }
 998
 999     /// : equalityExpression_9 ('&' equalityExpression_9)*
1000     RULE(andExpression_10) {
1001         TRY(leftop<
1002                 equalityExpression_9,
1003                 tok<Token::AND>
1004         >(ctx));
1005         OK();
1006     }
1007
1008     /// : relationalExpression_8 (('==' | '!=') relationalExpression_8)*
1009     RULE(equalityExpression_9) {
1010         TRY(leftop<
1011                 relationalExpression_8,
1012                 seq<alt<
1013                         tok<Token::EQ>,
1014                         tok<Token::NOT>
1015                 >, tok<Token::EQ>>
1016         >(ctx));
1017         OK();
1018     }
1019
1020     /// : shiftExpression_7 (('<' | '<=' | '>' | '>=') shiftExpression_7)*
1021     RULE(relationalExpression_8) {
1022         TRY(leftop<
1023                 shiftExpression_7,
1024                 alt<
1025                         tok<Token::LT>,
1026                         tok<Token::OP_LE>,
1027                         tok<Token::GT>,
1028                         tok<Token::OP_GE>
1029                 >
1030         >(ctx));
1031         OK();
1032     }
1033
1034     /// : additiveExpression_6 (('<<' | '>>') additiveExpression_6)*
1035     RULE(shiftExpression_7) {
1036         TRY(leftop<
1037                 additiveExpression_6,
1038                 alt<
1039                         tok<Token::OP_LSH>,
1040                         tok<Token::OP_RSH>
1041                 >
1042         >(ctx));
1043         OK();
1044     }
1045
1046     /// : multiplicativeExpression_5 (('+' | '-') multiplicativeExpression_5)*
1047     RULE(additiveExpression_6) {
1048         TRY(leftop<
1049                 multiplicativeExpression_5,
1050                 alt<
1051                         tok<Token::ADD>,
1052                         tok<Token::SUB>
1053                 >
1054         >(ctx));
1055         OK();
1056     }
1057
1058     /// : castExpression_3 (('*' | '/' | '%' | '><') castExpression_3)*
1059     RULE(multiplicativeExpression_5) {
1060         TRY(leftop<
1061                 castExpression_3,
1062                 alt<
1063                         tok<Token::MUL>,
1064                         tok<Token::DIV>,
1065                         tok<Token::MOD>,
1066                         tok<Token::OP_CROSS>
1067                 >
1068         >(ctx));
1069         OK();
1070     }
1071
1072     /// : unaryExpression_3
1073     /// | '(' typeName ')' castExpression_3
1074     /// right associative
1075     RULE(castExpression_3) {
1076         // no casts yet
1077         return unaryExpression_3(ctx);
1078     }
1079
1080     /// : postfixExpression_2 ('**' unaryExpression_3)*
1081     /// | ('++' | '--') unaryExpression_3
1082     /// | ('+' | '-' | '~' | '!') castExpression_3
1083     /// right associative
1084     RULE(unaryExpression_3) {
1085         TRY(alt<
1086                 seq<postfixExpression_2, star<seq<tok<Token::MUL>, tok<Token::MUL>, unaryExpression_3>>>,
1087                 seq<alt<
1088                         seq<tok<Token::ADD>, tok<Token::ADD>>,
1089                         seq<tok<Token::SUB>, tok<Token::SUB>>
1090                 >, unaryExpression_3>,
1091                 seq<alt<
1092                         tok<Token::ADD>,
1093                         tok<Token::SUB>,
1094                         tok<Token::BITNOT>,
1095                         tok<Token::NOT>
1096                 >, castExpression_3>
1097         >(ctx));
1098         OK();
1099     }
1100
1101     /// : primaryExpression (
1102     /// |   '[' expression ']'
1103     /// |   '(' expression? ')'
1104     /// |   '.' Identifier          # static field
1105     /// |   '.' '(' expression ')'  # computed field
1106     /// |   ('++' | '--')
1107     /// | )*
1108     RULE(postfixExpression_2) {
1109         TRY(primaryExpression(ctx));
1110         TRY(star<alt<
1111                 seq<tok<Token::BRACKET_OPEN>, expression, tok<Token::BRACKET_CLOSE>>,
1112                 seq<tok<Token::PAREN_OPEN>, opt<expression>, tok<Token::PAREN_CLOSE>>,
1113                 seq<tok<Token::DOT>, tok<Token::IDENT>>,
1114                 seq<tok<Token::DOT>, tok<Token::PAREN_OPEN>, expression, tok<Token::PAREN_CLOSE>>,
1115                 seq<alt<
1116                         seq<tok<Token::ADD>, tok<Token::ADD>>,
1117                         seq<tok<Token::SUB>, tok<Token::SUB>>
1118                 >>
1119         >>(ctx));
1120         OK();
1121     }
1122
1123     /// : Identifier
1124     /// | Constant
1125     /// | StringLiteral+
1126     /// | '...' '(' assignmentExpression_15 ',' typeSpecifier ')'  # absolute va_arg
1127     /// | '(' expression ')'
1128     RULE(primaryExpression) {
1129         TRY(alt<
1130                 tok<Token::IDENT>,
1131                 tok<Token::INTCONST>,
1132                 tok<Token::FLOATCONST>,
1133                 tok<Token::CHARCONST>,
1134                 tok<Token::VECTORCONST>,
1135                 cross<tok<Token::STRINGCONST>>,
1136                 seq<tok<Token::HASH>, tok<Token::INTCONST>>,
1137                 seq<tok<Token::DOTS>, tok<Token::PAREN_OPEN>, assignmentExpression_15, tok<Token::COMMA>, typeSpecifier, tok<Token::PAREN_CLOSE>>,
1138                 seq<tok<Token::PAREN_OPEN>, expression, tok<Token::PAREN_CLOSE>>
1139         >(ctx));
1140         OK();
1141     }
1142 };
1143
1144 static bool parser_compile(ctx_t &&ctx) {
1145     ctx.parser.lex->flags.noops = true; // don't parse operators
1146     ctx.next();
1147     auto result = grammar::compilationUnit(ctx);
1148     if (result) {
1149         return true;
1150     }
1151     ctx.error(result.error.c_str());
1152     return false;
1153 }
1154
1155 // utils
1156
1157 const int PARSER_HT_SIZE = 512;
1158 const int TYPEDEF_HT_SIZE = 512;
1159
1160 parser_t *parser_create() {
1161     auto parser = new parser_t;
1162     for (size_t i = 0; i < operator_count; ++i) {
1163         if (operators[i].id == opid1('=')) {
1164             parser->assign_op = &operators[i];
1165             break;
1166         }
1167     }
1168     if (!parser->assign_op) {
1169         con_err("internal error: initializing parser: failed to find assign operator\n");
1170         delete parser;
1171         return nullptr;
1172     }
1173
1174     return parser;
1175 }
1176
1177 parser_t::parser_t()
1178         : lex(nullptr), tok(Token::NONE), ast_cleaned(false), translated(0), crc_globals(0), crc_fields(0),
1179           function(nullptr),
1180           aliases(util_htnew(PARSER_HT_SIZE)), htfields(util_htnew(PARSER_HT_SIZE)),
1181           htglobals(util_htnew(PARSER_HT_SIZE)), assign_op(nullptr), noref(false), max_param_count(1), m_fold(*this),
1182           m_intrin(*this) {
1183     variables.push_back(htfields);
1184     variables.push_back(htglobals);
1185     typedefs.push_back(util_htnew(TYPEDEF_HT_SIZE));
1186     _blocktypedefs.push_back(0);
1187
1188     lex_ctx_t empty_ctx;
1189     empty_ctx.file = "<internal>";
1190     empty_ctx.line = 0;
1191     empty_ctx.column = 0;
1192     nil = new ast_value(empty_ctx, "nil", TYPE_NIL);
1193     nil->m_cvq = CV_CONST;
1194     if (OPTS_FLAG(UNTYPED_NIL))
1195         util_htset(htglobals, "nil", (void *) nil);
1196
1197     const_vec[0] = new ast_value(empty_ctx, "<vector.x>", TYPE_NOEXPR);
1198     const_vec[1] = new ast_value(empty_ctx, "<vector.y>", TYPE_NOEXPR);
1199     const_vec[2] = new ast_value(empty_ctx, "<vector.z>", TYPE_NOEXPR);
1200
1201     if (OPTS_OPTION_BOOL(OPTION_ADD_INFO)) {
1202         reserved_version = new ast_value(empty_ctx, "reserved:version", TYPE_STRING);
1203         reserved_version->m_cvq = CV_CONST;
1204         reserved_version->m_hasvalue = true;
1205         reserved_version->m_flags |= AST_FLAG_INCLUDE_DEF;
1206         reserved_version->m_flags |= AST_FLAG_NOREF;
1207         reserved_version->m_constval.vstring = util_strdup(GMQCC_FULL_VERSION_STRING);
1208     } else {
1209         reserved_version = nullptr;
1210     }
1211 }
1212
1213 parser_t::~parser_t() {
1214     remove_ast();
1215 }
1216
1217 void parser_t::remove_ast() {
1218
1219 }
1220
1221 bool parser_compile_string(parser_t &parser, const char *name, const char *str, size_t len) {
1222     parser.lex = lex_open_string(str, len, name);
1223     if (!parser.lex) {
1224         con_err("failed to create lexer for string \"%s\"\n", name);
1225         return false;
1226     }
1227     return parser_compile(ctx_t(parser));
1228 }
1229
1230 bool parser_compile_file(parser_t &parser, const char *filename) {
1231     parser.lex = lex_open(filename);
1232     if (!parser.lex) {
1233         con_err("failed to open file \"%s\"\n", filename);
1234         return false;
1235     }
1236     return parser_compile(ctx_t(parser));
1237 }
1238
1239 ast_expression *parser_find_global(parser_t &parser, const char *name) {
1240     auto ctx = ctx_t(parser);
1241     ast_expression *var = (ast_expression *) util_htget(parser.aliases, STRING());
1242     if (var)
1243         return var;
1244     return (ast_expression *) util_htget(parser.htglobals, name);
1245 }
1246
1247 bool parser_finish(parser_t &parser, const char *output) {
1248     return true;
1249 }