/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_serializer.py

  • Committer: Jelmer Vernooij
  • Date: 2020-04-05 19:11:34 UTC
  • mto: (7490.7.16 work)
  • mto: This revision was merged to the branch mainline in revision 7501.
  • Revision ID: jelmer@jelmer.uk-20200405191134-0aebh8ikiwygxma5
Populate the .gitignore file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/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
import bisect
 
22
 
 
23
from .. import tests
 
24
from ..sixish import (
 
25
    int2byte,
 
26
    )
 
27
 
 
28
from .test_btree_index import compiled_btreeparser_feature
 
29
 
 
30
 
 
31
class TestBtreeSerializer(tests.TestCase):
 
32
 
 
33
    _test_needs_features = [compiled_btreeparser_feature]
 
34
 
 
35
    @property
 
36
    def module(self):
 
37
        return compiled_btreeparser_feature.module
 
38
 
 
39
 
 
40
class TestHexAndUnhex(TestBtreeSerializer):
 
41
 
 
42
    def assertHexlify(self, as_binary):
 
43
        self.assertEqual(binascii.hexlify(as_binary),
 
44
                         self.module._py_hexlify(as_binary))
 
45
 
 
46
    def assertUnhexlify(self, as_hex):
 
47
        ba_unhex = binascii.unhexlify(as_hex)
 
48
        mod_unhex = self.module._py_unhexlify(as_hex)
 
49
        if ba_unhex != mod_unhex:
 
50
            if mod_unhex is None:
 
51
                mod_hex = b'<None>'
 
52
            else:
 
53
                mod_hex = binascii.hexlify(mod_unhex)
 
54
            self.fail('_py_unhexlify returned a different answer'
 
55
                      ' from binascii:\n    %r\n != %r'
 
56
                      % (binascii.hexlify(ba_unhex), mod_hex))
 
57
 
 
58
    def assertFailUnhexlify(self, as_hex):
 
59
        # Invalid hex content
 
60
        self.assertIs(None, self.module._py_unhexlify(as_hex))
 
61
 
 
62
    def test_to_hex(self):
 
63
        raw_bytes = b''.join(map(int2byte, range(256)))
 
64
        for i in range(0, 240, 20):
 
65
            self.assertHexlify(raw_bytes[i:i + 20])
 
66
        self.assertHexlify(raw_bytes[240:] + raw_bytes[0:4])
 
67
 
 
68
    def test_from_hex(self):
 
69
        self.assertUnhexlify(b'0123456789abcdef0123456789abcdef01234567')
 
70
        self.assertUnhexlify(b'123456789abcdef0123456789abcdef012345678')
 
71
        self.assertUnhexlify(b'0123456789ABCDEF0123456789ABCDEF01234567')
 
72
        self.assertUnhexlify(b'123456789ABCDEF0123456789ABCDEF012345678')
 
73
        hex_chars = binascii.hexlify(b''.join(map(int2byte, range(256))))
 
74
        for i in range(0, 480, 40):
 
75
            self.assertUnhexlify(hex_chars[i:i + 40])
 
76
        self.assertUnhexlify(hex_chars[480:] + hex_chars[0:8])
 
77
 
 
78
    def test_from_invalid_hex(self):
 
79
        self.assertFailUnhexlify(b'123456789012345678901234567890123456789X')
 
80
        self.assertFailUnhexlify(b'12345678901234567890123456789012345678X9')
 
81
 
 
82
    def test_bad_argument(self):
 
83
        self.assertRaises(ValueError, self.module._py_unhexlify, u'1a')
 
84
        self.assertRaises(ValueError, self.module._py_unhexlify, b'1b')
 
85
 
 
86
 
 
87
_hex_form = b'123456789012345678901234567890abcdefabcd'
 
88
 
 
89
 
 
90
class Test_KeyToSha1(TestBtreeSerializer):
 
91
 
 
92
    def assertKeyToSha1(self, expected, key):
 
93
        if expected is None:
 
94
            expected_bin = None
 
95
        else:
 
96
            expected_bin = binascii.unhexlify(expected)
 
97
        actual_sha1 = self.module._py_key_to_sha1(key)
 
98
        if expected_bin != actual_sha1:
 
99
            actual_hex_sha1 = None
 
100
            if actual_sha1 is not None:
 
101
                actual_hex_sha1 = binascii.hexlify(actual_sha1)
 
