[Feature Request] beartype.is_subtypes() API for deciding type hint A ⊆ B "compatibility" subset relations

Discussed in https://github.com/beartype/beartype/discussions/132

Originally posted by tlambert03 May 31, 2022
First, thanks for this amazing library.  The scope and detail are beary impressive. 🐻
Apologies if I've missed an obvious answer (or previous discussion) of this question: I've been digging through the readme and source code for a couple days but still haven't hit on it, and I'm not sure if this is just fundamentally out of the primary goal here of isinstance(some_object, some_typehint).
I'm looking for something that would tell me whether type hint B is "compatible" with type hint A (something akin to pytypes is_subtype function):
from typing import Sequence, List, Union, Optional, Any

def is_subtype(hintA, hintB) -> bool:
    ...  # ?

assert is_subtype(list, list) is True
assert is_subtype(list, Sequence) is True
assert is_subtype(Sequence, list) is False

assert is_subtype(List[int], Sequence[Any]) is True
assert is_subtype(List[int], Sequence[int]) is True
assert is_subtype(List[int], Sequence[str]) is False

assert is_subtype(list, Union[list, str]) is True
assert is_subtype(Union[int, str], Union[int, str, list]) is True
assert is_subtype(Union[list, str], list) is False
assert is_subtype(list, Union[int, str]) is False
assert is_subtype(Union[int, tuple], Union[int, str, list]) is False

assert is_subtype(Optional[int], int) is False
assert is_subtype(int, Optional[int]) is True

