영역 추론(NLL)

MIR 기반 영역 검사 코드는 rustc_mir::borrow_check 모듈에 있습니다.

MIR 기반 영역 분석은 두 가지 주요 함수로 이루어져 있습니다:

• 먼저 호출되는 replace_regions_in_mir는 두 가지 일을 합니다:
  • 첫째, 함수 시그니처 안에 나타나는 영역의 집합을 찾습니다(예: fn foo<'a>(&'a u32) { ... }의 'a). 이러한 영역을 “보편(universal)” 영역 또는 “자유(free)” 영역이라고 부르며, 특히 이들은 함수 본문에서 자유롭게 나타나는 영역입니다.
  • 둘째, 함수 본문의 모든 영역을 새로운 추론 변수로 바꿉니다. 이는 (현재로서는) 그 영역들이 어휘적(lexical) 영역 추론의 결과이므로 별로 중요하지 않기 때문입니다. 궁극적으로는 어휘적 영역 추론을 전혀 수행하지 않을 것이므로, 이 영역들은 “지워진 영역(erased region)”(즉, 아무 정보도 없는 영역)이 되는 것이 목표입니다.
• 두 번째로 호출되는 compute_regions: 이 함수는 이동 분석(move analysis)의 결과를 인자로 받습니다. 이 함수는 replace_regions_in_mir가 도입한 모든 추론 변수의 값을 계산하는 일을 맡습니다.
  • 이를 위해 먼저 MIR 타입 검사기를 실행합니다. 이는 기본적으로 일반적인 타입 검사기이지만 MIR에 특화되어 있으며, 물론 MIR은 완전한 Rust보다 훨씬 단순합니다. 그러나 MIR 타입 검사기를 실행하면 영역 변수 사이에 다양한 제약 조건이 생성되며, 이 제약 조건은 영역 변수가 가질 수 있는 값과 서로 간의 관계를 나타냅니다.
  • 그다음 RegionInferenceContext를 생성하고 그 solve 메서드를 호출하여 제약 전파를 수행합니다.
  • NLL RFC에서도 이 내용을 꽤 철저하게 (그리고 바라건대 읽기 쉽게) 다룹니다.

보편 영역

UniversalRegions 타입은 어떤 MIR DefId에 대응하는 보편 영역의 모음을 나타냅니다. 이 타입은 모든 영역을 새로운 추론 변수로 바꿀 때 replace_regions_in_mir에서 생성됩니다. UniversalRegions는 주어진 MIR의 모든 자유 영역에 대한 인덱스와 함께, 그 영역들 사이에 성립한다고 알려진 관계(예: 암시적 바운드, where 절 등)를 담고 있습니다.

예를 들어, 다음 함수의 MIR이 주어졌다고 합시다:

#![allow(unused)]
fn main() {
fn foo<'a>(x: &'a u32) {
    // ...
}
}

이 경우 'a에 대한 보편 영역 하나와 'static에 대한 보편 영역 하나를 생성합니다. 클로저를 처리하는 데에는 몇 가지 복잡한 문제가 더 있을 수 있지만, 지금은 무시하겠습니다.

TODO: 이 영역들이 어떻게 계산되는지 작성하십시오.

영역 변수

영역의 값은 하나의 집합으로 생각할 수 있습니다. 이 집합에는 해당 영역이 유효한 MIR의 모든 지점과 함께, 이 영역이 더 오래 사는(outlive) 모든 영역이 들어 있습니다(예: 'a: 'b이면 end('b)는 'a의 집합에 속합니다). 이 집합의 정의역을 RegionElement라고 부릅니다. 코드에서 모든 영역의 값은 rustc_borrowck::region_infer 모듈에서 관리합니다. 각 영역마다 그 값에 어떤 원소가 들어 있는지 저장하는 집합을 관리합니다(이를 효율적으로 하기 위해 원소의 종류마다 인덱스인 RegionElementIndex를 부여하고 희소 비트셋을 사용합니다).

영역 원소의 종류는 다음과 같습니다:

• MIR 제어 흐름 그래프의 각 location: location은 단순히 기본 블록과 인덱스의 쌍입니다. 이는 해당 인덱스의 문장(인덱스가 statements.len()과 같다면 종결자)에 진입하는 지점을 나타냅니다.
• 각 보편 영역 'a마다 end('a) 요소가 있으며, 이는 호출자(또는 호출자의 호출자 등)의 제어 흐름 그래프 중 일부에 해당합니다.
• 마찬가지로, 이 함수가 반환된 이후의 나머지 프로그램 실행에 해당하는, end('static)으로 표기되는 요소가 있습니다.
• 각 플레이스홀더 영역 !1마다 !1 요소가 있습니다. 이는 (직관적으로) 알 수 없는 다른 요소들의 집합에 해당합니다. 플레이스홀더에 대한 자세한 내용은 플레이스홀더와 유니버스 절을 참조하십시오.

제약

영역의 값을 추론하려면 먼저 영역에 대한 제약 조건을 수집해야 합니다. 제약의 전체 집합은 제약 전파에 관한 절에서 설명하지만, 가장 흔한 두 가지 종류의 제약은 다음과 같습니다.

1. outlives 제약 조건. 이는 한 영역이 다른 영역보다 오래 산다는 제약 조건입니다(예: 'a: 'b). outlives 제약 조건은 MIR 타입 검사기가 생성합니다.
2. 활성 제약. 각 영역은 사용될 수 있는 지점에서 활성 상태여야 합니다.

추론 개요

그렇다면 영역의 내용은 어떻게 계산합니까? 이 과정을 영역 추론이라고 합니다. 개략적인 아이디어는 꽤 단순하지만, 신경 써야 할 세부 사항이 몇 가지 있습니다.

개략적인 아이디어는 다음과 같습니다. 먼저 각 영역을, 활성 제약 조건에 따라 반드시 그 영역에 포함되어야 한다고 알고 있는 MIR 위치들로 초기화합니다. 거기서부터 타입 검사기가 계산한 모든 outlives 제약 조건을 사용하여 제약 조건을 전파합니다. 즉, 각 영역 'a에 대해 'a: 'b이면 end('b)를 포함한 'b의 모든 요소를 'a에 추가합니다. 이 모든 작업은 propagate_constraints에서 이루어집니다.

