1
# Copyright (C) 2005, 2006 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
# TODO: Some kind of command-line display of revision properties:
18
# perhaps show them in log -v and allow them as options to the commit command.
21
import bzrlib.errors as errors
22
from bzrlib.deprecated_graph import (
28
from bzrlib.osutils import contains_whitespace
29
from bzrlib.progress import DummyProgress
30
from bzrlib.symbol_versioning import (deprecated_function,
35
CURRENT_REVISION="current:"
38
class Revision(object):
39
"""Single revision on a branch.
41
Revisions may know their revision_hash, but only once they've been
42
written out. This is not stored because you cannot write the hash
43
into the file it describes.
45
After bzr 0.0.5 revisions are allowed to have multiple parents.
48
List of parent revision_ids
51
Dictionary of revision properties. These are attached to the
52
revision as extra metadata. The name must be a single
53
word; the value can be an arbitrary string.
56
def __init__(self, revision_id, properties=None, **args):
57
self.revision_id = revision_id
58
self.properties = properties or {}
59
self._check_properties()
61
self.parent_sha1s = []
62
"""Not used anymore - legacy from for 4."""
63
self.__dict__.update(args)
66
return "<Revision id %s>" % self.revision_id
68
def __eq__(self, other):
69
if not isinstance(other, Revision):
71
# FIXME: rbc 20050930 parent_ids are not being compared
73
self.inventory_sha1 == other.inventory_sha1
74
and self.revision_id == other.revision_id
75
and self.timestamp == other.timestamp
76
and self.message == other.message
77
and self.timezone == other.timezone
78
and self.committer == other.committer
79
and self.properties == other.properties)
81
def __ne__(self, other):
82
return not self.__eq__(other)
84
def _check_properties(self):
85
"""Verify that all revision properties are OK."""
86
for name, value in self.properties.iteritems():
87
if not isinstance(name, basestring) or contains_whitespace(name):
88
raise ValueError("invalid property name %r" % name)
89
if not isinstance(value, basestring):
90
raise ValueError("invalid property value %r for %r" %
93
def get_history(self, repository):
94
"""Return the canonical line-of-history for this revision.
96
If ghosts are present this may differ in result from a ghost-free
99
current_revision = self
101
while current_revision is not None:
102
reversed_result.append(current_revision.revision_id)
103
if not len (current_revision.parent_ids):
104
reversed_result.append(None)
105
current_revision = None
107
next_revision_id = current_revision.parent_ids[0]
108
current_revision = repository.get_revision(next_revision_id)
109
reversed_result.reverse()
110
return reversed_result
112
def get_summary(self):
113
"""Get the first line of the log message for this revision.
115
return self.message.split('\n', 1)[0]
118
def is_ancestor(revision_id, candidate_id, branch):
119
"""Return true if candidate_id is an ancestor of revision_id.
121
A false negative will be returned if any intermediate descendent of
122
candidate_id is not present in any of the revision_sources.
124
revisions_source is an object supporting a get_revision operation that
125
behaves like Branch's.
127
if is_null(candidate_id):
129
return (candidate_id in branch.repository.get_ancestry(revision_id,
133
def iter_ancestors(revision_id, revision_source, only_present=False):
134
ancestors = (revision_id,)
136
while len(ancestors) > 0:
138
for ancestor in ancestors:
140
yield ancestor, distance
142
revision = revision_source.get_revision(ancestor)
143
except errors.NoSuchRevision, e:
144
if e.revision == revision_id:
149
yield ancestor, distance
150
new_ancestors.extend(revision.parent_ids)
151
ancestors = new_ancestors
155
def find_present_ancestors(revision_id, revision_source):
156
"""Return the ancestors of a revision present in a branch.
158
It's possible that a branch won't have the complete ancestry of
159
one of its revisions.
163
anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
165
for anc_order, (anc_id, anc_distance) in anc_iter:
166
if anc_id not in found_ancestors:
167
found_ancestors[anc_id] = (anc_order, anc_distance)
168
return found_ancestors
171
def __get_closest(intersection):
174
for entry in intersection:
175
if entry[0] == intersection[0][0]:
176
matches.append(entry[2])
180
def revision_graph(revision, revision_source):
181
"""Produce a graph of the ancestry of the specified revision.
183
:return: root, ancestors map, descendants map
185
revision_source.lock_read()
187
return _revision_graph(revision, revision_source)
189
revision_source.unlock()
192
def _revision_graph(revision, revision_source):
193
"""See revision_graph."""
194
from bzrlib.tsort import topo_sort
195
graph = revision_source.get_revision_graph(revision)
196
# mark all no-parent revisions as being NULL_REVISION parentage.
197
for node, parents in graph.items():
198
if len(parents) == 0:
199
graph[node] = [NULL_REVISION]
200
# add NULL_REVISION to the graph
201
graph[NULL_REVISION] = []
203
# pick a root. If there are multiple roots
204
# this could pick a random one.
205
topo_order = topo_sort(graph.items())
211
# map the descendants of the graph.
212
# and setup our set based return graph.
213
for node in graph.keys():
214
descendants[node] = {}
215
for node, parents in graph.items():
216
for parent in parents:
217
descendants[parent][node] = 1
218
ancestors[node] = set(parents)
220
assert root not in descendants[root]
221
assert root not in ancestors[root]
222
return root, ancestors, descendants
225
def combined_graph(revision_a, revision_b, revision_source):
226
"""Produce a combined ancestry graph.
227
Return graph root, ancestors map, descendants map, set of common nodes"""
228
root, ancestors, descendants = revision_graph(
229
revision_a, revision_source)
230
root_b, ancestors_b, descendants_b = revision_graph(
231
revision_b, revision_source)
233
raise errors.NoCommonRoot(revision_a, revision_b)
235
for node, node_anc in ancestors_b.iteritems():
236
if node in ancestors:
239
ancestors[node] = set()
240
ancestors[node].update(node_anc)
241
for node, node_dec in descendants_b.iteritems():
242
if node not in descendants:
243
descendants[node] = {}
244
descendants[node].update(node_dec)
245
return root, ancestors, descendants, common
248
def common_ancestor(revision_a, revision_b, revision_source,
250
if None in (revision_a, revision_b):
252
if NULL_REVISION in (revision_a, revision_b):
254
# trivial optimisation
255
if revision_a == revision_b:
259
pb.update('Picking ancestor', 1, 3)
260
graph = revision_source.get_revision_graph_with_ghosts(
261
[revision_a, revision_b])
262
# Shortcut the case where one of the tips is already included in
263
# the other graphs ancestry.
264
ancestry_a = graph.get_ancestry(revision_a, topo_sorted=False)
265
if revision_b in ancestry_a:
267
ancestry_b = graph.get_ancestry(revision_b, topo_sorted=False)
268
if revision_a in ancestry_b:
270
# convert to a NULL_REVISION based graph.
271
ancestors = graph.get_ancestors()
272
descendants = graph.get_descendants()
273
common = set(ancestry_a)
274
common.intersection_update(ancestry_b)
275
descendants[NULL_REVISION] = {}
276
ancestors[NULL_REVISION] = []
277
for root in graph.roots:
278
descendants[NULL_REVISION][root] = 1
279
ancestors[root].append(NULL_REVISION)
280
for ghost in graph.ghosts:
281
# ghosts act as roots for the purpose of finding
282
# the longest paths from the root: any ghost *might*
283
# be directly attached to the root, so we treat them
285
# ghost now descends from NULL
286
descendants[NULL_REVISION][ghost] = 1
287
# that is it has an ancestor of NULL
288
ancestors[ghost] = [NULL_REVISION]
289
# ghost is common if any of ghosts descendants are common:
290
for ghost_descendant in descendants[ghost]:
291
if ghost_descendant in common:
295
common.add(NULL_REVISION)
296
except errors.NoCommonRoot:
297
raise errors.NoCommonAncestor(revision_a, revision_b)
299
pb.update('Picking ancestor', 2, 3)
300
distances = node_distances (descendants, ancestors, root)
301
pb.update('Picking ancestor', 3, 2)
302
farthest = select_farthest(distances, common)
303
if farthest is None or farthest == NULL_REVISION:
304
raise errors.NoCommonAncestor(revision_a, revision_b)
310
class MultipleRevisionSources(object):
311
"""Proxy that looks in multiple branches for revisions."""
312
def __init__(self, *args):
313
object.__init__(self)
314
assert len(args) != 0
315
self._revision_sources = args
317
def revision_parents(self, revision_id):
318
for source in self._revision_sources:
320
return source.revision_parents(revision_id)
321
except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:
325
def get_revision(self, revision_id):
326
for source in self._revision_sources:
328
return source.get_revision(revision_id)
329
except errors.NoSuchRevision, e:
333
def get_revision_graph(self, revision_id):
334
# we could probe incrementally until the pending
335
# ghosts list stop growing, but its cheaper for now
336
# to just ask for the complete graph for each repository.
338
for source in self._revision_sources:
339
ghost_graph = source.get_revision_graph_with_ghosts()
340
graphs.append(ghost_graph)
343
if not revision_id in graph.get_ancestors():
345
if absent == len(graphs):
346
raise errors.NoSuchRevision(self._revision_sources[0], revision_id)
350
pending = set([revision_id])
351
def find_parents(node_id):
352
"""find the parents for node_id."""
354
ancestors = graph.get_ancestors()
356
return ancestors[node_id]
359
raise errors.NoSuchRevision(self._revision_sources[0], node_id)
361
# all the graphs should have identical parent lists
362
node_id = pending.pop()
364
result[node_id] = find_parents(node_id)
365
for parent_node in result[node_id]:
366
if not parent_node in result:
367
pending.add(parent_node)
368
except errors.NoSuchRevision:
373
def get_revision_graph_with_ghosts(self, revision_ids):
374
# query all the sources for their entire graphs
375
# and then build a combined graph for just
378
for source in self._revision_sources:
379
ghost_graph = source.get_revision_graph_with_ghosts()
380
graphs.append(ghost_graph.get_ancestors())
381
for revision_id in revision_ids:
384
if not revision_id in graph:
386
if absent == len(graphs):
387
raise errors.NoSuchRevision(self._revision_sources[0],
392
pending = set(revision_ids)
394
def find_parents(node_id):
395
"""find the parents for node_id."""
398
return graph[node_id]
401
raise errors.NoSuchRevision(self._revision_sources[0], node_id)
403
# all the graphs should have identical parent lists
404
node_id = pending.pop()
406
parents = find_parents(node_id)
407
for parent_node in parents:
409
if (parent_node not in pending and
410
parent_node not in done):
412
pending.add(parent_node)
413
result.add_node(node_id, parents)
415
except errors.NoSuchRevision:
417
result.add_ghost(node_id)
422
for source in self._revision_sources:
426
for source in self._revision_sources:
430
@deprecated_function(zero_eight)
431
def get_intervening_revisions(ancestor_id, rev_id, rev_source,
432
revision_history=None):
433
"""Find the longest line of descent from maybe_ancestor to revision.
434
Revision history is followed where possible.
436
If ancestor_id == rev_id, list will be empty.
437
Otherwise, rev_id will be the last entry. ancestor_id will never appear.
438
If ancestor_id is not an ancestor, NotAncestor will be thrown
440
root, ancestors, descendants = revision_graph(rev_id, rev_source)
441
if len(descendants) == 0:
442
raise errors.NoSuchRevision(rev_source, rev_id)
443
if ancestor_id not in descendants:
444
rev_source.get_revision(ancestor_id)
445
raise errors.NotAncestor(rev_id, ancestor_id)
446
root_descendants = all_descendants(descendants, ancestor_id)
447
root_descendants.add(ancestor_id)
448
if rev_id not in root_descendants:
449
raise errors.NotAncestor(rev_id, ancestor_id)
450
distances = node_distances(descendants, ancestors, ancestor_id,
451
root_descendants=root_descendants)
453
def best_ancestor(rev_id):
455
for anc_id in ancestors[rev_id]:
457
distance = distances[anc_id]
460
if revision_history is not None and anc_id in revision_history:
462
elif best is None or distance > best[1]:
463
best = (anc_id, distance)
468
while next != ancestor_id:
470
next = best_ancestor(next)
475
def is_reserved_id(revision_id):
476
"""Determine whether a revision id is reserved
478
:return: True if the revision is is reserved, False otherwise
480
return isinstance(revision_id, basestring) and revision_id.endswith(':')
483
def check_not_reserved_id(revision_id):
484
"""Raise ReservedId if the supplied revision_id is reserved"""
485
if is_reserved_id(revision_id):
486
raise errors.ReservedId(revision_id)
489
def ensure_null(revision_id):
490
"""Ensure only NULL_REVISION is used to represent the null revisionn"""
491
if revision_id is None:
497
def is_null(revision_id):
498
assert revision_id is not None
499
return revision_id in (None, NULL_REVISION)
added
removed
bzrlib/revision.py
