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

  • Committer: Robert Collins
  • Date: 2005-10-19 10:11:57 UTC
  • mfrom: (1185.16.78)
  • mto: This revision was merged to the branch mainline in revision 1470.
  • Revision ID: robertc@robertcollins.net-20051019101157-17438d311e746b4f
merge from upstream

Show diffs side-by-side

added added

removed removed

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