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