/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-06-18 18:18:36 UTC
  • mto: This revision was merged to the branch mainline in revision 4461.
  • Revision ID: john@arbash-meinel.com-20090618181836-biodfkat9a8eyzjz
The new add_inventory_by_delta is returning a CHKInventory when mapping from NULL
Which is completely valid, but 'broke' one of the tests.
So to fix it, changed the test to use CHKInventories on both sides, and add an __eq__
member. The nice thing is that CHKInventory.__eq__ is fairly cheap, since it only
has to check the root keys.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_lru_cache.py
 
1
# Copyright (C) 2006, 2008 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_len(self):
 
136
        cache = lru_cache.LRUCache(max_cache=10, after_cleanup_count=10)
 
137
 
 
138
        cache[1] = 10
 
139
        cache[2] = 20
 
140
        cache[3] = 30
 
141
        cache[4] = 40
 
142
 
 
143
        self.assertEqual(4, len(cache))
 
144
 
 
145
        cache[5] = 50
 
146
        cache[6] = 60
 
147
        cache[7] = 70
 
148
        cache[8] = 80
 
149
 
 
150
        self.assertEqual(8, len(cache))
 
151
 
 
152
        cache[1] = 15 # replacement
 
153
 
 
154
        self.assertEqual(8, len(cache))
 
155
 
 
156
        cache[9] = 90
 
157
        cache[10] = 100
 
158
        cache[11] = 110
 
159
 
 
160
        # We hit the max
 
161
        self.assertEqual(10, len(cache))
 
162
        self.assertEqual([11, 10, 9, 1, 8, 7, 6, 5, 4, 3],
 
163
                         [n.key for n in cache._walk_lru()])
 
164
 
 
165
    def test_cleanup_shrinks_to_after_clean_count(self):
 
166
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=3)
 
167
 
 
168
        cache.add(1, 10)
 
169
        cache.add(2, 20)
 
170
        cache.add(3, 25)
 
171
        cache.add(4, 30)
 
172
        cache.add(5, 35)
 
173
 
 
174
        self.assertEqual(5, len(cache))
 
175
        # This will bump us over the max, which causes us to shrink down to
 
176
        # after_cleanup_cache size
 
177
        cache.add(6, 40)
 
178
        self.assertEqual(3, len(cache))
 
179
 
 
180
    def test_after_cleanup_larger_than_max(self):
 
181
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=10)
 
182
        self.assertEqual(5, cache._after_cleanup_count)
 
183
 
 
184
    def test_after_cleanup_none(self):
 
185
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=None)
 
186
        # By default _after_cleanup_size is 80% of the normal size
 
187
        self.assertEqual(4, cache._after_cleanup_count)
 
188
 
 
189
    def test_cleanup(self):
 
190
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=2)
 
191
 
 
192
        # Add these in order
 
193
        cache.add(1, 10)
 
194
        cache.add(2, 20)
 
195
        cache.add(3, 25)
 
196
        cache.add(4, 30)
 
197
        cache.add(5, 35)
 
198
 
 
199
        self.assertEqual(5, len(cache))
 
200
        # Force a compaction
 
201
        cache.cleanup()
 
202
        self.assertEqual(2, len(cache))
 
203
 
 
204
    def test_preserve_last_access_order(self):
 
205
        cache = lru_cache.LRUCache(max_cache=5)
 
206
 
 
207
        # Add these in order
 
208
        cache.add(1, 10)
 
209
        cache.add(2, 20)
 
210
        cache.add(3, 25)
 
211
        cache.add(4, 30)
 
212
        cache.add(5, 35)
 
213
 
 
214
        self.assertEqual([5, 4, 3, 2, 1], [n.key for n in cache._walk_lru()])
 
215
 
 
216
        # Now access some randomly
 
217
        cache[2]
 
218
        cache[5]
 
219
        cache[3]
 
220
        cache[2]
 
221
        self.assertEqual([2, 3, 5, 4, 1], [n.key for n in cache._walk_lru()])
 
