aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--lpcode.c43
-rw-r--r--lpprint.c9
-rw-r--r--lptree.c94
-rw-r--r--lptree.h9
-rw-r--r--lptypes.h30
-rw-r--r--lpvm.c59
-rw-r--r--lpvm.h1
-rw-r--r--makefile4
-rwxr-xr-xtest.lua1
-rw-r--r--testlabel.lua3
10 files changed, 146 insertions, 107 deletions
diff --git a/lpcode.c b/lpcode.c
index 2a85e02..9fa8867 100644
--- a/lpcode.c
+++ b/lpcode.c
@@ -11,7 +11,7 @@
11 11
12#include "lptypes.h" 12#include "lptypes.h"
13#include "lpcode.h" 13#include "lpcode.h"
14 14#include "lpprint.h" /* labeled failure */
15 15
16/* signals a "no-instruction */ 16/* signals a "no-instruction */
17#define NOINST -1 17#define NOINST -1
@@ -424,10 +424,11 @@ int sizei (const Instruction *i) {
424 case ITestSet: return CHARSETINSTSIZE + 1; 424 case ITestSet: return CHARSETINSTSIZE + 1;
425 case ITestChar: case ITestAny: case IChoice: case IJmp: case ICall: 425 case ITestChar: case ITestAny: case IChoice: case IJmp: case ICall:
426 case IOpenCall: case ICommit: case IPartialCommit: case IBackCommit: 426 case IOpenCall: case ICommit: case IPartialCommit: case IBackCommit:
427 case IThrow: /* labeled failure */
428 return 2; 427 return 2;
428 case IThrow: /* labeled failure */
429 return 1;
429 case ILabChoice: 430 case ILabChoice:
430 return 3; /* labeled failure */ 431 return (CHARSETINSTSIZE - 1) + 2; /* labeled failure */
431 default: return 1; 432 default: return 1;
432 } 433 }
433} 434}
@@ -491,27 +492,24 @@ static int addinstruction (CompileState *compst, Opcode op, int aux) {
491static int addoffsetinst (CompileState *compst, Opcode op) { 492static int addoffsetinst (CompileState *compst, Opcode op) {
492 int i = addinstruction(compst, op, 0); /* instruction */ 493 int i = addinstruction(compst, op, 0); /* instruction */
493 addinstruction(compst, (Opcode)0, 0); /* open space for offset */ 494 addinstruction(compst, (Opcode)0, 0); /* open space for offset */
494 assert(op == ITestSet || sizei(&getinstr(compst, i)) == 2); 495 assert(op == ITestSet || sizei(&getinstr(compst, i)) == 2 || op == ILabChoice); /* labeled failure */
495 return i; 496 return i;
496} 497}
497 498
498/* labeled failure begin */ 499/* labeled failure begin */
499static int addthrowinstruction (CompileState *compst, Labelset ls) { 500static int addthrowinstruction (CompileState *compst, byte lab) {
500 int i = nextinstruction(compst); 501 return addinstruction(compst, IThrow, lab);
501 getinstr(compst, i).i.code = IThrow;
502 i = nextinstruction(compst);
503 getinstr(compst, i).labels = ls;
504 return i;
505} 502}
506 503
507static int addoffsetlabinst (CompileState *compst, Labelset ls) { 504/*static int addoffsetlabinst (CompileState *compst, const byte *cs) {
508 int j; 505 int j;
509 int i = addinstruction(compst, ILabChoice, 0); /* instruction */ 506 int i = addinstruction(compst, ILabChoice, 0);
510 addinstruction(compst, (Opcode)0, 0); /* open space for offset */ 507 addinstruction(compst, (Opcode)0, 0);
511 j = nextinstruction(compst); /* open space for labels */ 508 j = nextinstruction(compst);
512 getinstr(compst, j).labels = ls; 509 getinstr(compst, j).labels = cs;
510
513 return i; 511 return i;
514} 512}*/
515/* labeled failure end */ 513/* labeled failure end */
516 514
517/* 515/*
@@ -718,18 +716,21 @@ static void codechoice (CompileState *compst, TTree *p1, TTree *p2, int opt,
718 716
719/* labeled failure begin */ 717/* labeled failure begin */
720static void codelabchoice (CompileState *compst, TTree *p1, TTree *p2, int opt, 718static void codelabchoice (CompileState *compst, TTree *p1, TTree *p2, int opt,
721 const Charset *fl, Labelset ls) { 719 const Charset *fl, const byte *cs) {
722 int emptyp2 = (p2->tag == TTrue); 720 int emptyp2 = (p2->tag == TTrue);
723 int pcommit; 721 int pcommit;
724 int test = NOINST; 722 int test = NOINST;
725 int pchoice = addoffsetlabinst(compst, ls); 723 /* int pchoice = addoffsetlabinst(compst, cs);*/
724 int pchoice = addoffsetinst(compst, ILabChoice);
725 addcharset(compst, cs);
726 codegen(compst, p1, emptyp2, test, fullset); 726 codegen(compst, p1, emptyp2, test, fullset);
727 pcommit = addoffsetinst(compst, ICommit); 727 pcommit = addoffsetinst(compst, ICommit);
728 jumptohere(compst, pchoice); 728 jumptohere(compst, pchoice);
729 jumptohere(compst, test); 729 jumptohere(compst, test);
730 /*printf("vou codificar codelabchoice %d\n", p2->tag);*/
730 codegen(compst, p2, opt, NOINST, fl); 731 codegen(compst, p2, opt, NOINST, fl);
731 jumptohere(compst, pcommit); 732 jumptohere(compst, pcommit);
732 733 /*printf("fim codelabchoice\n");*/
733} 734}
734/* labeled failure end */ 735/* labeled failure end */
735 736
@@ -961,11 +962,11 @@ static void codegen (CompileState *compst, TTree *tree, int opt, int tt,
961 tree = sib2(tree); goto tailcall; 962 tree = sib2(tree); goto tailcall;
962 } 963 }
963 case TThrow: { /* labeled failure */ 964 case TThrow: { /* labeled failure */
964 addthrowinstruction(compst, tree->labels); 965 addthrowinstruction(compst, (byte) tree->u.label);
965 break; 966 break;
966 } 967 }
967 case TLabChoice: { /* labeled failure */ 968 case TLabChoice: { /* labeled failure */
968 codelabchoice(compst, sib1(tree), sib2(tree), opt, fl, tree->labels); 969 codelabchoice(compst, sib1(tree), sib2(tree), opt, fl, treelabelset(tree));
969 break; 970 break;
970 } 971 }
971 default: assert(0); 972 default: assert(0);
diff --git a/lpprint.c b/lpprint.c
index 99cc3ac..0ca0b0e 100644
--- a/lpprint.c
+++ b/lpprint.c
@@ -109,12 +109,12 @@ void printinst (const Instruction *op, const Instruction *p) {
109 break; 109 break;
110 } 110 }
111 case IThrow: { /* labeled failure */ 111 case IThrow: { /* labeled failure */
112 printf("%d", (p + 1)->labels); 112 printf("%d", p->i.aux);
113 break; 113 break;
114 } 114 }
115 case ILabChoice: { /* labeled failure */ 115 case ILabChoice: { /* labeled failure */
116 printjmp(op, p); 116 printjmp(op, p);
117 printf(" %d", (p + 2)->labels); 117 printcharset((p+2)->buff);
118 break; 118 break;
119 } 119 }
120 default: break; 120 default: break;
@@ -217,14 +217,15 @@ void printtree (TTree *tree, int ident) {
217 break; 217 break;
218 } 218 }
219 case TThrow: { /* labeled failure */ 219 case TThrow: { /* labeled failure */
220 printf(" labels: %d\n", tree->labels); 220 printf(" labels: %d\n", tree->u.label);
221 break; 221 break;
222 } 222 }
223 default: { 223 default: {
224 int sibs = numsiblings[tree->tag]; 224 int sibs = numsiblings[tree->tag];
225 printf("\n"); 225 printf("\n");
226 if (tree->tag == TLabChoice) { /* labeled failure */ 226 if (tree->tag == TLabChoice) { /* labeled failure */
227 printf(" labels: %d\n", tree->labels); 227 printcharset(treelabelset(tree));
228 printf("\n");
228 } 229 }
229 if (sibs >= 1) { 230 if (sibs >= 1) {
230 printtree(sib1(tree), ident + 2); 231 printtree(sib1(tree), ident + 2);
diff --git a/lptree.c b/lptree.c
index 22cf606..b974bbb 100644
--- a/lptree.c
+++ b/lptree.c
@@ -34,7 +34,6 @@ const byte numsiblings[] = {
34 34
35static TTree *newgrammar (lua_State *L, int arg); 35static TTree *newgrammar (lua_State *L, int arg);
36 36
37
38/* 37/*
39** returns a reasonable name for value at index 'idx' on the stack 38** returns a reasonable name for value at index 'idx' on the stack
40*/ 39*/
@@ -63,7 +62,7 @@ static void fixonecall (lua_State *L, int postable, TTree *g, TTree *t) {
63 luaL_error(L, "rule '%s' undefined in given grammar", val2str(L, -1)); 62 luaL_error(L, "rule '%s' undefined in given grammar", val2str(L, -1));
64 } 63 }
65 t->tag = TCall; 64 t->tag = TCall;
66 t->u.ps = n - (t - g); /* position relative to node */ 65 t->u.s.ps = n - (t - g); /* position relative to node */
67 assert(sib2(t)->tag == TRule); 66 assert(sib2(t)->tag == TRule);
68 sib2(t)->key = t->key; 67 sib2(t)->key = t->key;
69} 68}
@@ -80,13 +79,13 @@ static void correctassociativity (TTree *tree) {
80 TTree *t1 = sib1(tree); 79 TTree *t1 = sib1(tree);
81 assert(tree->tag == TChoice || tree->tag == TSeq); 80 assert(tree->tag == TChoice || tree->tag == TSeq);
82 while (t1->tag == tree->tag) { 81 while (t1->tag == tree->tag) {
83 int n1size = tree->u.ps - 1; /* t1 == Op t11 t12 */ 82 int n1size = tree->u.s.ps - 1; /* t1 == Op t11 t12 */
84 int n11size = t1->u.ps - 1; 83 int n11size = t1->u.s.ps - 1;
85 int n12size = n1size - n11size - 1; 84 int n12size = n1size - n11size - 1;
86 memmove(sib1(tree), sib1(t1), n11size * sizeof(TTree)); /* move t11 */ 85 memmove(sib1(tree), sib1(t1), n11size * sizeof(TTree)); /* move t11 */
87 tree->u.ps = n11size + 1; 86 tree->u.s.ps = n11size + 1;
88 sib2(tree)->tag = tree->tag; 87 sib2(tree)->tag = tree->tag;
89 sib2(tree)->u.ps = n12size + 1; 88 sib2(tree)->u.s.ps = n12size + 1;
90 } 89 }
91} 90}
92 91
@@ -375,16 +374,6 @@ static TTree *newleaf (lua_State *L, int tag) {
375} 374}
376 375
377 376
378/* labeled failure begin */
379static TTree *newlabelleaf (lua_State *L, Labelset ls) {
380 TTree *tree = newtree(L, 1);
381 tree->tag = TThrow;
382 tree->labels = ls;
383 return tree;
384}
385/* labeled failure end */
386
387
388static TTree *newcharset (lua_State *L) { 377static TTree *newcharset (lua_State *L) {
389 TTree *tree = newtree(L, bytes2slots(CHARSETSIZE) + 1); 378 TTree *tree = newtree(L, bytes2slots(CHARSETSIZE) + 1);
390 tree->tag = TSet; 379 tree->tag = TSet;
@@ -398,7 +387,7 @@ static TTree *newcharset (lua_State *L) {
398** 'sibsize'); returns position for second sibling 387** 'sibsize'); returns position for second sibling
399*/ 388*/
400static TTree *seqaux (TTree *tree, TTree *sib, int sibsize) { 389static TTree *seqaux (TTree *tree, TTree *sib, int sibsize) {
401 tree->tag = TSeq; tree->u.ps = sibsize + 1; 390 tree->tag = TSeq; tree->u.s.ps = sibsize + 1;
402 memcpy(sib1(tree), sib, sibsize * sizeof(TTree)); 391 memcpy(sib1(tree), sib, sibsize * sizeof(TTree));
403 return sib2(tree); 392 return sib2(tree);
404} 393}
@@ -412,7 +401,7 @@ static TTree *seqaux (TTree *tree, TTree *sib, int sibsize) {
412static void fillseq (TTree *tree, int tag, int n, const char *s) { 401static void fillseq (TTree *tree, int tag, int n, const char *s) {
413 int i; 402 int i;
414 for (i = 0; i < n - 1; i++) { /* initial n-1 copies of Seq tag; Seq ... */ 403 for (i = 0; i < n - 1; i++) { /* initial n-1 copies of Seq tag; Seq ... */
415 tree->tag = TSeq; tree->u.ps = 2; 404 tree->tag = TSeq; tree->u.s.ps = 2;
416 sib1(tree)->tag = tag; 405 sib1(tree)->tag = tag;
417 sib1(tree)->u.n = s ? (byte)s[i] : 0; 406 sib1(tree)->u.n = s ? (byte)s[i] : 0;
418 tree = sib2(tree); 407 tree = sib2(tree);
@@ -519,7 +508,7 @@ static TTree *newroot2sib (lua_State *L, int tag) {
519 TTree *tree2 = getpatt(L, 2, &s2); 508 TTree *tree2 = getpatt(L, 2, &s2);
520 TTree *tree = newtree(L, 1 + s1 + s2); /* create new tree */ 509 TTree *tree = newtree(L, 1 + s1 + s2); /* create new tree */
521 tree->tag = tag; 510 tree->tag = tag;
522 tree->u.ps = 1 + s1; 511 tree->u.s.ps = 1 + s1;
523 memcpy(sib1(tree), tree1, s1 * sizeof(TTree)); 512 memcpy(sib1(tree), tree1, s1 * sizeof(TTree));
524 memcpy(sib2(tree), tree2, s2 * sizeof(TTree)); 513 memcpy(sib2(tree), tree2, s2 * sizeof(TTree));
525 joinktables(L, 1, sib2(tree), 2); 514 joinktables(L, 1, sib2(tree), 2);
@@ -527,6 +516,32 @@ static TTree *newroot2sib (lua_State *L, int tag) {
527} 516}
528 517
529 518
519/* labeled failure begin */
520static TTree *newthrowleaf (lua_State *L, int lab) {
521 TTree *tree = newtree(L, 1);
522 tree->tag = TThrow;
523 tree->u.label = lab;
524 return tree;
525}
526
527static TTree *newlabchoice (lua_State *L) {
528 int s1, s2;
529 TTree *tree1 = getpatt(L, 1, &s1);
530 TTree *tree2 = getpatt(L, 2, &s2);
531 TTree *tree = newtree(L, bytes2slots(LABELSETSIZE) + 1 + s1 + s2); /* create new tree */
532 tree->tag = TLabChoice;
533 tree->u.s.ps = 1 + s1;
534 tree->u.s.plab = 1 + s1 + s2;
535 memcpy(sib1(tree), tree1, s1 * sizeof(TTree));
536 memcpy(sib2(tree), tree2, s2 * sizeof(TTree));
537 loopset(i, treelabelset(tree)[i] = 0);
538 joinktables(L, 1, sib2(tree), 2);
539 return tree;
540}
541/* labeled failure end */
542
543
544
530static int lp_P (lua_State *L) { 545static int lp_P (lua_State *L) {
531 luaL_checkany(L, 1); 546 luaL_checkany(L, 1);
532 getpatt(L, 1, NULL); 547 getpatt(L, 1, NULL);
@@ -548,7 +563,7 @@ static int lp_seq (lua_State *L) {
548 else if (tree1->tag == TTrue) 563 else if (tree1->tag == TTrue)
549 lua_pushvalue(L, 2); /* true . x = x */ 564 lua_pushvalue(L, 2); /* true . x = x */
550 else 565 else
551 newroot2sib(L, TSeq); 566 newroot2sib(L, TSeq);
552 return 1; 567 return 1;
553} 568}
554 569
@@ -599,12 +614,12 @@ static int lp_star (lua_State *L) {
599 /* size = (choice + seq + tree1 + true) * n, but the last has no seq */ 614 /* size = (choice + seq + tree1 + true) * n, but the last has no seq */
600 tree = newtree(L, n * (size1 + 3) - 1); 615 tree = newtree(L, n * (size1 + 3) - 1);
601 for (; n > 1; n--) { /* repeat (n - 1) times */ 616 for (; n > 1; n--) { /* repeat (n - 1) times */
602 tree->tag = TChoice; tree->u.ps = n * (size1 + 3) - 2; 617 tree->tag = TChoice; tree->u.s.ps = n * (size1 + 3) - 2;
603 sib2(tree)->tag = TTrue; 618 sib2(tree)->tag = TTrue;
604 tree = sib1(tree); 619 tree = sib1(tree);
605 tree = seqaux(tree, tree1, size1); 620 tree = seqaux(tree, tree1, size1);
606 } 621 }
607 tree->tag = TChoice; tree->u.ps = size1 + 1; 622 tree->tag = TChoice; tree->u.s.ps = size1 + 1;
608 sib2(tree)->tag = TTrue; 623 sib2(tree)->tag = TTrue;
609 memcpy(sib1(tree), tree1, size1 * sizeof(TTree)); 624 memcpy(sib1(tree), tree1, size1 * sizeof(TTree));
610 } 625 }
@@ -647,7 +662,7 @@ static int lp_sub (lua_State *L) {
647 else { 662 else {
648 TTree *tree = newtree(L, 2 + s1 + s2); 663 TTree *tree = newtree(L, 2 + s1 + s2);
649 tree->tag = TSeq; /* sequence of... */ 664 tree->tag = TSeq; /* sequence of... */
650 tree->u.ps = 2 + s2; 665 tree->u.s.ps = 2 + s2;
651 sib1(tree)->tag = TNot; /* ...not... */ 666 sib1(tree)->tag = TNot; /* ...not... */
652 memcpy(sib1(sib1(tree)), t2, s2 * sizeof(TTree)); /* ...t2 */ 667 memcpy(sib1(sib1(tree)), t2, s2 * sizeof(TTree)); /* ...t2 */
653 memcpy(sib2(tree), t1, s1 * sizeof(TTree)); /* ... and t1 */ 668 memcpy(sib2(tree), t1, s1 * sizeof(TTree)); /* ... and t1 */
@@ -703,18 +718,12 @@ static int lp_behind (lua_State *L) {
703 718
704/* labeled failure begin */ 719/* labeled failure begin */
705/* 720/*
706** Throws a label or a set of labels 721** Throws a label
707*/ 722*/
708static int lp_throw (lua_State *L) { 723static int lp_throw (lua_State *L) {
709 int n = lua_gettop(L); 724 int label = luaL_checkinteger(L, -1);
710 Labelset ls = 0; 725 luaL_argcheck(L, label >= 0 && label < MAXLABELS, -1, "max or min label index exceeded");
711 int i; 726 newthrowleaf(L, label);
712 for (i = 1; i <= n; i++) {
713 long long int d = (long long int)luaL_checkinteger(L, i);
714 luaL_argcheck(L, d >= 0 && d < (long long int)MAXLABELS, i, "invalid label index");
715 setlabel(ls, d);
716 }
717 newlabelleaf(L, ls);
718 return 1; 727 return 1;
719} 728}
720 729
@@ -722,17 +731,14 @@ static int lp_throw (lua_State *L) {
722** labeled choice function 731** labeled choice function
723*/ 732*/
724static int lp_labchoice (lua_State *L) { 733static int lp_labchoice (lua_State *L) {
725 TTree *tree;
726 int n = lua_gettop(L); 734 int n = lua_gettop(L);
735 TTree *tree = newlabchoice(L);
727 int i; 736 int i;
728 Labelset ls = 0;
729 for (i = 3; i <= n; i++) { 737 for (i = 3; i <= n; i++) {
730 long long int d = (long long int)luaL_checkinteger(L, i); 738 int d = luaL_checkinteger(L, i);
731 luaL_argcheck(L, d >= 0 && d < (long long int)MAXLABELS, i, "invalid label index"); 739 luaL_argcheck(L, d >= 0 && d < MAXLABELS, i, "max or min label index exceeded");
732 setlabel(ls, d); 740 setlabel(treelabelset(tree), (byte)d);
733 } 741 }
734 tree = newroot2sib(L, TLabChoice);
735 tree->labels = ls;
736 return 1; 742 return 1;
737} 743}
738/* labeled failure end */ 744/* labeled failure end */
@@ -883,7 +889,7 @@ static int lp_constcapture (lua_State *L) {
883 tree = sib1(tree); 889 tree = sib1(tree);
884 for (i = 1; i <= n - 1; i++) { 890 for (i = 1; i <= n - 1; i++) {
885 tree->tag = TSeq; 891 tree->tag = TSeq;
886 tree->u.ps = 3; /* skip TCapture and its sibling */ 892 tree->u.s.ps = 3; /* skip TCapture and its sibling */
887 auxemptycap(sib1(tree), Cconst); 893 auxemptycap(sib1(tree), Cconst);
888 sib1(tree)->key = addtoktable(L, i); 894 sib1(tree)->key = addtoktable(L, i);
889 tree = sib2(tree); 895 tree = sib2(tree);
@@ -985,7 +991,7 @@ static void buildgrammar (lua_State *L, TTree *grammar, int frule, int n) {
985 nd->tag = TRule; 991 nd->tag = TRule;
986 nd->key = 0; 992 nd->key = 0;
987 nd->cap = i; /* rule number */ 993 nd->cap = i; /* rule number */
988 nd->u.ps = rulesize + 1; /* point to next rule */ 994 nd->u.s.ps = rulesize + 1; /* point to next rule */
989 memcpy(sib1(nd), rn, rulesize * sizeof(TTree)); /* copy rule */ 995 memcpy(sib1(nd), rn, rulesize * sizeof(TTree)); /* copy rule */
990 mergektable(L, ridx, sib1(nd)); /* merge its ktable into new one */ 996 mergektable(L, ridx, sib1(nd)); /* merge its ktable into new one */
991 nd = sib2(nd); /* move to next rule */ 997 nd = sib2(nd); /* move to next rule */
@@ -1213,8 +1219,8 @@ static int lp_match (lua_State *L) {
1213 long long int j = 0; 1219 long long int j = 0;
1214 int n = 1; 1220 int n = 1;
1215 lua_pushnil(L); 1221 lua_pushnil(L);
1216 while (j < (long long int) MAXLABELS) { 1222 while (j < MAXLABELS) {
1217 if (labelf & (1ULL << j)) { 1223 if (testlabel(labelf.cs, j)) {
1218 lua_pushinteger(L, j); 1224 lua_pushinteger(L, j);
1219 n++; 1225 n++;
1220 break; /* Changing the semantics: only one label */ 1226 break; /* Changing the semantics: only one label */
diff --git a/lptree.h b/lptree.h
index 43299a4..5ed67eb 100644
--- a/lptree.h
+++ b/lptree.h
@@ -44,10 +44,13 @@ typedef struct TTree {
44 byte tag; 44 byte tag;
45 byte cap; /* kind of capture (if it is a capture) */ 45 byte cap; /* kind of capture (if it is a capture) */
46 unsigned short key; /* key in ktable for Lua data (0 if no key) */ 46 unsigned short key; /* key in ktable for Lua data (0 if no key) */
47 Labelset labels; /* labeled failure */
48 union { 47 union {
49 int ps; /* occasional second sibling */
50 int n; /* occasional counter */ 48 int n; /* occasional counter */
49 int label; /* labeled failure */
50 struct { /* labeled failure */
51 int ps; /* occasional second sibling */
52 int plab; /* occasional label set */
53 } s; /* labeled failure */
51 } u; 54 } u;
52} TTree; 55} TTree;
53 56
@@ -68,7 +71,7 @@ extern const byte numsiblings[];
68 71
69/* access to siblings */ 72/* access to siblings */
70#define sib1(t) ((t) + 1) 73#define sib1(t) ((t) + 1)
71#define sib2(t) ((t) + (t)->u.ps) 74#define sib2(t) ((t) + (t)->u.s.ps)
72 75
73 76
74 77
diff --git a/lptypes.h b/lptypes.h
index 560ddbb..f61c0ff 100644
--- a/lptypes.h
+++ b/lptypes.h
@@ -110,18 +110,6 @@ typedef struct Charset {
110#define setchar(cs,b) ((cs)[(b) >> 3] |= (1 << ((b) & 7))) 110#define setchar(cs,b) ((cs)[(b) >> 3] |= (1 << ((b) & 7)))
111 111
112 112
113/* labeled failure begin */
114typedef long long int Labelset;
115
116#define MAXLABELS (sizeof(long long int) * 8)
117
118#define LFAIL 1
119
120/* set bit 'b' in set 's' */
121#define setlabel(s, b) ((s) |= (1ULL << (b)))
122/* labeled failure end */
123
124
125/* 113/*
126** in capture instructions, 'kind' of capture and its offset are 114** in capture instructions, 'kind' of capture and its offset are
127** packed in field 'aux', 4 bits for each 115** packed in field 'aux', 4 bits for each
@@ -156,6 +144,24 @@ typedef long long int Labelset;
156 144
157#define testchar(st,c) (((int)(st)[((c) >> 3)] & (1 << ((c) & 7)))) 145#define testchar(st,c) (((int)(st)[((c) >> 3)] & (1 << ((c) & 7))))
158 146
147/* labeled failure begin */
148#define MAXLABELS (UCHAR_MAX + 1)
149
150#define LABELSETSIZE CHARSETSIZE
151
152typedef Charset Labelset;
153
154#define setlabel setchar
155
156#define testlabel testchar
157
158/* access to labelset */
159#define treelabelset(t) ((byte *)((t) + (t)->u.s.plab))
160
161#define IDXLFAIL 0
162
163#define testlabel testchar
164/* labeled failure end */
159 165
160#endif 166#endif
161 167
diff --git a/lpvm.c b/lpvm.c
index c15d543..a57c4b3 100644
--- a/lpvm.c
+++ b/lpvm.c
@@ -26,6 +26,23 @@
26 26
27static const Instruction giveup = {{IGiveup, 0, 0}}; 27static const Instruction giveup = {{IGiveup, 0, 0}};
28 28
29/* labeled failure */
30static void setlabelfail(Labelset *ls) {
31 loopset(i, ls->cs[i] = 0);
32 ls->cs[IDXLFAIL] = 1;
33}
34
35static void clearandsetlabel(Labelset *ls, byte b) {
36 loopset(i, ls->cs[i] = 0);
37 setlabel(ls->cs, b);
38}
39
40
41static int cs_disjoint (const Charset *cs1, const Charset *cs2) {
42 loopset(i, if ((cs1->cs[i] & cs2->cs[i]) != 0) return 0;)
43 return 1;
44}
45/* labeled failure end */
29 46
30/* 47/*
31** {====================================================== 48** {======================================================
@@ -38,7 +55,7 @@ typedef struct Stack {
38 const char *s; /* saved position (or NULL for calls) */ 55 const char *s; /* saved position (or NULL for calls) */
39 const Instruction *p; /* next instruction */ 56 const Instruction *p; /* next instruction */
40 int caplevel; 57 int caplevel;
41 Labelset ls; /* labeled failure */ 58 const Labelset *ls; /* labeled failure */
42} Stack; 59} Stack;
43 60
44 61
@@ -142,6 +159,8 @@ static int removedyncap (lua_State *L, Capture *capture,
142} 159}
143 160
144 161
162
163
145/* 164/*
146** Opcode interpreter 165** Opcode interpreter
147*/ 166*/
@@ -154,15 +173,18 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
154 int captop = 0; /* point to first empty slot in captures */ 173 int captop = 0; /* point to first empty slot in captures */
155 int ndyncap = 0; /* number of dynamic captures (in Lua stack) */ 174 int ndyncap = 0; /* number of dynamic captures (in Lua stack) */
156 const Instruction *p = op; /* current instruction */ 175 const Instruction *p = op; /* current instruction */
176 Labelset lsfail;
177 setlabelfail(&lsfail);
157 stack->p = &giveup; stack->s = s; stack->caplevel = 0; stack++; 178 stack->p = &giveup; stack->s = s; stack->caplevel = 0; stack++;
158 lua_pushlightuserdata(L, stackbase); 179 lua_pushlightuserdata(L, stackbase);
159 for (;;) { 180 /*printf("match: %s\n", s);*/
160#if defined(DEBUG) 181 for (;;) {
161 printf("s: |%s| stck:%d, dyncaps:%d, caps:%d ", 182/*#if defined(DEBUG)*/
183 /* printf("s: |%s| stck:%d, dyncaps:%d, caps:%d ",
162 s, stack - getstackbase(L, ptop), ndyncap, captop); 184 s, stack - getstackbase(L, ptop), ndyncap, captop);
163 printinst(op, p); 185 printinst(op, p);*/
164 printcaplist(capture, capture + captop); 186 /*printcaplist(capture, capture + captop);*/
165#endif 187/*#endif*/
166 assert(stackidx(ptop) + ndyncap == lua_gettop(L) && ndyncap <= captop); 188 assert(stackidx(ptop) + ndyncap == lua_gettop(L) && ndyncap <= captop);
167 switch ((Opcode)p->i.code) { 189 switch ((Opcode)p->i.code) {
168 case IEnd: { 190 case IEnd: {
@@ -183,7 +205,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
183 case IAny: { 205 case IAny: {
184 if (s < e) { p++; s++; } 206 if (s < e) { p++; s++; }
185 else { 207 else {
186 *labelf = LFAIL; /* labeled failure */ 208 setlabelfail(labelf); /* labeled failure */
187 *sfail = s; 209 *sfail = s;
188 goto fail; 210 goto fail;
189 } 211 }
@@ -197,7 +219,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
197 case IChar: { 219 case IChar: {
198 if ((byte)*s == p->i.aux && s < e) { p++; s++; } 220 if ((byte)*s == p->i.aux && s < e) { p++; s++; }
199 else { 221 else {
200 *labelf = LFAIL; /* labeled failure */ 222 setlabelfail(labelf); /* labeled failure */
201 *sfail = s; 223 *sfail = s;
202 goto fail; 224 goto fail;
203 } 225 }
@@ -213,7 +235,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
213 if (testchar((p+1)->buff, c) && s < e) 235 if (testchar((p+1)->buff, c) && s < e)
214 { p += CHARSETINSTSIZE; s++; } 236 { p += CHARSETINSTSIZE; s++; }
215 else { 237 else {
216 *labelf = LFAIL; /* labeled failure */ 238 setlabelfail(labelf); /* labeled failure */
217 *sfail = s; 239 *sfail = s;
218 goto fail; 240 goto fail;
219 } 241 }
@@ -229,7 +251,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
229 case IBehind: { 251 case IBehind: {
230 int n = p->i.aux; 252 int n = p->i.aux;
231 if (n > s - o) { 253 if (n > s - o) {
232 *labelf = LFAIL; /* labeled failure */ 254 setlabelfail(labelf); /* labeled failure */
233 *sfail = s; 255 *sfail = s;
234 goto fail; 256 goto fail;
235 } 257 }
@@ -253,7 +275,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
253 stack = doublestack(L, &stacklimit, ptop); 275 stack = doublestack(L, &stacklimit, ptop);
254 stack->p = p + getoffset(p); 276 stack->p = p + getoffset(p);
255 stack->s = s; 277 stack->s = s;
256 stack->ls = LFAIL; /* labeled failure */ 278 stack->ls = &lsfail; /* labeled failure */
257 stack->caplevel = captop; 279 stack->caplevel = captop;
258 stack++; 280 stack++;
259 p += 2; 281 p += 2;
@@ -264,10 +286,10 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
264 stack = doublestack(L, &stacklimit, ptop); 286 stack = doublestack(L, &stacklimit, ptop);
265 stack->p = p + getoffset(p); 287 stack->p = p + getoffset(p);
266 stack->s = s; 288 stack->s = s;
267 stack->ls = (p + 2)->labels; 289 stack->ls = (const Labelset *) ((p + 2)->buff);
268 stack->caplevel = captop; 290 stack->caplevel = captop;
269 stack++; 291 stack++;
270 p += 3; 292 p += (CHARSETINSTSIZE - 1) + 2;
271 continue; 293 continue;
272 } 294 }
273 case ICall: { 295 case ICall: {
@@ -300,7 +322,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
300 continue; 322 continue;
301 } 323 }
302 case IThrow: { /* labeled failure */ 324 case IThrow: { /* labeled failure */
303 *labelf = (p+1)->labels; 325 clearandsetlabel(labelf, p->i.aux);
304 *sfail = s; 326 *sfail = s;
305 /*printf("s = %s, sfail = %s\n", s, *sfail);*/ 327 /*printf("s = %s, sfail = %s\n", s, *sfail);*/
306 goto fail; 328 goto fail;
@@ -310,13 +332,14 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
310 stack--; 332 stack--;
311 /* go through */ 333 /* go through */
312 case IFail: 334 case IFail:
313 *labelf = LFAIL; /* labeled failure */ 335 setlabelfail(labelf); /* labeled failure */
314 *sfail = s; 336 *sfail = s;
315 fail: { /* pattern failed: try to backtrack */ 337 fail: { /* pattern failed: try to backtrack */
316 do { /* remove pending calls */ 338 do { /* remove pending calls */
317 assert(stack > getstackbase(L, ptop)); 339 assert(stack > getstackbase(L, ptop));
318 s = (--stack)->s; 340 s = (--stack)->s;
319 } while (s == NULL || (!(stack->ls & *labelf) && stack->p != &giveup)); 341 /*printf("s = %s, disj = %d\n", s, cs_disjoint(stack->ls, labelf));*/
342 } while (s == NULL || (stack->p != &giveup && cs_disjoint(stack->ls, labelf)));
320 if (ndyncap > 0) /* is there matchtime captures? */ 343 if (ndyncap > 0) /* is there matchtime captures? */
321 ndyncap -= removedyncap(L, capture, stack->caplevel, captop); 344 ndyncap -= removedyncap(L, capture, stack->caplevel, captop);
322 captop = stack->caplevel; 345 captop = stack->caplevel;
@@ -333,7 +356,7 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
333 fr -= rem; /* 'rem' items were popped from Lua stack */ 356 fr -= rem; /* 'rem' items were popped from Lua stack */
334 res = resdyncaptures(L, fr, s - o, e - o); /* get result */ 357 res = resdyncaptures(L, fr, s - o, e - o); /* get result */
335 if (res == -1) { /* fail? */ 358 if (res == -1) { /* fail? */
336 *labelf = LFAIL; /* labeled failure */ 359 setlabelfail(labelf); /* labeled failure */
337 *sfail = (const char *) s; /* TODO: ??? */ 360 *sfail = (const char *) s; /* TODO: ??? */
338 goto fail; 361 goto fail;
339 } 362 }
diff --git a/lpvm.h b/lpvm.h
index cec9f5a..3e006d3 100644
--- a/lpvm.h
+++ b/lpvm.h
@@ -47,7 +47,6 @@ typedef union Instruction {
47 short key; 47 short key;
48 } i; 48 } i;
49 int offset; 49 int offset;
50 Labelset labels; /* labeled failure */
51 byte buff[1]; 50 byte buff[1];
52} Instruction; 51} Instruction;
53 52
diff --git a/makefile b/makefile
index 5728b38..ce53890 100644
--- a/makefile
+++ b/makefile
@@ -1,8 +1,8 @@
1LIBNAME = lpeglabel 1LIBNAME = lpeglabel
2LUADIR = ../lua/ 2LUADIR = ../lua/
3 3
4COPT = -O2 4#COPT = -O2
5# COPT = -DLPEG_DEBUG -g 5COPT = -DLPEG_DEBUG -g
6 6
7CWARNS = -Wall -Wextra -pedantic \ 7CWARNS = -Wall -Wextra -pedantic \
8 -Waggregate-return \ 8 -Waggregate-return \
diff --git a/test.lua b/test.lua
index d5922ac..3f94edc 100755
--- a/test.lua
+++ b/test.lua
@@ -1115,7 +1115,6 @@ local re = require "relabel"
1115local match, compile = re.match, re.compile 1115local match, compile = re.match, re.compile
1116 1116
1117 1117
1118
1119assert(match("a", ".") == 2) 1118assert(match("a", ".") == 2)
1120assert(match("a", "''") == 1) 1119assert(match("a", "''") == 1)
1121assert(match("", " ! . ") == 1) 1120assert(match("", " ! . ") == 1)
diff --git a/testlabel.lua b/testlabel.lua
index f7180a7..67dc36b 100644
--- a/testlabel.lua
+++ b/testlabel.lua
@@ -1,5 +1,7 @@
1local m = require 'lpeglabel' 1local m = require 'lpeglabel'
2 2
3p = m.Lc(true, true, 1, 3)
4
3local p, r, l, s, serror 5local p, r, l, s, serror
4 6
5-- throws a label 7-- throws a label
@@ -133,7 +135,6 @@ assert(p:match("B") == 2)
133p = m.Lc(m.P"A", m.P(false), 1) + m.P("B") 135p = m.Lc(m.P"A", m.P(false), 1) + m.P("B")
134assert(p:match("B") == 2) 136assert(p:match("B") == 2)
135 137
136
137--[[ 138--[[
138S -> A /{1} 'a' 139S -> A /{1} 'a'
139A -> B 140A -> B