JDK还是Google，正则表达式引擎孰优孰劣？
前言
最近同事反馈某个正则表达式在相关网站上面，能够正常去匹配字符串，但是在我们的系统中却抛出异常信息，如下：
于是我这边进行问题定位，发现是底层使用了Google的Re2j的正则表达式引擎，代码段如下：
public class TestGoogleCompile {
public static void main(String[] args) {
isPathValidateOfGoogleRe2j("^(?!.*aaa).*(bbb)+(?!.*aaa.*)");
}
private static boolean isPathValidateOfGoogleRe2j(String config) {
try {
com.google.re2j.Pattern.compile(config);
return true;
} catch (Exception ex) {
System.out.println(MessageFormat.format("isPathValidate error, config={0}, exception={1}",
config, ex.getMessage()));
return false;
}
}
}
好奇心驱使我去使用JDK原生的Regex正则表达式引擎，代码段如下：
public class TestJdkRegex {
public static void main(String[] args) {
isPathValidateOfJdkRegex();
}
private static void isPathValidateOfJdkRegex(){
String text = "aa.gradle";
String pattern = "^(?!.*lib_tavcam).*(gradle)+(?!.*lib_tavcam.*)";
Pattern p = Pattern.compile(pattern);
Matcher m = p.matcher(text);
// 调用匹配器对象的功能
if (m.find()) {
System.out.println(m.group());
}
}
}
TestJdkRegex 的运行结果一切正常，而TestGoogleCompile复现了bug。
Google的Re2j正则表达式引擎
RE2是一个正则表达式引擎，在输入的大小上以时间线性方式运行。RE2/J是RE2到纯Java的一个端口。
非确定性有限自动机
RE2算法使用非确定性有限自动机在一次传递输入数据时同时探索所有匹配。
所谓非确定性有限自动机（NFA）即：
对于某一个状态，读入某一个输入的时候，可能会有多种转移规则；
对于某一个状态，它可能会缺少对应某种输入的转移规则；
下面就是一个 NFA：
通过观察上图可以发现，在状态 1 输入 b 的时候，可能跳转到状态 1，也可能跳转到状态 2；而状态 4 则对任何输入不会有转移。这样的机器就是 NFA（Nondeterministic finite automata）。
JDK的Regex正则表达式引擎
Java的标准正则表达式包，以及许多其他广泛使用的正则表达式包，如PCRE、Perl和Python，都使用回溯实现策略：当一个模式呈现两个备选方案（如）时，引擎将首先尝试匹配子模式，如果结果不匹配，它将重置输入流并尝试匹配。
回溯实现策略
，又称试探法，是常用的，基本的优选搜索方法。常用于解决这一类问题：给定一定约束条件F（该约束条件常用于后面的剪枝）下求问题的一个解或者所有解。
回溯法其实是暴力枚举的一种改进，因为其会聪明的filter掉不合适的分支，大大减少了无谓的枚举。若某问题的枚举都是可行解得话，也就是没有剪枝发生，那么回溯法和暴力枚举并无二异。
不足之处
如果这样的选择是深层嵌套的，则此策略需要对输入数据进行指数级的传递，然后才能检测输入是否匹配。如果输入量很大，就很容易构造出运行时间超过宇宙生命周期的模式。当接受来自不受信任的源（如web应用程序的用户）的正则表达式模式时，这会产生安全风险。
在最坏的情况下，匹配器可能永远运行，或者超过可用堆栈空间而失败；这在RE2/J中永远不会发生。
如何选择正则表达式引擎呢？
1、StackOverflow的一个回复
看样子是正则表达式算法的效率问题？RE2J优先考虑效率，所以不支持lookaround？
2、Go对正则表达式引擎的选择
哦哦，原来Go是默认使用NFA的功能，因为效率优先的原则。
3、其他语言对正则表达式引擎的选择
3.1 正则表达式的Lookaround
包括和两种匹配模式（检测的是后缀，而检测的是前缀，它们有Positive、Negative两种匹配方式），而 是不支持lookaround的。
2）fileconfig服务中，同样使用了使用 的实现，所以我们要将 Lookaround 的语法转换为非 Lookaround 使用；而用户使用的path = ^(?!.*lib_tavcam).*(gradle)+(?!.*lib_tavcam.*)，是既有前瞻（lookahead），也有后视（lookbehind），所以判断为不合法。
3.2 JDK与Google的引擎孰优孰劣？
在这个问题上，JDK是能够正常识别lookaround的表达式，但是google选择效率优先，不支持lookaround的正则。
如果说你的系统是内部系统，确认不会出现SQL注入类似的安全问题，使用JDK原生的正则表达式引擎无疑让你的正则表达式支持范围更强大；
如果说你的系统是商业化系统，对安全问题是否看重，那么使用Google的Re2j引擎是不二选择。