Type Construction and Cycle Detection - The Go Programming Language

Skip to Main Content

Why Go arrow_drop_down

Press Enter to activate/deactivate dropdown

Case Studies

Common problems companies solve with Go

Use Cases

Stories about how and why companies use Go

Security

How Go can help keep you secure by default

Learn

Press Enter to activate/deactivate dropdown

Docs arrow_drop_down

Press Enter to activate/deactivate dropdown

Go Spec

The official Go language specification

Go User Manual

A complete introduction to building software with Go

Standard library

Reference documentation for Go's standard library

Release Notes

Learn what's new in each Go release

Effective Go

Tips for writing clear, performant, and idiomatic Go code

Packages

Press Enter to activate/deactivate dropdown

Community arrow_drop_down

Press Enter to activate/deactivate dropdown

Recorded Talks

Videos from prior events

Meetups
open_in_new

Meet other local Go developers

Conferences
open_in_new

Learn and network with Go developers from around the world

Go blog

The Go project's official blog.

Go project

Get help and stay informed from Go

Get connected

Why Go navigate_next

navigate_beforeWhy Go

Case Studies

Use Cases

Security

Learn

Docs navigate_next

navigate_beforeDocs

Go Spec

Go User Manual

Standard library

Release Notes

Effective Go

Packages

Community navigate_next

navigate_beforeCommunity

Recorded Talks

Meetups
open_in_new

Conferences
open_in_new

Go blog

Go project

Get connected

The Go Blog
Type Construction and Cycle Detection

Mark Freeman
24 March 2026

Go’s static typing is an important part of why Go is a good fit for production
systems that have to be robust and reliable. When a Go package is compiled, it
is first parsed—meaning that the Go source code within that package is converted
into an abstract syntax tree (or AST). This AST is then passed to the Go
type checker.
In this blog post, we’ll dive into a part of the type checker we significantly
improved in Go 1.26. How does this change things from a Go user’s perspective?
Unless one is fond of arcane type definitions, there’s no observable change
here. This refinement was intended to reduce corner cases, setting us up for
future improvements to Go. Also, it’s a fun look at something that seems quite
ordinary to Go programmers, but has some real subtleties hiding within.
But first, what exactly is type checking? It’s a step in the Go compiler that
eliminates whole classes of errors at compile time. Specifically, the Go type
checker verifies that:

Types appearing in the AST are valid (for example, a map’s key type must be
comparable).
Operations involving those types (or their values) are valid (for example,
one can’t add an int and a string).

To accomplish this, the type checker constructs an internal representation for
each type it encounters while traversing the AST—a process informally called
type construction.
As we’ll soon see, even though Go is known for its simple type system, type
construction can be deceptively complex in certain corners of the language.
Type construction
Let’s start by considering a simple pair of type declarations:
type T []U
type U *int

When the type checker is invoked, it first encounters the type declaration for
T. Here, the AST records a type definition of a type name T and a
type expression []U. T is a defined type; to represent
the actual data structure that the type checker uses when constructing defined
types, we’ll use a Defined struct.
The Defined struct contains a pointer to the type for the type expression to
the right of the type name. This underlying field is relevant for sourcing the
type’s underlying type. To help illustrate the
type checker’s state, let’s see how walking the AST fills in the data
structures, starting with:

At this point, T is under construction, indicated by the color yellow. Since
we haven’t evaluated the type expression []U yet—it’s still black—underlying
points to nil, indicated by an open arrow.
When we evaluate []U, the type checker constructs a Slice struct, the
internal data structure used to represent slice types. Similarly to Defined,
it contains a pointer to the element type for the slice. We don’t yet know what
the name U refers to, though we expect it to refer to a type. So, again, this
pointer is nil. We are left with:

