Collecting Declarations Before Resolving Any Body

Mutual recursion between two functions is the smallest program that a single-pass resolver cannot handle. One of the two definitions must come first in the file, and its body refers to a name declared only later. Any language that permits this — Go, Java, C# for members, OCaml, Haskell — forces the compiler to know about a declaration before it has walked the body that declares it. The mechanism that does this is a separate collection pass, and the constraints it must respect are subtler than the phrase “hoist the declarations” suggests.

The two passes and what separates them

A collection pass walks the syntax tree and inserts declarations into scope frames without resolving any expression or type. A resolution pass then walks the same tree with the frames populated and resolves every identifier use. Both traverse the same nodes; only the first mutates the environment.

The pass split must be by scope, not by node type. Collection for a block inserts every declaration directly contained in that block, including those nested inside constructs that do not introduce a new scope, and then recurses into constructs that do. Function parameters, receiver bindings, and type parameters belong to the function’s own frame and are collected before the body. A for loop whose header declares a variable creates a scope for the whole loop, and that variable is visible in the condition, the body, and the increment.

What collection must record beyond the name is dictated by the second pass. It needs the kind of entity, so that a type annotation resolves against a type and an expression against a value. It needs the declaration node, for diagnostics. It needs the declared type where one is written, since resolving a type expression may itself require the surrounding scope — var x T in Go resolves T in the scope where the declaration appears, and a resolver that collected only names could not resolve T at the right point. And for a language with multiple assignment or a declaration list, it needs the position within the list, because the initialization order rules are defined over that order.

What ordering rules survive collection

Hoisting does not mean order stops mattering. It means the visibility rule is decoupled from the evaluation rule, and the two must be recorded separately.

At package or module level, Go makes declarations order-independent: a function may reference a package-level variable declared later in the file, and the compiler resolves both directions. The language still defines initialization order as a dependency order computed over the initializers, so a cycle among package-level variables is an error even though the names resolve. That distinction — resolution succeeds, initialization fails — is only expressible if collection recorded the declaration without committing to an order.

Inside a function, the rule usually flips: a local must be initialized before it is read. Two mechanisms enforce that, and only the second needs the table to hold a binding that is not yet legal. Go and Java take the simpler route: the scope of a local begins at its declaration, at the declarator for Java and at the end of the specification for Go, so a use written before the declaration does not see the binding at all and either resolves to an outer declaration or fails as undeclared. JavaScript removes the escape hatch instead of defining it. A let or const binding is created when the block is entered and stays uninitialized until its declaration is reached, so it shadows an outer declaration for the whole block; a read in that window throws a ReferenceError, which is the temporal dead zone. Because the binding exists from block entry, a let declaration with the same name in the same block is a static error even if the later declaration is never reached, a rule that a name-availability test at the use site would not produce.

Java takes a third position for class members: fields are visible throughout the class body regardless of textual order, so a method may refer to a field declared after it. A field initializer is more restricted: the language forbids a simple-name forward reference from an initializer to a field declared later in the same class, reporting it as an illegal forward reference. The restriction is not a scoping rule, since the name is in scope, but a separate constraint on the use, which is why a resolver that only records scope cannot enforce it and the checker needs the declaration order as an extra input.

C has no hoisting at file scope. A function must be declared before use, which is why headers exist and why a call to an undeclared function is an error rather than a forward reference. C’s struct case is the interesting one: a struct may contain a pointer to itself, but the tag must be declared before it is used in the member list, which is why the incomplete-type idiom works — struct node; declares the tag without a body, and struct node *next; refers to the incomplete type. Collection here inserts a tag binding with no members, and resolution accepts it only in positions where an incomplete type is legal, such as behind a pointer.

Collection for recursive and mutually recursive types

Types create a dependency graph that is not a tree, and the collection pass must record enough to detect illegal cycles.

An alias or typedef that refers back to itself without intervening indirection is a cycle: typedef T T; in C is a redefinition of T in terms of itself, and in Go the alias form type T = T resolves the T on the right against whatever T denoted before the declaration, so in isolation it is simply an undefined name rather than a new type. A struct containing a pointer to itself is legal because the cycle passes through a pointer, which is a fixed-size indirection. A struct containing itself by value is illegal because its size would be infinite. The distinction is structural, and it is decided after collection, during type checking, when each type’s definition is walked with a set of in-progress nodes.

The standard technique is to mark a type as being checked when its definition is entered and unmark it when it completes. Encountering a marked node again means a cycle; whether the cycle is legal depends on the edge that closed it. A pointer, a slice, a map, or a function type breaks the cycle because their sizes do not depend on the pointee’s size. C arrays are the interesting exception: an array of incomplete type is rejected because the element size is unknown, but an array of complete type whose length is written as a constant expression is complete as soon as that constant is evaluated, so recursion through an array element is rejected on the size grounds rather than deferred.

