GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing github.com — Python 3.11.0b3 chockes on regex sub from rjsmin, time grows seemingly exponentially · Issue #94675 · python/cpython

Python 3.11.0b3 chockes on regex sub from rjsmin, time grows seemingly exponentially #94675

New issue

Copy link

New issue

Copy link

Closed

Python 3.11.0b3 chockes on regex sub from rjsmin, time grows seemingly exponentially#94675

Copy link

Labels

testsTests in the Lib/test dirTests in the Lib/test dirtopic-regextype-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error

Description

hroncok

opened

on Jul 7, 2022

Issue body actions

Bug report

When building chromium in Fedora 37 with Python 3.11.0b3, the build hangs seemingly forever.

While isolating the hang, we've noticed it happens in rjsmin, at https://github.com/ndparker/rjsmin/blob/1.2.0/rjsmin.py#L361

I've further reduced the javascript input as much as I could ~~but I kept the regex pattern intact~~.

Here's the reporucer:

import re, sys

# pattern from rjsmin
# Copyright 2011 - 2021 André Malo or his licensors, as applicable.
# Apache License Version 2.0
# https://github.com/ndparker/rjsmin/blob/1.2.0/rjsmin.py#L196
pattern = '(?<=[(,=:\\[!&|?{};\\r\\n+*-])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:(?:(?://[^\\r\\n]*)?[\\r\\n])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)*((?:/(?![\\r\\n/*])[^/\\\\\\[\\r\\n]*(?:(?:\\\\[^\\r\\n]|(?:\\[[^\\\\\\]\\r\\n]*(?:\\\\[^\\r\\n][^\\\\\\]\\r\\n]*)*\\]))[^/\\\\\\[\\r\\n]*)*/[a-z]*))((?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:(?:(?://[^\\r\\n]*)?[\\r\\n])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)+(?=[^\\000-\\040&)+,.:;=?\\]|}-]))?'
# (originally reported as) pattern = '([^\\047"\\140/\\000-\\040]+)|((?:(?:\\047[^\\047\\\\\\r\\n]*(?:\\\\(?:[^\\r\\n]|\\r?\\n|\\r)[^\\047\\\\\\r\\n]*)*\\047)|(?:"[^"\\\\\\r\\n]*(?:\\\\(?:[^\\r\\n]|\\r?\\n|\\r)[^"\\\\\\r\\n]*)*")|(?:\\140[^\\140\\\\]*(?:\\\\(?:[^\\r\\n]|\\r?\\n|\\r)[^\\140\\\\]*)*\\140))[^\\047"\\140/\\000-\\040]*)|(?<=[)])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:(?:(?://[^\\r\\n]*)?[\\r\\n])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)*((?:/(?![\\r\\n/*])[^/\\\\\\[\\r\\n]*(?:(?:\\\\[^\\r\\n]|(?:\\[[^\\\\\\]\\r\\n]*(?:\\\\[^\\r\\n][^\\\\\\]\\r\\n]*)*\\]))[^/\\\\\\[\\r\\n]*)*/[a-z]*))(?=(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:(?:(?://[^\\r\\n]*)?[\\r\\n])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)*\\.(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:(?:(?://[^\\r\\n]*)?[\\r\\n])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)*[a-z])|(?<=[(,=:\\[!&|?{};\\r\\n+*-])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:(?:(?://[^\\r\\n]*)?[\\r\\n])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)*((?:/(?![\\r\\n/*])[^/\\\\\\[\\r\\n]*(?:(?:\\\\[^\\r\\n]|(?:\\[[^\\\\\\]\\r\\n]*(?:\\\\[^\\r\\n][^\\\\\\]\\r\\n]*)*\\]))[^/\\\\\\[\\r\\n]*)*/[a-z]*))((?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:(?:(?://[^\\r\\n]*)?[\\r\\n])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)+(?=[^\\000-\\040&)+,.:;=?\\]|}-]))?|(?<=[\\000-#%-,./:-@\\[-^\\140{-~-]return)(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:((?:(?://[^\\r\\n]*)?[\\r\\n]))(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)*((?:/(?![\\r\\n/*])[^/\\\\\\[\\r\\n]*(?:(?:\\\\[^\\r\\n]|(?:\\[[^\\\\\\]\\r\\n]*(?:\\\\[^\\r\\n][^\\\\\\]\\r\\n]*)*\\]))[^/\\\\\\[\\r\\n]*)*/[a-z]*))((?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:(?:(?://[^\\r\\n]*)?[\\r\\n])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)+(?=[^\\000-\\040&)+,.:;=?\\]|}-]))?|(?<=[^\\000-!#%&(*,./:-@\\[\\\\^{|~])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:((?:(?://[^\\r\\n]*)?[\\r\\n]))(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)+(?=[^\\000-\\040"#%-\\047)*,./:-@\\\\-^\\140|-~])|(?<=[^\\000-#%-,./:-@\\[-^\\140{-~-])((?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/)))+(?=[^\\000-#%-,./:-@\\[-^\\140{-~-])|(?<=\\+)((?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/)))+(?=\\+)|(?<=-)((?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/)))+(?=-)|(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))+|(?:(?:(?://[^\\r\\n]*)?[\\r\\n])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)+'


