go

go copied to clipboard

Proposal Details

Background

There are various algorithms that are not easy to write in Go with generics because they are naturally expressed using an unknown number of type parameters. For example, the metrics package suggested in the generics proposal document is forced to define types, Metric1, Metric2, and so forth, based on the number of different fields required for the metric. For a different example, the iterator adapter proposal (https://go.dev/issue/61898) proposes two-element variants of most functions, such as Filter2, Concat2, Equal2, and so forth.

Languages like C++ use variadic templates to avoid this requirement. C++ has powerful facilities to, in effect, loop over the variadic type arguments. We do not propose introducing such facilities into Go, as that leads to template metaprogramming, which we do not want to support. In this proposal, Go variadic type parameters can only be used in limited ways.

Proposal

A generic type or function declaration is permitted to use a ... following the last type parameter of a type parameter list (as in T... for a type parameter T) to indicate that an instantiation may use zero or more trailing type arguments. We use T... constraint rather than T ...constraint (that is, gofmt will put the space after the ..., not before) because T is a list of types. It's not quite like a variadic function, in which the final argument is effectively a slice. Here T is a list, not a slice.

We permit an optional pair of integers after the ... to indicate the minimum and maximum number of type arguments permitted. If the maximum is 0, there is no upper limit. Omitting the numbers is the same as listing 0 0.

(We will permit implementations to restrict the maximum number of type arguments permitted. Implementations must support at least 255 type arguments. This is a limit on the number of types that are passed as type arguments, so 255 is very generous for readable code.)

type Metric[V... 1 0 comparable] /* type definition */
func Filter[K any, V... 0 1 any] /* function signature and body */
func Filter[K, V... 0 1 any]     /* same effect as previous line */

With this notation V becomes a variadic type parameter.

A variadic type parameter is a list of types. In general a variadic type parameter may be used wherever a list of types is permitted:

• In a function parameter or result list
  • func SliceOf[T... any](v T) []any
  • a variadic type parameter may not be used as the type of a regular variadic parameter
• In a variable declaration, to define a variadic variable.
  • func PrintZeroes[T... any]() { var z T; fmt.Println(z) }
• In a struct declaration, to define a variadic field.
  • type Keys[T... any] struct { keys T }

A variadic variable or field may be used wherever a list of values is permitted.

• When calling a function, either a conventional variadic function or a function with a parameter whose type is itself a corresponding variadic type parameter with compatible min/max values and constraints.
• In a struct composite literal, setting a variadic field with corresponding type.
• In a slice composite literal where the constraint of the variadic type parameter is assignable to the element type of the slice.
• Similarly, in an array composite literal, if it uses the [...]T syntax (here T is an ordinary type or type parameter, not a variadic type parameter).
• On the left hand side of a for/range statement, if the variadic type parameter is constrained to ensure that at most two variables are present.

Note that a variadic type parameter with a minimum of 0 may be used with no type arguments at all, in which case a variadic variable or field of that type parameter will wind up being an empty list with no values.

Note that in an instantiation of any generic function that uses a variadic type parameter, the number of type arguments is known, as are the exact type arguments themselves.

// Key is a key for a metric: a list of values.
type Key[T... 1 0 comparable] struct {
	keys T
}

// Metric accumulates metrics, where each metric is a set of values.
type Metric[T... 1 0 comparable] struct {
	mu sync.Mutex
	m map[Key[T]]int
}

// Add adds an instance of a value.
func (m *Metric[T]) Add(v T) {
	m.mu.Lock()
	defer m.mu.Unlock()
	if m.m == nil {
		m.m = make(map[Key[T]]int)
	}
	// Here we are using v, of type T,
	// in a composite literal of type Key[T].
	// This works because the only field of Key[T]
	// has type T. This is ordinary assignment
	// of a value of type T to a field of type T,
	// where the value and field are both a list.
	m.m[Key[T]{v}]++
}

// Log prints out all the accumulated values.
func (m *Metric[T]) Log() {
	m.mu.Lock()
	defer m.mu.Unlock()
	for k, v := range m.m {
		// We can just log the keys directly.
		// This passes the struct to fmt.Printf.
		fmt.Printf("%v: %d\n", k, v)

		// Or we can call fmt.Println with a variable number
		// of arguments, passing all the keys individually.
		fmt.Println(k.keys, ":", v)

		// Or we can use a slice composite literal.
		// Here the slice has zero or more elements,
		// as many as the number of type arguments to T.
		keys := []any{k.keys}
		fmt.Printf("%v: %d\n", keys, v)
	}
}

// m is an example of a metric with a pair of keys.
var m = Metric[string, int]{}

func F(s string, i int) {
	m.Add(s, i)
}

Variadic type parameters can be used with iterators.

// Seq is an iterator: a function that takes a yield function and
// calls yield with a sequence of values. We always require one
// value K, and there can be zero or more other values V.
// (This could also be written as Seq[K, V... 0 1 any].)
type Seq[K any, V... 0 1 any] = func(yield func(K, V) bool)

// Filter is an iterator that filters a sequence using a function.
// When Filter is instantiated with a single type argument A,
// the f argument must have type func(A) bool,
// and the type of seq is func(yield func(A) bool).
// When Filter is instantiated with two type arguments A1, A2,
// the f argument must have type func(A1, A2) bool,
// and the type of seq is func(yield func(A1, A2) bool).
func Filter[K, V... 0 1 any](f func(K, V) bool, seq Seq[K, V]) Seq[K, V] {
	return func(yield func(K, V) bool) {
		// This is range over a function.
		// This is permitted as the maximum for V is 1,
		// so the range will yield 1 or 2 values.
		// The seg argument is declared with V,
		// so it matches the number on the left.
		for k, v := range seq {
			if f(k, v) {
				if !yield(k, v) {
					return
				}
			}
		}
	}
}

In a struct type that uses a variadic field, as in struct { f T } where T is a variadic type parameter, the field must have a name. Embedding a variadic type parameter is not permitted. The reflect.Type information for an instantiated struct will use integer suffixes for the field names, producing f0, f1, and so forth. Direct references to these fields in Go code are not permitted, but the reflect package needs to have a field name. A type that uses a potentially conflicting field, such as struct { f0 int; f T } or even struct { f1000 int; f T }, is invalid.

Constraining the number of type arguments

The Filter example shows why we permit specifying the maximum number of type arguments. If we didn't do that, we wouldn't know whether the range clause was permitted, as range can return at most two values. We don't want to permit adding a range clause to a generic function to break existing calls, so the range clause can only be used if the maximum number of type arguments permits.

The minimum number is set mainly because we have to permit setting the minimum number.

Another approach would be to permit range over a function that takes a yield function with an arbitrary number of arguments, and for that case alone to permit range to return more than two values. Then Filter would work as written without need to specify a maximum number of type arguments.

Work required

If this proposal is accepted, at least the following things would have to be done.

• Spec changes
• Changes to the go/ast package
  • We would permit an Ellipsis in the constraint of the last type parameter.
  • This should have a separate sub-proposal.
• Type checker changes
  • Possible changes to the go/types API, a separate sub-proposal.
• Tools would need to adjust.
• go/ssa changes
• gopls changes
• Communication with other tool builders
• Analyzer changes
• gofmt adjustments (minor)
• Compiler backend changes
  • The shape of a function with a variadic type parameter would have to consider the number of type arguments.
  • Changes to the importer and exporter

Aside from the addition of constraints on the count of type parameters, this seems to be a more precise statement of #56462, for some additional background. (cc @DeedleFake)

Presumably func F[T... 2 1 any]() is illegal. What about func G[T... 1 1 any]()? If that's legal, it feels awkward for it to have a substantially different meaning from func H[T... 0 0 any]().

@zephyrtronium Thanks, I entirely forgot about #56462.

func G[T... 1 1 any]() requires a single type argument (which is valid but useless). func H[T... 0 0 any]() permits any number of type arguments. I'm not sure I see the awkwardness.

If there were tuple types that looks like it would satisfy the MetricN case and simplify variadic fields/values since you could just wrap any type list in a tuple and not have to define additional machinery.

It seems unfortunate to be limited to a single variadic type as that means you couldn't write, for example, a decorator for any function

Would a [V 0..1 any] and [V 0.. any] syntax look clearer? What about [V 0:1 any] and [V 0: any]?

Another question:

func F[T... any](T) {
    F(T, T) // legal?
}

@Merovius Presumably the rules would need to be tightened to not allow calls that generate infinite shapes. The following could also generate an infinite series of func shapes.

func rec[T... 0 0 any](v func(T)) {
   var f func(int, T)
   rec(f)
}
var _ = rec(func(){})

Though the word "compatible" might be doing some heavy lifting to disallow these example.

@jimmyfrasche A major goal here is to avoid requiring both Filter and Filter2 in #61898. I don't think a tuple type addresses that.

@Merovius I think that is already prohibited by the rule saying that a generic function may only refer to itself using identical type parameters.

@ianlancetaylor I meant that if you also had tuples you could offload the handling of values of type-vectors onto them. However it occurs to me you'd still need some mechanism for writing out the parameters to a closure.

Variadic type parameters as types of struct fields are significantly more complex to use than those representing variable-length arguments of functions. I suggest initially restricting their use to being available only as function arguments. Even so, it should help to reduce many types, such as Seq2.

EDIT: Is this insufficient?

type StringInt struct { s string; i int }

var m = metrics.Metric[StringInt]{}

func F(s string, i int) {
	m.Add(StringInt{s, i})
}

We should consider #12854 if we want to reduce StringInt.

// With type inferred composite literals:
var m = metrics.Metric[struct{s string; i int}]{}

func F(s string, i int) {
	m.Add({s, i})
}

If it is used as a struct field, what type should it be, tuple? Or some other unknown type?

type Seq[K any, V... 0 1 any] = func(yield func(K, V) bool)

in addition, why isn't this the case here? @ianlancetaylor

type Seq[E... 1 2 any] = func(yield func(E) bool)

I think there's a typo in the Log function example:

	defer [m.mu.Unlock()](about:blank)

@ianlancetaylor I can't find that rule in the spec? I can find one for generic types, but nothing equivalent for functions.

What does PrintZeroes[]() do?

@leaxoy

If it is used as a struct field, what type should it be, tuple? Or some other unknown type?

If a struct field has a variadic type, then it is actually a list of struct fields. The types of the listed fields are the list of type arguments.

@johanbrandhorst Thanks, fixed. Not sure how that happened.

@Merovius Apologies, I'm probably misremembering it. But it seems to me that we need that rule. Otherwise we can write

func F[T any]() string {
    var v T
    s := fmt.Sprintf("%T", v)
    if len(s) >= 1000 {
        return s
    }
    return F[struct{f T}]()
}

And indeed that currently fails to compile:

foo.go:11:8: instantiation cycle:
	foo.go:17:14: T instantiated as struct{f T}

@aarzilli

What does PrintZeroes do?

The same thing as fmt.Println(). That is, it does not pass any arguments.

The types of the listed fields are the list of type arguments.

Is this list mutable? Does it support iterate and subscript access?

There is a scenario where variable generics are used as function parameters and are expected to be accessible through subscript.

@aarzilli

What does PrintZeroes do?

The same thing as fmt.Println(). That is, it does not pass any arguments.

I'm guess that these:

func f1[T... any](x T) { fmt.Println(&x) }
func f2[T... any](x T) any { return x }

the first one is never allowed and the second one is only allowed if called with a single type? It seems weird to me that this introduces variables that aren't real variables and struct fields that aren't real struct fields.

@leaxoy The proposal intentionally does not propose allowing that. There are undeniably useful abilities, but they are out of scope here.

We do not propose introducing such facilities into Go, as that leads to template metaprogramming, which we do not want to support. In this proposal, Go variadic type parameters can only be used in limited ways.

@ianlancetaylor I'm a bit worried about the ability to specify bounds on the number of type-parameters, as it seems to me to have the potential to introduce corner cases allowing computation. For that reason, it would be useful to have a relatively precise phrasing what those rules are.

• Is f[~T... any] legal?
• Is kk := Keys{keys: ???}; for k := range kk.keys {...} legal?
• Is there an "unpack" to type params in this design?

@changkun

Is f[~T... any] legal?

I'm not sure what that syntax should mean, so I'd say no. Note that F[~T any] isn't legal either.

Is kk := Keys{keys: ???}; for k := range kk.keys {...} legal?

I don't think so (assuming you meant Key[T]{keys}?), as that is a struct type with fields f0, …, fn, there is no kk.keys. Otherwise you'd have to elaborate what Keys is in your example.

Is there an "unpack" to type params in this design?

No.

Note that F[~T any] isn't legal either.

Sorry for the noise. I meant like this f[T... ~int]. Is it legal?

I don't see a reason why it wouldn't be. Note that the proposal uses Metric[V... 1 0 comparable] as an example and the syntax explanation says f[T... constraint], ISTM that should make clear that any legal constraint can be used.

If the maximum is 0, there is no upper limit.

I was a little bit confused by the example type Metric[V... 1 0 comparable], because at first glance it seemed as if minimum > maximum.

I prefer following spec/syntax:

• If the maximum value is omitted, there is no upper limit: the above example would be written as Metric[V... 1 comparable].
• Maximum value less than 1 is illegal.

In addition, using variable generics to solve the problem of seq is not the only way. Another way is to introduce tuple. I have opened a corresponding issue #61920 before, but it was quickly closed.

Consider the following code

type Seq[E any] func (yield func(E) bool)

func MapEntries[K comparable, V any](m M) Seq[(K, V)] {
    for k, v := range m {
        if !yield((k, v)) {
            return
        }
    }
}

Its complexity is much less than that of variadic generics

---

And answer the previous comment: variadic generics as structure fields can also be tuple types.

Looks fine to me. I will need to think about it some more. It also shows how extensive a work it requires which is good information. Could allow to tackle a few other things such as the return of zero values.

Quite welcome to simplify iterators too!

A question I have is whether we can have multiple such variadic type parameters, so as to handle more function signatures as constraints. Example function (does it even make sense?)

func StringerifyFunc [A... any, R... any, F f(A) R, S interface{F; fmt.Stringer} ] (f F) S{
    // return a func type with a method that returns the func name
} 

And yes, for variadic fields, maybe there is a way to use a slightly more complex generated field name to further prevent conflicts, for instance, with methods names. (https://go.dev/play/p/qYwY79EG9Ls)

Nice.