96
87
return dict(node.iteritems(*args))
99
class TestCaseWithExampleMaps(TestCaseWithStore):
101
def get_chk_bytes(self):
102
if getattr(self, '_chk_bytes', None) is None:
103
self._chk_bytes = super(TestCaseWithExampleMaps,
104
self).get_chk_bytes()
105
return self._chk_bytes
107
def get_map(self, a_dict, maximum_size=100, search_key_func=None):
108
c_map = self._get_map(a_dict, maximum_size=maximum_size,
109
chk_bytes=self.get_chk_bytes(),
110
search_key_func=search_key_func)
113
def make_root_only_map(self, search_key_func=None):
114
return self.get_map({
115
('aaa',): 'initial aaa content',
116
('abb',): 'initial abb content',
117
}, search_key_func=search_key_func)
119
def make_root_only_aaa_ddd_map(self, search_key_func=None):
120
return self.get_map({
121
('aaa',): 'initial aaa content',
122
('ddd',): 'initial ddd content',
123
}, search_key_func=search_key_func)
125
def make_one_deep_map(self, search_key_func=None):
126
# Same as root_only_map, except it forces an InternalNode at the root
127
return self.get_map({
128
('aaa',): 'initial aaa content',
129
('abb',): 'initial abb content',
130
('ccc',): 'initial ccc content',
131
('ddd',): 'initial ddd content',
132
}, search_key_func=search_key_func)
134
def make_two_deep_map(self, search_key_func=None):
135
# Carefully chosen so that it creates a 2-deep map for both
136
# _search_key_plain and for _search_key_16
137
# Also so that things line up with make_one_deep_two_prefix_map
138
return self.get_map({
139
('aaa',): 'initial aaa content',
140
('abb',): 'initial abb content',
141
('acc',): 'initial acc content',
142
('ace',): 'initial ace content',
143
('add',): 'initial add content',
144
('adh',): 'initial adh content',
145
('adl',): 'initial adl content',
146
('ccc',): 'initial ccc content',
147
('ddd',): 'initial ddd content',
148
}, search_key_func=search_key_func)
150
def make_one_deep_two_prefix_map(self, search_key_func=None):
151
"""Create a map with one internal node, but references are extra long.
153
Otherwise has similar content to make_two_deep_map.
155
return self.get_map({
156
('aaa',): 'initial aaa content',
157
('add',): 'initial add content',
158
('adh',): 'initial adh content',
159
('adl',): 'initial adl content',
160
}, search_key_func=search_key_func)
162
def make_one_deep_one_prefix_map(self, search_key_func=None):
163
"""Create a map with one internal node, but references are extra long.
165
Similar to make_one_deep_two_prefix_map, except the split is at the
166
first char, rather than the second.
168
return self.get_map({
169
('add',): 'initial add content',
170
('adh',): 'initial adh content',
171
('adl',): 'initial adl content',
172
('bbb',): 'initial bbb content',
173
}, search_key_func=search_key_func)
176
class TestTestCaseWithExampleMaps(TestCaseWithExampleMaps):
177
"""Actual tests for the provided examples."""
179
def test_root_only_map_plain(self):
180
c_map = self.make_root_only_map()
181
self.assertEqualDiff(
183
" ('aaa',) 'initial aaa content'\n"
184
" ('abb',) 'initial abb content'\n",
187
def test_root_only_map_16(self):
188
c_map = self.make_root_only_map(search_key_func=chk_map._search_key_16)
189
self.assertEqualDiff(
191
" ('aaa',) 'initial aaa content'\n"
192
" ('abb',) 'initial abb content'\n",
195
def test_one_deep_map_plain(self):
196
c_map = self.make_one_deep_map()
197
self.assertEqualDiff(
200
" ('aaa',) 'initial aaa content'\n"
201
" ('abb',) 'initial abb content'\n"
203
" ('ccc',) 'initial ccc content'\n"
205
" ('ddd',) 'initial ddd content'\n",
208
def test_one_deep_map_16(self):
209
c_map = self.make_one_deep_map(search_key_func=chk_map._search_key_16)
210
self.assertEqualDiff(
213
" ('ccc',) 'initial ccc content'\n"
215
" ('abb',) 'initial abb content'\n"
217
" ('aaa',) 'initial aaa content'\n"
218
" ('ddd',) 'initial ddd content'\n",
221
def test_root_only_aaa_ddd_plain(self):
222
c_map = self.make_root_only_aaa_ddd_map()
223
self.assertEqualDiff(
225
" ('aaa',) 'initial aaa content'\n"
226
" ('ddd',) 'initial ddd content'\n",
229
def test_one_deep_map_16(self):
230
c_map = self.make_root_only_aaa_ddd_map(
231
search_key_func=chk_map._search_key_16)
232
# We use 'aaa' and 'ddd' because they happen to map to 'F' when using
234
self.assertEqualDiff(
236
" ('aaa',) 'initial aaa content'\n"
237
" ('ddd',) 'initial ddd content'\n",
240
def test_two_deep_map_plain(self):
241
c_map = self.make_two_deep_map()
242
self.assertEqualDiff(
244
" 'a' InternalNode\n"
246
" ('aaa',) 'initial aaa content'\n"
248
" ('abb',) 'initial abb content'\n"
250
" ('acc',) 'initial acc content'\n"
251
" ('ace',) 'initial ace content'\n"
253
" ('add',) 'initial add content'\n"
254
" ('adh',) 'initial adh content'\n"
255
" ('adl',) 'initial adl content'\n"
257
" ('ccc',) 'initial ccc content'\n"
259
" ('ddd',) 'initial ddd content'\n",
262
def test_two_deep_map_16(self):
263
c_map = self.make_two_deep_map(search_key_func=chk_map._search_key_16)
264
self.assertEqualDiff(
267
" ('acc',) 'initial acc content'\n"
268
" ('ccc',) 'initial ccc content'\n"
270
" ('abb',) 'initial abb content'\n"
272
" ('ace',) 'initial ace content'\n"
273
" 'F' InternalNode\n"
275
" ('aaa',) 'initial aaa content'\n"
277
" ('adl',) 'initial adl content'\n"
279
" ('adh',) 'initial adh content'\n"
281
" ('ddd',) 'initial ddd content'\n"
283
" ('add',) 'initial add content'\n",
286
def test_one_deep_two_prefix_map_plain(self):
287
c_map = self.make_one_deep_two_prefix_map()
288
self.assertEqualDiff(
291
" ('aaa',) 'initial aaa content'\n"
293
" ('add',) 'initial add content'\n"
294
" ('adh',) 'initial adh content'\n"
295
" ('adl',) 'initial adl content'\n",
298
def test_one_deep_two_prefix_map_16(self):
299
c_map = self.make_one_deep_two_prefix_map(
300
search_key_func=chk_map._search_key_16)
301
self.assertEqualDiff(
304
" ('aaa',) 'initial aaa content'\n"
306
" ('adl',) 'initial adl content'\n"
308
" ('adh',) 'initial adh content'\n"
310
" ('add',) 'initial add content'\n",
313
def test_one_deep_one_prefix_map_plain(self):
314
c_map = self.make_one_deep_one_prefix_map()
315
self.assertEqualDiff(
318
" ('add',) 'initial add content'\n"
319
" ('adh',) 'initial adh content'\n"
320
" ('adl',) 'initial adl content'\n"
322
" ('bbb',) 'initial bbb content'\n",
325
def test_one_deep_one_prefix_map_16(self):
326
c_map = self.make_one_deep_one_prefix_map(
327
search_key_func=chk_map._search_key_16)
328
self.assertEqualDiff(
331
" ('bbb',) 'initial bbb content'\n"
333
" ('add',) 'initial add content'\n"
334
" ('adh',) 'initial adh content'\n"
335
" ('adl',) 'initial adl content'\n",
339
90
class TestMap(TestCaseWithStore):
341
92
def assertHasABMap(self, chk_bytes):
2131
class TestCHKMapDifference(TestCaseWithExampleMaps):
2133
def get_difference(self, new_roots, old_roots,
2134
search_key_func=None):
2135
if search_key_func is None:
2136
search_key_func = chk_map._search_key_plain
2137
return chk_map.CHKMapDifference(self.get_chk_bytes(),
2138
new_roots, old_roots, search_key_func)
2140
def test__init__(self):
2141
c_map = self.make_root_only_map()
2143
c_map.map(('aaa',), 'new aaa content')
2144
key2 = c_map._save()
2145
diff = self.get_difference([key2], [key1])
2146
self.assertEqual(set([key1]), diff._all_old_chks)
2147
self.assertEqual([], diff._old_queue)
2148
self.assertEqual([], diff._new_queue)
2150
def help__read_all_roots(self, search_key_func):
2151
c_map = self.make_root_only_map(search_key_func=search_key_func)
2153
c_map.map(('aaa',), 'new aaa content')
2154
key2 = c_map._save()
2155
diff = self.get_difference([key2], [key1], search_key_func)
2156
root_results = [record.key for record in diff._read_all_roots()]
2157
self.assertEqual([key2], root_results)
2158
# We should have queued up only items that aren't in the old
2160
self.assertEqual([(('aaa',), 'new aaa content')],
2161
diff._new_item_queue)
2162
self.assertEqual([], diff._new_queue)
2163
# And there are no old references, so that queue should be
2165
self.assertEqual([], diff._old_queue)
2167
def test__read_all_roots_plain(self):
2168
self.help__read_all_roots(search_key_func=chk_map._search_key_plain)
2170
def test__read_all_roots_16(self):
2171
self.help__read_all_roots(search_key_func=chk_map._search_key_16)
2173
def test__read_all_roots_skips_known_old(self):
2174
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2176
c_map2 = self.make_root_only_map(chk_map._search_key_plain)
2178
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2179
root_results = [record.key for record in diff._read_all_roots()]
2180
# We should have no results. key2 is completely contained within key1,
2181
# and we should have seen that in the first pass
2182
self.assertEqual([], root_results)
2184
def test__read_all_roots_prepares_queues(self):
2185
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2187
c_map._dump_tree() # load everything
2188
key1_a = c_map._root_node._items['a'].key()
2189
c_map.map(('abb',), 'new abb content')
2190
key2 = c_map._save()
2191
key2_a = c_map._root_node._items['a'].key()
2192
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2193
root_results = [record.key for record in diff._read_all_roots()]
2194
self.assertEqual([key2], root_results)
2195
# At this point, we should have queued up only the 'a' Leaf on both
2196
# sides, both 'c' and 'd' are known to not have changed on both sides
2197
self.assertEqual([key2_a], diff._new_queue)
2198
self.assertEqual([], diff._new_item_queue)
2199
self.assertEqual([key1_a], diff._old_queue)
2201
def test__read_all_roots_multi_new_prepares_queues(self):
2202
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2204
c_map._dump_tree() # load everything
2205
key1_a = c_map._root_node._items['a'].key()
2206
key1_c = c_map._root_node._items['c'].key()
2207
c_map.map(('abb',), 'new abb content')
2208
key2 = c_map._save()
2209
key2_a = c_map._root_node._items['a'].key()
2210
key2_c = c_map._root_node._items['c'].key()
2211
c_map = chk_map.CHKMap(self.get_chk_bytes(), key1,
2212
chk_map._search_key_plain)
2213
c_map.map(('ccc',), 'new ccc content')
2214
key3 = c_map._save()
2215
key3_a = c_map._root_node._items['a'].key()
2216
key3_c = c_map._root_node._items['c'].key()
2217
diff = self.get_difference([key2, key3], [key1],
2218
chk_map._search_key_plain)
2219
root_results = [record.key for record in diff._read_all_roots()]
2220
self.assertEqual(sorted([key2, key3]), sorted(root_results))
2221
# We should have queued up key2_a, and key3_c, but not key2_c or key3_c
2222
self.assertEqual([key2_a, key3_c], diff._new_queue)
2223
self.assertEqual([], diff._new_item_queue)
2224
# And we should have queued up both a and c for the old set
2225
self.assertEqual([key1_a, key1_c], diff._old_queue)
2227
def test__read_all_roots_different_depths(self):
2228
c_map = self.make_two_deep_map(chk_map._search_key_plain)
2229
c_map._dump_tree() # load everything
2231
key1_a = c_map._root_node._items['a'].key()
2232
key1_c = c_map._root_node._items['c'].key()
2233
key1_d = c_map._root_node._items['d'].key()
2235
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2238
key2_aa = c_map2._root_node._items['aa'].key()
2239
key2_ad = c_map2._root_node._items['ad'].key()
2241
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2242
root_results = [record.key for record in diff._read_all_roots()]
2243
self.assertEqual([key2], root_results)
2244
# Only the 'a' subset should be queued up, since 'c' and 'd' cannot be
2246
self.assertEqual([key1_a], diff._old_queue)
2247
self.assertEqual([key2_aa, key2_ad], diff._new_queue)
2248
self.assertEqual([], diff._new_item_queue)
2250
diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2251
root_results = [record.key for record in diff._read_all_roots()]
2252
self.assertEqual([key1], root_results)
2254
self.assertEqual([key2_aa, key2_ad], diff._old_queue)
2255
self.assertEqual([key1_a, key1_c, key1_d], diff._new_queue)
2256
self.assertEqual([], diff._new_item_queue)
2258
def test__read_all_roots_different_depths_16(self):
2259
c_map = self.make_two_deep_map(chk_map._search_key_16)
2260
c_map._dump_tree() # load everything
2262
key1_2 = c_map._root_node._items['2'].key()
2263
key1_4 = c_map._root_node._items['4'].key()
2264
key1_C = c_map._root_node._items['C'].key()
2265
key1_F = c_map._root_node._items['F'].key()
2267
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_16)
2270
key2_F0 = c_map2._root_node._items['F0'].key()
2271
key2_F3 = c_map2._root_node._items['F3'].key()
2272
key2_F4 = c_map2._root_node._items['F4'].key()
2273
key2_FD = c_map2._root_node._items['FD'].key()
2275
diff = self.get_difference([key2], [key1], chk_map._search_key_16)
2276
root_results = [record.key for record in diff._read_all_roots()]
2277
self.assertEqual([key2], root_results)
2278
# Only the subset of keys that may be present should be queued up.
2279
self.assertEqual([key1_F], diff._old_queue)
2280
self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
2281
sorted(diff._new_queue))
2282
self.assertEqual([], diff._new_item_queue)
2284
diff = self.get_difference([key1], [key2], chk_map._search_key_16)
2285
root_results = [record.key for record in diff._read_all_roots()]
2286
self.assertEqual([key1], root_results)
2288
self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
2289
sorted(diff._old_queue))
2290
self.assertEqual(sorted([key1_2, key1_4, key1_C, key1_F]),
2291
sorted(diff._new_queue))
2292
self.assertEqual([], diff._new_item_queue)
2294
def test__read_all_roots_mixed_depth(self):
2295
c_map = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2296
c_map._dump_tree() # load everything
2298
key1_aa = c_map._root_node._items['aa'].key()
2299
key1_ad = c_map._root_node._items['ad'].key()
2301
c_map2 = self.make_one_deep_one_prefix_map(chk_map._search_key_plain)
2304
key2_a = c_map2._root_node._items['a'].key()
2305
key2_b = c_map2._root_node._items['b'].key()
2307
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2308
root_results = [record.key for record in diff._read_all_roots()]
2309
self.assertEqual([key2], root_results)
2310
# 'ad' matches exactly 'a' on the other side, so it should be removed,
2311
# and neither side should have it queued for walking
2312
self.assertEqual([], diff._old_queue)
2313
self.assertEqual([key2_b], diff._new_queue)
2314
self.assertEqual([], diff._new_item_queue)
2316
diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2317
root_results = [record.key for record in diff._read_all_roots()]
2318
self.assertEqual([key1], root_results)
2319
# Note: This is technically not the 'true minimal' set that we could
2320
# use The reason is that 'a' was matched exactly to 'ad' (by sha
2321
# sum). However, the code gets complicated in the case of more
2322
# than one interesting key, so for now, we live with this
2323
# Consider revising, though benchmarking showing it to be a
2324
# real-world issue should be done
2325
self.assertEqual([key2_a], diff._old_queue)
2326
# self.assertEqual([], diff._old_queue)
2327
self.assertEqual([key1_aa], diff._new_queue)
2328
self.assertEqual([], diff._new_item_queue)
2330
def test__read_all_roots_yields_extra_deep_records(self):
2331
# This is slightly controversial, as we will yield a chk page that we
2332
# might later on find out could be filtered out. (If a root node is
2333
# referenced deeper in the old set.)
2334
# However, even with stacking, we always have all chk pages that we
2335
# will need. So as long as we filter out the referenced keys, we'll
2336
# never run into problems.
2337
# This allows us to yield a root node record immediately, without any
2339
c_map = self.make_two_deep_map(chk_map._search_key_plain)
2340
c_map._dump_tree() # load all keys
2342
key1_a = c_map._root_node._items['a'].key()
2343
c_map2 = self.get_map({
2344
('acc',): 'initial acc content',
2345
('ace',): 'initial ace content',
2346
}, maximum_size=100)
2347
self.assertEqualDiff(
2349
" ('acc',) 'initial acc content'\n"
2350
" ('ace',) 'initial ace content'\n",
2351
c_map2._dump_tree())
2353
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2354
root_results = [record.key for record in diff._read_all_roots()]
2355
self.assertEqual([key2], root_results)
2356
# However, even though we have yielded the root node to be fetched,
2357
# we should have enqued all of the chk pages to be walked, so that we
2358
# can find the keys if they are present
2359
self.assertEqual([key1_a], diff._old_queue)
2360
self.assertEqual([(('acc',), 'initial acc content'),
2361
(('ace',), 'initial ace content'),
2362
], diff._new_item_queue)
2364
def test__read_all_roots_multiple_targets(self):
2365
c_map = self.make_root_only_map()
2367
c_map = self.make_one_deep_map()
2370
key2_c = c_map._root_node._items['c'].key()
2371
key2_d = c_map._root_node._items['d'].key()
2372
c_map.map(('ccc',), 'new ccc value')
2373
key3 = c_map._save()
2374
key3_c = c_map._root_node._items['c'].key()
2375
diff = self.get_difference([key2, key3], [key1],
2376
chk_map._search_key_plain)
2377
root_results = [record.key for record in diff._read_all_roots()]
2378
self.assertEqual(sorted([key2, key3]), sorted(root_results))
2379
self.assertEqual([], diff._old_queue)
2380
# the key 'd' is interesting from key2 and key3, but should only be
2381
# entered into the queue 1 time
2382
self.assertEqual(sorted([key2_c, key3_c, key2_d]),
2383
sorted(diff._new_queue))
2384
self.assertEqual([], diff._new_item_queue)
2386
def test__read_all_roots_no_old(self):
2387
# This is the 'initial branch' case. With nothing in the old
2388
# set, we can just queue up all root nodes into interesting queue, and
2389
# then have them fast-path flushed via _flush_new_queue
2390
c_map = self.make_two_deep_map()
2392
diff = self.get_difference([key1], [], chk_map._search_key_plain)
2393
root_results = [record.key for record in diff._read_all_roots()]
2394
self.assertEqual([], root_results)
2395
self.assertEqual([], diff._old_queue)
2396
self.assertEqual([key1], diff._new_queue)
2397
self.assertEqual([], diff._new_item_queue)
2399
c_map2 = self.make_one_deep_map()
2401
diff = self.get_difference([key1, key2], [], chk_map._search_key_plain)
2402
root_results = [record.key for record in diff._read_all_roots()]
2403
self.assertEqual([], root_results)
2404
self.assertEqual([], diff._old_queue)
2405
self.assertEqual(sorted([key1, key2]), sorted(diff._new_queue))
2406
self.assertEqual([], diff._new_item_queue)
2408
def test__read_all_roots_no_old_16(self):
2409
c_map = self.make_two_deep_map(chk_map._search_key_16)
2411
diff = self.get_difference([key1], [], chk_map._search_key_16)
2412
root_results = [record.key for record in diff._read_all_roots()]
2413
self.assertEqual([], root_results)
2414
self.assertEqual([], diff._old_queue)
2415
self.assertEqual([key1], diff._new_queue)
2416
self.assertEqual([], diff._new_item_queue)
2418
c_map2 = self.make_one_deep_map(chk_map._search_key_16)
2420
diff = self.get_difference([key1, key2], [],
2421
chk_map._search_key_16)
2422
root_results = [record.key for record in diff._read_all_roots()]
2423
self.assertEqual([], root_results)
2424
self.assertEqual([], diff._old_queue)
2425
self.assertEqual(sorted([key1, key2]),
2426
sorted(diff._new_queue))
2427
self.assertEqual([], diff._new_item_queue)
2429
def test__read_all_roots_multiple_old(self):
2430
c_map = self.make_two_deep_map()
2432
c_map._dump_tree() # load everything
2433
key1_a = c_map._root_node._items['a'].key()
2434
c_map.map(('ccc',), 'new ccc value')
2435
key2 = c_map._save()
2436
key2_a = c_map._root_node._items['a'].key()
2437
c_map.map(('add',), 'new add value')
2438
key3 = c_map._save()
2439
key3_a = c_map._root_node._items['a'].key()
2440
diff = self.get_difference([key3], [key1, key2],
2441
chk_map._search_key_plain)
2442
root_results = [record.key for record in diff._read_all_roots()]
2443
self.assertEqual([key3], root_results)
2444
# the 'a' keys should not be queued up 2 times, since they are
2446
self.assertEqual([key1_a], diff._old_queue)
2447
self.assertEqual([key3_a], diff._new_queue)
2448
self.assertEqual([], diff._new_item_queue)
2450
def test__process_next_old_batched_no_dupes(self):
2451
c_map = self.make_two_deep_map()
2453
c_map._dump_tree() # load everything
2454
key1_a = c_map._root_node._items['a'].key()
2455
key1_aa = c_map._root_node._items['a']._items['aa'].key()
2456
key1_ab = c_map._root_node._items['a']._items['ab'].key()
2457
key1_ac = c_map._root_node._items['a']._items['ac'].key()
2458
key1_ad = c_map._root_node._items['a']._items['ad'].key()
2459
c_map.map(('aaa',), 'new aaa value')
2460
key2 = c_map._save()
2461
key2_a = c_map._root_node._items['a'].key()
2462
key2_aa = c_map._root_node._items['a']._items['aa'].key()
2463
c_map.map(('acc',), 'new acc content')
2464
key3 = c_map._save()
2465
key3_a = c_map._root_node._items['a'].key()
2466
key3_ac = c_map._root_node._items['a']._items['ac'].key()
2467
diff = self.get_difference([key3], [key1, key2],
2468
chk_map._search_key_plain)
2469
root_results = [record.key for record in diff._read_all_roots()]
2470
self.assertEqual([key3], root_results)
2471
self.assertEqual(sorted([key1_a, key2_a]),
2472
sorted(diff._old_queue))
2473
self.assertEqual([key3_a], diff._new_queue)
2474
self.assertEqual([], diff._new_item_queue)
2475
diff._process_next_old()
2476
# All of the old records should be brought in and queued up,
2477
# but we should not have any duplicates
2478
self.assertEqual(sorted([key1_aa, key1_ab, key1_ac, key1_ad, key2_aa]),
2479
sorted(diff._old_queue))
2482
class TestIterInterestingNodes(TestCaseWithExampleMaps):
2484
def get_map_key(self, a_dict, maximum_size=10):
2485
c_map = self.get_map(a_dict, maximum_size=maximum_size)
1826
class TestIterInterestingNodes(TestCaseWithStore):
1828
def get_chk_bytes(self):
1829
if getattr(self, '_chk_bytes', None) is None:
1830
self._chk_bytes = super(TestIterInterestingNodes,
1831
self).get_chk_bytes()
1832
return self._chk_bytes
1834
def get_map_key(self, a_dict):
1835
c_map = self._get_map(a_dict, maximum_size=10,
1836
chk_bytes=self.get_chk_bytes())
2486
1837
return c_map.key()
2488
def assertIterInteresting(self, records, items, interesting_keys,
1839
def assertIterInteresting(self, expected, interesting_keys,
1840
uninteresting_keys):
2490
1841
"""Check the result of iter_interesting_nodes.
2492
Note that we no longer care how many steps are taken, etc, just that
2493
the right contents are returned.
2495
:param records: A list of record keys that should be yielded
2496
:param items: A list of items (key,value) that should be yielded.
1843
:param expected: A list of (record_keys, interesting_chk_pages,
1844
interesting key value pairs)
2498
1846
store = self.get_chk_bytes()
2499
store._search_key_func = chk_map._search_key_plain
2500
1847
iter_nodes = chk_map.iter_interesting_nodes(store, interesting_keys,
2504
for record, new_items in iter_nodes:
2505
if record is not None:
2506
record_keys.append(record.key)
2508
all_items.extend(new_items)
2509
self.assertEqual(sorted(records), sorted(record_keys))
2510
self.assertEqual(sorted(items), sorted(all_items))
1849
nodes = list(iter_nodes)
1850
for count, (exp, act) in enumerate(izip(expected, nodes)):
1851
exp_record, exp_items = exp
1853
exp_tuple = (exp_record, sorted(exp_items))
1855
act_tuple = (None, sorted(items))
1857
act_tuple = (record.key, sorted(items))
1858
self.assertEqual(exp_tuple, act_tuple,
1859
'entry %d did not match expected' % count)
1860
self.assertEqual(len(expected), len(nodes))
2512
1862
def test_empty_to_one_keys(self):
2513
1863
target = self.get_map_key({('a',): 'content'})
2514
self.assertIterInteresting([target],
2515
[(('a',), 'content')],
1864
self.assertIterInteresting(
1865
[(target, [(('a',), 'content')]),
2518
1868
def test_none_to_one_key(self):
2519
1869
basis = self.get_map_key({})
2520
1870
target = self.get_map_key({('a',): 'content'})
2521
self.assertIterInteresting([target],
2522
[(('a',), 'content')],
1871
self.assertIterInteresting(
1872
[(None, [(('a',), 'content')]),
1874
], [target], [basis])
2525
1876
def test_one_to_none_key(self):
2526
1877
basis = self.get_map_key({('a',): 'content'})
2527
1878
target = self.get_map_key({})
2528
self.assertIterInteresting([target],
1879
self.assertIterInteresting(
2532
1883
def test_common_pages(self):
2533
1884
basis = self.get_map_key({('a',): 'content',
2688
2048
# The key for the leaf bba node
2689
2049
bba_key = target2_map._root_node._items['b']._items['bba'].key()
2690
2050
self.assertIterInteresting(
2691
[target1, target2, a_key, aac_key, b_key, bba_key],
2692
[(('aac',), 'target1'), (('bba',), 'target2')],
2693
[target1, target2], [basis1, basis2])
2695
def test_multiple_maps_overlapping_common_new(self):
2696
# Test that when a node found through the interesting_keys iteration
2697
# for *some roots* and also via the old keys iteration, that
2698
# it is still scanned for old refs and items, because its
2699
# not truely new. This requires 2 levels of InternalNodes to expose,
2700
# because of the way the bootstrap in _find_children_info works.
2701
# This suggests that the code is probably amenable to/benefit from
2703
# How does this test work?
2704
# 1) We need a second level InternalNode present in a basis tree.
2705
# 2) We need a left side new tree that uses that InternalNode
2706
# 3) We need a right side new tree that does not use that InternalNode
2707
# at all but that has an unchanged *value* that was reachable inside
2709
basis = self.get_map_key({
2710
# InternalNode, unchanged in left:
2713
# Forces an internalNode at 'a'
2716
left = self.get_map_key({
2717
# All of basis unchanged
2721
# And a new top level node so the root key is different
2724
right = self.get_map_key({
2725
# A value that is unchanged from basis and thus should be filtered
2729
basis_map = CHKMap(self.get_chk_bytes(), basis)
2730
self.assertEqualDiff(
2732
" 'a' InternalNode\n"
2734
" ('aaa',) 'left'\n"
2736
" ('abb',) 'right'\n"
2738
" ('ccc',) 'common'\n",
2739
basis_map._dump_tree())
2740
# Get left expected data
2741
left_map = CHKMap(self.get_chk_bytes(), left)
2742
self.assertEqualDiff(
2744
" 'a' InternalNode\n"
2746
" ('aaa',) 'left'\n"
2748
" ('abb',) 'right'\n"
2750
" ('ccc',) 'common'\n"
2752
" ('ddd',) 'change'\n",
2753
left_map._dump_tree())
2754
# Keys from left side target
2755
l_d_key = left_map._root_node._items['d'].key()
2756
# Get right expected data
2757
right_map = CHKMap(self.get_chk_bytes(), right)
2758
self.assertEqualDiff(
2760
" ('abb',) 'right'\n",
2761
right_map._dump_tree())
2762
# Keys from the right side target - none, the root is enough.
2764
self.assertIterInteresting(
2765
[right, left, l_d_key],
2766
[(('ddd',), 'change')],
2767
[left, right], [basis])
2769
def test_multiple_maps_similar(self):
2770
# We want to have a depth=2 tree, with multiple entries in each leaf
2772
basis = self.get_map_key({
2773
('aaa',): 'unchanged',
2774
('abb',): 'will change left',
2775
('caa',): 'unchanged',
2776
('cbb',): 'will change right',
2778
left = self.get_map_key({
2779
('aaa',): 'unchanged',
2780
('abb',): 'changed left',
2781
('caa',): 'unchanged',
2782
('cbb',): 'will change right',
2784
right = self.get_map_key({
2785
('aaa',): 'unchanged',
2786
('abb',): 'will change left',
2787
('caa',): 'unchanged',
2788
('cbb',): 'changed right',
2790
basis_map = CHKMap(self.get_chk_bytes(), basis)
2791
self.assertEqualDiff(
2794
" ('aaa',) 'unchanged'\n"
2795
" ('abb',) 'will change left'\n"
2797
" ('caa',) 'unchanged'\n"
2798
" ('cbb',) 'will change right'\n",
2799
basis_map._dump_tree())
2800
# Get left expected data
2801
left_map = CHKMap(self.get_chk_bytes(), left)
2802
self.assertEqualDiff(
2805
" ('aaa',) 'unchanged'\n"
2806
" ('abb',) 'changed left'\n"
2808
" ('caa',) 'unchanged'\n"
2809
" ('cbb',) 'will change right'\n",
2810
left_map._dump_tree())
2811
# Keys from left side target
2812
l_a_key = left_map._root_node._items['a'].key()
2813
l_c_key = left_map._root_node._items['c'].key()
2814
# Get right expected data
2815
right_map = CHKMap(self.get_chk_bytes(), right)
2816
self.assertEqualDiff(
2819
" ('aaa',) 'unchanged'\n"
2820
" ('abb',) 'will change left'\n"
2822
" ('caa',) 'unchanged'\n"
2823
" ('cbb',) 'changed right'\n",
2824
right_map._dump_tree())
2825
r_a_key = right_map._root_node._items['a'].key()
2826
r_c_key = right_map._root_node._items['c'].key()
2827
self.assertIterInteresting(
2828
[right, left, l_a_key, r_c_key],
2829
[(('abb',), 'changed left'), (('cbb',), 'changed right')],
2830
[left, right], [basis])
2055
(aac_key, [(('aac',), 'target1')]),
2056
(bba_key, [(('bba',), 'target2')]),
2057
], [target1, target2], [basis1, basis2])
added
removed
bzrlib/tests/test_chk_map.py
