« back to all changes in this revision
Viewing changes to bzrlib/revision.py
- browse files at revision 1092.2.14
- compare with another revision
- download diff
- download tarball
- view history from revision 1092.2.14
- Committer: Robert Collins
- Date: 2005-09-13 09:39:26 UTC
- mto: This revision was merged to the branch mainline in revision 1397.
- Revision ID: robertc@robertcollins.net-20050913093926-7edba69aff28352d
bugfix symlink support - read the link from the abspath not relative path
- files added:
- bzrlib/graph.py
- files removed:
- bzrlib/meta_store.py
- files modified:
- NEWS
added
removed
bzrlib/revision.py
16
16
17
17
18
18
import bzrlib.errors
19
19
from bzrlib.graph import farthest_nodes, node_distances, all_descendants
20
20
21
21
class RevisionReference(object):
22
22
"""
24
24
25
25
Includes the revision_id and revision_sha1.
26
26
"""
27
revision_id = None
28
revision_sha1 = None
27
28
def __eq__(self, other):
29
try:
30
return self.revision_id == other.revision_id and \
31
self.revision_sha1 == other.revision_sha1
32
except AttributeError:
33
return False
34
29
35
def __init__(self, revision_id, revision_sha1=None):
36
self.revision_id = None
37
self.revision_sha1 = None
30
38
if revision_id == None \
31
39
or isinstance(revision_id, basestring):
32
40
self.revision_id = revision_id
54
62
parents
55
63
List of parent revisions, each is a RevisionReference.
56
64
"""
57
inventory_id = None
58
inventory_sha1 = None
59
revision_id = None
60
timestamp = None
61
message = None
62
timezone = None
63
committer = None
64
65
65
def __init__(self, **args):
66
self.__dict__.update(args)
67
self.parents = []
66
def __init__(self, inventory_id=None, inventory_sha1=None,
67
revision_id=None, timestamp=None,
68
message=None, timezone=None,
69
committer=None, parents=None):
70
self.inventory_id = inventory_id
71
self.inventory_sha1 = inventory_sha1
72
self.revision_id = revision_id
73
self.timestamp = timestamp
74
self.message = message
75
self.timezone = timezone
76
self.committer = committer
77
if parents is not None:
78
self.parents = parents
79
else:
80
self.parents = []
68
81
82
def __eq__(self, other):
83
try:
84
return self.inventory_id == other.inventory_id and \
85
self.inventory_sha1 == other.inventory_sha1 and \
86
self.revision_id == other.revision_id and \
87
self.timestamp == other.timestamp and \
88
self.message == other.message and \
89
self.timezone == other.timezone and \
90
self.committer == other.committer and \
91
self.parents == other.parents
92
except AttributeError:
93
return False
69
94
70
95
def __repr__(self):
71
96
return "<Revision id %s>" % self.revision_id
72
97
73
74
def to_element(self):
75
from bzrlib.xml import Element, SubElement
76
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,
83
)
84
if self.timezone:
85
root.set('timezone', str(self.timezone))
86
root.text = '\n'
87
88
msg = SubElement(root, 'message')
89
msg.text = self.message
90
msg.tail = '\n'
91
92
if self.parents:
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')
98
p.tail = '\n'
99
assert rr.revision_id
100
p.set('revision_id', rr.revision_id)
101
if rr.revision_sha1:
102
p.set('revision_sha1', rr.revision_sha1)
103
104
return root
105
106
107
def from_element(cls, elt):
108
return unpack_revision(elt)
109
110
from_element = classmethod(from_element)
111
112
113
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)
119
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')
125
)
126
127
precursor = elt.get('precursor')
128
precursor_sha1 = elt.get('precursor_sha1')
129
130
pelts = elt.find('parents')
131
132
if pelts:
133
for p in pelts:
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)
139
140
if precursor:
141
# must be consistent
142
prec_parent = rev.parents[0].revision_id
143
assert prec_parent == precursor
144
elif 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)
149
150
v = elt.get('timezone')
151
rev.timezone = v and int(v)
152
153
rev.message = elt.findtext('message') # text of <message>
154
return rev
155
98
def __eq__(self, other):
99
if not isinstance(other, Revision):
100
return False
101
return (self.inventory_id == other.inventory_id
102
and self.inventory_sha1 == other.inventory_sha1
103
and self.revision_id == other.revision_id
104
and self.timestamp == other.timestamp
105
and self.message == other.message
106
and self.timezone == other.timezone
107
and self.committer == other.committer)
108
109
def __ne__(self, other):
110
return not self.__eq__(other)
156
111
157
112
158
113
REVISION_ID_RE = None
162
117
global REVISION_ID_RE
163
118
if not REVISION_ID_RE:
164
119
import re
165
REVISION_ID_RE = re.compile('[\w.-]+@[\w.-]+--?\d+--?[0-9a-f]+\Z')
120
REVISION_ID_RE = re.compile('[\w:.-]+@[\w%.-]+--?[\w]+--?[0-9a-f]+\Z')
166
121
167
122
if not REVISION_ID_RE.match(rid):
168
123
raise ValueError("malformed revision-id %r" % rid)
228
183
return matches
229
184
230
185
231
def common_ancestor(revision_a, revision_b, revision_source):
186
def old_common_ancestor(revision_a, revision_b, revision_source):
232
187
"""Find the ancestor common to both revisions that is closest to both.
233
188
"""
234
189
from bzrlib.trace import mutter
259
214
raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
260
215
return a_closest[0]
261
216
217
def revision_graph(revision, revision_source):
218
"""Produce a graph of the ancestry of the specified revision.
219
Return root, ancestors map, descendants map
220
221
TODO: Produce graphs with the NULL revision as root, so that we can find
222
a common even when trees are not branches don't represent a single line
223
of descent.
224
"""
225
ancestors = {}
226
descendants = {}
227
lines = [revision]
228
root = None
229
descendants[revision] = {}
230
while len(lines) > 0:
231
new_lines = set()
232
for line in lines:
233
try:
234
rev = revision_source.get_revision(line)
235
parents = [p.revision_id for p in rev.parents]
236
if len(parents) == 0:
237
root = line
238
except bzrlib.errors.NoSuchRevision:
239
if line == revision:
240
raise
241
parents = None
242
if parents is not None:
243
for parent in parents:
244
if parent not in ancestors:
245
new_lines.add(parent)
246
if parent not in descendants:
247
descendants[parent] = {}
248
descendants[parent][line] = 1
249
if parents is not None:
250
ancestors[line] = set(parents)
251
lines = new_lines
252
assert root not in descendants[root]
253
assert root not in ancestors[root]
254
return root, ancestors, descendants
255
256
def combined_graph(revision_a, revision_b, revision_source):
257
"""Produce a combined ancestry graph.
258
Return graph root, ancestors map, descendants map, set of common nodes"""
259
root, ancestors, descendants = revision_graph(revision_a, revision_source)
260
root_b, ancestors_b, descendants_b = revision_graph(revision_b,
261
revision_source)
262
assert root == root_b
263
common = set()
264
for node, node_anc in ancestors_b.iteritems():
265
if node in ancestors:
266
common.add(node)
267
else:
268
ancestors[node] = set()
269
ancestors[node].update(node_anc)
270
for node, node_dec in descendants_b.iteritems():
271
if node not in descendants:
272
descendants[node] = set()
273
descendants[node].update(node_dec)
274
return root, ancestors, descendants, common
275
276
def common_ancestor(revision_a, revision_b, revision_source):
277
root, ancestors, descendants, common = \
278
combined_graph(revision_a, revision_b, revision_source)
279
nodes = farthest_nodes(descendants, ancestors, root)
280
for node in nodes:
281
if node in common:
282
return node
283
262
284
class MultipleRevisionSources(object):
263
285
"""Proxy that looks in multiple branches for revisions."""
264
286
def __init__(self, *args):
283
305
Otherwise, rev_id will be the last entry. ancestor_id will never appear.
284
306
If ancestor_id is not an ancestor, NotAncestor will be thrown
285
307
"""
286
[rev_source.get_revision(r) for r in (ancestor_id, rev_id)]
287
if ancestor_id == rev_id:
288
return []
289
def historical_lines(line):
290
"""Return a tuple of historical/non_historical lines, for sorting.
291
The non_historical count is negative, since non_historical lines are
292
a bad thing.
293
"""
294
good_count = 0
295
bad_count = 0
296
for revision in line:
297
if revision in revision_history:
298
good_count += 1
299
else:
300
bad_count -= 1
301
return good_count, bad_count
302
active = [[rev_id]]
303
successful_lines = []
304
while len(active) > 0:
305
new_active = []
306
for line in active:
307
parent_ids = [p.revision_id for p in
308
rev_source.get_revision(line[-1]).parents]
309
for parent in parent_ids:
310
line_copy = line[:]
311
if parent == ancestor_id:
312
successful_lines.append(line_copy)
313
else:
314
line_copy.append(parent)
315
new_active.append(line_copy)
316
active = new_active
317
if len(successful_lines) == 0:
318
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
319
for line in successful_lines:
320
line.reverse()
321
if revision_history is not None:
322
by_historical_lines = []
323
for line in successful_lines:
324
count = historical_lines(line)
325
by_historical_lines.append((count, line))
326
by_historical_lines.sort()
327
if by_historical_lines[-1][0][0] > 0:
328
return by_historical_lines[-1][1]
329
assert len(successful_lines)
330
successful_lines.sort(cmp, len)
331
return successful_lines[-1]
308
root, ancestors, descendants = revision_graph(rev_id, rev_source)
309
if len(descendants) == 0:
310
raise NoSuchRevision(rev_source, rev_id)
311
if ancestor_id not in descendants:
312
rev_source.get_revision(ancestor_id)
313
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
314
root_descendants = all_descendants(descendants, ancestor_id)
315
root_descendants.add(ancestor_id)
316
if rev_id not in root_descendants:
317
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
318
distances = node_distances(descendants, ancestors, ancestor_id,
319
root_descendants=root_descendants)
320
321
def best_ancestor(rev_id):
322
best = None
323
for anc_id in ancestors[rev_id]:
324
try:
325
distance = distances[anc_id]
326
except KeyError:
327
continue
328
if revision_history is not None and anc_id in revision_history:
329
return anc_id
330
elif best is None or distance > best[1]:
331
best = (anc_id, distance)
332
return best[0]
333
334
next = rev_id
335
path = []
336
while next != ancestor_id:
337
path.append(next)
338
next = best_ancestor(next)
339
path.reverse()
340
return path
Loggerhead is a web-based interface for Breezy
Version: 2.0.1