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

표준화

NOTE: FIXME: 이 장의 내용은 차세대 트레이트 해결 표준화 장과 일부 겹칩니다. 향후 이 내용을 재구성할 것을 권장합니다.

표준화는 추론 값을 그 컨텍스트로부터 격리하는 과정입니다. 이는 정준 쿼리를 구현하는 데 핵심적인 부분이며, 더 많은 맥락을 얻으려면 상위 장을 읽어 보셔도 좋습니다.

표준화는 사실 매우 단순한 개념에 기반합니다. 모든 추론 변수는 항상 두 상태 중 하나에 있습니다. 바인딩되지 않은 상태로서 아직 어떤 타입인지 알지 못하는 경우이거나, 바인딩된 상태로서 어떤 타입인지 아는 경우입니다. 따라서 타입/리전을 포함하는 어떤 데이터 구조 T를 그 환경으로부터 격리하려면, T를 따라 내려가며 T에 나타나는 바인딩되지 않은 변수들을 찾기만 하면 됩니다. 그 변수들은 “정준 변수“로 대체되며, 0부터 시작하여 고정된 순서로 번호가 매겨집니다(대체로 왼쪽에서 오른쪽 순서이지만, 일관되기만 하면 실제로는 순서가 중요하지 않습니다).

예를 들어 X = (?T, ?U)라는 타입이 있고 ?T와 ?U가 서로 다른, 바인딩되지 않은 추론 변수라면, X의 정준 형태는 (?0, ?1)이 되며, 여기서 ?0과 ?1은 이러한 정준 자리 표시자를 나타냅니다. Y = (?U, ?T) 타입 역시 (?0, ?1)로 정준화된다는 점에 유의하십시오. 그러나 Z = (?T, ?T) 타입은 (?0, ?0)으로 정준화됩니다((?U, ?U)도 마찬가지입니다). 다시 말해, 추론 변수가 정확히 무엇인지는 중요하지 않습니다. 단, 반복되는 경우는 예외입니다.

우리는 이를 사용하여 캐싱을 개선할 뿐만 아니라 트레이트 해석 중에 순환 및 기타 사항을 감지합니다. 대략적으로 말하면, 두 트레이트 쿼리의 정준 형태가 같다면 같은 답을 얻게 된다는 것이 핵심 아이디어입니다. 그 답은 정준 변수(?0, ?1)로 표현되며, 이를 다시 원래 변수(?T, ?U)로 대응시킬 수 있습니다.

쿼리 정준화하기

