Bug ID 6984178
There are many bugs related to the engine throwing StringIndexOutOfBoundsException (see: search results). This one in particular has been reported and internally accepted as Bug ID 6984178 (it may take a while for this to show up in the external database).
Here's a much simpler pattern that reproduces the bug (see also on ideone.com):
System.out.println(
"abaab".matches("(?x) (?: (?=(a+)) \\1 b )* x")
); // StringIndexOutOfBounds: -1
Note that using *? or *+ simply returns false as expected.
It looks like the problem is triggered by the attempt to backtrack a greedy repetition when there's a reference to a capturing group inside a lookahead: the out of bounds index is the difference in length between the first and the second a+ (e.g. "aabaaaaab" gets -3).
One would likely have to debug the java.util.regex.Pattern source code to pinpoint the exact nature of the bug.
Exploring the Fibonacci pattern
On the Java engine, with greedy backtracking +
Here's a more verbose snippet to show just how bonkers the engine gets on this pattern:
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);
}
}
The (slightly edited) output is (as seen on 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> ...
So somehow the engine tries to access string indices at -1, -3, -8, -21, -55, -144, etc. Note that these are every other Fibonacci number, but negative. Note also that beyond the first few numbers, the rest of the matches (6, 14, 35, ...) are NOT Fibonacci numbers.
On the .NET engine, with greedy backtracking +
While the pattern was originally written with the necessity for possessive quantifier in mind, in fact a backtracking repetition will still yield the correct answer (assuming the engine isn't buggy like Java's). Here's a C# implementation on the .NET engine (see also on 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
As you can see, the output is correct, even with a backtracking + "loop". In fact, precisely because it's a backtracking loop, the special case can be limited to just .{0,1} instead of .{0,2}.
On the Java engine, with reluctant backtracking +?
This works in Java as expected. Also, because it's reluctant, we can also limit the special case to just .{0,1} (see also on ideone.com):
String FIBONACCI =
"(?x) .{0,1} | (?: (?=(\\2|^)) (?=(\\2\\3|^.)) (?=(\\1)) \\2)+? . ";
On the algorithm
The formula
The pattern exploits the Second Identity of Fibonacci Numbers:
This can be proven by induction.
The pattern
Let's use this version of the pattern (which works in Java, and when anchored, also works in 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")
The Fibonacci sequence generation is straightforward, based on the [$1, $2] := [$2, $2+$1] transition. Since the assertions are performed sequentially, a temporary variable is introduced (just like the single-assignment "pseudocode" version).