٣٠ مايو ٢٠٢٠

التراجع الكارثي

تبدو بعض التعبيرات العادية بسيطة ، ولكن يمكنها تنفيذ كل وقت طويل ، وحتى “تعليق” محرك جافا سكريبت.

عاجلاً أم آجلاً ، يواجه معظم المطورين أحيانًا مثل هذا السلوك ، لأنه من السهل جدًا إنشاء مثل هذا regexp.

العَرَض النموذجي – يعمل التعبير العادي بشكل جيد في بعض الأحيان ، ولكن بالنسبة لبعض السلاسل “يتوقف” ويستهلك 100٪ من وحدة المعالجة المركزية.

في مثل هذه الحالة ، يقترح متصفح الويب إنهاء البرنامج النصي وإعادة تحميل الصفحة. ليس بالشيء الجيد بالتأكيد

بالنسبة لجافا سكريبت من جانب الخادم ، قد تصبح ثغرة أمنية في حالة معالجة التعبيرات العادية لبيانات المستخدم.

مثال

لنفترض أن لدينا سلسلة ، ونود أن نتحقق مما إذا كانت تتكون من الكلمات \ w + مع مساحة اختيارية \ s؟ بعد كل منها.

سنستخدم نمط regexp : ^ (\ w + \ s؟) * $ ، فهو يحدد 0 أو أكثر من هذه الكلمات.

في العمل:

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

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

يبدو أنه يعمل. والنتيجة صحيحة. على الرغم من ذلك ، على سلاسل معينة يستغرق الكثير من الوقت. طالما أن محرك جافا سكريبت “توقف” مع استهلاك CPU بنسبة 100٪.

إذا قمت بتشغيل المثال أدناه ، فربما لن ترى أي شيء ، لأن JavaScript سوف “يتعطل” فقط. سيتوقف متصفح الويب عن التفاعل مع الأحداث ، وستتوقف واجهة المستخدم عن العمل. بعد مرور بعض الوقت سيقترح إعادة تحميل الصفحة. لذا كن حذرًا مع هذا:

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

// will take a very long time
alert( regexp.test(str) );

يمكن لبعض محركات التعبير العادي معالجة مثل هذا البحث ، ولكن معظمها لا يستطيع ذلك.

مثال مبسط

ما الأمر؟ لماذا “تعليق” التعبير العادي؟

لفهم ذلك ، دعنا نبسط المثال: إزالة المسافات \ s؟. ثم يصبح النمط: ^ (\ w +) * $.

ولجعل الأمور أكثر وضوحًا ، دعنا نستبدل \ w بـ \ d. مازال التعبير العادي الناتج معلقًا ، على سبيل المثال:

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

let str = "012345678901234567890123456789!";

// will take a very long time
alert( regexp.test(str) );

إذن ما هو الخطأ في regexp؟

أولاً ، قد يلاحظ المرء أن نمط regexp : (\ d +) * غريب بعض الشيء. يبدو "نمط محدد الكمية: *غريبًا. إذا أردنا رقمًا ، فيمكننا استخدامpattern: \ d +`.

في الواقع ، إن التعبير العادي مصطنع. لكن السبب في أنها بطيئة هو نفسه الذي رأيناه أعلاه. لذلك دعونا نفهمها ، ومن ثم سيصبح المثال السابق واضحًا.

ماذا يحدث أثناء البحث عن النمط: ^ (\ d +) * $ في السطر الموضوع: 123456789! (اختصارًا قليلاً للوضوح) ، لماذا يستغرق وقتًا طويلاً؟

  1. أولاً ، يحاول محرك regexp إيجاد رقم النمط: \ d +. نمط `plus +: 'جشع افتراضيًا ، لذلك يستهلك جميع الأرقام:

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

ثم يحاول تطبيق مقياس كمية النجم ، ولكن لا يوجد المزيد من الأرقام ، لذا فهو لا يعطي أي شيء.

التالي في النمط هو “نهاية السلسلة”: $ ، ولكن في النص لدينا الموضوع:! `، لذلك لا يوجد تطابق:

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

  1. نظرًا لعدم وجود تطابق ، فإن نمط المحدد الكمي الجشع : + يقلل من عدد التكرار ، ويعيد حرفًا واحدًا إلى الوراء.

الآن النمط: \ d + يأخذ جميع الأرقام باستثناء آخر:     \ d + .......     (12345678) 9! 3. ثم يحاول المحرك متابعة البحث من الموضع الجديد (9).

يمكن تطبيق النجمة نمط: (\ d +) * – تعطي الرقم تطابق: 9:

``

\ d + ……. \ d +     (12345678) (9)!     ``

يحاول المحرك مطابقة النمط: $ مرة أخرى ، لكنه يفشل ، لأنه يلبي الموضوع:!:

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

  1. لا يوجد تطابق ، لذلك سيستمر المحرك في التراجع ، مما يقلل من عدد التكرار. يعمل التراجع بشكل عام على هذا النحو: يقلل محدد الكمية الجشع من عدد التكرار حتى يتمكن من ذلك. ثم ينقص محدد الكمية الجشع السابق ، وهكذا.

