← 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: Gordon Tyler
  • Date: 2010-02-02 06:30:43 UTC
  • mto: (5037.3.1 integration)
  • mto: This revision was merged to the branch mainline in revision 5046.
  • Revision ID: gordon@doxxx.net-20100202063043-3ygr1114d25m3f7m
Added cmdline.split function, which replaces commands.shlex_split_unicode.

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 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):
53
56
    def test_not_a_prefix(self):
54
57
        self.assertCommonPrefix('b', 'begin', 'b')
55
58
 
56
 
 
57
 
class TestCaseWithStore(tests.TestCaseWithTransport):
 
59
    def test_empty(self):
 
60
        self.assertCommonPrefix('', '', 'end')
 
61
        self.assertCommonPrefix('', 'begin', '')
 
62
        self.assertCommonPrefix('', '', '')
 
63
 
 
64
 
 
65
class TestCaseWithStore(tests.TestCaseWithMemoryTransport):
58
66
 
59
67
    def get_chk_bytes(self):
60
 
        # The easiest way to get a CHK store is a development5 repository and
61
 
        # then work with the chk_bytes attribute directly.
62
 
        repo = self.make_repository(".", format="development5")
63
 
        repo.lock_write()
64
 
        self.addCleanup(repo.unlock)
65
 
        repo.start_write_group()
66
 
        self.addCleanup(repo.abort_write_group)
67
 
        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
68
72
 
69
73
    def _get_map(self, a_dict, maximum_size=0, chk_bytes=None, key_width=1,
70
74
                 search_key_func=None):
73
77
        root_key = CHKMap.from_dict(chk_bytes, a_dict,
74
78
            maximum_size=maximum_size, key_width=key_width,
75
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")
76
85
        chkmap = CHKMap(chk_bytes, root_key, search_key_func=search_key_func)
77
86
        return chkmap
78
87
 
87
96
        return dict(node.iteritems(*args))
88
97
 
89
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
 
90
339
class TestMap(TestCaseWithStore):
91
340
 
92
341
    def assertHasABMap(self, chk_bytes):
218
467
        # updated key.
219
468
        self.assertEqual(new_root, chkmap._root_node._key)
220
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
 
221
482
    def test_apply_delta_is_deterministic(self):
222
483
        chk_bytes = self.get_chk_bytes()
223
484
        chkmap1 = CHKMap(chk_bytes, None)
571
832
        # 'ab' and 'ac' nodes
572
833
        chkmap.map(('aad',), 'v')
573
834
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
574
 
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
575
 
        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)
576
837
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
577
838
        # to map in 'ab'
578
839
        chkmap.unmap(('acd',))
579
840
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
580
 
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
 
841
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
581
842
 
582
843
    def test_unmap_without_fitting_doesnt_page_in(self):
583
844
        store = self.get_chk_bytes()
600
861
        chkmap.map(('aaf',), 'v')
601
862
        # At this point, the previous nodes should not be paged in, but the
602
863
        # newly added nodes would be
603
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
604
 
        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)
605
866
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
606
867
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
607
868
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
609
870
        # Now unmapping one of the new nodes will use only the already-paged-in
610
871
        # nodes to determine that we don't need to do more.
611
872
        chkmap.unmap(('aaf',))
612
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
613
 
        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)
614
875
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
615
876
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
616
877
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
637
898
        chkmap.map(('aad',), 'v')
638
899
        # At this point, the previous nodes should not be paged in, but the
639
900
        # newly added node would be
640
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
641
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
642
 
        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)
643
904
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
644
905
        # Unmapping the new node will check the existing nodes to see if they
645
906
        # would fit.
677
938
        chkmap.map(('aad',), 'v')
678
939
        # At this point, the previous nodes should not be paged in, but the
679
940
        # newly added node would be
680
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
681
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
682
 
        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)
683
944
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
684
945
        # Now clear the page cache, and only include 2 of the children in the
685
946
        # cache
694
955
        # Unmapping the new node will check the nodes from the page cache
695
956
        # first, and not have to read in 'aaa'
696
957
        chkmap.unmap(('aad',))
