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

  • Committer: Andrew Bennetts
  • Date: 2008-08-12 14:53:26 UTC
  • mto: This revision was merged to the branch mainline in revision 3624.
  • Revision ID: andrew.bennetts@canonical.com-20080812145326-yx693x2jc4rcovb7
Move the notes on writing tests out of HACKING into a new file, and improve
them.

Many of the testing notes in the HACKING file were in duplicated in two places
in that file!  This change removes that duplication.  It also adds new sections
on “Where should I put a new test?” and “TestCase and its subclasses”, and
others like “Test feature dependencies” have been expanded.  The whole document
has generally been edited to be a bit more coherent. 

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_lru_cache.py
1
 
# Copyright (C) 2006, 2008, 2009 Canonical Ltd
 
1
# Copyright (C) 2006 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
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
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
"""Tests for the lru_cache module."""
18
18
 
25
25
class TestLRUCache(tests.TestCase):
26
26
    """Test that LRU cache properly keeps track of entries."""
27
27
 
28
 
    def test_cache_size(self):
29
 
        cache = lru_cache.LRUCache(max_cache=10)
30
 
        self.assertEqual(10, cache.cache_size())
31
 
 
32
 
        cache = lru_cache.LRUCache(max_cache=256)
33
 
        self.assertEqual(256, cache.cache_size())
34
 
 
35
 
        cache.resize(512)
36
 
        self.assertEqual(512, cache.cache_size())
37
 
 
38
28
    def test_missing(self):
39
29
        cache = lru_cache.LRUCache(max_cache=10)
40
30
 
46
36
        self.failUnless('foo' in cache)
47
37
        self.failIf('bar' in cache)
48
38
 
49
 
    def test_map_None(self):
50
 
        # Make sure that we can properly map None as a key.
51
 
        cache = lru_cache.LRUCache(max_cache=10)
52
 
        self.failIf(None in cache)
53
 
        cache[None] = 1
54
 
        self.assertEqual(1, cache[None])
55
 
        cache[None] = 2
56
 
        self.assertEqual(2, cache[None])
57
 
        # Test the various code paths of __getitem__, to make sure that we can
58
 
        # handle when None is the key for the LRU and the MRU
59
 
        cache[1] = 3
60
 
        cache[None] = 1
61
 
        cache[None]
62
 
        cache[1]
63
 
        cache[None]
64
 
        self.assertEqual([None, 1], [n.key for n in cache._walk_lru()])
65
 
 
66
 
    def test_add__null_key(self):
67
 
        cache = lru_cache.LRUCache(max_cache=10)
68
 
        self.assertRaises(ValueError, cache.add, lru_cache._null_key, 1)
69
 
 
70
39
    def test_overflow(self):
71
40
        """Adding extra entries will pop out old ones."""
72
 
        cache = lru_cache.LRUCache(max_cache=1, after_cleanup_count=1)
 
41
        cache = lru_cache.LRUCache(max_cache=1)
73
42
 
74
43
        cache['foo'] = 'bar'
75
44
        # With a max cache of 1, adding 'baz' should pop out 'foo'
94
63
 
95
64
        self.failIf('foo' in cache)
96
65
 
 
66
    def test_queue_stays_bounded(self):
 
67
        """Lots of accesses does not cause the queue to grow without bound."""
 
68
        cache = lru_cache.LRUCache(max_cache=10)
 
69
 
 
70
        cache['baz'] = 'biz'
 
71
        cache['foo'] = 'bar'
 
72
 
 
73
        for i in xrange(1000):
 
74
            cache['baz']
 
75
 
 
76
        self.failUnless(len(cache._queue) < 40)
 
77
 
97
78
    def test_cleanup(self):
98
79
        """Test that we can use a cleanup function."""
99
80
        cleanup_called = []
111
92
        # 'foo' is now most recent, so final cleanup will call it last
112
93
        cache['foo']
113
94
        cache.clear()
114
 
        self.assertEqual([('baz', '1'), ('biz', '3'), ('foo', '2')],
115
 
                         cleanup_called)
 
