← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

  • Committer: Martin
  • Date: 2010-05-03 20:57:39 UTC
  • mto: This revision was merged to the branch mainline in revision 5204.
  • Revision ID: gzlist@googlemail.com-20100503205739-n326zdvevv0rmruh
Retain original stack and error message when translating to ValueError in bencode

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
1
 
# Copyright (C) 2008-2011 Canonical Ltd
 
1
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
27
27
    lru_cache,
28
28
    osutils,
29
29
    tests,
30
 
    transport,
31
30
    )
32
31
from bzrlib.tests import (
33
32
    TestCaseWithTransport,
34
 
    scenarios,
35
 
    )
36
 
from bzrlib.tests import (
37
 
    features,
38
 
    )
39
 
 
40
 
 
41
 
load_tests = scenarios.load_tests_apply_scenarios
42
 
 
43
 
 
44
 
def btreeparser_scenarios():
 
33
    condition_isinstance,
 
34
    multiply_tests,
 
35
    split_suite_by_condition,
 
36
    )
 
37
from bzrlib.transport import get_transport
 
38
 
 
39
 
 
40
def load_tests(standard_tests, module, loader):
 
41
    # parameterise the TestBTreeNodes tests
 
42
    node_tests, others = split_suite_by_condition(standard_tests,
 
43
        condition_isinstance(TestBTreeNodes))
45
44
    import bzrlib._btree_serializer_py as py_module
46
45
    scenarios = [('python', {'parse_btree': py_module})]
47
46
    if compiled_btreeparser_feature.available():
48
 
        scenarios.append(('C', 
49
 
            {'parse_btree': compiled_btreeparser_feature.module}))
50
 
    return scenarios
51
 
 
52
 
 
53
 
compiled_btreeparser_feature = features.ModuleAvailableFeature(
54
 
    'bzrlib._btree_serializer_pyx')
 
47
        scenarios.append(('C', {'parse_btree':
 
48
                                compiled_btreeparser_feature.module}))
 
49
    return multiply_tests(node_tests, scenarios, others)
 
50
 
 
51
 
 
52
compiled_btreeparser_feature = tests.ModuleAvailableFeature(
 
53
                                'bzrlib._btree_serializer_pyx')
55
54
 
56
55
 
57
56
class BTreeTestCase(TestCaseWithTransport):
59
58
    # that they test.
60
59
 
61
60
    def setUp(self):
62
 
        super(BTreeTestCase, self).setUp()
 
61
        TestCaseWithTransport.setUp(self)
63
62
        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
64
63
 
65
64
    def make_nodes(self, count, key_elements, reference_lists):
103
102
        self.overrideAttr(btree_index, '_PAGE_SIZE')
104
103
        btree_index._PAGE_SIZE = 2048
105
104
 
106
 
    def assertEqualsApproxCompressed(self, expected, actual, slop=6):
107
 
        """Check a count of compressed bytes is approximately as expected
108
 
 
109
 
        Relying on compressed length being stable even with fixed inputs is
110
 
        slightly bogus, but zlib is stable enough that this mostly works.
111
 
        """
112
 
        if not expected - slop < actual < expected + slop:
113
 
            self.fail("Expected around %d bytes compressed but got %d" %
114
 
                (expected, actual))
115
 
 
116
105
 
117
106
class TestBTreeBuilder(BTreeTestCase):
118
107
 
209
198
        temp_file = builder.finish()
210
199
        content = temp_file.read()
211
200
        del temp_file
212
 
        self.assertEqualsApproxCompressed(9283, len(content))
 
201
        self.assertEqual(9283, len(content))
