go/types: add iterator methods

[adonovan]

Proposal Details

There are many data types in the API of go/types that expose a sequence through a pair of methods NumFoo() int and Foo(int) Foo. For each of them, we propose to define new convenience methods that are go1.23 push iterators:

package types

// Methods is a go1.23 iterator over all the methods of an interface,
// ordered by Id.
//
// Example: for m := range t.Methods { ... }
func (t *Interface) Methods(yield func(*Func) bool) {
    for i := range t.NumMethods() {
        if !yield(t.Method(i)) {
            break
        }
    }
}

// ExplicitMethods is a go1.23 iterator over the explicit methods of an interface.
//
// Example: for m := range t.ExplicitMethods { ... }
func (t *Interface) ExplicitMethods(yield func(*Func) bool) {
    for i := range t.NumExplicitMethods() {
        if !yield(t.ExplicitMethod(i)) {
            break
        }
    }
}

// EmbeddedTypes is a go1.23 iterator over the types embedded within an interface.
//
// Example: for e := range t.EmbeddedTypes { ... }
func (t *Interface) EmbeddedTypes(yield func(Type) bool) {
    for i := range t.NumEmbeddeds() {
        if !yield(t.EmbeddedType(i)) {
            break
        }
    }
}

// Methods is a go1.23 iterator over the declared methods of a named type.
//
// Example: for m := range t.Methods { ... }
func (t *Named) Methods(yield func(*Func) bool) {
    for i := range t.NumMethods() {
        if !yield(t.Method(i)) {
            break
        }
    }
}

// Children is a go1.23 iterator over the child scopes nested within scope s.
//
// Example: for child := range scope.Children { ... }
func (s *Scope) Children(yield func(*Scope) bool) {
    for i := range s.NumChildren() {
        if !yield(s.Child(i)) {
            break
        }
    }
}

// Fields is a go1.23 iterator over the fields of a struct type.
//
// Example: for f := range s.Fields { ... }
func (s *Struct) Fields(yield func(*Var) bool) {
    for i := range s.NumFields() {
        if !yield(s.Field(i)) {
            break
        }
    }
}

// Variables is a go1.23 iterator over the variables of a tuple type.
//
// Example: for v := range tuple.Variables { ... }
func (t *Tuple) Variables(yield func(*Var) bool) {
    for i := range t.Len() {
        if !yield(t.At(i)) {
            break
        }
    }
}

// MethodSet is a go1.23 iterator over the methods of a method set.
//
// Example: for v := range tuple.Methods { ... }
func (s *MethodSet) Methods(yield func(*Selection) bool) {
    for i := range s.Len() {
        if !yield(s.At(i)) {
            break
        }
    }
}

// Terms is a go1.23 iterator over the terms of a union.
//
// Example: for term := range union.Terms { ... }
func (u *Union) Terms(yield func(*Term) bool) {
    for i := range u.Len() {
        if !yield(u.Term(i)) {
            break
        }
    }
}

// TypeParams is a go1.23 iterator over a list of type parameters.
//
// Example: for tparam := range l.TypeParams { ... }
func (l *TypeParamList) TypeParams(yield func(*TypeParam) bool) {
    for i := range l.Len() {
        if !yield(l.At(i)) {
            break
        }
    }
}

// Types is a go1.23 iterator over the elements of a list of type parameters.
//
// Example: for t := range l.Types { ... }
func (l *TypeList) Types(yield func(Type) bool) {
    for i := range l.Len() {
        if !yield(l.At(i)) {
            break
        }
    }
}

Fortunately, the most natural name (usually the plural) was available in all cases.

@findleyr @gri @mdempsky

[gopherbot]

Change https://go.dev/cl/575455 mentions this issue: go/types: add go1.23 iterator methods for 10 exported types

[icholy]

I would have expected an API like this:

func (t *Interface) Methods() iter.Seq[*Func] 
func (t *Interface) ExplicitMethods() iter.Seq[*Func]
func (t *Interface) EmbeddedTypes() iter.Seq[Type]
func (t *Named) Methods() iter.Seq[*Func]
func (s *Scope) Children() iter.Seq[*Scope]
func (s *Struct) Fields() iter.Seq[*Var]
func (t *Tuple) Variables() iter.Seq[*Var]
func (s *MethodSet) Methods() iter.Seq[*Selection]
func (u *Union) Terms() iter.Seq[*Term]
func (l *TypeParamList) TypeParams() iter.Seq[*TypeParam]
func (l *TypeList) Types() iter.Seq[Type]