95
        self.assertEqual([('baz', '1'), ('biz', '3'), ('foo', '2')], cleanup_called)
116
96
 
117
97
    def test_cleanup_on_replace(self):
118
98
        """Replacing an object should cleanup the old value."""
127
107
 
128
108
        self.assertEqual([(2, 20)], cleanup_called)
129
109
        self.assertEqual(25, cache[2])
130
 
 
 
110
        
131
111
        # Even __setitem__ should make sure cleanup() is called
132
112
        cache[2] = 26
133
113
        self.assertEqual([(2, 20), (2, 25)], cleanup_called)
134
114
 
135
 
    def test_cleanup_error_maintains_linked_list(self):
136
 
        cleanup_called = []
137
 
        def cleanup_func(key, val):
138
 
            cleanup_called.append((key, val))
139
 
            raise ValueError('failure during cleanup')
140
 
 
141
 
        cache = lru_cache.LRUCache(max_cache=10)
142
 
        for i in xrange(10):
143
 
            cache.add(i, i, cleanup=cleanup_func)
144
 
        for i in xrange(10, 20):
145
 
            self.assertRaises(ValueError,
146
 
                cache.add, i, i, cleanup=cleanup_func)
147
 
 
148
 
        self.assertEqual([(i, i) for i in xrange(10)], cleanup_called)
149
 
 
150
 
        self.assertEqual(range(19, 9, -1), [n.key for n in cache._walk_lru()])
151
 
 
152
 
    def test_cleanup_during_replace_still_replaces(self):
153
 
        cleanup_called = []
154
 
        def cleanup_func(key, val):
155
 
            cleanup_called.append((key, val))
156
 
            raise ValueError('failure during cleanup')
157
 
 
158
 
        cache = lru_cache.LRUCache(max_cache=10)
159
 
        for i in xrange(10):
160
 
            cache.add(i, i, cleanup=cleanup_func)
161
 
        self.assertRaises(ValueError,
162
 
            cache.add, 1, 20, cleanup=cleanup_func)
163
 
        # We also still update the recent access to this node
164
 
        self.assertEqual([1, 9, 8, 7, 6, 5, 4, 3, 2, 0],
165
 
                         [n.key for n in cache._walk_lru()])
166
 
        self.assertEqual(20, cache[1])
167
 
 
168
 
        self.assertEqual([(1, 1)], cleanup_called)
169
 
        self.assertEqual([1, 9, 8, 7, 6, 5, 4, 3, 2, 0],
170
 
                         [n.key for n in cache._walk_lru()])
171
 
 
172
115
    def test_len(self):
173
 
        cache = lru_cache.LRUCache(max_cache=10, after_cleanup_count=10)
 
116
        cache = lru_cache.LRUCache(max_cache=10)
174
117
 
175
118
        cache[1] = 10
176
119
        cache[2] = 20
196
139
 
197
140
        # We hit the max
198
141
        self.assertEqual(10, len(cache))
199
 
        self.assertEqual([11, 10, 9, 1, 8, 7, 6, 5, 4, 3],
200
 
                         [n.key for n in cache._walk_lru()])
201
142
 
202
 
    def test_cleanup_shrinks_to_after_clean_count(self):
203
 
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=3)
 
143
    def test_cleanup_shrinks_to_after_clean_size(self):
 
144
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_size=3)
204
145
 
205
146
        cache.add(1, 10)
206
147
        cache.add(2, 20)
215
156
        self.assertEqual(3, len(cache))
216
157
 
217
158
    def test_after_cleanup_larger_than_max(self):
218
 
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=10)
219
 
        self.assertEqual(5, cache._after_cleanup_count)
 
159
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_size=10)
 
160
        self.assertEqual(5, cache._after_cleanup_size)
220
161
 
221
162
    def test_after_cleanup_none(self):
222
 
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=None)
223
 
        # By default _after_cleanup_size is 80% of the normal size
224
 
        self.assertEqual(4, cache._after_cleanup_count)
 
163
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_size=None)
 
164
        self.assertEqual(5, cache._after_cleanup_size)
225
165
 
