Mercurial > evolve
changeset 2087:0c2371542687
depth: update depth to code to reuse ancestors depth
Computing the depth of all N revs is no longer 'O(N**2)'
| author | Pierre-Yves David <pierre-yves.david@ens-lyon.org> |
|---|---|
| date | Sat, 11 Mar 2017 10:26:30 -0800 |
| parents | 28241509ff6f |
| children | 9f7ce656bfdf |
| files | hgext3rd/evolve/obsdiscovery.py hgext3rd/evolve/utility.py |
| diffstat | 2 files changed, 22 insertions(+), 3 deletions(-) [+] |
line wrap: on
line diff
--- a/hgext3rd/evolve/obsdiscovery.py Sat Mar 11 09:08:20 2017 -0800 +++ b/hgext3rd/evolve/obsdiscovery.py Sat Mar 11 10:26:30 2017 -0800 @@ -485,6 +485,9 @@ n = repo.changelog.node s = node.short revs = scmutil.revrange(repo, opts['rev']) + # prewarm depth cache + for r in repo.revs("::%ld", revs): + utility.depth(repo, r) toproceed = [_range(repo, r, 0, ) for r in revs] ranges = set(toproceed) while toproceed: @@ -548,7 +551,7 @@ @util.propertycache def _revs(self): r = _stablesort(self._repo, [self.head])[self.index:] - assert len(r) == len(self), (self.head, self.index) + assert len(r) == len(self), (self.head, self.index, len(r), len(self)) return r def _slicesat(self, globalindex):
--- a/hgext3rd/evolve/utility.py Sat Mar 11 09:08:20 2017 -0800 +++ b/hgext3rd/evolve/utility.py Sat Mar 11 10:26:30 2017 -0800 @@ -32,7 +32,23 @@ elif p2 == node.nullrev: revdepth = depth(repo, p1) + 1 else: - # XXX we should just find the common ancestors - revdepth = len(list(cl.ancestors([rev], inclusive=True))) + ancs = cl.commonancestorsheads(cl.node(p1), cl.node(p2)) + depth_p1 = depth(repo, p1) + depth_p2 = depth(repo, p2) + if not ancs: + revdepth = depth_p1 + depth_p2 + 1 + elif len(ancs) == 1: + anc = cl.rev(ancs[0]) + revdepth = depth_anc = depth(repo, anc) + revdepth += depth_p1 - depth_anc + revdepth += depth_p2 - depth_anc + revdepth += 1 + else: + # multiple ancestors, we pick the highest and search all missing bits + anc = max(cl.rev(a) for a in ancs) + revdepth = depth(repo, anc) + revdepth += len(repo.revs('only(%d, %d)', rev, anc)) _depthcache[n] = revdepth + # actual_depth = len(list(cl.ancestors([rev], inclusive=True))) + # assert revdepth == actual_depth, (rev, revdepth, actual_depth) return revdepth