← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test__simple_set.py

(jelmer) Add RepositoryFormat.is_deprecated(). (Jelmer Vernooij)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__simple_set.py
 
1
# Copyright (C) 2009, 2010, 2011 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
"""Tests for the StaticTupleInterned type."""
 
18
 
 
19
import sys
 
20
 
 
21
from bzrlib import (
 
22
    tests,
 
23
    )
 
24
 
 
25
try:
 
26
    from bzrlib import _simple_set_pyx
 
27
except ImportError:
 
28
    _simple_set_pyx = None
 
29
 
 
30
 
 
31
class _Hashable(object):
 
32
    """A simple object which has a fixed hash value.
 
33
 
 
34
    We could have used an 'int', but it turns out that Int objects don't
 
35
    implement tp_richcompare...
 
36
    """
 
37
 
 
38
    def __init__(self, the_hash):
 
39
        self.hash = the_hash
 
40
 
 
41
    def __hash__(self):
 
42
        return self.hash
 
43
 
 
44
    def __eq__(self, other):
 
45
        if not isinstance(other, _Hashable):
 
46
            return NotImplemented
 
47
        return other.hash == self.hash
 
48
 
 
49
 
 
50
class _BadSecondHash(_Hashable):
 
51
 
 
52
    def __init__(self, the_hash):
 
53
        _Hashable.__init__(self, the_hash)
 
54
        self._first = True
 
55
 
 
56
    def __hash__(self):
 
57
        if self._first:
 
58
            self._first = False
 
59
            return self.hash
 
60
        else:
 
61
            raise ValueError('I can only be hashed once.')
 
62
 
 
63
 
 
64
class _BadCompare(_Hashable):
 
65
 
 
66
    def __eq__(self, other):
 
67
        raise RuntimeError('I refuse to play nice')
 
68
 
 
69
 
 
70
class _NoImplementCompare(_Hashable):
 
71
 
 
72
    def __eq__(self, other):
 
73
        return NotImplemented
 
74
 
 
75
 
 
76
# Even though this is an extension, we don't permute the tests for a python
 
77
# version. As the plain python version is just a dict or set
 
78
compiled_simpleset_feature = tests.ModuleAvailableFeature(
 
79
                                'bzrlib._simple_set_pyx')
 
80
 
 
81
 
 
82
class TestSimpleSet(tests.TestCase):
 
83
 
 
84
    _test_needs_features = [compiled_simpleset_feature]
 
85
    module = _simple_set_pyx
 
86
 
 
87
    def assertIn(self, obj, container):
 
88
        self.assertTrue(obj in container,
 
89
            '%s not found in %s' % (obj, container))
 
90
 
 
91
    def assertNotIn(self, obj, container):
 
92
        self.assertTrue(obj not in container,
 
93
            'We found %s in %s' % (obj, container))
 
94
 
 
95
    def assertFillState(self, used, fill, mask, obj):
 
96
        self.assertEqual((used, fill, mask), (obj.used, obj.fill, obj.mask))
 
97
 
 
98
    def assertLookup(self, offset, value, obj, key):
 
99
        self.assertEqual((offset, value), obj._test_lookup(key))
 
100
 
 
101
    def assertRefcount(self, count, obj):
 
102
        """Assert that the refcount for obj is what we expect.
 
103
 
 
104
        Note that this automatically adjusts for the fact that calling
 
105
        assertRefcount actually creates a new pointer, as does calling
 
106
        sys.getrefcount. So pass the expected value *before* the call.
 
107
        """
 
108
        # I'm not sure why the offset is 3, but I've check that in the caller,
 
109
        # an offset of 1 works, which is expected. Not sure why assertRefcount
 
110
        # is incrementing/decrementing 2 times
 
111
        self.assertEqual(count, sys.getrefcount(obj)-3)
 
112
 
 
113
    def test_initial(self):
 
114
        obj = self.module.SimpleSet()
 
115
        self.assertEqual(0, len(obj))
 
116
        st = ('foo', 'bar')
 
117
        self.assertFillState(0, 0, 0x3ff, obj)
 
118
 
 
119
    def test__lookup(self):
 
120
        # These are carefully chosen integers to force hash collisions in the
 
121
        # algorithm, based on the initial set size of 1024
 
122
        obj = self.module.SimpleSet()
 
123
        self.assertLookup(643, '<null>', obj, _Hashable(643))
 
124
        self.assertLookup(643, '<null>', obj, _Hashable(643 + 1024))
 
125
        self.assertLookup(643, '<null>', obj, _Hashable(643 + 50*1024))
 
