cargo-vet 日本語訳 誤訳を知らせる
cargo-vet ガイドアルゴリズム
  1. 動機
  2. 仕組み
  3. チュートリアル
  4. インストール
  5. セットアップ
  6. 監査基準
  7. 監査のインポート
  8. 監査の記録
  9. 監査の実施
  10. 公開者を信頼する
  11. ポリシーの指定
  12. 複数のリポジトリ
  13. CI の設定
  14. 監査の集まりを整える
  15. リファレンス
  16. 設定
  17. 監査エントリ
  18. ワイルドカード監査エントリ
  19. 信頼エントリ
  20. 組み込みの基準
  21. ファーストパーティのコード
  22. よくある質問
  23. コマンド
  24. アルゴリズム

Cargo Vet のアルゴリズム

vet の中心にあるのは「リゾルバ」です。リゾルバはビルドグラフと supply_chain ディレクトリを受け取り、vet check が通るべきかどうかを判定します。

check が失敗した場合、リゾルバはその失敗の理由を突き止めようとします(後で見るとおり、これは簡単な問題ではありません)。suggest を求めると、check を確実に満たす「良い」監査を提案しようとします(これもやはり簡単ではありません)。

この結果は、ほかのほとんどのコマンドが頼りにする基本的な部品です。

分かりやすくするために、この章では、リゾルバが必要とする入力の状態を集める「初期化」についても少し説明します。

初期化の手順

この段階は、おおむね読み込み・構文解析・妥当性の確認をひととおり行うだけです。コマンドによっては、 暗黙のうちに –locked や –frozen として動いたり、仮定の状態を問い合わせたりするため、 これらの手順の進め方が少し異なることがあります。

  1. ビルドグラフを取得する(cargo_metadata クレートを通じた cargo metadata)
  2. ストア(supply_chain)を取得する(読み込み、構文解析、妥当性の確認)
  3. インポートを更新する(取得、構文解析、妥当性の確認)
  4. audit-as-crates-io を確認する(ローカルの cargo レジストリと照合)

解決の手順

以下がリゾルバの論理的な手順です。ただし実際には、この最初のまとめから受ける印象よりも 互いに入り組んでいます。

  1. データ構造を組み立てる
    1. DepGraph を構築する
    2. CriteriaMapper を構築する
  2. 各パッケージに求められる基準を決める
    1. 開発用依存に対する要件を適用する
    2. ポリシーの要件をルートから葉に向かって伝える
  3. サードパーティ(crates.io)の各パッケージについて、確認済みの基準を解決する
    1. 各パッケージの AuditGraphs を構築する(あわせて違反を確認する)
    2. 各要件を満たす経路を監査グラフの中から探す
  4. 各クレートが、求められる基準を満たしているかを確認する
    1. それらの基準を満たすために必要だった但し書きを記録する
  5. 葉での失敗を直すための監査を提案する(千の差分の舞)

現在のリゾルバのアルゴリズムの全体を、省略した Rust 風の擬似コードで そのまま示します。それぞれの手順は、以降の節で詳しく説明します。

// 手順 1a: DepGraph を組み立てる
let graph = DepGraph::new(..);
// 手順 1b: CriteriaMapper を組み立てる
let mapper = CriteriaMapper::new(..);

// 手順 2: 各パッケージに求められる基準を決める
let requirements = resolve_requirements(..);

// 手順 3: サードパーティの各パッケージについて、確認済みの基準を解決する
for package in &graph.nodes {
    if !package.is_third_party {
        continue;
    }

    // 手順 3a: 各パッケージの AuditGraph を構築する
    let audit_graph = AuditGraph::build(..);
    // 手順 3b: 各要件を満たす経路を監査グラフの中から探す
    let search_results = all_criteria.map(|criteria| audit_graph.search(criteria, ..));

    // 手順 4: クレートが、求められる基準を満たしているかを確認する
    for criteria in requirements[package] {
        match &search_results[criteria] {
            ..
        }
    }
}

