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 (
29
28
STEP_UNIQUE_SEARCHER_EVERY = 5
60
59
def __repr__(self):
61
60
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
62
def get_parent_map(self, keys):
69
"""See StackedParentsProvider.get_parent_map"""
63
"""See _StackedParentsProvider.get_parent_map"""
70
64
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.
65
return dict((k, ancestry[k]) for k in keys if k in ancestry)
68
class _StackedParentsProvider(object):
80
70
def __init__(self, parent_providers):
81
71
self._parent_providers = parent_providers
83
73
def __repr__(self):
84
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
74
return "_StackedParentsProvider(%r)" % self._parent_providers
86
76
def get_parent_map(self, keys):
87
77
"""Get a mapping of keys => parents
100
90
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
91
for parents_provider in self._parent_providers:
118
92
new_found = parents_provider.get_parent_map(remaining)
119
93
found.update(new_found)
159
133
raise AssertionError('Cache enabled when already enabled.')
161
135
self._cache_misses = cache_misses
162
self.missing_keys = set()
164
137
def disable_cache(self):
165
138
"""Disable and clear the cache."""
166
139
self._cache = None
167
self._cache_misses = None
168
self.missing_keys = set()
170
141
def get_cached_map(self):
171
142
"""Return any cached get_parent_map values."""
172
143
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])
145
return dict((k, v) for k, v in self._cache.items()
187
148
def get_parent_map(self, keys):
188
"""See StackedParentsProvider.get_parent_map."""
191
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)
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)
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)
233
170
class Graph(object):
284
221
common ancestor of all border ancestors, because this shows that it
285
222
cannot be a descendant of any border ancestor.
287
The scaling of this operation should be proportional to:
224
The scaling of this operation should be proportional to
289
225
1. The number of uncommon ancestors
290
226
2. The number of border ancestors
291
227
3. The length of the shortest path between a border ancestor and an
306
242
right = searchers[1].seen
307
243
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
245
def find_distance_to_null(self, target_revision_id, known_revision_ids):
344
246
"""Find the left-hand distance to the NULL_REVISION.
394
296
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
298
def find_unique_ancestors(self, unique_revision, common_revisions):
418
299
"""Find the unique ancestors for a revision versus others.
719
600
all_unique_searcher._iterations)
720
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]
722
621
def get_parent_map(self, revisions):
723
622
"""Get a map of key:parent_list for revisions.
944
843
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
846
def find_unique_lca(self, left_revision, right_revision,
968
847
count_steps=False):
969
848
"""Find a unique LCA.
1021
900
yield (ghost, None)
1022
901
pending = next_pending
1024
def iter_lefthand_ancestry(self, start_key, stop_keys=None):
1025
if stop_keys is None:
1027
next_key = start_key
1028
def get_parents(key):
1030
return self._parents_provider.get_parent_map([key])[key]
1032
raise errors.RevisionNotPresent(next_key, self)
1034
if next_key in stop_keys:
1036
parents = get_parents(next_key)
1038
if len(parents) == 0:
1041
next_key = parents[0]
1043
903
def iter_topo_order(self, revisions):
1044
904
"""Iterate through the input revisions in topological order.
1061
920
return set([candidate_descendant]) == self.heads(
1062
921
[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
923
def _search_for_extra_common(self, common, searchers):
1076
924
"""Make sure that unique nodes are genuinely unique.
1348
1196
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1349
1197
' 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
1199
def get_result(self):
1200
"""Get a SearchResult for the current state of this searcher.
1202
:return: A SearchResult for this search so far. The SearchResult is
1203
static - the search can be advanced and the search result will not
1204
be invalidated or altered.
1356
1206
if self._returning == 'next':
1357
1207
# We have to know the current nodes children to be able to list the
1358
1208
# exclude keys for them. However, while we could have a second
1359
1209
# look-ahead result buffer and shuffle things around, this method
1360
1210
# is typically only called once per search - when memoising the
1361
# results of the search.
1211
# results of the search.
1362
1212
found, ghosts, next, parents = self._do_query(self._next_query)
1363
1213
# pretend we didn't query: perhaps we should tweak _do_query to be
1364
1214
# entirely stateless?
1368
1218
next_query = self._next_query
1369
1219
excludes = self._stopped_keys.union(next_query)
1370
1220
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),
1221
return SearchResult(self._started_keys, excludes, len(included_keys),
1385
1224
def step(self):
1462
1301
parents_of_found = set()
1463
1302
# revisions may contain nodes that point to other nodes in revisions:
1464
1303
# we want to filter them out.
1466
seen.update(revisions)
1304
self.seen.update(revisions)
1467
1305
parent_map = self._parents_provider.get_parent_map(revisions)
1468
1306
found_revisions.update(parent_map)
1469
1307
for rev_id, parents in parent_map.iteritems():
1470
1308
if parents is None:
1472
new_found_parents = [p for p in parents if p not in seen]
1310
new_found_parents = [p for p in parents if p not in self.seen]
1473
1311
if new_found_parents:
1474
1312
# Calling set.update() with an empty generator is actually
1475
1313
# rather expensive.
1544
1382
self._current_ghosts.intersection(revisions))
1545
1383
self._current_present.difference_update(stopped)
1546
1384
self._current_ghosts.difference_update(stopped)
1547
# stopping 'x' should stop returning parents of 'x', but
1385
# stopping 'x' should stop returning parents of 'x', but
1548
1386
# not if 'y' always references those same parents
1549
1387
stop_rev_references = {}
1550
1388
for rev in stopped_present:
1594
1432
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,)
1435
class SearchResult(object):
1436
"""The result of a breadth first search.
1438
A SearchResult provides the ability to reconstruct the search or access a
1439
set of the keys the search found.
1442
def __init__(self, start_keys, exclude_keys, key_count, keys):
1443
"""Create a SearchResult.
1445
:param start_keys: The keys the search started at.
1446
:param exclude_keys: The keys the search excludes.
1447
:param key_count: The total number of keys (from start to but not
1449
:param keys: The keys the search found. Note that in future we may get
1450
a SearchResult from a smart server, in which case the keys list is
1451
not necessarily immediately available.
1453
self._recipe = (start_keys, exclude_keys, key_count)
1454
self._keys = frozenset(keys)
1456
def get_recipe(self):
1457
"""Return a recipe that can be used to replay this search.
1459
The recipe allows reconstruction of the same results at a later date
1460
without knowing all the found keys. The essential elements are a list
1461
of keys to start and and to stop at. In order to give reproducible
1462
results when ghosts are encountered by a search they are automatically
1463
added to the exclude list (or else ghost filling may alter the
1466
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1467
recreate the results of this search, create a breadth first
1468
searcher on the same graph starting at start_keys. Then call next()
1469
(or next_with_ghosts()) repeatedly, and on every result, call
1470
stop_searching_any on any keys from the exclude_keys set. The
1471
revision_count value acts as a trivial cross-check - the found
1472
revisions of the new search should have as many elements as
1473
revision_count. If it does not, then additional revisions have been
1474
ghosted since the search was executed the first time and the second
1480
"""Return the keys found in this search.
1482
:return: A set of keys.
1612
1487
def collapse_linear_regions(parent_map):
1680
1555
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
