Merge lp:~gz/bzr/lru_cache_refactor into lp:bzr

[Martin Packman]

Refactor and deprecate unused parts of lru_cache

Remove some complications from bzrlib.lru_cache that made it harder for me to understand. There should be no functional change for Bazaar.

The LRUCache and LRUSize cache objects basically act like dicts, but may also evict items if a threshold is passed, starting with those touched 'least recently'.

The branch addresses the following wrinkles:

* Deprecates the `items` method that doesn't return a list of 2-tuples. This seems to be mostly for test usage so has been renamed to `as_dict` which is what it actually does.

* There's a test helper method `walk_lru` that may as well live with the tests.

* Given that usage of LRUSizeCache in bzrlib sensibly sticks to using to store simple immutable (or sort of at least, GroupCompressBlock is a bit odd) objects, their size may as well be recalculated on eviction. This is a judgement call, given bad objects that change size this could make caches behave oddly. That's already the case if given a `_compute_size` function that returns funny values.

* Remove per-node callback functions. Given that bzrlib has no callers that want this, and to work properly they need a fair bit of fixing, this seems like the simplest option. In short, the issues are:

** The nomenclature is confusing. The caches have a cleanup method, and their nodes have a cleanup slot that calling cleanup may, or may not, call.

** LRUSizeCache.add doesn't do the right thing with cleanup callbacks. It uses the one passed in with the new node if an old node is being replaced and there's not room for the new node, rather than the function from the slot. Otherwise when replacing a node, it doesn't call cleanup on the old node at all.

** The cleanup is per-node, but even the tests for it use it for a per-cache callback only.

** It'd be risky anyway to put things that need explict finalizing in a cache like this which may keep them alive indefinitely.

** The `add` method that exposed the cleanup object has been deprecated in favour of just using the dict-style access that nearly all callers use anyway. This avoids mixing up the check for removed functionality with live code.

** It seems that bzrlib.fifo_cache has a similar cleanup callback interface, but if it's not being used for lru_cache I see no reason to keep it around.

** I tried having a test-only cache with a cleanup callback, but basically the tests that need it are only testing things to do with the callback, the other tests do well enough at ensuring the caches behave in a sane manner.

[Jelmer Vernooij (jelmer)]

> * Deprecates the `items` method that doesn't return a list of 2-tuples. This seems to be mostly for test usage so has been renamed to `as_dict` which is what it actually does.
This (and the deprecation of 'add') seems like a worthwhile thing to document in the release notes, in case external users rely on it. bzr-git uses LRUSizeCache for example.

In general, this seems like a reasonable cleanup (excuse the pun :-P). Perhaps it would be good if somebody who has more experience with this code could also have a look at the API changes though.

review: Approve

[Martin Packman (gz)]

> This (and the deprecation of 'add') seems like a worthwhile thing to document
> in the release notes, in case external users rely on it. bzr-git uses
> LRUSizeCache for example.

Noted. I take it bzr-git just uses LRUSizeCache as a dict like everything else?

> In general, this seems like a reasonable cleanup (excuse the pun :-P).

More puns please!

[John A Meinel (jameinel)]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 10/14/2011 10:12 PM, Martin Packman wrote:
> Martin Packman has proposed merging lp:~gz/bzr/lru_cache_refactor
> into lp:bzr.
>
> Requested reviews: bzr-core (bzr-core)
>
> For more details, see:
> https://code.launchpad.net/~gz/bzr/lru_cache_refactor/+merge/79439
>
> Remove some complications from bzrlib.lru_cache that made it harder
> for me to understand. There should be no functional change for
> Bazaar.
>
> The LRUCache and LRUSize cache objects basically act like dicts,
> but may also evict items if a threshold is passed, starting with
> those touched 'least recently'.
>
>
> The branch addresses the following wrinkles:
>
> * Deprecates the `items` method that doesn't return a list of
> 2-tuples. This seems to be mostly for test usage so has been
> renamed to `as_dict` which is what it actually does.
>
> * There's a test helper method `walk_lru` that may as well live
> with the tests.
>
> * Given that usage of LRUSizeCache in bzrlib sensibly sticks to
> using to store simple immutable (or sort of at least,
> GroupCompressBlock is a bit odd) objects, their size may as well be
> recalculated on eviction. This is a judgement call, given bad
> objects that change size this could make caches behave oddly.
> That's already the case if given a `_compute_size` function that
> returns funny values.

