The Go Blog
Type Construction and Cycle Detection
Go's static type system is a core reason the language is well-suited for production systems that demand robustness and reliability. When the Go compiler processes a package, it begins by parsing the source code—converting it into an abstract syntax tree (AST). That AST is then handed off to the Go type checker.
This post takes a close look at a part of the type checker that was significantly overhauled in Go 1.26. From a user's perspective, the change is invisible unless you happen to craft particularly arcane type definitions. The real purpose was to reduce edge cases and lay groundwork for future improvements—but it also exposes some genuinely interesting complexity hiding inside what most Go programmers take for granted.
So what does type checking actually do? It's a compile-time pass that eliminates entire classes of errors before your program ever runs. Specifically, the type checker verifies two things:
- Types appearing in the AST are valid—for example, a map's key type must be
comparable. - Operations on those types or their values are valid—for example, you can't add an
intto astring.
To do this, the type checker builds an internal representation for every type it encounters while traversing the AST. This process is informally called type construction.
As we'll see, despite Go's reputation for a simple type system, type construction hides some real complexity in certain corners of the language.
Type construction
Consider a straightforward pair of type declarations:
type T []U
type U *int
When the type checker encounters the declaration for T, the AST records a type definition
associating the name T with the type expression []U. Because T is a
defined type, the type checker represents it internally using a
Defined struct—a data structure that holds a pointer to the type described by the
expression on the right-hand side of the declaration. That pointer, called underlying,
is what the type checker uses to resolve a type's
underlying type.
Here's what the type checker's state looks like at this moment:
T is marked under construction (shown in yellow). The type expression []U hasn't
been evaluated yet (shown in black), so underlying is nil, indicated by an open arrow.
Evaluating []U causes the type checker to construct a Slice struct—the internal
representation for slice types. Like Defined, it holds a pointer to its element type.
Since U hasn't been resolved yet, that pointer is also nil:
The pattern should be coming into focus. To resolve the name U, the type checker locates
its declaration, sees that it too is a defined type, and constructs a separate Defined
for it. The right-hand side of U is the type expression *int, which becomes a
Pointer struct whose base type is int.
Evaluating int triggers something special: it resolves to a predeclared type, one that
was constructed before the type checker began walking the AST. There's nothing left to
build—the type checker simply points to the existing int type.
The state is now:
The Pointer type is marked complete (shown in green). Completeness means that a type's
internal data structure is fully populated and every type it references is also complete.
This matters because completeness is what makes deconstruction—inspecting the internals
of a type—safe and sound. An incomplete type can't be safely examined, because some of its
fields may still be unresolved.
In this case, the Pointer struct has a single base field pointing to int. Since
int has no fields to populate, it's vacuously complete, which in turn makes *int complete.
From here, the type checker unwinds the call stack. A complete *int allows U to complete,
which allows []U to complete, which allows T to complete. The result is a fully resolved
set of types:
The numbers show the completion order after Pointer. Note that the bottom type completes
first—type construction is inherently depth-first, because completing a type requires its
dependencies to be completed first.
Recursive types
That example was clean, but Go's type system also supports recursive types. A familiar case:
type Node struct {
next *Node
}
We can introduce recursion into our earlier example by replacing *int with *T:
type T []U
type U *T
Tracing through as before, the type checker reaches the evaluation of *T in this state:
The question now is what to do with the base type for *T. The type checker has already
seen T and created a Defined for it, but T is still under construction—its
underlying field is still nil.
The solution is to point the base type of *T directly at T, even though T is incomplete:
This works because the type checker can rely on T completing later. Once T finishes
construction and points to a complete type, the base field of *T will transitively
reference a complete type, making *T complete as well.
In the meantime, the type checker heads back up the stack:
When construction of T finishes at the top, the cycle closes, and all types in the loop
complete simultaneously:
In the non-recursive case, evaluating a type expression always returned a complete type—a convenient guarantee that meant the type checker could safely deconstruct any type returned from evaluation.
But in the example above, evaluating T returned an incomplete type.
Deconstructing it before it completes would be unsound. Recursive types break the assumption
that evaluation always yields something fully resolved.
Yet type checking requires deconstructing types constantly. Confirming that a map key is
comparable, for instance, means inspecting the underlying field. How does the type
checker handle incomplete types safely?
The key insight is that type construction only needs to refer to types—it doesn't need to deconstruct them. Completeness is a prerequisite for deconstruction, but not for construction itself. So construction is never blocked by an incomplete type.
That means the type checker can safely defer any checks that require deconstruction until after all types have been constructed and completed. Since only the timing of an error report changes—not whether it's reported—this deferral is entirely correct.
With that foundation in place, let's look at a more complex scenario involving values of incomplete types.
Recursive types and values
Go's array types carry their size as part of the type itself—a
constant baked into the type definition. Some built-in operations,
like unsafe.Sizeof and len, can produce constants when applied to
certain values or
expressions, which means they can legally appear as array
sizes. Crucially, the values passed to those functions can be of any type—including an
incomplete one. We call these incomplete values.
Consider this example:
type T [unsafe.Sizeof(T{})]int
Walking through the type checker as before, we arrive at a state like this:
To construct the Array, the type checker must calculate its size—and here, that means
determining the size of T itself from unsafe.Sizeof(T{}). Calculating the size of an
array type requires deconstruction: the type checker must look inside T to determine both
the array's length and the size of each element.
This is fundamentally different from the recursive pointer case. Here, constructing the
Array requires deconstructing T, which means the Array cannot complete until T
is complete. The loop trick no longer applies—these types cannot complete simultaneously.
The result is a deadlock:
Tcannot complete until theArraycompletes.- The
Arraycannot complete untilTcompletes. - Unlike the pointer case, they cannot complete simultaneously.
There's no valid resolution. So what does the type checker do?
Cycle detection
At its core, code like this fails because determining the size of T requires already knowing the size of T—a logical impossibility regardless of type checker implementation. This specific problem, where a type's size depends circularly on itself, belongs to a broader category known as cycle errors. These errors arise whenever Go constructs reference themselves in their own definitions. Consider type T T as another example from this category, though it fails for distinct reasons. The compiler's mechanism for identifying and flagging these circular dependencies during type checking is called cycle detection.
How does cycle detection handle type T [unsafe.Sizeof(T{})]int? The key lies in examining the inner T{} expression. Since T{} is a composite literal, the type checker recognizes its value as type T. However, because T hasn't been fully defined yet, we classify T{} as an incomplete value.
Caution is essential here—operations on incomplete values are only valid when they don't require examining the value's underlying type structure. Consider type T [unsafe.Sizeof(new(T))]int, which is valid. The expression new(T) produces a value of type *T that's never deconstructed—pointer sizes are uniform regardless of what they point to. Put simply: sizing an incomplete value of type *T works fine, but sizing one of type T directly does not.
The distinction exists because the pointer nature of *T supplies sufficient type information for unsafe.Sizeof, while bare T doesn't. In general, operating on an incomplete value whose type is a defined type is never safe, since a type name alone provides no information about its underlying structure.
Where to do it
So far we've examined unsafe.Sizeof operating directly on potentially incomplete values. In type T [unsafe.Sizeof(T{})]int, the unsafe.Sizeof call forms the "root" of the array length expression. But we can easily envision the incomplete value T{} appearing as an operand within more complex expressions.
It might be passed to a function (type T [unsafe.Sizeof(f(T{}))]int), sliced (type T [unsafe.Sizeof(T{}[:])]int), or indexed (type T [unsafe.Sizeof(T{}[0])]int). All these cases are invalid because they require deconstructing T. Indexing T, for instance, requires verifying its underlying type. Since these expressions "consume" potentially incomplete values, we'll call them downstreams. Many more downstream operators exist, some less syntactically obvious than others.
Likewise, T{} represents just one expression that "produces" a potentially incomplete value—we'll call these upstreams:
By comparison, fewer value expressions can yield incomplete values, and they're more syntactically apparent. Enumerating these cases by examining Go's syntax definition is straightforward. This makes implementing cycle detection logic via upstreams—where potentially incomplete values originate—the simpler approach. Here are some upstream examples:
type T [unsafe.Sizeof(T(42))]int // conversion
func f() T
type T [unsafe.Sizeof(f())]int // function call
var i interface{}
type T [unsafe.Sizeof(i.(T))]int // assertion
type T [unsafe.Sizeof(<-(make(<-chan T)))]int // channel receive
type T [unsafe.Sizeof(make(map[int]T)[42])]int // map access
type T [unsafe.Sizeof(*new(T))]int // dereference
// ... and several more
For each case, the type checker includes specialized logic where that particular value expression gets evaluated. Once we determine the resulting value's type, we insert a straightforward test verifying the type is complete.
In the conversion example type T [unsafe.Sizeof(T(42))]int, the type checker contains logic resembling:
func callExpr(call *syntax.CallExpr) operand {
x := typeOrValue(call.Fun)
switch x.mode() {
// ... other cases
case typeExpr:
// T(), meaning it's a conversion
T := x.typ()
// ... handle the conversion, T *is not* safe to deconstruct
}
}
Once we identify the CallExpr as a conversion to T, we know the resulting type will be T (barring earlier errors). Before returning a value (an operand) of type T to the rest of the type checker, we must verify T's completeness:
func callExpr(call *syntax.CallExpr) operand {
x := typeOrValue(call.Fun)
switch x.mode() {
// ... other cases
case typeExpr:
// T(), meaning it's a conversion
T := x.typ()
+ if !isComplete(T) {
+ reportCycleErr(T)
+ return invalid
+ }
// ... handle the conversion, T *is* safe to deconstruct
}
}
Rather than returning an incomplete value, we return a special invalid operand signaling the call expression couldn't be evaluated. The type checker has dedicated handling for invalid operands. This addition prevents incomplete values from "escaping" downstream—both into the remaining type conversion logic and to downstream operators—while reporting a cycle error describing the issue with T.
Similar code patterns appear in all other cases, implementing cycle detection for incomplete values throughout the type checker.
Conclusion
Systematic cycle detection for incomplete values is a recent addition to the type checker. Prior to Go 1.26, a more complex type construction algorithm relied on specialized cycle detection that didn't always function correctly. This new, streamlined approach resolved numerous (admittedly obscure) compiler panics (issues #75918, #76383, #76384, #76478, and others), producing a more robust compiler.
As developers, we've grown accustomed to features like recursive type definitions and sized array types, potentially overlooking the nuanced complexity beneath them. While this discussion omits some finer implementation details, it should provide deeper insight into—and perhaps greater appreciation for—the challenges inherent in Go's type checking system.
