/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_chk_map.py

  • Committer: Jonathan Lange
  • Date: 2009-12-09 09:20:42 UTC
  • mfrom: (4881 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4907.
  • Revision ID: jml@canonical.com-20091209092042-s2zgqcf8f39yzxpj
Merge trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_chk_map.py
20
20
 
21
21
from bzrlib import (
22
22
    chk_map,
 
23
    errors,
 
24
    groupcompress,
23
25
    osutils,
24
26
    tests,
25
27
    )
29
31
    LeafNode,
30
32
    Node,
31
33
    )
 
34
from bzrlib.static_tuple import StaticTuple
32
35
 
33
36
 
34
37
class TestNode(tests.TestCase):
59
62
        self.assertCommonPrefix('', '', '')
60
63
 
61
64
 
62
 
class TestCaseWithStore(tests.TestCaseWithTransport):
 
65
class TestCaseWithStore(tests.TestCaseWithMemoryTransport):
63
66
 
64
67
    def get_chk_bytes(self):
65
 
        # The easiest way to get a CHK store is a development6 repository and
66
 
        # then work with the chk_bytes attribute directly.
67
 
        repo = self.make_repository(".", format="development6-rich-root")
68
 
        repo.lock_write()
69
 
        self.addCleanup(repo.unlock)
70
 
        repo.start_write_group()
71
 
        self.addCleanup(repo.abort_write_group)
72
 
        return repo.chk_bytes
 
68
        # This creates a standalone CHK store.
 
69
        factory = groupcompress.make_pack_factory(False, False, 1)
 
70
        self.chk_bytes = factory(self.get_transport())
 
71
        return self.chk_bytes
73
72
 
74
73
    def _get_map(self, a_dict, maximum_size=0, chk_bytes=None, key_width=1,
75
74
                 search_key_func=None):
97
96
        return dict(node.iteritems(*args))
98
97
 
99
98
 
 
99
class TestCaseWithExampleMaps(TestCaseWithStore):
 
100
 
 
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
 
106
 
 
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)
 
111
        return c_map
 
112
 
 
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)
 
118
 
 
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)
 
124
 
 
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)
 
133
 
 
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)
 
149
 
 
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.
 
152
 
 
153
        Otherwise has similar content to make_two_deep_map.
 
154
        """
 
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)
 
161
 
 
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.
 
164
 
 
165
        Similar to make_one_deep_two_prefix_map, except the split is at the
 
166
        first char, rather than the second.
 
167
        """
 
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)
 
174
 
 
175
 
 
176
class TestTestCaseWithExampleMaps(TestCaseWithExampleMaps):
 
177
    """Actual tests for the provided examples."""
 
178
 
 
179
    def test_root_only_map_plain(self):
 
180
        c_map = self.make_root_only_map()
 
181
        self.assertEqualDiff(
 
182
            "'' LeafNode\n"
 
183
            "      ('aaa',) 'initial aaa content'\n"
 
184
            "      ('abb',) 'initial abb content'\n",
 
185
            c_map._dump_tree())
 
186
 
 
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(
 
190
            "'' LeafNode\n"
 
191
            "      ('aaa',) 'initial aaa content'\n"
 
192
            "      ('abb',) 'initial abb content'\n",
 
193
            c_map._dump_tree())
 
194
 
 
195
    def test_one_deep_map_plain(self):
 
196
        c_map = self.make_one_deep_map()
 
197
        self.assertEqualDiff(
 
198
            "'' InternalNode\n"
 
199
            "  'a' LeafNode\n"
 
200
            "      ('aaa',) 'initial aaa content'\n"
 
201
            "      ('abb',) 'initial abb content'\n"
 
202
            "  'c' LeafNode\n"
 
203
            "      ('ccc',) 'initial ccc content'\n"
 
204
            "  'd' LeafNode\n"
 
205
            "      ('ddd',) 'initial ddd content'\n",
 
206
            c_map._dump_tree())
 
207
 
 
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(
 
211
            "'' InternalNode\n"
 
212
            "  '2' LeafNode\n"
 
213
            "      ('ccc',) 'initial ccc content'\n"
 
214
            "  '4' LeafNode\n"
 
215
            "      ('abb',) 'initial abb content'\n"
 
216
            "  'F' LeafNode\n"
 
217
            "      ('aaa',) 'initial aaa content'\n"
 
218
            "      ('ddd',) 'initial ddd content'\n",
 
219
            c_map._dump_tree())
 
220
 
 
221
    def test_root_only_aaa_ddd_plain(self):
 
222
        c_map = self.make_root_only_aaa_ddd_map()
 
