← 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: Canonical.com Patch Queue Manager
  • Date: 2009-10-12 17:54:40 UTC
  • mfrom: (4679.3.94 2.1-simple-set)
  • Revision ID: pqm@pqm.ubuntu.com-20091012175440-ev0bsp43dxi6dt6b
(jam) Add the SimpleSet class,
        will be used for interning StaticTuple objects.

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