[Mono-bugs] [Bug 72989][Blo] Changed - Stack overflw in RegularExpression parsing

[bugzilla-daemon@bugzilla.ximian.com]

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.