/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to breezy/tests/test_chk_map.py

  • Committer: Jelmer Vernooij
  • Date: 2018-02-18 21:42:57 UTC
  • mto: This revision was merged to the branch mainline in revision 6859.
  • Revision ID: jelmer@jelmer.uk-20180218214257-jpevutp1wa30tz3v
Update TODO to reference Breezy, not Bazaar.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test_chk_map.py
16
16
 
17
17
"""Tests for maps built on a CHK versionedfiles facility."""
18
18
 
19
 
from ... import (
 
19
from .. import (
20
20
    errors,
21
21
    osutils,
22
22
    tests,
23
23
    )
24
 
from .. import (
 
24
from ..bzr import (
25
25
    chk_map,
26
26
    groupcompress,
27
27
    )
28
 
from ..chk_map import (
 
28
from ..bzr.chk_map import (
29
29
    CHKMap,
30
30
    InternalNode,
31
31
    LeafNode,
32
32
    Node,
33
33
    )
34
 
from ...static_tuple import StaticTuple
 
34
from ..static_tuple import StaticTuple
35
35
 
36
36
 
37
37
class TestNode(tests.TestCase):
45
45
        self.assertEqual(expected_common, common)
46
46
 
47
47
    def test_common_prefix(self):
48
 
        self.assertCommonPrefix(b'beg', b'beg', b'begin')
 
48
        self.assertCommonPrefix('beg', 'beg', 'begin')
49
49
 
50
50
    def test_no_common_prefix(self):
51
 
        self.assertCommonPrefix(b'', b'begin', b'end')
 
51
        self.assertCommonPrefix('', 'begin', 'end')
52
52
 
53
53
    def test_equal(self):
54
 
        self.assertCommonPrefix(b'begin', b'begin', b'begin')
 
54
        self.assertCommonPrefix('begin', 'begin', 'begin')
55
55
 
56
56
    def test_not_a_prefix(self):
57
 
        self.assertCommonPrefix(b'b', b'begin', b'b')
 
57
        self.assertCommonPrefix('b', 'begin', 'b')
58
58
 
59
59
    def test_empty(self):
60
 
        self.assertCommonPrefix(b'', b'', b'end')
61
 
        self.assertCommonPrefix(b'', b'begin', b'')
62
 
        self.assertCommonPrefix(b'', b'', b'')
 
60
        self.assertCommonPrefix('', '', 'end')
 
61
        self.assertCommonPrefix('', 'begin', '')
 
62
        self.assertCommonPrefix('', '', '')
63
63
 
64
64
 
65
65
class TestCaseWithStore(tests.TestCaseWithMemoryTransport):
75
75
        if chk_bytes is None:
76
76
            chk_bytes = self.get_chk_bytes()
77
77
        root_key = CHKMap.from_dict(chk_bytes, a_dict,
78
 
                                    maximum_size=maximum_size, key_width=key_width,
79
 
                                    search_key_func=search_key_func)
 
78
            maximum_size=maximum_size, key_width=key_width,
 
79
            search_key_func=search_key_func)
80
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)
 
81
            maximum_size=maximum_size, key_width=key_width,
 
82
            search_key_func=search_key_func)
83
83
        self.assertEqual(root_key, root_key2, "CHKMap.from_dict() did not"
84
84
                         " match CHKMap._create_via_map")
85
85
        chkmap = CHKMap(chk_bytes, root_key, search_key_func=search_key_func)
112
112
 
113
113
    def make_root_only_map(self, search_key_func=None):
114
114
        return self.get_map({
115
 
            (b'aaa',): b'initial aaa content',
116
 
            (b'abb',): b'initial abb content',
 
115
            ('aaa',): 'initial aaa content',
 
116
            ('abb',): 'initial abb content',
117
117
        }, search_key_func=search_key_func)
118
118
 
119
119
    def make_root_only_aaa_ddd_map(self, search_key_func=None):
120
120
        return self.get_map({
121
 
            (b'aaa',): b'initial aaa content',
122
 
            (b'ddd',): b'initial ddd content',
 
121
            ('aaa',): 'initial aaa content',
 
122
            ('ddd',): 'initial ddd content',
123
123
        }, search_key_func=search_key_func)
124
124
 
125
125
    def make_one_deep_map(self, search_key_func=None):
126
126
        # Same as root_only_map, except it forces an InternalNode at the root
127
127
        return self.get_map({
128
 
            (b'aaa',): b'initial aaa content',
129
 
            (b'abb',): b'initial abb content',
130
 
            (b'ccc',): b'initial ccc content',
131
 
            (b'ddd',): b'initial ddd content',
 
128
            ('aaa',): 'initial aaa content',
 
129
            ('abb',): 'initial abb content',
 
130
            ('ccc',): 'initial ccc content',
 
131
            ('ddd',): 'initial ddd content',
132
132
        }, search_key_func=search_key_func)
133
133
 
134
134
    def make_two_deep_map(self, search_key_func=None):
136
136
        # _search_key_plain and for _search_key_16
137
137
        # Also so that things line up with make_one_deep_two_prefix_map
138
138
        return self.get_map({
139
 
            (b'aaa',): b'initial aaa content',
140
 
            (b'abb',): b'initial abb content',
141
 
            (b'acc',): b'initial acc content',
142
 
            (b'ace',): b'initial ace content',
143
 
            (b'add',): b'initial add content',
144
 
            (b'adh',): b'initial adh content',
145
 
            (b'adl',): b'initial adl content',
146
 
            (b'ccc',): b'initial ccc content',
147
 
            (b'ddd',): b'initial ddd content',
 
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
148
        }, search_key_func=search_key_func)
149
149
 
150
150
    def make_one_deep_two_prefix_map(self, search_key_func=None):
153
153
        Otherwise has similar content to make_two_deep_map.
154
154
        """
155
155
        return self.get_map({
156
 
            (b'aaa',): b'initial aaa content',
157
 
            (b'add',): b'initial add content',
158
 
            (b'adh',): b'initial adh content',
159
 
            (b'adl',): b'initial adl content',
 
156
            ('aaa',): 'initial aaa content',
 
157
            ('add',): 'initial add content',
 
158
            ('adh',): 'initial adh content',
 
159
            ('adl',): 'initial adl content',
160
160
        }, search_key_func=search_key_func)
161
161
 
162
162
    def make_one_deep_one_prefix_map(self, search_key_func=None):
166
166
        first char, rather than the second.
167
167
        """
168
168
        return self.get_map({
169
 
            (b'add',): b'initial add content',
170
 
            (b'adh',): b'initial adh content',
171
 
            (b'adl',): b'initial adl content',
172
 
            (b'bbb',): b'initial bbb content',
 
169
            ('add',): 'initial add content',
 
170
            ('adh',): 'initial adh content',
 
171
            ('adl',): 'initial adl content',
 
172
            ('bbb',): 'initial bbb content',
173
173
        }, search_key_func=search_key_func)
174
174
 
175
175
 
228
228
 
229
229
    def test_root_only_aaa_ddd_16(self):
230
230
        c_map = self.make_root_only_aaa_ddd_map(
231
 
            search_key_func=chk_map._search_key_16)
 
231
                search_key_func=chk_map._search_key_16)
232
232
        # We use 'aaa' and 'ddd' because they happen to map to 'F' when using
233
233
        # _search_key_16
234
234
        self.assertEqualDiff(
339
339
class TestMap(TestCaseWithStore):
340
340
 
341
341
    def assertHasABMap(self, chk_bytes):
342
 
        ab_leaf_bytes = b'chkleaf:\n0\n1\n1\na\n\x001\nb\n'
 
342
        ab_leaf_bytes = 'chkleaf:\n0\n1\n1\na\n\x001\nb\n'
343
343
        ab_sha1 = osutils.sha_string(ab_leaf_bytes)
344
 
        self.assertEqual(b'90986195696b177c8895d48fdb4b7f2366f798a0', ab_sha1)
345
 
        root_key = (b'sha1:' + ab_sha1,)
 
344
        self.assertEqual('90986195696b177c8895d48fdb4b7f2366f798a0', ab_sha1)
 
345
        root_key = ('sha1:' + ab_sha1,)
346
346
        self.assertEqual(ab_leaf_bytes, self.read_bytes(chk_bytes, root_key))
347
347
        return root_key
348
348
 
349
349
    def assertHasEmptyMap(self, chk_bytes):
350
 
        empty_leaf_bytes = b'chkleaf:\n0\n1\n0\n\n'
 
350
        empty_leaf_bytes = 'chkleaf:\n0\n1\n0\n\n'
351
351
        empty_sha1 = osutils.sha_string(empty_leaf_bytes)
352
 
        self.assertEqual(
353
 
            b'8571e09bf1bcc5b9621ce31b3d4c93d6e9a1ed26', empty_sha1)
354
 
        root_key = (b'sha1:' + empty_sha1,)
355
 
        self.assertEqual(empty_leaf_bytes,
356
 
                         self.read_bytes(chk_bytes, root_key))
 
352
        self.assertEqual('8571e09bf1bcc5b9621ce31b3d4c93d6e9a1ed26', empty_sha1)
 
353
        root_key = ('sha1:' + empty_sha1,)
 
354
        self.assertEqual(empty_leaf_bytes, self.read_bytes(chk_bytes, root_key))
357
355
        return root_key
358
356
 
359
357
    def assertMapLayoutEqual(self, map_one, map_two):
374
372
                # Internal nodes must have identical references
375
373
                self.assertEqual(sorted(node_one._items.keys()),
376
374
                                 sorted(node_two._items.keys()))
377
 
                node_one_stack.extend(sorted(
378
 
                    [n for n, _ in node_one._iter_nodes(map_one._store)],
379
 
                    key=lambda a: a._search_prefix))
380
 
                node_two_stack.extend(sorted(
381
 
                    [n for n, _ in node_two._iter_nodes(map_two._store)],
382
 
                    key=lambda a: a._search_prefix))
 
375
                node_one_stack.extend([n for n, _ in
 
376
                                       node_one._iter_nodes(map_one._store)])
 
377
                node_two_stack.extend([n for n, _ in
 
378
                                       node_two._iter_nodes(map_two._store)])
383
379
            else:
384
380
                # Leaf nodes must have identical contents
385
381
                self.assertEqual(node_one._items, node_two._items)
411
407
        map_two = CHKMap(store, None)
412
408
        map_two._root_node.set_maximum_size(20)
413
409
        self.assertMapLayoutEqual(map_one, map_two)
414
 
        map_one.map((b'aaa', ), b'value')
 
410
        map_one.map('aaa', 'value')
415
411
        self.assertRaises(AssertionError,
416
 
                          self.assertMapLayoutEqual, map_one, map_two)
417
 
        map_two.map((b'aaa', ), b'value')
 
412
            self.assertMapLayoutEqual, map_one, map_two)
 
413
        map_two.map('aaa', 'value')
418
414
        self.assertMapLayoutEqual(map_one, map_two)
419
415
        # Split the tree, so we ensure that internal nodes and leaf nodes are
420
416
        # properly checked
421
 
        map_one.map((b'aab', ), b'value')
 
417
        map_one.map('aab', 'value')
422
418
        self.assertIsInstance(map_one._root_node, InternalNode)
423
419
        self.assertRaises(AssertionError,
424
 
                          self.assertMapLayoutEqual, map_one, map_two)
425
 
        map_two.map((b'aab', ), b'value')
 
420
            self.assertMapLayoutEqual, map_one, map_two)
 
421
        map_two.map('aab', 'value')
426
422
        self.assertMapLayoutEqual(map_one, map_two)
427
 
        map_one.map((b'aac', ), b'value')
 
423
        map_one.map('aac', 'value')
428
424
        self.assertRaises(AssertionError,
429
 
                          self.assertMapLayoutEqual, map_one, map_two)
 
425
            self.assertMapLayoutEqual, map_one, map_two)
430
426
        self.assertCanonicalForm(map_one)
431
427
 
432
428
    def test_from_dict_empty(self):
438
434
 
439
435
    def test_from_dict_ab(self):
440
436
        chk_bytes = self.get_chk_bytes()
441
 
        root_key = CHKMap.from_dict(chk_bytes, {(b"a", ): b"b"})
 
437
        root_key = CHKMap.from_dict(chk_bytes, {"a": "b"})
442
438
        # Check the data was saved and inserted correctly.
443
439
        expected_root_key = self.assertHasABMap(chk_bytes)
444
440
        self.assertEqual(expected_root_key, root_key)
449
445
        chk_bytes = self.get_chk_bytes()
450
446
        root_key = CHKMap.from_dict(chk_bytes, {})
451
447
        chkmap = CHKMap(chk_bytes, root_key)
452
 
        new_root = chkmap.apply_delta([(None, (b"a", ), b"b")])
 
448
        new_root = chkmap.apply_delta([(None, "a", "b")])
453
449
        # Check the data was saved and inserted correctly.
454
450
        expected_root_key = self.assertHasABMap(chk_bytes)
455
451
        self.assertEqual(expected_root_key, new_root)
461
457
        # applying a delta ("a", None, None) to a map with 'a' in it generates
462
458
        # an empty map.
463
459
        chk_bytes = self.get_chk_bytes()
464
 
        root_key = CHKMap.from_dict(chk_bytes, {(b"a",): b"b"})
 
460
        root_key = CHKMap.from_dict(chk_bytes, {("a",):"b"})
465
461
        chkmap = CHKMap(chk_bytes, root_key)
466
 
        new_root = chkmap.apply_delta([((b"a",), None, None)])
 
462
        new_root = chkmap.apply_delta([(("a",), None, None)])
467
463
        # Check the data was saved and inserted correctly.
468
464
        expected_root_key = self.assertHasEmptyMap(chk_bytes)
469
465
        self.assertEqual(expected_root_key, new_root)
479
475
        # Add three items: 2 small enough to fit in one node, and one huge to
480
476
        # force multiple nodes.
481
477
        chkmap._root_node.set_maximum_size(100)
482
 
        chkmap.map((b'small',), b'value')
483
 
        chkmap.map((b'little',), b'value')
484
 
        chkmap.map((b'very-big',), b'x' * 100)
 
478
        chkmap.map(('small',), 'value')
 
479
        chkmap.map(('little',), 'value')
 
480
        chkmap.map(('very-big',), 'x' * 100)
485
481
        # (Check that we have constructed the scenario we want to test)
486
482
        self.assertIsInstance(chkmap._root_node, InternalNode)
487
483
        # Delete the huge item so that the map fits in one node again.
488
 
        delta = [((b'very-big',), None, None)]
 
484
        delta = [(('very-big',), None, None)]
489
485
        chkmap.apply_delta(delta)
490
486
        self.assertCanonicalForm(chkmap)
491
487
        self.assertIsInstance(chkmap._root_node, LeafNode)
494
490
        # applying a delta (None, "a", "b") to a map with 'a' in it generates
495
491
        # an error.
496
492
        chk_bytes = self.get_chk_bytes()
497
 
        root_key = CHKMap.from_dict(chk_bytes, {(b"a",): b"b"})
 
493
        root_key = CHKMap.from_dict(chk_bytes, {("a",):"b"})
498
494
        chkmap = CHKMap(chk_bytes, root_key)
499
495
        self.assertRaises(errors.InconsistentDelta, chkmap.apply_delta,
500
 
                          [(None, (b"a",), b"b")])
 
496
            [(None, ("a",), "b")])
501
497
        # As an error occured, the update should have left us without changing
502
498
        # anything (the root should be unchanged).
503
499
        self.assertEqual(root_key, chkmap._root_node._key)
506
502
        chk_bytes = self.get_chk_bytes()
507
503
        chkmap1 = CHKMap(chk_bytes, None)
508
504
        chkmap1._root_node.set_maximum_size(10)
509
 
        chkmap1.apply_delta([(None, (b'aaa',), b'common'),
510
 
                             (None, (b'bba',), b'target2'),
511
 
                             (None, (b'bbb',), b'common')])
 
505
        chkmap1.apply_delta([(None, ('aaa',), 'common'),
 
506
                             (None, ('bba',), 'target2'),
 
507
                             (None, ('bbb',), 'common')])
512
508
        root_key1 = chkmap1._save()
513
509
        self.assertCanonicalForm(chkmap1)
514
510
 
515
511
        chkmap2 = CHKMap(chk_bytes, None)
516
512
        chkmap2._root_node.set_maximum_size(10)
517
 
        chkmap2.apply_delta([(None, (b'bbb',), b'common'),
518
 
                             (None, (b'bba',), b'target2'),
519
 
                             (None, (b'aaa',), b'common')])
 
513
        chkmap2.apply_delta([(None, ('bbb',), 'common'),
 
514
                             (None, ('bba',), 'target2'),
 
515
                             (None, ('aaa',), 'common')])
520
516
        root_key2 = chkmap2._save()
521
517
        self.assertEqualDiff(chkmap1._dump_tree(include_keys=True),
522
518
                             chkmap2._dump_tree(include_keys=True))
528
524
        chkmap = CHKMap(store, None)
529
525
        # Should fit 2 keys per LeafNode
530
526
        chkmap._root_node.set_maximum_size(35)
531
 
        chkmap.map((b'aaa',), b'v')
 
527
        chkmap.map(('aaa',), 'v')
532
528
        self.assertEqualDiff("'' LeafNode\n"
533
529
                             "      ('aaa',) 'v'\n",
534
530
                             chkmap._dump_tree())
535
 
        chkmap.map((b'aab',), b'v')
 
531
        chkmap.map(('aab',), 'v')