226
166
    def test_cleanup(self):
227
 
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=2)
 
167
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_size=2)
228
168
 
229
169
        # Add these in order
230
170
        cache.add(1, 10)
238
178
        cache.cleanup()
239
179
        self.assertEqual(2, len(cache))
240
180
 
241
 
    def test_preserve_last_access_order(self):
 
181
    def test_compact_preserves_last_access_order(self):
242
182
        cache = lru_cache.LRUCache(max_cache=5)
243
183
 
244
184
        # Add these in order
248
188
        cache.add(4, 30)
249
189
        cache.add(5, 35)
250
190
 
251
 
        self.assertEqual([5, 4, 3, 2, 1], [n.key for n in cache._walk_lru()])
 
191
        self.assertEqual([1, 2, 3, 4, 5], list(cache._queue))
252
192
 
253
193
        # Now access some randomly
254
194
        cache[2]
255
195
        cache[5]
256
196
        cache[3]
257
197
        cache[2]
258
 
        self.assertEqual([2, 3, 5, 4, 1], [n.key for n in cache._walk_lru()])
 
198
        self.assertEqual([1, 2, 3, 4, 5, 2, 5, 3, 2], list(cache._queue))
 
199
        self.assertEqual({1:1, 2:3, 3:2, 4:1, 5:2}, cache._refcount)
 
200
 
 
201
        # Compacting should save the last position
 
202
        cache._compact_queue()
 
203
        self.assertEqual([1, 4, 5, 3, 2], list(cache._queue))
 
204
        self.assertEqual({1:1, 2:1, 3:1, 4:1, 5:1}, cache._refcount)
259
205
 
260
206
    def test_get(self):
261
207
        cache = lru_cache.LRUCache(max_cache=5)
266
212
        self.assertIs(None, cache.get(3))
267
213
        obj = object()
268
214
        self.assertIs(obj, cache.get(3, obj))
269
 
        self.assertEqual([2, 1], [n.key for n in cache._walk_lru()])
270
 
        self.assertEqual(10, cache.get(1))
271
 
        self.assertEqual([1, 2], [n.key for n in cache._walk_lru()])
272
 
 
273
 
    def test_keys(self):
274
 
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=5)
275
 
 
276
 
        cache[1] = 2
277
 
        cache[2] = 3
278
 
        cache[3] = 4
279
 
        self.assertEqual([1, 2, 3], sorted(cache.keys()))
280
 
        cache[4] = 5
281
 
        cache[5] = 6
282
 
        cache[6] = 7
283
 
        self.assertEqual([2, 3, 4, 5, 6], sorted(cache.keys()))
284
 
 
285
 
    def test_after_cleanup_size_deprecated(self):
286
 
        obj = self.callDeprecated([
287
 
            'LRUCache.__init__(after_cleanup_size) was deprecated in 1.11.'
288
 
            ' Use after_cleanup_count instead.'],
289
 
            lru_cache.LRUCache, 50, after_cleanup_size=25)
290
 
        self.assertEqual(obj._after_cleanup_count, 25)
291
 
 
292
 
    def test_resize_smaller(self):
293
 
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=4)
294
 
        cache[1] = 2
295
 
        cache[2] = 3
296
 
        cache[3] = 4
297
 
        cache[4] = 5
298
 
        cache[5] = 6
299
 
        self.assertEqual([1, 2, 3, 4, 5], sorted(cache.keys()))
300
 
        cache[6] = 7
301
 
        self.assertEqual([3, 4, 5, 6], sorted(cache.keys()))
302
 
        # Now resize to something smaller, which triggers a cleanup
303
 
        cache.resize(max_cache=3, after_cleanup_count=2)
304
 
        self.assertEqual([5, 6], sorted(cache.keys()))
305
 
        # Adding something will use the new size
306
 
        cache[7] = 8
307
 
        self.assertEqual([5, 6, 7], sorted(cache.keys()))
308
 
        cache[8] = 9
309
 
        self.assertEqual([7, 8], sorted(cache.keys()))
310
 
 
311
 
    def test_resize_larger(self):
