[Feature Request] New beartype.math API for performing type hint arithmetic

[leycec]

Discussed in #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!

[leycec]

Fascinating. Something spicey resembling beartype.is_subtype() is totally in @beartype's wheelhouse. Sadly, as you surmise, @beartype currently lacks a public API for testing type hint compatibility via (super|sub)set theoretic operators like ⊆ and ⊂ implemented through Python's builtin in operator – mostly because you're the first fearless bear-bro to ever request this.

my goal here would be to detect if an API breakage has occurred between two versions:

Yes! Thanks for that perfect use case as well. The real-world applicability is clear. If you've typed an existing callable as returning a type hint A, can you safely re-type that same callable as returning a type hint B while preserving backward compatibility? Equivalently, in set theoretic notation, is A ⊆ B?

So let's suppose we define this fun new beartype.is_subtype() API as we eventually should. I'm envisioning that function mostly being called interactively from Python REPLs like IPython3 or Jupyter Notebook. Is that right? Okay. So...

Let's Just Pretend Type Hints Are Sets, Guys

Scarce volunteer resources rears its ugly mullet cut yet again. Briefly inspecting the pytypes.is_subtype() tester suggests this problem domain to be really, really non-trivial. That's probably the most significant blocker here.

It sort of makes sense this would be the NP-hard of type hints, right? After all, type hints aren't sets. They're type hints. There's nothing innately set-like about type hints. So, attempting to coerce type hints into sets for the purpose of deciding superset and subset containment relations between otherwise unrelated type hints rapidly descends into some fairly intense academic theory-crafting.

Of course, we're all for theory-crafting here. @beartype is already built on a flimsy foundation of hand-waving, wishful thinking, and helpful assumptions that mostly hold up until you squint at them. Still... pytypes is dead. I can't help but think that part of the reason pytypes died is exactly this: pytypes authors devoted a shocking slice of their scarce time to grotesquely NP-hard-like problems that most of their userbase didn't particularly care about.

Let's not throw ourselves like disgruntled lemmings into that same hole. 🕳️

So What Are You Saying Here, @leycec?

Welp... I'm kinda sayin' this may never happen. I mean, I really hope it does! But it's a surprisingly hardcore feature that would strongly benefit from funding sponsorship of some sort. Lucrative grant funding agencies across the industrial world: make this happen for all humanity, please.

Let's see what the unruly rabble says. Does anyone else really want this too – or can I glibly pretend this never happened and devote myself to other h0t ticket dumpster fires that are currently on fire?

[leycec]

_{Originally posted by @tlambert03 May 31, 2022}

lolll ... I commend your honesty 😂

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!

[leycec]

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:

1. 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.
2. 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):
    # Apparently, we have to explicitly declare this
    # dunder method or Python obliquely complains:
    #     TypeError: Protocols with non-method members don't support issubclass()
    def __hash__(self): 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! You're darn 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. 😮

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. You just know something's gonna blow that trivial algorithm up hard. But until that happens, let's choose to believe in the miraculous healing power of Python's issubclass() builtin. 😁

[tlambert03]

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).

You just know something's gonna blow that trivial algorithm up hard.

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 😂

thanks again!

[leycec]

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. 🤗

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. This is a darkly lit road that none dare tread. And I was born and raised in Los Angeles. I know everything about darkly lit roads that none dare tread.

[tlambert03]

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 (note to self)

[leycec]

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. My brain hurts. 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. But your brave assistance would be welcome beyond all belief.

[tlambert03]

holy shit man.

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!

[leycec]

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

        #FIXME: Insufficient. This should also handle unsubscripted type hints
        #(e.g., "typing.List", "typing.AbstractSet"). PEP 484 specifies that such
        #hints are semantically equivalent to the equivalent type hints
        #subscripted by the "object" superclass. Ergo, we should expand here:
        #* "typing.List" as if it were "typing.List[object]".
        #* "typing.AbstractSet" as if it were "typing.AbstractSet[object]".

        # 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! 🎳

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. 👨‍🏫

[tlambert03]

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! 👍

[leycec]

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

[tlambert03]

you're too generous @leycec 😂 it was your pattern too! it was a pleasure working with you, thanks for the help!