この記事はGoodpatch Advent Calendar 2019 4日目の記事です。
私は普段Ruby on RailsのREST APIのインフラ・バックエンド周りが多いですが、最近は、TypeScriptでフロントエンドとバックエンドをつなぐ部分なども担当しています。
今回は、まだ実装中ですが、 チームでの共同編集が必要なアプリケーションのUndo/Redo の設計と実装について簡単に紹介します。
（アプリケーションの内容はまだ詳しくかけないので、その辺は察してください 
）
前提条件など
Undo/Redoとは
まず一般的なUndo/Redoは以下のような解釈でほとんどのユーザーでズレがないと思います。
- Undo
コンピューターの用語で直前に ユーザが 行った 操作を取り消し 、 元に戻す こと。データベースの専門用語ではロールバック。
Undo - Wikipedia
- Redo
コンピューターの用語で直前に ユーザが 行った 操作を取り消したことを取り消し 、 元に戻す こと。データベースの専門用語ではロールフォワード。
Redo - Wikipedia
概ねこんな感じだと思います
その上で、Undo/Redoに対するユーザーのメンタルモデルとしては、 自分自身の変更を取り消す つもりだと予測されるため、他人の変更まで取り消すつもりはない と考えられます。
「チームでの共同編集を行う」場合の特徴
シングルユーザーの場合と異なり、チーム内の複数のユーザーが、共同編集を行う場合はこんな感じになると考えられます。
- 色を変えたい人
- 太字にしたい人
- テキスト編集する人（まだ編集している最中だけどみんなに見せたい）
などなど
（ちなみに、今回はシームレスな共同編集のために、必要な時以外はロックをかけない方針としています ）
これを簡単に整理すると以下のようなことを実現する必要があります
-
みんなが同じモノを変えていく
- 例えば、１つのDBのレコード
-
みんなが違うトコロを変えていく
- 例えば、違うDBのカラムに対して
-
みんなが変えたらすぐに見える
- 例えば、議事録が途中で見える
共同編集のためのUndo/Redoとは
上記から、必要なUndo/Redoの条件を以下のように定義しました。
-
みんなが同じモノを変えていくので、
-
ユーザー個人が 行った操作のみをUndo/Redoする
- 他の人が行った操作は取り消さない
-
ユーザー個人が 行った操作のみをUndo/Redoする
-
みんなが違うトコロを変えていく ので
-
ユーザー個人が 行った操作によって変わった箇所 のみ をUndo/Redoする
- 全部を元に戻すわけではない
-
ユーザー個人が 行った操作によって変わった箇所 のみ をUndo/Redoする
-
みんなが変えたらすぐに見える ようにしたいので、
-
ユーザー個人が 行った 操作による変更は随時反映させるが、 履歴保持するタイミングを調整 する
- ユーザーのundo/redoのメンタルモデルに従い、キリの良いところでをUndo/Redoの単位にする
-
ユーザー個人が 行った 操作による変更は随時反映させるが、 履歴保持するタイミングを調整 する
実装していくためには 
一般的なUndo/Redoの実装例
まずは一般的な実装例を確認してみました。
- データの状態を履歴として保持して切り替える
- データの操作を履歴として保持して切り替える
1. データの状態を履歴とする
- データの状態の履歴全てと、現在の位置を保持する(mementoデザインパターン的な)
代表的なライブラリ： GitHub - omnidan/redux-undo: higher order reducer to add undo/redo functionality to redux state containers
{
past: [{ text:"a", color: "yellow" }],
present: [{ text:"b", color: "yellow" }],
future: [{ text:"b", color: "green" }],
}
共同編集時の問題点
- 以下の図のように自分の変更以外の状態も元に戻ってしまう
2. データの操作を履歴とする
- データの操作の履歴全てと、現在の位置を保持する(commandデザインパターン的な)
{
commands: [
create({ text:"a", color: "yellow" }),
update({ text:"b" }),
update({ color:"green" }),
]
}
- DBのREDOログとかはまさに、ほぼ、これだと思う。
- 戻す時に最初からコマンドを全て実行する必要があるので、時間がかかる
選択したUndo/Redoの方法
悩んだ挙句、 こちらの記事 に書いてある方法がとても良さそうだったので、採用！ 
- そのユーザーのデータの状態から変更差分のみを抽出して、操作履歴として保持
- 変更差分を戻す操作(Undo)をJSON-Patchとして保持(ChangePatch)
- 変更差分を戻す操作の取り消しのための操作(Redo)もJSON-Patchとして保持(InversePatch)
これで共同編集でも問題なくUndo/Redoできそうです
JSON-Patchについて
JSON-Patchは
JSON （ JavaScript Object Notation ）文書に適用する 一連の演算を表出するための JSON 文書構造を定義する
というものなので、JavaScriptのObjectに対してもほとんど適用可能だと思います。
詳しくは以下のリンクに記載されています。
RFC 6902 - JavaScript Object Notation (JSON) Patch （日本語訳）
保持するデータ
/color を green > yellow に変更した場合
{
changePatchs: [
{ op: "test", path: "/color", value: "yellow"},
{ op: "replace", path: "/color", value: "green"}
],
inversePatchs: [
{ op: "test", path: "/color", value: "green"},
{ op: "replace", path: "/color", value: "yellow"}
]
}
changePatchs （undoした時に行う操作）
-
test対象のpath/colorがyellowであるかを確認する- 他のメンバーによって別の色に変更されていた場合はundoできない
-
replace対象のpath/colorのみ、greenに置換する
inversePatchs （redoした時に行う操作）
-
test対象のpath/colorがgreenであるかを確認する- 他のメンバーによって別の色に変更されていた場合はredoできない
-
replace対象のpath/colorのみ、yellowに置換する
最終的な処理の概要
とうことで全体としてはこのような感じで実装を進めています
- 変更が入るごとにデータ差分を取得しのJSON-Patchを保持(ChangeSet)
- 保持データ（ChangeSet）の現在位置を保持(CurrentPosition)
- 履歴として追加するタイミングはアプリで制御
- 文字入力中は履歴として保持しないが、データを保存して反映。変更完了したら差分保持。
- Undoの時
-
ChangePatches[CurrentPosition]を適用する CurrentPosition--
-
- Redoの時
-
InversePatchs[CurrentPosition]を適用する CurrentPosition++
-
使用したライブラリ
（TypeScriptで処理する前提ですが）
最初は Immer を試していましたが、階層が深くなるとDiffがうまく取得できなかったり(v5では改善した模様)、今回のようにデータ前後でDiffをとる形にしたいケースでは対応しきれなかったので、JSON-Patch(fast-json-patch) を使用しています。
Patch作成の時もInversePatchで op:"test" がちゃんと入るので助かっています。
まとめ
- シングルユーザーではなくチームで共同編集を行うUndo/Redoはちょっと工夫が必要だよ
- データの差分をJSON-Patchとして、redo分まで保持していくやり方が良さそうだよ（参考文献に記載したページが非常に役に立ちました）
- ライブラリとしてはJSON-Patch(fast-json-patch) が用途に適していたのでそれを利用したよ
という感じで実装を進めていますが、まだまだデータの削除や追加などの対応を進まなければならず、Undo/Redoの実装は以外に大変だった ということがわかりました 
がんばっていきまっしょい！
補足
- Transactionかければとかそういうのはundo/redoとはまた異なるので、今回は割愛
- 今回の画像はWhimsicalで全て作成しています。便利ですね
