Mercurial > cpython-lru_cache-weakref

annotate Lib/functools.py @ 84007:dbfbdf2b5c19 3.3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix #17967: For ftp urls CWD to target instead of hopping to each directory towards target. This fixes a bug where target is accessible, but parent directories are restricted.
author Senthil Kumaran <senthil@uthcode.com>
date Sat, 01 Jun 2013 08:27:06 -0700
parents a9fa8a18d18d
children 02ffc9f94aab
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:
82437
1920422626a5 Don't deadlock on a reentrant call.
Raymond Hettinger <python@rcn.com>
parents: 77336
diff changeset
17 from _thread import RLock
64016
d8d0abe61e83 Add locks to make the caches well behaved in multi-threaded code.
Raymond Hettinger <python@rcn.com>
parents: 63823
diff changeset
18 except:
82450
e9732c25a018 Remove dependency on dummy_threading (to solve a bootstrap problem).
Raymond Hettinger <python@rcn.com>
parents: 82437
diff changeset
19 class RLock:
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
20 'Dummy reentrant lock for builds without threads'
82450
e9732c25a018 Remove dependency on dummy_threading (to solve a bootstrap problem).
Raymond Hettinger <python@rcn.com>
parents: 82437
diff changeset
21 def __enter__(self): pass
e9732c25a018 Remove dependency on dummy_threading (to solve a bootstrap problem).
Raymond Hettinger <python@rcn.com>
parents: 82437
diff changeset
22 def __exit__(self, exctype, excinst, exctb): pass
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
23
75776
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 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
26 ### update_wrapper() and wraps() decorator
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
27 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
28
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
29 # 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
30 # wrapper functions that can handle naive introspection
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
31
73943
963e98f5ad31 Issue #13544: Add __qualname__ to functools.WRAPPER_ASSIGNMENTS.
Meador Inge <meadori@gmail.com>
parents: 73019
diff changeset
32 WRAPPER_ASSIGNMENTS = ('__module__', '__name__', '__qualname__', '__doc__',
963e98f5ad31 Issue #13544: Add __qualname__ to functools.WRAPPER_ASSIGNMENTS.
Meador Inge <meadori@gmail.com>
parents: 73019
diff changeset
33 '__annotations__')
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
34 WRAPPER_UPDATES = ('__dict__',)
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
35 def update_wrapper(wrapper,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
36 wrapped,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
37 assigned = WRAPPER_ASSIGNMENTS,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
38 updated = WRAPPER_UPDATES):
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
39 """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
40
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
41 wrapper is the function to be updated
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
42 wrapped is the original function
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
43 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
44 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
45 functools.WRAPPER_ASSIGNMENTS)
40450
cc992d75d5b3 Four months of trunk changes (including a few releases...)
Thomas Wouters <thomas@python.org>
parents: 39691
diff changeset
46 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
47 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
48 function (defaults to functools.WRAPPER_UPDATES)
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
49 """
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
50 wrapper.__wrapped__ = wrapped
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
51 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
52 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
53 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
54 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
55 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
56 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
57 setattr(wrapper, attr, value)
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
58 for attr in updated:
40450
cc992d75d5b3 Four months of trunk changes (including a few releases...)
Thomas Wouters <thomas@python.org>
parents: 39691
diff changeset
59 getattr(wrapper, attr).update(getattr(wrapped, attr, {}))
38673
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
60 # 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
61 return wrapper
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
62
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
63 def wraps(wrapped,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
64 assigned = WRAPPER_ASSIGNMENTS,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
65 updated = WRAPPER_UPDATES):
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
66 """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
67
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
68 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
69 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
70 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
71 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
72 update_wrapper().
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
73 """
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
74 return partial(update_wrapper, wrapped=wrapped,
a19c20c5e5c7 Merge the rest of the trunk.
Thomas Wouters <thomas@python.org>
parents: 38669
diff changeset
75 assigned=assigned, updated=updated)
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
76
75776
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 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
79 ### total_ordering class decorator
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
80 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
81
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
82 def total_ordering(cls):
61761
82a4483d9c4a Merged revisions 80068 via svnmerge from
Georg Brandl <georg@python.org>
parents: 60479
diff changeset
83 """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
84 convert = {
67458
6492a713887e Issue #10042: Fixed the total_ordering decorator to handle cross-type
Raymond Hettinger <python@rcn.com>
parents: 66582
diff changeset
85 '__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
86 ('__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
87 ('__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
88 '__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
89 ('__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
90 ('__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
91 '__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
92 ('__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
93 ('__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
94 '__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
95 ('__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
96 ('__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
97 }
64776
985072cd31d0 Improve comment
Raymond Hettinger <python@rcn.com>
parents: 64755
diff changeset
98 # 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
99 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
100 if not roots:
805512329c75 Issue 8361: Remove assert from functools.total_ordering
Raymond Hettinger <python@rcn.com>
parents: 60370
diff changeset
101 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
102 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
103 for opname, opfunc in convert[root]:
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
104 if opname not in roots:
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
105 opfunc.__name__ = opname
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
106 opfunc.__doc__ = getattr(int, opname).__doc__
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
107 setattr(cls, opname, opfunc)
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
108 return cls
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
109
75776
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 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
112 ### cmp_to_key() function converter
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
113 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
114
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
115 def cmp_to_key(mycmp):
61761
82a4483d9c4a Merged revisions 80068 via svnmerge from
Georg Brandl <georg@python.org>
parents: 60479
diff changeset
116 """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
117 class K(object):
68824
97799a54728e Issue #11628: cmp_to_key should use __slots__.
Raymond Hettinger <python@rcn.com>
parents: 68257
diff changeset
118 __slots__ = ['obj']
69862
9f58612bc334 Sync-up minor code edits with the default branch.
Raymond Hettinger <python@rcn.com>
parents: 69810
diff changeset
119 def __init__(self, obj):
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
120 self.obj = obj
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
121 def __lt__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
122 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
123 def __gt__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
124 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
125 def __eq__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
126 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
127 def __le__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
128 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
129 def __ge__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
130 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
131 def __ne__(self, other):
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
132 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
133 __hash__ = None
60370
3ce66c6922ab Forward port total_ordering() and cmp_to_key().
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
134 return K
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
135
69150
a03fb2fc3ed8 Issue #11707: Fast C version of functools.cmp_to_key()
Raymond Hettinger <python@rcn.com>
parents: 68825
diff changeset
136 try:
a03fb2fc3ed8 Issue #11707: Fast C version of functools.cmp_to_key()
Raymond Hettinger <python@rcn.com>
parents: 68825
diff changeset
137 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
138 except ImportError:
a03fb2fc3ed8 Issue #11707: Fast C version of functools.cmp_to_key()
Raymond Hettinger <python@rcn.com>
parents: 68825
diff changeset
139 pass
a03fb2fc3ed8 Issue #11707: Fast C version of functools.cmp_to_key()
Raymond Hettinger <python@rcn.com>
parents: 68825
diff changeset
140
75776
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 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
143 ### LRU Cache function decorator
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
144 ################################################################################
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
145
75775
70672d21b9fd Minor beautification.
Raymond Hettinger <python@rcn.com>
parents: 75760
diff changeset
146 _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
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 class _HashedSeq(list):
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
149 """ This class guarantees that hash() will be called no more than once
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
150 per element. This is important because the lru_cache() will hash
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
151 the key multiple times on a cache miss.
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
152
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
153 """
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
154
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
155 __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
156
77336
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
157 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
158 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
159 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
160
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
161 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
162 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
163
77336
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
164 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
165 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
166 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
167 sorted=sorted, tuple=tuple, type=type, len=len):
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
168 """Make a cache key from optionally typed positional and keyword arguments
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
169
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
170 The key is constructed in a way that is flat as possible rather than
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
171 as a nested structure that would take more memory.
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
172
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
173 If there is only a single argument and its data type is known to cache
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
174 its hash value, then that argument is returned without a wrapper. This
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
175 saves space and improves lookup speed.
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
176
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
177 """
77336
2d5ca0ea2aab Separate key creation logic from the sequence class that memoizes its hash value.
Raymond Hettinger <python@rcn.com>
parents: 77068
diff changeset
178 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
179 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
180 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
181 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
182 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
183 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
184 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
185 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
186 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
187 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
188 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
189 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
190 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
191
77068
1cd147d9c645 Minor change to default lru size. Set default to a power of two.
Raymond Hettinger <python@rcn.com>
parents: 76681
diff changeset
192 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
193 """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
194
66582
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
195 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
196 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
197
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
198 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
199 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
200 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
201
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
202 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
203
76003
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
204 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
205 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
206 Access the underlying function with f.__wrapped__.
66441
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
207
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
208 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
209
63823
1086dad50c74 use same quoting as the rest of the file
Benjamin Peterson <benjamin@python.org>
parents: 63745
diff changeset
210 """
75998
123cf2192c79 Minor cleanup: add whitespace, add comments, bring function attribute updates together.
Raymond Hettinger <python@rcn.com>
parents: 75803
diff changeset
211
66441
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
212 # 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
213 # cache_info, cache_clear, and f.__wrapped__
66441
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
214 # 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
215 # 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
216
76649
2adcd28a5a3a Factor out shared variables.
Raymond Hettinger <python@rcn.com>
parents: 76643
diff changeset
217 # Constants shared by all lru cache instances:
76656
d4fd58fff480 Track the cache size directly.
Raymond Hettinger <python@rcn.com>
parents: 76649
diff changeset
218 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
219 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
220 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
221
75757
51b0711ee672 Refactor calculation of the cache key. Minor code cleanups.
Raymond Hettinger <python@rcn.com>
parents: 75753
diff changeset
222 def decorating_function(user_function):
66441
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
223
76003
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
224 cache = {}
82560
a9fa8a18d18d Sync-up with 3.4 to make maintenance easier.
Raymond Hettinger <python@rcn.com>
parents: 82558
diff changeset
225 hits = misses = 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
226 full = False
76004
1c22c1109824 Fix-up a comment
Raymond Hettinger <python@rcn.com>
parents: 76003
diff changeset
227 cache_get = cache.get # bound method to lookup a key or return None
82437
1920422626a5 Don't deadlock on a reentrant call.
Raymond Hettinger <python@rcn.com>
parents: 77336
diff changeset
228 lock = RLock() # because linkedlist updates aren't threadsafe
76003
387dcd8d7dec Fix-up comments and add a sentinel variable for clarity.
Raymond Hettinger <python@rcn.com>
parents: 76002
diff changeset
229 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
230 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
231
75802
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
232 if maxsize == 0:
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
233
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
234 def wrapper(*args, **kwds):
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
235 # 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
236 nonlocal misses
75803
b26056192653 Fix whitespace
Raymond Hettinger <python@rcn.com>
parents: 75802
diff changeset
237 result = user_function(*args, **kwds)
75802
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
238 misses += 1
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
239 return result
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
240
7080f443bd37 Low overhead path for maxsize==0
Raymond Hettinger <python@rcn.com>
parents: 75776
diff changeset
241 elif maxsize is None:
75776
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
242
66582
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
243 def wrapper(*args, **kwds):
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
244 # Simple caching without ordering or size limit
82560
a9fa8a18d18d Sync-up with 3.4 to make maintenance easier.
Raymond Hettinger <python@rcn.com>
parents: 82558
diff changeset
245 nonlocal hits, misses
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
246 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
247 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
248 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
249 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
250 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
251 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
252 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
253 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
254 return result
75776
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
255
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 else:
75776
66803fd0a6bc Section-off the source for better readability.
Raymond Hettinger <python@rcn.com>
parents: 75775
diff changeset
257
66582
00c8cdf53936 Issue 10593: Adopt Nick's suggestion for an lru_cache with maxsize=None.
Raymond Hettinger <python@rcn.com>
parents: 66578
diff changeset
258 def wrapper(*args, **kwds):
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
259 # Size limited caching that tracks accesses by recency
82560
a9fa8a18d18d Sync-up with 3.4 to make maintenance easier.
Raymond Hettinger <python@rcn.com>
parents: 82558
diff changeset
260 nonlocal root, hits, misses, 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
261 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
262 with lock:
75729
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
263 link = cache_get(key)
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
264 if link is not None:
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
265 # Move the link to the front of the circular queue
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
266 link_prev, link_next, _key, result = link
75729
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
267 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
268 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
269 last = root[PREV]
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
270 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
271 link[PREV] = last
3b2856d8614b Improve the memory utilization (and speed) of functools.lru_cache().
Raymond Hettinger <python@rcn.com>
parents: 73943
diff changeset
272 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
273 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
274 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
275 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
276 with lock:
76675
b3aeaef6c315 Handle a possible race condition
Raymond Hettinger <python@rcn.com>
parents: 76656
diff changeset
277 if key in cache:
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
278 # Getting here means that this same key was added to the
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
279 # cache while the lock was released. Since the link
76675
b3aeaef6c315 Handle a possible race condition
Raymond Hettinger <python@rcn.com>
parents: 76656
diff changeset
280 # update is already done, we need only return the
b3aeaef6c315 Handle a possible race condition
Raymond Hettinger <python@rcn.com>
parents: 76656
diff changeset
281 # computed result and update the count of misses.
b3aeaef6c315 Handle a possible race condition
Raymond Hettinger <python@rcn.com>
parents: 76656
diff changeset
282 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
283 elif full:
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
284 # Use the old root to store the new key and result.
82468
4b06fd08b78c Fix other re-entrancy nits for the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 82450
diff changeset
285 oldroot = root
4b06fd08b78c Fix other re-entrancy nits for the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 82450
diff changeset
286 oldroot[KEY] = key
4b06fd08b78c Fix other re-entrancy nits for the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 82450
diff changeset
287 oldroot[RESULT] = result
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
288 # Empty the oldest link and make it the new root.
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
289 # Keep a reference to the old key and old result to
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
290 # prevent their ref counts from going to zero during the
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
291 # update. That will prevent potentially arbitrary object
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
292 # clean-up code (i.e. __del__) from running while we're
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
293 # still adjusting the links.
82468
4b06fd08b78c Fix other re-entrancy nits for the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 82450
diff changeset
294 root = oldroot[NEXT]
4b06fd08b78c Fix other re-entrancy nits for the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 82450
diff changeset
295 oldkey = root[KEY]
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
296 oldresult = root[RESULT]
76004
1c22c1109824 Fix-up a comment
Raymond Hettinger <python@rcn.com>
parents: 76003
diff changeset
297 root[KEY] = root[RESULT] = None
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
298 # Now update the cache dictionary.
82468
4b06fd08b78c Fix other re-entrancy nits for the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 82450
diff changeset
299 del cache[oldkey]
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
300 # Save the potentially reentrant cache[key] assignment
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
301 # for last, after the root and links have been put in
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
302 # a consistent state.
82468
4b06fd08b78c Fix other re-entrancy nits for the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 82450
diff changeset
303 cache[key] = oldroot
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
304 else:
82558
1af9f7df3a96 Improve comments and variable names.
Raymond Hettinger <python@rcn.com>
parents: 82470
diff changeset
305 # Put result in a new link at the front of the queue.
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
306 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
307 link = [last, root, key, result]
82468
4b06fd08b78c Fix other re-entrancy nits for the lru_cache.
Raymond Hettinger <python@rcn.com>
parents: 82450
diff changeset
308 last[NEXT] = root[PREV] = cache[key] = link
82560
a9fa8a18d18d Sync-up with 3.4 to make maintenance easier.
Raymond Hettinger <python@rcn.com>
parents: 82558
diff changeset
309 full = (len(cache) >= 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
310 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
311 return result
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
312
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
313 def cache_info():
66552
f16bf4cae5d7 Neaten-up a bit.
Raymond Hettinger <python@rcn.com>
parents: 66550
diff changeset
314 """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
315 with lock:
82560
a9fa8a18d18d Sync-up with 3.4 to make maintenance easier.
Raymond Hettinger <python@rcn.com>
parents: 82558
diff changeset
316 return _CacheInfo(hits, misses, maxsize, len(cache))
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
317
64448
61c44793238d Adopt more descriptive attribute names as suggested on python-dev.
Raymond Hettinger <python@rcn.com>
parents: 64382
diff changeset
318 def cache_clear():
63823
1086dad50c74 use same quoting as the rest of the file
Benjamin Peterson <benjamin@python.org>
parents: 63745
diff changeset
319 """Clear the cache and cache statistics"""
82560
a9fa8a18d18d Sync-up with 3.4 to make maintenance easier.
Raymond Hettinger <python@rcn.com>
parents: 82558
diff changeset
320 nonlocal hits, misses, full
64016
d8d0abe61e83 Add locks to make the caches well behaved in multi-threaded code.
Raymond Hettinger <python@rcn.com>
parents: 63823
diff changeset
321 with lock:
d8d0abe61e83 Add locks to make the caches well behaved in multi-threaded code.
Raymond Hettinger <python@rcn.com>
parents: 63823
diff changeset
322 cache.clear()
75752
087da2a353e6 clear the root with the cache
Benjamin Peterson <benjamin@python.org>
parents: 75749
diff changeset
323 root[:] = [root, root, None, None]
82560
a9fa8a18d18d Sync-up with 3.4 to make maintenance easier.
Raymond Hettinger <python@rcn.com>
parents: 82558
diff changeset
324 hits = misses = 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
325 full = False
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
326
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
327 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
328 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
329 return update_wrapper(wrapper, user_function)
66441
03d933948bf3 Clean-up docstring, comments, and whitespace.
Raymond Hettinger <python@rcn.com>
parents: 64776
diff changeset
330
63370
c55876a6fa3c Re-commit r83327 now that the release is done.
Georg Brandl <georg@python.org>
parents: 63357
diff changeset
331 return decorating_function