[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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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 regular expression engine that this 
cannot happen to.

fixing this within python requires a complete rewrite and replacement of the re 
module with one that uses a different approach.  see the other work on the MRAB 
regex module and discussion surrounding that.  that is a non trivial task and 
it is fixing other more important things (unicode correctness!) than this...

Given that, I don't actually expect this issue to ever be fixed.

IMNSHO: People shouldn't abuse regexes and get themselves into this situation 
in the first place. ;)

discussion should really happen on python-ideas.

--
resolution:  - wont fix
status: open - closed

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1662581
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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 rep...@bugs.python.org
http://bugs.python.org/issue1662581
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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 rep...@bugs.python.org
http://bugs.python.org/issue1662581
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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
http://bugs.python.org/issue1662581
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1662581
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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 rep...@bugs.python.org
http://bugs.python.org/issue1662581
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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
http://bugs.python.org/issue1662581
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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 tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1662581
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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
_
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[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 passed to one of
the Markdown regular expressions caused this exponential behavior,
freezing up the app.

--
nosy: +aaronsw

_
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1662581
_
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com