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

트레이트 해석(기존 방식)

이 장에서는 트레이트 해결의 일반적인 과정을 설명하고, 쉽게 드러나지 않는 몇 가지 사항을 짚어 봅니다.

참고: 이 장(과 그 하위 장)은 트레이트 솔버가 현재 어떻게 동작하는지 설명합니다. 하지만 저희는 새 트레이트 솔버를 설계하고 있습니다. 그것에 대해 읽고 싶으시다면 이 하위 장을 참고하십시오.

주요 개념

트레이트 해석은 트레이트에 대한 각 참조를 impl과 짝짓는 과정입니다. 예를 들어 다음과 같은 제네릭 함수가 있고:

fn clone_slice<T:Clone>(x: &[T]) -> Vec<T> { ... }

그 함수를 다음과 같이 호출한다면:

let v: Vec<isize> = clone_slice(&[1, 2, 3])

(이 경우) isize : Clone의 impl이 존재하는지 알아내는 것이 트레이트 해석이 하는 일입니다.

제네릭 함수와 같은 일부 경우에는 구체적인 impl을 찾지 못할 수도 있지만, 호출자가 impl을 제공해야 한다는 사실은 알아낼 수 있다는 점에 유의하십시오. 예를 들어 clone_slice의 본문을 살펴보십시오:

fn clone_slice<T:Clone>(x: &[T]) -> Vec<T> {
    let mut v = Vec::new();
    for e in &x {
        v.push((*e).clone()); // (*)
    }
}

(*)로 표시된 줄은 T(*e의 타입)가 Clone 트레이트를 구현하는 경우에만 유효합니다. 당연히 T가 무엇인지 모르므로 구체적인 impl을 찾을 수는 없습니다. 하지만 T:Clone 바운드에 근거하여 호출자가 제공해야 하는 impl이 존재한다고 말할 수 있습니다.

impl이 필요한 트레이트 참조를 가리켜 의무(obligation)라는 용어를 사용합니다. 트레이트 해석 시스템은 기본적으로 적절한 impl이 실제로 존재함을 증명하여 의무를 해석합니다.

타입 검사 중에는 트레이트 선택의 결과를 저장하지 않습니다. 단지 트레이트 선택이 성공하리라는 것만 확인하려는 것입니다. 그런 다음 나중에 코드 생성 시점에 모든 구체 타입을 사용할 수 있게 되면, 트레이트 선택을 다시 수행하여 실제 구현을 고를 수 있으며, 그 구현이 출력 바이너리에 생성됩니다.

개요

트레이트 해석은 세 가지 주요 부분으로 구성됩니다.

  • 선택(Selection): 특정 의무를 어떻게 해결할지 결정합니다. 예를 들어 선택 과정은 특정 의무를 Self 타입과 일치하는 impl을 사용하여 해결할 수 있다고 결정하거나, 매개변수 바운드(예: T: Trait)를 사용하여 해결할 수 있다고 결정할 수 있습니다. impl의 경우, impl 자체에 있는 where 절 때문에 하나의 의무를 선택하면 중첩된 의무가 생길 수 있습니다. 또한 모호성을 해소하기 위해 그 중첩된 의무들을 평가해야 할 수도 있습니다.

  • 이행(Fulfillment): 이행 코드는 의무가 완전히 이행되었는지를 추적하는 코드입니다. 기본적으로 이는 선택되어야 할 의무들의 작업 목록입니다. 선택이 성공하면 해당 의무는 작업 목록에서 제거되고 중첩된 의무들이 큐에 추가됩니다. 이행은 추론 변수를 제약합니다.

  • 평가(Evaluation): 어떤 추론 변수도 제약하지 않고 의무가 성립하는지 검사합니다. 선택 과정에서 사용됩니다.

선택

선택(selection)은 의무(obligation)를 해결할 수 있는지, 그리고 해결할 수 있다면 어떻게(impl, where 절 등을 통해) 해결할지를 결정하는 과정입니다. 주요 인터페이스는 select() 함수이며, 이 함수는 의무를 받아 SelectionResult를 반환합니다. 가능한 결과는 세 가지입니다.

  • Ok(Some(selection)) – 예, 의무를 해결할 수 있으며 selection이 그 방법을 나타냅니다. impl을 통해 해결된 경우, selection은 해당 impl이 요구하는 중첩된 의무도 나타낼 수 있습니다.

  • Ok(None) – 의무를 해결할 수 있는지 아직 확실하지 않습니다. 이는 의무에 바인딩되지 않은 타입 변수가 포함되어 있을 때 가장 흔히 발생합니다.

  • Err(err) – 타입 오류 때문이거나 적용될 수 있는 impl이 전혀 없기 때문에 의무를 확실히 해결할 수 없습니다.

