쿼리 평가 모델 상세

이 장에서는 쿼리의 기반이 되는 추상 모델을 더 깊이 살펴봅니다. 구현 세부 사항까지 다루지는 않으며, 그 밑바탕에 있는 논리를 설명하고자 합니다. 따라서 여기에 나오는 예제는 간추리고 단순화한 것이며, 컴파일러 내부 API를 그대로 반영하지는 않습니다.

쿼리란 무엇입니까?

추상적으로 보면, 우리는 주어진 크레이트에 대한 컴파일러의 지식을 하나의 “데이터베이스“로 보며, 쿼리는 그에 관해 컴파일러에 질문하는 방법입니다. 즉, 우리는 컴파일러의 “데이터베이스“에 사실을 “쿼리“합니다.

그런데 이 컴파일러 데이터베이스에는 특별한 점이 있습니다. 처음에는 비어 있다가 쿼리가 실행될 때 필요에 따라 채워진다는 점입니다. 따라서 쿼리는 데이터베이스에 아직 결과가 없을 때 그 결과를 어떻게 계산하는지 알고 있어야 합니다. 이를 위해 쿼리는 다른 쿼리와, 데이터베이스가 생성될 때 미리 채워지는 특정 입력 값에 접근할 수 있습니다.

따라서 쿼리는 다음과 같은 요소로 구성됩니다.

• 쿼리를 식별하는 이름
• 무엇을 조회하려는지 지정하는 “키”
• 어떤 종류의 결과를 내는지 지정하는 결과 타입
• 데이터베이스에 결과가 아직 없을 때 결과를 어떻게 계산할지 지정하는 함수인 “프로바이더”

예를 들어, type_of 쿼리의 이름은 type_of이고, 쿼리 키는 타입을 알고자 하는 항목을 식별하는 DefId이며, 결과 타입은 Ty<'tcx>이고, 프로바이더는 쿼리 키와 나머지 데이터베이스에 대한 접근이 주어졌을 때 키로 식별되는 항목의 타입을 계산할 수 있는 함수입니다.

그러므로 어떤 의미에서 쿼리는 쿼리 키를 그에 대응하는 결과로 매핑하는 함수일 뿐입니다. 하지만 이것이 건전(sound)하려면 몇 가지 제약을 적용해야 합니다.

• 키와 결과는 불변 값이어야 합니다.
• 프로바이더 함수는 같은 키에 대해 항상 같은 결과를 내야 한다는 의미에서 순수 함수여야 합니다.
• 프로바이더 함수가 받는 매개변수는 키와 “쿼리 컨텍스트”(나머지 “데이터베이스“에 대한 접근을 제공합니다)에 대한 참조뿐입니다.

데이터베이스는 쿼리가 호출됨에 따라 지연(lazy) 방식으로 구축됩니다. 쿼리 프로바이더는 다른 쿼리를 호출하며, 그 결과는 이미 캐시되어 있거나 다른 쿼리 프로바이더를 호출하여 계산됩니다. 이러한 쿼리 프로바이더 호출은 개념적으로 방향성 비순환 그래프(DAG)를 이루며, 그 잎(leaf)에는 쿼리 컨텍스트가 생성될 때 이미 알려져 있는 입력 값이 있습니다.

캐싱/메모이제이션

쿼리 호출 결과는 “메모이제이션“됩니다. 즉, 쿼리 컨텍스트는 결과를 내부 테이블에 캐시하고, 같은 쿼리 키로 쿼리가 다시 호출되면 프로바이더를 다시 실행하는 대신 캐시에서 결과를 반환합니다.

이 캐싱은 쿼리 엔진을 효율적으로 만드는 데 매우 중요합니다. 메모이제이션이 없어도 시스템은 여전히 건전하겠지만(즉, 같은 결과를 내겠지만) 같은 계산이 계속해서 반복될 것입니다.

