Incorrect type inference with `__radd__` with subclass of `tuple[int, ...]`

[randolf-scholz]

Bug Report

mypy generally correctly prioritizes __radd__ if the right operand is a subtype of the left operand. However, I discovered that it can fail to do so when creating a subclass of tuple[int, ...].

To Reproduce

• https://mypy-play.net/?mypy=1.15.0&python=3.12&gist=720172b4776456220b93a7d4ab4af4db
• https://mypy-play.net/?mypy=1.15.0&python=3.12&gist=df9688d48ce1cea13d8bdd55b9ee1471&enable-incomplete-feature=PreciseTupleTypes

from typing import assert_type

class Size(tuple[int, ...]):
    def __add__(self, other: tuple[int, ...], /) -> "Size": return Size()  # type: ignore[override]
    def __radd__(self, other: tuple[int, ...], /) -> "Size": return Size()

tup0: tuple[()] = ()
tup1: tuple[int] = (1,)
tup2: tuple[int, int] = (1, 2)
tupN: tuple[int, ...] = (1, 2, 3)
size: Size = Size([3, 4])

# __radd__
assert_type(tup0 + tupN, tuple[int, ...])  # ✅
assert_type(tup1 + tupN, tuple[int, ...])  # ✅
assert_type(tup2 + tupN, tuple[int, ...])  # ✅
assert_type(tupN + tupN, tuple[int, ...])  # ✅
assert_type(tup0 + size, Size)  # ❌ False positive
assert_type(tup1 + size, Size)  # ❌ False positive
assert_type(tup2 + size, Size)  # ❌ False positive
assert_type(tupN + size, Size)  # ✅

The bug does seem to be tuple-specific, for instance it does not appear with integer literals: https://mypy-play.net/?mypy=latest&python=3.12&gist=da0763e25cd0654d1a8b8b0b67291bc5

Expected Behavior

All assert_type in the example above should succeed.

[sterliakov]

Ohh, this is interesting! tuple.__{r,}add__ methods are special-cased to handle their sizes and non-homogeneous item types. There must be something missing in fallback handling here:

mypy/mypy/checkexpr.py

Lines 3487 to 3516 in c724a6a

	if isinstance(proper_left_type, TupleType) and e.op == "+":
	left_add_method = proper_left_type.partial_fallback.type.get("__add__")
	if left_add_method and left_add_method.fullname == "builtins.tuple.__add__":
	proper_right_type = get_proper_type(self.accept(e.right))
	if isinstance(proper_right_type, TupleType):
	right_radd_method = proper_right_type.partial_fallback.type.get("__radd__")
	if right_radd_method is None:
	# One cannot have two variadic items in the same tuple.
	if (
	find_unpack_in_list(proper_left_type.items) is None
	or find_unpack_in_list(proper_right_type.items) is None
	):
	return self.concat_tuples(proper_left_type, proper_right_type)
	elif (
	PRECISE_TUPLE_TYPES in self.chk.options.enable_incomplete_feature
	and isinstance(proper_right_type, Instance)
	and self.chk.type_is_iterable(proper_right_type)
	):
	# Handle tuple[X, Y] + tuple[Z, ...] = tuple[X, Y, *tuple[Z, ...]].
	right_radd_method = proper_right_type.type.get("__radd__")
	if (
	right_radd_method is None
	and proper_left_type.partial_fallback.type.fullname == "builtins.tuple"
	and find_unpack_in_list(proper_left_type.items) is None
	):
	item_type = self.chk.iterable_item_type(proper_right_type, e)
	mapped = self.chk.named_generic_type("builtins.tuple", [item_type])
	return proper_left_type.copy_modified(
	items=proper_left_type.items + [UnpackType(mapped)]
	)

[randolf-scholz]

@sterliakov I stepped through this example with the debugger:

from typing import assert_type

class Size(tuple[int, ...]):
    def __add__(self, other: tuple[int, ...], /) -> "Size": return Size()  # type: ignore[override]
    def __radd__(self, other: tuple[int, ...], /) -> "Size": return Size()

size: Size = Size([3,4])
tup: tuple[int, ...] = (1, 2)

assert_type(tup + size, Size)  # ✅ tuple[int, ...] + Size
assert_type(() + size, Size)  # ❌ tuple[()] + Size
assert_type((1, 2) + size, Size)  # ❌ tuple[Literal[1], Literal[2]] + Size

The last two examples fail inside this branch:

mypy/mypy/subtypes.py

Lines 472 to 494 in c724a6a

	if isinstance(right, TupleType):
	if len(right.items) == 1:
	# Non-normalized Tuple type (may be left after semantic analysis
	# because semanal_typearg visitor is not a type translator).
	item = right.items[0]
	if isinstance(item, UnpackType):
	unpacked = get_proper_type(item.type)
	if isinstance(unpacked, Instance):
	return self._is_subtype(left, unpacked)
	if left.type.has_base(right.partial_fallback.type.fullname):
	if not self.proper_subtype:
	# Special cases to consider:
	# * Plain tuple[Any, ...] instance is a subtype of all tuple types.
	# * Foo[*tuple[Any, ...]] (normalized) instance is a subtype of all
	# tuples with fallback to Foo (e.g. for variadic NamedTuples).
	mapped = map_instance_to_supertype(left, right.partial_fallback.type)
	if is_erased_instance(mapped):
	if (
	mapped.type.fullname == "builtins.tuple"
	or mapped.type.has_type_var_tuple_type
	):
	return True
	return False