선택의 기본 알고리즘은 후보 수집(candidate assembly)과 확정(confirmation)이라는 두 개의 큰 단계로 나뉩니다.

라이프타임 추론이 작동하는 방식 때문에, 라이프타임 사이의 단일화(unification)나 서브타입 관계가 성립하는지 여부를 즉시 피드백으로 돌려줄 수 없다는 점에 유의하십시오. 따라서 선택 과정에서는 라이프타임 매칭을 고려하지 않습니다. 이는 하위 영역(subregion) 할당이 실패하지 않는다는 사실에 반영되어 있습니다. 이로 인해 나중에 오류로 판명될 라이프타임 제약 조건이 생길 수 있습니다(반면, 라이프타임이 아닌 제약 조건은 선택 과정에서 이미 검사되었으므로 결코 오류를 일으킬 수 없습니다. 물론 이후 단계에서 다른 오류로 이어질 수는 있습니다).

후보 수집

TODO: 서로 다른 후보가 존재하는 이유와, 이것이 왜 프로브(probe) 안에서 일어나야 하는지 설명해야 합니다.

의무를 충족하는 데 사용될 수 있는 impl/where 절 등을 검색합니다. 이들 각각을 후보(candidate)라고 부릅니다. 모호성을 피하기 위해, 확실하게 적용 가능한 후보를 정확히 하나 찾고자 합니다. 경우에 따라 impl/where 절이 적용되는지 여부를 알 수 없을 때도 있습니다. 이는 의무에 바인딩되지 않은 추론 변수가 포함되어 있을 때 발생합니다.

특정 impl/where 절 등이 특정 의무에 적용되는지를 결정하는 서브루틴들을 통틀어 매칭 과정이라고 부릅니다. impl 후보의 경우, 이는 중첩된 의무를 무시하면서 impl 헤더(Self 타입과 트레이트 인자)를 단일화하는 것에 해당합니다. 매칭에 성공하면 이를 후보 집합에 추가합니다. Copy, Sized, CoerceUnsized와 같은 내장 트레이트에 대한 후보를 수집할 때는 다른 규칙이 적용됩니다.

이 첫 번째 단계가 끝나면 후보 집합을 검토할 수 있습니다. 집합의 원소가 하나뿐이라면 작업이 끝납니다. 이것이 스코프 내에서 적용될 수 있는 유일한 impl이기 때문입니다. 그렇지 않다면 where 절과 기타 조건을 사용하여 후보 집합을 선별할 수 있습니다. 선별 과정에서는 evaluate_candidate를 사용하여 중첩된 의무가 적용될 수 있는지 검사합니다. 그래도 후보가 2개 이상 남으면 fn candidate_should_be_dropped_in_favor_of를 사용하여 일부 후보를 다른 후보보다 우선합니다.

이렇게 줄어든 집합에서 모호하지 않은 단일 항목이 나오면 그대로 진행하면 되고, 그렇지 않으면 결과를 모호한 것으로 간주합니다.

선별: 모호성 해소

그런데 모든 타입이 단일화되는 impl이 여러 개 있다면 어떻게 됩니까? 다음 예제를 살펴보십시오.

trait Get {
    fn get(&self) -> Self;
}

impl<T: Copy> Get for T {
    fn get(&self) -> T {
        *self
    }
}

impl<T: Get> Get for Box<T> {
    fn get(&self) -> Box<T> {
        Box::new(<T>::get(self))
    }
}

