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();
    if (tag == Tag::K_plugin && !driver().is_loaded(name) && !driver().flags().bootstrap) driver().load(name);
 
    auto filename = fs::path(name.view());
    driver().log().v("📥 import `{}`", name);
 
    if (!filename.has_extension()) filename.replace_extension("mim"); // TODO error cases
 
    fs::path rel_path;
    auto is_file = [](const fs::path& p) {
        std::error_code ignore;
        bool reg_file = fs::is_regular_file(p, ignore);
        return reg_file && !ignore;
    };
 
    // A path is relative to the importing file first; a bare name is only ever looked up in the search paths.
    if (is_path && !filename.is_absolute()) {
        rel_path = curr_dir() / filename;
        if (!is_file(rel_path)) rel_path.clear();
    }
 
    // A plugin's two halves must be the pair that shipped together, so take the `.mim` from the library's directory.
    if (rel_path.empty() && !is_path && tag == Tag::K_plugin) {
        if (auto dir = driver().plugin_dir(name.view())) {
            rel_path = *dir / filename;
            if (!is_file(rel_path)) rel_path = *dir / name.view() / filename;
            if (!is_file(rel_path)) rel_path.clear();
        }
    }
 
    if (rel_path.empty()) {
        for (const auto& path : driver().import_paths()) {
            rel_path = path / filename;
            if (is_file(rel_path)) break;
            if (is_path) continue; // `some/dir/foo.mim` must not also be probed as `some/dir/foo.mim/foo.mim`
            rel_path = path / name.view() / filename;
            if (is_file(rel_path)) break;
        }
    }
 
    auto [src, _] = driver().src().add(rel_path);
    if (!src) {
        // rel_path is whatever candidate the search loop tried last, so it only names a real file here.
        if (fs::exists(rel_path))
            error().e(dbg.loc(), "cannot read file `{}`", rel_path.string());
        else
            error().e(dbg.loc(), "cannot find `{}` in the search paths", name);
        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));
        if (auto file = import(dbg, false, 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 (tag == Tag::K_import && ahead().isa(Tag::L_str)) {
        name      = lex().dbg();
        file_path = name.sym();
    } else {
        // Only `plugin` needs a bare name: it is also the key for the shared object and the annex prefix.
        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);
    if (!ctxt) return nullptr;
    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::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_uniq_expr() {
    auto track = tracker();
    expect(Tag::D_curly_l, "opening curly bracket for singleton type");
    auto _          = this->anchor(Tag::D_curly_r);
    auto inhabitant = parse_expr("singleton type");
    recover("singleton type");
    expect(Tag::D_curly_r, "closing curly bracket for singleton type");
    return ptr<UniqExpr>(track, inhabitant);
}
 
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 ptrn  = parse_ptrn({}, "right-hand side of a match-arm", Prec::Bot);
        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, ptrn, body));
    } while (accept(Tag::T_pipe));
 
    return ptr<MatchExpr>(track, scrutinee, arms);
}
 
Ptr<Expr> Parser::parse_primary_expr(fe::Cite ctxt) {
    // 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_expr();
        case Tag::K_ret:     return parse_ret_expr();
        case Tag::D_curly_l: return parse_uniq_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();
        default:
            if (!ctxt) return nullptr;
            syntax_err("primary expression", ctxt);
    }
    // clang-format on
    return ptr<ErrorExpr>(missing());
}
 