223
        self.assertEqualDiff(
 
224
            "'' LeafNode\n"
 
225
            "      ('aaa',) 'initial aaa content'\n"
 
226
            "      ('ddd',) 'initial ddd content'\n",
 
227
            c_map._dump_tree())
 
228
 
 
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
 
233
        # _search_key_16
 
234
        self.assertEqualDiff(
 
235
            "'' LeafNode\n"
 
236
            "      ('aaa',) 'initial aaa content'\n"
 
237
            "      ('ddd',) 'initial ddd content'\n",
 
238
            c_map._dump_tree())
 
239
 
 
240
    def test_two_deep_map_plain(self):
 
241
        c_map = self.make_two_deep_map()
 
242
        self.assertEqualDiff(
 
243
            "'' InternalNode\n"
 
244
            "  'a' InternalNode\n"
 
245
            "    'aa' LeafNode\n"
 
246
            "      ('aaa',) 'initial aaa content'\n"
 
247
            "    'ab' LeafNode\n"
 
248
            "      ('abb',) 'initial abb content'\n"
 
249
            "    'ac' LeafNode\n"
 
250
            "      ('acc',) 'initial acc content'\n"
 
251
            "      ('ace',) 'initial ace content'\n"
 
252
            "    'ad' LeafNode\n"
 
253
            "      ('add',) 'initial add content'\n"
 
254
            "      ('adh',) 'initial adh content'\n"
 
255
            "      ('adl',) 'initial adl content'\n"
 
256
            "  'c' LeafNode\n"
 
257
            "      ('ccc',) 'initial ccc content'\n"
 
258
            "  'd' LeafNode\n"
 
259
            "      ('ddd',) 'initial ddd content'\n",
 
260
            c_map._dump_tree())
 
261
 
 
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(
 
265
            "'' InternalNode\n"
 
266
            "  '2' LeafNode\n"
 
267
            "      ('acc',) 'initial acc content'\n"
 
268
            "      ('ccc',) 'initial ccc content'\n"
 
269
            "  '4' LeafNode\n"
 
270
            "      ('abb',) 'initial abb content'\n"
 
271
            "  'C' LeafNode\n"
 
272
            "      ('ace',) 'initial ace content'\n"
 
273
            "  'F' InternalNode\n"
 
274
            "    'F0' LeafNode\n"
 
275
            "      ('aaa',) 'initial aaa content'\n"
 
276
            "    'F3' LeafNode\n"
 
277
            "      ('adl',) 'initial adl content'\n"
 
278
            "    'F4' LeafNode\n"
 
279
            "      ('adh',) 'initial adh content'\n"
 
280
            "    'FB' LeafNode\n"
 
281
            "      ('ddd',) 'initial ddd content'\n"
 
282
            "    'FD' LeafNode\n"
 
283
            "      ('add',) 'initial add content'\n",
 
284
            c_map._dump_tree())
 
285
 
 
286
    def test_one_deep_two_prefix_map_plain(self):
 
287
        c_map = self.make_one_deep_two_prefix_map()
 
288
        self.assertEqualDiff(
 
289
            "'' InternalNode\n"
 
290
            "  'aa' LeafNode\n"
 
291
            "      ('aaa',) 'initial aaa content'\n"
 
292
            "  'ad' LeafNode\n"
 
293
            "      ('add',) 'initial add content'\n"
 
294
            "      ('adh',) 'initial adh content'\n"
 
295
            "      ('adl',) 'initial adl content'\n",
 
296
            c_map._dump_tree())
 
297
 
 
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(
 
302
            "'' InternalNode\n"
 
303
            "  'F0' LeafNode\n"
 
304
            "      ('aaa',) 'initial aaa content'\n"
 
305
            "  'F3' LeafNode\n"
 
306
            "      ('adl',) 'initial adl content'\n"
 
307
            "  'F4' LeafNode\n"
 
308
            "      ('adh',) 'initial adh content'\n"
 
309
            "  'FD' LeafNode\n"
 
310
            "      ('add',) 'initial add content'\n",
 
311
            c_map._dump_tree())
 
312
 
 
313
    def test_one_deep_one_prefix_map_plain(self):
 
314
        c_map = self.make_one_deep_one_prefix_map()
 
315
        self.assertEqualDiff(
 
316
            "'' InternalNode\n"
 
317
            "  'a' LeafNode\n"
 
318
            "      ('add',) 'initial add content'\n"
 
319
            "      ('adh',) 'initial adh content'\n"
 
320
            "      ('adl',) 'initial adl content'\n"
 
321
            "  'b' LeafNode\n"
 
322
            "      ('bbb',) 'initial bbb content'\n",
 
323
            c_map._dump_tree())
 
