依存関係解決の詳細¶
この記事では、pip の依存関係解決アルゴリズムについてより詳細に説明します。特定の状況では、pip がインストール対象を決定するのに時間がかかることがあり、この記事は、そのプロセス中に「舞台裏」で何が起こっているかを理解するのに役立つことを目的としています。
注記
このドキュメントは現在作成中です。含まれる詳細は正確ですが（執筆時点）、特に resolvelib との pip のインターフェースに関する追加情報はまだ含まれていません。
このドキュメントの改善への貢献は大歓迎です。
依存関係解決の問題¶
パッケージ間の依存関係のセットを考慮して、インストールするパッケージのセットを見つけるプロセスは、NP困難問題として知られています。実際には、これは、問題のサイズが増加するにつれて、プロセスが非常に悪化するという意味です。したがって、多くの依存関係がある場合、最悪の場合、インストール対象を判断するのに非常に時間がかかります。
その実際的な意味は、pip が妥当な時間内にインストール対象を決定できない状況が常に存在するということです。そのような状況がめったに発生しないように最善を尽くしていますが、完全に排除することは理論上も不可能です。このような問題が発生した場合の対処方法については、後で少し説明します。
Python 固有の問題¶
依存関係解決を処理するための多くのアルゴリズムは、最初に問題の完全な詳細を知っていることを前提としています。つまり、すべての依存関係を事前に知っているということです。残念ながら、Python パッケージの場合、これは当てはまりません。現在のパッケージインデックス構造では、依存関係メタデータはパッケージファイルをダウンロードしてそのデータを取り出すことによってのみ利用できます。そして、ソース配布物では、依存関係を決定するためにダウンロード後にプロジェクトをビルドする必要があるため、状況はさらに悪化します。
メタデータをより低コストで容易に利用できるようにするための作業は進行中ですが、執筆時点では完了していません。
プロジェクトのダウンロードはコストのかかる操作であるため、pip は完全な依存関係ツリーを事前に計算できません。これは、依存関係解決問題を解決するための多くの手法を使用できないことを意味します。実際には、バックトラッキングアルゴリズムを使用する必要があります。
依存関係メタデータ¶
パッケージ解決プロセスを駆動するために正確にどのようなメタデータが必要であるかについて説明する価値があります。基本的に3つの重要な情報があります。
プロジェクト名
リリースバージョン
依存関係自体
その他にもデータ（例：エクストラ、Python バージョン制限、ホイール互換性タグ）が使用されますが、プロセスは基本的に変更されないため、ここでは無視します。
最も重要な情報は、プロジェクト名とバージョンです。これら2つの情報は、インストールの個々の「候補」を識別し、そのような候補を一意に識別する必要があります。候補オブジェクトが作成された時点から、名前とバージョンを利用可能にする必要があります。このことは、配布ファイル（sdist とホイール）の場合、そのデータはファイル名から取得できるため問題ではありませんが、パッケージ化されていないソースツリーの場合、pip はそのデータを取得するためにビルドバックエンドを呼び出す必要があります。これは、適切な解決が開始される前に実行されます。
依存関係データは事前に要求されません（前述のように、そうすると非常にコストがかかり、バックトラッキングアルゴリズムでは必要ありません）。代わりに、pip はアルゴリズムが特定の候補をチェックし始めると「オンデマンド」で依存関係データを要求します。
依存関係データの遅延フェッチングの1つの特別な意味は、多くの場合、pip が依存関係ツリー全体を人間が見ると明らかなことを知らないということです。たとえば、パッケージAがパッケージBのバージョン1.0に依存する場合、人間にとって、パッケージBの他のバージョンを探す意味はないことは明らかです。しかし、pip がAを考慮する前にBを調べ始めた場合、Aの依存関係データにアクセスできず、Bの他のバージョンを調べることは無駄な作業であると知る方法がありません。さらに悪いことに、pip はAの依存関係に重要な情報があることさえ知りません。
この最後の点は、pip が解決を完了するのに時間がかかる多くのケースにおける一般的なテーマです。pip が「間違った」選択を行う時点で、pip が知らない情報があります。アルゴリズムをガイドするためにリゾルバーに追加されたヒューリスティックのほとんどは、その知識の欠如に直面して正しく推測するように設計されています。
リゾルバーとファインダー¶
これまでのところ、「リゾルバー」を単一のエンティティとして説明してきました。それはほとんど正しいですが、インデックスからパッケージデータを取得するプロセスは、pip の別のコンポーネントである「ファインダー」によって処理されます。ファインダーは、候補をリゾルバーに供給する役割を担い、適切な候補を選択する上で重要な役割を果たします。
リゾルバーは、インデックスからフェッチされたパッケージにのみ関連していることに注意してください。他のソース（ローカルソースディレクトリ、直接 URL 参照）から取得された候補は、ファインダーを通過せず、リゾルバーの「プロバイダー」実装の一部として、ファインダーによって提供された候補とマージされます。
ファインダーは、特定のプロジェクトのインデックスにどのようなバージョンが存在するかを決定するだけでなく、その候補に使用する最適な配布ファイルを選択します。これはホイールまたはソース配布物である可能性があり、正確に何が選択されるかは、ホイール互換性タグ、pip のオプション（バイナリまたはソースを優先するかどうか）、インデックスによって提供されるメタデータによって制御されます。特に、ファイルが特定の Python バージョンのみを対象としてマークされている場合、そのファイルはファインダーによって無視され（そしてリゾルバーはそのバージョンを見ることさえできません）、ます。
ファインダーは、優先順位に従ってプロジェクトの候補をリゾルバーにも提供します。たとえば、プロバイダーは、より新しいバージョンを古いバージョンよりも優先するというルールを実装します。
リゾルバーアルゴリズム¶
リゾルバー自体は、別のパッケージであるresolvelibに基づいています。これは、Python パッケージの具体的な内容とは独立した方法で、抽象的なバックトラッキング解決アルゴリズムを実装します。それらの具体的な内容は、リゾルバーを呼び出す前に pip によって抽象化されます。
resolvelib への pip のインターフェースは、「プロバイダー」という形式であり、これは pip のパッケージモデルと解決アルゴリズム間のインターフェースです。プロバイダーは「候補」と「要件」を扱い、次の操作を実装します。
identify- 候補と要件のアイデンティティを実装します。たとえば、候補が名前とバージョンによって識別されるというルールを実装するのはこの操作です。get_preference- 解決プロセスを進める際にどの要件を「次に」調べるかをリゾルバーが選択するのに役立つ情報をリゾルバーに提供します。find_matches- 制約条件のセットを基に、それらを満たす候補が存在するかどうかを判断します。これは基本的に、ファインダーがリゾルバーとやり取りする場所です。is_satisfied_by- 候補が要件を満たすかどうかをチェックします。これは基本的に、要件の意味を実装したものです。get_dependencies- 候補の依存関係のメタデータを取得します。これは、パッケージメタデータの取得と読み取りのプロセスを実装したものです。
これらのメソッドのうち、非自明なのはget_preferenceメソッドだけです。これは、解決を導くために使用されるヒューリスティックを実装し、次にどの要件を満たそうとするかを指示します。このメソッドは、依存関係ツリーのどのルートが最も生産的かを推測しようとします。前述のように、これは限られた情報で行われます。次の図を参照してください。
プロバイダーに赤い要件（A->BとA->C）の選択が求められた場合、BまたはCの依存関係（グラフの灰色の部分）については何も知りません。
Pipの現在のプロバイダーの実装では、get_preferenceは次のように実装されています。
既知の要件のいずれかが「直接的」である場合（例：明示的なURLを指す場合）を優先します。
同等の場合、要件のいずれかが「ピン留めされている」場合（つまり、演算子
===または==を含む場合）を優先します。同等の場合、概算の「深さ」を計算し、ユーザー指定の要件により近い要件を最初に解決します。
ユーザー指定の要件を、指定された順序で並べ替えます。
同等の場合、「非フリー」の要件（つまり、
>=や<などの演算子を少なくとも1つ含む）を優先します。同等の場合、一貫性のためにアルファベット順に並べ替えます（デバッグ可能性を高めます）。