Halokatli orqaga qaytish (Catastrophic backtracking)

Ba’zi muntazam ifodalar oddiy ko’rinsa ham, juda uzoq vaqt ishlaydi va hatto JavaScript dvigatelini “osib qo’yadi”.

Ertami-kechmi deyarli barcha dasturchilarga bunday holatlar duch keladi. Odatiy alomat – muntazam ifoda ba’zan yaxshi ishlaydi, lekin muayyan satrlar uchun “osilib qoladi”, CPU ning 100% ni iste’mol qiladi.

Bunday holatlarda veb-brauzer skriptni o’chirib, sahifani qayta yuklashni taklif qiladi. Bu albatta yaxshi narsa emas.

Server tomonidagi JavaScript uchun bunday regexp server jarayonini osib qo’yishi mumkin, bu yanada yomonroq. Shuning uchun biz buni albatta ko’rib chiqishimiz kerak.

Misol

Aytaylik, bizda satr bor va biz uni so’zlardan \w+ iborat ekanligini, har biridan keyin ixtiyoriy bo’sh joy \s? bilan tekshirmoqchimiz.

Regexp yaratishning aniq usuli so’zni ixtiyoriy bo’sh joy bilan \w+\s? olib, keyin uni * bilan takrorlash bo’ladi.

Bu bizni ^(\w+\s?)*$ regexpiga olib boradi, u satr boshida ^ boshlanib, oxirida $ tugaydigan nol yoki ko’proq bunday so’zlarni belgilaydi.

Amalda:

let regexp = /^(\w+\s?)*$/;

alert( regexp.test("A good string") ); // true
alert( regexp.test("Bad characters: $@#") ); // false

Regexp ishlaganga o’xshaydi. Natija to’g’ri. Biroq, ba’zi satrlarda u juda ko’p vaqt oladi. Shunchalik uzoqki, JavaScript dvigateli 100% CPU iste’moli bilan “osilib qoladi”.

Agar quyidagi misolni ishga tushirsangiz, ehtimol hech narsa ko’rmaysiz, chunki JavaScript shunchaki “osilib qoladi”. Veb-brauzer voqealarga javob berishni to’xtatadi, UI ishlamay qoladi (ko’pchilik brauzerlar faqat aylantirishga ruxsat beradi). Bir muncha vaqt o’tgach, sahifani qayta yuklashni taklif qiladi. Shuning uchun ehtiyot bo’ling:

let regexp = /^(\w+\s?)*$/;
let str = "An input string that takes a long time or even makes this regexp hang!";

// juda uzoq vaqt oladi
alert( regexp.test(str) );

Adolatli bo’lish uchun, ba’zi muntazam ifoda dvigatelari bunday qidiruvni samarali bajarishi mumkinligini ta’kidlaymiz, masalan, V8 dvigateli 8.8 versiyasidan boshlab buni qila oladi (shuning uchun Google Chrome 88 bu yerda osilib qolmaydi), Firefox brauzer esa osilib qoladi.

Soddalashtirilgan misol

Nima gap? Nima uchun muntazam ifoda osilib qolyapti?

Buni tushunish uchun, misolni soddalashtiraylik: bo’sh joylarni \s? olib tashlaylik. Keyin u ^(\w+)*$ bo’ladi.

Va ishlarni yanada aniqroq qilish uchun, \w ni \d bilan almashtiring. Natijada hosil bo’lgan muntazam ifoda hali ham osilib qoladi, masalan:

let regexp = /^(\d+)*$/;

let str = "012345678901234567890123456789z";

// juda uzoq vaqt oladi (ehtiyot bo'ling!)
alert( regexp.test(str) );

Xo’sh, regexpda nima noto’g’ri?

Birinchidan, (\d+)* regexp biroz g’alati ekanligini payqash mumkin. * kvantifikatori ortiqcha ko’rinadi. Agar biz raqam istasak, \d+ dan foydalanishimiz mumkin.

Darhaqiqat, regexp sun’iy; biz uni oldingi misolni soddalashtirib oldik. Ammo uning sekin bo’lish sababi bir xil. Keling, buni tushunamiz, shunda oldingi misol ham aniq bo’ladi.

123456789z satrida ^(\d+)*$ qidirish vaqtida nima sodir bo’ladi (aniqlik uchun biroz qisqartirilgan, oxirida z raqam bo’lmagan belgini e’tibor bering, bu muhim), nima uchun bu shunchalik uzoq vaqt oladi?

