This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: Regular expression "hangs" interpreter
Type: behavior Stage: resolved
Components: Regular Expressions Versions: Python 2.7
process
Status: closed Resolution: wont fix
Dependencies: Superseder:
Assigned To: Nosy List: T Trindad, ezio.melotti, gdr@garethrees.org, mrabarnett, r.david.murray
Priority: normal Keywords:

Created on 2017-07-20 04:41 by T Trindad, last changed 2022-04-11 14:58 by admin. This issue is now closed.

Messages (4)
msg298705 - (view) Author: T Trindad (T Trindad) Date: 2017-07-20 04:41
The following code "hangs" the interpreter:

    import re
    re.search(r"/\*\*((?:[^*]+|\*[^/])*)\*/", """	/** Copy Constructor **/
	private EvaluationContext (EvaluationContext base) {""")



Changing the regex to r"/\*\*((?:[^*]|\*[^/])*)\*/" makes it work normally.
msg298715 - (view) Author: Gareth Rees (gdr@garethrees.org) * (Python triager) Date: 2017-07-20 11:49
This is the usual exponential backtracking behaviour of Python's regex engine. The problem is that the regex

    (?:[^*]+|\*[^/])*

can match against a string in exponentially many ways, and Python's regex engine tries all of them before giving up.
msg298727 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2017-07-20 15:24
Right.  We don't try to fix handling these kinds of exponential expressions.  This is a case of "don't do that" :)

(I don't know if the regex module is better at "handling" this kind of regex bug.)
msg298746 - (view) Author: Matthew Barnett (mrabarnett) * (Python triager) Date: 2017-07-20 19:22
The regex module is much better in this respect, but it's not foolproof. With this particular example it completes quickly.
History
Date User Action Args
2022-04-11 14:58:49adminsetgithub: 75156
2017-07-20 19:22:22mrabarnettsetmessages: + msg298746
2017-07-20 15:24:43r.david.murraysetstatus: open -> closed

type: crash -> behavior

nosy: + r.david.murray
messages: + msg298727
resolution: wont fix
stage: resolved
2017-07-20 11:49:54gdr@garethrees.orgsetnosy: + gdr@garethrees.org
messages: + msg298715
2017-07-20 04:41:58T Trindadcreate