plumbing: the commit walker can skip externally-seen commits

When the revlist is computing the set of hashes needed to transfer, it
doesn't need to walk over commits it has already processed.  So, it
can instruct the commit walker not to walk those commits by passing in
its own `seen` map.

For a 36K object repo, this brought the time for `revlist.Objects`
down from 50s to 30s.

5 files changed, 45 insertions, 15 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 {
diff --git a/remote.go b/remote.go
index 34ea7f5..5869d18 100644
--- a/remote.go
+++ b/remote.go
@@ -615,7 +615,7 @@ func isFastForward(s storer.EncodedObjectStorer, old, new plumbing.Hash) (bool,
 	}
 
 	found := false
-	iter := object.NewCommitPreorderIter(c, nil)
+	iter := object.NewCommitPreorderIter(c, nil, nil)
 	return found, iter.ForEach(func(c *object.Commit) error {
 		if c.Hash != old {
 			return nil
diff --git a/repository.go b/repository.go
index 8114740..6694517 100644
--- a/repository.go
+++ b/repository.go
@@ -720,7 +720,7 @@ func (r *Repository) Log(o *LogOptions) (object.CommitIter, error) {
 		return nil, err
 	}
 
-	return object.NewCommitPreorderIter(commit, nil), nil
+	return object.NewCommitPreorderIter(commit, nil, nil), nil
 }
 
 // Tags returns all the References from Tags. This method returns all the tag
@@ -949,7 +949,7 @@ func (r *Repository) ResolveRevision(rev plumbing.Revision) (*plumbing.Hash, err
 				commit = c
 			}
 		case revision.CaretReg:
-			history := object.NewCommitPreorderIter(commit, nil)
+			history := object.NewCommitPreorderIter(commit, nil, nil)
 
 			re := item.(revision.CaretReg).Regexp
 			negate := item.(revision.CaretReg).Negate
@@ -979,7 +979,7 @@ func (r *Repository) ResolveRevision(rev plumbing.Revision) (*plumbing.Hash, err
 
 			commit = c
 		case revision.AtDate:
-			history := object.NewCommitPreorderIter(commit, nil)
+			history := object.NewCommitPreorderIter(commit, nil, nil)
 
 			date := item.(revision.AtDate).Date