/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: 2017-07-23 22:06:41 UTC
  • mfrom: (6738 trunk)
  • mto: This revision was merged to the branch mainline in revision 6739.
  • Revision ID: jelmer@jelmer.uk-20170723220641-69eczax9bmv8d6kk
Merge trunk, address review comments.

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