Mana regexp dvigateli nima qiladi:

1. Birinchidan, regexp dvigateli qavslar ichidagi tarkibni topishga harakat qiladi: \d+ raqami. + standart ravishda ochko’z, shuning uchun u barcha raqamlarni iste’mol qiladi:

   \d+.......
   (123456789)z

   Barcha raqamlar iste’mol qilingandan so’ng, \d+ topilgan deb hisoblanadi (123456789 sifatida).

   Keyin yulduzcha kvantifikatori (\d+)* qo’llaniladi. Ammo matnda boshqa raqamlar yo’q, shuning uchun yulduzcha hech narsa bermaydi.

   Naqshdagi keyingi belgi satr oxiri $. Ammo matnda uning o’rniga z bor, shuning uchun mos kelish yo’q:

              X
   \d+........$
   (123456789)z

2. Mos kelish yo’q bo’lgani uchun, ochko’z kvantifikator + takrorlashlar sonini kamaytiradi, bir belgini orqaga qaytaradi.

   Endi \d+ oxirgisidan tashqari barcha raqamlarni oladi (12345678):

   \d+.......
   (12345678)9z

3. Keyin dvigatel keyingi pozitsiyadan (12345678 dan keyin) qidiruvni davom ettirishga harakat qiladi.

   Yulduzcha (\d+)* qo’llanishi mumkin – u \d+ ning yana bir mosligini beradi, 9 raqami:

   \d+.......\d+
   (12345678)(9)z

   Dvigatel $ ni yana moslashtirishga harakat qiladi, ammo muvaffaqiyatsiz bo’ladi, chunki u o’rniga z ni uchratadi:

                X
   \d+.......\d+
   (12345678)(9)z

4. Mos kelish yo’q, shuning uchun dvigatel orqaga qaytishni davom ettiradi, takrorlashlar sonini kamaytiradi. Orqaga qaytish odatda shunday ishlaydi: oxirgi ochko’z kvantifikator minimal darajaga yetguncha takrorlashlar sonini kamaytiradi. Keyin oldingi ochko’z kvantifikator kamayadi va hokazo.

   Barcha mumkin bo’lgan kombinatsiyalar sinab ko’riladi. Mana ularning misollari.

   Birinchi raqam \d+ da 7 ta raqam bor, keyin 2 ta raqamli raqam:

                X
   \d+......\d+
   (1234567)(89)z

   Birinchi raqamda 7 ta raqam bor, keyin har birida 1 ta raqamdan ikkita raqam:

                  X
   \d+......\d+\d+
   (1234567)(8)(9)z

   Birinchi raqamda 6 ta raqam bor, keyin 3 ta raqamli raqam:

                X
   \d+.......\d+
   (123456)(789)z

   Birinchi raqamda 6 ta raqam bor, keyin 2 ta raqam:

                  X
   \d+.....\d+ \d+
   (123456)(78)(9)z

   …Va hokazo.

123456789 raqamlar ketma-ketligini raqamlarga bo’lishning ko’p usullari bor. Aniq qilib aytganda, 2n-1 ta yo’l bor, bu yerda n ketma-ketlik uzunligi.

• 123456789 uchun bizda n=9, bu 511 ta kombinatsiya beradi.
• n=20 bilan uzunroq ketma-ketlik uchun taxminan bir million (1048575) kombinatsiya bor.
• n=30 uchun – ming marta ko’p (1073741823 kombinatsiya).

Ularning har birini sinab ko’rish qidiruvning uzoq vaqt olishining aniq sababidir.

So’zlar va satrlar uchun qaytish

Birinchi misolimizda ham xuddi shunday narsa sodir bo’ladi, An input that hangs! satrida ^(\w+\s?)*$ naqsh bilan so’zlarni qidirganimizda.

Sababi shundaki, so’z bitta \w+ yoki ko’p qismlarda ifodalanishi mumkin:

(input)
(inpu)(t)
(inp)(u)(t)
(in)(p)(ut)
...

Inson uchun mos kelish bo’lmasligi aniq, chunki satr undov belgisi ! bilan tugaydi, ammo muntazam ifoda oxirida so’z belgisi \w yoki bo’sh joy \s ni kutadi. Ammo dvigatel buni bilmaydi.

