pylint-dev / pylint-dev/astroid
`MultiLineBlockMixin` causes stack overflow from recursive `_get_assign_nodes()`
- Dominant language
- Python
- Stars
- 582
- Forks
- 357
- Avg merge
- 1d 1h
- Merged PRs (30d)
- 23
Description
## Problem
The recursive nature of the `_get_assign_nodes()` method can lead to a `RecursionError` and break running `pylint` on a project that has a class with a large control structure in its method.
### Workaround
A hackish means of avoiding this bug is to increase the stack size to some value that enables further recursion without exhausting the stack. It's documented [in a comment](https://github.com/PyCQA/astroid/issues/786#issuecomment-716662442), but in essence the idea is calling `sys.setrecursionlimit(some_int)` before running `pylint` or `astroid`). A more robust fix would be to avoid recursion altogether since this hack only increases the number of lines astroid can parse.
### Affected versions
```
>>> from astroid import __pkginfo__; print(__pkginfo__.version)
2.4.1
```
I've tested this on every minor version since Astroid 2.1.0. Astroid 2.0.4 is *not* affected.
Since the release of Astroid 2.1.0, we've been experiencing stack overflow exceptions for a class with a very large chain of `if/else` statements.
## How to reproduce:
The following Python file is enough to trigger a recursion error on any version of Astroid from 2.1.0 through the unreleased 2.5.0:
```python
# file_with_large_if_elif.py
class TestClasse:
def cause_astroid_recursion(self):
if True:
pass
elif True:
pass
# Repeat as needed to overflow > sys.getrecursionlimit() on your system
#
# On my machine, 119 total `elif` statements is enough to trigger recursion
elif True:
pass
```
```bash
$ pylint file_with_large_if_elif.py
File ".../astroid/mixins.py", line 153, in _get_assign_nodes
return list(itertools.chain.from_iterable(children_assign_nodes))
File ".../astroid/mixins.py", line 151, in
for child_node in block
File ".../astroid/decorators.py", line 33, in cached
cache[func] = result = func(*args, **kwargs)
File ".../astroid/mixins.py", line 153, in _get_assign_nodes
return list(itertools.chain.from_iterable(children_assign_nodes))
File ".../astroid/mixins.py", line 151, in
for child_node in block
File ".../astroid/decorators.py", line 33, in cached
cache[func] = result = func(*args, **kwargs)
RecursionError: maximum recursion depth exceeded while calling a Python object
```
### Source of the `RecursionError`
The [current implementation](https://github.com/PyCQA/astroid/blob/681336416aeea229d6bfdf32f70e781049c92065/astroid/mixins.py#L146-L153) of `MultiLineBlockMixin` makes a recursive call to `_get_assign_nodes()`:
```python
@decorators.cached
def _get_assign_nodes(self):
children_assign_nodes = (
child_node._get_assign_nodes()
for block in self._multi_line_blocks
for child_node in block
)
return list(itertools.chain.from_iterable(children_assign_nodes))
```
## Possible fix
I think that a possible fix would be to switch from a recursive design, towards a stack-based solution. If we instead built a list of nodes as we go (say, with a `while` loop & a stack), we could avoid the overflow.
The generators used in `_get_assign_nodes()` are eagerly converted into a list anyway, so keeping a list of children then popping to get all assign nodes should have no negative performance effects.
A quick attempt on my own machine seems to work (though I've not written any new tests, or tested my changes against the test suite).
## A less contrived reproduction
I stumbled upon this error by trying to run `astroid` on a class that's automatically produced by Apache Thrift.
Given an input file like so:
```c++
// proof_of_concept.thrift
struct LargeStruct {
1: optional string argument_1;
2: optional string argument_2;
3: optional string argument_3;
// ...
116: optional string argument_116;
}
```
One can run `thrift --gen py proof_of_concept.thrift` to produce `gen-py/proof_of_concept/ttypes.py`
In the produced file is a large Python class - the many `if/elif` statements in `read()` method is what trips up `astroid`:
```python
class LargeStruct(object):
#
def read(self, iprot):
# (some code truncated) - the body of the `while` loop is what's relevant
while True:
(fname, ftype, fid) = iprot.readFieldBegin()
if ftype == TType.STOP:
break
if fid == 1:
if ftype == TType.STRING:
self.argument_1 = iprot.readString().decode('utf-8') if sys.version_info[0] == 2 else iprot.readString()
else:
iprot.skip(ftype)
elif fid == 2:
if ftype == TType.STRING:
self.argument_2 = iprot.readString().decode('utf-8') if sys.version_info[0] == 2 else iprot.readString()
else:
iprot.skip(ftype)
#
# <113 other `elif` branches truncated>
#
elif fid == 116:
if ftype == TType.STRING:
self.argument_116 = iprot.readString().decode('utf-8') if sys.version_info[0] == 2 else iprot.readString()
else:
iprot.skip(ftype)
else:
iprot.skip(ftype)
iprot.readFieldEnd()
iprot.readStructEnd()
```
Large Thrift structs are fairly common, so this can happen with some frequency.
## Pull request?
I understand if parsing hundreds of control statements isn't something that `astroid` seeks to be able to do.
However, if you're open to refactoring out recursion, I'd be willing to write up a PR for this problem.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in astroid/mixins.py at MultiLineBlockMixin._get_assign_nodes(), then run the file_with_large_if_elif.py reproduction through pylint to observe the RecursionError. Replace the recursive traversal as proposed and verify that large chains of if/elif statements no longer overflow, while checking the test suite for regressions.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- devtools
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100