diff options
author | Andrew Thornton <art27@cantab.net> | 2023-10-08 15:49:51 +0100 |
---|---|---|
committer | Andrew Thornton <art27@cantab.net> | 2023-10-12 16:40:38 +0100 |
commit | 69b88d9bda44ebfe1d56a7624b956d9e20818c0e (patch) | |
tree | b6a17322552d0cdade956d3c4e0d6c14e49cf60e /plumbing/object/commitgraph/commitnode_walker_helper.go | |
parent | 623c6df4280e22f88f4aabc3c0a8ae2808d33a1b (diff) | |
download | go-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.go | 164 |
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 +} |