쿼리: 요구 기반 컴파일

컴파일러 개요에서 설명한 것처럼, Rust 컴파일러는 여전히( 2021년 7월 기준) 전통적인 “패스 기반” 구성에서 “요구 기반” 시스템으로 전환하는 중입니다.

컴파일러의 “쿼리 시스템“은 rustc의 요구 기반 구조의 핵심입니다. 완전히 독립적인 패스(파싱, 타입 검사 등) 대신, 함수와 비슷한 일련의 쿼리가 입력 소스에 관한 정보를 계산합니다. 예를 들어, type_of라는 쿼리가 있는데, 이 쿼리는 어떤 항목의 DefId가 주어지면 그 항목의 타입을 계산하여 반환합니다.

쿼리 실행은 메모이제이션됩니다. 쿼리를 처음 호출하면 실제로 계산을 수행하지만, 그다음부터는 해시 테이블에서 결과가 반환됩니다. 게다가 쿼리 실행은 증분 계산과도 잘 맞아떨어집니다. 대략적인 아이디어는, 쿼리를 호출했을 때 디스크에 저장된 데이터를 불러와서 결과를 반환할 수도 있다는 것입니다.¹

쿼리를 실행할 때, 그 쿼리가 어떤 다른 쿼리에 의존하는지도 (런타임에!) 알아냅니다. 이를 통해 크레이트의 의존성 그래프를 구성할 수 있으며, 이 그래프 덕분에 증분 계산의 건전성이 보장됩니다.

궁극적으로는 컴파일러의 전체 제어 흐름이 쿼리 기반으로 동작하기를 원합니다. 사실상 크레이트의 컴파일을 수행하는 최상위 쿼리(compile) 하나가 존재하게 되며, 이 쿼리는 다시 그 크레이트에 관한 정보를 끝에서부터 요구합니다.

예를 들면 다음과 같습니다.

compile 쿼리는 코드 생성 단위(즉, LLVM이 컴파일해야 하는 모듈)의 목록을 요구할 수 있습니다.
하지만 코드 생성 단위의 목록을 계산하려면 Rust 소스에 정의된 모든 모듈의 목록을 반환하는 하위 쿼리를 호출하게 됩니다.
그 쿼리는 다시 HIR을 요청하는 무언가를 호출하게 됩니다.
이런 과정이 점점 더 앞 단계로 거슬러 올라가다가 결국 실제 파싱을 수행하는 데까지 이릅니다.

이 구상이 완전히 실현된 것은 아니지만, 현재 컴파일러의 상당 부분(예를 들어 MIR 생성)은 정확히 이런 방식으로 동작합니다.

쿼리 호출하기

쿼리를 호출하는 방법은 간단합니다. TyCtxt(“타입 컨텍스트”) 구조체는 정의된 각 쿼리에 대한 메서드를 제공합니다. 예를 들어, type_of 쿼리를 호출하려면 다음과 같이 하기만 하면 됩니다.

let ty = tcx.type_of(some_def_id);

컴파일러가 쿼리를 실행하는 방식

그렇다면 쿼리 메서드를 호출할 때 무슨 일이 일어나는지 궁금할 수 있습니다. 답은 이렇습니다. 컴파일러는 각 쿼리마다 캐시를 유지합니다. 쿼리가 이미 실행된 적이 있다면 답은 간단합니다. 캐시에서 반환값을 복제하여 반환합니다(따라서 쿼리의 반환 타입은 적은 비용으로 복제할 수 있도록 해야 합니다. 필요하다면 Rc를 넣으십시오).

그러나 쿼리가 캐시에 없다면, 컴파일러는 해당하는 프로바이더 함수를 호출합니다. 프로바이더는 특정 모듈에 구현된 함수로, 컴파일러 초기화 과정에서 Providers 구조체(로컬 크레이트 쿼리용) 또는 ExternProviders 구조체(외부 크레이트 쿼리용)에 수동으로 등록됩니다. 매크로 시스템이 두 구조체를 모두 생성하며, 이 구조체들은 모든 쿼리 구현에 대한 함수 테이블 역할을 합니다. 각 필드는 실제 프로바이더를 가리키는 함수 포인터입니다.

참고: Providers 구조체와 ExternProviders 구조체는 모두 매크로로 생성되며, 모든 쿼리 구현을 위한 함수 테이블 역할을 합니다. 이들은 Rust 트레이트가 아니라 함수 포인터 필드를 가진 평범한 구조체입니다.

