pathlib match, full_match and glob take exponential time on short patterns because glob.translate skips fnmatch's atomic-group rewrite #159717

Bug report

PurePath.match, PurePath.full_match and Path.glob take exponential time on short patterns with several *, because glob.translate() does not apply the atomic-group rewrite that fnmatch uses to prevent catastrophic backtracking (gh-84660). glob.translate() keeps only the parts list from fnmatch._translate() and discards the star indices, so every * becomes a plain backtracking [^/]*. fnmatch.fnmatchcase and glob.glob (which goes through fnmatch.filter) are fast on the same inputs.

import fnmatch, glob, os, tempfile, time
from pathlib import Path, PurePosixPath

pat = '*a' * 8 + '*b'          # 18 characters
print('translate:', glob.translate(pat))

def t(f):
    s = time.perf_counter(); f(); return f'{time.perf_counter() - s:.4f} s'

for n in (28, 36, 44, 52):
    name = 'a' * n
    print(n, "full_match", t(lambda: PurePosixPath(name).full_match(pat)),
          '| match', t(lambda: PurePosixPath(name).match(pat)),
          '| fnmatchcase', t(lambda: fnmatch.fnmatchcase(name, pat)))

with tempfile.TemporaryDirectory() as d:
    open(os.path.join(d, 'a' * 44), 'w').close()
    print('Path.glob  ', t(lambda: list(Path(d).glob(pat))))
    print('glob.glob  ', t(lambda: glob.glob(pat, root_dir=d)))

Python 3.14.8 (3.15.0 gives the same figures within noise):

translate: (?s:(?!\.)[^/]*a[^/]*a[^/]*a[^/]*a[^/]*a[^/]*a[^/]*a[^/]*a[^/]*b)\z
28 full_match 0.0399 s | match 0.0320 s | fnmatchcase 0.0001 s
36 full_match 0.2907 s | match 0.2899 s | fnmatchcase 0.0000 s
44 full_match 1.6570 s | match 1.6754 s | fnmatchcase 0.0000 s
52 full_match 7.1611 s | match 7.1651 s | fnmatchcase 0.0000 s
Path.glob   1.6258 s
glob.glob   0.0000 s

The time grows roughly as the binomial of the name length over the number of stars, so a few more characters in the name or one more *a in the pattern push it to minutes, holding the GIL for the whole duration.

First affected release is 3.13.0, where glob.translate() was added (gh-72904) and pathlib started matching through it. 3.11 PurePath.match is not affected.

Cause, at the default branch: Lib/glob.py in translate():

results.extend(fnmatch._translate(part, f'{not_sep}*', not_sep)[0])

Index [0] keeps the parts and drops star_indices, so the (?>.*?...) atomic grouping in fnmatch._join_translated_parts() never applies. _compile_pattern in Lib/glob.py compiles the result for _StringGlobber, which pathlib builds in full_match, match and glob. The gh-84660 regression test test_slow_fnmatch in Lib/test/test_fnmatch.py has no glob or pathlib counterpart.

Suggested fix: build each segment in glob.translate() from both the parts and the star indices returned by fnmatch._translate(), the way fnmatch._join_translated_parts() does, wrapping every interior STAR fixed pair in an atomic group with the separator-excluding star, so that segment matching cannot backtrack. Add glob and pathlib counterparts of test_slow_fnmatch with the pattern above. I can open a PR for this if useful.

CPython versions tested on:

3.13, 3.14, 3.15

Operating systems tested on:

Linux

Linked PRs

• gh-159717: Avoid excessive backtracking in glob pattern translation #159861