작동 방식을 이해하기 위해, 다음 트레이트 쿼리의 해결을 요청한다고 가정해 봅시다. 쿼리는 ?A: Foo<'static, ?B>이며, 여기서 ?A와 ?B는 바인딩되지 않은 상태입니다. 이 쿼리는 바인딩되지 않은 변수 두 개를 포함하지만, 라이프타임 'static도 포함합니다. 트레이트 시스템은 일반적으로 모든 라이프타임을 무시하고 동일하게 취급하므로, 정준화할 때 모든 자유 라이프타임도 정준 변수로 대체합니다(여기서 'static은 실제로 자유 라이프타임 변수라는 점에 유의하십시오. 우리는 이를 전체 프로그램의 타이핑 컨텍스트에서 고려하는 것이 아니라 이 트레이트 참조의 컨텍스트에서만 고려합니다. 수학적으로 말하면, 프로그램 전체에 대해 한정하는 것이 아니라 이 의무에 대해서만 한정합니다). 따라서 다음과 같은 결과를 얻습니다:

?0: Foo<'?1, ?2>

때로는 이를 다음과 같이 다르게 표기하기도 합니다:

for<T,L,T> { ?0: Foo<'?1, ?2> }

이 for<>는 그 안에 있는 각 정준 변수에 대한 정보를 제공합니다. 이 경우 각 T는 타입 변수를 나타내므로 ?0과 ?2는 타입이고, L은 라이프타임 변수를 나타내므로 ?1은 라이프타임입니다. canonicalize 메서드는 정준화된 각 변수의 “원래 값“을 담은 CanonicalVarValues 배열 OV도 돌려줍니다:

[?A, 'static, ?B]

이 벡터 OV는 나중에 쿼리 응답을 처리할 때 필요합니다.

쿼리 실행하기

정준 쿼리를 구성하고 나면 이를 해결하려고 시도할 수 있습니다. 이를 위해 우리는 결국 새로운 추론 컨텍스트를 생성하고 그 컨텍스트에서 정준 쿼리를 인스턴스화하게 됩니다. 핵심 아이디어는 각 정준 변수마다 (적절한 종류의) 새로운 추론 변수를 담은 치환 S를 정준 형태로부터 만드는 것입니다. 따라서 앞의 예제 쿼리가 다음과 같다면:

for<T,L,T> { ?0: Foo<'?1, ?2> }

치환 S는 다음과 같을 수 있습니다:

S = [?A, '?B, ?C]

그런 다음 바운드 정준 변수(?0 등)를 이 추론 변수들로 치환하여 다음과 같이 완전히 인스턴스화된 쿼리를 얻을 수 있습니다.

?A: Foo<'?B, ?C>

하지만 그 치환 S를 꼭 기억해 두십시오! 나중에 필요하게 될 것입니다.

이제 새로운 추론 컨텍스트와 인스턴스화된 쿼리가 준비되었으므로, 이를 풀어 볼 수 있습니다. 트레이트 솔버 자체는 다른 절에서 더 자세히 설명하지만, 여기서는 트레이트 솔버가 확실성 값(Proven 또는 Ambiguous)을 계산하고 우리가 생성한 추론 변수에 부수 효과를 일으킨다는 정도만 말해 두면 충분합니다. 예를 들어, 다음과 같이 Foo의 impl이 하나뿐이라면:

impl<'a, X> Foo<'a, X> for Vec<X>
where X: 'a
{ ... }

확실성 값으로 Proven을 얻게 될 수 있으며, 동시에 (impl의 매개변수를 나타내기 위해) 새로운 추론 변수 '?D와 ?E를 생성하고 다음과 같이 단일화하게 됩니다.

  • '?B = '?D
  • ?A = Vec<?E>
  • ?C = ?E

where 절로 인해 영역 제약 ?E: '?D도 누적하게 됩니다.

최종 쿼리 결과를 만들려면, 이 값들을 쿼리의 추론 컨텍스트에서 “끌어올려” 원래의 추론 컨텍스트에 다시 적용할 수 있는 형태로 바꾸어야 합니다. 우리는 표준화를 다시 적용하여 이를 수행하지만, 이번에는 쿼리 결과에 적용합니다.

쿼리 결과 정규화하기

상위 절에서 논의한 바와 같이, 대부분의 트레이트 쿼리는 결국 “확실성 값” certainty, 결과 치환 var_values, 그리고 몇몇 영역 제약을 한데 묶은 결과를 내게 됩니다. 이를 만들기 위해, 처음 쿼리를 인스턴스화할 때 생성한 치환 S를 재사용하게 됩니다. 기억(메모리)을 되살려 보자면, 우리에게는 다음과 같은 쿼리가 있었습니다

for<T,L,T> { ?0: Foo<'?1, ?2> }

이에 대해 다음과 같은 치환 S를 만들었습니다.

S = [?A, '?B, ?C]

그런 다음 그 변수들 중 일부를 다른 것들과 단일화하는 작업을 수행했습니다. 최신 결과로 S를 “갱신“하면 다음을 얻습니다.

S = [Vec<?E>, '?D, ?E]

이것들은 정확히 원래 쿼리의 세 입력 변수에 대한 새로운 값입니다. 하지만 여기에는 (?E와 같은) 새로운 변수가 일부 포함되어 있다는 점에 유의하십시오. 다시 정규화하면 이것들을 없앨 수 있습니다! 다만 S만 정규화하는 것이 아니라, 쿼리 응답 QR 전체를 정규화합니다.

QR = {
    certainty: Proven,             // or whatever
    var_values: [Vec<?E>, '?D, ?E] // this is S
    region_constraints: [?E: '?D], // from the impl
    value: (),                     // for our purposes, just (), but
                                   // in some cases this might have
                                   // a type or other info
}

결과는 다음과 같습니다.

Canonical(QR) = for<T, L> {
    certainty: Proven,
    var_values: [Vec<?0>, '?1, ?0]
    region_constraints: [?0: '?1],
    value: (),
}

(한 가지 미묘한 점이 있습니다. 쿼리 결과를 정규화할 때는 자유 라이프타임을 특별히 취급하지 않습니다. 예를 들어, '?D에 대한 두 참조가 모두 같은 정준 변수(?1)로 변환되었다는 점에 유의하십시오. 이는 모든 자유 라이프타임을 새로운 정준 변수로 표준화했던 원래 쿼리와 대조됩니다.)

이제 이 결과를 필요한 각 컨텍스트에 다시 적용해야 합니다.

정규화된 쿼리 결과 처리하기

이전 절에서 우리는 정준 쿼리 결과를 만들었습니다. 이제 그 결과를 원래의 컨텍스트에 적용해야 합니다. 기억하시겠지만, 맨 처음에 우리는 다음 쿼리를 증명하려 하고 있었습니다:

?A: Foo<'static, ?B>

우리는 이것을 다음과 같이 정규화했습니다:

for<T,L,T> { ?0: Foo<'?1, ?2> }

그리고 이제 다음과 같은 정규 응답을 돌려받았습니다:

for<T, L> {
    certainty: Proven,
    var_values: [Vec<?0>, '?1, ?0]
    region_constraints: [?0: '?1],
    value: (),
}

이제 그 응답을 우리의 컨텍스트에 적용하려 합니다. 개념적으로 이를 수행하는 방법은 (a) 결과에 있는 각 정준 변수를 새로운 추론 변수로 인스턴스화하고, (b) 결과의 값들을 원래 값들과 단일화한 다음, (c) 나중을 위해 영역 제약을 기록하는 것입니다. (a) 단계를 수행하면 다음과 같은 결과가 나옵니다

{
      certainty: Proven,
      var_values: [Vec<?C>, '?D, ?C]
                       ^^   ^^^ fresh inference variables
      region_constraints: [?C: '?D],
      value: (),
}

그다음 (b) 단계에서는 다음을 단일화합니다:

?A with Vec<?C>
'static with '?D
?B with ?C

그리고 마지막으로 ?C: 'static이라는 영역 제약 조건이 나중에 검증할 수 있도록 기록됩니다.

(우리가 실제로 수행하는 것은 이를 약간 최적화한 변형입니다. 결과에 있는 모든 정준 값을 변수로 미리 인스턴스화하는 대신, 값의 벡터를 순회하면서 값이 단지 정준 변수에 불과한 경우를 찾습니다. 우리 예제에서 values[2]는 ?C이므로, ?C := ?B이고 '?D := 'static이라고 추론할 수 있습니다. 이를 통해 값들 중 일부를 얻습니다. 값을 찾지 못한 것에 대해서는 추론 변수를 생성합니다.)