메모이제이션은 쿼리 프로바이더가 순수 함수여야 하는 주된 이유 중 하나입니다. 프로바이더 함수를 호출할 때마다 (어떤 전역 가변 상태에 접근하기 때문에) 다른 결과가 나올 수 있다면, 그 결과를 메모이제이션할 수 없을 것입니다.

입력 데이터

쿼리 컨텍스트는 생성될 때 아직 비어 있습니다. 실행된 쿼리도 없고, 캐시된 결과도 없습니다. 하지만 컨텍스트는 이미 “입력” 데이터, 즉 컨텍스트가 생성되기 전에 계산되었으며 쿼리가 계산을 수행하기 위해 접근할 수 있는 불변 데이터 조각에 대한 접근을 제공합니다.

입력이 없다면 쿼리는 결과를 계산할 근거가 전혀 없는 공백 속에 놓이게 됩니다(쿼리 프로바이더는 다른 쿼리와 컨텍스트에만 접근할 수 있으며, 그 밖의 외부 상태나 정보에는 접근할 수 없다는 점을 기억하십시오).

쿼리 프로바이더 입장에서는 입력 데이터와 다른 쿼리의 결과가 완전히 똑같아 보입니다. 프로바이더는 컨텍스트에 “X의 값을 달라“고 요청할 뿐입니다. 입력 데이터는 불변이므로, 쿼리 결과와 마찬가지로 프로바이더는 입력 데이터가 서로 다른 쿼리 호출 사이에서도 동일하다고 믿을 수 있습니다.

몇 가지 쿼리의 실행 추적 예시

쿼리 호출로 이루어진 이 DAG는 어떻게 생겨나는 것입니까? 어느 시점에 컴파일러 드라이버가 아직 비어 있는 쿼리 컨텍스트를 생성합니다. 그런 다음 드라이버는 쿼리 시스템 외부에서 자신의 작업을 수행하는 데 필요한 쿼리를 호출합니다. 이는 대략 다음과 같습니다:

fn compile_crate() {
    let cli_options = ...;
    let hir_map = ...;

    // Create the query context `tcx`
    let tcx = TyCtxt::new(cli_options, hir_map);

    // Do type checking by invoking the type check query
    tcx.type_check_crate();
}

type_check_crate 쿼리 프로바이더는 대략 다음과 같은 모습입니다.

fn type_check_crate_provider(tcx, _key: ()) {
    let list_of_hir_items = tcx.hir_map.list_of_items();

    for item_def_id in list_of_hir_items {
        tcx.type_check_item(item_def_id);
    }
}

type_check_crate 쿼리가 입력 데이터(tcx.hir_map.list_of_items())에 접근하고 다른 쿼리(type_check_item)를 호출하는 것을 볼 수 있습니다. type_check_item 호출은 그 자체로 입력 데이터에 접근하거나 다른 쿼리를 호출하거나 둘 다 수행하므로, 결국 쿼리 호출의 DAG는 처음 실행된 노드로부터 거꾸로 구축됩니다:

         (2)                                                 (1)
  list_of_all_hir_items <----------------------------- type_check_crate()
                                                               |
    (5)             (4)                  (3)                   |
  Hir(foo) <--- type_of(foo) <--- type_check_item(foo) <-------+
                                      |                        |
                    +-----------------+                        |
                    |                                          |
    (7)             v  (6)                  (8)                |
  Hir(bar) <--- type_of(bar) <--- type_check_item(bar) <-------+

// (x) denotes invocation order

또한 쿼리 결과를 캐시에서 읽을 수 있는 경우가 많다는 것도 볼 수 있습니다. type_of(bar)는 type_check_item(foo)를 위해 계산되었으므로, type_check_item(bar)가 이를 필요로 할 때에는 이미 캐시에 들어 있습니다.

