Mercurial > cpython-lru_cache-weakref

annotate Lib/functools.py @ 79691:05c8928362ee

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge __next__ method link fixes with 3.3.
author Ezio Melotti <ezio.melotti@gmail.com>
date Fri, 12 Oct 2012 13:46:37 +0300
parents 2d5ca0ea2aab
children 1920422626a5 fcfaca024160
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
1 """functools.py - Tools for working with functions and callable objects
38669
19fd6141940d Partially merge trunk into p3yk. The removal of Mac/Tools is confusing svn
Thomas Wouters <thomas@python.org>
parents:
diff changeset
2 """
19fd6141940d Partially merge trunk into p3yk. The removal of Mac/Tools is confusing svn
Thomas Wouters <thomas@python.org>
parents:
diff changeset
3 # Python module wrapper for _functools C module
19fd6141940d Partially merge trunk into p3yk. The removal of Mac/Tools is confusing svn
Thomas Wouters <thomas@python.org>
parents:
diff changeset
4 # to allow utilities written in Python to be added
19fd6141940d Partially merge trunk into p3yk. The removal of Mac/Tools is confusing svn
Thomas Wouters <thomas@python.org>
parents:
diff changeset
5 # to the functools module.
19fd6141940d Partially merge trunk into p3yk. The removal of Mac/Tools is confusing svn
Thomas Wouters <thomas@python.org>
parents:
diff changeset
6 # Written by Nick Coghlan <ncoghlan at gmail.com>
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
7 # and Raymond Hettinger <python at rcn.com>
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
8 # Copyright (C) 2006-2010 Python Software Foundation.
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
9 # See C source code for _functools credits/copyright
38669
19fd6141940d Partially merge trunk into p3yk. The removal of Mac/Tools is confusing svn
Thomas Wouters <thomas@python.org>
parents:
diff changeset
10
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
11 __all__ = ['update_wrapper', 'wraps', 'WRAPPER_ASSIGNMENTS', 'WRAPPER_UPDATES',
64630
470a5360570c add reduce and partial to __all__
Benjamin Peterson <benjamin@python.org>
parents: 64502
diff changeset
12 'total_ordering', 'cmp_to_key', 'lru_cache', 'reduce', 'partial']
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
13
39691
c4d8c054616c Part of SF patch #1513870 (the still relevant part) -- add reduce() to
Guido van Rossum <guido@python.org>
parents: 38673
diff changeset
14 from _functools import partial, reduce
75729
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
15 from collections import namedtuple
64016
d8d0abe61e83 Add locks to make the caches well behaved in multi-threaded code.
Raymond Hettinger <python@rcn.com>
parents: 63823
diff changeset
16 try:
d8d0abe61e83 Add locks to make the caches well behaved in multi-threaded code.
Raymond Hettinger <python@rcn.com>
parents: 63823
diff changeset
17 from _thread import allocate_lock as Lock
d8d0abe61e83 Add locks to make the caches well behaved in multi-threaded code.
Raymond Hettinger <python@rcn.com>
parents: 63823
diff changeset
18 except:
d8d0abe61e83 Add locks to make the caches well behaved in multi-threaded code.
Raymond Hettinger <python@rcn.com>
parents: 63823
diff changeset
19 from _dummy_thread import allocate_lock as Lock
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
20
75776
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
21
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
22 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
23 ### update_wrapper() and wraps() decorator
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
24 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
25
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
26 # update_wrapper() and wraps() are tools to help write
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
27 # wrapper functions that can handle naive introspection
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
28
73943
963e98f5ad31 Issue #13544: Add __qualname__ to functools.WRAPPER_ASSIGNMENTS.
Meador Inge <meadori@gmail.com>
parents: 73019
diff changeset
29 WRAPPER_ASSIGNMENTS = ('__module__', '__name__', '__qualname__', '__doc__',
963e98f5ad31 Issue #13544: Add __qualname__ to functools.WRAPPER_ASSIGNMENTS.
Meador Inge <meadori@gmail.com>
parents: 73019
diff changeset
30 '__annotations__')
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
31 WRAPPER_UPDATES = ('__dict__',)
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
32 def update_wrapper(wrapper,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
33 wrapped,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
34 assigned = WRAPPER_ASSIGNMENTS,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
35 updated = WRAPPER_UPDATES):
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
36 """Update a wrapper function to look like the wrapped function
38669
19fd6141940d Partially merge trunk into p3yk. The removal of Mac/Tools is confusing svn
Thomas Wouters <thomas@python.org>
parents:
diff changeset
37
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
38 wrapper is the function to be updated
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
39 wrapped is the original function
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
40 assigned is a tuple naming the attributes assigned directly
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
41 from the wrapped function to the wrapper function (defaults to
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
42 functools.WRAPPER_ASSIGNMENTS)
40450
cc992d75d5b3 Four months of trunk changes (including a few releases...)
Thomas Wouters <thomas@python.org>
parents: 39691
diff changeset
43 updated is a tuple naming the attributes of the wrapper that
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
44 are updated with the corresponding attribute from the wrapped
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
45 function (defaults to functools.WRAPPER_UPDATES)
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
46 """
64102
77bf58296c87 Document and test the resolution of issue 3445 (tolerate missing attributes in functools.update_wrapper, previously implemented as a side effect of the __annotations__ copying patch) and implement issue 9567 (add a __wrapped__ attribute when using update_wrapper)
Nick Coghlan <ncoghlan@gmail.com>
parents: 64030
diff changeset
47 wrapper.__wrapped__ = wrapped
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
48 for attr in assigned:
64102
77bf58296c87 Document and test the resolution of issue 3445 (tolerate missing attributes in functools.update_wrapper, previously implemented as a side effect of the __annotations__ copying patch) and implement issue 9567 (add a __wrapped__ attribute when using update_wrapper)
Nick Coghlan <ncoghlan@gmail.com>
parents: 64030
diff changeset
49 try:
77bf58296c87 Document and test the resolution of issue 3445 (tolerate missing attributes in functools.update_wrapper, previously implemented as a side effect of the __annotations__ copying patch) and implement issue 9567 (add a __wrapped__ attribute when using update_wrapper)
Nick Coghlan <ncoghlan@gmail.com>
parents: 64030
diff changeset
50 value = getattr(wrapped, attr)
77bf58296c87 Document and test the resolution of issue 3445 (tolerate missing attributes in functools.update_wrapper, previously implemented as a side effect of the __annotations__ copying patch) and implement issue 9567 (add a __wrapped__ attribute when using update_wrapper)
Nick Coghlan <ncoghlan@gmail.com>
parents: 64030
diff changeset
51 except AttributeError:
77bf58296c87 Document and test the resolution of issue 3445 (tolerate missing attributes in functools.update_wrapper, previously implemented as a side effect of the __annotations__ copying patch) and implement issue 9567 (add a __wrapped__ attribute when using update_wrapper)
Nick Coghlan <ncoghlan@gmail.com>
parents: 64030
diff changeset
52 pass
77bf58296c87 Document and test the resolution of issue 3445 (tolerate missing attributes in functools.update_wrapper, previously implemented as a side effect of the __annotations__ copying patch) and implement issue 9567 (add a __wrapped__ attribute when using update_wrapper)
Nick Coghlan <ncoghlan@gmail.com>
parents: 64030
diff changeset
53 else:
77bf58296c87 Document and test the resolution of issue 3445 (tolerate missing attributes in functools.update_wrapper, previously implemented as a side effect of the __annotations__ copying patch) and implement issue 9567 (add a __wrapped__ attribute when using update_wrapper)
Nick Coghlan <ncoghlan@gmail.com>
parents: 64030
diff changeset
54 setattr(wrapper, attr, value)
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
55 for attr in updated:
40450
cc992d75d5b3 Four months of trunk changes (including a few releases...)
Thomas Wouters <thomas@python.org>
parents: 39691
diff changeset
56 getattr(wrapper, attr).update(getattr(wrapped, attr, {}))
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
57 # Return the wrapper so this can be used as a decorator via partial()
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
58 return wrapper
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
59
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
60 def wraps(wrapped,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
61 assigned = WRAPPER_ASSIGNMENTS,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
62 updated = WRAPPER_UPDATES):
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
63 """Decorator factory to apply update_wrapper() to a wrapper function
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
64
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
65 Returns a decorator that invokes update_wrapper() with the decorated
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
66 function as the wrapper argument and the arguments to wraps() as the
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
67 remaining arguments. Default arguments are as for update_wrapper().
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
68 This is a convenience function to simplify applying partial() to
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
69 update_wrapper().
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
70 """
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
71 return partial(update_wrapper, wrapped=wrapped,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
72 assigned=assigned, updated=updated)
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
73
75776
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
74
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
75 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
76 ### total_ordering class decorator
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
77 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
78
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
79 def total_ordering(cls):
61761
82a4483d9c4a Merged revisions 80068 via svnmerge from
Georg Brandl <georg@python.org>
parents: 60479
diff changeset
80 """Class decorator that fills in missing ordering methods"""
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
81 convert = {
67458
6492a713887e Issue #10042: Fixed the total_ordering decorator to handle cross-type
Raymond Hettinger <python@rcn.com>
parents: 66582
diff changeset
82 '__lt__': [('__gt__', lambda self, other: not (self < other or self == other)),
6492a713887e Issue #10042: Fixed the total_ordering decorator to handle cross-type
Raymond Hettinger <python@rcn.com>
parents: 66582
diff changeset
83 ('__le__', lambda self, other: self < other or self == other),
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
84 ('__ge__', lambda self, other: not self < other)],
67458
6492a713887e Issue #10042: Fixed the total_ordering decorator to handle cross-type
Raymond Hettinger <python@rcn.com>
parents: 66582
diff changeset
85 '__le__': [('__ge__', lambda self, other: not self <= other or self == other),
6492a713887e Issue #10042: Fixed the total_ordering decorator to handle cross-type
Raymond Hettinger <python@rcn.com>
parents: 66582
diff changeset
86 ('__lt__', lambda self, other: self <= other and not self == other),
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
87 ('__gt__', lambda self, other: not self <= other)],
67458
6492a713887e Issue #10042: Fixed the total_ordering decorator to handle cross-type
Raymond Hettinger <python@rcn.com>
parents: 66582
diff changeset
88 '__gt__': [('__lt__', lambda self, other: not (self > other or self == other)),
6492a713887e Issue #10042: Fixed the total_ordering decorator to handle cross-type
Raymond Hettinger <python@rcn.com>
parents: 66582
diff changeset
89 ('__ge__', lambda self, other: self > other or self == other),
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
90 ('__le__', lambda self, other: not self > other)],
67458
6492a713887e Issue #10042: Fixed the total_ordering decorator to handle cross-type
Raymond Hettinger <python@rcn.com>
parents: 66582
diff changeset
91 '__ge__': [('__le__', lambda self, other: (not self >= other) or self == other),
6492a713887e Issue #10042: Fixed the total_ordering decorator to handle cross-type
Raymond Hettinger <python@rcn.com>
parents: 66582
diff changeset
92 ('__gt__', lambda self, other: self >= other and not self == other),
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
93 ('__lt__', lambda self, other: not self >= other)]
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
94 }
64776
985072cd31d0 Improve comment
Raymond Hettinger <python@rcn.com>
parents: 64755
diff changeset
95 # Find user-defined comparisons (not those inherited from object).
64755
f643d53c51bd Future proof total_ordering against changes in methods defined on object.
Raymond Hettinger <python@rcn.com>
parents: 64642
diff changeset
96 roots = [op for op in convert if getattr(cls, op, None) is not getattr(object, op, None)]
60479
805512329c75 Issue 8361: Remove assert from functools.total_ordering
Raymond Hettinger <python@rcn.com>
parents: 60370
diff changeset
97 if not roots:
805512329c75 Issue 8361: Remove assert from functools.total_ordering
Raymond Hettinger <python@rcn.com>
parents: 60370
diff changeset
98 raise ValueError('must define at least one ordering operation: < > <= >=')
805512329c75 Issue 8361: Remove assert from functools.total_ordering
Raymond Hettinger <python@rcn.com>
parents: 60370
diff changeset
99 root = max(roots) # prefer __lt__ to __le__ to __gt__ to __ge__
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
100 for opname, opfunc in convert[root]:
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
101 if opname not in roots:
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
102 opfunc.__name__ = opname
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
103 opfunc.__doc__ = getattr(int, opname).__doc__
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
104 setattr(cls, opname, opfunc)
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
105 return cls
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
106
75776
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
107
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
108 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
109 ### cmp_to_key() function converter
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
110 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
111
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
112 def cmp_to_key(mycmp):
61761
82a4483d9c4a Merged revisions 80068 via svnmerge from
Georg Brandl <georg@python.org>
parents: 60479
diff changeset
113 """Convert a cmp= function into a key= function"""
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
114 class K(object):
68824
97799a54728e Issue #11628: cmp_to_key should use __slots__.
Raymond Hettinger <python@rcn.com>
parents: 68257
diff changeset
115 __slots__ = ['obj']
69862
9f58612bc334 Sync-up minor code edits with the default branch.
Raymond Hettinger <python@rcn.com>
parents: 69810
diff changeset
116 def __init__(self, obj):
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
117 self.obj = obj
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
118 def __lt__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
119 return mycmp(self.obj, other.obj) < 0
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
120 def __gt__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
121 return mycmp(self.obj, other.obj) > 0
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
122 def __eq__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
123 return mycmp(self.obj, other.obj) == 0
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
124 def __le__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
125 return mycmp(self.obj, other.obj) <= 0
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
126 def __ge__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
127 return mycmp(self.obj, other.obj) >= 0
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
128 def __ne__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
129 return mycmp(self.obj, other.obj) != 0
69810
2675415c57c1 Fix __hash__ in functools.cmp_to_key() to work with collections.Hashable.
Raymond Hettinger <python@rcn.com>
parents: 68824
diff changeset
130 __hash__ = None
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
131 return K
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
132
69150
a03fb2fc3ed8 Issue #11707: Fast C version of functools.cmp_to_key()
Raymond Hettinger <python@rcn.com>
parents: 68825
diff changeset
133 try:
a03fb2fc3ed8 Issue #11707: Fast C version of functools.cmp_to_key()
Raymond Hettinger <python@rcn.com>
parents: 68825
diff changeset
134 from _functools import cmp_to_key
a03fb2fc3ed8 Issue #11707: Fast C version of functools.cmp_to_key()
Raymond Hettinger <python@rcn.com>
parents: 68825
diff changeset
135 except ImportError:
a03fb2fc3ed8 Issue #11707: Fast C version of functools.cmp_to_key()
Raymond Hettinger <python@rcn.com>
parents: 68825
diff changeset
136 pass
a03fb2fc3ed8 Issue #11707: Fast C version of functools.cmp_to_key()
Raymond Hettinger <python@rcn.com>
parents: 68825
diff changeset
137
75776
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
138
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
139 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
140 ### LRU Cache function decorator
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
141 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
142
75775
70672d21b9fd Minor beautification.
Raymond Hettinger <python@rcn.com>
parents: 75760
diff changeset
143 _CacheInfo = namedtuple("CacheInfo", ["hits", "misses", "maxsize", "currsize"])
66550
312b2916cfd4 Issue 10586: change the new functools.lru_cache implementation to expose the maximum and current cache sizes through the public statistics API. This API is now a single function that returns a named tuple.
Nick Coghlan <ncoghlan@gmail.com>
parents: 66441
diff changeset
144
77336
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
145 class _HashedSeq(list):
76681
f981fe3b8bf7 Move make_key() out of the decorator body. Make keys that only need to be hashed once.
Raymond Hettinger <python@rcn.com>
parents: 76680
diff changeset
146 __slots__ = 'hashvalue'
f981fe3b8bf7 Move make_key() out of the decorator body. Make keys that only need to be hashed once.
Raymond Hettinger <python@rcn.com>
parents: 76680
diff changeset
147
77336
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
148 def __init__(self, tup, hash=hash):
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
149 self[:] = tup
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
150 self.hashvalue = hash(tup)
76681
f981fe3b8bf7 Move make_key() out of the decorator body. Make keys that only need to be hashed once.
Raymond Hettinger <python@rcn.com>
parents: 76680
diff changeset
151
f981fe3b8bf7 Move make_key() out of the decorator body. Make keys that only need to be hashed once.
Raymond Hettinger <python@rcn.com>
parents: 76680
diff changeset
152 def __hash__(self):
f981fe3b8bf7 Move make_key() out of the decorator body. Make keys that only need to be hashed once.
Raymond Hettinger <python@rcn.com>
parents: 76680
diff changeset
153 return self.hashvalue
f981fe3b8bf7 Move make_key() out of the decorator body. Make keys that only need to be hashed once.
Raymond Hettinger <python@rcn.com>
parents: 76680
diff changeset
154
77336
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
155 def _make_key(args, kwds, typed,
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
156 kwd_mark = (object(),),
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
157 fasttypes = {int, str, frozenset, type(None)},
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
158 sorted=sorted, tuple=tuple, type=type, len=len):
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
159 'Make a cache key from optionally typed positional and keyword arguments'
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
160 key = args
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
161 if kwds:
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
162 sorted_items = sorted(kwds.items())
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
163 key += kwd_mark
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
164 for item in sorted_items:
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
165 key += item
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
166 if typed:
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
167 key += tuple(type(v) for v in args)
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
168 if kwds:
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
169 key += tuple(type(v) for k, v in sorted_items)
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
170 elif len(key) == 1 and type(key[0]) in fasttypes:
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
171 return key[0]
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
172 return _HashedSeq(key)
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
173
77068
1cd147d9c645 Minor change to default lru size. Set default to a power of two.
Raymond Hettinger <python@rcn.com>
parents: 76681
diff changeset
174 def lru_cache(maxsize=128, typed=False):
63823
1086dad50c74 use same quoting as the rest of the file
Benjamin Peterson <benjamin@python.org>
parents: 63745
diff changeset
175 """Least-recently-used cache decorator.
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
176
66582
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
177 If *maxsize* is set to None, the LRU features are disabled and the cache
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
178 can grow without bound.
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
179
73019
cba503a2c468 Issue 13227: Option to make the lru_cache() type specific (suggested by Andrew Koenig).
Raymond Hettinger <python@rcn.com>
parents: 72944
diff changeset
180 If *typed* is True, arguments of different types will be cached separately.
cba503a2c468 Issue 13227: Option to make the lru_cache() type specific (suggested by Andrew Koenig).
Raymond Hettinger <python@rcn.com>
parents: 72944
diff changeset
181 For example, f(3.0) and f(3) will be treated as distinct calls with
cba503a2c468 Issue 13227: Option to make the lru_cache() type specific (suggested by Andrew Koenig).
Raymond Hettinger <python@rcn.com>
parents: 72944
diff changeset
182 distinct results.
cba503a2c468 Issue 13227: Option to make the lru_cache() type specific (suggested by Andrew Koenig).
Raymond Hettinger <python@rcn.com>
parents: 72944
diff changeset
183
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
184 Arguments to the cached function must be hashable.
66441
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
185
76003
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
186 View the cache statistics named tuple (hits, misses, maxsize, currsize)
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
187 with f.cache_info(). Clear the cache and statistics with f.cache_clear().
66578
5cb53f094c1a Doc and docstring nits.
Raymond Hettinger <python@rcn.com>
parents: 66573
diff changeset
188 Access the underlying function with f.__wrapped__.
66441
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
189
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
190 See: http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
191
63823
1086dad50c74 use same quoting as the rest of the file
Benjamin Peterson <benjamin@python.org>
parents: 63745
diff changeset
192 """
75998
123cf2192c79 Minor cleanup: add whitespace, add comments, bring function attribute updates together.
Raymond Hettinger <python@rcn.com>
parents: 75803
diff changeset
193
66441
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
194 # Users should only access the lru_cache through its public API:
66552
f16bf4cae5d7 Neaten-up a bit.
Raymond Hettinger <python@rcn.com>
parents: 66550
diff changeset
195 # cache_info, cache_clear, and f.__wrapped__
66441
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
196 # The internals of the lru_cache are encapsulated for thread safety and
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
197 # to allow the implementation to change (including a possible C version).
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
198
76649
2adcd28a5a3a Factor out shared variables.
Raymond Hettinger <python@rcn.com>
parents: 76643
diff changeset
199 # Constants shared by all lru cache instances:
76656
d4fd58fff480 Track the cache size directly.
Raymond Hettinger <python@rcn.com>
parents: 76649
diff changeset
200 sentinel = object() # unique object used to signal cache misses
77336
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
201 make_key = _make_key # build a key from the function arguments
76649
2adcd28a5a3a Factor out shared variables.
Raymond Hettinger <python@rcn.com>
parents: 76643
diff changeset
202 PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # names for the link fields
2adcd28a5a3a Factor out shared variables.
Raymond Hettinger <python@rcn.com>
parents: 76643
diff changeset
203
75757
51b0711ee672 Refactor calculation of the cache key. Minor code cleanups.
Raymond Hettinger <python@rcn.com>
parents: 75753
diff changeset
204 def decorating_function(user_function):
66441
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
205
76003
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
206 cache = {}
76656
d4fd58fff480 Track the cache size directly.
Raymond Hettinger <python@rcn.com>
parents: 76649
diff changeset
207 hits = misses = currsize = 0
76680
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
208 full = False
76004
1c22c1109824 Fix-up a comment
Raymond Hettinger <python@rcn.com>
parents: 76003
diff changeset
209 cache_get = cache.get # bound method to lookup a key or return None
76003
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
210 lock = Lock() # because linkedlist updates aren't threadsafe
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
211 root = [] # root of the circular doubly linked list
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
212 root[:] = [root, root, None, None] # initialize by pointing to self
75757
51b0711ee672 Refactor calculation of the cache key. Minor code cleanups.
Raymond Hettinger <python@rcn.com>
parents: 75753
diff changeset
213
75802
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
214 if maxsize == 0:
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
215
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
216 def wrapper(*args, **kwds):
76003
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
217 # no caching, just a statistics update after a successful call
75802
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
218 nonlocal misses
75803
b26056192653 Fix whitespace
Raymond Hettinger <python@rcn.com>
parents: 75802
diff changeset
219 result = user_function(*args, **kwds)
75802
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
220 misses += 1
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
221 return result
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
222
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
223 elif maxsize is None:
75776
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
224
66582
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
225 def wrapper(*args, **kwds):
75729
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
226 # simple caching without ordering or size limit
76656
d4fd58fff480 Track the cache size directly.
Raymond Hettinger <python@rcn.com>
parents: 76649
diff changeset
227 nonlocal hits, misses, currsize
76681
f981fe3b8bf7 Move make_key() out of the decorator body. Make keys that only need to be hashed once.
Raymond Hettinger <python@rcn.com>
parents: 76680
diff changeset
228 key = make_key(args, kwds, typed)
76003
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
229 result = cache_get(key, sentinel)
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
230 if result is not sentinel:
66550
312b2916cfd4 Issue 10586: change the new functools.lru_cache implementation to expose the maximum and current cache sizes through the public statistics API. This API is now a single function that returns a named tuple.
Nick Coghlan <ncoghlan@gmail.com>
parents: 66441
diff changeset
231 hits += 1
72943
8365f82f8a13 Issue 13177: Make tracebacks more readable by avoiding chained exceptions in the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 69862
diff changeset
232 return result
8365f82f8a13 Issue 13177: Make tracebacks more readable by avoiding chained exceptions in the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 69862
diff changeset
233 result = user_function(*args, **kwds)
8365f82f8a13 Issue 13177: Make tracebacks more readable by avoiding chained exceptions in the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 69862
diff changeset
234 cache[key] = result
8365f82f8a13 Issue 13177: Make tracebacks more readable by avoiding chained exceptions in the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 69862
diff changeset
235 misses += 1
76656
d4fd58fff480 Track the cache size directly.
Raymond Hettinger <python@rcn.com>
parents: 76649
diff changeset
236 currsize += 1
66582
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
237 return result
75776
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
238
66582
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
239 else:
75776
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
240
66582
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
241 def wrapper(*args, **kwds):
75729
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
242 # size limited caching that tracks accesses by recency
76680
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
243 nonlocal root, hits, misses, currsize, full
76681
f981fe3b8bf7 Move make_key() out of the decorator body. Make keys that only need to be hashed once.
Raymond Hettinger <python@rcn.com>
parents: 76680
diff changeset
244 key = make_key(args, kwds, typed)
72943
8365f82f8a13 Issue 13177: Make tracebacks more readable by avoiding chained exceptions in the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 69862
diff changeset
245 with lock:
75729
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
246 link = cache_get(key)
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
247 if link is not None:
76003
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
248 # move the link to the front of the circular queue
75729
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
249 link_prev, link_next, key, result = link
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
250 link_prev[NEXT] = link_next
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
251 link_next[PREV] = link_prev
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
252 last = root[PREV]
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
253 last[NEXT] = root[PREV] = link
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
254 link[PREV] = last
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
255 link[NEXT] = root
66582
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
256 hits += 1
72943
8365f82f8a13 Issue 13177: Make tracebacks more readable by avoiding chained exceptions in the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 69862
diff changeset
257 return result
8365f82f8a13 Issue 13177: Make tracebacks more readable by avoiding chained exceptions in the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 69862
diff changeset
258 result = user_function(*args, **kwds)
8365f82f8a13 Issue 13177: Make tracebacks more readable by avoiding chained exceptions in the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 69862
diff changeset
259 with lock:
76675
b3aeaef6c315 Handle a possible race condition
Raymond Hettinger <python@rcn.com>
parents: 76656
diff changeset
260 if key in cache:
b3aeaef6c315 Handle a possible race condition
Raymond Hettinger <python@rcn.com>
parents: 76656
diff changeset
261 # getting here means that this same key was added to the
b3aeaef6c315 Handle a possible race condition
Raymond Hettinger <python@rcn.com>
parents: 76656
diff changeset
262 # cache while the lock was released. since the link
b3aeaef6c315 Handle a possible race condition
Raymond Hettinger <python@rcn.com>
parents: 76656
diff changeset
263 # update is already done, we need only return the
b3aeaef6c315 Handle a possible race condition
Raymond Hettinger <python@rcn.com>
parents: 76656
diff changeset
264 # computed result and update the count of misses.
b3aeaef6c315 Handle a possible race condition
Raymond Hettinger <python@rcn.com>
parents: 76656
diff changeset
265 pass
76680
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
266 elif full:
76002
476f641a0455 No need to create and destroy links when updating a fixed-sized circular queue.
Raymond Hettinger <python@rcn.com>
parents: 75998
diff changeset
267 # use root to store the new key and result
476f641a0455 No need to create and destroy links when updating a fixed-sized circular queue.
Raymond Hettinger <python@rcn.com>
parents: 75998
diff changeset
268 root[KEY] = key
476f641a0455 No need to create and destroy links when updating a fixed-sized circular queue.
Raymond Hettinger <python@rcn.com>
parents: 75998
diff changeset
269 root[RESULT] = result
476f641a0455 No need to create and destroy links when updating a fixed-sized circular queue.
Raymond Hettinger <python@rcn.com>
parents: 75998
diff changeset
270 cache[key] = root
476f641a0455 No need to create and destroy links when updating a fixed-sized circular queue.
Raymond Hettinger <python@rcn.com>
parents: 75998
diff changeset
271 # empty the oldest link and make it the new root
476f641a0455 No need to create and destroy links when updating a fixed-sized circular queue.
Raymond Hettinger <python@rcn.com>
parents: 75998
diff changeset
272 root = root[NEXT]
476f641a0455 No need to create and destroy links when updating a fixed-sized circular queue.
Raymond Hettinger <python@rcn.com>
parents: 75998
diff changeset
273 del cache[root[KEY]]
76004
1c22c1109824 Fix-up a comment
Raymond Hettinger <python@rcn.com>
parents: 76003
diff changeset
274 root[KEY] = root[RESULT] = None
76680
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
275 else:
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
276 # put result in a new link at the front of the queue
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
277 last = root[PREV]
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
278 link = [last, root, key, result]
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
279 cache[key] = last[NEXT] = root[PREV] = link
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
280 currsize += 1
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
281 full = (currsize == maxsize)
72943
8365f82f8a13 Issue 13177: Make tracebacks more readable by avoiding chained exceptions in the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 69862
diff changeset
282 misses += 1
66582
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
283 return result
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
284
66550
312b2916cfd4 Issue 10586: change the new functools.lru_cache implementation to expose the maximum and current cache sizes through the public statistics API. This API is now a single function that returns a named tuple.
Nick Coghlan <ncoghlan@gmail.com>
parents: 66441
diff changeset
285 def cache_info():
66552
f16bf4cae5d7 Neaten-up a bit.
Raymond Hettinger <python@rcn.com>
parents: 66550
diff changeset
286 """Report cache statistics"""
66550
312b2916cfd4 Issue 10586: change the new functools.lru_cache implementation to expose the maximum and current cache sizes through the public statistics API. This API is now a single function that returns a named tuple.
Nick Coghlan <ncoghlan@gmail.com>
parents: 66441
diff changeset
287 with lock:
76656
d4fd58fff480 Track the cache size directly.
Raymond Hettinger <python@rcn.com>
parents: 76649
diff changeset
288 return _CacheInfo(hits, misses, maxsize, currsize)
66550
312b2916cfd4 Issue 10586: change the new functools.lru_cache implementation to expose the maximum and current cache sizes through the public statistics API. This API is now a single function that returns a named tuple.
Nick Coghlan <ncoghlan@gmail.com>
parents: 66441
diff changeset
289
64448
61c44793238d Adopt more descriptive attribute names as suggested on python-dev.
Raymond Hettinger <python@rcn.com>
parents: 64382
diff changeset
290 def cache_clear():
63823
1086dad50c74 use same quoting as the rest of the file
Benjamin Peterson <benjamin@python.org>
parents: 63745
diff changeset
291 """Clear the cache and cache statistics"""
76680
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
292 nonlocal hits, misses, currsize, full
64016
d8d0abe61e83 Add locks to make the caches well behaved in multi-threaded code.
Raymond Hettinger <python@rcn.com>
parents: 63823
diff changeset
293 with lock:
d8d0abe61e83 Add locks to make the caches well behaved in multi-threaded code.
Raymond Hettinger <python@rcn.com>
parents: 63823
diff changeset
294 cache.clear()
75752
087da2a353e6 clear the root with the cache
Benjamin Peterson <benjamin@python.org>
parents: 75749
diff changeset
295 root[:] = [root, root, None, None]
76656
d4fd58fff480 Track the cache size directly.
Raymond Hettinger <python@rcn.com>
parents: 76649
diff changeset
296 hits = misses = currsize = 0
76680
f5bb290c751a Use a flag to indicate when the circular queue is fully populated and stable.
Raymond Hettinger <python@rcn.com>
parents: 76675
diff changeset
297 full = False
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
298
66550
312b2916cfd4 Issue 10586: change the new functools.lru_cache implementation to expose the maximum and current cache sizes through the public statistics API. This API is now a single function that returns a named tuple.
Nick Coghlan <ncoghlan@gmail.com>
parents: 66441
diff changeset
299 wrapper.cache_info = cache_info
64448
61c44793238d Adopt more descriptive attribute names as suggested on python-dev.
Raymond Hettinger <python@rcn.com>
parents: 64382
diff changeset
300 wrapper.cache_clear = cache_clear
75998
123cf2192c79 Minor cleanup: add whitespace, add comments, bring function attribute updates together.
Raymond Hettinger <python@rcn.com>
parents: 75803
diff changeset
301 return update_wrapper(wrapper, user_function)
66441
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
302
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
303 return decorating_function