plumbing/object: add WalkCommitHistoryPost func

Also add a test. Make both the pre-order and post-order tests not sort
commits, to actually test the order in which the commit history is
walked.

Fixes #223.

2 files changed, 59 insertions, 7 deletions

diff --git a/plumbing/object/commit_walker.go b/plumbing/object/commit_walker.go
index b986067..681ea5e 100644
--- a/plumbing/object/commit_walker.go
+++ b/plumbing/object/commit_walker.go
@@ -69,3 +69,28 @@ func (w *commitWalker) walk() error {
 
 	return w.walk()
 }
+
+// WalkCommitHistoryPost walks the commit history like WalkCommitHistory
+// but in post-order. This means that after walking a merge commit, the
+// merged commit will be walked before the base it was merged on. This
+// can be useful if you wish to see the history in chronological order.
+func WalkCommitHistoryPost(c *Commit, cb func(*Commit) error) error {
+	stack := []*Commit{c}
+	seen := make(map[plumbing.Hash]bool)
+	for len(stack) > 0 {
+		c := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+		if seen[c.Hash] {
+			continue
+		}
+		seen[c.Hash] = true
+		if err := cb(c); err != nil {
+			return err
+		}
+		c.Parents().ForEach(func(pcm *Commit) error {
+			stack = append(stack, pcm)
+			return nil
+		})
+	}
+	return nil
+}
diff --git a/plumbing/object/commit_walker_test.go b/plumbing/object/commit_walker_test.go
index 67d6695..aa54de0 100644
--- a/plumbing/object/commit_walker_test.go
+++ b/plumbing/object/commit_walker_test.go
@@ -8,26 +8,53 @@ type CommitWalkerSuite struct {
 
 var _ = Suite(&CommitWalkerSuite{})
 
-func (s *CommitWalkerSuite) TestWalkerNext(c *C) {
+func (s *CommitWalkerSuite) TestWalkHistory(c *C) {
 	commit := s.commit(c, s.Fixture.Head)
 
 	var commits []*Commit
-
 	WalkCommitHistory(commit, func(c *Commit) error {
 		commits = append(commits, c)
 		return nil
 	})
 
-	SortCommits(commits)
 	c.Assert(commits, HasLen, 8)
 
 	expected := []string{
-		"b029517f6300c2da0f4b651b8642506cd6aaf45d", "b8e471f58bcbca63b07bda20e428190409c2db47",
-		"35e85108805c84807bc66a02d91535e1e24b38b9", "a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69",
-		"1669dce138d9b841a518c64b10914d88f5e488ea", "af2d6a6954d532f8ffb47615169c8fdf9d383a1a",
-		"918c48b83bd081e863dbe1b80f8998f058cd8294", "6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+		"6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+		"918c48b83bd081e863dbe1b80f8998f058cd8294",
+		"af2d6a6954d532f8ffb47615169c8fdf9d383a1a",
+		"1669dce138d9b841a518c64b10914d88f5e488ea",
+		"35e85108805c84807bc66a02d91535e1e24b38b9",
+		"b029517f6300c2da0f4b651b8642506cd6aaf45d",
+		"a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69",
+		"b8e471f58bcbca63b07bda20e428190409c2db47",
+	}
+	for i, commit := range commits {
+		c.Assert(commit.Hash.String(), Equals, expected[i])
 	}
+}
+
+func (s *CommitWalkerSuite) TestWalkHistoryPost(c *C) {
+	commit := s.commit(c, s.Fixture.Head)
+
+	var commits []*Commit
+	WalkCommitHistoryPost(commit, func(c *Commit) error {
+		commits = append(commits, c)
+		return nil
+	})
 
+	c.Assert(commits, HasLen, 8)
+
+	expected := []string{
+		"6ecf0ef2c2dffb796033e5a02219af86ec6584e5",
+		"918c48b83bd081e863dbe1b80f8998f058cd8294",
+		"af2d6a6954d532f8ffb47615169c8fdf9d383a1a",
+		"1669dce138d9b841a518c64b10914d88f5e488ea",
+		"a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69",
+		"b8e471f58bcbca63b07bda20e428190409c2db47",
+		"b029517f6300c2da0f4b651b8642506cd6aaf45d",
+		"35e85108805c84807bc66a02d91535e1e24b38b9",
+	}
 	for i, commit := range commits {
 		c.Assert(commit.Hash.String(), Equals, expected[i])
 	}