Mercurial > evolve
changeset 2130:d784622dd5dc
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.
| author | Pierre-Yves David <pierre-yves.david@ens-lyon.org> |
|---|---|
| date | Sun, 19 Mar 2017 03:07:01 +0100 |
| parents | d07bb7cbae2f |
| children | 86dd39478638 |
| files | hgext3rd/evolve/obsdiscovery.py hgext3rd/evolve/stablerange.py |
| diffstat | 2 files changed, 153 insertions(+), 145 deletions(-) [+] |
line wrap: on
line diff
--- 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()
--- 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):