It is possible to create deep directory hierarchies that cannot be removed via shutil.rmtree or walked via os.walk, because these functions exceed the interpreter recursion limit. This may have security implications for web services (e.g. various webdisks) that have to clean up user-created mess or walk through it.

[aep@aep-haswell ~]$ mkdir /tmp/badstuff
[aep@aep-haswell ~]$ cd /tmp/badstuff
[aep@aep-haswell badstuff]$ for x in `seq 2048` ; do mkdir $x ; cd $x ; done
[aep@aep-haswell 103]$ cd
[aep@aep-haswell ~]$ python
Python 3.9.7 (default, Oct 10 2021, 15:13:22) 
[GCC 11.1.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import shutil
>>> shutil.rmtree('/tmp/badstuff')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3.9/shutil.py", line 726, in rmtree
    _rmtree_safe_fd(fd, path, onerror)
  File "/usr/lib/python3.9/shutil.py", line 663, in _rmtree_safe_fd
    _rmtree_safe_fd(dirfd, fullname, onerror)
  File "/usr/lib/python3.9/shutil.py", line 663, in _rmtree_safe_fd
    _rmtree_safe_fd(dirfd, fullname, onerror)
  File "/usr/lib/python3.9/shutil.py", line 663, in _rmtree_safe_fd
    _rmtree_safe_fd(dirfd, fullname, onerror)
  [Previous line repeated 992 more times]
  File "/usr/lib/python3.9/shutil.py", line 642, in _rmtree_safe_fd
    fullname = os.path.join(path, entry.name)
  File "/usr/lib/python3.9/posixpath.py", line 77, in join
    sep = _get_sep(a)
  File "/usr/lib/python3.9/posixpath.py", line 42, in _get_sep
    if isinstance(path, bytes):
RecursionError: maximum recursion depth exceeded while calling a Python object
>>> import os
>>> list(os.walk('/tmp/badstuff'))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3.9/os.py", line 418, in _walk
    yield from _walk(new_path, topdown, onerror, followlinks)
  File "/usr/lib/python3.9/os.py", line 418, in _walk
    yield from _walk(new_path, topdown, onerror, followlinks)
  File "/usr/lib/python3.9/os.py", line 418, in _walk
    yield from _walk(new_path, topdown, onerror, followlinks)
  [Previous line repeated 993 more times]
  File "/usr/lib/python3.9/os.py", line 412, in _walk
    new_path = join(top, dirname)
  File "/usr/lib/python3.9/posixpath.py", line 77, in join
    sep = _get_sep(a)
  File "/usr/lib/python3.9/posixpath.py", line 42, in _get_sep
    if isinstance(path, bytes):
RecursionError: maximum recursion depth exceeded while calling a Python object
>>>

This also affects pathlib.Path.walk()

I am unsure on the bug vs feature classification here. On one side it seems like a clear problem and the fixes don’t change function signatures or the way they are used, but on the other side there is no guarantee that extremely deep hierachies are supported, and I wonder if there could be negative effects from the ocde changes (for example, can the stack list/deque grow extremely large during traversal?).

(Adding PR reviewers: @carljm @brettcannon @serhiy-storchaka)

I don't have strong feelings about calling it a bug vs a feature; I would tend to call it a bug because the function just fails in a subset of cases that aren't obviously outside its domain. I agree that it's a bug that we could just document as a known limitation, though I don't see any reason to do that when the fix is not that difficult. I guess the only real impact of how it's classified is whether the fix would be backported?

I wonder if there could be negative effects from the ocde changes (for example, can the stack list/deque grow extremely large during traversal?)

Sure, but in the current code the Python stack would instead grow very large in the same scenario. And the Python stack frames (plus everything they reference) are almost certainly larger than the stack elements tracked in the iterative version, so if anything I would expect the iterative version to also save memory in the case of a very deep traversal.

Yes exactly, the impact of my question is backporting or not.
Thanks for the reply about the memory concern!

I take it you feel ok about backporting the fix; let’s wait to see what a core dev thinks.

I would classify this as a feature request. There are plenty of things in CPython for which you can you run out of stack space for and it isn't considered a bug in those instances (and that's just part of general limitations that CPython has).

