依存関係と階層構造の軛

21世紀現在のプログラミング言語において、モジュールという機能はほぼ必要不可欠である。ソースコードを分割し、明示的な依存関係を指定する仕組みであるモジュールは、以下のような様々な恩恵をもたらす。

  • インクリメンタルビルド: モジュールごとにコンパイル結果を保存し、変更されていない部分を再コンパイルするのを防ぐ。
  • 内部の隠蔽: 実装の詳細を隠蔽し、モジュール外から触れないようにする。プログラムの見通しをよくしたり、不正な操作をする機会を減らす。
  • アーキテクチャの整理: モジュールは他のモジュールを参照できるが、原則として相互参照はしない。依存の向きを定めることで、適切な抽象化と、 それに基づいた実装の分離を促す。

さて、いくらモジュールが便利と言えど、数が増えすぎるとさすがに扱いにくい*1。そのため、ディレクトリの構造をモジュールの階層構造として運用する仕組みが備わっていることが多い。 コンパイラから見れば、ドットなどで区切られたモジュール名から、対応するファイルを探すだけの話だ。あくまで人間の都合であり、上で挙げたような恩恵とはあまり関係してこない──だが、本当にそれでいいのだろうか。

若干わざとらしい例ではあるが、掲示板のアプリケーションを実装するに当たり、以下のようにモジュールを分割するとしよう。

UtilsとModelの二つのディレクトリを設ける。Model.Commentでは、投稿を表すデータ型や、データベースの操作を定義する。Utils.Miscには雑多な便利関数をまとめ、Utils.Markupでは、投稿をHTMLに変換する処理を記述する。

あからさまかもしれないがこの構造には問題がある。というのも、UtilsとModelsは、ディレクトリ単位で見ると、双方向に依存関係を持っているのだ。 先述した通り、コンパイラから見れば、モジュールがどこのディレクトリに属していようが本質は変わらないし、正しい入力である。しかし、開発者はディレクトリの分割に意味を見出しているという齟齬が発生する(そして、コンパイラはそれを指摘しようがない)。この齟齬を放置したまま開発を続けていくと、想定外に深い依存関係が発生してビルドが遅くなったり、「Modelに依存したUtils」という存在と辻褄を合わせるために、本来隠蔽すべき詳細がどんどん漏れ出したりしてしまう。

これを防ぐ手段として、それぞれのディレクトリをパッケージ化し、依存関係を明示するというものがある。これは双方向の依存を防ぐという意味では効果的な一方、パッケージごとのメタデータを管理するコストが高まったり、パッケージ単位でのキャッシュはできても、モジュール単位のインクリメンタルビルドが効きにくくなるなど、デメリットも無視できない。

ならば、新たに静的解析を実装し、こういった問題を検出しようではないか。まずはモジュールの依存関係のグラフを可視化して見通しを立てたい──dot形式に変換し、graphvizで表示するだけの簡単な話だ。

……どうやら、そんな簡単な話ではなかったようだ。

もう少し、ディレクトリ同士の依存関係に着目して考えてみよう。Foo.Bar.A.BがFoo.Baz.C.Dに依存しているとき、「BarがBazに依存している」という情報さえ残せば、それより深い部分の情報は削いでも構わない。つまり、以下のようなアルゴリズムでグラフを導き出す。

  • 依存元、依存先のモジュール名をドットで区切り、リストにする
  • どちらかのリストが空になったら、終了する
  • リストの先頭を見る
    • 名前が同じなら、先頭を取り除く
    • 名前が違っていたら、辺を作成する

「Foo.BarがFoo.Bar.Bazに依存している」のような関係は今回は考慮しない。もし考慮したい場合は、「リストが空になったら、辺を作成する」ように書き換えればよい。

このアルゴリズムを利用すると、親のディレクトリごとに分割されたグラフができ、graphvizのcircoを使うと図のようになる。最初のグラフとはえらい違いだ。

成分をクローズアップすると以下のようになる。ディレクトリに要約されているため、関係が読みやすくなっているのがわかる。

だが本題に戻ろう。ディレクトリの意義を保つためには、相互依存がない──いや、さらに有向閉路が存在しないことを保証したい。つまり、強連結成分分解すればよいのだ。早速会社のコードベースに適用してみると、かなりの大物が釣れた。各辺の重みはインポートの件数を表す。

このグラフは強連結であり、すなわちどの頂点の間にも道が存在する。本来、このようなことが発生しないようにパッケージを分割していたはずなので少々驚きの結果だ。パッケージが細かすぎたゆえに、抜け道ができてしまったのだろう。

有向非巡回グラフにするために取り除くべき辺はFeedback arc set(FAS)と呼ばれている。 最小のFASを求めるのはNP困難だが、今回のケースでは抜け道の重みが圧倒的に小さい。そのため、重い辺から順に再構築していき、閉路を生む候補だけ弾く貪欲法で実用的な結果が得られそうだ。

件のグラフについては、以下の四つを除去するとDAGになる。幸い、件数はそれほど多くないので、循環をなくすのはそれほど難しくなさそうだ。

Queries -> QueryServices
Effects -> JobWorker
SendGrid -> Effects
DomainObjects -> Effects

ここまでの処理を自動化するため、Haskellコンパイラのプラグインとして実装したスタンドアロンのコマンドラインツールとして実装した。 orderorder srcを実行すると、src以下のモジュール同士の依存関係を調べ、強連結成分を列挙する。この結果を保存しておいて差分をCIなどでチェックすれば、関係を破壊するような依存関係が増えた際に気付くことが可能になる。

github.com

もちろん、ここまでの議論はHaskell以外にも適用できるため、他の言語にも同等のものを実装することは可能なはずだ。

まとめ

今まではモジュールの階層構造に明確なルールがなく、ある意味飾りだった。しかし「ディレクトリ間の依存関係」という概念を導入することで、自然に「モジュールの依存関係がDAGであるように、ディレクトリの依存関係もまたDAGになる」という制約を導入でき、我々の直観とのすり合わせができた。この仕組みをクリーンアーキテクチャの促進・保守に活用していきたい。

PRæž 

ここまで散々階層構造の話をしてきたが、HERPはオープンでフラットな組織を是としており、現在も積極的に技術者を募集している。興味のある方は、以下の資料を参照されたし。

github.com

*1:ワイルドカードを使うと、コマンドライン引数の長さが限界を超えてしまうなど、現実的な支障も発生する