/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: 2019-03-04 00:16:27 UTC
  • mfrom: (7293 work)
  • mto: This revision was merged to the branch mainline in revision 7318.
  • Revision ID: jelmer@jelmer.uk-20190304001627-v6u7o6pf97tukhek
Merge trunk.

Show diffs side-by-side

added added

removed removed

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