为什么Java正则表达式引擎在使用+重复符号时会抛出StringIndexOutOfBoundsException异常？

Question

我写了一个正则表达式模式来查找斐波那契数列（不重要的是为什么，我只是这样做了）。它像预期的一样完美地工作（在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 

一个possessive重复（即在主“循环”上使用 ++ ）非常关键，因为您不希望在此匹配算法中回溯。但是，使重复可回溯（即仅在主“循环”上使用 + ）不会导致不匹配，而是会导致运行时异常！（如在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正则表达式引擎中的一个错误吗？

- polygenelubricants

---

我敢打赌，这是因为正则表达式引擎已经厌倦了被要求做一些愚蠢的事情 :-). - Stephen C

用正则表达式找斐波那契数列？Poly，你疯了！ - Andreas Dolk

现在这个正则表达式真是一团糟... :-) 我还在努力理解你的正则表达式... - aioobe

看起来像是个 bug。如果有帮助的话，它似乎通过了 4 号测试用例但在 5 号上失败了（这两个本应该是相同的）- http://ideone.com/EXStT 。最近我也很无聊，所以做了一些与 平衡组 相关的事情，不过那并不是很困难 :) - Kobi

就算是在.NET中，可回溯的重复操作也能够运行（http://ideone.com/yB16g）。我本以为回溯会导致不匹配。看来连我自己都没有完全理解我的算法 =)。 - polygenelubricants

Answer 1

Bug ID 6984178

与引擎抛出的StringIndexOutOfBoundsException相关的bug很多（请参见：搜索结果）。这个特定的bug已被报告并在内部接受为Bug 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那样有bug）。以下是在.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]转换。由于断言是按顺序执行的，所以引入了一个临时变量（就像单赋值“伪代码”版本一样）。请注意保留HTML标签。

- polygenelubricants

---

请注意，其中大多数错误报告涉及格式不正确的正则表达式或替换字符串以及它们的处理方式。唯一的错误是它应该抛出PatternSyntaxException（正则表达式）或IllegalArgumentException（替换），而不是SIOOBE。我已经尝试过让他们改变这一点，但没有成功。 - Alan Moore