213
202
        self.assertEqual(
214
203
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
215
204
            "row_lengths=1,2\n",
227
216
        leaf1_bytes = zlib.decompress(leaf1)
228
217
        sorted_node_keys = sorted(node[0] for node in nodes)
229
218
        node = btree_index._LeafNode(leaf1_bytes, 1, 0)
230
 
        self.assertEqual(231, len(node))
231
 
        self.assertEqual(sorted_node_keys[:231], node.all_keys())
 
219
        self.assertEqual(231, len(node.keys))
 
220
        self.assertEqual(sorted_node_keys[:231], sorted(node.keys))
232
221
        leaf2_bytes = zlib.decompress(leaf2)
233
222
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
234
 
        self.assertEqual(400 - 231, len(node))
235
 
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
 
223
        self.assertEqual(400 - 231, len(node.keys))
 
224
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
236
225
 
237
226
    def test_last_page_rounded_1_layer(self):
238
227
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
243
232
        temp_file = builder.finish()
244
233
        content = temp_file.read()
245
234
        del temp_file
246
 
        self.assertEqualsApproxCompressed(155, len(content))
 
235
        self.assertEqual(155, len(content))
247
236
        self.assertEqual(
248
237
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
249
238
            "row_lengths=1\n",
252
241
        leaf2 = content[74:]
253
242
        leaf2_bytes = zlib.decompress(leaf2)
254
243
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
255
 
        self.assertEqual(10, len(node))
 
244
        self.assertEqual(10, len(node.keys))
256
245
        sorted_node_keys = sorted(node[0] for node in nodes)
257
 
        self.assertEqual(sorted_node_keys, node.all_keys())
 
246
        self.assertEqual(sorted_node_keys, sorted(node.keys))
258
247
 
259
248
    def test_last_page_not_rounded_2_layer(self):
260
249
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
265
254
        temp_file = builder.finish()
266
255
        content = temp_file.read()
267
256
        del temp_file
268
 
        self.assertEqualsApproxCompressed(9283, len(content))
 
257
        self.assertEqual(9283, len(content))
269
258
        self.assertEqual(
270
259
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
271
260
            "row_lengths=1,2\n",
274
263
        leaf2 = content[8192:]
275
264
        leaf2_bytes = zlib.decompress(leaf2)
276
265
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
277
 
        self.assertEqual(400 - 231, len(node))
 
266
        self.assertEqual(400 - 231, len(node.keys))
278
267
        sorted_node_keys = sorted(node[0] for node in nodes)
279
 
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
 
268
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
280
269
 
281
270
    def test_three_level_tree_details(self):
282
271
        # The left most pointer in the second internal node in a row should
291
280
 
292
281
        for node in nodes:
293
282
            builder.add_node(*node)
294
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
295
 
        size = t.put_file('index', self.time(builder.finish))
 
283
        transport = get_transport('trace+' + self.get_url(''))
 
284
        size = transport.put_file('index', self.time(builder.finish))
296
285
        del builder
297
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
286
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
298
287
        # Seed the metadata, we're using internal calls now.
299
288
        index.key_count()
300
289
        self.assertEqual(3, len(index._row_lengths),
313
302
        # in the second node it points at
314
303
        pos = index._row_offsets[2] + internal_node2.offset + 1
315
304
        leaf = index._get_leaf_nodes([pos])[pos]
316
 
        self.assertTrue(internal_node2.keys[0] in leaf)
 
305
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
317
306
 
318
307
    def test_2_leaves_2_2(self):
319
308
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
324
313
        temp_file = builder.finish()
325
314
        content = temp_file.read()
326
315
        del temp_file
327
 
        self.assertEqualsApproxCompressed(12643, len(content))
 
316
        self.assertEqual(12643, len(content))
328
317
        self.assertEqual(
329
318
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
330
319
            "row_lengths=1,3\n",
420
409
        self.assertEqual(None, builder._backing_indices[2])
421
410
        self.assertEqual(16, builder._backing_indices[3].key_count())
422
411
        # Now finish, and check we got a correctly ordered tree
423
 
        t = self.get_transport('')
424
 
        size = t.put_file('index', builder.finish())
425
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
412
        transport = self.get_transport('')
 
413
        size = transport.put_file('index', builder.finish())
 
414
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
426
415
        nodes = list(index.iter_all_entries())
427
416
        self.assertEqual(sorted(nodes), nodes)
428
417
        self.assertEqual(16, len(nodes))
618
607
        for key, value, references in nodes:
619
608
            builder.add_node(key, value, references)
620
609
        stream = builder.finish()
621
 
        trans = transport.get_transport_from_url('trace+' + self.get_url())
 
610
        trans = get_transport('trace+' + self.get_url())
622
611
        size = trans.put_file('index', stream)
623
612
        return btree_index.BTreeGraphIndex(trans, 'index', size)
624
613
 
659
648
        self.assertEqual(0, len(index._leaf_node_cache))
660
649
 
661
650
    def test_trivial_constructor(self):
662
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
663
 
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
651
        transport = get_transport('trace+' + self.get_url(''))
 
652
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
664
653
        # Checks the page size at load, but that isn't logged yet.
665
 
        self.assertEqual([], t._activity)
 
654
        self.assertEqual([], transport._activity)
666
655
 
667
656
    def test_with_size_constructor(self):
668
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
669
 
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
 
657
        transport = get_transport('trace+' + self.get_url(''))
 
658
        index = btree_index.BTreeGraphIndex(transport, 'index', 1)
670
659
        # Checks the page size at load, but that isn't logged yet.
671
 
        self.assertEqual([], t._activity)
 
660
        self.assertEqual([], transport._activity)
672
661
 
673
662
    def test_empty_key_count_no_size(self):
674
663
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
675
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
676
 
        t.put_file('index', builder.finish())
677
 
        index = btree_index.BTreeGraphIndex(t, 'index', None)
678
 
        del t._activity[:]
679
 
        self.assertEqual([], t._activity)
 
664
        transport = get_transport('trace+' + self.get_url(''))
 
665
        transport.put_file('index', builder.finish())
 
666
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
 
667
        del transport._activity[:]
 
668
        self.assertEqual([], transport._activity)
680
669
        self.assertEqual(0, index.key_count())
681
670
        # The entire index should have been requested (as we generally have the
682
671
        # size available, and doing many small readvs is inappropriate).
683
672
        # We can't tell how much was actually read here, but - check the code.
684
 
        self.assertEqual([('get', 'index')], t._activity)
 
673
        self.assertEqual([('get', 'index')], transport._activity)
685
674
 
686
675
    def test_empty_key_count(self):
687
676
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
688
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
689
 
        size = t.put_file('index', builder.finish())
 
677
        transport = get_transport('trace+' + self.get_url(''))
 
678
        size = transport.put_file('index', builder.finish())
690
679
        self.assertEqual(72, size)
691
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
692
 
        del t._activity[:]
693
 
        self.assertEqual([], t._activity)
 
680
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
681
        del transport._activity[:]
 
682
        self.assertEqual([], transport._activity)
694
683
        self.assertEqual(0, index.key_count())
695
684
        # The entire index should have been read, as 4K > size
696
685
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
697
 
                         t._activity)
 
686
            transport._activity)
698
687
 
699
688
    def test_non_empty_key_count_2_2(self):
700
689
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
701
690
        nodes = self.make_nodes(35, 2, 2)
702
691
        for node in nodes:
703
692
            builder.add_node(*node)
704
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
705
 
        size = t.put_file('index', builder.finish())
706
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
707
 
        del t._activity[:]
708
 
        self.assertEqual([], t._activity)
 
693
        transport = get_transport('trace+' + self.get_url(''))
 
694
        size = transport.put_file('index', builder.finish())
 
695
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
696
        del transport._activity[:]
 
697
        self.assertEqual([], transport._activity)
709
698
        self.assertEqual(70, index.key_count())
710
699
        # The entire index should have been read, as it is one page long.
711
700
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
712
 
            t._activity)
713
 
        self.assertEqualsApproxCompressed(1173, size)
 
701
            transport._activity)
 
702
        self.assertEqual(1173, size)
714
703
 
715
704
    def test_with_offset_no_size(self):
716
705
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
733
722
 
734
723
    def test__read_nodes_no_size_one_page_reads_once(self):
735
724
        self.make_index(nodes=[(('key',), 'value', ())])
736
 
        trans = transport.get_transport_from_url('trace+' + self.get_url())
 
725
        trans = get_transport('trace+' + self.get_url())
737
726
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
738
727
        del trans._activity[:]
739
728
        nodes = dict(index._read_nodes([0]))
740
729
        self.assertEqual([0], nodes.keys())
741
730
        node = nodes[0]
742
 
        self.assertEqual([('key',)], node.all_keys())
 
731
        self.assertEqual([('key',)], node.keys.keys())
743
732
        self.assertEqual([('get', 'index')], trans._activity)
744
733
 
745
734
    def test__read_nodes_no_size_multiple_pages(self):
747
736
        index.key_count()
748
737
        num_pages = index._row_offsets[-1]
749
738
        # Reopen with a traced transport and no size
750
 
        trans = transport.get_transport_from_url('trace+' + self.get_url())
 
739
        trans = get_transport('trace+' + self.get_url())
751
740
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
752
741
        del trans._activity[:]
753
742
        nodes = dict(index._read_nodes([0]))
758
747
        nodes = self.make_nodes(160, 2, 2)
759
748
        for node in nodes:
760
749
            builder.add_node(*node)
761
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
762
 
        size = t.put_file('index', builder.finish())
763
 
        self.assertEqualsApproxCompressed(17692, size)
764
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
765
 
        del t._activity[:]
766
 
        self.assertEqual([], t._activity)
 
750
        transport = get_transport('trace+' + self.get_url(''))
 
751
        size = transport.put_file('index', builder.finish())
 
752
        self.assertEqual(17692, size)
 
753
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
754
        del transport._activity[:]
 
755
        self.assertEqual([], transport._activity)
767
756
        self.assertEqual(320, index.key_count())
768
757
        # The entire index should not have been read.
769
758
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
770
 
                         t._activity)
 
