recursive type with Union causes RuntimeError: Internal error: unresolved forward reference

[joshstaiger]

Run mypy (0.540) on the following code

from typing import *

MYTYPE = List[Union[str, "MYTYPE"]]

This generates the following:

forward.py:1: error: INTERNAL ERROR -- please report a bug at https://github.com/python/mypy/issues version: 0.540
Traceback (most recent call last):
  File "/Users/joshstaiger/anaconda/bin/mypy", line 11, in <module>
    sys.exit(console_entry())
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/__main__.py", line 7, in console_entry
    main(None)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/main.py", line 50, in main
    res = type_check_only(sources, bin_dir, options)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/main.py", line 103, in type_check_only
    options=options)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/build.py", line 201, in build
    graph = dispatch(sources, manager)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/build.py", line 1867, in dispatch
    process_graph(graph, manager)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/build.py", line 2117, in process_graph
    process_stale_scc(graph, scc, manager)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/build.py", line 2214, in process_stale_scc
    graph[id].semantic_analysis_pass_three()
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/build.py", line 1760, in semantic_analysis_pass_three
    self.options, patches)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/semanal_pass3.py", line 56, in visit_file
    self.accept(file_node)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/semanal_pass3.py", line 73, in accept
    node.accept(self)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/nodes.py", line 228, in accept
    return visitor.visit_mypy_file(self)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/traverser.py", line 30, in visit_mypy_file
    d.accept(self)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/nodes.py", line 794, in accept
    return visitor.visit_assignment_stmt(self)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/semanal_pass3.py", line 187, in visit_assignment_stmt
    self.analyze(s.rvalue.analyzed.type, s.rvalue.analyzed, warn=True)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/semanal_pass3.py", line 311, in analyze
    type.accept(analyzer)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/types.py", line 476, in accept
    return visitor.visit_instance(self)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/typeanal.py", line 716, in visit_instance
    if not is_subtype(arg, bound):
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/subtypes.py", line 83, in is_subtype
    ignore_declared_variance=ignore_declared_variance))
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/types.py", line 1227, in accept
    return visitor.visit_union_type(self)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/subtypes.py", line 312, in visit_union_type
    for item in left.items)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/subtypes.py", line 312, in <genexpr>
    for item in left.items)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/subtypes.py", line 83, in is_subtype
    ignore_declared_variance=ignore_declared_variance))
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/types.py", line 1412, in accept
    return visitor.visit_forwardref_type(self)
  File "/Users/joshstaiger/anaconda/lib/python3.6/site-packages/mypy/types.py", line 1497, in visit_forwardref_type
    raise RuntimeError('Internal error: unresolved forward reference')
RuntimeError: Internal error: unresolved forward reference
forward.py:1: : note: use --pdb to drop into pdb

Note that I understand that recursive types are not yet supported and I get the more friendly message stating such if I define one that does not involve the Union.

[ilevkivskyi]

This is a manifestation of #3977 (calling is_subtype during semantic analysis). I think this is quite high priority since this can happen in many similar scenarios.

@JukkaL what do you think we should do? Maybe just add another round of patches? Currently all patches are in one "pile" (in a list actually, so they are ordered), I was thinking about having separate rounds, for example:

• resolving forward references
• recomputing MRO's
• fixing tuple and other fallback type arguments
• checking the boundaries and constraints of type variables

EDIT: fixed second sentence, thanks @elazarg

[JukkaL]

@ilevkivskyi What about adding a priority number to the patches? We'd sort the patches by their priority before applying them.

[ilevkivskyi]

What about adding a priority number to the patches?

OK, makes sense.

[JukkaL]

@ilevkivskyi Are you working on this? I can also look at this if you are busy.

[ilevkivskyi]

@JukkaL No, sorry, last two weeks were too busy. It would be great if you take care of this.

[ilevkivskyi]

Another repro for this crash reported in #4381:

from typing import List, NewType, Union

N = NewType('N', XXX)

x: List[Union[N, int]]

[JukkaL]

I'm going to look at this since this is interfering with some of my experiments and seems relatively easy to trigger through skipped imports.