← 返回首页
gh-89727: Fix os.fwalk RecursionError on deep trees by jonburdo · Pull Request #100347 · python/cpython · GitHub
Skip to content

Navigation Menu

Toggle navigation
Sign in
Appearance settings
Search or jump to...

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Include my email address so I can be contacted
Cancel Submit feedback

Saved searches

Use saved searches to filter your results more quickly

Cancel Create saved search
Appearance settings
Resetting focus

gh-89727: Fix os.fwalk RecursionError on deep trees#100347

Closed
jonburdo wants to merge 31 commits into
python:mainfrom
jonburdo:iterative-os-fwalk
Closed

gh-89727: Fix os.fwalk RecursionError on deep trees#100347
jonburdo wants to merge 31 commits into
python:mainfrom
jonburdo:iterative-os-fwalk

Conversation

jonburdo commented Dec 19, 2022 •
edited by bedevere-bot
Loading

Copy link
Copy Markdown
Contributor

Use a stack to implement os.fwalk iteratively instead of recursively to avoid hitting recursion limits on deeply nested trees.

Similar to how this is done for os.walk in #99803

bedevere-bot mentioned this pull request Dec 19, 2022
Open

bedevere-bot commented Dec 19, 2022

Copy link
Copy Markdown

Most changes to Python require a NEWS entry.

Please add it using the blurb_it web app or the blurb command-line tool.

bedevere-bot commented Dec 19, 2022

Copy link
Copy Markdown

Most changes to Python require a NEWS entry.

Please add it using the blurb_it web app or the blurb command-line tool.

jonburdo commented Dec 19, 2022 •
edited
Loading

Copy link
Copy Markdown
Contributor Author

TODO:

