前言

最近同事反馈某个正则表达式在相关网站上面，能够正常去匹配字符串，但是在我们的系统中却抛出异常信息，如下：

于是我这边进行问题定位，发现是底层使用了 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 的标准正则表达式包java.util.regex，以及许多其他广泛使用的正则表达式包，如 PCRE、Perl 和 Python，都使用回溯实现策略：当一个模式呈现两个备选方案（如a|b）时，引擎将首先尝试匹配子模式a，如果结果不匹配，它将重置输入流并尝试匹配b。

回溯实现策略

回溯法，又称试探法，是常用的，基本的优选搜索方法。常用于解决这一类问题：给定一定约束条件 F（该约束条件常用于后面的剪枝）下求问题的一个解或者所有解。

回溯法其实是暴力枚举的一种改进，因为其会聪明的 filter 掉不合适的分支，大大减少了无谓的枚举。若某问题的枚举都是可行解得话，也就是没有剪枝发生，那么回溯法和暴力枚举并无二异。

不足之处

如果这样的选择是深层嵌套的，则此策略需要对输入数据进行指数级的传递，然后才能检测输入是否匹配。如果输入量很大，就很容易构造出运行时间超过宇宙生命周期的模式。当接受来自不受信任的源（如 web 应用程序的用户）的正则表达式模式时，这会产生安全风险。

在最坏的情况下，java.util.regex匹配器可能永远运行，或者超过可用堆栈空间而失败；这在 RE2/J 中永远不会发生。

如何选择正则表达式引擎呢？

1、StackOverflow 的一个回复

看样子是正则表达式算法的效率问题？RE2J 优先考虑效率，所以不支持 lookaround？

2、Go 对正则表达式引擎的选择

哦哦，原来 Go 是默认使用 NFA 的功能，因为效率优先的原则。

3、其他语言对正则表达式引擎的选择

3.1 正则表达式的 Lookaround

1）Lookaround包括Lookahead和Lookbehind两种匹配模式（Lookahead检测的是后缀，而Lookbehind检测的是前缀，它们有 Positive、Negative 两种匹配方式），而 google/re2 是不支持 lookaround 的。

2）fileconfig 服务中，同样使用了使用 google/re2 的实现，所以我们要将 Lookaround 的语法转换为非 Lookaround 使用；而用户使用的 path = ^(?!.*lib_tavcam).*(gradle)+(?!.*lib_tavcam.*)，是既有前瞻（lookahead），也有后视（lookbehind），所以判断为不合法。

3.2 JDK 与 Google 的引擎孰优孰劣？

在这个问题上，JDK 是能够正常识别 lookaround 的表达式，但是 google 选择效率优先，不支持 lookaround 的正则。

• 如果说你的系统是内部系统，确认不会出现 SQL 注入类似的安全问题，使用 JDK 原生的正则表达式引擎无疑让你的正则表达式支持范围更强大；

• 如果说你的系统是商业化系统，对安全问题是否看重，那么使用 Google 的 Re2j 引擎是不二选择。