/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: 2008-08-18 22:34:21 UTC
  • mto: (3606.5.6 1.6)
  • mto: This revision was merged to the branch mainline in revision 3641.
  • Revision ID: john@arbash-meinel.com-20080818223421-todjny24vj4faj4t
Add tests for the fetching behavior.

The proper parameter passed is 'unordered' add an assert for it, and
fix callers that were passing 'unsorted' instead.
Add tests that we make the right get_record_stream call based
on the value of _fetch_uses_deltas.
Fix the fetch request for signatures.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_lru_cache.py
 
1
# Copyright (C) 2006 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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_missing(self):
 
29
        cache = lru_cache.LRUCache(max_cache=10)
 
30
 
 
31
        self.failIf('foo' in cache)
 
32
        self.assertRaises(KeyError, cache.__getitem__, 'foo')
 
33
 
 
34
        cache['foo'] = 'bar'
 
35
        self.assertEqual('bar', cache['foo'])
 
36
        self.failUnless('foo' in cache)
 
37
        self.failIf('bar' in cache)
 
38
 
 
39
    def test_overflow(self):
 
40
        """Adding extra entries will pop out old ones."""
 
41
        cache = lru_cache.LRUCache(max_cache=1)
 
42
 
 
43
        cache['foo'] = 'bar'
 
44
        # With a max cache of 1, adding 'baz' should pop out 'foo'
 
45
        cache['baz'] = 'biz'
 
46
 
 
47
        self.failIf('foo' in cache)
 
48
        self.failUnless('baz' in cache)
 
49
 
 
50
        self.assertEqual('biz', cache['baz'])
 
51
 
 
52
    def test_by_usage(self):
 
53
        """Accessing entries bumps them up in priority."""
 
54
        cache = lru_cache.LRUCache(max_cache=2)
 
55
 
 
56
        cache['baz'] = 'biz'
 
57
        cache['foo'] = 'bar'
 
58
 
 
59
        self.assertEqual('biz', cache['baz'])
 
60
 
 
61
        # This must kick out 'foo' because it was the last accessed
 
62
        cache['nub'] = 'in'
 
63
 
 
64
        self.failIf('foo' in cache)
 
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
 
 
78
    def test_cleanup(self):
 
79
        """Test that we can use a cleanup function."""
 
80
        cleanup_called = []
 
81
        def cleanup_func(key, val):
 
82
            cleanup_called.append((key, val))
 
83
 
 
84
        cache = lru_cache.LRUCache(max_cache=2)
 
85
 
 
86
        cache.add('baz', '1', cleanup=cleanup_func)
 
87
        cache.add('foo', '2', cleanup=cleanup_func)
 
88
        cache.add('biz', '3', cleanup=cleanup_func)
 
89
 
 
90
        self.assertEqual([('baz', '1')], cleanup_called)
 
91
 
 
92
        # 'foo' is now most recent, so final cleanup will call it last
 
93
        cache['foo']
 
94
        cache.clear()
 
95
        self.assertEqual([('baz', '1'), ('biz', '3'), ('foo', '2')], cleanup_called)
 
96
 
 
97
    def test_cleanup_on_replace(self):
 
98
        """Replacing an object should cleanup the old value."""
 
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
        cache.add(1, 10, cleanup=cleanup_func)
 
105
        cache.add(2, 20, cleanup=cleanup_func)
 
106
        cache.add(2, 25, cleanup=cleanup_func)
 
107
 
 
108
        self.assertEqual([(2, 20)], cleanup_called)
 
109
        self.assertEqual(25, cache[2])
 
110
        
 
111
        # Even __setitem__ should make sure cleanup() is called
 
112
        cache[2] = 26
 
113
        self.assertEqual([(2, 20), (2, 25)], cleanup_called)
 
114
 
 
115
    def test_len(self):
 
116
        cache = lru_cache.LRUCache(max_cache=10)
 
117
 
 
118
        cache[1] = 10
 
119
        cache[2] = 20
 
120
        cache[3] = 30
 
121
        cache[4] = 40
 
122
 
 
123
        self.assertEqual(4, len(cache))
 
124
 
 
125
        cache[5] = 50
 
126
        cache[6] = 60
 