تتم محاولة جميع التركيبات الممكنة. هنا أمثلةهم.

يتكون الرقم الأول من النمط: \ d + من 7 أرقام ، ثم عدد من رقمين:

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

يتكون الرقم الأول من 7 أرقام ، ثم رقمان من رقم واحد لكل منهما:

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

يتكون الرقم الأول من 6 أرقام ، ثم عدد 3 أرقام:

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

يتكون الرقم الأول من 6 أرقام ، ثم رقمان:

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

…وما إلى ذلك وهلم جرا.

هناك عدة طرق لتقسيم مجموعة من الأرقام 123456789 إلى أرقام. على وجه الدقة ، هناك 2 n ‑1 ، حيث n هو طول المجموعة.

بالنسبة لـ n = 20 ، هناك حوالي مليون تركيبة ، لـn = 30 – ألف مرة أكثر. تجربة كل واحد منهم هو بالضبط السبب في أن البحث يستغرق وقتًا طويلاً.

ماذا أفعل؟

هل يجب تشغيل الوضع الكسول؟

لسوء الحظ ، لن يساعد ذلك: إذا استبدلنا \ d + بـ \ d +؟ ، فسيظل regexp معلقًا. سيتغير ترتيب المجموعات ، ولكن ليس العدد الإجمالي لها.

بعض محركات التعبير العادي لديها اختبارات صعبة وأتمتة محدودة تسمح بتجنب المرور عبر جميع التركيبات أو تجعلها أسرع بكثير ، ولكن ليس جميع المحركات ، وليس في جميع الحالات.

الرجوع إلى الكلمات والسلاسل

يحدث الشيء نفسه في مثالنا الأول ، عندما ننظر إلى الكلمات حسب النمط ^ (\ w + \ s؟) * $ في السلسلة مدخل معلق!.

والسبب هو أن الكلمة يمكن تمثيلها كنمط واحد: \ w + أو العديد:

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

بالنسبة للإنسان ، من الواضح أنه قد لا يكون هناك تطابق ، لأن السلسلة تنتهي بعلامة تعجب ! ، لكن التعبير العادي يتوقع حرفًا كلمة نمط: \ w أو نمطمسافة: \ s في النهاية. لكن المحرك لا يعرف ذلك.

يحاول جميع التركيبات كيف أن نمط regexp : (\ w + \ s؟) * يمكن “استهلاك” السلسلة ، بما في ذلك المتغيرات ذات نمط المسافات: (\ w + \ s) * وبدونها نمط: (\ w +) *(لأن المساحات \ s؟اختيارية). نظرًا لوجود العديد من هذه المجموعات ، فإن البحث يستغرق الكثير من الوقت.

كيفية الإصلاح؟

هناك طريقتان رئيسيتان لإصلاح المشكلة.

الأول هو تقليل عدد التركيبات الممكنة.

دعنا نعيد كتابة التعبير العادي كـ ^ (\ w + \ s) * \ w * – سنبحث عن أي عدد من الكلمات متبوعًا بنمط المسافة: (\ w + \ s) * ، ثم ( اختياريًا) كلمة \ w *.

تعادل regexp هذه السابقة (تتطابق مع نفسها) وتعمل بشكل جيد:

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

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

لماذا اختفت المشكلة؟

الآن النجمة * يذهب بعد \ w + \ s بدلاً من \ w + \ s؟. أصبح من المستحيل تمثيل كلمة واحدة من السلسلة مع نمط متعدد متتالي: \ w +. يتم الآن توفير الوقت اللازم لتجربة هذه المجموعات.

على سبيل المثال ، النقش السابق (\ w + \ s؟) * يمكن أن يتطابق مع الكلمة string على هيئةpattern: \ w +`:

\w+\w+
string

النمط السابق ، بسبب `` النمط: \ sالاختياري للمتغيرات المسموح بهاالنمط: \ w +،النمط: \ w + \ s، النمط: \ w + \ w + `وما إلى ذلك.

مع النقش المُعاد كتابته النمط: (\ w + \ s) * ، هذا مستحيل: قد يكون هناك نمط: \ w + \ s أوالنمط: \ w + \ s \ w + \ s ، ولكن ليس النمط: \ w + \ w +. لذلك تم تقليل عدد المجموعات بشكل كبير.

منع التراجع

ليس من المناسب دائمًا إعادة كتابة regexp. وليس من الواضح دائمًا كيفية القيام بذلك.

النهج البديل هو منع التراجع عن المقياس الكمي.

يحاول محرك التعبيرات العادية العديد من المجموعات التي من الواضح أنها خاطئة للإنسان.

