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
from bzrlib.graph import node_distances, select_farthest, all_descendants
22
from bzrlib.osutils import contains_whitespace
26
class Revision(object):
27
"""Single revision on a branch.
29
Revisions may know their revision_hash, but only once they've been
30
written out. This is not stored because you cannot write the hash
31
into the file it describes.
33
After bzr 0.0.5 revisions are allowed to have multiple parents.
36
List of parent revision_ids
39
Dictionary of revision properties. These are attached to the
40
revision as extra metadata. The name must be a single
41
word; the value can be an arbitrary string.
44
def __init__(self, revision_id, properties=None, **args):
45
self.revision_id = revision_id
46
self.properties = properties or {}
47
self._check_properties()
48
self.__dict__.update(args)
50
self.parent_sha1s = []
53
return "<Revision id %s>" % self.revision_id
55
def __eq__(self, other):
56
if not isinstance(other, Revision):
58
# FIXME: rbc 20050930 parent_ids are not being compared
60
self.inventory_sha1 == other.inventory_sha1
61
and self.revision_id == other.revision_id
62
and self.timestamp == other.timestamp
63
and self.message == other.message
64
and self.timezone == other.timezone
65
and self.committer == other.committer
66
and self.properties == other.properties)
68
def __ne__(self, other):
69
return not self.__eq__(other)
71
def _check_properties(self):
72
"""Verify that all revision properties are OK.
74
for name, value in self.properties.iteritems():
75
if not isinstance(name, basestring) or contains_whitespace(name):
76
raise ValueError("invalid property name %r" % name)
77
if not isinstance(value, basestring):
78
raise ValueError("invalid property value %r for %r" %
82
def is_ancestor(revision_id, candidate_id, branch):
83
"""Return true if candidate_id is an ancestor of revision_id.
85
A false negative will be returned if any intermediate descendent of
86
candidate_id is not present in any of the revision_sources.
88
revisions_source is an object supporting a get_revision operation that
89
behaves like Branch's.
91
return candidate_id in branch.get_ancestry(revision_id)
94
def iter_ancestors(revision_id, revision_source, only_present=False):
95
ancestors = (revision_id,)
97
while len(ancestors) > 0:
99
for ancestor in ancestors:
101
yield ancestor, distance
103
revision = revision_source.get_revision(ancestor)
104
except bzrlib.errors.NoSuchRevision, e:
105
if e.revision == revision_id:
110
yield ancestor, distance
111
new_ancestors.extend(revision.parent_ids)
112
ancestors = new_ancestors
116
def find_present_ancestors(revision_id, revision_source):
117
"""Return the ancestors of a revision present in a branch.
119
It's possible that a branch won't have the complete ancestry of
120
one of its revisions.
124
anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
126
for anc_order, (anc_id, anc_distance) in anc_iter:
127
if not found_ancestors.has_key(anc_id):
128
found_ancestors[anc_id] = (anc_order, anc_distance)
129
return found_ancestors
132
def __get_closest(intersection):
135
for entry in intersection:
136
if entry[0] == intersection[0][0]:
137
matches.append(entry[2])
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
def revision_graph(revision, revision_source):
173
"""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
184
descendants[revision] = {}
185
while len(lines) > 0:
188
if line == NULL_REVISION:
193
rev = revision_source.get_revision(line)
194
parents = list(rev.parent_ids)
195
if len(parents) == 0:
196
parents = [NULL_REVISION]
197
except bzrlib.errors.NoSuchRevision:
201
if parents is not None:
202
for parent in parents:
203
if parent not in ancestors:
204
new_lines.add(parent)
205
if parent not in descendants:
206
descendants[parent] = {}
207
descendants[parent][line] = 1
208
if parents is not None:
209
ancestors[line] = set(parents)
211
assert root not in descendants[root]
212
assert root not in ancestors[root]
213
return root, ancestors, descendants
216
def combined_graph(revision_a, revision_b, revision_source):
217
"""Produce a combined ancestry graph.
218
Return graph root, ancestors map, descendants map, set of common nodes"""
219
root, ancestors, descendants = revision_graph(revision_a, revision_source)
220
root_b, ancestors_b, descendants_b = revision_graph(revision_b,
223
raise bzrlib.errors.NoCommonRoot(revision_a, revision_b)
225
for node, node_anc in ancestors_b.iteritems():
226
if node in ancestors:
229
ancestors[node] = set()
230
ancestors[node].update(node_anc)
231
for node, node_dec in descendants_b.iteritems():
232
if node not in descendants:
233
descendants[node] = {}
234
descendants[node].update(node_dec)
235
return root, ancestors, descendants, common
238
def common_ancestor(revision_a, revision_b, revision_source):
240
root, ancestors, descendants, common = \
241
combined_graph(revision_a, revision_b, revision_source)
242
except bzrlib.errors.NoCommonRoot:
243
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
245
distances = node_distances (descendants, ancestors, root)
246
farthest = select_farthest(distances, common)
247
if farthest is None or farthest == NULL_REVISION:
248
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
252
class MultipleRevisionSources(object):
253
"""Proxy that looks in multiple branches for revisions."""
254
def __init__(self, *args):
255
object.__init__(self)
256
assert len(args) != 0
257
self._revision_sources = args
259
def get_revision(self, revision_id):
260
for source in self._revision_sources:
262
return source.get_revision(revision_id)
263
except bzrlib.errors.NoSuchRevision, e:
267
def get_intervening_revisions(ancestor_id, rev_id, rev_source,
268
revision_history=None):
269
"""Find the longest line of descent from maybe_ancestor to revision.
270
Revision history is followed where possible.
272
If ancestor_id == rev_id, list will be empty.
273
Otherwise, rev_id will be the last entry. ancestor_id will never appear.
274
If ancestor_id is not an ancestor, NotAncestor will be thrown
276
root, ancestors, descendants = revision_graph(rev_id, rev_source)
277
if len(descendants) == 0:
278
raise NoSuchRevision(rev_source, rev_id)
279
if ancestor_id not in descendants:
280
rev_source.get_revision(ancestor_id)
281
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
282
root_descendants = all_descendants(descendants, ancestor_id)
283
root_descendants.add(ancestor_id)
284
if rev_id not in root_descendants:
285
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
286
distances = node_distances(descendants, ancestors, ancestor_id,
287
root_descendants=root_descendants)
289
def best_ancestor(rev_id):
291
for anc_id in ancestors[rev_id]:
293
distance = distances[anc_id]
296
if revision_history is not None and anc_id in revision_history:
298
elif best is None or distance > best[1]:
299
best = (anc_id, distance)
304
while next != ancestor_id:
306
next = best_ancestor(next)
added
removed
bzrlib/revision.py
