# discovery.py - protocol changeset discovery functions
#
# Copyright 2010 Olivia Mackall <olivia@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.
import collections
from .i18n import _
from .node import short
from . import (
error,
)
def findcommonincoming(repo, remote, heads=None, force=False, audit=None):
"""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.
"""
knownnode = repo.changelog.hasnode
search = []
fetch = set()
seen = set()
seenbranch = set()
base = set()
if not heads:
with remote.commandexecutor() as e:
heads = e.callcommand(b'heads', {}).result()
if audit is not None:
audit[b'total-roundtrips'] = 1
audit[b'total-roundtrips-heads'] = 1
audit[b'total-roundtrips-branches'] = 0
audit[b'total-roundtrips-between'] = 0
audit[b'total-queries'] = 0
audit[b'total-queries-branches'] = 0
audit[b'total-queries-between'] = 0
if repo.changelog.tip() == repo.nullid:
base.add(repo.nullid)
if heads != [repo.nullid]:
return [repo.nullid], [repo.nullid], list(heads)
return [repo.nullid], [], heads
# assume we're closer to the tip than the root
# and start by examining the heads
repo.ui.status(_(b"searching for changes\n"))
unknown = []
for h in heads:
if not knownnode(h):
unknown.append(h)
else:
base.add(h)
if not unknown:
return list(base), [], list(heads)
req = set(unknown)
reqcnt = 0
progress = repo.ui.makeprogress(_(b'searching'), unit=_(b'queries'))
# 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)
with remote.commandexecutor() as e:
if audit is not None:
audit[b'total-queries'] += len(unknown)
audit[b'total-queries-branches'] += len(unknown)
audit[b'total-roundtrips'] += 1
audit[b'total-roundtrips-branches'] += 1
branches = e.callcommand(b'branches', {b'nodes': unknown}).result()
unknown = collections.deque(branches)
while unknown:
r = []
while unknown:
n = unknown.popleft()
if n[0] in seen:
continue
repo.ui.debug(b"examining %s:%s\n" % (short(n[0]), short(n[1])))
if n[0] == repo.nullid: # found the end of the branch
pass
elif n in seenbranch:
repo.ui.debug(b"branch already found\n")
continue
elif n[1] and knownnode(n[1]): # do we know the base?
repo.ui.debug(
b"found incomplete branch %s:%s\n"
% (short(n[0]), short(n[1]))
)
search.append(n[0:2]) # schedule branch range for scanning
seenbranch.add(n)
else:
if n[1] not in seen and n[1] not in fetch:
if knownnode(n[2]) and knownnode(n[3]):
repo.ui.debug(b"found new changeset %s\n" % short(n[1]))
fetch.add(n[1]) # earliest unknown
for p in n[2:4]:
if knownnode(p):
base.add(p) # latest known
for p in n[2:4]:
if p not in req and not knownnode(p):
r.append(p)
req.add(p)
seen.add(n[0])
if r:
for p in range(0, len(r), 10):
reqcnt += 1
progress.increment()
if repo.ui.debugflag:
msg = b"request %d: %s\n"
msg %= (reqcnt, b" ".join(map(short, r)))
repo.ui.debug(msg)
with remote.commandexecutor() as e:
subset = r[p : p + 10]
if audit is not None:
audit[b'total-queries'] += len(subset)
audit[b'total-queries-branches'] += len(subset)
audit[b'total-roundtrips'] += 1
audit[b'total-roundtrips-branches'] += 1
branches = e.callcommand(
b'branches',
{
b'nodes': subset,
},
).result()
for b in branches:
repo.ui.debug(
b"received %s:%s\n" % (short(b[0]), short(b[1]))
)
unknown.append(b)
# do binary search on the branches we found
while search:
newsearch = []
reqcnt += 1
progress.increment()
with remote.commandexecutor() as e:
if audit is not None:
audit[b'total-queries'] += len(search)
audit[b'total-queries-between'] += len(search)
audit[b'total-roundtrips'] += 1
audit[b'total-roundtrips-between'] += 1
between = e.callcommand(b'between', {b'pairs': search}).result()
for n, l in zip(search, between):
l.append(n[1])
p = n[0]
f = 1
for i in l:
repo.ui.debug(b"narrowing %d:%d %s\n" % (f, len(l), short(i)))
if knownnode(i):
if f <= 2:
repo.ui.debug(
b"found new branch changeset %s\n" % short(p)
)
fetch.add(p)
base.add(i)
else:
repo.ui.debug(
b"narrowed branch search to %s:%s\n"
% (short(p), short(i))
)
newsearch.append((p, i))
break
p, f = i, f * 2
search = newsearch
# sanity check our fetch list
for f in fetch:
if knownnode(f):
raise error.RepoError(_(b"already have changeset ") + short(f[:4]))
base = list(base)
if base == [repo.nullid]:
if force:
repo.ui.warn(_(b"warning: repository is unrelated\n"))
else:
raise error.Abort(_(b"repository is unrelated"))
repo.ui.debug(
b"found new changesets starting at "
+ b" ".join([short(f) for f in fetch])
+ b"\n"
)
progress.complete()
repo.ui.debug(b"%d total queries\n" % reqcnt)
return base, list(fetch), heads