delete old noder, create a new one in utils (#241)

9 files changed, 0 insertions, 1004 deletions

diff --git a/plumbing/difftree/internal/merkletrie/doc.go b/plumbing/difftree/internal/merkletrie/doc.go
deleted file mode 100644
index f8c3b2f..0000000
--- a/plumbing/difftree/internal/merkletrie/doc.go
+++ /dev/null
@@ -1,30 +0,0 @@
-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/plumbing/difftree/internal/merkletrie/frame.go b/plumbing/difftree/internal/merkletrie/frame.go
deleted file mode 100644
index a40c6ad..0000000
--- a/plumbing/difftree/internal/merkletrie/frame.go
+++ /dev/null
@@ -1,79 +0,0 @@
-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/plumbing/difftree/internal/merkletrie/frame_test.go b/plumbing/difftree/internal/merkletrie/frame_test.go
deleted file mode 100644
index 0ef036a..0000000
--- a/plumbing/difftree/internal/merkletrie/frame_test.go
+++ /dev/null
@@ -1,69 +0,0 @@
-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/plumbing/difftree/internal/merkletrie/iter.go b/plumbing/difftree/internal/merkletrie/iter.go
deleted file mode 100644
index 417dbb3..0000000
--- a/plumbing/difftree/internal/merkletrie/iter.go
+++ /dev/null
@@ -1,167 +0,0 @@
-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
-// consequence 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/plumbing/difftree/internal/merkletrie/iter_fixtures_test.go b/plumbing/difftree/internal/merkletrie/iter_fixtures_test.go
deleted file mode 100644
index 20bddaf..0000000
--- a/plumbing/difftree/internal/merkletrie/iter_fixtures_test.go
+++ /dev/null
@@ -1,330 +0,0 @@
-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/plumbing/difftree/internal/merkletrie/iter_test.go b/plumbing/difftree/internal/merkletrie/iter_test.go
deleted file mode 100644
index 65116e1..0000000
--- a/plumbing/difftree/internal/merkletrie/iter_test.go
+++ /dev/null
@@ -1,176 +0,0 @@
-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/plumbing/difftree/internal/merkletrie/node.go b/plumbing/difftree/internal/merkletrie/node.go
deleted file mode 100644
index 99be5b8..0000000
--- a/plumbing/difftree/internal/merkletrie/node.go
+++ /dev/null
@@ -1,65 +0,0 @@
-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/plumbing/difftree/internal/merkletrie/node_test.go b/plumbing/difftree/internal/merkletrie/node_test.go
deleted file mode 100644
index 1622952..0000000
--- a/plumbing/difftree/internal/merkletrie/node_test.go
+++ /dev/null
@@ -1,68 +0,0 @@
-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/plumbing/difftree/internal/merkletrie/noder.go b/plumbing/difftree/internal/merkletrie/noder.go
deleted file mode 100644
index 3566657..0000000
--- a/plumbing/difftree/internal/merkletrie/noder.go
+++ /dev/null
@@ -1,20 +0,0 @@
-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
-}