diff -r 38184a72d793 -r cb98fed52495 mercurial/setdiscovery.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/mercurial/setdiscovery.py Mon May 02 19:21:30 2011 +0200 @@ -0,0 +1,178 @@ +# setdiscovery.py - improved discovery of common nodeset for mercurial +# +# Copyright 2010 Benoit Boissinot +# and Peter Arrenbrecht +# +# 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, collections, 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 = collections.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 = set(dag.heads()) + 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. + + shortcutlocal determines whether we try use direct access to localrepo if + remote is actually local. + ''' + roundtrips = 0 + cl = local.changelog + dag = dagutil.revlogdag(cl) + nodes = dag.nodeset() + + # early exit if we know all the specified server heads already + ui.debug("query 1; heads\n") + roundtrips += 1 + srvheadhashes = remote.heads() + + ## TODO We might want to request an additional random sample of the server's + ## nodes batched with the heads query here. + + 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.note("all remote heads known locally\n") + return (srvheadhashes, False, srvheadhashes,) + + # full blown discovery + undecided = nodes # own nodes where I don't know if the server knows them + common = set() # own nodes I know we both know + missing = set() # own nodes I know the server lacks + + # treat remote heads as a first implicit sample response + common.update(dag.ancestorset(srvheads)) + undecided.difference_update(common) + # use cheapish initial sample + if common: + ui.debug("taking initial sample\n") + sample = _takefullsample(dag, undecided, size=fullsamplesize) + else: + ui.debug("taking quick initial sample\n") + sample = _takequicksample(dag, nodes, 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)) + + while undecided: + 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 + + ui.note("sampling from both directions\n") + sample = _takefullsample(dag, undecided, size=fullsamplesize) + + 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)) + + 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,) + + return (dag.externalizeall(result), True, srvheadhashes,)