// A case of catastrophic backtracking in Java 8
//-----------------------------------------------
//
// regexp: (a*)*b
// strings: aa....
//
// compile: javac catastrophic.java
// call with: java catastrophic
//
// IMPORTANT:
// Java 9 improved its regex matching engine.
// This example is now much faster.
//
import java.util.regex.*;
public class catastrophic {
public static void main(String[] args) {
//we always run all the tests twice -> to warmup of the JVM
for (int runs = 0; runs < 2; runs++) {
Pattern pattern = Pattern.compile("(a*)*b");
// Run from 5 to 28 characters
for (int length = 5; length < 28; length++) {
// Build input of specified length
String input = "";
for (int i = 0; i < length; i++) { input += "a"; }
// Measure the average duration of two calls...
long start = System.nanoTime();
for (int i = 0; i < 2; i++) {
pattern.matcher(input).find();
}
// Print out time
System.out.println(length + " " + input + ": "
+ ((System.nanoTime() - start) / 2000000000d)
+ "s");
}
}
}
}