← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_chk_map.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-09-29 22:03:03 UTC
  • mfrom: (5416.2.6 jam-integration)
  • Revision ID: pqm@pqm.ubuntu.com-20100929220303-cr95h8iwtggco721
(mbp) Add 'break-lock --force'

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_chk_map.py
1
 
# Copyright (C) 2008 Canonical Ltd
 
1
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
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):
78
77
        root_key = CHKMap.from_dict(chk_bytes, a_dict,
79
78
            maximum_size=maximum_size, key_width=key_width,
80
79
            search_key_func=search_key_func)
 
80
        root_key2 = CHKMap._create_via_map(chk_bytes, a_dict,
 
81
            maximum_size=maximum_size, key_width=key_width,
 
82
            search_key_func=search_key_func)
 
83
        self.assertEqual(root_key, root_key2, "CHKMap.from_dict() did not"
 
84
                         " match CHKMap._create_via_map")
81
85
        chkmap = CHKMap(chk_bytes, root_key, search_key_func=search_key_func)
82
86
        return chkmap
83
87
 
92
96
        return dict(node.iteritems(*args))
93
97
 
94
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
 
95
339
class TestMap(TestCaseWithStore):
96
340
 
97
341
    def assertHasABMap(self, chk_bytes):
223
467
        # updated key.
224
468
        self.assertEqual(new_root, chkmap._root_node._key)
225
469
 
 
470
    def test_apply_delete_to_internal_node(self):
 
471
        # applying a delta should be convert an internal root node to a leaf
 
472
        # node if the delta shrinks the map enough.
 
473
        store = self.get_chk_bytes()
 
474
        chkmap = CHKMap(store, None)
 
475
        # Add three items: 2 small enough to fit in one node, and one huge to
 
476
        # force multiple nodes.
 
477
        chkmap._root_node.set_maximum_size(100)
 
478
        chkmap.map(('small',), 'value')
 
479
        chkmap.map(('little',), 'value')
 
480
        chkmap.map(('very-big',), 'x' * 100)
 
481
        # (Check that we have constructed the scenario we want to test)
 
482
        self.assertIsInstance(chkmap._root_node, InternalNode)
 
483
        # Delete the huge item so that the map fits in one node again.
 
484
        delta = [(('very-big',), None, None)]
 
485
        chkmap.apply_delta(delta)
 
486
        self.assertCanonicalForm(chkmap)
 
487
        self.assertIsInstance(chkmap._root_node, LeafNode)
 
488
 
 
489
    def test_apply_new_keys_must_be_new(self):
 
490
        # applying a delta (None, "a", "b") to a map with 'a' in it generates
 
491
        # an error.
 
492
        chk_bytes = self.get_chk_bytes()
 
493
        root_key = CHKMap.from_dict(chk_bytes, {("a",):"b"})
 
494
        chkmap = CHKMap(chk_bytes, root_key)
 
495
        self.assertRaises(errors.InconsistentDelta, chkmap.apply_delta,
 
496
            [(None, ("a",), "b")])
 
497
        # As an error occured, the update should have left us without changing
 
498
        # anything (the root should be unchanged).
 
499
        self.assertEqual(root_key, chkmap._root_node._key)
 
500
 
226
501
    def test_apply_delta_is_deterministic(self):
227
502
        chk_bytes = self.get_chk_bytes()
228
503
        chkmap1 = CHKMap(chk_bytes, None)
576
851
        # 'ab' and 'ac' nodes
577
852
        chkmap.map(('aad',), 'v')
578
853
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
579
 
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
580
 
        self.assertIsInstance(chkmap._root_node._items['ac'], tuple)
 
854
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
 
855
        self.assertIsInstance(chkmap._root_node._items['ac'], StaticTuple)
581
856
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
582
857
        # to map in 'ab'
583
858
        chkmap.unmap(('acd',))
584
859
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
585
 
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
 
860
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
586
861
 
587
862
    def test_unmap_without_fitting_doesnt_page_in(self):
588
863
        store = self.get_chk_bytes()
605
880
        chkmap.map(('aaf',), 'v')
606
881
        # At this point, the previous nodes should not be paged in, but the
607
882
        # newly added nodes would be
608
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
609
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
883
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
884
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
610
885
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
611
886
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
612
887
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
614
889
        # Now unmapping one of the new nodes will use only the already-paged-in
615
890
        # nodes to determine that we don't need to do more.
616
891
        chkmap.unmap(('aaf',))
617
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
618
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
 
892
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
893
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
619
894
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
620
895
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
621
896
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
642
917
        chkmap.map(('aad',), 'v')
643
918
        # At this point, the previous nodes should not be paged in, but the
644
919
        # newly added node would be
645
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
646
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
647
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
920
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
921
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
922
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
648
923
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
649
924
        # Unmapping the new node will check the existing nodes to see if they
650
925
        # would fit.
651
926
        # Clear the page cache so we ensure we have to read all the children
652
 
        chk_map._page_cache.clear()
 
927
        chk_map.clear_cache()
653
928
        chkmap.unmap(('aad',))
654
929
        self.assertIsInstance(chkmap._root_node._items['aaa'], LeafNode)
655
930
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
682
957
        chkmap.map(('aad',), 'v')
683
958
        # At this point, the previous nodes should not be paged in, but the
684
959
        # newly added node would be
685
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
686
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
687
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
960
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
961
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
962
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
688
963
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
689
964
        # Now clear the page cache, and only include 2 of the children in the
690
965
        # cache
691
966
        aab_key = chkmap._root_node._items['aab']
692
 
        aab_bytes = chk_map._page_cache[aab_key]
 
967
        aab_bytes = chk_map._get_cache()[aab_key]
693
968
        aac_key = chkmap._root_node._items['aac']
694
 
        aac_bytes = chk_map._page_cache[aac_key]
695
 
        chk_map._page_cache.clear()
696
 
        chk_map._page_cache[aab_key] = aab_bytes
697
 
        chk_map._page_cache[aac_key] = aac_bytes
 
969
        aac_bytes = chk_map._get_cache()[aac_key]
 
970
        chk_map.clear_cache()
 
971
        chk_map._get_cache()[aab_key] = aab_bytes
 
972
        chk_map._get_cache()[aac_key] = aac_bytes
698
973
 