Ptr<Expr> Parser::parse_seq_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;
    eat(delim_l);
    auto _ = this->anchor(Tok::delim_l2r(delim_l));
 
    Ptrs<IdPtrn> arities;
 
    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(fe::Cite(is_pack ? "shape of pack" : "shape of a array"));
        arities.emplace_back(IdPtrn::make_id(ast(), dbg, expr));
    } while (accept(Tag::T_comma));
 
    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(Tok::delim_l2r(delim_l),
           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& ptrn : arities | std::views::reverse) {
        auto loc = &ptrn == &arities.front() ? Loc(track) : ptrn->loc() + curr_;
        body     = ptr<SeqExpr>(loc, is_pack, ptrn, 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_s:
        case Tag::L_u: return {tok.loc(), -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: fe::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::C_CURRIED_B:
        case Tag::T_arrow_r: return parse_pi_expr(ptrn); // TODO precedences for patterns
        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 dom  = ptr<PiExpr::Dom>(domt, ptrn);
 
    auto codom = ISA(tag, C_CN) ? nullptr
                                : (expect(Tag::T_arrow_r, entity), parse_expr(Prec::Arrow, "codomain of a {}", entity));
 
    if (ISA(tag, C_FN)) {
        dom->add_ret(ast(), codom ? codom : ptr<HoleExpr>(missing()));
        codom = nullptr; // the `ret` continuation is where it went
    }
    return ptr<PiExpr>(track, tag, dom, 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);
    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 dbg  = dbgs.back();
                auto type = parse_expr("type of an identifier group within a tuple pattern");
                auto id   = ptr<IdPtrn>(dbg.loc() + type->loc().end, dbg, type);
 
                for (auto dbg : dbgs | std::views::take(dbgs.size() - 1))
                    ptrns.emplace_back(ptr<GrpPtrn>(dbg, id.get()));
                ptrns.emplace_back(id);
                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() {
    Ptrs<ValDecl> decls;
    while (true) {
        auto track = tracker();
        auto mods  = parse_modifiers();
        switch (ahead().tag()) {
            case Tag::T_semicolon: lex(); break; // eat up stray semicolons
            case Tag::K_axm: parse_axm_decl(track, mods, decls); 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_use: decls.emplace_back(parse_use_decl(track, mods)); break;
            case Tag::K_rec: decls.emplace_back(parse_rec_decl(track, true, 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()); 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 (mods.vis || mods.is_extern || mods.is_anx)
                    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)) {
        if (auto c = expect(Tag::L_u, "curry counter for axm")) curry = c;
        if (accept(Tag::T_comma)) {
            if (auto t = expect(Tag::L_u, "trip count for axm")) trip = t;
        }
    }
    return {type, normalizer, curry, trip};
}
 
void Parser::parse_axm_decl(Tracker track, Mods mods, Ptrs<ValDecl>& decls) {
    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
 
    if (ahead().isa(Tag::D_paren_l)) {
        for (auto decl : parse_axm_group(vis))
            decls.emplace_back(decl);
        return;
    }
 
    auto dbg = parse_id("name of an axm");
    if (accept(Tag::T_dot)) {
        auto group = parse_axm_group(vis);
        decls.emplace_back(ptr<ModDecl>(track, Vis::Pub, dbg, ast().scope(), ast().copy(group)));
        return;
    }
 
    auto [type, normalizer, curry, trip] = parse_axm_tail();
    decls.emplace_back(ptr<AxmDecl>(track, vis, dbg, type, normalizer, curry, trip));
}
 
Ptrs<ValDecl> Parser::parse_axm_group(Vis vis) {
    fe::Vector<Dbgs> members;
    parse_list("tag list of an axm", Tag::D_paren_l, [&]() {
        Dbgs names;
        names.emplace_back(parse_id("tag of an axm"));
        while (accept(Tag::T_assign))
            names.emplace_back(parse_id("alias of an axm tag"));
        members.emplace_back(std::move(names));
    });
 
    auto [type, normalizer, curry, trip] = parse_axm_tail();
 
    Ptrs<ValDecl> decls;
    const AxmDecl* owner = nullptr;
    for (auto& names : members) {
        auto primary = names.front();
        if (!owner) {
            auto axm = ptr<AxmDecl>(primary.loc(), vis, primary, type, normalizer, curry, trip);
            owner    = axm.get();
            decls.emplace_back(axm);
        } else {
            decls.emplace_back(ptr<AxmDecl::Sibling>(primary.loc(), vis, primary, owner));
        }
        for (auto alias : names | std::views::drop(1))
            decls.emplace_back(ptr<AliasDecl>(alias.loc(), Vis::Pub, alias, path(primary)));
    }
    return decls;
}
 
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");
    parse_type_ascr();
    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
    if (mods.is_extern) error().e(curr_, "`extern` is only meaningful on a function declaration, not a 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");
    expect(Tag::D_brace_l, "opening brace of a module");
    auto _     = this->anchor(Tag::D_brace_r);
    auto decls = parse_decls();
    recover("module");
    expect(Tag::D_brace_r, "closing brace 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, bool first, Mods mods) {
    check_no_extern(mods, "recursive declaration");
    eat(first ? Tag::K_rec : Tag::K_and);
    auto dbg = parse_id("recursive declaration");
    expect(Tag::T_assign, "recursive declaration");
    auto body = parse_expr("body of a recursive declaration");
    auto next = ahead().isa(Tag::K_and) ? parse_and_decl() : nullptr;
    return ptr<RecDecl>(track, mods, dbg, body, next);
}
 
Ptr<ValDecl> Parser::parse_rule_decl() {
    auto track   = tracker();
    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 = ahead().isa(Tag::K_when) ? (eat(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, 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: fe::unreachable();
    }
    // clang-format on
 
    auto dbg = decl ? parse_id(entity) : Dbg();
    Ptrs<LamDecl::Dom> doms;
    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};
        auto ptrn   = parse_ptrn(style, prec, "domain pattern of a {}", entity);
        auto filter = accept(Tag::T_at) ? parse_expr("filter") : nullptr;
        doms.emplace_back(ptr<LamDecl::Dom>(track, ptrn, filter));
 
        if (!ISA(ahead().tag(), C_CURRIED_P)) break;
    }
 
    // 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;
    if (ISA(tag, C_FN)) {
        doms.back()->add_ret(ast(), codom ? codom : ptr<HoleExpr>(missing()));
        codom = nullptr; // the `ret` continuation is where it went
    }
 
    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`");
    }
    auto next = ahead().isa(Tag::K_and) ? parse_and_decl() : nullptr;
 
    return ptr<LamDecl>(track, mods, tag, dbg, codom, body, next, doms);
}
 
Ptr<RecDecl> Parser::parse_and_decl() {
    if (ISA(ahead(1).tag(), C_LAM)) {
        lex();
        auto track = tracker();
        return parse_lam_decl(track, {});
    }
    return parse_rec_decl(tracker(), false, {});
}
 
} // namespace mim::ast