From 45587df8d0a129fb580cdd591f514efb09f49305 Mon Sep 17 00:00:00 2001
From: Barney Gale <barney.gale@gmail.com>
Date: Wed, 29 May 2024 21:53:08 +0100
Subject: [3.12] GH-89727: Partially fix `shutil.rmtree()` recursion error on
 deep trees (GH-119634) (#119749)

* GH-89727: Partially fix `shutil.rmtree()` recursion error on deep trees (#119634)

Make `shutil._rmtree_unsafe()` call `os.walk()`, which is implemented
without recursion.

`shutil._rmtree_safe_fd()` is not affected and can still raise a recursion
error.

Co-authored-by: Jelle Zijlstra <jelle.zijlstra@gmail.com>
(cherry picked from commit a150679f90c6e3f017bd75cac3b8f727063cc4aa)
---
 Lib/os.py                                          |  9 +++++-
 Lib/shutil.py                                      | 33 +++++++---------------
 Lib/test/test_shutil.py                            | 11 ++++++++
 .../2024-05-29-20-42-17.gh-issue-89727.5lPTTW.rst  |  3 ++
 4 files changed, 32 insertions(+), 24 deletions(-)
 create mode 100644 Misc/NEWS.d/next/Library/2024-05-29-20-42-17.gh-issue-89727.5lPTTW.rst

diff --git a/Lib/os.py b/Lib/os.py
index 7ee7d69..664d8b2 100644
--- a/Lib/os.py
+++ b/Lib/os.py
@@ -279,6 +279,10 @@ def renames(old, new):
 
 __all__.extend(["makedirs", "removedirs", "renames"])
 
+# Private sentinel that makes walk() classify all symlinks and junctions as
+# regular files.
+_walk_symlinks_as_files = object()
+
 def walk(top, topdown=True, onerror=None, followlinks=False):
     """Directory tree generator.
 
@@ -380,7 +384,10 @@ def walk(top, topdown=True, onerror=None, followlinks=False):
                     break
 
                 try:
-                    is_dir = entry.is_dir()
+                    if followlinks is _walk_symlinks_as_files:
+                        is_dir = entry.is_dir(follow_symlinks=False) and not entry.is_junction()
+                    else:
+                        is_dir = entry.is_dir()
                 except OSError:
                     # If is_dir() raises an OSError, consider the entry not to
                     # be a directory, same behaviour as os.path.isdir().
diff --git a/Lib/shutil.py b/Lib/shutil.py
index deb9d3b..23ef782 100644
--- a/Lib/shutil.py
+++ b/Lib/shutil.py
@@ -617,31 +617,18 @@ else:
 
 # version vulnerable to race conditions
 def _rmtree_unsafe(path, onexc):
-    try:
-        with os.scandir(path) as scandir_it:
-            entries = list(scandir_it)
-    except OSError as err:
-        onexc(os.scandir, path, err)
-        entries = []
-    for entry in entries:
-        fullname = entry.path
-        try:
-            is_dir = entry.is_dir(follow_symlinks=False)
-        except OSError:
-            is_dir = False
-
-        if is_dir and not entry.is_junction():
+    def onerror(err):
+        onexc(os.scandir, err.filename, err)
+    results = os.walk(path, topdown=False, onerror=onerror, followlinks=os._walk_symlinks_as_files)
+    for dirpath, dirnames, filenames in results:
+        for name in dirnames:
+            fullname = os.path.join(dirpath, name)
             try:
-                if entry.is_symlink():
-                    # This can only happen if someone replaces
-                    # a directory with a symlink after the call to
-                    # os.scandir or entry.is_dir above.
-                    raise OSError("Cannot call rmtree on a symbolic link")
+                os.rmdir(fullname)
             except OSError as err:
-                onexc(os.path.islink, fullname, err)
-                continue
-            _rmtree_unsafe(fullname, onexc)
-        else:
+                onexc(os.rmdir, fullname, err)
+        for name in filenames:
+            fullname = os.path.join(dirpath, name)
             try:
                 os.unlink(fullname)
             except OSError as err:
diff --git a/Lib/test/test_shutil.py b/Lib/test/test_shutil.py
index 51eccb8..926485d 100644
--- a/Lib/test/test_shutil.py
+++ b/Lib/test/test_shutil.py
@@ -686,6 +686,17 @@ class TestRmTree(BaseTest, unittest.TestCase):
         shutil.rmtree(TESTFN)
         self.assertFalse(os.path.exists(TESTFN))
 
+    @unittest.skipIf(shutil._use_fd_functions, "fd-based functions remain unfixed (GH-89727)")
+    def test_rmtree_above_recursion_limit(self):
+        recursion_limit = 40
+        # directory_depth > recursion_limit
+        directory_depth = recursion_limit + 10
+        base = os.path.join(TESTFN, *(['d'] * directory_depth))
+        os.makedirs(base)
+
+        with support.infinite_recursion(recursion_limit):
+            shutil.rmtree(TESTFN)
+
 
 class TestCopyTree(BaseTest, unittest.TestCase):
 
diff --git a/Misc/NEWS.d/next/Library/2024-05-29-20-42-17.gh-issue-89727.5lPTTW.rst b/Misc/NEWS.d/next/Library/2024-05-29-20-42-17.gh-issue-89727.5lPTTW.rst
new file mode 100644
index 0000000..3b73d27
--- /dev/null
+++ b/Misc/NEWS.d/next/Library/2024-05-29-20-42-17.gh-issue-89727.5lPTTW.rst
@@ -0,0 +1,3 @@
+Partially fix issue with :func:`shutil.rmtree` where a :exc:`RecursionError`
+is raised on deep directory trees. A recursion error is no longer raised
+when :data:`!rmtree.avoids_symlink_attacks` is false.
-- 
cgit v0.12