bind.cpp

Go to the documentation of this file.

#include <fe/restore.h>
 
#include "mim/ast/ast.h"
 
#include "family.h"
 
using namespace std::literals;
 
namespace mim::ast {
 
using Tag = Tok::Tag;
 
class DummyDecl : public Decl {
public:
    DummyDecl()
        : Decl(Loc()) {}
 
    void stream(fe::Tab&, std::ostream& os) const final { os << "<dummy>"; }
};
 
class Scopes {
public:
    Scopes(AST& ast)
        : ast_(ast)
        , dummy_(ast.ptr<DummyDecl>()) {
        push(); // root scope
    }
 
    AST& ast() const { return ast_; }
    Error& error() const { return ast().error(); }
    Scope& top() { return scopes_.back().scope(); }
    const Decl* dummy() const { return dummy_.get(); }
 
    void push() { scopes_.emplace_back(); }
    void push(Scope& scope) { scopes_.emplace_back(scope); }
 
    void pop() {
        assert(scopes_.size() > barrier_);
        scopes_.pop_back();
    }
 
    struct Barrier {
        size_t scopes, mods;
    };
 
    /// A file must not see the scope of whoever imports it, so its Scope becomes the new lookup floor.
    Barrier push_barrier(Scope& scope) {
        push(scope);
        return {std::exchange(barrier_, scopes_.size() - 1), std::exchange(mod_barrier_, mod_stack_.size())};
    }
 
    void pop_barrier(Barrier old) {
        barrier_     = old.scopes;
        mod_barrier_ = old.mods;
        pop();
    }
 
    /// @name Annex nesting
    /// Tracked by ModDecl::bind so AST::name2annex can derive `tag`/`sub` from lexical nesting.
    ///@{
    /// The top-level declaration being bound, if any; see NomDecl::rep_vis.
    const Decl* top_decl() const { return top_decl_; }
    auto enter_top_decl(const Decl* decl) { return fe::Restore(top_decl_, decl); }
 
    void push_mod(Sym name) { mod_stack_.emplace_back(name); }
    void pop_mod() { mod_stack_.pop_back(); }
    size_t mod_depth() const { return mod_stack_.size() - mod_barrier_; }
    Sym enclosing_mod() const { return mod_depth() == 0 ? Sym() : mod_stack_.back(); }
    ///@}
 
    const Decl* find(Dbg dbg, bool quiet = false) {
        // `_` never enters a Scope, so it cannot be planted as a dummy; the recorded error keeps emit from running.
        if (dbg.is_anon()) {
            if (!quiet) error().e(dbg.loc(), "`_` never binds an entity and cannot be referenced");
            return nullptr;
        }
 
        for (auto& frame : scopes_ | std::views::drop(barrier_) | std::views::reverse)
            if (auto bind = fe::lookup(frame.scope(), dbg.sym())) return bind->decl;
 
        if (!quiet) {
            auto& diag = error().e(dbg.loc(), "identifier `{}` not found", dbg.sym());
            // An infix operator only exists as whatever the user bound its escaped name to.
            if (dbg.sym().view().starts_with('`'))
                diag.n("an infix operator means whatever you bind its escaped name to");
            bind(dbg, dummy()); // put into scope to prevent further errors
        }
        return nullptr;
    }
 
    /// Diagnostic-only: is a module named @p sym reachable, shadowed by whatever `find` would actually return?
    /// Only a module - a ModDecl, an Import, or an AxmDecl family - yields a non-null Decl::scope.
    const Decl* find_shadowed_module(Sym sym) {
        for (auto& frame : scopes_ | std::views::drop(barrier_) | std::views::reverse)
            if (auto bind = fe::lookup(frame.scope(), sym); bind && bind->decl->scope()) return bind->decl;
        return nullptr;
    }
 
    void bind(Dbg dbg, const Decl* decl, bool rebind = false, bool quiet = false) {
        bind(dbg, decl, decl->vis(), rebind, quiet);
    }
 
