1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
package commitgraph
import (
"math"
"github.com/go-git/go-git/v5/plumbing"
"github.com/emirpasic/gods/trees/binaryheap"
)
// commitNodeStackable represents a common interface between heaps and stacks
type commitNodeStackable interface {
Push(c CommitNode)
Pop() (CommitNode, bool)
Peek() (CommitNode, bool)
Size() int
}
// commitNodeLifo is a stack implementation using an underlying slice
type commitNodeLifo struct {
l []CommitNode
}
// Push pushes a new CommitNode to the stack
func (l *commitNodeLifo) Push(c CommitNode) {
l.l = append(l.l, c)
}
// Pop pops the most recently added CommitNode from the stack
func (l *commitNodeLifo) Pop() (CommitNode, bool) {
if len(l.l) == 0 {
return nil, false
}
c := l.l[len(l.l)-1]
l.l = l.l[:len(l.l)-1]
return c, true
}
// Peek returns the most recently added CommitNode from the stack without removing it
func (l *commitNodeLifo) Peek() (CommitNode, bool) {
if len(l.l) == 0 {
return nil, false
}
return l.l[len(l.l)-1], true
}
// Size returns the number of CommitNodes in the stack
func (l *commitNodeLifo) Size() int {
return len(l.l)
}
// commitNodeHeap is a stack implementation using an underlying binary heap
type commitNodeHeap struct {
*binaryheap.Heap
}
// Push pushes a new CommitNode to the heap
func (h *commitNodeHeap) Push(c CommitNode) {
h.Heap.Push(c)
}
// Pop removes top element on heap and returns it, or nil if heap is empty.
// Second return parameter is true, unless the heap was empty and there was nothing to pop.
func (h *commitNodeHeap) Pop() (CommitNode, bool) {
c, ok := h.Heap.Pop()
if !ok {
return nil, false
}
return c.(CommitNode), true
}
// Peek returns top element on the heap without removing it, or nil if heap is empty.
// Second return parameter is true, unless the heap was empty and there was nothing to peek.
func (h *commitNodeHeap) Peek() (CommitNode, bool) {
c, ok := h.Heap.Peek()
if !ok {
return nil, false
}
return c.(CommitNode), true
}
// Size returns number of elements within the heap.
func (h *commitNodeHeap) Size() int {
return h.Heap.Size()
}
// generationAndDateOrderComparator compares two CommitNode objects based on their generation and commit time.
// If the left CommitNode object is in a higher generation or is newer than the right one, it returns a -1.
// If the left CommitNode object is in a lower generation or is older than the right one, it returns a 1.
// If the two CommitNode objects have the same commit time and generation, it returns 0.
func generationAndDateOrderComparator(left, right interface{}) int {
leftCommit := left.(CommitNode)
rightCommit := right.(CommitNode)
// if GenerationV2 is MaxUint64, then the node is not in the graph
if leftCommit.GenerationV2() == math.MaxUint64 {
if rightCommit.GenerationV2() == math.MaxUint64 {
switch {
case rightCommit.CommitTime().Before(leftCommit.CommitTime()):
return -1
case leftCommit.CommitTime().Before(rightCommit.CommitTime()):
return 1
}
return 0
}
// left is not in the graph, but right is, so it is newer than the right
return -1
}
if rightCommit.GenerationV2() == math.MaxInt64 {
// the right is not in the graph, therefore the left is before the right
return 1
}
if leftCommit.GenerationV2() == 0 || rightCommit.GenerationV2() == 0 {
// We need to assess generation and date
if leftCommit.Generation() < rightCommit.Generation() {
return 1
}
if leftCommit.Generation() > rightCommit.Generation() {
return -1
}
switch {
case rightCommit.CommitTime().Before(leftCommit.CommitTime()):
return -1
case leftCommit.CommitTime().Before(rightCommit.CommitTime()):
return 1
}
return 0
}
if leftCommit.GenerationV2() < rightCommit.GenerationV2() {
return 1
}
if leftCommit.GenerationV2() > rightCommit.GenerationV2() {
return -1
}
return 0
}
// composeIgnores composes the ignore list with the provided seenExternal list
func composeIgnores(ignore []plumbing.Hash, seenExternal map[plumbing.Hash]bool) map[plumbing.Hash]struct{} {
if len(ignore) == 0 {
seen := make(map[plumbing.Hash]struct{})
for h, ext := range seenExternal {
if ext {
seen[h] = struct{}{}
}
}
return seen
}
seen := make(map[plumbing.Hash]struct{})
for _, h := range ignore {
seen[h] = struct{}{}
}
for h, ext := range seenExternal {
if ext {
seen[h] = struct{}{}
}
}
return seen
}
|
