依存地獄の解決

新しいブログ記事が読みたいといういう声が聞こえてきたので、久しぶりにブログを書く。最近仕事で依存地獄の解決をしているので、その方法を書いてみる。

現代のソフトウェアは様々なライブラリに依存するものだ。ソフトウェアAがライブラリBに依存する場合を考える。

ソフトウェアAとライブラリBはそれぞれ別のgitレポジトリで管理されている。依存はパッケージマネージャーで管理されていて、レポジトリの中に設定ファイルがある。レポジトリAの中にはレポジトリBに依存する設定ファイルがある。npm, cargo, pip, rebar3といったパッケージマネージャーを考えるといい。

もちろんライブラリBも別のライブラリC, Dに依存している。

この場合、AはC, Dに間接的に依存していることになる。

実はさらにFというライブラリがあり、これはA, B, Dが依存している。

どんどん複雑になってきた。

ソフトウェアは不具合を修正したり新機能を追加したりする。そのため、同じレポジトリであれば同じというわけではない。今使っているパッケージマネージャーは、gitのハッシュ値やタグ、ブランチを指定することができる。master HEADを常に参照していると、互換性を壊す変更が入ったときに対応する暇がなくビルド不可能になる。そこで依存はgit tagで特定のコミットを指定している。レポジトリとそのバージョンを簡易的にAnで表してみよう。

今、レポジトリB1を変更してB2を作り出した。新しいB2を使うには、A1の設定ファイルに記述されている依存を変更しなければならない。設定ファイルを変更するということは、レポジトリAにも新しいコミットが行われ、A2が作られる。

C1を変更してC2を作り出した。この場合、まずB2のCに対する依存を変更してB3を作る。

その後、B3に依存するA3を作る。

A2, B2, C1はもう使わないのでグラフから削除しよう。

F1を変更してF2を作った場合は本当に複雑だ。Fに直接、関節に依存しているのはA, B, Dだ。しかし、BはDにも依存している。DのFに対する依存を変更したコミットを作らなければ、BのDに対する依存は修正できない。AとBの関係も同様だ。

以下のような手順になる、

F1を変更して、F2を作る
D1を変更して、F2に依存した、D2を作る
B3を変更して、D2, F2に依存した、B4を作る
A3を変更して、B4, F2に依存した、A4を作る

レポジトリが5個、エッジが6本しかない依存関係でもここまで面倒になる。

最終的に変更するレポジトリは4個なのだが、作業は並列化できない。なぜならば、Dを変更するにはFを変更していなければならず、Bを変更するにはD, Fを変更していなければならず、Aを変更するにはB, Fを変更していなければならないからだ。

健全なソフトウェア開発にはテストとコードレビューが不可欠だ。テストの実行は自動化できるが、コードレビューは自動化できない。変更をマージするにはコード変更者ではない複数人のコードレビューを経て承認されなければならないとすると、Fの変更には4回のコードレビューが必要だ。レポジトリの変更とコードレビューは交互に繰り返さなければならないので、コード変更者はレビューのたびに待たされることになる。

そもそも、Fに依存するレポジトリをすべて把握していないこともある。Fを変更し、ソフトウェアのトップレベルのレポジトリAはわかりやすいから変更するとして、残りを変更しない場合、このような依存関係になってしまう。

これが依存地獄だ。

同一レポジトリの複数のバージョンが混在したときにパッケージマネージャーがどのように振る舞うかについて正解はない。あるパッケージマネージャーはバージョンの混合を許す。あるパッケージマネージャーは、決定的な方法でバージョンを一意に保とうとする。

バージョンの混合を許す場合、Fに致命的な不具合があって修正したつもりでも、BやDから使うときは修正されないコードが実行されてしまう。バージョンを一意に保つ場合、F1かF2のどちらかが使われる。もしF1が選ばれた場合は修正が適用されない。

バージョンを決定的に一意に保つ方法として、上位ノードの指定した依存バージョンを優先し、同じ深さのノードの場合は辞書順で優先順位を決定するとしよう。その場合、最上位であるAからF2が依存されているので、ソフトウェアとして結合した場合にはFの修正が適用される。ただし、レポジトリBやDを単体で動かしたときは修正が適用されない。レポジトリごとに単体テストがある場合は問題だ。

大規模なソフトウェアは依存も多い。100個のレポジトリ、500本のエッジからなる依存関係をグラフに描くととんでもないことになる。そして、ほとんどのレポジトリで依存地獄が発生していた場合に修正する手間を考えてみよう。

この規模になるとグラフとして描画した結果から修正するレポジトリの順番を人力で決定するのが不可能になる。依存関係を解決して依存グラフの一番下から変更するレポジトリの順番を自動で決定する必要がある。

依存関係の解決をするには、依存関係を有向非巡回グラフに落とし込んだ上で、トポロジカルソートする。こう書くと難しそうだが、実はシェルスクリプトだけで解決できる。POSIXにはトポロジカルソートしてくれるtsortがあるのだ。

まず依存関係を書き出す。tsortは偶数個の入力を取る。文字列ペアの1つ目が依存する文字列、2つ目が依存されている文字列だ。AがBに依存しているならば、"A B"となる。

$ cat deps.txt
A  B
A  F
B  C
B  D
B  F
D  F

これをtsortに突っ込めばいい。

$ cat deps.txt | tsort
A
B
D
C
F

ただしtsortは依存グラフの上から下にソートしていくので今回ほしい順番とは逆順だ。tacにパイプして行ごとに逆順で出力する。

$ cat deps.txt | tsort | tac
F
C
D
B
A

これでレポジトリを修正していく順番がわかった。

実際に依存地獄を解決するには、ソフトウェアを構成するレポジトリ群のうち、依存地獄に陥っているレポジトリとそれに依存しているレポジトリ群だけを抽出し、依存解決し、レポジトリごとにどのレポジトリを修正すればいいか出力などするとさらに便利だ。

しかしなぜtsortというプログラムがPOSIXにあるのだろうか。その背景事情はGNUのドキュメントに書いてある。

https://www.gnu.org/software/coreutils/manual/html_node/tsort-background.html

初期のUNIXリンカーはアーカイブファイルを入力された順番で一回しか処理しなかった。そのため、依存関係を解決して正しい順序でアーカイブファイルを入力してやらなければならなかった。この処理はlorderというシェルスクリプトで行われていて、そのシェルスクリプトでトポロジカルソートをする必要があったのでtsortが実装された。

tsort自体はC++なら100行程度で実装できる簡単なものだ。私も今回の件で勉強がてら書いてみた。奇数個の入力のときに警告せず最後の入力を無視する以外は完全なtsortの実装だ。

https://github.com/EzoeRyou/tsort/blob/main/main.cpp