13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
from __future__ import absolute_import
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21
19
from bzrlib import (
27
from bzrlib.deprecated_graph import (node_distances, select_farthest)
29
29
STEP_UNIQUE_SEARCHER_EVERY = 5
60
60
def __repr__(self):
61
61
return 'DictParentsProvider(%r)' % self.ancestry
63
# Note: DictParentsProvider does not implement get_cached_parent_map
64
# Arguably, the data is clearly cached in memory. However, this class
65
# is mostly used for testing, and it keeps the tests clean to not
68
63
def get_parent_map(self, keys):
69
"""See StackedParentsProvider.get_parent_map"""
64
"""See _StackedParentsProvider.get_parent_map"""
70
65
ancestry = self.ancestry
71
return dict([(k, ancestry[k]) for k in keys if k in ancestry])
74
class StackedParentsProvider(object):
75
"""A parents provider which stacks (or unions) multiple providers.
77
The providers are queries in the order of the provided parent_providers.
66
return dict((k, ancestry[k]) for k in keys if k in ancestry)
69
class _StackedParentsProvider(object):
80
71
def __init__(self, parent_providers):
81
72
self._parent_providers = parent_providers
83
74
def __repr__(self):
84
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
75
return "_StackedParentsProvider(%r)" % self._parent_providers
86
77
def get_parent_map(self, keys):
87
78
"""Get a mapping of keys => parents
100
91
remaining = set(keys)
101
# This adds getattr() overhead to each get_parent_map call. However,
102
# this is StackedParentsProvider, which means we're dealing with I/O
103
# (either local indexes, or remote RPCs), so CPU overhead should be
105
for parents_provider in self._parent_providers:
106
get_cached = getattr(parents_provider, 'get_cached_parent_map',
108
if get_cached is None:
110
new_found = get_cached(remaining)
111
found.update(new_found)
112
remaining.difference_update(new_found)
117
92
for parents_provider in self._parent_providers:
118
93
new_found = parents_provider.get_parent_map(remaining)
119
94
found.update(new_found)
126
101
class CachingParentsProvider(object):
127
"""A parents provider which will cache the revision => parents as a dict.
129
This is useful for providers which have an expensive look up.
131
Either a ParentsProvider or a get_parent_map-like callback may be
132
supplied. If it provides extra un-asked-for parents, they will be cached,
133
but filtered out of get_parent_map.
135
The cache is enabled by default, but may be disabled and re-enabled.
102
"""A parents provider which will cache the revision => parents in a dict.
104
This is useful for providers that have an expensive lookup.
137
def __init__(self, parent_provider=None, get_parent_map=None):
140
:param parent_provider: The ParentProvider to use. It or
141
get_parent_map must be supplied.
142
:param get_parent_map: The get_parent_map callback to use. It or
143
parent_provider must be supplied.
107
def __init__(self, parent_provider):
145
108
self._real_provider = parent_provider
146
if get_parent_map is None:
147
self._get_parent_map = self._real_provider.get_parent_map
149
self._get_parent_map = get_parent_map
151
self.enable_cache(True)
109
# Theoretically we could use an LRUCache here
153
112
def __repr__(self):
154
113
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
156
def enable_cache(self, cache_misses=True):
158
if self._cache is not None:
159
raise AssertionError('Cache enabled when already enabled.')
161
self._cache_misses = cache_misses
162
self.missing_keys = set()
164
def disable_cache(self):
165
"""Disable and clear the cache."""
167
self._cache_misses = None
168
self.missing_keys = set()
170
def get_cached_map(self):
171
"""Return any cached get_parent_map values."""
172
if self._cache is None:
174
return dict(self._cache)
176
def get_cached_parent_map(self, keys):
177
"""Return items from the cache.
179
This returns the same info as get_parent_map, but explicitly does not
180
invoke the supplied ParentsProvider to search for uncached values.
185
return dict([(key, cache[key]) for key in keys if key in cache])
187
115
def get_parent_map(self, keys):
188
"""See StackedParentsProvider.get_parent_map."""
116
"""See _StackedParentsProvider.get_parent_map"""
118
# If the _real_provider doesn't have a key, we cache a value of None,
119
# which we then later use to realize we cannot provide a value for that
189
122
cache = self._cache
191
cache = self._get_parent_map(keys)
193
needed_revisions = set(key for key in keys if key not in cache)
194
# Do not ask for negatively cached keys
195
needed_revisions.difference_update(self.missing_keys)
197
parent_map = self._get_parent_map(needed_revisions)
198
cache.update(parent_map)
199
if self._cache_misses:
200
for key in needed_revisions:
201
if key not in parent_map:
202
self.note_missing_key(key)
205
value = cache.get(key)
206
if value is not None:
210
def note_missing_key(self, key):
211
"""Note that key is a missing key."""
212
if self._cache_misses:
213
self.missing_keys.add(key)
216
class CallableToParentsProviderAdapter(object):
217
"""A parents provider that adapts any callable to the parents provider API.
219
i.e. it accepts calls to self.get_parent_map and relays them to the
220
callable it was constructed with.
223
def __init__(self, a_callable):
224
self.callable = a_callable
227
return "%s(%r)" % (self.__class__.__name__, self.callable)
229
def get_parent_map(self, keys):
230
return self.callable(keys)
126
if value is not None:
127
parent_map[key] = value
132
new_parents = self._real_provider.get_parent_map(needed)
133
cache.update(new_parents)
134
parent_map.update(new_parents)
135
needed.difference_update(new_parents)
136
cache.update(dict.fromkeys(needed, None))
233
140
class Graph(object):
306
212
right = searchers[1].seen
307
213
return (left.difference(right), right.difference(left))
309
def find_descendants(self, old_key, new_key):
310
"""Find descendants of old_key that are ancestors of new_key."""
311
child_map = self.get_child_map(self._find_descendant_ancestors(
313
graph = Graph(DictParentsProvider(child_map))
314
searcher = graph._make_breadth_first_searcher([old_key])
318
def _find_descendant_ancestors(self, old_key, new_key):
319
"""Find ancestors of new_key that may be descendants of old_key."""
320
stop = self._make_breadth_first_searcher([old_key])
321
descendants = self._make_breadth_first_searcher([new_key])
322
for revisions in descendants:
323
old_stop = stop.seen.intersection(revisions)
324
descendants.stop_searching_any(old_stop)
325
seen_stop = descendants.find_seen_ancestors(stop.step())
326
descendants.stop_searching_any(seen_stop)
327
return descendants.seen.difference(stop.seen)
329
def get_child_map(self, keys):
330
"""Get a mapping from parents to children of the specified keys.
332
This is simply the inversion of get_parent_map. Only supplied keys
333
will be discovered as children.
334
:return: a dict of key:child_list for keys.
336
parent_map = self._parents_provider.get_parent_map(keys)
338
for child, parents in sorted(parent_map.items()):
339
for parent in parents:
340
parent_child.setdefault(parent, []).append(child)
343
215
def find_distance_to_null(self, target_revision_id, known_revision_ids):
344
216
"""Find the left-hand distance to the NULL_REVISION.
394
266
return known_revnos[cur_tip] + num_steps
396
def find_lefthand_distances(self, keys):
397
"""Find the distance to null for all the keys in keys.
399
:param keys: keys to lookup.
400
:return: A dict key->distance for all of keys.
402
# Optimisable by concurrent searching, but a random spread should get
403
# some sort of hit rate.
410
(key, self.find_distance_to_null(key, known_revnos)))
411
except errors.GhostRevisionsHaveNoRevno:
414
known_revnos.append((key, -1))
415
return dict(known_revnos)
417
268
def find_unique_ancestors(self, unique_revision, common_revisions):
418
269
"""Find the unique ancestors for a revision versus others.
719
570
all_unique_searcher._iterations)
720
571
unique_tip_searchers = next_unique_searchers
573
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
574
def get_parents(self, revisions):
575
"""Find revision ids of the parents of a list of revisions
577
A list is returned of the same length as the input. Each entry
578
is a list of parent ids for the corresponding input revision.
580
[NULL_REVISION] is used as the parent of the first user-committed
581
revision. Its parent list is empty.
583
If the revision is not present (i.e. a ghost), None is used in place
584
of the list of parents.
586
Deprecated in bzr 1.2 - please see get_parent_map.
588
parents = self.get_parent_map(revisions)
589
return [parents.get(r, None) for r in revisions]
722
591
def get_parent_map(self, revisions):
723
592
"""Get a map of key:parent_list for revisions.
944
813
stop.add(parent_id)
947
def find_lefthand_merger(self, merged_key, tip_key):
948
"""Find the first lefthand ancestor of tip_key that merged merged_key.
950
We do this by first finding the descendants of merged_key, then
951
walking through the lefthand ancestry of tip_key until we find a key
952
that doesn't descend from merged_key. Its child is the key that
955
:return: The first lefthand ancestor of tip_key to merge merged_key.
956
merged_key if it is a lefthand ancestor of tip_key.
957
None if no ancestor of tip_key merged merged_key.
959
descendants = self.find_descendants(merged_key, tip_key)
960
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
961
last_candidate = None
962
for candidate in candidate_iterator:
963
if candidate not in descendants:
964
return last_candidate
965
last_candidate = candidate
967
816
def find_unique_lca(self, left_revision, right_revision,
968
817
count_steps=False):
969
818
"""Find a unique LCA.
1061
890
return set([candidate_descendant]) == self.heads(
1062
891
[candidate_ancestor, candidate_descendant])
1064
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1065
"""Determine whether a revision is between two others.
1067
returns true if and only if:
1068
lower_bound_revid <= revid <= upper_bound_revid
1070
return ((upper_bound_revid is None or
1071
self.is_ancestor(revid, upper_bound_revid)) and
1072
(lower_bound_revid is None or
1073
self.is_ancestor(lower_bound_revid, revid)))
1075
893
def _search_for_extra_common(self, common, searchers):
1076
894
"""Make sure that unique nodes are genuinely unique.
1348
1166
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1349
1167
' seen=%r)' % (self._iterations, search, list(self.seen)))
1351
def get_state(self):
1352
"""Get the current state of this searcher.
1354
:return: Tuple with started keys, excludes and included keys
1169
def get_result(self):
1170
"""Get a SearchResult for the current state of this searcher.
1172
:return: A SearchResult for this search so far. The SearchResult is
1173
static - the search can be advanced and the search result will not
1174
be invalidated or altered.
1356
1176
if self._returning == 'next':
1357
1177
# We have to know the current nodes children to be able to list the
1358
1178
# exclude keys for them. However, while we could have a second
1359
1179
# look-ahead result buffer and shuffle things around, this method
1360
1180
# is typically only called once per search - when memoising the
1361
# results of the search.
1181
# results of the search.
1362
1182
found, ghosts, next, parents = self._do_query(self._next_query)
1363
1183
# pretend we didn't query: perhaps we should tweak _do_query to be
1364
1184
# entirely stateless?
1368
1188
next_query = self._next_query
1369
1189
excludes = self._stopped_keys.union(next_query)
1370
1190
included_keys = self.seen.difference(excludes)
1371
return self._started_keys, excludes, included_keys
1373
def _get_result(self):
1374
"""Get a SearchResult for the current state of this searcher.
1376
:return: A SearchResult for this search so far. The SearchResult is
1377
static - the search can be advanced and the search result will not
1378
be invalidated or altered.
1380
from bzrlib.vf_search import SearchResult
1381
(started_keys, excludes, included_keys) = self.get_state()
1382
return SearchResult(started_keys, excludes, len(included_keys),
1191
return SearchResult(self._started_keys, excludes, len(included_keys),
1385
1194
def step(self):
1594
1395
return revs, ghosts
1597
def invert_parent_map(parent_map):
1598
"""Given a map from child => parents, create a map of parent=>children"""
1600
for child, parents in parent_map.iteritems():
1602
# Any given parent is likely to have only a small handful
1603
# of children, many will have only one. So we avoid mem overhead of
1604
# a list, in exchange for extra copying of tuples
1605
if p not in child_map:
1606
child_map[p] = (child,)
1608
child_map[p] = child_map[p] + (child,)
1398
class SearchResult(object):
1399
"""The result of a breadth first search.
1401
A SearchResult provides the ability to reconstruct the search or access a
1402
set of the keys the search found.
1405
def __init__(self, start_keys, exclude_keys, key_count, keys):
1406
"""Create a SearchResult.
1408
:param start_keys: The keys the search started at.
1409
:param exclude_keys: The keys the search excludes.
1410
:param key_count: The total number of keys (from start to but not
1412
:param keys: The keys the search found. Note that in future we may get
1413
a SearchResult from a smart server, in which case the keys list is
1414
not necessarily immediately available.
1416
self._recipe = (start_keys, exclude_keys, key_count)
1417
self._keys = frozenset(keys)
1419
def get_recipe(self):
1420
"""Return a recipe that can be used to replay this search.
1422
The recipe allows reconstruction of the same results at a later date
1423
without knowing all the found keys. The essential elements are a list
1424
of keys to start and and to stop at. In order to give reproducible
1425
results when ghosts are encountered by a search they are automatically
1426
added to the exclude list (or else ghost filling may alter the
1429
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1430
recreate the results of this search, create a breadth first
1431
searcher on the same graph starting at start_keys. Then call next()
1432
(or next_with_ghosts()) repeatedly, and on every result, call
1433
stop_searching_any on any keys from the exclude_keys set. The
1434
revision_count value acts as a trivial cross-check - the found
1435
revisions of the new search should have as many elements as
1436
revision_count. If it does not, then additional revisions have been
1437
ghosted since the search was executed the first time and the second
1443
"""Return the keys found in this search.
1445
:return: A set of keys.
1612
1450
def collapse_linear_regions(parent_map):
1680
1518
removed.add(node)
1685
class GraphThunkIdsToKeys(object):
1686
"""Forwards calls about 'ids' to be about keys internally."""
1688
def __init__(self, graph):
1691
def topo_sort(self):
1692
return [r for (r,) in self._graph.topo_sort()]
1694
def heads(self, ids):
1695
"""See Graph.heads()"""
1696
as_keys = [(i,) for i in ids]
1697
head_keys = self._graph.heads(as_keys)
1698
return set([h[0] for h in head_keys])
1700
def merge_sort(self, tip_revision):
1701
nodes = self._graph.merge_sort((tip_revision,))
1703
node.key = node.key[0]
1706
def add_node(self, revision, parents):
1707
self._graph.add_node((revision,), [(p,) for p in parents])
1710
_counters = [0,0,0,0,0,0,0]
1712
from bzrlib._known_graph_pyx import KnownGraph
1713
except ImportError, e:
1714
osutils.failed_to_load_extension(e)
1715
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
