Is it possible to type a list of tuples of identical generic types, with a static type checker?

Consider the following:

from typing import TypeVar, Generic

class A(): pass
class B(A): pass
class C(A): pass


T = TypeVar("T", bound=A)


class Container(Generic[T]):
    def __init__(x: T):
        pass

b: Container[B] = Container(B())
c: Container[C] = Container(C())

How do I type-hint a function foo that will accept any list of tuples of identically typed containers:

foo([
    (b, b), 
    (c, c)
    ])

but refuse this (heterogeneous tuple):

foo([
    (c, b),  # tuples elements are not the same type
    (c, c)
    ])

I tried this:

ListOfSameContainerTuples = list[tuple[Container[T], Container[T]]]

def foo(containers: ListOfSameContainerTuples[T]):
    pass

but it doesn't work:

foo([
    (b, b), 
    (c, c)
    ])  
# error: Argument 1 to "foo" has incompatible type "list[tuple[object, object]]"; 
# expected "list[tuple[Container[<nothing>], Container[<nothing>]]]"  [arg-type]

foo([
    (c, b), 
    (c, c)
    ])
# error: List item 0 has incompatible type "tuple[Container[C], Container[B]]"; expected "tuple[Container[C], Container[C]]"  [list-item]

The second error on mypy looks good, but I don't understand the first one:

Why does mypy not know the type of b and c ?
Why is my type signature Container[<nothing>] ?

I tried solutions from Tuple with multiple numbers of arbitrary but equal type, to no avail.

Solution

As a partial solution*, you can make the TypeVar T covariant:

T = TypeVar("T", bound=A, covariant=True)

Then

foo([(b, b), (c, c)])

passes type checking with mypy --strict while

foo([(c, b), (c, c)])

fails with the message

error: Cannot infer type argument 1 of "foo"

^*This works since when T is covariant, the type tuple[Container[A], Container[A]] is considered to be a supertype of both tuple[Container[B], Container[B]] and tuple[Container[C], Container[C]]. Prior to making T covariant, you type checker infered the expression

[(b, b), (c, c)]

as having type tuple[object, object], because object was the only supertype common to both tuple[Container[B], Container[B]] and tuple[Container[C], Container[C]]. After making T covariant, that expression can instead be inferred as having type tuple[Container[A], Container[A]], which can bind with the parameter signature of foo by taking T=A.

The reason the mixed type case fails is a little more complicated, and still has some holes for mistakes. After making T covariant, your type checker infers the expression

(c, b), (c, c)

as having type

list[tuple[Container[C], Container[A]]]

This can't bind with the first parameter of foo, because even though Container[A] is a supertype of Container[C], tuple[Container[A], Container[A]] is not tuple[Container[C], Container[A]]. You're type checker can't simply take T=A and call it a day as before.

The only way that call to foo passes type checking is if your type checker infers the type of the argument to be a list of homogeneous tuples, be it tuple[Container[A], Container[A]] or something more specific like tuple[Container[B], Container[B]] or tuple[Container[C], Container[C]]

Unfortunately, this approach relies your type checker picking a specific and heterogeneous-tuple type in order for the mixed arguments case to fail type checking. This could be problem, since if you construct a sufficiently varied argument list, it is possible that your type checker will not infer a specific heterogeneous-tuple type and instead will find tuple[Container[A], Container[A]] to be the most specific supertype.

For example, the expression

[(c, b), (b, c)]

will be inferred as having type

list[tuple[Container[A], Container[A]]]

so this argument would pass type checking if passed to foo.

TL;DR: when T = TypeVar("T", bound=A), the code

reveal_type([(b, b), (b, b)])
reveal_type([(b, b), (c, c)])
reveal_type([(c, b), (c, c)])
reveal_type([(c, b), (b, c)])

will produce the mypy output

Revealed type is "builtins.list[Tuple[Container[B], tmp.Container[tmp.B]]]"
Revealed type is "builtins.list[Tuple[builtins.object, builtins.object]]"
Revealed type is "builtins.list[Tuple[Container[C], builtins.object]]"
Revealed type is "builtins.list[Tuple[builtins.object, builtins.object]]"

But when TypeVar("T", bound=A, covariant=True), it will produce the mypy output

Revealed type is "builtins.list[Tuple[Container[B], Container[B]]]"
Revealed type is "builtins.list[Tuple[Container[A], Container[A]]]"
Revealed type is "builtins.list[Tuple[Container[C], Container[A]]]"
Revealed type is "builtins.list[Tuple[Container[A], Container[A]]]"

Type checking will pass whenever the argument to foo is inferred to have a type of the form list[tuple[Container[T], Container[T]]] for a single substituted type T. Making T covariant makes that True for the example in the question (line #2, good!), but also makes it true for the maximally mixed case (line #4, bad!).