season's quarterly

数学/物理/プログラミング

【React + TypeScript】コードエディタとASTビュアーを作る

  • [2024/2/24]: 追記・コード修正

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[]; // DAGの隣接ノード
  belows: Node[]; // 木構造としての子ノード
  thread: Node | null; // Reingold-Tilfordアルゴリズムで用いる、木上の探索を効率化するためのポインタ

  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();
}

Canvasのマウス操作

season1618.hatenablog.jp

GitHub Pages

npm run buildするとbuildディレクトリ以下に生成物ができる。ディレクトリ名をdocsに変更した上でgithub pagesを設定。そのままだとindex.htmlでファイルのリンクが/...となってFailed to load resourceと出るので、package.jsonに"homepage": "."を追加。

参考文献