/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-06-10 21:59:15 UTC
  • mto: This revision was merged to the branch mainline in revision 6690.
  • Revision ID: jelmer@jelmer.uk-20170610215915-zcpu0in3r1irx3ml
Move serializer to bzr.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test_btree_index.py
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2008-2012, 2016 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
20
20
import pprint
21
21
import zlib
22
22
 
23
 
from bzrlib import (
24
 
    btree_index,
 
23
from .. import (
25
24
    errors,
26
25
    fifo_cache,
27
26
    lru_cache,
28
27
    osutils,
29
28
    tests,
30
 
    )
31
 
from bzrlib.tests import (
 
29
    transport,
 
30
    )
 
31
from ..bzr import (
 
32
    btree_index,
 
33
    )
 
34
from ..tests import (
32
35
    TestCaseWithTransport,
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))
44
 
    import bzrlib._btree_serializer_py as py_module
 
36
    scenarios,
 
37
    )
 
38
from ..tests import (
 
39
    features,
 
40
    )
 
41
 
 
42
 
 
43
load_tests = scenarios.load_tests_apply_scenarios
 
44
 
 
45
 
 
46
def btreeparser_scenarios():
 
47
    import breezy.bzr._btree_serializer_py as py_module
45
48
    scenarios = [('python', {'parse_btree': py_module})]
46
49
    if compiled_btreeparser_feature.available():
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')
 
50
        scenarios.append(('C', 
 
51
            {'parse_btree': compiled_btreeparser_feature.module}))
 
52
    return scenarios
 
53
 
 
54
 
 
55
compiled_btreeparser_feature = features.ModuleAvailableFeature(
 
56
    'breezy.bzr._btree_serializer_pyx')
54
57
 
55
58
 
56
59
class BTreeTestCase(TestCaseWithTransport):
58
61
    # that they test.
59
62
 
60
63
    def setUp(self):
61
 
        TestCaseWithTransport.setUp(self)
 
64
        super(BTreeTestCase, self).setUp()
62
65
        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
63
66
 
64
67
    def make_nodes(self, count, key_elements, reference_lists):
69
72
                prefix = (str(prefix_pos) * 40,)
70
73
            else:
71
74
                prefix = ()
72
 
            for pos in xrange(count):
 
75
            for pos in range(count):
73
76
                # TODO: This creates odd keys. When count == 100,000, it
74
77
                #       creates a 240 byte key
75
78
                key = prefix + (str(pos) * 40,)
102
105
        self.overrideAttr(btree_index, '_PAGE_SIZE')
103
106
        btree_index._PAGE_SIZE = 2048
104
107
 
 
108
    def assertEqualApproxCompressed(self, expected, actual, slop=6):
 
109
        """Check a count of compressed bytes is approximately as expected
 
110
 
 
111
        Relying on compressed length being stable even with fixed inputs is
 
112
        slightly bogus, but zlib is stable enough that this mostly works.
 
113
        """
 
114
        if not expected - slop < actual < expected + slop:
 
115
            self.fail("Expected around %d bytes compressed but got %d" %
 
116
                (expected, actual))
 
117
 
105
118
 
106
119
class TestBTreeBuilder(BTreeTestCase):
107
120
 
198
211
        temp_file = builder.finish()
199
212
        content = temp_file.read()
200
213
        del temp_file
201
 
        self.assertEqual(9283, len(content))
 
214
        self.assertEqualApproxCompressed(9283, len(content))
