difftree: merkletrie internal package with iterator (#133)

9 files changed, 1004 insertions, 0 deletions

diff --git a/difftree/internal/radixmerkle/doc.go b/difftree/internal/radixmerkle/doc.go
new file mode 100644
index 0000000..f8c3b2f
--- /dev/null
+++ b/difftree/internal/radixmerkle/doc.go
@@ -0,0 +1,30 @@
+package merkletrie
+
+/*
+Package merkletrie gives support for n-ary trees that are at the same
+time Merkle trees and Radix trees, and provides an efficient tree
+comparison algorithm for them.
+
+Git trees are Radix n-ary trees in virtue of the names of their
+tree entries.  At the same time, git trees are Merkle trees thanks to
+their hashes.
+
+When comparing git trees, the simple approach of alphabetically sorting
+their elements and comparing the resulting lists is not enough as it
+depends linearly on the number of files in the trees: When a directory
+has lots of files but none of them has been modified, this approach is
+very expensive.  We can do better by prunning whole directories that
+have not change, by just by looking at their hashes.  This package
+provides the tools to do exactly that.
+
+This package defines Radix-Merkle trees as nodes that should have:
+- a hash: the Merkle part of the Radix-Merkle tree
+- a key: the Radix part of the Radix-Merkle tree
+
+The Merkle hash condition is not enforced by this package though.  This
+means that node hashes doesn't have to take into account the hashes of
+their children,  which is good for testing purposes.
+
+Nodes in the Radix-Merkle tree are abstracted by the Noder interface.
+The intended use is that git.Tree implements this interface.
+*/
diff --git a/difftree/internal/radixmerkle/frame.go b/difftree/internal/radixmerkle/frame.go
new file mode 100644
index 0000000..a40c6ad
--- /dev/null
+++ b/difftree/internal/radixmerkle/frame.go
@@ -0,0 +1,79 @@
+package merkletrie
+
+import (
+	"bytes"
+	"fmt"
+)
+
+const sep = "/"
+
+// A frame represents siblings in a trie, along with the path to get to
+// them.  For example the frame for the node with key `b` in this trie:
+//
+//                    a
+//                   / \
+//                  /   \
+//                 /     \
+//                b       c
+//               /|\     / \
+//              y z x   d   e
+//                |
+//                g
+//
+// would be:
+//
+//     f := frame{
+//         base: "a/b",           // path to the siblings
+//         stack: []Node{z, y, x} // in reverse alphabetical order
+//     }
+type frame struct {
+	base  string  // absolute key of their parents
+	stack []Noder // siblings, sorted in reverse alphabetical order by key
+}
+
+// newFrame returns a frame for the children of a node n.
+func newFrame(parentAbsoluteKey string, n Noder) *frame {
+	return &frame{
+		base:  parentAbsoluteKey + sep + n.Key(),
+		stack: n.Children(),
+	}
+}
+
+func (f *frame) String() string {
+	var buf bytes.Buffer
+	_, _ = buf.WriteString(fmt.Sprintf("base=%q, stack=[", f.base))
+
+	sep := ""
+	for _, e := range f.stack {
+		_, _ = buf.WriteString(sep)
+		sep = ", "
+		_, _ = buf.WriteString(fmt.Sprintf("%q", e.Key()))
+	}
+
+	_ = buf.WriteByte(']')
+
+	return buf.String()
+}
+
+func (f *frame) top() (Noder, bool) {
+	if len(f.stack) == 0 {
+		return nil, false
+	}
+
+	top := len(f.stack) - 1
+
+	return f.stack[top], true
+}
+
+func (f *frame) pop() (Noder, bool) {
+	if len(f.stack) == 0 {
+		return nil, false
+	}
+
+	top := len(f.stack) - 1
+	ret := f.stack[top]
+	f.stack[top] = nil
+	f.stack = f.stack[:top]
+
+	return ret, true
+}
diff --git a/difftree/internal/radixmerkle/frame_test.go b/difftree/internal/radixmerkle/frame_test.go
new file mode 100644
index 0000000..0ef036a
--- /dev/null
+++ b/difftree/internal/radixmerkle/frame_test.go
@@ -0,0 +1,69 @@
+package merkletrie
+
+import . "gopkg.in/check.v1"
+
+type FrameSuite struct{}
+
+var _ = Suite(&FrameSuite{})
+
+func (s *FrameSuite) TestNewFrameFromLeaf(c *C) {
+	n := newNode(
+		[]byte("hash"),
+		"key",
+		[]*node{},
+	)
+
+	frame := newFrame("foo", n)
+
+	expectedString := `base="foo/key", stack=[]`
+	c.Assert(frame.String(), Equals, expectedString)
+
+	obtainedTopNode, obtainedTopOK := frame.top()
+	c.Assert(obtainedTopNode, IsNil)
+	c.Assert(obtainedTopOK, Equals, false)
+
+	obtainedPopNode, obtainedPopOK := frame.top()
+	c.Assert(obtainedPopNode, IsNil)
+	c.Assert(obtainedPopOK, Equals, false)
+}
+
+func (s *FrameSuite) TestNewFrameFromParent(c *C) {
+	leaf0 := newNode([]byte("leaf0 hash"), "leaf0 key", []*node{})
+	leaf1 := newNode([]byte("leaf1 hash"), "leaf1 key", []*node{})
+	leaf2 := newNode([]byte("leaf2 hash"), "leaf2 key", []*node{})
+	leaf3 := newNode([]byte("leaf3 hash"), "leaf3 key", []*node{})
+	parent := newNode(
+		[]byte("parent hash"),
+		"parent key",
+		[]*node{leaf3, leaf0, leaf2, leaf1}, // not alphabetically sorted
+	)
+
+	frame := newFrame("foo", parent)
+
+	expectedString := `base="foo/parent key", stack=["leaf3 key", "leaf2 key", "leaf1 key", "leaf0 key"]`
+	c.Assert(frame.String(), Equals, expectedString)
+
+	checkTopAndPop(c, frame, leaf0, true)
+	checkTopAndPop(c, frame, leaf1, true)
+	checkTopAndPop(c, frame, leaf2, true)
+	checkTopAndPop(c, frame, leaf3, true)
+	checkTopAndPop(c, frame, nil, false)
+}
+
+func checkTopAndPop(c *C, f *frame, expectedNode *node, expectedOK bool) {
+	n, ok := f.top()
+	if expectedNode == nil {
+		c.Assert(n, IsNil)
+	} else {
+		c.Assert(n, DeepEquals, expectedNode)
+	}
+	c.Assert(ok, Equals, expectedOK)
+
+	n, ok = f.pop()
+	if expectedNode == nil {
+		c.Assert(n, IsNil)
+	} else {
+		c.Assert(n, DeepEquals, expectedNode)
+	}
+	c.Assert(ok, Equals, expectedOK)
+}
diff --git a/difftree/internal/radixmerkle/iter.go b/difftree/internal/radixmerkle/iter.go
new file mode 100644
index 0000000..e175966
--- /dev/null
+++ b/difftree/internal/radixmerkle/iter.go
@@ -0,0 +1,167 @@
+package merkletrie
+
+// Iter is a radix tree iterator that will traverse the trie in
+// depth-first pre-order.  Entries are traversed in (case-sensitive)
+// alphabetical order for each level.
+//
+// This is the kind of traversal you will expect when listing
+// ordinary files and directories recursively, for example:
+//
+//             Trie           Traversal order
+//             ----           ---------------
+//              .
+//            / | \           a
+//           /  |  \          b
+//          b   a   z   ===>  b/a
+//         / \                b/c
+//        c   a               z
+//
+//
+// The Step method will return the next item, the Next method will do
+// the same but without descending deeper into the tree (i.e. skipping
+// the contents of "directories").
+//
+// The name of the type and its methods are based on the well known "next"
+// and "step" operations, quite common in debuggers, like gdb.
+type Iter struct {
+	// tells if the iteration has started.
+	hasStarted bool
+	// Each level of the tree is represented as a frame, this stack
+	// keeps track of the frames wrapping the current iterator position.
+	// The iterator will "step" into a node by adding its frame to the
+	// stack, or go to the next element at the same level by poping the
+	// current frame.
+	frameStack []*frame
+}
+
+// NewIter returns a new iterator for the trie with its root at n.
+func NewIter(n Noder) *Iter {
+	ret := &Iter{}
+	ret.push(newFrame("", n))
+
+	return ret
+}
+
+func (iter *Iter) top() (*frame, bool) {
+	if len(iter.frameStack) == 0 {
+		return nil, false
+	}
+
+	top := len(iter.frameStack) - 1
+
+	return iter.frameStack[top], true
+}
+
+func (iter *Iter) pop() (*frame, bool) {
+	if len(iter.frameStack) == 0 {
+		return nil, false
+	}
+
+	top := len(iter.frameStack) - 1
+	ret := iter.frameStack[top]
+	iter.frameStack[top] = nil
+	iter.frameStack = iter.frameStack[:top]
+
+	return ret, true
+}
+
+func (iter *Iter) push(f *frame) {
+	iter.frameStack = append(iter.frameStack, f)
+}
+
+const (
+	descend     = true
+	dontDescend = false
+)
+
+// Next returns the next node without descending deeper into the tree
+// and true.  If there are no more entries it returns nil and false.
+func (iter *Iter) Next() (Noder, bool) {
+	return iter.advance(dontDescend)
+}
+
+// Step returns the next node in the tree, descending deeper into it if
+// needed. If there are no more nodes in the tree, it returns nil and
+// false.
+func (iter *Iter) Step() (Noder, bool) {
+	return iter.advance(descend)
+}
+
+// advances the iterator in whatever direction you want: descend or
+// dontDescend.
+func (iter *Iter) advance(mustDescend bool) (Noder, bool) {
+	node, ok := iter.current()
+	if !ok {
+		return nil, false
+	}
+
+	// The first time we just return the current node.
+	if !iter.hasStarted {
+		iter.hasStarted = true
+		return node, ok
+	}
+	// following advances will involve dropping already seen nodes
+	// or getting into their children
+
+	ignoreChildren := node.NumChildren() == 0 || !mustDescend
+	if ignoreChildren {
+		// if we must ignore the current node children, just drop
+		// it and find the next one in the existing frames.
+		_ = iter.drop()
+		node, ok = iter.current()
+		return node, ok
+	}
+
+	// if we must descend into the current's node children, drop the
+	// parent and add a new frame with its children.
+	_ = iter.drop()
+	iter.push(newFrame(node.Key(), node))
+	node, _ = iter.current()
+
+	return node, true
+}
+
+// returns the current frame and the current node (i.e. the ones at the
+// top of their respective stacks.
+func (iter *Iter) current() (Noder, bool) {
+	f, ok := iter.top()
+	if !ok {
+		return nil, false
+	}
+
+	n, ok := f.top()
+	if !ok {
+		return nil, false
+	}
+
+	return n, true
+}
+
+// removes the current node and all the frames that become empty as a
+// consecuence of this action. It returns true if something was dropped,
+// and false if there were no more nodes in the iterator.
+func (iter *Iter) drop() bool {
+	frame, ok := iter.top()
+	if !ok {
+		return false
+	}
+
+	_, ok = frame.pop()
+	if !ok {
+		return false
+	}
+
+	for { // remove empty frames
+		if len(frame.stack) != 0 {
+			break
+		}
+
+		_, _ = iter.pop()
+		frame, ok = iter.top()
+		if !ok {
+			break
+		}
+	}
+
+	return true
+}
diff --git a/difftree/internal/radixmerkle/iter_fixtures_test.go b/difftree/internal/radixmerkle/iter_fixtures_test.go
new file mode 100644
index 0000000..20bddaf
--- /dev/null
+++ b/difftree/internal/radixmerkle/iter_fixtures_test.go
@@ -0,0 +1,330 @@
+package merkletrie
+
+// this files contains fixtures for testing the Iter.
+//
+// - iter... functions returns iterators for newly created trees
+//   for example:
+//
+//   + iterLeaf returns an iterator for simple tree with just the root.
+//
+//   + iter2Horizontal returns an iterator for a tree with 2 nodes, both
+//     childs of the root.
+//
+// - runs... contains sets of tests, indexed by a string that helps
+//   to understand each test: "nsn" means next, then step, then next
+//   again.  The test also contains the expected keys of the nodes you
+//   will get when calling the operations over the correspoding trees:
+//   Example: runs2HorizontalSorted with iter2HorizontalSorted and so on.
+
+func iterLeaf() *Iter {
+	root := newNode(hash, "root", empty)
+	return NewIter(root)
+}
+
+var runs0 = map[string][]test{
+	"nn": {{next, ""}, {next, ""}},
+	"ns": {{next, ""}, {step, ""}},
+	"sn": {{step, ""}, {next, ""}},
+	"ss": {{step, ""}, {step, ""}},
+}
+
+//   root
+//    |
+//    a
+func iter1() *Iter {
+	a := newNode(hash, "a", empty)
+	root := newNode(hash, "root", []*node{a})
+	return NewIter(root)
+}
+
+var runs1 = map[string][]test{
+	"nn": {{next, "a"}, {next, ""}},
+	"ns": {{next, "a"}, {step, ""}},
+	"sn": {{step, "a"}, {next, ""}},
+	"ss": {{step, "a"}, {step, ""}},
+}
+
+//     root
+//      / \
+//     a   b
+func iter2HorizontalSorted() *Iter {
+	a := newNode(hash, "a", empty)
+	b := newNode(hash, "b", empty)
+	root := newNode(hash, "root", []*node{a, b})
+	return NewIter(root)
+}
+
+//     root
+//      / \
+//     b   a
+func iter2HorizontalReverse() *Iter {
+	a := newNode(hash, "a", empty)
+	b := newNode(hash, "b", empty)
+	root := newNode(hash, "root", []*node{b, a})
+	return NewIter(root)
+}
+
+var runs2Horizontal = map[string][]test{
+	"nnn": {{next, "a"}, {next, "b"}, {next, ""}},
+	"nns": {{next, "a"}, {next, "b"}, {step, ""}},
+	"nsn": {{next, "a"}, {step, "b"}, {next, ""}},
+	"nss": {{next, "a"}, {step, "b"}, {step, ""}},
+	"snn": {{step, "a"}, {next, "b"}, {next, ""}},
+	"sns": {{step, "a"}, {next, "b"}, {step, ""}},
+	"ssn": {{step, "a"}, {step, "b"}, {next, ""}},
+	"sss": {{step, "a"}, {step, "b"}, {step, ""}},
+}
+
+//     root
+//      |
+//      a
+//      |
+//      b
+func iter2VerticalSorted() *Iter {
+	b := newNode(hash, "b", empty)
+	a := newNode(hash, "a", []*node{b})
+	root := newNode(hash, "root", []*node{a})
+	return NewIter(root)
+}
+
+var runs2VerticalSorted = map[string][]test{
+	"nnn": {{next, "a"}, {next, ""}, {next, ""}},
+	"nns": {{next, "a"}, {next, ""}, {step, ""}},
+	"nsn": {{next, "a"}, {step, "b"}, {next, ""}},
+	"nss": {{next, "a"}, {step, "b"}, {step, ""}},
+	"snn": {{step, "a"}, {next, ""}, {next, ""}},
+	"sns": {{step, "a"}, {next, ""}, {step, ""}},
+	"ssn": {{step, "a"}, {step, "b"}, {next, ""}},
+	"sss": {{step, "a"}, {step, "b"}, {step, ""}},
+}
+
+//     root
+//      |
+//      b
+//      |
+//      a
+func iter2VerticalReverse() *Iter {
+	a := newNode(hash, "a", empty)
+	b := newNode(hash, "b", []*node{a})
+	root := newNode(hash, "root", []*node{b})
+	return NewIter(root)
+}
+
+var runs2VerticalReverse = map[string][]test{
+	"nnn": {{next, "b"}, {next, ""}, {next, ""}},
+	"nns": {{next, "b"}, {next, ""}, {step, ""}},
+	"nsn": {{next, "b"}, {step, "a"}, {next, ""}},
+	"nss": {{next, "b"}, {step, "a"}, {step, ""}},
+	"snn": {{step, "b"}, {next, ""}, {next, ""}},
+	"sns": {{step, "b"}, {next, ""}, {step, ""}},
+	"ssn": {{step, "b"}, {step, "a"}, {next, ""}},
+	"sss": {{step, "b"}, {step, "a"}, {step, ""}},
+}
+
+//     root
+//      /|\
+//     c a b
+func iter3Horizontal() *Iter {
+	a := newNode(hash, "a", empty)
+	b := newNode(hash, "b", empty)
+	c := newNode(hash, "c", empty)
+	root := newNode(hash, "root", []*node{c, a, b})
+	return NewIter(root)
+}
+
+var runs3Horizontal = map[string][]test{
+	"nnnn": {{next, "a"}, {next, "b"}, {next, "c"}, {next, ""}},
+	"nnns": {{next, "a"}, {next, "b"}, {next, "c"}, {step, ""}},
+	"nnsn": {{next, "a"}, {next, "b"}, {step, "c"}, {next, ""}},
+	"nnss": {{next, "a"}, {next, "b"}, {step, "c"}, {step, ""}},
+	"nsnn": {{next, "a"}, {step, "b"}, {next, "c"}, {next, ""}},
+	"nsns": {{next, "a"}, {step, "b"}, {next, "c"}, {step, ""}},
+	"nssn": {{next, "a"}, {step, "b"}, {step, "c"}, {next, ""}},
+	"nsss": {{next, "a"}, {step, "b"}, {step, "c"}, {step, ""}},
+	"snnn": {{step, "a"}, {next, "b"}, {next, "c"}, {next, ""}},
+	"snns": {{step, "a"}, {next, "b"}, {next, "c"}, {step, ""}},
+	"snsn": {{step, "a"}, {next, "b"}, {step, "c"}, {next, ""}},
+	"snss": {{step, "a"}, {next, "b"}, {step, "c"}, {step, ""}},
+	"ssnn": {{step, "a"}, {step, "b"}, {next, "c"}, {next, ""}},
+	"ssns": {{step, "a"}, {step, "b"}, {next, "c"}, {step, ""}},
+	"sssn": {{step, "a"}, {step, "b"}, {step, "c"}, {next, ""}},
+	"ssss": {{step, "a"}, {step, "b"}, {step, "c"}, {step, ""}},
+}
+
+//     root
+//      |
+//      b
+//      |
+//      c
+//      |
+//      a
+func iter3Vertical() *Iter {
+	a := newNode(hash, "a", empty)
+	c := newNode(hash, "c", []*node{a})
+	b := newNode(hash, "b", []*node{c})
+	root := newNode(hash, "root", []*node{b})
+	return NewIter(root)
+}
+
+var runs3Vertical = map[string][]test{
+	"nnnn": {{next, "b"}, {next, ""}, {next, ""}, {next, ""}},
+	"nnns": {{next, "b"}, {next, ""}, {next, ""}, {step, ""}},
+	"nnsn": {{next, "b"}, {next, ""}, {step, ""}, {next, ""}},
+	"nnss": {{next, "b"}, {next, ""}, {step, ""}, {step, ""}},
+	"nsnn": {{next, "b"}, {step, "c"}, {next, ""}, {next, ""}},
+	"nsns": {{next, "b"}, {step, "c"}, {next, ""}, {step, ""}},
+	"nssn": {{next, "b"}, {step, "c"}, {step, "a"}, {next, ""}},
+	"nsss": {{next, "b"}, {step, "c"}, {step, "a"}, {step, ""}},
+	"snnn": {{step, "b"}, {next, ""}, {next, ""}, {next, ""}},
+	"snns": {{step, "b"}, {next, ""}, {next, ""}, {step, ""}},
+	"snsn": {{step, "b"}, {next, ""}, {step, ""}, {next, ""}},
+	"snss": {{step, "b"}, {next, ""}, {step, ""}, {step, ""}},
+	"ssnn": {{step, "b"}, {step, "c"}, {next, ""}, {next, ""}},
+	"ssns": {{step, "b"}, {step, "c"}, {next, ""}, {step, ""}},
+	"sssn": {{step, "b"}, {step, "c"}, {step, "a"}, {next, ""}},
+	"ssss": {{step, "b"}, {step, "c"}, {step, "a"}, {step, ""}},
+}
+
+//     root
+//      / \
+//     c   a
+//     |
+//     b
+func iter3Mix1() *Iter {
+	a := newNode(hash, "a", empty)
+	b := newNode(hash, "b", empty)
+	c := newNode(hash, "c", []*node{b})
+	root := newNode(hash, "root", []*node{c, a})
+	return NewIter(root)
+}
+
+var runs3Mix1 = map[string][]test{
+	"nnnn": {{next, "a"}, {next, "c"}, {next, ""}, {next, ""}},
+	"nnns": {{next, "a"}, {next, "c"}, {next, ""}, {step, ""}},
+	"nnsn": {{next, "a"}, {next, "c"}, {step, "b"}, {next, ""}},
+	"nnss": {{next, "a"}, {next, "c"}, {step, "b"}, {step, ""}},
+	"nsnn": {{next, "a"}, {step, "c"}, {next, ""}, {next, ""}},
+	"nsns": {{next, "a"}, {step, "c"}, {next, ""}, {step, ""}},
+	"nssn": {{next, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
+	"nsss": {{next, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
+	"snnn": {{step, "a"}, {next, "c"}, {next, ""}, {next, ""}},
+	"snns": {{step, "a"}, {next, "c"}, {next, ""}, {step, ""}},
+	"snsn": {{step, "a"}, {next, "c"}, {step, "b"}, {next, ""}},
+	"snss": {{step, "a"}, {next, "c"}, {step, "b"}, {step, ""}},
+	"ssnn": {{step, "a"}, {step, "c"}, {next, ""}, {next, ""}},
+	"ssns": {{step, "a"}, {step, "c"}, {next, ""}, {step, ""}},
+	"sssn": {{step, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
+	"ssss": {{step, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
+}
+
+//     root
+//      / \
+//     b   a
+//         |
+//         c
+func iter3Mix2() *Iter {
+	b := newNode(hash, "b", empty)
+	c := newNode(hash, "c", empty)
+	a := newNode(hash, "a", []*node{c})
+	root := newNode(hash, "root", []*node{b, a})
+	return NewIter(root)
+}
+
+var runs3Mix2 = map[string][]test{
+	"nnnn": {{next, "a"}, {next, "b"}, {next, ""}, {next, ""}},
+	"nnns": {{next, "a"}, {next, "b"}, {next, ""}, {step, ""}},
+	"nnsn": {{next, "a"}, {next, "b"}, {step, ""}, {next, ""}},
+	"nnss": {{next, "a"}, {next, "b"}, {step, ""}, {step, ""}},
+	"nsnn": {{next, "a"}, {step, "c"}, {next, "b"}, {next, ""}},
+	"nsns": {{next, "a"}, {step, "c"}, {next, "b"}, {step, ""}},
+	"nssn": {{next, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
+	"nsss": {{next, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
+	"snnn": {{step, "a"}, {next, "b"}, {next, ""}, {next, ""}},
+	"snns": {{step, "a"}, {next, "b"}, {next, ""}, {step, ""}},
+	"snsn": {{step, "a"}, {next, "b"}, {step, ""}, {next, ""}},
+	"snss": {{step, "a"}, {next, "b"}, {step, ""}, {step, ""}},
+	"ssnn": {{step, "a"}, {step, "c"}, {next, "b"}, {next, ""}},
+	"ssns": {{step, "a"}, {step, "c"}, {next, "b"}, {step, ""}},
+	"sssn": {{step, "a"}, {step, "c"}, {step, "b"}, {next, ""}},
+	"ssss": {{step, "a"}, {step, "c"}, {step, "b"}, {step, ""}},
+}
+
+//      root
+//      / | \
+//     /  |  ----
+//    f   d      h --------
+//   /\         /  \      |
+//  e   a      j   b      g
+//  |  / \     |
+//  l  n  k    icm
+//     |
+//     o
+//     |
+//     p
+func iterCrazy() *Iter {
+	l := newNode(hash, "l", empty)
+	e := newNode(hash, "e", []*node{l})
+
+	p := newNode(hash, "p", empty)
+	o := newNode(hash, "o", []*node{p})
+	n := newNode(hash, "n", []*node{o})
+	k := newNode(hash, "k", empty)
+	a := newNode(hash, "a", []*node{n, k})
+	f := newNode(hash, "f", []*node{e, a})
+
+	d := newNode(hash, "d", empty)
+
+	i := newNode(hash, "i", empty)
+	c := newNode(hash, "c", empty)
+	m := newNode(hash, "m", empty)
+	j := newNode(hash, "j", []*node{i, c, m})
+	b := newNode(hash, "b", empty)
+	g := newNode(hash, "g", empty)
+	h := newNode(hash, "h", []*node{j, b, g})
+
+	root := newNode(hash, "root", []*node{f, d, h})
+	return NewIter(root)
+}
+
+var (
+	n = next
+	s = step
+)
+
+var runsCrazy = map[string][]test{
+	"nn nn n": {{n, "d"}, {n, "f"}, {n, "h"}, {n, ""}, {n, ""}},
+	"nn nn s": {{n, "d"}, {n, "f"}, {n, "h"}, {n, ""}, {s, ""}},
+	"nn ns n": {{n, "d"}, {n, "f"}, {n, "h"}, {s, "b"}, {n, "g"}},
+	"nn ns s": {{n, "d"}, {n, "f"}, {n, "h"}, {s, "b"}, {s, "g"}},
+	"nn sn n": {{n, "d"}, {n, "f"}, {s, "a"}, {n, "e"}, {n, "h"}},
+	"nn sn s": {{n, "d"}, {n, "f"}, {s, "a"}, {n, "e"}, {s, "l"}},
+	"nn ss n": {{n, "d"}, {n, "f"}, {s, "a"}, {s, "k"}, {n, "n"}},
+	"nn ss s": {{n, "d"}, {n, "f"}, {s, "a"}, {s, "k"}, {s, "n"}},
+	"ns nn n": {{n, "d"}, {s, "f"}, {n, "h"}, {n, ""}, {n, ""}},
+	"ns nn s": {{n, "d"}, {s, "f"}, {n, "h"}, {n, ""}, {s, ""}},
+	"ns ns n": {{n, "d"}, {s, "f"}, {n, "h"}, {s, "b"}, {n, "g"}},
+	"ns ns s": {{n, "d"}, {s, "f"}, {n, "h"}, {s, "b"}, {s, "g"}},
+	"ns sn n": {{n, "d"}, {s, "f"}, {s, "a"}, {n, "e"}, {n, "h"}},
+
+	"ns ss ns ss": {
+		{n, "d"}, {s, "f"},
+		{s, "a"}, {s, "k"},
+		{n, "n"}, {s, "o"},
+		{s, "p"}, {s, "e"},
+	},
+
+	"ns ss ns sn": {
+		{n, "d"}, {s, "f"},
+		{s, "a"}, {s, "k"},
+		{n, "n"}, {s, "o"},
+		{s, "p"}, {n, "e"},
+	},
+
+	"nn ns ns ss nn": {
+		{n, "d"}, {n, "f"},
+		{n, "h"}, {s, "b"},
+		{n, "g"}, {s, "j"},
+		{s, "c"}, {s, "i"},
+		{n, "m"}, {n, ""},
+	},
+}
diff --git a/difftree/internal/radixmerkle/iter_test.go b/difftree/internal/radixmerkle/iter_test.go
new file mode 100644
index 0000000..65116e1
--- /dev/null
+++ b/difftree/internal/radixmerkle/iter_test.go
@@ -0,0 +1,176 @@
+package merkletrie
+
+import . "gopkg.in/check.v1"
+
+type IterSuite struct{}
+
+var _ = Suite(&IterSuite{})
+
+// we don't care about hashes for iterating the tree, so
+// use this hash for every object
+var hash = []byte{}
+
+// leafs have no children, use this empty list.
+var empty = []*node{}
+
+// test a defined as an operation to run on an iterator and the key of
+// the node expected to be returned by the operation.  Use "" as the
+// expected key for when there are no more objects in the tree.
+type test struct {
+	operation int    // next or step
+	expected  string // key of the expected node, "" for nil node
+}
+
+// test.operation
+const (
+	next = iota
+	step
+)
+
+// goes over a list of tests, calling each operation on the iter and
+// checking that the obtained result is equal to the expected result
+func runTests(c *C, description string, iter *Iter, list []test) {
+	var obtained Noder
+	var ok bool
+	var comment CommentInterface
+
+	for i, t := range list {
+		comment = Commentf("description %q, operation #%d",
+			description, i+1)
+
+		switch t.operation {
+		case next:
+			obtained, ok = iter.Next()
+		case step:
+			obtained, ok = iter.Step()
+		default:
+			c.Fatalf("invalid operation %d", t.operation)
+		}
+
+		if t.expected == "" {
+			c.Assert(ok, Equals, false, comment)
+			c.Assert(obtained, IsNil, comment)
+		} else {
+			c.Assert(ok, Equals, true, comment)
+			c.Assert(obtained.Key(), Equals, t.expected, comment)
+		}
+	}
+}
+
+// a simple tree consisting on just a leaf
+func (s *IterSuite) TestLeaf(c *C) {
+	for description, tests := range runs0 {
+		runTests(c, description, iterLeaf(), tests)
+	}
+}
+
+//     root
+//       |
+//       a
+func (s *IterSuite) TestOneChild(c *C) {
+	for description, tests := range runs1 {
+		runTests(c, description, iter1(), tests)
+	}
+}
+
+//     root
+//      / \
+//     a   b
+func (s *IterSuite) Test2HorizontalSorted(c *C) {
+	for description, tests := range runs2Horizontal {
+		runTests(c, description, iter2HorizontalSorted(), tests)
+	}
+}
+
+//     root
+//      / \
+//     b   a
+func (s *IterSuite) Test2HorizontalReverse(c *C) {
+	for description, tests := range runs2Horizontal {
+		runTests(c, description, iter2HorizontalReverse(), tests)
+	}
+}
+
+//     root
+//      |
+//      a
+//      |
+//      b
+func (s *IterSuite) Test2VerticalSorted(c *C) {
+	for description, tests := range runs2VerticalSorted {
+		runTests(c, description, iter2VerticalSorted(), tests)
+	}
+}
+
+//     root
+//      |
+//      b
+//      |
+//      a
+func (s *IterSuite) Test2VerticalReverse(c *C) {
+	for description, tests := range runs2VerticalReverse {
+		runTests(c, description, iter2VerticalReverse(), tests)
+	}
+}
+
+//     root
+//      /|\
+//     c a b
+func (s *IterSuite) Test3Horizontal(c *C) {
+	for description, tests := range runs3Horizontal {
+		runTests(c, description, iter3Horizontal(), tests)
+	}
+}
+
+//     root
+//      |
+//      b
+//      |
+//      c
+//      |
+//      a
+func (s *IterSuite) Test3Vertical(c *C) {
+	for description, tests := range runs3Vertical {
+		runTests(c, description, iter3Vertical(), tests)
+	}
+}
+
+//     root
+//      / \
+//     c   a
+//     |
+//     b
+func (s *IterSuite) Test3Mix1(c *C) {
+	for description, tests := range runs3Mix1 {
+		runTests(c, description, iter3Mix1(), tests)
+	}
+}
+
+//     root
+//      / \
+//     b   a
+//         |
+//         c
+func (s *IterSuite) Test3Mix2(c *C) {
+	for description, tests := range runs3Mix2 {
+		runTests(c, description, iter3Mix2(), tests)
+	}
+}
+
+//      root
+//      / | \
+//     /  |  ----
+//    f   d      h --------
+//   /\         /  \      |
+//  e   a      j   b      g
+//  |  / \     |
+//  l  n  k    icm
+//     |
+//     o
+//     |
+//     p
+func (s *IterSuite) TestCrazy(c *C) {
+	for description, tests := range runsCrazy {
+		runTests(c, description, iterCrazy(), tests)
+	}
+}
diff --git a/difftree/internal/radixmerkle/node.go b/difftree/internal/radixmerkle/node.go
new file mode 100644
index 0000000..99be5b8
--- /dev/null
+++ b/difftree/internal/radixmerkle/node.go
@@ -0,0 +1,65 @@
+package merkletrie
+
+import (
+	"sort"
+	"strings"
+)
+
+// A node is a Noder implementation for testing purposes:  It is easier
+// to create test trees using nodes than using real git tree objects.
+type node struct {
+	hash     []byte
+	key      string
+	children []*node
+}
+
+// newNode returns a new Node with the given hash, key and children
+// (children can be specified in any order).
+func newNode(hash []byte, key string, children []*node) *node {
+	sort.Sort(reverseAlphabeticallyByKey(children))
+
+	return &node{
+		hash:     hash,
+		key:      key,
+		children: children,
+	}
+}
+
+// Hash returns the hash of the node.
+func (n *node) Hash() []byte {
+	return n.hash
+}
+
+// Key returns the key of the node.
+func (n *node) Key() string {
+	return n.key
+}
+
+// NumChildren returns the number of children.
+func (n *node) NumChildren() int {
+	return len(n.children)
+}
+
+// Children returns the node's children in reverse key alphabetical
+// order.
+func (n *node) Children() []Noder {
+	ret := make([]Noder, n.NumChildren())
+	for i := range n.children {
+		ret[i] = n.children[i]
+	}
+	return ret
+}
+
+type reverseAlphabeticallyByKey []*node
+
+func (a reverseAlphabeticallyByKey) Len() int {
+	return len(a)
+}
+
+func (a reverseAlphabeticallyByKey) Swap(i, j int) {
+	a[i], a[j] = a[j], a[i]
+}
+
+func (a reverseAlphabeticallyByKey) Less(i, j int) bool {
+	return strings.Compare(a[i].key, a[j].key) > 0
+}
diff --git a/difftree/internal/radixmerkle/node_test.go b/difftree/internal/radixmerkle/node_test.go
new file mode 100644
index 0000000..1622952
--- /dev/null
+++ b/difftree/internal/radixmerkle/node_test.go
@@ -0,0 +1,68 @@
+package merkletrie
+
+import (
+	"testing"
+
+	. "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type NodeSuite struct{}
+
+var _ = Suite(&NodeSuite{})
+
+func (s *NodeSuite) TestHash(c *C) {
+	n := newNode([]byte("the_hash"), "the_key", []*node{})
+
+	expected := []byte("the_hash")
+	c.Assert(expected, DeepEquals, n.Hash())
+}
+
+func (s *NodeSuite) TestKey(c *C) {
+	n := newNode([]byte("the_hash"), "the_key", []*node{})
+
+	expected := "the_key"
+	c.Assert(expected, Equals, n.Key())
+}
+
+func (s *NodeSuite) TestNoChildren(c *C) {
+	n := newNode([]byte{}, "", []*node{})
+
+	expectedNumChildren := 0
+	c.Assert(n.NumChildren(), Equals, expectedNumChildren)
+
+	expectedChildren := []Noder{}
+	c.Assert(n.Children(), DeepEquals, expectedChildren)
+}
+
+func (s *NodeSuite) TestOneChild(c *C) {
+	child := newNode([]byte("child"), "child", []*node{})
+	parent := newNode([]byte("parent"), "parent", []*node{child})
+
+	expectedNumChildren := 1
+	c.Assert(parent.NumChildren(), Equals, expectedNumChildren)
+
+	expectedChildren := []Noder{Noder(child)}
+	c.Assert(parent.Children(), DeepEquals, expectedChildren)
+}
+
+func (s *NodeSuite) TestManyChildren(c *C) {
+	child0 := newNode([]byte("child0"), "child0", []*node{})
+	child1 := newNode([]byte("child1"), "child1", []*node{})
+	child2 := newNode([]byte("child2"), "child2", []*node{})
+	child3 := newNode([]byte("child3"), "child3", []*node{})
+	// children are added unsorted.
+	parent := newNode([]byte("parent"), "parent", []*node{child1, child3, child0, child2})
+
+	expectedNumChildren := 4
+	c.Assert(parent.NumChildren(), Equals, expectedNumChildren)
+
+	expectedChildren := []Noder{ // sorted alphabetically by key
+		Noder(child3),
+		Noder(child2),
+		Noder(child1),
+		Noder(child0),
+	}
+	c.Assert(parent.Children(), DeepEquals, expectedChildren)
+}
diff --git a/difftree/internal/radixmerkle/noder.go b/difftree/internal/radixmerkle/noder.go
new file mode 100644
index 0000000..3566657
--- /dev/null
+++ b/difftree/internal/radixmerkle/noder.go
@@ -0,0 +1,20 @@
+package merkletrie
+
+// The Noder interface is implemented by the elements of a Merkle Trie.
+type Noder interface {
+	// Hash returns the hash of the element.
+	Hash() []byte
+	// Key returns the key of the element.
+	Key() string
+	// Children returns the children of the element, sorted
+	// in reverse key alphabetical order.
+	Children() []Noder
+	// NumChildren returns the number of children this element has.
+	//
+	// This method is an optimization: the number of children is easily
+	// calculated as the length of the value returned by the Children
+	// method (above); yet, some implementations will be able to
+	// implement NumChildren in O(1) while Children is usually more
+	// complex.
+	NumChildren() int
+}