Merge pull request #588 from erizocosmico/perf/revlist-norevisit-ancestors-fixed
revlist: do not revisit ancestors as long as all branches are visited
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 @@
) ([]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 @@
}
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 @@
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 @@
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 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 @@
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 @@
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 @@
}
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"),
+ })
+}