(To be clear, I don't think there's a strong case for backporting this, so reasoning backwards from the conclusion I'm quite happy to call it a feature :P )

Are glob.glob(recursive=True) and pathlib.Path.rglob() also affected?

Are glob.glob(recursive=True) and pathlib.Path.rglob() also affected?

Yes, it looks like it. _rlistdir in Lib/os.py and _RecursiveWildcardSelector in Lib/pathlib.py could be changed to fix it

Adding followjunctions=True to os.walk() works for me

I'll give this a shot.

I spotted a problem with using os.walk() / os.fwalk() to implement rmtree(): for historical reasons, os.walk() places symlinks to directories in the dirnames list even if followlinks is set to False.

This is a wart we removed when we added pathlib.Path.walk(). So there's a possible alternative here:

1. Add a fwalk() method to pathlib.Path
2. Add a follow_junctions argument to pathlib.Path.walk()
3. Implement shutil.rmtree() atop those methods.

I'm going to have a crack at this.

Won't this be significantly slower? On my system, with a tree with ~5000 directories under it, Path.walk takes about 20-30% longer than os.walk. shutil.rmtree takes a lot longer of course, but even a 5% slowdown seems significant.

Why not adjust os.walk to allow returning os.DirEntry objects? This could even be an internal function for now.

os.walk() places symlinks to directories in the dirnames list even if followlinks is set to False.

Preferably dirnames would be ignored when implementing rmtree() using a bottom-up walk. The directories in that list should have been removed already. To get the desired behavior regarding symlinks/junctions, a parameter could be added to os.walk() to enable yielding non-followed symlinks/junctions in filenames instead of dirnames.

Won't this be significantly slower? On my system, with a tree with ~5000 directories under it, Path.walk takes about 20-30% longer than os.walk. shutil.rmtree takes a lot longer of course, but even a 5% slowdown seems significant.

Yep good point, it might be too slow. I also measure Path.walk() as ~20% slower than os.walk, though my implementation of Path.fwalk() is within 5% of os.fwalk().

OTOH, Path.walk() treats symlinks exactly as required by rmtree(), unlike os.walk().

Why not adjust os.walk to allow returning os.DirEntry objects? This could even be an internal function for now.

What does the API look like?

Preferably dirnames would be ignored when implementing rmtree() using a bottom-up walk. The directories in that list should have been removed already.

In both os.walk() and Path.walk(), if an os.DirEntry.is_dir() call succeeds but a subsequence scandir() of the same directory fails, then the directory will appear in dirnames of its parent but not be visited afterward. If rmtree() is then implemented on top, this behaviour causes test failures in test_tempfile.

Arguably Path.walk() could yield a result with empty dirnames and filenames when scandir() fails.

To get the desired behavior regarding symlinks/junctions, a parameter could be added to os.walk() to enable yielding non-followed symlinks/junctions in filenames instead of dirnames.

follow_symlinks_for_realsies? :)

rmtree() would use a bottom-up walk instead of the default top-down walk. Thus if os.scandir() fails for a directory, it does so before dirnames gets emitted for the parent directory. Each directory would be deleted via os.rmdir(dirpath), after first removing all of the yielded filenames. At this point, subdirectories have already been visited and removed, and dirnames would be completely ignored.

follow_symlinks_for_realsies? :)

I was being serious. Maybe strict_dirnames=False.

rmtree() would use a bottom-up walk instead of the default top-down walk. Thus if os.scandir() fails for a directory, it does so before dirnames gets emitted for the parent directory. Each directory would be deleted via os.rmdir(dirpath), after first removing all of the yielded filenames. At this point, subdirectories have already been visited and removed, and dirnames would be completely ignored.

