"fnmatch" exponential execution time

[kleshni]

BPO	40480
Nosy	@tim-one, @nedbat, @asottile
PRs	bpo-40480 "fnmatch" exponential execution time #19908 bpo-40480: restore ability to join fnmatch.translate() results #20049

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/tim-one'
closed_at = <Date 2020-05-06.02:31:54.930>
created_at = <Date 2020-05-03.09:37:07.339>
labels = ['library', '3.9', 'performance']
title = '"fnmatch" exponential execution time'
updated_at = <Date 2020-05-12.14:54:46.462>
user = 'https://bugs.python.org/kleshni'

bugs.python.org fields:

activity = <Date 2020-05-12.14:54:46.462>
actor = 'tim.peters'
assignee = 'tim.peters'
closed = True
closed_date = <Date 2020-05-06.02:31:54.930>
closer = 'tim.peters'
components = ['Library (Lib)']
creation = <Date 2020-05-03.09:37:07.339>
creator = 'kleshni'
dependencies = []
files = []
hgrepos = []
issue_num = 40480
keywords = ['patch']
message_count = 13.0
messages = ['367963', '367982', '367983', '368002', '368075', '368222', '368645', '368655', '368683', '368686', '368695', '368714', '368734']
nosy_count = 4.0
nosy_names = ['tim.peters', 'nedbat', 'Anthony Sottile', 'kleshni']
pr_nums = ['19908', '20049']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue40480'
versions = ['Python 3.9']

[kleshni]

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.

[kleshni]

So the solution is to replace multiple asterisks with a single one
No, this is not a solution. This glob also hangs:

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

And again, Bash and SQLite 3 work perfectly.

[tim-one]

Note that doctest has the same kind of potential problem with matching ellipsis (0 or more characters) in expected output blocks. Backtracking isn't needed at all to resolve patterns of that limited kind, but I don't think Python's re module supports enough gimmicks to disable backtracking.

So instead doctest has its own

_ellipsis_match()

function to do it in worst-case linear time.

[tim-one]

"The trick" with this kind of pattern is that a * should consume as little as possible to allow the next fixed portion to match. Apply that at every stage, and it succeeds or it doesn't. Backtracking can't change that outcome. For, e.g., the shell pattern:

a*bc*d*

a regexp to do this without backtracking would be like this, IF Python's re engine supported "atomic groups" (but it doesn't):

a(?>.*?bc)(?>.*?d).*\Z

The same effect can be gotten in a more convoluted way, via positive lookahead assertions and backreferencing (which Python's re engine does support):

a(?=(.*?bc))\1(?=(.*?d))\2.*\Z

Assertions are "one and done": if the overall match fails, assertions don't try alternatives.

So that's _a_ way to proceed. I'm unclear on that it's worth it, though. Stuff like "*a*a*a*a*a*a*" is just hard to swallow as a shell pattern that would occur in real life.

[tim-one]

Changed version to 3.9, because anything done would change the regexp generated, and fnmatch.translate()` makes that regexp visible.