parser.cpp

Go to the documentation of this file.

#include "mim/ast/parser.h"
 
#include <filesystem>
#include <ranges>
 
#include "mim/driver.h"
 
#include "family.h"
 
using namespace std::literals;
 
namespace mim::ast {
 
using Tag = Tok::Tag;
 
/*
 * entry points
 */
 
Ptr<File> Parser::parse_file() {
    auto track = tracker();
    auto decls = parse_decls();
    bool where = ahead().isa(Tag::K_where);
    expect(Tag::EoF, "file");
    auto file = ptr<File>(track, ast().scope(), ast().copy(decls));
    // curr_ is the stray `;`; file->loc().anew_end() would sit past the end of that line and render no snippet.
    if (where) error().n(curr_, "did you accidentally end your declaration expression with a `;`?");
    return file;
}
 
const File* Parser::import(Dbg dbg, bool is_path, Tok::Tag tag, std::ostream* md, bool record) {
    auto name   = dbg.sym();
    auto plugin = tag == Tag::K_plugin ? Driver::plugin_name(name.view()) : std::string();
    if (tag == Tag::K_plugin && !driver().is_loaded(plugin) && !driver().flags().bootstrap)
        driver().load(name.view(), dbg.loc());
 
    driver().log().v("📥 import `{}`", name);
 
    auto file = fs::path(name.view());
    if (!file.has_extension()) file.replace_extension("mim"); // TODO error cases
 
    auto path  = fs::path();
    auto probe = [&path](fs::path p) {
        if (std::error_code ec; !fs::is_regular_file(p, ec)) return false;
        path = std::move(p);
        return true;
    };
 
    // A plugin's two halves must be the pair that shipped together, so take the `.mim` from the library's directory.
    if (auto dir = plugin.empty() ? nullptr : driver().plugin_dir(plugin)) {
        auto mim = fs::path(plugin).replace_extension("mim");
        if (!probe(*dir / mim)) probe(*dir / plugin / mim);
    }
 
    // A path is relative to the importing file first; a bare name is only ever looked up in the search paths.
    if (path.empty() && is_path && !file.is_absolute()) probe(curr_dir() / file);
 
    if (path.empty()) {
        for (const auto& dir : driver().import_paths())
            // `some/dir/foo.mim` must not also be probed as `some/dir/foo.mim/foo.mim`.
            if (probe(dir / file) || (!is_path && probe(dir / name.view() / file))) break;
    }
 
    if (path.empty()) {
        if (std::error_code ec; fs::is_directory(fs::path(name.view()), ec))
            error().e(dbg.loc(), "`{}` is a directory, not a Mim file", name);
        else
            error().e(dbg.loc(), "cannot find `{}` in the search paths", name);
        return {};
    }
 
    auto [src, _] = driver().src().add(path);
    if (!src) {
        error().e(dbg.loc(), "cannot read file `{}`", path.string());
        return {};
    }
 
    if (record) driver().imports().add(src, name, tag, is_path);
    return import(*src, md, dbg.loc());
}
 
const File* Parser::import(std::istream& is, fs::path path, Loc loc, std::ostream* md) {
    if (!is) {
        error().e(loc, "cannot read file `{}`", path.string());
        return {};
    }
    auto [src, _] = driver().src().add(std::move(path), fe::SrcMap::slurp(is));
    return import(*src, md, loc);
}
 
const File* Parser::import(const fe::Src& src, std::ostream* md, Loc loc) {
    auto [slot, fresh] = ast().file(&src);
    if (!fresh) {
        // An empty slot is a file that is still being parsed further up the stack.
        if (!slot) error().e(loc, "cyclic import of `{}`", src.path().string());
        return slot.get();
    }
 
    driver().log().v("📄 read `{}`", src.path().string());
 
    auto state = std::tuple(curr_, ahead_, lexer_);
    auto lexer = Lexer(driver(), src, md);
    lexer_     = &lexer;
    init();
    auto parsed                     = parse_file();
    std::tie(curr_, ahead_, lexer_) = state;
 
    slot = parsed;
    return slot.get();
}
 
Ptrs<UseDecl> Parser::import_plugins(fe::View<std::string> plugins, Tok::Tag tag) {
    Ptrs<UseDecl> imports;
    for (const auto& name : plugins) {
        auto dbg     = Dbg(Loc(), driver().sym(name));
        bool is_path = fs::path(name).has_parent_path();
        if (auto file = import(dbg, is_path, tag))
            imports.emplace_back(ptr<UseDecl>(Loc(), Mods{}, tag, path(dbg), Sym(), Dbg(), false, file));
    }
    return imports;
}
 
const File* Parser::import_main(std::string_view input, fe::View<std::string> plugins, std::ostream* md) {
    auto imports = import_plugins(plugins, Tag::K_plugin);
    auto file    = import({Loc(), driver().sym(input)}, true, Tag::K_import, md, false);
    if (file) file->add_implicit_imports(ast().copy(imports));
    return file;
}
 
/*
 * misc
 */
 
Ptr<UseDecl> Parser::parse_import_or_plugin(Tracker track, Mods mods) {
    auto tag    = lex().tag();
    auto entity = fe::Cite(tag == Tag::K_import ? "import" : "plugin");
    if (mods.is_extern) error().e(curr_, "`extern` is only meaningful on a function declaration, not on `{}`", entity);
    if (mods.is_anx) error().e(curr_, "`anx` doesn't apply to `{}` - it never represents a single value", entity);
    auto vis = mods.vis.value_or(Vis::Priv);
 
    Dbg name;
    Sym file_path;
    if (ahead().isa(Tag::L_str)) {
        name      = lex().dbg();
        file_path = name.sym();
    } else {
        auto tok = expect(Tag::M_id, "{} name", entity);
        if (!tok) return {};
        name = tok.dbg();
    }
 
    Dbg alias;
    bool splice = false;
    if (accept(Tag::K_as)) {
        if (accept(Tag::T_star))
            splice = true;
        else
            alias = parse_id("alias of an import");
    }
    expect(Tag::T_semicolon, "end of {}", entity);
 
    auto mod = name;
    if (file_path) {
        auto stem  = fs::path(file_path.view()).stem().string();
        bool is_id = Lexer::is_id(stem);
        if (!is_id && !alias && !splice) {
            error()
                .e(name.loc(), "cannot derive a module name from `{}`", file_path)
                .n("name it explicitly with `as`")
                .n("or splice its members into this scope with `as *`");
            return {};
        }
        mod.set(is_id ? ast().sym(stem) : Sym());
    }
 
    if (auto file = import(name, (bool)file_path, tag))
        return ptr<UseDecl>(track, Mods{vis}, tag, path(mod), file_path, alias, splice, file);
    return {};
}
 
Dbg Parser::parse_id(fe::Cite ctxt) {
    if (auto id = accept(Tag::M_id)) return id.dbg();
    syntax_err("identifier", ctxt);
    return {missing(), driver().sym("<error>")};
}
 
Ptr<Path> Parser::parse_path(fe::Cite ctxt) {
    auto track = tracker();
    auto dbgs  = Dbgs{parse_id(ctxt)};
    while (accept(Tag::T_dot))
        dbgs.emplace_back(parse_id("component of a path"));
    return ptr<Path>(track, dbgs);
}
 
Ptr<Expr> Parser::parse_type_ascr(fe::Cite ctxt) {
    if (accept(Tag::T_colon)) return parse_expr(ctxt);
    syntax_err("`:`", ctxt);
    return ptr<ErrorExpr>(missing());
}
 
/*
 * exprs
 */
 
Ptr<Expr> Parser::parse_expr(fe::Cite ctxt, Prec curr_prec) {
    // An empty ctxt makes the expression optional, so there is nothing to recover into.
    if (ctxt) recover(ctxt);
    auto track = tracker();
    auto lhs   = parse_primary_expr(ctxt);
    return parse_infix_expr(track, lhs, curr_prec, ctxt);
}
 
Ptr<Expr> Parser::parse_infix_expr(Tracker track, Ptr<Expr> lhs, Prec curr_prec, fe::Cite ctxt) {
    auto prev = Prec::Err; // precedence this loop built last; a non-associative one must not repeat
    while (true) {
        // A closing delimiter nobody is waiting for must not end the expression.
        recover(ctxt ? ctxt : fe::Cite("expression"));
 
        if (auto prec = Tok::infix_prec(ahead().tag())) {
            if (should_reduce(curr_prec, *prec)) return lhs;
            if (*prec == prev && prec_assoc(*prec) == Assoc::N)
                error()
                    .e(ahead().loc(), "operator `{}` is not associative", ahead())
                    .n("parenthesize the left- or right-hand side");
            prev     = *prec;
            auto op  = lex();
            auto rhs = parse_expr(*prec, "right-hand side of the `{}` operator", op);
            lhs      = ptr<InfixExpr>(track, lhs, op, rhs, sugar_callee(op));
            continue;
        }
 
        // Application juxtaposes its operands, so there is no operator token to drive the loop above.
        if (ISA(ahead().tag(), C_EXPR)) {
            if (should_reduce(curr_prec, Prec::App)) return lhs;
            if (ISA(ahead().tag(), C_DECL))
                error()
                    .w(ahead().loc(), "you are passing a declaration expression as argument")
                    .n(lhs->loc(), "passed to this expression")
                    .n("if this was your intention, consider parenthesizing the declaration expression")
                    .n(lhs->loc().anew_end(), "or insert a `;` here");
            auto rhs = parse_expr("argument to an application", Prec::App);
            lhs      = ptr<AppExpr>(track, lhs, rhs);
            continue;
        }
 
        // `where` trails a whole declaration block instead of an expression, and closes the expression for good.
        if (ahead().isa(Tag::K_where)) {
            if (should_reduce(curr_prec, Prec::Where)) return lhs;
            lex();
            auto decls = parse_decls();
            lhs        = ptr<DeclExpr>(track, lhs, true, decls);
 
            bool where = ahead().tag() == Tag::K_where;
            expect(Tag::K_end, "end of a where declaration block");
            if (where) error().n(curr_, "did you accidentally end your declaration expression with a `;`?");
        }
 
        return lhs;
    }
}
 
Ptr<Expr> Parser::parse_prefix_expr() {
    auto track = tracker();
    auto op    = lex();
    auto rhs   = parse_expr(Prec::Prefix, "operand of the prefix `{}` operator", op);
    return ptr<PrefixExpr>(track, op, rhs);
}
 
Ptr<Expr> Parser::sugar_callee(Tok op) {
    auto sym = Tok::infix_sym(op.tag());
    return sym.empty() ? nullptr : path_expr(Dbg(op.loc(), driver().sym(sym)));
}
 
Ptr<Expr> Parser::parse_match_expr() {
    auto track = tracker();
    expect(Tag::K_match, "opening match for union destruction");
    auto scrutinee = parse_expr("destroyed union element");
    expect(Tag::K_with, "match");
    Ptrs<MatchExpr::Arm> arms;
    accept(Tag::T_pipe);
    do {
        auto track   = tracker();
        auto index   = std::optional<nat_t>();
        auto ctor    = Dbg();
        auto ptrn    = Ptr<Ptrn>();
        auto payload = [&] { return parse_ptrn({}, "payload of a constructor in a match-arm", Prec::Bot); };
        if (auto lit = accept(Tag::L_u)) {
            index = lit.lit_u();
            if (!ahead().isa(Tag::T_fat_arrow)) ptrn = payload();
        } else {
            ptrn = parse_ptrn({}, "right-hand side of a match-arm", Prec::Bot);
            if (auto id = ptrn->isa<IdPtrn>(); id && !id->type() && !ahead().isa(Tag::T_fat_arrow)) {
                ctor = id->dbg();
                ptrn = payload();
            }
        }
        expect(Tag::T_fat_arrow, "arm of a match-expression");
        auto body = parse_expr("arm of a match-expression");
        arms.emplace_back(ptr<MatchExpr::Arm>(track, index, ctor, ptrn, body));
    } while (accept(Tag::T_pipe));
 
    return ptr<MatchExpr>(track, scrutinee, arms);
}
 
Ptr<Expr> Parser::parse_variant_expr() {
    auto track = tracker();
    Ptrs<VariantExpr::Ctor> ctors;
    eat(Tag::T_pipe);
    // A `|` without any constructor is the empty variant, as in OCaml.
    if (ahead().isa(Tag::M_id)) {
        do {
            auto track = tracker();
            auto dbg   = parse_id("constructor of a variant");
            auto type  = Ptr<Expr>();
            if (auto colon = accept(Tag::T_colon)) {
                if (ahead().isa(Tag::T_pipe))
                    error()
                        .w(colon.loc(), "payload of constructor `{}` swallows the remaining constructors", dbg.sym())
                        .n("drop the `:` if `{}` carries no payload", dbg.sym())
                        .n("parenthesize the payload if a nested variant is intended");
                type = parse_expr("payload of a variant constructor");
            }
            ctors.emplace_back(ptr<VariantExpr::Ctor>(track, dbg, type));
        } while (accept(Tag::T_pipe));
    }
    return ptr<VariantExpr>(track, ctors);
}
 
Ptr<Expr> Parser::parse_primary_expr(fe::Cite ctxt) {
    if (Tok::is_prefix(ahead().tag())) return parse_prefix_expr();
    // clang-format off
    switch (ahead().tag()) {
        case Tag::C_PRIMARY: return ptr<PrimaryExpr>(lex());
        case Tag::C_ID:      return ptr<PathExpr>(parse_path());
        case Tag::C_LIT:
        case Tag::C_SIGN:    return parse_lit_expr();
        case Tag::C_DECL:    return parse_decl_expr();
        case Tag::C_PI:      return parse_pi_expr();
        case Tag::C_LM:      return parse_lam_expr();
        case Tag::C_SEQ:     return parse_seq_or_single_expr();
        case Tag::K_ret:     return parse_ret_expr();
        case Tag::D_brckt_l: return parse_sigma_expr();
        case Tag::D_paren_l: return parse_tuple_expr();
        case Tag::K_Type:    return parse_type_expr();
        case Tag::K_Rule:    return parse_rule_expr();
        case Tag::K_match:   return parse_match_expr();
        case Tag::T_pipe:    return parse_variant_expr();
        default:
            if (!ctxt) return nullptr;
            syntax_err("primary expression", ctxt);
    }
    // clang-format on
    return ptr<ErrorExpr>(missing());
}
 
Ptr<Expr> Parser::parse_seq_or_single_expr() {
    auto track   = tracker();
    bool is_pack = ahead().isa(Tag::D_angle_l);
    auto delim_l = is_pack ? Tag::D_angle_l : Tag::D_quote_l;
    auto delim_r = Tok::delim_l2r(delim_l);
    auto arities = fe::Vector<std::pair<Ptr<IdDecl>, Ptr<Expr>>>();
    auto _       = anchor(eat(delim_l), delim_r);
    auto ctxt    = fe::Cite(is_pack ? "shape of a pack or a singleton term introduction"
                                    : "shape of an array or a singleton type formation");
 
    do {
        Dbg dbg;
        if (ahead(0).isa(Tag::M_id) && ahead(1).isa(Tag::T_colon)) {
            dbg = eat(Tag::M_id).dbg();
            eat(Tag::T_colon);
        }
 
        auto expr = parse_expr(ctxt);
        // The `;` is what tells a shape from a singleton, so `«e»`/`‹e›` is the latter.
        if (arities.empty() && !dbg && ahead().isa(delim_r)) {
            eat(delim_r);
            return ptr<SingleExpr>(track, is_pack, expr);
        }
        arities.emplace_back(ptr<IdDecl>(dbg), expr);
        ctxt = fe::Cite(is_pack ? "shape of a pack" : "shape of an array");
    } while (accept(Tag::T_comma) && !ahead().isa(Tag::T_semicolon));
 
    expect(Tag::T_semicolon, fe::Cite(is_pack ? "pack" : "array"));
    auto body = parse_expr(fe::Cite(is_pack ? "body of a pack" : "body of an array"));
    recover(fe::Cite(is_pack ? "pack" : "array"));
    expect(delim_r, fe::Cite(is_pack ? "closing delimiter of a pack" : "closing delimiter of an array"));
 
    // `‹a, b; e›` nests one SeqExpr per arity; only the outermost one covers the delimiters.
    for (auto& [index, shape] : arities | std::views::reverse) {
        auto loc = &index == &arities.front().first ? Loc(track) : (index->dbg() ? index->loc() : shape->loc()) + curr_;
        body     = ptr<SeqExpr>(loc, is_pack, index, shape, body);
    }
 
    return body;
}
 
Ptr<Expr> Parser::parse_decl_expr() {
    auto track = tracker();
    auto decls = parse_decls();
    auto expr  = parse_expr("final expression of a declaration expression");
    return ptr<DeclExpr>(track, expr, false, decls);
}
 
/// Applies a leading `-` to a numeric literal Tok.
static Tok negate(Tok tok) {
    switch (tok.tag()) {
        case Tag::L_u: return {tok.loc(), std::bit_cast<s64>(-tok.lit_u())};
        case Tag::L_f: return {tok.loc(), -std::bit_cast<f64>(tok.lit_u())};
        case Tag::L_i: {
            auto [mod, val] = tok.lit_i();
            return {tok.loc(), mod, mod == 0 ? -val : (mod - val % mod) % mod};
        }
        default: std::unreachable();
    }
}
 
Ptr<Expr> Parser::parse_lit_expr() {
    auto track = tracker();
    auto sign  = ISA(ahead().tag(), C_SIGN) ? lex() : Tok();
 
    if (sign && !ISA(ahead().tag(), C_LIT_NUM)) {
        syntax_err("numeric literal", "signed literal");
        return ptr<ErrorExpr>(missing());
    }
 
    auto tok  = sign.isa(Tag::T_sub) ? negate(lex()) : lex();
    auto type = accept(Tag::T_colon) ? parse_expr("literal", Prec::Lit) : nullptr;
    return ptr<LitExpr>(track, tok, type);
}
 
Ptr<Expr> Parser::parse_sigma_expr() {
    auto track = tracker();
    auto ptrn  = parse_tuple_ptrn({.brckt = true});
    switch (ahead().tag()) {
        case Tag::K_as: {
            lex();
            auto alias = ptr<AliasPtrn>(track, ptrn, parse_id("alias pattern"));
            return parse_pi_expr(alias);
        }
        case Tag::T_arrow_r: return parse_pi_expr(ptrn);
        default: return ptr<SigmaExpr>(ptrn);
    }
}
 
Ptr<Expr> Parser::parse_tuple_expr() {
    auto track = tracker();
    Ptrs<Expr> elems;
    parse_list("tuple", Tag::D_paren_l, [&]() { elems.emplace_back(parse_expr("tuple element")); });
    return ptr<TupleExpr>(track, elems);
}
 
Ptr<Expr> Parser::parse_type_expr() {
    auto track = tracker();
    eat(Tag::K_Type);
    auto level = parse_expr("type level", Prec::App);
    return ptr<TypeExpr>(track, level);
}
 
Ptr<Expr> Parser::parse_rule_expr() {
    auto track = tracker();
    eat(Tag::K_Rule);
    return ptr<RuleExpr>(track, parse_expr("domain of rule", Prec::App));
}
 
Ptr<Expr> Parser::parse_pi_expr() {
    auto track      = tracker();
    auto tag        = ahead().tag();
    fe::Cite entity = "dependent function type";
 
    if (accept(Tag::K_Cn))
        entity = "continuation type";
    else if (accept(Tag::K_Fn))
        entity = "returning continuation type";
 
    auto domt = tracker();
    auto prec = ISA(tag, C_CN) ? Prec::Bot : Prec::Pi;
    auto ptrn = parse_ptrn({.brckt = true, .implicit = true}, prec, "domain of a {}", entity);
    auto dloc = Loc(domt);
 
    auto codom = ISA(tag, C_CN) ? nullptr
                                : (expect(Tag::T_arrow_r, entity), parse_expr(Prec::Arrow, "codomain of a {}", entity));
 
    // A `Fn`'s codomain is the type of its `return` continuation.
    auto fn = ISA(tag, C_FN);
    return ptr<PiExpr>(track, tag, ptr<PiExpr::Dom>(dloc, ptrn, fn ? codom : nullptr), fn ? nullptr : codom);
}
 
Ptr<Expr> Parser::parse_pi_expr(Ptr<Ptrn> ptrn) {
    auto track      = tracker(ptrn->loc());
    fe::Cite entity = "dependent function type";
    auto dom        = ptr<PiExpr::Dom>(ptrn->loc(), ptrn, nullptr);
    expect(Tag::T_arrow_r, entity);
    auto codom = parse_expr(Prec::Arrow, "codomain of a {}", entity);
    return ptr<PiExpr>(track, Tag::Nil, dom, codom);
}
 
Ptr<Expr> Parser::parse_lam_expr() { return ptr<LamExpr>(parse_lam_decl(tracker(), {})); }
 
Ptr<Expr> Parser::parse_ret_expr() {
    auto track = tracker();
    eat(Tag::K_ret);
    auto ptrn = parse_ptrn({}, "binding pattern of a ret expression");
    expect(Tag::T_assign, "ret expression");
    auto callee = parse_expr("continuation expression of a ret expression");
    expect(Tag::T_dollar, "separator of a ret expression");
    auto arg = parse_expr("argument of ret expression");
    expect(Tag::T_semicolon, "ret expression");
    auto body = parse_expr("body of a ret expression");
    return ptr<RetExpr>(track, ptrn, callee, arg, body);
}
 
/*
 * ptrns
 */
 
Ptr<Ptrn> Parser::parse_ptrn(PtrnStyle style, fe::Cite ctxt, Prec prec) {
    auto track = tracker();
    auto ptrn  = parse_ptrn_(style, ctxt, prec);
    if (accept(Tag::K_as)) return ptr<AliasPtrn>(track, ptrn, parse_id("alias pattern"));
    return ptrn;
}
 
Ptr<Ptrn> Parser::parse_ptrn_(PtrnStyle style, fe::Cite ctxt, Prec prec) {
    auto track = tracker();
 
    // p -> (p, ..., p)
    // p -> {p, ..., p}     b -> {b, ..., b}
    //                      b -> [b, ..., b]
    if (!style.brckt && ahead().isa(Tag::D_paren_l)) return parse_tuple_ptrn(style);
    if (style.implicit && ahead().isa(Tag::D_brace_l)) return parse_tuple_ptrn(style);
    if (style.brckt && ahead().isa(Tag::D_brckt_l)) return parse_tuple_ptrn(style);
 
    // p ->  s: e           b ->  s: e
    if (ahead(0).isa(Tag::M_id) && ahead(1).isa(Tag::T_colon)) {
        auto dbg = eat(Tag::M_id).dbg();
        eat(Tag::T_colon);
        auto type = parse_expr(ctxt, prec);
        return ptr<IdPtrn>(track, dbg, type);
    }
 
    if (!style.brckt) {
        // p ->  s
        if (auto id = accept(Tag::M_id)) return ptr<IdPtrn>(track, id.dbg(), nullptr);
        // p -> ↯
        syntax_err("pattern", ctxt);
        return ptr<ErrorPtrn>(missing());
    }
 
    //                      b -> e
    auto type = parse_expr(ctxt, prec);
    return anon_ptrn(Loc(track), type);
}
 
Ptr<TuplePtrn> Parser::parse_tuple_ptrn(PtrnStyle style) {
    auto track   = tracker();
    auto delim_l = ahead().tag();
 
    Ptrs<Ptrn> ptrns;
    parse_list("tuple pattern", delim_l, [&]() {
        auto track = tracker();
 
        if (ahead(0).isa(Tag::M_id) && ahead(1).isa(Tag::M_id)) {
            Dbgs dbgs;
            while (auto tok = accept(Tag::M_id))
                dbgs.emplace_back(tok.dbg());
 
            if (accept(Tag::T_colon)) { // identifier group: x y z: T
                auto type = parse_expr("type of an identifier group within a tuple pattern");
                auto id   = ptr<IdPtrn>(dbgs.front().loc() + type->loc().end, dbgs.front(), type);
 
                ptrns.emplace_back(id);
                for (auto dbg : dbgs | std::views::drop(1))
                    ptrns.emplace_back(ptr<GrpPtrn>(dbg, id.get()));
                return;
            }
 
            if (!style.brckt) { // `(x y)` is two binders short a `,`, never an application
                error().e(dbgs[1].loc(), "expected `,` or `:` between the binders of a tuple pattern");
                for (auto dbg : dbgs)
                    ptrns.emplace_back(ptr<IdPtrn>(dbg.loc(), dbg, nullptr));
                return;
            }
 
            // "x y z" is a curried app and maybe the prefix of a longer type expression
            Ptr<Expr> lhs = path_expr(dbgs.front());
            for (auto dbg : dbgs | std::views::drop(1)) {
                auto loc = lhs->loc() + dbg.loc();
                lhs      = ptr<AppExpr>(loc, lhs, path_expr(dbg));
            }
            auto app = parse_infix_expr(track, lhs, Prec::Bot, "element of a tuple pattern");
            auto loc = app->loc();
            ptrns.emplace_back(anon_ptrn(loc, app));
            return;
        }
 
        auto ptrn = parse_ptrn({.brckt = style.brckt}, "element of a tuple pattern");
 
        // A binder may turn out to be the prefix of an expr: `[[Nat, Nat] -> Nat]`, `[[Nat] Nat]`.
        if (style.brckt) {
            if (ahead().isa(Tag::T_arrow_r)) {
                auto loc = ptrn->loc();
                ptrn     = anon_ptrn(loc, parse_pi_expr(ptrn));
            } else if (auto expr = Ptrn::to_expr(ast(), ptrn)) {
                auto addr = expr.get();
                expr      = parse_infix_expr(track, expr, Prec::Bot, "element of a tuple pattern");
                if (expr.get() != addr) ptrn = anon_ptrn(expr->loc(), expr);
            }
        }
 
        ptrns.emplace_back(ptrn);
    });
 
    return ptr<TuplePtrn>(track, delim_l, ptrns);
}
 
/*
 * decls
 */
 
Mods Parser::parse_modifiers() {
    Mods mods;
    while (true) {
        // clang-format off
        switch (ahead().tag()) {
            case Tag::K_priv:
            case Tag::K_pub: {
                auto v = ahead().tag() == Tag::K_priv ? Vis::Priv : Vis::Pub;
                if (mods.vis) error().e(curr_, "visibility already specified");
                mods.vis = v;
                lex();
                continue;
            }
            case Tag::K_extern:
                if (mods.is_extern) error().e(curr_, "`extern` already specified");
                mods.is_extern = true;
                lex();
                continue;
            case Tag::K_anx:
                if (mods.is_anx) error().e(curr_, "`anx` already specified");
                mods.is_anx = true;
                lex();
                continue;
            default: return mods;
        }
        // clang-format on
    }
}
 
void Parser::check_no_extern(const Mods& mods, fe::Cite entity) {
    if (mods.is_extern) error().e(curr_, "`extern` is only meaningful on a function declaration, not a {}", entity);
}
 
Ptrs<ValDecl> Parser::parse_decls(Mods group) {
    Ptrs<ValDecl> decls;
    while (true) {
        auto track = tracker();
        auto own   = parse_modifiers();
        auto mods  = own.inherit(group);
        switch (ahead().tag()) {
            case Tag::T_semicolon: lex(); break; // eat up stray semicolons
            case Tag::K_axm: decls.emplace_back(parse_axm_decl(track, mods)); break;
            case Tag::K_let: decls.emplace_back(parse_let_decl(track, mods)); break;
            case Tag::K_mod: decls.emplace_back(parse_mod_decl(track, mods)); break;
            case Tag::K_nom: decls.emplace_back(parse_nom_decl(track, mods)); break;
            case Tag::K_use: decls.emplace_back(parse_use_decl(track, mods)); break;
            case Tag::K_mutual: decls.emplace_back(parse_mutual_decl(track, mods)); break;
            case Tag::K_rec: decls.emplace_back(parse_rec_decl(track, mods)); break;
            case Tag::C_LAM: decls.emplace_back(parse_lam_decl(track, mods)); break;
            case Tag::C_RULE: decls.emplace_back(parse_rule_decl(track, mods)); break;
            case Tag::C_IMPORT:
                if (auto i = parse_import_or_plugin(track, mods)) decls.emplace_back(i);
                break;
            case Tag::M_id:
                if (mods.is_anx) {
                    decls.emplace_back(parse_alias_decl(track, mods));
                    break;
                }
                [[fallthrough]];
            default:
                if (own.any()) error().e(curr_, "expected a declaration after a modifier");
                return decls;
        }
    }
}
 
std::tuple<Ptr<Expr>, Dbg, Tok, Tok> Parser::parse_axm_tail() {
    auto type = parse_type_ascr("type ascription of an axm");
    Dbg normalizer;
    Tok curry, trip;
    if (ahead(0).isa(Tag::T_comma) && ahead(1).isa(Tag::M_id)) {
        lex();
        normalizer = lex().dbg();
    }
    if (accept(Tag::T_comma)) {
        curry = expect(Tag::L_u, "curry counter for axm");
        if (accept(Tag::T_comma)) trip = expect(Tag::L_u, "trip count for axm");
    }
    return {type, normalizer, curry, trip};
}
 
Ptr<ValDecl> Parser::parse_axm_decl(Tracker track, Mods mods) {
    eat(Tag::K_axm);
 
    if (mods.is_extern) error().e(curr_, "`axm` is implicitly `anx`; cannot combine with `extern`");
    auto vis = mods.vis.value_or(Vis::Pub); // axm is always anx, so it always gets the pub nudge
 
    Dbg mod;
    Ptrs<AxmDecl::Name> names;
    bool is_family = ahead().isa(Tag::D_paren_l);
    if (!is_family) {
        auto dbg = parse_id("name of an axm");
        if (accept(Tag::T_dot)) {
            mod       = dbg;
            is_family = true;
        } else {
            names.emplace_back(ptr<AxmDecl::Name>(dbg.loc(), Dbgs{dbg}));
        }
    }
    if (is_family) names = parse_axm_names();
 
    auto [type, normalizer, curry, trip] = parse_axm_tail();
    auto members                         = mod ? &ast().scope() : nullptr;
    return ptr<AxmDecl>(track, vis, mod, members, is_family, type, normalizer, curry, trip, names);
}
 
Ptrs<AxmDecl::Name> Parser::parse_axm_names() {
    Ptrs<AxmDecl::Name> names;
    parse_list("tag list of an axm", Tag::D_paren_l, [&]() {
        Dbgs dbgs{parse_id("tag of an axm")};
        while (accept(Tag::T_assign))
            dbgs.emplace_back(parse_id("alias of an axm tag"));
        names.emplace_back(ptr<AxmDecl::Name>(dbgs.front().loc() + dbgs.back().loc(), dbgs));
    });
    return names;
}
 
Ptr<ValDecl> Parser::parse_alias_decl(Tracker track, Mods mods) {
    if (mods.is_extern) error().e(curr_, "`extern` and `anx` cannot be combined on an alias declaration");
    auto vis = mods.vis.value_or(Vis::Pub); // always anx, so always the pub nudge unless overridden
    auto dbg = parse_id("name of an alias declaration");
    expect(Tag::T_assign, "alias declaration");
    auto path = parse_path("target of an alias declaration");
    return ptr<AliasDecl>(track, vis, dbg, path);
}
 
Ptr<ValDecl> Parser::parse_let_decl(Tracker track, Mods mods) {
    check_no_extern(mods, "let declaration");
    eat(Tag::K_let);
    auto ptrn = parse_ptrn({}, "binding pattern of a let declaration", Prec::Bot);
    expect(Tag::T_assign, "let");
    auto value = parse_expr("value of a let declaration");
    return ptr<LetDecl>(track, mods, ptrn, value);
}
 
Ptr<ValDecl> Parser::parse_mod_decl(Tracker track, Mods mods) {
    // a mod is pure AST grouping, not a single value, so neither `extern` nor `anx` apply to it
    check_no_extern(mods, "module");
    if (mods.is_anx) error().e(curr_, "`anx` doesn't apply to a module - it groups declarations, not a single value");
    auto vis = mods.vis.value_or(Vis::Priv);
    eat(Tag::K_mod);
    auto dbg   = parse_id("name of a module");
    auto decls = parse_decls();
    expect(Tag::K_end, "end of a module");
    return ptr<ModDecl>(track, vis, dbg, ast().scope(), ast().copy(decls));
}
 
Ptr<ValDecl> Parser::parse_use_decl(Tracker track, Mods mods) {
    check_no_extern(mods, "use declaration");
    if (mods.is_anx) error().e(curr_, "`anx` doesn't apply to a use declaration - it never represents a single value");
    eat(Tag::K_use);
    auto path = parse_path("module of a use declaration");
    Dbg alias;
    // `use path;` is sugar for `use path as *;`
    if (accept(Tag::K_as) && !accept(Tag::T_star)) alias = parse_id("alias of a use declaration");
    expect(Tag::T_semicolon, "end of a use declaration");
    return ptr<UseDecl>(track, Mods{mods.vis.value_or(Vis::Priv)}, path, alias);
}
 
Ptr<RecDecl> Parser::parse_rec_decl(Tracker track, Mods mods) {
    check_no_extern(mods, "recursive declaration");
    eat(Tag::K_rec);
    auto dbg = parse_id("recursive declaration");
    expect(Tag::T_assign, "recursive declaration");
    auto body = parse_expr("body of a recursive declaration");
    return ptr<RecDecl>(track, mods, dbg, body);
}
 
Ptr<ValDecl> Parser::parse_mutual_decl(Tracker track, Mods mods) {
    eat(Tag::K_mutual);
    Ptrs<RecDecl> decls;
    for (auto decl : parse_decls(mods))
        if (auto rec = decl->isa<RecDecl>())
            decls.emplace_back(rec);
        else
            error().e(decl->loc(), "only `rec`, `nom`, `lam`, `con`, and `fun` declarations may be mutually recursive");
    expect(Tag::K_end, "end of a mutual block");
    return ptr<MutualDecl>(track, decls);
}
 
Ptr<RecDecl> Parser::parse_nom_decl(Tracker track, Mods mods) {
    check_no_extern(mods, "nominal type declaration");
    eat(Tag::K_nom);
    auto dbg = parse_id("nominal type declaration");
    if (accept(Tag::T_assign)) {
        auto body = parse_expr("underlying type of a nominal type declaration");
        return ptr<NomDecl>(track, mods, dbg, body);
    }
 
    // `nom I (dom)+ = e` is sugar for `lam I (dom)+ = nom I = e; I`; within `e`, `I` names the type constructor.
    Ptrs<LamDecl::Dom> doms;
    do {
        auto dom_track = tracker();
        auto ptrn      = parse_ptrn({.implicit = true}, Prec::Pi, "domain pattern of a nominal type declaration");
        doms.emplace_back(ptr<LamDecl::Dom>(dom_track, ptrn, nullptr, nullptr, nullptr));
    } while (ISA(ahead().tag(), C_CURRIED_P));
    expect(Tag::T_assign, "nominal type declaration");
    auto body  = parse_expr("underlying type of a nominal type declaration");
    auto nom   = ptr<NomDecl>(track, Mods{}, dbg, body);
    auto sugar = nom.get();
    auto decls = Ptrs<ValDecl>();
    decls.emplace_back(std::move(nom));
    auto inst = ptr<DeclExpr>(track, ptr<PathExpr>(ptr<Path>(dbg.loc(), Dbgs{dbg})), false, decls);
    return ptr<LamDecl>(track, mods, Tag::K_lam, dbg, nullptr, inst, sugar, doms);
}
 
Ptr<ValDecl> Parser::parse_rule_decl(Tracker track, Mods mods) {
    check_no_extern(mods, "rewrite rule");
    if (mods.is_anx) error().e(curr_, "`anx` doesn't apply to a rewrite rule");
    auto is_norm = lex().tag() == Tag::K_norm;
    auto dbg     = parse_id("rewrite rule");
    auto ptrn    = parse_ptrn({}, "meta variables in rewrite rule");
    expect(Tag::T_colon, "rewrite rule declaration");
    auto lhs   = parse_expr("rewrite pattern");
    auto guard = accept(Tag::K_when) ? parse_expr("rewrite guard") : ptr<PrimaryExpr>(missing(), Tag::K_tt);
    expect(Tag::T_fat_arrow, "rewrite rule declaration");
    auto rhs = parse_expr("rewrite result");
    return ptr<RuleDecl>(track, mods, dbg, ptrn, lhs, rhs, guard, is_norm);
}
 
Ptr<LamDecl> Parser::parse_lam_decl(Tracker track, Mods mods) {
    // unlike let/mod/rec, a function declaration is the one place `extern` currently makes sense
    if (mods.is_extern && mods.is_anx)
        error().e(curr_, "`extern` and `anx` cannot be combined on a function declaration");
    auto tag  = lex().tag();
    auto prec = ISA(tag, C_CN) ? Prec::Bot : Prec::Pi;
 
    bool decl;
    fe::Cite entity;
    // clang-format off
    switch (tag) {
        case Tag::T_lm:  decl = false; entity = "function expression";                break;
        case Tag::K_cn:  decl = false; entity = "continuation expression";            break;
        case Tag::K_fn:  decl = false; entity = "returning continuation expression";  break;
        case Tag::K_lam: decl = true ; entity = "function declaration";               break;
        case Tag::K_con: decl = true ; entity = "continuation declaration";           break;
        case Tag::K_fun: decl = true ; entity = "returning continuation declaration"; break;
        default: std::unreachable();
    }
    // clang-format on
 
    if (decl)
        if (auto late = parse_modifiers(); late.any()) {
            error().e(curr_, "modifiers must precede the keyword of a {}", entity);
            mods = late.inherit(mods);
        }
 
    auto dbg = decl ? parse_id(entity) : Dbg();
    // The last Dom is built after the codomain, which a `fn`/`fun` turns into its `return` type.
    Ptrs<LamDecl::Dom> doms;
    Loc loc;
    Ptr<Ptrn> ptrn;
    Ptr<Expr> filter;
    while (true) {
        auto track = tracker();
        // A domain spelled with brackets is a telescope; the check after the body rejects that where names must bind.
        auto style = ahead().isa(Tag::D_brckt_l) ? PtrnStyle{.brckt = true} : PtrnStyle{.implicit = true};
        ptrn       = parse_ptrn(style, prec, "domain pattern of a {}", entity);
        filter     = accept(Tag::T_at) ? parse_expr("filter") : nullptr;
        loc        = Loc(track);
 
        if (!ISA(ahead().tag(), C_CURRIED_P)) break;
        doms.emplace_back(ptr<LamDecl::Dom>(loc, ptrn, filter, nullptr, nullptr));
    }
 
    // The `: codom` slot ends at `=`, so it takes everything short of a `where`.
    auto codom = accept(Tag::T_colon) ? parse_expr(Prec(int(Prec::Where) + 1), "codomain of a {}", entity) : nullptr;
    Ptr<Expr> ret_type;
    Ptr<IdDecl> ret;
    if (ISA(tag, C_FN)) {
        ret_type = codom ? codom : ptr<HoleExpr>(missing());
        ret      = ptr<IdDecl>(Dbg(ret_type->loc(), ast().sym_return()));
        codom    = nullptr; // the `ret` continuation is where it went
    }
    doms.emplace_back(ptr<LamDecl::Dom>(loc, ptrn, filter, ret_type, ret));
 
    Ptr<Expr> body;
    if (decl && mods.is_extern && ahead().isa(Tag::T_semicolon)) {
        // forward declaration - the implementation lives in a native translation unit
    } else {
        expect(Tag::T_assign, "body of a {}", entity);
        body = parse_expr("body of a {}", entity);
 
        // Only a forward declaration may spell its domain as a telescope; with a body the names must actually bind.
        for (auto dom : doms)
            if (auto tuple = dom->ptrn()->isa<TuplePtrn>(); tuple && tuple->is_brckt())
                error()
                    .e(tuple->loc(), "a {} with a body must spell its domain as a `(...)` pattern", entity)
                    .n("`[...]` describes a type, so its names bind nothing here")
                    .n("write an unnamed component as `_: T`");
    }
 
    return ptr<LamDecl>(track, mods, tag, dbg, codom, body, nullptr, doms);
}
 
} // namespace mim::ast