Implementing the new semantics of predicates when a label is thrown

6 files changed, 114 insertions, 50 deletions

diff --git a/lpcode.c b/lpcode.c
index 1036fdf..ef357bc 100644
--- a/lpcode.c
+++ b/lpcode.c
@@ -449,7 +449,7 @@ int sizei (const Instruction *i) {
     case ITestChar: case ITestAny: case IChoice: case IJmp: case ICall:
     case IOpenCall: case ICommit: case IPartialCommit: case IBackCommit:
       return 2;
-    case IThrow:  /* labeled failure */ 
+    case IThrow: case IPredChoice: /* labeled failure */ 
                         return 2;
     case IThrowRec:  /* labeled failure */ 
                         return 3;
@@ -747,15 +747,19 @@ static void codechoice (CompileState *compst, TTree *p1, TTree *p2, int opt,
 ** (valid only when 'p' has no captures)
 */
 static void codeand (CompileState *compst, TTree *tree, int tt) {
-  int n = fixedlen(tree);
+  /* labeled failure: optimization disabled bacause in case of a failure it
+     does not report the expected error position (the current subject position
+     when begin the matching of <&p>) */
+  /*int n = fixedlen(tree);
   if (n >= 0 && n <= MAXBEHIND && !hascaptures(tree)) {
     codegen(compst, tree, 0, tt, fullset);
     if (n > 0)
       addinstruction(compst, IBehind, n);
   }
-  else {  /* default: Choice L1; p1; BackCommit L2; L1: Fail; L2: */
+  else */{  /* default: Choice L1; p1; BackCommit L2; L1: Fail; L2: */
     int pcommit;
-    int pchoice = addoffsetinst(compst, IChoice);
+    int pchoice = addoffsetinst(compst, IPredChoice); /* labeled failure */
+    getinstr(compst, pchoice).i.aux = ANDPRED;  
     codegen(compst, tree, 0, tt, fullset);
     pcommit = addoffsetinst(compst, IBackCommit);
     jumptohere(compst, pchoice);
@@ -857,7 +861,8 @@ static void codenot (CompileState *compst, TTree *tree) {
     addinstruction(compst, IFail, 0);
   else {
     /* test(fail(p))-> L1; choice L1; <p>; failtwice; L1:  */
-    int pchoice = addoffsetinst(compst, IChoice);
+    int pchoice = addoffsetinst(compst, IPredChoice); /* labeled failure */
+    getinstr(compst, pchoice).i.aux = NOTPRED;  
     codegen(compst, tree, 0, NOINST, fullset);
     addinstruction(compst, IFailTwice, 0);
     jumptohere(compst, pchoice);
diff --git a/lpprint.c b/lpprint.c
index 21fb038..3c6a8f6 100644
--- a/lpprint.c
+++ b/lpprint.c
@@ -58,7 +58,7 @@ void printinst (const Instruction *op, const Instruction *p) {
     "testany", "testchar", "testset",
     "span", "behind",
     "ret", "end",
-    "choice", "jmp", "call", "open_call",
+    "choice", "pred_choice", "jmp", "call", "open_call", /* labeled failure */
     "commit", "partial_commit", "back_commit", "failtwice", "fail", "giveup",
      "fullcapture", "opencapture", "closecapture", "closeruntime",
     "throw", "throw_rec",  /* labeled failure */
@@ -103,7 +103,8 @@ void printinst (const Instruction *op, const Instruction *p) {
       break;
     }
     case IJmp: case ICall: case ICommit: case IChoice:
-    case IPartialCommit: case IBackCommit: case ITestAny: {
+    case IPartialCommit: case IBackCommit: case ITestAny:
+    case IPredChoice: { /* labeled failure */
       printjmp(op, p);
       break;
     }
diff --git a/lptypes.h b/lptypes.h
index 25e84a2..d523e27 100644
--- a/lptypes.h
+++ b/lptypes.h
@@ -150,6 +150,11 @@ typedef struct Charset {
 /* update the farthest failure */
 #define updatefarthest(s1,s2) { if ((s2) > (s1)) s1 = s2; }
 
+/* indicate whether the machine is matching a predicate or not */
+#define OUTPRED 0
+#define NOTPRED 1
+#define ANDPRED 2
+
 /* labeled failure end */
 
 #endif
diff --git a/lpvm.c b/lpvm.c
index 9812e19..f56f1d5 100644
--- a/lpvm.c
+++ b/lpvm.c
@@ -39,6 +39,7 @@ typedef struct Stack {
   const Instruction *p;  /* next instruction */
   int caplevel;
   byte labenv; /* labeled failure */
+  byte predchoice; /* labeled failure */
 } Stack;
 
 
@@ -156,8 +157,8 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
   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 */
-  byte labenv = 1; /* labeled failure: label environment is on */
-  stack->p = &giveup; stack->s = s; stack->caplevel = 0; stack->labenv = 1; stack++;  /* labeled failure */
+  byte insidepred = OUTPRED; /* labeled failure: label environment is off inside predicates */
+  stack->p = &giveup; stack->s = s; stack->caplevel = 0; stack->labenv = insidepred; stack++;  /* labeled failure */
         *sfail = s; /* labeled failure */
   lua_pushlightuserdata(L, stackbase);
   for (;;) {
@@ -168,9 +169,8 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
              s, (int)(stack - getstackbase(L, ptop)), ndyncap, captop);
       printinst(op, p);
 #endif
-    printinst(op, p);
     assert(stackidx(ptop) + ndyncap == lua_gettop(L) && ndyncap <= captop);
-    assert(labenv == 1);
+    assert(insidepred == NOTPRED || insidepred == ANDPRED || insidepred == OUTPRED);
     switch ((Opcode)p->i.code) {
       case IEnd: {
         assert(stack == getstackbase(L, ptop) + 1);
@@ -191,7 +191,8 @@ 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 */
-                                        updatefarthest(*sfail, s); /*labeled failure */
+          if (insidepred == OUTPRED)
+                                          updatefarthest(*sfail, s); /*labeled failure */
           goto fail;
         }
         continue;
@@ -205,7 +206,8 @@ 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 */
-                                        updatefarthest(*sfail, s); /*labeled failure */
+          if (insidepred == OUTPRED)
+                                          updatefarthest(*sfail, s); /*labeled failure */
           goto fail;
         }
         continue;
@@ -221,7 +223,8 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
           { p += CHARSETINSTSIZE; s++; }
         else {
           *labelf = LFAIL; /* labeled failure */
-                                        updatefarthest(*sfail, s); /*labeled failure */
+          if (insidepred == OUTPRED)
+                                          updatefarthest(*sfail, s); /*labeled failure */
           goto fail;
         }
         continue;
@@ -237,7 +240,8 @@ 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 */
-                                        updatefarthest(*sfail, s); /*labeled failure */
+          if (insidepred == OUTPRED)
+                                          updatefarthest(*sfail, s); /*labeled failure */
           goto fail;
         }
         s -= n; p++;
@@ -261,10 +265,24 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         stack->p = p + getoffset(p);
         stack->s = s;
         stack->caplevel = captop;
-        stack->labenv = labenv; /* labeled failure */
+        stack->labenv = insidepred; /* labeled failure */
+        stack->predchoice = 0; /* labeled failure */
         stack++;
         p += 2;
         continue;
+      } 
+      case IPredChoice: { /* labeled failure: new instruction */
+        if (stack == stacklimit)
+          stack = doublestack(L, &stacklimit, ptop);
+        stack->p = p + getoffset(p);
+        stack->s = s;
+        stack->caplevel = captop;
+        stack->labenv = insidepred;
+        stack->predchoice = 1; 
+        stack++;
+        insidepred = p->i.aux; 
+        p += 2;
+        continue;
       }
       case ICall: {
         if (stack == stacklimit)
@@ -292,38 +310,30 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
       case IBackCommit: {
         assert(stack > getstackbase(L, ptop) && (stack - 1)->s != NULL);
         s = (--stack)->s;
-        labenv = stack->labenv; /* labeled failure */
-        assert(labenv == 1); /* labeled failure */
+        insidepred = stack->labenv; /* labeled failure */
         captop = stack->caplevel;
         p += getoffset(p);
         continue;
       }
       case IThrow: { /* labeled failure */
-        /*printf("IThrow here: key=%d, key+1=%d aux = %d top = %d\n", p->i.key, (p+1)->i.key, p->i.aux, lua_gettop(L));
-        lua_rawgeti(L, ktableidx(ptop), (p+1)->i.key); 
-        printf("IThrow there %s top = %d\n", lua_tostring(L, -1), lua_gettop(L));
-        lua_pop(L, 1);*/
-        if (labenv) {
+        if (insidepred == OUTPRED) {
           *labelf = (p+1)->i.key;
           if (*labelf == LFAIL)
             luaL_error(L, "labelf is %d", *labelf);
           stack = getstackbase(L, ptop);
           stack++;
-          printf("IThrow stack->labenv = %d\n", stack->labenv);
+          *sfail = s;
         }
         else {
-          labelf = LFAIL;
+          while (!(stack-1)->predchoice) {
+            --stack;
+          } 
+          *labelf = LFAIL;
         }
-        *sfail = s;
         goto fail;
       }
       case IThrowRec: { /* labeled failure */
-        /*printf("IThrowRec here: key=%d, key+2=%d aux = %d top = %d\n", p->i.key, (p+2)->i.key, p->i.aux, lua_gettop(L));
-        lua_rawgeti(L, ktableidx(ptop), (p+2)->i.key); 
-        printf("IThrowRec there %s top = %d\n", lua_tostring(L, -1), lua_gettop(L));
-        lua_pop(L, 1);*/
-        printf("labenv here = %d\n", labenv);
-        if (labenv) {
+        if (insidepred == OUTPRED) {
           *labelf = (p+2)->i.key;
           if (*labelf == LFAIL)
               luaL_error(L, "labelf is %d", *labelf);
@@ -334,12 +344,19 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
           stack->p = p + 3;
           stack->caplevel = captop;
           stack++;
+          *sfail = s;
           p += getoffset(p);
           continue;
         } else {
-          labelf = LFAIL;
+          while (!(stack-1)->predchoice) {
+            --stack;
+          } 
+          /*if ((stack-1)->labenv == ANDPRED) {
+            printf("ANDPRED: stack - 1\n");
+            stack--;
+          }*/
+          *labelf = LFAIL;
         }
-        *sfail = s;
         goto fail;
       }
       case IFailTwice:
@@ -348,7 +365,8 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         /* go through */
       case IFail:
       *labelf = LFAIL; /* labeled failure */
-                        updatefarthest(*sfail, s); /*labeled failure */
+      if (insidepred == OUTPRED)
+                          updatefarthest(*sfail, s); /*labeled failure */
       fail: { /* pattern failed: try to backtrack */
         do {  /* remove pending calls */
           assert(stack > getstackbase(L, ptop));
@@ -357,8 +375,9 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         if (ndyncap > 0)  /* is there matchtime captures? */
           ndyncap -= removedyncap(L, capture, stack->caplevel, captop);
         captop = stack->caplevel;
-        labenv = stack->labenv;
-        assert(labenv == 1);
+        assert(((insidepred == ANDPRED || insidepred == NOTPRED) && (stack->labenv == OUTPRED)) || insidepred == stack->labenv
+        || (insidepred != OUTPRED && stack->labenv != OUTPRED));
+        insidepred = stack->labenv;
         p = stack->p;
 #if defined(DEBUG)
         printf("**FAIL**\n");
@@ -377,7 +396,8 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         res = resdyncaptures(L, fr, s - o, e - o);  /* get result */
         if (res == -1) { /* fail? */
                 *labelf = LFAIL;  /* labeled failure */
-                                        updatefarthest(*sfail, s); /*labeled failure */
+          if (insidepred == OUTPRED)
+                                          updatefarthest(*sfail, s); /*labeled failure */
           goto fail;
         }
         s = o + res;  /* else update current position */
diff --git a/lpvm.h b/lpvm.h
index 37c8522..c5457c4 100644
--- a/lpvm.h
+++ b/lpvm.h
@@ -21,7 +21,7 @@ typedef enum Opcode {
   IRet,  /* return from a rule */
   IEnd,  /* end of pattern */
   IChoice,  /* stack a choice; next fail will jump to 'offset' */
-  /*IPredChoice,*/  /* labeld failure: stack a choice; changes label env next fail will jump to 'offset' */
+  IPredChoice,  /* labeld failure: stack a choice; changes label env next fail will jump to 'offset' */
   IJmp,  /* jump to 'offset' */
   ICall,  /* call rule at 'offset' */
   IOpenCall,  /* call rule number 'key' (must be closed to a ICall) */
diff --git a/testlabel.lua b/testlabel.lua
index b834be3..7461206 100644
--- a/testlabel.lua
+++ b/testlabel.lua
@@ -194,27 +194,59 @@ assert(p:match("bac") == 3)
 r, l, poserr = p:match("cab")
 assert(r == nil and l == 'fail' and poserr == 1)
 
-
 -- tests related to predicates
+p = #m.T(1)
+r, l, poserr = p:match("abc")
+assert(r == nil and l == 'fail' and poserr == 1)
+
 p = #m.T(1) + m.P"a"
 r, l, poserr = p:match("abc")
-assert(r == nil and l == 1 and poserr == 1)
+assert(r == 2)
+
+p = #m.T(1) * m.P"a"
+r, l, poserr = p:match("abc")
+assert(r == nil and l == 'fail' and poserr == 1)
 
 p = ##m.T(1) + m.P"a"
 r, l, poserr = p:match("abc")
-assert(r == nil and l == 1 and poserr == 1)
+assert(r == 2)
 
-p = -m.T(1) * m.P"a"
+p = -#m.T(1) + m.P"a"
 r, l, poserr = p:match("abc")
-assert(r == nil and l == 1 and poserr == 1)
+assert(r == 1)
 
 p = -m.T(1) * m.P"a"
+r, l, poserr = p:match("abc")
+assert(r == 2)
+
+p = -m.T(1)
 r, l, poserr = p:match("bbc")
-assert(r == nil and l == 1 and poserr == 1)
+assert(r == 1)
+
+p = -#m.T(1)
+r, l, poserr = p:match("bbc")
+assert(r == 1)
 
-p = -(-m.T(1)) * m.P"a"
+p = -(-m.P'a')
 r, l, poserr = p:match("abc")
-assert(r == nil and l == 1 and poserr == 1)
+assert(r == 1)
+
+p = -(-m.P'a')
+r, l, poserr = p:match("bbc")
+assert(r == nil and l == 'fail' and poserr == 1)
+
+p = #(m.P"a" * m.T(1))
+r, l, poserr = p:match("abc")
+assert(r == nil and l == 'fail' and poserr == 1)
+
+p = #(m.P"a" * m.P'a')
+r, l, poserr = p:match("abc")
+assert(r == nil and l == 'fail' and poserr == 1)
+
+
+p = -(-m.T(1))
+r, l, poserr = p:match("bbc")
+assert(r == nil and l == 'fail' and poserr == 1)
 
 p = m.P{
   "S",
@@ -222,7 +254,7 @@ p = m.P{
   ["22"] = m.P"a" 
 } 
 r, l, poserr = p:match("abc")
-assert(r == nil and l == 'fail' and poserr == 2)
+assert(r == 1)
 
 assert(p:match("bbc") == 1)
 
@@ -231,7 +263,8 @@ p = m.P{
   S = #m.T(22),
   ["22"] = m.P"a" 
 }
-assert(p:match("abc") == 1)
+r, l, poserr = p:match("abc")
+assert(r == nil and l == 'fail' and poserr == 1)
 
 p = m.P{
   "S",
@@ -262,7 +295,7 @@ p = m.P{
   ["22"] = m.T(15) 
 }
 r, l, poserr = p:match("abc")
-assert(r == nil and l == 15 and poserr == 2)
+assert(r == nil and l == 'fail' and poserr == 1)
 
 
 -- tests related to repetition