« back to all changes in this revision
Viewing changes to bzrlib/tests/test_chk_map.py
- browse files at revision 4536
- compare with another revision
- compare with revision 6217
- download diff
- download tarball
- view history from revision 4536
- Committer: Canonical.com Patch Queue Manager
- Date: 2009-07-14 17:33:13 UTC
- mfrom: (4476.1.40 1.17-chk-multilevel)
- Revision ID: pqm@pqm.ubuntu.com-20090714173313-3p3ytzlfuc3y2bm6
(jam) Some rework of the internals of chk_map.iter_interesting_nodes.
added
removed
bzrlib/tests/test_chk_map.py
20
20
21
21
from bzrlib import (
22
22
chk_map,
23
groupcompress,
23
24
osutils,
24
25
tests,
25
26
)
59
60
self.assertCommonPrefix('', '', '')
60
61
61
62
62
class TestCaseWithStore(tests.TestCaseWithTransport):
63
class TestCaseWithStore(tests.TestCaseWithMemoryTransport):
63
64
64
65
def get_chk_bytes(self):
65
66
# The easiest way to get a CHK store is a development6 repository and
66
67
# then work with the chk_bytes attribute directly.
67
repo = self.make_repository(".", format="development6-rich-root")
68
repo.lock_write()
69
self.addCleanup(repo.unlock)
70
repo.start_write_group()
71
self.addCleanup(repo.abort_write_group)
72
return repo.chk_bytes
68
factory = groupcompress.make_pack_factory(False, False, 1)
69
self.chk_bytes = factory(self.get_transport())
70
return self.chk_bytes
73
71
74
72
def _get_map(self, a_dict, maximum_size=0, chk_bytes=None, key_width=1,
75
73
search_key_func=None):
97
95
return dict(node.iteritems(*args))
98
96
99
97
98
class TestCaseWithExampleMaps(TestCaseWithStore):
99
100
def get_chk_bytes(self):
101
if getattr(self, '_chk_bytes', None) is None:
102
self._chk_bytes = super(TestCaseWithExampleMaps,
103
self).get_chk_bytes()
104
return self._chk_bytes
105
106
def get_map(self, a_dict, maximum_size=100, search_key_func=None):
107
c_map = self._get_map(a_dict, maximum_size=maximum_size,
108
chk_bytes=self.get_chk_bytes(),
109
search_key_func=search_key_func)
110
return c_map
111
112
def make_root_only_map(self, search_key_func=None):
113
return self.get_map({
114
('aaa',): 'initial aaa content',
115
('abb',): 'initial abb content',
116
}, search_key_func=search_key_func)
117
118
def make_root_only_aaa_ddd_map(self, search_key_func=None):
119
return self.get_map({
120
('aaa',): 'initial aaa content',
121
('ddd',): 'initial ddd content',
122
}, search_key_func=search_key_func)
123
124
def make_one_deep_map(self, search_key_func=None):
125
# Same as root_only_map, except it forces an InternalNode at the root
126
return self.get_map({
127
('aaa',): 'initial aaa content',
128
('abb',): 'initial abb content',
129
('ccc',): 'initial ccc content',
130
('ddd',): 'initial ddd content',
131
}, search_key_func=search_key_func)
132
133
def make_two_deep_map(self, search_key_func=None):
134
# Carefully chosen so that it creates a 2-deep map for both
135
# _search_key_plain and for _search_key_16
136
# Also so that things line up with make_one_deep_two_prefix_map
137
return self.get_map({
138
('aaa',): 'initial aaa content',
139
('abb',): 'initial abb content',
140
('acc',): 'initial acc content',
141
('ace',): 'initial ace content',
142
('add',): 'initial add content',
143
('adh',): 'initial adh content',
144
('adl',): 'initial adl content',
145
('ccc',): 'initial ccc content',
146
('ddd',): 'initial ddd content',
147
}, search_key_func=search_key_func)
148
149
def make_one_deep_two_prefix_map(self, search_key_func=None):
150
"""Create a map with one internal node, but references are extra long.
151
152
Otherwise has similar content to make_two_deep_map.
153
"""
154
return self.get_map({
155
('aaa',): 'initial aaa content',
156
('add',): 'initial add content',
157
('adh',): 'initial adh content',
158
('adl',): 'initial adl content',
159
}, search_key_func=search_key_func)
160
161
def make_one_deep_one_prefix_map(self, search_key_func=None):
162
"""Create a map with one internal node, but references are extra long.
163
164
Similar to make_one_deep_two_prefix_map, except the split is at the
165
first char, rather than the second.
166
"""
167
return self.get_map({
168
('add',): 'initial add content',
169
('adh',): 'initial adh content',
170
('adl',): 'initial adl content',
171
('bbb',): 'initial bbb content',
172
}, search_key_func=search_key_func)
173
174
175
class TestTestCaseWithExampleMaps(TestCaseWithExampleMaps):
176
"""Actual tests for the provided examples."""
177
178
def test_root_only_map_plain(self):
179
c_map = self.make_root_only_map()
180
self.assertEqualDiff(
181
"'' LeafNode\n"
182
" ('aaa',) 'initial aaa content'\n"
183
" ('abb',) 'initial abb content'\n",
184
c_map._dump_tree())
185
186
def test_root_only_map_16(self):
187
c_map = self.make_root_only_map(search_key_func=chk_map._search_key_16)
188
self.assertEqualDiff(
189
"'' LeafNode\n"
190
" ('aaa',) 'initial aaa content'\n"
191
" ('abb',) 'initial abb content'\n",
192
c_map._dump_tree())
193
194
def test_one_deep_map_plain(self):
195
c_map = self.make_one_deep_map()
196
self.assertEqualDiff(
197
"'' InternalNode\n"
198
" 'a' LeafNode\n"
199
" ('aaa',) 'initial aaa content'\n"
200
" ('abb',) 'initial abb content'\n"
201
" 'c' LeafNode\n"
202
" ('ccc',) 'initial ccc content'\n"
203
" 'd' LeafNode\n"
204
" ('ddd',) 'initial ddd content'\n",
205
c_map._dump_tree())
206
207
def test_one_deep_map_16(self):
208
c_map = self.make_one_deep_map(search_key_func=chk_map._search_key_16)
209
self.assertEqualDiff(
210
"'' InternalNode\n"
211
" '2' LeafNode\n"
212
" ('ccc',) 'initial ccc content'\n"
213
" '4' LeafNode\n"
214
" ('abb',) 'initial abb content'\n"
215
" 'F' LeafNode\n"
216
" ('aaa',) 'initial aaa content'\n"
217
" ('ddd',) 'initial ddd content'\n",
218
c_map._dump_tree())
219
220
def test_root_only_aaa_ddd_plain(self):
221
c_map = self.make_root_only_aaa_ddd_map()
222
self.assertEqualDiff(
223
"'' LeafNode\n"
224
" ('aaa',) 'initial aaa content'\n"
225
" ('ddd',) 'initial ddd content'\n",
226
c_map._dump_tree())
227
228
def test_one_deep_map_16(self):
229
c_map = self.make_root_only_aaa_ddd_map(
230
search_key_func=chk_map._search_key_16)
231
# We use 'aaa' and 'ddd' because they happen to map to 'F' when using
232
# _search_key_16
233
self.assertEqualDiff(
234
"'' LeafNode\n"
235
" ('aaa',) 'initial aaa content'\n"
236
" ('ddd',) 'initial ddd content'\n",
237
c_map._dump_tree())
238
239
def test_two_deep_map_plain(self):
240
c_map = self.make_two_deep_map()
241
self.assertEqualDiff(
242
"'' InternalNode\n"
243
" 'a' InternalNode\n"
244
" 'aa' LeafNode\n"
245
" ('aaa',) 'initial aaa content'\n"
246
" 'ab' LeafNode\n"
247
" ('abb',) 'initial abb content'\n"
248
" 'ac' LeafNode\n"
249
" ('acc',) 'initial acc content'\n"
250
" ('ace',) 'initial ace content'\n"
251
" 'ad' LeafNode\n"
252
" ('add',) 'initial add content'\n"
253
" ('adh',) 'initial adh content'\n"
254
" ('adl',) 'initial adl content'\n"
255
" 'c' LeafNode\n"
256
" ('ccc',) 'initial ccc content'\n"
257
" 'd' LeafNode\n"
258
" ('ddd',) 'initial ddd content'\n",
259
c_map._dump_tree())
260
261
def test_two_deep_map_16(self):
262
c_map = self.make_two_deep_map(search_key_func=chk_map._search_key_16)
263
self.assertEqualDiff(
264
"'' InternalNode\n"
265
" '2' LeafNode\n"
266
" ('acc',) 'initial acc content'\n"
267
" ('ccc',) 'initial ccc content'\n"
268
" '4' LeafNode\n"
269
" ('abb',) 'initial abb content'\n"
270
" 'C' LeafNode\n"
271
" ('ace',) 'initial ace content'\n"
272
" 'F' InternalNode\n"
273
" 'F0' LeafNode\n"
274
" ('aaa',) 'initial aaa content'\n"
275
" 'F3' LeafNode\n"
276
" ('adl',) 'initial adl content'\n"
277
" 'F4' LeafNode\n"
278
" ('adh',) 'initial adh content'\n"
279
" 'FB' LeafNode\n"
280
" ('ddd',) 'initial ddd content'\n"
281
" 'FD' LeafNode\n"
282
" ('add',) 'initial add content'\n",
283
c_map._dump_tree())
284
285
def test_one_deep_two_prefix_map_plain(self):
286
c_map = self.make_one_deep_two_prefix_map()
287
self.assertEqualDiff(
288
"'' InternalNode\n"
289
" 'aa' LeafNode\n"
290
" ('aaa',) 'initial aaa content'\n"
291
" 'ad' LeafNode\n"
292
" ('add',) 'initial add content'\n"
293
" ('adh',) 'initial adh content'\n"
294
" ('adl',) 'initial adl content'\n",
295
c_map._dump_tree())
296
297
def test_one_deep_two_prefix_map_16(self):
298
c_map = self.make_one_deep_two_prefix_map(
299
search_key_func=chk_map._search_key_16)
300
self.assertEqualDiff(
301
"'' InternalNode\n"
302
" 'F0' LeafNode\n"
303
" ('aaa',) 'initial aaa content'\n"
304
" 'F3' LeafNode\n"
305
" ('adl',) 'initial adl content'\n"
306
" 'F4' LeafNode\n"
307
" ('adh',) 'initial adh content'\n"
308
" 'FD' LeafNode\n"
309
" ('add',) 'initial add content'\n",
310
c_map._dump_tree())
311
312
def test_one_deep_one_prefix_map_plain(self):
313
c_map = self.make_one_deep_one_prefix_map()
314
self.assertEqualDiff(
315
"'' InternalNode\n"
316
" 'a' LeafNode\n"
317
" ('add',) 'initial add content'\n"
318
" ('adh',) 'initial adh content'\n"
319
" ('adl',) 'initial adl content'\n"
320
" 'b' LeafNode\n"
321
" ('bbb',) 'initial bbb content'\n",
322
c_map._dump_tree())
323
324
def test_one_deep_one_prefix_map_16(self):
325
c_map = self.make_one_deep_one_prefix_map(
326
search_key_func=chk_map._search_key_16)
327
self.assertEqualDiff(
328
"'' InternalNode\n"
329
" '4' LeafNode\n"
330
" ('bbb',) 'initial bbb content'\n"
331
" 'F' LeafNode\n"
332
" ('add',) 'initial add content'\n"
333
" ('adh',) 'initial adh content'\n"
334
" ('adl',) 'initial adl content'\n",
335
c_map._dump_tree())
336
337
100
338
class TestMap(TestCaseWithStore):
101
339
102
340
def assertHasABMap(self, chk_bytes):
1886
2124
# 1-4K get0
1887
2125
1888
2126
1889
class TestIterInterestingNodes(TestCaseWithStore):
1890
1891
def get_chk_bytes(self):
1892
if getattr(self, '_chk_bytes', None) is None:
1893
self._chk_bytes = super(TestIterInterestingNodes,
1894
self).get_chk_bytes()
1895
return self._chk_bytes
2127
class TestCHKMapDifference(TestCaseWithExampleMaps):
2128
2129
def get_difference(self, new_roots, old_roots,
2130
search_key_func=None):
2131
if search_key_func is None:
2132
search_key_func = chk_map._search_key_plain
2133
return chk_map.CHKMapDifference(self.get_chk_bytes(),
2134
new_roots, old_roots, search_key_func)
2135
2136
def test__init__(self):
2137
c_map = self.make_root_only_map()
2138
key1 = c_map.key()
2139
c_map.map(('aaa',), 'new aaa content')
2140
key2 = c_map._save()
2141
diff = self.get_difference([key2], [key1])
2142
self.assertEqual(set([key1]), diff._all_old_chks)
2143
self.assertEqual([], diff._old_queue)
2144
self.assertEqual([], diff._new_queue)
2145
2146
def help__read_all_roots(self, search_key_func):
2147
c_map = self.make_root_only_map(search_key_func=search_key_func)
2148
key1 = c_map.key()
2149
c_map.map(('aaa',), 'new aaa content')
2150
key2 = c_map._save()
2151
diff = self.get_difference([key2], [key1], search_key_func)
2152
root_results = [record.key for record in diff._read_all_roots()]
2153
self.assertEqual([key2], root_results)
2154
# We should have queued up only items that aren't in the old
2155
# set
2156
self.assertEqual([(('aaa',), 'new aaa content')],
2157
diff._new_item_queue)
2158
self.assertEqual([], diff._new_queue)
2159
# And there are no old references, so that queue should be
2160
# empty
2161
self.assertEqual([], diff._old_queue)
2162
2163
def test__read_all_roots_plain(self):
2164
self.help__read_all_roots(search_key_func=chk_map._search_key_plain)
2165
2166
def test__read_all_roots_16(self):
2167
self.help__read_all_roots(search_key_func=chk_map._search_key_16)
2168
2169
def test__read_all_roots_skips_known_old(self):
2170
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2171
key1 = c_map.key()
2172
c_map2 = self.make_root_only_map(chk_map._search_key_plain)
2173
key2 = c_map2.key()
2174
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2175
root_results = [record.key for record in diff._read_all_roots()]
2176
# We should have no results. key2 is completely contained within key1,
2177
# and we should have seen that in the first pass
2178
self.assertEqual([], root_results)
2179
2180
def test__read_all_roots_prepares_queues(self):
2181
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2182
key1 = c_map.key()
2183
c_map._dump_tree() # load everything
2184
key1_a = c_map._root_node._items['a'].key()
2185
c_map.map(('abb',), 'new abb content')
2186
key2 = c_map._save()
2187
key2_a = c_map._root_node._items['a'].key()
2188
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2189
root_results = [record.key for record in diff._read_all_roots()]
2190
self.assertEqual([key2], root_results)
2191
# At this point, we should have queued up only the 'a' Leaf on both
2192
# sides, both 'c' and 'd' are known to not have changed on both sides
2193
self.assertEqual([key2_a], diff._new_queue)
2194
self.assertEqual([], diff._new_item_queue)
2195
self.assertEqual([key1_a], diff._old_queue)
2196
2197
def test__read_all_roots_multi_new_prepares_queues(self):
2198
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2199
key1 = c_map.key()
2200
c_map._dump_tree() # load everything
2201
key1_a = c_map._root_node._items['a'].key()
2202
key1_c = c_map._root_node._items['c'].key()
2203
c_map.map(('abb',), 'new abb content')
2204
key2 = c_map._save()
2205
key2_a = c_map._root_node._items['a'].key()
2206
key2_c = c_map._root_node._items['c'].key()
2207
c_map = chk_map.CHKMap(self.get_chk_bytes(), key1,
2208
chk_map._search_key_plain)
2209
c_map.map(('ccc',), 'new ccc content')
2210
key3 = c_map._save()
2211
key3_a = c_map._root_node._items['a'].key()
2212
key3_c = c_map._root_node._items['c'].key()
2213
diff = self.get_difference([key2, key3], [key1],
2214
chk_map._search_key_plain)
2215
root_results = [record.key for record in diff._read_all_roots()]
2216
self.assertEqual(sorted([key2, key3]), sorted(root_results))
2217
# We should have queued up key2_a, and key3_c, but not key2_c or key3_c
2218
self.assertEqual([key2_a, key3_c], diff._new_queue)
2219
self.assertEqual([], diff._new_item_queue)
2220
# And we should have queued up both a and c for the old set
2221
self.assertEqual([key1_a, key1_c], diff._old_queue)
2222
2223
def test__read_all_roots_different_depths(self):
2224
c_map = self.make_two_deep_map(chk_map._search_key_plain)
2225
c_map._dump_tree() # load everything
2226
key1 = c_map.key()
2227
key1_a = c_map._root_node._items['a'].key()
2228
key1_c = c_map._root_node._items['c'].key()
2229
key1_d = c_map._root_node._items['d'].key()
2230
2231
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2232
c_map2._dump_tree()
2233
key2 = c_map2.key()
2234
key2_aa = c_map2._root_node._items['aa'].key()
2235
key2_ad = c_map2._root_node._items['ad'].key()
2236
2237
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2238
root_results = [record.key for record in diff._read_all_roots()]
2239
self.assertEqual([key2], root_results)
2240
# Only the 'a' subset should be queued up, since 'c' and 'd' cannot be
2241
# present
2242
self.assertEqual([key1_a], diff._old_queue)
2243
self.assertEqual([key2_aa, key2_ad], diff._new_queue)
2244
self.assertEqual([], diff._new_item_queue)
2245
2246
diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2247
root_results = [record.key for record in diff._read_all_roots()]
2248
self.assertEqual([key1], root_results)
2249
2250
self.assertEqual([key2_aa, key2_ad], diff._old_queue)
2251
self.assertEqual([key1_a, key1_c, key1_d], diff._new_queue)
2252
self.assertEqual([], diff._new_item_queue)
2253
2254
def test__read_all_roots_different_depths_16(self):
2255
c_map = self.make_two_deep_map(chk_map._search_key_16)
2256
c_map._dump_tree() # load everything
2257
key1 = c_map.key()
2258
key1_2 = c_map._root_node._items['2'].key()
2259
key1_4 = c_map._root_node._items['4'].key()
2260
key1_C = c_map._root_node._items['C'].key()
2261
key1_F = c_map._root_node._items['F'].key()
2262
2263
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_16)
2264
c_map2._dump_tree()
2265
key2 = c_map2.key()
2266
key2_F0 = c_map2._root_node._items['F0'].key()
2267
key2_F3 = c_map2._root_node._items['F3'].key()
2268
key2_F4 = c_map2._root_node._items['F4'].key()
2269
key2_FD = c_map2._root_node._items['FD'].key()
2270
2271
diff = self.get_difference([key2], [key1], chk_map._search_key_16)
2272
root_results = [record.key for record in diff._read_all_roots()]
2273
self.assertEqual([key2], root_results)
2274
# Only the subset of keys that may be present should be queued up.
2275
self.assertEqual([key1_F], diff._old_queue)
2276
self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
2277
sorted(diff._new_queue))
2278
self.assertEqual([], diff._new_item_queue)
2279
2280
diff = self.get_difference([key1], [key2], chk_map._search_key_16)
2281
root_results = [record.key for record in diff._read_all_roots()]
2282
self.assertEqual([key1], root_results)
2283
2284
self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
2285
sorted(diff._old_queue))
2286
self.assertEqual(sorted([key1_2, key1_4, key1_C, key1_F]),
2287
sorted(diff._new_queue))
2288
self.assertEqual([], diff._new_item_queue)
2289
2290
def test__read_all_roots_mixed_depth(self):
2291
c_map = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2292
c_map._dump_tree() # load everything
2293
key1 = c_map.key()
2294
key1_aa = c_map._root_node._items['aa'].key()
2295
key1_ad = c_map._root_node._items['ad'].key()
2296
2297
c_map2 = self.make_one_deep_one_prefix_map(chk_map._search_key_plain)
2298
c_map2._dump_tree()
2299
key2 = c_map2.key()
2300
key2_a = c_map2._root_node._items['a'].key()
2301
key2_b = c_map2._root_node._items['b'].key()
2302
2303
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2304
root_results = [record.key for record in diff._read_all_roots()]
2305
self.assertEqual([key2], root_results)
2306
# 'ad' matches exactly 'a' on the other side, so it should be removed,
2307
# and neither side should have it queued for walking
2308
self.assertEqual([], diff._old_queue)
2309
self.assertEqual([key2_b], diff._new_queue)
2310
self.assertEqual([], diff._new_item_queue)
2311
2312
diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2313
root_results = [record.key for record in diff._read_all_roots()]
2314
self.assertEqual([key1], root_results)
2315
# Note: This is technically not the 'true minimal' set that we could
2316
# use The reason is that 'a' was matched exactly to 'ad' (by sha
2317
# sum). However, the code gets complicated in the case of more
2318
# than one interesting key, so for now, we live with this
2319
# Consider revising, though benchmarking showing it to be a
2320
# real-world issue should be done
2321
self.assertEqual([key2_a], diff._old_queue)
2322
# self.assertEqual([], diff._old_queue)
2323
self.assertEqual([key1_aa], diff._new_queue)
2324
self.assertEqual([], diff._new_item_queue)
2325
2326
def test__read_all_roots_yields_extra_deep_records(self):
2327
# This is slightly controversial, as we will yield a chk page that we
2328
# might later on find out could be filtered out. (If a root node is
2329
# referenced deeper in the old set.)
2330
# However, even with stacking, we always have all chk pages that we
2331
# will need. So as long as we filter out the referenced keys, we'll
2332
# never run into problems.
2333
# This allows us to yield a root node record immediately, without any
2334
# buffering.
2335
c_map = self.make_two_deep_map(chk_map._search_key_plain)
2336
c_map._dump_tree() # load all keys
2337
key1 = c_map.key()
2338
key1_a = c_map._root_node._items['a'].key()
2339
c_map2 = self.get_map({
2340
('acc',): 'initial acc content',
2341
('ace',): 'initial ace content',
2342
}, maximum_size=100)
2343
self.assertEqualDiff(
2344
"'' LeafNode\n"
2345
" ('acc',) 'initial acc content'\n"
2346
" ('ace',) 'initial ace content'\n",
2347
c_map2._dump_tree())
2348
key2 = c_map2.key()
2349
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2350
root_results = [record.key for record in diff._read_all_roots()]
2351
self.assertEqual([key2], root_results)
2352
# However, even though we have yielded the root node to be fetched,
2353
# we should have enqued all of the chk pages to be walked, so that we
2354
# can find the keys if they are present
2355
self.assertEqual([key1_a], diff._old_queue)
2356
self.assertEqual([(('acc',), 'initial acc content'),
2357
(('ace',), 'initial ace content'),
2358
], diff._new_item_queue)
2359
2360
def test__read_all_roots_multiple_targets(self):
2361
c_map = self.make_root_only_map()
2362
key1 = c_map.key()
2363
c_map = self.make_one_deep_map()
2364
key2 = c_map.key()
2365
c_map._dump_tree()
2366
key2_c = c_map._root_node._items['c'].key()
2367
key2_d = c_map._root_node._items['d'].key()
2368
c_map.map(('ccc',), 'new ccc value')
2369
key3 = c_map._save()
2370
key3_c = c_map._root_node._items['c'].key()
2371
diff = self.get_difference([key2, key3], [key1],
2372
chk_map._search_key_plain)
2373
root_results = [record.key for record in diff._read_all_roots()]
2374
self.assertEqual(sorted([key2, key3]), sorted(root_results))
2375
self.assertEqual([], diff._old_queue)
2376
# the key 'd' is interesting from key2 and key3, but should only be
2377
# entered into the queue 1 time
2378
self.assertEqual(sorted([key2_c, key3_c, key2_d]),
2379
sorted(diff._new_queue))
2380
self.assertEqual([], diff._new_item_queue)
2381
2382
def test__read_all_roots_no_old(self):
2383
# This is the 'initial branch' case. With nothing in the old
2384
# set, we can just queue up all root nodes into interesting queue, and
2385
# then have them fast-path flushed via _flush_new_queue
2386
c_map = self.make_two_deep_map()
2387
key1 = c_map.key()
2388
diff = self.get_difference([key1], [], chk_map._search_key_plain)
2389
root_results = [record.key for record in diff._read_all_roots()]
2390
self.assertEqual([], root_results)
2391
self.assertEqual([], diff._old_queue)
2392
self.assertEqual([key1], diff._new_queue)
2393
self.assertEqual([], diff._new_item_queue)
2394
2395
c_map2 = self.make_one_deep_map()
2396
key2 = c_map2.key()
2397
diff = self.get_difference([key1, key2], [], chk_map._search_key_plain)
2398
root_results = [record.key for record in diff._read_all_roots()]
2399
self.assertEqual([], root_results)
2400
self.assertEqual([], diff._old_queue)
2401
self.assertEqual(sorted([key1, key2]), sorted(diff._new_queue))
2402
self.assertEqual([], diff._new_item_queue)
2403
2404
def test__read_all_roots_no_old_16(self):
2405
c_map = self.make_two_deep_map(chk_map._search_key_16)
2406
key1 = c_map.key()
2407
diff = self.get_difference([key1], [], chk_map._search_key_16)
2408
root_results = [record.key for record in diff._read_all_roots()]
2409
self.assertEqual([], root_results)
2410
self.assertEqual([], diff._old_queue)
2411
self.assertEqual([key1], diff._new_queue)
2412
self.assertEqual([], diff._new_item_queue)
2413
2414
c_map2 = self.make_one_deep_map(chk_map._search_key_16)
2415
key2 = c_map2.key()
2416
diff = self.get_difference([key1, key2], [],
2417
chk_map._search_key_16)
2418
root_results = [record.key for record in diff._read_all_roots()]
2419
self.assertEqual([], root_results)
2420
self.assertEqual([], diff._old_queue)
2421
self.assertEqual(sorted([key1, key2]),
2422
sorted(diff._new_queue))
2423
self.assertEqual([], diff._new_item_queue)
2424
2425
def test__read_all_roots_multiple_old(self):
2426
c_map = self.make_two_deep_map()
2427
key1 = c_map.key()
2428
c_map._dump_tree() # load everything
2429
key1_a = c_map._root_node._items['a'].key()
2430
c_map.map(('ccc',), 'new ccc value')
2431
key2 = c_map._save()
2432
key2_a = c_map._root_node._items['a'].key()
2433
c_map.map(('add',), 'new add value')
2434
key3 = c_map._save()
2435
key3_a = c_map._root_node._items['a'].key()
2436
diff = self.get_difference([key3], [key1, key2],
2437
chk_map._search_key_plain)
2438
root_results = [record.key for record in diff._read_all_roots()]
2439
self.assertEqual([key3], root_results)
2440
# the 'a' keys should not be queued up 2 times, since they are
2441
# identical
2442
self.assertEqual([key1_a], diff._old_queue)
2443
self.assertEqual([key3_a], diff._new_queue)
2444
self.assertEqual([], diff._new_item_queue)
2445
2446
def test__process_next_old_batched_no_dupes(self):
2447
c_map = self.make_two_deep_map()
2448
key1 = c_map.key()
2449
c_map._dump_tree() # load everything
2450
key1_a = c_map._root_node._items['a'].key()
2451
key1_aa = c_map._root_node._items['a']._items['aa'].key()
2452
key1_ab = c_map._root_node._items['a']._items['ab'].key()
2453
key1_ac = c_map._root_node._items['a']._items['ac'].key()
2454
key1_ad = c_map._root_node._items['a']._items['ad'].key()
2455
c_map.map(('aaa',), 'new aaa value')
2456
key2 = c_map._save()
2457
key2_a = c_map._root_node._items['a'].key()
2458
key2_aa = c_map._root_node._items['a']._items['aa'].key()
2459
c_map.map(('acc',), 'new acc content')
2460
key3 = c_map._save()
2461
key3_a = c_map._root_node._items['a'].key()
2462
key3_ac = c_map._root_node._items['a']._items['ac'].key()
2463
diff = self.get_difference([key3], [key1, key2],
2464
chk_map._search_key_plain)
2465
root_results = [record.key for record in diff._read_all_roots()]
2466
self.assertEqual([key3], root_results)
2467
self.assertEqual(sorted([key1_a, key2_a]),
2468
sorted(diff._old_queue))
2469
self.assertEqual([key3_a], diff._new_queue)
2470
self.assertEqual([], diff._new_item_queue)
2471
diff._process_next_old()
2472
# All of the old records should be brought in and queued up,
2473
# but we should not have any duplicates
2474
self.assertEqual(sorted([key1_aa, key1_ab, key1_ac, key1_ad, key2_aa]),
2475
sorted(diff._old_queue))
2476
2477
2478
class TestIterInterestingNodes(TestCaseWithExampleMaps):
1896
2479
1897
2480
def get_map_key(self, a_dict, maximum_size=10):
1898
c_map = self._get_map(a_dict, maximum_size=maximum_size,
1899
chk_bytes=self.get_chk_bytes())
2481
c_map = self.get_map(a_dict, maximum_size=maximum_size)
1900
2482
return c_map.key()
1901
2483
1902
def assertIterInteresting(self, expected, interesting_keys,
1903
uninteresting_keys):
2484
def assertIterInteresting(self, records, items, interesting_keys,
2485
old_keys):
1904
2486
"""Check the result of iter_interesting_nodes.
1905
2487
1906
:param expected: A list of (record_keys, interesting_chk_pages,
1907
interesting key value pairs)
2488
Note that we no longer care how many steps are taken, etc, just that
2489
the right contents are returned.
2490
2491
:param records: A list of record keys that should be yielded
2492
:param items: A list of items (key,value) that should be yielded.
1908
2493
"""
1909
2494
store = self.get_chk_bytes()
2495
store._search_key_func = chk_map._search_key_plain
1910
2496
iter_nodes = chk_map.iter_interesting_nodes(store, interesting_keys,
1911
uninteresting_keys)
1912
nodes = list(iter_nodes)
1913
for count, (exp, act) in enumerate(izip(expected, nodes)):
1914
exp_record, exp_items = exp
1915
record, items = act
1916
exp_tuple = (exp_record, sorted(exp_items))
1917
if record is None:
1918
act_tuple = (None, sorted(items))
1919
else:
1920
act_tuple = (record.key, sorted(items))
1921
self.assertEqual(exp_tuple, act_tuple,
1922
'entry %d did not match expected' % count)
1923
self.assertEqual(len(expected), len(nodes))
2497
old_keys)
2498
record_keys = []
2499
all_items = []
2500
for record, new_items in iter_nodes:
2501
if record is not None:
2502
record_keys.append(record.key)
2503
if new_items:
2504
all_items.extend(new_items)
2505
self.assertEqual(sorted(records), sorted(record_keys))
2506
self.assertEqual(sorted(items), sorted(all_items))
1924
2507
1925
2508
def test_empty_to_one_keys(self):
1926
2509
target = self.get_map_key({('a',): 'content'})
1927
self.assertIterInteresting(
1928
[(target, [(('a',), 'content')]),
1929
], [target], [])
2510
self.assertIterInteresting([target],
2511
[(('a',), 'content')],
2512
[target], [])
1930
2513
1931
2514
def test_none_to_one_key(self):
1932
2515
basis = self.get_map_key({})
1933
2516
target = self.get_map_key({('a',): 'content'})
1934
self.assertIterInteresting(
1935
[(None, [(('a',), 'content')]),
1936
(target, []),
1937
], [target], [basis])
2517
self.assertIterInteresting([target],
2518
[(('a',), 'content')],
2519
[target], [basis])
1938
2520
1939
2521
def test_one_to_none_key(self):
1940
2522
basis = self.get_map_key({('a',): 'content'})
1941
2523
target = self.get_map_key({})
1942
self.assertIterInteresting(
1943
[(target, [])],
1944
[target], [basis])
2524
self.assertIterInteresting([target],
2525
[],
2526
[target], [basis])
1945
2527
1946
2528
def test_common_pages(self):
1947
2529
basis = self.get_map_key({('a',): 'content',
1964
2546
target_map._dump_tree())
1965
2547
b_key = target_map._root_node._items['b'].key()
1966
2548
# This should return the root node, and the node for the 'b' key
1967
self.assertIterInteresting(
1968
[(target, []),
1969
(b_key, [(('b',), 'other content')])],
1970
[target], [basis])
2549
self.assertIterInteresting([target, b_key],
2550
[(('b',), 'other content')],
2551
[target], [basis])
1971
2552
1972
2553
def test_common_sub_page(self):
1973
2554
basis = self.get_map_key({('aaa',): 'common',
1991
2572
# The key for the internal aa node
1992
2573
a_key = target_map._root_node._items['a'].key()
1993
2574
# The key for the leaf aab node
2575
# aaa_key = target_map._root_node._items['a']._items['aaa'].key()
1994
2576
aab_key = target_map._root_node._items['a']._items['aab'].key()
1995
self.assertIterInteresting(
1996
[(target, []),
1997
(a_key, []),
1998
(aab_key, [(('aab',), 'new')])],
1999
[target], [basis])
2577
self.assertIterInteresting([target, a_key, aab_key],
2578
[(('aab',), 'new')],
2579
[target], [basis])
2000
2580
2001
2581
def test_common_leaf(self):
2002
2582
basis = self.get_map_key({})
2040
2620
a_key = target3_map._root_node._items['a'].key()
2041
2621
aac_key = target3_map._root_node._items['a']._items['aac'].key()
2042
2622
self.assertIterInteresting(
2043
[(None, [(('aaa',), 'common')]),
2044
(target1, []),
2045
(target2, []),
2046
(target3, []),
2047
(b_key, [(('bbb',), 'new')]),
2048
(a_key, []),
2049
(aac_key, [(('aac',), 'other')]),
2050
], [target1, target2, target3], [basis])
2051
2052
self.assertIterInteresting(
2053
[(target2, []),
2054
(target3, []),
2055
(b_key, [(('bbb',), 'new')]),
2056
(a_key, []),
2057
(aac_key, [(('aac',), 'other')]),
2058
], [target2, target3], [target1])
2059
2060
# This may be a case that we relax. A root node is a deep child of the
2061
# excluded set. The cost is buffering root nodes until we have
2062
# determined all possible exclusions. (Because a prefix of '', cannot
2063
# be excluded.)
2064
self.assertIterInteresting(
2065
[], [target1], [target3])
2623
[target1, target2, target3, a_key, aac_key, b_key],
2624
[(('aaa',), 'common'), (('bbb',), 'new'), (('aac',), 'other')],
2625
[target1, target2, target3], [basis])
2626
2627
self.assertIterInteresting(
2628
[target2, target3, a_key, aac_key, b_key],
2629
[(('bbb',), 'new'), (('aac',), 'other')],
2630
[target2, target3], [target1])
2631
2632
# Technically, target1 could be filtered out, but since it is a root
2633
# node, we yield it immediately, rather than waiting to find out much
2634
# later on.
2635
self.assertIterInteresting(
2636
[target1],
2637
[],
2638
[target1], [target3])
2066
2639
2067
2640
def test_multiple_maps(self):
2068
2641
basis1 = self.get_map_key({('aaa',): 'common',
2111
2684
# The key for the leaf bba node
2112
2685
bba_key = target2_map._root_node._items['b']._items['bba'].key()
2113
2686
self.assertIterInteresting(
2114
[(target1, []),
2115
(target2, []),
2116
(a_key, []),
2117
(b_key, []),
2118
(aac_key, [(('aac',), 'target1')]),
2119
(bba_key, [(('bba',), 'target2')]),
2120
], [target1, target2], [basis1, basis2])
2687
[target1, target2, a_key, aac_key, b_key, bba_key],
2688
[(('aac',), 'target1'), (('bba',), 'target2')],
2689
[target1, target2], [basis1, basis2])
2121
2690
2122
2691
def test_multiple_maps_overlapping_common_new(self):
2123
2692
# Test that when a node found through the interesting_keys iteration
2124
# for *some roots* and also via the uninteresting keys iteration, that
2125
# it is still scanned for uninteresting refs and items, because its
2693
# for *some roots* and also via the old keys iteration, that
2694
# it is still scanned for old refs and items, because its
2126
2695
# not truely new. This requires 2 levels of InternalNodes to expose,
2127
2696
# because of the way the bootstrap in _find_children_info works.
2128
2697
# This suggests that the code is probably amenable to/benefit from
2188
2757
right_map._dump_tree())
2189
2758
# Keys from the right side target - none, the root is enough.
2190
2759
# Test behaviour
2191
self.expectFailure("we don't properly filter different depths",
2192
self.assertIterInteresting,
2193
[(left, []),
2194
(right, []),
2195
(l_d_key, [(('ddd',), 'change')]),
2196
], [left, right], [basis])
2197
2760
self.assertIterInteresting(
2198
[(left, []),
2199
(right, []),
2200
(l_d_key, [(('ddd',), 'change')]),
2201
], [left, right], [basis])
2761
[right, left, l_d_key],
2762
[(('ddd',), 'change')],
2763
[left, right], [basis])
2202
2764
2203
2765
def test_multiple_maps_similar(self):
2204
2766
# We want to have a depth=2 tree, with multiple entries in each leaf
2259
2821
r_a_key = right_map._root_node._items['a'].key()
2260
2822
r_c_key = right_map._root_node._items['c'].key()
2261
2823
self.assertIterInteresting(
2262
[(left, []),
2263
(right, []),
2264
(l_a_key, [(('abb',), 'changed left')]),
2265
(r_c_key, [(('cbb',), 'changed right')]),
2266
], [left, right], [basis])
2824
[right, left, l_a_key, r_c_key],
2825
[(('abb',), 'changed left'), (('cbb',), 'changed right')],
2826
[left, right], [basis])
Loggerhead is a web-based interface for Breezy
Version: 2.0.1