536
532
        self.assertEqualDiff("'' LeafNode\n"
537
533
                             "      ('aaa',) 'v'\n"
538
534
                             "      ('aab',) 'v'\n",
540
536
        self.assertCanonicalForm(chkmap)
541
537
 
542
538
        # Creates a new internal node, and splits the others into leaves
543
 
        chkmap.map((b'aac',), b'v')
 
539
        chkmap.map(('aac',), 'v')
544
540
        self.assertEqualDiff("'' InternalNode\n"
545
541
                             "  'aaa' LeafNode\n"
546
542
                             "      ('aaa',) 'v'\n"
552
548
        self.assertCanonicalForm(chkmap)
553
549
 
554
550
        # Splits again, because it can't fit in the current structure
555
 
        chkmap.map((b'bbb',), b'v')
 
551
        chkmap.map(('bbb',), 'v')
556
552
        self.assertEqualDiff("'' InternalNode\n"
557
553
                             "  'a' InternalNode\n"
558
554
                             "    'aaa' LeafNode\n"
571
567
        chkmap = CHKMap(store, None)
572
568
        # Should fit 1 key per LeafNode
573
569
        chkmap._root_node.set_maximum_size(10)
574
 
        chkmap.map((b'aaa',), b'v')
575
 
        chkmap.map((b'aaaa',), b'v')
 
570
        chkmap.map(('aaa',), 'v')
 
571
        chkmap.map(('aaaa',), 'v')
576
572
        self.assertCanonicalForm(chkmap)
577
573
        self.assertIsInstance(chkmap._root_node, InternalNode)
578
574
 
581
577
        chkmap = CHKMap(store, None)
582
578
        # Should fit 1 key per LeafNode
583
579
        chkmap._root_node.set_maximum_size(10)
584
 
        chkmap.map((b'a\ra',), b'val1')
585
 
        chkmap.map((b'a\rb',), b'val2')
586
 
        chkmap.map((b'ac',), b'val3')
 
580
        chkmap.map(('a\ra',), 'val1')
 
581
        chkmap.map(('a\rb',), 'val2')
 
582
        chkmap.map(('ac',), 'val3')
587
583
        self.assertCanonicalForm(chkmap)
588
584
        self.assertEqualDiff("'' InternalNode\n"
589
585
                             "  'a\\r' InternalNode\n"
612
608
        chkmap = CHKMap(store, None)
613
609
        # Should fit 2 keys per LeafNode
614
610
        chkmap._root_node.set_maximum_size(40)
615
 
        chkmap.map((b'aaaaaaaa',), b'v')
616
 
        chkmap.map((b'aaaaabaa',), b'v')
 
611
        chkmap.map(('aaaaaaaa',), 'v')
 
612
        chkmap.map(('aaaaabaa',), 'v')
617
613
        self.assertEqualDiff("'' LeafNode\n"
618
614
                             "      ('aaaaaaaa',) 'v'\n"
619
615
                             "      ('aaaaabaa',) 'v'\n",
620
616
                             chkmap._dump_tree())
621
 
        chkmap.map((b'aaabaaaa',), b'v')
622
 
        chkmap.map((b'aaababaa',), b'v')
 
617
        chkmap.map(('aaabaaaa',), 'v')
 
618
        chkmap.map(('aaababaa',), 'v')
623
619
        self.assertEqualDiff("'' InternalNode\n"
624
620
                             "  'aaaa' LeafNode\n"
625
621
                             "      ('aaaaaaaa',) 'v'\n"
628
624
                             "      ('aaabaaaa',) 'v'\n"
629
625
                             "      ('aaababaa',) 'v'\n",
630
626
                             chkmap._dump_tree())
631
 
        chkmap.map((b'aaabacaa',), b'v')
632
 
        chkmap.map((b'aaabadaa',), b'v')
 
627
        chkmap.map(('aaabacaa',), 'v')
 
628
        chkmap.map(('aaabadaa',), 'v')
633
629
        self.assertEqualDiff("'' InternalNode\n"
634
630
                             "  'aaaa' LeafNode\n"
635
631
                             "      ('aaaaaaaa',) 'v'\n"
644
640
                             "    'aaabad' LeafNode\n"
645
641
                             "      ('aaabadaa',) 'v'\n",
646
642
                             chkmap._dump_tree())
647
 
        chkmap.map((b'aaababba',), b'val')
648
 
        chkmap.map((b'aaababca',), b'val')
 
643
        chkmap.map(('aaababba',), 'val')
 
644
        chkmap.map(('aaababca',), 'val')
649
645
        self.assertEqualDiff("'' InternalNode\n"
650
646
                             "  'aaaa' LeafNode\n"
651
647
                             "      ('aaaaaaaa',) 'v'\n"
668
664
        # Now we add a node that should fit around an existing InternalNode,
669
665
        # but has a slightly different key prefix, which causes a new
670
666
        # InternalNode split
671
 
        chkmap.map((b'aaabDaaa',), b'v')
 
667
        chkmap.map(('aaabDaaa',), 'v')
672
668
        self.assertEqualDiff("'' InternalNode\n"
673
669
                             "  'aaaa' LeafNode\n"
674
670
                             "      ('aaaaaaaa',) 'v'\n"
697
693
        chkmap = CHKMap(store, None)
698
694
        # Should fit 2 keys per LeafNode
699
695
        chkmap._root_node.set_maximum_size(35)
700
 
        chkmap.map((b'aaa',), b'v')
701
 
        chkmap.map((b'aab',), b'very long value that splits')
 
696
        chkmap.map(('aaa',), 'v')
 
697
        chkmap.map(('aab',), 'very long value that splits')
702
698
        self.assertEqualDiff("'' InternalNode\n"
703
699
                             "  'aaa' LeafNode\n"
704
700
                             "      ('aaa',) 'v'\n"
707
703
                             chkmap._dump_tree())
708
704
        self.assertCanonicalForm(chkmap)
709
705
        # Now changing the value to something small should cause a rebuild
710
 
        chkmap.map((b'aab',), b'v')
 
706
        chkmap.map(('aab',), 'v')
711
707
        self.assertEqualDiff("'' LeafNode\n"
712
708
                             "      ('aaa',) 'v'\n"
713
709
                             "      ('aab',) 'v'\n",
719
715
        chkmap = CHKMap(store, None)
720
716
        # Should fit 3 small keys per LeafNode
721
717
        chkmap._root_node.set_maximum_size(40)
722
 
        chkmap.map((b'aaa',), b'v')
723
 
        chkmap.map((b'aab',), b'very long value that splits')
724
 
        chkmap.map((b'abc',), b'v')
 
718
        chkmap.map(('aaa',), 'v')
 
719
        chkmap.map(('aab',), 'very long value that splits')
 
720
        chkmap.map(('abc',), 'v')
725
721
        self.assertEqualDiff("'' InternalNode\n"
726
722
                             "  'aa' InternalNode\n"
727
723
                             "    'aaa' LeafNode\n"
731
727
                             "  'ab' LeafNode\n"
732
728
                             "      ('abc',) 'v'\n",
733
729
                             chkmap._dump_tree())
734
 
        chkmap.map((b'aab',), b'v')
 
730
        chkmap.map(('aab',), 'v')
735
731
        self.assertCanonicalForm(chkmap)
736
732
        self.assertEqualDiff("'' LeafNode\n"
737
733
                             "      ('aaa',) 'v'\n"
744
740
        chkmap = CHKMap(store, None)
745
741
        # Should fit 2 keys per LeafNode
746
742
        chkmap._root_node.set_maximum_size(35)
747
 
        chkmap.map((b'aaa',), b'v')
748
 
        chkmap.map((b'aab',), b'v')
 
743
        chkmap.map(('aaa',), 'v')
 
744
        chkmap.map(('aab',), 'v')
749
745
        self.assertEqualDiff("'' LeafNode\n"
750
746
                             "      ('aaa',) 'v'\n"
751
747
                             "      ('aab',) 'v'\n",
752
748
                             chkmap._dump_tree())
753
749
        # Creates a new internal node, and splits the others into leaves
754
 
        chkmap.map((b'aac',), b'v')
 
750
        chkmap.map(('aac',), 'v')
755
751
        self.assertEqualDiff("'' InternalNode\n"
756
752
                             "  'aaa' LeafNode\n"
757
753
                             "      ('aaa',) 'v'\n"
763
759
        self.assertCanonicalForm(chkmap)
764
760
        # Now lets unmap one of the keys, and assert that we collapse the
765
761
        # structures.
766
 
        chkmap.unmap((b'aac',))
 
762
        chkmap.unmap(('aac',))
767
763
        self.assertEqualDiff("'' LeafNode\n"
768
764
                             "      ('aaa',) 'v'\n"
769
765
                             "      ('aab',) 'v'\n",
775
771
        chkmap = CHKMap(store, None)
776
772
        # Should fit 3 keys per LeafNode
777
773
        chkmap._root_node.set_maximum_size(40)
778
 
        chkmap.map((b'aaa',), b'v')
779
 
        chkmap.map((b'aaab',), b'v')
780
 
        chkmap.map((b'aab',), b'very long value')
781
 
        chkmap.map((b'abc',), b'v')
 
774
        chkmap.map(('aaa',), 'v')
 
775
        chkmap.map(('aaab',), 'v')
 
776
        chkmap.map(('aab',), 'very long value')
 
777
        chkmap.map(('abc',), 'v')
782
778
        self.assertEqualDiff("'' InternalNode\n"
783
779
                             "  'aa' InternalNode\n"
784
780
                             "    'aaa' LeafNode\n"
791
787
                             chkmap._dump_tree())
792
788
        # Removing the 'aab' key should cause everything to collapse back to a
793
789
        # single node
794
 
        chkmap.unmap((b'aab',))
 
790
        chkmap.unmap(('aab',))
795
791
        self.assertEqualDiff("'' LeafNode\n"
796
792
                             "      ('aaa',) 'v'\n"
797
793
                             "      ('aaab',) 'v'\n"
803
799
        chkmap = CHKMap(store, None)
804
800
        # Should fit 3 keys per LeafNode
805
801
        chkmap._root_node.set_maximum_size(40)
806
 
        chkmap.map((b'aaa',), b'v')
807
 
        chkmap.map((b'aab',), b'long value')
808
 
        chkmap.map((b'aabb',), b'v')
809
 
        chkmap.map((b'abc',), b'v')
 
802
        chkmap.map(('aaa',), 'v')
 
803
        chkmap.map(('aab',), 'long value')
 
804
        chkmap.map(('aabb',), 'v')
 
805
        chkmap.map(('abc',), 'v')
810
806
        self.assertEqualDiff("'' InternalNode\n"
811
807
                             "  'aa' InternalNode\n"
812
808
                             "    'aaa' LeafNode\n"
819
815
                             chkmap._dump_tree())
820
816
        # Removing the 'aab' key should cause everything to collapse back to a
821
817
        # single node
822
 
        chkmap.unmap((b'aab',))
 
818
        chkmap.unmap(('aab',))
823
819
        self.assertEqualDiff("'' LeafNode\n"
824
820
                             "      ('aaa',) 'v'\n"
825
821
                             "      ('aabb',) 'v'\n"
831
827
        chkmap = CHKMap(store, None)
832
828
        # Should fit 3 keys per LeafNode
833
829
        chkmap._root_node.set_maximum_size(30)
834
 
        chkmap.map((b'aaa',), b'v')
835
 
        chkmap.map((b'aab',), b'v')
836
 
        chkmap.map((b'aac',), b'v')
837
 
        chkmap.map((b'abc',), b'v')
838
 
        chkmap.map((b'acd',), b'v')
 
830
        chkmap.map(('aaa',), 'v')
 
831
        chkmap.map(('aab',), 'v')
 
832
        chkmap.map(('aac',), 'v')
 
833
        chkmap.map(('abc',), 'v')
 
834
        chkmap.map(('acd',), 'v')
839
835
        self.assertEqualDiff("'' InternalNode\n"
840
836
                             "  'aa' InternalNode\n"
841
837
                             "    'aaa' LeafNode\n"
853
849
        chkmap = CHKMap(store, chkmap._save())
854
850
        # Mapping an 'aa' key loads the internal node, but should not map the
855
851
        # 'ab' and 'ac' nodes
856
 
        chkmap.map((b'aad',), b'v')
857
 
        self.assertIsInstance(chkmap._root_node._items[b'aa'], InternalNode)
858
 
        self.assertIsInstance(chkmap._root_node._items[b'ab'], StaticTuple)
859
 
        self.assertIsInstance(chkmap._root_node._items[b'ac'], StaticTuple)
 
852
        chkmap.map(('aad',), 'v')
 
853
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
 
854
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
 
855
        self.assertIsInstance(chkmap._root_node._items['ac'], StaticTuple)
860
856
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
861
857
        # to map in 'ab'
862
 
        chkmap.unmap((b'acd',))
863
 
        self.assertIsInstance(chkmap._root_node._items[b'aa'], InternalNode)
864
 
        self.assertIsInstance(chkmap._root_node._items[b'ab'], StaticTuple)
 
858
        chkmap.unmap(('acd',))
 
859
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
 
860
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
865
861
 
866
862
    def test_unmap_without_fitting_doesnt_page_in(self):
867
863
        store = self.get_chk_bytes()
868
864
        chkmap = CHKMap(store, None)
869
865
        # Should fit 2 keys per LeafNode
870
866
        chkmap._root_node.set_maximum_size(20)
871
 
        chkmap.map((b'aaa',), b'v')
872
 
        chkmap.map((b'aab',), b'v')
 
867
        chkmap.map(('aaa',), 'v')
 
868
        chkmap.map(('aab',), 'v')
873
869
        self.assertEqualDiff("'' InternalNode\n"
874
870
                             "  'aaa' LeafNode\n"
875
871
                             "      ('aaa',) 'v'\n"
878
874
                             chkmap._dump_tree())
879
875
        # Save everything to the map, and start over
880
876
        chkmap = CHKMap(store, chkmap._save())
881
 
        chkmap.map((b'aac',), b'v')
882
 
        chkmap.map((b'aad',), b'v')
883
 
        chkmap.map((b'aae',), b'v')
884
 
        chkmap.map((b'aaf',), b'v')
 
877
        chkmap.map(('aac',), 'v')
 
878
        chkmap.map(('aad',), 'v')
 
879
        chkmap.map(('aae',), 'v')
 
880
        chkmap.map(('aaf',), 'v')
885
881
        # At this point, the previous nodes should not be paged in, but the
886
882
        # newly added nodes would be
887
 
        self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
888
 
        self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
889
 
        self.assertIsInstance(chkmap._root_node._items[b'aac'], LeafNode)
890
 
        self.assertIsInstance(chkmap._root_node._items[b'aad'], LeafNode)
891
 
        self.assertIsInstance(chkmap._root_node._items[b'aae'], LeafNode)
892
 
        self.assertIsInstance(chkmap._root_node._items[b'aaf'], LeafNode)
 
883
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
884
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
885
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
 
886
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
 
887
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
 
888
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
893
889
        # Now unmapping one of the new nodes will use only the already-paged-in
894
890
        # nodes to determine that we don't need to do more.
895
 
        chkmap.unmap((b'aaf',))
896
 
        self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
897
 
        self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
898
 
        self.assertIsInstance(chkmap._root_node._items[b'aac'], LeafNode)
899
 
        self.assertIsInstance(chkmap._root_node._items[b'aad'], LeafNode)
900
 
        self.assertIsInstance(chkmap._root_node._items[b'aae'], LeafNode)
 
891
        chkmap.unmap(('aaf',))
 
892
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
893
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
 
894
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
 
895
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
 
896
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
901
897
 
902
898
    def test_unmap_pages_in_if_necessary(self):
903
899
        store = self.get_chk_bytes()
904
900
        chkmap = CHKMap(store, None)
905
901
        # Should fit 2 keys per LeafNode
906
902
        chkmap._root_node.set_maximum_size(30)
907
 
        chkmap.map((b'aaa',), b'val')
908
 
        chkmap.map((b'aab',), b'val')
909
 
        chkmap.map((b'aac',), b'val')
 
903
        chkmap.map(('aaa',), 'val')
 
904
        chkmap.map(('aab',), 'val')
 
905
        chkmap.map(('aac',), 'val')
910
906
        self.assertEqualDiff("'' InternalNode\n"
911
907
                             "  'aaa' LeafNode\n"
912
908
                             "      ('aaa',) 'val'\n"
918
914
        root_key = chkmap._save()
919
915
        # Save everything to the map, and start over
920
916
        chkmap = CHKMap(store, root_key)
921
 
        chkmap.map((b'aad',), b'v')
 
917
        chkmap.map(('aad',), 'v')
922
918
        # At this point, the previous nodes should not be paged in, but the
923
919
        # newly added node would be
924
 
        self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
925
 
        self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
926
 
        self.assertIsInstance(chkmap._root_node._items[b'aac'], StaticTuple)
927
 
        self.assertIsInstance(chkmap._root_node._items[b'aad'], LeafNode)
 
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)
 
923
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
928
924
        # Unmapping the new node will check the existing nodes to see if they
929
925
        # would fit.
930
926
        # Clear the page cache so we ensure we have to read all the children
931
927
        chk_map.clear_cache()
932
 
        chkmap.unmap((b'aad',))
933
 
        self.assertIsInstance(chkmap._root_node._items[b'aaa'], LeafNode)
934
 
        self.assertIsInstance(chkmap._root_node._items[b'aab'], LeafNode)
935
 
        self.assertIsInstance(chkmap._root_node._items[b'aac'], LeafNode)
 
928
        chkmap.unmap(('aad',))
 
929
        self.assertIsInstance(chkmap._root_node._items['aaa'], LeafNode)
 
930
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
 
931
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
936
932
 
937
933
    def test_unmap_pages_in_from_page_cache(self):
938
934
        store = self.get_chk_bytes()
939
935
        chkmap = CHKMap(store, None)
940
936
        # Should fit 2 keys per LeafNode
941
937
        chkmap._root_node.set_maximum_size(30)
942
 
        chkmap.map((b'aaa',), b'val')
943
 
        chkmap.map((b'aab',), b'val')
944
 
        chkmap.map((b'aac',), b'val')
 
938
        chkmap.map(('aaa',), 'val')
 
939
        chkmap.map(('aab',), 'val')
 
940
        chkmap.map(('aac',), 'val')
945
941
        root_key = chkmap._save()
946
942
        # Save everything to the map, and start over
947
943
        chkmap = CHKMap(store, root_key)
948
 
        chkmap.map((b'aad',), b'val')
 
944
        chkmap.map(('aad',), 'val')
949
945
        self.assertEqualDiff("'' InternalNode\n"
950
946
                             "  'aaa' LeafNode\n"
951
947
                             "      ('aaa',) 'val'\n"
958
954
                             chkmap._dump_tree())
959
955
        # Save everything to the map, start over after _dump_tree
960
956
        chkmap = CHKMap(store, root_key)
961
 
        chkmap.map((b'aad',), b'v')
 
957
        chkmap.map(('aad',), 'v')
962
958
        # At this point, the previous nodes should not be paged in, but the
963
959
        # newly added node would be
964
 
        self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
965
 
        self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
966
 
        self.assertIsInstance(chkmap._root_node._items[b'aac'], StaticTuple)
967
 
        self.assertIsInstance(chkmap._root_node._items[b'aad'], LeafNode)
 
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)
 
963
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
968
964
        # Now clear the page cache, and only include 2 of the children in the
969
965
        # cache
970
 
        aab_key = chkmap._root_node._items[b'aab']
 
966
        aab_key = chkmap._root_node._items['aab']
971
967
        aab_bytes = chk_map._get_cache()[aab_key]
972
 
        aac_key = chkmap._root_node._items[b'aac']
 
968
        aac_key = chkmap._root_node._items['aac']
973
969
        aac_bytes = chk_map._get_cache()[aac_key]
974
970
        chk_map.clear_cache()
975
971
        chk_map._get_cache()[aab_key] = aab_bytes
977
973
 
978
974
        # Unmapping the new node will check the nodes from the page cache
979
975
        # first, and not have to read in 'aaa'
980
 
        chkmap.unmap((b'aad',))
981
 
        self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
982
 
        self.assertIsInstance(chkmap._root_node._items[b'aab'], LeafNode)
983
 
        self.assertIsInstance(chkmap._root_node._items[b'aac'], LeafNode)
 
976
        chkmap.unmap(('aad',))
 
977
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
 
978
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
 
979
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
984
980
 
985
981
    def test_unmap_uses_existing_items(self):
986
982
        store = self.get_chk_bytes()
987
983
        chkmap = CHKMap(store, None)
988
984
        # Should fit 2 keys per LeafNode
989
985
        chkmap._root_node.set_maximum_size(30)
990
 
        chkmap.map((b'aaa',), b'val')
991
 
        chkmap.map((b'aab',), b'val')
992
 
        chkmap.map((b'aac',), b'val')
 
986
        chkmap.map(('aaa',), 'val')
 
987
        chkmap.map(('aab',), 'val')
 
988
        chkmap.map(('aac',), 'val')
993
989
        root_key = chkmap._save()
994
990
        # Save everything to the map, and start over
995
991
        chkmap = CHKMap(store, root_key)
996
 
        chkmap.map((b'aad',), b'val')
997
 
        chkmap.map((b'aae',), b'val')
998
 
        chkmap.map((b'aaf',), b'val')
 
992
        chkmap.map(('aad',), 'val')
 
993
        chkmap.map(('aae',), 'val')
 
994
        chkmap.map(('aaf',), 'val')
999
995
        # At this point, the previous nodes should not be paged in, but the
1000
996
        # newly added node would be
1001
 
        self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
1002
 
        self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
1003
 
        self.assertIsInstance(chkmap._root_node._items[b'aac'], StaticTuple)
1004
 
        self.assertIsInstance(chkmap._root_node._items[b'aad'], LeafNode)
1005
 
        self.assertIsInstance(chkmap._root_node._items[b'aae'], LeafNode)
1006
 
        self.assertIsInstance(chkmap._root_node._items[b'aaf'], LeafNode)
 
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)
 
1000
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
 
1001
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
 
1002
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
1007
1003
 
1008
1004
        # Unmapping a new node will see the other nodes that are already in
1009
1005
        # memory, and not need to page in anything else
1010
 
        chkmap.unmap((b'aad',))
1011
 
        self.assertIsInstance(chkmap._root_node._items[b'aaa'], StaticTuple)
1012
 
        self.assertIsInstance(chkmap._root_node._items[b'aab'], StaticTuple)
1013
 
        self.assertIsInstance(chkmap._root_node._items[b'aac'], StaticTuple)
1014
 
        self.assertIsInstance(chkmap._root_node._items[b'aae'], LeafNode)
1015
 
        self.assertIsInstance(chkmap._root_node._items[b'aaf'], LeafNode)
 
1006
        chkmap.unmap(('aad',))
 
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)
 
1010
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
 
1011
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
1016
1012
 
1017
1013
    def test_iter_changes_empty_ab(self):
1018
1014
        # Asking for changes between an empty dict to a dict with keys returns
1019
1015
        # all the keys.
1020
1016
        basis = self._get_map({}, maximum_size=10)
1021
1017
        target = self._get_map(
1022
 
            {(b'a',): b'content here', (b'b',): b'more content'},
 
1018
            {('a',): 'content here', ('b',): 'more content'},
1023
1019
            chk_bytes=basis._store, maximum_size=10)
1024
 
        self.assertEqual([((b'a',), None, b'content here'),
1025
 
                          ((b'b',), None, b'more content')],
1026
 
                         sorted(list(target.iter_changes(basis))))
 
1020
        self.assertEqual([(('a',), None, 'content here'),
 
1021
            (('b',), None, 'more content')],
 
1022
            sorted(list(target.iter_changes(basis))))
1027
1023
 
1028
1024
    def test_iter_changes_ab_empty(self):
1029
1025
        # Asking for changes between a dict with keys to an empty dict returns
1030
1026
        # all the keys.
1031
 
        basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},
1032
 
                              maximum_size=10)
 
1027
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
 
1028
            maximum_size=10)
1033
1029
        target = self._get_map({}, chk_bytes=basis._store, maximum_size=10)
1034
 
        self.assertEqual([((b'a',), b'content here', None),
1035
 
                          ((b'b',), b'more content', None)],
1036
 
                         sorted(list(target.iter_changes(basis))))
 
1030
        self.assertEqual([(('a',), 'content here', None),
 
1031
            (('b',), 'more content', None)],
 
1032
            sorted(list(target.iter_changes(basis))))
1037
1033
 
1038
1034
    def test_iter_changes_empty_empty_is_empty(self):
1039
1035
        basis = self._get_map({}, maximum_size=10)
1041
1037
        self.assertEqual([], sorted(list(target.iter_changes(basis))))
1042
1038
 
1043
1039
    def test_iter_changes_ab_ab_is_empty(self):
1044
 
        basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},
1045
 
                              maximum_size=10)
 
1040
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
 
1041
            maximum_size=10)
1046
1042
        target = self._get_map(
1047
 
            {(b'a',): b'content here', (b'b',): b'more content'},
 
1043
            {('a',): 'content here', ('b',): 'more content'},
1048
1044
            chk_bytes=basis._store, maximum_size=10)
1049
1045
        self.assertEqual([], sorted(list(target.iter_changes(basis))))
1050
1046
 
1051
1047
    def test_iter_changes_ab_ab_nodes_not_loaded(self):
1052
 
        basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},
1053
 
                              maximum_size=10)
 
1048
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
 
1049
            maximum_size=10)
1054
1050
        target = self._get_map(
1055
 
            {(b'a',): b'content here', (b'b',): b'more content'},
 
1051
            {('a',): 'content here', ('b',): 'more content'},
1056
1052
            chk_bytes=basis._store, maximum_size=10)
1057
1053
        list(target.iter_changes(basis))
1058
1054
        self.assertIsInstance(target._root_node, StaticTuple)
1059
1055
        self.assertIsInstance(basis._root_node, StaticTuple)
1060
1056
 
1061
1057
    def test_iter_changes_ab_ab_changed_values_shown(self):
1062
 
        basis = self._get_map({(b'a',): b'content here', (b'b',): b'more content'},
1063
 
                              maximum_size=10)
 
1058
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
 
1059
            maximum_size=10)
