Skip to content

[WIP] GH-89727: Fix shutil.rmtree() recursion error on deep trees. #103164

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.

Sign up for GitHub

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

Closed
barneygale wants to merge 27 commits into from
+182 −219
Closed

[WIP] GH-89727: Fix shutil.rmtree() recursion error on deep trees. #103164

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
27 commits
Select commit Hold shift + click to select a range
17f02bb
GH-89727: Fix `shutil.rmtree()` recursion error on deep trees.
barneygale Apr 1, 2023
48dc5db
Delay urllib import
barneygale Apr 1, 2023
6e92b27
Fix up filenames in exceptions
barneygale Apr 1, 2023
c042220
Restore `shutil._rmtree_islink()`
barneygale Apr 1, 2023
e268e89
Tidy up exception handling
barneygale Apr 1, 2023
3f40cb0
Better compatibility with shutil tests.
barneygale Apr 1, 2023
b59bda8
Move main implementation into pathlib
barneygale Apr 1, 2023
c174376
Make `_fwalk()` private, tidy up naming.
barneygale Apr 1, 2023
0e8d8e6
Fix tests
barneygale Apr 1, 2023
fea58ab
Fix missing filename in exception, tidy up more naming.
barneygale Apr 1, 2023
bff0f5e
More cleanup
barneygale Apr 1, 2023
3b21684
Even more tidy-up
barneygale Apr 1, 2023
5abee55
Reduce diff a bit
barneygale Apr 2, 2023
57173d9
Performance improvements
barneygale Apr 2, 2023
58070d9
Simplify rmtree (h/t eryksun)
barneygale Apr 2, 2023
d61baa1
More performance tweaks
barneygale Apr 2, 2023
e983dd7
Make `error._func` private, as it's only intended for `shutil.rmtree()`
barneygale Apr 3, 2023
5387d32
Improve tests
barneygale Apr 3, 2023
75541fb
Improve performance
barneygale Apr 3, 2023
698db60
Merge branch 'main' into pathlib-fwalk
barneygale Apr 3, 2023
74cdd6c
Supply relative paths to `rmdir()` in fd-based walk.
barneygale Apr 7, 2023
c17d07c
Handle rmdir() and unlink() not accepting dir_fd
barneygale Apr 7, 2023
b4f120c
Move rmtree() implementation back into shutil.
barneygale Apr 12, 2023
e856ccb
Restore missing dir_fd check
barneygale Apr 12, 2023
d1e349c
Remove unnecessary change to test
barneygale Apr 12, 2023
63e55e1
Reduce memory usage a bit.
barneygale Apr 12, 2023
f7c5352
Reduce diff
barneygale Apr 12, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
More performance tweaks
  • Loading branch information
@barneygale
barneygale committed Apr 2, 2023
commit d61baa13ae0f3d88c7478ea9c66d588e94fd5955
21 changes: 8 additions & 13 deletions Lib/pathlib.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -209,7 +209,7 @@ class _WalkAction:
CLOSE = object()


