# HG changeset patch # User Pierre-Yves David # Date 1489889221 -3600 # Node ID d784622dd5dc6d768a67cebd20e11c1ac147bf35 # Parent d07bb7cbae2fa1e0e7ca2839090e703ff7b3ec37 stablerange: move the range class in the new module Our ultimate goal is to remove this class for performance reason. however for now, it contains most of the code we care about so we migrate it as a block first. diff -r d07bb7cbae2f -r d784622dd5dc hgext3rd/evolve/obsdiscovery.py --- a/hgext3rd/evolve/obsdiscovery.py Sun Mar 19 03:06:53 2017 +0100 +++ b/hgext3rd/evolve/obsdiscovery.py Sun Mar 19 03:07:01 2017 +0100 @@ -24,7 +24,6 @@ import hashlib import heapq -import math import struct from mercurial import ( @@ -260,7 +259,7 @@ return True for h in heads: - entry = _range(local, h, 0) + entry = stablerange.stablerange(local, h, 0) addentry(entry) querycount = 0 @@ -362,7 +361,7 @@ n = data[:20] index = _unpack('>I', data[20:])[0] r = op.repo.changelog.rev(n) - rhash = _range(op.repo, r, index).obshash + rhash = stablerange.stablerange(op.repo, r, index).obshash replies.append(data + rhash) data = inpart.read(24) op.reply.newpart('reply:_donotusemeever_evoext_obshashrange_1', data=iter(replies)) @@ -395,7 +394,7 @@ # prewarm depth cache for r in repo.revs("::%ld", revs): repo.stablerange.depthrev(repo, r) - toproceed = [_range(repo, r, 0, ) for r in revs] + toproceed = [stablerange.stablerange(repo, r, 0, ) for r in revs] ranges = set(toproceed) while toproceed: entry = toproceed.pop() @@ -410,147 +409,6 @@ d = (r.head, s(r.node), r.index, len(r), r.depth, node.short(r.obshash)) ui.status('%3d %s %5d %4d %5d %s\n' % d) -def _hlp2(i): - """return highest power of two lower than 'i'""" - return 2 ** int(math.log(i - 1, 2)) - -class _range(object): - - def __init__(self, repo, head, index, revs=None): - self._repo = repo.unfiltered() - self.head = head - self.index = index - if revs is not None: - assert len(revs) == len(self) - self._revs = revs - assert index < self.depth, (head, index, self.depth, revs) - - def __repr__(self): - return '%s %d %d %s' % (node.short(self.node), self.depth, self.index, node.short(self.obshash)) - - def __hash__(self): - return self._id - - def __eq__(self, other): - if type(self) != type(other): - raise NotImplementedError() - return self.stablekey == other.stablekey - - @util.propertycache - def _id(self): - return hash(self.stablekey) - - @util.propertycache - def stablekey(self): - return (self.node, self.index) - - @util.propertycache - def node(self): - return self._repo.changelog.node(self.head) - - def __len__(self): - return self.depth - self.index - - @util.propertycache - def depth(self): - return self._repo.stablerange.depthrev(self._repo, self.head) - - @util.propertycache - def _revs(self): - r = stablerange.stablesort(self._repo, [self.head])[self.index:] - assert len(r) == len(self), (self.head, self.index, len(r), len(self)) - return r - - def _slicesat(self, globalindex): - localindex = globalindex - self.index - - cl = self._repo.changelog - - result = [] - bottom = self._revs[:localindex] - top = _range(self._repo, self.head, globalindex, self._revs[localindex:]) - # - toprootdepth = self._repo.stablerange.depthrev(self._repo, top._revs[0]) - if toprootdepth + len(top) == self.depth + 1: - bheads = [bottom[-1]] - else: - bheads = set(bottom) - parentrevs = cl.parentrevs - du = bheads.difference_update - for r in bottom: - du(parentrevs(r)) - # if len(bheads) == 1: - # assert 1 == len(self._repo.revs('roots(%ld)', top._revs)) - if len(bheads) == 1: - newhead = bottom[-1] - bottomdepth = self._repo.stablerange.depthrev(self._repo, newhead) - newstart = bottomdepth - len(bottom) - result.append(_range(self._repo, newhead, newstart, bottom)) - else: - # assert 1 < len(bheads), (toprootdepth, len(top), len(self)) - cl = self._repo.changelog - for h in bheads: - subset = cl.ancestors([h], inclusive=True) - hrevs = [r for r in bottom if r in subset] - 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) - return result - - def subranges(self): - cached = self._repo.stablerange.subranges(self._repo, self) - if cached is not None: - return cached - step = _hlp2(self.depth) - standard_start = 0 - while standard_start < self.index and 0 < step: - if standard_start + step < self.depth: - standard_start += step - step //= 2 - if self.index == standard_start: - slicesize = _hlp2(len(self)) - slicepoint = self.index + slicesize - else: - assert standard_start < self.depth - slicepoint = standard_start - result = self._slicesat(slicepoint) - self._repo.stablerange.setsubranges(self, result) - return result - - @util.propertycache - def obshash(self): - cache = self._repo.obsstore.rangeobshashcache - obshash = cache.get(self) - if obshash is not None: - return obshash - pieces = [] - nullid = node.nullid - if len(self) == 1: - tmarkers = self._repo.obsstore.relevantmarkers([self.node]) - pieces = [] - for m in tmarkers: - mbin = obsolete._fm1encodeonemarker(m) - pieces.append(mbin) - pieces.sort() - else: - for subrange in self.subranges(): - obshash = subrange.obshash - if obshash != nullid: - pieces.append(obshash) - - sha = hashlib.sha1() - # note: if there is only one subrange with actual data, we'll just - # reuse the same hash. - if not pieces: - obshash = node.nullid - elif len(pieces) != 1 or obshash is None: - sha = hashlib.sha1() - for p in pieces: - sha.update(p) - obshash = cache[self] = sha.digest() - return obshash - @eh.wrapfunction(obsolete.obsstore, '_addmarkers') def _addmarkers(orig, obsstore, *args, **kwargs): obsstore.rangeobshashcache.clear() diff -r d07bb7cbae2f -r d784622dd5dc hgext3rd/evolve/stablerange.py --- a/hgext3rd/evolve/stablerange.py Sun Mar 19 03:06:53 2017 +0100 +++ b/hgext3rd/evolve/stablerange.py Sun Mar 19 03:07:01 2017 +0100 @@ -8,18 +8,23 @@ # GNU General Public License version 2 or any later version. import collections +import math +import hashlib + from mercurial import ( commands, cmdutil, localrepo, node as nodemod, scmutil, + util, ) from mercurial.i18n import _ from . import ( exthelper, + obsolete, ) eh = exthelper.exthelper() @@ -123,6 +128,10 @@ assert len(result) == len(set(result)) return result +################################# +### Stable Range computation ### +################################# + class stablerangecache(dict): def __init__(self): @@ -227,6 +236,147 @@ # this class reach. return self._subrangescache.get(rangeid) +def _hlp2(i): + """return highest power of two lower than 'i'""" + return 2 ** int(math.log(i - 1, 2)) + +class stablerange(object): + + def __init__(self, repo, head, index, revs=None): + self._repo = repo.unfiltered() + self.head = head + self.index = index + if revs is not None: + assert len(revs) == len(self) + self._revs = revs + assert index < self.depth, (head, index, self.depth, revs) + + def __repr__(self): + return '%s %d %d %s' % (nodemod.short(self.node), self.depth, self.index, nodemod.short(self.obshash)) + + def __hash__(self): + return self._id + + def __eq__(self, other): + if type(self) != type(other): + raise NotImplementedError() + return self.stablekey == other.stablekey + + @util.propertycache + def _id(self): + return hash(self.stablekey) + + @util.propertycache + def stablekey(self): + return (self.node, self.index) + + @util.propertycache + def node(self): + return self._repo.changelog.node(self.head) + + def __len__(self): + return self.depth - self.index + + @util.propertycache + def depth(self): + return self._repo.stablerange.depthrev(self._repo, self.head) + + @util.propertycache + def _revs(self): + r = stablesort(self._repo, [self.head])[self.index:] + assert len(r) == len(self), (self.head, self.index, len(r), len(self)) + return r + + def _slicesat(self, globalindex): + localindex = globalindex - self.index + + cl = self._repo.changelog + + result = [] + bottom = self._revs[:localindex] + top = stablerange(self._repo, self.head, globalindex, self._revs[localindex:]) + # + toprootdepth = self._repo.stablerange.depthrev(self._repo, top._revs[0]) + if toprootdepth + len(top) == self.depth + 1: + bheads = [bottom[-1]] + else: + bheads = set(bottom) + parentrevs = cl.parentrevs + du = bheads.difference_update + for r in bottom: + du(parentrevs(r)) + # if len(bheads) == 1: + # assert 1 == len(self._repo.revs('roots(%ld)', top._revs)) + if len(bheads) == 1: + newhead = bottom[-1] + bottomdepth = self._repo.stablerange.depthrev(self._repo, newhead) + newstart = bottomdepth - len(bottom) + result.append(stablerange(self._repo, newhead, newstart, bottom)) + else: + # assert 1 < len(bheads), (toprootdepth, len(top), len(self)) + cl = self._repo.changelog + for h in bheads: + subset = cl.ancestors([h], inclusive=True) + hrevs = [r for r in bottom if r in subset] + start = self._repo.stablerange.depthrev(self._repo, h) - len(hrevs) + entry = stablerange(self._repo, h, start, [r for r in bottom if r in subset]) + result.append(entry) + result.append(top) + return result + + def subranges(self): + cached = self._repo.stablerange.subranges(self._repo, self) + if cached is not None: + return cached + step = _hlp2(self.depth) + standard_start = 0 + while standard_start < self.index and 0 < step: + if standard_start + step < self.depth: + standard_start += step + step //= 2 + if self.index == standard_start: + slicesize = _hlp2(len(self)) + slicepoint = self.index + slicesize + else: + assert standard_start < self.depth + slicepoint = standard_start + result = self._slicesat(slicepoint) + self._repo.stablerange.setsubranges(self, result) + return result + + @util.propertycache + def obshash(self): + cache = self._repo.obsstore.rangeobshashcache + obshash = cache.get(self) + if obshash is not None: + return obshash + pieces = [] + nullid = nodemod.nullid + if len(self) == 1: + tmarkers = self._repo.obsstore.relevantmarkers([self.node]) + pieces = [] + for m in tmarkers: + mbin = obsolete._fm1encodeonemarker(m) + pieces.append(mbin) + pieces.sort() + else: + for subrange in self.subranges(): + obshash = subrange.obshash + if obshash != nullid: + pieces.append(obshash) + + sha = hashlib.sha1() + # note: if there is only one subrange with actual data, we'll just + # reuse the same hash. + if not pieces: + obshash = nodemod.nullid + elif len(pieces) != 1 or obshash is None: + sha = hashlib.sha1() + for p in pieces: + sha.update(p) + obshash = cache[self] = sha.digest() + return obshash + @eh.reposetup def setupcache(ui, repo):