##// END OF EJS Templates
setdiscovery: drop shadowed 'undecided' assignment...
Pierre-Yves David -
r23746:4ef2f2fa default
parent child Browse files
Show More
@@ -1,249 +1,248 b''
1 # setdiscovery.py - improved discovery of common nodeset for mercurial
1 # setdiscovery.py - improved discovery of common nodeset for mercurial
2 #
2 #
3 # Copyright 2010 Benoit Boissinot <bboissin@gmail.com>
3 # Copyright 2010 Benoit Boissinot <bboissin@gmail.com>
4 # and Peter Arrenbrecht <peter@arrenbrecht.ch>
4 # and Peter Arrenbrecht <peter@arrenbrecht.ch>
5 #
5 #
6 # This software may be used and distributed according to the terms of the
6 # This software may be used and distributed according to the terms of the
7 # GNU General Public License version 2 or any later version.
7 # GNU General Public License version 2 or any later version.
8 """
8 """
9 Algorithm works in the following way. You have two repository: local and
9 Algorithm works in the following way. You have two repository: local and
10 remote. They both contains a DAG of changelists.
10 remote. They both contains a DAG of changelists.
11
11
12 The goal of the discovery protocol is to find one set of node *common*,
12 The goal of the discovery protocol is to find one set of node *common*,
13 the set of nodes shared by local and remote.
13 the set of nodes shared by local and remote.
14
14
15 One of the issue with the original protocol was latency, it could
15 One of the issue with the original protocol was latency, it could
16 potentially require lots of roundtrips to discover that the local repo was a
16 potentially require lots of roundtrips to discover that the local repo was a
17 subset of remote (which is a very common case, you usually have few changes
17 subset of remote (which is a very common case, you usually have few changes
18 compared to upstream, while upstream probably had lots of development).
18 compared to upstream, while upstream probably had lots of development).
19
19
20 The new protocol only requires one interface for the remote repo: `known()`,
20 The new protocol only requires one interface for the remote repo: `known()`,
21 which given a set of changelists tells you if they are present in the DAG.
21 which given a set of changelists tells you if they are present in the DAG.
22
22
23 The algorithm then works as follow:
23 The algorithm then works as follow:
24
24
25 - We will be using three sets, `common`, `missing`, `unknown`. Originally
25 - We will be using three sets, `common`, `missing`, `unknown`. Originally
26 all nodes are in `unknown`.
26 all nodes are in `unknown`.
27 - Take a sample from `unknown`, call `remote.known(sample)`
27 - Take a sample from `unknown`, call `remote.known(sample)`
28 - For each node that remote knows, move it and all its ancestors to `common`
28 - For each node that remote knows, move it and all its ancestors to `common`
29 - For each node that remote doesn't know, move it and all its descendants
29 - For each node that remote doesn't know, move it and all its descendants
30 to `missing`
30 to `missing`
31 - Iterate until `unknown` is empty
31 - Iterate until `unknown` is empty
32
32
33 There are a couple optimizations, first is instead of starting with a random
33 There are a couple optimizations, first is instead of starting with a random
34 sample of missing, start by sending all heads, in the case where the local
34 sample of missing, start by sending all heads, in the case where the local
35 repo is a subset, you computed the answer in one round trip.
35 repo is a subset, you computed the answer in one round trip.
36
36
37 Then you can do something similar to the bisecting strategy used when
37 Then you can do something similar to the bisecting strategy used when
38 finding faulty changesets. Instead of random samples, you can try picking
38 finding faulty changesets. Instead of random samples, you can try picking
39 nodes that will maximize the number of nodes that will be
39 nodes that will maximize the number of nodes that will be
40 classified with it (since all ancestors or descendants will be marked as well).
40 classified with it (since all ancestors or descendants will be marked as well).
41 """
41 """
42
42
43 from node import nullid, nullrev
43 from node import nullid, nullrev
44 from i18n import _
44 from i18n import _
45 import random
45 import random
46 import util, dagutil
46 import util, dagutil
47
47
48 def _updatesample(dag, nodes, sample, always, quicksamplesize=0):
48 def _updatesample(dag, nodes, sample, always, quicksamplesize=0):
49 # if nodes is empty we scan the entire graph
49 # if nodes is empty we scan the entire graph
50 if nodes:
50 if nodes:
51 heads = dag.headsetofconnecteds(nodes)
51 heads = dag.headsetofconnecteds(nodes)
52 else:
52 else:
53 heads = dag.heads()
53 heads = dag.heads()
54 dist = {}
54 dist = {}
55 visit = util.deque(heads)
55 visit = util.deque(heads)
56 seen = set()
56 seen = set()
57 factor = 1
57 factor = 1
58 while visit:
58 while visit:
59 curr = visit.popleft()
59 curr = visit.popleft()
60 if curr in seen:
60 if curr in seen:
61 continue
61 continue
62 d = dist.setdefault(curr, 1)
62 d = dist.setdefault(curr, 1)
63 if d > factor:
63 if d > factor:
64 factor *= 2
64 factor *= 2
65 if d == factor:
65 if d == factor:
66 if curr not in always: # need this check for the early exit below
66 if curr not in always: # need this check for the early exit below
67 sample.add(curr)
67 sample.add(curr)
68 if quicksamplesize and (len(sample) >= quicksamplesize):
68 if quicksamplesize and (len(sample) >= quicksamplesize):
69 return
69 return
70 seen.add(curr)
70 seen.add(curr)
71 for p in dag.parents(curr):
71 for p in dag.parents(curr):
72 if not nodes or p in nodes:
72 if not nodes or p in nodes:
73 dist.setdefault(p, d + 1)
73 dist.setdefault(p, d + 1)
74 visit.append(p)
74 visit.append(p)
75
75
76 def _setupsample(dag, nodes, size):
76 def _setupsample(dag, nodes, size):
77 if len(nodes) <= size:
77 if len(nodes) <= size:
78 return set(nodes), None, 0
78 return set(nodes), None, 0
79 always = dag.headsetofconnecteds(nodes)
79 always = dag.headsetofconnecteds(nodes)
80 desiredlen = size - len(always)
80 desiredlen = size - len(always)
81 if desiredlen <= 0:
81 if desiredlen <= 0:
82 # This could be bad if there are very many heads, all unknown to the
82 # This could be bad if there are very many heads, all unknown to the
83 # server. We're counting on long request support here.
83 # server. We're counting on long request support here.
84 return always, None, desiredlen
84 return always, None, desiredlen
85 return always, set(), desiredlen
85 return always, set(), desiredlen
86
86
87 def _takequicksample(dag, nodes, size, initial):
87 def _takequicksample(dag, nodes, size, initial):
88 always, sample, desiredlen = _setupsample(dag, nodes, size)
88 always, sample, desiredlen = _setupsample(dag, nodes, size)
89 if sample is None:
89 if sample is None:
90 return always
90 return always
91 if initial:
91 if initial:
92 fromset = None
92 fromset = None
93 else:
93 else:
94 fromset = nodes
94 fromset = nodes
95 _updatesample(dag, fromset, sample, always, quicksamplesize=desiredlen)
95 _updatesample(dag, fromset, sample, always, quicksamplesize=desiredlen)
96 sample.update(always)
96 sample.update(always)
97 return sample
97 return sample
98
98
99 def _takefullsample(dag, nodes, size):
99 def _takefullsample(dag, nodes, size):
100 always, sample, desiredlen = _setupsample(dag, nodes, size)
100 always, sample, desiredlen = _setupsample(dag, nodes, size)
101 if sample is None:
101 if sample is None:
102 return always
102 return always
103 # update from heads
103 # update from heads
104 _updatesample(dag, nodes, sample, always)
104 _updatesample(dag, nodes, sample, always)
105 # update from roots
105 # update from roots
106 _updatesample(dag.inverse(), nodes, sample, always)
106 _updatesample(dag.inverse(), nodes, sample, always)
107 assert sample
107 assert sample
108 sample = _limitsample(sample, desiredlen)
108 sample = _limitsample(sample, desiredlen)
109 if len(sample) < desiredlen:
109 if len(sample) < desiredlen:
110 more = desiredlen - len(sample)
110 more = desiredlen - len(sample)
111 sample.update(random.sample(list(nodes - sample - always), more))
111 sample.update(random.sample(list(nodes - sample - always), more))
112 sample.update(always)
112 sample.update(always)
113 return sample
113 return sample
114
114
115 def _limitsample(sample, desiredlen):
115 def _limitsample(sample, desiredlen):
116 """return a random subset of sample of at most desiredlen item"""
116 """return a random subset of sample of at most desiredlen item"""
117 if len(sample) > desiredlen:
117 if len(sample) > desiredlen:
118 sample = set(random.sample(sample, desiredlen))
118 sample = set(random.sample(sample, desiredlen))
119 return sample
119 return sample
120
120
121 def findcommonheads(ui, local, remote,
121 def findcommonheads(ui, local, remote,
122 initialsamplesize=100,
122 initialsamplesize=100,
123 fullsamplesize=200,
123 fullsamplesize=200,
124 abortwhenunrelated=True):
124 abortwhenunrelated=True):
125 '''Return a tuple (common, anyincoming, remoteheads) used to identify
125 '''Return a tuple (common, anyincoming, remoteheads) used to identify
126 missing nodes from or in remote.
126 missing nodes from or in remote.
127 '''
127 '''
128 roundtrips = 0
128 roundtrips = 0
129 cl = local.changelog
129 cl = local.changelog
130 dag = dagutil.revlogdag(cl)
130 dag = dagutil.revlogdag(cl)
131
131
132 # early exit if we know all the specified remote heads already
132 # early exit if we know all the specified remote heads already
133 ui.debug("query 1; heads\n")
133 ui.debug("query 1; heads\n")
134 roundtrips += 1
134 roundtrips += 1
135 ownheads = dag.heads()
135 ownheads = dag.heads()
136 sample = _limitsample(ownheads, initialsamplesize)
136 sample = _limitsample(ownheads, initialsamplesize)
137 # indices between sample and externalized version must match
137 # indices between sample and externalized version must match
138 sample = list(sample)
138 sample = list(sample)
139 if remote.local():
139 if remote.local():
140 # stopgap until we have a proper localpeer that supports batch()
140 # stopgap until we have a proper localpeer that supports batch()
141 srvheadhashes = remote.heads()
141 srvheadhashes = remote.heads()
142 yesno = remote.known(dag.externalizeall(sample))
142 yesno = remote.known(dag.externalizeall(sample))
143 elif remote.capable('batch'):
143 elif remote.capable('batch'):
144 batch = remote.batch()
144 batch = remote.batch()
145 srvheadhashesref = batch.heads()
145 srvheadhashesref = batch.heads()
146 yesnoref = batch.known(dag.externalizeall(sample))
146 yesnoref = batch.known(dag.externalizeall(sample))
147 batch.submit()
147 batch.submit()
148 srvheadhashes = srvheadhashesref.value
148 srvheadhashes = srvheadhashesref.value
149 yesno = yesnoref.value
149 yesno = yesnoref.value
150 else:
150 else:
151 # compatibility with pre-batch, but post-known remotes during 1.9
151 # compatibility with pre-batch, but post-known remotes during 1.9
152 # development
152 # development
153 srvheadhashes = remote.heads()
153 srvheadhashes = remote.heads()
154 sample = []
154 sample = []
155
155
156 if cl.tip() == nullid:
156 if cl.tip() == nullid:
157 if srvheadhashes != [nullid]:
157 if srvheadhashes != [nullid]:
158 return [nullid], True, srvheadhashes
158 return [nullid], True, srvheadhashes
159 return [nullid], False, []
159 return [nullid], False, []
160
160
161 # start actual discovery (we note this before the next "if" for
161 # start actual discovery (we note this before the next "if" for
162 # compatibility reasons)
162 # compatibility reasons)
163 ui.status(_("searching for changes\n"))
163 ui.status(_("searching for changes\n"))
164
164
165 srvheads = dag.internalizeall(srvheadhashes, filterunknown=True)
165 srvheads = dag.internalizeall(srvheadhashes, filterunknown=True)
166 if len(srvheads) == len(srvheadhashes):
166 if len(srvheads) == len(srvheadhashes):
167 ui.debug("all remote heads known locally\n")
167 ui.debug("all remote heads known locally\n")
168 return (srvheadhashes, False, srvheadhashes,)
168 return (srvheadhashes, False, srvheadhashes,)
169
169
170 if sample and len(ownheads) <= initialsamplesize and util.all(yesno):
170 if sample and len(ownheads) <= initialsamplesize and util.all(yesno):
171 ui.note(_("all local heads known remotely\n"))
171 ui.note(_("all local heads known remotely\n"))
172 ownheadhashes = dag.externalizeall(ownheads)
172 ownheadhashes = dag.externalizeall(ownheads)
173 return (ownheadhashes, True, srvheadhashes,)
173 return (ownheadhashes, True, srvheadhashes,)
174
174
175 # full blown discovery
175 # full blown discovery
176
176
177 # own nodes where I don't know if remote knows them
178 undecided = dag.nodeset()
179 # own nodes I know we both know
177 # own nodes I know we both know
180 # treat remote heads (and maybe own heads) as a first implicit sample
178 # treat remote heads (and maybe own heads) as a first implicit sample
181 # response
179 # response
182 common = cl.incrementalmissingrevs(srvheads)
180 common = cl.incrementalmissingrevs(srvheads)
183 commoninsample = set(n for i, n in enumerate(sample) if yesno[i])
181 commoninsample = set(n for i, n in enumerate(sample) if yesno[i])
184 common.addbases(commoninsample)
182 common.addbases(commoninsample)
183 # own nodes where I don't know if remote knows them
185 undecided = set(common.missingancestors(ownheads))
184 undecided = set(common.missingancestors(ownheads))
186 # own nodes I know remote lacks
185 # own nodes I know remote lacks
187 missing = set()
186 missing = set()
188
187
189 full = False
188 full = False
190 while undecided:
189 while undecided:
191
190
192 if sample:
191 if sample:
193 missinginsample = [n for i, n in enumerate(sample) if not yesno[i]]
192 missinginsample = [n for i, n in enumerate(sample) if not yesno[i]]
194 missing.update(dag.descendantset(missinginsample, missing))
193 missing.update(dag.descendantset(missinginsample, missing))
195
194
196 undecided.difference_update(missing)
195 undecided.difference_update(missing)
197
196
198 if not undecided:
197 if not undecided:
199 break
198 break
200
199
201 if full:
200 if full:
202 ui.note(_("sampling from both directions\n"))
201 ui.note(_("sampling from both directions\n"))
203 sample = _takefullsample(dag, undecided, size=fullsamplesize)
202 sample = _takefullsample(dag, undecided, size=fullsamplesize)
204 targetsize = fullsamplesize
203 targetsize = fullsamplesize
205 elif common.hasbases():
204 elif common.hasbases():
206 # use cheapish initial sample
205 # use cheapish initial sample
207 ui.debug("taking initial sample\n")
206 ui.debug("taking initial sample\n")
208 sample = _takefullsample(dag, undecided, size=fullsamplesize)
207 sample = _takefullsample(dag, undecided, size=fullsamplesize)
209 targetsize = fullsamplesize
208 targetsize = fullsamplesize
210 else:
209 else:
211 # use even cheaper initial sample
210 # use even cheaper initial sample
212 ui.debug("taking quick initial sample\n")
211 ui.debug("taking quick initial sample\n")
213 sample = _takequicksample(dag, undecided, size=initialsamplesize,
212 sample = _takequicksample(dag, undecided, size=initialsamplesize,
214 initial=True)
213 initial=True)
215 targetsize = initialsamplesize
214 targetsize = initialsamplesize
216 sample = _limitsample(sample, targetsize)
215 sample = _limitsample(sample, targetsize)
217
216
218 roundtrips += 1
217 roundtrips += 1
219 ui.progress(_('searching'), roundtrips, unit=_('queries'))
218 ui.progress(_('searching'), roundtrips, unit=_('queries'))
220 ui.debug("query %i; still undecided: %i, sample size is: %i\n"
219 ui.debug("query %i; still undecided: %i, sample size is: %i\n"
221 % (roundtrips, len(undecided), len(sample)))
220 % (roundtrips, len(undecided), len(sample)))
222 # indices between sample and externalized version must match
221 # indices between sample and externalized version must match
223 sample = list(sample)
222 sample = list(sample)
224 yesno = remote.known(dag.externalizeall(sample))
223 yesno = remote.known(dag.externalizeall(sample))
225 full = True
224 full = True
226
225
227 if sample:
226 if sample:
228 commoninsample = set(n for i, n in enumerate(sample) if yesno[i])
227 commoninsample = set(n for i, n in enumerate(sample) if yesno[i])
229 common.addbases(commoninsample)
228 common.addbases(commoninsample)
230 common.removeancestorsfrom(undecided)
229 common.removeancestorsfrom(undecided)
231
230
232 # heads(common) == heads(common.bases) since common represents common.bases
231 # heads(common) == heads(common.bases) since common represents common.bases
233 # and all its ancestors
232 # and all its ancestors
234 result = dag.headsetofconnecteds(common.bases)
233 result = dag.headsetofconnecteds(common.bases)
235 # common.bases can include nullrev, but our contract requires us to not
234 # common.bases can include nullrev, but our contract requires us to not
236 # return any heads in that case, so discard that
235 # return any heads in that case, so discard that
237 result.discard(nullrev)
236 result.discard(nullrev)
238 ui.progress(_('searching'), None)
237 ui.progress(_('searching'), None)
239 ui.debug("%d total queries\n" % roundtrips)
238 ui.debug("%d total queries\n" % roundtrips)
240
239
241 if not result and srvheadhashes != [nullid]:
240 if not result and srvheadhashes != [nullid]:
242 if abortwhenunrelated:
241 if abortwhenunrelated:
243 raise util.Abort(_("repository is unrelated"))
242 raise util.Abort(_("repository is unrelated"))
244 else:
243 else:
245 ui.warn(_("warning: repository is unrelated\n"))
244 ui.warn(_("warning: repository is unrelated\n"))
246 return (set([nullid]), True, srvheadhashes,)
245 return (set([nullid]), True, srvheadhashes,)
247
246
248 anyincoming = (srvheadhashes != [nullid])
247 anyincoming = (srvheadhashes != [nullid])
249 return dag.externalizeall(result), anyincoming, srvheadhashes
248 return dag.externalizeall(result), anyincoming, srvheadhashes
General Comments 0
You need to be logged in to leave comments. Login now