リゾルバの内部
Tip
このドキュメントは、uvのリゾルバの内部動作に焦点を当てています。uvの使用方法については、 解決の概念のドキュメントを参照してください。
リゾルバ
教科書で定義されているように、解決、つまり与えられた要件セットからインストールするバージョンセットを見つけることは、 SAT問題と同等であり、したがってNP完全です。 最悪の場合、すべてのパッケージのすべてのバージョンのすべての組み合わせを試す必要があり、一般的で高速なアルゴリズムはありません。 実際には、これはいくつかの理由で誤解を招きます。
- uvの解決の最も遅い部分は、パッケージとバージョンのメタデータを読み込むことです。キャッシュされていても同様です。
- 多くの解決策が存在しますが、いくつかは他のものよりも好まれます。たとえば、一般的には最新バージョンのパッケージを使用することを好みます。
- パッケージの依存関係は複雑です。たとえば、連続したバージョン範囲があり、任意のブール値のバージョンの包含/除外ではなく、隣接するリリースは同じまたは類似の要件を持つことがよくあります。
- ほとんどの解決では、リゾルバはバックトラックする必要がなく、バージョンを反復的に選択するだけで十分です。以前の解決からのバージョンの優先順位がある場合、ほとんど作業は必要ありません。
- 解決が失敗した場合、SATソルバーで見られるように、解決策がないというメッセージ以上の情報が必要です。代わりに、リゾルバは、ユーザーが競合を削除できるように、どのパッケージが関与しているかを理解できるエラートレースを生成する必要があります。
uvは、インクリメンタルバージョンソルバーであるPubGrubのRust実装であるpubgrub-rsを使用します。uvのPubGrubは次の手順で動作します。
- 選択されたパッケージバージョンと未決定のパッケージを宣言する部分的な解決から開始します。最初は、仮想ルートパッケージのみが決定されます。
- 未決定のパッケージから最も優先度の高いパッケージが選択されます。URLを持つパッケージ（ファイル、gitなどを含む）が最も優先され、次により正確な指定子（
==など）を持つもの、次にあまり厳しくない指定子を持つものが優先されます。各カテゴリ内では、パッケージは最初に見られた順序（ファイル内の順序）で並べられ、解決が決定的になります。 - 選択されたパッケージのバージョンが選択されます。バージョンは、部分的な解決の要件からのすべての指定子と互換性があり、以前に非互換としてマークされていない必要があります。リゾルバは、ロックファイル（
uv.lockまたは-o requirements.txt）および現在の環境にインストールされているものからのバージョンを優先します。バージョンは、最高から最低までチェックされます（代替の解決戦略を使用していない限り）。 - 選択されたパッケージバージョンのすべての要件が未決定のパッケージに追加されます。uvはパフォーマンスを向上させるためにバックグラウンドでメタデータをプリフェッチします。
- プロセスは次のパッケージで繰り返されるか、競合が検出されるとリゾルバがバックトラックします。たとえば、部分的な解決には、他のパッケージの中に
a 2とb 2が含まれ、要件a 2 -> c 1とb 2 -> c 2があります。互換性のあるバージョンのcが見つかりません。PubGrubは、これがa 2とb 2によって引き起こされたことを判断し、非互換性{a 2, b 2}を追加します。これは、いずれかが選択された場合、他方は選択できないことを意味します。部分的な解決はa 2に戻され、追跡された非互換性があり、リゾルバはbの新しいバージョンを選択しようとします。
最終的に、リゾルバはすべてのパッケージに互換性のあるバージョンを選択するか（成功した解決）、ユーザーが要求したバージョンを定義する仮想「ルート」パッケージを含む非互換性があります。ルートパッケージとの非互換性は、ルート依存関係とその推移的依存関係のバージョンが選択されると、常に競合が発生することを示します。PubGrubで追跡された非互換性から、関与するパッケージを列挙するエラーメッセージが構築されます。
Tip
PubGrubアルゴリズムの詳細については、PubGrubアルゴリズムの内部を参照してください。
フォーキング
Pythonのリゾルバは歴史的にバックトラックをサポートしておらず、バックトラックをサポートしていても、解決は通常、特定のアーキテクチャ、オペレーティングシステム、Pythonバージョン、およびPython実装を持つ単一の環境に限定されていました。一部のパッケージは、異なる環境に対して矛盾する要件を使用します。たとえば：
Pythonは各パッケージの1つのバージョンのみを許可するため、単純なリゾルバはここでエラーを発生させます。 Poetryに触発されて、uvはフォーキングリゾルバを使用します。 異なるマーカーを持つパッケージに複数の要件がある場合、解決は分割されます。
上記の例では、部分的な解決はpython_version >= "3.11"用とpython_version < "3.11"用の2つの解決に分割されます。
マーカーが重複しているか、マーカースペースの一部が欠けている場合、リゾルバは追加の分割を行います。 パッケージごとに多くのフォークが存在する可能性があります。たとえば、次のような場合です。
sys_platform == 'darwin'、sys_platform == 'win32'、およびsys_platform != 'darwin' and sys_platform != 'win32'のフォークが作成されます。
フォークはネストできます。つまり、各フォークは発生した以前のフォークに依存します。 同一のパッケージを持つフォークは、フォークの数を少なくするためにマージされます。
Tip
uv lock -vのログでSplitting resolution on ...、Solving split ... (requires-python: ...)、およびSplit ... resolution took ...を探すことで、フォーキングを観察できます。
フォーキングリゾルバの難しさの1つは、分割が発生する場所がパッケージの順序に依存することです。
これは、uv.lockからの優先順位に依存します。
したがって、リゾルバが特定のフォークで要件を解決し、これをロックファイルに書き込み、リゾルバが再度呼び出されると、優先順位が異なるフォークポイントをもたらすため、異なる解決が見つかる可能性があります。
これを回避するために、各フォークの解決マーカーとフォーク間で分岐する各パッケージがロックファイルに書き込まれます。
新しい解決を行う際には、ロックファイルからのフォークが使用され、解決が安定するようにします。
要件が変更されると、新しいフォークが保存されたフォークに追加される場合があります。
requires-python
requires-python = ">=3.9"を持つ解決が含まれるPythonバージョンに実際にインストールできることを確認するために、uvはすべての依存関係が同じ最小Pythonバージョンを持つことを要求します。
requires-python = ">=3.10"のように、より高い最小Pythonバージョンを宣言するパッケージバージョンは拒否されます。
これは、そのバージョンを持つ解決がPython 3.9にインストールできないためです。
簡単さと将来の互換性のために、requires-pythonの下限のみが尊重されます。
たとえば、パッケージがrequires-python = ">=3.8,<4"を宣言している場合、<4マーカーは解決全体に伝播されません。
ホイールタグ
uvの解決は環境マーカーに関して普遍的ですが、これはホイールタグには拡張されません。
ホイールタグは、Pythonバージョン、Python実装、オペレーティングシステム、およびアーキテクチャをエンコードできます。
たとえば、torch-2.4.0-cp312-cp312-manylinux2014_aarch64.whlは、arm64 Linux上のCPython 3.12とglibc>=2.17（manylinux2014ポリシーによる）にのみ互換性がありますが、
tqdm-4.66.4-py3-none-any.whlは、任意のオペレーティングシステムおよびアーキテクチャ上のすべてのPython 3バージョンおよびインタープリタと互換性があります。
ほとんどのプロジェクトには、互換性のあるソースディストリビューションがあり、互換性のないホイールを持つパッケージをインストールしようとする場合に使用できますが、
torchのような一部のパッケージはソースディストリビューションを公開していません。
この場合、たとえばPython 3.13、一般的でないオペレーティングシステム、またはアーキテクチャでのインストールは失敗し、互換性のあるホイールがないと文句を言います。