102
            self.fail('_key_to_sha1 returned:\n    %s\n != %s'
 
103
                      % (actual_sha1, expected))
 
104
 
 
105
    def test_simple(self):
 
106
        self.assertKeyToSha1(_hex_form, (b'sha1:' + _hex_form,))
 
107
 
 
108
    def test_invalid_not_tuple(self):
 
109
        self.assertKeyToSha1(None, _hex_form)
 
110
        self.assertKeyToSha1(None, b'sha1:' + _hex_form)
 
111
 
 
112
    def test_invalid_empty(self):
 
113
        self.assertKeyToSha1(None, ())
 
114
 
 
115
    def test_invalid_not_string(self):
 
116
        self.assertKeyToSha1(None, (None,))
 
117
        self.assertKeyToSha1(None, (list(_hex_form),))
 
118
 
 
119
    def test_invalid_not_sha1(self):
 
120
        self.assertKeyToSha1(None, (_hex_form,))
 
121
        self.assertKeyToSha1(None, (b'sha2:' + _hex_form,))
 
122
 
 
123
    def test_invalid_not_hex(self):
 
124
        self.assertKeyToSha1(None,
 
125
                             (b'sha1:abcdefghijklmnopqrstuvwxyz12345678901234',))
 
126
 
 
127
 
 
128
class Test_Sha1ToKey(TestBtreeSerializer):
 
129
 
 
130
    def assertSha1ToKey(self, hex_sha1):
 
131
        bin_sha1 = binascii.unhexlify(hex_sha1)
 
132
        key = self.module._py_sha1_to_key(bin_sha1)
 
133
        self.assertEqual((b'sha1:' + hex_sha1,), key)
 
134
 
 
135
    def test_simple(self):
 
136
        self.assertSha1ToKey(_hex_form)
 
137
 
 
138
 
 
139
_one_key_content = b"""type=leaf
 
140
sha1:123456789012345678901234567890abcdefabcd\x00\x001 2 3 4
 
141
"""
 
142
 
 
143
_large_offsets = b"""type=leaf
 
144
sha1:123456789012345678901234567890abcdefabcd\x00\x0012345678901 1234567890 0 1
 
145
sha1:abcd123456789012345678901234567890abcdef\x00\x002147483648 2147483647 0 1
 
146
sha1:abcdefabcd123456789012345678901234567890\x00\x004294967296 4294967295 4294967294 1
 
147
"""
 
148
 
 
149
_multi_key_content = b"""type=leaf
 
150
sha1:c80c881d4a26984ddce795f6f71817c9cf4480e7\x00\x000 0 0 0
 
151
sha1:c86f7e437faa5a7fce15d1ddcb9eaeaea377667b\x00\x001 1 1 1
 
152
sha1:c8e240de74fb1ed08fa08d38063f6a6a91462a81\x00\x002 2 2 2
 
153
sha1:cda39a3ee5e6b4b0d3255bfef95601890afd8070\x00\x003 3 3 3
 
154
sha1:cdf51e37c269aa94d38f93e537bf6e2020b21406\x00\x004 4 4 4
 
155
sha1:ce0c9035898dd52fc65c41454cec9c4d2611bfb3\x00\x005 5 5 5
 
156
sha1:ce93b4e3c464ffd51732fbd6ded717e9efda28aa\x00\x006 6 6 6
 
157
sha1:cf7a9e24777ec23212c54d7a350bc5bea5477fdb\x00\x007 7 7 7
 
158
"""
 
159
 
 
160
_multi_key_same_offset = b"""type=leaf
 
161
sha1:080c881d4a26984ddce795f6f71817c9cf4480e7\x00\x000 0 0 0
 
162
sha1:c86f7e437faa5a7fce15d1ddcb9eaeaea377667b\x00\x001 1 1 1
 
163
sha1:cd0c9035898dd52fc65c41454cec9c4d2611bfb3\x00\x002 2 2 2
 
164
sha1:cda39a3ee5e6b4b0d3255bfef95601890afd8070\x00\x003 3 3 3
 
165
sha1:cde240de74fb1ed08fa08d38063f6a6a91462a81\x00\x004 4 4 4
 
166
sha1:cdf51e37c269aa94d38f93e537bf6e2020b21406\x00\x005 5 5 5
 
167
sha1:ce7a9e24777ec23212c54d7a350bc5bea5477fdb\x00\x006 6 6 6
 
168
sha1:ce93b4e3c464ffd51732fbd6ded717e9efda28aa\x00\x007 7 7 7
 
169
"""
 