312
 
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=4)
313
 
        cache[1] = 2
314
 
        cache[2] = 3
315
 
        cache[3] = 4
316
 
        cache[4] = 5
317
 
        cache[5] = 6
318
 
        self.assertEqual([1, 2, 3, 4, 5], sorted(cache.keys()))
319
 
        cache[6] = 7
320
 
        self.assertEqual([3, 4, 5, 6], sorted(cache.keys()))
321
 
        cache.resize(max_cache=8, after_cleanup_count=6)
322
 
        self.assertEqual([3, 4, 5, 6], sorted(cache.keys()))
323
 
        cache[7] = 8
324
 
        cache[8] = 9
325
 
        cache[9] = 10
326
 
        cache[10] = 11
327
 
        self.assertEqual([3, 4, 5, 6, 7, 8, 9, 10], sorted(cache.keys()))
328
 
        cache[11] = 12 # triggers cleanup back to new after_cleanup_count
329
 
        self.assertEqual([6, 7, 8, 9, 10, 11], sorted(cache.keys()))
330
215
 
331
216
 
332
217
class TestLRUSizeCache(tests.TestCase):
334
219
    def test_basic_init(self):
335
220
        cache = lru_cache.LRUSizeCache()
336
221
        self.assertEqual(2048, cache._max_cache)
337
 
        self.assertEqual(int(cache._max_size*0.8), cache._after_cleanup_size)
 
222
        self.assertEqual(4*2048, cache._compact_queue_length)
 
223
        self.assertEqual(cache._max_size, cache._after_cleanup_size)
338
224
        self.assertEqual(0, cache._value_size)
339
225
 
340
 
    def test_add__null_key(self):
341
 
        cache = lru_cache.LRUSizeCache()
342
 
        self.assertRaises(ValueError, cache.add, lru_cache._null_key, 1)
343
 
 
344
226
    def test_add_tracks_size(self):
345
227
        cache = lru_cache.LRUSizeCache()
346
228
        self.assertEqual(0, cache._value_size)
352
234
        self.assertEqual(0, cache._value_size)
353
235
        cache.add('my key', 'my value text')
354
236
        self.assertEqual(13, cache._value_size)
355
 
        node = cache._cache['my key']
356
 
        cache._remove_node(node)
 
237
        cache._remove('my key')
357
238
        self.assertEqual(0, cache._value_size)
358
239
 
359
240
    def test_no_add_over_size(self):
360
241
        """Adding a large value may not be cached at all."""
361
242
        cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=5)
362
243
        self.assertEqual(0, cache._value_size)
363
 
        self.assertEqual({}, cache.items())
 
244
        self.assertEqual({}, cache._cache)
364
245
        cache.add('test', 'key')
365
246
        self.assertEqual(3, cache._value_size)
366
 
        self.assertEqual({'test': 'key'}, cache.items())
 
247
        self.assertEqual({'test':'key'}, cache._cache)
367
248
        cache.add('test2', 'key that is too big')
368
249
        self.assertEqual(3, cache._value_size)
369
 
        self.assertEqual({'test':'key'}, cache.items())
 
250
        self.assertEqual({'test':'key'}, cache._cache)
370
251
        # If we would add a key, only to cleanup and remove all cached entries,
371
252
        # then obviously that value should not be stored
372
253
        cache.add('test3', 'bigkey')
373
254
        self.assertEqual(3, cache._value_size)
374
 
        self.assertEqual({'test':'key'}, cache.items())
 
255
        self.assertEqual({'test':'key'}, cache._cache)
375
256
 
376
257
        cache.add('test4', 'bikey')
377
258
        self.assertEqual(3, cache._value_size)
378
 
        self.assertEqual({'test':'key'}, cache.items())
379
 
 
380
 
    def test_no_add_over_size_cleanup(self):
381
 
        """If a large value is not cached, we will call cleanup right away."""
382
 
        cleanup_calls = []
383
 
        def cleanup(key, value):
384
 
            cleanup_calls.append((key, value))
385
 
 
386
 
        cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=5)
387
 
        self.assertEqual(0, cache._value_size)
