codekingpro/portable-devtools

1# Copyright 2009-2024 Joshua Bronson. All rights reserved.2#3# This Source Code Form is subject to the terms of the Mozilla Public4# License, v. 2.0. If a copy of the MPL was not distributed with this5# file, You can obtain one at http://mozilla.org/MPL/2.0/.6 7 8#                             * Code review nav *9#                        (see comments in __init__.py)10# ============================================================================11# ← Prev: _abc.py              Current: _base.py            Next: _frozen.py →12# ============================================================================13 14 15"""Provide :class:`BidictBase`."""16 17from __future__ import annotations18 19import typing as t20import weakref21from itertools import starmap22from operator import eq23from types import MappingProxyType24 25from ._abc import BidirectionalMapping26from ._dup import DROP_NEW27from ._dup import DROP_OLD28from ._dup import ON_DUP_DEFAULT29from ._dup import RAISE30from ._dup import OnDup31from ._exc import DuplicationError32from ._exc import KeyAndValueDuplicationError33from ._exc import KeyDuplicationError34from ._exc import ValueDuplicationError35from ._iter import inverted36from ._iter import iteritems37from ._typing import KT38from ._typing import MISSING39from ._typing import OKT40from ._typing import OVT41from ._typing import VT42from ._typing import Maplike43from ._typing import MapOrItems44 45 46OldKV = t.Tuple[OKT[KT], OVT[VT]]47DedupResult = t.Optional[OldKV[KT, VT]]48Unwrites = t.List[t.Tuple[t.Any, ...]]49BT = t.TypeVar('BT', bound='BidictBase[t.Any, t.Any]')50 51 52class BidictKeysView(t.KeysView[KT], t.ValuesView[KT]):53    """Since the keys of a bidict are the values of its inverse (and vice versa),54    the :class:`~collections.abc.ValuesView` result of calling *bi.values()*55    is also a :class:`~collections.abc.KeysView` of *bi.inverse*.56    """57 58 59class BidictBase(BidirectionalMapping[KT, VT]):60    """Base class implementing :class:`BidirectionalMapping`."""61 62    #: The default :class:`~bidict.OnDup`63    #: that governs behavior when a provided item64    #: duplicates the key or value of other item(s).65    #:66    #: *See also*67    #: :ref:`basic-usage:Values Must Be Unique` (https://bidict.rtfd.io/basic-usage.html#values-must-be-unique),68    #: :doc:`extending` (https://bidict.rtfd.io/extending.html)69    on_dup = ON_DUP_DEFAULT70 71    _fwdm: t.MutableMapping[KT, VT]  #: the backing forward mapping (*key* → *val*)72    _invm: t.MutableMapping[VT, KT]  #: the backing inverse mapping (*val* → *key*)73 74    # Use Any rather than KT/VT in the following to avoid "ClassVar cannot contain type variables" errors:75    _fwdm_cls: t.ClassVar[type[t.MutableMapping[t.Any, t.Any]]] = dict  #: class of the backing forward mapping76    _invm_cls: t.ClassVar[type[t.MutableMapping[t.Any, t.Any]]] = dict  #: class of the backing inverse mapping77 78    #: The class of the inverse bidict instance.79    _inv_cls: t.ClassVar[type[BidictBase[t.Any, t.Any]]]80 81    def __init_subclass__(cls) -> None:82        super().__init_subclass__()83        cls._init_class()84 85    @classmethod86    def _init_class(cls) -> None:87        cls._ensure_inv_cls()88        cls._set_reversed()89 90    __reversed__: t.ClassVar[t.Any]91 92    @classmethod93    def _set_reversed(cls) -> None:94        """Set __reversed__ for subclasses that do not set it explicitly95        according to whether backing mappings are reversible.96        """97        if cls is not BidictBase:98            resolved = cls.__reversed__99            overridden = resolved is not BidictBase.__reversed__100            if overridden:  # E.g. OrderedBidictBase, OrderedBidict101                return102        backing_reversible = all(issubclass(i, t.Reversible) for i in (cls._fwdm_cls, cls._invm_cls))103        cls.__reversed__ = _fwdm_reversed if backing_reversible else None104 105    @classmethod106    def _ensure_inv_cls(cls) -> None:107        """Ensure :attr:`_inv_cls` is set, computing it dynamically if necessary.108 109        All subclasses provided in :mod:`bidict` are their own inverse classes,110        i.e., their backing forward and inverse mappings are both the same type,111        but users may define subclasses where this is not the case.112        This method ensures that the inverse class is computed correctly regardless.113 114        See: :ref:`extending:Dynamic Inverse Class Generation`115        (https://bidict.rtfd.io/extending.html#dynamic-inverse-class-generation)116        """117        # This _ensure_inv_cls() method is (indirectly) corecursive with _make_inv_cls() below118        # in the case that we need to dynamically generate the inverse class:119        #   1. _ensure_inv_cls() calls cls._make_inv_cls()120        #   2. cls._make_inv_cls() calls type(..., (cls, ...), ...) to dynamically generate inv_cls121        #   3. Our __init_subclass__ hook (see above) is automatically called on inv_cls122        #   4. inv_cls.__init_subclass__() calls inv_cls._ensure_inv_cls()123        #   5. inv_cls._ensure_inv_cls() resolves to this implementation124        #      (inv_cls deliberately does not override this), so we're back where we started.125        # But since the _make_inv_cls() call will have set inv_cls.__dict__._inv_cls,126        # just check if it's already set before calling _make_inv_cls() to prevent infinite recursion.127        if getattr(cls, '__dict__', {}).get('_inv_cls'):  # Don't assume cls.__dict__ (e.g. mypyc native class)128            return129        cls._inv_cls = cls._make_inv_cls()130 131    @classmethod132    def _make_inv_cls(cls: type[BT]) -> type[BT]:133        diff = cls._inv_cls_dict_diff()134        cls_is_own_inv = all(getattr(cls, k, MISSING) == v for (k, v) in diff.items())135        if cls_is_own_inv:136            return cls137        # Suppress auto-calculation of _inv_cls's _inv_cls since we know it already.138        # Works with the guard in BidictBase._ensure_inv_cls() to prevent infinite recursion.139        diff['_inv_cls'] = cls140        inv_cls = type(f'{cls.__name__}Inv', (cls, GeneratedBidictInverse), diff)141        inv_cls.__module__ = cls.__module__142        return t.cast(t.Type[BT], inv_cls)143 144    @classmethod145    def _inv_cls_dict_diff(cls) -> dict[str, t.Any]:146        return {147            '_fwdm_cls': cls._invm_cls,148            '_invm_cls': cls._fwdm_cls,149        }150 151    def __init__(self, arg: MapOrItems[KT, VT] = (), /, **kw: VT) -> None:152        """Make a new bidirectional mapping.153        The signature behaves like that of :class:`dict`.154        ktems passed via positional arg are processed first,155        followed by any items passed via keyword argument.156        Any duplication encountered along the way157        is handled as per :attr:`on_dup`.158        """159        self._fwdm = self._fwdm_cls()160        self._invm = self._invm_cls()161        self._update(arg, kw, rollback=False)162 163    # If Python ever adds support for higher-kinded types, `inverse` could use them, e.g.164    #     def inverse(self: BT[KT, VT]) -> BT[VT, KT]:165    # Ref: https://github.com/python/typing/issues/548#issuecomment-621571821166    @property167    def inverse(self) -> BidictBase[VT, KT]:168        """The inverse of this bidirectional mapping instance."""169        # When `bi.inverse` is called for the first time, this method170        # computes the inverse instance, stores it for subsequent use, and then171        # returns it. It also stores a reference on `bi.inverse` back to `bi`,172        # but uses a weakref to avoid creating a reference cycle. Strong references173        # to inverse instances are stored in ._inv, and weak references are stored174        # in ._invweak.175 176        # First check if a strong reference is already stored.177        inv: BidictBase[VT, KT] | None = getattr(self, '_inv', None)178        if inv is not None:179            return inv180        # Next check if a weak reference is already stored.181        invweak = getattr(self, '_invweak', None)182        if invweak is not None:183            inv = invweak()  # Try to resolve a strong reference and return it.184            if inv is not None:185                return inv186        # No luck. Compute the inverse reference and store it for subsequent use.187        inv = self._make_inverse()188        self._inv: BidictBase[VT, KT] | None = inv189        self._invweak: weakref.ReferenceType[BidictBase[VT, KT]] | None = None190        # Also store a weak reference back to `instance` on its inverse instance, so that191        # the second `.inverse` access in `bi.inverse.inverse` hits the cached weakref.192        inv._inv = None193        inv._invweak = weakref.ref(self)194        # In e.g. `bidict().inverse.inverse`, this design ensures that a strong reference195        # back to the original instance is retained before its refcount drops to zero,196        # avoiding an unintended potential deallocation.197        return inv198 199    def _make_inverse(self) -> BidictBase[VT, KT]:200        inv: BidictBase[VT, KT] = self._inv_cls()201        inv._fwdm = self._invm202        inv._invm = self._fwdm203        return inv204 205    @property206    def inv(self) -> BidictBase[VT, KT]:207        """Alias for :attr:`inverse`."""208        return self.inverse209 210    def __repr__(self) -> str:211        """See :func:`repr`."""212        clsname = self.__class__.__name__213        items = dict(self.items()) if self else ''214        return f'{clsname}({items})'215 216    def values(self) -> BidictKeysView[VT]:217        """A set-like object providing a view on the contained values.218 219        Since the values of a bidict are equivalent to the keys of its inverse,220        this method returns a set-like object for this bidict's values221        rather than just a collections.abc.ValuesView.222        This object supports set operations like union and difference,223        and constant- rather than linear-time containment checks,224        and is no more expensive to provide than the less capable225        collections.abc.ValuesView would be.226 227        See :meth:`keys` for more information.228        """229        return t.cast(BidictKeysView[VT], self.inverse.keys())230 231    def keys(self) -> t.KeysView[KT]:232        """A set-like object providing a view on the contained keys.233 234        When *b._fwdm* is a :class:`dict`, *b.keys()* returns a235        *dict_keys* object that behaves exactly the same as236        *collections.abc.KeysView(b)*, except for237 238          - offering better performance239 240          - being reversible on Python 3.8+241 242          - having a .mapping attribute in Python 3.10+243            that exposes a mappingproxy to *b._fwdm*.244        """245        fwdm, fwdm_cls = self._fwdm, self._fwdm_cls246        return fwdm.keys() if fwdm_cls is dict else BidictKeysView(self)247 248    def items(self) -> t.ItemsView[KT, VT]:249        """A set-like object providing a view on the contained items.250 251        When *b._fwdm* is a :class:`dict`, *b.items()* returns a252        *dict_items* object that behaves exactly the same as253        *collections.abc.ItemsView(b)*, except for:254 255          - offering better performance256 257          - being reversible on Python 3.8+258 259          - having a .mapping attribute in Python 3.10+260            that exposes a mappingproxy to *b._fwdm*.261        """262        return self._fwdm.items() if self._fwdm_cls is dict else super().items()263 264    # The inherited collections.abc.Mapping.__contains__() method is implemented by doing a `try`265    # `except KeyError` around `self[key]`. The following implementation is much faster,266    # especially in the missing case.267    def __contains__(self, key: t.Any) -> bool:268        """True if the mapping contains the specified key, else False."""269        return key in self._fwdm270 271    # The inherited collections.abc.Mapping.__eq__() method is implemented in terms of an inefficient272    # `dict(self.items()) == dict(other.items())` comparison, so override it with a273    # more efficient implementation.274    def __eq__(self, other: object) -> bool:275        """*x.__eq__(other)　⟺　x == other*276 277        Equivalent to *dict(x.items()) == dict(other.items())*278        but more efficient.279 280        Note that :meth:`bidict's __eq__() <bidict.BidictBase.__eq__>` implementation281        is inherited by subclasses,282        in particular by the ordered bidict subclasses,283        so even with ordered bidicts,284        :ref:`== comparison is order-insensitive <eq-order-insensitive>`285        (https://bidict.rtfd.io/other-bidict-types.html#eq-is-order-insensitive).286 287        *See also* :meth:`equals_order_sensitive`288        """289        if isinstance(other, t.Mapping):290            return self._fwdm.items() == other.items()291        # Ref: https://docs.python.org/3/library/constants.html#NotImplemented292        return NotImplemented293 294    def equals_order_sensitive(self, other: object) -> bool:295        """Order-sensitive equality check.296 297        *See also* :ref:`eq-order-insensitive`298        (https://bidict.rtfd.io/other-bidict-types.html#eq-is-order-insensitive)299        """300        if not isinstance(other, t.Mapping) or len(self) != len(other):301            return False302        return all(starmap(eq, zip(self.items(), other.items())))303 304    def _dedup(self, key: KT, val: VT, on_dup: OnDup) -> DedupResult[KT, VT]:305        """Check *key* and *val* for any duplication in self.306 307        Handle any duplication as per the passed in *on_dup*.308 309        If (key, val) is already present, return None310        since writing (key, val) would be a no-op.311 312        If duplication is found and the corresponding :class:`~bidict.OnDupAction` is313        :attr:`~bidict.DROP_NEW`, return None.314 315        If duplication is found and the corresponding :class:`~bidict.OnDupAction` is316        :attr:`~bidict.RAISE`, raise the appropriate exception.317 318        If duplication is found and the corresponding :class:`~bidict.OnDupAction` is319        :attr:`~bidict.DROP_OLD`, or if no duplication is found,320        return *(oldkey, oldval)*.321        """322        fwdm, invm = self._fwdm, self._invm323        oldval: OVT[VT] = fwdm.get(key, MISSING)324        oldkey: OKT[KT] = invm.get(val, MISSING)325        isdupkey, isdupval = oldval is not MISSING, oldkey is not MISSING326        if isdupkey and isdupval:327            if key == oldkey:328                assert val == oldval329                # (key, val) duplicates an existing item -> no-op.330                return None331            # key and val each duplicate a different existing item.332            if on_dup.val is RAISE:333                raise KeyAndValueDuplicationError(key, val)334            if on_dup.val is DROP_NEW:335                return None336            assert on_dup.val is DROP_OLD337            # Fall through to the return statement on the last line.338        elif isdupkey:339            if on_dup.key is RAISE:340                raise KeyDuplicationError(key)341            if on_dup.key is DROP_NEW:342                return None343            assert on_dup.key is DROP_OLD344            # Fall through to the return statement on the last line.345        elif isdupval:346            if on_dup.val is RAISE:347                raise ValueDuplicationError(val)348            if on_dup.val is DROP_NEW:349                return None350            assert on_dup.val is DROP_OLD351            # Fall through to the return statement on the last line.352        # else neither isdupkey nor isdupval.353        return oldkey, oldval354 355    def _write(self, newkey: KT, newval: VT, oldkey: OKT[KT], oldval: OVT[VT], unwrites: Unwrites | None) -> None:356        """Insert (newkey, newval), extending *unwrites* with associated inverse operations if provided.357 358        *oldkey* and *oldval* are as returned by :meth:`_dedup`.359 360        If *unwrites* is not None, it is extended with the inverse operations necessary to undo the write.361        This design allows :meth:`_update` to roll back a partially applied update that fails part-way through362        when necessary.363 364        This design also allows subclasses that require additional operations to easily extend this implementation.365        For example, :class:`bidict.OrderedBidictBase` calls this inherited implementation, and then extends *unwrites*366        with additional operations needed to keep its internal linked list nodes consistent with its items' order367        as changes are made.368        """369        fwdm, invm = self._fwdm, self._invm370        fwdm_set, invm_set = fwdm.__setitem__, invm.__setitem__371        fwdm_del, invm_del = fwdm.__delitem__, invm.__delitem__372        # Always perform the following writes regardless of duplication.373        fwdm_set(newkey, newval)374        invm_set(newval, newkey)375        if oldval is MISSING and oldkey is MISSING:  # no key or value duplication376            # {0: 1, 2: 3} | {4: 5} => {0: 1, 2: 3, 4: 5}377            if unwrites is not None:378                unwrites.extend((379                    (fwdm_del, newkey),380                    (invm_del, newval),381                ))382        elif oldval is not MISSING and oldkey is not MISSING:  # key and value duplication across two different items383            # {0: 1, 2: 3} | {0: 3} => {0: 3}384            fwdm_del(oldkey)385            invm_del(oldval)386            if unwrites is not None:387                unwrites.extend((388                    (fwdm_set, newkey, oldval),389                    (invm_set, oldval, newkey),390                    (fwdm_set, oldkey, newval),391                    (invm_set, newval, oldkey),392                ))393        elif oldval is not MISSING:  # just key duplication394            # {0: 1, 2: 3} | {2: 4} => {0: 1, 2: 4}395            invm_del(oldval)396            if unwrites is not None:397                unwrites.extend((398                    (fwdm_set, newkey, oldval),399                    (invm_set, oldval, newkey),400                    (invm_del, newval),401                ))402        else:403            assert oldkey is not MISSING  # just value duplication404            # {0: 1, 2: 3} | {4: 3} => {0: 1, 4: 3}405            fwdm_del(oldkey)406            if unwrites is not None:407                unwrites.extend((408                    (fwdm_set, oldkey, newval),409                    (invm_set, newval, oldkey),410                    (fwdm_del, newkey),411                ))412 413    def _update(414        self,415        arg: MapOrItems[KT, VT],416        kw: t.Mapping[str, VT] = MappingProxyType({}),417        *,418        rollback: bool | None = None,419        on_dup: OnDup | None = None,420    ) -> None:421        """Update with the items from *arg* and *kw*, maybe failing and rolling back as per *on_dup* and *rollback*."""422        # Note: We must process input in a single pass, since arg may be a generator.423        if not isinstance(arg, (t.Iterable, Maplike)):424            raise TypeError(f"'{arg.__class__.__name__}' object is not iterable")425        if not arg and not kw:426            return427        if on_dup is None:428            on_dup = self.on_dup429        if rollback is None:430            rollback = RAISE in on_dup431 432        # Fast path when we're empty and updating only from another bidict (i.e. no dup vals in new items).433        if not self and not kw and isinstance(arg, BidictBase):434            self._init_from(arg)435            return436 437        # Fast path when we're adding more items than we contain already and rollback is enabled:438        # Update a copy of self with rollback disabled. Fail if that fails, otherwise become the copy.439        if rollback and isinstance(arg, t.Sized) and len(arg) + len(kw) > len(self):440            tmp = self.copy()441            tmp._update(arg, kw, rollback=False, on_dup=on_dup)442            self._init_from(tmp)443            return444 445        # In all other cases, benchmarking has indicated that the update is best implemented as follows:446        # For each new item, perform a dup check (raising if necessary), and apply the associated writes we need to447        # perform on our backing _fwdm and _invm mappings. If rollback is enabled, also compute the associated unwrites448        # as we go. If the update results in a DuplicationError and rollback is enabled, apply the accumulated unwrites449        # before raising, to ensure that we fail clean.450        write = self._write451        unwrites: Unwrites | None = [] if rollback else None452        for key, val in iteritems(arg, **kw):453            try:454                dedup_result = self._dedup(key, val, on_dup)455            except DuplicationError:456                if unwrites is not None:457                    for fn, *args in reversed(unwrites):458                        fn(*args)459                raise460            if dedup_result is not None:461                write(key, val, *dedup_result, unwrites=unwrites)462 463    def __copy__(self: BT) -> BT:464        """Used for the copy protocol. See the :mod:`copy` module."""465        return self.copy()466 467    def copy(self: BT) -> BT:468        """Make a (shallow) copy of this bidict."""469        # Could just `return self.__class__(self)` here, but the below is faster. The former470        # would copy this bidict's items into a new instance one at a time (checking for duplication471        # for each item), whereas the below copies from the backing mappings all at once, and foregoes472        # item-by-item duplication checking since the backing mappings have been checked already.473        return self._from_other(self.__class__, self)474 475    @staticmethod476    def _from_other(bt: type[BT], other: MapOrItems[KT, VT], inv: bool = False) -> BT:477        """Fast, private constructor based on :meth:`_init_from`.478 479        If *inv* is true, return the inverse of the instance instead of the instance itself.480        (Useful for pickling with dynamically-generated inverse classes -- see :meth:`__reduce__`.)481        """482        inst = bt()483        inst._init_from(other)484        return t.cast(BT, inst.inverse) if inv else inst485 486    def _init_from(self, other: MapOrItems[KT, VT]) -> None:487        """Fast init from *other*, bypassing item-by-item duplication checking."""488        self._fwdm.clear()489        self._invm.clear()490        self._fwdm.update(other)491        # If other is a bidict, use its existing backing inverse mapping, otherwise492        # other could be a generator that's now exhausted, so invert self._fwdm on the fly.493        inv = other.inverse if isinstance(other, BidictBase) else inverted(self._fwdm)494        self._invm.update(inv)495 496    # other's type is Mapping rather than Maplike since bidict() | SupportsKeysAndGetItem({})497    # raises a TypeError, just like dict() | SupportsKeysAndGetItem({}) does.498    def __or__(self: BT, other: t.Mapping[KT, VT]) -> BT:499        """Return self|other."""500        if not isinstance(other, t.Mapping):501            return NotImplemented502        new = self.copy()503        new._update(other, rollback=False)504        return new505 506    def __ror__(self: BT, other: t.Mapping[KT, VT]) -> BT:507        """Return other|self."""508        if not isinstance(other, t.Mapping):509            return NotImplemented510        new = self.__class__(other)511        new._update(self, rollback=False)512        return new513 514    def __len__(self) -> int:515        """The number of contained items."""516        return len(self._fwdm)517 518    def __iter__(self) -> t.Iterator[KT]:519        """Iterator over the contained keys."""520        return iter(self._fwdm)521 522    def __getitem__(self, key: KT) -> VT:523        """*x.__getitem__(key) ⟺ x[key]*"""524        return self._fwdm[key]525 526    def __reduce__(self) -> tuple[t.Any, ...]:527        """Return state information for pickling."""528        cls = self.__class__529        inst: t.Mapping[t.Any, t.Any] = self530        # If this bidict's class is dynamically generated, pickle the inverse instead, whose (presumably not531        # dynamically generated) class the caller is more likely to have a reference to somewhere in sys.modules532        # that pickle can discover.533        if should_invert := isinstance(self, GeneratedBidictInverse):534            cls = self._inv_cls535            inst = self.inverse536        return self._from_other, (cls, dict(inst), should_invert)537 538 539# See BidictBase._set_reversed() above.540def _fwdm_reversed(self: BidictBase[KT, t.Any]) -> t.Iterator[KT]:541    """Iterator over the contained keys in reverse order."""542    assert isinstance(self._fwdm, t.Reversible)543    return reversed(self._fwdm)544 545 546BidictBase._init_class()547 548 549class GeneratedBidictInverse:550    """Base class for dynamically-generated inverse bidict classes."""551 552 553#                             * Code review nav *554# ============================================================================555# ← Prev: _abc.py              Current: _base.py            Next: _frozen.py →556# ============================================================================557