ansaurus

Question

Python's Regular Expression Source String Length

Answer 1

+4 A:

The difference is that ".*?.*?.*?.*?.*?.*?.*?.*?.*?.*?"*50000 can be reduced to ".*?", while "x"*50000 has to generate 50000 nodes in the FSM (or a similar structure used by the regex engine).

EDIT: Ok, I was wrong. It's not that smart. The reason why "x"*50000 fails, but ".*?x"*50000 doesn't is that there is a limit on size of one "code item". "x"*50000 will generate one long item and ".*?x"*50000 will generate many small items. If you could split the string literal somehow without changing the meaning of the regex, it would work, but I can't think of a way to do that.

Lukáš Lalinský 2010-01-04 08:47:48

Thanks, but how about `re.compile(".*?x"*50000)`?

S.Mark 2010-01-04 09:11:13

I don't really know about internals about the Python regex engine, so I'm not sure. The regex should match 50000 x's with any characters between them. I don't know what optimalizations does it do, but it's likely that it does something special about the regex. FYI, all of the regexes work on Linux.

Lukáš Lalinský 2010-01-04 09:37:59

Thanks for info about linux version, I just checked _sre.c -> _compile function, there is no specific code for windows, so it may be because of some size different like `wchar_t` and/or your python is compiled with `Unicode=UCS4`

S.Mark 2010-01-04 10:12:03

`"x"*50000 will generate one long item and ".*?x"*50000 will generate many small items`, Thank you, that make sense.

S.Mark 2010-01-05 00:54:01

Answer 2

+2 A:

you want to match 50000 "x"s , correct??? if so, an alternative without regex

if "x"*50000 in mystring:
    print "found"

if you want to match 50000 "x"s using regex, you can use range

>>> pat=re.compile("x{50000}")
>>> pat.search(s)
<_sre.SRE_Match object at 0xb8057a30>

on my system it will take in length of 65535 max

>>> pat=re.compile("x{65536}")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python2.6/re.py", line 188, in compile
    return _compile(pattern, flags)
  File "/usr/lib/python2.6/re.py", line 241, in _compile
    p = sre_compile.compile(pattern, flags)
  File "/usr/lib/python2.6/sre_compile.py", line 529, in compile
    groupindex, indexgroup
RuntimeError: invalid SRE code
>>> pat=re.compile("x{65535}")
>>>

I don't know if there are tweaks in Python we can use to increase that limit though.

ghostdog74 2010-01-04 09:22:55

+1 Thanks, but I am looking for the reason, why for regex

S.Mark 2010-01-04 09:24:42

Thanks for the update for the code, but `{65535}` is the repetation limit, thats a bit different with mine. `"x"*50000` and `"x{50000}` is different in my understanding.

S.Mark 2010-01-04 09:57:25

"x"*50000 produces 50000 x's.. in a regex, if you put x{50000}, you are telling the regex engine to search for 50000 x's as well... Or am i missing something ? you should clearly state what you want to do in your question with examples...

ghostdog74 2010-01-04 10:27:01

@ghostdog74, you are right, I can use x{50000} if I want to match 50000 x. I am just wondering re.compile is safe or not and testing for vulnerablity. thats all.

S.Mark 2010-01-04 11:09:02

well, as you can see, string length exceeding 65535 (for my system) crashes the regex engine and produce error. I would suggest checking your string according to your application specs before passing it to re.compile.

ghostdog74 2010-01-04 11:28:03

ansaurus

tags:

views:

answers:

Python's Regular Expression Source String Length

related questions