프로바이더는 크레이트별로 정의됩니다. 컴파일러는 적어도 개념적으로는 모든 크레이트에 대한 프로바이더 테이블을 내부적으로 유지합니다. 프로바이더에는 두 가지 집합이 있습니다:

로컬 크레이트(즉, 현재 컴파일 중인 크레이트)에 대한 쿼리를 위한 Providers 구조체
외부 크레이트(즉, 로컬 크레이트의 의존성)에 대한 쿼리를 위한 ExternProviders 구조체

쿼리가 대상으로 하는 크레이트를 결정하는 것은 쿼리의 종류가 아니라 키라는 점에 유의하십시오. 예를 들어 tcx.type_of(def_id)를 호출하면, def_id가 어떤 크레이트를 가리키는지에 따라 로컬 쿼리가 될 수도 있고 외부 쿼리가 될 수도 있습니다(이것이 어떻게 동작하는지에 대한 자세한 내용은 self::keys::QueryKey 트레이트를 참고하십시오).

프로바이더는 항상 같은 시그니처를 가집니다:

fn provider<'tcx>(
    tcx: TyCtxt<'tcx>,
    key: QUERY_KEY,
) -> QUERY_RESULT {
    ...
}

프로바이더는 tcx와 쿼리 키라는 두 인자를 받습니다. 프로바이더는 쿼리의 결과를 반환합니다.

참고: 대부분의 rustc_* 크레이트는 로컬 프로바이더만 제공합니다. 거의 모든 외부 프로바이더는 결국 크레이트 메타데이터에서 정보를 불러오는 rustc_metadata 크레이트를 거치게 됩니다. 하지만 경우에 따라 로컬 크레이트와 외부 크레이트 모두에 대한 쿼리를 제공하는 크레이트도 있으며, 이 경우 해당 크레이트는 wasm_import_module_map을 통해 rustc_driver가 호출할 수 있는 provide 함수와 provide_extern 함수를 모두 정의합니다.

프로바이더 설정 방식

tcx가 생성될 때, 생성하는 쪽에서 rustc_middle::util의 Providers 구조체를 사용하여 tcx에 로컬 프로바이더와 외부 프로바이더를 모두 전달합니다. 이 구조체는 로컬 프로바이더와 외부 프로바이더를 모두 포함합니다:

pub struct Providers {
    pub queries: crate::query::Providers,        // Local crate providers
    pub extern_queries: crate::query::ExternProviders,  // External crate providers
    pub hooks: crate::hooks::Providers,
}

이 프로바이더 구조체들은 각각 매크로로 생성되며, 해당 쿼리에 대한 함수 포인터를 담고 있습니다.

프로바이더는 어떻게 등록됩니까?

util::Providers 구조체는 컴파일러 초기화 중에 rustc_interface 크레이트가 DEFAULT_QUERY_PROVIDERS 정적 변수로부터 채웁니다. 실제 프로바이더 함수는 여러 rustc_* 크레이트(rustc_middle, rustc_hir_analysis 등)에 걸쳐 정의되어 있습니다.

프로바이더를 등록하기 위해 각 크레이트는 다음과 같은 형태의 provide 함수를 노출합니다:

pub fn provide(providers: &mut query::Providers) {
    *providers = query::Providers {
        type_of,
        // ... add more providers here
        ..*providers
    };
}

이 함수는 util::Providers가 아니라 query::Providers를 받는다는 점에 유의하십시오. query::Providers만 받는 것이 아닌 provide 함수가 필요한 경우는 극히 드뭅니다. util::Providers의 queries 필드 외의 부분도 갱신해야 한다면 대신 util::Providers를 받을 수 있습니다:

pub fn provide(providers: &mut rustc_middle::util::Providers) {
    providers.queries.type_of = type_of;
    // ... add more local providers here

    providers.extern_queries.type_of = extern_type_of;
    // ... add more external providers here

    providers.hooks.some_hook = some_hook;
    // ... add more hooks here
}

새 프로바이더 추가하기

fubar라는 새 쿼리를 추가하려 한다고 가정해 봅시다. 이 절에서는 프로바이더를 연결하는 방법을 중점적으로 다룹니다. 거대한 rustc_queries! 매크로에서 쿼리 자체를 선언하는 방법은 아래의 새 쿼리 추가하기를 참고하십시오.

실제로는 보통 다음과 같이 합니다:

어떤 크레이트가 쿼리를 “소유“할지 결정합니다(예: rustc_hir_analysis, rustc_mir_build 또는 다른 rustc_* 크레이트).
해당 크레이트에서 기존 provide 함수를 찾습니다:
```
pub fn provide(providers: &mut query::Providers) {
    // existing assignments
}
```
해당 함수가 이미 있다면 이를 확장하여 새 쿼리의 필드를 설정하면 됩니다. 크레이트에 아직 provide 함수가 없다면 하나를 추가하고, 초기화 과정에서 실제로 호출되도록 rustc_interface 크레이트의 DEFAULT_QUERY_PROVIDERS에 포함되어 있는지 확인하십시오(위의 논의를 참고하십시오).

프로바이더 함수 자체를 구현하십시오.

fn fubar<'tcx>(tcx: TyCtxt<'tcx>, key: LocalDefId) -> Fubar<'tcx> { ... }

크레이트의 provide 함수에 이를 등록하십시오:

pub fn provide(providers: &mut query::Providers) {
    *providers = query::Providers {
        fubar,
        ..*providers
    };
}

쿼리가 외부 크레이트 메타데이터와 상호작용하는 방식

외부 크레이트(즉, 의존성)에 대해 쿼리가 수행되면, 쿼리 시스템은 해당 크레이트의 메타데이터에서 정보를 불러와야 합니다. 이 작업은 rustc_metadata 크레이트가 처리하며, 이 크레이트는 .rmeta 파일에 저장된 정보를 디코딩하고 제공하는 역할을 맡습니다.

이 과정은 다음과 같이 동작합니다:

쿼리가 수행되면 쿼리 시스템은 먼저 def_id.krate == LOCAL_CRATE인지 확인하여 DefId가 로컬 크레이트를 가리키는지 외부 크레이트를 가리키는지 검사합니다. 이를 통해 Providers의 로컬 프로바이더를 사용할지, ExternProviders의 외부 프로바이더를 사용할지가 결정됩니다.

외부 크레이트의 경우, 쿼리 시스템은 ExternProviders 구조체에서 프로바이더를 찾습니다. rustc_metadata 크레이트는 rustc_metadata/src/rmeta/decoder/cstore_impl.rs에 있는 provide_extern 함수를 통해 이러한 외부 프로바이더를 등록합니다. 예를 들면 다음과 같습니다:

#![allow(unused)]
fn main() {
pub fn provide_extern(providers: &mut ExternProviders) {
    providers.foo = |tcx, def_id| {
        // Load and decode metadata for external crate
        let cdata = CStore::from_tcx(tcx).get_crate_data(def_id.krate);
        cdata.foo(def_id.index)
    };
    // Register other external providers...
}
}

메타데이터는 .rmeta 파일에 바이너리 형식으로 저장되며, 여기에는 타입, 함수 시그니처, 트레이트 구현을 비롯해 컴파일러가 필요로 하는 기타 정보 등 외부 크레이트에 대해 미리 계산된 정보가 담겨 있습니다. 외부 쿼리가 수행되면 rustc_metadata 크레이트는 다음을 수행합니다:
- 외부 크레이트의 .rmeta 파일을 불러옵니다
- Decodable 트레이트를 사용하여 메타데이터를 디코딩합니다
- 디코딩된 정보를 쿼리 시스템에 반환합니다

이 방식은 외부 크레이트를 다시 컴파일하지 않아도 되게 하고, 의존하는 크레이트를 더 빠르게 컴파일할 수 있게 하며, 증분 컴파일이 크레이트 경계를 넘어 동작할 수 있게 합니다. 간단한 예를 들면, 외부 크레이트에 정의된 타입에 대해 tcx.type_of(def_id)를 호출하면 쿼리 시스템은 다음과 같이 동작합니다:

def_id.krate != LOCAL_CRATE를 검사하여 def_id가 외부 크레이트를 가리킨다는 것을 감지합니다
rustc_metadata가 등록한 ExternProviders에서 적절한 프로바이더를 호출합니다
프로바이더는 외부 크레이트의 메타데이터에서 타입 정보를 불러와 디코딩합니다
디코딩된 타입을 호출자에게 반환합니다

이 때문에 대부분의 rustc_* 크레이트는 로컬 프로바이더만 제공하면 됩니다. 외부 프로바이더는 메타데이터 시스템이 처리합니다. 유일한 예외는 크레이트가 외부 쿼리에 대해 특별한 처리를 제공해야 하는 경우이며, 이때는 로컬 프로바이더와 외부 프로바이더를 모두 구현합니다.

크레이트 간에 동작해야 하는 새 쿼리를 정의할 때, 그 쿼리가 rustc_queries!에 나열되었다는 이유만으로 자동으로 크레이트 간 쿼리가 되지는 않습니다. 일반적으로 다음 작업이 필요합니다:

적절한 수정자(예를 들어 디스크에 캐시되는지 여부)와 함께 rustc_queries!에 쿼리를 추가하십시오.
해당 쿼리를 소유한 크레이트에 로컬 프로바이더를 구현하고, 그 크레이트의 provide 함수를 통해 등록하십시오.
provide_extern을 통해 rustc_metadata에 외부 프로바이더를 추가하고, 쿼리 결과가 크레이트 메타데이터에 인코딩 및 디코딩되도록 하십시오.

이러한 크레이트 간 쿼리를 도입하는 예시는 rust-lang/rust 저장소의 커밋 996a185에서 찾을 수 있습니다.

새 쿼리 추가하기

새 쿼리는 어떻게 추가합니까? 쿼리 정의는 두 단계로 이루어집니다:

쿼리 이름, 인자, 설명을 선언하십시오.
필요한 곳에 쿼리 프로바이더를 제공하십시오.

쿼리 이름과 인자를 선언하려면 compiler/rustc_middle/src/query/mod.rs에 있는 큰 매크로 호출에 항목을 하나 추가하기만 하면 됩니다. 그런 다음 여기에 내부용 설명을 담은 문서 주석을 추가해야 합니다. 그런 다음 쿼리에 대한 사용자용 설명을 담은 desc 속성을 제공하십시오. desc 속성은 쿼리 순환이 발생했을 때 사용자에게 표시됩니다.

대략 다음과 같은 모습입니다:

rustc_queries! {
    /// Records the type of every item.
    query type_of(key: DefId) -> Ty<'tcx> {
        desc { |tcx| "computing the type of `{}`", tcx.def_path_str(key) }
        cache_on_disk
        separate_provide_extern
    }
    ...
}

쿼리 정의는 다음과 같은 형식을 가집니다:

query type_of(key: DefId) -> Ty<'tcx> { ... }
^^^^^ ^^^^^^^      ^^^^^     ^^^^^^^^   ^^^
|     |            |         |          |
|     |            |         |          query modifiers
|     |            |         result type
|     |            query key type
|     name of query
query keyword

이 요소들을 하나씩 살펴봅시다:

쿼리 키워드: 쿼리 정의의 시작을 나타냅니다.
쿼리 이름: 쿼리 메서드의 이름(tcx.type_of(..))입니다. 이 쿼리를 나타내기 위해 생성될 구조체(ty::queries::type_of)의 이름으로도 사용됩니다.
쿼리 키 타입: 이 쿼리에 전달되는 인자의 타입입니다. 이 타입은 ty::query::keys::QueryKey 트레이트를 구현해야 하며, 이 트레이트는 (예를 들어) 해당 타입을 크레이트에 매핑하는 방법 등을 정의합니다.
쿼리의 결과 타입: 이 쿼리가 생성하는 타입입니다. 이 타입은 (a) RefCell이나 그 밖의 내부 가변성을 사용하지 않아야 하며 (b) 저렴하게 복제할 수 있어야 합니다. 단순하지 않은 데이터 타입에는 인터닝을 하거나 Rc 또는 Arc를 사용하는 것을 권장합니다.²
쿼리 수식자: 쿼리가 처리되는 방식을 (주로 증분 컴파일과 관련하여) 조정하는 다양한 플래그와 옵션입니다.

따라서 쿼리를 추가하려면 다음과 같이 하십시오:

위의 형식을 사용하여 rustc_queries!에 항목을 추가하십시오.
적절한 provide 메서드를 수정하여 프로바이더를 연결하십시오. 또는 필요하다면 새 메서드를 추가하고 rustc_driver가 그 메서드를 호출하는지 확인하십시오.

외부 링크

관련 설계 아이디어 및 추적 이슈:

설계 문서: On-demand Rustc incremental design doc
추적 이슈: 컴파일러의 “Red/Green” 의존성 추적

추가 논의 및 이슈:

증분 컴파일 상세 장에서는 쿼리가 무엇이며 어떻게 동작하는지 더 깊이 있게 설명합니다. 직접 쿼리를 작성하려는 경우 읽어 볼 만한 장입니다. ↩
이 규칙의 유일한 예외는 ty::steal::Steal 타입으로, MIR을 제자리에서 저렴하게 수정하는 데 사용됩니다. 자세한 내용은 Steal의 정의를 참조하십시오. @rust-lang/compiler에 알리지 않고 Steal을 새로 사용하는 코드를 추가해서는 안 됩니다. ↩

Keyboard shortcuts

Rust 컴파일러 개발 가이드