为什么Python会被这个正则表达式噎住？

Question

这看起来像一个简单的正则表达式，没有反引用，没有“any”字符，我甚至敢说它可以被Thomson DFA解析。它甚至可以工作，但是被非常简单的非匹配项阻塞了。你知道吗

{\s*?
ngx_string\("(?P<name>[a-z0-9_]+)"\)\s*?,\s*?
(?P<where>(([A-Z0-9_]+)\s*\|?)+?)\s*?,\s*?
(?P<bla>[^\n}]+?)\s*?,\s*?
(?P<bla2>[^\n}]+?)\s*?,\s*?
(?P<bla3>[^\n}]+?)\s*?,\s*?
(?P<bla4>[^\n}]+?)\s*?
}

+ re.MULTILINE | re.VERBOSE 

runnable gist here

我目前正在Python2.7.8上尝试这一点（但是链接的gist在py3.4上也失败了；另外linux、x86-64、Ubuntu、PCRE在[least/proc//maps中静态链接也没有显示任何有趣的内容）。你知道吗

这很好地解释了：

{ ngx_string("daemon"),
  NGX_MAIN_CONF|NGX_DIRECT_CONF|NGX_CONF_FLAG,
  ngx_conf_set_flag_slot,
  0,
  offsetof(ngx_core_conf_t, daemon),
  NULL },

这就是乐趣的终点：

 { ngx_string("off"), NGX_HTTP_REQUEST_BODY_FILE_OFF },
 { ngx_string("on"), NGX_HTTP_REQUEST_BODY_FILE_ON },

此外，更多数据：

把第二行改成这个

(?P<where>(([A-Z0-9_]{1,20})\s*\|?){1,6}?)\s{0,10}?,\s{0,10}?

，它最终在合理的时间内完成，但指数爆炸仍然存在，只是可以承受：

trying      { ngx_string("off"), NGX_HTTP_REQUEST_BODY_FILE
Took 0.033483 s
trying      { ngx_string("off"), NGX_HTTP_REQUEST_BODY_FILE_
Took 0.038528 s
trying      { ngx_string("off"), NGX_HTTP_REQUEST_BODY_FILE_O
Took 0.044108 s
trying      { ngx_string("off"), NGX_HTTP_REQUEST_BODY_FILE_OF
Took 0.053547 s

另外，有趣的是，一个基于JS的Python regex（仿真器？）解析器可以把它当作PCRE冠军的早餐来吃：https://www.debuggex.com/r/S__vSvp8-LGLuCLQ

哦，也许有人应该创建一个病理正则表达式标签：|

Answer 1

(?P<where>(([A-Z0-9_]+)\s*\|?)+?)
                     ^        ^

这就是你的正则表达式爆炸。读http://www.regular-expressions.info/catastrophic.html。你知道吗

每次失败时，它都会返回一步以检查是否存在错误匹配。这个正在为regex引擎创建大量的步骤和可能性。你知道吗

Answer 2

问题是原始正则表达式中的(([A-Z0-9_]+)\s*\|?)+?或测试正则表达式中的(([A-Z0-9_]{1,20})\s*\|?){1,6}?。{1,20}和{1,6}只起到抑制指数回溯的作用。你知道吗

由于\s*和\|?是可选的，当输入只包含[A-Z0-9_]而不包含空格或条|，但与regex的其余部分不匹配时，regex可以扩展到指数回溯(([A-Z0-9_]+))+?的经典示例。你知道吗

例如，匹配(?P<where>(([A-Z0-9_]+)\s*\|?)+?)\s*?,\s*?和AAAAAAAAAAAAAA（,丢失）将导致引擎检查所有拆分字符串的可能性，每个标记在外部重复的不同迭代中匹配：

AAAAAAAAAAAAAA
AAAAAAAAAAAAA A
AAAAAAAAAAAA AA
AAAAAAAAAAAA A A
AAAAAAAAAAA AAA
...
A AAAAAAAAAAAAA
A AAAAAAAAAAAA A
A AAAAAAAAAAA AA
...
A A A A A A A A A A A A A A

仔细看，regex的其余部分也有过多的回溯问题。你知道吗

以(?P<bla2>[^\n}]+?)\s*?,\s*?为例。[^\n}]可以匹配空格（或制表符，或许多其他空格字符），因此\s也可以匹配。如果不匹配的输入包含一长串空格，这可能会导致过度回溯。也可能存在正确性问题，因为,也可以与[^\n}]匹配。你知道吗

另一方面，Python re是一个NFA引擎，没有任何优化来缓解指数回溯问题。你知道吗

要减轻指数回溯：

{\s*
ngx_string\("(?P<name>[a-z0-9_]+)"\)\s*,\s*
(?P<where>[A-Z0-9_]+(?:\s*\|\s*[A-Z0-9_]+)*)\s*,\s*
(?P<bla>[^\n}]+?)\s*,\s*
(?P<bla2>[^\n}]+?)\s*,\s*
(?P<bla3>[^\n}]+?)\s*,\s*
(?P<bla4>[^\n}]+?)\s*
}

[^\n}]的过度回溯和正确性问题仍然没有得到解决。如果参数不在不同的行上，函数调用中的,可能会被错误地识别为外部块{}的一部分。你知道吗

一般的解决方案需要递归正则表达式，因为您可以调用函数作为参数传递其结果，例如offsetof(ngx_core_conf_t, daemon)，但是递归正则表达式特性在re包中不可用。一个不太通用的解决方案是匹配到某些级别的嵌套括号，例如1级嵌套：

(?P<bla>(?:\([^)]*\)|[^,()])+),\s*

整个正则表达式是：

{\s*?
ngx_string\("(?P<name>[a-z0-9_]+)"\)\s*,\s*
(?P<where>[A-Z0-9_]+(?:\s*\|\s*[A-Z0-9_]+)*)\s*,
(?P<bla>(?:\([^)]*\)|[^,()])+),\s*
(?P<bla2>(?:\([^)]*\)|[^,()])+),\s*
(?P<bla3>(?:\([^)]*\)|[^,()])+),\s*
(?P<bla4>(?:\([^)]*\)|[^,()])+)
}

DEMO

有两个注意事项：

• <bla*>捕获组的末尾将包含空格。如果您想删除空格，和防止可能的过度回溯，regex会更长一些。您可以尝试将\s*之前的,添加回this demo here。你知道吗
• 它假定()不是任何字符串文本的一部分。你知道吗