classification
Title: Stack overflow in repr of deeply nested dicts
Type: crash Stage: resolved
Components: Interpreter Core Versions: Python 3.7, Python 3.6, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: rhettinger, serhiy.storchaka, vstinner
Priority: normal Keywords: patch

Created on 2017-11-26 08:53 by serhiy.storchaka, last changed 2018-02-02 14:30 by serhiy.storchaka. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 4570 merged serhiy.storchaka, 2017-11-26 12:42
PR 4689 merged python-dev, 2017-12-03 20:12
PR 4812 closed serhiy.storchaka, 2017-12-12 11:10
PR 4823 bennorth, 2017-12-12 22:40
PR 5493 merged serhiy.storchaka, 2018-02-02 13:25
Messages (7)
msg306997 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-11-26 08:53
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.
msg307522 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-03 20:12
New changeset 1fb72d2ad243c965d4432b4e93884064001a2607 by Serhiy Storchaka in branch 'master':
bpo-32137: The repr of deeply nested dict now raises a RecursionError (#4570)
https://github.com/python/cpython/commit/1fb72d2ad243c965d4432b4e93884064001a2607
msg308114 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-12 11:11
PR 4812 is an alternate fix for 3.6. It doesn't touch reprs of other types.
msg309021 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-25 00:17
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?
msg311420 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-01 11:57
New changeset 688b6dec4e8847a154ef27257069291175764794 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)
https://github.com/python/cpython/commit/688b6dec4e8847a154ef27257069291175764794
msg311488 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2018-02-02 10:06
The issue seems somewhat contrived but the fix looks fine to me.
msg311493 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-02 14:29
New changeset b7a2c17be8411bc4c7a2babdc650074c14204aa8 by Serhiy Storchaka in branch '2.7':
[2.7] bpo-32137: The repr of deeply nested dict now raises a RuntimeError (GH-4570) (#5493)
https://github.com/python/cpython/commit/b7a2c17be8411bc4c7a2babdc650074c14204aa8
History
Date User Action Args
2018-02-02 14:30:31serhiy.storchakasetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2018-02-02 14:29:09serhiy.storchakasetmessages: + msg311493
2018-02-02 13:25:59serhiy.storchakasetpull_requests: + pull_request5326
2018-02-02 10:06:54rhettingersetassignee: rhettinger ->
messages: + msg311488
2018-02-01 11:57:30serhiy.storchakasetmessages: + msg311420
2017-12-25 00:17:07serhiy.storchakasetassignee: rhettinger

messages: + msg309021
nosy: + rhettinger
2017-12-12 22:40:14bennorthsetpull_requests: + pull_request4716
2017-12-12 11:11:50serhiy.storchakasetmessages: + msg308114
2017-12-12 11:10:19serhiy.storchakasetpull_requests: + pull_request4707
2017-12-03 20:12:24python-devsetpull_requests: + pull_request4602
2017-12-03 20:12:15serhiy.storchakasetmessages: + msg307522
2017-11-28 22:52:44vstinnersetnosy: + vstinner
2017-11-26 12:42:44serhiy.storchakasetkeywords: + patch
stage: patch review
pull_requests: + pull_request4498
2017-11-26 08:53:30serhiy.storchakacreate