759
            transport._activity)
771
760
 
772
761
    def test_validate_one_page(self):
773
762
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
774
763
        nodes = self.make_nodes(45, 2, 2)
775
764
        for node in nodes:
776
765
            builder.add_node(*node)
777
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
778
 
        size = t.put_file('index', builder.finish())
779
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
780
 
        del t._activity[:]
781
 
        self.assertEqual([], t._activity)
 
766
        transport = get_transport('trace+' + self.get_url(''))
 
767
        size = transport.put_file('index', builder.finish())
 
768
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
769
        del transport._activity[:]
 
770
        self.assertEqual([], transport._activity)
782
771
        index.validate()
783
772
        # The entire index should have been read linearly.
784
773
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
785
 
                         t._activity)
786
 
        self.assertEqualsApproxCompressed(1488, size)
 
774
            transport._activity)
 
775
        self.assertEqual(1488, size)
787
776
 
788
777
    def test_validate_two_pages(self):
789
778
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
790
779
        nodes = self.make_nodes(80, 2, 2)
791
780
        for node in nodes:
792
781
            builder.add_node(*node)
793
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
794
 
        size = t.put_file('index', builder.finish())
 
782
        transport = get_transport('trace+' + self.get_url(''))
 
783
        size = transport.put_file('index', builder.finish())