324
 
 
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(
 
329
            "'' InternalNode\n"
 
330
            "  '4' LeafNode\n"
 
331
            "      ('bbb',) 'initial bbb content'\n"
 
332
            "  'F' LeafNode\n"
 
333
            "      ('add',) 'initial add content'\n"
 
334
            "      ('adh',) 'initial adh content'\n"
 
335
            "      ('adl',) 'initial adl content'\n",
 
336
            c_map._dump_tree())
 
337
 
 
338
 
100
339
class TestMap(TestCaseWithStore):
101
340
 
102
341
    def assertHasABMap(self, chk_bytes):
228
467
        # updated key.
229
468
        self.assertEqual(new_root, chkmap._root_node._key)
230
469
 
 
470
    def test_apply_new_keys_must_be_new(self):
 
471
        # applying a delta (None, "a", "b") to a map with 'a' in it generates
 
472
        # an error.
 
473
        chk_bytes = self.get_chk_bytes()
 
474
        root_key = CHKMap.from_dict(chk_bytes, {("a",):"b"})
 
475
        chkmap = CHKMap(chk_bytes, root_key)
 
476
        self.assertRaises(errors.InconsistentDelta, chkmap.apply_delta,
 
477
            [(None, ("a",), "b")])
 
478
        # As an error occured, the update should have left us without changing
 
479
        # anything (the root should be unchanged).
 
480
        self.assertEqual(root_key, chkmap._root_node._key)
 
481
 
231
482
    def test_apply_delta_is_deterministic(self):
232
483
        chk_bytes = self.get_chk_bytes()
233
484
        chkmap1 = CHKMap(chk_bytes, None)
581
832
        # 'ab' and 'ac' nodes
582
833
        chkmap.map(('aad',), 'v')
583
834
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
584
 
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
585
 
        self.assertIsInstance(chkmap._root_node._items['ac'], tuple)
 
835
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
 
836
        self.assertIsInstance(chkmap._root_node._items['ac'], StaticTuple)
586
837
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
587
838
        # to map in 'ab'
588
839
        chkmap.unmap(('acd',))
589
840
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
590
 
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
 
841
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
591
842
 
592
843
    def test_unmap_without_fitting_doesnt_page_in(self):
593
844
        store = self.get_chk_bytes()
610
861
        chkmap.map(('aaf',), 'v')
611
862
        # At this point, the previous nodes should not be paged in, but the
612
863
        # newly added nodes would be
613
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
614
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
864
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
865
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
615
866
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
616
867
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
617
868
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
619
870
        # Now unmapping one of the new nodes will use only the already-paged-in
620
871
        # nodes to determine that we don't need to do more.
621
872
        chkmap.unmap(('aaf',))
622
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
623
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
873
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
874
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
624
875
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
625
876
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
626
877
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
647
898
        chkmap.map(('aad',), 'v')
648
899
        # At this point, the previous nodes should not be paged in, but the
649
900
        # newly added node would be
650
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
651
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
652
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
901
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
902
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
903
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
653
904
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
654
905
        # Unmapping the new node will check the existing nodes to see if they
655
906
        # would fit.
687
938
        chkmap.map(('aad',), 'v')
688
939
        # At this point, the previous nodes should not be paged in, but the
689
940
        # newly added node would be
690
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
691
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
692
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
941
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
942
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
943
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
693
944
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
694
945
        # Now clear the page cache, and only include 2 of the children in the
695
946
        # cache
704
955
        # Unmapping the new node will check the nodes from the page cache
705
956
        # first, and not have to read in 'aaa'
706
957
        chkmap.unmap(('aad',))
707
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
958
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
708
959
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
709
960
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
710
961
 
724
975
        chkmap.map(('aaf',), 'val')
725
976
        # At this point, the previous nodes should not be paged in, but the
726
977
        # newly added node would be
727
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
728
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
729
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
978
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
979
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
980
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
730
981
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
731
982
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
732
983
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
734
985
        # Unmapping a new node will see the other nodes that are already in
735
986
        # memory, and not need to page in anything else
736
987
        chkmap.unmap(('aad',))
737
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
738
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
739
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
988
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
989
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
990
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
740
991
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
741
992
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
742
993
 
781
1032
            {('a',): 'content here', ('b',): 'more content'},
782
1033
            chk_bytes=basis._store, maximum_size=10)
783
1034
        list(target.iter_changes(basis))
784
 
        self.assertIsInstance(target._root_node, tuple)