388
 
        self.assertEqual({}, cache.items())
389
 
        cache.add('test', 'key that is too big', cleanup=cleanup)
390
 
        # key was not added
391
 
        self.assertEqual(0, cache._value_size)
392
 
        self.assertEqual({}, cache.items())
393
 
        # and cleanup was called
394
 
        self.assertEqual([('test', 'key that is too big')], cleanup_calls)
 
259
        self.assertEqual({'test':'key'}, cache._cache)
395
260
 
396
261
    def test_adding_clears_cache_based_on_size(self):
397
262
        """The cache is cleared in LRU order until small enough"""
405
270
        # We have to remove 2 keys to get back under limit
406
271
        self.assertEqual(6+8, cache._value_size)
407
272
        self.assertEqual({'key2':'value2', 'key4':'value234'},
408
 
                         cache.items())
 
273
                         cache._cache)
409
274
 
410
275
    def test_adding_clears_to_after_cleanup_size(self):
411
276
        cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
417
282
        cache.add('key4', 'value234') # 8 chars, over limit
418
283
        # We have to remove 3 keys to get back under limit
419
284
        self.assertEqual(8, cache._value_size)
420
 
        self.assertEqual({'key4':'value234'}, cache.items())
 
285
        self.assertEqual({'key4':'value234'}, cache._cache)
421
286
 
422
287
    def test_custom_sizes(self):
423
288
        def size_of_list(lst):
433
298
        cache.add('key4', ['value', '234']) # 8 chars, over limit
434
299
        # We have to remove 3 keys to get back under limit
435
300
        self.assertEqual(8, cache._value_size)
436
 
        self.assertEqual({'key4':['value', '234']}, cache.items())
 
301
        self.assertEqual({'key4':['value', '234']}, cache._cache)
437
302
 
438
303
    def test_cleanup(self):
439
304
        cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
447
312
        cache.cleanup()
448
313
        # Only the most recent fits after cleaning up
449
314
        self.assertEqual(7, cache._value_size)
450
 
 
451
 
    def test_keys(self):
452
 
        cache = lru_cache.LRUSizeCache(max_size=10)
453
 
 
454
 
        cache[1] = 'a'
455
 
        cache[2] = 'b'
456
 
        cache[3] = 'cdef'
457
 
        self.assertEqual([1, 2, 3], sorted(cache.keys()))
458
 
 
459
 
    def test_resize_smaller(self):
460
 
        cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=9)
461
 
        cache[1] = 'abc'
462
 
        cache[2] = 'def'
463
 
        cache[3] = 'ghi'
464
 
        cache[4] = 'jkl'
465
 
        # Triggers a cleanup
466
 
        self.assertEqual([2, 3, 4], sorted(cache.keys()))
467
 
        # Resize should also cleanup again
468
 
        cache.resize(max_size=6, after_cleanup_size=4)
469
 
        self.assertEqual([4], sorted(cache.keys()))
470
 
        # Adding should use the new max size
471
 
        cache[5] = 'mno'
472
 
        self.assertEqual([4, 5], sorted(cache.keys()))
473
 
        cache[6] = 'pqr'
474
 
        self.assertEqual([6], sorted(cache.keys()))
475
 
 
476
 
    def test_resize_larger(self):
477
 
        cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=9)
478
 
        cache[1] = 'abc'
479
 
        cache[2] = 'def'
480
 
        cache[3] = 'ghi'
481
 
        cache[4] = 'jkl'
482
 
        # Triggers a cleanup
483
 
        self.assertEqual([2, 3, 4], sorted(cache.keys()))
484
 
        cache.resize(max_size=15, after_cleanup_size=12)
485
 
        self.assertEqual([2, 3, 4], sorted(cache.keys()))
486
 
        cache[5] = 'mno'
487
 
        cache[6] = 'pqr'
488
 
        self.assertEqual([2, 3, 4, 5, 6], sorted(cache.keys()))
489
 
        cache[7] = 'stu'
490
 
        self.assertEqual([4, 5, 6, 7], sorted(cache.keys()))
491