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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
from __future__ import absolute_import
19
21
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
63
68
def get_parent_map(self, keys):
64
"""See _StackedParentsProvider.get_parent_map"""
69
"""See StackedParentsProvider.get_parent_map"""
65
70
ancestry = self.ancestry
66
return dict((k, ancestry[k]) for k in keys if k in ancestry)
69
class _StackedParentsProvider(object):
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.
71
80
def __init__(self, parent_providers):
72
81
self._parent_providers = parent_providers
74
83
def __repr__(self):
75
return "_StackedParentsProvider(%r)" % self._parent_providers
84
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
77
86
def get_parent_map(self, keys):
78
87
"""Get a mapping of keys => parents
101
126
class CachingParentsProvider(object):
102
"""A parents provider which will cache the revision => parents in a dict.
104
This is useful for providers that have an expensive lookup.
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.
137
def __init__(self, parent_provider=None, get_parent_map=None):
107
def __init__(self, parent_provider):
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.
108
145
self._real_provider = parent_provider
109
# Theoretically we could use an LRUCache here
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)
154
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
def get_parent_map(self, keys):
188
"""See StackedParentsProvider.get_parent_map."""
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
112
226
def __repr__(self):
113
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
227
return "%s(%r)" % (self.__class__.__name__, self.callable)
115
229
def get_parent_map(self, keys):
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
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))
230
return self.callable(keys)
140
233
class Graph(object):
212
306
right = searchers[1].seen
213
307
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)
215
343
def find_distance_to_null(self, target_revision_id, known_revision_ids):
216
344
"""Find the left-hand distance to the NULL_REVISION.
266
394
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)
268
417
def find_unique_ancestors(self, unique_revision, common_revisions):
269
418
"""Find the unique ancestors for a revision versus others.
570
719
all_unique_searcher._iterations)
571
720
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]
591
722
def get_parent_map(self, revisions):
592
723
"""Get a map of key:parent_list for revisions.
813
944
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
816
967
def find_unique_lca(self, left_revision, right_revision,
817
968
count_steps=False):
818
969
"""Find a unique LCA.
890
1061
return set([candidate_descendant]) == self.heads(
891
1062
[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)))
893
1075
def _search_for_extra_common(self, common, searchers):
894
1076
"""Make sure that unique nodes are genuinely unique.
1166
1348
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1167
1349
' seen=%r)' % (self._iterations, search, list(self.seen)))
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.
1351
def get_state(self):
1352
"""Get the current state of this searcher.
1354
:return: Tuple with started keys, excludes and included keys
1176
1356
if self._returning == 'next':
1177
1357
# We have to know the current nodes children to be able to list the
1178
1358
# exclude keys for them. However, while we could have a second
1179
1359
# look-ahead result buffer and shuffle things around, this method
1180
1360
# is typically only called once per search - when memoising the
1181
# results of the search.
1361
# results of the search.
1182
1362
found, ghosts, next, parents = self._do_query(self._next_query)
1183
1363
# pretend we didn't query: perhaps we should tweak _do_query to be
1184
1364
# entirely stateless?
1188
1368
next_query = self._next_query
1189
1369
excludes = self._stopped_keys.union(next_query)
1190
1370
included_keys = self.seen.difference(excludes)
1191
return SearchResult(self._started_keys, excludes, len(included_keys),
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),
1194
1385
def step(self):
1402
1594
return revs, ghosts
1405
class SearchResult(object):
1406
"""The result of a breadth first search.
1408
A SearchResult provides the ability to reconstruct the search or access a
1409
set of the keys the search found.
1412
def __init__(self, start_keys, exclude_keys, key_count, keys):
1413
"""Create a SearchResult.
1415
:param start_keys: The keys the search started at.
1416
:param exclude_keys: The keys the search excludes.
1417
:param key_count: The total number of keys (from start to but not
1419
:param keys: The keys the search found. Note that in future we may get
1420
a SearchResult from a smart server, in which case the keys list is
1421
not necessarily immediately available.
1423
self._recipe = (start_keys, exclude_keys, key_count)
1424
self._keys = frozenset(keys)
1426
def get_recipe(self):
1427
"""Return a recipe that can be used to replay this search.
1429
The recipe allows reconstruction of the same results at a later date
1430
without knowing all the found keys. The essential elements are a list
1431
of keys to start and and to stop at. In order to give reproducible
1432
results when ghosts are encountered by a search they are automatically
1433
added to the exclude list (or else ghost filling may alter the
1436
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1437
recreate the results of this search, create a breadth first
1438
searcher on the same graph starting at start_keys. Then call next()
1439
(or next_with_ghosts()) repeatedly, and on every result, call
1440
stop_searching_any on any keys from the exclude_keys set. The
1441
revision_count value acts as a trivial cross-check - the found
1442
revisions of the new search should have as many elements as
1443
revision_count. If it does not, then additional revisions have been
1444
ghosted since the search was executed the first time and the second
1450
"""Return the keys found in this search.
1452
:return: A set of keys.
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,)
1457
1612
def collapse_linear_regions(parent_map):
1525
1680
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
