René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Python 3.11.0b3 chockes on regex sub from rjsmin, time grows seemingly exponentially","articleBody":"**Bug report**\r\n\r\nWhen building chromium in Fedora 37 with Python 3.11.0b3, the build hangs seemingly forever.\r\n\r\nWhile isolating the hang, we've noticed it happens in rjsmin, at https://github.com/ndparker/rjsmin/blob/1.2.0/rjsmin.py#L361\r\n\r\nI've further reduced the javascript input as much as I could \u003cdel\u003ebut I kept the regex pattern intact\u003c/del\u003e.\r\n\r\nHere's the reporucer:\r\n\r\n```python\r\nimport re, sys\r\n\r\n# pattern from rjsmin\r\n# Copyright 2011 - 2021 André Malo or his licensors, as applicable.\r\n# Apache License Version 2.0\r\n# https://github.com/ndparker/rjsmin/blob/1.2.0/rjsmin.py#L196\r\npattern = '(?\u003c=[(,=:\\\\[!\u0026|?{};\\\\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\u0026)+,.:;=?\\\\]|}-]))?'\r\n# (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]*)|(?\u003c=[)])(?:[\\\\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])|(?\u003c=[(,=:\\\\[!\u0026|?{};\\\\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\u0026)+,.:;=?\\\\]|}-]))?|(?\u003c=[\\\\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\u0026)+,.:;=?\\\\]|}-]))?|(?\u003c=[^\\\\000-!#%\u0026(*,./:-@\\\\[\\\\\\\\^{|~])(?:[\\\\000-\\\\011\\\\013\\\\014\\\\016-\\\\040]|(?:/\\\\*[^*]*\\\\*+(?:[^/*][^*]*\\\\*+)*/))*(?:((?:(?://[^\\\\r\\\\n]*)?[\\\\r\\\\n]))(?:[\\\\000-\\\\011\\\\013\\\\014\\\\016-\\\\040]|(?:/\\\\*[^*]*\\\\*+(?:[^/*][^*]*\\\\*+)*/))*)+(?=[^\\\\000-\\\\040\"#%-\\\\047)*,./:-@\\\\\\\\-^\\\\140|-~])|(?\u003c=[^\\\\000-#%-,./:-@\\\\[-^\\\\140{-~-])((?:[\\\\000-\\\\011\\\\013\\\\014\\\\016-\\\\040]|(?:/\\\\*[^*]*\\\\*+(?:[^/*][^*]*\\\\*+)*/)))+(?=[^\\\\000-#%-,./:-@\\\\[-^\\\\140{-~-])|(?\u003c=\\\\+)((?:[\\\\000-\\\\011\\\\013\\\\014\\\\016-\\\\040]|(?:/\\\\*[^*]*\\\\*+(?:[^/*][^*]*\\\\*+)*/)))+(?=\\\\+)|(?\u003c=-)((?:[\\\\000-\\\\011\\\\013\\\\014\\\\016-\\\\040]|(?:/\\\\*[^*]*\\\\*+(?:[^/*][^*]*\\\\*+)*/)))+(?=-)|(?:[\\\\000-\\\\011\\\\013\\\\014\\\\016-\\\\040]|(?:/\\\\*[^*]*\\\\*+(?:[^/*][^*]*\\\\*+)*/))+|(?:(?:(?://[^\\\\r\\\\n]*)?[\\\\r\\\\n])(?:[\\\\000-\\\\011\\\\013\\\\014\\\\016-\\\\040]|(?:/\\\\*[^*]*\\\\*+(?:[^/*][^*]*\\\\*+)*/))*)+'\r\n\r\n\r\ninput_data = \"\"\"a(function() {{\r\n      {}\r\n}});\r\n\"\"\".format('/' * int(sys.argv[1]))\r\n\r\nprint(re.compile(pattern).sub('', input_data))\r\n```\r\n\r\nThe original input reduced from Chromium's JavaScript file looks like:\r\n\r\n```javascript\r\na(function() {\r\n      //////////////////////////////////////////////////////////////////////////\r\n}); \r\n```\r\n\r\nAnd here how long it takes with Python 3.10.5 and 3.11.0b3 for a reduced number of slashes.\r\n\r\n```\r\n$ time python3.10 reproducer.py 30\r\nreal    0m0,033s\r\n\r\n$ time python3.11 reproducer.py 30\r\nreal    0m0,082s\r\n\r\n$ time python3.10 reproducer.py 40\r\nreal    0m0,034s\r\n\r\n$ time python3.11 reproducer.py 40\r\nreal    0m6,902s\r\n\r\n$ time python3.10 reproducer.py 45\r\nreal    0m0,032s\r\n\r\n$ time python3.11 reproducer.py 45\r\nreal    1m25,004s\r\n\r\n$ time python3.10 reproducer.py 50\r\nreal    0m0,031s\r\n\r\n$ time python3.11 reproducer.py 50\r\n??? killed after 10+ minutes\r\n```\r\n\r\nFor 74 slashes, I guess it would run forever.\r\n\r\n**Your environment**\r\n\r\n\u003c!-- Include as many relevant details as possible about the environment you experienced the bug in --\u003e\r\n\r\n- CPython versions tested on: 3.11.0b3\r\n- Operating system and architecture: Fedora Linux 35 or 37, x86_64\r\n\r\n\u003c!--\r\nYou can freely edit this text. Remove any lines you believe are unnecessary.\r\n--\u003e\r\n","author":{"url":"https://github.com/hroncok","@type":"Person","name":"hroncok"},"datePublished":"2022-07-07T23:09:33.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":10},"url":"https://github.com/94675/cpython/issues/94675"}