/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: John Arbash Meinel
  • Date: 2009-12-22 16:28:47 UTC
  • mto: This revision was merged to the branch mainline in revision 4922.
  • Revision ID: john@arbash-meinel.com-20091222162847-tvnsc69to4l4uf5r
Implement a permute_for_extension helper.

Use it for all of the 'simple' extension permutations.
It basically permutes all tests in the current module, by setting TestCase.module.
Which works well for most of our extension tests. Some had more advanced
handling of permutations (extra permutations, custom vars, etc.)

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
 
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 lru_cache module."""
 
18
 
 
19
from bzrlib import (
 
20
    lru_cache,
 
21
    tests,
 
22
    )
 
23
 
 
24
 
 
25
class TestLRUCache(tests.TestCase):
 
26
    """Test that LRU cache properly keeps track of entries."""
 
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
    def test_missing(self):
 
39
        cache = lru_cache.LRUCache(max_cache=10)
 
40
 
 
41
        self.failIf('foo' in cache)
 
42
        self.assertRaises(KeyError, cache.__getitem__, 'foo')
 
43
 
 
44
        cache['foo'] = 'bar'
 
45
        self.assertEqual('bar', cache['foo'])
 
46
        self.failUnless('foo' in cache)
 
47
        self.failIf('bar' in cache)
 
48
 
 
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
    def test_overflow(self):
 
71
        """Adding extra entries will pop out old ones."""
 
72
        cache = lru_cache.LRUCache(max_cache=1, after_cleanup_count=1)
 
73
 
 
74
        cache['foo'] = 'bar'
 
75
        # With a max cache of 1, adding 'baz' should pop out 'foo'
 
76
        cache['baz'] = 'biz'
 
77
 
 
78
        self.failIf('foo' in cache)
 
79
        self.failUnless('baz' in cache)
 
80
 
 
81
        self.assertEqual('biz', cache['baz'])
 
82
 
 
83
    def test_by_usage(self):
 
84
        """Accessing entries bumps them up in priority."""
 
85
        cache = lru_cache.LRUCache(max_cache=2)
 
86
 
 
87
        cache['baz'] = 'biz'
 
88
        cache['foo'] = 'bar'
 
89
 
 
90
        self.assertEqual('biz', cache['baz'])
 
91
 
 
92
        # This must kick out 'foo' because it was the last accessed
 
93
        cache['nub'] = 'in'
 
94
 
 
95
        self.failIf('foo' in cache)
 
96
 
 
97
    def test_cleanup(self):
 
98
        """Test that we can use a cleanup function."""
 
99
        cleanup_called = []
 
100
        def cleanup_func(key, val):
 
101
            cleanup_called.append((key, val))
 
102
 
 
103
        cache = lru_cache.LRUCache(max_cache=2)
 
104
 
 
105
        cache.add('baz', '1', cleanup=cleanup_func)
 
106
        cache.add('foo', '2', cleanup=cleanup_func)
 
107
        cache.add('biz', '3', cleanup=cleanup_func)
 
108
 
 
109
        self.assertEqual([('baz', '1')], cleanup_called)
 
110
 
 
111
        # 'foo' is now most recent, so final cleanup will call it last
 
112
        cache['foo']
 
113
        cache.clear()
 
114
        self.assertEqual([('baz', '1'), ('biz', '3'), ('foo', '2')],
 
115
                         cleanup_called)
 
116
 
 
117
    def test_cleanup_on_replace(self):
 
118
        """Replacing an object should cleanup the old value."""
 
119
        cleanup_called = []
 
120
        def cleanup_func(key, val):
 
121
            cleanup_called.append((key, val))
 
122
 
 
123
        cache = lru_cache.LRUCache(max_cache=2)
 
124
        cache.add(1, 10, cleanup=cleanup_func)
 
125
        cache.add(2, 20, cleanup=cleanup_func)
 
126
        cache.add(2, 25, cleanup=cleanup_func)
 
127
 
 
128
        self.assertEqual([(2, 20)], cleanup_called)
 
129
        self.assertEqual(25, cache[2])
 
130
 
 
131
        # Even __setitem__ should make sure cleanup() is called
 
132
        cache[2] = 26
 
133
        self.assertEqual([(2, 20), (2, 25)], cleanup_called)
 
134
 
 
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
    def test_len(self):
 
173
        cache = lru_cache.LRUCache(max_cache=10, after_cleanup_count=10)
 
174
 
 
175
        cache[1] = 10
 
176
        cache[2] = 20
 
177
        cache[3] = 30
 
178
        cache[4] = 40
 
179
 
 
180
        self.assertEqual(4, len(cache))
 
181
 
 
182
        cache[5] = 50
 
183
        cache[6] = 60
 
184
        cache[7] = 70
 
185
        cache[8] = 80
 
186
 
 
187
        self.assertEqual(8, len(cache))
 
188
 
 
189
        cache[1] = 15 # replacement
 
190
 
 
191
        self.assertEqual(8, len(cache))
 
192
 
 
193
        cache[9] = 90
 
194
        cache[10] = 100
 
195
        cache[11] = 110
 
196
 
 
197
        # We hit the max
 
198
        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
 
 
202
    def test_cleanup_shrinks_to_after_clean_count(self):
 
203
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=3)
 
204
 
 
205
        cache.add(1, 10)
 
206
        cache.add(2, 20)
 
207
        cache.add(3, 25)
 
208
        cache.add(4, 30)
 
209
        cache.add(5, 35)
 
210
 
 
211
        self.assertEqual(5, len(cache))
 
212
        # This will bump us over the max, which causes us to shrink down to
 
213
        # after_cleanup_cache size
 
214
        cache.add(6, 40)
 
215
        self.assertEqual(3, len(cache))
 
216
 
 
217
    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)
 
220
 
 
221
    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)
 
225
 
 
226
    def test_cleanup(self):
 
227
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=2)
 
228
 
 
229
        # Add these in order
 
230
        cache.add(1, 10)
 
231
        cache.add(2, 20)
 
232
        cache.add(3, 25)
 
233
        cache.add(4, 30)
 
234
        cache.add(5, 35)
 
235
 
 
236
        self.assertEqual(5, len(cache))
 
237
        # Force a compaction
 
238
        cache.cleanup()
 
239
        self.assertEqual(2, len(cache))
 
240
 
 
241
    def test_preserve_last_access_order(self):
 
242
        cache = lru_cache.LRUCache(max_cache=5)
 
243
 
 
244
        # Add these in order
 
245
        cache.add(1, 10)
 
246
        cache.add(2, 20)
 
247
        cache.add(3, 25)
 
248
        cache.add(4, 30)
 
249
        cache.add(5, 35)
 
250
 
 
251
        self.assertEqual([5, 4, 3, 2, 1], [n.key for n in cache._walk_lru()])
 
252
 
 
253
        # Now access some randomly
 
254
        cache[2]
 
255
        cache[5]
 
256
        cache[3]
 
257
        cache[2]
 
258
        self.assertEqual([2, 3, 5, 4, 1], [n.key for n in cache._walk_lru()])
 
259
 
 
260
    def test_get(self):
 
261
        cache = lru_cache.LRUCache(max_cache=5)
 
262
 
 
263
        cache.add(1, 10)
 
264
        cache.add(2, 20)
 
265
        self.assertEqual(20, cache.get(2))
 
266
        self.assertIs(None, cache.get(3))
 
267
        obj = object()
 
268
        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
 
 
331
 
 
332
class TestLRUSizeCache(tests.TestCase):
 
333
 
 
334
    def test_basic_init(self):
 
335
        cache = lru_cache.LRUSizeCache()
 
336
        self.assertEqual(2048, cache._max_cache)
 
337
        self.assertEqual(int(cache._max_size*0.8), cache._after_cleanup_size)
 
338
        self.assertEqual(0, cache._value_size)
 
339
 
 
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
    def test_add_tracks_size(self):
 
345
        cache = lru_cache.LRUSizeCache()
 
346
        self.assertEqual(0, cache._value_size)
 
347
        cache.add('my key', 'my value text')
 
348
        self.assertEqual(13, cache._value_size)
 
349
 
 
350
    def test_remove_tracks_size(self):
 
351
        cache = lru_cache.LRUSizeCache()
 
352
        self.assertEqual(0, cache._value_size)
 
353
        cache.add('my key', 'my value text')
 
354
        self.assertEqual(13, cache._value_size)
 
355
        node = cache._cache['my key']
 
356
        cache._remove_node(node)
 
357
        self.assertEqual(0, cache._value_size)
 
358
 
 
359
    def test_no_add_over_size(self):
 
360
        """Adding a large value may not be cached at all."""
 
361
        cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=5)
 
362
        self.assertEqual(0, cache._value_size)
 
363
        self.assertEqual({}, cache.items())
 
364
        cache.add('test', 'key')
 
365
        self.assertEqual(3, cache._value_size)
 
366
        self.assertEqual({'test': 'key'}, cache.items())
 
367
        cache.add('test2', 'key that is too big')
 
368
        self.assertEqual(3, cache._value_size)
 
369
        self.assertEqual({'test':'key'}, cache.items())
 
370
        # If we would add a key, only to cleanup and remove all cached entries,
 
371
        # then obviously that value should not be stored
 
372
        cache.add('test3', 'bigkey')
 
373
        self.assertEqual(3, cache._value_size)
 
374
        self.assertEqual({'test':'key'}, cache.items())
 
375
 
 
376
        cache.add('test4', 'bikey')
 
377
        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)
 
395
 
 
396
    def test_adding_clears_cache_based_on_size(self):
 
397
        """The cache is cleared in LRU order until small enough"""
 
398
        cache = lru_cache.LRUSizeCache(max_size=20)
 
399
        cache.add('key1', 'value') # 5 chars
 
400
        cache.add('key2', 'value2') # 6 chars
 
401
        cache.add('key3', 'value23') # 7 chars
 
402
        self.assertEqual(5+6+7, cache._value_size)
 
403
        cache['key2'] # reference key2 so it gets a newer reference time
 
404
        cache.add('key4', 'value234') # 8 chars, over limit
 
405
        # We have to remove 2 keys to get back under limit
 
406
        self.assertEqual(6+8, cache._value_size)
 
407
        self.assertEqual({'key2':'value2', 'key4':'value234'},
 
408
                         cache.items())
 
409
 
 
410
    def test_adding_clears_to_after_cleanup_size(self):
 
411
        cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
 
412
        cache.add('key1', 'value') # 5 chars
 
413
        cache.add('key2', 'value2') # 6 chars
 
414
        cache.add('key3', 'value23') # 7 chars
 
415
        self.assertEqual(5+6+7, cache._value_size)
 
416
        cache['key2'] # reference key2 so it gets a newer reference time
 
417
        cache.add('key4', 'value234') # 8 chars, over limit
 
418
        # We have to remove 3 keys to get back under limit
 
419
        self.assertEqual(8, cache._value_size)
 
420
        self.assertEqual({'key4':'value234'}, cache.items())
 
421
 
 
422
    def test_custom_sizes(self):
 
423
        def size_of_list(lst):
 
424
            return sum(len(x) for x in lst)
 
425
        cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10,
 
426
                                       compute_size=size_of_list)
 
427
 
 
428
        cache.add('key1', ['val', 'ue']) # 5 chars
 
429
        cache.add('key2', ['val', 'ue2']) # 6 chars
 
430
        cache.add('key3', ['val', 'ue23']) # 7 chars
 
431
        self.assertEqual(5+6+7, cache._value_size)
 
432
        cache['key2'] # reference key2 so it gets a newer reference time
 
433
        cache.add('key4', ['value', '234']) # 8 chars, over limit
 
434
        # We have to remove 3 keys to get back under limit
 
435
        self.assertEqual(8, cache._value_size)
 
436
        self.assertEqual({'key4':['value', '234']}, cache.items())
 
437
 
 
438
    def test_cleanup(self):
 
439
        cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
 
440
 
 
441
        # Add these in order
 
442
        cache.add('key1', 'value') # 5 chars
 
443
        cache.add('key2', 'value2') # 6 chars
 
444
        cache.add('key3', 'value23') # 7 chars
 
445
        self.assertEqual(5+6+7, cache._value_size)
 
446
 
 
447
        cache.cleanup()
 
448
        # Only the most recent fits after cleaning up
 
449
        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