Type Construction and Cycle Detection

Summary

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 o...