699
974
        # Unmapping the new node will check the nodes from the page cache
700
975
        # first, and not have to read in 'aaa'
701
976
        chkmap.unmap(('aad',))
702
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
977
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
703
978
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
704
979
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
705
980
 
719
994
        chkmap.map(('aaf',), 'val')
720
995
        # At this point, the previous nodes should not be paged in, but the
721
996
        # newly added node would be
722
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
723
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
724
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
997
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
998
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
999
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
725
1000
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
726
1001
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
727
1002
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
729
1004
        # Unmapping a new node will see the other nodes that are already in
730
1005
        # memory, and not need to page in anything else
731
1006
        chkmap.unmap(('aad',))
732
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
733
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
734
 
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
 
1007
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
1008
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
1009
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
735
1010
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
736
1011
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
737
1012
 
776
1051
            {('a',): 'content here', ('b',): 'more content'},
777
1052
            chk_bytes=basis._store, maximum_size=10)
778
1053
        list(target.iter_changes(basis))
779
 
        self.assertIsInstance(target._root_node, tuple)
780
 
        self.assertIsInstance(basis._root_node, tuple)
 
1054
        self.assertIsInstance(target._root_node, StaticTuple)
 
1055
        self.assertIsInstance(basis._root_node, StaticTuple)
781
1056
 
782
1057
    def test_iter_changes_ab_ab_changed_values_shown(self):
783
1058
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
889
1164
 
890
1165
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
891
1166
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
892
 
        self.assertEqual('E8B7BE43\x00E8B7BE43', search_key_func(('a', 'a')))
893
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
894
 
        self.assertEqual('71BEEFF9\x0000000000', search_key_func(('b', '')))
 
1167
        self.assertEqual('E8B7BE43\x00E8B7BE43',
 
1168
                         search_key_func(StaticTuple('a', 'a')))
 
1169
        self.assertEqual('E8B7BE43\x0071BEEFF9',
 
1170
                         search_key_func(StaticTuple('a', 'b')))
 
1171
        self.assertEqual('71BEEFF9\x0000000000',
 
1172
                         search_key_func(StaticTuple('b', '')))
895
1173
        chkmap = self._get_map(
896
1174
            {("a","a"):"content here", ("a", "b",):"more content",
897
1175
             ("b", ""): 'boring content'},
1194
1472
                             , chkmap._dump_tree())
1195
1473
 
1196
1474
 
1197
 
class TestSearchKeyFuncs(tests.TestCase):
1198
 
 
1199
 
    def assertSearchKey16(self, expected, key):
1200
 
        self.assertEqual(expected, chk_map._search_key_16(key))
1201
 
 
1202
 
    def assertSearchKey255(self, expected, key):
1203
 
        actual = chk_map._search_key_255(key)
1204
 
        self.assertEqual(expected, actual, 'actual: %r' % (actual,))
1205
 
 
1206
 
    def test_simple_16(self):
1207
 
        self.assertSearchKey16('8C736521', ('foo',))
1208
 
        self.assertSearchKey16('8C736521\x008C736521', ('foo', 'foo'))
1209
 
        self.assertSearchKey16('8C736521\x0076FF8CAA', ('foo', 'bar'))
1210
 
        self.assertSearchKey16('ED82CD11', ('abcd',))
1211
 
 
1212
 
    def test_simple_255(self):
1213
 
        self.assertSearchKey255('\x8cse!', ('foo',))
1214
 
        self.assertSearchKey255('\x8cse!\x00\x8cse!', ('foo', 'foo'))
1215
 
        self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', ('foo', 'bar'))
1216
 
        # The standard mapping for these would include '\n', so it should be
1217
 
        # mapped to '_'
1218
 
        self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
1219
 
 
1220
 
    def test_255_does_not_include_newline(self):
1221
 
        # When mapping via _search_key_255, we should never have the '\n'
1222
 
        # character, but all other 255 values should be present
1223
 
        chars_used = set()
1224
 
        for char_in in range(256):
1225
 
            search_key = chk_map._search_key_255((chr(char_in),))
1226
 
            chars_used.update(search_key)
1227
 
        all_chars = set([chr(x) for x in range(256)])
1228
 
        unused_chars = all_chars.symmetric_difference(chars_used)
1229
 
        self.assertEqual(set('\n'), unused_chars)
1230
 
 
1231
 
 
1232
1475
class TestLeafNode(TestCaseWithStore):
1233
1476
 
1234
1477
    def test_current_size_empty(self):
1653
1896
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1654
1897
        node = InternalNode(search_key_func=search_key_func)
1655
1898
        leaf1 = LeafNode(search_key_func=search_key_func)
1656
 
        leaf1.map(None, ('foo bar',), 'quux')
 
1899
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
1657
1900
        leaf2 = LeafNode(search_key_func=search_key_func)
1658
 
        leaf2.map(None, ('strange',), 'beast')
1659
 
        self.assertEqual('\xbeF\x014', search_key_func(('foo bar',)))
1660
 
        self.assertEqual('\x85\xfa\xf7K', search_key_func(('strange',)))
 
1901
        leaf2.map(None, StaticTuple('strange',), 'beast')
 
1902
        self.assertEqual('\xbeF\x014', search_key_func(StaticTuple('foo bar',)))
 
1903
        self.assertEqual('\x85\xfa\xf7K', search_key_func(StaticTuple('strange',)))
1661
1904
        node.add_node("\xbe", leaf1)
1662
1905
        # This sets up a path that should not be followed - it will error if
1663
1906
        # the code tries to.
1664
1907
        node._items['\xbe'] = None
1665
1908
        node.add_node("\x85", leaf2)
1666
1909
        self.assertEqual([(('strange',), 'beast')],
1667
 
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
 
1910
            sorted(node.iteritems(None, [StaticTuple('strange',),
 
1911
                                         StaticTuple('weird',)])))
1668
1912
 
1669
1913
    def test_iteritems_partial_empty(self):
1670
1914
        node = InternalNode()
1677
1921
        # Ensure test validity: nothing paged in below the root.
1678
1922
        self.assertEqual(2,
1679
1923
            len([value for value in node._items.values()
1680
 
                if type(value) == tuple]))
 
1924
                if type(value) is StaticTuple]))
