discovery.py
308 lines
| 11.4 KiB
| text/x-python
|
PythonLexer
/ mercurial / discovery.py
|
r11313 | # discovery.py - protocol changeset discovery functions | ||
|
r11301 | # | ||
|
r11313 | # Copyright 2010 Matt Mackall <mpm@selenic.com> | ||
|
r11301 | # | ||
# 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, short | ||||
from i18n import _ | ||||
import util, error | ||||
|
r12760 | def findcommonincoming(repo, remote, heads=None, force=False): | ||
|
r11301 | """Return a tuple (common, missing roots, heads) used to identify | ||
missing nodes from remote. | ||||
If a list of heads is specified, return only nodes which are heads | ||||
or ancestors of these heads. | ||||
""" | ||||
m = repo.changelog.nodemap | ||||
search = [] | ||||
fetch = set() | ||||
seen = set() | ||||
seenbranch = set() | ||||
|
r12761 | base = set() | ||
|
r11301 | |||
if not heads: | ||||
heads = remote.heads() | ||||
if repo.changelog.tip() == nullid: | ||||
|
r12761 | base.add(nullid) | ||
|
r11301 | if heads != [nullid]: | ||
return [nullid], [nullid], list(heads) | ||||
return [nullid], [], [] | ||||
# assume we're closer to the tip than the root | ||||
# and start by examining the heads | ||||
repo.ui.status(_("searching for changes\n")) | ||||
unknown = [] | ||||
for h in heads: | ||||
if h not in m: | ||||
unknown.append(h) | ||||
else: | ||||
|
r12761 | base.add(h) | ||
|
r11301 | |||
heads = unknown | ||||
if not unknown: | ||||
|
r12761 | return list(base), [], [] | ||
|
r11301 | |||
req = set(unknown) | ||||
reqcnt = 0 | ||||
# 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) | ||||
unknown = remote.branches(unknown) | ||||
while unknown: | ||||
r = [] | ||||
while unknown: | ||||
n = unknown.pop(0) | ||||
if n[0] in seen: | ||||
continue | ||||
repo.ui.debug("examining %s:%s\n" | ||||
% (short(n[0]), short(n[1]))) | ||||
if n[0] == nullid: # found the end of the branch | ||||
pass | ||||
elif n in seenbranch: | ||||
repo.ui.debug("branch already found\n") | ||||
continue | ||||
elif n[1] and n[1] in m: # do we know the base? | ||||
repo.ui.debug("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 n[2] in m and n[3] in m: | ||||
repo.ui.debug("found new changeset %s\n" % | ||||
short(n[1])) | ||||
fetch.add(n[1]) # earliest unknown | ||||
for p in n[2:4]: | ||||
if p in m: | ||||
|
r12761 | base.add(p) # latest known | ||
|
r11301 | |||
for p in n[2:4]: | ||||
if p not in req and p not in m: | ||||
r.append(p) | ||||
req.add(p) | ||||
seen.add(n[0]) | ||||
if r: | ||||
reqcnt += 1 | ||||
repo.ui.progress(_('searching'), reqcnt, unit=_('queries')) | ||||
repo.ui.debug("request %d: %s\n" % | ||||
(reqcnt, " ".join(map(short, r)))) | ||||
for p in xrange(0, len(r), 10): | ||||
for b in remote.branches(r[p:p + 10]): | ||||
repo.ui.debug("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 | ||||
repo.ui.progress(_('searching'), reqcnt, unit=_('queries')) | ||||
for n, l in zip(search, remote.between(search)): | ||||
l.append(n[1]) | ||||
p = n[0] | ||||
f = 1 | ||||
for i in l: | ||||
repo.ui.debug("narrowing %d:%d %s\n" % (f, len(l), short(i))) | ||||
if i in m: | ||||
if f <= 2: | ||||
repo.ui.debug("found new branch changeset %s\n" % | ||||
short(p)) | ||||
fetch.add(p) | ||||
|
r12761 | base.add(i) | ||
|
r11301 | else: | ||
repo.ui.debug("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 f in m: | ||||
raise error.RepoError(_("already have changeset ") | ||||
+ short(f[:4])) | ||||
|
r12761 | base = list(base) | ||
if base == [nullid]: | ||||
|
r11301 | if force: | ||
repo.ui.warn(_("warning: repository is unrelated\n")) | ||||
else: | ||||
raise util.Abort(_("repository is unrelated")) | ||||
repo.ui.debug("found new changesets starting at " + | ||||
" ".join([short(f) for f in fetch]) + "\n") | ||||
repo.ui.progress(_('searching'), None) | ||||
repo.ui.debug("%d total queries\n" % reqcnt) | ||||
|
r12761 | return base, list(fetch), heads | ||
|
r11301 | |||
|
r11576 | def findoutgoing(repo, remote, base=None, remoteheads=None, force=False): | ||
|
r11301 | """Return list of nodes that are roots of subsets not in remote | ||
If base dict is specified, assume that these nodes and their parents | ||||
exist on the remote side. | ||||
|
r11576 | If remotehead is specified, assume it is the list of the heads from | ||
the remote repository. | ||||
|
r11301 | """ | ||
if base is None: | ||||
|
r12759 | base = findcommonincoming(repo, remote, heads=remoteheads, | ||
force=force)[0] | ||||
else: | ||||
base = list(base) | ||||
|
r11301 | |||
repo.ui.debug("common changesets up to " | ||||
|
r12759 | + " ".join(map(short, base)) + "\n") | ||
|
r11301 | |||
remain = set(repo.changelog.nodemap) | ||||
# prune everything remote has from the tree | ||||
remain.remove(nullid) | ||||
|
r12759 | remove = base | ||
|
r11301 | while remove: | ||
n = remove.pop(0) | ||||
if n in remain: | ||||
remain.remove(n) | ||||
for p in repo.changelog.parents(n): | ||||
remove.append(p) | ||||
# find every node whose parents have been pruned | ||||
subset = [] | ||||
# find every remote head that will get new children | ||||
for n in remain: | ||||
p1, p2 = repo.changelog.parents(n) | ||||
if p1 not in remain and p2 not in remain: | ||||
subset.append(n) | ||||
|
r11576 | return subset | ||
|
r11301 | |||
def prepush(repo, remote, force, revs, newbranch): | ||||
'''Analyze the local and remote repositories and determine which | ||||
changesets need to be pushed to the remote. Return value depends | ||||
on circumstances: | ||||
If we are not going to push anything, return a tuple (None, | ||||
outgoing) where outgoing is 0 if there are no outgoing | ||||
changesets and 1 if there are, but we refuse to push them | ||||
(e.g. would create new remote heads). | ||||
Otherwise, return a tuple (changegroup, remoteheads), where | ||||
changegroup is a readable file-like object whose read() returns | ||||
successive changegroup chunks ready to be sent over the wire and | ||||
remoteheads is the list of remote heads.''' | ||||
|
r11577 | remoteheads = remote.heads() | ||
|
r12759 | common, inc, rheads = findcommonincoming(repo, remote, heads=remoteheads, | ||
force=force) | ||||
|
r11301 | |||
cl = repo.changelog | ||||
|
r11577 | update = findoutgoing(repo, remote, common, remoteheads) | ||
|
r11301 | outg, bases, heads = cl.nodesbetween(update, revs) | ||
if not bases: | ||||
repo.ui.status(_("no changes found\n")) | ||||
return None, 1 | ||||
|
r11577 | if not force and remoteheads != [nullid]: | ||
|
r11301 | if remote.capable('branchmap'): | ||
# Check for each named branch if we're creating new remote heads. | ||||
# To be a remote head after push, node must be either: | ||||
# - unknown locally | ||||
# - a local outgoing head descended from update | ||||
# - a remote head that's known locally and not | ||||
# ancestral to an outgoing head | ||||
# | ||||
# New named branches cannot be created without --force. | ||||
# 1. Create set of branches involved in the push. | ||||
branches = set(repo[n].branch() for n in outg) | ||||
# 2. Check for new branches on the remote. | ||||
remotemap = remote.branchmap() | ||||
newbranches = branches - set(remotemap) | ||||
if newbranches and not newbranch: # new branch requires --new-branch | ||||
|
r11429 | branchnames = ', '.join(sorted(newbranches)) | ||
|
r11574 | raise util.Abort(_("push creates new remote branches: %s!") | ||
% branchnames, | ||||
hint=_("use 'hg push --new-branch' to create" | ||||
" new remote branches")) | ||||
|
r11301 | branches.difference_update(newbranches) | ||
# 3. Construct the initial oldmap and newmap dicts. | ||||
# They contain information about the remote heads before and | ||||
# after the push, respectively. | ||||
# Heads not found locally are not included in either dict, | ||||
# since they won't be affected by the push. | ||||
# unsynced contains all branches with incoming changesets. | ||||
oldmap = {} | ||||
newmap = {} | ||||
unsynced = set() | ||||
for branch in branches: | ||||
|
r11577 | remotebrheads = remotemap[branch] | ||
prunedbrheads = [h for h in remotebrheads if h in cl.nodemap] | ||||
oldmap[branch] = prunedbrheads | ||||
newmap[branch] = list(prunedbrheads) | ||||
if len(remotebrheads) > len(prunedbrheads): | ||||
|
r11301 | unsynced.add(branch) | ||
# 4. Update newmap with outgoing changes. | ||||
# This will possibly add new heads and remove existing ones. | ||||
ctxgen = (repo[n] for n in outg) | ||||
repo._updatebranchcache(newmap, ctxgen) | ||||
else: | ||||
|
r11578 | # 1-4b. old servers: Check for new topological heads. | ||
# Construct {old,new}map with branch = None (topological branch). | ||||
# (code based on _updatebranchcache) | ||||
oldheads = set(h for h in remoteheads if h in cl.nodemap) | ||||
newheads = oldheads.union(outg) | ||||
|
r11301 | if len(newheads) > 1: | ||
for latest in reversed(outg): | ||||
if latest not in newheads: | ||||
continue | ||||
minhrev = min(cl.rev(h) for h in newheads) | ||||
reachable = cl.reachable(latest, cl.node(minhrev)) | ||||
reachable.remove(latest) | ||||
newheads.difference_update(reachable) | ||||
|
r11578 | branches = set([None]) | ||
newmap = {None: newheads} | ||||
oldmap = {None: oldheads} | ||||
unsynced = inc and branches or set() | ||||
# 5. Check for new heads. | ||||
# If there are more heads after the push than before, a suitable | ||||
# warning, depending on unsynced status, is displayed. | ||||
for branch in branches: | ||||
if len(newmap[branch]) > len(oldmap[branch]): | ||||
if branch: | ||||
msg = _("push creates new remote heads " | ||||
"on branch '%s'!") % branch | ||||
else: | ||||
msg = _("push creates new remote heads!") | ||||
if branch in unsynced: | ||||
hint = _("you should pull and merge or use push -f to force") | ||||
else: | ||||
hint = _("did you forget to merge? use push -f to force") | ||||
raise util.Abort(msg, hint=hint) | ||||
# 6. Check for unsynced changes on involved branches. | ||||
if unsynced: | ||||
repo.ui.warn(_("note: unsynced remote changes!\n")) | ||||
|
r11301 | |||
if revs is None: | ||||
# use the fast path, no race possible on push | ||||
|
r12759 | nodes = repo.changelog.findmissing(common) | ||
|
r11301 | cg = repo._changegroup(nodes, 'push') | ||
else: | ||||
cg = repo.changegroupsubset(update, revs, 'push') | ||||
|
r11577 | return cg, remoteheads | ||