697
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
 
958
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
698
959
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
699
960
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
700
961
 
714
975
        chkmap.map(('aaf',), 'val')
715
976
        # At this point, the previous nodes should not be paged in, but the
716
977
        # newly added node would be
717
 
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
718
 
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
719
 
        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)
720
981
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
721
982
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
722
983
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
724
985
        # Unmapping a new node will see the other nodes that are already in
725
986
        # memory, and not need to page in anything else
726
987
        chkmap.unmap(('aad',))
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)
 
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)
730
991
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
731
992
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
732
993
 
771
1032
            {('a',): 'content here', ('b',): 'more content'},
772
1033
            chk_bytes=basis._store, maximum_size=10)
773
1034
        list(target.iter_changes(basis))
774
 
        self.assertIsInstance(target._root_node, tuple)
775
 
        self.assertIsInstance(basis._root_node, tuple)
 
1035
        self.assertIsInstance(target._root_node, StaticTuple)
 
1036
        self.assertIsInstance(basis._root_node, StaticTuple)
776
1037
 
777
1038
    def test_iter_changes_ab_ab_changed_values_shown(self):
778
1039
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
884
1145
 
885
1146
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
886
1147
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
887
 
        self.assertEqual('E8B7BE43\x00E8B7BE43', search_key_func(('a', 'a')))
888
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
889
 
        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', '')))
890
1154
        chkmap = self._get_map(
891
1155
            {("a","a"):"content here", ("a", "b",):"more content",
892
1156
             ("b", ""): 'boring content'},
1189
1453
                             , chkmap._dump_tree())
1190
1454
 
1191
1455
 
1192
 
class TestSearchKeyFuncs(tests.TestCase):
1193
 
 
1194
 
    def assertSearchKey16(self, expected, key):
1195
 
        self.assertEqual(expected, chk_map._search_key_16(key))
1196
 
 
1197
 
    def assertSearchKey255(self, expected, key):
1198
 
        actual = chk_map._search_key_255(key)
1199
 
        self.assertEqual(expected, actual, 'actual: %r' % (actual,))
1200
 
 
1201
 
    def test_simple_16(self):
1202
 
        self.assertSearchKey16('8C736521', ('foo',))
1203
 
        self.assertSearchKey16('8C736521\x008C736521', ('foo', 'foo'))
1204
 
        self.assertSearchKey16('8C736521\x0076FF8CAA', ('foo', 'bar'))
1205
 
        self.assertSearchKey16('ED82CD11', ('abcd',))
1206
 
 
1207
 
    def test_simple_255(self):
1208
 
        self.assertSearchKey255('\x8cse!', ('foo',))
1209
 
        self.assertSearchKey255('\x8cse!\x00\x8cse!', ('foo', 'foo'))
1210
 
        self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', ('foo', 'bar'))
1211
 
        # The standard mapping for these would include '\n', so it should be
1212
 
        # mapped to '_'
1213
 
        self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
1214
 
 
1215
 
    def test_255_does_not_include_newline(self):
1216
 
        # When mapping via _search_key_255, we should never have the '\n'
1217
 
        # character, but all other 255 values should be present
1218
 
        chars_used = set()
1219
 
        for char_in in range(256):
1220
 
            search_key = chk_map._search_key_255((chr(char_in),))
1221
 
            chars_used.update(search_key)
1222
 
        all_chars = set([chr(x) for x in range(256)])
1223
 
        unused_chars = all_chars.symmetric_difference(chars_used)
1224
 
        self.assertEqual(set('\n'), unused_chars)
1225
 
 
1226
 
 
1227
1456
class TestLeafNode(TestCaseWithStore):
1228
1457
 
1229
1458
    def test_current_size_empty(self):
1555
1784
        child.map(None, ("baz",), "val")
1556
1785
        node.add_node("b", child)
1557
1786
 
1558
 
        key_filter = (('foo',), ('fob',), ('bar',), ('baz',))
 
1787
        # Note that 'ram' doesn't match anything, so it should be freely
 
1788
        # ignored
 
