ベテランエンジニアも意外と知らない「パッケージ管理システムの仕組み」

この記事はNuco Advent Calendar 2023の16日目の記事です。

1. はじめに

世の中には、複雑な計算や面倒な分析を1行で済ませてくれるような便利なパッケージが数多くあります。それらをインストールするときには、以下のようなOSやプログラム言語に応じた簡単なコマンドを実行していることでしょう。

apt install {パッケージ名}

あなたがパッケージをインストールする裏で、それらのパッケージを管理するシステムが地獄のような処理を人知れず行なっていることはご存知でしたか？

本稿ではそんな縁の下の力持ちであるパッケージ管理システムが、一体どのような仕組みで動いているのか、その全貌を明らかにしていきたいと思います！

弊社Nucoでは、他にも様々なお役立ち記事を公開しています。よかったら、Organizationのページも覗いてみてください。
また、Nucoでは一緒に働く仲間も募集しています！興味をお持ちいただける方は、こちらまで。

目次

1. はじめに
2. パッケージ管理システムとは
3. パッケージ？とは何ぞや
4. パッケージ管理システムがないとどうなる？
5. パッケージ管理システム...その始まり...
6. 大解剖！パッケージ管理システムの裏側
7. まとめ

2. パッケージ管理システムとは

システムの概要

パッケージ管理システムは、ソフトウェア開発環境で使用されるモジュールやライブラリなどのパッケージを管理するためのシステムです。

パッケージマネージャやパッケージ管理ツールと呼ばれることもあります。

主な機能として、配布サーバーと連携してパッケージのインストールやアンインストール、そして依存関係の解決などのタスクを自動化し、開発プロセスを効率化します。

パッケージ配布サーバーとの連携

パッケージ管理システムは、パッケージを配布するために、システムに応じた専用のサーバーと連携します。

開発者は、パッケージをサーバーにアップロードし、他の開発者がそれをダウンロードして使用することができます。

インストール/アンインストール管理

パッケージ管理システムは、パッケージのインストールとアンインストールを簡単に行えるようにします。

開発者は、コマンドを使用して必要なパッケージをまとめてインストールしたり、きれいさっぱりアンインストールしたりすることができます。

依存関係の解決

パッケージ管理における依存関係とは、あるパッケージAを実行するためにはパッケージBとパッケージCが必要になるといったパッケージどうしの関係性のことを言います。

XXXXモジュールが見つかりません！といったエラー文はエンジニアの誰もが開発中に目にしたことがあるのではないでしょうか…？

詳しくは後述しますが、そうしたパッケージ同士の関係性を把握して、必要なものを取り揃えてくれる機能が「依存関係の解決」です。

3. パッケージ？とは何ぞや

そもそもの前提としてパッケージ管理システムが取り扱うパッケージについて説明します。

パッケージは、何らかの処理を実行させるために必要なモジュールやリソースをまとめたもので、複数のファイルを含んだディレクトリ構造であることが基本です。

パッケージの構成要素としては、基本的に以下のものが含まれています。

• プログラム
  • 処理を実行するソースコードそのもの
• ドキュメント
  • プログラムの説明、使い方などをまとめたファイル
    • READMEという名前で配置されることがほとんど
• メタデータ
  • そのパッケージに関する情報が記述されたデータ
    • パッケージの名前やバージョン情報などが含まれる

ライブラリ, モジュールとの違いは？

よくパッケージと混同されがちなライブラリ、モジュールという概念についても合わせて説明します。

ライブラリ
ライブラリは、再利用可能なコードの集まりであり、特定の目的に対しての機能を提供します。ライブラリを利用することで、面倒な計算や作業を容易に実行することが可能です。ライブラリには前述したパッケージも、後述するモジュールも含まれます。

モジュール
モジュールは、プログラムの一部分であり、通常はファイルとして実装されます。モジュールは関数、クラス、変数、定数などを含むことができます。