    /// Binds @p decl under @p dbg with an explicit @p vis - a splice re-exports under its own visibility.
    void bind(Dbg dbg, const Decl* decl, Vis vis, bool rebind = false, bool quiet = false) {
        if (dbg.is_anon()) return;
 
        auto& scope = top();
        if (rebind) {
            scope[dbg.sym()] = Bind{decl, vis};
        } else if (auto [i, ins] = scope.try_emplace(dbg.sym(), Bind{decl, vis}); !ins) {
            auto prev = i->second.decl;
            if (!quiet && !prev->isa<DummyDecl>()) // if prev stems from an error - don't complain
                error().e(dbg.loc(), "redeclaration of `{}`", dbg).n(prev->dbg().loc(), "previous declaration here");
        } else if (!quiet && !decl->scope()) {
            if (auto mod = find_shadowed_module(dbg.sym()))
                error()
                    .w(dbg.loc(), "`{}` shadows a module of the same name", dbg)
                    .n(mod->dbg().loc(), "module declared here; a later `{}.member` would fail to resolve it",
                       dbg.sym());
        }
    }
 
private:
    /// Owns the Scope of an anonymous binder; a File's or ModDecl's Scope outlives Scopes and is borrowed.
    class Frame {
    public:
        Frame() = default;
        Frame(Scope& scope)
            : borrowed_(&scope) {}
 
        Scope& scope() { return borrowed_ ? *borrowed_ : own_; }
 
    private:
        Scope own_;
        Scope* borrowed_ = nullptr;
    };
 
