Full abstraction for representation of array values

9 files changed, 128 insertions, 93 deletions

diff --git a/lapi.c b/lapi.c
index 4a3ba724..99c8473e 100644
--- a/lapi.c
+++ b/lapi.c
@@ -653,21 +653,17 @@ l_sinline int auxgetstr (lua_State *L, const TValue *t, const char *k) {
 }
 
 
-/*
-** Get the global table in the registry. Since all predefined
-** indices in the registry were inserted right when the registry
-** was created and never removed, they must always be in the array
-** part of the registry.
-*/
-#define getGtable(L)  \
-        (&hvalue(&G(L)->l_registry)->array[LUA_RIDX_GLOBALS - 1])
+static void getGlobalTable (lua_State *L, TValue *gt) {
+  Table *registry = hvalue(&G(L)->l_registry);
+  luaH_getint(registry, LUA_RIDX_GLOBALS, gt);
+}
 
 
 LUA_API int lua_getglobal (lua_State *L, const char *name) {
-  const TValue *G;
+  TValue gt;
   lua_lock(L);
-  G = getGtable(L);
-  return auxgetstr(L, G, name);
+  getGlobalTable(L, &gt);
+  return auxgetstr(L, &gt, name);
 }
 
 
@@ -840,10 +836,10 @@ static void auxsetstr (lua_State *L, const TValue *t, const char *k) {
 
 
 LUA_API void lua_setglobal (lua_State *L, const char *name) {
-  const TValue *G;
+  TValue gt;
   lua_lock(L);  /* unlock done in 'auxsetstr' */
-  G = getGtable(L);
-  auxsetstr(L, G, name);
+  getGlobalTable(L, &gt);
+  auxsetstr(L, &gt, name);
 }
 
 
@@ -1093,10 +1089,11 @@ LUA_API int lua_load (lua_State *L, lua_Reader reader, void *data,
     LClosure *f = clLvalue(s2v(L->top.p - 1));  /* get new function */
     if (f->nupvalues >= 1) {  /* does it have an upvalue? */
       /* get global table from registry */
-      const TValue *gt = getGtable(L);
+      TValue gt;
+      getGlobalTable(L, &gt);
       /* set global table as 1st upvalue of 'f' (may be LUA_ENV) */
-      setobj(L, f->upvals[0]->v.p, gt);
-      luaC_barrier(L, f->upvals[0], gt);
+      setobj(L, f->upvals[0]->v.p, &gt);
+      luaC_barrier(L, f->upvals[0], &gt);
     }
   }
   lua_unlock(L);
diff --git a/lgc.c b/lgc.c
index a3094ff5..813b08d5 100644
--- a/lgc.c
+++ b/lgc.c
@@ -91,6 +91,13 @@
 #define gcvalueN(o)     (iscollectable(o) ? gcvalue(o) : NULL)
 
 
+/*
+** Access to collectable objects in array part of tables
+*/
+#define gcvalarr(t,i)  \
+        ((*getArrTag(t,i) & BIT_ISCOLLECTABLE) ? getArrVal(t,i)->gc : NULL)
+
+
 #define markvalue(g,o) { checkliveness(g->mainthread,o); \
   if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); }
 
