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 (
28
29
STEP_UNIQUE_SEARCHER_EVERY = 5
59
60
def __repr__(self):
60
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
62
68
def get_parent_map(self, keys):
63
"""See _StackedParentsProvider.get_parent_map"""
69
"""See StackedParentsProvider.get_parent_map"""
64
70
ancestry = self.ancestry
65
return dict((k, ancestry[k]) for k in keys if k in ancestry)
68
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.
70
80
def __init__(self, parent_providers):
71
81
self._parent_providers = parent_providers
73
83
def __repr__(self):
74
return "_StackedParentsProvider(%r)" % self._parent_providers
84
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
76
86
def get_parent_map(self, keys):
77
87
"""Get a mapping of keys => parents
90
100
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)
91
117
for parents_provider in self._parent_providers:
92
118
new_found = parents_provider.get_parent_map(remaining)
93
119
found.update(new_found)
133
159
raise AssertionError('Cache enabled when already enabled.')
135
161
self._cache_misses = cache_misses
162
self.missing_keys = set()
137
164
def disable_cache(self):
138
165
"""Disable and clear the cache."""
139
166
self._cache = None
167
self._cache_misses = None
168
self.missing_keys = set()
141
170
def get_cached_map(self):
142
171
"""Return any cached get_parent_map values."""
143
172
if self._cache is None:
145
return dict((k, v) for k, v in self._cache.items()
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])
148
187
def get_parent_map(self, 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)
188
"""See StackedParentsProvider.get_parent_map."""
191
cache = self._get_parent_map(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)
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)
170
233
class Graph(object):
221
284
common ancestor of all border ancestors, because this shows that it
222
285
cannot be a descendant of any border ancestor.
224
The scaling of this operation should be proportional to
287
The scaling of this operation should be proportional to:
225
289
1. The number of uncommon ancestors
226
290
2. The number of border ancestors
227
291
3. The length of the shortest path between a border ancestor and an
242
306
right = searchers[1].seen
243
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)
245
343
def find_distance_to_null(self, target_revision_id, known_revision_ids):
246
344
"""Find the left-hand distance to the NULL_REVISION.
296
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)
298
417
def find_unique_ancestors(self, unique_revision, common_revisions):
299
418
"""Find the unique ancestors for a revision versus others.
600
719
all_unique_searcher._iterations)
601
720
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]
621
722
def get_parent_map(self, revisions):
622
723
"""Get a map of key:parent_list for revisions.
843
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
846
967
def find_unique_lca(self, left_revision, right_revision,
847
968
count_steps=False):
848
969
"""Find a unique LCA.
900
1021
yield (ghost, None)
901
1022
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]
903
1043
def iter_topo_order(self, revisions):
904
1044
"""Iterate through the input revisions in topological order.
920
1061
return set([candidate_descendant]) == self.heads(
921
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)))
923
1075
def _search_for_extra_common(self, common, searchers):
924
1076
"""Make sure that unique nodes are genuinely unique.
1196
1348
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1197
1349
' seen=%r)' % (self._iterations, search, list(self.seen)))
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.
1351
def get_state(self):
1352
"""Get the current state of this searcher.
1354
:return: Tuple with started keys, excludes and included keys
1206
1356
if self._returning == 'next':
1207
1357
# We have to know the current nodes children to be able to list the
1208
1358
# exclude keys for them. However, while we could have a second
1209
1359
# look-ahead result buffer and shuffle things around, this method
1210
1360
# is typically only called once per search - when memoising the
1211
# results of the search.
1361
# results of the search.
1212
1362
found, ghosts, next, parents = self._do_query(self._next_query)
1213
1363
# pretend we didn't query: perhaps we should tweak _do_query to be
1214
1364
# entirely stateless?
1218
1368
next_query = self._next_query
1219
1369
excludes = self._stopped_keys.union(next_query)
1220
1370
included_keys = self.seen.difference(excludes)
1221
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),
1224
1385
def step(self):
1301
1462
parents_of_found = set()
1302
1463
# revisions may contain nodes that point to other nodes in revisions:
1303
1464
# we want to filter them out.
1304
self.seen.update(revisions)
1466
seen.update(revisions)
1305
1467
parent_map = self._parents_provider.get_parent_map(revisions)
1306
1468
found_revisions.update(parent_map)
1307
1469
for rev_id, parents in parent_map.iteritems():
1308
1470
if parents is None:
1310
new_found_parents = [p for p in parents if p not in self.seen]
1472
new_found_parents = [p for p in parents if p not in seen]
1311
1473
if new_found_parents:
1312
1474
# Calling set.update() with an empty generator is actually
1313
1475
# rather expensive.
1382
1544
self._current_ghosts.intersection(revisions))
1383
1545
self._current_present.difference_update(stopped)
1384
1546
self._current_ghosts.difference_update(stopped)
1385
# stopping 'x' should stop returning parents of 'x', but
1547
# stopping 'x' should stop returning parents of 'x', but
1386
1548
# not if 'y' always references those same parents
1387
1549
stop_rev_references = {}
1388
1550
for rev in stopped_present:
1432
1594
return revs, ghosts
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.
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,)
1487
1612
def collapse_linear_regions(parent_map):
1555
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
