diff options
Diffstat (limited to 'Lib/functools.py')
| -rw-r--r-- | Lib/functools.py | 421 |
1 files changed, 402 insertions, 19 deletions
diff --git a/Lib/functools.py b/Lib/functools.py index 053e44e3e8..1e79b31140 100644 --- a/Lib/functools.py +++ b/Lib/functools.py @@ -3,16 +3,24 @@ # Python module wrapper for _functools C module # to allow utilities written in Python to be added # to the functools module. -# Written by Nick Coghlan <ncoghlan at gmail.com> -# and Raymond Hettinger <python at rcn.com> -# Copyright (C) 2006-2010 Python Software Foundation. +# Written by Nick Coghlan <ncoghlan at gmail.com>, +# Raymond Hettinger <python at rcn.com>, +# and Łukasz Langa <lukasz at langa.pl>. +# Copyright (C) 2006-2013 Python Software Foundation. # See C source code for _functools credits/copyright __all__ = ['update_wrapper', 'wraps', 'WRAPPER_ASSIGNMENTS', 'WRAPPER_UPDATES', - 'total_ordering', 'cmp_to_key', 'lru_cache', 'reduce', 'partial'] + 'total_ordering', 'cmp_to_key', 'lru_cache', 'reduce', 'partial', + 'partialmethod', 'singledispatch'] -from _functools import partial, reduce +try: + from _functools import reduce +except ImportError: + pass +from abc import get_cache_token from collections import namedtuple +from types import MappingProxyType, MethodType +from weakref import WeakKeyDictionary try: from _thread import RLock except: @@ -47,7 +55,6 @@ def update_wrapper(wrapper, are updated with the corresponding attribute from the wrapped function (defaults to functools.WRAPPER_UPDATES) """ - wrapper.__wrapped__ = wrapped for attr in assigned: try: value = getattr(wrapped, attr) @@ -57,6 +64,9 @@ def update_wrapper(wrapper, setattr(wrapper, attr, value) for attr in updated: getattr(wrapper, attr).update(getattr(wrapped, attr, {})) + # Issue #17482: set __wrapped__ last so we don't inadvertently copy it + # from the wrapped function when updating __dict__ + wrapper.__wrapped__ = wrapped # Return the wrapper so this can be used as a decorator via partial() return wrapper @@ -79,21 +89,91 @@ def wraps(wrapped, ### total_ordering class decorator ################################################################################ +# The correct way to indicate that a comparison operation doesn't +# recognise the other type is to return NotImplemented and let the +# interpreter handle raising TypeError if both operands return +# NotImplemented from their respective comparison methods +# +# This makes the implementation of total_ordering more complicated, since +# we need to be careful not to trigger infinite recursion when two +# different types that both use this decorator encounter each other. +# +# For example, if a type implements __lt__, it's natural to define +# __gt__ as something like: +# +# lambda self, other: not self < other and not self == other +# +# However, using the operator syntax like that ends up invoking the full +# type checking machinery again and means we can end up bouncing back and +# forth between the two operands until we run out of stack space. +# +# The solution is to define helper functions that invoke the appropriate +# magic methods directly, ensuring we only try each operand once, and +# return NotImplemented immediately if it is returned from the +# underlying user provided method. Using this scheme, the __gt__ derived +# from a user provided __lt__ becomes: +# +# lambda self, other: _not_op_and_not_eq(self.__lt__, self, other)) + +def _not_op(op, other): + # "not a < b" handles "a >= b" + # "not a <= b" handles "a > b" + # "not a >= b" handles "a < b" + # "not a > b" handles "a <= b" + op_result = op(other) + if op_result is NotImplemented: + return NotImplemented + return not op_result + +def _op_or_eq(op, self, other): + # "a < b or a == b" handles "a <= b" + # "a > b or a == b" handles "a >= b" + op_result = op(other) + if op_result is NotImplemented: + return NotImplemented + return op_result or self == other + +def _not_op_and_not_eq(op, self, other): + # "not (a < b or a == b)" handles "a > b" + # "not a < b and a != b" is equivalent + # "not (a > b or a == b)" handles "a < b" + # "not a > b and a != b" is equivalent + op_result = op(other) + if op_result is NotImplemented: + return NotImplemented + return not op_result and self != other + +def _not_op_or_eq(op, self, other): + # "not a <= b or a == b" handles "a >= b" + # "not a >= b or a == b" handles "a <= b" + op_result = op(other) + if op_result is NotImplemented: + return NotImplemented + return not op_result or self == other + +def _op_and_not_eq(op, self, other): + # "a <= b and not a == b" handles "a < b" + # "a >= b and not a == b" handles "a > b" + op_result = op(other) + if op_result is NotImplemented: + return NotImplemented + return op_result and self != other + def total_ordering(cls): """Class decorator that fills in missing ordering methods""" convert = { - '__lt__': [('__gt__', lambda self, other: not (self < other or self == other)), - ('__le__', lambda self, other: self < other or self == other), - ('__ge__', lambda self, other: not self < other)], - '__le__': [('__ge__', lambda self, other: not self <= other or self == other), - ('__lt__', lambda self, other: self <= other and not self == other), - ('__gt__', lambda self, other: not self <= other)], - '__gt__': [('__lt__', lambda self, other: not (self > other or self == other)), - ('__ge__', lambda self, other: self > other or self == other), - ('__le__', lambda self, other: not self > other)], - '__ge__': [('__le__', lambda self, other: (not self >= other) or self == other), - ('__gt__', lambda self, other: self >= other and not self == other), - ('__lt__', lambda self, other: not self >= other)] + '__lt__': [('__gt__', lambda self, other: _not_op_and_not_eq(self.__lt__, self, other)), + ('__le__', lambda self, other: _op_or_eq(self.__lt__, self, other)), + ('__ge__', lambda self, other: _not_op(self.__lt__, other))], + '__le__': [('__ge__', lambda self, other: _not_op_or_eq(self.__le__, self, other)), + ('__lt__', lambda self, other: _op_and_not_eq(self.__le__, self, other)), + ('__gt__', lambda self, other: _not_op(self.__le__, other))], + '__gt__': [('__lt__', lambda self, other: _not_op_and_not_eq(self.__gt__, self, other)), + ('__ge__', lambda self, other: _op_or_eq(self.__gt__, self, other)), + ('__le__', lambda self, other: _not_op(self.__gt__, other))], + '__ge__': [('__le__', lambda self, other: _not_op_or_eq(self.__ge__, self, other)), + ('__gt__', lambda self, other: _op_and_not_eq(self.__ge__, self, other)), + ('__lt__', lambda self, other: _not_op(self.__ge__, other))] } # Find user-defined comparisons (not those inherited from object). roots = [op for op in convert if getattr(cls, op, None) is not getattr(object, op, None)] @@ -140,6 +220,103 @@ except ImportError: ################################################################################ +### partial() argument application +################################################################################ + +# Purely functional, no descriptor behaviour +def partial(func, *args, **keywords): + """New function with partial application of the given arguments + and keywords. + """ + def newfunc(*fargs, **fkeywords): + newkeywords = keywords.copy() + newkeywords.update(fkeywords) + return func(*(args + fargs), **newkeywords) + newfunc.func = func + newfunc.args = args + newfunc.keywords = keywords + return newfunc + +try: + from _functools import partial +except ImportError: + pass + +# Descriptor version +class partialmethod(object): + """Method descriptor with partial application of the given arguments + and keywords. + + Supports wrapping existing descriptors and handles non-descriptor + callables as instance methods. + """ + + def __init__(self, func, *args, **keywords): + if not callable(func) and not hasattr(func, "__get__"): + raise TypeError("{!r} is not callable or a descriptor" + .format(func)) + + # func could be a descriptor like classmethod which isn't callable, + # so we can't inherit from partial (it verifies func is callable) + if isinstance(func, partialmethod): + # flattening is mandatory in order to place cls/self before all + # other arguments + # it's also more efficient since only one function will be called + self.func = func.func + self.args = func.args + args + self.keywords = func.keywords.copy() + self.keywords.update(keywords) + else: + self.func = func + self.args = args + self.keywords = keywords + + def __repr__(self): + args = ", ".join(map(repr, self.args)) + keywords = ", ".join("{}={!r}".format(k, v) + for k, v in self.keywords.items()) + format_string = "{module}.{cls}({func}, {args}, {keywords})" + return format_string.format(module=self.__class__.__module__, + cls=self.__class__.__name__, + func=self.func, + args=args, + keywords=keywords) + + def _make_unbound_method(self): + def _method(*args, **keywords): + call_keywords = self.keywords.copy() + call_keywords.update(keywords) + cls_or_self, *rest = args + call_args = (cls_or_self,) + self.args + tuple(rest) + return self.func(*call_args, **call_keywords) + _method.__isabstractmethod__ = self.__isabstractmethod__ + return _method + + def __get__(self, obj, cls): + get = getattr(self.func, "__get__", None) + result = None + if get is not None: + new_func = get(obj, cls) + if new_func is not self.func: + # Assume __get__ returning something new indicates the + # creation of an appropriate callable + result = partial(new_func, *self.args, **self.keywords) + try: + result.__self__ = new_func.__self__ + except AttributeError: + pass + if result is None: + # If the underlying descriptor didn't do anything, treat this + # like an instance method + result = self._make_unbound_method().__get__(obj, cls) + return result + + @property + def __isabstractmethod__(self): + return getattr(self.func, "__isabstractmethod__", False) + + +################################################################################ ### LRU Cache function decorator ################################################################################ @@ -220,7 +397,6 @@ def lru_cache(maxsize=128, typed=False): PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # names for the link fields def decorating_function(user_function): - cache = {} hits = misses = 0 full = False @@ -329,3 +505,210 @@ def lru_cache(maxsize=128, typed=False): return update_wrapper(wrapper, user_function) return decorating_function + + +################################################################################ +### singledispatch() - single-dispatch generic function decorator +################################################################################ + +def _c3_merge(sequences): + """Merges MROs in *sequences* to a single MRO using the C3 algorithm. + + Adapted from http://www.python.org/download/releases/2.3/mro/. + + """ + result = [] + while True: + sequences = [s for s in sequences if s] # purge empty sequences + if not sequences: + return result + for s1 in sequences: # find merge candidates among seq heads + candidate = s1[0] + for s2 in sequences: + if candidate in s2[1:]: + candidate = None + break # reject the current head, it appears later + else: + break + if not candidate: + raise RuntimeError("Inconsistent hierarchy") + result.append(candidate) + # remove the chosen candidate + for seq in sequences: + if seq[0] == candidate: + del seq[0] + +def _c3_mro(cls, abcs=None): + """Computes the method resolution order using extended C3 linearization. + + If no *abcs* are given, the algorithm works exactly like the built-in C3 + linearization used for method resolution. + + If given, *abcs* is a list of abstract base classes that should be inserted + into the resulting MRO. Unrelated ABCs are ignored and don't end up in the + result. The algorithm inserts ABCs where their functionality is introduced, + i.e. issubclass(cls, abc) returns True for the class itself but returns + False for all its direct base classes. Implicit ABCs for a given class + (either registered or inferred from the presence of a special method like + __len__) are inserted directly after the last ABC explicitly listed in the + MRO of said class. If two implicit ABCs end up next to each other in the + resulting MRO, their ordering depends on the order of types in *abcs*. + + """ + for i, base in enumerate(reversed(cls.__bases__)): + if hasattr(base, '__abstractmethods__'): + boundary = len(cls.__bases__) - i + break # Bases up to the last explicit ABC are considered first. + else: + boundary = 0 + abcs = list(abcs) if abcs else [] + explicit_bases = list(cls.__bases__[:boundary]) + abstract_bases = [] + other_bases = list(cls.__bases__[boundary:]) + for base in abcs: + if issubclass(cls, base) and not any( + issubclass(b, base) for b in cls.__bases__ + ): + # If *cls* is the class that introduces behaviour described by + # an ABC *base*, insert said ABC to its MRO. + abstract_bases.append(base) + for base in abstract_bases: + abcs.remove(base) + explicit_c3_mros = [_c3_mro(base, abcs=abcs) for base in explicit_bases] + abstract_c3_mros = [_c3_mro(base, abcs=abcs) for base in abstract_bases] + other_c3_mros = [_c3_mro(base, abcs=abcs) for base in other_bases] + return _c3_merge( + [[cls]] + + explicit_c3_mros + abstract_c3_mros + other_c3_mros + + [explicit_bases] + [abstract_bases] + [other_bases] + ) + +def _compose_mro(cls, types): + """Calculates the method resolution order for a given class *cls*. + + Includes relevant abstract base classes (with their respective bases) from + the *types* iterable. Uses a modified C3 linearization algorithm. + + """ + bases = set(cls.__mro__) + # Remove entries which are already present in the __mro__ or unrelated. + def is_related(typ): + return (typ not in bases and hasattr(typ, '__mro__') + and issubclass(cls, typ)) + types = [n for n in types if is_related(n)] + # Remove entries which are strict bases of other entries (they will end up + # in the MRO anyway. + def is_strict_base(typ): + for other in types: + if typ != other and typ in other.__mro__: + return True + return False + types = [n for n in types if not is_strict_base(n)] + # Subclasses of the ABCs in *types* which are also implemented by + # *cls* can be used to stabilize ABC ordering. + type_set = set(types) + mro = [] + for typ in types: + found = [] + for sub in typ.__subclasses__(): + if sub not in bases and issubclass(cls, sub): + found.append([s for s in sub.__mro__ if s in type_set]) + if not found: + mro.append(typ) + continue + # Favor subclasses with the biggest number of useful bases + found.sort(key=len, reverse=True) + for sub in found: + for subcls in sub: + if subcls not in mro: + mro.append(subcls) + return _c3_mro(cls, abcs=mro) + +def _find_impl(cls, registry): + """Returns the best matching implementation from *registry* for type *cls*. + + Where there is no registered implementation for a specific type, its method + resolution order is used to find a more generic implementation. + + Note: if *registry* does not contain an implementation for the base + *object* type, this function may return None. + + """ + mro = _compose_mro(cls, registry.keys()) + match = None + for t in mro: + if match is not None: + # If *match* is an implicit ABC but there is another unrelated, + # equally matching implicit ABC, refuse the temptation to guess. + if (t in registry and t not in cls.__mro__ + and match not in cls.__mro__ + and not issubclass(match, t)): + raise RuntimeError("Ambiguous dispatch: {} or {}".format( + match, t)) + break + if t in registry: + match = t + return registry.get(match) + +def singledispatch(func): + """Single-dispatch generic function decorator. + + Transforms a function into a generic function, which can have different + behaviours depending upon the type of its first argument. The decorated + function acts as the default implementation, and additional + implementations can be registered using the register() attribute of the + generic function. + + """ + registry = {} + dispatch_cache = WeakKeyDictionary() + cache_token = None + + def dispatch(cls): + """generic_func.dispatch(cls) -> <function implementation> + + Runs the dispatch algorithm to return the best available implementation + for the given *cls* registered on *generic_func*. + + """ + nonlocal cache_token + if cache_token is not None: + current_token = get_cache_token() + if cache_token != current_token: + dispatch_cache.clear() + cache_token = current_token + try: + impl = dispatch_cache[cls] + except KeyError: + try: + impl = registry[cls] + except KeyError: + impl = _find_impl(cls, registry) + dispatch_cache[cls] = impl + return impl + + def register(cls, func=None): + """generic_func.register(cls, func) -> func + + Registers a new implementation for the given *cls* on a *generic_func*. + + """ + nonlocal cache_token + if func is None: + return lambda f: register(cls, f) + registry[cls] = func + if cache_token is None and hasattr(cls, '__abstractmethods__'): + cache_token = get_cache_token() + dispatch_cache.clear() + return func + + def wrapper(*args, **kw): + return dispatch(args[0].__class__)(*args, **kw) + + registry[object] = func + wrapper.register = register + wrapper.dispatch = dispatch + wrapper.registry = MappingProxyType(registry) + wrapper._clear_cache = dispatch_cache.clear + update_wrapper(wrapper, func) + return wrapper |