1789
        key_filter = (('foo',), ('fob',), ('bar',), ('baz',), ('ram',))
1559
1790
        for child, node_key_filter in node._iter_nodes(None,
1560
1791
                                                       key_filter=key_filter):
1561
 
            # each child could matches two key filters, so make sure they were
 
1792
            # each child could match two key filters, so make sure they were
1562
1793
            # both included.
1563
1794
            self.assertEqual(2, len(node_key_filter))
1564
1795
 
 
1796
    def make_fo_fa_node(self):
 
1797
        node = InternalNode('f')
 
1798
        child = LeafNode()
 
1799
        child.set_maximum_size(100)
 
1800
        child.map(None, ("foo",), "val")
 
1801
        child.map(None, ("fob",), "val")
 
1802
        node.add_node('fo', child)
 
1803
        child = LeafNode()
 
1804
        child.set_maximum_size(100)
 
1805
        child.map(None, ("far",), "val")
 
1806
        child.map(None, ("faz",), "val")
 
1807
        node.add_node("fa", child)
 
1808
        return node
 
1809
 
 
1810
    def test__iter_nodes_single_entry(self):
 
1811
        node = self.make_fo_fa_node()
 
1812
        key_filter = [('foo',)]
 
1813
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
 
1814
        self.assertEqual(1, len(nodes))
 
1815
        self.assertEqual(key_filter, nodes[0][1])
 
1816
 
 
1817
    def test__iter_nodes_single_entry_misses(self):
 
1818
        node = self.make_fo_fa_node()
 
1819
        key_filter = [('bar',)]
 
1820
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
 
1821
        self.assertEqual(0, len(nodes))
 
1822
 
 
1823
    def test__iter_nodes_mixed_key_width(self):
 
1824
        node = self.make_fo_fa_node()
 
1825
        key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('b',)]
 
1826
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
 
1827
        self.assertEqual(1, len(nodes))
 
1828
        matches = key_filter[:]
 
1829
        matches.remove(('b',))
 
1830
        self.assertEqual(sorted(matches), sorted(nodes[0][1]))
 
1831
 
 
1832
    def test__iter_nodes_match_all(self):
 
1833
        node = self.make_fo_fa_node()
 
1834
        key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('f',)]
 
1835
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
 
1836
        self.assertEqual(2, len(nodes))
 
1837
 
 
1838
    def test__iter_nodes_fixed_widths_and_misses(self):
 
1839
        node = self.make_fo_fa_node()
 
1840
        # foo and faa should both match one child, baz should miss
 
1841
        key_filter = [('foo',), ('faa',), ('baz',)]
 
1842
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
 
1843
        self.assertEqual(2, len(nodes))
 
1844
        for node, matches in nodes:
 
1845
            self.assertEqual(1, len(matches))
 
1846
 
1565
1847
    def test_iteritems_empty_new(self):
1566
1848
        node = InternalNode()
1567
1849
        self.assertEqual([], sorted(node.iteritems(None)))
1595
1877
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1596
1878
        node = InternalNode(search_key_func=search_key_func)
1597
1879
        leaf1 = LeafNode(search_key_func=search_key_func)
1598
 
        leaf1.map(None, ('foo bar',), 'quux')
 
1880
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
1599
1881
        leaf2 = LeafNode(search_key_func=search_key_func)
1600
 
        leaf2.map(None, ('strange',), 'beast')
1601
 
        self.assertEqual('\xbeF\x014', search_key_func(('foo bar',)))
1602
 
        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',)))
1603
1885
        node.add_node("\xbe", leaf1)
1604
1886
        # This sets up a path that should not be followed - it will error if
1605
1887
        # the code tries to.
1606
1888
        node._items['\xbe'] = None
1607
1889
        node.add_node("\x85", leaf2)
1608
1890
        self.assertEqual([(('strange',), 'beast')],
1609
 
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
 
1891
            sorted(node.iteritems(None, [StaticTuple('strange',),
 
1892
                                         StaticTuple('weird',)])))
1610
1893
 
1611
1894
    def test_iteritems_partial_empty(self):
1612
1895
        node = InternalNode()
