Skip to content

Resolver internals#

Tip

このドキュメントでは、uvのリゾルバの内部動作に焦点を当てています。uvの使用については、resolution conceptのドキュメントを参照してください。

Resolver#

テキストブックで定義されているように、解決、または特定の要件セットからインストールするバージョンセットを見つけることは、SAT problemと同等であり、したがって NP 完全である:最悪の場合、すべてのパッケージのすべてのバージョンのすべての可能な組み合わせを試す必要があり、一般的で高速なアルゴリズムは存在しない。実際には、これはいくつかの理由で誤解を招きます。

  • uv の解像度で最も遅い部分は、キャッシュされていても、パッケージとバージョンのメタデータをロードすることです。
  • 可能な解決策はたくさんありますが、いくつかは他よりも好ましいものです。例えば、私たちは一般的に最新バージョンのパッケージを使用することを好みます。
  • パッケージの依存関係が複雑です。例えば、連続したバージョン範囲がある-任意のブール値によるバージョンの包含/除外ではない、隣接するリリースはしばしば同一または類似の要件を持つ、など。
  • ほとんどの解決では、リゾルバはバックトラックする必要がなく、バージョンを繰り返し選択するだけで十分です。以前の解決からのバージョン設定がある場合、ほとんど作業を行う必要はありません。
  • 解決が失敗した場合、(SAT ソルバで見られるように)解決がないというメッセージよりも多くの情報が必要になります。その代わりに、リゾルバは、ユーザが競合を取り除くことができるように、どのパッケージが関係しているかを示す理解可能なエラートレースを生成する必要があります。

uv はPubGrub-rsを使用しており、これはPubGrubの Rust 実装であり、インクリメンタルバージョンソルバーです。uv の PubGrub は次のステップで動作します。

  • どのパッケージのバージョンが選択され、どのバージョンが未決定であるかを宣言する部分的なソリューションから開始します。最初は、仮想ルートパッケージのみが決定されます。
  • 未決定のパッケージの中から、最も優先度の高いパッケージが選択されます。URL(file、git などを含む)を持つパッケージが最も優先度が高く、より正確な指定子(==など)を持つパッケージが最も優先度が高く、より厳密でない指定子を持つパッケージが最も優先度が低くなります。各カテゴリ内では、パッケージは最初に表示されたとき(つまり、ファイル内の順序)によって順序付けられ、解決が決定的になります。

  • 選択したパッケージのバージョンが選択されます。バージョンは、部分的なソリューションの要件からのすべての指定子で動作する必要があり、以前に互換性がないとマークされていてはなりません。リゾルバは、ロックファイル(uv.lockまたは-o requirements.txt)のバージョンと、現在の環境にインストールされているバージョンを優先します。バージョンは、(代替のresolution strategyを使用しない限り)高いものから低いものへとチェックされます。

  • All requirements of the selected package version are added to the undecided packages. uv prefetches their metadata in the background to improve performance.

  • 選択したパッケージバージョンのすべての要件が、未決定のパッケージに追加されます。uv は、パフォーマンスを向上させるために、バックグラウンドでメタデータをプリフェッチします。

-このプロセスは、競合が検出されない限り、次のパッケージで繰り返されます。競合が検出されると、リゾルバはバックトラックします。たとえば、部分的なソリューションには、他のパッケージの中でもa 2が含まれ、次にa 2 -> c 1とb 2 -> c 2という要件を持つb 2が含まれます。cの互換性のあるバージョンが見つかりません。PubGrub は、これがa 2とb 2によって引き起こされたと判断し、非互換性{a 2, b 2}を追加します。これは、どちらかが選択された場合、もう一方は選択できないことを意味します。部分的なソリューションは、追跡された非互換性を持つa 2に復元され、リゾルバはbの新しいバージョンを選択しようとします。

最終的に、リゾルバはすべてのパッケージに対して互換性のあるバージョンを選択するか(解決の成功)、ユーザーが要求したバージョンを定義する仮想「ルート」パッケージを含む非互換性が存在するかのいずれかになります。ルートパッケージとの非互換性は、ルート依存関係とその推移的依存関係のバージョンが選択されても、常に競合が存在することを示します。PubGrub で追跡された非互換性から、関連するパッケージを列挙するためのエラーメッセージが構築されます。

Tip

PubGrubアルゴリズムの詳細については、Internals of the PubGrub algorithmを参照してください。

Forking#

Python リゾルバはこれまでバックトラックをサポートしておらず、バックトラックを使用しても、解決は通常、特定のアーキテクチャ、オペレーティングシステム、Python バージョン、および Python 実装を含む単一の環境に限定されていました。一部のパッケージでは、次のように異なる環境に対して矛盾した要件が使用されています。

numpy>=2,<3 ; python_version >= "3.11"
numpy>=1.16,<2 ; python_version < "3.11"

Python では各パッケージに対して 1 つのバージョンしか許可されていないため、単純なリゾルバではここでエラーが発生します。Poetryに触発されて、uv はフォークリゾルバを使用しています : 異なるマーカーを持つパッケージに対して複数の要件がある場合は常に、解像度が分割されます。

上記の例では、部分的なソリューションは 2 つの解像度に分割されます。1 つはpython_version >= "3.11"用で、もう 1 つはpython_version < "3.11"用です。

マーカーがオーバーラップしたり、マーカー空間の一部が欠落している場合、リゾルバはさらに分割します。パッケージごとに多数のフォークが存在する可能性があります。次に例を示します:

flask > 1 ; sys_platform == 'darwin'
flask > 2 ; sys_platform == 'win32'
flask

フォークは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 taken ...を探すことで確認できます。

分岐リゾルバにおける 1 つの問題は、分割が発生する場所が、見られるパッケージの順序に依存し、次に、例えばuv.lockからの選好に依存することです。したがって、リゾルバが特定のフォークで要件を解決し、これをロックファイルに書き込むことが可能であり、リゾルバが再度呼び出されると、選好が異なるフォークポイントをもたらすため、異なる解が見つかります。これを回避するために、各フォークとフォーク間で分岐する各パッケージのenvironment-markersがロックファイルに書き込まれます。新しい解決を実行する場合、ロックファイルからのフォークを使用して、解決が安定していることを確認します。要件が変更されると、保存されたフォークに新しいフォークが追加されることがあります。

Requires-python#

含まれている Python バージョンに対してrequires-python = ">=3.9"の解像度を実際にインストールできるようにするために、uv はすべての依存関係が同じ最小 Python バージョンを持つことを要求します。requires-python= ">=3.10"のように、より高い最小 Python バージョンを宣言するパッケージバージョンは、そのバージョンの解像度を Python 3.9 にインストールできないため、拒否されます。単純化と上位互換性のために、requires-pythonの下限のみが尊重されます。たとえば、パッケージがrequires-python = ">=3.8,<4"と宣言した場合、<4マーカーは解像度全体には伝播されません。

Wheel tags#

uv の解像度は環境マーカーに関しては普遍的ですが、これは wheel タグには拡張されません。wheel タグは、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 バージョンとインタプリタで動作します。ほとんどのプロジェクトには、互換性のある wheel を持たないパッケージをインストールしようとしたときに使用できる、普遍的に互換性のあるソースディストリビューションがありますが、torchのようにソースディストリビューションを公開しないパッケージもあります。この場合、例えば Python 3.13、一般的でないオペレーティングシステム、またはアーキテクチャでのインストールは失敗し、一致する wheel がないと警告します。