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>

1 files changed, 41 insertions, 0 deletions

diff --git a/plumbing/object/commitgraph/commitnode_walker_date_order.go b/plumbing/object/commitgraph/commitnode_walker_date_order.go
new file mode 100644
index 0000000..659a4fa
--- /dev/null
+++ b/plumbing/object/commitgraph/commitnode_walker_date_order.go
@@ -0,0 +1,41 @@
+package commitgraph
+
+import (
+	"github.com/go-git/go-git/v5/plumbing"
+
+	"github.com/emirpasic/gods/trees/binaryheap"
+)
+
+// NewCommitNodeIterDateOrder returns a CommitNodeIter that walks the commit history,
+// starting at the given commit and visiting its parents in Committer Time and Generation order,
+// but with the  constraint that no parent is emitted before its children are emitted.
+//
+// This matches `git log --date-order`
+func NewCommitNodeIterDateOrder(c CommitNode,
+	seenExternal map[plumbing.Hash]bool,
+	ignore []plumbing.Hash,
+) CommitNodeIter {
+	seen := make(map[plumbing.Hash]struct{})
+	for _, h := range ignore {
+		seen[h] = struct{}{}
+	}
+	for h, ext := range seenExternal {
+		if ext {
+			seen[h] = struct{}{}
+		}
+	}
+	inCounts := make(map[plumbing.Hash]int)
+
+	exploreHeap := &commitNodeHeap{binaryheap.NewWith(generationAndDateOrderComparator)}
+	exploreHeap.Push(c)
+
+	visitHeap := &commitNodeHeap{binaryheap.NewWith(generationAndDateOrderComparator)}
+	visitHeap.Push(c)
+
+	return &commitNodeIteratorTopological{
+		exploreStack: exploreHeap,
+		visitStack:   visitHeap,
+		inCounts:     inCounts,
+		ignore:       seen,
+	}
+}