/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-04-05 19:11:34 UTC
  • mto: (7490.7.16 work)
  • mto: This revision was merged to the branch mainline in revision 7501.
  • Revision ID: jelmer@jelmer.uk-20200405191134-0aebh8ikiwygxma5
Populate the .gitignore file.

Show diffs side-by-side

added added

removed removed

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