| # setdiscovery.py - improved discovery of common nodeset for mercurial |
| # |
| # Copyright 2010 Benoit Boissinot <bboissin@gmail.com> |
| # and Peter Arrenbrecht <peter@arrenbrecht.ch> |
| # |
| # This software may be used and distributed according to the terms of the |
| # GNU General Public License version 2 or any later version. |
| |
| from node import nullid |
| from i18n import _ |
| import random, util, dagutil |
| |
| def _updatesample(dag, nodes, sample, always, quicksamplesize=0): |
| # if nodes is empty we scan the entire graph |
| if nodes: |
| heads = dag.headsetofconnecteds(nodes) |
| else: |
| heads = dag.heads() |
| dist = {} |
| visit = util.deque(heads) |
| seen = set() |
| factor = 1 |
| while visit: |
| curr = visit.popleft() |
| if curr in seen: |
| continue |
| d = dist.setdefault(curr, 1) |
| if d > factor: |
| factor *= 2 |
| if d == factor: |
| if curr not in always: # need this check for the early exit below |
| sample.add(curr) |
| if quicksamplesize and (len(sample) >= quicksamplesize): |
| return |
| seen.add(curr) |
| for p in dag.parents(curr): |
| if not nodes or p in nodes: |
| dist.setdefault(p, d + 1) |
| visit.append(p) |
| |
| def _setupsample(dag, nodes, size): |
| if len(nodes) <= size: |
| return set(nodes), None, 0 |
| always = dag.headsetofconnecteds(nodes) |
| desiredlen = size - len(always) |
| if desiredlen <= 0: |
| # This could be bad if there are very many heads, all unknown to the |
| # server. We're counting on long request support here. |
| return always, None, desiredlen |
| return always, set(), desiredlen |
| |
| def _takequicksample(dag, nodes, size, initial): |
| always, sample, desiredlen = _setupsample(dag, nodes, size) |
| if sample is None: |
| return always |
| if initial: |
| fromset = None |
| else: |
| fromset = nodes |
| _updatesample(dag, fromset, sample, always, quicksamplesize=desiredlen) |
| sample.update(always) |
| return sample |
| |
| def _takefullsample(dag, nodes, size): |
| always, sample, desiredlen = _setupsample(dag, nodes, size) |
| if sample is None: |
| return always |
| # update from heads |
| _updatesample(dag, nodes, sample, always) |
| # update from roots |
| _updatesample(dag.inverse(), nodes, sample, always) |
| assert sample |
| if len(sample) > desiredlen: |
| sample = set(random.sample(sample, desiredlen)) |
| elif len(sample) < desiredlen: |
| more = desiredlen - len(sample) |
| sample.update(random.sample(list(nodes - sample - always), more)) |
| sample.update(always) |
| return sample |
| |
| def findcommonheads(ui, local, remote, |
| initialsamplesize=100, |
| fullsamplesize=200, |
| abortwhenunrelated=True): |
| '''Return a tuple (common, anyincoming, remoteheads) used to identify |
| missing nodes from or in remote. |
| ''' |
| roundtrips = 0 |
| cl = local.changelog |
| dag = dagutil.revlogdag(cl) |
| |
| # early exit if we know all the specified remote heads already |
| ui.debug("query 1; heads\n") |
| roundtrips += 1 |
| ownheads = dag.heads() |
| sample = ownheads |
| if remote.local(): |
| # stopgap until we have a proper localpeer that supports batch() |
| srvheadhashes = remote.heads() |
| yesno = remote.known(dag.externalizeall(sample)) |
| elif remote.capable('batch'): |
| batch = remote.batch() |
| srvheadhashesref = batch.heads() |
| yesnoref = batch.known(dag.externalizeall(sample)) |
| batch.submit() |
| srvheadhashes = srvheadhashesref.value |
| yesno = yesnoref.value |
| else: |
| # compatibility with pre-batch, but post-known remotes during 1.9 |
| # development |
| srvheadhashes = remote.heads() |
| sample = [] |
| |
| if cl.tip() == nullid: |
| if srvheadhashes != [nullid]: |
| return [nullid], True, srvheadhashes |
| return [nullid], False, [] |
| |
| # start actual discovery (we note this before the next "if" for |
| # compatibility reasons) |
| ui.status(_("searching for changes\n")) |
| |
| srvheads = dag.internalizeall(srvheadhashes, filterunknown=True) |
| if len(srvheads) == len(srvheadhashes): |
| ui.debug("all remote heads known locally\n") |
| return (srvheadhashes, False, srvheadhashes,) |
| |
| if sample and util.all(yesno): |
| ui.note(_("all local heads known remotely\n")) |
| ownheadhashes = dag.externalizeall(ownheads) |
| return (ownheadhashes, True, srvheadhashes,) |
| |
| # full blown discovery |
| |
| # own nodes where I don't know if remote knows them |
| undecided = dag.nodeset() |
| # own nodes I know we both know |
| common = set() |
| # own nodes I know remote lacks |
| missing = set() |
| |
| # treat remote heads (and maybe own heads) as a first implicit sample |
| # response |
| common.update(dag.ancestorset(srvheads)) |
| undecided.difference_update(common) |
| |
| full = False |
| while undecided: |
| |
| if sample: |
| commoninsample = set(n for i, n in enumerate(sample) if yesno[i]) |
| common.update(dag.ancestorset(commoninsample, common)) |
| |
| missinginsample = [n for i, n in enumerate(sample) if not yesno[i]] |
| missing.update(dag.descendantset(missinginsample, missing)) |
| |
| undecided.difference_update(missing) |
| undecided.difference_update(common) |
| |
| if not undecided: |
| break |
| |
| if full: |
| ui.note(_("sampling from both directions\n")) |
| sample = _takefullsample(dag, undecided, size=fullsamplesize) |
| elif common: |
| # use cheapish initial sample |
| ui.debug("taking initial sample\n") |
| sample = _takefullsample(dag, undecided, size=fullsamplesize) |
| else: |
| # use even cheaper initial sample |
| ui.debug("taking quick initial sample\n") |
| sample = _takequicksample(dag, undecided, size=initialsamplesize, |
| initial=True) |
| |
| roundtrips += 1 |
| ui.progress(_('searching'), roundtrips, unit=_('queries')) |
| ui.debug("query %i; still undecided: %i, sample size is: %i\n" |
| % (roundtrips, len(undecided), len(sample))) |
| # indices between sample and externalized version must match |
| sample = list(sample) |
| yesno = remote.known(dag.externalizeall(sample)) |
| full = True |
| |
| result = dag.headsetofconnecteds(common) |
| ui.progress(_('searching'), None) |
| ui.debug("%d total queries\n" % roundtrips) |
| |
| if not result and srvheadhashes != [nullid]: |
| if abortwhenunrelated: |
| raise util.Abort(_("repository is unrelated")) |
| else: |
| ui.warn(_("warning: repository is unrelated\n")) |
| return (set([nullid]), True, srvheadhashes,) |
| |
| anyincoming = (srvheadhashes != [nullid]) |
| return dag.externalizeall(result), anyincoming, srvheadhashes |
