Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Rustdoc 検索

Rustdoc Search は search_index.rs と search.js という 2 つのプログラムです。前者は、ドキュメントバンドル内の クレートに含まれるアイテムと関数シグネチャの完全なリストを持つ厄介な JSON ファイルを生成し、後者はそれを読み込み、いくつかのメモリ内構造に変換して、 それらを線形に走査して検索します。

検索インデックス形式

search.js はこれを Raw と呼びます。読み込み後に、 より通常のオブジェクトツリーへ変換するためです。 容量削減のため、改行やスペースなしでも書き出されます。

[
    [ "crate_name", {
        // 名前
        "n": ["function_name", "Data"],
        // 型
        "t": "HF",
        // 親モジュール
        "q": [[0, "crate_name"]],
        // 親型
        "i": [2, 0],
        // 型辞書
        "p": [[1, "i32"], [1, "str"], [5, "Data", 0]],
        // 関数シグネチャ
        "f": "{{gb}{d}}`", // [[3, 1], [2]]
        // impl 曖昧性解消子
        "b": [],
        // 非推奨フラグ
        "c": "OjAAAAAAAAA=", // 空のビットマップ
        // 空の説明フラグ
        "e": "OjAAAAAAAAA=", // 空のビットマップ
        // エイリアス
        "a": [["get_name", 0]],
        // 説明シャード
        "D": "g", // 3
        // インライン化された再エクスポート
        "r": [],
    }]
]

src/librustdoc/html/static/js/rustdoc.d.ts は、TypeScript の type で実際のスキーマを定義しています。

KeyNameDescription
n名前アイテム名
tアイテム型1 文字のアイテム型コード
q親モジュールMap<index, path>
i親型インデックスのリスト
f関数シグネチャエンコード済み
bImpl 曖昧性解消子Map<index, string>
c非推奨フラグroaring bitmap
e説明が空roaring bitmap
p型辞書[[item type, path]]
aエイリアスMap<string, index>
D説明シャードエンコード済み

上のインデックスは、crate_name というクレートを定義しています。 そこには、function_name という自由関数と Data という構造体があり、 型シグネチャは Data, i32 -> str です。 さらに、function_name を同等に参照するエイリアス get_name があります。

検索インデックスは、rustdoc コンパイラ、 search.js フロントエンドのニーズを満たし、 さらにコンパクトで高速にデコードできる必要があります。 そのため、多くの妥協がなされています。

  • rustdoc コンパイラは一度に 1 つのクレートに対して実行されるため、 各クレートは本質的に個別の検索インデックスを持ちます。 各クレートを 1 行に置き、 最初のクォートされた文字列を見ることで、それらをマージします。
  • 検索インデックス内の名前は、 元の大文字小文字とアンダースコアを保持したまま与えられます。 検索インデックスが読み込まれると、 search.js は表示用に元の名前を保存しますが、 検索用には小文字に畳み込み、アンダースコアを取り除きます。 それらは normalized と呼ばれているのを目にするでしょう。
  • f 配列は、型を p 配列へのオフセットとして格納します。 これらの型は実際には別のクレート由来である可能性があるため、 同じインデックス内の複数のクレートが同じ型に言及している場合に それらを重複排除するため、search.js は数値を名前へ変換し、 その後で再び数値へ戻す必要があります。
  • これは JSON ファイルですが、人間が読みやすいようには設計されていません。 ブラウザにはすでに最適化された JSON デコーダが含まれているため、 これにより search.js のコードを節約でき、小さなクレートでは性能も向上します。 しかし、通常の JSON 形式のようにオブジェクトを使う代わりに、 同じ型のデータを互いに隣接させようとします。 そうすることで、DEFLATE が使用するスライディングウィンドウが冗長性を見つけられるためです。 search.js が独自に圧縮を行う箇所では、 それはディスク上やネットワーク転送時のサイズだけでなく、 ファイルが最終的に読み込まれたときのメモリを節約するように設計されています。

並列配列とインデックス付きマップ

抽象的には、Rustdoc Search のデータは列優先形式で格納されたテーブルです。 インデックス内のほとんどのデータは、同じ位置にあれば同じデータを参照する、 並列配列（「列」）の集合を表します。

