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

plumbing: commitgraph, Add generation v2 support

9 files changed, 634 insertions, 1 deletions

diff --git a/plumbing/object/commitgraph/commitnode.go b/plumbing/object/commitgraph/commitnode.go
index d92c906..47227d4 100644
--- a/plumbing/object/commitgraph/commitnode.go
+++ b/plumbing/object/commitgraph/commitnode.go
@@ -29,6 +29,10 @@ type CommitNode interface {
 	// Generation returns the generation of the commit for reachability analysis.
 	// Objects with newer generation are not reachable from objects of older generation.
 	Generation() uint64
+	// GenerationV2 stores the corrected commit date for the commits
+	// It combines the contents of the GDA2 and GDO2 sections of the commit-graph
+	// with the commit time portion of the CDAT section.
+	GenerationV2() uint64
 	// Commit returns the full commit object from the node
 	Commit() (*object.Commit, error)
 }
diff --git a/plumbing/object/commitgraph/commitnode_graph.go b/plumbing/object/commitgraph/commitnode_graph.go
index 252b518..0f51e3b 100644
--- a/plumbing/object/commitgraph/commitnode_graph.go
+++ b/plumbing/object/commitgraph/commitnode_graph.go
@@ -120,6 +120,13 @@ func (c *graphCommitNode) Generation() uint64 {
 	return c.commitData.Generation
 }
 
+func (c *graphCommitNode) GenerationV2() uint64 {
+	// If the commit-graph file was generated with older Git version that
+	// set the generation to zero for every commit the generation assumption
+	// is still valid. It is just less useful.
+	return c.commitData.GenerationV2
+}
+
 func (c *graphCommitNode) Commit() (*object.Commit, error) {
 	return object.GetCommit(c.gci.s, c.hash)
 }
diff --git a/plumbing/object/commitgraph/commitnode_object.go b/plumbing/object/commitgraph/commitnode_object.go
index 1bd37e3..7256bed 100644
--- a/plumbing/object/commitgraph/commitnode_object.go
+++ b/plumbing/object/commitgraph/commitnode_object.go
@@ -85,6 +85,13 @@ func (c *objectCommitNode) Generation() uint64 {
 	return math.MaxUint64
 }
 
+func (c *objectCommitNode) GenerationV2() uint64 {
+	// Commit nodes representing objects outside of the commit graph can never
+	// be reached by objects from the commit-graph thus we return the highest
+	// possible value.
+	return math.MaxUint64
+}
+
 func (c *objectCommitNode) Commit() (*object.Commit, error) {
 	return c.commit, nil
 }
