aboutsummaryrefslogtreecommitdiffstats
path: root/plumbing/revlist/revlist.go
diff options
context:
space:
mode:
authorMiguel Molina <miguel@erizocosmi.co>2017-09-12 10:04:46 +0200
committerMiguel Molina <miguel@erizocosmi.co>2017-09-12 13:37:18 +0200
commit5bb64f6220bd3c3c985efbc148e3f7253b3d9d71 (patch)
tree96bb055b1ffd5cea41af7c0207399c44e2e246d8 /plumbing/revlist/revlist.go
parent8cb0215282c329d299d7d1d195abae4704981ba6 (diff)
downloadgo-git-5bb64f6220bd3c3c985efbc148e3f7253b3d9d71.tar.gz
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>
Diffstat (limited to 'plumbing/revlist/revlist.go')
-rw-r--r--plumbing/revlist/revlist.go30
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,