785
 
        self.assertIsInstance(basis._root_node, tuple)
 
1035
        self.assertIsInstance(target._root_node, StaticTuple)
 
1036
        self.assertIsInstance(basis._root_node, StaticTuple)
786
1037
 
787
1038
    def test_iter_changes_ab_ab_changed_values_shown(self):
788
1039
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
894
1145
 
895
1146
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
896
1147
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
897
 
        self.assertEqual('E8B7BE43\x00E8B7BE43', search_key_func(('a', 'a')))
898
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
899
 
        self.assertEqual('71BEEFF9\x0000000000', search_key_func(('b', '')))
 
1148
        self.assertEqual('E8B7BE43\x00E8B7BE43',
 
1149
                         search_key_func(StaticTuple('a', 'a')))
 
1150
        self.assertEqual('E8B7BE43\x0071BEEFF9',
 
1151
                         search_key_func(StaticTuple('a', 'b')))
 
1152
        self.assertEqual('71BEEFF9\x0000000000',
 
1153
                         search_key_func(StaticTuple('b', '')))
900
1154
        chkmap = self._get_map(
901
1155
            {("a","a"):"content here", ("a", "b",):"more content",
902
1156
             ("b", ""): 'boring content'},
1199
1453
                             , chkmap._dump_tree())
1200
1454
 
1201
1455
 
1202
 
class TestSearchKeyFuncs(tests.TestCase):
1203
 
 
1204
 
    def assertSearchKey16(self, expected, key):
1205
 
        self.assertEqual(expected, chk_map._search_key_16(key))
1206
 
 
1207
 
    def assertSearchKey255(self, expected, key):
1208
 
        actual = chk_map._search_key_255(key)
1209
 
        self.assertEqual(expected, actual, 'actual: %r' % (actual,))
1210
 
 
1211
 
    def test_simple_16(self):
1212
 
        self.assertSearchKey16('8C736521', ('foo',))
1213
 
        self.assertSearchKey16('8C736521\x008C736521', ('foo', 'foo'))
1214
 
        self.assertSearchKey16('8C736521\x0076FF8CAA', ('foo', 'bar'))
1215
 
        self.assertSearchKey16('ED82CD11', ('abcd',))
1216
 
 
1217
 
    def test_simple_255(self):
1218
 
        self.assertSearchKey255('\x8cse!', ('foo',))
1219
 
        self.assertSearchKey255('\x8cse!\x00\x8cse!', ('foo', 'foo'))
1220
 
        self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', ('foo', 'bar'))
1221
 
        # The standard mapping for these would include '\n', so it should be
1222
 
        # mapped to '_'
1223
 
        self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
1224
 
 
1225
 
    def test_255_does_not_include_newline(self):
1226
 
        # When mapping via _search_key_255, we should never have the '\n'
1227
 
        # character, but all other 255 values should be present
1228
 
        chars_used = set()
1229
 
        for char_in in range(256):
1230
 
            search_key = chk_map._search_key_255((chr(char_in),))
1231
 
            chars_used.update(search_key)
1232
 
        all_chars = set([chr(x) for x in range(256)])
1233
 
        unused_chars = all_chars.symmetric_difference(chars_used)
1234
 
        self.assertEqual(set('\n'), unused_chars)
1235
 
 
1236
 
 
1237
1456
class TestLeafNode(TestCaseWithStore):
1238
1457
 
1239
1458
    def test_current_size_empty(self):
1658
1877
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1659
1878
        node = InternalNode(search_key_func=search_key_func)
1660
1879
        leaf1 = LeafNode(search_key_func=search_key_func)
1661
 
        leaf1.map(None, ('foo bar',), 'quux')
 
1880
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
1662
1881
        leaf2 = LeafNode(search_key_func=search_key_func)
1663
 
        leaf2.map(None, ('strange',), 'beast')
1664
 
        self.assertEqual('\xbeF\x014', search_key_func(('foo bar',)))
1665
 
        self.assertEqual('\x85\xfa\xf7K', search_key_func(('strange',)))
 
1882
        leaf2.map(None, StaticTuple('strange',), 'beast')
 
1883
        self.assertEqual('\xbeF\x014', search_key_func(StaticTuple('foo bar',)))
 
1884
        self.assertEqual('\x85\xfa\xf7K', search_key_func(StaticTuple('strange',)))
1666
1885
        node.add_node("\xbe", leaf1)
1667
1886
        # This sets up a path that should not be followed - it will error if
1668
1887
        # the code tries to.
1669
1888
        node._items['\xbe'] = None
1670
1889
        node.add_node("\x85", leaf2)
