codekingpro/portable-devtools

1"""functools.py - Tools for working with functions and callable objects2"""3# Python module wrapper for _functools C module4# to allow utilities written in Python to be added5# to the functools module.6# Written by Nick Coghlan <ncoghlan at gmail.com>,7# Raymond Hettinger <python at rcn.com>,8# and Łukasz Langa <lukasz at langa.pl>.9#   Copyright (C) 2006 Python Software Foundation.10# See C source code for _functools credits/copyright11 12__all__ = ['update_wrapper', 'wraps', 'WRAPPER_ASSIGNMENTS', 'WRAPPER_UPDATES',13           'total_ordering', 'cache', 'cmp_to_key', 'lru_cache', 'reduce',14           'partial', 'partialmethod', 'singledispatch', 'singledispatchmethod',15           'cached_property', 'Placeholder']16 17from abc import get_cache_token18from collections import namedtuple19# import weakref  # Deferred to single_dispatch()20from operator import itemgetter21from reprlib import recursive_repr22from types import GenericAlias, MethodType, MappingProxyType, UnionType23from _thread import RLock24 25################################################################################26### update_wrapper() and wraps() decorator27################################################################################28 29# update_wrapper() and wraps() are tools to help write30# wrapper functions that can handle naive introspection31 32WRAPPER_ASSIGNMENTS = ('__module__', '__name__', '__qualname__', '__doc__',33                       '__annotate__', '__type_params__')34WRAPPER_UPDATES = ('__dict__',)35def update_wrapper(wrapper,36                   wrapped,37                   assigned = WRAPPER_ASSIGNMENTS,38                   updated = WRAPPER_UPDATES):39    """Update a wrapper function to look like the wrapped function40 41       wrapper is the function to be updated42       wrapped is the original function43       assigned is a tuple naming the attributes assigned directly44       from the wrapped function to the wrapper function (defaults to45       functools.WRAPPER_ASSIGNMENTS)46       updated is a tuple naming the attributes of the wrapper that47       are updated with the corresponding attribute from the wrapped48       function (defaults to functools.WRAPPER_UPDATES)49    """50    for attr in assigned:51        try:52            value = getattr(wrapped, attr)53        except AttributeError:54            pass55        else:56            setattr(wrapper, attr, value)57    for attr in updated:58        getattr(wrapper, attr).update(getattr(wrapped, attr, {}))59    # Issue #17482: set __wrapped__ last so we don't inadvertently copy it60    # from the wrapped function when updating __dict__61    wrapper.__wrapped__ = wrapped62    # Return the wrapper so this can be used as a decorator via partial()63    return wrapper64 65def wraps(wrapped,66          assigned = WRAPPER_ASSIGNMENTS,67          updated = WRAPPER_UPDATES):68    """Decorator factory to apply update_wrapper() to a wrapper function69 70       Returns a decorator that invokes update_wrapper() with the decorated71       function as the wrapper argument and the arguments to wraps() as the72       remaining arguments. Default arguments are as for update_wrapper().73       This is a convenience function to simplify applying partial() to74       update_wrapper().75    """76    return partial(update_wrapper, wrapped=wrapped,77                   assigned=assigned, updated=updated)78 79 80################################################################################81### total_ordering class decorator82################################################################################83 84# The total ordering functions all invoke the root magic method directly85# rather than using the corresponding operator.  This avoids possible86# infinite recursion that could occur when the operator dispatch logic87# detects a NotImplemented result and then calls a reflected method.88 89def _gt_from_lt(self, other):90    'Return a > b.  Computed by @total_ordering from (not a < b) and (a != b).'91    op_result = type(self).__lt__(self, other)92    if op_result is NotImplemented:93        return op_result94    return not op_result and self != other95 96def _le_from_lt(self, other):97    'Return a <= b.  Computed by @total_ordering from (a < b) or (a == b).'98    op_result = type(self).__lt__(self, other)99    if op_result is NotImplemented:100        return op_result101    return op_result or self == other102 103def _ge_from_lt(self, other):104    'Return a >= b.  Computed by @total_ordering from (not a < b).'105    op_result = type(self).__lt__(self, other)106    if op_result is NotImplemented:107        return op_result108    return not op_result109 110def _ge_from_le(self, other):111    'Return a >= b.  Computed by @total_ordering from (not a <= b) or (a == b).'112    op_result = type(self).__le__(self, other)113    if op_result is NotImplemented:114        return op_result115    return not op_result or self == other116 117def _lt_from_le(self, other):118    'Return a < b.  Computed by @total_ordering from (a <= b) and (a != b).'119    op_result = type(self).__le__(self, other)120    if op_result is NotImplemented:121        return op_result122    return op_result and self != other123 124def _gt_from_le(self, other):125    'Return a > b.  Computed by @total_ordering from (not a <= b).'126    op_result = type(self).__le__(self, other)127    if op_result is NotImplemented:128        return op_result129    return not op_result130 131def _lt_from_gt(self, other):132    'Return a < b.  Computed by @total_ordering from (not a > b) and (a != b).'133    op_result = type(self).__gt__(self, other)134    if op_result is NotImplemented:135        return op_result136    return not op_result and self != other137 138def _ge_from_gt(self, other):139    'Return a >= b.  Computed by @total_ordering from (a > b) or (a == b).'140    op_result = type(self).__gt__(self, other)141    if op_result is NotImplemented:142        return op_result143    return op_result or self == other144 145def _le_from_gt(self, other):146    'Return a <= b.  Computed by @total_ordering from (not a > b).'147    op_result = type(self).__gt__(self, other)148    if op_result is NotImplemented:149        return op_result150    return not op_result151 152def _le_from_ge(self, other):153    'Return a <= b.  Computed by @total_ordering from (not a >= b) or (a == b).'154    op_result = type(self).__ge__(self, other)155    if op_result is NotImplemented:156        return op_result157    return not op_result or self == other158 159def _gt_from_ge(self, other):160    'Return a > b.  Computed by @total_ordering from (a >= b) and (a != b).'161    op_result = type(self).__ge__(self, other)162    if op_result is NotImplemented:163        return op_result164    return op_result and self != other165 166def _lt_from_ge(self, other):167    'Return a < b.  Computed by @total_ordering from (not a >= b).'168    op_result = type(self).__ge__(self, other)169    if op_result is NotImplemented:170        return op_result171    return not op_result172 173_convert = {174    '__lt__': [('__gt__', _gt_from_lt),175               ('__le__', _le_from_lt),176               ('__ge__', _ge_from_lt)],177    '__le__': [('__ge__', _ge_from_le),178               ('__lt__', _lt_from_le),179               ('__gt__', _gt_from_le)],180    '__gt__': [('__lt__', _lt_from_gt),181               ('__ge__', _ge_from_gt),182               ('__le__', _le_from_gt)],183    '__ge__': [('__le__', _le_from_ge),184               ('__gt__', _gt_from_ge),185               ('__lt__', _lt_from_ge)]186}187 188def total_ordering(cls):189    """Class decorator that fills in missing ordering methods"""190    # Find user-defined comparisons (not those inherited from object).191    roots = {op for op in _convert if getattr(cls, op, None) is not getattr(object, op, None)}192    if not roots:193        raise ValueError('must define at least one ordering operation: < > <= >=')194    root = max(roots)       # prefer __lt__ to __le__ to __gt__ to __ge__195    for opname, opfunc in _convert[root]:196        if opname not in roots:197            opfunc.__name__ = opname198            setattr(cls, opname, opfunc)199    return cls200 201 202################################################################################203### cmp_to_key() function converter204################################################################################205 206def cmp_to_key(mycmp):207    """Convert a cmp= function into a key= function"""208    class K(object):209        __slots__ = ['obj']210        def __init__(self, obj):211            self.obj = obj212        def __lt__(self, other):213            return mycmp(self.obj, other.obj) < 0214        def __gt__(self, other):215            return mycmp(self.obj, other.obj) > 0216        def __eq__(self, other):217            return mycmp(self.obj, other.obj) == 0218        def __le__(self, other):219            return mycmp(self.obj, other.obj) <= 0220        def __ge__(self, other):221            return mycmp(self.obj, other.obj) >= 0222        __hash__ = None223    return K224 225try:226    from _functools import cmp_to_key227except ImportError:228    pass229 230 231################################################################################232### reduce() sequence to a single item233################################################################################234 235_initial_missing = object()236 237def reduce(function, sequence, initial=_initial_missing):238    """239    reduce(function, iterable, /[, initial]) -> value240 241    Apply a function of two arguments cumulatively to the items of an iterable, from left to right.242 243    This effectively reduces the iterable to a single value.  If initial is present,244    it is placed before the items of the iterable in the calculation, and serves as245    a default when the iterable is empty.246 247    For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5])248    calculates ((((1 + 2) + 3) + 4) + 5).249    """250 251    it = iter(sequence)252 253    if initial is _initial_missing:254        try:255            value = next(it)256        except StopIteration:257            raise TypeError(258                "reduce() of empty iterable with no initial value") from None259    else:260        value = initial261 262    for element in it:263        value = function(value, element)264 265    return value266 267 268################################################################################269### partial() argument application270################################################################################271 272 273class _PlaceholderType:274    """The type of the Placeholder singleton.275 276    Used as a placeholder for partial arguments.277    """278    __instance = None279    __slots__ = ()280 281    def __init_subclass__(cls, *args, **kwargs):282        raise TypeError(f"type '{cls.__name__}' is not an acceptable base type")283 284    def __new__(cls):285        if cls.__instance is None:286            cls.__instance = object.__new__(cls)287        return cls.__instance288 289    def __repr__(self):290        return 'Placeholder'291 292    def __reduce__(self):293        return 'Placeholder'294 295Placeholder = _PlaceholderType()296 297def _partial_prepare_merger(args):298    if not args:299        return 0, None300    nargs = len(args)301    order = []302    j = nargs303    for i, a in enumerate(args):304        if a is Placeholder:305            order.append(j)306            j += 1307        else:308            order.append(i)309    phcount = j - nargs310    merger = itemgetter(*order) if phcount else None311    return phcount, merger312 313def _partial_new(cls, func, /, *args, **keywords):314    if issubclass(cls, partial):315        base_cls = partial316        if not callable(func):317            raise TypeError("the first argument must be callable")318    else:319        base_cls = partialmethod320        # func could be a descriptor like classmethod which isn't callable321        if not callable(func) and not hasattr(func, "__get__"):322            raise TypeError(f"the first argument {func!r} must be a callable "323                            "or a descriptor")324    if args and args[-1] is Placeholder:325        raise TypeError("trailing Placeholders are not allowed")326    for value in keywords.values():327        if value is Placeholder:328            raise TypeError("Placeholder cannot be passed as a keyword argument")329    if isinstance(func, base_cls):330        pto_phcount = func._phcount331        tot_args = func.args332        if args:333            tot_args += args334            if pto_phcount:335                # merge args with args of `func` which is `partial`336                nargs = len(args)337                if nargs < pto_phcount:338                    tot_args += (Placeholder,) * (pto_phcount - nargs)339                tot_args = func._merger(tot_args)340                if nargs > pto_phcount:341                    tot_args += args[pto_phcount:]342            phcount, merger = _partial_prepare_merger(tot_args)343        else:   # works for both pto_phcount == 0 and != 0344            phcount, merger = pto_phcount, func._merger345        keywords = {**func.keywords, **keywords}346        func = func.func347    else:348        tot_args = args349        phcount, merger = _partial_prepare_merger(tot_args)350 351    self = object.__new__(cls)352    self.func = func353    self.args = tot_args354    self.keywords = keywords355    self._phcount = phcount356    self._merger = merger357    return self358 359def _partial_repr(self):360    cls = type(self)361    module = cls.__module__362    qualname = cls.__qualname__363    args = [repr(self.func)]364    args.extend(map(repr, self.args))365    args.extend(f"{k}={v!r}" for k, v in self.keywords.items())366    return f"{module}.{qualname}({', '.join(args)})"367 368# Purely functional, no descriptor behaviour369class partial:370    """New function with partial application of the given arguments371    and keywords.372    """373 374    __slots__ = ("func", "args", "keywords", "_phcount", "_merger",375                 "__dict__", "__weakref__")376 377    __new__ = _partial_new378    __repr__ = recursive_repr()(_partial_repr)379 380    def __call__(self, /, *args, **keywords):381        phcount = self._phcount382        if phcount:383            try:384                pto_args = self._merger(self.args + args)385                args = args[phcount:]386            except IndexError:387                raise TypeError("missing positional arguments "388                                "in 'partial' call; expected "389                                f"at least {phcount}, got {len(args)}")390        else:391            pto_args = self.args392        keywords = {**self.keywords, **keywords}393        return self.func(*pto_args, *args, **keywords)394 395    def __get__(self, obj, objtype=None):396        if obj is None:397            return self398        return MethodType(self, obj)399 400    def __reduce__(self):401        return type(self), (self.func,), (self.func, self.args,402               self.keywords or None, self.__dict__ or None)403 404    def __setstate__(self, state):405        if not isinstance(state, tuple):406            raise TypeError("argument to __setstate__ must be a tuple")407        if len(state) != 4:408            raise TypeError(f"expected 4 items in state, got {len(state)}")409        func, args, kwds, namespace = state410        if (not callable(func) or not isinstance(args, tuple) or411           (kwds is not None and not isinstance(kwds, dict)) or412           (namespace is not None and not isinstance(namespace, dict))):413            raise TypeError("invalid partial state")414 415        if args and args[-1] is Placeholder:416            raise TypeError("trailing Placeholders are not allowed")417        phcount, merger = _partial_prepare_merger(args)418 419        args = tuple(args) # just in case it's a subclass420        if kwds is None:421            kwds = {}422        elif type(kwds) is not dict: # XXX does it need to be *exactly* dict?423            kwds = dict(kwds)424        if namespace is None:425            namespace = {}426 427        self.__dict__ = namespace428        self.func = func429        self.args = args430        self.keywords = kwds431        self._phcount = phcount432        self._merger = merger433 434    __class_getitem__ = classmethod(GenericAlias)435 436 437try:438    from _functools import partial, Placeholder, _PlaceholderType439except ImportError:440    pass441 442# Descriptor version443class partialmethod:444    """Method descriptor with partial application of the given arguments445    and keywords.446 447    Supports wrapping existing descriptors and handles non-descriptor448    callables as instance methods.449    """450    __new__ = _partial_new451    __repr__ = _partial_repr452 453    def _make_unbound_method(self):454        def _method(cls_or_self, /, *args, **keywords):455            phcount = self._phcount456            if phcount:457                try:458                    pto_args = self._merger(self.args + args)459                    args = args[phcount:]460                except IndexError:461                    raise TypeError("missing positional arguments "462                                    "in 'partialmethod' call; expected "463                                    f"at least {phcount}, got {len(args)}")464            else:465                pto_args = self.args466            keywords = {**self.keywords, **keywords}467            return self.func(cls_or_self, *pto_args, *args, **keywords)468        _method.__isabstractmethod__ = self.__isabstractmethod__469        _method.__partialmethod__ = self470        return _method471 472    def __get__(self, obj, cls=None):473        get = getattr(self.func, "__get__", None)474        result = None475        if get is not None:476            new_func = get(obj, cls)477            if new_func is not self.func:478                # Assume __get__ returning something new indicates the479                # creation of an appropriate callable480                result = partial(new_func, *self.args, **self.keywords)481                try:482                    result.__self__ = new_func.__self__483                except AttributeError:484                    pass485        if result is None:486            # If the underlying descriptor didn't do anything, treat this487            # like an instance method488            result = self._make_unbound_method().__get__(obj, cls)489        return result490 491    @property492    def __isabstractmethod__(self):493        return getattr(self.func, "__isabstractmethod__", False)494 495    __class_getitem__ = classmethod(GenericAlias)496 497 498# Helper functions499 500def _unwrap_partial(func):501    while isinstance(func, partial):502        func = func.func503    return func504 505def _unwrap_partialmethod(func):506    prev = None507    while func is not prev:508        prev = func509        while isinstance(getattr(func, "__partialmethod__", None), partialmethod):510            func = func.__partialmethod__511        while isinstance(func, partialmethod):512            func = getattr(func, 'func')513        func = _unwrap_partial(func)514    return func515 516################################################################################517### LRU Cache function decorator518################################################################################519 520_CacheInfo = namedtuple("CacheInfo", ["hits", "misses", "maxsize", "currsize"])521 522def _make_key(args, kwds, typed,523             kwd_mark = (object(),),524             fasttypes = {int, str},525             tuple=tuple, type=type, len=len):526    """Make a cache key from optionally typed positional and keyword arguments527 528    The key is constructed in a way that is flat as possible rather than529    as a nested structure that would take more memory.530 531    If there is only a single argument and its data type is known to cache532    its hash value, then that argument is returned without a wrapper.  This533    saves space and improves lookup speed.534 535    """536    # All of code below relies on kwds preserving the order input by the user.537    # Formerly, we sorted() the kwds before looping.  The new way is *much*538    # faster; however, it means that f(x=1, y=2) will now be treated as a539    # distinct call from f(y=2, x=1) which will be cached separately.540    key = args541    if kwds:542        key += kwd_mark543        for item in kwds.items():544            key += item545    if typed:546        key += tuple(type(v) for v in args)547        if kwds:548            key += tuple(type(v) for v in kwds.values())549    elif len(key) == 1 and type(key[0]) in fasttypes:550        return key[0]551    return key552 553def lru_cache(maxsize=128, typed=False):554    """Least-recently-used cache decorator.555 556    If *maxsize* is set to None, the LRU features are disabled and the cache557    can grow without bound.558 559    If *typed* is True, arguments of different types will be cached separately.560    For example, f(decimal.Decimal("3.0")) and f(3.0) will be treated as561    distinct calls with distinct results. Some types such as str and int may562    be cached separately even when typed is false.563 564    Arguments to the cached function must be hashable.565 566    View the cache statistics named tuple (hits, misses, maxsize, currsize)567    with f.cache_info().  Clear the cache and statistics with f.cache_clear().568    Access the underlying function with f.__wrapped__.569 570    See:  https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)571 572    """573 574    # Users should only access the lru_cache through its public API:575    #       cache_info, cache_clear, and f.__wrapped__576    # The internals of the lru_cache are encapsulated for thread safety and577    # to allow the implementation to change (including a possible C version).578 579    if isinstance(maxsize, int):580        # Negative maxsize is treated as 0581        if maxsize < 0:582            maxsize = 0583    elif callable(maxsize) and isinstance(typed, bool):584        # The user_function was passed in directly via the maxsize argument585        user_function, maxsize = maxsize, 128586        wrapper = _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo)587        wrapper.cache_parameters = lambda : {'maxsize': maxsize, 'typed': typed}588        return update_wrapper(wrapper, user_function)589    elif maxsize is not None:590        raise TypeError(591            'Expected first argument to be an integer, a callable, or None')592 593    def decorating_function(user_function):594        wrapper = _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo)595        wrapper.cache_parameters = lambda : {'maxsize': maxsize, 'typed': typed}596        return update_wrapper(wrapper, user_function)597 598    return decorating_function599 600def _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo):601    # Constants shared by all lru cache instances:602    sentinel = object()          # unique object used to signal cache misses603    make_key = _make_key         # build a key from the function arguments604    PREV, NEXT, KEY, RESULT = 0, 1, 2, 3   # names for the link fields605 606    cache = {}607    hits = misses = 0608    full = False609    cache_get = cache.get    # bound method to lookup a key or return None610    cache_len = cache.__len__  # get cache size without calling len()611    lock = RLock()           # because linkedlist updates aren't threadsafe612    root = []                # root of the circular doubly linked list613    root[:] = [root, root, None, None]     # initialize by pointing to self614 615    if maxsize == 0:616 617        def wrapper(*args, **kwds):618            # No caching -- just a statistics update619            nonlocal misses620            misses += 1621            result = user_function(*args, **kwds)622            return result623 624    elif maxsize is None:625 626        def wrapper(*args, **kwds):627            # Simple caching without ordering or size limit628            nonlocal hits, misses629            key = make_key(args, kwds, typed)630            result = cache_get(key, sentinel)631            if result is not sentinel:632                hits += 1633                return result634            misses += 1635            result = user_function(*args, **kwds)636            cache[key] = result637            return result638 639    else:640 641        def wrapper(*args, **kwds):642            # Size limited caching that tracks accesses by recency643            nonlocal root, hits, misses, full644            key = make_key(args, kwds, typed)645            with lock:646                link = cache_get(key)647                if link is not None:648                    # Move the link to the front of the circular queue649                    link_prev, link_next, _key, result = link650                    link_prev[NEXT] = link_next651                    link_next[PREV] = link_prev652                    last = root[PREV]653                    last[NEXT] = root[PREV] = link654                    link[PREV] = last655                    link[NEXT] = root656                    hits += 1657                    return result658                misses += 1659            result = user_function(*args, **kwds)660            with lock:661                if key in cache:662                    # Getting here means that this same key was added to the663                    # cache while the lock was released.  Since the link664                    # update is already done, we need only return the665                    # computed result and update the count of misses.666                    pass667                elif full:668                    # Use the old root to store the new key and result.669                    oldroot = root670                    oldroot[KEY] = key671                    oldroot[RESULT] = result672                    # Empty the oldest link and make it the new root.673                    # Keep a reference to the old key and old result to674                    # prevent their ref counts from going to zero during the675                    # update. That will prevent potentially arbitrary object676                    # clean-up code (i.e. __del__) from running while we're677                    # still adjusting the links.678                    root = oldroot[NEXT]679                    oldkey = root[KEY]680                    oldresult = root[RESULT]681                    root[KEY] = root[RESULT] = None682                    # Now update the cache dictionary.683                    del cache[oldkey]684                    # Save the potentially reentrant cache[key] assignment685                    # for last, after the root and links have been put in686                    # a consistent state.687                    cache[key] = oldroot688                else:689                    # Put result in a new link at the front of the queue.690                    last = root[PREV]691                    link = [last, root, key, result]692                    last[NEXT] = root[PREV] = cache[key] = link693                    # Use the cache_len bound method instead of the len() function694                    # which could potentially be wrapped in an lru_cache itself.695                    full = (cache_len() >= maxsize)696            return result697 698    def cache_info():699        """Report cache statistics"""700        with lock:701            return _CacheInfo(hits, misses, maxsize, cache_len())702 703    def cache_clear():704        """Clear the cache and cache statistics"""705        nonlocal hits, misses, full706        with lock:707            cache.clear()708            root[:] = [root, root, None, None]709            hits = misses = 0710            full = False711 712    wrapper.cache_info = cache_info713    wrapper.cache_clear = cache_clear714    return wrapper715 716try:717    from _functools import _lru_cache_wrapper718except ImportError:719    pass720 721 722################################################################################723### cache -- simplified access to the infinity cache724################################################################################725 726def cache(user_function, /):727    'Simple lightweight unbounded cache.  Sometimes called "memoize".'728    return lru_cache(maxsize=None)(user_function)729 730 731################################################################################732### singledispatch() - single-dispatch generic function decorator733################################################################################734 735def _c3_merge(sequences):736    """Merges MROs in *sequences* to a single MRO using the C3 algorithm.737 738    Adapted from https://docs.python.org/3/howto/mro.html.739 740    """741    result = []742    while True:743        sequences = [s for s in sequences if s]   # purge empty sequences744        if not sequences:745            return result746        for s1 in sequences:   # find merge candidates among seq heads747            candidate = s1[0]748            for s2 in sequences:749                if candidate in s2[1:]:750                    candidate = None751                    break      # reject the current head, it appears later752            else:753                break754        if candidate is None:755            raise RuntimeError("Inconsistent hierarchy")756        result.append(candidate)757        # remove the chosen candidate758        for seq in sequences:759            if seq[0] == candidate:760                del seq[0]761 762def _c3_mro(cls, abcs=None):763    """Computes the method resolution order using extended C3 linearization.764 765    If no *abcs* are given, the algorithm works exactly like the built-in C3766    linearization used for method resolution.767 768    If given, *abcs* is a list of abstract base classes that should be inserted769    into the resulting MRO. Unrelated ABCs are ignored and don't end up in the770    result. The algorithm inserts ABCs where their functionality is introduced,771    i.e. issubclass(cls, abc) returns True for the class itself but returns772    False for all its direct base classes. Implicit ABCs for a given class773    (either registered or inferred from the presence of a special method like774    __len__) are inserted directly after the last ABC explicitly listed in the775    MRO of said class. If two implicit ABCs end up next to each other in the776    resulting MRO, their ordering depends on the order of types in *abcs*.777 778    """779    for i, base in enumerate(reversed(cls.__bases__)):780        if hasattr(base, '__abstractmethods__'):781            boundary = len(cls.__bases__) - i782            break   # Bases up to the last explicit ABC are considered first.783    else:784        boundary = 0785    abcs = list(abcs) if abcs else []786    explicit_bases = list(cls.__bases__[:boundary])787    abstract_bases = []788    other_bases = list(cls.__bases__[boundary:])789    for base in abcs:790        if issubclass(cls, base) and not any(791                issubclass(b, base) for b in cls.__bases__792            ):793            # If *cls* is the class that introduces behaviour described by794            # an ABC *base*, insert said ABC to its MRO.795            abstract_bases.append(base)796    for base in abstract_bases:797        abcs.remove(base)798    explicit_c3_mros = [_c3_mro(base, abcs=abcs) for base in explicit_bases]799    abstract_c3_mros = [_c3_mro(base, abcs=abcs) for base in abstract_bases]800    other_c3_mros = [_c3_mro(base, abcs=abcs) for base in other_bases]801    return _c3_merge(802        [[cls]] +803        explicit_c3_mros + abstract_c3_mros + other_c3_mros +804        [explicit_bases] + [abstract_bases] + [other_bases]805    )806 807def _compose_mro(cls, types):808    """Calculates the method resolution order for a given class *cls*.809 810    Includes relevant abstract base classes (with their respective bases) from811    the *types* iterable. Uses a modified C3 linearization algorithm.812 813    """814    bases = set(cls.__mro__)815    # Remove entries which are already present in the __mro__ or unrelated.816    def is_related(typ):817        return (typ not in bases and hasattr(typ, '__mro__')818                                 and not isinstance(typ, GenericAlias)819                                 and issubclass(cls, typ))820    types = [n for n in types if is_related(n)]821    # Remove entries which are strict bases of other entries (they will end up822    # in the MRO anyway.823    def is_strict_base(typ):824        for other in types:825            if typ != other and typ in other.__mro__:826                return True827        return False828    types = [n for n in types if not is_strict_base(n)]829    # Subclasses of the ABCs in *types* which are also implemented by830    # *cls* can be used to stabilize ABC ordering.831    type_set = set(types)832    mro = []833    for typ in types:834        found = []835        for sub in typ.__subclasses__():836            if sub not in bases and issubclass(cls, sub):837                found.append([s for s in sub.__mro__ if s in type_set])838        if not found:839            mro.append(typ)840            continue841        # Favor subclasses with the biggest number of useful bases842        found.sort(key=len, reverse=True)843        for sub in found:844            for subcls in sub:845                if subcls not in mro:846                    mro.append(subcls)847    return _c3_mro(cls, abcs=mro)848 849def _find_impl(cls, registry):850    """Returns the best matching implementation from *registry* for type *cls*.851 852    Where there is no registered implementation for a specific type, its method853    resolution order is used to find a more generic implementation.854 855    Note: if *registry* does not contain an implementation for the base856    *object* type, this function may return None.857 858    """859    mro = _compose_mro(cls, registry.keys())860    match = None861    for t in mro:862        if match is not None:863            # If *match* is an implicit ABC but there is another unrelated,864            # equally matching implicit ABC, refuse the temptation to guess.865            if (t in registry and t not in cls.__mro__866                              and match not in cls.__mro__867                              and not issubclass(match, t)):868                raise RuntimeError("Ambiguous dispatch: {} or {}".format(869                    match, t))870            break871        if t in registry:872            match = t873    return registry.get(match)874 875def singledispatch(func):876    """Single-dispatch generic function decorator.877 878    Transforms a function into a generic function, which can have different879    behaviours depending upon the type of its first argument. The decorated880    function acts as the default implementation, and additional881    implementations can be registered using the register() attribute of the882    generic function.883    """884    # There are many programs that use functools without singledispatch, so we885    # trade-off making singledispatch marginally slower for the benefit of886    # making start-up of such applications slightly faster.887    import weakref888 889    registry = {}890    dispatch_cache = weakref.WeakKeyDictionary()891    cache_token = None892 893    def dispatch(cls):894        """generic_func.dispatch(cls) -> <function implementation>895 896        Runs the dispatch algorithm to return the best available implementation897        for the given *cls* registered on *generic_func*.898 899        """900        nonlocal cache_token901        if cache_token is not None:902            current_token = get_cache_token()903            if cache_token != current_token:904                dispatch_cache.clear()905                cache_token = current_token906        try:907            impl = dispatch_cache[cls]908        except KeyError:909            try:910                impl = registry[cls]911            except KeyError:912                impl = _find_impl(cls, registry)913            dispatch_cache[cls] = impl914        return impl915 916    def _is_valid_dispatch_type(cls):917        if isinstance(cls, type):918            return True919        return (isinstance(cls, UnionType) and920                all(isinstance(arg, type) for arg in cls.__args__))921 922    def register(cls, func=None):923        """generic_func.register(cls, func) -> func924 925        Registers a new implementation for the given *cls* on a *generic_func*.926 927        """928        nonlocal cache_token929        if _is_valid_dispatch_type(cls):930            if func is None:931                return lambda f: register(cls, f)932        else:933            if func is not None:934                raise TypeError(935                    f"Invalid first argument to `register()`. "936                    f"{cls!r} is not a class or union type."937                )938            ann = getattr(cls, '__annotate__', None)939            if ann is None:940                raise TypeError(941                    f"Invalid first argument to `register()`: {cls!r}. "942                    f"Use either `@register(some_class)` or plain `@register` "943                    f"on an annotated function."944                )945            func = cls946 947            # only import typing if annotation parsing is necessary948            from typing import get_type_hints949            from annotationlib import Format, ForwardRef950            argname, cls = next(iter(get_type_hints(func, format=Format.FORWARDREF).items()))951            if not _is_valid_dispatch_type(cls):952                if isinstance(cls, UnionType):953                    raise TypeError(954                        f"Invalid annotation for {argname!r}. "955                        f"{cls!r} not all arguments are classes."956                    )957                elif isinstance(cls, ForwardRef):958                    raise TypeError(959                        f"Invalid annotation for {argname!r}. "960                        f"{cls!r} is an unresolved forward reference."961                    )962                else:963                    raise TypeError(964                        f"Invalid annotation for {argname!r}. "965                        f"{cls!r} is not a class."966                    )967 968        if isinstance(cls, UnionType):969            for arg in cls.__args__:970                registry[arg] = func971        else:972            registry[cls] = func973        if cache_token is None and hasattr(cls, '__abstractmethods__'):974            cache_token = get_cache_token()975        dispatch_cache.clear()976        return func977 978    def wrapper(*args, **kw):979        if not args:980            raise TypeError(f'{funcname} requires at least '981                            '1 positional argument')982        return dispatch(args[0].__class__)(*args, **kw)983 984    funcname = getattr(func, '__name__', 'singledispatch function')985    registry[object] = func986    wrapper.register = register987    wrapper.dispatch = dispatch988    wrapper.registry = MappingProxyType(registry)989    wrapper._clear_cache = dispatch_cache.clear990    update_wrapper(wrapper, func)991    return wrapper992 993 994# Descriptor version995class singledispatchmethod:996    """Single-dispatch generic method descriptor.997 998    Supports wrapping existing descriptors.999    """1000 1001    def __init__(self, func):1002        if not callable(func) and not hasattr(func, "__get__"):1003            raise TypeError(f"{func!r} is not callable or a descriptor")1004 1005        self.dispatcher = singledispatch(func)1006        self.func = func1007 1008    def register(self, cls, method=None):1009        """generic_method.register(cls, func) -> func1010 1011        Registers a new implementation for the given *cls* on a *generic_method*.1012        """1013        return self.dispatcher.register(cls, func=method)1014 1015    def __get__(self, obj, cls=None):1016        return _singledispatchmethod_get(self, obj, cls)1017 1018    @property1019    def __isabstractmethod__(self):1020        return getattr(self.func, '__isabstractmethod__', False)1021 1022    def __repr__(self):1023        try:1024            name = self.func.__qualname__1025        except AttributeError:1026            try:1027                name = self.func.__name__1028            except AttributeError:1029                name = '?'1030        return f'<single dispatch method descriptor {name}>'1031 1032class _singledispatchmethod_get:1033    def __init__(self, unbound, obj, cls):1034        self._unbound = unbound1035        self._dispatch = unbound.dispatcher.dispatch1036        self._obj = obj1037        self._cls = cls1038        # Set instance attributes which cannot be handled in __getattr__()1039        # because they conflict with type descriptors.1040        func = unbound.func1041        try:1042            self.__module__ = func.__module__1043        except AttributeError:1044            pass1045        try:1046            self.__doc__ = func.__doc__1047        except AttributeError:1048            pass1049 1050    def __repr__(self):1051        try:1052            name = self.__qualname__1053        except AttributeError:1054            try:1055                name = self.__name__1056            except AttributeError:1057                name = '?'1058        if self._obj is not None:1059            return f'<bound single dispatch method {name} of {self._obj!r}>'1060        else:1061            return f'<single dispatch method {name}>'1062 1063    def __call__(self, /, *args, **kwargs):1064        if not args:1065            funcname = getattr(self._unbound.func, '__name__',1066                               'singledispatchmethod method')1067            raise TypeError(f'{funcname} requires at least '1068                            '1 positional argument')1069        return self._dispatch(args[0].__class__).__get__(self._obj, self._cls)(*args, **kwargs)1070 1071    def __getattr__(self, name):1072        # Resolve these attributes lazily to speed up creation of1073        # the _singledispatchmethod_get instance.1074        if name not in {'__name__', '__qualname__', '__isabstractmethod__',1075                        '__annotations__', '__type_params__'}:1076            raise AttributeError1077        return getattr(self._unbound.func, name)1078 1079    @property1080    def __wrapped__(self):1081        return self._unbound.func1082 1083    @property1084    def register(self):1085        return self._unbound.register1086 1087 1088################################################################################1089### cached_property() - property result cached as instance attribute1090################################################################################1091 1092_NOT_FOUND = object()1093 1094class cached_property:1095    def __init__(self, func):1096        self.func = func1097        self.attrname = None1098        self.__doc__ = func.__doc__1099        self.__module__ = func.__module__1100 1101    def __set_name__(self, owner, name):1102        if self.attrname is None:1103            self.attrname = name1104        elif name != self.attrname:1105            raise TypeError(1106                "Cannot assign the same cached_property to two different names "1107                f"({self.attrname!r} and {name!r})."1108            )1109 1110    def __get__(self, instance, owner=None):1111        if instance is None:1112            return self1113        if self.attrname is None:1114            raise TypeError(1115                "Cannot use cached_property instance without calling __set_name__ on it.")1116        try:1117            cache = instance.__dict__1118        except AttributeError:  # not all objects have __dict__ (e.g. class defines slots)1119            msg = (1120                f"No '__dict__' attribute on {type(instance).__name__!r} "1121                f"instance to cache {self.attrname!r} property."1122            )1123            raise TypeError(msg) from None1124        val = cache.get(self.attrname, _NOT_FOUND)1125        if val is _NOT_FOUND:1126            val = self.func(instance)1127            try:1128                cache[self.attrname] = val1129            except TypeError:1130                msg = (1131                    f"The '__dict__' attribute on {type(instance).__name__!r} instance "1132                    f"does not support item assignment for caching {self.attrname!r} property."1133                )1134                raise TypeError(msg) from None1135        return val1136 1137    __class_getitem__ = classmethod(GenericAlias)1138 1139def _warn_python_reduce_kwargs(py_reduce):1140    @wraps(py_reduce)1141    def wrapper(*args, **kwargs):1142        if 'function' in kwargs or 'sequence' in kwargs:1143            import os1144            import warnings1145            warnings.warn(1146                'Calling functools.reduce with keyword arguments '1147                '"function" or "sequence" '1148                'is deprecated in Python 3.14 and will be '1149                'forbidden in Python 3.16.',1150                DeprecationWarning,1151                skip_file_prefixes=(os.path.dirname(__file__),))1152        return py_reduce(*args, **kwargs)1153    return wrapper1154 1155reduce = _warn_python_reduce_kwargs(reduce)1156del _warn_python_reduce_kwargs1157 1158# The import of the C accelerated version of reduce() has been moved1159# here due to gh-121676. In Python 3.16, _warn_python_reduce_kwargs()1160# should be removed and the import block should be moved back right1161# after the definition of reduce().1162try:1163    from _functools import reduce1164except ImportError:1165    pass1166