proposal: reflect: allow creation of recursive types atomically

[TheCount]

Background and introduction

The proposal in #39528 has been criticised for the fact that it would introduce "incomplete" instances of reflect.Type. This alternative proposal addresses that shortcoming: here, newly created recursive reflect.Types can emerge only through a single function, reflect.Bind. This new function either returns a reflect.Type which can be used with the same expectations as any other reflect.Type, or it panics (hence, "atomically"). The remainder of the reflect API is not affected.

This convenience comes at the cost of building a partially parallel infrastructure to describe the type to be newly created. The central component is a new interface reflect.TypeDesc instances of which are immutable descriptions of a type (or type-to-be) and a number of functions for the construction of such descriptions.

Proposal

We provide the proposal in the form of go source code. For orientation, the following new objects parallel existing objects in the reflect package:

New	Existing
DescArray	Array
DescChan	Chan
DescFunc	Func
DescInterface	Interface
DescInvalid	Invalid
DescKind	Kind
DescMap	Map
DescPtr	Ptr
DescSlice	Slice
DescStruct	Struct
DescribeArray	ArrayOf
DescribeChan	ChanOf
DescribeFunc	FuncOf
DescribeMap	MapOf
DescribePtr	PtrTo
DescribeSlice	SliceOf
DescribeStruct	StructOf
MethodDesc	Method
StructFieldDesc	StructField
TypeDesc	Type

The following new objects have no parallel:

New
Bind
Complete
DescComplete
DescIncomplete
DescribeInterface
Incomplete

Proposal as go code:

// A DescKind represents the specific kind of type description that a TypeDesc
// represents. The zero DescKind is not a valid type description kind.
type DescKind uint

const (
	DescInvalid             = DescKind(Invalid)
	DescArray               = DescKind(Array)
	DescChan                = DescKind(Chan)
	DescFunc                = DescKind(Func)
	DescInterface           = DescKind(Interface)
	DescMap                 = DescKind(Map)
	DescPtr                 = DescKind(Ptr)
	DescSlice               = DescKind(Slice)
	DescStruct              = DescKind(Struct)
	DescIncomplete DescKind = (1 << 5) - 2
	DescComplete   DescKind = (1 << 5) - 1
)

// String returns the name of dk.
func (dk DescKind) String() string

// TypeDesc represents a description of a (possibly incomplete) type. A type
// description is a safe way to describe the layout of a (possibly recursive)
// type with the Complete, Incomplete, DescribeArray, DescribeChan,
// DescribeFunc, DescribeInterface, DescribeMap, DescribePtr, DescribeSlice,
// and DescribeStruct functions before the actual Type is created with Bind.
type TypeDesc interface {
	// ChanDir returns a channel description's direction.
	// It panics if the description kind is not DescChan.
	ChanDir() ChanDir

	// Elem returns the element type description for this type description.
	// It panics if the description kind is not DescArray, DescChan, DescMap,
	// DescPtr, or DescSlice.
	Elem() TypeDesc

	// Field returns a struct type description's i'th field description.
	// It panics if the description kind is not DescStruct.
	// It panics if i is not in the range [0, NumField()).
	Field(i int) StructFieldDesc

	// FieldByName returns the struct field description with the given name
	// and a boolean indicating if the field description was found.
	// It panics if the description kind if not DescStruct.
	FieldByName(name string) (StructFieldDesc, bool)

	// Key returns a map type description's key type description.
	// It panics if the description kind is not DescMap.
	Key() TypeDesc

	// Kind returns the specific description kind of this type description.
	Kind() DescKind

	// In returns the type description of a function type descriptions's i'th
	// input parameter.
	// It panics if the description kind is not DescFunc.
	// It panics if i is not in the range [0, NumIn()).
	In(i int) TypeDesc

	// IsVariadic reports whether a function type description's final input
	// parameter is a "..." parameter. If so, td.In(td.NumIn() - 1) returns the
	// parameter's implicit actual type description []T.
	//
	// For concreteness, if td describes func(x int, y ... float64), then
	//
	//	td.NumIn() == 2
	//	td.In(0) is a reflect.TypeDesc for "int"
	//	td.In(1) is a reflect.TypeDesc for "[]float64"
	//	td.IsVariadic() == true
	//
	// IsVariadic panics if the description kind is not DescFunc.
	IsVariadic() bool

	// Len returns the length property of an array description.
	// It panics if the description kind is not DescArray.
	Len() int

	// Method returns the i'th method description in the type description's
	// method description set.
	// It panics if the description kind is not DescInterface,
	// or if i is not in the range [0, NumMethod()).
	//
	// In particular, Method does not work on descriptions with kind DescStruct.
	// Method returns only method descriptions explicitly added with
	// DescribeInterface, not methods implicitly acquired through embedded fields.
	//
	// The returned method description describes the method signature, without a
	// receiver. The Func field is nil.
	//
	// There is no guarantee that the methods of the resulting type will have the
	// same sort order as in the description.
	Method(int) MethodDesc

	// MethodByName returns the method description for the method with that name
	// in the type descriptions's method description set and a boolean indicating
	// if the method was found.
	// It panics if the description kind is not DescInterface.
	//
	// The returned method description describes the method signature, without a
	// receiver. The Func field is nil.
	MethodByName(string) (MethodDesc, bool)

	// Name returns the name of the described type.
	// It panics if the description kind is not DescIncomplete.
	Name() string

	// NumField returns a struct type description's field description count.
	// It panics if the description kind is not DescStruct.
	NumField() int

	// NumIn returns a function type description's input parameter count.
	// It panics if the description type is not DescFunc.
	NumIn() int

	// NumMethod returns the number of method descriptions in the type
	// description's method set.
	// It panics if the description kind is not DescInterface.
	NumMethod() int

	// NumOut returns a function type description's output parameter count.
	// It panics if the description kind is not DescFunc.
	NumOut() int

	// PkgPath returns the designated package path in a description of an
	// incomplete type. It panics if the description kind is not DescIncomplete.
	PkgPath() string

	// Out returns the type description of a function type description's i'th
	// output parameter.
	// It panics if the description kind is not DescFunc.
	// It panics if i is not in the range [0, NumOut()).
	Out(i int) TypeDesc

	// Underlying returns the actual type underlying this type description.
	// It panics if the description kind is not DescComplete.
	Underlying() Type
}