1671
1890
        self.assertEqual([(('strange',), 'beast')],
1672
 
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
 
1891
            sorted(node.iteritems(None, [StaticTuple('strange',),
 
1892
                                         StaticTuple('weird',)])))
1673
1893
 
1674
1894
    def test_iteritems_partial_empty(self):
1675
1895
        node = InternalNode()
1682
1902
        # Ensure test validity: nothing paged in below the root.
1683
1903
        self.assertEqual(2,
1684
1904
            len([value for value in node._items.values()
1685
 
                if type(value) == tuple]))
 
1905
                if type(value) is StaticTuple]))
1686
1906
        # now, mapping to k3 should add a k3 leaf
1687
1907
        prefix, nodes = node.map(None, ('k3',), 'quux')
1688
1908
        self.assertEqual("k", prefix)
1721
1941
        # Ensure test validity: nothing paged in below the root.
1722
1942
        self.assertEqual(2,
1723
1943
            len([value for value in node._items.values()
1724
 
                if type(value) == tuple]))
 
1944
                if type(value) is StaticTuple]))
1725
1945
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1726
1946
        # k23, which for simplicity in the current implementation generates
1727
1947
        # a new internal node between node, and k22/k23.
1766
1986
        node = InternalNode(search_key_func=search_key_func)
1767
1987
        node._key_width = 2
1768
1988
        node._node_width = 4
1769
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
1770
 
        self.assertEqual('E8B7', node._search_prefix_filter(('a', 'b')))
1771
 
        self.assertEqual('E8B7', node._search_prefix_filter(('a',)))
 
1989
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(
 
1990
            StaticTuple('a', 'b')))
 
1991
        self.assertEqual('E8B7', node._search_prefix_filter(
 
1992
            StaticTuple('a', 'b')))
 
1993
        self.assertEqual('E8B7', node._search_prefix_filter(
 
1994
            StaticTuple('a',)))
1772
1995
 
1773
1996
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
1774
1997
        chkmap = self._get_map(
1886
2109
# 1-4K get0
1887
2110
 
1888
2111
 
1889
 
class TestIterInterestingNodes(TestCaseWithStore):
1890
 
 
1891
 
    def get_chk_bytes(self):
1892
 
        if getattr(self, '_chk_bytes', None) is None:
1893
 
            self._chk_bytes = super(TestIterInterestingNodes,
1894
 
                                    self).get_chk_bytes()
1895
 
        return self._chk_bytes
 
2112
class TestCHKMapDifference(TestCaseWithExampleMaps):
 
2113
 
 
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)
 
2120
 
 
2121
    def test__init__(self):
 
2122
        c_map = self.make_root_only_map()
 
2123
        key1 = c_map.key()
 
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)
 
2130
 
 
2131
    def help__read_all_roots(self, search_key_func):
 
2132
        c_map = self.make_root_only_map(search_key_func=search_key_func)
 
2133
        key1 = c_map.key()
 
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
 
2140
        # set
 
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
 
2145
        # empty
 
2146
        self.assertEqual([], diff._old_queue)
 
2147
 
 
2148
    def test__read_all_roots_plain(self):
 
2149
        self.help__read_all_roots(search_key_func=chk_map._search_key_plain)
 
2150
 
 
2151
    def test__read_all_roots_16(self):
 
2152
        self.help__read_all_roots(search_key_func=chk_map._search_key_16)
 
2153
 
 
2154
    def test__read_all_roots_skips_known_old(self):
 
2155
        c_map = self.make_one_deep_map(chk_map._search_key_plain)
 
2156
        key1 = c_map.key()
 
2157
        c_map2 = self.make_root_only_map(chk_map._search_key_plain)
 
2158
        key2 = c_map2.key()
 
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)
 
2164
 
 
2165
    def test__read_all_roots_prepares_queues(self):
 
2166
        c_map = self.make_one_deep_map(chk_map._search_key_plain)
 
2167
        key1 = c_map.key()
 
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)
 
2181
 
 
2182
    def test__read_all_roots_multi_new_prepares_queues(self):
 
2183
        c_map = self.make_one_deep_map(chk_map._search_key_plain)
 
2184
        key1 = c_map.key()
 
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)
 
2207
 
 
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
 
2211
        key1 = c_map.key()
 
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()
 
2215
 
 
2216
        c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
 
2217
        c_map2._dump_tree()
 
2218
        key2 = c_map2.key()
 
2219
        key2_aa = c_map2._root_node._items['aa'].key()
 
2220
        key2_ad = c_map2._root_node._items['ad'].key()
 
2221
 
 
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
 
2226
        # present
 
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)
 
