UTF-8 エンコーディングのままでバッファ・ギャップ

昨夜投稿したものの再投稿です。 更新しようとして操作ミスで削除してしまいました。

ピュア Ruby で記述した Emacs 風のテキスト・エディタ Textbringer は、 Ruby の String オブジェクトをバッファ・ギャップにしています。 バッファ・ギャップの要点はギャップの端と端の間だけで小さな部分文字列を動かすことにあります。 そのため、 Textbringer はバッファにしている String オブジェクトのエンコーディングをバイナリに設定し、 UTF-8 のバイト列を自力で扱い、 必要に応じて force_encoding メソッドで UTF-8 エンコーディングにしています。

現実問題として、 UTF-8 に限らず、 1 バイトを越える可能性があるエンコーディングを String オブジェクトに設定すると、 コード・ポイント位置とバイト位置、 コード・ポイント数とバイト数の変換のために、 内部表現のバイト列の先頭からの走査が生じてしまうため、 バイナリにするのは正解だろうとは思います。

ただ、 バイナリのままで文字列を扱うのは面倒くさいわけです。 Emacs を意識した重量級のテキスト・エディタならともかく、 もっとお手軽な用途のバッファでは UTF-8 エンコーディングなどのままでのバッファ・ギャップの方が気軽に使えることでしょう。

ということで、 マルチ・バイト・エンコーディングでも動く String オブジェクトを使ったバッファ・ギャップの書き方を考えてみます。 そのためには、 バッファ・ギャップとして必要なメモリ・コピーだけをおこなわせるために、 Ruby が内部でどのように String オブジェクトのメモリ・コピーをおこなうのかを、 あらかじめ調べておかなければ本末転倒になってしまいます。

文字列 str の beg 文字位置から len 文字数を val 文字列で書き換える式を例にとります。

str[beg, len] = val

str へのメッセージ式は、 内部では string.c の rb_str_aset_m 関数呼び出しを生じます。

ruby-2.5.1/string.c

static VALUE
rb_str_aset_m(int argc, VALUE *argv, VALUE str)
{
    /* 関連する箇所のみ抜粋 */
    rb_str_splice(str, NUM2LONG(argv[0]), NUM2LONG(argv[1]), argv[2]);
    return argv[2];
}

RubyVALUE から C の long に変換して rb_str_splice に移ります。 これは rb_str_update 関数の別名です。 なお、 上のメッセージ式では Range オブジェクトを渡すこともできます。 その場合でも、 途中に関数呼び出しが一段余計に挟まれるだけで、 rb_str_update 関数を呼び出すのは同じです。 rb_str_update 関数は、 レシーバの String オブジェクトのエンコーディングでの開始文字位置 beg と、 文字数 len を引数とし、 それから開始バイト位置と、 バイト数を求める変換をおこないます。 途中を略すと、 変換を終えてから rb_str_splice_0 関数を呼びます。

ruby-2.5.1/string.c

void                  /* beg と len は文字単位 */
rb_str_update(VALUE str, long beg, long len, VALUE val)
{
    /* 略 */
    beg = p - RSTRING_PTR(str); /* physical position */
    len = e - p;                /* physical length */
    rb_str_splice_0(str, beg, len, val);
    /* 略 */
}

rb_str_splice_0 関数は、 val が空文字でないときは、 str の beg バイト位置から len バイトを val の内容で置き換えます。 まず、 文字列本体を格納しているバイト配列が小さいときは大きくして、 その後は、 C 言語でお馴染みの memmove で文字列を置換します。 memmove は 2 箇所で使っており、 最初で、 val のバイト数と str の len バイト数が異なるとき、 str の後ろ側を移動しています。 その後、 beg 位置に val からのコピーをします。

ruby-2.5.1/string.c

static void
rb_str_splice_0(VALUE str, long beg, long len, VALUE val)
{
    /* 略 */
    long slen, vlen = RSTRING_LEN(val);
    /* 略 */
    RSTRING_GETMEM(str, sptr, slen);
    if (len < vlen) {
        /* expand string */
        RESIZE_CAPA(str, slen + vlen - len);
        sptr = RSTRING_PTR(str);
    }
    /* 略 */
    if (vlen != len) {
        memmove(sptr + beg + vlen,
                sptr + beg + len,
                slen - (beg + len));
    }
    if (vlen < beg && len < 0) {
        MEMZERO(sptr + slen, char, -len);
    }
    if (vlen > 0) {
        memmove(sptr + beg, RSTRING_PTR(val), vlen);
    }
    slen += vlen - len;
    STR_SET_LEN(str, slen);
    /* 略 */
}

バッファ・ギャップは最初の memmove をおこさせないためのテクニックです。 そのことから、 Ruby の String 文字列で、 バッファ・ギャップの動作にするには、 どのようなエンコーディングであれ、 同じバイト数で置換すれば良いということがわかります。 String オブジェクトは、 都合良く、 bytesize メソッドが利用できるので、 それを使って移動したい部分の文字数とバイト数のつじつまを合わせてやれば良いわけです。 ギャップは空白で埋めることにします。 つまり、 これは空白が 1 バイトであるエンコーディング用です。

