177
176
behaves like Branch's.
180
from bzrlib.branch import NoSuchRevision
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):
181
185
ancestors = (revision_id,)
182
187
while len(ancestors) > 0:
183
188
new_ancestors = []
184
189
for ancestor in ancestors:
185
if ancestor == candidate_id:
191
yield ancestor, distance
188
193
revision = revision_source.get_revision(ancestor)
189
except NoSuchRevision, e:
194
except bzrlib.errors.NoSuchRevision, e:
190
195
if e.revision == revision_id:
200
yield ancestor, distance
194
201
new_ancestors.extend([p.revision_id for p in revision.parents])
195
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)
198
327
class MultipleRevisionSources(object):
328
"""Proxy that looks in multiple branches for revisions."""
199
329
def __init__(self, *args):
200
330
object.__init__(self)
201
331
assert len(args) != 0
202
332
self._revision_sources = args
204
334
def get_revision(self, revision_id):
205
from bzrlib.branch import NoSuchRevision
206
335
for source in self._revision_sources:
208
337
return source.get_revision(revision_id)
209
except NoSuchRevision, e:
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