// StructFieldDesc describes a struct field.
type StructFieldDesc struct {
	// Name is the field name. It must start with an uppercase letter.
	Name string

	// Type is the description of the field type.
	Type TypeDesc

	// Tag is the field tag string.
	Tag StructTag

	// Anonymous indicates whether or not this struct field description
	// describes an embedded field.
	Anonymous bool
}

// MethodDesc describes a method.
type MethodDesc struct {
	// Name is the method name. It must start with an uppercase letter.
	Name string

	// Type describes the method type.
	//
	// For interface descriptions, Type should describe the signature of the
	// method.
	//
	// For descriptions of incomplete types, Type should describe a function
	// whose first argument is the receiver.
	Type TypeDesc

	// Func is nil if this description describes an interface method.
	//
	// For descriptions of methods of incomplete types, Func is the method
	// implementation with receiver, arguments and return values in terms of
	// reflect.Value.
	// Methods for incomplete types are not implemented yet.
	Func func(recv Value, in []Value) []Value
}

// Incomplete creates a type description for an incomplete named type.
// It panics if name is not a valid identifier starting with an uppercase
// letter. The package name may be empty but it is recommended that each
// package use a unique string here (such as its fully qualified package name)
// to avoid naming clashes with other packages.
func Incomplete(pkgName, name string) TypeDesc

// Complete creates a description of the given already complete type.
func Complete(typ Type) TypeDesc

// DescribeArray creates a description of an array type with the given count and
// element type described by elem.
// It panics if elem's description kind is DescIncomplete.
func DescribeArray(count int, elem TypeDesc) TypeDesc

// DescribeChan creates a description of a channel type with the given
// direction and element type described by t.
//
// The gc runtime currently imposes a limit of 64 kB on channel element types.
// If t is not of description kind DescIncomplete and describes a type whose
// size is equal to or exceeds this limit, DescribeChan panics. If t describes
// an incomplete type, a later call to Bind will panic if the resulting type
// would violate this limit.
func DescribeChan(dir ChanDir, t TypeDesc) TypeDesc

// DescribeFunc creates a description of the function type with the argument
// and result types described by in and out.
//
// The variadic argument controls whether the description of a variadic function
// is returned. If variadic is true and in[len(in)-1] does not represent a
// slice (i. e., is either of description kind DescSlice, or DescComplete and
// describes a slice type), DescribeFunc panics.
func DescribeFunc(in, out []TypeDesc, variadic bool) TypeDesc