126
 
 
127
    def test__lookup_collision(self):
 
128
        obj = self.module.SimpleSet()
 
129
        k1 = _Hashable(643)
 
130
        k2 = _Hashable(643 + 1024)
 
131
        self.assertLookup(643, '<null>', obj, k1)
 
132
        self.assertLookup(643, '<null>', obj, k2)
 
133
        obj.add(k1)
 
134
        self.assertLookup(643, k1, obj, k1)
 
135
        self.assertLookup(644, '<null>', obj, k2)
 
136
 
 
137
    def test__lookup_after_resize(self):
 
138
        obj = self.module.SimpleSet()
 
139
        k1 = _Hashable(643)
 
140
        k2 = _Hashable(643 + 1024)
 
141
        obj.add(k1)
 
142
        obj.add(k2)
 
143
        self.assertLookup(643, k1, obj, k1)
 
144
        self.assertLookup(644, k2, obj, k2)
 
145
        obj._py_resize(2047) # resized to 2048
 
146
        self.assertEqual(2048, obj.mask + 1)
 
147
        self.assertLookup(643, k1, obj, k1)
 
148
        self.assertLookup(643+1024, k2, obj, k2)
 
149
        obj._py_resize(1023) # resized back to 1024
 
150
        self.assertEqual(1024, obj.mask + 1)
 
151
        self.assertLookup(643, k1, obj, k1)
 
152
        self.assertLookup(644, k2, obj, k2)
 
153
 
 
154
    def test_get_set_del_with_collisions(self):
 
155
        obj = self.module.SimpleSet()
 
156
 
 
157
        h1 = 643
 
158
        h2 = 643 + 1024
 
159
        h3 = 643 + 1024*50
 
160
        h4 = 643 + 1024*25
 
161
        h5 = 644
 
162
        h6 = 644 + 1024
 
163
 
 
164
        k1 = _Hashable(h1)
 
165
        k2 = _Hashable(h2)
 
166
        k3 = _Hashable(h3)
 
167
        k4 = _Hashable(h4)
 
168
        k5 = _Hashable(h5)
 
169
        k6 = _Hashable(h6)
 
170
        self.assertLookup(643, '<null>', obj, k1)
 
171
        self.assertLookup(643, '<null>', obj, k2)
 
172
        self.assertLookup(643, '<null>', obj, k3)
 
173
        self.assertLookup(643, '<null>', obj, k4)
 
174
        self.assertLookup(644, '<null>', obj, k5)
 
175
        self.assertLookup(644, '<null>', obj, k6)
 
176
        obj.add(k1)
 
177
        self.assertIn(k1, obj)
 
178
        self.assertNotIn(k2, obj)
 
179
        self.assertNotIn(k3, obj)
 
180
        self.assertNotIn(k4, obj)
 
181
        self.assertLookup(643, k1, obj, k1)
 
182
        self.assertLookup(644, '<null>', obj, k2)
 
183
        self.assertLookup(644, '<null>', obj, k3)
 
184
        self.assertLookup(644, '<null>', obj, k4)
 
185
        self.assertLookup(644, '<null>', obj, k5)
 
186
        self.assertLookup(644, '<null>', obj, k6)
 
187
        self.assertIs(k1, obj[k1])
 
188
        self.assertIs(k2, obj.add(k2))
 
189
        self.assertIs(k2, obj[k2])
 
190
        self.assertLookup(643, k1, obj, k1)
 
191
        self.assertLookup(644, k2, obj, k2)
 
192
        self.assertLookup(646, '<null>', obj, k3)
 
193
        self.assertLookup(646, '<null>', obj, k4)
 
194
        self.assertLookup(645, '<null>', obj, k5)
 
195
        self.assertLookup(645, '<null>', obj, k6)
 
196
        self.assertLookup(643, k1, obj, _Hashable(h1))
 
197
        self.assertLookup(644, k2, obj, _Hashable(h2))
 
198
        self.assertLookup(646, '<null>', obj, _Hashable(h3))
 
199
        self.assertLookup(646, '<null>', obj, _Hashable(h4))
 
200
        self.assertLookup(645, '<null>', obj, _Hashable(h5))
 
201
        self.assertLookup(645, '<null>', obj, _Hashable(h6))
 
202
        obj.add(k3)
 
203
        self.assertIs(k3, obj[k3])
 
204
        self.assertIn(k1, obj)
 
205
        self.assertIn(k2, obj)
 
206
        self.assertIn(k3, obj)
 
207
        self.assertNotIn(k4, obj)
 
208
 
 
209
        obj.discard(k1)
 
