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.
1463
1536
return revs, ghosts
1466
class SearchResult(object):
1539
class AbstractSearchResult(object):
1541
def get_recipe(self):
1542
"""Return a recipe that can be used to replay this search.
1544
The recipe allows reconstruction of the same results at a later date.
1546
:return: A tuple of (search_kind_str, *details). The details vary by
1547
kind of search result.
1549
raise NotImplementedError(self.get_recipe)
1551
def get_network_struct(self):
1552
"""Return a tuple that can be transmitted via the HPSS protocol."""
1553
raise NotImplementedError(self.get_network_struct)
1556
"""Return the keys found in this search.
1558
:return: A set of keys.
1560
raise NotImplementedError(self.get_keys)
1563
"""Return false if the search lists 1 or more revisions."""
1564
raise NotImplementedError(self.is_empty)
1566
def refine(self, seen, referenced):
1567
"""Create a new search by refining this search.
1569
:param seen: Revisions that have been satisfied.
1570
:param referenced: Revision references observed while satisfying some
1572
:return: A search result.
1574
raise NotImplementedError(self.refine)
1577
class AbstractSearch(object):
1580
"""Construct a network-ready search result from this search description.
1582
This may take some time to search repositories, etc.
1584
:return: A search result (an object that implements
1585
AbstractSearchResult's API).
1587
raise NotImplementedError(self.execute)
1590
class SearchResult(AbstractSearchResult):
1467
1591
"""The result of a breadth first search.
1469
1593
A SearchResult provides the ability to reconstruct the search or access a
1484
1608
self._recipe = ('search', start_keys, exclude_keys, key_count)
1485
1609
self._keys = frozenset(keys)
1612
kind, start_keys, exclude_keys, key_count = self._recipe
1613
if len(start_keys) > 5:
1614
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1616
start_keys_repr = repr(start_keys)
1617
if len(exclude_keys) > 5:
1618
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1620
exclude_keys_repr = repr(exclude_keys)
1621
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1622
kind, start_keys_repr, exclude_keys_repr, key_count)
1487
1624
def get_recipe(self):
1488
1625
"""Return a recipe that can be used to replay this search.
1606
1763
return PendingAncestryResult(referenced - seen, self.repo)
1766
class EmptySearchResult(AbstractSearchResult):
1767
"""An empty search result."""
1773
class EverythingResult(AbstractSearchResult):
1774
"""A search result that simply requests everything in the repository."""
1776
def __init__(self, repo):
1780
return '%s(%r)' % (self.__class__.__name__, self._repo)
1782
def get_recipe(self):
1783
raise NotImplementedError(self.get_recipe)
1785
def get_network_struct(self):
1786
return ('everything',)
1789
if 'evil' in debug.debug_flags:
1790
from bzrlib import remote
1791
if isinstance(self._repo, remote.RemoteRepository):
1792
# warn developers (not users) not to do this
1793
trace.mutter_callsite(
1794
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1795
return self._repo.all_revision_ids()
1798
# It's ok for this to wrongly return False: the worst that can happen
1799
# is that RemoteStreamSource will initiate a get_stream on an empty
1800
# repository. And almost all repositories are non-empty.
1803
def refine(self, seen, referenced):
1804
heads = set(self._repo.all_revision_ids())
1805
heads.difference_update(seen)
1806
heads.update(referenced)
1807
return PendingAncestryResult(heads, self._repo)
1810
class EverythingNotInOther(AbstractSearch):
1811
"""Find all revisions in that are in one repo but not the other."""
1813
def __init__(self, to_repo, from_repo, find_ghosts=False):
1814
self.to_repo = to_repo
1815
self.from_repo = from_repo
1816
self.find_ghosts = find_ghosts
1819
return self.to_repo.search_missing_revision_ids(
1820
self.from_repo, find_ghosts=self.find_ghosts)
1823
class NotInOtherForRevs(AbstractSearch):
1824
"""Find all revisions missing in one repo for a some specific heads."""
1826
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1830
:param required_ids: revision IDs of heads that must be found, or else
1831
the search will fail with NoSuchRevision. All revisions in their
1832
ancestry not already in the other repository will be included in
1834
:param if_present_ids: revision IDs of heads that may be absent in the
1835
source repository. If present, then their ancestry not already
1836
found in other will be included in the search result.
1838
self.to_repo = to_repo
1839
self.from_repo = from_repo
1840
self.find_ghosts = find_ghosts
1841
self.required_ids = required_ids
1842
self.if_present_ids = if_present_ids
1845
if len(self.required_ids) > 5:
1846
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1848
reqd_revs_repr = repr(self.required_ids)
1849
if self.if_present_ids and len(self.if_present_ids) > 5:
1850
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1852
ifp_revs_repr = repr(self.if_present_ids)
1854
return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
1855
self.__class__.__name__, self.from_repo, self.to_repo,
1856
self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
1859
return self.to_repo.search_missing_revision_ids(
1860
self.from_repo, revision_ids=self.required_ids,
1861
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
1609
1864
def collapse_linear_regions(parent_map):
1610
1865
"""Collapse regions of the graph that are 'linear'.