// DescribeInterface creates a description of the interface type with the
// methods described by methods.
func DescribeInterface(methods []MethodDesc) TypeDesc

// DescribeMap creates a description of the map type with key and
// element types described by key and elem, respectively.
// It panics if key's description kind is DescIncomplete.
//
// Map key types must be comparable (i. e., implement Go's == operator).
// DescribeMap does not perform this check, but a later call to Bind will
// panic if the resulting type would not be a valid key type.
func DescribeMap(key, elem TypeDesc) TypeDesc

// DescribePtr creates a description of the pointer type with element type
// described by t.
func DescribePtr(t TypeDesc) TypeDesc

// DescribeSlice creates a description of the slice type with element type
// described by t.
func DescribeSlice(t TypeDesc) TypeDesc

// DescribeStruct creates a description of the struct type with the fields
// described by fields.
func DescribeStruct(fields []StructFieldDesc) TypeDesc

// Bind creates a new type by binding the type name given by incomp to the type
// described by def.
//
// The methods argument must be nil. A later version may lift this restriction.
//
// It panics if the (package name, name) combination given incomp has been used
// to create a type with Bind before. This does not mean the name of the
// resulting type is unique as this restriction only applies to types created
// with Bind.
//
// It panics if the description kind of def is DescIncomplete, or if def
// indirectly references a description of an incomplete type other than incomp,
// or if a resulting type would be illegal for some reason (for example, a
// channel type whose element size would be too big, or a map key type not
// implementing Go's == operator).
func Bind(incomp, def TypeDesc, methods []Method) Type

Open questions

• The proposal above does not explicitly allow creation of interfaces with embedded interfaces. If deemed necessary, the DescribeInterface function can get an additional embedded []TypeDesc parameter. This would allow the creation of interfaces with unexported methods if the embedded interfaces have unexported methods.

[cosmos72]

I am continuing my implementation of #39528, and the incompleteness and mutability of the few reflect.Type created with the proposed new function Named is spreading to all kinds of types, through the functions ArrayOf ChanOf MapOf FuncOf SliceOf and StructOf. It starts looking like a major refactoring of reflect.Type methods.

So I welcome a different API that avoids this problem. Out of curiosity: is there a reason why you did not try to leverage go/types.Type API?

[TheCount]

Out of curiosity: is there a reason why you did not try to leverage go/types.Type API?

I briefly considered it but discarded the idea for the simple reason that I'm not terribly familiar with that API, which, at first sight, seemed unnecessarily complex to me. My interest in the reflect package comes from writing generic pieces of code, and while I might be wrong, I suspect it's similar for most users, so I tried to make the TypeDesc API as similar as possible to the familiar Type API. I understand that for people whose primary interest in reflect comes from parsing actual Go code, priorities might be different.

I'm not sure how important that actually is, but another aspect to consider might be the dependencies of the reflect package. I might be misinterpreting this, but it seems to me the implementers went to certain lengths to avoid pulling in "convenience" packages such as fmt. The biggest dependencies currently appear to be Unicode related. go/types with its own dependencies would significantly increase the size of reflect dependencies.

[ianlancetaylor]

The reflect package can't depend on go/types, because go/types depends on fmt and fmt depends on reflect. It would be quite awkward to rewrite go/types such that it does not depend on reflect in any way.

[rsc]

This is certainly a complex API to design.
I understand the need in a Go interpreter, but it's unclear that the benefit outweighs the very significant API cost.
We should keep thinking about whether there are ways to simplify the cost (API surface, complexity of implementation).

Maybe it would make sense to have a separate package with the same constructors as reflect but that operates only on these incomplete types:

package incomplete // import "reflect/incomplete"

type Type ...

func Complete(list []Type) []reflect.Type
func Of(reflect.Type) Type
func StructOf
PointerTo
ChanOf
MapOf
...

That would at least solve the "Desc everywhere" problem. I'm not sure how much that would end up being a second copy of reflect. And I'm not sure how methods get attached, if anyone wants to try to figure that out.

[cosmos72]

An external package that allows building recursive reflect.Types could in theory depend on go/types.

Then the most minimal API is probably:

package convert // import "reflect/convert"
import (
    "go/types"
    "reflect"
)
func ToGoType(reflect.Type) *types.Named
func ToReflect([]*types.Named) []reflect.Type

