aboutsummaryrefslogtreecommitdiffstats
path: root/plumbing/object/commit_walker_bfs.go
diff options
context:
space:
mode:
authorMáximo Cuadros <mcuadros@gmail.com>2018-03-12 09:38:00 +0100
committerGitHub <noreply@github.com>2018-03-12 09:38:00 +0100
commit1d28459504251497e0ce6132a0fadd5eb44ffd22 (patch)
treedd56e4f69f58e0988cd87b5a221e2e6e88b5904c /plumbing/object/commit_walker_bfs.go
parentecda5c1512bcb19e1802d629b18872ec995e23cf (diff)
parent3b75e0c904a81069d623a3361954242c668f496d (diff)
downloadgo-git-1d28459504251497e0ce6132a0fadd5eb44ffd22.tar.gz
Merge pull request #771 from ilius/PR-log-orderv4.2.0
repository.Log: add alternatives for commit traversal order
Diffstat (limited to 'plumbing/object/commit_walker_bfs.go')
-rw-r--r--plumbing/object/commit_walker_bfs.go100
1 files changed, 100 insertions, 0 deletions
diff --git a/plumbing/object/commit_walker_bfs.go b/plumbing/object/commit_walker_bfs.go
new file mode 100644
index 0000000..aef1cf2
--- /dev/null
+++ b/plumbing/object/commit_walker_bfs.go
@@ -0,0 +1,100 @@
+package object
+
+import (
+ "io"
+
+ "gopkg.in/src-d/go-git.v4/plumbing"
+ "gopkg.in/src-d/go-git.v4/plumbing/storer"
+)
+
+type bfsCommitIterator struct {
+ seenExternal map[plumbing.Hash]bool
+ seen map[plumbing.Hash]bool
+ queue []*Commit
+}
+
+// NewCommitIterBSF returns a CommitIter that walks the commit history,
+// starting at the given commit and visiting its parents in pre-order.
+// 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
+// cannot be traversed (e.g. missing objects). Ignore allows to skip some
+// commits from being iterated.
+func NewCommitIterBSF(
+ c *Commit,
+ seenExternal map[plumbing.Hash]bool,
+ ignore []plumbing.Hash,
+) CommitIter {
+ seen := make(map[plumbing.Hash]bool)
+ for _, h := range ignore {
+ seen[h] = true
+ }
+
+ return &bfsCommitIterator{
+ seenExternal: seenExternal,
+ seen: seen,
+ queue: []*Commit{c},
+ }
+}
+
+func (w *bfsCommitIterator) appendHash(store storer.EncodedObjectStorer, h plumbing.Hash) error {
+ if w.seen[h] || w.seenExternal[h] {
+ return nil
+ }
+ c, err := GetCommit(store, h)
+ if err != nil {
+ return err
+ }
+ w.queue = append(w.queue, c)
+ return nil
+}
+
+func (w *bfsCommitIterator) Next() (*Commit, error) {
+ var c *Commit
+ for {
+ if len(w.queue) == 0 {
+ return nil, io.EOF
+ }
+ c = w.queue[0]
+ w.queue = w.queue[1:]
+
+ if w.seen[c.Hash] || w.seenExternal[c.Hash] {
+ continue
+ }
+
+ w.seen[c.Hash] = true
+
+ for _, h := range c.ParentHashes {
+ err := w.appendHash(c.s, h)
+ if err != nil {
+ return nil, nil
+ }
+ }
+
+ return c, nil
+ }
+}
+
+func (w *bfsCommitIterator) ForEach(cb func(*Commit) error) error {
+ for {
+ c, err := w.Next()
+ if err == io.EOF {
+ break
+ }
+ if err != nil {
+ return err
+ }
+
+ err = cb(c)
+ if err == storer.ErrStop {
+ break
+ }
+ if err != nil {
+ return err
+ }
+ }
+
+ return nil
+}
+
+func (w *bfsCommitIterator) Close() {}