Repository: go
Issue: proposal: reflect: allow creation of recursive types atomically
Labels: Proposal,Proposal-Hold

### 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.Type`s 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:

```go
// 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.