coverage html crashes with RecursionError in ast traversal

[oscarbenjamin]

Describe the bug

Running coverage html crashes with RecursionError in ast traversal when trying to measure coverage of SymPy's sympy.polys module.

To Reproduce

Tested in a fresh venv with Python 3.8, 3.11 and 3.12 using coverage 7.5.0. It seems to be a new problem in coverage 7.5.0 because I can't reproduce it with e.g. coverage 7.4.4.

To reproduce run:

pip install pytest coverage==7.5.0 pytest-cov hypothesis sympy==1.12
pytest --cov=sympy.polys --pyargs sympy.polys.tests.test_densetools
coverage html

Then coverage html crashes out with:

$ coverage html
Traceback (most recent call last):
  File "/home/oscar/current/active/sympy/tmp/tmp2/venv/bin/coverage", line 8, in <module>
    sys.exit(main())
             ^^^^^^
  File "/home/oscar/current/active/sympy/tmp/tmp2/venv/lib/python3.12/site-packages/coverage/cmdline.py", line 970, in main
    status = CoverageScript().command_line(argv)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/oscar/current/active/sympy/tmp/tmp2/venv/lib/python3.12/site-packages/coverage/cmdline.py", line 720, in command_line
    total = self.coverage.html_report(
            ^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/oscar/current/active/sympy/tmp/tmp2/venv/lib/python3.12/site-packages/coverage/control.py", line 1171, in html_report
    ret = reporter.report(morfs)
          ^^^^^^^^^^^^^^^^^^^^^^
  File "/home/oscar/current/active/sympy/tmp/tmp2/venv/lib/python3.12/site-packages/coverage/html.py", line 335, in report
    self.write_html_page(ftr)
  File "/home/oscar/current/active/sympy/tmp/tmp2/venv/lib/python3.12/site-packages/coverage/html.py", line 419, in write_html_page
    file_data = self.datagen.data_for_file(ftr.fr, ftr.analysis)
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/oscar/current/active/sympy/tmp/tmp2/venv/lib/python3.12/site-packages/coverage/html.py", line 138, in data_for_file
    for lineno, tokens in enumerate(fr.source_token_lines(), start=1):
  File "/home/oscar/current/active/sympy/tmp/tmp2/venv/lib/python3.12/site-packages/coverage/phystokens.py", line 127, in source_token_lines
    soft_key_lines = SoftKeywordFinder(source).soft_key_lines
                     ^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/oscar/current/active/sympy/tmp/tmp2/venv/lib/python3.12/site-packages/coverage/phystokens.py", line 86, in __init__
    self.visit(ast.parse(source))
  File "/home/oscar/.pyenv/versions/3.12.0/lib/python3.12/ast.py", line 407, in visit
    return visitor(node)
           ^^^^^^^^^^^^^
  File "/home/oscar/.pyenv/versions/3.12.0/lib/python3.12/ast.py", line 415, in generic_visit
    self.visit(item)
  File "/home/oscar/.pyenv/versions/3.12.0/lib/python3.12/ast.py", line 407, in visit
    return visitor(node)
           ^^^^^^^^^^^^^
  File "/home/oscar/.pyenv/versions/3.12.0/lib/python3.12/ast.py", line 417, in generic_visit
    self.visit(value)
  File "/home/oscar/.pyenv/versions/3.12.0/lib/python3.12/ast.py", line 407, in visit
    return visitor(node)
           ^^^^^^^^^^^^^
  File "/home/oscar/.pyenv/versions/3.12.0/lib/python3.12/ast.py", line 415, in generic_visit
    self.visit(item)
  File "/home/oscar/.pyenv/versions/3.12.0/lib/python3.12/ast.py", line 407, in visit
    return visitor(node)
           ^^^^^^^^^^^^^
...
  File "/home/oscar/.pyenv/versions/3.12.0/lib/python3.12/ast.py", line 417, in generic_visit
    self.visit(value)
  File "/home/oscar/.pyenv/versions/3.12.0/lib/python3.12/ast.py", line 407, in visit
    return visitor(node)
           ^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded

Expected behavior

Should produce coverage html report.

Additional context

There are other ways to reproduce this e.g. in a sympy git checkout:

pytest --cov=sympy.polys --cov-report=html sympy/polys

[oscarbenjamin]

It seems to be a new problem in coverage 7.5.0 because I can't reproduce it with e.g. coverage 7.4.4.

Actually I'm not sure about this. I just reproduced this in a different way with 7.4.4...

[nedbat]

Wow, interesting bug report. When I try it, it does happen with 7.4.4 as well as 7.5.0. In fact, it happens without coverage at all:

import ast
import inspect
import sympy.polys.numberfields.resolvent_lookup as mod
source = inspect.getsource(mod)
# Causes RecursionError: maximum recursion depth exceeded
ast.NodeVisitor().visit(ast.parse(source))

Has something else changed along with the 7.4.4->7.5.0 coverage update? The file is relatively new (18 months) but I would expect it to have failed like this before now.

[oscarbenjamin]

Thanks Ned.

Has something else changed along with the 7.4.4->7.5.0 coverage update?

I think it must be a while since I last tried to make a coverage html report that would have included this file. I was getting confused before about which versions of coverage I was testing with because of mixed up virtual environments. I guess what is new is just this file in sympy...

[oscarbenjamin]

Strangely though the code that you showed crashes if I run it as a direct script but not if run in ipython:

In [1]: import ast
   ...: import inspect
   ...: import sympy.polys.numberfields.resolvent_lookup as mod
   ...: source = inspect.getsource(mod)
   ...: # no error here
   ...: ast.NodeVisitor().visit(ast.parse(source))

In [2]: 

I'm not sure why that would be...

In any case I suppose that this is an ast bug then so I will go to cpython...

[nedbat]

I don't think it's an ast bug. If you use sys.setrecursionlimit() higher, it will succeed. You have crafted a source file with a truly deep AST.

[nedbat]

A recursion limit of 1100 fails, 1200 succeeds. The usual limit is 1000.

[oscarbenjamin]

It looks like the ast.walk function is better suited to what coverage needs here rather than NodeVisitor:
https://github.com/python/cpython/blob/13245027526bf1b21fae6e7ca62ceec2e39fcfb7/Lib/ast.py#L390-L401
That is non-recursive and yields all nodes in the tree. It can be wrapped up like:

if sys.version_info >= (3, 10):
    from ast import MatchClass
else:
    class MatchClass: pass


if sys.version_info >= (3, 12):
    from ast import TypeAlias
else:
    class TypeAlias: pass


def get_soft_key_lines(source):
    """Helper for finding lines with soft keywords, like match/case lines."""
    tree = ast.parse(source)
    soft_key_lines = set()

    for node in ast.walk(tree):
        if isinstance(node, MatchClass):
            soft_key_lines.add(node.lineno)
        elif isinstance(node, TypeAlias):
            soft_key_lines.add(node.lineno)
            for case in node.cases:
                soft_key_lines.add(case.pattern.lineno)

    return soft_key_lines

Unfortunately after making that change I get basically the same error coming from RegionFinder instead.

[nedbat]

Yes, coverage uses the ast in three places (up from two in 7.4.4). I'm wondering about limiting the depth of exploration, since it would also save time, and maybe caching the parses.

[nedbat]

Fixed in commit 5fa9f67.

[nedbat]

This is now released as part of coverage 7.5.1.

[oscarbenjamin]

Thanks Ned!

I was still thinking what could fix this. It seems to me that the ast module is missing some kind of generic primitive that would be usable for something like RegionFinder. There is walk but that does breadth first search. What is needed here is more like a preorder traversal except that you also need to remember the parents of each node while traversing.

It is problematic that NodeVisitor breaks with large expressions but there is not much else provided for traversal.