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.
30
def __eq__(self, other):
32
return self.revision_id == other.revision_id and \
33
self.revision_sha1 == other.revision_sha1
34
except AttributeError:
37
def __init__(self, revision_id, revision_sha1=None):
38
self.revision_id = None
39
self.revision_sha1 = None
40
if revision_id == None \
41
or isinstance(revision_id, basestring):
42
self.revision_id = revision_id
44
raise ValueError('bad revision_id %r' % revision_id)
46
if revision_sha1 != None:
47
if isinstance(revision_sha1, basestring) \
48
and len(revision_sha1) == 40:
49
self.revision_sha1 = revision_sha1
51
raise ValueError('bad revision_sha1 %r' % revision_sha1)
55
class Revision(object):
56
"""Single revision on a branch.
58
Revisions may know their revision_hash, but only once they've been
59
written out. This is not stored because you cannot write the hash
60
into the file it describes.
62
After bzr 0.0.5 revisions are allowed to have multiple parents.
65
List of parent revisions, each is a RevisionReference.
68
def __init__(self, inventory_id=None, inventory_sha1=None,
69
revision_id=None, timestamp=None,
70
message=None, timezone=None,
71
committer=None, parents=None):
72
self.inventory_id = inventory_id
73
self.inventory_sha1 = inventory_sha1
74
self.revision_id = revision_id
75
self.timestamp = timestamp
76
self.message = message
77
self.timezone = timezone
78
self.committer = committer
79
if parents is not None:
80
self.parents = parents
84
def __eq__(self, other):
86
return self.inventory_id == other.inventory_id and \
87
self.inventory_sha1 == other.inventory_sha1 and \
88
self.revision_id == other.revision_id and \
89
self.timestamp == other.timestamp and \
90
self.message == other.message and \
91
self.timezone == other.timezone and \
92
self.committer == other.committer and \
93
self.parents == other.parents
94
except AttributeError:
98
return "<Revision id %s>" % self.revision_id
100
def __eq__(self, other):
101
if not isinstance(other, Revision):
103
return (self.inventory_id == other.inventory_id
104
and self.inventory_sha1 == other.inventory_sha1
105
and self.revision_id == other.revision_id
106
and self.timestamp == other.timestamp
107
and self.message == other.message
108
and self.timezone == other.timezone
109
and self.committer == other.committer)
111
def __ne__(self, other):
112
return not self.__eq__(other)
115
REVISION_ID_RE = None
117
def validate_revision_id(rid):
118
"""Check rid is syntactically valid for a revision id."""
119
global REVISION_ID_RE
120
if not REVISION_ID_RE:
122
REVISION_ID_RE = re.compile('[\w:.-]+@[\w%.-]+--?[\w]+--?[0-9a-f]+\Z')
124
if not REVISION_ID_RE.match(rid):
125
raise ValueError("malformed revision-id %r" % rid)
127
def is_ancestor(revision_id, candidate_id, revision_source):
128
"""Return true if candidate_id is an ancestor of revision_id.
129
A false negative will be returned if any intermediate descendent of
130
candidate_id is not present in any of the revision_sources.
132
revisions_source is an object supporting a get_revision operation that
133
behaves like Branch's.
135
if candidate_id is None:
137
for ancestor_id, distance in iter_ancestors(revision_id, revision_source):
138
if ancestor_id == candidate_id:
142
def iter_ancestors(revision_id, revision_source, only_present=False):
143
ancestors = (revision_id,)
145
while len(ancestors) > 0:
147
for ancestor in ancestors:
149
yield ancestor, distance
151
revision = revision_source.get_revision(ancestor)
152
except bzrlib.errors.NoSuchRevision, e:
153
if e.revision == revision_id:
158
yield ancestor, distance
159
new_ancestors.extend([p.revision_id for p in revision.parents])
160
ancestors = new_ancestors
164
def find_present_ancestors(revision_id, revision_source):
165
"""Return the ancestors of a revision present in a branch.
167
It's possible that a branch won't have the complete ancestry of
168
one of its revisions.
172
anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
174
for anc_order, (anc_id, anc_distance) in anc_iter:
175
if not found_ancestors.has_key(anc_id):
176
found_ancestors[anc_id] = (anc_order, anc_distance)
177
return found_ancestors
180
def __get_closest(intersection):
183
for entry in intersection:
184
if entry[0] == intersection[0][0]:
185
matches.append(entry[2])
189
def old_common_ancestor(revision_a, revision_b, revision_source):
190
"""Find the ancestor common to both revisions that is closest to both.
192
from bzrlib.trace import mutter
193
a_ancestors = find_present_ancestors(revision_a, revision_source)
194
b_ancestors = find_present_ancestors(revision_b, revision_source)
197
# a_order is used as a tie-breaker when two equally-good bases are found
198
for revision, (a_order, a_distance) in a_ancestors.iteritems():
199
if b_ancestors.has_key(revision):
200
a_intersection.append((a_distance, a_order, revision))
201
b_intersection.append((b_ancestors[revision][1], a_order, revision))
202
mutter("a intersection: %r" % a_intersection)
203
mutter("b intersection: %r" % b_intersection)
205
a_closest = __get_closest(a_intersection)
206
if len(a_closest) == 0:
208
b_closest = __get_closest(b_intersection)
209
assert len(b_closest) != 0
210
mutter ("a_closest %r" % a_closest)
211
mutter ("b_closest %r" % b_closest)
212
if a_closest[0] in b_closest:
214
elif b_closest[0] in a_closest:
217
raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
220
def revision_graph(revision, revision_source):
221
"""Produce a graph of the ancestry of the specified revision.
222
Return root, ancestors map, descendants map
224
TODO: Produce graphs with the NULL revision as root, so that we can find
225
a common even when trees are not branches don't represent a single line
232
descendants[revision] = {}
233
while len(lines) > 0:
236
if line == NULL_REVISION:
241
rev = revision_source.get_revision(line)
242
parents = [p.revision_id for p in rev.parents]
243
if len(parents) == 0:
244
parents = [NULL_REVISION]
245
except bzrlib.errors.NoSuchRevision:
249
if parents is not None:
250
for parent in parents:
251
if parent not in ancestors:
252
new_lines.add(parent)
253
if parent not in descendants:
254
descendants[parent] = {}
255
descendants[parent][line] = 1
256
if parents is not None:
257
ancestors[line] = set(parents)
259
assert root not in descendants[root]
260
assert root not in ancestors[root]
261
return root, ancestors, descendants
264
def combined_graph(revision_a, revision_b, revision_source):
265
"""Produce a combined ancestry graph.
266
Return graph root, ancestors map, descendants map, set of common nodes"""
267
root, ancestors, descendants = revision_graph(revision_a, revision_source)
268
root_b, ancestors_b, descendants_b = revision_graph(revision_b,
271
raise bzrlib.errors.NoCommonRoot(revision_a, revision_b)
273
for node, node_anc in ancestors_b.iteritems():
274
if node in ancestors:
277
ancestors[node] = set()
278
ancestors[node].update(node_anc)
279
for node, node_dec in descendants_b.iteritems():
280
if node not in descendants:
281
descendants[node] = {}
282
descendants[node].update(node_dec)
283
return root, ancestors, descendants, common
286
def common_ancestor(revision_a, revision_b, revision_source):
288
root, ancestors, descendants, common = \
289
combined_graph(revision_a, revision_b, revision_source)
290
except bzrlib.errors.NoCommonRoot:
291
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
293
distances = node_distances (descendants, ancestors, root)
294
farthest = select_farthest(distances, common)
295
if farthest is None or farthest == NULL_REVISION:
296
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
300
class MultipleRevisionSources(object):
301
"""Proxy that looks in multiple branches for revisions."""
302
def __init__(self, *args):
303
object.__init__(self)
304
assert len(args) != 0
305
self._revision_sources = args
307
def get_revision(self, revision_id):
308
for source in self._revision_sources:
310
return source.get_revision(revision_id)
311
except bzrlib.errors.NoSuchRevision, e:
315
def get_intervening_revisions(ancestor_id, rev_id, rev_source,
316
revision_history=None):
317
"""Find the longest line of descent from maybe_ancestor to revision.
318
Revision history is followed where possible.
320
If ancestor_id == rev_id, list will be empty.
321
Otherwise, rev_id will be the last entry. ancestor_id will never appear.
322
If ancestor_id is not an ancestor, NotAncestor will be thrown
324
root, ancestors, descendants = revision_graph(rev_id, rev_source)
325
if len(descendants) == 0:
326
raise NoSuchRevision(rev_source, rev_id)
327
if ancestor_id not in descendants:
328
rev_source.get_revision(ancestor_id)
329
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
330
root_descendants = all_descendants(descendants, ancestor_id)
331
root_descendants.add(ancestor_id)
332
if rev_id not in root_descendants:
333
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
334
distances = node_distances(descendants, ancestors, ancestor_id,
335
root_descendants=root_descendants)
337
def best_ancestor(rev_id):
339
for anc_id in ancestors[rev_id]:
341
distance = distances[anc_id]
344
if revision_history is not None and anc_id in revision_history:
346
elif best is None or distance > best[1]:
347
best = (anc_id, distance)
352
while next != ancestor_id:
354
next = best_ancestor(next)
added
removed
bzrlib/revision.py
