前言
最近一个星期都在加班赶专题项目，腾讯 9 月 9 日公益日，我们公司踊跃（beipo）捐款 100w 换来腾讯大佬一点流量进行一下品牌推广。专题页面几个端推广，webview / app webview / 微信浏览器 / 小程序 webview / 手机浏览器。这个项目里面有个图片上传功能，一开始项目没那么紧张的时候就把几个端的图片上传兼容性问题整理一下，抽取一个各个端都可用的图片上传功能组件。
在测试的时候发现我们家的 app 在图片转换过程中卡死半分钟才有反应，然后开始排查问题，在最后找出了一个正则导致的问题。
围绕这个找一些资料，发现这个是一个叫做回溯灾难（backtracking catastrophic）的问题。
问题
在我的组件中，图片最终都会转为一个文件对象，会给出一个 FileDetail 的对象，大概是这样的, 两个字段，会给出类型和 base64。
1
2
3
4
5
| {
base64: 'data:image/jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIBAQIBAQICAgICAgICAwUDAwMDAwYEBAMFBwYHBwcGBwcICQsJCAgKCAcHCg0KCgsMDAwMBwkODw0MDgsMDAz/2wBDAQICAgMDAwYDAwYMCAcIDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDA....',
type: 'image/jpeg'
}
|
我的实现是这样的，后面我们看看正则表达式
1
2
3
4
5
6
7
8
9
10
11
| class FileDetail {
constructor(base64) {
const regMineType = /data\:(.+\/.+)\;/;
let execResult = regMineType.exec(base64);
if (execResult === null) {
throw new Error("非法的 base64 字符串");
}
this.base64 = base64;
this.type = execResult[1];
}
}
|
正则表达式长这样，它是用来匹配 base64 字符串的 minetype 的。
在电脑中测试得十分完美，微信中也是一样，没有什么大问题，但是在我家 app 中就会导致手机发热，卡死长达数十秒的问题。
1
| const regMineType = /data\:(.+\/.+)\;/;
|
后面我将表达式改成如下，就解决掉了问题了。
1
| const regMineType = /data\:(.+?\/.+)\;/;
|
正则表达式通配的匹配方式
正则中的 * + 这些都是采用贪心匹配的，也就意味着他们会尽可能多地匹配字符。
用以上的一段 base64 为例（这段 base64 只是节选，真正的 base64 都超级长，意味着匹配性能会差上百或者上千倍）。
1
| const regMineType = /data\:(.+\/.+)\;/;
|
这段表达式的表现是
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| - data:image/jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz/wYEBAMFBw
1 data:image/jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz|wYEBAMFBw(;)
2 data:image/jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD|gsMDAz/wYEBAMFBw(;)
3 data:image/jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD|AwMBwkODw0MD/gsMDAz/wYEBAMFBw(;)
4 data:image/jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc|GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz/wYEBAMFBw(;)
5 data:image/jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA|wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz/wYEBAMFBw(;)
6 data:image/jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB|AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz/wYEBAMFBw(;)
7 data:image/jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD|2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz/wYEBAMFBw(;)
8 data:image/jpeg;base64,/9j|4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz/wYEBAMFBw(;)
9 data:image/jpeg;base64,|9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz/wYEBAMFBw(;)
10 data:image/jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz/wYEBAMFBw(;)
11 [data:image|jpeg;]base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz/wYEBAMFBw(;)
|
因为是贪心匹配，一开始它会找到最后的一个斜杠，然后在去寻找分号，但发现没有分号，就需要缩小搜索范围（也就是不那么贪心，去找倒数第二个斜杠）。
按照这样一路持续下去，它要找 11 次才找到带分号的完整匹配。
后面按照我们的改造，改成非贪心匹配。
1
| const regMineType = /data\:(.+?\/.+)\;/;
|
1
2
3
| - data:image/jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz/wYEBAMFBw
1 data:image|jpeg;base64,/9j/4AAQSkZJRgABAQEBLAEsAAD/2wBDAAIB/AQIBAQICAgICAgICA/wUDAwMDAwYEBAMFBwYHBwc/GBwcICQsJCAgKCAcHCg0KCgsMD/AwMBwkODw0MD/gsMDAz/wYEBAMFBw
|
因为我们选用了非贪心匹配，所以看到正则会先选择最短的匹配长度进行匹配，它会按照尽可能小的搜索范围来进行匹配。
实际测试了一下，两种方法的时间相差了快几万倍，原因是实际的 base64 会很长，数据中会存在很多斜杠，导致贪心匹配会比非贪心匹配浪费了很多时间进行无效的匹配。
catastrophic backtracking
https://www.regular-expressions.info/catastrophic.html
这个网站说了一些关于回溯灾难的例子，所谓回溯，就是匹配中过度匹配，因为匹配过程中过度匹配了，导致程序需要重新按照另一种策略回头再匹配一次的过程。
就像贪心算法需要缩小搜索范围来搜索的过程，这就是过度匹配带来的问题，按照上面那个例子来说，就是该正则表达式回溯了 10 次才找到正确的结果。
我们需要对匹配结果和源匹配字符串有充分的理解才不会掉入重复回溯的灾难中。
每一个正则表达式都是一台状态机，真的需要好好构造它，我们才能够做出高性能的匹配。
贪心和从心
正则表达式是贪心好呢还是怂好呢，贪心又会掉入性能陷阱做无用功，但怂呢有时候又会匹配到错误结果。
这又让我想到了个两难问题，人是贪心点好呢，还是怂点好呢。
其实我发现这问题之后，就暗自决定自己以后要写得怂一点，匹配错了再贪心一点也不为过，一开始太贪心反而会出问题。
我自己还是比较怂的，物似主人形嘛。