← 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

Merge bzr.dev

Show diffs side-by-side

added added

removed removed

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