Fast implementation of Git in pure Go
codeberg.org/lindenii/furgit
git
go
1package commitquery
2
3import "slices"
4
5// removeRedundant removes redundant merge-base candidates.
6func removeRedundant(query *query, candidates []nodeIndex) ([]nodeIndex, error) {
7 for _, idx := range candidates {
8 if query.effectiveGeneration(idx) != generationInfinity {
9 return removeRedundantWithGen(query, candidates), nil
10 }
11 }
12
13 return removeRedundantNoGen(query, candidates)
14}
15
16// removeRedundantNoGen removes redundant candidates without generation data.
17func removeRedundantNoGen(query *query, candidates []nodeIndex) ([]nodeIndex, error) {
18 redundant := make([]bool, len(candidates))
19 work := make([]nodeIndex, 0, len(candidates)-1)
20 filledIndex := make([]int, 0, len(candidates)-1)
21
22 for i, candidate := range candidates {
23 if redundant[i] {
24 continue
25 }
26
27 work = work[:0]
28 filledIndex = filledIndex[:0]
29
30 minGeneration := query.effectiveGeneration(candidate)
31
32 for j, other := range candidates {
33 if i == j || redundant[j] {
34 continue
35 }
36
37 work = append(work, other)
38 filledIndex = append(filledIndex, j)
39
40 otherGeneration := query.effectiveGeneration(other)
41 if otherGeneration < minGeneration {
42 minGeneration = otherGeneration
43 }
44 }
45
46 err := query.paintDownToCommon(candidate, work, minGeneration)
47 if err != nil {
48 return nil, err
49 }
50
51 if query.hasAnyMarks(candidate, markRight) {
52 redundant[i] = true
53 }
54
55 for j, other := range work {
56 if query.hasAnyMarks(other, markLeft) {
57 redundant[filledIndex[j]] = true
58 }
59 }
60
61 query.clearTouchedMarks(allMarks)
62 }
63
64 out := make([]nodeIndex, 0, len(candidates))
65 for i, idx := range candidates {
66 if !redundant[i] {
67 out = append(out, idx)
68 }
69 }
70
71 return out, nil
72}
73
74// removeRedundantWithGen removes redundant candidates using generation data.
75func removeRedundantWithGen(query *query, candidates []nodeIndex) []nodeIndex {
76 sorted := append([]nodeIndex(nil), candidates...)
77 slices.SortFunc(sorted, query.compareByGeneration())
78
79 minGeneration := query.effectiveGeneration(sorted[0])
80 minGenPos := 0
81 countStillIndependent := len(candidates)
82
83 query.beginMarkPhase()
84
85 walkStart := make([]nodeIndex, 0, len(candidates)*2)
86
87 for _, idx := range candidates {
88 query.setMarks(idx, markResult)
89
90 for _, parent := range query.parents(idx) {
91 if query.hasAnyMarks(parent, markStale) {
92 continue
93 }
94
95 query.setMarks(parent, markStale)
96 walkStart = append(walkStart, parent)
97 }
98 }
99
100 slices.SortFunc(walkStart, query.compareByGeneration())
101
102 for _, idx := range walkStart {
103 query.clearMarks(idx, markStale)
104 }
105
106 for i := len(walkStart) - 1; i >= 0 && countStillIndependent > 1; i-- {
107 stack := []nodeIndex{walkStart[i]}
108 query.setMarks(walkStart[i], markStale)
109
110 for len(stack) > 0 {
111 top := stack[len(stack)-1]
112
113 if query.hasAnyMarks(top, markResult) {
114 query.clearMarks(top, markResult)
115
116 countStillIndependent--
117 if countStillIndependent <= 1 {
118 break
119 }
120
121 if top == sorted[minGenPos] {
122 for minGenPos < len(sorted)-1 && query.hasAnyMarks(sorted[minGenPos], markStale) {
123 minGenPos++
124 }
125
126 minGeneration = query.effectiveGeneration(sorted[minGenPos])
127 }
128 }
129
130 if query.effectiveGeneration(top) < minGeneration {
131 stack = stack[:len(stack)-1]
132
133 continue
134 }
135
136 pushed := false
137
138 for _, parent := range query.parents(top) {
139 if query.hasAnyMarks(parent, markStale) {
140 continue
141 }
142
143 query.setMarks(parent, markStale)
144 stack = append(stack, parent)
145 pushed = true
146
147 break
148 }
149
150 if !pushed {
151 stack = stack[:len(stack)-1]
152 }
153 }
154 }
155
156 out := make([]nodeIndex, 0, len(candidates))
157 for _, idx := range candidates {
158 if !query.hasAnyMarks(idx, markStale) {
159 out = append(out, idx)
160 }
161 }
162
163 query.clearTouchedMarks(markStale | markResult)
164
165 return out
166}