base.nt

module neat.base;

import backend.base;
import helpers;
public import neat.runtime.locrange;
import polyhash;

enum TokenType {
    none,
    end,
    whitespace,
    identifier,
    number,
    comment,
    dot,
    comma,
    singleQuote,
    charLiteral,
    doubleQuote, // ["]foo $(bar) baz["]
    stringLiteral, // "[foo ]$(bar)[ baz]"
    formatQuoteStart, // "foo [$](bar)"
    backtick,
    colon,
    semicolon,
    lparen,
    rparen,
    smaller,
    greater,
    equal,
    exclamationmark,
    questionmark,
    dollar,
    lsquarebracket,
    rsquarebracket,
    lcurlybracket,
    rcurlybracket,
    plus,
    minus,
    asterisk,
    slash,
    backslash,
    circumflex,
    percent,
    tilde,
    ampersand,
    bar,
    hash,
}

// something that can be referenced by a name
abstract class Symbol
{
    /**
    * The sort of thing that can be implicitly called.
    * Marker to shortcut the call() logic to speed up `isExpressionImplCall`:
    * if this is not set, implicit call won't even be considered.
    */
    abstract bool mayCallImplicit();

    string repr() {
        // TODO this.__classname
        return "TODO Symbol.repr $(cast(void*) this)";
    }
    string toString() return repr;
}

/**
 * Gifted: An expression with an unmanaged lifetime that we must take over.
 * Ephemeral: An expression that will be freed at some indeterminate point.
 * Lexical: An expression that will be freed at the earliest when the scope ends.
 * Permanent: An expression that will never naturally be freed.
 *  (Can be incremented and decremented, but must remain above 1.)
 *  TODO: Do we need this anywhere? Most sites should be None.
 * None: An expression that should not have rc done on it.
 *
 * Examples:
 * - gifted: `new Class()`
 * - ephemeral: `foo.(that)`
 * - lexical: `void foo(Class obj) { }` or `Class obj;`
 * - permanent: `"string"`
 * - none: cast(T) foo
 */
enum Lifetime
{
    gifted,
    ephemeral,
    lexical,
    permanent,
    none,
}

struct ExprInfo
{
    Lifetime lifetime;

    string repr() {
        mut string ret;
        if (lifetime == Lifetime.gifted) ret ~= "gifted";
        else if (lifetime == Lifetime.ephemeral) ret ~= "ephemeral";
        else if (lifetime == Lifetime.lexical) ret ~= "lexical";
        else if (lifetime == Lifetime.permanent) ret ~= "permanent";
        else if (lifetime == Lifetime.none) ret ~= "none";
        else assert(false);
        return ret;
    }
    string toString() return repr;
}

abstract class Expression : Symbol
{
    Type type;
    ExprInfo info;
    abstract int emit(Generator output);
    abstract void hash(Hash hash);
    override bool mayCallImplicit() => false;
}

abstract class Statement
{
    abstract void emit(Generator output);
    abstract void hash(Hash hash);
    string repr() => "TODO Statement.repr";
    string toString() => repr;
}

abstract class Reference : Expression
{
    bool mutable;
    abstract int emitLocation(Generator output);
}

enum Protection
{
    public_,
    protected_,
    private_
}

abstract class Type : Symbol
{
    abstract BackendType emit(Platform platform);
    abstract bool same(Type type);
    string mangle() {
        print("Don't know how to mangle $(repr)");
        assert(false);
    }
    abstract void hash(Hash hash);
    override bool mayCallImplicit() => false;

    bool zeroInitializable;

    bool hasElaborateCopyConstructor;

    (nullable Expression | Error) implicitConvertFrom(Context context, Expression source, LocRange locRange)
    {
        return null;
    }

    (nullable Expression | Error) implicitConvertTo(
        Context context, Expression source, Type target, LocRange locRange)
    {
        return null;
    }

    /**
     * Implicitly converts to the target without change in bits.
     * Used for implicit array type conversion.
     */
    bool triviallyConvertsTo(Type target)
    {
        return this.same(target);
    }

    (nullable Expression | Error) truthy(Context context, Expression expr, LocRange locRange)
    {
        return null;
    }

    /**
     * Called to create a copy of the expression.
     * The returned expression will count as a new reference.
     */
    (Expression | Error) copy(Context context, Expression source, LocRange locRange)
    {
        return source;
    }

    /**
     * Called when a scoped expression goes out of scope.
     */
    nullable Statement endLifetime(Context context, Expression value)
    {
        return null;
    }

    /**
     * When looking up a nember in this type at scope 'namespace',
     * what is the maximum protection level of the member where
     * lookup will succeed?
     */
    Protection protectionAt(Namespace namespace) {
        // all are visible by default.
        return Protection.private_;
    }

    /**
     * Called to resolve `value.field`.
     * If `base` is null, this indicates a static field access, `Type.field`.
     * Note that `base` will not be refmanaged. Dispose of it correctly!
     */
    (nullable Symbol | Error) accessMember(
        Context context, nullable Expression base, string field, Protection protection, LocRange locRange)
    {
        return null;
    }

    /**
     * Called to resolve `value.field(args)`.
     */
    (nullable Expression | Error) callMember(
        Context context, nullable Expression base, string field, ASTArgument[] args, Protection protection, LocRange locRange)
    {
        return null;
    }

    /**
     * Called to resolve `value.field = arg`.
     */
    (nullable Statement | Error) assignMember(
        Context context, Expression base, string field, Expression arg, Protection protection, LocRange locRange)
    {
        return null;
    }

    /**
     * Called to resolve `base[index]`.
     */
    (nullable Expression | Error) index(Context context, Expression base, ASTSymbol index, LocRange locRange)
    {
        return null;
    }

    /**
     * Called to resolve `base[index] = value`.
     */
    (nullable Statement | Error) indexAssignment(
        Context context, Expression base, ASTSymbol index, Expression value, LocRange locRange)
    {
        return null;
    }

    /**
     * Called to resolve 'lhs op rhs' where op is a binary operator.
     */
    (nullable Expression | Error) binaryOp(Context context, string op, Expression lhs, Expression rhs, LocRange locRange)
    {
        return null;
    }

    /**
     * Called to resolve 'Type(a, b, c)'.
     *
     * TODO: rename to callType
     */
    (nullable Expression | Error) call(Context context, LocRange locRange, ASTArgument[] args)
    {
        return null;
    }

    /**
     * Called to resolve `expr(a, b, c)`, where `typeof(expr)` is `Type`.
     *
     * TODO: rename to call
     */
    (nullable Expression | Error) callExpr(Context context, LocRange locRange, Expression expr, ASTArgument[] args)
    {
        return null;
    }

    /**
     * Implement lambda quarantine checks.
     * So far, only return is affected directly.
     *
     * See: doc/quarantine.md
     */
    (void | Error) checkQuarantine(Context context, LocRange locRange, QuarantineReason reason)
    {
    }

    /**
     * Case `a.b = c`:
     * Behavior depends on the quarantine policy of `a` and `c`.
     * Assignment of a checked value to an occluded container field is an error.
     * Assignment of a checked value to a transparent non-lexical container field is an error.
     *  - But I think it's impossible. How can you lexically export the type?
     */
    QuarantinePolicy quarantinePolicy()
    {
        return QuarantinePolicy(container=:occluded, value=:harmless);
    }
}