By now you might be getting the gist, so we’ll pick up the pace a bit.
To convert the type name U to a type, we first locate its declaration. Upon
seeing that it represents another defined type, we construct a separate
Defined for U accordingly. Inspecting the right side of U, we see the type
expression *int, which evaluates to a Pointer struct, with the base type of
the pointer being the type expression int.
When we evaluate int, something special happens: we get back a predeclared
type. Predeclared types are constructed before the type checker even begins
walking the AST. Since the type for int is already constructed, there’s
nothing for us to do but point to that type.
We now have:

Note that the Pointer type is complete at this point, indicated by the color
green. Completeness means that the type’s internal data structure has all of its
fields populated and any types pointed to by those fields are complete.
Completeness is an important property of a type because it ensures that
accessing the internals, or deconstruction, of that type is sound: we have all
the information describing the type.
In the image above, the Pointer struct only contains a base field, which
points to int. Since int has no fields to populate, it’s “vacuously”
complete, making the type for *int complete.
From here, the type checker begins unwinding the stack. Since the type for
*int is complete, we can complete the type for U, meaning we can complete
the type for []U, and so on for T. When this process ends, we are left with
only complete types, as shown below:

The numbering above shows the order in which the types were completed (after the
Pointer). Note that the type on the bottom completed first. Type construction
is naturally a depth-first process, since completing a type requires its
dependencies to be completed first.
Recursive types
With this simple example out of the way, let’s add a bit more nuance. Go’s type
system also allows us to express recursive types. A typical example is something
like:
type Node struct {
next *Node
}

If we reconsider our example from above, we can add a bit of recursion by
swapping *int for *T like so:
type T []U
type U *T

Now for a trace: let’s start once more with T, but skip ahead to illustrate
the effects of this change. As one might suspect from our previous example, the
type checker will approach the evaluation of *T with the below state:

The question is what to do with the base type for *T. We have an idea of what
T is (a Defined), but it’s currently being constructed (its underlying is
still nil).
We simply point the base type for *T to T, even though T is incomplete:

We do this assuming that T will complete when it finishes construction
in the future (by pointing to a complete type). When that happens, base will
point to a complete type, thus making *T complete.
In the meantime, we’ll begin heading back up the stack:

When we get back to the top and finish constructing T, the “loop” of types
will close, completing each type in the loop simultaneously:

Before we considered recursive types, evaluating a type expression always
returned a complete type. That was a convenient property because it meant the
type checker could always deconstruct (look inside) a type returned from
evaluation.
But in the example above, evaluation of T returned an incomplete
type, meaning deconstructing T is unsound until it completes. Generally
speaking, recursive types mean that the type checker can no longer assume that
types returned from evaluation will be complete.
Yet, type checking involves many checks which require deconstructing a type. A
classic example is confirming that a map key is comparable, which requires
inspecting the underlying field. How do we safely interact with incomplete
types like T?
Recall that type completeness is a prerequisite for deconstructing a type. In
this case, type construction never deconstructs a type, it merely refers to
types. In other words, type completeness does not block type construction
here.
Because type construction isn’t blocked, the type checker can simply delay such
checks until the end of type checking, when all types are complete (note that
the checks themselves also do not block type construction). If a type were to
reveal a type error, it makes no difference when that error is reported during
type checking—only that it is reported eventually.
With this knowledge in mind, let’s examine a more complex example involving
values of incomplete types.
Recursive types and values
Let’s take a brief detour and have a look at Go’s
array types. Importantly, array types have a size,
which is a constant that is part of the type. Some
operations, like the built-in functions unsafe.Sizeof and len can return
constants when applied to certain values or
expressions, meaning they can appear as array
sizes. Importantly, the values passed to those functions can be of any type,
even an incomplete type. We call these incomplete values.
Let’s consider this example:
type T [unsafe.Sizeof(T{})]int

In the same way as before, we’ll reach a state like the below:

To construct the Array, we must calculate its size. From the value expression
unsafe.Sizeof(T{}), that’s the size of T. For array types (such as T),
calculating their size requires deconstruction: we need to look inside the type
to determine the length of the array and size of each element.
In other words, type construction for the Array does deconstruct T,
meaning the Array cannot finish construction (let alone complete) before T
completes. The “loop” trick that we used earlier—where a loop of types
simultaneously completes as the type starting the loop finishes
construction—doesn’t work here.
This leaves us in a bind:

