この記事は、東京大学工学部電子情報工学科/電気電子工学科の後期実験「大規模ソフトウェアを手探る」のレポートとして作成されました。

Undo/Redo の履歴が消える悲しみ

編集系のソフトウェアで誰もがお世話になっているであろう Undo/Redo 機能ですが、このような悲しみに襲われたことはないでしょうか？

「以前の状態に戻したいのに、履歴が消えて戻せない〜〜〜」

講義室でアンケートを取ったところ、8 割以上の方がこの悲しみを経験されていたようです。
といっても、ピンとこない方がいると思うので、具体的にどういう問題があるのか説明していきます。

テキストエディタを例にとります。まず、操作 A, B, C を行います。ここでいう「操作」は、文字列の入力や Back space など、Undo/Redo 以外でエディタの編集状態を変えるものを指します。

続いて Undo を行います。

続いて操作 D を行います。

ほとんどのソフトウェアでは、この状態から Undo/Redo のみで ABC の状態に戻ることはできません。編集履歴が一次元的に管理されているためです。より詳細には、この状態から Redo を行っても何も起こらず、Undo を実行していくと

と遷移し、これ以上 Undo できなくなります。この間に ABC の状態は現れません。

私たちは、この「履歴が上書きされて消えてしまう」という問題を解決するべく、オープンソースプロジェクトである vscode を相手に Undo/Redo の機能改変を行うことにしました。

vscode: Undo/Redo がどう実現されているのか

戦いに勝つには、まずは敵を知ることから始めましょうということで、私たちはこの機能が現状どのように実現されているかを手探っていきました。

vscode を build して Undo/Redo に関係ありそうなところがないか見てみたところ、すぐに見つかりました。ここから先は、vscode/src/vs/platform/undoRedo/undoRedoService.ts を調べた結果、明らかになった現時点での Undo/Redo の実装方法をお伝えしていきます。

現状の Undo/Redo を説明する上で、大切なキーワードは「操作ベースでの管理」と「2 つのスタック」です。
以下の図をご覧ください。

vscode は操作を past と future という 2 つのスタックに適切に割り振ることで Undo/Redo を実現しています。
例えば、先程と同じように、操作 A, B, C を行いましょう。これらの操作はすべて past スタックに入ります。
ここで一度 Undo をして、操作 C を取り消してみましょう。

すると、上の図のように、操作 C が future スタックに移ります。同時に、操作 C の逆の操作 (以下、逆操作) を現在の編集状態に適用します。
例えば、「あ」と打ち込んで画面出現させる操作の逆操作は、「あ」を画面から削除する操作になります。逆に、「あ」を画面から削除する操作の逆操作は、「あ」を画面に出現させる操作にあたります。

続いて Redo を行うと、操作 C が今度は past スタックから future スタックに移り、操作 C が現在の編集状態に適用され、Undo する前の編集状態に戻るというわけです。

では、Redo する代わりに操作 D を行うと、どうなるかというと……

現状の実装では、future スタックをこの時点で空にしています。
あなたの大事な編集履歴は、永遠に失われてしまったのです。

以上の実装をコードレベルで追ってみます。

2 つのスタックは、_past, _future として ResourceEditStack クラスでまとめて管理されています。

class ResourceEditStack {
	...
	private _past: StackElement[];
	private _future: StackElement[];
	...
}

StackElementが操作にあたり、動的配列をスタックとして用いていることがわかります。なお、StackElement は ResourceStackElement と WorkspaceStackElement の Union 型であり、前者は現在開いているファイルに対しての操作、後者は開いているワークスペースに対しての操作を表します。以下では前者の場合に焦点を当てます。

Undo/Redo 周りの総合的な管理を行うのが UndoRedoService クラスです。例えば Undo を行うと _resourceUndo メソッドが呼び出されます。

export class UndoRedoService implements IUndoRedoService {
	...
	private _resourceUndo(editStack: ResourceEditStack, element: ResourceStackElement, undoConfirmed: boolean): Promise<void> | void {
		...
		return this._invokeResourcePrepare(element, (cleanup) => {
			editStack.moveBackward(element);
			return this._safeInvokeWithLocks(element, () => element.actual.undo(), new EditStackSnapshot([editStack]), cleanup, () => this._continueUndoInGroup(element.groupId, undoConfirmed));
		});
	}
}

