resolve-lang 0.4.1

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.4"
hir-lang = "0.4"
intern-lang = "1"

Without the standard library:

[dependencies]
resolve-lang = { version = "0.4", 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>>(())

PHP's tables and Python's MRO

use hir_lang::{Builder, Expr, Name};
use intern_lang::Interner;
use resolve_lang::{Policy, Resolver};

// function strLen() {}   const config = 1;   function config() {}
// function main() { STRLEN(); config(); config; }
let mut names = Interner::new();
let mut b = Builder::new();
let body = b.block(&[], None);
let strlen = b.func(Name::new(names.intern("strLen")), &[], body);
let one = b.int(1);
let config = Name::new(names.intern("config"));
let k = b.item(hir_lang::Item::new(Some(config), hir_lang::ItemKind::Const { ty: None, value: Some(one) }));
let body = b.block(&[], None);
let f = b.func(config, &[], body);
let c1 = b.name_expr(Name::new(names.intern("STRLEN")));
let call1 = b.call(c1, &[]);
let c2 = b.name_expr(config);
let call2 = b.call(c2, &[]);
let value = b.name_expr(config);
let list = b.list(&[call1, call2, value]);
let t = b.expr(Expr::Tuple(list));
let main_body = b.block(&[], Some(t));
let main = b.func(Name::new(names.intern("main")), &[], main_body);
let root = b.module(None, &[strlen, k, f, main]);
let hir = b.finish(root)?;
let unit = hir.unit();

let res = Resolver::new(Policy::php()).resolve(hir, &names)?;
// No duplicate (a function and a constant may share a name), nothing unresolved.
assert!(res.is_clean());
let hir = res.hir(unit).unwrap();
let target = |e| match *hir.expr(e) { Expr::Call { callee, .. } => callee, _ => e };
let res_of = |e| match *hir.expr(target(e)) { Expr::Path(p) => hir.path(p).res, _ => unreachable!() };
assert_eq!(res_of(call1), hir_lang::Res::Def(hir.def(hir_lang::Def::Item(strlen))));
assert_eq!(res_of(call2), hir_lang::Res::Def(hir.def(hir_lang::Def::Item(f))));
assert_eq!(res_of(value), hir_lang::Res::Def(hir.def(hir_lang::Def::Item(k))));
# Ok::<(), Box<dyn std::error::Error>>(())

Under Policy::python(), a class C(A, B) looks members up in C3 order (C, A, B, …), and a hierarchy with no consistent order is reported, as Python raises TypeError; see the php_python example.

More in examples/: basic (the lazy path), multi_unit (two units importing each other), lsp (go-to-definition, references, rename, outline), php_python (PHP's tables and case folding, Python's C3 order).

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.
• Case folding per table: PHP 8's ASCII rule for functions, methods, classes, and namespaces, through every lookup; names stay as written in diagnostics and the index, and a rename covers every case variant.
• Constants apart from functions (PHP): a call's callee searches functions first, any other value constants first, so a method and a class constant may share a name.
• 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.
• HIR 0.4 forms: a let_place alias is visible in its body only and crosses no frame (a closure naming it is reported), while its place's operands resolve outside it; a template's alias carries its mark, so user names never reach it. Keyed yield and yield from operands, and every type path in a union or intersection, resolve like any other; union members hir-lang's normalization dropped are left alone.
• 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, matched case-insensitively under PHP), inherited lookups in C3 order (Python's MRO), private and protected access; under lexical class scoping, unqualified names see inherited members before enclosing scopes.
• Diagnostics: unresolved names (with a suggestion within a small edit distance), ambiguous globs, private access, duplicates, uncapturable locals, wrong kinds, import cycles, mixin conflicts, inconsistent method resolution orders.

Performance

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

| Generator functions with four let_place aliases each, keyed yield, yield from, and union-typed parameters (hir-lang 0.4 forms) | 192,000 nodes | 31 ms |

These are library numbers: the time includes building the index and writing every resolution into the Hir. The rows above the last were measured for 0.3.0; for 0.4.0 the 0.3.0 and 0.4.0 crates were run back to back on the same machine under the same load (124k- and 1.24M-node units, eight units, index queries), and 0.4.0 was within noise or faster on each. The last row was measured on a loaded machine, so it is an upper bound.

Testing

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

The property tests in tests/properties.rs, tests/import_graph.rs, tests/import_corner.rs, tests/case_fold.rs, and tests/inheritance.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.