202
215
        self.assertEqual(
203
216
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
204
217
            "row_lengths=1,2\n",
216
229
        leaf1_bytes = zlib.decompress(leaf1)
217
230
        sorted_node_keys = sorted(node[0] for node in nodes)
218
231
        node = btree_index._LeafNode(leaf1_bytes, 1, 0)
219
 
        self.assertEqual(231, len(node.keys))
220
 
        self.assertEqual(sorted_node_keys[:231], sorted(node.keys))
 
232
        self.assertEqual(231, len(node))
 
233
        self.assertEqual(sorted_node_keys[:231], node.all_keys())
221
234
        leaf2_bytes = zlib.decompress(leaf2)
222
235
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
223
 
        self.assertEqual(400 - 231, len(node.keys))
224
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
236
        self.assertEqual(400 - 231, len(node))
 
237
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
225
238
 
226
239
    def test_last_page_rounded_1_layer(self):
227
240
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
232
245
        temp_file = builder.finish()
233
246
        content = temp_file.read()
234
247
        del temp_file
235
 
        self.assertEqual(155, len(content))
 
248
        self.assertEqualApproxCompressed(155, len(content))
236
249
        self.assertEqual(
237
250
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
238
251
            "row_lengths=1\n",
241
254
        leaf2 = content[74:]
242
255
        leaf2_bytes = zlib.decompress(leaf2)
243
256
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
244
 
        self.assertEqual(10, len(node.keys))
 
257
        self.assertEqual(10, len(node))
245
258
        sorted_node_keys = sorted(node[0] for node in nodes)
246
 
        self.assertEqual(sorted_node_keys, sorted(node.keys))
 
259
        self.assertEqual(sorted_node_keys, node.all_keys())
247
260
 
248
261
    def test_last_page_not_rounded_2_layer(self):
249
262
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
254
267
        temp_file = builder.finish()
255
268
        content = temp_file.read()
256
269
        del temp_file
257
 
        self.assertEqual(9283, len(content))
 
270
        self.assertEqualApproxCompressed(9283, len(content))
258
271
        self.assertEqual(
259
272
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
260
273
            "row_lengths=1,2\n",
263
276
        leaf2 = content[8192:]
264
277
        leaf2_bytes = zlib.decompress(leaf2)
265
278
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
266
 
        self.assertEqual(400 - 231, len(node.keys))
 
279
        self.assertEqual(400 - 231, len(node))
267
280
        sorted_node_keys = sorted(node[0] for node in nodes)
268
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
281
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
269
282
 
270
283
    def test_three_level_tree_details(self):
271
284
        # The left most pointer in the second internal node in a row should
280
293
 
281
294
        for node in nodes:
282
295
            builder.add_node(*node)
283
 
        transport = get_transport('trace+' + self.get_url(''))
284
 
        size = transport.put_file('index', self.time(builder.finish))
 
296
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
297
        size = t.put_file('index', self.time(builder.finish))
285
298
        del builder
286
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
299
        index = btree_index.BTreeGraphIndex(t, 'index', size)
287
300
        # Seed the metadata, we're using internal calls now.
288
301
        index.key_count()
289
302
        self.assertEqual(3, len(index._row_lengths),
302
315
        # in the second node it points at
303
316
        pos = index._row_offsets[2] + internal_node2.offset + 1
304
317
        leaf = index._get_leaf_nodes([pos])[pos]
305
 
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
 
318
        self.assertTrue(internal_node2.keys[0] in leaf)
306
319
 
307
320
    def test_2_leaves_2_2(self):
308
321
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
313
326
        temp_file = builder.finish()
314
327
        content = temp_file.read()
315
328
        del temp_file
316
 
        self.assertEqual(12643, len(content))
 
329
        self.assertEqualApproxCompressed(12643, len(content))
317
330
        self.assertEqual(
318
331
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
319
332
            "row_lengths=1,3\n",
391
404
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
392
405
            list(builder.iter_all_entries()))
393
406
        # Two nodes - one memory one disk
394
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
407
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
395
408
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
396
409
        self.assertEqual(13, builder.key_count())
397
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
410
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
398
411
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
399
412
        builder.add_node(*nodes[13])
400
413
        self.assertEqual(3, len(builder._backing_indices))
409
422
        self.assertEqual(None, builder._backing_indices[2])
410
423
        self.assertEqual(16, builder._backing_indices[3].key_count())
411
424
        # Now finish, and check we got a correctly ordered tree
412
 
        transport = self.get_transport('')
413
 
        size = transport.put_file('index', builder.finish())
414
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
425
        t = self.get_transport('')
 
426
        size = t.put_file('index', builder.finish())
 
427
        index = btree_index.BTreeGraphIndex(t, 'index', size)
415
428
        nodes = list(index.iter_all_entries())
416
429
        self.assertEqual(sorted(nodes), nodes)
417
430
        self.assertEqual(16, len(nodes))
465
478
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
466
479
            list(builder.iter_all_entries()))
467
480
        # Two nodes - one memory one disk
468
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
481
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
469
482
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
470
483
        self.assertEqual(13, builder.key_count())
471
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
484
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
472
485
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
473
486
        builder.add_node(*nodes[13])
474
487
        builder.add_node(*nodes[14])
565
578
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
566
579
            list(builder.iter_all_entries()))
567
580
        # Two nodes - one memory one disk
568
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
581
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
569
582
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
570
583
        self.assertEqual(13, builder.key_count())
571
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
584
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
572
585
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
573
586
        builder.add_node(*nodes[13])
574
587
        self.assertEqual(3, len(builder._backing_indices))
607
620
        for key, value, references in nodes:
608
621
            builder.add_node(key, value, references)
609
622
        stream = builder.finish()
610
 
        trans = get_transport('trace+' + self.get_url())
 
623
        trans = transport.get_transport_from_url('trace+' + self.get_url())
611
624
        size = trans.put_file('index', stream)
612
625
        return btree_index.BTreeGraphIndex(trans, 'index', size)
613
626
 
632
645
        self.assertEqual(1, len(list(index.iter_entries([nodes[30][0]]))))
633
646
        self.assertEqual([1, 4], index._row_lengths)
634
647
        self.assertIsNot(None, index._root_node)
635
 
        internal_node_pre_clear = index._internal_node_cache.keys()
 
648
        internal_node_pre_clear = set(index._internal_node_cache)
636
649
        self.assertTrue(len(index._leaf_node_cache) > 0)
637
650
        index.clear_cache()
638
651
        # We don't touch _root_node or _internal_node_cache, both should be
644
657
        #       becuase without a 3-level index, we don't have any internal
645
658
        #       nodes cached.
646
659
        self.assertEqual(internal_node_pre_clear,
647
 
                         index._internal_node_cache.keys())
 
660
                         set(index._internal_node_cache))
648
661
        self.assertEqual(0, len(index._leaf_node_cache))
649
662
 
650
663
    def test_trivial_constructor(self):
651
 
        transport = get_transport('trace+' + self.get_url(''))
652
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
 
664
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
665
        index = btree_index.BTreeGraphIndex(t, 'index', None)
653
666
        # Checks the page size at load, but that isn't logged yet.
654
 
        self.assertEqual([], transport._activity)
 
667
        self.assertEqual([], t._activity)
655
668
 
656
669
    def test_with_size_constructor(self):
657
 
        transport = get_transport('trace+' + self.get_url(''))
658
 
        index = btree_index.BTreeGraphIndex(transport, 'index', 1)
 
670
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
671
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
659
672
        # Checks the page size at load, but that isn't logged yet.
660
 
        self.assertEqual([], transport._activity)
 
673
        self.assertEqual([], t._activity)
661
674
 
662
675
    def test_empty_key_count_no_size(self):
663
676
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
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)
 