1619
1902
        # Ensure test validity: nothing paged in below the root.
1620
1903
        self.assertEqual(2,
1621
1904
            len([value for value in node._items.values()
1622
 
                if type(value) == tuple]))
 
1905
                if type(value) is StaticTuple]))
1623
1906
        # now, mapping to k3 should add a k3 leaf
1624
1907
        prefix, nodes = node.map(None, ('k3',), 'quux')
1625
1908
        self.assertEqual("k", prefix)
1658
1941
        # Ensure test validity: nothing paged in below the root.
1659
1942
        self.assertEqual(2,
1660
1943
            len([value for value in node._items.values()
1661
 
                if type(value) == tuple]))
 
1944
                if type(value) is StaticTuple]))
1662
1945
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1663
1946
        # k23, which for simplicity in the current implementation generates
1664
1947
        # a new internal node between node, and k22/k23.
1703
1986
        node = InternalNode(search_key_func=search_key_func)
1704
1987
        node._key_width = 2
1705
1988
        node._node_width = 4
1706
 
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
1707
 
        self.assertEqual('E8B7', node._search_prefix_filter(('a', 'b')))
1708
 
        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',)))
1709
1995
 
1710
1996
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
1711
1997
        chkmap = self._get_map(
1823
2109
# 1-4K get0
1824
2110
 
1825
2111
 
1826
 
class TestIterInterestingNodes(TestCaseWithStore):
1827
 
 
1828
 
    def get_chk_bytes(self):
1829
 
        if getattr(self, '_chk_bytes', None) is None:
1830
 
            self._chk_bytes = super(TestIterInterestingNodes,
1831
 
                                    self).get_chk_bytes()
1832
 
        return self._chk_bytes
1833
 
 
1834
 
    def get_map_key(self, a_dict):
1835
 
        c_map = self._get_map(a_dict, maximum_size=10,
1836
 
                              chk_bytes=self.get_chk_bytes())
 
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):
 
2464
 
 
2465
    def get_map_key(self, a_dict, maximum_size=10):
 
2466
        c_map = self.get_map(a_dict, maximum_size=maximum_size)
1837
2467
        return c_map.key()
1838
2468
 
1839
 
    def assertIterInteresting(self, expected, interesting_keys,
1840
 
                              uninteresting_keys):
 
2469
    def assertIterInteresting(self, records, items, interesting_keys,
 
2470
                              old_keys):
1841
2471
        """Check the result of iter_interesting_nodes.
1842
2472
 
1843
 
        :param expected: A list of (record_keys, interesting_chk_pages,
1844
 
                                    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.
1845
2478
        """
1846
2479
        store = self.get_chk_bytes()
 
2480
        store._search_key_func = chk_map._search_key_plain
1847
2481
        iter_nodes = chk_map.iter_interesting_nodes(store, interesting_keys,
1848
 
                                                    uninteresting_keys)
1849
 
        for count, (exp, act) in enumerate(izip(expected, iter_nodes)):
1850
 
            exp_record_keys, exp_items = exp
1851
 
            records, items = act
1852
 
            exp_tuple = (sorted(exp_record_keys), sorted(exp_items))
1853
 
            act_tuple = (sorted(records.keys()), sorted(items))
1854
 
            self.assertEqual(exp_tuple, act_tuple)
1855
 
        self.assertEqual(len(expected), count + 1)
 
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))
1856
2492
 
1857
2493
    def test_empty_to_one_keys(self):
1858
2494
        target = self.get_map_key({('a',): 'content'})
1859
 
        self.assertIterInteresting(
1860
 
            [([target], [(('a',), 'content')])],
1861
 
            [target], [])
 
2495
        self.assertIterInteresting([target],
 
2496
                                   [(('a',), 'content')],
 
2497
                                   [target], [])
1862
2498
 
1863
2499
    def test_none_to_one_key(self):
1864
2500
        basis = self.get_map_key({})
1865
2501
        target = self.get_map_key({('a',): 'content'})
1866
 
        self.assertIterInteresting(
1867
 
            [([target], [(('a',), 'content')])],
1868
 
            [target], [basis])
 
