Mercurial > evolve
changeset 2125:e0a25339ff17
stablerange: move 'depth' inside a new 'stablerange' module
The stablerange used for discovery requires significant amount of code. There is
algorithme, cache, cache persistence, etc. So we create a dedicated module for
it.
The function is directly moved into a rich class handling cache (for now in
memory) because we know we will need it.
| author | Pierre-Yves David <pierre-yves.david@ens-lyon.org> |
|---|---|
| date | Sat, 18 Mar 2017 22:48:26 +0100 |
| parents | 6665aad2d41b |
| children | 839e96521c5a |
| files | hgext3rd/evolve/obsdiscovery.py hgext3rd/evolve/stablerange.py hgext3rd/evolve/utility.py |
| diffstat | 3 files changed, 113 insertions(+), 39 deletions(-) [+] |
line wrap: on
line diff
--- a/hgext3rd/evolve/obsdiscovery.py Wed Mar 22 03:15:58 2017 +0100 +++ b/hgext3rd/evolve/obsdiscovery.py Sat Mar 18 22:48:26 2017 +0100 @@ -50,12 +50,14 @@ from . import ( exthelper, utility, + stablerange, ) _pack = struct.pack _unpack = struct.unpack eh = exthelper.exthelper() +eh.merge(stablerange.eh) obsexcmsg = utility.obsexcmsg ########################################## @@ -494,7 +496,7 @@ revs = scmutil.revrange(repo, opts['rev']) # prewarm depth cache for r in repo.revs("::%ld", revs): - utility.depth(repo, r) + repo.stablerange.depthrev(repo, r) toproceed = [_range(repo, r, 0, ) for r in revs] ranges = set(toproceed) while toproceed: @@ -553,7 +555,7 @@ @util.propertycache def depth(self): - return utility.depth(self._repo, self.head) + return self._repo.stablerange.depthrev(self._repo, self.head) @util.propertycache def _revs(self): @@ -570,7 +572,7 @@ bottom = self._revs[:localindex] top = _range(self._repo, self.head, globalindex, self._revs[localindex:]) # - toprootdepth = utility.depth(self._repo, top._revs[0]) + toprootdepth = self._repo.stablerange.depthrev(self._repo, top._revs[0]) if toprootdepth + len(top) == self.depth + 1: bheads = [bottom[-1]] else: @@ -583,7 +585,7 @@ # assert 1 == len(self._repo.revs('roots(%ld)', top._revs)) if len(bheads) == 1: newhead = bottom[-1] - bottomdepth = utility.depth(self._repo, newhead) + bottomdepth = self._repo.stablerange.depthrev(self._repo, newhead) newstart = bottomdepth - len(bottom) result.append(_range(self._repo, newhead, newstart, bottom)) else: @@ -592,7 +594,7 @@ for h in bheads: subset = cl.ancestors([h], inclusive=True) hrevs = [r for r in bottom if r in subset] - start = utility.depth(self._repo, h) - len(hrevs) + start = self._repo.stablerange.depthrev(self._repo, h) - len(hrevs) entry = _range(self._repo, h, start, [r for r in bottom if r in subset]) result.append(entry) result.append(top)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/hgext3rd/evolve/stablerange.py Sat Mar 18 22:48:26 2017 +0100 @@ -0,0 +1,106 @@ +# Code dedicated to the computation and properties of "stable ranges" +# +# These stable ranges are use for obsolescence markers discovery +# +# Copyright 2017 Pierre-Yves David <pierre-yves.david@ens-lyon.org> +# +# This software may be used and distributed according to the terms of the +# GNU General Public License version 2 or any later version. + +from mercurial import ( + localrepo, + node as nodemod, +) + +from . import ( + exthelper, +) + +eh = exthelper.exthelper() + +class stablerangecache(dict): + + def __init__(self): + self._depthcache = {} + + def depthrev(self, repo, rev): + cl = repo.changelog + cache = self._depthcache + nullrev = nodemod.nullrev + stack = [rev] + while stack: + revdepth = None + current = stack[-1] + revdepth = cache.get(current) + if revdepth is not None: + stack.pop() + continue + p1, p2 = cl.parentrevs(current) + if p1 == nullrev: + # root case + revdepth = 1 + elif p2 == nullrev: + # linear commit case + parentdepth = cache.get(p1) + if parentdepth is None: + stack.append(p1) + else: + revdepth = parentdepth + 1 + else: + # merge case + depth_p1 = cache.get(p1) + depth_p2 = cache.get(p2) + missingparent = False + if depth_p1 is None: + stack.append(p1) + missingparent = True + if depth_p2 is None: + stack.append(p2) + missingparent = True + if missingparent: + continue + # computin depth of a merge + # XXX the common ancestors heads could be cached + ancnodes = cl.commonancestorsheads(cl.node(p1), cl.node(p2)) + ancrevs = [cl.rev(a) for a in ancnodes] + anyunkown = False + ancdepth = [] + for r in ancrevs: + d = cache.get(r) + if d is None: + anyunkown = True + stack.append(r) + ancdepth.append((r, d)) + if anyunkown: + continue + if not ancrevs: + # unrelated branch, (no common root) + revdepth = depth_p1 + depth_p2 + 1 + elif len(ancrevs) == 1: + # one unique branch point: + # we can compute depth without any walk + depth_anc = ancdepth[0][1] + revdepth = depth_p1 + (depth_p2 - depth_anc) + 1 + else: + # multiple ancestors, we pick one that is + # * the deepest (less changeset outside of it), + # * lowest revs because more chance to have descendant of other "above" + anc, revdepth = max(ancdepth, key=lambda x: (x[1], -x[0])) + revdepth += len(cl.findmissingrevs(common=[anc], heads=[current])) + if revdepth is not None: + cache[current] = revdepth + stack.pop() + # actual_depth = len(list(cl.ancestors([rev], inclusive=True))) + # assert revdepth == actual_depth, (rev, revdepth, actual_depth) + return revdepth + +@eh.reposetup +def setupcache(ui, repo): + + class stablerangerepo(repo.__class__): + + @localrepo.unfilteredpropertycache + def stablerange(self): + return stablerangecache() + + repo.__class__ = stablerangerepo
--- a/hgext3rd/evolve/utility.py Wed Mar 22 03:15:58 2017 +0100 +++ b/hgext3rd/evolve/utility.py Sat Mar 18 22:48:26 2017 +0100 @@ -4,7 +4,6 @@ # # This software may be used and distributed according to the terms of the # GNU General Public License version 2 or any later version. -from mercurial import node def obsexcmsg(ui, message, important=False): verbose = ui.configbool('experimental', 'verbose-obsolescence-exchange', @@ -19,36 +18,3 @@ if ui.configbool('experimental', 'verbose-obsolescence-exchange', False): topic = 'OBSEXC' ui.progress(topic, *args, **kwargs) - -_depthcache = {} -def depth(repo, rev): - cl = repo.changelog - n = cl.node(rev) - revdepth = _depthcache.get(n, None) - if revdepth is None: - p1, p2 = cl.parentrevs(rev) - if p1 == node.nullrev: - revdepth = 1 - elif p2 == node.nullrev: - revdepth = depth(repo, p1) + 1 - else: - 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(cl.findmissingrevs(common=[anc], heads=[rev])) - _depthcache[n] = revdepth - # actual_depth = len(list(cl.ancestors([rev], inclusive=True))) - # assert revdepth == actual_depth, (rev, revdepth, actual_depth) - return revdepth