blob: 9f024f14d7dec877ce79d3bda4ddd652c2b7755c [file] [log] [blame]
Thomas Wouters73e5a5b2006-06-08 15:35:45 +00001"""functools.py - Tools for working with functions and callable objects
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00002"""
3# Python module wrapper for _functools C module
4# to allow utilities written in Python to be added
5# to the functools module.
6# Written by Nick Coghlan <ncoghlan at gmail.com>
Georg Brandl2e7346a2010-07-31 18:09:23 +00007# and Raymond Hettinger <python at rcn.com>
8# Copyright (C) 2006-2010 Python Software Foundation.
Thomas Wouters73e5a5b2006-06-08 15:35:45 +00009# See C source code for _functools credits/copyright
Thomas Wouters4d70c3d2006-06-08 14:42:34 +000010
Georg Brandl2e7346a2010-07-31 18:09:23 +000011__all__ = ['update_wrapper', 'wraps', 'WRAPPER_ASSIGNMENTS', 'WRAPPER_UPDATES',
Benjamin Peterson1017ae52010-09-10 23:35:52 +000012 'total_ordering', 'cmp_to_key', 'lru_cache', 'reduce', 'partial']
Georg Brandl2e7346a2010-07-31 18:09:23 +000013
Guido van Rossum0919a1a2006-08-26 20:49:04 +000014from _functools import partial, reduce
Raymond Hettingerec0e9102012-03-16 01:16:31 -070015from collections import namedtuple
Raymond Hettingercbe88132010-08-14 22:22:10 +000016try:
17 from _thread import allocate_lock as Lock
18except:
19 from _dummy_thread import allocate_lock as Lock
Thomas Wouters4d70c3d2006-06-08 14:42:34 +000020
Raymond Hettingerbc8e81d2012-03-17 00:24:09 -070021
22################################################################################
23### update_wrapper() and wraps() decorator
24################################################################################
25
Thomas Wouters73e5a5b2006-06-08 15:35:45 +000026# update_wrapper() and wraps() are tools to help write
27# wrapper functions that can handle naive introspection
28
Meador Ingeff7f64c2011-12-11 22:37:31 -060029WRAPPER_ASSIGNMENTS = ('__module__', '__name__', '__qualname__', '__doc__',
30 '__annotations__')
Thomas Wouters73e5a5b2006-06-08 15:35:45 +000031WRAPPER_UPDATES = ('__dict__',)
32def update_wrapper(wrapper,
33 wrapped,
34 assigned = WRAPPER_ASSIGNMENTS,
35 updated = WRAPPER_UPDATES):
36 """Update a wrapper function to look like the wrapped function
37
38 wrapper is the function to be updated
39 wrapped is the original function
40 assigned is a tuple naming the attributes assigned directly
41 from the wrapped function to the wrapper function (defaults to
42 functools.WRAPPER_ASSIGNMENTS)
Thomas Wouters89f507f2006-12-13 04:49:30 +000043 updated is a tuple naming the attributes of the wrapper that
Thomas Wouters73e5a5b2006-06-08 15:35:45 +000044 are updated with the corresponding attribute from the wrapped
45 function (defaults to functools.WRAPPER_UPDATES)
46 """
Nick Coghlan98876832010-08-17 06:17:18 +000047 wrapper.__wrapped__ = wrapped
Thomas Wouters73e5a5b2006-06-08 15:35:45 +000048 for attr in assigned:
Nick Coghlan98876832010-08-17 06:17:18 +000049 try:
50 value = getattr(wrapped, attr)
51 except AttributeError:
52 pass
53 else:
54 setattr(wrapper, attr, value)
Thomas Wouters73e5a5b2006-06-08 15:35:45 +000055 for attr in updated:
Thomas Wouters89f507f2006-12-13 04:49:30 +000056 getattr(wrapper, attr).update(getattr(wrapped, attr, {}))
Thomas Wouters73e5a5b2006-06-08 15:35:45 +000057 # Return the wrapper so this can be used as a decorator via partial()
58 return wrapper
59
60def wraps(wrapped,
61 assigned = WRAPPER_ASSIGNMENTS,
62 updated = WRAPPER_UPDATES):
63 """Decorator factory to apply update_wrapper() to a wrapper function
64
65 Returns a decorator that invokes update_wrapper() with the decorated
66 function as the wrapper argument and the arguments to wraps() as the
67 remaining arguments. Default arguments are as for update_wrapper().
68 This is a convenience function to simplify applying partial() to
69 update_wrapper().
70 """
71 return partial(update_wrapper, wrapped=wrapped,
72 assigned=assigned, updated=updated)
Raymond Hettingerc50846a2010-04-05 18:56:31 +000073
Raymond Hettingerbc8e81d2012-03-17 00:24:09 -070074
75################################################################################
76### total_ordering class decorator
77################################################################################
78
Raymond Hettingerc50846a2010-04-05 18:56:31 +000079def total_ordering(cls):
Georg Brandle5a26732010-05-19 21:06:36 +000080 """Class decorator that fills in missing ordering methods"""
Raymond Hettingerc50846a2010-04-05 18:56:31 +000081 convert = {
Raymond Hettinger23f9fc32011-01-08 07:01:56 +000082 '__lt__': [('__gt__', lambda self, other: not (self < other or self == other)),
83 ('__le__', lambda self, other: self < other or self == other),
Raymond Hettingerc50846a2010-04-05 18:56:31 +000084 ('__ge__', lambda self, other: not self < other)],
Raymond Hettinger23f9fc32011-01-08 07:01:56 +000085 '__le__': [('__ge__', lambda self, other: not self <= other or self == other),
86 ('__lt__', lambda self, other: self <= other and not self == other),
Raymond Hettingerc50846a2010-04-05 18:56:31 +000087 ('__gt__', lambda self, other: not self <= other)],
Raymond Hettinger23f9fc32011-01-08 07:01:56 +000088 '__gt__': [('__lt__', lambda self, other: not (self > other or self == other)),
89 ('__ge__', lambda self, other: self > other or self == other),
Raymond Hettingerc50846a2010-04-05 18:56:31 +000090 ('__le__', lambda self, other: not self > other)],
Raymond Hettinger23f9fc32011-01-08 07:01:56 +000091 '__ge__': [('__le__', lambda self, other: (not self >= other) or self == other),
92 ('__gt__', lambda self, other: self >= other and not self == other),
Raymond Hettingerc50846a2010-04-05 18:56:31 +000093 ('__lt__', lambda self, other: not self >= other)]
94 }
Raymond Hettinger3255c632010-09-16 00:31:21 +000095 # Find user-defined comparisons (not those inherited from object).
Raymond Hettinger1006bd42010-09-14 22:55:13 +000096 roots = [op for op in convert if getattr(cls, op, None) is not getattr(object, op, None)]
Raymond Hettinger56de7e22010-04-10 16:59:03 +000097 if not roots:
98 raise ValueError('must define at least one ordering operation: < > <= >=')
99 root = max(roots) # prefer __lt__ to __le__ to __gt__ to __ge__
Raymond Hettingerc50846a2010-04-05 18:56:31 +0000100 for opname, opfunc in convert[root]:
101 if opname not in roots:
102 opfunc.__name__ = opname
103 opfunc.__doc__ = getattr(int, opname).__doc__
104 setattr(cls, opname, opfunc)
105 return cls
106
Raymond Hettingerbc8e81d2012-03-17 00:24:09 -0700107
108################################################################################
109### cmp_to_key() function converter
110################################################################################
111
Raymond Hettingerc50846a2010-04-05 18:56:31 +0000112def cmp_to_key(mycmp):
Georg Brandle5a26732010-05-19 21:06:36 +0000113 """Convert a cmp= function into a key= function"""
Raymond Hettingerc50846a2010-04-05 18:56:31 +0000114 class K(object):
Raymond Hettingera0d1d962011-03-21 17:50:28 -0700115 __slots__ = ['obj']
Raymond Hettinger7ab9e222011-04-05 02:33:54 -0700116 def __init__(self, obj):
Raymond Hettingerc50846a2010-04-05 18:56:31 +0000117 self.obj = obj
118 def __lt__(self, other):
119 return mycmp(self.obj, other.obj) < 0
120 def __gt__(self, other):
121 return mycmp(self.obj, other.obj) > 0
122 def __eq__(self, other):
123 return mycmp(self.obj, other.obj) == 0
124 def __le__(self, other):
125 return mycmp(self.obj, other.obj) <= 0
126 def __ge__(self, other):
127 return mycmp(self.obj, other.obj) >= 0
128 def __ne__(self, other):
129 return mycmp(self.obj, other.obj) != 0
Raymond Hettinger003be522011-05-03 11:01:32 -0700130 __hash__ = None
Raymond Hettingerc50846a2010-04-05 18:56:31 +0000131 return K
Georg Brandl2e7346a2010-07-31 18:09:23 +0000132
Raymond Hettinger7ab9e222011-04-05 02:33:54 -0700133try:
134 from _functools import cmp_to_key
135except ImportError:
136 pass
137
Raymond Hettingerbc8e81d2012-03-17 00:24:09 -0700138
139################################################################################
140### LRU Cache function decorator
141################################################################################
142
Raymond Hettingerdce583e2012-03-16 22:12:20 -0700143_CacheInfo = namedtuple("CacheInfo", ["hits", "misses", "maxsize", "currsize"])
Nick Coghlan234515a2010-11-30 06:19:46 +0000144
Raymond Hettinger9acbb602012-04-30 22:32:16 -0700145class _CacheKey(list):
146 'Make a cache key from optionally typed positional and keyword arguments'
147
148 __slots__ = 'hashvalue'
149
150 def __init__(self, args, kwds, typed,
151 kwd_mark = (object(),),
152 sorted=sorted, tuple=tuple, type=type, hash=hash):
153 key = args
154 if kwds:
155 sorted_items = sorted(kwds.items())
156 key += kwd_mark
157 for item in sorted_items:
158 key += item
159 if typed:
160 key += tuple(type(v) for v in args)
161 if kwds:
162 key += tuple(type(v) for k, v in sorted_items)
163 self[:] = key
164 self.hashvalue = hash(key) # so we only have to hash just once
165
166 def __hash__(self):
167 return self.hashvalue
168
Raymond Hettinger010ce322012-05-19 21:20:48 -0700169def lru_cache(maxsize=128, typed=False):
Benjamin Peterson1f594ad2010-08-08 13:17:07 +0000170 """Least-recently-used cache decorator.
Georg Brandl2e7346a2010-07-31 18:09:23 +0000171
Raymond Hettingerc79fb0e2010-12-01 03:45:41 +0000172 If *maxsize* is set to None, the LRU features are disabled and the cache
173 can grow without bound.
174
Raymond Hettingercd9fdfd2011-10-20 08:57:45 -0700175 If *typed* is True, arguments of different types will be cached separately.
176 For example, f(3.0) and f(3) will be treated as distinct calls with
177 distinct results.
178
Georg Brandl2e7346a2010-07-31 18:09:23 +0000179 Arguments to the cached function must be hashable.
Raymond Hettinger5fa40c02010-11-25 08:11:57 +0000180
Raymond Hettinger7f7a5a72012-03-30 21:50:40 -0700181 View the cache statistics named tuple (hits, misses, maxsize, currsize)
182 with f.cache_info(). Clear the cache and statistics with f.cache_clear().
Raymond Hettinger00f2f972010-12-01 00:47:56 +0000183 Access the underlying function with f.__wrapped__.
Raymond Hettinger5fa40c02010-11-25 08:11:57 +0000184
185 See: http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used
Georg Brandl2e7346a2010-07-31 18:09:23 +0000186
Benjamin Peterson1f594ad2010-08-08 13:17:07 +0000187 """
Raymond Hettinger1ff50df2012-03-30 13:15:48 -0700188
Raymond Hettinger5fa40c02010-11-25 08:11:57 +0000189 # Users should only access the lru_cache through its public API:
Raymond Hettinger5e20bab2010-11-30 07:13:04 +0000190 # cache_info, cache_clear, and f.__wrapped__
Raymond Hettinger5fa40c02010-11-25 08:11:57 +0000191 # The internals of the lru_cache are encapsulated for thread safety and
192 # to allow the implementation to change (including a possible C version).
193
Raymond Hettinger9f0ab9f2012-04-29 14:55:27 -0700194 # Constants shared by all lru cache instances:
Raymond Hettingerb6b98c02012-04-29 18:09:02 -0700195 sentinel = object() # unique object used to signal cache misses
Raymond Hettinger9acbb602012-04-30 22:32:16 -0700196 make_key = _CacheKey # build a key from the function arguments
Raymond Hettinger9f0ab9f2012-04-29 14:55:27 -0700197 PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # names for the link fields
198
Raymond Hettinger6e8c8172012-03-16 16:53:05 -0700199 def decorating_function(user_function):
Raymond Hettinger5fa40c02010-11-25 08:11:57 +0000200
Raymond Hettinger7f7a5a72012-03-30 21:50:40 -0700201 cache = {}
Raymond Hettingerb6b98c02012-04-29 18:09:02 -0700202 hits = misses = currsize = 0
Raymond Hettinger018b4fb2012-04-30 20:48:55 -0700203 full = False
Raymond Hettingerc6897852012-03-31 02:19:06 -0700204 cache_get = cache.get # bound method to lookup a key or return None
Raymond Hettinger7f7a5a72012-03-30 21:50:40 -0700205 lock = Lock() # because linkedlist updates aren't threadsafe
206 root = [] # root of the circular doubly linked list
207 root[:] = [root, root, None, None] # initialize by pointing to self
Raymond Hettinger6e8c8172012-03-16 16:53:05 -0700208
Raymond Hettinger7e0c5812012-03-17 15:10:24 -0700209 if maxsize == 0:
210
Raymond Hettinger7e0c5812012-03-17 15:10:24 -0700211 def wrapper(*args, **kwds):
Raymond Hettinger7f7a5a72012-03-30 21:50:40 -0700212 # no caching, just a statistics update after a successful call
Raymond Hettinger7e0c5812012-03-17 15:10:24 -0700213 nonlocal misses
Raymond Hettinger7dabfed2012-03-17 15:11:09 -0700214 result = user_function(*args, **kwds)
Raymond Hettinger7e0c5812012-03-17 15:10:24 -0700215 misses += 1
216 return result
217
218 elif maxsize is None:
Raymond Hettingerbc8e81d2012-03-17 00:24:09 -0700219
Raymond Hettingerc79fb0e2010-12-01 03:45:41 +0000220 def wrapper(*args, **kwds):
Raymond Hettingerec0e9102012-03-16 01:16:31 -0700221 # simple caching without ordering or size limit
Raymond Hettingerb6b98c02012-04-29 18:09:02 -0700222 nonlocal hits, misses, currsize
Raymond Hettinger9acbb602012-04-30 22:32:16 -0700223 key = make_key(args, kwds, typed)
Raymond Hettinger7f7a5a72012-03-30 21:50:40 -0700224 result = cache_get(key, sentinel)
225 if result is not sentinel:
Nick Coghlan234515a2010-11-30 06:19:46 +0000226 hits += 1
Raymond Hettinger4b779b32011-10-15 23:50:42 -0700227 return result
Raymond Hettinger4b779b32011-10-15 23:50:42 -0700228 result = user_function(*args, **kwds)
229 cache[key] = result
230 misses += 1
Raymond Hettingerb6b98c02012-04-29 18:09:02 -0700231 currsize += 1
Raymond Hettingerc79fb0e2010-12-01 03:45:41 +0000232 return result
Raymond Hettingerbc8e81d2012-03-17 00:24:09 -0700233
Raymond Hettingerc79fb0e2010-12-01 03:45:41 +0000234 else:
Raymond Hettingerbc8e81d2012-03-17 00:24:09 -0700235
Raymond Hettingerc79fb0e2010-12-01 03:45:41 +0000236 def wrapper(*args, **kwds):
Raymond Hettingerec0e9102012-03-16 01:16:31 -0700237 # size limited caching that tracks accesses by recency
Raymond Hettinger018b4fb2012-04-30 20:48:55 -0700238 nonlocal root, hits, misses, currsize, full
Raymond Hettinger9acbb602012-04-30 22:32:16 -0700239 key = make_key(args, kwds, typed)
Raymond Hettinger4b779b32011-10-15 23:50:42 -0700240 with lock:
Raymond Hettingerec0e9102012-03-16 01:16:31 -0700241 link = cache_get(key)
242 if link is not None:
Raymond Hettinger7f7a5a72012-03-30 21:50:40 -0700243 # move the link to the front of the circular queue
Raymond Hettingerec0e9102012-03-16 01:16:31 -0700244 link_prev, link_next, key, result = link
245 link_prev[NEXT] = link_next
246 link_next[PREV] = link_prev
247 last = root[PREV]
248 last[NEXT] = root[PREV] = link
249 link[PREV] = last
250 link[NEXT] = root
Raymond Hettingerc79fb0e2010-12-01 03:45:41 +0000251 hits += 1
Raymond Hettinger4b779b32011-10-15 23:50:42 -0700252 return result
Raymond Hettinger4b779b32011-10-15 23:50:42 -0700253 result = user_function(*args, **kwds)
254 with lock:
Raymond Hettinger34d94a22012-04-30 14:14:28 -0700255 if key in cache:
256 # getting here means that this same key was added to the
257 # cache while the lock was released. since the link
258 # update is already done, we need only return the
259 # computed result and update the count of misses.
260 pass
Raymond Hettinger018b4fb2012-04-30 20:48:55 -0700261 elif full:
Raymond Hettinger41eb79a2012-03-30 19:15:18 -0700262 # use root to store the new key and result
263 root[KEY] = key
264 root[RESULT] = result
265 cache[key] = root
266 # empty the oldest link and make it the new root
267 root = root[NEXT]
268 del cache[root[KEY]]
Raymond Hettingerc6897852012-03-31 02:19:06 -0700269 root[KEY] = root[RESULT] = None
Raymond Hettinger018b4fb2012-04-30 20:48:55 -0700270 else:
271 # put result in a new link at the front of the queue
272 last = root[PREV]
273 link = [last, root, key, result]
274 cache[key] = last[NEXT] = root[PREV] = link
275 currsize += 1
276 full = (currsize == maxsize)
Raymond Hettingerec0e9102012-03-16 01:16:31 -0700277 misses += 1
Raymond Hettingerc79fb0e2010-12-01 03:45:41 +0000278 return result
Georg Brandl2e7346a2010-07-31 18:09:23 +0000279
Nick Coghlan234515a2010-11-30 06:19:46 +0000280 def cache_info():
Raymond Hettinger5e20bab2010-11-30 07:13:04 +0000281 """Report cache statistics"""
Nick Coghlan234515a2010-11-30 06:19:46 +0000282 with lock:
Raymond Hettingerb6b98c02012-04-29 18:09:02 -0700283 return _CacheInfo(hits, misses, maxsize, currsize)
Nick Coghlan234515a2010-11-30 06:19:46 +0000284
Raymond Hettinger02566ec2010-09-04 22:46:06 +0000285 def cache_clear():
Benjamin Peterson1f594ad2010-08-08 13:17:07 +0000286 """Clear the cache and cache statistics"""
Raymond Hettinger018b4fb2012-04-30 20:48:55 -0700287 nonlocal hits, misses, currsize, full
Raymond Hettingercbe88132010-08-14 22:22:10 +0000288 with lock:
289 cache.clear()
Benjamin Peterson954cf572012-03-16 18:22:26 -0500290 root[:] = [root, root, None, None]
Raymond Hettingerb6b98c02012-04-29 18:09:02 -0700291 hits = misses = currsize = 0
Raymond Hettinger018b4fb2012-04-30 20:48:55 -0700292 full = False
Georg Brandl2e7346a2010-07-31 18:09:23 +0000293
Nick Coghlan234515a2010-11-30 06:19:46 +0000294 wrapper.cache_info = cache_info
Raymond Hettinger02566ec2010-09-04 22:46:06 +0000295 wrapper.cache_clear = cache_clear
Raymond Hettinger1ff50df2012-03-30 13:15:48 -0700296 return update_wrapper(wrapper, user_function)
Raymond Hettinger5fa40c02010-11-25 08:11:57 +0000297
Georg Brandl2e7346a2010-07-31 18:09:23 +0000298 return decorating_function