where for simplicity ToGoType only accepts named (i.e. defined) reflect.Types.

To be implementable, it probably also needs this constraints: ToReflect can only convert types.Type which satisfy one of the two conditions:

• either returned by a previous call of ToGoType - for symmetry and invertibility
• or has an underlying type that, when traversed recursively, contains only unnamed types (which are themselves traversed recursively), plus named types returned by a previous call of ToGoType, plus named types passed to the same call of ToReflect - the idea is: you can convert mutually recursive named types A and B by calling ToReflect([]*types.Named{A, B})

This would allow a user to collect the named reflect.Types he wants, convert them to *types.Named, build a new *types.Named (say X) from them with the go/types API - which supports creating new named types and recursive types - then convert such new named type X to a reflect.Type

Clearly, reflect/convert would need to access some a lot of internal features and types of reflect: I'd say at least rtype, arrayType, chanType, mapType, funcType, interfaceType, ptrType, sliceType and structType.

Such API could even (if it's implementable) create new interface types - something that reflect cannot do yet.

And it would not need the proposed reflect.Type.Underlying()

[cosmos72]

Update: or even

package convert // import "reflect/convert"
import (
    "go/types"
    "reflect"
)
func ToGoType(reflect.Type) types.Type
func ToReflect([]types.Type) []reflect.Type

[TheCount]

@rsc Separate package sounds good.

There would certainly be some overlap with existing reflect functionality. It seems unnatural exclude "incidentally" non-recursive types (maybe even unnamed types if there is a Complete API) from the new package, so the *Of functions of reflect would become redundant in the sense that the new API could be used to the same effect (the original *Of functions would still be easier to use for the quick creation of a non-recursive, unnamed type).

@cosmos72 your idea to leverage the go/types package sounds intriguing, especially given it comes with type checking facilities. I've never used it, though, and glancing at it, the API seems quite complex to me, and also not quite geared towards the kind of runtime type creation you'd want in reflect. For example, to create a named recursive type, you'd need a call to NewPackage, NewTypeName and NewNamed, and I don't know what would be sensible arguments for pos and path in a reflectesque context. Also, the type checker only works on an entire file set.

As for implementation complexity, I guess some stuff would probably have to be moved from reflect to some new reflect/internal package, in particular the lookup caches which reflect maintains in order to ensure that for two reflect.Types t1 and t2 we have t1 == t2 if and only if t1 and t2 are identical. The internal package would then be used by both reflect and the new package for incomplete types.

[cosmos72]

The idea to leverage go/types is useful to understand what's the absolute minimum API needed to create recursive reflect.Types atomically. It has the downside of involving go/types, which:

1. Has a verbose type creation API, slightly more complicated than strictly needed
2. Is a large package - it also contains a lot of type-checking features, which are not used in this case
3. Depends on fmt, which depends on reflect - the implementation of reflect/convert may become tricky, as it cannot depend on reflect

so that's the price to pay for the minimal API: offload the complexity to some other existing package, which does what's needed but also has other features (unused in this case)

Any other API which avoids go/types needs at least:

1. A two-step process to create named and/or recursive types
2. A whole series of functions ArrayOf ChanOf MapOf FuncOf PtrTo SliceOf StructOf to compose (possibly incomplete) types
3. Convenience methods to examine the contents of (possibly incomplete) types: Key Elem ChanDir Field In Out Variadic etc.

thus it cannot be much simpler than your proposal or @rsc one.

[nrwiersma]

Is it not possible to take a middle road, when we still have incomplete types, but only for a defined amount of time. Something like:

NamedOf(name Name, k Kind, m []Method, fn func(t Type) (underlying Type)) Type

This allows the incomplete type to only exist in the closure (as t) but it is an actual type of kind k and will panic if the underlying returned is not the same kind as k. It could be documented that functions like Elem on t would panic, and this no longer needs to be guarded. This seems simple enough to fit in the reflect package and does not cause any duplication of methods.

[rsc]

If you build on go/types you'd also have to build some kind of bridge between the types already built into the binary and the go/types API. Those are really meant to be separate. It doesn't make sense to cross-connect them just for reflection. Let's focus on non-go/types solutions.

Like @cosmos72 said above, it really does seem like the full API (as in #39717 (comment)) is needed, and we just want to get it as lightweight as possible.

Maybe someone would be interested to try to build the API sketched in that comment and see how well it works?