Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Stack overflow in itertools.chain.from_iterable. #74128

Closed
Yhg1s opened this issue Mar 29, 2017 · 9 comments
Closed

Stack overflow in itertools.chain.from_iterable. #74128

Yhg1s opened this issue Mar 29, 2017 · 9 comments
Assignees
@Yhg1s
Labels
3.7 (EOL) end of life type-crash A hard crash of the interpreter, possibly with a core dump

Comments

@Yhg1s
Copy link
Member

Yhg1s commented Mar 29, 2017

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
    Copy link
    Member Author

    Yhg1s commented Mar 29, 2017

    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)

    @Yhg1s Yhg1s added the type-crash A hard crash of the interpreter, possibly with a core dump label Mar 29, 2017
    @serhiy-storchaka serhiy-storchaka added the 3.7 (EOL) end of life label Mar 29, 2017
    @rhettinger
    Copy link
    Contributor

    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
    Copy link
    Member

    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
    Copy link
    Member Author

    Yhg1s commented Mar 30, 2017

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

    @Yhg1s
    Copy link
    Member Author

    Yhg1s commented Mar 30, 2017

    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
    Copy link
    Member

    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
    Copy link
    Member Author

    Yhg1s commented Mar 30, 2017

    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
    Copy link
    Member Author

    Yhg1s commented Mar 30, 2017

    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
    Copy link
    Member Author

    Yhg1s commented Mar 30, 2017

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

    @Yhg1s Yhg1s closed this as completed Mar 30, 2017
    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Assignees

    @Yhg1s Yhg1s

    Labels
    3.7 (EOL) end of life type-crash A hard crash of the interpreter, possibly with a core dump
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    4 participants
    @mdickinson @rhettinger @serhiy-storchaka @Yhg1s