Perl 显然是如何避免灾难性的回溯的？

Question

我正在使用 Perl 5.34.1 和 Python 3.10.12。

以下脚本在 Python 中需要 16 秒：

import re
patt = re.compile(r"W(X|Y+)+Z")
print(patt.search("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA"))

但在 Perl 中几乎不需要花费任何时间：

use v5.34;
my $patt = qr/W(X|Y+)+Z/;
print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);

这是https://medium.com/bigpanda-engineering/catastropic-backtracking-the-dark-side-of-regular-expressions-80cab9c443f6提供的灾难性回溯示例。

我预计任何回溯正则表达式引擎都会在这种情况下受到影响，但显然 Perl 正则表达式引擎不会。在这个例子中它如何避免灾难性的回溯？它实际上是在内部“灾难性”地回溯，但比 Python 引擎快几个数量级吗？它是否使用一些快速路径优化来防止在完成完整回溯序列之前提前失败？

Answer 1

因为优化。它意识到Z需要 a，但没有找到。

$ perl -Mre=debug -e'
    use v5.34;
    my $patt = qr/W(X|Y+)+Z/;
    print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);
'
Compiling REx "W(X|Y+)+Z"
Final program:
   1: EXACT <W> (3)
   3: CURLYX<1:1>[0]{1,INFTY} (21)
   7:   OPEN1 (9)
   9:     BRANCH (buf:1/1) (13)
  11:       EXACT <X> (18)
  13:     BRANCH (buf:1/1) (FAIL)
  15:       PLUS (18)
  16:         EXACT <Y> (0)
  18:   CLOSE1 (20)
  20: WHILEM[1/1] (0)
  21: NOTHING (22)
  22: EXACT <Z> (24)
  24: END (0)
anchored "W" at 0..0 floating "Z" at 2..9223372036854775807 (checking floating) minlen 3
Matching REx "W(X|Y+)+Z" against "WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA"
Intuit: trying to determine minimum start position...
  doing 'check' fbm scan, [2..30] gave -1
  Did not find floating substr "Z"...
Match rejected by optimizer
Freeing REx: "W(X|Y+)+Z"

也就是说，使用qr/W(X|Y+)+(Z|!)/绕过了优化。

$ perl -Mre=debug -e'
    use v5.34;
    my $patt = qr/W(X|Y+)+Z/;
    print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);
' 2>&1 | wc -l
22

$ perl -Mre=debug -e'
    use v5.34;
    my $patt = qr/W(X|Y+)+(Z|!)/;
    print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);
' 2>&1 | wc -l
2971

不过，在我的机器上，差异还不到 1 毫秒。

$ time perl -e'
    use v5.34;
    my $patt = qr/W(X|Y+)+Z/;
    print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);
' 2>&1 | wc -l
0

real    0m0.002s
user    0m0.002s
sys     0m0.000s

$ time perl -e'
    use v5.34;
    my $patt = qr/W(X|Y+)+(Z|!)/;
    print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);
' 2>&1 | wc -l
0

real    0m0.002s
user    0m0.002s
sys     0m0.000s

显然，还有其他优化。-Mre=debug此版本包含以下消息：

WHILEM: Detected a super-linear match, switching on caching...

你可以尝试看看 Yves“demerphq”Orton 是否就此做过任何演讲。