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

hroncok · 2022-07-07T23:09:33Z

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

The text was updated successfully, but these errors were encountered:

hroncok · 2022-07-07T23:25:50Z

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 · 2022-07-07T23:48:09Z

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);\]}]))'

hauntsaninja · 2022-07-08T06:53:08Z

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 · 2022-07-08T06:55:36Z

(If #93928 did indeed fix, it would be nice to add your reduced example as a test case!)

hroncok · 2022-07-08T08:53:11Z

Will test.

hroncok · 2022-07-08T09:09:05Z

This is fixed on main.

hroncok · 2022-07-08T09:10:37Z

#93928 also fixes it on 3.11

hroncok · 2022-07-08T09:37:29Z

@hauntsaninja Any idea how are the "does not take too long" cases handled in cpython tests?

hroncok · 2022-07-08T10:24:07Z

I've added #94685 -- hoping that the general timeout thing would stop it on b3

Use multiprocessing to kill the test after SHORT_TIMEOUT.

This fixes a speed regression in the re module which prevented chromium from building in Fedora. Revert "bpo-23689: re module, fix memory leak when a match is terminated by a signal or memory allocation failure" This reverts commit 6e3eee5. Manual fixups to increase the MAGIC number and to handle conflicts with a couple of changes that landed after that. (cherry picked from commit 4beee0c) Co-authored-by: Gregory P. Smith <greg@krypto.org> pythongh-94675: Add a regression test for rjsmin re slowdown Co-authored-by: Miro Hrončok <miro@hroncok.cz>

This tests a speed regression in the re module which prevented chromium from building in Fedora. python#94685

…H-94685) Adds a regression test for an re slowdown observed by rjsmin. Uses multiprocessing to kill the test after SHORT_TIMEOUT. Co-authored-by: Oleg Iarygin <dralife@yandex.ru> Co-authored-by: Christian Heimes <christian@python.org> (cherry picked from commit fe23c00) Co-authored-by: Miro Hrončok <miro@hroncok.cz>

Adds a regression test for an re slowdown observed by rjsmin. Uses multiprocessing to kill the test after SHORT_TIMEOUT. Co-authored-by: Oleg Iarygin <dralife@yandex.ru> Co-authored-by: Christian Heimes <christian@python.org>

Adds a regression test for an re slowdown observed by rjsmin. Uses multiprocessing to kill the test after SHORT_TIMEOUT. Co-authored-by: Oleg Iarygin <dralife@yandex.ru> Co-authored-by: Christian Heimes <christian@python.org> (cherry picked from commit fe23c00) Co-authored-by: Miro Hrončok <miro@hroncok.cz>

kumaraditya303 · 2022-08-10T11:19:39Z

Fixed by #94685

…uilding For details, see python/cpython#94675 Backported from upstream 3.11 branch + python/cpython#94685 Needs bootstrap for test_distutils (assert _sre.MAGIC == MAGIC, "SRE module mismatch").

hroncok added the type-bug An unexpected behavior, bug, or error label Jul 7, 2022

AlexWaygood added topic-regex 3.11 only security fixes 3.12 bugs and security fixes labels Jul 8, 2022

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 Jul 8, 2022

AlexWaygood added tests Tests in the Lib/test dir and removed 3.11 only security fixes 3.12 bugs and security fixes labels Jul 8, 2022

hroncok added a commit to hroncok/cpython that referenced this issue Jul 8, 2022

pythongh-94675: Add a regression test for rjsmin re slowdown

63f9899

bedevere-bot mentioned this issue Jul 8, 2022

gh-94675: Add a regression test for rjsmin re slowdown #94685

Merged

hroncok added a commit to hroncok/cpython that referenced this issue Jul 8, 2022

fixup! pythongh-94675: Add a regression test for rjsmin re slowdown

ee602ea

Use multiprocessing to kill the test after SHORT_TIMEOUT.

hroncok added a commit to fedora-python/cpython that referenced this issue Jul 11, 2022

00385: pythongh-94675: Add a regression test for rjsmin re slowdown

6f1cf68

This tests a speed regression in the re module which prevented chromium from building in Fedora. python#94685

hrnciar pushed a commit to fedora-python/cpython that referenced this issue Jul 26, 2022

00385: pythongh-94675: Add a regression test for rjsmin re slowdown

0d31185

This tests a speed regression in the re module which prevented chromium from building in Fedora. python#94685

bedevere-bot mentioned this issue Aug 3, 2022

[3.11] gh-94675: Add a regression test for rjsmin re slowdown (GH-94685) #95630

Merged

kumaraditya303 closed this as completed Aug 10, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

hroncok commented Jul 7, 2022 •

edited

Loading

hroncok commented Jul 7, 2022

hroncok commented Jul 7, 2022 •

edited

Loading

hauntsaninja commented Jul 8, 2022

hauntsaninja commented Jul 8, 2022

hroncok commented Jul 8, 2022

hroncok commented Jul 8, 2022

hroncok commented Jul 8, 2022

hroncok commented Jul 8, 2022

hroncok commented Jul 8, 2022

kumaraditya303 commented Aug 10, 2022

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

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

Comments

hroncok commented Jul 7, 2022 • edited Loading

hroncok commented Jul 7, 2022

hroncok commented Jul 7, 2022 • edited Loading

hauntsaninja commented Jul 8, 2022

hauntsaninja commented Jul 8, 2022

hroncok commented Jul 8, 2022

hroncok commented Jul 8, 2022

hroncok commented Jul 8, 2022

hroncok commented Jul 8, 2022

hroncok commented Jul 8, 2022

kumaraditya303 commented Aug 10, 2022

hroncok commented Jul 7, 2022 •

edited

Loading

hroncok commented Jul 7, 2022 •

edited

Loading