// 違反のエントリと矛盾するものがあれば、ここで打ち切る
if !violations.is_empty() {
    return ResolveReport { conclusion: Conclusion::FailForViolationConflict(..), .. };
}

// 失敗が 1 つもなければ、これで完了
if failures.is_empty() {
    return ResolveReport { conclusion: Conclusion::Success(..), .. };
}

// 手順 5: 提案の時間。失敗を直すための最も簡単な監査を計算する
let suggest = compute_suggest(..);

return ResolveReport { conclusion: Conclusion::FailForVet(..), .. };

求められる基準は独立したパスで決めるので、それより後の分析はすべて どの順番で行ってもかまいません。要件の分析はルートのノードから始まり、 葉のノードへ向かって下に伝わっていきます。

手順 1a: DepGraph(Cargo Metadata の処理)

私たちの分析はすべて、cargo metadata の出力と、それに対する私たちの 解釈から導かれます。そのため、これをどう使っているのか、その出力について 何が成り立つと考えているのかを説明しておく価値があります。

メタデータに対する私たちの解釈が DepGraph です。DepGraph は cargo vet dump-graph で出力できます。ほとんどのコマンドは --filter-graph 引数を受け取ります。 これを指定すると、コマンドの処理を行う前に DepGraph の特定の部分を 強制的に捨てさせることができます。問題の調査には便利ですが、ストアを壊さないように、 --locked を付けているときだけ使うことをおすすめします。

既定では cargo metadata --locked --all-features を実行します。vet に --locked を渡すと、 cargo metadata には代わりに --frozen を渡します。--all-features は、 vet に --no-all-features を渡すと打ち消せます。それ以外については、cargo の通常の フィーチャー用フラグをそのまま使えるようにしています。

--all-features を渡すのは、「最大の」ビルドグラフが欲しいからです。 「実際の」ビルドはどれも、このグラフの部分集合にすぎません。cargo metadata はおおむねこれを返しますが、 無効になっているフィーチャーの奥にあるオプションの依存は省かれます。すべてのフィーチャーを有効にすれば、 あらゆるフィーチャーとプラットフォームについて、あり得る依存がすべて得られるはずです。

最大のビルドグラフが検証済みであることを確認すれば、あり得るビルドはすべて 検証済みになるはずです。どのビルドも、そのグラフの部分集合にすぎないからです。

cargo metadata は、ビルドグラフをやや扱いにくい形で出力します。パッケージの情報の 一部は "packages" に、別の一部は "resolve" に入っています。そのうえ、 「ルート」「テスト専用」「トポロジカルソート」といった多くの事実を自分で計算する必要があります (メタデータにもルートという概念はありますが、想像するものとは違い、ほとんどは cargo の内部の概念を反映したもので、私たちの役には立ちません)。

当時 guppy を知っていたら、cargo metadata の結果の解釈には それを使っていたかもしれません。実際のところは、そのあたりをすべて自前で書いています。

cargo metadata は、ビルドの中のパッケージを識別する主キーとして、おおむね PackageId を 使います。内部的には私たちもおおむねそれに従っていますが、監査のように人が直接触れる インターフェースの一部では、(PackageName, Version) も有効なキーとして扱います。これは crates.io そのものでは正しいのですが、未公開のパッケージ、 パッチや名前の変更(?)、サードパーティのレジストリを含めると成り立たないかもしれません。今のところ、あいまいさを解消する しっかりした方針はありません。そういうことは起きないものと仮定して、気にしないことにしています。

リゾルバは、パッケージの主キーとして主に PackageIdx を使います。これは PackageId をインターン化したものです。 このインターナーは DepGraph が持っています。

テストから生じる循環への対処