struct QuarantinePolicy {
    // transparent containers allow assignment
    (:transparent | :occluded) container;
    (:checked | :harmless) value;
}

alias QuarantineReason = (
    :returningFrom, Returnable returnable
);

interface Hashable
{
    (ASTSymbol | Error) hash(CompilerBase compiler, ASTSymbol value);
}

class Generator
{
    BackendModule mod;

    mut nullable BackendFunction fun;

    FileIdTable fileIdTable;

    Platform platform;

    mut int frameReg;

    mut string[] extraFlags; // from pragma(lib)

    this(this.platform, this.mod, this.fileIdTable)
    {
        this.fun = null;
    }

    bool once(string name)
    {
        return this.mod.once(name);
    }

    void addFlag(string flag) {
        for (flag2 in extraFlags) if (flag == flag2) return;
        this.extraFlags ~= flag;
    }
}

abstract class ASTSymbol
{
    LocRange locRange;

    this(this.locRange=__CALLER__) {}

    abstract (Symbol | Error) compile(Context context);

    /**
     * Compile a LHS AST node that has special handling for assignment.
     * Example: ASTIndex, ASTMember.
     */
    (nullable Statement | Error) assign(Context context, Expression value) {
        return null;
    }

    // TODO this.classname
    string repr() { return "TODO repr(ASTSymbol): $(locRange.toString)"; }
    string toString() => repr;
}

/**
 * `foo` or `$bar`, pretty much.
 * A symbol that can appear in a declaration like `A B = C`, or `A.B = C`, in position `B`.
 * Can be resolved to a string without compiling.
 */
abstract class ASTIdentifierSymbol : ASTSymbol
{
    abstract string name(WarmContext warmContext);
}

// TODO Statement, Context multi-return with destructuring
struct StatementCompileResult
{
    Statement statement;

    Namespace namespace;
}

abstract class ASTStatement
{
    LocRange locRange;

    this(this.locRange=__CALLER__) {}

    abstract (StatementCompileResult | Error) compile(Context context);

    // TODO this.classname
    string repr() { return "TODO repr(ASTStatement): $(locRange.toString)"; }
}

/**
 * Something that updates a namespace without behavioral side effects:
 *
 * - import
 * - alias
 * - struct decl
 * - class decl
 *
 * Ironically, a variable declaration is not an ASTDeclaration.
 * Find a better name?
 */
abstract class ASTDeclaration
{
    LocRange locRange;

    abstract (Namespace | Error) compile(Context context);

    // TODO this.classname
    string repr() { return "TODO repr(ASTDeclaration)"; }
    string toString() return repr;
}

abstract class ASTSymbolDeclaration : ASTDeclaration
{
    ASTIdentifierSymbol name;

    abstract (Symbol | Error) compileSymbol(Context context);

    override (Namespace | Error) compile(Context context) {
        auto symbol = compileSymbol(context)?;
        auto name = this.name.name(context.warmContext);

        return context.compiler.exprAlias(context.namespace, name, symbol);
    }
}

// 'name' is ASTIdentifier or ASTQuotedSymbol
alias ExtForVarDecl = ((:auto_ | ASTSymbol | :none) type, LocRange locRange, ASTIdentifierSymbol name);

enum LookupReason
{
    // normal name lookup
    identifier,
    // lookup for foo.bar (ufcs, don't match class methods on 'this')
    ufcs,
    // Lookup for resolving an ASTAssignment, ie. the `x` in `x = y`.
    // Might return something magical like an AssignmentHelper, idk.
    assignment,
    // didYouMean,
}

abstract class AssignmentHelper : Symbol
{
    abstract (nullable Statement | Error) assign(Context context, Expression value);
}

/**
 * A namespace is a lexical environment that supports identifier lookup.
 * Note that this means "foo", not "a.foo".
 */
abstract class Namespace
{
    nullable Namespace parent; // lexical parent

    bool isContextScope;

    this(this.parent, this.isContextScope) { }

    /**
     * name:    The name being looked up.
     *
     * context: The compiler context originating the lookup.
     *          The namespace in context is used as the provenance of the lookup,
     *          meaning it decides whether private members may be read.
     *
     * loc:     The location of the symbol triggering the lookup.
     */
    abstract (nullable Symbol | Error) lookup(
        string name, Context context, LookupReason reason, LocRange locRange);

    string mangle() { return this.parent.mangle; }
    abstract string repr();
}

/// Something that 'return' returns from.
interface Returnable
{
    /// We want to return `proposed`, so give me a type you can be happy with.
    (Type | Error) mergeReturn(Context context, Expression ret, LocRange locRange);
}

/// Something that variables can be declared in.
interface Declarable
{
    LatentVariable declare(Context context, string name, Type type, bool mut, bool borrowed, (int | :none) parentId);
}

// Namespace with unwind side effect, such as onExit call.
// Evaluated before declaration cleanup.
interface Unwindable
{
    (nullable Statement | Error) unwind(Context context);
}

// variable without stackframe
abstract class LatentVariable
{
    int id;

    this(this.id) {}

    abstract Type type();

    abstract Reference access(Context context);
}

// Something that should be cleaned up on unwind.
// TODO remove this - it's redundant with Unwindable. (?)
abstract class DeclarationHolder : Namespace
{
    abstract bool freeOnExit();

    abstract Reference accessDecl(Context context);

    // when we don't strictly need a Reference
    Expression access(Context context) => accessDecl(context);
}

final class QuoteScope
{
    // used to match lookups to scopes
    int scopeId;

    nullable QuoteScope parent;

    ASTSymbol[] symbols;

    ASTStatement[] statements;

    ASTIdentifierSymbol[] identifiers;

    this(this.scopeId, this.parent, this.symbols, this.statements, this.identifiers) {}
}

/**
 * This contains the parts of Context that are never modified at all.
 */
final class ColdContext
{
    CompilerBase compiler;

    Platform platform;

    MacroState macroState;

    // here for caching reasons
    // TODO replace with once
    Type nativeWordType;

    int loopPass;

    ModulePreProcessor modulePreProcessor;

    ModulePostProcessor modulePostProcessor;

    this(this.compiler, this.platform, this.macroState, this.nativeWordType, this.loopPass,
         this.modulePreProcessor, this.modulePostProcessor) { }

    ColdContext withMacroState(MacroState macroState) {
        return new ColdContext(this.compiler, this.platform, macroState,
            this.nativeWordType, this.loopPass, this.modulePreProcessor,
            this.modulePostProcessor);
    }
}

/**
 * This contains the parts of Context that are modified occasionally,
 * but not too often.
 */
final class WarmContext
{
    // the reference by which free variables are resolved.
    nullable Expression framePointer;

    // the lookup depth of the framepointer
    (int | :none) frameDepth;

    nullable ModuleBase compilingModule;

    LabelCounter labelCounter;

    IUniqCounter uniqCounter;

    nullable QuoteScope quoteScope;

    mut LocRange[] errorStack;

    this(
        this.framePointer, this.frameDepth, this.compilingModule, this.labelCounter,
        this.uniqCounter, this.quoteScope, this.errorStack)
    { }

    WarmContext withFramePointer(nullable Expression framePointer, (int | :none) frameDepth) {
        return new WarmContext(
            framePointer, frameDepth, this.compilingModule, this.labelCounter,
            this.uniqCounter, this.quoteScope, this.errorStack);
    }