677
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
678
        t.put_file('index', builder.finish())
 
679
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
680
        del t._activity[:]
 
681
        self.assertEqual([], t._activity)
669
682
        self.assertEqual(0, index.key_count())
670
683
        # The entire index should have been requested (as we generally have the
671
684
        # size available, and doing many small readvs is inappropriate).
672
685
        # We can't tell how much was actually read here, but - check the code.
673
 
        self.assertEqual([('get', 'index')], transport._activity)
 
686
        self.assertEqual([('get', 'index')], t._activity)
674
687
 
675
688
    def test_empty_key_count(self):
676
689
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
677
 
        transport = get_transport('trace+' + self.get_url(''))
678
 
        size = transport.put_file('index', builder.finish())
 
690
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
691
        size = t.put_file('index', builder.finish())
679
692
        self.assertEqual(72, size)
680
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
681
 
        del transport._activity[:]
682
 
        self.assertEqual([], transport._activity)
 
693
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
694
        del t._activity[:]
 
695
        self.assertEqual([], t._activity)
683
696
        self.assertEqual(0, index.key_count())
684
697
        # The entire index should have been read, as 4K > size
685
698
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
686
 
            transport._activity)
 
699
                         t._activity)
687
700
 
688
701
    def test_non_empty_key_count_2_2(self):
