258
258
right = searchers[1].seen
259
259
return (left.difference(right), right.difference(left))
261
def find_descendants(self, old_key, new_key):
262
"""Find descendants of old_key that are ancestors of new_key."""
263
child_map = self.get_child_map(self._find_descendant_ancestors(
265
graph = Graph(DictParentsProvider(child_map))
266
searcher = graph._make_breadth_first_searcher([old_key])
270
def _find_descendant_ancestors(self, old_key, new_key):
271
"""Find ancestors of new_key that may be descendants of old_key."""
272
stop = self._make_breadth_first_searcher([old_key])
273
descendants = self._make_breadth_first_searcher([new_key])
274
for revisions in descendants:
275
old_stop = stop.seen.intersection(revisions)
276
descendants.stop_searching_any(old_stop)
277
seen_stop = descendants.find_seen_ancestors(stop.step())
278
descendants.stop_searching_any(seen_stop)
279
return descendants.seen.difference(stop.seen)
281
def get_child_map(self, keys):
282
"""Get a mapping from parents to children of the specified keys.
284
This is simply the inversion of get_parent_map. Only supplied keys
285
will be discovered as children.
286
:return: a dict of key:child_list for keys.
288
parent_map = self._parents_provider.get_parent_map(keys)
290
for child, parents in sorted(parent_map.items()):
291
for parent in parents:
292
parent_child.setdefault(parent, []).append(child)
261
295
def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
296
"""Find the left-hand distance to the NULL_REVISION.
862
896
stop.add(parent_id)
899
def find_lefthand_merger(self, merged_key, tip_key):
900
"""Find the first lefthand ancestor of tip_key that merged merged_key.
902
We do this by first finding the descendants of merged_key, then
903
walking through the lefthand ancestry of tip_key until we find a key
904
that doesn't descend from merged_key. Its child is the key that
907
:return: The first lefthand ancestor of tip_key to merge merged_key.
908
merged_key if it is a lefthand ancestor of tip_key.
909
None if no ancestor of tip_key merged merged_key.
911
descendants = self.find_descendants(merged_key, tip_key)
912
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
913
last_candidate = None
914
for candidate in candidate_iterator:
915
if candidate not in descendants:
916
return last_candidate
917
last_candidate = candidate
865
919
def find_unique_lca(self, left_revision, right_revision,
866
920
count_steps=False):
867
921
"""Find a unique LCA.
919
973
yield (ghost, None)
920
974
pending = next_pending
976
def iter_lefthand_ancestry(self, start_key, stop_keys=None):
977
if stop_keys is None:
980
def get_parents(key):
982
return self._parents_provider.get_parent_map([key])[key]
984
raise errors.RevisionNotPresent(next_key, self)
986
if next_key in stop_keys:
988
parents = get_parents(next_key)
990
if len(parents) == 0:
993
next_key = parents[0]
922
995
def iter_topo_order(self, revisions):
923
996
"""Iterate through the input revisions in topological order.
1484
1557
self._recipe = ('search', start_keys, exclude_keys, key_count)
1485
1558
self._keys = frozenset(keys)
1561
kind, start_keys, exclude_keys, key_count = self._recipe
1562
if len(start_keys) > 5:
1563
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1565
start_keys_repr = repr(start_keys)
1566
if len(exclude_keys) > 5:
1567
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1569
exclude_keys_repr = repr(exclude_keys)
1570
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1571
kind, start_keys_repr, exclude_keys_repr, key_count)
1487
1573
def get_recipe(self):
1488
1574
"""Return a recipe that can be used to replay this search.
1508
1594
return self._recipe
1596
def get_network_struct(self):
1597
start_keys = ' '.join(self._recipe[1])
1598
stop_keys = ' '.join(self._recipe[2])
1599
count = str(self._recipe[3])
1600
return (self._recipe[0], '\n'.join((start_keys, stop_keys, count)))
1510
1602
def get_keys(self):
1511
1603
"""Return the keys found in this search.
1606
1703
return PendingAncestryResult(referenced - seen, self.repo)
1706
class EmptySearchResult(object):
1712
class EverythingResult(object):
1713
"""A search result that simply requests everything in the repository."""
1715
def __init__(self, repo):
1718
def get_recipe(self):
1719
raise NotImplementedError(self.get_recipe)
1721
def get_network_struct(self):
1722
return ('everything',)
1725
if 'evil' in debug.debug_flags:
1726
from bzrlib import remote
1727
if isinstance(self._repo, remote.RemoteRepository):
1728
# warn developers (not users) not to do this
1729
trace.mutter_callsite(
1730
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1731
return self._repo.all_revision_ids()
1734
# It's ok for this to wrongly return False: the worst that can happen
1735
# is that RemoteStreamSource will initiate a get_stream on an empty
1736
# repository. And almost all repositories are non-empty.
1739
def refine(self, seen, referenced):
1740
heads = set(self._repo.all_revision_ids())
1741
heads.difference_update(seen)
1742
heads.update(referenced)
1743
return PendingAncestryResult(heads, self._repo)
1746
class EverythingNotInOther(object):
1748
def __init__(self, to_repo, from_repo, find_ghosts=False):
1749
self.to_repo = to_repo
1750
self.from_repo = from_repo
1751
self.find_ghosts = find_ghosts
1753
def get_search(self):
1754
return self.to_repo.search_missing_revision_ids(
1755
self.from_repo, find_ghosts=self.find_ghosts)
1758
class NotInOtherForRevs(object):
1760
def __init__(self, to_repo, from_repo, revision_ids, find_ghosts=False):
1761
self.to_repo = to_repo
1762
self.from_repo = from_repo
1763
self.find_ghosts = find_ghosts
1764
self.revision_ids = revision_ids
1766
def get_search(self):
1767
return self.to_repo.search_missing_revision_ids(
1768
self.from_repo, revision_ids=self.revision_ids,
1769
find_ghosts=self.find_ghosts)
1609
1772
def collapse_linear_regions(parent_map):
1610
1773
"""Collapse regions of the graph that are 'linear'.
added
removed
bzrlib/graph.py
