Katashin .info

テキスト編集における Selective Undo を実装した

Selective Undo とは、その名の通り Undo したい処理を選択することのできる Undo のことです。テキスト編集で Selective Undo をするためのライブラリを書いたので、それを実装する上で学んだことを簡単に述べます。

基本的なコンセプト #

Selective Undo を実現するための手法は複数あるのですが、この記事では操作の逆変換を用いる Selective Undo について述べます。

逆操作を生成、実行する #

ある操作 A があるとき、その逆操作 A' は、A を打ち消す操作のことを指します。例えば、文字列 'abc' を 5 番目に挿入する操作 ins(5, 'abc') がある時、5 番目から 3 文字削除する操作 del(5, 3) は ins(5, 'abc') の逆操作と言えます。定義から、元の操作 A と逆操作 A' の両方を実行した時、得られる文字列は入力した文字列と同一であるということが言えます。すなわち、操作 A を Undo したい時はその逆操作 A' を生成し、実行すれば良いということになります。

しかし、Undo を選択可能にするためには、逆操作を生成するだけでは不十分であり、生成した逆操作を変換する必要があります。なぜなら、Undo したい操作が実行された時の文字列の内容が、現在の文字列の状態と異なることにより、得られる結果が期待していないものとなる場合があるためです。

例えば、操作 A = ins(0, 'abc') で、操作 B = ins(0, '123') とします。A, B がこの順番で実行された時、文字列は '123abc' となります。このとき、操作 A の逆操作を実行すると、A' = del(0, 3) となり、文字列は 'abc' となります。操作 A は 'abc' を挿入する操作なので、逆操作 A' は 'abc' を消すことが期待されますが、'123' が消されてしまいました。

これは、操作 B が実行されたことで、対象の文字列の場所がずれてしまったためです。このようなことを防ぐために、次で述べる操作変換を行う必要があります。

現在のコンテキストに適用できるようになるまで操作変換する #

ある操作 A, B があるとき、操作変換とは A, B から変換後の操作 A', B' を生成することであり、A(B(text)) == B'(A'(text)) となります (B, A の順で実行した時の結果と A', B' の順で実行した時の結果が一致する)。ただし、Selective Undo の実装上は、逆操作の変換結果のみを使用するのみで良いです。その説明は長くなりそうなので省略しますが、直感的には逆操作ではない方の操作は、履歴にすでに入っている操作であるため、変換する必要がないというイメージです。

ここで、コンテキストとは、ある操作を実行するときの、全体の文字列の状態を指します。操作を実行する時は、その操作が想定しているコンテキストと、現在のコンテキストが一致していなければ、正しい結果が得られません。これは、前の節で述べた、操作の順番によって期待される結果が得られないという話と同じです。

逆操作を操作変換する流れは以下のとおりになります。操作 A, B, C があり、操作 A を Undo したいとき、逆操作 A' が生成されます。このとき、操作の履歴は以下のようになり、A' は A が実行された直後のコンテキストを期待しています。操作は左から右に適用されるとし、カッコはカッコ内の操作がその位置で実行されることが期待されていることを示します。

A (A') B C [現在のコンテキスト]

A' を現在のコンテキストで適用できるようにするため、操作変換を行います。まずは A' と B で操作変換します。

A B (A'') C [現在のコンテキスト]

次に A'' と C で操作変換します。

A B C (A''')[現在のコンテキスト]

A''' は現在のコンテキストに適用できるようになったため、A''' を実行することで A の Undo となります。

実装 #

各操作ごとのクラスを作り、それぞれが apply, inverse, transform メソッドを持つようにしています。

apply はその操作を実行させるためのメソッドで、引数で渡された文字列に対して操作を行います。

inverse はその操作の逆操作を生成するためのメソッドです。削除操作に関しては、何を削除したのかがわからなければ逆操作を生成することができないため、apply が実行された後でなければエラーを投げるようにしています。

transform は引数に渡された操作から、自分自身を操作変換するメソッドです。操作変換は、Selective Undo を適用するアプリケーションに依存する処理で、かつ、操作の種類の組み合わせごとに処理を書かなければならないので、最も実装が大変な部分だと思います。

また、undo 時に逆操作を生成、操作変換を行う処理は Buffer クラスに書いています。主要な処理は各操作のクラスに書いているため、こちらはすっきりしてます。

未実装部分など #

Undo の使い勝手を良くするために、追加した文字列が連結可能な場合など、まとめることのできる操作はまとめるのが良いと思いますが、それはまだ実装していません。また、テストを十分にしているわけではないので、Undo の結果がおかしかったり、人間の直感に反する場合があると思います。

Selective Undo が最も活きるユースケースが複数人で一つの文書を編集しているときだと考えているため、そういったケースで使えるようにはしたいです。複数人で編集できるようにするには Operational Transformation の実装などしないといけないのでかなりめんどくさそうですが……。以前、Google Wave OT は実装したのですが、Selective Undo と組み合わせた時にどうなるかなど、考慮すべき点はまだまだありそうです。

参考文献 #

Selective Undo の基本的な考え方は以下の論文から。

操作変換の部分は Operational Transformation と似てるので、以下も参考になると思います。