Rustdoc 검색

Rustdoc 검색은 search_index.rs와 search.js라는 두 프로그램으로 구성됩니다. 전자는 문서 번들에 포함된 크레이트의 모든 항목과 함수 시그니처 목록을 담은 지저분한 JSON 파일을 생성하고, 후자는 이 파일을 읽어 메모리 내 구조체로 변환한 뒤 이를 선형으로 훑어 검색합니다.

검색 인덱스 형식

search.js는 이것을 로드한 후 더 일반적인 객체 트리로 변환하므로 이것을 Raw라고 부릅니다. 공간을 절약하기 위해 줄바꿈이나 공백 없이 작성되기도 합니다.

[
    [ "crate_name", {
        // name
        "n": ["function_name", "Data"],
        // type
        "t": "HF",
        // parent module
        "q": [[0, "crate_name"]],
        // parent type
        "i": [2, 0],
        // type dictionary
        "p": [[1, "i32"], [1, "str"], [5, "Data", 0]],
        // function signature
        "f": "{{gb}{d}}`", // [[3, 1], [2]]
        // impl disambiguator
        "b": [],
        // deprecated flag
        "c": "OjAAAAAAAAA=", // empty bitmap
        // empty description flag
        "e": "OjAAAAAAAAA=", // empty bitmap
        // aliases
        "a": [["get_name", 0]],
        // description shards
        "D": "g", // 3
        // inlined re-exports
        "r": [],
    }]
]

src/librustdoc/html/static/js/rustdoc.d.ts는 TypeScript type으로 실제 스키마를 정의합니다.

위 인덱스는 crate_name이라는 크레이트를 정의합니다. 이 크레이트에는 function_name이라는 자유 함수와 Data라는 구조체가 있으며, 함수의 타입 시그니처는 Data, i32 -> str이고, function_name을 동일하게 가리키는 별칭 get_name도 있습니다.

검색 인덱스는 rustdoc 컴파일러와 search.js 프런트엔드의 요구를 모두 충족해야 하며, 크기가 작고 디코딩도 빨라야 합니다. 이를 위해 많은 부분에서 절충합니다:

• rustdoc 컴파일러는 한 번에 하나의 크레이트만 처리하므로, 각 크레이트는 사실상 별도의 검색 인덱스를 가집니다. 각 크레이트를 한 줄에 하나씩 두고 첫 번째 따옴표 문자열을 확인하는 방식으로 이들을 병합합니다.
• 검색 인덱스의 이름은 원래의 대소문자와 밑줄을 그대로 유지합니다. 검색 인덱스를 불러오면 search.js는 표시용으로 원래 이름을 저장하는 한편, 검색용으로는 이름을 소문자로 바꾸고 밑줄을 제거합니다. 이렇게 처리된 이름은 normalized라고 불립니다.
• f 배열은 타입을 p 배열에 대한 오프셋으로 저장합니다. 이 타입들은 실제로 다른 크레이트에서 온 것일 수 있으므로, 같은 인덱스에 있는 여러 크레이트가 같은 타입을 언급하는 경우 search.js는 중복을 제거하기 위해 숫자를 이름으로 바꾼 뒤 다시 숫자로 바꿔야 합니다.
• 이 파일은 JSON 파일이지만, 사람이 읽기 쉽도록 설계되지는 않았습니다. 브라우저에는 이미 최적화된 JSON 디코더가 포함되어 있으므로 search.js 코드를 줄일 수 있고 작은 크레이트에서 성능도 더 좋습니다. 다만 일반적인 JSON 형식처럼 객체를 사용하는 대신, DEFLATE가 사용하는 슬라이딩 윈도우가 중복을 찾을 수 있도록 같은 타입의 데이터를 서로 인접하게 배치하려고 합니다. search.js가 자체적으로 압축을 수행하는 부분은 디스크 크기나 네트워크 전송량만이 아니라, 파일을 최종적으로 불러왔을 때의 메모리도 절약하도록 설계되었습니다.

