Implement git refs API for listing references (branches, tags and other) (#5354)

* Inital routes to git refs api

* Git refs API implementation

* Update swagger

* Fix copyright

* Make swagger happy add basic test

* Fix test

* Fix test again :)

10 files changed, 1540 insertions, 0 deletions

diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/change.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/change.go
new file mode 100644
index 0000000000..0b50ca71d3
--- /dev/null
+++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/change.go
@@ -0,0 +1,149 @@
+package merkletrie
+
+import (
+	"fmt"
+	"io"
+
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+// Action values represent the kind of things a Change can represent:
+// insertion, deletions or modifications of files.
+type Action int
+
+// The set of possible actions in a change.
+const (
+	_ Action = iota
+	Insert
+	Delete
+	Modify
+)
+
+// String returns the action as a human readable text.
+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))
+	}
+}
+
+// A Change value represent how a noder has change between to merkletries.
+type Change struct {
+	// The noder before the change or nil if it was inserted.
+	From noder.Path
+	// The noder after the change or nil if it was deleted.
+	To noder.Path
+}
+
+// Action is convenience method that returns what Action c represents.
+func (c *Change) Action() (Action, error) {
+	if c.From == nil && c.To == nil {
+		return Action(0), fmt.Errorf("malformed change: nil from and to")
+	}
+	if c.From == nil {
+		return Insert, nil
+	}
+	if c.To == nil {
+		return Delete, nil
+	}
+
+	return Modify, nil
+}
+
+// NewInsert returns a new Change representing the insertion of n.
+func NewInsert(n noder.Path) Change { return Change{To: n} }
+
+// NewDelete returns a new Change representing the deletion of n.
+func NewDelete(n noder.Path) Change { return Change{From: n} }
+
+// NewModify returns a new Change representing that a has been modified and
+// it is now b.
+func NewModify(a, b noder.Path) Change {
+	return Change{
+		From: a,
+		To:   b,
+	}
+}
+
+// String returns a single change in human readable form, using the
+// format: '<' + action + space + path + '>'.  The contents of the file
+// before or after the change are not included in this format.
+//
+// Example: inserting a file at the path a/b/c.txt will return "<Insert
+// a/b/c.txt>".
+func (c Change) String() string {
+	action, err := c.Action()
+	if err != nil {
+		panic(err)
+	}
+
+	var path string
+	if action == Delete {
+		path = c.From.String()
+	} else {
+		path = c.To.String()
+	}
+
+	return fmt.Sprintf("<%s %s>", action, path)
+}
+
+// Changes is a list of changes between to merkletries.
+type Changes []Change
+
+// NewChanges returns an empty list of changes.
+func NewChanges() Changes {
+	return Changes{}
+}
+
+// Add adds the change c to the list of changes.
+func (l *Changes) Add(c Change) {
+	*l = append(*l, c)
+}
+
+// AddRecursiveInsert adds the required changes to insert all the
+// file-like noders found in root, recursively.
+func (l *Changes) AddRecursiveInsert(root noder.Path) error {
+	return l.addRecursive(root, NewInsert)
+}
+
+// AddRecursiveDelete adds the required changes to delete all the
+// file-like noders found in root, recursively.
+func (l *Changes) AddRecursiveDelete(root noder.Path) error {
+	return l.addRecursive(root, NewDelete)
+}
+
+type noderToChangeFn func(noder.Path) Change // NewInsert or NewDelete
+
+func (l *Changes) addRecursive(root noder.Path, ctor noderToChangeFn) error {
+	if !root.IsDir() {
+		l.Add(ctor(root))
+		return nil
+	}
+
+	i, err := NewIterFromPath(root)
+	if err != nil {
+		return err
+	}
+
+	var current noder.Path
+	for {
+		if current, err = i.Step(); err != nil {
+			if err == io.EOF {
+				break
+			}
+			return err
+		}
+		if current.IsDir() {
+			continue
+		}
+		l.Add(ctor(current))
+	}
+
+	return nil
+}
diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/difftree.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/difftree.go
new file mode 100644
index 0000000000..d57ed13332
--- /dev/null
+++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/difftree.go
@@ -0,0 +1,424 @@
+package merkletrie
+
+// The focus of this difftree implementation is to save time by
+// skipping whole directories if their hash is the same in both
+// trees.
+//
+// The diff algorithm implemented here is based on the doubleiter
+// type defined in this same package; we will iterate over both
+// trees at the same time, while comparing the current noders in
+// each iterator.  Depending on how they differ we will output the
+// corresponding chages and move the iterators further over both
+// trees.
+//
+// The table bellow show all the possible comparison results, along
+// with what changes should we produce and how to advance the
+// iterators.
+//
+// The table is implemented by the switches in this function,
+// diffTwoNodes, diffTwoNodesSameName and diffTwoDirs.
+//
+// Many Bothans died to bring us this information, make sure you
+// understand the table before modifying this code.
+
+// # Cases
+//
+// When comparing noders in both trees you will found yourself in
+// one of 169 possible cases, but if we ignore moves, we can
+// simplify a lot the search space into the following table:
+//
+// - "-": nothing, no file or directory
+// - a<>: an empty file named "a".
+// - a<1>: a file named "a", with "1" as its contents.
+// - a<2>: a file named "a", with "2" as its contents.
+// - a(): an empty dir named "a".
+// - a(...): a dir named "a", with some files and/or dirs inside (possibly
+//   empty).
+// - a(;;;): a dir named "a", with some other files and/or dirs inside
+//   (possibly empty), which different from the ones in "a(...)".
+//
+//     \ to     -   a<>  a<1>  a<2>  a()  a(...)  a(;;;)
+// from \
+// -           00    01    02    03   04     05      06
+// a<>         10    11    12    13   14     15      16
+// a<1>        20    21    22    23   24     25      26
+// a<2>        30    31    32    33   34     35      36
+// a()         40    41    42    43   44     45      46
+// a(...)      50    51    52    53   54     55      56
+// a(;;;)      60    61    62    63   64     65      66
+//
+// Every (from, to) combination in the table is a special case, but
+// some of them can be merged into some more general cases, for
+// instance 11 and 22 can be merged into the general case: both
+// noders are equal.
+//
+// Here is a full list of all the cases that are similar and how to
+// merge them together into more general cases.  Each general case
+// is labeled with an uppercase letter for further reference, and it
+// is followed by the pseudocode of the checks you have to perfrom
+// on both noders to see if you are in such a case, the actions to
+// perform (i.e. what changes to output) and how to advance the
+// iterators of each tree to continue the comparison process.
+//
+// ## A. Impossible: 00
+//
+// ## B. Same thing on both sides: 11, 22, 33, 44, 55, 66
+//   - check: `SameName() && SameHash()`
+//   - action: do nothing.
+//   - advance: `FromNext(); ToNext()`
+//
+// ### C. To was created: 01, 02, 03, 04, 05, 06
+//   - check: `DifferentName() && ToBeforeFrom()`
+//   - action: inserRecursively(to)
+//   - advance: `ToNext()`
+//
+// ### D. From was deleted: 10, 20, 30, 40, 50, 60
+//   - check: `DifferentName() && FromBeforeTo()`
+//   - action: `DeleteRecursively(from)`
+//   - advance: `FromNext()`
+//
+// ### E. Empty file to file with contents: 12, 13
+//   - check: `SameName() && DifferentHash() && FromIsFile() &&
+//             ToIsFile() && FromIsEmpty()`
+//   - action: `modifyFile(from, to)`
+//   - advance: `FromNext()` or `FromStep()`
+//
+// ### E'. file with contents to empty file: 21, 31
+//   - check: `SameName() && DifferentHash() && FromIsFile() &&
+//             ToIsFile() && ToIsEmpty()`
+//   - action: `modifyFile(from, to)`
+//   - advance: `FromNext()` or `FromStep()`
+//
+// ### F. empty file to empty dir with the same name: 14
+//   - check: `SameName() && FromIsFile() && FromIsEmpty() &&
+//             ToIsDir() && ToIsEmpty()`
+//   - action: `DeleteFile(from); InsertEmptyDir(to)`
+//   - advance: `FromNext(); ToNext()`
+//
+// ### F'. empty dir to empty file of the same name: 41
+//   - check: `SameName() && FromIsDir() && FromIsEmpty &&
+//             ToIsFile() && ToIsEmpty()`
+//   - action: `DeleteEmptyDir(from); InsertFile(to)`
+//   - advance: `FromNext(); ToNext()` or step for any of them.
+//
+// ### G. empty file to non-empty dir of the same name: 15, 16
+//   - check: `SameName() && FromIsFile() && ToIsDir() &&
+//             FromIsEmpty() && ToIsNotEmpty()`
+//   - action: `DeleteFile(from); InsertDirRecursively(to)`
+//   - advance: `FromNext(); ToNext()`
+//
+// ### G'. non-empty dir to empty file of the same name: 51, 61
+//   - check: `SameName() && FromIsDir() && FromIsNotEmpty() &&
+//             ToIsFile() && FromIsEmpty()`
+//   - action: `DeleteDirRecursively(from); InsertFile(to)`
+//   - advance: `FromNext(); ToNext()`
+//
+// ### H. modify file contents: 23, 32
+//   - check: `SameName() && FromIsFile() && ToIsFile() &&
+//             FromIsNotEmpty() && ToIsNotEmpty()`
+//   - action: `ModifyFile(from, to)`
+//   - advance: `FromNext(); ToNext()`
+//
+// ### I. file with contents to empty dir: 24, 34
+//   - check: `SameName() && DifferentHash() && FromIsFile() &&
+//             FromIsNotEmpty() && ToIsDir() && ToIsEmpty()`
+//   - action: `DeleteFile(from); InsertEmptyDir(to)`
+//   - advance: `FromNext(); ToNext()`
+//
+// ### I'. empty dir to file with contents: 42, 43
+//   - check: `SameName() && DifferentHash() && FromIsDir() &&
+//             FromIsEmpty() && ToIsFile() && ToIsEmpty()`
+//   - action: `DeleteDir(from); InsertFile(to)`
+//   - advance: `FromNext(); ToNext()`
+//
+// ### J. file with contents to dir with contetns: 25, 26, 35, 36
+//   - check: `SameName() && DifferentHash() && FromIsFile() &&
+//             FromIsNotEmpty() && ToIsDir() && ToIsNotEmpty()`
+//   - action: `DeleteFile(from); InsertDirRecursively(to)`
+//   - advance: `FromNext(); ToNext()`
+//
+// ### J'. dir with contetns to file with contents: 52, 62, 53, 63
+//   - check: `SameName() && DifferentHash() && FromIsDir() &&
+//             FromIsNotEmpty() && ToIsFile() && ToIsNotEmpty()`
+//   - action: `DeleteDirRecursively(from); InsertFile(to)`
+//   - advance: `FromNext(); ToNext()`
+//
+// ### K. empty dir to dir with contents: 45, 46
+//   - check: `SameName() && DifferentHash() && FromIsDir() &&
+//             FromIsEmpty() && ToIsDir() && ToIsNotEmpty()`
+//   - action: `InsertChildrenRecursively(to)`
+//   - advance: `FromNext(); ToNext()`
+//
+// ### K'. dir with contents to empty dir: 54, 64
+//   - check: `SameName() && DifferentHash() && FromIsDir() &&
+//             FromIsEmpty() && ToIsDir() && ToIsNotEmpty()`
+//   - action: `DeleteChildrenRecursively(from)`
+//   - advance: `FromNext(); ToNext()`
+//
+// ### L. dir with contents to dir with different contents: 56, 65
+//   - check: `SameName() && DifferentHash() && FromIsDir() &&
+//             FromIsNotEmpty() && ToIsDir() && ToIsNotEmpty()`
+//   - action: nothing
+//   - advance: `FromStep(); ToStep()`
+//
+//
+
+// All these cases can be further simplified by a truth table
+// reduction process, in which we gather similar checks together to
+// make the final code easier to read and understand.
+//
+// The first 6 columns are the outputs of the checks to perform on
+// both noders.  I have labeled them 1 to 6, this is what they mean:
+//
+// 1: SameName()
+// 2: SameHash()
+// 3: FromIsDir()
+// 4: ToIsDir()
+// 5: FromIsEmpty()
+// 6: ToIsEmpty()
+//
+// The from and to columns are a fsnoder example of the elements
+// that you will find on each tree under the specified comparison
+// results (columns 1 to 6).
+//
+// The type column identifies the case we are into, from the list above.
+//
+// The type' column identifies the new set of reduced cases, using
+// lowercase letters, and they are explained after the table.
+//
+// The last column is the set of actions and advances for each case.
+//
+// "---" means impossible except in case of hash collision.
+//
+// advance meaning:
+// - NN: from.Next(); to.Next()
+// - SS: from.Step(); to.Step()
+//
+// 1 2 3 4 5 6 | from   |  to    |type|type'|action ; advance
+// ------------+--------+--------+----+------------------------------------
+// 0 0 0 0 0 0 |        |        |    |     | if !SameName() {
+//     .       |        |        |    |     |    if FromBeforeTo() {
+//     .       |        |        | D  |  d  |       delete(from); from.Next()
+//     .       |        |        |    |     |    } else {
+//     .       |        |        | C  |  c  |       insert(to); to.Next()
+//     .       |        |        |    |     |    }
+// 0 1 1 1 1 1 |        |        |    |     | }
+// 1 0 0 0 0 0 |  a<1>  |  a<2>  | H  |  e  | modify(from, to); NN
+// 1 0 0 0 0 1 |  a<1>  |   a<>  | E' |  e  | modify(from, to); NN
+// 1 0 0 0 1 0 |   a<>  |  a<1>  | E  |  e  | modify(from, to); NN
+// 1 0 0 0 1 1 |  ----  |  ----  |    |  e  |
+// 1 0 0 1 0 0 |  a<1>  | a(...) | J  |  f  | delete(from); insert(to); NN
+// 1 0 0 1 0 1 |  a<1>  |    a() | I  |  f  | delete(from); insert(to); NN
+// 1 0 0 1 1 0 |   a<>  | a(...) | G  |  f  | delete(from); insert(to); NN
+// 1 0 0 1 1 1 |   a<>  |    a() | F  |  f  | delete(from); insert(to); NN
+// 1 0 1 0 0 0 | a(...) |  a<1>  | J' |  f  | delete(from); insert(to); NN
+// 1 0 1 0 0 1 | a(...) |   a<>  | G' |  f  | delete(from); insert(to); NN
+// 1 0 1 0 1 0 |    a() |  a<1>  | I' |  f  | delete(from); insert(to); NN
+// 1 0 1 0 1 1 |    a() |   a<>  | F' |  f  | delete(from); insert(to); NN
+// 1 0 1 1 0 0 | a(...) | a(;;;) | L  |  g  | nothing; SS
+// 1 0 1 1 0 1 | a(...) |    a() | K' |  h  | deleteChidren(from); NN
+// 1 0 1 1 1 0 |    a() | a(...) | K  |  i  | insertChildren(to); NN
+// 1 0 1 1 1 1 |  ----  |  ----  |    |     |
+// 1 1 0 0 0 0 |  a<1>  |  a<1>  | B  |  b  | nothing; NN
+// 1 1 0 0 0 1 |  ----  |  ----  |    |  b  |
+// 1 1 0 0 1 0 |  ----  |  ----  |    |  b  |
+// 1 1 0 0 1 1 |   a<>  |   a<>  | B  |  b  | nothing; NN
+// 1 1 0 1 0 0 |  ----  |  ----  |    |  b  |
+// 1 1 0 1 0 1 |  ----  |  ----  |    |  b  |
+// 1 1 0 1 1 0 |  ----  |  ----  |    |  b  |
+// 1 1 0 1 1 1 |  ----  |  ----  |    |  b  |
+// 1 1 1 0 0 0 |  ----  |  ----  |    |  b  |
+// 1 1 1 0 0 1 |  ----  |  ----  |    |  b  |
+// 1 1 1 0 1 0 |  ----  |  ----  |    |  b  |
+// 1 1 1 0 1 1 |  ----  |  ----  |    |  b  |
+// 1 1 1 1 0 0 | a(...) | a(...) | B  |  b  | nothing; NN
+// 1 1 1 1 0 1 |  ----  |  ----  |    |  b  |
+// 1 1 1 1 1 0 |  ----  |  ----  |    |  b  |
+// 1 1 1 1 1 1 |   a()  |   a()  | B  |  b  | nothing; NN
+//
+// c and d:
+//     if !SameName()
+//         d if FromBeforeTo()
+//         c else
+// b: SameName) && sameHash()
+// e: SameName() && !sameHash() && BothAreFiles()
+// f: SameName() && !sameHash() && FileAndDir()
+// g: SameName() && !sameHash() && BothAreDirs() && NoneIsEmpty
+// i: SameName() && !sameHash() && BothAreDirs() && FromIsEmpty
+// h: else of i
+
+import (
+	"context"
+	"errors"
+	"fmt"
+
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+var (
+	ErrCanceled = errors.New("operation canceled")
+)
+
+// DiffTree calculates the list of changes between two merkletries.  It
+// uses the provided hashEqual callback to compare noders.
+func DiffTree(fromTree, toTree noder.Noder,
+	hashEqual noder.Equal) (Changes, error) {
+	return DiffTreeContext(context.Background(), fromTree, toTree, hashEqual)
+}
+
+// DiffTree calculates the list of changes between two merkletries.  It
+// uses the provided hashEqual callback to compare noders.
+// Error will be returned if context expires
+// Provided context must be non nil
+func DiffTreeContext(ctx context.Context, fromTree, toTree noder.Noder,
+	hashEqual noder.Equal) (Changes, error) {
+	ret := NewChanges()
+
+	ii, err := newDoubleIter(fromTree, toTree, hashEqual)
+	if err != nil {
+		return nil, err
+	}
+
+	for {
+		select {
+		case <-ctx.Done():
+			return nil, ErrCanceled
+		default:
+		}
+
+		from := ii.from.current
+		to := ii.to.current
+
+		switch r := ii.remaining(); r {
+		case noMoreNoders:
+			return ret, nil
+		case onlyFromRemains:
+			if err = ret.AddRecursiveDelete(from); err != nil {
+				return nil, err
+			}
+			if err = ii.nextFrom(); err != nil {
+				return nil, err
+			}
+		case onlyToRemains:
+			if err = ret.AddRecursiveInsert(to); err != nil {
+				return nil, err
+			}
+			if err = ii.nextTo(); err != nil {
+				return nil, err
+			}
+		case bothHaveNodes:
+			if err = diffNodes(&ret, ii); err != nil {
+				return nil, err
+			}
+		default:
+			panic(fmt.Sprintf("unknown remaining value: %d", r))
+		}
+	}
+}
+
+func diffNodes(changes *Changes, ii *doubleIter) error {
+	from := ii.from.current
+	to := ii.to.current
+	var err error
+
+	// compare their full paths as strings
+	switch from.Compare(to) {
+	case -1:
+		if err = changes.AddRecursiveDelete(from); err != nil {
+			return err
+		}
+		if err = ii.nextFrom(); err != nil {
+			return err
+		}
+	case 1:
+		if err = changes.AddRecursiveInsert(to); err != nil {
+			return err
+		}
+		if err = ii.nextTo(); err != nil {
+			return err
+		}
+	default:
+		if err := diffNodesSameName(changes, ii); err != nil {
+			return err
+		}
+	}
+
+	return nil
+}
+
+func diffNodesSameName(changes *Changes, ii *doubleIter) error {
+	from := ii.from.current
+	to := ii.to.current
+
+	status, err := ii.compare()
+	if err != nil {
+		return err
+	}
+
+	switch {
+	case status.sameHash:
+		// do nothing
+		if err = ii.nextBoth(); err != nil {
+			return err
+		}
+	case status.bothAreFiles:
+		changes.Add(NewModify(from, to))
+		if err = ii.nextBoth(); err != nil {
+			return err
+		}
+	case status.fileAndDir:
+		if err = changes.AddRecursiveDelete(from); err != nil {
+			return err
+		}
+		if err = changes.AddRecursiveInsert(to); err != nil {
+			return err
+		}
+		if err = ii.nextBoth(); err != nil {
+			return err
+		}
+	case status.bothAreDirs:
+		if err = diffDirs(changes, ii); err != nil {
+			return err
+		}
+	default:
+		return fmt.Errorf("bad status from double iterator")
+	}
+
+	return nil
+}
+
+func diffDirs(changes *Changes, ii *doubleIter) error {
+	from := ii.from.current
+	to := ii.to.current
+
+	status, err := ii.compare()
+	if err != nil {
+		return err
+	}
+
+	switch {
+	case status.fromIsEmptyDir:
+		if err = changes.AddRecursiveInsert(to); err != nil {
+			return err
+		}
+		if err = ii.nextBoth(); err != nil {
+			return err
+		}
+	case status.toIsEmptyDir:
+		if err = changes.AddRecursiveDelete(from); err != nil {
+			return err
+		}
+		if err = ii.nextBoth(); err != nil {
+			return err
+		}
+	case !status.fromIsEmptyDir && !status.toIsEmptyDir:
+		// do nothing
+		if err = ii.stepBoth(); err != nil {
+			return err
+		}
+	default:
+		return fmt.Errorf("both dirs are empty but has different hash")
+	}
+
+	return nil
+}
diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doc.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doc.go
new file mode 100644
index 0000000000..5204024ad4
--- /dev/null
+++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doc.go
@@ -0,0 +1,34 @@
+/*
+Package merkletrie provides support for n-ary trees that are at the same
+time Merkle trees and Radix trees (tries).
+
+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.
+
+This package defines Merkle tries as nodes that should have:
+
+- a hash: the Merkle part of the Merkle trie
+
+- a key: the Radix part of the Merkle trie
+
+The Merkle hash condition is not enforced by this package though.  This
+means that the hash of a node doesn't have to take into account the hashes of
+their children,  which is good for testing purposes.
+
+Nodes in the Merkle trie are abstracted by the Noder interface.  The
+intended use is that git trees implements this interface, either
+directly or using a simple wrapper.
+
+This package provides an iterator for merkletries that can skip whole
+directory-like noders and an efficient merkletrie comparison algorithm.
+
+When comparing git trees, the simple approach of alphabetically sorting
+their elements and comparing the resulting lists is too slow 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, just by looking at their hashes.  This package provides
+the tools to do exactly that.
+*/
+package merkletrie
diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doubleiter.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doubleiter.go
new file mode 100644
index 0000000000..e56dee701f
--- /dev/null
+++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/doubleiter.go
@@ -0,0 +1,187 @@
+package merkletrie
+
+import (
+	"fmt"
+	"io"
+
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+// A doubleIter is a convenience type to keep track of the current
+// noders in two merkletries that are going to be iterated in parallel.
+// It has methods for:
+//
+// - iterating over the merkletries, both at the same time or
+// individually: nextFrom, nextTo, nextBoth, stepBoth
+//
+// - checking if there are noders left in one or both of them with the
+// remaining method and its associated returned type.
+//
+// - comparing the current noders of both merkletries in several ways,
+// with the compare method and its associated returned type.
+type doubleIter struct {
+	from struct {
+		iter    *Iter
+		current noder.Path // nil if no more nodes
+	}
+	to struct {
+		iter    *Iter
+		current noder.Path // nil if no more nodes
+	}
+	hashEqual noder.Equal
+}
+
+// NewdoubleIter returns a new doubleIter for the merkletries "from" and
+// "to".  The hashEqual callback function will be used by the doubleIter
+// to compare the hash of the noders in the merkletries.  The doubleIter
+// will be initialized to the first elements in each merkletrie if any.
+func newDoubleIter(from, to noder.Noder, hashEqual noder.Equal) (
+	*doubleIter, error) {
+	var ii doubleIter
+	var err error
+
+	if ii.from.iter, err = NewIter(from); err != nil {
+		return nil, fmt.Errorf("from: %s", err)
+	}
+	if ii.from.current, err = ii.from.iter.Next(); turnEOFIntoNil(err) != nil {
+		return nil, fmt.Errorf("from: %s", err)
+	}
+
+	if ii.to.iter, err = NewIter(to); err != nil {
+		return nil, fmt.Errorf("to: %s", err)
+	}
+	if ii.to.current, err = ii.to.iter.Next(); turnEOFIntoNil(err) != nil {
+		return nil, fmt.Errorf("to: %s", err)
+	}
+
+	ii.hashEqual = hashEqual
+
+	return &ii, nil
+}
+
+func turnEOFIntoNil(e error) error {
+	if e != nil && e != io.EOF {
+		return e
+	}
+	return nil
+}
+
+// NextBoth makes d advance to the next noder in both merkletries.  If
+// any of them is a directory, it skips its contents.
+func (d *doubleIter) nextBoth() error {
+	if err := d.nextFrom(); err != nil {
+		return err
+	}
+	if err := d.nextTo(); err != nil {
+		return err
+	}
+
+	return nil
+}
+
+// NextFrom makes d advance to the next noder in the "from" merkletrie,
+// skipping its contents if it is a directory.
+func (d *doubleIter) nextFrom() (err error) {
+	d.from.current, err = d.from.iter.Next()
+	return turnEOFIntoNil(err)
+}
+
+// NextTo makes d advance to the next noder in the "to" merkletrie,
+// skipping its contents if it is a directory.
+func (d *doubleIter) nextTo() (err error) {
+	d.to.current, err = d.to.iter.Next()
+	return turnEOFIntoNil(err)
+}
+
+// StepBoth makes d advance to the next noder in both merkletries,
+// getting deeper into directories if that is the case.
+func (d *doubleIter) stepBoth() (err error) {
+	if d.from.current, err = d.from.iter.Step(); turnEOFIntoNil(err) != nil {
+		return err
+	}
+	if d.to.current, err = d.to.iter.Step(); turnEOFIntoNil(err) != nil {
+		return err
+	}
+	return nil
+}
+
+// Remaining returns if there are no more noders in the tree, if both
+// have noders or if one of them doesn't.
+func (d *doubleIter) remaining() remaining {
+	if d.from.current == nil && d.to.current == nil {
+		return noMoreNoders
+	}
+
+	if d.from.current == nil && d.to.current != nil {
+		return onlyToRemains
+	}
+
+	if d.from.current != nil && d.to.current == nil {
+		return onlyFromRemains
+	}
+
+	return bothHaveNodes
+}
+
+// Remaining values tells you whether both trees still have noders, or
+// only one of them or none of them.
+type remaining int
+
+const (
+	noMoreNoders remaining = iota
+	onlyToRemains
+	onlyFromRemains
+	bothHaveNodes
+)
+
+// Compare returns the comparison between the current elements in the
+// merkletries.
+func (d *doubleIter) compare() (s comparison, err error) {
+	s.sameHash = d.hashEqual(d.from.current, d.to.current)
+
+	fromIsDir := d.from.current.IsDir()
+	toIsDir := d.to.current.IsDir()
+
+	s.bothAreDirs = fromIsDir && toIsDir
+	s.bothAreFiles = !fromIsDir && !toIsDir
+	s.fileAndDir = !s.bothAreDirs && !s.bothAreFiles
+
+	fromNumChildren, err := d.from.current.NumChildren()
+	if err != nil {
+		return comparison{}, fmt.Errorf("from: %s", err)
+	}
+
+	toNumChildren, err := d.to.current.NumChildren()
+	if err != nil {
+		return comparison{}, fmt.Errorf("to: %s", err)
+	}
+
+	s.fromIsEmptyDir = fromIsDir && fromNumChildren == 0
+	s.toIsEmptyDir = toIsDir && toNumChildren == 0
+
+	return
+}
+
+// Answers to a lot of questions you can ask about how to noders are
+// equal or different.
+type comparison struct {
+	// the following are only valid if both nodes have the same name
+	// (i.e. nameComparison == 0)
+
+	// Do both nodes have the same hash?
+	sameHash bool
+	// Are both nodes files?
+	bothAreFiles bool
+
+	// the following are only valid if any of the noders are dirs,
+	// this is, if !bothAreFiles
+
+	// Is one a file and the other a dir?
+	fileAndDir bool
+	// Are both nodes dirs?
+	bothAreDirs bool
+	// Is the from node an empty dir?
+	fromIsEmptyDir bool
+	// Is the to Node an empty dir?
+	toIsEmptyDir bool
+}
diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/filesystem/node.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/filesystem/node.go
new file mode 100644
index 0000000000..12d00189a3
--- /dev/null
+++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/filesystem/node.go
@@ -0,0 +1,196 @@
+package filesystem
+
+import (
+	"io"
+	"os"
+	"path"
+
+	"gopkg.in/src-d/go-git.v4/plumbing"
+	"gopkg.in/src-d/go-git.v4/plumbing/filemode"
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+
+	"gopkg.in/src-d/go-billy.v4"
+)
+
+var ignore = map[string]bool{
+	".git": true,
+}
+
+// The node represents a file or a directory in a billy.Filesystem. It
+// implements the interface noder.Noder of merkletrie package.
+//
+// This implementation implements a "standard" hash method being able to be
+// compared with any other noder.Noder implementation inside of go-git.
+type node struct {
+	fs         billy.Filesystem
+	submodules map[string]plumbing.Hash
+
+	path     string
+	hash     []byte
+	children []noder.Noder
+	isDir    bool
+}
+
+// NewRootNode returns the root node based on a given billy.Filesystem.
+//
+// In order to provide the submodule hash status, a map[string]plumbing.Hash
+// should be provided where the key is the path of the submodule and the commit
+// of the submodule HEAD
+func NewRootNode(
+	fs billy.Filesystem,
+	submodules map[string]plumbing.Hash,
+) noder.Noder {
+	return &node{fs: fs, submodules: submodules, isDir: true}
+}
+
+// Hash the hash of a filesystem is the result of concatenating the computed
+// plumbing.Hash of the file as a Blob and its plumbing.FileMode; that way the
+// difftree algorithm will detect changes in the contents of files and also in
+// their mode.
+//
+// The hash of a directory is always a 24-bytes slice of zero values
+func (n *node) Hash() []byte {
+	return n.hash
+}
+
+func (n *node) Name() string {
+	return path.Base(n.path)
+}
+
+func (n *node) IsDir() bool {
+	return n.isDir
+}
+
+func (n *node) Children() ([]noder.Noder, error) {
+	if err := n.calculateChildren(); err != nil {
+		return nil, err
+	}
+
+	return n.children, nil
+}
+
+func (n *node) NumChildren() (int, error) {
+	if err := n.calculateChildren(); err != nil {
+		return -1, err
+	}
+
+	return len(n.children), nil
+}
+
+func (n *node) calculateChildren() error {
+	if !n.IsDir() {
+		return nil
+	}
+
+	if len(n.children) != 0 {
+		return nil
+	}
+
+	files, err := n.fs.ReadDir(n.path)
+	if err != nil {
+		if os.IsNotExist(err) {
+			return nil
+		}
+
+		return nil
+	}
+
+	for _, file := range files {
+		if _, ok := ignore[file.Name()]; ok {
+			continue
+		}
+
+		c, err := n.newChildNode(file)
+		if err != nil {
+			return err
+		}
+
+		n.children = append(n.children, c)
+	}
+
+	return nil
+}
+
+func (n *node) newChildNode(file os.FileInfo) (*node, error) {
+	path := path.Join(n.path, file.Name())
+
+	hash, err := n.calculateHash(path, file)
+	if err != nil {
+		return nil, err
+	}
+
+	node := &node{
+		fs:         n.fs,
+		submodules: n.submodules,
+
+		path:  path,
+		hash:  hash,
+		isDir: file.IsDir(),
+	}
+
+	if hash, isSubmodule := n.submodules[path]; isSubmodule {
+		node.hash = append(hash[:], filemode.Submodule.Bytes()...)
+		node.isDir = false
+	}
+
+	return node, nil
+}
+
+func (n *node) calculateHash(path string, file os.FileInfo) ([]byte, error) {
+	if file.IsDir() {
+		return make([]byte, 24), nil
+	}
+
+	var hash plumbing.Hash
+	var err error
+	if file.Mode()&os.ModeSymlink != 0 {
+		hash, err = n.doCalculateHashForSymlink(path, file)
+	} else {
+		hash, err = n.doCalculateHashForRegular(path, file)
+	}
+
+	if err != nil {
+		return nil, err
+	}
+
+	mode, err := filemode.NewFromOSFileMode(file.Mode())
+	if err != nil {
+		return nil, err
+	}
+
+	return append(hash[:], mode.Bytes()...), nil
+}
+
+func (n *node) doCalculateHashForRegular(path string, file os.FileInfo) (plumbing.Hash, error) {
+	f, err := n.fs.Open(path)
+	if err != nil {
+		return plumbing.ZeroHash, err
+	}
+
+	defer f.Close()
+
+	h := plumbing.NewHasher(plumbing.BlobObject, file.Size())
+	if _, err := io.Copy(h, f); err != nil {
+		return plumbing.ZeroHash, err
+	}
+
+	return h.Sum(), nil
+}
+
+func (n *node) doCalculateHashForSymlink(path string, file os.FileInfo) (plumbing.Hash, error) {
+	target, err := n.fs.Readlink(path)
+	if err != nil {
+		return plumbing.ZeroHash, err
+	}
+
+	h := plumbing.NewHasher(plumbing.BlobObject, file.Size())
+	if _, err := h.Write([]byte(target)); err != nil {
+		return plumbing.ZeroHash, err
+	}
+
+	return h.Sum(), nil
+}
+
+func (n *node) String() string {
+	return n.path
+}
diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/index/node.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/index/node.go
new file mode 100644
index 0000000000..9622622483
--- /dev/null
+++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/index/node.go
@@ -0,0 +1,90 @@
+package index
+
+import (
+	"path"
+	"strings"
+
+	"gopkg.in/src-d/go-git.v4/plumbing/format/index"
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+// The node represents a index.Entry or a directory inferred from the path
+// of all entries. It implements the interface noder.Noder of merkletrie
+// package.
+//
+// This implementation implements a "standard" hash method being able to be
+// compared with any other noder.Noder implementation inside of go-git
+type node struct {
+	path     string
+	entry    *index.Entry
+	children []noder.Noder
+	isDir    bool
+}
+
+// NewRootNode returns the root node of a computed tree from a index.Index,
+func NewRootNode(idx *index.Index) noder.Noder {
+	const rootNode = ""
+
+	m := map[string]*node{rootNode: {isDir: true}}
+
+	for _, e := range idx.Entries {
+		parts := strings.Split(e.Name, string("/"))
+
+		var fullpath string
+		for _, part := range parts {
+			parent := fullpath
+			fullpath = path.Join(fullpath, part)
+
+			if _, ok := m[fullpath]; ok {
+				continue
+			}
+
+			n := &node{path: fullpath}
+			if fullpath == e.Name {
+				n.entry = e
+			} else {
+				n.isDir = true
+			}
+
+			m[n.path] = n
+			m[parent].children = append(m[parent].children, n)
+		}
+	}
+
+	return m[rootNode]
+}
+
+func (n *node) String() string {
+	return n.path
+}
+
+// Hash the hash of a filesystem is a 24-byte slice, is the result of
+// concatenating the computed plumbing.Hash of the file as a Blob and its
+// plumbing.FileMode; that way the difftree algorithm will detect changes in the
+// contents of files and also in their mode.
+//
+// If the node is computed and not based on a index.Entry the hash is equals
+// to a 24-bytes slices of zero values.
+func (n *node) Hash() []byte {
+	if n.entry == nil {
+		return make([]byte, 24)
+	}
+
+	return append(n.entry.Hash[:], n.entry.Mode.Bytes()...)
+}
+
+func (n *node) Name() string {
+	return path.Base(n.path)
+}
+
+func (n *node) IsDir() bool {
+	return n.isDir
+}
+
+func (n *node) Children() ([]noder.Noder, error) {
+	return n.children, nil
+}
+
+func (n *node) NumChildren() (int, error) {
+	return len(n.children), nil
+}
diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/internal/frame/frame.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/internal/frame/frame.go
new file mode 100644
index 0000000000..a0b042ee61
--- /dev/null
+++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/internal/frame/frame.go
@@ -0,0 +1,91 @@
+package frame
+
+import (
+	"bytes"
+	"fmt"
+	"sort"
+	"strings"
+
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+// A Frame is a collection of siblings in a trie, sorted alphabetically
+// by name.
+type Frame struct {
+	// siblings, sorted in reverse alphabetical order by name
+	stack []noder.Noder
+}
+
+type byName []noder.Noder
+
+func (a byName) Len() int      { return len(a) }
+func (a byName) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
+func (a byName) Less(i, j int) bool {
+	return strings.Compare(a[i].Name(), a[j].Name()) < 0
+}
+
+// New returns a frame with the children of the provided node.
+func New(n noder.Noder) (*Frame, error) {
+	children, err := n.Children()
+	if err != nil {
+		return nil, err
+	}
+
+	sort.Sort(sort.Reverse(byName(children)))
+	return &Frame{
+		stack: children,
+	}, nil
+}
+
+// String returns the quoted names of the noders in the frame sorted in
+// alphabeticall order by name, surrounded by square brackets and
+// separated by comas.
+//
+// Examples:
+//     []
+//     ["a", "b"]
+func (f *Frame) String() string {
+	var buf bytes.Buffer
+	_ = buf.WriteByte('[')
+
+	sep := ""
+	for i := f.Len() - 1; i >= 0; i-- {
+		_, _ = buf.WriteString(sep)
+		sep = ", "
+		_, _ = buf.WriteString(fmt.Sprintf("%q", f.stack[i].Name()))
+	}
+
+	_ = buf.WriteByte(']')
+
+	return buf.String()
+}
+
+// First returns, but dont extract, the noder with the alphabetically
+// smaller name in the frame and true if the frame was not empy.
+// Otherwise it returns nil and false.
+func (f *Frame) First() (noder.Noder, bool) {
+	if f.Len() == 0 {
+		return nil, false
+	}
+
+	top := f.Len() - 1
+
+	return f.stack[top], true
+}
+
+// Drop extracts the noder with the alphabetically smaller name in the
+// frame or does nothing if the frame was empty.
+func (f *Frame) Drop() {
+	if f.Len() == 0 {
+		return
+	}
+
+	top := f.Len() - 1
+	f.stack[top] = nil
+	f.stack = f.stack[:top]
+}
+
+// Len returns the number of noders in the frame.
+func (f *Frame) Len() int {
+	return len(f.stack)
+}
diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/iter.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/iter.go
new file mode 100644
index 0000000000..b4d4c99a33
--- /dev/null
+++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/iter.go
@@ -0,0 +1,216 @@
+package merkletrie
+
+import (
+	"fmt"
+	"io"
+
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/internal/frame"
+	"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+// Iter is an iterator for merkletries (only the trie part of the
+// merkletrie is relevant here, it does not use the Hasher interface).
+//
+// The iteration is performed in depth-first pre-order.  Entries at each
+// depth are traversed in (case-sensitive) alphabetical order.
+//
+// This is the kind of traversal you will expect when listing ordinary
+// files and directories recursively, for example:
+//
+//          Trie           Traversal order
+//          ----           ---------------
+//           .
+//         / | \           c
+//        /  |  \          d/
+//       d   c   z   ===>  d/a
+//      / \                d/b
+//     b   a               z
+//
+//
+// This iterator is somewhat especial as you can chose to skip whole
+// "directories" when iterating:
+//
+// - The Step method will iterate normally.
+//
+// - the Next method will not descend deeper into the tree.
+//
+// For example, if the iterator is at `d/`, the Step method will return
+// `d/a` while the Next would have returned `z` instead (skipping `d/`
+// and its descendants).  The name of the these two methods are based on
+// the well known "next" and "step" operations, quite common in
+// debuggers, like gdb.
+//
+// The paths returned by the iterator will be relative, if the iterator
+// was created from a single node, or absolute, if the iterator was
+// created from the path to the node (the path will be prefixed to all
+// returned paths).
+type Iter struct {
+	// Tells if the iteration has started.
+	hasStarted bool
+	// The top of this stack has the current node and its siblings.  The
+	// rest of the stack keeps the ancestors of the current node and
+	// their corresponding siblings.  The current element is always the
+	// top element of the top frame.
+	//
+	// When "step"ping into a node, its children are pushed as a new
+	// frame.
+	//
+	// When "next"ing pass a node, the current element is dropped by
+	// popping the top frame.
+	frameStack []*frame.Frame
+	// The base path used to turn the relative paths used internally by
+	// the iterator into absolute paths used by external applications.
+	// For relative iterator this will be nil.
+	base noder.Path
+}
+
+// NewIter returns a new relative iterator using the provider noder as
+// its unnamed root.  When iterating, all returned paths will be
+// relative to node.
+func NewIter(n noder.Noder) (*Iter, error) {
+	return newIter(n, nil)
+}
+
+// NewIterFromPath returns a new absolute iterator from the noder at the
+// end of the path p.  When iterating, all returned paths will be
+// absolute, using the root of the path p as their root.
+func NewIterFromPath(p noder.Path) (*Iter, error) {
+	return newIter(p, p) // Path implements Noder
+}
+
+func newIter(root noder.Noder, base noder.Path) (*Iter, error) {
+	ret := &Iter{
+		base: base,
+	}
+
+	if root == nil {
+		return ret, nil
+	}
+
+	frame, err := frame.New(root)
+	if err != nil {
+		return nil, err
+	}
+	ret.push(frame)
+
+	return ret, nil
+}
+
+func (iter *Iter) top() (*frame.Frame, bool) {
+	if len(iter.frameStack) == 0 {
+		return nil, false
+	}
+	top := len(iter.frameStack) - 1
+
+	return iter.frameStack[top], true
+}
+
+func (iter *Iter) push(f *frame.Frame) {
+	iter.frameStack = append(iter.frameStack, f)
+}
+
+const (
+	doDescend   = true
+	dontDescend = false
+)
+
+// Next returns the path of the next node without descending deeper into
+// the trie and nil.  If there are no more entries in the trie it
+// returns nil and io.EOF.  In case of error, it will return nil and the
+// error.
+func (iter *Iter) Next() (noder.Path, error) {
+	return iter.advance(dontDescend)
+}
+
+// Step returns the path to the next node in the trie, descending deeper
+// into it if needed, and nil. If there are no more nodes in the trie,
+// it returns nil and io.EOF.  In case of error, it will return nil and
+// the error.
+func (iter *Iter) Step() (noder.Path, error) {
+	return iter.advance(doDescend)
+}
+
+// Advances the iterator in the desired direction: descend or
+// dontDescend.
+//
+// Returns the new current element and a nil error on success.  If there
+// are no more elements in the trie below the base, it returns nil, and
+// io.EOF.  Returns nil and an error in case of errors.
+func (iter *Iter) advance(wantDescend bool) (noder.Path, error) {
+	current, err := iter.current()
+	if err != nil {
+		return nil, err
+	}
+
+	// The first time we just return the current node.
+	if !iter.hasStarted {
+		iter.hasStarted = true
+		return current, nil
+	}
+
+	// Advances means getting a next current node, either its first child or
+	// its next sibling, depending if we must descend or not.
+	numChildren, err := current.NumChildren()
+	if err != nil {
+		return nil, err
+	}
+
+	mustDescend := numChildren != 0 && wantDescend
+	if mustDescend {
+		// descend: add a new frame with the current's children.
+		frame, err := frame.New(current)
+		if err != nil {
+			return nil, err
+		}
+		iter.push(frame)
+	} else {
+		// don't descend: just drop the current node
+		iter.drop()
+	}
+
+	return iter.current()
+}
+
+// Returns the path to the current node, adding the base if there was
+// one, and a nil error.  If there were no noders left, it returns nil
+// and io.EOF.  If an error occurred, it returns nil and the error.
+func (iter *Iter) current() (noder.Path, error) {
+	if topFrame, ok := iter.top(); !ok {
+		return nil, io.EOF
+	} else if _, ok := topFrame.First(); !ok {
+		return nil, io.EOF
+	}
+
+	ret := make(noder.Path, 0, len(iter.base)+len(iter.frameStack))
+
+	// concat the base...
+	ret = append(ret, iter.base...)
+	// ... and the current node and all its ancestors
+	for i, f := range iter.frameStack {
+		t, ok := f.First()
+		if !ok {
+			panic(fmt.Sprintf("frame %d is empty", i))
+		}
+		ret = append(ret, t)
+	}
+
+	return ret, nil
+}
+
+// removes the current node if any, and all the frames that become empty as a
+// consequence of this action.
+func (iter *Iter) drop() {
+	frame, ok := iter.top()
+	if !ok {
+		return
+	}
+
+	frame.Drop()
+	// if the frame is empty, remove it and its parent, recursively
+	if frame.Len() == 0 {
+		top := len(iter.frameStack) - 1
+		iter.frameStack[top] = nil
+		iter.frameStack = iter.frameStack[:top]
+		iter.drop()
+	}
+}
diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/noder.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/noder.go
new file mode 100644
index 0000000000..d6b3de4ada
--- /dev/null
+++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/noder.go
@@ -0,0 +1,59 @@
+// Package noder provide an interface for defining nodes in a
+// merkletrie, their hashes and their paths (a noders and its
+// ancestors).
+//
+// The hasher interface is easy to implement naively by elements that
+// already have a hash, like git blobs and trees.  More sophisticated
+// implementations can implement the Equal function in exotic ways
+// though: for instance, comparing the modification time of directories
+// in a filesystem.
+package noder
+
+import "fmt"
+
+// Hasher interface is implemented by types that can tell you
+// their hash.
+type Hasher interface {
+	Hash() []byte
+}
+
+// Equal functions take two hashers and return if they are equal.
+//
+// These functions are expected to be faster than reflect.Equal or
+// reflect.DeepEqual because they can compare just the hash of the
+// objects, instead of their contents, so they are expected to be O(1).
+type Equal func(a, b Hasher) bool
+
+// The Noder interface is implemented by the elements of a Merkle Trie.
+//
+// There are two types of elements in a Merkle Trie:
+//
+// - file-like nodes: they cannot have children.
+//
+// - directory-like nodes: they can have 0 or more children and their
+// hash is calculated by combining their children hashes.
+type Noder interface {
+	Hasher
+	fmt.Stringer // for testing purposes
+	// Name returns the name of an element (relative, not its full
+	// path).
+	Name() string
+	// IsDir returns true if the element is a directory-like node or
+	// false if it is a file-like node.
+	IsDir() bool
+	// Children returns the children of the element.  Note that empty
+	// directory-like noders and file-like noders will both return
+	// NoChildren.
+	Children() ([]Noder, error)
+	// 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, error)
+}
+
+// NoChildren represents the children of a noder without children.
+var NoChildren = []Noder{}
diff --git a/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/path.go b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/path.go
new file mode 100644
index 0000000000..e9c905c96b
--- /dev/null
+++ b/vendor/gopkg.in/src-d/go-git.v4/utils/merkletrie/noder/path.go
@@ -0,0 +1,94 @@
+package noder
+
+import (
+	"bytes"
+	"strings"
+
+	"golang.org/x/text/unicode/norm"
+)
+
+// Path values represent a noder and its ancestors.  The root goes first
+// and the actual final noder the path is referring to will be the last.
+//
+// A path implements the Noder interface, redirecting all the interface
+// calls to its final noder.
+//
+// Paths build from an empty Noder slice are not valid paths and should
+// not be used.
+type Path []Noder
+
+// String returns the full path of the final noder as a string, using
+// "/" as the separator.
+func (p Path) String() string {
+	var buf bytes.Buffer
+	sep := ""
+	for _, e := range p {
+		_, _ = buf.WriteString(sep)
+		sep = "/"
+		_, _ = buf.WriteString(e.Name())
+	}
+
+	return buf.String()
+}
+
+// Last returns the final noder in the path.
+func (p Path) Last() Noder {
+	return p[len(p)-1]
+}
+
+// Hash returns the hash of the final noder of the path.
+func (p Path) Hash() []byte {
+	return p.Last().Hash()
+}
+
+// Name returns the name of the final noder of the path.
+func (p Path) Name() string {
+	return p.Last().Name()
+}
+
+// IsDir returns if the final noder of the path is a directory-like
+// noder.
+func (p Path) IsDir() bool {
+	return p.Last().IsDir()
+}
+
+// Children returns the children of the final noder in the path.
+func (p Path) Children() ([]Noder, error) {
+	return p.Last().Children()
+}
+
+// NumChildren returns the number of children the final noder of the
+// path has.
+func (p Path) NumChildren() (int, error) {
+	return p.Last().NumChildren()
+}
+
+// Compare returns -1, 0 or 1 if the path p is smaller, equal or bigger
+// than other, in "directory order"; for example:
+//
+// "a" < "b"
+// "a/b/c/d/z" < "b"
+// "a/b/a" > "a/b"
+func (p Path) Compare(other Path) int {
+	i := 0
+	for {
+		switch {
+		case len(other) == len(p) && i == len(p):
+			return 0
+		case i == len(other):
+			return 1
+		case i == len(p):
+			return -1
+		default:
+			form := norm.Form(norm.NFC)
+			this := form.String(p[i].Name())
+			that := form.String(other[i].Name())
+
+			cmp := strings.Compare(this, that)
+			if cmp != 0 {
+				return cmp
+			}
+		}
+		i++
+	}
+}