689
702
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
690
703
        nodes = self.make_nodes(35, 2, 2)
691
704
        for node in nodes:
692
705
            builder.add_node(*node)
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)
 
706
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
707
        size = t.put_file('index', builder.finish())
 
708
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
709
        del t._activity[:]
 
710
        self.assertEqual([], t._activity)
698
711
        self.assertEqual(70, index.key_count())
699
712
        # The entire index should have been read, as it is one page long.
700
713
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
701
 
            transport._activity)
702
 
        self.assertEqual(1173, size)
 
714
            t._activity)
 
715
        self.assertEqualApproxCompressed(1173, size)
703
716
 
704
717
    def test_with_offset_no_size(self):
705
718
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
722
735
 
723
736
    def test__read_nodes_no_size_one_page_reads_once(self):
724
737
        self.make_index(nodes=[(('key',), 'value', ())])
725
 
        trans = get_transport('trace+' + self.get_url())
 
738
        trans = transport.get_transport_from_url('trace+' + self.get_url())
726
739
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
727
740
        del trans._activity[:]
728
741
        nodes = dict(index._read_nodes([0]))
729
 
        self.assertEqual([0], nodes.keys())
 
742
        self.assertEqual({0}, set(nodes))
730
743
        node = nodes[0]
731
 
        self.assertEqual([('key',)], node.keys.keys())
 
744
        self.assertEqual([('key',)], node.all_keys())
732
745
        self.assertEqual([('get', 'index')], trans._activity)
733
746
 
734
747
    def test__read_nodes_no_size_multiple_pages(self):
736
749
        index.key_count()
737
750
        num_pages = index._row_offsets[-1]
738
751
        # Reopen with a traced transport and no size
739
 
        trans = get_transport('trace+' + self.get_url())
 
752
        trans = transport.get_transport_from_url('trace+' + self.get_url())
740
753
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
741
754
        del trans._activity[:]
742
755
        nodes = dict(index._read_nodes([0]))
743
 
        self.assertEqual(range(num_pages), nodes.keys())
 
756
        self.assertEqual(list(range(num_pages)), sorted(nodes))
744
757
 
745
758
    def test_2_levels_key_count_2_2(self):
746
759
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
747
760
        nodes = self.make_nodes(160, 2, 2)
748
761
        for node in nodes:
749
762
            builder.add_node(*node)
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)
 
763
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
764
        size = t.put_file('index', builder.finish())
 
765
        self.assertEqualApproxCompressed(17692, size)
 
766
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
767
        del t._activity[:]
 
768
        self.assertEqual([], t._activity)
756
769
        self.assertEqual(320, index.key_count())
757
770
        # The entire index should not have been read.
758
771
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
759
 
            transport._activity)
 
772
                         t._activity)
760
773
 
761
774
    def test_validate_one_page(self):
762
775
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
763
776
        nodes = self.make_nodes(45, 2, 2)
764
777
        for node in nodes:
765
778
            builder.add_node(*node)
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)
 
779
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
780
        size = t.put_file('index', builder.finish())
 
781
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
782
        del t._activity[:]
 
783
        self.assertEqual([], t._activity)
771
784
        index.validate()