リゾルバは、最大のグラフが DAG であると仮定しています。これはほぼ正しく、 グラフを少し脱糖(desugar)すれば正しくできます。cargo のビルドグラフが DAG にならない状況は 1 つだけで、それはクレートのテストです。これはとても簡単に起こり、 ある意味では自然なことですが、初めて知ったときにはかなり厄介に感じます。

具体例を挙げると、serde と serde_derive の間には、概念上の循環のようなものがあります。serde_derive は独立したクレートで、serde は(オプションで) serde_derive を依存として取り込みます。ところが serde_derive をテストするときには、serde_derive は ごく当然のこととして、自分の出力をテストするために serde に依存します。その結果、自分自身への循環依存ができてしまいます。

この厄介な状況を解消するには、serde_derive のテストが、実際には serde_derive とは別のパッケージなのだと考えます。私たちはこれを serde_derive_dev と呼んでいます(cargo がテスト用の 辺を「dev dependencies」と呼ぶからです)。つまり、cargo_metadata が報告するグラフは循環に見えますが、

serde <-----+
  |         |
  |         |
  +--> serde_derive

実際には、serde_derive_dev が循環を断ち切り、きれいな DAG になります。

  +--serde_derive_dev ---+
  |          |           |
  v          |           v
serde        |     test_only_dep
  |          |           |
  |          v          ...
  +--> serde_derive

ここで、テストだけに使われるパッケージについては、微妙な区別が必要です。 これらは開発用依存(開発用の辺)がなければビルドグラフに含まれませんが、 それでも「本物の」ノードです。その依存もすべて「本物」であり、やはり 正しい DAG になっていなければなりません。循環の原因となる開発用依存を持つことができ、 したがって「偽の」ノードを作る脱糖が必要になるパッケージは、ワークスペースのメンバーだけです。 これらは、cargo test --workspace を実行したときにテストされるパッケージです。

この脱糖を実際に行うのは、とても面倒です。「本物の」ノードについて成り立つことの多くは 「偽の」ノードについても成り立ちますし、たいていは「本物の」ノードと 「偽の」ノードを 1 つのものとして扱いたいからです。そこで実際には、ビルドグラフを 2 段階に分けて分析するだけにしています。この仕組みを理解するには、まず DAG がどのように分析されるかを見る必要があります。

DAG に対する分析は、たいていトポロジカルソートから始まります。難しく聞こえますが、要するに、すべてのルートから深さ優先探索(DFS)を行い、あるノードの子をすべて探索し終えてから初めてそのノードを使う、ということです(グラフに詳しい人向けに言えば、帰りがけ順です)。なお、DFS の各回では、 前の回までの「訪問済み」の情報を使い回します。各ノードは 1 回だけ訪れたいからです。

また、ルートを知っていることは単なる最適化にすぎません。すべてのノードから DFS を実行するだけでも、正しいトポロジカル順序が得られます。私たちは、ワークスペースのすべてのメンバーから DFS を実行しています。そこにはすべての ルートが含まれますが、テスト専用のパッケージは 1 つも含まれません。これは、脱糖の話に進んだときに、 テスト専用のパッケージを見分けるのに役立ちます(実際にはテスト専用のワークスペースのメンバーがあるかも しれませんが、vet から見れば、それらはそれ自体が正式なパッケージです。ただし、そうしたパッケージは ポリシーを safe-to-run に上書きする候補として適しています)。

DAG の重要な性質は、すべてのノードをトポロジカル順序で訪れると、 あるノードの推移的な依存はすべて、そのノードより先に訪れられることです。 この事実を使うと、依存の性質に再帰的に依存するようなノードの性質を 何でも計算できます。もっと簡単に言えば、各ノードの性質を計算する for ループを 書くだけでよく、依存についての問い合わせは結果がすでに計算済みだと 決めてかかってかまいません。便利ですね。

ただし私たちのアルゴリズムでは、実際には逆トポロジカル順序で訪れます。 こうすると、あるノードの逆依存がすべて、そのノードより先に訪れられることになります。 基準の要件は逆依存から受け継がれる(言い換えれば、クレートからその依存へと 押し出される)からです。

