Lesson 5.3 — Name-resolution strategies: declare-before-use, order independence, modules and imports, scope graphs¶

Techniques: declare-before-use in one pass (C, Pascal; forward declarations), order-independent resolution in several passes (Java members, Rust and Swift items, Pebble's top level), module and import resolution — qualified names, explicit and glob imports, shadowing and ambiguity, cyclic imports resolved by a fixed point (Modula-2, Java packages, Python modules, Rust's resolver, RFC 1560), and scope graphs as a unifying model (Néron, Tolmach, Visser & Wachsmuth 2015; Statix, van Antwerpen et al. 2018) · Pebble implements: two passes over the module (collect every item, then resolve bodies with declare-before-use inside them; exercise E2); ★ scope graphs for a module language in the lab (SPEC §5) · Prerequisites: Lessons 5.1–5.2 · Time: 4 hours

Lessons 5.1 and 5.2 resolved names inside one block structure, walking in source order. Real programs complicate the walk in two ways. Declarations can come after their uses: mutually recursive functions, a struct used before it is defined, a method calling one declared further down the class. And names cross modules: std::io::Write, import java.util.*, from os import path, where the module that declares a name may itself be found only by resolving another import. This lesson compares the strategies compilers use, from C's single pass to Rust's import fixed point, and ends with scope graphs, a single formalism in which all of them are special cases of "find a path in a graph".

1. Problem and motivation¶

The problem. Extend Lesson 5.1's resolution to (a) regions in which declaration order does not matter, and (b) programs split into named modules that refer to each other through qualified paths and imports, possibly cyclically. The output is still a binding per use (or an error: unbound, ambiguous, cyclic). The strategy decides how many passes the front end needs, whether forward declarations are required, and what errors programmers can get.

Declare-before-use¶