772
785
        # The entire index should have been read linearly.
773
786
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
774
 
            transport._activity)
775
 
        self.assertEqual(1488, size)
 
787
                         t._activity)
 
788
        self.assertEqualApproxCompressed(1488, size)
776
789
 
777
790
    def test_validate_two_pages(self):
778
791
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
779
792
        nodes = self.make_nodes(80, 2, 2)
780
793
        for node in nodes:
781
794
            builder.add_node(*node)
782
 
        transport = get_transport('trace+' + self.get_url(''))
783
 
        size = transport.put_file('index', builder.finish())
 
795
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
796
        size = t.put_file('index', builder.finish())
784
797
        # Root page, 2 leaf pages
785
 
        self.assertEqual(9339, size)
786
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
787
 
        del transport._activity[:]
788
 
        self.assertEqual([], transport._activity)
 
798
        self.assertEqualApproxCompressed(9339, size)
 
799
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
800
        del t._activity[:]
 
801
        self.assertEqual([], t._activity)
789
802
        index.validate()
 
803
        rem = size - 8192 # Number of remaining bytes after second block
790
804
        # The entire index should have been read linearly.
791
 
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
792
 
            ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
793
 
            transport._activity)
 
805
        self.assertEqual(
 
806
            [('readv', 'index', [(0, 4096)], False, None),
 
807
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
 
808
            t._activity)
794
809
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
795
810
        # node and make validate find them.
796
811
 
797
812
    def test_eq_ne(self):
798
813
        # two indices are equal when constructed with the same parameters:
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))
 
814
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
 
815
        t2 = self.get_transport()
 
816
        self.assertTrue(
 
817
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
 
818
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
819
        self.assertTrue(
 
820
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
821
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
822
        self.assertFalse(
 
823
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
824
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
825
        self.assertFalse(
 
826
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
 
827
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
828
        self.assertFalse(
 
829
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
 
830
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
831
        self.assertFalse(
 
832
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
 
833
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
834
        self.assertFalse(
 
835
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
836
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
837
        self.assertTrue(
 
838
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
839
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
840
        self.assertTrue(
 
841
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
 
842
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
843
        self.assertTrue(
 
844
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
 
845
            btree_index.BTreeGraphIndex(t1, 'index', 20))
831
846
 
 
847
    def test_key_too_big(self):
 
848
        # the size that matters here is the _compressed_ size of the key, so we can't
 
849
        # do a simple character repeat.
 
850
        bigKey = ''.join(map(repr, range(btree_index._PAGE_SIZE)))
 
851
        self.assertRaises(errors.BadIndexKey,
 
852
                          self.make_index,
 
853
                          nodes=[((bigKey,), 'value', ())])
 
854
        
832
855
    def test_iter_all_only_root_no_size(self):
833
856
        self.make_index(nodes=[(('key',), 'value', ())])
834
 
        trans = get_transport('trace+' + self.get_url(''))
835
 
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
836
 
        del trans._activity[:]
 
857
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
858
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
859
        del t._activity[:]
837
860
        self.assertEqual([(('key',), 'value')],
838
861
                         [x[1:] for x in index.iter_all_entries()])
839
 
        self.assertEqual([('get', 'index')], trans._activity)
 
862
        self.assertEqual([('get', 'index')], t._activity)
840
863
 
841
864
    def test_iter_all_entries_reads(self):
842
865
        # iterating all entries reads the header, then does a linear
848
871
        nodes = self.make_nodes(10000, 2, 2)
849
872
        for node in nodes:
850
873
            builder.add_node(*node)
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
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
875
        size = t.put_file('index', builder.finish())
855
876
        page_size = btree_index._PAGE_SIZE
856
877
        del builder
857
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
858
 
        del transport._activity[:]
859
 
        self.assertEqual([], transport._activity)
 
878
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
879
        del t._activity[:]
 
880
        self.assertEqual([], t._activity)
860
881
        found_nodes = self.time(list, index.iter_all_entries())
861
882
        bare_nodes = []
862
883
        for node in found_nodes:
873
894
        # The entire index should have been read
874
895
        total_pages = sum(index._row_lengths)
875
896
        self.assertEqual(total_pages, index._row_offsets[-1])
876
 
        self.assertEqual(1303220, size)
 
897
        self.assertEqualApproxCompressed(1303220, size)
877
898
        # The start of the leaves
878
899
        first_byte = index._row_offsets[-2] * page_size
879
900
        readv_request = []
880
901
        for offset in range(first_byte, size, page_size):
881
902
            readv_request.append((offset, page_size))
882
903
        # The last page is truncated
883
 
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
 
904
        readv_request[-1] = (readv_request[-1][0], size % page_size)
884
905
        expected = [('readv', 'index', [(0, page_size)], False, None),
885
906
             ('readv',  'index', readv_request, False, None)]
886
 
        if expected != transport._activity:
 
907
        if expected != t._activity:
887
908
            self.assertEqualDiff(pprint.pformat(expected),
888
 
                                 pprint.pformat(transport._activity))
 
909
                                 pprint.pformat(t._activity))
889
910
 
890
911
    def _test_iter_entries_references_resolved(self):
891
912
        index = self.make_index(1, nodes=[
892
913
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
893
914
            (('ref', ), 'refdata', ([], ))])
894
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
895
 
            (index, ('ref', ), 'refdata', ((), ))]),
 
915
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),('ref',)),)),
 
916
            (index, ('ref', ), 'refdata', ((), ))},
896
917
            set(index.iter_entries([('name',), ('ref',)])))