그런 다음 오류를 검사합니다. 먼저 check_type_tests를 호출하여 타입 테스트가 충족되는지 검사합니다. 이는 T: 'a와 같은 제약 조건을 검사합니다. 둘째로, 보편 영역이 “너무 크지” 않은지 검사합니다. 이는 check_universal_regions를 호출하여 수행합니다. 이는 각 영역 'a에 대해, 'a가 end('b) 요소를 포함한다면 'a: 'b가 성립한다는 것을 (예: where 절로부터) 이미 알고 있어야 한다는 점을 검사합니다. 이를 이미 알고 있지 않다면 오류입니다… 음, 거의 그렇습니다. 클로저에는 나중에 논의할 특별한 처리가 몇 가지 있습니다.

예시

다음 예제를 살펴보십시오.

fn foo<'a, 'b>(x: &'a usize) -> &'b usize {
    x
}

'a가 'b보다 오래 사는지 알 수 없으므로 이 코드는 당연히 컴파일되어서는 안 됩니다(오래 살지 않는다면 반환 값이 댕글링 참조가 될 수 있습니다).

잠시 한 걸음 물러서 봅시다. (replace_regions_in_mir에서 하는 것처럼) 몇 가지 자유 추론 변수를 도입해야 합니다. 이 예제는 실제로 생성되는 영역을 그대로 사용하지는 않지만, 개념을 전달하기에는 (바라건대) 충분합니다.

fn foo<'a, 'b>(x: &'a /* '#1 */ usize) -> &'b /* '#3 */ usize {
    x // '#2, location L1
}

표기법: '#1, '#3, '#2는 각각 인자, 반환값, 표현식 x에 대한 보편 영역을 나타냅니다. 또한 표현식 x의 위치를 L1이라고 부르겠습니다.

이제 활성 제약 조건을 사용하여 다음과 같은 시작점을 얻을 수 있습니다.

이제 outlives 제약 조건을 사용하여 각 영역을 확장합니다. 구체적으로, '#2: '#3임을 알고 있으므로 …

… 또한 '#1: '#2이므로 …

이제 너무 큰 영역이 없는지 확인해야 합니다(이 경우에는 확인할 타입 테스트가 없습니다). 이제 '#1에 end('#3)가 포함되어 있지만, 'a: 'b임을 나타내는 where 절이나 암시적 바운드가 없다는 점에 주목하십시오. 이것은 오류입니다!

세부 사항

RegionInferenceContext 타입에는 replace_regions_in_mir에서 얻은 보편 영역과 각 영역에 대해 계산된 제약 조건을 포함하여 추론에 필요한 모든 정보가 들어 있습니다. 이는 활성 제약을 계산한 직후에 생성됩니다.

다음은 이 구조체의 필드 중 일부입니다.

• constraints: 모든 outlives 제약 조건을 담고 있습니다.
• liveness_constraints: 모든 활성 제약을 담고 있습니다.
• universal_regions: replace_regions_in_mir가 반환한 UniversalRegions를 담고 있습니다.
• universal_region_relations: 보편 영역에 대해 참으로 알려진 관계를 담고 있습니다. 예를 들어 'a: 'b라는 where 절이 있다면, 구현을 빌림 검사하는 동안 그 관계는 참으로 가정되므로(이는 호출자 쪽에서 검사됩니다) universal_region_relations에는 'a: 'b가 포함됩니다.
• type_tests: 추론 후에 반드시 확인해야 하는 타입에 대한 몇 가지 제약 조건(예: T: 'a)을 담고 있습니다.
• closure_bounds_mapping: 클로저의 영역 제약 조건을 클로저를 생성한 쪽으로 다시 전파하는 데 사용됩니다.

TODO: 다른 필드도 논의해야 합니까? SCC는 어떻습니까?

자, 이제 RegionInferenceContext를 생성했으므로 추론을 수행할 수 있습니다. 추론은 컨텍스트의 solve 메서드를 호출하여 수행합니다. 앞에서 설명한 것처럼, 이 메서드에서 propagate_constraints를 호출한 다음 그 결과로 나온 타입 테스트와 보편 영역을 확인합니다.