1681
1925
        # now, mapping to k3 should add a k3 leaf
1682
1926
        prefix, nodes = node.map(None, ('k3',), 'quux')
1683
1927
        self.assertEqual("k", prefix)
1716
1960
        # Ensure test validity: nothing paged in below the root.
1717
1961
        self.assertEqual(2,
1718
1962
            len([value for value in node._items.values()
1719
 
                if type(value) == tuple]))
 
1963
                if type(value) is StaticTuple]))
1720
1964
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1721
1965
        # k23, which for simplicity in the current implementation generates
1722
1966
        # a new internal node between node, and k22/k23.
1761
2005
        node = InternalNode(search_key_func=search_key_func)
1762
2006
        node._key_width = 2
1763
2007
        node._node_width = 4
1764
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
1765
 
        self.assertEqual('E8B7', node._search_prefix_filter(('a', 'b')))
1766
 
        self.assertEqual('E8B7', node._search_prefix_filter(('a',)))
 
2008
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(
 
2009
            StaticTuple('a', 'b')))
 
2010
        self.assertEqual('E8B7', node._search_prefix_filter(
 
2011
            StaticTuple('a', 'b')))
 
2012
        self.assertEqual('E8B7', node._search_prefix_filter(
 
2013
            StaticTuple('a',)))
1767
2014
 
1768
2015
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
1769
2016
        chkmap = self._get_map(
1881
2128
# 1-4K get0
1882
2129
 
1883
2130
 
1884
 
class TestIterInterestingNodes(TestCaseWithStore):
1885
 
 
1886
 
    def get_chk_bytes(self):
1887
 
        if getattr(self, '_chk_bytes', None) is None:
1888
 
            self._chk_bytes = super(TestIterInterestingNodes,
1889
 
                                    self).get_chk_bytes()
1890
 
        return self._chk_bytes
1891
 
 
1892
 
    def get_map_key(self, a_dict):
1893
 
        c_map = self._get_map(a_dict, maximum_size=10,
1894
 
                              chk_bytes=self.get_chk_bytes())
 
2131
class TestCHKMapDifference(TestCaseWithExampleMaps):
 
2132
 
 
2133
    def get_difference(self, new_roots, old_roots,
 
2134
                       search_key_func=None):
 
2135
        if search_key_func is None:
 
2136
            search_key_func = chk_map._search_key_plain
 
2137
        return chk_map.CHKMapDifference(self.get_chk_bytes(),
 
2138
            new_roots, old_roots, search_key_func)
 
2139
 
 
2140
    def test__init__(self):
 
2141
        c_map = self.make_root_only_map()
 
2142
        key1 = c_map.key()
 
2143
        c_map.map(('aaa',), 'new aaa content')
 
2144
        key2 = c_map._save()
 
2145
        diff = self.get_difference([key2], [key1])
 
2146
        self.assertEqual(set([key1]), diff._all_old_chks)
 
2147
        self.assertEqual([], diff._old_queue)
 
2148
        self.assertEqual([], diff._new_queue)
 
2149
 
 
2150
    def help__read_all_roots(self, search_key_func):
 
2151
        c_map = self.make_root_only_map(search_key_func=search_key_func)
 
2152
        key1 = c_map.key()
 
2153
        c_map.map(('aaa',), 'new aaa content')
 
2154
        key2 = c_map._save()
 
2155
        diff = self.get_difference([key2], [key1], search_key_func)
 
2156
        root_results = [record.key for record in diff._read_all_roots()]
 
2157
        self.assertEqual([key2], root_results)
 
2158
        # We should have queued up only items that aren't in the old
 
2159
        # set
 
2160
        self.assertEqual([(('aaa',), 'new aaa content')],
 
2161
                         diff._new_item_queue)
 
2162
        self.assertEqual([], diff._new_queue)
 
2163
        # And there are no old references, so that queue should be
 
2164
        # empty
 
2165
        self.assertEqual([], diff._old_queue)
 
2166
 
 
2167
    def test__read_all_roots_plain(self):
 
2168
        self.help__read_all_roots(search_key_func=chk_map._search_key_plain)
 
2169
 
 
2170
    def test__read_all_roots_16(self):
 
2171
        self.help__read_all_roots(search_key_func=chk_map._search_key_16)
 
2172
 
 
2173
    def test__read_all_roots_skips_known_old(self):
 
2174
        c_map = self.make_one_deep_map(chk_map._search_key_plain)
 
2175
        key1 = c_map.key()
 
2176
        c_map2 = self.make_root_only_map(chk_map._search_key_plain)
 
2177
        key2 = c_map2.key()
 
2178
        diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
 
2179
        root_results = [record.key for record in diff._read_all_roots()]
 
2180
        # We should have no results. key2 is completely contained within key1,
 
2181
        # and we should have seen that in the first pass
 
2182
        self.assertEqual([], root_results)
 
2183
 
 
2184
    def test__read_all_roots_prepares_queues(self):
 
2185
        c_map = self.make_one_deep_map(chk_map._search_key_plain)
 
2186
        key1 = c_map.key()
 
2187
        c_map._dump_tree() # load everything
 
2188
        key1_a = c_map._root_node._items['a'].key()
 
2189
        c_map.map(('abb',), 'new abb content')
 
2190
        key2 = c_map._save()
 
2191
        key2_a = c_map._root_node._items['a'].key()
 
2192
        diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
 
2193
        root_results = [record.key for record in diff._read_all_roots()]
 
2194
        self.assertEqual([key2], root_results)
 
2195
        # At this point, we should have queued up only the 'a' Leaf on both
 
2196
        # sides, both 'c' and 'd' are known to not have changed on both sides
 
2197
        self.assertEqual([key2_a], diff._new_queue)
 
2198
        self.assertEqual([], diff._new_item_queue)
 
2199
        self.assertEqual([key1_a], diff._old_queue)
 
2200
 
 
2201
    def test__read_all_roots_multi_new_prepares_queues(self):
 
2202
        c_map = self.make_one_deep_map(chk_map._search_key_plain)
 
2203
        key1 = c_map.key()
 
2204
        c_map._dump_tree() # load everything
 
2205
        key1_a = c_map._root_node._items['a'].key()
 
2206
        key1_c = c_map._root_node._items['c'].key()
 
2207
        c_map.map(('abb',), 'new abb content')
 
2208
        key2 = c_map._save()
 
2209
        key2_a = c_map._root_node._items['a'].key()
 
2210
        key2_c = c_map._root_node._items['c'].key()
 
2211
        c_map = chk_map.CHKMap(self.get_chk_bytes(), key1,
 
2212
                               chk_map._search_key_plain)
 
2213
        c_map.map(('ccc',), 'new ccc content')
 
2214
        key3 = c_map._save()
 
2215
        key3_a = c_map._root_node._items['a'].key()
 
2216
        key3_c = c_map._root_node._items['c'].key()
 
2217
        diff = self.get_difference([key2, key3], [key1],
 
2218
                                   chk_map._search_key_plain)
 
2219
        root_results = [record.key for record in diff._read_all_roots()]
 
2220
        self.assertEqual(sorted([key2, key3]), sorted(root_results))
 
2221
        # We should have queued up key2_a, and key3_c, but not key2_c or key3_c
 
2222
        self.assertEqual([key2_a, key3_c], diff._new_queue)
 
2223
        self.assertEqual([], diff._new_item_queue)
 
2224
        # And we should have queued up both a and c for the old set
 
2225
        self.assertEqual([key1_a, key1_c], diff._old_queue)
 
2226
 
 
2227
    def test__read_all_roots_different_depths(self):
 
2228
        c_map = self.make_two_deep_map(chk_map._search_key_plain)
 
2229
        c_map._dump_tree() # load everything
 
2230
        key1 = c_map.key()
 
2231
        key1_a = c_map._root_node._items['a'].key()
 
2232
        key1_c = c_map._root_node._items['c'].key()
 
2233
        key1_d = c_map._root_node._items['d'].key()
 
2234
 
 
2235
        c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
 
2236
        c_map2._dump_tree()
 
2237
        key2 = c_map2.key()
 
2238
        key2_aa = c_map2._root_node._items['aa'].key()
 
2239
        key2_ad = c_map2._root_node._items['ad'].key()
 
2240
 
 
2241
        diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
 
2242
        root_results = [record.key for record in diff._read_all_roots()]
 
2243
        self.assertEqual([key2], root_results)
 
2244
        # Only the 'a' subset should be queued up, since 'c' and 'd' cannot be
 
2245
        # present
 
2246
        self.assertEqual([key1_a], diff._old_queue)
 
2247
        self.assertEqual([key2_aa, key2_ad], diff._new_queue)
 
2248
        self.assertEqual([], diff._new_item_queue)
 
2249
 
 
2250
        diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
 
2251
        root_results = [record.key for record in diff._read_all_roots()]
 
2252
        self.assertEqual([key1], root_results)
 
2253
 
 
2254
        self.assertEqual([key2_aa, key2_ad], diff._old_queue)
 
2255
        self.assertEqual([key1_a, key1_c, key1_d], diff._new_queue)
 
2256
        self.assertEqual([], diff._new_item_queue)
 
2257
 
 
2258
    def test__read_all_roots_different_depths_16(self):
 
2259
        c_map = self.make_two_deep_map(chk_map._search_key_16)
 
2260
        c_map._dump_tree() # load everything
 
2261
        key1 = c_map.key()
 
2262
        key1_2 = c_map._root_node._items['2'].key()
 
2263
        key1_4 = c_map._root_node._items['4'].key()
 
2264
        key1_C = c_map._root_node._items['C'].key()
 
2265
        key1_F = c_map._root_node._items['F'].key()
 
2266
 
 
2267
        c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_16)
 