is this something that could be achieved with beartype?  digging through the source, i see lots of stuff that seems very useful towards this goal, but not sure I see anything in the public API (since we're not really trying to determine whether some object is an instance of a hint).
my goal here would be to detect if an API breakage has occurred between two versions:
# version 1
def func() -> list:
   ...

# version 2
def func() -> Sequence:  # potential API breakage
   ...

... and this seems like something you'd have an opinion on :)
thanks for your work!

Originally posted by tlambert03 May 31, 2022
lolll ... I commend your honesty :joy:
I am not surprised to hear you say that.  I kinda supposed it was a hardcore feature.  I'll promise to try to sneak your name into any conversations I happen to have with deep-pocketed FOSS lovers 🤑
however... in the meantime, let's suppose I'm a positively gruntled lemming who's a bit obsessed with this problem at the moment, likely a bit naïve, and that you're not going to lose me that easily.  (but that I also definitely don't expect to pull you so easily from your many other dumpster fires which we can all understand and empathize with).
And let's also suppose that I'm ok with thinking about this in stages.   If you look at the pytypes implementation, for all its complexity and indirection, it boils down to this:
from typing import ForwardRef, TypeVar

def is_subtype(sub, sup):
    if isinstance(sub, ForwardRef) or isinstance(sup, ForwardRef): ...
        # deal with all the nastiness of ForwardRefs
    if issubclass(sub, Empty) or issubclass(sup, Empty): ...
        # where Empty is a special pytypes class trying to deal with
        # https://github.com/python/typing/issues/157
    if isinstance(sup, TypeVar) or isinstance(sub, TypeVar): ...
        # deal with __bound__, __contravariant__, __covariant__
    if is_Tuple(sup): ...
    if is_Union(sup): ...
    if is_Union(sub): ...
    if is_Generic(sup): ...
    try:
        return issubclass(sub, sup)
    except TypeError:
        return False

ForwardRefs are annoying, but that's a different (namespace) problem.
I'm ok with ignoring the Empty case for now, maybe forever.
TypeVar is bounds and co/contra-variants are hard, but I'd happily raise a NotImplementedError for now and likely still profit quite a bit.
after that, we're down to Generics – probably the bulk of the "non-standard" work
then the rest is "straightforward" enough.

If I were to dig into this some more on my own time – likely using some of your private API and fully expecting it to break without notice – would you have any additional "here's where I might start if I were you" sort of thoughts?  (s'ok if not!)  I feel like there's some gold buried in sanify_hint_root and in _util/hint/* that could get this started off on at least a nice normalized footing.
thanks already for your time and thorough response!

Yes, yes, and yes. While clearing the ruinous fallout of a 150 year-old oak tree that fell over during the deadliest derecho in Ontario history, crushed our bunkhouse, and then toppled onto our cottage, I had a miraculous epiphany. Praise Guido!
I didn't intend to think about this – but there I was, hauling debris, petting cats, and thinking about this despite my best intentions. But first...
What Not to Do
What not to do is what pytypes does – probably. You've spelunked deeper into the cavernous labyrinth of the pytypes codebase than I have. So, this is mere baseless speculation on my part. But...
What pytypes does is guaranteed to fail – probably. If I'm reading the pytypes.type_util submodule correctly, the pytypes.is_subtype() function basically reduces to a linear chain of if conditionals. Your superb synopsis of that function corroborates that I am not entirely insane. Sadly, a linear chain of if conditionals can't possibly suffice to cover all possible edge cases. Why? Because type hints are infinitely composable (i.e., recursively nestable). For example, consider just this simple fragment from your pytypes.is_subtype() simplification:
    if is_Tuple(sup): ...
    if is_Union(sup): ...
    if is_Union(sub): ...
    if is_Generic(sup): ...

So, what if both the subtype and supertype are type hints containing multiple generics subscripting multiple tuples subscripting multiple unions subscripting a dictionary subscripting a list (e.g., list[dict[Union[tuple[MuhGeneric, MuhOtherGeneric, ...], int], str]])? Those are hardly worst-case type hints, either.
Since there are a countably infinite number of possible type hints, there's an even larger number of 2-combinations (subtype, supertype) for any arbitrary type hint subtype being compared against any arbitrary type hint supertype. Ergo, there is some 2-combination of type hints that cannot possibly be handled by a linear chain of if conditionals. Indeed, the binomial coefficient tells us that the number of possible 2-combinations between n type hints grows explosively as:
(n 2) = "n pick 2" = n!/[2(n-2)!]

This is why C++ popularized operator overloading, right? By overloading the <= comparator within four C++ classes A, B, C, and D in a compatible manner, any two instances of those four classes can be implicitly compared without having to explicitly code a linear chain of if conditionals. That's good! Explicitly coding a linear chain of if conditionals rapidly becomes impossible in practice, because combinatorial explosion makes my brain burn.
What to Do, Then?
What to do is what we always do in Computer Science when confronted with a seemingly insurmountable, intractable, and infeasible mountain of pain: we transform that complex problem we cannot solve into a simpler problem we have already solved.
In this case, Python has already solved a simpler problem: deciding whether one type is a subclass of another (i.e., the issubclass(A, B) relation). If we can transform our complex is_subtype(A, B) relation we cannot readily solve into the simpler issubclass(A, B) relation that Python has already solved, then our job is done before it even began. Can we do this?
Yes, we can. you knew that was coming B-b-but... how can we? "Simple." The beartype.is_subtype(subtype, supertype) tester function should probably:

Dynamically create one in-memory class for each inclusive superclass of each nested type hint of each passed type hint, ultimately producing two internal type hierarchies: a type hierarchy SubType representing the passed subtype type hint and yet another type hierarchy SuperType representing the passed supertype type hint. This operation has O(jk) time complexity (I think?), where:

j is the maximum number of superclasses of any nested type hint, equivalent to the length of the method resolution order (MRO) for that hint (i.e., j = len(type_hint.__mro__)).
k is the maximum number of nested type hints of each passed type hint.

Return the result of calling issubclass(SubType, SuperType).

Obviously, 2. is a trivial one-liner. That just leaves 1., which is non-trivial but tractable. Consider this concrete example:
>>> from beartype import is_subtype
>>> from beartype.typing import list, Sequence, Union

# User-defined "int" subclass, just 'cause.
>>> class MuhInt(int): pass

>>> subtype = list[MuhInt]
>>> supertype = Union[Sequence[int], str]
>>> is_subtype(subtype, supertype)
True

Internally, beartype.is_subtype() will create two type hierarchies: one representing the passed subtype and the other representing the passed supertype. For this concrete example, these type hierarchies might resemble:
     # v--- beartype-specific fast caching protocols for the win
from beartype.typing import Protocol

# ------[ TYPE HIERARCHY FOR: list[MuhInt] ]------
# Type representing the type hint "list[object]".
class ListOfObject(list, Protocol): pass

# Type representing the type hint "list[int]".
class ListOfInt(ListOfObject, Protocol):
    def has_int(): pass

# Type representing the type hint "list[MuhInt]".
class ListOfMuhInt(ListOfInt, Protocol):
    def has_MuhInt(): pass

# ------[ TYPE HIERARCHY FOR: Union[Sequence[int], str] ]------
# Type representing the type hint "Sequence[object]".
from collections.abc import Sequence
class SequenceOfObject(Sequence, Protocol): pass

# Type representing the type hint "Sequence[int]".
class SequenceOfInt(SequenceOfObject, Protocol):
    def has_int(): pass

# Type representing the type hint "Union[Sequence[int], str]".
UnionOfSequenceOfIntAndStr = SequenceOfInt | str
         # ^--- check dat dark PEP 604 magic out, bro

We can both agree there's a tractable algorithm for producing those two type hierarchies, right? Right!  Indeed, note that Python itself already provides an out-of-the-box comparison between the builtin list type and the collections.abc.Sequence ABC:
>>> from collections.abc import Sequence
>>> issubclass(list, Sequence)
True

Because both the ListOfMuhInt and SequenceOfInt protocols declare the same has_int() method, the former is necessarily a subclass of the latter under PEP 544-style structural subtyping. :open_mouth:
We can also then agree that we've transformed our complex is_subtype(A, B) relation we cannot readily solve into the simpler issubclass(A, B) relation that Python has already solved. Altogether, this means that:
# This non-trivial function call copied from above...
>>> is_subtype(list[MuhInt], Union[Sequence[int], str])
# ...is now trivially reducible to this obvious function call
# leveraging the two type hierarchies we generated above.
>>> issubclass(ListOfMuhInt, UnionOfSequenceOfIntAndStr)
True

I've tested that. It actually works. Shocked Pikachu face, arise!

...Can't Be That Easy
...heh. Yeah.  But until that happens, let's choose to believe in the miraculous healing power of Python's issubclass() builtin. :grin:

Dynamically create one in-memory class for each inclusive superclass of each nested type hint of each passed type hint

brilliant! 🎉
I'm so sorry to hear about your bunkhouse & cottage, but I'm really glad/appreciative that this problem is still percolating a bit in your brain.
I will definitely take your example here and tinker with it some more.  I'll open a PR if I hit on something useful (though I suspect it will not be up to beartype rigor).

Yep, I'm more than happy to take this in stages.  Particularly for the application of detecting API changes, even if this works 50% of the time, it's still way better than nothing.  If we just quietly fail when it breaks, we haven't done anything worse than the situation we're already in... which is no checking whatsoever :joy:
thanks again!

I'll open a PR if I hit on something useful (though I suspect it will not be up to beartype rigor).

Wunderbar! Literally anything is useful, because we currently have nothing. Unlike various other GitHub repositories that shall remain nameless, I've committed to merging every PR that passes tests in a prompt and shamelessly desperate manner. I'm here for the community, because the community's here for me. :hugs:
What now follows are mostly unreadable notes to myself, because I will forget this tomorrow. In fact, I've already forgotten everything. Thanks fer nuthin', short-term memory recall. </gulp>
Unions: They're No Longer Just for Dock Workers
Above, I slyly suggested that union type hints (e.g., Union[Sequence[int], str]) could just be coerced into PEP 644-style new union objects (e.g., SequenceOfInt | str). Technically, that works in the exact example I gave. Pragmatically, I just got lucky. That doesn't work in general. PEP 644-style new union objects can't be subclassed, which means you can't generalize that coercion to embedded unions (e.g., list[Union[Sequence[int], str]]):
>>> class StrOrInt(str | int): pass
TypeError: cannot create 'types.UnionType' instances

That means we'll need to do something magical to support embedded unions. Since "magical" is synonymous with "pagan metaclass trickery" in Python, that means we'll need to define a new beartype.typing._typingpep544._CachingProtocolMeta.__subclasscheck__() dunder method handling embedded unions. Since the beartype.typing._typingpep544 submodule is already an incoherent nightmare despite the collective best efforts of the bear bros, that means...
This may never happen. Still, I hope with an ageless, burning hunger that someone who is not me tries to do something about this. They'll probably crash and burn, true – but at least they'll have tried.
So, Impossible?
Probably, yes.

The source of mypy.subtypes.is_subtype will almost certainly be of relevance here as well.
Outside of difficulties of using mypy directly (i.e. outside of cli usage) the main reason it can't be used directly is that it accepts mypy.types.Type objects as arguments... I don't know enough about the internals of mypy to figure out how to construct one of those Type objects outside of mypy on the cli, but that might also be worth looking into

lolbro. I did this, because Harvard Medical School deserves this best. Srsly, tho. Your feature request inspired me hard while clearing yet more tree wreckage from our based hugelkultur permaculture raised garden bed. Ergo, I did this for humanity and Harvard:
# In the existing "beartype.roar._roarexc" submodule:
class BeartypeMathException(BeartypeException):
    '''
    Abstract base class of all **beartype math exceptions.**

    Instances of subclasses of this exception are raised at call time from the
    callables and classes published by the :func:`beartype.math` subpackage.
    '''

    pass

# In a new "beartype.math.__init__" submodule:
from beartype.math._mathcls import TypeHint

# In a new "beartype.math._mathcls" submodule:
from beartype.roar import BeartypeMathException
from beartype.typing import (
    Iterable,
)
from beartype._data.hint.pep.sign.datapepsigns import (
    HintSignAbstractSet,
    HintSignAsyncContextManager,
    HintSignAsyncIterable,
    HintSignAsyncIterator,
    HintSignAwaitable,
    HintSignByteString,
    HintSignCollection,
    HintSignContainer,
    HintSignContextManager,
    HintSignCounter,
    HintSignDeque,
    HintSignFrozenSet,
    HintSignItemsView,
    HintSignIterable,
    HintSignIterator,
    HintSignKeysView,
    HintSignList,
    HintSignMatch,
    HintSignMutableSequence,
    HintSignMutableSet,
    HintSignPattern,
    HintSignSequence,
    HintSignSet,
    HintSignType,
    HintSignValuesView,
)
from beartype._data.hint.pep.sign.datapepsignset import (
    HINT_SIGNS_UNION,
)
from beartype._util.cache.utilcachecall import callable_cached
from beartype._util.hint.pep.utilpepget import (
    get_hint_pep_args,
    get_hint_pep_sign,
)
from collections.abc import Collection as CollectionABC
from functools import total_ordering

#FIXME: Unit test us up, please!
@total_ordering
class TypeHint(CollectionABC):
    '''
    Abstract base class (ABC) of all **totally ordered type hint** (i.e.,
    high-level object encapsulating a low-level type hint augmented with all
    rich comparison ordering methods).

    Instances of this class are totally ordered with respect to one another.
    Equivalently, instances of this class support all binary comparators (i.e.,
    ``==``, ``!=``, ``<``, ``<=``, ``>``, and ``>=``) according such that for
    any three instances ``a``, ``b`, and ``c`` of this class:

    * ``a ≤ a`` (i.e., reflexivity).
    * If ``a ≤ b`` and ``b ≤ c``, then ``a ≤ c`` (i.e., transitivity).
    * If ``a ≤ b`` and ``b ≤ a``, then ``a == b`` (i.e., antisymmetry).
    * Either ``a ≤ b`` or ``b ≤ a`` (i.e., totality).

    Instances of this class are thus usable in algorithms and data structures
    requiring a total ordering across their input.
    '''

    def __new__(cls, hint: object) -> 'TypeHint':
        '''
        Factory constructor magically instantiating and returning an instance of
        the private concrete subclass of this public abstract base class (ABC)
        appropriate for handling the passed low-level unordered type hint.

        Parameters
        ----------
        hint : object
            Lower-level unordered type hint to be encapsulated by this
            higher-level totally ordered type hint.

        Returns
        ----------
        TypeHint
           Higher-level totally ordered type hint encapsulating that hint.

        Raises
        ----------
        BeartypeMathException
            If this class does *not* currently support the passed hint.
        BeartypeDecorHintPepSignException
            If the passed hint is *not* actually a PEP-compliant type hint.
        '''

        # Sign uniquely identifying this hint if any *OR* raise an exception
        # (i.e., if this hint is *NOT* actually a PEP-compliant type hint).
        hint_sign = get_hint_pep_sign(hint)

        # Private concrete subclass of this ABC handling this hint if any *OR*
        # "None" otherwise (i.e., if no such subclass has been authored yet).
        TypeHintSubclass = _HINT_SIGN_TO_TypeHint.get(hint_sign)

        # If this hint appears to be currently unsupported...
        if TypeHintSubclass is None:
            # If this hint is a type, defer to the subclass handling types.
            if isinstance(hint, type):
                TypeHintSubclass = _TypeHintClass
            # Else, this hint is *NOT* a type. Ergo, this hint is unsupported.
            # In this case, raise an exception.
            else:
                raise BeartypeMathException(
                    f'Type hint {repr(hint)} currently unsupported by '
                    f'class "beartype.math.TypeHint".'
                )
        # Else, this hint is supported.

        # Return this subclass.
        return super().__new__(TypeHintSubclass)

    def __init__(self, hint: object) -> None:
        '''
        Initialize this high-level totally ordered type hint against the passed
        low-level unordered type hint.

        Parameters
        ----------
        hint : object
            Lower-level unordered type hint to be encapsulated by this
            higher-level totally ordered type hint.
        '''

        # Classify all passed parameters. Note that this type hint is guaranteed
        # to be a type hint by validation performed by the __new__() method.
        self._hint = hint

        # Tuple of all low-level unordered child type hints of this hint.
        self._hints_child_unordered = get_hint_pep_args(hint)

        # Tuple of all high-level totally ordered child type hints of this hint.
        self._hints_child_ordered = tuple(
            TypeHint(hint_child_unordered)
            for hint_child_unordered in self._hints_child_unordered
        )

    def __len__(self) -> int:
        return len(self._hints_child_ordered)

    def __iter__(self) -> Iterable['TypeHint']:
        '''
        Immutable iterable of all **children** (i.e., high-level totally ordered
        type hints encapsulating all low-level unordered child type hints
        subscripting (indexing) the low-level unordered parent type hint
        encapsulated by this high-level totally ordered parent type hint) of
        this totally ordered parent type hint.
        '''

        return self._hints_child_ordered

    #FIXME: Implement us up, please! The implementation should probably resemble
    #that of the __le__() method defined below. *phew*
    #FIXME: Docstring us up, please!
    @abstractmethod
    def __eq__(self, other: 'TypeHint') -> bool: pass

    @callable_cached
    def __le__(self, other: 'TypeHint') -> bool:
        '''
        ``True`` only if this totally ordered type hint is **compatible** with
        the passed totally ordered type hint, where compatibility implies that
        the unordered type hint encapsulated by this totally ordered type hint
        may be losslessly replaced by the unordered type hint encapsulated by
        the parent totally ordered type hint *without* breaking backward
        compatibility in APIs annotated by the former.

        This method is memoized and thus enjoys ``O(1)`` amortized worst-case
        time complexity across all calls to this method.
        '''

        # If the passed object is *NOT* a totally ordered type hint, raise an
        # exception.
        _die_unless_TypeHint(other)
        # Else, that object is a totally ordered type hint.

        # For each branch of the passed union if that hint is a union *OR* that
        # hint as is otherwise...
        for branch in other.branches():
            # If this hint is compatible with that branch, return true.
            if self._is_le_branch(branch):
                return True
            # Else, this hint is incompatible with that branch. In this case,
            # silently continue to the next branch.

        # Else, this hint is incompatible with that hint.
        return False

    @property
    def branches(self) -> Iterable['TypeHint']:
        '''
        Immutable iterable of all **branches** (i.e., high-level totally ordered
        type hints encapsulating all low-level unordered child type hints
        subscripting (indexing) the low-level unordered parent type hint
        encapsulated by this high-level totally ordered parent type hint if this
        is a union (and thus an instance of the :class:`_TypeHintUnion`
        subclass) *or* the 1-tuple containing only this instance itself
        otherwise) of this totally ordered parent type hint.

        This property enables the child type hints of :pep:`484`- and
        :pep:`604`-compliant unions (e.g., :attr:`typing.Union`,
        :attr:`typing.Optional`, and ``|``-delimited type objects) to be handled
        transparently *without* special cases in subclass implementations.
        '''

        # Default to returning the 1-tuple containing only this instance, as
        # *ALL* subclasses except "_HintTypeUnion" require this default.
        return (self,)

    @abstractmethod
    def _is_le_branch(self, branch: 'TypeHint') -> bool:
        '''
        ``True`` only if this totally ordered type hint is **compatible** with
        the passed branch of another totally ordered type hint passed to the
        parent call of the :meth:`__le__` dunder method.

        See Also
        ----------
        :meth:`__le__`
            Further details.
        '''

        pass

class _TypeHintClass(TypeHint):
    '''
    **Totally ordered class type hint** (i.e., high-level object encapsulating a
    low-level PEP-compliant type hint that is, in fact, a simple class).
    '''

    #FIXME: Define __eq__() too, please!

    def _is_le_branch(self, branch: TypeHint) -> bool:

        # Return true only if...
        return (
            # That branch is also a totally ordered class type hint *AND*...
            isinstance(branch, _TypeHintClass) and
            issubclass(
                # The low-level unordered type hint encapsulated by this
                # high-level totally ordered type hint is a subclass of...
                self._hint,
                # The low-level unordered type hint encapsulated by that
                # branch...
                branch._hint
            )
        )

class _TypeHintSubscripted(TypeHint):
    '''
    **Totally ordered subscripted type hint** (i.e., high-level object
    encapsulating a low-level parent type hint subscripted (indexed) by one or
    more equally low-level children type hints).

    Attributes
    ----------
    _hints_child_unordered : tuple[object]
        Tuple of all low-level unordered children type hints of the low-level
        unordered parent type hint passed to the :meth:`__init__` method.
    _hints_child_ordered : tuple[TypeHint]
        Tuple of all high-level totally ordered children type hints of this
        high-level totally ordered parent type hint.
    '''

    def __init__(self, *args, **kwargs) -> None:
        '''
        Initialize this high-level totally ordered subscripted type hint against
        the passed low-level unordered subscripted type hint.

        Parameters
        ----------
        All passed parameters are passed as is to the superclass
        :meth:`TypeHint.__init__` method.
        '''

        # Initialize our superclass with all passed parameters.
        super().__init__(*args, **kwargs)

        #FIXME: Perform additional validation here, please. Notably, raise an
        #exception if this hint is subscripted by *NO* child type hints.
        # Tuple of all low-level unordered child type hints of this hint.
        self._hints_child_unordered = get_hint_pep_args(hint)

        # Tuple of all high-level totally ordered child type hints of this hint.
        self._hints_child_ordered = tuple(
            TypeHint(hint_child_unordered)
            for hint_child_unordered in self._hints_child_unordered
        )

class _TypeHintOriginIsinstanceableArgs1(_TypeHintSubscripted):
    '''
    **Totally ordered single-argument isinstanceable type hint** (i.e.,
    high-level object encapsulating a low-level PEP-compliant type hint
    subscriptable by only one child type hint originating from an
    isinstanceable class such that *all* objects satisfying that hint are
    instances of that class).
    '''

    #FIXME: Define __eq__() too, please!

    def _is_le_branch(self, branch: TypeHint) -> bool:

        # Return true only if...
        return (
            # That branch is also a totally ordered single-argument
            # isinstanceable type hint *AND*...
            isinstance(branch, _TypeHintOriginIsinstanceableArgs1) and
            issubclass(
                # The low-level unordered type hint encapsulated by this
                # high-level totally ordered type hint is a subclass of...
                self._hint,
                # The low-level unordered type hint encapsulated by that
                # branch...
                branch._hint
            ) and
            # The high-level totally ordered child type hint subscripted by this
            # high-level totally ordered parent type hint is "compatible" with
            # the high-level totally ordered child type hint subscripted by that
            # high-level totally ordered parent type hint.
            self._hints_child_unordered[0] <= branch._hints_child_unordered[0]
        )

class _TypeHintUnion(_TypeHintSubscripted):
    '''
    **Totally ordered union type hint** (i.e., high-level object encapsulating a
    low-level PEP-compliant union type hint, including both :pep:`484`-compliant
    :attr:`typing.Union` and :attr:`typing.Optional` unions *and*
    :pep:`604`-compliant ``|``-delimited type unions).
    '''

    #FIXME: Define __eq__() too, please!

    def branches(self) -> Iterable[TypeHint]:
        return self._hints_child_ordered

    @callable_cached
    def __le__(self, other: TypeHint) -> bool:

        # If the passed object is *NOT* a totally ordered type hint, raise an
        # exception.
        _die_unless_TypeHint(other)

        # If that hint is *NOT* a totally ordered union type hint, return false.
        if not isinstance(other, _TypeHintUnion):
            return False
        # Else, that hint is a totally ordered union type hint.

        #FIXME: O(n^2) complexity ain't that great. Perhaps that's unavoidable
        #here, though? Contemplate optimizations, please.

        # For each branch of this union...
        for self_branch in self.branches():
            # For each branch of that union...
            for other_branch in other.branches():
                # If this branch is compatible with that branch, return true.
                if self_branch <= other_branch:
                    return True

        # Else, this hint is incompatible with that hint.
        return False

    def _is_le_branch(self, branch: TypeHint) -> bool:

        #FIXME: Is this right? I have no idea.  The API could
        #probably be cleaned up a bit by:
        #* Shifting the TypeHint.__le__() method *IMPLEMENTATION* into
        #  "_TypeHintSubscripted".
        #* Decorating the TypeHint.__le__() method with @abstractmethod.
        #* Shifting the TypeHint._is_le_branch() method into
        #  "_TypeHintSubscripted".
        raise NotImplementedError('_TypeHintUnion._is_le_branch() unsupported.')

def _die_unless_TypeHint(obj: object) -> None:
    '''
    Raise an exception unless the passed object is a **totally ordered type
    hint** (i.e., :class:`TypeHint` instance).

    Parameters
    ----------
    obj : object
        Arbitrary object to be validated.

    Raises
    ----------
    BeartypeMathException
        If this object is *not* a totally ordered type hint.
    '''

    # If this object is *NOT* a totally ordered type hint, raise an exception.
    if not isinstance(obj, TypeHint):
        raise BeartypeMathException(
            f'{repr(obj)} not totally ordered type hint
            f'(i.e., "beartype.math.TypeHint" instance).'
        )

_HINT_SIGNS_ORIGIN_ISINSTANCEABLE_ARGS_1 = frozenset((
    HintSignAbstractSet,
    HintSignAsyncContextManager,
    HintSignAsyncIterable,
    HintSignAsyncIterator,
    HintSignAwaitable,
    HintSignByteString,
    HintSignCollection,
    HintSignContainer,
    HintSignContextManager,
    HintSignCounter,
    HintSignDeque,
    HintSignFrozenSet,
    HintSignItemsView,
    HintSignIterable,
    HintSignIterator,
    HintSignKeysView,
    HintSignList,
    HintSignMatch,
    HintSignMutableSequence,
    HintSignMutableSet,
    HintSignPattern,
    HintSignSequence,
    HintSignSet,
    HintSignType,
    HintSignValuesView,
))
'''
Frozen set of all signs uniquely identifying **single-argument PEP-compliant
type hints** (i.e., type hints subscriptable by only one child type hint)
originating from an **isinstanceable origin type** (i.e., isinstanceable class
such that *all* objects satisfying this hint are instances of this class).
'''

# Initialized below by the _init() function.
_HINT_SIGN_TO_TypeHint = {}
'''
Dictionary mapping from each sign uniquely identifying PEP-compliant type hints
to the :class:`TypeHint` subclass handling those hints.
'''

def _init() -> None:
    '''
    Initialize this submodule.
    '''

    # Fully initialize the "_HINT_SIGN_TO_TypeHint" dictionary declared above.
    for hint_sign in _HINT_SIGNS_ORIGIN_ISINSTANCEABLE_ARGS_1:
        _HINT_SIGN_TO_TypeHint[hint_sign] = _TypeHintOriginIsinstanceableArgs1
    for hint_sign in HINT_SIGNS_UNION:
        _HINT_SIGN_TO_TypeHint[hint_sign] = _TypeHintUnion

# Initialize this submodule.
_init()

Cogito ergo sum. Completely untested – but confident of worky. Humanity, you're welcome!
@tlambert03: Would you mind doctoring that up a bit, sprinkling in a few unit tests, and submitting a mostly working PR? If so, we can get this typing party started. If not, I'll still eventually get this typing party started.
I can absolutely run with this and submit a PR with tests.  This start would have taken me a long time!  Still need to wrap my head around it, but this gives me some golden honey to work with 🍯

Ergo, I did this for humanity and Harvard:

I can't speak for Harvard, but all of humanity thanks you ;)
more soon!

Last-minute edit for great glory. The ABC design above was a bit ad-hoc, which always happens when you're blasting out 500 lines of spaghetti after a lukewarm bath. Allow me to politely tighten that up for the crowd following along at home:
# In the "beartype.roar._roarexc" submodule:
class BeartypeMathException(BeartypeException):
    '''
    Abstract base class of all **beartype math exceptions.**

    Instances of subclasses of this exception are raised at call time from the
    callables and classes published by the :func:`beartype.math` subpackage.
    '''

    pass

# In the "beartype.math.__init__" submodule:
from beartype.math._mathcls import TypeHint

# In the "beartype.math._mathcls" submodule:
from abc import ABC, abstractmethod
from beartype.roar import BeartypeMathException
from beartype.typing import (
    Iterable,
)
from beartype._data.hint.pep.sign.datapepsigns import (
    HintSignAbstractSet,
    HintSignAsyncContextManager,
    HintSignAsyncIterable,
    HintSignAsyncIterator,
    HintSignAwaitable,
    HintSignByteString,
    HintSignCollection,
    HintSignContainer,
    HintSignContextManager,
    HintSignCounter,
    HintSignDeque,
    HintSignFrozenSet,
    HintSignItemsView,
    HintSignIterable,
    HintSignIterator,
    HintSignKeysView,
    HintSignList,
    HintSignMatch,
    HintSignMutableSequence,
    HintSignMutableSet,
    HintSignPattern,
    HintSignSequence,
    HintSignSet,
    HintSignType,
    HintSignValuesView,
)
from beartype._data.hint.pep.sign.datapepsignset import (
    HINT_SIGNS_UNION,
)
from beartype._util.cache.utilcachecall import callable_cached
from beartype._util.hint.pep.utilpepget import (
    get_hint_pep_args,
    get_hint_pep_origin,
    get_hint_pep_sign,
)
from functools import total_ordering

#FIXME: Unit test us up, please!
@total_ordering
class TypeHint(ABC):
    '''
    Abstract base class (ABC) of all **totally ordered type hint** (i.e.,
    high-level object encapsulating a low-level type hint augmented with all
    rich comparison ordering methods).

    Instances of this class are totally ordered with respect to one another.
    Equivalently, instances of this class support all binary comparators (i.e.,
    ``==``, ``!=``, ``<``, ``<=``, ``>``, and ``>=``) according such that for
    any three instances ``a``, ``b`, and ``c`` of this class:

    * ``a ≤ a`` (i.e., reflexivity).
    * If ``a ≤ b`` and ``b ≤ c``, then ``a ≤ c`` (i.e., transitivity).
    * If ``a ≤ b`` and ``b ≤ a``, then ``a == b`` (i.e., antisymmetry).
    * Either ``a ≤ b`` or ``b ≤ a`` (i.e., totality).

    Instances of this class are thus usable in algorithms and data structures
    requiring a total ordering across their input.

    Attributes
    ----------
    _hints_child_unordered : tuple[object]
        Tuple of all low-level unordered children type hints of the low-level
        unordered parent type hint passed to the :meth:`__init__` method.
    _hints_child_ordered : tuple[TypeHint]
        Tuple of all high-level totally ordered children type hints of this
        high-level totally ordered parent type hint.
    '''

    def __new__(cls, hint: object) -> 'TypeHint':
        '''
        Factory constructor magically instantiating and returning an instance of
        the private concrete subclass of this public abstract base class (ABC)
        appropriate for handling the passed low-level unordered type hint.

        Parameters
        ----------
        hint : object
            Lower-level unordered type hint to be encapsulated by this
            higher-level totally ordered type hint.

        Returns
        ----------
        TypeHint
           Higher-level totally ordered type hint encapsulating that hint.

        Raises
        ----------
        BeartypeMathException
            If this class does *not* currently support the passed hint.
        BeartypeDecorHintPepSignException
            If the passed hint is *not* actually a PEP-compliant type hint.
        '''

        # Sign uniquely identifying this hint if any *OR* raise an exception
        # (i.e., if this hint is *NOT* actually a PEP-compliant type hint).
        hint_sign = get_hint_pep_sign(hint)

        # Private concrete subclass of this ABC handling this hint if any *OR*
        # "None" otherwise (i.e., if no such subclass has been authored yet).
        TypeHintSubclass = _HINT_SIGN_TO_TypeHint.get(hint_sign)

        # If this hint appears to be currently unsupported...
        if TypeHintSubclass is None:
            # If this hint is a type, defer to the subclass handling types.
            if isinstance(hint, type):
                TypeHintSubclass = _TypeHintClass
            # Else, this hint is *NOT* a type. Ergo, this hint is unsupported.
            # In this case, raise an exception.
            else:
                raise BeartypeMathException(
                    f'Type hint {repr(hint)} currently unsupported by '
                    f'class "beartype.math.TypeHint".'
                )
        # Else, this hint is supported.

        # Return this subclass.
        return super().__new__(TypeHintSubclass)

    def __init__(self, hint: object) -> None:
        '''
        Initialize this high-level totally ordered type hint against the passed
        low-level unordered type hint.

        Parameters
        ----------
        hint : object
            Lower-level unordered type hint to be encapsulated by this
            higher-level totally ordered type hint.
        '''

        # Classify all passed parameters. Note that this type hint is guaranteed
        # to be a type hint by validation performed by the __new__() method.
        self._hint = hint

        # Tuple of all low-level unordered child type hints of this hint.
        self._hints_child_unordered = get_hint_pep_args(hint)

        # Tuple of all high-level totally ordered child type hints of this hint.
        self._hints_child_ordered = tuple(
            TypeHint(hint_child_unordered)
            for hint_child_unordered in self._hints_child_unordered
        )

    #FIXME: Implement us up, please! The implementation should probably resemble
    #that of the concrete __le__() methods defined below. *phew*
    #FIXME: Docstring us up, please!
    @abstractmethod
    def __eq__(self, other: 'TypeHint') -> bool: pass

    @abstractmethod
    def __le__(self, other: 'TypeHint') -> bool:
        '''
        ``True`` only if this totally ordered type hint is **compatible** with
        the passed totally ordered type hint, where compatibility implies that
        the unordered type hint encapsulated by this totally ordered type hint
        may be losslessly replaced by the unordered type hint encapsulated by
        the parent totally ordered type hint *without* breaking backward
        compatibility in APIs annotated by the former.

        This method is memoized and thus enjoys ``O(1)`` amortized worst-case
        time complexity across all calls to this method.
        '''

        pass

    @property
    @abstractmethod
    def branches(self) -> Iterable['TypeHint']:
        '''
        Immutable iterable of all **branches** (i.e., high-level totally ordered
        type hints encapsulating all low-level unordered child type hints
        subscripting (indexing) the low-level unordered parent type hint
        encapsulated by this high-level totally ordered parent type hint if this
        is a union (and thus an instance of the :class:`_TypeHintUnion`
        subclass) *or* the 1-tuple containing only this instance itself
        otherwise) of this totally ordered parent type hint.

        This property enables the child type hints of :pep:`484`- and
        :pep:`604`-compliant unions (e.g., :attr:`typing.Union`,
        :attr:`typing.Optional`, and ``|``-delimited type objects) to be handled
        transparently *without* special cases in subclass implementations.
        '''

        pass

class _TypeHintNonunion(TypeHint):
    '''
    **Totally ordered non-union type hint** (i.e., high-level object
    encapsulating any low-level parent type hint *other* than a :pep:`484`- or
    :pep:`604`-compliant type hint).
    '''

    @property
    def branches(self) -> Iterable[TypeHint]:

        # Default to returning the 1-tuple containing only this instance, as
        # *ALL* subclasses except "_HintTypeUnion" require this default.
        return (self,)

    @callable_cached
    def __le__(self, other: TypeHint) -> bool:
        '''
        ``True`` only if this totally ordered type hint is **compatible** with
        the passed totally ordered type hint, where compatibility implies that
        the unordered type hint encapsulated by this totally ordered type hint
        may be losslessly replaced by the unordered type hint encapsulated by
        the parent totally ordered type hint *without* breaking backward
        compatibility in APIs annotated by the former.

        This method is memoized and thus enjoys ``O(1)`` amortized worst-case
        time complexity across all calls to this method.
        '''

        # If the passed object is *NOT* a totally ordered type hint, raise an
        # exception.
        _die_unless_TypeHint(other)
        # Else, that object is a totally ordered type hint.

        # For each branch of the passed union if that hint is a union *OR* that
        # hint as is otherwise...
        for branch in other.branches:
            # If this hint is compatible with that branch, return true.
            if self._is_le_branch(branch):
                return True
            # Else, this hint is incompatible with that branch. In this case,
            # silently continue to the next branch.

        # Else, this hint is incompatible with that hint.
        return False

    @abstractmethod
    def _is_le_branch(self, branch: TypeHint) -> bool:
        '''
        ``True`` only if this totally ordered type hint is **compatible** with
        the passed branch of another totally ordered type hint passed to the
        parent call of the :meth:`__le__` dunder method.

        See Also
        ----------
        :meth:`__le__`
            Further details.
        '''

        pass

class _TypeHintClass(_TypeHintNonunion):
    '''
    **Totally ordered class type hint** (i.e., high-level object encapsulating a
    low-level PEP-compliant type hint that is, in fact, a simple class).
    '''

    #FIXME: Define __eq__() too, please!

    def _is_le_branch(self, branch: TypeHint) -> bool:

        #FIXME: Insufficient. This should also support comparison of a
        #class against a union (i.e., "if isinstance(branch, _TypeHintUnion)").
        #We leave this as an exercise for the perspicacious reader. :p
        # Return true only if...
        return (
            # That branch is also a totally ordered class type hint *AND*...
            isinstance(branch, _TypeHintClass) and
            issubclass(
                # The low-level unordered type hint encapsulated by this
                # high-level totally ordered type hint is a subclass of...
                self._hint,
                # The low-level unordered type hint encapsulated by that
                # branch...
                branch._hint
            )
        )

class _TypeHintOriginIsinstanceableArgs1(_TypeHintNonunion):
    '''
    **Totally ordered single-argument isinstanceable type hint** (i.e.,
    high-level object encapsulating a low-level PEP-compliant type hint
    subscriptable by only one child type hint originating from an
    isinstanceable class such that *all* objects satisfying that hint are
    instances of that class).
    '''

    #FIXME: Define __eq__() too, please!

    def _is_le_branch(self, branch: TypeHint) -> bool:

        # Return true only if...
        return (
            # That branch is also a totally ordered single-argument
            # isinstanceable type hint *AND*...
            isinstance(branch, _TypeHintOriginIsinstanceableArgs1) and
            issubclass(
                # The issubclassable class underlying the low-level
                # unordered type hint encapsulated by this
                # high-level totally ordered type hint is a subclass of...
                get_hint_pep_origin(self._hint),
                # The issubclassable class underlying the low-level
                # unordered type hint encapsulated by that branch...
                get_hint_pep_origin(branch._hint)
            ) and
            # The high-level totally ordered child type hint subscripted by this
            # high-level totally ordered parent type hint is "compatible" with
            # the high-level totally ordered child type hint subscripted by that
            # high-level totally ordered parent type hint.
            self._hints_child_ordered[0] <= branch._hints_child_ordered[0]
        )

class _TypeHintUnion(TypeHint):
    '''
    **Totally ordered union type hint** (i.e., high-level object encapsulating a
    low-level PEP-compliant union type hint, including both :pep:`484`-compliant
    :attr:`typing.Union` and :attr:`typing.Optional` unions *and*
    :pep:`604`-compliant ``|``-delimited type unions).
    '''

    #FIXME: Define __eq__() too, please!

    @property
    def branches(self) -> Iterable[TypeHint]:
        return self._hints_child_ordered

    @callable_cached
    def __le__(self, other: TypeHint) -> bool:

        # If the passed object is *NOT* a totally ordered type hint, raise an
        # exception.
        _die_unless_TypeHint(other)

        # If that hint is *NOT* a totally ordered union type hint, return false.
        if not isinstance(other, _TypeHintUnion):
            return False
        # Else, that hint is a totally ordered union type hint.

        #FIXME: O(n**2) complexity ain't that great. Perhaps that's unavoidable
        #here, though? Contemplate up a few optimizations, please.

        # For each branch of this union...
        for self_branch in self.branches:
            # For each branch of that union...
            for other_branch in other.branches:
                # If this branch is compatible with that branch, return true.
                if self_branch <= other_branch:
                    return True

        # Else, this hint is incompatible with that hint.
        return False

def _die_unless_TypeHint(obj: object) -> None:
    '''
    Raise an exception unless the passed object is a **totally ordered type
    hint** (i.e., :class:`TypeHint` instance).

    Parameters
    ----------
    obj : object
        Arbitrary object to be validated.

    Raises
    ----------
    BeartypeMathException
        If this object is *not* a totally ordered type hint.
    '''

    # If this object is *NOT* a totally ordered type hint, raise an exception.
    if not isinstance(obj, TypeHint):
        raise BeartypeMathException(
            f'{repr(obj)} not totally ordered type hint '
            f'(i.e., "beartype.math.TypeHint" instance).'
        )

_HINT_SIGNS_ORIGIN_ISINSTANCEABLE_ARGS_1 = frozenset((
    HintSignAbstractSet,
    HintSignAsyncContextManager,
    HintSignAsyncIterable,
    HintSignAsyncIterator,
    HintSignAwaitable,
    HintSignByteString,
    HintSignCollection,
    HintSignContainer,
    HintSignContextManager,
    HintSignCounter,
    HintSignDeque,
    HintSignFrozenSet,
    HintSignItemsView,
    HintSignIterable,
    HintSignIterator,
    HintSignKeysView,
    HintSignList,
    HintSignMatch,
    HintSignMutableSequence,
    HintSignMutableSet,
    HintSignPattern,
    HintSignSequence,
    HintSignSet,
    HintSignType,
    HintSignValuesView,
))
'''
Frozen set of all signs uniquely identifying **single-argument PEP-compliant
type hints** (i.e., type hints subscriptable by only one child type hint)
originating from an **isinstanceable origin type** (i.e., isinstanceable class
such that *all* objects satisfying this hint are instances of this class).
'''

# Initialized below by the _init() function.
_HINT_SIGN_TO_TypeHint = {}
'''
Dictionary mapping from each sign uniquely identifying PEP-compliant type hints
to the :class:`TypeHint` subclass handling those hints.
'''

def _init() -> None:
    '''
    Initialize this submodule.
    '''

    # Fully initialize the "_HINT_SIGN_TO_TypeHint" dictionary declared above.
    for hint_sign in _HINT_SIGNS_ORIGIN_ISINSTANCEABLE_ARGS_1:
        _HINT_SIGN_TO_TypeHint[hint_sign] = _TypeHintOriginIsinstanceableArgs1
    for hint_sign in HINT_SIGNS_UNION:
        _HINT_SIGN_TO_TypeHint[hint_sign] = _TypeHintUnion

# Initialize this submodule.
_init()

Feelin' good about that. No more last-minute edits, I solemnly swear on my sacred honour as a GitHub techbro. Let the good typing times roll, everyone! :bowling:
What We Actually Did Is This
Oh – and here's how to actually use that API. Currently, the above implementation explicitly supports:

PEP 604-style unions.
typing.Optional.
typing.Union.
typing.AbstractSet.
typing.AsyncContextManager.
typing.AsyncIterable.
typing.AsyncIterator.
typing.Awaitable.
typing.ByteString.
typing.Collection.
typing.Container.
typing.ContextManager.
typing.Counter.
typing.Deque.
typing.FrozenSet.
typing.ItemsView.
typing.Iterable.
typing.Iterator.
typing.KeysView.
typing.List.
typing.Match.
typing.MutableSequence.
typing.MutableSet.
typing.Pattern.
typing.Sequence.
typing.Set.
typing.Type.
typing.ValuesView.

Not too shabby for a first-draft off-the-cuff back-of-the-envelope hack job. Right? Right?
Okay. So, the public beartype.math.TypeHint class defines a total ordering over the set of all PEP-compliant type hints according to the relation of "type hint compatibility," which we just made up. Nobody's formalized that with a standard yet, but... let's pretend this is formally rigorous and that we actually know what we're doing. Here's how you'd use beartype.math.TypeHint to decide subtype compatibility for various example type hints:
>>> from beartype.math import TypeHint
>>> from beartype.typing import Sequence, Union
>>> TypeHint(list[str]) <= TypeHint(Sequence[str])
True
>>> TypeHint(list[str]) <= TypeHint(Union[Sequence[str], int])
True
>>> TypeHint(str | list | int) <= TypeHint(str | list | int | bool)
True
>>> TypeHint(Sequence[str]) <= TypeHint(list[str])
False

More to come... as you define it for us! Please do run with this if you find a spare weekend lying around anywhere. Type hint arithmetic is fun, everybody. :man_teacher:

awesome, thanks as always!  Didn't see this before I started on #136, but will have a look at the diff and incorporate changes this weekend.  The pattern seems to be working nicely! 👍

Resolved by 7809ea2. Can't believe you did this, @tlambert03 – but you did. Now all peoples across Planet Earth hail and praise you.


Fixing broken links and translation errors

Pulling out some broken links in the text and fixing the translation (pt-br).

[x] I have read freeCodeCamp's contribution guidelines.
[x] My pull request has a descriptive title (not a vague title like Update index.md)
[x] My pull request targets the master branch of freeCodeCamp.
[x] None of my changes are plagiarized from another source without proper attribution.
[x] My article does not contain shortened URLs or affiliate links.

If your pull request closes a GitHub issue, replace the XXXXX below with the issue number.
Closes #XXXXX

Closed and Reopened this PR to attempt to resolve a specific Travis build failure.

Thank you for your contribution to the page! 👍
We're happy to accept these changes, and look forward to future contributions. 🎉


fix(charts): set blockHistoryLength back to 100

:tada: This PR is included in version 1.2.1 :tada:
The release is available on GitHub release
Your semantic-release bot :package::rocket:


Switching to GM-xcode and newest PM-version in Linux builds

even of they are always failing...

Current coverage is 75.00% (diff: 95.65%)

No coverage report found for Development at ea553c8.

Powered by Codecov. Last update ea553c8...d10284f


[Paloma] Add a section of Paloma website with Logos from Partners building with Paloma

Closed as not needed right now.


No Loading

[13-12-2015 15:36] Error downloading stash for Standard, exception details: System.Net.WebException: The remote server returned an error: (500) Internal Server Error.
at System.Net.HttpWebRequest.GetResponse()
at POEApi.Transport.HttpTransport.GetStash(Int32 index, String league, Boolean refresh)
at POEApi.Transport.CachedTransport.GetStash(Int32 index, String league, Boolean refresh)
at POEApi.Model.POEModel.GetStash(Int32 index, String league, Boolean forceRefresh)
at POEApi.Model.POEModel.GetStash(String league, String accountName)
[13-12-2015 15:36] System.Exception: Downloading stash for Standard, details logged to DebugInfo.log, please open a ticket at https://github.com/Stickymaddness/Procurement/issues
at POEApi.Model.POEModel.GetStash(String league, String accountName)
at Procurement.ViewModel.LoginWindowViewModel.LoadStashItems(Character character)
at Procurement.ViewModel.LoginWindowViewModel.d__6.MoveNext()
at System.Collections.Generic.List1..ctor(IEnumerable1 collection)
at System.Linq.Enumerable.ToList[TSource](IEnumerable`1 source)
at Procurement.ViewModel.LoginWindowViewModel.<>c__DisplayClass2.b__1()
at System.Threading.Tasks.Task.Execute()

I have the same issue, it appears the GGG server is having issues current or they are actively blocking Procurement.

Cancel that, they have changed something.
I'll release a fix as soon as possible.

Please see https://github.com/Stickymaddness/Procurement/issues/284 for progress updates


Is there like a chain combinator?

I want to use a combinator like chain, but does this library have such a function?
https://github.com/jneen/parsimmon/blob/master/API.md#parserchainnewparserfunc
If there is another way, please let me know.

Hey! Sorry for the late reply. I recently updated the library. I did add a combinator like that - thenPick. Hope it's as you wanted it.

Thanks!!! I'll try using it.


Configure Open Graph metadata to work for Twitter, Slack, Facebook and LinkedIn

Is easier to do after #78


Silee2/relative dlopen

Since this was a single line change it was easier to simply copy the line to the branch rather than resolve the merge conflicts.