ザックリ言えば、ライブラリはパッケージやモジュールも含めたコードの集合体、パッケージは関連する複数のモジュールをまとめたディレクトリ、モジュールは個々のプログラムの一部分を指します。

4. パッケージ管理システムがないとどうなる？

もし自分の開発環境にパッケージ管理システムが搭載されていなかったら

パッケージ管理システムは我々の開発環境の裏側で膨大な数のパッケージを淡々と管理してくれています。

もし仮にあなたの開発環境にパッケージ管理システムが搭載されていなかったとして、ネットで見つけた素敵なパッケージをあなたのPCで実行できるようにするためには一体どれだけの作業が必要になるのでしょうか？

パッケージをインストールする際の手順は以下のようになります。

1. まず、パッケージAをインストールするための保存先を作成します。
2. インストールしたいパッケージAの開発者を調べて、パッケージAの配布元となるサーバーのアドレスを突き止めます。
3. 配布サーバーからパッケージAの実行に必要なファイルを全てダウンロードします。
4. ダウンロードしたファイルのREADME（説明ファイル）を読み込み、パッケージAの実行に必要な別のパッケージBを突き止めます。
   1. パッケージAの実行に必要なパッケージBの開発者を調べて、パッケージBの配布元となるサーバーのアドレスを突き止めます。
   2. 配布サーバーからパッケージBの実行に必要なファイルを全てダウンロードします。
   3. ダウンロードしたファイルのREADME（説明ファイル）を読み込み、パッケージBの実行に必要なパッケージCを突き止めます。
      1. パッケージBの実行に必要なパッケージCの開発者を調べて、パッケージCの配布元となるサーバーのアドレスを突き止めます。
      2. 配布サーバーからパッケージCの実行に必要なファイルを全てダウンロードします。
      3. ダウンロードしたファイルのREADME（説明ファイル）を読み込み、パッケージCの実行に必要なパッケージDを突き止めます。
         1. パッケージCの実行に必要なパッケージDの...（必要なパッケージが全て揃うまで繰り返す）
5. 必要なパッケージが全て揃ったら、自分の開発環境でビルド
6. 開発スタート…

こうして見ると、やはり依存パッケージをかき集める作業があまりにも負担に感じられます。

また、パッケージの保存先ですが、使用されるパッケージの媒体（OSなのかプログラム言語なのかなど）に応じて適切なディレクトリに配置しなければ正常に呼び出すことができないため、ここも注意が必要です。

さらに言えば、上記の問題はあくまでパッケージを新しくインストールするときの話になります。実際に開発を進めていくうえで、追加で必要なパッケージをインストールする場合や、既にインストールしていたパッケージにアップデートが必要になったとき、パッケージの依存関係は恐ろしく複雑になり混迷を極めることでしょう。（この問題は依存性地獄：Dependency Hellとも呼ばれます）

パッケージ管理システムがないと、
気が遠くなるようなインストール作業を延々と行うはめに...

5. パッケージ管理システム...その始まり...

最初のパッケージ管理システム？

1977年頃のUNIX OSには既に特定のプログラムのインストール/アンインストールそしてアップデートを管理するシステムが備わっていたとされています。
もちろん、この時点では依存関係の自動解決など複雑な機能は備わっていなかったようです。

求められた機能と発展

OSが広く普及されるのにつれて、ユーザーたちはオペレーティングシステムのカーネルだけでなく、それ以上の機能を求めるようになりました。初期にはシェルなどの基本的な要素が主流でしたが、Cut、sed、awkなどのユーティリティや、viやemacsなどのエディターなど、多くのコンポーネントが必要とされました。
これらのコンポーネントのソースコードを手動でビルドすることも可能でしたが、これにより新たな開発環境を構築する際のハードルが一層高くなりました。

1993年には、この課題に対処するために、より洗練されたパッケージマネージャーが登場しました。なんと、これら初期のパッケージマネージャーの一部は現在でも使われ続けています！例えば、Linux OSのひとつであるDebianは今でもdpkgを使用していますし、同じくLinux OSのRed Hatもrpmを採用しています。

