فهم التعقب التراجعي الكارثي في التعابير النمطية RegEx

قد تبدو بعض التعابير النمطية regular expressions بسيطةً لكن قد يستغرق تنفيذها وقتًا طويلًا، وقد يسبب توقف محرك JavaScript عن الاستجابة، وسيواجه المطورون عاجلًا أم آجلًا هذا السلوك، ومن أعراضه توقف استجابة محرك تعبير نمطي يعمل جيدًا في بعض الأحيان، عندما يبحث ضمن نص معين مستهلكًا موارد المعالج 100%، حيث سيقترح المتصفح في حالة مثل هذه إيقاف تنفيذ السكربت، وإعادة تحميل الصفحة، وليس جيدًا بالطبع أن يُوقف سكربت JavaScript يعمل في الواجهة الخلفية استجابة عملية من عمليات الخادم، فلا بد إذًا من إلقاء نظرة على ذلك.

مشكلة انتظار انتهاء التعبير النمطي

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

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

alert( regexp.test("A good string") ); // true ناجح
alert( regexp.test("Bad characters: $@#") ); // false فاشل

يبدو أنّ التعبير سيعمل والنتيجة صحيحة، لكنه في نصوص معينة سيستغرق وقتًا طويلًا حتى تتوقف استجابة محرك JavaScript، وتُستهلك موارد المعالج 100%.

قد لا تلاحظ شيئًا إن نفّذت المثال التالي، لأن محرك JavaScript سيتوقف عن الاستجابة، وسيتوقف المتصفح عن التجاوب مع الأحداث، وستتوقف واجهة المستخدم عن العمل (تتيح معظم المتصفحات ميزة التمرير فقط)، وسيقترح المتصفح بعد فترة إعادة تحميل الصفحة، فكن على حذر.

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

// سيأخذ بعض الوقت
alert( regexp.test(str) );

وعلينا القول -حتى نكون منصفين- بأن بعض محركات التعابير النمطية تتعامل مع هذا النوع من البحث بفعالية، فالمحرك "V8" وابتداءً من النسخة 8.8 قادر على ذلك، فلن تتوقف استجابة المتصفح 88 Chrome في حالات مثل هذه، بينما ستتوقف استجابة متصفح Firefox.

السؤال الذي طرح نفسه، ما المشكلة؟ لماذا تتوقف استجابة التعبير النمطي؟

لتوضيح ذلك دعونا نبسّط المثال السابق بإزالة الفراغات ?S\، وبالتالي سيصبح التعبير النمطي على الشكل $*(?w+\s\)^، ولتوضيح الأمر أكثر دعونا نستبدل الصنف d\ بالصنف w\، وستتوقف مع ذلك استجابة التعبير الجديد أيضًا، فمثلًا:

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

let str = "012345678901234567890123456789z";

// انتبه، سيأخذ بعض الوقت
alert( regexp.test(str) );

ما المشكلة في هذا التعبير النمطي؟

قد يلاحظ القارئ أنّ التعبير *(+d\) غريب بعض الشيء، فوجود المحدد الكمي * يبدو مبالغًا فيه، فإن أردنا عددًا يمكن استخدام d\، ومع ذلك يبدو التعبير الجديد المبسط عمليًا أكثر، لكن سبب بطئه أيضًا لم يتغير، لهذا علينا دراسته بالتفصيل للوقوف على المشكلة، فما الذي يحدث أثناء البحث عن النمط $*(+d\)^ ضمن النص 123456789z، واختُصر قليلًا للوضوح، ولماذا يستغرق الأمر وقتًا؟

إليك ما يفعله المحرك:

أولًا، يحاول المحرك بدايةً البحث عن محتوى الأقواس، وهي الأعداد +d\، وطالما أنّ + محدد كمي جشع greedy افتراضيًا فسيضم كل الأرقام في النص.

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

عند ضم الأرقام جميعها يعدُّ المحرك أن البحث عن +d\ قد أنجز، وأن النتيجة هي 123456789، ثم ينتقل بعد ذلك إلى تطبيق المحدد الكمي *، لكن الأرقام في النص قد استهلكت جميعها، فلن يقدم مرتكز البداية ^ أي شيء، ثم يبحث المحرك عن آخر محارف النمط $، ولن يجده لأنّ المحرف الباقي من النص هو z:

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

ثانيًا، وطالما أنّ التطابق غير موجود فسينقص المُكمِّم + عدد المحارف واحدًا ويعيد البحث، لذلك ستكون نتيجة +d\ كل الأرقام عدا الأخير 12345678:

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

ثالثًا، يحاول المحرك الآن البحث في الموقع التالي بعد 12345678، وعندها يمكن تطبيق المكمِّم *، وسيعطي النمط *(+d\) تطابقًا جديدًا وهو 9.

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

ثم يحاول المحرك من جديد إيجاد آخر محرف من النمط $ فلن يجده، بل سيجد المحرف الباقي من النص، وهو z:

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

رابعًا، لن يحصل المحرك على التطابق المطلوب؛ وسيستمر في العودة والتعقب مخفضًا عدد التكرارات وهذا ما يسمى بعملية التعقب التراجعي Backtracking أو التراجع والمطابقة ببساطة، وتجري عملية التعقب التراجعي عادةً بالشكل التالي: يقلل آخر محدد كمي جشع عدد التكرارات حتى يصل إلى الحد الأدنى، ثم يأتي دور المحدد الكمي الجشع الذي يسبقه في إنقاص عدد التكرارات وهكذا، إلى أن يتقصى المحرك كل الحالات الممكنة، وإليك بعض الأمثلة عن هذه الحالات:

العدد الأول مؤلف من 7 أرقام، ثم عدد برقمين:

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

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

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

العدد الأول من 6 أرقام، والثاني من ثلاثة:

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

العدد الأول من 6 أرقام، يليه عددان آخران:

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

ويوجد عدد كبير من الاحتمالات التي نفصل فيها سلسلةً من الأرقام 123456789 إلى أعداد، ولنكون أكثر دقة توجد ‎2<sup>n</sup>-1 طريقة، حيث n هو طول سلسلة الأرقام، ففي حالة 9 أرقام -كما في حالتنا- لدينا 511 احتمال، أما في حالة 20 رقمًا فلدينا 1048575 احتمال، وبالتالي سيسبب مرور المحرك بهذه الحالات التأخير.

العودة إلى الكلمات والنصوص

يحدث الأمر ذاته كما في مثالنا الأول، عندما بحثنا عن كلمات باستخدام النمط $*(?w+\s\)^ ضمن النص التالي:

An input that hangs!‎

والسبب طبعًا أن الكلمة +w\ قد تُمثَّل بعدد كبير من الحالات:

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

قد يكون عدم وجود التطابق واضحًا، لأن النص ينتهي بإشارة تعجب، لكن ما يتوقعه التعبير النمطي هو محرف كلمة w\ أو فراغ s\ في النهاية، وهذا ما لا يعرفه المحرك، إذ سيبحث عن كل الحالات التي يحتمل أن تطابق فيها النمط *(?w+\s\) كل محارف النص، بما في ذلك الحالات التي تضم الفراغ *(w+\s\) أو التي لا تضمها *(+w\)، لأن النمط ?s\ اختياري، وسيستغرق وقتًا طويلًا نظرًا لوجود عدد كبير من الحالات التي سيستكشفها المحرك، فما العمل؟ هل علينا تفعيل البحث الكسول lazy mode؟

لن يساعدنا ذلك لسوء الحظ، ستتوقف الاستجابة أيضًا إذا استبدلنا النمط ?+w\ بالنمط +w\، وسيتغير ترتيب الحالات التي سيبحث فيها المحرك فقط، وليس عددها.

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

ما هو الحل؟

توجد مقاربتان لحل المشكلة، الأولى تخفيض عدد الحالات الممكنة، فمثلًا لنجعل المساحة الفارغة إجباريةً، بجعل النمط بالشكل التالي $*w+\s)*\w\)^، أي سنبحث عن أي عدد من الكلمات التي يفصل بينها فراغ، عدا الكلمة الأخيرة فستكون اختيارية w\*، سينتهي البحث سواء وجدت أم لا، انظر إلى التعبير التالي المكافئ للسابق (يحصل على التطابقات نفسها) ويعمل جيدًا:

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

لماذا اختفت المشكلة؟ لأن الفراغ بين الكلمات أصبح إجباريًا، فلو حذفنا الفراغ في التعبير السابق فسيقود إلى عدد أكبر من حالات +w\ ضمن الكلمة ذاتها، إذ يمكن الحصول على الكلمة input من تكرارين +w\ بالشكل التالي:

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

لكن النمط الجديد مختلف، فالكلمة متبوعة بفراغ حتمًا *(w+\s\)، وبالتالي لن نحصل على الكلمة من خلال تكرارين للنمط w+\s\، وبهذا لن يهدر المزيد من الوقت في البحث عن كل الحالات الممكنة للحصول على كلمة.

منع التعقب التراجعي في التعابير النمطية

لن تساعدنا إعادة كتابة النمط دائمًا، إذ كانت العملية سهلةً وواضحةً في المثال السابق، لكنها عادةً ليست كذلك، كما ستقود إعادة كتابة النمط إلى أنماط أكثر تعقيدًا، وهذا أمر سيء، فالتعابير النمطية معقدة بطبيعتها، لحسن الحظ توجد مقاربة بديلة تقتضي منع التعقب التراجعي backtracking للمحدد الكمي، فأصل المشكلة هو تجربة المحرًك للكثير من الحالات الخاطئة -من وجهة نظرنا طبعًا-، فمن الواضح أنّ تعقب + في النمط $*(+d\) سيسبب مشكلةً، ولن يتغير شيء إن بدّلنا النمط +d+\d\ بالنمط +d\:

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

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

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

تدعم محركات التعابير النمطية الحديثة المحددات الكمية الاستحواذية possessive quantifiers عن طريق إضافة الإشارة + بعد المحدد الكمي، أي نضع ++d\ بدلًا من +d\، وذلك لمنعه من الوقوع في فخ التعقب التراجعي، فالمحددات الكمية الاستحواذية أبسط من النظامية، حيث تطابق ما تستطيع من المحارف دون الوقوع في التعقب التراجعي، وسيكون البحث آنذاك أبسط.

كما يوجد ما يُسمى "المجموعات الذرية الملتقطة" atomic capturing groups، وهو وسيلة لمنع التعقب التراجعي ضمن الأقواس، والخبر السيئ هو أنها غير مدعومة في JavaScript، لكن يمكن تقليدها باستخدام شرط التحقق مما يلي المطابقة lookahead transform.

البحث عن الخلاص

لقد وصلنا إلى موضوع متقدم فعلًا، إذ نريد منع المحددات الكمية -مثل +- من التعقب التراجعي، لأن تعقب بعض الأمور غير منطقي على الإطلاق.

إنّ النمط الذي يأخذ أكبر عدد ممكن من تكرارات w\ دون تعقب تراجعي هو 1$(+w$=?)، وبالطبع يمكن اختيار أي نمط بدل w\، وقد يبدو النمط غريبًا، لكنه في الواقع تحويل بسيط، لنصفه:

سيبحث نمط البحث قُدُمًا =? عن أطول كلمة +w\ ابتداءً من الموقع الحالي.
لن يتذكر المحرك محتوى ما بين القوسين المسبوق بالمحارف =?، لذلك وضعنا +w\ ضمن أقواس، ثم سيتذكر المحرك محتوى القوسين التاليين.
ثم نشير إلى الأقواس الخارجية بالرقم 1.

سيتقدم البحث إلى الأمام وعند وجود كلمة +w\ فسيحددها بالرقم 1\، وبكذا سنكون قد صممنا محددًا كميًا استحواذيًا من المحدد الكمي +، حيث يلتقط الكلمة +w\ كاملةً فقط، وليس جزءًا منها، فيمكن مثلًا الحصول على الكلمة Java من الكلمة JavaScript، وترك الكلمة Script لتتطابق مع بقية النمط، وإليك موازنةً بين نمطين:

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

في الحالة الأولى: سنحصل على الكلمة كاملةً، لكن المحدد الكمي سيتعقب بقية النمط متراجعًا محرفًا محرفًا، محاولًا إيجاد بقية النمط، ثم سينجح أخيرًا، عندما يتطابق النمط +w\ الكلمة Java.
في الحالة الثانية: سيجري البحث قُدمًا وسيجد الكلمة JavaScript كاملةً، وسيحددها بالرقم 1، وبالتالي لا طريقة بعد ذلك لإيجاد الكلمة Script.

يمكن استخدام تعابير نمطية أكثر تعقيدًا من w\ ضمن 1$(+w$=?) عندما نريد منع التعقب التراجعي للمحدد الكمي +.

لنكتب مثالنا الأول باستخدام التحقق مما يلي التطابق لمنع التعقب التراجعي:

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, يعمل وبسرعة

وضعنا 2\ بدلًا من الرقم 1\ لوجود أقواس خارجية إضافية، كما يمكننا تسمية الأقواس أيضًا (+<word>\w>?).

//  ?<word>وتُسمى الأقواس كالتالي, \k<word>يشار إلى الأقواس كالتالي 
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