T cannot be completed until the Array completes.
The Array cannot be completed until T completes.
They cannot be completed simultaneously (unlike before).

Clearly, this is impossible to satisfy. What is the type checker to do?
Cycle detection
Fundamentally, code such as this is invalid because the size of T cannot be
determined without knowing the size of T, regardless of how the type checker
operates. This particular instance—cyclic size definition—is part of a class of
errors called cycle errors, which generally involve cyclic definition of Go
constructs. As another example, consider type T T, which is also in this
class, but for different reasons. The process of finding and reporting cycle
errors in the course of type checking is called cycle detection.
Now, how does cycle detection work for type T [unsafe.Sizeof(T{})]int? To
answer this, let’s look at the inner T{}. Because T{} is a composite literal
expression, the type checker knows that its resulting value is of type T.
Because T is incomplete, we call the value T{} an incomplete value.
We must be cautious—operating on an incomplete value is only sound if it doesn’t
deconstruct the value’s type. For example, type T [unsafe.Sizeof(new(T))]int
is sound, since the value new(T) (of type *T) is never deconstructed—all
pointers have the same size. To reiterate, it is sound to size an incomplete
value of type *T, but not one of type T.
This is because the “pointerness” of *T provides enough type information for
unsafe.Sizeof, whereas just T does not. In fact, it’s never sound to operate
on an incomplete value whose type is a defined type, because a mere type name
conveys no (underlying) type information at all.
Where to do it
Up to now we’ve focused on unsafe.Sizeof directly operating on potentially
incomplete values. In type T [unsafe.Sizeof(T{})], the call to unsafe.Sizeof
is just the “root” of the array length expression. We can readily imagine the
incomplete value T{} as an operand in some other value expression.
For example, it could be passed to a function (i.e.
type T [unsafe.Sizeof(f(T{}))]int), sliced (i.e.
type T [unsafe.Sizeof(T{}[:])]int), indexed (i.e.
type T [unsafe.Sizeof(T{}[0])]int), etc. All of these are invalid because they
require deconstructing T. For instance, indexing T
requires checking the underlying type of T.
Because these expressions “consume” potentially incomplete values, let’s call
them downstreams. There are many more examples of downstream operators, some
of which are not syntactically obvious.
Similarly, T{} is just one example of an expression that “produces” a
potentially incomplete value—let’s call these kinds of expressions upstreams:

Comparatively, there are fewer and more syntactically obvious value expressions
that might result in incomplete values. Also, it’s rather simple to enumerate
these cases by inspecting Go’s syntax definition. For these reasons, it’ll be
simpler to implement our cycle detection logic via the upstreams, where
potentially incomplete values originate. Below are some examples of them:

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 a handful more

For each of these cases, the type checker has extra logic where that particular
kind of value expression is evaluated. As soon as we know the type of the
resulting value, we insert a simple test that checks that the type is complete.
For instance, in the conversion example type T [unsafe.Sizeof(T(42))]int,
there is a snippet in the type checker that resembles:
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
}
}

As soon as we observe that the CallExpr is a conversion to T, we know that
the resulting type will be T (assuming no preceding errors). Before we pass
back a value (here, an operand) of type T to the rest of the type checker,
we need to check for completeness of T:
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
}
}