diff --git a/plumbing/object/commitgraph/commitnode_walker_author_order.go b/plumbing/object/commitgraph/commitnode_walker_author_order.go
new file mode 100644
index 0000000..f5b23cc
--- /dev/null
+++ b/plumbing/object/commitgraph/commitnode_walker_author_order.go
@@ -0,0 +1,61 @@
+package commitgraph
+
+import (
+	"github.com/go-git/go-git/v5/plumbing"
+
+	"github.com/emirpasic/gods/trees/binaryheap"
+)
+
+// NewCommitNodeIterAuthorDateOrder returns a CommitNodeIter that walks the commit history,
+// starting at the given commit and visiting its parents in Author Time order but with the
+// constraint that no parent is emitted before its children are emitted.
+//
+// This matches `git log --author-order`
+//
+// This ordering requires that commit objects need to be loaded into memory - thus this
+// ordering is likely to be slower than other orderings.
+func NewCommitNodeIterAuthorDateOrder(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(func(left, right interface{}) int {
+		leftCommit, err := left.(CommitNode).Commit()
+		if err != nil {
+			return -1
+		}
+		rightCommit, err := right.(CommitNode).Commit()
+		if err != nil {
+			return -1
+		}
+
+		switch {
+		case rightCommit.Author.When.Before(leftCommit.Author.When):
+			return -1
+		case leftCommit.Author.When.Before(rightCommit.Author.When):
+			return 1
+		}
+		return 0
+	})}
+	visitHeap.Push(c)
+
+	return &commitNodeIteratorTopological{
+		exploreStack: exploreHeap,
+		visitStack:   visitHeap,
+		inCounts:     inCounts,
+		ignore:       seen,
+	}
+}
diff --git a/plumbing/object/commitgraph/commitnode_walker_ctime.go b/plumbing/object/commitgraph/commitnode_walker_ctime.go
index c26873c..3ab9e6e 100644
--- a/plumbing/object/commitgraph/commitnode_walker_ctime.go
+++ b/plumbing/object/commitgraph/commitnode_walker_ctime.go
@@ -17,7 +17,8 @@ type commitNodeIteratorByCTime struct {
 
 // NewCommitNodeIterCTime returns a CommitNodeIter that walks the commit history,
 // starting at the given commit and visiting its parents while preserving Committer Time order.
-// this appears to be the closest order to `git log`
+// this is close in order to `git log` but does not guarantee topological order and will
+// order things incorrectly occasionally.
 // The given callback will be called for each visited commit. Each commit will
 // be visited only once. If the callback returns an error, walking will stop
 // and will return the error. Other errors might be returned if the history
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,
+	}
+}
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
+}
diff --git a/plumbing/object/commitgraph/commitnode_walker_test.go b/plumbing/object/commitgraph/commitnode_walker_test.go
new file mode 100644
index 0000000..1e09c0b
--- /dev/null
+++ b/plumbing/object/commitgraph/commitnode_walker_test.go
@@ -0,0 +1,187 @@
+package commitgraph
+
+import (
+	"strings"
+
+	"github.com/go-git/go-git/v5/plumbing"
+	commitgraph "github.com/go-git/go-git/v5/plumbing/format/commitgraph/v2"
+
+	fixtures "github.com/go-git/go-git-fixtures/v4"
+	. "gopkg.in/check.v1"
+)
+
+func (s *CommitNodeSuite) TestCommitNodeIter(c *C) {
+	f := fixtures.ByTag("commit-graph-chain-2").One()
+
+	storer := unpackRepository(f)
+
+	index, err := commitgraph.OpenChainOrFileIndex(storer.Filesystem())
+	c.Assert(err, IsNil)
+
+	nodeIndex := NewGraphCommitNodeIndex(index, storer)
+
+	head, err := nodeIndex.Get(plumbing.NewHash("ec6f456c0e8c7058a29611429965aa05c190b54b"))
+	c.Assert(err, IsNil)
+
+	testTopoOrder(c, head)
+	testDateOrder(c, head)
+	testAuthorDateOrder(c, head)
+}
+
+func testTopoOrder(c *C, head CommitNode) {
+	iter := NewCommitNodeIterTopoOrder(
+		head,
+		nil,
+		nil,
+	)
+
+	var commits []string
+	iter.ForEach(func(c CommitNode) error {
+		commits = append(commits, c.ID().String())
+		return nil
+	})
+	c.Assert(commits, DeepEquals, strings.Split(`ec6f456c0e8c7058a29611429965aa05c190b54b
+d82f291cde9987322c8a0c81a325e1ba6159684c
+3048d280d2d5b258d9e582a226ff4bbed34fd5c9
+27aa8cdd2431068606741a589383c02c149ea625
+fa058d42fa3bc53f39108a56dad67157169b2191
+6c629843a1750a27c9af01ed2985f362f619c47a
+d10a0e7c1f340a6cfc14540a5f8c508ce7e2eabf
+d0a18ccd8eea3bdabc76d6dc5420af1ea30aae9f
+cf2874632223220e0445abf0a7806dc772c0b37a
+758ac33217f092bfcded4ad4774954ac054c9609
+214e1dca024fb6da5ed65564d2de734df5dc2127
+70923099e61fa33f0bc5256d2f938fa44c4df10e
+bcaa1ac5644b16f1febb72f31e204720b7bb8934
+e1d8866ffa78fa16d2f39b0ba5344a7269ee5371
+2275fa7d0c75d20103f90b0e1616937d5a9fc5e6
+bdd9a92789d4a86b20a8d3df462df373f41acf23
+b359f11ea09e642695edcd114b463da4395b10c1
+6f43e8933ba3c04072d5d104acc6118aac3e52ee
+ccafe8bd5f9dbfb8b98b0da03ced29608dcfdeec
+939814f341fdd5d35e81a3845a33c4fedb19d2d2
+5f5ad88bf2babe506f927d64d2b7a1e1493dc2ae
+a2014124ca3b3f9ff28fbab0a83ce3c71bf4622e
+77906b653c3eb8a1cd5bd7254e161c00c6086d83
+465cba710284204f9851854587c2887c247222db
+b9471b13256703d3f5eb88b280b4a16ce325ec1b
+62925030859646daeeaf5a4d386a0c41e00dda8a
+5f56aea0ca8b74215a5b982bca32236e1e28c76b
+23148841baa5dbce48f6adcb7ddf83dcd97debb3
+c336d16298a017486c4164c40f8acb28afe64e84
+31eae7b619d166c366bf5df4991f04ba8cebea0a
+d2a38b4a5965d529566566640519d03d2bd10f6c
+b977a025ca21e3b5ca123d8093bd7917694f6da7
+35b585759cbf29f8ec428ef89da20705d59f99ec
+c2bbf9fe8009b22d0f390f3c8c3f13937067590f
+fc9f0643b21cfe571046e27e0c4565f3a1ee96c8
+c088fd6a7e1a38e9d5a9815265cb575bb08d08ff
+5fddbeb678bd2c36c5e5c891ab8f2b143ced5baf
+5d7303c49ac984a9fec60523f2d5297682e16646`, "\n"))
+}
+
+func testDateOrder(c *C, head CommitNode) {
+	iter := NewCommitNodeIterDateOrder(
+		head,
+		nil,
+		nil,
+	)
+
+	var commits []string
+	iter.ForEach(func(c CommitNode) error {
+		commits = append(commits, c.ID().String())
+		return nil
+	})
+
+	c.Assert(commits, DeepEquals, strings.Split(`ec6f456c0e8c7058a29611429965aa05c190b54b
+3048d280d2d5b258d9e582a226ff4bbed34fd5c9
+d82f291cde9987322c8a0c81a325e1ba6159684c
+27aa8cdd2431068606741a589383c02c149ea625
+fa058d42fa3bc53f39108a56dad67157169b2191
+d0a18ccd8eea3bdabc76d6dc5420af1ea30aae9f
+6c629843a1750a27c9af01ed2985f362f619c47a
+cf2874632223220e0445abf0a7806dc772c0b37a
+d10a0e7c1f340a6cfc14540a5f8c508ce7e2eabf
+758ac33217f092bfcded4ad4774954ac054c9609
+214e1dca024fb6da5ed65564d2de734df5dc2127
+70923099e61fa33f0bc5256d2f938fa44c4df10e
+bcaa1ac5644b16f1febb72f31e204720b7bb8934
+e1d8866ffa78fa16d2f39b0ba5344a7269ee5371
+2275fa7d0c75d20103f90b0e1616937d5a9fc5e6
+bdd9a92789d4a86b20a8d3df462df373f41acf23
+b359f11ea09e642695edcd114b463da4395b10c1
+6f43e8933ba3c04072d5d104acc6118aac3e52ee
+ccafe8bd5f9dbfb8b98b0da03ced29608dcfdeec
+939814f341fdd5d35e81a3845a33c4fedb19d2d2
+5f5ad88bf2babe506f927d64d2b7a1e1493dc2ae
+a2014124ca3b3f9ff28fbab0a83ce3c71bf4622e
+77906b653c3eb8a1cd5bd7254e161c00c6086d83
+465cba710284204f9851854587c2887c247222db
+b9471b13256703d3f5eb88b280b4a16ce325ec1b
+62925030859646daeeaf5a4d386a0c41e00dda8a
+5f56aea0ca8b74215a5b982bca32236e1e28c76b
+23148841baa5dbce48f6adcb7ddf83dcd97debb3
+c336d16298a017486c4164c40f8acb28afe64e84
+31eae7b619d166c366bf5df4991f04ba8cebea0a
+b977a025ca21e3b5ca123d8093bd7917694f6da7
+d2a38b4a5965d529566566640519d03d2bd10f6c
+35b585759cbf29f8ec428ef89da20705d59f99ec
+c2bbf9fe8009b22d0f390f3c8c3f13937067590f
+fc9f0643b21cfe571046e27e0c4565f3a1ee96c8
+c088fd6a7e1a38e9d5a9815265cb575bb08d08ff
+5fddbeb678bd2c36c5e5c891ab8f2b143ced5baf
+5d7303c49ac984a9fec60523f2d5297682e16646`, "\n"))
+}
+
+func testAuthorDateOrder(c *C, head CommitNode) {
+	iter := NewCommitNodeIterAuthorDateOrder(
+		head,
+		nil,
+		nil,
+	)
+
+	var commits []string
+	iter.ForEach(func(c CommitNode) error {
+		commits = append(commits, c.ID().String())
+		return nil
+	})
+
+	c.Assert(commits, DeepEquals, strings.Split(`ec6f456c0e8c7058a29611429965aa05c190b54b
+3048d280d2d5b258d9e582a226ff4bbed34fd5c9
+d82f291cde9987322c8a0c81a325e1ba6159684c
+27aa8cdd2431068606741a589383c02c149ea625
+fa058d42fa3bc53f39108a56dad67157169b2191
+d0a18ccd8eea3bdabc76d6dc5420af1ea30aae9f
+6c629843a1750a27c9af01ed2985f362f619c47a
+cf2874632223220e0445abf0a7806dc772c0b37a
+d10a0e7c1f340a6cfc14540a5f8c508ce7e2eabf
+758ac33217f092bfcded4ad4774954ac054c9609
+214e1dca024fb6da5ed65564d2de734df5dc2127
+70923099e61fa33f0bc5256d2f938fa44c4df10e
+bcaa1ac5644b16f1febb72f31e204720b7bb8934
+e1d8866ffa78fa16d2f39b0ba5344a7269ee5371
+2275fa7d0c75d20103f90b0e1616937d5a9fc5e6
+bdd9a92789d4a86b20a8d3df462df373f41acf23
+b359f11ea09e642695edcd114b463da4395b10c1
+6f43e8933ba3c04072d5d104acc6118aac3e52ee
+ccafe8bd5f9dbfb8b98b0da03ced29608dcfdeec
+939814f341fdd5d35e81a3845a33c4fedb19d2d2
+5f5ad88bf2babe506f927d64d2b7a1e1493dc2ae
+a2014124ca3b3f9ff28fbab0a83ce3c71bf4622e
+77906b653c3eb8a1cd5bd7254e161c00c6086d83
+465cba710284204f9851854587c2887c247222db
+b9471b13256703d3f5eb88b280b4a16ce325ec1b
+5f56aea0ca8b74215a5b982bca32236e1e28c76b
+62925030859646daeeaf5a4d386a0c41e00dda8a
+23148841baa5dbce48f6adcb7ddf83dcd97debb3
+c336d16298a017486c4164c40f8acb28afe64e84
+31eae7b619d166c366bf5df4991f04ba8cebea0a
+b977a025ca21e3b5ca123d8093bd7917694f6da7
+d2a38b4a5965d529566566640519d03d2bd10f6c
+35b585759cbf29f8ec428ef89da20705d59f99ec
+c2bbf9fe8009b22d0f390f3c8c3f13937067590f
+fc9f0643b21cfe571046e27e0c4565f3a1ee96c8
+c088fd6a7e1a38e9d5a9815265cb575bb08d08ff
+5fddbeb678bd2c36c5e5c891ab8f2b143ced5baf
+5d7303c49ac984a9fec60523f2d5297682e16646`, "\n"))
+}
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() {
+}