210
        self.assertLookup(643, '<dummy>', obj, k1)
 
211
        self.assertLookup(644, k2, obj, k2)
 
212
        self.assertLookup(646, k3, obj, k3)
 
213
        self.assertLookup(643, '<dummy>', obj, k4)
 
214
        self.assertNotIn(k1, obj)
 
215
        self.assertIn(k2, obj)
 
216
        self.assertIn(k3, obj)
 
217
        self.assertNotIn(k4, obj)
 
218
 
 
219
    def test_add(self):
 
220
        obj = self.module.SimpleSet()
 
221
        self.assertFillState(0, 0, 0x3ff, obj)
 
222
        # We use this clumsy notation, because otherwise the refcounts are off.
 
223
        # I'm guessing the python compiler sees it is a static tuple, and adds
 
224
        # it to the function variables, or somesuch
 
225
        k1 = tuple(['foo'])
 
226
        self.assertRefcount(1, k1)
 
227
        self.assertIs(k1, obj.add(k1))
 
228
        self.assertFillState(1, 1, 0x3ff, obj)
 
229
        self.assertRefcount(2, k1)
 
230
        ktest = obj[k1]
 
231
        self.assertRefcount(3, k1)
 
232
        self.assertIs(k1, ktest)
 
233
        del ktest
 
234
        self.assertRefcount(2, k1)
 
235
        k2 = tuple(['foo'])
 
236
        self.assertRefcount(1, k2)
 
237
        self.assertIsNot(k1, k2)
 
238
        # doesn't add anything, so the counters shouldn't be adjusted
 
239
        self.assertIs(k1, obj.add(k2))
 
240
        self.assertFillState(1, 1, 0x3ff, obj)
 
241
        self.assertRefcount(2, k1) # not changed
 
242
        self.assertRefcount(1, k2) # not incremented
 
243
        self.assertIs(k1, obj[k1])
 
244
        self.assertIs(k1, obj[k2])
 
245
        self.assertRefcount(2, k1)
 
246
        self.assertRefcount(1, k2)
 
247
        # Deleting an entry should remove the fill, but not the used
 
248
        obj.discard(k1)
 
249
        self.assertFillState(0, 1, 0x3ff, obj)
 
250
        self.assertRefcount(1, k1)
 
251
        k3 = tuple(['bar'])
 
252
        self.assertRefcount(1, k3)
 
253
        self.assertIs(k3, obj.add(k3))
 
254
        self.assertFillState(1, 2, 0x3ff, obj)
 
255
        self.assertRefcount(2, k3)
 
256
        self.assertIs(k2, obj.add(k2))
 
257
        self.assertFillState(2, 2, 0x3ff, obj)
 
258
        self.assertRefcount(1, k1)
 
259
        self.assertRefcount(2, k2)
 
260
        self.assertRefcount(2, k3)
 
261
 
 
262
    def test_discard(self):
 
263
        obj = self.module.SimpleSet()
 
264
        k1 = tuple(['foo'])
 
265
        k2 = tuple(['foo'])
 
266
        k3 = tuple(['bar'])
 
267
        self.assertRefcount(1, k1)
 
268
        self.assertRefcount(1, k2)
 
269
        self.assertRefcount(1, k3)
 
270
        obj.add(k1)
 
271
        self.assertRefcount(2, k1)
 
272
        self.assertEqual(0, obj.discard(k3))
 
273
        self.assertRefcount(1, k3)
 
274
        obj.add(k3)
 
275
        self.assertRefcount(2, k3)
 
276
        self.assertEqual(1, obj.discard(k3))
 
277
        self.assertRefcount(1, k3)
 
278
 
 
279
    def test__resize(self):
 
280
        obj = self.module.SimpleSet()
 
281
        k1 = ('foo',)
 
282
        k2 = ('bar',)
 
283
        k3 = ('baz',)
 
284
        obj.add(k1)
 
285
        obj.add(k2)
 
286
        obj.add(k3)
 
287
        obj.discard(k2)
 
288
        self.assertFillState(2, 3, 0x3ff, obj)
 
289
        self.assertEqual(1024, obj._py_resize(500))
 
290
        # Doesn't change the size, but does change the content
 
291
        self.assertFillState(2, 2, 0x3ff, obj)
 
292
        obj.add(k2)
 
293
        obj.discard(k3)
 
294
        self.assertFillState(2, 3, 0x3ff, obj)
 
295
        self.assertEqual(4096, obj._py_resize(4095))
 
296
        self.assertFillState(2, 2, 0xfff, obj)
 
