List concatenation problems with type context and different operand item types

[whoiscc]

Here is a reproduction snippet:

from typing import List, Sequence, cast


class A:
    pass


class B1(A):
    pass


class B2(A):
    pass


# ok
list1: List[A] = [A()] * 10
# ok
list2: List[A] = [B1()] * 10
list2 += [B2()] * 10
# error!
list3: List[A] = [B1()] * 10 + [B2()] * 10
# error!
seq3: Sequence[A] = [B1()] * 10 + [B2()] * 10

# ok, but looks weird
list4: List[A] = [cast(A, B1())] * 10 + [B2()] * 10

Error report looks like this:

test.py:22: error: Incompatible types in assignment (expression has type "List[B1]", variable has type "List[A]")
test.py:22: error: List item 0 has incompatible type "B2"; expected "B1"
test.py:24: error: List item 0 has incompatible type "B2"; expected "B1"

The covariance of Sequence helps eliminate the first error. But I can never add two lists of objects of different classes without existing annotation, even the classes have same base.

In my opinion, cast takes place when downcasting is necessary. So it should not be used in this way.

[ilevkivskyi]

I think this is a consequence of how list.__add__ is typed in typeshed. I am however not sure what would be a better signature.

[JelleZijlstra]

python/typeshed#2404 fixes this.

[JukkaL]

(This comment is copied from #5778, which is a duplicate issue.)

Code like this doesn't type check correctly (Python 2 example):

from typing import List, Optional
result = range(10) + [None]  # type: List[Optional[int]]

It generates these errors:

t.py:2: error: Incompatible types in assignment (expression has type "List[int]", variable has type "List[Optional[int]]")
t.py:2: error: List item 0 has incompatible type "None"; expected "int"

Issues like these seem somewhat frequent. There are also similar examples in the mypy codebase.

The errors have two causes:

1. list concatenation cannot vary the return type based on context
2. the types of the list items must match in concatenation.

A quick way to fix this particular example would be to change the signature of list.__add__ to something like this:

class list(Generic[_T]):
    ...
    def __add__(self, x: List[_S]) -> List[Union[_T, _S]]: ...
    ...

This signature might cause other problems, though. This wouldn't solve the problem in general. For example, if the annotation would say # type: List[Union[int, str, None]] the error would persist, even though the code would be safe.

With some type system extensions we could fix this more generally. We'd need type variable lower bounds (we currently only have upper bounds), and to allow type variable bounds to refer to other type variables. I think that this would be a good signature:

T = TypeVar('T')
S = TypeVar('S')
U = TypeVar('U', lower_bound=Union[T, S])

class list(Generic[T]):
    def __add__(self, other: List[S]) -> List[U]: ...

Implementing this could be difficult.

Instead, we could special case list.__add__ in the type checker, since it's a very common operation. This would be ugly and potentially confusing, since the effective signature wouldn't match typeshed.

[JukkaL]

Increasing priority to high since we have several independent sightings of this issue.