aboutsummaryrefslogtreecommitdiffstats
path: root/plumbing/object/merge_base.go
diff options
context:
space:
mode:
Diffstat (limited to 'plumbing/object/merge_base.go')
-rw-r--r--plumbing/object/merge_base.go210
1 files changed, 210 insertions, 0 deletions
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
+ }
+}