59
60
return 'DictParentsProvider(%r)' % self.ancestry
61
62
def get_parent_map(self, keys):
62
"""See StackedParentsProvider.get_parent_map"""
63
"""See _StackedParentsProvider.get_parent_map"""
63
64
ancestry = self.ancestry
64
65
return dict((k, ancestry[k]) for k in keys if k in ancestry)
67
class StackedParentsProvider(object):
68
"""A parents provider which stacks (or unions) multiple providers.
70
The providers are queries in the order of the provided parent_providers.
68
class _StackedParentsProvider(object):
73
70
def __init__(self, parent_providers):
74
71
self._parent_providers = parent_providers
76
73
def __repr__(self):
77
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
74
return "_StackedParentsProvider(%r)" % self._parent_providers
79
76
def get_parent_map(self, keys):
80
77
"""Get a mapping of keys => parents
136
133
raise AssertionError('Cache enabled when already enabled.')
138
135
self._cache_misses = cache_misses
139
self.missing_keys = set()
141
137
def disable_cache(self):
142
138
"""Disable and clear the cache."""
143
139
self._cache = None
144
self._cache_misses = None
145
self.missing_keys = set()
147
141
def get_cached_map(self):
148
142
"""Return any cached get_parent_map values."""
149
143
if self._cache is None:
151
return dict(self._cache)
145
return dict((k, v) for k, v in self._cache.items()
153
148
def get_parent_map(self, keys):
154
"""See StackedParentsProvider.get_parent_map."""
157
cache = self._get_parent_map(keys)
149
"""See _StackedParentsProvider.get_parent_map."""
150
# Hack to build up the caching logic.
151
ancestry = self._cache
153
# Caching is disabled.
154
missing_revisions = set(keys)
159
needed_revisions = set(key for key in keys if key not in cache)
160
# Do not ask for negatively cached keys
161
needed_revisions.difference_update(self.missing_keys)
163
parent_map = self._get_parent_map(needed_revisions)
164
cache.update(parent_map)
165
if self._cache_misses:
166
for key in needed_revisions:
167
if key not in parent_map:
168
self.note_missing_key(key)
171
value = cache.get(key)
172
if value is not None:
176
def note_missing_key(self, key):
177
"""Note that key is a missing key."""
178
if self._cache_misses:
179
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)
157
missing_revisions = set(key for key in keys if key not in ancestry)
158
if missing_revisions:
159
parent_map = self._get_parent_map(missing_revisions)
160
ancestry.update(parent_map)
161
if self._cache_misses:
162
# None is never a valid parents list, so it can be used to
164
ancestry.update(dict((k, None) for k in missing_revisions
165
if k not in parent_map))
166
present_keys = [k for k in keys if ancestry.get(k) is not None]
167
return dict((k, ancestry[k]) for k in present_keys)
199
170
class Graph(object):
272
242
right = searchers[1].seen
273
243
return (left.difference(right), right.difference(left))
275
def find_descendants(self, old_key, new_key):
276
"""Find descendants of old_key that are ancestors of new_key."""
277
child_map = self.get_child_map(self._find_descendant_ancestors(
279
graph = Graph(DictParentsProvider(child_map))
280
searcher = graph._make_breadth_first_searcher([old_key])
284
def _find_descendant_ancestors(self, old_key, new_key):
285
"""Find ancestors of new_key that may be descendants of old_key."""
286
stop = self._make_breadth_first_searcher([old_key])
287
descendants = self._make_breadth_first_searcher([new_key])
288
for revisions in descendants:
289
old_stop = stop.seen.intersection(revisions)
290
descendants.stop_searching_any(old_stop)
291
seen_stop = descendants.find_seen_ancestors(stop.step())
292
descendants.stop_searching_any(seen_stop)
293
return descendants.seen.difference(stop.seen)
295
def get_child_map(self, keys):
296
"""Get a mapping from parents to children of the specified keys.
298
This is simply the inversion of get_parent_map. Only supplied keys
299
will be discovered as children.
300
:return: a dict of key:child_list for keys.
302
parent_map = self._parents_provider.get_parent_map(keys)
304
for child, parents in sorted(parent_map.items()):
305
for parent in parents:
306
parent_child.setdefault(parent, []).append(child)
309
245
def find_distance_to_null(self, target_revision_id, known_revision_ids):
310
246
"""Find the left-hand distance to the NULL_REVISION.
360
296
return known_revnos[cur_tip] + num_steps
362
def find_lefthand_distances(self, keys):
363
"""Find the distance to null for all the keys in keys.
365
:param keys: keys to lookup.
366
:return: A dict key->distance for all of keys.
368
# Optimisable by concurrent searching, but a random spread should get
369
# some sort of hit rate.
376
(key, self.find_distance_to_null(key, known_revnos)))
377
except errors.GhostRevisionsHaveNoRevno:
380
known_revnos.append((key, -1))
381
return dict(known_revnos)
383
298
def find_unique_ancestors(self, unique_revision, common_revisions):
384
299
"""Find the unique ancestors for a revision versus others.
685
600
all_unique_searcher._iterations)
686
601
unique_tip_searchers = next_unique_searchers
603
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
604
def get_parents(self, revisions):
605
"""Find revision ids of the parents of a list of revisions
607
A list is returned of the same length as the input. Each entry
608
is a list of parent ids for the corresponding input revision.
610
[NULL_REVISION] is used as the parent of the first user-committed
611
revision. Its parent list is empty.
613
If the revision is not present (i.e. a ghost), None is used in place
614
of the list of parents.
616
Deprecated in bzr 1.2 - please see get_parent_map.
618
parents = self.get_parent_map(revisions)
619
return [parents.get(r, None) for r in revisions]
688
621
def get_parent_map(self, revisions):
689
622
"""Get a map of key:parent_list for revisions.
910
843
stop.add(parent_id)
913
def find_lefthand_merger(self, merged_key, tip_key):
914
"""Find the first lefthand ancestor of tip_key that merged merged_key.
916
We do this by first finding the descendants of merged_key, then
917
walking through the lefthand ancestry of tip_key until we find a key
918
that doesn't descend from merged_key. Its child is the key that
921
:return: The first lefthand ancestor of tip_key to merge merged_key.
922
merged_key if it is a lefthand ancestor of tip_key.
923
None if no ancestor of tip_key merged merged_key.
925
descendants = self.find_descendants(merged_key, tip_key)
926
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
927
last_candidate = None
928
for candidate in candidate_iterator:
929
if candidate not in descendants:
930
return last_candidate
931
last_candidate = candidate
933
846
def find_unique_lca(self, left_revision, right_revision,
934
847
count_steps=False):
935
848
"""Find a unique LCA.
1550
1443
return revs, ghosts
1553
class AbstractSearchResult(object):
1554
"""The result of a search, describing a set of keys.
1556
Search results are typically used as the 'fetch_spec' parameter when
1559
:seealso: AbstractSearch
1562
def get_recipe(self):
1563
"""Return a recipe that can be used to replay this search.
1565
The recipe allows reconstruction of the same results at a later date.
1567
:return: A tuple of `(search_kind_str, *details)`. The details vary by
1568
kind of search result.
1570
raise NotImplementedError(self.get_recipe)
1572
def get_network_struct(self):
1573
"""Return a tuple that can be transmitted via the HPSS protocol."""
1574
raise NotImplementedError(self.get_network_struct)
1577
"""Return the keys found in this search.
1579
:return: A set of keys.
1581
raise NotImplementedError(self.get_keys)
1584
"""Return false if the search lists 1 or more revisions."""
1585
raise NotImplementedError(self.is_empty)
1587
def refine(self, seen, referenced):
1588
"""Create a new search by refining this search.
1590
:param seen: Revisions that have been satisfied.
1591
:param referenced: Revision references observed while satisfying some
1593
:return: A search result.
1595
raise NotImplementedError(self.refine)
1598
class AbstractSearch(object):
1599
"""A search that can be executed, producing a search result.
1601
:seealso: AbstractSearchResult
1605
"""Construct a network-ready search result from this search description.
1607
This may take some time to search repositories, etc.
1609
:return: A search result (an object that implements
1610
AbstractSearchResult's API).
1612
raise NotImplementedError(self.execute)
1615
class SearchResult(AbstractSearchResult):
1446
class SearchResult(object):
1616
1447
"""The result of a breadth first search.
1618
1449
A SearchResult provides the ability to reconstruct the search or access a
1633
1464
self._recipe = ('search', start_keys, exclude_keys, key_count)
1634
1465
self._keys = frozenset(keys)
1637
kind, start_keys, exclude_keys, key_count = self._recipe
1638
if len(start_keys) > 5:
1639
start_keys_repr = repr(list(start_keys)[:5])[:-1] + ', ...]'
1641
start_keys_repr = repr(start_keys)
1642
if len(exclude_keys) > 5:
1643
exclude_keys_repr = repr(list(exclude_keys)[:5])[:-1] + ', ...]'
1645
exclude_keys_repr = repr(exclude_keys)
1646
return '<%s %s:(%s, %s, %d)>' % (self.__class__.__name__,
1647
kind, start_keys_repr, exclude_keys_repr, key_count)
1649
1467
def get_recipe(self):
1650
1468
"""Return a recipe that can be used to replay this search.
1652
1470
The recipe allows reconstruction of the same results at a later date
1653
1471
without knowing all the found keys. The essential elements are a list
1654
of keys to start and to stop at. In order to give reproducible
1472
of keys to start and and to stop at. In order to give reproducible
1655
1473
results when ghosts are encountered by a search they are automatically
1656
1474
added to the exclude list (or else ghost filling may alter the
1788
1586
return PendingAncestryResult(referenced - seen, self.repo)
1791
class EmptySearchResult(AbstractSearchResult):
1792
"""An empty search result."""
1798
class EverythingResult(AbstractSearchResult):
1799
"""A search result that simply requests everything in the repository."""
1801
def __init__(self, repo):
1805
return '%s(%r)' % (self.__class__.__name__, self._repo)
1807
def get_recipe(self):
1808
raise NotImplementedError(self.get_recipe)
1810
def get_network_struct(self):
1811
return ('everything',)
1814
if 'evil' in debug.debug_flags:
1815
from bzrlib import remote
1816
if isinstance(self._repo, remote.RemoteRepository):
1817
# warn developers (not users) not to do this
1818
trace.mutter_callsite(
1819
2, "EverythingResult(RemoteRepository).get_keys() is slow.")
1820
return self._repo.all_revision_ids()
1823
# It's ok for this to wrongly return False: the worst that can happen
1824
# is that RemoteStreamSource will initiate a get_stream on an empty
1825
# repository. And almost all repositories are non-empty.
1828
def refine(self, seen, referenced):
1829
heads = set(self._repo.all_revision_ids())
1830
heads.difference_update(seen)
1831
heads.update(referenced)
1832
return PendingAncestryResult(heads, self._repo)
1835
class EverythingNotInOther(AbstractSearch):
1836
"""Find all revisions in that are in one repo but not the other."""
1838
def __init__(self, to_repo, from_repo, find_ghosts=False):
1839
self.to_repo = to_repo
1840
self.from_repo = from_repo
1841
self.find_ghosts = find_ghosts
1844
return self.to_repo.search_missing_revision_ids(
1845
self.from_repo, find_ghosts=self.find_ghosts)
1848
class NotInOtherForRevs(AbstractSearch):
1849
"""Find all revisions missing in one repo for a some specific heads."""
1851
def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1852
find_ghosts=False, limit=None):
1855
:param required_ids: revision IDs of heads that must be found, or else
1856
the search will fail with NoSuchRevision. All revisions in their
1857
ancestry not already in the other repository will be included in
1859
:param if_present_ids: revision IDs of heads that may be absent in the
1860
source repository. If present, then their ancestry not already
1861
found in other will be included in the search result.
1862
:param limit: maximum number of revisions to fetch
1864
self.to_repo = to_repo
1865
self.from_repo = from_repo
1866
self.find_ghosts = find_ghosts
1867
self.required_ids = required_ids
1868
self.if_present_ids = if_present_ids
1872
if len(self.required_ids) > 5:
1873
reqd_revs_repr = repr(list(self.required_ids)[:5])[:-1] + ', ...]'
1875
reqd_revs_repr = repr(self.required_ids)
1876
if self.if_present_ids and len(self.if_present_ids) > 5:
1877
ifp_revs_repr = repr(list(self.if_present_ids)[:5])[:-1] + ', ...]'
1879
ifp_revs_repr = repr(self.if_present_ids)
1881
return ("<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r"
1883
self.__class__.__name__, self.from_repo, self.to_repo,
1884
self.find_ghosts, reqd_revs_repr, ifp_revs_repr,
1888
return self.to_repo.search_missing_revision_ids(
1889
self.from_repo, revision_ids=self.required_ids,
1890
if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts,
1894
1589
def collapse_linear_regions(parent_map):
1895
1590
"""Collapse regions of the graph that are 'linear'.
1962
1657
removed.add(node)
1967
class GraphThunkIdsToKeys(object):
1968
"""Forwards calls about 'ids' to be about keys internally."""
1970
def __init__(self, graph):
1973
def topo_sort(self):
1974
return [r for (r,) in self._graph.topo_sort()]
1976
def heads(self, ids):
1977
"""See Graph.heads()"""
1978
as_keys = [(i,) for i in ids]
1979
head_keys = self._graph.heads(as_keys)
1980
return set([h[0] for h in head_keys])
1982
def merge_sort(self, tip_revision):
1983
nodes = self._graph.merge_sort((tip_revision,))
1985
node.key = node.key[0]
1988
def add_node(self, revision, parents):
1989
self._graph.add_node((revision,), [(p,) for p in parents])
1992
_counters = [0,0,0,0,0,0,0]
1994
from bzrlib._known_graph_pyx import KnownGraph
1995
except ImportError, e:
1996
osutils.failed_to_load_extension(e)
1997
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