def _walk_step(top_down, follow_symlinks, follow_junctions, use_fd, entries, actions):
def _walk_step(top_down, follow_symlinks, follow_junctions, use_fd, actions):
action, value = actions.pop()
if action is _WalkAction.WALK:
path, dir_fd, entry = value
Expand All @@ -227,27 +227,23 @@ def _walk_step(top_down, follow_symlinks, follow_junctions, use_fd, entries, act
error.func = os.scandir
error.filename = str(path)
raise error
if not top_down:
actions.append((_WalkAction.YIELD, result))
with scandir_it:
for entry in scandir_it:
try:
if entry.is_dir(follow_symlinks=follow_symlinks) and (
follow_junctions or not entry.is_junction()):
if entries is not None:
entries.append(entry)
if not top_down:
actions.append((_WalkAction.WALK, (
path._make_child_relpath(entry.name), fd, entry)))
dirnames.append(entry.name)
else:
filenames.append(entry.name)
except OSError:
filenames.append(entry.name)
if top_down:
yield result
else:
actions.append((_WalkAction.YIELD, result))
if entries is not None:
for entry in reversed(entries):
actions.append((_WalkAction.WALK, (path._make_child_relpath(entry.name), fd, entry)))
entries.clear()
else:
for dirname in reversed(dirnames):
actions.append((_WalkAction.WALK, (path._make_child_relpath(dirname), fd, None)))
elif action is _WalkAction.YIELD:
Expand Down Expand Up @@ -1255,7 +1251,7 @@ def walk(self, top_down=True, on_error=None, follow_symlinks=False, follow_junct
actions = [(_WalkAction.WALK, (self, None, None))]
while actions:
try:
yield from _walk_step(top_down, follow_symlinks, follow_junctions, False, None, actions)
yield from _walk_step(top_down, follow_symlinks, follow_junctions, False, actions)
except OSError as error:
if on_error is not None:
on_error(error)
Expand All @@ -1264,12 +1260,11 @@ def walk(self, top_down=True, on_error=None, follow_symlinks=False, follow_junct
def _fwalk(self, top_down=True, *, on_error=None, follow_symlinks=False, dir_fd=None):
"""Walk the directory tree from this directory, similar to os.fwalk()."""
sys.audit("pathlib.Path._fwalk", self, on_error, follow_symlinks, dir_fd)
entries = [] if not top_down and not follow_symlinks else None
actions = [(_WalkAction.WALK, (self, dir_fd, None))]
try:
while actions:
try:
yield from _walk_step(top_down, follow_symlinks, True, True, entries, actions)
yield from _walk_step(top_down, follow_symlinks, True, True, actions)
except OSError as error:
if on_error is not None:
on_error(error)
Expand Down
40 changes: 25 additions & 15 deletions Lib/test/test_pathlib.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2708,21 +2708,31 @@ def test_walk_bottom_up(self):
all = list(self.walk_path.walk( top_down=False))

self.assertEqual(len(all), 4, all)
# We can't know which order SUB1 and SUB2 will appear in.
# Not flipped: SUB11, SUB1, SUB2, TESTFN
# flipped: SUB2, SUB11, SUB1, TESTFN
flipped = all[3][1][0] != "SUB1"
all[3][1].sort()
all[2 - 2 * flipped][-1].sort()
all[2 - 2 * flipped][1].sort()
self.assertEqual(all[3],
(self.walk_path, ["SUB1", "SUB2"], ["tmp1"]))
self.assertEqual(all[flipped],
(self.sub11_path, [], []))
self.assertEqual(all[flipped + 1],
(self.sub1_path, ["SUB11"], ["tmp2"]))
self.assertEqual(all[2 - 2 * flipped],
self.sub2_tree)
seen_testfn = seen_sub1 = seen_sub2 = seen_sub11 = False
for path, dirnames, filenames in all:
if path == self.walk_path:
self.assertTrue(seen_sub1)
self.assertTrue(seen_sub2)
self.assertEqual(sorted(dirnames), ["SUB1", "SUB2"])
self.assertEqual(filenames, ["tmp1"])
seen_testfn = True
elif path == self.sub1_path:
self.assertFalse(seen_testfn)
self.assertTrue(seen_sub11)
self.assertEqual(dirnames, ["SUB11"])
self.assertEqual(filenames, ["tmp2"])
seen_sub1 = True
elif path == self.sub11_path:
self.assertFalse(seen_testfn)
self.assertFalse(seen_sub1)
self.assertEqual(dirnames, [])
self.assertEqual(filenames, [])
seen_sub11 = True
elif path == self.sub2_path:
self.assertFalse(seen_testfn)
self.assertEqual(sorted(dirnames), sorted(self.sub2_tree[1]))
self.assertEqual(sorted(filenames), sorted(self.sub2_tree[2]))
seen_sub2 = True

@os_helper.skip_unless_symlink
def test_walk_follow_symlinks(self):
Expand Down