以上を踏まえて、「偽の」ノードの脱糖を模倣するために実際に使っている方法を示します。

  1. 開発用依存(の辺)を除いたビルドグラフを分析する。これは間違いなく DAG である
  2. 開発用依存を戻し、すべてのノードを「偽の」ノードであるかのように処理し直す

この方法の要点は、暗黙の開発用ノードがすべてルートである、つまり何からも 依存されていない、ということです。そのため、これらのノードを加えても、「本物の」ノードが どのパッケージに依存するかは変わりません。本物のノードに対して行った分析はどれも、開発用の辺がなくても正しいのです。

トポロジカルソートでは、ワークスペースのメンバーからしか DFS を実行しません。 その結果、最初のパスでは「実際の」ビルドに含まれるノードをすべて訪れ、 2 回目のパスでテスト専用のパッケージを訪れることになります。こうして、 「テスト専用」のパッケージは、トポロジカルソートの都合のよい副産物として求まります。再帰的な 分析が次のように 2 つのループの形をとっている限り、得られた順序がトポロジカルソートとして 機能することは、お分かりいただけると思います。

for node in topological_sort:
    analysis_that_DOESNT_query_dev_dependencies(node)
for node in topological_sort:
    analysis_that_CAN_query_dev_dependencies(node)

2 つ目のループは、実質的に「偽の」開発用ノードをすべて処理しています。

なお、クレートを訪れる前にその逆依存の確認が済んでいるように、 これを逆順で実行する場合には、開発用依存の分析を先に行う必要があります。 開発用依存の「偽の」ノードは、実質的にトポロジカルソートの末尾に 追加されているからです。

DepGraph の中身

DepGraph の最も難しい仕事は、前の節で説明したパッケージの トポロジカルソートを計算することです。しかしそれ以外にも、各パッケージ(ノード)について 次の事実を計算します。

パッケージがサードパーティかどうかの判定は、cargo_metadata の is_crates_io メソッドに任せていますが、 config.toml の audit-as-crates-io で上書きできます。これによって、 リゾルバがそのパッケージの基準を確認する方法がまったく変わります。サードパーティではないパッケージは 「ファーストパーティ」と呼びます。

ルートとは、単に逆依存を持たないパッケージのことです。これが重要なのは、 ほかにポリシーが指定されていなければ、ルートは暗黙のうちに既定のルートポリシー(safe-to-deploy)を 満たすことが求められるからです。

ワークスペースのメンバーは、開発用ポリシーの確認を通らなければなりません。開発用依存を 問い合わせるのはここだけです(前の節で触れた、あの「2 回目のパス」の中です)。

開発専用のパッケージはテストでしか使われないので、問い合わせを受けるのは 開発用ポリシーの確認のときだけです(そのため既定では safe-to-run であれば十分です)。

手順 1b: CriteriaMapper

CriteriaMapper は、基準の名前と CriteriaIndices を相互に変換する処理を 担当します。基本的にはインターナーですが、組み込みの基準、インポート、 「含意する(implies)」関係があるために、もう少し複雑になっています。

リゾルバは主に CriteriaSet を扱います。これは CriteriaIndices の集合です。 その目的は、基準にまつわる細かな事情をすべて 1 か所で扱ってバグを防ぐことと、 全体を効率よくすることです。

リゾルバの処理のほとんどは、「これらの基準の集合の和集合をとる」や 「この基準の集合が、求められる集合を包含しているかを確認する」といったものです。

現在は、CriteriaSet を効率的にするために(内部的には単なる u64 です)、 自分とすべてのインポートを合わせて基準は最大 64 個まで、という人為的な上限があります。 誰かがこの上限に達した場合には簡単に引き上げられるように(u128 を使うか、 きちんとした BitSet を使うかして)コードを設計してあります。

