Replace recursion with iteration

python · barneygale · Mar 22, 2023 · Dec 15, 2022 · Dec 15, 2022 · Dec 15, 2022
commit 037a71712f159301e43b443ba72b898be53d052f
@@ -19,6 +19,7 @@
 from operator import attrgetter
 from stat import S_ISDIR, S_ISLNK, S_ISREG, S_ISSOCK, S_ISBLK, S_ISCHR, S_ISFIFO
 from urllib.parse import quote_from_bytes as urlquote_from_bytes
+from collections import deque
 
 
 __all__ = [
@@ -1282,42 +1283,51 @@ def walk(self, top_down=True, on_error=None, follow_symlinks=False):
         return self._walk(top_down, on_error, follow_symlinks)
 
     def _walk(self, top_down, on_error, follow_symlinks):
-        # We may not have read permission for self, in which case we can't
-        # get a list of the files the directory contains. os.walk
-        # always suppressed the exception then, rather than blow up for a
-        # minor reason when (say) a thousand readable directories are still
-        # left to visit. That logic is copied here.
-        try:
-            scandir_it = self._scandir()
-        except OSError as error:
-            if on_error is not None:
-                on_error(error)
-            return
+        stack: ... = deque(((False, self),))
 
-        with scandir_it:
-            dirnames = []
-            filenames = []
-            for entry in scandir_it:
-                try:
-                    is_dir = entry.is_dir(follow_symlinks=follow_symlinks)
-                except OSError:
-                    # Carried over from os.path.isdir().
-                    is_dir = False
+        while stack:
+            is_result, top = stack.pop()
+            if is_result:
+                yield top
+                continue
 
-                if is_dir:
-                    dirnames.append(entry.name)
-                else:
-                    filenames.append(entry.name)
 
-        if top_down:
-            yield self, dirnames, filenames
+            # We may not have read permission for self, in which case we can't
+            # get a list of the files the directory contains. os.walk
+            # always suppressed the exception then, rather than blow up for a
+            # minor reason when (say) a thousand readable directories are still
+            # left to visit. That logic is copied here.
+            try:
+                scandir_it = self._scandir()
+            except OSError as error:
+                if on_error is not None:
+                    on_error(error)
+                continue
+
+            with scandir_it:
+                dirnames = []
+                filenames = []
+                for entry in scandir_it:
+                    try:
+                        is_dir = entry.is_dir(follow_symlinks=follow_symlinks)
+                    except OSError:
+                        # Carried over from os.path.isdir().
+                        is_dir = False
+
+                    if is_dir:
+                        dirnames.append(entry.name)
+                    else:
+                        filenames.append(entry.name)
+
+            if top_down:
+                stack.append((True, (top, dirnames, filenames)))
 
-        for dirname in dirnames:
-            dirpath = self._make_child_relpath(dirname)
-            yield from dirpath._walk(top_down, on_error, follow_symlinks)
+            for dirname in dirnames:
+                dirpath = self._make_child_relpath(dirname)
+                stack.append((False, dirpath))
 
-        if not top_down:
-            yield self, dirnames, filenames
+            if not top_down:
+                stack.append((True, (top, dirnames, filenames)))
 
 
 class PosixPath(Path, PurePosixPath):