discussion: standard iterator interface · golang go · Discussion #54245 · GitHub
Skip to content You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert discussion: standard iterator interface #54245 Closed Locked ianlancetaylor announced in Discussions discussion: standard iterator interface #54245 ianlancetaylor Aug 4, 2022 · 95 comments · 539 replies Return to top Discussion options Uh oh!
There was an error while loading. Please reload this page . Uh oh! There was an error while loading. Please reload this page . ianlancetaylor Aug 4, 2022 Collaborator This is a discussion that is intended to lead to a proposal. This was written with lots of input from @jba and @rsc . Background Most languages provide a standardized way to iterate over values stored in containers using an iterator interface (see the appendix below for a discussion of other languages).
Go provides for range for use with maps, slices, strings, arrays, and channels, but it does not provide any general mechanism for user-written containers, and it does not provide an iterator interface. Go does have examples of non-generic iterators: runtime.CallersFrames returns a runtime.Frames that iterates over stack frames; Frames has a Next method that returns a Frame and a bool that reports whether there are more frames. bufio.Scanner is an iterator through an io.Reader , where the Scan method advances to the next value.
The value is returned by a Bytes method. Errors are collected and returned by an Err method. database/sql.Rows iterates through the results of a query, where the Next method advances to the next value and the value is returned by a Scan method. The Scan method can return an error. Even this short list reveals that there are no common patterns in use today. This is in part because before generics were introduced, there was no way to write an interface that described an iterator.
And of course there may be no simple pattern that will cover all of these use cases.. Today we can write an interface Iter[E] for an iterator over a container that has elements of type E . The existence of iterators in other languages shows that this is a powerful facility. This proposal is about how to write such an interface in Go. What we want from Go iterators Go is of course explicit about errors. Iterators over containers can't fail.
For the most common uses it doesn't make any more sense to have iterators return an error than it does for a for range statement to return an error. Algorithms that use iterators should often behave differently when using iterators that can fail. Therefore, rather than try to combine non-failing and failing iterators into the same interface, we should instead return explicit errors from iterators that can fail. These errors can be part of the values returned by the iterator, or perhaps they can be returned as additional values.
Iterators have two fundamental operations: retrieve the current value, and advance to the next value. For Go we can combine these operations into a single method, as runtime.Frames does. In the general case we may want to implement iterators with some additional state that is not trivially garbage collected, such as an open file or a separate goroutine. In C++, for example, this state would be cleared up by a destructor, but of course Go does not have destructors.
Therefore, we should have some explicit way to indicate that we no longer need an iterator. This should be optional, as many iterators do not require any special cleanup. We should encourage iterators to use finalizers if necessary to clean up resources, and also to clean up after themselves when reaching the end of an iteration. In Go the builtin type map permits values to be inserted and removed while iterating over the map, with well-defined behavior.
In general for Go we should be flexible, though of course the program should never simply crash. We should let each container type define how it behaves if the container is modified while iterators are active. For example, container modification may cause arbitrary elements to be skipped or returned two or more times during the iteration. In some cases, hopefully rare, container modification may cause uses of existing iterators to panic, or to return values that have been removed from the container.
Proposal We define a new package iter that defines a set of interfaces. The expectation is that containers and other types will provide functions and methods that return values that implement these interfaces. Code that wants to work with arbitrary containers will use the interfaces defined in this package. That will permit people to write functions that work with containers but are agnostic to the actual container type being used, much as interfaces like io.Reader permit code to be agnostic as the source of the data stream. iter.Iter The core interface in the iterators package is iter.Iter[E] . // Iter supports iterating over a sequence of values of type `E`. type Iter [ E any ] interface { // Next returns the next value in the iteration if there is one, // and reports whether the returned value is valid. // Once Next returns ok==false, the iteration is over, // and all subsequent calls will return ok==false.
Next () ( elem E , ok bool ) } We also define a related interface for containers, such as maps, for which elements inherently have two values. // Iter2 is like Iter but each iteration returns a pair of values. type Iter2 [ E1 , E2 any ] interface { Next () ( E1 , E2 , bool ) } An iterator that can fail will either return a single value that includes an error indication, or it will implement Iter2[E, error] . It's not yet clear which of those options is better.
As mentioned above, some iterators may have additional state that may be discarded when no more values are expected from an iterator (for example, a goroutine that sends values on a channel). Telling the iterator that no more values are expected is done using an optional interface that an iterator may implement. // StopIter is an optional interface for Iter. type StopIter [ E any ] interface { Iter [ E ] // Stop indicates that the iterator will no longer be used. // After a call to Stop, future calls to Next may panic. // Stop may be called multiple times; // all calls after the first will have no effect.
Stop () } // StopIter2 is like StopIter, but for Iter2. type StopIter2 [ E1 , E2 any ] interface { Iter2 [ E1 , E2 ] Stop () } The Stop method should always be considered to be an optimization. The program should work correctly even if Stop is never called. If an iterator is read to the end (until Next returns false ) calling Stop should be a no-op. If necessary, iterator implementations should use finalizers to clean up cases where Stop is not called.
As a matter of programming style, the code that calls a function to obtain a StopIter is responsible for calling the Stop method. A function that accepts an Iter should not use a type assertion to detect and call the Stop method. This is similar to the way that a function that accepts an io.Reader should not use a type assertion to detect and call the Close method. iter.New functions iter.Iter provides a convenient way for the users of a container to iterate over its contents.
We also want to consider the other side of that operation, and provide convenient ways for containers to define iterators. // NewGen creates a new iterator from a generator function gen. // The gen function is called once. It is expected to call // yield(v) for every value v to be returned by the iterator. // If yield(v) returns false, gen must stop calling yield and return. func NewGen [ E any ]( gen func ( yield func ( E ) bool )) StopIter [ E ] // NewGen2 is like NewGen for Iter2. func NewGen2 [ E1 , E2 any ]( gen func ( yield func ( E1 , E2 ) bool )) StopIter2 [ E1 , E2 ] An appendix below discusses how these functions can be implemented efficien
The rest of this page is on the live site.