チームでの共同編集を行うアプリケーションのUndo/Redo

この記事は[Goodpatch Advent Calendar 2019](https://qiita.com/advent-calendar/2019/goodpatch) 4日目の記事です。

私は普段Ruby on RailsのREST APIのインフラ・バックエンド周りが多いですが、最近は、TypeScriptでフロントエンドとバックエンドをつなぐ部分なども担当しています。
今回は、まだ実装中ですが、 **チームでの共同編集が必要なアプリケーションのUndo/Redo** の設計と実装について簡単に紹介します。
（アプリケーションの内容はまだ詳しくかけないので、その辺は察してください :wink: ）

# 前提条件など

## Undo/Redoとは
まず一般的なUndo/Redoは以下のような解釈でほとんどのユーザーでズレがないと思います。

* Undo  
> コンピューターの用語で直前に **ユーザが** 行った **操作を取り消し** 、 **元に戻す** こと。データベースの専門用語ではロールバック。
[Undo - Wikipedia](https://ja.wikipedia.org/wiki/Undo)

* Redo  
> コンピューターの用語で直前に **ユーザが** 行った **操作を取り消したことを取り消し** 、 **元に戻す** こと。データベースの専門用語ではロールフォワード。
[Redo - Wikipedia](https://ja.wikipedia.org/wiki/Redo)

概ねこんな感じだと思います
![Undor-Redo-0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25926/25e06d4f-00f2-da9b-ef25-97de6fab41b6.png)
その上で、Undo/Redoに対するユーザーのメンタルモデルとしては、 **自分自身の変更を取り消す** つもりだと予測されるため、**他人の変更まで取り消すつもりはない** と考えられます。

## 「チームでの共同編集を行う」場合の特徴

シングルユーザーの場合と異なり、チーム内の複数のユーザーが、共同編集を行う場合はこんな感じになると考えられます。

![Undo-Redo-1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25926/82935318-ec22-e721-27f3-9098e6e03a0c.png)

* 色を変えたい人
* 太字にしたい人
* テキスト編集する人（まだ編集している最中だけどみんなに見せたい）

などなど
（ちなみに、今回はシームレスな共同編集のために、必要な時以外はロックをかけない方針としています :wink: ）

これを簡単に整理すると以下のようなことを実現する必要があります

* **みんなが同じモノを変えていく**
    * 例えば、１つのDBのレコード
* **みんなが違うトコロを変えていく**
    * 例えば、違うDBのカラムに対して
* **みんなが変えたらすぐに見える**
    * 例えば、議事録が途中で見える


## 共同編集のためのUndo/Redoとは

上記から、必要なUndo/Redoの条件を以下のように定義しました。

* **みんなが同じモノを変えていく**ので、
    * **ユーザー個人**が 行った操作**のみ**をUndo/Redoする
        * 他の人が行った操作は取り消さない
* **みんなが違うトコロを変えていく** ので
    * **ユーザー個人**が 行った操作によって変わった箇所 **のみ** をUndo/Redoする
        * 全部を元に戻すわけではない
* **みんなが変えたらすぐに見える** ようにしたいので、
    * **ユーザー個人**が 行った 操作による変更は随時反映させるが、 **履歴保持するタイミングを調整** する
        * ユーザーのundo/redoのメンタルモデルに従い、キリの良いところでをUndo/Redoの単位にする

# 実装していくためには :muscle: 

## 一般的なUndo/Redoの実装例

まずは一般的な実装例を確認してみました。

1. データの**状態**を履歴として保持して切り替える
2. データの**操作**を履歴として保持して切り替える

### 1. データの状態を履歴とする
* データの状態の履歴全てと、現在の位置を保持する(mementoデザインパターン的な)  
代表的なライブラリ： [GitHub - omnidan/redux-undo: higher order reducer to add undo/redo functionality to redux state containers](https://github.com/omnidan/redux-undo)

```typescript
{
 past: [{ text:"a", color: "yellow" }],
 present: [{ text:"b", color: "yellow" }],
 future: [{ text:"b", color: "green" }],
}
```

#### 共同編集時の問題点
* 以下の図のように自分の変更以外の状態も元に戻ってしまう

![Undo-redo-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25926/64536048-e8d3-6b25-de41-1dafbce9cd28.png)

### 2. データの操作を履歴とする
* データの操作の履歴全てと、現在の位置を保持する(commandデザインパターン的な)

```typescript
{
 commands: [
   create({ text:"a", color: "yellow" }),
   update({ text:"b" }),
   update({ color:"green" }),
 ]
}
```

* DBのREDOログとかはまさに、ほぼ、これだと思う。
* 戻す時に最初からコマンドを全て実行する必要があるので、時間がかかる


## 選択したUndo/Redoの方法

悩んだ挙句、 [こちらの記事](https://nils-mehlhorn.de/posts/angular-undo-redo-ngrx-redux) に書いてある方法がとても良さそうだったので、採用！ :tada:

* そのユーザーの**データの状態**から変更差分のみを抽出して、**操作**履歴として保持
    * 変更差分を戻す操作(Undo)をJSON-Patchとして保持(ChangePatch)
    * 変更差分を戻す操作の取り消しのための操作(Redo)もJSON-Patchとして保持(InversePatch)

![Undo-Redo-3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25926/d3c14d27-9588-783c-9411-b4cb2d592971.png)
これで共同編集でも問題なくUndo/Redoできそうです

## JSON-Patchについて

JSON-Patchは
>  JSON （ JavaScript Object Notation ）文書に適用する 一連の演算を表出するための JSON 文書構造を定義する

というものなので、JavaScriptのObjectに対してもほとんど適用可能だと思います。
詳しくは以下のリンクに記載されています。
[RFC 6902 - JavaScript Object Notation (JSON) Patch （日本語訳）](https://triple-underscore.github.io/RFC6902-ja.html)

### 保持するデータ
`/color` を `green` > `yellow` に変更した場合

```typescript
{
  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` に置換する

## 最終的な処理の概要
とうことで全体としてはこのような感じで実装を進めています :muscle: 

![Undo-Redo-4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25926/75249697-99be-fb11-bcdc-eec2de9ff04a.png)

* 変更が入るごとにデータ差分を取得しのJSON-Patchを保持(ChangeSet)
* 保持データ（ChangeSet）の現在位置を保持(CurrentPosition)
* 履歴として追加するタイミングはアプリで制御
    * 文字入力中は履歴として保持しないが、データを保存して反映。変更完了したら差分保持。
* Undoの時
    * `ChangePatches[CurrentPosition]`を適用する
    * `CurrentPosition--`
* Redoの時
    * `InversePatchs[CurrentPosition]`を適用する
    * `CurrentPosition++`

### 使用したライブラリ

（TypeScriptで処理する前提ですが）
最初は [Immer](https://github.com/immerjs/immer) を試していましたが、階層が深くなるとDiffがうまく取得できなかったり(v5では改善した模様)、今回のようにデータ前後でDiffをとる形にしたいケースでは対応しきれなかったので、[JSON-Patch(fast-json-patch)](https://github.com/Starcounter-Jack/JSON-Patch) を使用しています。
Patch作成の時もInversePatchで `op:"test"` がちゃんと入るので助かっています。

## まとめ

* シングルユーザーではなくチームで共同編集を行うUndo/Redoはちょっと工夫が必要だよ
* データの差分をJSON-Patchとして、redo分まで保持していくやり方が良さそうだよ（参考文献に記載したページが非常に役に立ちました）
* ライブラリとしては[JSON-Patch(fast-json-patch)](https://github.com/Starcounter-Jack/JSON-Patch) が用途に適していたのでそれを利用したよ

という感じで実装を進めていますが、まだまだデータの削除や追加などの対応を進まなければならず、**Undo/Redoの実装は以外に大変だった** ということがわかりました :hugging: 
がんばっていきまっしょい！

### 補足
* Transactionかければとかそういうのはundo/redoとはまた異なるので、今回は割愛
* 今回の画像はWhimsicalで全て作成しています。便利ですね :thumbsup:

## FYI: 参考文献
* [Implementing Undo-Redo with NgRx or Redux | Lessons Unlearned](https://nils-mehlhorn.de/posts/angular-undo-redo-ngrx-redux)
    * これにほとんど書いてあります！
* [Multilevel Undo and Redo Implementation in C# - Part II (Using  Command Pattern) - CodeProject](https://www.codeproject.com/Articles/33384/Multilevel-Undo-and-Redo-Implementation-in-Cshar-2)
    * ↑の記事の元はこれ
* [(PDF)3Dビジュアルシミュレーションにおける効率的なundo/redoのアルゴリズムとデータ構造について](https://pdfs.semanticscholar.org/d852/0390acea51f8f457f4106e16abc7af42b288.pdf)
    * 初期段階の考察にあたり大変参考になりました。