diff options
Diffstat (limited to 'Lib/functools.py')
| -rw-r--r-- | Lib/functools.py | 122 |
1 files changed, 115 insertions, 7 deletions
diff --git a/Lib/functools.py b/Lib/functools.py index 53680b8..85ea257 100644 --- a/Lib/functools.py +++ b/Lib/functools.py @@ -4,15 +4,24 @@ # to allow utilities written in Python to be added # to the functools module. # Written by Nick Coghlan <ncoghlan at gmail.com> -# Copyright (C) 2006 Python Software Foundation. +# and Raymond Hettinger <python at rcn.com> +# Copyright (C) 2006-2010 Python Software Foundation. # See C source code for _functools credits/copyright +__all__ = ['update_wrapper', 'wraps', 'WRAPPER_ASSIGNMENTS', 'WRAPPER_UPDATES', + 'total_ordering', 'cmp_to_key', 'lru_cache', 'reduce', 'partial'] + from _functools import partial, reduce +from collections import OrderedDict, namedtuple +try: + from _thread import allocate_lock as Lock +except: + from _dummy_thread import allocate_lock as Lock # update_wrapper() and wraps() are tools to help write # wrapper functions that can handle naive introspection -WRAPPER_ASSIGNMENTS = ('__module__', '__name__', '__doc__') +WRAPPER_ASSIGNMENTS = ('__module__', '__name__', '__doc__', '__annotations__') WRAPPER_UPDATES = ('__dict__',) def update_wrapper(wrapper, wrapped, @@ -29,8 +38,14 @@ def update_wrapper(wrapper, are updated with the corresponding attribute from the wrapped function (defaults to functools.WRAPPER_UPDATES) """ + wrapper.__wrapped__ = wrapped for attr in assigned: - setattr(wrapper, attr, getattr(wrapped, attr)) + try: + value = getattr(wrapped, attr) + except AttributeError: + pass + else: + setattr(wrapper, attr, value) for attr in updated: getattr(wrapper, attr).update(getattr(wrapped, attr, {})) # Return the wrapper so this can be used as a decorator via partial() @@ -66,7 +81,8 @@ def total_ordering(cls): ('__gt__', lambda self, other: self >= other and not self == other), ('__lt__', lambda self, other: not self >= other)] } - roots = set(dir(cls)) & set(convert) + # Find user-defined comparisons (not those inherited from object). + roots = [op for op in convert if getattr(cls, op, None) is not getattr(object, op, None)] if not roots: raise ValueError('must define at least one ordering operation: < > <= >=') root = max(roots) # prefer __lt__ to __le__ to __gt__ to __ge__ @@ -81,7 +97,7 @@ def cmp_to_key(mycmp): """Convert a cmp= function into a key= function""" class K(object): __slots__ = ['obj'] - def __init__(self, obj, *args): + def __init__(self, obj): self.obj = obj def __lt__(self, other): return mycmp(self.obj, other.obj) < 0 @@ -95,6 +111,98 @@ def cmp_to_key(mycmp): return mycmp(self.obj, other.obj) >= 0 def __ne__(self, other): return mycmp(self.obj, other.obj) != 0 - def __hash__(self): - raise TypeError('hash not implemented') + __hash__ = None return K + +_CacheInfo = namedtuple("CacheInfo", "hits misses maxsize currsize") + +def lru_cache(maxsize=100): + """Least-recently-used cache decorator. + + If *maxsize* is set to None, the LRU features are disabled and the cache + can grow without bound. + + Arguments to the cached function must be hashable. + + View the cache statistics named tuple (hits, misses, maxsize, currsize) with + f.cache_info(). Clear the cache and statistics with f.cache_clear(). + Access the underlying function with f.__wrapped__. + + See: http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used + + """ + # Users should only access the lru_cache through its public API: + # cache_info, cache_clear, and f.__wrapped__ + # The internals of the lru_cache are encapsulated for thread safety and + # to allow the implementation to change (including a possible C version). + + def decorating_function(user_function, + tuple=tuple, sorted=sorted, len=len, KeyError=KeyError): + + hits = misses = 0 + kwd_mark = (object(),) # separates positional and keyword args + lock = Lock() # needed because OrderedDict isn't threadsafe + + if maxsize is None: + cache = dict() # simple cache without ordering or size limit + + @wraps(user_function) + def wrapper(*args, **kwds): + nonlocal hits, misses + key = args + if kwds: + key += kwd_mark + tuple(sorted(kwds.items())) + try: + result = cache[key] + hits += 1 + return result + except KeyError: + pass + result = user_function(*args, **kwds) + cache[key] = result + misses += 1 + return result + else: + cache = OrderedDict() # ordered least recent to most recent + cache_popitem = cache.popitem + cache_renew = cache.move_to_end + + @wraps(user_function) + def wrapper(*args, **kwds): + nonlocal hits, misses + key = args + if kwds: + key += kwd_mark + tuple(sorted(kwds.items())) + with lock: + try: + result = cache[key] + cache_renew(key) # record recent use of this key + hits += 1 + return result + except KeyError: + pass + result = user_function(*args, **kwds) + with lock: + cache[key] = result # record recent use of this key + misses += 1 + if len(cache) > maxsize: + cache_popitem(0) # purge least recently used cache entry + return result + + def cache_info(): + """Report cache statistics""" + with lock: + return _CacheInfo(hits, misses, maxsize, len(cache)) + + def cache_clear(): + """Clear the cache and cache statistics""" + nonlocal hits, misses + with lock: + cache.clear() + hits = misses = 0 + + wrapper.cache_info = cache_info + wrapper.cache_clear = cache_clear + return wrapper + + return decorating_function |