たとえば、 上の検索インデックスは次のテーブルへ変換できます。

ntdqifbc
0crate_nameDDocumentationNULL0NULLNULL0
1function_nameHThis function gets the name of an integer with Datacrate_name2{{gb}{d}}NULL0
2DataFThe data structcrate_name0`NULL0

クレート行はほとんどの列で暗黙的に扱われます。なぜなら、その型は既知であり（クレートです）、 親を持つことができず（クレートはモジュールツリーのルートを形成します）、 名前はマップキーとして指定され、 impl 曖昧性解消子のような関数固有のデータも適用できないためです。 ただし、説明を持つことはでき、非推奨にすることもできます。 したがって、クレートは 0 という主キーを持ちます。

上のコードでは、非推奨のインデックスを保持する c や、 インデックスを文字列へマップする b は使用していません。 もし crate_name::function_name が両方を使用していたなら、次のようになるかもしれません。

        "b": [[0, "impl-Foo-for-Bar"]],
        "c": "OjAAAAEAAAAAAAIAEAAAABUAbgZYCQ==",

これはインデックス 1 に曖昧性解消子を付与し、それを非推奨としてマークします。

このレイアウトの利点は、これらの API がしばしば、 DEFLATE が活用できる暗黙の構造を持つ一方で、 rustdoc はそれを仮定できないことです。 たとえば、名前は通常 CamelCase や snake_case ですが、 説明はそうではありません。 また、boolean フラグのようなものにスパースデータを使いやすくもなります。

q は、最初に適用可能な ID から親モジュールパスへの Map です。 これは奇妙なトリックですが、疑似コードではより理解しやすくなります。

#![allow(unused)]
fn main() {
let mut parent_module = "";
for (i, entry) in search_index.iter().enumerate() {
    if q.contains(i) {
        parent_module = q.get(i);
    }
    // ... `entry` を使って他の処理を行う ...
}
}

これは、すべてのものが親モジュールを持つため有効です （たとえそれがクレート自体であるだけだとしても）。 また、rustdoc ジェネレータはシリアライズ前にパスでソートするため、組み立ても簡単です。 これにより rustdoc は検索インデックスを小さくできるだけでなく、 親パスを表す同じ文字列を、複数のメモリ内アイテム間で再利用できます。

スパース列の表現

VLQ Hex

この形式は、私の知る限り rustdoc 以外では使われていません。 これは次の文法に従います。

VLQHex = { VHItem | VHBackref }
VHItem = VHNumber | ( '{', {VHItem}, '}' )
VHNumber = { '@' | 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' | 'J' | 'K' | 'L' | 'M' | 'N' | 'O' }, ( '`' | 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' | 'k ' | 'l' | 'm' | 'n' | 'o' )
VHBackref = ( '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | ':' | ';' | '<' | '=' | '>' | '?' )

VHNumber は可変長の自己終端型16進数です （最後の16進桁が小文字で、それ以外がすべて大文字であるため終端します）。 符号ビットは zig-zag encoding を使用して表現されます。

このアルファベットが選ばれているのは、ASCII エンコーディングの下位4ビットを マスクすることで、文字を16進桁に変換できるためです。

rustdoc で行われるすべての「圧縮」と同様に、このエンコーディングの大きな特徴は、 ランタイムのメモリ上でさえ 圧縮形式のままでいられることです。 これが、HBackref がトップレベルでのみ使用される理由であり、 また、すべてに単に Flate を使わない理由です。search.js のデコーダーは backref が見つかるたびにデコード済みオブジェクト全体を再利用し、 デコード作業とメモリを節約します。

Roaring Bitmaps

非推奨かどうかや空の説明などのフラグ形式のデータは、 standard Roaring Bitmap serialization format with runs を使用して保存されます。 そのデータは書き込み時に base64 エンコードされます。

簡単に概説すると、roaring bitmap はチャンク化されたビット配列であり、 this paper で説明されています。 チャンクは、整数のリスト、ビットフィールド、または run のリストのいずれかです。 いずれの場合も、検索エンジンはそれを base64 デコードし、 チャンクインデックス自体を読み取る必要がありますが、 ペイロードデータはそのまま残ります。

rustdoc のすべての roaring bitmap は現在、各項目インデックスのフラグを保存します。 クレートは項目 0 で、それ以外はすべて 1 から始まります。

説明の保存方法

最も大きなデータ量を占めるもの、 そして Rustdoc Search が扱うもののうち実際には 検索に使われない主なものは、説明です。 SERP テーブルでは、これは一番右の列に表示されるものです。

項目の種類項目パス説明（この部分）
関数my_crate::my_functionこの関数は Data を使って整数の名前を取得します

誰かが rustdoc で初めて検索を実行すると、そのブラウザーは 3つのステップからなる「サンドイッチワークロード」を処理します。

  1. search-index.js ファイルと search.js ファイルをダウンロードする（ネットワークのボトルネック）。
  2. 実際の検索を実行する（CPU とメモリ帯域幅のボトルネック）。
  3. 説明データをダウンロードする（もう1つのネットワークのボトルネック）。

ここでダウンロードするデータ量を減らすと、ほぼ常にレイテンシが増加します。 これは、何をダウンロードするかの決定が他の作業の後に遅らされるため、かつ/または、 何か別のものを先にダウンロードしなければダウンロードできないものが生じるような データ依存関係が追加されるためです。この場合、検索が完了するまで 説明のダウンロードを開始できません。なぜなら、それによってどの 説明をダウンロードするかを決定できるようになるからです （結果をソートしてから 200 件に切り詰める必要があります）。

これを実現するため、Roaring Bitmaps と VLQ Hex の両方を土台として、 検索インデックスには2つの列が保存されます。

  • e は空の説明のインデックスです。これは各項目（クレート自体は項目 0、 残りは 1 から始まります）の roaring bitmap です。
  • D はシャードリストで、整数のフラットなリストとして VLQ hex に保存されます。 各整数は、そのシャード内の説明の数を示します。 デコーダーがインデックスをたどる際、説明が空かどうかを確認します。 空でなければ、それは「現在の」シャード内にあります。すべての項目を 処理し終えると、次のシャードへ進みます。

各シャードの中には、JSONP 形式の関数呼び出しでラップされた、 改行区切りの説明リストがあります。

i、f、および p

i と f はどちらも、親項目の配列である p へのインデックスです。

i は単なる1始まりの数値です （親項目を持たない項目に 0 が使われるため、0始まりではありません）。 これは q とは異なります。q は、すべての項目が持つ親のモジュールまたはクレート を表すのに対し、 i/q はメソッドのような型およびトレイト関連項目に使われるためです。

関数シグネチャである f は、VLQ hex ツリーを使用します。 数値は、p への1始まりの参照、 ジェネリックを表す負数、 または null を表すゼロのいずれかです。

（内部オブジェクト表現でも、 デコード後であっても、 ジェネリックを表すために負数を使用します）。

たとえば、{{gb}{d}} は JSON の [[3, 1], [2]] に相当します。 zigzag 符号化により、` は +0、a は -0（これは使用されません）、 b は +1、c は -1 です。

名前による検索

名前による検索は、検索インデックスをループ処理し、 各項目に対して以下の関数を実行することで動作します。

  • editDistance は一致を判定するために常に使用されます （引用符が指定されている場合を除き、その場合は代わりに単純な等価性が使用されます）。 これは、クエリ名をエントリー名に変換するために必要な 入れ替え、挿入、削除の回数を計算します。 たとえば、foo はそれ自身との距離がゼロですが、 ofo（1回の入れ替え）および foob（1回の挿入）からの距離は 1 です。 これはヒューリスティックな閾値と照合され、その後、 その閾値内にある場合は、ランキングのために距離が保存されます。
  • String.prototype.indexOf は一致を判定するために常に使用されます。 -1 以外を返した場合、editDistance がその閾値を超えていても、 結果が追加され、 ランキングのためにインデックスが保存されます。
  • checkPath は、クエリで親パスが指定されている場合にのみ使用されます。 たとえば、vec には親パスがありませんが、vec::vec にはあります。 checkPath 内では、editDistance と indexOf が使用され、 パスクエリにも独自のヒューリスティックな閾値があります。 閾値内にない場合、最初の2つが通っていても、 エントリーは拒否されます。 閾値内にある場合、ランキングのためにパス距離が保存されます。
  • checkType は、struct:vec における struct のような型フィルターがある場合にのみ使用されます。 失敗した場合、 エントリーは拒否されます。

4つの基準すべてを満たした場合 （技術的にはクエリの一部ではないクレートフィルターも加えて）、 結果は sortResults によってソートされます。

型による検索

型による検索は2つのフェーズに分けることができ、 2番目のフェーズには2つのサブフェーズがあります。

  • クエリ内の名前を数値に変換する。
  • 検索インデックス内の各エントリーをループ処理する:
    • ブルームフィルターを使用した高速な拒否。
    • 再帰的な型単一化アルゴリズムを使用した低速な拒否。 names->numbers フェーズでは、クエリに名前が1つだけ含まれている場合、 完全一致に失敗すると、editDistance 関数を使用して近い一致を探しますが、 クエリに複数の項目がある場合は、 一致しない項目は代わりにジェネリクスとして扱われます。 つまり、hahsmap は単独では hashmap に一致しますが、hahsmap, u32 は T, u32 が一致するものと同じものに一致することになります （ただし rustdoc はこの特定の問題を検出して警告します）。

次に、実際に各項目をループするとき、 ブルームフィルターはおそらく、クエリで言及されているすべての型を 持っていないエントリを拒否します。 たとえば、ブルームクエリでは i32 -> u32 というクエリが 型 i32, u32 -> bool を持つ関数に一致できますが、 単一化は後でそれを拒否します。

単一化フィルターは、次のことを保証します。

  • バッグセマンティクスが尊重されます。クエリが i32, i32 と指定している場合、 関数は i32 を1つだけではなく、2つ 言及している必要があります。
  • ネストのセマンティクスが尊重されます。クエリが vec<option> と指定している場合、 vec<option<i32>> は問題ありませんが、option<vec<i32>> は一致しません。
  • 戻り値の型とパラメーターの区分が尊重されます。 i32 -> u32 と u32 -> i32 は完全に異なります。

ブルームフィルターはこれらを一切チェックせず、 さらに偽陽性が発生することもあります。 しかし高速で、使用するメモリが非常に少ないため、ブルームフィルターは役に立ちます。

再エクスポート

再エクスポートのインライン化 により、同じ項目を複数の名前で見つけられます。 検索では、同じ項目に複数のエントリを与え、 指定されたパスと異なる項目については正規パスを追跡することで、これをサポートしています。

たとえば、このサンプルインデックスには、2つのパスからエクスポートされた単一の構造体があります。

[
    [ "crate_name", {
        "doc": "Documentation",
        "n": ["Data", "Data"],
        "t": "FF",
        "d": ["The data struct", "The data struct"],
        "q": [[0, "crate_name"], [1, "crate_name::submodule"]],
        "i": [0, 0],
        "p": [],
        "f": "``",
        "b": [],
        "c": [],
        "a": [],
        "r": [[0, 1]],
    }]
]

この例で重要なのは r 配列です。 これは、q 配列内のパスエントリ 1 が 項目 0 の正規パスであることを示しています。 つまり、crate_name::Data の正規パスは crate_name::submodule::Data です。

これは重複したデータを持っているため、奇妙な設計に聞こえるかもしれません。 このようになっているのは、インライン化がクレートをまたいで発生する可能性があり、 それらのクレートは個別にコンパイルされ、すべてがドキュメントに存在するとは限らないためです。

[
  [ "crate_name", ... ],
  [ "crate_name_2", { "q": [[0, "crate_name::submodule"], [5, "core::option"]], ... }]
]

上の例では、正規パスの1つは実際には依存関係から来ており、 もう1つはインライン化された標準ライブラリ項目から来ています。 正規パスはインデックス内にすらありません！ 正規パスが private である可能性もあります。 どちらの場合でも、それはユーザーには表示されず、重複排除にのみ使用されます。

関連型は、メソッドと同様に、異なる方法で保存されます。 これらの型は p（その「親」）内のエントリと結び付けられており、 それぞれに省略可能な3番目のタプル要素があります。

"p": [[5, "Data", 0, 1]]

これは次を意味します。

  • 5: 構造体であること
  • “Data”: その名前
  • 0: その表示パス、“crate_name”
  • 1: その正規パス、“crate_name::submodule”

どちらの場合でも、正規パスはまったく公開されていない可能性があり、 またはドキュメントに含まれていない別のクレートから来ている可能性があります。 そのため、ユーザーには表示されず、重複排除に使用されます。

検索エンジンのテスト

生成された UI は rustdoc-gui テストを使用してテストされますが、 検索エンジンをテストする主な方法は rustdoc-js と rustdoc-js-std テストです。これらは NodeJS で実行されます。

rustdoc-js テストには、同じ名前の .rs ファイルと .js ファイルがあります。 .rs ファイルは、検索を実行する仮想的なライブラリクレートを指定します （見つける必要があるものは必ず pub としてマークしてください）。 .js ファイルは、実際の検索を指定します。 rustdoc-js-std テストも同じですが、標準ライブラリを使用するため、 .rs ファイルは必要ありません。

.js ファイルはモジュールのようなものです（ただし、ローダーが exports を処理してくれます）。次の変数を使用します。

名前型説明
FILTER_CRATEstring指定されたクレートの結果のみを含めます。GUI では、これは「crate 内の結果」ドロップダウンメニューです。
EXPECTED[ResultsTable]|ResultsTable実行するテストのリスト。仮想ユーザーが検索ボックスに入力し、タブで見る内容を指定します
PARSED[ParsedQuery]|ParsedQuery実際の検索を実行せずに実行するパーサーテストのリスト

FILTER_CRATE は省略できます（「すべてのクレート」を検索することと同等です）が、 EXPECTED または PARSED を指定する必要があります。

デフォルトでは、テストケースで指定された結果のいずれかが検索の実行後に 見つからない場合、または検索の実行後に見つかった結果が テスト内と同じ順序で表示されない場合、テストは失敗します。 ただし、実際の検索結果には、テストに含まれていない結果が含まれる場合があります。 これを上書きするには、次のマジックコメントのいずれかを指定します。 インデントせず、それぞれ単独の行に置いてください。

  • // exact-check: テストケースの一部ではない検索結果が表示された場合、 失敗します。
  • // ignore-order: 検索結果が任意の順序で表示されることを許可します。
  • // should-fail: ネガティブテストを書くために使用します。

標準ライブラリのテストでは通常、// exact-check を指定すべきではありません。 これは、libs チームが新しい項目を追加しても、無関係な テストが失敗しないようにしたいためです。一方、スタンドアロンのテストでは、より頻繁に使用されます。

ResultsTable 型と ParsedQuery 型は、 rustdoc.d.ts で指定されています。

たとえば、constructor という名前の関数を見つけられないバグを 修正する必要があったとします。これを行うには、2つのファイルを書きます。

#![allow(unused)]
fn main() {
// tests/rustdoc-js/constructor_search.rs
// テストケースはこの結果を見つける必要があります。
pub fn constructor(_input: &str) -> i32 { 1 }
}
// tests/rustdoc-js/constructor_search.js
// exact-check
// このテストは自身のクレートに対して実行されるため、
// 新しい項目は検索結果に表示されるべきではありません。
const EXPECTED = [
  // この最初のテストは名前ベースの検索を対象とします。
  {
    query: "constructor",
    others: [
      { path: "constructor_search", name: "constructor" },
    ],
    in_args: [],
    returned: [],
  },
  // このテストは2番目のタブを対象とします。
  {
    query: "str",
    others: [],
    in_args: [
      { path: "constructor_search", name: "constructor" },
    ],
    returned: [],
  },
  // このテストは3番目のタブを対象とします。
  {
    query: "i32",
    others: [],
    in_args: [],
    returned: [
      { path: "constructor_search", name: "constructor" },
    ],
  },
  // このテストは高度な型駆動検索を対象とします。
  {
    query: "str -> i32",
    others: [
      { path: "constructor_search", name: "constructor" },
    ],
    in_args: [],
    returned: [],
  },
]

//@ revisions ディレクティブが使用されている場合、JSファイルは REVISION という変数にアクセスできます。

const EXPECTED = [
  // この最初のテストは名前ベースの検索を対象とします。
  {
    query: "constructor",
    others: REVISION === "has_constructor" ?
      [
        { path: "constructor_search", name: "constructor" },
      ] :
      [],
    in_args: [],
    returned: [],
  },
];