188
158
if anc_id not in found_ancestors:
189
159
found_ancestors[anc_id] = (anc_order, anc_distance)
190
160
return found_ancestors
193
163
def __get_closest(intersection):
194
164
intersection.sort()
196
166
for entry in intersection:
197
167
if entry[0] == intersection[0][0]:
198
168
matches.append(entry[2])
172
def revision_graph(revision, revision_source):
173
"""Produce a graph of the ancestry of the specified revision.
175
:return: root, ancestors map, descendants map
177
revision_source.lock_read()
179
return _revision_graph(revision, revision_source)
181
revision_source.unlock()
184
def _revision_graph(revision, revision_source):
185
"""See revision_graph."""
186
from bzrlib.tsort import topo_sort
187
graph = revision_source.get_revision_graph(revision)
188
# mark all no-parent revisions as being NULL_REVISION parentage.
189
for node, parents in graph.items():
190
if len(parents) == 0:
191
graph[node] = [NULL_REVISION]
192
# add NULL_REVISION to the graph
193
graph[NULL_REVISION] = []
195
# pick a root. If there are multiple roots
196
# this could pick a random one.
197
topo_order = topo_sort(graph.items())
203
# map the descendants of the graph.
204
# and setup our set based return graph.
205
for node in graph.keys():
206
descendants[node] = {}
207
for node, parents in graph.items():
208
for parent in parents:
209
descendants[parent][node] = 1
210
ancestors[node] = set(parents)
212
assert root not in descendants[root]
213
assert root not in ancestors[root]
214
return root, ancestors, descendants
217
def combined_graph(revision_a, revision_b, revision_source):
218
"""Produce a combined ancestry graph.
219
Return graph root, ancestors map, descendants map, set of common nodes"""
220
root, ancestors, descendants = revision_graph(
221
revision_a, revision_source)
222
root_b, ancestors_b, descendants_b = revision_graph(
223
revision_b, revision_source)
225
raise errors.NoCommonRoot(revision_a, revision_b)
227
for node, node_anc in ancestors_b.iteritems():
228
if node in ancestors:
231
ancestors[node] = set()
232
ancestors[node].update(node_anc)
233
for node, node_dec in descendants_b.iteritems():
234
if node not in descendants:
235
descendants[node] = {}
236
descendants[node].update(node_dec)
237
return root, ancestors, descendants, common
240
def common_ancestor(revision_a, revision_b, revision_source,
242
if None in (revision_a, revision_b):
244
if NULL_REVISION in (revision_a, revision_b):
246
# trivial optimisation
247
if revision_a == revision_b:
251
pb.update('Picking ancestor', 1, 3)
252
graph = revision_source.get_revision_graph_with_ghosts(
253
[revision_a, revision_b])
254
# convert to a NULL_REVISION based graph.
255
ancestors = graph.get_ancestors()
256
descendants = graph.get_descendants()
257
common = set(graph.get_ancestry(revision_a)).intersection(
258
set(graph.get_ancestry(revision_b)))
259
descendants[NULL_REVISION] = {}
260
ancestors[NULL_REVISION] = []
261
for root in graph.roots:
262
descendants[NULL_REVISION][root] = 1
263
ancestors[root].append(NULL_REVISION)
264
for ghost in graph.ghosts:
265
# ghosts act as roots for the purpose of finding
266
# the longest paths from the root: any ghost *might*
267
# be directly attached to the root, so we treat them
269
# ghost now descends from NULL
270
descendants[NULL_REVISION][ghost] = 1
271
# that is it has an ancestor of NULL
272
ancestors[ghost] = [NULL_REVISION]
273
# ghost is common if any of ghosts descendants are common:
274
for ghost_descendant in descendants[ghost]:
275
if ghost_descendant in common:
279
common.add(NULL_REVISION)
280
except errors.NoCommonRoot:
281
raise errors.NoCommonAncestor(revision_a, revision_b)
283
pb.update('Picking ancestor', 2, 3)
284
distances = node_distances (descendants, ancestors, root)
285
pb.update('Picking ancestor', 3, 2)
286
farthest = select_farthest(distances, common)
287
if farthest is None or farthest == NULL_REVISION:
288
raise errors.NoCommonAncestor(revision_a, revision_b)
294
class MultipleRevisionSources(object):
295
"""Proxy that looks in multiple branches for revisions."""
296
def __init__(self, *args):
297
object.__init__(self)
298
assert len(args) != 0
299
self._revision_sources = args
301
def revision_parents(self, revision_id):
302
for source in self._revision_sources:
304
return source.revision_parents(revision_id)
305
except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
309
def get_revision(self, revision_id):
310
for source in self._revision_sources:
312
return source.get_revision(revision_id)
313
except errors.NoSuchRevision, e:
317
def get_revision_graph(self, revision_id):
318
# we could probe incrementally until the pending
319
# ghosts list stop growing, but its cheaper for now
320
# to just ask for the complete graph for each repository.
322
for source in self._revision_sources:
323
ghost_graph = source.get_revision_graph_with_ghosts()
324
graphs.append(ghost_graph)
327
if not revision_id in graph.get_ancestors():
329
if absent == len(graphs):
330
raise errors.NoSuchRevision(self._revision_sources[0], revision_id)
334
pending = set([revision_id])
335
def find_parents(node_id):
336
"""find the parents for node_id."""
338
ancestors = graph.get_ancestors()
340
return ancestors[node_id]
343
raise errors.NoSuchRevision(self._revision_sources[0], node_id)
345
# all the graphs should have identical parent lists
346
node_id = pending.pop()
348
result[node_id] = find_parents(node_id)
349
for parent_node in result[node_id]:
350
if not parent_node in result:
351
pending.add(parent_node)
352
except errors.NoSuchRevision:
357
def get_revision_graph_with_ghosts(self, revision_ids):
358
# query all the sources for their entire graphs
359
# and then build a combined graph for just
362
for source in self._revision_sources:
363
ghost_graph = source.get_revision_graph_with_ghosts()
364
graphs.append(ghost_graph.get_ancestors())
365
for revision_id in revision_ids:
368
if not revision_id in graph:
370
if absent == len(graphs):
371
raise errors.NoSuchRevision(self._revision_sources[0],
376
pending = set(revision_ids)
378
def find_parents(node_id):
379
"""find the parents for node_id."""
382
return graph[node_id]
385
raise errors.NoSuchRevision(self._revision_sources[0], node_id)
387
# all the graphs should have identical parent lists
388
node_id = pending.pop()
390
parents = find_parents(node_id)
391
for parent_node in parents:
393
if (parent_node not in pending and
394
parent_node not in done):
396
pending.add(parent_node)
397
result.add_node(node_id, parents)
399
except errors.NoSuchRevision:
401
result.add_ghost(node_id)
406
for source in self._revision_sources:
410
for source in self._revision_sources:
414
@deprecated_function(zero_eight)
415
def get_intervening_revisions(ancestor_id, rev_id, rev_source,
416
revision_history=None):
417
"""Find the longest line of descent from maybe_ancestor to revision.
418
Revision history is followed where possible.
420
If ancestor_id == rev_id, list will be empty.
421
Otherwise, rev_id will be the last entry. ancestor_id will never appear.
422
If ancestor_id is not an ancestor, NotAncestor will be thrown
424
root, ancestors, descendants = revision_graph(rev_id, rev_source)
425
if len(descendants) == 0:
426
raise errors.NoSuchRevision(rev_source, rev_id)
427
if ancestor_id not in descendants:
428
rev_source.get_revision(ancestor_id)
429
raise errors.NotAncestor(rev_id, ancestor_id)
430
root_descendants = all_descendants(descendants, ancestor_id)
431
root_descendants.add(ancestor_id)
432
if rev_id not in root_descendants:
433
raise errors.NotAncestor(rev_id, ancestor_id)
434
distances = node_distances(descendants, ancestors, ancestor_id,
435
root_descendants=root_descendants)
437
def best_ancestor(rev_id):
439
for anc_id in ancestors[rev_id]:
441
distance = distances[anc_id]
444
if revision_history is not None and anc_id in revision_history:
446
elif best is None or distance > best[1]:
447
best = (anc_id, distance)
452
while next != ancestor_id:
454
next = best_ancestor(next)
202
459
def is_reserved_id(revision_id):
203
460
"""Determine whether a revision id is reserved
205
:return: True if the revision is reserved, False otherwise
462
:return: True if the revision is is reserved, False otherwise
207
464
return isinstance(revision_id, basestring) and revision_id.endswith(':')