/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to breezy/tests/test_chk_map.py

  • Committer: Jelmer Vernooij
  • Date: 2020-05-06 02:13:25 UTC
  • mfrom: (7490.7.21 work)
  • mto: This revision was merged to the branch mainline in revision 7501.
  • Revision ID: jelmer@jelmer.uk-20200506021325-awbmmqu1zyorz7sj
Merge 3.1 branch.

Show diffs side-by-side

added added

removed removed

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