codekingpro/portable-devtools

1"""Extensible memoizing collections and decorators."""2 3__all__ = (4    "Cache",5    "FIFOCache",6    "LFUCache",7    "LRUCache",8    "MRUCache",9    "RRCache",10    "TLRUCache",11    "TTLCache",12    "cached",13    "cachedmethod",14)15 16__version__ = "5.3.3"17 18import collections19import collections.abc20import functools21import heapq22import random23import time24 25from . import keys26 27 28class _DefaultSize:29 30    __slots__ = ()31 32    def __getitem__(self, _):33        return 134 35    def __setitem__(self, _, value):36        assert value == 137 38    def pop(self, _):39        return 140 41 42class Cache(collections.abc.MutableMapping):43    """Mutable mapping to serve as a simple cache or cache base class."""44 45    __marker = object()46 47    __size = _DefaultSize()48 49    def __init__(self, maxsize, getsizeof=None):50        if getsizeof:51            self.getsizeof = getsizeof52        if self.getsizeof is not Cache.getsizeof:53            self.__size = dict()54        self.__data = dict()55        self.__currsize = 056        self.__maxsize = maxsize57 58    def __repr__(self):59        return "%s(%s, maxsize=%r, currsize=%r)" % (60            self.__class__.__name__,61            repr(self.__data),62            self.__maxsize,63            self.__currsize,64        )65 66    def __getitem__(self, key):67        try:68            return self.__data[key]69        except KeyError:70            return self.__missing__(key)71 72    def __setitem__(self, key, value):73        maxsize = self.__maxsize74        size = self.getsizeof(value)75        if size > maxsize:76            raise ValueError("value too large")77        if key not in self.__data or self.__size[key] < size:78            while self.__currsize + size > maxsize:79                self.popitem()80        if key in self.__data:81            diffsize = size - self.__size[key]82        else:83            diffsize = size84        self.__data[key] = value85        self.__size[key] = size86        self.__currsize += diffsize87 88    def __delitem__(self, key):89        size = self.__size.pop(key)90        del self.__data[key]91        self.__currsize -= size92 93    def __contains__(self, key):94        return key in self.__data95 96    def __missing__(self, key):97        raise KeyError(key)98 99    def __iter__(self):100        return iter(self.__data)101 102    def __len__(self):103        return len(self.__data)104 105    def get(self, key, default=None):106        if key in self:107            return self[key]108        else:109            return default110 111    def pop(self, key, default=__marker):112        if key in self:113            value = self[key]114            del self[key]115        elif default is self.__marker:116            raise KeyError(key)117        else:118            value = default119        return value120 121    def setdefault(self, key, default=None):122        if key in self:123            value = self[key]124        else:125            self[key] = value = default126        return value127 128    @property129    def maxsize(self):130        """The maximum size of the cache."""131        return self.__maxsize132 133    @property134    def currsize(self):135        """The current size of the cache."""136        return self.__currsize137 138    @staticmethod139    def getsizeof(value):140        """Return the size of a cache element's value."""141        return 1142 143 144class FIFOCache(Cache):145    """First In First Out (FIFO) cache implementation."""146 147    def __init__(self, maxsize, getsizeof=None):148        Cache.__init__(self, maxsize, getsizeof)149        self.__order = collections.OrderedDict()150 151    def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):152        cache_setitem(self, key, value)153        try:154            self.__order.move_to_end(key)155        except KeyError:156            self.__order[key] = None157 158    def __delitem__(self, key, cache_delitem=Cache.__delitem__):159        cache_delitem(self, key)160        del self.__order[key]161 162    def popitem(self):163        """Remove and return the `(key, value)` pair first inserted."""164        try:165            key = next(iter(self.__order))166        except StopIteration:167            raise KeyError("%s is empty" % type(self).__name__) from None168        else:169            return (key, self.pop(key))170 171 172class LFUCache(Cache):173    """Least Frequently Used (LFU) cache implementation."""174 175    def __init__(self, maxsize, getsizeof=None):176        Cache.__init__(self, maxsize, getsizeof)177        self.__counter = collections.Counter()178 179    def __getitem__(self, key, cache_getitem=Cache.__getitem__):180        value = cache_getitem(self, key)181        if key in self:  # __missing__ may not store item182            self.__counter[key] -= 1183        return value184 185    def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):186        cache_setitem(self, key, value)187        self.__counter[key] -= 1188 189    def __delitem__(self, key, cache_delitem=Cache.__delitem__):190        cache_delitem(self, key)191        del self.__counter[key]192 193    def popitem(self):194        """Remove and return the `(key, value)` pair least frequently used."""195        try:196            ((key, _),) = self.__counter.most_common(1)197        except ValueError:198            raise KeyError("%s is empty" % type(self).__name__) from None199        else:200            return (key, self.pop(key))201 202 203class LRUCache(Cache):204    """Least Recently Used (LRU) cache implementation."""205 206    def __init__(self, maxsize, getsizeof=None):207        Cache.__init__(self, maxsize, getsizeof)208        self.__order = collections.OrderedDict()209 210    def __getitem__(self, key, cache_getitem=Cache.__getitem__):211        value = cache_getitem(self, key)212        if key in self:  # __missing__ may not store item213            self.__update(key)214        return value215 216    def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):217        cache_setitem(self, key, value)218        self.__update(key)219 220    def __delitem__(self, key, cache_delitem=Cache.__delitem__):221        cache_delitem(self, key)222        del self.__order[key]223 224    def popitem(self):225        """Remove and return the `(key, value)` pair least recently used."""226        try:227            key = next(iter(self.__order))228        except StopIteration:229            raise KeyError("%s is empty" % type(self).__name__) from None230        else:231            return (key, self.pop(key))232 233    def __update(self, key):234        try:235            self.__order.move_to_end(key)236        except KeyError:237            self.__order[key] = None238 239 240class MRUCache(Cache):241    """Most Recently Used (MRU) cache implementation."""242 243    def __init__(self, maxsize, getsizeof=None):244        Cache.__init__(self, maxsize, getsizeof)245        self.__order = collections.OrderedDict()246 247    def __getitem__(self, key, cache_getitem=Cache.__getitem__):248        value = cache_getitem(self, key)249        if key in self:  # __missing__ may not store item250            self.__update(key)251        return value252 253    def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):254        cache_setitem(self, key, value)255        self.__update(key)256 257    def __delitem__(self, key, cache_delitem=Cache.__delitem__):258        cache_delitem(self, key)259        del self.__order[key]260 261    def popitem(self):262        """Remove and return the `(key, value)` pair most recently used."""263        try:264            key = next(iter(self.__order))265        except StopIteration:266            raise KeyError("%s is empty" % type(self).__name__) from None267        else:268            return (key, self.pop(key))269 270    def __update(self, key):271        try:272            self.__order.move_to_end(key, last=False)273        except KeyError:274            self.__order[key] = None275 276 277class RRCache(Cache):278    """Random Replacement (RR) cache implementation."""279 280    def __init__(self, maxsize, choice=random.choice, getsizeof=None):281        Cache.__init__(self, maxsize, getsizeof)282        self.__choice = choice283 284    @property285    def choice(self):286        """The `choice` function used by the cache."""287        return self.__choice288 289    def popitem(self):290        """Remove and return a random `(key, value)` pair."""291        try:292            key = self.__choice(list(self))293        except IndexError:294            raise KeyError("%s is empty" % type(self).__name__) from None295        else:296            return (key, self.pop(key))297 298 299class _TimedCache(Cache):300    """Base class for time aware cache implementations."""301 302    class _Timer:303        def __init__(self, timer):304            self.__timer = timer305            self.__nesting = 0306 307        def __call__(self):308            if self.__nesting == 0:309                return self.__timer()310            else:311                return self.__time312 313        def __enter__(self):314            if self.__nesting == 0:315                self.__time = time = self.__timer()316            else:317                time = self.__time318            self.__nesting += 1319            return time320 321        def __exit__(self, *exc):322            self.__nesting -= 1323 324        def __reduce__(self):325            return _TimedCache._Timer, (self.__timer,)326 327        def __getattr__(self, name):328            return getattr(self.__timer, name)329 330    def __init__(self, maxsize, timer=time.monotonic, getsizeof=None):331        Cache.__init__(self, maxsize, getsizeof)332        self.__timer = _TimedCache._Timer(timer)333 334    def __repr__(self, cache_repr=Cache.__repr__):335        with self.__timer as time:336            self.expire(time)337            return cache_repr(self)338 339    def __len__(self, cache_len=Cache.__len__):340        with self.__timer as time:341            self.expire(time)342            return cache_len(self)343 344    @property345    def currsize(self):346        with self.__timer as time:347            self.expire(time)348            return super().currsize349 350    @property351    def timer(self):352        """The timer function used by the cache."""353        return self.__timer354 355    def clear(self):356        with self.__timer as time:357            self.expire(time)358            Cache.clear(self)359 360    def get(self, *args, **kwargs):361        with self.__timer:362            return Cache.get(self, *args, **kwargs)363 364    def pop(self, *args, **kwargs):365        with self.__timer:366            return Cache.pop(self, *args, **kwargs)367 368    def setdefault(self, *args, **kwargs):369        with self.__timer:370            return Cache.setdefault(self, *args, **kwargs)371 372 373class TTLCache(_TimedCache):374    """LRU Cache implementation with per-item time-to-live (TTL) value."""375 376    class _Link:377 378        __slots__ = ("key", "expires", "next", "prev")379 380        def __init__(self, key=None, expires=None):381            self.key = key382            self.expires = expires383 384        def __reduce__(self):385            return TTLCache._Link, (self.key, self.expires)386 387        def unlink(self):388            next = self.next389            prev = self.prev390            prev.next = next391            next.prev = prev392 393    def __init__(self, maxsize, ttl, timer=time.monotonic, getsizeof=None):394        _TimedCache.__init__(self, maxsize, timer, getsizeof)395        self.__root = root = TTLCache._Link()396        root.prev = root.next = root397        self.__links = collections.OrderedDict()398        self.__ttl = ttl399 400    def __contains__(self, key):401        try:402            link = self.__links[key]  # no reordering403        except KeyError:404            return False405        else:406            return self.timer() < link.expires407 408    def __getitem__(self, key, cache_getitem=Cache.__getitem__):409        try:410            link = self.__getlink(key)411        except KeyError:412            expired = False413        else:414            expired = not (self.timer() < link.expires)415        if expired:416            return self.__missing__(key)417        else:418            return cache_getitem(self, key)419 420    def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):421        with self.timer as time:422            self.expire(time)423            cache_setitem(self, key, value)424        try:425            link = self.__getlink(key)426        except KeyError:427            self.__links[key] = link = TTLCache._Link(key)428        else:429            link.unlink()430        link.expires = time + self.__ttl431        link.next = root = self.__root432        link.prev = prev = root.prev433        prev.next = root.prev = link434 435    def __delitem__(self, key, cache_delitem=Cache.__delitem__):436        cache_delitem(self, key)437        link = self.__links.pop(key)438        link.unlink()439        if not (self.timer() < link.expires):440            raise KeyError(key)441 442    def __iter__(self):443        root = self.__root444        curr = root.next445        while curr is not root:446            # "freeze" time for iterator access447            with self.timer as time:448                if time < curr.expires:449                    yield curr.key450            curr = curr.next451 452    def __setstate__(self, state):453        self.__dict__.update(state)454        root = self.__root455        root.prev = root.next = root456        for link in sorted(self.__links.values(), key=lambda obj: obj.expires):457            link.next = root458            link.prev = prev = root.prev459            prev.next = root.prev = link460        self.expire(self.timer())461 462    @property463    def ttl(self):464        """The time-to-live value of the cache's items."""465        return self.__ttl466 467    def expire(self, time=None):468        """Remove expired items from the cache."""469        if time is None:470            time = self.timer()471        root = self.__root472        curr = root.next473        links = self.__links474        cache_delitem = Cache.__delitem__475        while curr is not root and not (time < curr.expires):476            cache_delitem(self, curr.key)477            del links[curr.key]478            next = curr.next479            curr.unlink()480            curr = next481 482    def popitem(self):483        """Remove and return the `(key, value)` pair least recently used that484        has not already expired.485 486        """487        with self.timer as time:488            self.expire(time)489            try:490                key = next(iter(self.__links))491            except StopIteration:492                raise KeyError("%s is empty" % type(self).__name__) from None493            else:494                return (key, self.pop(key))495 496    def __getlink(self, key):497        value = self.__links[key]498        self.__links.move_to_end(key)499        return value500 501 502class TLRUCache(_TimedCache):503    """Time aware Least Recently Used (TLRU) cache implementation."""504 505    @functools.total_ordering506    class _Item:507 508        __slots__ = ("key", "expires", "removed")509 510        def __init__(self, key=None, expires=None):511            self.key = key512            self.expires = expires513            self.removed = False514 515        def __lt__(self, other):516            return self.expires < other.expires517 518    def __init__(self, maxsize, ttu, timer=time.monotonic, getsizeof=None):519        _TimedCache.__init__(self, maxsize, timer, getsizeof)520        self.__items = collections.OrderedDict()521        self.__order = []522        self.__ttu = ttu523 524    def __contains__(self, key):525        try:526            item = self.__items[key]  # no reordering527        except KeyError:528            return False529        else:530            return self.timer() < item.expires531 532    def __getitem__(self, key, cache_getitem=Cache.__getitem__):533        try:534            item = self.__getitem(key)535        except KeyError:536            expired = False537        else:538            expired = not (self.timer() < item.expires)539        if expired:540            return self.__missing__(key)541        else:542            return cache_getitem(self, key)543 544    def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):545        with self.timer as time:546            expires = self.__ttu(key, value, time)547            if not (time < expires):548                return  # skip expired items549            self.expire(time)550            cache_setitem(self, key, value)551        # removing an existing item would break the heap structure, so552        # only mark it as removed for now553        try:554            self.__getitem(key).removed = True555        except KeyError:556            pass557        self.__items[key] = item = TLRUCache._Item(key, expires)558        heapq.heappush(self.__order, item)559 560    def __delitem__(self, key, cache_delitem=Cache.__delitem__):561        with self.timer as time:562            # no self.expire() for performance reasons, e.g. self.clear() [#67]563            cache_delitem(self, key)564        item = self.__items.pop(key)565        item.removed = True566        if not (time < item.expires):567            raise KeyError(key)568 569    def __iter__(self):570        for curr in self.__order:571            # "freeze" time for iterator access572            with self.timer as time:573                if time < curr.expires and not curr.removed:574                    yield curr.key575 576    @property577    def ttu(self):578        """The local time-to-use function used by the cache."""579        return self.__ttu580 581    def expire(self, time=None):582        """Remove expired items from the cache."""583        if time is None:584            time = self.timer()585        items = self.__items586        order = self.__order587        # clean up the heap if too many items are marked as removed588        if len(order) > len(items) * 2:589            self.__order = order = [item for item in order if not item.removed]590            heapq.heapify(order)591        cache_delitem = Cache.__delitem__592        while order and (order[0].removed or not (time < order[0].expires)):593            item = heapq.heappop(order)594            if not item.removed:595                cache_delitem(self, item.key)596                del items[item.key]597 598    def popitem(self):599        """Remove and return the `(key, value)` pair least recently used that600        has not already expired.601 602        """603        with self.timer as time:604            self.expire(time)605            try:606                key = next(iter(self.__items))607            except StopIteration:608                raise KeyError("%s is empty" % self.__class__.__name__) from None609            else:610                return (key, self.pop(key))611 612    def __getitem(self, key):613        value = self.__items[key]614        self.__items.move_to_end(key)615        return value616 617 618_CacheInfo = collections.namedtuple(619    "CacheInfo", ["hits", "misses", "maxsize", "currsize"]620)621 622 623def cached(cache, key=keys.hashkey, lock=None, info=False):624    """Decorator to wrap a function with a memoizing callable that saves625    results in a cache.626 627    """628 629    def decorator(func):630        if info:631            hits = misses = 0632 633            if isinstance(cache, Cache):634 635                def getinfo():636                    nonlocal hits, misses637                    return _CacheInfo(hits, misses, cache.maxsize, cache.currsize)638 639            elif isinstance(cache, collections.abc.Mapping):640 641                def getinfo():642                    nonlocal hits, misses643                    return _CacheInfo(hits, misses, None, len(cache))644 645            else:646 647                def getinfo():648                    nonlocal hits, misses649                    return _CacheInfo(hits, misses, 0, 0)650 651            if cache is None:652 653                def wrapper(*args, **kwargs):654                    nonlocal misses655                    misses += 1656                    return func(*args, **kwargs)657 658                def cache_clear():659                    nonlocal hits, misses660                    hits = misses = 0661 662                cache_info = getinfo663 664            elif lock is None:665 666                def wrapper(*args, **kwargs):667                    nonlocal hits, misses668                    k = key(*args, **kwargs)669                    try:670                        result = cache[k]671                        hits += 1672                        return result673                    except KeyError:674                        misses += 1675                    v = func(*args, **kwargs)676                    try:677                        cache[k] = v678                    except ValueError:679                        pass  # value too large680                    return v681 682                def cache_clear():683                    nonlocal hits, misses684                    cache.clear()685                    hits = misses = 0686 687                cache_info = getinfo688 689            else:690 691                def wrapper(*args, **kwargs):692                    nonlocal hits, misses693                    k = key(*args, **kwargs)694                    try:695                        with lock:696                            result = cache[k]697                            hits += 1698                            return result699                    except KeyError:700                        with lock:701                            misses += 1702                    v = func(*args, **kwargs)703                    # in case of a race, prefer the item already in the cache704                    try:705                        with lock:706                            return cache.setdefault(k, v)707                    except ValueError:708                        return v  # value too large709 710                def cache_clear():711                    nonlocal hits, misses712                    with lock:713                        cache.clear()714                        hits = misses = 0715 716                def cache_info():717                    with lock:718                        return getinfo()719 720        else:721            if cache is None:722 723                def wrapper(*args, **kwargs):724                    return func(*args, **kwargs)725 726                def cache_clear():727                    pass728 729            elif lock is None:730 731                def wrapper(*args, **kwargs):732                    k = key(*args, **kwargs)733                    try:734                        return cache[k]735                    except KeyError:736                        pass  # key not found737                    v = func(*args, **kwargs)738                    try:739                        cache[k] = v740                    except ValueError:741                        pass  # value too large742                    return v743 744                def cache_clear():745                    cache.clear()746 747            else:748 749                def wrapper(*args, **kwargs):750                    k = key(*args, **kwargs)751                    try:752                        with lock:753                            return cache[k]754                    except KeyError:755                        pass  # key not found756                    v = func(*args, **kwargs)757                    # in case of a race, prefer the item already in the cache758                    try:759                        with lock:760                            return cache.setdefault(k, v)761                    except ValueError:762                        return v  # value too large763 764                def cache_clear():765                    with lock:766                        cache.clear()767 768            cache_info = None769 770        wrapper.cache = cache771        wrapper.cache_key = key772        wrapper.cache_lock = lock773        wrapper.cache_clear = cache_clear774        wrapper.cache_info = cache_info775 776        return functools.update_wrapper(wrapper, func)777 778    return decorator779 780 781def cachedmethod(cache, key=keys.methodkey, lock=None):782    """Decorator to wrap a class or instance method with a memoizing783    callable that saves results in a cache.784 785    """786 787    def decorator(method):788        if lock is None:789 790            def wrapper(self, *args, **kwargs):791                c = cache(self)792                if c is None:793                    return method(self, *args, **kwargs)794                k = key(self, *args, **kwargs)795                try:796                    return c[k]797                except KeyError:798                    pass  # key not found799                v = method(self, *args, **kwargs)800                try:801                    c[k] = v802                except ValueError:803                    pass  # value too large804                return v805 806            def clear(self):807                c = cache(self)808                if c is not None:809                    c.clear()810 811        else:812 813            def wrapper(self, *args, **kwargs):814                c = cache(self)815                if c is None:816                    return method(self, *args, **kwargs)817                k = key(self, *args, **kwargs)818                try:819                    with lock(self):820                        return c[k]821                except KeyError:822                    pass  # key not found823                v = method(self, *args, **kwargs)824                # in case of a race, prefer the item already in the cache825                try:826                    with lock(self):827                        return c.setdefault(k, v)828                except ValueError:829                    return v  # value too large830 831            def clear(self):832                c = cache(self)833                if c is not None:834                    with lock(self):835                        c.clear()836 837        wrapper.cache = cache838        wrapper.cache_key = key839        wrapper.cache_lock = lock840        wrapper.cache_clear = clear841 842        return functools.update_wrapper(wrapper, method)843 844    return decorator845