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)
295
261
def find_distance_to_null(self, target_revision_id, known_revision_ids):
296
262
"""Find the left-hand distance to the NULL_REVISION.
896
862
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
919
865
def find_unique_lca(self, left_revision, right_revision,
920
866
count_steps=False):
921
867
"""Find a unique LCA.
1536
1463
return revs, ghosts
1539
class AbstractSearchResult(object):
1540
"""The result of a search, describing a set of keys.
1542
Search results are typically used as the 'fetch_spec' parameter when
1545
:seealso: AbstractSearch
1548
def get_recipe(self):
1549
"""Return a recipe that can be used to replay this search.
1551
The recipe allows reconstruction of the same results at a later date.
1553
:return: A tuple of (search_kind_str, *details). The details vary by
1554
kind of search result.
1556
raise NotImplementedError(self.get_recipe)
1558
def get_network_struct(self):
1559
"""Return a tuple that can be transmitted via the HPSS protocol."""
1560
raise NotImplementedError(self.get_network_struct)
1563
"""Return the keys found in this search.
1565
:return: A set of keys.
1567
raise NotImplementedError(self.get_keys)
1570
"""Return false if the search lists 1 or more revisions."""
1571
raise NotImplementedError(self.is_empty)
1573
def refine(self, seen, referenced):
1574
"""Create a new search by refining this search.
1576
:param seen: Revisions that have been satisfied.
1577
:param referenced: Revision references observed while satisfying some
1579
:return: A search result.
1581
raise NotImplementedError(self.refine)
1584
class AbstractSearch(object):
1585
"""A search that can be executed, producing a search result.
1587
:seealso: AbstractSearchResult
1591
"""Construct a network-ready search result from this search description.
1593
This may take some time to search repositories, etc.
1595
:return: A search result (an object that implements
1596
AbstractSearchResult's API).
1598
raise NotImplementedError(self.execute)
1601
class SearchResult(AbstractSearchResult):
1466
class SearchResult(object):
1602
1467
"""The result of a breadth first search.
1604
1469
A SearchResult provides the ability to reconstruct the search or access a
1619
1484
self._recipe = ('search', start_keys, exclude_keys, key_count)
1620
1485
self._keys = frozenset(keys)
1623
kind, start_keys, exclude_keys, key_count = self._recipe
1624
if len(start_keys) > 5:
1625
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1627
start_keys_repr = repr(start_keys)
1628
if len(exclude_keys) > 5:
1629
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1631
exclude_keys_repr = repr(exclude_keys)
1632
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1633
kind, start_keys_repr, exclude_keys_repr, key_count)
1635
1487
def get_recipe(self):
1636
1488
"""Return a recipe that can be used to replay this search.
1774
1606
return PendingAncestryResult(referenced - seen, self.repo)
1777
class EmptySearchResult(AbstractSearchResult):
1778
"""An empty search result."""
1784
class EverythingResult(AbstractSearchResult):
1785
"""A search result that simply requests everything in the repository."""
1787
def __init__(self, repo):
1791
return '%s(%r)' % (self.__class__.__name__, self._repo)
1793
def get_recipe(self):
1794
raise NotImplementedError(self.get_recipe)
1796
def get_network_struct(self):
1797
return ('everything',)
1800
if 'evil' in debug.debug_flags:
1801
from bzrlib import remote
1802
if isinstance(self._repo, remote.RemoteRepository):
1803
# warn developers (not users) not to do this
1804
trace.mutter_callsite(
1805
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1806
return self._repo.all_revision_ids()
1809
# It's ok for this to wrongly return False: the worst that can happen
1810
# is that RemoteStreamSource will initiate a get_stream on an empty
1811
# repository. And almost all repositories are non-empty.
1814
def refine(self, seen, referenced):
1815
heads = set(self._repo.all_revision_ids())
1816
heads.difference_update(seen)
1817
heads.update(referenced)
1818
return PendingAncestryResult(heads, self._repo)
1821
class EverythingNotInOther(AbstractSearch):
1822
"""Find all revisions in that are in one repo but not the other."""
1824
def __init__(self, to_repo, from_repo, find_ghosts=False):
1825
self.to_repo = to_repo
1826
self.from_repo = from_repo
1827
self.find_ghosts = find_ghosts
1830
return self.to_repo.search_missing_revision_ids(
1831
self.from_repo, find_ghosts=self.find_ghosts)
1834
class NotInOtherForRevs(AbstractSearch):
1835
"""Find all revisions missing in one repo for a some specific heads."""
1837
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1841
:param required_ids: revision IDs of heads that must be found, or else
1842
the search will fail with NoSuchRevision. All revisions in their
1843
ancestry not already in the other repository will be included in
1845
:param if_present_ids: revision IDs of heads that may be absent in the
1846
source repository. If present, then their ancestry not already
1847
found in other will be included in the search result.
1849
self.to_repo = to_repo
1850
self.from_repo = from_repo
1851
self.find_ghosts = find_ghosts
1852
self.required_ids = required_ids
1853
self.if_present_ids = if_present_ids
1856
if len(self.required_ids) > 5:
1857
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1859
reqd_revs_repr = repr(self.required_ids)
1860
if self.if_present_ids and len(self.if_present_ids) > 5:
1861
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1863
ifp_revs_repr = repr(self.if_present_ids)
1865
return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
1866
self.__class__.__name__, self.from_repo, self.to_repo,
1867
self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
1870
return self.to_repo.search_missing_revision_ids(
1871
self.from_repo, revision_ids=self.required_ids,
1872
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
1875
1609
def collapse_linear_regions(parent_map):
1876
1610
"""Collapse regions of the graph that are 'linear'.
added
removed
bzrlib/graph.py