    WarmContext withCompilingModule(ModuleBase compilingModule) {
        return new WarmContext(
            this.framePointer, this.frameDepth, compilingModule, this.labelCounter,
            this.uniqCounter, this.quoteScope, this.errorStack);
    }

    WarmContext withLabelPrefix(string prefix) {
        auto labelCounter = new LabelCounter(prefix);
        auto uniqCounter = this.uniqCounter.dup;

        return new WarmContext(
            this.framePointer, this.frameDepth, this.compilingModule, labelCounter,
            uniqCounter, this.quoteScope, this.errorStack);
    }

    WarmContext withQuoteScope(QuoteScope quoteScope) {
        return new WarmContext(
            this.framePointer, this.frameDepth, this.compilingModule, this.labelCounter,
            this.uniqCounter, quoteScope, this.errorStack);
    }

    ASTSymbol getQuoteSymbol(int scopeId, int index) {
        mut auto current = this.quoteScope;
        while (current) {
            if (current.scopeId == scopeId) return current.symbols[index];
            current = current.parent;
        }
        print("cannot get quote symbol @$index with scope id $scopeId");
        assert(false);
    }

    ASTStatement getQuoteStatement(int scopeId, int index) {
        mut auto current = this.quoteScope;
        while (current) {
            if (current.scopeId == scopeId) return current.statements[index];
            current = current.parent;
        }
        print("cannot get quote statement @$index with scope id $scopeId");
        assert(false);
    }

    ASTIdentifierSymbol getQuoteIdentifier(int scopeId, int index) {
        mut auto current = this.quoteScope;
        while (current) {
            if (current.scopeId == scopeId) {
                if (index < current.identifiers.length)
                    return current.identifiers[index];
                print("cannot get quote identifier @$index with scope id $scopeId: "
                    ~ "only got $(current.identifiers.length)");
                assert(false);
            }
            current = current.parent;
        }
        print("cannot get quote identifier @$index with scope id $scopeId");
        assert(false);
    }
}

/**
 * Generates unique text labels with a prefix.
 * Usually used for names that will appear in the output and must be stable between runs.
 */
class LabelCounter
{
    string prefix;

    mut int count;

    this(this.prefix = "uniq") { }

    string next() {
        auto count = this.count++;
        return "$(this.prefix)$count";
    }
}

/**
 * Generate a unique numeric label.
 * This class is more performant than `LabelCounter`.
 * The value is not stable between runs; however, it is guaranteed to be globally unique per program run.
 * `dup` must be called when the UniqCounter will be passed to another thread.
 */
interface IUniqCounter {
    int next();
    IUniqCounter dup();
}

// Used by main to analyze the AST tree (docgen)
interface ModulePreProcessor
{
    void process(ASTModuleBase astModule_);
}

// Will be used by main to start emitting modules as soon as they finish.
interface ModulePostProcessor
{
    void process(ModuleBase module_);
}

/**
 * Context used when transforming an AST into a semantic tree.
 *
 * TODO figure out how to reduce refcounts on this.
 */
struct Context
{
    Namespace namespace;

    WarmContext warmContext;

    ColdContext coldContext;

    Context withNamespace(Namespace namespace) {
        return Context(namespace, this.warmContext, this.coldContext);
    }

    Context withFramePointer(nullable Expression framePointer, (int | :none) frameDepth) {
        return Context(this.namespace, this.warmContext.withFramePointer(framePointer, frameDepth), this.coldContext);
    }

    Context withCompilingModule(ModuleBase compilingModule) {
        return Context(this.namespace, this.warmContext.withCompilingModule(compilingModule), this.coldContext);
    }

    Context withLabelPrefix(string prefix) {
        return Context(this.namespace, this.warmContext.withLabelPrefix(prefix), this.coldContext);
    }

    Context withQuoteScope(QuoteScope quoteScope) {
        return Context(this.namespace, this.warmContext.withQuoteScope(quoteScope), this.coldContext);
    }

    ASTSymbol getQuoteSymbol(int scopeId, int index) =>
        this.warmContext.getQuoteSymbol(scopeId, index);

    ASTStatement getQuoteStatement(int scopeId, int index) =>
        this.warmContext.getQuoteStatement(scopeId, index);

    ASTIdentifierSymbol getQuoteIdentifier(int scopeId, int index) =>
        this.warmContext.getQuoteIdentifier(scopeId, index);

    alias compiler = (coldContext.compiler);
    alias platform = (coldContext.platform);
    alias macroState = (coldContext.macroState);
    alias nativeWordType = (coldContext.nativeWordType);
    alias modulePreProcessor = (coldContext.modulePreProcessor);
    alias modulePostProcessor = (coldContext.modulePostProcessor);
    alias loopPass = (coldContext.loopPass);

    alias framePointer = (warmContext.framePointer);
    alias frameDepth = (warmContext.frameDepth);
    alias compilingModule = (warmContext.compilingModule);
    alias labelCounter = (warmContext.labelCounter);
    alias uniqCounter = (warmContext.uniqCounter);
    alias quoteScope = (warmContext.quoteScope);
    alias errorStack = (warmContext.errorStack);

    void pushErrorLoc(LocRange locRange) {
        this.warmContext.errorStack ~= locRange;
    }

    void popErrorLoc() {
        this.warmContext.errorStack = this.warmContext.errorStack[0 .. $ - 1];
    }

    (void | Error) assert2(bool test, LocRange locRange, string msg) {
        if (test) return;
        return fail(locRange, msg);
    }

    Error fail(LocRange locRange, string msg) {
        return new Error(warmContext.errorStack ~ locRange, msg);
    }

    string getLabel() { return this.warmContext.labelCounter.next; }

    int getUniqueId() { return this.warmContext.uniqCounter.next; }
}

// bleh cycle
abstract class ASTModuleBase
{
    string mangledName;

    abstract void addEntry(Protection protection, (ASTExternFunctionBase | ASTPragmaBase | ASTDeclaration) target);

    abstract void addAliasDecl(string name, Protection protection, ASTSymbol target);

    abstract nullable ASTSymbol getSymbolAlias(string name);
}

abstract class ASTPragmaBase
{
    abstract (FinishedSymbol | Error) compile(Context context);
}

abstract class ASTExternFunctionBase
{
    string name;

    abstract string repr();
}

// TODO clear all this up
abstract class FinishedSymbol
{
    abstract void emit(Generator generator);
    abstract void hash(Hash hash);
}

// cycle breaker helper: needed for CompilerBase
abstract class ModuleBase : Namespace
{
    string name;

    string mangledName;

    Package pak;

    abstract void addImport(ModuleBase module_, bool public_, (string name, Symbol symbol)[] symbols);

    abstract void addModuleDependency(ModuleBase module_);

    abstract (void | Error) compile(Context context);

    // Add symbol to list of anonymous symbols that will be emitted.
    abstract void track((Symbol | FinishedSymbol) sym);

    override string repr() => "Module";
}

struct ASTArgument
{
    ASTSymbol sym;

    string name;

    LocRange locRange;
}

struct ASTParameter
{
    string name;

    bool mutable;

    ASTSymbol type;

    nullable ASTSymbol defaultValue;

    LocRange locRange;

