Merge pull request #771 from ilius/PR-log-orderv4.2.0

repository.Log: add alternatives for commit traversal order

6 files changed, 329 insertions, 3 deletions

diff --git a/options.go b/options.go
index a87b497..f0c2fd8 100644
--- a/options.go
+++ b/options.go
@@ -307,12 +307,27 @@ func (o *ResetOptions) Validate(r *Repository) error {
 	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 @@ func (s *CommitWalkerSuite) TestCommitPostIteratorWithIgnore(c *C) {
 		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 @@ func (r *Repository) Log(o *LogOptions) (object.CommitIter, error) {
 		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 @@ func (s *RepositorySuite) TestLog(c *C) {
 	c.Assert(err, IsNil)
 
 	cIter, err := r.Log(&LogOptions{
-		plumbing.NewHash("b8e471f58bcbca63b07bda20e428190409c2db47"),
+		From: plumbing.NewHash("b8e471f58bcbca63b07bda20e428190409c2db47"),
 	})
 
 	c.Assert(err, IsNil)
@@ -930,7 +930,7 @@ func (s *RepositorySuite) TestLogError(c *C) {
 	c.Assert(err, IsNil)
 
 	_, err = r.Log(&LogOptions{
-		plumbing.NewHash("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"),
+		From: plumbing.NewHash("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"),
 	})
 	c.Assert(err, NotNil)
 }