/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: Martin
  • Date: 2018-11-16 16:38:22 UTC
  • mto: This revision was merged to the branch mainline in revision 7172.
  • Revision ID: gzlist@googlemail.com-20181116163822-yg1h1cdng6w7w9kn
Make --profile-imports work on Python 3

Also tweak heading to line up correctly.

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