From a9c5a38994074d2c9c5da4cf081c4ca9fa8b3271 Mon Sep 17 00:00:00 2001 From: Sergio Queiroz Date: Fri, 9 Sep 2016 16:26:44 -0300 Subject: Updating implementation of Recovery to follow Fabio's idea. Not compatible with labeled ordered choice --- lpcode.c | 6 ++--- lptree.c | 6 ++--- lptypes.h | 2 -- lpvm.c | 77 +++++++++++++++++++++++++++-------------------------------- makefile | 14 +++++------ test.lua | 2 +- testlabel.lua | 5 ++-- 7 files changed, 52 insertions(+), 60 deletions(-) diff --git a/lpcode.c b/lpcode.c index f7246da..d5f8d68 100644 --- a/lpcode.c +++ b/lpcode.c @@ -725,17 +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 pjmp; + int pcommit; int test = NOINST; int precovery = addoffsetinst(compst, IRecov); addcharset(compst, cs); codegen(compst, p1, emptyp2, test, fullset); - pjmp = addoffsetinst(compst, IJmp); + pcommit = addoffsetinst(compst, ICommit); jumptohere(compst, precovery); jumptohere(compst, test); codegen(compst, p2, opt, NOINST, fl); addinstruction(compst, IRet, 0); - jumptohere(compst, pjmp); + jumptohere(compst, pcommit); } /* labeled failure end */ diff --git a/lptree.c b/lptree.c index 2044a5c..700398b 100644 --- a/lptree.c +++ b/lptree.c @@ -748,7 +748,7 @@ 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); + /*setlabel(treelabelset(tree), LFAIL); recovery does not catch regular fail */ } else { int i; for (i = 3; i <= n; i++) { @@ -1361,8 +1361,8 @@ static struct luaL_Reg metareg[] = { }; -int luaopen_lpeglabel (lua_State *L); /* labeled failure */ -int luaopen_lpeglabel (lua_State *L) { /* labeled failure */ +int luaopen_lpeglabelrec (lua_State *L); /* labeled failure */ +int luaopen_lpeglabelrec (lua_State *L) { /* labeled failure */ luaL_newmetatable(L, PATTERN_T); lua_pushnumber(L, MAXBACK); /* initialize maximum backtracking */ lua_setfield(L, LUA_REGISTRYINDEX, MAXSTACKIDX); diff --git a/lptypes.h b/lptypes.h index 85339a0..dc4ada6 100644 --- a/lptypes.h +++ b/lptypes.h @@ -161,8 +161,6 @@ 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 917a626..44975a1 100644 --- a/lpvm.c +++ b/lpvm.c @@ -48,12 +48,6 @@ 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))) @@ -162,25 +156,22 @@ 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 */ - RecStack *reclimit = recbase + MAXRECOVERY; - RecStack *recstack = recbase; - int capsize = INITCAPSIZE; + 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) + printinst(op, p); printf("s: |%s| stck:%d, dyncaps:%d, caps:%d ", s, stack - getstackbase(L, ptop), ndyncap, captop); - printinst(op, p); printcaplist(capture, capture + captop); #endif assert(stackidx(ptop) + ndyncap == lua_gettop(L) && ndyncap <= captop); @@ -204,6 +195,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; } @@ -218,6 +210,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; } @@ -234,6 +227,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; } @@ -250,6 +244,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; } @@ -291,11 +286,13 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e, continue; } case IRecov: { /* labeled failure */ - 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++; + 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; } @@ -310,8 +307,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; @@ -332,24 +329,9 @@ 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); + pk = p + 1; *sfail = s; - /*goto fail;*/ - continue; + goto fail; } case IFailTwice: assert(stack > getstackbase(L, ptop)); @@ -357,20 +339,30 @@ 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; + Stack *pstack = stack; do { /* remove pending calls */ - assert(stack > getstackbase(L, ptop)); - auxlab = (--stack)->ls; - } while (auxlab == NULL || (stack->p != &giveup && !testlabel(stack->ls->cs, *labelf))); - if (stack->p == &giveup || stack->s != NULL) { /* labeled failure */ + assert(pstack > getstackbase(L, ptop)); + auxlab = (--pstack)->ls; + } while (auxlab == NULL || (pstack->p != &giveup && labelf != LFAIL && !testlabel(pstack->ls->cs, *labelf))); + if (pstack->p == &giveup || pstack->s != NULL) { /* labeled failure: giveup or backtrack frame */ + stack = pstack; s = stack->s; - } + } else { /* labeled failure: recovery frame */ + if (stack == stacklimit) + stack = doublestack(L, &stacklimit, ptop); + stack->s = NULL; + stack->p = pk; /* save return address */ + stack->ls = NULL; + stack++; + } if (ndyncap > 0) /* is there matchtime captures? */ ndyncap -= removedyncap(L, capture, stack->caplevel, captop); captop = stack->caplevel; - p = stack->p; + p = pstack->p; continue; } case ICloseRunTime: { @@ -385,6 +377,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/makefile b/makefile index 5728b38..414651e 100644 --- a/makefile +++ b/makefile @@ -1,4 +1,4 @@ -LIBNAME = lpeglabel +LIBNAME = lpeglabelrec LUADIR = ../lua/ COPT = -O2 @@ -29,24 +29,24 @@ FILES = lpvm.o lpcap.o lptree.o lpcode.o lpprint.o # For Linux linux: - make lpeglabel.so "DLLFLAGS = -shared -fPIC" + make lpeglabelrec.so "DLLFLAGS = -shared -fPIC" # For Mac OS macosx: - make lpeglabel.so "DLLFLAGS = -bundle -undefined dynamic_lookup" + make lpeglabelrec.so "DLLFLAGS = -bundle -undefined dynamic_lookup" -lpeglabel.so: $(FILES) - env $(CC) $(DLLFLAGS) $(FILES) -o lpeglabel.so +lpeglabelrec.so: $(FILES) + env $(CC) $(DLLFLAGS) $(FILES) -o lpeglabelrec.so $(FILES): makefile -test: test.lua testlabel.lua testerrors.lua relabel.lua lpeglabel.so +test: test.lua testlabel.lua testerrors.lua relabel.lua lpeglabelrec.so lua test.lua lua testlabel.lua lua testerrors.lua clean: - rm -f $(FILES) lpeglabel.so + rm -f $(FILES) lpeglabelrec.so lpcap.o: lpcap.c lpcap.h lptypes.h diff --git a/test.lua b/test.lua index d5922ac..fc2b607 100755 --- a/test.lua +++ b/test.lua @@ -4,7 +4,7 @@ -- require"strict" -- just to be pedantic -local m = require"lpeglabel" +local m = require"lpeglabelrec" -- for general use diff --git a/testlabel.lua b/testlabel.lua index cbe623c..8cfb671 100644 --- a/testlabel.lua +++ b/testlabel.lua @@ -1,4 +1,4 @@ -local m = require 'lpeglabel' +local m = require 'lpeglabelrec' local p, r, l, s, serror @@ -557,6 +557,7 @@ print("+") p = m.Rec("a", "b") assert(p:match("a") == 2) --assert(p:match("b") == 2) +checkeqlab({nil, 0, "b"}, p:match("b")) checkeqlab({nil, 0, "c"}, p:match("c")) p = m.Rec("a", "b", 3) @@ -607,7 +608,7 @@ C -> c+ ]] g = m.P{ "S", - S = m.Rec(m.V"A", (-m.P"c" * m.P(1))^0) * m.V"C", + S = m.Rec(m.V"A", (-m.P"c" * m.P(1))^0, 0) * m.V"C", --explicitly put 0 in Rec A = m.P"a"^0 * m.P"b" + m.T(0), C = m.P"c"^1, } -- cgit v1.2.3-55-g6feb