sbtにおけるKeyとは何か? 〜 有向非巡回グラフ(Directed Acyclic Graph)とsbt

sbtを使ったことがある人なら、たいていSettingKeyやTaskKeyという言葉を聞いたことがあるはずです。もし聞いたことがなくても、1度でもsbtを使ったことがあるなら、すでに知らないうちにそれらに触れているはずでしょう。
それらSettingKeyやTaskKeyを含んだsbtの内部DSLについては、その独特さゆえに、好みが分かれることが多いと思います。
そもそも

  • なぜSettingKeyやTaskKeyという概念が必要なのか?
  • それらは一体何なのか?

ということに関して、少し別の視点から考察や解説をしてみることによって、sbt自体の理解の手助けとなることを目的として、このエントリを書いてみます。


なんだか、少しばかり堅苦しい始まり(?)にしてみましたが、つまり


「sbtのKeyは有向非巡回グラフにおけるNodeであり、build.sbtは有向非巡回グラフを組み立てるDSLである」


みたいな話をするだけです。今の一文を聞いただけで完全に理解した人は、この続きは読まなくていいでしょう。


sbt自体のアーキテクチャの説明としては、以前もわりと頑張って以下のようなものを書いたことがありますが


sbtの密結合な内部アーキテクチャ


今回説明するのは、その部分と比べればフロント寄り?というか、その部分とは基本的に独立して考えることが可能な部分であり、sbtの根本的な重要な概念の一つだと思っています。



SettingKeyやTaskKeyそのものについては、このエントリではそんなに詳しく解説しません。sbtの公式ドキュメントや、最近だと、このまえのj5ik2oさんのScala関西での発表資料をみるといいかもしれません。

さて、有向非巡回グラフ(Directed Acyclic Graph)って聞いたことありますか?言葉だけだと少しすごそうに見える(?)かもしれませんが、プログラミングをやっていると、いたるところにあふれていると言っても過言ではないかもしれません。
たとえばScalaのclassやtraitの継承関係あたりもそうじゃないでしょうか?
sbtのシステムとの関係というか少し似ている(?)ものでいえば、SparkのJobの依存関係なんかも、DAGが使われているはずです。*1
あとは、最近話題?なakka-streamのFlowGraphあたりも、おそらくDAGでしょう

https://github.com/akka/akka/blob/releasing-akka-stream-and-http-experimental-1.0/akka-stream-tests/src/test/scala/akka/stream/scaladsl/FlowGraphCompileSpec.scala#L148

例を上げていったらキリがないほど身の回りにあふれているはず?なので、他にも自分で探してみてください。


DAGの説明自体も丁寧にはしないので、wikipediaなり何なりを読んでください


wikipedia 有向非巡回グラフ


いま「SparkのJobの依存関係」と言いましたが、sbtでもつまり「Task同士の依存関係」があります。sbtには、代表的なものとして、SettingKeyとTaskKeyという2種類のKeyがあります。*2どちらで説明しても本質は同じなので、あまり区別せずに適当に例を挙げていきますが、たとえば

  • compileというTaskがある
  • test:compile(テストコードのコンパイル)というTaskもある
  • testというTaskがある

というときに

  • test:compileはcompileというTaskに依存する
  • testはtest:compileに依存する

という関係のはずですね?これだと単に一直線な依存関係です。もうすこし「グラフ」なことが意識しやすい例を挙げるとしたら、以下のようなマルチプロジェクトになっている場合

lazl val a = project

lazl val b = project

lazl val c = project.dependsOn(a, b)
  • cのコードをcompileするには、まずaとbをコンパイルする必要がある
  • しかし、aとb自体には依存関係はないので、aを先にコンパイルしても、bを先にコンパイルしてもどちらでもよいし、並列に実行しても良い

というような関係ですね?*3
今は、compileやtestくらいしか挙げていませんが、他にも「プロジェクトをビルドする」という際には、色んな行為を行うはずです。

  • sbt上からmainメソッドの実行
  • ソースコード生成
  • 依存ライブラリの解決
  • scaladocの生成
  • jarの生成
  • pom.xmlの生成
  • その他、任意の色々な独自task


sbtがデフォルトで用意しているKey一覧はKeys.scalaというファイルにあるので、暇な時になんとなく眺めるのをオススメします


https://github.com/sbt/sbt/blob/v0.13.8/main/src/main/scala/sbt/Keys.scala


それらは、相互に複雑に依存し合っているはずですね?しかしどんなに複雑であろうとも、基本的にそれは
「有向非巡回グラフで表現できる」
というのがポイントです。SettingKeyはともかくTaskKeyの場合、副作用があり得るので何度も評価できるようになってなければならないし、それぞれのTaskは単にlazy valかdefのようなものではなく「全体の関係をデータ構造としてグラフで保持」する必要があります。

また、さきほど、さり気なく「並列に実行しても良い」と書きましたが、sbtは事実、並列に実行可能な部分は並列に実行します。
仮に並列に実行しないとしても、依存関係を把握して、無駄なTaskを再実行しないためには、グラフとして保持するのは必要不可欠です。


並列実行の観点で言うと、よこたさんの以下の記事


sbt-sequential を用いたタスクの逐次化


あたりも、興味があれば読んでみるとよいでしょう。(最近この機能はsbt本体に入りました)