U regexp (\w+\s?)* satrni qanday “iste’mol qilishi” mumkinligining barcha kombinatsiyalarini sinab ko’radi, jumladan bo’sh joylar bilan (\w+\s)* va ularsiz (\w+)* variantlarni (chunki bo’sh joylar \s? ixtiyoriy). Bunday kombinatsiyalar ko’p bo’lgani uchun (biz buni raqamlar bilan ko’rdik), qidiruv ko’p vaqt oladi.

Nima qilish kerak?

Dangasa rejimni yoqish kerakmi?

Afsuski, bu yordam bermaydi: agar biz \w+ ni \w+? bilan almashtirsa, regexp hali ham osilib qoladi. Kombinatsiyalar tartibi o’zgaradi, ammo ularning umumiy soni emas.

Ba’zi muntazam ifoda dvigatellari barcha kombinatsiyalarni ko’rib chiqishdan qochish yoki uni ancha tezlashtirish imkonini beradigan murakkab testlar va chekli avtomatlarga ega, ammo ko’pchilik dvigatellar yo’q va bu har doim ham yordam bermaydi.

Qanday tuzatish kerak?

Muammoni hal qilishning ikkita asosiy usuli bor.

Birinchisi mumkin bo’lgan kombinatsiyalar sonini kamaytirish.

Bo’sh joyni majburiy qilib, muntazam ifodani ^(\w+\s)*\w*$ deb qayta yozaylik – biz bo’sh joy bilan so’zlangan istalgan miqdordagi so’zlarni (\w+\s)*, keyin (ixtiyoriy) oxirgi so’zni \w* qidiramiz.

Bu regexp avvalgisiga teng (bir xil mosliklar) va yaxshi ishlaydi:

let regexp = /^(\w+\s)*\w*$/;
let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

Nega muammo yo’qoldi?

Buning sababi endi bo’sh joy majburiy.

Oldingi regexp, agar biz bo’sh joyni chiqarib tashlasak, (\w+)* bo’lib, bitta so’z ichida \w+ ning ko’p kombinatsiyalariga olib keladi.

Shunday qilib, input \w+ ning ikki takrorlanishi sifatida moslashtirishi mumkin, masalan:

\w+  \w+
(inp)(ut)

Yangi naqsh boshqacha: (\w+\s)* bo’sh joy bilan so’zlangan so’zlarning takrorlanishini belgilaydi! input satri \w+\s ning ikki takrorlanishi sifatida moslashtirila olmaydi, chunki bo’sh joy majburiy.

Ko’p (aslida ko’pchilik) kombinatsiyalarni sinab ko’rish uchun zarur bo’lgan vaqt endi tejaldi.

Orqaga qaytishni oldini olish

Biroq regexp ni qayta yozish har doim ham qulay emas. Yuqoridagi misolda bu oson edi, ammo buni qanday qilish har doim ham aniq emas.

Bundan tashqari, qayta yozilgan regexp odatda murakkabroq va bu yaxshi emas. Regexplar qo’shimcha harakatlarsiz ham etarlicha murakkab.

Yaxshiyamki, muqobil yondashuv bor. Biz kvantifikator uchun orqaga qaytishni taqiqlashimiz mumkin.

Muammoning ildizi shundaki, regexp dvigateli inson uchun aniq noto’g’ri bo’lgan ko’p kombinatsiyalarni sinab ko’radi.

Masalan, (\d+)*$ regexpida inson uchun + orqaga qaytmasligi kerakligi aniq. Agar biz bitta \d+ ni ikkita alohida \d+\d+ bilan almashtirsa, hech narsa o’zgarmaydi:

\d+........
(123456789)!

\d+...\d+....
(1234)(56789)!

Va asl misolda ^(\w+\s?)*$ da biz \w+ da orqaga qaytishni taqiqlashni xohlashimiz mumkin. Ya’ni: \w+ maksimal mumkin bo’lgan uzunlik bilan butun so’zga mos kelishi kerak. \w+ da takrorlashlar sonini kamaytirish yoki uni ikkita so’zga \w+\w+ bo’lish va hokazolar kerak emas.

Zamonaviy muntazam ifoda dvigatellari buning uchun egalik kvantifikatorlarini qo’llab-quvvatlaydi. Oddiy kvantifikatorlar, agar biz ulardan keyin + qo’shsak, egalik bo’ladi. Ya’ni, biz + ni orqaga qaytishdan to’xtatish uchun \d+ o’rniga \d++ dan foydalanamiz.

