175
@deprecated_function(symbol_versioning.one_four)
176
def revision_graph(revision, revision_source):
177
"""Produce a graph of the ancestry of the specified revision.
179
:return: root, ancestors map, descendants map
181
revision_source.lock_read()
183
return _revision_graph(revision, revision_source)
185
revision_source.unlock()
188
def _revision_graph(revision, revision_source):
189
"""See revision_graph."""
190
from bzrlib.tsort import topo_sort
191
graph = revision_source.get_revision_graph(revision)
192
# mark all no-parent revisions as being NULL_REVISION parentage.
193
for node, parents in graph.items():
194
if len(parents) == 0:
195
graph[node] = [NULL_REVISION]
196
# add NULL_REVISION to the graph
197
graph[NULL_REVISION] = []
199
# pick a root. If there are multiple roots
200
# this could pick a random one.
201
topo_order = topo_sort(graph.items())
207
# map the descendants of the graph.
208
# and setup our set based return graph.
209
for node in graph.keys():
210
descendants[node] = {}
211
for node, parents in graph.items():
212
for parent in parents:
213
descendants[parent][node] = 1
214
ancestors[node] = set(parents)
215
return root, ancestors, descendants
218
@deprecated_function(symbol_versioning.one_three)
219
def combined_graph(revision_a, revision_b, revision_source):
220
"""Produce a combined ancestry graph.
221
Return graph root, ancestors map, descendants map, set of common nodes"""
222
root, ancestors, descendants = revision_graph(
223
revision_a, revision_source)
224
root_b, ancestors_b, descendants_b = revision_graph(
225
revision_b, revision_source)
227
raise errors.NoCommonRoot(revision_a, revision_b)
229
for node, node_anc in ancestors_b.iteritems():
230
if node in ancestors:
233
ancestors[node] = set()
234
ancestors[node].update(node_anc)
235
for node, node_dec in descendants_b.iteritems():
236
if node not in descendants:
237
descendants[node] = {}
238
descendants[node].update(node_dec)
239
return root, ancestors, descendants, common
242
@deprecated_function(symbol_versioning.one_three)
243
def common_ancestor(revision_a, revision_b, revision_source,
245
if None in (revision_a, revision_b):
247
if NULL_REVISION in (revision_a, revision_b):
249
# trivial optimisation
250
if revision_a == revision_b:
254
pb.update('Picking ancestor', 1, 3)
255
graph = revision_source.get_revision_graph_with_ghosts(
256
[revision_a, revision_b])
257
# Shortcut the case where one of the tips is already included in
258
# the other graphs ancestry.
259
ancestry_a = graph.get_ancestry(revision_a, topo_sorted=False)
260
if revision_b in ancestry_a:
262
ancestry_b = graph.get_ancestry(revision_b, topo_sorted=False)
263
if revision_a in ancestry_b:
265
# convert to a NULL_REVISION based graph.
266
ancestors = graph.get_ancestors()
267
descendants = graph.get_descendants()
268
common = set(ancestry_a)
269
common.intersection_update(ancestry_b)
270
descendants[NULL_REVISION] = {}
271
ancestors[NULL_REVISION] = []
272
for root in graph.roots:
273
descendants[NULL_REVISION][root] = 1
274
ancestors[root].append(NULL_REVISION)
275
for ghost in graph.ghosts:
276
# ghosts act as roots for the purpose of finding
277
# the longest paths from the root: any ghost *might*
278
# be directly attached to the root, so we treat them
280
# ghost now descends from NULL
281
descendants[NULL_REVISION][ghost] = 1
282
# that is it has an ancestor of NULL
283
ancestors[ghost] = [NULL_REVISION]
284
# ghost is common if any of ghosts descendants are common:
285
for ghost_descendant in descendants[ghost]:
286
if ghost_descendant in common:
290
common.add(NULL_REVISION)
291
except errors.NoCommonRoot:
292
raise errors.NoCommonAncestor(revision_a, revision_b)
294
pb.update('Picking ancestor', 2, 3)
295
distances = node_distances (descendants, ancestors, root)
296
pb.update('Picking ancestor', 3, 2)
297
farthest = select_farthest(distances, common)
298
if farthest is None or farthest == NULL_REVISION:
299
raise errors.NoCommonAncestor(revision_a, revision_b)
305
class MultipleRevisionSources(object):
306
"""Proxy that looks in multiple branches for revisions."""
308
@symbol_versioning.deprecated_method(symbol_versioning.one_three)
309
def __init__(self, *args):
310
object.__init__(self)
311
self._revision_sources = args
313
def revision_parents(self, revision_id):
314
for source in self._revision_sources:
316
return source.revision_parents(revision_id)
317
except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
321
def get_revision(self, revision_id):
322
for source in self._revision_sources:
324
return source.get_revision(revision_id)
325
except errors.NoSuchRevision, e:
329
def get_revision_graph(self, revision_id):
330
# we could probe incrementally until the pending
331
# ghosts list stop growing, but its cheaper for now
332
# to just ask for the complete graph for each repository.
334
for source in self._revision_sources:
335
ghost_graph = source.get_revision_graph_with_ghosts()
336
graphs.append(ghost_graph)
339
if not revision_id in graph.get_ancestors():
341
if absent == len(graphs):
342
raise errors.NoSuchRevision(self._revision_sources[0], revision_id)
346
pending = set([revision_id])
347
def find_parents(node_id):
348
"""find the parents for node_id."""
350
ancestors = graph.get_ancestors()
352
return ancestors[node_id]
355
raise errors.NoSuchRevision(self._revision_sources[0], node_id)
357
# all the graphs should have identical parent lists
358
node_id = pending.pop()
360
result[node_id] = find_parents(node_id)
361
for parent_node in result[node_id]:
362
if not parent_node in result:
363
pending.add(parent_node)
364
except errors.NoSuchRevision:
369
def get_revision_graph_with_ghosts(self, revision_ids):
370
# query all the sources for their entire graphs
371
# and then build a combined graph for just
374
for source in self._revision_sources:
375
ghost_graph = source.get_revision_graph_with_ghosts()
376
graphs.append(ghost_graph.get_ancestors())
377
for revision_id in revision_ids:
380
if not revision_id in graph:
382
if absent == len(graphs):
383
raise errors.NoSuchRevision(self._revision_sources[0],
388
pending = set(revision_ids)
390
def find_parents(node_id):
391
"""find the parents for node_id."""
394
return graph[node_id]
397
raise errors.NoSuchRevision(self._revision_sources[0], node_id)
399
# all the graphs should have identical parent lists
400
node_id = pending.pop()
402
parents = find_parents(node_id)
403
for parent_node in parents:
405
if (parent_node not in pending and
406
parent_node not in done):
408
pending.add(parent_node)
409
result.add_node(node_id, parents)
411
except errors.NoSuchRevision:
413
result.add_ghost(node_id)
418
for source in self._revision_sources:
422
for source in self._revision_sources:
426
167
def is_reserved_id(revision_id):
427
168
"""Determine whether a revision id is reserved
added
removed
bzrlib/revision.py
