179
183
self.missing_keys.add(key)
182
class CallableToParentsProviderAdapter(object):
183
"""A parents provider that adapts any callable to the parents provider API.
185
i.e. it accepts calls to self.get_parent_map and relays them to the
186
callable it was constructed with.
189
def __init__(self, a_callable):
190
self.callable = a_callable
193
return "%s(%r)" % (self.__class__.__name__, self.callable)
195
def get_parent_map(self, keys):
196
return self.callable(keys)
199
186
class Graph(object):
200
187
"""Provide incremental access to revision graphs.
271
258
right = searchers[1].seen
272
259
return (left.difference(right), right.difference(left))
274
def find_descendants(self, old_key, new_key):
275
"""Find descendants of old_key that are ancestors of new_key."""
276
child_map = self.get_child_map(self._find_descendant_ancestors(
278
graph = Graph(DictParentsProvider(child_map))
279
searcher = graph._make_breadth_first_searcher([old_key])
283
def _find_descendant_ancestors(self, old_key, new_key):
284
"""Find ancestors of new_key that may be descendants of old_key."""
285
stop = self._make_breadth_first_searcher([old_key])
286
descendants = self._make_breadth_first_searcher([new_key])
287
for revisions in descendants:
288
old_stop = stop.seen.intersection(revisions)
289
descendants.stop_searching_any(old_stop)
290
seen_stop = descendants.find_seen_ancestors(stop.step())
291
descendants.stop_searching_any(seen_stop)
292
return descendants.seen.difference(stop.seen)
294
def get_child_map(self, keys):
295
"""Get a mapping from parents to children of the specified keys.
297
This is simply the inversion of get_parent_map. Only supplied keys
298
will be discovered as children.
299
:return: a dict of key:child_list for keys.
301
parent_map = self._parents_provider.get_parent_map(keys)
303
for child, parents in sorted(parent_map.items()):
304
for parent in parents:
305
parent_child.setdefault(parent, []).append(child)
308
261
def find_distance_to_null(self, target_revision_id, known_revision_ids):
309
262
"""Find the left-hand distance to the NULL_REVISION.
909
862
stop.add(parent_id)
912
def find_lefthand_merger(self, merged_key, tip_key):
913
"""Find the first lefthand ancestor of tip_key that merged merged_key.
915
We do this by first finding the descendants of merged_key, then
916
walking through the lefthand ancestry of tip_key until we find a key
917
that doesn't descend from merged_key. Its child is the key that
920
:return: The first lefthand ancestor of tip_key to merge merged_key.
921
merged_key if it is a lefthand ancestor of tip_key.
922
None if no ancestor of tip_key merged merged_key.
924
descendants = self.find_descendants(merged_key, tip_key)
925
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
926
last_candidate = None
927
for candidate in candidate_iterator:
928
if candidate not in descendants:
929
return last_candidate
930
last_candidate = candidate
932
865
def find_unique_lca(self, left_revision, right_revision,
933
866
count_steps=False):
934
867
"""Find a unique LCA.
1549
1463
return revs, ghosts
1552
class AbstractSearchResult(object):
1553
"""The result of a search, describing a set of keys.
1555
Search results are typically used as the 'fetch_spec' parameter when
1558
:seealso: AbstractSearch
1561
def get_recipe(self):
1562
"""Return a recipe that can be used to replay this search.
1564
The recipe allows reconstruction of the same results at a later date.
1566
:return: A tuple of (search_kind_str, *details). The details vary by
1567
kind of search result.
1569
raise NotImplementedError(self.get_recipe)
1571
def get_network_struct(self):
1572
"""Return a tuple that can be transmitted via the HPSS protocol."""
1573
raise NotImplementedError(self.get_network_struct)
1576
"""Return the keys found in this search.
1578
:return: A set of keys.
1580
raise NotImplementedError(self.get_keys)
1583
"""Return false if the search lists 1 or more revisions."""
1584
raise NotImplementedError(self.is_empty)
1586
def refine(self, seen, referenced):
1587
"""Create a new search by refining this search.
1589
:param seen: Revisions that have been satisfied.
1590
:param referenced: Revision references observed while satisfying some
1592
:return: A search result.
1594
raise NotImplementedError(self.refine)
1597
class AbstractSearch(object):
1598
"""A search that can be executed, producing a search result.
1600
:seealso: AbstractSearchResult
1604
"""Construct a network-ready search result from this search description.
1606
This may take some time to search repositories, etc.
1608
:return: A search result (an object that implements
1609
AbstractSearchResult's API).
1611
raise NotImplementedError(self.execute)
1614
class SearchResult(AbstractSearchResult):
1466
class SearchResult(object):
1615
1467
"""The result of a breadth first search.
1617
1469
A SearchResult provides the ability to reconstruct the search or access a
1632
1484
self._recipe = ('search', start_keys, exclude_keys, key_count)
1633
1485
self._keys = frozenset(keys)
1636
kind, start_keys, exclude_keys, key_count = self._recipe
1637
if len(start_keys) > 5:
1638
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1640
start_keys_repr = repr(start_keys)
1641
if len(exclude_keys) > 5:
1642
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1644
exclude_keys_repr = repr(exclude_keys)
1645
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1646
kind, start_keys_repr, exclude_keys_repr, key_count)
1648
1487
def get_recipe(self):
1649
1488
"""Return a recipe that can be used to replay this search.
1787
1606
return PendingAncestryResult(referenced - seen, self.repo)
1790
class EmptySearchResult(AbstractSearchResult):
1791
"""An empty search result."""
1797
class EverythingResult(AbstractSearchResult):
1798
"""A search result that simply requests everything in the repository."""
1800
def __init__(self, repo):
1804
return '%s(%r)' % (self.__class__.__name__, self._repo)
1806
def get_recipe(self):
1807
raise NotImplementedError(self.get_recipe)
1809
def get_network_struct(self):
1810
return ('everything',)
1813
if 'evil' in debug.debug_flags:
1814
from bzrlib import remote
1815
if isinstance(self._repo, remote.RemoteRepository):
1816
# warn developers (not users) not to do this
1817
trace.mutter_callsite(
1818
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1819
return self._repo.all_revision_ids()
1822
# It's ok for this to wrongly return False: the worst that can happen
1823
# is that RemoteStreamSource will initiate a get_stream on an empty
1824
# repository. And almost all repositories are non-empty.
1827
def refine(self, seen, referenced):
1828
heads = set(self._repo.all_revision_ids())
1829
heads.difference_update(seen)
1830
heads.update(referenced)
1831
return PendingAncestryResult(heads, self._repo)
1834
class EverythingNotInOther(AbstractSearch):
1835
"""Find all revisions in that are in one repo but not the other."""
1837
def __init__(self, to_repo, from_repo, find_ghosts=False):
1838
self.to_repo = to_repo
1839
self.from_repo = from_repo
1840
self.find_ghosts = find_ghosts
1843
return self.to_repo.search_missing_revision_ids(
1844
self.from_repo, find_ghosts=self.find_ghosts)
1847
class NotInOtherForRevs(AbstractSearch):
1848
"""Find all revisions missing in one repo for a some specific heads."""
1850
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1854
:param required_ids: revision IDs of heads that must be found, or else
1855
the search will fail with NoSuchRevision. All revisions in their
1856
ancestry not already in the other repository will be included in
1858
:param if_present_ids: revision IDs of heads that may be absent in the
1859
source repository. If present, then their ancestry not already
1860
found in other will be included in the search result.
1862
self.to_repo = to_repo
1863
self.from_repo = from_repo
1864
self.find_ghosts = find_ghosts
1865
self.required_ids = required_ids
1866
self.if_present_ids = if_present_ids
1869
if len(self.required_ids) > 5:
1870
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1872
reqd_revs_repr = repr(self.required_ids)
1873
if self.if_present_ids and len(self.if_present_ids) > 5:
1874
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1876
ifp_revs_repr = repr(self.if_present_ids)
1878
return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
1879
self.__class__.__name__, self.from_repo, self.to_repo,
1880
self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
1883
return self.to_repo.search_missing_revision_ids(
1884
self.from_repo, revision_ids=self.required_ids,
1885
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
1888
1609
def collapse_linear_regions(parent_map):
1889
1610
"""Collapse regions of the graph that are 'linear'.
added
removed
bzrlib/graph.py
