classification
Title: Stack overflow in itertools.chain.from_iterable.
Type: crash Stage: resolved
Components: Versions: Python 3.7, Python 3.6, Python 3.5, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: twouters Nosy List: gregory.p.smith, mark.dickinson, rhettinger, serhiy.storchaka, twouters
Priority: normal Keywords:

Created on 2017-03-29 17:09 by twouters, last changed 2017-03-30 19:52 by twouters. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 889 merged twouters, 2017-03-29 17:09
PR 911 merged twouters, 2017-03-30 17:37
PR 912 merged twouters, 2017-03-30 17:37
PR 913 merged twouters, 2017-03-30 17:38
Messages (9)
msg290787 - (view) Author: Thomas Wouters (twouters) * (Python committer) Date: 2017-03-29 17:09
itertools.chain.from_iterable (somewhat ironically) uses recursion to resolve the next iterator, which means it can run out of the C stack when there's a long run of empty iterables. This is most obvious when building with low optimisation modes, or with Py_DEBUG enabled:

Python 3.7.0a0 (heads/master:c431854a09, Mar 29 2017, 10:03:50) 
[GCC 4.8.4] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import itertools
>>> next(itertools.chain.from_iterable(() for unused in range(10000000)))
Segmentation fault (core dumped)
msg290829 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2017-03-30 07:36
This looks fine.  Feel free to apply and to backport this to earlier versions.

I would have guessed that the C compiler would have automatically removed the tail recursion, but your experience would indicate otherwise.
msg290831 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2017-03-30 07:46
> I would have guessed that the C compiler would have automatically removed the tail recursion

I think it probably does, unless optimisation is turned off: I'm unable to reproduce except in debug builds of Python.
msg290861 - (view) Author: Thomas Wouters (twouters) * (Python committer) Date: 2017-03-30 16:58
New changeset 5466d4af5fe76ec0a5fbc8a05675287d9e8e9d14 by T. Wouters in branch 'master':
bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. (#889)
https://github.com/python/cpython/commit/5466d4af5fe76ec0a5fbc8a05675287d9e8e9d14
msg290863 - (view) Author: Thomas Wouters (twouters) * (Python committer) Date: 2017-03-30 17:05
FWIW, we ran into this in real-world cases (Youtube, I think), when we switched from using a pre-built Python interpreter to one built from source using the same optimisation and debug levels as we use for all other C/C++ code. Even so, the accompanying test really does fail in pydebug mode ;-P

I'll backport to 3.6, 3.5 and 2.7.
msg290866 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-03-30 18:02
Possible workaround: use chain.from_iterable(filter(None, iterables)) instead of chain.from_iterable(iterables). But this works only when iterables are collections, not iterators.
msg290874 - (view) Author: Thomas Wouters (twouters) * (Python committer) Date: 2017-03-30 19:48
New changeset 599bb181036f724629a515317f0f39520950d51c by T. Wouters in branch '3.6':
bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. (#911)
https://github.com/python/cpython/commit/599bb181036f724629a515317f0f39520950d51c
msg290875 - (view) Author: Thomas Wouters (twouters) * (Python committer) Date: 2017-03-30 19:48
New changeset 9273dfe1800fc7241d69f4d523d748ebd35b3801 by T. Wouters in branch '3.5':
bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. (#912)
https://github.com/python/cpython/commit/9273dfe1800fc7241d69f4d523d748ebd35b3801
msg290876 - (view) Author: Thomas Wouters (twouters) * (Python committer) Date: 2017-03-30 19:49
New changeset d694a06206fc09b76b4507aacde5e69a248f434f by T. Wouters in branch '2.7':
bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. (#913)
https://github.com/python/cpython/commit/d694a06206fc09b76b4507aacde5e69a248f434f
History
Date User Action Args
2017-03-30 19:52:34twouterssetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2017-03-30 19:49:24twouterssetmessages: + msg290876
2017-03-30 19:48:57twouterssetmessages: + msg290875
2017-03-30 19:48:26twouterssetmessages: + msg290874
2017-03-30 18:02:03serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg290866
2017-03-30 17:38:09twouterssetpull_requests: + pull_request813
2017-03-30 17:37:40twouterssetpull_requests: + pull_request812
2017-03-30 17:37:04twouterssetpull_requests: + pull_request811
2017-03-30 17:05:41twouterssetmessages: + msg290863
2017-03-30 16:58:37twouterssetmessages: + msg290861
2017-03-30 07:46:34mark.dickinsonsetnosy: + mark.dickinson
messages: + msg290831
2017-03-30 07:36:27rhettingersetassignee: twouters
messages: + msg290829
2017-03-29 17:41:59serhiy.storchakasetnosy: + rhettinger
stage: patch review

versions: + Python 2.7, Python 3.5, Python 3.6, Python 3.7
2017-03-29 17:09:14twouterssettype: crash
2017-03-29 17:09:09twouterscreate