JavaScript regex exec выполняется слишком долго - PullRequest
Новая
       8

JavaScript regex exec выполняется слишком долго

3 голосов
/ 09 июля 2009

У меня есть простая проверка регулярных выражений JavaScript (написанная другим разработчиком), которая отлично работает на тысячах различных строк. Однако я только что обнаружил одно конкретное строковое значение, которое вызывает выполнение этого регулярного выражения в Firefox / IE 10 минут, что недопустимо. Для вашего удобства я извлек реальный вызов regex в небольшой фрагмент кода: 

<html>
  <script>
    function dodo(){
      var mask = /^([\w'#@\-\&\(\)\/.]+[ ]*){1,100}$/;
      var value = "Optometrists Association Australia, Queensland/NT Division";
      mask.exec(value);
    }
  </script>
  <body>
    <input type="button" value="Click" onclick="dodo()">
  </body>
</html>

В чем здесь проблема? Если я изменю значение на что-то еще, оно будет отлично работать.

Спасибо!

Ответы [ 4 ]

6 голосов
/ 09 июля 2009

Возможно, вы имели в виду + ​​после пробела, а не *. Если вы замените его обратно на +, все пойдет намного быстрее. Символ * заставляет анализатор регулярных выражений пробовать огромное количество комбинаций, каждая из которых завершается неудачей, когда достигает значения «,» Возможно, вы захотите добавить ',' и к первой группе символов.

В целом, это может выглядеть так: 

var mask = /^([\w'#@\-\&\(\)\/.,]+[ ]+){1,100}$/;
6 голосов
/ 09 июля 2009

Вы работаете с сумасшедшим возвратом, распространенной функцией в регулярных выражениях, которая включает в себя что-то вроде формы ([символы] +) + - она ​​отлично работает для всех типов совпадающих шаблонов, но затем вы найдете строку, подобную этой , который заставляет его взорваться, повторяя всю строку. Вот набросок того, что происходит.

Для начала ваш шаблон разбивает строку на группы. Я использую | для запуска экземпляров вашей группы, которые вы повторяете {1,100}. > - это конец группы, а ? - это «курсор» анализатора регулярных выражений. 

|----------->|---------->|-------?
Optometrists Association Australia, Queensland/NT Division

В? Ваш шаблон не может больше соответствовать символам или пробелам, поэтому он пытается соответствовать $. Поскольку курсор еще не достиг конца строки, он завершается ошибкой, и анализатор регулярных выражений возвращается: 

|----------->|---------->|------?
Optometrists Association Australia, Queensland/NT Division

Еще раз, он не может найти ни одного пробела, поэтому он завершает группу и пытается запустить еще один (поскольку может быть до 100, а мы пока использовали только 3). 

|----------->|---------->|------|-?
Optometrists Association Australia, Queensland/NT Division

Синтаксический анализатор снова достиг проблемного ,, и он убивает это дерево выполнения, заставляя его еще раз вернуться к i в Australia. И, как и в прошлый раз, он пытается создать группу: 

|----------->|---------->|-----|--?
Optometrists Association Australia, Queensland/NT Division

... в любом случае, вы поняли идею. Этот цикл сбоя, возврата и среза снова фактически заморозит ваш анализатор Regex, пока он не исчерпает каждую перестановку и не вернет false. Ключом к распознаванию и исправлению этого является то, что никогда не повторяет повторяющуюся группу без какой-либо формы разделителя в начале и / или конце. Я бы предложил использовать привязку границы слова \b, поскольку [ ]+ потребует, чтобы ваши строки заканчивались пробелами: 

/^(\b[\w'#@\-\&\(\)\/.]+\b[ ]*){1,100}$/

В качестве дополнительного примечания трудно сказать, что делает ваше регулярное выражение без дополнительного контекста, но кажется, что вы также можете просто вызвать value.split(' '), чтобы разбить строку на пробельные символы и выполнить более простое регулярное выражение для всех этих подстроки. Это исключило бы необходимость повторения двойного регулярного выражения.

4 голосов
/ 09 июля 2009

Это выглядит как плохое приложение для регулярных выражений и плохое регулярное выражение для загрузки. Я думаю, что цель состоит в том, чтобы соответствовать списку от 1 до 100 разделенных пробелами слов. Вот основные проблемы, которые я вижу:

  1. Использование «[] *» в конце слова вместо «[] +» означает, что каждый байт потенциально может быть одним «словом», независимо от того, ограничен он пробелами или нет. Это множество совпадений для вашего двигателя, чтобы отслеживать.

  2. Вы используете фиксирующие скобки ("(...)") вместо нефиксированных ("(?: ...)"). Группировка будет выполнять еще большую опеку, чтобы сохранить последнее слово, которое вам подходит, что вам, вероятно, нужно или нет.

И некоторые незначительные проблемы:

  1. Выражение "[] *" является избыточным. Просто используйте «*», чтобы найти ноль или более пробелов. Но вы, вероятно, хотите, чтобы "\ s" соответствовал пробелам любого типа, а не только пробелу.

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

  3. Для удобства чтения не используйте обратную косую черту, где она не нужна. Только «-» в вашей скобке действительно нуждается в этом.

  4. Что такое магия около 100? Вы действительно хотите жестко закодировать это ограничение?

Наконец, зачем вообще здесь использовать регулярное выражение? Почему бы просто не разбить () на пустом пространстве на массив подстрок, а затем проверить каждое полученное слово на предмет более простого выражения?

1 голос
/ 09 июля 2009

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

...