diff options
Diffstat (limited to 'fi-prune-empty2/prune.go')
| -rw-r--r-- | fi-prune-empty2/prune.go | 40 |
1 files changed, 27 insertions, 13 deletions
diff --git a/fi-prune-empty2/prune.go b/fi-prune-empty2/prune.go index ff0119b..e3181b2 100644 --- a/fi-prune-empty2/prune.go +++ b/fi-prune-empty2/prune.go @@ -75,8 +75,8 @@ type Pruner struct { replace map[Mark]Mark - ancestors map[Mark]map[Mark]struct{} // all ancestors, not just immediate parents - tree map[Mark]Tree + parents map[Mark]map[Mark]struct{} + tree map[Mark]Tree newhash2mark map[Hash]Mark } @@ -94,8 +94,8 @@ func NewPruner( replace: make(map[Mark]Mark), - ancestors: make(map[Mark]map[Mark]struct{}), - tree: make(map[Mark]Tree), + parents: make(map[Mark]map[Mark]struct{}), + tree: make(map[Mark]Tree), newhash2mark: make(map[Hash]Mark), } @@ -156,14 +156,13 @@ func (p *Pruner) ProcessCommit(commit Commit) (*Commit, error) { return nil, nil } - ancestors := map[Mark]struct{}{} - for _, parent := range commit.Parents { - ancestors[parent] = struct{}{} - for ancestor := range p.ancestors[parent] { - ancestors[ancestor] = struct{}{} + p.parents[commit.Mark] = func() map[Mark]struct{} { + parents := make(map[Mark]struct{}, len(commit.Parents)) + for _, parent := range commit.Parents { + parents[parent] = struct{}{} } - } - p.ancestors[commit.Mark] = ancestors + return parents + }() p.tree[commit.Mark] = commit.Tree return &commit, nil @@ -241,8 +240,23 @@ func (p *Pruner) isEmpty(commit Commit) (bool, error) { } func (p *Pruner) isAncestor(ancestor, descendant Mark) bool { - _, ret := p.ancestors[descendant][ancestor] - return ret + isDescendentMemo := make(map[Mark]bool) + var isDescendent func(desc Mark) bool + isDescendent = func(desc Mark) bool { + if ret, ok := isDescendentMemo[desc]; ok { + return ret + } + ret := false + for descParent := range p.parents[desc] { + if descParent == ancestor || isDescendent(descParent) { + ret = true + break + } + } + isDescendentMemo[desc] = ret + return ret + } + return isDescendent(descendant) } // pruneParents prunes "duplicate" parents of a commit. It is |