Python的正则表达式源字符串长度

Question

在Python中的正则表达式中，

re.compile("x"*50000)

出现了OverflowError: regular expression code size limit exceeded错误，但是下面的代码没有报错，但是会导致CPU占用率达到100%，在我的电脑上需要1分钟的时间才能运行完。

>>> re.compile(".*?.*?.*?.*?.*?.*?.*?.*?.*?.*?"*50000)
<_sre.SRE_Pattern object at 0x03FB0020>

这正常吗？

我应该假设 ".*?.*?.*?.*?.*?.*?.*?.*?.*?.*?"*50000 比 "x"*50000 短吗？

在 Python 2.6、Win32 上测试过。

更新1：

看起来 ".*?.*?.*?.*?.*?.*?.*?.*?.*?.*?"*50000 可以简化为 .*?

那么这个怎么样？

re.compile(".*?x"*50000)

它确实编译通过，如果它也可以简化为".*?x"，它应该匹配字符串"abcx"或"x"，但它并没有匹配成功。所以，我是不是漏了什么？更新2：我的重点不是要知道正则表达式源字符串的最大限制，我想知道"x"*50000被溢出处理程序捕获的一些原因/概念，但不涉及".*?x"*50000。对我来说这没有意义，这是溢出检查中缺少了什么，还是一切都很好或者它确实溢出了什么？任何提示/意见将不胜感激。

- YOU

---

不是“.?x”5000缩减为“.?x” - 它会缩减为一个正则表达式，其中有5000个x，在每个x之前都有“.?”。这就是为什么它不能匹配“abcx”或“x”的原因 - 它只能匹配一个带有5000个x的字符串。 - Dave Kirby

这让我想起曾经在尝试将SVG路径的ABNF转换为正则表达式时，遇到过PHP正则表达式最大长度的限制。因此，在我看来，了解答案是很有必要的。 - Boldewyn

@Dave Kirby，谢谢，但是它是50000（50k）。我的原始问题是re.compile("x"*50000)没有被编译，但是re.compile(".*?x"*50000)被编译了。 - YOU

为什么需要知道正则表达式的最大值？只需编写所需的正则表达式。x{5000}或x{500000}或其他任何内容。当您达到限制时，就在那里了。知道限制在哪里有什么意义呢？除非（不太可能）您编写了一个真正过长的正则表达式，否则您不需要知道。这些不合理的正则表达式本来就不是明智的选择。 - S.Lott

@S.Lott，您说得对，了解极限并没有任何意义，但是您不认为当 "x"*50000 被溢出处理程序捕获时，它可能会容易受到缓冲区溢出攻击，而 ".*?x"*50000 却不会，甚至 ".*?x"*100000 也不会吗？ - YOU

正则表达式编译缓冲区溢出不是“漏洞”。正则表达式是设计时的功能。您需要自己调试它们。一旦它们工作，正则表达式的编译形式就可以正常工作。它不会自动变得更大并发生缓冲区溢出。没有用户输入。它可能被静态编译到您的代码中。 - S.Lott

Answer 1

区别在于".*?.*?.*?.*?.*?.*?.*?.*?.*?.*?"*50000可以简化为".*?"，而"x"*50000则必须在FSM（或正则表达式引擎使用的类似结构）中生成50000个节点。

编辑：好吧，我错了。它并不那么聪明。 "x"*50000失败，但".*?x"*50000之所以不会，是因为“代码项”的大小有限制。 "x"*50000将生成一个长代码项，而".*?x"*50000将生成许多小代码项。如果你能想出一种不改变正则表达式含义的方式来分割字符串文字，那么它就可以工作，但我想不到这样的方法。

- Lukáš Lalinský

---

谢谢，但re.compile（".*?x"*50000）怎么样？ - YOU

我不太了解Python正则表达式引擎的内部情况，所以我不确定。该正则表达式应匹配50000个x之间的任何字符。我不知道它进行了什么优化，但很可能它对正则表达式进行了特殊处理。顺便说一下，所有的正则表达式都在Linux上工作。 - Lukáš Lalinský

感谢关于Linux版本的信息，我刚刚检查了_sre.c -> _compile函数，没有特定的Windows代码，所以可能是由于某些大小差异，例如wchar_t和/或您的Python编译时使用了Unicode=UCS4。 - YOU

" x "50000 会生成一个长项目，而 " .?x "*50000 会生成许多小项目。谢谢，那很有道理。 - YOU

Answer 2

你想匹配50000个"x"，对吗？如果是的话，可以考虑不使用正则表达式的替代方案。

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

如果你想使用正则表达式匹配50000个"x"，你可以使用范围

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

在我的系统中，它最多可以接受长度为65535。

>>> 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}")
>>>

我不知道在Python中是否有一些调整可以用来增加这个限制。

- ghostdog74

---

感谢您更新代码，但{65535}是重复限制，与我的有些不同。在我看来，"x"*50000和"x{50000}是不同的。 - YOU

"x"*50000 会产生 50000 个 x。在正则表达式中，如果你输入 x{50000}，那么你告诉正则表达式引擎去搜索 50000 个 x。或者我有什么遗漏的吗？你应该清楚地陈述你想要做什么，并给出示例。 - ghostdog74

@ghostdog74，你说得对，如果我想匹配50000个x，我可以使用x{50000}。我只是在想re.compile是否安全以及测试它是否存在漏洞。仅此而已。 - YOU

好的，正如您所看到的，字符串长度超过65535（对于我的系统）会导致正则表达式引擎崩溃并产生错误。我建议在将其传递给re.compile之前，根据您的应用程序规格检查您的字符串。 - ghostdog74