From 261e41117c2ec8d50b9aff1ecaaa701d2af5c211 Mon Sep 17 00:00:00 2001 From: Sérgio Queiroz Date: Thu, 28 Dec 2017 15:45:29 -0300 Subject: When matching a predicate, the position of the farthest failure may not be the subject position where the predicate started to match --- lpcode.c | 2 -- lptypes.h | 4 +--- lpvm.c | 47 ++++++++++++++++++----------------------------- testlabel.lua | 33 ++++++++++++++++++++++++++++++--- 4 files changed, 49 insertions(+), 37 deletions(-) diff --git a/lpcode.c b/lpcode.c index ef357bc..c5869e8 100644 --- a/lpcode.c +++ b/lpcode.c @@ -759,7 +759,6 @@ static void codeand (CompileState *compst, TTree *tree, int tt) { else */{ /* default: Choice L1; p1; BackCommit L2; L1: Fail; L2: */ int pcommit; 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); @@ -862,7 +861,6 @@ static void codenot (CompileState *compst, TTree *tree) { else { /* test(fail(p))-> L1; choice L1;

; failtwice; L1: */ 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/lptypes.h b/lptypes.h index d523e27..6158be1 100644 --- a/lptypes.h +++ b/lptypes.h @@ -150,11 +150,9 @@ 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 +#define INPRED 1 /* labeled failure end */ #endif diff --git a/lpvm.c b/lpvm.c index 1eb7944..0c70766 100644 --- a/lpvm.c +++ b/lpvm.c @@ -18,11 +18,11 @@ /* initial size for call/backtrack stack */ #if !defined(INITBACK) -#define INITBACK MAXBACK +#define INITBACK MAXBACK #endif -#define getoffset(p) (((p) + 1)->offset) +#define getoffset(p) (((p) + 1)->offset) static const Instruction giveup = {{IGiveup, 0, 0}}; @@ -43,7 +43,7 @@ typedef struct Stack { } Stack; -#define getstackbase(L, ptop) ((Stack *)lua_touserdata(L, stackidx(ptop))) +#define getstackbase(L, ptop) ((Stack *)lua_touserdata(L, stackidx(ptop))) /* @@ -159,7 +159,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e, const Instruction *p = op; /* current instruction */ 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 */ + *sfail = s; /* labeled failure */ lua_pushlightuserdata(L, stackbase); for (;;) { #if defined(DEBUG) @@ -170,7 +170,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e, printinst(op, p); #endif assert(stackidx(ptop) + ndyncap == lua_gettop(L) && ndyncap <= captop); - assert(insidepred == NOTPRED || insidepred == ANDPRED || insidepred == OUTPRED); + assert(insidepred == INPRED || insidepred == OUTPRED); switch ((Opcode)p->i.code) { case IEnd: { assert(stack == getstackbase(L, ptop) + 1); @@ -191,8 +191,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 */ - if (insidepred == OUTPRED) - updatefarthest(*sfail, s); /*labeled failure */ + updatefarthest(*sfail, s); /*labeled failure */ goto fail; } continue; @@ -206,8 +205,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 */ - if (insidepred == OUTPRED) - updatefarthest(*sfail, s); /*labeled failure */ + updatefarthest(*sfail, s); /*labeled failure */ goto fail; } continue; @@ -223,8 +221,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e, { p += CHARSETINSTSIZE; s++; } else { *labelf = LFAIL; /* labeled failure */ - if (insidepred == OUTPRED) - updatefarthest(*sfail, s); /*labeled failure */ + updatefarthest(*sfail, s); /*labeled failure */ goto fail; } continue; @@ -240,8 +237,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 */ - if (insidepred == OUTPRED) - updatefarthest(*sfail, s); /*labeled failure */ + updatefarthest(*sfail, s); /*labeled failure */ goto fail; } s -= n; p++; @@ -280,7 +276,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e, stack->labenv = insidepred; stack->predchoice = 1; stack++; - insidepred = p->i.aux; + insidepred = INPRED; p += 2; continue; } @@ -318,11 +314,8 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e, case IThrow: { /* labeled failure */ if (insidepred == OUTPRED) { *labelf = (p+1)->i.key; - if (*labelf == LFAIL) - luaL_error(L, "labelf is %d", *labelf); stack = getstackbase(L, ptop); stack++; - *sfail = s; } else { while (!(stack-1)->predchoice) { @@ -330,21 +323,19 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e, } *labelf = LFAIL; } + *sfail = s; goto fail; } case IThrowRec: { /* labeled failure */ if (insidepred == OUTPRED) { *labelf = (p+2)->i.key; - if (*labelf == LFAIL) - luaL_error(L, "labelf is %d", *labelf); - *sfail = s; + *sfail = s; if (stack == stacklimit) stack = doublestack(L, &stacklimit, ptop); stack->s = NULL; stack->p = p + 3; stack->caplevel = captop; stack++; - *sfail = s; p += getoffset(p); continue; } else { @@ -352,6 +343,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e, --stack; } *labelf = LFAIL; + *sfail = s; } goto fail; } @@ -361,8 +353,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e, /* go through */ case IFail: *labelf = LFAIL; /* labeled failure */ - if (insidepred == OUTPRED) - updatefarthest(*sfail, s); /*labeled failure */ + updatefarthest(*sfail, s); /*labeled failure */ fail: { /* pattern failed: try to backtrack */ do { /* remove pending calls */ assert(stack > getstackbase(L, ptop)); @@ -371,9 +362,8 @@ 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; - assert(((insidepred == ANDPRED || insidepred == NOTPRED) && (stack->labenv == OUTPRED)) || insidepred == stack->labenv - || (insidepred != OUTPRED && stack->labenv != OUTPRED)); - insidepred = stack->labenv; + assert((insidepred == INPRED && stack->labenv == OUTPRED) || insidepred == stack->labenv); + insidepred = stack->labenv; /* labeled failure */ p = stack->p; #if defined(DEBUG) printf("**FAIL**\n"); @@ -391,9 +381,8 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e, fr -= rem; /* 'rem' items were popped from Lua stack */ res = resdyncaptures(L, fr, s - o, e - o); /* get result */ if (res == -1) { /* fail? */ - *labelf = LFAIL; /* labeled failure */ - if (insidepred == OUTPRED) - updatefarthest(*sfail, s); /*labeled failure */ + *labelf = LFAIL; /* labeled failure */ + updatefarthest(*sfail, s); /*labeled failure */ goto fail; } s = o + res; /* else update current position */ diff --git a/testlabel.lua b/testlabel.lua index 7461206..d60bb54 100644 --- a/testlabel.lua +++ b/testlabel.lua @@ -237,12 +237,39 @@ 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) +assert(r == nil and l == 'fail' and poserr == 2) p = #(m.P"a" * m.P'a') r, l, poserr = p:match("abc") -assert(r == nil and l == 'fail' and poserr == 1) +assert(r == nil and l == 'fail' and poserr == 2) +p = m.P'a' * #m.P('a') +r, l, poserr = p:match("abc") +assert(r == nil and l == 'fail' and poserr == 2) + +p = m.P'a' * #m.P('ba') +r, l, poserr = p:match("abc") +assert(r == nil and l == 'fail' and poserr == 3) + +p = m.P'a' * -m.P('b') +r, l, poserr = p:match("abc") +assert(r == nil and l == 'fail' and poserr == 2) + +p = m.P'a' * -m.P('bc') +r, l, poserr = p:match("abc") +assert(r == nil and l == 'fail' and poserr == 4) + +p = m.P'a' * #m.T('a') +r, l, poserr = p:match("abc") +assert(r == nil and l == 'fail' and poserr == 2) + +p = m.P'a' * #(m.P'b' * m.T('a')) +r, l, poserr = p:match("abc") +assert(r == nil and l == 'fail' and poserr == 3) + +p = m.P'a' * (m.P'b' * m.T('a')) +r, l, poserr = p:match("abc") +assert(r == nil and l == 'a' and poserr == 3) p = -(-m.T(1)) r, l, poserr = p:match("bbc") @@ -295,7 +322,7 @@ p = m.P{ ["22"] = m.T(15) } r, l, poserr = p:match("abc") -assert(r == nil and l == 'fail' and poserr == 1) +assert(r == nil and l == 'fail' and poserr == 2) -- tests related to repetition -- cgit v1.2.3-55-g6feb