dulwich/tests/test_lru_cache.py

   1 # Copyright (C) 2006, 2008 Canonical Ltd
   2 #
   3 # Dulwich is dual-licensed under the Apache License, Version 2.0 and the GNU
   4 # General Public License as public by the Free Software Foundation; version 2.0
   5 # or (at your option) any later version. You can redistribute it and/or
   6 # modify it under the terms of either of these two licenses.
   7 #
   8 # Unless required by applicable law or agreed to in writing, software
   9 # distributed under the License is distributed on an "AS IS" BASIS,
  10 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  11 # See the License for the specific language governing permissions and
  12 # limitations under the License.
  13 #
  14 # You should have received a copy of the licenses; if not, see
  15 # <http://www.gnu.org/licenses/> for a copy of the GNU General Public License
  16 # and <http://www.apache.org/licenses/LICENSE-2.0> for a copy of the Apache
  17 # License, Version 2.0.
  18 #
  19
  20 """Tests for the lru_cache module."""
  21
  22 from dulwich import (
  23     lru_cache,
  24     )
  25 from dulwich.tests import (
  26     TestCase,
  27     )
  28
  29
  30 class TestLRUCache(TestCase):
  31     """Test that LRU cache properly keeps track of entries."""
  32
  33     def test_cache_size(self):
  34         cache = lru_cache.LRUCache(max_cache=10)
  35         self.assertEqual(10, cache.cache_size())
  36
  37         cache = lru_cache.LRUCache(max_cache=256)
  38         self.assertEqual(256, cache.cache_size())
  39
  40         cache.resize(512)
  41         self.assertEqual(512, cache.cache_size())
  42
  43     def test_missing(self):
  44         cache = lru_cache.LRUCache(max_cache=10)
  45
  46         self.assertFalse('foo' in cache)
  47         self.assertRaises(KeyError, cache.__getitem__, 'foo')
  48
  49         cache['foo'] = 'bar'
  50         self.assertEqual('bar', cache['foo'])
  51         self.assertTrue('foo' in cache)
  52         self.assertFalse('bar' in cache)
  53
  54     def test_map_None(self):
  55         # Make sure that we can properly map None as a key.
  56         cache = lru_cache.LRUCache(max_cache=10)
  57         self.assertFalse(None in cache)
  58         cache[None] = 1
  59         self.assertEqual(1, cache[None])
  60         cache[None] = 2
  61         self.assertEqual(2, cache[None])
  62         # Test the various code paths of __getitem__, to make sure that we can
  63         # handle when None is the key for the LRU and the MRU
  64         cache[1] = 3
  65         cache[None] = 1
  66         cache[None]
  67         cache[1]
  68         cache[None]
  69         self.assertEqual([None, 1], [n.key for n in cache._walk_lru()])
  70
  71     def test_add__null_key(self):
  72         cache = lru_cache.LRUCache(max_cache=10)
  73         self.assertRaises(ValueError, cache.add, lru_cache._null_key, 1)
  74
  75     def test_overflow(self):
  76         """Adding extra entries will pop out old ones."""
  77         cache = lru_cache.LRUCache(max_cache=1, after_cleanup_count=1)
  78
  79         cache['foo'] = 'bar'
  80         # With a max cache of 1, adding 'baz' should pop out 'foo'
  81         cache['baz'] = 'biz'
  82
  83         self.assertFalse('foo' in cache)
  84         self.assertTrue('baz' in cache)
  85
  86         self.assertEqual('biz', cache['baz'])
  87
  88     def test_by_usage(self):
  89         """Accessing entries bumps them up in priority."""
  90         cache = lru_cache.LRUCache(max_cache=2)
  91
  92         cache['baz'] = 'biz'
  93         cache['foo'] = 'bar'
  94
  95         self.assertEqual('biz', cache['baz'])
  96
  97         # This must kick out 'foo' because it was the last accessed
  98         cache['nub'] = 'in'
  99
 100         self.assertFalse('foo' in cache)
 101
 102     def test_cleanup(self):
 103         """Test that we can use a cleanup function."""
 104         cleanup_called = []
 105
 106         def cleanup_func(key, val):
 107             cleanup_called.append((key, val))
 108
 109         cache = lru_cache.LRUCache(max_cache=2, after_cleanup_count=2)
 110
 111         cache.add('baz', '1', cleanup=cleanup_func)
 112         cache.add('foo', '2', cleanup=cleanup_func)
 113         cache.add('biz', '3', cleanup=cleanup_func)
 114
 115         self.assertEqual([('baz', '1')], cleanup_called)
 116
 117         # 'foo' is now most recent, so final cleanup will call it last
 118         cache['foo']
 119         cache.clear()
 120         self.assertEqual([('baz', '1'), ('biz', '3'), ('foo', '2')],
 121                          cleanup_called)
 122
 123     def test_cleanup_on_replace(self):
 124         """Replacing an object should cleanup the old value."""
 125         cleanup_called = []
 126
 127         def cleanup_func(key, val):
 128             cleanup_called.append((key, val))
 129
 130         cache = lru_cache.LRUCache(max_cache=2)
 131         cache.add(1, 10, cleanup=cleanup_func)
 132         cache.add(2, 20, cleanup=cleanup_func)
 133         cache.add(2, 25, cleanup=cleanup_func)
 134
 135         self.assertEqual([(2, 20)], cleanup_called)
 136         self.assertEqual(25, cache[2])
 137
 138         # Even __setitem__ should make sure cleanup() is called
 139         cache[2] = 26
 140         self.assertEqual([(2, 20), (2, 25)], cleanup_called)
 141
 142     def test_len(self):
 143         cache = lru_cache.LRUCache(max_cache=10, after_cleanup_count=10)
 144
 145         cache[1] = 10
 146         cache[2] = 20
 147         cache[3] = 30
 148         cache[4] = 40
 149
 150         self.assertEqual(4, len(cache))
 151
 152         cache[5] = 50
 153         cache[6] = 60
 154         cache[7] = 70
 155         cache[8] = 80
 156
 157         self.assertEqual(8, len(cache))
 158
 159         cache[1] = 15  # replacement
 160
 161         self.assertEqual(8, len(cache))
 162
 163         cache[9] = 90
 164         cache[10] = 100
 165         cache[11] = 110
 166
 167         # We hit the max
 168         self.assertEqual(10, len(cache))
 169         self.assertEqual([11, 10, 9, 1, 8, 7, 6, 5, 4, 3],
 170                          [n.key for n in cache._walk_lru()])
 171
 172     def test_cleanup_shrinks_to_after_clean_count(self):
 173         cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=3)
 174
 175         cache.add(1, 10)
 176         cache.add(2, 20)
 177         cache.add(3, 25)
 178         cache.add(4, 30)
 179         cache.add(5, 35)
 180
 181         self.assertEqual(5, len(cache))
 182         # This will bump us over the max, which causes us to shrink down to
 183         # after_cleanup_cache size
 184         cache.add(6, 40)
 185         self.assertEqual(3, len(cache))
 186
 187     def test_after_cleanup_larger_than_max(self):
 188         cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=10)
 189         self.assertEqual(5, cache._after_cleanup_count)
 190
 191     def test_after_cleanup_none(self):
 192         cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=None)
 193         # By default _after_cleanup_size is 80% of the normal size
 194         self.assertEqual(4, cache._after_cleanup_count)
 195
 196     def test_cleanup_2(self):
 197         cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=2)
 198
 199         # Add these in order
 200         cache.add(1, 10)
 201         cache.add(2, 20)
 202         cache.add(3, 25)
 203         cache.add(4, 30)
 204         cache.add(5, 35)
 205
 206         self.assertEqual(5, len(cache))
 207         # Force a compaction
 208         cache.cleanup()
 209         self.assertEqual(2, len(cache))
 210
 211     def test_preserve_last_access_order(self):
 212         cache = lru_cache.LRUCache(max_cache=5)
 213
 214         # Add these in order
 215         cache.add(1, 10)
 216         cache.add(2, 20)
 217         cache.add(3, 25)
 218         cache.add(4, 30)
 219         cache.add(5, 35)
 220
 221         self.assertEqual([5, 4, 3, 2, 1], [n.key for n in cache._walk_lru()])
 222
 223         # Now access some randomly
 224         cache[2]
 225         cache[5]
 226         cache[3]
 227         cache[2]
 228         self.assertEqual([2, 3, 5, 4, 1], [n.key for n in cache._walk_lru()])
 229
 230     def test_get(self):
 231         cache = lru_cache.LRUCache(max_cache=5)
 232
 233         cache.add(1, 10)
 234         cache.add(2, 20)
 235         self.assertEqual(20, cache.get(2))
 236         self.assertEqual(None, cache.get(3))
 237         obj = object()
 238         self.assertTrue(obj is cache.get(3, obj))
 239         self.assertEqual([2, 1], [n.key for n in cache._walk_lru()])
 240         self.assertEqual(10, cache.get(1))
 241         self.assertEqual([1, 2], [n.key for n in cache._walk_lru()])
 242
 243     def test_keys(self):
 244         cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=5)
 245
 246         cache[1] = 2
 247         cache[2] = 3
 248         cache[3] = 4
 249         self.assertEqual([1, 2, 3], sorted(cache.keys()))
 250         cache[4] = 5
 251         cache[5] = 6
 252         cache[6] = 7
 253         self.assertEqual([2, 3, 4, 5, 6], sorted(cache.keys()))
 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(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
 347         def cleanup(key, value):
 348             cleanup_calls.append((key, value))
 349
 350         cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=5)
 351         self.assertEqual(0, cache._value_size)
 352         self.assertEqual({}, cache.items())
 353         cache.add('test', 'key that is too big', cleanup=cleanup)
 354         # key was not added
 355         self.assertEqual(0, cache._value_size)
 356         self.assertEqual({}, cache.items())
 357         # and cleanup was called
 358         self.assertEqual([('test', 'key that is too big')], cleanup_calls)
 359
 360     def test_adding_clears_cache_based_on_size(self):
 361         """The cache is cleared in LRU order until small enough"""
 362         cache = lru_cache.LRUSizeCache(max_size=20)
 363         cache.add('key1', 'value')  # 5 chars
 364         cache.add('key2', 'value2')  # 6 chars
 365         cache.add('key3', 'value23')  # 7 chars
 366         self.assertEqual(5+6+7, cache._value_size)
 367         cache['key2']  # reference key2 so it gets a newer reference time
 368         cache.add('key4', 'value234')  # 8 chars, over limit
 369         # We have to remove 2 keys to get back under limit
 370         self.assertEqual(6+8, cache._value_size)
 371         self.assertEqual({'key2': 'value2', 'key4': 'value234'},
 372                          cache.items())
 373
 374     def test_adding_clears_to_after_cleanup_size(self):
 375         cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
 376         cache.add('key1', 'value')  # 5 chars
 377         cache.add('key2', 'value2')  # 6 chars
 378         cache.add('key3', 'value23')  # 7 chars
 379         self.assertEqual(5+6+7, cache._value_size)
 380         cache['key2']  # reference key2 so it gets a newer reference time
 381         cache.add('key4', 'value234')  # 8 chars, over limit
 382         # We have to remove 3 keys to get back under limit
 383         self.assertEqual(8, cache._value_size)
 384         self.assertEqual({'key4': 'value234'}, cache.items())
 385
 386     def test_custom_sizes(self):
 387         def size_of_list(lst):
 388             return sum(len(x) for x in lst)
 389         cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10,
 390                                        compute_size=size_of_list)
 391
 392         cache.add('key1', ['val', 'ue'])  # 5 chars
 393         cache.add('key2', ['val', 'ue2'])  # 6 chars
 394         cache.add('key3', ['val', 'ue23'])  # 7 chars
 395         self.assertEqual(5+6+7, cache._value_size)
 396         cache['key2']  # reference key2 so it gets a newer reference time
 397         cache.add('key4', ['value', '234'])  # 8 chars, over limit
 398         # We have to remove 3 keys to get back under limit
 399         self.assertEqual(8, cache._value_size)
 400         self.assertEqual({'key4': ['value', '234']}, cache.items())
 401
 402     def test_cleanup(self):
 403         cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
 404
 405         # Add these in order
 406         cache.add('key1', 'value')  # 5 chars
 407         cache.add('key2', 'value2')  # 6 chars
 408         cache.add('key3', 'value23')  # 7 chars
 409         self.assertEqual(5+6+7, cache._value_size)
 410
 411         cache.cleanup()
 412         # Only the most recent fits after cleaning up
 413         self.assertEqual(7, cache._value_size)
 414
 415     def test_keys(self):
 416         cache = lru_cache.LRUSizeCache(max_size=10)
 417
 418         cache[1] = 'a'
 419         cache[2] = 'b'
 420         cache[3] = 'cdef'
 421         self.assertEqual([1, 2, 3], sorted(cache.keys()))
 422
 423     def test_resize_smaller(self):
 424         cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=9)
 425         cache[1] = 'abc'
 426         cache[2] = 'def'
 427         cache[3] = 'ghi'
 428         cache[4] = 'jkl'
 429         # Triggers a cleanup
 430         self.assertEqual([2, 3, 4], sorted(cache.keys()))
 431         # Resize should also cleanup again
 432         cache.resize(max_size=6, after_cleanup_size=4)
 433         self.assertEqual([4], sorted(cache.keys()))
 434         # Adding should use the new max size
 435         cache[5] = 'mno'
 436         self.assertEqual([4, 5], sorted(cache.keys()))
 437         cache[6] = 'pqr'
 438         self.assertEqual([6], sorted(cache.keys()))
 439
 440     def test_resize_larger(self):
 441         cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=9)
 442         cache[1] = 'abc'
 443         cache[2] = 'def'
 444         cache[3] = 'ghi'
 445         cache[4] = 'jkl'
 446         # Triggers a cleanup
 447         self.assertEqual([2, 3, 4], sorted(cache.keys()))
 448         cache.resize(max_size=15, after_cleanup_size=12)
 449         self.assertEqual([2, 3, 4], sorted(cache.keys()))
 450         cache[5] = 'mno'
 451         cache[6] = 'pqr'
 452         self.assertEqual([2, 3, 4, 5, 6], sorted(cache.keys()))
 453         cache[7] = 'stu'
 454         self.assertEqual([4, 5, 6, 7], sorted(cache.keys()))