diff options
-rw-r--r-- | lpcode.c | 43 | ||||
-rw-r--r-- | lpprint.c | 9 | ||||
-rw-r--r-- | lptree.c | 94 | ||||
-rw-r--r-- | lptree.h | 9 | ||||
-rw-r--r-- | lptypes.h | 30 | ||||
-rw-r--r-- | lpvm.c | 59 | ||||
-rw-r--r-- | lpvm.h | 1 | ||||
-rw-r--r-- | makefile | 4 | ||||
-rwxr-xr-x | test.lua | 1 | ||||
-rw-r--r-- | testlabel.lua | 3 |
10 files changed, 146 insertions, 107 deletions
@@ -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) { | |||
491 | static int addoffsetinst (CompileState *compst, Opcode op) { | 492 | static 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 */ |
499 | static int addthrowinstruction (CompileState *compst, Labelset ls) { | 500 | static 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 | ||
507 | static 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 */ |
720 | static void codelabchoice (CompileState *compst, TTree *p1, TTree *p2, int opt, | 718 | static 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); |
@@ -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); |
@@ -34,7 +34,6 @@ const byte numsiblings[] = { | |||
34 | 34 | ||
35 | static TTree *newgrammar (lua_State *L, int arg); | 35 | static 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 */ | ||
379 | static 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 | |||
388 | static TTree *newcharset (lua_State *L) { | 377 | static 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 | */ |
400 | static TTree *seqaux (TTree *tree, TTree *sib, int sibsize) { | 389 | static 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) { | |||
412 | static void fillseq (TTree *tree, int tag, int n, const char *s) { | 401 | static 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 */ | ||
520 | static 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 | |||
527 | static 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 | |||
530 | static int lp_P (lua_State *L) { | 545 | static 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 | */ |
708 | static int lp_throw (lua_State *L) { | 723 | static 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 | */ |
724 | static int lp_labchoice (lua_State *L) { | 733 | static 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 */ |
@@ -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 | ||
@@ -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 */ | ||
114 | typedef 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 | |||
152 | typedef 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 | ||
@@ -26,6 +26,23 @@ | |||
26 | 26 | ||
27 | static const Instruction giveup = {{IGiveup, 0, 0}}; | 27 | static const Instruction giveup = {{IGiveup, 0, 0}}; |
28 | 28 | ||
29 | /* labeled failure */ | ||
30 | static void setlabelfail(Labelset *ls) { | ||
31 | loopset(i, ls->cs[i] = 0); | ||
32 | ls->cs[IDXLFAIL] = 1; | ||
33 | } | ||
34 | |||
35 | static void clearandsetlabel(Labelset *ls, byte b) { | ||
36 | loopset(i, ls->cs[i] = 0); | ||
37 | setlabel(ls->cs, b); | ||
38 | } | ||
39 | |||
40 | |||
41 | static 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 | } |
@@ -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 | ||
@@ -1,8 +1,8 @@ | |||
1 | LIBNAME = lpeglabel | 1 | LIBNAME = lpeglabel |
2 | LUADIR = ../lua/ | 2 | LUADIR = ../lua/ |
3 | 3 | ||
4 | COPT = -O2 | 4 | #COPT = -O2 |
5 | # COPT = -DLPEG_DEBUG -g | 5 | COPT = -DLPEG_DEBUG -g |
6 | 6 | ||
7 | CWARNS = -Wall -Wextra -pedantic \ | 7 | CWARNS = -Wall -Wextra -pedantic \ |
8 | -Waggregate-return \ | 8 | -Waggregate-return \ |
@@ -1115,7 +1115,6 @@ local re = require "relabel" | |||
1115 | local match, compile = re.match, re.compile | 1115 | local match, compile = re.match, re.compile |
1116 | 1116 | ||
1117 | 1117 | ||
1118 | |||
1119 | assert(match("a", ".") == 2) | 1118 | assert(match("a", ".") == 2) |
1120 | assert(match("a", "''") == 1) | 1119 | assert(match("a", "''") == 1) |
1121 | assert(match("", " ! . ") == 1) | 1120 | assert(match("", " ! . ") == 1) |
diff --git a/testlabel.lua b/testlabel.lua index f7180a7..67dc36b 100644 --- a/testlabel.lua +++ b/testlabel.lua | |||
@@ -1,5 +1,7 @@ | |||
1 | local m = require 'lpeglabel' | 1 | local m = require 'lpeglabel' |
2 | 2 | ||
3 | p = m.Lc(true, true, 1, 3) | ||
4 | |||
3 | local p, r, l, s, serror | 5 | local p, r, l, s, serror |
4 | 6 | ||
5 | -- throws a label | 7 | -- throws a label |
@@ -133,7 +135,6 @@ assert(p:match("B") == 2) | |||
133 | p = m.Lc(m.P"A", m.P(false), 1) + m.P("B") | 135 | p = m.Lc(m.P"A", m.P(false), 1) + m.P("B") |
134 | assert(p:match("B") == 2) | 136 | assert(p:match("B") == 2) |
135 | 137 | ||
136 | |||
137 | --[[ | 138 | --[[ |
138 | S -> A /{1} 'a' | 139 | S -> A /{1} 'a' |
139 | A -> B | 140 | A -> B |