ここまでの説明で

  • え、そんなこと当たり前だろ?
  • 何言ってるかわからない
  • なるほどそういうことだったのか!?

とそれぞれ思った人が何割ずつなのか不明ですが、そういうことなのです!(強引


sbtのDSLが独特すぎて意味不明だと感じていた人も、その「有向非巡回グラフ」という点を意識すると、sbtと少しだけ仲良くなれるかもしれません。つまり「グラフの言葉」を使ってsbtのDSLを説明してみると、以下のようになります

// fooというnodeに、それまで繋がっていたedgeを全部断ち切って、"bar"という固定値で上書き

foo := "bar"
// aというnodeに、bとcというnodeをつなげる
// あくまでもaとb、aとcの結びつけ、であって、
// bからc、もしくはcからbへの依存関係は結びつけていない

a := {
  f(b.value, c.value)
}

// マクロ使わない書き方
a <<= (b, c).map{ (b0, c0) =>
  f(b0, c0)
}
// node間の依存関係は変えずに、edgeの値だけを変換

a ~= { currentValue => f(currentValue) }

これら、Keyの依存関係は、データ構造としてずっと保持しておかないといけません。依存関係の解決は、すぐその場でおこなわれるのではなく、ある程度必要になるまで遅延されるはずです。また、sbtのコンソール上で"set"というコマンドを使って、インタラクティブにグラフ構造を変更することも可能です。


sbtがDAGを使っているという証拠に、そのままな DAG.scala というファイルが存在します

https://github.com/sbt/sbt/blob/v0.13.8/util/collection/src/main/scala/sbt/Dag.scala

また、その中に topologicalSort というメソッドもあり、それが
「グラフの依存関係を解決して、ソートする(一直線に並べる)」
ためのものです。ソートしないグラフの構造のままだと、どこから実行すればいいのかわからないので、ソートして、依存関係の大元の部分から実行するわけですね?


また、DAGとして保持するというのは、

  • node Aの値はキャッシュ可能にする
  • node Aに依存したnode Bは、node Aのキャッシュ済みの値があれば、通常それを使う
  • なので、node Bを評価しようとした場合は、まず依存先であるnode Aのキャッシュの有無を調べ、キャッシュが無ければnode Aを評価する

といったことも可能です。具体的にはcompileとtestのTaskはそういう関係ですね?


sbtとのDSLとの関連として言えば
「そのDAGを組み立てるためのDSLが(Scalaのオブジェクト的には) immutable」
なので、すこし独特に感じるのかもしれません*4


そのような「タスク同士の依存関係」を表現するには、DAGは最適なデータ構造だと思うので、他のビルドツールでも多かれ少なかれ、内部的には似たような構造を持っていると思うのですが、他のビルドツール詳しくないのでわかりません。誰かそういう説明エントリ書いてください


また、たとえばbuild.sbtに以下のようなものを書くと「Cyclic reference involving」というエラーになると思いますが

val a = SettingKey[String]("a")
val b = SettingKey[String]("b")

a := b.value
b := a.value

TaskやSettingの依存関係は
「有向巡回グラフ」
でなければならないので、sbtはある意味その「グラフが循環している」という、内部のエラーをそのまま投げている、ということなのです。
初心者が何も知らずにそのエラー見ても、わかりづらくて面食らうことがある・・・のでしょうか?(初心者の頃の気持ちを思い出せない・・・)



また、コレを読んだ後に、よこたさんの

sbt 0.13 を用いた四次元空間内の移動

を読むと、少しは理解が進むのではないかと期待してるのですがどうでしょう?
というか、逆にこのDAGの構造を全く意識したことがない人が「4次元」と言われても、たぶん困惑するだけな気はします。



このように見ていくと、このTaskKeyとTaskがDAGとして表現されている、という部分だけみると「ビルドツール」というよりは、少し大げさに言えば

「依存関係を独自DSLによって宣言的に定義できる、別のプログラミング環境」

みたいな捉え方ができるかもしれません(?)。
ただ、そもそも他のビルドツールでも結局ある程度宣言的に(外部、内部問わず)DSLで依存関係を定義する、みたいなことは行われていると思うので、ビルドツールというものは、突き詰めていくと良くも悪くもそのようになっていくのが必然な気がしてるのですが、どうなんでしょう?


そういえば、twitterが作ったpantsというビルドツールでも、適当にソースコードgrepしたらDAGの文字出てきますね


https://github.com/pantsbuild/pants/blob/release_0.0.40/src/python/pants/backend/jvm/tasks/jvm_compile/execution_graph.py#L18



さて、それなりな長さを書いたわりには、最初に書いた

「sbtのKeyは有向非巡回グラフにおけるNodeであり、build.sbtは有向非巡回グラフを組み立てるDSLである」

を、言葉を変えて繰り返し言っただけのようなエントリですが、これがsbtの理解の助けになることを願って、そろそろ終わりにします

*1:sparkの設計詳しくないので詳細は解説できないので、ググってください・・・

*2:他にもInputKeyとかありますが・・・

*3:たとえば、ほかにも "bのテスト実行" と "cのコンパイル" も並列実行が可能ですね?

*4:いや、それ以外にもsbtのDSLが独特なのは理由がありそうですが