Together for a Shared future
开发经验
最近我在实际工作中，接手了兄弟部门开发的一个模块，然后有部分用户提了一个问题到我这里。
经过一顿排查，原因竟然是：开发人员选择了不同的正则表达式引擎，导致了用户使用上的体验差异。
正则表达式的基础，大家可以通过菜鸟教程（https://www.runoob.com/regexp/regexp-intro.html）复习一下概念和正则语法~~
问题凸显
最近同事反馈某个正则表达式在相关网站上面，能够正常去匹配字符串，但是在我们的系统中却抛出异常信息，如下：
不同引擎的使用差异
于是我这边进行问题定位，发现是底层使用了 Google 的 Re2j 的正则表达式引擎，代码段如下：
代码语言：javascript复制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;
}
}
}isPathValidate error, config=^(?!.*aaa).*(bbb) (?!.*aaa.*),
exception=error parsing regexp:
invalid or unsupported Perl syntax: `(?!`然后使用 JDK 原生的 Regex 正则表达式引擎，代码段如下：
代码语言：javascript复制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());
}
}
}
aa.gradle结论：
相同的正则表达式，不同的表达式引擎，会出现不同的表现结果。两相对比，TestJdkRegex 的运行结果一切正常，而 TestGoogleCompile 复现了 bug。
Google 的 Re2j 正则表达式引擎
RE2/J 是 RE2 到纯 Java 的一个端口。
maven 依赖
代码语言：javascript复制<!-- https://mvnrepository.com/artifact/com.google.re2j/re2j -->
<dependency>
<groupId>com.google.re2j</groupId>
<artifactId>re2j</artifactId>
<version>1.0</version>
</dependency>非确定性有限自动机
RE2 是一个正则表达式引擎，在输入的大小上以时间线性方式运行。
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。
应用层
java.util.regex 包主要包括以下三个类：
- Pattern 类： pattern 对象是一个正则表达式的编译表示。Pattern 类没有公共构造方法。要创建一个 Pattern 对象，你必须首先调用其公共静态编译方法，它返回一个 Pattern 对象。该方法接受一个正则表达式作为它的第一个参数。
- Matcher 类： Matcher 对象是对输入字符串进行解释和匹配操作的引擎。与Pattern 类一样，Matcher 也没有公共构造方法。你需要调用 Pattern 对象的 matcher 方法来获得一个 Matcher 对象。
- PatternSyntaxException： PatternSyntaxException 是一个非强制异常类，它表示一个正则表达式模式中的语法错误。
回溯实现策略
回溯法，又称试探法，是常用的，基本的优选搜索方法。常用于解决这一类问题：给定一定约束条件 F（该约束条件常用于后面的剪枝）下求问题的一个解或者所有解。
回溯法其实是暴力枚举的一种改进，因为其会聪明的 filter 掉不合适的分支，大大减少了无谓的枚举。若某问题的枚举都是可行解得话，也就是没有剪枝发生，那么回溯法和暴力枚举并无二异。
不足之处
如果这样的选择是深层嵌套的，则此策略需要对输入数据进行指数级的传递，然后才能检测输入是否匹配。如果输入量很大，就很容易构造出运行时间超过宇宙生命周期的模式。当接受来自不受信任的源（如 web 应用程序的用户）的正则表达式模式时，这会产生安全风险。
在最坏的情况下，java.util.regex匹配器可能永远运行，或者超过可用堆栈空间而失败；这在 RE2/J 中永远不会发生。
Go 对正则表达式引擎的选择
显然， Go 正则表达式引擎，本质也 NFA 的应用，遵守效率优先的原则。
其他语言对正则表达式引擎的选择
问题原因：Lookaround
回到用户提到的问题，为什么google的表达式引擎，在解析执行时会抛异常呢？
1）Lookaround包括Lookahead和Lookbehind两种匹配模式
（Lookahead检测的是后缀，而Lookbehind检测的是前缀，它们有 Positive、Negative 两种匹配方式），而 google/re2 是不支持 lookaround 的。
2）部分功能使用了 google/re2 的实现，所以我们要将 Lookaround 的语法转换为非 Lookaround 使用；
而上面的案例，用户使用的 path = ^(?!.*lib_tavcam).*(gradle) (?!.*lib_tavcam.*)，是既有前瞻（lookahead），也有后视（lookbehind），所以判断为不合法。
如何选择正则表达式引擎呢？
那么在我们日常开发过程中，在 JDK 与 Google 的引擎应该进行什么选择呢？下面给出一些建议：
在这个问题上，JDK 是能够正常识别 lookaround 的表达式，但是 google 选择效率优先，不支持 lookaround 的正则。
- 如果说你的系统是内部系统，确认不会出现 SQL 注入类似的安全问题，使用 JDK 原生的正则表达式引擎无疑让你的正则表达式支持范围更强大；
- 如果说你的系统是商业化系统，对安全问题是否看重，那么使用 Google 的 Re2j 引擎是不二选择。
- 务必确保所有的模块都使用同一个技术栈，避免因为引擎选择不同，而导致的功能性兼容问题。