1064
1060
        target = self._get_map(
1065
 
            {(b'a',): b'content here', (b'b',): b'different content'},
 
1061
            {('a',): 'content here', ('b',): 'different content'},
1066
1062
            chk_bytes=basis._store, maximum_size=10)
1067
1063
        result = sorted(list(target.iter_changes(basis)))
1068
 
        self.assertEqual([((b'b',), b'more content', b'different content')],
1069
 
                         result)
 
1064
        self.assertEqual([(('b',), 'more content', 'different content')],
 
1065
            result)
1070
1066
 
1071
1067
    def test_iter_changes_mixed_node_length(self):
1072
1068
        # When one side has different node lengths than the other, common
1080
1076
        # aaa to be not loaded (later test)
1081
1077
        # aab, b, at to be returned.
1082
1078
        # basis splits at byte 0,1,2, aaa is commonb is basis only
1083
 
        basis_dict = {(b'aaa',): b'foo bar',
1084
 
                      (b'aab',): b'common altered a', (b'b',): b'foo bar b'}
 
1079
        basis_dict = {('aaa',): 'foo bar',
 
1080
            ('aab',): 'common altered a', ('b',): 'foo bar b'}
1085
1081
        # target splits at byte 1,2, at is target only
1086
 
        target_dict = {(b'aaa',): b'foo bar',
1087
 
                       (b'aab',): b'common altered b', (b'at',): b'foo bar t'}
 
1082
        target_dict = {('aaa',): 'foo bar',
 
1083
            ('aab',): 'common altered b', ('at',): 'foo bar t'}
1088
1084
        changes = [
1089
 
            ((b'aab',), b'common altered a', b'common altered b'),
1090
 
            ((b'at',), None, b'foo bar t'),
1091
 
            ((b'b',), b'foo bar b', None),
 
1085
            (('aab',), 'common altered a', 'common altered b'),
 
1086
            (('at',), None, 'foo bar t'),
 
1087
            (('b',), 'foo bar b', None),
1092
1088
            ]
1093
1089
        basis = self._get_map(basis_dict, maximum_size=10)
1094
1090
        target = self._get_map(target_dict, maximum_size=10,
1095
 
                               chk_bytes=basis._store)
 
1091
            chk_bytes=basis._store)
1096
1092
        self.assertEqual(changes, sorted(list(target.iter_changes(basis))))
1097
1093
 
1098
1094
    def test_iter_changes_common_pages_not_loaded(self):
1103
1099
        # we expect:
1104
1100
        # aaa to be not loaded
1105
1101
        # aaa not to be in result.
1106
 
        basis_dict = {(b'aaa',): b'foo bar',
1107
 
                      (b'aab',): b'common altered a', (b'b',): b'foo bar b'}
 
1102
        basis_dict = {('aaa',): 'foo bar',
 
1103
            ('aab',): 'common altered a', ('b',): 'foo bar b'}
1108
1104
        # target splits at byte 1, at is target only
1109
 
        target_dict = {(b'aaa',): b'foo bar',
1110
 
                       (b'aab',): b'common altered b', (b'at',): b'foo bar t'}
 
1105
        target_dict = {('aaa',): 'foo bar',
 
1106
            ('aab',): 'common altered b', ('at',): 'foo bar t'}
1111
1107
        basis = self._get_map(basis_dict, maximum_size=10)
1112
1108
        target = self._get_map(target_dict, maximum_size=10,
1113
 
                               chk_bytes=basis._store)
 
1109
            chk_bytes=basis._store)
1114
1110
        basis_get = basis._store.get_record_stream
1115
 
 
1116
1111
        def get_record_stream(keys, order, fulltext):
1117
 
            if (b'sha1:1adf7c0d1b9140ab5f33bb64c6275fa78b1580b7',) in keys:
 
1112
            if ('sha1:1adf7c0d1b9140ab5f33bb64c6275fa78b1580b7',) in keys:
1118
1113
                raise AssertionError("'aaa' pointer was followed %r" % keys)
1119
1114
            return basis_get(keys, order, fulltext)
1120
1115
        basis._store.get_record_stream = get_record_stream
1121
1116
        result = sorted(list(target.iter_changes(basis)))
1122
1117
        for change in result:
1123
 
            if change[0] == (b'aaa',):
 
1118
            if change[0] == ('aaa',):
1124
1119
                self.fail("Found unexpected change: %s" % change)
1125
1120
 
1126
1121
    def test_iter_changes_unchanged_keys_in_multi_key_leafs_ignored(self):
1127
1122
        # Within a leaf there are no hash's to exclude keys, make sure multi
1128
1123
        # value leaf nodes are handled well.
1129
 
        basis_dict = {(b'aaa',): b'foo bar',
1130
 
                      (b'aab',): b'common altered a', (b'b',): b'foo bar b'}
1131
 
        target_dict = {(b'aaa',): b'foo bar',
1132
 
                       (b'aab',): b'common altered b', (b'at',): b'foo bar t'}
 
1124
        basis_dict = {('aaa',): 'foo bar',
 
1125
            ('aab',): 'common altered a', ('b',): 'foo bar b'}
 
1126
        target_dict = {('aaa',): 'foo bar',
 
1127
            ('aab',): 'common altered b', ('at',): 'foo bar t'}
1133
1128
        changes = [
1134
 
            ((b'aab',), b'common altered a', b'common altered b'),
1135
 
            ((b'at',), None, b'foo bar t'),
1136
 
            ((b'b',), b'foo bar b', None),
 
1129
            (('aab',), 'common altered a', 'common altered b'),
 
1130
            (('at',), None, 'foo bar t'),
 
1131
            (('b',), 'foo bar b', None),
1137
1132
            ]
1138
1133
        basis = self._get_map(basis_dict)
1139
1134
        target = self._get_map(target_dict, chk_bytes=basis._store)
1148
1143
    def test_iteritems_two_items(self):
1149
1144
        chk_bytes = self.get_chk_bytes()
1150
1145
        root_key = CHKMap.from_dict(chk_bytes,
1151
 
                                    {(b"a", ): b"content here", (b"b", ): b"more content"})
 
1146
            {"a":"content here", "b":"more content"})
1152
1147
        chkmap = CHKMap(chk_bytes, root_key)
1153
 
        self.assertEqual([((b"a",), b"content here"), ((b"b",), b"more content")],
1154
 
                         sorted(list(chkmap.iteritems())))
 
1148
        self.assertEqual([(("a",), "content here"), (("b",), "more content")],
 
1149
            sorted(list(chkmap.iteritems())))
1155
1150
 
1156
1151
    def test_iteritems_selected_one_of_two_items(self):
1157
 
        chkmap = self._get_map(
1158
 
            {(b"a",): b"content here", (b"b",): b"more content"})
1159
 
        self.assertEqual({(b"a",): b"content here"},
1160
 
                         self.to_dict(chkmap, [(b"a",)]))
 
1152
        chkmap = self._get_map( {("a",):"content here", ("b",):"more content"})
 
1153
        self.assertEqual({("a",): "content here"},
 
1154
            self.to_dict(chkmap, [("a",)]))
1161
1155
 
1162
1156
    def test_iteritems_keys_prefixed_by_2_width_nodes(self):
1163
1157
        chkmap = self._get_map(
1164
 
            {(b"a", b"a"): b"content here", (b"a", b"b",): b"more content",
1165
 
             (b"b", b""): b'boring content'},
 
1158
            {("a", "a"):"content here", ("a", "b",):"more content",
 
1159
             ("b", ""): 'boring content'},
1166
1160
            maximum_size=10, key_width=2)
1167
1161
        self.assertEqual(
1168
 
            {(b"a", b"a"): b"content here", (b"a", b"b"): b'more content'},
1169
 
            self.to_dict(chkmap, [(b"a",)]))
 
1162
            {("a", "a"): "content here", ("a", "b"): 'more content'},
 
1163
            self.to_dict(chkmap, [("a",)]))
1170
1164
 
1171
1165
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1172
 
        search_key_func = chk_map.search_key_registry.get(b'hash-16-way')
1173
 
        self.assertEqual(b'E8B7BE43\x00E8B7BE43',
1174
 
                         search_key_func(StaticTuple(b'a', b'a')))
1175
 
        self.assertEqual(b'E8B7BE43\x0071BEEFF9',
1176
 
                         search_key_func(StaticTuple(b'a', b'b')))
1177
 
        self.assertEqual(b'71BEEFF9\x0000000000',
1178
 
                         search_key_func(StaticTuple(b'b', b'')))
 
1166
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
 
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', '')))
1179
1173
        chkmap = self._get_map(
1180
 
            {(b"a", b"a"): b"content here", (b"a", b"b",): b"more content",
1181
 
             (b"b", b""): b'boring content'},
 
1174
            {("a", "a"):"content here", ("a", "b",):"more content",
 
1175
             ("b", ""): 'boring content'},
1182
1176
            maximum_size=10, key_width=2, search_key_func=search_key_func)
1183
1177
        self.assertEqual(
1184
 
            {(b"a", b"a"): b"content here", (b"a", b"b"): b'more content'},
1185
 
            self.to_dict(chkmap, [(b"a",)]))
 
1178
            {("a", "a"): "content here", ("a", "b"): 'more content'},
 
1179
            self.to_dict(chkmap, [("a",)]))
1186
1180
 
1187
1181
    def test_iteritems_keys_prefixed_by_2_width_one_leaf(self):
1188
1182
        chkmap = self._get_map(
1189
 
            {(b"a", b"a"): b"content here", (b"a", b"b",): b"more content",
1190
 
             (b"b", b""): b'boring content'}, key_width=2)
 
1183
            {("a", "a"):"content here", ("a", "b",):"more content",
 
1184
             ("b", ""): 'boring content'}, key_width=2)
1191
1185
        self.assertEqual(
1192
 
            {(b"a", b"a"): b"content here", (b"a", b"b"): b'more content'},
1193
 
            self.to_dict(chkmap, [(b"a",)]))
 
1186
            {("a", "a"): "content here", ("a", "b"): 'more content'},
 
1187
            self.to_dict(chkmap, [("a",)]))
1194
1188
 
1195
1189
    def test___len__empty(self):
1196
1190
        chkmap = self._get_map({})
1197
1191
        self.assertEqual(0, len(chkmap))
1198
1192
 
1199
1193
    def test___len__2(self):
1200
 
        chkmap = self._get_map({(b"foo",): b"bar", (b"gam",): b"quux"})
 
1194
        chkmap = self._get_map({("foo",):"bar", ("gam",):"quux"})
1201
1195
        self.assertEqual(2, len(chkmap))
1202
1196
 
1203
1197
    def test_max_size_100_bytes_new(self):
1204
1198
        # When there is a 100 byte upper node limit, a tree is formed.
1205
 
        chkmap = self._get_map(
1206
 
            {(b"k1" * 50,): b"v1", (b"k2" * 50,): b"v2"}, maximum_size=100)
 
1199
        chkmap = self._get_map({("k1"*50,):"v1", ("k2"*50,):"v2"}, maximum_size=100)
1207
1200
        # We expect three nodes:
1208
1201
        # A root, with two children, and with two key prefixes - k1 to one, and
1209
1202
        # k2 to the other as our node splitting is only just being developed.
1213
1206
        self.assertEqual(1, chkmap._root_node._key_width)
1214
1207
        # There should be two child nodes, and prefix of 2(bytes):
1215
1208
        self.assertEqual(2, len(chkmap._root_node._items))
1216
 
        self.assertEqual(b"k", chkmap._root_node._compute_search_prefix())
 
1209
        self.assertEqual("k", chkmap._root_node._compute_search_prefix())
1217
1210
        # The actual nodes pointed at will change as serialisers change; so
1218
1211
        # here we test that the key prefix is correct; then load the nodes and
1219
1212
        # check they have the right pointed at key; whether they have the
1223
1216
        nodes = sorted(chkmap._root_node._items.items())
1224
1217
        ptr1 = nodes[0]
1225
1218
        ptr2 = nodes[1]
1226
 
        self.assertEqual(b'k1', ptr1[0])
1227
 
        self.assertEqual(b'k2', ptr2[0])
1228
 
        node1 = chk_map._deserialise(
1229
 
            chkmap._read_bytes(ptr1[1]), ptr1[1], None)
 
1219
        self.assertEqual('k1', ptr1[0])
 
1220
        self.assertEqual('k2', ptr2[0])
 
1221
        node1 = chk_map._deserialise(chkmap._read_bytes(ptr1[1]), ptr1[1], None)
1230
1222
        self.assertIsInstance(node1, LeafNode)
1231
1223
        self.assertEqual(1, len(node1))
