写了一个假的正则 验证URL , 可以卡掉浏览器

Question

var reg = /^(https?:\/\/)([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/

var url = "https://www.amazon.com/Kipling-BP3872-Ravier-Houndstooth-Multi/dp/B00RUBLS58/ref=s9u_simh_gw_i5?_encoding=UTF8&fpl=fresh&pf_rd_m=ATVPDKIKX0DER&pf_rd_s=&pf_rd_r=8A9F9XHY539KKRA96135&pf_rd_t=36701&pf_rd_p=a6aaf593-1ba4-4f4e-bdcc-0febe090b8ed&pf_rd_i=desktop";


reg.test(url)

在谷歌浏览器下运行

有大神可以指导一下 ，为什么会卡掉吗？

Answer 1

console.time('/X(.+)+X/ test');
"==XX=============================".match(/X(.+)+X/);
console.timeEnd('/X(.+)+X/ test');

试试这个，也会卡住。

当然现在我还解释不了，只能先告诉你这个貌似是 NFA 引擎的回溯失控导致的。 所以才能用这个方法检测 NFA 和 DFA 了。

NFA 是 表达式主导引擎，DFA 则是 文本主导引擎，js是传统型NFA。

正则引擎主要可以分为两大类：一种是DFA，一种是NFA。这两种引擎都有了很久的历史(至今二十多年)，当中也由这两种引擎产生了很多变体！于是POSIX的出台产生规范了不必要变体的继续产生。这样一来，目前的主流正则引擎又分为3类：一、DFA，二、传统型NFA，三、POSIX NFA。
DFA 引擎在线性时状态下执行，因为它们不要求回溯（并因此它们永远不测试相同的字符两次）。DFA 引擎还可以确保匹配最长的可能的字符串。但是，因为 DFA 引擎只包含有限的状态，所以它不能匹配具有反向引用的模式；并且因为它不构造显示扩展，所以它不可以捕获子表达式。
传统的 NFA 引擎运行所谓的“贪婪的”匹配回溯算法，以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配，所以它可以捕获子表达式匹配和匹配的反向引用。但是，因为传统的 NFA 回溯，所以它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。因此，在最坏情况下，它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现。

Answer 2

@sanae 是正解，

很多regex engine都是基于NFA回溯的，遇到 ** 就会傻逼了，

你把状态机的图画出来，手动做一次DFS就知道了，

一个*是这样的：

**则是这样的：

中间多出了一个环，本来一个*失配的时候就可以跳出去了，现在多了一个*，失配后又重新进入下个*了，一下子回溯的次数指数式上涨，就出现了题目卡死的情况

Answer 3

中括号里面的东西不需要转义的。

Answer 4

([\/\w \.-]*)*后面的星号去掉就好了