[Common Lisp] システム内のパッケージ間の関係をグラフ化

システム内に存在するパッケージ間の参照関係をgraphvizでグラフ化するRoswellスクリプトmake-package-tree.rosを書いてみました。リファクタリングに使える…かもしれません。

github.com

前説

これを作ったきっかけの話です。

Common Lispを始めた頃に、とりあえず練習用でオセロのプログラムを書いていました。単純なミニマックス探索(αβ法)と単純なモンテカルロ木探索(UCT)*1を備えていて、簡単なCUIインタフェースもつけてます。

そうして右も左も分からない中で書いたのがothello-clです*2。パッケージを分けたり、SBCL, CCLの両対応にしたりと、これをもう少し整えたものが下のcl-othelloです。

github.com

このとき、とりあえずテストを通すこと優先で各パッケージでひたすらexportしていたのですが、だいぶ余計なものをexportしている気がしました。そんなわけで、リファクタリングついでにグラフ化して見てみよう、というのが今回のスクリプトを作った動機です。

使用感

使い方

引数なしでヘルプが見れます。こうしたヘルプの生成兼コマンドライン引数の処理にはCL-CLIを利用しています。

$ ./make-package-tree.ros
./make-package-tree.ros [OPTION]... SYSTEM-NAME

 [ OPTIONS ]

Global options:
  -P,--only-package                Show only packages (doesn't show symbols)
  -o,--output        <file>        Place the output into <file> (default: 
                                   temp.png)
  -e,--exclude       <package names> Exclude packages from graph (if you 
                                   exclude multiple packages, write them 
                                   separating by space)
  • システム名には(ql:quickload ...)でロードできるシステムの名前(小文字可)を入れます
  • アウトプット名は特に解析していないので、拡張子に関わらずPNGしか出ません
  • excludeの複数指定は"cl-othello cl-othello.utils"のような感じです

次に適用結果の一部を拡大して見方を説明します。

f:id:eshamster:20160321034045p:plain

  • 四角いボックスはパッケージ
    • 内部の楕円はエクスポートしているシンボル
      • 入ってくる矢印は他パッケージからの参照
        • ただし、use-pacakgeされている場合は省略
    • 小さい円はパッケージ自身*3
      • 入ってくる矢印はuse-packageされていることを示す(上の例にはないですが…)
      • 出て行く矢印はシンボルをimportもしくはパッケージをuse-packageしていることを示す

cl-othelloに適用した結果

Before: おおむねothello-clからの移植が終わった時点。コミットID:ba72a26...

f:id:eshamster:20160321012823p:plain 原寸大リンク(3047x4615)

After: 記事時点のコミット。コミットID:eb3fe18...("CL-OTHELLO"パッケージをexclude)

f:id:eshamster:20160321032745p:plain 原寸大リンク(2925x4126)

なるほど、分からん。

まあパッと見をどうこうするというよりは、ざっと眺めていって、参照されてないシンボルがあるけどこれexport必要だっけ、とか、このパッケージのシンボル1個だけ参照してるけど不要な参照してないっけ、とかを考えるためのものです。

ちなみに、--only-packageをつけるとこんな感じの出力になります。汚い…。

f:id:eshamster:20160321161612p:plain 原寸大リンク(1035x943)

実装について

対象となるパッケージを取り出す

まずは、システム内のパッケージを一通り取り出す部分です。怪しげなので、もっと賢い方法があれば知りたいです…。

;; ロードメッセージ省略コードやreadtableを戻すコードは省略
(defvar *unprocessed-pack-list* nil)

(defun make-macroexpand-hook-fun (old-hook)
  (lambda (fun form env)
    (when (and (consp form)
               (eq (car form) 'cl:defpackage))
      (pushnew (cadr form) *unprocessed-pack-list*
               :test #'string=))
    (funcall old-hook fun form env)))

(defun load-target-package-list (system-name)
  (ql:quickload system-name)
  (let ((*macroexpand-hook* (make-macroexpand-hook-fun *macroexpand-hook*)))
    (asdf:load-system (intern system-name "KEYWORD") :force t)))

ここはql:quickloadのパッケージ名出力コードを参考にしています。*macroexpand-hook*にフックをかけて、defpackageが来たらそのパッケージ名をリストに入れるというのが基本的な考え方です。しかし、ql:quickloadでは依存パッケージが全て読まれてしまうため、どれが対象のsystem下のパッケージか分からないという問題があります*4。そこで次のような力業に出ています。

  1. とりあえずql:quickloadで全てロード
  2. 上記のフックをかける
  3. (asdf:load-system ... :force t)で対象システムを無理やり読み直す
    • 依存システムはロード済みなので、対象システム下のパッケージだけがとれる…はず

参照している他パッケージのシンボルを取り出す

残りは末尾に全コードを貼り付けたので、書きたいところだけ簡潔に…。

どのパッケージのシンボルをインポートしているかを調べる処理のメインはinterpret-package関数です。do-symbolsで各パッケージ内の全シンボルを調べて、exportされているシンボルと、同システム内の別パッケージから継承したシンボルを記録しています。これで漏れが出ない…はず。

また、パッケージ間の関係を木構造(正確には有向グラフ?)と見た場合、幅優先探索の順序でパッケージを見ています(起点は上記のパッケージ探しで最初に見つけたもの)。この方がgraphviz上で元の木構造に近い形が得られやすいためです。実際、深さ優先探索版をcl-othelloに適用したところ、ほぼ全パッケージが縦に並んでしまい、うまく配置できないようでした。ただ、こうした探索自体が歴史的経緯*5で必要だったもので、今なら単に上記で見つけた順で問題ない気もします。

グラフ化

graphviz用のコードを出すためにs-dotというライブラリを利用しています。graphvizのドット形式をS式で書くためのDSL兼レンダラです。

ただ困ったことに、DSLのキーワードであるnodeやらedgeやらが全てs-dotパッケージのシンボルとeq判定をとっていて、しかもexportされていません…*6。一個や二個ではないので、対症療法としても一々s-dot::nodeのように書くのも面倒です。そんなわけで、下記のリードマクロで$nodeのように書けるようにしています。

(set-macro-character #\$ #'(lambda (stream &rest rest)
                             (declare (ignore rest))
                             (let ((sym (read stream nil)))
                               (intern (symbol-name sym) "S-DOT"))))

全コード

この記事時点のコードを貼り付けます。

gist.github.com

感想

こうメタな情報に普通にアクセスできるのはなんだか気分がいいですね。


*1:モンテカルロ木探索といえばAlpha Goが話題ですね。Deep Learningばかり話題になっている感もありますが、2004年に登場したモンテカルロ木探索というブレイクスルーあってのものだとこっそり主張しておきたかったりします。個人的には、モンテカルロ木探索がDeep Learningという翼を得てさらに飛翔するのか、翼だけ飛んでいってしまうのか気になってます。

*2:「clなんとか」という名前順になっていない辺り分かってなかった感が目に見えます

*3:本当はボックス(cluster)から直接線を伸ばしたいのですが、それができないので代替手段です

*4:quickloadの方は依存パッケージも全て出力するのでこの問題は関係ありません

*5:元々system内のパッケージ一覧を取り出す方法を思いつかなかったので、システム名と同名のパッケージがあると仮定(ないとエラー)して、そこから辿っていました

*6:まあ大量にexportされても困るのでキーワードにしておいて欲しかったという話です。実際、キーワード利用に変更したs-dot2というプロジェクトがあったりします(quicklispのリポジトリには登録されていませんが…)