Preface

Firstly, let's understand what an iterator is and why we need it. In programming, we frequently require an API to provide callers with a series of homogeneous elements for further processing. The most straightforward approach is to furnish an API that returns a slice of elements. For instance, our code might fetch all users from a database for the caller:

func GetUsers() ([]User, error)

However, fetching all elements isn't always the best choice due to several reasons:

Handling large volumes of data at once can exert memory pressure. In contrast, processing data in chunks or streams tends to be more memory-efficient.
Retrieving all elements can be resource-intensive. In scenarios where the caller might stop processing midway – for example, when a client terminates an HTTP connection – fetching every element becomes wasteful, as not all of them will be used.
At times, the anticipated elements might not be readily available. Consider a situation where our system must post a new entry to a Kafka topic as soon as it's available. Here, the iterator would 'block' or wait until the required data emerges in the source database, essentially creating an endless iterator.

To present a more realistic depiction, we'll use reading from an SQL database as the foundation for our iterator, veering away from the often-cited counter-increment example.

When choosing the best method to implement iterators, several factors come into play:

State Maintenance: Iterators often need to preserve a state, be it a cursor's location in a document or a page number in a paginated API.
Error Handling: While fetching the next element, the iterator might encounter errors. Implementation methods differ in how they manage such mishaps.
Closure: Iterators frequently allocate resources, such as database connections or HTTP sessions. It's crucial to devise a strategy to close the iterator, either due to surrounding code errors or when there's no longer a need for additional elements.
Stopping: Beyond merely closing an iterator to free up resources, callers should also possess the capability to halt an iterator, particularly if flow control is waiting on the iterator.

We'll delve into three techniques that the Golang standard and third-party libraries frequently employ to provide iteration APIs:

The .Next() method
Go channels
The Visitor function approach.

Push and Pull Semantics

The iterator API can be broken down in terms of push and pull semantics. There are primarily two prevalent methodologies: pull and push.

In the pull method, the caller governs the program flow, deciding when to solicit the next data chunk from the iterator. Conversely, with the push method, the iterator steers the program, determining when to send the succeeding data piece to the caller. This choice can profoundly influence system architecture, agility, and overall performance.

The Next() method embodies pure pull semantics. The visitor function method is rooted in push semantics. Go channels adopt a mixed strategy, presupposing the existence of two separate goroutines. From the iterator's perspective, it's pushing data; however, from the caller's vantage point, data is being pulled.

Techniques

The Next() method

This approach is straightforward and should be familiar to developers from other languages. Here, we define a struct that maintains state in its fields. The caller retrieves the next element by invoking the .Next() method. Although commonly referred to as "Next", this method might have other names like .Read(), .FetchOne(), etc. The core idea remains consistent: retrieving one piece of data per call.

‣

Implementation

var ErrEndOfRows = errors.New("end of rows")

type User struct {
	ID   int    `json:"id"`
	Name string `json:"name"`
}

type Iterator struct {
	rows *sql.Rows
}

func NewIterator(db *sql.DB) (*Iterator, error) {
	rows, err := db.Query("SELECT id, name FROM users")
	if err != nil {
		return nil, err
	}
	return &Iterator{rows: rows}, nil
}

func (i *Iterator) Next() (User, error) {
	if i.rows.Next() {
		var u User
		err := i.rows.Scan(&u.ID, &u.Name)
		if err != nil {
			return User{}, err
		}
		return u, nil
	}
	if err := i.rows.Err(); err != nil {
		return User{}, err
	}

	return User{}, ErrEndOfRows
}

func (i *Iterator) Close() error {
	return i.rows.Close()
}

State maintenance

With each call to the .Next() method, all local variables within that method are discarded. Consequently, the iterator needs to retain its state using the struct fields. In complex scenarios, especially with intricate states like those in certain parsers, resuming the state from these struct fields can prove challenging. We keep underlying rows struct in our Iterator fields in the example.

Closure

To free up allocated resources, the iterator typically offers a .Close() method. It falls upon the caller to execute this method, either when an error surfaces in the iterator or during its routine closure.

Error Handling

Should any errors arise during the iteration, the Next() method can return an error. In such situations, the caller is equipped to handle the error as per its specific logic. Despite this, it remains standard for the caller to execute Close(). Moreover, after encountering an error, calling Next() is typically disallowed. This necessitates the caller to be well-acquainted with the iterator's behavior to use it aptly.

Stopping

After every Next() invocation, the caller retains explicit control over the program's flow. This setup empowers them to cease the iterator at any given moment between calls without demanding any supplementary halting mechanics within the iterator.

for iter.Next() {
   if shouldStop {
       iter.Close()
       return
   }
   // Regular processing here
}

Examples

Go Channels

Channels are fundamental to Go, offering a seamless means to implement the iterator pattern. With this approach, a separate goroutine is initiated within the iterator, sending data into either a buffered or unbuffered channel. Typically, the iterator constructor will return this channel to the caller.

In the provided implementation, there is also a stopCh channel. This channel facilitates the detection of the caller's intent to halt the iterator. If the caller closes this channel, the iterator recognizes the signal to cease operation.

‣

Implementation

type User struct {
	ID   int    `json:"id"`
	Name string `json:"name"`
}

