新しい APT 3.0 ソルバー

APT 2.9.3 では、コード名solver3 という新しいソルバーの最初のイテレーションが導入されており、-solver 3.0 オプションで利用できるようになりました。 新しいソルバーは、古いソルバーとは根本的に動作が異なります。

どのように機能するのでしょうか?

Solver3 は、選択を可能な限り遅らせる完全にバックトラッキングな依存関係解決アルゴリズムです。 空のパッケージ セットから開始され、手動でインストールされたパッケージが追加され、依存関係を満たすために必要に応じてパッケージが自動的にインストールされます。

選択の延期は複数の方法で実装されます。

まず、すべてのインストール要求は、単一のインストール ソリューションを使用して依存関係を再帰的にマークします。また、競合またはユーザー要求により拒否されたパッケージは、そのパッケージまたはグループが別のソリューションで解決できない場合、その逆の依存関係が推移的に拒否されたものとしてマークされます。パッケージ。

次に、複数の選択肢を持つ依存関係は、考えられる解決策の数で順序付けされた優先キューにプッシュされ、a|b|c の前に a|b が解決されます。

ない ただ ただし、解の数によって異なります。 注意すべき重要な点の 1 つは、オプションの依存関係、つまり推奨は常に必須の依存関係の後に並べ替えられることです。 以下の点に注意してください: 推奨パッケージはバックトラッキングで「ネスト」しません。推奨パッケージ自体の依存関係はオプションではないため、次の推奨パッケージがキューに表示される前に依存関係を解決する必要があります。

選択を先送りするためのもう 1 つの重要な手順は、パッケージのバージョン全体にわたって共通の依存関係を抽出し、どのバージョンをインストールするかを決定する前にそれらをインストールすることです。結局、依存関係の 1 つが特定のバージョンに戻る可能性があります。

パッケージ レベルに関する決定は、特定の決定レベルで記録されます。競合に達した場合は、前の決定レベルに戻り、行った決定 (X をインストール) を逆にマークし (X をインストールしない)、すべての状態をリセットします。より高いレベルで作成され、解決されなくなった依存関係を作業キューに復元します。

SAT ソルバー設計との比較。

SAT ソルバーの設計を学習したことがある場合は、これが本質的に純粋な文字通りの消去を行わない DPLL ソルバーであることがわかるでしょう。 純粋なリテラルの削除フェーズは、パッケージ マネージャーでは機能しません。まず、否定的な純粋なリテラル (すべてが競合するパッケージ) は存在しません。また、肯定的な純粋なリテラル (何も競合しないパッケージ) は、インストール用にマークしたくありません。インストールはできるだけ少なくしてください (ポリシーに応じて異なります)。

解決フェーズの一環として、部分的ではありますが、含意グラフも作成します。別のパッケージをインストールする最初のパッケージが理由としてマークされます (A -> B)。競合の場合も同様です (A ではなく B ではありません)。 。

含意グラフに複数の親を持つ機能を追加したら、より高度な競合駆動型の節学習方法も実装できるのは当然です。 ここでは、前の意思決定レベルに戻るのではなく、競合を引き起こした意思決定レベルに正確に戻ります。 これにより、後戻りが大幅に高速化されます。

行動にどのような変化が期待できますか?

従来の APT ソルバーとの最も顕著な違いは、ソルバー 3 は手動でインストールされたパッケージを常に保持し、削除を提案しないことです。 今後のイテレーションではこれを緩和して、 交換する パッケージを新しいパッケージと置き換えます。つまり、パッケージがリポジトリで利用できなくなった (廃止された) が、競合 + 置換 + 提供するパッケージが存在する場合、solver3 はそれをインストールし、もう 1 つのパッケージを削除できます。

このポリシーの実装は非常に簡単です。キューに入れるだけで済みます。 obsolete | replacement
古いパッケージをインストール対象としてマークするのではなく、解決すべき依存関係として使用します。

もう 1 つの重要な違いは、自動削除動作の変更です。新しいソルバーは現在、各パッケージへの最も強い依存関係チェーンのみを認識しているため、より弱いチェーン経由でのみ到達可能なパッケージを回避しません。 一般的な例は次のような場合です gcc- パッケージは何年にもわたってシステムに蓄積されます。 彼らは皆持っています Provides: c-compiler そしてその libtool Depends: gcc | c-compiler

それらを手元に置いておくには十分です。

新しいオプション --no-strict-pinning 候補バージョンだけでなく、パッケージのすべてのバージョンを考慮するようにソルバーに指示します。 たとえば、次のように使用できます apt install foo=2.0 --no-strict-pinning
foo のバージョン 2.0 をインストールし、必要に応じてパッケージをアップグレードまたはダウングレードします。 foo=2.0 依存関係。 これは主に、Debian の実験的ポケットや Ubuntu が提案したポケットに関連するユースケースで役立ちます。そこからパッケージをインストールしたいが、できる限り通常のリリースで満足するように努めます。

含意グラフの構築により、 apt why このコマンドは、aptitude ほど詳しくはありませんが、少なくともパッケージがインストールされる正確な理由を示します。 もちろん、それが記録されるものであるため、最初は最も強い依存関係チェーンのみが表示されます。

やるべきことは何でしょうか？

現時点では、エラー情報はバックトラッキングを介して一切保存されませんが、通常は、最も自然な競合であるため、最初に到達した競合を示したいと思います。 またはすべての衝突。 現在、最後の競合が発生しますが、これは特に役に立たない可能性があります。

同様に、現在、エラーは単に次の形式の含意グラフとしてレンダリングされます。 [not] A -> [not] B -> ...それらをうまく表示するには、いくつかの作業を行う必要があります。

テストスイートはまだ合格していないので、実際に作業を始めていません。 課題は、テスト スイート内のほとんどのパッケージがモック化されるときに手動でインストールされ、ソルバーがそれらを削除しないことです。

foo を次のように置き換えることができるような置換ロジックを実装する予定です。 foo2 Conflicts/Replaces/Provides foo
自動的にインストールされる必要はありません。

バックトラッキングを非時系列の競合主導型の条項学習に改善すると、バックトラッキングのパフォーマンスが大幅に向上します。 私の限られたテスト (主に高貴な 64-bit-time_t アップグレード) では、現時点では問題ないようです。 手動でインストールされたパッケージとその結果として生じるユニットの伝播 (単一ソリューションの依存/競合に対する逆依存) により、実際にどのような変更を加えることができるかがすでにかなり明確になっているため、通常はそのような複雑さの多くは存在しません。

すべてのものが完成したら、展開を開始してフィードバックを収集する必要があります。 Ubuntu では、リグレッションに関する自動フィードバックが必要です (ソルバー 3 を並行して実行し、結果が悪くなっているかどうかを確認してからエラー トラッカーにエラーを送信します)。Debian では、これは単にソルバー ダンプの送信先となる役割の電子メール アドレスになる可能性があります。

同時に、これを段階的に展開し始めることもできます。 Ubuntu の段階的なアップデートと同様に、完全に 100% になる前に、新しいソルバーをデフォルトとしてユーザーの 10%、20%、50% にロールアウトすることもできます。 これにより、リグレッションを早期に検出して修正できるようになります。