'lineinfo' in prototypes saved as differences instead of absolute

values, so that the array can use bytes instead of ints, reducing
its size. (A new array 'abslineinfo' is used when line differences
do not fit in a byte.)

11 files changed, 195 insertions, 33 deletions

diff --git a/lcode.c b/lcode.c
index 2d396000..740cf564 100644
--- a/lcode.c
+++ b/lcode.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lcode.c,v 2.118 2017/04/28 20:57:45 roberto Exp roberto $
+** $Id: lcode.c,v 2.119 2017/05/18 19:44:19 roberto Exp roberto $
 ** Code generator for Lua
 ** See Copyright Notice in lua.h
 */
@@ -10,6 +10,7 @@
 #include "lprefix.h"
 
 
+#include <limits.h>
 #include <math.h>
 #include <stdlib.h>
 
@@ -285,6 +286,33 @@ void luaK_patchclose (FuncState *fs, int list, int level) {
   }
 }
 
+#if !defined(MAXIWTHABS)
+#define MAXIWTHABS      120
+#endif
+
+/*
+** Save line info for a new instruction. If difference from last line
+** does not fit in a byte, of after that many instructions, save a new
+** absolute line info; (in that case, the special value 'ABSLINEINFO'
+** in 'lineinfo' signals the existence of this absolute information.)
+** Otherwise, store the difference from last line in 'lineinfo'.
+*/
+static void savelineinfo (FuncState *fs, Proto *f, int pc, int line) {
+  int linedif = line - fs->previousline;
+  if (abs(linedif) >= 0x80 || fs->iwthabs++ > MAXIWTHABS) {
+    luaM_growvector(fs->ls->L, f->abslineinfo, fs->nabslineinfo,
+                    f->sizeabslineinfo, AbsLineInfo, MAX_INT, "lines");
+    f->abslineinfo[fs->nabslineinfo].pc = pc;
+    f->abslineinfo[fs->nabslineinfo++].line = line;
+    linedif = ABSLINEINFO;  /* signal there is absolute information */
+    fs->iwthabs = 0;  /* restart counter */
+  }
+  luaM_growvector(fs->ls->L, f->lineinfo, pc, f->sizelineinfo, ls_byte,
+                  MAX_INT, "opcodes");
+  f->lineinfo[pc] = linedif;
+  fs->previousline = line;  /* last line saved */
+}
+
 
 /*
 ** Emit instruction 'i', checking for array sizes and saving also its
@@ -297,10 +325,7 @@ static int luaK_code (FuncState *fs, Instruction i) {
   luaM_growvector(fs->ls->L, f->code, fs->pc, f->sizecode, Instruction,
                   MAX_INT, "opcodes");
   f->code[fs->pc] = i;
-  /* save corresponding line information */
-  luaM_growvector(fs->ls->L, f->lineinfo, fs->pc, f->sizelineinfo, int,
-                  MAX_INT, "opcodes");
-  f->lineinfo[fs->pc] = fs->ls->lastline;
+  savelineinfo(fs, f, fs->pc, fs->ls->lastline);
   return fs->pc++;
 }
 