2230
 
 
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)
 
2234
 
 
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)
 
2238
 
 
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
 
2242
        key1 = c_map.key()
 
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()
 
2247
 
 
2248
        c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_16)
 
2249
        c_map2._dump_tree()
 
2250
        key2 = c_map2.key()
 
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()
 
2255
 
 
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)
 
2264
 
 
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)
 
2268
 
 
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)
 
2274
 
 
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
 
2278
        key1 = c_map.key()
 
2279
        key1_aa = c_map._root_node._items['aa'].key()
 
2280
        key1_ad = c_map._root_node._items['ad'].key()
 
2281
 
 
2282
        c_map2 = self.make_one_deep_one_prefix_map(chk_map._search_key_plain)
 
2283
        c_map2._dump_tree()
 
2284
        key2 = c_map2.key()
 
2285
        key2_a = c_map2._root_node._items['a'].key()
 
2286
        key2_b = c_map2._root_node._items['b'].key()
 
2287
 
 
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)
 
2296
 
 
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)
 
2310
 
 
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
 
2319
        # buffering.
 
2320
        c_map = self.make_two_deep_map(chk_map._search_key_plain)
 
2321
        c_map._dump_tree() # load all keys
 
2322
        key1 = c_map.key()
 
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(
 
2329
            "'' LeafNode\n"
 
2330
            "      ('acc',) 'initial acc content'\n"
 
2331
            "      ('ace',) 'initial ace content'\n",
 
2332
            c_map2._dump_tree())
 
2333
        key2 = c_map2.key()
 
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)
 
2344
 
 
2345
    def test__read_all_roots_multiple_targets(self):
 
2346
        c_map = self.make_root_only_map()
 
2347
        key1 = c_map.key()
 
2348
        c_map = self.make_one_deep_map()
 
2349
        key2 = c_map.key()
 
2350
        c_map._dump_tree()
 
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)
 
2366
 
 
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()
 
2372
        key1 = c_map.key()
 
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)
 
2379
 
 
2380
        c_map2 = self.make_one_deep_map()
 
2381
        key2 = c_map2.key()
 
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)
 
2388
 
 
2389
    def test__read_all_roots_no_old_16(self):
 
2390
        c_map = self.make_two_deep_map(chk_map._search_key_16)
 
2391
        key1 = c_map.key()
 
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)
 
2398
 
 
2399
        c_map2 = self.make_one_deep_map(chk_map._search_key_16)
 
2400
        key2 = c_map2.key()
 
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)
 
2409
 
 
2410
    def test__read_all_roots_multiple_old(self):
 
2411
        c_map = self.make_two_deep_map()
 
2412
        key1 = c_map.key()
 
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
 
2426
        # identical
 
2427
        self.assertEqual([key1_a], diff._old_queue)
 
2428
        self.assertEqual([key3_a], diff._new_queue)
 
2429
        self.assertEqual([], diff._new_item_queue)
 
2430
 
 
2431
    def test__process_next_old_batched_no_dupes(self):
 
2432
        c_map = self.make_two_deep_map()
 
2433
        key1 = c_map.key()
 
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))
 
2461
 
 
2462
 
 
2463
class TestIterInterestingNodes(TestCaseWithExampleMaps):
1896
2464
 
1897
2465
    def get_map_key(self, a_dict, maximum_size=10):
1898
 
        c_map = self._get_map(a_dict, maximum_size=maximum_size,
1899
 
                              chk_bytes=self.get_chk_bytes())
 
2466
        c_map = self.get_map(a_dict, maximum_size=maximum_size)
1900
2467
        return c_map.key()
1901
2468
 
1902
 
    def assertIterInteresting(self, expected, interesting_keys,
1903
 
                              uninteresting_keys):
 
2469
    def assertIterInteresting(self, records, items, interesting_keys,
 
2470
                              old_keys):
1904
2471
        """Check the result of iter_interesting_nodes.
1905
2472
 
1906
 
        :param expected: A list of (record_keys, interesting_chk_pages,
1907
 
                                    interesting key value pairs)
 
2473
        Note that we no longer care how many steps are taken, etc, just that
 
2474
        the right contents are returned.
 
2475
 
 
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.
1908
2478
        """
1909
2479
        store = self.get_chk_bytes()
 
2480
        store._search_key_func = chk_map._search_key_plain
1910
2481
        iter_nodes = chk_map.iter_interesting_nodes(store, interesting_keys,
1911
 
                                                    uninteresting_keys)
1912
 
        nodes = list(iter_nodes)
1913
 
        for count, (exp, act) in enumerate(izip(expected, nodes)):