2268
        c_map2._dump_tree()
 
2269
        key2 = c_map2.key()
 
2270
        key2_F0 = c_map2._root_node._items['F0'].key()
 
2271
        key2_F3 = c_map2._root_node._items['F3'].key()
 
2272
        key2_F4 = c_map2._root_node._items['F4'].key()
 
2273
        key2_FD = c_map2._root_node._items['FD'].key()
 
2274
 
 
2275
        diff = self.get_difference([key2], [key1], chk_map._search_key_16)
 
2276
        root_results = [record.key for record in diff._read_all_roots()]
 
2277
        self.assertEqual([key2], root_results)
 
2278
        # Only the subset of keys that may be present should be queued up.
 
2279
        self.assertEqual([key1_F], diff._old_queue)
 
2280
        self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
 
2281
                         sorted(diff._new_queue))
 
2282
        self.assertEqual([], diff._new_item_queue)
 
2283
 
 
2284
        diff = self.get_difference([key1], [key2], chk_map._search_key_16)
 
2285
        root_results = [record.key for record in diff._read_all_roots()]
 
2286
        self.assertEqual([key1], root_results)
 
2287
 
 
2288
        self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
 
2289
                         sorted(diff._old_queue))
 
2290
        self.assertEqual(sorted([key1_2, key1_4, key1_C, key1_F]),
 
2291
                         sorted(diff._new_queue))
 
2292
        self.assertEqual([], diff._new_item_queue)
 
2293
 
 
2294
    def test__read_all_roots_mixed_depth(self):
 
2295
        c_map = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
 
2296
        c_map._dump_tree() # load everything
 
2297
        key1 = c_map.key()
 
2298
        key1_aa = c_map._root_node._items['aa'].key()
 
2299
        key1_ad = c_map._root_node._items['ad'].key()
 
2300
 
 
2301
        c_map2 = self.make_one_deep_one_prefix_map(chk_map._search_key_plain)
 
2302
        c_map2._dump_tree()
 
2303
        key2 = c_map2.key()
 
2304
        key2_a = c_map2._root_node._items['a'].key()
 
2305
        key2_b = c_map2._root_node._items['b'].key()
 
2306
 
 
2307
        diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
 
2308
        root_results = [record.key for record in diff._read_all_roots()]
 
2309
        self.assertEqual([key2], root_results)
 
2310
        # 'ad' matches exactly 'a' on the other side, so it should be removed,
 
2311
        # and neither side should have it queued for walking
 
2312
        self.assertEqual([], diff._old_queue)
 
2313
        self.assertEqual([key2_b], diff._new_queue)
 
2314
        self.assertEqual([], diff._new_item_queue)
 
2315
 
 
2316
        diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
 
2317
        root_results = [record.key for record in diff._read_all_roots()]
 
