为什么Java正则表达式引擎会在+重复上抛出StringIndexOutOfBoundsException？

Question

我写了一个正则表达式模式来找到Fibonacci数字(没关系,为什么,我刚刚做了).它按预期工作得非常好(参见ideone.com):

    String FIBONACCI = 
        "(?x) .{0,2} | (?: (?=(\\2?)) (?=(\\2\\3|^.)) (?=(\\1)) \\2)++ . ";

    for (int n = 0; n < 1000; n++) {
        String s = new String(new char[n]);
        if (s.matches(FIBONACCI)) {
            System.out.print(n + " ");
        }
    } // 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 

一个占有欲重复(即++主"回路")是至关重要的,因为你不希望这种匹配算法回溯.然而,使重复回溯(即仅+在主"循环"上)不会导致不匹配,而是导致运行时异常!(如ideone.com上所示):

Exception in thread "main" java.lang.StringIndexOutOfBoundsException:
    String index out of range: -1

    at java.lang.String.charAt(String.java:686)
    at java.lang.Character.codePointAt(Character.java:2335)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3344)
    at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:3994)
    at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:3966)
    at java.util.regex.Pattern$GroupCurly.match(Pattern.java:3916)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
    at java.util.regex.Matcher.match(Matcher.java:1127)
    at java.util.regex.Matcher.matches(Matcher.java:502)
    at java.util.regex.Pattern.matches(Pattern.java:930)
    at java.lang.String.matches(String.java:2090)

有人可以解释这里发生了什么吗 这是Java正则表达式引擎中的错误吗？

Answer 1

错误ID 6984178

有许多与引擎投掷相关的错误StringIndexOutOfBoundsException(请参阅:搜索结果.特别是已报告此内容并在内部接受为错误ID 6984178(可能需要一段时间才能显示在外部数据库中).

这是一个更简单的模式,可以重现bug(另请参见ideone.com):

System.out.println(
   "abaab".matches("(?x) (?: (?=(a+)) \\1 b )* x")
); // StringIndexOutOfBounds: -1

请注意,使用*?或*+只是false按预期返回.

看起来问题是由于在前瞻中有一个对捕获组的引用而试图回溯贪婪的重复时触发:越界索引是第一个和第二个之间的长度差异a+(例如,"aabaaaaab"获取-3).

人们可能不得不调试java.util.regex.Pattern源代码以查明错误的确切性质.

探索斐波那契模式

在Java引擎上,贪婪的回溯 +

这里有一个更详细的片段,展示了引擎如何在这种模式下获得的疯狂:

String FIBONACCI = 
    "(?x) .{0,2} | (?: (?=(\\2|^)) (?=(\\2\\3|^.)) (?=(\\1)) \\2)+ . ";

for (int n = 0; n < 1000; n++) {
    String s = new String(new char[n]);
    try {
        if (s.matches(FIBONACCI)) {
            System.out.printf("%n%s", n);
        }
    } catch (StringIndexOutOfBoundsException e) {
        String index = e.getMessage().replace("String index out of range: ", "");
        System.out.printf(" <%s:%s>", n, index);
    }
}

(稍微编辑过的)输出(如ideone.com上所示):

0 1 2 3 <5:-1>
6 <7:-1> ... <12:-1> <13:-3>
14 <15:-3> ... <33:-3> <34:-8>
35 <36:-8> ... <88:-8> <89:-21>
90 <91:-21> ... <232:-21> <233:-55>
234 <235:-55> ... <609:-55> <610:-144>
611 <612:-144> ...

所以引擎试图以-1,-3,-8,-21,-55,-144等方式访问字符串索引.请注意,这些是其他所有斐波纳契数,但是为负数.还需要注意的是超越了第几号,比赛的其余部分(6,14,35,......)是不是斐波那契数.

在.NET引擎上,贪婪的回溯 +

尽管该模式最初是为了占有量量词的必要性而编写的,但实际上回溯重复仍然会产生正确的答案(假设引擎不像Java那样错误).这是.NET引擎上的C#实现(另请参见ideone.com):

Regex r = new Regex(
  @"(?x) ^.{0,1}$ | ^(?: (?=(\2?)) (?=(\2\3|^.)) (?=(\1)) \2)+ . $ "
);

for (int n = 0; n < 1000; n++) {
  if (r.IsMatch("".PadLeft(n))) {
    Console.Write("{0} ", n);
  }
}
// 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 

正如您所看到的,即使使用回溯+"循环" ,输出也是正确的.事实上,正是因为它是一个回溯循环,特殊情况可以仅限于.{0,1}而不是.{0,2}.

在Java引擎上,不情愿的回溯 +?

这可以按预期在Java中使用.此外,因为它不情愿,我们也可以将特殊情况限制为.{0,1}(也见ideone.com):

String FIBONACCI = 
        "(?x) .{0,1} | (?: (?=(\\2|^)) (?=(\\2\\3|^.)) (?=(\\1)) \\2)+? . ";

关于算法

公式

该模式利用斐波那契数的第二个同一性:

这可以通过归纳证明.

模式

让我们使用这个版本的模式(在Java中工作,锚定时,也适用于C#):

                                                     summation 
free-space!                                            "loop"
    ?                                                     ?
   (?x) .{0,1} | (?: (?=(\2|^)) (?=(\2\3|^.)) (?=(\1)) \2)+? .
        \____/   \___________________________________/  ?    ?  
      base case      inductive case                    +Fi  +1
     for n = 0,1
                     (assertions don't "count" toward sum)!
                        $1 := $2    (or initialized with 0)
                        $2 := $2+$3 (or initialized with 1)
                        $3 := $1    (a temporary variable for the "swap")

基于[$1, $2] := [$2, $2+$1]转换,Fibonacci序列生成很简单.由于断言是按顺序执行的,因此引入了临时变量(就像单指派"伪代码"版本一样).