resolve-lang 0.2.0

The model

• resolve resolves one unit with the default (lexical, Kraken-style) policy: the lazy path.
• A Policy is a language's scoping rules as data. Presets: kraken, php, python.
• A Resolver resolves one unit with a policy, an Env (names outside the program: other packages, the standard library, primitive types), and a Budget.
• A Program resolves several units against each other; a unit given a root name is reachable from every unit as name::item.
• The Resolution holds the resolved units, the **Diagnostic**s, and the Index.

What it guarantees, and how each guarantee is checked:

Installation

[dependencies]
resolve-lang = "0.2"
hir-lang = "0.3"
intern-lang = "1"

Without the standard library:

[dependencies]
resolve-lang = { version = "0.2", default-features = false }

Quick start

Build a unit with hir-lang's builder, resolve it, read the result:

use hir_lang::{Builder, Expr, Name, Res};
use intern_lang::Interner;

// fn length(n) { n }      fn main() { lenght }
let mut names = Interner::new();
let n = Name::new(names.intern("n"));
let mut b = Builder::new();
let (param, n_binder) = b.local_param(n);
let use_n = b.name_expr(n);
let body = b.block(&[], Some(use_n));
let length = b.func(Name::new(names.intern("length")), &[param], body);
let typo = b.name_expr(Name::new(names.intern("lenght")));
let main_body = b.block(&[], Some(typo));
let main = b.func(Name::new(names.intern("main")), &[], main_body);
let root = b.module(None, &[length, main]);
let hir = b.finish(root)?;
let unit = hir.unit();

let res = resolve_lang::resolve(hir, &names)?;
let hir = res.hir(unit).unwrap();
let Expr::Path(p) = *hir.expr(use_n) else { unreachable!() };
assert_eq!(hir.path(p).res, Res::Local(n_binder));
assert_eq!(
    res.diagnostics()[0].message(&names),
    "cannot find value `lenght` in this scope; did you mean `length`?",
);
# Ok::<(), Box<dyn std::error::Error>>(())

A language's policy and environment

use hir_lang::{Builder, Name, Ns, Prim, Res, Ty};
use intern_lang::Interner;
use resolve_lang::{DefKind, Export, MapEnv, Namespace, Policy, Resolver};

let mut names = Interner::new();
let int = Name::new(names.intern("int"));
// The host provides primitive type names.
let env = MapEnv::new().with_prelude(int, Namespace::Type, Export::new(Res::Prim(Prim::I64), DefKind::Prim));

// type Count = int
let mut b = Builder::new();
let path = b.name_path(int, Ns::Type);
let ty = b.ty(Ty::Path(path));
let alias = b.item(hir_lang::Item::new(
    Some(Name::new(names.intern("Count"))),
    hir_lang::ItemKind::Alias { generics: hir_lang::Generics::default(), ty },
));
let root = b.module(None, &[alias]);

let res = Resolver::new(Policy::python()).with_env(&env).resolve(b.finish(root)?, &names)?;
assert_eq!(res.units()[0].hir().path(path).res, Res::Prim(Prim::I64));
# Ok::<(), Box<dyn std::error::Error>>(())

Several units, and the index

use hir_lang::{Builder, FnDef, Item, ItemKind, Name, Ns, Path, Segment, UnitId, Vis};
use intern_lang::Interner;
use resolve_lang::{Policy, Program, Target};

let mut names = Interner::new();
let (util, helper) = (Name::new(names.intern("util")), Name::new(names.intern("helper")));

// Unit 1, reachable as `util`: pub fn helper() {}
let mut b = Builder::for_unit(UnitId::new(1));
let body = b.block(&[], None);
let f = b.item(Item::new(Some(helper), ItemKind::Fn(FnDef { body: Some(body), ..FnDef::default() })).with_vis(Vis::Public));
let root = b.module(None, &[f]);
let util_hir = b.finish(root)?;

// Unit 2: fn main() { util::helper }
let mut b = Builder::for_unit(UnitId::new(2));
let segs = [Segment::new(util, b.origin()), Segment::new(helper, b.origin())];
let segs = b.list(&segs);
let path = b.path(Path::new(segs, Ns::Value));
let call = b.expr(hir_lang::Expr::Path(path));
let body = b.block(&[], Some(call));
let main = b.func(Name::new(names.intern("main")), &[], body);
let root = b.module(None, &[main]);
let app_hir = b.finish(root)?;

let mut program = Program::new(Policy::kraken());
program.add_unit(Some(util), util_hir);
program.add_unit(None, app_hir);
let res = program.resolve(&names)?;
assert!(res.is_clean());

// Find references: `util::helper` is one reference to `helper`.
let index = res.index();
let def = index.def_of(Target::Def(hir_lang::DefId::foreign(UnitId::new(1), hir_lang::Def::Item(f)))).unwrap();
assert_eq!(index.references(def).len(), 1);
assert_eq!(index.resolve_at(UnitId::new(2), path, 1), Some(def));
# Ok::<(), Box<dyn std::error::Error>>(())

More in examples/: basic (the lazy path), multi_unit (two units importing each other), lsp (go-to-definition, references, rename, outline).

What resolution covers

• Binders through Hir::lookup_local and the walk's Bind/Scope/Frame events: the HIR's own scope rules, never re-derived. A local behind a frame it cannot cross (a nested function) is reported, not silently skipped.
• Items by namespace and hoisting: visible in their whole scope, from their declaration on, or (PHP) in their whole module wherever declared.
• Paths: a::b::c through modules, sum variants, and the environment's containers; partial resolution where the rest is type-directed (Vec::new, T::Item, <T as Tr>::Out); roots ::, self::, super::; self::/parent::/static:: early or late per policy.
• Imports: single, aliased, glob, re-exported, private, across units, in cycles; ambiguity between globs reported where the name is used.
• Patterns: a bare identifier pattern matches a constant, unit variant, or unit record of that name, and binds otherwise.
• Classes: member tables with mixin expansion (insteadof, as), inherited lookups, private and protected access.
• Diagnostics: unresolved names (with a suggestion within a small edit distance), ambiguous globs, private access, duplicates, uncapturable locals, wrong kinds, import cycles, mixin conflicts.

Performance

Measured with cargo bench --bench bench on a desktop x86_64 machine (Windows, release profile), resolution only (building the HIR is excluded):

These are library numbers: the time includes building the index and writing every resolution into the Hir.

Testing

cargo test --all-features
cargo clippy --all-targets --all-features -- -D warnings
cargo bench --bench bench

The property tests in tests/properties.rs and tests/import_graph.rs hold the resolver to independent references written in the tests. Every rust example in this README and in docs/API.md is compiled and run as a doctest.

Cross-platform support

• Linux (x86_64, aarch64)
• macOS (x86_64, Apple Silicon)
• Windows (x86_64)

The crate uses no operating-system facilities and no platform-specific code.

Contributing

See REPS.md for the engineering standards every change is held to, dev/DIRECTIVES.md for the definition of done, and dev/ROADMAP.md for the plan. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.