Отладка RegEx

Ответ 1

Я бы не стал полагаться ни на количество шагов, ни на какую-либо отладку как тест
либо отступления, либо сбой.

Как правило, избегайте простых конструкций, таких как (A+)*, что не только backtrack внутренний A+, но также возвращает outter (..)*.
Каждый проход наружу дает новую (новую) внутреннюю серию возврата.

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

Ниже приведен пример (A+)? vs (A+)*. Мы установили цель для известного отказа

и неуклонно увеличивать длину, чтобы продлить обработку этого отказа.

Если вы посмотрите на regex 2 (A+)*, вы можете заметить экспоненциальное увеличение просто увеличивается три цели.
Наконец, мы продуваем цель, чтобы перегрузить внутренние ресурсы двигателя.

Изменить. После некоторого анализа я публикую небольшой вывод о шагах возврата.
При анализе контрольного времени, приведенного ниже, обратное отслеживание, по-видимому, является процессом 2 ^ N.
Где N - количество символов, которые возвращаются с ошибкой.

Учитывая простой случай Revo, немного легче изолировать откат.
Потому что это похоже на то, что% 98 от общего времени занимает просто откат.

Учитывая это предположение, можно взять результаты времени из 2 точек и сгенерировать уравнение.

Форма используемого уравнения была f(x) = a * r^x.
Приведенные координаты (# из "А против времени" ), используя точки (7, 1.13), (9, 4.43), которые порождали это f(x) = 0.009475 * 1.9799 ^ x
что на самом деле это # sec = 0.009475 * 1.9799 ^ # letters
Я запустил все количество букв "А" из приведенного ниже теста в эту формулу.

#LTR   Bench Time
 7         1.13
 9         4.43
13        70.51

который произвел точное контрольное время (+/-.1%).

Затем я увидел, что 1.9799 довольно близко к 2.0, поэтому я скорректировал коэффициент "a" до 0,009 и снова запустил его, получив следующее:

f(7 letters) = 2 ^ 7 * .009 =  1.152 sec’s
f(9 letters) = 2 ^ 9 * .009 =  4.608 sec’s
f(13 letters) = 2 ^ 13 * .009 =  73.728 sec’s
f(27 letters) = 2 ^ 27 * .009 =  1207959.552 sec’s = 335 hours  

Теперь кажется довольно ясным, что шаги отступания коррелируют с числом буквы для возврата в соотношении 2 ^ N.

Я также считаю, что это справедливая ставка, что некоторые двигатели могут сделать эту простую математику 2 ^ N только в простом сценарии, подобном этому. Кажется, это время, когда двигатель немедленно возвращается и говорит Слишком сложно!.
Перевод здесь состоит в том, что регулярное выражение достаточно простое, чтобы движок мог обнаружить его. В других случаях двигатель никогда не возвращается,
он висел, и может вернуться через год или два (или десять...).

Заключение, следовательно, не в том, что двигатель отступит, но будет, но как будет ли ваша целевая строка влиять на обратную трассировку.

Таким образом, бдительность требуется при написании регулярного выражения и должна быть настороже против
вложенных открытых кванторов.

Я бы сказал, что лучший выбор - всегда сильно ударить по регулярному выражению, чтобы он не получился.
И я говорю о чрезмерных повторяющихся литералах в подозрительных местах.
end edit

Приложение Benchmark

Цель: AAAAAAAC

Контрольная точка

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.07 s,   72.04 ms,   72040 µs


Regex2:   ^(A+)*B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    1.13 s,   1126.44 ms,   1126444 µs

Цель: AAAAAAAAAC

Контрольная точка

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.08 s,   82.43 ms,   82426 µs


Regex2:   ^(A+)*B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    4.43 s,   4433.19 ms,   4433188 µs

Цель: AAAAAAAAAAAAAC

Контрольная точка

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.10 s,   104.02 ms,   104023 µs


Regex2:   ^(A+)*B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    70.51 s,   70509.32 ms,   70509321 µs

Цель: AAAAAAAAAAAAAAAAAAAAAAAAAAAC

Контрольная точка

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.18 s,   184.05 ms,   184047 µs


Regex2:   ^(A+)*B
Options:  < none >
Error:  Regex Runtime Error !!   
Completed iterations:   0  /  50     ( x 1000 )
Matches found per iteration:   -1
Elapsed Time:    0.01 s,   7.38 ms,   7384 µs


Error item 2 :  Target Operation .. 

The complexity of matching the regular expression exceeded predefined
bounds. Try refactoring the regular expression to make each choice made by
the state machine unambiguous. This exception is thrown to prevent
"eternal" matches that take an indefinite period time to locate. 

Ответ 2

TL; DR

Короче говоря, "backtracking" - это когда механизм regex возвращается к "гибкому" совпадению, пытаясь найти другой путь для успешного совпадения.

Откат с чередованием

Например, в следующем шаблоне и вводе:

foo(bar|baz)

foobaz

Механизм regex будет соответствовать "foo", а затем попытается выполнить первый из двух параметров, соответствующий "b", а затем "a" , но не получится "r". Вместо того, чтобы проваливать весь матч, он будет "перематывать ленту" и начать со второй альтернативы, соответствующей "b", затем "a" , а затем "z"... успех!

Откат с кванторами

Это также работает с квантификаторами. Квантификатор - это все, что побуждает двигатель соответствовать повторяющемуся шаблону, включая ?, *, + и {n,m} (в зависимости от двигателя).

Жадный квантификатор (по умолчанию) будет соответствовать столько повторений, сколько возможно, прежде чем перейти к остальной части шаблона. Например, учитывая рисунок и ввод ниже:

\w+bar

foobar

Образец \w+ начнется с сопоставления всей строки: "foobar". Однако, когда он переходит к b, механизм регулярных выражений достигает конца ввода, и совпадение не выполняется. Вместо того, чтобы просто отказаться, двигатель попросит последнего жадного квантора отказаться от одного из своих повторений, теперь совпадающего с "fooba". Матч все еще не удается, поэтому двигатель просит \w+ отказаться от "a" (сбой), а затем "b". После отказа от "b" двигатель теперь может соответствовать bar, и совпадение будет успешным.

Деревья и обратная трассировка

Еще один способ мышления регулярного выражения - это "дерево", а обратное отслеживание возвращается к node и пытается использовать другой путь. Учитывая шаблон foo(bar|baz) и ввод "foobaz", движок попытается сделать что-то вроде следующего:

foo(bar|baz)
|\
| \
|  : f (match)
|  : o (match)
|  : o (match)
|  | (bar|baz)
|  |\
|  | \
|  |  : b (match)
|  |  : a (match)
|  |  : r (FAIL: go back up a level)
|  |  ^
|  |\
|  | \
|  |  : b (match)
|  |  : a (match)
|  |  : z (match)
|  | /
|  |/
| /
|/
SUCCESS

Подсчет "Backtracks"

Относительно того, почему вы видите различия в "количестве" обратных потоков... это, вероятно, имеет много общего с внутренними оптимизациями и уровнем ведения журнала. Например, RegexBuddy, похоже, не регистрирует совпадение с пустой строкой до ^, тогда как regex101 делает. В конце концов, однако, на самом деле не имеет значения, какой точный порядок вы возвращаетесь (какой порядок вы поднимаете назад по дереву), пока вы заканчиваете тем же результатом.

Evil Regexes

Вы уже знаете это, но в интересах любого другого, кто случился, ваше регулярное выражение было написано, чтобы продемонстрировать " катастрофическое обратное отслеживание" ( aka "злое регулярное выражение" ), где количество попыток возврата увеличивается экспоненциально по мере увеличения длины ввода. Эти регулярные выражения могут быть использованы для выполнения DoS-атак, поэтому вам следует проявлять осторожность, чтобы не вводить их в свои шаблоны (как Я узнал).