Code size stored in code itself

Most patterns do not have code, as they are not directly used for
a match; they are created only to compose larger patterns. So, we
shouldn't waste space to store the size of their code, as a NULL
pointer already indicates that the size is zero.

7 files changed, 66 insertions, 28 deletions

diff --git a/lpcode.c b/lpcode.c
index 9d7d0eb..f3b8ae3 100644
--- a/lpcode.c
+++ b/lpcode.c
@@ -392,29 +392,63 @@ static void codegen (CompileState *compst, TTree *tree, int opt, int tt,
                      const Charset *fl);
 
 
-void realloccode (lua_State *L, Pattern *p, int nsize) {
+static void finishrelcode (lua_State *L, Pattern *p, Instruction *block,
+                                         int size) {
+  if (block == NULL)
+    luaL_error(L, "not enough memory");
+  block->codesize = size;
+  p->code = (Instruction *)block + 1;
+}
+
+
+/*
+** Initialize array 'p->code'
+*/
+static void newcode (lua_State *L, Pattern *p, int size) {
   void *ud;
+  Instruction *block;
   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;
+  size++;  /* slot for 'codesize' */
+  block = (Instruction*) f(ud, NULL, 0, size * sizeof(Instruction));
+  finishrelcode(L, p, block, size);
+}
+
+
+void freecode (lua_State *L, Pattern *p) {
+  if (p->code != NULL) {
+    void *ud;
+    lua_Alloc f = lua_getallocf(L, &ud);
+    uint osize = p->code[-1].codesize;
+    f(ud, p->code - 1, osize * sizeof(Instruction), 0);  /* free block */
+  }
+}
+
+
+/*
+** Assume that 'nsize' is not zero and that 'p->code' already exists.
+*/
+static void realloccode (lua_State *L, Pattern *p, int nsize) {
+  void *ud;
+  lua_Alloc f = lua_getallocf(L, &ud);
+  Instruction *block = p->code - 1;
+  uint osize = block->codesize;
+  nsize++;  /* add the 'codesize' slot to size */
+  block = (Instruction*) f(ud, block, osize * sizeof(Instruction),
+                                      nsize * sizeof(Instruction));
+  finishrelcode(L, p, block, nsize);
 }
 
 
 /*
-** Add space for 'n' more instructions and return the index of
-** the first one.
+** Add space for an instruction with 'n' slots and return its index.
 */
 static int nextinstruction (CompileState *compst, int n) {
-  int size = compst->p->codesize;
+  int size = compst->p->code[-1].codesize - 1;
   int ncode = compst->ncode;
-  if (ncode >= size - n) {
+  if (ncode > size - n) {
     uint nsize = size + (size >> 1) + n;
-    if (nsize > INT_MAX)
-      luaL_error(compst->L, "code too large");
+    if (nsize >= INT_MAX)
+      luaL_error(compst->L, "pattern code too large");
     realloccode(compst->L, compst->p, nsize);
   }
   compst->ncode = ncode + n;
@@ -998,12 +1032,13 @@ static void peephole (CompileState *compst) {
 
 
 /*
-** Compile a pattern
+** Compile a pattern. 'size' is the size of the pattern's tree,
+** which gives a hint for the size of the final code.
 */
-Instruction *compile (lua_State *L, Pattern *p) {
+Instruction *compile (lua_State *L, Pattern *p, uint size) {
   CompileState compst;
   compst.p = p;  compst.ncode = 0;  compst.L = L;
-  realloccode(L, p, 4);  /* minimum initial size */
+  newcode(L, p, size/2u + 2);  /* set initial size */
   codegen(&compst, p->tree, 0, NOINST, fullset);
   addinstruction(&compst, IEnd, 0);
   realloccode(L, p, compst.ncode);  /* set final size */
diff --git a/lpcode.h b/lpcode.h
index 3c71451..10c2ced 100644
--- a/lpcode.h
+++ b/lpcode.h
@@ -12,8 +12,8 @@ int checkaux (TTree *tree, int pred);
 int fixedlen (TTree *tree);
 int hascaptures (TTree *tree);
 int lp_gc (lua_State *L);
-Instruction *compile (lua_State *L, Pattern *p);
-void realloccode (lua_State *L, Pattern *p, int nsize);
+Instruction *compile (lua_State *L, Pattern *p, uint size);
+void freecode (lua_State *L, Pattern *p);
 int sizei (const Instruction *i);
 
 
diff --git a/lpprint.c b/lpprint.c
index 3e7e7f2..54a3da7 100644
--- a/lpprint.c
+++ b/lpprint.c
@@ -137,8 +137,9 @@ void printinst (const Instruction *op, const Instruction *p) {
 }
 
 
-void printpatt (Instruction *p, int n) {
+void printpatt (Instruction *p) {
   Instruction *op = p;
+  uint n = op[-1].codesize - 1;
   while (p < op + n) {
     printinst(op, p);
     p += sizei(p);
diff --git a/lpprint.h b/lpprint.h
index 42d7f98..e97f8c0 100644
--- a/lpprint.h
+++ b/lpprint.h
@@ -9,7 +9,7 @@
 
 #if defined(LPEG_DEBUG)
 
-void printpatt (Instruction *p, int n);
+void printpatt (Instruction *p);
 void printtree (TTree *tree, int ident);
 void printktable (lua_State *L, int idx);
 void printcharset (const byte *st);
diff --git a/lptree.c b/lptree.c
index dcee27e..0b2d824 100644
--- a/lptree.c
+++ b/lptree.c
@@ -359,7 +359,7 @@ static TTree *newtree (lua_State *L, int len) {
   lua_pushvalue(L, -1);
   lua_setuservalue(L, -3);
   lua_setmetatable(L, -2);
-  p->code = NULL;  p->codesize = 0;
+  p->code = NULL;
   return p->tree;
 }
 
@@ -1189,7 +1189,7 @@ static Instruction *prepcompile (lua_State *L, Pattern *p, int idx) {
   lua_getuservalue(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);
+  return compile(L, p, getsize(L, idx));
 }
 
 
@@ -1212,7 +1212,7 @@ static int lp_printcode (lua_State *L) {
   printktable(L, 1);
   if (p->code == NULL)  /* not compiled yet? */
     prepcompile(L, p, 1);
-  printpatt(p->code, p->codesize);
+  printpatt(p->code);
   return 0;
 }
 
@@ -1290,7 +1290,7 @@ static int lp_type (lua_State *L) {
 
 int lp_gc (lua_State *L) {
   Pattern *p = getpattern(L, 1);
-  realloccode(L, p, 0);  /* delete code block */
+  freecode(L, p);  /* delete code block */
   return 0;
 }
 
@@ -1377,7 +1377,6 @@ static struct luaL_Reg metareg[] = {
 
 int luaopen_lpeg (lua_State *L);
 int luaopen_lpeg (lua_State *L) {
-printf("%ld\n", sizeof(TTree));
   luaL_newmetatable(L, PATTERN_T);
   lua_pushnumber(L, MAXBACK);  /* initialize maximum backtracking */
   lua_setfield(L, LUA_REGISTRYINDEX, MAXSTACKIDX);
diff --git a/lptree.h b/lptree.h
index 7dab362..c788741 100644
--- a/lptree.h
+++ b/lptree.h
@@ -72,7 +72,6 @@ typedef struct TTree {
 */
 typedef struct Pattern {
   union Instruction *code;
-  int codesize;
   TTree tree[1];
 } Pattern;
 
diff --git a/lpvm.h b/lpvm.h
index a64d577..684f0c9 100644
--- a/lpvm.h
+++ b/lpvm.h
@@ -43,7 +43,11 @@ typedef enum Opcode {
 } Opcode;
 
 
-
+/*
+** All array of instructions has a 'codesize' as its first element
+** and is referred by a pointer to its second element, which is the
+** first actual opcode.
+*/
 typedef union Instruction {
   struct Inst {
     byte code;
@@ -57,6 +61,7 @@ typedef union Instruction {
     } aux2;
   } i;
   int offset;
+  uint codesize;
   byte buff[1];
 } Instruction;
 
@@ -66,7 +71,6 @@ typedef union Instruction {
 
 
 int charinset (const Instruction *i, const byte *buff, uint c);
-void printpatt (Instruction *p, int n);
 const char *match (lua_State *L, const char *o, const char *s, const char *e,
                    Instruction *op, Capture *capture, int ptop);