|
1 # discovery.py - protocol changeset discovery functions |
|
2 # |
|
3 # Copyright 2010 Matt Mackall <mpm@selenic.com> |
|
4 # |
|
5 # This software may be used and distributed according to the terms of the |
|
6 # GNU General Public License version 2 or any later version. |
|
7 |
|
8 from node import nullid, short |
|
9 from i18n import _ |
|
10 import util, error |
|
11 |
|
12 def findcommonincoming(repo, remote, heads=None, force=False): |
|
13 """Return a tuple (common, missing roots, heads) used to identify |
|
14 missing nodes from remote. |
|
15 |
|
16 If a list of heads is specified, return only nodes which are heads |
|
17 or ancestors of these heads. |
|
18 """ |
|
19 m = repo.changelog.nodemap |
|
20 search = [] |
|
21 fetch = set() |
|
22 seen = set() |
|
23 seenbranch = set() |
|
24 base = set() |
|
25 |
|
26 if not heads: |
|
27 heads = remote.heads() |
|
28 |
|
29 if repo.changelog.tip() == nullid: |
|
30 base.add(nullid) |
|
31 if heads != [nullid]: |
|
32 return [nullid], [nullid], list(heads) |
|
33 return [nullid], [], [] |
|
34 |
|
35 # assume we're closer to the tip than the root |
|
36 # and start by examining the heads |
|
37 repo.ui.status(_("searching for changes\n")) |
|
38 |
|
39 unknown = [] |
|
40 for h in heads: |
|
41 if h not in m: |
|
42 unknown.append(h) |
|
43 else: |
|
44 base.add(h) |
|
45 |
|
46 heads = unknown |
|
47 if not unknown: |
|
48 return list(base), [], [] |
|
49 |
|
50 req = set(unknown) |
|
51 reqcnt = 0 |
|
52 |
|
53 # search through remote branches |
|
54 # a 'branch' here is a linear segment of history, with four parts: |
|
55 # head, root, first parent, second parent |
|
56 # (a branch always has two parents (or none) by definition) |
|
57 unknown = remote.branches(unknown) |
|
58 while unknown: |
|
59 r = [] |
|
60 while unknown: |
|
61 n = unknown.pop(0) |
|
62 if n[0] in seen: |
|
63 continue |
|
64 |
|
65 repo.ui.debug("examining %s:%s\n" |
|
66 % (short(n[0]), short(n[1]))) |
|
67 if n[0] == nullid: # found the end of the branch |
|
68 pass |
|
69 elif n in seenbranch: |
|
70 repo.ui.debug("branch already found\n") |
|
71 continue |
|
72 elif n[1] and n[1] in m: # do we know the base? |
|
73 repo.ui.debug("found incomplete branch %s:%s\n" |
|
74 % (short(n[0]), short(n[1]))) |
|
75 search.append(n[0:2]) # schedule branch range for scanning |
|
76 seenbranch.add(n) |
|
77 else: |
|
78 if n[1] not in seen and n[1] not in fetch: |
|
79 if n[2] in m and n[3] in m: |
|
80 repo.ui.debug("found new changeset %s\n" % |
|
81 short(n[1])) |
|
82 fetch.add(n[1]) # earliest unknown |
|
83 for p in n[2:4]: |
|
84 if p in m: |
|
85 base.add(p) # latest known |
|
86 |
|
87 for p in n[2:4]: |
|
88 if p not in req and p not in m: |
|
89 r.append(p) |
|
90 req.add(p) |
|
91 seen.add(n[0]) |
|
92 |
|
93 if r: |
|
94 reqcnt += 1 |
|
95 repo.ui.progress(_('searching'), reqcnt, unit=_('queries')) |
|
96 repo.ui.debug("request %d: %s\n" % |
|
97 (reqcnt, " ".join(map(short, r)))) |
|
98 for p in xrange(0, len(r), 10): |
|
99 for b in remote.branches(r[p:p + 10]): |
|
100 repo.ui.debug("received %s:%s\n" % |
|
101 (short(b[0]), short(b[1]))) |
|
102 unknown.append(b) |
|
103 |
|
104 # do binary search on the branches we found |
|
105 while search: |
|
106 newsearch = [] |
|
107 reqcnt += 1 |
|
108 repo.ui.progress(_('searching'), reqcnt, unit=_('queries')) |
|
109 for n, l in zip(search, remote.between(search)): |
|
110 l.append(n[1]) |
|
111 p = n[0] |
|
112 f = 1 |
|
113 for i in l: |
|
114 repo.ui.debug("narrowing %d:%d %s\n" % (f, len(l), short(i))) |
|
115 if i in m: |
|
116 if f <= 2: |
|
117 repo.ui.debug("found new branch changeset %s\n" % |
|
118 short(p)) |
|
119 fetch.add(p) |
|
120 base.add(i) |
|
121 else: |
|
122 repo.ui.debug("narrowed branch search to %s:%s\n" |
|
123 % (short(p), short(i))) |
|
124 newsearch.append((p, i)) |
|
125 break |
|
126 p, f = i, f * 2 |
|
127 search = newsearch |
|
128 |
|
129 # sanity check our fetch list |
|
130 for f in fetch: |
|
131 if f in m: |
|
132 raise error.RepoError(_("already have changeset ") |
|
133 + short(f[:4])) |
|
134 |
|
135 base = list(base) |
|
136 if base == [nullid]: |
|
137 if force: |
|
138 repo.ui.warn(_("warning: repository is unrelated\n")) |
|
139 else: |
|
140 raise util.Abort(_("repository is unrelated")) |
|
141 |
|
142 repo.ui.debug("found new changesets starting at " + |
|
143 " ".join([short(f) for f in fetch]) + "\n") |
|
144 |
|
145 repo.ui.progress(_('searching'), None) |
|
146 repo.ui.debug("%d total queries\n" % reqcnt) |
|
147 |
|
148 return base, list(fetch), heads |
|
149 |
|
150 def findoutgoing(repo, remote, base=None, remoteheads=None, force=False): |
|
151 """Return list of nodes that are roots of subsets not in remote |
|
152 |
|
153 If base dict is specified, assume that these nodes and their parents |
|
154 exist on the remote side. |
|
155 If remotehead is specified, assume it is the list of the heads from |
|
156 the remote repository. |
|
157 """ |
|
158 if base is None: |
|
159 base = findcommonincoming(repo, remote, heads=remoteheads, |
|
160 force=force)[0] |
|
161 else: |
|
162 base = list(base) |
|
163 |
|
164 repo.ui.debug("common changesets up to " |
|
165 + " ".join(map(short, base)) + "\n") |
|
166 |
|
167 remain = set(repo.changelog.nodemap) |
|
168 |
|
169 # prune everything remote has from the tree |
|
170 remain.remove(nullid) |
|
171 remove = base |
|
172 while remove: |
|
173 n = remove.pop(0) |
|
174 if n in remain: |
|
175 remain.remove(n) |
|
176 for p in repo.changelog.parents(n): |
|
177 remove.append(p) |
|
178 |
|
179 # find every node whose parents have been pruned |
|
180 subset = [] |
|
181 # find every remote head that will get new children |
|
182 for n in remain: |
|
183 p1, p2 = repo.changelog.parents(n) |
|
184 if p1 not in remain and p2 not in remain: |
|
185 subset.append(n) |
|
186 |
|
187 return subset |
|
188 |
|
189 def prepush(repo, remote, force, revs, newbranch): |
|
190 '''Analyze the local and remote repositories and determine which |
|
191 changesets need to be pushed to the remote. Return value depends |
|
192 on circumstances: |
|
193 |
|
194 If we are not going to push anything, return a tuple (None, |
|
195 outgoing) where outgoing is 0 if there are no outgoing |
|
196 changesets and 1 if there are, but we refuse to push them |
|
197 (e.g. would create new remote heads). |
|
198 |
|
199 Otherwise, return a tuple (changegroup, remoteheads), where |
|
200 changegroup is a readable file-like object whose read() returns |
|
201 successive changegroup chunks ready to be sent over the wire and |
|
202 remoteheads is the list of remote heads.''' |
|
203 remoteheads = remote.heads() |
|
204 common, inc, rheads = findcommonincoming(repo, remote, heads=remoteheads, |
|
205 force=force) |
|
206 |
|
207 cl = repo.changelog |
|
208 update = findoutgoing(repo, remote, common, remoteheads) |
|
209 outg, bases, heads = cl.nodesbetween(update, revs) |
|
210 |
|
211 if not bases: |
|
212 repo.ui.status(_("no changes found\n")) |
|
213 return None, 1 |
|
214 |
|
215 if not force and remoteheads != [nullid]: |
|
216 if remote.capable('branchmap'): |
|
217 # Check for each named branch if we're creating new remote heads. |
|
218 # To be a remote head after push, node must be either: |
|
219 # - unknown locally |
|
220 # - a local outgoing head descended from update |
|
221 # - a remote head that's known locally and not |
|
222 # ancestral to an outgoing head |
|
223 # |
|
224 # New named branches cannot be created without --force. |
|
225 |
|
226 # 1. Create set of branches involved in the push. |
|
227 branches = set(repo[n].branch() for n in outg) |
|
228 |
|
229 # 2. Check for new branches on the remote. |
|
230 remotemap = remote.branchmap() |
|
231 newbranches = branches - set(remotemap) |
|
232 if newbranches and not newbranch: # new branch requires --new-branch |
|
233 branchnames = ', '.join(sorted(newbranches)) |
|
234 raise util.Abort(_("push creates new remote branches: %s!") |
|
235 % branchnames, |
|
236 hint=_("use 'hg push --new-branch' to create" |
|
237 " new remote branches")) |
|
238 branches.difference_update(newbranches) |
|
239 |
|
240 # 3. Construct the initial oldmap and newmap dicts. |
|
241 # They contain information about the remote heads before and |
|
242 # after the push, respectively. |
|
243 # Heads not found locally are not included in either dict, |
|
244 # since they won't be affected by the push. |
|
245 # unsynced contains all branches with incoming changesets. |
|
246 oldmap = {} |
|
247 newmap = {} |
|
248 unsynced = set() |
|
249 for branch in branches: |
|
250 remotebrheads = remotemap[branch] |
|
251 prunedbrheads = [h for h in remotebrheads if h in cl.nodemap] |
|
252 oldmap[branch] = prunedbrheads |
|
253 newmap[branch] = list(prunedbrheads) |
|
254 if len(remotebrheads) > len(prunedbrheads): |
|
255 unsynced.add(branch) |
|
256 |
|
257 # 4. Update newmap with outgoing changes. |
|
258 # This will possibly add new heads and remove existing ones. |
|
259 ctxgen = (repo[n] for n in outg) |
|
260 repo._updatebranchcache(newmap, ctxgen) |
|
261 |
|
262 else: |
|
263 # 1-4b. old servers: Check for new topological heads. |
|
264 # Construct {old,new}map with branch = None (topological branch). |
|
265 # (code based on _updatebranchcache) |
|
266 oldheads = set(h for h in remoteheads if h in cl.nodemap) |
|
267 newheads = oldheads.union(outg) |
|
268 if len(newheads) > 1: |
|
269 for latest in reversed(outg): |
|
270 if latest not in newheads: |
|
271 continue |
|
272 minhrev = min(cl.rev(h) for h in newheads) |
|
273 reachable = cl.reachable(latest, cl.node(minhrev)) |
|
274 reachable.remove(latest) |
|
275 newheads.difference_update(reachable) |
|
276 branches = set([None]) |
|
277 newmap = {None: newheads} |
|
278 oldmap = {None: oldheads} |
|
279 unsynced = inc and branches or set() |
|
280 |
|
281 # 5. Check for new heads. |
|
282 # If there are more heads after the push than before, a suitable |
|
283 # warning, depending on unsynced status, is displayed. |
|
284 for branch in branches: |
|
285 if len(newmap[branch]) > len(oldmap[branch]): |
|
286 if branch: |
|
287 msg = _("push creates new remote heads " |
|
288 "on branch '%s'!") % branch |
|
289 else: |
|
290 msg = _("push creates new remote heads!") |
|
291 |
|
292 if branch in unsynced: |
|
293 hint = _("you should pull and merge or use push -f to force") |
|
294 else: |
|
295 hint = _("did you forget to merge? use push -f to force") |
|
296 raise util.Abort(msg, hint=hint) |
|
297 |
|
298 # 6. Check for unsynced changes on involved branches. |
|
299 if unsynced: |
|
300 repo.ui.warn(_("note: unsynced remote changes!\n")) |
|
301 |
|
302 if revs is None: |
|
303 # use the fast path, no race possible on push |
|
304 nodes = repo.changelog.findmissing(common) |
|
305 cg = repo._changegroup(nodes, 'push') |
|
306 else: |
|
307 cg = repo.changegroupsubset(update, revs, 'push') |
|
308 return cg, remoteheads |