@@ -1260,10 +1285,23 @@ void luaK_posfix (FuncState *fs, BinOpr op,
 
 
 /*
-** Change line information associated with current position.
+** Change line information associated with current position. If that
+** information is absolute, just change it and correct 'previousline'.
+** Otherwise, restore 'previousline' to its value before saving the
+** current position and than saves the line information again, with the
+** new line.
 */
 void luaK_fixline (FuncState *fs, int line) {
-  fs->f->lineinfo[fs->pc - 1] = line;
+  Proto *f = fs->f;
+  if (f->lineinfo[fs->pc - 1] == ABSLINEINFO) {
+    lua_assert(f->abslineinfo[fs->nabslineinfo - 1].pc == fs->pc - 1);
+    f->abslineinfo[fs->nabslineinfo - 1].line = line;
+    fs->previousline = line;
+  }
+  else {
+    fs->previousline -= f->lineinfo[fs->pc - 1];  /* undo previous info. */
+    savelineinfo(fs, f, fs->pc - 1, line);  /* redo it */ 
+  }
 }
 
 
diff --git a/ldebug.c b/ldebug.c
index 4193cda8..6971e475 100644
--- a/ldebug.c
+++ b/ldebug.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ldebug.c,v 2.125 2017/05/13 13:04:33 roberto Exp roberto $
+** $Id: ldebug.c,v 2.126 2017/05/13 13:54:47 roberto Exp roberto $
 ** Debug Interface
 ** See Copyright Notice in lua.h
 */
@@ -48,8 +48,61 @@ static int currentpc (CallInfo *ci) {
 }
 
 
+/*
+** Get a "base line" to find the line corresponding to an instruction.
+** For that, search the array of absolute line info for the largest saved
+** instruction smaller or equal to the wanted instrution. A special
+** case is when there is no absolute info or the instruction is before
+** the first absolute one.
+*/
+static int getbaseline (Proto *f, int pc, int *basepc) {
+  if (f->sizeabslineinfo == 0 || pc < f->abslineinfo[0].pc) {
+    *basepc = -1;  /* start from the beginning */
+    return f->linedefined;
+  }
+  else {
+    unsigned int i;
+    if (pc >= f->abslineinfo[f->sizeabslineinfo - 1].pc)
+      i = f->sizeabslineinfo - 1;  /* instruction is after last saved one */
+    else {  /* binary search */
+      unsigned int j = f->sizeabslineinfo - 1;  /* pc < anchorlines[j] */
+      i = 0;  /* abslineinfo[i] <= pc */
+      while (i < j - 1) {
+        unsigned int m = (j + i) / 2;
+        if (pc >= f->abslineinfo[m].pc)
+          i = m;
+        else
+          j = m;
+      }
+    }
+    *basepc = f->abslineinfo[i].pc;
+    return f->abslineinfo[i].line;
+  }
+}
+
+
+/*
+** Get the line corresponding to instruction 'pc' in function 'f';
+** first gets a base line and from there does the increments until
+** the desired instruction.
+*/
+int luaG_getfuncline (Proto *f, int pc) {
+  if (f->lineinfo == NULL)  /* no debug information? */
+    return -1;
+  else {
+    int basepc;
+    int baseline = getbaseline(f, pc, &basepc);
+    while (basepc++ < pc) {  /* walk until given instruction */
+      lua_assert(f->lineinfo[basepc] != ABSLINEINFO);
+      baseline += f->lineinfo[basepc];  /* correct line */
+    }
+    return baseline;
+  }
+}
+
+
 static int currentline (CallInfo *ci) {
-  return getfuncline(ci_func(ci)->p, currentpc(ci));
+  return luaG_getfuncline(ci_func(ci)->p, currentpc(ci));
 }
 
 
@@ -211,6 +264,14 @@ static void funcinfo (lua_Debug *ar, Closure *cl) {
 }
 
 
+static int nextline (Proto *p, int currentline, int pc) {
+  if (p->lineinfo[pc] != ABSLINEINFO)
+    return currentline + p->lineinfo[pc];
+  else
+    return luaG_getfuncline(p, pc);
+}
+
+
 static void collectvalidlines (lua_State *L, Closure *f) {
   if (noLuaClosure(f)) {
     setnilvalue(L->top);
@@ -219,13 +280,16 @@ static void collectvalidlines (lua_State *L, Closure *f) {
   else {
     int i;
     TValue v;
-    int *lineinfo = f->l.p->lineinfo;
+    Proto *p = f->l.p;
+    int currentline = p->linedefined;
     Table *t = luaH_new(L);  /* new table to store active lines */
     sethvalue(L, L->top, t);  /* push it on stack */
     api_incr_top(L);
     setbvalue(&v, 1);  /* boolean 'true' to be the value of all indices */
-    for (i = 0; i < f->l.p->sizelineinfo; i++)  /* for all lines with code */
-      luaH_setint(L, t, lineinfo[i], &v);  /* table[line] = true */
+    for (i = 0; i < p->sizelineinfo; i++) {  /* for all lines with code */
+      currentline = nextline(p, currentline, i);
+      luaH_setint(L, t, currentline, &v);  /* table[line] = true */
+    }
   }
 }
 
@@ -681,6 +745,19 @@ l_noret luaG_runerror (lua_State *L, const char *fmt, ...) {
 }
 
 
+/*
+** Check whether new instruction 'newpc' is in a different line from
+** previous instruction 'oldpc'.
+*/
+static int changedline (Proto *p, int oldpc, int newpc) {
+  while (oldpc++ < newpc) {
+    if (p->lineinfo[oldpc] != 0)
+      return (luaG_getfuncline(p, oldpc - 1) != luaG_getfuncline(p, newpc));
+  }
+  return 0;  /* no line changes in the way */
+}
+
+
 void luaG_traceexec (lua_State *L) {
   CallInfo *ci = L->ci;
   lu_byte mask = L->hookmask;
@@ -698,11 +775,12 @@ void luaG_traceexec (lua_State *L) {
   if (mask & LUA_MASKLINE) {
     Proto *p = ci_func(ci)->p;
     int npc = pcRel(ci->u.l.savedpc, p);
-    int newline = getfuncline(p, npc);
     if (npc == 0 ||  /* call linehook when enter a new function, */
         ci->u.l.savedpc <= L->oldpc ||  /* when jump back (loop), or when */
-        newline != getfuncline(p, pcRel(L->oldpc, p)))  /* enter a new line */
+        changedline(p, pcRel(L->oldpc, p), npc)) {  /* enter new line */
+      int newline = luaG_getfuncline(p, npc);  /* new line */
       luaD_hook(L, LUA_HOOKLINE, newline);  /* call line hook */
+    }
   }
   L->oldpc = ci->u.l.savedpc;
   if (L->status == LUA_YIELD) {  /* did hook yield? */
diff --git a/ldebug.h b/ldebug.h
index 9c0a03a6..9062f4bd 100644
--- a/ldebug.h
+++ b/ldebug.h
@@ -1,5 +1,5 @@
 /*
-** $Id: ldebug.h,v 2.13 2015/03/11 16:10:41 roberto Exp roberto $
+** $Id: ldebug.h,v 2.14 2015/05/22 17:45:56 roberto Exp roberto $
 ** Auxiliary functions from Debug Interface module
 ** See Copyright Notice in lua.h
 */
@@ -13,11 +13,15 @@
 
 #define pcRel(pc, p)    (cast(int, (pc) - (p)->code) - 1)
 
-#define getfuncline(f,pc)       (((f)->lineinfo) ? (f)->lineinfo[pc] : -1)
-
 #define resethookcount(L)       (L->hookcount = L->basehookcount)
 
+/*
+** mark for entries in 'lineinfo' array that has absolute information in
+** 'abslineinfo' array
+*/
+#define ABSLINEINFO     (-0x80)
 
+LUAI_FUNC int luaG_getfuncline (Proto *f, int pc);
 LUAI_FUNC l_noret luaG_typeerror (lua_State *L, const TValue *o,
                                                 const char *opname);
 LUAI_FUNC l_noret luaG_concaterror (lua_State *L, const TValue *p1,
diff --git a/ldump.c b/ldump.c
index 19030edc..a22d6197 100644
--- a/ldump.c
+++ b/ldump.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ldump.c,v 2.36 2015/03/30 15:43:51 roberto Exp roberto $
+** $Id: ldump.c,v 2.37 2015/10/08 15:53:49 roberto Exp roberto $
 ** save precompiled Lua chunks
 ** See Copyright Notice in lua.h
 */
@@ -149,6 +149,12 @@ static void DumpDebug (const Proto *f, DumpState *D) {
   n = (D->strip) ? 0 : f->sizelineinfo;
   DumpInt(n, D);
   DumpVector(f->lineinfo, n, D);
+  n = (D->strip) ? 0 : f->sizeabslineinfo;
+  DumpInt(n, D);
+  for (i = 0; i < n; i++) {
+    DumpInt(f->abslineinfo[i].pc, D);
+    DumpInt(f->abslineinfo[i].line, D);
+  }
   n = (D->strip) ? 0 : f->sizelocvars;
   DumpInt(n, D);
   for (i = 0; i < n; i++) {
diff --git a/lfunc.c b/lfunc.c
index e84538c9..a4a4e29d 100644
--- a/lfunc.c
+++ b/lfunc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lfunc.c,v 2.48 2017/04/30 20:43:26 roberto Exp roberto $
+** $Id: lfunc.c,v 2.49 2017/05/24 18:54:54 roberto Exp roberto $
 ** Auxiliary functions to manipulate prototypes and closures
 ** See Copyright Notice in lua.h
 */
@@ -119,6 +119,8 @@ Proto *luaF_newproto (lua_State *L) {
   f->sizecode = 0;
   f->lineinfo = NULL;
   f->sizelineinfo = 0;
+  f->abslineinfo = NULL;
+  f->sizeabslineinfo = 0;
   f->upvalues = NULL;
   f->sizeupvalues = 0;
   f->numparams = 0;
@@ -138,6 +140,7 @@ void luaF_freeproto (lua_State *L, Proto *f) {
   luaM_freearray(L, f->p, f->sizep);
   luaM_freearray(L, f->k, f->sizek);
   luaM_freearray(L, f->lineinfo, f->sizelineinfo);
+  luaM_freearray(L, f->abslineinfo, f->sizeabslineinfo);
   luaM_freearray(L, f->locvars, f->sizelocvars);
   luaM_freearray(L, f->upvalues, f->sizeupvalues);
   luaM_free(L, f);
diff --git a/lobject.h b/lobject.h
index e245f306..9af501af 100644
--- a/lobject.h
+++ b/lobject.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lobject.h,v 2.122 2017/06/09 16:48:44 roberto Exp roberto $
+** $Id: lobject.h,v 2.123 2017/06/12 14:21:44 roberto Exp roberto $
 ** Type definitions for Lua objects
 ** See Copyright Notice in lua.h
 */
@@ -418,6 +418,21 @@ typedef struct LocVar {
 
 
 /*
+** Associates the absolute line source for a given instruction ('pc').
+** The array 'lineinfo' gives, for each instruction, the difference in
+** lines from the previous instruction. When that difference does not
+** fit into a byte, Lua saves the absolute line for that instruction.
+** (Lua also saves the absolute line periodically, to speed up the
+** computation of a line number: we can use binary search in the
+** absolute-line array, but we must traverse the 'lineinfo' array
+** linearly to compute a line.)
+*/
+typedef struct AbsLineInfo {
+  int pc;
+  int line;
+} AbsLineInfo;
+
+/*
 ** Function Prototypes
 */
 typedef struct Proto {
@@ -432,15 +447,17 @@ typedef struct Proto {
   int sizelineinfo;
   int sizep;  /* size of 'p' */
   int sizelocvars;
+  int sizeabslineinfo;  /* size of 'abslineinfo' */
   int linedefined;  /* debug information  */
   int lastlinedefined;  /* debug information  */
   TValue *k;  /* constants used by the function */
+  struct LClosure *cache;  /* last-created closure with this prototype */
   Instruction *code;  /* opcodes */
   struct Proto **p;  /* functions defined inside the function */
-  int *lineinfo;  /* map from opcodes to source lines (debug information) */
-  LocVar *locvars;  /* information about local variables (debug information) */
   Upvaldesc *upvalues;  /* upvalue information */
-  struct LClosure *cache;  /* last-created closure with this prototype */
+  ls_byte *lineinfo;  /* information about source lines (debug information) */
+  AbsLineInfo *abslineinfo;  /* idem */
+  LocVar *locvars;  /* information about local variables (debug information) */
   TString  *source;  /* used for debug information */
   GCObject *gclist;
 } Proto;
diff --git a/lparser.c b/lparser.c
index 37f84cce..5e244e24 100644
--- a/lparser.c
+++ b/lparser.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lparser.c,v 2.158 2017/04/29 18:09:17 roberto Exp roberto $
+** $Id: lparser.c,v 2.159 2017/05/13 12:57:20 roberto Exp roberto $
 ** Lua Parser
 ** See Copyright Notice in lua.h
 */
@@ -527,22 +527,24 @@ static void codeclosure (LexState *ls, expdesc *v) {
 
 
 static void open_func (LexState *ls, FuncState *fs, BlockCnt *bl) {
-  Proto *f;
+  Proto *f = fs->f;
   fs->prev = ls->fs;  /* linked list of funcstates */
   fs->ls = ls;
   ls->fs = fs;
   fs->pc = 0;
+  fs->previousline = f->linedefined;
+  fs->iwthabs = 0;
   fs->lasttarget = 0;
   fs->jpc = NO_JUMP;
   fs->freereg = 0;
   fs->nk = 0;
+  fs->nabslineinfo = 0;
   fs->np = 0;
   fs->nups = 0;
   fs->nlocvars = 0;
   fs->nactvar = 0;
   fs->firstlocal = ls->dyd->actvar.n;
   fs->bl = NULL;
-  f = fs->f;
   f->source = ls->source;
   f->maxstacksize = 2;  /* registers 0/1 are always valid */
   enterblock(fs, bl, 0);
@@ -557,8 +559,11 @@ static void close_func (LexState *ls) {
   leaveblock(fs);
   luaM_reallocvector(L, f->code, f->sizecode, fs->pc, Instruction);
   f->sizecode = fs->pc;
-  luaM_reallocvector(L, f->lineinfo, f->sizelineinfo, fs->pc, int);
+  luaM_reallocvector(L, f->lineinfo, f->sizelineinfo, fs->pc, ls_byte);
   f->sizelineinfo = fs->pc;
+  luaM_reallocvector(L, f->abslineinfo, f->sizeabslineinfo,
+                        fs->nabslineinfo, AbsLineInfo);
+  f->sizeabslineinfo = fs->nabslineinfo;
   luaM_reallocvector(L, f->k, f->sizek, fs->nk, TValue);
   f->sizek = fs->nk;
   luaM_reallocvector(L, f->p, f->sizep, fs->np, Proto *);
diff --git a/lparser.h b/lparser.h
index 16124181..3ab6065d 100644
--- a/lparser.h
+++ b/lparser.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lparser.h,v 1.76 2015/12/30 18:16:13 roberto Exp roberto $
+** $Id: lparser.h,v 1.77 2017/04/28 20:57:45 roberto Exp roberto $
 ** Lua Parser
 ** See Copyright Notice in lua.h
 */
@@ -123,14 +123,17 @@ typedef struct FuncState {
   struct BlockCnt *bl;  /* chain of current blocks */
   int pc;  /* next position to code (equivalent to 'ncode') */
   int lasttarget;   /* 'label' of last 'jump label' */
+  int previousline;  /* last line that was saved in 'lineinfo' */
   int jpc;  /* list of pending jumps to 'pc' */
   int nk;  /* number of elements in 'k' */
   int np;  /* number of elements in 'p' */
+  int nabslineinfo;  /* number of elements in 'abslineinfo' */
   int firstlocal;  /* index of first local var (in Dyndata array) */
   short nlocvars;  /* number of elements in 'f->locvars' */
   lu_byte nactvar;  /* number of active local variables */
   lu_byte nups;  /* number of upvalues */
   lu_byte freereg;  /* first free register */
+  lu_byte iwthabs;  /* instructions issued since last absolute line info */
 } FuncState;
 
 
diff --git a/ltests.c b/ltests.c
index 733e47d4..8b2c0ee1 100644
--- a/ltests.c
+++ b/ltests.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltests.c,v 2.219 2017/06/09 16:48:44 roberto Exp roberto $
+** $Id: ltests.c,v 2.220 2017/06/12 14:21:44 roberto Exp roberto $
 ** Internal Module for Debugging of the Lua Implementation
 ** See Copyright Notice in lua.h
 */
@@ -537,7 +537,7 @@ static char *buildop (Proto *p, int pc, char *buff) {
   Instruction i = p->code[pc];
   OpCode o = GET_OPCODE(i);
   const char *name = luaP_opnames[o];
-  int line = getfuncline(p, pc);
+  int line = luaG_getfuncline(p, pc);
   sprintf(buff, "(%4d) %4d - ", line, pc);
   switch (getOpMode(o)) {
     case iABC:
diff --git a/ltests.h b/ltests.h
index 9d26fcb0..82ccc97c 100644
--- a/ltests.h
+++ b/ltests.h
@@ -1,5 +1,5 @@
 /*
-** $Id: ltests.h,v 2.49 2015/09/22 14:18:24 roberto Exp roberto $
+** $Id: ltests.h,v 2.50 2016/07/19 17:13:00 roberto Exp roberto $
 ** Internal Header for Debugging of the Lua Implementation
 ** See Copyright Notice in lua.h
 */
@@ -111,6 +111,7 @@ LUA_API void *debug_realloc (void *ud, void *block,
 #define LUAL_BUFFERSIZE         23
 #define MINSTRTABSIZE           2
 #define MAXINDEXRK              1
+#define MAXIWTHABS              3
 
 
 /* make stack-overflow tests run faster */
diff --git a/lundump.c b/lundump.c
index 13916bc1..7fb05762 100644
--- a/lundump.c
+++ b/lundump.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lundump.c,v 2.43 2015/09/17 15:51:05 roberto Exp roberto $
+** $Id: lundump.c,v 2.44 2015/11/02 16:09:30 roberto Exp roberto $
 ** load precompiled Lua chunks
 ** See Copyright Notice in lua.h
 */
@@ -180,10 +180,17 @@ static void LoadUpvalues (LoadState *S, Proto *f) {
 static void LoadDebug (LoadState *S, Proto *f) {
   int i, n;
   n = LoadInt(S);
-  f->lineinfo = luaM_newvector(S->L, n, int);
+  f->lineinfo = luaM_newvector(S->L, n, ls_byte);
   f->sizelineinfo = n;
   LoadVector(S, f->lineinfo, n);
   n = LoadInt(S);
+  f->abslineinfo = luaM_newvector(S->L, n, AbsLineInfo);
+  f->sizeabslineinfo = n;
+  for (i = 0; i < n; i++) {
+    f->abslineinfo[i].pc = LoadInt(S);
+    f->abslineinfo[i].line = LoadInt(S);
+  }
+  n = LoadInt(S);
   f->locvars = luaM_newvector(S->L, n, LocVar);
   f->sizelocvars = n;
   for (i = 0; i < n; i++)