treediscovery.py
185 lines
| 5.8 KiB
| text/x-python
|
PythonLexer
/ mercurial / treediscovery.py
|
r14164 | # discovery.py - protocol changeset discovery functions | ||
# | ||||
# Copyright 2010 Matt Mackall <mpm@selenic.com> | ||||
# | ||||
# This software may be used and distributed according to the terms of the | ||||
# GNU General Public License version 2 or any later version. | ||||
|
r25987 | from __future__ import absolute_import | ||
|
r25113 | import collections | ||
|
r25987 | |||
from .i18n import _ | ||||
from .node import ( | ||||
nullid, | ||||
short, | ||||
) | ||||
from . import ( | ||||
error, | ||||
|
r38806 | pycompat, | ||
|
r25987 | ) | ||
|
r14164 | |||
|
r43346 | |||
|
r14164 | def findcommonincoming(repo, remote, heads=None, force=False): | ||
"""Return a tuple (common, fetch, heads) used to identify the common | ||||
subset of nodes between repo and remote. | ||||
"common" is a list of (at least) the heads of the common subset. | ||||
"fetch" is a list of roots of the nodes that would be incoming, to be | ||||
supplied to changegroupsubset. | ||||
"heads" is either the supplied heads, or else the remote's heads. | ||||
""" | ||||
|
r20225 | knownnode = repo.changelog.hasnode | ||
|
r14164 | search = [] | ||
fetch = set() | ||||
seen = set() | ||||
seenbranch = set() | ||||
base = set() | ||||
if not heads: | ||||
|
r37652 | with remote.commandexecutor() as e: | ||
|
r43347 | heads = e.callcommand(b'heads', {}).result() | ||
|
r14164 | |||
if repo.changelog.tip() == nullid: | ||||
base.add(nullid) | ||||
if heads != [nullid]: | ||||
return [nullid], [nullid], list(heads) | ||||
|
r14199 | return [nullid], [], heads | ||
|
r14164 | |||
# assume we're closer to the tip than the root | ||||
# and start by examining the heads | ||||
|
r43347 | repo.ui.status(_(b"searching for changes\n")) | ||
|
r14164 | |||
unknown = [] | ||||
for h in heads: | ||||
|
r20225 | if not knownnode(h): | ||
|
r14164 | unknown.append(h) | ||
else: | ||||
base.add(h) | ||||
|
r14199 | if not unknown: | ||
return list(base), [], list(heads) | ||||
|
r14164 | req = set(unknown) | ||
reqcnt = 0 | ||||
|
r43347 | progress = repo.ui.makeprogress(_(b'searching'), unit=_(b'queries')) | ||
|
r14164 | |||
# search through remote branches | ||||
# a 'branch' here is a linear segment of history, with four parts: | ||||
# head, root, first parent, second parent | ||||
# (a branch always has two parents (or none) by definition) | ||||
|
r37652 | with remote.commandexecutor() as e: | ||
|
r43347 | branches = e.callcommand(b'branches', {b'nodes': unknown}).result() | ||
|
r37652 | |||
unknown = collections.deque(branches) | ||||
|
r14164 | while unknown: | ||
r = [] | ||||
while unknown: | ||||
|
r16803 | n = unknown.popleft() | ||
|
r14164 | if n[0] in seen: | ||
continue | ||||
|
r43347 | repo.ui.debug(b"examining %s:%s\n" % (short(n[0]), short(n[1]))) | ||
|
r43346 | if n[0] == nullid: # found the end of the branch | ||
|
r14164 | pass | ||
elif n in seenbranch: | ||||
|
r43347 | repo.ui.debug(b"branch already found\n") | ||
|
r14164 | continue | ||
|
r43346 | elif n[1] and knownnode(n[1]): # do we know the base? | ||
repo.ui.debug( | ||||
|
r43347 | b"found incomplete branch %s:%s\n" | ||
|
r43346 | % (short(n[0]), short(n[1])) | ||
) | ||||
search.append(n[0:2]) # schedule branch range for scanning | ||||
|
r14164 | seenbranch.add(n) | ||
else: | ||||
if n[1] not in seen and n[1] not in fetch: | ||||
|
r20225 | if knownnode(n[2]) and knownnode(n[3]): | ||
|
r43347 | repo.ui.debug(b"found new changeset %s\n" % short(n[1])) | ||
|
r43346 | fetch.add(n[1]) # earliest unknown | ||
|
r14164 | for p in n[2:4]: | ||
|
r20225 | if knownnode(p): | ||
|
r43346 | base.add(p) # latest known | ||
|
r14164 | |||
for p in n[2:4]: | ||||
|
r20225 | if p not in req and not knownnode(p): | ||
|
r14164 | r.append(p) | ||
req.add(p) | ||||
seen.add(n[0]) | ||||
if r: | ||||
reqcnt += 1 | ||||
|
r38419 | progress.increment() | ||
|
r43346 | repo.ui.debug( | ||
|
r43347 | b"request %d: %s\n" % (reqcnt, b" ".join(map(short, r))) | ||
|
r43346 | ) | ||
|
r38806 | for p in pycompat.xrange(0, len(r), 10): | ||
|
r37652 | with remote.commandexecutor() as e: | ||
|
r43346 | branches = e.callcommand( | ||
|
r46554 | b'branches', | ||
{ | ||||
b'nodes': r[p : p + 10], | ||||
}, | ||||
|
r43346 | ).result() | ||
|
r37652 | |||
for b in branches: | ||||
|
r43346 | repo.ui.debug( | ||
|
r43347 | b"received %s:%s\n" % (short(b[0]), short(b[1])) | ||
|
r43346 | ) | ||
|
r14164 | unknown.append(b) | ||
# do binary search on the branches we found | ||||
while search: | ||||
newsearch = [] | ||||
reqcnt += 1 | ||||
|
r38419 | progress.increment() | ||
|
r37652 | |||
with remote.commandexecutor() as e: | ||||
|
r43347 | between = e.callcommand(b'between', {b'pairs': search}).result() | ||
|
r37652 | |||
for n, l in zip(search, between): | ||||
|
r14164 | l.append(n[1]) | ||
p = n[0] | ||||
f = 1 | ||||
for i in l: | ||||
|
r43347 | repo.ui.debug(b"narrowing %d:%d %s\n" % (f, len(l), short(i))) | ||
|
r20225 | if knownnode(i): | ||
|
r14164 | if f <= 2: | ||
|
r43346 | repo.ui.debug( | ||
|
r43347 | b"found new branch changeset %s\n" % short(p) | ||
|
r43346 | ) | ||
|
r14164 | fetch.add(p) | ||
base.add(i) | ||||
else: | ||||
|
r43346 | repo.ui.debug( | ||
|
r43347 | b"narrowed branch search to %s:%s\n" | ||
|
r43346 | % (short(p), short(i)) | ||
) | ||||
|
r14164 | newsearch.append((p, i)) | ||
break | ||||
p, f = i, f * 2 | ||||
search = newsearch | ||||
# sanity check our fetch list | ||||
for f in fetch: | ||||
|
r20225 | if knownnode(f): | ||
|
r43347 | raise error.RepoError(_(b"already have changeset ") + short(f[:4])) | ||
|
r14164 | |||
base = list(base) | ||||
if base == [nullid]: | ||||
if force: | ||||
|
r43347 | repo.ui.warn(_(b"warning: repository is unrelated\n")) | ||
|
r14164 | else: | ||
|
r43347 | raise error.Abort(_(b"repository is unrelated")) | ||
|
r14164 | |||
|
r43346 | repo.ui.debug( | ||
|
r43347 | b"found new changesets starting at " | ||
+ b" ".join([short(f) for f in fetch]) | ||||
+ b"\n" | ||||
|
r43346 | ) | ||
|
r14164 | |||
|
r38419 | progress.complete() | ||
|
r43347 | repo.ui.debug(b"%d total queries\n" % reqcnt) | ||
|
r14164 | |||
return base, list(fetch), heads | ||||