bug: RecursionError for expression with huge amount of binary operators

[filaretov]

Description of the bug

When parsing an expression with a huge number of binary operators, like this one in sympy, griffe fails with a RecursionError because it exceeds the recursion limit.

To Reproduce

With latest griffe installed as an executable:

git clone --depth=1 https://github.com/sympy/sympy
griffe dump sympy/sympy/polys/numberfields/resolvent_lookup.py

Full traceback

INFO       Loading package sympy/sympy/polys/numberfields/resolvent_lookup.py
ERROR      sympy/sympy/polys/numberfields/resolvent_lookup.py:7: Failed to get expression from Dict: RecursionError: maximum recursion depth exceeded
Traceback (most recent call last):
  File "/Users/user/.local/bin/griffe", line 12, in <module>
    sys.exit(main())
             ~~~~^^
  File "/Users/user/Library/Application Support/uv/tools/griffe/lib/python3.13/site-packages/griffe/_internal/cli.py", line 568, in main
    return commands[subcommand](**opts_dict)
           ~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^
  File "/Users/user/Library/Application Support/uv/tools/griffe/lib/python3.13/site-packages/griffe/_internal/cli.py", line 389, in dump
    loader = _load_packages(
        packages,
    ...<10 lines>...
        find_stubs_package=find_stubs_package,
    )
  File "/Users/user/Library/Application Support/uv/tools/griffe/lib/python3.13/site-packages/griffe/_internal/cli.py", line 101, in _load_packages
    loader.load(package, try_relative_path=True, find_stubs_package=find_stubs_package)
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/user/Library/Application Support/uv/tools/griffe/lib/python3.13/site-packages/griffe/_internal/loader.py", line 184, in load
    return self._post_load(top_module, obj_path)
           ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/user/Library/Application Support/uv/tools/griffe/lib/python3.13/site-packages/griffe/_internal/loader.py", line 198, in _post_load
    obj = self.modules_collection.get_member(obj_path)
  File "/Users/user/Library/Application Support/uv/tools/griffe/lib/python3.13/site-packages/griffe/_internal/mixins.py", line 83, in get_member
    return self.members[parts[0]]  # type: ignore[attr-defined]
           ~~~~~~~~~~~~^^^^^^^^^^
KeyError: 'resolvent_lookup'

Separately, I used an editable install of griffe and let the error propagate:

  File "/Users/user/dev/external/griffe/src/griffe/_internal/expressions.py", line 1355, in _build
    return _node_map[type(node)](node, parent, **kwargs)
  File "/Users/user/dev/external/griffe/src/griffe/_internal/expressions.py", line 1086, in _build_binop
    _build(node.left, parent, **kwargs),
  File "/Users/user/dev/external/griffe/src/griffe/_internal/expressions.py", line 1355, in _build
    return _node_map[type(node)](node, parent, **kwargs)
  File "/Users/user/dev/external/griffe/src/griffe/_internal/expressions.py", line 1086, in _build_binop
    _build(node.left, parent, **kwargs),
  File "/Users/user/dev/external/griffe/src/griffe/_internal/expressions.py", line 1355, in _build
    return _node_map[type(node)](node, parent, **kwargs)
RecursionError: maximum recursion depth exceeded in comparison

Expected behavior

The unreasonably large expression parses.

Environment information

• System: macOS-15.5-arm64-arm-64bit-Mach-O
• Python: cpython 3.13.2 (/Users/user/Library/Application Support/uv/tools/griffe/bin/python)
• Environment variables:
• Installed packages:
  • griffe v1.11.1

Additional context

Thanks for the excellent package!

[pawamoy]

Ouch! Thanks for the report @filaretov 🏄

Let me think about how to fix that, apart from increasing the maximum recursion with sys.setrecursionlimit.

[pawamoy]

Looks like 1175 is enough (compared to the default of 1000, at least on my machine). Maybe just increasing it to 1200 before loading an expression does the job 🤷

[pawamoy]

Hmm the recursion error happens in several places. I wonder if we could flatten the recursive AST before processing it. Or maybe we just sys.setrecursionlimit(1200) only once when loading a package (not each time we want to build an expression).

[pawamoy]

Just for info: in the biggest lambda, there are 290 + ops and 268 - ops (in a single expression, i.e. without parentheses), amounting to 558 nested binary ops. Considering our code, since we call _build() in between each _build_binop(), that amounts to a stack size of 1116. This is not counting the higher up frames that aren't relevant to expression building. That matches the numbers shown above 🙂

• No memoization possible here to skip frames.
• Always flattening the AST of binops just for this special case sounds overpowered (and inefficient).
• Actually special-casing this code from Sympy doesn't sound good either.
• Arbitrarily increasing the recursion limit feels a bit hacky and not really future proof.
• Rewriting the AST visitor (just the one for building expression) is kind of a big change.

Instead, I eventually thought about short-circuiting the recursivity a bit:

 def _build_binop(node: ast.BinOp, parent: Module | Class, **kwargs: Any) -> Expr:
     return ExprBinOp(
-        _build(node.left, parent, **kwargs),
+        _node_map[type(node.left)](node.left, parent, **kwargs),
         _binary_op_map[type(node.op)],
-        _build(node.right, parent, **kwargs),
+        _node_map[type(node.right)](node.right, parent, **kwargs),
     )

This divides the number of frames by two for building a binary operation expression 🙂 We can selectively apply this trick to other ops when someone hits the limit again. Or apply it immediately everwhere. It's a bit more verbose but the efficiency gain is worth considering.

[pawamoy]

Erm well yeah but the recursion limit is reached elsewhere too, as mentioned previously, so maybe we'll have to flatten anyway...

[johnslavik]

Ez just python/mypy#2766 and gg /j

[pawamoy]

Yeah so, the division by 2 of the stack size when building expression will solve loading. @filaretov would that be enough for you, or do you actually want to dump SymPy's API data, or render polys.numberfields.resolvent_lookup.resolvent_coeff_lambdas and its value with mkdocstrings? If not, then you're fine. If yes, I'll probably go with what @bswck mentioned here and just increase the limit, at least as a temporary solution (if not definitive). Solving that in a general manner without increasing the limit would require that we flatten parts of the AST where feasible, or somehow change all our recursive algorithms to iterative ones 😵

[pawamoy]

In the end I just increased the limit:

• when calling Griffe as CLI tool
• when instantiating the Python handler in mkdocstrings-python

This should solve this issue, I'll try to release both soon.