297
        self.assertIn(k1, obj)
 
298
        self.assertIn(k2, obj)
 
299
        self.assertNotIn(k3, obj)
 
300
        obj.add(k2)
 
301
        self.assertIn(k2, obj)
 
302
        obj.discard(k2)
 
303
        self.assertEqual((591, '<dummy>'), obj._test_lookup(k2))
 
304
        self.assertFillState(1, 2, 0xfff, obj)
 
305
        self.assertEqual(2048, obj._py_resize(1024))
 
306
        self.assertFillState(1, 1, 0x7ff, obj)
 
307
        self.assertEqual((591, '<null>'), obj._test_lookup(k2))
 
308
 
 
309
    def test_second_hash_failure(self):
 
310
        obj = self.module.SimpleSet()
 
311
        k1 = _BadSecondHash(200)
 
312
        k2 = _Hashable(200)
 
313
        # Should only call hash() one time
 
314
        obj.add(k1)
 
315
        self.assertFalse(k1._first)
 
316
        self.assertRaises(ValueError, obj.add, k2)
 
317
 
 
318
    def test_richcompare_failure(self):
 
319
        obj = self.module.SimpleSet()
 
320
        k1 = _Hashable(200)
 
321
        k2 = _BadCompare(200)
 
322
        obj.add(k1)
 
323
        # Tries to compare with k1, fails
 
324
        self.assertRaises(RuntimeError, obj.add, k2)
 
325
 
 
326
    def test_richcompare_not_implemented(self):
 
327
        obj = self.module.SimpleSet()
 
328
        # Even though their hashes are the same, tp_richcompare returns
 
329
        # NotImplemented, which means we treat them as not equal
 
330
        k1 = _NoImplementCompare(200)
 
331
        k2 = _NoImplementCompare(200)
 
332
        self.assertLookup(200, '<null>', obj, k1)
 
333
        self.assertLookup(200, '<null>', obj, k2)
 
334
        self.assertIs(k1, obj.add(k1))
 
335
        self.assertLookup(200, k1, obj, k1)
 
336
        self.assertLookup(201, '<null>', obj, k2)
 
337
        self.assertIs(k2, obj.add(k2))
 
338
        self.assertIs(k1, obj[k1])
 
339
 
 
340
    def test_add_and_remove_lots_of_items(self):
 
341
        obj = self.module.SimpleSet()
 
342
        chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890'
 
343
        for i in chars:
 
344
            for j in chars:
 
345
                k = (i, j)
 
346
                obj.add(k)
 
347
        num = len(chars)*len(chars)
 
348
        self.assertFillState(num, num, 0x1fff, obj)
 
349
        # Now delete all of the entries and it should shrink again
 
350
        for i in chars:
 
351
            for j in chars:
 
352
                k = (i, j)
 
353
                obj.discard(k)
 
354
        # It should be back to 1024 wide mask, though there may still be some
 
355
        # dummy values in there
 
356
        self.assertFillState(0, obj.fill, 0x3ff, obj)
 
357
        # but there should be fewer than 1/5th dummy entries
 
358
        self.assertTrue(obj.fill < 1024 / 5)
 
359
 
 
360
    def test__iter__(self):
 
361
        obj = self.module.SimpleSet()
 
362
        k1 = ('1',)
 
363
        k2 = ('1', '2')
 
364
        k3 = ('3', '4')
 
365
        obj.add(k1)
 
366
        obj.add(k2)
 
367
        obj.add(k3)
 
368
        all = set()
 
369
        for key in obj:
 
370
            all.add(key)
 
371
        self.assertEqual(sorted([k1, k2, k3]), sorted(all))
 
372
        iterator = iter(obj)
 
373
        iterator.next()
 
374
        obj.add(('foo',))
 
375
        # Set changed size
 
376
        self.assertRaises(RuntimeError, iterator.next)
 
377
        # And even removing an item still causes it to fail
 
378
        obj.discard(k2)
 
379
        self.assertRaises(RuntimeError, iterator.next)
 
380
 
 
381
    def test__sizeof__(self):
 
382
        # SimpleSet needs a custom sizeof implementation, because it allocates
 
383
        # memory that Python cannot directly see (_table).
 
384
        # Too much variability in platform sizes for us to give a fixed size
 
385
        # here. However without a custom implementation, __sizeof__ would give
 
386
        # us only the size of the object, and not its table. We know the table
 
387
        # is at least 4bytes*1024entries in size.
 
388
        obj = self.module.SimpleSet()
 
389
        self.assertTrue(obj.__sizeof__() > 4096)