テキスト・エディタの行の折り返し表示 その 4 - キャッシュ更新の改善

行の折り返し表示 その 3」 でテキスト・エディタで長い文書ファイルを開いても、 表示速度が極端に落ちないようにと、 行の折り返し表示のための書記素クラスタ情報をキャッシュすることにしました。 ところが、 キャッシュは良いことばかりではないようで、 キー入力による文字挿入・削除の応答性を改善するために速度を落としている箇所を探してみたところ、 キャッシュ追加時の each ループが原因になっていました。

#@<unshift@>=
  def unshift(value)
    # 問題部分
    each do |e|                                                     # !
      if e.value.last >= value.first && value.last > e.value.first  # !
        delete(e)                                                   # !
      end                                                           # !
    end                                                             # !
    super(value)
  end

このループは、 バッファが改行で終わるとき、 バッファ末尾の書記素クラスタ情報で line.first == line.last になっておりキャッシュに残っていた分を削除するのに必要でした。 他の場合は、 行内の場所 loc に対して、 line.first <= loc < line.last がなりたつので文字挿入・削除時にキャッシュから削除できていました。

改善前

  バッファ          書記素クラスタ情報
  "quick brown\n"   Lines.new(0, 12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
  "fox jumps\n"     Lines.new(12, 22, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  ""                Lines.new(22, 22, [0])

バッファ末尾を含めて、 すべての書記素クラスタ情報で、 line.first <= loc < line.last がなりたてば、 挿入・削除時にキャッシュから削除できる理屈で、 キャッシュ追加時の余計な重い each ループが不要になります。 そのためには、 擬似的にバッファ末尾を表す制御文字があるかのように書記素クラスタ情報を作れば良いわけです。 つまり、 バッファの正味の文字数は 22 文字なのですが、 擬似末尾制御文字を含めて書記素クラスタを 23 個とします。

改善後

  バッファ          書記素クラスタ情報
  "quick brown\n"   Lines.new(0, 12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
  "fox jumps\n"     Lines.new(12, 22, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  ""                Lines.new(22, 23, [0, 1])

改善後では、 バッファ末尾が改行で終わってないときも同様に考えて、 擬似的なバッファ末尾文字があるかのように書記素クラスタ情報を作ることにします。 この場合、 バッファの正味の文字数は 21 文字なのですが、 擬似末尾制御文字を含めて書記素クラスタを 22 個とします。

改善後

  バッファ          書記素クラスタ情報
  "quick brown\n"   Lines.new(0, 12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
  "fox jumps"       Lines.new(12, 22, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

ギャップ・バッファの作る書記素クラスタ情報 Line は行の折り返しを考慮しません。 求めたいユーザ座標 loc を含む改行文字と改行文字の間を行として、 その中に含まれている書記素クラスタの開始ユーザ座標の相対値をリストアップします。 前のコードではギャップを挟むとき、 文字列に切り出してから書記素クラスタの開始位置を求めていたのですが、 今回はそこも改善し、 文字列切り出しなしで書記素クラスタをたどっていきます。 その場合、 書記素クラスタの途中にギャップが開いている可能性があるので、 ギャップの直前の書記素クラスタを、 ギャップ直後へ移動してから書記素クラスタをもう一度、 同じ文字からたどらせています。 ただし、 この改善による応答性への寄与は小さく、 上の each ループの除去ほどの効果はありません。

Line = Struct.new(:first, :last, :h)

class GapEditor
  GRAPHEME_CLUSTER = %r/\G\X/

  def grapheme_clusters_of_line(loc)
    left = find_first_in_backward("\n", loc, false)
    dol = find_first_in_forward("\n", loc, false)
    line = Line.new(left, dol + 1, [])
    right = (dol < size) ? dol + 1 : dol
    data = @data
    i = left
    if left < @gap_start && @gap_start < right
      gs = @gap_start
      while i < gs
        line.h << i - left
        i = GRAPHEME_CLUSTER.match(data, i).end(0)
      end
      gap_move(left + line.h.last)
      line.h.pop
      i = @gap_start
    end
    gap = right <= @gap_start ? 0 : @gap_end - @gap_start
    i, left_gap, right_gap = i + gap, left + gap, right + gap
    while i < right_gap
      line.h << i - left_gap
      i = GRAPHEME_CLUSTER.match(data, i).end(0)
    end
    while true
      line.h << right - left
      (line.h.last + line.first < line.last) or break
      right += 1
    end
    line
  end

  # 省略
end

末尾の特別扱いが不要になったので、 キャッシュへの追加時の削除が不要になり、 unshift は Cache クラスのものをそのまま使えるようになります。 キャッシュからの検索に使う条件式も素直になります。

class RangeCache < Cache
  def lookup(loc)
    each do |e|
      r = e.value
      if r.first <= loc && loc < r.last
        touch(e)
        return r
      end
    end
    nil
  end
end

Buffer クラスで、 書記素クラスタ情報 Line をキャッシュするやりかたは、 前のままで変化はありません。 キャッシュにあるときは、 それを使い、 ないときはギャップ・バッファに Line オブジェクトを作ってもらってキャッシュに追加します。

class Buffer
  def grapheme_clusters_of_line(loc)
    line = @line_cache.lookup(loc)
    if line.nil?
      line = content.grapheme_clusters_of_line(loc)
      @line_cache.unshift line
    end
    line
  end

#@<content_insert, content_delete@>

  # 省略
end

文字挿入・削除で、 以前はバッファの内容を更新してからキャッシュとマークを更新していたのですけど、 更新の順番が逆の方が、 デバッグ時の挙動の追跡がわかりやすいことに気がついたので、 逆にしています。

#@<content_insert, content_delete@>=
  def content_insert(dot, str)
    count = str.size
    screen.window_of_buffer_owner(self).each do |win|
      update_mark_insert(win.mark_list, dot, count)
      update_cache(win.layout.cache, dot, 0, count)
    end
    update_mark_insert(@mark_list, dot, count)
    update_cache(@line_cache, dot, 0, count)
    content.insert(dot.point, str)
    dot.point += count
    @revision += 1
    self
  end

  def content_delete(dot, count)
    count_abs = count.abs
    screen.window_of_buffer_owner(self).each do |win|
      update_mark_delete(win.mark_list, dot, count_abs)
      update_cache(win.layout.cache, dot, count_abs, -count_abs)
    end
    update_mark_delete(@mark_list, dot, count_abs)
    update_cache(@line_cache, dot, count_abs, -count_abs)
    content.delete(dot.point, count)
    @revision += 1
    self
  end

#@<update_cache@>

キャッシュの更新は前のままです。 そのままでもバッファ末尾のキャッシュを扱えるようになりました。 次のコードは dot.point をくくりだしただけで、 本質は前と同じです。

#@<update_cache@>=
  def update_cache(cache, dot, count1, count2)
    loc = dot.point
    cache.each do |e|
      if e.value.first <= loc + count1 && loc < e.value.last
        cache.delete(e)
      elsif e.value.first > loc
        e.value.first += count2
        e.value.last += count2
      end
    end
  end

Layout クラスが、 書記素クラスタ情報 Line から行を折り返して、 Grid を作ります。 Line の変更によって、 影響を受けるのは、 現在の Grid がバッファ末尾を含むことをチェックする箇所です。 今度は、 grid.last がバッファ・サイズを越えていることを調べるようにします。

class Layout
  def eos?()
    @grid.last > window.buffer.size
  end

#@<layout@>

  # 省略
end

書記素クラスタ開始位置配列から行の折り返し位置を求める layout クラスは前と同じで良いのですが、 バッファ末尾でも Line の開始位置配列が必ず 2 個以上になったことから、 末尾が 1 個のときを特別扱いしなくて済むようになります。

#@<layout@>=
  def layout(loc)
    tty = window.screen.tty
    buffer = window.buffer
    @grid = @cache.lookup(loc)
    if @grid.nil?
      tab_width = buffer.mode.tab_width
      width = window.size.x
      line = buffer.grapheme_clusters_of_line(loc)
      @grid = Grid.new(line.first, line.last, [[]])
      x = 0
      line.h.each_index do |j|
        loc = line.h[j] + line.first
        len = line.h[j + 1] - line.h[j]
        ch = loc < buffer.size ? buffer[loc] : END_BUFFER
        span = END_BUFFER == ch ? 0 \
             : "\n" == ch ? 0 \
             : "\t" == ch ? tab_width - (x % width) % tab_width
             : ch.ord < 0x20 ? 2
             : tty.wcwidth(ch.ord)
        if x % width + span > width
          x += width - x % width
          @grid.v << []
        end
        @grid.v[-1] << HBox.new(line.h[j], len, span)
        if span > 1
          (span - 1).times {|d| @grid.v[-1] << HBox.new(line.h[j], 0, -(d + 1)) }
        end
        break if END_BUFFER == ch || "\n" == ch
        if x % width + span >= width
          @grid.v << []
        end
        x += span
      end
      @cache.unshift @grid
    end
    self
  end

以上で、 キャッシュの更新を挿入・削除時に完了させることができるようになり、 キャッシュ追加時のループを削除することができました。 しないでも良い無駄な処理をしないで済ますようにデータを構成する大切さを体感できる事例でした。