Регулярное выражение занимает довольно много времени при несоответствии

ProgramBox

Регулярное выражение занимает довольно много времени при несоответствии

Post author:admin
Запись опубликована:9 ноября, 2022
Post category:Вопросы по программированию

#javascript #regex

#javascript #регулярное выражение

Вопрос:

У меня есть текст, похожий на следующий:

 rule "Example_Rule"
    dialect "java"
    no-loop true
    when
        $transaction : Transaction( someProperty1 == "123" )
    then
        $transaction.addReason( "SOME_MESSAGE" );
end

и я успешно обрабатываю его, используя приведенное ниже регулярное выражение:

 
const COLLECT_PATTERN = /[s]*(Number|ArrayList)?(?[ ]*(?:$transaction[ ]*:[ ]*)?([^)]*)?)?[ ]*(from accumulate|from collect)?[ ]*(?[ ]*([aA-zZ0-9]*)[ ]*([ ]*([^)]*))[ ]*(over window:length|over window:time)?[ ]*[(]?[ ]*([aA-zZ0-9 ]*)?[ ]*[)]?/;
const COLLECT_PATTERN_GLOBAL = /[s]*(Number|ArrayList)?(?[ ]*(?:$transaction[ ]*:[ ]*)?([^)]*)?)?[ ]*(from accumulate|from collect)?[ ]*(?[ ]*([aA-zZ0-9]*)[ ]*([ ]*([^)]*))[ ]*(over window:length|over window:time)?[ ]*[(]?[ ]*([aA-zZ0-9 ]*)?[ ]*[)]?/g;

const CONDITION_PATTERN = /([a-zA-Z0-9.$]*)[ ]*(==|!=|<=|>=|>|<|:|memberOf|not memberOf|before|after)[ ]*([[a-zA-Z0-9., $"]*]|[a-zA-Z0-9. $"]*)/;
const CONDITION_PATTERN_GLOBAL = /([a-zA-Z0-9.$]*)[ ]*(==|!=|<=|>=|>|<|:|memberOf|not memberOf|before|after)[ ]*([[a-zA-Z0-9., $"]*]|[a-zA-Z0-9. $"]*)/g;

const RULE_PATTERN = /([sS]*)(when)([sS]*)(then)([sS]*)(end)/;

try {

    var matches = myText.match(RULE_PATTERN);

    console.log(1);

    var whenList = matches[3].match(COLLECT_PATTERN_GLOBAL);

    console.log(2);

    whenList.forEach(function (when) {

        var whenParts = when.match(COLLECT_PATTERN);

        var conditions = [];
        var conditionList = whenParts[5] ? whenParts[5].match(CONDITION_PATTERN_GLOBAL) : null;
        var accumulateConditionList = whenParts[1] amp;amp; whenParts[2] ? whenParts[2].match(CONDITION_PATTERN_GLOBAL) : null;

        var whenClass = $scope.classes.find(function (clazz) { return clazz.simpleName === whenParts[2]; });

        if (conditionList) conditions = conditions.concat(parseConditions(conditionList, whenClass)); 

    ...
    // some code accessing some nested part of whenList
    ...

} catch (exception) {
    console.log(exception);
}

и parseConditions :

 var parseConditions = function (conditionList, whenClass, prefix) {

    var conditions = [];

    conditionList.forEach(function (condition) {

        var conditionParts = CONDITION_PATTERN.exec(condition);

        var value = conditionParts[3].trim(),
            operand = conditionParts[2].trim(),
            fieldItem = conditionParts[1].trim();

        var field = $scope.fields[whenClass.name].find(function (field) {
            return prefix ?
                field.name === prefix   '.'   fieldItem :
                field.name === fieldItem
        });

        ...
};

Но если я изменю текст на следующий:

 rule "Example_Rule"
    dialect "java"
    no-loop true
    when
        $transaction : Transaction( someProperty2 memberOf [SomeProperty.VALUE_1, SomeProperty.VALUE_2] ) // Some line that I expect not to be matched
    then
        $transaction.addReason( "SOME_MESSAGE" );
end

Я не ожидаю, что текст будет подобран идеально, но происходит следующее: я 1 печатаюсь, но для печати требуется вечность 2 . Сразу после этого я получаю: Property 'name' cannot be found on 'undefined' за 'whenClass.name' . Я думаю, что происходит то, что регулярное выражение on var whenList = matches[3].match(COLLECT_PATTERN_GLOBAL); попадает в какой-то бесконечный цикл / занимает слишком много времени для сопоставления. Лучший пример можно найти на github.com/hasancansaral/editor-demo

Я не ожидаю, что оно будет соответствовать, но мне нужно, чтобы оно быстрее завершалось сбоем. Как мне этого добиться, что я делаю не так?

1. В RULE_PATTERN вы можете выиграть, заменив каждое * на *? , сделав «все» совпадающим ленивым, а не жадным.

2. @trincot Эффект будет противоположным, если when появится ближе к концу строки. Замена жадности не учитывает лучшую скорость сопоставления с произвольными строками.

3. Это COLLECT_PATTERN_GLOBAL ужасно, это не будет работать быстрее. Это медленно, потому что — не говоря уже о неудачной [aA-zZ0-9 ] части, которая должна быть [a-zA-Z0-9 ] — все ее части являются необязательными (за исключением пары () ), и из-за этого многое может «попасть друг в друга» и вызвать катастрофический откат. Чтобы решить эту проблему, вы должны предоставить список требований к шаблону, чему он должен соответствовать. Пожалуйста, отредактируйте вопрос, указав эти данные.

Ответ №1:

Я считаю, что основная проблема заключается в этом коде. Чтобы исправить это, поместите вокруг этого условное обозначение, как вы делали с другими списками, которые вы создаете.

Это не должно выполняться, если whenParts[2] === null :

 var whenClass = $scope.classes.find(function (clazz) { 
    return clazz.simpleName === whenParts[2]; 
});

Объяснение:

В искомом тексте, вызывающем эту проблему, пример 2, whenParts[2] является null . Это приводит к find() поиску метода по всему списку классов. It ( find() ) в конечном итоге возвращается undefined .

(Здесь немного предположений, но, возможно, когда whenParts[2] null имя класса не найдено очень быстро? Невозможно узнать из вашего вопроса.)

Итак, whenClass.name не существует на undefined .

Кроме того, время появления или отсутствия 2 в консоли является просто результатом того, что цикл блокирует поток до его завершения. Рендеринг в консоли является асинхронным в большинстве реализаций и часто приводит к ложным показаниям, подобным этому.