New iteration behavior via FileIter and TreeWalker

Instead of returning a channel of files, Tree.Files() now returns a
FileIter with these qualities:

* It returns files in the original order of the repository (relying on a
* new Tree.OrderedNames property)
* It can return errors encountered when retrieving files and trees from
* underlying storage
* It can be Closed without having to drain the entire channel
* It defers the heavy lifting to a new TreeWalker type
* Its behavior is a little more consistent with other Iter types
* It's a little less prone to memory leaks

This update includes a new TreeWalker type that will iterate through all
of the entries of a tree and its descendant subtrees. It does the dirty
work that Tree.walkEntries() used to do, but with a public API.

A new TreeIter type is also included that just walks through subtrees.
This could be useful for performing a directory search while ignoring
files/blobs altogether.

1 files changed, 110 insertions, 0 deletions

diff --git a/tree_walker.go b/tree_walker.go
new file mode 100644
index 0000000..3272718
--- /dev/null
+++ b/tree_walker.go
@@ -0,0 +1,110 @@
+package git
+
+import (
+	"io"
+	"path"
+
+	"gopkg.in/src-d/go-git.v3/core"
+)
+
+const (
+	startingStackSize = 8
+)
+
+// TreeWalker provides a means of walking through all of the entries in a Tree.
+type TreeWalker struct {
+	stack []TreeEntryIter
+	base  string
+
+	r *Repository
+}
+
+// NewTreeWalker returns a new TreeWalker for the given repository and tree.
+//
+// It is the caller's responsibility to call Close() when finished with the
+// tree walker.
+func NewTreeWalker(r *Repository, t *Tree) *TreeWalker {
+	w := TreeWalker{
+		stack: make([]TreeEntryIter, 0, startingStackSize),
+		base:  "",
+		r:     r,
+	}
+	w.stack = append(w.stack, *NewTreeEntryIter(t))
+	return &w
+}
+
+// Next returns the next object from the tree. Objects are returned in order
+// and subtrees are included. After the last object has been returned further
+// calls to Next() will return io.EOF.
+//
+// In the current implementation any objects which cannot be found in the
+// underlying repository will be skipped automatically. It is possible that this
+// may change in future versions.
+func (w *TreeWalker) Next() (name string, entry TreeEntry, obj core.Object, err error) {
+	for {
+		current := len(w.stack) - 1
+		if current < 0 {
+			// Nothing left on the stack so we're finished
+			err = io.EOF
+			return
+		}
+		if current > maxTreeDepth {
+			// We're probably following bad data or some self-referencing tree
+			err = ErrMaxTreeDepth
+			return
+		}
+
+		entry, err = w.stack[current].Next()
+		if err == io.EOF {
+			// Finished with the current tree, move back up to the parent
+			w.stack = w.stack[:current]
+			w.base, _ = path.Split(w.base)
+			w.base = path.Clean(w.base) // Remove trailing slash
+			continue
+		}
+		if err != nil {
+			return
+		}
+
+		obj, err = w.r.Storage.Get(entry.Hash)
+		if err == core.ObjectNotFoundErr {
+			// FIXME: Avoid doing this here in case the caller actually cares about
+			//        missing objects.
+			continue // ignore entries without hash (= submodule dirs)
+		}
+
+		name = path.Join(w.base, entry.Name)
+
+		if err != nil {
+			return
+		}
+
+		break
+	}
+
+	if obj.Type() == core.TreeObject {
+		tree := &Tree{r: w.r}
+		err = tree.Decode(obj)
+		if err != nil {
+			return
+		}
+		w.stack = append(w.stack, *NewTreeEntryIter(tree))
+		w.base = path.Join(w.base, entry.Name)
+	}
+
+	return
+}
+
+// Tree returns the tree that the tree walker most recently operated on.
+func (w *TreeWalker) Tree() *Tree {
+	current := len(w.stack) - 1
+	if current < 0 {
+		return nil
+	}
+	return w.stack[current].t
+}
+
+// Close releases any resources used by the TreeWalker.
+func (w *TreeWalker) Close() {
+	w.stack = nil
+}