4988.10.3
by John Arbash Meinel
Merge bzr.dev 5007, resolve conflict, update NEWS |
1 |
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
2 |
#
|
3 |
# This program is free software; you can redistribute it and/or modify
|
|
4 |
# it under the terms of the GNU General Public License as published by
|
|
5 |
# the Free Software Foundation; either version 2 of the License, or
|
|
6 |
# (at your option) any later version.
|
|
7 |
#
|
|
8 |
# This program is distributed in the hope that it will be useful,
|
|
9 |
# but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
10 |
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
11 |
# GNU General Public License for more details.
|
|
12 |
#
|
|
13 |
# You should have received a copy of the GNU General Public License
|
|
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
|
|
16 |
||
17 |
"""Persistent maps from tuple_of_strings->string using CHK stores.
|
|
18 |
||
19 |
Overview and current status:
|
|
20 |
||
21 |
The CHKMap class implements a dict from tuple_of_strings->string by using a trie
|
|
22 |
with internal nodes of 8-bit fan out; The key tuples are mapped to strings by
|
|
23 |
joining them by \x00, and \x00 padding shorter keys out to the length of the
|
|
24 |
longest key. Leaf nodes are packed as densely as possible, and internal nodes
|
|
3735.19.1
by Ian Clatworthy
CHKMap cleanups |
25 |
are all an additional 8-bits wide leading to a sparse upper tree.
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
26 |
|
27 |
Updates to a CHKMap are done preferentially via the apply_delta method, to
|
|
28 |
allow optimisation of the update operation; but individual map/unmap calls are
|
|
4526.9.5
by Robert Collins
Require that added ids in inventory deltas be new. |
29 |
possible and supported. Individual changes via map/unmap are buffered in memory
|
30 |
until the _save method is called to force serialisation of the tree.
|
|
31 |
apply_delta records its changes immediately by performing an implicit _save.
|
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
32 |
|
33 |
TODO:
|
|
34 |
-----
|
|
35 |
||
36 |
Densely packed upper nodes.
|
|
37 |
||
38 |
"""
|
|
39 |
||
40 |
import heapq |
|
4797.7.1
by Robert Collins
Introduce a threading.local to isolate the chk_map page cache from other threads. |
41 |
import threading |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
42 |
|
43 |
from bzrlib import lazy_import |
|
44 |
lazy_import.lazy_import(globals(), """ |
|
4526.9.5
by Robert Collins
Require that added ids in inventory deltas be new. |
45 |
from bzrlib import (
|
46 |
errors,
|
|
47 |
versionedfile,
|
|
48 |
)
|
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
49 |
""") |
50 |
from bzrlib import ( |
|
51 |
lru_cache, |
|
52 |
osutils, |
|
53 |
registry, |
|
4668.3.2
by John Arbash Meinel
Don't forget to import the library... |
54 |
static_tuple, |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
55 |
trace, |
56 |
)
|
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
57 |
from bzrlib.static_tuple import StaticTuple |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
58 |
|
3735.19.1
by Ian Clatworthy
CHKMap cleanups |
59 |
# approx 4MB
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
60 |
# If each line is 50 bytes, and you have 255 internal pages, with 255-way fan
|
61 |
# out, it takes 3.1MB to cache the layer.
|
|
62 |
_PAGE_CACHE_SIZE = 4*1024*1024 |
|
4797.7.1
by Robert Collins
Introduce a threading.local to isolate the chk_map page cache from other threads. |
63 |
# Per thread caches for 2 reasons:
|
64 |
# - in the server we may be serving very different content, so we get less
|
|
65 |
# cache thrashing.
|
|
66 |
# - we avoid locking on every cache lookup.
|
|
67 |
_thread_caches = threading.local() |
|
68 |
# The page cache.
|
|
69 |
_thread_caches.page_cache = None |
|
70 |
||
71 |
def _get_cache(): |
|
72 |
"""Get the per-thread page cache.
|
|
73 |
||
74 |
We need a function to do this because in a new thread the _thread_caches
|
|
75 |
threading.local object does not have the cache initialized yet.
|
|
76 |
"""
|
|
77 |
page_cache = getattr(_thread_caches, 'page_cache', None) |
|
78 |
if page_cache is None: |
|
79 |
# We are caching bytes so len(value) is perfectly accurate
|
|
80 |
page_cache = lru_cache.LRUSizeCache(_PAGE_CACHE_SIZE) |
|
81 |
_thread_caches.page_cache = page_cache |
|
82 |
return page_cache |
|
83 |
||
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
84 |
|
4543.2.2
by John Arbash Meinel
work out some tests that expose that bundles don't work w/ 2a formats. |
85 |
def clear_cache(): |
4797.7.1
by Robert Collins
Introduce a threading.local to isolate the chk_map page cache from other threads. |
86 |
_get_cache().clear() |
87 |
||
4543.2.2
by John Arbash Meinel
work out some tests that expose that bundles don't work w/ 2a formats. |
88 |
|
3735.2.123
by Ian Clatworthy
only check for remap if changes are interesting in size |
89 |
# If a ChildNode falls below this many bytes, we check for a remap
|
90 |
_INTERESTING_NEW_SIZE = 50 |
|
91 |
# If a ChildNode shrinks by more than this amount, we check for a remap
|
|
92 |
_INTERESTING_SHRINKAGE_LIMIT = 20 |
|
93 |
# If we delete more than this many nodes applying a delta, we check for a remap
|
|
94 |
_INTERESTING_DELETES_LIMIT = 5 |
|
95 |
||
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
96 |
|
97 |
def _search_key_plain(key): |
|
98 |
"""Map the key tuple into a search string that just uses the key bytes."""
|
|
99 |
return '\x00'.join(key) |
|
100 |
||
101 |
||
102 |
search_key_registry = registry.Registry() |
|
103 |
search_key_registry.register('plain', _search_key_plain) |
|
104 |
||
105 |
||
106 |
class CHKMap(object): |
|
107 |
"""A persistent map from string to string backed by a CHK store."""
|
|
108 |
||
4759.1.2
by John Arbash Meinel
Change CHKMap to use __slots__ |
109 |
__slots__ = ('_store', '_root_node', '_search_key_func') |
110 |
||
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
111 |
def __init__(self, store, root_key, search_key_func=None): |
112 |
"""Create a CHKMap object.
|
|
113 |
||
114 |
:param store: The store the CHKMap is stored in.
|
|
115 |
:param root_key: The root key of the map. None to create an empty
|
|
116 |
CHKMap.
|
|
117 |
:param search_key_func: A function mapping a key => bytes. These bytes
|
|
118 |
are then used by the internal nodes to split up leaf nodes into
|
|
119 |
multiple pages.
|
|
120 |
"""
|
|
121 |
self._store = store |
|
122 |
if search_key_func is None: |
|
123 |
search_key_func = _search_key_plain |
|
124 |
self._search_key_func = search_key_func |
|
125 |
if root_key is None: |
|
126 |
self._root_node = LeafNode(search_key_func=search_key_func) |
|
127 |
else: |
|
128 |
self._root_node = self._node_key(root_key) |
|
129 |
||
130 |
def apply_delta(self, delta): |
|
131 |
"""Apply a delta to the map.
|
|
132 |
||
133 |
:param delta: An iterable of old_key, new_key, new_value tuples.
|
|
134 |
If new_key is not None, then new_key->new_value is inserted
|
|
135 |
into the map; if old_key is not None, then the old mapping
|
|
136 |
of old_key is removed.
|
|
137 |
"""
|
|
3735.2.123
by Ian Clatworthy
only check for remap if changes are interesting in size |
138 |
delete_count = 0 |
4526.9.5
by Robert Collins
Require that added ids in inventory deltas be new. |
139 |
# Check preconditions first.
|
4679.9.9
by John Arbash Meinel
Create a Barrier at the CHKMap interface. |
140 |
as_st = StaticTuple.from_sequence |
141 |
new_items = set([as_st(key) for (old, key, value) in delta |
|
142 |
if key is not None and old is None]) |
|
4526.9.5
by Robert Collins
Require that added ids in inventory deltas be new. |
143 |
existing_new = list(self.iteritems(key_filter=new_items)) |
144 |
if existing_new: |
|
145 |
raise errors.InconsistentDeltaDelta(delta, |
|
146 |
"New items are already in the map %r." % existing_new) |
|
147 |
# Now apply changes.
|
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
148 |
for old, new, value in delta: |
149 |
if old is not None and old != new: |
|
3735.2.122
by Ian Clatworthy
don't check_remap on every unmap call in CHKMap.apply_delta() |
150 |
self.unmap(old, check_remap=False) |
3735.2.123
by Ian Clatworthy
only check for remap if changes are interesting in size |
151 |
delete_count += 1 |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
152 |
for old, new, value in delta: |
153 |
if new is not None: |
|
154 |
self.map(new, value) |
|
3735.2.123
by Ian Clatworthy
only check for remap if changes are interesting in size |
155 |
if delete_count > _INTERESTING_DELETES_LIMIT: |
156 |
trace.mutter("checking remap as %d deletions", delete_count) |
|
3735.2.122
by Ian Clatworthy
don't check_remap on every unmap call in CHKMap.apply_delta() |
157 |
self._check_remap() |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
158 |
return self._save() |
159 |
||
160 |
def _ensure_root(self): |
|
161 |
"""Ensure that the root node is an object not a key."""
|
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
162 |
if type(self._root_node) is StaticTuple: |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
163 |
# Demand-load the root
|
164 |
self._root_node = self._get_node(self._root_node) |
|
165 |
||
166 |
def _get_node(self, node): |
|
167 |
"""Get a node.
|
|
168 |
||
3735.19.1
by Ian Clatworthy
CHKMap cleanups |
169 |
Note that this does not update the _items dict in objects containing a
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
170 |
reference to this node. As such it does not prevent subsequent IO being
|
171 |
performed.
|
|
172 |
||
173 |
:param node: A tuple key or node object.
|
|
174 |
:return: A node object.
|
|
175 |
"""
|
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
176 |
if type(node) is StaticTuple: |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
177 |
bytes = self._read_bytes(node) |
178 |
return _deserialise(bytes, node, |
|
179 |
search_key_func=self._search_key_func) |
|
180 |
else: |
|
181 |
return node |
|
182 |
||
183 |
def _read_bytes(self, key): |
|
3735.2.124
by Ian Clatworthy
use the page cache in CHKMap._read_bytes() |
184 |
try: |
4797.7.1
by Robert Collins
Introduce a threading.local to isolate the chk_map page cache from other threads. |
185 |
return _get_cache()[key] |
3735.2.124
by Ian Clatworthy
use the page cache in CHKMap._read_bytes() |
186 |
except KeyError: |
187 |
stream = self._store.get_record_stream([key], 'unordered', True) |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
188 |
bytes = stream.next().get_bytes_as('fulltext') |
4797.7.1
by Robert Collins
Introduce a threading.local to isolate the chk_map page cache from other threads. |
189 |
_get_cache()[key] = bytes |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
190 |
return bytes |
191 |
||
192 |
def _dump_tree(self, include_keys=False): |
|
193 |
"""Return the tree in a string representation."""
|
|
194 |
self._ensure_root() |
|
195 |
res = self._dump_tree_node(self._root_node, prefix='', indent='', |
|
196 |
include_keys=include_keys) |
|
197 |
res.append('') # Give a trailing '\n' |
|
198 |
return '\n'.join(res) |
|
199 |
||
200 |
def _dump_tree_node(self, node, prefix, indent, include_keys=True): |
|
201 |
"""For this node and all children, generate a string representation."""
|
|
202 |
result = [] |
|
203 |
if not include_keys: |
|
204 |
key_str = '' |
|
205 |
else: |
|
206 |
node_key = node.key() |
|
207 |
if node_key is not None: |
|
208 |
key_str = ' %s' % (node_key[0],) |
|
209 |
else: |
|
210 |
key_str = ' None' |
|
211 |
result.append('%s%r %s%s' % (indent, prefix, node.__class__.__name__, |
|
212 |
key_str)) |
|
213 |
if type(node) is InternalNode: |
|
214 |
# Trigger all child nodes to get loaded
|
|
215 |
list(node._iter_nodes(self._store)) |
|
216 |
for prefix, sub in sorted(node._items.iteritems()): |
|
217 |
result.extend(self._dump_tree_node(sub, prefix, indent + ' ', |
|
218 |
include_keys=include_keys)) |
|
219 |
else: |
|
220 |
for key, value in sorted(node._items.iteritems()): |
|
221 |
# Don't use prefix nor indent here to line up when used in
|
|
222 |
# tests in conjunction with assertEqualDiff
|
|
4679.9.1
by John Arbash Meinel
Merge in the static-tuple-no-use branch, and bring back the chk_map use. |
223 |
result.append(' %r %r' % (tuple(key), value)) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
224 |
return result |
225 |
||
226 |
@classmethod
|
|
3735.19.1
by Ian Clatworthy
CHKMap cleanups |
227 |
def from_dict(klass, store, initial_value, maximum_size=0, key_width=1, |
228 |
search_key_func=None): |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
229 |
"""Create a CHKMap in store with initial_value as the content.
|
230 |
||
231 |
:param store: The store to record initial_value in, a VersionedFiles
|
|
232 |
object with 1-tuple keys supporting CHK key generation.
|
|
233 |
:param initial_value: A dict to store in store. Its keys and values
|
|
234 |
must be bytestrings.
|
|
235 |
:param maximum_size: The maximum_size rule to apply to nodes. This
|
|
236 |
determines the size at which no new data is added to a single node.
|
|
237 |
:param key_width: The number of elements in each key_tuple being stored
|
|
238 |
in this map.
|
|
3735.19.1
by Ian Clatworthy
CHKMap cleanups |
239 |
:param search_key_func: A function mapping a key => bytes. These bytes
|
240 |
are then used by the internal nodes to split up leaf nodes into
|
|
241 |
multiple pages.
|
|
242 |
:return: The root chk of the resulting CHKMap.
|
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
243 |
"""
|
4413.5.7
by John Arbash Meinel
Switch to using a single code path for from_dict(). |
244 |
root_key = klass._create_directly(store, initial_value, |
245 |
maximum_size=maximum_size, key_width=key_width, |
|
246 |
search_key_func=search_key_func) |
|
4679.9.15
by John Arbash Meinel
Cleanup some code paths. Make _check_key a helper that can be used |
247 |
if type(root_key) is not StaticTuple: |
248 |
raise AssertionError('we got a %s instead of a StaticTuple' |
|
249 |
% (type(root_key),)) |
|
4413.5.5
by John Arbash Meinel
Make it more obvious how the two creation methods are defined. |
250 |
return root_key |
251 |
||
252 |
@classmethod
|
|
253 |
def _create_via_map(klass, store, initial_value, maximum_size=0, |
|
254 |
key_width=1, search_key_func=None): |
|
255 |
result = klass(store, None, search_key_func=search_key_func) |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
256 |
result._root_node.set_maximum_size(maximum_size) |
257 |
result._root_node._key_width = key_width |
|
258 |
delta = [] |
|
259 |
for key, value in initial_value.items(): |
|
260 |
delta.append((None, key, value)) |
|
4413.5.4
by John Arbash Meinel
Change CHKMap.from_dict to create a LeafNode and split it. |
261 |
root_key = result.apply_delta(delta) |
4413.5.5
by John Arbash Meinel
Make it more obvious how the two creation methods are defined. |
262 |
return root_key |
263 |
||
264 |
@classmethod
|
|
265 |
def _create_directly(klass, store, initial_value, maximum_size=0, |
|
266 |
key_width=1, search_key_func=None): |
|
4413.5.4
by John Arbash Meinel
Change CHKMap.from_dict to create a LeafNode and split it. |
267 |
node = LeafNode(search_key_func=search_key_func) |
268 |
node.set_maximum_size(maximum_size) |
|
269 |
node._key_width = key_width |
|
4679.9.9
by John Arbash Meinel
Create a Barrier at the CHKMap interface. |
270 |
as_st = StaticTuple.from_sequence |
271 |
node._items = dict([(as_st(key), val) for key, val |
|
272 |
in initial_value.iteritems()]) |
|
4413.5.4
by John Arbash Meinel
Change CHKMap.from_dict to create a LeafNode and split it. |
273 |
node._raw_size = sum([node._key_value_len(key, value) |
4679.9.9
by John Arbash Meinel
Create a Barrier at the CHKMap interface. |
274 |
for key,value in node._items.iteritems()]) |
4413.5.4
by John Arbash Meinel
Change CHKMap.from_dict to create a LeafNode and split it. |
275 |
node._len = len(node._items) |
276 |
node._compute_search_prefix() |
|
277 |
node._compute_serialised_prefix() |
|
278 |
if (node._len > 1 |
|
279 |
and maximum_size |
|
280 |
and node._current_size() > maximum_size): |
|
281 |
prefix, node_details = node._split(store) |
|
4413.5.8
by John Arbash Meinel
Change some asserts into raise: calls. |
282 |
if len(node_details) == 1: |
283 |
raise AssertionError('Failed to split using node._split') |
|
4413.5.4
by John Arbash Meinel
Change CHKMap.from_dict to create a LeafNode and split it. |
284 |
node = InternalNode(prefix, search_key_func=search_key_func) |
285 |
node.set_maximum_size(maximum_size) |
|
286 |
node._key_width = key_width |
|
287 |
for split, subnode in node_details: |
|
288 |
node.add_node(split, subnode) |
|
289 |
keys = list(node.serialise(store)) |
|
4679.9.15
by John Arbash Meinel
Cleanup some code paths. Make _check_key a helper that can be used |
290 |
return keys[-1] |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
291 |
|
292 |
def iter_changes(self, basis): |
|
293 |
"""Iterate over the changes between basis and self.
|
|
294 |
||
295 |
:return: An iterator of tuples: (key, old_value, new_value). Old_value
|
|
296 |
is None for keys only in self; new_value is None for keys only in
|
|
297 |
basis.
|
|
298 |
"""
|
|
299 |
# Overview:
|
|
300 |
# Read both trees in lexographic, highest-first order.
|
|
301 |
# Any identical nodes we skip
|
|
302 |
# Any unique prefixes we output immediately.
|
|
303 |
# values in a leaf node are treated as single-value nodes in the tree
|
|
304 |
# which allows them to be not-special-cased. We know to output them
|
|
305 |
# because their value is a string, not a key(tuple) or node.
|
|
306 |
#
|
|
307 |
# corner cases to beware of when considering this function:
|
|
308 |
# *) common references are at different heights.
|
|
309 |
# consider two trees:
|
|
310 |
# {'a': LeafNode={'aaa':'foo', 'aab':'bar'}, 'b': LeafNode={'b'}}
|
|
311 |
# {'a': InternalNode={'aa':LeafNode={'aaa':'foo', 'aab':'bar'},
|
|
312 |
# 'ab':LeafNode={'ab':'bar'}}
|
|
313 |
# 'b': LeafNode={'b'}}
|
|
314 |
# the node with aaa/aab will only be encountered in the second tree
|
|
315 |
# after reading the 'a' subtree, but it is encountered in the first
|
|
316 |
# tree immediately. Variations on this may have read internal nodes
|
|
317 |
# like this. we want to cut the entire pending subtree when we
|
|
318 |
# realise we have a common node. For this we use a list of keys -
|
|
319 |
# the path to a node - and check the entire path is clean as we
|
|
320 |
# process each item.
|
|
321 |
if self._node_key(self._root_node) == self._node_key(basis._root_node): |
|
322 |
return
|
|
323 |
self._ensure_root() |
|
324 |
basis._ensure_root() |
|
325 |
excluded_keys = set() |
|
326 |
self_node = self._root_node |
|
327 |
basis_node = basis._root_node |
|
328 |
# A heap, each element is prefix, node(tuple/NodeObject/string),
|
|
329 |
# key_path (a list of tuples, tail-sharing down the tree.)
|
|
330 |
self_pending = [] |
|
331 |
basis_pending = [] |
|
332 |
def process_node(node, path, a_map, pending): |
|
333 |
# take a node and expand it
|
|
334 |
node = a_map._get_node(node) |
|
335 |
if type(node) == LeafNode: |
|
336 |
path = (node._key, path) |
|
337 |
for key, value in node._items.items(): |
|
338 |
# For a LeafNode, the key is a serialized_key, rather than
|
|
339 |
# a search_key, but the heap is using search_keys
|
|
340 |
search_key = node._search_key_func(key) |
|
341 |
heapq.heappush(pending, (search_key, key, value, path)) |
|
342 |
else: |
|
343 |
# type(node) == InternalNode
|
|
344 |
path = (node._key, path) |
|
345 |
for prefix, child in node._items.items(): |
|
346 |
heapq.heappush(pending, (prefix, None, child, path)) |
|
347 |
def process_common_internal_nodes(self_node, basis_node): |
|
348 |
self_items = set(self_node._items.items()) |
|
349 |
basis_items = set(basis_node._items.items()) |
|
350 |
path = (self_node._key, None) |
|
351 |
for prefix, child in self_items - basis_items: |
|
352 |
heapq.heappush(self_pending, (prefix, None, child, path)) |
|
353 |
path = (basis_node._key, None) |
|
354 |
for prefix, child in basis_items - self_items: |
|
355 |
heapq.heappush(basis_pending, (prefix, None, child, path)) |
|
356 |
def process_common_leaf_nodes(self_node, basis_node): |
|
357 |
self_items = set(self_node._items.items()) |
|
358 |
basis_items = set(basis_node._items.items()) |
|
359 |
path = (self_node._key, None) |
|
360 |
for key, value in self_items - basis_items: |
|
361 |
prefix = self._search_key_func(key) |
|
362 |
heapq.heappush(self_pending, (prefix, key, value, path)) |
|
363 |
path = (basis_node._key, None) |
|
364 |
for key, value in basis_items - self_items: |
|
365 |
prefix = basis._search_key_func(key) |
|
366 |
heapq.heappush(basis_pending, (prefix, key, value, path)) |
|
367 |
def process_common_prefix_nodes(self_node, self_path, |
|
368 |
basis_node, basis_path): |
|
369 |
# Would it be more efficient if we could request both at the same
|
|
370 |
# time?
|
|
371 |
self_node = self._get_node(self_node) |
|
372 |
basis_node = basis._get_node(basis_node) |
|
373 |
if (type(self_node) == InternalNode |
|
374 |
and type(basis_node) == InternalNode): |
|
375 |
# Matching internal nodes
|
|
376 |
process_common_internal_nodes(self_node, basis_node) |
|
377 |
elif (type(self_node) == LeafNode |
|
378 |
and type(basis_node) == LeafNode): |
|
379 |
process_common_leaf_nodes(self_node, basis_node) |
|
380 |
else: |
|
381 |
process_node(self_node, self_path, self, self_pending) |
|
382 |
process_node(basis_node, basis_path, basis, basis_pending) |
|
383 |
process_common_prefix_nodes(self_node, None, basis_node, None) |
|
384 |
self_seen = set() |
|
385 |
basis_seen = set() |
|
386 |
excluded_keys = set() |
|
387 |
def check_excluded(key_path): |
|
388 |
# Note that this is N^2, it depends on us trimming trees
|
|
389 |
# aggressively to not become slow.
|
|
390 |
# A better implementation would probably have a reverse map
|
|
391 |
# back to the children of a node, and jump straight to it when
|
|
392 |
# a common node is detected, the proceed to remove the already
|
|
393 |
# pending children. bzrlib.graph has a searcher module with a
|
|
394 |
# similar problem.
|
|
395 |
while key_path is not None: |
|
396 |
key, key_path = key_path |
|
397 |
if key in excluded_keys: |
|
398 |
return True |
|
399 |
return False |
|
400 |
||
401 |
loop_counter = 0 |
|
402 |
while self_pending or basis_pending: |
|
403 |
loop_counter += 1 |
|
404 |
if not self_pending: |
|
405 |
# self is exhausted: output remainder of basis
|
|
406 |
for prefix, key, node, path in basis_pending: |
|
407 |
if check_excluded(path): |
|
408 |
continue
|
|
409 |
node = basis._get_node(node) |
|
410 |
if key is not None: |
|
411 |
# a value
|
|
412 |
yield (key, node, None) |
|
413 |
else: |
|
414 |
# subtree - fastpath the entire thing.
|
|
415 |
for key, value in node.iteritems(basis._store): |
|
416 |
yield (key, value, None) |
|
417 |
return
|
|
418 |
elif not basis_pending: |
|
419 |
# basis is exhausted: output remainder of self.
|
|
420 |
for prefix, key, node, path in self_pending: |
|
421 |
if check_excluded(path): |
|
422 |
continue
|
|
423 |
node = self._get_node(node) |
|
424 |
if key is not None: |
|
425 |
# a value
|
|
426 |
yield (key, None, node) |
|
427 |
else: |
|
428 |
# subtree - fastpath the entire thing.
|
|
429 |
for key, value in node.iteritems(self._store): |
|
430 |
yield (key, None, value) |
|
431 |
return
|
|
432 |
else: |
|
433 |
# XXX: future optimisation - yield the smaller items
|
|
434 |
# immediately rather than pushing everything on/off the
|
|
435 |
# heaps. Applies to both internal nodes and leafnodes.
|
|
436 |
if self_pending[0][0] < basis_pending[0][0]: |
|
437 |
# expand self
|
|
438 |
prefix, key, node, path = heapq.heappop(self_pending) |
|
439 |
if check_excluded(path): |
|
440 |
continue
|
|
441 |
if key is not None: |
|
442 |
# a value
|
|
443 |
yield (key, None, node) |
|
444 |
else: |
|
445 |
process_node(node, path, self, self_pending) |
|
446 |
continue
|
|
447 |
elif self_pending[0][0] > basis_pending[0][0]: |
|
448 |
# expand basis
|
|
449 |
prefix, key, node, path = heapq.heappop(basis_pending) |
|
450 |
if check_excluded(path): |
|
451 |
continue
|
|
452 |
if key is not None: |
|
453 |
# a value
|
|
454 |
yield (key, node, None) |
|
455 |
else: |
|
456 |
process_node(node, path, basis, basis_pending) |
|
457 |
continue
|
|
458 |
else: |
|
459 |
# common prefix: possibly expand both
|
|
460 |
if self_pending[0][1] is None: |
|
461 |
# process next self
|
|
462 |
read_self = True |
|
463 |
else: |
|
464 |
read_self = False |
|
465 |
if basis_pending[0][1] is None: |
|
466 |
# process next basis
|
|
467 |
read_basis = True |
|
468 |
else: |
|
469 |
read_basis = False |
|
470 |
if not read_self and not read_basis: |
|
471 |
# compare a common value
|
|
472 |
self_details = heapq.heappop(self_pending) |
|
473 |
basis_details = heapq.heappop(basis_pending) |
|
474 |
if self_details[2] != basis_details[2]: |
|
475 |
yield (self_details[1], |
|
476 |
basis_details[2], self_details[2]) |
|
477 |
continue
|
|
478 |
# At least one side wasn't a simple value
|
|
479 |
if (self._node_key(self_pending[0][2]) == |
|
480 |
self._node_key(basis_pending[0][2])): |
|
481 |
# Identical pointers, skip (and don't bother adding to
|
|
482 |
# excluded, it won't turn up again.
|
|
483 |
heapq.heappop(self_pending) |
|
484 |
heapq.heappop(basis_pending) |
|
485 |
continue
|
|
486 |
# Now we need to expand this node before we can continue
|
|
487 |
if read_self and read_basis: |
|
488 |
# Both sides start with the same prefix, so process
|
|
489 |
# them in parallel
|
|
490 |
self_prefix, _, self_node, self_path = heapq.heappop( |
|
491 |
self_pending) |
|
492 |
basis_prefix, _, basis_node, basis_path = heapq.heappop( |
|
493 |
basis_pending) |
|
494 |
if self_prefix != basis_prefix: |
|
495 |
raise AssertionError( |
|
496 |
'%r != %r' % (self_prefix, basis_prefix)) |
|
497 |
process_common_prefix_nodes( |
|
498 |
self_node, self_path, |
|
499 |
basis_node, basis_path) |
|
500 |
continue
|
|
501 |
if read_self: |
|
502 |
prefix, key, node, path = heapq.heappop(self_pending) |
|
503 |
if check_excluded(path): |
|
504 |
continue
|
|
505 |
process_node(node, path, self, self_pending) |
|
506 |
if read_basis: |
|
507 |
prefix, key, node, path = heapq.heappop(basis_pending) |
|
508 |
if check_excluded(path): |
|
509 |
continue
|
|
510 |
process_node(node, path, basis, basis_pending) |
|
511 |
# print loop_counter
|
|
512 |
||
513 |
def iteritems(self, key_filter=None): |
|
514 |
"""Iterate over the entire CHKMap's contents."""
|
|
515 |
self._ensure_root() |
|
4679.9.10
by John Arbash Meinel
Change the testing layer so that CHKMap is tested using tuples. |
516 |
if key_filter is not None: |
517 |
as_st = StaticTuple.from_sequence |
|
518 |
key_filter = [as_st(key) for key in key_filter] |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
519 |
return self._root_node.iteritems(self._store, key_filter=key_filter) |
520 |
||
521 |
def key(self): |
|
522 |
"""Return the key for this map."""
|
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
523 |
if type(self._root_node) is StaticTuple: |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
524 |
return self._root_node |
525 |
else: |
|
526 |
return self._root_node._key |
|
527 |
||
528 |
def __len__(self): |
|
529 |
self._ensure_root() |
|
530 |
return len(self._root_node) |
|
531 |
||
532 |
def map(self, key, value): |
|
4526.9.5
by Robert Collins
Require that added ids in inventory deltas be new. |
533 |
"""Map a key tuple to value.
|
534 |
|
|
535 |
:param key: A key to map.
|
|
536 |
:param value: The value to assign to key.
|
|
537 |
"""
|
|
4679.9.9
by John Arbash Meinel
Create a Barrier at the CHKMap interface. |
538 |
key = StaticTuple.from_sequence(key) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
539 |
# Need a root object.
|
540 |
self._ensure_root() |
|
541 |
prefix, node_details = self._root_node.map(self._store, key, value) |
|
542 |
if len(node_details) == 1: |
|
543 |
self._root_node = node_details[0][1] |
|
544 |
else: |
|
545 |
self._root_node = InternalNode(prefix, |
|
546 |
search_key_func=self._search_key_func) |
|
547 |
self._root_node.set_maximum_size(node_details[0][1].maximum_size) |
|
548 |
self._root_node._key_width = node_details[0][1]._key_width |
|
549 |
for split, node in node_details: |
|
550 |
self._root_node.add_node(split, node) |
|
551 |
||
552 |
def _node_key(self, node): |
|
3735.19.1
by Ian Clatworthy
CHKMap cleanups |
553 |
"""Get the key for a node whether it's a tuple or node."""
|
4679.9.9
by John Arbash Meinel
Create a Barrier at the CHKMap interface. |
554 |
if type(node) is tuple: |
555 |
node = StaticTuple.from_sequence(node) |
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
556 |
if type(node) is StaticTuple: |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
557 |
return node |
558 |
else: |
|
559 |
return node._key |
|
560 |
||
3735.2.122
by Ian Clatworthy
don't check_remap on every unmap call in CHKMap.apply_delta() |
561 |
def unmap(self, key, check_remap=True): |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
562 |
"""remove key from the map."""
|
4679.9.9
by John Arbash Meinel
Create a Barrier at the CHKMap interface. |
563 |
key = StaticTuple.from_sequence(key) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
564 |
self._ensure_root() |
565 |
if type(self._root_node) is InternalNode: |
|
3735.2.122
by Ian Clatworthy
don't check_remap on every unmap call in CHKMap.apply_delta() |
566 |
unmapped = self._root_node.unmap(self._store, key, |
567 |
check_remap=check_remap) |
|
568 |
else: |
|
569 |
unmapped = self._root_node.unmap(self._store, key) |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
570 |
self._root_node = unmapped |
571 |
||
3735.2.122
by Ian Clatworthy
don't check_remap on every unmap call in CHKMap.apply_delta() |
572 |
def _check_remap(self): |
573 |
"""Check if nodes can be collapsed."""
|
|
574 |
self._ensure_root() |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
575 |
if type(self._root_node) is InternalNode: |
3735.2.122
by Ian Clatworthy
don't check_remap on every unmap call in CHKMap.apply_delta() |
576 |
self._root_node._check_remap(self._store) |
577 |
||
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
578 |
def _save(self): |
579 |
"""Save the map completely.
|
|
580 |
||
581 |
:return: The key of the root node.
|
|
582 |
"""
|
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
583 |
if type(self._root_node) is StaticTuple: |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
584 |
# Already saved.
|
585 |
return self._root_node |
|
586 |
keys = list(self._root_node.serialise(self._store)) |
|
587 |
return keys[-1] |
|
588 |
||
589 |
||
590 |
class Node(object): |
|
591 |
"""Base class defining the protocol for CHK Map nodes.
|
|
592 |
||
593 |
:ivar _raw_size: The total size of the serialized key:value data, before
|
|
594 |
adding the header bytes, and without prefix compression.
|
|
595 |
"""
|
|
596 |
||
4759.1.2
by John Arbash Meinel
Change CHKMap to use __slots__ |
597 |
__slots__ = ('_key', '_len', '_maximum_size', '_key_width', |
598 |
'_raw_size', '_items', '_search_prefix', '_search_key_func' |
|
599 |
)
|
|
600 |
||
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
601 |
def __init__(self, key_width=1): |
602 |
"""Create a node.
|
|
603 |
||
604 |
:param key_width: The width of keys for this node.
|
|
605 |
"""
|
|
606 |
self._key = None |
|
607 |
# Current number of elements
|
|
608 |
self._len = 0 |
|
609 |
self._maximum_size = 0 |
|
3735.19.1
by Ian Clatworthy
CHKMap cleanups |
610 |
self._key_width = key_width |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
611 |
# current size in bytes
|
612 |
self._raw_size = 0 |
|
613 |
# The pointers/values this node has - meaning defined by child classes.
|
|
614 |
self._items = {} |
|
615 |
# The common search prefix
|
|
616 |
self._search_prefix = None |
|
617 |
||
618 |
def __repr__(self): |
|
619 |
items_str = str(sorted(self._items)) |
|
620 |
if len(items_str) > 20: |
|
3735.2.154
by Ian Clatworthy
fix chk_map Node %r formatting |
621 |
items_str = items_str[:16] + '...]' |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
622 |
return '%s(key:%s len:%s size:%s max:%s prefix:%s items:%s)' % ( |
623 |
self.__class__.__name__, self._key, self._len, self._raw_size, |
|
624 |
self._maximum_size, self._search_prefix, items_str) |
|
625 |
||
626 |
def key(self): |
|
627 |
return self._key |
|
628 |
||
629 |
def __len__(self): |
|
630 |
return self._len |
|
631 |
||
632 |
@property
|
|
633 |
def maximum_size(self): |
|
634 |
"""What is the upper limit for adding references to a node."""
|
|
635 |
return self._maximum_size |
|
636 |
||
637 |
def set_maximum_size(self, new_size): |
|
638 |
"""Set the size threshold for nodes.
|
|
639 |
||
640 |
:param new_size: The size at which no data is added to a node. 0 for
|
|
641 |
unlimited.
|
|
642 |
"""
|
|
643 |
self._maximum_size = new_size |
|
644 |
||
645 |
@classmethod
|
|
646 |
def common_prefix(cls, prefix, key): |
|
647 |
"""Given 2 strings, return the longest prefix common to both.
|
|
648 |
||
649 |
:param prefix: This has been the common prefix for other keys, so it is
|
|
650 |
more likely to be the common prefix in this case as well.
|
|
651 |
:param key: Another string to compare to
|
|
652 |
"""
|
|
653 |
if key.startswith(prefix): |
|
654 |
return prefix |
|
4358.1.1
by Jelmer Vernooij
Support empty keys when looking for common prefixes in CHKMap. |
655 |
pos = -1 |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
656 |
# Is there a better way to do this?
|
657 |
for pos, (left, right) in enumerate(zip(prefix, key)): |
|
658 |
if left != right: |
|
659 |
pos -= 1 |
|
660 |
break
|
|
661 |
common = prefix[:pos+1] |
|
662 |
return common |
|
663 |
||
664 |
@classmethod
|
|
665 |
def common_prefix_for_keys(cls, keys): |
|
666 |
"""Given a list of keys, find their common prefix.
|
|
667 |
||
668 |
:param keys: An iterable of strings.
|
|
669 |
:return: The longest common prefix of all keys.
|
|
670 |
"""
|
|
671 |
common_prefix = None |
|
672 |
for key in keys: |
|
673 |
if common_prefix is None: |
|
674 |
common_prefix = key |
|
675 |
continue
|
|
676 |
common_prefix = cls.common_prefix(common_prefix, key) |
|
677 |
if not common_prefix: |
|
678 |
# if common_prefix is the empty string, then we know it won't
|
|
679 |
# change further
|
|
680 |
return '' |
|
681 |
return common_prefix |
|
682 |
||
683 |
||
684 |
# Singleton indicating we have not computed _search_prefix yet
|
|
685 |
_unknown = object() |
|
686 |
||
687 |
class LeafNode(Node): |
|
688 |
"""A node containing actual key:value pairs.
|
|
689 |
||
690 |
:ivar _items: A dict of key->value items. The key is in tuple form.
|
|
691 |
:ivar _size: The number of bytes that would be used by serializing all of
|
|
692 |
the key/value pairs.
|
|
693 |
"""
|
|
694 |
||
5169.3.1
by Martin
Make LeafNode._serialise_key a static method on the class rather than the instance |
695 |
__slots__ = ('_common_serialised_prefix',) |
4759.1.2
by John Arbash Meinel
Change CHKMap to use __slots__ |
696 |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
697 |
def __init__(self, search_key_func=None): |
698 |
Node.__init__(self) |
|
699 |
# All of the keys in this leaf node share this common prefix
|
|
700 |
self._common_serialised_prefix = None |
|
701 |
if search_key_func is None: |
|
702 |
self._search_key_func = _search_key_plain |
|
703 |
else: |
|
704 |
self._search_key_func = search_key_func |
|
705 |
||
706 |
def __repr__(self): |
|
3735.2.154
by Ian Clatworthy
fix chk_map Node %r formatting |
707 |
items_str = str(sorted(self._items)) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
708 |
if len(items_str) > 20: |
3735.2.154
by Ian Clatworthy
fix chk_map Node %r formatting |
709 |
items_str = items_str[:16] + '...]' |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
710 |
return \
|
711 |
'%s(key:%s len:%s size:%s max:%s prefix:%s keywidth:%s items:%s)' \ |
|
712 |
% (self.__class__.__name__, self._key, self._len, self._raw_size, |
|
713 |
self._maximum_size, self._search_prefix, self._key_width, items_str) |
|
714 |
||
715 |
def _current_size(self): |
|
716 |
"""Answer the current serialised size of this node.
|
|
717 |
||
718 |
This differs from self._raw_size in that it includes the bytes used for
|
|
719 |
the header.
|
|
720 |
"""
|
|
721 |
if self._common_serialised_prefix is None: |
|
722 |
bytes_for_items = 0 |
|
723 |
prefix_len = 0 |
|
724 |
else: |
|
725 |
# We will store a single string with the common prefix
|
|
726 |
# And then that common prefix will not be stored in any of the
|
|
727 |
# entry lines
|
|
728 |
prefix_len = len(self._common_serialised_prefix) |
|
729 |
bytes_for_items = (self._raw_size - (prefix_len * self._len)) |
|
730 |
return (9 # 'chkleaf:\n' |
|
731 |
+ len(str(self._maximum_size)) + 1 |
|
732 |
+ len(str(self._key_width)) + 1 |
|
733 |
+ len(str(self._len)) + 1 |
|
734 |
+ prefix_len + 1 |
|
735 |
+ bytes_for_items) |
|
736 |
||
737 |
@classmethod
|
|
738 |
def deserialise(klass, bytes, key, search_key_func=None): |
|
739 |
"""Deserialise bytes, with key key, into a LeafNode.
|
|
740 |
||
741 |
:param bytes: The bytes of the node.
|
|
742 |
:param key: The key that the serialised node has.
|
|
743 |
"""
|
|
4668.3.1
by John Arbash Meinel
Fix bug #471193, allow tuples into the CHK code. |
744 |
key = static_tuple.expect_static_tuple(key) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
745 |
return _deserialise_leaf_node(bytes, key, |
746 |
search_key_func=search_key_func) |
|
747 |
||
748 |
def iteritems(self, store, key_filter=None): |
|
749 |
"""Iterate over items in the node.
|
|
750 |
||
751 |
:param key_filter: A filter to apply to the node. It should be a
|
|
752 |
list/set/dict or similar repeatedly iterable container.
|
|
753 |
"""
|
|
754 |
if key_filter is not None: |
|
755 |
# Adjust the filter - short elements go to a prefix filter. All
|
|
756 |
# other items are looked up directly.
|
|
757 |
# XXX: perhaps defaultdict? Profiling<rinse and repeat>
|
|
758 |
filters = {} |
|
759 |
for key in key_filter: |
|
760 |
if len(key) == self._key_width: |
|
761 |
# This filter is meant to match exactly one key, yield it
|
|
762 |
# if we have it.
|
|
763 |
try: |
|
764 |
yield key, self._items[key] |
|
765 |
except KeyError: |
|
766 |
# This key is not present in this map, continue
|
|
767 |
pass
|
|
768 |
else: |
|
769 |
# Short items, we need to match based on a prefix
|
|
770 |
length_filter = filters.setdefault(len(key), set()) |
|
771 |
length_filter.add(key) |
|
772 |
if filters: |
|
773 |
filters = filters.items() |
|
774 |
for item in self._items.iteritems(): |
|
775 |
for length, length_filter in filters: |
|
776 |
if item[0][:length] in length_filter: |
|
777 |
yield item |
|
778 |
break
|
|
779 |
else: |
|
780 |
for item in self._items.iteritems(): |
|
781 |
yield item |
|
782 |
||
783 |
def _key_value_len(self, key, value): |
|
784 |
# TODO: Should probably be done without actually joining the key, but
|
|
785 |
# then that can be done via the C extension
|
|
786 |
return (len(self._serialise_key(key)) + 1 |
|
787 |
+ len(str(value.count('\n'))) + 1 |
|
788 |
+ len(value) + 1) |
|
789 |
||
790 |
def _search_key(self, key): |
|
791 |
return self._search_key_func(key) |
|
792 |
||
793 |
def _map_no_split(self, key, value): |
|
794 |
"""Map a key to a value.
|
|
795 |
||
796 |
This assumes either the key does not already exist, or you have already
|
|
797 |
removed its size and length from self.
|
|
798 |
||
799 |
:return: True if adding this node should cause us to split.
|
|
800 |
"""
|
|
801 |
self._items[key] = value |
|
802 |
self._raw_size += self._key_value_len(key, value) |
|
803 |
self._len += 1 |
|
804 |
serialised_key = self._serialise_key(key) |
|
805 |
if self._common_serialised_prefix is None: |
|
806 |
self._common_serialised_prefix = serialised_key |
|
807 |
else: |
|
808 |
self._common_serialised_prefix = self.common_prefix( |
|
809 |
self._common_serialised_prefix, serialised_key) |
|
810 |
search_key = self._search_key(key) |
|
811 |
if self._search_prefix is _unknown: |
|
812 |
self._compute_search_prefix() |
|
813 |
if self._search_prefix is None: |
|
814 |
self._search_prefix = search_key |
|
815 |
else: |
|
816 |
self._search_prefix = self.common_prefix( |
|
817 |
self._search_prefix, search_key) |
|
818 |
if (self._len > 1 |
|
819 |
and self._maximum_size |
|
820 |
and self._current_size() > self._maximum_size): |
|
821 |
# Check to see if all of the search_keys for this node are
|
|
822 |
# identical. We allow the node to grow under that circumstance
|
|
823 |
# (we could track this as common state, but it is infrequent)
|
|
824 |
if (search_key != self._search_prefix |
|
825 |
or not self._are_search_keys_identical()): |
|
826 |
return True |
|
827 |
return False |
|
828 |
||
829 |
def _split(self, store): |
|
830 |
"""We have overflowed.
|
|
831 |
||
832 |
Split this node into multiple LeafNodes, return it up the stack so that
|
|
833 |
the next layer creates a new InternalNode and references the new nodes.
|
|
834 |
||
835 |
:return: (common_serialised_prefix, [(node_serialised_prefix, node)])
|
|
836 |
"""
|
|
837 |
if self._search_prefix is _unknown: |
|
838 |
raise AssertionError('Search prefix must be known') |
|
839 |
common_prefix = self._search_prefix |
|
840 |
split_at = len(common_prefix) + 1 |
|
841 |
result = {} |
|
842 |
for key, value in self._items.iteritems(): |
|
843 |
search_key = self._search_key(key) |
|
844 |
prefix = search_key[:split_at] |
|
845 |
# TODO: Generally only 1 key can be exactly the right length,
|
|
846 |
# which means we can only have 1 key in the node pointed
|
|
847 |
# at by the 'prefix\0' key. We might want to consider
|
|
848 |
# folding it into the containing InternalNode rather than
|
|
849 |
# having a fixed length-1 node.
|
|
850 |
# Note this is probably not true for hash keys, as they
|
|
851 |
# may get a '\00' node anywhere, but won't have keys of
|
|
852 |
# different lengths.
|
|
853 |
if len(prefix) < split_at: |
|
854 |
prefix += '\x00'*(split_at - len(prefix)) |
|
855 |
if prefix not in result: |
|
856 |
node = LeafNode(search_key_func=self._search_key_func) |
|
857 |
node.set_maximum_size(self._maximum_size) |
|
858 |
node._key_width = self._key_width |
|
859 |
result[prefix] = node |
|
860 |
else: |
|
861 |
node = result[prefix] |
|
4413.5.4
by John Arbash Meinel
Change CHKMap.from_dict to create a LeafNode and split it. |
862 |
sub_prefix, node_details = node.map(store, key, value) |
863 |
if len(node_details) > 1: |
|
864 |
if prefix != sub_prefix: |
|
865 |
# This node has been split and is now found via a different
|
|
866 |
# path
|
|
867 |
result.pop(prefix) |
|
868 |
new_node = InternalNode(sub_prefix, |
|
869 |
search_key_func=self._search_key_func) |
|
870 |
new_node.set_maximum_size(self._maximum_size) |
|
871 |
new_node._key_width = self._key_width |
|
872 |
for split, node in node_details: |
|
873 |
new_node.add_node(split, node) |
|
874 |
result[prefix] = new_node |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
875 |
return common_prefix, result.items() |
876 |
||
877 |
def map(self, store, key, value): |
|
878 |
"""Map key to value."""
|
|
879 |
if key in self._items: |
|
880 |
self._raw_size -= self._key_value_len(key, self._items[key]) |
|
881 |
self._len -= 1 |
|
882 |
self._key = None |
|
883 |
if self._map_no_split(key, value): |
|
884 |
return self._split(store) |
|
885 |
else: |
|
886 |
if self._search_prefix is _unknown: |
|
887 |
raise AssertionError('%r must be known' % self._search_prefix) |
|
888 |
return self._search_prefix, [("", self)] |
|
889 |
||
5169.3.1
by Martin
Make LeafNode._serialise_key a static method on the class rather than the instance |
890 |
_serialise_key = '\x00'.join |
891 |
||
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
892 |
def serialise(self, store): |
893 |
"""Serialise the LeafNode to store.
|
|
894 |
||
895 |
:param store: A VersionedFiles honouring the CHK extensions.
|
|
896 |
:return: An iterable of the keys inserted by this operation.
|
|
897 |
"""
|
|
898 |
lines = ["chkleaf:\n"] |
|
899 |
lines.append("%d\n" % self._maximum_size) |
|
900 |
lines.append("%d\n" % self._key_width) |
|
901 |
lines.append("%d\n" % self._len) |
|
902 |
if self._common_serialised_prefix is None: |
|
903 |
lines.append('\n') |
|
904 |
if len(self._items) != 0: |
|
905 |
raise AssertionError('If _common_serialised_prefix is None' |
|
906 |
' we should have no items') |
|
907 |
else: |
|
908 |
lines.append('%s\n' % (self._common_serialised_prefix,)) |
|
909 |
prefix_len = len(self._common_serialised_prefix) |
|
910 |
for key, value in sorted(self._items.items()): |
|
911 |
# Always add a final newline
|
|
912 |
value_lines = osutils.chunks_to_lines([value + '\n']) |
|
913 |
serialized = "%s\x00%s\n" % (self._serialise_key(key), |
|
914 |
len(value_lines)) |
|
915 |
if not serialized.startswith(self._common_serialised_prefix): |
|
916 |
raise AssertionError('We thought the common prefix was %r' |
|
917 |
' but entry %r does not have it in common' |
|
918 |
% (self._common_serialised_prefix, serialized)) |
|
919 |
lines.append(serialized[prefix_len:]) |
|
920 |
lines.extend(value_lines) |
|
921 |
sha1, _, _ = store.add_lines((None,), (), lines) |
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
922 |
self._key = StaticTuple("sha1:" + sha1,).intern() |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
923 |
bytes = ''.join(lines) |
924 |
if len(bytes) != self._current_size(): |
|
925 |
raise AssertionError('Invalid _current_size') |
|
4797.7.1
by Robert Collins
Introduce a threading.local to isolate the chk_map page cache from other threads. |
926 |
_get_cache().add(self._key, bytes) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
927 |
return [self._key] |
928 |
||
929 |
def refs(self): |
|
930 |
"""Return the references to other CHK's held by this node."""
|
|
931 |
return [] |
|
932 |
||
933 |
def _compute_search_prefix(self): |
|
934 |
"""Determine the common search prefix for all keys in this node.
|
|
935 |
||
936 |
:return: A bytestring of the longest search key prefix that is
|
|
937 |
unique within this node.
|
|
938 |
"""
|
|
939 |
search_keys = [self._search_key_func(key) for key in self._items] |
|
940 |
self._search_prefix = self.common_prefix_for_keys(search_keys) |
|
941 |
return self._search_prefix |
|
942 |
||
943 |
def _are_search_keys_identical(self): |
|
944 |
"""Check to see if the search keys for all entries are the same.
|
|
945 |
||
946 |
When using a hash as the search_key it is possible for non-identical
|
|
947 |
keys to collide. If that happens enough, we may try overflow a
|
|
948 |
LeafNode, but as all are collisions, we must not split.
|
|
949 |
"""
|
|
950 |
common_search_key = None |
|
951 |
for key in self._items: |
|
952 |
search_key = self._search_key(key) |
|
953 |
if common_search_key is None: |
|
954 |
common_search_key = search_key |
|
955 |
elif search_key != common_search_key: |
|
956 |
return False |
|
957 |
return True |
|
958 |
||
959 |
def _compute_serialised_prefix(self): |
|
960 |
"""Determine the common prefix for serialised keys in this node.
|
|
961 |
||
962 |
:return: A bytestring of the longest serialised key prefix that is
|
|
963 |
unique within this node.
|
|
964 |
"""
|
|
965 |
serialised_keys = [self._serialise_key(key) for key in self._items] |
|
966 |
self._common_serialised_prefix = self.common_prefix_for_keys( |
|
967 |
serialised_keys) |
|
3735.19.1
by Ian Clatworthy
CHKMap cleanups |
968 |
return self._common_serialised_prefix |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
969 |
|
970 |
def unmap(self, store, key): |
|
971 |
"""Unmap key from the node."""
|
|
972 |
try: |
|
973 |
self._raw_size -= self._key_value_len(key, self._items[key]) |
|
974 |
except KeyError: |
|
975 |
trace.mutter("key %s not found in %r", key, self._items) |
|
976 |
raise
|
|
977 |
self._len -= 1 |
|
978 |
del self._items[key] |
|
979 |
self._key = None |
|
980 |
# Recompute from scratch
|
|
981 |
self._compute_search_prefix() |
|
982 |
self._compute_serialised_prefix() |
|
983 |
return self |
|
984 |
||
985 |
||
986 |
class InternalNode(Node): |
|
987 |
"""A node that contains references to other nodes.
|
|
988 |
||
989 |
An InternalNode is responsible for mapping search key prefixes to child
|
|
990 |
nodes.
|
|
991 |
||
992 |
:ivar _items: serialised_key => node dictionary. node may be a tuple,
|
|
993 |
LeafNode or InternalNode.
|
|
994 |
"""
|
|
995 |
||
4759.1.2
by John Arbash Meinel
Change CHKMap to use __slots__ |
996 |
__slots__ = ('_node_width',) |
997 |
||
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
998 |
def __init__(self, prefix='', search_key_func=None): |
999 |
Node.__init__(self) |
|
1000 |
# The size of an internalnode with default values and no children.
|
|
1001 |
# How many octets key prefixes within this node are.
|
|
1002 |
self._node_width = 0 |
|
1003 |
self._search_prefix = prefix |
|
1004 |
if search_key_func is None: |
|
1005 |
self._search_key_func = _search_key_plain |
|
1006 |
else: |
|
1007 |
self._search_key_func = search_key_func |
|
1008 |
||
1009 |
def add_node(self, prefix, node): |
|
1010 |
"""Add a child node with prefix prefix, and node node.
|
|
1011 |
||
1012 |
:param prefix: The search key prefix for node.
|
|
1013 |
:param node: The node being added.
|
|
1014 |
"""
|
|
3735.2.126
by Ian Clatworthy
replace asserts in chk_map.py with AssertionErrors |
1015 |
if self._search_prefix is None: |
1016 |
raise AssertionError("_search_prefix should not be None") |
|
1017 |
if not prefix.startswith(self._search_prefix): |
|
1018 |
raise AssertionError("prefixes mismatch: %s must start with %s" |
|
1019 |
% (prefix,self._search_prefix)) |
|
1020 |
if len(prefix) != len(self._search_prefix) + 1: |
|
1021 |
raise AssertionError("prefix wrong length: len(%s) is not %d" % |
|
1022 |
(prefix, len(self._search_prefix) + 1)) |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1023 |
self._len += len(node) |
1024 |
if not len(self._items): |
|
1025 |
self._node_width = len(prefix) |
|
3735.2.126
by Ian Clatworthy
replace asserts in chk_map.py with AssertionErrors |
1026 |
if self._node_width != len(self._search_prefix) + 1: |
1027 |
raise AssertionError("node width mismatch: %d is not %d" % |
|
1028 |
(self._node_width, len(self._search_prefix) + 1)) |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1029 |
self._items[prefix] = node |
1030 |
self._key = None |
|
1031 |
||
1032 |
def _current_size(self): |
|
1033 |
"""Answer the current serialised size of this node."""
|
|
1034 |
return (self._raw_size + len(str(self._len)) + len(str(self._key_width)) + |
|
1035 |
len(str(self._maximum_size))) |
|
1036 |
||
1037 |
@classmethod
|
|
1038 |
def deserialise(klass, bytes, key, search_key_func=None): |
|
1039 |
"""Deserialise bytes to an InternalNode, with key key.
|
|
1040 |
||
1041 |
:param bytes: The bytes of the node.
|
|
1042 |
:param key: The key that the serialised node has.
|
|
1043 |
:return: An InternalNode instance.
|
|
1044 |
"""
|
|
4668.3.1
by John Arbash Meinel
Fix bug #471193, allow tuples into the CHK code. |
1045 |
key = static_tuple.expect_static_tuple(key) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1046 |
return _deserialise_internal_node(bytes, key, |
1047 |
search_key_func=search_key_func) |
|
1048 |
||
1049 |
def iteritems(self, store, key_filter=None): |
|
1050 |
for node, node_filter in self._iter_nodes(store, key_filter=key_filter): |
|
1051 |
for item in node.iteritems(store, key_filter=node_filter): |
|
1052 |
yield item |
|
1053 |
||
1054 |
def _iter_nodes(self, store, key_filter=None, batch_size=None): |
|
1055 |
"""Iterate over node objects which match key_filter.
|
|
1056 |
||
1057 |
:param store: A store to use for accessing content.
|
|
1058 |
:param key_filter: A key filter to filter nodes. Only nodes that might
|
|
1059 |
contain a key in key_filter will be returned.
|
|
1060 |
:param batch_size: If not None, then we will return the nodes that had
|
|
1061 |
to be read using get_record_stream in batches, rather than reading
|
|
1062 |
them all at once.
|
|
1063 |
:return: An iterable of nodes. This function does not have to be fully
|
|
1064 |
consumed. (There will be no pending I/O when items are being returned.)
|
|
1065 |
"""
|
|
1066 |
# Map from chk key ('sha1:...',) to (prefix, key_filter)
|
|
1067 |
# prefix is the key in self._items to use, key_filter is the key_filter
|
|
1068 |
# entries that would match this node
|
|
1069 |
keys = {} |
|
4413.4.1
by John Arbash Meinel
Add a shortcut for the case when we are searching for a single full-width key. |
1070 |
shortcut = False |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1071 |
if key_filter is None: |
4413.4.1
by John Arbash Meinel
Add a shortcut for the case when we are searching for a single full-width key. |
1072 |
# yielding all nodes, yield whatever we have, and queue up a read
|
1073 |
# for whatever we are missing
|
|
1074 |
shortcut = True |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1075 |
for prefix, node in self._items.iteritems(): |
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
1076 |
if node.__class__ is StaticTuple: |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1077 |
keys[node] = (prefix, None) |
1078 |
else: |
|
1079 |
yield node, None |
|
4413.4.1
by John Arbash Meinel
Add a shortcut for the case when we are searching for a single full-width key. |
1080 |
elif len(key_filter) == 1: |
4413.4.2
by John Arbash Meinel
Rewrite the shortcuts. |
1081 |
# Technically, this path could also be handled by the first check
|
1082 |
# in 'self._node_width' in length_filters. However, we can handle
|
|
1083 |
# this case without spending any time building up the
|
|
1084 |
# prefix_to_keys, etc state.
|
|
1085 |
||
1086 |
# This is a bit ugly, but TIMEIT showed it to be by far the fastest
|
|
1087 |
# 0.626us list(key_filter)[0]
|
|
1088 |
# is a func() for list(), 2 mallocs, and a getitem
|
|
1089 |
# 0.489us [k for k in key_filter][0]
|
|
1090 |
# still has the mallocs, avoids the func() call
|
|
1091 |
# 0.350us iter(key_filter).next()
|
|
1092 |
# has a func() call, and mallocs an iterator
|
|
1093 |
# 0.125us for key in key_filter: pass
|
|
1094 |
# no func() overhead, might malloc an iterator
|
|
1095 |
# 0.105us for key in key_filter: break
|
|
1096 |
# no func() overhead, might malloc an iterator, probably
|
|
1097 |
# avoids checking an 'else' clause as part of the for
|
|
1098 |
for key in key_filter: |
|
1099 |
break
|
|
1100 |
search_prefix = self._search_prefix_filter(key) |
|
1101 |
if len(search_prefix) == self._node_width: |
|
4413.4.1
by John Arbash Meinel
Add a shortcut for the case when we are searching for a single full-width key. |
1102 |
# This item will match exactly, so just do a dict lookup, and
|
1103 |
# see what we can return
|
|
1104 |
shortcut = True |
|
1105 |
try: |
|
4413.4.2
by John Arbash Meinel
Rewrite the shortcuts. |
1106 |
node = self._items[search_prefix] |
4413.4.1
by John Arbash Meinel
Add a shortcut for the case when we are searching for a single full-width key. |
1107 |
except KeyError: |
1108 |
# A given key can only match 1 child node, if it isn't
|
|
1109 |
# there, then we can just return nothing
|
|
1110 |
return
|
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
1111 |
if node.__class__ is StaticTuple: |
4413.4.2
by John Arbash Meinel
Rewrite the shortcuts. |
1112 |
keys[node] = (search_prefix, [key]) |
4413.4.1
by John Arbash Meinel
Add a shortcut for the case when we are searching for a single full-width key. |
1113 |
else: |
4413.4.2
by John Arbash Meinel
Rewrite the shortcuts. |
1114 |
# This is loaded, and the only thing that can match,
|
1115 |
# return
|
|
1116 |
yield node, [key] |
|
1117 |
return
|
|
4413.4.1
by John Arbash Meinel
Add a shortcut for the case when we are searching for a single full-width key. |
1118 |
if not shortcut: |
4413.4.2
by John Arbash Meinel
Rewrite the shortcuts. |
1119 |
# First, convert all keys into a list of search prefixes
|
1120 |
# Aggregate common prefixes, and track the keys they come from
|
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1121 |
prefix_to_keys = {} |
1122 |
length_filters = {} |
|
1123 |
for key in key_filter: |
|
4413.4.2
by John Arbash Meinel
Rewrite the shortcuts. |
1124 |
search_prefix = self._search_prefix_filter(key) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1125 |
length_filter = length_filters.setdefault( |
4413.4.2
by John Arbash Meinel
Rewrite the shortcuts. |
1126 |
len(search_prefix), set()) |
1127 |
length_filter.add(search_prefix) |
|
1128 |
prefix_to_keys.setdefault(search_prefix, []).append(key) |
|
1129 |
||
1130 |
if (self._node_width in length_filters |
|
1131 |
and len(length_filters) == 1): |
|
1132 |
# all of the search prefixes match exactly _node_width. This
|
|
1133 |
# means that everything is an exact match, and we can do a
|
|
1134 |
# lookup into self._items, rather than iterating over the items
|
|
1135 |
# dict.
|
|
1136 |
search_prefixes = length_filters[self._node_width] |
|
1137 |
for search_prefix in search_prefixes: |
|
1138 |
try: |
|
1139 |
node = self._items[search_prefix] |
|
1140 |
except KeyError: |
|
1141 |
# We can ignore this one
|
|
1142 |
continue
|
|
1143 |
node_key_filter = prefix_to_keys[search_prefix] |
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
1144 |
if node.__class__ is StaticTuple: |
4413.4.2
by John Arbash Meinel
Rewrite the shortcuts. |
1145 |
keys[node] = (search_prefix, node_key_filter) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1146 |
else: |
1147 |
yield node, node_key_filter |
|
4413.4.2
by John Arbash Meinel
Rewrite the shortcuts. |
1148 |
else: |
1149 |
# The slow way. We walk every item in self._items, and check to
|
|
1150 |
# see if there are any matches
|
|
1151 |
length_filters = length_filters.items() |
|
1152 |
for prefix, node in self._items.iteritems(): |
|
1153 |
node_key_filter = [] |
|
1154 |
for length, length_filter in length_filters: |
|
1155 |
sub_prefix = prefix[:length] |
|
1156 |
if sub_prefix in length_filter: |
|
1157 |
node_key_filter.extend(prefix_to_keys[sub_prefix]) |
|
1158 |
if node_key_filter: # this key matched something, yield it |
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
1159 |
if node.__class__ is StaticTuple: |
4413.4.2
by John Arbash Meinel
Rewrite the shortcuts. |
1160 |
keys[node] = (prefix, node_key_filter) |
1161 |
else: |
|
1162 |
yield node, node_key_filter |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1163 |
if keys: |
1164 |
# Look in the page cache for some more bytes
|
|
1165 |
found_keys = set() |
|
1166 |
for key in keys: |
|
1167 |
try: |
|
4797.7.1
by Robert Collins
Introduce a threading.local to isolate the chk_map page cache from other threads. |
1168 |
bytes = _get_cache()[key] |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1169 |
except KeyError: |
1170 |
continue
|
|
1171 |
else: |
|
1172 |
node = _deserialise(bytes, key, |
|
1173 |
search_key_func=self._search_key_func) |
|
1174 |
prefix, node_key_filter = keys[key] |
|
1175 |
self._items[prefix] = node |
|
1176 |
found_keys.add(key) |
|
1177 |
yield node, node_key_filter |
|
1178 |
for key in found_keys: |
|
1179 |
del keys[key] |
|
1180 |
if keys: |
|
1181 |
# demand load some pages.
|
|
1182 |
if batch_size is None: |
|
1183 |
# Read all the keys in
|
|
1184 |
batch_size = len(keys) |
|
1185 |
key_order = list(keys) |
|
1186 |
for batch_start in range(0, len(key_order), batch_size): |
|
1187 |
batch = key_order[batch_start:batch_start + batch_size] |
|
1188 |
# We have to fully consume the stream so there is no pending
|
|
1189 |
# I/O, so we buffer the nodes for now.
|
|
1190 |
stream = store.get_record_stream(batch, 'unordered', True) |
|
1191 |
node_and_filters = [] |
|
1192 |
for record in stream: |
|
1193 |
bytes = record.get_bytes_as('fulltext') |
|
1194 |
node = _deserialise(bytes, record.key, |
|
1195 |
search_key_func=self._search_key_func) |
|
1196 |
prefix, node_key_filter = keys[record.key] |
|
1197 |
node_and_filters.append((node, node_key_filter)) |
|
1198 |
self._items[prefix] = node |
|
4797.7.1
by Robert Collins
Introduce a threading.local to isolate the chk_map page cache from other threads. |
1199 |
_get_cache().add(record.key, bytes) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1200 |
for info in node_and_filters: |
1201 |
yield info |
|
1202 |
||
1203 |
def map(self, store, key, value): |
|
1204 |
"""Map key to value."""
|
|
1205 |
if not len(self._items): |
|
3735.2.122
by Ian Clatworthy
don't check_remap on every unmap call in CHKMap.apply_delta() |
1206 |
raise AssertionError("can't map in an empty InternalNode.") |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1207 |
search_key = self._search_key(key) |
3735.2.126
by Ian Clatworthy
replace asserts in chk_map.py with AssertionErrors |
1208 |
if self._node_width != len(self._search_prefix) + 1: |
1209 |
raise AssertionError("node width mismatch: %d is not %d" % |
|
1210 |
(self._node_width, len(self._search_prefix) + 1)) |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1211 |
if not search_key.startswith(self._search_prefix): |
1212 |
# This key doesn't fit in this index, so we need to split at the
|
|
1213 |
# point where it would fit, insert self into that internal node,
|
|
1214 |
# and then map this key into that node.
|
|
1215 |
new_prefix = self.common_prefix(self._search_prefix, |
|
1216 |
search_key) |
|
1217 |
new_parent = InternalNode(new_prefix, |
|
1218 |
search_key_func=self._search_key_func) |
|
1219 |
new_parent.set_maximum_size(self._maximum_size) |
|
1220 |
new_parent._key_width = self._key_width |
|
1221 |
new_parent.add_node(self._search_prefix[:len(new_prefix)+1], |
|
1222 |
self) |
|
1223 |
return new_parent.map(store, key, value) |
|
1224 |
children = [node for node, _ |
|
1225 |
in self._iter_nodes(store, key_filter=[key])] |
|
1226 |
if children: |
|
1227 |
child = children[0] |
|
1228 |
else: |
|
1229 |
# new child needed:
|
|
1230 |
child = self._new_child(search_key, LeafNode) |
|
1231 |
old_len = len(child) |
|
1232 |
if type(child) is LeafNode: |
|
1233 |
old_size = child._current_size() |
|
1234 |
else: |
|
1235 |
old_size = None |
|
1236 |
prefix, node_details = child.map(store, key, value) |
|
1237 |
if len(node_details) == 1: |
|
1238 |
# child may have shrunk, or might be a new node
|
|
1239 |
child = node_details[0][1] |
|
1240 |
self._len = self._len - old_len + len(child) |
|
1241 |
self._items[search_key] = child |
|
1242 |
self._key = None |
|
1243 |
new_node = self |
|
1244 |
if type(child) is LeafNode: |
|
3735.2.123
by Ian Clatworthy
only check for remap if changes are interesting in size |
1245 |
if old_size is None: |
1246 |
# The old node was an InternalNode which means it has now
|
|
1247 |
# collapsed, so we need to check if it will chain to a
|
|
1248 |
# collapse at this level.
|
|
1249 |
trace.mutter("checking remap as InternalNode -> LeafNode") |
|
1250 |
new_node = self._check_remap(store) |
|
1251 |
else: |
|
1252 |
# If the LeafNode has shrunk in size, we may want to run
|
|
1253 |
# a remap check. Checking for a remap is expensive though
|
|
1254 |
# and the frequency of a successful remap is very low.
|
|
1255 |
# Shrinkage by small amounts is common, so we only do the
|
|
1256 |
# remap check if the new_size is low or the shrinkage
|
|
1257 |
# amount is over a configurable limit.
|
|
1258 |
new_size = child._current_size() |
|
1259 |
shrinkage = old_size - new_size |
|
1260 |
if (shrinkage > 0 and new_size < _INTERESTING_NEW_SIZE |
|
1261 |
or shrinkage > _INTERESTING_SHRINKAGE_LIMIT): |
|
1262 |
trace.mutter( |
|
1263 |
"checking remap as size shrunk by %d to be %d", |
|
1264 |
shrinkage, new_size) |
|
1265 |
new_node = self._check_remap(store) |
|
3735.2.126
by Ian Clatworthy
replace asserts in chk_map.py with AssertionErrors |
1266 |
if new_node._search_prefix is None: |
1267 |
raise AssertionError("_search_prefix should not be None") |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1268 |
return new_node._search_prefix, [('', new_node)] |
1269 |
# child has overflown - create a new intermediate node.
|
|
1270 |
# XXX: This is where we might want to try and expand our depth
|
|
1271 |
# to refer to more bytes of every child (which would give us
|
|
1272 |
# multiple pointers to child nodes, but less intermediate nodes)
|
|
1273 |
child = self._new_child(search_key, InternalNode) |
|
1274 |
child._search_prefix = prefix |
|
1275 |
for split, node in node_details: |
|
1276 |
child.add_node(split, node) |
|
1277 |
self._len = self._len - old_len + len(child) |
|
1278 |
self._key = None |
|
1279 |
return self._search_prefix, [("", self)] |
|
1280 |
||
1281 |
def _new_child(self, search_key, klass): |
|
1282 |
"""Create a new child node of type klass."""
|
|
1283 |
child = klass() |
|
1284 |
child.set_maximum_size(self._maximum_size) |
|
1285 |
child._key_width = self._key_width |
|
1286 |
child._search_key_func = self._search_key_func |
|
1287 |
self._items[search_key] = child |
|
1288 |
return child |
|
1289 |
||
1290 |
def serialise(self, store): |
|
1291 |
"""Serialise the node to store.
|
|
1292 |
||
1293 |
:param store: A VersionedFiles honouring the CHK extensions.
|
|
1294 |
:return: An iterable of the keys inserted by this operation.
|
|
1295 |
"""
|
|
1296 |
for node in self._items.itervalues(): |
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
1297 |
if type(node) is StaticTuple: |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1298 |
# Never deserialised.
|
1299 |
continue
|
|
1300 |
if node._key is not None: |
|
1301 |
# Never altered
|
|
1302 |
continue
|
|
1303 |
for key in node.serialise(store): |
|
1304 |
yield key |
|
1305 |
lines = ["chknode:\n"] |
|
1306 |
lines.append("%d\n" % self._maximum_size) |
|
1307 |
lines.append("%d\n" % self._key_width) |
|
1308 |
lines.append("%d\n" % self._len) |
|
3735.2.126
by Ian Clatworthy
replace asserts in chk_map.py with AssertionErrors |
1309 |
if self._search_prefix is None: |
1310 |
raise AssertionError("_search_prefix should not be None") |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1311 |
lines.append('%s\n' % (self._search_prefix,)) |
1312 |
prefix_len = len(self._search_prefix) |
|
1313 |
for prefix, node in sorted(self._items.items()): |
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
1314 |
if type(node) is StaticTuple: |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1315 |
key = node[0] |
1316 |
else: |
|
1317 |
key = node._key[0] |
|
1318 |
serialised = "%s\x00%s\n" % (prefix, key) |
|
3735.2.126
by Ian Clatworthy
replace asserts in chk_map.py with AssertionErrors |
1319 |
if not serialised.startswith(self._search_prefix): |
1320 |
raise AssertionError("prefixes mismatch: %s must start with %s" |
|
1321 |
% (serialised, self._search_prefix)) |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1322 |
lines.append(serialised[prefix_len:]) |
1323 |
sha1, _, _ = store.add_lines((None,), (), lines) |
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
1324 |
self._key = StaticTuple("sha1:" + sha1,).intern() |
4797.7.1
by Robert Collins
Introduce a threading.local to isolate the chk_map page cache from other threads. |
1325 |
_get_cache().add(self._key, ''.join(lines)) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1326 |
yield self._key |
1327 |
||
1328 |
def _search_key(self, key): |
|
1329 |
"""Return the serialised key for key in this node."""
|
|
1330 |
# search keys are fixed width. All will be self._node_width wide, so we
|
|
1331 |
# pad as necessary.
|
|
1332 |
return (self._search_key_func(key) + '\x00'*self._node_width)[:self._node_width] |
|
1333 |
||
1334 |
def _search_prefix_filter(self, key): |
|
1335 |
"""Serialise key for use as a prefix filter in iteritems."""
|
|
1336 |
return self._search_key_func(key)[:self._node_width] |
|
1337 |
||
1338 |
def _split(self, offset): |
|
1339 |
"""Split this node into smaller nodes starting at offset.
|
|
1340 |
||
1341 |
:param offset: The offset to start the new child nodes at.
|
|
1342 |
:return: An iterable of (prefix, node) tuples. prefix is a byte
|
|
1343 |
prefix for reaching node.
|
|
1344 |
"""
|
|
1345 |
if offset >= self._node_width: |
|
1346 |
for node in self._items.values(): |
|
1347 |
for result in node._split(offset): |
|
1348 |
yield result |
|
1349 |
return
|
|
1350 |
for key, node in self._items.items(): |
|
1351 |
pass
|
|
1352 |
||
1353 |
def refs(self): |
|
1354 |
"""Return the references to other CHK's held by this node."""
|
|
1355 |
if self._key is None: |
|
1356 |
raise AssertionError("unserialised nodes have no refs.") |
|
1357 |
refs = [] |
|
1358 |
for value in self._items.itervalues(): |
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
1359 |
if type(value) is StaticTuple: |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1360 |
refs.append(value) |
1361 |
else: |
|
1362 |
refs.append(value.key()) |
|
1363 |
return refs |
|
1364 |
||
1365 |
def _compute_search_prefix(self, extra_key=None): |
|
1366 |
"""Return the unique key prefix for this node.
|
|
1367 |
||
1368 |
:return: A bytestring of the longest search key prefix that is
|
|
1369 |
unique within this node.
|
|
1370 |
"""
|
|
1371 |
self._search_prefix = self.common_prefix_for_keys(self._items) |
|
1372 |
return self._search_prefix |
|
1373 |
||
3735.2.122
by Ian Clatworthy
don't check_remap on every unmap call in CHKMap.apply_delta() |
1374 |
def unmap(self, store, key, check_remap=True): |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1375 |
"""Remove key from this node and it's children."""
|
1376 |
if not len(self._items): |
|
3735.2.126
by Ian Clatworthy
replace asserts in chk_map.py with AssertionErrors |
1377 |
raise AssertionError("can't unmap in an empty InternalNode.") |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1378 |
children = [node for node, _ |
1379 |
in self._iter_nodes(store, key_filter=[key])] |
|
1380 |
if children: |
|
1381 |
child = children[0] |
|
1382 |
else: |
|
1383 |
raise KeyError(key) |
|
1384 |
self._len -= 1 |
|
1385 |
unmapped = child.unmap(store, key) |
|
1386 |
self._key = None |
|
1387 |
search_key = self._search_key(key) |
|
1388 |
if len(unmapped) == 0: |
|
1389 |
# All child nodes are gone, remove the child:
|
|
1390 |
del self._items[search_key] |
|
1391 |
unmapped = None |
|
1392 |
else: |
|
1393 |
# Stash the returned node
|
|
1394 |
self._items[search_key] = unmapped |
|
1395 |
if len(self._items) == 1: |
|
1396 |
# this node is no longer needed:
|
|
1397 |
return self._items.values()[0] |
|
1398 |
if type(unmapped) is InternalNode: |
|
1399 |
return self |
|
3735.2.122
by Ian Clatworthy
don't check_remap on every unmap call in CHKMap.apply_delta() |
1400 |
if check_remap: |
1401 |
return self._check_remap(store) |
|
1402 |
else: |
|
1403 |
return self |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1404 |
|
1405 |
def _check_remap(self, store): |
|
1406 |
"""Check if all keys contained by children fit in a single LeafNode.
|
|
1407 |
||
1408 |
:param store: A store to use for reading more nodes
|
|
1409 |
:return: Either self, or a new LeafNode which should replace self.
|
|
1410 |
"""
|
|
1411 |
# Logic for how we determine when we need to rebuild
|
|
1412 |
# 1) Implicitly unmap() is removing a key which means that the child
|
|
1413 |
# nodes are going to be shrinking by some extent.
|
|
1414 |
# 2) If all children are LeafNodes, it is possible that they could be
|
|
1415 |
# combined into a single LeafNode, which can then completely replace
|
|
1416 |
# this internal node with a single LeafNode
|
|
1417 |
# 3) If *one* child is an InternalNode, we assume it has already done
|
|
1418 |
# all the work to determine that its children cannot collapse, and
|
|
1419 |
# we can then assume that those nodes *plus* the current nodes don't
|
|
1420 |
# have a chance of collapsing either.
|
|
1421 |
# So a very cheap check is to just say if 'unmapped' is an
|
|
1422 |
# InternalNode, we don't have to check further.
|
|
1423 |
||
1424 |
# TODO: Another alternative is to check the total size of all known
|
|
1425 |
# LeafNodes. If there is some formula we can use to determine the
|
|
1426 |
# final size without actually having to read in any more
|
|
1427 |
# children, it would be nice to have. However, we have to be
|
|
1428 |
# careful with stuff like nodes that pull out the common prefix
|
|
1429 |
# of each key, as adding a new key can change the common prefix
|
|
1430 |
# and cause size changes greater than the length of one key.
|
|
1431 |
# So for now, we just add everything to a new Leaf until it
|
|
1432 |
# splits, as we know that will give the right answer
|
|
1433 |
new_leaf = LeafNode(search_key_func=self._search_key_func) |
|
1434 |
new_leaf.set_maximum_size(self._maximum_size) |
|
1435 |
new_leaf._key_width = self._key_width |
|
1436 |
# A batch_size of 16 was chosen because:
|
|
1437 |
# a) In testing, a 4k page held 14 times. So if we have more than 16
|
|
1438 |
# leaf nodes we are unlikely to hold them in a single new leaf
|
|
1439 |
# node. This still allows for 1 round trip
|
|
1440 |
# b) With 16-way fan out, we can still do a single round trip
|
|
1441 |
# c) With 255-way fan out, we don't want to read all 255 and destroy
|
|
1442 |
# the page cache, just to determine that we really don't need it.
|
|
1443 |
for node, _ in self._iter_nodes(store, batch_size=16): |
|
1444 |
if type(node) is InternalNode: |
|
1445 |
# Without looking at any leaf nodes, we are sure
|
|
1446 |
return self |
|
1447 |
for key, value in node._items.iteritems(): |
|
1448 |
if new_leaf._map_no_split(key, value): |
|
1449 |
return self |
|
3735.2.123
by Ian Clatworthy
only check for remap if changes are interesting in size |
1450 |
trace.mutter("remap generated a new LeafNode") |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1451 |
return new_leaf |
1452 |
||
1453 |
||
1454 |
def _deserialise(bytes, key, search_key_func): |
|
1455 |
"""Helper for repositorydetails - convert bytes to a node."""
|
|
1456 |
if bytes.startswith("chkleaf:\n"): |
|
1457 |
node = LeafNode.deserialise(bytes, key, search_key_func=search_key_func) |
|
1458 |
elif bytes.startswith("chknode:\n"): |
|
1459 |
node = InternalNode.deserialise(bytes, key, |
|
1460 |
search_key_func=search_key_func) |
|
1461 |
else: |
|
1462 |
raise AssertionError("Unknown node type.") |
|
1463 |
return node |
|
1464 |
||
1465 |
||
4476.1.38
by John Arbash Meinel
Rename InterestingNodeIterator => CHKMapDifference, update tests. |
1466 |
class CHKMapDifference(object): |
1467 |
"""Iterate the stored pages and key,value pairs for (new - old).
|
|
1468 |
||
1469 |
This class provides a generator over the stored CHK pages and the
|
|
1470 |
(key, value) pairs that are in any of the new maps and not in any of the
|
|
1471 |
old maps.
|
|
1472 |
||
1473 |
Note that it may yield chk pages that are common (especially root nodes),
|
|
1474 |
but it won't yield (key,value) pairs that are common.
|
|
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1475 |
"""
|
1476 |
||
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1477 |
def __init__(self, store, new_root_keys, old_root_keys, |
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1478 |
search_key_func, pb=None): |
4679.9.15
by John Arbash Meinel
Cleanup some code paths. Make _check_key a helper that can be used |
1479 |
# TODO: Should we add a StaticTuple barrier here? It would be nice to
|
1480 |
# force callers to use StaticTuple, because there will often be
|
|
1481 |
# lots of keys passed in here. And even if we cast it locally,
|
|
1482 |
# that just meanst that we will have *both* a StaticTuple and a
|
|
1483 |
# tuple() in memory, referring to the same object. (so a net
|
|
1484 |
# increase in memory, not a decrease.)
|
|
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1485 |
self._store = store |
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1486 |
self._new_root_keys = new_root_keys |
1487 |
self._old_root_keys = old_root_keys |
|
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1488 |
self._pb = pb |
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1489 |
# All uninteresting chks that we have seen. By the time they are added
|
1490 |
# here, they should be either fully ignored, or queued up for
|
|
1491 |
# processing
|
|
4679.9.23
by John Arbash Meinel
Mostly TODO entries. |
1492 |
# TODO: This might grow to a large size if there are lots of merge
|
1493 |
# parents, etc. However, it probably doesn't scale to O(history)
|
|
1494 |
# like _processed_new_refs does.
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1495 |
self._all_old_chks = set(self._old_root_keys) |
1496 |
# All items that we have seen from the old_root_keys
|
|
1497 |
self._all_old_items = set() |
|
4476.1.32
by John Arbash Meinel
A few more updates. |
1498 |
# These are interesting items which were either read, or already in the
|
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1499 |
# interesting queue (so we don't need to walk them again)
|
4679.9.23
by John Arbash Meinel
Mostly TODO entries. |
1500 |
# TODO: processed_new_refs becomes O(all_chks), consider switching to
|
1501 |
# SimpleSet here.
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1502 |
self._processed_new_refs = set() |
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1503 |
self._search_key_func = search_key_func |
1504 |
||
4476.1.33
by John Arbash Meinel
Simpify the code a lot by ignoring the heapq stuff. |
1505 |
# The uninteresting and interesting nodes to be searched
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1506 |
self._old_queue = [] |
1507 |
self._new_queue = [] |
|
4476.1.34
by John Arbash Meinel
Major rework, simplify what is put into the queues. |
1508 |
# Holds the (key, value) items found when processing the root nodes,
|
1509 |
# waiting for the uninteresting nodes to be walked
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1510 |
self._new_item_queue = [] |
4476.1.17
by John Arbash Meinel
Start running all of the iter_interesting_nodes tests |
1511 |
self._state = None |
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1512 |
|
1513 |
def _read_nodes_from_store(self, keys): |
|
4797.7.1
by Robert Collins
Introduce a threading.local to isolate the chk_map page cache from other threads. |
1514 |
# We chose not to use _get_cache(), because we think in
|
1515 |
# terms of records to be yielded. Also, we expect to touch each page
|
|
1516 |
# only 1 time during this code. (We may want to evaluate saving the
|
|
1517 |
# raw bytes into the page cache, which would allow a working tree
|
|
1518 |
# update after the fetch to not have to read the bytes again.)
|
|
4679.9.20
by John Arbash Meinel
as_st(items) saves about 800kB peak memory. |
1519 |
as_st = StaticTuple.from_sequence |
4476.1.12
by John Arbash Meinel
Start testing the new class. |
1520 |
stream = self._store.get_record_stream(keys, 'unordered', True) |
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1521 |
for record in stream: |
1522 |
if self._pb is not None: |
|
1523 |
self._pb.tick() |
|
1524 |
if record.storage_kind == 'absent': |
|
4476.1.17
by John Arbash Meinel
Start running all of the iter_interesting_nodes tests |
1525 |
raise errors.NoSuchRevision(self._store, record.key) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1526 |
bytes = record.get_bytes_as('fulltext') |
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1527 |
node = _deserialise(bytes, record.key, |
1528 |
search_key_func=self._search_key_func) |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1529 |
if type(node) is InternalNode: |
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1530 |
# Note we don't have to do node.refs() because we know that
|
1531 |
# there are no children that have been pushed into this node
|
|
4679.9.23
by John Arbash Meinel
Mostly TODO entries. |
1532 |
# Note: Using as_st() here seemed to save 1.2MB, which would
|
1533 |
# indicate that we keep 100k prefix_refs around while
|
|
1534 |
# processing. They *should* be shorter lived than that...
|
|
1535 |
# It does cost us ~10s of processing time
|
|
1536 |
#prefix_refs = [as_st(item) for item in node._items.iteritems()]
|
|
1537 |
prefix_refs = node._items.items() |
|
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1538 |
items = [] |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1539 |
else: |
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1540 |
prefix_refs = [] |
4679.9.23
by John Arbash Meinel
Mostly TODO entries. |
1541 |
# Note: We don't use a StaticTuple here. Profiling showed a
|
1542 |
# minor memory improvement (0.8MB out of 335MB peak 0.2%)
|
|
1543 |
# But a significant slowdown (15s / 145s, or 10%)
|
|
1544 |
items = node._items.items() |
|
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1545 |
yield record, node, prefix_refs, items |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1546 |
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1547 |
def _read_old_roots(self): |
1548 |
old_chks_to_enqueue = [] |
|
1549 |
all_old_chks = self._all_old_chks |
|
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1550 |
for record, node, prefix_refs, items in \ |
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1551 |
self._read_nodes_from_store(self._old_root_keys): |
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1552 |
# Uninteresting node
|
4476.1.34
by John Arbash Meinel
Major rework, simplify what is put into the queues. |
1553 |
prefix_refs = [p_r for p_r in prefix_refs |
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1554 |
if p_r[1] not in all_old_chks] |
4476.1.34
by John Arbash Meinel
Major rework, simplify what is put into the queues. |
1555 |
new_refs = [p_r[1] for p_r in prefix_refs] |
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1556 |
all_old_chks.update(new_refs) |
4679.9.23
by John Arbash Meinel
Mostly TODO entries. |
1557 |
# TODO: This might be a good time to turn items into StaticTuple
|
1558 |
# instances and possibly intern them. However, this does not
|
|
1559 |
# impact 'initial branch' performance, so I'm not worrying
|
|
1560 |
# about this yet
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1561 |
self._all_old_items.update(items) |
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1562 |
# Queue up the uninteresting references
|
1563 |
# Don't actually put them in the 'to-read' queue until we have
|
|
1564 |
# finished checking the interesting references
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1565 |
old_chks_to_enqueue.extend(prefix_refs) |
1566 |
return old_chks_to_enqueue |
|
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1567 |
|
4476.1.40
by John Arbash Meinel
cleanup indentation. |
1568 |
def _enqueue_old(self, new_prefixes, old_chks_to_enqueue): |
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1569 |
# At this point, we have read all the uninteresting and interesting
|
1570 |
# items, so we can queue up the uninteresting stuff, knowing that we've
|
|
1571 |
# handled the interesting ones
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1572 |
for prefix, ref in old_chks_to_enqueue: |
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1573 |
not_interesting = True |
1574 |
for i in xrange(len(prefix), 0, -1): |
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1575 |
if prefix[:i] in new_prefixes: |
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1576 |
not_interesting = False |
1577 |
break
|
|
1578 |
if not_interesting: |
|
1579 |
# This prefix is not part of the remaining 'interesting set'
|
|
1580 |
continue
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1581 |
self._old_queue.append(ref) |
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1582 |
|
1583 |
def _read_all_roots(self): |
|
1584 |
"""Read the root pages.
|
|
1585 |
||
1586 |
This is structured as a generator, so that the root records can be
|
|
1587 |
yielded up to whoever needs them without any buffering.
|
|
1588 |
"""
|
|
1589 |
# This is the bootstrap phase
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1590 |
if not self._old_root_keys: |
1591 |
# With no old_root_keys we can just shortcut and be ready
|
|
1592 |
# for _flush_new_queue
|
|
1593 |
self._new_queue = list(self._new_root_keys) |
|
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1594 |
return
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1595 |
old_chks_to_enqueue = self._read_old_roots() |
4476.1.12
by John Arbash Meinel
Start testing the new class. |
1596 |
# filter out any root keys that are already known to be uninteresting
|
4476.1.40
by John Arbash Meinel
cleanup indentation. |
1597 |
new_keys = set(self._new_root_keys).difference(self._all_old_chks) |
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1598 |
# These are prefixes that are present in new_keys that we are
|
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1599 |
# thinking to yield
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1600 |
new_prefixes = set() |
4476.1.18
by John Arbash Meinel
Tracked it down. |
1601 |
# We are about to yield all of these, so we don't want them getting
|
1602 |
# added a second time
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1603 |
processed_new_refs = self._processed_new_refs |
1604 |
processed_new_refs.update(new_keys) |
|
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1605 |
for record, node, prefix_refs, items in \ |
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1606 |
self._read_nodes_from_store(new_keys): |
4476.1.5
by John Arbash Meinel
Start working on a new InterestingNodeIterator class. |
1607 |
# At this level, we now know all the uninteresting references
|
4476.1.35
by John Arbash Meinel
Change some of the inner loop workings into list comprehensions. |
1608 |
# So we filter and queue up whatever is remaining
|
1609 |
prefix_refs = [p_r for p_r in prefix_refs |
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1610 |
if p_r[1] not in self._all_old_chks |
1611 |
and p_r[1] not in processed_new_refs] |
|
4476.1.35
by John Arbash Meinel
Change some of the inner loop workings into list comprehensions. |
1612 |
refs = [p_r[1] for p_r in prefix_refs] |
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1613 |
new_prefixes.update([p_r[0] for p_r in prefix_refs]) |
1614 |
self._new_queue.extend(refs) |
|
4476.1.34
by John Arbash Meinel
Major rework, simplify what is put into the queues. |
1615 |
# TODO: We can potentially get multiple items here, however the
|
1616 |
# current design allows for this, as callers will do the work
|
|
1617 |
# to make the results unique. We might profile whether we
|
|
1618 |
# gain anything by ensuring unique return values for items
|
|
4679.9.23
by John Arbash Meinel
Mostly TODO entries. |
1619 |
# TODO: This might be a good time to cast to StaticTuple, as
|
1620 |
# self._new_item_queue will hold the contents of multiple
|
|
1621 |
# records for an extended lifetime
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1622 |
new_items = [item for item in items |
4476.1.40
by John Arbash Meinel
cleanup indentation. |
1623 |
if item not in self._all_old_items] |
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1624 |
self._new_item_queue.extend(new_items) |
1625 |
new_prefixes.update([self._search_key_func(item[0]) |
|
4476.1.40
by John Arbash Meinel
cleanup indentation. |
1626 |
for item in new_items]) |
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1627 |
processed_new_refs.update(refs) |
4476.1.13
by John Arbash Meinel
Test that _read_all_roots does what is expected |
1628 |
yield record |
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1629 |
# For new_prefixes we have the full length prefixes queued up.
|
4476.1.35
by John Arbash Meinel
Change some of the inner loop workings into list comprehensions. |
1630 |
# However, we also need possible prefixes. (If we have a known ref to
|
1631 |
# 'ab', then we also need to include 'a'.) So expand the
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1632 |
# new_prefixes to include all shorter prefixes
|
1633 |
for prefix in list(new_prefixes): |
|
4476.1.40
by John Arbash Meinel
cleanup indentation. |
1634 |
new_prefixes.update([prefix[:i] for i in xrange(1, len(prefix))]) |
1635 |
self._enqueue_old(new_prefixes, old_chks_to_enqueue) |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1636 |
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1637 |
def _flush_new_queue(self): |
4476.1.27
by John Arbash Meinel
Rewrite of _flush_interesting_queue |
1638 |
# No need to maintain the heap invariant anymore, just pull things out
|
1639 |
# and process them
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1640 |
refs = set(self._new_queue) |
1641 |
self._new_queue = [] |
|
4476.1.31
by John Arbash Meinel
streamline the _flush_interesting_queue a bit. |
1642 |
# First pass, flush all interesting items and convert to using direct refs
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1643 |
all_old_chks = self._all_old_chks |
1644 |
processed_new_refs = self._processed_new_refs |
|
1645 |
all_old_items = self._all_old_items |
|
1646 |
new_items = [item for item in self._new_item_queue |
|
4476.1.40
by John Arbash Meinel
cleanup indentation. |
1647 |
if item not in all_old_items] |
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1648 |
self._new_item_queue = [] |
1649 |
if new_items: |
|
1650 |
yield None, new_items |
|
1651 |
refs = refs.difference(all_old_chks) |
|
4679.9.23
by John Arbash Meinel
Mostly TODO entries. |
1652 |
processed_new_refs.update(refs) |
4476.1.31
by John Arbash Meinel
streamline the _flush_interesting_queue a bit. |
1653 |
while refs: |
4679.9.24
by John Arbash Meinel
Note a memory savings with a special set |
1654 |
# TODO: Using a SimpleSet for self._processed_new_refs and
|
1655 |
# saved as much as 10MB of peak memory. However, it requires
|
|
1656 |
# implementing a non-pyrex version.
|
|
4476.1.31
by John Arbash Meinel
streamline the _flush_interesting_queue a bit. |
1657 |
next_refs = set() |
1658 |
next_refs_update = next_refs.update |
|
1659 |
# Inlining _read_nodes_from_store improves 'bzr branch bzr.dev'
|
|
1660 |
# from 1m54s to 1m51s. Consider it.
|
|
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1661 |
for record, _, p_refs, items in self._read_nodes_from_store(refs): |
4679.9.23
by John Arbash Meinel
Mostly TODO entries. |
1662 |
if all_old_items: |
1663 |
# using the 'if' check saves about 145s => 141s, when
|
|
1664 |
# streaming initial branch of Launchpad data.
|
|
1665 |
items = [item for item in items |
|
1666 |
if item not in all_old_items] |
|
4476.1.27
by John Arbash Meinel
Rewrite of _flush_interesting_queue |
1667 |
yield record, items |
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1668 |
next_refs_update([p_r[1] for p_r in p_refs]) |
4679.9.23
by John Arbash Meinel
Mostly TODO entries. |
1669 |
del p_refs |
1670 |
# set1.difference(set/dict) walks all of set1, and checks if it
|
|
1671 |
# exists in 'other'.
|
|
1672 |
# set1.difference(iterable) walks all of iterable, and does a
|
|
1673 |
# 'difference_update' on a clone of set1. Pick wisely based on the
|
|
1674 |
# expected sizes of objects.
|
|
1675 |
# in our case it is expected that 'new_refs' will always be quite
|
|
1676 |
# small.
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1677 |
next_refs = next_refs.difference(all_old_chks) |
1678 |
next_refs = next_refs.difference(processed_new_refs) |
|
1679 |
processed_new_refs.update(next_refs) |
|
4476.1.31
by John Arbash Meinel
streamline the _flush_interesting_queue a bit. |
1680 |
refs = next_refs |
4476.1.17
by John Arbash Meinel
Start running all of the iter_interesting_nodes tests |
1681 |
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1682 |
def _process_next_old(self): |
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1683 |
# Since we don't filter uninteresting any further than during
|
1684 |
# _read_all_roots, process the whole queue in a single pass.
|
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1685 |
refs = self._old_queue |
1686 |
self._old_queue = [] |
|
1687 |
all_old_chks = self._all_old_chks |
|
4476.1.32
by John Arbash Meinel
A few more updates. |
1688 |
for record, _, prefix_refs, items in self._read_nodes_from_store(refs): |
4679.9.23
by John Arbash Meinel
Mostly TODO entries. |
1689 |
# TODO: Use StaticTuple here?
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1690 |
self._all_old_items.update(items) |
1691 |
refs = [r for _,r in prefix_refs if r not in all_old_chks] |
|
1692 |
self._old_queue.extend(refs) |
|
1693 |
all_old_chks.update(refs) |
|
4476.1.17
by John Arbash Meinel
Start running all of the iter_interesting_nodes tests |
1694 |
|
1695 |
def _process_queues(self): |
|
4476.1.39
by John Arbash Meinel
Rename interesting => new, uninteresting => old |
1696 |
while self._old_queue: |
1697 |
self._process_next_old() |
|
1698 |
return self._flush_new_queue() |
|
4476.1.17
by John Arbash Meinel
Start running all of the iter_interesting_nodes tests |
1699 |
|
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1700 |
def process(self): |
1701 |
for record in self._read_all_roots(): |
|
1702 |
yield record, [] |
|
1703 |
for record, items in self._process_queues(): |
|
1704 |
yield record, items |
|
1705 |
||
4476.1.25
by John Arbash Meinel
A bit more testing. |
1706 |
|
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1707 |
def iter_interesting_nodes(store, interesting_root_keys, |
1708 |
uninteresting_root_keys, pb=None): |
|
1709 |
"""Given root keys, find interesting nodes.
|
|
1710 |
||
1711 |
Evaluate nodes referenced by interesting_root_keys. Ones that are also
|
|
1712 |
referenced from uninteresting_root_keys are not considered interesting.
|
|
1713 |
||
1714 |
:param interesting_root_keys: keys which should be part of the
|
|
1715 |
"interesting" nodes (which will be yielded)
|
|
1716 |
:param uninteresting_root_keys: keys which should be filtered out of the
|
|
1717 |
result set.
|
|
1718 |
:return: Yield
|
|
1719 |
(interesting record, {interesting key:values})
|
|
1720 |
"""
|
|
4476.1.38
by John Arbash Meinel
Rename InterestingNodeIterator => CHKMapDifference, update tests. |
1721 |
iterator = CHKMapDifference(store, interesting_root_keys, |
1722 |
uninteresting_root_keys, |
|
1723 |
search_key_func=store._search_key_func, |
|
1724 |
pb=pb) |
|
4476.1.37
by John Arbash Meinel
Some small code cleanup passes |
1725 |
return iterator.process() |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1726 |
|
1727 |
||
1728 |
try: |
|
1729 |
from bzrlib._chk_map_pyx import ( |
|
5218.2.1
by John Arbash Meinel
Implement a compiled extension for parsing the text key out of a CHKInventory value. |
1730 |
_bytes_to_text_key, |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1731 |
_search_key_16, |
1732 |
_search_key_255, |
|
1733 |
_deserialise_leaf_node, |
|
1734 |
_deserialise_internal_node, |
|
1735 |
)
|
|
4574.3.6
by Martin Pool
More warnings when failing to load extensions |
1736 |
except ImportError, e: |
4574.3.8
by Martin Pool
Only mutter extension load errors when they occur, and record for later |
1737 |
osutils.failed_to_load_extension(e) |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1738 |
from bzrlib._chk_map_py import ( |
5218.2.1
by John Arbash Meinel
Implement a compiled extension for parsing the text key out of a CHKInventory value. |
1739 |
_bytes_to_text_key, |
4241.6.1
by Ian Clatworthy
chk_map code from brisbane-core |
1740 |
_search_key_16, |
1741 |
_search_key_255, |
|
1742 |
_deserialise_leaf_node, |
|
1743 |
_deserialise_internal_node, |
|
1744 |
)
|
|
1745 |
search_key_registry.register('hash-16-way', _search_key_16) |
|
1746 |
search_key_registry.register('hash-255-way', _search_key_255) |
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
1747 |
|
4679.9.15
by John Arbash Meinel
Cleanup some code paths. Make _check_key a helper that can be used |
1748 |
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
1749 |
def _check_key(key): |
4679.9.15
by John Arbash Meinel
Cleanup some code paths. Make _check_key a helper that can be used |
1750 |
"""Helper function to assert that a key is properly formatted.
|
1751 |
||
1752 |
This generally shouldn't be used in production code, but it can be helpful
|
|
1753 |
to debug problems.
|
|
1754 |
"""
|
|
4679.9.4
by John Arbash Meinel
A bit broken, but getting there. |
1755 |
if type(key) is not StaticTuple: |
1756 |
raise TypeError('key %r is not StaticTuple but %s' % (key, type(key))) |
|
1757 |
if len(key) != 1: |
|
1758 |
raise ValueError('key %r should have length 1, not %d' % (key, len(key),)) |
|
1759 |
if type(key[0]) is not str: |
|
1760 |
raise TypeError('key %r should hold a str, not %r' |
|
1761 |
% (key, type(key[0]))) |
|
1762 |
if not key[0].startswith('sha1:'): |
|
1763 |
raise ValueError('key %r should point to a sha1:' % (key,)) |
|
1764 |
||
1765 |