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++)