[Bug] Try to del key that handled by __missing__ and result in KeyError

[NatureGeorge]

Python 3.7.1
cachetools 4.2.0

Reproduce

from cachetools import LRUCache

class M(LRUCache):
    def __missing__(self, key):
         if key == (0,0):
             return 0
         else:
             return 1

a = M(maxsize=2)
print(a[0,0])
for i in range(10):
    a[(i,i+1)] = i**2

Traceback Info:

KeyError                                  Traceback (most recent call last)
<ipython-input-4-b46350f4c2e0> in <module>
      1 for i in range(10):
----> 2     a[(i,i+1)] = i**2
      3

c:\users\nature\miniconda3\lib\site-packages\cachetools\lru.py in __setitem__(self, key, value, cache_setitem)
     17
     18     def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
---> 19         cache_setitem(self, key, value)
     20         self.__update(key)
     21

c:\users\nature\miniconda3\lib\site-packages\cachetools\cache.py in __setitem__(self, key, value)
     53         if key not in self.__data or self.__size[key] < size:
     54             while self.__currsize + size > maxsize:
---> 55                 self.popitem()
     56         if key in self.__data:
     57             diffsize = size - self.__size[key]

c:\users\nature\miniconda3\lib\site-packages\cachetools\lru.py in popitem(self)
     31             raise KeyError('%s is empty' % type(self).__name__) from None
     32         else:
---> 33             return (key, self.pop(key))
     34
     35     def __update(self, key):

c:\users\nature\miniconda3\lib\site-packages\cachetools\cache.py in pop(self, key, default)
     90             del self[key]
     91         elif default is self.__marker:
---> 92             raise KeyError(key)
     93         else:
     94             value = default

Expected Behavior:

Usual use case of LRUCache but handling some special keys in __missing__ at the same time.

[tkem]

@NatureGeorge Thanks for reporting! Already noticed this myself, though IMHO the usual way is to add the key/value pair to the cache in __missing__, as illustrated in the example, e.g.

class M(LRUCache):
    def __missing__(self, key):
         if key == (0,0):
             self[key] = 0
         else:
             self[key] = 1
         return self[key]

However, I'm aware that there are use cases that imply not adding the "missing" value to the cache, such as #186.
I'll think about it.

[akudan]

I just ran across a very similar issue, which can be reproduced by running the example PepStore code from the docs (just try some large pep key that will not get found and then a few additional good ones). When a key is not added to the cache in an overridden __missing__, it is still added to __order, which will result in a KeyError once the cache limit is reached and it tries to pop that key from the cache. Either the PepStore example should be updated or perhaps __update(key) should not be called if value = cache_getitem(self, key) returns None.

[tkem]

@akudan: Good catch, the try/except block should definitely be removed from the example, since it doesn't add much value, IMHO. As for general __missing__ behavior, I guess this needs to be fixed for every cache class that overrides __getitem__ separately. Should be able to work on this soon.