897
918
 
898
919
    def test_iter_entries_references_2_refs_resolved(self):
903
924
        nodes = self.make_nodes(160, 2, 2)
904
925
        for node in nodes:
905
926
            builder.add_node(*node)
906
 
        transport = get_transport('trace+' + self.get_url(''))
907
 
        size = transport.put_file('index', builder.finish())
 
927
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
928
        size = t.put_file('index', builder.finish())
908
929
        del builder
909
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
910
 
        del transport._activity[:]
911
 
        self.assertEqual([], transport._activity)
 
930
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
931
        del t._activity[:]
 
932
        self.assertEqual([], t._activity)
912
933
        # search for one key
913
934
        found_nodes = list(index.iter_entries([nodes[30][0]]))
914
935
        bare_nodes = []
922
943
        # Should have read the root node, then one leaf page:
923
944
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
924
945
             ('readv',  'index', [(8192, 4096), ], False, None)],
925
 
            transport._activity)
 
946
            t._activity)
926
947
 
927
948
    def test_iter_key_prefix_1_element_key_None(self):
928
949
        index = self.make_index()
943
964
        index = self.make_index( nodes=[
944
965
            (('name', ), 'data', ()),
945
966
            (('ref', ), 'refdata', ())])
946
 
        self.assertEqual(set([(index, ('name', ), 'data'),
947
 
            (index, ('ref', ), 'refdata')]),
 
967
        self.assertEqual({(index, ('name', ), 'data'),
 
968
            (index, ('ref', ), 'refdata')},
948
969
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
949
970
 
950
971
    def test_iter_key_prefix_1_key_element_refs(self):
951
972
        index = self.make_index(1, nodes=[
952
973
            (('name', ), 'data', ([('ref', )], )),
953
974
            (('ref', ), 'refdata', ([], ))])
954
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
955
 
            (index, ('ref', ), 'refdata', ((), ))]),
 
975
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
976
            (index, ('ref', ), 'refdata', ((), ))},
956
977
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
957
978
 
958
979
    def test_iter_key_prefix_2_key_element_no_refs(self):
960
981
            (('name', 'fin1'), 'data', ()),
961
982
            (('name', 'fin2'), 'beta', ()),
962
983
            (('ref', 'erence'), 'refdata', ())])
963
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
964
 
            (index, ('ref', 'erence'), 'refdata')]),
 