병렬 배열과 인덱스 맵

추상적으로 보면 Rustdoc 검색 데이터는 열 우선(column-major) 형태로 저장된 표입니다. 인덱스의 데이터 대부분은 병렬 배열(“열”)의 집합을 나타내며, 같은 위치에 있는 값들은 같은 데이터를 가리킵니다.

예를 들어, 위 검색 인덱스는 다음과 같은 표로 바꿀 수 있습니다:

크레이트 행은 대부분의 열에서 암시됩니다. 타입이 이미 알려져 있고(크레이트이므로), 부모를 가질 수 없으며(크레이트는 모듈 트리의 루트이므로), 이름은 맵 키로 지정되고, impl 구분자 같은 함수 전용 데이터도 적용될 수 없기 때문입니다. 하지만 크레이트도 설명을 가질 수 있고 지원 중단(deprecated)될 수도 있습니다. 따라서 크레이트의 기본 키는 0입니다.

위 코드는 지원 중단된 인덱스를 담는 c나 인덱스를 문자열에 매핑하는 b를 사용하지 않습니다. crate_name::function_name이 둘 다 사용한다면 다음과 같은 모습이 될 것입니다.

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

이는 인덱스 1에 구분자를 붙이고 해당 항목을 지원 중단으로 표시합니다.

이 레이아웃의 장점은 이러한 API에 DEFLATE는 활용할 수 있지만 rustdoc은 가정할 수 없는 암묵적인 구조가 흔히 있다는 점입니다. 예를 들어 이름은 보통 CamelCase나 snake_case이지만 설명은 그렇지 않습니다. 또한 불리언 플래그 같은 것에 희소 데이터를 사용하기도 더 쉬워집니다.

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);
    }
    // ... do other stuff with `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진 자릿수만 소문자이고 나머지는 모두 대문자이기 때문에 끝을 알 수 있습니다). 여기서 “가변“은 길이를 나타내는 변수 값이 정해져 있지 않다는 뜻입니다. 부호 비트는 지그재그 인코딩을 사용하여 표현합니다.

이 알파벳을 선택한 이유는 ASCII 인코딩의 마지막 네 비트만 남기고 마스킹하면 문자를 헥싯으로 바꿀 수 있기 때문입니다.

rustdoc에서 수행하는 모든 “압축“과 마찬가지로, 이 인코딩의 주요 기능은 런타임에 메모리 안에서도 압축된 형식을 유지할 수 있다는 점입니다. 이것이 HBackref가 최상위 수준에서만 사용되는 이유이자, 모든 것에 그냥 Flate를 사용하지 않는 이유입니다: search.js의 디코더는 백레퍼런스를 만날 때마다 디코딩된 객체 전체를 재사용하므로 디코딩 작업과 메모리를 절약합니다.

Roaring 비트맵

지원 중단 여부나 빈 설명 같은 플래그 형태의 데이터는 런(run)을 포함한 표준 Roaring Bitmap 직렬화 형식을 사용하여 저장됩니다. 그런 다음 데이터를 기록할 때 base64로 인코딩합니다.

간단히 개요를 설명하면, roaring 비트맵은 이 논문에 설명된 청크 단위의 비트 배열입니다. 청크는 정수 목록, 비트필드, 런 목록 중 하나일 수 있습니다. 어느 경우든 검색 엔진은 이를 base64로 디코딩하고 청크 인덱스를 직접 읽어야 하지만, 페이로드 데이터는 그대로 유지됩니다.

현재 rustdoc의 모든 roaring 비트맵은 항목 인덱스마다 플래그를 하나씩 저장합니다. 크레이트는 항목 0이며, 나머지는 모두 1부터 시작합니다.

설명이 저장되는 방식

가장 많은 양을 차지하는 데이터이자, Rustdoc Search가 다루는 것 중 실제로 검색에는 사용되지 않는 주된 데이터는 설명입니다. SERP 표에서 설명은 가장 오른쪽 열에 표시됩니다.