    AST& ast_;
    Ptr<DummyDecl> dummy_;
    fe::Vector<Frame> scopes_;
    fe::Vector<Sym> mod_stack_;
    const Decl* top_decl_ = nullptr;
    size_t barrier_       = 0;
    size_t mod_barrier_   = 0;
};
 
/*
 * File
 */
 
void File::bind(AST& ast) const {
    auto scopes = Scopes(ast);
    bind(scopes);
}
 
void File::bind(Scopes& s) const {
    if (bound_) return;
    bound_ = true;
 
    auto barrier = s.push_barrier(members());
    for (auto import : implicit_imports())
        import->bind(s);
    bind_decls(s);
    s.pop_barrier(barrier);
}
 
/*
 * Ptrn
 */
 
void ErrorPtrn::bind(Scopes&, bool, bool) const {}
void GrpPtrn::bind(Scopes& s, bool rebind, bool quiet) const { s.bind(dbg(), this, rebind, quiet); }
 
void IdPtrn::bind(Scopes& s, bool rebind, bool quiet) const {
    if (!quiet && type()) type()->bind(s);
    s.bind(dbg(), this, rebind, quiet);
}
 
void IdDecl::bind(Scopes& s, bool quiet) const { s.bind(dbg(), this, false, quiet); }
 
void AliasPtrn::bind(Scopes& s, bool rebind, bool quiet) const {
    ptrn()->bind(s, rebind, quiet);
    s.bind(dbg(), this, rebind, quiet);
}
 
void TuplePtrn::bind(Scopes& s, bool rebind, bool quiet) const {
    for (auto ptrn : ptrns())
        ptrn->bind(s, rebind, quiet);
}
 
/*
 * Expr
 */
 
void Path::bind(Scopes& s, bool quiet) const {
    decl_     = s.find(front(), quiet);
    auto prev = front();
 
    for (auto dbg : dbgs() | std::views::drop(1)) {
        if (!decl_) return;
        auto scope  = decl_->scope();
        auto member = scope ? fe::lookup(*scope, dbg.sym()) : nullptr;
        if (!member) {
            if (!quiet && !decl_->isa<DummyDecl>()) {
                if (scope) {
                    s.error().e(dbg.loc(), "`{}` has no member `{}`", prev.sym(), dbg.sym());
                } else {
                    auto& err = s.error().e(prev.loc(), "`{}` is not a module", prev.sym());
                    if (auto mod = s.find_shadowed_module(prev.sym()))
                        err.n(mod->dbg().loc(), "a module `{}` exists here but is shadowed by the `{}` in scope",
                              prev.sym(), prev.sym());
                }
            }
            decl_ = nullptr;
            return;
        }
        decl_ = member->decl;
        prev  = dbg;
 
        // A dotted path always crosses into decl_'s enclosing mod from outside: `priv` blocks it.
        if (member->vis == Vis::Priv) {
            if (!quiet) s.error().e(dbg.loc(), "`{}` is private to its enclosing `mod`", dbg.sym());
            decl_ = nullptr;
            return;
        }
    }
}
 
// clang-format off
void PathExpr   ::bind(Scopes& s) const { path()->bind(s); }
void TypeExpr   ::bind(Scopes& s) const { level()->bind(s); }
void RuleExpr   ::bind(Scopes& s) const { dom()->bind(s); }
void ErrorExpr  ::bind(Scopes&) const {}
void HoleExpr   ::bind(Scopes&) const {}
void PrimaryExpr::bind(Scopes&) const {}
// clang-format on
 
void LitExpr::bind(Scopes& s) const {
    if (type()) {
        type()->bind(s);
        if (ISA(tag(), C_LIT_TYPED)) s.error().e(type()->loc(), "a `{}` must not have a type annotation", tag());
    } else if (tag() == Tag::L_f) {
        s.error().e(loc(), "floating-point literal requires a type annotation");
    }
}
 
void DeclExpr::bind(Scopes& s) const {
    if (is_where())
        for (auto decl : decls() | std::views::reverse)
            decl->bind(s);
    else
        for (auto decl : decls())
            decl->bind(s);
    expr()->bind(s);
}
 
void PrefixExpr::bind(Scopes& s) const { rhs()->bind(s); }
 
void InfixExpr::bind(Scopes& s) const {
    if (callee()) callee()->bind(s);
    lhs()->bind(s);
    // `t#x` may name a field of `t`'s Sigma rather than anything in scope; InfixExpr::emit_ resolves that.
    if (auto path = op().isa(Tag::T_extract) ? rhs()->isa<PathExpr>() : nullptr)
        path->path()->bind(s, true);
    else
        rhs()->bind(s);
}
 
void MatchExpr::Arm::bind(Scopes& s) const {
    s.push();
    if (ptrn()) ptrn()->bind(s, false, false);
    body()->bind(s);
    s.pop();
}
 
void VariantExpr::bind(Scopes& s) const {
    for (auto ctor : ctors())
        if (ctor->type()) ctor->type()->bind(s);
}
 
void MatchExpr::bind(Scopes& s) const {
    scrutinee()->bind(s);
    for (auto arm : arms())
        arm->bind(s);
}
 
void PiExpr::Dom::bind(Scopes& s, bool quiet) const {
    ptrn()->bind(s, false, quiet);
    if (ret_type() && !quiet) ret_type()->bind(s);
}
 
void PiExpr::bind(Scopes& s) const {
    s.push();
    dom()->bind(s);
    if (codom()) codom()->bind(s);
    s.pop();
}
 
void LamExpr::bind(Scopes& s) const {
    lam()->bind_decl(s);
    lam()->bind_body(s);
}
 
void AppExpr::bind(Scopes& s) const {
    callee()->bind(s);
    arg()->bind(s);
}
 
void RetExpr::bind(Scopes& s) const {
    callee()->bind(s);
    arg()->bind(s);
    s.push();
    ptrn()->bind(s, true, false);
    body()->bind(s);
    s.pop();
}
 
void SigmaExpr::bind(Scopes& s) const {
    s.push();
    ptrn()->bind(s, false, false);
    s.pop();
}
 
void TupleExpr::bind(Scopes& s) const {
    for (auto elem : elems())
        elem->bind(s);
}
 
void SeqExpr::bind(Scopes& s) const {
    s.push();
    shape()->bind(s);
    index()->bind(s);
    body()->bind(s);
    s.pop();
}
 
void SingleExpr::bind(Scopes& s) const { body()->bind(s); }
 
/*
 * Decl
 */
 
static Sym loc2plugin(AST& ast, Loc loc) {
    return loc.src ? ast.sym(fs::path(loc.src->path()).stem().string()) : ast.sym_error();
}
 
/// Records the constructor or field names that @p type - the body of an annex declaration - spells out.
static void add_names(AnnexInfo& annex, const Expr* type) {
    if (auto variant = type->isa<VariantExpr>()) {
        annex.names  = fe::Vector<Sym>(variant->ctors(), [](const auto& ctor) { return ctor->dbg().sym(); });
        annex.fields = false;
    } else if (auto sigma = type->isa<SigmaExpr>()) {
        auto tuple   = sigma->ptrn();
        annex.names  = fe::Vector<Sym>(tuple->num_ptrns(), [tuple](size_t i) { return tuple->field(i); });
        annex.fields = true;
    }
}
 
AnnexInfo* AST::name2annex(Scopes& s, Dbg dbg, sub_t* sub_id, const Expr* type) {
    if (!dbg) return nullptr;
 
    auto depth = s.mod_depth();
    if (depth > 1) {
        error().e(dbg.loc(), "`{}` sits {} `mod` levels deep; an `anx` declaration may nest at most one", dbg, depth);
        return nullptr;
    }
 
    auto plugin_s = loc2plugin(*this, dbg.loc());
    auto tag_s    = depth == 0 ? dbg.sym() : s.enclosing_mod();
    Sym sub_s     = depth == 0 ? Sym() : dbg.sym();
 
    auto& sym2annex = plugin2sym2annex_[plugin_s];
    auto tag_id     = sym2annex.size();
 
    if (plugin_s == sym_error()) error().e(dbg.loc(), "plugin name `{}` is reserved", dbg);
    if (tag_id > std::numeric_limits<tag_t>::max())
        error().e(dbg.loc(), "exceeded maximum number of annexes in current plugin");
 
    if (!Annex::mangle(plugin_s)) {
        error().e(dbg.loc(), "invalid annex name `{}`", dbg);
        plugin_s = sym_error();
    }
 
    auto [i, fresh] = sym2annex.try_emplace(tag_s, AnnexInfo{plugin_s, tag_s, (tag_t)tag_id});
    auto annex      = &i->second;
 
    if (sub_s) {
        if (sub_id) {
            *sub_id       = annex->subs.size();
            auto& aliases = annex->subs.emplace_back();
            aliases.emplace_back(sub_s);
        } else {
            error().e(dbg.loc(), "annex `{}` must not have a subtag", dbg);
        }
    }
 
    if (!fresh) annex->fresh = false;
    if (type) add_names(*annex, type);
    return annex;
}
 
/// Registers @p alias as a further name of the annex slot @p target introduced.
static void add_alias(AnnexInfo* annex, sub_t sub, Sym target, Sym alias) {
    // An ungrouped target (the common case) never allocated its own sub-group; seed one now,
    // named after the target itself, so this alias has a slot to share.
    if (sub >= annex->subs.size()) {
        assert(sub == annex->subs.size());
        annex->subs.emplace_back(fe::Vector<Sym>{target});
    }
    annex->subs[sub].emplace_back(alias);
}
 
void AxmDecl::bind(Scopes& s) const {
    type()->bind(s);
    auto pi = type()->isa<PiExpr>() || InfixExpr::isa_op(Tag::T_arrow_r, type());
 
    if (members_) {
        s.push(*members_);
        s.push_mod(mod_.sym());
    }
 
    for (auto name : names()) {
        auto dbg    = name->dbg();
        auto& annex = name->annex_ = s.ast().name2annex(s, dbg, &name->sub_);
 
        if (annex && annex->fresh) {
            annex->normalizer = normalizer();
            annex->pi         = pi;
        } else if (annex) {
            if (annex->pi != pi)
                s.error().e(dbg.loc(),
                            "all declarations of annex `{}` must be function types if one of them is (they share one "
                            "annex tag - via mod-nesting or a `tag.(...)` family - and must agree in shape)",
                            dbg.sym());
 
            if (annex->normalizer.sym() != normalizer().sym()) {
                auto l    = normalizer().loc() ? normalizer().loc() : loc().anew_end();
                auto& err = s.error().e(l, "normalizer mismatch for axm `{}`", dbg);
                if (auto norm = annex->normalizer)
                    err.n(norm.loc(), "previous normalizer `{}` declared here", norm);
                else
                    err.n("initially no normalizer was specified");
            }
        }
 
        s.bind(dbg, name.get(), vis());
        for (auto alias : name->aliases()) {
            s.bind(alias, name.get(), vis());
            if (annex) add_alias(annex, name->sub_, dbg.sym(), alias.sym());
        }
    }
 
    if (members_) {
        s.pop_mod();
        s.pop();
        // The family is reachable as a module whatever the visibility of its axioms.
        s.bind(mod_, this, Vis::Pub);
    }
}
 
void AliasDecl::bind(Scopes& s) const {
    path()->bind(s);
    s.bind(dbg(), this);
 
    auto target = path()->decl();
    if (!target) return;
 
    if (target->isa<AliasDecl>()) {
        s.error().e(loc(), "`{}` aliases `{}`, which is itself an alias; alias chains are not supported", dbg(),
                    path()->back());
        return;
    }
 
    std::tie(annex_, sub_) = target->annex_sub();
    if (!annex_) {
        s.error().e(loc(), "`{}` must alias a compiler-exposed (`anx`) declaration", dbg());
        return;
    }
 
    auto& ast = s.ast();
    if (auto plugin = loc2plugin(ast, dbg().loc());
        plugin != ast.sym_error() && plugin != annex_->sym.plugin && s.mod_depth() == 0) {
        foreign_ = ast.sym(plugin.str() + "." + dbg().sym().str());
        ast.add_foreign_alias(plugin, {dbg().sym(), annex_, sub_});
        return;
    }
 
    add_alias(annex_, sub_, target->dbg().sym(), dbg().sym());
}
 
void LetDecl::bind(Scopes& s) const {
    s.push();
    value()->bind(s);
    s.pop();
 
    auto id = ptrn()->isa<IdPtrn>();
    // Scopes::bind snapshots Decl::vis, so mirror it onto the Ptrn *before* the Ptrn enters a Scope.
    if (id) {
        id->vis_ = vis();
        id->anx_ = is_anx();
    }
    ptrn()->bind(s, true, false);
    if (id && is_anx()) id->annex_ = s.ast().name2annex(s, id->dbg(), &id->sub_, value());
}
 
void RecDecl::bind(Scopes& s) const {
    bind_decl(s);
    bind_body(s);
}
 
void MutualDecl::bind(Scopes& s) const {
    // Only a top-level `mutual` makes its members top-level.
    auto is_top = s.top_decl() == this;
    for (auto decl : decls()) {
        auto _ = s.enter_top_decl(is_top ? decl.get() : s.top_decl());
        decl->bind_decl(s);
    }
    for (auto decl : decls()) {
        auto _ = s.enter_top_decl(is_top ? decl.get() : s.top_decl());
        decl->bind_body(s);
    }
}
 
bool RecDecl::has_mut_body() const {
    return body()->isa<PiExpr>() || InfixExpr::isa_op(Tag::T_arrow_r, body()) || body()->isa<SigmaExpr>()
        || body()->isa<VariantExpr>();
}
 
void RecDecl::bind_decl(Scopes& s) const {
    // A `nom` over any other body is merely not recursive.
    if (!isa<NomDecl>() && !has_mut_body())
        s.error()
            .e(body()->loc(), "unsupported expression in a recursive declaration")
            .n("must be a sigma, a variant, or a function type; use `lam`/`con`/`fun` to declare a recursive function");
 
    s.bind(dbg(), this);
    if (is_anx()) annex_ = s.ast().name2annex(s, dbg(), &sub_, body());
}
 
void RecDecl::bind_body(Scopes& s) const { body()->bind(s); }
 
void NomDecl::bind_body(Scopes& s) const {
    rep_vis_ = s.top_decl() ? s.top_decl()->vis() : Vis::Pub;
    RecDecl::bind_body(s);
}
 
void LamDecl::Dom::bind(Scopes& s, bool quiet) const {
    PiExpr::Dom::bind(s, quiet);
    if (ret()) ret()->bind(s, quiet);
    if (filter() && !quiet) filter()->bind(s);
}
 
void LamDecl::bind_decl(Scopes& s) const {
    s.push();
    for (auto&& dom : doms())
        dom->bind(s);
 
    if (auto filter = doms().back()->filter()) {
        if (auto pe = filter->isa<PrimaryExpr>()) {
            if (pe->tag() == Tag::K_tt && ISA(tag(), C_DS))
                s.error().w(filter->loc(),
                            "`tt`-filter superfluous as the last curried function group of a `{}` receives a "
                            "`tt`-filter by default",
                            tag());
            if (pe->tag() == Tag::K_ff && !ISA(tag(), C_DS))
                s.error().w(filter->loc(),
                            "`ff`-filter superfluous as the last curried function group of a `{}` receives a "
                            "`ff`-filter by default",
                            tag());
        }
    }
 
    if (codom()) {
        if (ISA(tag(), C_CN)) s.error().e(codom()->loc(), "a continuation must not have a codomain");
        codom()->bind(s);
    }
 
    s.pop();
    s.bind(dbg(), this);
    if (is_anx()) annex_ = s.ast().name2annex(s, dbg(), &sub_, nom_sugar() ? nom_sugar()->body() : nullptr);
}
 
void LamDecl::bind_body(Scopes& s) const {
    s.push();
    for (auto dom : doms())
        dom->bind(s, true);
    if (auto nom = nom_sugar())
        nom->bind_body(s);
    else if (body())
        body()->bind(s);
    s.pop();
}
 
void ModDecl::bind_decls(Scopes& s) const {
    for (auto decl : decls()) {
        auto _ = s.enter_top_decl(decl.get());
        decl->bind(s);
    }
}
 
void ModDecl::bind(Scopes& s) const {
    s.push(members());
    s.push_mod(dbg().sym());
    bind_decls(s);
    s.pop_mod();
    s.pop();
    s.bind(dbg(), this);
}
 
const Scope* UseDecl::module(Scopes& s) const {
    if (is_import()) {
        if (!file()) return nullptr;
        file()->bind(s);
        return file()->scope();
    }
 
    path()->bind(s);
    auto decl = path()->decl();
    if (!decl) return nullptr;
 
    auto scope = decl->scope();
    if (!scope) s.error().e(path()->loc(), "`{}` is not a module", path()->back().sym());
    return scope;
}
 
void UseDecl::bind(Scopes& s) const {
    auto mod = module(s);
    if (!mod) return;
 
    if (is_splice()) {
        // Quiet: a name already bound here wins, so a splice never shadows and never conflicts.
        for (const auto& [sym, binding] : *mod)
            if (binding.vis == Vis::Pub) s.bind(Dbg(loc(), sym), binding.decl, vis(), false, true);
        return;
    }
 
    // The same file may be imported more than once - as `-p foo` plus a `plugin foo;` directive, say.
    if (file())
        if (auto prev = s.find(dbg(), true))
            if (auto use = prev->isa<UseDecl>(); use && use->file() == file()) return;
 
    scope_ = mod;
    s.bind(dbg(), this);
}
 
void RuleDecl::bind(Scopes& s) const {
    s.push();
    var()->bind(s, true, false);
    lhs()->bind(s);
    rhs()->bind(s);
    guard()->bind(s);
    s.pop();
    s.bind(dbg(), this);
}
 
} // namespace mim::ast