Name resolution

Deep dive

How it works

In: an AST walked in source order, with declarations and uses · Out: every use bound to a DefId or reported unresolved, plus a captured flag per definition · State: visible (name to stack of DefId) and an undo log, alive for one pass · Cost: O(n) time, about 23 ns per use measured below

1. Walk the AST in source order. Keep visible: name -> stack of DefId and an undo log of declared names; a scope is a mark in the log.
2. Enter scope: remember undo.len(). Exit: pop the log back to the mark and pop each name's stack, so the shadowed outer definition becomes visible again.
3. Declare: allocate a DefId, push it on the name's stack, append the name to the log.
4. Use: top of the name's stack is the binding; empty or missing means an unresolved-name error. Record (occurrence, DefId).
5. let x = init: resolve init first, then declare x. So let x = x + 1 reads the outer x, and a use before the let does not see it.
6. Items (fn) in a block are hoisted: declare all of them first, then resolve bodies, which allows mutual recursion and use before the text position.
7. Functions bump a fn_level. A use whose definition has a smaller level is a capture: mark the definition captured (this is what closures and upvalues later need).

fn even(n) { odd(n) }    pass 1 declares even, odd (hoisted)
fn odd(n)  { even(n) }   pass 2 resolves bodies: both calls bind
let k = 3                k declared after its initializer
(a) => a + k             a: level 1, same function; k: level 0 < 1, so captured

Code

use std::collections::HashMap;

pub enum Expr {
    Num(i64),
    Name(String),
    Add(Box<Expr>, Box<Expr>),
    Call(Box<Expr>, Vec<Expr>),
    Lambda(Vec<String>, Box<Expr>),
    Block(Vec<Stmt>, Box<Expr>), // statements, then the value expression
}
pub enum Stmt {
    Let(String, Expr),                // sequential: visible only AFTER its initializer
    Fn(String, Vec<String>, Expr),    // item: visible in the whole block (hoisted)
}

pub type DefId = u32;
#[derive(Debug, PartialEq, Clone, Copy)]
pub enum Res { Def(DefId), Unresolved }

pub struct Def { pub name: String, pub fn_level: u32, pub captured: bool, pub used: bool }

#[derive(Default)]
pub struct Resolver {
    pub defs: Vec<Def>,
    pub uses: Vec<(String, Res)>,        // one entry per name occurrence, in source order
    pub errors: Vec<String>,
    visible: HashMap<String, Vec<DefId>>, // name -> stack of visible defs; top = innermost
    undo: Vec<String>,                    // names declared, in order; scope exit pops back to a mark
    fn_level: u32,
}

impl Resolver {
    fn declare(&mut self, name: &str) -> DefId {
        let id = self.defs.len() as DefId;
        self.defs.push(Def { name: name.to_string(), fn_level: self.fn_level, captured: false, used: false });
        self.visible.entry(name.to_string()).or_default().push(id);
        self.undo.push(name.to_string());
        id
    }
    fn lookup(&mut self, name: &str) {
        let res = match self.visible.get(name).and_then(|s| s.last()) {
            Some(&id) => {
                let d = &mut self.defs[id as usize];
                d.used = true;
                if d.fn_level != self.fn_level { d.captured = true; } // defined in an enclosing function
                Res::Def(id)
            }
            None => { self.errors.push(format!("unresolved name `{name}`")); Res::Unresolved }
        };
        self.uses.push((name.to_string(), res));
    }
    fn scope<T>(&mut self, f: impl FnOnce(&mut Self) -> T) -> T {
        let mark = self.undo.len();
        let r = f(self);
        while self.undo.len() > mark {
            let n = self.undo.pop().unwrap();
            self.visible.get_mut(&n).unwrap().pop(); // innermost shadow removed, outer one is visible again
        }
        r
    }
    fn function(&mut self, params: &[String], body: &Expr) {
        self.fn_level += 1;
        self.scope(|r| {
            for (i, p) in params.iter().enumerate() {
                if params[..i].contains(p) { r.errors.push(format!("duplicate parameter `{p}`")); }
                r.declare(p);
            }
            r.expr(body);
        });
        self.fn_level -= 1;
    }
    pub fn expr(&mut self, e: &Expr) {
        match e {
            Expr::Num(_) => {}
            Expr::Name(n) => self.lookup(n),
            Expr::Add(a, b) => { self.expr(a); self.expr(b); }
            Expr::Call(f, args) => { self.expr(f); args.iter().for_each(|a| self.expr(a)); }
            Expr::Lambda(ps, body) => self.function(ps, body),
            Expr::Block(stmts, tail) => self.scope(|r| {
                // pass 1: hoist fn items so they can call each other and be used before their text
                let mut ids = Vec::new();
                for s in stmts { if let Stmt::Fn(n, ..) = s { ids.push(r.declare(n)); } }
                // pass 2: resolve bodies; `let` declares after its initializer (so `let x = x + 1` sees the outer x)
                for s in stmts {
                    match s {
                        Stmt::Let(n, init) => { r.expr(init); r.declare(n); }
                        Stmt::Fn(_, ps, body) => r.function(ps, body),
                    }
                }
                r.expr(tail);
            }),
        }
    }
}