Collection’s role is to make the tag or name resolvable before the cycle is walked. Without a pre-pass, struct node { struct node *next; }; cannot be resolved by a single forward walk: the member list refers to the tag being defined. The pre-pass inserts the tag, the member walk resolves the pointer to it, and the size computation happens after the body is complete. The tag lives in its own namespace, which is why the same spelling can also name a variable; the layout consequences of that split are covered in Separate Namespaces and Overload Sets in a Symbol Table.

Generics make collection recursive

A generic declaration introduces type parameters whose scope is the declaration’s own signature and body. Collection must therefore push a frame for the type parameters before collecting the signature, because the signature mentions them.

Go’s type List[T any] struct { next *List[T] } needs T in scope to resolve the field type, and needs List in scope to resolve the self-reference. Both are collected before the body is walked. In languages where a declaration’s type parameters may themselves be constrained by other types in the same declaration group, the dependency can run in both directions, and collection must iterate until the frame is stable or report a cycle.

A class may refer to itself in its own members, and an inner class may refer to the enclosing class’s type parameters. That works because an inner (non-static) class is written inside the enclosing class body, where those parameters are already in scope: collection walks the enclosing chain when it builds the frame, so the inner frame has the outer parameters visible. A static nested class written at the same textual position needs its own parameters, because it has no enclosing instance. A compiler that collects each class in isolation resolves the inner references to nothing.

When collection cannot be complete

Some declarations cannot be collected without evaluating something. C++ templates are the clearest case: inside a class template, the members of the base class it derives from are not known until the template arguments are substituted, so the collector cannot insert them. The language requires the parser and the checker to treat such names as dependent and defer resolution, which is why typename and template disambiguators are sometimes needed in the source. A collection pass that assumed completeness would fail on any template that uses a dependent name.

Macros and conditional compilation produce the same effect from a different direction. A preprocessor can make a declaration appear or disappear, so the collector operates on the post-preprocessing token stream, not on the source text. A compiler that collects from the raw source will see declarations that the preprocessor removed.

Modules with cyclic imports raise the issue at a larger scale. Two modules that each import the other cannot be resolved in a single pass over one file; the compiler must build a dependency graph over modules, break the cycle at the declaration level, and resolve names in an order that respects the graph rather than the file order. This is why some languages forbid cyclic imports outright and others permit them with restrictions on what may be used at initialization time.

A collection pass in outline

The code below shows the essential shape for a language with function-level hoisting and block-level ordering, written in Go.

type Binding struct {
	Name     string
	Kind     Kind      // Var, Func, Type, Const
	Decl     Node      // for diagnostics
	DeclPos  int       // offset, for ordering diagnostics
	Frame    *Frame
}

func collect(f *Frame, nodes []Node) {
	for _, n := range nodes {
		switch n := n.(type) {
		case *VarDecl:
			f.Insert(&Binding{Name: n.Name, Kind: Var, Decl: n, DeclPos: n.Pos, Frame: f})
		case *FuncDecl:
			f.Insert(&Binding{Name: n.Name, Kind: Func, Decl: n, DeclPos: n.Pos, Frame: f})
		case *TypeDecl:
			f.Insert(&Binding{Name: n.Name, Kind: Type, Decl: n, DeclPos: n.Pos, Frame: f})
		case *Block:
			child := f.NewChild()
			collect(child, n.Stmts)   // recurse, do not resolve
		}
	}
}

func (f *Frame) Insert(b *Binding) {
	if prev, ok := f.names[b.Name]; ok && prev.Kind == b.Kind {
		f.Errf(b.Decl, "redeclaration of %s", b.Name)
		return
	}
	f.names[b.Name] = b
}

DeclPos is what makes the second pass able to enforce an ordering rule that lookup alone does not: a use of a binding whose DeclPos is greater than the use’s own offset, within the same frame, is a use at a point where the value is not yet available even though the lookup succeeded. The check applies wherever a language lets the binding be visible before its declaration, either because the spec puts the scope at block entry, as with JavaScript let, or because a rule other than scope restricts the forward reference, as with Java field initializers. Where the scope begins at the declarator, the lookup itself already fails and the position is redundant.

The invariant the two passes must preserve

Collection must be idempotent with respect to resolution: running collection twice must not duplicate bindings, and running resolution twice must produce the same edges. In practice the second property is the one that breaks, because resolution mutates the use nodes. A resolver that overwrites a resolved edge on a second pass will silently rebind names if the environment changed in between, which happens in any compiler that rechecks a function after an edit.

The guard is to make resolution refuse to overwrite an existing edge unless the tree was explicitly invalidated. That, plus the ordering check above, covers the failure modes that produce wrong code rather than a diagnostic. The remaining interactions — how captured bindings in nested functions are collected, and what a closure’s frame must contain — belong to Closure Capture, Scope, and Storage Duration.