على سبيل المثال في نمط regexp : (\ d +) * $ من الواضح للإنسان ، أن النمط: + لا يجب التراجع عنه. إذا استبدلنا نمطًا `` واحدًا: \ d + بنمطين منفصلين: \ d + \ d + `، فلن يتغير شيء:

`` \d+……… (123456789)!

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

وفي المثال الأصلي `pattern: ^ (\ w + \ s؟) * $` قد نرغب في منع التراجع في `pattern: \ w +`. هذا هو: `النمط: \ w +` يجب أن يتطابق مع كلمة كاملة ، مع أقصى طول ممكن. ليست هناك حاجة لخفض عدد التكرارات في `النمط: \ w +` ، حاول تقسيمه إلى كلمتين `نمط: \ w + \ w +` وما إلى ذلك.

تدعم محركات التعبير العادية الحديثة محددات الكمية الملكية لذلك. إنهم مثل الجشعين ، لكنهم لا يتراجعون (لذلك هم في الواقع أبسط من المحددات الكمية العادية).

هناك أيضًا ما يسمى "مجموعات الالتقاط الذري" - وهي طريقة لتعطيل التراجع داخل الأقواس.

لسوء الحظ ، في JavaScript غير مدعومة. ولكن هناك طريقة أخرى.

### انظروا إلى الإنقاذ!

يمكننا منع التراجع باستخدام lookahead.

النمط الذي يجب أن يتكرر من خلال "النمط: \ w" بقدر الإمكان بدون التراجع هو: "النمط: (؟ = (\ w +)) \ 1`.

دعونا نفكها:
- Lookahead `pattern:؟ =` يتطلع لأطول كلمة `pattern: \ w +` بدءًا من الموضع الحالي.
- محتويات الأقواس مع `النمط:؟ = ...` لا يحفظها المحرك ، لذا قم بتغليف `النمط: \ w +` بين قوسين. ثم يقوم المحرك بحفظ محتوياتها
- ... واسمح لنا بالإشارة إليها في النمط باسم "pattern: \ 1".

هذا هو: نحن نتطلع إلى المستقبل - وإذا كانت هناك كلمة `pattern: \ w +` ، فقم بمطابقتها كـ `pattern: \ 1`.

لماذا ا؟ ذلك لأن lookahead يعثر على كلمة `pattern: \ w +` ككل ونلتقطها في النمط بـ `pattern: \ 1`. لذا قمنا بتطبيق نمط امتلاك زائد `نمط: +` كمّي. يلتقط فقط الكلمة `نمط: \ w +` ، وليس جزءًا منها.

على سبيل المثال ، في كلمة `subject: JavaScript` ، قد لا تتطابق فقط مع` match: Java` ، ولكن تترك `match: Script` لتتطابق مع باقي النمط.

إليك مقارنة بين نمطين:

```js run
alert( "JavaScript".match(/\w+Script/)); // JavaScript
alert( "JavaScript".match(/(?=(\w+))\1Script/)); // null
  1. في المتغير الأول النمط: \ w + يلتقط أولاً الكلمة الموضوع: جافا سكريبت ثمالنمط: +يتراجع حرفًا بحرف ، في محاولة لمطابقة بقية النمط ، حتى ينجح في النهاية (عندما \ w + يتطابق مع Java).
  2. في المتغير الثاني النمط: (؟ = (\ w +)) يتطلع إلى الأمام ويجد كلمة الموضوع: JavaScript ، المضمنة في النمط ككل بواسطةالنمط: \ 1 ، لذلك لا يزال هناك لا توجد طريقة للعثور على “الموضوع: البرنامج النصي” بعده.

يمكننا وضع تعبير عادي أكثر تعقيدًا في النمط: (؟ = (\ w +)) \ 1 بدلاً منالنمط: \ w ، عندما نحتاج إلى منع التراجع عن النمط: + بعده.

برجاء الملاحظة:

هناك المزيد حول العلاقة بين محددات الكمية التملكية و lookahead في المقالات [Regex: Emulate Atomic Grouping (and Possessive Quantifiers) with LookAhead] (http://instanceof.me/post/52245507631/regex-emulate-atomic-grouping-with-lookahead ) و [محاكاة المجموعات الذرية] (http://blog.stevenlevithan.com/archives/mimic-atomic-groups). ``

دعونا نعيد كتابة المثال الأول باستخدام lookahead لمنع التراجع:

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 to hang!";

alert( regexp.test(str) ); // false, works and fast!

هنا يُستخدم “النمط: \ 2” بدلاً من “النمط: \ 1” ، نظرًا لوجود أقواس خارجية إضافية. لتجنب العبث بالأرقام ، يمكننا تسمية الأقواس ، على سبيل المثال نمط :(؟ <word> \ w +).

// parentheses are named ?<word>, referenced as \k<word>
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

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

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

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

تسمى المشكلة الموضحة في هذه المقالة “التراجع الكارثي”.

تناولنا طريقتين لكيفية حلها:

  • أعد كتابة regexp لخفض عدد المجموعات الممكنة.
  • منع التراجع.
خريطة الدورة التعليمية

التعليقات

إقرأ هذا قبل أن تضع تعليقًا…
  • إذا كان لديك اقتراحات أو تريد تحسينًا - من فضلك من فضلك إفتح موضوعًا فى جيتهاب أو شارك بنفسك بدلًا من التعليقات.
  • إذا لم تستطع أن تفهم شيئّا فى المقال - وضّح ماهو.
  • إذا كنت تريد عرض كود استخدم عنصر <code> ، وللكثير من السطور استخدم <pre>، ولأكثر من 10 سطور استخدم (plnkr, JSBin, codepen…)