| 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) |
| _ = 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 |
| } |
| } |