これらのツールはシンプルですが、インストール、アップグレード、削除などが事前に構築されたバイナリパッケージをダウンロードすることが可能でした。さらに、現在と同様に、初期のパッケージマネージャーは他のソフトウェアに関する情報をエンコードするための依存関係メタデータの概念を導入していました。

1977年のUNIX OSにはパッケージ管理システムが存在していた。1993年に登場したDebianのdpkgやRedHatのrpmなどは今も使用されている。

6. 大解剖！パッケージ管理システムの裏側

それでは、パッケージ管理システムについてより具体的に解説していきます。

パッケージ配布サーバーとの連携

パッケージ配布サーバは、ソフトウェアやライブラリなどのパッケージを管理・保管し、ユーザーがそれらのパッケージを取得できるようにするサーバーです。さまざまなOSやプログラミング言語において、それぞれのパッケージ配布サーバが存在します。

以下に、代表的なOSやプログラミング言語ごとのパッケージ配布サーバの例を挙げます：

OSごとのパッケージ配布サーバ:

1. Linux (Debian/Ubuntu)
   • APT (Advanced Package Tool): Debianおよびその派生ディストリビューションで利用されるパッケージ管理ツール。公式のパッケージリポジトリからパッケージをインストールできます。
2. Linux (Red Hat/Fedora)
   • DNF (Dandified Yum): Red Hatおよびその派生ディストリビューションで利用されるパッケージ管理ツール。RPMパッケージを使用し、公式のリポジトリからパッケージを取得します。
3. macOS
   • Homebrew: macOS向けのパッケージ管理ツール。Homebrewが提供する公式リポジトリからパッケージをインストールできます。
4. Windows
   • Chocolatey: Windows向けのパッケージ管理ツール。Chocolateyが提供するパッケージギャラリーからアプリケーションやツールをインストールできます。

プログラミング言語ごとのパッケージ配布サーバ:

1. Node.js (JavaScript)
   • npm (Node Package Manager): Node.jsのパッケージ管理ツール。npm RegistryからNode.jsモジュールを取得できます。
2. Python
   • PyPI (Python Package Index): Pythonの公式パッケージリポジトリ。**pip**コマンドを使用してPyPIからパッケージをインストールできます。
3. Ruby
   • RubyGems: Rubyの公式パッケージリポジトリ。**gem**コマンドを使用してRubyGemsからGem（Rubyのパッケージ）をインストールできます。
4. Java
   • Maven Central Repository: Javaの公式中央リポジトリ。MavenやGradleなどのビルドツールを通じてJavaライブラリやアプリケーションを依存関係として指定できます。
5. C/C++ (Linux)
   • apt, yum: Linuxディストリビューションの公式パッケージリポジトリから、C/C++ライブラリやツールをインストールできます。

依存関係

パッケージの依存関係は、あるパッケージが他のパッケージを利用するために、他のパッケージに依存している状態を指します。

これにより、プログラマは既存の機能やライブラリを再利用し、ソフトウェアの開発を効果的に行うことができます。

依存関係のタイプ:

• ランタイム依存関係 : 実際にプログラムが実行される際に必要な依存関係。アプリケーションの主要な機能や構造に関わるものがこれに含まれます。
• 開発時依存関係 : 開発者がプロジェクトを構築する際にのみ必要な依存関係。例えば、テストフレームワークやビルドツールがこれに含まれます。

依存関係ツリー

パッケージの依存関係は通常、ツリー構造で表現されます。親のパッケージが子のパッケージに依存し、子のパッケージがさらに孫のパッケージに依存するといった形です。このツリー構造を理解することで、依存関係の複雑な構造を可視化することができます。

パッケージの依存関係はツリー構造で可視化できる

バージョン管理

セマンティックバージョニング

パッケージ管理、ひいてはソフトウェア開発の世界において、「依存性地獄」と呼ばれる恐ろしいものが存在します。システムが成長し、さまざまなパッケージが組み込まれるほど、より大きな地獄があなたを待ち受けることでしょう。

