GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — gh-89727: Fix os.fwalk RecursionError on deep trees by jonburdo · Pull Request #100347 · python/cpython

Conversation

@jonburdo

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

Uh oh!

There was an error while loading. Please reload this page.

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

  • Issue: Change shutil.rmtree and os.walk to support very deep hierarchies #89727

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
jonburdo added 2 commits December 19, 2022 09:40
@jonburdo
fix os.walk RecursionError on deep trees
d9f6f44
@jonburdo
use _WalkAction enum
61b8078
@bedevere-bot bedevere-bot mentioned this pull request Dec 19, 2022
Change shutil.rmtree and os.walk to support very deep hierarchies #89727
Open
@bedevere-bot bedevere-bot added the awaiting review label Dec 19, 2022
@bedevere-bot

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.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@jonburdo
Merge branch 'main' into iterative-os-fwalk
d5e2042
@bedevere-bot

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.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@jonburdo

jonburdo commented Dec 19, 2022 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor Author

TODO:

  • Once gh-89727: Fix os.walk RecursionError on deep trees #99803 is merged, this line can be removed so that FwalkTests will run test_walk_above_recursion_limit to prevent a regression
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

AlexWaygood
AlexWaygood reviewed Dec 19, 2022
View reviewed changes
Comment thread Lib/os.py Resolved

Uh oh!

There was an error while loading. Please reload this page.

jonburdo and others added 13 commits December 20, 2022 10:05
@jonburdo
fix formatting
90c123b
@jonburdo
remove enum from os
570818b
@jonburdo
add blurb
30aeed7
@jonburdo
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.
@slateny @JelleZijlstra @jonburdo
pythongh-69929: re docs: Add more specific definition of \w (python#9…
f41cef6
…2015)

Co-authored-by: Jelle Zijlstra <[email protected]>
@graingert @blurb-it
@tiran @hugovk @jonburdo
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 <[email protected]>
Co-authored-by: Hugo van Kemenade <[email protected]>
Fixes python#89051
@tbwolfe @jonburdo
pythongh-88211: Change lower-case and upper-case to match recommendat…
f9b6796
…ions in imaplib docs (python#99625)
@rkojedzinszky @jonburdo
pythongh-100348: Fix ref cycle in asyncio._SelectorSocketTransport …
77d160f
…with `_read_ready_cb` (python#100349)
@fnesveda @jonburdo
pythongh-99925: Fix inconsistency in json.dumps() error messages (p…
db820a2
…ythonGH-99926)
@pablogsal @jonburdo
Clarify that every thread has its own default context in contextvars (p…
c39ce63
…ython#99246)
@jonburdo
run test_walk_above_recursion_limit for fwalk
8d2befb
@jonburdo
set stack outside try-except in fwalk
d29188e
@jonburdo
fix comments
2cf7550
@jonburdo
jonburdo requested review from a team, 1st1, asvetlov, gvanrossum and kumaraditya303 as code owners December 20, 2022 15:08
@jonburdo
Merge branch 'main' into iterative-os-fwalk
f2cca94
@AlexWaygood
AlexWaygood removed request for a team and 1st1 December 20, 2022 15:13
@gpshead
gpshead self-requested a review December 24, 2022 02:45
@jonburdo
jonburdo marked this pull request as draft January 4, 2023 22:56
jonburdo added 5 commits March 23, 2023 09:03
@jonburdo
Merge branch 'main' into iterative-os-fwalk
9eedf9a
@jonburdo
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.
@jonburdo
use a separate fd_stack for simpler cleanup and error handling
f0f9330
@jonburdo
Merge branch 'main' into iterative-os-fwalk
ccfb955
@jonburdo
run test_walk_above_recursion_limit with fwalk tests
598bdf9
@arhadthedev arhadthedev added the stdlib Standard Library Python modules in the Lib/ directory label Mar 23, 2023
@jonburdo

jonburdo commented Mar 23, 2023 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

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.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

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

jonburdo commented Mar 24, 2023

Copy link
Copy Markdown
Contributor Author

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

barneygale
barneygale reviewed Mar 24, 2023
View reviewed changes
Comment thread Lib/os.py Resolved

Uh oh!

There was an error while loading. Please reload this page.

jonburdo added 4 commits March 24, 2023 17:08
@jonburdo
Merge branch 'main' into iterative-os-fwalk
c158be3
@jonburdo
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
@jonburdo
revert to using a single stack instead of a separate ffd stack
d026146
@jonburdo
remove unused variable
762c03a
barneygale
barneygale approved these changes Mar 30, 2023
View reviewed changes

@barneygale barneygale left a comment

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

LGTM, nice work!

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@bedevere-bot bedevere-bot added awaiting merge and removed awaiting review labels Mar 30, 2023
@barneygale

barneygale commented Mar 31, 2023 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

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.

jonburdo reacted with thumbs up emoji
All reactions
  • 👍 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

barneygale
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 barneygale Mar 31, 2023

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Could this be a finally: block?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

AlexWaygood reacted with thumbs up emoji
All reactions
  • 👍 1 reaction

@jonburdo jonburdo Mar 31, 2023

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

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?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@barneygale barneygale Apr 1, 2023

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

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

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@AlexWaygood AlexWaygood Apr 1, 2023

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

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.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@jonburdo jonburdo Apr 1, 2023

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

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.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
jonburdo and others added 4 commits April 1, 2023 11:16
@jonburdo
get rid of unnecessary os._fwalk
045fd88
@jonburdo
change except clause to finally clause in os.fwalk
f3f793a
@AlexWaygood
Merge branch 'main' into iterative-os-fwalk
dfb9685
@erlend-aasland
Merge branch 'main' into iterative-os-fwalk
0ebc475
@barneygale

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.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@barneygale barneygale closed this Jun 1, 2024
@jonburdo

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 :)

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@barneygale barneygale barneygale approved these changes
@AlexWaygood AlexWaygood Awaiting requested review from AlexWaygood

Uh oh!

There was an error while loading. Please reload this page.

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.

Uh oh!

There was an error while loading. Please reload this page.

12 participants

@jonburdo @bedevere-bot @barneygale @AlexWaygood @arhadthedev @slateny @graingert @tbwolfe @rkojedzinszky @fnesveda @pablogsal @erlend-aasland
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.