← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test__btree_serializer.py

  • Committer: John Arbash Meinel
  • Date: 2010-08-04 04:33:24 UTC
  • mto: This revision was merged to the branch mainline in revision 5390.
  • Revision ID: john@arbash-meinel.com-20100804043324-1ldc2v2w1kza7ox4
get into the nitty gritty for the _key_to_sha1 function.

It doesn't seem to help to op-out of the actual unhexlify call, so at least
that doesn't seem to be the performance overhead.
We get down to around 19.9us for _key_to_sha1 across 120 keys, which is
0.166us per key.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__btree_serializer.py
 
1
# Copyright (C) 2010 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
#
 
17
 
 
18
"""Direct tests of the btree serializer extension"""
 
19
 
 
20
import binascii
 
21
 
 
22
from bzrlib import tests
 
23
 
 
24
from bzrlib.tests.test_btree_index import compiled_btreeparser_feature
 
25
 
 
26
 
 
27
class TestBtreeSerializer(tests.TestCase):
 
28
 
 
29
    _test_needs_features = [compiled_btreeparser_feature]
 
30
 
 
31
    def setUp(self):
 
32
        super(TestBtreeSerializer, self).setUp()
 
33
        self.module = compiled_btreeparser_feature.module
 
34
 
 
35
 
 
36
class TestHexAndUnhex(TestBtreeSerializer):
 
37
 
 
38
    def assertHexlify(self, as_binary):
 
39
        self.assertEqual(binascii.hexlify(as_binary),
 
40
                         self.module._test_hexlify(as_binary))
 
41
 
 
42
    def assertUnhexlify(self, as_hex):
 
43
        ba_unhex = binascii.unhexlify(as_hex)
 
44
        mod_unhex = self.module._test_unhexlify(as_hex)
 
45
        if ba_unhex != mod_unhex:
 
46
            if mod_unhex is None:
 
47
                mod_hex = '<None>'
 
48
            else:
 
49
                mod_hex = binascii.hexlify(mod_unhex)
 
50
            self.fail('_test_unhexlify returned a different answer'
 
51
                      ' from binascii:\n    %s\n != %s'
 
52
                      % (binascii.hexlify(ba_unhex), mod_hex))
 
53
 
 
54
    def assertFailUnhexlify(self, as_hex):
 
55
        # Invalid hex content
 
56
        self.assertIs(None, self.module._test_unhexlify(as_hex))
 
57
 
 
58
    def test_to_hex(self):
 
59
        raw_bytes = ''.join(map(chr, range(256)))
 
60
        for i in range(0, 240, 20):
 
61
            self.assertHexlify(raw_bytes[i:i+20])
 
62
        self.assertHexlify(raw_bytes[240:]+raw_bytes[0:4])
 
63
 
 
64
    def test_from_hex(self):
 
65
        self.assertUnhexlify('0123456789abcdef0123456789abcdef01234567')
 
66
        self.assertUnhexlify('123456789abcdef0123456789abcdef012345678')
 
67
        self.assertUnhexlify('0123456789ABCDEF0123456789ABCDEF01234567')
 
68
        self.assertUnhexlify('123456789ABCDEF0123456789ABCDEF012345678')
 
69
        hex_chars = binascii.hexlify(''.join(map(chr, range(256))))
 
70
        for i in range(0, 480, 40):
 
71
            self.assertUnhexlify(hex_chars[i:i+40])
 
72
        self.assertUnhexlify(hex_chars[480:]+hex_chars[0:8])
 
73
 
 
74
    def test_from_invalid_hex(self):
 
75
        self.assertFailUnhexlify('123456789012345678901234567890123456789X')
 
76
        self.assertFailUnhexlify('12345678901234567890123456789012345678X9')
 
77
 
 
78
 
 
79
_hex_form = '123456789012345678901234567890abcdefabcd'
 
80
 
 
81
class Test_KeyToSha1(TestBtreeSerializer):
 
82
 
 
83
    def assertKeyToSha1(self, expected, key):
 
84
        if expected is None:
 
85
            expected_bin = None
 
86
        else:
 
87
            expected_bin = binascii.unhexlify(expected)
 
88
        actual_sha1 = self.module._test_key_to_sha1(key)
 
89
        if expected_bin != actual_sha1:
 
90
            actual_hex_sha1 = None
 
91
            if actual_sha1 is not None:
 
92
                actual_hex_sha1 = binascii.hexlify(actual_sha1)
 
93
            self.fail('_key_to_sha1 returned:\n    %s\n != %s'
 
94
                      % (actual_sha1, expected))
 
95
 
 
96
    def test_simple(self):
 
97
        self.assertKeyToSha1(_hex_form, ('sha1:' + _hex_form,))
 
98
 
 
99
    def test_invalid_not_tuple(self):
 
100
        self.assertKeyToSha1(None, _hex_form)
 
101
        self.assertKeyToSha1(None, 'sha1:' + _hex_form)
 
102
 
 
103
    def test_invalid_empty(self):
 
104
        self.assertKeyToSha1(None, ())
 
105
 
 
106
    def test_invalid_not_string(self):
 
107
        self.assertKeyToSha1(None, (None,))
 