input_data = """a(function() {{
      {}
}});
""".format('/' * int(sys.argv[1]))

print(re.compile(pattern).sub('', input_data))

The original input reduced from Chromium's JavaScript file looks like:

a(function() {
      //////////////////////////////////////////////////////////////////////////
});

And here how long it takes with Python 3.10.5 and 3.11.0b3 for a reduced number of slashes.

$ time python3.10 reproducer.py 30
real    0m0,033s

$ time python3.11 reproducer.py 30
real    0m0,082s

$ time python3.10 reproducer.py 40
real    0m0,034s

$ time python3.11 reproducer.py 40
real    0m6,902s

$ time python3.10 reproducer.py 45
real    0m0,032s

$ time python3.11 reproducer.py 45
real    1m25,004s

$ time python3.10 reproducer.py 50
real    0m0,031s

$ time python3.11 reproducer.py 50
??? killed after 10+ minutes

For 74 slashes, I guess it would run forever.

Your environment

CPython versions tested on: 3.11.0b3
Operating system and architecture: Fedora Linux 35 or 37, x86_64

Activity

hroncok
added
type-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error
on Jul 7, 2022

hroncok commented on Jul 7, 2022

hroncok

on Jul 7, 2022

ContributorAuthor

More actions

A more "real" example is to pipe the javascript input to https://github.com/ndparker/rjsmin/blob/1.2.0/rjsmin.py

$ cat file_to_pipe_in.js 
a(function() {
      /////////////////////////////////////////////
});

$ time python3.10 rjsmin.py < file_to_pipe_in.js
a(function(){});
real	0m0,039s
user	0m0,031s
sys	0m0,009s

$ time python3.11 rjsmin.py < file_to_pipe_in.js
...

hroncok commented on Jul 7, 2022

hroncok

on Jul 7, 2022

ContributorAuthor

More actions

I've simplified the regex to:

pattern = '(?<=[(,=:\\[!&|?{};\\r\\n+*-])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:(?:(?://[^\\r\\n]*)?[\\r\\n])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)*((?:/(?![\\r\\n/*])[^/\\\\\\[\\r\\n]*(?:(?:\\\\[^\\r\\n]|(?:\\[[^\\\\\\]\\r\\n]*(?:\\\\[^\\r\\n][^\\\\\\]\\r\\n]*)*\\]))[^/\\\\\\[\\r\\n]*)*/[a-z]*))((?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*(?:(?:(?://[^\\r\\n]*)?[\\r\\n])(?:[\\000-\\011\\013\\014\\016-\\040]|(?:/\\*[^*]*\\*+(?:[^/*][^*]*\\*+)*/))*)+(?=[^\\000-\\040&)+,.:;=?\\]|}-]))?'

The following ones are even shorter and exhibit the same behavior but slightly different times, so I am not editing it in the original report:

pattern = r'(?<=[({}])(?:(?:(?://[^\n]*)?[\n])(?:[\000-\040])*)*((?:/[^/\[\n]*(?:(?:[^\n]|(?:\[\n]*(?:]*)*\]))[^/\[]*)*/))((?:(?:(?://[^\n]*)?[\n])(?:[\000-\040]|(?:/\*[^*]*\*+(?:[^/*]\*+)*/))*)+(?=[^\000-\040&)+,.:;=?\]|}-]))'
pattern = r'(?<=[({}])(((//[^\n]*)?[\n])([\000-\040])*)*((/[^/\[\n]*(([^\n]|(\[\n]*(]*)*\]))[^/\[]*)*/))((((//[^\n]*)?[\n])([\000-\040]|(/\*[^*]*\*+([^/*]\*+)*/))*)+(?=[^\000-\040);\]}]))'

