やり直し)の実装

2023-10-15

テキストエディタ然りペイントツール然り、何かしらのデータや作品の編集ソフトを利用するならそこに「Ctrl+Z」の存在を期待してしまうのは現代人の性である。その手のツールを実用的に開発するならば、やはり「元に戻す」を真面目に実装することを迫られよう。

最近実際にそういう実装をやってみたことがあったので、そこで得られたアンドゥ・リドゥ実装の知見を書き留めておく。

以下に示すコードは全て疑似コードである。

抽象アンドゥ・リドゥの実装

大概の編集ソフトにおいて、変更操作というものは多様なものである。例えばペイントツールならばペンで線を描くとか、消しゴムで消すとか、キャンバスを広げるとか、いろいろある。テキストエディタでも入力と削除の2種類は最低限あろう。なのでそれらを統一的に表現できる機構が要る。

interface Operation {
    undo()
    redo()
}

doHistory = []    // 行われた操作の配列
undoHistory = []    // 元に戻された操作の配列

commitOperation(operation) {
    doHistory.push(operation)
    undoHistory = []    // 操作したらリドゥ不可に
}

undo() {
    lastOperation = doHistory.pop()
    lastOperation.undo()
    undoHistory.push(lastOperation)
}

redo() {
    lastUndoOperation = undoHistory.pop()
    lastUndoOperation.redo()
    doHistory.push(lastUndoOperation)
}

どう実装するとしても大体こんなものだろう。配列を2つ用意せずに、1つの配列と境界位置で管理する方法も取れるだろうが、本質的にはあまり変わらない。(そちらの方がメモリ効率は良いかもしれない。)

具体的なアンドゥの実装

一番簡単な実装は「操作される前のデータの全体を丸ごとコピーして保持しておく」ことである。アンドゥする場合は操作中のデータを全てそれに書き換えてしまえばよい。ただ、この場合当然メモリ効率は悪いし、全体をコピーするぶん処理負荷も高い。なので出来るだけ差分のみを保存しそれのみを反映させることが望ましい。

例えばテキストエディタならば変更された行のみを保持するとか、ペイントツールならばキャンバスの全体を格子状に区切って変更のあったマスのみのデータを保持するなどが考えられる。このように行なりマス目なり、区切り方はエディタの種類により様々だろうが、あまり細かく区切ると今度は区切るための処理負荷や各区画のデータを保持するためのメモリ負荷が問題になる可能性があるので注意。

具体的なリドゥの実装

こちらはアンドゥに比べると簡単なことが多いかもしれない。データではなくユーザーの操作情報をほぼそのまま記録して同じことを行えばいい。

操作に対するアンドゥ・リドゥを実装しようとしているということは前提として操作の処理が実装されているはずで、リドゥの処理にはそのコードの多くを再利用できるはずである。

ただし例外として、非常に重い処理の場合はアンドゥと同様に、操作情報ではなく操作後のデータを保持した方が良いかもしれない。

操作した位置の保持と復帰

適当なテキストエディタで多少長めのテキストファイルを開き、ある行を編集してみて欲しい。それからスクロールして、編集した部分を画面外にする。それからCtrl+Zをやってみるとどうだろう。編集した部分までカーソルが戻ったのではないだろうか。

このように、アンドゥ・リドゥ時にはデータが巻き戻る・進むだけでなく、カーソルの位置なども変わってくれた方がユーザーとしては心地が良い。というかそうなってくれないとアンドゥ・リドゥが行われたのか、それとも押し間違えたりして効かなかったのか、一見して分からないという問題があるため、実装した方がよい。

ただ、ペイントツールなどで急にキャンバスが動くと大変ということもありうるので、その辺はアプリケーションに合わせてという形にはなる。

実装

上の疑似コードで言うcommitOperation()あたりでそうした「現在の位置情報」を取得・保存してundo/redo時に反映させるのもアリだし、具体的な各操作のundo()/redo()の実装の側の責任にするのもアリだと思う。これもユースケース次第な気がする。

排他処理

編集ツールにおける何らかの操作というものは、例えば文字の削除のように(ユーザーにとって)一瞬で行われるものもあれば、逆にペイントツールにおける線の描画のように時間的長さを伴うものもある。このような時間的長さを伴う操作の場合、その最中にCtrl+Zが行われた場合が問題になる。何の対策もしなければ、操作中のデータと矛盾しておかしなことになりうる。

考えられる挙動は2通りある。

操作中にアンドゥが呼び出された場合、アンドゥを行わない
操作中にアンドゥが呼び出された場合、操作をキャンセルする

このどちらを選ぶかは好みによるだろう。ただいずれにしても「現在操作中である」ということをフラグを使って管理することになる。

アンドゥを行わないパターン

isOperating = false     // 操作中フラグ

beginOperation() {
    isOperating = true
}

commitOperation(operation) {
    doHistory.push(operation)
    undoHistory = []    // 操作したらリドゥ不可に
    isOperating = false
}

undo() {
    if (isOperating) return
    lastOperation = doHistory.pop()
    lastOperation.undo()
    undoHistory.push(lastOperation)
}

redo() {
    if (isOperating) return
    lastUndoOperation = undoHistory.pop()
    lastUndoOperation.redo()
    doHistory.push(lastUndoOperation)
}

操作をキャンセルするパターン

isOperating = false     // 操作中フラグ
nowOperation            // 現在進行中の操作

beginOperation() {
    isOperating = true
}

cancelOperation() {
    nowOperation.cancel()
    isOperating = false;
}

commitOperation() {
    doHistory.push(nowOperation)
    undoHistory = []    // 操作したらリドゥ不可に
    isOperating = false
}

undo() {
    cancelOperation()
    lastOperation = doHistory.pop()
    lastOperation.undo()
    undoHistory.push(lastOperation)
}

redo() {
    cancelOperation()
    lastUndoOperation = undoHistory.pop()
    lastUndoOperation.redo()
    doHistory.push(lastUndoOperation)
}

またさらに、アプリケーション次第ではアンドゥやリドゥにも(処理負荷などにより)時間がかかる場合というのがありうるが、その場合も適宜対策が必要と思われる。

メモリ最適化

注: この辺はまだ自分の手でやってないので仮説段階である。

アンドゥのための操作履歴のデータをそのまま保持していればメモリ負荷は高いので、適宜データ圧縮したり、メモリからファイルやデータベースに書き出したりした方が恐らく良い。しかし軽快なアンドゥ・リドゥが出来た方がユーザ体験はいいので、考えられる実装としては、近い(2～3操作以内とかの)操作履歴だけ無圧縮・メモリ内で保持して、遠い履歴は圧縮するなどがある。機会があればちゃんと実証したい。

ところでこの記事を書くきっかけとなった自作のソフトではこうした圧縮などやっていない訳であるが、最近のPCは性能が良いためか、ぶっちゃけこんな圧縮などしなくても中々問題にはならないようである。ヘビーな使い方をしたらどうか分からないが。

まとめ

アンドゥ・リドゥはナイーブな実装なら実は結構シンプルだが、操作中のアンドゥなどイレギュラーへの対応や負荷削減なども真面目にやろうとするとまあまあ大変な機能である。

ただし最近のマシンは性能が良いので、負荷という面についてはナイーブな実装でも割と使用に耐えることはあり、後々改良していくという方針でもそこまで悪くはないのではないかと思う。

Tech Notes