インポートされた基準は、ストアを取得する際に、あらかじめローカルの基準に対応付けられます。 まずインポート元の名前空間の CriteriaMapper を使って、含意される基準を 求めます。次に criteria-map で指定された対応付けを適用して、 対応するローカルの基準を決めます。こうすることで、リゾルバ本体を実行するときに インポート元の名前空間を気にせずに済み、基準の数が多い場合に起こり得る問題も 避けやすくなります。

この処理で最も複雑なのは、「含意する」の扱いです。これによって、 safe-to-deploy のような基準は、ほとんどの状況で実際には safe-to-deploy かつ safe-to-run になります。CriteriaMapper は、基準ごとに、含意する関係の推移閉包を CriteriaSet としてあらかじめ計算しておきます。基準の名前を CriteriaIndices に対応付けるときに返されるのは、この CriteriaSet です。

基準の集合を基準の名前のリストに対応付けるときには、含意される基準を省きます (つまり ["safe-to-deploy", "safe-to-run"] は、単に ["safe-to-deploy"] になります)。

基準の推移閉包の計算

ある基準の推移閉包とは、その基準自身と、それが含意するすべての基準、 さらに「それら」が含意するすべての基準、というように加えていったときに得られる CriteriaSet のことです。こうして得られる CriteriaSet が、実質的にその基準の「真の」値です。

これは、「含意する」を辺とする有向の「基準グラフ」を作ることで求めます。 各基準の推移閉包は、そのノードから深さ優先探索(DFS)を実行し、 到達できるノードをすべて CriteriaSet に加えることで計算できます。

これだけです。

推移閉包をあらかじめ計算できるおかげで、リゾルバはとても単純になります。 CriteriaSet の和集合をとるときに、含意する関係を評価し直す必要がまったくなくなり、 O(n3) になり得る処理が定数時間の処理になるからです。 ここで n は基準の数です(基準グラフには O(n2) 個の基準があり得て、 基準の集合には O(n) 個の基準があり得ます。そして、基準を 1 つ追加するたびに、 すべての基準についてグラフのすべての辺を調べなければならないかもしれません)。

しかし、推移閉包が存在することは、根本的な真理ではありません。これが 存在するのは、インポートの対応付けと含意にできることを、私たちが人為的に制限しているからです。 特に、ある基準を含意するのに 2 つの異なる基準を必要とするような含意の関係を認めてしまうと、推移閉包は 役に立つ概念ではなくなります。そうなると、基準の集合に基準が追加されるたびに (これはリゾルバの中で絶えず起きています)、すべての含意の規則を確認し直さなければなりません。

この問題を示す詳しい例は、こちらの issue を参照してください。

手順 2: 各パッケージに求められる基準を決める

一般に、どのパッケージも、そのパッケージ自身に求められたのと同じ基準を、 すべての依存が満たすことを求めます。この処理は、 ルートのクレートから始めて、求められる CriteriaSet を葉に向かって 外側へ伝えていくことで行います。場合によっては、policy テーブルで、 依存に課す要件として別の基準が指定されていることがあります。その場合は、 通常の伝播の代わりにそちらを使います。

開発用依存が持つ循環の性質を避けるために、これらのターゲットを 最初に処理します。開発用依存の依存はすべて通常の依存なので、 最初の辺より先は、循環のない通常の要件の伝播に任せられます。そのため、 この最初の段階では、要件を 1 階層分だけ適用すれば十分です。 この要件は既定では safe-to-run ですが、policy で 変更できます。

その後、グラフのルートのクレートから始めて外側へ進みます。その際、 ポリシーの要件を適用する必要があるかを確認してから、要件を依存へ 伝えていきます。その結果、すべてのクレートに、監査に求められる基準を表す CritseriaSet が対応することになります。

手順 3a: AuditGraph

