1package object 2 3import ( 4 "fmt" 5 "sort" 6 7 "github.com/go-git/go-git/v5/plumbing" 8 "github.com/go-git/go-git/v5/plumbing/storer" 9) 10 11// errIsReachable is thrown when first commit is an ancestor of the second 12var errIsReachable = fmt.Errorf("first is reachable from second") 13 14// MergeBase mimics the behavior of `git merge-base actual other`, returning the 15// best common ancestor between the actual and the passed one. 16// The best common ancestors can not be reached from other common ancestors. 17func (c *Commit) MergeBase(other *Commit) ([]*Commit, error) { 18 // use sortedByCommitDateDesc strategy 19 sorted := sortByCommitDateDesc(c, other) 20 newer := sorted[0] 21 older := sorted[1] 22 23 newerHistory, err := ancestorsIndex(older, newer) 24 if err == errIsReachable { 25 return []*Commit{older}, nil 26 } 27 28 if err != nil { 29 return nil, err 30 } 31 32 var res []*Commit 33 inNewerHistory := isInIndexCommitFilter(newerHistory) 34 resIter := NewFilterCommitIter(older, &inNewerHistory, &inNewerHistory) 35 _ = resIter.ForEach(func(commit *Commit) error { 36 res = append(res, commit) 37 return nil 38 }) 39 40 return Independents(res) 41} 42 43// IsAncestor returns true if the actual commit is ancestor of the passed one. 44// It returns an error if the history is not transversable 45// It mimics the behavior of `git merge --is-ancestor actual other` 46func (c *Commit) IsAncestor(other *Commit) (bool, error) { 47 found := false 48 iter := NewCommitPreorderIter(other, nil, nil) 49 err := iter.ForEach(func(comm *Commit) error { 50 if comm.Hash != c.Hash { 51 return nil 52 } 53 54 found = true 55 return storer.ErrStop 56 }) 57 58 return found, err 59} 60 61// ancestorsIndex returns a map with the ancestors of the starting commit if the 62// excluded one is not one of them. It returns errIsReachable if the excluded commit 63// is ancestor of the starting, or another error if the history is not traversable. 64func ancestorsIndex(excluded, starting *Commit) (map[plumbing.Hash]struct{}, error) { 65 if excluded.Hash.String() == starting.Hash.String() { 66 return nil, errIsReachable 67 } 68 69 startingHistory := map[plumbing.Hash]struct{}{} 70 startingIter := NewCommitIterBSF(starting, nil, nil) 71 err := startingIter.ForEach(func(commit *Commit) error { 72 if commit.Hash == excluded.Hash { 73 return errIsReachable 74 } 75 76 startingHistory[commit.Hash] = struct{}{} 77 return nil 78 }) 79 80 if err != nil { 81 return nil, err 82 } 83 84 return startingHistory, nil 85} 86 87// Independents returns a subset of the passed commits, that are not reachable the others 88// It mimics the behavior of `git merge-base --independent commit...`. 89func Independents(commits []*Commit) ([]*Commit, error) { 90 // use sortedByCommitDateDesc strategy 91 candidates := sortByCommitDateDesc(commits...) 92 candidates = removeDuplicated(candidates) 93 94 seen := map[plumbing.Hash]struct{}{} 95 var isLimit CommitFilter = func(commit *Commit) bool { 96 _, ok := seen[commit.Hash] 97 return ok 98 } 99 100 if len(candidates) < 2 { 101 return candidates, nil 102 } 103 104 pos := 0 105 for { 106 from := candidates[pos] 107 others := remove(candidates, from) 108 fromHistoryIter := NewFilterCommitIter(from, nil, &isLimit) 109 err := fromHistoryIter.ForEach(func(fromAncestor *Commit) error { 110 for _, other := range others { 111 if fromAncestor.Hash == other.Hash { 112 candidates = remove(candidates, other) 113 others = remove(others, other) 114 } 115 } 116 117 if len(candidates) == 1 { 118 return storer.ErrStop 119 } 120 121 seen[fromAncestor.Hash] = struct{}{} 122 return nil 123 }) 124 125 if err != nil { 126 return nil, err 127 } 128 129 nextPos := indexOf(candidates, from) + 1 130 if nextPos >= len(candidates) { 131 break 132 } 133 134 pos = nextPos 135 } 136 137 return candidates, nil 138} 139 140// sortByCommitDateDesc returns the passed commits, sorted by `committer.When desc` 141// 142// Following this strategy, it is tried to reduce the time needed when walking 143// the history from one commit to reach the others. It is assumed that ancestors 144// use to be committed before its descendant; 145// That way `Independents(A^, A)` will be processed as being `Independents(A, A^)`; 146// so starting by `A` it will be reached `A^` way sooner than walking from `A^` 147// to the initial commit, and then from `A` to `A^`. 148func sortByCommitDateDesc(commits ...*Commit) []*Commit { 149 sorted := make([]*Commit, len(commits)) 150 copy(sorted, commits) 151 sort.Slice(sorted, func(i, j int) bool { 152 return sorted[i].Committer.When.After(sorted[j].Committer.When) 153 }) 154 155 return sorted 156} 157 158// indexOf returns the first position where target was found in the passed commits 159func indexOf(commits []*Commit, target *Commit) int { 160 for i, commit := range commits { 161 if target.Hash == commit.Hash { 162 return i 163 } 164 } 165 166 return -1 167} 168 169// remove returns the passed commits excluding the commit toDelete 170func remove(commits []*Commit, toDelete *Commit) []*Commit { 171 res := make([]*Commit, len(commits)) 172 j := 0 173 for _, commit := range commits { 174 if commit.Hash == toDelete.Hash { 175 continue 176 } 177 178 res[j] = commit 179 j++ 180 } 181 182 return res[:j] 183} 184 185// removeDuplicated removes duplicated commits from the passed slice of commits 186func removeDuplicated(commits []*Commit) []*Commit { 187 seen := make(map[plumbing.Hash]struct{}, len(commits)) 188 res := make([]*Commit, len(commits)) 189 j := 0 190 for _, commit := range commits { 191 if _, ok := seen[commit.Hash]; ok { 192 continue 193 } 194 195 seen[commit.Hash] = struct{}{} 196 res[j] = commit 197 j++ 198 } 199 200 return res[:j] 201} 202 203// isInIndexCommitFilter returns a commitFilter that returns true 204// if the commit is in the passed index. 205func isInIndexCommitFilter(index map[plumbing.Hash]struct{}) CommitFilter { 206 return func(c *Commit) bool { 207 _, ok := index[c.Hash] 208 return ok 209 } 210} 211