[New-bugs-announce] [issue40480] "fnmatch" exponential execution time

[kleshni]

New submission from kleshni <kleshni at protonmail.ch>:

Hello. The following code hangs:

import fnmatch
fnmatch.fnmatchcase("a" * 32, "*" * 16 + "b")

Measurements show that its execution time rises exponentially with the number of asterisks. Bash and SQLite 3 process this glob instantly.

This is because "fnmatchcase" generates a regular expression with repeated dots:

(?s:.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*b)\\Z

It's equivalent to:

(?s:.*b)\\Z

But works in exponential time. So the solution is to replace multiple asterisks with a single one, so the latter regexp is generated instead.

----------
components: Library (Lib)
messages: 367963
nosy: kleshni
priority: normal
severity: normal
status: open
title: "fnmatch" exponential execution time
type: performance
versions: Python 3.8

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue40480>
_______________________________________