「一つのパッケージをアップグレードしたかっただけなのに...」

パッケージAでセキュリティの脆弱性が見つかった！
↓
新機能も気になってたし折角なので、パッケージAのバージョンを1から2へアップグレードした！
↓
パッケージAのバージョンをあげたことで、パッケージBが動かなくなった...
↓
仕方ないのでパッケージBのバージョンをあげたらパッケージCとDとEが.......

依存性地獄とはパッケージやライブラリのバージョン管理が幾重にも絡み合い、適切なバージョンのパッケージが利用できずに問題が発生する状況を指します。

この問題の解決策として、パッケージをより細かい粒度の番号で管理するための簡単なルールが提案されました。

例えばあなたがあるパッケージを開発し何らかのサーバーにアップロードしたとします。そして、あなたがそのパッケージの機能に改修を加える、あるいは何かしらソースコードを変更した際にはルールに従ってバージョン番号を上げなければなりません。そのルールでは、X.Y.Z（メジャー.マイナー.パッチ）というバージョン形式を守る必要があります。

このルールを「セマンティックバージョニング」と呼びます。

セマンティックバージョニングによるバージョン表記例

hogehoge 1.0.0
freezer 0.5.3

パッケージに影響を与えないバグ修正はパッチバージョンを、後方互換性を保ちつつパッケージを変更または追加した場合はマイナーバージョンを、そして、後方互換性のない大規模な変更を行なった場合はメジャーバージョンを上げます。

小規模なセキュリティアップデートであれば、パッチバージョンのみが新しいバージョンにアップデートするだけで、他のパッケージに与える影響を最小限にできるということです。

そして、セマンティックバージョニングに従えば、ユーザーはバージョン番号を見るだけで、新しいバージョンがどのように変更されたのかを把握することができるというメリットもあります！

パッケージのバージョンは、メジャー.マイナー.パッチの3段階で管理されている。

依存解決アルゴリズム

では、パッケージ管理システムは複雑怪奇な依存関係を一体どのように解決、解消しているのでしょうか。ここでは、その一端をご紹介いたします。

トポロジカルソート

トポロジカルソートはカーンのアルゴリズムとしても知られる一般的なソートアルゴリズムです。有向グラフを入力として使用して、各ノードがそのノードが指すノードの前に表示されるようにノードを並べ替えます。

このアルゴリズムはLinuxOSのパッケージ管理システムとして知られるaptやJavaのプロジェクト管理ツールであるApatchMavenで使用されています。

パッケージ管理においては、パッケージ自体を有向グラフのノード（点）、依存関係をエッジ（線）として表すことで、複雑な依存関係を持つパッケージたちを、どの順番でビルドしていけば良いかを決めるのに役立ちます。

それでは、実際にグラフを例に出して、トポロジカルソートの手順を見ていきましょう。
まず、以下のような有向グラフがあるとします。

6種類のパッケージが丸いノードで表されています。
各ノードから伸びている矢印の先にいるノードが、依存している子パッケージです。

ステップ1） グラフ内のすべてのノードの入次数または入力エッジを計算します。

• 入次数は、ノードを指す有向エッジを意味します。
• 出次数とは、ノードからの有向エッジを意味します。

このグラフの入次数と出次数と現在の状態は次のとおりです。

パッケージ	A	B	C	D	E	F
入次数	0	1	1	2	2	2
出次数	2	2	2	1	1	0

ステップ2） 0 の入次数または 0 の入力エッジを持つノードを見つけます。

入次数が 0 のノードは、そのノードに向かうエッジがないことを意味します。 ノード「A」の入次数は 0 です。これは、ノード「A」を指すエッジが存在しないことを意味します。

したがって、次のアクションを行います。

• このノードとその出次エッジ (外向きエッジ) を削除します。
• ノードをキューに入れます。
• 「A」の隣接ノードの次数カウントを更新します。

パッケージ	B	C	D	E	F
入次数	0	0	2	2	2
出次数	2	2	1	1	0