    string toString() {
        auto mutstr = "mut " if this.mutable else "";
        return "$mutstr$type $name";
    }
}

/*
 * Stackoverflow insists that "parameters" are the stuff in the function parameter list,
 * and "arguments" are the values you pass to a function.
 *
 * Fine by me.
 *
 * We could separate "declaration parameters" and "definition parameters."
 * For instance, extern(C) declarations are only interesting for generating a call,
 * and will never generate a function body. However, usually when meaningful information
 * is used to customize the define-site, this is also interesting for the call-site,
 * especially with regards to lifetime. As such, it's probably good there is only one type.
 */
struct Parameter
{
    bool isThisAssignment;

    string name;

    bool mutable;

    Type type;

    (nullable Expression | :callerRange) defaultValue;

    LocRange locRange;

    static Parameter fromType(Type type) {
        return Parameter(false, "", false, type, null, __RANGE__);
    }

    static Parameter simple(string name, Type type) {
        return Parameter(false, name, false, type, null, __RANGE__);
    }

    string toString() => "Parameter(isThisAssignment=$isThisAssignment, name=$name, mutable=$mutable, "
        ~ "type=$type, defaultValue=..., locRange=$locRange)";
}

alias LibraryCallRecord = (string soname, string fnname);

abstract class ParserHelper
{
    abstract (LibraryCallRecord | Error) proxyCall(ASTModuleBase astModule, string function_, void* ptr,
        LocRange locRange);
}

// FIXME class Object
class ASTImportStatementBase
{
}

/**
 * Helper class used to break dependency loops between neat.base, macros and the rest of the compiler.
 */
abstract class CompilerBase
{
    WorkPoolBase workPool;

    // for std.macro.cimport
    string[] cFlags;

    FileIdTable fileIdTable;

    mut ParserHelper parserHelper;

    // parser
    abstract (Parser | Error) createParser(string filename, string fulltext);

    abstract (Parser | Error) createFragmentParser(string fragment, LocRange locRange);

    // must be called or LocRange IDs may be wrong.
    abstract void disposeParser(Parser parser);

    // all packages for the current build
    abstract Package[] allPackages();

    abstract (nullable ASTSymbol | Error) parseExpression(
        Parser parser, LexicalContext lexicalContext);

    // Parse an expression that may be arithmetic, but not ternary-if.
    abstract (nullable ASTSymbol | Error) parseArithmetic(
        Parser parser, LexicalContext lexicalContext);

    abstract (nullable ASTSymbol | Error) parseExpressionLeaf(
        Parser parser, LexicalContext lexicalContext);

    abstract (nullable ASTSymbol | Error) parseType(
        Parser parser, LexicalContext lexicalContext);

    abstract (ASTStatement | Error) parseStatement(
        Parser parser, LexicalContext lexicalContext);

    abstract (nullable ASTIdentifierSymbol | Error) parseIdentifierSymbol(
        Parser parser, LexicalContext lexicalContext);

    abstract (nullable ASTDeclaration | Error) parseDeclaration(
        Parser parser, LexicalContext lexicalContext);

    abstract (ASTSymbol | Error) parseStringLiteral(
        Parser parser, LexicalContext lexicalContext);

    (ASTSymbol | Error) parseStringLiteral(
        Parser parser, LexicalContext lexicalContext, string separator, LocRange from)
    {
        return parseStringLiteral(parser, lexicalContext);
    }

    abstract (nullable ASTSymbolDeclaration | Error) parseTemplateStub(
        Parser parser, LexicalContext lexicalContext, ASTIdentifierSymbol name, string comment,
        (nullable ASTSymbolDeclaration | Error) delegate!() dg);

    abstract (ASTStatement | Error) parseFunctionBody(
        Parser parser, LexicalContext lexicalContext);

    abstract ASTStatement astExpressionStmt(ASTSymbol expr, LocRange locRange=__CALLER__);

    abstract ASTStatement astScope(ASTStatement[] stmts, LocRange locRange=__CALLER__);

    // sequence of statements that don't open a new scope
    abstract ASTStatement astSequence(ASTStatement[] stmts, LocRange locRange=__CALLER__);

    abstract ASTStatement astIf((ASTSymbol | ASTStatement) test, ASTStatement then, nullable ASTStatement else_,
        LocRange locRange=__CALLER__);

    abstract ASTStatement astForLoop(
        ASTStatement init, ASTSymbol test, ASTStatement step, ASTStatement body_, LocRange locRange=__CALLER__);

    abstract ASTStatement astExtForLoop(ASTSymbol source, ExtForVarDecl var1, (ExtForVarDecl | :none) var2,
        ASTStatement body_, LocRange locRange=__CALLER__);

    abstract ASTStatement astAssign(ASTSymbol target, ASTSymbol source, LocRange locRange=__CALLER__);

    // a += 2
    abstract ASTStatement astOpAssign(ASTSymbol left, string op, ASTSymbol right, LocRange locRange=__CALLER__);

    abstract ASTStatement astDeclareVar(ASTIdentifierSymbol name, bool mutable, bool uninitialized,
        nullable ASTSymbol initial, LocRange locRange=__CALLER__);

    abstract ASTStatement astDeclareVarExtract(ASTIdentifierSymbol name, bool mutable, bool infer,
        nullable ASTSymbol type, ASTSymbol source, LocRange locRange=__CALLER__);

    // initial is optional
    abstract ASTStatement astDeclareTypedVar(ASTIdentifierSymbol name, bool mutable, bool uninitialized,
        ASTSymbol type, nullable ASTSymbol initial, LocRange locRange=__CALLER__);

    abstract ASTSymbol astReturn(ASTSymbol value, LocRange locRange=__CALLER__);

    abstract ASTSymbol astBreak(LocRange locRange=__CALLER__);

    abstract ASTSymbol astContinue(LocRange locRange=__CALLER__);

    abstract ASTSymbol astSuper(LocRange locRange=__CALLER__);

    abstract ASTStatement astDeclarationStatement(ASTDeclaration target, LocRange locRange=__CALLER__);

    // compiler.$stmt
    abstract ASTStatement astQuotedStatement(string fragment, Package pak,
        ASTSymbol[] symbols, ASTStatement[] statements, ASTIdentifierSymbol[] identifiers, LocRange locRange=__CALLER__,
        nullable MacroState macroState = null);

    // compiler.$expr
    abstract ASTSymbol astQuotedExpression(string fragment, Package pak,
        ASTSymbol[] symbols, ASTStatement[] statements, ASTIdentifierSymbol[] identifiers,
        LocRange locRange=__CALLER__);

    // compiler.$type
    abstract ASTSymbol astQuotedType(string fragment, Package pak,
        ASTSymbol[] symbols, ASTStatement[] statements, ASTIdentifierSymbol[] identifiers,
        LocRange locRange=__CALLER__);

    abstract ASTSymbol astBinaryOp(string op, ASTSymbol left, ASTSymbol right, LocRange locRange=__CALLER__);

    abstract (ASTSymbol left, string op, ASTSymbol right | :else) destructAstBinaryOp(ASTSymbol sym);

    abstract (ASTSymbol decl, ASTSymbol[] types | :else) destructAstTemplateInstance(ASTSymbol sym);

    abstract ASTSymbol astCast(ASTSymbol target, ASTSymbol value, LocRange locRange=__CALLER__);

