Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

go/types: add iterator methods #66626

Open
adonovan opened this issue Mar 31, 2024 · 13 comments
Open

go/types: add iterator methods #66626

adonovan opened this issue Mar 31, 2024 · 13 comments

Comments

@adonovan
Copy link
Member

adonovan commented Mar 31, 2024

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 gopherbot added this to the Proposal milestone Mar 31, 2024
@gopherbot
Copy link

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

@icholy
Copy link

icholy commented Apr 1, 2024

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
Copy link
Member Author

adonovan commented Apr 1, 2024

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
Copy link
Contributor

findleyr commented Apr 1, 2024

@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
Copy link
Member Author

adonovan commented Apr 1, 2024

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
Copy link
Contributor

rsc commented Apr 3, 2024

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

adonovan referenced this issue in google/starlark-go Apr 3, 2024
This change defines two helpers, Elements(seq)
and Entries(mapping), that adapt the Iterable and
IterableMapping interfaces to one- and two-variable
go1.23 range loops. The new syntax is more concise
and frees the caller from worrying about Iterator.Done.

We do not yet update any calls to use them, so that
the project can continue to be build with pre-go1.23
releases of Go.

Also, define Elements methods on {*List,Tuple,*Set}
and an Entries method on *Dict. These optimized iterators
(which can fetch both k and v in one go) will be
used by the Elements and Entries standalone functions
when the operand supports it. (User-defined types
can implement these methods too, although the
interface isn't currently documented.)

Also, a go1.23-only test of the new iteration.
@adonovan
Copy link
Member Author

adonovan commented Apr 4, 2024

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 rsc changed the title proposal: go/types: add go1.23 push iterators alongside existing NumFoo()/Foo(int) APIs proposal: go/types: add iterator methods Apr 4, 2024
@rsc
Copy link
Contributor

rsc commented Apr 4, 2024

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

adonovan added a commit to google/starlark-go that referenced this issue Apr 7, 2024
According to
golang/go#66626 (comment),
the convention for iterator methods is that they should return
an iterator, not be an iterator. The caller thus uses this form:

   for _ elem := range v.Elements() { ... }

not this one:

   for _ elem := range v.Elements { ... }

This is unfortunately a breaking API change, but since go1.23 is
not yet released, no-one should be using the new range syntax yet.
adonovan added a commit to google/starlark-go that referenced this issue Apr 8, 2024
According to
golang/go#66626 (comment),
the convention for iterator methods is that they should return
an iterator, not be an iterator. The caller thus uses this form:

   for _ elem := range v.Elements() { ... }

not this one:

   for _ elem := range v.Elements { ... }

This is unfortunately a breaking API change, but since go1.23 is
not yet released, no-one should be using the new range syntax yet.
@rsc
Copy link
Contributor

rsc commented Apr 10, 2024

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

@rsc
Copy link
Contributor

rsc commented Apr 10, 2024

Have all remaining concerns about this proposal been addressed?

The proposal is to add the API listed in #66626 (comment), but using iter.Seq instead of explicit func types.

@adonovan
Copy link
Member Author

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
Copy link
Contributor

rsc commented Apr 24, 2024

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 #66626 (comment), but using iter.Seq instead of explicit func types.

@rsc
Copy link
Contributor

rsc commented May 8, 2024

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 #66626 (comment), but using iter.Seq instead of explicit func types.

@rsc rsc changed the title proposal: go/types: add iterator methods go/types: add iterator methods May 8, 2024
@rsc rsc modified the milestones: Proposal, Backlog May 8, 2024
@adonovan adonovan self-assigned this May 15, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: Accepted
Development

No branches or pull requests

5 participants