Symbol Tables and Scopes

Name resolution associates uses of names in source code with their declarations or candidate declarations. Symbol tables store these identities and related information, which are later relied upon for type checking, capture analysis, and code generation. In complex languages, these phases may be interleaved, and not all names can be resolved in a single pass without type information.

The most important distinction is between spelling and identity: two variables both named x can be different symbols, and the same symbol may be accessed via aliases or qualified paths.

Scope Determines Name Visibility

Lexical scope determines the lookup environment based on program structure. Assuming the language allows inner scopes to shadow outer ones, entering an inner scope prioritizes finding the inner declaration; leaving it restores the outer environment.

When declarations become visible is dictated by the language. Whether functions allow forward references, whether local variables are visible within their own initializers, and whether re-declaration in the same block is an error, cannot be replaced by the simplistic rule of "add to the table upon encountering the definition."

For example, in let x = x + 1, some languages allow the right-hand side to refer to the previous x, while others might place the new declaration in an uninitialized state. Implementations should distinguish between declaration, initialization, and readable states.

A Concise Implementation of Lexical Environments

Each scope maintains a mapping from names to SymbolId and a reference to its parent. insert only checks for duplicates within the current scope; lookup searches up the parent chain from the current environment; lookup_current is used in scenarios requiring a search limited to the current layer only.

Hash table queries per layer are typically expected to be O(1), while searching the parent chain depends on depth. Implementations can also use binding stacks per name, undo logs, or persistent maps; there is no single data structure that is "correct" solely by adopting a scope stack.

If the AST or IDE index still references SymbolId after analysis ends, the symbol records must persist. Popping the current active scope does not mean deleting declaration data referenced by subsequent phases. Separating temporary traversal stacks from long-term symbol storage avoids dangling indices.

Active environments can exit, but resolved references cannot disappear

The following defines rules for a teaching language: duplicate declarations with the same name in the same layer cause an error, while inner layers are allowed to shadow; it only handles value names and does not support imports or overloading. Symbol records are stored in the arena of the current analysis, and scopes only save the index of the records. This integer ID is stable within the current analysis, not a globally stable ID across file edits.

from dataclasses import dataclass

@dataclass(frozen=True)
class Symbol:
    name: str
    declaration: str

class Scope:
    def __init__(self, parent=None):
        self.parent = parent
        self.names = {}

    def declare(self, arena, name, location):
        if name in self.names:
            raise ValueError(f"duplicate {name}: {location}")
        identity = len(arena)
        arena.append(Symbol(name, location))
        self.names[name] = identity
        return identity

    def lookup(self, name):
        current = self
        while current is not None:
            if name in current.names:
                return current.names[name]
            current = current.parent
        raise NameError(name)

arena = []
outer = Scope()
a = outer.declare(arena, "x", "line 1")
inner = Scope(outer)
assert inner.lookup("x") == a  # Before inner declaration appears
b = inner.declare(arena, "x", "line 3")
resolved_use = inner.lookup("x")
assert resolved_use == b and a != b
try:
    inner.declare(arena, "x", "line 4")
except ValueError:
    pass
else:
    raise AssertionError("duplicate accepted")
assert len(arena) == 2  # Failed insertion leaves no ghost records
active = outer
assert active.lookup("x") == a
assert arena[resolved_use].declaration == "line 3"
try:
    active.lookup("missing")
except NameError:
    pass
else:
    raise AssertionError("unresolved name accepted")

The final read of the arena illustrates: after exiting the inner scope, resolved usage points still refer to the inner declaration. Code generation or "jump to definition" cannot re-lookup lookup("x") from the current outer environment, or it would incorrectly rebind inner references to the outer one.

To support continuous shadowing within the same block, one can establish new visibility layers after each declaration or adjust binding stack rules; one cannot claim to have fully implemented Rust's let rules while simultaneously using the "duplicate error in same layer" approach from this example. Rustc Scopes

Does leaving a scope rebind existing references?

Connect each use to a declaration ID, not merely a shared color for spelling x. New lookup may find S1 inside and S0 after exit, while recorded uses keep their original targets. Closure uses also have a binding origin. The toggle rebuilds source analysis instead of pretending declaration edits rebind runtime variables.

What Symbol Records Should Store