何やら複雑な入れ子の形になっていますが、要するにスタックに加える変更 (editStack.moveBackward(element)) と現在の編集状態に加える変更 (element.actual.undo()) を定めています。Redo についても _resourceRedo が同じように定義されています。

スタックに関するメソッドは、新たに操作を行ったときに呼ばれる pushElement と合わせて以下のように定義されています。

class ResourceEditStack {
	...
	public pushElement(element: StackElement): void {
		...
		this._future = [];
		this._past.push(element);
		this.versionId++;
	}
	...
	public moveBackward(element: StackElement): void {
		this._past.pop();
		this._future.push(element);
		this.versionId++;
	}

	public moveForward(element: StackElement): void {
		this._future.pop();
		this._past.push(element);
		this.versionId++;
	}
}

まさしく上で解説したような処理が行われていることがわかります。

機能を改変しよう！

私たちは、この future スタックの初期化のようなことをせずに、ある編集点から分岐するように履歴を残せないかと考えました。こうすると、編集履歴は一次元的なものではなく、編集状態を頂点、操作を辺とする木構造になるはずです。

このような議論が行われている issue で、現在 open されているものを調べたところ、見つかりました。これです。

こちらの issue では、分岐点で木をユーザーに表示し、どの道に進むか選んでもらうようにしてはどうか、といった方針の UI が多く提案されていました。

とても参考になったのですが、結論から言うと、私たちは木をグラフィカルに表示することなく、木について定められるオイラーツアーをベースにした UI を実装しました。

メリットとしては、

既存の実装をうまく使える
[Ctrl+Z],[Ctrl+Y]のふたつのコマンドだけで編集履歴の行き来ができる

ことが挙げられます。

[Ctrl+Y] は Redo のショートカットですが、OS によっては [Ctrl+Shift+Z] で行っている方もいらっしゃるかもしれません。本記事では Redo ショートカットは [Ctrl+Y] で表記します。

オイラーツアーに関しては、この記事がわかりやすくまとまっています。

オイラーツアーの順で編集履歴の木をたどることが出来れば、今まで編集画面に現れた全ての状態に立ち返ることができます。

なお、issue では拡張機能としての実現可能性について言及されていますが、現状の API では困難だと私たちは考えています。API の追加を視野に入れるとしても、その設計にあたってまずは現状の実装と必要な変更箇所を把握しなくてはなりません。したがって、今回は vscode を直接編集する方法をとりました。

編集履歴をオイラーツアーでたどる。

実は、木を陽に保持することなく、1 つのデックを用いることで所望の処理が行えます。具体的には、現在いる位置を開始点とする、辺ベースのオイラーツアーをデックに持っておきます。

例えば、以下のような編集履歴の木があるとします。現在いるのは星印の位置です。辺に対応する操作を行うことにより、頂点間の移動ができます。
保持しているデックは、反時計回りのオイラーツアーになっています。ここで、下線付きX は操作 X の逆操作を表します。

まず、初期状態から、新たに操作 F を行った場合を見てみましょう。

上の図のように新たな葉が生じ、デックでは両端に操作 F とその逆操作を入れてあげれば良さそうです。

初期状態から [Ctrl+Z] をするとこうなります。

オイラーツアー上では時計回りに動き、操作 B が編集状態に適用されます。デックについては、左から右に B の逆操作をもってきてあげればよいとわかります。

それでは逆に初期状態から [Ctrl+Y] をするとどうなるでしょうか。

オイラーツアー上では反時計回りに動き、操作 C が編集状態に適用されます。デックについては、今度は右から左に操作をもってきてあげればよいですね。

