revlist: do not visit again already visited parents
Signed-off-by: Miguel Molina <miguel@erizocosmi.co>
diff --git a/plumbing/revlist/revlist.go b/plumbing/revlist/revlist.go
index 5b2ff99..3071584 100644
--- a/plumbing/revlist/revlist.go
+++ b/plumbing/revlist/revlist.go
@@ -35,9 +35,9 @@
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 @@
}
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 @@
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 @@
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:
@@ -103,34 +104,60 @@
// objects from the specified commit. To avoid to iterate over seen commits,
// if a commit hash is into the 'seen' set, we will not iterate all his trees
// and blobs objects.
+// We assume all commits have the same parents, unless a commit has no parents.
+// So when we've visited a commit before, we can stop iterating commits, as we've
+// already processed all its ancestors before as well. `visited` keeps track of
+// all the commits that have been visited that had parents.
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, ignore)
- return i.ForEach(func(commit *object.Commit) error {
+ for {
+ commit, err := i.Next()
+ if err == io.EOF {
+ break
+ }
+
+ if err != nil {
+ return err
+ }
+
+ if visited[commit.Hash] {
+ break
+ }
+
if seen[commit.Hash] {
- return nil
+ continue
}
cb(commit.Hash)
+ if commit.NumParents() > 0 {
+ visited[commit.Hash] = true
+ }
tree, err := commit.Tree()
if err != nil {
return err
}
- return iterateCommitTrees(seen, tree, cb)
- })
+ if err := iterateCommitTrees(seen, tree, cb); err != nil {
+ return err
+ }
+ }
+
+ return nil
}
// 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
}
