aboutsummaryrefslogtreecommitdiffstats
path: root/plumbing/object/commitgraph/commitnode_walker_helper.go
diff options
context:
space:
mode:
authorAndrew Thornton <art27@cantab.net>2023-10-08 15:49:51 +0100
committerAndrew Thornton <art27@cantab.net>2023-10-12 16:40:38 +0100
commit69b88d9bda44ebfe1d56a7624b956d9e20818c0e (patch)
treeb6a17322552d0cdade956d3c4e0d6c14e49cf60e /plumbing/object/commitgraph/commitnode_walker_helper.go
parent623c6df4280e22f88f4aabc3c0a8ae2808d33a1b (diff)
downloadgo-git-69b88d9bda44ebfe1d56a7624b956d9e20818c0e.tar.gz
plumbing: commitgraph, Add generation v2 support
This PR adds in support for generation v2 support and a couple of new walkers to match --date-order etc options on log. This PR also fixes a bug in the chain code and adds more tests. Signed-off-by: Andrew Thornton <art27@cantab.net>
Diffstat (limited to 'plumbing/object/commitgraph/commitnode_walker_helper.go')
-rw-r--r--plumbing/object/commitgraph/commitnode_walker_helper.go164
1 files changed, 164 insertions, 0 deletions
diff --git a/plumbing/object/commitgraph/commitnode_walker_helper.go b/plumbing/object/commitgraph/commitnode_walker_helper.go
new file mode 100644
index 0000000..c54f6ca
--- /dev/null
+++ b/plumbing/object/commitgraph/commitnode_walker_helper.go
@@ -0,0 +1,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
+}