18
18
import bzrlib.errors
19
from bzrlib.graph import node_distances, select_farthest, all_descendants
21
class RevisionReference(object):
23
Reference to a stored revision.
25
Includes the revision_id and revision_sha1.
29
def __init__(self, revision_id, revision_sha1=None):
30
if revision_id == None \
31
or isinstance(revision_id, basestring):
32
self.revision_id = revision_id
34
raise ValueError('bad revision_id %r' % revision_id)
36
if revision_sha1 != None:
37
if isinstance(revision_sha1, basestring) \
38
and len(revision_sha1) == 40:
39
self.revision_sha1 = revision_sha1
41
raise ValueError('bad revision_sha1 %r' % revision_sha1)
23
45
class Revision(object):
24
46
"""Single revision on a branch.
30
52
After bzr 0.0.5 revisions are allowed to have multiple parents.
33
List of parent revision_ids
55
List of parent revisions, each is a RevisionReference.
36
def __init__(self, revision_id, **args):
37
self.revision_id = revision_id
65
def __init__(self, **args):
38
66
self.__dict__.update(args)
40
self.parent_sha1s = []
42
70
def __repr__(self):
43
71
return "<Revision id %s>" % self.revision_id
65
93
global REVISION_ID_RE
66
94
if not REVISION_ID_RE:
68
REVISION_ID_RE = re.compile('[\w:.-]+@[\w%.-]+--?[\w]+--?[0-9a-f]+\Z')
96
REVISION_ID_RE = re.compile('[\w.-]+@[\w.-]+--?\d+--?[0-9a-f]+\Z')
70
98
if not REVISION_ID_RE.match(rid):
71
99
raise ValueError("malformed revision-id %r" % rid)
74
def is_ancestor(revision_id, candidate_id, branch):
101
def is_ancestor(revision_id, candidate_id, revision_source):
75
102
"""Return true if candidate_id is an ancestor of revision_id.
77
103
A false negative will be returned if any intermediate descendent of
78
104
candidate_id is not present in any of the revision_sources.
80
106
revisions_source is an object supporting a get_revision operation that
81
107
behaves like Branch's.
83
return candidate_id in branch.get_ancestry(revision_id)
110
for ancestor_id, distance in iter_ancestors(revision_id, revision_source):
111
if ancestor_id == candidate_id:
86
115
def iter_ancestors(revision_id, revision_source, only_present=False):
87
116
ancestors = (revision_id,)
161
190
raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
162
191
return a_closest[0]
164
def revision_graph(revision, revision_source):
165
"""Produce a graph of the ancestry of the specified revision.
166
Return root, ancestors map, descendants map
168
TODO: Produce graphs with the NULL revision as root, so that we can find
169
a common even when trees are not branches don't represent a single line
176
descendants[revision] = {}
177
while len(lines) > 0:
180
if line == NULL_REVISION:
185
rev = revision_source.get_revision(line)
186
parents = list(rev.parent_ids)
187
if len(parents) == 0:
188
parents = [NULL_REVISION]
189
except bzrlib.errors.NoSuchRevision:
193
if parents is not None:
194
for parent in parents:
195
if parent not in ancestors:
196
new_lines.add(parent)
197
if parent not in descendants:
198
descendants[parent] = {}
199
descendants[parent][line] = 1
200
if parents is not None:
201
ancestors[line] = set(parents)
203
assert root not in descendants[root]
204
assert root not in ancestors[root]
205
return root, ancestors, descendants
208
def combined_graph(revision_a, revision_b, revision_source):
209
"""Produce a combined ancestry graph.
210
Return graph root, ancestors map, descendants map, set of common nodes"""
211
root, ancestors, descendants = revision_graph(revision_a, revision_source)
212
root_b, ancestors_b, descendants_b = revision_graph(revision_b,
215
raise bzrlib.errors.NoCommonRoot(revision_a, revision_b)
217
for node, node_anc in ancestors_b.iteritems():
218
if node in ancestors:
221
ancestors[node] = set()
222
ancestors[node].update(node_anc)
223
for node, node_dec in descendants_b.iteritems():
224
if node not in descendants:
225
descendants[node] = {}
226
descendants[node].update(node_dec)
227
return root, ancestors, descendants, common
230
def common_ancestor(revision_a, revision_b, revision_source):
232
root, ancestors, descendants, common = \
233
combined_graph(revision_a, revision_b, revision_source)
234
except bzrlib.errors.NoCommonRoot:
235
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
237
distances = node_distances (descendants, ancestors, root)
238
farthest = select_farthest(distances, common)
239
if farthest is None or farthest == NULL_REVISION:
240
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
244
193
class MultipleRevisionSources(object):
245
194
"""Proxy that looks in multiple branches for revisions."""
246
195
def __init__(self, *args):
265
214
Otherwise, rev_id will be the last entry. ancestor_id will never appear.
266
215
If ancestor_id is not an ancestor, NotAncestor will be thrown
268
root, ancestors, descendants = revision_graph(rev_id, rev_source)
269
if len(descendants) == 0:
270
raise NoSuchRevision(rev_source, rev_id)
271
if ancestor_id not in descendants:
272
rev_source.get_revision(ancestor_id)
273
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
274
root_descendants = all_descendants(descendants, ancestor_id)
275
root_descendants.add(ancestor_id)
276
if rev_id not in root_descendants:
277
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
278
distances = node_distances(descendants, ancestors, ancestor_id,
279
root_descendants=root_descendants)
281
def best_ancestor(rev_id):
283
for anc_id in ancestors[rev_id]:
285
distance = distances[anc_id]
288
if revision_history is not None and anc_id in revision_history:
290
elif best is None or distance > best[1]:
291
best = (anc_id, distance)
296
while next != ancestor_id:
298
next = best_ancestor(next)
217
[rev_source.get_revision(r) for r in (ancestor_id, rev_id)]
218
if ancestor_id == rev_id:
220
def historical_lines(line):
221
"""Return a tuple of historical/non_historical lines, for sorting.
222
The non_historical count is negative, since non_historical lines are
227
for revision in line:
228
if revision in revision_history:
232
return good_count, bad_count
234
successful_lines = []
235
while len(active) > 0:
238
parent_ids = [p.revision_id for p in
239
rev_source.get_revision(line[-1]).parents]
240
for parent in parent_ids:
242
if parent == ancestor_id:
243
successful_lines.append(line_copy)
245
line_copy.append(parent)
246
new_active.append(line_copy)
248
if len(successful_lines) == 0:
249
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
250
for line in successful_lines:
252
if revision_history is not None:
253
by_historical_lines = []
254
for line in successful_lines:
255
count = historical_lines(line)
256
by_historical_lines.append((count, line))
257
by_historical_lines.sort()
258
if by_historical_lines[-1][0][0] > 0:
259
return by_historical_lines[-1][1]
260
assert len(successful_lines)
261
successful_lines.sort(cmp, len)
262
return successful_lines[-1]
added
removed
bzrlib/revision.py
