7 files changed, 123 insertions, 22 deletions

diff --git a/lpcode.c b/lpcode.c
index 50e6764..2987cfc 100644
--- a/lpcode.c
+++ b/lpcode.c
@@ -196,8 +196,8 @@ int checkaux (TTree *tree, int pred) {
       if (checkaux(sib2(tree), pred)) return 1;
       /* else return checkaux(sib1(tree), pred); */
       tree = sib1(tree); goto tailcall;
-                case TLabChoice: /* labeled failure */
-     /* in a labeled ordered choice we do not know whether sib2 will be evaluated */
+                case TLabChoice: case TRecov: /* labeled failure */
+     /* we do not know whether sib2 will be evaluated */
      tree = sib1(tree); goto tailcall;
     case TCapture: case TGrammar: case TRule:
       /* return checkaux(sib1(tree), pred); */
@@ -231,7 +231,7 @@ int fixedlenx (TTree *tree, int count, int len) {
         return -1;  /* may be a loop */
       /* else return fixedlenx(sib2(tree), count); */
       tree = sib2(tree); goto tailcall;
-    case TSeq: {
+    case TSeq: case TRecov: { /* labeled failure */
       len = fixedlenx(sib1(tree), count, len);
       if (len < 0) return -1;
       /* else return fixedlenx(sib2(tree), count, len); */
@@ -294,6 +294,12 @@ static int getfirst (TTree *tree, const Charset *follow, Charset *firstset) {
       loopset(i, firstset->cs[i] |= csaux.cs[i]);
       return e1 | e2;
     }
+    case TRecov: { /* labeled failure */
+        /* when p1 is not nullable, p2 has nothing to contribute;
+           and when p1 is nullable, then p2 will not match 
+           return getfirst(sib1(tree), fullset, firstset); */
+      tree = sib1(tree); follow = fullset; goto tailcall;
+    }
     case TSeq: {
       if (!nullable(sib1(tree))) {
         /* when p1 is not nullable, p2 has nothing to contribute;
@@ -372,7 +378,7 @@ static int headfail (TTree *tree) {
       if (!nofail(sib2(tree))) return 0;
       /* else return headfail(sib1(tree)); */
       tree = sib1(tree); goto tailcall;
-    case TChoice: case TLabChoice:  /* labeled failure */
+    case TChoice: case TLabChoice: case TRecov: /* labeled failure */
       if (!headfail(sib1(tree))) return 0;
       /* else return headfail(sib2(tree)); */
       tree = sib2(tree); goto tailcall;
@@ -392,7 +398,7 @@ static int needfollow (TTree *tree) {
     case TChar: case TSet: case TAny:
     case TFalse: case TTrue: case TAnd: case TNot:
     case TRunTime: case TGrammar: case TCall: case TBehind:
-    case TThrow: case TLabChoice: /* (?)labeled failure */
+    case TThrow: case TLabChoice: case TRecov: /* (?)labeled failure */
       return 0;
     case TChoice: case TRep:
       return 1;
@@ -427,7 +433,7 @@ int sizei (const Instruction *i) {
       return 2;
     case IThrow:  /* labeled failure */ 
                         return 1;
-    case ILabChoice: 
+    case ILabChoice: case IRecov: 
       return (CHARSETINSTSIZE - 1) + 2; /* labeled failure */
     default: return 1;
   }
@@ -492,7 +498,8 @@ static int addinstruction (CompileState *compst, Opcode op, int aux) {
 static int addoffsetinst (CompileState *compst, Opcode op) {
   int i = addinstruction(compst, op, 0);  /* instruction */
   addinstruction(compst, (Opcode)0, 0);  /* open space for offset */
-  assert(op == ITestSet || sizei(&getinstr(compst, i)) == 2);
+  assert(op == ITestSet || sizei(&getinstr(compst, i)) == 2 || 
+        op == IRecov || op == ILabChoice); /* labeled failure */
   return i;
 }
 
@@ -714,6 +721,21 @@ static void codelabchoice (CompileState *compst, TTree *p1, TTree *p2, int opt,
     codegen(compst, p2, opt, NOINST, fl);
     jumptohere(compst, pcommit);
 }
+
+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 test = NOINST;
+                int precovery = addoffsetinst(compst, IRecov);
+                addcharset(compst, cs);
+    codegen(compst, p1, emptyp2, test, fullset);
+    pcommit = addoffsetinst(compst, ICommit);
+    jumptohere(compst, precovery);
+    jumptohere(compst, test);
+    codegen(compst, p2, opt, NOINST, fl);
+    jumptohere(compst, pcommit);
+}
 /* labeled failure end */
 
 
@@ -951,6 +973,10 @@ static void codegen (CompileState *compst, TTree *tree, int opt, int tt,
                         codelabchoice(compst, sib1(tree), sib2(tree), opt, fl, treelabelset(tree)); 
                         break;
                 }
+                case TRecov: { /* labeled failure */
+                        coderecovery(compst, sib1(tree), sib2(tree), opt, fl, treelabelset(tree)); 
+                        break;
+                }
     default: assert(0);
   }
 }
@@ -972,7 +998,8 @@ static void peephole (CompileState *compst) {
    redo:
     switch (code[i].i.code) {
       case IChoice: case ICall: case ICommit: case IPartialCommit:
-      case IBackCommit: case ITestChar: case ITestSet: case ILabChoice: /* labeled failure */
+      case IBackCommit: case ITestChar: case ITestSet:
+      case ILabChoice: case IRecov: /* labeled failure */
       case ITestAny: {  /* instructions with labels */
         jumptothere(compst, i, finallabel(code, i));  /* optimize label */
         break;
diff --git a/lpprint.c b/lpprint.c
index 0ca0b0e..122d2e5 100644
--- a/lpprint.c
+++ b/lpprint.c
@@ -61,7 +61,7 @@ void printinst (const Instruction *op, const Instruction *p) {
     "choice", "jmp", "call", "open_call",
     "commit", "partial_commit", "back_commit", "failtwice", "fail", "giveup",
      "fullcapture", "opencapture", "closecapture", "closeruntime",
-    "throw", "labeled_choice" /* labeled failure */
+    "throw", "labeled_choice", "recovery" /* labeled failure */
   };
   printf("%02ld: %s ", (long)(p - op), names[p->i.code]);
   switch ((Opcode)p->i.code) {
@@ -112,7 +112,7 @@ void printinst (const Instruction *op, const Instruction *p) {
       printf("%d", p->i.aux);
       break;
     }
-                case ILabChoice: { /* labeled failure */
+                case ILabChoice: case IRecov: { /* labeled failure */
       printjmp(op, p);
       printcharset((p+2)->buff);
       break;
@@ -165,7 +165,7 @@ static const char *tagnames[] = {
   "call", "opencall", "rule", "grammar",
   "behind",
   "capture", "run-time",
-  "throw", "labeled-choice"  /* labeled failure */
+  "throw", "labeled-choice", "recov"  /* labeled failure */
 };
 
 
@@ -223,7 +223,7 @@ void printtree (TTree *tree, int ident) {
     default: {
       int sibs = numsiblings[tree->tag];
       printf("\n");
-      if (tree->tag == TLabChoice) { /* labeled failure */
+      if (tree->tag == TLabChoice || tree->tag == TRecov) { /* labeled failure */
         printcharset(treelabelset(tree));
         printf("\n");
                         }
diff --git a/lptree.c b/lptree.c
index 6d0f78c..c59f443 100644
--- a/lptree.c
+++ b/lptree.c
@@ -28,7 +28,7 @@ const byte numsiblings[] = {
   0, 0, 2, 1,  /* call, opencall, rule, grammar */
   1,  /* behind */
   1, 1,  /* capture, runtime capture */
-  0, 2  /* labeled failure throw, labeled choice */
+  0, 2, 2  /* labeled failure throw, labeled choice, recovery */
 };
 
 
@@ -525,12 +525,12 @@ static TTree *newthrowleaf (lua_State *L, int lab) {
   return tree;
 }
 
-static TTree *newlabchoice (lua_State *L) {
+static TTree *newrootlab2sib (lua_State *L, int tag) {
   int s1, s2;
   TTree *tree1 = getpatt(L, 1, &s1);
   TTree *tree2 = getpatt(L, 2, &s2);
   TTree *tree = newtree(L, bytes2slots(LABELSETSIZE) + 1 + s1 + s2);  /* create new tree */
-  tree->tag = TLabChoice;
+  tree->tag = tag;
   tree->u.s.ps =  1 + s1;
         tree->u.s.plab = 1 + s1 + s2;
         memcpy(sib1(tree), tree1, s1 * sizeof(TTree));
@@ -733,7 +733,7 @@ static int lp_throw (lua_State *L) {
 */
 static int lp_labchoice (lua_State *L) {
         int n = lua_gettop(L);
-        TTree *tree = newlabchoice(L);
+        TTree *tree = newrootlab2sib(L, TLabChoice);
         int i;
         for (i = 3; i <= n; i++) {
                 int d = luaL_checkinteger(L, i);
@@ -742,6 +742,24 @@ static int lp_labchoice (lua_State *L) {
         }
   return 1;
 }
+
+
+static int lp_recovery (lua_State *L) {
+        int n = lua_gettop(L);
+        TTree *tree = newrootlab2sib(L, TRecov);
+  if (n == 2) {  /* catches fail as default */
+                setlabel(treelabelset(tree), LFAIL);
+  } else {
+                int i;
+                for (i = 3; i <= n; i++) {
+                        int d = luaL_checkinteger(L, i);
+                        luaL_argcheck(L, d >= 0 && d < MAXLABELS, i, "the number of a label must be between 0 and 255");
+        setlabel(treelabelset(tree), (byte)d);
+                }
+        }
+  return 1;
+}
+
 /* labeled failure end */
 
 
@@ -1325,6 +1343,7 @@ static struct luaL_Reg pattreg[] = {
   {"type", lp_type},
   {"T", lp_throw}, /* labeled failure throw */
   {"Lc", lp_labchoice}, /* labeled failure choice */
+  {"Rec", lp_recovery}, /* labeled failure choice */
   {NULL, NULL}
 };
 
diff --git a/lptree.h b/lptree.h
index 5ed67eb..cca346e 100644
--- a/lptree.h
+++ b/lptree.h
@@ -25,7 +25,7 @@ typedef enum TTag {
   TBehind,  /* match behind */
   TCapture,  /* regular capture */
   TRunTime,  /* run-time capture */
-  TThrow, TLabChoice     /* labeled failure */
+  TThrow, TLabChoice, TRecov     /* labeled failure */
 } TTag;
 
 /* number of siblings for each tree */
diff --git a/lpvm.c b/lpvm.c
index 4d9797c..277acf7 100644
--- a/lpvm.c
+++ b/lpvm.c
@@ -164,7 +164,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
   const Instruction *p = op;  /* current instruction */
         Labelset lsfail;
         setlabelfail(&lsfail);
-  stack->p = &giveup; stack->s = s; stack->caplevel = 0; stack++;
+  stack->p = &giveup; stack->s = s; stack->ls = &lsfail; stack->caplevel = 0; stack++;  /* labeled failure */
   lua_pushlightuserdata(L, stackbase);
   for (;;) {
 #if defined(DEBUG)
@@ -280,17 +280,31 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         p += (CHARSETINSTSIZE - 1) + 2;
         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++;
+        p += (CHARSETINSTSIZE - 1) + 2;
+        continue;
+      }
+
       case ICall: {
         if (stack == stacklimit)
           stack = doublestack(L, &stacklimit, ptop);
         stack->s = NULL;
         stack->p = p + 2;  /* save return address */
+        stack->ls = NULL;
         stack++;
         p += getoffset(p);
         continue;
       }
       case ICommit: {
-        assert(stack > getstackbase(L, ptop) && (stack - 1)->s != NULL);
+        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;
@@ -322,10 +336,14 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
       *labelf = LFAIL; /* labeled failure */
                         *sfail = s;
       fail: { /* pattern failed: try to backtrack */
+        const Labelset *auxlab = NULL;
         do {  /* remove pending calls */
           assert(stack > getstackbase(L, ptop));
-          s = (--stack)->s;
-        } while (s == NULL || (stack->p != &giveup && !testlabel(stack->ls->cs, *labelf)));
+          auxlab = (--stack)->ls;
+        } 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;
diff --git a/lpvm.h b/lpvm.h
index 4b4dda5..3c27027 100644
--- a/lpvm.h
+++ b/lpvm.h
@@ -35,7 +35,8 @@ typedef enum Opcode {
   ICloseCapture,
   ICloseRunTime,
   IThrow,   /* "fails" with a specific label labeled failure */
-  ILabChoice   /* labeled choice */
+  ILabChoice,   /* labeled choice */
+  IRecov    /* stack a recovery; next fail with label 'f' will jump to 'offset'  */
 } Opcode;
 
 
diff --git a/testlabel.lua b/testlabel.lua
index 4f0768d..6ae184f 100644
--- a/testlabel.lua
+++ b/testlabel.lua
@@ -2,6 +2,15 @@ local m = require 'lpeglabel'
 
 local p, r, l, s, serror
 
+local function checkeqlab (x, ...)
+  y = { ... }
+  assert(type(x) == "table")
+  assert(#x == #y)
+  for i = 1, 3 do
+    assert(x[i] == y[i])
+  end
+end
+
 -- throws a label 
 p = m.T(1)
 s = "abc"
@@ -538,4 +547,31 @@ A := a;]]
 assert(g:match(s) == terror['undefined']) 
 
 
+print("+")
+
+
+-- test recovery operator
+p = m.Rec("a", "b") 
+assert(p:match("a") == 2)
+assert(p:match("b") == 2)
+checkeqlab({nil, 0, "c"}, p:match("c"))
+
+p = m.Rec("a", "b", 3) 
+assert(p:match("a") == 2)
+checkeqlab({nil, 0, "b"}, p:match("b"))
+checkeqlab({nil, 0, "c"}, p:match("c"))
+
+p = m.Rec(m.T(3), "b") 
+checkeqlab({nil, 3, "a"}, p:match("a"))
+checkeqlab({nil, 3, "b"}, p:match("b"))
+
+p = m.Rec(m.T(3), "b", 3) 
+p:pcode()
+checkeqlab({nil, 0, "a"}, p:match("a"))
+assert(p:match("b") == 2)
+
+
 print("OK")
+
+
+