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