Регулярное выражение для разбора горизонтальных правил в Markdown

Я - текущий сопровождающий Showdownjs, анализатор разметки, на котором основан файл PageDown (парсер разметки stackexchange).

Showdown использует следующее регулярное выражение для анализа горизонтальных правил:

/^( ?(-|\*|_) ?){3,}[ \t]*$/gm

Это работает отлично для большинства случаев. Однако следующий ввод:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - abc

делает библиотеку болезненно медленной (занимает около 10 секунд на nodeJS и дольше в браузерах). Чем больше тире вы добавляете, тем медленнее оно становится.

На самом деле, если вы скопируете введенный выше текст и вставьте его здесь в stackexchange, страница замерзнет. (stackexchange использует аналогичное регулярное выражение для синтаксического анализа <hr>)

Как я могу сделать это быстрее?

28 голосов | спросил Tivie 19 MonEurope/Moscow2016-12-19T14:18:13+03:00Europe/Moscow12bEurope/MoscowMon, 19 Dec 2016 14:18:13 +0300 2016, 14:18:13

3 ответа


32

Поздравляем, что у вас здесь есть случай действительно очень плохого отступления. Помните об отключении StackOverflow в ​​июле 2016 года ? Потому что это объясняется довольно хорошо там.

regex101 настолько любезен сообщить нам в виде отладчика , сколько шагов выполняет регулярное выражение, пока оно не будет соответствовать , Если вам интересно, это 111,803

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

/^( ?[-_*]){3,} ?[\t]*$/

Уже сокращает распознавание несоответствия шаблона в вашем примере до минимальных 272 шагов. Обратите внимание, что я взял на себя смелость заменить вашу группу захвата ORing значительно более «легким» классом символов. Функциональность в основном эквивалентна, если мы игнорируем тот факт, что группа захвата, которую вы используете, приводит к несовпадению и дополнительным шагам.
Это изменение облегчает регулярное выражение для регулярного выражения.

Единственное существенное различие между вашим шаблоном и моим состоит в том, что моя не распознает «нестандартную» (насколько это определено в уценке):

-  -  -
- - - // as opposed to this with only one space between dashes

и тот факт, что он не демонстрирует катастрофического обратного следования :) проверить его на regex101

ответил Vogel612 19 MonEurope/Moscow2016-12-19T14:37:25+03:00Europe/Moscow12bEurope/MoscowMon, 19 Dec 2016 14:37:25 +0300 2016, 14:37:25
7

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

Я хотел бы добавить, что в PCRE также возможно сделать {3,} не обратный путь вообще. Вы можете сделать это, добавив за ним +. В этом случае он полностью эквивалентен, потому что часть до и после добавления + не перекрывается (кроме дополнительного пространства). Следующему регулярному выражению требуется только 196 шагов, чтобы найти, что он не соответствует:

^( ?(-|\*|_) ?){3,}+[ \t]*$

Если я объединю это с трюком Vogel612 по удалению нескольких опций в соответствии с пробелами, я могу получить его до 103:

^( ?[-_*]){3,}+ ?[\t]*$
ответил TimVdE 19 MonEurope/Moscow2016-12-19T18:58:32+03:00Europe/Moscow12bEurope/MoscowMon, 19 Dec 2016 18:58:32 +0300 2016, 18:58:32
2

Теперь я могу ошибаться, но я могу соответствовать:

------- от 3 и вверх

- - - - - от 3 и вверх

Пока не сопоставляется пример 'abc' (или любая строка, которая бросает символ горизонтального правила в микс в любом месте строки):

/^ *[\-\*_] *[\-\*_] *[\-\*_][\-\*_ \t]*$/ в 66 шаги.

Моя единственная проблема заключается в том, что я не уверен, что вы хотите разрешить несколько пробелов между символами горизонтального правила. Поскольку это определенно позволяет добавлять дополнительные пробелы между символами.

Если возможность добавления дополнительных пробелов не является проблемой, будет ли это законным вариантом для сокращения количества требуемых шагов поиска?

Вы можете проверить шаблон на regex101

ответил Matthew C. Lewis 26 Jam1000000amThu, 26 Jan 2017 08:54:24 +030017 2017, 08:54:24

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132