Zipperでコードフォーマッターを実装する (greglook/cljstyle に学ぶ)

北川です。

Clojure 始めました。 Clojure のお勉強をするにあたり何か良い題材はないかと探していたところ greglook/cljstyle というツールが目につきました。以前からフォーマッターや linter の実装に興味があったということもあり、ちょうど良いのでこれを題材にお勉強を始めていきます。

コンテキスト不明なものをいきなり読んでも眠くなってしまいそうなので greglook/cljstyle のソースコードをそのまま抜粋するなどはしません。しかし、この記事を読み終える頃には自分好みのコードフォーマッターを再実装できそうな気持ちになれます。*1

実際にcljstyleを使ってフォーマットをかけていく方法については、こちらの記事をご覧ください。

tech.toyokumo.co.jp

フォーマット処理の流れ

例えば cljstyle check コマンドは以下の通りです。

Clojure コードの文字列を取得
文字列をパースしてツリーを取得
ツリーをトラバースしてフォーマットルールに反した箇所を探す
変更する
オリジナルソースと変更後ソースの diff をとる
結果を整形して表示する

1, 5, 6 についてはやるだけなので 2, 3, 4, について見ていきます。

Zipper

本題に入る前に Zipper についてほんのり触れておきます。Zipper とは1996年に Gérard Huet という人が発明したデータ構造です。 Clojure のような immutable なデータ構造を変更する際 Zipper を適用すると比較的簡単な操作で効率的に再構築できるというものです。Zipper の特徴は現在の注目点(loc)と、そこに至るまでのパスを保持している点です。あまり Zipper について思いを馳せると長くなってしまうので、今回は便利なAPIだなあと思うことにします。さっそく使い方を見ていきます。

(require [clojure.zip :as zip])

(-> (zip/vector-zip [1 2 [3 4]])
    (zip/down))

;;=> [1 {:l [], :pnodes [[1 2 [3 4]]], :ppath nil, :r (2 [3 4])}]

vector-zip を使うと vector をトラバースするための Zipper が得られます。zip/down でルートからひとつ下に降り、注目点が 1, right-node が [2 [3 4]] という状態になりました。

(require [clojure.zip :as zip])

(-> (zip/vector-zip [1 2 [3 4]])
    (zip/down)
    (zip/right))

;;=> [2 {:l [1], :pnodes [[1 2 [3 4]]], :ppath nil, :r ([3 4])}]

さらに right-node へ進むと、注目点が 2, right-node が [3 4]、left-node が [1] という状態になりました。

(require [clojure.zip :as zip])

(-> (zip/vector-zip [1 2 [3 4]])
    (zip/down)
    (zip/right)
    (zip/edit inc)
    (zip/root))

;;=> [1 3 [3 4]]

注目点の値を1増やし zip/root でデータを再構築すると変更後の vector を取得することができました。このように Zipper はデータを歩き回り変更したい時に便利ですね。

rewrite-clj で文字列をパース

greglook/cljstyle では文字列をパースしてツリーを取得する工程で、xsc/rewrite-clj が使われています。rewrite-clj の返す Zipper は clojure.zip の上に実装されているので rewrite-clj の提供するAPIはもちろん使えますし先ほどの zip/right のような clojure.zip が提供する操作も問題なく使うことができます。動きを見ていきます。

(require [rewrite-clj.zip :as z])

(z/of-string "(defn add [a b] (+ a b)) (add 1 2)")

;;=> [<list: (defn add [a b] (+ a b)) >
;;  {:l [], :pnodes [<forms: (defn add [a b] (+ a b)) (add 1 2) >], :ppath nil,
;;  :r (<whitespace: " " > <list: (add 1 2) >)}]

z/of-string は文字列から Clojure コードツリーの Zipper を生成します。現在の注目点が (defn add [a b] (+ a b)) フォームとなり、right-node が残りの (add 1 2) という部分です。ここでうれしいのが、ホワイトスペース等のフォームの評価時には不要なトークンを保持しているという点です。これはコードフォーマッターを実装する時にはとても都合が良さそうです。

実際にフォーマットしてみる - surrounding-whitespace の除去

greglook/cljstyle でもフォーマットルールとして定義されている surrounding-whitespace の除去をやってみます。

(　　　* a 3　) このようなフォームを (* a 3) このようにフォーマットします。