AlexWaygood
added
topic-regex

3.11only security fixesonly security fixes

3.12only security fixesonly security fixes
on Jul 8, 2022
hauntsaninja commented on Jul 8, 2022
hauntsaninja
on Jul 8, 2022
Contributor
More actions
Can you repro on latest main?
A slowdown in Chromium build was previously reported here #91404 (comment)
I believe #93928 did not make beta 3
hauntsaninja commented on Jul 8, 2022
hauntsaninja
on Jul 8, 2022
Contributor
More actions
(If #93928 did indeed fix, it would be nice to add your reduced example as a test case!)
hroncok commented on Jul 8, 2022
hroncok
on Jul 8, 2022
ContributorAuthor
More actions
Will test.
hroncok commented on Jul 8, 2022
hroncok
on Jul 8, 2022
ContributorAuthor
More actions
This is fixed on main.
hroncok commented on Jul 8, 2022
hroncok
on Jul 8, 2022
ContributorAuthor
More actions
#93928 also fixes it on 3.11
hroncok
changed the title ~~[-]Python 3.11 chockes on regex sub from rjsmin, time grows seemingly exponentially[/-]~~ [+]Python 3.11.0b3 chockes on regex sub from rjsmin, time grows seemingly exponentially[/+] on Jul 8, 2022
AlexWaygood
added
testsTests in the Lib/test dirTests in the Lib/test dir
and removed
3.11only security fixesonly security fixes

3.12only security fixesonly security fixes
on Jul 8, 2022
hroncok commented on Jul 8, 2022
hroncok
on Jul 8, 2022
ContributorAuthor
More actions
@hauntsaninja Any idea how are the "does not take too long" cases handled in cpython tests?
hroncok commented on Jul 8, 2022
hroncok
on Jul 8, 2022
ContributorAuthor
More actions
I've added #94685 -- hoping that the general timeout thing would stop it on b3
hroncok
added 3 commits that reference this issue on Jul 8, 2022
fixup! pythongh-94675: Add a regression test for rjsmin re slowdown
ee602ea
00385: pythongh-91404: Revert "bpo-23689: re module, fix memory leak..."
f35fa1a
00385: pythongh-94675: Add a regression test for rjsmin re slowdown
6f1cf68
hrnciar
added a commit that references this issue on Jul 26, 2022
00385: pythongh-94675: Add a regression test for rjsmin re slowdown
0d31185
miss-islington
added a commit that references this issue on Aug 3, 2022
pythongh-94675: Add a regression test for rjsmin re slowdown (pythonG…
9175421
gpshead
added a commit that references this issue on Aug 3, 2022
gh-94675: Add a regression test for rjsmin re slowdown (GH-94685)
fe23c00
miss-islington
added a commit that references this issue on Aug 3, 2022
gh-94675: Add a regression test for rjsmin re slowdown (GH-94685)
1bd1e37
kumaraditya303 commented on Aug 10, 2022
kumaraditya303
on Aug 10, 2022
Contributor
More actions
Fixed by #94685
kumaraditya303
closed this as completed on Aug 10, 2022
daandemeyer
added a commit that references this issue on Nov 17, 2022
Fix speed regression in the re module which prevented chromium from b…
0b91c9e

Metadata

Assignees

No one assigned

Labels

testsTests in the Lib/test dirTests in the Lib/test dirtopic-regextype-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

GeezerVison

Python 3.11.0b3 chockes on regex sub from rjsmin, time grows seemingly exponentially #94675

Description

Activity

hroncok commented on Jul 7, 2022

hroncok commented on Jul 7, 2022

hauntsaninja commented on Jul 8, 2022

hauntsaninja commented on Jul 8, 2022

hroncok commented on Jul 8, 2022

hroncok commented on Jul 8, 2022

hroncok commented on Jul 8, 2022

hroncok commented on Jul 8, 2022

hroncok commented on Jul 8, 2022

kumaraditya303 commented on Aug 10, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions