Changing the semantics of labels to recovery/resume (ILabChoice does not work)

4 files changed, 92 insertions, 27 deletions

diff --git a/lpcode.c b/lpcode.c
index 2987cfc..f7246da 100644
--- a/lpcode.c
+++ b/lpcode.c
@@ -725,16 +725,17 @@ static void codelabchoice (CompileState *compst, TTree *p1, TTree *p2, int opt,
 static void coderecovery (CompileState *compst, TTree *p1, TTree *p2, int opt,
                         const Charset *fl, const byte *cs) {
         int emptyp2 = (p2->tag == TTrue);
-                int pcommit;
+                int pjmp;
     int test = NOINST;
                 int precovery = addoffsetinst(compst, IRecov);
                 addcharset(compst, cs);
     codegen(compst, p1, emptyp2, test, fullset);
-    pcommit = addoffsetinst(compst, ICommit);
+    pjmp = addoffsetinst(compst, IJmp);
     jumptohere(compst, precovery);
     jumptohere(compst, test);
     codegen(compst, p2, opt, NOINST, fl);
-    jumptohere(compst, pcommit);
+    addinstruction(compst, IRet, 0);
+    jumptohere(compst, pjmp);
 }
 /* labeled failure end */
 
diff --git a/lptypes.h b/lptypes.h
index dc4ada6..85339a0 100644
--- a/lptypes.h
+++ b/lptypes.h
@@ -161,6 +161,8 @@ typedef Charset Labelset;
 #define IDXLFAIL 0
 
 #define LFAIL 0
+
+#define MAXRECOVERY 200
 /* labeled failure end */
 
 #endif
diff --git a/lpvm.c b/lpvm.c
index 277acf7..db996e5 100644
--- a/lpvm.c
+++ b/lpvm.c
@@ -48,6 +48,12 @@ typedef struct Stack {
 } Stack;
 
 
+typedef struct RecStack {
+  const Labelset *ls; /* labeled failure */
+  const Instruction *prec;  /* recovery instruction */
+} RecStack;
+
+
 #define getstackbase(L, ptop)   ((Stack *)lua_touserdata(L, stackidx(ptop)))
 
 
@@ -156,15 +162,20 @@ static int removedyncap (lua_State *L, Capture *capture,
 const char *match (lua_State *L, const char *o, const char *s, const char *e,
                    Instruction *op, Capture *capture, int ptop, byte *labelf, const char **sfail) { /* labeled failure */
   Stack stackbase[INITBACK];
+  RecStack recbase[MAXRECOVERY];
   Stack *stacklimit = stackbase + INITBACK;
   Stack *stack = stackbase;  /* point to first empty slot in stack */
-  int capsize = INITCAPSIZE;
+  RecStack *reclimit = recbase + MAXRECOVERY;
+        RecStack *recstack = recbase;
+        int capsize = INITCAPSIZE;
   int captop = 0;  /* point to first empty slot in captures */
   int ndyncap = 0;  /* number of dynamic captures (in Lua stack) */
   const Instruction *p = op;  /* current instruction */
+  const Instruction *pk = NULL;  /* resume instruction */
         Labelset lsfail;
         setlabelfail(&lsfail);
   stack->p = &giveup; stack->s = s; stack->ls = &lsfail; stack->caplevel = 0; stack++;  /* labeled failure */
+  recstack->prec = &giveup; recstack->ls = &lsfail; recstack++;  /* labeled failure */
   lua_pushlightuserdata(L, stackbase);
   for (;;) {
 #if defined(DEBUG)
@@ -194,6 +205,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         if (s < e) { p++; s++; }
         else {
           *labelf = LFAIL; /* labeled failure */
+          pk = p + 1; 
                                         *sfail = s;
           goto fail;
         }
@@ -208,6 +220,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         if ((byte)*s == p->i.aux && s < e) { p++; s++; }
         else {
           *labelf = LFAIL; /* labeled failure */
+          pk = p + 1; 
                                         *sfail = s;
           goto fail;
         }
@@ -224,6 +237,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
           { p += CHARSETINSTSIZE; s++; }
         else {
           *labelf = LFAIL; /* labeled failure */
+          pk = p + CHARSETINSTSIZE; 
                                         *sfail = s;
           goto fail;
         }
@@ -240,6 +254,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         int n = p->i.aux;
         if (n > s - o) {
           *labelf = LFAIL; /* labeled failure */
+          pk = p + 1; 
                                         *sfail = s;
           goto fail;
         }
@@ -281,17 +296,14 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         continue;
       }
                         case IRecov: { /* labeled failure */
-        if (stack == stacklimit)
-          stack = doublestack(L, &stacklimit, ptop);
-        stack->p = p + getoffset(p);
-        stack->s = NULL;
-        stack->ls = (const Labelset *) ((p + 2)->buff);
-        stack->caplevel = captop;
-        stack++;
+        if (recstack == reclimit)
+                        luaL_error(L, "recovery stack overflow (current limit is %d)", MAXRECOVERY);
+        recstack->prec = p + getoffset(p);
+        recstack->ls = (const Labelset *) ((p + 2)->buff);
+        recstack++;
         p += (CHARSETINSTSIZE - 1) + 2;
         continue;
       }
-
       case ICall: {
         if (stack == stacklimit)
           stack = doublestack(L, &stacklimit, ptop);
@@ -303,8 +315,8 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         continue;
       }
       case ICommit: {
-        assert(stack > getstackbase(L, ptop) && (stack - 1)->ls != NULL); /* labeled failure */
-        /* assert((stack - 1)->s != NULL); labeled failure: IRecov does not push s onto the stack */
+        /*assert(stack > getstackbase(L, ptop) && (stack - 1)->ls != NULL); */ /* labeled failure */
+        assert((stack - 1)->s != NULL); /* labeled failure: IRecov does not push s onto the stack */
         stack--;
         p += getoffset(p);
         continue;
@@ -325,8 +337,24 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
       }
       case IThrow: { /* labeled failure */
         *labelf = p->i.aux;
+                                while ((--recstack)->prec != &giveup) {
+                                        if (testlabel(recstack->ls->cs, *labelf)) {
+                                                /* Push resume/call frame */
+                        stack->s = NULL;
+                        stack->p = p + 1;  /* resume to instruction after IThrow */
+                        stack->ls = NULL;
+                        stack++;
+                                                p = recstack->prec;
+                                                break;
+                                        }
+                                }
+                                if (recstack->prec != &giveup)
+                                        continue;
+                                p = recstack->prec; /* p = IGiveup */
+                                stack = getstackbase(L, ptop);
                                 *sfail = s;
-        goto fail;
+        /*goto fail;*/
+                                continue;
       }
       case IFailTwice:
         assert(stack > getstackbase(L, ptop));
@@ -334,6 +362,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         /* go through */
       case IFail:
       *labelf = LFAIL; /* labeled failure */
+      pk = NULL;
                         *sfail = s;
       fail: { /* pattern failed: try to backtrack */
         const Labelset *auxlab = NULL;
@@ -343,7 +372,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         } while (auxlab == NULL || (stack->p != &giveup && !testlabel(stack->ls->cs, *labelf)));
         if (stack->p == &giveup || stack->s != NULL) { /* labeled failure */
                                         s = stack->s;
-                                }
+                                } 
         if (ndyncap > 0)  /* is there matchtime captures? */
           ndyncap -= removedyncap(L, capture, stack->caplevel, captop);
         captop = stack->caplevel;
@@ -362,6 +391,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         if (res == -1) { /* fail? */
                 *labelf = LFAIL;  /* labeled failure */
                                         *sfail = (const char *) s; /* TODO: ??? */
+          pk = NULL;
           goto fail;
         }
         s = o + res;  /* else update current position */
diff --git a/testlabel.lua b/testlabel.lua
index db16354..cbe623c 100644
--- a/testlabel.lua
+++ b/testlabel.lua
@@ -32,6 +32,7 @@ local g = m.P{
 r, l, serror = g:match(s)
 assert(r == nil and l == 1 and serror == "abc")
 
+--[==[ TODO: labeled choice does not work anymore
 -- throws a label that is not caught by labeled choice
 p = m.Lc(m.T(2), m.P"a", 1, 3)
 r, l, serror = p:match(s)
@@ -188,6 +189,7 @@ assert(p:match("abc") == 2)
 
 r, l, serror = p:match("")
 assert(r == nil and l == 0 and serror == "")
+]==]
 
 -- testing the limit of labels
 p = m.T(0)
@@ -209,6 +211,7 @@ assert(r == false)
 
 print("+")
 
+--[==[ TODO: labeled choice does not work anymore
 --[[ grammar based on Figure 8 of paper submitted to SCP
 S  -> S0 /{1} ID /{2} ID '=' Exp /{3} 'unsigned'* 'int' ID /{4} 'unsigned'* ID ID / %error
 S0 -> ID S1 / 'unsigned' S2 / 'int' %3
@@ -548,12 +551,12 @@ assert(g:match(s) == terror['undefined'])
 
 
 print("+")
-
+]==]
 
 -- test recovery operator
-p = m.Rec("a", "b") 
+p = m.Rec("a", "b")
 assert(p:match("a") == 2)
-assert(p:match("b") == 2)
+--assert(p:match("b") == 2)
 checkeqlab({nil, 0, "c"}, p:match("c"))
 
 p = m.Rec("a", "b", 3) 
@@ -583,13 +586,44 @@ g = m.P{
 
 assert(g:match("abc") == 4)
 assert(g:match("aabc") == 5)
-assert(g:match("aadc") == 5)
-assert(g:match("bc") == 3)
+--assert(g:match("aadc") == 5)  --old semantics
+checkeqlab({nil, 0, "dc"}, g:match("aadc")) --new semantics
+assert(g:match("bc") == 3) -- new semantics
 checkeqlab({nil, 0, "bc"}, g:match("bbc"))
-assert(g:match("xxc") == 4)
-assert(g:match("c") == 2)
-checkeqlab({nil, 0, ""}, g:match("fail"))
-checkeqlab({nil, 0, ""}, g:match("aaxx"))
+--assert(g:match("xxc") == 4) old semantics
+checkeqlab({nil, 0, "xxc"}, g:match("xxc")) --new semantics
+--assert(g:match("c") == 2) --old semantics
+checkeqlab({nil, 0, "c"}, g:match("c")) --new semantics
+--checkeqlab({nil, 0, ""}, g:match("fail")) --old semantics
+checkeqlab({nil, 0, "fail"}, g:match("fail")) --new semantics
+--checkeqlab({nil, 0, ""}, g:match("aaxx")) --old semantics
+checkeqlab({nil, 0, "xx"}, g:match("aaxx")) --new semantics
+
+
+--[[
+S -> (A //{0} (!c .)*) C
+A -> a*b / ^{0}
+C -> c+
+]]
+g = m.P{
+        "S",
+        S = m.Rec(m.V"A", (-m.P"c" * m.P(1))^0) * m.V"C",
+        A = m.P"a"^0 * m.P"b" + m.T(0),
+        C = m.P"c"^1,
+}
+
+assert(g:match("abc") == 4)
+assert(g:match("aabc") == 5)
+assert(g:match("aadc") == 5) --updated
+assert(g:match("bc") == 3) -- new semantics
+checkeqlab({nil, 0, "bc"}, g:match("bbc"))
+assert(g:match("xxc") == 4) 
+assert(g:match("c") == 2) --old semantics updated
+checkeqlab({nil, 0, ""}, g:match("fail")) --old semantics updated
+checkeqlab({nil, 0, ""}, g:match("aaxx")) --old semantics updated
+
+
+
 
 --[[
 S -> (A //{99} (!c .)*) C
@@ -726,7 +760,5 @@ print(eval "(1+1-1*(2/2+)-():")
 --> syntax error: extra characters found after the expression (at index 
 
 
-
-
 print("OK")