diff options
Diffstat (limited to 'Build/source/texk/web2c/luatexdir/luapeg/lpeg.c')
-rw-r--r-- | Build/source/texk/web2c/luatexdir/luapeg/lpeg.c | 4085 |
1 files changed, 2510 insertions, 1575 deletions
diff --git a/Build/source/texk/web2c/luatexdir/luapeg/lpeg.c b/Build/source/texk/web2c/luatexdir/luapeg/lpeg.c index d46d4638abd..3e64950fb98 100644 --- a/Build/source/texk/web2c/luatexdir/luapeg/lpeg.c +++ b/Build/source/texk/web2c/luatexdir/luapeg/lpeg.c @@ -1,249 +1,23 @@ -/* -** $Id: lpeg.c,v 1.114 2011/02/16 15:02:20 roberto Exp $ -** LPeg - PEG pattern matching for Lua -** Copyright 2007, Lua.org & PUC-Rio (see 'lpeg.html' for license) -** written by Roberto Ierusalimschy -*/ - - -#include <assert.h> -#include <ctype.h> -#include <limits.h> -#include <stdio.h> -#include <string.h> - -#include "lua.h" -#include "lauxlib.h" #include "lpeg.h" -#define VERSION "0.10" -#define PATTERN_T "lpeg-pattern" -#define MAXSTACKIDX "lpeg-maxstack" - - /* -** compatibility with Lua 5.2 +** $Id: lpprint.c,v 1.7 2013/04/12 16:29:49 roberto Exp $ +** Copyright 2007, Lua.org & PUC-Rio (see 'lpeg.html' for license) */ -#if (LUA_VERSION_NUM == 502) - -#undef lua_equal -#define lua_equal(L,idx1,idx2) lua_compare(L,(idx1),(idx2),LUA_OPEQ) - -#undef lua_getfenv -#define lua_getfenv lua_getuservalue -#undef lua_setfenv -#define lua_setfenv lua_setuservalue - -#undef lua_objlen -#define lua_objlen lua_rawlen - -#undef luaL_register -#define luaL_register(L,n,f) \ - { if ((n) == NULL) luaL_setfuncs(L,f,0); else luaL_newlib(L,f); } - -#endif - - - -/* initial size for call/backtrack stack */ -#define INITBACK 100 - -/* default maximum size for call/backtrack stack */ -#define MAXBACK INITBACK - -/* size for call/backtrack stack for verifier */ -#define MAXBACKVER 200 - -/* initial size for capture's list */ -#define INITCAPSIZE 32 - - -/* index, on Lua stack, for subject */ -#define SUBJIDX 2 - -/* number of fixed arguments to 'match' (before capture arguments) */ -#define FIXEDARGS 3 - -/* index, on Lua stack, for substitution value cache */ -#define subscache(cs) ((cs)->ptop + 1) - -/* index, on Lua stack, for capture list */ -#define caplistidx(ptop) ((ptop) + 2) - -/* index, on Lua stack, for pattern's fenv */ -#define penvidx(ptop) ((ptop) + 3) - -/* index, on Lua stack, for backtracking stack */ -#define stackidx(ptop) ((ptop) + 4) - - - -typedef unsigned char byte; - - -#define CHARSETSIZE ((UCHAR_MAX/CHAR_BIT) + 1) - - -typedef byte Charset[CHARSETSIZE]; - - -/* Virtual Machine's instructions */ -typedef enum Opcode { - IAny, IChar, ISet, ISpan, - IBack, - IRet, IEnd, - IChoice, IJmp, ICall, IOpenCall, - ICommit, IPartialCommit, IBackCommit, IFailTwice, IFail, IGiveup, - IFunc, - IFullCapture, IEmptyCapture, IEmptyCaptureIdx, - IOpenCapture, ICloseCapture, ICloseRunTime -} Opcode; +/* #include <ctype.h> */ +/* #include <limits.h> */ +/* #include <stdio.h> */ -#define ISJMP 0x1 -#define ISCHECK 0x2 -#define ISFIXCHECK 0x4 -#define ISNOFAIL 0x8 -#define ISCAPTURE 0x10 -#define ISMOVABLE 0x20 -#define ISFENVOFF 0x40 - -static const int opproperties[] = { - /* IAny */ ISCHECK | ISFIXCHECK | ISJMP, - /* IChar */ ISCHECK | ISFIXCHECK | ISJMP, - /* ISet */ ISCHECK | ISFIXCHECK | ISJMP, - /* ISpan */ ISNOFAIL, - /* IBack */ 0, - /* IRet */ 0, - /* IEnd */ 0, - /* IChoice */ ISJMP, - /* IJmp */ ISJMP | ISNOFAIL, - /* ICall */ ISJMP, - /* IOpenCall */ ISFENVOFF, - /* ICommit */ ISJMP, - /* IPartialCommit */ ISJMP, - /* IBackCommit */ ISJMP, - /* IFailTwice */ 0, - /* IFail */ 0, - /* IGiveup */ 0, - /* IFunc */ ISCHECK | ISJMP, - /* IFullCapture */ ISCAPTURE | ISNOFAIL | ISFENVOFF, - /* IEmptyCapture */ ISCAPTURE | ISNOFAIL | ISMOVABLE, - /* IEmptyCaptureIdx */ISCAPTURE | ISNOFAIL | ISMOVABLE | ISFENVOFF, - /* IOpenCapture */ ISCAPTURE | ISNOFAIL | ISMOVABLE | ISFENVOFF, - /* ICloseCapture */ ISCAPTURE | ISNOFAIL | ISMOVABLE | ISFENVOFF, - /* ICloseRunTime */ ISCAPTURE | ISFENVOFF -}; - - -typedef union Instruction { - struct Inst { - byte code; - byte aux; - short offset; - } i; - PattFunc f; - int iv; - byte buff[1]; -} Instruction; - -static const Instruction giveup = {{IGiveup, 0, 0}}; - -#define getkind(op) ((op)->i.aux & 0xF) -#define getoff(op) (((op)->i.aux >> 4) & 0xF) - -#define dest(p,x) ((x) + ((p)+(x))->i.offset) - -#define MAXOFF 0xF -#define MAXAUX 0xFF - -/* maximum size (in elements) for a pattern */ -#define MAXPATTSIZE (SHRT_MAX - 10) - - -#define isprop(op,p) (opproperties[(op)->i.code] & (p)) -#define isjmp(op) (isprop(op, ISJMP) && (op)->i.offset != 0) -#define iscapture(op) isprop(op, ISCAPTURE) -#define ischeck(op) (isprop(op, ISCHECK) && (op)->i.offset == 0) -#define isfixcheck(op) (isprop(op, ISFIXCHECK) && (op)->i.offset == 0) -#define istest(op) (isprop(op, ISCHECK) && (op)->i.offset != 0) -#define isnofail(op) isprop(op, ISNOFAIL) -#define ismovable(op) isprop(op, ISMOVABLE) -#define isfenvoff(op) isprop(op, ISFENVOFF) - - -/* kinds of captures */ -typedef enum CapKind { - Cclose, Cposition, Cconst, Cbackref, Carg, Csimple, Ctable, Cfunction, - Cquery, Cstring, Csubst, Cfold, Cruntime, Cgroup -} CapKind; - -#define iscapnosize(k) ((k) == Cposition || (k) == Cconst) - - -typedef struct Capture { - const char *s; /* position */ - short idx; - byte kind; - byte siz; -} Capture; - - -/* size (in elements) for an instruction plus extra l bytes */ -#define instsize(l) (((l) + sizeof(Instruction) - 1)/sizeof(Instruction) + 1) - - -/* size (in elements) for a ISet instruction */ -#define CHARSETINSTSIZE instsize(CHARSETSIZE) - -/* size (in elements) for a IFunc instruction */ -#define funcinstsize(p) ((p)->i.aux + 2) - - -#define loopset(v,b) { int v; for (v = 0; v < CHARSETSIZE; v++) b; } - - -#define testchar(st,c) (((int)(st)[((c) >> 3)] & (1 << ((c) & 7)))) -#define setchar(st,c) ((st)[(c) >> 3] |= (1 << ((c) & 7))) - - -static int target (Instruction *p, int i); - - -static int sizei (const Instruction *i) { - switch((Opcode)i->i.code) { - case ISet: case ISpan: return CHARSETINSTSIZE; - case IFunc: return funcinstsize(i); - default: return 1; - } -} - - -static const char *val2str (lua_State *L, int idx) { - const char *k = lua_tostring(L, idx); - if (k != NULL) - return lua_pushfstring(L, "rule '%s'", k); - else - return lua_pushfstring(L, "rule <a %s>", luaL_typename(L, idx)); -} +/* #include "lptypes.h" */ +/* #include "lpprint.h" */ +/* #include "lpcode.h" */ -static int getposition (lua_State *L, int t, int i) { - int res; - lua_getfenv(L, -1); - lua_rawgeti(L, -1, i); /* get key from pattern's environment */ - lua_gettable(L, t); /* get position from positions table */ - res = lua_tointeger(L, -1); - if (res == 0) { /* key has no registered position? */ - lua_rawgeti(L, -2, i); /* get key again */ - return luaL_error(L, "%s is not defined in given grammar", val2str(L, -1)); - } - lua_pop(L, 2); /* remove environment and position */ - return res; -} +#if defined(LPEG_DEBUG) /* ** {====================================================== @@ -252,7 +26,7 @@ static int getposition (lua_State *L, int t, int i) { */ -static void printcharset (const Charset st) { +void printcharset (const byte *st) { int i; printf("["); for (i = 0; i <= UCHAR_MAX; i++) { @@ -271,51 +45,53 @@ static void printcapkind (int kind) { const char *const modes[] = { "close", "position", "constant", "backref", "argument", "simple", "table", "function", - "query", "string", "substitution", "fold", + "query", "string", "num", "substitution", "fold", "runtime", "group"}; printf("%s", modes[kind]); } static void printjmp (const Instruction *op, const Instruction *p) { - printf("-> "); - if (p->i.offset == 0) printf("FAIL"); - else printf("%d", (int)(dest(0, p) - op)); + printf("-> %d", (int)(p + (p + 1)->offset - op)); } static void printinst (const Instruction *op, const Instruction *p) { const char *const names[] = { - "any", "char", "set", "span", "back", + "any", "char", "set", + "testany", "testchar", "testset", + "span", "behind", "ret", "end", "choice", "jmp", "call", "open_call", "commit", "partial_commit", "back_commit", "failtwice", "fail", "giveup", - "func", - "fullcapture", "emptycapture", "emptycaptureidx", "opencapture", - "closecapture", "closeruntime" + "fullcapture", "opencapture", "closecapture", "closeruntime" }; printf("%02ld: %s ", (long)(p - op), names[p->i.code]); switch ((Opcode)p->i.code) { case IChar: { printf("'%c'", p->i.aux); - printjmp(op, p); break; } - case IAny: { - printf("* %d", p->i.aux); - printjmp(op, p); + case ITestChar: { + printf("'%c'", p->i.aux); printjmp(op, p); + break; + } + case IFullCapture: { + printcapkind(getkind(p)); + printf(" (size = %d) (idx = %d)", getoff(p), p->i.key); break; } - case IFullCapture: case IOpenCapture: - case IEmptyCapture: case IEmptyCaptureIdx: - case ICloseCapture: case ICloseRunTime: { + case IOpenCapture: { printcapkind(getkind(p)); - printf("(n = %d) (off = %d)", getoff(p), p->i.offset); + printf(" (idx = %d)", p->i.key); break; } case ISet: { printcharset((p+1)->buff); - printjmp(op, p); + break; + } + case ITestSet: { + printcharset((p+2)->buff); printjmp(op, p); break; } case ISpan: { @@ -323,16 +99,15 @@ static void printinst (const Instruction *op, const Instruction *p) { break; } case IOpenCall: { - printf("-> %d", p->i.offset); + printf("-> %d", (p + 1)->offset); break; } - case IChoice: { - printjmp(op, p); - printf(" (%d)", p->i.aux); + case IBehind: { + printf("%d", p->i.aux); break; } - case IJmp: case ICall: case ICommit: - case IPartialCommit: case IBackCommit: { + case IJmp: case ICall: case ICommit: case IChoice: + case IPartialCommit: case IBackCommit: case ITestAny: { printjmp(op, p); break; } @@ -342,25 +117,27 @@ static void printinst (const Instruction *op, const Instruction *p) { } -static void printpatt (Instruction *p) { +void printpatt (Instruction *p, int n) { Instruction *op = p; - for (;;) { + while (p < op + n) { printinst(op, p); - if ((Opcode)p->i.code == IEnd) break; p += sizei(p); } } -#if 0 +#if defined(LPEG_DEBUG) static void printcap (Capture *cap) { printcapkind(cap->kind); printf(" (idx: %d - size: %d) -> %p\n", cap->idx, cap->siz, cap->s); } -static void printcaplist (Capture *cap) { - for (; cap->s; cap++) printcap(cap); +void printcaplist (Capture *cap, Capture *limit) { + printf(">======\n"); + for (; cap->s && (limit == NULL || cap < limit); cap++) + printcap(cap); + printf("=======\n"); } #endif @@ -369,14 +146,147 @@ static void printcaplist (Capture *cap) { /* ** {====================================================== +** Printing trees (for debugging) +** ======================================================= +*/ + +static const char *tagnames[] = { + "char", "set", "any", + "true", "false", + "rep", + "seq", "choice", + "not", "and", + "call", "opencall", "rule", "grammar", + "behind", + "capture", "run-time" +}; + + +void printtree (TTree *tree, int ident) { + int i; + for (i = 0; i < ident; i++) printf(" "); + printf("%s", tagnames[tree->tag]); + switch (tree->tag) { + case TChar: { + int c = tree->u.n; + if (isprint(c)) + printf(" '%c'\n", c); + else + printf(" (%02X)\n", c); + break; + } + case TSet: { + printcharset(treebuffer(tree)); + printf("\n"); + break; + } + case TOpenCall: case TCall: { + printf(" key: %d\n", tree->key); + break; + } + case TBehind: { + printf(" %d\n", tree->u.n); + printtree(sib1(tree), ident + 2); + break; + } + case TCapture: { + printf(" cap: %d key: %d n: %d\n", tree->cap, tree->key, tree->u.n); + printtree(sib1(tree), ident + 2); + break; + } + case TRule: { + printf(" n: %d key: %d\n", tree->cap, tree->key); + printtree(sib1(tree), ident + 2); + break; /* do not print next rule as a sibling */ + } + case TGrammar: { + TTree *rule = sib1(tree); + printf(" %d\n", tree->u.n); /* number of rules */ + for (i = 0; i < tree->u.n; i++) { + printtree(rule, ident + 2); + rule = sib2(rule); + } + assert(rule->tag == TTrue); /* sentinel */ + break; + } + default: { + int sibs = numsiblings[tree->tag]; + printf("\n"); + if (sibs >= 1) { + printtree(sib1(tree), ident + 2); + if (sibs >= 2) + printtree(sib2(tree), ident + 2); + } + break; + } + } +} + + +void printktable (lua_State *L, int idx) { + int n, i; + lua_getfenv(L, idx); + if (lua_isnil(L, -1)) /* no ktable? */ + return; + n = lua_objlen(L, -1); + printf("["); + for (i = 1; i <= n; i++) { + printf("%d = ", i); + lua_rawgeti(L, -1, i); + if (lua_isstring(L, -1)) + printf("%s ", lua_tostring(L, -1)); + else + printf("%s ", lua_typename(L, lua_type(L, -1))); + lua_pop(L, 1); + } + printf("]\n"); + /* leave ktable at the stack */ +} + +/* }====================================================== */ + +#endif + + +/* +** $Id: lpvm.c,v 1.5 2013/04/12 16:29:49 roberto Exp $ +** Copyright 2007, Lua.org & PUC-Rio (see 'lpeg.html' for license) +*/ + +/* #include <limits.h> */ +/* #include <string.h> */ + + +/* #include "lua.h" */ +/* #include "lauxlib.h" */ + +/* #include "lpcap.h" */ +/* #include "lptypes.h" */ +/* #include "lpvm.h" */ +/* #include "lpprint.h" */ + + +/* initial size for call/backtrack stack */ +#if !defined(INITBACK) +#define INITBACK 100 +#endif + + +#define getoffset(p) (((p) + 1)->offset) + +static const Instruction giveup = {{IGiveup, 0, 0}}; + + +/* +** {====================================================== ** Virtual Machine ** ======================================================= */ typedef struct Stack { - const char *s; - const Instruction *p; + const char *s; /* saved position (or NULL for calls) */ + const Instruction *p; /* next instruction */ int caplevel; } Stack; @@ -384,10 +294,9 @@ typedef struct Stack { #define getstackbase(L, ptop) ((Stack *)lua_touserdata(L, stackidx(ptop))) -static int runtimecap (lua_State *L, Capture *close, Capture *ocap, - const char *o, const char *s, int ptop); - - +/* +** Double the size of the array of captures +*/ static Capture *doublecap (lua_State *L, Capture *cap, int captop, int ptop) { Capture *newc; if (captop >= INT_MAX/((int)sizeof(Capture) * 2)) @@ -399,61 +308,111 @@ static Capture *doublecap (lua_State *L, Capture *cap, int captop, int ptop) { } +/* +** Double the size of the stack +*/ static Stack *doublestack (lua_State *L, Stack **stacklimit, int ptop) { Stack *stack = getstackbase(L, ptop); Stack *newstack; - int n = *stacklimit - stack; + int n = *stacklimit - stack; /* current stack size */ int max, newn; lua_getfield(L, LUA_REGISTRYINDEX, MAXSTACKIDX); - max = lua_tointeger(L, -1); + max = lua_tointeger(L, -1); /* maximum allowed size */ lua_pop(L, 1); - if (n >= max) + if (n >= max) /* already at maximum size? */ luaL_error(L, "too many pending calls/choices"); - newn = 2*n; if (newn > max) newn = max; + newn = 2 * n; /* new size */ + if (newn > max) newn = max; newstack = (Stack *)lua_newuserdata(L, newn * sizeof(Stack)); memcpy(newstack, stack, n * sizeof(Stack)); lua_replace(L, stackidx(ptop)); *stacklimit = newstack + newn; - return newstack + n; + return newstack + n; /* return next position */ +} + +/* +** Interpret the result of a dynamic capture: false -> fail; +** true -> keep current position; number -> next position. +** Return new subject position. 'fr' is stack index where +** is the result; 'curr' is current subject position; 'limit' +** is subject's size. +*/ +static int resdyncaptures (lua_State *L, int fr, int curr, int limit) { + lua_Integer res; + if (!lua_toboolean(L, fr)) { /* false value? */ + lua_settop(L, fr - 1); /* remove results */ + return -1; /* and fail */ + } + else if (lua_isboolean(L, fr)) /* true? */ + res = curr; /* keep current position */ + else { + res = lua_tointeger(L, fr) - 1; /* new position */ + if (res < curr || res > limit) + luaL_error(L, "invalid position returned by match-time capture"); + } + lua_remove(L, fr); /* remove first result (offset) */ + return res; } +/* +** Add capture values returned by a dynamic capture to the capture list +** 'base', nested inside a group capture. 'fd' indexes the first capture +** value, 'n' is the number of values (at least 1). +*/ static void adddyncaptures (const char *s, Capture *base, int n, int fd) { int i; - assert(base[0].kind == Cruntime && base[0].siz == 0); - base[0].idx = fd; /* first returned capture */ - for (i = 1; i < n; i++) { /* add extra captures */ + /* Cgroup capture is already there */ + assert(base[0].kind == Cgroup && base[0].siz == 0); + base[0].idx = 0; /* make it an anonymous group */ + for (i = 1; i <= n; i++) { /* add runtime captures */ + base[i].kind = Cruntime; base[i].siz = 1; /* mark it as closed */ + base[i].idx = fd + i - 1; /* stack index of capture value */ base[i].s = s; - base[i].kind = Cruntime; - base[i].idx = fd + i; /* stack index */ } - base[n].kind = Cclose; /* add closing entry */ - base[n].siz = 1; - base[n].s = s; + base[i].kind = Cclose; /* close group */ + base[i].siz = 1; + base[i].s = s; } -#define condfailed(p) { int f = p->i.offset; if (f) p+=f; else goto fail; } +/* +** Remove dynamic captures from the Lua stack (called in case of failure) +*/ +static int removedyncap (lua_State *L, Capture *capture, + int level, int last) { + int id = finddyncap(capture + level, capture + last); /* index of 1st cap. */ + int top = lua_gettop(L); + if (id == 0) return 0; /* no dynamic captures? */ + lua_settop(L, id - 1); /* remove captures */ + return top - id + 1; /* number of values removed */ +} + -static const char *match (lua_State *L, - const char *o, const char *s, const char *e, - Instruction *op, Capture *capture, int ptop) { +/* +** Opcode interpreter +*/ +const char *match (lua_State *L, const char *o, const char *s, const char *e, + Instruction *op, Capture *capture, int ptop) { Stack stackbase[INITBACK]; Stack *stacklimit = stackbase + INITBACK; Stack *stack = stackbase; /* point to first empty slot in stack */ int capsize = INITCAPSIZE; int captop = 0; /* point to first empty slot in captures */ - const Instruction *p = op; + int ndyncap = 0; /* number of dynamic captures (in Lua stack) */ + const Instruction *p = op; /* current instruction */ stack->p = &giveup; stack->s = s; stack->caplevel = 0; stack++; lua_pushlightuserdata(L, stackbase); for (;;) { #if defined(DEBUG) - printf("s: |%s| stck: %d c: %d ", - s, stack - getstackbase(L, ptop), captop); + 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); switch ((Opcode)p->i.code) { case IEnd: { assert(stack == getstackbase(L, ptop) + 1); @@ -471,24 +430,40 @@ static const char *match (lua_State *L, continue; } case IAny: { - int n = p->i.aux; - if (n <= e - s) { p++; s += n; } - else condfailed(p); + if (s < e) { p++; s++; } + else goto fail; + continue; + } + case ITestAny: { + if (s < e) p += 2; + else p += getoffset(p); continue; } case IChar: { if ((byte)*s == p->i.aux && s < e) { p++; s++; } - else condfailed(p); + else goto fail; + continue; + } + case ITestChar: { + if ((byte)*s == p->i.aux && s < e) p += 2; + else p += getoffset(p); continue; } case ISet: { int c = (byte)*s; if (testchar((p+1)->buff, c) && s < e) { p += CHARSETINSTSIZE; s++; } - else condfailed(p); + else goto fail; + continue; + } + case ITestSet: { + int c = (byte)*s; + if (testchar((p + 2)->buff, c) && s < e) + p += 1 + CHARSETINSTSIZE; + else p += getoffset(p); continue; } - case IBack: { + case IBehind: { int n = p->i.aux; if (n > s - o) goto fail; s -= n; p++; @@ -502,53 +477,47 @@ static const char *match (lua_State *L, p += CHARSETINSTSIZE; continue; } - case IFunc: { - const char *r = (p+1)->f(s, e, o, (p+2)->buff); - if (r != NULL) { s = r; p += funcinstsize(p); } - else condfailed(p); - continue; - } case IJmp: { - p += p->i.offset; + p += getoffset(p); continue; } case IChoice: { if (stack == stacklimit) stack = doublestack(L, &stacklimit, ptop); - stack->p = dest(0, p); - stack->s = s - p->i.aux; + stack->p = p + getoffset(p); + stack->s = s; stack->caplevel = captop; stack++; - p++; + p += 2; continue; } case ICall: { if (stack == stacklimit) stack = doublestack(L, &stacklimit, ptop); stack->s = NULL; - stack->p = p + 1; /* save return address */ + stack->p = p + 2; /* save return address */ stack++; - p += p->i.offset; + p += getoffset(p); continue; } case ICommit: { assert(stack > getstackbase(L, ptop) && (stack - 1)->s != NULL); stack--; - p += p->i.offset; + p += getoffset(p); continue; } case IPartialCommit: { assert(stack > getstackbase(L, ptop) && (stack - 1)->s != NULL); (stack - 1)->s = s; (stack - 1)->caplevel = captop; - p += p->i.offset; + p += getoffset(p); continue; } case IBackCommit: { assert(stack > getstackbase(L, ptop) && (stack - 1)->s != NULL); s = (--stack)->s; captop = stack->caplevel; - p += p->i.offset; + p += getoffset(p); continue; } case IFailTwice: @@ -561,41 +530,41 @@ static const char *match (lua_State *L, assert(stack > getstackbase(L, ptop)); s = (--stack)->s; } while (s == NULL); + if (ndyncap > 0) /* is there matchtime captures? */ + ndyncap -= removedyncap(L, capture, stack->caplevel, captop); captop = stack->caplevel; p = stack->p; continue; } case ICloseRunTime: { + CapState cs; + int rem, res, n; int fr = lua_gettop(L) + 1; /* stack index of first result */ - int ncap = runtimecap(L, capture + captop, capture, o, s, ptop); - lua_Integer res = lua_tointeger(L, fr) - 1; /* offset */ - int n = lua_gettop(L) - fr; /* number of new captures */ - if (res == -1) { /* may not be a number */ - if (!lua_toboolean(L, fr)) { /* false value? */ - lua_settop(L, fr - 1); /* remove results */ - goto fail; /* and fail */ - } - else if (lua_isboolean(L, fr)) /* true? */ - res = s - o; /* keep current position */ - } - if (res < s - o || res > e - o) - luaL_error(L, "invalid position returned by match-time capture"); - s = o + res; /* update current position */ - captop -= ncap; /* remove nested captures */ - lua_remove(L, fr); /* remove first result (offset) */ - if (n > 0) { /* captures? */ - if ((captop += n + 1) >= capsize) { + cs.s = o; cs.L = L; cs.ocap = capture; cs.ptop = ptop; + n = runtimecap(&cs, capture + captop, s, &rem); /* call function */ + captop -= n; /* remove nested captures */ + fr -= rem; /* 'rem' items were popped from Lua stack */ + res = resdyncaptures(L, fr, s - o, e - o); /* get result */ + if (res == -1) /* fail? */ + goto fail; + s = o + res; /* else update current position */ + n = lua_gettop(L) - fr + 1; /* number of new captures */ + ndyncap += n - rem; /* update number of dynamic captures */ + if (n > 0) { /* any new capture? */ + if ((captop += n + 2) >= capsize) { capture = doublecap(L, capture, captop, ptop); capsize = 2 * captop; } - adddyncaptures(s, capture + captop - n - 1, n, fr); + /* add new captures to 'capture' list */ + adddyncaptures(s, capture + captop - n - 2, n, fr); } p++; continue; } case ICloseCapture: { - const char *s1 = s - getoff(p); + const char *s1 = s; assert(captop > 0); + /* if possible, turn capture into a full capture */ if (capture[captop - 1].siz == 0 && s1 - capture[captop - 1].s < UCHAR_MAX) { capture[captop - 1].siz = s1 - capture[captop - 1].s + 1; @@ -604,20 +573,20 @@ static const char *match (lua_State *L, } else { capture[captop].siz = 1; /* mark entry as closed */ - goto capture; + capture[captop].s = s; + goto pushcapture; } } - case IEmptyCapture: case IEmptyCaptureIdx: - capture[captop].siz = 1; /* mark entry as closed */ - goto capture; case IOpenCapture: capture[captop].siz = 0; /* mark entry as open */ - goto capture; + capture[captop].s = s; + goto pushcapture; case IFullCapture: capture[captop].siz = getoff(p) + 1; /* save capture size */ - capture: { capture[captop].s = s - getoff(p); - capture[captop].idx = p->i.offset; + /* goto pushcapture; */ + pushcapture: { + capture[captop].idx = p->i.key; capture[captop].kind = getkind(p); if (++captop >= capsize) { capture = doublecap(L, capture, captop, ptop); @@ -626,10 +595,6 @@ static const char *match (lua_State *L, p++; continue; } - case IOpenCall: { - lua_rawgeti(L, penvidx(ptop), p->i.offset); - luaL_error(L, "reference to %s outside a grammar", val2str(L, -1)); - } default: assert(0); return NULL; } } @@ -638,1207 +603,982 @@ static const char *match (lua_State *L, /* }====================================================== */ -/* -** {====================================================== -** Verifier -** ======================================================= -*/ /* -** check whether pattern may go from 'p' to 'e' without consuming any -** input. Raises an error if it detects a left recursion. 'op' points -** the beginning of the pattern. If pattern belongs to a grammar, -** 'rule' is the stack index where is its corresponding key (only for -** error messages) and 'posttable' is the stack index with a table -** mapping rule keys to the position of their code in the pattern. +** $Id: lpcode.c,v 1.18 2013/04/12 16:30:33 roberto Exp $ +** Copyright 2007, Lua.org & PUC-Rio (see 'lpeg.html' for license) */ -static int verify (lua_State *L, Instruction *op, const Instruction *p, - Instruction *e, int postable, int rule) { - static const char dummy[] = ""; - Stack back[MAXBACKVER]; - int backtop = 0; /* point to first empty slot in back */ - while (p != e) { - switch ((Opcode)p->i.code) { - case IRet: { - p = back[--backtop].p; - continue; - } - case IChoice: { - if (backtop >= MAXBACKVER) - return luaL_error(L, "too many pending calls/choices"); - back[backtop].p = dest(0, p); - back[backtop++].s = dummy; - p++; - continue; - } - case ICall: { - assert((p + 1)->i.code != IRet); /* no tail call */ - if (backtop >= MAXBACKVER) - return luaL_error(L, "too many pending calls/choices"); - back[backtop].s = NULL; - back[backtop++].p = p + 1; - goto dojmp; - } - case IOpenCall: { - int i; - if (postable == 0) /* grammar still not fixed? */ - goto fail; /* to be verified later */ - for (i = 0; i < backtop; i++) { - if (back[i].s == NULL && back[i].p == p + 1) - return luaL_error(L, "%s is left recursive", val2str(L, rule)); - } - if (backtop >= MAXBACKVER) - return luaL_error(L, "too many pending calls/choices"); - back[backtop].s = NULL; - back[backtop++].p = p + 1; - p = op + getposition(L, postable, p->i.offset); - continue; - } - case IBackCommit: - case ICommit: { - assert(backtop > 0 && p->i.offset > 0); - backtop--; - goto dojmp; - } - case IPartialCommit: { - assert(backtop > 0); - if (p->i.offset > 0) goto dojmp; /* forward jump */ - else { /* loop will be detected when checking corresponding rule */ - assert(postable != 0); - backtop--; - p++; /* just go on now */ - continue; - } - } - case IBack: { - if (p->i.aux == 1 && isfixcheck(p + 1)) { /* char test? */ - p++; /* skip back instruction */ - p += sizei(p); /* skip char test */ - } - else { /* standard lookbehind code */ - assert((Opcode)(p - 1)->i.code == IChoice); /* look behind */ - backtop--; - p += (p - 1)->i.offset; - assert((Opcode)(p - 1)->i.code == IFail); /* look behind */ - } - continue; - } - case IAny: - case IChar: - case ISet: { - const Instruction *next = p + sizei(p); - if ((Opcode)next->i.code == IBack) - p = next + 1; /* continue after the back instruction */ - else if (p->i.offset == 0) goto fail; - else /* jump */ - p += p->i.offset; - continue; - } - case IJmp: - dojmp: { - p += p->i.offset; - continue; - } - case IFailTwice: /* 'not' predicate */ - goto fail; /* body could have failed; try to backtrack it */ - case IFail: { - if (p > op && (p - 1)->i.code == IBackCommit) { /* 'and' predicate? */ - p++; /* pretend it succeeded and go ahead */ - continue; - } - /* else failed: go through */ - } - fail: { /* pattern failed: try to backtrack */ - do { - if (backtop-- == 0) - return 1; /* no more backtracking */ - } while (back[backtop].s == NULL); - p = back[backtop].p; - continue; - } - case ISpan: - case IOpenCapture: case ICloseCapture: - case IEmptyCapture: case IEmptyCaptureIdx: - case IFullCapture: { - p += sizei(p); - continue; - } - case ICloseRunTime: { - goto fail; /* be liberal in this case */ - } - case IFunc: { - const char *r = (p+1)->f(dummy, dummy, dummy, (p+2)->buff); - if (r != NULL) { p += funcinstsize(p); } - else condfailed(p); - continue; - } - case IEnd: /* cannot happen (should stop before it) */ - default: assert(0); return 0; - } - } - assert(backtop == 0); - return 0; -} - - -static void checkrule (lua_State *L, Instruction *op, int from, int to, - int postable, int rule) { - int i; - int lastopen = 0; /* more recent OpenCall seen in the code */ - for (i = from; i < to; i += sizei(op + i)) { - if (op[i].i.code == IPartialCommit && op[i].i.offset < 0) { /* loop? */ - int start = dest(op, i); - assert(op[start - 1].i.code == IChoice && - dest(op, start - 1) == target(op, i + 1)); - if (start <= lastopen) { /* loop does contain an open call? */ - if (!verify(L, op, op + start, op + i, postable, rule)) /* check body */ - luaL_error(L, "possible infinite loop in %s", val2str(L, rule)); - } - } - else if (op[i].i.code == IOpenCall) - lastopen = i; - } - assert(op[i - 1].i.code == IRet); - verify(L, op, op + from, op + to - 1, postable, rule); -} - +/* #include <limits.h> */ -/* }====================================================== */ +/* #include "lua.h" */ +/* #include "lauxlib.h" */ +/* #include "lptypes.h" */ +/* #include "lpcode.h" */ -/* -** {====================================================== -** Building Patterns -** ======================================================= -*/ -enum charsetanswer { NOINFO, ISCHARSET, VALIDSTARTS }; +/* signals a "no-instruction */ +#define NOINST -1 -typedef struct CharsetTag { - enum charsetanswer tag; - Charset cs; -} CharsetTag; -static Instruction *getpatt (lua_State *L, int idx, int *size); - - -static void check2test (Instruction *p, int n) { - assert(ischeck(p) && n != 0); - p->i.offset = n; -} +static const Charset fullset_ = + {{0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF}}; +static const Charset *fullset = &fullset_; /* -** invert array slice p[0]-p[e] (both inclusive) +** {====================================================== +** Analysis and some optimizations +** ======================================================= */ -static void invert (Instruction *p, int e) { - int i; - for (i = 0; i < e; i++, e--) { - Instruction temp = p[i]; - p[i] = p[e]; - p[e] = temp; - } -} - /* -** rotate array slice p[0]-p[e] (both inclusive) 'n' steps -** to the 'left' +** Check whether a charset is empty (IFail), singleton (IChar), +** full (IAny), or none of those (ISet). */ -static void rotate (Instruction *p, int e, int n) { - invert(p, n - 1); - invert(p + n, e - n); - invert(p, e); -} - - -#define op_step(p) ((p)->i.code == IAny ? (p)->i.aux : 1) - - -static int skipchecks (Instruction *p, int up, int *pn) { - int i, n = 0; - for (i = 0; isfixcheck(p + i); i += sizei(p + i)) { - int st = op_step(p + i); - if (n + st > MAXOFF - up) break; - n += st; - } - *pn = n; - return i; -} - - -#define ismovablecap(op) (ismovable(op) && getoff(op) < MAXOFF) - -static void optimizecaptures (Instruction *p) { +static Opcode charsettype (const byte *cs, int *c) { + int count = 0; int i; - int limit = 0; - for (i = 0; p[i].i.code != IEnd; i += sizei(p + i)) { - if (isjmp(p + i) && dest(p, i) >= limit) - limit = dest(p, i) + 1; /* do not optimize jump targets */ - else if (i >= limit && ismovablecap(p + i) && isfixcheck(p + i + 1)) { - int end, n, j; /* found a border capture|check */ - int maxoff = getoff(p + i); - int start = i; - /* find first capture in the group */ - while (start > limit && ismovablecap(p + start - 1)) { - start--; - if (getoff(p + start) > maxoff) maxoff = getoff(p + start); + int candidate = -1; /* candidate position for a char */ + for (i = 0; i < CHARSETSIZE; i++) { + int b = cs[i]; + if (b == 0) { + if (count > 1) return ISet; /* else set is still empty */ + } + else if (b == 0xFF) { + if (count < (i * BITSPERCHAR)) + return ISet; + else count += BITSPERCHAR; /* set is still full */ + } + else if ((b & (b - 1)) == 0) { /* byte has only one bit? */ + if (count > 0) + return ISet; /* set is neither full nor empty */ + else { /* set has only one char till now; track it */ + count++; + candidate = i; } - end = skipchecks(p + i + 1, maxoff, &n) + i; /* find last check */ - if (n == 0) continue; /* first check is too big to move across */ - assert(n <= MAXOFF && start <= i && i < end); - for (j = start; j <= i; j++) - p[j].i.aux += (n << 4); /* correct offset of captures to be moved */ - rotate(p + start, end - start, i - start + 1); /* move them up */ - i = end; - assert(isfixcheck(p + start) && iscapture(p + i)); + } + else return ISet; /* byte is neither empty, full, nor singleton */ + } + switch (count) { + case 0: return IFail; /* empty set */ + case 1: { /* singleton; find character bit inside byte */ + int b = cs[candidate]; + *c = candidate * BITSPERCHAR; + if ((b & 0xF0) != 0) { *c += 4; b >>= 4; } + if ((b & 0x0C) != 0) { *c += 2; b >>= 2; } + if ((b & 0x02) != 0) { *c += 1; } + return IChar; + } + default: { + assert(count == CHARSETSIZE * BITSPERCHAR); /* full set */ + return IAny; } } } - -static int target (Instruction *p, int i) { - while (p[i].i.code == IJmp) i += p[i].i.offset; - return i; -} - - -static void optimizejumps (Instruction *p) { - int i; - for (i = 0; p[i].i.code != IEnd; i += sizei(p + i)) { - if (isjmp(p + i)) - p[i].i.offset = target(p, dest(p, i)) - i; - } +/* +** A few basic operations on Charsets +*/ +static void cs_complement (Charset *cs) { + loopset(i, cs->cs[i] = ~cs->cs[i]); } -static void optimizechoice (Instruction *p) { - assert(p->i.code == IChoice); - if (isfixcheck(p + 1)) { - int lc = sizei(p + 1); - rotate(p, lc, 1); - assert(isfixcheck(p) && (p + lc)->i.code == IChoice); - (p + lc)->i.aux = op_step(p); - check2test(p, (p + lc)->i.offset); - (p + lc)->i.offset -= lc; - } +static int cs_equal (const byte *cs1, const byte *cs2) { + loopset(i, if (cs1[i] != cs2[i]) return 0); + return 1; } /* -** A 'headfail' pattern is a pattern that can only fails in its first -** instruction, which must be a check. +** computes whether sets cs1 and cs2 are disjoint */ -static int isheadfail (Instruction *p) { - if (!ischeck(p)) return 0; - /* check that other operations cannot fail */ - for (p += sizei(p); p->i.code != IEnd; p += sizei(p)) - if (!isnofail(p)) return 0; +static int cs_disjoint (const Charset *cs1, const Charset *cs2) { + loopset(i, if ((cs1->cs[i] & cs2->cs[i]) != 0) return 0;) return 1; } -#define checkpattern(L, idx) ((Instruction *)luaL_checkudata(L, idx, PATTERN_T)) - - /* -** Return the number of elements in the ktable of a pattern. -** in Lua 5.2, default "environment" for patterns is nil, not -** a table. Treat it as an empty table. +** Convert a 'char' pattern (TSet, TChar, TAny) to a charset */ -static int ktablelen (lua_State *L, int idx) { - if (!lua_istable(L, idx)) return 0; - else return lua_objlen(L, idx); -} - - -/* -** join the elements of the ktable from pattern 'p1' into the ktable of -** the pattern at the top of the stack ('p'). If 'p1' has no elements, -** 'p' keeps its original ktable. If 'p' has no elements, it shares -** 'p1' ktable. Otherwise, this function creates a new ktable for 'p'. -** Return the offset of original 'p' elements in the new ktable. -*/ -static int jointable (lua_State *L, int p1) { - int n, n1, i; - lua_getfenv(L, p1); - n1 = ktablelen(L, -1); /* number of elements in p1's env */ - lua_getfenv(L, -2); - if (n1 == 0 || lua_equal(L, -2, -1)) { - lua_pop(L, 2); - return 0; /* no need to change anything */ - } - n = ktablelen(L, -1); /* number of elements in p's env */ - if (n == 0) { - lua_pop(L, 1); /* removes p env */ - lua_setfenv(L, -2); /* p now shares p1's env */ - return 0; /* no need to correct anything */ - } - lua_createtable(L, n + n1, 0); - /* stack: p; p1 env; p env; new p env */ - for (i = 1; i <= n; i++) { - lua_rawgeti(L, -2, i); - lua_rawseti(L, -2, i); - } - for (i = 1; i <= n1; i++) { - lua_rawgeti(L, -3, i); - lua_rawseti(L, -2, n + i); +int tocharset (TTree *tree, Charset *cs) { + switch (tree->tag) { + case TSet: { /* copy set */ + loopset(i, cs->cs[i] = treebuffer(tree)[i]); + return 1; + } + case TChar: { /* only one char */ + assert(0 <= tree->u.n && tree->u.n <= UCHAR_MAX); + loopset(i, cs->cs[i] = 0); /* erase all chars */ + setchar(cs->cs, tree->u.n); /* add that one */ + return 1; + } + case TAny: { + loopset(i, cs->cs[i] = 0xFF); /* add all to the set */ + return 1; + } + default: return 0; } - lua_setfenv(L, -4); /* new table becomes p env */ - lua_pop(L, 2); /* remove p1 env and old p env */ - return n; } -#define copypatt(p1,p2,sz) memcpy(p1, p2, (sz) * sizeof(Instruction)); - -#define pattsize(L,idx) (lua_objlen(L, idx)/sizeof(Instruction) - 1) - - -static int addpatt (lua_State *L, Instruction *p, int p1idx) { - Instruction *p1 = (Instruction *)lua_touserdata(L, p1idx); - int sz = pattsize(L, p1idx); - int corr = jointable(L, p1idx); - copypatt(p, p1, sz + 1); - if (corr != 0) { - Instruction *px; - for (px = p; px < p + sz; px += sizei(px)) { - if (isfenvoff(px) && px->i.offset != 0) - px->i.offset += corr; +/* +** Checks whether a pattern has captures +*/ +int hascaptures (TTree *tree) { + tailcall: + switch (tree->tag) { + case TCapture: case TRunTime: + return 1; + default: { + switch (numsiblings[tree->tag]) { + case 1: /* return hascaptures(sib1(tree)); */ + tree = sib1(tree); goto tailcall; + case 2: + if (hascaptures(sib1(tree))) return 1; + /* else return hascaptures(sib2(tree)); */ + tree = sib2(tree); goto tailcall; + default: assert(numsiblings[tree->tag] == 0); return 0; + } } } - return sz; -} - - -static void setinstaux (Instruction *i, Opcode op, int offset, int aux) { - assert(aux <= MAXAUX); - i->i.code = op; - i->i.offset = offset; - i->i.aux = aux; } -#define setinst(i,op,off) setinstaux(i,op,off,0) - -#define setinstcap(i,op,idx,k,n) setinstaux(i,op,idx,((k) | ((n) << 4))) - /* -** create a new ktable for pattern at the stack top, mapping -** '1' to the value at stack position 'vidx'. +** Checks how a pattern behaves regarding the empty string, +** in one of two different ways: +** A pattern is *nullable* if it can match without consuming any character; +** A pattern is *nofail* if it never fails for any string +** (including the empty string). +** The difference is only for predicates and run-time captures; +** for other patterns, the two properties are equivalent. +** (With predicates, &'a' is nullable but not nofail. Of course, +** nofail => nullable.) +** These functions are all convervative in the following way: +** p is nullable => nullable(p) +** nofail(p) => p cannot fail +** The function assumes that TOpenCall is not nullable; +** this will be checked again when the grammar is fixed.) +** Run-time captures can do whatever they want, so the result +** is conservative. */ -static int value2fenv (lua_State *L, int vidx) { - lua_createtable(L, 1, 0); - lua_pushvalue(L, vidx); - lua_rawseti(L, -2, 1); - lua_setfenv(L, -2); - return 1; +int checkaux (TTree *tree, int pred) { + tailcall: + switch (tree->tag) { + case TChar: case TSet: case TAny: + case TFalse: case TOpenCall: + return 0; /* not nullable */ + case TRep: case TTrue: + return 1; /* no fail */ + case TNot: case TBehind: /* can match empty, but can fail */ + if (pred == PEnofail) return 0; + else return 1; /* PEnullable */ + case TAnd: /* can match empty; fail iff body does */ + if (pred == PEnullable) return 1; + /* else return checkaux(sib1(tree), pred); */ + tree = sib1(tree); goto tailcall; + case TRunTime: /* can fail; match empty iff body does */ + if (pred == PEnofail) return 0; + /* else return checkaux(sib1(tree), pred); */ + tree = sib1(tree); goto tailcall; + case TSeq: + if (!checkaux(sib1(tree), pred)) return 0; + /* else return checkaux(sib2(tree), pred); */ + tree = sib2(tree); goto tailcall; + case TChoice: + if (checkaux(sib2(tree), pred)) return 1; + /* else return checkaux(sib1(tree), pred); */ + tree = sib1(tree); goto tailcall; + case TCapture: case TGrammar: case TRule: + /* return checkaux(sib1(tree), pred); */ + tree = sib1(tree); goto tailcall; + case TCall: /* return checkaux(sib2(tree), pred); */ + tree = sib2(tree); goto tailcall; + default: assert(0); return 0; + }; } -static Instruction *newpatt (lua_State *L, size_t n) { - Instruction *p; - if (n >= MAXPATTSIZE - 1) - luaL_error(L, "pattern too big"); - p = (Instruction *)lua_newuserdata(L, (n + 1) * sizeof(Instruction)); - luaL_getmetatable(L, PATTERN_T); - lua_setmetatable(L, -2); - setinst(p + n, IEnd, 0); - return p; +/* +** number of characters to match a pattern (or -1 if variable) +** ('count' avoids infinite loops for grammars) +*/ +int fixedlenx (TTree *tree, int count, int len) { + tailcall: + switch (tree->tag) { + case TChar: case TSet: case TAny: + return len + 1; + case TFalse: case TTrue: case TNot: case TAnd: case TBehind: + return len; + case TRep: case TRunTime: case TOpenCall: + return -1; + case TCapture: case TRule: case TGrammar: + /* return fixedlenx(sib1(tree), count); */ + tree = sib1(tree); goto tailcall; + case TCall: + if (count++ >= MAXRULES) + return -1; /* may be a loop */ + /* else return fixedlenx(sib2(tree), count); */ + tree = sib2(tree); goto tailcall; + case TSeq: { + len = fixedlenx(sib1(tree), count, len); + if (len < 0) return -1; + /* else return fixedlenx(sib2(tree), count, len); */ + tree = sib2(tree); goto tailcall; + } + case TChoice: { + int n1, n2; + n1 = fixedlenx(sib1(tree), count, len); + if (n1 < 0) return -1; + n2 = fixedlenx(sib2(tree), count, len); + if (n1 == n2) return n1; + else return -1; + } + default: assert(0); return 0; + }; } -static void fillcharset (Instruction *p, Charset cs) { - switch (p[0].i.code) { - case ISet: { - loopset(i, cs[i] = p[1].buff[i]); - break; +/* +** Computes the 'first set' of a pattern. +** The result is a conservative aproximation: +** match p ax -> x' for some x ==> a in first(p). +** The set 'follow' is the first set of what follows the +** pattern (full set if nothing follows it). +** The function returns 0 when this set can be used for +** tests that avoid the pattern altogether. +** A non-zero return can happen for two reasons: +** 1) match p '' -> '' ==> returns 1. +** (tests cannot be used because they always fail for an empty input) +** 2) there is a match-time capture ==> returns 2. +** (match-time captures should not be avoided by optimizations) +*/ +static int getfirst (TTree *tree, const Charset *follow, Charset *firstset) { + tailcall: + switch (tree->tag) { + case TChar: case TSet: case TAny: { + tocharset(tree, firstset); + return 0; } - case IChar: { - loopset(i, cs[i] = 0); - setchar(cs, p[0].i.aux); - break; + case TTrue: { + loopset(i, firstset->cs[i] = follow->cs[i]); + return 1; } - default: { /* any char may start unhandled instructions */ - loopset(i, cs[i] = 0xff); - break; + case TFalse: { + loopset(i, firstset->cs[i] = 0); + return 0; + } + case TChoice: { + Charset csaux; + int e1 = getfirst(sib1(tree), follow, firstset); + int e2 = getfirst(sib2(tree), follow, &csaux); + loopset(i, firstset->cs[i] |= csaux.cs[i]); + return e1 | e2; + } + case TSeq: { + if (!nullable(sib1(tree))) { + /* return getfirst(sib1(tree), fullset, firstset); */ + tree = sib1(tree); follow = fullset; goto tailcall; + } + else { /* FIRST(p1 p2, fl) = FIRST(p1, FIRST(p2, fl)) */ + Charset csaux; + int e2 = getfirst(sib2(tree), follow, &csaux); + int e1 = getfirst(sib1(tree), &csaux, firstset); + if (e1 == 0) return 0; /* 'e1' ensures that first can be used */ + else if ((e1 | e2) & 2) /* one of the children has a matchtime? */ + return 2; /* pattern has a matchtime capture */ + else return e2; /* else depends on 'e2' */ + } + } + case TRep: { + getfirst(sib1(tree), follow, firstset); + loopset(i, firstset->cs[i] |= follow->cs[i]); + return 1; /* accept the empty string */ + } + case TCapture: case TGrammar: case TRule: { + /* return getfirst(sib1(tree), follow, firstset); */ + tree = sib1(tree); goto tailcall; + } + case TRunTime: { /* function invalidates any follow info. */ + int e = getfirst(sib1(tree), fullset, firstset); + if (e) return 2; /* function is not "protected"? */ + else return 0; /* pattern inside capture ensures first can be used */ } + case TCall: { + /* return getfirst(sib2(tree), follow, firstset); */ + tree = sib2(tree); goto tailcall; + } + case TAnd: { + int e = getfirst(sib1(tree), follow, firstset); + loopset(i, firstset->cs[i] &= follow->cs[i]); + return e; + } + case TNot: { + if (tocharset(sib1(tree), firstset)) { + cs_complement(firstset); + return 1; + } + /* else go through */ + } + case TBehind: { /* instruction gives no new information */ + /* call 'getfirst' to check for math-time captures */ + int e = getfirst(sib1(tree), follow, firstset); + loopset(i, firstset->cs[i] = follow->cs[i]); /* uses follow */ + return e | 1; /* always can accept the empty string */ + } + default: assert(0); return 0; } } /* -** Function 'tocharset' gets information about which chars may be a -** valid start for a pattern. +** If it returns true, then pattern can fail only depending on the next +** character of the subject */ - -static enum charsetanswer tocharset (Instruction *p, CharsetTag *c) { - if (isfixcheck(p)) { - fillcharset(p, c->cs); - if ((p + sizei(p))->i.code == IEnd && op_step(p) == 1) - c->tag = ISCHARSET; - else - c->tag = VALIDSTARTS; +static int headfail (TTree *tree) { + tailcall: + switch (tree->tag) { + case TChar: case TSet: case TAny: case TFalse: + return 1; + case TTrue: case TRep: case TRunTime: case TNot: + case TBehind: + return 0; + case TCapture: case TGrammar: case TRule: case TAnd: + tree = sib1(tree); goto tailcall; /* return headfail(sib1(tree)); */ + case TCall: + tree = sib2(tree); goto tailcall; /* return headfail(sib2(tree)); */ + case TSeq: + if (!nofail(sib2(tree))) return 0; + /* else return headfail(sib1(tree)); */ + tree = sib1(tree); goto tailcall; + case TChoice: + if (!headfail(sib1(tree))) return 0; + /* else return headfail(sib2(tree)); */ + tree = sib2(tree); goto tailcall; + default: assert(0); return 0; } - else - c->tag = NOINFO; - return c->tag; } -static int exclusiveset (Charset c1, Charset c2) { - /* non-empty intersection? */ - loopset(i, {if ((c1[i] & c2[i]) != 0) return 0;}); - return 1; /* no intersection */ +/* +** Check whether the code generation for the given tree can benefit +** from a follow set (to avoid computing the follow set when it is +** not needed) +*/ +static int needfollow (TTree *tree) { + tailcall: + switch (tree->tag) { + case TChar: case TSet: case TAny: + case TFalse: case TTrue: case TAnd: case TNot: + case TRunTime: case TGrammar: case TCall: case TBehind: + return 0; + case TChoice: case TRep: + return 1; + case TCapture: + tree = sib1(tree); goto tailcall; + case TSeq: + tree = sib2(tree); goto tailcall; + default: assert(0); return 0; + } } - -static int exclusive (CharsetTag *c1, CharsetTag *c2) { - if (c1->tag == NOINFO || c2->tag == NOINFO) - return 0; /* one of them is not filled */ - else return exclusiveset(c1->cs, c2->cs); -} +/* }====================================================== */ -static Instruction *newcharset (lua_State *L) { - Instruction *p = newpatt(L, CHARSETINSTSIZE); - p[0].i.code = ISet; - p[0].i.offset = 0; - loopset(i, p[1].buff[i] = 0); - return p; -} - -static int set_l (lua_State *L) { - size_t l; - const char *s = luaL_checklstring(L, 1, &l); - if (l == 1) - getpatt(L, 1, NULL); /* a unit set is equivalent to a literal */ - else { - Instruction *p = newcharset(L); - while (l--) { - setchar(p[1].buff, (byte)(*s)); - s++; - } - } - return 1; -} +/* +** {====================================================== +** Code generation +** ======================================================= +*/ -static int range_l (lua_State *L) { - int arg; - int top = lua_gettop(L); - Instruction *p = newcharset(L); - for (arg = 1; arg <= top; arg++) { - int c; - size_t l; - const char *r = luaL_checklstring(L, arg, &l); - luaL_argcheck(L, l == 2, arg, "range must have two characters"); - for (c = (byte)r[0]; c <= (byte)r[1]; c++) - setchar(p[1].buff, c); +/* +** size of an instruction +*/ +int sizei (const Instruction *i) { + switch((Opcode)i->i.code) { + case ISet: case ISpan: return CHARSETINSTSIZE; + case ITestSet: return CHARSETINSTSIZE + 1; + case ITestChar: case ITestAny: case IChoice: case IJmp: + case ICall: case IOpenCall: case ICommit: case IPartialCommit: + case IBackCommit: return 2; + default: return 1; } - return 1; } -static int nter_l (lua_State *L) { - Instruction *p; - luaL_argcheck(L, !lua_isnoneornil(L, 1), 1, "non-nil value expected"); - p = newpatt(L, 1); - setinst(p, IOpenCall, value2fenv(L, 1)); - return 1; -} - - - -static int testpattern (lua_State *L, int idx) { - if (lua_touserdata(L, idx)) { /* value is a userdata? */ - if (lua_getmetatable(L, idx)) { /* does it have a metatable? */ - luaL_getmetatable(L, PATTERN_T); - if (lua_rawequal(L, -1, -2)) { /* does it have the correct mt? */ - lua_pop(L, 2); /* remove both metatables */ - return 1; - } - } - } - return 0; -} +/* +** state for the compiler +*/ +typedef struct CompileState { + Pattern *p; /* pattern being compiled */ + int ncode; /* next position in p->code to be filled */ + lua_State *L; +} CompileState; -static Instruction *fix_l (lua_State *L, int t) { - Instruction *p; - int i; - int totalsize = 2; /* include initial call and jump */ - int n = 0; /* number of rules */ - int base = lua_gettop(L); - lua_newtable(L); /* to store relative positions of each rule */ - lua_pushinteger(L, 1); /* default initial rule */ - /* collect patterns and compute sizes */ - lua_pushnil(L); - while (lua_next(L, t) != 0) { - int l; - if (lua_tonumber(L, -2) == 1 && lua_isstring(L, -1)) { - lua_replace(L, base + 2); /* use this value as initial rule */ - continue; - } - if (!testpattern(L, -1)) - luaL_error(L, "%s is not a pattern", val2str(L, -2)); - l = pattsize(L, -1) + 1; /* space for pattern + ret */ - if (totalsize >= MAXPATTSIZE - l) - luaL_error(L, "grammar too large"); - luaL_checkstack(L, LUA_MINSTACK, "grammar has too many rules"); - lua_insert(L, -2); /* put key on top */ - lua_pushvalue(L, -1); /* duplicate key (for lua_next) */ - lua_pushvalue(L, -1); /* duplicate key (to index positions table)) */ - lua_pushinteger(L, totalsize); /* position for this rule */ - lua_settable(L, base + 1); /* store key=>position in positions table */ - totalsize += l; - n++; - } - luaL_argcheck(L, n > 0, t, "empty grammar"); - p = newpatt(L, totalsize); /* create new pattern */ - p++; /* save space for call */ - setinst(p++, IJmp, totalsize - 1); /* after call, jumps to the end */ - for (i = 1; i <= n; i++) { /* copy all rules into new pattern */ - p += addpatt(L, p, base + 1 + i*2); - setinst(p++, IRet, 0); - } - p -= totalsize; /* back to first position */ - totalsize = 2; /* go through each rule's position */ - for (i = 1; i <= n; i++) { /* check all rules */ - int l = pattsize(L, base + 1 + i*2) + 1; - checkrule(L, p, totalsize, totalsize + l, base + 1, base + 2 + i*2); - totalsize += l; - } - lua_pushvalue(L, base + 2); /* get initial rule */ - lua_gettable(L, base + 1); /* get its position in postions table */ - i = lua_tonumber(L, -1); /* convert to number */ - lua_pop(L, 1); - if (i == 0) /* is it defined? */ - luaL_error(L, "initial rule not defined in given grammar"); - setinst(p, ICall, i); /* first instruction calls initial rule */ - /* correct calls */ - for (i = 0; i < totalsize; i += sizei(p + i)) { - if (p[i].i.code == IOpenCall) { - int pos = getposition(L, base + 1, p[i].i.offset); - p[i].i.code = (p[target(p, i + 1)].i.code == IRet) ? IJmp : ICall; - p[i].i.offset = pos - i; - } - } - optimizejumps(p); - lua_replace(L, t); /* put new pattern in old's position */ - lua_settop(L, base); /* remove rules and positions table */ - return p; -} +/* +** code generation is recursive; 'opt' indicates that the code is +** being generated under a 'IChoice' operator jumping to its end. +** 'tt' points to a previous test protecting this code. 'fl' is +** the follow set of the pattern. +*/ +static void codegen (CompileState *compst, TTree *tree, int opt, int tt, + const Charset *fl); -static Instruction *any (lua_State *L, int n, int extra, int *offsetp) { - int offset = offsetp ? *offsetp : 0; - Instruction *p = newpatt(L, (n - 1)/UCHAR_MAX + extra + 1); - Instruction *p1 = p + offset; - for (; n > UCHAR_MAX; n -= UCHAR_MAX) - setinstaux(p1++, IAny, 0, UCHAR_MAX); - setinstaux(p1++, IAny, 0, n); - if (offsetp) *offsetp = p1 - p; - return p; +void reallocprog (lua_State *L, Pattern *p, int nsize) { + void *ud; + lua_Alloc f = lua_getallocf(L, &ud); + void *newblock = f(ud, p->code, p->codesize * sizeof(Instruction), + nsize * sizeof(Instruction)); + if (newblock == NULL && nsize > 0) + luaL_error(L, "not enough memory"); + p->code = (Instruction *)newblock; + p->codesize = nsize; } -static Instruction *getpatt (lua_State *L, int idx, int *size) { - Instruction *p; - switch (lua_type(L, idx)) { - case LUA_TSTRING: { - size_t i, len; - const char *s = lua_tolstring(L, idx, &len); - p = newpatt(L, len); - for (i = 0; i < len; i++) - setinstaux(p + i, IChar, 0, (byte)s[i]); - lua_replace(L, idx); - break; - } - case LUA_TNUMBER: { - int n = lua_tointeger(L, idx); - if (n == 0) /* empty pattern? */ - p = newpatt(L, 0); - else if (n > 0) - p = any(L, n, 0, NULL); - else if (-n <= UCHAR_MAX) { - p = newpatt(L, 2); - setinstaux(p, IAny, 2, -n); - setinst(p + 1, IFail, 0); - } - else { - int offset = 2; /* space for ITestAny & IChoice */ - p = any(L, -n - UCHAR_MAX, 3, &offset); - setinstaux(p, IAny, offset + 1, UCHAR_MAX); - setinstaux(p + 1, IChoice, offset, UCHAR_MAX); - setinst(p + offset, IFailTwice, 0); - } - lua_replace(L, idx); - break; - } - case LUA_TBOOLEAN: { - if (lua_toboolean(L, idx)) /* true? */ - p = newpatt(L, 0); /* empty pattern (always succeeds) */ - else { - p = newpatt(L, 1); - setinst(p, IFail, 0); - } - lua_replace(L, idx); - break; - } - case LUA_TTABLE: { - p = fix_l(L, idx); - break; - } - case LUA_TFUNCTION: { - p = newpatt(L, 2); - setinstcap(p, IOpenCapture, value2fenv(L, idx), Cruntime, 0); - setinstcap(p + 1, ICloseRunTime, 0, Cclose, 0); - lua_replace(L, idx); - break; - } - default: { - p = checkpattern(L, idx); - break; - } - } - if (size) *size = pattsize(L, idx); - return p; +static int nextinstruction (CompileState *compst) { + int size = compst->p->codesize; + if (compst->ncode >= size) + reallocprog(compst->L, compst->p, size * 2); + return compst->ncode++; } -static int getpattl (lua_State *L, int idx) { - int size; - getpatt(L, idx, &size); - return size; -} +#define getinstr(cs,i) ((cs)->p->code[i]) -static int pattern_l (lua_State *L) { - lua_settop(L, 1); - getpatt(L, 1, NULL); - return 1; +static int addinstruction (CompileState *compst, Opcode op, int aux) { + int i = nextinstruction(compst); + getinstr(compst, i).i.code = op; + getinstr(compst, i).i.aux = aux; + return i; } -#define isany(p) ((p)->i.code == IAny && ((p) + 1)->i.code == IEnd) -#define isfail(p) ((p)->i.code == IFail) -#define issucc(p) ((p)->i.code == IEnd) - -static int concat_l (lua_State *L) { - /* p1; p2; */ - int l1, l2; - Instruction *p1 = getpatt(L, 1, &l1); - Instruction *p2 = getpatt(L, 2, &l2); - if (isfail(p1) || issucc(p2)) - lua_pushvalue(L, 1); /* fail * x == fail; x * true == x */ - else if (isfail(p2) || issucc(p1)) - lua_pushvalue(L, 2); /* x * fail == fail; true * x == x */ - else if (isany(p1) && isany(p2)) - any(L, p1->i.aux + p2->i.aux, 0, NULL); - else { - Instruction *op = newpatt(L, l1 + l2); - Instruction *p = op + addpatt(L, op, 1); - addpatt(L, p, 2); - optimizecaptures(op); - } - return 1; +static int addoffsetinst (CompileState *compst, Opcode op) { + int i = addinstruction(compst, op, 0); /* instruction */ + addinstruction(compst, (Opcode)0, 0); /* open space for offset */ + assert(op == ITestSet || sizei(&getinstr(compst, i)) == 2); + return i; } -static int diff_l (lua_State *L) { - int l1, l2; - Instruction *p1 = getpatt(L, 1, &l1); - Instruction *p2 = getpatt(L, 2, &l2); - CharsetTag st1, st2; - if (tocharset(p1, &st1) == ISCHARSET && tocharset(p2, &st2) == ISCHARSET) { - Instruction *p = newcharset(L); - loopset(i, p[1].buff[i] = st1.cs[i] & ~st2.cs[i]); - } - else if (isheadfail(p2)) { - Instruction *p = newpatt(L, l2 + 1 + l1); - p += addpatt(L, p, 2); - check2test(p - l2, l2 + 1); - setinst(p++, IFail, 0); - addpatt(L, p, 1); - } - else { /* !e2 . e1 */ - /* !e -> choice L1; e; failtwice; L1: ... */ - Instruction *p = newpatt(L, 1 + l2 + 1 + l1); - Instruction *pi = p; - setinst(p++, IChoice, 1 + l2 + 1); - p += addpatt(L, p, 2); - setinst(p++, IFailTwice, 0); - addpatt(L, p, 1); - optimizechoice(pi); - } - return 1; +static void setoffset (CompileState *compst, int instruction, int offset) { + getinstr(compst, instruction + 1).offset = offset; } -static int unm_l (lua_State *L) { - Instruction *p = getpatt(L, 1, NULL); - if (isfail(p)) { /* -false? */ - newpatt(L, 0); /* true */ - return 1; - } - else if (issucc(p)) { /* -true? */ - Instruction *p1 = newpatt(L, 1); /* false */ - setinst(p1, IFail, 0); - return 1; - } - else { /* -A == '' - A */ - lua_pushliteral(L, ""); - lua_insert(L, 1); - return diff_l(L); - } +/* +** Add a capture instruction: +** 'op' is the capture instruction; 'cap' the capture kind; +** 'key' the key into ktable; 'aux' is optional offset +** +*/ +static int addinstcap (CompileState *compst, Opcode op, int cap, int key, + int aux) { + int i = addinstruction(compst, op, joinkindoff(cap, aux)); + getinstr(compst, i).i.key = key; + return i; } -static int pattand_l (lua_State *L) { - int l1; - CharsetTag st1; - Instruction *p1 = getpatt(L, 1, &l1); - if (isfail(p1) || issucc(p1)) - lua_pushvalue(L, 1); /* &fail == fail; &true == true */ - else if (tocharset(p1, &st1) == ISCHARSET) { - Instruction *p = newpatt(L, l1 + 1); - copypatt(p, p1, l1); p += l1; - setinstaux(p, IBack, 0, 1); - } - else { /* Choice L1; p1; BackCommit L2; L1: Fail; L2: */ - Instruction *p = newpatt(L, 1 + l1 + 2); - setinst(p++, IChoice, 1 + l1 + 1); - p += addpatt(L, p, 1); - setinst(p++, IBackCommit, 2); - setinst(p, IFail, 0); - } - return 1; -} - +#define gethere(compst) ((compst)->ncode) -static int nocalls (const Instruction *p) { - for (; (Opcode)p->i.code != IEnd; p += sizei(p)) - if ((Opcode)p->i.code == IOpenCall) return 0; - return 1; -} +#define target(code,i) ((i) + code[i + 1].offset) -static int pattbehind (lua_State *L) { - int l1; - CharsetTag st1; - Instruction *p1 = getpatt(L, 1, &l1); - int n = luaL_optint(L, 2, 1); - luaL_argcheck(L, n <= MAXAUX, 2, "lookbehind delta too large"); - if (!nocalls(p1)) - luaL_error(L, "lookbehind pattern cannot contain non terminals"); - if (isfail(p1) || issucc(p1)) - lua_pushvalue(L, 1); /* <fail == fail; <true == true */ - else if (n == 1 && tocharset(p1, &st1) == ISCHARSET) { - Instruction *p = newpatt(L, 1 + l1); - setinstaux(p, IBack, 0, 1); p++; - copypatt(p, p1, l1); - } - else { /* Choice L1; Back; p1; BackCommit L2; L1: fail; L2: */ - Instruction *p = newpatt(L, 2 + l1 + 2); - setinst(p++, IChoice, 2 + l1 + 1); - setinstaux(p++, IBack, 0, n); - p += addpatt(L, p, 1); - setinst(p++, IBackCommit, 2); - setinst(p, IFail, 0); - } - return 1; +static void jumptothere (CompileState *compst, int instruction, int target) { + if (instruction >= 0) + setoffset(compst, instruction, target - instruction); } - -static int firstpart (Instruction *p, int l) { - if (istest(p)) { - int e = p[0].i.offset - 1; - if ((p[e].i.code == IJmp || p[e].i.code == ICommit) && - e + p[e].i.offset == l) - return e + 1; - } - else if (p[0].i.code == IChoice) { - int e = p[0].i.offset - 1; - if (p[e].i.code == ICommit && e + p[e].i.offset == l) - return e + 1; - } - return 0; +static void jumptohere (CompileState *compst, int instruction) { + jumptothere(compst, instruction, gethere(compst)); } -static Instruction *auxnew (lua_State *L, Instruction **op, int *size, - int extra) { - *op = newpatt(L, *size + extra); - jointable(L, 1); - *size += extra; - return *op + *size - extra; +/* +** Code an IChar instruction, or IAny if there is an equivalent +** test dominating it +*/ +static void codechar (CompileState *compst, int c, int tt) { + if (tt >= 0 && getinstr(compst, tt).i.code == ITestChar && + getinstr(compst, tt).i.aux == c) + addinstruction(compst, IAny, 0); + else + addinstruction(compst, IChar, c); } -static int nofail (Instruction *p, int l) { +/* +** Add a charset posfix to an instruction +*/ +static void addcharset (CompileState *compst, const byte *cs) { + int p = gethere(compst); int i; - for (i = 0; i < l; i += sizei(p + i)) { - if (!isnofail(p + i)) return 0; - } - return 1; + for (i = 0; i < (int)CHARSETINSTSIZE - 1; i++) + nextinstruction(compst); /* space for buffer */ + /* fill buffer with charset */ + loopset(j, getinstr(compst, p).buff[j] = cs[j]); } -static int interfere (Instruction *p1, int l1, CharsetTag *st2) { - if (nofail(p1, l1)) /* p1 cannot fail? */ - return 0; /* nothing can intefere with it */ - if (st2->tag == NOINFO) return 1; - assert(p1->i.offset != 0); - switch (p1->i.code) { - case IChar: return testchar(st2->cs, p1->i.aux); - case ISet: return !exclusiveset(st2->cs, (p1 + 1)->buff); - default: assert(p1->i.code == IAny); return 1; +/* +** code a char set, optimizing unit sets for IChar, "complete" +** sets for IAny, and empty sets for IFail; also use an IAny +** when instruction is dominated by an equivalent test. +*/ +static void codecharset (CompileState *compst, const byte *cs, int tt) { + int c = 0; /* (=) to avoid warnings */ + Opcode op = charsettype(cs, &c); + switch (op) { + case IChar: codechar(compst, c, tt); break; + case ISet: { /* non-trivial set? */ + if (tt >= 0 && getinstr(compst, tt).i.code == ITestSet && + cs_equal(cs, getinstr(compst, tt + 2).buff)) + addinstruction(compst, IAny, 0); + else { + addinstruction(compst, ISet, 0); + addcharset(compst, cs); + } + break; + } + default: addinstruction(compst, op, c); break; } } -static Instruction *basicUnion (lua_State *L, Instruction *p1, int l1, - int l2, int *size, CharsetTag *st2) { - Instruction *op; - CharsetTag st1; - tocharset(p1, &st1); - if (st1.tag == ISCHARSET && st2->tag == ISCHARSET) { - Instruction *p = auxnew(L, &op, size, CHARSETINSTSIZE); - setinst(p, ISet, 0); - loopset(i, p[1].buff[i] = st1.cs[i] | st2->cs[i]); - } - else if (exclusive(&st1, st2) || isheadfail(p1)) { - Instruction *p = auxnew(L, &op, size, l1 + 1 + l2); - copypatt(p, p1, l1); - check2test(p, l1 + 1); - p += l1; - setinst(p++, IJmp, l2 + 1); - addpatt(L, p, 2); - } - else { - /* choice L1; e1; commit L2; L1: e2; L2: ... */ - Instruction *p = auxnew(L, &op, size, 1 + l1 + 1 + l2); - setinst(p++, IChoice, 1 + l1 + 1); - copypatt(p, p1, l1); p += l1; - setinst(p++, ICommit, 1 + l2); - addpatt(L, p, 2); - optimizechoice(p - (1 + l1 + 1)); - } - return op; -} - - -static Instruction *separateparts (lua_State *L, Instruction *p1, int l1, - int l2, int *size, CharsetTag *st2) { - int sp = firstpart(p1, l1); - if (sp == 0) /* first part is entire p1? */ - return basicUnion(L, p1, l1, l2, size, st2); - else if ((p1 + sp - 1)->i.code == ICommit || !interfere(p1, sp, st2)) { - Instruction *p; - int init = *size; - int end = init + sp; - *size = end; - p = separateparts(L, p1 + sp, l1 - sp, l2, size, st2); - copypatt(p + init, p1, sp); - (p + end - 1)->i.offset = *size - (end - 1); - return p; - } - else { /* must change back to non-optimized choice */ - Instruction *p; - int init = *size; - int end = init + sp + 1; /* needs one extra instruction (choice) */ - int sizefirst = sizei(p1); /* size of p1's first instruction (the test) */ - *size = end; - p = separateparts(L, p1 + sp, l1 - sp, l2, size, st2); - copypatt(p + init, p1, sizefirst); /* copy the test */ - (p + init)->i.offset++; /* correct jump (because of new instruction) */ - init += sizefirst; - setinstaux(p + init, IChoice, sp - sizefirst + 1, 1); init++; - copypatt(p + init, p1 + sizefirst, sp - sizefirst - 1); - init += sp - sizefirst - 1; - setinst(p + init, ICommit, *size - (end - 1)); - return p; - } -} - - -static int union_l (lua_State *L) { - int l1, l2; - int size = 0; - Instruction *p1 = getpatt(L, 1, &l1); - Instruction *p2 = getpatt(L, 2, &l2); - CharsetTag st2; - if (isfail(p1)) /* check for simple identities */ - lua_pushvalue(L, 2); /* fail / a == a */ - else if (isfail(p2) || issucc(p1)) - lua_pushvalue(L, 1); /* a / fail == a; true / a == true */ +/* +** code a test set, optimizing unit sets for ITestChar, "complete" +** sets for ITestAny, and empty sets for IJmp (always fails). +** 'e' is true iff test should accept the empty string. (Test +** instructions in the current VM never accept the empty string.) +*/ +static int codetestset (CompileState *compst, Charset *cs, int e) { + if (e) return NOINST; /* no test */ else { - tocharset(p2, &st2); - separateparts(L, p1, l1, l2, &size, &st2); + int c = 0; + Opcode op = charsettype(cs->cs, &c); + switch (op) { + case IFail: return addoffsetinst(compst, IJmp); /* always jump */ + case IAny: return addoffsetinst(compst, ITestAny); + case IChar: { + int i = addoffsetinst(compst, ITestChar); + getinstr(compst, i).i.aux = c; + return i; + } + case ISet: { + int i = addoffsetinst(compst, ITestSet); + addcharset(compst, cs->cs); + return i; + } + default: assert(0); return 0; + } } - return 1; } -static int repeatcharset (lua_State *L, Charset cs, int l1, int n) { - /* e; ...; e; span; */ - int i; - Instruction *p = newpatt(L, n*l1 + CHARSETINSTSIZE); - for (i = 0; i < n; i++) { - p += addpatt(L, p, 1); - } - setinst(p, ISpan, 0); - loopset(k, p[1].buff[k] = cs[k]); - return 1; +/* +** Find the final destination of a sequence of jumps +*/ +static int finaltarget (Instruction *code, int i) { + while (code[i].i.code == IJmp) + i = target(code, i); + return i; } -static Instruction *repeatheadfail (lua_State *L, int l1, int n) { - /* e; ...; e; L2: e'(L1); jump L2; L1: ... */ - int i; - Instruction *p = newpatt(L, (n + 1)*l1 + 1); - Instruction *op = p; - for (i = 0; i < n; i++) { - p += addpatt(L, p, 1); - } - p += addpatt(L, p, 1); - check2test(p - l1, l1 + 1); - setinst(p, IJmp, -l1); - return op; +/* +** final label (after traversing any jumps) +*/ +static int finallabel (Instruction *code, int i) { + return finaltarget(code, target(code, i)); } -static Instruction *repeats (lua_State *L, Instruction *p1, int l1, int n) { - /* e; ...; e; choice L1; L2: e; partialcommit L2; L1: ... */ - int i; - Instruction *op = newpatt(L, (n + 1)*l1 + 2); - Instruction *p = op; - if (!verify(L, p1, p1, p1 + l1, 0, 0)) - luaL_error(L, "loop body may accept empty string"); - for (i = 0; i < n; i++) { - p += addpatt(L, p, 1); - } - setinst(p++, IChoice, 1 + l1 + 1); - p += addpatt(L, p, 1); - setinst(p, IPartialCommit, -l1); - return op; +/* +** <behind(p)> == behind n; <p> (where n = fixedlen(p)) +*/ +static void codebehind (CompileState *compst, TTree *tree) { + if (tree->u.n > 0) + addinstruction(compst, IBehind, tree->u.n); + codegen(compst, sib1(tree), 0, NOINST, fullset); } -static void optionalheadfail (lua_State *L, int l1, int n) { - Instruction *op = newpatt(L, n * l1); - Instruction *p = op; - int i; - for (i = 0; i < n; i++) { - p += addpatt(L, p, 1); - check2test(p - l1, (n - i)*l1); +/* +** Choice; optimizations: +** - when p1 is headfail +** - when first(p1) and first(p2) are disjoint; than +** a character not in first(p1) cannot go to p1, and a character +** in first(p1) cannot go to p2 (at it is not in first(p2)). +** (The optimization is not valid if p1 accepts the empty string, +** as then there is no character at all...) +** - when p2 is empty and opt is true; a IPartialCommit can resuse +** the Choice already active in the stack. +*/ +static void codechoice (CompileState *compst, TTree *p1, TTree *p2, int opt, + const Charset *fl) { + int emptyp2 = (p2->tag == TTrue); + Charset cs1, cs2; + int e1 = getfirst(p1, fullset, &cs1); + if (headfail(p1) || + (!e1 && (getfirst(p2, fl, &cs2), cs_disjoint(&cs1, &cs2)))) { + /* <p1 / p2> == test (fail(p1)) -> L1 ; p1 ; jmp L2; L1: p2; L2: */ + int test = codetestset(compst, &cs1, 0); + int jmp = NOINST; + codegen(compst, p1, 0, test, fl); + if (!emptyp2) + jmp = addoffsetinst(compst, IJmp); + jumptohere(compst, test); + codegen(compst, p2, opt, NOINST, fl); + jumptohere(compst, jmp); + } + else if (opt && emptyp2) { + /* p1? == IPartialCommit; p1 */ + jumptohere(compst, addoffsetinst(compst, IPartialCommit)); + codegen(compst, p1, 1, NOINST, fullset); + } + else { + /* <p1 / p2> == + test(fail(p1)) -> L1; choice L1; <p1>; commit L2; L1: <p2>; L2: */ + int pcommit; + int test = codetestset(compst, &cs1, e1); + int pchoice = addoffsetinst(compst, IChoice); + codegen(compst, p1, emptyp2, test, fullset); + pcommit = addoffsetinst(compst, ICommit); + jumptohere(compst, pchoice); + jumptohere(compst, test); + codegen(compst, p2, opt, NOINST, fl); + jumptohere(compst, pcommit); } } -static void optionals (lua_State *L, int l1, int n) { - /* choice L1; e; partialcommit L2; L2: ... e; L1: commit L3; L3: ... */ - int i; - Instruction *op = newpatt(L, n*(l1 + 1) + 1); - Instruction *p = op; - setinst(p++, IChoice, 1 + n*(l1 + 1)); - for (i = 0; i < n; i++) { - p += addpatt(L, p, 1); - setinst(p++, IPartialCommit, 1); +/* +** And predicate +** optimization: fixedlen(p) = n ==> <&p> == <p>; behind n +** (valid only when 'p' has no captures) +*/ +static void codeand (CompileState *compst, TTree *tree, int tt) { + int n = fixedlen(tree); + if (n >= 0 && n <= MAXBEHIND && !hascaptures(tree)) { + codegen(compst, tree, 0, tt, fullset); + if (n > 0) + addinstruction(compst, IBehind, n); + } + else { /* default: Choice L1; p1; BackCommit L2; L1: Fail; L2: */ + int pcommit; + int pchoice = addoffsetinst(compst, IChoice); + codegen(compst, tree, 0, tt, fullset); + pcommit = addoffsetinst(compst, IBackCommit); + jumptohere(compst, pchoice); + addinstruction(compst, IFail, 0); + jumptohere(compst, pcommit); } - setinst(p - 1, ICommit, 1); /* correct last commit */ - optimizechoice(op); } -static int star_l (lua_State *L) { - int l1; - int n = luaL_checkint(L, 2); - Instruction *p1 = getpatt(L, 1, &l1); - if (n >= 0) { - CharsetTag st; - Instruction *op; - if (tocharset(p1, &st) == ISCHARSET) - return repeatcharset(L, st.cs, l1, n); - if (isheadfail(p1)) - op = repeatheadfail(L, l1, n); - else - op = repeats(L, p1, l1, n); - optimizecaptures(op); - optimizejumps(op); +/* +** Captures: if pattern has fixed (and not too big) length, use +** a single IFullCapture instruction after the match; otherwise, +** enclose the pattern with OpenCapture - CloseCapture. +*/ +static void codecapture (CompileState *compst, TTree *tree, int tt, + const Charset *fl) { + int len = fixedlen(sib1(tree)); + if (len >= 0 && len <= MAXOFF && !hascaptures(sib1(tree))) { + codegen(compst, sib1(tree), 0, tt, fl); + addinstcap(compst, IFullCapture, tree->cap, tree->key, len); } else { - if (isheadfail(p1)) - optionalheadfail(L, l1, -n); - else - optionals(L, l1, -n); + addinstcap(compst, IOpenCapture, tree->cap, tree->key, 0); + codegen(compst, sib1(tree), 0, tt, fl); + addinstcap(compst, ICloseCapture, Cclose, 0, 0); } - return 1; } -static int getlabel (lua_State *L, int labelidx) { - if (labelidx == 0) return 0; - else return value2fenv(L, labelidx); +static void coderuntime (CompileState *compst, TTree *tree, int tt) { + addinstcap(compst, IOpenCapture, Cgroup, tree->key, 0); + codegen(compst, sib1(tree), 0, tt, fullset); + addinstcap(compst, ICloseRunTime, Cclose, 0, 0); } -static int capture_aux (lua_State *L, int kind, int labelidx) { - int l1, n; - Instruction *p1 = getpatt(L, 1, &l1); - int lc = skipchecks(p1, 0, &n); - if (lc == l1) { /* got whole pattern? */ - /* may use a IFullCapture instruction at its end */ - Instruction *p = newpatt(L, l1 + 1); - int label = getlabel(L, labelidx); - p += addpatt(L, p, 1); - setinstcap(p, IFullCapture, label, kind, n); +/* +** Repetion; optimizations: +** When pattern is a charset, can use special instruction ISpan. +** When pattern is head fail, or if it starts with characters that +** are disjoint from what follows the repetions, a simple test +** is enough (a fail inside the repetition would backtrack to fail +** again in the following pattern, so there is no need for a choice). +** When 'opt' is true, the repetion can reuse the Choice already +** active in the stack. +*/ +static void coderep (CompileState *compst, TTree *tree, int opt, + const Charset *fl) { + Charset st; + if (tocharset(tree, &st)) { + addinstruction(compst, ISpan, 0); + addcharset(compst, st.cs); } - else { /* must use open-close pair */ - Instruction *op = newpatt(L, 1 + l1 + 1); - Instruction *p = op; - setinstcap(p++, IOpenCapture, getlabel(L, labelidx), kind, 0); - p += addpatt(L, p, 1); - setinstcap(p, ICloseCapture, 0, Cclose, 0); - optimizecaptures(op); + else { + int e1 = getfirst(tree, fullset, &st); + if (headfail(tree) || (!e1 && cs_disjoint(&st, fl))) { + /* L1: test (fail(p1)) -> L2; <p>; jmp L1; L2: */ + int jmp; + int test = codetestset(compst, &st, 0); + codegen(compst, tree, opt, test, fullset); + jmp = addoffsetinst(compst, IJmp); + jumptohere(compst, test); + jumptothere(compst, jmp, test); + } + else { + /* test(fail(p1)) -> L2; choice L2; L1: <p>; partialcommit L1; L2: */ + /* or (if 'opt'): partialcommit L1; L1: <p>; partialcommit L1; */ + int commit, l2; + int test = codetestset(compst, &st, e1); + int pchoice = NOINST; + if (opt) + jumptohere(compst, addoffsetinst(compst, IPartialCommit)); + else + pchoice = addoffsetinst(compst, IChoice); + l2 = gethere(compst); + codegen(compst, tree, 0, NOINST, fullset); + commit = addoffsetinst(compst, IPartialCommit); + jumptothere(compst, commit, l2); + jumptohere(compst, pchoice); + jumptohere(compst, test); + } } - return 1; } -static int capture_l (lua_State *L) { return capture_aux(L, Csimple, 0); } -static int tcapture_l (lua_State *L) { return capture_aux(L, Ctable, 0); } -static int capsubst_l (lua_State *L) { return capture_aux(L, Csubst, 0); } - -static int rcapture_l (lua_State *L) { - switch (lua_type(L, 2)) { - case LUA_TFUNCTION: return capture_aux(L, Cfunction, 2); - case LUA_TTABLE: return capture_aux(L, Cquery, 2); - case LUA_TSTRING: return capture_aux(L, Cstring, 2); - default: return luaL_argerror(L, 2, "invalid replacement value"); +/* +** Not predicate; optimizations: +** In any case, if first test fails, 'not' succeeds, so it can jump to +** the end. If pattern is headfail, that is all (it cannot fail +** in other parts); this case includes 'not' of simple sets. Otherwise, +** use the default code (a choice plus a failtwice). +*/ +static void codenot (CompileState *compst, TTree *tree) { + Charset st; + int e = getfirst(tree, fullset, &st); + int test = codetestset(compst, &st, e); + if (headfail(tree)) /* test (fail(p1)) -> L1; fail; L1: */ + addinstruction(compst, IFail, 0); + else { + /* test(fail(p))-> L1; choice L1; <p>; failtwice; L1: */ + int pchoice = addoffsetinst(compst, IChoice); + codegen(compst, tree, 0, NOINST, fullset); + addinstruction(compst, IFailTwice, 0); + jumptohere(compst, pchoice); } + jumptohere(compst, test); } -static int fold_l (lua_State *L) { - luaL_checktype(L, 2, LUA_TFUNCTION); - return capture_aux(L, Cfold, 2); -} - - -static int group_l (lua_State *L) { - if (lua_isnoneornil(L, 2)) - return capture_aux(L, Cgroup, 0); - else { - luaL_checkstring(L, 2); - return capture_aux(L, Cgroup, 2); +/* +** change open calls to calls, using list 'positions' to find +** correct offsets; also optimize tail calls +*/ +static void correctcalls (CompileState *compst, int *positions, + int from, int to) { + int i; + Instruction *code = compst->p->code; + for (i = from; i < to; i += sizei(&code[i])) { + if (code[i].i.code == IOpenCall) { + int n = code[i].i.key; /* rule number */ + int rule = positions[n]; /* rule position */ + assert(rule == from || code[rule - 1].i.code == IRet); + if (code[finaltarget(code, i + 2)].i.code == IRet) /* call; ret ? */ + code[i].i.code = IJmp; /* tail call */ + else + code[i].i.code = ICall; + jumptothere(compst, i, rule); /* call jumps to respective rule */ + } } + assert(i == to); } -static int position_l (lua_State *L) { - Instruction *p = newpatt(L, 1); - setinstcap(p, IEmptyCapture, 0, Cposition, 0); - return 1; +/* +** Code for a grammar: +** call L1; jmp L2; L1: rule 1; ret; rule 2; ret; ...; L2: +*/ +static void codegrammar (CompileState *compst, TTree *grammar) { + int positions[MAXRULES]; + int rulenumber = 0; + TTree *rule; + int firstcall = addoffsetinst(compst, ICall); /* call initial rule */ + int jumptoend = addoffsetinst(compst, IJmp); /* jump to the end */ + int start = gethere(compst); /* here starts the initial rule */ + jumptohere(compst, firstcall); + for (rule = sib1(grammar); rule->tag == TRule; rule = sib2(rule)) { + positions[rulenumber++] = gethere(compst); /* save rule position */ + codegen(compst, sib1(rule), 0, NOINST, fullset); /* code rule */ + addinstruction(compst, IRet, 0); + } + assert(rule->tag == TTrue); + jumptohere(compst, jumptoend); + correctcalls(compst, positions, start, gethere(compst)); } -static int backref_l (lua_State *L) { - Instruction *p = newpatt(L, 1); - int n = getlabel(L, 1); - setinstcap(p, IEmptyCaptureIdx, n, Cbackref, 0); - return 1; +static void codecall (CompileState *compst, TTree *call) { + int c = addoffsetinst(compst, IOpenCall); /* to be corrected later */ + getinstr(compst, c).i.key = sib2(call)->cap; /* rule number */ + assert(sib2(call)->tag == TRule); } -static int argcap_l (lua_State *L) { - int n = luaL_checkint(L, 1); - Instruction *p = newpatt(L, 1); - luaL_argcheck(L, 0 < n && n <= SHRT_MAX, 1, "invalid argument index"); - setinstcap(p, IEmptyCapture, n, Carg, 0); - return 1; +/* +** Code first child of a sequence +** (second child is called in-place to allow tail call) +** Return 'tt' for second child +*/ +static int codeseq1 (CompileState *compst, TTree *p1, TTree *p2, + int tt, const Charset *fl) { + if (needfollow(p1)) { + Charset fl1; + getfirst(p2, fl, &fl1); /* p1 follow is p2 first */ + codegen(compst, p1, 0, tt, &fl1); + } + else /* use 'fullset' as follow */ + codegen(compst, p1, 0, tt, fullset); + if (fixedlen(p1) != 0) /* can 'p1' consume anything? */ + return NOINST; /* invalidate test */ + else return tt; /* else 'tt' still protects sib2 */ } -static int matchtime_l (lua_State *L) { - int l1 = getpattl(L, 1); - Instruction *op = newpatt(L, 1 + l1 + 1); - Instruction *p = op; - luaL_checktype(L, 2, LUA_TFUNCTION); - setinstcap(p++, IOpenCapture, value2fenv(L, 2), Cruntime, 0); - p += addpatt(L, p, 1); - setinstcap(p, ICloseRunTime, 0, Cclose, 0); - optimizecaptures(op); - return 1; +/* +** Main code-generation function: dispatch to auxiliar functions +** according to kind of tree +*/ +static void codegen (CompileState *compst, TTree *tree, int opt, int tt, + const Charset *fl) { + tailcall: + switch (tree->tag) { + case TChar: codechar(compst, tree->u.n, tt); break; + case TAny: addinstruction(compst, IAny, 0); break; + case TSet: codecharset(compst, treebuffer(tree), tt); break; + case TTrue: break; + case TFalse: addinstruction(compst, IFail, 0); break; + case TChoice: codechoice(compst, sib1(tree), sib2(tree), opt, fl); break; + case TRep: coderep(compst, sib1(tree), opt, fl); break; + case TBehind: codebehind(compst, tree); break; + case TNot: codenot(compst, sib1(tree)); break; + case TAnd: codeand(compst, sib1(tree), tt); break; + case TCapture: codecapture(compst, tree, tt, fl); break; + case TRunTime: coderuntime(compst, tree, tt); break; + case TGrammar: codegrammar(compst, tree); break; + case TCall: codecall(compst, tree); break; + case TSeq: { + tt = codeseq1(compst, sib1(tree), sib2(tree), tt, fl); /* code 'p1' */ + /* codegen(compst, p2, opt, tt, fl); */ + tree = sib2(tree); goto tailcall; + } + default: assert(0); + } } -static int capconst_l (lua_State *L) { - int i, j; - int n = lua_gettop(L); - Instruction *p = newpatt(L, n > 1 ? n + 2 : n); - lua_createtable(L, n, 0); /* new environment for the new pattern */ - if (n > 1) setinstcap(p++, IOpenCapture, 0, Cgroup, 0); - for (i = j = 1; i <= n; i++) { - if (lua_isnil(L, i)) - setinstcap(p++, IEmptyCaptureIdx, 0, Cconst, 0); - else { - setinstcap(p++, IEmptyCaptureIdx, j, Cconst, 0); - lua_pushvalue(L, i); - lua_rawseti(L, -2, j++); +/* +** Optimize jumps and other jump-like instructions. +** * Update labels of instructions with labels to their final +** destinations (e.g., choice L1; ... L1: jmp L2: becomes +** choice L2) +** * Jumps to other instructions that do jumps become those +** instructions (e.g., jump to return becomes a return; jump +** to commit becomes a commit) +*/ +static void peephole (CompileState *compst) { + Instruction *code = compst->p->code; + int i; + for (i = 0; i < compst->ncode; i += sizei(&code[i])) { + switch (code[i].i.code) { + case IChoice: case ICall: case ICommit: case IPartialCommit: + case IBackCommit: case ITestChar: case ITestSet: + case ITestAny: { /* instructions with labels */ + jumptothere(compst, i, finallabel(code, i)); /* optimize label */ + break; + } + case IJmp: { + int ft = finaltarget(code, i); + switch (code[ft].i.code) { /* jumping to what? */ + case IRet: case IFail: case IFailTwice: + case IEnd: { /* instructions with unconditional implicit jumps */ + code[i] = code[ft]; /* jump becomes that instruction */ + code[i + 1].i.code = IAny; /* 'no-op' for target position */ + break; + } + case ICommit: case IPartialCommit: + case IBackCommit: { /* inst. with unconditional explicit jumps */ + int fft = finallabel(code, ft); + code[i] = code[ft]; /* jump becomes that instruction... */ + jumptothere(compst, i, fft); /* but must correct its offset */ + i--; /* reoptimize its label */ + break; + } + default: { + jumptothere(compst, i, ft); /* optimize label */ + break; + } + } + break; + } + default: break; } } - if (n > 1) setinstcap(p++, ICloseCapture, 0, Cclose, 0); - lua_setfenv(L, -2); /* set environment */ - return 1; + assert(code[i - 1].i.code == IEnd); } -/* }====================================================== */ - - /* -** {====================================================== -** User-Defined Patterns -** ======================================================= +** Compile a pattern */ - -static void l_newpf (lua_State *L, PattFunc f, const void *ud, size_t l) { - int n = instsize(l) + 1; - Instruction *p = newpatt(L, n); - if (n > MAXAUX) luaL_error(L, "pattern data too long"); - p[0].i.code = IFunc; - p[0].i.aux = n - 2; - p[0].i.offset = 0; - p[1].f = f; - memcpy(p[2].buff, ud, l); +Instruction *compile (lua_State *L, Pattern *p) { + CompileState compst; + compst.p = p; compst.ncode = 0; compst.L = L; + reallocprog(L, p, 2); /* minimum initial size */ + codegen(&compst, p->tree, 0, NOINST, fullset); + addinstruction(&compst, IEnd, 0); + reallocprog(L, p, compst.ncode); /* set final size */ + peephole(&compst); + return p->code; } + /* }====================================================== */ /* -** {====================================================== -** Captures -** ======================================================= +** $Id: lpcap.c,v 1.4 2013/03/21 20:25:12 roberto Exp $ +** Copyright 2007, Lua.org & PUC-Rio (see 'lpeg.html' for license) */ +/* #include "lua.h" */ +/* #include "lauxlib.h" */ -typedef struct CapState { - Capture *cap; /* current capture */ - Capture *ocap; /* (original) capture list */ - lua_State *L; - int ptop; /* index of last argument to 'match' */ - const char *s; /* original string */ - int valuecached; /* value stored in cache slot */ -} CapState; +/* #include "lpcap.h" */ +/* #include "lptypes.h" */ #define captype(cap) ((cap)->kind) @@ -1849,84 +1589,114 @@ typedef struct CapState { #define isfullcap(cap) ((cap)->siz != 0) -#define getfromenv(cs,v) lua_rawgeti((cs)->L, penvidx((cs)->ptop), v) -#define pushluaval(cs) getfromenv(cs, (cs)->cap->idx) - -#define pushsubject(cs, c) lua_pushlstring((cs)->L, (c)->s, (c)->siz - 1) +#define getfromktable(cs,v) lua_rawgeti((cs)->L, ktableidx((cs)->ptop), v) +#define pushluaval(cs) getfromktable(cs, (cs)->cap->idx) -#define updatecache(cs,v) { if ((v) != (cs)->valuecached) updatecache_(cs,v); } -static void updatecache_ (CapState *cs, int v) { - getfromenv(cs, v); - lua_replace(cs->L, subscache(cs)); - cs->valuecached = v; +/* +** Put at the cache for Lua values the value indexed by 'v' in ktable +** of the running pattern (if it is not there yet); returns its index. +*/ +static int updatecache (CapState *cs, int v) { + int idx = cs->ptop + 1; /* stack index of cache for Lua values */ + if (v != cs->valuecached) { /* not there? */ + getfromktable(cs, v); /* get value from 'ktable' */ + lua_replace(cs->L, idx); /* put it at reserved stack position */ + cs->valuecached = v; /* keep track of what is there */ + } + return idx; } static int pushcapture (CapState *cs); +/* +** Goes back in a list of captures looking for an open capture +** corresponding to a close +*/ static Capture *findopen (Capture *cap) { - int n = 0; + int n = 0; /* number of closes waiting an open */ for (;;) { cap--; - if (isclosecap(cap)) n++; + if (isclosecap(cap)) n++; /* one more open to skip */ else if (!isfullcap(cap)) if (n-- == 0) return cap; } } -static Capture *nextcap (Capture *cap) { - if (isfullcap(cap)) return cap + 1; - else { - int n = 0; - for (;;) { +/* +** Go to the next capture +*/ +static void nextcap (CapState *cs) { + Capture *cap = cs->cap; + if (!isfullcap(cap)) { /* not a single capture? */ + int n = 0; /* number of opens waiting a close */ + for (;;) { /* look for corresponding close */ cap++; if (isclosecap(cap)) { - if (n-- == 0) return cap + 1; + if (n-- == 0) break; } else if (!isfullcap(cap)) n++; } } + cs->cap = cap + 1; /* + 1 to skip last close (or entire single capture) */ } -static int pushallvalues (CapState *cs, int addextra) { +/* +** Push on the Lua stack all values generated by nested captures inside +** the current capture. Returns number of values pushed. 'addextra' +** makes it push the entire match after all captured values. The +** entire match is pushed also if there are no other nested values, +** so the function never returns zero. +*/ +static int pushnestedvalues (CapState *cs, int addextra) { Capture *co = cs->cap; - int n = 0; - if (isfullcap(cs->cap++)) { - pushsubject(cs, co); /* push whole match */ - return 1; + if (isfullcap(cs->cap++)) { /* no nested captures? */ + lua_pushlstring(cs->L, co->s, co->siz - 1); /* push whole match */ + return 1; /* that is it */ } - while (!isclosecap(cs->cap)) - n += pushcapture(cs); - if (addextra || n == 0) { /* need extra? */ - lua_pushlstring(cs->L, co->s, cs->cap->s - co->s); /* push whole match */ - n++; + else { + int n = 0; + while (!isclosecap(cs->cap)) /* repeat for all nested patterns */ + n += pushcapture(cs); + if (addextra || n == 0) { /* need extra? */ + lua_pushlstring(cs->L, co->s, cs->cap->s - co->s); /* push whole match */ + n++; + } + cs->cap++; /* skip close entry */ + return n; } - cs->cap++; /* skip close entry */ - return n; } +/* +** Push only the first value generated by nested captures +*/ +static void pushonenestedvalue (CapState *cs) { + int n = pushnestedvalues(cs, 0); + if (n > 1) + lua_pop(cs->L, n - 1); /* pop extra values */ +} + + +/* +** Try to find a named group capture with the name given at the top of +** the stack; goes backward from 'cap'. +*/ static Capture *findback (CapState *cs, Capture *cap) { lua_State *L = cs->L; - for (;;) { - if (cap == cs->ocap) { /* not found */ - const char *s = lua_tostring(L, -1); - if (s == NULL) s = lua_pushfstring(L, "(a %s)", luaL_typename(L, -1)); - luaL_error(L, "back reference '%s' not found", s); - } - cap--; + while (cap-- > cs->ocap) { /* repeat until end of list */ if (isclosecap(cap)) - cap = findopen(cap); + cap = findopen(cap); /* skip nested captures */ else if (!isfullcap(cap)) continue; /* opening an enclosing capture: skip and get previous */ if (captype(cap) == Cgroup) { - getfromenv(cs, cap->idx); /* get group name */ + getfromktable(cs, cap->idx); /* get group name */ if (lua_equal(L, -2, -1)) { /* right group? */ lua_pop(L, 2); /* remove reference name and group name */ return cap; @@ -1934,20 +1704,29 @@ static Capture *findback (CapState *cs, Capture *cap) { else lua_pop(L, 1); /* remove group name */ } } + luaL_error(L, "back reference '%s' not found", lua_tostring(L, -1)); + return NULL; /* to avoid warnings */ } +/* +** Back-reference capture. Return number of values pushed. +*/ static int backrefcap (CapState *cs) { int n; Capture *curr = cs->cap; pushluaval(cs); /* reference name */ - cs->cap = findback(cs, curr); - n = pushallvalues(cs, 0); + cs->cap = findback(cs, curr); /* find corresponding group */ + n = pushnestedvalues(cs, 0); /* push group's values */ cs->cap = curr + 1; return n; } +/* +** Table capture: creates a new table and populates it with nested +** captures. +*/ static int tablecap (CapState *cs) { lua_State *L = cs->L; int n = 0; @@ -1956,182 +1735,249 @@ static int tablecap (CapState *cs) { return 1; /* table is empty */ while (!isclosecap(cs->cap)) { if (captype(cs->cap) == Cgroup && cs->cap->idx != 0) { /* named group? */ - int k; pushluaval(cs); /* push group name */ - k = pushallvalues(cs, 0); - if (k == 0) { /* no value? */ - lua_pop(L, 1); /* remove group name */ - continue; /* and go on */ - } - else if (k > 1) - lua_pop(L, k - 1); /* keep just one value */ + pushonenestedvalue(cs); lua_settable(L, -3); } - else { + else { /* not a named group */ int i; int k = pushcapture(cs); - for (i = k; i > 0; i--) + for (i = k; i > 0; i--) /* store all values into table */ lua_rawseti(L, -(i + 1), n + i); n += k; } } cs->cap++; /* skip close entry */ - return 1; + return 1; /* number of values pushed (only the table) */ } +/* +** Table-query capture +*/ static int querycap (CapState *cs) { int idx = cs->cap->idx; - int n = pushallvalues(cs, 0); - if (n > 1) /* extra captures? */ - lua_pop(cs->L, n - 1); /* throw them away */ - updatecache(cs, idx); - lua_gettable(cs->L, subscache(cs)); + pushonenestedvalue(cs); /* get nested capture */ + lua_gettable(cs->L, updatecache(cs, idx)); /* query cap. value at table */ if (!lua_isnil(cs->L, -1)) return 1; - else { - lua_pop(cs->L, 1); /* remove value */ + else { /* no value */ + lua_pop(cs->L, 1); /* remove nil */ return 0; } } +/* +** Fold capture +*/ static int foldcap (CapState *cs) { int n; lua_State *L = cs->L; int idx = cs->cap->idx; - if (isfullcap(cs->cap++) || isclosecap(cs->cap) || (n = pushcapture(cs)) == 0) + if (isfullcap(cs->cap++) || /* no nested captures? */ + isclosecap(cs->cap) || /* no nested captures (large subject)? */ + (n = pushcapture(cs)) == 0) /* nested captures with no values? */ return luaL_error(L, "no initial value for fold capture"); if (n > 1) - lua_pop(L, n - 1); /* leave only one result */ + lua_pop(L, n - 1); /* leave only one result for accumulator */ while (!isclosecap(cs->cap)) { - updatecache(cs, idx); - lua_pushvalue(L, subscache(cs)); /* get folding function */ + lua_pushvalue(L, updatecache(cs, idx)); /* get folding function */ lua_insert(L, -2); /* put it before accumulator */ - n = pushcapture(cs); /* get other captures */ + n = pushcapture(cs); /* get next capture's values */ lua_call(L, n + 1, 1); /* call folding function */ } cs->cap++; /* skip close entry */ - return 1; + return 1; /* only accumulator left on the stack */ } +/* +** Function capture +*/ static int functioncap (CapState *cs) { int n; int top = lua_gettop(cs->L); - pushluaval(cs); - n = pushallvalues(cs, 0); - lua_call(cs->L, n, LUA_MULTRET); - return lua_gettop(cs->L) - top; + pushluaval(cs); /* push function */ + n = pushnestedvalues(cs, 0); /* push nested captures */ + lua_call(cs->L, n, LUA_MULTRET); /* call function */ + return lua_gettop(cs->L) - top; /* return function's results */ } -static int runtimecap (lua_State *L, Capture *close, Capture *ocap, - const char *o, const char *s, int ptop) { - CapState cs; - int n; +/* +** Select capture +*/ +static int numcap (CapState *cs) { + int idx = cs->cap->idx; /* value to select */ + if (idx == 0) { /* no values? */ + nextcap(cs); /* skip entire capture */ + return 0; /* no value produced */ + } + else { + int n = pushnestedvalues(cs, 0); + if (n < idx) /* invalid index? */ + return luaL_error(cs->L, "no capture '%d'", idx); + else { + lua_pushvalue(cs->L, -(n - idx + 1)); /* get selected capture */ + lua_replace(cs->L, -(n + 1)); /* put it in place of 1st capture */ + lua_pop(cs->L, n - 1); /* remove other captures */ + return 1; + } + } +} + + +/* +** Return the stack index of the first runtime capture in the given +** list of captures (or zero if no runtime captures) +*/ +int finddyncap (Capture *cap, Capture *last) { + for (; cap < last; cap++) { + if (cap->kind == Cruntime) + return cap->idx; /* stack position of first capture */ + } + return 0; /* no dynamic captures in this segment */ +} + + +/* +** Calls a runtime capture. Returns number of captures removed by +** the call, including the initial Cgroup. (Captures to be added are +** on the Lua stack.) +*/ +int runtimecap (CapState *cs, Capture *close, const char *s, int *rem) { + int n, id; + lua_State *L = cs->L; + int otop = lua_gettop(L); Capture *open = findopen(close); - assert(captype(open) == Cruntime); - close->kind = Cclose; + assert(captype(open) == Cgroup); + id = finddyncap(open, close); /* get first dynamic capture argument */ + close->kind = Cclose; /* closes the group */ close->s = s; - cs.ocap = ocap; cs.cap = open; cs.L = L; - cs.s = o; cs.valuecached = 0; cs.ptop = ptop; + cs->cap = open; cs->valuecached = 0; /* prepare capture state */ luaL_checkstack(L, 4, "too many runtime captures"); - pushluaval(&cs); + pushluaval(cs); /* push function to be called */ lua_pushvalue(L, SUBJIDX); /* push original subject */ - lua_pushinteger(L, s - o + 1); /* current position */ - n = pushallvalues(&cs, 0); - lua_call(L, n + 2, LUA_MULTRET); - return close - open; + lua_pushinteger(L, s - cs->s + 1); /* push current position */ + n = pushnestedvalues(cs, 0); /* push nested captures */ + lua_call(L, n + 2, LUA_MULTRET); /* call dynamic function */ + if (id > 0) { /* are there old dynamic captures to be removed? */ + int i; + for (i = id; i <= otop; i++) + lua_remove(L, id); /* remove old dynamic captures */ + *rem = otop - id + 1; /* total number of dynamic captures removed */ + } + else + *rem = 0; /* no dynamic captures removed */ + return close - open; /* number of captures of all kinds removed */ } - +/* +** Auxiliary structure for substitution and string captures: keep +** information about nested captures for future use, avoiding to push +** string results into Lua +*/ typedef struct StrAux { - int isstring; + int isstring; /* whether capture is a string */ union { - Capture *cp; - struct { - const char *s; - const char *e; + Capture *cp; /* if not a string, respective capture */ + struct { /* if it is a string... */ + const char *s; /* ... starts here */ + const char *e; /* ... ends here */ } s; } u; } StrAux; #define MAXSTRCAPS 10 +/* +** Collect values from current capture into array 'cps'. Current +** capture must be Cstring (first call) or Csimple (recursive calls). +** (In first call, fills %0 with whole match for Cstring.) +** Returns number of elements in the array that were filled. +*/ static int getstrcaps (CapState *cs, StrAux *cps, int n) { int k = n++; - cps[k].isstring = 1; - cps[k].u.s.s = cs->cap->s; - if (!isfullcap(cs->cap++)) { - while (!isclosecap(cs->cap)) { + cps[k].isstring = 1; /* get string value */ + cps[k].u.s.s = cs->cap->s; /* starts here */ + if (!isfullcap(cs->cap++)) { /* nested captures? */ + while (!isclosecap(cs->cap)) { /* traverse them */ if (n >= MAXSTRCAPS) /* too many captures? */ - cs->cap = nextcap(cs->cap); /* skip it */ - else if (captype(cs->cap) == Csimple) - n = getstrcaps(cs, cps, n); + nextcap(cs); /* skip extra captures (will not need them) */ + else if (captype(cs->cap) == Csimple) /* string? */ + n = getstrcaps(cs, cps, n); /* put info. into array */ else { - cps[n].isstring = 0; - cps[n].u.cp = cs->cap; - cs->cap = nextcap(cs->cap); + cps[n].isstring = 0; /* not a string */ + cps[n].u.cp = cs->cap; /* keep original capture */ + nextcap(cs); n++; } } cs->cap++; /* skip close */ } - cps[k].u.s.e = closeaddr(cs->cap - 1); + cps[k].u.s.e = closeaddr(cs->cap - 1); /* ends here */ return n; } /* -** add next capture (which should be a string) to buffer +** add next capture value (which should be a string) to buffer 'b' */ static int addonestring (luaL_Buffer *b, CapState *cs, const char *what); +/* +** String capture: add result to buffer 'b' (instead of pushing +** it into the stack) +*/ static void stringcap (luaL_Buffer *b, CapState *cs) { StrAux cps[MAXSTRCAPS]; int n; size_t len, i; - const char *c; - updatecache(cs, cs->cap->idx); - c = lua_tolstring(cs->L, subscache(cs), &len); - n = getstrcaps(cs, cps, 0) - 1; - for (i = 0; i < len; i++) { - if (c[i] != '%' || c[++i] < '0' || c[i] > '9') - luaL_addchar(b, c[i]); + const char *fmt; /* format string */ + fmt = lua_tolstring(cs->L, updatecache(cs, cs->cap->idx), &len); + n = getstrcaps(cs, cps, 0) - 1; /* collect nested captures */ + for (i = 0; i < len; i++) { /* traverse them */ + if (fmt[i] != '%') /* not an escape? */ + luaL_addchar(b, fmt[i]); /* add it to buffer */ + else if (fmt[++i] < '0' || fmt[i] > '9') /* not followed by a digit? */ + luaL_addchar(b, fmt[i]); /* add to buffer */ else { - int l = c[i] - '0'; + int l = fmt[i] - '0'; /* capture index */ if (l > n) luaL_error(cs->L, "invalid capture index (%d)", l); else if (cps[l].isstring) luaL_addlstring(b, cps[l].u.s.s, cps[l].u.s.e - cps[l].u.s.s); else { Capture *curr = cs->cap; - cs->cap = cps[l].u.cp; - if (addonestring(b, cs, "capture") == 0) + cs->cap = cps[l].u.cp; /* go back to evaluate that nested capture */ + if (!addonestring(b, cs, "capture")) luaL_error(cs->L, "no values in capture index %d", l); - cs->cap = curr; + cs->cap = curr; /* continue from where it stopped */ } } } } +/* +** Substitution capture: add result to buffer 'b' +*/ static void substcap (luaL_Buffer *b, CapState *cs) { const char *curr = cs->cap->s; if (isfullcap(cs->cap)) /* no nested captures? */ luaL_addlstring(b, curr, cs->cap->siz - 1); /* keep original text */ else { - cs->cap++; - while (!isclosecap(cs->cap)) { + cs->cap++; /* skip open entry */ + while (!isclosecap(cs->cap)) { /* traverse nested captures */ const char *next = cs->cap->s; luaL_addlstring(b, curr, next - curr); /* add text up to capture */ - if (addonestring(b, cs, "replacement") == 0) /* no capture value? */ - curr = next; /* keep original text in final result */ - else + if (addonestring(b, cs, "replacement")) curr = closeaddr(cs->cap - 1); /* continue after match */ + else /* no capture value */ + curr = next; /* keep original text in final result */ } luaL_addlstring(b, curr, cs->cap->s - curr); /* add last piece of text */ } @@ -2139,6 +1985,10 @@ static void substcap (luaL_Buffer *b, CapState *cs) { } +/* +** Evaluates a capture and adds its first value to buffer 'b'; returns +** whether there was a value +*/ static int addonestring (luaL_Buffer *b, CapState *cs, const char *what) { switch (captype(cs->cap)) { case Cstring: @@ -2162,11 +2012,16 @@ static int addonestring (luaL_Buffer *b, CapState *cs, const char *what) { } +/* +** Push all values of the current capture into the stack; returns +** number of values pushed +*/ static int pushcapture (CapState *cs) { - luaL_checkstack(cs->L, 4, "too many captures"); + lua_State *L = cs->L; + luaL_checkstack(L, 4, "too many captures"); switch (captype(cs->cap)) { case Cposition: { - lua_pushinteger(cs->L, cs->cap->s - cs->s + 1); + lua_pushinteger(L, cs->cap->s - cs->s + 1); cs->cap++; return 1; } @@ -2178,50 +2033,45 @@ static int pushcapture (CapState *cs) { case Carg: { int arg = (cs->cap++)->idx; if (arg + FIXEDARGS > cs->ptop) - return luaL_error(cs->L, "reference to absent argument #%d", arg); - lua_pushvalue(cs->L, arg + FIXEDARGS); + return luaL_error(L, "reference to absent argument #%d", arg); + lua_pushvalue(L, arg + FIXEDARGS); return 1; } case Csimple: { - int k = pushallvalues(cs, 1); - if (k > 1) - lua_insert(cs->L, -k); /* whole match is first result */ + int k = pushnestedvalues(cs, 1); + lua_insert(L, -k); /* make whole match be first result */ return k; } case Cruntime: { - int n = 0; - while (!isclosecap(cs->cap++)) { - luaL_checkstack(cs->L, 4, "too many captures"); - lua_pushvalue(cs->L, (cs->cap - 1)->idx); - n++; - } - return n; + lua_pushvalue(L, (cs->cap++)->idx); /* value is in the stack */ + return 1; } case Cstring: { luaL_Buffer b; - luaL_buffinit(cs->L, &b); + luaL_buffinit(L, &b); stringcap(&b, cs); luaL_pushresult(&b); return 1; } case Csubst: { luaL_Buffer b; - luaL_buffinit(cs->L, &b); + luaL_buffinit(L, &b); substcap(&b, cs); luaL_pushresult(&b); return 1; } case Cgroup: { if (cs->cap->idx == 0) /* anonymous group? */ - return pushallvalues(cs, 0); /* add all nested values */ + return pushnestedvalues(cs, 0); /* add all nested values */ else { /* named group: add no values */ - cs->cap = nextcap(cs->cap); /* skip capture */ + nextcap(cs); /* skip capture */ return 0; } } case Cbackref: return backrefcap(cs); case Ctable: return tablecap(cs); case Cfunction: return functioncap(cs); + case Cnum: return numcap(cs); case Cquery: return querycap(cs); case Cfold: return foldcap(cs); default: assert(0); return 0; @@ -2229,7 +2079,15 @@ static int pushcapture (CapState *cs) { } -static int getcaptures (lua_State *L, const char *s, const char *r, int ptop) { +/* +** Prepare a CapState structure and traverse the entire list of +** captures in the stack pushing its results. 's' is the subject +** string, 'r' is the final position of the match, and 'ptop' +** the index in the stack where some useful values were pushed. +** Returns the number of results pushed. (If the list produces no +** results, push the final position of the match.) +*/ +int getcaptures (lua_State *L, const char *s, const char *r, int ptop) { Capture *capture = (Capture *)lua_touserdata(L, caplistidx(ptop)); int n = 0; if (!isclosecap(capture)) { /* is there any capture? */ @@ -2247,16 +2105,1137 @@ static int getcaptures (lua_State *L, const char *s, const char *r, int ptop) { return n; } + +/* +** $Id: lptree.c,v 1.10 2013/04/12 16:30:33 roberto Exp $ +** Copyright 2013, Lua.org & PUC-Rio (see 'lpeg.html' for license) +*/ + +/* #include <ctype.h> */ +/* #include <limits.h> */ +/* #include <string.h> */ + + +/* #include "lua.h" */ +/* #include "lauxlib.h" */ + +/* #include "lptypes.h" */ +/* #include "lpcap.h" */ +/* #include "lpcode.h" */ +/* #include "lpprint.h" */ +/* #include "lptree.h" */ + + +/* number of siblings for each tree */ +const byte numsiblings[] = { + 0, 0, 0, /* char, set, any */ + 0, 0, /* true, false */ + 1, /* rep */ + 2, 2, /* seq, choice */ + 1, 1, /* not, and */ + 0, 0, 2, 1, /* call, opencall, rule, grammar */ + 1, /* behind */ + 1, 1 /* capture, runtime capture */ +}; + + +static TTree *newgrammar (lua_State *L, int arg); + + +/* +** returns a reasonable name for value at index 'idx' on the stack +*/ +static const char *val2str (lua_State *L, int idx) { + const char *k = lua_tostring(L, idx); + if (k != NULL) + return lua_pushfstring(L, "%s", k); + else + return lua_pushfstring(L, "(a %s)", luaL_typename(L, idx)); +} + + +/* +** Fix a TOpenCall into a TCall node, using table 'postable' to +** translate a key to its rule address in the tree. Raises an +** error if key does not exist. +*/ +static void fixonecall (lua_State *L, int postable, TTree *g, TTree *t) { + int n; + lua_rawgeti(L, -1, t->key); /* get rule's name */ + lua_gettable(L, postable); /* query name in position table */ + n = lua_tonumber(L, -1); /* get (absolute) position */ + lua_pop(L, 1); /* remove position */ + if (n == 0) { /* no position? */ + lua_rawgeti(L, -1, t->key); /* get rule's name again */ + luaL_error(L, "rule '%s' undefined in given grammar", val2str(L, -1)); + } + t->tag = TCall; + t->u.ps = n - (t - g); /* position relative to node */ + assert(sib2(t)->tag == TRule); + sib2(t)->key = t->key; +} + + +/* +** Transform left associative constructions into right +** associative ones, for sequence and choice; that is: +** (t11 + t12) + t2 => t11 + (t12 + t2) +** (t11 * t12) * t2 => t11 * (t12 * t2) +** (that is, Op (Op t11 t12) t2 => Op t11 (Op t12 t2)) +*/ +static void correctassociativity (TTree *tree) { + TTree *t1 = sib1(tree); + assert(tree->tag == TChoice || tree->tag == TSeq); + while (t1->tag == tree->tag) { + int n1size = tree->u.ps - 1; /* t1 == Op t11 t12 */ + int n11size = t1->u.ps - 1; + int n12size = n1size - n11size - 1; + memmove(sib1(tree), sib1(t1), n11size * sizeof(TTree)); /* move t11 */ + tree->u.ps = n11size + 1; + sib2(tree)->tag = tree->tag; + sib2(tree)->u.ps = n12size + 1; + } +} + + +/* +** Make final adjustments in a tree. Fix open calls in tree 't', +** making them refer to their respective rules or raising appropriate +** errors (if not inside a grammar). Correct associativity of associative +** constructions (making them right associative). Assume that tree's +** ktable is at the top of the stack (for error messages). +*/ +static void finalfix (lua_State *L, int postable, TTree *g, TTree *t) { + tailcall: + switch (t->tag) { + case TGrammar: /* subgrammars were already fixed */ + return; + case TOpenCall: { + if (g != NULL) /* inside a grammar? */ + fixonecall(L, postable, g, t); + else { /* open call outside grammar */ + lua_rawgeti(L, -1, t->key); + luaL_error(L, "rule '%s' used outside a grammar", val2str(L, -1)); + } + break; + } + case TSeq: case TChoice: + correctassociativity(t); + break; + } + switch (numsiblings[t->tag]) { + case 1: /* finalfix(L, postable, g, sib1(t)); */ + t = sib1(t); goto tailcall; + case 2: + finalfix(L, postable, g, sib1(t)); + t = sib2(t); goto tailcall; /* finalfix(L, postable, g, sib2(t)); */ + default: assert(numsiblings[t->tag] == 0); break; + } +} + + +/* +** {====================================================== +** Tree generation +** ======================================================= +*/ + +/* +** In 5.2, could use 'luaL_testudata'... +*/ +static int testpattern (lua_State *L, int idx) { + if (lua_touserdata(L, idx)) { /* value is a userdata? */ + if (lua_getmetatable(L, idx)) { /* does it have a metatable? */ + luaL_getmetatable(L, PATTERN_T); + if (lua_rawequal(L, -1, -2)) { /* does it have the correct mt? */ + lua_pop(L, 2); /* remove both metatables */ + return 1; + } + } + } + return 0; +} + + +static Pattern *getpattern (lua_State *L, int idx) { + return (Pattern *)luaL_checkudata(L, idx, PATTERN_T); +} + + +static int getsize (lua_State *L, int idx) { + return (lua_objlen(L, idx) - sizeof(Pattern)) / sizeof(TTree) + 1; +} + + +static TTree *gettree (lua_State *L, int idx, int *len) { + Pattern *p = getpattern(L, idx); + if (len) + *len = getsize(L, idx); + return p->tree; +} + + +/* +** create a pattern +*/ +static TTree *newtree (lua_State *L, int len) { + size_t size = (len - 1) * sizeof(TTree) + sizeof(Pattern); + Pattern *p = (Pattern *)lua_newuserdata(L, size); + luaL_getmetatable(L, PATTERN_T); + lua_setmetatable(L, -2); + p->code = NULL; p->codesize = 0; + return p->tree; +} + + +static TTree *newleaf (lua_State *L, int tag) { + TTree *tree = newtree(L, 1); + tree->tag = tag; + return tree; +} + + +static TTree *newcharset (lua_State *L) { + TTree *tree = newtree(L, bytes2slots(CHARSETSIZE) + 1); + tree->tag = TSet; + loopset(i, treebuffer(tree)[i] = 0); + return tree; +} + + +/* +** add to tree a sequence where first sibling is 'sib' (with size +** 'sibsize'); returns position for second sibling +*/ +static TTree *seqaux (TTree *tree, TTree *sib, int sibsize) { + tree->tag = TSeq; tree->u.ps = sibsize + 1; + memcpy(sib1(tree), sib, sibsize * sizeof(TTree)); + return sib2(tree); +} + + +/* +** Add element 'idx' to 'ktable' of pattern at the top of the stack; +** create new 'ktable' if necessary. Return index of new element. +*/ +static int addtoktable (lua_State *L, int idx) { + if (idx == 0 || lua_isnil(L, idx)) /* no actual value to insert? */ + return 0; + else { + int n; + lua_getfenv(L, -1); /* get ktable from pattern */ + n = lua_objlen(L, -1); + if (n == 0) { /* is it empty/non-existent? */ + lua_pop(L, 1); /* remove it */ + lua_createtable(L, 1, 0); /* create a fresh table */ + } + lua_pushvalue(L, idx); /* element to be added */ + lua_rawseti(L, -2, n + 1); + lua_setfenv(L, -2); /* set it as ktable for pattern */ + return n + 1; + } +} + + +/* +** Build a sequence of 'n' nodes, each with tag 'tag' and 'u.n' got +** from the array 's' (or 0 if array is NULL). (TSeq is binary, so it +** must build a sequence of sequence of sequence...) +*/ +static void fillseq (TTree *tree, int tag, int n, const char *s) { + int i; + for (i = 0; i < n - 1; i++) { /* initial n-1 copies of Seq tag; Seq ... */ + tree->tag = TSeq; tree->u.ps = 2; + sib1(tree)->tag = tag; + sib1(tree)->u.n = s ? (byte)s[i] : 0; + tree = sib2(tree); + } + tree->tag = tag; /* last one does not need TSeq */ + tree->u.n = s ? (byte)s[i] : 0; +} + + +/* +** Numbers as patterns: +** 0 == true (always match); n == TAny repeated 'n' times; +** -n == not (TAny repeated 'n' times) +*/ +static TTree *numtree (lua_State *L, int n) { + if (n == 0) + return newleaf(L, TTrue); + else { + TTree *tree, *nd; + if (n > 0) + tree = nd = newtree(L, 2 * n - 1); + else { /* negative: code it as !(-n) */ + n = -n; + tree = newtree(L, 2 * n); + tree->tag = TNot; + nd = sib1(tree); + } + fillseq(nd, TAny, n, NULL); /* sequence of 'n' any's */ + return tree; + } +} + + +/* +** Convert value at index 'idx' to a pattern +*/ +static TTree *getpatt (lua_State *L, int idx, int *len) { + TTree *tree; + switch (lua_type(L, idx)) { + case LUA_TSTRING: { + size_t slen; + const char *s = lua_tolstring(L, idx, &slen); /* get string */ + if (slen == 0) /* empty? */ + tree = newleaf(L, TTrue); /* always match */ + else { + tree = newtree(L, 2 * (slen - 1) + 1); + fillseq(tree, TChar, slen, s); /* sequence of 'slen' chars */ + } + break; + } + case LUA_TNUMBER: { + int n = lua_tointeger(L, idx); + tree = numtree(L, n); + break; + } + case LUA_TBOOLEAN: { + tree = (lua_toboolean(L, idx) ? newleaf(L, TTrue) : newleaf(L, TFalse)); + break; + } + case LUA_TTABLE: { + tree = newgrammar(L, idx); + break; + } + case LUA_TFUNCTION: { + tree = newtree(L, 2); + tree->tag = TRunTime; + tree->key = addtoktable(L, idx); + sib1(tree)->tag = TTrue; + break; + } + default: { + return gettree(L, idx, len); + } + } + lua_replace(L, idx); /* put new tree into 'idx' slot */ + if (len) + *len = getsize(L, idx); + return tree; +} + + +/* +** Return the number of elements in the ktable of pattern at 'idx'. +** In Lua 5.2, default "environment" for patterns is nil, not +** a table. Treat it as an empty table. In Lua 5.1, assumes that +** the environment has no numeric indices (len == 0) +*/ +static int ktablelen (lua_State *L, int idx) { + if (!lua_istable(L, idx)) return 0; + else return lua_objlen(L, idx); +} + + +/* +** Concatentate the contents of table 'idx1' into table 'idx2'. +** (Assume that both indices are negative.) +** Return the original length of table 'idx2' +*/ +static int concattable (lua_State *L, int idx1, int idx2) { + int i; + int n1 = ktablelen(L, idx1); + int n2 = ktablelen(L, idx2); + if (n1 == 0) return 0; /* nothing to correct */ + for (i = 1; i <= n1; i++) { + lua_rawgeti(L, idx1, i); + lua_rawseti(L, idx2 - 1, n2 + i); /* correct 'idx2' */ + } + return n2; +} + + +/* +** Make a merge of ktables from p1 and p2 the ktable for the new +** pattern at the top of the stack. +*/ +static int joinktables (lua_State *L, int p1, int p2) { + int n1, n2; + lua_getfenv(L, p1); /* get ktables */ + lua_getfenv(L, p2); + n1 = ktablelen(L, -2); + n2 = ktablelen(L, -1); + if (n1 == 0 && n2 == 0) { /* are both tables empty? */ + lua_pop(L, 2); /* nothing to be done; pop tables */ + return 0; /* nothing to correct */ + } + if (n2 == 0 || lua_equal(L, -2, -1)) { /* second table is empty or equal? */ + lua_pop(L, 1); /* pop 2nd table */ + lua_setfenv(L, -2); /* set 1st ktable into new pattern */ + return 0; /* nothing to correct */ + } + if (n1 == 0) { /* first table is empty? */ + lua_setfenv(L, -3); /* set 2nd table into new pattern */ + lua_pop(L, 1); /* pop 1st table */ + return 0; /* nothing to correct */ + } + else { + lua_createtable(L, n1 + n2, 0); /* create ktable for new pattern */ + /* stack: new p; ktable p1; ktable p2; new ktable */ + concattable(L, -3, -1); /* from p1 into new ktable */ + concattable(L, -2, -1); /* from p2 into new ktable */ + lua_setfenv(L, -4); /* new ktable becomes p env */ + lua_pop(L, 2); /* pop other ktables */ + return n1; /* correction for indices from p2 */ + } +} + + +static void correctkeys (TTree *tree, int n) { + if (n == 0) return; /* no correction? */ + tailcall: + switch (tree->tag) { + case TOpenCall: case TCall: case TRunTime: case TRule: { + if (tree->key > 0) + tree->key += n; + break; + } + case TCapture: { + if (tree->key > 0 && tree->cap != Carg && tree->cap != Cnum) + tree->key += n; + break; + } + default: break; + } + switch (numsiblings[tree->tag]) { + case 1: /* correctkeys(sib1(tree), n); */ + tree = sib1(tree); goto tailcall; + case 2: + correctkeys(sib1(tree), n); + tree = sib2(tree); goto tailcall; /* correctkeys(sib2(tree), n); */ + default: assert(numsiblings[tree->tag] == 0); break; + } +} + + +/* +** copy 'ktable' of element 'idx' to new tree (on top of stack) +*/ +static void copyktable (lua_State *L, int idx) { + lua_getfenv(L, idx); + lua_setfenv(L, -2); +} + + +/* +** merge 'ktable' from rule at stack index 'idx' into 'ktable' +** from tree at the top of the stack, and correct corresponding +** tree. +*/ +static void mergektable (lua_State *L, int idx, TTree *rule) { + int n; + lua_getfenv(L, -1); /* get ktables */ + lua_getfenv(L, idx); + n = concattable(L, -1, -2); + lua_pop(L, 2); /* remove both ktables */ + correctkeys(rule, n); +} + + +/* +** create a new tree, whith a new root and one sibling. +** Sibling must be on the Lua stack, at index 1. +*/ +static TTree *newroot1sib (lua_State *L, int tag) { + int s1; + TTree *tree1 = getpatt(L, 1, &s1); + TTree *tree = newtree(L, 1 + s1); /* create new tree */ + tree->tag = tag; + memcpy(sib1(tree), tree1, s1 * sizeof(TTree)); + copyktable(L, 1); + return tree; +} + + +/* +** create a new tree, whith a new root and 2 siblings. +** Siblings must be on the Lua stack, first one at index 1. +*/ +static TTree *newroot2sib (lua_State *L, int tag) { + int s1, s2; + TTree *tree1 = getpatt(L, 1, &s1); + TTree *tree2 = getpatt(L, 2, &s2); + TTree *tree = newtree(L, 1 + s1 + s2); /* create new tree */ + tree->tag = tag; + tree->u.ps = 1 + s1; + memcpy(sib1(tree), tree1, s1 * sizeof(TTree)); + memcpy(sib2(tree), tree2, s2 * sizeof(TTree)); + correctkeys(sib2(tree), joinktables(L, 1, 2)); + return tree; +} + + +static int lp_P (lua_State *L) { + luaL_checkany(L, 1); + getpatt(L, 1, NULL); + lua_settop(L, 1); + return 1; +} + + +/* +** sequence operator; optimizations: +** false x => false, x true => x, true x => x +** (cannot do x . false => false because x may have runtime captures) +*/ +static int lp_seq (lua_State *L) { + TTree *tree1 = getpatt(L, 1, NULL); + TTree *tree2 = getpatt(L, 2, NULL); + if (tree1->tag == TFalse || tree2->tag == TTrue) + lua_pushvalue(L, 1); /* false . x == false, x . true = x */ + else if (tree1->tag == TTrue) + lua_pushvalue(L, 2); /* true . x = x */ + else + newroot2sib(L, TSeq); + return 1; +} + + +/* +** choice operator; optimizations: +** charset / charset => charset +** true / x => true, x / false => x, false / x => x +** (x / true is not equivalent to true) +*/ +static int lp_choice (lua_State *L) { + Charset st1, st2; + TTree *t1 = getpatt(L, 1, NULL); + TTree *t2 = getpatt(L, 2, NULL); + if (tocharset(t1, &st1) && tocharset(t2, &st2)) { + TTree *t = newcharset(L); + loopset(i, treebuffer(t)[i] = st1.cs[i] | st2.cs[i]); + } + else if (nofail(t1) || t2->tag == TFalse) + lua_pushvalue(L, 1); /* true / x => true, x / false => x */ + else if (t1->tag == TFalse) + lua_pushvalue(L, 2); /* false / x => x */ + else + newroot2sib(L, TChoice); + return 1; +} + + +/* +** p^n +*/ +static int lp_star (lua_State *L) { + int size1; + int n = luaL_checkint(L, 2); + TTree *tree1 = gettree(L, 1, &size1); + if (n >= 0) { /* seq tree1 (seq tree1 ... (seq tree1 (rep tree1))) */ + TTree *tree = newtree(L, (n + 1) * (size1 + 1)); + if (nullable(tree1)) + luaL_error(L, "loop body may accept empty string"); + while (n--) /* repeat 'n' times */ + tree = seqaux(tree, tree1, size1); + tree->tag = TRep; + memcpy(sib1(tree), tree1, size1 * sizeof(TTree)); + } + else { /* choice (seq tree1 ... choice tree1 true ...) true */ + TTree *tree; + n = -n; + /* size = (choice + seq + tree1 + true) * n, but the last has no seq */ + tree = newtree(L, n * (size1 + 3) - 1); + for (; n > 1; n--) { /* repeat (n - 1) times */ + tree->tag = TChoice; tree->u.ps = n * (size1 + 3) - 2; + sib2(tree)->tag = TTrue; + tree = sib1(tree); + tree = seqaux(tree, tree1, size1); + } + tree->tag = TChoice; tree->u.ps = size1 + 1; + sib2(tree)->tag = TTrue; + memcpy(sib1(tree), tree1, size1 * sizeof(TTree)); + } + copyktable(L, 1); + return 1; +} + + +/* +** #p == &p +*/ +static int lp_and (lua_State *L) { + newroot1sib(L, TAnd); + return 1; +} + + +/* +** -p == !p +*/ +static int lp_not (lua_State *L) { + newroot1sib(L, TNot); + return 1; +} + + +/* +** [t1 - t2] == Seq (Not t2) t1 +** If t1 and t2 are charsets, make their difference. +*/ +static int lp_sub (lua_State *L) { + Charset st1, st2; + int s1, s2; + TTree *t1 = getpatt(L, 1, &s1); + TTree *t2 = getpatt(L, 2, &s2); + if (tocharset(t1, &st1) && tocharset(t2, &st2)) { + TTree *t = newcharset(L); + loopset(i, treebuffer(t)[i] = st1.cs[i] & ~st2.cs[i]); + } + else { + TTree *tree = newtree(L, 2 + s1 + s2); + tree->tag = TSeq; /* sequence of... */ + tree->u.ps = 2 + s2; + sib1(tree)->tag = TNot; /* ...not... */ + memcpy(sib1(sib1(tree)), t2, s2 * sizeof(TTree)); /* ...t2 */ + memcpy(sib2(tree), t1, s1 * sizeof(TTree)); /* ... and t1 */ + correctkeys(sib1(tree), joinktables(L, 1, 2)); + } + return 1; +} + + +static int lp_set (lua_State *L) { + size_t l; + const char *s = luaL_checklstring(L, 1, &l); + TTree *tree = newcharset(L); + while (l--) { + setchar(treebuffer(tree), (byte)(*s)); + s++; + } + return 1; +} + + +static int lp_range (lua_State *L) { + int arg; + int top = lua_gettop(L); + TTree *tree = newcharset(L); + for (arg = 1; arg <= top; arg++) { + int c; + size_t l; + const char *r = luaL_checklstring(L, arg, &l); + luaL_argcheck(L, l == 2, arg, "range must have two characters"); + for (c = (byte)r[0]; c <= (byte)r[1]; c++) + setchar(treebuffer(tree), c); + } + return 1; +} + + +/* +** Look-behind predicate +*/ +static int lp_behind (lua_State *L) { + TTree *tree; + TTree *tree1 = getpatt(L, 1, NULL); + int n = fixedlen(tree1); + luaL_argcheck(L, !hascaptures(tree1), 1, "pattern have captures"); + luaL_argcheck(L, n > 0, 1, "pattern may not have fixed length"); + luaL_argcheck(L, n <= MAXBEHIND, 1, "pattern too long to look behind"); + tree = newroot1sib(L, TBehind); + tree->u.n = n; + return 1; +} + + +/* +** Create a non-terminal +*/ +static int lp_V (lua_State *L) { + TTree *tree = newleaf(L, TOpenCall); + luaL_argcheck(L, !lua_isnoneornil(L, 1), 1, "non-nil value expected"); + tree->key = addtoktable(L, 1); + return 1; +} + + +/* +** Create a tree for a non-empty capture, with a body and +** optionally with an associated Lua value (at index 'labelidx' in the +** stack) +*/ +static int capture_aux (lua_State *L, int cap, int labelidx) { + TTree *tree = newroot1sib(L, TCapture); + tree->cap = cap; + tree->key = addtoktable(L, labelidx); + return 1; +} + + +/* +** Fill a tree with an empty capture, using an empty (TTrue) sibling. +*/ +static TTree *auxemptycap (lua_State *L, TTree *tree, int cap, int idx) { + tree->tag = TCapture; + tree->cap = cap; + tree->key = addtoktable(L, idx); + sib1(tree)->tag = TTrue; + return tree; +} + + +/* +** Create a tree for an empty capture +*/ +static TTree *newemptycap (lua_State *L, int cap, int idx) { + return auxemptycap(L, newtree(L, 2), cap, idx); +} + + +/* +** Captures with syntax p / v +** (function capture, query capture, string capture, or number capture) +*/ +static int lp_divcapture (lua_State *L) { + switch (lua_type(L, 2)) { + case LUA_TFUNCTION: return capture_aux(L, Cfunction, 2); + case LUA_TTABLE: return capture_aux(L, Cquery, 2); + case LUA_TSTRING: return capture_aux(L, Cstring, 2); + case LUA_TNUMBER: { + int n = lua_tointeger(L, 2); + TTree *tree = newroot1sib(L, TCapture); + luaL_argcheck(L, 0 <= n && n <= SHRT_MAX, 1, "invalid number"); + tree->cap = Cnum; + tree->key = n; + return 1; + } + default: return luaL_argerror(L, 2, "invalid replacement value"); + } +} + + +static int lp_substcapture (lua_State *L) { + return capture_aux(L, Csubst, 0); +} + + +static int lp_tablecapture (lua_State *L) { + return capture_aux(L, Ctable, 0); +} + + +static int lp_groupcapture (lua_State *L) { + if (lua_isnoneornil(L, 2)) + return capture_aux(L, Cgroup, 0); + else { + luaL_checkstring(L, 2); + return capture_aux(L, Cgroup, 2); + } +} + + +static int lp_foldcapture (lua_State *L) { + luaL_checktype(L, 2, LUA_TFUNCTION); + return capture_aux(L, Cfold, 2); +} + + +static int lp_simplecapture (lua_State *L) { + return capture_aux(L, Csimple, 0); +} + + +static int lp_poscapture (lua_State *L) { + newemptycap(L, Cposition, 0); + return 1; +} + + +static int lp_argcapture (lua_State *L) { + int n = luaL_checkint(L, 1); + TTree *tree = newemptycap(L, Carg, 0); + tree->key = n; + luaL_argcheck(L, 0 < n && n <= SHRT_MAX, 1, "invalid argument index"); + return 1; +} + + +static int lp_backref (lua_State *L) { + luaL_checkstring(L, 1); + newemptycap(L, Cbackref, 1); + return 1; +} + + +/* +** Constant capture +*/ +static int lp_constcapture (lua_State *L) { + int i; + int n = lua_gettop(L); /* number of values */ + if (n == 0) /* no values? */ + newleaf(L, TTrue); /* no capture */ + else if (n == 1) + newemptycap(L, Cconst, 1); /* single constant capture */ + else { /* create a group capture with all values */ + TTree *tree = newtree(L, 1 + 3 * (n - 1) + 2); + tree->tag = TCapture; + tree->cap = Cgroup; + tree->key = 0; + tree = sib1(tree); + for (i = 1; i <= n - 1; i++) { + tree->tag = TSeq; + tree->u.ps = 3; /* skip TCapture and its sibling */ + auxemptycap(L, sib1(tree), Cconst, i); + tree = sib2(tree); + } + auxemptycap(L, tree, Cconst, i); + } + return 1; +} + + +static int lp_matchtime (lua_State *L) { + TTree *tree; + luaL_checktype(L, 2, LUA_TFUNCTION); + tree = newroot1sib(L, TRunTime); + tree->key = addtoktable(L, 2); + return 1; +} + /* }====================================================== */ -static int version_l (lua_State *L) { +/* +** {====================================================== +** Grammar - Tree generation +** ======================================================= +*/ + +/* +** push on the stack the index and the pattern for the +** initial rule of grammar at index 'arg' in the stack; +** also add that index into position table. +*/ +static void getfirstrule (lua_State *L, int arg, int postab) { + lua_rawgeti(L, arg, 1); /* access first element */ + if (lua_isstring(L, -1)) { /* is it the name of initial rule? */ + lua_pushvalue(L, -1); /* duplicate it to use as key */ + lua_gettable(L, arg); /* get associated rule */ + } + else { + lua_pushinteger(L, 1); /* key for initial rule */ + lua_insert(L, -2); /* put it before rule */ + } + if (!testpattern(L, -1)) { /* initial rule not a pattern? */ + if (lua_isnil(L, -1)) + luaL_error(L, "grammar has no initial rule"); + else + luaL_error(L, "initial rule '%s' is not a pattern", lua_tostring(L, -2)); + } + lua_pushvalue(L, -2); /* push key */ + lua_pushinteger(L, 1); /* push rule position (after TGrammar) */ + lua_settable(L, postab); /* insert pair at position table */ +} + +/* +** traverse grammar at index 'arg', pushing all its keys and patterns +** into the stack. Create a new table (before all pairs key-pattern) to +** collect all keys and their associated positions in the final tree +** (the "position table"). +** Return the number of rules and (in 'totalsize') the total size +** for the new tree. +*/ +static int collectrules (lua_State *L, int arg, int *totalsize) { + int n = 1; /* to count number of rules */ + int postab = lua_gettop(L) + 1; /* index of position table */ + int size; /* accumulator for total size */ + lua_newtable(L); /* create position table */ + getfirstrule(L, arg, postab); + size = 2 + getsize(L, postab + 2); /* TGrammar + TRule + rule */ + lua_pushnil(L); /* prepare to traverse grammar table */ + while (lua_next(L, arg) != 0) { + if (lua_tonumber(L, -2) == 1 || + lua_equal(L, -2, postab + 1)) { /* initial rule? */ + lua_pop(L, 1); /* remove value (keep key for lua_next) */ + continue; + } + if (!testpattern(L, -1)) /* value is not a pattern? */ + luaL_error(L, "rule '%s' is not a pattern", val2str(L, -2)); + luaL_checkstack(L, LUA_MINSTACK, "grammar has too many rules"); + lua_pushvalue(L, -2); /* push key (to insert into position table) */ + lua_pushinteger(L, size); + lua_settable(L, postab); + size += 1 + getsize(L, -1); /* update size */ + lua_pushvalue(L, -2); /* push key (for next lua_next) */ + n++; + } + *totalsize = size + 1; /* TTrue to finish list of rules */ + return n; +} + + +static void buildgrammar (lua_State *L, TTree *grammar, int frule, int n) { + int i; + TTree *nd = sib1(grammar); /* auxiliary pointer to traverse the tree */ + for (i = 0; i < n; i++) { /* add each rule into new tree */ + int ridx = frule + 2*i + 1; /* index of i-th rule */ + int rulesize; + TTree *rn = gettree(L, ridx, &rulesize); + nd->tag = TRule; + nd->key = 0; + nd->cap = i; /* rule number */ + nd->u.ps = rulesize + 1; /* point to next rule */ + memcpy(sib1(nd), rn, rulesize * sizeof(TTree)); /* copy rule */ + mergektable(L, ridx, sib1(nd)); /* merge its ktable into new one */ + nd = sib2(nd); /* move to next rule */ + } + nd->tag = TTrue; /* finish list of rules */ +} + + +/* +** Check whether a tree has potential infinite loops +*/ +static int checkloops (TTree *tree) { + tailcall: + if (tree->tag == TRep && nullable(sib1(tree))) + return 1; + else if (tree->tag == TGrammar) + return 0; /* sub-grammars already checked */ + else { + switch (numsiblings[tree->tag]) { + case 1: /* return checkloops(sib1(tree)); */ + tree = sib1(tree); goto tailcall; + case 2: + if (checkloops(sib1(tree))) return 1; + /* else return checkloops(sib2(tree)); */ + tree = sib2(tree); goto tailcall; + default: assert(numsiblings[tree->tag] == 0); return 0; + } + } +} + + +static int verifyerror (lua_State *L, int *passed, int npassed) { + int i, j; + for (i = npassed - 1; i >= 0; i--) { /* search for a repetition */ + for (j = i - 1; j >= 0; j--) { + if (passed[i] == passed[j]) { + lua_rawgeti(L, -1, passed[i]); /* get rule's key */ + return luaL_error(L, "rule '%s' may be left recursive", val2str(L, -1)); + } + } + } + return luaL_error(L, "too many left calls in grammar"); +} + + +/* +** Check whether a rule can be left recursive; raise an error in that +** case; otherwise return 1 iff pattern is nullable. Assume ktable at +** the top of the stack. +*/ +static int verifyrule (lua_State *L, TTree *tree, int *passed, int npassed, + int nullable) { + tailcall: + switch (tree->tag) { + case TChar: case TSet: case TAny: + case TFalse: + return nullable; /* cannot pass from here */ + case TTrue: + case TBehind: /* look-behind cannot have calls */ + return 1; + case TNot: case TAnd: case TRep: + /* return verifyrule(L, sib1(tree), passed, npassed, 1); */ + tree = sib1(tree); nullable = 1; goto tailcall; + case TCapture: case TRunTime: + /* return verifyrule(L, sib1(tree), passed, npassed); */ + tree = sib1(tree); goto tailcall; + case TCall: + /* return verifyrule(L, sib2(tree), passed, npassed); */ + tree = sib2(tree); goto tailcall; + case TSeq: /* only check 2nd child if first is nullable */ + if (!verifyrule(L, sib1(tree), passed, npassed, 0)) + return nullable; + /* else return verifyrule(L, sib2(tree), passed, npassed); */ + tree = sib2(tree); goto tailcall; + case TChoice: /* must check both children */ + nullable = verifyrule(L, sib1(tree), passed, npassed, nullable); + /* return verifyrule(L, sib2(tree), passed, npassed, nullable); */ + tree = sib2(tree); goto tailcall; + case TRule: + if (npassed >= MAXRULES) + return verifyerror(L, passed, npassed); + else { + passed[npassed++] = tree->key; + /* return verifyrule(L, sib1(tree), passed, npassed); */ + tree = sib1(tree); goto tailcall; + } + case TGrammar: + return nullable(tree); /* sub-grammar cannot be left recursive */ + default: assert(0); return 0; + } +} + + +static void verifygrammar (lua_State *L, TTree *grammar) { + int passed[MAXRULES]; + TTree *rule; + /* check left-recursive rules */ + for (rule = sib1(grammar); rule->tag == TRule; rule = sib2(rule)) { + if (rule->key == 0) continue; /* unused rule */ + verifyrule(L, sib1(rule), passed, 0, 0); + } + assert(rule->tag == TTrue); + /* check infinite loops inside rules */ + for (rule = sib1(grammar); rule->tag == TRule; rule = sib2(rule)) { + if (rule->key == 0) continue; /* unused rule */ + if (checkloops(sib1(rule))) { + lua_rawgeti(L, -1, rule->key); /* get rule's key */ + luaL_error(L, "empty loop in rule '%s'", val2str(L, -1)); + } + } + assert(rule->tag == TTrue); +} + + +/* +** Give a name for the initial rule if it is not referenced +*/ +static void initialrulename (lua_State *L, TTree *grammar, int frule) { + if (sib1(grammar)->key == 0) { /* initial rule is not referenced? */ + int n = lua_objlen(L, -1) + 1; /* index for name */ + lua_pushvalue(L, frule); /* rule's name */ + lua_rawseti(L, -2, n); /* ktable was on the top of the stack */ + sib1(grammar)->key = n; + } +} + + +static TTree *newgrammar (lua_State *L, int arg) { + int treesize; + int frule = lua_gettop(L) + 2; /* position of first rule's key */ + int n = collectrules(L, arg, &treesize); + TTree *g = newtree(L, treesize); + luaL_argcheck(L, n <= MAXRULES, arg, "grammar has too many rules"); + g->tag = TGrammar; g->u.n = n; + lua_newtable(L); /* create 'ktable' */ + lua_setfenv(L, -2); + buildgrammar(L, g, frule, n); + lua_getfenv(L, -1); /* get 'ktable' for new tree */ + finalfix(L, frule - 1, g, sib1(g)); + initialrulename(L, g, frule); + verifygrammar(L, g); + lua_pop(L, 1); /* remove 'ktable' */ + lua_insert(L, -(n * 2 + 2)); /* move new table to proper position */ + lua_pop(L, n * 2 + 1); /* remove position table + rule pairs */ + return g; /* new table at the top of the stack */ +} + +/* }====================================================== */ + + +static Instruction *prepcompile (lua_State *L, Pattern *p, int idx) { + lua_getfenv(L, idx); /* push 'ktable' (may be used by 'finalfix') */ + finalfix(L, 0, NULL, p->tree); + lua_pop(L, 1); /* remove 'ktable' */ + return compile(L, p); +} + + +static int lp_printtree (lua_State *L) { + TTree *tree = getpatt(L, 1, NULL); + int c = lua_toboolean(L, 2); + if (c) { + lua_getfenv(L, 1); /* push 'ktable' (may be used by 'finalfix') */ + finalfix(L, 0, NULL, tree); + lua_pop(L, 1); /* remove 'ktable' */ + } + printktable(L, 1); + printtree(tree, 0); + return 0; +} + + +static int lp_printcode (lua_State *L) { + Pattern *p = getpattern(L, 1); + printktable(L, 1); + if (p->code == NULL) /* not compiled yet? */ + prepcompile(L, p, 1); + printpatt(p->code, p->codesize); + return 0; +} + + +/* +** Get the initial position for the match, interpreting negative +** values from the end of the subject +*/ +static size_t initposition (lua_State *L, size_t len) { + lua_Integer ii = luaL_optinteger(L, 3, 1); + if (ii > 0) { /* positive index? */ + if ((size_t)ii <= len) /* inside the string? */ + return (size_t)ii - 1; /* return it (corrected to 0-base) */ + else return len; /* crop at the end */ + } + else { /* negative index */ + if ((size_t)(-ii) <= len) /* inside the string? */ + return len - ((size_t)(-ii)); /* return position from the end */ + else return 0; /* crop at the beginning */ + } +} + + +/* +** Main match function +*/ +static int lp_match (lua_State *L) { + Capture capture[INITCAPSIZE]; + const char *r; + size_t l; + Pattern *p = (getpatt(L, 1, NULL), getpattern(L, 1)); + Instruction *code = (p->code != NULL) ? p->code : prepcompile(L, p, 1); + const char *s = luaL_checklstring(L, SUBJIDX, &l); + size_t i = initposition(L, l); + int ptop = lua_gettop(L); + lua_pushnil(L); /* initialize subscache */ + lua_pushlightuserdata(L, capture); /* initialize caplistidx */ + lua_getfenv(L, 1); /* initialize penvidx */ + r = match(L, s, s + i, s + l, code, capture, ptop); + if (r == NULL) { + lua_pushnil(L); + return 1; + } + return getcaptures(L, s, r, ptop); +} + + + +/* +** {====================================================== +** Library creation and functions not related to matching +** ======================================================= +*/ + +static int lp_setmax (lua_State *L) { + luaL_optinteger(L, 1, -1); + lua_settop(L, 1); + lua_setfield(L, LUA_REGISTRYINDEX, MAXSTACKIDX); + return 0; +} + + +static int lp_version (lua_State *L) { lua_pushstring(L, VERSION); return 1; } -static int type_l (lua_State *L) { +static int lp_type (lua_State *L) { if (testpattern(L, 1)) lua_pushliteral(L, "pattern"); else @@ -2265,16 +3244,24 @@ static int type_l (lua_State *L) { } +int lp_gc (lua_State *L) { + Pattern *p = getpattern(L, 1); + if (p->codesize > 0) + reallocprog(L, p, 0); + return 0; +} + + static void createcat (lua_State *L, const char *catname, int (catf) (int)) { - Instruction *p = newcharset(L); + TTree *t = newcharset(L); int i; - for (i = 0; i < CHAR_MAX; i++) - if (catf(i)) setchar(p[1].buff, i); + for (i = 0; i <= UCHAR_MAX; i++) + if (catf(i)) setchar(treebuffer(t), i); lua_setfield(L, -2, catname); } -static int locale_l (lua_State *L) { +static int lp_locale (lua_State *L) { if (lua_isnoneornil(L, 1)) { lua_settop(L, 0); lua_createtable(L, 0, 12); @@ -2298,108 +3285,56 @@ static int locale_l (lua_State *L) { } -static int setmax (lua_State *L) { - luaL_optinteger(L, 1, -1); - lua_settop(L, 1); - lua_setfield(L, LUA_REGISTRYINDEX, MAXSTACKIDX); - return 0; -} - - -static int printpat_l (lua_State *L) { - Instruction *p = getpatt(L, 1, NULL); - int n, i; - lua_getfenv(L, 1); - n = ktablelen(L, -1); - printf("["); - for (i = 1; i <= n; i++) { - printf("%d = ", i); - lua_rawgeti(L, -1, i); - if (lua_isstring(L, -1)) - printf("%s ", lua_tostring(L, -1)); - else - printf("%s ", lua_typename(L, lua_type(L, -1))); - lua_pop(L, 1); - } - printf("]\n"); - printpatt(p); - return 0; -} - - -static int matchl (lua_State *L) { - Capture capture[INITCAPSIZE]; - const char *r; - size_t l; - Instruction *p = getpatt(L, 1, NULL); - const char *s = luaL_checklstring(L, SUBJIDX, &l); - int ptop = lua_gettop(L); - lua_Integer ii = luaL_optinteger(L, 3, 1); - size_t i = (ii > 0) ? - (((size_t)ii <= l) ? (size_t)ii - 1 : l) : - (((size_t)-ii <= l) ? l - ((size_t)-ii) : 0); - lua_pushnil(L); /* subscache */ - lua_pushlightuserdata(L, capture); /* caplistidx */ - lua_getfenv(L, 1); /* penvidx */ - r = match(L, s, s + i, s + l, p, capture, ptop); - if (r == NULL) { - lua_pushnil(L); - return 1; - } - return getcaptures(L, s, r, ptop); -} - - static struct luaL_Reg pattreg[] = { - {"match", matchl}, - {"print", printpat_l}, - {"locale", locale_l}, - {"setmaxstack", setmax}, - {"B", pattbehind}, - {"C", capture_l}, - {"Cf", fold_l}, - {"Cc", capconst_l}, - {"Cg", group_l}, - {"Cp", position_l}, - {"Cb", backref_l}, - {"Carg", argcap_l}, - {"Cmt", matchtime_l}, - {"Cs", capsubst_l}, - {"Ct", tcapture_l}, - {"P", pattern_l}, - {"R", range_l}, - {"S", set_l}, - {"V", nter_l}, - {"type", type_l}, - {"version", version_l}, + {"ptree", lp_printtree}, + {"pcode", lp_printcode}, + {"match", lp_match}, + {"B", lp_behind}, + {"V", lp_V}, + {"C", lp_simplecapture}, + {"Cc", lp_constcapture}, + {"Cmt", lp_matchtime}, + {"Cb", lp_backref}, + {"Carg", lp_argcapture}, + {"Cp", lp_poscapture}, + {"Cs", lp_substcapture}, + {"Ct", lp_tablecapture}, + {"Cf", lp_foldcapture}, + {"Cg", lp_groupcapture}, + {"P", lp_P}, + {"S", lp_set}, + {"R", lp_range}, + {"locale", lp_locale}, + {"version", lp_version}, + {"setmaxstack", lp_setmax}, + {"type", lp_type}, {NULL, NULL} }; -static struct luaL_Reg metapattreg[] = { - {"__add", union_l}, - {"__pow", star_l}, - {"__sub", diff_l}, - {"__mul", concat_l}, - {"__div", rcapture_l}, - {"__unm", unm_l}, - {"__len", pattand_l}, +static struct luaL_Reg metareg[] = { + {"__mul", lp_seq}, + {"__add", lp_choice}, + {"__pow", lp_star}, + {"__gc", lp_gc}, + {"__len", lp_and}, + {"__div", lp_divcapture}, + {"__unm", lp_not}, + {"__sub", lp_sub}, {NULL, NULL} }; int luaopen_lpeg (lua_State *L); int luaopen_lpeg (lua_State *L) { - lua_pushcfunction(L, (lua_CFunction)&l_newpf); /* new-pattern function */ - lua_setfield(L, LUA_REGISTRYINDEX, KEYNEWPATT); /* register it */ luaL_newmetatable(L, PATTERN_T); - lua_pushnumber(L, MAXBACK); + lua_pushnumber(L, MAXBACK); /* initialize maximum backtracking */ lua_setfield(L, LUA_REGISTRYINDEX, MAXSTACKIDX); - luaL_register(L, NULL, metapattreg); + luaL_register(L, NULL, metareg); luaL_register(L, "lpeg", pattreg); - lua_pushliteral(L, "__index"); - lua_pushvalue(L, -2); - lua_settable(L, -4); + lua_pushvalue(L, -1); + lua_setfield(L, -3, "__index"); return 1; } +/* }====================================================== */ |