最新的Perl不会匹配超过32768个字符的某些正则表达式

Question

我希望一些Perl大师可以对以下内容发表意见.这是我能找到的最小可能的例子,它可以重现我的问题:

>./perl -e 'print (("a".("f"x32767)."a") =~ /a(?:[^a]|bb)*a/)'
1

但

>./perl -e 'print (("a".("f"x32768)."a") =~ /a(?:[^a]|bb)*a/)'
>

我从源代码编译了最新的Perl,看它是否能解决问题:

>./perl -v

This is perl 5, version 20, subversion 1 (v5.20.1) built for i686-linux

这是一个错误(看起来像我)？

Answer 1

添加use warnings:

use strict;
use warnings;
use feature qw(say);

say "Version is $^V";

say +("a".("f"x32767)."a") =~ /a(?:[^a]|bb)*a/ ? 'matches' : 'no match';

say +("a".("f"x32768)."a") =~ /a(?:[^a]|bb)*a/ ? 'matches' : 'no match';

输出:

Complex regular subexpression recursion limit (32766) exceeded at e.pl line 7.
Complex regular subexpression recursion limit (32766) exceeded at e.pl line 9.
Version is v5.20.1
matches
no match

从 perldiag

超出复杂的常规子表达式递归限制(%d)

(W regexp)正则表达式引擎在需要反向跟踪的复杂情况下使用递归.递归深度限制为32766,或者在堆栈无法任意增长的架构中可能更少.("简单"和"中等"情况在没有递归的情况下处理,不受限制.)尝试缩短检查中的字符串; 循环使用Perl代码(例如使用while)而不是正则表达式引擎; 或重写正则表达式,使其更简单或回溯更少.(有关掌握正则表达式的信息,请参阅perlfaq2.)

Answer 2

这是自2002年以来报告的已知错误,尚未修复.您现在知道您不是第一个遇到此错误的人(或功能,您很快就会看到).

从该评论中的bug报告,似乎量词(*,+,{n,m},{n,})被设计成具有上重复的次数,从而避免发动机时用于回溯溢出堆栈段错误的上限,但违反了非常清晰正则表达式中的Kleene运算符(重复模式任意次数)并为查询¹提供错误答案.

^{1相反,Java的正则表达式引擎(Oracle的implemetation)简单地允许StackOverflowError发生像这样的情况下,但量词具有2上限32 - 1,这足以满足大多数使用情况.对于像这样的情况,存在一种解决方法,即使用占有量词.}

同样的注释也打印正则表达式编译调试信息,输出清楚地显示*转换为{0,32767}.它在我的机器上也是可重现的(为x86_64-linux-thread-multi构建的perl v5.10.1(*)).

$ perl -Mre=debug -wce '/(A|B)*/'
Compiling REx "(A|B)*"
Final program:
   1: CURLYM[1] {0,32767} (15)
   5:   TRIE-EXACT[AB] (13)
        <A>
        <B>
  13:   SUCCEED (0)
  14: NOTHING (15)
  15: END (0)
minlen 0
-e syntax OK
Freeing REx: "(A|B)*"

以下测试进一步确认了该问题,并显示perl不允许您指定超出限制的重复.

$ perl -e 'print (("a".("f"x32767)."a") =~ /a(?:[^a]|bb){0,32767}a/)'
Quantifier in {,} bigger than 32766 in regex; marked by <-- HERE in m/a(?:[^a]|bb){ <-- HERE 0,32767}a/ at -e line 1.

使得量词占有欲*+也没有解决问题,因为限制仍然存在:

$ perl -Mre=debug -wce '/(A|B)*+/'
Compiling REx "(A|B)*+"
Final program:
   1: SUSPEND (19)
   3:   CURLYM[1] {0,32767} (17)
   7:     TRIE-EXACT[AB] (15)
          <A>
          <B>
  15:     SUCCEED (0)
  16:   NOTHING (17)
  17:   SUCCEED (0)
  18: TAIL (19)
  19: END (0)
minlen 0
-e syntax OK
Freeing REx: "(A|B)*+"