Stack overflow in itertools.chain.from_iterable.

[Yhg1s]

BPO	29942
Nosy	@Yhg1s, @rhettinger, @gpshead, @mdickinson, @serhiy-storchaka
PRs	bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. #889 bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. #911 bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. #912 bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. #913

^{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 = 'https://github.com/Yhg1s'
closed_at = <Date 2017-03-30.19:52:34.673>
created_at = <Date 2017-03-29.17:09:09.320>
labels = ['3.7', 'type-crash']
title = 'Stack overflow in itertools.chain.from_iterable.'
updated_at = <Date 2017-03-30.19:52:34.672>
user = 'https://github.com/Yhg1s'

bugs.python.org fields:

activity = <Date 2017-03-30.19:52:34.672>
actor = 'twouters'
assignee = 'twouters'
closed = True
closed_date = <Date 2017-03-30.19:52:34.673>
closer = 'twouters'
components = []
creation = <Date 2017-03-29.17:09:09.320>
creator = 'twouters'
dependencies = []
files = []
hgrepos = []
issue_num = 29942
keywords = []
message_count = 9.0
messages = ['290787', '290829', '290831', '290861', '290863', '290866', '290874', '290875', '290876']
nosy_count = 5.0
nosy_names = ['twouters', 'rhettinger', 'gregory.p.smith', 'mark.dickinson', 'serhiy.storchaka']
pr_nums = ['889', '911', '912', '913']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue29942'
versions = ['Python 2.7', 'Python 3.5', 'Python 3.6', 'Python 3.7']

[Yhg1s]

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)

[rhettinger]

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.

[mdickinson]

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.

[Yhg1s]

New changeset 5466d4a by T. Wouters in branch 'master':
bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. (#889)
5466d4a

[Yhg1s]

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.

[serhiy-storchaka]

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.

[Yhg1s]

New changeset 599bb18 by T. Wouters in branch '3.6':
bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. (#911)
599bb18

[Yhg1s]

New changeset 9273dfe by T. Wouters in branch '3.5':
bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. (#912)
9273dfe

[Yhg1s]

New changeset d694a06 by T. Wouters in branch '2.7':
bpo-29942: Fix the use of recursion in itertools.chain.from_iterable. (#913)
d694a06