Even with topdown=False, the function internally visits directories from top to bottom (there's no other way), and what I wrote about there being no 3-tuple yielded for un-scandir()able directories still applies.

I was being serious. Maybe strict_dirnames=False.

Sorry, I didn't mean to imply you weren't being serious, only that I thought the naming wasn't obvious and that follow_symlinks should already take care of this. strict_dirnames is OK but I'm generally not a fan of complicating a function signature to allow users to make things behave how they should always have behaved. And I don't really see the need to add this when we already have pathlib.Path.walk(), which gets symlink handling right -- in fact, I believe this improvement was one of the things Brett Cannon thought tipped the balance in favour of adding Path.walk() at all.

what I wrote about there being no 3-tuple yielded for un-scandir()able directories still applies.

Say os.walk() calls scandir('d1'), which contains subdirectory "d2" and no files. It pushes ('d1', ['d2'], []) on the stack (a list), and then it pushes "d2" on the stack. The next iteration pops "d2" from the stack and calls os.scandir('d1/d2'). If we assume it fails, then the default onerror handler of rmtree() re-raises the exception, and rmtree() fails, as it should. If os.scandir('d1/d2') succeeds, and "d2" contains file "f", then ('d1/d2', [], ['f']) gets pushed on the stack. The latter gets yielded to rmtree(), which calls os.unlink('d1/d2/f') and then os.rmdir('d1/d2'). Finally, ('d1', ['d2'], []) gets yielded to rmtree(), which calls os.rmdir('d1'), and we're done.

You're totally right, of course Eryk :-). I must have made a mistake when I tried that approach previously, as when I try it now I get zero test failures from test_tempfile.

I also measure Path.walk() as ~20% slower than os.walk, though my implementation of Path.fwalk() is within 5% of os.fwalk().

Maybe that is close enough to just use Path.fwalk(), although it's probably worth directly comparing any refactor of rmtree to the existing implementation to make sure.

Why not adjust os.walk to allow returning os.DirEntry objects? This could even be an internal function for now.

What does the API look like?

It could simply mean introducing a kwarg like direntry=False. This seems questionable to introduce a kwarg on os.walk itself, but there are a couple of options:

1. Introduce os._walk with direntry=True, so this isn't public-facing. Maybe os.walk just calls os._walk always with direntry=False.
2. More generally, implement whatever walk function would be most useful for rmtree and whatever else should make use of it (copytree maybe) as something like os._walk or os._fwalk. This might essentially be what you've already done with Path.fwalk. On the other hand, implementing a purely bottom up function that only returns os.DirEntry objects for dirs could end up being simpler and faster by enough to be worthwhile.

Either of these options could also help avoid introducing strict_dirnames=False. And whether it's used for this or not, I think Path.fwalk is good to have.

Personally I don't see an ideal solution, which can also comfortably made to be public-facing. Even if pathlib's walk function were as fast as os's , in some cases I specifically want string paths and avoiding Path creation altogether is preferable. I'd personally love to have a public facing os.walk2 or something which implements os.walk as we'd do it now if backwards compatibility weren't an issue. This is probably more extreme, ugly, confusing, etc than simply adding kwargs to os.walk though.

What sort of thing would os._walk(direntry=True) yield? A 2-tuple of (path, entries)? A 3-tuple of (path, direntries, fileentries)? A 4-tuple of (path, dirnames, direntries, filenames)? Bearing in mind we want users to be able to influence the walk by adjusting the directory list, and distinguish between between files/directories/symlinks for the purposes of walking.

public facing os.walk2 or something which implements os.walk as we'd do it now

If new functions are added, I suggest os.path.walk() and os.path.fwalk(). It's where I think they belong, in correspondence with pathlib.Path. I'd prefer if it yielded os.DirEntry instances for dirpath and for the items in dirnames and filenames. There's no point in throwing away the basic stat information. I'd prefer for the onerror handler to match shutil.rmtree(), with three parameters: function, path, and excinfo (or just the exception instance instead of excinfo).

What sort of thing would os._walk(direntry=True) yield?

It would simply replace members of dirnames and filenames with os.DirEntry objects. So this would basically be the current os.walk implementation with a two line change, replacing dirs.append(entry.name) with dirs.append(entry if direntry else entry.name) - same for nondirs. And the same could be done for fwalk.

Of course if we just want a separate implementation, public or not, then we could maybe just get rid of direntry and strict_dirnames kwargs altogether. Instead we handle symlinks properly and always return os.DirEntry objects (maybe still a string path for dirpath though).

I'd be interested to see an implementation! You'd need to support os.walk()'s behaviour of adding symlinks to directories to dirnames but not walking into them, and also rmtree()'s requirement that those symlinks appear in filenames for unlink()ing.

For now I'm -1 on adding new public functions. I wrestled with the os.walk() API when we added pathlib.Path.walk(). I was initially convinced that the API could be significantly improved, but the more I worked it, the more I realised that (path, dirnames, filenames) covers 99% of use cases most elegantly.

It would simply replace members of dirnames and filenames with os.DirEntry objects. So this would basically be the current os.walk implementation with a two line change, replacing dirs.append(entry.name) with dirs.append(entry if direntry else entry.name) - same for nondirs. And the same could be done for fwalk.

Returning os.DirEntry objects doesn't avoid the need to fix the problem with dirnames. Without strict_dirnames, rmtree() would have to try to delete every item in dirnames, of which everything except unfollowed symlinks and junctions was already deleted. OTOH, with strict_dirnames, rmtree() can ignore dirnames.

Of course if we just want a separate implementation, public or not, then we could maybe just get rid of direntry and strict_dirnames kwargs altogether. Instead we handle symlinks properly and always return os.DirEntry objects (maybe still a string path for dirpath though).

The split between dirnames and filenames is convenient. rmtree() would simply loop over filenames to unlink() each item, and ignore dirnames.

I'd prefer to return dirpath as a DirEntry. It has basic stat info that's very cheap on Windows (size, timestamps, file attributes, reparse tag) -- much cheaper than os.[l]stat() -- and it supports __fspath__() for use with os, os.path, and pathlib.Path.

I think my suggestion wasn't clear enough - I also might be missing something.

Returning os.DirEntry objects doesn't avoid the need to fix the problem with dirnames.

Right, I'm discussing these as separate matters. Imagine that we take these steps:

1. Copy the os.walk implementation to os._walk
2. Add direntry=False, which if set to True returns os.DirEntry objects instead of strings.
3. Add strict_dirnames=False.
4. Add followjunctions=True.
   We can create an os._fwalk function similarly. Now we have private functions for things like rmtree. Then we realize we don't need strict_dirnames=False on this function, so we remove strict_dirnames, but keep the functionality of strict_dirnames=True. Maybe we also realize that we don't need direntry=False either, so we remove direntry, keeping the functionality of direntry=True.

Maybe a simpler way to think about this: We want the behavior of Path.walk and @barneygale's Path.fwalk, but without any pathlib objects involved. Instead of Path objects we always return os.DirEntry objects. The benefit here is speed and access to the os.DirEntry objects.

I didn't mean to suggest that we remove the split between dirnames and filenames.

I'd prefer to return dirpath as a DirEntry

You might be right.

Anyways, I need to think a little more about it and maybe I can get an implementation done soon to demonstrate.

My view (open to change) is that we don't need a strict_dirnames argument or a new implementation of walk() that supports this behaviour when we already have pathlib.Path.walk(): a method that exists in part because it implements the strict_dirnames behaviour that we need for rmtree().

I have a WIP implementation using pathlib in #103164

The only downside I can see is performance, and we haven't yet put a number to it. I'll try to do that soon. I think only Windows will be affected, if that. (Is it possible we'll make rmtree() slightly more reliable on Windows by pausing for longer between deletions? 😂). And there are still avenues available to us to improve pathlib performance that could make up the difference.

That said, I'm an ardent pathlib fanboy, so it would be good to get other opinions on this.

Is it possible we'll make rmtree() slightly more reliable on Windows by pausing for longer between deletions?

Microsoft has improved this for the cases in which a file or directory is open with delete sharing (e.g. watching a directory for changes, or a malware scanner). In Windows 10, DeleteFileW() uses a POSIX delete if supported by the filesystem. In Windows 11, RemoveDirectoryW() uses a POSIX delete if the filesystem supports it. For NTFS, a POSIX delete renames the file or directory into a hidden system directory named "\$Extend\$Deleted". For example:

>>> os.mkdir('spam')
>>> h = win32file.CreateFile('spam', 0x0001_0000, 7, None, 3, 0x0200_0000, None)
>>> os.rmdir('spam')
>>> win32file.GetFinalPathNameByHandle(h, 0)
'\\\\?\\C:\\$Extend\\$Deleted\\000B000000041FC810B3AEBC'

OTOH, if a file or directory is opened without delete sharing (e.g. via Python's open() or os.chdir()), then trying to delete it will fail as a sharing violation (error 32). Also, if a file is mapped as an executable image (e.g. a process executable or loaded DLL), then trying to delete it will fail with access denied (error 5). There's nothing we can do about this in general, short of terminating the offending processes. We can use an error handler that retries the delete with an increasing timeout up to maximum total wait time, which is useful for a race condition between closing and deleting a file.

In issue #101601, I proposed adding job object support to subprocess.Popen and better support for sending SIGBREAK to a console process group. This would support cleanly and reliably ensuring that a process tree has terminated before attempting to remove files and directories in use by the processes.

Here's a rough draft of walk/fwalk functions that return os.DirEntry objects: #103234

It needs a couple changes, including the follow_junctions kwarg if we'd want that. It's pretty similar to the current Path.walk and to my os.fwalk function in #100347

@barneygale I think your rmtree implementation and pathlib functions in #103164 look good. I'd honestly love to have public walk functions returning os.DirEntry objects and also Path.fwalk. Of course for now though, we can use whatever private functions seem most reasonable for rmtree.

I've raised this on discourse: https://discuss.python.org/t/using-iterative-filesystem-walk-instead-of-recursive/21955/22