JSのProxyを使ってアルゴリズムの実行中の各ステップを可視化する仕組みを作る記事です。
（inspired by アルゴリズム図鑑）
初めに完成品のキャプチャとデモのリンクを貼っておきます。
DEMO: https://codesandbox.io/s/heuristic-morse-1kc2d?file=/src/index.js
※ スマホだとシンタックスハイライトでエラーが出てるのでコード記載無し版も置いておきます。
https://codesandbox.io/s/happy-sun-211bq?file=/src/index.js
JavaScriptのProxyとは
Proxy - JavaScript | MDN
最初にJSのProxyとは何か簡単に説明すると、
特定の操作に対するオブジェクトの振る舞いを拡張/変更できるオブジェクトです。
拡張されるオブジェクト（ターゲット）と、操作を受けた時の挙動を定義するオブジェクト（ハンドラ）をコンストラクタに渡すことで生成できます。
const proxy = new Proxy(target, handler);
振る舞いを変更できる操作の種類は
- プロパティ値の読み出し/書き込み/削除
- 関数オブジェクトに対する関数呼び出しやnew付きの呼び出し
- その他（プロパティやプロトタイプに関する様々な操作）
などがあります。
ハンドラに各操作に対応するトラップという関数を持たせることで挙動を定義できます。定義できるトラップの一覧はこちら。
Proxy handler - JavaScript | MDN
以下はプロパティ値の書き込み操作に対応するsetトラップを定義する例。
代入された値を10倍にしてターゲットに設定しています。
const t = {};
const p = new Proxy(t, {
set(target, property, value, receiver) {
target[property] = value * 10;
return true; // 値の設定に成功した場合はtrueを返す
}
});
p.n = 5;
console.log(t.n); // 50
setトラップの引数はターゲット、設定するプロパティの名前、設定するプロパティの新しい値、操作を受けたオブジェクト（プロキシ自身、またはプロキシを継承しているオブジェクト）です。
receiverについてはReflectと併用するのが主な用途なのかなと思います。
参考: JavaScript（ES2015〜）のProxyで、プロパティにフックする正しいやり方
プログラムの流れ
それではコードを見ていきます。
視覚化したいデータを初期化関数に渡す
今回は以下の内容の挿入ソートを視覚化します。
（ちなみにアルゴリズムはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造を参考に実装しています）
const a = [5, 2, 4, 6, 1, 3];
insertionSort(a);
function insertionSort(a) {
const n = a.length;
for (let i = 1; i < n; i++) {
const v = a[i];
let j = i-1;
while (j >= 0 && a[j] > v) {
a[j+1] = a[j];
j--;
}
a[j+1] = v;
}
}
視覚化する値としては操作対象の配列a、ループ変数のi, j、一時変数のvにします。
それらを初期化関数に渡すことでプロキシに置き換えて値の変更を捕捉可能にします。
ただし、プロキシはオブジェクトに対する操作しか捕捉できないため、ローカル変数i, j, vに関してはローカル変数保持用のオブジェクト$のプロパティとして実装します。
// 初期化関数に{変数名: 値}の形で渡すことでプロキシが返される
const { a, $ } = initVisualization({
a: [5, 2, 4, 6, 1, 3],
$: { i: null, j: null, v: null } // {}でもいいけど分かりやすいようにnullで初期化
});
...
// アルゴリズム実装側もローカル変数の代わりに$を使うよう書き換え
function insertionSort(a) {
const n = a.length;
for ($.i = 1; $.i < n; $.i++) {
$.v = a[$.i];
$.j = $.i - 1;
while ($.j >= 0 && a[$.j] > $.v) {
a[$.j + 1] = a[$.j];
$.j--;
}
a[$.j + 1] = $.v;
}
}
できればアルゴリズム実装側には手を入れずに実現したかったけど、止むを得ません…。
初期化関数で渡されたデータのプロキシを生成
受け取った観測対象のデータ（aと$）それぞれに対して、プロパティ値が設定された時に全てのデータのスナップショットを取るようsetトラップを定義します。
import { takeSnapshot } from "./snapshot";
export function initVisualization(targets) {
const proxies = {};
Object.entries(targets).forEach(([key, target]) => {
proxies[key] = new Proxy(target, {
set(t, p, v) {
t[p] = v;
takeSnapshot(targets);
return true;
}
});
});
takeSnapshot(targets);
return proxies;
}
スナップショットの実装
const snapshots = [];
export function takeSnapshot(variables) {
const snapshot = {};
for (const k in variables) {
snapshot[k] = deepCopy(variables[k]);
}
snapshots.push(snapshot);
}
返されたプロキシを使ってアルゴリズムの処理を実行し、UI描画
あとは返されたプロキシを使ってアルゴリズムを実行するだけです。代入やインクリメントのタイミングでスナップショットが取られます。
完了してからViewを描画します。
insertionSort(a);
render();
この時点でのデモはこちらです。
代入操作にアニメーションを付ける
ここまでで値の可視化はできました。
ここからさらに、変数間での値の受け渡しが分かりやすいように代入元から代入先に要素が移動するアニメーションを付けてみます。
そのためには渡された値はどの変数に入っていたかという情報が要りますが、setトラップには値そのものしか渡ってきません。
そこで、ちょっとhackyですが初期化関数を以下のように書き換えてみました。
export function initVisualization(targets) {
const proxies = {};
const name = Symbol("variable name"); // 変数名を保持するためのシンボル
const from = Symbol("assign from"); // 代入元を保持するためのシンボル
Object.entries(targets).forEach(([key, target]) => {
target[name] = key; // 変数名を持たせる
proxies[key] = new Proxy(target, {
get(t, p) {
if (t[name] === "a" || p === "v")
return {
valueOf: () => t[p],
[from]: t[name] === "$" ? p : `${t[name]}.${p}` // 代入元情報
};
else return t[p];
},
set(t, p, v) {
if (v[from]) { // fromを持っていれば代入されたと判定
t[p] = v.valueOf();
takeSnapshot(targets, {
assign: {
from: v[from],
to: t[name] === "$" ? p : `${t[name]}.${p}` // 代入先情報
}
});
} else {
t[p] = v;
takeSnapshot(targets);
}
return true;
}
});
});
...
}
まずプロキシ生成時にターゲットに自身の名前を持たせておきます。
getトラップを使用してアニメーション対象である配列aの要素か変数vが参照された場合には値をオブジェクトでラップして、どの変数の値を読み出したかを示すfromプロパティを添えて返します。この時、元の値をvalueOfの戻り値とすることで比較演算など数値としての振る舞いが期待される文脈では元の値が自動的に返されます。
setトラップでは渡された値がfromプロパティを持っていれば別変数からの代入と判断して、自身の名前を代入先toとしてfromと合わせてtakeSnapshotの第２引数に渡します。
これで値と共に操作もスナップショットに記録されます。
export function takeSnapshot(variables, operation) {
const snapshot = {};
for (const k in variables) {
snapshot[k] = deepCopy(variables[k]);
}
snapshot[Symbol.for("operation")] = operation; // シンボルキーで操作内容を保存
snapshots.push(snapshot);
}
後はその情報を元にアニメーションを組み立てます。
export function getAnimation(operation) {
if (!operation || !operation.assign) return null;
const { from, to } = operation.assign;
const fromSelector = `[data-variable-name="${from}"]`;
const toSelector = `[data-variable-name="${to}"]`;
const fromRect = document.querySelector(fromSelector).getBoundingClientRect();
const toRect = document.querySelector(toSelector).getBoundingClientRect();
const startX = fromRect.left - toRect.left;
const startY = fromRect.bottom - toRect.bottom;
return `
${toSelector} {
animation: assign .3s;
}
@keyframes assign {
0% {
transform: translate(${startX}px, ${startY}px);
}
}
`;
}
今回はやりませんが、比較演算など代入以外の操作も_.gtのように関数でラップしたスタイルで実装し、applyトラップと組み合わせることで操作の記録ができると思います。
View側（React）は省略しますが、ソース全体はCodeSandboxかGithubからご覧いただけます。
おわり
プロキシによるロギングと、それを利用したアルゴリズムの可視化の試みでした。
プロキシにはログを取る以外にもバリデーションや値の加工、変更の通知など様々な活用方法があるので以下の記事も参考になると思います。