京公网安备11010502063487号Go 标准库的 regexp 不支持反向引用和断言,这是个常被抱怨的限制。它换来的是一个保证:匹配时间与输入长度成线性关系,不会被恶意输入拖垮(ReDoS)。这篇用同一个灾难性模式在 Go 和 Python 上各跑一遍,把这个代价与收益都摆出来。
Go regexp(RE2 风格): Go regexp `^(a+)+$` 匹配 1000 个 a 加一个 b:匹配结果 false,0.1 ms Go regexp `^(a+)+$` 匹配 10000 个 a 加一个 b:匹配结果 false,0.4 ms Go regexp `^(a+)+$` 匹配 100000 个 a 加一个 b:匹配结果 false,4.2 ms Go regexp `^(a+)+$` 匹配 1000000 个 a 加一个 b:匹配结果 false,38.0 ms Python re(回溯引擎),同一个模式、同样的输入(每次最多等 20 秒): Python re `^(a+)+$` 匹配 20 个 a 加一个 b:35 ms Python re `^(a+)+$` 匹配 24 个 a 加一个 b:549 ms Python re `^(a+)+$` 匹配 26 个 a 加一个 b:2193 ms Python re `^(a+)+$` 匹配 28 个 a 加一个 b:8919 ms Python re `^(a+)+$` 匹配 30 个 a 加一个 b:超过 20 秒,被我中断
Go 的耗时随输入线性增长:1000 个字符 0.1 ms,100 万个 38.0 ms。回溯引擎(Python 的 re)在同一个模式上每多 2 个字符约慢 4 倍:24 个字符 549 ms,28 个 8919 ms。这就是 ReDoS:攻击者用几十个字符就能耗尽一个线程。Python 的结果只代表这个版本的 re,别的回溯引擎(如 PCRE、Java)的数字不同,但指数增长的形状相似,我没有测。
Compile("(a)\\1") 失败:error parsing regexp: invalid escape sequence: `\1`
Compile("(?=a)b") 失败:error parsing regexp: invalid or unsupported Perl syntax: `(?=`
Compile("(?!a)b") 失败:error parsing regexp: invalid or unsupported Perl syntax: `(?!`
Compile("(?<=a)b") 失败:error parsing regexp: invalid named capture: `(?<=a)b`
Compile("a++") 失败:error parsing regexp: invalid nested repetition operator: `++`
Compile("(?i)abc") 成功
Compile("\\d{1,1001}") 失败:error parsing regexp: invalid repeat count: `{1,1001}`不支持反向引用 \1、先行 (?=…)/(?!…)、后行断言和占有量词 a++,重复次数上限是 1000;这些在编译时就会报错,不会静默地降级。
`a|ab` 在 "ab" 里(默认,Perl 风格最左优先):"a" 同一个模式调用 Longest()(POSIX 最左最长):"ab" MustCompilePOSIX:"ab"
默认是 Perl 风格的最左优先:a|ab 匹配 "ab" 得到 "a"。需要 POSIX 的最左最长就用 Longest() 或 CompilePOSIX,得到 "ab"。
在 63000 字节文本的开头附近命中:re.MatchString 172 ns/次;strings.Contains 7 ns/次 regexp.MustCompile 一次:1149 ns/次(21 次分配);每次都用 regexp.MatchString(内部再编译):1118 ns/次;预编译的 re.MatchString(短串):68 ns/次
预编译的短串匹配 68 ns,每次都 regexp.MatchString(内部再编译)1118 ns,要预编译并复用。简单的子串查找,strings.Contains 7 ns 比 regexp 快得多,不需要正则就别用。
backtrack.go:backtrack is a regular expression search with submatch tracking for small regular expressions and texts. It allocates a bit vector with (length of input) * (length of prog) bits, to make sure it never explores the same (character position, instruction) state multiple times. This limits the search to run in time linear in the length of the test. backtrack is a fast replacement for the NFA code on small regexps when onepass cannot be used. go doc regexp:The regexp implementation provided by this package is guaranteed to run in time linear in the size of the input. (This is a property not guaranteed by most open source implementations of regular expressions.) For more information about this property, see https://swtch.com/~rsc/regexp/regexp1.html or any book about
源码里的 backtrack.go 注释说明了它的做法:用位向量记住已经探索过的 (位置, 指令) 状态,不重复探索,所以时间与文本长度线性相关;文档也明确写了“保证与输入大小成线性”。这里我没有读 NFA 与 onepass 引擎的细节。