AuditGraph は、特定のパッケージ名に対するすべての監査からなるグラフです。 グラフのノードは Version で、辺は差分監査(たとえば 0.1.0 -> 0.2.0)です。 それぞれの辺は、その辺が保証すると主張する基準のリストと、依存に対する基準を持っています。後者は、 その辺が「有効」と見なされるために、このパッケージの依存が満たさなければならない基準です (詳しくは次の節を参照してください)。

空のパッケージを表す、暗黙のルートバージョンがあります。そのため、 監査グラフの大部分では、バージョンは Option<Version> として表現されます。

パッケージの特定のバージョンが監査済みかどうかを確認しようとするときには、 ターゲットバージョンもグラフに追加します(まだ存在しない場合)。

全体監査は、ルートバージョンからの差分監査に脱糖されます(つまり 0.2.0 の監査は、 Root -> 0.2.0 という差分監査に変換されます)。

免除は、その由来を示す特別な DeltaEdgeOrigin を持つ全体監査(したがって差分)に 脱糖されます。これは、その辺の優先度を下げて、もう必要のない免除を 見つけやすくするために使われます。

インポートされた監査は、ローカルの基準とまったく同じ方法で変換されますが、 その由来を示す特別な DeltaEdgeOrigin が付きます。これによって、 インポートされた監査の優先度を下げ、どの監査が必要なのかを正確に判断できます。

インポートされたワイルドカードの基準にも特別な DeltaEdgeOrigin が使われます。 これは、どのワイルドカード監査によるものなのかと、どの公開者の 情報が使われているのかの両方を示します。

以上を踏まえると、あるパッケージが特定の基準について監査済みかどうかを判定する問題は、 その基準を保証する辺をたどって、ルートバージョンからターゲットバージョンに至る経路が 存在するかどうかを判定する問題に帰着できます。同様に、監査を提案することは、 目的の基準についてルートとターゲットをつなぐために追加する「最良の」辺を見つけることになります。

違反の確認

AuditGraph の構築中に、違反も確認します。違反は、VersionReq と、 違反している基準のリストを持っています。違反が主張しているのは、VersionReq が対象とするすべてのバージョンについて、 挙げられた基準に明確に違反していると考えている、ということです。AuditGraph に辺を追加するときに、 どちらかの端点が VersionReq に一致し、かつ、 その辺が監査の対象だと主張する基準のいずれかが違反に挙げられていれば、エラーになります。

この文は読み解くのがとても難しいので、例をいくつか見てみましょう。

violation: safe-to-deploy, audit: safe-to-deploy -- ERROR!
violation: safe-to-deploy, audit: safe-to-run    -- OK!
violation: safe-to-run,    audit: safe-to-deploy -- ERROR!
violation: [a, b],         audit: [a, c]         -- ERROR!

ここから導かれるとても重要な帰結は、["safe-to-run", "safe-to-deploy"] に対する違反が、 実際には ["safe-to-deploy"] ではなく ["safe-to-run"] と同等だということです。つまり、 違反の基準を 1 つの CriteriaSet に変換して audit.contains(violation) を確認する、という通常の扱い方は誤りなのです。

代わりに、違反に含まれる項目の 1 つ 1 つについて、この確認を行わなければなりません。

let has_violation = violation.iter().any(|item| audit.contains(item));

いずれかの監査が、いずれかの違反と少しでも矛盾していたらエラーにする、 というのは少し奇妙に思えるかもしれません。それは必要なのでしょうか。それで十分なのでしょうか。

十分であることは間違いありません。あるバージョンに端点を持つ監査の辺がなければ、 そのバージョンを確認済みにすることはできないからです。

また、これは必要でもあると考えます。違反と直接矛盾する監査(または免除)が 存在するということは、本質的に、私たちが扱っている主張の整合性に関する エラーだからです。自分ではその監査をもう何にも使っていなくても、 あなたとピアリングしてあなたの監査をインポートしている人が使っているかもしれません。 ですから、それらの監査が誤っているかもしれないと分かったら、すぐに何らかの対応をすべきです。

