/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: Jelmer Vernooij
  • Date: 2018-05-19 13:16:11 UTC
  • mto: (6968.4.3 git-archive)
  • mto: This revision was merged to the branch mainline in revision 6972.
  • Revision ID: jelmer@jelmer.uk-20180519131611-l9h9ud41j7qg1m03
Move tar/zip to breezy.archive.

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
        st = ('foo', 'bar')
 
116
        self.assertFillState(0, 0, 0x3ff, obj)
 
117
 
 
118
    def test__lookup(self):
 
119
        # These are carefully chosen integers to force hash collisions in the
 
120
        # algorithm, based on the initial set size of 1024
 
121
        obj = self.module.SimpleSet()
 
122
        self.assertLookup(643, '<null>', obj, _Hashable(643))
 
123
        self.assertLookup(643, '<null>', obj, _Hashable(643 + 1024))
 
124
        self.assertLookup(643, '<null>', obj, _Hashable(643 + 50*1024))
 
125
 
 
126
    def test__lookup_collision(self):
 
127
        obj = self.module.SimpleSet()
 
128
        k1 = _Hashable(643)
 
129
        k2 = _Hashable(643 + 1024)
 
130
        self.assertLookup(643, '<null>', obj, k1)
 
131
        self.assertLookup(643, '<null>', obj, k2)
 
132
        obj.add(k1)
 
133
        self.assertLookup(643, k1, obj, k1)
 
134
        self.assertLookup(644, '<null>', obj, k2)
 
135
 
 
136
    def test__lookup_after_resize(self):
 
137
        obj = self.module.SimpleSet()
 
138
        k1 = _Hashable(643)
 
139
        k2 = _Hashable(643 + 1024)
 
140
        obj.add(k1)
 
141
        obj.add(k2)
 
142
        self.assertLookup(643, k1, obj, k1)
 
143
        self.assertLookup(644, k2, obj, k2)
 
144
        obj._py_resize(2047) # resized to 2048
 
145
        self.assertEqual(2048, obj.mask + 1)
 
146
        self.assertLookup(643, k1, obj, k1)
 
147
        self.assertLookup(643+1024, k2, obj, k2)
 
148
        obj._py_resize(1023) # resized back to 1024
 
149
        self.assertEqual(1024, obj.mask + 1)
 
150
        self.assertLookup(643, k1, obj, k1)
 
151
        self.assertLookup(644, k2, obj, k2)
 
152
 
 
153
    def test_get_set_del_with_collisions(self):
 
154
        obj = self.module.SimpleSet()
 
155
 
 
156
        h1 = 643
 
157
        h2 = 643 + 1024
 
158
        h3 = 643 + 1024*50
 
159
        h4 = 643 + 1024*25
 
160
        h5 = 644
 
161
        h6 = 644 + 1024
 
162
 
 
163
        k1 = _Hashable(h1)
 
164
        k2 = _Hashable(h2)
 
165
        k3 = _Hashable(h3)
 
166
        k4 = _Hashable(h4)
 
167
        k5 = _Hashable(h5)
 
168
        k6 = _Hashable(h6)
 
169
        self.assertLookup(643, '<null>', obj, k1)
 
170
        self.assertLookup(643, '<null>', obj, k2)
 
171
        self.assertLookup(643, '<null>', obj, k3)
 
172
        self.assertLookup(643, '<null>', obj, k4)
 
173
        self.assertLookup(644, '<null>', obj, k5)
 
174
        self.assertLookup(644, '<null>', obj, k6)
 
175
        obj.add(k1)
 
176
        self.assertIn(k1, obj)
 
177
        self.assertNotIn(k2, obj)
 
178
        self.assertNotIn(k3, obj)
 
179
        self.assertNotIn(k4, obj)
 
180
        self.assertLookup(643, k1, obj, k1)
 
181
        self.assertLookup(644, '<null>', obj, k2)
 
182
        self.assertLookup(644, '<null>', obj, k3)
 
183
        self.assertLookup(644, '<null>', obj, k4)
 
184
        self.assertLookup(644, '<null>', obj, k5)
 
185
        self.assertLookup(644, '<null>', obj, k6)
 
186
        self.assertIs(k1, obj[k1])
 
187
        self.assertIs(k2, obj.add(k2))
 
188
        self.assertIs(k2, obj[k2])
 
189
        self.assertLookup(643, k1, obj, k1)
 
190
        self.assertLookup(644, k2, obj, k2)
 
191
        self.assertLookup(646, '<null>', obj, k3)
 
192
        self.assertLookup(646, '<null>', obj, k4)
 
193
        self.assertLookup(645, '<null>', obj, k5)
 
194
        self.assertLookup(645, '<null>', obj, k6)
 