222
 
 
223
    def test_get(self):
 
224
        cache = lru_cache.LRUCache(max_cache=5)
 
225
 
 
226
        cache.add(1, 10)
 
227
        cache.add(2, 20)
 
228
        self.assertEqual(20, cache.get(2))
 
229
        self.assertIs(None, cache.get(3))
 
230
        obj = object()
 
231
        self.assertIs(obj, cache.get(3, obj))
 
232
        self.assertEqual([2, 1], [n.key for n in cache._walk_lru()])
 
233
        self.assertEqual(10, cache.get(1))
 
234
        self.assertEqual([1, 2], [n.key for n in cache._walk_lru()])
 
235
 
 
236
    def test_keys(self):
 
237
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=5)
 
238
 
 
239
        cache[1] = 2
 
240
        cache[2] = 3
 
241
        cache[3] = 4
 
242
        self.assertEqual([1, 2, 3], sorted(cache.keys()))
 
243
        cache[4] = 5
 
244
        cache[5] = 6
 
245
        cache[6] = 7
 
246
        self.assertEqual([2, 3, 4, 5, 6], sorted(cache.keys()))
 
247
 
 
248
    def test_after_cleanup_size_deprecated(self):
 
249
        obj = self.callDeprecated([
 
250
            'LRUCache.__init__(after_cleanup_size) was deprecated in 1.11.'
 
251
            ' Use after_cleanup_count instead.'],
 
252
            lru_cache.LRUCache, 50, after_cleanup_size=25)
 
253
        self.assertEqual(obj._after_cleanup_count, 25)
 
254
 
 
255
    def test_resize_smaller(self):
 
256
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=4)
 
257
        cache[1] = 2
 
258
        cache[2] = 3
 
259
        cache[3] = 4
 
260
        cache[4] = 5
 
261
        cache[5] = 6
 
262
        self.assertEqual([1, 2, 3, 4, 5], sorted(cache.keys()))
 
263
        cache[6] = 7
 
264
        self.assertEqual([3, 4, 5, 6], sorted(cache.keys()))
 
265
        # Now resize to something smaller, which triggers a cleanup
 
266
        cache.resize(max_cache=3, after_cleanup_count=2)
 
267
        self.assertEqual([5, 6], sorted(cache.keys()))
 
268
        # Adding something will use the new size
 
269
        cache[7] = 8
 
270
        self.assertEqual([5, 6, 7], sorted(cache.keys()))
 
271
        cache[8] = 9
 
272
        self.assertEqual([7, 8], sorted(cache.keys()))
 
273
 
 
274
    def test_resize_larger(self):
 
275
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=4)
 
276
        cache[1] = 2
 
277
        cache[2] = 3
 
278
        cache[3] = 4
 
279
        cache[4] = 5
 
280
        cache[5] = 6
 
281
        self.assertEqual([1, 2, 3, 4, 5], sorted(cache.keys()))
 
282
        cache[6] = 7
 
283
        self.assertEqual([3, 4, 5, 6], sorted(cache.keys()))
 
284
        cache.resize(max_cache=8, after_cleanup_count=6)
 
285
        self.assertEqual([3, 4, 5, 6], sorted(cache.keys()))
 
286
        cache[7] = 8
 
287
        cache[8] = 9
 
288
        cache[9] = 10
 
289
        cache[10] = 11
 
290
        self.assertEqual([3, 4, 5, 6, 7, 8, 9, 10], sorted(cache.keys()))
 
291
        cache[11] = 12 # triggers cleanup back to new after_cleanup_count
 
292
        self.assertEqual([6, 7, 8, 9, 10, 11], sorted(cache.keys()))
 
293
 
 
294
 
 
295
class TestLRUSizeCache(tests.TestCase):
 
296
 
 
297
    def test_basic_init(self):
 
298
        cache = lru_cache.LRUSizeCache()
 
299
        self.assertEqual(2048, cache._max_cache)
 
