setdiscovery.py
200 lines
| 6.9 KiB
| text/x-python
|
PythonLexer
/ mercurial / setdiscovery.py
|
r14164 | # 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, collections, util, dagutil | ||||
|
r15713 | import phases | ||
|
r14164 | |||
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 | ||||
|
r15063 | always = dag.headsetofconnecteds(nodes) | ||
|
r14164 | 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): | ||||
|
r14206 | '''Return a tuple (common, anyincoming, remoteheads) used to identify | ||
missing nodes from or in remote. | ||||
|
r14164 | |||
shortcutlocal determines whether we try use direct access to localrepo if | ||||
remote is actually local. | ||||
''' | ||||
roundtrips = 0 | ||||
cl = local.changelog | ||||
dag = dagutil.revlogdag(cl) | ||||
|
r14624 | # early exit if we know all the specified remote heads already | ||
|
r14164 | ui.debug("query 1; heads\n") | ||
roundtrips += 1 | ||||
|
r14624 | ownheads = dag.heads() | ||
sample = ownheads | ||||
if remote.local(): | ||||
# stopgap until we have a proper localpeer that supports batch() | ||||
|
r15713 | srvheadhashes = phases.visibleheads(remote) | ||
|
r14624 | 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: | ||||
# compatibitity with pre-batch, but post-known remotes during 1.9 devel | ||||
srvheadhashes = remote.heads() | ||||
sample = [] | ||||
|
r14164 | |||
if cl.tip() == nullid: | ||||
if srvheadhashes != [nullid]: | ||||
return [nullid], True, srvheadhashes | ||||
return [nullid], False, [] | ||||
|
r14206 | # start actual discovery (we note this before the next "if" for | ||
# compatibility reasons) | ||||
|
r14164 | ui.status(_("searching for changes\n")) | ||
srvheads = dag.internalizeall(srvheadhashes, filterunknown=True) | ||||
if len(srvheads) == len(srvheadhashes): | ||||
|
r14833 | ui.debug("all remote heads known locally\n") | ||
|
r14164 | return (srvheadhashes, False, srvheadhashes,) | ||
|
r14624 | if sample and util.all(yesno): | ||
|
r15497 | ui.note(_("all local heads known remotely\n")) | ||
|
r14624 | ownheadhashes = dag.externalizeall(ownheads) | ||
return (ownheadhashes, True, srvheadhashes,) | ||||
|
r14164 | # full blown discovery | ||
|
r16683 | # 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 | ||||
|
r14164 | common.update(dag.ancestorset(srvheads)) | ||
undecided.difference_update(common) | ||||
|
r14624 | |||
full = False | ||||
while undecided: | ||||
|
r14164 | |||
|
r14624 | if sample: | ||
commoninsample = set(n for i, n in enumerate(sample) if yesno[i]) | ||||
common.update(dag.ancestorset(commoninsample, common)) | ||||
|
r14164 | |||
|
r14624 | missinginsample = [n for i, n in enumerate(sample) if not yesno[i]] | ||
missing.update(dag.descendantset(missinginsample, missing)) | ||||
|
r14164 | |||
|
r14624 | undecided.difference_update(missing) | ||
undecided.difference_update(common) | ||||
|
r14164 | |||
if not undecided: | ||||
break | ||||
|
r14624 | if full: | ||
|
r15497 | ui.note(_("sampling from both directions\n")) | ||
|
r14624 | 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) | ||||
|
r14164 | |||
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)) | ||||
|
r14624 | full = True | ||
|
r14164 | |||
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,) | ||||
|
r14981 | anyincoming = (srvheadhashes != [nullid]) | ||
return dag.externalizeall(result), anyincoming, srvheadhashes | ||||