1232
 
        self.assertEqual({(b'k1' * 50,): b'v1'},
1233
 
                         self.to_dict(node1, chkmap._store))
1234
 
        node2 = chk_map._deserialise(
1235
 
            chkmap._read_bytes(ptr2[1]), ptr2[1], None)
 
1224
        self.assertEqual({('k1'*50,): 'v1'}, self.to_dict(node1, chkmap._store))
 
1225
        node2 = chk_map._deserialise(chkmap._read_bytes(ptr2[1]), ptr2[1], None)
1236
1226
        self.assertIsInstance(node2, LeafNode)
1237
1227
        self.assertEqual(1, len(node2))
1238
 
        self.assertEqual({(b'k2' * 50,): b'v2'},
1239
 
                         self.to_dict(node2, chkmap._store))
 
1228
        self.assertEqual({('k2'*50,): 'v2'}, self.to_dict(node2, chkmap._store))
1240
1229
        # Having checked we have a good structure, check that the content is
1241
1230
        # still accessible.
1242
1231
        self.assertEqual(2, len(chkmap))
1243
 
        self.assertEqual({(b"k1" * 50,): b"v1", (b"k2" * 50,): b"v2"},
1244
 
                         self.to_dict(chkmap))
 
1232
        self.assertEqual({("k1"*50,): "v1", ("k2"*50,): "v2"},
 
1233
            self.to_dict(chkmap))
1245
1234
 
1246
1235
    def test_init_root_is_LeafNode_new(self):
1247
1236
        chk_bytes = self.get_chk_bytes()
1260
1249
    def test_map_first_item_new(self):
1261
1250
        chk_bytes = self.get_chk_bytes()
1262
1251
        chkmap = CHKMap(chk_bytes, None)
1263
 
        chkmap.map((b"foo,",), b"bar")
1264
 
        self.assertEqual({(b'foo,',): b'bar'}, self.to_dict(chkmap))
 
1252
        chkmap.map(("foo,",), "bar")
 
1253
        self.assertEqual({('foo,',): 'bar'}, self.to_dict(chkmap))
1265
1254
        self.assertEqual(1, len(chkmap))
1266
1255
        key = chkmap._save()
1267
1256
        leaf_node = LeafNode()
1268
 
        leaf_node.map(chk_bytes, (b"foo,",), b"bar")
 
1257
        leaf_node.map(chk_bytes, ("foo,",), "bar")
1269
1258
        self.assertEqual([key], leaf_node.serialise(chk_bytes))
1270
1259
 
1271
1260
    def test_unmap_last_item_root_is_leaf_new(self):
1272
 
        chkmap = self._get_map({(b"k1" * 50,): b"v1", (b"k2" * 50,): b"v2"})
1273
 
        chkmap.unmap((b"k1" * 50,))
1274
 
        chkmap.unmap((b"k2" * 50,))
 
1261
        chkmap = self._get_map({("k1"*50,): "v1", ("k2"*50,): "v2"})
 
1262
        chkmap.unmap(("k1"*50,))
 
1263
        chkmap.unmap(("k2"*50,))
1275
1264
        self.assertEqual(0, len(chkmap))
1276
1265
        self.assertEqual({}, self.to_dict(chkmap))
1277
1266
        key = chkmap._save()
1279
1268
        self.assertEqual([key], leaf_node.serialise(chkmap._store))
1280
1269
 
1281
1270
    def test__dump_tree(self):
1282
 
        chkmap = self._get_map({(b"aaa",): b"value1", (b"aab",): b"value2",
1283
 
                                (b"bbb",): b"value3", },
 
1271
        chkmap = self._get_map({("aaa",): "value1", ("aab",): "value2",
 
1272
                                ("bbb",): "value3",},
1284
1273
                               maximum_size=15)
1285
1274
        self.assertEqualDiff("'' InternalNode\n"
1286
1275
                             "  'a' InternalNode\n"
1312
1301
            chkmap._dump_tree(include_keys=True))
1313
1302
 
1314
1303
    def test__dump_tree_in_progress(self):
1315
 
        chkmap = self._get_map({(b"aaa",): b"value1", (b"aab",): b"value2"},
 
1304
        chkmap = self._get_map({("aaa",): "value1", ("aab",): "value2"},
1316
1305
                               maximum_size=10)
1317
 
        chkmap.map((b'bbb',), b'value3')
 
1306
        chkmap.map(('bbb',), 'value3')
1318
1307
        self.assertEqualDiff("'' InternalNode\n"
1319
1308
                             "  'a' InternalNode\n"
1320
1309
                             "    'aaa' LeafNode\n"
1342
1331
    """A search key function that maps all nodes to the same value"""
1343
1332
    return 'value'
1344
1333
 
1345
 
 
1346
1334
def _test_search_key(key):
1347
 
    return b'test:' + b'\x00'.join(key)
 
1335
    return 'test:' + '\x00'.join(key)
1348
1336
 
1349
1337
 
1350
1338
class TestMapSearchKeys(TestCaseWithStore):
1351
1339
 
1352
1340
    def test_default_chk_map_uses_flat_search_key(self):
1353
1341
        chkmap = chk_map.CHKMap(self.get_chk_bytes(), None)
1354
 
        self.assertEqual(b'1',
1355
 
                         chkmap._search_key_func((b'1',)))
1356
 
        self.assertEqual(b'1\x002',
1357
 
                         chkmap._search_key_func((b'1', b'2')))
1358
 
        self.assertEqual(b'1\x002\x003',
1359
 
                         chkmap._search_key_func((b'1', b'2', b'3')))
 
1342
        self.assertEqual('1',
 
1343
                         chkmap._search_key_func(('1',)))
 
1344
        self.assertEqual('1\x002',
 
1345
                         chkmap._search_key_func(('1', '2')))
 
1346
        self.assertEqual('1\x002\x003',
 
1347
                         chkmap._search_key_func(('1', '2', '3')))
1360
1348
 
1361
1349
    def test_search_key_is_passed_to_root_node(self):
1362
1350
        chkmap = chk_map.CHKMap(self.get_chk_bytes(), None,
1363
1351
                                search_key_func=_test_search_key)
1364
1352
        self.assertIs(_test_search_key, chkmap._search_key_func)
1365
 
        self.assertEqual(b'test:1\x002\x003',
1366
 
                         chkmap._search_key_func((b'1', b'2', b'3')))
1367
 
        self.assertEqual(b'test:1\x002\x003',
1368
 
                         chkmap._root_node._search_key((b'1', b'2', b'3')))
 
1353
        self.assertEqual('test:1\x002\x003',
 
1354
                         chkmap._search_key_func(('1', '2', '3')))
 
1355
        self.assertEqual('test:1\x002\x003',
 
1356
                         chkmap._root_node._search_key(('1', '2', '3')))
1369
1357
 
1370
1358
    def test_search_key_passed_via__ensure_root(self):
1371
1359
        chk_bytes = self.get_chk_bytes()
1375
1363
        chkmap = chk_map.CHKMap(chk_bytes, root_key,
1376
1364
                                search_key_func=_test_search_key)
1377
1365
        chkmap._ensure_root()
1378
 
        self.assertEqual(b'test:1\x002\x003',
1379
 
                         chkmap._root_node._search_key((b'1', b'2', b'3')))
 
1366
        self.assertEqual('test:1\x002\x003',
 
1367
                         chkmap._root_node._search_key(('1', '2', '3')))
1380
1368
 
1381
1369
    def test_search_key_with_internal_node(self):
1382
1370
        chk_bytes = self.get_chk_bytes()
1383
1371
        chkmap = chk_map.CHKMap(chk_bytes, None,
1384
1372
                                search_key_func=_test_search_key)
1385
1373
        chkmap._root_node.set_maximum_size(10)
1386
 
        chkmap.map((b'1',), b'foo')
1387
 
        chkmap.map((b'2',), b'bar')
1388
 
        chkmap.map((b'3',), b'baz')
 
1374
        chkmap.map(('1',), 'foo')
 
1375
        chkmap.map(('2',), 'bar')
 
1376
        chkmap.map(('3',), 'baz')
1389
1377
        self.assertEqualDiff("'' InternalNode\n"
1390
1378
                             "  'test:1' LeafNode\n"
1391
1379
                             "      ('1',) 'foo'\n"
1392
1380
                             "  'test:2' LeafNode\n"
1393
1381
                             "      ('2',) 'bar'\n"
1394
1382
                             "  'test:3' LeafNode\n"
1395
 
                             "      ('3',) 'baz'\n", chkmap._dump_tree())
 
1383
                             "      ('3',) 'baz'\n"
 
1384
                             , chkmap._dump_tree())
1396
1385
        root_key = chkmap._save()
1397
1386
        chkmap = chk_map.CHKMap(chk_bytes, root_key,
1398
1387
                                search_key_func=_test_search_key)
1402
1391
                             "  'test:2' LeafNode\n"
1403
1392
                             "      ('2',) 'bar'\n"
1404
1393
                             "  'test:3' LeafNode\n"
1405
 
                             "      ('3',) 'baz'\n", chkmap._dump_tree())
 
1394
                             "      ('3',) 'baz'\n"
 
1395
                             , chkmap._dump_tree())
1406
1396
 
1407
1397
    def test_search_key_16(self):
1408
1398
        chk_bytes = self.get_chk_bytes()
1409
1399
        chkmap = chk_map.CHKMap(chk_bytes, None,
1410
1400
                                search_key_func=chk_map._search_key_16)
1411
1401
        chkmap._root_node.set_maximum_size(10)
1412
 
        chkmap.map((b'1',), b'foo')
1413
 
        chkmap.map((b'2',), b'bar')
1414
 
        chkmap.map((b'3',), b'baz')
 
1402
        chkmap.map(('1',), 'foo')
 
1403
        chkmap.map(('2',), 'bar')
 
1404
        chkmap.map(('3',), 'baz')
1415
1405
        self.assertEqualDiff("'' InternalNode\n"
1416
1406
                             "  '1' LeafNode\n"
1417
1407
                             "      ('2',) 'bar'\n"
1418
1408
                             "  '6' LeafNode\n"
1419
1409
                             "      ('3',) 'baz'\n"
1420
1410
                             "  '8' LeafNode\n"
1421
 
                             "      ('1',) 'foo'\n", chkmap._dump_tree())
 
1411
                             "      ('1',) 'foo'\n"
 
1412
                             , chkmap._dump_tree())
1422
1413
        root_key = chkmap._save()
1423
1414
        chkmap = chk_map.CHKMap(chk_bytes, root_key,
1424
1415
                                search_key_func=chk_map._search_key_16)
1425
1416
        # We can get the values back correctly
1426
 
        self.assertEqual([((b'1',), b'foo')],
1427
 
                         list(chkmap.iteritems([(b'1',)])))
 
1417
        self.assertEqual([(('1',), 'foo')],
 
1418
                         list(chkmap.iteritems([('1',)])))
1428
1419
        self.assertEqualDiff("'' InternalNode\n"
1429
1420
                             "  '1' LeafNode\n"
1430
1421
                             "      ('2',) 'bar'\n"
1431
1422
                             "  '6' LeafNode\n"
1432
1423
                             "      ('3',) 'baz'\n"
1433
1424
                             "  '8' LeafNode\n"
1434
 
                             "      ('1',) 'foo'\n", chkmap._dump_tree())
 
1425
                             "      ('1',) 'foo'\n"
 
1426
                             , chkmap._dump_tree())
1435
1427
 
1436
1428
    def test_search_key_255(self):
1437
1429
        chk_bytes = self.get_chk_bytes()
1438
1430
        chkmap = chk_map.CHKMap(chk_bytes, None,
1439
1431
                                search_key_func=chk_map._search_key_255)
1440
1432
        chkmap._root_node.set_maximum_size(10)
1441
 
        chkmap.map((b'1',), b'foo')
1442
 
        chkmap.map((b'2',), b'bar')
1443
 
        chkmap.map((b'3',), b'baz')
 
1433
        chkmap.map(('1',), 'foo')
 
1434
        chkmap.map(('2',), 'bar')
 
1435
        chkmap.map(('3',), 'baz')
1444
1436
        self.assertEqualDiff("'' InternalNode\n"
1445
1437
                             "  '\\x1a' LeafNode\n"
1446
1438
                             "      ('2',) 'bar'\n"
1447
1439
                             "  'm' LeafNode\n"
1448
1440
                             "      ('3',) 'baz'\n"
1449
1441
                             "  '\\x83' LeafNode\n"
1450
 
                             "      ('1',) 'foo'\n", chkmap._dump_tree(encoding='latin1'))
 
1442
                             "      ('1',) 'foo'\n"
 
1443
                             , chkmap._dump_tree())
1451
1444
        root_key = chkmap._save()
1452
1445
        chkmap = chk_map.CHKMap(chk_bytes, root_key,
1453
1446
                                search_key_func=chk_map._search_key_255)
1454
1447
        # We can get the values back correctly
1455
 
        self.assertEqual([((b'1',), b'foo')],
1456
 
                         list(chkmap.iteritems([(b'1',)])))
 
1448
        self.assertEqual([(('1',), 'foo')],
 
1449
                         list(chkmap.iteritems([('1',)])))
1457
1450
        self.assertEqualDiff("'' InternalNode\n"
1458
1451
                             "  '\\x1a' LeafNode\n"
1459
1452
                             "      ('2',) 'bar'\n"
1460
1453
                             "  'm' LeafNode\n"
1461
1454
                             "      ('3',) 'baz'\n"
1462
1455
                             "  '\\x83' LeafNode\n"
1463
 
                             "      ('1',) 'foo'\n", chkmap._dump_tree(encoding='latin1'))
 
1456
                             "      ('1',) 'foo'\n"
 
1457
                             , chkmap._dump_tree())
1464
1458
 
1465
1459
    def test_search_key_collisions(self):
1466
1460
        chkmap = chk_map.CHKMap(self.get_chk_bytes(), None,
1468
1462
        # The node will want to expand, but it cannot, because it knows that
1469
1463
        # all the keys must map to this node
1470
1464
        chkmap._root_node.set_maximum_size(20)
1471
 
        chkmap.map((b'1',), b'foo')
1472
 
        chkmap.map((b'2',), b'bar')
1473
 
        chkmap.map((b'3',), b'baz')
 
1465
        chkmap.map(('1',), 'foo')
 
1466
        chkmap.map(('2',), 'bar')
 
1467
        chkmap.map(('3',), 'baz')
1474
1468
        self.assertEqualDiff("'' LeafNode\n"
1475
1469
                             "      ('1',) 'foo'\n"
1476
1470
                             "      ('2',) 'bar'\n"
1477
 
                             "      ('3',) 'baz'\n", chkmap._dump_tree())
 
1471
                             "      ('3',) 'baz'\n"
 
1472
                             , chkmap._dump_tree())
1478
1473
 
1479
1474
 
1480
1475
class TestLeafNode(TestCaseWithStore):
1496
1491
    def test_current_size_items(self):
1497
1492
        node = LeafNode()
1498
1493
        base_size = node._current_size()
1499
 
        node.map(None, (b"foo bar",), b"baz")
 
1494
        node.map(None, ("foo bar",), "baz")
1500
1495
        self.assertEqual(base_size + 14, node._current_size())
1501
1496
 
1502
1497
    def test_deserialise_empty(self):
1503
 
        node = LeafNode.deserialise(b"chkleaf:\n10\n1\n0\n\n", (b"sha1:1234",))
 
1498
        node = LeafNode.deserialise("chkleaf:\n10\n1\n0\n\n", ("sha1:1234",))
1504
1499
        self.assertEqual(0, len(node))
1505
1500
        self.assertEqual(10, node.maximum_size)
1506
 
        self.assertEqual((b"sha1:1234",), node.key())
 
1501
        self.assertEqual(("sha1:1234",), node.key())
1507
1502
        self.assertIs(None, node._search_prefix)
1508
1503
        self.assertIs(None, node._common_serialised_prefix)
1509
1504
 
1510
1505
    def test_deserialise_items(self):
1511
1506
        node = LeafNode.deserialise(
1512
 
            b"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1513
 
            (b"sha1:1234",))
 
1507
            "chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
 
1508
            ("sha1:1234",))
1514
1509
        self.assertEqual(2, len(node))
1515
 
        self.assertEqual([((b"foo bar",), b"baz"), ((b"quux",), b"blarh")],
1516
 
                         sorted(node.iteritems(None)))
 
1510
        self.assertEqual([(("foo bar",), "baz"), (("quux",), "blarh")],
 
1511
            sorted(node.iteritems(None)))
1517
1512
 
1518
1513
    def test_deserialise_item_with_null_width_1(self):
1519
1514
        node = LeafNode.deserialise(
1520
 
            b"chkleaf:\n0\n1\n2\n\nfoo\x001\nbar\x00baz\nquux\x001\nblarh\n",
1521
 
            (b"sha1:1234",))
 
1515
            "chkleaf:\n0\n1\n2\n\nfoo\x001\nbar\x00baz\nquux\x001\nblarh\n",
 
1516
            ("sha1:1234",))
1522
1517
        self.assertEqual(2, len(node))
1523
 
        self.assertEqual([((b"foo",), b"bar\x00baz"), ((b"quux",), b"blarh")],
1524
 
                         sorted(node.iteritems(None)))
 
1518
        self.assertEqual([(("foo",), "bar\x00baz"), (("quux",), "blarh")],
 
1519
            sorted(node.iteritems(None)))
1525
1520
 
1526
1521
    def test_deserialise_item_with_null_width_2(self):
1527
1522
        node = LeafNode.deserialise(
1528
 
            b"chkleaf:\n0\n2\n2\n\nfoo\x001\x001\nbar\x00baz\n"
1529
 
            b"quux\x00\x001\nblarh\n",
1530
 
            (b"sha1:1234",))
 
1523
            "chkleaf:\n0\n2\n2\n\nfoo\x001\x001\nbar\x00baz\n"
 
1524
            "quux\x00\x001\nblarh\n",
 
1525
            ("sha1:1234",))
1531
1526
        self.assertEqual(2, len(node))
1532
 
        self.assertEqual([((b"foo", b"1"), b"bar\x00baz"), ((b"quux", b""), b"blarh")],
1533
 
                         sorted(node.iteritems(None)))
 
1527
        self.assertEqual([(("foo", "1"), "bar\x00baz"), (("quux", ""), "blarh")],
 
1528
            sorted(node.iteritems(None)))
1534
1529
 
1535
1530
    def test_iteritems_selected_one_of_two_items(self):
1536
1531
        node = LeafNode.deserialise(
1537
 
            b"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1538
 
            (b"sha1:1234",))
 
1532
            "chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
 
1533
            ("sha1:1234",))
1539
1534
        self.assertEqual(2, len(node))
