"maximum semantic analysis iteration count reached" with TypeVar bound to recursive type definition

[brianmaissy]

I encountered what appears to be a bug when using a TypeVar bound to a recursive type definition.

• Python 3.6.9
• mypy 0.761, also master

Simplified example code:

from typing import Union, List, TypeVar

SomethingWithWs = Union[str, List['SomethingWithWs']]

T = TypeVar('T', bound=SomethingWithWs)


def remove_w(data: T) -> T:
    if isinstance(data, str):
        return data.replace('w', '')
    elif isinstance(data, list):
        return [remove_w(d) for d in data]
    else:
        raise TypeError()

I ran the command:
mypy remove_w.py --show-traceback
with no additional configuration file

Output:

Deferral trace:
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
    remove_w:3
    remove_w:3
    remove_w:-1
    remove_w:5
    remove_w:5
remove_w.py: error: INTERNAL ERROR: maximum semantic analysis iteration count reached
remove_w.py:8: error: INTERNAL ERROR -- Please try using mypy master on Github:
https://mypy.rtfd.io/en/latest/common_issues.html#using-a-development-mypy-build
Please report a bug at https://github.com/python/mypy/issues
version: 0.761
Traceback (most recent call last):
  File "mypy/semanal.py", line 4665, in accept
  File "mypy/nodes.py", line 676, in accept
  File "mypy/semanal.py", line 557, in visit_func_def
  File "mypy/semanal.py", line 586, in analyze_func_def
  File "mypy/typeanal.py", line 501, in visit_callable_type
  File "mypy/typeanal.py", line 867, in anal_var_defs
  File "mypy/types.py", line 1888, in accept
  File "mypy/typeanal.py", line 600, in visit_placeholder_type
  File "mypy/semanal.py", line 4399, in defer
AssertionError: Must not defer during final iteration
remove_w.py:8: : note: use --pdb to drop into pdb

[ilevkivskyi]

Thanks for reporting! Recursive types are not supported, but at least it shouldn't crash.

[jirassimok]

The problem appears to be that whatever check is used to detect recursive types does not run when analyzing type variables.

This seems to happen when a type variable is bounded or constrained by a recursively-defined type.

from typing import Union, TypeVar
R = Union['R']
T = TypeVar('T', bound=R)

This generates the error with every generic type constructor I tried, as well as class R(R): .... It also works using a type variable constrained (rather than bounded) by the recursive type.

---

Traceback on the current master branch (d6c2c01)

version: 0.770+dev.d6c2c01fd04043bff55222f1f43a9fe2e15c0ccf
Traceback (most recent call last):
  File "venv/bin/mypy", line 10, in <module>
    sys.exit(console_entry())
  File "venv/.../mypy/__main__.py", line 8, in console_entry
    main(None, sys.stdout, sys.stderr)
  File "venv/.../mypy/main.py", line 89, in main
    res = build.build(sources, options, None, flush_errors, fscache, stdout, stderr)
  File "venv/.../mypy/build.py", line 165, in build
    result = _build(
  File "venv/.../mypy/build.py", line 234, in _build
    graph = dispatch(sources, manager, stdout)
  File "venv/.../mypy/build.py", line 2631, in dispatch
    process_graph(graph, manager)
  File "venv/.../mypy/build.py", line 2938, in process_graph
    process_stale_scc(graph, scc, manager)
  File "venv/.../mypy/build.py", line 3031, in process_stale_scc
    mypy.semanal_main.semantic_analysis_for_scc(graph, scc, manager.errors)
  File "venv/.../mypy/semanal_main.py", line 83, in semantic_analysis_for_scc
    check_type_arguments(graph, scc, errors)
  File "venv/.../mypy/semanal_main.py", line 359, in check_type_arguments
    state.tree.accept(analyzer)
  File "/system_python/3.8/.../contextlib.py", line 131, in __exit__
    self.gen.throw(type, value, traceback)
  File "venv/.../mypy/build.py", line 1903, in wrap_context
    yield
  File "venv/.../mypy/semanal_main.py", line 359, in check_type_arguments
    state.tree.accept(analyzer)
  File "venv/.../mypy/nodes.py", line 294, in accept
    return visitor.visit_mypy_file(self)
  File "venv/.../mypy/semanal_typeargs.py", line 39, in visit_mypy_file
    super().visit_mypy_file(o)
  File "venv/.../mypy/traverser.py", line 35, in visit_mypy_file
    d.accept(self)
  File "venv/.../mypy/nodes.py", line 1062, in accept
    return visitor.visit_assignment_stmt(self)
  File "venv/.../mypy/mixedtraverser.py", line 64, in visit_assignment_stmt
    super().visit_assignment_stmt(o)
  File "venv/.../mypy/traverser.py", line 85, in visit_assignment_stmt
    o.rvalue.accept(self)
  File "venv/.../mypy/nodes.py", line 1544, in accept
    return visitor.visit_call_expr(self)
  File "venv/.../mypy/traverser.py", line 172, in visit_call_expr
    o.analyzed.accept(self)
  File "venv/.../mypy/nodes.py", line 2091, in accept
    return visitor.visit_type_var_expr(self)
  File "venv/.../mypy/mixedtraverser.py", line 40, in visit_type_var_expr
    o.upper_bound.accept(self)
  File "venv/.../mypy/types.py", line 794, in accept
    return visitor.visit_instance(self)
  File "venv/.../mypy/semanal_typeargs.py", line 82, in visit_instance
    if not is_subtype(arg, tvar.upper_bound):
  File "venv/.../mypy/subtypes.py", line 93, in is_subtype
    return _is_subtype(left, right,
  File "venv/.../mypy/subtypes.py", line 135, in _is_subtype
    return left.accept(SubtypeVisitor(orig_right,
  File "venv/.../mypy/types.py", line 1898, in accept
    assert isinstance(visitor, SyntheticTypeVisitor)
AssertionError:

[ilevkivskyi]

The original example doesn't crash on master with --enable-recursive-aliases. It does give couple errors, but those are kind of expected (e.g. what if data is a subclass of str, the return will not be T in this case):

test.py:10: error: Incompatible return value type (got "str", expected "T")
test.py:12: error: Incompatible return value type (got "List[Union[str, List[SomethingWithWs]]]", expected "T")

The weird example with R = Union[R] actually still crashes, but no-one will ever use something like this. Feel free to re-open if there is still a crash on a realistic recursive type.