Lispコードを書くと抽象構文木を表示してくれるWebアプリをReactで作った(正確には計算グラフとかProgram Dependence Graphというべき)。
github.com
season1618.github.io
ReactもTypeScriptもまともに使ったことがないのでもっと良い書き方があるかもしれない。
構成
画面の左半分にエディタを置いて、右半分にCanvasを置いた。useContext
で構文木を共有して、コードが変更されたときに右のViewも変更されるようにする。
function App() {
const [node, setNode] = useState<Node | undefined>(initNode);
return (
<div id="app">
<nav><h2>Lisp Syntax Viewer</h2></nav>
<div id="flex">
<NodeContext.Provider value={[node, setNode]}>
<CodeEditor /><Canvas />
</NodeContext.Provider>
</div>
</div>
);
}
構文木を保持する変数node
と更新関数であるsetNode
の両方を共有することになる。setNode
の型はエディタではReact.Dispatch<React.SetStateAction<Node | undefined>>
と表示されているが、createContext
で生成するときの型注釈は単に(node: Node | undefined) => void
で良いらしい(よく分からない)。
const initNode: Node | undefined = undefined;
export const NodeContext = createContext<[Node | undefined, (node: Node | undefined) => void]>([initNode, (node: Node | undefined) => {}])
コードエディタ
スタイル
<textarea>
でやる。
white-space: nowrap;
で横スクロールが可能。
textarea:focus { outline: 0; }
でフォーカスが当たったときに輪郭が強調されるのをoffにする。
textarea::selection
でテキストが選択されたときのスタイルを制御。
補完
基本的にはテキストが変更されたらそのまま反映すれば良い。デフォルトではTabキーでフォーカスが移ってしまうので、e.preventDefault()
でフォーカスが移るのを防ぐ。
return (
<div id="editor">
<textarea
value={code}
onChange={
(e) => {
format(e.target.selectionStart, e.target.value);
}
}
onKeyDown={
(e) => {
if (e.key === 'Tab') {
e.preventDefault();
const target = e.target as HTMLTextAreaElement;
formatTab(target.selectionStart);
}
}
}
/>
</div>
);
カーソルの位置はHTMLTextAreaElement
からセットする。
let target: HTMLTextAreaElement;
useEffect(
() => {
target = document.querySelector('textarea') as HTMLTextAreaElement;
}
);
useEffect(
() => {
target.focus();
target.setSelectionRange(cursorPos, cursorPos);
},
[cursorPos]
);
その他、開き括弧が入力されたら閉じ括弧を補完する、引用符が入力されたらもう一個加えるなどの処理を行う。
function format(pos: number, nextCode: string) {
pos -= 1;
if (code.length < nextCode.length) {
switch (nextCode[pos]) {
case '(':
nextCode = nextCode.substring(0, pos + 1) + ')' + nextCode.substring(pos + 1, nextCode.length);
break;
case ')':
if (pos + 1 < nextCode.length && nextCode[pos + 1] === ')') nextCode = code;
break;
case '\'':
if (pos + 1 < nextCode.length && nextCode[pos + 1] === '\'') nextCode = code;
else nextCode = nextCode.substring(0, pos + 1) + '\'' + nextCode.substring(pos + 1, nextCode.length);
break;
}
}
setCode(nextCode);
setCursorPos(pos + 1);
}
TypeScriptにはunion型があるが、タグ無しなのでパターンマッチがなくkind
メンバで場合分けして処理した。Call
は関数適用、Prim
は定数やシンボルなどのprimaryノード、Var
は変数で式を保持する。
export type Ast = Expr;
export type Expr = Call | Prim | Var;
基本的には通常の構文解析と同じだが、構文木を描画する関係で必要なデータを予め求めておく。この手のアプリケーションはレイアウトのアルゴリズムを考えるのと実装するのが一番大変。
depth
は構文木の深さで、Canvas上でのノードのy
座標を保持する。offset
はx
座標を保持する。depth
は深さ優先探索で根から順番に求めていける。ただし変数は複数参照されるので最大値を取る。offset
はdepth
が決定した後にまとめて計算する。OffsetTableを用意しておき、depth
ごとに現在使われているものの最大値 + 1とそれぞれのノードに最適な位置(Call
なら引数のoffsetの平均)のうち、大きい方を採用する。
calcOffset(depth: number, offset: number = -1): number {
if (!(depth in this.table)) {
this.table[depth] = new Set();
}
let maxOffset = Math.max(-1, ...this.table[depth]);
let finOffset = Math.max(maxOffset + 1, offset);
this.table[depth].add(finOffset);
return finOffset;
}
ASTビュアー
構文木の描画(2024/2/24追記)
変数は複数のノードから参照されるので木構造ではないが、自分より深さが1小さいノードの一つを親として考える。構文木の描画はそのような木の描画として行う。木の描画はReingold-Tilfordアルゴリズムを用いる。
まずASTから描画するための座標などを保持するデータ構造に変換する。
class Node {
label: string;
shift: number;
offset: number;
depth: number;
childs: Node[];
belows: Node[];
thread: Node | null;
visited: boolean;
havePar: boolean;
...
}
ノードの深さは根からの最長距離になる。無駄な計算を省くためトポロジカル順序で更新する。
calcDepth() {
const torder = this.tsortReverse().reverse();
for (const node of torder) {
for (const child of node.childs) {
child.depth = Math.max(child.depth, node.depth + 1);
}
}
}
再帰的な処理を行うため、childs
とは別に木構造としての子要素の配列belows
を求めておく。つまりbelows
を辿って再帰すると木上をDFSできる。条件は深さが自ノードより1大きいかつ親が決まっていないこと。
calcBelows() {
for (const node of this.childs) {
if (this.depth + 1 === node.depth && !node.havePar) {
this.belows.push(node);
node.havePar = true;
node.calcBelows();
}
}
}
calcOffset
で最左兄弟ノードに対する相対座標を決定し、calcAbsolute
で絶対座標を算出する(offsetを使いまわす)。
最後に描画を行う。childs
を辿って辺を描画し、belows
を辿って再帰。
function draw(node: Node, originX: number, originY: number) {
let x = originX + width * node.offset;
let y = originY + height * node.depth;
drawNode(x, y, node.label);
node.childs.forEach((child, index) => {
let x1 = x + (index + 1) / (node.childs.length + 1) * 2 * r - r;
let y1 = y + r;
let x2 = originX + width * child.offset;
let y2 = originY + height * child.depth - r;
drawArrow(x1, y1, x2, y2);
});
node.belows.forEach((below) => {
draw(below, originX, originY);
});
}
有向辺は3次ベジェ曲線で描いている。やっぱり構文木の辺はベジェ曲線にするのがかっこいい。
function drawArrow(x1: number, y1: number, x2: number, y2: number) {
context.beginPath();
context.moveTo(x1, y1);
context.lineTo(x1 - s, y1 + Math.sqrt(3) * s);
context.lineTo(x1 + s, y1 + Math.sqrt(3) * s);
context.closePath();
context.fill();
context.bezierCurveTo(x1, (y1 + y2) / 2, x2, (y1 + y2) / 2, x2, y2);
context.stroke();
}
season1618.hatenablog.jp
npm run build
するとbuildディレクトリ以下に生成物ができる。ディレクトリ名をdocsに変更した上でgithub pagesを設定。そのままだとindex.htmlでファイルのリンクが/...
となってFailed to load resourceと出るので、package.jsonに"homepage": "."
を追加。
参考文献