From f62852b584d4625276e870ec9e148c37ba5fe6ca Mon Sep 17 00:00:00 2001 From: David Pordomingo Date: Mon, 25 Mar 2019 06:54:39 +0100 Subject: Create merge-base feature Signed-off-by: David Pordomingo --- plumbing/object/commit_walker_bfs_filtered.go | 176 +++++++++++ plumbing/object/commit_walker_bfs_filtered_test.go | 262 +++++++++++++++++ plumbing/object/merge_base.go | 210 ++++++++++++++ plumbing/object/merge_base_test.go | 323 +++++++++++++++++++++ 4 files changed, 971 insertions(+) create mode 100644 plumbing/object/commit_walker_bfs_filtered.go create mode 100644 plumbing/object/commit_walker_bfs_filtered_test.go create mode 100644 plumbing/object/merge_base.go create mode 100644 plumbing/object/merge_base_test.go (limited to 'plumbing/object') 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) +} -- cgit