Stack overflow in repr of deeply nested dicts

[serhiy-storchaka]

BPO	32137
Nosy	@rhettinger, @vstinner, @serhiy-storchaka
PRs	bpo-32137: The repr of deeply nested dict now raises a RecursionError #4570 [3.6] bpo-32137: The repr of deeply nested dict now raises a RecursionError (GH-4570) #4689 [3.6] bpo-32137: The repr of deeply nested dict now raises a RecursionError (GH-4570) #4812 bpo-18533: Avoid RuntimeError from repr() of recursive dictview #4823 [2.7] bpo-32137: The repr of deeply nested dict now raises a RuntimeError (GH-4570) #5493

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2018-02-02.14:30:31.024>
created_at = <Date 2017-11-26.08:53:30.503>
labels = ['interpreter-core', '3.7', 'type-crash']
title = 'Stack overflow in repr of deeply nested dicts'
updated_at = <Date 2018-02-02.14:30:31.024>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2018-02-02.14:30:31.024>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2018-02-02.14:30:31.024>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2017-11-26.08:53:30.503>
creator = 'serhiy.storchaka'
dependencies = []
files = []
hgrepos = []
issue_num = 32137
keywords = ['patch']
message_count = 7.0
messages = ['306997', '307522', '308114', '309021', '311420', '311488', '311493']
nosy_count = 3.0
nosy_names = ['rhettinger', 'vstinner', 'serhiy.storchaka']
pr_nums = ['4570', '4689', '4812', '4823', '5493']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue32137'
versions = ['Python 2.7', 'Python 3.6', 'Python 3.7']

[serhiy-storchaka]

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 bpo-18533 and bpo-25240.

[serhiy-storchaka]

New changeset 1fb72d2 by Serhiy Storchaka in branch 'master':
bpo-32137: The repr of deeply nested dict now raises a RecursionError (bpo-4570)
1fb72d2

[serhiy-storchaka]

PR 4812 is an alternate fix for 3.6. It doesn't touch reprs of other types.

[serhiy-storchaka]

Could you please take a look at PR 4689 and PR 4812 Raymond? I remember you had objections against similar changes and I have small hesitates. What way of solving this issue in maintained releases do you prefer?

[serhiy-storchaka]

New changeset 688b6de by Serhiy Storchaka (Miss Islington (bot)) in branch '3.6':
bpo-32137: The repr of deeply nested dict now raises a RecursionError (GH-4570) (GH-4689)
688b6de

[rhettinger]

The issue seems somewhat contrived but the fix looks fine to me.

[serhiy-storchaka]

New changeset b7a2c17 by Serhiy Storchaka in branch '2.7':
[2.7] bpo-32137: The repr of deeply nested dict now raises a RuntimeError (GH-4570) (bpo-5493)
b7a2c17