2318
        self.assertEqual([key1], root_results)
 
2319
        # Note: This is technically not the 'true minimal' set that we could
 
2320
        #       use The reason is that 'a' was matched exactly to 'ad' (by sha
 
2321
        #       sum).  However, the code gets complicated in the case of more
 
2322
        #       than one interesting key, so for now, we live with this
 
2323
        #       Consider revising, though benchmarking showing it to be a
 
2324
        #       real-world issue should be done
 
2325
        self.assertEqual([key2_a], diff._old_queue)
 
2326
        # self.assertEqual([], diff._old_queue)
 
2327
        self.assertEqual([key1_aa], diff._new_queue)
 
2328
        self.assertEqual([], diff._new_item_queue)
 
2329
 
 
2330
    def test__read_all_roots_yields_extra_deep_records(self):
 
2331
        # This is slightly controversial, as we will yield a chk page that we
 
2332
        # might later on find out could be filtered out. (If a root node is
 
2333
        # referenced deeper in the old set.)
 
2334
        # However, even with stacking, we always have all chk pages that we
 
2335
        # will need. So as long as we filter out the referenced keys, we'll
 
2336
        # never run into problems.
 
2337
        # This allows us to yield a root node record immediately, without any
 
2338
        # buffering.
 
2339
        c_map = self.make_two_deep_map(chk_map._search_key_plain)
 
2340
        c_map._dump_tree() # load all keys
 
2341
        key1 = c_map.key()
 
2342
        key1_a = c_map._root_node._items['a'].key()
 
2343
        c_map2 = self.get_map({
 
2344
            ('acc',): 'initial acc content',
 
2345
            ('ace',): 'initial ace content',
 
2346
        }, maximum_size=100)
 
2347
        self.assertEqualDiff(
 
2348
            "'' LeafNode\n"
 
2349
            "      ('acc',) 'initial acc content'\n"
 
2350
            "      ('ace',) 'initial ace content'\n",
 
2351
            c_map2._dump_tree())
 
2352
        key2 = c_map2.key()
 
2353
        diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
 
2354
        root_results = [record.key for record in diff._read_all_roots()]
 
2355
        self.assertEqual([key2], root_results)
 
2356
        # However, even though we have yielded the root node to be fetched,
 
2357
        # we should have enqued all of the chk pages to be walked, so that we
 
2358
        # can find the keys if they are present
 
2359
        self.assertEqual([key1_a], diff._old_queue)
 
2360
        self.assertEqual([(('acc',), 'initial acc content'),
 
2361
                          (('ace',), 'initial ace content'),
 
2362
                         ], diff._new_item_queue)
 
2363
 
 
2364
    def test__read_all_roots_multiple_targets(self):
 
2365
        c_map = self.make_root_only_map()
 
2366
        key1 = c_map.key()
 
2367
        c_map = self.make_one_deep_map()
 
2368
        key2 = c_map.key()
 
2369
        c_map._dump_tree()
 
2370
        key2_c = c_map._root_node._items['c'].key()
 
2371
        key2_d = c_map._root_node._items['d'].key()
 
2372
        c_map.map(('ccc',), 'new ccc value')
 
2373
        key3 = c_map._save()
 
2374
        key3_c = c_map._root_node._items['c'].key()
 
2375
        diff = self.get_difference([key2, key3], [key1],
 
2376
                                   chk_map._search_key_plain)
 
2377
        root_results = [record.key for record in diff._read_all_roots()]
 
2378
        self.assertEqual(sorted([key2, key3]), sorted(root_results))
 
2379
        self.assertEqual([], diff._old_queue)
 
2380
        # the key 'd' is interesting from key2 and key3, but should only be
 
2381
        # entered into the queue 1 time
 
2382
        self.assertEqual(sorted([key2_c, key3_c, key2_d]),
 
2383
                         sorted(diff._new_queue))
 
2384
        self.assertEqual([], diff._new_item_queue)
 
2385
 
 
2386
    def test__read_all_roots_no_old(self):
 
2387
        # This is the 'initial branch' case. With nothing in the old
 
2388
        # set, we can just queue up all root nodes into interesting queue, and
 
2389
        # then have them fast-path flushed via _flush_new_queue
 
2390
        c_map = self.make_two_deep_map()
 
2391
        key1 = c_map.key()
 
2392
        diff = self.get_difference([key1], [], chk_map._search_key_plain)
 
2393
        root_results = [record.key for record in diff._read_all_roots()]
 
2394
        self.assertEqual([], root_results)
 
2395
        self.assertEqual([], diff._old_queue)
 
2396
        self.assertEqual([key1], diff._new_queue)
 
2397
        self.assertEqual([], diff._new_item_queue)
 
2398
 
 
2399
        c_map2 = self.make_one_deep_map()
 
2400
        key2 = c_map2.key()
 
2401
        diff = self.get_difference([key1, key2], [], chk_map._search_key_plain)
 
2402
        root_results = [record.key for record in diff._read_all_roots()]
 
2403
        self.assertEqual([], root_results)
 
2404
        self.assertEqual([], diff._old_queue)
 
2405
        self.assertEqual(sorted([key1, key2]), sorted(diff._new_queue))
 
2406
        self.assertEqual([], diff._new_item_queue)
 
2407
 
 
2408
    def test__read_all_roots_no_old_16(self):
 
2409
        c_map = self.make_two_deep_map(chk_map._search_key_16)
 
2410
        key1 = c_map.key()
 
2411
        diff = self.get_difference([key1], [], chk_map._search_key_16)
 
2412
        root_results = [record.key for record in diff._read_all_roots()]
 
2413
        self.assertEqual([], root_results)
 
2414
        self.assertEqual([], diff._old_queue)
 
2415
        self.assertEqual([key1], diff._new_queue)
 
2416
        self.assertEqual([], diff._new_item_queue)
 
2417
 
 
2418
        c_map2 = self.make_one_deep_map(chk_map._search_key_16)
 
2419
        key2 = c_map2.key()
 
2420
        diff = self.get_difference([key1, key2], [],
 
2421
                                   chk_map._search_key_16)
 
2422
        root_results = [record.key for record in diff._read_all_roots()]
 
2423
        self.assertEqual([], root_results)
 
2424
        self.assertEqual([], diff._old_queue)
 