pub fn resolve(e: &Expr) -> Resolver { let mut r = Resolver::default(); r.expr(e); r }

Tested with asserts: shadowing (let x = x + 1), use before let, mutual recursion of hoisted fns, capture flag on k, unresolved name, the outer binding restored on scope exit.

Complexity and constants

• Time O(n): every node once, one hash lookup per name occurrence, one push and one pop per declaration. Depth does not matter.
• Memory: one Def per declaration, one Vec<DefId> per distinct name, one use record per occurrence.
• Measured on one Apple-silicon Mac, release build, 40 nested blocks of 10 lets, 1 000 000 uses of the outermost name: about 23 ns per use for this design (including a String allocation per use in the code above), versus about 230-280 ns per use for a stack of per-scope HashMaps walked innermost-out. Cost driver: hashes per lookup (1 vs up to depth).

Efficiency

• Cost: about 23 ns per use for the single-map design, including a String allocation per use in the code above, versus 230-280 ns per use for a chain of per-scope HashMaps (measured above: Apple-silicon Mac, release build, 40 nested blocks, 1,000,000 uses of the outermost name). Memory: one Def per declaration, one Vec<DefId> per distinct name, one record per use. Bound: hashing and pointer chasing, not compute.
• Levers:
  • one map with shadow stacks and an undo log — one probe instead of up to depth, about 10x at depth 40 (measured above) — nested scopes
  • intern names to u32 symbols in the lexer — no hashing or string compare, visible becomes a Vec<Vec<DefId>> by symbol — any compiler
  • flat result Vecs indexed by id — dropping the pass frees everything at once — batch passes
  • resolve lazily per function body and cache by body — only edited bodies re-resolve — editors and language servers
  • scan a Vec<(name, slot)> from the end (Lua's local variables) — no hashing; competitive when few locals are live (measure first) — tiny languages
• Naive → standard → state of the art:
  • chain of per-scope hash maps, walked innermost-out · 230-280 ns per use at depth 40 (measured)
  • single map with shadow stacks and undo log · about 23 ns per use (measured)
  • interned symbols, array-indexed stacks, lazy per-body resolution · no hashing or allocation per use (design claim, not measured)

Implementation notes

• Store results as ids: uses[i] parallel to occurrence order, or write the DefId into the AST node. Later passes index defs by id.
• Use one pre-sized arena for defs and uses; avoid per-node boxes.
• Unused-variable lint costs one bool per definition (used).
• Assign frame slots at declaration time (slot = live locals in this function) to get stack offsets for free; reuse slots on scope exit.
• Separate namespaces (values, types, labels) by keeping one visible map per namespace.
• Multi-pass for module-level items: collect all top-level declarations first, resolve imports, then resolve bodies (this is the early/late split in rustc).
• Report the use span and the span of the previous declaration in duplicate errors; keep spans in Def.

Pitfalls

• Declare before initializer: let x = x + 1 then refers to itself (a bug, or a "used before init" case in JavaScript's TDZ). Decide per language and test it.
• Forgetting to pop on early return: with an undo log, always pop to the mark, including on error paths, or later lookups see stale bindings.
• Hoisting only some items: fn hoists, let does not; macros and imports add a third order.
• Capture by function level, not scope level: a block inside one function is not a closure boundary.
• Dynamic features (eval, with, import * with unknown contents) defeat static resolution; reject them or fall back to runtime lookup.
• Renaming/minifying: rename by DefId, never by string, or shadowed names collide.

Variants and alternatives

In production

• Compilers: Lua resolves locals to registers and upvalues during parsing (lparser.c); rustc's rustc_resolve resolves imports and macros early and every other name in a late pass over a stack of ribs (guide); Go's type checker collects package-level objects first and resolves bodies afterwards.
• Build tools: esbuild sets up scopes and declares symbols while parsing, then uses them for scope hoisting and minification (architecture); Babel and swc compute scopes and bindings for JavaScript transforms.
• Editors and IDEs: rust-analyzer does name resolution in its HIR crates and builds expression scopes per function body (architecture); the same bindings back LSP textDocument/definition.
• Databases: PostgreSQL's parse analysis binds table and column references in parse_relation.c (parser README).

Implementations

Sources

• Robert Nystrom, Crafting Interpreters, 2021, chapter "Resolving and Binding". read
• Rust compiler development guide, "Name resolution" (scopes and ribs, early vs late). read
• Pierre Neron, Andrew Tolmach, Eelco Visser, Guido Wachsmuth, A Theory of Name Resolution, ESOP 2015. paper
• Lua source, lparser.c (locals and upvalues resolved during parsing). code