テキスト・エディタの Undo

Emacs 系のテキスト・エディタは文字を一文字ずつバッファに self-insert-command で挿入していきます。 ところが、 Undo コマンド (C-x u) は、 挿入単位の一文字ごとではなく、 一連の文字挿入をまとめて巻き戻すように作ってあります。 一連の文字削除も同様です。 この一連まとめ Undo を作ってみます。 さらに、 バッファ名とファイル名も undo の対象に加えておきます。

一連まとめ Undo を組み込むのは Buffer クラスとします。 そこから関連する部分だけを抜き出していきます。 Undo のためのジャーナリングnil 終端の単方向リストにしています。 単方向リストの項目は 4 種類あります。 Ins はどこに何文字挿入したかを記録したものです。 Del はどこから文字列を削除したかを記録します。 Ren はバッファに結びついているファイル名の変更を記録します。 UndoGroup は置換等で Ins と Del をまとめて Undo するための区画を表します。 Buffer のリビジョン revision は、 ゼロから始まり挿入・削除ごとにカウント・アップしていきます。 revision_head は、 ファイル読み書き時に revision の値をコピーしたもので、 revision がこの値に一致しているときはバッファが未変更状況にある特別なリビジョンであるかどうかを調べるためのものです。

Ins = Struct.new(:rev, :head, :point, :count, :tail)
Del = Struct.new(:rev, :head, :point, :data, :tail)
Ren = Struct.new(:rev, :head, :filename, :name, :tail)
UndoGroup = Struct.new(:bottom, :tail)

class Buffer
  attr_reader :filename, :name, :revision

  def initialize()
    @filename = ''
    @name = 'UNTITLED'
    @content = GapEditor.new
    @revision = @revision_head = 0
    @journal = nil
    @undo_group_bottom = nil
    @enable_undo = true
    #略
  end

#@<enable_undo@>
#@<flush_undo@>
#@<insert@>
#@<delete@>
#@<undo_group@>
#@<undo@>
#@<undo_step@>
end

enable-undo コマンドの本体です。 ジャーナリング機能をオンにします。

#@<enable_undo@>=
  def enable_undo()
    @enable_undo = true
    self
  end

flush-undo コマンドの本体です。 ジャーナリング機能をオフにして、 記録済みのリストも捨てます。

#@<flush_undo@>=
  def flush_undo()
    @journal = nil
    @enable_undo = false
    self
  end

挿入の場合、 直前も挿入のときはジャーナリング・リストの先頭も Ins です。 そのとき、 先頭の Ins に記録された挿入された文字列の末尾に追加するときは、 Ins の文字数に追加分を足します。 self-insert-command による一連の挿入は、 この場合に相当します。 Ins に記録された挿入された文字列の先頭に追加するときも、 追加分を足します。 それ以外のときは、 新しく Ins をリストに加えます。 実際の挿入処理は、 行の折り返しで説明した content_insert メソッドにまかせます。

#@<insert@>=
  def insert(dot, str)
    ! str.empty? or return self
    if @enable_undo
      if Ins === @journal && @journal.point + @journal.count == dot.point
        @journal.count += str.size
      elsif Ins === @journal && @journal.point == dot.point
        @journal.count += str.size
      else
        @journal = Ins.new(@revision, @revision_head, dot.point, str.size, @journal)
      end
    end
    content_insert(dot, str)
  end

削除の場合、削除する文字数が負のときがあるので、 文字数を正に揃えます。 一連の削除の場合も、 直前の削除の末尾側を続けて削除するときは、 Del に記録してある削除された文字列の末尾へ削除しようとしている文字列を追加します。 先頭側を続けて削除するときは、 削除された文字列の先頭へ削除しようとしている文字列を挿入します。 これら以外のときは、 新しく Del を追加します。 実際の処理を content_delete にまかせるのは、 挿入と同じです。

#@<delete@>=
  def delete(dot, count)
    if count > 0
      count = [count, self.size - dot.point].min
    elsif count < 0
      count = [-count, dot.point].min
      dot.point -= count
    end
    count != 0 or return self
    if @enable_undo
      if Del === @journal && @journal.point == dot.point
        @journal.data << slice(dot.point, count)
      elsif Del === @journal && @journal.point == dot.point + count
        @journal.point = dot.point
        @journal.data.insert(0, slice(dot.point, count))
      else
        str = slice(dot.point, count)
        @journal = Del.new(@revision, @revision_head, dot.point, str, @journal)
      end
    end
    content_delete(dot, count)
  end

文字列置換のときは、 Ins と Del が組になります。 そのようなときは、 組の始まりをメモしておいて、 Ins と Del をリストに加えた後に、 リストの先頭に UndoGroup を追加します。 UndoGroup の bottom 欄に、 組を始める直前の巻き戻し位置を格納します。

#@<undo_group@>=
  def undo_group()
    undo_group_begin()
    begin
      yield
    ensure
      undo_group_end()
    end
    self
  end

  def undo_group_begin()
    @undo_group_bottom = @journal
    self
  end

  def undo_group_end()
    if @enable_undo
      @journal = UndoGroup.new(@undo_group_bottom, @journal)
    end
    @undo_group_bottom = nil
  end

ファイルからバッファへ読み込むとき、 バッファからファイルへ書き出すときに、 ファイル名の変更があるときも、 変更履歴を記録します。

  def filename_and_name_set!(filename, name)
    if filename != @filename || name != @name
      if @enable_undo
        @journal = Ren.new(@revision, @revision_head, @filename, @name, @journal)
      end
      @filename = filename
      @name = name
    end
    self
  end

Undo コマンドの本体です。 ジャーナリング・リストの先頭が UndoGroup のときは、 bottom が露出するまで、 Undo を繰り返します。 そうでないときは、 一段階だけ Undo をします。

#@<undo@>=
  def undo(dot)
    case @journal
    when UndoGroup
      bottom = @journal.bottom
      @journal = @journal.tail
      while ! @journal.nil? && ! bottom.equal?(@journal)
        undo_step(dot)
      end
    else
      undo_step(dot)
    end
    self
  end

Undo の一段階では、 Ins、 Del、 Ren の巻き戻しをします。 Ins に対しては削除で、 Del に対しては挿入でバッファの内容を戻します。 Ren はファイル名とバッファ名を書き戻します。 ところで、 Emacs ではバッファのどこを書き戻したのかを知らせるため、 現点を書き戻し座標に移します。 ここでの書き戻しに伴う現点移動はそのような移動になっています。 なお、 content_insert と content_delete は バッファのリビジョンを進めるため、 リビジョンの巻き戻しを、 これらが終わった後でおこなわなければなりません。

#@<undo_step@>=
  def undo_step(dot)
    case @journal
    when Ins
      dot.point = @journal.point
      content_delete(dot, @journal.count)
    when Del
      dot.point = @journal.point
      content_insert(dot, @journal.data)
    when Ren
      @name = @journal.name
      @filename = @journal.filename
    else
      return
    end
    @revision, @revision_head = @journal.rev, @journal.head
    @journal = @journal.tail
  end