[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2021-04-11 Thread Gregory P. Smith
Gregory P. Smith added the comment: https://pypi.org/project/pyre2/ seems to be a maintained version of that for use on modern Python interpreters. -- ___ Python tracker

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2017-04-24 Thread Gregory P. Smith
Changes by Gregory P. Smith : -- versions: +Python 3.7 -Python 3.4 ___ Python tracker ___

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2017-04-24 Thread Gregory P. Smith
Gregory P. Smith added the comment: Note that https://pypi.python.org/pypi/re2 exists today as well and offers a re module compatible interface. I haven't tried it. -- ___ Python tracker

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2013-05-16 Thread Antoine Pitrou
Antoine Pitrou added the comment: Note this can be used for denials of service: see http://bugs.python.org/issue17980 -- nosy: +pitrou ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue1662581

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2013-05-16 Thread Gregory P. Smith
Gregory P. Smith added the comment: The recommendation for anyone using regular expressions on hostile input is to (a) don't do that. (b) use a better regexp without this possible behavior and (c) use something like re2 (there's a Python binding at https://github.com/axiak/pyre2) which is a

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2012-11-27 Thread Mark Dickinson
Mark Dickinson added the comment: Given the number of times this comes up, I think it's a least worth an upgrade from 'low' priority to 'normal' priority. -- priority: low - normal versions: +Python 3.4 -Python 3.3 ___ Python tracker

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2011-02-25 Thread Terry J. Reedy
Terry J. Reedy tjre...@udel.edu added the comment: Another example from #11307 import re r = re.compile(r'(\w+)*=.*') r.match(abcdefghijklmnopqrstuvwxyz) -- nosy: +terry.reedy versions: +Python 3.3 -Python 2.7 ___ Python tracker

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2009-10-21 Thread Dan
Dan wit...@torsion.org added the comment: Here's an easy way to trigger the poor performance. Tested with 2.5, 2.6, and 2.7: re.compile( '(\s+.*)*x' ).search( 'a ' * 30 ) -- nosy: +witten ___ Python tracker rep...@bugs.python.org

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2009-10-21 Thread Matthew Barnett
Matthew Barnett pyt...@mrabarnett.plus.com added the comment: I'm still tinkering with my regex engine (issue #2636). Some timings: re.compile(r'(\s+.*)*x').search('a ' * 25) 20.23secs regex.compile(r'(\s+.*)*x').search('a ' * 25) 0.10secs -- ___

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2009-02-09 Thread Matthew Barnett
Matthew Barnett pyt...@mrabarnett.plus.com added the comment: This has been addressed in issue #2636. -- nosy: +mrabarnett ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue1662581 ___

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2009-02-09 Thread Mark Dickinson
Mark Dickinson dicki...@gmail.com added the comment: This has been addressed in issue #2636. Are you sure about this? Does the proposed new regex engine use Thompson NFAs, or some variant thereof? -- nosy: +marketdickinson ___ Python tracker

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2009-02-09 Thread Matthew Barnett
Matthew Barnett pyt...@mrabarnett.plus.com added the comment: The new code includes some extra checks which, although not foolproof, certainly reduce the amount of backtracking in a lot of cases. ___ Python tracker rep...@bugs.python.org

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2008-09-27 Thread Jeffrey C. Jacobs
Changes by Jeffrey C. Jacobs [EMAIL PROTECTED]: -- nosy: +timehorse versions: +Python 2.7 ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue1662581 ___ ___

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2008-07-09 Thread Yarko Tymciurak
Yarko Tymciurak [EMAIL PROTECTED] added the comment: Not sure if this is a real-world case of this in particular, but possibly: http://groups.google.com/group/web2py/browse_thread/thread/59ff2e31698bced6/9bbae2d482d11b88 -- nosy: +yarkot ___ Python

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2008-04-24 Thread Russ Cox
Changes by Russ Cox [EMAIL PROTECTED]: -- nosy: +rsc _ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue1662581 _ ___ Python-bugs-list mailing list Unsubscribe:

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2008-01-09 Thread Ralf Schmitt
Ralf Schmitt added the comment: here are two other bug reports about the same issue: http://bugs.python.org/issue1448325 http://bugs.python.org/issue1566086 -- nosy: +schmir _ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue1662581

[issue1662581] the re module can perform poorly: O(2**n) versus O(n**2)

2007-10-07 Thread Aaron Swartz
Aaron Swartz added the comment: Just a note for those who think this is a purely theoretical issue: We've been using the python-markdown module on our web app for a while, only to notice the app has been repeatedly going down. After tracking down the culprit, we found that a speech from Hamlet