쿼리 결과는 컨텍스트가 살아 있는 동안 쿼리 컨텍스트에 캐시된 채로 유지됩니다. 따라서 컴파일러 드라이버가 나중에 다른 쿼리를 호출하더라도 위의 그래프는 여전히 존재하며, 이미 실행된 쿼리를 다시 수행할 필요가 없습니다.

순환

앞에서 쿼리 호출이 DAG를 형성한다고 말했습니다. 그러나 예를 들어 다음과 같은 쿼리 프로바이더를 두면 순환 그래프를 쉽게 만들 수 있습니다.

fn cyclic_query_provider(tcx, key) -> u32 {
  // Invoke the same query with the same key again
  tcx.cyclic_query(key)
}

쿼리 프로바이더는 일반 함수이므로, 이 코드는 예상대로 동작합니다. 즉, 평가가 무한 재귀에 빠집니다. 이와 같은 쿼리는 별로 쓸모도 없습니다. 하지만 때로는 특정 종류의 잘못된 사용자 입력으로 인해 쿼리가 순환적으로 호출될 수 있습니다. 쿼리 엔진에는 동일한 입력 인자로 쿼리가 순환 호출되는지 검사하는 기능이 포함되어 있습니다. 그리고 순환은 복구할 수 없는 오류이므로, 쿼리 엔진은 사람이 읽기 쉽도록 작성된 “순환 오류(cycle error)” 메시지와 함께 실행을 중단합니다.

한때 컴파일러에는 “순환 복구(cycle recovery)“라는 개념이 있었습니다. 즉, 쿼리 실행을 “시도“해 보고, 그 결과 순환이 발생하면 다른 방식으로 진행할 수 있었습니다. 하지만 이것이 이론적으로, 특히 증분 컴파일과 관련하여 어떤 결과를 낳는지가 완전히 명확하지 않았기 때문에 나중에 제거되었습니다.

“훔치기(Steal)” 쿼리

일부 쿼리는 결과가 Steal<T> 구조체로 감싸여 있습니다. 이러한 쿼리는 한 가지 예외를 제외하면 일반 쿼리와 완전히 똑같이 동작합니다. 그 예외란 결과가 어느 시점에 캐시에서 “도난“당할 것으로 예상된다는 점입니다. 이는 프로그램의 다른 부분이 결과의 소유권을 가져가며, 이후로는 그 결과에 더 이상 접근할 수 없다는 뜻입니다.

이 훔치기 메커니즘은 순전히 성능 최적화를 위해 존재합니다. 일부 결괏값(예: 함수의 MIR)은 복제하는 데 비용이 너무 크기 때문입니다. 결과 훔치기는 쿼리 결과가 불변이어야 한다는 조건을 위반하는 것처럼 보일 수 있지만(결국 결괏값을 캐시 밖으로 옮기는 것이기 때문입니다), 그 변경이 관찰될 수 없는 한 문제가 없습니다. 이는 두 가지를 통해 달성됩니다.

• 결과를 훔치기 전에, 그 결과를 읽어야 할 가능성이 있는 모든 쿼리를 반드시 미리 실행합니다. 이는 해당 쿼리들을 호출하여 수동으로 수행해야 합니다.
• 쿼리가 훔쳐진 결과에 접근하려고 할 때마다 ICE(Internal Compiler Error, 내부 컴파일러 오류)를 발생시켜 이러한 상황이 눈에 띄지 않고 지나가는 일이 없도록 합니다.

수동 개입이 필요하므로 이는 이상적인 구성이 아닙니다. 따라서 드물게, 그리고 어떤 쿼리가 주어진 결과에 접근할 수 있는지 잘 알려진 경우에만 사용해야 합니다. 그러나 실제로는 훔치기가 유지 보수에 큰 부담이 되지는 않았습니다.

요약하면, “훔치기 쿼리“는 통제된 방식으로 일부 규칙을 어깁니다. 아무것도 조용히 잘못되는 일이 없도록 보장하는 검사가 마련되어 있습니다.