2502
        self.assertIterInteresting([target],
 
2503
                                   [(('a',), 'content')],
 
2504
                                   [target], [basis])
1869
2505
 
1870
2506
    def test_one_to_none_key(self):
1871
2507
        basis = self.get_map_key({('a',): 'content'})
1872
2508
        target = self.get_map_key({})
1873
 
        self.assertIterInteresting(
1874
 
            [([target], [])],
1875
 
            [target], [basis])
 
2509
        self.assertIterInteresting([target],
 
2510
                                   [],
 
2511
                                   [target], [basis])
1876
2512
 
1877
2513
    def test_common_pages(self):
1878
2514
        basis = self.get_map_key({('a',): 'content',
1895
2531
            target_map._dump_tree())
1896
2532
        b_key = target_map._root_node._items['b'].key()
1897
2533
        # This should return the root node, and the node for the 'b' key
1898
 
        self.assertIterInteresting(
1899
 
            [([target], []),
1900
 
             ([b_key], [(('b',), 'other content')])],
1901
 
            [target], [basis])
 
2534
        self.assertIterInteresting([target, b_key],
 
2535
                                   [(('b',), 'other content')],
 
2536
                                   [target], [basis])
1902
2537
 
1903
2538
    def test_common_sub_page(self):
1904
2539
        basis = self.get_map_key({('aaa',): 'common',
1922
2557
        # The key for the internal aa node
1923
2558
        a_key = target_map._root_node._items['a'].key()
1924
2559
        # The key for the leaf aab node
 
2560
        # aaa_key = target_map._root_node._items['a']._items['aaa'].key()
1925
2561
        aab_key = target_map._root_node._items['a']._items['aab'].key()
1926
 
        self.assertIterInteresting(
1927
 
            [([target], []),
1928
 
             ([a_key], []),
1929
 
             ([aab_key], [(('aab',), 'new')])],
1930
 
            [target], [basis])
 
2562
        self.assertIterInteresting([target, a_key, aab_key],
 
2563
                                   [(('aab',), 'new')],
 
2564
                                   [target], [basis])
 
2565
 
 
2566
    def test_common_leaf(self):
 
2567
        basis = self.get_map_key({})
 
2568
        target1 = self.get_map_key({('aaa',): 'common'})
 
2569
        target2 = self.get_map_key({('aaa',): 'common',
 
2570
                                    ('bbb',): 'new',
 
2571
                                   })
 
2572
        target3 = self.get_map_key({('aaa',): 'common',
 
2573
                                    ('aac',): 'other',
 
2574
                                    ('bbb',): 'new',
 
2575
                                   })
 
2576
        # The LeafNode containing 'aaa': 'common' occurs at 3 different levels.
 
2577
        # Once as a root node, once as a second layer, and once as a third
 
2578
        # layer. It should only be returned one time regardless
 
2579
        target1_map = CHKMap(self.get_chk_bytes(), target1)
 
2580
        self.assertEqualDiff(
 
2581
            "'' LeafNode\n"
 
2582
            "      ('aaa',) 'common'\n",
 
2583
            target1_map._dump_tree())
 
2584
        target2_map = CHKMap(self.get_chk_bytes(), target2)
 
2585
        self.assertEqualDiff(
 
2586
            "'' InternalNode\n"
 
2587
            "  'a' LeafNode\n"
 
2588
            "      ('aaa',) 'common'\n"
 
2589
            "  'b' LeafNode\n"
 
2590
            "      ('bbb',) 'new'\n",
 
2591
            target2_map._dump_tree())
 
2592
        target3_map = CHKMap(self.get_chk_bytes(), target3)
 
2593
        self.assertEqualDiff(
 
2594
            "'' InternalNode\n"
 
2595
            "  'a' InternalNode\n"
 
2596
            "    'aaa' LeafNode\n"
 
2597
            "      ('aaa',) 'common'\n"
 
2598
            "    'aac' LeafNode\n"
 
2599
            "      ('aac',) 'other'\n"
 
2600
            "  'b' LeafNode\n"
 
2601
            "      ('bbb',) 'new'\n",
 
2602
            target3_map._dump_tree())
 
2603
        aaa_key = target1_map._root_node.key()
 
2604
        b_key = target2_map._root_node._items['b'].key()
 
2605
        a_key = target3_map._root_node._items['a'].key()
 
2606
        aac_key = target3_map._root_node._items['a']._items['aac'].key()
 
2607
        self.assertIterInteresting(
 
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])
1931
2624
 
1932
2625
    def test_multiple_maps(self):
1933
2626
        basis1 = self.get_map_key({('aaa',): 'common',
1976
2669
        # The key for the leaf bba node
1977
2670
        bba_key = target2_map._root_node._items['b']._items['bba'].key()
1978
2671
        self.assertIterInteresting(
1979
 
            [([target1, target2], []),
1980
 
             ([a_key], []),
1981
 
             ([b_key], []),
1982
 
             ([aac_key], [(('aac',), 'target1')]),
1983
 
             ([bba_key], [(('bba',), 'target2')]),
1984
 
            ], [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])
 
2675
 
 
2676
    def test_multiple_maps_overlapping_common_new(self):
 
2677
        # Test that when a node found through the interesting_keys iteration
 
2678
        # for *some roots* and also via the old keys iteration, that
 
2679
        # it is still scanned for old refs and items, because its
 
2680
        # not truely new. This requires 2 levels of InternalNodes to expose,
 
2681
        # because of the way the bootstrap in _find_children_info works.
 
2682
        # This suggests that the code is probably amenable to/benefit from
 
2683
        # consolidation.
 
2684
        # How does this test work?
 
2685
        # 1) We need a second level InternalNode present in a basis tree.
 
2686
        # 2) We need a left side new tree that uses that InternalNode
 
2687
        # 3) We need a right side new tree that does not use that InternalNode
 
2688
        #    at all but that has an unchanged *value* that was reachable inside
 
2689
        #    that InternalNode
 
2690
        basis = self.get_map_key({
 
2691
            # InternalNode, unchanged in left:
 
2692
            ('aaa',): 'left',
 
2693
            ('abb',): 'right',
 
2694
            # Forces an internalNode at 'a'
 
2695
            ('ccc',): 'common',
 
2696
            })
 
2697
        left = self.get_map_key({
 
2698
            # All of basis unchanged
 
2699
            ('aaa',): 'left',
 
2700
            ('abb',): 'right',
 
2701
            ('ccc',): 'common',
 
2702
            # And a new top level node so the root key is different
 
2703
            ('ddd',): 'change',
 
2704
            })
 
2705
        right = self.get_map_key({
 
2706
            # A value that is unchanged from basis and thus should be filtered
 
2707
            # out.
 
2708
            ('abb',): 'right'
 
2709
            })
 
2710
        basis_map = CHKMap(self.get_chk_bytes(), basis)
 
2711
        self.assertEqualDiff(
 
2712
            "'' InternalNode\n"
 
2713
            "  'a' InternalNode\n"
 
2714
            "    'aa' LeafNode\n"
 
2715
            "      ('aaa',) 'left'\n"
 
2716
            "    'ab' LeafNode\n"
 
2717
            "      ('abb',) 'right'\n"
 
2718
            "  'c' LeafNode\n"
 
2719
            "      ('ccc',) 'common'\n",
 
2720
            basis_map._dump_tree())
 
2721
        # Get left expected data
 
2722
        left_map = CHKMap(self.get_chk_bytes(), left)
 
2723
        self.assertEqualDiff(
 
2724
            "'' InternalNode\n"
 
2725
            "  'a' InternalNode\n"
 
2726
            "    'aa' LeafNode\n"
 
2727
            "      ('aaa',) 'left'\n"
 
2728
            "    'ab' LeafNode\n"
 
2729
            "      ('abb',) 'right'\n"
 
2730
            "  'c' LeafNode\n"
 
2731
            "      ('ccc',) 'common'\n"
 
2732
            "  'd' LeafNode\n"
 
2733
            "      ('ddd',) 'change'\n",
 
2734
            left_map._dump_tree())
 
2735
        # Keys from left side target
 
2736
        l_d_key = left_map._root_node._items['d'].key()
 
2737
        # Get right expected data
 
2738
        right_map = CHKMap(self.get_chk_bytes(), right)
 
2739
        self.assertEqualDiff(
 
2740
            "'' LeafNode\n"
 
2741
            "      ('abb',) 'right'\n",
 
2742
            right_map._dump_tree())
 
2743
        # Keys from the right side target - none, the root is enough.
 
2744
        # Test behaviour
 
2745
        self.assertIterInteresting(
 
2746
            [right, left, l_d_key],
 
2747
            [(('ddd',), 'change')],
 
2748
            [left, right], [basis])
 
2749
 
 
2750
    def test_multiple_maps_similar(self):
 
2751
        # We want to have a depth=2 tree, with multiple entries in each leaf
 
2752
        # node
 
2753
        basis = self.get_map_key({
 
2754
            ('aaa',): 'unchanged',
 
2755
            ('abb',): 'will change left',
 
2756
            ('caa',): 'unchanged',
 
2757
            ('cbb',): 'will change right',
 
2758
            }, maximum_size=60)
 
2759
        left = self.get_map_key({
 
2760
            ('aaa',): 'unchanged',
 
2761
            ('abb',): 'changed left',
 
2762
            ('caa',): 'unchanged',
 
2763
            ('cbb',): 'will change right',
 
2764
            }, maximum_size=60)
 
2765
        right = self.get_map_key({
 
2766
            ('aaa',): 'unchanged',
 
2767
            ('abb',): 'will change left',
 
2768
            ('caa',): 'unchanged',
 
2769
            ('cbb',): 'changed right',
 
2770
            }, maximum_size=60)
 
2771
        basis_map = CHKMap(self.get_chk_bytes(), basis)
 
2772
        self.assertEqualDiff(
 
2773
            "'' InternalNode\n"
 
2774
            "  'a' LeafNode\n"
 
2775
            "      ('aaa',) 'unchanged'\n"
 
2776
            "      ('abb',) 'will change left'\n"
 
2777
            "  'c' LeafNode\n"
 
2778
            "      ('caa',) 'unchanged'\n"
 
2779
            "      ('cbb',) 'will change right'\n",
 
2780
            basis_map._dump_tree())
 
2781
        # Get left expected data
 
2782
        left_map = CHKMap(self.get_chk_bytes(), left)
 
2783
        self.assertEqualDiff(
 
2784
            "'' InternalNode\n"
 
2785
            "  'a' LeafNode\n"
 
2786
            "      ('aaa',) 'unchanged'\n"
 
2787
            "      ('abb',) 'changed left'\n"
 
2788
            "  'c' LeafNode\n"
 
2789
            "      ('caa',) 'unchanged'\n"
 
2790
            "      ('cbb',) 'will change right'\n",
 
2791
            left_map._dump_tree())
 
2792
        # Keys from left side target
 
2793
        l_a_key = left_map._root_node._items['a'].key()
 
2794
        l_c_key = left_map._root_node._items['c'].key()
 
2795
        # Get right expected data
 
2796
        right_map = CHKMap(self.get_chk_bytes(), right)
 
2797
        self.assertEqualDiff(
 
2798
            "'' InternalNode\n"
 
2799
            "  'a' LeafNode\n"
 
2800
            "      ('aaa',) 'unchanged'\n"
 
2801
            "      ('abb',) 'will change left'\n"
 
2802
            "  'c' LeafNode\n"
 
2803
            "      ('caa',) 'unchanged'\n"
 
2804
            "      ('cbb',) 'changed right'\n",
 
2805
            right_map._dump_tree())
 
2806
        r_a_key = right_map._root_node._items['a'].key()
 
2807
        r_c_key = right_map._root_node._items['c'].key()
 
2808
        self.assertIterInteresting(
 
2809
            [right, left, l_a_key, r_c_key],
 
2810
            [(('abb',), 'changed left'), (('cbb',), 'changed right')],
 
2811
            [left, right], [basis])