Unexpected instantiation of expected Union type?

[msakai]

• Are you reporting a bug, or opening a feature request?

bug (or intended behavior?)

• Please insert below the code you are checking with mypy,
  or a mock-up repro if the source is private. We would appreciate
  if you try to simplify your case to a minimal repro.

from typing import cast, List, Union, TypeVar

A = TypeVar('A')
B = TypeVar('B')

def concat(xs: List[A], ys: List[B]) -> List[Union[A, B]]:
    return cast(List[Union[A, B]], xs) + cast(List[Union[A, B]], ys)

def test() -> List[Union[int, str]]:
    xs = [1, 2, 3]
    ys = ['A', 'B']
    zs = concat(xs, ys)
    reveal_type(xs)  # builtins.list[builtins.int*]
    reveal_type(ys)  # builtins.list[builtins.str*]
    reveal_type(zs)  # builtins.list[Union[builtins.int*, builtins.str*]]
    #return zs  # OK
    return concat(xs, ys)  # NG
    # union_fragile.py:17: error: Argument 1 to "concat" has incompatible type "List[int]"; expected "List[Union[int, str]]"
    # union_fragile.py:17: note: "List" is invariant -- see http://mypy.readthedocs.io/en/latest/common_issues.html#variance
    # union_fragile.py:17: note: Consider using "Sequence" instead, which is covariant
    # union_fragile.py:17: error: Argument 2 to "concat" has incompatible type "List[str]"; expected "List[Union[int, str]]"

• What is the actual behavior/output?

$ mypy union_fragile.py 
mypy union_fragile.py 
union_fragile.py:13: note: Revealed type is 'builtins.list[builtins.int*]'
union_fragile.py:14: note: Revealed type is 'builtins.list[builtins.str*]'
union_fragile.py:15: note: Revealed type is 'builtins.list[Union[builtins.int*, builtins.str*]]'
union_fragile.py:17: error: Argument 1 to "concat" has incompatible type "List[int]"; expected "List[Union[int, str]]"
union_fragile.py:17: note: "List" is invariant -- see http://mypy.readthedocs.io/en/latest/common_issues.html#variance
union_fragile.py:17: note: Consider using "Sequence" instead, which is covariant
union_fragile.py:17: error: Argument 2 to "concat" has incompatible type "List[str]"; expected "List[Union[int, str]]"
Found 2 errors in 1 file (checked 1 source file)

• What is the behavior/output you expect?

I expect this to be accepted.
Because if I replace return concat(xs, ys) with return zs, it is accepted.

• What are the versions of mypy and Python you are using?
  Do you see the same issue after installing mypy from Git master?

$ mypy --version
mypy --version
mypy 0.761
$ python --version
python --version
Python 3.6.3 :: Anaconda, Inc.

I see the same issue after install installing mypy from Git master.

• What are the mypy flags you are using? (For example --strict-optional)

I did not provide any flags.

[msakai]

(I'm not familiar with mypy internals and the following is just my guess.)

It seems that mypy first compared List[Union[A, B]] (the return type of concat) with expected type List[Union[int, str]] and derived an instantiation A = B = Union[int, str]. But, since List is non-injective type constructor, there are other possible instantiation including:

• A=int, B=str,
• A=str, B=int,
• A=Union[int, str], B=int,
• ..

Therefore, committing to a particular instantiation (A = B = Union[int, str] in this case) is not possible at the moment.

[ilevkivskyi]

I think this is essentially a duplicate of #5492 (plus the issue that mypy prefers external type context during inference).