lstring

lstring は文字列を取り扱っている。まずヘッダファイルを見てみる。たとえば次の定義は文字列の長さを計算するものであるようだ。

#define sizestring(l)   (cast(lu_mem, sizeof(union TString))+ \
                         (cast(lu_mem, l)+1)*sizeof(char))

cast というのはマクロで、次のように定義されている。つまり、キャストを行うだけのものだ。

#define cast(t, exp)    ((t)(exp))

キャストは厳密にやろうとするとカッコが頻出してわかりづらくなるからこのようにしているのだろう。 TString は、先週の lobject.h にひっそりと定義されている。

typedef union TString {
  L_Umaxalign dummy;  /* ensures maximum alignment for strings */
  struct {
    CommonHeader;
    lu_byte reserved;
    lu_hash hash;
    size_t len;
  } tsv;
} TString;

reserved はおそらく確保されている文字列のサイズ、 len は文字列の長さ、hashはハッシュ値だろう。つまり文字列の(lua上の)オブジェクトのメタデータを持っているデータオブジェクトである。ハッシュ値をあらかじめ計算しておくというスタイルなのは、 lua がテーブルを多用し、また、キーには文字列が非常に多いため、効率の問題だろうか？

で、ようするに TString のサイズと文字列それ自体の長さから文字列データのメモリ上の大きさを計算するというマクロが sizestring であるようだ。ユーザプログラムから使うものではなくて、ほかのところで使うのだろう(grepすると lgc.c と lstring.c でしか使われていない)。 TString でない方の記述がもうひとつよくわからないが、気にせず進む。

ヘッダファイルをもう少し見ると、 luaS_new と luaS_newliteral という2つが lua で文字列を確保するための基本関数であることがわかる。またさらに、これらはマクロで、実体は luaS_newstr だということがわかる(文字列の長さを明示的に指定するときにはこちらを使うようだ)。 new と newliteral の差は、後者は(Cレベルでの)文字列リテラルしか受け付けないところにある。 "a" "b" という表現は C で可能だが(2つの文字列を連結したものと解釈される)、これを利用してコンパイル段階でエラーとして弾いている。

さて、 luaS_newstr の実装は次のようになる。

TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  GCObject *o;
  lu_hash h = (lu_hash)l;  /* seed */
  size_t step = (l>>5)+1;  /* if string is too long, don't hash all its chars */
  size_t l1;
  for (l1=l; l1>=step; l1-=step)  /* compute hash */
    h = h ^ ((h<<5)+(h>>2)+(unsigned char)(str[l1-1]));
  for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
       o != NULL;
       o = o->gch.next) {
    TString *ts = gcotots(o);
    if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0))
      return ts;
  }
  return newlstr(L, str, l, h);  /* not found */
}

lua_State は初出で筆者もよくわからないが、 VM の状態(変数とか、定義済の定数とか)を管理している実体だと思う。たぶん。この関数では、主にハッシュの計算をしている。ハッシュの計算方法はなかなか複雑で、文字列の長さを初期のキーとし、末尾からstep文字ごとに計算をしている。で、このハッシュはどう使うかというと、先述したのとちょっと違っている。 G は lua_state のグローバルステートを取り出すもので、 strt は stringtable 。つまり lua の VM は「いま取り扱っている文字列」というのをぜんぶ持っているというわけだ。もし新しい文字列を取り出そうというときに、もうそれがあるならそれを返しておしまい。発見されなかったら newlstr で新しいものを作る、ということだろう。

newlstr の実装は次のとおり。

static TString *newlstr (lua_State *L, const char *str, size_t l, lu_hash h) {
  TString *ts = cast(TString *, luaM_malloc(L, sizestring(l)));
  stringtable *tb;
  ts->tsv.len = l;
  ts->tsv.hash = h;
  ts->tsv.marked = 0;
  ts->tsv.tt = LUA_TSTRING;
  ts->tsv.reserved = 0;
  memcpy(ts+1, str, l*sizeof(char));
  ((char *)(ts+1))[l] = '\0';  /* ending 0 */
  tb = &G(L)->strt;
  h = lmod(h, tb->size);
  ts->tsv.next = tb->hash[h];  /* chain new entry */
  tb->hash[h] = valtogco(ts);
  tb->nuse++;
  if (tb->nuse > cast(ls_nstr, tb->size) && tb->size <= MAX_INT/2)
    luaS_resize(L, tb->size*2);  /* too crowded */
  return ts;
}

というわけで sizestring はここで使われている。 luaM_malloc はたぶん、 GC 用に malloc するというものだと思うのでその時まで詳細ははぶく。 sizestring には、メモリ確保用の l が使われている。つまり「文字列の長さが l のときの『lua上の文字列を表現したデータオブジェクト』のサイズ」が sizestring ということだ。 sizestring で +1 しているのは、文字列がつねに null 終端するために1文字余計に必要だから。

最初はヘッダ部にデータを与えている。 reserved は 0 のママなので、筆者の予想とは違っているようだ。このフィールドを使う場面まで後回し。ちなみに marked と tt というのは CommonHeader の方に入っている。
次の memcpy はちょっと特殊だが、ようするに「TStringなパートと文字列部分」がそのまま連結されたものを luaM_malloc で返させているということだろう。

確保したものは strt の hash 番目にプッシュしている。そして nuse (number of use＝つまり利用されている文字列の個数)をインクリメントしている。ハッシュ表で nuse が size を越えているときにはハッシュが密になりすぎていると判断してハッシュの大きさを変えているようだ。ハッシュの大きさを変更する luaS_resize は、大筋はそんなに難しくないので割愛する。

lstring には、なぜか user data を確保する luaS_newudata もあるが、こちらも詳細は省く。