1540
 
        self.assertEqual([((b"quux",), b"blarh")],
1541
 
                         sorted(node.iteritems(None, [(b"quux",), (b"qaz",)])))
 
1535
        self.assertEqual([(("quux",), "blarh")],
 
1536
            sorted(node.iteritems(None, [("quux",), ("qaz",)])))
1542
1537
 
1543
1538
    def test_deserialise_item_with_common_prefix(self):
1544
1539
        node = LeafNode.deserialise(
1545
 
            b"chkleaf:\n0\n2\n2\nfoo\x00\n1\x001\nbar\x00baz\n2\x001\nblarh\n",
1546
 
            (b"sha1:1234",))
 
1540
            "chkleaf:\n0\n2\n2\nfoo\x00\n1\x001\nbar\x00baz\n2\x001\nblarh\n",
 
1541
            ("sha1:1234",))
1547
1542
        self.assertEqual(2, len(node))
1548
 
        self.assertEqual([((b"foo", b"1"), b"bar\x00baz"), ((b"foo", b"2"), b"blarh")],
1549
 
                         sorted(node.iteritems(None)))
 
1543
        self.assertEqual([(("foo", "1"), "bar\x00baz"), (("foo", "2"), "blarh")],
 
1544
            sorted(node.iteritems(None)))
1550
1545
        self.assertIs(chk_map._unknown, node._search_prefix)
1551
 
        self.assertEqual(b'foo\x00', node._common_serialised_prefix)
 
1546
        self.assertEqual('foo\x00', node._common_serialised_prefix)
1552
1547
 
1553
1548
    def test_deserialise_multi_line(self):
1554
1549
        node = LeafNode.deserialise(
1555
 
            b"chkleaf:\n0\n2\n2\nfoo\x00\n1\x002\nbar\nbaz\n2\x002\nblarh\n\n",
1556
 
            (b"sha1:1234",))
 
1550
            "chkleaf:\n0\n2\n2\nfoo\x00\n1\x002\nbar\nbaz\n2\x002\nblarh\n\n",
 
1551
            ("sha1:1234",))
1557
1552
        self.assertEqual(2, len(node))
1558
 
        self.assertEqual([((b"foo", b"1"), b"bar\nbaz"),
1559
 
                          ((b"foo", b"2"), b"blarh\n"),
1560
 
                          ], sorted(node.iteritems(None)))
 
1553
        self.assertEqual([(("foo", "1"), "bar\nbaz"),
 
1554
                          (("foo", "2"), "blarh\n"),
 
1555
                         ], sorted(node.iteritems(None)))
1561
1556
        self.assertIs(chk_map._unknown, node._search_prefix)
1562
 
        self.assertEqual(b'foo\x00', node._common_serialised_prefix)
 
1557
        self.assertEqual('foo\x00', node._common_serialised_prefix)
1563
1558
 
1564
1559
    def test_key_new(self):
1565
1560
        node = LeafNode()
1566
1561
        self.assertEqual(None, node.key())
1567
1562
 
1568
1563
    def test_key_after_map(self):
1569
 
        node = LeafNode.deserialise(b"chkleaf:\n10\n1\n0\n\n", (b"sha1:1234",))
1570
 
        node.map(None, (b"foo bar",), b"baz quux")
 
1564
        node = LeafNode.deserialise("chkleaf:\n10\n1\n0\n\n", ("sha1:1234",))
 
1565
        node.map(None, ("foo bar",), "baz quux")
1571
1566
        self.assertEqual(None, node.key())
1572
1567
 
1573
1568
    def test_key_after_unmap(self):
1574
1569
        node = LeafNode.deserialise(
1575
 
            b"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1576
 
            (b"sha1:1234",))
1577
 
        node.unmap(None, (b"foo bar",))
 
1570
            "chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
 
1571
            ("sha1:1234",))
 
1572
        node.unmap(None, ("foo bar",))
1578
1573
        self.assertEqual(None, node.key())
1579
1574
 
1580
1575
    def test_map_exceeding_max_size_only_entry_new(self):
1581
1576
        node = LeafNode()
1582
1577
        node.set_maximum_size(10)
1583
 
        result = node.map(None, (b"foo bar",), b"baz quux")
1584
 
        self.assertEqual((b"foo bar", [(b"", node)]), result)
 
1578
        result = node.map(None, ("foo bar",), "baz quux")
 
1579
        self.assertEqual(("foo bar", [("", node)]), result)
1585
1580
        self.assertTrue(10 < node._current_size())
1586
1581
 
1587
1582
    def test_map_exceeding_max_size_second_entry_early_difference_new(self):
1588
1583
        node = LeafNode()
1589
1584
        node.set_maximum_size(10)
1590
 
        node.map(None, (b"foo bar",), b"baz quux")
1591
 
        prefix, result = list(node.map(None, (b"blue",), b"red"))
1592
 
        self.assertEqual(b"", prefix)
 
1585
        node.map(None, ("foo bar",), "baz quux")
 
1586
        prefix, result = list(node.map(None, ("blue",), "red"))
 
1587
        self.assertEqual("", prefix)
1593
1588
        self.assertEqual(2, len(result))
1594
1589
        split_chars = {result[0][0], result[1][0]}
1595
 
        self.assertEqual({b"f", b"b"}, split_chars)
 
1590
        self.assertEqual({"f", "b"}, split_chars)
1596
1591
        nodes = dict(result)
1597
 
        node = nodes[b"f"]
1598
 
        self.assertEqual({(b"foo bar",): b"baz quux"},
1599
 
                         self.to_dict(node, None))
 
1592
        node = nodes["f"]
 
1593
        self.assertEqual({("foo bar",): "baz quux"}, self.to_dict(node, None))
1600
1594
        self.assertEqual(10, node.maximum_size)
1601
1595
        self.assertEqual(1, node._key_width)
1602
 
        node = nodes[b"b"]
1603
 
        self.assertEqual({(b"blue",): b"red"}, self.to_dict(node, None))
 
1596
        node = nodes["b"]
 
1597
        self.assertEqual({("blue",): "red"}, self.to_dict(node, None))
1604
1598
        self.assertEqual(10, node.maximum_size)
1605
1599
        self.assertEqual(1, node._key_width)
1606
1600
 
1607
1601
    def test_map_first(self):
1608
1602
        node = LeafNode()
1609
 
        result = node.map(None, (b"foo bar",), b"baz quux")
1610
 
        self.assertEqual((b"foo bar", [(b"", node)]), result)
1611
 
        self.assertEqual({(b"foo bar",): b"baz quux"},
1612
 
                         self.to_dict(node, None))
 
1603
        result = node.map(None, ("foo bar",), "baz quux")
 
1604
        self.assertEqual(("foo bar", [("", node)]), result)
 
1605
        self.assertEqual({("foo bar",):"baz quux"}, self.to_dict(node, None))
1613
1606
        self.assertEqual(1, len(node))
1614
1607
 
1615
1608
    def test_map_second(self):
1616
1609
        node = LeafNode()
1617
 
        node.map(None, (b"foo bar",), b"baz quux")
1618
 
        result = node.map(None, (b"bingo",), b"bango")
1619
 
        self.assertEqual((b"", [(b"", node)]), result)
1620
 
        self.assertEqual({(b"foo bar",): b"baz quux", (b"bingo",): b"bango"},
1621
 
                         self.to_dict(node, None))
 
1610
        node.map(None, ("foo bar",), "baz quux")
 
1611
        result = node.map(None, ("bingo",), "bango")
 
1612
        self.assertEqual(("", [("", node)]), result)
 
1613
        self.assertEqual({("foo bar",):"baz quux", ("bingo",):"bango"},
 
1614
            self.to_dict(node, None))
1622
1615
        self.assertEqual(2, len(node))
1623
1616
 
1624
1617
    def test_map_replacement(self):
1625
1618
        node = LeafNode()
1626
 
        node.map(None, (b"foo bar",), b"baz quux")
1627
 
        result = node.map(None, (b"foo bar",), b"bango")
1628
 
        self.assertEqual((b"foo bar", [(b"", node)]), result)
1629
 
        self.assertEqual({(b"foo bar",): b"bango"},
1630
 
                         self.to_dict(node, None))
 
1619
        node.map(None, ("foo bar",), "baz quux")
 
1620
        result = node.map(None, ("foo bar",), "bango")
 
1621
        self.assertEqual(("foo bar", [("", node)]), result)
 
1622
        self.assertEqual({("foo bar",): "bango"},
 
1623
            self.to_dict(node, None))
1631
1624
        self.assertEqual(1, len(node))
1632
1625
 
1633
1626
    def test_serialise_empty(self):
1634
1627
        store = self.get_chk_bytes()
1635
1628
        node = LeafNode()
1636
1629
        node.set_maximum_size(10)
1637
 
        expected_key = (b"sha1:f34c3f0634ea3f85953dffa887620c0a5b1f4a51",)
 
1630
        expected_key = ("sha1:f34c3f0634ea3f85953dffa887620c0a5b1f4a51",)
1638
1631
        self.assertEqual([expected_key],
1639
 
                         list(node.serialise(store)))
1640
 
        self.assertEqual(b"chkleaf:\n10\n1\n0\n\n",
1641
 
                         self.read_bytes(store, expected_key))
 
1632
            list(node.serialise(store)))
 
1633
        self.assertEqual("chkleaf:\n10\n1\n0\n\n", self.read_bytes(store, expected_key))
1642
1634
        self.assertEqual(expected_key, node.key())
1643
1635
 
1644
1636
    def test_serialise_items(self):
1645
1637
        store = self.get_chk_bytes()
1646
1638
        node = LeafNode()
1647
1639
        node.set_maximum_size(10)
1648
 
        node.map(None, (b"foo bar",), b"baz quux")
1649
 
        expected_key = (b"sha1:f89fac7edfc6bdb1b1b54a556012ff0c646ef5e0",)
1650
 
        self.assertEqual(b'foo bar', node._common_serialised_prefix)
 
1640
        node.map(None, ("foo bar",), "baz quux")
 
1641
        expected_key = ("sha1:f89fac7edfc6bdb1b1b54a556012ff0c646ef5e0",)
 
1642
        self.assertEqual('foo bar', node._common_serialised_prefix)
1651
1643
        self.assertEqual([expected_key],
1652
 
                         list(node.serialise(store)))
1653
 
        self.assertEqual(b"chkleaf:\n10\n1\n1\nfoo bar\n\x001\nbaz quux\n",
1654
 
                         self.read_bytes(store, expected_key))
 
1644
            list(node.serialise(store)))
 
1645
        self.assertEqual("chkleaf:\n10\n1\n1\nfoo bar\n\x001\nbaz quux\n",
 
1646
            self.read_bytes(store, expected_key))
1655
1647
        self.assertEqual(expected_key, node.key())
1656
1648
 
1657
1649
    def test_unique_serialised_prefix_empty_new(self):
1660
1652
 
1661
1653
    def test_unique_serialised_prefix_one_item_new(self):
1662
1654
        node = LeafNode()
1663
 
        node.map(None, (b"foo bar", b"baz"), b"baz quux")
1664
 
        self.assertEqual(b"foo bar\x00baz", node._compute_search_prefix())
 
1655
        node.map(None, ("foo bar", "baz"), "baz quux")
 
1656
        self.assertEqual("foo bar\x00baz", node._compute_search_prefix())
1665
1657
 
1666
1658
    def test_unmap_missing(self):
1667
1659
        node = LeafNode()
1668
 
        self.assertRaises(KeyError, node.unmap, None, (b"foo bar",))
 
1660
        self.assertRaises(KeyError, node.unmap, None, ("foo bar",))
1669
1661
 
1670
1662
    def test_unmap_present(self):
1671
1663
        node = LeafNode()
1672
 
        node.map(None, (b"foo bar",), b"baz quux")
1673
 
        result = node.unmap(None, (b"foo bar",))
 
1664
        node.map(None, ("foo bar",), "baz quux")
 
1665
        result = node.unmap(None, ("foo bar",))
1674
1666
        self.assertEqual(node, result)
1675
1667
        self.assertEqual({}, self.to_dict(node, None))
1676
1668
        self.assertEqual(0, len(node))
1678
1670
    def test_map_maintains_common_prefixes(self):
1679
1671
        node = LeafNode()
1680
1672
        node._key_width = 2
1681
 
        node.map(None, (b"foo bar", b"baz"), b"baz quux")
1682
 
        self.assertEqual(b'foo bar\x00baz', node._search_prefix)
1683
 
        self.assertEqual(b'foo bar\x00baz', node._common_serialised_prefix)
1684
 
        node.map(None, (b"foo bar", b"bing"), b"baz quux")
1685
 
        self.assertEqual(b'foo bar\x00b', node._search_prefix)
1686
 
        self.assertEqual(b'foo bar\x00b', node._common_serialised_prefix)
1687
 
        node.map(None, (b"fool", b"baby"), b"baz quux")
1688
 
        self.assertEqual(b'foo', node._search_prefix)
1689
 
        self.assertEqual(b'foo', node._common_serialised_prefix)
1690
 
        node.map(None, (b"foo bar", b"baz"), b"replaced")
1691
 
        self.assertEqual(b'foo', node._search_prefix)
1692
 
        self.assertEqual(b'foo', node._common_serialised_prefix)
1693
 
        node.map(None, (b"very", b"different"), b"value")
1694
 
        self.assertEqual(b'', node._search_prefix)
1695
 
        self.assertEqual(b'', node._common_serialised_prefix)
 
1673
        node.map(None, ("foo bar", "baz"), "baz quux")
 
1674
        self.assertEqual('foo bar\x00baz', node._search_prefix)
 
1675
        self.assertEqual('foo bar\x00baz', node._common_serialised_prefix)
 
1676
        node.map(None, ("foo bar", "bing"), "baz quux")
 
1677
        self.assertEqual('foo bar\x00b', node._search_prefix)
 
1678
        self.assertEqual('foo bar\x00b', node._common_serialised_prefix)
 
1679
        node.map(None, ("fool", "baby"), "baz quux")
 
1680
        self.assertEqual('foo', node._search_prefix)
 
1681
        self.assertEqual('foo', node._common_serialised_prefix)
 
1682
        node.map(None, ("foo bar", "baz"), "replaced")
 
1683
        self.assertEqual('foo', node._search_prefix)
 
1684
        self.assertEqual('foo', node._common_serialised_prefix)
 
1685
        node.map(None, ("very", "different"), "value")
 
1686
        self.assertEqual('', node._search_prefix)
 
1687
        self.assertEqual('', node._common_serialised_prefix)
1696
1688
 
1697
1689
    def test_unmap_maintains_common_prefixes(self):
1698
1690
        node = LeafNode()
1699
1691
        node._key_width = 2
1700
 
        node.map(None, (b"foo bar", b"baz"), b"baz quux")
1701
 
        node.map(None, (b"foo bar", b"bing"), b"baz quux")
1702
 
        node.map(None, (b"fool", b"baby"), b"baz quux")
1703
 
        node.map(None, (b"very", b"different"), b"value")
1704
 
        self.assertEqual(b'', node._search_prefix)
1705
 
        self.assertEqual(b'', node._common_serialised_prefix)
1706
 
        node.unmap(None, (b"very", b"different"))
1707
 
        self.assertEqual(b"foo", node._search_prefix)
1708
 
        self.assertEqual(b"foo", node._common_serialised_prefix)
1709
 
        node.unmap(None, (b"fool", b"baby"))
1710
 
        self.assertEqual(b'foo bar\x00b', node._search_prefix)
1711
 
        self.assertEqual(b'foo bar\x00b', node._common_serialised_prefix)
1712
 
        node.unmap(None, (b"foo bar", b"baz"))
1713
 
        self.assertEqual(b'foo bar\x00bing', node._search_prefix)
1714
 
        self.assertEqual(b'foo bar\x00bing', node._common_serialised_prefix)
1715
 
        node.unmap(None, (b"foo bar", b"bing"))
 
1692
        node.map(None, ("foo bar", "baz"), "baz quux")
 
1693
        node.map(None, ("foo bar", "bing"), "baz quux")
 
1694
        node.map(None, ("fool", "baby"), "baz quux")
 
1695
        node.map(None, ("very", "different"), "value")
 
1696
        self.assertEqual('', node._search_prefix)
 
1697
        self.assertEqual('', node._common_serialised_prefix)
 
1698
        node.unmap(None, ("very", "different"))
 
1699
        self.assertEqual("foo", node._search_prefix)
 
1700
        self.assertEqual("foo", node._common_serialised_prefix)
 
1701
        node.unmap(None, ("fool", "baby"))
 
1702
        self.assertEqual('foo bar\x00b', node._search_prefix)
 
1703
        self.assertEqual('foo bar\x00b', node._common_serialised_prefix)
 
1704
        node.unmap(None, ("foo bar", "baz"))
 
1705
        self.assertEqual('foo bar\x00bing', node._search_prefix)
 
1706
        self.assertEqual('foo bar\x00bing', node._common_serialised_prefix)
 
1707
        node.unmap(None, ("foo bar", "bing"))
1716
1708
        self.assertEqual(None, node._search_prefix)
1717
1709
        self.assertEqual(None, node._common_serialised_prefix)
1718
1710
 
1720
1712
class TestInternalNode(TestCaseWithStore):
1721
1713
 
1722
1714
    def test_add_node_empty_new(self):
1723
 
        node = InternalNode(b'fo')
 
1715
        node = InternalNode('fo')
1724
1716
        child = LeafNode()
1725
1717
        child.set_maximum_size(100)
1726
 
        child.map(None, (b"foo",), b"bar")
1727
 
        node.add_node(b"foo", child)
 
1718
        child.map(None, ("foo",), "bar")
 
1719
        node.add_node("foo", child)
1728
1720
        # Note that node isn't strictly valid now as a tree (only one child),
1729
1721
        # but thats ok for this test.
1730
1722
        # The first child defines the node's width:
1731
1723
        self.assertEqual(3, node._node_width)
1732
1724
        # We should be able to iterate over the contents without doing IO.
1733
 
        self.assertEqual({(b'foo',): b'bar'}, self.to_dict(node, None))
 
1725
        self.assertEqual({('foo',): 'bar'}, self.to_dict(node, None))
1734
1726
        # The length should be known:
1735
1727
        self.assertEqual(1, len(node))
1736
1728
        # serialising the node should serialise the child and the node.
1738
1730
        keys = list(node.serialise(chk_bytes))
1739
1731
        child_key = child.serialise(chk_bytes)[0]
1740
1732
        self.assertEqual(
1741
 
            [child_key, (b'sha1:cf67e9997d8228a907c1f5bfb25a8bd9cd916fac',)],
 
1733
            [child_key, ('sha1:cf67e9997d8228a907c1f5bfb25a8bd9cd916fac',)],
1742
1734
            keys)
1743
1735
        # We should be able to access deserialised content.
