[issue40480] "fnmatch" exponential execution time

Tim Peters added the comment: Ned, I'm happy to do this. While the ability to join wasn't documented, it's not an unreasonable expectation. I'm not sure it's possible to fail _unless_ the regexps use named groups (and/or numbered backreferences) - and nobody in their right mind would expect

[issue40480] "fnmatch" exponential execution time

Ned Batchelder added the comment: Wow, thanks Tim. To be honest, I was coming around to your original point of view that it was too much to promise that these regexes could be combined the way I'm doing it. If we have to undo this latest change, I can live with it. -- _

[issue40480] "fnmatch" exponential execution time

Tim Peters added the comment: New changeset b1b4c790e7d3b5f4244450aefe3d8f01710c13f7 by Tim Peters in branch 'master': bpo-40480: restore ability to join fnmatch.translate() results (GH-20049) https://github.com/python/cpython/commit/b1b4c790e7d3b5f4244450aefe3d8f01710c13f7 --

[issue40480] "fnmatch" exponential execution time

Change by Tim Peters : -- pull_requests: +19358 pull_request: https://github.com/python/cpython/pull/20049 ___ Python tracker ___ __

[issue40480] "fnmatch" exponential execution time

Tim Peters added the comment: I don't want something probabilistic. Fix it or don't ;-) One thing that would work, but at the cost of non-determinism: do the same as now, but obtain the number part of the group name by applying next() to a module-global private instance of itertools.count(

[issue40480] "fnmatch" exponential execution time

Anthony Sottile added the comment: one way might be to give the groups "unique" names (perhaps hashing the input string?) ((this is what I attempted to do in a little bit of code which tried to "backport" (group)*+ and (group)++)) -- nosy: +Anthony Sottile _

[issue40480] "fnmatch" exponential execution time

Tim Peters added the comment: Ned, would it be possible to rewrite code of the form: if giant pasted regexp matches: to: if any(p matches for p in patterns): That should work under any version of Python. There's no guarantee that regexps _can_ be pasted together and still work,

[issue40480] "fnmatch" exponential execution time

Ned Batchelder added the comment: This change has caused a problem for coverage.py. The full details are here: https://github.com/nedbat/coveragepy/issues/988#issuecomment-626926513 Coverage.py combines fnmatch-produced regexes by joining them with pipes into one larger regex. The \ group

[issue40480] "fnmatch" exponential execution time

Change by Tim Peters : -- assignee: -> tim.peters resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___ _

[issue40480] "fnmatch" exponential execution time

Tim Peters added the comment: New changeset b9c46a2c2d7fc68457bff641f78932d66f5e5f59 by Tim Peters in branch 'master': bpo-40480 "fnmatch" exponential execution time (GH-19908) https://github.com/python/cpython/commit/b9c46a2c2d7fc68457bff641f78932d66f5e5f59 --

[issue40480] "fnmatch" exponential execution time

Change by Tim Peters : -- keywords: +patch pull_requests: +19223 stage: needs patch -> patch review pull_request: https://github.com/python/cpython/pull/19908 ___ Python tracker __

[issue40480] "fnmatch" exponential execution time

Tim Peters added the comment: Changed version to 3.9, because anything done would change the regexp generated, and fnmatch.translate()` makes that regexp visible. -- stage: -> needs patch versions: +Python 3.9 -Python 3.8 ___ Python tracker

[issue40480] "fnmatch" exponential execution time

Tim Peters added the comment: "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:

[issue40480] "fnmatch" exponential execution time

Tim Peters added the comment: 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 gim

[issue40480] "fnmatch" exponential execution time

kleshni added the comment: >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. -- ___ Pyt

[issue40480] "fnmatch" exponential execution time

New submission from 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"