Чорна діра бектрекінгу
Рано чи пізно, з цим стикається будь-який розробник, тому що ненароком створити такий регулярний вираз - легше легені.
Типова ситуація, коли регулярний вираз до певного часу працює нормально, і раптом на якомусь тексті почне «підвішувати» інтерпретатор і є 100% процесора.
План викладу у нас буде таким:
- Спочатку подивимося на проблему у реальній ситуації.
- Потім спростимо реальну ситуацію до коренів і побачимо, звідки вона береться.
Розглянемо, наприклад, пошук за HTML.
Ми хочемо знайти теги з атрибутами, тобто збіги .
Найпростіший спосіб це зробити – ]*> . Але він же і не зовсім коректний, тому що тег може виглядати так: "href="#">. Тобто, всередині «загартованого» атрибуту може бути символ >. Найпростіший регексп на ньому зупиниться і знайде.
А нам потрібний весь тег.
Щоб правильно обробляти такі ситуації, потрібно врахувати їх у регулярному вираженні. Воно матиме вигляд.
Якщо перекласти мовою регекспів, то: :
- - Початок тега
- (\s*\w+=(\w+"[^"]*")\s*)* – довільна кількість пар виду слово=значення , де «значення» може бути також словом \w+ , або рядком у лапках "[^ "]*" .
Ми поки що не враховуємо всі деталі граматики HTML, адже рядки можливі й у „одинарних“ лапках, але на даний момент цього достатньо. Головне, що регулярне вираження вийшло в міру простим та зрозумілим.
Випробуємо отриманий регексп у дії:
Чудово, все працює! Знайшло як довгий тег " href="#"> , так і самотній.
А тепер – демонстрація проблеми.
Якщо запустити приклад нижче, він може підвісити браузер:
Деякі двигуни регулярних виразівможуть у розумний час розібратися з таким пошуком, але більшість – ні.
В чому справа? Чому нескладний регулярний вираз на такому невеликому рядку «висне» наглухо?
Спростимо ситуацію, видаливши тег і можливість вказувати рядки в лапках:
На цьому ми закінчимо з демонстрацією «практичного прикладу» і перейдемо до того, що відбувається.
Бектрекінг
Як ще простіший регулярний вираз, розглянемо (\d+)*$ .
У більшості движків регекспів, наприклад, у Chrome або IE, цей пошук виконується дуже довго (обережно, може «підвісити» браузер):
У чому ж справа, що не так із регекспом?
Уважний читач, подивившись на нього, напевно здивується, адже він якийсь дивний. Квантифікатор тут виглядає зайвим.
Якщо хочеться знайти число, то з тим самим успіхом можна шукати \d+$.
Так, цей регексп має штучний характер, але, розібравшись з ним, ми зрозуміємо і практичний приклад, даний вище. Причина їхньої повільної роботи однакова.
Загалом, із регекспом «все так», синтаксис цілком допустимий. Проблема у тому, як виконується пошук по ньому.
Подивимося, що відбувається при пошуку в рядку 123456789z :
Насамперед, двигун регекспів намагається знайти d+. Плюс + є жадібним за умовчанням, тому він вистачає всі цифри, які може:
Потім двигун намагається застосувати зірку навколо дужок (\d+)* , але більше цифр немає, так що зірочка не дає повторень.
Потім у шаблоні йде символ кінця рядка $, а тексті – символ z .
Оскільки відповідність не знайдено, то «жадібний» плюс + відступає однією символ (бэктрекинг).
Тепер \d+ - це всі цифри, за винятком останньої:
Після бектрекінгу \d+ містить все число, крім останньої цифри. Двигунзнову намагається знайти збіг, з нової позиції ( 9 ).
Зірочка (\d+)* тепер може бути застосована – вона дає число 9:
Двигун намагається знайти $, але це йому не вдається - на його шляху знову z:
Так як збігу немає, то пошуковий двигун відступає назад ще раз.
Тепер перше число \d+ міститиме 7 цифр, а залишок рядка 89 стає другим \d+ :
На жаль, все ще немає відповідності для $.
Пошуковий движок знову повинен відступити назад. При цьому останній жадібний квантифікатор відпускає символ. В даному випадку це означає, що коротшає другий \d+ до одного символу 8 і зірочка забирає наступний 9 .
…І знову невдача. Друге і третє відступили по-максимуму, так що скорочується знову перше число, до 123456 , а зірочка бере те, що залишилося:
Знову немає збігу. Процес повторюється, останній жадібний квантифікатор + відпускає один символ ( 9 ):
Виходить, що двигун регулярних виразів перебирає всі комбінації з 123456789 та їх підпослідовності. А таких комбінацій дуже багато.
На цьому місці розумний читач може вигукнути: «В усьому винен бектрекінг? Давайте увімкнемо лінивий режим – і не буде ніякого бектрекінгу!»
Що ж, замінимо \d+ на \d+? і подивимося (акуратно, може підвісити браузер):
Ліниві регулярні вирази роблять те саме, але у зворотному порядку.
Деякі двигуни регулярних виразів містять хитрі перевірки та кінцеві автомати, які дозволяють уникнути нескінченного перебору або кардинально прискорити його, але не всі двигуни і не завжди.
Повертаючись наприклад вище – при пошуку в рядку відбувається те саме.
Пошук успішно починається, вибирається якась комбінація з \s*\w+=\w+\s* , яка, оскільки в кінціні > , Виявляється не підходящою. Двигун чесно відступає, пробує іншу комбінацію - і таке інше.
Що робити?
Проблема – у надбагатоваріантному переборі.
Двигун регулярних виразів перебирає купу можливих варіантів дужок там, де не потрібно.
Наприклад, в регекспі (d+)*$ нам (людям) очевидно, що в (d+) відкочуватися не потрібно. Від того, що замість одного d+ у нас два незалежних d+, нічого не зміниться.
Якщо повернутися до більш реального прикладу, то сам алгоритм пошуку, який у нас в голові, передбачає, що ми «просто» шукаємо тег, а потім пари атрибут = значення (скільки вийде).
Жодного «відкату» тут не потрібно.
У сучасних регулярних висловлюваннях для вирішення цієї проблеми придумали «possessive» (наджадібні?
Тобто, вони навіть простіші, ніж «жадібні» – беруть максимальну кількість символів і все. Пошук продовжується далі. При розбіжності жодного повернення немає.
Це, з одного боку, зменшує кількість можливих результатів, але, з іншого боку, часом очевидно, що повернення (зменшення кількість повторень квантифікатора) результату не дасть. А тільки згаяє час, що якраз і доставляє проблеми. Саме такі ситуації і описані вище.
Є й інший засіб – «атомарні дужки», які забороняють перебір усередині дужок, по суті дозволяючи домагатися того ж, що й наджадібні квантифікатори,
Взяття максимальної кількості повторень a+ без відкату має такий вигляд: (?=(a+))\1 .