今日、どこからともなく: 単位伝播、論理スキーム、競合駆動学習などのように聞こえる用語を使用して、他のバージョンのソリューションよりも高速に実行され、バグが少ないソリューションアルゴリズムの新しいバージョンです。現在、 統合され、Dart 2.0.0-dev.44.0でリリースされています。このアルゴリズムが、いつかすべてのプログラミング言語に恩恵をもたらすことを願っています。
まず、バージョニングとは何を意味するのでしょうか？
パッケージマネージャは、現代のプログラミング言語にとって重要な部分です。これは、アプリケーションの依存関係、依存関係の依存関係を、すべての依存関係が満たされるまでフェッチできるツールです。パッケージマネージャの中心はバージョン管理アルゴリズムであり、各パッケージのバージョンがすべての依存関係を満たすようにインストールされることを保証します。
残念ながら、良いバージョンの解アルゴリズムを構築するのは本当に難しい。非アルゴリズム研究者にとって、効率的なアルゴリズムの存在は、コンピュータサイエンスにおける主要な未解決問題の1つです。
あなたのアプリがメニューパッケージの最新バージョン1.5.0に依存し、dropdown >= 2.0.0に依存しているとします。その場合、アルゴリズムは、可能な限り最高のバージョンであるdropdown 2.2.0を試すかもしれません。ドロップダウン2.1.0と2.0.0の間でも、同じ問題が発生することがあります。
次のステップは、menu 1.4.0を試して、要件を満たしているかどうかを確認することです。 solverは再びドロップダウンの全バージョンを繰り返し、動作するかどうかを確認しますが、答えはノーです。最終的にsolverはmenu 1.1.0とdropdown 1.8.0にロックします。これは、このバージョンの組み合わせがアプリと互換性があることを意味します。 このプロセスに戻ると、メニューの繰り返しで1つのバージョン、ドロップダウンの繰り返しで1つのバージョンというように、多くの繰り返しがあります。バージョンが多ければ、さらに繰り返しがあるかもしれません。
当面は、「ドロップダウンが使えない問題は解決したので、このバージョンを再度チェックする必要はありません。しかし、問題はそれほど単純ではありません。どのパッケージのどのバージョンも、他のパッケージに依存している可能性があります。つまり、あるパッケージの異なるバージョンを選択するときはいつでも、他のすべてのパッケージの依存関係を考慮しなければなりません。これは、パッケージの依存関係を解く時間を指数関数的に増大させることになります。
ではPubGrubは何をするのでしょうか？
シートベルトを着用してください！用語とはPubGrubの作業の最も基本的な単位で、あるパッケージに対して必要または禁止されるバージョンの範囲です。例えば、menu >= 1.1.0は項であり、dropdown >= 2.0.0も項ではありません。もしmenu 1.2.0が選択されていれば、menu >= 1.1.0、dropdown 1.8.0が選択されていれば、dropdown >= 2.0.0ではありません。
非互換性を使用して、1回限りの要件を満たさない用語のセットを定義します。つまり、パッケージがすべての用語を一度に満たす場合、そのパッケージは有効なソリューションの一部ではないことが知られています。非互換性を使用して、パッケージ間の依存関係を表します。{menu >= 1.1.0 not dropdown >= 2.2.0} たとえば、非互換性は、menu >= 1.1.0 のバージョンが選択された場合、それは無効であり、dropdown のバージョンは >= 2.0.0 ではないことを意味します。言い換えれば、menu >= 1.1.0 は dropdown >= 2.0.0 に依存します。
外部コンテキストに関係なく、非互換性の条件は非互換であり、PubGrubは何度も作業を繰り返すことを避けるために使用することができます。上の例のようにパッケージの依存関係を表す非互換性を生成するのは簡単ですが、既存の条件から新しい非互換性を生成できることも望ましいです。ドロップダウンに初めて遭遇したときに、{dropdown >= 2.0.0}の非互換性から非互換性を生成できれば、多くの冗長な作業を省くことができます。
これが "conflict-driven clause learning "の節学習です。手始めに "conflict "の部分を見てみましょう。"conflict "は実行中のPubGrubのコアループに由来します。
コア・ループ
ほとんどの場合、PubGrubはパッケージのバージョンセットで使用するパッケージバージョンの暫定セットを生成しながら、2つのフェーズを交互に繰り返します。
第一段階は「ユニットパッシング」で、選択されたパッケージバージョンのセットと非互換性のセットを組み合わせて、選択されたパッケージバージョンから真となる用語のセットを見つけます。{menu >= 1.1.0, not dropdown >= 2.0.0}例えば、menu 1.4.0が選択されている場合、.NET Framework 2.0.0に基づいてドロップダウンが>=2.0.0かどうかを確認することができます。
生成された用語は、ユニットデリバリフェーズにも入力されます。 {dropdown >= 2.0.0, not icons >= 2.0.0} ドロップダウン >= 2.0.0が生成されると、非互換性からアイコン >= 2.0.0が推測されます。 この推測は新しいものが生成されなくなるまで続きます。この時点でPubGrubは2番目のフェーズに入ります。
第二段階は決定生成で、通過するユニットがもうないけれども、依存関係が解 決されていないときに発生します。この時点で、特定のパッケージの特定のバージョンが選択され、 パッケージのバージョンリストに追加されます。上で推論されたすべての条件を満たすバージョンが動作するものですが、 パッケージマネージャが特定のパッケージの最新バージョンを選択したいことも よくあります。
これは PubGrub が新しいパッケージの依存関係を示すために非互換性を追加する場所でもあります。すべてのパッケージの依存関係を最初に追加するのではなく、パッケージがパースされたときに不活性に読み込むことが重要です。
すべてがうまくいけば、コアループはすべてのパッケージの依存関係を満たすパッケージのバージョンセットを見つけ、ユーザーはコードを実行し始めることができます。しかし、私たちは常にすべてがスムーズにいく世界に生きているわけではありません。
紛争解決
{root any, not icons < 2.0.0}ユニットデリバリフェーズで、PubGrubが特定の非互換性に基づいてすべての用語を満たす用語を生成することがあります。 たとえば、ルートパッケージのバージョン（アイコンに依存する）と一致するicon >= 2.0.0に基づいて新しい用語を生成する場合。これは競合を引き起こし、それを解決するために3番目のステージをトリガーします。
現代のバージョン管理ソリューションでは、コンフリクトの解決策はコンフリクトを引き起こした可能性のあるバージョンにジャンプバックして別のバージョンを試すことです。 PubGrubは同じことをしますが、コンフリクトの原因を見つけて互換性がないものとしてマークします。PubGrubは同じことをしますが、コンフリクトの原因を見つけ、互換性がないものとしてマークします。 この互換性がないことは、ユニットパスの段階で同じコンフリクトが何度も発生するのを防ぐのに役立ちます。
競合の原因は、既知の論理ルールと非互換性を継続的に組み合わせることで生成されます。ルールとは、"P or Q "と "R or not Q "の両方が真であれば、"P or R "も真であるというものです。 非互換性については、{U, S}は既知の{S,T}と{U, not T}から導くことができます。
{root any, not icons < 2.0.0} {dropdown >= 2.0.0, not icons >= 2.0.0}コンフリクトの原因となった非互換性と、すでに派生している用語(icons >= 2.0.0、.から派生)を組み合わせることから始めます。を組み合わせます。 {root any, dropdown >= 2.0.0}すなわち、ルートパッケージは、 >= 2.0.0のドロップダウンと互換性がありません。
{menu >= 1.0.0, not dropdown >= 2.0.0} 次に、一致する最近派生した用語と組み合わせてください（例：dropdown >= 2.0.0は.から派生しました）。組み合わせ。 {root any, menu >= 1.1.0}この組み合わせにより、.この適合する用語は、デシジョン生成フェーズで生成されたものであり、派生フェーズで生成されたものではないため、これが根本的な原因であると仮定することができ、デシジョンを生成するために選択メニュー1.4.0にジャンプバックし、ユニット通過フェーズに戻ります。
この非互換性を念頭に置くことで、ユニットパッシングは互換性のないドロップダウンのバージョンを見て、menu >= 1.1.0ではなく、menu 1.0.0を選択するという判断を下す必要性をなくすことができます。これがPubGrubの核心です。
もし失敗したら？
正しい解決策を効率的に見つけることは良いことですが、PubGrubが強力であるのと同様に、別の依存関係に一致するパッケージのバージョンセットを見つけられなかった理由をユーザーに説明できる必要もあります。バージョン管理の失敗の理由は複雑な場合がありますが、PubGrubはどんなに混乱していても、何が間違っていたのかの明確な説明を生成することができます。
例えば、intl >= 5.0.0をアプリに追加しようとしても、dropdown < 2.0.0はintl < 4.0.0に依存しています。
最新のバージョン管理ソリューションでは、これはintlが原因のエラーであると報告するだけで、あなたのアプリが解決すべき本当の問題は依存アイコンのアップグレードです。 PubGrubの提案は以下の通りです。
Because dropdown >=2.0.0 depends on icons >=2.0.0 and root depends
on icons <2.0.0, dropdown >=2.0.0 is forbidden.
And because menu >=1.1.0 depends on dropdown >=2.0.0, menu >=1.1.0
is forbidden.
And because menu <1.1.0 depends on dropdown >=1.0.0 <2.0.0 which
depends on intl <4.0.0, every version of menu requires intl
<4.0.0.
So, because root depends on both menu >=1.0.0 and intl >=5.0.0,
version solving failed.
これにより、なぜドロップダウンの最新バージョンが選択できないのか、また古いバージョンを選択しても問題が解決しないのかが明確になります。この出力に基づき、ユーザーはこの問題をサポートする最新のアイコン・バージョンか古いイントル・バージョンのいずれかを見つけることができます。
この詳細なエラー出力は PubGrub の競合解決機能によってサポートされています。競合解決を使用して 2 つの非互換を結合するたびに、親へのポインタが新しい非互換に追加されます。それ以上さかのぼることができない非互換性に到達した場合、これらの親へのポインタを使用して、ルートパッケージの依存関係を満たすことができない非互換性の有向非循環グラフを形成することができます。
この例では、上に示したグラフは単なる直線です。エラーが複雑であればあるほど、図も複雑になります。また、同じ非互換性から枝分かれ、時には複数の枝分かれが発生することもあります。
PubGrubはこのグラフを深さ優先で走査し、よりユーザーフレンドリーな出力に変換します。この変換はすべてを人間が読めるようにすることを目的としているため、互換性のない記述を巧みに組み合わせたり、一見明白でないように見えるステップをひとまとめにしたり、プレーンな行だけでは不十分な場合に行番号を追加したりするなど、曖昧さを連想させるような手法が多く用いられています。
PubGrubを使いたいのですが！
これまでのところ、PubGrubはDartのパッケージマネージャとしてのみ実装されています。しかし、それは同じ問題を解決するために他の場所で使用することができる汎用の純粋なアルゴリズムとして設計されました。ですから、お気に入りのパッケージマネージャのGithubリポジトリで問題を提起し、PubGrubのサポートを求めてください。
このアルゴリズムの利点の一つはその柔軟性です。Pubはバージョンロック、強制アップグレード、SDKバージョン制限、依存関係オーバーライドなどの機能をサポートしています。Pubはバージョンロック、強制アップグレード、SDKバージョン制限、依存関係オーバーライドなどの機能をサポートしています。 各パッケージの非互換性を微調整することで、特定の要件をカスタマイズすることも簡単です。
もしあなたがパッケージマネージャーソリューションの知的サポートを提供していてPubGrubに興味があるのであれば、読むことをお勧めします。この記事でカバーされていないアルゴリズムの詳細について書かれています。もし何か質問があれば、 問題を提起してください。もちろん、 Twitterや メールで 私に連絡することもできます。
謝辞
オープンソース万歳。