    abstract (ASTSymbol target, ASTSymbol value | :else) destructAstCast(ASTSymbol sym);

    abstract ASTSymbol astIndex(ASTSymbol base, ASTSymbol index, LocRange locRange=__CALLER__);

    abstract ASTSymbol astMember(ASTSymbol base, ASTIdentifierSymbol name, LocRange locRange=__CALLER__);

    abstract (ASTSymbol base, ASTIdentifierSymbol member | :else) destructAstMember(ASTSymbol astMember);

    abstract (ASTSymbol base, ASTSymbol index | :else) destructAstIndex(ASTSymbol astMember);

    abstract ASTSymbol astReference(ASTSymbol value, LocRange locRange=__CALLER__);

    abstract ASTSymbol astDereference(ASTSymbol value, LocRange locRange=__CALLER__);

    abstract ASTSymbol astNumberLiteral(long value, LocRange locRange=__CALLER__);

    abstract (long | :else) destructAstNumberLiteral(ASTSymbol sym);

    abstract ASTSymbol astStringLiteral(string text, LocRange locRange=__CALLER__);

    abstract ASTSymbol astCharLiteral(char ch, LocRange locRange=__CALLER__);

    abstract (string | :else) destructAstStringLiteral(ASTSymbol sym);

    abstract (ASTStatement[] | :else) destructAstSequence(ASTStatement stmt);

    abstract (ASTSymbol target, ASTArgument[] args | :else) destructAstCall(ASTSymbol sym);

    abstract ASTSymbol astFormatString(ASTSymbol[] parts, LocRange locRange=__CALLER__);

    ASTSymbol astBoolLiteral(bool value, LocRange locRange=__CALLER__) {
        if (value) return astIdentifier("true", locRange);
        else return astIdentifier("false", locRange);
    }

    abstract ASTSymbol astArrayLiteral(ASTSymbol[] values, LocRange locRange=__CALLER__);

    abstract ASTSymbol astTupleLiteral(ASTSymbol[] entries, LocRange locRange=__CALLER__);

    abstract ASTSymbol astTupleLiteral2((string name, ASTSymbol symbol)[] entries, LocRange locRange=__CALLER__);

    abstract ASTSymbol astArraySlice(ASTSymbol array, ASTSymbol lower, ASTSymbol upper, LocRange locRange=__CALLER__);

    // a .. b
    abstract ASTSymbol astIota(ASTSymbol from, ASTSymbol to, LocRange locRange=__CALLER__);

    abstract ASTSymbol astVoidLiteral(LocRange locRange=__CALLER__);

    abstract ASTIdentifierSymbol astIdentifier(string name, LocRange locRange=__CALLER__);

    abstract (string | :else) destructAstIdentifier(ASTSymbol sym);

    abstract ASTSymbol astNegation(ASTSymbol value, LocRange locRange=__CALLER__);

    abstract (ASTSymbol | :else) destructAstNegation(ASTSymbol sym);

    abstract ASTSymbol astCall(ASTSymbol target, ASTSymbol[] args, LocRange locRange=__CALLER__);

    abstract ASTSymbol astNewExpression(ASTSymbol type, (ASTSymbol[] | ASTArgument[]) args,
        LocRange locRange=__CALLER__);

    abstract ASTSymbol astDestroy(ASTSymbol target, LocRange locRange=__CALLER__);

    abstract ASTSymbol astStatementExpression(ASTStatement[] statements, ASTSymbol expr, LocRange locRange=__CALLER__);

    abstract ASTSymbol astArray(ASTSymbol elementType, bool mutableElements, LocRange locRange=__CALLER__);

    abstract ASTSymbol astBasicType(string name, LocRange locRange=__CALLER__);

    abstract ASTSymbol astTypeOf(ASTSymbol symbol, LocRange locRange=__CALLER__);

    abstract ASTSymbol astPointer(ASTSymbol target, LocRange locRange=__CALLER__);

    abstract ASTSymbol astFunctionPointer(ASTSymbol ret, ASTSymbol[] params, LocRange locRange=__CALLER__);

    abstract ASTSymbol astTupleType((string name, ASTSymbol type)[] members, LocRange locRange=__CALLER__);

    abstract ASTSymbolDeclaration astStructDecl(string name, ASTStructMember[] members, bool externC,
        LocRange locRange=__CALLER__);

    abstract ASTSymbol astUnion(string name, ASTUnionMember[] members, LocRange locRange=__CALLER__);

    abstract ASTSymbol astEitherType((ASTSymbol symbol, LocRange locRange)[] entries,
        LocRange locRange=__CALLER__);

    abstract ASTSymbol astEitherCaseExpr(ASTSymbol base, ASTEitherCaseExprCase[] cases, LocRange locRange=__CALLER__);

    abstract ASTStatement astEitherCaseStmt(ASTSymbol base, ASTEitherCaseStmtCase[] cases,
        nullable ASTStatement default_, LocRange locRange=__CALLER__);

    abstract ASTSymbol astNullable(ASTSymbol next, bool nullify, LocRange locRange=__CALLER__);

    abstract ASTExternFunctionBase astExternFunction(
        string name, ASTSymbol ret, ASTParameter[] params, bool variadic, LocRange retLocRange);

    abstract ASTModuleBase astModule(
        string name, Package pak, MacroState macroState, LocRange locRange, nullable ASTModuleBase parent);

    abstract ASTDeclaration astImport(string name, string pak, string[] symbols, LocRange locRange=__CALLER__);

    abstract ASTDeclaration astImport2(string name, string pak, string[] symbols, LocRange locRange=__CALLER__);

    abstract ASTPragmaBase astPragma(string pragma_, ASTSymbol[] args, LocRange locRange=__CALLER__);

    abstract ASTSymbol astParenPropertyExpression(ASTSymbol base, ASTSymbol prop, LocRange locRange=__CALLER__);

    abstract ASTModuleBase resolveImport(string pak, ASTImportStatementBase import_, LocRange locRange=__CALLER__);

    // expressions and statements
    abstract (nullable Expression | Error) implicitConvertTo(Context context, Expression from, Type to,
        LocRange locRange=__CALLER__);

    abstract (Expression | Error) binaryOp(string op, Context context, Expression left, Expression right,
        LocRange locRange=__CALLER__);

    abstract Expression intLiteral(int value);

    abstract Expression longLiteral(long value);

    abstract Expression wordLiteral(Platform platform, long value);

    abstract Expression boolLiteral(bool value);

    abstract Expression voidLiteral();

    abstract (Expression | Error) truthy(Context context, Expression value, LocRange locRange);

    abstract Expression castTo(Type target, Expression source);

    abstract Expression trivialCastTo(Type target, Expression source);

    abstract Expression stringLiteral(Platform platform, string value);

    abstract (nullable Expression | Error) isExpressionImplCall(Context context, Symbol symbol, LocRange locRange);

    abstract Reference stackFrame(Type type);

    abstract (nullable Expression | Error) call(
        Context context, ASTSymbol target, ASTArgument[] args, LocRange locRange, bool isImplCall);

    abstract Expression mkCall(Symbol target, Expression[] args, LocRange locRange=__CALLER__);

    abstract Expression simpleCall(Context context, string name, Type ret, Expression[] args,
        LocRange locRange=__CALLER__);

    abstract Expression pointerOffset(Expression pointer, Expression offset);