ステップ3） 入次数が 0 のノードを見つける必要があります。現在のグラフでは、「B」と「C」の入次数が 0 です。

ここでは、この2つのどちらかを選択できます。今回は「B」をグラフから削除してみましょう。
次に、他のノードの値を更新します。
これらの操作を実行すると、グラフとキューは次のようになります。

パッケージ	C	D	E	F
入次数	0	2	2	2
出次数	2	1	1	0

ステップ4） ノード「C」には入力エッジがありません。 そこで、グラフからノード「C」を削除し、キューにプッシュします。

これで、グラフは次のようになります。

パッケージ	D	E	F
入次数	0	0	2
出次数	1	1	0

ステップ5） ノード「D」と「E」の入次数が 0 であることがわかります。 ノードを取得してキューに入れましょう。

結果は次のようになります。

パッケージ	F
入次数	0
出次数	0

ステップ6） ノード「F」の入次数（入力エッジ）と出次数（出力エッジ）が 0 になりました。したがって、ノード「E」の前提条件はすべて満たされています。

ここでは、キューの最後に「F」を付けます。 したがって、ノードが残っていないため、アルゴリズムはここで終了します。

あとは、キューの順番でパッケージをビルドしていけば、なんの競合も起こすことなく、平穏無事にパッケージをインストールすることができるというわけです。

しかし、トポロジカルソートだけでは解決しきれない場合が存在します。

例えば以下のような依存関係があったとします。

パッケージ	X	Y	Z
入次数	1	1	1
出次数	1	1	1

トポロジカルソートでは入次数が0のノードを見つける必要がありましたが、こうなってしまってはもうお手上げです。上記のような循環のあるグラフでは、トポロジカルソートが機能しなくなってしまうのです...

トポロジカルソートでは、循環した依存関係を解決できない...！

ですが、安心してください。
このように依存関係が何かしらの競合を起こしてしまう場合にも解決する仕組みが存在します。

PubGrub

PubGrubは、Dart言語のパッケージ管理システムであるPubの依存関係解決アルゴリズムです。
このアルゴリズムは、効率的かつ、複数のパッケージ間における非互換性を明らかにできるという点で優れており、先述したPub(Dart)以外にもSwiftPM(Swift)や、gel-rb(Ruby)、poetry(Python)といった様々なパッケージ管理システムで取り入れられています。

トポロジカルソートと同様に、PubGrubにおいてもパッケージの依存関係を解決するためにグラフ理論に基づいたアルゴリズムを使用しています。このアルゴリズムは依存関係のグラフを構築し、各パッケージが他のパッケージにどのように依存しているかを考慮して解決を行います。PubGrubの目指す目標は、すべての依存関係が満たされることに加えて、競合が発生しないように、バージョンを選択することです。

そしてなんと、PubGrubには依存関係グラフ上の競合を回避しつつ依存関係を解決する強力な機能が備わっているのです。

PubGrubの依存関係解決アルゴリズム

本格的な解説に入る前に、PubGrubにおいてパッケージとそれらのバージョンがどのような形式で取り扱われているかを説明します。

これ以降の説明では以下の開発環境を想定して解説を進めていきます。
あなたは、何らかのアプリ（以後rootパッケージとします）を開発しており、それがmenuパッケージとiconsパッケージに依存しているとします。menuパッケージはdropdownパッケージに依存しており、さらに、dropdownパッケージもiconsパッケージに依存しています。

PubGrubでは"term"と呼ばれる特殊な単位が用いられます。termは個々のパッケージのバージョン範囲を表していて、それには要求するパッケージ(required)や互換性のないパッケージ(forbidden)が示されています。例えば、menu ≥ 1.1.0やnot dropdown ≥ 2.0.0はそれぞれtermとなります。

termは、選択されたパッケージのバージョンと一致する場合に成立します。例えば、menu ≥ 1.1.0は、menuのバージョンが1.1.0以上であれば良いので、menu 1.2.0が選択されても満たされますし、not dropdown ≥ 2.0.0であれば、dropdownのバージョンが2.0.0以上でなければ良いので、dropdown 1.8.0が選択された場合（またはdropdownのバージョンが一切選択されていない場合）にも満たされます。

PubGrubの非互換性

PubGrubでは非互換性という概念があります。異なるtermから構成されるセットにおいて、特定のtermが同時に満たされないようなセットを非互換性として定義します。

例えば、{menu ≥ 1.1.0, not dropdown ≥ 2.0.0} は、非互換性を示すセットです。このセットは、menuのバージョンが1.1.0以上で、dropdownのバージョンが2.0.0以上でないのなら、パッケージが成立しないということを示しています。これは同時に、menuパッケージがdropdown ≥ 2.0.0に依存していることを意味します。

このような非互換性の指定は、異なるパッケージのバージョンが競合するのを防いでくれます。

PubGrubの非互換性はセットで表される。例えば、
{hoge ≥ 2.0.0, fuga ≥ 1.0.0} は hoge ≥ 2.0.0 と fuga ≥ 1.0.0 を同時に満たすことができないことを示す。

また、非互換性は以下のようにパッケージが1つの場合でも適用される。例えば、
{hogehoge ≥ 2.0.0} は hogehoge の 2.0.0 以上のバージョンを選択してはいけないことを示す。

コアループ

コアループはPubGrubが依存関係を解決するための中核となる部分で、伝播フェーズと決定フェーズという2つのフェーズを交互に繰り返しながら、競合が起きることのないパッケージバージョンのリストを組み上げていきます。

初めの伝播フェーズでは、選択したパッケージバージョンのリストと、それらに対応する非互換性セットを組み合わせて、それぞれの条件が満たされるようなバージョンを探索します。例えば、menu 1.4.0を選択している場合、非互換性{menu ≥ 1.1.0, not dropdown ≥ 2.0.0}から、dropdown ≥ 2.0.0が必要だという条件が導かれます。

dropdown ≥ 2.0.0が導かれたら、このtermと非互換性{dropdown ≥ 2.0.0、not icons ≥ 2.0.0}を組み合わせてicons ≥ 2.0.0を導き出すことができます。
このようにtermが次々と導かれていき、最終的に導出できるものがなくなるまで続きます。

可能な限り導出をしたうえで、まだ条件が満たせていない依存関係のパッケージがある場合、次の決定フェーズに移ります。ここでは、条件を満たすことのできるバージョンを見つける作業が行われますが、基本的には最新のバージョンを選ぶことが多いです。

最終的に、すべてのパッケージの依存関係が解決されると、プロジェクトの実行が可能になります。
しかし、実際にはそう簡単に事が運ぶこともなく、特定のパッケージ間でなんらかの競合が起こってしまうことがほとんどです。
したがって、次に説明する衝突解決フェーズが必要になります。

衝突解決

伝播フェーズの過程で、定義済みの非互換性に抵触してしまう導出がなされることがあります。例えば、特定のパッケージからicons ≥ 2.0.0が導き出されてしまったとき、これはrootがもつ非互換性{root any, not icons < 2.0.0}(あらゆるバージョンのrootがインストールされているとき、iconsが2.0.0未満でないなら成立しないことを意味する)と衝突してしまいます。これを解決するため、PubGrubは衝突解決フェーズに移行します。

このフェーズでは、PubGrubは以前に選択されたパッケージバージョンに戻り、衝突の原因となったバージョンとは別のバージョンを検討します。これによって、PubGrubは衝突の根本原因を特定し、それを非互換性として新たに記録します。

PubGrubが新たな非互換性を生成するためには、「resolution」と呼ばれる論理的な導出ルールが活用されます。
このルールでは、「PまたはQ」および「Rまたはnot Q」の両方が真である時、「PまたはR」も真となります。非互換性の観点から言えば、これは{S、T}と{U、not T}が与えられた場合、{S、U}を導き出せるということになります。