127
        cache[7] = 70
 
128
        cache[8] = 80
 
129
 
 
130
        self.assertEqual(8, len(cache))
 
131
 
 
132
        cache[1] = 15 # replacement
 
133
 
 
134
        self.assertEqual(8, len(cache))
 
135
 
 
136
        cache[9] = 90
 
137
        cache[10] = 100
 
138
        cache[11] = 110
 
139
 
 
140
        # We hit the max
 
141
        self.assertEqual(10, len(cache))
 
142
 
 
143
    def test_cleanup_shrinks_to_after_clean_size(self):
 
144
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_size=3)
 
145
 
 
146
        cache.add(1, 10)
 
147
        cache.add(2, 20)
 
148
        cache.add(3, 25)
 
149
        cache.add(4, 30)
 
150
        cache.add(5, 35)
 
151
 
 
152
        self.assertEqual(5, len(cache))
 
153
        # This will bump us over the max, which causes us to shrink down to
 
154
        # after_cleanup_cache size
 
155
        cache.add(6, 40)
 
156
        self.assertEqual(3, len(cache))
 
157
 
 
158
    def test_after_cleanup_larger_than_max(self):
 
159
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_size=10)
 
160
        self.assertEqual(5, cache._after_cleanup_size)
 
161
 
 
162
    def test_after_cleanup_none(self):
 
163
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_size=None)
 
164
        self.assertEqual(5, cache._after_cleanup_size)
 
165
 
 
166
    def test_cleanup(self):
 
167
        cache = lru_cache.LRUCache(max_cache=5, after_cleanup_size=2)
 
168
 
 
169
        # Add these in order
 
170
        cache.add(1, 10)
 
171
        cache.add(2, 20)
 
172
        cache.add(3, 25)
 
173
        cache.add(4, 30)
 
174
        cache.add(5, 35)
 
175
 
 
176
        self.assertEqual(5, len(cache))
 
177
        # Force a compaction
 
178
        cache.cleanup()
 
179
        self.assertEqual(2, len(cache))
 
180
 
 
181
    def test_compact_preserves_last_access_order(self):
 
182
        cache = lru_cache.LRUCache(max_cache=5)
 
183
 
 
184
        # Add these in order
 
185
        cache.add(1, 10)
 
186
        cache.add(2, 20)
 
187
        cache.add(3, 25)
 
188
        cache.add(4, 30)
 
189
        cache.add(5, 35)
 
190
 
 
191
        self.assertEqual([1, 2, 3, 4, 5], list(cache._queue))
 
192
 
 
193
        # Now access some randomly
 
194
        cache[2]
 
195
        cache[5]
 
196
        cache[3]
 
197
        cache[2]
 
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)
 
205
 
 
206
    def test_get(self):
 
207
        cache = lru_cache.LRUCache(max_cache=5)
 
208
 
 
209
        cache.add(1, 10)
 
210
        cache.add(2, 20)
 
211
        self.assertEqual(20, cache.get(2))
 
212
        self.assertIs(None, cache.get(3))
 
213
        obj = object()
 
214
        self.assertIs(obj, cache.get(3, obj))
 
215
 
 
216
 
 
217
class TestLRUSizeCache(tests.TestCase):
 
218
 
 
219
    def test_basic_init(self):
 
220
        cache = lru_cache.LRUSizeCache()
 
221
        self.assertEqual(2048, cache._max_cache)
 
222
        self.assertEqual(4*2048, cache._compact_queue_length)
 
223
        self.assertEqual(cache._max_size, cache._after_cleanup_size)
 
224
        self.assertEqual(0, cache._value_size)
 
225
 
 
226
    def test_add_tracks_size(self):
 
227
        cache = lru_cache.LRUSizeCache()
 
228
        self.assertEqual(0, cache._value_size)
 
229
        cache.add('my key', 'my value text')
 
230
        self.assertEqual(13, cache._value_size)
 
231
 
 
232
    def test_remove_tracks_size(self):
 
233
        cache = lru_cache.LRUSizeCache()
 
234
        self.assertEqual(0, cache._value_size)
 
235
        cache.add('my key', 'my value text')
 
236
        self.assertEqual(13, cache._value_size)
 