300
        self.assertEqual(int(cache._max_size*0.8), cache._after_cleanup_size)
 
301
        self.assertEqual(0, cache._value_size)
 
302
 
 
303
    def test_add__null_key(self):
 
304
        cache = lru_cache.LRUSizeCache()
 
305
        self.assertRaises(ValueError, cache.add, lru_cache._null_key, 1)
 
306
 
 
307
    def test_add_tracks_size(self):
 
308
        cache = lru_cache.LRUSizeCache()
 
309
        self.assertEqual(0, cache._value_size)
 
310
        cache.add('my key', 'my value text')
 
311
        self.assertEqual(13, cache._value_size)
 
312
 
 
313
    def test_remove_tracks_size(self):
 
314
        cache = lru_cache.LRUSizeCache()
 
315
        self.assertEqual(0, cache._value_size)
 
316
        cache.add('my key', 'my value text')
 
317
        self.assertEqual(13, cache._value_size)
 
318
        node = cache._cache['my key']
 
319
        cache._remove_node(node)
 
320
        self.assertEqual(0, cache._value_size)
 
321
 
 
322
    def test_no_add_over_size(self):
 
323
        """Adding a large value may not be cached at all."""
 
324
        cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=5)
 
325
        self.assertEqual(0, cache._value_size)
 
326
        self.assertEqual({}, cache.items())
 
327
        cache.add('test', 'key')
 
328
        self.assertEqual(3, cache._value_size)
 
329
        self.assertEqual({'test': 'key'}, cache.items())
 
330
        cache.add('test2', 'key that is too big')
 
331
        self.assertEqual(3, cache._value_size)
 
332
        self.assertEqual({'test':'key'}, cache.items())
 
333
        # If we would add a key, only to cleanup and remove all cached entries,
 
334
        # then obviously that value should not be stored
 
335
        cache.add('test3', 'bigkey')
 
336
        self.assertEqual(3, cache._value_size)
 
337
        self.assertEqual({'test':'key'}, cache.items())
 
338
 
 
339
        cache.add('test4', 'bikey')
 
340
        self.assertEqual(3, cache._value_size)
 
341
        self.assertEqual({'test':'key'}, cache.items())
 
342
 
 
343
    def test_no_add_over_size_cleanup(self):
 
344
        """If a large value is not cached, we will call cleanup right away."""
 
345
        cleanup_calls = []
 
346
        def cleanup(key, value):
 
347
            cleanup_calls.append((key, value))
 
348
 
 
349
        cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=5)
 
350
        self.assertEqual(0, cache._value_size)
 
351
        self.assertEqual({}, cache.items())
 
352
        cache.add('test', 'key that is too big', cleanup=cleanup)
 
353
        # key was not added
 
354
        self.assertEqual(0, cache._value_size)
 
355
        self.assertEqual({}, cache.items())
 
356
        # and cleanup was called
 
357
        self.assertEqual([('test', 'key that is too big')], cleanup_calls)
 
358
 
 
359
    def test_adding_clears_cache_based_on_size(self):
 
360
        """The cache is cleared in LRU order until small enough"""
 
361
        cache = lru_cache.LRUSizeCache(max_size=20)
 
362
        cache.add('key1', 'value') # 5 chars
 
363
        cache.add('key2', 'value2') # 6 chars
 
364
        cache.add('key3', 'value23') # 7 chars
 
365
        self.assertEqual(5+6+7, cache._value_size)
 
366
        cache['key2'] # reference key2 so it gets a newer reference time
 
367
        cache.add('key4', 'value234') # 8 chars, over limit
 
368
        # We have to remove 2 keys to get back under limit
 
369
        self.assertEqual(6+8, cache._value_size)
 
370
        self.assertEqual({'key2':'value2', 'key4':'value234'},
 
371
                         cache.items())
 
372
 
 
373
    def test_adding_clears_to_after_cleanup_size(self):
 
374
        cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
 
375
        cache.add('key1', 'value') # 5 chars
 
376
        cache.add('key2', 'value2') # 6 chars
 
