/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-08-14 01:15:02 UTC
  • mto: This revision was merged to the branch mainline in revision 7078.
  • Revision ID: jelmer@jelmer.uk-20180814011502-5zaydaq02vc2qxo1
Fix tests.

Show diffs side-by-side

added added

removed removed

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