Backed out changeset: b0a0b9b59012
diff --git a/Lib/functools.py b/Lib/functools.py
index 19c25e1..09df068 100644
--- a/Lib/functools.py
+++ b/Lib/functools.py
@@ -419,120 +419,129 @@
if maxsize is not None and not isinstance(maxsize, int):
raise TypeError('Expected maxsize to be an integer or None')
+ def decorating_function(user_function):
+ wrapper = _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo)
+ return update_wrapper(wrapper, user_function)
+
+ return decorating_function
+
+def _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo):
# Constants shared by all lru cache instances:
sentinel = object() # unique object used to signal cache misses
make_key = _make_key # build a key from the function arguments
PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # names for the link fields
- def decorating_function(user_function):
- cache = {}
- hits = misses = 0
- full = False
- cache_get = cache.get # bound method to lookup a key or return None
- lock = RLock() # because linkedlist updates aren't threadsafe
- root = [] # root of the circular doubly linked list
- root[:] = [root, root, None, None] # initialize by pointing to self
+ cache = {}
+ hits = misses = 0
+ full = False
+ cache_get = cache.get # bound method to lookup a key or return None
+ lock = RLock() # because linkedlist updates aren't threadsafe
+ root = [] # root of the circular doubly linked list
+ root[:] = [root, root, None, None] # initialize by pointing to self
- if maxsize == 0:
+ if maxsize == 0:
- def wrapper(*args, **kwds):
- # No caching -- just a statistics update after a successful call
- nonlocal misses
- result = user_function(*args, **kwds)
- misses += 1
+ def wrapper(*args, **kwds):
+ # No caching -- just a statistics update after a successful call
+ nonlocal misses
+ result = user_function(*args, **kwds)
+ misses += 1
+ return result
+
+ elif maxsize is None:
+
+ def wrapper(*args, **kwds):
+ # Simple caching without ordering or size limit
+ nonlocal hits, misses
+ key = make_key(args, kwds, typed)
+ result = cache_get(key, sentinel)
+ if result is not sentinel:
+ hits += 1
return result
+ result = user_function(*args, **kwds)
+ cache[key] = result
+ misses += 1
+ return result
- elif maxsize is None:
+ else:
- def wrapper(*args, **kwds):
- # Simple caching without ordering or size limit
- nonlocal hits, misses
- key = make_key(args, kwds, typed)
- result = cache_get(key, sentinel)
- if result is not sentinel:
+ def wrapper(*args, **kwds):
+ # Size limited caching that tracks accesses by recency
+ nonlocal root, hits, misses, full
+ key = make_key(args, kwds, typed)
+ with lock:
+ link = cache_get(key)
+ if link is not None:
+ # Move the link to the front of the circular queue
+ link_prev, link_next, _key, result = link
+ link_prev[NEXT] = link_next
+ link_next[PREV] = link_prev
+ last = root[PREV]
+ last[NEXT] = root[PREV] = link
+ link[PREV] = last
+ link[NEXT] = root
hits += 1
return result
- result = user_function(*args, **kwds)
- cache[key] = result
+ result = user_function(*args, **kwds)
+ with lock:
+ if key in cache:
+ # Getting here means that this same key was added to the
+ # cache while the lock was released. Since the link
+ # update is already done, we need only return the
+ # computed result and update the count of misses.
+ pass
+ elif full:
+ # Use the old root to store the new key and result.
+ oldroot = root
+ oldroot[KEY] = key
+ oldroot[RESULT] = result
+ # Empty the oldest link and make it the new root.
+ # Keep a reference to the old key and old result to
+ # prevent their ref counts from going to zero during the
+ # update. That will prevent potentially arbitrary object
+ # clean-up code (i.e. __del__) from running while we're
+ # still adjusting the links.
+ root = oldroot[NEXT]
+ oldkey = root[KEY]
+ oldresult = root[RESULT]
+ root[KEY] = root[RESULT] = None
+ # Now update the cache dictionary.
+ del cache[oldkey]
+ # Save the potentially reentrant cache[key] assignment
+ # for last, after the root and links have been put in
+ # a consistent state.
+ cache[key] = oldroot
+ else:
+ # Put result in a new link at the front of the queue.
+ last = root[PREV]
+ link = [last, root, key, result]
+ last[NEXT] = root[PREV] = cache[key] = link
+ full = (len(cache) >= maxsize)
misses += 1
- return result
+ return result
- else:
+ def cache_info():
+ """Report cache statistics"""
+ with lock:
+ return _CacheInfo(hits, misses, maxsize, len(cache))
- def wrapper(*args, **kwds):
- # Size limited caching that tracks accesses by recency
- nonlocal root, hits, misses, full
- key = make_key(args, kwds, typed)
- with lock:
- link = cache_get(key)
- if link is not None:
- # Move the link to the front of the circular queue
- link_prev, link_next, _key, result = link
- link_prev[NEXT] = link_next
- link_next[PREV] = link_prev
- last = root[PREV]
- last[NEXT] = root[PREV] = link
- link[PREV] = last
- link[NEXT] = root
- hits += 1
- return result
- result = user_function(*args, **kwds)
- with lock:
- if key in cache:
- # Getting here means that this same key was added to the
- # cache while the lock was released. Since the link
- # update is already done, we need only return the
- # computed result and update the count of misses.
- pass
- elif full:
- # Use the old root to store the new key and result.
- oldroot = root
- oldroot[KEY] = key
- oldroot[RESULT] = result
- # Empty the oldest link and make it the new root.
- # Keep a reference to the old key and old result to
- # prevent their ref counts from going to zero during the
- # update. That will prevent potentially arbitrary object
- # clean-up code (i.e. __del__) from running while we're
- # still adjusting the links.
- root = oldroot[NEXT]
- oldkey = root[KEY]
- oldresult = root[RESULT]
- root[KEY] = root[RESULT] = None
- # Now update the cache dictionary.
- del cache[oldkey]
- # Save the potentially reentrant cache[key] assignment
- # for last, after the root and links have been put in
- # a consistent state.
- cache[key] = oldroot
- else:
- # Put result in a new link at the front of the queue.
- last = root[PREV]
- link = [last, root, key, result]
- last[NEXT] = root[PREV] = cache[key] = link
- full = (len(cache) >= maxsize)
- misses += 1
- return result
+ def cache_clear():
+ """Clear the cache and cache statistics"""
+ nonlocal hits, misses, full
+ with lock:
+ cache.clear()
+ root[:] = [root, root, None, None]
+ hits = misses = 0
+ full = False
- def cache_info():
- """Report cache statistics"""
- with lock:
- return _CacheInfo(hits, misses, maxsize, len(cache))
+ wrapper.cache_info = cache_info
+ wrapper.cache_clear = cache_clear
+ return update_wrapper(wrapper, user_function)
- def cache_clear():
- """Clear the cache and cache statistics"""
- nonlocal hits, misses, full
- with lock:
- cache.clear()
- root[:] = [root, root, None, None]
- hits = misses = 0
- full = False
-
- wrapper.cache_info = cache_info
- wrapper.cache_clear = cache_clear
- return update_wrapper(wrapper, user_function)
-
- return decorating_function
+try:
+ from _functools import _lru_cache_wrapper
+except ImportError:
+ pass
################################################################################
diff --git a/Lib/test/test_functools.py b/Lib/test/test_functools.py
index 03dd545..271d655 100644
--- a/Lib/test/test_functools.py
+++ b/Lib/test/test_functools.py
@@ -7,6 +7,10 @@
from test import support
import unittest
from weakref import proxy
+try:
+ import threading
+except ImportError:
+ threading = None
import functools
@@ -912,12 +916,12 @@
return self.value == other.value
-class TestLRU(unittest.TestCase):
+class TestLRU:
def test_lru(self):
def orig(x, y):
return 3 * x + y
- f = functools.lru_cache(maxsize=20)(orig)
+ f = self.module.lru_cache(maxsize=20)(orig)
hits, misses, maxsize, currsize = f.cache_info()
self.assertEqual(maxsize, 20)
self.assertEqual(currsize, 0)
@@ -955,7 +959,7 @@
self.assertEqual(currsize, 1)
# test size zero (which means "never-cache")
- @functools.lru_cache(0)
+ @self.module.lru_cache(0)
def f():
nonlocal f_cnt
f_cnt += 1
@@ -971,7 +975,7 @@
self.assertEqual(currsize, 0)
# test size one
- @functools.lru_cache(1)
+ @self.module.lru_cache(1)
def f():
nonlocal f_cnt
f_cnt += 1
@@ -987,7 +991,7 @@
self.assertEqual(currsize, 1)
# test size two
- @functools.lru_cache(2)
+ @self.module.lru_cache(2)
def f(x):
nonlocal f_cnt
f_cnt += 1
@@ -1004,7 +1008,7 @@
self.assertEqual(currsize, 2)
def test_lru_with_maxsize_none(self):
- @functools.lru_cache(maxsize=None)
+ @self.module.lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
@@ -1012,17 +1016,26 @@
self.assertEqual([fib(n) for n in range(16)],
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610])
self.assertEqual(fib.cache_info(),
- functools._CacheInfo(hits=28, misses=16, maxsize=None, currsize=16))
+ self.module._CacheInfo(hits=28, misses=16, maxsize=None, currsize=16))
fib.cache_clear()
self.assertEqual(fib.cache_info(),
- functools._CacheInfo(hits=0, misses=0, maxsize=None, currsize=0))
+ self.module._CacheInfo(hits=0, misses=0, maxsize=None, currsize=0))
+
+ def test_lru_with_maxsize_negative(self):
+ @self.module.lru_cache(maxsize=-10)
+ def eq(n):
+ return n
+ for i in (0, 1):
+ self.assertEqual([eq(n) for n in range(150)], list(range(150)))
+ self.assertEqual(eq.cache_info(),
+ self.module._CacheInfo(hits=0, misses=300, maxsize=-10, currsize=1))
def test_lru_with_exceptions(self):
# Verify that user_function exceptions get passed through without
# creating a hard-to-read chained exception.
# http://bugs.python.org/issue13177
for maxsize in (None, 128):
- @functools.lru_cache(maxsize)
+ @self.module.lru_cache(maxsize)
def func(i):
return 'abc'[i]
self.assertEqual(func(0), 'a')
@@ -1035,7 +1048,7 @@
def test_lru_with_types(self):
for maxsize in (None, 128):
- @functools.lru_cache(maxsize=maxsize, typed=True)
+ @self.module.lru_cache(maxsize=maxsize, typed=True)
def square(x):
return x * x
self.assertEqual(square(3), 9)
@@ -1050,7 +1063,7 @@
self.assertEqual(square.cache_info().misses, 4)
def test_lru_with_keyword_args(self):
- @functools.lru_cache()
+ @self.module.lru_cache()
def fib(n):
if n < 2:
return n
@@ -1060,13 +1073,13 @@
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
)
self.assertEqual(fib.cache_info(),
- functools._CacheInfo(hits=28, misses=16, maxsize=128, currsize=16))
+ self.module._CacheInfo(hits=28, misses=16, maxsize=128, currsize=16))
fib.cache_clear()
self.assertEqual(fib.cache_info(),
- functools._CacheInfo(hits=0, misses=0, maxsize=128, currsize=0))
+ self.module._CacheInfo(hits=0, misses=0, maxsize=128, currsize=0))
def test_lru_with_keyword_args_maxsize_none(self):
- @functools.lru_cache(maxsize=None)
+ @self.module.lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
@@ -1074,15 +1087,71 @@
self.assertEqual([fib(n=number) for number in range(16)],
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610])
self.assertEqual(fib.cache_info(),
- functools._CacheInfo(hits=28, misses=16, maxsize=None, currsize=16))
+ self.module._CacheInfo(hits=28, misses=16, maxsize=None, currsize=16))
fib.cache_clear()
self.assertEqual(fib.cache_info(),
- functools._CacheInfo(hits=0, misses=0, maxsize=None, currsize=0))
+ self.module._CacheInfo(hits=0, misses=0, maxsize=None, currsize=0))
+
+ def test_lru_cache_decoration(self):
+ def f(zomg: 'zomg_annotation'):
+ """f doc string"""
+ return 42
+ g = self.module.lru_cache()(f)
+ for attr in self.module.WRAPPER_ASSIGNMENTS:
+ self.assertEqual(getattr(g, attr), getattr(f, attr))
+
+ @unittest.skipUnless(threading, 'This test requires threading.')
+ def test_lru_cache_threaded(self):
+ def orig(x, y):
+ return 3 * x + y
+ f = self.module.lru_cache(maxsize=20)(orig)
+ hits, misses, maxsize, currsize = f.cache_info()
+ self.assertEqual(currsize, 0)
+
+ def full(f, *args):
+ for _ in range(10):
+ f(*args)
+
+ def clear(f):
+ for _ in range(10):
+ f.cache_clear()
+
+ orig_si = sys.getswitchinterval()
+ sys.setswitchinterval(1e-6)
+ try:
+ # create 5 threads in order to fill cache
+ threads = []
+ for k in range(5):
+ t = threading.Thread(target=full, args=[f, k, k])
+ t.start()
+ threads.append(t)
+
+ for t in threads:
+ t.join()
+
+ hits, misses, maxsize, currsize = f.cache_info()
+ self.assertEqual(hits, 45)
+ self.assertEqual(misses, 5)
+ self.assertEqual(currsize, 5)
+
+ # create 5 threads in order to fill cache and 1 to clear it
+ cleaner = threading.Thread(target=clear, args=[f])
+ cleaner.start()
+ threads = [cleaner]
+ for k in range(5):
+ t = threading.Thread(target=full, args=[f, k, k])
+ t.start()
+ threads.append(t)
+
+ for t in threads:
+ t.join()
+ finally:
+ sys.setswitchinterval(orig_si)
def test_need_for_rlock(self):
# This will deadlock on an LRU cache that uses a regular lock
- @functools.lru_cache(maxsize=10)
+ @self.module.lru_cache(maxsize=10)
def test_func(x):
'Used to demonstrate a reentrant lru_cache call within a single thread'
return x
@@ -1110,6 +1179,12 @@
def f():
pass
+class TestLRUC(TestLRU, unittest.TestCase):
+ module = c_functools
+
+class TestLRUPy(TestLRU, unittest.TestCase):
+ module = py_functools
+
class TestSingleDispatch(unittest.TestCase):
def test_simple_overloads(self):