    // evaluate first `statement`, then `expression`.
    abstract Expression statementExpression(Statement statement, Expression expression);

    abstract Expression statementExpression(Statement statement, Expression expression, ExprInfo exprInfo);

    abstract Reference dereference(Expression value);

    abstract Expression reference(Reference ref_);

    abstract Expression functionReference(FunctionDeclarationBase funcDecl);

    abstract Expression wrap(nullable Statement before, Expression value, nullable Statement after);

    abstract (Expression | Error) wrapWithCleanup(Context context, Expression base, LocRange locRange,
        Expression delegate!(Expression) callback);

    // wrap(), allowing References
    abstract Expression wrapRef(nullable Statement before, Expression value, nullable Statement after);

    // Call dg with temporized `expr`.
    // If expr was a gift, it is freed after.
    abstract (Expression | Error) consume(
        Context context, Expression expr, (Expression | Error) delegate!(Expression) dg);

    abstract (nullable Expression | Error) consume(
        Context context, Expression expr, (nullable Expression | Error) delegate!(Expression) dg);

    abstract Statement consumeStmt(Context context, Expression expr, Statement delegate!(Expression) dg);

    /// Call dg with owned temp of expr.
    /// If expr was a gift, it is freed after.
    ///
    /// Set `mayUnwind` to true if `dg()` may unwind.
    /// in that case, borrowed `expr` must be copied.
    abstract (nullable Expression | Error) consumeTemporary(
            Context context, bool allowRefReturn, Expression expr,
            (nullable Expression | Error) delegate!(Expression) dg);

    abstract (nullable Symbol | Error) accessMember(
        Context context, Symbol base, string member, LocRange locRange, bool allowUndefined);

    abstract Reference structMemberReference(Reference base, int index);

    // look up name following the namespace in context
    abstract (nullable Symbol | Error) lookup(
        Context context, LocRange locRange, LookupReason reason, string name);

    abstract (Expression | Error) locRangeExpr(Context context, LocRange locRange);

    abstract Statement assignStatement(Reference target, Expression value);

    abstract Statement assignStatement(Reference target, Expression value, LocRange locRange);

    abstract Statement sequence(Statement first, nullable Statement second);

    Statement sequence2(nullable Statement first, Statement second) {
        if (auto first = first) return sequence(first, second);
        return second;
    }

    abstract Statement sequenceStatement(Statement[] stmts);

    abstract Statement ifStatement(Expression test, Statement then, nullable Statement else_);

    abstract Statement loopStatement(
            Context context, Statement initializer, Expression test, Statement body_, Statement step);

    abstract Statement returnStatement(Expression value);

    abstract Statement exprStatement(Expression test);

    abstract (Statement | Error) move(Context context, Reference target, Expression source, LocRange locRange);

    /// Create a temporary of `type`. Temporary is passed to `callback`, which returns an initializer.
    /// Returns Expression evaluating to "Initializer, then temporary".
    abstract (nullable Expression | Error) exprWithScratchspace(
        int uniqId, Type type, bool temporary, (nullable Statement | Error) delegate!(Reference) callback);

    abstract (Statement | Error) unwindScope(Context context, Namespace target, Statement next);

    abstract (nullable Statement | Error) stmtWithTemporary(
        int uniqId, Expression value, (nullable Statement | Error) delegate!(Reference) callback);

    abstract (nullable Expression | Error) exprWithTemporary(
        int uniqId, Expression value, (nullable Expression | Error) delegate!(Reference) callback);

    // don't create referenceable memory
    abstract (nullable Statement | Error) stmtWithTemporaryExpr(
        int uniqId, Expression value, (nullable Statement | Error) delegate!(Expression) callback);

    abstract (nullable Expression | Error) exprWithTemporaryExpr(
        int uniqId, Expression value, (nullable Expression | Error) delegate!(Expression) callback);

    abstract (nullable Expression | Error) exprWithTemporaryExpr(
        int uniqId, Expression value, bool copyLifetime,
        (nullable Expression | Error) delegate!(Expression) callback);

    /**
    * Create a runtime function that, given some parameters, declares and calls the ASTStatement
    * provided.
    * The function will be automatically linked in.
    */
    abstract FunctionDeclarationBase createRuntimeFunction(
        Context context, string name, Type ret, Parameter[] params, ASTStatement delegate!() makeBody);

    Namespace exprAlias(nullable Namespace parent, string name, Symbol value) {
        return symbolAlias(parent, name, value);
    }

    abstract Namespace symbolAlias(nullable Namespace parent, string name, Symbol value);

    abstract DeclarationHolder variableDeclaration(
        nullable Namespace parent, string name, Context context, Type type, bool mut, bool borrowed, bool hidden);

    abstract Type nativeWordType(Platform platform);

    abstract Type struct_(string name, StructMemberDeclaration[] members, LocRange locRange, string manglePrefix);

    abstract Type eitherType(Type[] types);

    abstract (Type | :else) isArrayType(Type type);

    abstract (string | :else) isBasicType(Type type);

    abstract (nullable Symbol | Error) primitiveIdentifier(Context context, string name);

    (Expression | Error) expectImplicitConvertTo(Context context, Expression from, Type to, LocRange locRange)
    {
        if (auto result = implicitConvertTo(context, from, to, locRange)?) return result;
        context.assert2(false, locRange, "Cannot convert to $(to.repr): $(from.type.repr)")?;
    }

    // true if ClassType or IntfType
    abstract bool isClassType(Type type);

    // called when expr is discarded (usually via ignored return value)
    abstract (void | Error) discardErrorCheck(Expression expr, LocRange locRange);

    abstract (void | Error) addDefaultImports(Context context, ModuleBase module_);

    abstract ModuleBase createModule(
        string name, string mangle, string moduleParseTaskId, LocRange locRange, nullable ModuleBase parent);

    abstract string queueModuleCompilation(Context context, ASTModuleBase module_);

    abstract (ModuleBase | Error) getCompiledModule(string id);

    LocRange makeLocRange((string | int) fileName, int fromRow, int fromColumn, int toRow, int toColumn) {
        int fileId = fileName.case(string s: -1, int i: i);
        return LocRange(fileId, (fromRow, fromColumn), (toRow, toColumn));
    }

    abstract IUniqCounter uniqCounter();
}

alias ASTStructMember = (string name, Protection protection, ASTSymbol type, nullable ASTSymbol default_);

alias ASTUnionMember = (string name, ASTSymbol type);

abstract class FunctionDeclarationBase : Symbol
{
    string name;

    /**
     * The field for the `ret` accessor.
     * The created function should only become globally visible once `ret` has been resolved.
     * Yes this identifier is supposed to look ugly.
     * See Function::inferReturnType.
     */
    mut nullable Type retWIP;

    Type ret() { return this.retWIP? else die; }

    Parameter[] params;

    mut bool variadic;

    mut nullable Type contextType; // must be a pointer

    abstract void declare(Generator output);

    abstract string mangle();

    override bool mayCallImplicit() {
        for (param in params)
            if (param.defaultValue == null)
                return false;
        return true;
    }
}

/**
 * This is in base because it's circular with Context.
 */
class MacroState
{
    mut Macro[] macros;

    mut MacroState[] imports;

    // A record of every dynamic library call done to
    // get the macro state to where it currently is.
    // This is used for macro caching.
    mut LibraryCallRecord[] records;

