/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 brzlib/tests/test_chk_map.py

  • Committer: Jelmer Vernooij
  • Date: 2017-05-21 12:41:27 UTC
  • mto: This revision was merged to the branch mainline in revision 6623.
  • Revision ID: jelmer@jelmer.uk-20170521124127-iv8etg0vwymyai6y
s/bzr/brz/ in apport config.

Show diffs side-by-side

added added

removed removed

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