テーブルの中の配列とハッシュ

luaのテーブルは配列用のエントリとハッシュ（連想配列）用のエントリを別々２つを持ってて、別々に管理している、、、っていうのは何となくは知っていたのだけれど、具体的にどうであるかとか全然分かってなかった。ので、最初
Luaで空テーブルかどうか判定する -- sh1.2 pyblosxom
これ見た時「ん？ #でlenを調べちゃダメ？」とか初心者丸出しのことを考えてしまった。
実際やってみるとわかるけど、

> array = {11,22,33}
> print(#array)
3
> hash = {a=1, b=2}
> print(#hash)
0

となって「どひーん」となる。要するにlen(#)は array側しか見てくれていなくって、hashの要素数なんて知らん*1仕様になっている。結局はshunuhsせんせーのやっていた通り next()が一番良い解法になりそうな感じ。

中はどうなってんの？

その上、luaの配列の長さ管理は結構独特。

> a = {1,2,3,4,5}
> for i,v in ipairs(a) do print (i .. ":" .. v) end
1:1
2:2
3:3
4:4
5:5
> print(#a)
5
> a[1] = nil
> for i,v in ipairs(a) do print (i .. ":" .. v) end
> print(#a)
5

ビックリ。どうやら終端を動的に求めているよう。もともとこの配列の分断は禁止されていて、動作は未定義になっている。一体内部はどうなってんだろう、とソースを追っ掛けてみる。

ltable.c -

/*
** Try to find a boundary in table `t'. A `boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
*/
int luaH_getn (Table *t) {
  unsigned int j = t->sizearray;
  if (j > 0 && ttisnil(&t->array[j - 1])) {
    /* there is a boundary in the array part: (binary) search for it */
    unsigned int i = 0;
    while (j - i > 1) {
      unsigned int m = (i+j)/2;
      if (ttisnil(&t->array[m - 1])) j = m;
      else i = m;
    }
    return i;
  }
  /* else must find a boundary in hash part */
  else if (t->node == dummynode)  /* hash part is empty? */
    return j;  /* that is easy... */
  else return unbound_search(t, j);
}

ここ。末尾がつまってるか(nilじゃないか)見て、もしnilだったらバイナリサーチして末尾ポイントを「推定」。つまってたら、さらにハッシュパートを調べて、空ならそのまんま確保されている長さ(j = t->sizearray)を、ハッシュパートが空じゃない場合はunbound_search()でハッシュの中も見ていく。これはどうやら後からa[..] = .. で追加した場合を考えているみたい。なるほどねえ。ということは、

> a = {1,2,3,4,5,nil}
> print(#a)
5
> a[2] = nil
> print(#a)
5
> a[3] = nil
> print(#a)
1

やっぱり。不感症のポイントがあるのだね。

というかやっぱりハッシュの大きさも欲しい

ので少し内部を見てみた。結果どうやら sizenode とやらで（確保されている）ハッシュエントリ数が分かるっぽいので、これを組み込んでみる。
lua のパーサは非常に素直な再起下降パーサになっているので、追加は結構簡単でおもしろい。というか時間無くなってしまったので、パッチだけ置いて、説明はまた別の機会に。。。
動作は以下の用にテーブルの前に + をつけると（確保されている）ハッシュエントリ数が返るようにしてみた。

> print(+{a=1})
1
> print(+{})
0
> print(+{a=1,b=2})
2
> print(+{1,2,3})
0

素のままsizenodeを返すとからっぽのテーブル {}でもエントリは１確保されているので１がかえってしまう。ので

+  return t->node == dummynode? 0: sizenode(t);

としてある。また、{}でないテーブルのエントリを消して {}になった場合、確保されているエントリ数は変わらないので 0 にならない、という問題点が。。。（まずい？）
というかどういう使用用途だったのかな。。。

まあ、いろいろ挙動が見えておもしろいけど。

hashlen.patch -

diff --git a/src/lcode.c b/src/lcode.c
index cff626b..2465860 100644
--- a/src/lcode.c
+++ b/src/lcode.c
@@ -710,6 +710,11 @@ void luaK_prefix (FuncState *fs, UnOpr op, expdesc *e) {
       codearith(fs, OP_LEN, e, &e2);
       break;
     }
+    case OPR_HLEN: {
+      luaK_exp2anyreg(fs, e);  /* cannot operate on constants */
+      codearith(fs, OP_HLEN, e, &e2);
+      break;
+    }
     default: lua_assert(0);
   }
 }
diff --git a/src/lcode.h b/src/lcode.h
index b941c60..7962c57 100644
--- a/src/lcode.h
+++ b/src/lcode.h
@@ -33,7 +33,7 @@ typedef enum BinOpr {
 } BinOpr;


-typedef enum UnOpr { OPR_MINUS, OPR_NOT, OPR_LEN, OPR_NOUNOPR } UnOpr;
+typedef enum UnOpr { OPR_MINUS, OPR_NOT, OPR_LEN, OPR_NOUNOPR, OPR_HLEN } UnOpr;


 #define getcode(fs,e)  ((fs)->f->code[(e)->u.s.info])
diff --git a/src/lopcodes.h b/src/lopcodes.h
index 41224d6..76262bd 100644
--- a/src/lopcodes.h
+++ b/src/lopcodes.h
@@ -177,6 +177,7 @@ OP_POW,/*   A B C   R(A) := RK(B) ^ RK(C)                           */
 OP_UNM,/*      A B     R(A) := -R(B)                                   */
 OP_NOT,/*      A B     R(A) := not R(B)                                */
 OP_LEN,/*      A B     R(A) := length of R(B)                          */
+OP_HLEN,/*     A B     R(A) := node length of R(B)                             */

 OP_CONCAT,/*   A B C   R(A) := R(B).. ... ..R(C)                       */

diff --git a/src/lparser.c b/src/lparser.c
index 1e2a9a8..c8a0242 100644
--- a/src/lparser.c
+++ b/src/lparser.c
@@ -780,6 +780,7 @@ static UnOpr getunopr (int op) {
     case TK_NOT: return OPR_NOT;
     case '-': return OPR_MINUS;
     case '#': return OPR_LEN;
+    case '+': return OPR_HLEN;
     default: return OPR_NOUNOPR;
   }
 }
diff --git a/src/ltable.c b/src/ltable.c
index ec84f4f..a1c0a26 100644
--- a/src/ltable.c
+++ b/src/ltable.c
@@ -575,6 +575,9 @@ int luaH_getn (Table *t) {
   else return unbound_search(t, j);
 }

+int luaH_gethn (Table *t) {
+  return t->node == dummynode? 0: sizenode(t);
+}


 #if defined(LUA_DEBUG)
diff --git a/src/lvm.c b/src/lvm.c
index ee3256a..0749229 100644
--- a/src/lvm.c
+++ b/src/lvm.c
@@ -507,6 +507,22 @@ void luaV_execute (lua_State *L, int nexeccalls) {
         setbvalue(ra, res);
         continue;
       }
+      case OP_HLEN: {
+        const TValue *rb = RB(i);
+        switch (ttype(rb)) {
+          case LUA_TTABLE: {
+            setnvalue(ra, cast_num(luaH_gethn(hvalue(rb))));
+            break;
+          }
+          default: {  /* try metamethod */
+            Protect(
+              if (!call_binTM(L, rb, luaO_nilobject, ra, TM_LEN))
+                luaG_typeerror(L, rb, "get length of");
+            )
+          }
+        }
+        continue;
+      }
       case OP_LEN: {
         const TValue *rb = RB(i);
         switch (ttype(rb)) {

*1:実は内部的にも確保されているエントリ数は分かっても実際に生きているエントリまでは直接はわからない