항목 타입	항목 경로	설명 (이 부분)
함수	my_crate::my_function	이 함수는 Data로 정수의 이름을 가져옵니다

누군가 rustdoc에서 처음으로 검색을 실행하면, 브라우저는 세 단계로 이루어진 “샌드위치 작업 부하“를 처리합니다:

1. search-index.js와 search.js 파일을 다운로드합니다(네트워크 병목).
2. 실제 검색을 수행합니다(CPU 및 메모리 대역폭 병목).
3. 설명 데이터를 다운로드합니다(또 다른 네트워크 병목).

여기서 다운로드하는 데이터의 양을 줄이면 거의 항상 지연 시간이 늘어납니다. 무엇을 다운로드할지 결정하는 일이 다른 작업 뒤로 밀리거나, 다른 것을 먼저 다운로드해야만 무언가를 다운로드할 수 있는 데이터 의존성이 추가되기 때문입니다. 이 경우에는 검색이 끝나기 전까지 설명 다운로드를 시작할 수 없습니다. 검색이 끝나야 어떤 설명을 다운로드할지 결정할 수 있기 때문입니다(결과를 정렬한 다음 200개로 잘라야 합니다).

이를 위해 검색 인덱스에는 Roaring Bitmap과 VLQ Hex를 모두 기반으로 하는 두 개의 열이 저장됩니다.

• e는 비어 있는(empty) 설명의 인덱스입니다. 이것은 각 항목에 대한 roaring bitmap입니다(크레이트 자체가 항목 0이고, 나머지는 1부터 시작합니다).
• D는 샤드 목록으로, VLQ hex로 된 평탄한 정수 목록 형태로 저장됩니다. 각 정수는 해당 샤드에 들어 있는 설명의 개수를 나타냅니다. 디코더는 인덱스를 순회하면서 설명이 비어 있는지 확인합니다. 비어 있지 않다면 그 설명은 “현재” 샤드에 속합니다. 모든 항목을 다 소진하면 다음 샤드로 넘어갑니다.

각 샤드 안에는 줄바꿈으로 구분된 설명 목록이 JSONP 스타일의 함수 호출로 감싸여 들어 있습니다.

i, f, p

i와 f는 모두 부모 항목의 배열인 p를 가리키는 인덱스입니다.

i는 단순히 1부터 시작하는 숫자입니다(0부터 시작하지 않는 이유는 0이 부모 항목이 없는 항목에 사용되기 때문입니다). 이것은 q와 다릅니다. q는 모든 항목이 가지고 있는 부모 모듈 또는 크레이트를 나타내는 반면, i/q는 메서드와 같은 타입 및 트레이트 연관 항목에 사용되기 때문입니다.

함수 시그니처인 f는 VLQ hex 트리를 사용합니다. 각 숫자는 p를 가리키는 1부터 시작하는 참조이거나, 제네릭을 나타내는 음수이거나, null을 나타내는 0입니다.

(내부 객체 표현도 디코딩 이후에도 제네릭을 나타내기 위해 음수를 사용합니다.)

