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

  • Committer: Marius Kruger
  • Date: 2010-07-10 21:28:56 UTC
  • mto: (5384.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 5385.
  • Revision ID: marius.kruger@enerweb.co.za-20100710212856-uq4ji3go0u5se7hx
* Update documentation
* add NEWS

Show diffs side-by-side

added added

removed removed

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