1744
1736
        bytes = self.read_bytes(chk_bytes, keys[1])
1745
1737
        node = chk_map._deserialise(bytes, keys[1], None)
1746
1738
        self.assertEqual(1, len(node))
1747
 
        self.assertEqual({(b'foo',): b'bar'}, self.to_dict(node, chk_bytes))
 
1739
        self.assertEqual({('foo',): 'bar'}, self.to_dict(node, chk_bytes))
1748
1740
        self.assertEqual(3, node._node_width)
1749
1741
 
1750
1742
    def test_add_node_resets_key_new(self):
1751
 
        node = InternalNode(b'fo')
 
1743
        node = InternalNode('fo')
1752
1744
        child = LeafNode()
1753
1745
        child.set_maximum_size(100)
1754
 
        child.map(None, (b"foo",), b"bar")
1755
 
        node.add_node(b"foo", child)
 
1746
        child.map(None, ("foo",), "bar")
 
1747
        node.add_node("foo", child)
1756
1748
        chk_bytes = self.get_chk_bytes()
1757
1749
        keys = list(node.serialise(chk_bytes))
1758
1750
        self.assertEqual(keys[1], node._key)
1759
 
        node.add_node(b"fos", child)
 
1751
        node.add_node("fos", child)
1760
1752
        self.assertEqual(None, node._key)
1761
1753
 
1762
1754
#    def test_add_node_empty_oversized_one_ok_new(self):
1765
1757
#    def test_add_node_one_oversized_second_splits_errors(self):
1766
1758
 
1767
1759
    def test__iter_nodes_no_key_filter(self):
1768
 
        node = InternalNode(b'')
1769
 
        child = LeafNode()
1770
 
        child.set_maximum_size(100)
1771
 
        child.map(None, (b"foo",), b"bar")
1772
 
        node.add_node(b"f", child)
1773
 
        child = LeafNode()
1774
 
        child.set_maximum_size(100)
1775
 
        child.map(None, (b"bar",), b"baz")
1776
 
        node.add_node(b"b", child)
 
1760
        node = InternalNode('')
 
1761
        child = LeafNode()
 
1762
        child.set_maximum_size(100)
 
1763
        child.map(None, ("foo",), "bar")
 
1764
        node.add_node("f", child)
 
1765
        child = LeafNode()
 
1766
        child.set_maximum_size(100)
 
1767
        child.map(None, ("bar",), "baz")
 
1768
        node.add_node("b", child)
1777
1769
 
1778
1770
        for child, node_key_filter in node._iter_nodes(None, key_filter=None):
1779
1771
            self.assertEqual(None, node_key_filter)
1780
1772
 
1781
1773
    def test__iter_nodes_splits_key_filter(self):
1782
 
        node = InternalNode(b'')
1783
 
        child = LeafNode()
1784
 
        child.set_maximum_size(100)
1785
 
        child.map(None, (b"foo",), b"bar")
1786
 
        node.add_node(b"f", child)
1787
 
        child = LeafNode()
1788
 
        child.set_maximum_size(100)
1789
 
        child.map(None, (b"bar",), b"baz")
1790
 
        node.add_node(b"b", child)
 
1774
        node = InternalNode('')
 
1775
        child = LeafNode()
 
1776
        child.set_maximum_size(100)
 
1777
        child.map(None, ("foo",), "bar")
 
1778
        node.add_node("f", child)
 
1779
        child = LeafNode()
 
1780
        child.set_maximum_size(100)
 
1781
        child.map(None, ("bar",), "baz")
 
1782
        node.add_node("b", child)
1791
1783
 
1792
1784
        # foo and bar both match exactly one leaf node, but 'cat' should not
1793
1785
        # match any, and should not be placed in one.
1794
 
        key_filter = ((b'foo',), (b'bar',), (b'cat',))
 
1786
        key_filter = (('foo',), ('bar',), ('cat',))
1795
1787
        for child, node_key_filter in node._iter_nodes(None,
1796
1788
                                                       key_filter=key_filter):
1797
1789
            # each child could only match one key filter, so make sure it was
1799
1791
            self.assertEqual(1, len(node_key_filter))
1800
1792
 
1801
1793
    def test__iter_nodes_with_multiple_matches(self):
1802
 
        node = InternalNode(b'')
1803
 
        child = LeafNode()
1804
 
        child.set_maximum_size(100)
1805
 
        child.map(None, (b"foo",), b"val")
1806
 
        child.map(None, (b"fob",), b"val")
1807
 
        node.add_node(b"f", child)
1808
 
        child = LeafNode()
1809
 
        child.set_maximum_size(100)
1810
 
        child.map(None, (b"bar",), b"val")
1811
 
        child.map(None, (b"baz",), b"val")
1812
 
        node.add_node(b"b", child)
 
1794
        node = InternalNode('')
 
1795
        child = LeafNode()
 
1796
        child.set_maximum_size(100)
 
1797
        child.map(None, ("foo",), "val")
 
1798
        child.map(None, ("fob",), "val")
 
1799
        node.add_node("f", child)
 
1800
        child = LeafNode()
 
1801
        child.set_maximum_size(100)
 
1802
        child.map(None, ("bar",), "val")
 
1803
        child.map(None, ("baz",), "val")
 
1804
        node.add_node("b", child)
1813
1805
 
1814
1806
        # Note that 'ram' doesn't match anything, so it should be freely
1815
1807
        # ignored
1816
 
        key_filter = ((b'foo',), (b'fob',), (b'bar',), (b'baz',), (b'ram',))
 
1808
        key_filter = (('foo',), ('fob',), ('bar',), ('baz',), ('ram',))
1817
1809
        for child, node_key_filter in node._iter_nodes(None,
1818
1810
                                                       key_filter=key_filter):
1819
1811
            # each child could match two key filters, so make sure they were
1821
1813
            self.assertEqual(2, len(node_key_filter))
1822
1814
 
1823
1815
    def make_fo_fa_node(self):
1824
 
        node = InternalNode(b'f')
1825
 
        child = LeafNode()
1826
 
        child.set_maximum_size(100)
1827
 
        child.map(None, (b"foo",), b"val")
1828
 
        child.map(None, (b"fob",), b"val")
1829
 
        node.add_node(b'fo', child)
1830
 
        child = LeafNode()
1831
 
        child.set_maximum_size(100)
1832
 
        child.map(None, (b"far",), b"val")
1833
 
        child.map(None, (b"faz",), b"val")
1834
 
        node.add_node(b"fa", child)
 
1816
        node = InternalNode('f')
 
1817
        child = LeafNode()
 
1818
        child.set_maximum_size(100)
 
1819
        child.map(None, ("foo",), "val")
 
1820
        child.map(None, ("fob",), "val")
 
1821
        node.add_node('fo', child)
 
1822
        child = LeafNode()
 
1823
        child.set_maximum_size(100)
 
1824
        child.map(None, ("far",), "val")
 
1825
        child.map(None, ("faz",), "val")
 
1826
        node.add_node("fa", child)
1835
1827
        return node
1836
1828
 
1837
1829
    def test__iter_nodes_single_entry(self):
1838
1830
        node = self.make_fo_fa_node()
1839
 
        key_filter = [(b'foo',)]
 
1831
        key_filter = [('foo',)]
1840
1832
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
1841
1833
        self.assertEqual(1, len(nodes))
1842
1834
        self.assertEqual(key_filter, nodes[0][1])
1843
1835
 
1844
1836
    def test__iter_nodes_single_entry_misses(self):
1845
1837
        node = self.make_fo_fa_node()
1846
 
        key_filter = [(b'bar',)]
 
1838
        key_filter = [('bar',)]
1847
1839
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
1848
1840
        self.assertEqual(0, len(nodes))
1849
1841
 
1850
1842
    def test__iter_nodes_mixed_key_width(self):
1851
1843
        node = self.make_fo_fa_node()
1852
 
        key_filter = [(b'foo', b'bar'), (b'foo',), (b'fo',), (b'b',)]
 
1844
        key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('b',)]
1853
1845
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
1854
1846
        self.assertEqual(1, len(nodes))
1855
1847
        matches = key_filter[:]
1856
 
        matches.remove((b'b',))
 
1848
        matches.remove(('b',))
1857
1849
        self.assertEqual(sorted(matches), sorted(nodes[0][1]))
1858
1850
 
1859
1851
    def test__iter_nodes_match_all(self):
1860
1852
        node = self.make_fo_fa_node()
1861
 
        key_filter = [(b'foo', b'bar'), (b'foo',), (b'fo',), (b'f',)]
 
1853
        key_filter = [('foo', 'bar'), ('foo',), ('fo',), ('f',)]
1862
1854
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
1863
1855
        self.assertEqual(2, len(nodes))
1864
1856
 
1865
1857
    def test__iter_nodes_fixed_widths_and_misses(self):
1866
1858
        node = self.make_fo_fa_node()
1867
1859
        # foo and faa should both match one child, baz should miss
1868
 
        key_filter = [(b'foo',), (b'faa',), (b'baz',)]
 
1860
        key_filter = [('foo',), ('faa',), ('baz',)]
1869
1861
        nodes = list(node._iter_nodes(None, key_filter=key_filter))
1870
1862
        self.assertEqual(2, len(nodes))
1871
1863
        for node, matches in nodes:
1878
1870
    def test_iteritems_two_children(self):
1879
1871
        node = InternalNode()
1880
1872
        leaf1 = LeafNode()
1881
 
        leaf1.map(None, (b'foo bar',), b'quux')
 
1873
        leaf1.map(None, ('foo bar',), 'quux')
1882
1874
        leaf2 = LeafNode()
1883
 
        leaf2.map(None, (b'strange',), b'beast')
1884
 
        node.add_node(b"f", leaf1)
1885
 
        node.add_node(b"s", leaf2)
1886
 
        self.assertEqual([((b'foo bar',), b'quux'), ((b'strange',), b'beast')],
1887
 
                         sorted(node.iteritems(None)))
 
1875
        leaf2.map(None, ('strange',), 'beast')
 
1876
        node.add_node("f", leaf1)
 
1877
        node.add_node("s", leaf2)
 
1878
        self.assertEqual([(('foo bar',), 'quux'), (('strange',), 'beast')],
 
1879
            sorted(node.iteritems(None)))
1888
1880
 
1889
1881
    def test_iteritems_two_children_partial(self):
1890
1882
        node = InternalNode()
1891
1883
        leaf1 = LeafNode()
1892
 
        leaf1.map(None, (b'foo bar',), b'quux')
 
1884
        leaf1.map(None, ('foo bar',), 'quux')
1893
1885
        leaf2 = LeafNode()
1894
 
        leaf2.map(None, (b'strange',), b'beast')
1895
 
        node.add_node(b"f", leaf1)
 
1886
        leaf2.map(None, ('strange',), 'beast')
 
1887
        node.add_node("f", leaf1)
1896
1888
        # This sets up a path that should not be followed - it will error if
1897
1889
        # the code tries to.
1898
 
        node._items[b'f'] = None
1899
 
        node.add_node(b"s", leaf2)
1900
 
        self.assertEqual([((b'strange',), b'beast')],
1901
 
                         sorted(node.iteritems(None, [(b'strange',), (b'weird',)])))
 
1890
        node._items['f'] = None
 
1891
        node.add_node("s", leaf2)
 
1892
        self.assertEqual([(('strange',), 'beast')],
 
1893
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
1902
1894
 
1903
1895
    def test_iteritems_two_children_with_hash(self):
1904
 
        search_key_func = chk_map.search_key_registry.get(b'hash-255-way')
 
1896
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1905
1897
        node = InternalNode(search_key_func=search_key_func)
1906
1898
        leaf1 = LeafNode(search_key_func=search_key_func)
1907
 
        leaf1.map(None, StaticTuple(b'foo bar',), b'quux')
 
1899
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
1908
1900
        leaf2 = LeafNode(search_key_func=search_key_func)
1909
 
        leaf2.map(None, StaticTuple(b'strange',), b'beast')
1910
 
        self.assertEqual(b'\xbeF\x014', search_key_func(
1911
 
            StaticTuple(b'foo bar',)))
1912
 
        self.assertEqual(b'\x85\xfa\xf7K', search_key_func(
1913
 
            StaticTuple(b'strange',)))
1914
 
        node.add_node(b"\xbe", leaf1)
 
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',)))
 
1904
        node.add_node("\xbe", leaf1)
1915
1905
        # This sets up a path that should not be followed - it will error if
1916
1906
        # the code tries to.
1917
 
        node._items[b'\xbe'] = None
1918
 
        node.add_node(b"\x85", leaf2)
1919
 
        self.assertEqual([((b'strange',), b'beast')],
1920
 
                         sorted(node.iteritems(None, [StaticTuple(b'strange',),
1921
 
                                                      StaticTuple(b'weird',)])))
 
1907
        node._items['\xbe'] = None
 
1908
        node.add_node("\x85", leaf2)
 
1909
        self.assertEqual([(('strange',), 'beast')],
 
1910
            sorted(node.iteritems(None, [StaticTuple('strange',),
 
1911
                                         StaticTuple('weird',)])))
1922
1912
 
1923
1913
    def test_iteritems_partial_empty(self):
1924
1914
        node = InternalNode()
1925
 
        self.assertEqual([], sorted(node.iteritems([(b'missing',)])))
 
1915
        self.assertEqual([], sorted(node.iteritems([('missing',)])))
1926
1916
 
1927
1917
    def test_map_to_new_child_new(self):
1928
 
        chkmap = self._get_map(
1929
 
            {(b'k1',): b'foo', (b'k2',): b'bar'}, maximum_size=10)
 
1918
        chkmap = self._get_map({('k1',):'foo', ('k2',):'bar'}, maximum_size=10)
1930
1919
        chkmap._ensure_root()
1931
1920
        node = chkmap._root_node
1932
1921
        # Ensure test validity: nothing paged in below the root.
1933
1922
        self.assertEqual(2,
1934
 
                         len([value for value in node._items.values()
1935
 
                              if isinstance(value, StaticTuple)]))
 
1923
            len([value for value in node._items.values()
 
1924
                if isinstance(value, StaticTuple)]))
1936
1925
        # now, mapping to k3 should add a k3 leaf
1937
 
        prefix, nodes = node.map(None, (b'k3',), b'quux')
1938
 
        self.assertEqual(b"k", prefix)
1939
 
        self.assertEqual([(b"", node)], nodes)
 
1926
        prefix, nodes = node.map(None, ('k3',), 'quux')
 
1927
        self.assertEqual("k", prefix)
 
1928
        self.assertEqual([("", node)], nodes)
1940
1929
        # check new child details
1941
 
        child = node._items[b'k3']
 
1930
        child = node._items['k3']
1942
1931
        self.assertIsInstance(child, LeafNode)
1943
1932
        self.assertEqual(1, len(child))
1944
 
        self.assertEqual({(b'k3',): b'quux'}, self.to_dict(child, None))
 
1933
        self.assertEqual({('k3',): 'quux'}, self.to_dict(child, None))
1945
1934
        self.assertEqual(None, child._key)
1946
1935
        self.assertEqual(10, child.maximum_size)
1947
1936
        self.assertEqual(1, child._key_width)
1948
1937
        # Check overall structure:
1949
1938
        self.assertEqual(3, len(chkmap))
1950
 
        self.assertEqual({(b'k1',): b'foo', (b'k2',): b'bar', (b'k3',): b'quux'},
1951
 
                         self.to_dict(chkmap))
 
1939
        self.assertEqual({('k1',): 'foo', ('k2',): 'bar', ('k3',): 'quux'},
 
1940
            self.to_dict(chkmap))
1952
1941
        # serialising should only serialise the new data - k3 and the internal
1953
1942
        # node.
1954
1943
        keys = list(node.serialise(chkmap._store))
1956
1945
        self.assertEqual([child_key, keys[1]], keys)
1957
1946
 
1958
1947
    def test_map_to_child_child_splits_new(self):
1959
 
        chkmap = self._get_map(
1960
 
            {(b'k1',): b'foo', (b'k22',): b'bar'}, maximum_size=10)
 
1948
        chkmap = self._get_map({('k1',):'foo', ('k22',):'bar'}, maximum_size=10)
1961
1949
        # Check for the canonical root value for this tree:
1962
1950
        self.assertEqualDiff("'' InternalNode\n"
1963
1951
                             "  'k1' LeafNode\n"
1964
1952
                             "      ('k1',) 'foo'\n"
1965
1953
                             "  'k2' LeafNode\n"
1966
 
                             "      ('k22',) 'bar'\n", chkmap._dump_tree())
 
1954
                             "      ('k22',) 'bar'\n"
 
1955
                             , chkmap._dump_tree())
1967
1956
        # _dump_tree pages everything in, so reload using just the root
1968
1957
        chkmap = CHKMap(chkmap._store, chkmap._root_node)
1969
1958
        chkmap._ensure_root()
1970
1959
        node = chkmap._root_node
1971
1960
        # Ensure test validity: nothing paged in below the root.
1972
1961
        self.assertEqual(2,
1973
 
                         len([value for value in node._items.values()
1974
 
                              if isinstance(value, StaticTuple)]))
 
1962
            len([value for value in node._items.values()
 
1963
                if isinstance(value, StaticTuple)]))
1975
1964
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1976
1965
        # k23, which for simplicity in the current implementation generates
1977
1966
        # a new internal node between node, and k22/k23.
1978
 
        prefix, nodes = node.map(chkmap._store, (b'k23',), b'quux')
1979
 
        self.assertEqual(b"k", prefix)
1980
 
        self.assertEqual([(b"", node)], nodes)
 
1967
        prefix, nodes = node.map(chkmap._store, ('k23',), 'quux')
 
1968
        self.assertEqual("k", prefix)
 
1969
        self.assertEqual([("", node)], nodes)
1981
1970
        # check new child details
1982
 
        child = node._items[b'k2']
 
1971
        child = node._items['k2']
1983
1972
        self.assertIsInstance(child, InternalNode)
1984
1973
        self.assertEqual(2, len(child))
1985
 
        self.assertEqual({(b'k22',): b'bar', (b'k23',): b'quux'},
1986
 
                         self.to_dict(child, None))
 
1974
        self.assertEqual({('k22',): 'bar', ('k23',): 'quux'},
 
1975
            self.to_dict(child, None))
1987
1976
        self.assertEqual(None, child._key)
1988
1977
        self.assertEqual(10, child.maximum_size)
1989
1978
        self.assertEqual(1, child._key_width)
1990
1979
        self.assertEqual(3, child._node_width)
1991
1980
        # Check overall structure:
1992
1981
        self.assertEqual(3, len(chkmap))
1993
 
        self.assertEqual({(b'k1',): b'foo', (b'k22',): b'bar', (b'k23',): b'quux'},
1994
 
                         self.to_dict(chkmap))
 