func IterateUsers(db *sql.DB, stopCh chan struct{}) (<-chan User, <-chan error, error) {

	rows, err := db.Query("SELECT id, name FROM users")
	if err != nil {
		return nil, nil, err
	}

	userCh := make(chan User)
	errCh := make(chan error)

	go func() {
		defer close(userCh)
		defer close(errCh)
		defer rows.Close()

		for rows.Next() {
			var u User
			err := rows.Scan(&u)
			if err != nil {
				errCh <- err
				return
			}
			select {
			case userCh <- u:
			case <-stopCh:
				return
			}
		}
		if err := rows.Err(); err != nil {
			errCh <- err
		}
	}()

	return userCh, errCh, nil
}

State maintenance

Unlike methods that maintain state using struct fields, goroutines preserve their state in local variables. These variables remain consistent between pushes to the channel, often simplifying the iterator's state management.

Closure

In this approach, the goroutine is responsible for releasing any resources before its termination.

Error handling

The iterator can also return an errors channel alongside the primary data channel. The onus is on the caller to monitor this channel, typically achieved with a select statement:

data, errs, _ := IterateUsers(db, stopCh)
L:
	for {
		select {
		case u, ok := <-data:
	    if !ok {
				// end of data. Normal closure
				return
			}
			// handle data
		case err := <-errs:
			// handle error
			break L  // exit loop
		}
	}

Stopping

Given the concurrent nature of goroutines, it's more likely for the caller to forget to halt this iterator. If the caller receives a stop signal, neglecting to halt the iterator can lead to resource leakage, especially if the iterator runs indefinitely.

Furthermore, due to this concurrency, it's often imperative to not only close the stopCh channel but also to wait until the iterator has genuinely ceased operation and released all pertinent resources:

data, errs, _ := IterateUsers(db, stopCh)
L:
	for {
		select {
		case u, ok := <-data:
	    if !ok {
				// end of data. Normal closure
				return
			}
			// handle data
      if shouldStop {
				close(stopCh)
        continue  // WE CAN'T just return here, because iterator is not stopped yet. We continue and expecting closing of <-data channel
			}
		case err := <-errs:
			// handle error
			break L  // exit loop
		}
	}

Examples

time.Ticker

The Visitor function approach

In this method, the iterator controls the program's flow, with the caller blocked during the iterator's execution. The primary requisite for the caller is to supply a function or "hook" that the iterator calls for each element.

‣

Implementation

type User struct {
	ID   int    `json:"id"`
	Name string `json:"name"`
}

func IterateUsers(db *sql.DB, visit func(User) error) error {
	rows, err := db.Query("SELECT id, name FROM users")
	if err != nil {
		return err
	}
	defer rows.Close()

	for rows.Next() {
		var u User
		err := rows.Scan(&u.ID, &u.Name)
		if err != nil {
			return err
		}
		err = visit(u)
		if err != nil {
			return err
		}
	}

	return rows.Err()
}

State maintenance

Similar to the channel-based approach, local variables maintain the state inside the iterator. This often simplifies the iterator's implementation, as the state can be tracked seamlessly within the iterator's own context without requiring external constructs.

Closure

As with the channel-based approach, this iterator typically frees up resources upon completion.

Error handling

Handling errors can be nuanced in this approach. As seen in the IterateUsers function, only one error is returned. This could either be an intrinsic error from the iterator or an error returned by the visitor, which gets relayed to the caller. This inversion of control can introduce complexity, making the program harder to comprehend.

Stopping

Termination can also be somewhat intricate. Since the program flow is blocked by the iterator, a common technique involves the caller returning a unique sentinel error within its hook. The iterator, in turn, returns this error. By distinguishing this error from others, one can ascertain whether a genuine error occurred or if it's merely a signal to halt the iterator.

var ErrStop = errors.New("stop")
err = IterateUsers(db, func(user User) {
	// processing
	if shouldStop {
		return ErrStop
	}
})
if errors.Is(err, ErrStop) {
  // This is expected situation, caller just decided to stop iterati
	return
}
if err != nil {
	// handle actuall error
}

Examples

filepath.Walk

Conclusion

Iteration patterns are essential in programming, enabling developers to traverse and manipulate data collections effectively. In Go, there are several distinct approaches to implement iterators, each bringing its own advantages and intricacies to the table. The choice of iteration pattern should align with the nature of the data being processed, the desired flow of control, and the specific requirements of the task at hand. Let's explore the pros and cons of three prominent iteration methods in Go to provide a clearer understanding and guide the selection process:

The Next() method

Pros:

Familiar pattern to developers from other languages.
Explicit control of the iteration process.
Straightforward error handling.

Cons:

Maintaining state can become complex.
Caller must remember to close resources.

Go Channels

Pros:

Native Go way of handling concurrent data streams.
Goroutines maintain state in local variables, making it easier to track.
Automatic resource cleanup when the goroutine finishes.

Cons:

Overhead of managing goroutines and channels.
Caller must handle potential goroutine leaks, especially if the iterator is long-running.
Requires additional error handling (usually through a separate channel).

The Visitor function approach

Pros:

Offers inversion of control; the iterator calls back on provided functions.
Simplified resource management (usually managed within the iterator).

Cons:

Control flow is in the hands of the iterator, which can be less intuitive.
Error handling might involve proxying errors through the iterator, complicating the control flow.
Stopping the iterator requires sentinel values or other mechanisms.

Iterating in Go: Traditional and Idiomatic Approaches

Preface

Push and Pull Semantics

Techniques

The Next() method

Implementation

State maintenance

Closure

Error Handling

Stopping

Examples

Go Channels

Implementation

State maintenance

Closure

Error handling

Stopping

Examples

The Visitor function approach

Implementation

State maintenance

Closure

Error handling

Stopping

Examples

Conclusion