170
 
 
171
_common_32_bits = b"""type=leaf
 
172
sha1:123456784a26984ddce795f6f71817c9cf4480e7\x00\x000 0 0 0
 
173
sha1:1234567874fb1ed08fa08d38063f6a6a91462a81\x00\x001 1 1 1
 
174
sha1:12345678777ec23212c54d7a350bc5bea5477fdb\x00\x002 2 2 2
 
175
sha1:123456787faa5a7fce15d1ddcb9eaeaea377667b\x00\x003 3 3 3
 
176
sha1:12345678898dd52fc65c41454cec9c4d2611bfb3\x00\x004 4 4 4
 
177
sha1:12345678c269aa94d38f93e537bf6e2020b21406\x00\x005 5 5 5
 
178
sha1:12345678c464ffd51732fbd6ded717e9efda28aa\x00\x006 6 6 6
 
179
sha1:12345678e5e6b4b0d3255bfef95601890afd8070\x00\x007 7 7 7
 
180
"""
 
181
 
 
182
 
 
183
class TestGCCKHSHA1LeafNode(TestBtreeSerializer):
 
184
 
 
185
    def assertInvalid(self, data):
 
186
        """Ensure that we get a proper error when trying to parse invalid bytes.
 
187
 
 
188
        (mostly this is testing that bad input doesn't cause us to segfault)
 
189
        """
 
190
        self.assertRaises(
 
191
            (ValueError, TypeError), self.module._parse_into_chk, data, 1, 0)
 
192
 
 
193
    def test_non_bytes(self):
 
194
        self.assertInvalid(u'type=leaf\n')
 
195
 
 
196
    def test_not_leaf(self):
 
197
        self.assertInvalid(b'type=internal\n')
 
198
 
 
199
    def test_empty_leaf(self):
 
200
        leaf = self.module._parse_into_chk(b'type=leaf\n', 1, 0)
 
201
        self.assertEqual(0, len(leaf))
 
202
        self.assertEqual([], leaf.all_items())
 
203
        self.assertEqual([], leaf.all_keys())
 
204
        # It should allow any key to be queried
 
205
        self.assertFalse(('key',) in leaf)
 
206
 
 
207
    def test_one_key_leaf(self):
 
208
        leaf = self.module._parse_into_chk(_one_key_content, 1, 0)
 
209
        self.assertEqual(1, len(leaf))
 
210
        sha_key = (b'sha1:' + _hex_form,)
 
211
        self.assertEqual([sha_key], leaf.all_keys())
 
212
        self.assertEqual([(sha_key, (b'1 2 3 4', ()))], leaf.all_items())
 
213
        self.assertTrue(sha_key in leaf)
 
214
 
 
215
    def test_large_offsets(self):
 
216
        leaf = self.module._parse_into_chk(_large_offsets, 1, 0)
 
217
        self.assertEqual([b'12345678901 1234567890 0 1',
 
218
                          b'2147483648 2147483647 0 1',
 
219
                          b'4294967296 4294967295 4294967294 1',
 
220
                          ], [x[1][0] for x in leaf.all_items()])
 
221
 
 
222
    def test_many_key_leaf(self):
 
223
        leaf = self.module._parse_into_chk(_multi_key_content, 1, 0)
 
224
        self.assertEqual(8, len(leaf))
 
225
        all_keys = leaf.all_keys()
 
226
        self.assertEqual(8, len(leaf.all_keys()))
 
227
        for idx, key in enumerate(all_keys):
 
228
            self.assertEqual(b'%d' % idx, leaf[key][0].split()[0])
 
229
 
 
230
    def test_common_shift(self):
 
231
        # The keys were deliberately chosen so that the first 5 bits all
 
232
        # overlapped, it also happens that a later bit overlaps
 
233
        # Note that by 'overlap' we mean that given bit is either on in all
 
234
        # keys, or off in all keys
 
235
        leaf = self.module._parse_into_chk(_multi_key_content, 1, 0)
 
236
        self.assertEqual(19, leaf.common_shift)
 
237
        # The interesting byte for each key is
 
238
        # (defined as the 8-bits that come after the common prefix)
 
239
        lst = [1, 13, 28, 180, 190, 193, 210, 239]
 
240
        offsets = leaf._get_offsets()
 
241
        self.assertEqual([bisect.bisect_left(lst, x) for x in range(0, 257)],
 
242
                         offsets)
 