377
        cache.add('key3', 'value23') # 7 chars
 
378
        self.assertEqual(5+6+7, cache._value_size)
 
379
        cache['key2'] # reference key2 so it gets a newer reference time
 
380
        cache.add('key4', 'value234') # 8 chars, over limit
 
381
        # We have to remove 3 keys to get back under limit
 
382
        self.assertEqual(8, cache._value_size)
 
383
        self.assertEqual({'key4':'value234'}, cache.items())
 
384
 
 
385
    def test_custom_sizes(self):
 
386
        def size_of_list(lst):
 
387
            return sum(len(x) for x in lst)
 
388
        cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10,
 
389
                                       compute_size=size_of_list)
 
390
 
 
391
        cache.add('key1', ['val', 'ue']) # 5 chars
 
392
        cache.add('key2', ['val', 'ue2']) # 6 chars
 
393
        cache.add('key3', ['val', 'ue23']) # 7 chars
 
394
        self.assertEqual(5+6+7, cache._value_size)
 
395
        cache['key2'] # reference key2 so it gets a newer reference time
 
396
        cache.add('key4', ['value', '234']) # 8 chars, over limit
 
397
        # We have to remove 3 keys to get back under limit
 
398
        self.assertEqual(8, cache._value_size)
 
399
        self.assertEqual({'key4':['value', '234']}, cache.items())
 
400
 
 
401
    def test_cleanup(self):
 
402
        cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
 
403
 
 
404
        # Add these in order
 
405
        cache.add('key1', 'value') # 5 chars
 
406
        cache.add('key2', 'value2') # 6 chars
 
407
        cache.add('key3', 'value23') # 7 chars
 
408
        self.assertEqual(5+6+7, cache._value_size)
 
409
 
 
410
        cache.cleanup()
 
411
        # Only the most recent fits after cleaning up
 
412
        self.assertEqual(7, cache._value_size)
 
413
 
 
414
    def test_keys(self):
 
415
        cache = lru_cache.LRUSizeCache(max_size=10)
 
416
 
 
417
        cache[1] = 'a'
 
418
        cache[2] = 'b'
 
419
        cache[3] = 'cdef'
 
420
        self.assertEqual([1, 2, 3], sorted(cache.keys()))
 
421
 
 
422
    def test_resize_smaller(self):
 
423
        cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=9)
 
424
        cache[1] = 'abc'
 
425
        cache[2] = 'def'
 
426
        cache[3] = 'ghi'
 
427
        cache[4] = 'jkl'
 
428
        # Triggers a cleanup
 
429
        self.assertEqual([2, 3, 4], sorted(cache.keys()))
 
430
        # Resize should also cleanup again
 
431
        cache.resize(max_size=6, after_cleanup_size=4)
 
432
        self.assertEqual([4], sorted(cache.keys()))
 
433
        # Adding should use the new max size
 
434
        cache[5] = 'mno'
 
435
        self.assertEqual([4, 5], sorted(cache.keys()))
 
436
        cache[6] = 'pqr'
 
437
        self.assertEqual([6], sorted(cache.keys()))
 
438
 
 
439
    def test_resize_larger(self):
 
440
        cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=9)
 
441
        cache[1] = 'abc'
 
442
        cache[2] = 'def'
 
443
        cache[3] = 'ghi'
 
444
        cache[4] = 'jkl'
 
445
        # Triggers a cleanup
 
446
        self.assertEqual([2, 3, 4], sorted(cache.keys()))
 
447
        cache.resize(max_size=15, after_cleanup_size=12)
 
448
        self.assertEqual([2, 3, 4], sorted(cache.keys()))
 
449
        cache[5] = 'mno'
 
450
        cache[6] = 'pqr'
 
451
        self.assertEqual([2, 3, 4, 5, 6], sorted(cache.keys()))
 
452
        cache[7] = 'stu'
 
453
        self.assertEqual([4, 5, 6, 7], sorted(cache.keys()))
 
454