94
92
return dict(node.iteritems(*args))
97
class TestCaseWithExampleMaps(TestCaseWithStore):
99
def get_chk_bytes(self):
100
if getattr(self, '_chk_bytes', None) is None:
101
self._chk_bytes = super(TestCaseWithExampleMaps,
102
self).get_chk_bytes()
103
return self._chk_bytes
105
def get_map(self, a_dict, maximum_size=100, search_key_func=None):
106
c_map = self._get_map(a_dict, maximum_size=maximum_size,
107
chk_bytes=self.get_chk_bytes(),
108
search_key_func=search_key_func)
111
def make_root_only_map(self, search_key_func=None):
112
return self.get_map({
113
('aaa',): 'initial aaa content',
114
('abb',): 'initial abb content',
115
}, search_key_func=search_key_func)
117
def make_root_only_aaa_ddd_map(self, search_key_func=None):
118
return self.get_map({
119
('aaa',): 'initial aaa content',
120
('ddd',): 'initial ddd content',
121
}, search_key_func=search_key_func)
123
def make_one_deep_map(self, search_key_func=None):
124
# Same as root_only_map, except it forces an InternalNode at the root
125
return self.get_map({
126
('aaa',): 'initial aaa content',
127
('abb',): 'initial abb content',
128
('ccc',): 'initial ccc content',
129
('ddd',): 'initial ddd content',
130
}, search_key_func=search_key_func)
132
def make_two_deep_map(self, search_key_func=None):
133
# Carefully chosen so that it creates a 2-deep map for both
134
# _search_key_plain and for _search_key_16
135
# Also so that things line up with make_one_deep_two_prefix_map
136
return self.get_map({
137
('aaa',): 'initial aaa content',
138
('abb',): 'initial abb content',
139
('acc',): 'initial acc content',
140
('ace',): 'initial ace content',
141
('add',): 'initial add content',
142
('adh',): 'initial adh content',
143
('adl',): 'initial adl content',
144
('ccc',): 'initial ccc content',
145
('ddd',): 'initial ddd content',
146
}, search_key_func=search_key_func)
148
def make_one_deep_two_prefix_map(self, search_key_func=None):
149
"""Create a map with one internal node, but references are extra long.
151
Otherwise has similar content to make_two_deep_map.
153
return self.get_map({
154
('aaa',): 'initial aaa content',
155
('add',): 'initial add content',
156
('adh',): 'initial adh content',
157
('adl',): 'initial adl content',
158
}, search_key_func=search_key_func)
160
def make_one_deep_one_prefix_map(self, search_key_func=None):
161
"""Create a map with one internal node, but references are extra long.
163
Similar to make_one_deep_two_prefix_map, except the split is at the
164
first char, rather than the second.
166
return self.get_map({
167
('add',): 'initial add content',
168
('adh',): 'initial adh content',
169
('adl',): 'initial adl content',
170
('bbb',): 'initial bbb content',
171
}, search_key_func=search_key_func)
174
class TestTestCaseWithExampleMaps(TestCaseWithExampleMaps):
175
"""Actual tests for the provided examples."""
177
def test_root_only_map_plain(self):
178
c_map = self.make_root_only_map()
179
self.assertEqualDiff(
181
" ('aaa',) 'initial aaa content'\n"
182
" ('abb',) 'initial abb content'\n",
185
def test_root_only_map_16(self):
186
c_map = self.make_root_only_map(search_key_func=chk_map._search_key_16)
187
self.assertEqualDiff(
189
" ('aaa',) 'initial aaa content'\n"
190
" ('abb',) 'initial abb content'\n",
193
def test_one_deep_map_plain(self):
194
c_map = self.make_one_deep_map()
195
self.assertEqualDiff(
198
" ('aaa',) 'initial aaa content'\n"
199
" ('abb',) 'initial abb content'\n"
201
" ('ccc',) 'initial ccc content'\n"
203
" ('ddd',) 'initial ddd content'\n",
206
def test_one_deep_map_16(self):
207
c_map = self.make_one_deep_map(search_key_func=chk_map._search_key_16)
208
self.assertEqualDiff(
211
" ('ccc',) 'initial ccc content'\n"
213
" ('abb',) 'initial abb content'\n"
215
" ('aaa',) 'initial aaa content'\n"
216
" ('ddd',) 'initial ddd content'\n",
219
def test_root_only_aaa_ddd_plain(self):
220
c_map = self.make_root_only_aaa_ddd_map()
221
self.assertEqualDiff(
223
" ('aaa',) 'initial aaa content'\n"
224
" ('ddd',) 'initial ddd content'\n",
227
def test_root_only_aaa_ddd_16(self):
228
c_map = self.make_root_only_aaa_ddd_map(
229
search_key_func=chk_map._search_key_16)
230
# We use 'aaa' and 'ddd' because they happen to map to 'F' when using
232
self.assertEqualDiff(
234
" ('aaa',) 'initial aaa content'\n"
235
" ('ddd',) 'initial ddd content'\n",
238
def test_two_deep_map_plain(self):
239
c_map = self.make_two_deep_map()
240
self.assertEqualDiff(
242
" 'a' InternalNode\n"
244
" ('aaa',) 'initial aaa content'\n"
246
" ('abb',) 'initial abb content'\n"
248
" ('acc',) 'initial acc content'\n"
249
" ('ace',) 'initial ace content'\n"
251
" ('add',) 'initial add content'\n"
252
" ('adh',) 'initial adh content'\n"
253
" ('adl',) 'initial adl content'\n"
255
" ('ccc',) 'initial ccc content'\n"
257
" ('ddd',) 'initial ddd content'\n",
260
def test_two_deep_map_16(self):
261
c_map = self.make_two_deep_map(search_key_func=chk_map._search_key_16)
262
self.assertEqualDiff(
265
" ('acc',) 'initial acc content'\n"
266
" ('ccc',) 'initial ccc content'\n"
268
" ('abb',) 'initial abb content'\n"
270
" ('ace',) 'initial ace content'\n"
271
" 'F' InternalNode\n"
273
" ('aaa',) 'initial aaa content'\n"
275
" ('adl',) 'initial adl content'\n"
277
" ('adh',) 'initial adh content'\n"
279
" ('ddd',) 'initial ddd content'\n"
281
" ('add',) 'initial add content'\n",
284
def test_one_deep_two_prefix_map_plain(self):
285
c_map = self.make_one_deep_two_prefix_map()
286
self.assertEqualDiff(
289
" ('aaa',) 'initial aaa content'\n"
291
" ('add',) 'initial add content'\n"
292
" ('adh',) 'initial adh content'\n"
293
" ('adl',) 'initial adl content'\n",
296
def test_one_deep_two_prefix_map_16(self):
297
c_map = self.make_one_deep_two_prefix_map(
298
search_key_func=chk_map._search_key_16)
299
self.assertEqualDiff(
302
" ('aaa',) 'initial aaa content'\n"
304
" ('adl',) 'initial adl content'\n"
306
" ('adh',) 'initial adh content'\n"
308
" ('add',) 'initial add content'\n",
311
def test_one_deep_one_prefix_map_plain(self):
312
c_map = self.make_one_deep_one_prefix_map()
313
self.assertEqualDiff(
316
" ('add',) 'initial add content'\n"
317
" ('adh',) 'initial adh content'\n"
318
" ('adl',) 'initial adl content'\n"
320
" ('bbb',) 'initial bbb content'\n",
323
def test_one_deep_one_prefix_map_16(self):
324
c_map = self.make_one_deep_one_prefix_map(
325
search_key_func=chk_map._search_key_16)
326
self.assertEqualDiff(
329
" ('bbb',) 'initial bbb content'\n"
331
" ('add',) 'initial add content'\n"
332
" ('adh',) 'initial adh content'\n"
333
" ('adl',) 'initial adl content'\n",
337
95
class TestMap(TestCaseWithStore):
339
97
def assertHasABMap(self, chk_bytes):
2129
class TestCHKMapDifference(TestCaseWithExampleMaps):
2131
def get_difference(self, new_roots, old_roots,
2132
search_key_func=None):
2133
if search_key_func is None:
2134
search_key_func = chk_map._search_key_plain
2135
return chk_map.CHKMapDifference(self.get_chk_bytes(),
2136
new_roots, old_roots, search_key_func)
2138
def test__init__(self):
2139
c_map = self.make_root_only_map()
2141
c_map.map(('aaa',), 'new aaa content')
2142
key2 = c_map._save()
2143
diff = self.get_difference([key2], [key1])
2144
self.assertEqual(set([key1]), diff._all_old_chks)
2145
self.assertEqual([], diff._old_queue)
2146
self.assertEqual([], diff._new_queue)
2148
def help__read_all_roots(self, search_key_func):
2149
c_map = self.make_root_only_map(search_key_func=search_key_func)
2151
c_map.map(('aaa',), 'new aaa content')
2152
key2 = c_map._save()
2153
diff = self.get_difference([key2], [key1], search_key_func)
2154
root_results = [record.key for record in diff._read_all_roots()]
2155
self.assertEqual([key2], root_results)
2156
# We should have queued up only items that aren't in the old
2158
self.assertEqual([(('aaa',), 'new aaa content')],
2159
diff._new_item_queue)
2160
self.assertEqual([], diff._new_queue)
2161
# And there are no old references, so that queue should be
2163
self.assertEqual([], diff._old_queue)
2165
def test__read_all_roots_plain(self):
2166
self.help__read_all_roots(search_key_func=chk_map._search_key_plain)
2168
def test__read_all_roots_16(self):
2169
self.help__read_all_roots(search_key_func=chk_map._search_key_16)
2171
def test__read_all_roots_skips_known_old(self):
2172
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2174
c_map2 = self.make_root_only_map(chk_map._search_key_plain)
2176
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2177
root_results = [record.key for record in diff._read_all_roots()]
2178
# We should have no results. key2 is completely contained within key1,
2179
# and we should have seen that in the first pass
2180
self.assertEqual([], root_results)
2182
def test__read_all_roots_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
c_map.map(('abb',), 'new abb content')
2188
key2 = c_map._save()
2189
key2_a = c_map._root_node._items['a'].key()
2190
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2191
root_results = [record.key for record in diff._read_all_roots()]
2192
self.assertEqual([key2], root_results)
2193
# At this point, we should have queued up only the 'a' Leaf on both
2194
# sides, both 'c' and 'd' are known to not have changed on both sides
2195
self.assertEqual([key2_a], diff._new_queue)
2196
self.assertEqual([], diff._new_item_queue)
2197
self.assertEqual([key1_a], diff._old_queue)
2199
def test__read_all_roots_multi_new_prepares_queues(self):
2200
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2202
c_map._dump_tree() # load everything
2203
key1_a = c_map._root_node._items['a'].key()
2204
key1_c = c_map._root_node._items['c'].key()
2205
c_map.map(('abb',), 'new abb content')
2206
key2 = c_map._save()
2207
key2_a = c_map._root_node._items['a'].key()
2208
key2_c = c_map._root_node._items['c'].key()
2209
c_map = chk_map.CHKMap(self.get_chk_bytes(), key1,
2210
chk_map._search_key_plain)
2211
c_map.map(('ccc',), 'new ccc content')
2212
key3 = c_map._save()
2213
key3_a = c_map._root_node._items['a'].key()
2214
key3_c = c_map._root_node._items['c'].key()
2215
diff = self.get_difference([key2, key3], [key1],
2216
chk_map._search_key_plain)
2217
root_results = [record.key for record in diff._read_all_roots()]
2218
self.assertEqual(sorted([key2, key3]), sorted(root_results))
2219
# We should have queued up key2_a, and key3_c, but not key2_c or key3_c
2220
self.assertEqual([key2_a, key3_c], diff._new_queue)
2221
self.assertEqual([], diff._new_item_queue)
2222
# And we should have queued up both a and c for the old set
2223
self.assertEqual([key1_a, key1_c], diff._old_queue)
2225
def test__read_all_roots_different_depths(self):
2226
c_map = self.make_two_deep_map(chk_map._search_key_plain)
2227
c_map._dump_tree() # load everything
2229
key1_a = c_map._root_node._items['a'].key()
2230
key1_c = c_map._root_node._items['c'].key()
2231
key1_d = c_map._root_node._items['d'].key()
2233
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2236
key2_aa = c_map2._root_node._items['aa'].key()
2237
key2_ad = c_map2._root_node._items['ad'].key()
2239
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2240
root_results = [record.key for record in diff._read_all_roots()]
2241
self.assertEqual([key2], root_results)
2242
# Only the 'a' subset should be queued up, since 'c' and 'd' cannot be
2244
self.assertEqual([key1_a], diff._old_queue)
2245
self.assertEqual([key2_aa, key2_ad], diff._new_queue)
2246
self.assertEqual([], diff._new_item_queue)
2248
diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2249
root_results = [record.key for record in diff._read_all_roots()]
2250
self.assertEqual([key1], root_results)
2252
self.assertEqual([key2_aa, key2_ad], diff._old_queue)
2253
self.assertEqual([key1_a, key1_c, key1_d], diff._new_queue)
2254
self.assertEqual([], diff._new_item_queue)
2256
def test__read_all_roots_different_depths_16(self):
2257
c_map = self.make_two_deep_map(chk_map._search_key_16)
2258
c_map._dump_tree() # load everything
2260
key1_2 = c_map._root_node._items['2'].key()
2261
key1_4 = c_map._root_node._items['4'].key()
2262
key1_C = c_map._root_node._items['C'].key()
2263
key1_F = c_map._root_node._items['F'].key()
2265
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_16)
2268
key2_F0 = c_map2._root_node._items['F0'].key()
2269
key2_F3 = c_map2._root_node._items['F3'].key()
2270
key2_F4 = c_map2._root_node._items['F4'].key()
2271
key2_FD = c_map2._root_node._items['FD'].key()
2273
diff = self.get_difference([key2], [key1], chk_map._search_key_16)
2274
root_results = [record.key for record in diff._read_all_roots()]
2275
self.assertEqual([key2], root_results)
2276
# Only the subset of keys that may be present should be queued up.
2277
self.assertEqual([key1_F], diff._old_queue)
2278
self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
2279
sorted(diff._new_queue))
2280
self.assertEqual([], diff._new_item_queue)
2282
diff = self.get_difference([key1], [key2], chk_map._search_key_16)
2283
root_results = [record.key for record in diff._read_all_roots()]
2284
self.assertEqual([key1], root_results)
2286
self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
2287
sorted(diff._old_queue))
2288
self.assertEqual(sorted([key1_2, key1_4, key1_C, key1_F]),
2289
sorted(diff._new_queue))
2290
self.assertEqual([], diff._new_item_queue)
2292
def test__read_all_roots_mixed_depth(self):
2293
c_map = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2294
c_map._dump_tree() # load everything
2296
key1_aa = c_map._root_node._items['aa'].key()
2297
key1_ad = c_map._root_node._items['ad'].key()
2299
c_map2 = self.make_one_deep_one_prefix_map(chk_map._search_key_plain)
2302
key2_a = c_map2._root_node._items['a'].key()
2303
key2_b = c_map2._root_node._items['b'].key()
2305
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2306
root_results = [record.key for record in diff._read_all_roots()]
2307
self.assertEqual([key2], root_results)
2308
# 'ad' matches exactly 'a' on the other side, so it should be removed,
2309
# and neither side should have it queued for walking
2310
self.assertEqual([], diff._old_queue)
2311
self.assertEqual([key2_b], diff._new_queue)
2312
self.assertEqual([], diff._new_item_queue)
2314
diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2315
root_results = [record.key for record in diff._read_all_roots()]
2316
self.assertEqual([key1], root_results)
2317
# Note: This is technically not the 'true minimal' set that we could
2318
# use The reason is that 'a' was matched exactly to 'ad' (by sha
2319
# sum). However, the code gets complicated in the case of more
2320
# than one interesting key, so for now, we live with this
2321
# Consider revising, though benchmarking showing it to be a
2322
# real-world issue should be done
2323
self.assertEqual([key2_a], diff._old_queue)
2324
# self.assertEqual([], diff._old_queue)
2325
self.assertEqual([key1_aa], diff._new_queue)
2326
self.assertEqual([], diff._new_item_queue)
2328
def test__read_all_roots_yields_extra_deep_records(self):
2329
# This is slightly controversial, as we will yield a chk page that we
2330
# might later on find out could be filtered out. (If a root node is
2331
# referenced deeper in the old set.)
2332
# However, even with stacking, we always have all chk pages that we
2333
# will need. So as long as we filter out the referenced keys, we'll
2334
# never run into problems.
2335
# This allows us to yield a root node record immediately, without any
2337
c_map = self.make_two_deep_map(chk_map._search_key_plain)
2338
c_map._dump_tree() # load all keys
2340
key1_a = c_map._root_node._items['a'].key()
2341
c_map2 = self.get_map({
2342
('acc',): 'initial acc content',
2343
('ace',): 'initial ace content',
2344
}, maximum_size=100)
2345
self.assertEqualDiff(
2347
" ('acc',) 'initial acc content'\n"
2348
" ('ace',) 'initial ace content'\n",
2349
c_map2._dump_tree())
2351
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2352
root_results = [record.key for record in diff._read_all_roots()]
2353
self.assertEqual([key2], root_results)
2354
# However, even though we have yielded the root node to be fetched,
2355
# we should have enqued all of the chk pages to be walked, so that we
2356
# can find the keys if they are present
2357
self.assertEqual([key1_a], diff._old_queue)
2358
self.assertEqual([(('acc',), 'initial acc content'),
2359
(('ace',), 'initial ace content'),
2360
], diff._new_item_queue)
2362
def test__read_all_roots_multiple_targets(self):
2363
c_map = self.make_root_only_map()
2365
c_map = self.make_one_deep_map()
2368
key2_c = c_map._root_node._items['c'].key()
2369
key2_d = c_map._root_node._items['d'].key()
2370
c_map.map(('ccc',), 'new ccc value')
2371
key3 = c_map._save()
2372
key3_c = c_map._root_node._items['c'].key()
2373
diff = self.get_difference([key2, key3], [key1],
2374
chk_map._search_key_plain)
2375
root_results = [record.key for record in diff._read_all_roots()]
2376
self.assertEqual(sorted([key2, key3]), sorted(root_results))
2377
self.assertEqual([], diff._old_queue)
2378
# the key 'd' is interesting from key2 and key3, but should only be
2379
# entered into the queue 1 time
2380
self.assertEqual(sorted([key2_c, key3_c, key2_d]),
2381
sorted(diff._new_queue))
2382
self.assertEqual([], diff._new_item_queue)
2384
def test__read_all_roots_no_old(self):
2385
# This is the 'initial branch' case. With nothing in the old
2386
# set, we can just queue up all root nodes into interesting queue, and
2387
# then have them fast-path flushed via _flush_new_queue
2388
c_map = self.make_two_deep_map()
2390
diff = self.get_difference([key1], [], chk_map._search_key_plain)
2391
root_results = [record.key for record in diff._read_all_roots()]
2392
self.assertEqual([], root_results)
2393
self.assertEqual([], diff._old_queue)
2394
self.assertEqual([key1], diff._new_queue)
2395
self.assertEqual([], diff._new_item_queue)
2397
c_map2 = self.make_one_deep_map()
2399
diff = self.get_difference([key1, key2], [], chk_map._search_key_plain)
2400
root_results = [record.key for record in diff._read_all_roots()]
2401
self.assertEqual([], root_results)
2402
self.assertEqual([], diff._old_queue)
2403
self.assertEqual(sorted([key1, key2]), sorted(diff._new_queue))
2404
self.assertEqual([], diff._new_item_queue)
2406
def test__read_all_roots_no_old_16(self):
2407
c_map = self.make_two_deep_map(chk_map._search_key_16)
2409
diff = self.get_difference([key1], [], chk_map._search_key_16)
2410
root_results = [record.key for record in diff._read_all_roots()]
2411
self.assertEqual([], root_results)
2412
self.assertEqual([], diff._old_queue)
2413
self.assertEqual([key1], diff._new_queue)
2414
self.assertEqual([], diff._new_item_queue)
2416
c_map2 = self.make_one_deep_map(chk_map._search_key_16)
2418
diff = self.get_difference([key1, key2], [],
2419
chk_map._search_key_16)
2420
root_results = [record.key for record in diff._read_all_roots()]
2421
self.assertEqual([], root_results)
2422
self.assertEqual([], diff._old_queue)
2423
self.assertEqual(sorted([key1, key2]),
2424
sorted(diff._new_queue))
2425
self.assertEqual([], diff._new_item_queue)
2427
def test__read_all_roots_multiple_old(self):
2428
c_map = self.make_two_deep_map()
2430
c_map._dump_tree() # load everything
2431
key1_a = c_map._root_node._items['a'].key()
2432
c_map.map(('ccc',), 'new ccc value')
2433
key2 = c_map._save()
2434
key2_a = c_map._root_node._items['a'].key()
2435
c_map.map(('add',), 'new add value')
2436
key3 = c_map._save()
2437
key3_a = c_map._root_node._items['a'].key()
2438
diff = self.get_difference([key3], [key1, key2],
2439
chk_map._search_key_plain)
2440
root_results = [record.key for record in diff._read_all_roots()]
2441
self.assertEqual([key3], root_results)
2442
# the 'a' keys should not be queued up 2 times, since they are
2444
self.assertEqual([key1_a], diff._old_queue)
2445
self.assertEqual([key3_a], diff._new_queue)
2446
self.assertEqual([], diff._new_item_queue)
2448
def test__process_next_old_batched_no_dupes(self):
2449
c_map = self.make_two_deep_map()
2451
c_map._dump_tree() # load everything
2452
key1_a = c_map._root_node._items['a'].key()
2453
key1_aa = c_map._root_node._items['a']._items['aa'].key()
2454
key1_ab = c_map._root_node._items['a']._items['ab'].key()
2455
key1_ac = c_map._root_node._items['a']._items['ac'].key()
2456
key1_ad = c_map._root_node._items['a']._items['ad'].key()
2457
c_map.map(('aaa',), 'new aaa value')
2458
key2 = c_map._save()
2459
key2_a = c_map._root_node._items['a'].key()
2460
key2_aa = c_map._root_node._items['a']._items['aa'].key()
2461
c_map.map(('acc',), 'new acc content')
2462
key3 = c_map._save()
2463
key3_a = c_map._root_node._items['a'].key()
2464
key3_ac = c_map._root_node._items['a']._items['ac'].key()
2465
diff = self.get_difference([key3], [key1, key2],
2466
chk_map._search_key_plain)
2467
root_results = [record.key for record in diff._read_all_roots()]
2468
self.assertEqual([key3], root_results)
2469
self.assertEqual(sorted([key1_a, key2_a]),
2470
sorted(diff._old_queue))
2471
self.assertEqual([key3_a], diff._new_queue)
2472
self.assertEqual([], diff._new_item_queue)
2473
diff._process_next_old()
2474
# All of the old records should be brought in and queued up,
2475
# but we should not have any duplicates
2476
self.assertEqual(sorted([key1_aa, key1_ab, key1_ac, key1_ad, key2_aa]),
2477
sorted(diff._old_queue))
2480
class TestIterInterestingNodes(TestCaseWithExampleMaps):
2482
def get_map_key(self, a_dict, maximum_size=10):
2483
c_map = self.get_map(a_dict, maximum_size=maximum_size)
1831
class TestIterInterestingNodes(TestCaseWithStore):
1833
def get_chk_bytes(self):
1834
if getattr(self, '_chk_bytes', None) is None:
1835
self._chk_bytes = super(TestIterInterestingNodes,
1836
self).get_chk_bytes()
1837
return self._chk_bytes
1839
def get_map_key(self, a_dict):
1840
c_map = self._get_map(a_dict, maximum_size=10,
1841
chk_bytes=self.get_chk_bytes())
2484
1842
return c_map.key()
2486
def assertIterInteresting(self, records, items, interesting_keys,
1844
def assertIterInteresting(self, expected, interesting_keys,
1845
uninteresting_keys):
2488
1846
"""Check the result of iter_interesting_nodes.
2490
Note that we no longer care how many steps are taken, etc, just that
2491
the right contents are returned.
2493
:param records: A list of record keys that should be yielded
2494
:param items: A list of items (key,value) that should be yielded.
1848
:param expected: A list of (record_keys, interesting_chk_pages,
1849
interesting key value pairs)
2496
1851
store = self.get_chk_bytes()
2497
store._search_key_func = chk_map._search_key_plain
2498
1852
iter_nodes = chk_map.iter_interesting_nodes(store, interesting_keys,
2502
for record, new_items in iter_nodes:
2503
if record is not None:
2504
record_keys.append(record.key)
2506
all_items.extend(new_items)
2507
self.assertEqual(sorted(records), sorted(record_keys))
2508
self.assertEqual(sorted(items), sorted(all_items))
1854
nodes = list(iter_nodes)
1855
for count, (exp, act) in enumerate(izip(expected, nodes)):
1856
exp_record, exp_items = exp
1858
exp_tuple = (exp_record, sorted(exp_items))
1860
act_tuple = (None, sorted(items))
1862
act_tuple = (record.key, sorted(items))
1863
self.assertEqual(exp_tuple, act_tuple,
1864
'entry %d did not match expected' % count)
1865
self.assertEqual(len(expected), len(nodes))
2510
1867
def test_empty_to_one_keys(self):
2511
1868
target = self.get_map_key({('a',): 'content'})
2512
self.assertIterInteresting([target],
2513
[(('a',), 'content')],
1869
self.assertIterInteresting(
1870
[(target, [(('a',), 'content')]),
2516
1873
def test_none_to_one_key(self):
2517
1874
basis = self.get_map_key({})
2518
1875
target = self.get_map_key({('a',): 'content'})
2519
self.assertIterInteresting([target],
2520
[(('a',), 'content')],
1876
self.assertIterInteresting(
1877
[(None, [(('a',), 'content')]),
1879
], [target], [basis])
2523
1881
def test_one_to_none_key(self):
2524
1882
basis = self.get_map_key({('a',): 'content'})
2525
1883
target = self.get_map_key({})
2526
self.assertIterInteresting([target],
1884
self.assertIterInteresting(
2530
1888
def test_common_pages(self):
2531
1889
basis = self.get_map_key({('a',): 'content',
2686
2053
# The key for the leaf bba node
2687
2054
bba_key = target2_map._root_node._items['b']._items['bba'].key()
2688
2055
self.assertIterInteresting(
2689
[target1, target2, a_key, aac_key, b_key, bba_key],
2690
[(('aac',), 'target1'), (('bba',), 'target2')],
2691
[target1, target2], [basis1, basis2])
2693
def test_multiple_maps_overlapping_common_new(self):
2694
# Test that when a node found through the interesting_keys iteration
2695
# for *some roots* and also via the old keys iteration, that
2696
# it is still scanned for old refs and items, because its
2697
# not truely new. This requires 2 levels of InternalNodes to expose,
2698
# because of the way the bootstrap in _find_children_info works.
2699
# This suggests that the code is probably amenable to/benefit from
2701
# How does this test work?
2702
# 1) We need a second level InternalNode present in a basis tree.
2703
# 2) We need a left side new tree that uses that InternalNode
2704
# 3) We need a right side new tree that does not use that InternalNode
2705
# at all but that has an unchanged *value* that was reachable inside
2707
basis = self.get_map_key({
2708
# InternalNode, unchanged in left:
2711
# Forces an internalNode at 'a'
2714
left = self.get_map_key({
2715
# All of basis unchanged
2719
# And a new top level node so the root key is different
2722
right = self.get_map_key({
2723
# A value that is unchanged from basis and thus should be filtered
2727
basis_map = CHKMap(self.get_chk_bytes(), basis)
2728
self.assertEqualDiff(
2730
" 'a' InternalNode\n"
2732
" ('aaa',) 'left'\n"
2734
" ('abb',) 'right'\n"
2736
" ('ccc',) 'common'\n",
2737
basis_map._dump_tree())
2738
# Get left expected data
2739
left_map = CHKMap(self.get_chk_bytes(), left)
2740
self.assertEqualDiff(
2742
" 'a' InternalNode\n"
2744
" ('aaa',) 'left'\n"
2746
" ('abb',) 'right'\n"
2748
" ('ccc',) 'common'\n"
2750
" ('ddd',) 'change'\n",
2751
left_map._dump_tree())
2752
# Keys from left side target
2753
l_d_key = left_map._root_node._items['d'].key()
2754
# Get right expected data
2755
right_map = CHKMap(self.get_chk_bytes(), right)
2756
self.assertEqualDiff(
2758
" ('abb',) 'right'\n",
2759
right_map._dump_tree())
2760
# Keys from the right side target - none, the root is enough.
2762
self.assertIterInteresting(
2763
[right, left, l_d_key],
2764
[(('ddd',), 'change')],
2765
[left, right], [basis])
2767
def test_multiple_maps_similar(self):
2768
# We want to have a depth=2 tree, with multiple entries in each leaf
2770
basis = self.get_map_key({
2771
('aaa',): 'unchanged',
2772
('abb',): 'will change left',
2773
('caa',): 'unchanged',
2774
('cbb',): 'will change right',
2776
left = self.get_map_key({
2777
('aaa',): 'unchanged',
2778
('abb',): 'changed left',
2779
('caa',): 'unchanged',
2780
('cbb',): 'will change right',
2782
right = self.get_map_key({
2783
('aaa',): 'unchanged',
2784
('abb',): 'will change left',
2785
('caa',): 'unchanged',
2786
('cbb',): 'changed right',
2788
basis_map = CHKMap(self.get_chk_bytes(), basis)
2789
self.assertEqualDiff(
2792
" ('aaa',) 'unchanged'\n"
2793
" ('abb',) 'will change left'\n"
2795
" ('caa',) 'unchanged'\n"
2796
" ('cbb',) 'will change right'\n",
2797
basis_map._dump_tree())
2798
# Get left expected data
2799
left_map = CHKMap(self.get_chk_bytes(), left)
2800
self.assertEqualDiff(
2803
" ('aaa',) 'unchanged'\n"
2804
" ('abb',) 'changed left'\n"
2806
" ('caa',) 'unchanged'\n"
2807
" ('cbb',) 'will change right'\n",
2808
left_map._dump_tree())
2809
# Keys from left side target
2810
l_a_key = left_map._root_node._items['a'].key()
2811
l_c_key = left_map._root_node._items['c'].key()
2812
# Get right expected data
2813
right_map = CHKMap(self.get_chk_bytes(), right)
2814
self.assertEqualDiff(
2817
" ('aaa',) 'unchanged'\n"
2818
" ('abb',) 'will change left'\n"
2820
" ('caa',) 'unchanged'\n"
2821
" ('cbb',) 'changed right'\n",
2822
right_map._dump_tree())
2823
r_a_key = right_map._root_node._items['a'].key()
2824
r_c_key = right_map._root_node._items['c'].key()
2825
self.assertIterInteresting(
2826
[right, left, l_a_key, r_c_key],
2827
[(('abb',), 'changed left'), (('cbb',), 'changed right')],
2828
[left, right], [basis])
2060
(aac_key, [(('aac',), 'target1')]),
2061
(bba_key, [(('bba',), 'target2')]),
2062
], [target1, target2], [basis1, basis2])
added
removed
bzrlib/tests/test_chk_map.py
