概要

Ace Editor を Operational Transformaton アルゴリズムでリアルタイム編集可能にするための npm ライブラリです

縛りについて

今回は「NAGO」から始まるライブラリ縛りに応じて、

• Node.js：npm ライブラリとして実装
• Ace Editor：テキストエディタのベースとして採用
• Gulp：js の Minify に使用。余興。
• Operational Transformation：競合解決アルゴリズム。自前で実装

の４つの技術を使用しました。 余談ですが、Node.js を除く下の3つは、ここ5年の環境環境では完全に上位互換の概念が存在するみたいでした。かわいそう。

Operational Transformation とは

リアルタイムに同じドキュメントを編集する際、同じタイミングで更新をかけると後者の変更のみが反映されます（＝変更の競合）。 これを解決するのが Operational Transformation（以下 OT）で、後者の変更を前者の変更にとって無害なものに変換することで解決しています。

OT をサービスする npm ライブラリとしてはかつて ot.js が存在していましたが、4年前の更新を最後に deprecated となっていました そのため、今回はこれを実装し（ようとしてい）ました

変換ロジック

詳しくは実装（AceAdapter#transform）を見てください。コメントで解説してます

前提として、クライアントは Delta という変更の差分を送り合って互いの変更を通知します。今回の実装では Ace Editor 内部の AceAjax.Delta インタフェースをそのまま採用しています

interface Delta {
    action: "insert" | "remove";
    end: Ace.Point;  // {row: number, column: number}
    lines: string[];
    start: Ace.Point;   // {row: number, column: number}
}

見ての通り、挿入（insert）または削除（remove）のパターンがあります 実際の通信では、これに差分のバージョン番号を示す revision を含めて送信します。各差分をバージョン付で管理することで、同じバージョンの差分＝競合する差分　として扱うことができます。

差分の変換処理について

insert / remove の総当たりとなる 4 通りに分け、そこから二つの変更の位置関係でパターン分けしています。

例として insert / remove を挙げます。 挿入処理は開始位置を基準とした点に対する処理と考え、削除処理は開始位置から終了位置までを取り除く範囲に対する処理と考えます これを数学の不等式の要領でパターン分けすると

• 点 < 範囲の開始地点
• 点 = 範囲の開始地点
• 点 > 範囲の開始地点 && 点 < 範囲の終了地点
• 点 = 範囲の終了地点
• 点 > 範囲の終了地点

みたいな感じで場合分けできるので、それぞれに対して適切な処理を実装しています （実際は複数の行を含む文字列の配列について考えなければいけないので、ここまで単純じゃないかも）

使用技術メモ

Node.js

言わずもがな、サーバーサイドJSの実行環境です。今考えたら N の枠は「npm」にして bun でライブラリ書けばよかった。

Ace Editor

本当は Quill を使いたかったですが、制約によって泣く泣くこれになりました。textChangeイベントにsilentオプションがなかったりDeltaが扱いづらかったりと散々。

Gulp

現在は Vite に取って代わられたタスクランナーです。ホットリロードの実現から複雑なタスクプロセスの実装まで、プラグインの手の届く範囲でいろいろできるみたい。

Operational Transformation

これはアルゴリズムですが、上位互換となる CDRT が登場してからはほとんど使われていません。（現にライブラリが deprecated になってた） 実際に実装する場合は、特別な事情がない限り CDRT を採用することをお勧めします（Yjs など）