Create merge-base feature

Signed-off-by: David Pordomingo <David.Pordomingo.F@gmail.com>

4 files changed, 971 insertions, 0 deletions

diff --git a/plumbing/object/commit_walker_bfs_filtered.go b/plumbing/object/commit_walker_bfs_filtered.go
new file mode 100644
index 0000000..b12523d
--- /dev/null
+++ b/plumbing/object/commit_walker_bfs_filtered.go
@@ -0,0 +1,176 @@
+package object
+
+import (
+	"io"
+
+	"gopkg.in/src-d/go-git.v4/plumbing"
+	"gopkg.in/src-d/go-git.v4/plumbing/storer"
+)
+
+// NewFilterCommitIter returns a CommitIter that walks the commit history,
+// starting at the passed commit and visiting its parents in Breadth-first order.
+// The commits returned by the CommitIter will validate the passed CommitFilter.
+// The history won't be transversed beyond a commit if isLimit is true for it.
+// Each commit will be visited only once.
+// If the commit history can not be traversed, or the Close() method is called,
+// the CommitIter won't return more commits.
+// If no isValid is passed, all ancestors of from commit will be valid.
+// If no isLimit is limmit, all ancestors of all commits will be visited.
+func NewFilterCommitIter(
+	from *Commit,
+	isValid *CommitFilter,
+	isLimit *CommitFilter,
+) CommitIter {
+	var validFilter CommitFilter
+	if isValid == nil {
+		validFilter = func(_ *Commit) bool {
+			return true
+		}
+	} else {
+		validFilter = *isValid
+	}
+
+	var limitFilter CommitFilter
+	if isLimit == nil {
+		limitFilter = func(_ *Commit) bool {
+			return false
+		}
+	} else {
+		limitFilter = *isLimit
+	}
+
+	return &filterCommitIter{
+		isValid: validFilter,
+		isLimit: limitFilter,
+		visited: map[plumbing.Hash]struct{}{},
+		queue:   []*Commit{from},
+	}
+}
+
+// CommitFilter returns a boolean for the passed Commit
+type CommitFilter func(*Commit) bool
+
+// filterCommitIter implments CommitIter
+type filterCommitIter struct {
+	isValid CommitFilter
+	isLimit CommitFilter
+	visited map[plumbing.Hash]struct{}
+	queue   []*Commit
+	lastErr error
+}
+
+// Next returns the next commit of the CommitIter.
+// It will return io.EOF if there are no more commits to visit,
+// or an error if the history could not be traversed.
+func (w *filterCommitIter) Next() (*Commit, error) {
+	var commit *Commit
+	var err error
+	for {
+		commit, err = w.popNewFromQueue()
+		if err != nil {
+			return nil, w.close(err)
+		}
+
+		w.visited[commit.Hash] = struct{}{}
+
+		if !w.isLimit(commit) {
+			err = w.addToQueue(commit.s, commit.ParentHashes...)
+			if err != nil {
+				return nil, w.close(err)
+			}
+		}
+
+		if w.isValid(commit) {
+			return commit, nil
+		}
+	}
+}
+
+// ForEach runs the passed callback over each Commit returned by the CommitIter
+// until the callback returns an error or there is no more commits to traverse.
+func (w *filterCommitIter) ForEach(cb func(*Commit) error) error {
+	for {
+		commit, err := w.Next()
+		if err == io.EOF {
+			break
+		}
+
+		if err != nil {
+			return err
+		}
+
+		if err := cb(commit); err == storer.ErrStop {
+			break
+		} else if err != nil {
+			return err
+		}
+	}
+
+	return nil
+}
+
+// Error returns the error that caused that the CommitIter is no longer returning commits
+func (w *filterCommitIter) Error() error {
+	return w.lastErr
+}
+
+// Close closes the CommitIter
+func (w *filterCommitIter) Close() {
+	w.visited = map[plumbing.Hash]struct{}{}
+	w.queue = []*Commit{}
+	w.isLimit = nil
+	w.isValid = nil
+}
+
+// close closes the CommitIter with an error
+func (w *filterCommitIter) close(err error) error {
+	w.Close()
+	w.lastErr = err
+	return err
+}
+
+// popNewFromQueue returns the first new commit from the internal fifo queue,
+// or an io.EOF error if the queue is empty
+func (w *filterCommitIter) popNewFromQueue() (*Commit, error) {
+	var first *Commit
+	for {
+		if len(w.queue) == 0 {
+			if w.lastErr != nil {
+				return nil, w.lastErr
+			}
+
+			return nil, io.EOF
+		}
+
+		first = w.queue[0]
+		w.queue = w.queue[1:]
+		if _, ok := w.visited[first.Hash]; ok {
+			continue
+		}
+
+		return first, nil
+	}
+}
+
+// addToQueue adds the passed commits to the internal fifo queue if they weren't seen
+// or returns an error if the passed hashes could not be used to get valid commits
+func (w *filterCommitIter) addToQueue(
+	store storer.EncodedObjectStorer,
+	hashes ...plumbing.Hash,
+) error {
+	for _, hash := range hashes {
+		if _, ok := w.visited[hash]; ok {
+			continue
+		}
+
+		commit, err := GetCommit(store, hash)
+		if err != nil {
+			return err
+		}
+
+		w.queue = append(w.queue, commit)
+	}
+
+	return nil
+}
+
diff --git a/plumbing/object/commit_walker_bfs_filtered_test.go b/plumbing/object/commit_walker_bfs_filtered_test.go
new file mode 100644
index 0000000..d31bdf0
--- /dev/null
+++ b/plumbing/object/commit_walker_bfs_filtered_test.go
@@ -0,0 +1,262 @@
+package object
+
+import (
+	"fmt"
+	"strings"
+
+	"gopkg.in/src-d/go-git.v4/plumbing"
+	"gopkg.in/src-d/go-git.v4/plumbing/storer"
+
+	. "gopkg.in/check.v1"
+)
+
+var _ = Suite(&filterCommitIterSuite{})
+
+type filterCommitIterSuite struct {
+	BaseObjectsSuite
+}
+
+func commitsFromIter(iter CommitIter) ([]*Commit, error) {
+	var commits []*Commit
+	err := iter.ForEach(func(c *Commit) error {
+		commits = append(commits, c)
+		return nil
+	})
+
+	return commits, err
+}
+
+func assertHashes(c *C, commits []*Commit, hashes []string) {
+	if len(commits) != len(hashes) {
+		var expected []string
+		for _, c := range hashes {
+			expected = append(expected, c)
+		}
+		fmt.Println("expected:", strings.Join(expected, ", "))
+		var got []string
+		for _, c := range commits {
+			got = append(got, c.Hash.String())
+		}
+		fmt.Println("     got:", strings.Join(got, ", "))
+	}
+
+	c.Assert(commits, HasLen, len(hashes))
+	for i, commit := range commits {
+		c.Assert(hashes[i], Equals, commit.Hash.String())
+	}
+}
+
+func validIfCommit(ignored plumbing.Hash) CommitFilter {
+	return func(c *Commit) bool {
+		if c.Hash == ignored {
+			return true
+		}
+
+		return false
+	}
+}
+
+func not(filter CommitFilter) CommitFilter {
+	return func(c *Commit) bool {
+		return !filter(c)
+	}
+}
+
+/*
+// TestCase history
+
+* 6ecf0ef2c2dffb796033e5a02219af86ec6584e5 <- HEAD
+|
+| * e8d3ffab552895c19b9fcf7aa264d277cde33881
+|/
+* 918c48b83bd081e863dbe1b80f8998f058cd8294
+|
+* af2d6a6954d532f8ffb47615169c8fdf9d383a1a
+|
+* 1669dce138d9b841a518c64b10914d88f5e488ea
+|\
+| * a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69	// isLimit
+| |\
+| | * b8e471f58bcbca63b07bda20e428190409c2db47  // ignored if isLimit is passed
+| |/
+* | 35e85108805c84807bc66a02d91535e1e24b38b9	// isValid; ignored if passed as !isValid
+|/
+* b029517f6300c2da0f4b651b8642506cd6aaf45d
+*/
+
+// TestFilterCommitIter asserts that FilterCommitIter returns all commits from
+// history, but e8d3ffab552895c19b9fcf7aa264d277cde33881, that is not reachable
+// from HEAD
+func (s *filterCommitIterSuite) TestFilterCommitIter(c *C) {
+	from := s.commit(c, s.Fixture.Head)
+
+	commits, err := commitsFromIter(NewFilterCommitIter(from, nil, nil))
+	c.Assert(err, IsNil)
+
+	expected := []string{
+		"6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+		"918c48b83bd081e863dbe1b80f8998f058cd8294",
+		"af2d6a6954d532f8ffb47615169c8fdf9d383a1a",
+		"1669dce138d9b841a518c64b10914d88f5e488ea",
+		"35e85108805c84807bc66a02d91535e1e24b38b9",
+		"a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69",
+		"b029517f6300c2da0f4b651b8642506cd6aaf45d",
+		"b8e471f58bcbca63b07bda20e428190409c2db47",
+	}
+
+	assertHashes(c, commits, expected)
+}
+
+// TestFilterCommitIterWithValid asserts that FilterCommitIter returns only commits
+// that matches the passed isValid filter; in this testcase, it was filtered out
+// all commits but one from history
+func (s *filterCommitIterSuite) TestFilterCommitIterWithValid(c *C) {
+	from := s.commit(c, s.Fixture.Head)
+
+	validIf := validIfCommit(plumbing.NewHash("35e85108805c84807bc66a02d91535e1e24b38b9"))
+	commits, err := commitsFromIter(NewFilterCommitIter(from, &validIf, nil))
+	c.Assert(err, IsNil)
+
+	expected := []string{
+		"35e85108805c84807bc66a02d91535e1e24b38b9",
+	}
+
+	assertHashes(c, commits, expected)
+}
+
+// that matches the passed isValid filter; in this testcase, it was filtered out
+// only one commit from history
+func (s *filterCommitIterSuite) TestFilterCommitIterWithInvalid(c *C) {
+	from := s.commit(c, s.Fixture.Head)
+
+	validIf := validIfCommit(plumbing.NewHash("35e85108805c84807bc66a02d91535e1e24b38b9"))
+	validIfNot := not(validIf)
+	commits, err := commitsFromIter(NewFilterCommitIter(from, &validIfNot, nil))
+	c.Assert(err, IsNil)
+
+	expected := []string{
+		"6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+		"918c48b83bd081e863dbe1b80f8998f058cd8294",
+		"af2d6a6954d532f8ffb47615169c8fdf9d383a1a",
+		"1669dce138d9b841a518c64b10914d88f5e488ea",
+		"a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69",
+		"b029517f6300c2da0f4b651b8642506cd6aaf45d",
+		"b8e471f58bcbca63b07bda20e428190409c2db47",
+	}
+
+	assertHashes(c, commits, expected)
+}
+
+// TestFilterCommitIterWithNoValidCommits asserts that FilterCommitIter returns
+// no commits if the passed isValid filter does not allow any commit
+func (s *filterCommitIterSuite) TestFilterCommitIterWithNoValidCommits(c *C) {
+	from := s.commit(c, s.Fixture.Head)
+
+	validIf := validIfCommit(plumbing.NewHash("THIS_COMMIT_DOES_NOT_EXIST"))
+	commits, err := commitsFromIter(NewFilterCommitIter(from, &validIf, nil))
+	c.Assert(err, IsNil)
+	c.Assert(commits, HasLen, 0)
+}
+
+// TestFilterCommitIterWithStopAt asserts that FilterCommitIter returns only commits
+// are not beyond a isLimit filter
+func (s *filterCommitIterSuite) TestFilterCommitIterWithStopAt(c *C) {
+	from := s.commit(c, s.Fixture.Head)
+
+	stopAtRule := validIfCommit(plumbing.NewHash("a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69"))
+	commits, err := commitsFromIter(NewFilterCommitIter(from, nil, &stopAtRule))
+	c.Assert(err, IsNil)
+
+	expected := []string{
+		"6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+		"918c48b83bd081e863dbe1b80f8998f058cd8294",
+		"af2d6a6954d532f8ffb47615169c8fdf9d383a1a",
+		"1669dce138d9b841a518c64b10914d88f5e488ea",
+		"35e85108805c84807bc66a02d91535e1e24b38b9",
+		"a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69",
+		"b029517f6300c2da0f4b651b8642506cd6aaf45d",
+	}
+
+	assertHashes(c, commits, expected)
+}
+
+// TestFilterCommitIterWithStopAt asserts that FilterCommitIter works properly
+// with isValid and isLimit filters
+func (s *filterCommitIterSuite) TestFilterCommitIterWithInvalidAndStopAt(c *C) {
+	from := s.commit(c, s.Fixture.Head)
+
+	stopAtRule := validIfCommit(plumbing.NewHash("a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69"))
+	validIf := validIfCommit(plumbing.NewHash("35e85108805c84807bc66a02d91535e1e24b38b9"))
+	validIfNot := not(validIf)
+	commits, err := commitsFromIter(NewFilterCommitIter(from, &validIfNot, &stopAtRule))
+	c.Assert(err, IsNil)
+
+	expected := []string{
+		"6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+		"918c48b83bd081e863dbe1b80f8998f058cd8294",
+		"af2d6a6954d532f8ffb47615169c8fdf9d383a1a",
+		"1669dce138d9b841a518c64b10914d88f5e488ea",
+		"a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69",
+		"b029517f6300c2da0f4b651b8642506cd6aaf45d",
+	}
+
+	assertHashes(c, commits, expected)
+}
+
+// TestIteratorForEachCallbackReturn that ForEach callback does not cause
+// the ForEach to return an error if it returned an ErrStop
+//
+//   - 6ecf0ef2c2dffb796033e5a02219af86ec6584e5
+//   - 918c48b83bd081e863dbe1b80f8998f058cd8294 //<- stop
+//   - af2d6a6954d532f8ffb47615169c8fdf9d383a1a
+//   - 1669dce138d9b841a518c64b10914d88f5e488ea //<- err
+//   - 35e85108805c84807bc66a02d91535e1e24b38b9
+//   - a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69
+//   - b029517f6300c2da0f4b651b8642506cd6aaf45d
+//   - b8e471f58bcbca63b07bda20e428190409c2db47
+func (s *filterCommitIterSuite) TestIteratorForEachCallbackReturn(c *C) {
+
+	var visited []*Commit
+	errUnexpected := fmt.Errorf("Could not continue")
+	cb := func(c *Commit) error {
+		switch c.Hash {
+		case plumbing.NewHash("918c48b83bd081e863dbe1b80f8998f058cd8294"):
+			return storer.ErrStop
+		case plumbing.NewHash("1669dce138d9b841a518c64b10914d88f5e488ea"):
+			return errUnexpected
+		}
+
+		visited = append(visited, c)
+		return nil
+	}
+
+	from := s.commit(c, s.Fixture.Head)
+
+	iter := NewFilterCommitIter(from, nil, nil)
+	err := iter.ForEach(cb)
+	c.Assert(err, IsNil)
+	expected := []string{
+		"6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+	}
+	assertHashes(c, visited, expected)
+
+	err = iter.ForEach(cb)
+	c.Assert(err, Equals, errUnexpected)
+	expected = []string{
+		"6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+		"af2d6a6954d532f8ffb47615169c8fdf9d383a1a",
+	}
+	assertHashes(c, visited, expected)
+
+	err = iter.ForEach(cb)
+	c.Assert(err, IsNil)
+	expected = []string{
+		"6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+		"af2d6a6954d532f8ffb47615169c8fdf9d383a1a",
+		"35e85108805c84807bc66a02d91535e1e24b38b9",
+		"a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69",
+		"b029517f6300c2da0f4b651b8642506cd6aaf45d",
+		"b8e471f58bcbca63b07bda20e428190409c2db47",
+	}
+	assertHashes(c, visited, expected)
+}
diff --git a/plumbing/object/merge_base.go b/plumbing/object/merge_base.go
new file mode 100644
index 0000000..689e421
--- /dev/null
+++ b/plumbing/object/merge_base.go
@@ -0,0 +1,210 @@
+package object
+
+import (
+	"fmt"
+	"sort"
+
+	"gopkg.in/src-d/go-git.v4/plumbing"
+	"gopkg.in/src-d/go-git.v4/plumbing/storer"
+)
+
+// errIsReachable is thrown when first commit is an ancestor of the second
+var errIsReachable = fmt.Errorf("first is reachable from second")
+
+// MergeBase mimics the behavior of `git merge-base actual other`, returning the
+// best common ancestor between the actual and the passed one.
+// The best common ancestors can not be reached from other common ancestors.
+func (c *Commit) MergeBase(other *Commit) ([]*Commit, error) {
+	// use sortedByCommitDateDesc strategy
+	sorted := sortByCommitDateDesc(c, other)
+	newer := sorted[0]
+	older := sorted[1]
+
+	newerHistory, err := ancestorsIndex(older, newer)
+	if err == errIsReachable {
+		return []*Commit{older}, nil
+	}
+
+	if err != nil {
+		return nil, err
+	}
+
+	var res []*Commit
+	inNewerHistory := isInIndexCommitFilter(newerHistory)
+	resIter := NewFilterCommitIter(older, &inNewerHistory, &inNewerHistory)
+	err = resIter.ForEach(func(commit *Commit) error {
+		res = append(res, commit)
+		return nil
+	})
+
+	return Independents(res)
+}
+
+// IsAncestor returns true if the actual commit is ancestor of the passed one.
+// It returns an error if the history is not transversable
+// It mimics the behavior of `git merge --is-ancestor actual other`
+func (c *Commit) IsAncestor(other *Commit) (bool, error) {
+	found := false
+	iter := NewCommitPreorderIter(other, nil, nil)
+	err := iter.ForEach(func(comm *Commit) error {
+		if comm.Hash != c.Hash {
+			return nil
+		}
+
+		found = true
+		return storer.ErrStop
+	})
+
+	return found, err
+}
+
+// ancestorsIndex returns a map with the ancestors of the starting commit if the
+// excluded one is not one of them. It returns errIsReachable if the excluded commit
+// is ancestor of the starting, or another error if the history is not traversable.
+func ancestorsIndex(excluded, starting *Commit) (map[plumbing.Hash]struct{}, error) {
+	if excluded.Hash.String() == starting.Hash.String() {
+		return nil, errIsReachable
+	}
+
+	startingHistory := map[plumbing.Hash]struct{}{}
+	startingIter := NewCommitIterBSF(starting, nil, nil)
+	err := startingIter.ForEach(func(commit *Commit) error {
+		if commit.Hash == excluded.Hash {
+			return errIsReachable
+		}
+
+		startingHistory[commit.Hash] = struct{}{}
+		return nil
+	})
+
+	if err != nil {
+		return nil, err
+	}
+
+	return startingHistory, nil
+}
+
+// Independents returns a subset of the passed commits, that are not reachable the others
+// It mimics the behavior of `git merge-base --independent commit...`.
+func Independents(commits []*Commit) ([]*Commit, error) {
+	// use sortedByCommitDateDesc strategy
+	candidates := sortByCommitDateDesc(commits...)
+	candidates = removeDuplicated(candidates)
+
+	seen := map[plumbing.Hash]struct{}{}
+	var isLimit CommitFilter = func(commit *Commit) bool {
+		_, ok := seen[commit.Hash]
+		return ok
+	}
+
+	if len(candidates) < 2 {
+		return candidates, nil
+	}
+
+	pos := 0
+	for {
+		from := candidates[pos]
+		others := remove(candidates, from)
+		fromHistoryIter := NewFilterCommitIter(from, nil, &isLimit)
+		err := fromHistoryIter.ForEach(func(fromAncestor *Commit) error {
+			for _, other := range others {
+				if fromAncestor.Hash == other.Hash {
+					candidates = remove(candidates, other)
+					others = remove(others, other)
+				}
+			}
+
+			if len(candidates) == 1 {
+				return storer.ErrStop
+			}
+
+			seen[fromAncestor.Hash] = struct{}{}
+			return nil
+		})
+
+		if err != nil {
+			return nil, err
+		}
+
+		nextPos := indexOf(candidates, from) + 1
+		if nextPos >= len(candidates) {
+			break
+		}
+
+		pos = nextPos
+	}
+
+	return candidates, nil
+}
+
+// sortByCommitDateDesc returns the passed commits, sorted by `committer.When desc`
+//
+// Following this strategy, it is tried to reduce the time needed when walking
+// the history from one commit to reach the others. It is assumed that ancestors
+// use to be committed before its descendant;
+// That way `Independents(A^, A)` will be processed as being `Independents(A, A^)`;
+// so starting by `A` it will be reached `A^` way sooner than walking from `A^`
+// to the initial commit, and then from `A` to `A^`.
+func sortByCommitDateDesc(commits ...*Commit) []*Commit {
+	sorted := make([]*Commit, len(commits))
+	copy(sorted, commits)
+	sort.Slice(sorted, func(i, j int) bool {
+		return sorted[i].Committer.When.After(sorted[j].Committer.When)
+	})
+
+	return sorted
+}
+
+// indexOf returns the first position where target was found in the passed commits
+func indexOf(commits []*Commit, target *Commit) int {
+	for i, commit := range commits {
+		if target.Hash == commit.Hash {
+			return i
+		}
+	}
+
+	return -1
+}
+
+// remove returns the passed commits excluding the commit toDelete
+func remove(commits []*Commit, toDelete *Commit) []*Commit {
+	res := make([]*Commit, len(commits))
+	j := 0
+	for _, commit := range commits {
+		if commit.Hash == toDelete.Hash {
+			continue
+		}
+
+		res[j] = commit
+		j++
+	}
+
+	return res[:j]
+}
+
+// removeDuplicated removes duplicated commits from the passed slice of commits
+func removeDuplicated(commits []*Commit) []*Commit {
+	seen := make(map[plumbing.Hash]struct{}, len(commits))
+	res := make([]*Commit, len(commits))
+	j := 0
+	for _, commit := range commits {
+		if _, ok := seen[commit.Hash]; ok {
+			continue
+		}
+
+		seen[commit.Hash] = struct{}{}
+		res[j] = commit
+		j++
+	}
+
+	return res[:j]
+}
+
+// isInIndexCommitFilter returns a commitFilter that returns true
+// if the commit is in the passed index.
+func isInIndexCommitFilter(index map[plumbing.Hash]struct{}) CommitFilter {
+	return func(c *Commit) bool {
+		_, ok := index[c.Hash]
+		return ok
+	}
+}
diff --git a/plumbing/object/merge_base_test.go b/plumbing/object/merge_base_test.go
new file mode 100644
index 0000000..598539d
--- /dev/null
+++ b/plumbing/object/merge_base_test.go
@@ -0,0 +1,323 @@
+package object
+
+import (
+	"fmt"
+	"sort"
+
+	"gopkg.in/src-d/go-git.v4/plumbing"
+	"gopkg.in/src-d/go-git.v4/plumbing/cache"
+	"gopkg.in/src-d/go-git.v4/storage/filesystem"
+
+	. "gopkg.in/check.v1"
+	fixtures "gopkg.in/src-d/go-git-fixtures.v3"
+)
+
+func alphabeticSortCommits(commits []*Commit) {
+	sort.Slice(commits, func(i, j int) bool {
+		return commits[i].Hash.String() > commits[j].Hash.String()
+	})
+}
+
+/*
+
+The following tests consider this history having two root commits: V and W
+
+V---o---M----AB----A---CD1--P---C--------S-------------------Q < master
+               \         \ /            /                   /
+                \         X            GQ1---G < feature   /
+                 \       / \          /     /             /
+W---o---N----o----B---CD2---o---D----o----GQ2------------o < dev
+
+MergeBase
+----------------------------
+passed  merge-base
+ M, N               Commits with unrelated history, have no merge-base
+ A, B    AB         Regular merge-base between two commits
+ A, A    A          The merge-commit between equal commits, is the same
+ Q, N    N          The merge-commit between a commit an its ancestor, is the ancestor
+ C, D    CD1, CD2   Cross merges causes more than one merge-base
+ G, Q    GQ1, GQ2   Feature branches including merges, causes more than one merge-base
+
+Independents
+----------------------------
+candidates           result
+ A                    A           Only one commit returns it
+ A, A, A              A           Repeated commits are ignored
+ A, A, M, M, N        A, N        M is reachable from A, so it is not independent
+ S, G, P              S, G        P is reachable from S, so it is not independent
+ CD1, CD2, M, N       CD1, CD2    M and N are reachable from CD2, so they're not
+ C, G, dev, M, N      C, G, dev   M and N are reachable from G, so they're not
+ C, D, M, N           C, D        M and N are reachable from C, so they're not
+ A, A^, A, N, N^      A, N        A^ and N^ are rechable from A and N
+ A^^^, A^, A^^, A, N  A, N        A^^^, A^^ and A^ are rechable from A, so they're not
+
+IsAncestor
+----------------------------
+passed   result
+ A^^, A   true      Will be true if first is ancestor of the second
+ M, G     true      True because it will also reach G from M crossing merge commits
+ A, A     true      True if first and second are the same
+ M, N     false     Commits with unrelated history, will return false
+*/
+
+var _ = Suite(&mergeBaseSuite{})
+
+type mergeBaseSuite struct {
+	BaseObjectsSuite
+}
+
+func (s *mergeBaseSuite) SetUpSuite(c *C) {
+	s.Suite.SetUpSuite(c)
+	s.Fixture = fixtures.ByTag("merge-base").One()
+	s.Storer = filesystem.NewStorage(s.Fixture.DotGit(), cache.NewObjectLRUDefault())
+}
+
+var revisionIndex = map[string]plumbing.Hash{
+	"master":  plumbing.NewHash("dce0e0c20d701c3d260146e443d6b3b079505191"),
+	"feature": plumbing.NewHash("d1b0093698e398d596ef94d646c4db37e8d1e970"),
+	"dev":     plumbing.NewHash("25ca6c810c08482d61113fbcaaada38bb59093a8"),
+	"M":       plumbing.NewHash("bb355b64e18386dbc3af63dfd09c015c44cbd9b6"),
+	"N":       plumbing.NewHash("d64b894762ab5f09e2b155221b90c18bd0637236"),
+	"A":       plumbing.NewHash("29740cfaf0c2ee4bb532dba9e80040ca738f367c"),
+	"B":       plumbing.NewHash("2c84807970299ba98951c65fe81ebbaac01030f0"),
+	"AB":      plumbing.NewHash("31a7e081a28f149ee98ffd13ba1a6d841a5f46fd"),
+	"P":       plumbing.NewHash("ff84393134864cf9d3a9853a81bde81778bd5805"),
+	"C":       plumbing.NewHash("8b72fabdc4222c3ff965bc310ded788c601c50ed"),
+	"D":       plumbing.NewHash("14777cf3e209334592fbfd0b878f6868394db836"),
+	"CD1":     plumbing.NewHash("4709e13a3cbb300c2b8a917effda776e1b8955c7"),
+	"CD2":     plumbing.NewHash("38468e274e91e50ffb637b88a1954ab6193fe974"),
+	"S":       plumbing.NewHash("628f1a42b70380ed05734bf01b468b46206ef1ea"),
+	"G":       plumbing.NewHash("d1b0093698e398d596ef94d646c4db37e8d1e970"),
+	"Q":       plumbing.NewHash("dce0e0c20d701c3d260146e443d6b3b079505191"),
+	"GQ1":     plumbing.NewHash("ccaaa99c21dad7e9f392c36ae8cb72dc63bed458"),
+	"GQ2":     plumbing.NewHash("806824d4778e94fe7c3244e92a9cd07090c9ab54"),
+	"A^":      plumbing.NewHash("31a7e081a28f149ee98ffd13ba1a6d841a5f46fd"),
+	"A^^":     plumbing.NewHash("bb355b64e18386dbc3af63dfd09c015c44cbd9b6"),
+	"A^^^":    plumbing.NewHash("8d08dd1388b82dd354cb43918d83da86c76b0978"),
+	"N^":      plumbing.NewHash("b6e1fc8dad4f1068fb42774ec5fc65c065b2c312"),
+}
+
+func (s *mergeBaseSuite) commitsFromRevs(c *C, revs []string) ([]*Commit, error) {
+	var commits []*Commit
+	for _, rev := range revs {
+		hash, ok := revisionIndex[rev]
+		if !ok {
+			return nil, fmt.Errorf("Revision not found '%s'", rev)
+		}
+
+		commits = append(commits, s.commit(c, hash))
+	}
+
+	return commits, nil
+}
+
+// AssertMergeBase validates that the merge-base of the passed revs,
+// matches the expected result
+func (s *mergeBaseSuite) AssertMergeBase(c *C, revs, expectedRevs []string) {
+	c.Assert(revs, HasLen, 2)
+
+	commits, err := s.commitsFromRevs(c, revs)
+	c.Assert(err, IsNil)
+
+	results, err := commits[0].MergeBase(commits[1])
+	c.Assert(err, IsNil)
+
+	expected, err := s.commitsFromRevs(c, expectedRevs)
+	c.Assert(err, IsNil)
+
+	c.Assert(results, HasLen, len(expected))
+
+	alphabeticSortCommits(results)
+	alphabeticSortCommits(expected)
+	for i, commit := range results {
+		c.Assert(commit.Hash.String(), Equals, expected[i].Hash.String())
+	}
+}
+
+// AssertIndependents validates the independent commits of the passed list
+func (s *mergeBaseSuite) AssertIndependents(c *C, revs, expectedRevs []string) {
+	commits, err := s.commitsFromRevs(c, revs)
+	c.Assert(err, IsNil)
+
+	results, err := Independents(commits)
+	c.Assert(err, IsNil)
+
+	expected, err := s.commitsFromRevs(c, expectedRevs)
+	c.Assert(err, IsNil)
+
+	c.Assert(results, HasLen, len(expected))
+
+	alphabeticSortCommits(results)
+	alphabeticSortCommits(expected)
+	for i, commit := range results {
+		c.Assert(commit.Hash.String(), Equals, expected[i].Hash.String())
+	}
+}
+
+// AssertAncestor validates if the first rev is ancestor of the second one
+func (s *mergeBaseSuite) AssertAncestor(c *C, revs []string, shouldBeAncestor bool) {
+	c.Assert(revs, HasLen, 2)
+
+	commits, err := s.commitsFromRevs(c, revs)
+	c.Assert(err, IsNil)
+
+	isAncestor, err := commits[0].IsAncestor(commits[1])
+	c.Assert(err, IsNil)
+	c.Assert(isAncestor, Equals, shouldBeAncestor)
+}
+
+// TestNoAncestorsWhenNoCommonHistory validates that merge-base returns no commits
+// when there is no common history (M, N -> none)
+func (s *mergeBaseSuite) TestNoAncestorsWhenNoCommonHistory(c *C) {
+	revs := []string{"M", "N"}
+	nothing := []string{}
+	s.AssertMergeBase(c, revs, nothing)
+}
+
+// TestCommonAncestorInMergedOrphans validates that merge-base returns a common
+// ancestor in orphan branches when they where merged (A, B -> AB)
+func (s *mergeBaseSuite) TestCommonAncestorInMergedOrphans(c *C) {
+	revs := []string{"A", "B"}
+	expectedRevs := []string{"AB"}
+	s.AssertMergeBase(c, revs, expectedRevs)
+}
+
+// TestMergeBaseWithSelf validates that merge-base between equal commits, returns
+// the same commit (A, A -> A)
+func (s *mergeBaseSuite) TestMergeBaseWithSelf(c *C) {
+	revs := []string{"A", "A"}
+	expectedRevs := []string{"A"}
+	s.AssertMergeBase(c, revs, expectedRevs)
+}
+
+// TestMergeBaseWithAncestor validates that merge-base between a commit an its
+// ancestor returns the ancestor (Q, N -> N)
+func (s *mergeBaseSuite) TestMergeBaseWithAncestor(c *C) {
+	revs := []string{"Q", "N"}
+	expectedRevs := []string{"N"}
+	s.AssertMergeBase(c, revs, expectedRevs)
+}
+
+// TestDoubleCommonAncestorInCrossMerge validates that merge-base returns two
+// common ancestors when there are cross merges (C, D -> CD1, CD2)
+func (s *mergeBaseSuite) TestDoubleCommonAncestorInCrossMerge(c *C) {
+	revs := []string{"C", "D"}
+	expectedRevs := []string{"CD1", "CD2"}
+	s.AssertMergeBase(c, revs, expectedRevs)
+}
+
+// TestDoubleCommonInSubFeatureBranches validates that merge-base returns two
+// common ancestors when two branches where partially merged (G, Q -> GQ1, GQ2)
+func (s *mergeBaseSuite) TestDoubleCommonInSubFeatureBranches(c *C) {
+	revs := []string{"G", "Q"}
+	expectedRevs := []string{"GQ1", "GQ2"}
+	s.AssertMergeBase(c, revs, expectedRevs)
+}
+
+// TestIndependentOnlyOne validates that Independents for one commit returns
+// that same commit (A -> A)
+func (s *mergeBaseSuite) TestIndependentOnlyOne(c *C) {
+	revs := []string{"A"}
+	expectedRevs := []string{"A"}
+	s.AssertIndependents(c, revs, expectedRevs)
+}
+
+// TestIndependentOnlyRepeated validates that Independents for one repeated commit
+// returns that same commit (A, A, A -> A)
+func (s *mergeBaseSuite) TestIndependentOnlyRepeated(c *C) {
+	revs := []string{"A", "A", "A"}
+	expectedRevs := []string{"A"}
+	s.AssertIndependents(c, revs, expectedRevs)
+}
+
+// TestIndependentWithRepeatedAncestors validates that Independents works well
+// when there are repeated ancestors (A, A, M, M, N -> A, N)
+func (s *mergeBaseSuite) TestIndependentWithRepeatedAncestors(c *C) {
+	revs := []string{"A", "A", "M", "M", "N"}
+	expectedRevs := []string{"A", "N"}
+	s.AssertIndependents(c, revs, expectedRevs)
+}
+
+// TestIndependentBeyondShortcut validates that Independents does not stop walking
+// in all paths when one of them is known (S, G, P -> S, G)
+func (s *mergeBaseSuite) TestIndependentBeyondShortcut(c *C) {
+	revs := []string{"S", "G", "P"}
+	expectedRevs := []string{"S", "G"}
+	s.AssertIndependents(c, revs, expectedRevs)
+}
+
+// TestIndependentBeyondShortcutBis validates that Independents does not stop walking
+// in all paths when one of them is known (CD1, CD2, M, N -> CD1, CD2)
+func (s *mergeBaseSuite) TestIndependentBeyondShortcutBis(c *C) {
+	revs := []string{"CD1", "CD2", "M", "N"}
+	expectedRevs := []string{"CD1", "CD2"}
+	s.AssertIndependents(c, revs, expectedRevs)
+}
+
+// TestIndependentWithPairOfAncestors validates that Independents excluded all
+// the ancestors (C, D, M, N -> C, D)
+func (s *mergeBaseSuite) TestIndependentWithPairOfAncestors(c *C) {
+	revs := []string{"C", "D", "M", "N"}
+	expectedRevs := []string{"C", "D"}
+	s.AssertIndependents(c, revs, expectedRevs)
+}
+
+// TestIndependentAcrossCrossMerges validates that Independents works well
+// along cross merges (C, G, dev, M -> C, G, dev)
+func (s *mergeBaseSuite) TestIndependentAcrossCrossMerges(c *C) {
+	revs := []string{"C", "G", "dev", "M", "N"}
+	expectedRevs := []string{"C", "G", "dev"}
+	s.AssertIndependents(c, revs, expectedRevs)
+}
+
+// TestIndependentChangingOrderRepetition validates that Independents works well
+// when the order and repetition is tricky (A, A^, A, N, N^ -> A, N)
+func (s *mergeBaseSuite) TestIndependentChangingOrderRepetition(c *C) {
+	revs := []string{"A", "A^", "A", "N", "N^"}
+	expectedRevs := []string{"A", "N"}
+	s.AssertIndependents(c, revs, expectedRevs)
+}
+
+// TestIndependentChangingOrder validates that Independents works well
+// when the order is tricky (A^^^, A^, A^^, A, N -> A, N)
+func (s *mergeBaseSuite) TestIndependentChangingOrder(c *C) {
+	revs := []string{"A^^^", "A^", "A^^", "A", "N"}
+	expectedRevs := []string{"A", "N"}
+	s.AssertIndependents(c, revs, expectedRevs)
+}
+
+// TestAncestor validates that IsAncestor returns true if walking from first
+// commit, through its parents, it can be reached the second ( A^^, A -> true )
+func (s *mergeBaseSuite) TestAncestor(c *C) {
+	revs := []string{"A^^", "A"}
+	s.AssertAncestor(c, revs, true)
+
+	revs = []string{"A", "A^^"}
+	s.AssertAncestor(c, revs, false)
+}
+
+// TestAncestorBeyondMerges validates that IsAncestor returns true also if first can be
+// be reached from first one even crossing merge commits in between ( M, G -> true )
+func (s *mergeBaseSuite) TestAncestorBeyondMerges(c *C) {
+	revs := []string{"M", "G"}
+	s.AssertAncestor(c, revs, true)
+
+	revs = []string{"G", "M"}
+	s.AssertAncestor(c, revs, false)
+}
+
+// TestAncestorSame validates that IsAncestor returns both are the same ( A, A -> true )
+func (s *mergeBaseSuite) TestAncestorSame(c *C) {
+	revs := []string{"A", "A"}
+	s.AssertAncestor(c, revs, true)
+}
+
+// TestAncestorUnrelated validates that IsAncestor returns false when the passed commits
+// does not share any history, no matter the order used ( M, N -> false )
+func (s *mergeBaseSuite) TestAncestorUnrelated(c *C) {
+	revs := []string{"M", "N"}
+	s.AssertAncestor(c, revs, false)
+
+	revs = []string{"N", "M"}
+	s.AssertAncestor(c, revs, false)
+}