87
95
return dict(node.iteritems(*args))
98
class TestCaseWithExampleMaps(TestCaseWithStore):
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
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)
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)
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)
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)
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)
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.
152
Otherwise has similar content to make_two_deep_map.
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)
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.
164
Similar to make_one_deep_two_prefix_map, except the split is at the
165
first char, rather than the second.
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)
175
class TestTestCaseWithExampleMaps(TestCaseWithExampleMaps):
176
"""Actual tests for the provided examples."""
178
def test_root_only_map_plain(self):
179
c_map = self.make_root_only_map()
180
self.assertEqualDiff(
182
" ('aaa',) 'initial aaa content'\n"
183
" ('abb',) 'initial abb content'\n",
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(
190
" ('aaa',) 'initial aaa content'\n"
191
" ('abb',) 'initial abb content'\n",
194
def test_one_deep_map_plain(self):
195
c_map = self.make_one_deep_map()
196
self.assertEqualDiff(
199
" ('aaa',) 'initial aaa content'\n"
200
" ('abb',) 'initial abb content'\n"
202
" ('ccc',) 'initial ccc content'\n"
204
" ('ddd',) 'initial ddd content'\n",
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(
212
" ('ccc',) 'initial ccc content'\n"
214
" ('abb',) 'initial abb content'\n"
216
" ('aaa',) 'initial aaa content'\n"
217
" ('ddd',) 'initial ddd content'\n",
220
def test_root_only_aaa_ddd_plain(self):
221
c_map = self.make_root_only_aaa_ddd_map()
222
self.assertEqualDiff(
224
" ('aaa',) 'initial aaa content'\n"
225
" ('ddd',) 'initial ddd content'\n",
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
233
self.assertEqualDiff(
235
" ('aaa',) 'initial aaa content'\n"
236
" ('ddd',) 'initial ddd content'\n",
239
def test_two_deep_map_plain(self):
240
c_map = self.make_two_deep_map()
241
self.assertEqualDiff(
243
" 'a' InternalNode\n"
245
" ('aaa',) 'initial aaa content'\n"
247
" ('abb',) 'initial abb content'\n"
249
" ('acc',) 'initial acc content'\n"
250
" ('ace',) 'initial ace content'\n"
252
" ('add',) 'initial add content'\n"
253
" ('adh',) 'initial adh content'\n"
254
" ('adl',) 'initial adl content'\n"
256
" ('ccc',) 'initial ccc content'\n"
258
" ('ddd',) 'initial ddd content'\n",
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(
266
" ('acc',) 'initial acc content'\n"
267
" ('ccc',) 'initial ccc content'\n"
269
" ('abb',) 'initial abb content'\n"
271
" ('ace',) 'initial ace content'\n"
272
" 'F' InternalNode\n"
274
" ('aaa',) 'initial aaa content'\n"
276
" ('adl',) 'initial adl content'\n"
278
" ('adh',) 'initial adh content'\n"
280
" ('ddd',) 'initial ddd content'\n"
282
" ('add',) 'initial add content'\n",
285
def test_one_deep_two_prefix_map_plain(self):
286
c_map = self.make_one_deep_two_prefix_map()
287
self.assertEqualDiff(
290
" ('aaa',) 'initial aaa content'\n"
292
" ('add',) 'initial add content'\n"
293
" ('adh',) 'initial adh content'\n"
294
" ('adl',) 'initial adl content'\n",
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(
303
" ('aaa',) 'initial aaa content'\n"
305
" ('adl',) 'initial adl content'\n"
307
" ('adh',) 'initial adh content'\n"
309
" ('add',) 'initial add content'\n",
312
def test_one_deep_one_prefix_map_plain(self):
313
c_map = self.make_one_deep_one_prefix_map()
314
self.assertEqualDiff(
317
" ('add',) 'initial add content'\n"
318
" ('adh',) 'initial adh content'\n"
319
" ('adl',) 'initial adl content'\n"
321
" ('bbb',) 'initial bbb content'\n",
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(
330
" ('bbb',) 'initial bbb content'\n"
332
" ('add',) 'initial add content'\n"
333
" ('adh',) 'initial adh content'\n"
334
" ('adl',) 'initial adl content'\n",
90
338
class TestMap(TestCaseWithStore):
92
340
def assertHasABMap(self, chk_bytes):
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())
2139
class TestCHKMapDifference(TestCaseWithExampleMaps):
2141
def get_difference(self, new_roots, old_roots,
2142
search_key_func=None):
2143
if search_key_func is None:
2144
search_key_func = chk_map._search_key_plain
2145
return chk_map.CHKMapDifference(self.get_chk_bytes(),
2146
new_roots, old_roots, search_key_func)
2148
def test__init__(self):
2149
c_map = self.make_root_only_map()
2151
c_map.map(('aaa',), 'new aaa content')
2152
key2 = c_map._save()
2153
diff = self.get_difference([key2], [key1])
2154
self.assertEqual(set([key1]), diff._all_old_chks)
2155
self.assertEqual([], diff._old_queue)
2156
self.assertEqual([], diff._new_queue)
2158
def help__read_all_roots(self, search_key_func):
2159
c_map = self.make_root_only_map(search_key_func=search_key_func)
2161
c_map.map(('aaa',), 'new aaa content')
2162
key2 = c_map._save()
2163
diff = self.get_difference([key2], [key1], search_key_func)
2164
root_results = [record.key for record in diff._read_all_roots()]
2165
self.assertEqual([key2], root_results)
2166
# We should have queued up only items that aren't in the old
2168
self.assertEqual([(('aaa',), 'new aaa content')],
2169
diff._new_item_queue)
2170
self.assertEqual([], diff._new_queue)
2171
# And there are no old references, so that queue should be
2173
self.assertEqual([], diff._old_queue)
2175
def test__read_all_roots_plain(self):
2176
self.help__read_all_roots(search_key_func=chk_map._search_key_plain)
2178
def test__read_all_roots_16(self):
2179
self.help__read_all_roots(search_key_func=chk_map._search_key_16)
2181
def test__read_all_roots_skips_known_old(self):
2182
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2184
c_map2 = self.make_root_only_map(chk_map._search_key_plain)
2186
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2187
root_results = [record.key for record in diff._read_all_roots()]
2188
# We should have no results. key2 is completely contained within key1,
2189
# and we should have seen that in the first pass
2190
self.assertEqual([], root_results)
2192
def test__read_all_roots_prepares_queues(self):
2193
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2195
c_map._dump_tree() # load everything
2196
key1_a = c_map._root_node._items['a'].key()
2197
c_map.map(('abb',), 'new abb content')
2198
key2 = c_map._save()
2199
key2_a = c_map._root_node._items['a'].key()
2200
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2201
root_results = [record.key for record in diff._read_all_roots()]
2202
self.assertEqual([key2], root_results)
2203
# At this point, we should have queued up only the 'a' Leaf on both
2204
# sides, both 'c' and 'd' are known to not have changed on both sides
2205
self.assertEqual([key2_a], diff._new_queue)
2206
self.assertEqual([], diff._new_item_queue)
2207
self.assertEqual([key1_a], diff._old_queue)
2209
def test__read_all_roots_multi_new_prepares_queues(self):
2210
c_map = self.make_one_deep_map(chk_map._search_key_plain)
2212
c_map._dump_tree() # load everything
2213
key1_a = c_map._root_node._items['a'].key()
2214
key1_c = c_map._root_node._items['c'].key()
2215
c_map.map(('abb',), 'new abb content')
2216
key2 = c_map._save()
2217
key2_a = c_map._root_node._items['a'].key()
2218
key2_c = c_map._root_node._items['c'].key()
2219
c_map = chk_map.CHKMap(self.get_chk_bytes(), key1,
2220
chk_map._search_key_plain)
2221
c_map.map(('ccc',), 'new ccc content')
2222
key3 = c_map._save()
2223
key3_a = c_map._root_node._items['a'].key()
2224
key3_c = c_map._root_node._items['c'].key()
2225
diff = self.get_difference([key2, key3], [key1],
2226
chk_map._search_key_plain)
2227
root_results = [record.key for record in diff._read_all_roots()]
2228
self.assertEqual(sorted([key2, key3]), sorted(root_results))
2229
# We should have queued up key2_a, and key3_c, but not key2_c or key3_c
2230
self.assertEqual([key2_a, key3_c], diff._new_queue)
2231
self.assertEqual([], diff._new_item_queue)
2232
# And we should have queued up both a and c for the old set
2233
self.assertEqual([key1_a, key1_c], diff._old_queue)
2235
def test__read_all_roots_different_depths(self):
2236
c_map = self.make_two_deep_map(chk_map._search_key_plain)
2237
c_map._dump_tree() # load everything
2239
key1_a = c_map._root_node._items['a'].key()
2240
key1_c = c_map._root_node._items['c'].key()
2241
key1_d = c_map._root_node._items['d'].key()
2243
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2246
key2_aa = c_map2._root_node._items['aa'].key()
2247
key2_ad = c_map2._root_node._items['ad'].key()
2249
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2250
root_results = [record.key for record in diff._read_all_roots()]
2251
self.assertEqual([key2], root_results)
2252
# Only the 'a' subset should be queued up, since 'c' and 'd' cannot be
2254
self.assertEqual([key1_a], diff._old_queue)
2255
self.assertEqual([key2_aa, key2_ad], diff._new_queue)
2256
self.assertEqual([], diff._new_item_queue)
2258
diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2259
root_results = [record.key for record in diff._read_all_roots()]
2260
self.assertEqual([key1], root_results)
2262
self.assertEqual([key2_aa, key2_ad], diff._old_queue)
2263
self.assertEqual([key1_a, key1_c, key1_d], diff._new_queue)
2264
self.assertEqual([], diff._new_item_queue)
2266
def test__read_all_roots_different_depths_16(self):
2267
c_map = self.make_two_deep_map(chk_map._search_key_16)
2268
c_map._dump_tree() # load everything
2270
key1_2 = c_map._root_node._items['2'].key()
2271
key1_4 = c_map._root_node._items['4'].key()
2272
key1_C = c_map._root_node._items['C'].key()
2273
key1_F = c_map._root_node._items['F'].key()
2275
c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_16)
2278
key2_F0 = c_map2._root_node._items['F0'].key()
2279
key2_F3 = c_map2._root_node._items['F3'].key()
2280
key2_F4 = c_map2._root_node._items['F4'].key()
2281
key2_FD = c_map2._root_node._items['FD'].key()
2283
diff = self.get_difference([key2], [key1], chk_map._search_key_16)
2284
root_results = [record.key for record in diff._read_all_roots()]
2285
self.assertEqual([key2], root_results)
2286
# Only the subset of keys that may be present should be queued up.
2287
self.assertEqual([key1_F], diff._old_queue)
2288
self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
2289
sorted(diff._new_queue))
2290
self.assertEqual([], diff._new_item_queue)
2292
diff = self.get_difference([key1], [key2], chk_map._search_key_16)
2293
root_results = [record.key for record in diff._read_all_roots()]
2294
self.assertEqual([key1], root_results)
2296
self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
2297
sorted(diff._old_queue))
2298
self.assertEqual(sorted([key1_2, key1_4, key1_C, key1_F]),
2299
sorted(diff._new_queue))
2300
self.assertEqual([], diff._new_item_queue)
2302
def test__read_all_roots_mixed_depth(self):
2303
c_map = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2304
c_map._dump_tree() # load everything
2306
key1_aa = c_map._root_node._items['aa'].key()
2307
key1_ad = c_map._root_node._items['ad'].key()
2309
c_map2 = self.make_one_deep_one_prefix_map(chk_map._search_key_plain)
2312
key2_a = c_map2._root_node._items['a'].key()
2313
key2_b = c_map2._root_node._items['b'].key()
2315
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2316
root_results = [record.key for record in diff._read_all_roots()]
2317
self.assertEqual([key2], root_results)
2318
# 'ad' matches exactly 'a' on the other side, so it should be removed,
2319
# and neither side should have it queued for walking
2320
self.assertEqual([], diff._old_queue)
2321
self.assertEqual([key2_b], diff._new_queue)
2322
self.assertEqual([], diff._new_item_queue)
2324
diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2325
root_results = [record.key for record in diff._read_all_roots()]
2326
self.assertEqual([key1], root_results)
2327
# Note: This is technically not the 'true minimal' set that we could
2328
# use The reason is that 'a' was matched exactly to 'ad' (by sha
2329
# sum). However, the code gets complicated in the case of more
2330
# than one interesting key, so for now, we live with this
2331
# Consider revising, though benchmarking showing it to be a
2332
# real-world issue should be done
2333
self.assertEqual([key2_a], diff._old_queue)
2334
# self.assertEqual([], diff._old_queue)
2335
self.assertEqual([key1_aa], diff._new_queue)
2336
self.assertEqual([], diff._new_item_queue)
2338
def test__read_all_roots_yields_extra_deep_records(self):
2339
# This is slightly controversial, as we will yield a chk page that we
2340
# might later on find out could be filtered out. (If a root node is
2341
# referenced deeper in the old set.)
2342
# However, even with stacking, we always have all chk pages that we
2343
# will need. So as long as we filter out the referenced keys, we'll
2344
# never run into problems.
2345
# This allows us to yield a root node record immediately, without any
2347
c_map = self.make_two_deep_map(chk_map._search_key_plain)
2348
c_map._dump_tree() # load all keys
2350
key1_a = c_map._root_node._items['a'].key()
2351
c_map2 = self.get_map({
2352
('acc',): 'initial acc content',
2353
('ace',): 'initial ace content',
2354
}, maximum_size=100)
2355
self.assertEqualDiff(
2357
" ('acc',) 'initial acc content'\n"
2358
" ('ace',) 'initial ace content'\n",
2359
c_map2._dump_tree())
2361
diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2362
root_results = [record.key for record in diff._read_all_roots()]
2363
self.assertEqual([key2], root_results)
2364
# However, even though we have yielded the root node to be fetched,
2365
# we should have enqued all of the chk pages to be walked, so that we
2366
# can find the keys if they are present
2367
self.assertEqual([key1_a], diff._old_queue)
2368
self.assertEqual([(('acc',), 'initial acc content'),
2369
(('ace',), 'initial ace content'),
2370
], diff._new_item_queue)
2372
def test__read_all_roots_multiple_targets(self):
2373
c_map = self.make_root_only_map()
2375
c_map = self.make_one_deep_map()
2378
key2_c = c_map._root_node._items['c'].key()
2379
key2_d = c_map._root_node._items['d'].key()
2380
c_map.map(('ccc',), 'new ccc value')
2381
key3 = c_map._save()
2382
key3_c = c_map._root_node._items['c'].key()
2383
diff = self.get_difference([key2, key3], [key1],
2384
chk_map._search_key_plain)
2385
root_results = [record.key for record in diff._read_all_roots()]
2386
self.assertEqual(sorted([key2, key3]), sorted(root_results))
2387
self.assertEqual([], diff._old_queue)
2388
# the key 'd' is interesting from key2 and key3, but should only be
2389
# entered into the queue 1 time
2390
self.assertEqual(sorted([key2_c, key3_c, key2_d]),
2391
sorted(diff._new_queue))
2392
self.assertEqual([], diff._new_item_queue)
2394
def test__read_all_roots_no_old(self):
2395
# This is the 'initial branch' case. With nothing in the old
2396
# set, we can just queue up all root nodes into interesting queue, and
2397
# then have them fast-path flushed via _flush_new_queue
2398
c_map = self.make_two_deep_map()
2400
diff = self.get_difference([key1], [], chk_map._search_key_plain)
2401
root_results = [record.key for record in diff._read_all_roots()]
2402
self.assertEqual([], root_results)
2403
self.assertEqual([], diff._old_queue)
2404
self.assertEqual([key1], diff._new_queue)
2405
self.assertEqual([], diff._new_item_queue)
2407
c_map2 = self.make_one_deep_map()
2409
diff = self.get_difference([key1, key2], [], chk_map._search_key_plain)
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(sorted([key1, key2]), sorted(diff._new_queue))
2414
self.assertEqual([], diff._new_item_queue)
2416
def test__read_all_roots_no_old_16(self):
2417
c_map = self.make_two_deep_map(chk_map._search_key_16)
2419
diff = self.get_difference([key1], [], 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([key1], diff._new_queue)
2424
self.assertEqual([], diff._new_item_queue)
2426
c_map2 = self.make_one_deep_map(chk_map._search_key_16)
2428
diff = self.get_difference([key1, key2], [],
2429
chk_map._search_key_16)
2430
root_results = [record.key for record in diff._read_all_roots()]
2431
self.assertEqual([], root_results)
2432
self.assertEqual([], diff._old_queue)
2433
self.assertEqual(sorted([key1, key2]),
2434
sorted(diff._new_queue))
2435
self.assertEqual([], diff._new_item_queue)
2437
def test__read_all_roots_multiple_old(self):
2438
c_map = self.make_two_deep_map()
2440
c_map._dump_tree() # load everything
2441
key1_a = c_map._root_node._items['a'].key()
2442
c_map.map(('ccc',), 'new ccc value')
2443
key2 = c_map._save()
2444
key2_a = c_map._root_node._items['a'].key()
2445
c_map.map(('add',), 'new add value')
2446
key3 = c_map._save()
2447
key3_a = c_map._root_node._items['a'].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
# the 'a' keys should not be queued up 2 times, since they are
2454
self.assertEqual([key1_a], diff._old_queue)
2455
self.assertEqual([key3_a], diff._new_queue)
2456
self.assertEqual([], diff._new_item_queue)
2458
def test__process_next_old_batched_no_dupes(self):
2459
c_map = self.make_two_deep_map()
2461
c_map._dump_tree() # load everything
2462
key1_a = c_map._root_node._items['a'].key()
2463
key1_aa = c_map._root_node._items['a']._items['aa'].key()
2464
key1_ab = c_map._root_node._items['a']._items['ab'].key()
2465
key1_ac = c_map._root_node._items['a']._items['ac'].key()
2466
key1_ad = c_map._root_node._items['a']._items['ad'].key()
2467
c_map.map(('aaa',), 'new aaa value')
2468
key2 = c_map._save()
2469
key2_a = c_map._root_node._items['a'].key()
2470
key2_aa = c_map._root_node._items['a']._items['aa'].key()
2471
c_map.map(('acc',), 'new acc content')
2472
key3 = c_map._save()
2473
key3_a = c_map._root_node._items['a'].key()
2474
key3_ac = c_map._root_node._items['a']._items['ac'].key()
2475
diff = self.get_difference([key3], [key1, key2],
2476
chk_map._search_key_plain)
2477
root_results = [record.key for record in diff._read_all_roots()]
2478
self.assertEqual([key3], root_results)
2479
self.assertEqual(sorted([key1_a, key2_a]),
2480
sorted(diff._old_queue))
2481
self.assertEqual([key3_a], diff._new_queue)
2482
self.assertEqual([], diff._new_item_queue)
2483
diff._process_next_old()
2484
# All of the old records should be brought in and queued up,
2485
# but we should not have any duplicates
2486
self.assertEqual(sorted([key1_aa, key1_ab, key1_ac, key1_ad, key2_aa]),
2487
sorted(diff._old_queue))
2490
class TestIterInterestingNodes(TestCaseWithExampleMaps):
2492
def get_map_key(self, a_dict, maximum_size=10):
2493
c_map = self.get_map(a_dict, maximum_size=maximum_size)
1837
2494
return c_map.key()
1839
def assertIterInteresting(self, expected, interesting_keys,
1840
uninteresting_keys):
2496
def assertIterInteresting(self, records, items, interesting_keys,
1841
2498
"""Check the result of iter_interesting_nodes.
1843
:param expected: A list of (record_keys, interesting_chk_pages,
1844
interesting key value pairs)
2500
Note that we no longer care how many steps are taken, etc, just that
2501
the right contents are returned.
2503
:param records: A list of record keys that should be yielded
2504
:param items: A list of items (key,value) that should be yielded.
1846
2506
store = self.get_chk_bytes()
2507
store._search_key_func = chk_map._search_key_plain
1847
2508
iter_nodes = chk_map.iter_interesting_nodes(store, interesting_keys,
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
for record, new_items in iter_nodes:
2513
if record is not None:
2514
record_keys.append(record.key)
2516
all_items.extend(new_items)
2517
self.assertEqual(sorted(records), sorted(record_keys))
2518
self.assertEqual(sorted(items), sorted(all_items))
1862
2520
def test_empty_to_one_keys(self):
1863
2521
target = self.get_map_key({('a',): 'content'})
1864
self.assertIterInteresting(
1865
[(target, [(('a',), 'content')]),
2522
self.assertIterInteresting([target],
2523
[(('a',), 'content')],
1868
2526
def test_none_to_one_key(self):
1869
2527
basis = self.get_map_key({})
1870
2528
target = self.get_map_key({('a',): 'content'})
1871
self.assertIterInteresting(
1872
[(None, [(('a',), 'content')]),
1874
], [target], [basis])
2529
self.assertIterInteresting([target],
2530
[(('a',), 'content')],
1876
2533
def test_one_to_none_key(self):
1877
2534
basis = self.get_map_key({('a',): 'content'})
1878
2535
target = self.get_map_key({})
1879
self.assertIterInteresting(
2536
self.assertIterInteresting([target],
1883
2540
def test_common_pages(self):
1884
2541
basis = self.get_map_key({('a',): 'content',
2048
2696
# The key for the leaf bba node
2049
2697
bba_key = target2_map._root_node._items['b']._items['bba'].key()
2050
2698
self.assertIterInteresting(
2055
(aac_key, [(('aac',), 'target1')]),
2056
(bba_key, [(('bba',), 'target2')]),
2057
], [target1, target2], [basis1, basis2])
2699
[target1, target2, a_key, aac_key, b_key, bba_key],
2700
[(('aac',), 'target1'), (('bba',), 'target2')],
2701
[target1, target2], [basis1, basis2])
2703
def test_multiple_maps_overlapping_common_new(self):
2704
# Test that when a node found through the interesting_keys iteration
2705
# for *some roots* and also via the old keys iteration, that
2706
# it is still scanned for old refs and items, because its
2707
# not truely new. This requires 2 levels of InternalNodes to expose,
2708
# because of the way the bootstrap in _find_children_info works.
2709
# This suggests that the code is probably amenable to/benefit from
2711
# How does this test work?
2712
# 1) We need a second level InternalNode present in a basis tree.
2713
# 2) We need a left side new tree that uses that InternalNode
2714
# 3) We need a right side new tree that does not use that InternalNode
2715
# at all but that has an unchanged *value* that was reachable inside
2717
basis = self.get_map_key({
2718
# InternalNode, unchanged in left:
2721
# Forces an internalNode at 'a'
2724
left = self.get_map_key({
2725
# All of basis unchanged
2729
# And a new top level node so the root key is different
2732
right = self.get_map_key({
2733
# A value that is unchanged from basis and thus should be filtered
2737
basis_map = CHKMap(self.get_chk_bytes(), basis)
2738
self.assertEqualDiff(
2740
" 'a' InternalNode\n"
2742
" ('aaa',) 'left'\n"
2744
" ('abb',) 'right'\n"
2746
" ('ccc',) 'common'\n",
2747
basis_map._dump_tree())
2748
# Get left expected data
2749
left_map = CHKMap(self.get_chk_bytes(), left)
2750
self.assertEqualDiff(
2752
" 'a' InternalNode\n"
2754
" ('aaa',) 'left'\n"
2756
" ('abb',) 'right'\n"
2758
" ('ccc',) 'common'\n"
2760
" ('ddd',) 'change'\n",
2761
left_map._dump_tree())
2762
# Keys from left side target
2763
l_d_key = left_map._root_node._items['d'].key()
2764
# Get right expected data
2765
right_map = CHKMap(self.get_chk_bytes(), right)
2766
self.assertEqualDiff(
2768
" ('abb',) 'right'\n",
2769
right_map._dump_tree())
2770
# Keys from the right side target - none, the root is enough.
2772
self.assertIterInteresting(
2773
[right, left, l_d_key],
2774
[(('ddd',), 'change')],
2775
[left, right], [basis])
2777
def test_multiple_maps_similar(self):
2778
# We want to have a depth=2 tree, with multiple entries in each leaf
2780
basis = self.get_map_key({
2781
('aaa',): 'unchanged',
2782
('abb',): 'will change left',
2783
('caa',): 'unchanged',
2784
('cbb',): 'will change right',
2786
left = self.get_map_key({
2787
('aaa',): 'unchanged',
2788
('abb',): 'changed left',
2789
('caa',): 'unchanged',
2790
('cbb',): 'will change right',
2792
right = self.get_map_key({
2793
('aaa',): 'unchanged',
2794
('abb',): 'will change left',
2795
('caa',): 'unchanged',
2796
('cbb',): 'changed right',
2798
basis_map = CHKMap(self.get_chk_bytes(), basis)
2799
self.assertEqualDiff(
2802
" ('aaa',) 'unchanged'\n"
2803
" ('abb',) 'will change left'\n"
2805
" ('caa',) 'unchanged'\n"
2806
" ('cbb',) 'will change right'\n",
2807
basis_map._dump_tree())
2808
# Get left expected data
2809
left_map = CHKMap(self.get_chk_bytes(), left)
2810
self.assertEqualDiff(
2813
" ('aaa',) 'unchanged'\n"
2814
" ('abb',) 'changed left'\n"
2816
" ('caa',) 'unchanged'\n"
2817
" ('cbb',) 'will change right'\n",
2818
left_map._dump_tree())
2819
# Keys from left side target
2820
l_a_key = left_map._root_node._items['a'].key()
2821
l_c_key = left_map._root_node._items['c'].key()
2822
# Get right expected data
2823
right_map = CHKMap(self.get_chk_bytes(), right)
2824
self.assertEqualDiff(
2827
" ('aaa',) 'unchanged'\n"
2828
" ('abb',) 'will change left'\n"
2830
" ('caa',) 'unchanged'\n"
2831
" ('cbb',) 'changed right'\n",
2832
right_map._dump_tree())
2833
r_a_key = right_map._root_node._items['a'].key()
2834
r_c_key = right_map._root_node._items['c'].key()
2835
self.assertIterInteresting(
2836
[right, left, l_a_key, r_c_key],
2837
[(('abb',), 'changed left'), (('cbb',), 'changed right')],
2838
[left, right], [basis])
added
removed
bzrlib/tests/test_chk_map.py