108
        self.assertKeyToSha1(None, (list(_hex_form),))
 
109
 
 
110
    def test_invalid_not_sha1(self):
 
111
        self.assertKeyToSha1(None, (_hex_form,))
 
112
        self.assertKeyToSha1(None, ('sha2:' + _hex_form,))
 
113
 
 
114
    def test_invalid_not_hex(self):
 
115
        self.assertKeyToSha1(None,
 
116
            ('sha1:abcdefghijklmnopqrstuvwxyz12345678901234',))
 
117
 
 
118
 
 
119
class Test_Sha1ToKey(TestBtreeSerializer):
 
120
 
 
121
    def assertSha1ToKey(self, hex_sha1):
 
122
        bin_sha1 = binascii.unhexlify(hex_sha1)
 
123
        key = self.module._test_sha1_to_key(bin_sha1)
 
124
        self.assertEqual(('sha1:' + hex_sha1,), key)
 
125
 
 
126
    def test_simple(self):
 
127
        self.assertSha1ToKey(_hex_form)
 
128
 
 
129
 
 
130
_one_key_content = """type=leaf
 
131
sha1:123456789012345678901234567890abcdefabcd\x00\x001 2 3 4
 
132
"""
 
133
 
 
134
_large_offsets = """type=leaf
 
135
sha1:123456789012345678901234567890abcdefabcd\x00\x0012345678901 1234567890 0 1
 
136
sha1:abcd123456789012345678901234567890abcdef\x00\x002147483648 2147483647 0 1
 
137
sha1:abcdefabcd123456789012345678901234567890\x00\x004294967296 4294967295 4294967294 1
 
138
"""
 
139
 
 
140
_multi_key_content = """type=leaf
 
141
sha1:70c881d4a26984ddce795f6f71817c9cf4480e79\x00\x000 0 0 0
 
142
sha1:7e240de74fb1ed08fa08d38063f6a6a91462a815\x00\x001 1 1 1
 
143
sha1:86f7e437faa5a7fce15d1ddcb9eaeaea377667b8\x00\x002 2 2 2
 
144
sha1:da39a3ee5e6b4b0d3255bfef95601890afd80709\x00\x003 3 3 3
 
145
sha1:df51e37c269aa94d38f93e537bf6e2020b21406c\x00\x004 4 4 4
 
146
sha1:e0c9035898dd52fc65c41454cec9c4d2611bfb37\x00\x005 5 5 5
 
147
sha1:e93b4e3c464ffd51732fbd6ded717e9efda28aad\x00\x006 6 6 6
 
148
sha1:f7a9e24777ec23212c54d7a350bc5bea5477fdbb\x00\x007 7 7 7
 
149
"""
 
150
 
 
151
class TestGCCKHSHA1LeafNode(TestBtreeSerializer):
 
152
 
 
153
    def assertInvalid(self, bytes):
 
154
        """Ensure that we get a proper error when trying to parse invalid bytes.
 
155
 
 
156
        (mostly this is testing that bad input doesn't cause us to segfault)
 
157
        """
 
158
        self.assertRaises((ValueError, TypeError), 
 
159
                          self.module._parse_into_chk, bytes, 1, 0)
 
160
 
 
161
    def test_non_str(self):
 
162
        self.assertInvalid(u'type=leaf\n')
 
163
 
 
164
    def test_not_leaf(self):
 
165
        self.assertInvalid('type=internal\n')
 
166
 
 
167
    def test_empty_leaf(self):
 
168
        leaf = self.module._parse_into_chk('type=leaf\n', 1, 0)
 
169
        self.assertEqual(0, len(leaf))
 
170
        self.assertEqual([], leaf.all_items())
 
171
        self.assertEqual([], leaf.all_keys())
 
172
        # It should allow any key to be queried
 
173
        self.assertFalse(('key',) in leaf)
 
174
 
 
175
    def test_one_key_leaf(self):
 
176
        leaf = self.module._parse_into_chk(_one_key_content, 1, 0)
 
177
        self.assertEqual(1, len(leaf))
 
178
        sha_key = ('sha1:' + _hex_form,)
 
179
        self.assertEqual([sha_key], leaf.all_keys())
 
180
        self.assertEqual([(sha_key, ('1 2 3 4', ()))], leaf.all_items())
 
181
        self.assertTrue(sha_key in leaf)
 
182
 
 
183
    def test_large_offsets(self):
 
184
        leaf = self.module._parse_into_chk(_large_offsets, 1, 0)
 
185
        self.assertEqual(['12345678901 1234567890 0 1',
 
186
                          '2147483648 2147483647 0 1',
 
187
                          '4294967296 4294967295 4294967294 1',
 
188
                         ], [x[1][0] for x in leaf.all_items()])
 
189
 
 
190
    def test_many_key_leaf(self):
 
191
        leaf = self.module._parse_into_chk(_multi_key_content, 1, 0)
 
192
        self.assertEqual(8, len(leaf))
 
193
        all_keys = leaf.all_keys()
 
194
        self.assertEqual(8, len(leaf.all_keys()))
 
195
        for idx, key in enumerate(all_keys):
 
196
            self.assertEqual(str(idx), leaf[key][0].split()[0])