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

정준 쿼리

트레이트 시스템의 “시작점“은 정준 쿼리입니다(이는 일반적인 의미의 쿼리, 즉 답을 알고 싶은 무언가라는 의미이기도 하고, rustc 특유의 의미의 쿼리이기도 합니다). 타입 검사기나 시스템의 다른 부분이 자신의 작업을 수행하는 과정에서 어떤 타입에 대해 어떤 트레이트가 구현되어 있는지(예: u32: Debug가 참인지) 알고 싶어 할 수 있다는 것이 핵심입니다. 또는 어떤 연관 타입을 정규화하고 싶어 할 수도 있습니다.

이 절에서는 상당히 높은 추상화 수준에서 쿼리를 다룹니다. 하위 절에서는 이러한 아이디어가 rustc에서 어떻게 구현되는지 좀 더 자세히 살펴봅니다.

전통적인 대화형 Prolog 쿼리

전통적인 Prolog 시스템에서는 쿼리를 시작하면 솔버가 실행되어 찾을 수 있는 모든 가능한 답을 제공하기 시작합니다. 예를 들어 다음과 같은 쿼리가 주어졌다고 합시다:

?- Vec<i32>: AsRef<?U>

솔버는 다음과 같이 답할 수 있습니다:

Vec<i32>: AsRef<[i32]>
    continue? (y/n)

이 continue 부분이 흥미롭습니다. Prolog의 아이디어는 솔버가 쿼리를 참으로 만드는 모든 가능한 인스턴스화를 찾는다는 것입니다. 이 경우 ?U = [i32]로 인스턴스화하면 쿼리는 참이 됩니다(전통적인 Prolog 인터페이스는 ?U의 값을 직접 알려 주지 않지만, 응답을 원래 쿼리와 단일화하여 값을 추론할 수 있다는 점에 유의하십시오. Rust의 솔버는 그 대신 치환을 돌려줍니다). y를 누르면 솔버는 또 다른 가능한 답을 줄 수 있습니다:

Vec<i32>: AsRef<Vec<i32>>
    continue? (y/n)

이 답은 AsRef에 대한 반사적 impl(impl<T> AsRef<T> for T)이 존재한다는 사실에서 비롯됩니다. y를 다시 누르면 부정적인 응답을 받을 수도 있습니다:

no

물론 어떤 경우에는 가능한 답이 전혀 없을 수도 있으며, 이때 솔버는 곧바로 no를 돌려줍니다:

?- Box<i32>: Copy
    no

어떤 경우에는 응답이 무한히 많을 수도 있습니다. 예를 들어 다음 쿼리를 주고 계속 y를 누르면, 솔버는 끝없이 답을 돌려줍니다:

?- Vec<?U>: Clone
    Vec<i32>: Clone
        continue? (y/n)
    Vec<Box<i32>>: Clone
        continue? (y/n)
    Vec<Box<Box<i32>>>: Clone
        continue? (y/n)
    Vec<Box<Box<Box<i32>>>>: Clone
        continue? (y/n)

짐작할 수 있듯이, 솔버는 우리가 멈추라고 하거나 메모리가 바닥날 때까지 신나게 Box를 한 겹씩 계속 추가합니다.

또 하나 흥미로운 점은 쿼리에 여전히 변수가 남아 있을 수 있다는 것입니다. 예를 들면 다음과 같습니다.

?- Rc<?T>: Clone

다음과 같은 답을 낼 수 있습니다:

Rc<?T>: Clone
    continue? (y/n)

결국 Rc<?T>는 ?T가 어떤 타입이든 상관없이 참입니다.

rustc의 트레이트 쿼리

rustc의 트레이트 쿼리는 다소 다르게 동작합니다. 모든 가능한 답을 나열하려 하는 대신, 모호하지 않은 답을 찾습니다. 특히 타입 변수의 값을 알려 준다는 것은, 현재의 impl과 where 절 집합이 주어졌을 때 그것이 증명 가능하면서 사용할 수 있는 유일한 인스턴스화라는 뜻입니다.

rustc에서 트레이트 쿼리에 대한 응답은 일반적으로 Result<QueryResult<T>, NoSolution>입니다(여기서 T는 쿼리 자체에 따라 조금씩 달라집니다). Err(NoSolution) 경우는 쿼리가 거짓이었고 답이 없었음을 나타냅니다(예: Box<i32>: Copy). 그렇지 않은 경우, QueryResult는 우리가 찾아낸 가능한 답(들)에 대한 정보를 돌려줍니다. 이것은 네 부분으로 구성됩니다.

  • 확실성(Certainty): 이 답을 얼마나 확신하는지 알려 줍니다. 이것은 두 가지 값을 가질 수 있습니다.
    • Proven은 결과가 참임이 알려져 있다는 뜻입니다.
      • 예를 들어 Vec<i32>: Clone이나 Rc<?T>: Clone을 증명하려 할 때 이러한 결과가 나올 수 있습니다.
    • Ambiguous는 참인지 또는 거짓인지 아직 증명할 수 없는 것이 있었다는 뜻이며, 일반적으로 더 많은 타입 정보가 필요했기 때문입니다. (곧 예시를 살펴보겠습니다.)
      • Vec<?T>: Clone을 증명하려 할 때 이러한 결과가 나올 수 있습니다.
  • 변수 값(Var values): 원래 쿼리에 나타난 바인딩되지 않은 각 추론 변수(?T 등)의 값입니다. (Prolog에서는 이것들을 추론해야 했다는 점을 기억하십시오.)
    • 아래 예시에서 보겠지만, Ambiguous인 경우에도 변수 값을 돌려받을 수 있습니다.
  • 영역 제약(Region constraints): 입력으로 제공한 라이프타임들 사이에 성립해야 하는 관계입니다. 여기서는 이것들을 무시하겠습니다.
  • 값(Value): 쿼리 결과에는 T 타입의 값도 함께 제공됩니다. 연관 타입 정규화와 같은 일부 특수한 쿼리에서는 이 값이 추가 결과를 전달하는 데 사용되지만, 대개는 그저 ()입니다.

