javascript - 如何避免 RegExp 中的灾难性回溯？

Question

我正在尝试为字符串测试制作一个正则表达式。

基本上我想要的是something-something。

'a' ===> TRUE
'abc' ===> TRUE
'a-b' ===> TRUE
'-' ===> FALSE
'a-' ===> FALSE
'-b' ===> FALSE

于是这个正则表达式的第一个版本诞生了。

/^[\w]+[-\s]?[\w]+$/

它工作正常，但如果字符串只有一个字母，它不会通过。

'a', failed

所以我修改了模式

^[\w]+([-\s]?[\w]+)*$

它工作正常，但如果测试的字符串很长(比如 20 多个字母)，浏览器会挂起，是的，我知道那里发生了什么，灾难性回溯。

那么在这种情况下，我该如何改进呢？

更新:

我想我错过了一个场景，它应该也支持重复组。

aaa aaa aaa aaa ===> TRUE
aaa-aaa aaa-aaa ===> TRUE

这就是为什么我用方括号制作组。

Answer 1

您遇到的问题是模式 ([-\s]?[\w]+)* 中的两次重复 - 您允许一个或多个 \w 和 一个可选的空格或破折号。该组也重复零次或多次，这将导致 catastrophic backtracking因为可选的 [-\s] 意味着有很多方法可以匹配相同的输入。例如abc可以匹配(\w\w\w), (\w\w)(\w), (\w)(\w\w)、(\w)(\w)(\w) 和正则表达式引擎将尝试所有这些可能性，因为模式 ([-\s]?[\w]+)* (或者通过删除破折号使其更明显 ([\w]+)*) 允许它.

当模式的结尾无法匹配时，将尝试所有可能性。例如，输入 "aaa-" - 最后一个 - 将失败，但正则表达式引擎将继续回溯并检查所有排列。

相反，您可以将正则表达式简化为此

/^\w+(?:[-\s]\w+)*$/

1. [\w] 不需要字符类 - 如果其中只有一项。这不会改变任何内容，但删除方括号会使其更易于阅读。
2. 如果你不提取模式的后半部分，那么你可以使用a non-capturing group - (?:)。
3. 使正则表达式的整个后半部分成为可选的。这意味着您或者匹配\w+(一个或多个单词字符)或者完整的\w+[-\s]\w+。引擎不会被迫重试失败的匹配。

最后一步是解决问题，其他只是轻微的清理。重要的是模式是受限制的，它不允许多种方式来匹配错误的输入 - [-\s] 和 \一样是强制的 w+ (至少一个)，因此重复组 (?:[-\s]\w+)* 不会有重叠匹配。如果我们手动展开为([-\s]\w\w\w)，([-\s]\w\w)([-\s]\w) 和 ([-\s]\w)([-\s]\w\w) 很容易看出这不会匹配相同的输入。

const regex = /^\w+(?:[-\s]\w+)*$/;

const valid = [
  'a',
  'abc',
  'a-b',
  'aaa aaa aaa aaa',
  'aaa-aaa aaa-aaa',
  'a'.repeat(100),
  `a-${'a'.repeat(100)}`,
  `a-${'a'.repeat(100)}-${'a'.repeat(100)}`,
  `a-${'a'.repeat(100)}-${'a'.repeat(100)}`,
  `a ${'a'.repeat(100)} ${'a'.repeat(100)}`,
  `a ${'a '.repeat(100)}a`,
]

const invalid = [
  '-',
  'a-',
  '-b',
  'aaa aaa aaa aaa-',
  `a-${'a'.repeat(100)}-${'a'.repeat(100)}-`,
  `a ${'a'.repeat(100)} ${'a'.repeat(100)} `,
  `a-${'-'.repeat(100)}`,
  `a ${' '.repeat(100)}`,
  `a-${'-'.repeat(100)}a`,
  `a ${'a '.repeat(100)}`,
  `-${'a'.repeat(100)}`,
  ` ${'a'.repeat(100)}`,
  `${'a'.repeat(100)}-`,
  `${'a'.repeat(100)} `,
  `a-${'a'.repeat(100)}-${'a'.repeat(100)}-`,
  `a-${'-'.repeat(100)}`,
  `a-${'a-'.repeat(100)}`,
  `-${'a'.repeat(100)}`,
  `${'a'.repeat(100)}-`,
]

console.log('---- VALID ----');
for (const s of valid) 
  test(s);

console.log('---- INVALID ----');
for (const s of invalid) 
  test(s);


function test(str) {
  console.log(`${str} ===> ${regex.test(str)}`);
}