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

Some previous discussion in #70732.