proposal: go/types: TypeSet, an API for normalized interface terms

@griesemer

[See #61013 (comment) for the latest draft. --adonovan, Oct 22 2026.]

~~EDIT(2024-02-06): Please see the actual proposal in this comment below: #61013 (comment)~~

As discussed in #60994, there are some missing go/types APIs that are currently papered over with the x/exp/typeparams package.

In particular, we should propose a go/types API that serves the purpose of the NormalTerms function -- some way to traverse a normalized representation of the terms of an interface types.

We could expose an equivalent API to NormalTerms, or do something simpler. Let's decide early in the go1.22 cycle.

CC @griesemer @adonovan @timothy-king @mdempsky

Might be helpful to go over what x/tools/go/ssa uses. The heaviest usage of NormalTerms is indirect via x/tools/internal/typeparams.CoreType. If we only release NormalTerms, CoreType will be the performance sensitive path. Other uses of NormalTerm go through the function x/tools/go/ssa.typeSetOf. The use of this is somewhat varied. FWIW all uses only pay attention to the underlying types in the list.

This issue is currently labeled as early-in-cycle for Go 1.22.
That time is now, so a friendly reminder to look at it again.

Unfortunately, this isn't going to happen for 1.22, which is perhaps not unreasonable given #63940. Let's wait another cycle to see if the correct API emerges.

This issue is currently labeled as early-in-cycle for Go 1.23.
That time is now, so a friendly reminder to look at it again.

I still think we should do this, but it's been an unfortunately low priority as most users have access to terms via x/tools/internal or x/exp/typeparams.

Moving to the backlog, as it seems unlikely that we'll take this on before there is more demand. As mentioned above, #63940 is a higher priority for the team, and may affect the design of this API.

@timothy-king

@timothy-king as you are working on go/types and have a lot of experience with core types / normalized interface terms from your work on go/ssa, you seem like the perfect person to design a nice API here :)

Tentatively reassigning, though I will leave it to you to prioritize.

Change https://go.dev/cl/848487 mentions this issue: internal/typeparams: replace NormalTerms et al with TypeSetOf
So does https://go.dev/cl/851489 (Remove TypeSet. Empty).

This is the API we're currently aiming for:

package types

// A TypeSet is the type set of a type, represented as a normalized
// list of specific terms (types T or ~T). It is immutable.
//
// If [TypeSet.Unrestricted], the set is constrained only by methods,
// if at all (e.g. any, comparable, interface{ M() }), and has no terms.
// This is the zero value.
//
// Otherwise, the set is exactly the union of its [TypeSet.Len] disjoint
// terms. Zero terms denotes the empty set (e.g. interface{ int; string }).
//
// Terms are reported in a deterministic but otherwise unspecified order.
type TypeSet struct { ... }

// TypeSetOf returns the type set of t:
//
//   - For a type parameter, it is the type set of its constraint.
//   - For an interface or union type (or a named type whose underlying
//     type is an interface), it is the set implied by its embedded
//     non-interface types and unions, ignoring methods.
//   - For any other type t, it is {t}: a single non-tilde term holding t
//     as provided (including any alias).
//
// The specific terms are normalized: the type set is expressed as a single
// union containing no interface terms, minimal in the sense that removing
// any term changes the set. For example, given
//
//	type A interface{ ~string|~[]byte }
//	type B interface{ int|string }
//	type C interface{ ~string|~int }
//	type T[P interface{ A|B; C }] int
//
// the type set of P is ~string|int: A|B expands to
// ~string|~[]byte|int|string, which reduces to ~string|~[]byte|int,
// which when intersected with C (~string|~int) yields ~string|int.
//
// TypeSetOf never fails. If t is ill-formed (e.g. it has an invalid
// embedded type or cyclic declaration) or exceeds complexity bounds,
// the result is Unrestricted. This cannot happen in well-typed code,
// and for ill-typed code it is the conservative answer: "does every
// type in the set satisfy P?" yields false (whereas the empty set
// would vacuously yield true, licensing unsound transformations), and
// "does some type in the set satisfy P?" finds no witness (so no
// spurious diagnostic is reported).
//
// Performance notes (non-normative): the singleton case {t} allocates
// a [types.Term]; callers may avoid this by first checking
// !types.IsInterface(t), which holds exactly when the type set of t
// is {t}. (IsInterface reports true for type parameters.) Interfaces
// and type parameters allocate only if they have type terms.
func TypeSetOf(t Type) TypeSet

// Unrestricted reports whether the type set has no specific terms,
// for example any, comparable, or interface{ M() }.
// It also reports true for ill-formed types; see [TypeSetOf].
func (TypeSet) Unrestricted() bool

// Len returns the number of specific terms.
// Zero means either Unrestricted (all types) or empty (no types).
func (s TypeSet) Len() int { return len(s.terms) }

// Term returns the ith specific term.
// It panics unless 0 <= i < s.Len().
func (TypeSet) Term(i int) *Term

// Terms returns an iterator over the specific terms.
// It yields nothing if the set is Unrestricted or empty.
func (s TypeSet) Terms() iter.Seq[*Term]

// UnderlyingTypes returns an iterator over the underlying types of the
// specific terms. (For a term ~T, this is T itself.) It yields nothing
// if the set is Unrestricted or empty.
//
// Duplicates are not eliminated: for example, MyInt1|MyInt2
// yields int twice if both have underlying type int.
func (s TypeSet) UnderlyingTypes() iter.Seq[Type]

// String returns a representation of the type set for debugging:
// "𝓤" if unrestricted, "∅" if empty, or a union of terms.
func (s TypeSet) String() string

What's changed:

NewTypeSet is TypeSetOf, since a TypeSet is an immutable value type, not a variable denoted by a pointer.
The error has gone away. This makes all call sites more convenient.
Instead, the Unrestricted accessor can be used if needed, but it is not the common case.
There's a String method.
The UnderlyingTypes convenience iterator simplifies a lot of callers.

Navigation Menu

Repository navigation

proposal: go/types: TypeSet, an API for normalized interface terms #61013

20 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

proposal: go/types: TypeSet, an API for normalized interface terms #61013

Description

Activity

timothy-king commented on Jun 28, 2023

gopherbot commented on Jul 20, 2023

findleyr commented on Nov 7, 2023

gopherbot commented on Jan 22, 2024

findleyr commented on May 14, 2024

findleyr commented on Aug 6, 2024

20 remaining items

gopherbot commented on Oct 14, 2026

gopherbot commented on Oct 14, 2026

gopherbot commented on Oct 14, 2026

gopherbot commented on Oct 14, 2026

gopherbot commented on Oct 20, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions