التعابير النمطية (regular expressions) من الأدوات التي نستعملها دون أن نسأل كيف تعمل. ثم يأتي يوم يلتقي فيه نمط مثل (a+)+$ بمُدخل طويل، فتتجمّد خدمة كاملة. لهذا العطل اسم: catastrophic backtracking (التراجع الكارثي)، وهو ليس قانونًا من قوانين الطبيعة. مصدره طريقة واحدة لتنفيذ الـ regex. وهناك طريقة أخرى، أقدم ومبنية على الآليات (automata)، تعمل في زمن خطي بالنسبة للمُدخل مهما كان النمط.
شرح Russ Cox هذه الطريقة في سلسلة مقالات معروفة. regex-engine هو تنفيذي لها بلغة Rust، مكتوبًا من الصفر: parser، ثم Thompson NFA، ثم Pike VM و lazy DFA. لا يقوم بأي backtracking، ونتائجه تُقارَن بنتائج الـ crate المسمّى regex عبر الاختبار التفاضلي (differential testing). هذا المقال عمّا بنيته وما يعلّمه.
ماذا بنيت
المحرّك سلسلة من أربع مراحل.
1. الـ parser (parser.rs) محلل بطريقة recursive descent ينتج AST. كل حرف وكل صنف (class) وكل escape يصبح قائمة مرتّبة من مجالات char، فلا ترى المراحل التالية إلا نوعًا واحدًا من الأوراق.
2. الـ Thompson NFA (nfa.rs) يترجم الـ AST إلى مجموعة تعليمات صغيرة: Class (طابِق حرفًا واحدًا ضمن مجالات)، Split (جرّب فرعين)، Save (سجّل موضع capture)، Look (الشرطان ^ و$) وMatch. التعليمة Split مرتّبة: الفرع الأول له الأولوية، وهذا هو كل الفرق بين المكمّمات الطمّاعة (greedy) والكسولة (lazy). والتكرار المعدود مثل {2,5} يُفكّ إلى نسخ.
3. الـ Pike VM (pikevm.rs) تحاكي كل خيوط الـ NFA معًا خطوة بخطوة، حرفًا واحدًا من المُدخل في كل مرة، بترتيب الأولوية. كل خيط يحمل نسخته من خانات الـ capture. حين يطابق خيط، تُقطع الخيوط الأقل أولوية، فنحصل على دلالة leftmost-first، وهي القاعدة نفسها التي تتبعها المحرّكات على طريقة Perl. تُستعمل لـ find وcaptures وfind_iter.
4. الـ lazy DFA (dfa.rs) يبني حالات الـ DFA، وكل حالة مجموعة من حالات الـ NFA، عند الطلب أثناء المسح، ويخزّن الانتقالات في cache: جداول بـ 128 مدخلًا لـ ASCII مع map للحروف الأخرى. البحث غير مثبَّت (تُضاف حالة بداية الـ NFA من جديد بعد كل حرف)، وشروط $ تبقى معلّقة حتى نهاية المُدخل. يُفرَّغ الـ cache حين يتجاوز 4096 حالة، فتبقى الذاكرة محدودة. يُستعمل لـ is_match، وكرفض سريع قبل تشغيل الـ Pike VM.
الصياغة المدعومة: الحروف، . (أي حرف غير \n)، الأصناف [a-z] و[^...] و[]a] و[a-]، والـ escapes \d \w \s \D \W \S بتعريفات ASCII، و\n \t \r \f \v، وعلامات الترقيم المهرَّبة، والمرساتان ^ و$ (بداية النص ونهايته)، والمجموعات ( ) و(?: )، والتناوب |، والمكمّمات * + ? {n} {n,} {n,m} وصيغها الكسولة *? +? ?? {n,m}?.
طريقة الاستعمال
أضفه إلى مشروع Rust كـ git dependency:
cargo add --git https://github.com/AbdeldjalilChougui/regex-engine
الـ API سيبدو مألوفًا إن استعملت الـ crate المسمّى regex:
use regex_engine::Regex;
let re = Regex::new(r"(\w+)@(\w+)\.(com|org)")?;
assert!(re.is_match("mail bob@example.org")); // lazy DFA
let caps = re.captures("mail bob@example.org").unwrap(); // Pike VM
let m = re.find("x 12 345").map(|m| (m.start, m.end));
let all = re.find_iter("a@b.com c@d.org");
لاحظ أي محرّك يجيب عن أي سؤال. is_match تحتاج نعم أو لا فقط، فتذهب إلى الـ DFA. وcaptures تحتاج مواضع المجموعات، وهذه لا يتتبعها الـ DFA، فتذهب إلى الـ Pike VM.
في المستودع أيضًا grep صغير. انسخه وشغّل:
git clone https://github.com/AbdeldjalilChougui/regex-engine
cd regex-engine
cargo run --release --bin rgrep -- [-o] '<pattern>' file...
ماذا تعلّمت
الزمن الخطي يأتي من عدم الرجوع أبدًا. المحرّك الذي يعمل بالـ backtracking يجرّب مسارًا واحدًا في النمط، وعند الفشل يعيد المُدخل إلى الوراء ويجرّب مسارًا آخر. أما الـ Pike VM فتقدّم كل المسارات الممكنة معًا وتقرأ كل حرف من المُدخل مرة واحدة. عدد الخيوط الحية محدود بحجم الـ NFA، فالعمل لكل حرف محدود أيضًا. والأنماط التي تجمّد محرّك backtracking عادية هنا.
الأولوية هي الجزء الصعب، لا المطابقة. تحديد إن كانت السلسلة تطابق سهل بالـ NFA. أما تحديد أي مطابقة تُرجَع، وأي captures، فهنا يكون الحذر. ترتيب فرعَي كل Split، وترتيب تقديم الخيوط، يرمّزان ذلك كله.
خيار صغير في الترجمة يغيّر الـ captures. التعبير e* يُترجَم كحلقة واحدة، أو كـ (e+)? حين يمكن لـ e أن يطابق السلسلة الفارغة. هذا نفس الخيار الذي يتخذه الـ crate regex، وشكل الترجمة يغيّر أي captures تُرجعها الـ Pike VM. لم أجد ذلك بالقراءة. وجدته الاختبارات التفاضلية.
الـ DFA هو cache لمحاكاة الـ NFA. كل حالة DFA هي ببساطة "مجموعة حالات الـ NFA التي قد أكون فيها". بناؤها كلها مسبقًا قد ينفجر حجمه، فالـ lazy DFA يبني فقط الحالات التي يبلغها المُدخل فعلًا، ويرمي الـ cache حين يكبر كثيرًا. هذه الفكرة الواحدة تشرح لماذا الـ DFA سريع ولماذا يبقى آمنًا.
الاختبار التفاضلي أثمن من الحالات المكتوبة باليد. الملف tests/differential.rs يولّد أنماطًا عشوائية (مجموعات متداخلة، تناوبات، كل صيغ المكمّمات، أصناف، escapes، مرساة) ونصوصًا عشوائية. ولكل زوج يتحقق من is_match على الـ DFA والـ Pike VM معًا، ومن find وcaptures وfind_iter، مقارنةً بالـ crate regex. وحين تفشل حالة، يقلّصها examples/minimize.rs إلى أصغر مثال يعيد إنتاج الخطأ. هكذا وُجدت مشكلة أولوية الـ capture في (e+)?.
cargo test # unit tests + differential (200 patterns in debug)
cargo test --release --test differential # 4000 random patterns x 25 haystacks
DIFF_PATTERNS=20000 cargo test --release --test differential
ما يجب معرفته
هذا مشروع تعليمي. الـ README يسرد الحدود:
-
صياغة ناقصة. لا flags (
(?i)و(?m)و(?s))، ولا\b، ولا أصناف Unicode (\p{..})، ولا مجموعات مسمّاة، ولا أصناف متداخلة ولا عمليات مجموعات على الأصناف. -
أصناف ASCII.
\d \w \sخاصة بـ ASCII فقط، بينماregexيعتمد Unicode افتراضيًا. الاختبارات التفاضلية تستعمل نصوص ASCII، حيث يتفق الاثنان. -
الـ DFA يجيب عن
is_matchفقط. مواضع المطابقة تأتي من الـ Pike VM، وهي أبطأ بكثير من بحث حقيقي مبني على DFA. -
RegexليسSync، لأن cache الـ DFA موجود داخلRefCell.
للعمل الحقيقي استعمل الـ crate regex. هو المرجع الذي يُختبر هذا المشروع مقابله.
لماذا بنيته
أردت أن أفهم لماذا تستطيع بعض محرّكات الـ regex أن تعِد بزمن خطي ولا يستطيع غيرها. مقالات Russ Cox تشرح النظرية بوضوح، وهي المكان الصحيح للبدء. لكن النظرية تتسع لها صفحة، والصعوبة في التفاصيل التي تتخطّاها الصفحة: مجموعات الـ capture، الطمّاع مقابل الكسول، المطابقات الفارغة، المرساة داخل بحث غير مثبَّت. كتابة المحرّك هي ما يجعل هذه التفاصيل ملموسة.
ووجود محرّك ناضج للمقارنة جعل المشروع أصدق بكثير. دون الاختبارات التفاضلية كان عندي محرّك regex ينجح في الحالات التي خطرت لي. ومعها عندي محرّك يتفق مع regex على آلاف الأنماط العشوائية، ضمن الصياغة التي يدعمها الاثنان.
الكود
الكود والاختبارات التفاضلية وأداة التقليص موجودة على GitHub: https://github.com/AbdeldjalilChougui/regex-engine. الرخصة MIT، والـ issues والـ pull requests مرحّب بها. ومقالات Russ Cox موجودة على swtch.com/~rsc/regexp/.
نُشر في الأصل على abdeldjalilchougui.biz.
Top comments (0)