Instead of returning an incomplete value, we return a special invalid operand,
which signals that the call expression could not be evaluated. The rest of the
type checker has special handling for invalid operands. By adding this, we
prevented incomplete values from “escaping” downstream—both into the rest of the
type conversion logic and to downstream operators—and instead reported a cycle
error describing the problem with T.
A similar code pattern is used in all other cases, implementing cycle detection
for incomplete values.
Conclusion
Systematic cycle detection involving incomplete values is a new addition to the
type checker. Before Go 1.26, we used a more complex type construction algorithm,
which involved more bespoke cycle detection that didn’t always work. Our new,
simpler approach addressed a number of (admittedly esoteric) compiler panics
(issues #75918, #76383,
#76384, #76478, and more), resulting in a more
stable compiler.
As programmers, we’ve become accustomed to features like recursive type
definitions and sized array types such that we might overlook the nuance of
their underlying complexity. While this post does skip over some finer details,
hopefully we’ve conveyed a deeper understanding of (and perhaps appreciation
for) the problems surrounding type checking in Go.

Previous article: //go:fix inline and the source-level inliner
Blog Index

Why Go

Use Cases

Case Studies

Get Started

Playground

Tour

Stack Overflow

Help

Packages

Standard Library

About Go Packages

About

Download

Blog

Issue Tracker

Release Notes

Brand Guidelines

Code of Conduct

Connect

Bluesky

Mastodon

Twitter

GitHub

Slack

r/golang

Meetup

Golang Weekly

Opens in new window.

Copyright

Terms of Service

Privacy Policy

Report an Issue

go.dev uses cookies from Google to deliver and enhance the quality of its services and to
analyze traffic. Learn more.
Okay

Type Construction and Cycle Detection – The Go Programming Language

Mark Freeman, 24 March 2026

Go’s static typing plays a crucial role in creating robust and reliable production systems, and the type checker is a key component of this. When a Go package is compiled, the source code is first parsed into an abstract syntax tree (AST). This AST then passes through the Go type checker, which verifies type validity and operations. This blog post delves into a significant improvement within the Go type checker, specifically addressing cycle detection, highlighting its impact on Go users while offering an insight into the underlying intricacies. The primary goal of this internal refinement was to mitigate corner cases and set the stage for future enhancements to Go’s type system, presenting a detailed, thorough, and complex explanation of the process.

The core function of the type checker is to eliminate errors at compile time by verifying type compatibility and ensuring the validity of operations. This is achieved through “type construction,” an internal representation process where the type checker analyzes the AST and creates an internal representation for each encountered type. This process isn’t immediately visible to the programmer, but it’s the foundational step in determining the correctness of the code.

Type construction involves traversing the AST to identify and represent types. Let's breakdown the process with a simple example: defining type `T` as `[]U` and type `U` as `*int`. The type checker constructs an internal representation for each, building up a hierarchy of type information. Each type is represented internally by a `Defined` struct which contains a pointer to the type expression to the right of the type name.

The process involves a depth-first traversal of the AST, creating type structures. Completeness is a critical property – a complete type signifies that its internal data structures are fully populated, insuring that operations on that type are sound. A complete type has all fields populated and any internally referenced types are themselves complete.

A more complex scenario arises with recursive types, like `Node` defined as `struct { next *Node }`. Building a recursive type requires careful attention to how types are constructed and linked. The type checker needs to anticipate and handle the cyclical nature of these definitions to prevent infinite loops of type construction. Cycle detection involves identifying situations where a type references itself or a circular dependency of types, halting the construction process to avoid an infinite recursion and a crash.

The key insight is that type completeness is not automatically achieved. The type checker must proactively verify that types are truly complete before attempting to deconstruct them – before operating on a type in a way that requires examining its internal structure. This is handled through techniques like cycle detection.

The cycle detection mechanism specifically targets scenarios where an incomplete type is used in a way that requires knowing its definitive type. This typically manifests when an operation attempts to deconstruct a partially constructed type, triggering a potential error. The type checker proactively checks for this situation, reporting a cycle error if detected, preventing more serious issues during runtime. These checks were implemented through several upstream expressions, offering a comprehensive approach to ensure consistency and security.

This improved approach dramatically reduced corner cases and enhances the stability of the Go compiler. The blog post highlights an often-overlooked aspect of Go’s type system—the meticulous work performed behind the scenes to ensure type safety and reliability. It provides a clear and detailed explanation of the logic behind the refinements.