고차 트레이트 바운드

트레이트 해석에서 비교적 미묘한 개념 중 하나는 고차 트레이트 바운드입니다. 이러한 바운드의 예로는 for<'a> MyTrait<&'a isize>가 있습니다. 고차 트레이트 참조에 대한 선택이 어떻게 동작하는지 차례로 살펴봅시다.

기본 매칭과 플레이스홀더 누출

트레이트 Foo가 있다고 가정합시다:

#![allow(unused)]
fn main() {
trait Foo<X> {
    fn foo(&self, x: X) { }
}
}

임의의 'a에 대해 Foo<&'a isize>를 구현하는 타입을 요구하는 함수 want_hrtb가 있다고 합시다:

fn want_hrtb<T>() where T : for<'a> Foo<&'a isize> { ... }

이제 임의의 'a에 대해 Foo<&'a isize>를 구현하는 구조체 AnyInt가 있습니다:

struct AnyInt;
impl<'a> Foo<&'a isize> for AnyInt { }

그렇다면 질문은 AnyInt : for<'a> Foo<&'a isize>가 성립하는가 하는 것입니다. 우리는 답이 ’예’이기를 원합니다. 이를 알아내는 알고리즘은 고차 타입에 대한 서브타이핑과 밀접하게 관련되어 있습니다(이는 여기와 SPJ의 논문에도 설명되어 있습니다. 고차 서브타이핑을 이해하고 싶다면 그 논문을 읽어 보기를 권장합니다). 알고리즘은 몇 가지 단계로 이루어집니다:

의무에 있는 바운드 영역을 플레이스홀더로 대체합니다.
impl을 플레이스홀더 의무와 매칭합니다.
플레이스홀더 누출을 검사합니다.

그러면 예제를 차근차근 살펴봅시다.

가장 먼저 할 일은 의무에 있는 바운드 영역을 플레이스홀더로 대체하여 AnyInt : Foo<&'0 isize>를 얻는 것입니다(여기서 '0은 플레이스홀더 영역 #0을 나타냅니다). 이제 한정자가 더 이상 없다는 점에 유의하십시오. 컴파일러 타입의 관점에서 보면, 이는 ty::PolyTraitRef에서 TraitRef로 바뀌는 것입니다. 그다음 impl로부터 TraitRef를 생성하는데, 이때 그 바운드 영역에는 새로운 변수를 사용합니다(그 결과 Foo<&'$a isize>를 얻으며, 여기서 '$a는 'a에 대한 추론 변수입니다).
다음으로 두 트레이트 참조를 서로 관계 짓고, 그 결과 '0 == '$a라는 제약 조건을 가진 그래프를 얻습니다.
마지막으로 플레이스홀더 “누출“을 검사합니다 – 누출이란 기본적으로 플레이스홀더 영역을 다른 플레이스홀더 영역이나 impl 매칭 이전부터 존재하던 임의의 영역과 관계 지으려는 모든 시도를 말합니다. 누출 검사는 플레이스홀더 영역에서부터 탐색하여 그 영역과 어떤 식으로든 관련된 영역들의 집합을 찾는 방식으로 수행됩니다. 이를 “오염(taint)” 집합이라고 합니다. 검사를 통과하려면 그 집합은 오직 자기 자신과 impl에서 나온 영역 변수들로만 구성되어야 합니다. 오염 집합에 그 밖의 다른 영역이 포함되어 있으면 매칭은 실패합니다. 이 경우 '0의 오염 집합은 {'0, '$a}이므로 검사는 성공합니다.

실패하는 경우를 살펴봅시다. 다음과 같은 구조체도 있다고 가정해 봅시다

struct StaticInt;
impl Foo<&'static isize> for StaticInt;

StaticInt : for<'a> Foo<&'a isize> 의무는 충족되지 않은 것으로 간주되어야 합니다. 검사는 앞에서와 똑같이 시작됩니다. 'a는 플레이스홀더 '0으로 대체되고, impl 트레이트 참조는 Foo<&'static isize>로 인스턴스화됩니다. 이 둘을 관계 지으면 'static == '0과 같은 제약 조건을 얻습니다. 이는 '0의 오염 집합(taint set)이 {'0, 'static}이라는 뜻이며, 따라서 누출 검사(leak check)에 실패합니다.

TODO: 이는 'static이 영역 변수가 아닌데도 오염 집합에 포함되어 있기 때문이 맞습니까?

고차 트레이트 의무

기본적인 매칭이 끝나면 또 다른 흥미로운 주제로 넘어갑니다. 바로 impl 의무를 어떻게 처리하느냐는 것입니다. 여기서는 간단한 예제를 하나 살펴보겠습니다. 트레이트 Foo와 Bar, 그리고 이와 연관된 impl이 있다고 가정해 보십시오:

#![allow(unused)]
fn main() {
trait Foo<X> {
    fn foo(&self, x: X) { }
}

trait Bar<X> {
    fn bar(&self, x: X) { }
}

impl<X,F> Foo<X> for F
    where F : Bar<X>
{
}
}

이제 Baz: for<'a> Foo<&'a isize>라는 의무가 있고 이 impl을 매칭한다고 합시다. 그 결과로 어떤 의무가 생성됩니까? 우리는 Baz: for<'a> Bar<&'a isize>를 얻고자 하는데, 이는 어떻게 이루어집니까?

매칭이 끝나면 X => &'0 isize와 같은 플레이스홀더 치환을 갖게 됩니다. 이 치환을 impl 의무에 적용하면 F : Bar<&'0 isize>를 얻습니다. 플레이스홀더 영역 '0은 계산 밖으로 누출될 수 없으므로, 이를 그대로 사용할 수 없다는 것은 분명합니다.

우리가 하는 일은 '0의 오염 집합에서 '0이 유래한 원래의 바운드 영역(여기서는 'a)으로 되돌아가는 역매핑을 만드는 것입니다. (이 작업은 higher_ranked::plug_leaks에서 수행됩니다.) 누출 검사를 통과했다는 것을 알고 있으므로, 이 오염 집합은 플레이스홀더 영역 자체와 여러 중간 영역 변수만으로 구성됩니다. 그런 다음 트레이트 참조를 순회하면서 그 오염 집합에 속한 모든 영역을 다시 후기 바운드 영역으로 변환하므로, 이 경우 최종적으로 Baz: for<'a> Bar<&'a isize>를 얻게 됩니다.

Keyboard shortcuts

Rust 컴파일러 개발 가이드

고차 트레이트 바운드

기본 매칭과 플레이스홀더 누출

고차 트레이트 의무