184
by mbp at sourcefrog
pychecker fixups |
1 |
# (C) 2005 Canonical
|
1
by mbp at sourcefrog
import from baz patch-364 |
2 |
|
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.
|
|
7 |
||
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.
|
|
12 |
||
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
|
|
16 |
||
17 |
||
974.1.26
by aaron.bentley at utoronto
merged mbp@sourcefrog.net-20050817233101-0939da1cf91f2472 |
18 |
import bzrlib.errors |
974.1.87
by Aaron Bentley
Refactored and documented graph stuff |
19 |
from bzrlib.graph import node_distances, select_farthest, all_descendants |
8
by mbp at sourcefrog
store committer's timezone in revision and show |
20 |
|
802
by Martin Pool
- Remove XMLMixin class in favour of simple pack_xml, unpack_xml functions |
21 |
class RevisionReference(object): |
696
by Martin Pool
- Refactor revision deserialization code |
22 |
"""
|
23 |
Reference to a stored revision.
|
|
24 |
||
25 |
Includes the revision_id and revision_sha1.
|
|
26 |
"""
|
|
27 |
revision_id = None |
|
28 |
revision_sha1 = None |
|
816
by Martin Pool
- don't write precursor field in new revision xml |
29 |
def __init__(self, revision_id, revision_sha1=None): |
696
by Martin Pool
- Refactor revision deserialization code |
30 |
if revision_id == None \ |
31 |
or isinstance(revision_id, basestring): |
|
32 |
self.revision_id = revision_id |
|
33 |
else: |
|
34 |
raise ValueError('bad revision_id %r' % revision_id) |
|
35 |
||
36 |
if revision_sha1 != None: |
|
37 |
if isinstance(revision_sha1, basestring) \ |
|
38 |
and len(revision_sha1) == 40: |
|
39 |
self.revision_sha1 = revision_sha1 |
|
40 |
else: |
|
41 |
raise ValueError('bad revision_sha1 %r' % revision_sha1) |
|
42 |
||
43 |
||
44 |
||
802
by Martin Pool
- Remove XMLMixin class in favour of simple pack_xml, unpack_xml functions |
45 |
class Revision(object): |
1
by mbp at sourcefrog
import from baz patch-364 |
46 |
"""Single revision on a branch.
|
47 |
||
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.
|
|
51 |
||
697
by Martin Pool
- write out parent list for new revisions |
52 |
After bzr 0.0.5 revisions are allowed to have multiple parents.
|
696
by Martin Pool
- Refactor revision deserialization code |
53 |
|
54 |
parents
|
|
700
by Martin Pool
doc |
55 |
List of parent revisions, each is a RevisionReference.
|
1
by mbp at sourcefrog
import from baz patch-364 |
56 |
"""
|
696
by Martin Pool
- Refactor revision deserialization code |
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 |
||
1
by mbp at sourcefrog
import from baz patch-364 |
65 |
def __init__(self, **args): |
66 |
self.__dict__.update(args) |
|
696
by Martin Pool
- Refactor revision deserialization code |
67 |
self.parents = [] |
68 |
||
1
by mbp at sourcefrog
import from baz patch-364 |
69 |
|
70 |
def __repr__(self): |
|
184
by mbp at sourcefrog
pychecker fixups |
71 |
return "<Revision id %s>" % self.revision_id |
1
by mbp at sourcefrog
import from baz patch-364 |
72 |
|
1185
by Martin Pool
- add xml round-trip test for revisions |
73 |
def __eq__(self, other): |
74 |
if not isinstance(other, Revision): |
|
75 |
return False |
|
76 |
return (self.inventory_id == other.inventory_id |
|
77 |
and self.inventory_sha1 == other.inventory_sha1 |
|
78 |
and self.revision_id == other.revision_id |
|
79 |
and self.timestamp == other.timestamp |
|
80 |
and self.message == other.message |
|
81 |
and self.timezone == other.timezone |
|
82 |
and self.committer == other.committer) |
|
83 |
||
84 |
def __ne__(self, other): |
|
85 |
return not self.__eq__(other) |
|
86 |
||
1
by mbp at sourcefrog
import from baz patch-364 |
87 |
|
810
by Martin Pool
- New validate_revision_id function |
88 |
|
89 |
REVISION_ID_RE = None |
|
90 |
||
91 |
def validate_revision_id(rid): |
|
92 |
"""Check rid is syntactically valid for a revision id."""
|
|
93 |
global REVISION_ID_RE |
|
94 |
if not REVISION_ID_RE: |
|
95 |
import re |
|
814
by Martin Pool
- allow doubled-dashes in revision ids |
96 |
REVISION_ID_RE = re.compile('[\w.-]+@[\w.-]+--?\d+--?[0-9a-f]+\Z') |
810
by Martin Pool
- New validate_revision_id function |
97 |
|
98 |
if not REVISION_ID_RE.match(rid): |
|
99 |
raise ValueError("malformed revision-id %r" % rid) |
|
974.1.26
by aaron.bentley at utoronto
merged mbp@sourcefrog.net-20050817233101-0939da1cf91f2472 |
100 |
|
101 |
def is_ancestor(revision_id, candidate_id, revision_source): |
|
102 |
"""Return true if candidate_id is an ancestor of revision_id.
|
|
103 |
A false negative will be returned if any intermediate descendent of
|
|
104 |
candidate_id is not present in any of the revision_sources.
|
|
810
by Martin Pool
- New validate_revision_id function |
105 |
|
974.1.26
by aaron.bentley at utoronto
merged mbp@sourcefrog.net-20050817233101-0939da1cf91f2472 |
106 |
revisions_source is an object supporting a get_revision operation that
|
107 |
behaves like Branch's.
|
|
108 |
"""
|
|
109 |
||
974.1.35
by aaron.bentley at utoronto
Added revision-based common-ancestor checking |
110 |
for ancestor_id, distance in iter_ancestors(revision_id, revision_source): |
111 |
if ancestor_id == candidate_id: |
|
112 |
return True |
|
113 |
return False |
|
114 |
||
115 |
def iter_ancestors(revision_id, revision_source, only_present=False): |
|
974.1.26
by aaron.bentley at utoronto
merged mbp@sourcefrog.net-20050817233101-0939da1cf91f2472 |
116 |
ancestors = (revision_id,) |
974.1.35
by aaron.bentley at utoronto
Added revision-based common-ancestor checking |
117 |
distance = 0 |
974.1.26
by aaron.bentley at utoronto
merged mbp@sourcefrog.net-20050817233101-0939da1cf91f2472 |
118 |
while len(ancestors) > 0: |
119 |
new_ancestors = [] |
|
120 |
for ancestor in ancestors: |
|
974.1.35
by aaron.bentley at utoronto
Added revision-based common-ancestor checking |
121 |
if not only_present: |
122 |
yield ancestor, distance |
|
974.1.26
by aaron.bentley at utoronto
merged mbp@sourcefrog.net-20050817233101-0939da1cf91f2472 |
123 |
try: |
124 |
revision = revision_source.get_revision(ancestor) |
|
125 |
except bzrlib.errors.NoSuchRevision, e: |
|
126 |
if e.revision == revision_id: |
|
127 |
raise
|
|
128 |
else: |
|
129 |
continue
|
|
974.1.35
by aaron.bentley at utoronto
Added revision-based common-ancestor checking |
130 |
if only_present: |
131 |
yield ancestor, distance |
|
974.1.26
by aaron.bentley at utoronto
merged mbp@sourcefrog.net-20050817233101-0939da1cf91f2472 |
132 |
new_ancestors.extend([p.revision_id for p in revision.parents]) |
133 |
ancestors = new_ancestors |
|
974.1.35
by aaron.bentley at utoronto
Added revision-based common-ancestor checking |
134 |
distance += 1 |
135 |
||
136 |
||
137 |
def find_present_ancestors(revision_id, revision_source): |
|
1133
by Martin Pool
doc |
138 |
"""Return the ancestors of a revision present in a branch.
|
139 |
||
140 |
It's possible that a branch won't have the complete ancestry of
|
|
141 |
one of its revisions.
|
|
142 |
||
143 |
"""
|
|
974.1.35
by aaron.bentley at utoronto
Added revision-based common-ancestor checking |
144 |
found_ancestors = {} |
145 |
anc_iter = enumerate(iter_ancestors(revision_id, revision_source, |
|
146 |
only_present=True)) |
|
147 |
for anc_order, (anc_id, anc_distance) in anc_iter: |
|
148 |
if not found_ancestors.has_key(anc_id): |
|
149 |
found_ancestors[anc_id] = (anc_order, anc_distance) |
|
150 |
return found_ancestors |
|
151 |
||
1153
by Martin Pool
- clean up some code in revision.py |
152 |
|
153 |
def __get_closest(intersection): |
|
154 |
intersection.sort() |
|
155 |
matches = [] |
|
156 |
for entry in intersection: |
|
157 |
if entry[0] == intersection[0][0]: |
|
158 |
matches.append(entry[2]) |
|
159 |
return matches |
|
160 |
||
974.1.35
by aaron.bentley at utoronto
Added revision-based common-ancestor checking |
161 |
|
974.1.65
by Aaron Bentley
Cleanup and test-fixing |
162 |
def old_common_ancestor(revision_a, revision_b, revision_source): |
974.1.35
by aaron.bentley at utoronto
Added revision-based common-ancestor checking |
163 |
"""Find the ancestor common to both revisions that is closest to both.
|
164 |
"""
|
|
165 |
from bzrlib.trace import mutter |
|
166 |
a_ancestors = find_present_ancestors(revision_a, revision_source) |
|
167 |
b_ancestors = find_present_ancestors(revision_b, revision_source) |
|
168 |
a_intersection = [] |
|
169 |
b_intersection = [] |
|
170 |
# a_order is used as a tie-breaker when two equally-good bases are found
|
|
171 |
for revision, (a_order, a_distance) in a_ancestors.iteritems(): |
|
172 |
if b_ancestors.has_key(revision): |
|
173 |
a_intersection.append((a_distance, a_order, revision)) |
|
174 |
b_intersection.append((b_ancestors[revision][1], a_order, revision)) |
|
175 |
mutter("a intersection: %r" % a_intersection) |
|
176 |
mutter("b intersection: %r" % b_intersection) |
|
177 |
||
1153
by Martin Pool
- clean up some code in revision.py |
178 |
a_closest = __get_closest(a_intersection) |
974.1.35
by aaron.bentley at utoronto
Added revision-based common-ancestor checking |
179 |
if len(a_closest) == 0: |
180 |
return None |
|
1153
by Martin Pool
- clean up some code in revision.py |
181 |
b_closest = __get_closest(b_intersection) |
974.1.35
by aaron.bentley at utoronto
Added revision-based common-ancestor checking |
182 |
assert len(b_closest) != 0 |
183 |
mutter ("a_closest %r" % a_closest) |
|
184 |
mutter ("b_closest %r" % b_closest) |
|
185 |
if a_closest[0] in b_closest: |
|
186 |
return a_closest[0] |
|
187 |
elif b_closest[0] in a_closest: |
|
188 |
return b_closest[0] |
|
189 |
else: |
|
1154
by Martin Pool
- fix imports for moved errors |
190 |
raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0])) |
974.1.35
by aaron.bentley at utoronto
Added revision-based common-ancestor checking |
191 |
return a_closest[0] |
974.1.26
by aaron.bentley at utoronto
merged mbp@sourcefrog.net-20050817233101-0939da1cf91f2472 |
192 |
|
974.1.60
by aaron.bentley at utoronto
Initial import of common-ancestor detection |
193 |
def revision_graph(revision, revision_source): |
974.1.66
by Aaron Bentley
more cleanups, docs, sorting stuff |
194 |
"""Produce a graph of the ancestry of the specified revision.
|
195 |
Return root, ancestors map, descendants map
|
|
196 |
||
197 |
TODO: Produce graphs with the NULL revision as root, so that we can find
|
|
198 |
a common even when trees are not branches don't represent a single line
|
|
199 |
of descent.
|
|
200 |
"""
|
|
974.1.60
by aaron.bentley at utoronto
Initial import of common-ancestor detection |
201 |
ancestors = {} |
202 |
descendants = {} |
|
203 |
lines = [revision] |
|
204 |
root = None |
|
974.1.61
by abentley
fixes for common ancestor picker |
205 |
descendants[revision] = {} |
974.1.60
by aaron.bentley at utoronto
Initial import of common-ancestor detection |
206 |
while len(lines) > 0: |
207 |
new_lines = set() |
|
208 |
for line in lines: |
|
209 |
try: |
|
210 |
rev = revision_source.get_revision(line) |
|
211 |
parents = [p.revision_id for p in rev.parents] |
|
212 |
if len(parents) == 0: |
|
213 |
root = line |
|
214 |
except bzrlib.errors.NoSuchRevision: |
|
974.1.73
by Aaron Bentley
Reimplemented get_intervening_revisions for better scalability |
215 |
if line == revision: |
216 |
raise
|
|
974.1.64
by Aaron Bentley
Handled ancestors that are missing when finding a base |
217 |
parents = None |
218 |
if parents is not None: |
|
219 |
for parent in parents: |
|
220 |
if parent not in ancestors: |
|
221 |
new_lines.add(parent) |
|
222 |
if parent not in descendants: |
|
223 |
descendants[parent] = {} |
|
224 |
descendants[parent][line] = 1 |
|
225 |
if parents is not None: |
|
226 |
ancestors[line] = set(parents) |
|
974.1.60
by aaron.bentley at utoronto
Initial import of common-ancestor detection |
227 |
lines = new_lines |
974.1.63
by Aaron Bentley
Fixed graph-generation |
228 |
assert root not in descendants[root] |
229 |
assert root not in ancestors[root] |
|
974.1.60
by aaron.bentley at utoronto
Initial import of common-ancestor detection |
230 |
return root, ancestors, descendants |
231 |
||
232 |
def combined_graph(revision_a, revision_b, revision_source): |
|
974.1.66
by Aaron Bentley
more cleanups, docs, sorting stuff |
233 |
"""Produce a combined ancestry graph.
|
234 |
Return graph root, ancestors map, descendants map, set of common nodes"""
|
|
974.1.60
by aaron.bentley at utoronto
Initial import of common-ancestor detection |
235 |
root, ancestors, descendants = revision_graph(revision_a, revision_source) |
236 |
root_b, ancestors_b, descendants_b = revision_graph(revision_b, |
|
237 |
revision_source) |
|
974.1.80
by Aaron Bentley
Improved merge error handling and testing |
238 |
if root != root_b: |
239 |
raise bzrlib.errors.NoCommonRoot(revision_a, revision_b) |
|
974.1.60
by aaron.bentley at utoronto
Initial import of common-ancestor detection |
240 |
common = set() |
241 |
for node, node_anc in ancestors_b.iteritems(): |
|
242 |
if node in ancestors: |
|
243 |
common.add(node) |
|
244 |
else: |
|
245 |
ancestors[node] = set() |
|
246 |
ancestors[node].update(node_anc) |
|
247 |
for node, node_dec in descendants_b.iteritems(): |
|
248 |
if node not in descendants: |
|
249 |
descendants[node] = set() |
|
974.1.63
by Aaron Bentley
Fixed graph-generation |
250 |
descendants[node].update(node_dec) |
974.1.60
by aaron.bentley at utoronto
Initial import of common-ancestor detection |
251 |
return root, ancestors, descendants, common |
252 |
||
253 |
def common_ancestor(revision_a, revision_b, revision_source): |
|
974.1.80
by Aaron Bentley
Improved merge error handling and testing |
254 |
try: |
255 |
root, ancestors, descendants, common = \ |
|
256 |
combined_graph(revision_a, revision_b, revision_source) |
|
257 |
except bzrlib.errors.NoCommonRoot: |
|
258 |
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b) |
|
259 |
||
974.1.87
by Aaron Bentley
Refactored and documented graph stuff |
260 |
distances = node_distances (descendants, ancestors, root) |
261 |
farthest = select_farthest(distances, common) |
|
262 |
if farthest is None: |
|
263 |
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b) |
|
264 |
return farthest |
|
974.1.60
by aaron.bentley at utoronto
Initial import of common-ancestor detection |
265 |
|
974.1.26
by aaron.bentley at utoronto
merged mbp@sourcefrog.net-20050817233101-0939da1cf91f2472 |
266 |
class MultipleRevisionSources(object): |
1153
by Martin Pool
- clean up some code in revision.py |
267 |
"""Proxy that looks in multiple branches for revisions."""
|
974.1.26
by aaron.bentley at utoronto
merged mbp@sourcefrog.net-20050817233101-0939da1cf91f2472 |
268 |
def __init__(self, *args): |
269 |
object.__init__(self) |
|
270 |
assert len(args) != 0 |
|
271 |
self._revision_sources = args |
|
272 |
||
273 |
def get_revision(self, revision_id): |
|
274 |
for source in self._revision_sources: |
|
275 |
try: |
|
276 |
return source.get_revision(revision_id) |
|
277 |
except bzrlib.errors.NoSuchRevision, e: |
|
278 |
pass
|
|
279 |
raise e |
|
974.2.7
by aaron.bentley at utoronto
Merged from bzr.24 |
280 |
|
281 |
def get_intervening_revisions(ancestor_id, rev_id, rev_source, |
|
282 |
revision_history=None): |
|
283 |
"""Find the longest line of descent from maybe_ancestor to revision.
|
|
284 |
Revision history is followed where possible.
|
|
285 |
||
286 |
If ancestor_id == rev_id, list will be empty.
|
|
287 |
Otherwise, rev_id will be the last entry. ancestor_id will never appear.
|
|
288 |
If ancestor_id is not an ancestor, NotAncestor will be thrown
|
|
289 |
"""
|
|
974.1.73
by Aaron Bentley
Reimplemented get_intervening_revisions for better scalability |
290 |
root, ancestors, descendants = revision_graph(rev_id, rev_source) |
291 |
if len(descendants) == 0: |
|
292 |
raise NoSuchRevision(rev_source, rev_id) |
|
293 |
if ancestor_id not in descendants: |
|
294 |
rev_source.get_revision(ancestor_id) |
|
295 |
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id) |
|
296 |
root_descendants = all_descendants(descendants, ancestor_id) |
|
297 |
root_descendants.add(ancestor_id) |
|
298 |
if rev_id not in root_descendants: |
|
299 |
raise bzrlib.errors.NotAncestor(rev_id, ancestor_id) |
|
300 |
distances = node_distances(descendants, ancestors, ancestor_id, |
|
301 |
root_descendants=root_descendants) |
|
302 |
||
303 |
def best_ancestor(rev_id): |
|
304 |
best = None |
|
305 |
for anc_id in ancestors[rev_id]: |
|
306 |
try: |
|
307 |
distance = distances[anc_id] |
|
308 |
except KeyError: |
|
309 |
continue
|
|
310 |
if revision_history is not None and anc_id in revision_history: |
|
311 |
return anc_id |
|
312 |
elif best is None or distance > best[1]: |
|
313 |
best = (anc_id, distance) |
|
314 |
return best[0] |
|
315 |
||
316 |
next = rev_id |
|
317 |
path = [] |
|
318 |
while next != ancestor_id: |
|
319 |
path.append(next) |
|
320 |
next = best_ancestor(next) |
|
321 |
path.reverse() |
|
322 |
return path |