2425
        self.assertEqual(sorted([key1, key2]),
 
2426
                         sorted(diff._new_queue))
 
2427
        self.assertEqual([], diff._new_item_queue)
 
2428
 
 
2429
    def test__read_all_roots_multiple_old(self):
 
2430
        c_map = self.make_two_deep_map()
 
2431
        key1 = c_map.key()
 
2432
        c_map._dump_tree() # load everything
 
2433
        key1_a = c_map._root_node._items['a'].key()
 
2434
        c_map.map(('ccc',), 'new ccc value')
 
2435
        key2 = c_map._save()
 
2436
        key2_a = c_map._root_node._items['a'].key()
 
2437
        c_map.map(('add',), 'new add value')
 
2438
        key3 = c_map._save()
 
2439
        key3_a = c_map._root_node._items['a'].key()
 
2440
        diff = self.get_difference([key3], [key1, key2],
 
2441
                                   chk_map._search_key_plain)
 
2442
        root_results = [record.key for record in diff._read_all_roots()]
 
2443
        self.assertEqual([key3], root_results)
 
2444
        # the 'a' keys should not be queued up 2 times, since they are
 
2445
        # identical
 
2446
        self.assertEqual([key1_a], diff._old_queue)
 
2447
        self.assertEqual([key3_a], diff._new_queue)
 
2448
        self.assertEqual([], diff._new_item_queue)
 
2449
 
 
2450
    def test__process_next_old_batched_no_dupes(self):
 
2451
        c_map = self.make_two_deep_map()
 
2452
        key1 = c_map.key()
 
2453
        c_map._dump_tree() # load everything
 
2454
        key1_a = c_map._root_node._items['a'].key()
 
2455
        key1_aa = c_map._root_node._items['a']._items['aa'].key()
 
2456
        key1_ab = c_map._root_node._items['a']._items['ab'].key()
 
2457
        key1_ac = c_map._root_node._items['a']._items['ac'].key()
 
2458
        key1_ad = c_map._root_node._items['a']._items['ad'].key()
 
2459
        c_map.map(('aaa',), 'new aaa value')
 
2460
        key2 = c_map._save()
 
2461
        key2_a = c_map._root_node._items['a'].key()
 
2462
        key2_aa = c_map._root_node._items['a']._items['aa'].key()
 
2463
        c_map.map(('acc',), 'new acc content')
 
2464
        key3 = c_map._save()
 
2465
        key3_a = c_map._root_node._items['a'].key()
 
2466
        key3_ac = c_map._root_node._items['a']._items['ac'].key()
 
2467
        diff = self.get_difference([key3], [key1, key2],
 
2468
                                   chk_map._search_key_plain)
 
2469
        root_results = [record.key for record in diff._read_all_roots()]
 
2470
        self.assertEqual([key3], root_results)
 
2471
        self.assertEqual(sorted([key1_a, key2_a]),
 
2472
                         sorted(diff._old_queue))
 
2473
        self.assertEqual([key3_a], diff._new_queue)
 
2474
        self.assertEqual([], diff._new_item_queue)
 
2475
        diff._process_next_old()
 
2476
        # All of the old records should be brought in and queued up,
 
2477
        # but we should not have any duplicates
 
2478
        self.assertEqual(sorted([key1_aa, key1_ab, key1_ac, key1_ad, key2_aa]),
 
2479
                         sorted(diff._old_queue))
 
2480
 
 
2481
 
 
2482
class TestIterInterestingNodes(TestCaseWithExampleMaps):
 
2483
 
 
2484
    def get_map_key(self, a_dict, maximum_size=10):
 
2485
        c_map = self.get_map(a_dict, maximum_size=maximum_size)
1895
2486
        return c_map.key()
1896
2487
 
1897
 
    def assertIterInteresting(self, expected, interesting_keys,
1898
 
                              uninteresting_keys):
 
2488
    def assertIterInteresting(self, records, items, interesting_keys,
 
2489
                              old_keys):
1899
2490
        """Check the result of iter_interesting_nodes.
1900
2491
 
1901
 
        :param expected: A list of (record_keys, interesting_chk_pages,
1902
 
                                    interesting key value pairs)
 
2492
        Note that we no longer care how many steps are taken, etc, just that
 
2493
        the right contents are returned.
 
2494
 
 
2495
        :param records: A list of record keys that should be yielded
 
2496
        :param items: A list of items (key,value) that should be yielded.
1903
2497
        """
1904
2498
        store = self.get_chk_bytes()
 
2499
        store._search_key_func = chk_map._search_key_plain
1905
2500
        iter_nodes = chk_map.iter_interesting_nodes(store, interesting_keys,
1906
 
                                                    uninteresting_keys)
1907
 
        nodes = list(iter_nodes)
1908
 
        for count, (exp, act) in enumerate(izip(expected, nodes)):
1909
 
            exp_record, exp_items = exp
1910
 
            record, items = act
1911
 
            exp_tuple = (exp_record, sorted(exp_items))
1912
 
            if record is None:
1913
 
                act_tuple = (None, sorted(items))
1914
 
            else:
1915
 
                act_tuple = (record.key, sorted(items))
1916
 
            self.assertEqual(exp_tuple, act_tuple,
1917
 
                             'entry %d did not match expected' % count)
1918
 
        self.assertEqual(len(expected), len(nodes))
 
2501
                                                    old_keys)
 
2502
        record_keys = []
 
2503
        all_items = []
 
2504
        for record, new_items in iter_nodes:
 
2505
            if record is not None:
 
2506
                record_keys.append(record.key)
 
2507
            if new_items:
 
2508
                all_items.extend(new_items)
 
2509
        self.assertEqual(sorted(records), sorted(record_keys))
 
2510
        self.assertEqual(sorted(items), sorted(all_items))
1919
2511
 
1920
2512
    def test_empty_to_one_keys(self):
1921
2513
        target = self.get_map_key({('a',): 'content'})
1922
 
        self.assertIterInteresting(
1923
 
            [(target, [(('a',), 'content')]),
1924
 
            ], [target], [])
 
2514
        self.assertIterInteresting([target],
 
2515
                                   [(('a',), 'content')],
 
2516
                                   [target], [])
1925
2517
 
1926
2518
    def test_none_to_one_key(self):