984
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
985
            (index, ('ref', 'erence'), 'refdata')},
965
986
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
966
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
967
 
            (index, ('name', 'fin2'), 'beta')]),
 
987
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
988
            (index, ('name', 'fin2'), 'beta')},
968
989
            set(index.iter_entries_prefix([('name', None)])))
969
990
 
970
991
    def test_iter_key_prefix_2_key_element_refs(self):
972
993
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
973
994
            (('name', 'fin2'), 'beta', ([], )),
974
995
            (('ref', 'erence'), 'refdata', ([], ))])
975
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
976
 
            (index, ('ref', 'erence'), 'refdata', ((), ))]),
 
996
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
997
            (index, ('ref', 'erence'), 'refdata', ((), ))},
977
998
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
978
 
        self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
979
 
            (index, ('name', 'fin2'), 'beta', ((), ))]),
 
999
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
1000
            (index, ('name', 'fin2'), 'beta', ((), ))},
980
1001
            set(index.iter_entries_prefix([('name', None)])))
981
1002
 
982
1003
    # XXX: external_references tests are duplicated in test_index.  We
994
1015
        missing_key = ('missing',)
995
1016
        index = self.make_index(ref_lists=1, nodes=[
996
1017
            (('key',), 'value', ([missing_key],))])
997
 
        self.assertEqual(set([missing_key]), index.external_references(0))
 
1018
        self.assertEqual({missing_key}, index.external_references(0))
998
1019
 
999
1020
    def test_external_references_multiple_ref_lists(self):
1000
1021
        missing_key = ('missing',)
1001
1022
        index = self.make_index(ref_lists=2, nodes=[
1002
1023
            (('key',), 'value', ([], [missing_key]))])
1003
1024
        self.assertEqual(set([]), index.external_references(0))
1004
 
        self.assertEqual(set([missing_key]), index.external_references(1))
 
1025
        self.assertEqual({missing_key}, index.external_references(1))
1005
1026
 
1006
1027
    def test_external_references_two_records(self):
1007
1028
        index = self.make_index(ref_lists=1, nodes=[
1039
1060
        self.assertEqual({key2: ()}, parent_map)
1040
1061
        # we know that key3 is missing because we read the page that it would
1041
1062
        # otherwise be on
1042
 
        self.assertEqual(set([key3]), missing_keys)
 
1063
        self.assertEqual({key3}, missing_keys)
1043
1064
        self.assertEqual(set(), search_keys)
1044
1065
 
1045
1066
    def test__find_ancestors_one_parent_missing(self):
1059
1080
        # all we know is that key3 wasn't present on the page we were reading
1060
1081
        # but if you look, the last key is key2 which comes before key3, so we
1061
1082
        # don't know whether key3 would land on this page or not.
1062
 
        self.assertEqual(set([key3]), search_keys)
 
1083
        self.assertEqual({key3}, search_keys)
1063
1084
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
1064
1085
                                            missing_keys)
1065
1086
        # passing it back in, we are sure it is 'missing'
1066
1087
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1067
 
        self.assertEqual(set([key3]), missing_keys)
 
1088
        self.assertEqual({key3}, missing_keys)
1068
1089
        self.assertEqual(set([]), search_keys)
1069
1090
 
1070
1091
    def test__find_ancestors_dont_search_known(self):
1092
1113
        nodes = []
1093
1114
        ref_lists = ((),)
1094
1115
        rev_keys = []
1095
 
        for i in xrange(400):
 
1116
        for i in range(400):
1096
1117
            rev_id = '%s-%s-%s' % (email,
1097
1118
                                   osutils.compact_date(start_time + i),
1098
1119
                                   osutils.rand_chars(16))
1111
1132
        min_l2_key = l2.min_key
1112
1133
        max_l1_key = l1.max_key
1113
1134
        self.assertTrue(max_l1_key < min_l2_key)
1114
 
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
 
1135
        parents_min_l2_key = l2[min_l2_key][1][0]
1115
1136
        self.assertEqual((l1.max_key,), parents_min_l2_key)
1116
1137
        # Now, whatever key we select that would fall on the second page,
1117
1138
        # should give us all the parents until the page break
1126
1147
                                            missing_keys)