ここで注意したいのは、デック上で移動させる操作と編集状態に適用する操作の関係についてです。[Ctrl+Z]のときは、操作 B の逆操作を移動させて操作 B を適用しているのに対し、[Ctrl+Y]のときは操作 C を移動させて操作 C を適用しています。このように、[Ctrl+Z]のときは移動させる操作の逆操作を、[Ctrl+Y]のときは移動させる操作そのものを適用すれば良いです。
このとき、「逆操作の逆操作」というものが出てくることがありますが、これは元の操作そのものになります。

私たちは、StackElementに逆操作か否かを表すメンバ変数 inverese: boolean を持たせておき、Undo が呼ばれた際に、この変数をチェックして、true 、つまり逆操作であれば、内部的には Redo を実行させることにしました。
Redo が呼び出されたときにも同様に、対象の操作が逆操作であれば、内部的には Undo を実行します。

先に示した部分は、次のように変更されます。

class ResourceEditStack {
	...
	private _history: Deque<StackElement>;
	...
	public pushElement(element: StackElement): void {
		this._history.pushFront(element);
		this._history.pushBack(element.getInverse());
		this.versionId++;
	}
	...
	public moveBackward(element: StackElement): void {
		this._history.popFront();
		this._history.pushBack(element);
		this.versionId++;
	}

	public moveForward(element: StackElement): void {
		this._history.popBack();
		this._history.pushFront(element);
		this.versionId++;
	}
}

export class UndoRedoService implements IUndoRedoService {
	...
	private _resourceUndo(editStack: ResourceEditStack, element: ResourceStackElement, undoConfirmed: boolean): Promise<void> | void {
		...
		return this._invokeResourcePrepare(element, (cleanup) => {
			editStack.moveBackward(element);
			return this._safeInvokeWithLocks(element, () => {
				if (!element.inverse) {
					element.actual.undo();
				} else {
					element.actual.redo();
				}
			}, new EditStackSnapshot([editStack]), cleanup, () => this._continueUndoInGroup(element.groupId, undoConfirmed));
		});

	}
}

Deque の実装

vscode は TypeScript で書かれているのですが、残念ながらデックは搭載されていないので、このスライドを参考に、スタック 2 つを使って実装することにしました。
詳しくは上のスライドを参考にしていただければよいのですが、直感的理解には以下の図が役立つかもしれません。片方向からしか出し入れできないスタックを背中合わせにくっつけると、デックと同じような振る舞いを実現できそうです。

なお、上記の方法でクエリあたり定数時間で抑えられるのは償却計算量であり、一回のクエリで編集履歴のサイズについて線形な計算時間がかかってしまうことはありえます。しかし、もともとスタックが動的配列を用いて表現されており、動的配列の要素追加も同じく最悪計算量は線形であることから、設計思想的にそのことは問題ないと考えました。

デモ

実際の編集の様子と、[Ctrl+Z]や[Ctrl+Y]による状態遷移のデモです。

画面左半分がメインです。画面右半分はいま行っていることを示す注釈であり、詳しい説明は以下です。

preparation: 文字入力と[Ctrl+Y]によって木を形成しています。ここで形成される木は、解説で示した初期状態の木と同じ構造になっています。
Ctrl+Z: [Ctrl+Z]によって木の回りをオイラーツアーに沿って時計回りに一周しています。
Ctrl+Y: [Ctrl+Y]によって木の回りをオイラーツアーに沿って反時計回りに一周しています。

具体的な変更とビルド

班員の使用 OS は Ubuntu20.04, Ubuntu18.04, MacOS(M1) です。

VSCode(OSS)の入手

公式のGitHubから落としてきます。

大規模ソフトウェア課題においては、GitLab を使用します。GitLab 上でプロジェクトを作成した後、以下のコマンドで vscode リポジトリの main ブランチを自分たちのプロジェクトに持ってくることができました。

git clone https://github.com/microsoft/vscode.git
cd vscode
git remote rename origin upstream
git remote add origin git@doss-gitlab.eidos.ic.i.u-tokyo.ac.jp:suigyoza/vscode.git
git push -u origin main

ビルドができるようになるまで

基本は公式が書いてくれている手順書に従うだけですが、詰まった点について述べます。

yarn するまで