195
        self.assertLookup(643, k1, obj, _Hashable(h1))
 
196
        self.assertLookup(644, k2, obj, _Hashable(h2))
 
197
        self.assertLookup(646, '<null>', obj, _Hashable(h3))
 
198
        self.assertLookup(646, '<null>', obj, _Hashable(h4))
 
199
        self.assertLookup(645, '<null>', obj, _Hashable(h5))
 
200
        self.assertLookup(645, '<null>', obj, _Hashable(h6))
 
201
        obj.add(k3)
 
202
        self.assertIs(k3, obj[k3])
 
203
        self.assertIn(k1, obj)
 
204
        self.assertIn(k2, obj)
 
205
        self.assertIn(k3, obj)
 
206
        self.assertNotIn(k4, obj)
 
207
 
 
208
        obj.discard(k1)
 
209
        self.assertLookup(643, '<dummy>', obj, k1)
 
210
        self.assertLookup(644, k2, obj, k2)
 
211
        self.assertLookup(646, k3, obj, k3)
 
212
        self.assertLookup(643, '<dummy>', obj, k4)
 
213
        self.assertNotIn(k1, obj)
 
214
        self.assertIn(k2, obj)
 
215
        self.assertIn(k3, obj)
 
216
        self.assertNotIn(k4, obj)
 
217
 
 
218
    def test_add(self):
 
219
        obj = self.module.SimpleSet()
 
220
        self.assertFillState(0, 0, 0x3ff, obj)
 
221
        # We use this clumsy notation, because otherwise the refcounts are off.
 
222
        # I'm guessing the python compiler sees it is a static tuple, and adds
 
223
        # it to the function variables, or somesuch
 
224
        k1 = tuple(['foo'])
 
225
        self.assertRefcount(1, k1)
 
226
        self.assertIs(k1, obj.add(k1))
 
227
        self.assertFillState(1, 1, 0x3ff, obj)
 
228
        self.assertRefcount(2, k1)
 
229
        ktest = obj[k1]
 
230
        self.assertRefcount(3, k1)
 
231
        self.assertIs(k1, ktest)
 
232
        del ktest
 
233
        self.assertRefcount(2, k1)
 
234
        k2 = tuple(['foo'])
 
235
        self.assertRefcount(1, k2)
 
236
        self.assertIsNot(k1, k2)
 
237
        # doesn't add anything, so the counters shouldn't be adjusted
 
238
        self.assertIs(k1, obj.add(k2))
 
239
        self.assertFillState(1, 1, 0x3ff, obj)
 
240
        self.assertRefcount(2, k1) # not changed
 
241
        self.assertRefcount(1, k2) # not incremented
 
242
        self.assertIs(k1, obj[k1])
 
243
        self.assertIs(k1, obj[k2])
 
244
        self.assertRefcount(2, k1)
 
245
        self.assertRefcount(1, k2)
 
246
        # Deleting an entry should remove the fill, but not the used
 
247
        obj.discard(k1)
 
248
        self.assertFillState(0, 1, 0x3ff, obj)
 
249
        self.assertRefcount(1, k1)
 
250
        k3 = tuple(['bar'])
 
251
        self.assertRefcount(1, k3)
 
252
        self.assertIs(k3, obj.add(k3))
 
253
        self.assertFillState(1, 2, 0x3ff, obj)
 
254
        self.assertRefcount(2, k3)
 
255
        self.assertIs(k2, obj.add(k2))
 
256
        self.assertFillState(2, 2, 0x3ff, obj)
 
257
        self.assertRefcount(1, k1)
 
258
        self.assertRefcount(2, k2)
 
259
        self.assertRefcount(2, k3)
 
260
 
 
261
    def test_discard(self):
 
262
        obj = self.module.SimpleSet()
 
263
        k1 = tuple(['foo'])
 
264
        k2 = tuple(['foo'])
 
265
        k3 = tuple(['bar'])
 
266
        self.assertRefcount(1, k1)
 
267
        self.assertRefcount(1, k2)
 
268
        self.assertRefcount(1, k3)
 
269
        obj.add(k1)
 
270
        self.assertRefcount(2, k1)
 
271
        self.assertEqual(0, obj.discard(k3))
 
272
        self.assertRefcount(1, k3)
 
273
        obj.add(k3)
 
274
        self.assertRefcount(2, k3)
 
275
        self.assertEqual(1, obj.discard(k3))
 
276
        self.assertRefcount(1, k3)
 
277
 
 
278
    def test__resize(self):
 
279
        obj = self.module.SimpleSet()
 
280
        # Need objects with exact hash as checking offset of <null> later
 
281
        k1 = _Hashable(501)
 
282
        k2 = _Hashable(591)
 
283
        k3 = _Hashable(2051)
 
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
        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)