Namespaces are also dictated by the language. In C, tag names and regular identifiers belong to different namespaces; labels have their own scope. Putting all spellings into a single unclassified table would cause false duplicate reports or wrong definition lookups.

Module Imports: Candidate Sources and Access Rights

Priorities differ among module paths, explicit imports, wildcard imports, aliases, and built-in names. Symbol tables should retain candidate sources to facilitate reporting ambiguities like "both imports provide this name," rather than arbitrarily selecting the last inserted one.

Finding a declaration and allowing access to it from the current location are two separate issues. Visibility checks may also depend on module hierarchy, packages, or other language rules, not just public/private values.

Module cycles are not necessarily illegal. Some languages allow collecting declarations first, then resolving function bodies or handling strongly connected components; others prohibit certain dependency cycles. Recursive imports should be prevented from causing infinite resolution, but unconditional errors for all cycles are incorrect. Rust's name resolution also interacts with macro expansion and different namespaces. Rustc Name Resolution

Overloading: Lookup Candidates and Target Selection Can Be Stepwise

Languages with overloading may first obtain a candidate set based on name and scope, then select the callable target based on argument count, types, implicit conversions, and generic constraints. Member lookup also depends on the receiver type.

Therefore, "lookup returns a single symbol" is an interface for simple languages. Complex implementations can return candidates, deferred resolution items, or error placeholders, retaining source information for diagnostics.

Closure Capture: Name Resolution Only Completes the First Step

When a closure references an outer local variable, the resolver needs to know which external binding it points to; capture methods, environment layout, and escaping require analyzing how the closure uses that value and the language's ownership rules.

fn main() {
    let values = vec![2, 4, 6];
    let length = || values.len();
    assert_eq!(length(), 3);
    assert_eq!(values[0], 2);
}

Here, reading the length of the Vec only requires a shared borrow; it does not automatically move ownership just because Vec is not Copy. move capture does not imply the closure can only be called once; Fn, FnMut, and FnOnce depend on how the closure uses captured values upon invocation. Rust Closures

Being captured does not necessarily mean heap allocation. Non-escaping closures may use stack environments; capturing by value can place data into the closure object, and optimizations may even eliminate the environment. The true requirement is that captured values remain valid for the required duration; borrowing, copying, moving, boxing, or upvalues are different implementation strategies.

Closures Cannot Re-lookup by Same Name at Invocation

Once lexical binding is determined, subsequent declarations with the same name do not rewire existing closures to the new declaration. In the following Rust example, the closure always references the first value; the second value merely shadows the name for subsequent direct uses. Both bindings remain valid for their required durations.

fn main() {
    let value = 10;
    let read_old = || value;
    let value = 20;
    assert_eq!(read_old(), 10);
    assert_eq!(value, 20);
    assert_eq!(read_old(), 10);
}

This is a separate dimension from "capture by value vs. by reference": first determine which binding is referenced, then decide how to provide that binding to the closure. If a language allows modifying the same binding being referenced, subsequent reads might observe its new value; but switching to another binding with the same name does not equate to modifying the original binding.

Generic Instantiation: Source Symbols and Backend Instances Managed Separately

A generic declaration has a stable identity, while specific type arguments form the instantiation context. The backend can cache instances using keys like "declaration identity + substituted parameters," avoiding the need to copy a set of source-language scope symbols for every use.

Whether code generation uses monomorphization, shared implementations, or dictionary passing is a subsequent strategy. Different type arguments do not guarantee different machine code in the final output; optimization, inlining, and link-time deduplication all affect the artifacts.

From Batch Compilation to IDE

Batch traversal can use an active environment stack; interactive systems must also handle modified symbol identities, dependency invalidation, and old location mappings. Editing a single function body should not arbitrarily change all symbol identities in the entire project; changes to public declarations may require re-checking dependencies.

Diagnostics should ideally indicate usage locations, candidate declarations, and specific failure rules, such as "this name comes from a private module" or "two wildcard imports cause ambiguity," rather than converting everything to "symbol not found."

References

• rustc Name Resolution.
• Rust Closures.
• Type Systems, LSP.

Keywords: symbol table, SymbolId, lexical scope, shadowing, namespace, visibility, overload, closure capture, lifetime