예시

각 부분이 무엇을 의미하는지 알아보기 위해 예시 쿼리를 살펴봅시다. Borrow 트레이트를 생각해 보십시오. 이 트레이트에는 여러 impl이 있으며, 그중에는 다음 두 가지가 있습니다(명확성을 위해 Sized 바운드를 명시적으로 적었습니다).

impl<T> Borrow<T> for T where T: ?Sized
impl<T> Borrow<[T]> for Vec<T> where T: Sized

예시 1. 다음의 (다소 인위적인) 코드를 타입 검사한다고 생각해 보십시오.

fn foo<A, B>(a: A, vec_b: Option<B>) where A: Borrow<B> { }

fn main() {
    let mut t: Vec<_> = vec![]; // Type: Vec<?T>
    let mut u: Option<_> = None; // Type: Option<?U>
    foo(t, u); // Example 1: requires `Vec<?T>: Borrow<?U>`
    ...
}

주석에서 알 수 있듯이, 먼저 두 변수 t와 u를 만듭니다. t는 빈 벡터이고 u는 None 옵션입니다. 이 두 변수 모두 타입에 바인딩되지 않은 추론 변수를 가지고 있습니다. ?T는 벡터 t의 요소를 나타내고 ?U는 옵션 u에 저장된 값을 나타냅니다. 다음으로 foo를 호출합니다. foo의 시그니처를 인자와 비교하면 결국 A = Vec<?T>와 B = ?U를 얻게 됩니다. 따라서 foo의 where 절은 Vec<?T>: Borrow<?U>를 요구합니다. 이것이 바로 첫 번째 예시 트레이트 쿼리입니다.

Vec<?T>: Borrow<?U> 쿼리에는 가능한 해가 많이 있습니다. 예를 들면 다음과 같습니다.

  • ?U = Vec<?T>,
  • ?U = [?T],
  • ?T = u32, ?U = [u32]
  • 등이 있습니다.

따라서 돌려받는 결과는 다음과 같습니다(영역 제약과 “값“은 무시하겠습니다).

  • 확실성: Ambiguous – 이것이 성립하는지 아직 확실하지 않습니다
  • 변수 값: [?T = ?T, ?U = ?U] – 변수의 값에 대해 아무것도 알아내지 못했습니다

요컨대, 이 쿼리 결과는 이 트레이트가 증명되는지에 대해 무언가를 말하기에는 아직 이르다는 뜻입니다. 타입 검사 중에 이것은 즉시 오류가 되지 않습니다. 대신 타입 검사기는 이 요구 사항(Vec<?T>: Borrow<?U>)을 보류해 두고 기다립니다. 다음 예제에서 보겠지만, ?T와 ?U가 결국 다른 출처로부터 제약을 받게 될 수도 있으며, 그런 경우 트레이트 쿼리를 다시 시도할 수 있습니다.

예제 2. 이제 앞의 예제를 조금 확장하여 u에 값을 대입해 보겠습니다:

fn foo<A, B>(a: A, vec_b: Option<B>) where A: Borrow<B> { }

fn main() {
    // What we saw before:
    let mut t: Vec<_> = vec![]; // Type: Vec<?T>
    let mut u: Option<_> = None; // Type: Option<?U>
    foo(t, u); // `Vec<?T>: Borrow<?U>` => ambiguous

    // New stuff:
    u = Some(vec![]); // ?U = Vec<?V>
}

이 대입의 결과로 u의 타입은 Option<Vec<?V>>로 강제되며, 여기서 ?V는 벡터의 원소 타입을 나타냅니다. 이는 다시 ?U가 Vec<?V>로 단일화된다는 것을 의미합니다.

타입 검사기가 앞서 보았던 “아직 증명되지 않은” 트레이트 의무인 Vec<?T>: Borrow<?U>를 다시 살펴보기로 한다고 가정해 봅시다. ?U는 더 이상 바인딩되지 않은 추론 변수가 아니며, 이제 Vec<?V>라는 값을 가집니다. 따라서 그 값으로 쿼리를 “갱신“하면 다음과 같은 결과를 얻습니다:

Vec<?T>: Borrow<Vec<?V>>

이번에는 적용되는 impl이 반사적(reflexive) impl 하나뿐입니다:

impl<T> Borrow<T> for T where T: ?Sized

따라서 트레이트 검사기는 다음과 같이 답할 것입니다:

  • 확실성: Proven
  • 변수 값: [?T = ?T, ?V = ?T]

여기서 이 결과는 의무가 성립함을 실제로 증명했으며, ?T와 ?V가 같은 타입이라는 것도 알게 되었다는 뜻입니다(다만 그 타입이 무엇인지는 아직 모릅니다!).

(실제로는 함수가 여기서 끝나므로, 타입 검사기는 이 시점에서 오류를 낼 것입니다. t와 u의 원소 타입이 서로 같다는 것은 알려져 있지만, 그 타입 자체는 여전히 알려지지 않았기 때문입니다.)