@@ -486,9 +493,10 @@ static int traverseephemeron (global_State *g, Table *h, int inv) {
   unsigned int nsize = sizenode(h);
   /* traverse array part */
   for (i = 0; i < asize; i++) {
-    if (valiswhite(&h->array[i])) {
+    GCObject *o = gcvalarr(h, i + 1);
+    if (o != NULL && iswhite(o)) {
       marked = 1;
-      reallymarkobject(g, gcvalue(&h->array[i]));
+      reallymarkobject(g, o);
     }
   }
   /* traverse hash part; if 'inv', traverse descending
@@ -524,8 +532,11 @@ static void traversestrongtable (global_State *g, Table *h) {
   Node *n, *limit = gnodelast(h);
   unsigned int i;
   unsigned int asize = luaH_realasize(h);
-  for (i = 0; i < asize; i++)  /* traverse array part */
-    markvalue(g, &h->array[i]);
+  for (i = 0; i < asize; i++) {  /* traverse array part */
+    GCObject *o = gcvalarr(h, i + 1);
+    if (o != NULL && iswhite(o))
+      reallymarkobject(g, o);
+  }
   for (n = gnode(h, 0); n < limit; n++) {  /* traverse hash part */
     if (isempty(gval(n)))  /* entry is empty? */
       clearkey(n);  /* clear its key */
@@ -746,9 +757,9 @@ static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) {
     unsigned int i;
     unsigned int asize = luaH_realasize(h);
     for (i = 0; i < asize; i++) {
-      TValue *o = &h->array[i];
-      if (iscleared(g, gcvalueN(o)))  /* value was collected? */
-        setempty(o);  /* remove entry */
+      GCObject *o = gcvalarr(h, i + 1);
+      if (iscleared(g, o))  /* value was collected? */
+        *getArrTag(h, i + 1) = LUA_VEMPTY;  /* remove entry */
     }
     for (n = gnode(h, 0); n < limit; n++) {
       if (iscleared(g, gcvalueN(gval(n))))  /* unmarked value? */
diff --git a/lobject.h b/lobject.h
index 556608e4..e91bb0f8 100644
--- a/lobject.h
+++ b/lobject.h
@@ -736,12 +736,15 @@ typedef union Node {
 #define setnorealasize(t)       ((t)->flags |= BITRAS)
 
 
+typedef struct ArrayCell ArrayCell;
+
+
 typedef struct Table {
   CommonHeader;
   lu_byte flags;  /* 1<<p means tagmethod(p) is not present */
   lu_byte lsizenode;  /* log2 of size of 'node' array */
   unsigned int alimit;  /* "limit" of 'array' array */
-  TValue *array;  /* array part */
+  ArrayCell *array;  /* array part */
   Node *node;
   Node *lastfree;  /* any free position is before this position */
   struct Table *metatable;
diff --git a/lstate.c b/lstate.c
index 1e925e5a..d10cd88c 100644
--- a/lstate.c
+++ b/lstate.c
@@ -215,13 +215,16 @@ static void freestack (lua_State *L) {
 */
 static void init_registry (lua_State *L, global_State *g) {
   /* create registry */
+  TValue aux;
   Table *registry = luaH_new(L);
   sethvalue(L, &g->l_registry, registry);
   luaH_resize(L, registry, LUA_RIDX_LAST, 0);
   /* registry[LUA_RIDX_MAINTHREAD] = L */
-  setthvalue(L, &registry->array[LUA_RIDX_MAINTHREAD - 1], L);
+  setthvalue(L, &aux, L);
+  luaH_setint(L, registry, LUA_RIDX_MAINTHREAD, &aux);
   /* registry[LUA_RIDX_GLOBALS] = new table (table of globals) */
-  sethvalue(L, &registry->array[LUA_RIDX_GLOBALS - 1], luaH_new(L));
+  sethvalue(L, &aux, luaH_new(L));
+  luaH_setint(L, registry, LUA_RIDX_GLOBALS, &aux);
 }
 
 
diff --git a/ltable.c b/ltable.c
index d436cf6e..ddda9a44 100644
--- a/ltable.c
+++ b/ltable.c
@@ -350,9 +350,10 @@ int luaH_next (lua_State *L, Table *t, StkId key) {
   unsigned int asize = luaH_realasize(t);
   unsigned int i = findindex(L, t, s2v(key), asize);  /* find original key */
   for (; i < asize; i++) {  /* try first array part */
-    if (!isempty(&t->array[i])) {  /* a non-empty entry? */
+    int tag = *getArrTag(t, i + 1);
+    if (!tagisempty(tag)) {  /* a non-empty entry? */
       setivalue(s2v(key), i + 1);
-      setobj2s(L, key + 1, &t->array[i]);
+      farr2val(t, i + 1, tag, s2v(key + 1));
       return 1;
     }
   }
@@ -375,6 +376,41 @@ static void freehash (lua_State *L, Table *t) {
 
 
 /*
+** Check whether an integer key is in the array part. If 'alimit' is
+** not the real size of the array, the key still can be in the array
+** part.  In this case, do the "Xmilia trick" to check whether 'key-1'
+** is smaller than the real size.
+** The trick works as follow: let 'p' be an integer such that
+** '2^(p+1) >= alimit > 2^p', or  '2^(p+1) > alimit-1 >= 2^p'.
+** That is, 2^(p+1) is the real size of the array, and 'p' is the highest
+** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'.
+** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will
+** have the 'p' bit cleared. If the key is outside the array, that is,
+** 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than 'p',
+** therefore it will be larger or equal to 'alimit', and the check
+** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than
+** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
+** than 2^p, therefore smaller than 'alimit', and the check succeeds.
+** As special cases, when 'alimit' is 0 the condition is trivially false,
+** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
+** If key is 0 or negative, 'res' will have its higher bit on, so that
+** if cannot be smaller than alimit.
+*/
+static int keyinarray (Table *t, lua_Integer key) {
+  lua_Unsigned alimit = t->alimit;
+  if (l_castS2U(key) - 1u < alimit)  /* 'key' in [1, t->alimit]? */
+    return 1;
+  else if (!isrealasize(t) &&  /* key still may be in the array part? */
+           (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) {
+    t->alimit = cast_uint(key);  /* probably '#t' is here now */
+    return 1;
+  }
+  else
+    return 0;
+}
+
+
+/*
 ** {=============================================================
 ** Rehash
 ** ==============================================================
@@ -421,6 +457,12 @@ static int countint (lua_Integer key, unsigned int *nums) {
 }
 
 
+l_sinline int arraykeyisempty (const Table *t, lua_Integer key) {
+  int tag = *getArrTag(t, key);
+  return tagisempty(tag);
+}
+
+
 /*
 ** Count keys in array part of table 't': Fill 'nums[i]' with
 ** number of keys that will go into corresponding slice and return
@@ -443,7 +485,7 @@ static unsigned int numusearray (const Table *t, unsigned int *nums) {
     }
     /* count elements in range (2^(lg - 1), 2^lg] */
     for (; i <= lim; i++) {
-      if (!isempty(&t->array[i-1]))
+      if (!arraykeyisempty(t, i))
         lc++;
     }
     nums[lg] += lc;
@@ -555,7 +597,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
   unsigned int i;
   Table newt;  /* to keep the new hash part */
   unsigned int oldasize = setlimittosize(t);
-  TValue *newarray;
+  ArrayCell *newarray;
   /* create new hash part with appropriate size into 'newt' */
   setnodevector(L, &newt, nhsize);
   if (newasize < oldasize) {  /* will array shrink? */
@@ -563,14 +605,18 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
     exchangehashpart(t, &newt);  /* and new hash */
     /* re-insert into the new hash the elements from vanishing slice */
     for (i = newasize; i < oldasize; i++) {
-      if (!isempty(&t->array[i]))
-        luaH_setint(L, t, i + 1, &t->array[i]);
+      int tag = *getArrTag(t, i + 1);
+      if (!tagisempty(tag)) {  /* a non-empty entry? */
+        TValue aux;
+        farr2val(t, i + 1, tag, &aux);
+        luaH_setint(L, t, i + 1, &aux);
+      }
     }
     t->alimit = oldasize;  /* restore current size... */
     exchangehashpart(t, &newt);  /* and hash (in case of errors) */
   }
   /* allocate new array */
-  newarray = luaM_reallocvector(L, t->array, oldasize, newasize, TValue);
+  newarray = luaM_reallocvector(L, t->array, oldasize, newasize, ArrayCell);
   if (l_unlikely(newarray == NULL && newasize > 0)) {  /* allocation failed? */
     freehash(L, &newt);  /* release new hash part */
     luaM_error(L);  /* raise error (with array unchanged) */
@@ -580,7 +626,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
   t->array = newarray;  /* set new array part */
   t->alimit = newasize;
   for (i = oldasize; i < newasize; i++)  /* clear new slice of the array */
-     setempty(&t->array[i]);
+    *getArrTag(t, i + 1) = LUA_VEMPTY;
   /* re-insert elements from old hash part into new parts */
   reinsert(L, &newt, t);  /* 'newt' now has the old hash */
   freehash(L, &newt);  /* free old hash part */
@@ -719,41 +765,6 @@ void luaH_newkey (lua_State *L, Table *t, const TValue *key, TValue *value) {
 }
 
 
-/*
-** Check whether key is in the array part. If 'alimit' is not the real
-** size of the array, the key still can be in the array part.  In this
-** case, do the "Xmilia trick" to check whether 'key-1' is smaller than
-** the real size.
-** The trick works as follow: let 'p' be an integer such that
-** '2^(p+1) >= alimit > 2^p', or  '2^(p+1) > alimit-1 >= 2^p'.
-** That is, 2^(p+1) is the real size of the array, and 'p' is the highest
-** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'.
-** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will
-** have the 'p' bit cleared. If the key is outside the array, that is,
-** 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than 'p',
-** therefore it will be larger or equal to 'alimit', and the check
-** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than
-** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
-** than 2^p, therefore smaller than 'alimit', and the check succeeds.
-** As special cases, when 'alimit' is 0 the condition is trivially false,
-** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
-** If key is 0 or negative, 'res' will have its higher bit on, so that
-** if cannot be smaller than alimit.
-*/
-static int keyinarray (Table *t, lua_Integer key) {
-  lua_Unsigned alimit = t->alimit;
-  if (l_castS2U(key) - 1u < alimit)  /* 'key' in [1, t->alimit]? */
-    return 1;
-  else if (!isrealasize(t) &&  /* key still may be in the array part? */
-           (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) {
-    t->alimit = cast_uint(key);  /* probably '#t' is here now */
-    return 1;
-  }
-  else
-    return 0;
-}
-
-
 static const TValue *getintfromhash (Table *t, lua_Integer key) {
   Node *n = hashint(t, key);
   lua_assert(l_castS2U(key) - 1u >= luaH_realasize(t));
@@ -770,15 +781,8 @@ static const TValue *getintfromhash (Table *t, lua_Integer key) {
 }
 
 
-l_sinline int arraykeyisempty (Table *t, lua_Integer key) {
-  int tag = *getArrTag(t, key);
-  return tagisempty(tag);
-}
-
-
 static int hashkeyisempty (Table *t, lua_Integer key) {
   const TValue *val = getintfromhash(t, key);
-  lua_assert(!keyinarray(t, key));
   return isempty(val);
 }
 
@@ -797,7 +801,7 @@ int luaH_getint (Table *t, lua_Integer key, TValue *res) {
   if (keyinarray(t, key)) {
     int tag = *getArrTag(t, key);
     if (!tagisempty(tag)) {
-      arr2val(t, key, tag, res);
+      farr2val(t, key, tag, res);
       return HOK;  /* success */
     }
     else
@@ -900,7 +904,7 @@ int luaH_psetint (Table *t, lua_Integer key, TValue *val) {
   if (keyinarray(t, key)) {
     lu_byte *tag = getArrTag(t, key);
     if (!tagisempty(*tag)) {
-      val2arr(t, key, tag, val);
+      fval2arr(t, key, tag, val);
       return HOK;  /* success */
     }
     else
@@ -956,7 +960,7 @@ void luaH_finishset (lua_State *L, Table *t, const TValue *key,
   }
   else {  /* array entry */
     hres = ~hres;  /* real index */
-    val2arr(t, hres, getArrTag(t, hres), value);
+    fval2arr(t, hres, getArrTag(t, hres), value);
   }
 }
 
@@ -1087,11 +1091,11 @@ lua_Unsigned luaH_getn (Table *t) {
   /* 'limit' is zero or present in table */
   if (!limitequalsasize(t)) {  /* (2)? */
     /* 'limit' > 0 and array has more elements after 'limit' */
-    if (isempty(&t->array[limit]))  /* 'limit + 1' is empty? */
+    if (arraykeyisempty(t, limit + 1))  /* 'limit + 1' is empty? */
       return limit;  /* this is the boundary */
     /* else, try last element in the array */
     limit = luaH_realasize(t);
-    if (isempty(&t->array[limit - 1])) {  /* empty? */
+    if (arraykeyisempty(t, limit)) {  /* empty? */
       /* there must be a boundary in the array after old limit,
          and it must be a valid new limit */
       unsigned int boundary = binsearch(t, t->alimit, limit);
@@ -1102,7 +1106,7 @@ lua_Unsigned luaH_getn (Table *t) {
   }
   /* (3) 'limit' is the last element and either is zero or present in table */
   lua_assert(limit == luaH_realasize(t) &&
-             (limit == 0 || !isempty(&t->array[limit - 1])));
+             (limit == 0 || !arraykeyisempty(t, limit)));
   if (isdummy(t) || hashkeyisempty(t, cast(lua_Integer, limit + 1)))
     return limit;  /* 'limit + 1' is absent */
   else  /* 'limit + 1' is also present */
diff --git a/ltable.h b/ltable.h
index 5ec7b447..371e721d 100644
--- a/ltable.h
+++ b/ltable.h
@@ -51,20 +51,33 @@
 */
 
 
+struct ArrayCell {
+  lu_byte tt;
+  Value value;
+};
+
 
 /* fast access to components of array values */
-#define getArrTag(t,k)  (&(t)->array[k - 1].tt_)
-#define getArrVal(t,k)  (&(t)->array[k - 1].value_)
+#define getArrTag(t,k)  (&(t)->array[k - 1].tt)
+#define getArrVal(t,k)  (&(t)->array[k - 1].value)
 
 #define tagisempty(tag)  (novariant(tag) == LUA_TNIL)
 
-#define arr2val(h,k,tag,res)  \
+
+#define farr2val(h,k,tag,res)  \
   ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,k))
 
-#define val2arr(h,k,tag,val)  \
+#define fval2arr(h,k,tag,val)  \
   (*tag = (val)->tt_, *getArrVal(h,k) = (val)->value_)
 
 
+#define obj2arr(h,k,val)  \
+  (*getArrTag(h,k) = (val)->tt_, *getArrVal(h,k) = (val)->value_)
+
+#define arr2obj(h,k,val)  \
+  ((val)->tt_ = *getArrTag(h,k), (val)->value_ = *getArrVal(h,k))
+
+
 LUAI_FUNC int luaH_getshortstr (Table *t, TString *key, TValue *res);
 LUAI_FUNC int luaH_getstr (Table *t, TString *key, TValue *res);
 LUAI_FUNC int luaH_get (Table *t, const TValue *key, TValue *res);
diff --git a/ltests.c b/ltests.c
index 7d184c0d..e2bf76bd 100644
--- a/ltests.c
+++ b/ltests.c
@@ -362,8 +362,11 @@ static void checktable (global_State *g, Table *h) {
   Node *n, *limit = gnode(h, sizenode(h));
   GCObject *hgc = obj2gco(h);
   checkobjrefN(g, hgc, h->metatable);
-  for (i = 0; i < asize; i++)
-    checkvalref(g, hgc, &h->array[i]);
+  for (i = 0; i < asize; i++) {
+    TValue aux;
+    arr2obj(h, i + 1, &aux);
+    checkvalref(g, hgc, &aux);
+  }
   for (n = gnode(h, 0); n < limit; n++) {
     if (!isempty(gval(n))) {
       TValue k;
@@ -1005,7 +1008,8 @@ static int table_query (lua_State *L) {
   }
   else if ((unsigned int)i < asize) {
     lua_pushinteger(L, i);
-    pushobject(L, &t->array[i]);
+    arr2obj(t, i + 1, s2v(L->top.p));
+    api_incr_top(L);
     lua_pushnil(L);
   }
   else if ((i -= asize) < sizenode(t)) {
diff --git a/lvm.c b/lvm.c
index 96413718..927272df 100644
--- a/lvm.c
+++ b/lvm.c
@@ -1845,7 +1845,7 @@ void luaV_execute (lua_State *L, CallInfo *ci) {
           luaH_resizearray(L, h, last);  /* preallocate it at once */
         for (; n > 0; n--) {
           TValue *val = s2v(ra + n);
-          setobj2t(L, &h->array[last - 1], val);
+          obj2arr(h, last, val);
           last--;
           luaC_barrierback(L, obj2gco(h), val);
         }
diff --git a/lvm.h b/lvm.h
index 8808c942..32455fba 100644
--- a/lvm.h
+++ b/lvm.h
@@ -92,7 +92,7 @@ typedef enum {
     if ((u - 1u < h->alimit)) { \
       int tag = *getArrTag(h,u); \
       if (tagisempty(tag)) aux = HNOTFOUND; \
-      else { arr2val(h, u, tag, res); aux = HOK; }} \
+      else { farr2val(h, u, tag, res); aux = HOK; }} \
     else { aux = luaH_getint(h, u, res); }}
 
 
@@ -105,7 +105,7 @@ typedef enum {
     if ((u - 1u < h->alimit)) { \
       lu_byte *tag = getArrTag(h,u); \
       if (tagisempty(*tag)) aux = ~cast_int(u); \
-      else { val2arr(h, u, tag, val); aux = HOK; }} \
+      else { fval2arr(h, u, tag, val); aux = HOK; }} \
     else { aux = luaH_psetint(h, u, val); }}