add merkletrie iterator and its helper frame type (#252)

* add merkletrie iterator and its helper frame type

* requested changes by mcuadros

* reuqested changes: smola

4 files changed, 873 insertions, 0 deletions

diff --git a/utils/merkletrie/internal/frame/frame.go b/utils/merkletrie/internal/frame/frame.go
new file mode 100644
index 0000000..fd06307
--- /dev/null
+++ b/utils/merkletrie/internal/frame/frame.go
@@ -0,0 +1,91 @@
+package frame
+
+import (
+	"bytes"
+	"fmt"
+	"sort"
+	"strings"
+
+	"srcd.works/go-git.v4/utils/merkletrie/noder"
+)
+
+// A Frame is a collection of siblings in a trie, sorted alphabetically
+// by name.
+type Frame struct {
+	// siblings, sorted in reverse alphabetical order by name
+	stack []noder.Noder
+}
+
+type byName []noder.Noder
+
+func (a byName) Len() int      { return len(a) }
+func (a byName) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
+func (a byName) Less(i, j int) bool {
+	return strings.Compare(a[i].Name(), a[j].Name()) < 0
+}
+
+// New returns a frame with the children of the provided node.
+func New(n noder.Noder) (*Frame, error) {
+	children, err := n.Children()
+	if err != nil {
+		return nil, err
+	}
+
+	sort.Sort(sort.Reverse(byName(children)))
+	return &Frame{
+		stack: children,
+	}, nil
+}
+
+// String returns the quoted names of the noders in the frame sorted in
+// alphabeticall order by name, surrounded by square brackets and
+// separated by comas.
+//
+// Examples:
+//     []
+//     ["a", "b"]
+func (f *Frame) String() string {
+	var buf bytes.Buffer
+	_ = buf.WriteByte('[')
+
+	sep := ""
+	for i := f.Len() - 1; i >= 0; i-- {
+		_, _ = buf.WriteString(sep)
+		sep = ", "
+		_, _ = buf.WriteString(fmt.Sprintf("%q", f.stack[i].Name()))
+	}
+
+	_ = buf.WriteByte(']')
+
+	return buf.String()
+}
+
+// First returns, but dont extract, the noder with the alphabetically
+// smaller name in the frame and true if the frame was not empy.
+// Otherwise it returns nil and false.
+func (f *Frame) First() (noder.Noder, bool) {
+	if f.Len() == 0 {
+		return nil, false
+	}
+
+	top := f.Len() - 1
+
+	return f.stack[top], true
+}
+
+// Drop extracts the noder with the alphabetically smaller name in the
+// frame or does nothing if the frame was empty.
+func (f *Frame) Drop() {
+	if f.Len() == 0 {
+		return
+	}
+
+	top := f.Len() - 1
+	f.stack[top] = nil
+	f.stack = f.stack[:top]
+}
+
+// Len returns the number of noders in the frame.
+func (f *Frame) Len() int {
+	return len(f.stack)
+}
diff --git a/utils/merkletrie/internal/frame/frame_test.go b/utils/merkletrie/internal/frame/frame_test.go
new file mode 100644
index 0000000..9cc0994
--- /dev/null
+++ b/utils/merkletrie/internal/frame/frame_test.go
@@ -0,0 +1,108 @@
+package frame
+
+import (
+	"fmt"
+	"testing"
+
+	"srcd.works/go-git.v4/utils/merkletrie/internal/fsnoder"
+	"srcd.works/go-git.v4/utils/merkletrie/noder"
+
+	. "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type FrameSuite struct{}
+
+var _ = Suite(&FrameSuite{})
+
+func (s *FrameSuite) TestNewFrameFromEmptyDir(c *C) {
+	A, err := fsnoder.New("A()")
+	c.Assert(err, IsNil)
+
+	frame, err := New(A)
+	c.Assert(err, IsNil)
+
+	expectedString := `[]`
+	c.Assert(frame.String(), Equals, expectedString)
+
+	first, ok := frame.First()
+	c.Assert(first, IsNil)
+	c.Assert(ok, Equals, false)
+
+	first, ok = frame.First()
+	c.Assert(first, IsNil)
+	c.Assert(ok, Equals, false)
+
+	l := frame.Len()
+	c.Assert(l, Equals, 0)
+}
+
+func (s *FrameSuite) TestNewFrameFromNonEmpty(c *C) {
+	//        _______A/________
+	//        |     /  \       |
+	//        x    y    B/     C/
+	//                         |
+	//                         z
+	root, err := fsnoder.New("A(x<> y<> B() C(z<>))")
+	c.Assert(err, IsNil)
+	frame, err := New(root)
+	c.Assert(err, IsNil)
+
+	expectedString := `["B", "C", "x", "y"]`
+	c.Assert(frame.String(), Equals, expectedString)
+
+	l := frame.Len()
+	c.Assert(l, Equals, 4)
+
+	checkFirstAndDrop(c, frame, "B", true)
+	l = frame.Len()
+	c.Assert(l, Equals, 3)
+
+	checkFirstAndDrop(c, frame, "C", true)
+	l = frame.Len()
+	c.Assert(l, Equals, 2)
+
+	checkFirstAndDrop(c, frame, "x", true)
+	l = frame.Len()
+	c.Assert(l, Equals, 1)
+
+	checkFirstAndDrop(c, frame, "y", true)
+	l = frame.Len()
+	c.Assert(l, Equals, 0)
+
+	checkFirstAndDrop(c, frame, "", false)
+	l = frame.Len()
+	c.Assert(l, Equals, 0)
+
+	checkFirstAndDrop(c, frame, "", false)
+}
+
+func checkFirstAndDrop(c *C, f *Frame, expectedNodeName string, expectedOK bool) {
+	first, ok := f.First()
+	c.Assert(ok, Equals, expectedOK)
+	if expectedOK {
+		c.Assert(first.Name(), Equals, expectedNodeName)
+	}
+
+	f.Drop()
+}
+
+// a mock noder that returns error when Children() is called
+type errorNoder struct{}
+
+func (e *errorNoder) Hash() []byte   { return nil }
+func (e *errorNoder) Name() string   { return "" }
+func (e *errorNoder) String() string { return "" }
+func (e *errorNoder) IsDir() bool    { return true }
+func (e *errorNoder) Children() ([]noder.Noder, error) {
+	return nil, fmt.Errorf("mock error")
+}
+func (e *errorNoder) NumChildren() (int, error) {
+	return 0, fmt.Errorf("mock error")
+}
+
+func (s *FrameSuite) TestNewFrameErrors(c *C) {
+	_, err := New(&errorNoder{})
+	c.Assert(err, Not(IsNil))
+}
diff --git a/utils/merkletrie/iter.go b/utils/merkletrie/iter.go
new file mode 100644
index 0000000..44cba70
--- /dev/null
+++ b/utils/merkletrie/iter.go
@@ -0,0 +1,212 @@
+package merkletrie
+
+import (
+	"fmt"
+	"io"
+
+	"srcd.works/go-git.v4/utils/merkletrie/internal/frame"
+	"srcd.works/go-git.v4/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).
+type Iter struct {
+	// Tells if the iteration has started.
+	hasStarted bool
+	// 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.
+	frameStack []*frame.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,
+	}
+
+	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
+	if mustDescend {
+		// descend: add a new frame with the current's children.
+		frame, err := frame.New(current)
+		if err != nil {
+			return nil, err
+		}
+		iter.push(frame)
+	} else {
+		// 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...
+	ret = append(ret, iter.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
+// consecuence of this action.
+func (iter *Iter) drop() {
+	frame, ok := iter.top()
+	if !ok {
+		return
+	}
+
+	frame.Drop()
+	// 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()
+	}
+}
diff --git a/utils/merkletrie/iter_test.go b/utils/merkletrie/iter_test.go
new file mode 100644
index 0000000..52d567a
--- /dev/null
+++ b/utils/merkletrie/iter_test.go
@@ -0,0 +1,462 @@
+package merkletrie_test
+
+import (
+	"fmt"
+	"io"
+	"strings"
+	"testing"
+
+	"srcd.works/go-git.v4/utils/merkletrie"
+	"srcd.works/go-git.v4/utils/merkletrie/internal/fsnoder"
+	"srcd.works/go-git.v4/utils/merkletrie/noder"
+
+	. "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type IterSuite struct{}
+
+var _ = Suite(&IterSuite{})
+
+// A test is a list of operations we want to perform on an iterator and
+// their expected results.
+//
+// The operations are expresed as a sequence of `n` and `s`,
+// representing the amount of next and step operations we want to call
+// on the iterator and their order.  For example, an operations value of
+// "nns" means: call a `n`ext, then another `n`ext and finish with a
+// `s`tep.
+//
+// The expeced is the full path of the noders returned by the
+// operations, separated by spaces.
+//
+// For instance:
+//
+//     t := test{
+//         operations: "ns",
+//         expected:   "a a/b"
+//     }
+//
+// means:
+//
+// - the first iterator operation has to be Next, and it must return a
+// node called "a" with no ancestors.
+//
+// - the second operation has to be Step, and it must return a node
+// called "b" with a single ancestor called "a".
+type test struct {
+	operations string
+	expected   string
+}
+
+// Runs a test on the provided iterator, checking that the names of the
+// returned values are correct.  If not, the treeDescription value is
+// printed along with information about mismatch.
+func (t test) run(c *C, iter *merkletrie.Iter,
+	treeDescription string, testNumber int) {
+
+	expectedChunks := strings.Split(t.expected, " ")
+	if t.expected == "" {
+		expectedChunks = []string{}
+	}
+
+	if len(t.operations) < len(expectedChunks) {
+		c.Fatalf("malformed test %d: not enough operations", testNumber)
+		return
+	}
+
+	var obtained noder.Path
+	var err error
+	for i := range t.operations {
+		comment := Commentf("\ntree: %q\ntest #%d (%q)\noperation #%d (%q)",
+			treeDescription, testNumber, t.operations, i, t.operations[i])
+
+		switch t.operations[i] {
+		case 'n':
+			obtained, err = iter.Next()
+			if err != io.EOF {
+				c.Assert(err, IsNil)
+			}
+		case 's':
+			obtained, err = iter.Step()
+			if err != io.EOF {
+				c.Assert(err, IsNil)
+			}
+		default:
+			c.Fatalf("unknown operation at test %d, operation %d (%s)\n",
+				testNumber, i, t.operations[i])
+		}
+		if i >= len(expectedChunks) {
+			c.Assert(err, Equals, io.EOF, comment)
+			continue
+		}
+
+		c.Assert(err, IsNil, comment)
+		c.Assert(obtained.String(), Equals, expectedChunks[i], comment)
+	}
+}
+
+// A testsCollection value represents a tree and a collection of tests
+// we want to perfrom on iterators of that tree.
+//
+// Example:
+//
+//            .
+//            |
+//        ---------
+//        |   |   |
+//        a   b   c
+//            |
+//            z
+//
+//    var foo testCollection = {
+// 	      tree: "(a<> b(z<>) c<>)"
+//     	  tests: []test{
+//            {operations: "nns", expected: "a b b/z"},
+//            {operations: "nnn", expected: "a b c"},
+//		  },
+//    }
+//
+// A new iterator will be build for each test.
+type testsCollection struct {
+	tree  string // a fsnoder description of a tree.
+	tests []test // the collection of tests we want to run
+}
+
+// Executes all the tests in a testsCollection.
+func (tc testsCollection) run(c *C) {
+	root, err := fsnoder.New(tc.tree)
+	c.Assert(err, IsNil)
+
+	for i, t := range tc.tests {
+		iter, err := merkletrie.NewIter(root)
+		c.Assert(err, IsNil)
+		t.run(c, iter, root.String(), i)
+	}
+}
+
+func (s *IterSuite) TestEmptyNamedDir(c *C) {
+	tc := testsCollection{
+		tree: "A()",
+		tests: []test{
+			{operations: "n", expected: ""},
+			{operations: "nn", expected: ""},
+			{operations: "nnn", expected: ""},
+			{operations: "nnns", expected: ""},
+			{operations: "nnnssnsnns", expected: ""},
+			{operations: "s", expected: ""},
+			{operations: "ss", expected: ""},
+			{operations: "sss", expected: ""},
+			{operations: "sssn", expected: ""},
+			{operations: "sssnnsnssn", expected: ""},
+		},
+	}
+	tc.run(c)
+}
+
+func (s *IterSuite) TestEmptyUnnamedDir(c *C) {
+	tc := testsCollection{
+		tree: "()",
+		tests: []test{
+			{operations: "n", expected: ""},
+			{operations: "nn", expected: ""},
+			{operations: "nnn", expected: ""},
+			{operations: "nnns", expected: ""},
+			{operations: "nnnssnsnns", expected: ""},
+			{operations: "s", expected: ""},
+			{operations: "ss", expected: ""},
+			{operations: "sss", expected: ""},
+			{operations: "sssn", expected: ""},
+			{operations: "sssnnsnssn", expected: ""},
+		},
+	}
+	tc.run(c)
+}
+
+func (s *IterSuite) TestOneFile(c *C) {
+	tc := testsCollection{
+		tree: "(a<>)",
+		tests: []test{
+			{operations: "n", expected: "a"},
+			{operations: "nn", expected: "a"},
+			{operations: "nnn", expected: "a"},
+			{operations: "nnns", expected: "a"},
+			{operations: "nnnssnsnns", expected: "a"},
+			{operations: "s", expected: "a"},
+			{operations: "ss", expected: "a"},
+			{operations: "sss", expected: "a"},
+			{operations: "sssn", expected: "a"},
+			{operations: "sssnnsnssn", expected: "a"},
+		},
+	}
+	tc.run(c)
+}
+
+//     root
+//      / \
+//     a   b
+func (s *IterSuite) TestTwoFiles(c *C) {
+	tc := testsCollection{
+		tree: "(a<> b<>)",
+		tests: []test{
+			{operations: "nnn", expected: "a b"},
+			{operations: "nns", expected: "a b"},
+			{operations: "nsn", expected: "a b"},
+			{operations: "nss", expected: "a b"},
+			{operations: "snn", expected: "a b"},
+			{operations: "sns", expected: "a b"},
+			{operations: "ssn", expected: "a b"},
+			{operations: "sss", expected: "a b"},
+		},
+	}
+	tc.run(c)
+}
+
+//     root
+//      |
+//      a
+//      |
+//      b
+func (s *IterSuite) TestDirWithFile(c *C) {
+	tc := testsCollection{
+		tree: "(a(b<>))",
+		tests: []test{
+			{operations: "nnn", expected: "a"},
+			{operations: "nns", expected: "a"},
+			{operations: "nsn", expected: "a a/b"},
+			{operations: "nss", expected: "a a/b"},
+			{operations: "snn", expected: "a"},
+			{operations: "sns", expected: "a"},
+			{operations: "ssn", expected: "a a/b"},
+			{operations: "sss", expected: "a a/b"},
+		},
+	}
+	tc.run(c)
+}
+
+//     root
+//      /|\
+//     c a b
+func (s *IterSuite) TestThreeSiblings(c *C) {
+	tc := testsCollection{
+		tree: "(c<> a<> b<>)",
+		tests: []test{
+			{operations: "nnnn", expected: "a b c"},
+			{operations: "nnns", expected: "a b c"},
+			{operations: "nnsn", expected: "a b c"},
+			{operations: "nnss", expected: "a b c"},
+			{operations: "nsnn", expected: "a b c"},
+			{operations: "nsns", expected: "a b c"},
+			{operations: "nssn", expected: "a b c"},
+			{operations: "nsss", expected: "a b c"},
+			{operations: "snnn", expected: "a b c"},
+			{operations: "snns", expected: "a b c"},
+			{operations: "snsn", expected: "a b c"},
+			{operations: "snss", expected: "a b c"},
+			{operations: "ssnn", expected: "a b c"},
+			{operations: "ssns", expected: "a b c"},
+			{operations: "sssn", expected: "a b c"},
+			{operations: "ssss", expected: "a b c"},
+		},
+	}
+	tc.run(c)
+}
+
+//     root
+//      |
+//      b
+//      |
+//      c
+//      |
+//      a
+func (s *IterSuite) TestThreeVertical(c *C) {
+	tc := testsCollection{
+		tree: "(b(c(a())))",
+		tests: []test{
+			{operations: "nnnn", expected: "b"},
+			{operations: "nnns", expected: "b"},
+			{operations: "nnsn", expected: "b"},
+			{operations: "nnss", expected: "b"},
+			{operations: "nsnn", expected: "b b/c"},
+			{operations: "nsns", expected: "b b/c"},
+			{operations: "nssn", expected: "b b/c b/c/a"},
+			{operations: "nsss", expected: "b b/c b/c/a"},
+			{operations: "snnn", expected: "b"},
+			{operations: "snns", expected: "b"},
+			{operations: "snsn", expected: "b"},
+			{operations: "snss", expected: "b"},
+			{operations: "ssnn", expected: "b b/c"},
+			{operations: "ssns", expected: "b b/c"},
+			{operations: "sssn", expected: "b b/c b/c/a"},
+			{operations: "ssss", expected: "b b/c b/c/a"},
+		},
+	}
+	tc.run(c)
+}
+
+//     root
+//      / \
+//     c   a
+//     |
+//     b
+func (s *IterSuite) TestThreeMix1(c *C) {
+	tc := testsCollection{
+		tree: "(c(b<>) a<>)",
+		tests: []test{
+			{operations: "nnnn", expected: "a c"},
+			{operations: "nnns", expected: "a c"},
+			{operations: "nnsn", expected: "a c c/b"},
+			{operations: "nnss", expected: "a c c/b"},
+			{operations: "nsnn", expected: "a c"},
+			{operations: "nsns", expected: "a c"},
+			{operations: "nssn", expected: "a c c/b"},
+			{operations: "nsss", expected: "a c c/b"},
+			{operations: "snnn", expected: "a c"},
+			{operations: "snns", expected: "a c"},
+			{operations: "snsn", expected: "a c c/b"},
+			{operations: "snss", expected: "a c c/b"},
+			{operations: "ssnn", expected: "a c"},
+			{operations: "ssns", expected: "a c"},
+			{operations: "sssn", expected: "a c c/b"},
+			{operations: "ssss", expected: "a c c/b"},
+		},
+	}
+	tc.run(c)
+}
+
+//     root
+//      / \
+//     b   a
+//         |
+//         c
+func (s *IterSuite) TestThreeMix2(c *C) {
+	tc := testsCollection{
+		tree: "(b() a(c<>))",
+		tests: []test{
+			{operations: "nnnn", expected: "a b"},
+			{operations: "nnns", expected: "a b"},
+			{operations: "nnsn", expected: "a b"},
+			{operations: "nnss", expected: "a b"},
+			{operations: "nsnn", expected: "a a/c b"},
+			{operations: "nsns", expected: "a a/c b"},
+			{operations: "nssn", expected: "a a/c b"},
+			{operations: "nsss", expected: "a a/c b"},
+			{operations: "snnn", expected: "a b"},
+			{operations: "snns", expected: "a b"},
+			{operations: "snsn", expected: "a b"},
+			{operations: "snss", expected: "a b"},
+			{operations: "ssnn", expected: "a a/c b"},
+			{operations: "ssns", expected: "a a/c b"},
+			{operations: "sssn", expected: "a a/c b"},
+			{operations: "ssss", expected: "a a/c b"},
+		},
+	}
+	tc.run(c)
+}
+
+//      root
+//      / | \
+//     /  |  ----
+//    f   d      h --------
+//   /\         /  \      |
+//  e   a      j   b/      g
+//  |  / \     |
+//  l  n  k    icm
+//     |
+//     o
+//     |
+//     p/
+func (s *IterSuite) TestCrazy(c *C) {
+	tc := testsCollection{
+		tree: "(f(e(l<>) a(n(o(p())) k<>)) d<> h(j(i<> c<> m<>) b() g<>))",
+		tests: []test{
+			{operations: "nnnnn", expected: "d f h"},
+			{operations: "nnnns", expected: "d f h"},
+			{operations: "nnnsn", expected: "d f h h/b h/g"},
+			{operations: "nnnss", expected: "d f h h/b h/g"},
+			{operations: "nnsnn", expected: "d f f/a f/e h"},
+			{operations: "nnsns", expected: "d f f/a f/e f/e/l"},
+			{operations: "nnssn", expected: "d f f/a f/a/k f/a/n"},
+			{operations: "nnsss", expected: "d f f/a f/a/k f/a/n"},
+			{operations: "nsnnn", expected: "d f h"},
+			{operations: "nsnns", expected: "d f h"},
+			{operations: "nsnsn", expected: "d f h h/b h/g"},
+			{operations: "nsnss", expected: "d f h h/b h/g"},
+			{operations: "nssnn", expected: "d f f/a f/e h"},
+		},
+	}
+	tc.run(c)
+}
+
+//      .
+//      |
+//      a
+//      |
+//      b
+//     / \
+//    z   h
+//   / \
+//  d   e
+//      |
+//      f
+func (s *IterSuite) TestNewIterFromPath(c *C) {
+	tree, err := fsnoder.New("(a(b(z(d<> e(f<>)) h<>)))")
+	c.Assert(err, IsNil)
+
+	z := find(c, tree, "z")
+
+	iter, err := merkletrie.NewIterFromPath(z)
+	c.Assert(err, IsNil)
+
+	n, err := iter.Next()
+	c.Assert(err, IsNil)
+	c.Assert(n.String(), Equals, "a/b/z/d")
+
+	n, err = iter.Next()
+	c.Assert(err, IsNil)
+	c.Assert(n.String(), Equals, "a/b/z/e")
+
+	n, err = iter.Step()
+	c.Assert(err, IsNil)
+	c.Assert(n.String(), Equals, "a/b/z/e/f")
+
+	_, err = iter.Step()
+	c.Assert(err, Equals, io.EOF)
+}
+
+func find(c *C, tree noder.Noder, name string) noder.Path {
+	iter, err := merkletrie.NewIter(tree)
+	c.Assert(err, IsNil)
+
+	for {
+		current, err := iter.Step()
+		if err != io.EOF {
+			c.Assert(err, IsNil)
+		} else {
+			c.Fatalf("node %s not found in tree %s", name, tree)
+		}
+
+		if current.Name() == name {
+			return current
+		}
+	}
+}
+
+type errorNoder struct{}
+
+func (e *errorNoder) Name() string   { return "" }
+func (e *errorNoder) String() string { return "" }
+func (e *errorNoder) Hash() []byte   { return nil }
+func (e *errorNoder) IsDir() bool    { return true }
+func (e *errorNoder) Children() ([]noder.Noder, error) {
+	return nil, fmt.Errorf("mock error")
+}
+func (e *errorNoder) NumChildren() (int, error) {
+	return 0, fmt.Errorf("mock error")
+}
+
+func (s *IterSuite) TestNewIterFailsOnChildrenErrors(c *C) {
+	_, err := merkletrie.NewIter(&errorNoder{})
+	c.Assert(err, Not(IsNil))
+}