文字列末尾 4 つの空白は、 コピー・オン・ライトでバッファ文字列本体の複製が生じないようにするためのバッドノウハウの仕込みです。 現在の rubys[ge .. -1] のように文字列の途中から末尾までを部分文字列として切り出すと、 元の s の文字列本体を共用します。 共用元文字列の印付きの s を更新すると、 s の文字列本体を複製してから更新します。 困ったことに、 共用元文字列の印を消す方法が今のところありません。 そこで、 ギャップ・バッファのような場合は末尾にダミーの文字を並べておいて、 末尾を含んだ部分文字列を絶対に切り出さないようにします。

# -*- coding: utf-8 -*-
s = "ruby の UTF-8 文字列は                       マルチバイトで格納してあります。    "
p [s].pack('P')     #=> "\xA8\x96\xC4\t"  RString 構造体の ptr (リテラル文字列のアドレス)
s[0] = s[0]         #   リテラル文字列から文字列を複製させるための空更新
p [s].pack('P')     #=> "\xD0\x14\xAC\t"  複製後のアドレス

# s[ge .. -1] は次の s の更新で文字列全体の複製を生じるので絶対に使わないこと。
p s[0 ... -4]
#=> "ruby の UTF-8 文字列は                       マルチバイトで格納してあります。"

gs, ge = 17, 40
s.encoding          #=> #<Encoding:UTF-8>
p s[0 ... gs]       #=> "ruby の UTF-8 文字列は"
p s[ge ... -4]      #=> "マルチバイトで格納してあります。"

現点 pt がギャップ開始位置 gs より大きな 17 + 6 文字位置にあるとします。 この場合、 ギャップ終了位置 ge から 6 文字を gs に移動するとギャップを現点に移動したことになります。 この移動の際に、 ruby 内部での最初の memmove が生じないようにしたいわけです。 そのため、 まず移動対象を t に求めた後、 t のバイト数の空白列で置き換えます。 t と空白列は同じバイト数なので、 内部では 2 番目の memmove しか実行されません。 続いて、 gs からの t のバイト数の空白列を t で置き換えます。 このときも空白列と t は同じバイト数なので、 内部では 2 番目の memmove しかおこないません。 ギャップの内容を移動したら、 gs と ge を文字数分移動します。

pt = gs + 6
count = pt - gs
t = s[ge, count]    #=> "マルチバイト"  移動対象
p t.size            #=> 6 文字
p t.bytesize        #=> 18 バイト

s[ge, count] = ' ' * t.bytesize
s[gs, t.bytesize] = t
gs += count         #=> 23
ge += count         #=> 46

p s[0 ... -4]
#=> "ruby の UTF-8 文字列はマルチバイト                       で格納してあります。"
p [s].pack('P')     #=> "\xD0\x14\xAC\t"  アドレスは変化してません。
p s[0 ... gs]       #=> "ruby の UTF-8 文字列はマルチバイト"
p s[ge ... -4]      #=> "で格納してあります。"

今度は現点がギャップより前にあるときです。 上に続いて 6 文字を移動してみます。 ギャップの前の 6 文字をギャップの終わりに移動します。 まず、 ギャップから 6 文字前を t に入れ、 そのバイト数分の空白列で置き換えます。 さて、 ここで、 ギャップの終わりを示す ge が文字単位であることを思いだしましょう。 6 文字 18 バイトを、 18 文字 18 バイトで置き換えたので、 ge の文字単位の位置が 18 文字 - 6 文字ずれてしまっています。 その分を補正すると、 t を置き換える文字単位の位置は ge - 18 ではなく、 ge - 6 になります。 この文字位置から t のバイト数分の空白列を t で置き換えます。

pt = 17
count = pt - gs     #=> -6 文字
t = s[pt, -count]   #=> "マルチバイト"  移動対象  6 文字 18 バイト
s[pt, -count] = ' ' * t.bytesize
# ge + (t.bytesize - (-count)) - t.bytesize
s[ge + count, t.bytesize] = t
gs += count         #=> 17
ge += count         #=> 46

p s[0 ... -4]
#=> "ruby の UTF-8 文字列は                       マルチバイトで格納してあります。"
p [s].pack('P')     #=> "\xD0\x14\xAC\t"  アドレスは変化してません。
p s[0 ... gs]       #=> "ruby の UTF-8 文字列は"
p s[ge ... -4]      #=> "マルチバイトで格納してあります。"

文字単位とバイト単位のつじつまを合わせておけば、 文字単位での文字操作であっても、 バッファ・ギャップのふるまいをさせることができることを確かめたので、 クラスにしておきます。

# -*- coding: utf-8 -*-

class GapBuffer
  INITSIZE = 4096
  TAILHACK = 4

  def initialize()
    @data = ' ' * INITSIZE
    @gap_start = 0                      # 文字単位
    @gap_end = @data.size - TAILHACK    # 文字単位
  end

  def size() @data.size - (@gap_end - @gap_start) - TAILHACK end

  def gap_move(point)       # point: 文字単位
    count = point - @gap_start
    if count > 0
      t = @data[@gap_end, count]
      @data[@gap_end, count] = ' ' * t.bytesize
      @data[@gap_start, t.bytesize] = t
    elsif count < 0
      t = @data[point, -count]
      @data[point, -count] = ' ' * t.bytesize
      @data[@gap_end + count, t.bytesize] = t
    end
    @gap_start += count
    @gap_end += count
    self
  end
end