    this() { }

    MacroState dup() {
        auto newState = new MacroState;
        newState.macros = macros.dup.freeze;
        newState.imports = imports.dup.freeze;
        newState.records = records.dup.freeze;
        return newState;
    }

    void applyMacro(MacroArgs args) {
        this.applyMacroExported(args);
        if (args.done) return;
        for (import_ in this.imports) {
            import_.applyMacroExported(args);
            if (args.done) return;
        }
    }

    void applyMacroExported(MacroArgs args) {
        for (macro_ in this.macros) {
            macro_.apply(args);
            if (args.done) return;
        }
    }

    void addImport(MacroState target) {
        this.imports ~= target;
    }

    void addMacro(Macro macro_) {
        this.macros ~= macro_;
    }
}

abstract class Macro
{
    abstract void apply(MacroArgs args);
}

// macro subclasses are differentiated by args
abstract class MacroArgs
{
    abstract bool done();
}

// hook the ASTCall -> Call transform
class CallMacroArgs : MacroArgs
{
    ASTSymbol target;
    ASTArgument[] args;
    Context context;
    LocRange locRange;
    mut (nullable Expression | Error) transformed; // out
    this() {
        this.transformed = null;
    }
    void set(this.target, this.args, this.context, this.locRange=__CALLER__) {
        this.transformed = null;
    }
    override bool done() {
        return this.transformed.case(nullable Expression expr: !!expr, Error: true);
    }
}

/// Placed here to allow quoting a.case()
struct ASTEitherCaseExprCase
{
    LocRange locRange;

    ASTSymbol type;

    // may be null
    string identifier;

    ASTSymbol expr;
}

struct ASTExprCaseExprCase
{
    LocRange locRange;

    ASTSymbol value;

    ASTSymbol expr;
}

// alternate interpretation: value.case(2: "A", 3: "B");
(ASTExprCaseExprCase | Error) reinterpretAsExprCase(ASTEitherCaseExprCase arg, Context context) {
    context.assert2(arg.identifier == "", arg.locRange, "Expression case cannot have a name")?;
    return arg.(ASTExprCaseExprCase(locRange, type, expr));
}

/**
 * Tag types that are reinterpretable as sumtypes.
 * This exists for one usecase only: so that you can do
 * ```
 * nullable Object obj;
 * Object obj = obj.case(null: return null);
 * ```
 */
interface CanTreatAsEither
{
    (nullable Expression | Error) toEitherType(Context context, Expression base);
}

///
struct ASTEitherCaseStmtCase
{
    LocRange locRange;

    ASTSymbol type;

    string identifier;

    ASTStatement stmt;
}

final class Overload : Symbol
{
    Symbol[] parts;

    this(this.parts) { }

    override bool mayCallImplicit() => true;

    override string repr() {
        mut string partsRepr;
        for (i, part in parts) {
            if (i) partsRepr ~= ", ";
            partsRepr ~= part.repr;
        }
        return "[$partsRepr]";
    }
}

// hook parseExpressionBase
class ParseExpressionBaseArgs : MacroArgs
{
    Parser parser;
    LexicalContext lexicalContext;
    mut (nullable ASTSymbol | Error) symbol; // out
    this(this.parser, this.lexicalContext) {
        this.symbol = null;
    }
    override bool done() {
        return this.symbol.case(nullable ASTSymbol sym: !!sym, Error: true);
    }
}

// hook parseProperties
class ParsePropertyArgs : MacroArgs
{
    Parser parser;
    LexicalContext lexicalContext;
    ASTSymbol left;
    mut (nullable ASTSymbol | Error) result; // out
    this(this.parser, this.lexicalContext, this.left) {
        this.result = null;
    }
    override bool done() {
        return this.result.case(nullable ASTSymbol sym: !!sym, Error: true);
    }
}

// hook parseStatement
class ParseStatementArgs : MacroArgs
{
    Parser parser;
    LexicalContext lexicalContext;
    mut (nullable ASTStatement | Error) statement; // out
    this(this.parser, this.lexicalContext) {
        this.statement = null;
    }
    override bool done() {
        return this.statement.case(nullable ASTStatement stmt: !!stmt, Error: true);
    }
}

bottom die() { import backend.base : die; die; }

interface ImportModuleBaseTask : ITask
{
    (ASTModuleBase | Error) module_();
}

// hook "import "
class ParseImportArgs : MacroArgs
{
    Parser parser;
    LexicalContext lexicalContext;
    bool toplevel;
    mut (nullable ASTModuleBase | Error | ImportModuleBaseTask) module_; // out
    this(this.parser, this.lexicalContext, this.toplevel) {
        this.module_ = null;
    }
    (ASTModuleBase | ImportModuleBaseTask | Error) getModule(CompilerBase compiler) {
        return this.module_.case(
            nullable ASTModuleBase base: base? else die,
            ImportModuleBaseTask task: task,
            Error err: err);
    }
    override bool done() {
        return this.module_.case(
            ImportModuleBaseTask task: true,
            nullable ASTModuleBase mod: !!mod,
            Error: true);
    }
}

abstract class Parser
{
    // Whether our file ID must be preserved in the next binary.
    mut bool pinned;

    abstract void begin();
    abstract void commit();
    abstract void revert();
    abstract bool accept(string match);
    abstract Error fail(string message);
    abstract LocRange loc();
    abstract LocRange from();
    abstract LocRange to(LocRange from);
    abstract void strip();
    abstract string parseLastComment();
    abstract string remainingText();
    abstract bool acceptToken(TokenType type);
    abstract bool acceptToken2(TokenType first, TokenType second);
    abstract bool acceptToken3(TokenType first, TokenType second, TokenType third);
    abstract bool acceptToken2Not(TokenType match, TokenType nomatch);
    abstract bool acceptToken2Not2(TokenType match, TokenType nomatch1, TokenType nomatch2);
    abstract (string | :none) acceptTokenStr(TokenType type);
    abstract bool acceptIdentifier(string identifier);
    abstract (void | Error) expectToken(TokenType token);
    abstract bool peekToken(TokenType type);
    abstract void dropToken();
    abstract bool eof();
    abstract bool hard_eof();
    abstract (void | Error) verifyTransactions(string msg, (void | Error) delegate!() dg);
    abstract string parseIdentifier();
    abstract (:failure | :success, long, bool withBasePrefix | Error) parseNumber();

    (void | Error) assert_(bool flag, string message)
    {
        if (!flag) return this.fail(message);
        return;
    }

    (void | Error) expect(string match)
    {
        if (this.accept(match))
            return;
        return this.fail("'" ~ match ~ "' expected");
    }

    ParserTransaction transaction() {
        return ParserTransaction(this, committed=false);
    }

    bool isKeyword(string identifier) {
        // :sigh: TODO Give macros the ability to define custom reserved keywords.
        if (identifier == "the") return true;
        return identifier == "mut" || identifier == "auto" || identifier == "new" || identifier == "return";
    }
}

(void | Error) expectIdentifier(Parser parser, string match)
{
    if (parser.acceptIdentifier(match))
        return;
    return parser.fail("'" ~ match ~ "' expected");
}