795
784
        # Root page, 2 leaf pages
796
 
        self.assertEqualsApproxCompressed(9339, size)
797
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
798
 
        del t._activity[:]
799
 
        self.assertEqual([], t._activity)
 
785
        self.assertEqual(9339, size)
 
786
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
787
        del transport._activity[:]
 
788
        self.assertEqual([], transport._activity)
800
789
        index.validate()
801
 
        rem = size - 8192 # Number of remaining bytes after second block
802
790
        # The entire index should have been read linearly.
803
 
        self.assertEqual(
804
 
            [('readv', 'index', [(0, 4096)], False, None),
805
 
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
806
 
            t._activity)
 
791
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
 
792
            ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
 
793
            transport._activity)
807
794
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
808
795
        # node and make validate find them.
809
796
 
810
797
    def test_eq_ne(self):
811
798
        # two indices are equal when constructed with the same parameters:
812
 
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
813
 
        t2 = self.get_transport()
814
 
        self.assertTrue(
815
 
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
816
 
            btree_index.BTreeGraphIndex(t1, 'index', None))
817
 
        self.assertTrue(
818
 
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
819
 
            btree_index.BTreeGraphIndex(t1, 'index', 20))
820
 
        self.assertFalse(
821
 
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
822
 
            btree_index.BTreeGraphIndex(t2, 'index', 20))
