bpo-47080: Use atomic groups to simplify fnmatch (GH-32029)

Use re's new atomic groups to greatly simplify the construction of worst-case linear-time patterns.

1 files changed, 5 insertions, 19 deletions

diff --git a/Lib/fnmatch.py b/Lib/fnmatch.py
index 239c749..0f5a41a 100644
--- a/Lib/fnmatch.py
+++ b/Lib/fnmatch.py
@@ -16,12 +16,6 @@ import functools
 
 __all__ = ["filter", "fnmatch", "fnmatchcase", "translate"]
 
-# Build a thread-safe incrementing counter to help create unique regexp group
-# names across calls.
-from itertools import count
-_nextgroupnum = count().__next__
-del count
-
 def fnmatch(name, pat):
     """Test whether FILENAME matches PATTERN.
 
@@ -149,17 +143,10 @@ def translate(pat):
     # Now deal with STAR fixed STAR fixed ...
     # For an interior `STAR fixed` pairing, we want to do a minimal
     # .*? match followed by `fixed`, with no possibility of backtracking.
-    # We can't spell that directly, but can trick it into working by matching
-    #    .*?fixed
-    # in a lookahead assertion, save the matched part in a group, then
-    # consume that group via a backreference. If the overall match fails,
-    # the lookahead assertion won't try alternatives. So the translation is:
-    #     (?=(?P<name>.*?fixed))(?P=name)
-    # Group names are created as needed: g0, g1, g2, ...
-    # The numbers are obtained from _nextgroupnum() to ensure they're unique
-    # across calls and across threads. This is because people rely on the
-    # undocumented ability to join multiple translate() results together via
-    # "|" to build large regexps matching "one of many" shell patterns.
+    # Atomic groups ("(?>...)") allow us to spell that directly.
+    # Note: people rely on the undocumented ability to join multiple
+    # translate() results together via "|" to build large regexps matching
+    # "one of many" shell patterns.
     while i < n:
         assert inp[i] is STAR
         i += 1
@@ -176,8 +163,7 @@ def translate(pat):
             add(".*")
             add(fixed)
         else:
-            groupnum = _nextgroupnum()
-            add(f"(?=(?P<g{groupnum}>.*?{fixed}))(?P=g{groupnum})")
+            add(f"(?>.*?{fixed})")
     assert i == n
     res = "".join(res)
     return fr'(?s:{res})\Z'