1914
 
            exp_record, exp_items = exp
1915
 
            record, items = act
1916
 
            exp_tuple = (exp_record, sorted(exp_items))
1917
 
            if record is None:
1918
 
                act_tuple = (None, sorted(items))
1919
 
            else:
1920
 
                act_tuple = (record.key, sorted(items))
1921
 
            self.assertEqual(exp_tuple, act_tuple,
1922
 
                             'entry %d did not match expected' % count)
1923
 
        self.assertEqual(len(expected), len(nodes))
 
2482
                                                    old_keys)
 
2483
        record_keys = []
 
2484
        all_items = []
 
2485
        for record, new_items in iter_nodes:
 
2486
            if record is not None:
 
2487
                record_keys.append(record.key)
 
2488
            if new_items:
 
2489
                all_items.extend(new_items)
 
2490
        self.assertEqual(sorted(records), sorted(record_keys))
 
2491
        self.assertEqual(sorted(items), sorted(all_items))
1924
2492
 
1925
2493
    def test_empty_to_one_keys(self):
1926
2494
        target = self.get_map_key({('a',): 'content'})
1927
 
        self.assertIterInteresting(
1928
 
            [(target, [(('a',), 'content')]),
1929
 
            ], [target], [])
 
2495
        self.assertIterInteresting([target],
 
2496
                                   [(('a',), 'content')],
 
2497
                                   [target], [])
1930
2498
 
1931
2499
    def test_none_to_one_key(self):
1932
2500
        basis = self.get_map_key({})
1933
2501
        target = self.get_map_key({('a',): 'content'})
1934
 
        self.assertIterInteresting(
1935
 
            [(None, [(('a',), 'content')]),
1936
 
             (target, []),
1937
 
            ], [target], [basis])
 
2502
        self.assertIterInteresting([target],
 
2503
                                   [(('a',), 'content')],
 
2504
                                   [target], [basis])
1938
2505
 
1939
2506
    def test_one_to_none_key(self):
1940
2507
        basis = self.get_map_key({('a',): 'content'})
1941
2508
        target = self.get_map_key({})
1942
 
        self.assertIterInteresting(
1943
 
            [(target, [])],
1944
 
            [target], [basis])
 
2509
        self.assertIterInteresting([target],
 
2510
                                   [],
 
2511
                                   [target], [basis])
1945
2512
 
1946
2513
    def test_common_pages(self):
