/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 bzrlib/tests/test__simple_set.py

Finish the pycurl feature.

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