Merge pull request #869 from zeripath/graph-generation-2v5.10.0

plumbing: commitgraph, Add generation v2 support

1 files changed, 161 insertions, 0 deletions

diff --git a/plumbing/object/commitgraph/commitnode_walker_topo_order.go b/plumbing/object/commitgraph/commitnode_walker_topo_order.go
new file mode 100644
index 0000000..29f4bb7
--- /dev/null
+++ b/plumbing/object/commitgraph/commitnode_walker_topo_order.go
@@ -0,0 +1,161 @@
+package commitgraph
+
+import (
+	"io"
+
+	"github.com/go-git/go-git/v5/plumbing"
+	"github.com/go-git/go-git/v5/plumbing/storer"
+
+	"github.com/emirpasic/gods/trees/binaryheap"
+)
+
+type commitNodeIteratorTopological struct {
+	exploreStack commitNodeStackable
+	visitStack   commitNodeStackable
+	inCounts     map[plumbing.Hash]int
+
+	ignore map[plumbing.Hash]struct{}
+}
+
+// NewCommitNodeIterTopoOrder returns a CommitNodeIter that walks the commit history,
+// starting at the given commit and visiting its parents in a topological order but
+// with the constraint that no parent is emitted before its children are emitted.
+//
+// This matches `git log --topo-order`
+func NewCommitNodeIterTopoOrder(c CommitNode,
+	seenExternal map[plumbing.Hash]bool,
+	ignore []plumbing.Hash,
+) CommitNodeIter {
+	seen := composeIgnores(ignore, seenExternal)
+	inCounts := make(map[plumbing.Hash]int)
+
+	heap := &commitNodeHeap{binaryheap.NewWith(generationAndDateOrderComparator)}
+	heap.Push(c)
+
+	lifo := &commitNodeLifo{make([]CommitNode, 0, 8)}
+	lifo.Push(c)
+
+	return &commitNodeIteratorTopological{
+		exploreStack: heap,
+		visitStack:   lifo,
+		inCounts:     inCounts,
+		ignore:       seen,
+	}
+}
+
+func (iter *commitNodeIteratorTopological) Next() (CommitNode, error) {
+	var next CommitNode
+	for {
+		var ok bool
+		next, ok = iter.visitStack.Pop()
+		if !ok {
+			return nil, io.EOF
+		}
+
+		if iter.inCounts[next.ID()] == 0 {
+			break
+		}
+	}
+
+	minimumLevel, generationV2 := next.GenerationV2(), true
+	if minimumLevel == 0 {
+		minimumLevel, generationV2 = next.Generation(), false
+	}
+
+	parents := make([]CommitNode, 0, len(next.ParentHashes()))
+	for i := range next.ParentHashes() {
+		pc, err := next.ParentNode(i)
+		if err != nil {
+			return nil, err
+		}
+
+		parents = append(parents, pc)
+
+		if generationV2 {
+			if pc.GenerationV2() < minimumLevel {
+				minimumLevel = pc.GenerationV2()
+			}
+			continue
+		}
+
+		if pc.Generation() < minimumLevel {
+			minimumLevel = pc.Generation()
+		}
+	}
+
+	// EXPLORE
+	for {
+		toExplore, ok := iter.exploreStack.Peek()
+		if !ok {
+			break
+		}
+
+		if toExplore.ID() != next.ID() && iter.exploreStack.Size() == 1 {
+			break
+		}
+		if generationV2 {
+			if toExplore.GenerationV2() < minimumLevel {
+				break
+			}
+		} else {
+			if toExplore.Generation() < minimumLevel {
+				break
+			}
+		}
+
+		iter.exploreStack.Pop()
+		for i, h := range toExplore.ParentHashes() {
+			if _, has := iter.ignore[h]; has {
+				continue
+			}
+			iter.inCounts[h]++
+
+			if iter.inCounts[h] == 1 {
+				pc, err := toExplore.ParentNode(i)
+				if err != nil {
+					return nil, err
+				}
+				iter.exploreStack.Push(pc)
+			}
+		}
+	}
+
+	// VISIT
+	for i, h := range next.ParentHashes() {
+		if _, has := iter.ignore[h]; has {
+			continue
+		}
+		iter.inCounts[h]--
+
+		if iter.inCounts[h] == 0 {
+			iter.visitStack.Push(parents[i])
+		}
+	}
+	delete(iter.inCounts, next.ID())
+
+	return next, nil
+}
+
+func (iter *commitNodeIteratorTopological) ForEach(cb func(CommitNode) error) error {
+	for {
+		obj, err := iter.Next()
+		if err != nil {
+			if err == io.EOF {
+				return nil
+			}
+
+			return err
+		}
+
+		if err := cb(obj); err != nil {
+			if err == storer.ErrStop {
+				return nil
+			}
+
+			return err
+		}
+	}
+}
+
+func (iter *commitNodeIteratorTopological) Close() {
+}