aboutsummaryrefslogtreecommitdiffstats
path: root/plumbing/object
diff options
context:
space:
mode:
Diffstat (limited to 'plumbing/object')
-rw-r--r--plumbing/object/commitgraph/commitnode.go4
-rw-r--r--plumbing/object/commitgraph/commitnode_graph.go7
-rw-r--r--plumbing/object/commitgraph/commitnode_object.go7
-rw-r--r--plumbing/object/commitgraph/commitnode_walker_author_order.go61
-rw-r--r--plumbing/object/commitgraph/commitnode_walker_ctime.go3
-rw-r--r--plumbing/object/commitgraph/commitnode_walker_date_order.go41
-rw-r--r--plumbing/object/commitgraph/commitnode_walker_helper.go164
-rw-r--r--plumbing/object/commitgraph/commitnode_walker_test.go187
-rw-r--r--plumbing/object/commitgraph/commitnode_walker_topo_order.go161
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() {
+}