aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorsergio <sqmedeiros@gmail.com>2016-07-22 15:13:58 -0300
committersergio <sqmedeiros@gmail.com>2016-07-22 15:13:58 -0300
commitabb26cdfd3d44e7b10ec001f2afb980616c71573 (patch)
tree86a5caade53be9dc1d3b5cefb3d212f9096842b4
parent28a44f01cb7a75068b75a99c0badb3abdaf7047a (diff)
downloadlpeglabel-abb26cdfd3d44e7b10ec001f2afb980616c71573.tar.gz
lpeglabel-abb26cdfd3d44e7b10ec001f2afb980616c71573.tar.bz2
lpeglabel-abb26cdfd3d44e7b10ec001f2afb980616c71573.zip
Changing the semantics of labels to recovery/resume (ILabChoice does not work)
-rw-r--r--lpcode.c7
-rw-r--r--lptypes.h2
-rw-r--r--lpvm.c56
-rw-r--r--testlabel.lua54
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,
725static void coderecovery (CompileState *compst, TTree *p1, TTree *p2, int opt, 725static void coderecovery (CompileState *compst, TTree *p1, TTree *p2, int opt,
726 const Charset *fl, const byte *cs) { 726 const Charset *fl, const byte *cs) {
727 int emptyp2 = (p2->tag == TTrue); 727 int emptyp2 = (p2->tag == TTrue);
728 int pcommit; 728 int pjmp;
729 int test = NOINST; 729 int test = NOINST;
730 int precovery = addoffsetinst(compst, IRecov); 730 int precovery = addoffsetinst(compst, IRecov);
731 addcharset(compst, cs); 731 addcharset(compst, cs);
732 codegen(compst, p1, emptyp2, test, fullset); 732 codegen(compst, p1, emptyp2, test, fullset);
733 pcommit = addoffsetinst(compst, ICommit); 733 pjmp = addoffsetinst(compst, IJmp);
734 jumptohere(compst, precovery); 734 jumptohere(compst, precovery);
735 jumptohere(compst, test); 735 jumptohere(compst, test);
736 codegen(compst, p2, opt, NOINST, fl); 736 codegen(compst, p2, opt, NOINST, fl);
737 jumptohere(compst, pcommit); 737 addinstruction(compst, IRet, 0);
738 jumptohere(compst, pjmp);
738} 739}
739/* labeled failure end */ 740/* labeled failure end */
740 741
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;
161#define IDXLFAIL 0 161#define IDXLFAIL 0
162 162
163#define LFAIL 0 163#define LFAIL 0
164
165#define MAXRECOVERY 200
164/* labeled failure end */ 166/* labeled failure end */
165 167
166#endif 168#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 {
48} Stack; 48} Stack;
49 49
50 50
51typedef struct RecStack {
52 const Labelset *ls; /* labeled failure */
53 const Instruction *prec; /* recovery instruction */
54} RecStack;
55
56
51#define getstackbase(L, ptop) ((Stack *)lua_touserdata(L, stackidx(ptop))) 57#define getstackbase(L, ptop) ((Stack *)lua_touserdata(L, stackidx(ptop)))
52 58
53 59
@@ -156,15 +162,20 @@ static int removedyncap (lua_State *L, Capture *capture,
156const char *match (lua_State *L, const char *o, const char *s, const char *e, 162const char *match (lua_State *L, const char *o, const char *s, const char *e,
157 Instruction *op, Capture *capture, int ptop, byte *labelf, const char **sfail) { /* labeled failure */ 163 Instruction *op, Capture *capture, int ptop, byte *labelf, const char **sfail) { /* labeled failure */
158 Stack stackbase[INITBACK]; 164 Stack stackbase[INITBACK];
165 RecStack recbase[MAXRECOVERY];
159 Stack *stacklimit = stackbase + INITBACK; 166 Stack *stacklimit = stackbase + INITBACK;
160 Stack *stack = stackbase; /* point to first empty slot in stack */ 167 Stack *stack = stackbase; /* point to first empty slot in stack */
161 int capsize = INITCAPSIZE; 168 RecStack *reclimit = recbase + MAXRECOVERY;
169 RecStack *recstack = recbase;
170 int capsize = INITCAPSIZE;
162 int captop = 0; /* point to first empty slot in captures */ 171 int captop = 0; /* point to first empty slot in captures */
163 int ndyncap = 0; /* number of dynamic captures (in Lua stack) */ 172 int ndyncap = 0; /* number of dynamic captures (in Lua stack) */
164 const Instruction *p = op; /* current instruction */ 173 const Instruction *p = op; /* current instruction */
174 const Instruction *pk = NULL; /* resume instruction */
165 Labelset lsfail; 175 Labelset lsfail;
166 setlabelfail(&lsfail); 176 setlabelfail(&lsfail);
167 stack->p = &giveup; stack->s = s; stack->ls = &lsfail; stack->caplevel = 0; stack++; /* labeled failure */ 177 stack->p = &giveup; stack->s = s; stack->ls = &lsfail; stack->caplevel = 0; stack++; /* labeled failure */
178 recstack->prec = &giveup; recstack->ls = &lsfail; recstack++; /* labeled failure */
168 lua_pushlightuserdata(L, stackbase); 179 lua_pushlightuserdata(L, stackbase);
169 for (;;) { 180 for (;;) {
170#if defined(DEBUG) 181#if defined(DEBUG)
@@ -194,6 +205,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
194 if (s < e) { p++; s++; } 205 if (s < e) { p++; s++; }
195 else { 206 else {
196 *labelf = LFAIL; /* labeled failure */ 207 *labelf = LFAIL; /* labeled failure */
208 pk = p + 1;
197 *sfail = s; 209 *sfail = s;
198 goto fail; 210 goto fail;
199 } 211 }
@@ -208,6 +220,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
208 if ((byte)*s == p->i.aux && s < e) { p++; s++; } 220 if ((byte)*s == p->i.aux && s < e) { p++; s++; }
209 else { 221 else {
210 *labelf = LFAIL; /* labeled failure */ 222 *labelf = LFAIL; /* labeled failure */
223 pk = p + 1;
211 *sfail = s; 224 *sfail = s;
212 goto fail; 225 goto fail;
213 } 226 }
@@ -224,6 +237,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
224 { p += CHARSETINSTSIZE; s++; } 237 { p += CHARSETINSTSIZE; s++; }
225 else { 238 else {
226 *labelf = LFAIL; /* labeled failure */ 239 *labelf = LFAIL; /* labeled failure */
240 pk = p + CHARSETINSTSIZE;
227 *sfail = s; 241 *sfail = s;
228 goto fail; 242 goto fail;
229 } 243 }
@@ -240,6 +254,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
240 int n = p->i.aux; 254 int n = p->i.aux;
241 if (n > s - o) { 255 if (n > s - o) {
242 *labelf = LFAIL; /* labeled failure */ 256 *labelf = LFAIL; /* labeled failure */
257 pk = p + 1;
243 *sfail = s; 258 *sfail = s;
244 goto fail; 259 goto fail;
245 } 260 }
@@ -281,17 +296,14 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
281 continue; 296 continue;
282 } 297 }
283 case IRecov: { /* labeled failure */ 298 case IRecov: { /* labeled failure */
284 if (stack == stacklimit) 299 if (recstack == reclimit)
285 stack = doublestack(L, &stacklimit, ptop); 300 luaL_error(L, "recovery stack overflow (current limit is %d)", MAXRECOVERY);
286 stack->p = p + getoffset(p); 301 recstack->prec = p + getoffset(p);
287 stack->s = NULL; 302 recstack->ls = (const Labelset *) ((p + 2)->buff);
288 stack->ls = (const Labelset *) ((p + 2)->buff); 303 recstack++;
289 stack->caplevel = captop;
290 stack++;
291 p += (CHARSETINSTSIZE - 1) + 2; 304 p += (CHARSETINSTSIZE - 1) + 2;
292 continue; 305 continue;
293 } 306 }
294
295 case ICall: { 307 case ICall: {
296 if (stack == stacklimit) 308 if (stack == stacklimit)
297 stack = doublestack(L, &stacklimit, ptop); 309 stack = doublestack(L, &stacklimit, ptop);
@@ -303,8 +315,8 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
303 continue; 315 continue;
304 } 316 }
305 case ICommit: { 317 case ICommit: {
306 assert(stack > getstackbase(L, ptop) && (stack - 1)->ls != NULL); /* labeled failure */ 318 /*assert(stack > getstackbase(L, ptop) && (stack - 1)->ls != NULL); */ /* labeled failure */
307 /* assert((stack - 1)->s != NULL); labeled failure: IRecov does not push s onto the stack */ 319 assert((stack - 1)->s != NULL); /* labeled failure: IRecov does not push s onto the stack */
308 stack--; 320 stack--;
309 p += getoffset(p); 321 p += getoffset(p);
310 continue; 322 continue;
@@ -325,8 +337,24 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
325 } 337 }
326 case IThrow: { /* labeled failure */ 338 case IThrow: { /* labeled failure */
327 *labelf = p->i.aux; 339 *labelf = p->i.aux;
340 while ((--recstack)->prec != &giveup) {
341 if (testlabel(recstack->ls->cs, *labelf)) {
342 /* Push resume/call frame */
343 stack->s = NULL;
344 stack->p = p + 1; /* resume to instruction after IThrow */
345 stack->ls = NULL;
346 stack++;
347 p = recstack->prec;
348 break;
349 }
350 }
351 if (recstack->prec != &giveup)
352 continue;
353 p = recstack->prec; /* p = IGiveup */
354 stack = getstackbase(L, ptop);
328 *sfail = s; 355 *sfail = s;
329 goto fail; 356 /*goto fail;*/
357 continue;
330 } 358 }
331 case IFailTwice: 359 case IFailTwice:
332 assert(stack > getstackbase(L, ptop)); 360 assert(stack > getstackbase(L, ptop));
@@ -334,6 +362,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
334 /* go through */ 362 /* go through */
335 case IFail: 363 case IFail:
336 *labelf = LFAIL; /* labeled failure */ 364 *labelf = LFAIL; /* labeled failure */
365 pk = NULL;
337 *sfail = s; 366 *sfail = s;
338 fail: { /* pattern failed: try to backtrack */ 367 fail: { /* pattern failed: try to backtrack */
339 const Labelset *auxlab = NULL; 368 const Labelset *auxlab = NULL;
@@ -343,7 +372,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
343 } while (auxlab == NULL || (stack->p != &giveup && !testlabel(stack->ls->cs, *labelf))); 372 } while (auxlab == NULL || (stack->p != &giveup && !testlabel(stack->ls->cs, *labelf)));
344 if (stack->p == &giveup || stack->s != NULL) { /* labeled failure */ 373 if (stack->p == &giveup || stack->s != NULL) { /* labeled failure */
345 s = stack->s; 374 s = stack->s;
346 } 375 }
347 if (ndyncap > 0) /* is there matchtime captures? */ 376 if (ndyncap > 0) /* is there matchtime captures? */
348 ndyncap -= removedyncap(L, capture, stack->caplevel, captop); 377 ndyncap -= removedyncap(L, capture, stack->caplevel, captop);
349 captop = stack->caplevel; 378 captop = stack->caplevel;
@@ -362,6 +391,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
362 if (res == -1) { /* fail? */ 391 if (res == -1) { /* fail? */
363 *labelf = LFAIL; /* labeled failure */ 392 *labelf = LFAIL; /* labeled failure */
364 *sfail = (const char *) s; /* TODO: ??? */ 393 *sfail = (const char *) s; /* TODO: ??? */
394 pk = NULL;
365 goto fail; 395 goto fail;
366 } 396 }
367 s = o + res; /* else update current position */ 397 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{
32r, l, serror = g:match(s) 32r, l, serror = g:match(s)
33assert(r == nil and l == 1 and serror == "abc") 33assert(r == nil and l == 1 and serror == "abc")
34 34
35--[==[ TODO: labeled choice does not work anymore
35-- throws a label that is not caught by labeled choice 36-- throws a label that is not caught by labeled choice
36p = m.Lc(m.T(2), m.P"a", 1, 3) 37p = m.Lc(m.T(2), m.P"a", 1, 3)
37r, l, serror = p:match(s) 38r, l, serror = p:match(s)
@@ -188,6 +189,7 @@ assert(p:match("abc") == 2)
188 189
189r, l, serror = p:match("") 190r, l, serror = p:match("")
190assert(r == nil and l == 0 and serror == "") 191assert(r == nil and l == 0 and serror == "")
192]==]
191 193
192-- testing the limit of labels 194-- testing the limit of labels
193p = m.T(0) 195p = m.T(0)
@@ -209,6 +211,7 @@ assert(r == false)
209 211
210print("+") 212print("+")
211 213
214--[==[ TODO: labeled choice does not work anymore
212--[[ grammar based on Figure 8 of paper submitted to SCP 215--[[ grammar based on Figure 8 of paper submitted to SCP
213S -> S0 /{1} ID /{2} ID '=' Exp /{3} 'unsigned'* 'int' ID /{4} 'unsigned'* ID ID / %error 216S -> S0 /{1} ID /{2} ID '=' Exp /{3} 'unsigned'* 'int' ID /{4} 'unsigned'* ID ID / %error
214S0 -> ID S1 / 'unsigned' S2 / 'int' %3 217S0 -> ID S1 / 'unsigned' S2 / 'int' %3
@@ -548,12 +551,12 @@ assert(g:match(s) == terror['undefined'])
548 551
549 552
550print("+") 553print("+")
551 554]==]
552 555
553-- test recovery operator 556-- test recovery operator
554p = m.Rec("a", "b") 557p = m.Rec("a", "b")
555assert(p:match("a") == 2) 558assert(p:match("a") == 2)
556assert(p:match("b") == 2) 559--assert(p:match("b") == 2)
557checkeqlab({nil, 0, "c"}, p:match("c")) 560checkeqlab({nil, 0, "c"}, p:match("c"))
558 561
559p = m.Rec("a", "b", 3) 562p = m.Rec("a", "b", 3)
@@ -583,13 +586,44 @@ g = m.P{
583 586
584assert(g:match("abc") == 4) 587assert(g:match("abc") == 4)
585assert(g:match("aabc") == 5) 588assert(g:match("aabc") == 5)
586assert(g:match("aadc") == 5) 589--assert(g:match("aadc") == 5) --old semantics
587assert(g:match("bc") == 3) 590checkeqlab({nil, 0, "dc"}, g:match("aadc")) --new semantics
591assert(g:match("bc") == 3) -- new semantics
588checkeqlab({nil, 0, "bc"}, g:match("bbc")) 592checkeqlab({nil, 0, "bc"}, g:match("bbc"))
589assert(g:match("xxc") == 4) 593--assert(g:match("xxc") == 4) old semantics
590assert(g:match("c") == 2) 594checkeqlab({nil, 0, "xxc"}, g:match("xxc")) --new semantics
591checkeqlab({nil, 0, ""}, g:match("fail")) 595--assert(g:match("c") == 2) --old semantics
592checkeqlab({nil, 0, ""}, g:match("aaxx")) 596checkeqlab({nil, 0, "c"}, g:match("c")) --new semantics
597--checkeqlab({nil, 0, ""}, g:match("fail")) --old semantics
598checkeqlab({nil, 0, "fail"}, g:match("fail")) --new semantics
599--checkeqlab({nil, 0, ""}, g:match("aaxx")) --old semantics
600checkeqlab({nil, 0, "xx"}, g:match("aaxx")) --new semantics
601
602
603--[[
604S -> (A //{0} (!c .)*) C
605A -> a*b / ^{0}
606C -> c+
607]]
608g = m.P{
609 "S",
610 S = m.Rec(m.V"A", (-m.P"c" * m.P(1))^0) * m.V"C",
611 A = m.P"a"^0 * m.P"b" + m.T(0),
612 C = m.P"c"^1,
613}
614
615assert(g:match("abc") == 4)
616assert(g:match("aabc") == 5)
617assert(g:match("aadc") == 5) --updated
618assert(g:match("bc") == 3) -- new semantics
619checkeqlab({nil, 0, "bc"}, g:match("bbc"))
620assert(g:match("xxc") == 4)
621assert(g:match("c") == 2) --old semantics updated
622checkeqlab({nil, 0, ""}, g:match("fail")) --old semantics updated
623checkeqlab({nil, 0, ""}, g:match("aaxx")) --old semantics updated
624
625
626
593 627
594--[[ 628--[[
595S -> (A //{99} (!c .)*) C 629S -> (A //{99} (!c .)*) C
@@ -726,7 +760,5 @@ print(eval "(1+1-1*(2/2+)-():")
726--> syntax error: extra characters found after the expression (at index 760--> syntax error: extra characters found after the expression (at index
727 761
728 762
729
730
731print("OK") 763print("OK")
732 764