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):
2112
class TestCHKMapDifference(TestCaseWithExampleMaps):
2114
def get_difference(self, new_roots, old_roots,
2115
search_key_func=None):
2116
if search_key_func is None:
2117
search_key_func = chk_map._search_key_plain
2118
return chk_map.CHKMapDifference(self.get_chk_bytes(),
2119
new_roots, old_roots, search_key_func)
2121
def test__init__(self):
2122
c_map = self.make_root_only_map()
2124
c_map.map(('aaa',), 'new aaa content')
2125
key2 = c_map._save()
2126
diff = self.get_difference([key2], [key1])
2127
self.assertEqual(set([key1]), diff._all_old_chks)
2128
self.assertEqual([], diff._old_queue)
2129
self.assertEqual([], diff._new_queue)
2131
def help__read_all_roots(self, search_key_func):
2132
c_map = self.make_root_only_map(search_key_func=search_key_func)
2134
c_map.map(('aaa',), 'new aaa content')
2135
key2 = c_map._save()
2136
diff = self.get_difference([key2], [key1], search_key_func)
2137
root_results = [record.key for record in diff._read_all_roots()]
2138
self.assertEqual([key2], root_results)
2139
# We should have queued up only items that aren't in the old
2141
self.assertEqual([(('aaa',), 'new aaa content')],
2142
diff._new_item_queue)
2143
self.assertEqual([], diff._new_queue)
2144
# And there are no old references, so that queue should be
2146
self.assertEqual([], diff._old_queue)
2148
def test__read_all_roots_plain(self):
2149
self.help__read_all_roots(search_key_func=chk_map._search_key_plain)
2151
def test__read_all_roots_16(self):
2152
self.help__read_all_roots(search_key_func=chk_map._search_key_16)
2154
def test__read_all_roots_skips_known_old(self):
2155
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2157
c_map2 = self.make_root_only_map(chk_map._search_key_plain)
2159
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2160
root_results = [record.key for record in diff._read_all_roots()]
2161
# We should have no results. key2 is completely contained within key1,
2162
# and we should have seen that in the first pass
2163
self.assertEqual([], root_results)
2165
def test__read_all_roots_prepares_queues(self):
2166
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2168
c_map._dump_tree() # load everything
2169
key1_a = c_map._root_node._items['a'].key()
2170
c_map.map(('abb',), 'new abb content')
2171
key2 = c_map._save()
2172
key2_a = c_map._root_node._items['a'].key()
2173
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2174
root_results = [record.key for record in diff._read_all_roots()]
2175
self.assertEqual([key2], root_results)
2176
# At this point, we should have queued up only the 'a' Leaf on both
2177
# sides, both 'c' and 'd' are known to not have changed on both sides
2178
self.assertEqual([key2_a], diff._new_queue)
2179
self.assertEqual([], diff._new_item_queue)
2180
self.assertEqual([key1_a], diff._old_queue)
2182
def test__read_all_roots_multi_new_prepares_queues(self):
2183
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2185
c_map._dump_tree() # load everything
2186
key1_a = c_map._root_node._items['a'].key()
2187
key1_c = c_map._root_node._items['c'].key()
2188
c_map.map(('abb',), 'new abb content')
2189
key2 = c_map._save()
2190
key2_a = c_map._root_node._items['a'].key()
2191
key2_c = c_map._root_node._items['c'].key()
2192
c_map = chk_map.CHKMap(self.get_chk_bytes(), key1,
2193
chk_map._search_key_plain)
2194
c_map.map(('ccc',), 'new ccc content')
2195
key3 = c_map._save()
2196
key3_a = c_map._root_node._items['a'].key()
2197
key3_c = c_map._root_node._items['c'].key()
2198
diff = self.get_difference([key2, key3], [key1],
2199
chk_map._search_key_plain)
2200
root_results = [record.key for record in diff._read_all_roots()]
2201
self.assertEqual(sorted([key2, key3]), sorted(root_results))
2202
# We should have queued up key2_a, and key3_c, but not key2_c or key3_c
2203
self.assertEqual([key2_a, key3_c], diff._new_queue)
2204
self.assertEqual([], diff._new_item_queue)
2205
# And we should have queued up both a and c for the old set
2206
self.assertEqual([key1_a, key1_c], diff._old_queue)
2208
def test__read_all_roots_different_depths(self):
2209
c_map = self.make_two_deep_map(chk_map._search_key_plain)
2210
c_map._dump_tree() # load everything
2212
key1_a = c_map._root_node._items['a'].key()
2213
key1_c = c_map._root_node._items['c'].key()
2214
key1_d = c_map._root_node._items['d'].key()
2216
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2219
key2_aa = c_map2._root_node._items['aa'].key()
2220
key2_ad = c_map2._root_node._items['ad'].key()
2222
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2223
root_results = [record.key for record in diff._read_all_roots()]
2224
self.assertEqual([key2], root_results)
2225
# Only the 'a' subset should be queued up, since 'c' and 'd' cannot be
2227
self.assertEqual([key1_a], diff._old_queue)
2228
self.assertEqual([key2_aa, key2_ad], diff._new_queue)
2229
self.assertEqual([], diff._new_item_queue)
2231
diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2232
root_results = [record.key for record in diff._read_all_roots()]
2233
self.assertEqual([key1], root_results)
2235
self.assertEqual([key2_aa, key2_ad], diff._old_queue)
2236
self.assertEqual([key1_a, key1_c, key1_d], diff._new_queue)
2237
self.assertEqual([], diff._new_item_queue)
2239
def test__read_all_roots_different_depths_16(self):
2240
c_map = self.make_two_deep_map(chk_map._search_key_16)
2241
c_map._dump_tree() # load everything
2243
key1_2 = c_map._root_node._items['2'].key()
2244
key1_4 = c_map._root_node._items['4'].key()
2245
key1_C = c_map._root_node._items['C'].key()
2246
key1_F = c_map._root_node._items['F'].key()
2248
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_16)
2251
key2_F0 = c_map2._root_node._items['F0'].key()
2252
key2_F3 = c_map2._root_node._items['F3'].key()
2253
key2_F4 = c_map2._root_node._items['F4'].key()
2254
key2_FD = c_map2._root_node._items['FD'].key()
2256
diff = self.get_difference([key2], [key1], chk_map._search_key_16)
2257
root_results = [record.key for record in diff._read_all_roots()]
2258
self.assertEqual([key2], root_results)
2259
# Only the subset of keys that may be present should be queued up.
2260
self.assertEqual([key1_F], diff._old_queue)
2261
self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
2262
sorted(diff._new_queue))
2263
self.assertEqual([], diff._new_item_queue)
2265
diff = self.get_difference([key1], [key2], chk_map._search_key_16)
2266
root_results = [record.key for record in diff._read_all_roots()]
2267
self.assertEqual([key1], root_results)
2269
self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
2270
sorted(diff._old_queue))
2271
self.assertEqual(sorted([key1_2, key1_4, key1_C, key1_F]),
2272
sorted(diff._new_queue))
2273
self.assertEqual([], diff._new_item_queue)
2275
def test__read_all_roots_mixed_depth(self):
2276
c_map = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2277
c_map._dump_tree() # load everything
2279
key1_aa = c_map._root_node._items['aa'].key()
2280
key1_ad = c_map._root_node._items['ad'].key()
2282
c_map2 = self.make_one_deep_one_prefix_map(chk_map._search_key_plain)
2285
key2_a = c_map2._root_node._items['a'].key()
2286
key2_b = c_map2._root_node._items['b'].key()
2288
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2289
root_results = [record.key for record in diff._read_all_roots()]
2290
self.assertEqual([key2], root_results)
2291
# 'ad' matches exactly 'a' on the other side, so it should be removed,
2292
# and neither side should have it queued for walking
2293
self.assertEqual([], diff._old_queue)
2294
self.assertEqual([key2_b], diff._new_queue)
2295
self.assertEqual([], diff._new_item_queue)
2297
diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2298
root_results = [record.key for record in diff._read_all_roots()]
2299
self.assertEqual([key1], root_results)
2300
# Note: This is technically not the 'true minimal' set that we could
2301
# use The reason is that 'a' was matched exactly to 'ad' (by sha
2302
# sum). However, the code gets complicated in the case of more
2303
# than one interesting key, so for now, we live with this
2304
# Consider revising, though benchmarking showing it to be a
2305
# real-world issue should be done
2306
self.assertEqual([key2_a], diff._old_queue)
2307
# self.assertEqual([], diff._old_queue)
2308
self.assertEqual([key1_aa], diff._new_queue)
2309
self.assertEqual([], diff._new_item_queue)
2311
def test__read_all_roots_yields_extra_deep_records(self):
2312
# This is slightly controversial, as we will yield a chk page that we
2313
# might later on find out could be filtered out. (If a root node is
2314
# referenced deeper in the old set.)
2315
# However, even with stacking, we always have all chk pages that we
2316
# will need. So as long as we filter out the referenced keys, we'll
2317
# never run into problems.
2318
# This allows us to yield a root node record immediately, without any
2320
c_map = self.make_two_deep_map(chk_map._search_key_plain)
2321
c_map._dump_tree() # load all keys
2323
key1_a = c_map._root_node._items['a'].key()
2324
c_map2 = self.get_map({
2325
('acc',): 'initial acc content',
2326
('ace',): 'initial ace content',
2327
}, maximum_size=100)
2328
self.assertEqualDiff(
2330
" ('acc',) 'initial acc content'\n"
2331
" ('ace',) 'initial ace content'\n",
2332
c_map2._dump_tree())
2334
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2335
root_results = [record.key for record in diff._read_all_roots()]
2336
self.assertEqual([key2], root_results)
2337
# However, even though we have yielded the root node to be fetched,
2338
# we should have enqued all of the chk pages to be walked, so that we
2339
# can find the keys if they are present
2340
self.assertEqual([key1_a], diff._old_queue)
2341
self.assertEqual([(('acc',), 'initial acc content'),
2342
(('ace',), 'initial ace content'),
2343
], diff._new_item_queue)
2345
def test__read_all_roots_multiple_targets(self):
2346
c_map = self.make_root_only_map()
2348
c_map = self.make_one_deep_map()
2351
key2_c = c_map._root_node._items['c'].key()
2352
key2_d = c_map._root_node._items['d'].key()
2353
c_map.map(('ccc',), 'new ccc value')
2354
key3 = c_map._save()
2355
key3_c = c_map._root_node._items['c'].key()
2356
diff = self.get_difference([key2, key3], [key1],
2357
chk_map._search_key_plain)
2358
root_results = [record.key for record in diff._read_all_roots()]
2359
self.assertEqual(sorted([key2, key3]), sorted(root_results))
2360
self.assertEqual([], diff._old_queue)
2361
# the key 'd' is interesting from key2 and key3, but should only be
2362
# entered into the queue 1 time
2363
self.assertEqual(sorted([key2_c, key3_c, key2_d]),
2364
sorted(diff._new_queue))
2365
self.assertEqual([], diff._new_item_queue)
2367
def test__read_all_roots_no_old(self):
2368
# This is the 'initial branch' case. With nothing in the old
2369
# set, we can just queue up all root nodes into interesting queue, and
2370
# then have them fast-path flushed via _flush_new_queue
2371
c_map = self.make_two_deep_map()
2373
diff = self.get_difference([key1], [], chk_map._search_key_plain)
2374
root_results = [record.key for record in diff._read_all_roots()]
2375
self.assertEqual([], root_results)
2376
self.assertEqual([], diff._old_queue)
2377
self.assertEqual([key1], diff._new_queue)
2378
self.assertEqual([], diff._new_item_queue)
2380
c_map2 = self.make_one_deep_map()
2382
diff = self.get_difference([key1, key2], [], chk_map._search_key_plain)
2383
root_results = [record.key for record in diff._read_all_roots()]
2384
self.assertEqual([], root_results)
2385
self.assertEqual([], diff._old_queue)
2386
self.assertEqual(sorted([key1, key2]), sorted(diff._new_queue))
2387
self.assertEqual([], diff._new_item_queue)
2389
def test__read_all_roots_no_old_16(self):
2390
c_map = self.make_two_deep_map(chk_map._search_key_16)
2392
diff = self.get_difference([key1], [], chk_map._search_key_16)
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(chk_map._search_key_16)
2401
diff = self.get_difference([key1, key2], [],
2402
chk_map._search_key_16)
2403
root_results = [record.key for record in diff._read_all_roots()]
2404
self.assertEqual([], root_results)
2405
self.assertEqual([], diff._old_queue)
2406
self.assertEqual(sorted([key1, key2]),
2407
sorted(diff._new_queue))
2408
self.assertEqual([], diff._new_item_queue)
2410
def test__read_all_roots_multiple_old(self):
2411
c_map = self.make_two_deep_map()
2413
c_map._dump_tree() # load everything
2414
key1_a = c_map._root_node._items['a'].key()
2415
c_map.map(('ccc',), 'new ccc value')
2416
key2 = c_map._save()
2417
key2_a = c_map._root_node._items['a'].key()
2418
c_map.map(('add',), 'new add value')
2419
key3 = c_map._save()
2420
key3_a = c_map._root_node._items['a'].key()
2421
diff = self.get_difference([key3], [key1, key2],
2422
chk_map._search_key_plain)
2423
root_results = [record.key for record in diff._read_all_roots()]
2424
self.assertEqual([key3], root_results)
2425
# the 'a' keys should not be queued up 2 times, since they are
2427
self.assertEqual([key1_a], diff._old_queue)
2428
self.assertEqual([key3_a], diff._new_queue)
2429
self.assertEqual([], diff._new_item_queue)
2431
def test__process_next_old_batched_no_dupes(self):
2432
c_map = self.make_two_deep_map()
2434
c_map._dump_tree() # load everything
2435
key1_a = c_map._root_node._items['a'].key()
2436
key1_aa = c_map._root_node._items['a']._items['aa'].key()
2437
key1_ab = c_map._root_node._items['a']._items['ab'].key()
2438
key1_ac = c_map._root_node._items['a']._items['ac'].key()
2439
key1_ad = c_map._root_node._items['a']._items['ad'].key()
2440
c_map.map(('aaa',), 'new aaa value')
2441
key2 = c_map._save()
2442
key2_a = c_map._root_node._items['a'].key()
2443
key2_aa = c_map._root_node._items['a']._items['aa'].key()
2444
c_map.map(('acc',), 'new acc content')
2445
key3 = c_map._save()
2446
key3_a = c_map._root_node._items['a'].key()
2447
key3_ac = c_map._root_node._items['a']._items['ac'].key()
2448
diff = self.get_difference([key3], [key1, key2],
2449
chk_map._search_key_plain)
2450
root_results = [record.key for record in diff._read_all_roots()]
2451
self.assertEqual([key3], root_results)
2452
self.assertEqual(sorted([key1_a, key2_a]),
2453
sorted(diff._old_queue))
2454
self.assertEqual([key3_a], diff._new_queue)
2455
self.assertEqual([], diff._new_item_queue)
2456
diff._process_next_old()
2457
# All of the old records should be brought in and queued up,
2458
# but we should not have any duplicates
2459
self.assertEqual(sorted([key1_aa, key1_ab, key1_ac, key1_ad, key2_aa]),
2460
sorted(diff._old_queue))
2463
class TestIterInterestingNodes(TestCaseWithExampleMaps):
2465
def get_map_key(self, a_dict, maximum_size=10):
2466
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())
2467
1837
return c_map.key()
2469
def assertIterInteresting(self, records, items, interesting_keys,
1839
def assertIterInteresting(self, expected, interesting_keys,
1840
uninteresting_keys):
2471
1841
"""Check the result of iter_interesting_nodes.
2473
Note that we no longer care how many steps are taken, etc, just that
2474
the right contents are returned.
2476
:param records: A list of record keys that should be yielded
2477
: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)
2479
1846
store = self.get_chk_bytes()
2480
store._search_key_func = chk_map._search_key_plain
2481
1847
iter_nodes = chk_map.iter_interesting_nodes(store, interesting_keys,
2485
for record, new_items in iter_nodes:
2486
if record is not None:
2487
record_keys.append(record.key)
2489
all_items.extend(new_items)
2490
self.assertEqual(sorted(records), sorted(record_keys))
2491
self.assertEqual(sorted(items), sorted(all_items))
1849
for count, (exp, act) in enumerate(izip(expected, iter_nodes)):
1850
exp_record_keys, exp_items = exp
1851
records, items = act
1852
exp_tuple = (sorted(exp_record_keys), sorted(exp_items))
1853
act_tuple = (sorted(records.keys()), sorted(items))
1854
self.assertEqual(exp_tuple, act_tuple)
1855
self.assertEqual(len(expected), count + 1)
2493
1857
def test_empty_to_one_keys(self):
2494
1858
target = self.get_map_key({('a',): 'content'})
2495
self.assertIterInteresting([target],
2496
[(('a',), 'content')],
1859
self.assertIterInteresting(
1860
[([target], [(('a',), 'content')])],
2499
1863
def test_none_to_one_key(self):
2500
1864
basis = self.get_map_key({})
2501
1865
target = self.get_map_key({('a',): 'content'})
2502
self.assertIterInteresting([target],
2503
[(('a',), 'content')],
1866
self.assertIterInteresting(
1867
[([target], [(('a',), 'content')])],
2506
1870
def test_one_to_none_key(self):
2507
1871
basis = self.get_map_key({('a',): 'content'})
2508
1872
target = self.get_map_key({})
2509
self.assertIterInteresting([target],
1873
self.assertIterInteresting(
2513
1877
def test_common_pages(self):
2514
1878
basis = self.get_map_key({('a',): 'content',
2669
1976
# The key for the leaf bba node
2670
1977
bba_key = target2_map._root_node._items['b']._items['bba'].key()
2671
1978
self.assertIterInteresting(
2672
[target1, target2, a_key, aac_key, b_key, bba_key],
2673
[(('aac',), 'target1'), (('bba',), 'target2')],
2674
[target1, target2], [basis1, basis2])
2676
def test_multiple_maps_overlapping_common_new(self):
2677
# Test that when a node found through the interesting_keys iteration
2678
# for *some roots* and also via the old keys iteration, that
2679
# it is still scanned for old refs and items, because its
2680
# not truely new. This requires 2 levels of InternalNodes to expose,
2681
# because of the way the bootstrap in _find_children_info works.
2682
# This suggests that the code is probably amenable to/benefit from
2684
# How does this test work?
2685
# 1) We need a second level InternalNode present in a basis tree.
2686
# 2) We need a left side new tree that uses that InternalNode
2687
# 3) We need a right side new tree that does not use that InternalNode
2688
# at all but that has an unchanged *value* that was reachable inside
2690
basis = self.get_map_key({
2691
# InternalNode, unchanged in left:
2694
# Forces an internalNode at 'a'
2697
left = self.get_map_key({
2698
# All of basis unchanged
2702
# And a new top level node so the root key is different
2705
right = self.get_map_key({
2706
# A value that is unchanged from basis and thus should be filtered
2710
basis_map = CHKMap(self.get_chk_bytes(), basis)
2711
self.assertEqualDiff(
2713
" 'a' InternalNode\n"
2715
" ('aaa',) 'left'\n"
2717
" ('abb',) 'right'\n"
2719
" ('ccc',) 'common'\n",
2720
basis_map._dump_tree())
2721
# Get left expected data
2722
left_map = CHKMap(self.get_chk_bytes(), left)
2723
self.assertEqualDiff(
2725
" 'a' InternalNode\n"
2727
" ('aaa',) 'left'\n"
2729
" ('abb',) 'right'\n"
2731
" ('ccc',) 'common'\n"
2733
" ('ddd',) 'change'\n",
2734
left_map._dump_tree())
2735
# Keys from left side target
2736
l_d_key = left_map._root_node._items['d'].key()
2737
# Get right expected data
2738
right_map = CHKMap(self.get_chk_bytes(), right)
2739
self.assertEqualDiff(
2741
" ('abb',) 'right'\n",
2742
right_map._dump_tree())
2743
# Keys from the right side target - none, the root is enough.
2745
self.assertIterInteresting(
2746
[right, left, l_d_key],
2747
[(('ddd',), 'change')],
2748
[left, right], [basis])
2750
def test_multiple_maps_similar(self):
2751
# We want to have a depth=2 tree, with multiple entries in each leaf
2753
basis = self.get_map_key({
2754
('aaa',): 'unchanged',
2755
('abb',): 'will change left',
2756
('caa',): 'unchanged',
2757
('cbb',): 'will change right',
2759
left = self.get_map_key({
2760
('aaa',): 'unchanged',
2761
('abb',): 'changed left',
2762
('caa',): 'unchanged',
2763
('cbb',): 'will change right',
2765
right = self.get_map_key({
2766
('aaa',): 'unchanged',
2767
('abb',): 'will change left',
2768
('caa',): 'unchanged',
2769
('cbb',): 'changed right',
2771
basis_map = CHKMap(self.get_chk_bytes(), basis)
2772
self.assertEqualDiff(
2775
" ('aaa',) 'unchanged'\n"
2776
" ('abb',) 'will change left'\n"
2778
" ('caa',) 'unchanged'\n"
2779
" ('cbb',) 'will change right'\n",
2780
basis_map._dump_tree())
2781
# Get left expected data
2782
left_map = CHKMap(self.get_chk_bytes(), left)
2783
self.assertEqualDiff(
2786
" ('aaa',) 'unchanged'\n"
2787
" ('abb',) 'changed left'\n"
2789
" ('caa',) 'unchanged'\n"
2790
" ('cbb',) 'will change right'\n",
2791
left_map._dump_tree())
2792
# Keys from left side target
2793
l_a_key = left_map._root_node._items['a'].key()
2794
l_c_key = left_map._root_node._items['c'].key()
2795
# Get right expected data
2796
right_map = CHKMap(self.get_chk_bytes(), right)
2797
self.assertEqualDiff(
2800
" ('aaa',) 'unchanged'\n"
2801
" ('abb',) 'will change left'\n"
2803
" ('caa',) 'unchanged'\n"
2804
" ('cbb',) 'changed right'\n",
2805
right_map._dump_tree())
2806
r_a_key = right_map._root_node._items['a'].key()
2807
r_c_key = right_map._root_node._items['c'].key()
2808
self.assertIterInteresting(
2809
[right, left, l_a_key, r_c_key],
2810
[(('abb',), 'changed left'), (('cbb',), 'changed right')],
2811
[left, right], [basis])
1979
[([target1, target2], []),
1982
([aac_key], [(('aac',), 'target1')]),
1983
([bba_key], [(('bba',), 'target2')]),
1984
], [target1, target2], [basis1, basis2])
added
removed
bzrlib/tests/test_chk_map.py