Ubuntu の 20.04 未満において、
On Debian-based Linux: sudo apt-get install build-essential g++ libx11-dev libxkbfile-dev libsecret-1-dev python-is-python3 を実行した際に、 python-is-python3 がない的なお叱りを受ける。→python-is-python3 を消去して実行する

python-is-python3 は Ubuntu20.04 以降で、Python2, 3 の衝突を避けるために実装された機能らしく (?)、それ以前の人は無視していい。（というかつけるとエラーが起きる）
参考: https://askubuntu.com/questions/1296790/python-is-python3-package-in-ubuntu-20-04-what-is-it-and-what-does-it-actually

yarn して以降

node.js のバージョンが node v14-17 でないとビルドエラーになる。(2021/10/11 時点) → node.js のバージョン変える。
./scripts/code.sh でビルドした VSCode を起動する際に、crbug:638180 が発生
→VSCode 内のターミナルから起動することはできない模様。普通のターミナルから実行するべし。

yarn を一度したら、以降は yarn watch でやるのが楽。(変更後いちいち yarn しなくても、自動で差分ビルドしてくれるので楽だし早い)

同実験を履修されていた先輩の進捗記録
の 10/13 あたりが参考になる。

なお、yarn watch にて、「file を watch できません」とエラーが出る場合は、watch する file 数の上限を開放すると解決する。

参考:
https://code.visualstudio.com/docs/setup/linux#_visual-studio-code-is-unable-to-watch-for-file-changes-in-this-large-workspace-error-enospc

デバッグができるようになるまで

VSCode の拡張機能 the Debugger for Chrome extension で行いました。

デバッグのやり方の説明がちょっと雑なので詳しく書くと、

the Debugger for Chrome extensionをインストール
vscode ディレクトリ直下で code . とする
TS ファイル内に適宜ブレイクポイントを設定
実行とデバッグを押し、「Launch VS Code」を選択し、実行 (F5)
新たに開いた VSCode 側で Ctrl+Shift+P をおして、Toggle Developer Tools を入力し開発者ツールを開く
デバッグ開始！

ブレイクポイントは、VSCode のコードを編集している VSCode において、ブレイクポイントを作るだけで大丈夫です。

今後の課題

ファイルの作成やファイル名の変更など workspace に関する Undo/Redo(WorkspaceStackElementで定義される)については、扱いませんでした。
Snapshot,groupID に関する動作を把握しきれませんでした。
Notebook を使うと動作が不安定になることがあります。

感想

今回、私がかねてより実装してみたいと思っていた Undo/Redo の代わりとなるオイラーツアーによる状態遷移を、後期実験にかこつけて班員の力を借りて実現できたことを嬉しく思います。VSCode にはまだまだわからない部分が多いですが、今後も趣味として理解を深めていきたいです。 (@packer_jp)
今回、大規模ソフトウェアの実験は、個人的に終始楽しく取り組むことができました。
特に、個性豊かなメンバーとともに、それぞれの長所を活かして一つの成果物を作るのが個人的にはいい経験になりました。
はじめは TypeScript なんもわからん状態でしたが、探ることで少し VSCode のことを理解できた気がしています。OSSって「いつも使ってるあの動きはこんな実装してるのかー」ってわかって面白いですね。
ただ、内容を理解するのは割と大変だったので、今後自分が大きなソフトを作ったり、いじったりする際には可読性と編集のしやすさと丁寧なコメントをつけるのを意識したいなと思いました。(@kakekakemiya)
今回、初めて個人としてオープンソースプロジェクトに関わる機会となりました。まず、このOSSの世界に最初の一歩を踏み入れることができたこと、それ自体が貴重な経験になったように感じます。
VSCode の内部を手探っていき、普段使っているエディタの秘密が段々と見えてくる過程には、謎解きのような面白さもあり、大学の授業で、こんなにも毎回胸を躍らせたことはありませんでした（╹◡╹）
大きなソフトウェアへ立ち向かう方法を習得したいあなたは、本実験「大規模ソフトウェアを手探る」を取ることを強くお勧めします！！！
(@casa_recce)

【VSCode】Undo/Redoに革命を起こしたい