If something's size does change, then this quickly messes up the size
tracking. I think it is reasonable to eject an item with the size that
you added it.

>
> * Remove per-node callback functions. Given that bzrlib has no
> callers that want this, and to work properly they need a fair bit
> of fixing, this seems like the simplest option. In short, the
> issues are:
>

I do believe there is already 3rd party code (Launchpad, loggerhead?)
that makes use of this. bzr-cvsps-import I think also uses it.

John
=:->

> ** The nomenclature is confusing. The caches have a cleanup method,
> and their nodes have a cleanup slot that calling cleanup may, or
> may not, call.
>
> ** LRUSizeCache.add doesn't do the right thing with cleanup
> callbacks. It uses the one passed in with the new node if an old
> node is being replaced and there's not room for the new node,
> rather than the function from the slot. Otherwise when replacing a
> node, it doesn't call cleanup on the old node at all.
>
> ** The cleanup is per-node, but even the tests for it use it for a
> per-cache callback only.

bzr-cvsps-import passes in Branch objects, and uses their
Branch.unlock() as the cleanup callback. Which does use a per-node
callback (every branch's unlock is different). We can certainly update
the tests to reflect this.

>
> ** It'd be risky anyway to put things that need explict finalizing
> in a cache like this which may keep them alive indefinitely.
>
> ** The `add` method that exposed the cleanup object has been
> deprecated in favour of just using the dict-style access that
> nearly all callers use anyway. This avoids mixing up the check for
> removed functionality with live code.
>
> ** It seems that bzrlib.fifo_cache has a similar cleanup callback
> interface, but if it's not being used for lru_cache I see...

[Martin Packman (gz)]

> If something's size does change, then this quickly messes up the size
> tracking. I think it is reasonable to eject an item with the size that
> you added it.

This is true, but if objects cached change size that's already making the cache a dangerous rather than useful thing. I guess it's a question of how much we want to defend against misuse.

> bzr-cvsps-import passes in Branch objects, and uses their
> Branch.unlock() as the cleanup callback. Which does use a per-node
> callback (every branch's unlock is different). We can certainly update
> the tests to reflect this.

My initial thought was to add a new base class without the per-node cleanup, move all the bzrlib users to it, and write a small subclass under the current name that adds callbacks. I could still do this, especially if there is code in launchpad or loggerhead that wants it.

I'm unconvinced by the cvsps use case though, caching locked branches doesn't seem a great idea to start with. It would be simple enough to do this with a per-cache callback though, with something like `getattr(value "unlock")()` but... wait, that's not needed, the plugin as its own lru_cache module and doesn't use the one in bzrlib at all.

[Martin Packman (gz)]

Loggerhead just uses LRUCache as a dict, and none of the deprecated methods. Launchpad I can't branch, so I can't grep.

[Robert Collins (lifeless)]

On Sun, Oct 16, 2011 at 1:10 AM, Martin Packman
<email address hidden> wrote:
> Loggerhead just uses LRUCache as a dict, and none of the deprecated methods. Launchpad I can't branch, so I can't grep.

What happens when you try?

[John A Meinel (jameinel)]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 10/16/2011 7:46 PM, Robert Collins wrote:
> On Sun, Oct 16, 2011 at 1:10 AM, Martin Packman
> <email address hidden> wrote:
>> Loggerhead just uses LRUCache as a dict, and none of the
>> deprecated methods. Launchpad I can't branch, so I can't grep.
>
> What happens when you try?
>

I think he is on Windows, and Launchpad has symlinks in the source tree.

John
=:->

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk6b4IsACgkQJdeBCYSNAAOAkQCfTjnzuXZIgnVEMnxqiSONZ7Nn
Q3gAn0DZmtFCD2ZndhIzxzK4avQTrrlr
=XPrT
-----END PGP SIGNATURE-----

[Martin Packman (gz)]

> > Loggerhead just uses LRUCache as a dict, and none of the deprecated methods.
> Launchpad I can't branch, so I can't grep.
>
> What happens when you try?

Sorry, that was just me being lazy over the weekend. Was easy enough from John's suggestion to branch and inspect the Loggerhead source, but previous experience stopped me trying with Launchpad - I should have just asked someone to grep it for me.

The basic problem in the past has been that it takes a long time and a lot of resources, and the connection hangs after a while, and it's not possible to resume an interrupted branch. I could certainly try again at some point.

[Robert Collins (lifeless)]

On Mon, Oct 17, 2011 at 9:30 PM, Martin Packman
<email address hidden> wrote:
> The basic problem in the past has been that it takes a long time and a lot of resources, and the connection hangs after a while, and it's not possible to resume an interrupted branch. I could certainly try again at some point.

I highly recommend following the Running/LXC wiki page so that you
have a dev environment available: LP is one of the larger single
consumers of bzr, and being able to see what we do with it firsthand
(and poke at it) is invaluable.

-Rob

[Martin Packman (gz)]

Have just grepped the launchpad source, via the kind assistance of allenap, and there are no uses of lru_cache outside loggerhead which I'v already checked.

[Martin Packman (gz)]

sent to pqm by email

[Martin Packman (gz)]

sent to pqm by email

=== modified file 'bzrlib/chk_map.py'
--- bzrlib/chk_map.py	2011-05-20 14:46:02 +0000
+++ bzrlib/chk_map.py	2011-10-27 15:17:22 +0000
@@ -920,7 +920,7 @@
         bytes = ''.join(lines)
         if len(bytes) != self._current_size():
             raise AssertionError('Invalid _current_size')
-        _get_cache().add(self._key, bytes)
+        _get_cache()[self._key] = bytes
         return [self._key]
 
     def refs(self):
@@ -1193,7 +1193,7 @@
                     prefix, node_key_filter = keys[record.key]
                     node_and_filters.append((node, node_key_filter))
                     self._items[prefix] = node
-                    _get_cache().add(record.key, bytes)
+                    _get_cache()[record.key] = bytes
                 for info in node_and_filters:
                     yield info
 
@@ -1319,7 +1319,7 @@
             lines.append(serialised[prefix_len:])
         sha1, _, _ = store.add_lines((None,), (), lines)
         self._key = StaticTuple("sha1:" + sha1,).intern()
-        _get_cache().add(self._key, ''.join(lines))
+        _get_cache()[self._key] = ''.join(lines)
         yield self._key
 
     def _search_key(self, key):

=== modified file 'bzrlib/lru_cache.py'
--- bzrlib/lru_cache.py	2010-07-15 13:05:40 +0000
+++ bzrlib/lru_cache.py	2011-10-27 15:17:22 +0000
@@ -17,6 +17,7 @@
 """A simple least-recently-used (LRU) cache."""
 
 from bzrlib import (
+    symbol_versioning,
     trace,
     )
 
@@ -25,18 +26,13 @@
 class _LRUNode(object):
     """This maintains the linked-list which is the lru internals."""
 
-    __slots__ = ('prev', 'next_key', 'key', 'value', 'cleanup', 'size')
+    __slots__ = ('prev', 'next_key', 'key', 'value')
 
-    def __init__(self, key, value, cleanup=None):
+    def __init__(self, key, value):
         self.prev = None
         self.next_key = _null_key
         self.key = key
         self.value = value
-        self.cleanup = cleanup
-        # TODO: We could compute this 'on-the-fly' like we used to, and remove
-        #       one pointer from this object, we just need to decide if it
-        #       actually costs us much of anything in normal usage
-        self.size = None
 
     def __repr__(self):
         if self.prev is None:
@@ -46,16 +42,6 @@
         return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
                                      self.next_key, prev_key)
 
-    def run_cleanup(self):
-        try:
-            if self.cleanup is not None:
-                self.cleanup(self.key, self.value)
-        finally:
-            # cleanup might raise an exception, but we want to make sure
-            # to break refcycles, etc
-            self.cleanup = None
-            self.value = None
-
 
 class LRUCache(object):
     """A class which manages a cache of entries, removing unused ones."""
@@ -105,62 +91,23 @@
     def __len__(self):
         return len(self._cache)
 
-    def _walk_lru(self):
-        """Walk the LRU list, only meant to be used in tests."""
-        node = self._most_recently_used
-        if node is not None:
-            if node.prev is not None:
-                raise AssertionError('the _most_recently_used entry is not'
-                                     ' supposed to have a previous entry'
-                                     ' %s' % (node,))
-        while node is not None:
-            if node.next_key is _null_key:
-                if node is not self._least_recently_used:
-                    raise AssertionError('only the last node should have'
-                                         ' no next value: %s' % (node,))
-                node_next = None
-            else:
-                node_next = self._cache[node.next_key]
-                if node_next.prev is not node:
-                    raise AssertionError('inconsistency found, node.next.prev'
-                                         ' != node: %s' % (node,))
-            if node.prev is None:
-                if node is not self._most_recently_used:
-                    raise AssertionError('only the _most_recently_used should'
-                                         ' not have a previous node: %s'
-                                         % (node,))
-            else:
-                if node.prev.next_key != node.key:
-                    raise AssertionError('inconsistency found, node.prev.next'
-                                         ' != node: %s' % (node,))
-            yield node
-            node = node_next
-
+    @symbol_versioning.deprecated_method(
+        symbol_versioning.deprecated_in((2, 5, 0)))
     def add(self, key, value, cleanup=None):
-        """Add a new value to the cache.
-
-        Also, if the entry is ever removed from the cache, call
-        cleanup(key, value).
-
-        :param key: The key to store it under
-        :param value: The object to store
-        :param cleanup: None or a function taking (key, value) to indicate
-                        'value' should be cleaned up.
-        """
+        if cleanup is not None:
+            raise ValueError("Per-node cleanup functions no longer supported")
+        return self.__setitem__(key, value)
+
+    def __setitem__(self, key, value):
+        """Add a new value to the cache"""
         if key is _null_key:
             raise ValueError('cannot use _null_key as a key')
         if key in self._cache:
             node = self._cache[key]
-            try:
-                node.run_cleanup()
-            finally:
-                # Maintain the LRU properties, even if cleanup raises an
-                # exception
-                node.value = value
-                node.cleanup = cleanup
-                self._record_access(node)
+            node.value = value
+            self._record_access(node)
         else:
-            node = _LRUNode(key, value, cleanup=cleanup)
+            node = _LRUNode(key, value)
             self._cache[key] = node
             self._record_access(node)
 
@@ -190,10 +137,13 @@
         """
         return self._cache.keys()
 
-    def items(self):
-        """Get the key:value pairs as a dict."""
+    def as_dict(self):
+        """Get a new dict with the same key:value pairs as the cache"""
         return dict((k, n.value) for k, n in self._cache.iteritems())
 
+    items = symbol_versioning.deprecated_method(
+        symbol_versioning.deprecated_in((2, 5, 0)))(as_dict)
+
     def cleanup(self):
         """Clear the cache until it shrinks to the requested size.
 
@@ -204,10 +154,6 @@
         while len(self._cache) > self._after_cleanup_count:
             self._remove_lru()
 
-    def __setitem__(self, key, value):
-        """Add a value to the cache, there will be no cleanup function."""
-        self.add(key, value, cleanup=None)
-
     def _record_access(self, node):
         """Record that key was accessed."""
         # Move 'node' to the front of the queue
@@ -241,19 +187,14 @@
         # If we have removed all entries, remove the head pointer as well
         if self._least_recently_used is None:
             self._most_recently_used = None
-        try:
-            node.run_cleanup()
-        finally:
-            # cleanup might raise an exception, but we want to make sure to
-            # maintain the linked list
-            if node.prev is not None:
-                node.prev.next_key = node.next_key
-            if node.next_key is not _null_key:
-                node_next = self._cache[node.next_key]
-                node_next.prev = node.prev
-            # And remove this node's pointers
-            node.prev = None
-            node.next_key = _null_key
+        if node.prev is not None:
+            node.prev.next_key = node.next_key
+        if node.next_key is not _null_key:
+            node_next = self._cache[node.next_key]
+            node_next.prev = node.prev
+        # And remove this node's pointers
+        node.prev = None
+        node.next_key = _null_key
 
     def _remove_lru(self):
         """Remove one entry from the lru, and handle consequences.
@@ -316,17 +257,8 @@
         self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
         LRUCache.__init__(self, max_cache=max(int(max_size/512), 1))
 
-    def add(self, key, value, cleanup=None):
-        """Add a new value to the cache.
-
-        Also, if the entry is ever removed from the cache, call
-        cleanup(key, value).
-
-        :param key: The key to store it under
-        :param value: The object to store
-        :param cleanup: None or a function taking (key, value) to indicate
-                        'value' should be cleaned up.
-        """
+    def __setitem__(self, key, value):
+        """Add a new value to the cache"""
         if key is _null_key:
             raise ValueError('cannot use _null_key as a key')
         node = self._cache.get(key, None)
@@ -341,15 +273,12 @@
             if node is not None:
                 # We won't be replacing the old node, so just remove it
                 self._remove_node(node)
-            if cleanup is not None:
-                cleanup(key, value)
             return
         if node is None:
-            node = _LRUNode(key, value, cleanup=cleanup)
+            node = _LRUNode(key, value)
             self._cache[key] = node
         else:
-            self._value_size -= node.size
-        node.size = value_len
+            self._value_size -= self._compute_size(node.value)
         self._value_size += value_len
         self._record_access(node)
 
@@ -368,7 +297,7 @@
             self._remove_lru()
 
     def _remove_node(self, node):
-        self._value_size -= node.size
+        self._value_size -= self._compute_size(node.value)
         LRUCache._remove_node(self, node)
 
     def resize(self, max_size, after_cleanup_size=None):

=== modified file 'bzrlib/tests/test_lru_cache.py'
--- bzrlib/tests/test_lru_cache.py	2011-05-13 12:51:05 +0000
+++ bzrlib/tests/test_lru_cache.py	2011-10-27 15:17:22 +0000
@@ -18,10 +18,43 @@
 
 from bzrlib import (
     lru_cache,
+    symbol_versioning,
     tests,
     )
 
 
+def walk_lru(lru):
+    """Test helper to walk the LRU list and assert its consistency"""
+    node = lru._most_recently_used
+    if node is not None:
+        if node.prev is not None:
+            raise AssertionError('the _most_recently_used entry is not'
+                                 ' supposed to have a previous entry'
+                                 ' %s' % (node,))
+    while node is not None:
+        if node.next_key is lru_cache._null_key:
+            if node is not lru._least_recently_used:
+                raise AssertionError('only the last node should have'
+                                     ' no next value: %s' % (node,))
+            node_next = None
+        else:
+            node_next = lru._cache[node.next_key]
+            if node_next.prev is not node:
+                raise AssertionError('inconsistency found, node.next.prev'
+                                     ' != node: %s' % (node,))
+        if node.prev is None:
+            if node is not lru._most_recently_used:
+                raise AssertionError('only the _most_recently_used should'
+                                     ' not have a previous node: %s'
+                                     % (node,))
+        else:
+            if node.prev.next_key != node.key:
+                raise AssertionError('inconsistency found, node.prev.next'
+                                     ' != node: %s' % (node,))
+        yield node
+        node = node_next
+
+ 
 class TestLRUCache(tests.TestCase):
     """Test that LRU cache properly keeps track of entries."""
 
@@ -61,11 +94,12 @@
         cache[None]
         cache[1]
         cache[None]
-        self.assertEqual([None, 1], [n.key for n in cache._walk_lru()])
+        self.assertEqual([None, 1], [n.key for n in walk_lru(cache)])
 
     def test_add__null_key(self):
         cache = lru_cache.LRUCache(max_cache=10)
-        self.assertRaises(ValueError, cache.add, lru_cache._null_key, 1)
+        self.assertRaises(ValueError,
+            cache.__setitem__, lru_cache._null_key, 1)
 
     def test_overflow(self):
         """Adding extra entries will pop out old ones."""
@@ -94,80 +128,12 @@
 
         self.assertFalse('foo' in cache)
 
-    def test_cleanup(self):
-        """Test that we can use a cleanup function."""
-        cleanup_called = []
-        def cleanup_func(key, val):
-            cleanup_called.append((key, val))
-
-        cache = lru_cache.LRUCache(max_cache=2)
-
-        cache.add('baz', '1', cleanup=cleanup_func)
-        cache.add('foo', '2', cleanup=cleanup_func)
-        cache.add('biz', '3', cleanup=cleanup_func)
-
-        self.assertEqual([('baz', '1')], cleanup_called)
-
-        # 'foo' is now most recent, so final cleanup will call it last
-        cache['foo']
-        cache.clear()
-        self.assertEqual([('baz', '1'), ('biz', '3'), ('foo', '2')],
-                         cleanup_called)
-
-    def test_cleanup_on_replace(self):
-        """Replacing an object should cleanup the old value."""
-        cleanup_called = []
-        def cleanup_func(key, val):
-            cleanup_called.append((key, val))
-
-        cache = lru_cache.LRUCache(max_cache=2)
-        cache.add(1, 10, cleanup=cleanup_func)
-        cache.add(2, 20, cleanup=cleanup_func)
-        cache.add(2, 25, cleanup=cleanup_func)
-
-        self.assertEqual([(2, 20)], cleanup_called)
-        self.assertEqual(25, cache[2])
-
-        # Even __setitem__ should make sure cleanup() is called
-        cache[2] = 26
-        self.assertEqual([(2, 20), (2, 25)], cleanup_called)
-
-    def test_cleanup_error_maintains_linked_list(self):
-        cleanup_called = []
-        def cleanup_func(key, val):
-            cleanup_called.append((key, val))
-            raise ValueError('failure during cleanup')
-
-        cache = lru_cache.LRUCache(max_cache=10)
-        for i in xrange(10):
-            cache.add(i, i, cleanup=cleanup_func)
-        for i in xrange(10, 20):
-            self.assertRaises(ValueError,
-                cache.add, i, i, cleanup=cleanup_func)
-
-        self.assertEqual([(i, i) for i in xrange(10)], cleanup_called)
-
-        self.assertEqual(range(19, 9, -1), [n.key for n in cache._walk_lru()])
-
-    def test_cleanup_during_replace_still_replaces(self):
-        cleanup_called = []
-        def cleanup_func(key, val):
-            cleanup_called.append((key, val))
-            raise ValueError('failure during cleanup')
-
-        cache = lru_cache.LRUCache(max_cache=10)
-        for i in xrange(10):
-            cache.add(i, i, cleanup=cleanup_func)
-        self.assertRaises(ValueError,
-            cache.add, 1, 20, cleanup=cleanup_func)
-        # We also still update the recent access to this node
-        self.assertEqual([1, 9, 8, 7, 6, 5, 4, 3, 2, 0],
-                         [n.key for n in cache._walk_lru()])
-        self.assertEqual(20, cache[1])
-
-        self.assertEqual([(1, 1)], cleanup_called)
-        self.assertEqual([1, 9, 8, 7, 6, 5, 4, 3, 2, 0],
-                         [n.key for n in cache._walk_lru()])
+    def test_cleanup_function_deprecated(self):
+        """Test that per-node cleanup functions are no longer allowed"""
+        cache = lru_cache.LRUCache()
+        self.assertRaises(ValueError, self.applyDeprecated,
+            symbol_versioning.deprecated_in((2, 5, 0)),
+            cache.add, "key", 1, cleanup=lambda: None)
 
     def test_len(self):
         cache = lru_cache.LRUCache(max_cache=10, after_cleanup_count=10)
@@ -197,21 +163,21 @@
         # We hit the max
         self.assertEqual(10, len(cache))
         self.assertEqual([11, 10, 9, 1, 8, 7, 6, 5, 4, 3],
-                         [n.key for n in cache._walk_lru()])
+                         [n.key for n in walk_lru(cache)])
 
     def test_cleanup_shrinks_to_after_clean_count(self):
         cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=3)
 
-        cache.add(1, 10)
-        cache.add(2, 20)
-        cache.add(3, 25)
-        cache.add(4, 30)
-        cache.add(5, 35)
+        cache[1] = 10
+        cache[2] = 20
+        cache[3] = 25
+        cache[4] = 30
+        cache[5] = 35
 
         self.assertEqual(5, len(cache))
         # This will bump us over the max, which causes us to shrink down to
         # after_cleanup_cache size
-        cache.add(6, 40)
+        cache[6] = 40
         self.assertEqual(3, len(cache))
 
     def test_after_cleanup_larger_than_max(self):
@@ -227,11 +193,11 @@
         cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=2)
 
         # Add these in order
-        cache.add(1, 10)
-        cache.add(2, 20)
-        cache.add(3, 25)
-        cache.add(4, 30)
-        cache.add(5, 35)
+        cache[1] = 10
+        cache[2] = 20
+        cache[3] = 25
+        cache[4] = 30
+        cache[5] = 35
 
         self.assertEqual(5, len(cache))
         # Force a compaction
@@ -242,33 +208,33 @@
         cache = lru_cache.LRUCache(max_cache=5)
 
         # Add these in order
-        cache.add(1, 10)
-        cache.add(2, 20)
-        cache.add(3, 25)
-        cache.add(4, 30)
-        cache.add(5, 35)
+        cache[1] = 10
+        cache[2] = 20
+        cache[3] = 25
+        cache[4] = 30
+        cache[5] = 35
 
-        self.assertEqual([5, 4, 3, 2, 1], [n.key for n in cache._walk_lru()])
+        self.assertEqual([5, 4, 3, 2, 1], [n.key for n in walk_lru(cache)])
 
         # Now access some randomly
         cache[2]
         cache[5]
         cache[3]
         cache[2]
-        self.assertEqual([2, 3, 5, 4, 1], [n.key for n in cache._walk_lru()])
+        self.assertEqual([2, 3, 5, 4, 1], [n.key for n in walk_lru(cache)])
 
     def test_get(self):
         cache = lru_cache.LRUCache(max_cache=5)
 
-        cache.add(1, 10)
-        cache.add(2, 20)
+        cache[1] = 10
+        cache[2] = 20
         self.assertEqual(20, cache.get(2))
         self.assertIs(None, cache.get(3))
         obj = object()
         self.assertIs(obj, cache.get(3, obj))
-        self.assertEqual([2, 1], [n.key for n in cache._walk_lru()])
+        self.assertEqual([2, 1], [n.key for n in walk_lru(cache)])
         self.assertEqual(10, cache.get(1))
-        self.assertEqual([1, 2], [n.key for n in cache._walk_lru()])
+        self.assertEqual([1, 2], [n.key for n in walk_lru(cache)])
 
     def test_keys(self):
         cache = lru_cache.LRUCache(max_cache=5, after_cleanup_count=5)
@@ -332,18 +298,19 @@
 
     def test_add__null_key(self):
         cache = lru_cache.LRUSizeCache()
-        self.assertRaises(ValueError, cache.add, lru_cache._null_key, 1)
+        self.assertRaises(ValueError,
+            cache.__setitem__, lru_cache._null_key, 1)
 
     def test_add_tracks_size(self):
         cache = lru_cache.LRUSizeCache()
         self.assertEqual(0, cache._value_size)
-        cache.add('my key', 'my value text')
+        cache['my key'] = 'my value text'
         self.assertEqual(13, cache._value_size)
 
     def test_remove_tracks_size(self):
         cache = lru_cache.LRUSizeCache()
         self.assertEqual(0, cache._value_size)
-        cache.add('my key', 'my value text')
+        cache['my key'] = 'my value text'
         self.assertEqual(13, cache._value_size)
         node = cache._cache['my key']
         cache._remove_node(node)
@@ -353,64 +320,48 @@
         """Adding a large value may not be cached at all."""
         cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=5)
         self.assertEqual(0, cache._value_size)
-        self.assertEqual({}, cache.items())
-        cache.add('test', 'key')
-        self.assertEqual(3, cache._value_size)
-        self.assertEqual({'test': 'key'}, cache.items())
-        cache.add('test2', 'key that is too big')
-        self.assertEqual(3, cache._value_size)
-        self.assertEqual({'test':'key'}, cache.items())
+        self.assertEqual({}, cache.as_dict())
+        cache['test'] = 'key'
+        self.assertEqual(3, cache._value_size)
+        self.assertEqual({'test': 'key'}, cache.as_dict())
+        cache['test2'] = 'key that is too big'
+        self.assertEqual(3, cache._value_size)
+        self.assertEqual({'test':'key'}, cache.as_dict())
         # If we would add a key, only to cleanup and remove all cached entries,
         # then obviously that value should not be stored
-        cache.add('test3', 'bigkey')
-        self.assertEqual(3, cache._value_size)
-        self.assertEqual({'test':'key'}, cache.items())
-
-        cache.add('test4', 'bikey')
-        self.assertEqual(3, cache._value_size)
-        self.assertEqual({'test':'key'}, cache.items())
-
-    def test_no_add_over_size_cleanup(self):
-        """If a large value is not cached, we will call cleanup right away."""
-        cleanup_calls = []
-        def cleanup(key, value):
-            cleanup_calls.append((key, value))
-
-        cache = lru_cache.LRUSizeCache(max_size=10, after_cleanup_size=5)
-        self.assertEqual(0, cache._value_size)
-        self.assertEqual({}, cache.items())
-        cache.add('test', 'key that is too big', cleanup=cleanup)
-        # key was not added
-        self.assertEqual(0, cache._value_size)
-        self.assertEqual({}, cache.items())
-        # and cleanup was called
-        self.assertEqual([('test', 'key that is too big')], cleanup_calls)
+        cache['test3'] = 'bigkey'
+        self.assertEqual(3, cache._value_size)
+        self.assertEqual({'test':'key'}, cache.as_dict())
+
+        cache['test4'] = 'bikey'
+        self.assertEqual(3, cache._value_size)
+        self.assertEqual({'test':'key'}, cache.as_dict())
 
     def test_adding_clears_cache_based_on_size(self):
         """The cache is cleared in LRU order until small enough"""
         cache = lru_cache.LRUSizeCache(max_size=20)
-        cache.add('key1', 'value') # 5 chars
-        cache.add('key2', 'value2') # 6 chars
-        cache.add('key3', 'value23') # 7 chars
+        cache['key1'] = 'value' # 5 chars
+        cache['key2'] = 'value2' # 6 chars
+        cache['key3'] = 'value23' # 7 chars
         self.assertEqual(5+6+7, cache._value_size)
         cache['key2'] # reference key2 so it gets a newer reference time
-        cache.add('key4', 'value234') # 8 chars, over limit
+        cache['key4'] = 'value234' # 8 chars, over limit
         # We have to remove 2 keys to get back under limit
         self.assertEqual(6+8, cache._value_size)
         self.assertEqual({'key2':'value2', 'key4':'value234'},
-                         cache.items())
+                         cache.as_dict())
 
     def test_adding_clears_to_after_cleanup_size(self):
         cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
-        cache.add('key1', 'value') # 5 chars
-        cache.add('key2', 'value2') # 6 chars
-        cache.add('key3', 'value23') # 7 chars
+        cache['key1'] = 'value' # 5 chars
+        cache['key2'] = 'value2' # 6 chars
+        cache['key3'] = 'value23' # 7 chars
         self.assertEqual(5+6+7, cache._value_size)
         cache['key2'] # reference key2 so it gets a newer reference time
-        cache.add('key4', 'value234') # 8 chars, over limit
+        cache['key4'] = 'value234' # 8 chars, over limit
         # We have to remove 3 keys to get back under limit
         self.assertEqual(8, cache._value_size)
-        self.assertEqual({'key4':'value234'}, cache.items())
+        self.assertEqual({'key4':'value234'}, cache.as_dict())
 
     def test_custom_sizes(self):
         def size_of_list(lst):
@@ -418,23 +369,23 @@
         cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10,
                                        compute_size=size_of_list)
 
-        cache.add('key1', ['val', 'ue']) # 5 chars
-        cache.add('key2', ['val', 'ue2']) # 6 chars
-        cache.add('key3', ['val', 'ue23']) # 7 chars
+        cache['key1'] = ['val', 'ue'] # 5 chars
+        cache['key2'] = ['val', 'ue2'] # 6 chars
+        cache['key3'] = ['val', 'ue23'] # 7 chars
         self.assertEqual(5+6+7, cache._value_size)
         cache['key2'] # reference key2 so it gets a newer reference time
-        cache.add('key4', ['value', '234']) # 8 chars, over limit
+        cache['key4'] = ['value', '234'] # 8 chars, over limit
         # We have to remove 3 keys to get back under limit
         self.assertEqual(8, cache._value_size)
-        self.assertEqual({'key4':['value', '234']}, cache.items())
+        self.assertEqual({'key4':['value', '234']}, cache.as_dict())
 
     def test_cleanup(self):
         cache = lru_cache.LRUSizeCache(max_size=20, after_cleanup_size=10)
 
         # Add these in order
-        cache.add('key1', 'value') # 5 chars
-        cache.add('key2', 'value2') # 6 chars
-        cache.add('key3', 'value23') # 7 chars
+        cache['key1'] = 'value' # 5 chars
+        cache['key2'] = 'value2' # 6 chars
+        cache['key3'] = 'value23' # 7 chars
         self.assertEqual(5+6+7, cache._value_size)
 
         cache.cleanup()

=== modified file 'doc/en/release-notes/bzr-2.5.txt'
--- doc/en/release-notes/bzr-2.5.txt	2011-10-25 12:50:34 +0000
+++ doc/en/release-notes/bzr-2.5.txt	2011-10-27 15:17:22 +0000
@@ -81,6 +81,9 @@
 
 * ``Branch.revision_history`` is now deprecated. (Jelmer Vernooij, #799519)
 
+* Methods ``add`` and ``items`` of ``LRUCache`` and ``LRUSizeCache`` are
+  deprecated. Use normal dict-style access instead. (Martin Packman)
+
 * New flag ``RepositoryFormat.supports_unreferenced_revisions`` which
   indicates whether revisions can be present in a repository without
   being referenced from e.g. a branch history at the same time.