Gentoo Manifest regex takes superlinear time on runs of whitespace #3473

Summary

The gentoo-manifest test in polyfile/magic_defs/gentoo:38 takes superlinear time when the data after the tag is a long run of whitespace. A 306-byte input takes about 4 seconds, and a 506-byte input takes about 28 seconds. The regex window is 8 KiB, so an input a few kilobytes long does not finish.

This is a different root cause from #3411, which is about polyfile/magic_defs/c-lang:78, and it is not fixed by the change in that pull request.

Reproducer

import time

from polyfile.magic import MagicMatcher

data = b"DIST " + b" " * 500 + b"\n"

start = time.perf_counter()
for match in MagicMatcher.DEFAULT_INSTANCE.match(data):
    _ = set(match.mimetypes)
print(f"{len(data)} bytes took {time.perf_counter() - start:.1f} seconds")

Output on master (commit ffdf476):

506 bytes took 27.7 seconds

Cause

polyfile/magic_defs/gentoo:9-18 invokes the named test gentoo-manifest as soon as an input starts with AUX , DATA , DIST , EBUILD , or MANIFEST . That named test is:

0	name	gentoo-manifest
>&0	regex	[[:space:]]+[[:print:]]+[[:space:]]+[[:digit:]]+[[:space:]]+[[:alnum:]]+[[:space:]]+[[:xdigit:]]{32}	Gentoo Manifest (GLEP 74)

[[:print:]] and [[:alnum:]] both overlap [[:space:]], and the pattern chains four + quantifiers over overlapping classes. Python's re is a backtracking engine, so the number of ways to split a run of spaces across those quantifiers grows as a polynomial of high degree. Measured against a buffer of only spaces:

libmagic itself is not affected, because it compiles its tests with a POSIX engine rather than a backtracking one.

Environment

• PolyFile at commit ffdf476
• Python 3.14