예를 들어 {{gb}{d}}는 json [[3, 1], [2]]와 동일합니다. 지그재그 인코딩 때문에 `는 +0, a는 -0(사용되지 않음), b는 +1, c는 -1입니다.

이름으로 검색하기

이름으로 검색할 때는 검색 인덱스를 순회하면서 각 항목에 다음 함수들을 실행합니다.

• editDistance는 일치 여부를 판단하는 데 항상 사용됩니다(따옴표를 지정한 경우는 예외이며, 이때는 단순 동등 비교를 대신 사용합니다). 이 함수는 쿼리 이름을 항목 이름으로 바꾸는 데 필요한 교환, 삽입, 삭제 횟수를 계산합니다. 예를 들어, foo는 자기 자신과의 거리가 0이지만, ofo(교환 1회) 및 foob(삽입 1회)와의 거리는 1입니다. 이 거리를 휴리스틱 임곗값과 비교하고, 임곗값 이내이면 순위 결정을 위해 거리를 저장합니다.
• String.prototype.indexOf는 일치 여부를 판단하는 데 항상 사용됩니다. 이 함수가 -1 이외의 값을 반환하면 editDistance가 임곗값을 초과하더라도 결과가 추가되며, 순위 결정을 위해 인덱스가 저장됩니다.
• checkPath는 쿼리에 부모 경로가 지정된 경우에만 사용됩니다. 예를 들어, vec에는 부모 경로가 없지만 vec::vec에는 있습니다. checkPath 안에서는 editDistance와 indexOf가 사용되며, 경로 쿼리에도 자체 휴리스틱 임곗값이 있습니다. 임곗값 이내가 아니면 앞의 두 검사를 통과했더라도 해당 항목은 거부됩니다. 임곗값 이내이면 순위 결정을 위해 경로 거리가 저장됩니다.
• checkType은 struct:vec의 구조체(struct)처럼 타입 필터가 있는 경우에만 사용됩니다. 이 검사에 실패하면 해당 항목은 거부됩니다.

네 가지 기준을 모두 통과하면(엄밀히 말해 쿼리의 일부는 아닌 크레이트 필터도 포함하여) 결과가 sortResults에 의해 정렬됩니다.

타입으로 검색하기

타입으로 검색하는 과정은 두 단계로 나눌 수 있으며, 두 번째 단계는 다시 두 개의 하위 단계로 나뉩니다.

• 쿼리에 있는 이름을 숫자로 변환합니다.
• 검색 인덱스의 각 항목을 루프로 순회합니다:
  • 블룸 필터를 사용하여 빠르게 거부합니다.
  • 재귀적 타입 통합(unification) 알고리즘을 사용하여 느리게 거부합니다.

이름을 숫자로 변환하는 단계에서 쿼리에 이름이 하나뿐이면 정확한 일치에 실패했을 때 editDistance 함수로 근사 일치를 찾지만, 쿼리에 항목이 여러 개 있으면 일치하지 않는 항목은 대신 제네릭으로 취급됩니다. 즉, hahsmap은 단독으로는 hashmap과 일치하지만, hahsmap, u32는 T, u32와 일치하는 것과 같은 대상과 일치하게 됩니다(다만 rustdoc은 이 특정 문제를 감지하고 경고합니다).

그런 다음 실제로 각 항목을 순회할 때, 블룸 필터는 쿼리에 언급된 타입을 모두 갖고 있지 않은 항목을 대체로 거부합니다. 예를 들어, 블룸 쿼리는 i32 -> u32 쿼리가 i32, u32 -> bool 타입의 함수와 일치하도록 허용하지만, 나중에 통합 단계에서 이를 거부합니다.

통합 필터는 다음 사항을 보장합니다.

• 백(bag) 의미론을 준수합니다. 쿼리가 i32, i32이면 함수는 i32를 하나가 아니라 두 개 언급해야 합니다.
• 중첩 의미론을 준수합니다. 쿼리가 vec<option>이면 vec<option<i32>>는 일치하지만 option<vec<i32>>는 일치하지 않습니다.
• 반환 타입과 매개변수의 구분을 준수합니다. i32 -> u32와 u32 -> i32는 완전히 다릅니다.

블룸 필터는 이 중 어느 것도 검사하지 않으며, 게다가 거짓 양성이 발생할 수도 있습니다. 하지만 빠르고 메모리를 매우 적게 사용하므로 블룸 필터는 도움이 됩니다.

재내보내기

재내보내기 인라이닝을 사용하면 같은 항목을 여러 이름으로 찾을 수 있습니다. 검색은 같은 항목에 여러 개의 엔트리를 부여하고, 정규 경로가 주어진 경로와 다른 항목에 대해서는 정규 경로를 추적하는 방식으로 이를 지원합니다.

예를 들어, 다음 샘플 인덱스에는 두 경로에서 내보내진 구조체 하나가 있습니다.

[
    [ "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"]], ... }]
]

위 예제에서 정규 경로 하나는 실제로 의존성에서 오고, 다른 하나는 인라인된 표준 라이브러리 항목에서 옵니다. 정규 경로가 인덱스에 아예 없는 것입니다! 정규 경로가 비공개일 수도 있습니다. 어느 경우든 정규 경로는 사용자에게 절대 표시되지 않으며, 중복 제거에만 사용됩니다.

연관 타입은 메서드와 마찬가지로 이를 다른 방식으로 저장합니다. 이러한 타입은 p의 엔트리(해당 타입의 “부모”)와 연결되며, 각 타입에는 선택적인 세 번째 튜플 요소가 있습니다.

"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_CRATE는 생략할 수 있지만(“all crates“를 검색하는 것과 동일합니다), EXPECTED 또는 PARSED는 반드시 지정해야 합니다.

기본적으로 테스트 케이스에 지정된 결과 중 하나라도 검색을 실행한 후 찾을 수 없거나, 검색을 실행한 후 찾은 결과가 테스트에 적힌 것과 같은 순서로 나타나지 않으면 테스트가 실패합니다. 그러나 실제 검색 결과에는 테스트에 없는 결과가 포함될 수 있습니다. 이 동작을 재정의하려면 다음 매직 주석 중 하나를 지정하십시오. 매직 주석은 들여쓰기 없이 별도의 줄에 작성하십시오.

• // exact-check: 테스트 케이스에 포함되지 않은 검색 결과가 나타나면 실패합니다.
• // ignore-order: 검색 결과가 어떤 순서로 나타나도 허용합니다.
• // should-fail: 부정 테스트를 작성할 때 사용합니다.

표준 라이브러리 테스트에는 일반적으로 // exact-check를 지정하지 않아야 합니다. libs 팀이 관련 없는 테스트를 실패시키지 않고 새 항목을 추가할 수 있어야 하기 때문입니다. 반면 독립 실행형 테스트에서는 이 주석을 더 자주 사용합니다.

ResultsTable 및 ParsedQuery 타입은 rustdoc.d.ts에 명시되어 있습니다.

예를 들어, constructor라는 이름의 함수를 찾을 수 없는 버그를 수정해야 한다고 가정해 봅시다. 이를 위해 다음 두 파일을 작성하십시오.

#![allow(unused)]
fn main() {
// tests/rustdoc-js/constructor_search.rs
// The test case needs to find this result.
pub fn constructor(_input: &str) -> i32 { 1 }
}

// tests/rustdoc-js/constructor_search.js
// exact-check
// Since this test runs against its own crate,
// new items should not appear in the search results.
const EXPECTED = [
  // This first test targets name-based search.
  {
    query: "constructor",
    others: [
      { path: "constructor_search", name: "constructor" },
    ],
    in_args: [],
    returned: [],
  },
  // This test targets the second tab.
  {
    query: "str",
    others: [],
    in_args: [
      { path: "constructor_search", name: "constructor" },
    ],
    returned: [],
  },
  // This test targets the third tab.
  {
    query: "i32",
    others: [],
    in_args: [],
    returned: [
      { path: "constructor_search", name: "constructor" },
    ],
  },
  // This test targets advanced type-driven search.
  {
    query: "str -> i32",
    others: [
      { path: "constructor_search", name: "constructor" },
    ],
    in_args: [],
    returned: [],
  },
]

//@ revisions 지시문을 사용하면 JS 파일에서 REVISION이라는 변수에 접근할 수 있습니다.

const EXPECTED = [
  // This first test targets name-based search.
  {
    query: "constructor",
    others: REVISION === "has_constructor" ?
      [
        { path: "constructor_search", name: "constructor" },
      ] :
      [],
    in_args: [],
    returned: [],
  },
];