1982
        self.assertEqual({('k1',): 'foo', ('k22',): 'bar', ('k23',): 'quux'},
 
1983
            self.to_dict(chkmap))
1995
1984
        # serialising should only serialise the new data - although k22 hasn't
1996
1985
        # changed because its a special corner case (splitting on with only one
1997
1986
        # key leaves one node unaltered), in general k22 is serialised, so we
1998
1987
        # expect k22, k23, the new internal node, and node, to be serialised.
1999
1988
        keys = list(node.serialise(chkmap._store))
2000
1989
        child_key = child._key
2001
 
        k22_key = child._items[b'k22']._key
2002
 
        k23_key = child._items[b'k23']._key
2003
 
        self.assertEqual({k22_key, k23_key, child_key, node.key()}, set(keys))
 
1990
        k22_key = child._items['k22']._key
 
1991
        k23_key = child._items['k23']._key
 
1992
        self.assertEqual([k22_key, k23_key, child_key, node.key()], keys)
2004
1993
        self.assertEqualDiff("'' InternalNode\n"
2005
1994
                             "  'k1' LeafNode\n"
2006
1995
                             "      ('k1',) 'foo'\n"
2008
1997
                             "    'k22' LeafNode\n"
2009
1998
                             "      ('k22',) 'bar'\n"
2010
1999
                             "    'k23' LeafNode\n"
2011
 
                             "      ('k23',) 'quux'\n", chkmap._dump_tree())
 
2000
                             "      ('k23',) 'quux'\n"
 
2001
                             , chkmap._dump_tree())
2012
2002
 
2013
2003
    def test__search_prefix_filter_with_hash(self):
2014
 
        search_key_func = chk_map.search_key_registry.get(b'hash-16-way')
 
2004
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
2015
2005
        node = InternalNode(search_key_func=search_key_func)
2016
2006
        node._key_width = 2
2017
2007
        node._node_width = 4
2018
 
        self.assertEqual(b'E8B7BE43\x0071BEEFF9', search_key_func(
2019
 
            StaticTuple(b'a', b'b')))
2020
 
        self.assertEqual(b'E8B7', node._search_prefix_filter(
2021
 
            StaticTuple(b'a', b'b')))
2022
 
        self.assertEqual(b'E8B7', node._search_prefix_filter(
2023
 
            StaticTuple(b'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',)))
2024
2014
 
2025
2015
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
2026
2016
        chkmap = self._get_map(
2027
 
            {(b'k1',): b'foo', (b'k22',): b'bar', (b'k23',): b'quux'}, maximum_size=10)
 
2017
            {('k1',):'foo', ('k22',):'bar', ('k23',): 'quux'}, maximum_size=10)
2028
2018
        # Check we have the expected tree.
2029
2019
        self.assertEqualDiff("'' InternalNode\n"
2030
2020
                             "  'k1' LeafNode\n"
2033
2023
                             "    'k22' LeafNode\n"
2034
2024
                             "      ('k22',) 'bar'\n"
2035
2025
                             "    'k23' LeafNode\n"
2036
 
                             "      ('k23',) 'quux'\n", chkmap._dump_tree())
 
2026
                             "      ('k23',) 'quux'\n"
 
2027
                             , chkmap._dump_tree())
2037
2028
        chkmap = CHKMap(chkmap._store, chkmap._root_node)
2038
2029
        chkmap._ensure_root()
2039
2030
        node = chkmap._root_node
2040
2031
        # unmapping k23 should give us a root, with k1 and k22 as direct
2041
2032
        # children.
2042
 
        result = node.unmap(chkmap._store, (b'k23',))
 
2033
        result = node.unmap(chkmap._store, ('k23',))
2043
2034
        # check the pointed-at object within node - k2 should now point at the
2044
2035
        # k22 leaf (which has been paged in to see if we can collapse the tree)
2045
 
        child = node._items[b'k2']
 
2036
        child = node._items['k2']
2046
2037
        self.assertIsInstance(child, LeafNode)
2047
2038
        self.assertEqual(1, len(child))
2048
 
        self.assertEqual({(b'k22',): b'bar'},
2049
 
                         self.to_dict(child, None))
 
2039
        self.assertEqual({('k22',): 'bar'},
 
2040
            self.to_dict(child, None))
2050
2041
        # Check overall structure is instact:
2051
2042
        self.assertEqual(2, len(chkmap))
2052
 
        self.assertEqual({(b'k1',): b'foo', (b'k22',): b'bar'},
2053
 
                         self.to_dict(chkmap))
 
2043
        self.assertEqual({('k1',): 'foo', ('k22',): 'bar'},
 
2044
            self.to_dict(chkmap))
2054
2045
        # serialising should only serialise the new data - the root node.
2055
2046
        keys = list(node.serialise(chkmap._store))
2056
2047
        self.assertEqual([keys[-1]], keys)
2059
2050
                             "  'k1' LeafNode\n"
2060
2051
                             "      ('k1',) 'foo'\n"
2061
2052
                             "  'k2' LeafNode\n"
2062
 
                             "      ('k22',) 'bar'\n", chkmap._dump_tree())
 
2053
                             "      ('k22',) 'bar'\n"
 
2054
                             , chkmap._dump_tree())
2063
2055
 
2064
2056
    def test_unmap_k1_from_k1_k22_k23_gives_k22_k23_tree_new(self):
2065
2057
        chkmap = self._get_map(
2066
 
            {(b'k1',): b'foo', (b'k22',): b'bar', (b'k23',): b'quux'}, maximum_size=10)
 
2058
            {('k1',):'foo', ('k22',):'bar', ('k23',): 'quux'}, maximum_size=10)
2067
2059
        self.assertEqualDiff("'' InternalNode\n"
2068
2060
                             "  'k1' LeafNode\n"
2069
2061
                             "      ('k1',) 'foo'\n"
2071
2063
                             "    'k22' LeafNode\n"
2072
2064
                             "      ('k22',) 'bar'\n"
2073
2065
                             "    'k23' LeafNode\n"
2074
 
                             "      ('k23',) 'quux'\n", chkmap._dump_tree())
 
2066
                             "      ('k23',) 'quux'\n"
 
2067
                             , chkmap._dump_tree())
2075
2068
        orig_root = chkmap._root_node
2076
2069
        chkmap = CHKMap(chkmap._store, orig_root)
2077
2070
        chkmap._ensure_root()
2078
2071
        node = chkmap._root_node
2079
 
        k2_ptr = node._items[b'k2']
 
2072
        k2_ptr = node._items['k2']
2080
2073
        # unmapping k1 should give us a root, with k22 and k23 as direct
2081
2074
        # children, and should not have needed to page in the subtree.
2082
 
        result = node.unmap(chkmap._store, (b'k1',))
 
2075
        result = node.unmap(chkmap._store, ('k1',))
2083
2076
        self.assertEqual(k2_ptr, result)
2084
2077
        chkmap = CHKMap(chkmap._store, orig_root)
2085
2078
        # Unmapping at the CHKMap level should switch to the new root
2086
 
        chkmap.unmap((b'k1',))
 
2079
        chkmap.unmap(('k1',))
2087
2080
        self.assertEqual(k2_ptr, chkmap._root_node)
2088
2081
        self.assertEqualDiff("'' InternalNode\n"
2089
2082
                             "  'k22' LeafNode\n"
2090
2083
                             "      ('k22',) 'bar'\n"
2091
2084
                             "  'k23' LeafNode\n"
2092
 
                             "      ('k23',) 'quux'\n", chkmap._dump_tree())
 
2085
                             "      ('k23',) 'quux'\n"
 
2086
                             , chkmap._dump_tree())
2093
2087
 
2094
2088
 
2095
2089
# leaf:
2141
2135
        if search_key_func is None:
2142
2136
            search_key_func = chk_map._search_key_plain
2143
2137
        return chk_map.CHKMapDifference(self.get_chk_bytes(),
2144
 
                                        new_roots, old_roots, search_key_func)
 
2138
            new_roots, old_roots, search_key_func)
2145
2139
 
2146
2140
    def test__init__(self):
2147
2141
        c_map = self.make_root_only_map()
2148
2142
        key1 = c_map.key()
2149
 
        c_map.map((b'aaa',), b'new aaa content')
 
2143
        c_map.map(('aaa',), 'new aaa content')
2150
2144
        key2 = c_map._save()
2151
2145
        diff = self.get_difference([key2], [key1])
2152
2146
        self.assertEqual({key1}, diff._all_old_chks)
2156
2150
    def help__read_all_roots(self, search_key_func):
2157
2151
        c_map = self.make_root_only_map(search_key_func=search_key_func)
2158
2152
        key1 = c_map.key()
2159
 
        c_map.map((b'aaa',), b'new aaa content')
 
2153
        c_map.map(('aaa',), 'new aaa content')
2160
2154
        key2 = c_map._save()
2161
2155
        diff = self.get_difference([key2], [key1], search_key_func)
2162
2156
        root_results = [record.key for record in diff._read_all_roots()]
2163
2157
        self.assertEqual([key2], root_results)
2164
2158
        # We should have queued up only items that aren't in the old
2165
2159
        # set
2166
 
        self.assertEqual([((b'aaa',), b'new aaa content')],
 
2160
        self.assertEqual([(('aaa',), 'new aaa content')],
2167
2161
                         diff._new_item_queue)
2168
2162
        self.assertEqual([], diff._new_queue)
2169
2163
        # And there are no old references, so that queue should be
2190
2184
    def test__read_all_roots_prepares_queues(self):
2191
2185
        c_map = self.make_one_deep_map(chk_map._search_key_plain)
2192
2186
        key1 = c_map.key()
2193
 
        c_map._dump_tree()  # load everything
2194
 
        key1_a = c_map._root_node._items[b'a'].key()
2195
 
        c_map.map((b'abb',), b'new abb content')
 
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')
2196
2190
        key2 = c_map._save()
2197
 
        key2_a = c_map._root_node._items[b'a'].key()
 
2191
        key2_a = c_map._root_node._items['a'].key()
2198
2192
        diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2199
2193
        root_results = [record.key for record in diff._read_all_roots()]
2200
2194
        self.assertEqual([key2], root_results)
2207
2201
    def test__read_all_roots_multi_new_prepares_queues(self):
2208
2202
        c_map = self.make_one_deep_map(chk_map._search_key_plain)
2209
2203
        key1 = c_map.key()
2210
 
        c_map._dump_tree()  # load everything
2211
 
        key1_a = c_map._root_node._items[b'a'].key()
2212
 
        key1_c = c_map._root_node._items[b'c'].key()
2213
 
        c_map.map((b'abb',), b'new abb content')
 
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')
2214
2208
        key2 = c_map._save()
2215
 
        key2_a = c_map._root_node._items[b'a'].key()
2216
 
        key2_c = c_map._root_node._items[b'c'].key()
 
2209
        key2_a = c_map._root_node._items['a'].key()
 
2210
        key2_c = c_map._root_node._items['c'].key()
2217
2211
        c_map = chk_map.CHKMap(self.get_chk_bytes(), key1,
2218
2212
                               chk_map._search_key_plain)
2219
 
        c_map.map((b'ccc',), b'new ccc content')
 
2213
        c_map.map(('ccc',), 'new ccc content')
2220
2214
        key3 = c_map._save()
2221
 
        key3_a = c_map._root_node._items[b'a'].key()
2222
 
        key3_c = c_map._root_node._items[b'c'].key()
 
2215
        key3_a = c_map._root_node._items['a'].key()
 
2216
        key3_c = c_map._root_node._items['c'].key()
2223
2217
        diff = self.get_difference([key2, key3], [key1],
2224
2218
                                   chk_map._search_key_plain)
2225
2219
        root_results = [record.key for record in diff._read_all_roots()]
2226
2220
        self.assertEqual(sorted([key2, key3]), sorted(root_results))
2227
2221
        # We should have queued up key2_a, and key3_c, but not key2_c or key3_c
2228
 
        self.assertEqual({key2_a, key3_c}, set(diff._new_queue))
 
2222
        self.assertEqual([key2_a, key3_c], diff._new_queue)
2229
2223
        self.assertEqual([], diff._new_item_queue)
2230
2224
        # And we should have queued up both a and c for the old set
2231
 
        self.assertEqual({key1_a, key1_c}, set(diff._old_queue))
 
2225
        self.assertEqual([key1_a, key1_c], diff._old_queue)
2232
2226
 
2233
2227
    def test__read_all_roots_different_depths(self):
2234
2228
        c_map = self.make_two_deep_map(chk_map._search_key_plain)
2235
 
        c_map._dump_tree()  # load everything
 
2229
        c_map._dump_tree() # load everything
2236
2230
        key1 = c_map.key()
2237
 
        key1_a = c_map._root_node._items[b'a'].key()
2238
 
        key1_c = c_map._root_node._items[b'c'].key()
2239
 
        key1_d = c_map._root_node._items[b'd'].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()
2240
2234
 
2241
2235
        c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2242
2236
        c_map2._dump_tree()
2243
2237
        key2 = c_map2.key()
2244
 
        key2_aa = c_map2._root_node._items[b'aa'].key()
2245
 
        key2_ad = c_map2._root_node._items[b'ad'].key()
 
2238
        key2_aa = c_map2._root_node._items['aa'].key()
 
2239
        key2_ad = c_map2._root_node._items['ad'].key()
2246
2240
 
2247
2241
        diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2248
2242
        root_results = [record.key for record in diff._read_all_roots()]
2250
2244
        # Only the 'a' subset should be queued up, since 'c' and 'd' cannot be
2251
2245
        # present
2252
2246
        self.assertEqual([key1_a], diff._old_queue)
2253
 
        self.assertEqual({key2_aa, key2_ad}, set(diff._new_queue))
 
2247
        self.assertEqual([key2_aa, key2_ad], diff._new_queue)
2254
2248
        self.assertEqual([], diff._new_item_queue)
2255
2249
 
2256
2250
        diff = self.get_difference([key1], [key2], chk_map._search_key_plain)
2257
2251
        root_results = [record.key for record in diff._read_all_roots()]
2258
2252
        self.assertEqual([key1], root_results)
2259
2253
 
2260
 
        self.assertEqual({key2_aa, key2_ad}, set(diff._old_queue))
2261
 
        self.assertEqual({key1_a, key1_c, key1_d}, set(diff._new_queue))
 
2254
        self.assertEqual([key2_aa, key2_ad], diff._old_queue)
 
2255
        self.assertEqual([key1_a, key1_c, key1_d], diff._new_queue)
2262
2256
        self.assertEqual([], diff._new_item_queue)
2263
2257
 
2264
2258
    def test__read_all_roots_different_depths_16(self):
2265
2259
        c_map = self.make_two_deep_map(chk_map._search_key_16)
2266
 
        c_map._dump_tree()  # load everything
 
2260
        c_map._dump_tree() # load everything
2267
2261
        key1 = c_map.key()
2268
 
        key1_2 = c_map._root_node._items[b'2'].key()
2269
 
        key1_4 = c_map._root_node._items[b'4'].key()
2270
 
        key1_C = c_map._root_node._items[b'C'].key()
2271
 
        key1_F = c_map._root_node._items[b'F'].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()
2272
2266
 
2273
2267
        c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_16)
2274
2268
        c_map2._dump_tree()
2275
2269
        key2 = c_map2.key()
2276
 
        key2_F0 = c_map2._root_node._items[b'F0'].key()
2277
 
        key2_F3 = c_map2._root_node._items[b'F3'].key()
2278
 
        key2_F4 = c_map2._root_node._items[b'F4'].key()
2279
 
        key2_FD = c_map2._root_node._items[b'FD'].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()
2280
2274
 
2281
2275
        diff = self.get_difference([key2], [key1], chk_map._search_key_16)
2282
2276
        root_results = [record.key for record in diff._read_all_roots()]
2299
2293
 
2300
2294
    def test__read_all_roots_mixed_depth(self):
2301
2295
        c_map = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
2302
 
        c_map._dump_tree()  # load everything
 
2296
        c_map._dump_tree() # load everything
2303
2297
        key1 = c_map.key()
2304
 
        key1_aa = c_map._root_node._items[b'aa'].key()
2305
 
        key1_ad = c_map._root_node._items[b'ad'].key()
 
2298
        key1_aa = c_map._root_node._items['aa'].key()
 
2299
        key1_ad = c_map._root_node._items['ad'].key()
2306
2300
 
2307
2301
        c_map2 = self.make_one_deep_one_prefix_map(chk_map._search_key_plain)
2308
2302
        c_map2._dump_tree()
2309
2303
        key2 = c_map2.key()
2310
 
        key2_a = c_map2._root_node._items[b'a'].key()
2311
 
        key2_b = c_map2._root_node._items[b'b'].key()
 
2304
        key2_a = c_map2._root_node._items['a'].key()
 
2305
        key2_b = c_map2._root_node._items['b'].key()
2312
2306
 
2313
2307
        diff = self.get_difference([key2], [key1], chk_map._search_key_plain)
2314
2308
        root_results = [record.key for record in diff._read_all_roots()]
2343
2337
        # This allows us to yield a root node record immediately, without any
2344
2338
        # buffering.
2345
2339
        c_map = self.make_two_deep_map(chk_map._search_key_plain)
2346
 
        c_map._dump_tree()  # load all keys
 
2340
        c_map._dump_tree() # load all keys
2347
2341
        key1 = c_map.key()
2348
 
        key1_a = c_map._root_node._items[b'a'].key()
 
2342
        key1_a = c_map._root_node._items['a'].key()
2349
2343
        c_map2 = self.get_map({
2350
 
            (b'acc',): b'initial acc content',
2351
 
            (b'ace',): b'initial ace content',
 
2344
            ('acc',): 'initial acc content',
 
2345
            ('ace',): 'initial ace content',
2352
2346
        }, maximum_size=100)