예를 들어 get(&Box::new(1_u16))를 호출하면 어떻게 됩니까? 이 경우 Self 타입은 Box<u16>입니다. 첫 번째 impl은 모든 타입 T에 적용되고 두 번째 impl은 모든 Box<T>에 적용되므로, 이 타입은 두 impl 모두와 단일화됩니다. 이를 모호하지 않게 만들기 위해 컴파일러는 where 절을 고려하여 후보를 제거하려고 시도하는 선별(winnowing) 패스를 수행합니다. 이 경우 첫 번째 impl은 Box<u16> : Copy가 성립할 때만 적용되는데, 이는 성립하지 않습니다. 따라서 선별을 마치면 후보가 하나만 남으므로 계속 진행할 수 있습니다.

where 절

impl 외에 의무(obligation)를 해결하는 또 다른 주요 방법은 where 절을 이용하는 것입니다. 선택 과정에는 항상 where 절 목록을 담은 매개변수 환경이 주어지며, 이 where 절들은 기본적으로 충족 가능하다고 가정할 수 있는 의무입니다. 우리는 그 목록을 순회하면서 현재 의무를 그 목록에서 찾을 수 있는지 확인합니다. 찾을 수 있다면 그 의무는 충족된 것으로 간주합니다. 더 정확히 말하면, 같은 트레이트(또는 어떤 하위 트레이트)에 대한 where 절 의무 중 해당 의무와 매칭될 수 있는 것이 있는지 확인하려는 것입니다.

다음의 간단한 예제를 살펴보십시오.

trait A1 {
    fn do_a1(&self);
}
trait A2 : A1 { ... }

trait B {
    fn do_b(&self);
}

fn foo<X:A2+B>(x: X) {
    x.do_a1(); // (*)
    x.do_b();  // (#)
}

foo의 본문에서는 분명히 변수 x에 대해 A1, A2, B의 메서드를 사용할 수 있습니다. (*)로 표시된 줄은 X: A1 의무를 발생시키고, (#)로 표시된 줄은 X: B 의무를 발생시킵니다. 한편 매개변수 환경에는 X : A2와 X : B라는 두 개의 where 절이 담깁니다. 그러면 각 의무에 대해 이 where 절 목록을 검색합니다. X: B 의무는 where 절 X: B와 자명하게 매칭됩니다. X:A1 의무를 해결하려면 X:A2가 X:A1을 함의한다는 점에 주목하면 됩니다.

확인

확인(confirmation)은 트레이트의 출력 타입 매개변수를 의무에서 찾은 값과 단일화하며, 이 과정에서 타입 오류가 발생할 수 있습니다.

이전 절의 Convert 예제를 다음과 같이 변형했다고 가정해 봅시다.

trait Convert<Target> {
    fn convert(&self) -> Target;
}

impl Convert<usize> for isize { ... } // isize -> usize
impl Convert<isize> for usize { ... } // usize -> isize

let x: isize = ...;
let y: char = x.convert(); // NOTE: `y: char` now!

impl은 Target이 usize라고 지정했지만 의무는 char를 보고했으므로, 오류가 보고되는 곳은 바로 확인 단계입니다. 따라서 선택의 결과는 오류가 됩니다.

후보 impl은 Self 타입을 기준으로 선택되지만, 확인은 (이 경우) Target 타입 매개변수를 기준으로 수행된다는 점에 유의하십시오.

코드 생성 중의 선택

앞서 언급했듯이 타입 검사 중에는 트레이트 선택의 결과를 저장하지 않습니다. 코드 생성 시점에는 각 메서드 호출에 대해 특정 impl을 고르기 위해 트레이트 선택을 다시 수행합니다. 이는 fn codegen_select_candidate를 사용하여 수행됩니다. 각 해석이 특정 impl로 귀결된다는 것을 알고 있으므로, 이 두 번째 선택에서는 어떤 where 절도 스코프 안에 있는 것으로 간주하지 않습니다.

한 가지 흥미로운 점은 중첩된 의무(nested obligation)와 관련이 있습니다. 일반적으로 코드 생성에서는 어떤 후보가 적용되는지만 알아내면 되며, 중첩된 의무는 이미 참이라고 가정되므로 신경 쓰지 않습니다. 그럼에도 불구하고 현재는 이 의무들을 모두 실제로 이행합니다. 이렇게 하면 때때로 타입 추론 결과에 필요한 정보를 얻을 수 있기 때문입니다. 즉, impl의 타입 변수에 대한 완전한 치환을 알 수 없으므로, 모든 것을 알아내려면 트레이트 선택을 실행해야 합니다.