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, node_distances, 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)
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:
287
if parents is not None:
288
for parent in parents:
289
if parent not in ancestors:
290
new_lines.add(parent)
291
if parent not in descendants:
292
descendants[parent] = {}
293
descendants[parent][line] = 1
294
if parents is not None:
295
ancestors[line] = set(parents)
297
assert root not in descendants[root]
298
assert root not in ancestors[root]
299
return root, ancestors, descendants
301
def combined_graph(revision_a, revision_b, revision_source):
302
"""Produce a combined ancestry graph.
303
Return graph root, ancestors map, descendants map, set of common nodes"""
304
root, ancestors, descendants = revision_graph(revision_a, revision_source)
305
root_b, ancestors_b, descendants_b = revision_graph(revision_b,
307
assert root == root_b
309
for node, node_anc in ancestors_b.iteritems():
310
if node in ancestors:
313
ancestors[node] = set()
314
ancestors[node].update(node_anc)
315
for node, node_dec in descendants_b.iteritems():
316
if node not in descendants:
317
descendants[node] = set()
318
descendants[node].update(node_dec)
319
return root, ancestors, descendants, common
321
def common_ancestor(revision_a, revision_b, revision_source):
322
root, ancestors, descendants, common = \
323
combined_graph(revision_a, revision_b, revision_source)
324
nodes = farthest_nodes(descendants, ancestors, root)
329
class MultipleRevisionSources(object):
330
"""Proxy that looks in multiple branches for revisions."""
331
def __init__(self, *args):
332
object.__init__(self)
333
assert len(args) != 0
334
self._revision_sources = args
336
def get_revision(self, revision_id):
337
for source in self._revision_sources:
339
return source.get_revision(revision_id)
340
except bzrlib.errors.NoSuchRevision, e:
344
def get_intervening_revisions(ancestor_id, rev_id, rev_source,
345
revision_history=None):
346
"""Find the longest line of descent from maybe_ancestor to revision.
347
Revision history is followed where possible.
349
If ancestor_id == rev_id, list will be empty.
350
Otherwise, rev_id will be the last entry. ancestor_id will never appear.
351
If ancestor_id is not an ancestor, NotAncestor will be thrown
353
root, ancestors, descendants = revision_graph(rev_id, rev_source)
354
if len(descendants) == 0:
355
raise NoSuchRevision(rev_source, rev_id)
356
if ancestor_id not in descendants:
357
rev_source.get_revision(ancestor_id)
358
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
359
root_descendants = all_descendants(descendants, ancestor_id)
360
root_descendants.add(ancestor_id)
361
if rev_id not in root_descendants:
362
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
363
distances = node_distances(descendants, ancestors, ancestor_id,
364
root_descendants=root_descendants)
366
def best_ancestor(rev_id):
368
for anc_id in ancestors[rev_id]:
370
distance = distances[anc_id]
373
if revision_history is not None and anc_id in revision_history:
375
elif best is None or distance > best[1]:
376
best = (anc_id, distance)
381
while next != ancestor_id:
383
next = best_ancestor(next)
added
removed
bzrlib/revision.py
