JS编程建议——45：警惕嵌套量词和回溯失控

建议45：警惕嵌套量词和回溯失控
嵌套量词总是需要额外的关注和小心，以确保没有掩盖回溯失控问题。嵌套量词出现在一个自身被重复量词修饰的组中。
嵌套量词本身并不会造成性能危害，只是在尝试匹配字符串过程中，很容易不小心在内部量词和外部量词之间，产生一大堆分解文本的方法。例如，要匹配HTML 标签，使用了下面的正则表达式：
/<(?:¹|"²"|'³')*>/
这也许过于简单，因为它不能正确地处理所有情况的有效和无效标记，但在处理有效HTML 片段时应该没什么问题。与更加简单的/<⁴*>/相比，它的优势在于涵盖了出现在属性值中的>符号。在非捕获组中它不使用第二和第三分支，仅匹配单引号和双引号包围的属性值，除特定的引号外允许所有字符出现。
虽然遇到了嵌套量词*，但目前还没有回溯失控的危险。在分组的每次重复过程中，由于第二和第三分支选项严格匹配一个带引号的字符串，所以潜在的回溯点数目随目标字符串长度而呈线性增长。
但是，查看非捕获组的第一分支：¹，每次只匹配一个字符，效率似乎有些低。在字符类后面加一个量词会更好些，这样每次组重复过程就可以匹配多于一个的字符了。正则表达式可以在目标字符串的位置上发现一个匹配。通过每次匹配多个字符，正则表达式会在成功匹配的过程中跳过许多不必要的步骤。
如果正则表达式匹配一个“<”字符，但后面没有“>”，则可以令匹配成功完成，回溯失控就会进入“快车道”，因为内部量词和外部量词的排列组合产生了数量巨大的分支路径（跟在非捕获组之后）用以匹配“<”之后的文本。正则表达式在最终放弃匹配之前必须尝试所有的排列组合。
关于嵌套量词导致回溯失控，一个更加极端的例子是，在一大串A 上应用正则表达式/(A+A+)+B/。虽然这个正则表达式写成/AA+B/更好，但为了讨论方便，设想一下两个A 能够匹配同一个字符串的多少种模板。
当应用在一个由10 个A 组成的字符串上（“AAAAAAAAAA”）时，正则表达式首先使用第一个A+匹配所有10 个字符，然后正则表达式回溯一个字符，让第二个A+匹配最后一个字符。这个分组试图重复，但没有更多的A ，而且分组中的+量词已经符合匹配所需的最少一次，因此正则表达式开始查找B。虽然正则表达式没有找到B，但是还不能放弃，因为还有许多路径没有被测试过。如果第一个A+匹配8 个字符，第二个A+匹配2 个字符会怎么样呢？或者第一个匹配3个，第二个匹配2个，分组重复两次，又会怎么样呢？如果在分组的第一遍重复中，第一个A+匹配2个字符，第二个A+匹配3 个字符，然后在第二遍重复中，第一个匹配1 个，第二个匹配4个，又怎么样呢？
正则表达式在最坏情况下的复杂性是惊人的O(2n)，也就是2 的n 次方。n 表示字符串的长度。在由10 个A 构成的字符串中，正则表达式需要1024 次回溯才能确定匹配失败，如果是20 个A，回溯的数字剧增到一百万以上。25 个A足以挂起Chrome、IE、Firefox和Opera 浏览器至少10 分钟（如果还没死机）用以处理超过34 000 000次回溯以排除正则表达式的各种排列组合。唯一的例外是最新的Safari浏览器，它能够检测到正则表达式陷入了循环，并快速终止匹配（Safari 浏览器还限定了回溯的次数，超出则终止匹配尝试）。
预防此类问题的关键是确保正则表达式的两个部分不能对字符串的同一部分进行匹配。这个正则表达式可重写为/AA+B/，但复杂的正则表达式可能难以避免此类问题。虽然还有其他解决办法，但是增加一个模拟原子组往往作为最后一招使用，如果可能，尽可能保持正则表达式简单易懂。如果这么做，此正则表达式将改成/((?=(A+A+))2)+B/，就可以彻底消除回溯问题。