1 files changed, 49 insertions, 12 deletions

diff --git a/plumbing/revlist/revlist.go b/plumbing/revlist/revlist.go
index f56cf28..0a9d1e8 100644
--- a/plumbing/revlist/revlist.go
+++ b/plumbing/revlist/revlist.go
@@ -35,9 +35,9 @@ func objects(
 	ignore []plumbing.Hash,
 	allowMissingObjects bool,
 ) ([]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] {
@@ -47,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
 			}
@@ -64,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 {
@@ -83,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:
@@ -106,13 +107,36 @@ 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 {
+	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 {
+			break
+		}
+
+		if err != nil {
+			return err
+		}
+
+		if pending[commit.Hash] {
+			delete(pending, commit.Hash)
+		}
+
+		addPendingParents(pending, visited, commit)
+
+		if visited[commit.Hash] && len(pending) == 0 {
+			break
+		}
 
-	i := object.NewCommitPreorderIter(commit, ignore)
-	return i.ForEach(func(commit *object.Commit) error {
 		if seen[commit.Hash] {
-			return nil
+			continue
 		}
 
 		cb(commit.Hash)
@@ -122,22 +146,35 @@ func reachableObjects(
 			return err
 		}
 
-		return iterateCommitTrees(seen, tree, cb)
-	})
+		if err := iterateCommitTrees(seen, tree, cb); err != nil {
+			return err
+		}
+	}
+
+	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,
 	tree *object.Tree,
-	cb func(h plumbing.Hash)) error {
+	cb func(h plumbing.Hash),
+) error {
 	if seen[tree.Hash] {
 		return nil
 	}
 
 	cb(tree.Hash)
 
-	treeWalker := object.NewTreeWalker(tree, true)
+	treeWalker := object.NewTreeWalker(tree, true, seen)
 
 	for {
 		_, e, err := treeWalker.Next()