/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to breezy/tests/test_btree_index.py

  • Committer: Jelmer Vernooij
  • Date: 2018-02-18 21:42:57 UTC
  • mto: This revision was merged to the branch mainline in revision 6859.
  • Revision ID: jelmer@jelmer.uk-20180218214257-jpevutp1wa30tz3v
Update TODO to reference Breezy, not Bazaar.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test_btree_index.py
20
20
import pprint
21
21
import zlib
22
22
 
23
 
from ... import (
 
23
from .. import (
24
24
    errors,
25
25
    fifo_cache,
26
26
    lru_cache,
28
28
    tests,
29
29
    transport,
30
30
    )
31
 
from .. import (
 
31
from ..bzr import (
32
32
    btree_index,
33
33
    index as _mod_index,
34
34
    )
35
 
from ...tests import (
 
35
from ..tests import (
36
36
    TestCaseWithTransport,
37
37
    scenarios,
38
38
    )
39
 
from ...tests import (
 
39
from ..tests import (
40
40
    features,
41
41
    )
42
42
 
48
48
    import breezy.bzr._btree_serializer_py as py_module
49
49
    scenarios = [('python', {'parse_btree': py_module})]
50
50
    if compiled_btreeparser_feature.available():
51
 
        scenarios.append(('C',
52
 
                          {'parse_btree': compiled_btreeparser_feature.module}))
 
51
        scenarios.append(('C', 
 
52
            {'parse_btree': compiled_btreeparser_feature.module}))
53
53
    return scenarios
54
54
 
55
55
 
92
92
                        for ref_pos in range(list_pos + pos % 2):
93
93
                            if pos % 2:
94
94
                                # refer to a nearby key
95
 
                                refs[-1].append(prefix
96
 
                                                + _pos_to_key(pos - 1, b"ref"))
 
95
                                refs[-1].append(prefix + _pos_to_key(pos - 1, b"ref"))
97
96
                            else:
98
97
                                # serial of this ref in the ref list
99
 
                                refs[-1].append(prefix
100
 
                                                + _pos_to_key(ref_pos, b"ref"))
 
98
                                refs[-1].append(prefix + _pos_to_key(ref_pos, b"ref"))
101
99
                        refs[-1] = tuple(refs[-1])
102
100
                    refs = tuple(refs)
103
101
                else:
118
116
        """
119
117
        if not expected - slop < actual < expected + slop:
120
118
            self.fail("Expected around %d bytes compressed but got %d" %
121
 
                      (expected, actual))
 
119
                (expected, actual))
122
120
 
123
121
 
124
122
class TestBTreeBuilder(BTreeTestCase):
168
166
        node_content = content[73:]
169
167
        node_bytes = zlib.decompress(node_content)
170
168
        expected_node = (b"type=leaf\n"
171
 
                         b"0000000000000000000000000000000000000000\x00\x00value:0\n"
172
 
                         b"1111111111111111111111111111111111111111\x00\x00value:1\n"
173
 
                         b"2222222222222222222222222222222222222222\x00\x00value:2\n"
174
 
                         b"3333333333333333333333333333333333333333\x00\x00value:3\n"
175
 
                         b"4444444444444444444444444444444444444444\x00\x00value:4\n")
 
169
            b"0000000000000000000000000000000000000000\x00\x00value:0\n"
 
170
            b"1111111111111111111111111111111111111111\x00\x00value:1\n"
 
171
            b"2222222222222222222222222222222222222222\x00\x00value:2\n"
 
172
            b"3333333333333333333333333333333333333333\x00\x00value:3\n"
 
173
            b"4444444444444444444444444444444444444444\x00\x00value:4\n")
176
174
        self.assertEqual(expected_node, node_bytes)
177
175
 
178
176
    def test_root_leaf_2_2(self):
305
303
        # Seed the metadata, we're using internal calls now.
306
304
        index.key_count()
307
305
        self.assertEqual(3, len(index._row_lengths),
308
 
                         "Not enough rows: %r" % index._row_lengths)
 
306
            "Not enough rows: %r" % index._row_lengths)
309
307
        self.assertEqual(4, len(index._row_offsets))
310
308
        self.assertEqual(sum(index._row_lengths), index._row_offsets[-1])
311
309
        internal_nodes = index._get_internal_nodes([0, 1, 2])
343
341
        root_bytes = zlib.decompress(root)
344
342
        expected_root = (
345
343
            b"type=internal\n"
346
 
            b"offset=0\n" +
347
 
            (b"0" * 40) + b"\x00" + (b"91" * 40) + b"\n" +
348
 
            (b"1" * 40) + b"\x00" + (b"81" * 40) + b"\n"
 
344
            b"offset=0\n"
 
345
            + (b"0" * 40) + b"\x00" + (b"91" * 40) + b"\n"
 
346
            + (b"1" * 40) + b"\x00" + (b"81" * 40) + b"\n"
349
347
            )
350
348
        self.assertEqual(expected_root, root_bytes)
351
349
        # We assume the other leaf nodes have been written correctly - layering
407
405
        # Test that memory and disk are both used for query methods; and that
408
406
        # None is skipped over happily.
409
407
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
410
 
                         list(builder.iter_all_entries()))
 
408
            list(builder.iter_all_entries()))
411
409
        # Two nodes - one memory one disk
412
410
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
413
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
411
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
414
412
        self.assertEqual(13, builder.key_count())
415
413
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
416
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
414
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
417
415
        builder.add_node(*nodes[13])
418
416
        self.assertEqual(3, len(builder._backing_indices))
419
417
        self.assertEqual(2, builder._backing_indices[0].key_count())
481
479
        # Test that memory and disk are both used for query methods; and that
482
480
        # None is skipped over happily.
483
481
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
484
 
                         list(builder.iter_all_entries()))
 
482
            list(builder.iter_all_entries()))
485
483
        # Two nodes - one memory one disk
486
484
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
487
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
485
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
488
486
        self.assertEqual(13, builder.key_count())
489
487
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
490
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
488
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
491
489
        builder.add_node(*nodes[13])
492
490
        builder.add_node(*nodes[14])
493
491
        builder.add_node(*nodes[15])
522
520
    def test_spill_index_stress_2_2(self):
523
521
        # test that references and longer keys don't confuse things.
524
522
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
525
 
                                           spill_at=2)
 
523
            spill_at=2)
526
524
        nodes = self.make_nodes(16, 2, 2)
527
525
        builder.add_node(*nodes[0])
528
526
        # Test the parts of the index that take up memory are doing so
535
533
        self.assertEqual(1, len(builder._backing_indices))
536
534
        self.assertEqual(2, builder._backing_indices[0].key_count())
537
535
        # now back to memory
538
 
        # Build up the nodes by key dict
539
 
        old = dict(builder._get_nodes_by_key())
 
536
        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict
540
537
        builder.add_node(*nodes[2])
541
538
        self.assertEqual(1, len(builder._nodes))
542
539
        self.assertIsNot(None, builder._nodes_by_key)
582
579
        # Test that memory and disk are both used for query methods; and that
583
580
        # None is skipped over happily.
584
581
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
585
 
                         list(builder.iter_all_entries()))
 
582
            list(builder.iter_all_entries()))
586
583
        # Two nodes - one memory one disk
587
584
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
588
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
585
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
589
586
        self.assertEqual(13, builder.key_count())
590
587
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
591
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
588
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
592
589
        builder.add_node(*nodes[13])
593
590
        self.assertEqual(3, len(builder._backing_indices))
594
591
        self.assertEqual(2, builder._backing_indices[0].key_count())
622
619
 
623
620
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
624
621
        builder = btree_index.BTreeBuilder(reference_lists=ref_lists,
625
 
                                           key_elements=key_elements)
 
622
            key_elements=key_elements)
626
623
        for key, value, references in nodes:
627
624
            builder.add_node(key, value, references)
628
625
        stream = builder.finish()
641
638
        content = temp_file.read()
642
639
        del temp_file
643
640
        size = len(content)
644
 
        transport.put_bytes('index', (b' ' * offset) + content)
 
641
        transport.put_bytes('index', (b' '*offset)+content)
645
642
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
646
643
                                           offset=offset)
647
644
 
717
714
        self.assertEqual(70, index.key_count())
718
715
        # The entire index should have been read, as it is one page long.
719
716
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
720
 
                         t._activity)
 
717
            t._activity)
721
718
        self.assertEqualApproxCompressed(1173, size)
722
719
 
723
720
    def test_with_offset_no_size(self):
724
721
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
725
722
                                            offset=1234,
726
723
                                            nodes=self.make_nodes(200, 1, 1))
727
 
        index._size = None  # throw away the size info
 
724
        index._size = None # throw away the size info
728
725
        self.assertEqual(200, index.key_count())
729
726
 
730
727
    def test_with_small_offset(self):
806
803
        del t._activity[:]
807
804
        self.assertEqual([], t._activity)
808
805
        index.validate()
809
 
        rem = size - 8192  # Number of remaining bytes after second block
 
806
        rem = size - 8192 # Number of remaining bytes after second block
810
807
        # The entire index should have been read linearly.
811
808
        self.assertEqual(
812
809
            [('readv', 'index', [(0, 4096)], False, None),
820
817
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
821
818
        t2 = self.get_transport()
822
819
        self.assertTrue(
823
 
            btree_index.BTreeGraphIndex(t1, 'index', None)
824
 
            == btree_index.BTreeGraphIndex(t1, 'index', None))
825
 
        self.assertTrue(
826
 
            btree_index.BTreeGraphIndex(t1, 'index', 20)
827
 
            == btree_index.BTreeGraphIndex(t1, 'index', 20))
828
 
        self.assertFalse(
829
 
            btree_index.BTreeGraphIndex(t1, 'index', 20)
830
 
            == btree_index.BTreeGraphIndex(t2, 'index', 20))
831
 
        self.assertFalse(
832
 
            btree_index.BTreeGraphIndex(t1, 'inde1', 20)
833
 
            == btree_index.BTreeGraphIndex(t1, 'inde2', 20))
834
 
        self.assertFalse(
835
 
            btree_index.BTreeGraphIndex(t1, 'index', 10)
836
 
            == btree_index.BTreeGraphIndex(t1, 'index', 20))
837
 
        self.assertFalse(
838
 
            btree_index.BTreeGraphIndex(t1, 'index', None)
839
 
            != btree_index.BTreeGraphIndex(t1, 'index', None))
840
 
        self.assertFalse(
841
 
            btree_index.BTreeGraphIndex(t1, 'index', 20)
842
 
            != btree_index.BTreeGraphIndex(t1, 'index', 20))
843
 
        self.assertTrue(
844
 
            btree_index.BTreeGraphIndex(t1, 'index', 20)
845
 
            != btree_index.BTreeGraphIndex(t2, 'index', 20))
846
 
        self.assertTrue(
847
 
            btree_index.BTreeGraphIndex(t1, 'inde1', 20)
848
 
            != btree_index.BTreeGraphIndex(t1, 'inde2', 20))
849
 
        self.assertTrue(
850
 
            btree_index.BTreeGraphIndex(t1, 'index', 10)
851
 
            != btree_index.BTreeGraphIndex(t1, 'index', 20))
 
820
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
 
821
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
822
        self.assertTrue(
 
823
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
824
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
825
        self.assertFalse(
 
826
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
827
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
828
        self.assertFalse(
 
829
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
 
830
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
831
        self.assertFalse(
 
832
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
 
833
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
834
        self.assertFalse(
 
835
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
 
836
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
837
        self.assertFalse(
 
838
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
839
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
840
        self.assertTrue(
 
841
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
842
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
843
        self.assertTrue(
 
844
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
 
845
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
846
        self.assertTrue(
 
847
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
 
848
            btree_index.BTreeGraphIndex(t1, 'index', 20))
852
849
 
853
850
    def test_key_too_big(self):
854
851
        # the size that matters here is the _compressed_ size of the key, so we can't
890
887
            self.assertTrue(node[0] is index)
891
888
            bare_nodes.append(node[1:])
892
889
        self.assertEqual(3, len(index._row_lengths),
893
 
                         "Not enough rows: %r" % index._row_lengths)
 
890
            "Not enough rows: %r" % index._row_lengths)
894
891
        # Should be as long as the nodes we supplied
895
892
        self.assertEqual(20000, len(found_nodes))
896
893
        # Should have the same content
909
906
        # The last page is truncated
910
907
        readv_request[-1] = (readv_request[-1][0], size % page_size)
911
908
        expected = [('readv', 'index', [(0, page_size)], False, None),
912
 
                    ('readv', 'index', readv_request, False, None)]
 
909
             ('readv',  'index', readv_request, False, None)]
913
910
        if expected != t._activity:
914
911
            self.assertEqualDiff(pprint.pformat(expected),
915
912
                                 pprint.pformat(t._activity))
940
937
        self.assertEqual(nodes[30], bare_nodes[0])
941
938
        # Should have read the root node, then one leaf page:
942
939
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
943
 
                          ('readv', 'index', [(8192, 4096), ], False, None)],
944
 
                         t._activity)
 
940
             ('readv',  'index', [(8192, 4096), ], False, None)],
 
941
            t._activity)
945
942
 
946
943
    def test_iter_key_prefix_1_element_key_None(self):
947
944
        index = self.make_index()
948
945
        self.assertRaises(_mod_index.BadIndexKey, list,
949
 
                          index.iter_entries_prefix([(None, )]))
 
946
            index.iter_entries_prefix([(None, )]))
950
947
 
951
948
    def test_iter_key_prefix_wrong_length(self):
952
949
        index = self.make_index()
953
950
        self.assertRaises(_mod_index.BadIndexKey, list,
954
 
                          index.iter_entries_prefix([(b'foo', None)]))
 
951
            index.iter_entries_prefix([(b'foo', None)]))
955
952
        index = self.make_index(key_elements=2)
956
953
        self.assertRaises(_mod_index.BadIndexKey, list,
957
 
                          index.iter_entries_prefix([(b'foo', )]))
 
954
            index.iter_entries_prefix([(b'foo', )]))
958
955
        self.assertRaises(_mod_index.BadIndexKey, list,
959
 
                          index.iter_entries_prefix([(b'foo', None, None)]))
 
956
            index.iter_entries_prefix([(b'foo', None, None)]))
960
957
 
961
958
    def test_iter_key_prefix_1_key_element_no_refs(self):
962
959
        index = self.make_index(nodes=[
963
960
            ((b'name', ), b'data', ()),
964
961
            ((b'ref', ), b'refdata', ())])
965
962
        self.assertEqual({(index, (b'name', ), b'data'),
966
 
                          (index, (b'ref', ), b'refdata')},
967
 
                         set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
 
963
            (index, (b'ref', ), b'refdata')},
 
964
            set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
968
965
 
969
966
    def test_iter_key_prefix_1_key_element_refs(self):
970
967
        index = self.make_index(1, nodes=[
971
968
            ((b'name', ), b'data', ([(b'ref', )], )),
972
969
            ((b'ref', ), b'refdata', ([], ))])
973
970
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
974
 
                          (index, (b'ref', ), b'refdata', ((), ))},
975
 
                         set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
 
971
            (index, (b'ref', ), b'refdata', ((), ))},
 
972
            set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
976
973
 
977
974
    def test_iter_key_prefix_2_key_element_no_refs(self):
978
975
        index = self.make_index(key_elements=2, nodes=[
980
977
            ((b'name', b'fin2'), b'beta', ()),
981
978
            ((b'ref', b'erence'), b'refdata', ())])
982
979
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
983
 
                          (index, (b'ref', b'erence'), b'refdata')},
984
 
                         set(index.iter_entries_prefix(
985
 
                             [(b'name', b'fin1'), (b'ref', b'erence')])))
 
980
            (index, (b'ref', b'erence'), b'refdata')},
 
981
            set(index.iter_entries_prefix(
 
982
                [(b'name', b'fin1'), (b'ref', b'erence')])))
986
983
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
987
 
                          (index, (b'name', b'fin2'), b'beta')},
988
 
                         set(index.iter_entries_prefix([(b'name', None)])))
 
984
            (index, (b'name', b'fin2'), b'beta')},
 
985
            set(index.iter_entries_prefix([(b'name', None)])))
989
986
 
990
987
    def test_iter_key_prefix_2_key_element_refs(self):
991
988
        index = self.make_index(1, key_elements=2, nodes=[
1042
1039
            ])
1043
1040
        parent_map = {}
1044
1041
        missing_keys = set()
1045
 
        search_keys = index._find_ancestors(
1046
 
            [key1], 0, parent_map, missing_keys)
 
1042
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1047
1043
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1048
1044
        self.assertEqual(set(), missing_keys)
1049
1045
        self.assertEqual(set(), search_keys)
1118
1114
        rev_keys = []
1119
1115
        for i in range(400):
1120
1116
            rev_id = ('%s-%s-%s' % (email,
1121
 
                                    osutils.compact_date(start_time + i),
1122
 
                                    osutils.rand_chars(16))).encode('ascii')
 
1117
                                   osutils.compact_date(start_time + i),
 
1118
                                   osutils.rand_chars(16))).encode('ascii')
1123
1119
            rev_key = (rev_id,)
1124
1120
            nodes.append((rev_key, b'value', ref_lists))
1125
1121
            # We have a ref 'list' of length 1, with a list of parents, with 1
1140
1136
        # Now, whatever key we select that would fall on the second page,
1141
1137
        # should give us all the parents until the page break
1142
1138
        key_idx = rev_keys.index(min_l2_key)
1143
 
        next_key = rev_keys[key_idx + 1]
 
1139
        next_key = rev_keys[key_idx+1]
1144
1140
        # So now when we get the parent map, we should get the key we are
1145
1141
        # looking for, min_l2_key, and then a reference to go look for the
1146
1142
        # parent of that key
1216
1212
 
1217
1213
    def test_LeafNode_1_0(self):
1218
1214
        node_bytes = (b"type=leaf\n"
1219
 
                      b"0000000000000000000000000000000000000000\x00\x00value:0\n"
1220
 
                      b"1111111111111111111111111111111111111111\x00\x00value:1\n"
1221
 
                      b"2222222222222222222222222222222222222222\x00\x00value:2\n"
1222
 
                      b"3333333333333333333333333333333333333333\x00\x00value:3\n"
1223
 
                      b"4444444444444444444444444444444444444444\x00\x00value:4\n")
 
1215
            b"0000000000000000000000000000000000000000\x00\x00value:0\n"
 
1216
            b"1111111111111111111111111111111111111111\x00\x00value:1\n"
 
1217
            b"2222222222222222222222222222222222222222\x00\x00value:2\n"
 
1218
            b"3333333333333333333333333333333333333333\x00\x00value:3\n"
 
1219
            b"4444444444444444444444444444444444444444\x00\x00value:4\n")
1224
1220
        node = btree_index._LeafNode(node_bytes, 1, 0)
1225
1221
        # We do direct access, or don't care about order, to leaf nodes most of
1226
1222
        # the time, so a dict is useful:
1234
1230
 
1235
1231
    def test_LeafNode_2_2(self):
1236
1232
        node_bytes = (b"type=leaf\n"
1237
 
                      b"00\x0000\x00\t00\x00ref00\x00value:0\n"
1238
 
                      b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1239
 
                      b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1240
 
                      b"11\x0044\x00\t11\x00ref00\x00value:4\n"
1241
 
                      b""
1242
 
                      )
 
1233
            b"00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1234
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1235
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1236
            b"11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1237
            b""
 
1238
            )
1243
1239
        node = btree_index._LeafNode(node_bytes, 2, 2)
1244
1240
        # We do direct access, or don't care about order, to leaf nodes most of
1245
1241
        # the time, so a dict is useful:
1246
1242
        self.assertEqual({
1247
1243
            (b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
1248
1244
            (b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
1249
 
                                          ((b'00', b'ref00'), (b'01', b'ref01')))),
 
1245
                ((b'00', b'ref00'), (b'01', b'ref01')))),
1250
1246
            (b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
1251
 
                                          ((b'11', b'ref22'), (b'11', b'ref22')))),
 
1247
                ((b'11', b'ref22'), (b'11', b'ref22')))),
1252
1248
            (b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
1253
1249
            }, dict(node.all_items()))
1254
1250
 
1255
1251
    def test_InternalNode_1(self):
1256
1252
        node_bytes = (b"type=internal\n"
1257
 
                      b"offset=1\n"
1258
 
                      b"0000000000000000000000000000000000000000\n"
1259
 
                      b"1111111111111111111111111111111111111111\n"
1260
 
                      b"2222222222222222222222222222222222222222\n"
1261
 
                      b"3333333333333333333333333333333333333333\n"
1262
 
                      b"4444444444444444444444444444444444444444\n"
1263
 
                      )
 
1253
            b"offset=1\n"
 
1254
            b"0000000000000000000000000000000000000000\n"
 
1255
            b"1111111111111111111111111111111111111111\n"
 
1256
            b"2222222222222222222222222222222222222222\n"
 
1257
            b"3333333333333333333333333333333333333333\n"
 
1258
            b"4444444444444444444444444444444444444444\n"
 
1259
            )
1264
1260
        node = btree_index._InternalNode(node_bytes)
1265
1261
        # We want to bisect to find the right children from this node, so a
1266
1262
        # vector is most useful.
1275
1271
 
1276
1272
    def test_LeafNode_2_2(self):
1277
1273
        node_bytes = (b"type=leaf\n"
1278
 
                      b"00\x0000\x00\t00\x00ref00\x00value:0\n"
1279
 
                      b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1280
 
                      b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1281
 
                      b"11\x0044\x00\t11\x00ref00\x00value:4\n"
1282
 
                      b""
1283
 
                      )
 
1274
            b"00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1275
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1276
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1277
            b"11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1278
            b""
 
1279
            )
1284
1280
        node = btree_index._LeafNode(node_bytes, 2, 2)
1285
1281
        # We do direct access, or don't care about order, to leaf nodes most of
1286
1282
        # the time, so a dict is useful:
1287
1283
        self.assertEqual({
1288
1284
            (b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
1289
1285
            (b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
1290
 
                                          ((b'00', b'ref00'), (b'01', b'ref01')))),
 
1286
                ((b'00', b'ref00'), (b'01', b'ref01')))),
1291
1287
            (b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
1292
 
                                          ((b'11', b'ref22'), (b'11', b'ref22')))),
 
1288
                ((b'11', b'ref22'), (b'11', b'ref22')))),
1293
1289
            (b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
1294
1290
            }, dict(node.all_items()))
1295
1291
 
1302
1298
    def test__flatten_node(self):
1303
1299
        self.assertFlattened(b'key\0\0value\n', (b'key',), b'value', [])
1304
1300
        self.assertFlattened(b'key\0tuple\0\0value str\n',
1305
 
                             (b'key', b'tuple'), b'value str', [])
 
1301
            (b'key', b'tuple'), b'value str', [])
1306
1302
        self.assertFlattened(b'key\0tuple\0triple\0\0value str\n',
1307
 
                             (b'key', b'tuple', b'triple'), b'value str', [])
 
1303
            (b'key', b'tuple', b'triple'), b'value str', [])
1308
1304
        self.assertFlattened(b'k\0t\0s\0ref\0value str\n',
1309
 
                             (b'k', b't', b's'), b'value str', [[(b'ref',)]])
 
1305
            (b'k', b't', b's'), b'value str', [[(b'ref',)]])
1310
1306
        self.assertFlattened(b'key\0tuple\0ref\0key\0value str\n',
1311
 
                             (b'key', b'tuple'), b'value str', [[(b'ref', b'key')]])
 
1307
            (b'key', b'tuple'), b'value str', [[(b'ref', b'key')]])
1312
1308
        self.assertFlattened(b"00\x0000\x00\t00\x00ref00\x00value:0\n",
1313
 
                             (b'00', b'00'), b'value:0', ((), ((b'00', b'ref00'),)))
 
1309
            (b'00', b'00'), b'value:0', ((), ((b'00', b'ref00'),)))
1314
1310
        self.assertFlattened(
1315
1311
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
1316
1312
            (b'00', b'11'), b'value:1',
1317
 
            (((b'00', b'ref00'),), ((b'00', b'ref00'), (b'01', b'ref01'))))
 
1313
                (((b'00', b'ref00'),), ((b'00', b'ref00'), (b'01', b'ref01'))))
1318
1314
        self.assertFlattened(
1319
1315
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
1320
1316
            (b'11', b'33'), b'value:3',
1321
 
            (((b'11', b'ref22'),), ((b'11', b'ref22'), (b'11', b'ref22'))))
 
1317
                (((b'11', b'ref22'),), ((b'11', b'ref22'), (b'11', b'ref22'))))
1322
1318
        self.assertFlattened(
1323
1319
            b"11\x0044\x00\t11\x00ref00\x00value:4\n",
1324
1320
            (b'11', b'44'), b'value:4', ((), ((b'11', b'ref00'),)))
1337
1333
    def assertMultiBisectRight(self, offsets, search_keys, fixed_keys):
1338
1334
        self.assertEqual(offsets,
1339
1335
                         btree_index.BTreeGraphIndex._multi_bisect_right(
1340
 
                             search_keys, fixed_keys))
 
1336
                            search_keys, fixed_keys))
1341
1337
 
1342
1338
    def test_after(self):
1343
1339
        self.assertMultiBisectRight([(1, ['b'])], ['b'], ['a'])
1351
1347
 
1352
1348
    def test_exact(self):
1353
1349
        self.assertMultiBisectRight([(1, ['a'])], ['a'], ['a'])
1354
 
        self.assertMultiBisectRight(
1355
 
            [(1, ['a']), (2, ['b'])], ['a', 'b'], ['a', 'b'])
 
1350
        self.assertMultiBisectRight([(1, ['a']), (2, ['b'])], ['a', 'b'], ['a', 'b'])
1356
1351
        self.assertMultiBisectRight([(1, ['a']), (3, ['c'])],
1357
1352
                                    ['a', 'c'], ['a', 'b', 'c'])
1358
1353
 
1402
1397
        self.set_cached_offsets(index, cached_offsets)
1403
1398
 
1404
1399
    def make_100_node_index(self):
1405
 
        index = self.make_index(4096 * 100, 6)
 
1400
        index = self.make_index(4096*100, 6)
1406
1401
        # Consider we've already made a single request at the middle
1407
1402
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1408
1403
                           key_count=1000, row_lengths=[1, 99],
1410
1405
        return index
1411
1406
 
1412
1407
    def make_1000_node_index(self):
1413
 
        index = self.make_index(4096 * 1000, 6)
 
1408
        index = self.make_index(4096*1000, 6)
1414
1409
        # Pretend we've already made a single request in the middle
1415
1410
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1416
1411
                           key_count=90000, row_lengths=[1, 9, 990],
1438
1433
        self.assertNumPages(1, index, 4096)
1439
1434
        self.assertNumPages(2, index, 4097)
1440
1435
        self.assertNumPages(2, index, 8192)
1441
 
        self.assertNumPages(76, index, 4096 * 75 + 10)
 
1436
        self.assertNumPages(76, index, 4096*75 + 10)
1442
1437
 
1443
1438
    def test__find_layer_start_and_stop(self):
1444
1439
        index = self.make_1000_node_index()
1456
1451
        self.assertExpandOffsets([1, 4, 9], index, [1, 4, 9])
1457
1452
 
1458
1453
    def test_more_than_recommended(self):
1459
 
        index = self.make_index(4096 * 100, 2)
 
1454
        index = self.make_index(4096*100, 2)
1460
1455
        self.assertExpandOffsets([1, 10], index, [1, 10])
1461
1456
        self.assertExpandOffsets([1, 10, 20], index, [1, 10, 20])
1462
1457
 
1463
1458
    def test_read_all_from_root(self):
1464
 
        index = self.make_index(4096 * 10, 20)
 
1459
        index = self.make_index(4096*10, 20)
1465
1460
        self.assertExpandOffsets(list(range(10)), index, [0])
1466
1461
 
1467
1462
    def test_read_all_when_cached(self):
1468
1463
        # We've read enough that we can grab all the rest in a single request
1469
 
        index = self.make_index(4096 * 10, 5)
 
1464
        index = self.make_index(4096*10, 5)
1470
1465
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1471
1466
                           key_count=1000, row_lengths=[1, 9],
1472
1467
                           cached_offsets=[0, 1, 2, 5, 6])
1476
1471
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [9])
1477
1472
 
1478
1473
    def test_no_root_node(self):
1479
 
        index = self.make_index(4096 * 10, 5)
 
1474
        index = self.make_index(4096*10, 5)
1480
1475
        self.assertExpandOffsets([0], index, [0])
1481
1476
 
1482
1477
    def test_include_neighbors(self):
1492
1487
        # Requesting many nodes will expand all locations equally
1493
1488
        self.assertExpandOffsets([1, 2, 3, 80, 81, 82], index, [2, 81])
1494
1489
        self.assertExpandOffsets([1, 2, 3, 9, 10, 11, 80, 81, 82], index,
1495
 
                                 [2, 10, 81])
 
1490
                               [2, 10, 81])
1496
1491
 
1497
1492
    def test_stop_at_cached(self):
1498
1493
        index = self.make_100_node_index()