كيفية تجنب الحلقات اللانهائية في فئة .NET RegEx؟

Question

حصلت على مهمة بسيطة للحصول على تعبير XPath وإرجاع بادئة تطابق أصل العقدة التي (قد تكون) محددة.

مثال:

/aaa/bbb       =>   /aaa
/aaa/bbb/ccc   =>   /aaa/bbb
/aaa/bbb/ccc[@x='1' and @y="/aaa[name='z']"] => /aaa/bbb

نظرًا لأن الأنماط الموجودة داخل الأقواس المربعة قد تحتوي على أقواس بين علامتي اقتباس، فقد قررت أن أحاول تحقيق ذلك باستخدام التعبيرات العادية.إليك مقتطف التعليمات البرمجية:

string input =
    "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
                                            //  ^-- remove space for no loop
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";

System.Text.RegularExpressions.Regex re =
    new System.Text.RegularExpressions.Regex(pattern);
bool ismatch = re.IsMatch(input); // <== Infinite loop in here
// some code based on the match

نظرًا لأن الأنماط منتظمة إلى حد ما، فقد بحثت عن '/' متبوعًا بمعرف متبوعًا بمجموعة اختيارية تتطابق في نهاية السلسلة (....)؟$

يبدو أن الكود يعمل ولكن عند اللعب بقيم مختلفة لسلسلة الإدخال، وجدت أنه بمجرد إدخال مسافة (في الموقع الموضح في التعليق)، تدخل وظيفة .NET IsMatch في حلقة لا نهائية، مع أخذ كل وحدة المعالجة المركزية التي تحصل عليها .

الآن بغض النظر عما إذا كان نمط التعبير العادي هذا هو الأفضل (كان لدي نمط أكثر تعقيدًا ولكن قمت بتبسيطه لإظهار المشكلة)، يبدو أن هذا يوضح أن استخدام RegEx مع أي شيء غير تافه قد يكون محفوفًا بالمخاطر للغاية.

هل فاتني شيء؟هل هناك طريقة للحماية من الحلقات اللانهائية في مباريات التعبير العادي؟

Answer 1

حسنًا ، دعنا نحلل هذا بعد ذلك:

Input: /aaa/bbb/ccc[@x='1' and @y="/aaa[name='z'] "]
Pattern: /[a-zA-Z0-9]+(\[([^]]*(]")?)+])?$

(أفترض أنك تقصد \" في سلسلة الهروب C#، وليس ""...الترجمة من VB.NET؟)

أولاً، /[a-zA-Z0-9]+ سوف يلتهم القوس المربع الأول، ويترك:

Input: [@x='1' and @y="/aaa[name='z'] "]

يجب أن تتطابق المجموعة الخارجية لـ (\[([^]]*(]"")?)+])?$" إذا كان هناك مثيل 0 أو 1 قبل موسوعة الحياة.لذلك دعونا نقتحم الداخل ونرى ما إذا كان يطابق أي شيء.

يتم التهام "[" على الفور، مما يترك لنا:

Input: @x='1' and @y="/aaa[name='z'] "]
Pattern: ([^]]*(]")?)+]

كسر النمط:مطابقة 0 أو أكثر غير] الأحرف ومن ثم المباراة "] 0 أو 1 مرة، واستمر في القيام بذلك حتى لا تتمكن من ذلك.ثم حاول العثور على وتلتهم أ ] بعد ذلك.

يتطابق النمط بناءً على [^]]* حتى يصل إلى ].

وبما أن هناك مسافة بين ] و ", ، لا يمكنه التهام أي من تلك الشخصيات، ولكن ? بعد (]") يسمح لها بالعودة صحيحا على أي حال.

الآن لقد تمت المطابقة بنجاح ([^]]*(]")?) مرة واحدة، ولكن + يقول أننا يجب أن نحاول الاستمرار في مطابقته لأي عدد ممكن من المرات.

وهذا يتركنا مع:

Input: ] "]

المشكلة هنا هي أن هذا الإدخال يمكن أن يتطابق ([^]]*(]")?) ان لانهائي مرات دون أن يتم التهامها أبدًا، و"+" ستجبرها على الاستمرار في المحاولة.

أنت تقوم بشكل أساسي بمطابقة المواقف "1 أو أكثر" حيث يمكنك مطابقة "0 أو 1" لشيء ما متبوعًا بـ "0 أو 1" لشيء آخر.نظرًا لعدم وجود أي من النمطين الفرعيين في الإدخال المتبقي، فإنه يستمر في مطابقة 0 من [^]]\* و 0 من (]")? في حلقة لا نهاية لها.

لا يتم التهام المدخلات أبدًا، ولا يتم تقييم بقية النمط بعد علامة "+" أبدًا.

(آمل أن أكون قد حصلت على SO-escape-of-regex-escape أعلاه مباشرة.)

Answer 2

<اقتباس فقرة>   

والمشكلة هنا هي أن هذا المدخل يمكن أن المباراة ([^]] * (] ")؟) لانهائي من المرات دون أن يجري استحوذت، و" + "واجبارها للحفاظ على مجرد محاولة.

وهذا هو واحد من الجحيم خطأ في التنفيذ باستخدام التعابير المنطقية. NET ل. التعابير العادية فقط لا تعمل من هذا القبيل. عند تحويلها إلى الآلي، وتحصل تلقائيا على حقيقة أن التكرار لا حصر له من سلسلة فارغة لا يزال سلسلة فارغة.

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

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

Answer 3

وهذا يظهر أن استخدام <م> كود مع أي شيء لا تافهة يمكن أن تكون خطرة. قمت بإنشائه التعليمات البرمجية التي يمكن أن يؤدي إلى حلقة لا نهائية، ومترجم باستخدام التعابير المنطقية ملزمة. لا شيء جديد لم يحدث منذ أول 20 IF X = 0 THEN GOTO 10.

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

Answer 4

للرد على السؤال الأصلي (أي كيفية تجنب حلقة لا نهائية مع التعابير المنطقية)، أصبح هذا العمل سهلا مع صافي 4.5 كما يمكنك ببساطة تمرير الوقت لأساليب التعبير العادي. هناك جهاز توقيت الداخلية التي من شأنها وقف حلقة التعابير المنطقية عند انتهاء المهلة ورفع RegexMatchTimeoutException

وعلى سبيل المثال، يمكنك أن تفعل ما يلي

string input = "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";
bool ismatch = Regex.IsMatch(input, pattern, RegexOptions.None, TimeSpan.FromSeconds(5));

ويمكنك التحقق من MSDN لمزيد من التفاصيل