2353
2347
        self.assertEqualDiff(
2354
2348
            "'' LeafNode\n"
2363
2357
        # we should have enqued all of the chk pages to be walked, so that we
2364
2358
        # can find the keys if they are present
2365
2359
        self.assertEqual([key1_a], diff._old_queue)
2366
 
        self.assertEqual({((b'acc',), b'initial acc content'),
2367
 
                          ((b'ace',), b'initial ace content'),
2368
 
                          }, set(diff._new_item_queue))
 
2360
        self.assertEqual([(('acc',), 'initial acc content'),
 
2361
                          (('ace',), 'initial ace content'),
 
2362
                         ], diff._new_item_queue)
2369
2363
 
2370
2364
    def test__read_all_roots_multiple_targets(self):
2371
2365
        c_map = self.make_root_only_map()
2373
2367
        c_map = self.make_one_deep_map()
2374
2368
        key2 = c_map.key()
2375
2369
        c_map._dump_tree()
2376
 
        key2_c = c_map._root_node._items[b'c'].key()
2377
 
        key2_d = c_map._root_node._items[b'd'].key()
2378
 
        c_map.map((b'ccc',), b'new ccc value')
 
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')
2379
2373
        key3 = c_map._save()
2380
 
        key3_c = c_map._root_node._items[b'c'].key()
 
2374
        key3_c = c_map._root_node._items['c'].key()
2381
2375
        diff = self.get_difference([key2, key3], [key1],
2382
2376
                                   chk_map._search_key_plain)
2383
2377
        root_results = [record.key for record in diff._read_all_roots()]
2435
2429
    def test__read_all_roots_multiple_old(self):
2436
2430
        c_map = self.make_two_deep_map()
2437
2431
        key1 = c_map.key()
2438
 
        c_map._dump_tree()  # load everything
2439
 
        key1_a = c_map._root_node._items[b'a'].key()
2440
 
        c_map.map((b'ccc',), b'new ccc value')
 
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')
2441
2435
        key2 = c_map._save()
2442
 
        key2_a = c_map._root_node._items[b'a'].key()
2443
 
        c_map.map((b'add',), b'new add value')
 
2436
        key2_a = c_map._root_node._items['a'].key()
 
2437
        c_map.map(('add',), 'new add value')
2444
2438
        key3 = c_map._save()
2445
 
        key3_a = c_map._root_node._items[b'a'].key()
 
2439
        key3_a = c_map._root_node._items['a'].key()
2446
2440
        diff = self.get_difference([key3], [key1, key2],
2447
2441
                                   chk_map._search_key_plain)
2448
2442
        root_results = [record.key for record in diff._read_all_roots()]
2456
2450
    def test__process_next_old_batched_no_dupes(self):
2457
2451
        c_map = self.make_two_deep_map()
2458
2452
        key1 = c_map.key()
2459
 
        c_map._dump_tree()  # load everything
2460
 
        key1_a = c_map._root_node._items[b'a'].key()
2461
 
        key1_aa = c_map._root_node._items[b'a']._items[b'aa'].key()
2462
 
        key1_ab = c_map._root_node._items[b'a']._items[b'ab'].key()
2463
 
        key1_ac = c_map._root_node._items[b'a']._items[b'ac'].key()
2464
 
        key1_ad = c_map._root_node._items[b'a']._items[b'ad'].key()
2465
 
        c_map.map((b'aaa',), b'new aaa value')
 
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')
2466
2460
        key2 = c_map._save()
2467
 
        key2_a = c_map._root_node._items[b'a'].key()
2468
 
        key2_aa = c_map._root_node._items[b'a']._items[b'aa'].key()
2469
 
        c_map.map((b'acc',), b'new acc content')
 
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')
2470
2464
        key3 = c_map._save()
2471
 
        key3_a = c_map._root_node._items[b'a'].key()
2472
 
        key3_ac = c_map._root_node._items[b'a']._items[b'ac'].key()
 
2465
        key3_a = c_map._root_node._items['a'].key()
 
2466
        key3_ac = c_map._root_node._items['a']._items['ac'].key()
2473
2467
        diff = self.get_difference([key3], [key1, key2],
2474
2468
                                   chk_map._search_key_plain)
2475
2469
        root_results = [record.key for record in diff._read_all_roots()]
2516
2510
        self.assertEqual(sorted(items), sorted(all_items))
2517
2511
 
2518
2512
    def test_empty_to_one_keys(self):
2519
 
        target = self.get_map_key({(b'a',): b'content'})
 
2513
        target = self.get_map_key({('a',): 'content'})
2520
2514
        self.assertIterInteresting([target],
2521
 
                                   [((b'a',), b'content')],
 
2515
                                   [(('a',), 'content')],
2522
2516
                                   [target], [])
2523
2517
 
2524
2518
    def test_none_to_one_key(self):
2525
2519
        basis = self.get_map_key({})
2526
 
        target = self.get_map_key({(b'a',): b'content'})
 
2520
        target = self.get_map_key({('a',): 'content'})
2527
2521
        self.assertIterInteresting([target],
2528
 
                                   [((b'a',), b'content')],
 
2522
                                   [(('a',), 'content')],
2529
2523
                                   [target], [basis])
2530
2524
 
2531
2525
    def test_one_to_none_key(self):
2532
 
        basis = self.get_map_key({(b'a',): b'content'})
 
2526
        basis = self.get_map_key({('a',): 'content'})
2533
2527
        target = self.get_map_key({})
2534
2528
        self.assertIterInteresting([target],
2535
2529
                                   [],
2536
2530
                                   [target], [basis])
2537
2531
 
2538
2532
    def test_common_pages(self):
2539
 
        basis = self.get_map_key({(b'a',): b'content',
2540
 
                                  (b'b',): b'content',
2541
 
                                  (b'c',): b'content',
 
2533
        basis = self.get_map_key({('a',): 'content',
 
2534
                                  ('b',): 'content',
 
2535
                                  ('c',): 'content',
 
2536
                                 })
 
2537
        target = self.get_map_key({('a',): 'content',
 
2538
                                   ('b',): 'other content',
 
2539
                                   ('c',): 'content',
2542
2540
                                  })
2543
 
        target = self.get_map_key({(b'a',): b'content',
2544
 
                                   (b'b',): b'other content',
2545
 
                                   (b'c',): b'content',
2546
 
                                   })
2547
2541
        target_map = CHKMap(self.get_chk_bytes(), target)
2548
2542
        self.assertEqualDiff(
2549
2543
            "'' InternalNode\n"
2554
2548
            "  'c' LeafNode\n"
2555
2549
            "      ('c',) 'content'\n",
2556
2550
            target_map._dump_tree())
2557
 
        b_key = target_map._root_node._items[b'b'].key()
 
2551
        b_key = target_map._root_node._items['b'].key()
2558
2552
        # This should return the root node, and the node for the 'b' key
2559
2553
        self.assertIterInteresting([target, b_key],
2560
 
                                   [((b'b',), b'other content')],
 
2554
                                   [(('b',), 'other content')],
2561
2555
                                   [target], [basis])
2562
2556
 
2563
2557
    def test_common_sub_page(self):
2564
 
        basis = self.get_map_key({(b'aaa',): b'common',
2565
 
                                  (b'c',): b'common',
 
2558
        basis = self.get_map_key({('aaa',): 'common',
 
2559
                                  ('c',): 'common',
 
2560
                                 })
 
2561
        target = self.get_map_key({('aaa',): 'common',
 
2562
                                   ('aab',): 'new',
 
2563
                                   ('c',): 'common',
2566
2564
                                  })
2567
 
        target = self.get_map_key({(b'aaa',): b'common',
2568
 
                                   (b'aab',): b'new',
2569
 
                                   (b'c',): b'common',
2570
 
                                   })
2571
2565
        target_map = CHKMap(self.get_chk_bytes(), target)
2572
2566
        self.assertEqualDiff(
2573
2567
            "'' InternalNode\n"
2580
2574
            "      ('c',) 'common'\n",
2581
2575
            target_map._dump_tree())
2582
2576
        # The key for the internal aa node
2583
 
        a_key = target_map._root_node._items[b'a'].key()
 
2577
        a_key = target_map._root_node._items['a'].key()
2584
2578
        # The key for the leaf aab node
2585
2579
        # aaa_key = target_map._root_node._items['a']._items['aaa'].key()
2586
 
        aab_key = target_map._root_node._items[b'a']._items[b'aab'].key()
 
2580
        aab_key = target_map._root_node._items['a']._items['aab'].key()
2587
2581
        self.assertIterInteresting([target, a_key, aab_key],
2588
 
                                   [((b'aab',), b'new')],
 
2582
                                   [(('aab',), 'new')],
2589
2583
                                   [target], [basis])
2590
2584
 
2591
2585
    def test_common_leaf(self):
2592
2586
        basis = self.get_map_key({})
2593
 
        target1 = self.get_map_key({(b'aaa',): b'common'})
2594
 
        target2 = self.get_map_key({(b'aaa',): b'common',
2595
 
                                    (b'bbb',): b'new',
2596
 
                                    })
2597
 
        target3 = self.get_map_key({(b'aaa',): b'common',
2598
 
                                    (b'aac',): b'other',
2599
 
                                    (b'bbb',): b'new',
2600
 
                                    })
 
2587
        target1 = self.get_map_key({('aaa',): 'common'})
 
2588
        target2 = self.get_map_key({('aaa',): 'common',
 
2589
                                    ('bbb',): 'new',
 
2590
                                   })
 
2591
        target3 = self.get_map_key({('aaa',): 'common',
 
2592
                                    ('aac',): 'other',
 
2593
                                    ('bbb',): 'new',
 
2594
                                   })
2601
2595
        # The LeafNode containing 'aaa': 'common' occurs at 3 different levels.
2602
2596
        # Once as a root node, once as a second layer, and once as a third
2603
2597
        # layer. It should only be returned one time regardless
2626
2620
            "      ('bbb',) 'new'\n",
2627
2621
            target3_map._dump_tree())
2628
2622
        aaa_key = target1_map._root_node.key()
2629
 
        b_key = target2_map._root_node._items[b'b'].key()
2630
 
        a_key = target3_map._root_node._items[b'a'].key()
2631
 
        aac_key = target3_map._root_node._items[b'a']._items[b'aac'].key()
 
2623
        b_key = target2_map._root_node._items['b'].key()
 
2624
        a_key = target3_map._root_node._items['a'].key()
 
2625
        aac_key = target3_map._root_node._items['a']._items['aac'].key()
2632
2626
        self.assertIterInteresting(
2633
2627
            [target1, target2, target3, a_key, aac_key, b_key],
2634
 
            [((b'aaa',), b'common'), ((b'bbb',), b'new'), ((b'aac',), b'other')],
 
2628
            [(('aaa',), 'common'), (('bbb',), 'new'), (('aac',), 'other')],
2635
2629
            [target1, target2, target3], [basis])
2636
2630
 
2637
2631
        self.assertIterInteresting(
2638
2632
            [target2, target3, a_key, aac_key, b_key],
2639
 
            [((b'bbb',), b'new'), ((b'aac',), b'other')],
 
2633
            [(('bbb',), 'new'), (('aac',), 'other')],
2640
2634
            [target2, target3], [target1])
2641
2635
 
2642
2636
        # Technically, target1 could be filtered out, but since it is a root
2648
2642
            [target1], [target3])
2649
2643
 
2650
2644
    def test_multiple_maps(self):
2651
 
        basis1 = self.get_map_key({(b'aaa',): b'common',
2652
 
                                   (b'aab',): b'basis1',
2653
 
                                   })
2654
 
        basis2 = self.get_map_key({(b'bbb',): b'common',
2655
 
                                   (b'bbc',): b'basis2',
2656
 
                                   })
2657
 
        target1 = self.get_map_key({(b'aaa',): b'common',
2658
 
                                    (b'aac',): b'target1',
2659
 
                                    (b'bbb',): b'common',
2660
 
                                    })
2661
 
        target2 = self.get_map_key({(b'aaa',): b'common',
2662
 
                                    (b'bba',): b'target2',
2663
 
                                    (b'bbb',): b'common',
2664
 
                                    })
 
2645
        basis1 = self.get_map_key({('aaa',): 'common',
 
2646
                                   ('aab',): 'basis1',
 
2647
                                  })
 
2648
        basis2 = self.get_map_key({('bbb',): 'common',
 
2649
                                   ('bbc',): 'basis2',
 
2650
                                  })
 
2651
        target1 = self.get_map_key({('aaa',): 'common',
 
2652
                                    ('aac',): 'target1',
 
2653
                                    ('bbb',): 'common',
 
2654
                                   })
 
2655
        target2 = self.get_map_key({('aaa',): 'common',
 
2656
                                    ('bba',): 'target2',
 
2657
                                    ('bbb',): 'common',
 
2658
                                   })
2665
2659
        target1_map = CHKMap(self.get_chk_bytes(), target1)
2666
2660
        self.assertEqualDiff(
2667
2661
            "'' InternalNode\n"
2674
2668
            "      ('bbb',) 'common'\n",
2675
2669
            target1_map._dump_tree())
2676
2670
        # The key for the target1 internal a node
2677
 
        a_key = target1_map._root_node._items[b'a'].key()
 
2671
        a_key = target1_map._root_node._items['a'].key()
2678
2672
        # The key for the leaf aac node
2679
 
        aac_key = target1_map._root_node._items[b'a']._items[b'aac'].key()
 
2673
        aac_key = target1_map._root_node._items['a']._items['aac'].key()
2680
2674
 
2681
2675
        target2_map = CHKMap(self.get_chk_bytes(), target2)
2682
2676
        self.assertEqualDiff(
2690
2684
            "      ('bbb',) 'common'\n",
2691
2685
            target2_map._dump_tree())
2692
2686
        # The key for the target2 internal bb node
2693
 
        b_key = target2_map._root_node._items[b'b'].key()
 
2687
        b_key = target2_map._root_node._items['b'].key()
2694
2688
        # The key for the leaf bba node
2695
 
        bba_key = target2_map._root_node._items[b'b']._items[b'bba'].key()
 
2689
        bba_key = target2_map._root_node._items['b']._items['bba'].key()
2696
2690
        self.assertIterInteresting(
2697
2691
            [target1, target2, a_key, aac_key, b_key, bba_key],
2698
 
            [((b'aac',), b'target1'), ((b'bba',), b'target2')],
 
2692
            [(('aac',), 'target1'), (('bba',), 'target2')],
2699
2693
            [target1, target2], [basis1, basis2])
2700
2694
 
2701
2695
    def test_multiple_maps_overlapping_common_new(self):
2714
2708
        #    that InternalNode
2715
2709
        basis = self.get_map_key({
2716
2710
            # InternalNode, unchanged in left:
2717
 
            (b'aaa',): b'left',
2718
 
            (b'abb',): b'right',
 
2711
            ('aaa',): 'left',
 
2712
            ('abb',): 'right',
2719
2713
            # Forces an internalNode at 'a'
2720
 
            (b'ccc',): b'common',
 
2714
            ('ccc',): 'common',
2721
2715
            })
2722
2716
        left = self.get_map_key({
2723
2717
            # All of basis unchanged
2724
 
            (b'aaa',): b'left',
2725
 
            (b'abb',): b'right',
2726
 
            (b'ccc',): b'common',
 
2718
            ('aaa',): 'left',
 
2719
            ('abb',): 'right',
 
2720
            ('ccc',): 'common',
2727
2721
            # And a new top level node so the root key is different
2728
 
            (b'ddd',): b'change',
 
2722
            ('ddd',): 'change',
2729
2723
            })
2730
2724
        right = self.get_map_key({
2731
2725
            # A value that is unchanged from basis and thus should be filtered
2732
2726
            # out.
2733
 
            (b'abb',): b'right'
 
2727
            ('abb',): 'right'
2734
2728
            })
2735
2729
        basis_map = CHKMap(self.get_chk_bytes(), basis)
2736
2730
        self.assertEqualDiff(
2758
2752
            "      ('ddd',) 'change'\n",
2759
2753
            left_map._dump_tree())
2760
2754
        # Keys from left side target
2761
 
        l_d_key = left_map._root_node._items[b'd'].key()
 
2755
        l_d_key = left_map._root_node._items['d'].key()
2762
2756
        # Get right expected data
2763
2757
        right_map = CHKMap(self.get_chk_bytes(), right)
2764
2758
        self.assertEqualDiff(
2769
2763
        # Test behaviour
2770
2764
        self.assertIterInteresting(
2771
2765
            [right, left, l_d_key],
2772
 
            [((b'ddd',), b'change')],
 
2766
            [(('ddd',), 'change')],
2773
2767
            [left, right], [basis])
2774
2768
 
2775
2769
    def test_multiple_maps_similar(self):
2776
2770
        # We want to have a depth=2 tree, with multiple entries in each leaf
2777
2771
        # node
2778
2772
        basis = self.get_map_key({
2779
 
            (b'aaa',): b'unchanged',
2780
 
            (b'abb',): b'will change left',
2781
 
            (b'caa',): b'unchanged',
2782
 
            (b'cbb',): b'will change right',
 
2773
            ('aaa',): 'unchanged',
 
2774
            ('abb',): 'will change left',
 
2775
            ('caa',): 'unchanged',
 
2776
            ('cbb',): 'will change right',
2783
2777
            }, maximum_size=60)
2784
2778
        left = self.get_map_key({
2785
 
            (b'aaa',): b'unchanged',
2786
 
            (b'abb',): b'changed left',
2787
 
            (b'caa',): b'unchanged',
2788
 
            (b'cbb',): b'will change right',
 
2779
            ('aaa',): 'unchanged',
 
2780
            ('abb',): 'changed left',
 
2781
            ('caa',): 'unchanged',
 
2782
            ('cbb',): 'will change right',
2789
2783
            }, maximum_size=60)
2790
2784
        right = self.get_map_key({
2791
 
            (b'aaa',): b'unchanged',
2792
 
            (b'abb',): b'will change left',
2793
 
            (b'caa',): b'unchanged',
2794
 
            (b'cbb',): b'changed right',
 
2785
            ('aaa',): 'unchanged',
 
2786
            ('abb',): 'will change left',
 
2787
            ('caa',): 'unchanged',
 
2788
            ('cbb',): 'changed right',
2795
2789
            }, maximum_size=60)
2796
2790
        basis_map = CHKMap(self.get_chk_bytes(), basis)
2797
2791
        self.assertEqualDiff(
2815
2809
            "      ('cbb',) 'will change right'\n",
2816
2810
            left_map._dump_tree())
2817
2811
        # Keys from left side target
2818
 
        l_a_key = left_map._root_node._items[b'a'].key()
2819
 
        l_c_key = left_map._root_node._items[b'c'].key()
 
2812
        l_a_key = left_map._root_node._items['a'].key()
 
2813
        l_c_key = left_map._root_node._items['c'].key()
2820
2814
        # Get right expected data
2821
2815
        right_map = CHKMap(self.get_chk_bytes(), right)
2822
2816
        self.assertEqualDiff(
2828
2822
            "      ('caa',) 'unchanged'\n"
2829
2823
            "      ('cbb',) 'changed right'\n",
2830
2824
            right_map._dump_tree())
2831
 
        r_a_key = right_map._root_node._items[b'a'].key()
2832
 
        r_c_key = right_map._root_node._items[b'c'].key()
 
2825
        r_a_key = right_map._root_node._items['a'].key()
 
2826
        r_c_key = right_map._root_node._items['c'].key()
2833
2827
        self.assertIterInteresting(
2834
2828
            [right, left, l_a_key, r_c_key],
2835
 
            [((b'abb',), b'changed left'), ((b'cbb',), b'changed right')],
 
2829
            [(('abb',), 'changed left'), (('cbb',), 'changed right')],
2836
2830
            [left, right], [basis])