Merge pull request #771 from ilius/PR-log-order
repository.Log: add alternatives for commit traversal order
diff --git a/options.go b/options.go
index a87b497..f0c2fd8 100644
--- a/options.go
+++ b/options.go
@@ -307,12 +307,27 @@
return nil
}
+type LogOrder int8
+
+const (
+ LogOrderDefault LogOrder = iota
+ LogOrderDFS
+ LogOrderDFSPost
+ LogOrderBSF
+ LogOrderCommitterTime
+)
+
// LogOptions describes how a log action should be performed.
type LogOptions struct {
// When the From option is set the log will only contain commits
// reachable from it. If this option is not set, HEAD will be used as
// the default From.
From plumbing.Hash
+
+ // The default traversal algorithm is Depth-first search
+ // set Order=LogOrderCommitterTime for ordering by committer time (more compatible with `git log`)
+ // set Order=LogOrderBSF for Breadth-first search
+ Order LogOrder
}
var (
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() {}
diff --git a/plumbing/object/commit_walker_ctime.go b/plumbing/object/commit_walker_ctime.go
new file mode 100644
index 0000000..0191614
--- /dev/null
+++ b/plumbing/object/commit_walker_ctime.go
@@ -0,0 +1,103 @@
+package object
+
+import (
+ "io"
+
+ "github.com/emirpasic/gods/trees/binaryheap"
+
+ "gopkg.in/src-d/go-git.v4/plumbing"
+ "gopkg.in/src-d/go-git.v4/plumbing/storer"
+)
+
+type commitIteratorByCTime struct {
+ seenExternal map[plumbing.Hash]bool
+ seen map[plumbing.Hash]bool
+ heap *binaryheap.Heap
+}
+
+// NewCommitIterCTime returns a CommitIter 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`
+// 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 NewCommitIterCTime(
+ c *Commit,
+ seenExternal map[plumbing.Hash]bool,
+ ignore []plumbing.Hash,
+) CommitIter {
+ seen := make(map[plumbing.Hash]bool)
+ for _, h := range ignore {
+ seen[h] = true
+ }
+
+ heap := binaryheap.NewWith(func(a, b interface{}) int {
+ if a.(*Commit).Committer.When.Before(b.(*Commit).Committer.When) {
+ return 1
+ }
+ return -1
+ })
+ heap.Push(c)
+
+ return &commitIteratorByCTime{
+ seenExternal: seenExternal,
+ seen: seen,
+ heap: heap,
+ }
+}
+
+func (w *commitIteratorByCTime) Next() (*Commit, error) {
+ var c *Commit
+ for {
+ cIn, ok := w.heap.Pop()
+ if !ok {
+ return nil, io.EOF
+ }
+ c = cIn.(*Commit)
+
+ if w.seen[c.Hash] || w.seenExternal[c.Hash] {
+ continue
+ }
+
+ w.seen[c.Hash] = true
+
+ for _, h := range c.ParentHashes {
+ if w.seen[h] || w.seenExternal[h] {
+ continue
+ }
+ pc, err := GetCommit(c.s, h)
+ if err != nil {
+ return nil, err
+ }
+ w.heap.Push(pc)
+ }
+
+ return c, nil
+ }
+}
+
+func (w *commitIteratorByCTime) 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 *commitIteratorByCTime) Close() {}
diff --git a/plumbing/object/commit_walker_test.go b/plumbing/object/commit_walker_test.go
index a27104e..9b0a260 100644
--- a/plumbing/object/commit_walker_test.go
+++ b/plumbing/object/commit_walker_test.go
@@ -132,3 +132,99 @@
c.Assert(commit.Hash.String(), Equals, expected[i])
}
}
+
+func (s *CommitWalkerSuite) TestCommitCTimeIterator(c *C) {
+ commit := s.commit(c, s.Fixture.Head)
+
+ var commits []*Commit
+ NewCommitIterCTime(commit, nil, nil).ForEach(func(c *Commit) error {
+ commits = append(commits, c)
+ return nil
+ })
+
+ c.Assert(commits, HasLen, 8)
+
+ expected := []string{
+ "6ecf0ef2c2dffb796033e5a02219af86ec6584e5", // 2015-04-05T23:30:47+02:00
+ "918c48b83bd081e863dbe1b80f8998f058cd8294", // 2015-03-31T13:56:18+02:00
+ "af2d6a6954d532f8ffb47615169c8fdf9d383a1a", // 2015-03-31T13:51:51+02:00
+ "1669dce138d9b841a518c64b10914d88f5e488ea", // 2015-03-31T13:48:14+02:00
+ "a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69", // 2015-03-31T13:47:14+02:00
+ "35e85108805c84807bc66a02d91535e1e24b38b9", // 2015-03-31T13:46:24+02:00
+ "b8e471f58bcbca63b07bda20e428190409c2db47", // 2015-03-31T13:44:52+02:00
+ "b029517f6300c2da0f4b651b8642506cd6aaf45d", // 2015-03-31T13:42:21+02:00
+ }
+ for i, commit := range commits {
+ c.Assert(commit.Hash.String(), Equals, expected[i])
+ }
+}
+
+func (s *CommitWalkerSuite) TestCommitCTimeIteratorWithIgnore(c *C) {
+ commit := s.commit(c, s.Fixture.Head)
+
+ var commits []*Commit
+ NewCommitIterCTime(commit, nil, []plumbing.Hash{
+ plumbing.NewHash("af2d6a6954d532f8ffb47615169c8fdf9d383a1a"),
+ }).ForEach(func(c *Commit) error {
+ commits = append(commits, c)
+ return nil
+ })
+
+ c.Assert(commits, HasLen, 2)
+
+ expected := []string{
+ "6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+ "918c48b83bd081e863dbe1b80f8998f058cd8294",
+ }
+ for i, commit := range commits {
+ c.Assert(commit.Hash.String(), Equals, expected[i])
+ }
+}
+
+func (s *CommitWalkerSuite) TestCommitBSFIterator(c *C) {
+ commit := s.commit(c, s.Fixture.Head)
+
+ var commits []*Commit
+ NewCommitIterBSF(commit, nil, nil).ForEach(func(c *Commit) error {
+ commits = append(commits, c)
+ return nil
+ })
+
+ c.Assert(commits, HasLen, 8)
+
+ expected := []string{
+ "6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+ "918c48b83bd081e863dbe1b80f8998f058cd8294",
+ "af2d6a6954d532f8ffb47615169c8fdf9d383a1a",
+ "1669dce138d9b841a518c64b10914d88f5e488ea",
+ "35e85108805c84807bc66a02d91535e1e24b38b9",
+ "a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69",
+ "b029517f6300c2da0f4b651b8642506cd6aaf45d",
+ "b8e471f58bcbca63b07bda20e428190409c2db47",
+ }
+ for i, commit := range commits {
+ c.Assert(commit.Hash.String(), Equals, expected[i])
+ }
+}
+
+func (s *CommitWalkerSuite) TestCommitBSFIteratorWithIgnore(c *C) {
+ commit := s.commit(c, s.Fixture.Head)
+
+ var commits []*Commit
+ NewCommitIterBSF(commit, nil, []plumbing.Hash{
+ plumbing.NewHash("af2d6a6954d532f8ffb47615169c8fdf9d383a1a"),
+ }).ForEach(func(c *Commit) error {
+ commits = append(commits, c)
+ return nil
+ })
+
+ c.Assert(commits, HasLen, 2)
+
+ expected := []string{
+ "6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+ "918c48b83bd081e863dbe1b80f8998f058cd8294",
+ }
+ for i, commit := range commits {
+ c.Assert(commit.Hash.String(), Equals, expected[i])
+ }
+}
diff --git a/repository.go b/repository.go
index 24d025d..98558d9 100644
--- a/repository.go
+++ b/repository.go
@@ -728,7 +728,19 @@
return nil, err
}
- return object.NewCommitPreorderIter(commit, nil, nil), nil
+ switch o.Order {
+ case LogOrderDefault:
+ return object.NewCommitPreorderIter(commit, nil, nil), nil
+ case LogOrderDFS:
+ return object.NewCommitPreorderIter(commit, nil, nil), nil
+ case LogOrderDFSPost:
+ return object.NewCommitPostorderIter(commit, nil), nil
+ case LogOrderBSF:
+ return object.NewCommitIterBSF(commit, nil, nil), nil
+ case LogOrderCommitterTime:
+ return object.NewCommitIterCTime(commit, nil, nil), nil
+ }
+ return nil, fmt.Errorf("invalid Order=%v", o.Order)
}
// Tags returns all the References from Tags. This method returns all the tag
diff --git a/repository_test.go b/repository_test.go
index ef37e37..1ad1607 100644
--- a/repository_test.go
+++ b/repository_test.go
@@ -870,7 +870,7 @@
c.Assert(err, IsNil)
cIter, err := r.Log(&LogOptions{
- plumbing.NewHash("b8e471f58bcbca63b07bda20e428190409c2db47"),
+ From: plumbing.NewHash("b8e471f58bcbca63b07bda20e428190409c2db47"),
})
c.Assert(err, IsNil)
@@ -930,7 +930,7 @@
c.Assert(err, IsNil)
_, err = r.Log(&LogOptions{
- plumbing.NewHash("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"),
+ From: plumbing.NewHash("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"),
})
c.Assert(err, NotNil)
}
