# HG changeset patch # User Pierre-Yves David # Date 1537738868 -7200 # Node ID bc4e62a1cb823bcbe6eebd234ca80e18b29d675f # Parent 4e5ec9ae682e49ae2733f279777d4c11744ffe34 pullbundle: slice pull into multiple ranges We subdivide the set of missing revisions into multiple "range" using the "stable range" data structure. This slicing aims at maximizing the capability of the resulting ranges. diff -r 4e5ec9ae682e -r bc4e62a1cb82 hgext3rd/pullbundle.py --- a/hgext3rd/pullbundle.py Sun Sep 23 23:53:23 2018 +0200 +++ b/hgext3rd/pullbundle.py Sun Sep 23 23:41:08 2018 +0200 @@ -5,14 +5,22 @@ # This software may be used and distributed according to the terms of the # GNU General Public License version 2 or any later version. +import errno +import os + from mercurial import ( changegroup, + discovery, exchange, narrowspec, + node as nodemod, + util, ) from mercurial.i18n import _ +# generic wrapping + def uisetup(ui): exchange.getbundle2partsmapping['changegroup'] = _getbundlechangegrouppart @@ -59,14 +67,156 @@ def makeallcgpart(newpart, repo, outgoing, version, source, bundlecaps, filematcher, cgversions): - makeonecgpart(newpart, repo, outgoing, version, source, bundlecaps, - filematcher, cgversions) + + pullbundle = not filematcher + if pullbundle and not util.safehasattr(repo, 'stablerange'): + repo.ui.warn('pullbundle: required extension "evolve" are missing, skipping pullbundle\n') + pullbundle = False + if filematcher: + makeonecgpart(newpart, repo, None, outgoing, version, source, bundlecaps, + filematcher, cgversions) + else: + for sliceid, sliceout in sliceoutgoing(repo, outgoing): + makeonecgpart(newpart, repo, sliceid, sliceout, version, source, bundlecaps, + filematcher, cgversions) + +# stable range slicing + +def sliceoutgoing(repo, outgoing): + cl = repo.changelog + rev = cl.nodemap.get + node = cl.node + revsort = repo.stablesort + + missingrevs = set(rev(n) for n in outgoing.missing) + allslices = [] + missingheads = [rev(n) for n in outgoing.missingheads] + for head in missingheads: + localslices = [] + localmissing = set(repo.revs('%ld and ::%d', missingrevs, head)) + while localmissing: + slicerevs = [] + for r in revsort.walkfrom(repo, head): + if r not in missingrevs: + break + slicerevs.append(r) + slicenodes = [node(r) for r in slicerevs] + localslices.extend(canonicalslices(repo, slicenodes)) + missingrevs.difference_update(slicerevs) + localmissing.difference_update(slicerevs) + if localmissing: + head = max(localmissing) + + allslices.extend(localslices) + return [(rangeid, outgoingfromnodes(repo, nodes)) + for rangeid, nodes in allslices] + +def canonicalslices(repo, nodes): + depth = repo.depthcache.get + stablerange = repo.stablerange + rangelength = lambda x: stablerange.rangelength(repo, x) + headrev = repo.changelog.rev(nodes[0]) + nbrevs = len(nodes) + headdepth = depth(headrev) + skipped = headdepth - nbrevs + rangeid = (headrev, skipped) + + subranges = canonicalsubranges(repo, stablerange, rangeid) + idx = 0 + slices =[] + nodes.reverse() + for rangeid in subranges: + size = rangelength(rangeid) + slices.append((rangeid, nodes[idx:idx + size])) + idx += size + return slices + +def canonicalsubranges(repo, stablerange, rangeid): + """slice a size of nodes into most reusable subranges + + We try to slice a range into a set of "largest" and "canonical" stable + range. + + It might make sense to move this function as a 'stablerange' method. + """ + headrev, skip = rangeid + rangedepth = stablerange.depthrev(repo, rangeid[0]) + canonicals = [] + + # 0. find the first power of 2 higher than this range depth + cursor = 1 + while cursor <= rangedepth: + cursor *= 2 + + # 1. find first cupt + precut = cut = 0 + while True: + if skip <= cut: + break + if cut + cursor < rangedepth: + precut = cut + cut += cursor + if cursor == 1: + break + cursor //=2 + + # 2. optimise, bottom part + if skip != cut: + tailranges = [] + tailsize = cut - skip + assert 0 < tailsize, tailsize + prerange = (headrev, precut) + size = stablerange.rangelength(repo, prerange) + sub = stablerange.subranges(repo, prerange)[:-1] + while not poweroftwo(tailsize): + for prerange in reversed(sub): + if tailsize <= 0: + break + + assert stablerange.depthrev(repo, prerange[0]) != prerange[1], prerange + tailrev, tailskip = prerange + size = stablerange.rangelength(repo, (tailrev, tailskip)) + if tailsize < size: + tailskip += size - tailsize + size = tailsize + tailranges.append((tailrev, tailskip)) + tailsize -= size + else: + # size of the last block + tailsize = stablerange.rangelength(repo, tailranges[-1]) + if poweroftwo(tailsize): + continue # exit the loop + prerange = tailranges.pop() + sub = stablerange.subranges(repo, prerange) + + tailranges.reverse() + canonicals.extend(tailranges) + + # 3. take recursive subrange until we get to a power of two size? + current = (headrev, cut) + while not poweroftwo(stablerange.rangelength(repo, current)): + sub = stablerange.subranges(repo, current) + canonicals.extend(sub[:-1]) + current = sub[-1] + canonicals.append(current) + + return canonicals + +def poweroftwo(num): + return num and not num & (num - 1) + +def outgoingfromnodes(repo, nodes): + return discovery.outgoing(repo, + missingroots=nodes, + missingheads=nodes) + +# changegroup part construction def _changegroupinfo(repo, nodes, source): if repo.ui.verbose or source == 'bundle': repo.ui.status(_("%d changesets found\n") % len(nodes)) -def makeonecgpart(newpart, repo, outgoing, version, source, +def makeonecgpart(newpart, repo, rangeid, outgoing, version, source, bundlecaps, filematcher, cgversions): # same as upstream code diff -r 4e5ec9ae682e -r bc4e62a1cb82 tests/test-pullbundle.t --- a/tests/test-pullbundle.t Sun Sep 23 23:53:23 2018 +0200 +++ b/tests/test-pullbundle.t Sun Sep 23 23:41:08 2018 +0200 @@ -2,7 +2,11 @@ $ cat << EOF >> $HGRCPATH > [extensions] + > # evolve is providing the stable range code + > evolve= > pullbundle= + > [experimental] + > obshashrange.warm-cache=yes > EOF basic setup @@ -10,16 +14,31 @@ $ hg init server $ hg -R server debugbuilddag '.+898:branchpoint+352:mergepoint+267