AlexWaygood reviewed Dec 19, 2022
View reviewed changes
Comment thread Lib/os.py Outdated Show resolved Hide resolved
jonburdo and others added 13 commits December 20, 2022 10:05
fix formatting
90c123b
remove enum from os
570818b
add blurb
30aeed7
pythongh-89727: Fix os.walk RecursionError on deep trees (python#99803) …
55e17b8
Use a stack to implement os.walk iteratively instead of recursively to avoid hitting recursion limits on deeply nested trees.
pythongh-69929: re docs: Add more specific definition of \w (python#9… …
f41cef6
…2015) Co-authored-by: Jelle Zijlstra <jelle.zijlstra@gmail.com>
pythongh-89051: Add ssl.OP_LEGACY_SERVER_CONNECT (python#93927) …
33ba6a5
Co-authored-by: blurb-it[bot] <43283697+blurb-it[bot]@users.noreply.github.com> Co-authored-by: Christian Heimes <christian@python.org> Co-authored-by: Hugo van Kemenade <hugovk@users.noreply.github.com> Fixes python#89051
pythongh-88211: Change lower-case and upper-case to match recommendat… …
f9b6796
…ions in imaplib docs (python#99625)
pythongh-100348: Fix ref cycle in asyncio._SelectorSocketTransport … …
77d160f
…with `_read_ready_cb` (python#100349)
pythongh-99925: Fix inconsistency in json.dumps() error messages (p… …
db820a2
…ythonGH-99926)
Clarify that every thread has its own default context in contextvars (p… …
c39ce63
…ython#99246)
run test_walk_above_recursion_limit for fwalk
8d2befb
set stack outside try-except in fwalk
d29188e
fix comments
2cf7550
AlexWaygood removed request for a team and 1st1 December 20, 2022 15:13
14 hidden items Load more…
gpshead self-requested a review December 24, 2022 02:45
jonburdo marked this pull request as draft January 4, 2023 22:56
jonburdo added 5 commits March 23, 2023 09:03
Merge branch 'main' into iterative-os-fwalk
9eedf9a
add more reliable file descriptor closing logic in os.fwalk …
5ee50c6
Make sure file descriptors get closed if an exception occurs right after the file descriptor was popped from the stack. Also catch exceptions thrown by calling os.close on an already-closed file-descriptor when doing file descriptor cleanup.
use a separate fd_stack for simpler cleanup and error handling
f0f9330
Merge branch 'main' into iterative-os-fwalk
ccfb955
run test_walk_above_recursion_limit with fwalk tests
598bdf9
arhadthedev added the stdlib Standard Library Python modules in the Lib/ directory label Mar 23, 2023

jonburdo commented Mar 23, 2023 •
edited
Loading

Copy link
Copy Markdown
Contributor Author

Note that handling of a single exception should function the same, but repeated errors will interrupt the file descriptor cleanup (closing).

Imagine a user holds down ctrl-c sending a burst of KeyboardExceptions. Previously in the recursive version there were nested try-finally statements making sure close(fd) gets called. I believe each exception might cause one of these close(fd) calls to be missed (if it occurs in the finally before close(fd) is executed), but after the burst of exceptions is over, the remaining calls would be made. Now the cleanup is handled in a loop, so a single exception would end the fd cleanup:

try: ... except: for fd in reversed(fd_stack): try: close(fd) except OSError: pass raise

I'm not sure this is a problem. If I understand correctly, neither versions handles this perfectly. It seemed worth mentioning though.

I thought about changing the except OSError: is this cleanup loop to a bare except:, but then you get kind of a weird, inconsistent behavior where a KeyboardInterrupt that happens to fall just before the try-except starts will end the loop, but one that falls in the try-except won't.

jonburdo marked this pull request as ready for review March 23, 2023 15:16
jonburdo requested review from AlexWaygood and removed request for gpshead March 24, 2023 00:35

jonburdo commented Mar 24, 2023

Copy link
Copy Markdown
Contributor Author

Opening this up for review in response to #89727 (comment)

barneygale reviewed Mar 24, 2023
View reviewed changes
Comment thread Lib/os.py Outdated Show resolved Hide resolved
jonburdo added 4 commits March 24, 2023 17:08
Merge branch 'main' into iterative-os-fwalk
c158be3
make sure we don't close the same fd twice …
6608a6a
If an exception occurred between `close(fd_stack[-1])` and `fd_stack.pop()`, then we would close the fd a second time in the except clause. It would be better to risk leaving the fd open, as the previous implementation of fwalk could
revert to using a single stack instead of a separate ffd stack
d026146
remove unused variable
762c03a
barneygale approved these changes Mar 30, 2023
View reviewed changes

barneygale left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality Hide comment

LGTM, nice work!

barneygale commented Mar 31, 2023 •
edited
Loading

Copy link
Copy Markdown
Contributor

A thought: could you merge _fwalk() into fwalk()? As we're no longer calling _fwalk() recursively, the separation appears pointless, and the yield from indirection will have a small performance cost.

barneygale reviewed Mar 31, 2023
View reviewed changes
Comment thread Lib/os.py Outdated
Comment on lines +563 to +570
except:
for action, value in reversed(stack):
if action is _WalkAction.CLOSE:
try:
close(value)
except OSError:
pass
raise

barneygale Mar 31, 2023

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality Hide comment

Could this be a finally: block?

jonburdo Mar 31, 2023

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality Hide comment

Sure, would you consider that more readable or explicit? I just didn't see any benefit, since this is only needed if an exception occurs. The only functional difference would be that we'd iterate over an empty list if no exceptions occur right?

barneygale Apr 1, 2023

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality Hide comment

I think I'd consider it more explicit, though feel free to wait for another opinion if you'd like.

AlexWaygood Apr 1, 2023

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality Hide comment

I'd also prefer finally here. Not sure if it actually delivers any functional benefit here (can't remember the exact semantics off the top of my head...), but it does feel at least more readable to me.

jonburdo Apr 1, 2023

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality Hide comment

Makes sense, thanks for clarifying. I'll change it to finally. Functionally, I think finally is slightly worse but it's negligible.

In this case, changing to finally is functionally equivalent to adding an else clause with the same for-loop:

try: ... except: for action, value in reversed(stack): ... raise else: for action, value in reversed(stack): ...

If no exception occurs in the try, then stack will be empty and all of the fds will have been closed already. So changing to finally means we're adding a step where we simply iterate over an empty list - unnecessary, but costs almost nothing.

To me, a bare except indicates a cleanup step, but finally is even more explicit, so it probably makes sense here.

barneygale commented Jun 1, 2024

Copy link
Copy Markdown
Contributor

@jonburdo I've fixed this in another PR - #119638. Shamefully I forgot about this PR :(.

Comparing our code, I think we arrived at similar solutions, the main difference being that I moved the lstat() of directory entries our of the scandir() loop. If there's anything you think I've missed in my implementation please let me know or log another PR and I'll review. Thanks and sorry.

barneygale closed this Jun 1, 2024

jonburdo commented Jun 2, 2024

Copy link
Copy Markdown
Contributor Author

@barneygale No worries! Thanks for mentioning it. I meant to follow up on this. I'll take a look at your PR.

Thanks for working on this function and the related ones! It feels great to see these improvements :)

This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

barneygale barneygale approved these changes
AlexWaygood Awaiting requested review from AlexWaygood

Assignees

No one assigned

Labels

awaiting merge stdlib Standard Library Python modules in the Lib/ directory

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Footer

© 2026 GitHub, Inc.