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>

1 files changed, 27 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,