[Mono-bugs] [Bug 72989][Blo] Changed - Stack overflw in RegularExpression parsing
bugzilla-daemon@bugzilla.ximian.com
bugzilla-daemon@bugzilla.ximian.com
Wed, 2 Mar 2005 14:21:04 -0500 (EST)
Please do not reply to this email- if you want to comment on the bug, go to the
URL shown below and enter your comments there.
Changed by eyala@mainsoft.com.
http://bugzilla.ximian.com/show_bug.cgi?id=72989
--- shadow/72989 2005-03-02 14:12:47.000000000 -0500
+++ shadow/72989.tmp.4772 2005-03-02 14:21:04.000000000 -0500
@@ -160,6 +160,52 @@
recursion level being proportional to the regular expression and not
to the input.
Could you give me an explanation of the code in order for me to make
such a change? I'd like to implement the following logic:
for (;;) {
+
+------- Additional Comments From eyala@mainsoft.com 2005-03-02 14:21 -------
+I still see the stack overflow happening using the test case. Is
+there something I am missing? I have applied the patch to the Mono
+latest version of interpreter.cs and it did not help. It could be
+since I am not using Mono but am testing agains the .Net CLR, so
+please test that as well.
+The code flow as I understand it now is that for handling a '*'
+operator that is applied on an expression (I'll call it a repeat
+expression) then the code will match the repeat expression once and
+use a recursion to repeatedly match the input with the repeat
+expression and the expressions that follow it.
+In the scenario attached here the repeat expression matches one
+character at a time (it is the last part ([^;]) that is successful
+every time) and then goes into recursion once for EVERY character.
+This is indeed too much
+for every character there is a recursions to check if it matches the
+repeat expression (the most outer expression that is repeatedly
+matched using '*'). Since every character in the example string
+matches the last part within the repeat expression ([^;]) then the
+code goes again into recursion to see if it can continue to match.
+The changes you made did not affect this behaviour.
+A change that will not recurse every time it matches the repeat
+expression will resolve the problem. The goal is to have the
+recursion level being proportional to the regular expression and not
+to the input.
+Could you give me an explanation of the code in order for me to make
+such a change? I'd like to implement the following logic:
+for (;;) {
+ States.Push(current state);
+ if (!Match(Only the repeat expression)) {
+ current state = States.Pop();
+ break;
+ }
+}
+for (;;) {
+ if (Eval(Mode.Match, ref ptr, pc + 1)) // Match the tail.
+ goto Pass;
+ if (States.IsEmpty())
+ goto Fail;
+ current state = States.Pop(); // try previous match of the repeat
+expression
+}
+The main issue is that I don't see well how to match the Repeat
+expression exactly once. I think I can define well what is the state
+to hold within the stack and how to manage the other details.