大型迭代器超出最大调用堆栈大小

Question

我正在尝试将迭代器转换为数组。迭代器是在一个很长的字符串上调用 matchAll 的结果。迭代器（我假设）在字符串中有很多匹配项。首先，我尝试使用传播运算符：

const array = [...myLongString.matchAll(/myregex/g)];

这给了我错误：RangeError: Maximum call stack size exceeded

所以我尝试通过 next() 进行迭代：

const safeIteratorToArray = (iterator) => {
    const result = [];
    let item = iterator.next();

    while (!item.done) {
        result.push(item.value);
        item = iterator.next();
    }

    return result;
};

但这在 item = iterator.next() 行给了我同样的错误。所以我试着让它异步以重置调用堆栈：

const safeIteratorToArray = async (iterator) => {
    const result = [];
    let item = iterator.next();

    while (!item.done) {
        result.push(item.value);
        item = await new Promise(resolve => setTimeout(() => resolve(iterator.next())));
    }

    return result;
};

但我仍然得到同样的错误。

如果您对实际用例感到好奇：

我实际使用的正则表达式是：

 /\[(.+?)\] \[DEBUG\] \[Item (.+?)\] Success with response: ((.|\n)+?)\n\[/g

文本文件（它是一个日志文件）的内容通常如下所示：

[TIMESTAMP] [LOG_LEVEL] [Item ITEM_ID] Success with response: {
    ...put a giant json object here
}

重复那个令人作呕的广告，在每个日志之间换行。

Answer 1

（此处为 V8 开发人员。）

这与迭代器无关，与 RegExp 有关。

[更新]
看来我在测试中被错别字误导了，所以我之前的 explanation/suggestion 并没有解决问题。测试更正后，结果是只有表达式的末尾（我之前称之为“fishy”）需要修复。

栈内存大量消耗是因为(.|\n)是一个捕获组，匹配非常频繁。一种想法是将其写成 [.\n]，但是 . 元字符在 [...] 字符集中无效。

向@cachius 致敬，感谢他提出了一个优雅的解决方案：使用 the s flag 使 . 匹配 \n 个字符。
作为一个不相关的修复，更喜欢检查行首的结束 } 而不是下一个开始 [ ，这样匹配范围之间就没有重叠（这会让你错过一些匹配）。
因此，总而言之，将 ((.|\n)+?)\n\[/g 替换为 (.+?)\n}/gs。

[/更新]

这是一个可重现的例子。以下显示堆栈溢出：

let lines = ["[TIMESTAMP] [DEBUG] [Item ITEM_ID] {"];
for (let i = 0; i < 1000000; i++) {
  lines.push("  [0]");  // Fake JSON, close enough for RegExp purposes.
}
lines.push("}");
lines.push("[TIMESTAMP]");
let myLongString = lines.join("\n");

const re = /\[(.+?)\] \[DEBUG\] \[Item (.+?)\] ((.|\n)+?)\n\[/g;
myLongString.match(re);

如果将 const re = ... 行替换为：

const re = /\[(.+?)\] \[DEBUG\] \[Item (.+?)\] (.+?)\n}/gs;

然后堆栈溢出消失。

（可以进一步简化简化示例，但与原始案例的联系不会那么明显。）

[原文如下 post -- 我在这里解释的机制实际上是正确的，应用建议的替换确实提高了 25% 的性能，因为它使 RegExp 更容易匹配，但这还不够修复堆栈溢出。]
有问题的模式是：

\[(.+?)\]

毕竟，这意味着“[，然后是任意数量的任意字符，然后是 ]”。虽然我知道正则表达式可能 看起来 像魔术，但它们实际上是幕后真正的算法工作，有点像它们自己的微型程序。特别是，每当在字符串中遇到 ] 时，算法必须决定是将其算作“任意字符”之一，还是算作结束此序列的 ]。由于它无法神奇地知道这一点，因此它必须“牢记”（=在堆栈上）两种可能性，选择一种，如果结果不正确则回溯。由于此回溯信息保存在堆栈中（还有什么地方？），如果您将足够多的 ] 放入字符串中，堆栈将从 space.

中取出运行

幸运的是，解决方案很简单：因为您的实际意思是“一个 [，那么 不是 ] 的任意数量的字符, 然后是 ]", 你可以告诉 RegExp 引擎, 将 . 替换为 [^\]]:

\[([^\]]+?)\]

注意：((.|\n)+?)\n\[ 出于同样的原因似乎有问题，但根据这个测试似乎不是问题，即使我进一步增加输入大小。我不确定为什么；这可能是由于我如何创建测试。如果您发现实际输入有更多问题，可能也值得重新制定这部分内容。
[/原文post]

大型迭代器超出最大调用堆栈大小

Maximum call stack size exceeded for large iterators

javascript

callstack

iterator

iterable

v8