Source: iter.go in package github.com/go-git/go-git/v5/utils/merkletrie

package merkletrie

import (
	"fmt"
	"io"

	"github.com/go-git/go-git/v5/utils/merkletrie/internal/frame"
	"github.com/go-git/go-git/v5/utils/merkletrie/noder"
)

Iter is an iterator for merkletries (only the trie part of the merkletrie is relevant here, it does not use the Hasher interface). The iteration is performed in depth-first pre-order. Entries at each depth are traversed in (case-sensitive) alphabetical order. This is the kind of traversal you will expect when listing ordinary files and directories recursively, for example: Trie Traversal order ---- --------------- . / | \ c / | \ d/ d c z ===> d/a / \ d/b b a z This iterator is somewhat especial as you can chose to skip whole "directories" when iterating: - The Step method will iterate normally. - the Next method will not descend deeper into the tree. For example, if the iterator is at `d/`, the Step method will return `d/a` while the Next would have returned `z` instead (skipping `d/` and its descendants). The name of the these two methods are based on the well known "next" and "step" operations, quite common in debuggers, like gdb. The paths returned by the iterator will be relative, if the iterator was created from a single node, or absolute, if the iterator was created from the path to the node (the path will be prefixed to all returned paths).

Tells if the iteration has started.

The top of this stack has the current node and its siblings. The rest of the stack keeps the ancestors of the current node and their corresponding siblings. The current element is always the top element of the top frame. When "step"ping into a node, its children are pushed as a new frame. When "next"ing pass a node, the current element is dropped by popping the top frame.

The base path used to turn the relative paths used internally by the iterator into absolute paths used by external applications. For relative iterator this will be nil.

	base noder.Path
}

NewIter returns a new relative iterator using the provider noder as its unnamed root. When iterating, all returned paths will be relative to node.

func NewIter(n noder.Noder) (*Iter, error) {
	return newIter(n, nil)
}

NewIterFromPath returns a new absolute iterator from the noder at the end of the path p. When iterating, all returned paths will be absolute, using the root of the path p as their root.

func NewIterFromPath(p noder.Path) (*Iter, error) {
	return newIter(p, p) // Path implements Noder
}

func newIter(root noder.Noder, base noder.Path) (*Iter, error) {
	ret := &Iter{
		base: base,
	}

	if root == nil {
		return ret, nil
	}

	frame, err := frame.New(root)
	if err != nil {
		return nil, err
	}
	ret.push(frame)

	return ret, nil
}

func (iter *Iter) top() (*frame.Frame, bool) {
	if len(iter.frameStack) == 0 {
		return nil, false
	}
	top := len(iter.frameStack) - 1

	return iter.frameStack[top], true
}

func (iter *Iter) push(f *frame.Frame) {
	iter.frameStack = append(iter.frameStack, f)
}

const (
	doDescend   = true
	dontDescend = false
)

Next returns the path of the next node without descending deeper into the trie and nil. If there are no more entries in the trie it returns nil and io.EOF. In case of error, it will return nil and the error.

func (iter *Iter) Next() (noder.Path, error) {
	return iter.advance(dontDescend)
}

Step returns the path to the next node in the trie, descending deeper into it if needed, and nil. If there are no more nodes in the trie, it returns nil and io.EOF. In case of error, it will return nil and the error.

func (iter *Iter) Step() (noder.Path, error) {
	return iter.advance(doDescend)
}

Advances the iterator in the desired direction: descend or dontDescend. Returns the new current element and a nil error on success. If there are no more elements in the trie below the base, it returns nil, and io.EOF. Returns nil and an error in case of errors.

func (iter *Iter) advance(wantDescend bool) (noder.Path, error) {
	current, err := iter.current()
	if err != nil {
		return nil, err
	}

The first time we just return the current node.

	if !iter.hasStarted {
		iter.hasStarted = true
		return current, nil
	}

Advances means getting a next current node, either its first child or its next sibling, depending if we must descend or not.

	numChildren, err := current.NumChildren()
	if err != nil {
		return nil, err
	}

	mustDescend := numChildren != 0 && wantDescend

descend: add a new frame with the current's children.

		frame, err := frame.New(current)
		if err != nil {
			return nil, err
		}
		iter.push(frame)

don't descend: just drop the current node

		iter.drop()
	}

	return iter.current()
}

Returns the path to the current node, adding the base if there was one, and a nil error. If there were no noders left, it returns nil and io.EOF. If an error occurred, it returns nil and the error.

func (iter *Iter) current() (noder.Path, error) {
	if topFrame, ok := iter.top(); !ok {
		return nil, io.EOF
	} else if _, ok := topFrame.First(); !ok {
		return nil, io.EOF
	}

	ret := make(noder.Path, 0, len(iter.base)+len(iter.frameStack))

concat the base...

... and the current node and all its ancestors

	for i, f := range iter.frameStack {
		t, ok := f.First()
		if !ok {
			panic(fmt.Sprintf("frame %d is empty", i))
		}
		ret = append(ret, t)
	}

	return ret, nil
}

removes the current node if any, and all the frames that become empty as a consequence of this action.

func (iter *Iter) drop() {
	frame, ok := iter.top()
	if !ok {
		return
	}

if the frame is empty, remove it and its parent, recursively

	if frame.Len() == 0 {
		top := len(iter.frameStack) - 1
		iter.frameStack[top] = nil
		iter.frameStack = iter.frameStack[:top]
		iter.drop()
	}