Merge pull request #586 from keybase/strib/commit-preorder-seen-gh-master

plumbing: the commit walker can skip externally-seen commits

3 files changed, 41 insertions, 11 deletions

diff --git a/plumbing/object/commit_walker.go b/plumbing/object/commit_walker.go
index 797c17a..40ad258 100644
--- a/plumbing/object/commit_walker.go
+++ b/plumbing/object/commit_walker.go
@@ -8,9 +8,10 @@ import (
 )
 
 type commitPreIterator struct {
-	seen  map[plumbing.Hash]bool
-	stack []CommitIter
-	start *Commit
+	seenExternal map[plumbing.Hash]bool
+	seen         map[plumbing.Hash]bool
+	stack        []CommitIter
+	start        *Commit
 }
 
 // NewCommitPreorderIter returns a CommitIter that walks the commit history,
@@ -20,16 +21,21 @@ type commitPreIterator struct {
 // 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 NewCommitPreorderIter(c *Commit, ignore []plumbing.Hash) CommitIter {
+func NewCommitPreorderIter(
+	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 &commitPreIterator{
-		seen:  seen,
-		stack: make([]CommitIter, 0),
-		start: c,
+		seenExternal: seenExternal,
+		seen:         seen,
+		stack:        make([]CommitIter, 0),
+		start:        c,
 	}
 }
 
@@ -57,7 +63,7 @@ func (w *commitPreIterator) Next() (*Commit, error) {
 			}
 		}
 
-		if w.seen[c.Hash] {
+		if w.seen[c.Hash] || w.seenExternal[c.Hash] {
 			continue
 		}
 
diff --git a/plumbing/object/commit_walker_test.go b/plumbing/object/commit_walker_test.go
index 48b504d..a27104e 100644
--- a/plumbing/object/commit_walker_test.go
+++ b/plumbing/object/commit_walker_test.go
@@ -16,7 +16,7 @@ func (s *CommitWalkerSuite) TestCommitPreIterator(c *C) {
 	commit := s.commit(c, s.Fixture.Head)
 
 	var commits []*Commit
-	NewCommitPreorderIter(commit, nil).ForEach(func(c *Commit) error {
+	NewCommitPreorderIter(commit, nil, nil).ForEach(func(c *Commit) error {
 		commits = append(commits, c)
 		return nil
 	})
@@ -42,7 +42,7 @@ func (s *CommitWalkerSuite) TestCommitPreIteratorWithIgnore(c *C) {
 	commit := s.commit(c, s.Fixture.Head)
 
 	var commits []*Commit
-	NewCommitPreorderIter(commit, []plumbing.Hash{
+	NewCommitPreorderIter(commit, nil, []plumbing.Hash{
 		plumbing.NewHash("af2d6a6954d532f8ffb47615169c8fdf9d383a1a"),
 	}).ForEach(func(c *Commit) error {
 		commits = append(commits, c)
@@ -60,6 +60,30 @@ func (s *CommitWalkerSuite) TestCommitPreIteratorWithIgnore(c *C) {
 	}
 }
 
+func (s *CommitWalkerSuite) TestCommitPreIteratorWithSeenExternal(c *C) {
+	commit := s.commit(c, s.Fixture.Head)
+
+	var commits []*Commit
+	seenExternal := map[plumbing.Hash]bool{
+		plumbing.NewHash("af2d6a6954d532f8ffb47615169c8fdf9d383a1a"): true,
+	}
+	NewCommitPreorderIter(commit, seenExternal, nil).
+		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) TestCommitPostIterator(c *C) {
 	commit := s.commit(c, s.Fixture.Head)
 
diff --git a/plumbing/revlist/revlist.go b/plumbing/revlist/revlist.go
index 10a5813..009fc93 100644
--- a/plumbing/revlist/revlist.go
+++ b/plumbing/revlist/revlist.go
@@ -108,7 +108,7 @@ func reachableObjects(
 	ignore []plumbing.Hash,
 	cb func(h plumbing.Hash),
 ) error {
-	i := object.NewCommitPreorderIter(commit, ignore)
+	i := object.NewCommitPreorderIter(commit, seen, ignore)
 	for {
 		commit, err := i.Next()
 		if err == io.EOF {