現在のところ、このような整合性のエラーを機械的に処理する仕組みはありません。 その監査や違反が外部からのインポートに由来する場合でも同じです。このような状況は、 人どうしが直接話し合うに値するほど深刻です。とはいえ、これが 大きな問題になるようであれば、いずれそうした機能を追加するかもしれません。

手順 3b: AuditGraph の中で経路を探す

この作業の大変な部分の多くは、手順 3a(AuditGraph)で済んでいます。

すべての基準を一度に確認しようとすると、少し頭が混乱します (基準によって、確認に使われる経路が異なるかもしれないからです)。そこで 単純にするために、基準を 1 つずつ個別に確認します(つまり、これから 説明することはすべて for ループの中で起こります)。

パッケージがある基準を満たしているかどうかだけを知りたいのであれば、 ルートノードから深さ優先探索(DFS)を実行して、ターゲットノードに 到達するかどうかを見るだけで済みます。ただし、たどるのは (依存についてすでに確認済みの基準に基づいて)有効な辺だけ、という制約を付けます。

到達すれば、ターゲットバージョンについてその基準を確認できたことになります。到達しなければ、 確認できていません。

しかし、実際にはずっと複雑です。監査の状態について、もっと多くの 情報を返したいからです。

これは、スタックではなく優先度付きキューを使って探索を進めることで 実現しています。こうすると、「最良の」辺だけを最初に試すことができ、 より良い辺を使う経路をすべて試し終えるまでは、「より悪い」辺を試さないことが 保証されます。

何よりも良い辺は、ローカルの監査です。この辺だけを使う経路が 見つかれば、完全に監査済みであり、このパッケージに対する 免除があっても必要なく(これには但し書きがたくさんあるので、実際には この結論を確実に出しているわけではありません)、imports.lock を更新する必要もありません。

経路を見つけるために免除を戻す必要があるのなら、その免除は この基準を確認するために必要だったということです。

経路を見つけるために新しいインポートを戻す必要があるのなら、 imports.lock を更新して、–locked での実行に必要な監査をキャッシュしなければなりません (これが免除の後に来るため、インポートを更新するときには、 あるものが「完全に監査済み」かどうかの判定が少し不正確になるかもしれません。その後の 実行では、ここまでたどり着かないからです。それでも、imports.lock の更新を 最小限に抑えられる利点のほうが大きいと考えています)。

これらのいずれかが成功した場合は、Ok(..) を返します。これによって、 パッケージがこの基準を満たしていることと、但し書きがあればその内容を、呼び出し元に伝えます。

そうでなければ、Err(..) を返し、現在のノードに原因があると見なします。この 基準が求められている場合、このパッケージが検証を通るには、 追加の監査か免除が必要になります。

この処理の中で、ルートバージョンから到達可能なノードと、 ターゲットバージョンから逆向きに到達可能なノードも計算します。 後者は、すべての辺を逆向きにたどることで計算します。つまり、 手順 3a の AuditGraph は、辺をすべて逆向きにしたもう 1 つの有向グラフも 持っており、ルートとターゲットを入れ替えてアルゴリズムをもう一度実行します。

この情報が役に立つのは、Err の場合に、監査すべき差分を提案したいからです。 ルートから到達可能なノードから、ターゲットから到達可能なノードへの差分であれば、 どれでも十分です。

探索の結果はすべて、確認済みの基準や、途中で分かったそのほかの 興味深い事実とともに、そのノードの ResolveResult に保存されます。 ResolveResult の内容は、手順 2 と 3 で、逆依存によって 使われます。

ここで触れておきたいのは、差分監査は「後戻り」できる(つまり 1.0.1 -> 1.0.0)ということです。 このコードはすべて、特別な場合分けなしにそれを問題なく扱えます。 これによって AuditGraph に循環ができる可能性はありますが、 DFS は循環をまったく気にしません。再訪を避けるために、訪れたノードを 記録しているからです(私たちは辺を段階的に追加していくので、少し複雑にはなります)。

