[New-bugs-announce] [issue32137] Stack overflow in repr of deeply nested dicts

[Serhiy Storchaka]

New submission from Serhiy Storchaka <storchaka+cpython at gmail.com>:

repr() of deeply nested dicts and dictviews can cause a stack overflow.

>>> x = {}
>>> for i in range(100000):
...     x = {1: x}
... 
>>> repr(x)
Segmentation fault

>>> x = {}
>>> for i in range(100000):
...     x = {1: x}
... 
>>> repr(x.values())
Segmentation fault

repr() of virtually all other deeply nested collections are guarded by using Py_EnterRecursiveCall().

>>> x = ()
>>> for i in range(100000):
...     x = (x,)
... 
>>> repr(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded while getting the repr of a tuple

>>> x = []
>>> for i in range(100000):
...     x = [x]
... 
>>> repr(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded while getting the repr of a list

>>> x = frozenset()
>>> for i in range(100000):
...     x = frozenset({x})
... 
>>> repr(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded while getting the repr of a list

>>> from collections import OrderedDict
>>> x = {}
>>> for i in range(100000):
...     x = OrderedDict({1: x})
... 
>>> repr(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded while getting the repr of a list

>>> from collections import deque
>>> x = deque()
>>> for i in range(100000):
...     x = deque([x])
... 
>>> repr(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded while getting the repr of a list

But the case of infinite recursion already is handled:

>>> x = {}
>>> x[1] = x
>>> repr(x)
'{1: {...}}'

Only finite but very deep recursion causes a crash.

The one possible solution -- add Py_EnterRecursiveCall() in the implementation of dict.__repr__(), like it already is added in list.__repr__() and tuple.__repr__().

The more general solution -- add Py_EnterRecursiveCall() in PyObject_Repr(). In any case it is called before calling PyObject_Repr() for every item in the repr of most collections except dict. And it is already added in PyObject_Str(). Therefore adding it will not add much overhead, but can handle more corner cases.

See also issue18533 and issue25240.

----------
components: Interpreter Core
messages: 306997
nosy: serhiy.storchaka
priority: normal
severity: normal
status: open
title: Stack overflow in repr of deeply nested dicts
type: crash
versions: Python 2.7, Python 3.6, Python 3.7

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue32137>
_______________________________________