823
 
        self.assertFalse(
824
 
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
825
 
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
826
 
        self.assertFalse(
827
 
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
828
 
            btree_index.BTreeGraphIndex(t1, 'index', 20))
829
 
        self.assertFalse(
830
 
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
831
 
            btree_index.BTreeGraphIndex(t1, 'index', None))
832
 
        self.assertFalse(
833
 
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
834
 
            btree_index.BTreeGraphIndex(t1, 'index', 20))
835
 
        self.assertTrue(
836
 
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
837
 
            btree_index.BTreeGraphIndex(t2, 'index', 20))
838
 
        self.assertTrue(
839
 
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
840
 
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
841
 
        self.assertTrue(
842
 
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
843
 
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
799
        transport1 = get_transport('trace+' + self.get_url(''))
 
800
        transport2 = get_transport(self.get_url(''))
 
801
        self.assertTrue(
 
802
            btree_index.BTreeGraphIndex(transport1, 'index', None) ==
 
803
            btree_index.BTreeGraphIndex(transport1, 'index', None))
 
804
        self.assertTrue(
 
805
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
 
806
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
807
        self.assertFalse(
 
808
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
 
809
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
 
810
        self.assertFalse(
 
811
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) ==
 
812
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
 
813
        self.assertFalse(
 
814
            btree_index.BTreeGraphIndex(transport1, 'index', 10) ==
 
815
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
816
        self.assertFalse(
 
817
            btree_index.BTreeGraphIndex(transport1, 'index', None) !=
 
818
            btree_index.BTreeGraphIndex(transport1, 'index', None))
 
819
        self.assertFalse(
 
820
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
 
821
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
822
        self.assertTrue(
 
823
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
 
824
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
 
825
        self.assertTrue(
 
826
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) !=
 
827
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
 
828
        self.assertTrue(
 
829
            btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
 
830
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
844
831
 
845
 
    def test_key_too_big(self):
846
 
        # the size that matters here is the _compressed_ size of the key, so we can't
847
 
        # do a simple character repeat.
848
 
        bigKey = ''.join(map(repr, xrange(btree_index._PAGE_SIZE)))
849
 
        self.assertRaises(errors.BadIndexKey,
850
 
                          self.make_index,
851
 
                          nodes=[((bigKey,), 'value', ())])
852
 
        
853
832
    def test_iter_all_only_root_no_size(self):
854
833
        self.make_index(nodes=[(('key',), 'value', ())])
855
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
856
 
        index = btree_index.BTreeGraphIndex(t, 'index', None)
857
 
        del t._activity[:]
 
834
        trans = get_transport('trace+' + self.get_url(''))
 
835
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
 
836
        del trans._activity[:]
858
837
        self.assertEqual([(('key',), 'value')],
859
838
                         [x[1:] for x in index.iter_all_entries()])
860
 
        self.assertEqual([('get', 'index')], t._activity)
 
839
        self.assertEqual([('get', 'index')], trans._activity)
861
840
 
862
841
    def test_iter_all_entries_reads(self):
863
842
        # iterating all entries reads the header, then does a linear
869
848
        nodes = self.make_nodes(10000, 2, 2)
870
849
        for node in nodes:
871
850
            builder.add_node(*node)
872
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
873
 
        size = t.put_file('index', builder.finish())
 
851
        transport = get_transport('trace+' + self.get_url(''))
 
852
        size = transport.put_file('index', builder.finish())
 
853
        self.assertEqual(1303220, size, 'number of expected bytes in the'
 
854
                                        ' output changed')
874
855
        page_size = btree_index._PAGE_SIZE
875
856
        del builder
876
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
877
 
        del t._activity[:]
878
 
        self.assertEqual([], t._activity)
 
857
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
858
        del transport._activity[:]
 
859
        self.assertEqual([], transport._activity)
879
860
        found_nodes = self.time(list, index.iter_all_entries())
880
861
        bare_nodes = []
881
862
        for node in found_nodes:
892
873
        # The entire index should have been read
893
874
        total_pages = sum(index._row_lengths)
894
875
        self.assertEqual(total_pages, index._row_offsets[-1])
895
 
        self.assertEqualsApproxCompressed(1303220, size)
 
876
        self.assertEqual(1303220, size)
896
877
        # The start of the leaves
897
878
        first_byte = index._row_offsets[-2] * page_size
898
879
        readv_request = []
899
880
        for offset in range(first_byte, size, page_size):
900
881
            readv_request.append((offset, page_size))
901
882
        # The last page is truncated
902
 
        readv_request[-1] = (readv_request[-1][0], size % page_size)
 
883
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
903
884
        expected = [('readv', 'index', [(0, page_size)], False, None),
904
885
             ('readv',  'index', readv_request, False, None)]
905
 
        if expected != t._activity:
 
886
        if expected != transport._activity:
906
887
            self.assertEqualDiff(pprint.pformat(expected),
907
 
                                 pprint.pformat(t._activity))
 
888
                                 pprint.pformat(transport._activity))
908
889
 
909
890
    def _test_iter_entries_references_resolved(self):
910
891
        index = self.make_index(1, nodes=[
922
903
        nodes = self.make_nodes(160, 2, 2)
923
904
        for node in nodes:
924
905
            builder.add_node(*node)
925
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
926
 
        size = t.put_file('index', builder.finish())
 
906
        transport = get_transport('trace+' + self.get_url(''))
 
907
        size = transport.put_file('index', builder.finish())
927
908
        del builder
928
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
929
 
        del t._activity[:]
930
 
        self.assertEqual([], t._activity)
 
909
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
910
        del transport._activity[:]
 
911
        self.assertEqual([], transport._activity)
931
912
        # search for one key
932
913
        found_nodes = list(index.iter_entries([nodes[30][0]]))
933
914
        bare_nodes = []
941
922
        # Should have read the root node, then one leaf page:
942
923
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
943
924
             ('readv',  'index', [(8192, 4096), ], False, None)],
944
 
            t._activity)
 
925
            transport._activity)
945
926
 
946
927
    def test_iter_key_prefix_1_element_key_None(self):
947
928
        index = self.make_index()
1130
1111
        min_l2_key = l2.min_key
1131
1112
        max_l1_key = l1.max_key
1132
1113
        self.assertTrue(max_l1_key < min_l2_key)
1133
 
        parents_min_l2_key = l2[min_l2_key][1][0]
 
1114
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
1134
1115
        self.assertEqual((l1.max_key,), parents_min_l2_key)
1135
1116
        # Now, whatever key we select that would fall on the second page,
1136
1117
        # should give us all the parents until the page break
1149
1130
        parent_map = {}
1150
1131
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1151
1132
                                            missing_keys)
1152
 
        self.assertEqual(l1.all_keys(), sorted(parent_map))
 
1133
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
1153
1134
        self.assertEqual(set(), missing_keys)
1154
1135
        self.assertEqual(set(), search_keys)
1155
1136
 
1171
1152
        for node in nodes:
1172
1153
            builder.add_node(*node)
1173
1154
        stream = builder.finish()
1174
 
        trans = self.get_transport()
 
1155
        trans = get_transport(self.get_url())
1175
1156
        size = trans.put_file('index', stream)
1176
1157
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1177
1158
        self.assertEqual(500, index.key_count())
1203
1184
 
1204
1185
class TestBTreeNodes(BTreeTestCase):
1205
1186
 
1206
 
    scenarios = btreeparser_scenarios()
1207
 
 
1208
1187
    def setUp(self):
1209
 
        super(TestBTreeNodes, self).setUp()
 
1188
        BTreeTestCase.setUp(self)
1210
1189
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1211
1190
 
1212
1191
    def test_LeafNode_1_0(self):
1225
1204
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
1226
1205
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
1227
1206
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1228
 
            }, dict(node.all_items()))
 
1207
            }, node.keys)
1229
1208
 
1230
1209
    def test_LeafNode_2_2(self):
1231
1210
        node_bytes = ("type=leaf\n"
1245
1224
            ('11', '33'): ('value:3',
1246
1225
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1247
1226
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1248
 
            }, dict(node.all_items()))
 
1227
            }, node.keys)
1249
1228
 
1250
1229
    def test_InternalNode_1(self):
1251
1230
        node_bytes = ("type=internal\n"
1286
1265
            ('11', '33'): ('value:3',
1287
1266
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1288
1267
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1289
 
            }, dict(node.all_items()))
 
1268
            }, node.keys)
1290
1269
 
1291
1270
    def assertFlattened(self, expected, key, value, refs):
1292
1271
        flat_key, flat_line = self.parse_btree._flatten_node(
1370
1349
        This doesn't actually create anything on disk, it just primes a
1371
1350
        BTreeGraphIndex with the recommended information.
1372
1351
        """
1373
 
        index = btree_index.BTreeGraphIndex(
1374
 
            transport.get_transport_from_url('memory:///'),
1375
 
            'test-index', size=size)
 
1352
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
 
1353
                                            'test-index', size=size)
1376
1354
        if recommended_pages is not None:
1377
1355
            index._recommended_pages = recommended_pages
1378
1356
        return index