revlist: do not revisit ancestors as long as all branches are visited

This change is the fixed version of the previous performance improvement
that was reverted due to some bogus logic.
Now it's fixed and only stops the iteration if and only if all of the
branches we've come across have been visited, being a branch a parent
commit of a commit we've visited.

Signed-off-by: Miguel Molina <miguel@erizocosmi.co>

2 files changed, 84 insertions, 3 deletions

diff --git a/plumbing/revlist/revlist.go b/plumbing/revlist/revlist.go
index 009fc93..0a9d1e8 100644
--- a/plumbing/revlist/revlist.go
+++ b/plumbing/revlist/revlist.go
@@ -37,6 +37,7 @@ func objects(
 ) ([]plumbing.Hash, error) {
 	seen := hashListToSet(ignore)
 	result := make(map[plumbing.Hash]bool)
+	visited := make(map[plumbing.Hash]bool)
 
 	walkerFunc := func(h plumbing.Hash) {
 		if !seen[h] {
@@ -46,7 +47,7 @@ func objects(
 	}
 
 	for _, h := range objects {
-		if err := processObject(s, h, seen, ignore, walkerFunc); err != nil {
+		if err := processObject(s, h, seen, visited, ignore, walkerFunc); err != nil {
 			if allowMissingObjects && err == plumbing.ErrObjectNotFound {
 				continue
 			}
@@ -63,6 +64,7 @@ func processObject(
 	s storer.EncodedObjectStorer,
 	h plumbing.Hash,
 	seen map[plumbing.Hash]bool,
+	visited map[plumbing.Hash]bool,
 	ignore []plumbing.Hash,
 	walkerFunc func(h plumbing.Hash),
 ) error {
@@ -82,12 +84,12 @@ func processObject(
 
 	switch do := do.(type) {
 	case *object.Commit:
-		return reachableObjects(do, seen, ignore, walkerFunc)
+		return reachableObjects(do, seen, visited, ignore, walkerFunc)
 	case *object.Tree:
 		return iterateCommitTrees(seen, do, walkerFunc)
 	case *object.Tag:
 		walkerFunc(do.Hash)
-		return processObject(s, do.Target, seen, ignore, walkerFunc)
+		return processObject(s, do.Target, seen, visited, ignore, walkerFunc)
 	case *object.Blob:
 		walkerFunc(do.Hash)
 	default:
@@ -105,10 +107,14 @@ func processObject(
 func reachableObjects(
 	commit *object.Commit,
 	seen map[plumbing.Hash]bool,
+	visited map[plumbing.Hash]bool,
 	ignore []plumbing.Hash,
 	cb func(h plumbing.Hash),
 ) error {
 	i := object.NewCommitPreorderIter(commit, seen, ignore)
+	pending := make(map[plumbing.Hash]bool)
+	addPendingParents(pending, visited, commit)
+
 	for {
 		commit, err := i.Next()
 		if err == io.EOF {
@@ -119,6 +125,16 @@ func reachableObjects(
 			return err
 		}
 
+		if pending[commit.Hash] {
+			delete(pending, commit.Hash)
+		}
+
+		addPendingParents(pending, visited, commit)
+
+		if visited[commit.Hash] && len(pending) == 0 {
+			break
+		}
+
 		if seen[commit.Hash] {
 			continue
 		}
@@ -138,6 +154,14 @@ func reachableObjects(
 	return nil
 }
 
+func addPendingParents(pending, visited map[plumbing.Hash]bool, commit *object.Commit) {
+	for _, p := range commit.ParentHashes {
+		if !visited[p] {
+			pending[p] = true
+		}
+	}
+}
+
 // iterateCommitTrees iterate all reachable trees from the given commit
 func iterateCommitTrees(
 	seen map[plumbing.Hash]bool,
diff --git a/plumbing/revlist/revlist_test.go b/plumbing/revlist/revlist_test.go
index dd1e8c1..643e3eb 100644
--- a/plumbing/revlist/revlist_test.go
+++ b/plumbing/revlist/revlist_test.go
@@ -217,3 +217,60 @@ func (s *RevListSuite) TestRevListObjectsNewBranch(c *C) {
 	}
 	c.Assert(len(remoteHist), Equals, len(revList))
 }
+
+// This tests will ensure that a5b8b09 and b8e471f will be visited even if
+// 35e8510 has already been visited and will not stop iterating until they
+// have been as well.
+//
+// * af2d6a6 some json
+// *   1669dce Merge branch 'master'
+// |\
+// | *   a5b8b09 Merge pull request #1
+// | |\
+// | | * b8e471f Creating changelog
+// | |/
+// * | 35e8510 binary file
+// |/
+// * b029517 Initial commit
+func (s *RevListSuite) TestReachableObjectsNoRevisit(c *C) {
+	obj, err := s.Storer.EncodedObject(plumbing.CommitObject, plumbing.NewHash("af2d6a6954d532f8ffb47615169c8fdf9d383a1a"))
+	c.Assert(err, IsNil)
+
+	do, err := object.DecodeObject(s.Storer, obj)
+	c.Assert(err, IsNil)
+
+	commit, ok := do.(*object.Commit)
+	c.Assert(ok, Equals, true)
+
+	var visited []plumbing.Hash
+	err = reachableObjects(
+		commit,
+		map[plumbing.Hash]bool{
+			plumbing.NewHash("35e85108805c84807bc66a02d91535e1e24b38b9"): true,
+		},
+		map[plumbing.Hash]bool{
+			plumbing.NewHash("35e85108805c84807bc66a02d91535e1e24b38b9"): true,
+		},
+		nil,
+		func(h plumbing.Hash) {
+			obj, err := s.Storer.EncodedObject(plumbing.AnyObject, h)
+			c.Assert(err, IsNil)
+
+			do, err := object.DecodeObject(s.Storer, obj)
+			c.Assert(err, IsNil)
+
+			if _, ok := do.(*object.Commit); ok {
+				visited = append(visited, h)
+			}
+		},
+	)
+	c.Assert(err, IsNil)
+
+	c.Assert(visited, DeepEquals, []plumbing.Hash{
+		plumbing.NewHash("af2d6a6954d532f8ffb47615169c8fdf9d383a1a"),
+		plumbing.NewHash("1669dce138d9b841a518c64b10914d88f5e488ea"),
+		plumbing.NewHash("a5b8b09e2f8fcb0bb99d3ccb0958157b40890d69"),
+		plumbing.NewHash("b029517f6300c2da0f4b651b8642506cd6aaf45d"),
+		plumbing.NewHash("b8e471f58bcbca63b07bda20e428190409c2db47"),
+	})
+}