diff options
Diffstat (limited to 'plumbing/object/commitgraph')
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() { +} |