(require
  [clojure.zip :as zip]
  [rewrite-clj.zip :as z])

(defn surrounding-whitespace?
  [zloc]
  (and (z/whitespace? zloc)
       (or (nil? (zip/left zloc))
           (nil? (z/skip zip/right z/whitespace? zloc)))))

(defn remove-surrounding-whitespace
  [form]
  (loop [zloc (z/of-string form)]
    (if-let [zloc (z/find-next zloc zip/next surrounding-whitespace?)]
      (recur (zip/remove zloc))
      zloc)))

remove-surrounding-whitespace では最初に (z/of-string form) で受け取った Clojure コードをトラバースするための Zipper を作ります。

(z/find-next zloc zip/next surrounding-whitespace?) では、述語 surrounding-whitespace? にマッチするノードを探します。

zip/next は z/find-next が使用する次の注目点への移動関数です。rewrite-clj.zip が提供する z/next はホワイトスペースやコメントをスキップするため普通に Zipper を歩く分には便利なのですが、コードフォーマッターとしてはスキップして欲しくないです。そこで clojure.zip が提供する zip/next を使います。zip/next はホワイトスペース等を無視せず Zipper を深さ優先的に探索するので今回はこれが使えます。

surrounding-whitespace? は注目点がホワイトスペースなノードであることと、フォーム左端または右端であることを調べています。

(z/skip zip/right z/whitespace? zloc) では、Zipper 全体ではなくトップレベルの1フォーム内をホワイトスペース等は無視せず探索したいため z/skip と zip/right を使用していることがポイントです。

(require
  [clojure.zip :as zip]
  [rewrite-clj.zip :as z])

;; ...

(z/root-string (remove-surrounding-whitespace "(    * a 3  )"))
;;=> "(* a 3)"

(z/root-string (remove-surrounding-whitespace "(  + 2 3 (    * 4 5    )  )   (   + d 3    )"))
;;=> "(+ 2 3 (* 4 5))   (+ d 3)"

動いているように見えます。

一般化する

先ほどの remove-surrounding-whitespace から、フォーマットルールに反しているか調べる述語と、ルール違反を検知したら何をするか、を分離すると一般化することができます。

(require
  [clojure.zip :as zip]
  [rewrite-clj.zip :as z])

(defn edit-all
  [form p? f]
  (loop [zloc (z/of-string form)]
    (if-let [zloc (z/find-next zloc zip/next p?)]
      (recur (f zloc))
      zloc)))

さらにコードフォーマッター用の設定ファイル等からマップを生成し、設定が有効ならば何をするかを定義することができます。

(require
  [clojure.zip :as zip]
  [rewrite-clj.zip :as z])

(defn remove-surrounding-whitespace
  "Transform this form by removing any surrounding whitespace nodes."
  [form]
  (z/root-string (edit-all form surrounding-whitespace? zip/remove)))

(defn reformat-form
  "Transform this form by applying formatting rules to it."
  [form config]
  (cond-> form
    ;; config は
    ;; { :remove-surrounding-whitespace? true, :another-rule? false, ... }
    ;; のようなマップ
    (:remove-surrounding-whitespace? config true)
    (remove-surrounding-whitespace)
    ;; ...
    ))

あとは、フォーマットルールに反しているか調べる述語と、ルール違反を検知したら何をするか、をひとつひとつ実装していけばコードフォーマッターが完成しそうですね。

ここまでくると greglook/cljstyle のソースコードにかなり近くなってきました。実際にはもっと細やかな気配りのもと書かれていますが、要旨は押さえられていると思います。

(上記の実装だと設定項目の数だけソースコード全体をパースして走査することになるのが少し気になりますね。)

最後に

自分でもコードフォーマッターが実装できそうな気持ちになれました。トークン列からソースコード上の位置などを取得できれば linter も同じように実装できそうです。

また、rewrite-clj といったツールを作るためのツールの存在は偉大ですね。ぼくも rewrite-clj を使って何かやりたいなあと思えてきました。

トヨクモ株式会社ではClojureを書きたいエンジニア、PHP/Reactを書きたいエンジニア、技術が好きなエンジニアを募集しております。

よろしければ採用ページをご覧ください。

*1:気持ちになれます

Toyokumo Tech Blog

トヨクモ株式会社の開発本部のブログです。