Skip to content

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

Closed
Closed
Python 3.11.0b3 chockes on regex sub from rjsmin, time grows seemingly exponentially#94675
Labels
testsTests in the Lib/test dirtopic-regextype-bugAn unexpected behavior, bug, or error

Description

@hroncok
hroncok
opened on Jul 7, 2022

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

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

  2. hroncok commented on Jul 7, 2022

    @hroncok
    hroncok
    on Jul 7, 2022
    ContributorAuthor

    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
...

  3. hroncok commented on Jul 7, 2022

    @hroncok
    hroncok
    on Jul 7, 2022
    ContributorAuthor

    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);\]}]))'
  4. AlexWaygood
    added
    topic-regex
    3.11only security fixes
    3.12only security fixes
    on Jul 8, 2022

  5. hauntsaninja commented on Jul 8, 2022

    @hauntsaninja
    hauntsaninja
    on Jul 8, 2022
    Contributor

    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

  6. hauntsaninja commented on Jul 8, 2022

    @hauntsaninja
    hauntsaninja
    on Jul 8, 2022
    Contributor

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

  7. hroncok commented on Jul 8, 2022

    @hroncok
    hroncok
    on Jul 8, 2022
    ContributorAuthor

    Will test.

  8. hroncok commented on Jul 8, 2022

    @hroncok
    hroncok
    on Jul 8, 2022
    ContributorAuthor

    This is fixed on main.

  9. hroncok commented on Jul 8, 2022

    @hroncok
    hroncok
    on Jul 8, 2022
    ContributorAuthor

    #93928 also fixes it on 3.11

  10. 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
  11. AlexWaygood
    added
    testsTests in the Lib/test dir
    and removed
    3.11only security fixes
    3.12only security fixes
    on Jul 8, 2022

  12. hroncok commented on Jul 8, 2022

    @hroncok
    hroncok
    on Jul 8, 2022
    ContributorAuthor

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

  13. hroncok commented on Jul 8, 2022

    @hroncok
    hroncok
    on Jul 8, 2022
    ContributorAuthor

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

  14. 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
  15. hrnciar
    added a commit that references this issue on Jul 26, 2022

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

    0d31185
  16. 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
  17. 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
  18. 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

  19. kumaraditya303 commented on Aug 10, 2022

    @kumaraditya303
    kumaraditya303
    on Aug 10, 2022
    Contributor

    Fixed by #94685

  20. kumaraditya303
    closed this as completedon Aug 10, 2022
  21. 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

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

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions