Node.js зависание dom-парсера tagRegExp соответствует регулярному выражению: катастрофический откат назад?

Question

Я использую dom-анализатор node.js, который (не обязательно) извлекает теги из DOM с помощью регулярных выражений.

Вы можете найти dom-parser по адресу: https://github.com/ershov-konst/dom-parser

Иногда HTML некоторых веб-страниц (например, https://www.ecosia.org/) приводит к зависанию приложения node.js.Я протестировал использование простого ванильного сценария сопоставления и обнаружил, что tagRegExp приводит к зависанию сценария (возможно, из-за катастрофического обратного отслеживания?)

Я на самом деле использую его для нахождения ссылки rel = "canonical" и href= "xyz" (если есть, у Ecosia нет канонического).

tagRegExp:

/(<\/?[a-z][a-z0-9]*(?::[a-z][a-z0-9]*)?\s*(?:\s+[a-z0-9-_]+=(?:(?:'[\s\S]*?')|(?:"[\s\S]*?")))*\s*\/?>)|([^<]|<(?![a-z\/]))*/gi

Сценарий тестирования чистого JS:

<script type="text/javascript">
var text = '... html source ...';
var text_esc = text
text_esc = text_esc.replace(/\</g, "&lt;");
text_esc = text_esc.replace(/\>/g, "&gt;");
var regex = /(<\/?[a-z][a-z0-9]*(?::[a-z][a-z0-9]*)?\s*(?:\s+[a-z0-9-_]+=(?:(?:'[\s\S]*?')|(?:"[\s\S]*?")))*\s*\/?>)|([^<]|<(?![a-z\/]))*/gi;
var found = text.match(regex);
var found_len = found.length;

document.write("Text: " + text_esc + "<br /><br />" + "Regex pattern: " + regex + "<br /><br />");

document.write("Matches: " + found_len + "<br /><br />");

for (var i=0;i<found_len;i++)
{
    found[i] = found[i].replace(/\</g, "&lt;");
    found[i] = found[i].replace(/\>/g, "&gt;");

    document.write("[" + i + "]: " + found[i] + "<br /><br />");
}
</script>

Любые идеи приветствуются.Заранее спасибо.

Answer 1

Проблема вызвана шаблонами [\s\S]*? и неэффективным шаблоном (x|[^x])*.

Вы можете использовать

/(<\/?[a-z][a-z0-9]*(?::[a-z][a-z0-9]*)?\s*(?:\s+[a-z0-9-_]+=(?:'[^']*'|"[^"]*"))*\s*\/?>)|[^<]*(?:<(?![a-z\/])[^<]*)*/gi

'[\s\S]*?' превращается в '[^']*'где [^']* - жадно выраженный класс отрицанных символов, соответствующий любому символу, кроме ' и "[\s\S]*?", обрабатываются таким же образом.Класс отрицанных символов лучше, чем .*? ленивый аналог, так как он соответствует всем символам, отличным от указанного (ых), за один раз, и движку регулярных выражений не нужно проверять все последующие подшаблоны после этого шаблона, а затем расширяться каждый раз приошибка.

([^<]|<(?![a-z\/]))* может быть развернутым как [^<]*(?:<(?![a-z\/])[^<]*)*, он будет соответствовать тем же текстам, но быстрее (так же, как и раньше, класс отрицанных символовшаблоны с жадными квантификаторами быстрее проходят по тексту).

Примечание. Я также удалил несколько избыточных групп без захвата.