1 files changed, 499 insertions, 0 deletions

diff --git a/lplvm.c b/lplvm.c
new file mode 100644
index 0000000..1dddfe6
--- /dev/null
+++ b/lplvm.c
@@ -0,0 +1,499 @@
+/*
+** $Id: lplvm.c $
+** Copyright 2007, Lua.org & PUC-Rio  (see 'lpeg.html' for license)
+*/
+
+#include <limits.h>
+#include <string.h>
+
+
+#include "lua.h"
+#include "lauxlib.h"
+
+#include "lplcap.h"
+#include "lpltypes.h"
+#include "lplvm.h"
+#include "lplprint.h"
+
+
+/* initial size for call/backtrack stack */
+#if !defined(INITBACK)
+#define INITBACK        MAXBACK
+#endif
+
+
+#define getoffset(p)    (((p) + 1)->offset)
+
+static const Instruction giveup = {{IGiveup, 0, 0}};
+
+
+/*
+** Decode one UTF-8 sequence, returning NULL if byte sequence is invalid.
+*/
+static const char *utf8_decode (const char *o, int *val) {
+  static const unsigned int limits[] = {0xFF, 0x7F, 0x7FF, 0xFFFFu};
+  const unsigned char *s = (const unsigned char *)o;
+  unsigned int c = s[0];  /* first byte */
+  unsigned int res = 0;  /* final result */
+  if (c < 0x80)  /* ascii? */
+    res = c;
+  else {
+    int count = 0;  /* to count number of continuation bytes */
+    while (c & 0x40) {  /* still have continuation bytes? */
+      int cc = s[++count];  /* read next byte */
+      if ((cc & 0xC0) != 0x80)  /* not a continuation byte? */
+        return NULL;  /* invalid byte sequence */
+      res = (res << 6) | (cc & 0x3F);  /* add lower 6 bits from cont. byte */
+      c <<= 1;  /* to test next bit */
+    }
+    res |= (c & 0x7F) << (count * 5);  /* add first byte */
+    if (count > 3 || res > 0x10FFFFu || res <= limits[count])
+      return NULL;  /* invalid byte sequence */
+    s += count;  /* skip continuation bytes read */
+  }
+  *val = res;
+  return (const char *)s + 1;  /* +1 to include first byte */
+}
+
+
+/*
+** {======================================================
+** Virtual Machine
+** =======================================================
+*/
+
+
+typedef struct Stack {
+  const char *s;  /* saved position (or NULL for calls) */
+  const Instruction *p;  /* next instruction */
+  int caplevel;
+  byte labenv; /* labeled failure */
+  byte predchoice; /* labeled failure */
+} Stack;
+
+
+#define getstackbase(L, ptop)   ((Stack *)lua_touserdata(L, stackidx(ptop)))
+
+
+/*
+** Ensures the size of array 'capture' (with size '*capsize' and
+** 'captop' elements being used) is enough to accomodate 'n' extra
+** elements plus one.  (Because several opcodes add stuff to the capture
+** array, it is simpler to ensure the array always has at least one free
+** slot upfront and check its size later.)
+*/
+static Capture *growcap (lua_State *L, Capture *capture, int *capsize,
+                                       int captop, int n, int ptop) {
+  if (*capsize - captop > n)
+    return capture;  /* no need to grow array */
+  else {  /* must grow */
+    Capture *newc;
+    int newsize = captop + n + 1;  /* minimum size needed */
+    if (newsize < INT_MAX/((int)sizeof(Capture) * 2))
+      newsize *= 2;  /* twice that size, if not too big */
+    else if (newsize >= INT_MAX/((int)sizeof(Capture)))
+      luaL_error(L, "too many captures");
+    newc = (Capture *)lua_newuserdata(L, newsize * sizeof(Capture));
+    memcpy(newc, capture, captop * sizeof(Capture));
+    *capsize = newsize;
+    lua_replace(L, caplistidx(ptop));
+    return newc;
+  }
+}
+
+
+/*
+** 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;  /* current stack size */
+  int max, newn;
+  lua_getfield(L, LUA_REGISTRYINDEX, MAXSTACKIDX);
+  max = lua_tointeger(L, -1);  /* maximum allowed size */
+  lua_pop(L, 1);
+  if (n >= max)  /* already at maximum size? */
+    luaL_error(L, "backtrack stack overflow (current limit is %d)", 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 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 list
+** 'capture', nested inside a group. 'fd' indexes the first capture
+** value, 'n' is the number of values (at least 1). The open group
+** capture is already in 'capture', before the place for the new entries.
+*/
+static void adddyncaptures (const char *s, Capture *capture, int n, int fd) {
+  int i;
+  assert(capture[-1].kind == Cgroup && capture[-1].siz == 0);
+  capture[-1].idx = 0;  /* make group capture an anonymous group */
+  for (i = 0; i < n; i++) {  /* add runtime captures */
+    capture[i].kind = Cruntime;
+    capture[i].siz = 1;  /* mark it as closed */
+    capture[i].idx = fd + i;  /* stack index of capture value */
+    capture[i].s = s;
+  }
+  capture[n].kind = Cclose;  /* close group */
+  capture[n].siz = 1;
+  capture[n].s = s;
+}
+
+
+/*
+** 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 */
+}
+
+
+/*
+** Opcode interpreter
+*/
+const char *match (lua_State *L, const char *o, const char *s, const char *e,
+                   Instruction *op, Capture *capture, int ptop, short *labelf, const char **sfail) { /* labeled failure */
+  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 */
+  int ndyncap = 0;  /* number of dynamic captures (in Lua stack) */
+  const Instruction *p = op;  /* current instruction */
+  byte insidepred = OUTPRED; /* labeled failure: label environment is off inside predicates */
+  stack->p = &giveup; stack->s = s; stack->caplevel = 0; stack->labenv = insidepred; stack++;  /* labeled failure */
+  *sfail = s; /* labeled failure */
+  lua_pushlightuserdata(L, stackbase);
+  for (;;) {
+#if defined(DEBUG)
+      printf("-------------------------------------\n");
+      printcaplist(capture, capture + captop);
+      printf("s: |%s| stck:%d, dyncaps:%d, caps:%d  ",
+             s, (int)(stack - getstackbase(L, ptop)), ndyncap, captop);
+      printinst(op, p);
+#endif
+    assert(stackidx(ptop) + ndyncap == lua_gettop(L) && ndyncap <= captop);
+    assert(insidepred == INPRED || insidepred == OUTPRED);
+    switch ((Opcode)p->i.code) {
+      case IEnd: {
+        assert(stack == getstackbase(L, ptop) + 1);
+        capture[captop].kind = Cclose;
+        capture[captop].s = NULL;
+        return s;
+      }
+      case IGiveup: {
+        assert(stack == getstackbase(L, ptop));
+        return NULL;
+      }
+      case IRet: {
+        assert(stack > getstackbase(L, ptop) && (stack - 1)->s == NULL);
+        p = (--stack)->p;
+        continue;
+      }
+      case IAny: {
+        if (s < e) { p++; s++; }
+        else {
+          *labelf = LFAIL; /* labeled failure */
+          updatefarthest(*sfail, s); /*labeled failure */
+          goto fail;
+        }
+        continue;
+      }
+      case IUTFR: {
+        int codepoint;
+        if (s >= e)
+          goto fail;
+        s = utf8_decode (s, &codepoint);
+        if (s && p[1].offset <= codepoint && codepoint <= utf_to(p))
+          p += 2;
+        else {
+          *labelf = LFAIL; /* labeled failure */
+          updatefarthest(*sfail, s); /*labeled failure */
+          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 {
+          *labelf = LFAIL; /* labeled failure */
+          updatefarthest(*sfail, s); /*labeled failure */
+          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 {
+          *labelf = LFAIL; /* labeled failure */
+          updatefarthest(*sfail, s); /*labeled failure */
+          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 IBehind: {
+        int n = p->i.aux;
+        if (n > s - o) {
+          *labelf = LFAIL; /* labeled failure */
+          updatefarthest(*sfail, s); /*labeled failure */
+          goto fail;
+        }
+        s -= n; p++;
+        continue;
+      }
+      case ISpan: {
+        for (; s < e; s++) {
+          int c = (byte)*s;
+          if (!testchar((p+1)->buff, c)) break;
+        }
+        p += CHARSETINSTSIZE;
+        continue;
+      }
+      case IJmp: {
+        p += getoffset(p);
+        continue;
+      }
+      case IChoice: {
+        if (stack == stacklimit)
+          stack = doublestack(L, &stacklimit, ptop);
+        stack->p = p + getoffset(p);
+        stack->s = s;
+        stack->caplevel = captop;
+        stack->labenv = insidepred; /* labeled failure */
+        stack->predchoice = 0; /* labeled failure */
+        stack++;
+        p += 2;
+        continue;
+      } 
+      case IPredChoice: { /* labeled failure: new instruction */
+        if (stack == stacklimit)
+          stack = doublestack(L, &stacklimit, ptop);
+        stack->p = p + getoffset(p);
+        stack->s = s;
+        stack->caplevel = captop;
+        stack->labenv = insidepred;
+        stack->predchoice = 1; 
+        stack++;
+        insidepred = INPRED;
+        p += 2;
+        continue;
+      }
+      case ICall: {
+        if (stack == stacklimit)
+          stack = doublestack(L, &stacklimit, ptop);
+        stack->s = NULL;
+        stack->p = p + 2;  /* save return address */
+        stack++;
+        p += getoffset(p);
+        continue;
+      }
+      case ICommit: {
+        assert(stack > getstackbase(L, ptop) && (stack - 1)->s != NULL);
+        stack--;
+        p += getoffset(p);
+        continue;
+      }
+      case IPartialCommit: {
+        assert(stack > getstackbase(L, ptop) && (stack - 1)->s != NULL);
+        (stack - 1)->s = s;
+        (stack - 1)->caplevel = captop;
+        p += getoffset(p);
+        continue;
+      }
+      case IBackCommit: {
+        assert(stack > getstackbase(L, ptop) && (stack - 1)->s != NULL);
+        s = (--stack)->s;
+        insidepred = stack->labenv; /* labeled failure */
+        if (ndyncap > 0)  /* are there matchtime captures? */
+          ndyncap -= removedyncap(L, capture, stack->caplevel, captop);
+        captop = stack->caplevel;
+        p += getoffset(p);
+        continue;
+      }
+      case IThrow: { /* labeled failure */
+        if (insidepred == OUTPRED) {
+          *labelf = (p+1)->i.key;
+          stack = getstackbase(L, ptop);
+          stack++;
+        }
+        else {
+          while (!(stack-1)->predchoice) {
+            --stack;
+          } 
+          *labelf = LFAIL;
+        }
+        *sfail = s;
+        goto fail;
+      }
+      case IThrowRec: { /* labeled failure */
+        if (insidepred == OUTPRED) {
+          *labelf = (p+2)->i.key;
+          *sfail = s;
+          if (stack == stacklimit)
+            stack = doublestack(L, &stacklimit, ptop);
+          stack->s = NULL;
+          stack->p = p + 3;
+          stack->caplevel = captop;
+          stack++;
+          p += getoffset(p);
+          continue;
+        } else {
+          while (!(stack-1)->predchoice) {
+            --stack;
+          } 
+          *labelf = LFAIL;
+          *sfail = s;
+        }
+        goto fail;
+      }
+      case IFailTwice:
+        assert(stack > getstackbase(L, ptop));
+        stack--;
+        /* go through */
+      case IFail:
+      *labelf = LFAIL; /* labeled failure */
+      updatefarthest(*sfail, s); /*labeled failure */
+      fail: { /* pattern failed: try to backtrack */
+        do {  /* remove pending calls */
+          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;
+        assert((insidepred == INPRED && stack->labenv == OUTPRED) || insidepred == stack->labenv);
+        insidepred = stack->labenv; /* labeled failure */
+        p = stack->p;
+#if defined(DEBUG)
+        printf("**FAIL**\n");
+#endif
+        continue;
+      }
+      case ICloseRunTime: {
+        CapState cs;
+        int rem, res, n;
+        int fr = lua_gettop(L) + 1;  /* stack index of first result */
+        cs.reclevel = 0; cs.L = L;
+        cs.s = o; cs.ocap = capture; cs.ptop = ptop;
+        n = runtimecap(&cs, capture + captop, s, &rem);  /* call function */
+        captop -= n;  /* remove nested captures */
+        ndyncap -= rem;  /* update number of dynamic captures */
+        fr -= rem;  /* 'rem' items were popped from Lua stack */
+        res = resdyncaptures(L, fr, s - o, e - o);  /* get result */
+        if (res == -1) { /* fail? */
+          *labelf = LFAIL;  /* labeled failure */
+          updatefarthest(*sfail, s); /*labeled failure */
+          goto fail;
+        }
+        s = o + res;  /* else update current position */
+        n = lua_gettop(L) - fr + 1;  /* number of new captures */
+        ndyncap += n;  /* update number of dynamic captures */
+        if (n == 0)  /* no new captures? */
+          captop--;  /* remove open group */
+        else {  /* new captures; keep original open group */
+          if (fr + n >= SHRT_MAX)
+            luaL_error(L, "too many results in match-time capture");
+          /* add new captures + close group to 'capture' list */
+          capture = growcap(L, capture, &capsize, captop, n + 1, ptop);
+          adddyncaptures(s, capture + captop, n, fr);
+          captop += n + 1;  /* new captures + close group */
+        }
+        p++;
+        continue;
+      }
+      case ICloseCapture: {
+        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;
+          p++;
+          continue;
+        }
+        else {
+          capture[captop].siz = 1;  /* mark entry as closed */
+          capture[captop].s = s;
+          goto pushcapture;
+        }
+      }
+      case IOpenCapture:
+        capture[captop].siz = 0;  /* mark entry as open */
+        capture[captop].s = s;
+        goto pushcapture;
+      case IFullCapture:
+        capture[captop].siz = getoff(p) + 1;  /* save capture size */
+        capture[captop].s = s - getoff(p);
+        /* goto pushcapture; */
+      pushcapture: {
+        capture[captop].idx = p->i.key;
+        capture[captop].kind = getkind(p);
+        captop++;
+        capture = growcap(L, capture, &capsize, captop, 0, ptop);
+        p++;
+        continue;
+      }
+      default: assert(0); return NULL;
+    }
+  }
+}
+
+/* }====================================================== */
+
+