A one-pass compiler must know what a name means when it reads it, so the language requires every name to be declared before its first use: Pascal (1970), C, and early Fortran compilers. Mutual recursion needs a forward declaration (Pascal's forward, a C prototype). C89 still accepted a call to an undeclared function as an implicit declaration returning int; C99 removed that, and Clang 16 and GCC 14 made it an error (§7). Pebble uses declare-before-use inside function bodies (a local is visible from the next statement, pebble-spec §6.3).

Order-independent resolution¶

Java class members, Rust and Swift items, Haskell top-level bindings, and Pebble's functions and structs are visible in their whole region, regardless of order (pebble-spec §6.2). The compiler therefore resolves in (at least) two passes: first collect every declaration of the region into its table, then resolve the uses [ALSU07, §6.3; EaC3, Ch. 5]. Languages mix the two: Java members are order-independent but a field initializer may not read a field declared later (JLS §8.3.3 [JLS21-8]); Swift and Rust items are order-independent while locals are declare-before-use.

Module and import resolution¶

Modules add names that are qualified by a path (a::b::c) and imports that copy bindings from one module into another: an explicit import (use a::f;) binds one name, a glob import (use a::*;, import java.util.*;) binds every public name. Two questions make this hard: what happens when two imports bind the same name (Rust: an explicit import shadows a glob, two globs conflict only if the name is used [RFC1560]; Java: a single-type import shadows an on-demand one, JLS §6.4.1), and how to resolve imports that depend on other imports, possibly cyclically (mod a { pub use crate::b::*; } mod b { pub use crate::a::*; } is legal Rust). rustc answers the second with a fixed-point iteration over the unresolved imports (resolve_imports, §7).

Scope graphs¶

Each language above has its own ad hoc resolution rules. Néron, Tolmach, Visser and Wachsmuth [NTVW15] proposed one model: a scope graph whose nodes are scopes, with labeled edges for lexical parents (P), imports (I) and declarations (D); a reference resolves to the declarations reachable by a well-formed path (a regular expression over labels, such as \(P^{*} I^{?} D\)), keeping only the most specific paths under an order on labels (\(D < I < P\)). Lexical scoping, modules, imports, inheritance and records are all expressible, and resolution is language-independent. Statix [vAPRV18] turned scope graphs into a constraint language for type systems, and the Rust library scopegraphs (by the same group, §7) packages the resolution algorithm.

2. Definitions and algorithms¶

Definition 5.3.1 (Ordered and order-independent regions)

A region (Definition 5.1.1) is ordered if a declaration is a candidate only for uses that follow it (Definition 5.1.2), and order-independent if every declaration of the region is a candidate for every use in it. In an order-independent region two declarations of the same name in the same namespace are a redefinition error (Pebble E0302), because no position decides between them.

Algorithm 5.3.2 (Two-pass resolution: collect, then resolve)

Input: a module whose top-level region is order-independent and whose function bodies are ordered.
Output: a binding for every use; redefinition errors.
Precondition: item declarations can be recognized without resolving anything (their names are syntactic).
Postcondition: every use of an item name binds to that item wherever it appears; locals follow Definition 5.1.2.
Invariant: after pass 1, the item table holds exactly one entry per item name, the first definition.

function ResolveModule(M):
    items ← empty table                          # pass 1: collect
    for d in M.items in source order:
        if name(d) ∈ items: report redefinition at d, with a note at items[name(d)]
        else: items[name(d)] ← d
    for d in M.items:                             # pass 2: resolve
        for each item name used in d's signature: bind it through items
        if d has a body: ResolveBody(d.body, items)   # Algorithm 5.2.4, falling back to items

Definition 5.3.3 (Module tree, qualified path, import)

A module is an order-independent region with a name; modules form a tree under nesting (the crate or package root at the top). A qualified path \(a_1 :: a_2 :: \dots :: a_k\) resolves \(a_1\) in the scope of the use and each \(a_{i+1}\) among the members of the module \(a_i\) denotes. An explicit import use p::a; in module \(M\) adds to \(M\) the binding \(a \mapsto \mathrm{res}(p::a)\); a glob import use p::*; adds \(b \mapsto \mathrm{res}(p::b)\) for every public member \(b\) of \(\mathrm{res}(p)\). A module's bindings are its own declarations, its explicit imports and its glob imports, in decreasing priority; two bindings of equal priority for the same name are ambiguous (an error only if the name is used).

Algorithm 5.3.4 (Import resolution by fixed-point iteration)

Input: a module tree with declarations and imports.
Output: for every import, its target(s), or an error (unresolved, ambiguous).
Precondition: resolving a path can answer found, not found, or undetermined (the answer could still change because some import that might supply the name is itself unresolved).
Postcondition: every import that the loop resolved keeps its resolution in the final state; the rest are reported.
Invariant: (I1) a binding once added to a module is never removed or replaced; (I2) the number of undetermined imports never increases from one round to the next.

pending ← all imports;  done ← ∅
repeat:
    progress ← false
    for imp in pending:
        r ← ResolvePath(imp.path)                # found / not found / undetermined
        if r = undetermined: continue
        pending ← pending − {imp};  done ← done ∪ {imp};  progress ← true
        if r = found: add imp's binding(s) to imp's module   # glob: current and future members
until not progress
report every import still in pending (unresolved, or part of an import cycle with no base)

function ResolvePath(a1 :: ... :: ak):
    look a_i up in the current module; the answer is undetermined if the name is absent
    but some pending import of that module could still supply it (for a glob: could still
    gain members), or if a glob supplies it but a pending explicit import could shadow it

Definition 5.3.5 (Scope graph, following Néron et al. 2015)

A scope graph is a directed graph whose nodes are scopes and declarations, with edges labeled from a finite alphabet: here \(P\) (scope → lexical parent), \(I\) (scope → the body scope of an imported module) and \(D\) (scope → a declaration in it). A reference is a pair (name \(x\), scope \(s\)). A resolution path for it is a path from \(s\) to a declaration named \(x\) whose label word lies in a regular language \(\mathit{WF}\) (well-formedness). A label order \(<\) extends to paths: path \(p\) is more specific than \(q\) if at the first position where their label words differ, \(p\)'s label is smaller (a prefix counts as more specific than a longer path through its last scope, since \(D\) is the smallest label). The resolution of the reference is the set of declarations at the end of the most specific well-formed paths.

Definition 5.3.6 (The module calculus of the lab)

The lab's module language (def x;, module M { … }, import p;, ref p;) gives a scope graph: one scope per file and per module body, a \(P\) edge from each module body to the scope it is declared in, a \(D\) edge from each scope to each declaration in it, and an \(I\) edge from scope \(s\) to the body of module \(m\) for every import p; in \(s\) whose path resolves to \(m\). References use \(\mathit{WF}_{\mathrm{ref}} = P^{*} I^{?} D\) with \(D < I < P\) (local declarations beat imports, which beat enclosing scopes; imports are not transitive); import paths use \(\mathit{WF}_{\mathrm{imp}} = P^{*} D\) (imports are resolved lexically, which makes cyclic imports harmless); each further segment of a qualified path is one \(D\) step from the body of the module the previous segment denotes. More than one most specific declaration is ambiguous.

Algorithm 5.3.7 (Resolution in a scope graph with label order D < I < P)

Input: a scope graph as in Definition 5.3.6 with its \(I\) edges already built; a reference \((x, s)\); a flag saying whether \(I\) edges may be used.
Output: the set of declarations of the most specific well-formed paths.
Precondition: \(P\) edges form a tree (each scope has at most one parent).
Postcondition: the output equals the resolution of Definition 5.3.5 for \(\mathit{WF} = P^{*} I^{?} D\) (or \(P^{*} D\)).
Invariant: when the loop reaches scope \(t\) (after \(k\) parent steps), no well-formed path with fewer than \(k\) \(P\) edges ends at a declaration named \(x\).

function Lookup(s, x, useImports):
    t ← s
    while t ≠ none:
        ds ← { d | t —D→ d, name(d) = x }            # D beats I and P
        if ds ≠ ∅: return ds
        if useImports:
            ds ← { d | t —I→ b —D→ d, name(d) = x }   # I D beats P
            if ds ≠ ∅: return ds
        t ← parent(t)                                   # one more P step
    return ∅

3. Worked example¶

Declare-before-use and order independence¶

The Pebble module of Definition 5.3.1's example (checked with ch05-resolve):

fn main() -> int { return even(4) as int; }
fn even(n: int) -> bool { if n == 0 { return true; } return odd(n - 1); }
fn odd(n: int) -> bool { if n == 0 { return false; } return even(n - 1); }
struct Pair { a: Point, b: Point }
struct Point { x: int, y: int }

A single declare-before-use pass fails at the first forward reference; Algorithm 5.3.2 does not:

step	pass	event	functions table	structs table	result
1	one pass	read `fn main`, body uses `even`	{main}	{}	unbound `even` (declared at line 2)
2	two passes, 1	collect `main`, `even`, `odd`	{main, even, odd}	{}
3	1	collect `Pair`, `Point`	{main, even, odd}	{Pair, Point}
4	2	`main`: call `even`			`fn even@2:4`
5	2	`even`: call `odd`; `odd`: call `even`			`fn odd@3:4`, `fn even@2:4`
6	2	`Pair`: field types `Point`, `Point`			`struct Point@5:8` (twice)

ch05-resolve prints exactly these bindings (1:27 call even -> fn even@2:4, 2:61 call odd -> fn odd@3:4, 4:18 type Point -> struct Point@5:8, …). In C you would write prototypes bool even(int); bool odd(int); above main — a manual pass 1.

Imports as a fixed point¶

Rust-like modules (the imports are listed in the order the loop visits them):

mod a { pub use crate::b::*; pub fn f() {} }
mod b { pub use crate::c::g; }
mod c { pub fn g() {} }
mod d { use crate::a::g; }

round	import	ResolvePath	outcome	bindings added
1	`a: use b::*`	module `b` found	resolved (glob: now and later members of `b`)	a gets b's members: none yet
1	`b: use c::g`	`c::g` found	resolved	b: g ↦ c::g, so a: g ↦ c::g too
1	`d: use a::g`	`a::g` found through the glob	resolved	d: g ↦ c::g
2	—	nothing pending	stop

Visiting d: use a::g before b: use c::g would give undetermined in round 1 (a glob of a could still gain g), and found in round 2. The measure "number of undetermined imports" went 1 → 0 (Invariant I2); rustc counts it the same way.

Scope graphs¶

The lab's hand test (ch05.Binders.L6_ScopeGraphHandCases), with its scope graph:

def x;                  # 1:5
module A {              # 2:8
  def x;                # 3:7
  def y;                # 4:7
  module B { def z; }   # 5:10, z at 5:18
}
module C {              # 7:8
  import A;
  ref x;   ref y;   ref B.z;   ref z;
  def y;                # 13:7
  ref A.B.z;
}
ref x;  ref A.x;  ref A.q;  ref x.y;

flowchart TD
  F([file scope]) -->|D| DX1[x 1:5]
  F -->|D| MA[module A 2:8]
  F -->|D| MC[module C 7:8]
  SA[scope A] -->|P| F
  SA -->|D| DX3[x 3:7]
  SA -->|D| DY4[y 4:7]
  SA -->|D| MB[module B 5:10]
  SB[scope B] -->|P| SA
  SB -->|D| DZ[z 5:18]
  SC[scope C] -->|P| F
  SC -->|I| SA
  SC -->|D| DY13[y 13:7]

Algorithm 5.3.7 on the references of C (the import import A was resolved first with \(P^{*} D\): from scope C, no A among C's declarations, one \(P\) step, \(D\) to module A 2:8; this created the \(I\) edge C → scope A):

reference	scope t	step	candidates	result
`ref x`	C	D: C's declarations named x	∅
	C	I D: A's declarations named x	{x 3:7}	3:7 — the import beats the file's `x`
`ref y`	C	D	{y 13:7}	13:7 — the local `def y` beats the import (position does not matter in a module)
`ref B.z`	C	D, then I D for `B`	{module B 5:10}	then D from B's body: z 5:18
`ref z`	C	D, I D	∅, ∅ (z is inside B, and imports are not transitive)
	file	D, I D	∅, ∅	unresolved
`ref A.B.z`	C	D, I D for `A`	∅, ∅
	file	D	{module A 2:8}	then B, then z 5:18

And at the file level: ref x → 1:5, ref A.x → 3:7, ref A.q → unresolved, ref x.y → unresolved (x is not a module).

Try it

The lab's L6_ScopeGraphRandomAgainstEnvironments test generates 400 module programs like this one; write a few by hand and predict the results before running ./course test 5 -R L6. The drill ./course drill resolve-scopes --difficulty medium practices the order-dependent part inside functions.

4. Invariants and correctness¶

Declare-before-use¶

Proposition 5.3.8 (One pass suffices exactly for declare-before-use)

A resolver that makes one left-to-right pass and never revisits a use resolves every use correctly if and only if every use's static binding precedes it in the source.

Proof

(⇐) Theorem 5.2.3: the resolution walk is a single left-to-right pass, and each lookup needs only declarations that precede the use. (⇒) If some use \(u\) binds to a declaration \(d\) after it, then when the pass reaches \(u\) it has not seen \(d\), so its answer is computed without \(d\) and is wrong (either another declaration or "unbound"); since the pass never revisits \(u\), it stays wrong.

Order-independent resolution¶

Theorem 5.3.9 (Two-pass resolution is correct)

Algorithm 5.3.2 binds every use of an item name in the module to the (first) item of that name, wherever the use appears, and resolves locals by Definition 5.1.2.

Proof

Pass 1 visits every item before pass 2 starts, so when any use is resolved the item table is complete; by the invariant it holds the first definition of each name. In pass 2, item uses in signatures are looked up in the table directly. Inside bodies, the resolver of Lesson 5.2 looks in the local scopes first and falls back to the table; since the module region is the outermost region and is order-independent, falling back to the complete table gives every item as a candidate at every use (Definition 5.3.1), so the innermost-candidate rule chooses a local when one is visible and the item otherwise. Redefinitions are reported in pass 1, and later definitions of the same name are ignored for binding, so there is a unique answer.

Module and import resolution¶

Theorem 5.3.10 (The import fixed point terminates, and resolved imports are final)

Algorithm 5.3.4 terminates after at most \(I + 1\) rounds, where \(I\) is the number of imports. Every import it resolves has the same resolution as it would have in the final module state.

Proof

Termination: each round either removes at least one import from pending (progress) or ends the loop; pending starts with \(I\) imports. Finality: an import is resolved only when ResolvePath answers found or not found, never undetermined. By the definition of ResolvePath, such an answer is given only if no pending import could add a binding for any looked-up name or shadow a glob binding it used. Bindings are only ever added (I1), and only by pending imports; so the bindings the answer relied on, and the absence of the ones it did not find, both persist until the end. Hence the resolution in the final state is the same.

Why undetermined answers are needed

Suppose mod m { use crate::a::*; use crate::b::f; } and the loop resolves a use of m::f while use crate::b::f is still pending, taking f from the glob of a. When the explicit import resolves, it shadows the glob (Definition 5.3.3), and the earlier answer becomes wrong. Answering undetermined while an explicit import of the same name is pending prevents that; rustc's Determinacy::Undetermined exists for this reason.

Scope graphs¶

Theorem 5.3.11 (Scope-graph resolution equals environment resolution)

For the module calculus of Definition 5.3.6, Algorithm 5.3.7 returns the resolution of Definition 5.3.5, and it coincides with the environment semantics \(\mathrm{env}(s, x) = D(s, x)\) if non-empty, else \(\mathrm{Imp}(s, x)\) if non-empty, else \(\mathrm{env}(\mathrm{parent}(s), x)\) — where \(D(s, x)\) is the set of declarations named \(x\) directly in \(s\) and \(\mathrm{Imp}(s, x)\) the union of \(D(b, x)\) over the bodies \(b\) imported into \(s\) (the lab's test oracle).

Proof

Well-formed paths: a path matching \(P^{k} D\) ends at a declaration of \(\mathrm{parent}^{k}(s)\); a path matching \(P^{k} I D\) ends at a declaration of a body imported into \(\mathrm{parent}^{k}(s)\). Specificity: compare two such paths by their label words. If they have different numbers \(k < k'\) of leading \(P\)s, they first differ at position \(k + 1\), where the shorter one has \(D\) or \(I\) and the longer one has \(P\); since \(D < P\) and \(I < P\), the path with fewer \(P\) steps is more specific. With equal \(k\), \(P^{k} D\) beats \(P^{k} I D\) at position \(k + 1\) because \(D < I\). So the most specific paths are those with the smallest \(k\) for which a declaration exists, and at that \(k\) the \(D\)-paths if any, else the \(I D\)-paths. Algorithm: the loop tries \(k = 0, 1, \dots\) in order (invariant: it reaches \(\mathrm{parent}^{k}(s)\) only after finding nothing for smaller \(k\)), and at each \(k\) returns the \(D\)-set if non-empty, else the \(I D\)-set if non-empty: exactly the most specific paths' endpoints. Environment: unfolding \(\mathrm{env}\) gives the same case analysis, level by level. With useImports false, the same argument with \(P^{*} D\) gives the lexical rule used for imports.

5. Complexity¶

Variables: \(n\) identifier occurrences; \(m\) items; \(I\) imports; \(g\) glob imports; \(\delta\) the depth of the module tree (or of the scope-graph \(P\) chain); \(e\) the number of edges of a scope graph.

Technique	Time	Space	Pathological input
Declare-before-use, one pass	\(O(n)\) expected	\(O(n)\)	none; but forward references need prototypes
Order-independent, two passes	\(O(n + m)\) expected	\(O(n + m)\) (the item table)	none
Import fixed point (Alg. 5.3.4)	\(O(I \cdot R)\) rounds × cost, \(R \le I + 1\) rounds: \(O(I^2 \cdot c)\) with \(c\) the cost of one `ResolvePath`	\(O(\text{bindings})\)	a chain of \(I\) imports listed in reverse dependency order resolves one per round: \(\Theta(I^2)\) attempts
Globs	each glob re-exports up to all members: \(O(g \cdot \text{members})\) bindings	same	\(g\) modules each glob-importing all others: \(\Theta(g^2 \cdot \text{members})\) bindings
Scope graphs (Alg. 5.3.7)	\(O(\delta \cdot \text{out-degree})\) per query; general regular \(\mathit{WF}\): \(O(e \cdot \lvert \text{automaton} \rvert)\) per query by product-graph search	\(O(e)\)	transitive imports (\(I^{*}\)) need cycle detection on the product graph

Justification. The chain \(M_1\) imports \(M_2\) imports … \(M_I\), visited in the order \(M_1, \dots, M_I\), is undetermined everywhere except the last pending one in each round, so round \(r\) attempts \(I - r + 1\) imports: \(\sum_r (I - r + 1) = \Theta(I^2)\). For scope graphs, a query with an arbitrary regular \(\mathit{WF}\) is a shortest-path search in the product of the graph and the automaton of \(\mathit{WF}\) [NTVW15, §4]; with \(P^{*} I^{?} D\) and a parent tree, the product degenerates to the loop of Algorithm 5.3.7. Real scale: rustc resolves the imports of a large crate in a few rounds because most imports resolve in round 1; the quadratic case needs adversarial ordering.

Declare-before-use¶

Forward declarations (Pascal forward, C prototypes, C++ class forward declarations): the programmer supplies pass 1 by hand.
Implicit declarations (C89 functions, Fortran implicit typing): an unknown name gets a default declaration; convenient, and a classic source of bugs, which is why C99 dropped it for functions.

Order-independent resolution¶

Lazy, on-demand resolution instead of a separate collect pass: resolve an item's signature when first needed and detect cycles with an "in progress" mark (Swift's request evaluator, Lesson 5.6).
Mixed regions: Java members are order-independent but field initializers are checked for forward references (JLS §8.3.3); C++ class members are visible in member function bodies (a "complete-class context") but not in member declarations earlier in the class.

Module and import resolution¶

Globs: explicit-over-glob shadowing (Rust, Java single-type vs on-demand imports); "ambiguous only if used" (Rust) vs "ambiguous at the import" (older designs).
Cyclic imports: allowed and resolved statically (Rust, Java, Haskell with hs-boot files) or at run time with partially initialized modules (Python's module cache, where from a import f inside a cycle can fail with "partially initialized module").
Separate compilation: imports of other compilation units read an interface (C++20 BMIs, Rust .rmeta, Swift .swiftmodule) instead of source.

Scope graphs¶

Scopes as types and Statix [vAPRV18]: scope graphs built by constraint solving, with scopes also representing record and module types; queries may be issued before the graph is complete, which requires knowing when a query's answer is stable — the "critical edges" of Rouvoet et al. [RvAPKV20], analogous to Algorithm 5.3.4's undetermined.
Stack graphs (GitHub, 2021): a scope-graph variant that can be built per file and joined incrementally for code navigation across a repository.

7. In real compilers¶

Declare-before-use¶

Clang reports a call to an undeclared function in C99 and later as an error (Sema::ImplicitlyDefineFunction in clang/lib/Sema/SemaDecl.cpp, LLVM 23.1.2 [CLANG-SemaDecl]); GCC 14 made -Wimplicit-function-declaration an error by default.

Clang 23 and GCC 14 reject a use before declaration in C

Reproduce (clang 23.1.2, gcc 14.2.0):

cat > order.c <<'EOF'
int main(void) { return helper(2); }
int helper(int n) { return n + 1; }
EOF
clang-23 -fsyntax-only order.c
gcc-14 -fsyntax-only order.c

Output (complete; Clang, then GCC):

order.c:1:25: error: call to undeclared function 'helper'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
    1 | int main(void) { return helper(2); }
      |                         ^
1 error generated.
order.c: In function 'main':
order.c:1:25: error: implicit declaration of function 'helper' [-Wimplicit-function-declaration]
    1 | int main(void) { return helper(2); }
      |                         ^~~~~~

What to notice: C's file scope is an ordered region (Definition 5.3.1): helper is declared, but only after the use, so the one-pass resolver cannot see it (Proposition 5.3.8). A prototype int helper(int); above main fixes it.

Order-independent resolution¶

rustc collects all items of a crate into its module tree before resolving any body (build_reduced_graph in compiler/rustc_resolve/src/build_reduced_graph.rs, rustc 1.94.1 [RUSTC-BRG]). javac enters all class members first (TypeEnter/MemberEnter) and checks field forward references separately (Attr.checkInit, Errors.IllegalForwardRef in src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Attr.java, jdk-21+35 [JAVAC-Attr]).

Order-independent items in rustc 1.94 and javac 21's one exception

Reproduce (rustc 1.94.1, javac 21.0.10):

cat > items.rs <<'EOF'
fn main() {
    println!("{}", even(10));       // defined below: items are order-independent
    let p = Point { x: 1 };
    println!("{}", p.x);
}
fn even(n: u32) -> bool { if n == 0 { true } else { odd(n - 1) } }
fn odd(n: u32) -> bool { if n == 0 { false } else { even(n - 1) } }
struct Point { x: i32 }
EOF
rustc --edition 2021 items.rs -o items && ./items
mkdir -p j && cat > j/Order.java <<'EOF'
class Order {
    static int a = b + 1;          // a field initializer may not read a later field
    static int b = 2;
    static int f() { return g(); } // methods: any order
    static int g() { return a; }
}
EOF
javac -d j j/Order.java

Output (complete; the two lines of the Rust program, then javac):

true
1
j/Order.java:2: error: illegal forward reference
    static int a = b + 1;          // a field initializer may not read a later field
                   ^
1 error

What to notice: Rust resolves even, odd and Point before their definitions (Theorem 5.3.9). Java does the same for methods (f calls g), but its field initializers form an ordered region inside an order-independent class, because they run in textual order and reading b early would observe its default value.

Module and import resolution¶

rustc: resolve_imports is the fixed-point loop of Algorithm 5.3.4, iterating while the count of undetermined imports decreases, and finalize_imports reports what is left (compiler/rustc_resolve/src/imports.rs, rustc 1.94.1 [RUSTC-Imports]); resolve_ident_in_lexical_scope in ident.rs walks ribs and modules. The rules for globs and shadowing are RFC 1560 [RFC1560]. javac resolves imports in TypeEnter and reports on-demand ambiguities at the use (Resolve.java).

Glob imports, shadowing and ambiguity in rustc 1.94

Reproduce (rustc 1.94.1):

cat > globs.rs <<'EOF'
mod a { pub fn f() -> &'static str { "a::f" } pub fn g() -> &'static str { "a::g" } }
mod b { pub fn f() -> &'static str { "b::f" } }
mod c {
    use crate::a::*;          // glob imports: f and g
    use crate::b::f;          // an explicit import shadows the glob's f
    pub fn run() -> String { format!("{} {}", f(), g()) }
}
mod d {
    use crate::a::*;
    use crate::b::*;          // two globs both provide f: only an error if f is used
    pub fn run() -> &'static str { f() }
}
fn main() { println!("{}", c::run()); println!("{}", d::run()); }
EOF
rustc --edition 2021 globs.rs -o globs

Output (complete):

error[E0659]: `f` is ambiguous
  --> globs.rs:11:36
   |
11 |     pub fn run() -> &'static str { f() }
   |                                    ^ ambiguous name
   |
   = note: ambiguous because of multiple glob imports of a name in the same module
note: `f` could refer to the function imported here
  --> globs.rs:9:9
   |
 9 |     use crate::a::*;
   |         ^^^^^^^^^^^
   = help: consider adding an explicit import of `f` to disambiguate
note: `f` could also refer to the function imported here
  --> globs.rs:10:9
   |
10 |     use crate::b::*;          // two globs both provide f: only an error if f is used
   |         ^^^^^^^^^^^
   = help: consider adding an explicit import of `f` to disambiguate

warning: unused import: `crate::b::*`
  --> globs.rs:10:9
   |
10 |     use crate::b::*;          // two globs both provide f: only an error if f is used
   |         ^^^^^^^^^^^
   |
   = note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default

error: aborting due to 1 previous error; 1 warning emitted

For more information about this error, try `rustc --explain E0659`.

What to notice: module c compiles — its explicit use crate::b::f outranks the glob's f (Definition 5.3.3) — and only d's use of f is an error: two bindings of equal priority are ambiguous only when referenced. (Replacing d::run's body by a string literal makes the program compile and print b::f a::g.)

Scope graphs¶

No production compiler of a mainstream language resolves through a general scope-graph engine; the model lives in language workbenches: Spoofax and Statix [vAPRV18], and the scopegraphs Rust crate by the same TU Delft group (metaborg/rust-scopegraphs, 0.3.3 [SG-Crate]), whose query() API takes exactly a well-formedness regex and a label order. GitHub's stack graphs (code navigation) are the industrial descendant. The lab's ★ milestone implements Algorithm 5.3.7.

Label orders decide shadowing: the scopegraphs crate 0.3.3

Reproduce (rustc/cargo 1.94.1; downloads the crate from crates.io):

mkdir -p sgdemo/src && cd sgdemo
cat > Cargo.toml <<'EOF'
[package]
name = "sgdemo"
version = "0.1.0"
edition = "2021"

[dependencies]
scopegraphs = "=0.3.3"
EOF
cat > src/main.rs <<'EOF'
// file:   def x;                        (scope s_file)
//         module A { def x; }           (scope s_a, parent s_file)
//         module B { import A; ref x; } (scope s_b, parent s_file, imports s_a)
use scopegraphs::completeness::UncheckedCompleteness;
use scopegraphs::resolve::Resolve;
use scopegraphs::{label_order, query_regex, Label, ScopeGraph, Storage};

#[derive(Label, Hash, PartialEq, Eq, Debug, Clone, Copy)]
enum Lbl { Lex, Imp, Def }
use Lbl::*;

#[derive(Hash, PartialEq, Eq, Debug, Default)]
enum Data { #[default] Scope, Decl { name: &'static str, site: &'static str } }

fn main() {
    let storage = Storage::new();
    let sg: ScopeGraph<Lbl, Data, UncheckedCompleteness> = unsafe { ScopeGraph::raw(&storage) };
    let s_file = sg.add_scope_default();
    let s_a = sg.add_scope_default();
    let s_b = sg.add_scope_default();
    sg.add_edge(s_a, Lex, s_file);
    sg.add_edge(s_b, Lex, s_file);
    sg.add_edge(s_b, Imp, s_a);
    sg.add_decl(s_file, Def, Data::Decl { name: "x", site: "file" });
    sg.add_decl(s_a, Def, Data::Decl { name: "x", site: "module A" });

    let is_x = |d: &Data| matches!(d, Data::Decl { name: "x", .. });
    for (order, env) in [
        ("Def < Imp < Lex", sg.query()
            .with_path_wellformedness(query_regex!(Lbl: Lex* Imp? Def))
            .with_data_wellformedness(is_x)
            .with_label_order(label_order!(Lbl: Def < Imp < Lex))
            .resolve(s_b)),
        ("Def < Lex < Imp", sg.query()
            .with_path_wellformedness(query_regex!(Lbl: Lex* Imp? Def))
            .with_data_wellformedness(is_x)
            .with_label_order(label_order!(Lbl: Def < Lex < Imp))
            .resolve(s_b)),
    ] {
        for path in env.into_iter() {
            println!("order {order}: `ref x` in B resolves to {:?}", path.data());
        }
    }
}
EOF
cargo run -q

Output (complete):

order Def < Imp < Lex: `ref x` in B resolves to Decl { name: "x", site: "module A" }
order Def < Lex < Imp: `ref x` in B resolves to Decl { name: "x", site: "file" }

What to notice: the graph and the well-formedness regex \(P^{*} I^{?} D\) (Lex* Imp? Def) are the same in both queries; only the label order changes, and with it which of the two reachable declarations shadows the other (Definition 5.3.5). Pebble's lab uses \(D < I < P\), the first order: imports beat enclosing scopes, as in Java and Rust.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Declare-before-use	Correct only if every binding precedes its use (Proposition 5.3.8); mutual recursion needs forward declarations	\(O(n)\), one pass · the fastest	Clear "undeclared" errors, but also for names declared later in the file	Lowest	C, Pascal, locals in most languages, Pebble function bodies
Order-independent resolution	Any order within the region (Theorem 5.3.9); redefinitions must be errors	\(O(n + m)\), two passes	Errors can point to both definitions; "used before declared" is impossible	Low: a collect pass	Java members, Rust/Swift/Haskell items, Pebble items
Module and import resolution	Qualified names, globs, re-exports and cycles (Theorem 5.3.10)	\(O(I^2 c)\) worst case, a few rounds in practice	Ambiguity and "unresolved import" errors with notes for each candidate (E0659 box)	High: determinacy, globs, visibility	Rust, Java, Haskell, Python (at run time), C++20 modules
Scope graphs	Language-independent; lexical, import, inheritance and record lookups in one model (Theorem 5.3.11)	\(O(\delta)\) per query for \(P^{*} I^{?} D\); product-graph search in general	Resolution paths explain why a name resolved	Medium for the engine, low per language	Language workbenches (Spoofax/Statix), the `scopegraphs` crate, stack graphs, the lab

Choose declare-before-use for local variables and for one-pass compilers. Choose order independence for everything at module or class level: programmers should not have to order functions. Choose a fixed-point import resolver as soon as imports can re-export (globs, pub use); use determinacy to keep results order-independent. Choose scope graphs when you design several languages or a language workbench, when you need an explanation of each resolution for tooling, or as the specification you test an ad hoc resolver against (as the lab does).

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Declare-before-use	`one-pass-forward`, `find-clang-implicit`	`resolve-scopes` (declarations visible from the next statement)	`declare-before-use`	E1
Order-independent resolution	`two-pass-items`, `java-forward-ref`	— (the pass structure is fixed; E2's tests exercise it)	`order-independent`	E2
Module and import resolution	`glob-shadowing`, `import-fixpoint-rounds`	— (quiz traces)	`module-imports`	—
Scope graphs	`scope-graph-resolve`, `label-order`	— (lab L6 generates random module programs)	`scope-graphs`	lab L6 ★

References¶

See the chapter references.

Lesson 5.3 — Name-resolution strategies: declare-before-use, order independence, modules and imports, scope graphs¶

1. Problem and motivation¶

Declare-before-use¶

Order-independent resolution¶

Module and import resolution¶

Scope graphs¶

2. Definitions and algorithms¶

3. Worked example¶

Declare-before-use and order independence¶

Imports as a fixed point¶

Scope graphs¶

4. Invariants and correctness¶

Declare-before-use¶

Order-independent resolution¶

Module and import resolution¶

Scope graphs¶

5. Complexity¶

6. Variants and refinements¶

Declare-before-use¶

Order-independent resolution¶

Module and import resolution¶

Scope graphs¶

7. In real compilers¶

Declare-before-use¶

Order-independent resolution¶

Module and import resolution¶

Scope graphs¶

8. Comparison¶

9. Assessment¶

References¶