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):
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):
1579
def get_search_result(self):
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.
1586
raise NotImplementedError(self.get_search_result)
1589
class SearchResult(AbstractSearchResult):
1466
class SearchResult(object):
1590
1467
"""The result of a breadth first search.
1592
1469
A SearchResult provides the ability to reconstruct the search or access a
1607
1484
self._recipe = ('search', start_keys, exclude_keys, key_count)
1608
1485
self._keys = frozenset(keys)
1611
kind, start_keys, exclude_keys, key_count = self._recipe
1612
if len(start_keys) > 5:
1613
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1615
start_keys_repr = repr(start_keys)
1616
if len(exclude_keys) > 5:
1617
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1619
exclude_keys_repr = repr(exclude_keys)
1620
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1621
kind, start_keys_repr, exclude_keys_repr, key_count)
1623
1487
def get_recipe(self):
1624
1488
"""Return a recipe that can be used to replay this search.
1761
1606
return PendingAncestryResult(referenced - seen, self.repo)
1764
class EmptySearchResult(AbstractSearchResult):
1765
"""An empty search result."""
1771
class EverythingResult(AbstractSearchResult):
1772
"""A search result that simply requests everything in the repository."""
1774
def __init__(self, repo):
1778
return '%s(%r)' % (self.__class__.__name__, self._repo)
1780
def get_recipe(self):
1781
raise NotImplementedError(self.get_recipe)
1783
def get_network_struct(self):
1784
return ('everything',)
1787
if 'evil' in debug.debug_flags:
1788
from bzrlib import remote
1789
if isinstance(self._repo, remote.RemoteRepository):
1790
# warn developers (not users) not to do this
1791
trace.mutter_callsite(
1792
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1793
return self._repo.all_revision_ids()
1796
# It's ok for this to wrongly return False: the worst that can happen
1797
# is that RemoteStreamSource will initiate a get_stream on an empty
1798
# repository. And almost all repositories are non-empty.
1801
def refine(self, seen, referenced):
1802
heads = set(self._repo.all_revision_ids())
1803
heads.difference_update(seen)
1804
heads.update(referenced)
1805
return PendingAncestryResult(heads, self._repo)
1808
class EverythingNotInOther(AbstractSearch):
1809
"""Find all revisions in that are in one repo but not the other."""
1811
def __init__(self, to_repo, from_repo, find_ghosts=False):
1812
self.to_repo = to_repo
1813
self.from_repo = from_repo
1814
self.find_ghosts = find_ghosts
1816
def get_search_result(self):
1817
return self.to_repo.search_missing_revision_ids(
1818
self.from_repo, find_ghosts=self.find_ghosts)
1821
class NotInOtherForRevs(AbstractSearch):
1822
"""Find all revisions missing in one repo for a some specific heads."""
1824
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1828
:param required_ids: revision IDs of heads that must be found, or else
1829
the search will fail with NoSuchRevision. All revisions in their
1830
ancestry not already in the other repository will be included in
1832
:param if_present_ids: revision IDs of heads that may be absent in the
1833
source repository. If present, then their ancestry not already
1834
found in other will be included in the search result.
1836
self.to_repo = to_repo
1837
self.from_repo = from_repo
1838
self.find_ghosts = find_ghosts
1839
self.required_ids = required_ids
1840
self.if_present_ids = if_present_ids
1843
if len(self.required_ids) > 5:
1844
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1846
reqd_revs_repr = repr(self.required_ids)
1847
if self.if_present_ids and len(self.if_present_ids) > 5:
1848
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1850
ifp_revs_repr = repr(self.if_present_ids)
1852
return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
1853
self.__class__.__name__, self.from_repo, self.to_repo,
1854
self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
1856
def get_search_result(self):
1857
return self.to_repo.search_missing_revision_ids(
1858
self.from_repo, revision_ids=self.required_ids,
1859
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
1862
1609
def collapse_linear_regions(parent_map):
1863
1610
"""Collapse regions of the graph that are 'linear'.
added
removed
bzrlib/graph.py