bool acceptTokenIdentifier(Parser parser, TokenType first, string second) with (parser)
{
    if (!peekToken(first)) return false;
    begin;
    dropToken;
    if (!acceptIdentifier(second)) {
        revert;
        return false;
    }
    commit;
    return true;
}

struct ParserTransaction
{
    private Parser parser;
    private bool committed;
    void onEnter() {
        parser.begin;
    }
    void onExit() {
        if (!committed) parser.revert;
    }
    void commit() {
        assert(!committed);
        parser.commit;
        committed = true;
    }
}

class StructMemberDeclaration
{
    string name;

    Protection protection;

    Type type;

    (Expression expr, LocRange range | nullptr_t) default_;

    this(this.name, this.protection, this.type, this.default_=null) { }
}

abstract class LexicalContext
{
    CompilerBase compiler;

    Package pak;

    // here so downstream tasks can be declared as depending on parsing this module
    string moduleParseTaskId;

    MacroState macroState;

    /**
     * Quoting logic: "$a" will pass `new ASTIdentifier("a")` to `allocQuoteToken`,
     * save the resulting offset, and later use `Context.getQuote*` to resolve.
     * Except actually it just errors because you can't use macro tokens outside
     * QuotedLexicalContext.
     */
    (int | Error) allocQuoteToken(ASTSymbol symbol, QuoteTokenCategory category) {
        return symbol.locRange.fail("Quasiquote outside of quoted environment");
    }

    /**
     * We didn't need this quote token after all.
     * Used when we back out a quoted identifier parse rule.
     */
    void revertQuoteToken(int token, QuoteTokenCategory category) {
        die;
    }

    int quoteScope() {
        assert(false);
    }

    // break an annoying dependency cycle
    abstract (ASTModuleBase | Error) resolveImport(ASTImportStatementBase importStmt);
}

enum QuoteTokenCategory {
    symbol,
    statement,
    identifier,
}

class Package
{
    string name;
    string path;
    // whether to run unittests in this package
    mut bool unittest_;
    mut Package[] deps;

    this(this.name, this.path, this.deps) { }

    void addDependency(Package dep) {
        this.deps ~= dep;
    }

    void enableUnittest() {
        this.unittest_ = true;
    }

    ASTSymbol quote(CompilerBase compiler) {
        mut ASTSymbol[] deps_;
        for (auto dep in this.deps)
            deps_ ~= dep.quote(compiler);
        return compiler.astNewExpression(
            compiler.astIdentifier("Package"), [
                compiler.astStringLiteral(this.name),
                compiler.astStringLiteral(this.path),
                compiler.astArrayLiteral(deps_)]);
    }

    string repr() { return toString; }

    string toString() {
        mut string depStr;
        for (dep in deps) {
            if (depStr.length) depStr ~= ", ";
            depStr ~= dep.name;
        }
        return "Package($name, $path, [$depStr])";
    }
}

abstract class WorkPoolBase
{
    abstract void queue(ITask task);
    abstract ITask wait(string id);
    // if `provider` is not fresh, `consumer` is not fresh.
    abstract void dependency((string | :current) provider, (string | :current) consumer);
    /**
     * The bill-of-materials system allows validating that an artifact is still current
     * without actually parsing anything. We attach bill items, which are key-value pairs,
     * to the current task.
     * Then we can query all bill items that are transitively part of a task.
     * The point is that, for instance for a macro object, we can store the dynamic filename
     * and bill of materials; then when we need to reload the macro, we just check that the
     * BOM is still current.
     * Though the API is kept generic, in practice `id` will be a filename and `value` a hash.
     */
    abstract void addBomItem(string id, string value);
    abstract string[string] bom(string id);
}

interface ITask
{
    void run(WorkPoolBase workPool);
    string id();
    // Return false if environment conditions have changed from when the task was added.
    // For instance, if a file changed checksum or last-modified date.
    bool fresh();
}

class Error __errorclass
{
    LocRange[] stack;

    string msg;

    this(this.stack, this.msg) { }

    string toString() => "Error($msg)";
}

interface FileIdTable
{
    int toFileId(string filename);
    void setInheritedFileId(int id, string filename);
    string toFileName(int fileId);
    void pin(int fileId);
}

string repr(LocRange locRange, FileIdTable fileIdTable) {
    return fileIdTable.toFileName(locRange.fileId)
        ~ ":" ~ itoa(locRange.from.row + 1)
        ~ ":" ~ itoa(locRange.from.column + 1);
}

string toString(LocRange locRange) with (locRange) {
    if (to.row || to.column) {
        return "[?$fileId]:$(from.row+1):$(from.column+1)..$(to.row+1):$(to.column+1)";
    }
    return "[?$fileId]:$(from.row+1):$(from.column+1)";
}

// This should have been caught earlier.
void hardCheck(LocRange locRange, bool flag, string message) {
    if (flag) return;
    print("$(locRange.toString): Internal compiler error!");
    print(message);
    exit(1);
}

bottom die(LocRange locRange, string message) {
    print("$(locRange.toString): Internal compiler error!");
    print(message);
    exit(1);
}

extern(C) void exit(int);

void assert(bool test) {
    import helpers : assert;
    assert(test);
}

(void | Error) assert(LocRange locRange, bool test, (string delegate!() | string) msg) {
    if (!test) return locRange.fail(msg.case(string delegate!() dg: dg()));
}

BackendLocation toBackendLoc(LocRange locRange, FileIdTable fileIdTable) {
    mut BackendLocation ret;
    ret.file = fileIdTable.toFileName(locRange.fileId);
    ret.line = locRange.from.row;
    ret.column = locRange.from.column;
    return ret;
}

Error fail(LocRange locRange, string message) {
    return new Error([locRange], message);

}

bottom exitWithError(Error err, nullable FileIdTable fileIdTable = null) {
    printError(err, fileIdTable);
    exit(1);
}

void printError(Error err, nullable FileIdTable fileIdTable = null) {
    assert(err.stack.length > 0);
    if (auto fileIdTable = fileIdTable) {
        for (loc in err.stack[0 .. $ - 1])
            print(loc.repr(fileIdTable) ~ ":");
    } else {
        for (loc in err.stack[0 .. $ - 1])
            print(loc.toString ~ ":");
    }
    err.stack[$ - 1].printAtErrorLoc(fileIdTable, err.msg);
}

void printAtErrorLoc(LocRange locRange, nullable FileIdTable fileIdTable, string message) {
    mut string filename = "";
    if (auto fileIdTable = fileIdTable)
        filename = fileIdTable.toFileName(locRange.fileId);
    if (filename.empty || !exists(filename)) {
        print("$(filename):$(locRange.from.row + 1):$(locRange.from.column + 1): $message");
        return;
    }
    auto text = read(filename);
    print("$(filename):$(locRange.from.row + 1):");
    auto line = text.getLine(locRange.from.row);
    print(line);
    if (locRange.(from.row != to.row || from.column == to.column)) {
        mut string spacer;
        for (i in 0 .. locRange.from.column) spacer ~= " ";
        print("$spacer^ $message");
    } else {
        mut string wiggle;
        for (i in 0 .. locRange.from.column) wiggle ~= " ";
        for (i in locRange.from.column .. locRange.to.column) wiggle ~= "~";
        print("$wiggle $message");
    }
}

string getLine(string text, int line) {
    auto lines = text.split("\n");
    if (line >= lines.length) return "???????????????";
    return lines[line];
}