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 farthest_nodes
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)
45
class Revision(object):
46
"""Single revision on a branch.
48
Revisions may know their revision_hash, but only once they've been
49
written out. This is not stored because you cannot write the hash
50
into the file it describes.
52
After bzr 0.0.5 revisions are allowed to have multiple parents.
55
List of parent revisions, each is a RevisionReference.
65
def __init__(self, **args):
66
self.__dict__.update(args)
71
return "<Revision id %s>" % self.revision_id
75
from bzrlib.xml import Element, SubElement
77
root = Element('revision',
78
committer = self.committer,
79
timestamp = '%.9f' % self.timestamp,
80
revision_id = self.revision_id,
81
inventory_id = self.inventory_id,
82
inventory_sha1 = self.inventory_sha1,
85
root.set('timezone', str(self.timezone))
88
msg = SubElement(root, 'message')
89
msg.text = self.message
93
pelts = SubElement(root, 'parents')
94
pelts.tail = pelts.text = '\n'
95
for rr in self.parents:
96
assert isinstance(rr, RevisionReference)
97
p = SubElement(pelts, 'revision_ref')
100
p.set('revision_id', rr.revision_id)
102
p.set('revision_sha1', rr.revision_sha1)
107
def from_element(cls, elt):
108
return unpack_revision(elt)
110
from_element = classmethod(from_element)
114
def unpack_revision(elt):
115
"""Convert XML element into Revision object."""
116
# <changeset> is deprecated...
117
if elt.tag not in ('revision', 'changeset'):
118
raise bzrlib.errors.BzrError("unexpected tag in revision file: %r" % elt)
120
rev = Revision(committer = elt.get('committer'),
121
timestamp = float(elt.get('timestamp')),
122
revision_id = elt.get('revision_id'),
123
inventory_id = elt.get('inventory_id'),
124
inventory_sha1 = elt.get('inventory_sha1')
127
precursor = elt.get('precursor')
128
precursor_sha1 = elt.get('precursor_sha1')
130
pelts = elt.find('parents')
134
assert p.tag == 'revision_ref', \
135
"bad parent node tag %r" % p.tag
136
rev_ref = RevisionReference(p.get('revision_id'),
137
p.get('revision_sha1'))
138
rev.parents.append(rev_ref)
142
prec_parent = rev.parents[0].revision_id
143
assert prec_parent == precursor
145
# revisions written prior to 0.0.5 have a single precursor
146
# give as an attribute
147
rev_ref = RevisionReference(precursor, precursor_sha1)
148
rev.parents.append(rev_ref)
150
v = elt.get('timezone')
151
rev.timezone = v and int(v)
153
rev.message = elt.findtext('message') # text of <message>
158
REVISION_ID_RE = None
160
def validate_revision_id(rid):
161
"""Check rid is syntactically valid for a revision id."""
162
global REVISION_ID_RE
163
if not REVISION_ID_RE:
165
REVISION_ID_RE = re.compile('[\w.-]+@[\w.-]+--?\d+--?[0-9a-f]+\Z')
167
if not REVISION_ID_RE.match(rid):
168
raise ValueError("malformed revision-id %r" % rid)
170
def is_ancestor(revision_id, candidate_id, revision_source):
171
"""Return true if candidate_id is an ancestor of revision_id.
172
A false negative will be returned if any intermediate descendent of
173
candidate_id is not present in any of the revision_sources.
175
revisions_source is an object supporting a get_revision operation that
176
behaves like Branch's.
179
for ancestor_id, distance in iter_ancestors(revision_id, revision_source):
180
if ancestor_id == candidate_id:
184
def iter_ancestors(revision_id, revision_source, only_present=False):
185
ancestors = (revision_id,)
187
while len(ancestors) > 0:
189
for ancestor in ancestors:
191
yield ancestor, distance
193
revision = revision_source.get_revision(ancestor)
194
except bzrlib.errors.NoSuchRevision, e:
195
if e.revision == revision_id:
200
yield ancestor, distance
201
new_ancestors.extend([p.revision_id for p in revision.parents])
202
ancestors = new_ancestors
206
def find_present_ancestors(revision_id, revision_source):
207
"""Return the ancestors of a revision present in a branch.
209
It's possible that a branch won't have the complete ancestry of
210
one of its revisions.
214
anc_iter = enumerate(iter_ancestors(revision_id, revision_source,
216
for anc_order, (anc_id, anc_distance) in anc_iter:
217
if not found_ancestors.has_key(anc_id):
218
found_ancestors[anc_id] = (anc_order, anc_distance)
219
return found_ancestors
222
def __get_closest(intersection):
225
for entry in intersection:
226
if entry[0] == intersection[0][0]:
227
matches.append(entry[2])
231
def old_common_ancestor(revision_a, revision_b, revision_source):
232
"""Find the ancestor common to both revisions that is closest to both.
234
from bzrlib.trace import mutter
235
a_ancestors = find_present_ancestors(revision_a, revision_source)
236
b_ancestors = find_present_ancestors(revision_b, revision_source)
239
# a_order is used as a tie-breaker when two equally-good bases are found
240
for revision, (a_order, a_distance) in a_ancestors.iteritems():
241
if b_ancestors.has_key(revision):
242
a_intersection.append((a_distance, a_order, revision))
243
b_intersection.append((b_ancestors[revision][1], a_order, revision))
244
mutter("a intersection: %r" % a_intersection)
245
mutter("b intersection: %r" % b_intersection)
247
a_closest = __get_closest(a_intersection)
248
if len(a_closest) == 0:
250
b_closest = __get_closest(b_intersection)
251
assert len(b_closest) != 0
252
mutter ("a_closest %r" % a_closest)
253
mutter ("b_closest %r" % b_closest)
254
if a_closest[0] in b_closest:
256
elif b_closest[0] in a_closest:
259
raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
262
def revision_graph(revision, revision_source):
263
"""Produce a graph of the ancestry of the specified revision.
264
Return root, ancestors map, descendants map
266
TODO: Produce graphs with the NULL revision as root, so that we can find
267
a common even when trees are not branches don't represent a single line
274
descendants[revision] = {}
275
while len(lines) > 0:
279
rev = revision_source.get_revision(line)
280
parents = [p.revision_id for p in rev.parents]
281
if len(parents) == 0:
283
except bzrlib.errors.NoSuchRevision:
285
if parents is not None:
286
for parent in parents:
287
if parent not in ancestors:
288
new_lines.add(parent)
289
if parent not in descendants:
290
descendants[parent] = {}
291
descendants[parent][line] = 1
292
if parents is not None:
293
ancestors[line] = set(parents)
295
assert root not in descendants[root]
296
assert root not in ancestors[root]
297
return root, ancestors, descendants
299
def combined_graph(revision_a, revision_b, revision_source):
300
"""Produce a combined ancestry graph.
301
Return graph root, ancestors map, descendants map, set of common nodes"""
302
root, ancestors, descendants = revision_graph(revision_a, revision_source)
303
root_b, ancestors_b, descendants_b = revision_graph(revision_b,
305
assert root == root_b
307
for node, node_anc in ancestors_b.iteritems():
308
if node in ancestors:
311
ancestors[node] = set()
312
ancestors[node].update(node_anc)
313
for node, node_dec in descendants_b.iteritems():
314
if node not in descendants:
315
descendants[node] = set()
316
descendants[node].update(node_dec)
317
return root, ancestors, descendants, common
319
def common_ancestor(revision_a, revision_b, revision_source):
320
root, ancestors, descendants, common = \
321
combined_graph(revision_a, revision_b, revision_source)
322
nodes = farthest_nodes(descendants, ancestors, root)
327
class MultipleRevisionSources(object):
328
"""Proxy that looks in multiple branches for revisions."""
329
def __init__(self, *args):
330
object.__init__(self)
331
assert len(args) != 0
332
self._revision_sources = args
334
def get_revision(self, revision_id):
335
for source in self._revision_sources:
337
return source.get_revision(revision_id)
338
except bzrlib.errors.NoSuchRevision, e:
342
def get_intervening_revisions(ancestor_id, rev_id, rev_source,
343
revision_history=None):
344
"""Find the longest line of descent from maybe_ancestor to revision.
345
Revision history is followed where possible.
347
If ancestor_id == rev_id, list will be empty.
348
Otherwise, rev_id will be the last entry. ancestor_id will never appear.
349
If ancestor_id is not an ancestor, NotAncestor will be thrown
351
[rev_source.get_revision(r) for r in (ancestor_id, rev_id)]
352
if ancestor_id == rev_id:
354
def historical_lines(line):
355
"""Return a tuple of historical/non_historical lines, for sorting.
356
The non_historical count is negative, since non_historical lines are
361
for revision in line:
362
if revision in revision_history:
366
return good_count, bad_count
368
successful_lines = []
369
while len(active) > 0:
372
parent_ids = [p.revision_id for p in
373
rev_source.get_revision(line[-1]).parents]
374
for parent in parent_ids:
376
if parent == ancestor_id:
377
successful_lines.append(line_copy)
379
line_copy.append(parent)
380
new_active.append(line_copy)
382
if len(successful_lines) == 0:
383
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
384
for line in successful_lines:
386
if revision_history is not None:
387
by_historical_lines = []
388
for line in successful_lines:
389
count = historical_lines(line)
390
by_historical_lines.append((count, line))
391
by_historical_lines.sort()
392
if by_historical_lines[-1][0][0] > 0:
393
return by_historical_lines[-1][1]
394
assert len(successful_lines)
395
successful_lines.sort(cmp, len)
396
return successful_lines[-1]
added
removed
bzrlib/revision.py