1947
2514
        basis = self.get_map_key({('a',): 'content',
1964
2531
            target_map._dump_tree())
1965
2532
        b_key = target_map._root_node._items['b'].key()
1966
2533
        # This should return the root node, and the node for the 'b' key
1967
 
        self.assertIterInteresting(
1968
 
            [(target, []),
1969
 
             (b_key, [(('b',), 'other content')])],
1970
 
            [target], [basis])
 
2534
        self.assertIterInteresting([target, b_key],
 
2535
                                   [(('b',), 'other content')],
 
2536
                                   [target], [basis])
1971
2537
 
1972
2538
    def test_common_sub_page(self):
1973
2539
        basis = self.get_map_key({('aaa',): 'common',
1991
2557
        # The key for the internal aa node
1992
2558
        a_key = target_map._root_node._items['a'].key()
1993
2559
        # The key for the leaf aab node
 
2560
        # aaa_key = target_map._root_node._items['a']._items['aaa'].key()
1994
2561
        aab_key = target_map._root_node._items['a']._items['aab'].key()
1995
 
        self.assertIterInteresting(
1996
 
            [(target, []),
1997
 
             (a_key, []),
1998
 
             (aab_key, [(('aab',), 'new')])],
1999
 
            [target], [basis])
 
2562
        self.assertIterInteresting([target, a_key, aab_key],
 
2563
                                   [(('aab',), 'new')],
 
2564
                                   [target], [basis])
2000
2565
 
2001
2566
    def test_common_leaf(self):
2002
2567
        basis = self.get_map_key({})
2040
2605
        a_key = target3_map._root_node._items['a'].key()
2041
2606
        aac_key = target3_map._root_node._items['a']._items['aac'].key()
2042
2607
        self.assertIterInteresting(
2043
 
            [(None, [(('aaa',), 'common')]),
2044
 
             (target1, []),
2045
 
             (target2, []),
2046
 
             (target3, []),
2047
 
             (b_key, [(('bbb',), 'new')]),
2048
 
             (a_key, []),
2049
 
             (aac_key, [(('aac',), 'other')]),
2050
 
            ], [target1, target2, target3], [basis])
2051
 
 
2052
 
        self.assertIterInteresting(
2053
 
            [(target2, []),
2054
 
             (target3, []),
2055
 
             (b_key, [(('bbb',), 'new')]),
2056
 
             (a_key, []),
2057
 
             (aac_key, [(('aac',), 'other')]),
2058
 
            ], [target2, target3], [target1])
2059
 
 
2060
 
        # This may be a case that we relax. A root node is a deep child of the
2061
 
        # excluded set. The cost is buffering root nodes until we have
2062
 
        # determined all possible exclusions. (Because a prefix of '', cannot
2063
 
        # be excluded.)
2064
 
        self.assertIterInteresting(
2065
 
            [], [target1], [target3])
 
2608
            [target1, target2, target3, a_key, aac_key, b_key],
 
2609
            [(('aaa',), 'common'), (('bbb',), 'new'), (('aac',), 'other')],
 
2610
            [target1, target2, target3], [basis])
 
2611
 
 
2612
        self.assertIterInteresting(
 
2613
            [target2, target3, a_key, aac_key, b_key],
 
2614
            [(('bbb',), 'new'), (('aac',), 'other')],
 
2615
            [target2, target3], [target1])
 
2616
 
 
2617
        # Technically, target1 could be filtered out, but since it is a root
 
2618
        # node, we yield it immediately, rather than waiting to find out much
 
2619
        # later on.
 
2620
        self.assertIterInteresting(
 
2621
            [target1],
 
2622
            [],
 
2623
            [target1], [target3])
2066
2624
 
2067
2625
    def test_multiple_maps(self):
2068
2626
        basis1 = self.get_map_key({('aaa',): 'common',
2111
2669
        # The key for the leaf bba node
2112
2670
        bba_key = target2_map._root_node._items['b']._items['bba'].key()
2113
2671
        self.assertIterInteresting(
2114
 
            [(target1, []),
2115
 
             (target2, []),
2116
 
             (a_key, []),
2117
 
             (b_key, []),
2118
 
             (aac_key, [(('aac',), 'target1')]),
2119
 
             (bba_key, [(('bba',), 'target2')]),
2120
 
            ], [target1, target2], [basis1, basis2])
 
2672
            [target1, target2, a_key, aac_key, b_key, bba_key],
 
2673
            [(('aac',), 'target1'), (('bba',), 'target2')],
 
2674
            [target1, target2], [basis1, basis2])
2121
2675
 
2122
2676
    def test_multiple_maps_overlapping_common_new(self):
2123
2677
        # Test that when a node found through the interesting_keys iteration
2124
 
        # for *some roots* and also via the uninteresting keys iteration, that
2125
 
        # it is still scanned for uninteresting refs and items, because its
 
2678
        # for *some roots* and also via the old keys iteration, that
 
2679
        # it is still scanned for old refs and items, because its
2126
2680
        # not truely new. This requires 2 levels of InternalNodes to expose,
2127
2681
        # because of the way the bootstrap in _find_children_info works.
2128
2682
        # This suggests that the code is probably amenable to/benefit from
2188
2742
            right_map._dump_tree())
2189
2743
        # Keys from the right side target - none, the root is enough.
2190
2744
        # Test behaviour
2191
 
        self.expectFailure("we don't properly filter different depths",
2192
 
            self.assertIterInteresting,
2193
 
            [(left, []),
2194
 
             (right, []),
2195
 
             (l_d_key, [(('ddd',), 'change')]),
2196
 
            ], [left, right], [basis])
2197
2745
        self.assertIterInteresting(
2198
 
            [(left, []),
2199
 
             (right, []),
2200
 
             (l_d_key, [(('ddd',), 'change')]),
2201
 
            ], [left, right], [basis])
 
2746
            [right, left, l_d_key],
 
2747
            [(('ddd',), 'change')],
 
2748
            [left, right], [basis])
2202
2749
 
2203
2750
    def test_multiple_maps_similar(self):
2204
2751
        # We want to have a depth=2 tree, with multiple entries in each leaf
2259
2806
        r_a_key = right_map._root_node._items['a'].key()
2260
2807
        r_c_key = right_map._root_node._items['c'].key()
2261
2808
        self.assertIterInteresting(
2262
 
            [(left, []),
2263
 
             (right, []),
2264
 
             (l_a_key, [(('abb',), 'changed left')]),
2265
 
             (r_c_key, [(('cbb',), 'changed right')]),
2266
 
            ], [left, right], [basis])
 
2809
            [right, left, l_a_key, r_c_key],
 
2810
            [(('abb',), 'changed left'), (('cbb',), 'changed right')],
 
2811
            [left, right], [basis])