1927
2519
        basis = self.get_map_key({})
1928
2520
        target = self.get_map_key({('a',): 'content'})
1929
 
        self.assertIterInteresting(
1930
 
            [(None, [(('a',), 'content')]),
1931
 
             (target, []),
1932
 
            ], [target], [basis])
 
2521
        self.assertIterInteresting([target],
 
2522
                                   [(('a',), 'content')],
 
2523
                                   [target], [basis])
1933
2524
 
1934
2525
    def test_one_to_none_key(self):
1935
2526
        basis = self.get_map_key({('a',): 'content'})
1936
2527
        target = self.get_map_key({})
1937
 
        self.assertIterInteresting(
1938
 
            [(target, [])],
1939
 
            [target], [basis])
 
2528
        self.assertIterInteresting([target],
 
2529
                                   [],
 
2530
                                   [target], [basis])
1940
2531
 
1941
2532
    def test_common_pages(self):
1942
2533
        basis = self.get_map_key({('a',): 'content',
1959
2550
            target_map._dump_tree())
1960
2551
        b_key = target_map._root_node._items['b'].key()
1961
2552
        # This should return the root node, and the node for the 'b' key
1962
 
        self.assertIterInteresting(
1963
 
            [(target, []),
1964
 
             (b_key, [(('b',), 'other content')])],
1965
 
            [target], [basis])
 
2553
        self.assertIterInteresting([target, b_key],
 
2554
                                   [(('b',), 'other content')],
 
2555
                                   [target], [basis])
1966
2556
 
1967
2557
    def test_common_sub_page(self):
1968
2558
        basis = self.get_map_key({('aaa',): 'common',
1986
2576
        # The key for the internal aa node
1987
2577
        a_key = target_map._root_node._items['a'].key()
1988
2578
        # The key for the leaf aab node
 
2579
        # aaa_key = target_map._root_node._items['a']._items['aaa'].key()
1989
2580
        aab_key = target_map._root_node._items['a']._items['aab'].key()
1990
 
        self.assertIterInteresting(
1991
 
            [(target, []),
1992
 
             (a_key, []),
1993
 
             (aab_key, [(('aab',), 'new')])],
1994
 
            [target], [basis])
 
2581
        self.assertIterInteresting([target, a_key, aab_key],
 
2582
                                   [(('aab',), 'new')],
 
2583
                                   [target], [basis])
1995
2584
 
1996
2585
    def test_common_leaf(self):
1997
2586
        basis = self.get_map_key({})
2035
2624
        a_key = target3_map._root_node._items['a'].key()
2036
2625
        aac_key = target3_map._root_node._items['a']._items['aac'].key()
2037
2626
        self.assertIterInteresting(
2038
 
            [(None, [(('aaa',), 'common')]),
2039
 
             (target1, []),
2040
 
             (target2, []),
2041
 
             (target3, []),
2042
 
             (b_key, [(('bbb',), 'new')]),
2043
 
             (a_key, []),
2044
 
             (aac_key, [(('aac',), 'other')]),
2045
 
            ], [target1, target2, target3], [basis])
2046
 
 
2047
 
        self.assertIterInteresting(
2048
 
            [(target2, []),
2049
 
             (target3, []),
2050
 
             (b_key, [(('bbb',), 'new')]),
2051
 
             (a_key, []),
2052
 
             (aac_key, [(('aac',), 'other')]),
2053
 
            ], [target2, target3], [target1])
2054
 
 
2055
 
        # This may be a case that we relax. A root node is a deep child of the
2056
 
        # excluded set. The cost is buffering root nodes until we have
2057
 
        # determined all possible exclusions. (Because a prefix of '', cannot
2058
 
        # be excluded.)
2059
 
        self.assertIterInteresting(
2060
 
            [], [target1], [target3])
 
2627
            [target1, target2, target3, a_key, aac_key, b_key],
 
2628
            [(('aaa',), 'common'), (('bbb',), 'new'), (('aac',), 'other')],
 
2629
            [target1, target2, target3], [basis])
 
2630
 
 
2631
        self.assertIterInteresting(
 
2632
            [target2, target3, a_key, aac_key, b_key],
 
2633
            [(('bbb',), 'new'), (('aac',), 'other')],
 
2634
            [target2, target3], [target1])
 
2635
 
 
2636
        # Technically, target1 could be filtered out, but since it is a root
 
2637
        # node, we yield it immediately, rather than waiting to find out much
 
2638
        # later on.
 
2639
        self.assertIterInteresting(
 
2640
            [target1],
 
2641
            [],
 
2642
            [target1], [target3])
2061
2643
 
2062
2644
    def test_multiple_maps(self):
2063
2645
        basis1 = self.get_map_key({('aaa',): 'common',
2106
2688
        # The key for the leaf bba node
2107
2689
        bba_key = target2_map._root_node._items['b']._items['bba'].key()
2108
2690
        self.assertIterInteresting(
2109
 
            [(target1, []),
2110
 
             (target2, []),
2111
 
             (a_key, []),
2112
 
             (b_key, []),
2113
 
             (aac_key, [(('aac',), 'target1')]),
2114
 
             (bba_key, [(('bba',), 'target2')]),
2115
 
            ], [target1, target2], [basis1, basis2])
 
2691
            [target1, target2, a_key, aac_key, b_key, bba_key],
 
2692
            [(('aac',), 'target1'), (('bba',), 'target2')],
 
2693
            [target1, target2], [basis1, basis2])
 
2694
 
 
2695
    def test_multiple_maps_overlapping_common_new(self):
 
2696
        # Test that when a node found through the interesting_keys iteration
 
2697
        # for *some roots* and also via the old keys iteration, that
 
2698
        # it is still scanned for old refs and items, because its
 
2699
        # not truely new. This requires 2 levels of InternalNodes to expose,
 
2700
        # because of the way the bootstrap in _find_children_info works.
 
2701
        # This suggests that the code is probably amenable to/benefit from
 
2702
        # consolidation.
 
2703
        # How does this test work?
 
2704
        # 1) We need a second level InternalNode present in a basis tree.
 
2705
        # 2) We need a left side new tree that uses that InternalNode
 
2706
        # 3) We need a right side new tree that does not use that InternalNode
 
2707
        #    at all but that has an unchanged *value* that was reachable inside
 
2708
        #    that InternalNode
 
2709
        basis = self.get_map_key({
 
2710
            # InternalNode, unchanged in left:
 
2711
            ('aaa',): 'left',
 
2712
            ('abb',): 'right',
 
2713
            # Forces an internalNode at 'a'
 
2714
            ('ccc',): 'common',
 
2715
            })
 
2716
        left = self.get_map_key({
 
2717
            # All of basis unchanged
 
2718
            ('aaa',): 'left',
 
2719
            ('abb',): 'right',
 
2720
            ('ccc',): 'common',
 
2721
            # And a new top level node so the root key is different
 
2722
            ('ddd',): 'change',
 
2723
            })
 
2724
        right = self.get_map_key({
 
2725
            # A value that is unchanged from basis and thus should be filtered
 
2726
            # out.
 
2727
            ('abb',): 'right'
 
2728
            })
 
2729
        basis_map = CHKMap(self.get_chk_bytes(), basis)
 
2730
        self.assertEqualDiff(
 
2731
            "'' InternalNode\n"
 
2732
            "  'a' InternalNode\n"
 
2733
            "    'aa' LeafNode\n"
 
2734
            "      ('aaa',) 'left'\n"
 
2735
            "    'ab' LeafNode\n"
 
2736
            "      ('abb',) 'right'\n"
 
2737
            "  'c' LeafNode\n"
 
2738
            "      ('ccc',) 'common'\n",
 
2739
            basis_map._dump_tree())
 
2740
        # Get left expected data
 
2741
        left_map = CHKMap(self.get_chk_bytes(), left)
 
2742
        self.assertEqualDiff(
 
2743
            "'' InternalNode\n"
 
2744
            "  'a' InternalNode\n"
 
2745
            "    'aa' LeafNode\n"
 
2746
            "      ('aaa',) 'left'\n"
 
2747
            "    'ab' LeafNode\n"
 
2748
            "      ('abb',) 'right'\n"
 
2749
            "  'c' LeafNode\n"
 
2750
            "      ('ccc',) 'common'\n"
 
2751
            "  'd' LeafNode\n"
 
2752
            "      ('ddd',) 'change'\n",
 
2753
            left_map._dump_tree())
 
2754
        # Keys from left side target
 
2755
        l_d_key = left_map._root_node._items['d'].key()
 
2756
        # Get right expected data
 
2757
        right_map = CHKMap(self.get_chk_bytes(), right)
 
2758
        self.assertEqualDiff(
 
2759
            "'' LeafNode\n"
 
2760
            "      ('abb',) 'right'\n",
 
2761
            right_map._dump_tree())
 
2762
        # Keys from the right side target - none, the root is enough.
 
2763
        # Test behaviour
 
2764
        self.assertIterInteresting(
 
2765
            [right, left, l_d_key],
 
2766
            [(('ddd',), 'change')],
 
2767
            [left, right], [basis])
 
2768
 
 
2769
    def test_multiple_maps_similar(self):
 
2770
        # We want to have a depth=2 tree, with multiple entries in each leaf
 
2771
        # node
 
2772
        basis = self.get_map_key({
 
2773
            ('aaa',): 'unchanged',
 
2774
            ('abb',): 'will change left',
 
2775
            ('caa',): 'unchanged',
 
2776
            ('cbb',): 'will change right',
 
2777
            }, maximum_size=60)
 
2778
        left = self.get_map_key({
 
2779
            ('aaa',): 'unchanged',
 
2780
            ('abb',): 'changed left',
 
2781
            ('caa',): 'unchanged',
 
2782
            ('cbb',): 'will change right',
 
2783
            }, maximum_size=60)
 
2784
        right = self.get_map_key({
 
2785
            ('aaa',): 'unchanged',
 
2786
            ('abb',): 'will change left',
 
2787
            ('caa',): 'unchanged',
 
2788
            ('cbb',): 'changed right',
 
2789
            }, maximum_size=60)
 
2790
        basis_map = CHKMap(self.get_chk_bytes(), basis)
 
2791
        self.assertEqualDiff(
 
2792
            "'' InternalNode\n"
 
2793
            "  'a' LeafNode\n"
 
2794
            "      ('aaa',) 'unchanged'\n"
 
2795
            "      ('abb',) 'will change left'\n"
 
2796
            "  'c' LeafNode\n"
 
2797
            "      ('caa',) 'unchanged'\n"
 
2798
            "      ('cbb',) 'will change right'\n",
 
2799
            basis_map._dump_tree())
 
2800
        # Get left expected data
 
2801
        left_map = CHKMap(self.get_chk_bytes(), left)
 
2802
        self.assertEqualDiff(
 
2803
            "'' InternalNode\n"
 
2804
            "  'a' LeafNode\n"
 
2805
            "      ('aaa',) 'unchanged'\n"
 
2806
            "      ('abb',) 'changed left'\n"
 
2807
            "  'c' LeafNode\n"
 
2808
            "      ('caa',) 'unchanged'\n"
 
2809
            "      ('cbb',) 'will change right'\n",
 
2810
            left_map._dump_tree())
 
2811
        # Keys from left side target
 
2812
        l_a_key = left_map._root_node._items['a'].key()
 
2813
        l_c_key = left_map._root_node._items['c'].key()
 
2814
        # Get right expected data
 
2815
        right_map = CHKMap(self.get_chk_bytes(), right)
 
2816
        self.assertEqualDiff(
 
2817
            "'' InternalNode\n"
 
2818
            "  'a' LeafNode\n"
 
2819
            "      ('aaa',) 'unchanged'\n"
 
2820
            "      ('abb',) 'will change left'\n"
 
2821
            "  'c' LeafNode\n"
 
2822
            "      ('caa',) 'unchanged'\n"
 
2823
            "      ('cbb',) 'changed right'\n",
 
2824
            right_map._dump_tree())
 
2825
        r_a_key = right_map._root_node._items['a'].key()
 
2826
        r_c_key = right_map._root_node._items['c'].key()
 
2827
        self.assertIterInteresting(
 
2828
            [right, left, l_a_key, r_c_key],
 
2829
            [(('abb',), 'changed left'), (('cbb',), 'changed right')],
 
2830
            [left, right], [basis])