255
258
right = searchers[1].seen
256
259
return (left.difference(right), right.difference(left))
258
def find_descendants(self, old_key, new_key):
259
"""Find descendants of old_key that are ancestors of new_key."""
260
child_map = self.get_child_map(self._find_descendant_ancestors(
262
graph = Graph(DictParentsProvider(child_map))
263
searcher = graph._make_breadth_first_searcher([old_key])
267
def _find_descendant_ancestors(self, old_key, new_key):
268
"""Find ancestors of new_key that may be descendants of old_key."""
269
stop = self._make_breadth_first_searcher([old_key])
270
descendants = self._make_breadth_first_searcher([new_key])
271
for revisions in descendants:
272
old_stop = stop.seen.intersection(revisions)
273
descendants.stop_searching_any(old_stop)
274
seen_stop = descendants.find_seen_ancestors(stop.step())
275
descendants.stop_searching_any(seen_stop)
276
return descendants.seen.difference(stop.seen)
278
def get_child_map(self, keys):
279
"""Get a mapping from parents to children of the specified keys.
281
This is simply the inversion of get_parent_map. Only supplied keys
282
will be discovered as children.
283
:return: a dict of key:child_list for keys.
285
parent_map = self._parents_provider.get_parent_map(keys)
287
for child, parents in sorted(parent_map.items()):
288
for parent in parents:
289
parent_child.setdefault(parent, []).append(child)
292
261
def find_distance_to_null(self, target_revision_id, known_revision_ids):
293
262
"""Find the left-hand distance to the NULL_REVISION.
893
862
stop.add(parent_id)
896
def find_lefthand_merger(self, merged_key, tip_key):
897
"""Find the first lefthand ancestor of tip_key that merged merged_key.
899
We do this by first finding the descendants of merged_key, then
900
walking through the lefthand ancestry of tip_key until we find a key
901
that doesn't descend from merged_key. Its child is the key that
904
:return: The first lefthand ancestor of tip_key to merge merged_key.
905
merged_key if it is a lefthand ancestor of tip_key.
906
None if no ancestor of tip_key merged merged_key.
908
descendants = self.find_descendants(merged_key, tip_key)
909
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
910
last_candidate = None
911
for candidate in candidate_iterator:
912
if candidate not in descendants:
913
return last_candidate
914
last_candidate = candidate
916
865
def find_unique_lca(self, left_revision, right_revision,
917
866
count_steps=False):
918
867
"""Find a unique LCA.
1533
1463
return revs, ghosts
1536
class AbstractSearchResult(object):
1537
"""The result of a search, describing a set of keys.
1539
Search results are typically used as the 'fetch_spec' parameter when
1542
:seealso: AbstractSearch
1545
def get_recipe(self):
1546
"""Return a recipe that can be used to replay this search.
1548
The recipe allows reconstruction of the same results at a later date.
1550
:return: A tuple of (search_kind_str, *details). The details vary by
1551
kind of search result.
1553
raise NotImplementedError(self.get_recipe)
1555
def get_network_struct(self):
1556
"""Return a tuple that can be transmitted via the HPSS protocol."""
1557
raise NotImplementedError(self.get_network_struct)
1560
"""Return the keys found in this search.
1562
:return: A set of keys.
1564
raise NotImplementedError(self.get_keys)
1567
"""Return false if the search lists 1 or more revisions."""
1568
raise NotImplementedError(self.is_empty)
1570
def refine(self, seen, referenced):
1571
"""Create a new search by refining this search.
1573
:param seen: Revisions that have been satisfied.
1574
:param referenced: Revision references observed while satisfying some
1576
:return: A search result.
1578
raise NotImplementedError(self.refine)
1581
class AbstractSearch(object):
1582
"""A search that can be executed, producing a search result.
1584
:seealso: AbstractSearchResult
1588
"""Construct a network-ready search result from this search description.
1590
This may take some time to search repositories, etc.
1592
:return: A search result (an object that implements
1593
AbstractSearchResult's API).
1595
raise NotImplementedError(self.execute)
1598
class SearchResult(AbstractSearchResult):
1466
class SearchResult(object):
1599
1467
"""The result of a breadth first search.
1601
1469
A SearchResult provides the ability to reconstruct the search or access a
1616
1484
self._recipe = ('search', start_keys, exclude_keys, key_count)
1617
1485
self._keys = frozenset(keys)
1620
kind, start_keys, exclude_keys, key_count = self._recipe
1621
if len(start_keys) > 5:
1622
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1624
start_keys_repr = repr(start_keys)
1625
if len(exclude_keys) > 5:
1626
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1628
exclude_keys_repr = repr(exclude_keys)
1629
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1630
kind, start_keys_repr, exclude_keys_repr, key_count)
1632
1487
def get_recipe(self):
1633
1488
"""Return a recipe that can be used to replay this search.
1771
1606
return PendingAncestryResult(referenced - seen, self.repo)
1774
class EmptySearchResult(AbstractSearchResult):
1775
"""An empty search result."""
1781
class EverythingResult(AbstractSearchResult):
1782
"""A search result that simply requests everything in the repository."""
1784
def __init__(self, repo):
1788
return '%s(%r)' % (self.__class__.__name__, self._repo)
1790
def get_recipe(self):
1791
raise NotImplementedError(self.get_recipe)
1793
def get_network_struct(self):
1794
return ('everything',)
1797
if 'evil' in debug.debug_flags:
1798
from bzrlib import remote
1799
if isinstance(self._repo, remote.RemoteRepository):
1800
# warn developers (not users) not to do this
1801
trace.mutter_callsite(
1802
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1803
return self._repo.all_revision_ids()
1806
# It's ok for this to wrongly return False: the worst that can happen
1807
# is that RemoteStreamSource will initiate a get_stream on an empty
1808
# repository. And almost all repositories are non-empty.
1811
def refine(self, seen, referenced):
1812
heads = set(self._repo.all_revision_ids())
1813
heads.difference_update(seen)
1814
heads.update(referenced)
1815
return PendingAncestryResult(heads, self._repo)
1818
class EverythingNotInOther(AbstractSearch):
1819
"""Find all revisions in that are in one repo but not the other."""
1821
def __init__(self, to_repo, from_repo, find_ghosts=False):
1822
self.to_repo = to_repo
1823
self.from_repo = from_repo
1824
self.find_ghosts = find_ghosts
1827
return self.to_repo.search_missing_revision_ids(
1828
self.from_repo, find_ghosts=self.find_ghosts)
1831
class NotInOtherForRevs(AbstractSearch):
1832
"""Find all revisions missing in one repo for a some specific heads."""
1834
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1838
:param required_ids: revision IDs of heads that must be found, or else
1839
the search will fail with NoSuchRevision. All revisions in their
1840
ancestry not already in the other repository will be included in
1842
:param if_present_ids: revision IDs of heads that may be absent in the
1843
source repository. If present, then their ancestry not already
1844
found in other will be included in the search result.
1846
self.to_repo = to_repo
1847
self.from_repo = from_repo
1848
self.find_ghosts = find_ghosts
1849
self.required_ids = required_ids
1850
self.if_present_ids = if_present_ids
1853
if len(self.required_ids) > 5:
1854
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1856
reqd_revs_repr = repr(self.required_ids)
1857
if self.if_present_ids and len(self.if_present_ids) > 5:
1858
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1860
ifp_revs_repr = repr(self.if_present_ids)
1862
return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
1863
self.__class__.__name__, self.from_repo, self.to_repo,
1864
self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
1867
return self.to_repo.search_missing_revision_ids(
1868
self.from_repo, revision_ids=self.required_ids,
1869
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
1872
1609
def collapse_linear_regions(parent_map):
1873
1610
"""Collapse regions of the graph that are 'linear'.
added
removed
bzrlib/graph.py
