AST Recursion failure from hypothesis in SymPy CI

[oscarbenjamin]

This is coming from sympy/sympy#27967

The hypothesis tests in SymPy CI are failing because of what looks like a bug in hypothesis:
https://github.com/sympy/sympy/actions/runs/14534219412/job/40779555253?pr=27821

The failure is a RecursionError:

=================================== FAILURES ===================================
_____________________________ test_gcd_hypothesis ______________________________
[gw3] linux -- Python 3.13.3 /opt/hostedtoolcache/Python/3.13.3/x64/bin/python

    @given(f=polys(), g=polys(), r=polys())
>   def test_gcd_hypothesis(f, g, r):

sympy/polys/tests/test_hypothesis.py:17: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/ast.py:428: in visit
    return visitor(node)
...
/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/ast.py:438: in generic_visit
    self.visit(value)
/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/ast.py:428: in visit
    return visitor(node)
/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/ast.py:438: in generic_visit
    self.visit(value)
/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/ast.py:428: in visit
    return visitor(node)
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

self = <hypothesis.internal.constants_ast.ConstantVisitor object at 0x7fe7fc6e0870>
node = <ast.BinOp object at 0x7fe7fcb4fc50>

    def generic_visit(self, node):
        """Called if no explicit visitor function exists for a node."""
>       for field, value in iter_fields(node):
E       RecursionError: maximum recursion depth exceeded

I don't understand enough about hypothesis to know why it is using the ast module here or what ast it is trying to analyse. The code in the test functions is not complicated so there is no reason why it would have a large ast.

I don't know how to reproduce the failure outside of CI but it happens reliably there on all PRs now.

[oscarbenjamin]

After updating to the latest hypothesis 6.131.3 locally I still don't reproduce the failure locally but it is extremely slow:

$ pytest sympy/polys/tests/test_hypothesis.py 
======================================== test session starts ========================================
platform linux -- Python 3.12.8, pytest-8.3.5, pluggy-1.5.0
architecture: 64-bit
cache:        yes
ground types: flint (python-flint==0.7.1)

rootdir: /stuff/current/active/sympy
configfile: pyproject.toml
plugins: hypothesis-6.131.3, xdist-3.6.1, anyio-4.9.0, cov-6.1.1
collected 3 items                                                                                   

sympy/polys/tests/test_hypothesis.py ...                                                      [100%]

======================================== 3 passed in 27.77s =========================================

That slowness seems to have happened before 6.131.3 though. This is what I see with 6.123.13:

$ pytest sympy/polys/tests/test_hypothesis.py 
======================================== test session starts ========================================
platform linux -- Python 3.12.8, pytest-8.3.5, pluggy-1.5.0
architecture: 64-bit
cache:        yes
ground types: flint (python-flint==0.7.1)

rootdir: /stuff/current/active/sympy
configfile: pyproject.toml
plugins: xdist-3.6.1, hypothesis-6.123.13, anyio-4.9.0, cov-6.1.1
collected 3 items                                                                                   

sympy/polys/tests/test_hypothesis.py ...                                                      [100%]

========================================= 3 passed in 3.92s =========================================

So it's 30 seconds vs 4 seconds. Maybe some very slow ast stuff?

I bisected that to 6.131.1 i.e. 6.131.0 is 4 seconds and 6.131.1 is 30 seconds.

Hard to tell the exact time of the release from PyPI but that probably coincides with SymPy CI breaking due to the recursion error problem.

[oscarbenjamin]

My money is on gh-4356

CC @tybug

[oscarbenjamin]

For a simple reproducer you can do:

pip install sympy==1.13.3
pytest --pyargs sympy.polys.tests.test_hypothesis

[tybug]

Thanks for the report. This is certainly from #4356. I'm looking into this

[tybug]

Slowness will be fixed by #4366. I'm unsure it will do anything for the recursion error. Probably we should put a generic try/catch around this, I've seen enough weird issues on e.g. libcst to be wary of getting this right 100% of the time

[oscarbenjamin]

I'm unsure it will do anything for the recursion error. Probably we should put a generic try/catch around this

The ast module is poorly designed in that it uses recursion but can easily end up having deep trees. I think it is better to not to use the ast module's visit method.

It is better to use the non-recursive walk function if possible:
https://github.com/python/cpython/blob/main/Lib/ast.py#L392-L403

[oscarbenjamin]

I don't see why the ast module would have any problem with the module in question though:
https://github.com/sympy/sympy/blob/089edf0ea752497120cbaa1a5af4b5d4bcab9a85/sympy/polys/tests/test_hypothesis.py#L1-L36

Is it recursively following all the imports and parsing everything?

[tybug]

We do use the context from NodeVisitor to e.g. avoid collecting constants from f-strings, so I don't think walk will work.

Is it recursively following all the imports and parsing everything?

It looks for any "local" files in sys.modules - which is anything that isn't a stdlib module or a third-party library. In other words, all of sympy's source files. The idea is that literal integers, strings, etc used in a codebase are much more likely to induce bugs in tests in that codebase, and so we should generate them more often. So it's recursion-erroring on some local sympy source file.

[oscarbenjamin]

It looks for any "local" files in sys.modules - which is anything that isn't a stdlib module or a third-party library. In other words, all of sympy's source files.

This should not be enabled by default.

[oscarbenjamin]

In [5]: from hypothesis.internal.constants_ast import local_modules

In [6]: len(local_modules())
Out[6]: 420

In [13]: sum([len(open(m.__file__).read()) for m in local_modules()])
Out[13]: 9470030

This is pulling in 10 megabytes of source code and parsing it with the slow ast module.

[tybug]

Parsing all the constants in symyp takes 1.8s on the first run, even after #4366:

from hypothesis.internal.constants_ast import local_modules, constants_from_module
import time

# in sympy/.../test_hypothesis.py

t = time.time()
for module in local_modules():
    constants_from_module(module)

print(time.time() - t)
# 1.8274540901184082

Definitely not great

0.985 seconds of this is from ast.parse, the rest is from the NodeVisitor

[oscarbenjamin]

The ast module can fail to parse valid python code e.g.:
https://github.com/sympy/sympy/blob/089edf0ea752497120cbaa1a5af4b5d4bcab9a85/sympy/polys/numberfields/resolvent_lookup.py#L1