In both cases, mapped = map_instance_to_supertype(left, right.partial_fallback.type) yields tuple[int, ...] and then is_erased_instance(mapped) returns False.

[sterliakov]

That's correct: only tuple[Any, ...] is a subtype of all tuples including fixed-sizes one. tuple[int, ...] is not a subtype of tuple[int, int], for example (while the reverse is true - a fixed-size tuple[int, int] is a subtype of variadic tuple[int, ...]). This Any special-case is intentional (because variadic Any tuples can arise from some untyped constructs), but it does not generalize to other tuples. https://mypy-play.net/?mypy=master&python=3.12&flags=strict&gist=d60b71630f447223ac70c69f8b7d7d62

Sorry, I linked to the wrong place - that one is for cases without __radd__, so with custom __radd__ we fall back to plain self.check_op. Runtime dispatch doesn't care about tuple params, so we ignore __radd__ when we shouldn't. Maybe just allow variadic tuples explicitly when gathering candidates in check_op_reversible (or one more flag for is_subtype)?

[randolf-scholz]

Right, so it doesn't really have anything to do with tuple literals after all, I will update the OP.

[randolf-scholz]

@sterliakov To recapitulate:

mypy/mypy/checkexpr.py

Lines 4050 to 4062 in d68ea35

	elif (
	is_subtype(right_type, left_type)
	and isinstance(left_type, Instance)
	and isinstance(right_type, Instance)
	and not (
	left_type.type.alt_promote is not None
	and left_type.type.alt_promote.type is right_type.type
	)
	and lookup_definer(left_type, op_name) != lookup_definer(right_type, rev_op_name)
	):
	# When we do "A() + B()" where B is a subclass of A, we'll actually try calling
	# B's __radd__ method first, but ONLY if B explicitly defines or overrides the
	# __radd__ method.

In the specific case here, the LHS is a fixed size tuple tuple[*Ts], whereas the RHS is a variable size tuple tuple[T, ...].

So mypy checks whether is_subtype(tuple[T, ...], tuple[*Ts]); in our specific case is_subtype(tuple[int, ...], tuple[()]), which obviously fails.

However, wouldn't it make sense here to consider reinterpreting the fixed size tuple as a variable size tuple?

One could ask: Does there exist a choice of S for which tuple[*Ts] <: tuple[S, ...] and tuple[T, ...] <: tuple[S, ...]? Indeed, this is trivially true for S = object, and the minimal type that satisfies these constraints is S = T | Union[*Ts], which in our case would always be S = int, so everything checks out.

[sterliakov]

@randolf-scholz Not sure I follow, are you trying to convince me that variadic tuples should be considered subtypes of some fixed-length tuples? tuple[int, ...] might, for example, be a 3-tuple (1, 2, 3), so it cannot be a subtype of tuple[int, int] nor tuple[()]. Looking from set-oriented type theory side, no amount of upcasting and reinterpreting can make a variadic tuple subtype of a fixed tuple, the former has more elements so no bijection can exist.

By definition, tuple[T, ...] is a tuple containing zero or more elements of type T - the length is deliberately unknown. Variadic tuples are essentially sequences that happen to have class tuple, while fixed tuples are most close to product types.

If I'm not misreading, you're saying that (for some T and U) T <: U if T and U have a common supertype? That sounds wrong, consider

class A: ...
class B(A): ...
class C(A): ...

Applying your argument, does there exist a choice of S such that B <: S and C <: S? Yes, that's object and also that's A, so B <: C?

Here's a link to the spec chapter laying out tuple assignability rules: https://typing.python.org/en/latest/spec/tuples.html#type-compatibility-rules

[randolf-scholz]

Not sure I follow, are you trying to convince me that variadic tuples should be considered subtypes of some fixed-length tuples?

That was definitely not the goal 😅. The issue is that the is_subtype check is likely too strong to be compatible with runtime, so I was wondering if one could weaken this check - in the specific case of checking reverse-op applicability - in one way or another without breaking things.

Looking at the python C-source, the actual check performed is PyType_IsSubtype(Py_TYPE(right), Py_TYPE(left))) ¹, which simply checks whether type(right) in type(left).__mro__ ².

This check ignores generics, hence the suggestion above was to slightly weaken the is_subtype check³ to consider upcasting the parametrization of a generic type (e.g. from tuple[*Ts] to tuple[T | Union[*Ts], ...] in this case.) I do not think it ever makes sense to upcast the base type itself (e.g. from tuple to object.)

Footnotes

1. https://github.com/python/cpython/blob/08d7687094c6acb8c2ea1925a292a94ce1246c82/Objects/abstract.c#L919-L980 ↩

2. https://github.com/python/cpython/blob/ff4959b6b0cf6da5d2f59260a9103b31c812b0ba/Objects/typeobject.c#L2695-L2724 ↩

3. Of course only in the context of checking whether to apply the reverse op. ↩

[sterliakov]

Ough, sorry, I was missing the third footnote in your previous comment - I thought you're trying to change is_subtype behaviour for all purposes.

Yes, at runtime we have essentially an issubclass check, and it really doesn't play well with static generics. Perhaps we should replace is_subtype with covers_at_runtime to determine whether __rOP__ should be called first?

[randolf-scholz]

@sterliakov I created a draft PR, but there are still some things unclear #19046