move plumbing from top level package to plumbing (#183)

* plumbing: rename Object -> EncodedObject.

* plumbing/storer: rename ObjectStorer -> EncodedObjectStorer.

* move difftree to plumbing/difftree.

* move diff -> utils/diff

* make Object/Tag/Blob/Tree/Commit/File depend on storer.

* Object and its implementations now depend only on
  storer.EncodedObjectStorer, not git.Repository.
* Tests are decoupled accordingly.

* move Object/Commit/File/Tag/Tree to plumbing/object.

* move Object/Commit/File/Tag/Tree to plumbing/object.
* move checkClose to utils/ioutil.

* move RevListObjects to plumbing/revlist.Objects.

* move DiffTree to plumbing/difftree package.

* rename files with plural nouns to singular

* plumbing/object: add GetBlob/GetCommit/GetTag/GetTree.

11 files changed, 1687 insertions, 0 deletions

diff --git a/plumbing/difftree/difftree.go b/plumbing/difftree/difftree.go
new file mode 100644
index 0000000..3bc4d63
--- /dev/null
+++ b/plumbing/difftree/difftree.go
@@ -0,0 +1,253 @@
+package git
+
+import (
+	"bytes"
+	"fmt"
+	"io"
+	"sort"
+	"strings"
+
+	"gopkg.in/src-d/go-git.v4/plumbing"
+	"gopkg.in/src-d/go-git.v4/plumbing/object"
+)
+
+type Action int
+
+func (a Action) String() string {
+	switch a {
+	case Insert:
+		return "Insert"
+	case Delete:
+		return "Delete"
+	case Modify:
+		return "Modify"
+	default:
+		panic(fmt.Sprintf("unsupported action: %d", a))
+	}
+}
+
+const (
+	Insert Action = iota
+	Delete
+	Modify
+)
+
+type Change struct {
+	Action
+	From ChangeEntry
+	To   ChangeEntry
+}
+
+type ChangeEntry struct {
+	Name      string
+	Tree      *object.Tree
+	TreeEntry object.TreeEntry
+}
+
+func (c *Change) Files() (from, to *object.File, err error) {
+	if c.Action == Insert || c.Action == Modify {
+		to, err = c.To.Tree.TreeEntryFile(&c.To.TreeEntry)
+		if err != nil {
+			return
+		}
+
+	}
+
+	if c.Action == Delete || c.Action == Modify {
+		from, err = c.From.Tree.TreeEntryFile(&c.From.TreeEntry)
+		if err != nil {
+			return
+		}
+	}
+
+	return
+}
+
+func (c *Change) String() string {
+	return fmt.Sprintf("<Action: %s, Path: %s>", c.Action, c.name())
+}
+
+func (c *Change) name() string {
+	if c.From.Name != "" {
+		return c.From.Name
+	}
+
+	return c.To.Name
+}
+
+type Changes []*Change
+
+func newEmpty() Changes {
+	return make([]*Change, 0, 0)
+}
+
+func DiffTree(a, b *object.Tree) ([]*Change, error) {
+	if a == b {
+		return newEmpty(), nil
+	}
+
+	if a == nil || b == nil {
+		return newWithEmpty(a, b)
+	}
+
+	return newDiffTree(a, b)
+}
+
+func (c Changes) Len() int {
+	return len(c)
+}
+
+func (c Changes) Swap(i, j int) {
+	c[i], c[j] = c[j], c[i]
+}
+
+func (c Changes) Less(i, j int) bool {
+	return strings.Compare(c[i].name(), c[j].name()) < 0
+}
+
+func (c Changes) String() string {
+	var buffer bytes.Buffer
+	buffer.WriteString("[")
+	comma := ""
+	for _, v := range c {
+		buffer.WriteString(comma)
+		buffer.WriteString(v.String())
+		comma = ", "
+	}
+	buffer.WriteString("]")
+
+	return buffer.String()
+}
+
+func newWithEmpty(a, b *object.Tree) (Changes, error) {
+	changes := newEmpty()
+
+	var action Action
+	var tree *object.Tree
+	if a == nil {
+		action = Insert
+		tree = b
+	} else {
+		action = Delete
+		tree = a
+	}
+
+	w := object.NewTreeWalker(tree, true)
+	defer w.Close()
+
+	for {
+		path, entry, err := w.Next()
+		if err == io.EOF {
+			break
+		} else if err != nil {
+			return nil, fmt.Errorf("cannot get next file: %s", err)
+		}
+
+		if entry.Mode.IsDir() {
+			continue
+		}
+
+		c := &Change{Action: action}
+
+		if action == Insert {
+			c.To.Name = path
+			c.To.TreeEntry = entry
+			c.To.Tree = tree
+		} else {
+			c.From.Name = path
+			c.From.TreeEntry = entry
+			c.From.Tree = tree
+		}
+
+		changes = append(changes, c)
+	}
+
+	return changes, nil
+}
+
+// FIXME: this is very inefficient, but correct.
+// The proper way to do this is to implement a diff-tree algorithm,
+// while taking advantage of the tree hashes to avoid traversing
+// subtrees when the hash is equal in both inputs.
+func newDiffTree(a, b *object.Tree) ([]*Change, error) {
+	var result []*Change
+
+	aChanges, err := newWithEmpty(a, nil)
+	if err != nil {
+		return nil, fmt.Errorf("cannot create nil-diff of source tree: %s", err)
+	}
+	sort.Sort(aChanges)
+
+	bChanges, err := newWithEmpty(nil, b)
+	if err != nil {
+		return nil, fmt.Errorf("cannot create nil-diff of destination tree: %s", err)
+	}
+	sort.Sort(bChanges)
+
+	for len(aChanges) > 0 && len(bChanges) > 0 {
+		switch comp := strings.Compare(aChanges[0].name(), bChanges[0].name()); {
+		case comp == 0: // append as "Modify" or ignore if not changed
+			modified, err := hasChange(a, b, aChanges[0].name())
+			if err != nil {
+				return nil, err
+			}
+
+			if modified {
+				c := mergeInsertAndDeleteIntoModify(aChanges[0], bChanges[0])
+				result = append(result, c)
+			}
+
+			aChanges = aChanges[1:]
+			bChanges = bChanges[1:]
+		case comp < 0: // delete first a change
+			result = append(result, aChanges[0])
+			aChanges = aChanges[1:]
+		case comp > 0: // insert first b change
+			result = append(result, bChanges[0])
+			bChanges = bChanges[1:]
+		}
+	}
+
+	// append all remaining changes in aChanges, if any, as deletes
+	// append all remaining changes in bChanges, if any, as inserts
+	result = append(result, aChanges...)
+	result = append(result, bChanges...)
+
+	return result, nil
+}
+
+func mergeInsertAndDeleteIntoModify(a, b *Change) *Change {
+	c := &Change{Action: Modify}
+	c.From.Name = a.From.Name
+	c.From.Tree = a.From.Tree
+	c.From.TreeEntry = a.From.TreeEntry
+	c.To.Name = b.To.Name
+	c.To.Tree = b.To.Tree
+	c.To.TreeEntry = b.To.TreeEntry
+
+	return c
+}
+
+func hasChange(a, b *object.Tree, path string) (bool, error) {
+	ha, err := hash(a, path)
+	if err != nil {
+		return false, err
+	}
+
+	hb, err := hash(b, path)
+	if err != nil {
+		return false, err
+	}
+
+	return ha != hb, nil
+}
+
+func hash(tree *object.Tree, path string) (plumbing.Hash, error) {
+	file, err := tree.File(path)
+	if err != nil {
+		var empty plumbing.Hash
+		return empty, fmt.Errorf("cannot find file %s in tree: %s", path, err)
+	}
+
+	return file.Hash, nil
+}
diff --git a/plumbing/difftree/difftree_test.go b/plumbing/difftree/difftree_test.go
new file mode 100644
index 0000000..c95e879
--- /dev/null
+++ b/plumbing/difftree/difftree_test.go
@@ -0,0 +1,430 @@
+package git
+
+import (
+	"sort"
+	"testing"
+
+	"gopkg.in/src-d/go-git.v4/fixtures"
+	"gopkg.in/src-d/go-git.v4/plumbing"
+	"gopkg.in/src-d/go-git.v4/plumbing/format/packfile"
+	"gopkg.in/src-d/go-git.v4/plumbing/object"
+	"gopkg.in/src-d/go-git.v4/plumbing/storer"
+	"gopkg.in/src-d/go-git.v4/storage/filesystem"
+	"gopkg.in/src-d/go-git.v4/storage/memory"
+
+	. "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type DiffTreeSuite struct {
+	fixtures.Suite
+	Storer  storer.EncodedObjectStorer
+	Fixture *fixtures.Fixture
+	cache   map[string]storer.EncodedObjectStorer
+}
+
+func (s *DiffTreeSuite) SetUpSuite(c *C) {
+	s.Suite.SetUpSuite(c)
+	s.Fixture = fixtures.Basic().One()
+	sto, err := filesystem.NewStorage(s.Fixture.DotGit())
+	c.Assert(err, IsNil)
+	s.Storer = sto
+	s.cache = make(map[string]storer.EncodedObjectStorer)
+}
+
+func (s *DiffTreeSuite) tree(c *C, h plumbing.Hash) *object.Tree {
+	t, err := object.GetTree(s.Storer, h)
+	c.Assert(err, IsNil)
+	return t
+}
+
+func (s *DiffTreeSuite) commitFromStorer(c *C, sto storer.EncodedObjectStorer,
+	h plumbing.Hash) *object.Commit {
+
+	commit, err := object.GetCommit(sto, h)
+	c.Assert(err, IsNil)
+	return commit
+}
+
+func (s *DiffTreeSuite) storageFromPackfile(f *fixtures.Fixture) storer.EncodedObjectStorer {
+	sto, ok := s.cache[f.URL]
+	if ok {
+		return sto
+	}
+
+	sto = memory.NewStorage()
+
+	pf := f.Packfile()
+
+	defer pf.Close()
+
+	n := packfile.NewScanner(pf)
+	d, err := packfile.NewDecoder(n, sto)
+	if err != nil {
+		panic(err)
+	}
+
+	_, err = d.Decode()
+	if err != nil {
+		panic(err)
+	}
+
+	s.cache[f.URL] = sto
+	return sto
+}
+
+var _ = Suite(&DiffTreeSuite{})
+
+func (s *DiffTreeSuite) TestActionString(c *C) {
+	expected := "Insert"
+	action := Insert
+	obtained := action.String()
+	c.Assert(obtained, Equals, expected)
+
+	expected = "Delete"
+	action = Delete
+	obtained = action.String()
+	c.Assert(obtained, Equals, expected)
+
+	expected = "Modify"
+	action = Modify
+	obtained = action.String()
+	c.Assert(obtained, Equals, expected)
+
+	action = 37
+	c.Assert(func() { _ = action.String() },
+		PanicMatches, "unsupported action: 37")
+}
+
+func (s *DiffTreeSuite) TestChangeFilesInsert(c *C) {
+	tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+	change := &Change{Action: Insert}
+	change.To.Name = "json/long.json"
+	change.To.Tree = tree
+	change.To.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
+
+	from, to, err := change.Files()
+	c.Assert(err, IsNil)
+	c.Assert(from, IsNil)
+	c.Assert(to.ID(), Equals, change.To.TreeEntry.Hash)
+}
+
+func (s *DiffTreeSuite) TestChangeFilesDelete(c *C) {
+	tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+	change := &Change{Action: Delete}
+	change.From.Name = "json/long.json"
+	change.From.Tree = tree
+	change.From.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
+
+	from, to, err := change.Files()
+	c.Assert(err, IsNil)
+	c.Assert(to, IsNil)
+	c.Assert(from.ID(), Equals, change.From.TreeEntry.Hash)
+}
+
+func (s *DiffTreeSuite) TestChangeFilesModify(c *C) {
+	tree := s.tree(c, plumbing.NewHash("a8d315b2b1c615d43042c3a62402b8a54288cf5c"))
+
+	change := &Change{Action: Modify}
+	change.To.Name = "json/long.json"
+	change.To.Tree = tree
+	change.To.TreeEntry.Hash = plumbing.NewHash("49c6bb89b17060d7b4deacb7b338fcc6ea2352a9")
+	change.From.Name = "json/long.json"
+	change.From.Tree = tree
+	change.From.TreeEntry.Hash = plumbing.NewHash("9a48f23120e880dfbe41f7c9b7b708e9ee62a492")
+
+	from, to, err := change.Files()
+	c.Assert(err, IsNil)
+	c.Assert(to.ID(), Equals, change.To.TreeEntry.Hash)
+	c.Assert(from.ID(), Equals, change.From.TreeEntry.Hash)
+}
+
+func (s *DiffTreeSuite) TestChangeString(c *C) {
+	expected := "<Action: Insert, Path: foo>"
+	change := &Change{Action: Insert}
+	change.From.Name = "foo"
+
+	obtained := change.String()
+	c.Assert(obtained, Equals, expected)
+}
+
+func (s *DiffTreeSuite) TestChangesString(c *C) {
+	expected := "[]"
+	changes := newEmpty()
+	obtained := changes.String()
+	c.Assert(obtained, Equals, expected)
+
+	expected = "[<Action: Modify, Path: bla>]"
+	changes = make([]*Change, 1)
+	changes[0] = &Change{Action: Modify}
+	changes[0].From.Name = "bla"
+
+	obtained = changes.String()
+	c.Assert(obtained, Equals, expected)
+
+	expected = "[<Action: Modify, Path: bla>, <Action: Insert, Path: foo/bar>]"
+	changes = make([]*Change, 2)
+	changes[0] = &Change{Action: Modify}
+	changes[0].From.Name = "bla"
+	changes[1] = &Change{Action: Insert}
+	changes[1].From.Name = "foo/bar"
+	obtained = changes.String()
+	c.Assert(obtained, Equals, expected)
+}
+
+type expectChange struct {
+	Action Action
+	Name   string
+}
+
+func (s *DiffTreeSuite) TestDiffTree(c *C) {
+	for i, t := range []struct {
+		repository string         // the repo name as in localRepos
+		commit1    string         // the commit of the first tree
+		commit2    string         // the commit of the second tree
+		expected   []expectChange // the expected list of []changeExpect
+	}{{
+		"https://github.com/dezfowler/LiteMock.git",
+		"",
+		"",
+		[]expectChange{},
+	}, {
+		"https://github.com/dezfowler/LiteMock.git",
+		"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+		"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+		[]expectChange{},
+	}, {
+		"https://github.com/dezfowler/LiteMock.git",
+		"",
+		"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+		[]expectChange{
+			{Action: Insert, Name: "README"},
+		},
+	}, {
+		"https://github.com/dezfowler/LiteMock.git",
+		"b7965eaa2c4f245d07191fe0bcfe86da032d672a",
+		"",
+		[]expectChange{
+			{Action: Delete, Name: "README"},
+		},
+	}, {
+		"https://github.com/githubtraining/example-branches.git",
+		"",
+		"f0eb272cc8f77803478c6748103a1450aa1abd37",
+		[]expectChange{
+			{Action: Insert, Name: "README.md"},
+		},
+	}, {
+		"https://github.com/githubtraining/example-branches.git",
+		"f0eb272cc8f77803478c6748103a1450aa1abd37",
+		"",
+		[]expectChange{
+			{Action: Delete, Name: "README.md"},
+		},
+	}, {
+		"https://github.com/githubtraining/example-branches.git",
+		"f0eb272cc8f77803478c6748103a1450aa1abd37",
+		"f0eb272cc8f77803478c6748103a1450aa1abd37",
+		[]expectChange{},
+	}, {
+		"https://github.com/github/gem-builder.git",
+		"",
+		"9608eed92b3839b06ebf72d5043da547de10ce85",
+		[]expectChange{
+			{Action: Insert, Name: "README"},
+			{Action: Insert, Name: "gem_builder.rb"},
+			{Action: Insert, Name: "gem_eval.rb"},
+		},
+	}, {
+		"https://github.com/github/gem-builder.git",
+		"9608eed92b3839b06ebf72d5043da547de10ce85",
+		"",
+		[]expectChange{
+			{Action: Delete, Name: "README"},
+			{Action: Delete, Name: "gem_builder.rb"},
+			{Action: Delete, Name: "gem_eval.rb"},
+		},
+	}, {
+		"https://github.com/github/gem-builder.git",
+		"9608eed92b3839b06ebf72d5043da547de10ce85",
+		"9608eed92b3839b06ebf72d5043da547de10ce85",
+		[]expectChange{},
+	}, {
+		"https://github.com/toqueteos/ts3.git",
+		"",
+		"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+		[]expectChange{
+			{Action: Insert, Name: "README.markdown"},
+			{Action: Insert, Name: "examples/bot.go"},
+			{Action: Insert, Name: "examples/raw_shell.go"},
+			{Action: Insert, Name: "helpers.go"},
+			{Action: Insert, Name: "ts3.go"},
+		},
+	}, {
+		"https://github.com/toqueteos/ts3.git",
+		"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+		"",
+		[]expectChange{
+			{Action: Delete, Name: "README.markdown"},
+			{Action: Delete, Name: "examples/bot.go"},
+			{Action: Delete, Name: "examples/raw_shell.go"},
+			{Action: Delete, Name: "helpers.go"},
+			{Action: Delete, Name: "ts3.go"},
+		},
+	}, {
+		"https://github.com/toqueteos/ts3.git",
+		"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+		"764e914b75d6d6df1fc5d832aa9840f590abf1bb",
+		[]expectChange{},
+	}, {
+		"https://github.com/github/gem-builder.git",
+		"9608eed92b3839b06ebf72d5043da547de10ce85",
+		"6c41e05a17e19805879689414026eb4e279f7de0",
+		[]expectChange{
+			{Action: Modify, Name: "gem_eval.rb"},
+		},
+	}, {
+		"https://github.com/github/gem-builder.git",
+		"6c41e05a17e19805879689414026eb4e279f7de0",
+		"89be3aac2f178719c12953cc9eaa23441f8d9371",
+		[]expectChange{
+			{Action: Modify, Name: "gem_eval.rb"},
+			{Action: Insert, Name: "gem_eval_test.rb"},
+			{Action: Insert, Name: "security.rb"},
+			{Action: Insert, Name: "security_test.rb"},
+		},
+	}, {
+		"https://github.com/github/gem-builder.git",
+		"89be3aac2f178719c12953cc9eaa23441f8d9371",
+		"597240b7da22d03ad555328f15abc480b820acc0",
+		[]expectChange{
+			{Action: Modify, Name: "gem_eval.rb"},
+		},
+	}, {
+		"https://github.com/github/gem-builder.git",
+		"597240b7da22d03ad555328f15abc480b820acc0",
+		"0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
+		[]expectChange{
+			{Action: Modify, Name: "gem_eval.rb"},
+			{Action: Modify, Name: "gem_eval_test.rb"},
+			{Action: Insert, Name: "lazy_dir.rb"},
+			{Action: Insert, Name: "lazy_dir_test.rb"},
+			{Action: Modify, Name: "security.rb"},
+			{Action: Modify, Name: "security_test.rb"},
+		},
+	}, {
+		"https://github.com/github/gem-builder.git",
+		"0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
+		"597240b7da22d03ad555328f15abc480b820acc0",
+		[]expectChange{
+			{Action: Modify, Name: "gem_eval.rb"},
+			{Action: Modify, Name: "gem_eval_test.rb"},
+			{Action: Delete, Name: "lazy_dir.rb"},
+			{Action: Delete, Name: "lazy_dir_test.rb"},
+			{Action: Modify, Name: "security.rb"},
+			{Action: Modify, Name: "security_test.rb"},
+		},
+	}, {
+		"https://github.com/github/gem-builder.git",
+		"0260380e375d2dd0e1a8fcab15f91ce56dbe778e",
+		"ca9fd470bacb6262eb4ca23ee48bb2f43711c1ff",
+		[]expectChange{
+			{Action: Modify, Name: "gem_eval.rb"},
+			{Action: Modify, Name: "security.rb"},
+			{Action: Modify, Name: "security_test.rb"},
+		},
+	}, {
+		"https://github.com/github/gem-builder.git",
+		"fe3c86745f887c23a0d38c85cfd87ca957312f86",
+		"b7e3f636febf7a0cd3ab473b6d30081786d2c5b6",
+		[]expectChange{
+			{Action: Modify, Name: "gem_eval.rb"},
+			{Action: Modify, Name: "gem_eval_test.rb"},
+			{Action: Insert, Name: "git_mock"},
+			{Action: Modify, Name: "lazy_dir.rb"},
+			{Action: Modify, Name: "lazy_dir_test.rb"},
+			{Action: Modify, Name: "security.rb"},
+		},
+	}, {
+		"https://github.com/rumpkernel/rumprun-xen.git",
+		"1831e47b0c6db750714cd0e4be97b5af17fb1eb0",
+		"51d8515578ea0c88cc8fc1a057903675cf1fc16c",
+		[]expectChange{
+			{Action: Modify, Name: "Makefile"},
+			{Action: Modify, Name: "netbsd_init.c"},
+			{Action: Modify, Name: "rumphyper_stubs.c"},
+			{Action: Delete, Name: "sysproxy.c"},
+		},
+	}, {
+		"https://github.com/rumpkernel/rumprun-xen.git",
+		"1831e47b0c6db750714cd0e4be97b5af17fb1eb0",
+		"e13e678f7ee9badd01b120889e0ec5fdc8ae3802",
+		[]expectChange{
+			{Action: Modify, Name: "app-tools/rumprun"},
+		},
+	}} {
+		f := fixtures.ByURL(t.repository).One()
+		sto := s.storageFromPackfile(f)
+
+		var tree1, tree2 *object.Tree
+		var err error
+		if t.commit1 != "" {
+			tree1, err = s.commitFromStorer(c, sto,
+				plumbing.NewHash(t.commit1)).Tree()
+			c.Assert(err, IsNil,
+				Commentf("subtest %d: unable to retrieve tree from commit %s and repo %s: %s", i, t.commit1, t.repository, err))
+		}
+
+		if t.commit2 != "" {
+			tree2, err = s.commitFromStorer(c, sto,
+				plumbing.NewHash(t.commit2)).Tree()
+			c.Assert(err, IsNil,
+				Commentf("subtest %d: unable to retrieve tree from commit %s and repo %s", i, t.commit2, t.repository, err))
+		}
+
+		obtained, err := DiffTree(tree1, tree2)
+		c.Assert(err, IsNil,
+			Commentf("subtest %d: unable to calculate difftree: %s", i, err))
+		c.Assert(equalChanges(obtained, t.expected), Equals, true,
+			Commentf("subtest:%d\nrepo=%s\ncommit1=%s\ncommit2=%s\nexpected=%s\nobtained=%s",
+				i, t.repository, t.commit1, t.commit2, t.expected, obtained))
+
+		assertChanges(obtained, c)
+	}
+}
+
+func assertChanges(a Changes, c *C) {
+	for _, changes := range a {
+		switch changes.Action {
+		case Insert:
+			c.Assert(changes.From.Tree, IsNil)
+			c.Assert(changes.To.Tree, NotNil)
+		case Delete:
+			c.Assert(changes.From.Tree, NotNil)
+			c.Assert(changes.To.Tree, IsNil)
+		case Modify:
+			c.Assert(changes.From.Tree, NotNil)
+			c.Assert(changes.To.Tree, NotNil)
+		}
+	}
+}
+
+func equalChanges(a Changes, b []expectChange) bool {
+	if len(a) != len(b) {
+		return false
+	}
+
+	sort.Sort(a)
+
+	for i, va := range a {
+		vb := b[i]
+		if va.Action != vb.Action || va.name() != vb.Name {
+			return false
+		}
+	}
+
+	return true
+}
diff --git a/plumbing/difftree/internal/merkletrie/doc.go b/plumbing/difftree/internal/merkletrie/doc.go
new file mode 100644
index 0000000..f8c3b2f
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/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/plumbing/difftree/internal/merkletrie/frame.go b/plumbing/difftree/internal/merkletrie/frame.go
new file mode 100644
index 0000000..a40c6ad
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/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/plumbing/difftree/internal/merkletrie/frame_test.go b/plumbing/difftree/internal/merkletrie/frame_test.go
new file mode 100644
index 0000000..0ef036a
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/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/plumbing/difftree/internal/merkletrie/iter.go b/plumbing/difftree/internal/merkletrie/iter.go
new file mode 100644
index 0000000..e175966
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/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/plumbing/difftree/internal/merkletrie/iter_fixtures_test.go b/plumbing/difftree/internal/merkletrie/iter_fixtures_test.go
new file mode 100644
index 0000000..20bddaf
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/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/plumbing/difftree/internal/merkletrie/iter_test.go b/plumbing/difftree/internal/merkletrie/iter_test.go
new file mode 100644
index 0000000..65116e1
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/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/plumbing/difftree/internal/merkletrie/node.go b/plumbing/difftree/internal/merkletrie/node.go
new file mode 100644
index 0000000..99be5b8
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/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/plumbing/difftree/internal/merkletrie/node_test.go b/plumbing/difftree/internal/merkletrie/node_test.go
new file mode 100644
index 0000000..1622952
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/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/plumbing/difftree/internal/merkletrie/noder.go b/plumbing/difftree/internal/merkletrie/noder.go
new file mode 100644
index 0000000..3566657
--- /dev/null
+++ b/plumbing/difftree/internal/merkletrie/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
+}