78
92
raise ValueError("invalid property value %r for %r" %
95
def get_history(self, repository):
96
"""Return the canonical line-of-history for this revision.
98
If ghosts are present this may differ in result from a ghost-free
101
current_revision = self
103
while current_revision is not None:
104
reversed_result.append(current_revision.revision_id)
105
if not len (current_revision.parent_ids):
106
reversed_result.append(None)
107
current_revision = None
109
next_revision_id = current_revision.parent_ids[0]
110
current_revision = repository.get_revision(next_revision_id)
111
reversed_result.reverse()
112
return reversed_result
114
def get_summary(self):
115
"""Get the first line of the log message for this revision.
117
return self.message.lstrip().split('\n', 1)[0]
119
def get_apparent_author(self):
120
"""Return the apparent author of this revision.
122
If the revision properties contain the author name,
123
return it. Otherwise return the committer name.
125
return self.properties.get('author', self.committer)
82
128
def is_ancestor(revision_id, candidate_id, branch):
83
129
"""Return true if candidate_id is an ancestor of revision_id.
141
def old_common_ancestor(revision_a, revision_b, revision_source):
142
"""Find the ancestor common to both revisions that is closest to both.
144
from bzrlib.trace import mutter
145
a_ancestors = find_present_ancestors(revision_a, revision_source)
146
b_ancestors = find_present_ancestors(revision_b, revision_source)
149
# a_order is used as a tie-breaker when two equally-good bases are found
150
for revision, (a_order, a_distance) in a_ancestors.iteritems():
151
if b_ancestors.has_key(revision):
152
a_intersection.append((a_distance, a_order, revision))
153
b_intersection.append((b_ancestors[revision][1], a_order, revision))
154
mutter("a intersection: %r", a_intersection)
155
mutter("b intersection: %r", b_intersection)
157
a_closest = __get_closest(a_intersection)
158
if len(a_closest) == 0:
160
b_closest = __get_closest(b_intersection)
161
assert len(b_closest) != 0
162
mutter ("a_closest %r", a_closest)
163
mutter ("b_closest %r", b_closest)
164
if a_closest[0] in b_closest:
166
elif b_closest[0] in a_closest:
169
raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
172
190
def revision_graph(revision, revision_source):
173
191
"""Produce a graph of the ancestry of the specified revision.
174
Return root, ancestors map, descendants map
176
TODO: Produce graphs with the NULL revision as root, so that we can find
177
a common even when trees are not branches don't represent a single line
179
RBC: 20051024: note that when we have two partial histories, this may not
180
be possible. But if we are willing to pretend :)... sure.
193
:return: root, ancestors map, descendants map
195
revision_source.lock_read()
197
return _revision_graph(revision, revision_source)
199
revision_source.unlock()
202
def _revision_graph(revision, revision_source):
203
"""See revision_graph."""
204
from bzrlib.tsort import topo_sort
205
graph = revision_source.get_revision_graph(revision)
206
# mark all no-parent revisions as being NULL_REVISION parentage.
207
for node, parents in graph.items():
208
if len(parents) == 0:
209
graph[node] = [NULL_REVISION]
210
# add NULL_REVISION to the graph
211
graph[NULL_REVISION] = []
213
# pick a root. If there are multiple roots
214
# this could pick a random one.
215
topo_order = topo_sort(graph.items())
186
descendants[revision] = {}
187
while len(lines) > 0:
190
if line == NULL_REVISION:
195
rev = revision_source.get_revision(line)
196
parents = list(rev.parent_ids)
197
if len(parents) == 0:
198
parents = [NULL_REVISION]
199
except bzrlib.errors.NoSuchRevision:
203
if parents is not None:
204
for parent in parents:
205
if parent not in ancestors:
206
new_lines.add(parent)
207
if parent not in descendants:
208
descendants[parent] = {}
209
descendants[parent][line] = 1
210
if parents is not None:
211
ancestors[line] = set(parents)
214
# The history for revision becomes inaccessible without
215
# actually hitting a no-parents revision. This then
216
# makes these asserts below trigger. So, if root is None
217
# determine the actual root by walking the accessible tree
218
# and then stash NULL_REVISION at the end.
220
descendants[root] = {}
221
# for every revision, check we can access at least
222
# one parent, if we cant, add NULL_REVISION and
224
for rev in ancestors:
225
if len(ancestors[rev]) == 0:
226
raise RuntimeError('unreachable code ?!')
228
for parent in ancestors[rev]:
229
if parent in ancestors:
233
descendants[root][rev] = 1
234
ancestors[rev].add(root)
235
ancestors[root] = set()
221
# map the descendants of the graph.
222
# and setup our set based return graph.
223
for node in graph.keys():
224
descendants[node] = {}
225
for node, parents in graph.items():
226
for parent in parents:
227
descendants[parent][node] = 1
228
ancestors[node] = set(parents)
236
230
assert root not in descendants[root]
237
231
assert root not in ancestors[root]
238
232
return root, ancestors, descendants
241
235
def combined_graph(revision_a, revision_b, revision_source):
242
236
"""Produce a combined ancestry graph.
243
237
Return graph root, ancestors map, descendants map, set of common nodes"""
244
root, ancestors, descendants = revision_graph(revision_a, revision_source)
245
root_b, ancestors_b, descendants_b = revision_graph(revision_b,
238
root, ancestors, descendants = revision_graph(
239
revision_a, revision_source)
240
root_b, ancestors_b, descendants_b = revision_graph(
241
revision_b, revision_source)
247
242
if root != root_b:
248
raise bzrlib.errors.NoCommonRoot(revision_a, revision_b)
243
raise errors.NoCommonRoot(revision_a, revision_b)
250
245
for node, node_anc in ancestors_b.iteritems():
251
246
if node in ancestors:
260
255
return root, ancestors, descendants, common
263
def common_ancestor(revision_a, revision_b, revision_source):
258
def common_ancestor(revision_a, revision_b, revision_source,
260
if None in (revision_a, revision_b):
262
if NULL_REVISION in (revision_a, revision_b):
264
# trivial optimisation
265
if revision_a == revision_b:
265
root, ancestors, descendants, common = \
266
combined_graph(revision_a, revision_b, revision_source)
267
except bzrlib.errors.NoCommonRoot:
268
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
270
distances = node_distances (descendants, ancestors, root)
271
farthest = select_farthest(distances, common)
272
if farthest is None or farthest == NULL_REVISION:
273
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
269
pb.update('Picking ancestor', 1, 3)
270
graph = revision_source.get_revision_graph_with_ghosts(
271
[revision_a, revision_b])
272
# Shortcut the case where one of the tips is already included in
273
# the other graphs ancestry.
274
ancestry_a = graph.get_ancestry(revision_a, topo_sorted=False)
275
if revision_b in ancestry_a:
277
ancestry_b = graph.get_ancestry(revision_b, topo_sorted=False)
278
if revision_a in ancestry_b:
280
# convert to a NULL_REVISION based graph.
281
ancestors = graph.get_ancestors()
282
descendants = graph.get_descendants()
283
common = set(ancestry_a)
284
common.intersection_update(ancestry_b)
285
descendants[NULL_REVISION] = {}
286
ancestors[NULL_REVISION] = []
287
for root in graph.roots:
288
descendants[NULL_REVISION][root] = 1
289
ancestors[root].append(NULL_REVISION)
290
for ghost in graph.ghosts:
291
# ghosts act as roots for the purpose of finding
292
# the longest paths from the root: any ghost *might*
293
# be directly attached to the root, so we treat them
295
# ghost now descends from NULL
296
descendants[NULL_REVISION][ghost] = 1
297
# that is it has an ancestor of NULL
298
ancestors[ghost] = [NULL_REVISION]
299
# ghost is common if any of ghosts descendants are common:
300
for ghost_descendant in descendants[ghost]:
301
if ghost_descendant in common:
305
common.add(NULL_REVISION)
306
except errors.NoCommonRoot:
307
raise errors.NoCommonAncestor(revision_a, revision_b)
309
pb.update('Picking ancestor', 2, 3)
310
distances = node_distances (descendants, ancestors, root)
311
pb.update('Picking ancestor', 3, 2)
312
farthest = select_farthest(distances, common)
313
if farthest is None or farthest == NULL_REVISION:
314
raise errors.NoCommonAncestor(revision_a, revision_b)
281
324
assert len(args) != 0
282
325
self._revision_sources = args
327
def revision_parents(self, revision_id):
328
for source in self._revision_sources:
330
return source.revision_parents(revision_id)
331
except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
284
335
def get_revision(self, revision_id):
285
336
for source in self._revision_sources:
287
338
return source.get_revision(revision_id)
288
except bzrlib.errors.NoSuchRevision, e:
339
except errors.NoSuchRevision, e:
292
def get_intervening_revisions(ancestor_id, rev_id, rev_source,
293
revision_history=None):
294
"""Find the longest line of descent from maybe_ancestor to revision.
295
Revision history is followed where possible.
297
If ancestor_id == rev_id, list will be empty.
298
Otherwise, rev_id will be the last entry. ancestor_id will never appear.
299
If ancestor_id is not an ancestor, NotAncestor will be thrown
343
def get_revision_graph(self, revision_id):
344
# we could probe incrementally until the pending
345
# ghosts list stop growing, but its cheaper for now
346
# to just ask for the complete graph for each repository.
348
for source in self._revision_sources:
349
ghost_graph = source.get_revision_graph_with_ghosts()
350
graphs.append(ghost_graph)
353
if not revision_id in graph.get_ancestors():
355
if absent == len(graphs):
356
raise errors.NoSuchRevision(self._revision_sources[0], revision_id)
360
pending = set([revision_id])
361
def find_parents(node_id):
362
"""find the parents for node_id."""
364
ancestors = graph.get_ancestors()
366
return ancestors[node_id]
369
raise errors.NoSuchRevision(self._revision_sources[0], node_id)
371
# all the graphs should have identical parent lists
372
node_id = pending.pop()
374
result[node_id] = find_parents(node_id)
375
for parent_node in result[node_id]:
376
if not parent_node in result:
377
pending.add(parent_node)
378
except errors.NoSuchRevision:
383
def get_revision_graph_with_ghosts(self, revision_ids):
384
# query all the sources for their entire graphs
385
# and then build a combined graph for just
388
for source in self._revision_sources:
389
ghost_graph = source.get_revision_graph_with_ghosts()
390
graphs.append(ghost_graph.get_ancestors())
391
for revision_id in revision_ids:
394
if not revision_id in graph:
396
if absent == len(graphs):
397
raise errors.NoSuchRevision(self._revision_sources[0],
402
pending = set(revision_ids)
404
def find_parents(node_id):
405
"""find the parents for node_id."""
408
return graph[node_id]
411
raise errors.NoSuchRevision(self._revision_sources[0], node_id)
413
# all the graphs should have identical parent lists
414
node_id = pending.pop()
416
parents = find_parents(node_id)
417
for parent_node in parents:
419
if (parent_node not in pending and
420
parent_node not in done):
422
pending.add(parent_node)
423
result.add_node(node_id, parents)
425
except errors.NoSuchRevision:
427
result.add_ghost(node_id)
432
for source in self._revision_sources:
436
for source in self._revision_sources:
440
def is_reserved_id(revision_id):
441
"""Determine whether a revision id is reserved
443
:return: True if the revision is is reserved, False otherwise
301
root, ancestors, descendants = revision_graph(rev_id, rev_source)
302
if len(descendants) == 0:
303
raise NoSuchRevision(rev_source, rev_id)
304
if ancestor_id not in descendants:
305
rev_source.get_revision(ancestor_id)
306
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
307
root_descendants = all_descendants(descendants, ancestor_id)
308
root_descendants.add(ancestor_id)
309
if rev_id not in root_descendants:
310
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
311
distances = node_distances(descendants, ancestors, ancestor_id,
312
root_descendants=root_descendants)
314
def best_ancestor(rev_id):
316
for anc_id in ancestors[rev_id]:
318
distance = distances[anc_id]
321
if revision_history is not None and anc_id in revision_history:
323
elif best is None or distance > best[1]:
324
best = (anc_id, distance)
329
while next != ancestor_id:
331
next = best_ancestor(next)
445
return isinstance(revision_id, basestring) and revision_id.endswith(':')
448
def check_not_reserved_id(revision_id):
449
"""Raise ReservedId if the supplied revision_id is reserved"""
450
if is_reserved_id(revision_id):
451
raise errors.ReservedId(revision_id)
454
def ensure_null(revision_id):
455
"""Ensure only NULL_REVISION is used to represent the null revisionn"""
456
if revision_id is None:
457
symbol_versioning.warn('NULL_REVISION should be used for the null'
458
' revision instead of None, as of bzr 0.91.',
459
DeprecationWarning, stacklevel=2)
465
def is_null(revision_id):
466
if revision_id is None:
467
symbol_versioning.warn('NULL_REVISION should be used for the null'
468
' revision instead of None, as of bzr 0.90.',
469
DeprecationWarning, stacklevel=2)
470
return revision_id in (None, NULL_REVISION)
added
removed
bzrlib/revision.py