手順 4: 各クレートが、求められる基準を満たしているかを確認する

この手順は、手順 2(要件の計算)と手順 3(確認済みの基準の解決)の結果を 組み合わせるだけの、ごく単純なものです。各パッケージについて、 確認済みの基準が要件を包含しているかを調べます。包含していれば 成功で、そうでなければ失敗です。

エラーの場合には、より良い監査を提案できるように、どの基準で失敗したかを 記録します。成功の場合には、成功した実行の但し書きをまとめます。 こうして、個々の基準ごとではなく、クレートごとにまとめた結果を 得ます。

手順 5: 監査の提案(千の差分による死)

この手順では、手順 4 で失敗したパッケージを受け取り、それを直す監査を すすめます。手順 3b では、つながっていないパッケージについて、ルートから到達可能なノードと ターゲットから到達可能なノードを計算しました。この段階では、それらを 候補として使い、できるだけ良い差分監査を見つけようとします。

もう少し具体的に言うと、このパッケージが失敗したすべての基準について、 ルートから到達可能なノードの共通部分を使います(ターゲットから到達可能なノードについても同様です)。 共通部分を使うことで、一方の集合からもう一方の集合への差分としてすすめるものはどれも、 求められる基準をすべてカバーすることが保証されます。そのため、1 つの 差分ですべてを直す提案ができます。ルートとターゲットは常にそれぞれの 集合に含まれるので、共通部分が空でないことも保証されます。

では、最良の差分はどうやって選ぶのでしょうか。実は、監査があるパッケージのバージョンを 片っ端からすべてダウンロードして、すべての組み合わせの diff-stat をとります。最も小さい差分の勝ちです。ひどく 遅そうに聞こえますか。そのとおりです。だから、あなたのシステム上には、秘密のグローバルな diff-stat キャッシュがあります。

また、文字どおりすべての組み合わせの差分をとるわけではありません。簡単なヒューリスティックで、O(n2) 個の差分を O(n) 個の差分に減らしています。ターゲットから到達可能なノードのそれぞれについて、 そのバージョンより小さい最も近いバージョンと、そのバージョンより大きい最も近い バージョンを見つけます。そして、そのバージョンとの差分は、この 2 つのバージョンに対してだけとります。 大きな変更が加えられた後で元に戻された、というような魔法のような差分を見逃すかもしれませんが、 この差分の処理は、ある程度抑えておく必要があります。

Version は正式な距離空間をなさない、という点にも触れておきます。2 つの Version の間の 「距離」を抽象的に計算して、それを別の 2 つのバージョンの間の「距離」と 比べることはできません。しかし、バージョンには全順序があります。そのため、 最小と最大のバージョンを計算したり、あるバージョンが別のバージョンより大きいか小さいかを 判定したりできます。その結果、「X より小さいバージョンのうち最大のもの」と 「X より大きいバージョンのうち最小のもの」を計算でき、私たちはこれを使っています。ただし、 小さい側の最大と大きい側の最小のどちらが X に近いのかを判定する方法はないので、 両方を試さなければなりません。

差分は後戻りできる、ということも、ここで改めて述べておきます。1.0.0 を使っていて 1.0.1 の監査がある場合、1.0.1 -> 1.0.0 という逆向きの差分を迷わずすすめます。 最初は少し頭が混乱しますが、これを特別に扱う必要のあるものは実際には何もなく、 そのままうまく動きます。

ルートバージョンからの差分をすすめる場合は、すべて、全体監査をすすめる形に「糖衣をかけ直し」ます (このときの差分は、空のディレクトリとの比較で計算します)。ルートバージョン への差分をすすめることはできません。ルートバージョンの監査は 存在し得ないからです。