← 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

  • Committer: Jonathan Riddell
  • Date: 2011-09-27 14:06:24 UTC
  • mto: This revision was merged to the branch mainline in revision 6174.
  • Revision ID: jriddell@canonical.com-20110927140624-b2kx73ur01cu72il
use header format consistent with rest of bzr.  change copyright to canonical in line with copyright agreement

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