「resolusion」は二つの条件から一つの新たな条件を「導出」する。例えば、
「P(偶数) または Q(10以下)」と「R(3の倍数) または notQ(10以下でない)」
が両方真のとき、
「P(偶数) または R(3の倍数)」
も必ず真といえる

このルールを実際に当てはめてみましょう。
まず、衝突を引き起こしたtermであるicons ≥ 2.0.0。これは元々、伝播フェーズの過程で非互換性{dropdown ≥ 2.0.0, not icons ≥ 2.0.0}から導出されていることがわかっています。

ここに、rootパッケージから定義されていた非互換性{root any, not icons < 2.0.0}を組み合わせることで、非互換性{root any, dropdown ≥ 2.0.0}が導かれます。このことから、rootがdropdown ≥ 2.0.0と互換性がないことが明らかになります。

┌─────────────────────────────────────┐ ┌─────────────────────────────┐
│{dropdown ≥ 2.0.0, not icons ≥ 2.0.0}│ │{root any, not icons < 2.0.0}│
└────────────┬────────────────────────┘ └──────────────┬──────────────┘
             │   ┌─────────────────────────────────────┘     
             ▼   ▼
┌────────────┴───┴───────────┐
│{root any, dropdown ≥ 2.0.0}│
└────────────────────────────┘

そして、dropdown ≥ 2.0.0は{menu ≥ 1.1.0, not dropdown ≥ 2.0.0}によって導出されていることがわかっています。

最終的に、{root any, dropdown ≥ 2.0.0}と{menu ≥ 1.1.0, not dropdown ≥ 2.0.0}
この二つの非互換性を組み合わせることで、{root any, menu ≥ 1.1.0}が定義されます。

┌─────────────────────────────────────┐ ┌─────────────────────────────┐
│{dropdown ≥ 2.0.0, not icons ≥ 2.0.0}│ │{root any, not icons < 2.0.0}│
└────────────┬────────────────────────┘ └──────────────┬──────────────┘
             │   ┌─────────────────────────────────────┘     
             ▼   ▼
┌────────────┴───┴───────────┐ ┌────────────────────────────────────┐
│{root any, dropdown ≥ 2.0.0}│ │{menu ≥ 1.1.0, not dropdown ≥ 2.0.0}│
└────────────┬───────────────┘ └──────────────────┬─────────────────┘
             │   ┌────────────────────────────────┘     
             ▼   ▼
┌────────────┴───┴───────┐
│{root any, menu ≥ 1.1.0}│
└────────────────────────┘

これでようやくrootパッケージではmenu 1.4.0は適さないということが判明したわけです。これを根本的な原因として、menu 1.4.0を選択する前まで戻り、伝播フェーズを再試行します。この際、これまでの過程で生まれた非互換性{root any, menu ≥ 1.1.0}を考慮することで、代わりにmenu 1.0.0を選択することができます。

PubGrubはこのように複数の非互換性を連鎖的に組み合わせていくことで、衝突の起こらないパッケージリストを作成することができるのです。

7. まとめ

パッケージ管理システムは、現代のソフトウェア開発において不可欠なツールであり、数々の優れた機能によって開発者やシステム管理者に多くの利点を提供しています。パッケージ管理、自動的な更新そして、依存関係のスムーズな解決など、これらの機能は作業の合理化とプロジェクトの安定性を確保する上で極めて重要です。

そして、我々がコマンドひとつでパッケージをインストールしている裏で、強力なアルゴリズムを利用して大量のパッケージの複雑な依存関係を解決しているのです。（本稿で紹介したもの以外にもOSやプログラム言語に応じた様々なアルゴリズムが利用されています！）

最後に、この記事があなたがパッケージ管理システムを理解する一助となってくれれば幸いです。

弊社Nucoでは、他にも様々なお役立ち記事を公開しています。よかったら、Organizationのページも覗いてみてください。
また、Nucoでは一緒に働く仲間も募集しています！興味をお持ちいただける方は、こちらまで。