1127
1148
        self.assertEqual([min_l2_key, next_key], sorted(parent_map))
1128
1149
        self.assertEqual(set(), missing_keys)
1129
 
        self.assertEqual(set([max_l1_key]), search_keys)
 
1150
        self.assertEqual({max_l1_key}, search_keys)
1130
1151
        parent_map = {}
1131
1152
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1132
1153
                                            missing_keys)
1133
 
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
 
1154
        self.assertEqual(l1.all_keys(), sorted(parent_map))
1134
1155
        self.assertEqual(set(), missing_keys)
1135
1156
        self.assertEqual(set(), search_keys)
1136
1157
 
1142
1163
                                            missing_keys)
1143
1164
        self.assertEqual(set(), search_keys)
1144
1165
        self.assertEqual({}, parent_map)
1145
 
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
 
1166
        self.assertEqual({('one',), ('two',)}, missing_keys)
1146
1167
 
1147
1168
    def test_supports_unlimited_cache(self):
1148
1169
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
1152
1173
        for node in nodes:
1153
1174
            builder.add_node(*node)
1154
1175
        stream = builder.finish()
1155
 
        trans = get_transport(self.get_url())
 
1176
        trans = self.get_transport()
1156
1177
        size = trans.put_file('index', stream)
1157
1178
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1158
1179
        self.assertEqual(500, index.key_count())
1184
1205
 
1185
1206
class TestBTreeNodes(BTreeTestCase):
1186
1207
 
 
1208
    scenarios = btreeparser_scenarios()
 
1209
 
1187
1210
    def setUp(self):
1188
 
        BTreeTestCase.setUp(self)
 
1211
        super(TestBTreeNodes, self).setUp()
1189
1212
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1190
1213
 
1191
1214
    def test_LeafNode_1_0(self):
1204
1227
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
1205
1228
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
1206
1229
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1207
 
            }, node.keys)
 
1230
            }, dict(node.all_items()))
1208
1231
 
1209
1232
    def test_LeafNode_2_2(self):
1210
1233
        node_bytes = ("type=leaf\n"
1224
1247
            ('11', '33'): ('value:3',
1225
1248
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1226
1249
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1227
 
            }, node.keys)
 
1250
            }, dict(node.all_items()))
1228
1251
 
1229
1252
    def test_InternalNode_1(self):
1230
1253
        node_bytes = ("type=internal\n"
1265
1288
            ('11', '33'): ('value:3',
1266
1289
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1267
1290
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1268
 
            }, node.keys)
 
1291
            }, dict(node.all_items()))
1269
1292
 
1270
1293
    def assertFlattened(self, expected, key, value, refs):
1271
1294
        flat_key, flat_line = self.parse_btree._flatten_node(
1349
1372
        This doesn't actually create anything on disk, it just primes a
1350
1373
        BTreeGraphIndex with the recommended information.
1351
1374
        """
1352
 
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
1353
 
                                            'test-index', size=size)
 
1375
        index = btree_index.BTreeGraphIndex(
 
1376
            transport.get_transport_from_url('memory:///'),
 
1377
            'test-index', size=size)
1354
1378
        if recommended_pages is not None:
1355
1379
            index._recommended_pages = recommended_pages
1356
1380
        return index
1434
1458
 
1435
1459
    def test_read_all_from_root(self):
1436
1460
        index = self.make_index(4096*10, 20)
1437
 
        self.assertExpandOffsets(range(10), index, [0])
 
1461
        self.assertExpandOffsets(list(range(10)), index, [0])
1438
1462
 
1439
1463
    def test_read_all_when_cached(self):
1440
1464
        # We've read enough that we can grab all the rest in a single request