[adonovan]

I would have expected an API like this ...

That works, but leads to unnecessary eta abstraction: the implementation of the method has to create a lambda abstraction that the caller (range statement) immediately reduces. It's more syntax for both parties, and less efficient. Recall that in Go, the method value t.Methods forms a closure with code (*Interface).Methods and data t, so there's no need to create a second closure.

[findleyr]

@adonovan it seems like the Set.All or List.All examples in #61897 could probably also be written without the additional eta abstraction. I think we need clarity on idiomatic signatures for iterators.

I personally would also prefer the simpler pattern proposed here, avoiding the unnecessary closure. But we should be consistent in the standard library.

[adonovan]

The performance difference is negligible. (Apologies for my short-lived earlier draft containing an obvious major blunder!)

src$ go test  -bench=. ./iter
goos: darwin
goarch: arm64
pkg: iter
cpu: Apple M1 Pro
BenchmarkA-8    217676379            5.440 ns/op
BenchmarkB-8    220483566            5.437 ns/op
PASS
ok      iter    3.728s

package iter_test

import "testing"

type T struct{}

func (T) A() func(yield func(elem int) bool) {
    return func(yield func(elem int) bool) {
        _ = yield(1) && yield(2)
    }
}

func (T) B(yield func(elem int) bool) {
    _ = yield(1) && yield(2)
}

func BenchmarkA(b *testing.B) {
    sum := 0
    for range b.N {
        for i := range new(T).A() {
            sum += i
        }
    }
    if sum == -1 {
        println(sum)
    }
}

func BenchmarkB(b *testing.B) {
    sum := 0
    for range b.N {
        for i := range new(T).B {
            sum += i
        }
    }
    if sum == -1 {
        println(sum)
    }
}

[rsc]

These should be written to take no arguments and return an iter.Seq[...] but otherwise looks good.

[adonovan]

These should be written to take no arguments and return an iter.Seq[...] but otherwise looks good.

OK, https://go.dev/cl/575455 has been updated to reflect that.

pkg go/types, method (*Interface) EmbeddedTypes() func(func(Type) bool) #66626
pkg go/types, method (*Interface) ExplicitMethods() func(func(*Func) bool) #66626
pkg go/types, method (*Interface) Methods() func(func(*Func) bool) #66626
pkg go/types, method (*MethodSet) Methods() func(func(*Selection) bool) #66626
pkg go/types, method (*Named) Methods() func(func(*Func) bool) #66626
pkg go/types, method (*Scope) Children() func(func(*Scope) bool) #66626
pkg go/types, method (*Struct) Fields() func(func(*Var) bool) #66626
pkg go/types, method (*Tuple) Variables() func(func(*Var) bool) #66626
pkg go/types, method (*TypeList) Types() func(func(Type) bool) #66626
pkg go/types, method (*TypeParamList) TypeParams() func(func(*TypeParam) bool) #66626
pkg go/types, method (*Union) Terms() func(func(*Term) bool) #66626

[rsc]

This proposal has been added to the active column of the proposals project and will now be reviewed at the weekly proposal review meetings. — rsc for the proposal review group

[rsc]

The API tool should record those as returning iter.Seq[foo] not func(func(foo)bool).

[rsc]

Have all remaining concerns about this proposal been addressed?

The proposal is to add the API listed in https://github.com/golang/go/issues/66626#issuecomment-2037717088, but using iter.Seq instead of explicit func types.

[adonovan]

Ah, I remember now: I used the underlying type of iter.Seq because the iter package is build-tagged goexperiment.rangefunc, so it can't be imported from go/types (unless the file in go/types is similarly tagged). Once we commit to the experiment we should definitely use the log forms.

(I don't think there's any problem with the API tool.)

[rsc]

Based on the discussion above, this proposal seems like a likely accept. — rsc for the proposal review group

The proposal is to add the API listed in https://github.com/golang/go/issues/66626#issuecomment-2037717088, but using iter.Seq instead of explicit func types.

[rsc]

No change in consensus, so accepted. 🎉 This issue now tracks the work of implementing the proposal. — rsc for the proposal review group

The proposal is to add the API listed in https://github.com/golang/go/issues/66626#issuecomment-2037717088, but using iter.Seq instead of explicit func types.