32
32
from bzrlib.tests import (
33
33
TestCaseWithTransport,
36
split_suite_by_condition,
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))
36
from bzrlib.tests import (
41
load_tests = scenarios.load_tests_apply_scenarios
44
def btreeparser_scenarios():
44
45
import bzrlib._btree_serializer_py as py_module
45
46
scenarios = [('python', {'parse_btree': py_module})]
46
47
if compiled_btreeparser_feature.available():
47
scenarios.append(('C', {'parse_btree':
48
compiled_btreeparser_feature.module}))
49
return multiply_tests(node_tests, scenarios, others)
52
compiled_btreeparser_feature = tests.ModuleAvailableFeature(
53
'bzrlib._btree_serializer_pyx')
48
scenarios.append(('C',
49
{'parse_btree': compiled_btreeparser_feature.module}))
53
compiled_btreeparser_feature = features.ModuleAvailableFeature(
54
'bzrlib._btree_serializer_pyx')
56
57
class BTreeTestCase(TestCaseWithTransport):
61
TestCaseWithTransport.setUp(self)
62
super(BTreeTestCase, self).setUp()
62
63
self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
64
65
def make_nodes(self, count, key_elements, reference_lists):
102
103
self.overrideAttr(btree_index, '_PAGE_SIZE')
103
104
btree_index._PAGE_SIZE = 2048
106
def assertEqualsApproxCompressed(self, expected, actual, slop=6):
107
"""Check a count of compressed bytes is approximately as expected
109
Relying on compressed length being stable even with fixed inputs is
110
slightly bogus, but zlib is stable enough that this mostly works.
112
if not expected - slop < actual < expected + slop:
113
self.fail("Expected around %d bytes compressed but got %d" %
106
117
class TestBTreeBuilder(BTreeTestCase):
607
618
for key, value, references in nodes:
608
619
builder.add_node(key, value, references)
609
620
stream = builder.finish()
610
trans = transport.get_transport('trace+' + self.get_url())
621
trans = transport.get_transport_from_url('trace+' + self.get_url())
611
622
size = trans.put_file('index', stream)
612
623
return btree_index.BTreeGraphIndex(trans, 'index', size)
648
659
self.assertEqual(0, len(index._leaf_node_cache))
650
661
def test_trivial_constructor(self):
651
t = transport.get_transport('trace+' + self.get_url(''))
662
t = transport.get_transport_from_url('trace+' + self.get_url(''))
652
663
index = btree_index.BTreeGraphIndex(t, 'index', None)
653
664
# Checks the page size at load, but that isn't logged yet.
654
665
self.assertEqual([], t._activity)
656
667
def test_with_size_constructor(self):
657
t = transport.get_transport('trace+' + self.get_url(''))
668
t = transport.get_transport_from_url('trace+' + self.get_url(''))
658
669
index = btree_index.BTreeGraphIndex(t, 'index', 1)
659
670
# Checks the page size at load, but that isn't logged yet.
660
671
self.assertEqual([], t._activity)
662
673
def test_empty_key_count_no_size(self):
663
674
builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
664
t = transport.get_transport('trace+' + self.get_url(''))
675
t = transport.get_transport_from_url('trace+' + self.get_url(''))
665
676
t.put_file('index', builder.finish())
666
677
index = btree_index.BTreeGraphIndex(t, 'index', None)
667
678
del t._activity[:]
675
686
def test_empty_key_count(self):
676
687
builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
677
t = transport.get_transport('trace+' + self.get_url(''))
688
t = transport.get_transport_from_url('trace+' + self.get_url(''))
678
689
size = t.put_file('index', builder.finish())
679
690
self.assertEqual(72, size)
680
691
index = btree_index.BTreeGraphIndex(t, 'index', size)
690
701
nodes = self.make_nodes(35, 2, 2)
691
702
for node in nodes:
692
703
builder.add_node(*node)
693
t = transport.get_transport('trace+' + self.get_url(''))
704
t = transport.get_transport_from_url('trace+' + self.get_url(''))
694
705
size = t.put_file('index', builder.finish())
695
706
index = btree_index.BTreeGraphIndex(t, 'index', size)
696
707
del t._activity[:]
699
710
# The entire index should have been read, as it is one page long.
700
711
self.assertEqual([('readv', 'index', [(0, size)], False, None)],
702
self.assertEqual(1173, size)
713
self.assertEqualsApproxCompressed(1173, size)
704
715
def test_with_offset_no_size(self):
705
716
index = self.make_index_with_offset(key_elements=1, ref_lists=1,
723
734
def test__read_nodes_no_size_one_page_reads_once(self):
724
735
self.make_index(nodes=[(('key',), 'value', ())])
725
trans = transport.get_transport('trace+' + self.get_url())
736
trans = transport.get_transport_from_url('trace+' + self.get_url())
726
737
index = btree_index.BTreeGraphIndex(trans, 'index', None)
727
738
del trans._activity[:]
728
739
nodes = dict(index._read_nodes([0]))
736
747
index.key_count()
737
748
num_pages = index._row_offsets[-1]
738
749
# Reopen with a traced transport and no size
739
trans = transport.get_transport('trace+' + self.get_url())
750
trans = transport.get_transport_from_url('trace+' + self.get_url())
740
751
index = btree_index.BTreeGraphIndex(trans, 'index', None)
741
752
del trans._activity[:]
742
753
nodes = dict(index._read_nodes([0]))
747
758
nodes = self.make_nodes(160, 2, 2)
748
759
for node in nodes:
749
760
builder.add_node(*node)
750
t = transport.get_transport('trace+' + self.get_url(''))
761
t = transport.get_transport_from_url('trace+' + self.get_url(''))
751
762
size = t.put_file('index', builder.finish())
752
self.assertEqual(17692, size)
763
self.assertEqualsApproxCompressed(17692, size)
753
764
index = btree_index.BTreeGraphIndex(t, 'index', size)
754
765
del t._activity[:]
755
766
self.assertEqual([], t._activity)
763
774
nodes = self.make_nodes(45, 2, 2)
764
775
for node in nodes:
765
776
builder.add_node(*node)
766
t = transport.get_transport('trace+' + self.get_url(''))
777
t = transport.get_transport_from_url('trace+' + self.get_url(''))
767
778
size = t.put_file('index', builder.finish())
768
779
index = btree_index.BTreeGraphIndex(t, 'index', size)
769
780
del t._activity[:]
772
783
# The entire index should have been read linearly.
773
784
self.assertEqual([('readv', 'index', [(0, size)], False, None)],
775
self.assertEqual(1488, size)
786
self.assertEqualsApproxCompressed(1488, size)
777
788
def test_validate_two_pages(self):
778
789
builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
779
790
nodes = self.make_nodes(80, 2, 2)
780
791
for node in nodes:
781
792
builder.add_node(*node)
782
t = transport.get_transport('trace+' + self.get_url(''))
793
t = transport.get_transport_from_url('trace+' + self.get_url(''))
783
794
size = t.put_file('index', builder.finish())
784
795
# Root page, 2 leaf pages
785
self.assertEqual(9339, size)
796
self.assertEqualsApproxCompressed(9339, size)
786
797
index = btree_index.BTreeGraphIndex(t, 'index', size)
787
798
del t._activity[:]
788
799
self.assertEqual([], t._activity)
801
rem = size - 8192 # Number of remaining bytes after second block
790
802
# The entire index should have been read linearly.
791
803
self.assertEqual(
792
804
[('readv', 'index', [(0, 4096)], False, None),
793
('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
805
('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
795
807
# XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
796
808
# node and make validate find them.
798
810
def test_eq_ne(self):
799
811
# two indices are equal when constructed with the same parameters:
800
t1 = transport.get_transport('trace+' + self.get_url(''))
801
t2 = transport.get_transport(self.get_url(''))
812
t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
813
t2 = self.get_transport()
803
815
btree_index.BTreeGraphIndex(t1, 'index', None) ==
804
816
btree_index.BTreeGraphIndex(t1, 'index', None))
830
842
btree_index.BTreeGraphIndex(t1, 'index', 10) !=
831
843
btree_index.BTreeGraphIndex(t1, 'index', 20))
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,
851
nodes=[((bigKey,), 'value', ())])
833
853
def test_iter_all_only_root_no_size(self):
834
854
self.make_index(nodes=[(('key',), 'value', ())])
835
t = transport.get_transport('trace+' + self.get_url(''))
855
t = transport.get_transport_from_url('trace+' + self.get_url(''))
836
856
index = btree_index.BTreeGraphIndex(t, 'index', None)
837
857
del t._activity[:]
838
858
self.assertEqual([(('key',), 'value')],
849
869
nodes = self.make_nodes(10000, 2, 2)
850
870
for node in nodes:
851
871
builder.add_node(*node)
852
t = transport.get_transport('trace+' + self.get_url(''))
872
t = transport.get_transport_from_url('trace+' + self.get_url(''))
853
873
size = t.put_file('index', builder.finish())
854
self.assertEqual(1303220, size, 'number of expected bytes in the'
856
874
page_size = btree_index._PAGE_SIZE
858
876
index = btree_index.BTreeGraphIndex(t, 'index', size)
874
892
# The entire index should have been read
875
893
total_pages = sum(index._row_lengths)
876
894
self.assertEqual(total_pages, index._row_offsets[-1])
877
self.assertEqual(1303220, size)
895
self.assertEqualsApproxCompressed(1303220, size)
878
896
# The start of the leaves
879
897
first_byte = index._row_offsets[-2] * page_size
880
898
readv_request = []
881
899
for offset in range(first_byte, size, page_size):
882
900
readv_request.append((offset, page_size))
883
901
# The last page is truncated
884
readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
902
readv_request[-1] = (readv_request[-1][0], size % page_size)
885
903
expected = [('readv', 'index', [(0, page_size)], False, None),
886
904
('readv', 'index', readv_request, False, None)]
887
905
if expected != t._activity:
888
906
self.assertEqualDiff(pprint.pformat(expected),
889
pprint.pformat(transport._activity))
907
pprint.pformat(t._activity))
891
909
def _test_iter_entries_references_resolved(self):
892
910
index = self.make_index(1, nodes=[
904
922
nodes = self.make_nodes(160, 2, 2)
905
923
for node in nodes:
906
924
builder.add_node(*node)
907
t = transport.get_transport('trace+' + self.get_url(''))
925
t = transport.get_transport_from_url('trace+' + self.get_url(''))
908
926
size = t.put_file('index', builder.finish())
910
928
index = btree_index.BTreeGraphIndex(t, 'index', size)
1153
1171
for node in nodes:
1154
1172
builder.add_node(*node)
1155
1173
stream = builder.finish()
1156
trans = transport.get_transport(self.get_url())
1174
trans = self.get_transport()
1157
1175
size = trans.put_file('index', stream)
1158
1176
index = btree_index.BTreeGraphIndex(trans, 'index', size)
1159
1177
self.assertEqual(500, index.key_count())
1186
1204
class TestBTreeNodes(BTreeTestCase):
1206
scenarios = btreeparser_scenarios()
1188
1208
def setUp(self):
1189
BTreeTestCase.setUp(self)
1209
super(TestBTreeNodes, self).setUp()
1190
1210
self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1192
1212
def test_LeafNode_1_0(self):
1351
1371
BTreeGraphIndex with the recommended information.
1353
1373
index = btree_index.BTreeGraphIndex(
1354
transport.get_transport('memory:///'), 'test-index', size=size)
1374
transport.get_transport_from_url('memory:///'),
1375
'test-index', size=size)
1355
1376
if recommended_pages is not None:
1356
1377
index._recommended_pages = recommended_pages