237
        cache._remove('my key')
 
238
        self.assertEqual(0, cache._value_size)
 
239
 
 
240
    def test_no_add_over_size(self):
 
241
        """Adding a large value may not be cached at all."""
 
242
        cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=5)
 
243
        self.assertEqual(0, cache._value_size)
 
244
        self.assertEqual({}, cache._cache)
 
245
        cache.add('test', 'key')
 
246
        self.assertEqual(3, cache._value_size)
 
247
        self.assertEqual({'test':'key'}, cache._cache)
 
248
        cache.add('test2', 'key that is too big')
 
249
        self.assertEqual(3, cache._value_size)
 
250
        self.assertEqual({'test':'key'}, cache._cache)
 
251
        # If we would add a key, only to cleanup and remove all cached entries,
 
252
        # then obviously that value should not be stored
 
253
        cache.add('test3', 'bigkey')
 
254
        self.assertEqual(3, cache._value_size)
 
255
        self.assertEqual({'test':'key'}, cache._cache)
 
256
 
 
257
        cache.add('test4', 'bikey')
 
258
        self.assertEqual(3, cache._value_size)
 
259
        self.assertEqual({'test':'key'}, cache._cache)
 
260
 
 
261
    def test_adding_clears_cache_based_on_size(self):
 
262
        """The cache is cleared in LRU order until small enough"""
 
263
        cache = lru_cache.LRUSizeCache(max_size=20)
 
264
        cache.add('key1', 'value') # 5 chars
 
265
        cache.add('key2', 'value2') # 6 chars
 
266
        cache.add('key3', 'value23') # 7 chars
 
267
        self.assertEqual(5+6+7, cache._value_size)
 
268
        cache['key2'] # reference key2 so it gets a newer reference time
 
269
        cache.add('key4', 'value234') # 8 chars, over limit
 
270
        # We have to remove 2 keys to get back under limit
 
271
        self.assertEqual(6+8, cache._value_size)
 
272
        self.assertEqual({'key2':'value2', 'key4':'value234'},
 
273
                         cache._cache)
 
274
 
 
275
    def test_adding_clears_to_after_cleanup_size(self):
 
276
        cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
 
277
        cache.add('key1', 'value') # 5 chars
 
278
        cache.add('key2', 'value2') # 6 chars
 
279
        cache.add('key3', 'value23') # 7 chars
 
280
        self.assertEqual(5+6+7, cache._value_size)
 
281
        cache['key2'] # reference key2 so it gets a newer reference time
 
282
        cache.add('key4', 'value234') # 8 chars, over limit
 
283
        # We have to remove 3 keys to get back under limit
 
284
        self.assertEqual(8, cache._value_size)
 
285
        self.assertEqual({'key4':'value234'}, cache._cache)
 
286
 
 
287
    def test_custom_sizes(self):
 
288
        def size_of_list(lst):
 
289
            return sum(len(x) for x in lst)
 
290
        cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10,
 
291
                                       compute_size=size_of_list)
 
292
 
 
293
        cache.add('key1', ['val', 'ue']) # 5 chars
 
294
        cache.add('key2', ['val', 'ue2']) # 6 chars
 
295
        cache.add('key3', ['val', 'ue23']) # 7 chars
 
296
        self.assertEqual(5+6+7, cache._value_size)
 
297
        cache['key2'] # reference key2 so it gets a newer reference time
 
298
        cache.add('key4', ['value', '234']) # 8 chars, over limit
 
299
        # We have to remove 3 keys to get back under limit
 
300
        self.assertEqual(8, cache._value_size)
 
301
        self.assertEqual({'key4':['value', '234']}, cache._cache)
 
302
 
 
303
    def test_cleanup(self):
 
304
        cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
 
305
 
 
306
        # Add these in order
 
307
        cache.add('key1', 'value') # 5 chars
 
308
        cache.add('key2', 'value2') # 6 chars
 
309
        cache.add('key3', 'value23') # 7 chars
 
310
        self.assertEqual(5+6+7, cache._value_size)
 
311
 
 
312
        cache.cleanup()
 
313
        # Only the most recent fits after cleaning up
 
314
        self.assertEqual(7, cache._value_size)