Egalik kvantifikatorlari aslida “oddiy” lardan sodda. Ular shunchaki iloji boricha ko’p moslashtiradi, hech qanday orqaga qaytishsiz. Orqaga qaytishsiz qidiruv jarayoni soddaroq.

“Atom tutuvchi guruhlar” ham bor – qavslar ichida orqaga qaytishni o’chirish usuli.

…Ammo yomon xabar shundaki, afsuski, JavaScript da ular qo’llab-quvvatlanmaydi.

Biroq biz ularni “oldinga qarash o’zgarishi” yordamida taqlid qilishimiz mumkin.

Oldinga qarash yordamga keladi!

Shunday qilib, biz haqiqiy ilg’or mavzularga keldik. Biz + kabi kvantifikatorning orqaga qaytmasligini istayiz, chunki ba’zan orqaga qaytish ma’noga ega emas.

Orqaga qaytishsiz \w ning iloji boricha ko’p takrorlanishini olish naqshi: (?=(\w+))\1. Albatta, \w o’rniga boshqa naqshni olishimiz mumkin.

Bu g’alati tuyulishi mumkin, ammo bu aslida juda oddiy o’zgartirish.

Keling, uni deshipr qilaylik:

• Oldinga qarash ?= joriy pozitsiyadan boshlanadigan eng uzun so’z \w+ ni qidiradi.
• ?=... bilan qavslar tarkibi dvigatel tomonidan eslab qolinmaydi, shuning uchun \w+ ni qavslarga o’rang. Keyin dvigatel ularning tarkibini eslab qoladi
• …Va naqshda uni \1 sifatida murojaat qilishga imkon beradi.

Ya’ni: biz oldinga qaraymiz – va agar so’z \w+ bo’lsa, uni \1 sifatida moslashtiring.

Nega? Buning sababi shundaki, oldinga qarash so’z \w+ ni butunligicha topadi va biz uni naqshga \1 bilan qo’lamiz. Shunday qilib, biz mohiyatan egalik plus + kvantifikatorini amalga oshirdik. U faqat butun so’z \w+ ni qo’lga oladi, uning bir qismini emas.

Masalan, JavaScript so’zida u nafaqat Java ni moslashishi mumkin, balki naqshning qolgan qismiga mos kelish uchun Script ni tashlab ketishi mumkin.

Mana ikki naqshning taqqoslashuvi:

alert( "JavaScript".match(/\w+Script/)); // JavaScript
alert( "JavaScript".match(/(?=(\w+))\1Script/)); // null

1. Birinchi variantda \w+ avval butun JavaScript so’zini qo’lga oladi, ammo keyin + naqshning qolgan qismiga mos kelish uchun belgi bo’yicha orqaga qaytadi, oxir-oqibat muvaffaqiyat qozonadi (\w+ Java ga mos kelganda).
2. Ikkinchi variantda (?=(\w+)) oldinga qaradi va JavaScript so’zini topadi, bu \1 tomonidan naqshga butunligicha kiritiladi, shuning uchun undan keyin Script ni topishning yo’li qolmaydi.

Biz \w o’rniga (?=(\w+))\1 ga murakkabroq muntazam ifoda qo’yishimiz mumkin, agar undan keyin + uchun orqaga qaytishni taqiqlashimiz kerak bo’lsa.

Keling, orqaga qaytishni oldini olish uchun oldinga qarishdan foydalanib birinchi misolni qayta yozaylik:

let regexp = /^((?=(\w+))\2\s?)*$/;

alert( regexp.test("A good string") ); // true

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false, ishlaydi va tez!

Bu yerda \2 \1 o’rniga ishlatiladi, chunki qo’shimcha tashqi qavslar bor. Raqamlar bilan aralashmaslik uchun qavslarga nom berishimiz mumkin, masalan (?<word>\w+).

// qavslar ?<word> deb nomlangan, \k<word> sifatida murojaat qilingan
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

alert( regexp.test("A correct string") ); // true

Ushbu maqolada tasvirlangan muammo “halokatli orqaga qaytish” deb ataladi.

Biz uni hal qilishning ikkita usulini ko’rib chiqdik:

• Mumkin bo’lgan kombinatsiyalar sonini kamaytirish uchun regexp ni qayta yozish.
• Orqaga qaytishni oldini olish.