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
19
from bzrlib.graph import node_distances, select_farthest, all_descendants
23
class RevisionReference(object):
25
Reference to a stored revision.
27
Includes the revision_id and revision_sha1.
31
def __init__(self, revision_id, revision_sha1=None):
32
if revision_id == None \
33
or isinstance(revision_id, basestring):
34
self.revision_id = revision_id
36
raise ValueError('bad revision_id %r' % revision_id)
38
if revision_sha1 != None:
39
if isinstance(revision_sha1, basestring) \
40
and len(revision_sha1) == 40:
41
self.revision_sha1 = revision_sha1
43
raise ValueError('bad revision_sha1 %r' % revision_sha1)
47
class Revision(object):
48
"""Single revision on a branch.
50
Revisions may know their revision_hash, but only once they've been
51
written out. This is not stored because you cannot write the hash
52
into the file it describes.
54
After bzr 0.0.5 revisions are allowed to have multiple parents.
57
List of parent revisions, each is a RevisionReference.
67
def __init__(self, **args):
68
self.__dict__.update(args)
73
return "<Revision id %s>" % self.revision_id
75
def __eq__(self, other):
76
if not isinstance(other, Revision):
78
return (self.inventory_id == other.inventory_id
79
and self.inventory_sha1 == other.inventory_sha1
80
and self.revision_id == other.revision_id
81
and self.timestamp == other.timestamp
82
and self.message == other.message
83
and self.timezone == other.timezone
84
and self.committer == other.committer)
86
def __ne__(self, other):
87
return not self.__eq__(other)
93
def validate_revision_id(rid):
94
"""Check rid is syntactically valid for a revision id."""
96
if not REVISION_ID_RE:
98
REVISION_ID_RE = re.compile('[\w.-]+@[\w.-]+--?\d+--?[0-9a-f]+\Z')
100
if not REVISION_ID_RE.match(rid):
101
raise ValueError("malformed revision-id %r" % rid)
103
def is_ancestor(revision_id, candidate_id, revision_source):
104
"""Return true if candidate_id is an ancestor of revision_id.
105
A false negative will be returned if any intermediate descendent of
106
candidate_id is not present in any of the revision_sources.
108
revisions_source is an object supporting a get_revision operation that
109
behaves like Branch's.
111
if candidate_id is None:
113
for ancestor_id, distance in iter_ancestors(revision_id, revision_source):
114
if ancestor_id == candidate_id:
118
def iter_ancestors(revision_id, revision_source, only_present=False):
119
ancestors = (revision_id,)
121
while len(ancestors) > 0:
123
for ancestor in ancestors:
125
yield ancestor, distance
127
revision = revision_source.get_revision(ancestor)
128
except bzrlib.errors.NoSuchRevision, e:
129
if e.revision == revision_id:
134
yield ancestor, distance
135
new_ancestors.extend([p.revision_id for p in revision.parents])
136
ancestors = new_ancestors
140
def find_present_ancestors(revision_id, revision_source):
141
"""Return the ancestors of a revision present in a branch.
143
It's possible that a branch won't have the complete ancestry of
144
one of its revisions.
148
anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
150
for anc_order, (anc_id, anc_distance) in anc_iter:
151
if not found_ancestors.has_key(anc_id):
152
found_ancestors[anc_id] = (anc_order, anc_distance)
153
return found_ancestors
156
def __get_closest(intersection):
159
for entry in intersection:
160
if entry[0] == intersection[0][0]:
161
matches.append(entry[2])
165
def old_common_ancestor(revision_a, revision_b, revision_source):
166
"""Find the ancestor common to both revisions that is closest to both.
168
from bzrlib.trace import mutter
169
a_ancestors = find_present_ancestors(revision_a, revision_source)
170
b_ancestors = find_present_ancestors(revision_b, revision_source)
173
# a_order is used as a tie-breaker when two equally-good bases are found
174
for revision, (a_order, a_distance) in a_ancestors.iteritems():
175
if b_ancestors.has_key(revision):
176
a_intersection.append((a_distance, a_order, revision))
177
b_intersection.append((b_ancestors[revision][1], a_order, revision))
178
mutter("a intersection: %r" % a_intersection)
179
mutter("b intersection: %r" % b_intersection)
181
a_closest = __get_closest(a_intersection)
182
if len(a_closest) == 0:
184
b_closest = __get_closest(b_intersection)
185
assert len(b_closest) != 0
186
mutter ("a_closest %r" % a_closest)
187
mutter ("b_closest %r" % b_closest)
188
if a_closest[0] in b_closest:
190
elif b_closest[0] in a_closest:
193
raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
196
def revision_graph(revision, revision_source):
197
"""Produce a graph of the ancestry of the specified revision.
198
Return root, ancestors map, descendants map
200
TODO: Produce graphs with the NULL revision as root, so that we can find
201
a common even when trees are not branches don't represent a single line
208
descendants[revision] = {}
209
while len(lines) > 0:
212
if line == NULL_REVISION:
217
rev = revision_source.get_revision(line)
218
parents = [p.revision_id for p in rev.parents]
219
if len(parents) == 0:
220
parents = [NULL_REVISION]
221
except bzrlib.errors.NoSuchRevision:
225
if parents is not None:
226
for parent in parents:
227
if parent not in ancestors:
228
new_lines.add(parent)
229
if parent not in descendants:
230
descendants[parent] = {}
231
descendants[parent][line] = 1
232
if parents is not None:
233
ancestors[line] = set(parents)
235
assert root not in descendants[root]
236
assert root not in ancestors[root]
237
return root, ancestors, descendants
239
def combined_graph(revision_a, revision_b, revision_source):
240
"""Produce a combined ancestry graph.
241
Return graph root, ancestors map, descendants map, set of common nodes"""
242
root, ancestors, descendants = revision_graph(revision_a, revision_source)
243
root_b, ancestors_b, descendants_b = revision_graph(revision_b,
246
raise bzrlib.errors.NoCommonRoot(revision_a, revision_b)
248
for node, node_anc in ancestors_b.iteritems():
249
if node in ancestors:
252
ancestors[node] = set()
253
ancestors[node].update(node_anc)
254
for node, node_dec in descendants_b.iteritems():
255
if node not in descendants:
256
descendants[node] = {}
257
descendants[node].update(node_dec)
258
return root, ancestors, descendants, common
260
def common_ancestor(revision_a, revision_b, revision_source):
262
root, ancestors, descendants, common = \
263
combined_graph(revision_a, revision_b, revision_source)
264
except bzrlib.errors.NoCommonRoot:
265
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
267
distances = node_distances (descendants, ancestors, root)
268
farthest = select_farthest(distances, common)
269
if farthest is None or farthest == NULL_REVISION:
270
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
273
class MultipleRevisionSources(object):
274
"""Proxy that looks in multiple branches for revisions."""
275
def __init__(self, *args):
276
object.__init__(self)
277
assert len(args) != 0
278
self._revision_sources = args
280
def get_revision(self, revision_id):
281
for source in self._revision_sources:
283
return source.get_revision(revision_id)
284
except bzrlib.errors.NoSuchRevision, e:
288
def get_intervening_revisions(ancestor_id, rev_id, rev_source,
289
revision_history=None):
290
"""Find the longest line of descent from maybe_ancestor to revision.
291
Revision history is followed where possible.
293
If ancestor_id == rev_id, list will be empty.
294
Otherwise, rev_id will be the last entry. ancestor_id will never appear.
295
If ancestor_id is not an ancestor, NotAncestor will be thrown
297
root, ancestors, descendants = revision_graph(rev_id, rev_source)
298
if len(descendants) == 0:
299
raise NoSuchRevision(rev_source, rev_id)
300
if ancestor_id not in descendants:
301
rev_source.get_revision(ancestor_id)
302
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
303
root_descendants = all_descendants(descendants, ancestor_id)
304
root_descendants.add(ancestor_id)
305
if rev_id not in root_descendants:
306
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
307
distances = node_distances(descendants, ancestors, ancestor_id,
308
root_descendants=root_descendants)
310
def best_ancestor(rev_id):
312
for anc_id in ancestors[rev_id]:
314
distance = distances[anc_id]
317
if revision_history is not None and anc_id in revision_history:
319
elif best is None or distance > best[1]:
320
best = (anc_id, distance)
325
while next != ancestor_id:
327
next = best_ancestor(next)
added
removed
bzrlib/revision.py