243
        for idx, val in enumerate(lst):
 
244
            self.assertEqual(idx, offsets[val])
 
245
        for idx, key in enumerate(leaf.all_keys()):
 
246
            self.assertEqual(b'%d' % idx, leaf[key][0].split()[0])
 
247
 
 
248
    def test_multi_key_same_offset(self):
 
249
        # there is no common prefix, though there are some common bits
 
250
        leaf = self.module._parse_into_chk(_multi_key_same_offset, 1, 0)
 
251
        self.assertEqual(24, leaf.common_shift)
 
252
        offsets = leaf._get_offsets()
 
253
        # The interesting byte is just the first 8-bits of the key
 
254
        lst = [8, 200, 205, 205, 205, 205, 206, 206]
 
255
        self.assertEqual([bisect.bisect_left(lst, x) for x in range(0, 257)],
 
256
                         offsets)
 
257
        for val in lst:
 
258
            self.assertEqual(lst.index(val), offsets[val])
 
259
        for idx, key in enumerate(leaf.all_keys()):
 
260
            self.assertEqual(b'%d' % idx, leaf[key][0].split()[0])
 
261
 
 
262
    def test_all_common_prefix(self):
 
263
        # The first 32 bits of all hashes are the same. This is going to be
 
264
        # pretty much impossible, but I don't want to fail because of this
 
265
        leaf = self.module._parse_into_chk(_common_32_bits, 1, 0)
 
266
        self.assertEqual(0, leaf.common_shift)
 
267
        lst = [0x78] * 8
 
268
        offsets = leaf._get_offsets()
 
269
        self.assertEqual([bisect.bisect_left(lst, x) for x in range(0, 257)],
 
270
                         offsets)
 
271
        for val in lst:
 
272
            self.assertEqual(lst.index(val), offsets[val])
 
273
        for idx, key in enumerate(leaf.all_keys()):
 
274
            self.assertEqual(b'%d' % idx, leaf[key][0].split()[0])
 
275
 
 
276
    def test_many_entries(self):
 
277
        # Again, this is almost impossible, but we should still work
 
278
        # It would be hard to fit more that 120 entries in a 4k page, much less
 
279
        # more than 256 of them. but hey, weird stuff happens sometimes
 
280
        lines = [b'type=leaf\n']
 
281
        for i in range(500):
 
282
            key_str = b'sha1:%04x%s' % (i, _hex_form[:36])
 
283
            key = (key_str,)
 
284
            lines.append(b'%s\0\0%d %d %d %d\n' % (key_str, i, i, i, i))
 
285
        data = b''.join(lines)
 
286
        leaf = self.module._parse_into_chk(data, 1, 0)
 
287
        self.assertEqual(24 - 7, leaf.common_shift)
 
288
        offsets = leaf._get_offsets()
 
289
        # This is the interesting bits for each entry
 
290
        lst = [x // 2 for x in range(500)]
 
291
        expected_offsets = [x * 2 for x in range(128)] + [255] * 129
 
292
        self.assertEqual(expected_offsets, offsets)
 
293
        # We truncate because offsets is an unsigned char. So the bisection
 
294
        # will just say 'greater than the last one' for all the rest
 
295
        lst = lst[:255]
 
296
        self.assertEqual([bisect.bisect_left(lst, x) for x in range(0, 257)],
 
297
                         offsets)
 
298
        for val in lst:
 
299
            self.assertEqual(lst.index(val), offsets[val])
 
300
        for idx, key in enumerate(leaf.all_keys()):
 
301
            self.assertEqual(b'%d' % idx, leaf[key][0].split()[0])
 
302
 
 
303
    def test__sizeof__(self):
 
304
        # We can't use the exact numbers because of platform variations, etc.
 
305
        # But what we really care about is that it does get bigger with more
 
306
        # content.
 
307
        leaf0 = self.module._parse_into_chk(b'type=leaf\n', 1, 0)
 
308
        leaf1 = self.module._parse_into_chk(_one_key_content, 1, 0)
 
309
        leafN = self.module._parse_into_chk(_multi_key_content, 1, 0)
 
310
        sizeof_1 = leaf1.__sizeof__() - leaf0.__sizeof__()
 
311
        self.assertTrue(sizeof_1 > 0)
 
312
        sizeof_N = leafN.__sizeof__() - leaf0.__sizeof__()
 
313
        self.assertEqual(sizeof_1 * len(leafN), sizeof_N)