제약 전파

영역 추론의 주요 작업은 제약 전파이며, 이는 propagate_constraints 함수에서 수행됩니다. NLL에서 사용되는 제약에는 세 가지 종류가 있으며, 이 종류의 제약을 한 번에 하나씩 “겹쳐 쌓는” 방식으로 propagate_constraints가 어떻게 동작하는지 설명하겠습니다(각 종류는 다른 종류와 상당히 독립적입니다).

• 활성(liveness)에서 발생하는 활성 제약(R live at E)
• 서브타이핑에서 발생하는 outlives 제약(R1: R2)
• impl 트레이트(impl Trait)에서 발생하는 멤버 제약 조건(member R_m of [R_c...])입니다.

이 장에서는 활성 제약과 outlives 제약을 모두 다루면서 제약 전파의 “핵심“을 설명하겠습니다.

표기법과 고수준 개념

개념적으로 영역 추론은 “고정점(fixed-point)” 계산입니다. 영역 추론은 제약 집합 {C}를 입력으로 받아, 각 영역 R을 원소 집합 {E}에 대응시키는 값 집합 Values: R -> {E}를 계산합니다(영역 원소에 대한 자세한 내용은 여기를 참고하십시오).

• 처음에는 각 영역이 빈 집합에 대응되므로, 모든 영역 R에 대해 Values(R) = {}입니다.
• 다음으로, 고정점에 도달할 때까지 제약을 반복적으로 처리합니다.
  • 각 제약 C에 대해:
    • 제약을 만족시키는 데 필요한 만큼 Values를 갱신합니다

간단한 예로, 활성 제약 R live at E가 있다면 Values(R) = Values(R) union {E}를 적용하여 제약이 만족되도록 할 수 있습니다. 마찬가지로, outlives 제약 R1: R2가 있다면 Values(R1) = Values(R1) union Values(R2)를 적용할 수 있습니다. (멤버 제약은 더 복잡하며 이 절에서 다룹니다.)

그러나 실제로는 조금 더 영리한 방법을 사용합니다. 제약을 루프에서 반복 적용하는 대신, 제약을 분석하여 올바른 적용 순서를 알아낼 수 있습니다. 이렇게 하면 최종 결과를 구하기 위해 각 제약을 한 번만 적용하면 됩니다.

마찬가지로, 구현에서 Values 집합은 scc_values 필드에 저장되지만, 영역이 아니라 강한 연결 요소(SCC)를 기준으로 인덱싱됩니다. SCC는 많은 중복 저장과 계산을 피하기 위한 최적화입니다. 이에 대해서는 outlives 제약에 관한 절에서 설명합니다.

활성 제약

활성 제약은 타입에 영역 R을 포함하는 어떤 변수가 어떤 지점 P에서 활성 상태일 때 발생합니다. 이는 단순히 R의 값이 지점 P를 포함해야 한다는 의미입니다. 활성 제약은 MIR 타입 검사기가 계산합니다.

활성 제약 R live at E는 E가 Values(R)의 원소일 때 만족됩니다. 따라서 이러한 제약을 Values에 “적용“하려면 Values(R) = Values(R) union {E}를 계산하기만 하면 됩니다.

활성 값은 타입 검사 과정에서 계산되어, 영역 추론이 생성될 때 liveness_constraints 인자로 전달됩니다. 다만 이 값들은 R live at E와 같은 개별 제약으로 표현되지 않습니다. 대신 영역 변수마다 (LivenessValues 타입의) (희소) 비트셋을 저장합니다. 이렇게 하면 활성 제약 하나당 비트 하나만 있으면 됩니다.

한 가지 언급할 만한 점이 있습니다. 모든 라이프타임 매개변수는 항상 함수 본문 전체에 걸쳐 활성 상태인 것으로 간주됩니다. 이는 라이프타임 매개변수가 호출자의 실행 중 일부에 해당하고, 호출자가 이 함수의 반환을 기다리고 있으므로 그 실행에는 이 함수에서 소요되는 시간이 분명히 포함되기 때문입니다.

Outlives 제약 조건

outlives 제약 조건 'a: 'b는 'a의 값이 'b 값의 상위 집합이어야 함을 나타냅니다. 즉, outlives 제약 조건 R1: R2는 Values(R1)이 Values(R2)의 상위 집합일 때 충족됩니다. 따라서 이러한 제약 조건을 Values에 “적용“하려면 Values(R1) = Values(R1) union Values(R2)를 계산하기만 하면 됩니다.

이로부터 알 수 있는 한 가지 사실은 R1: R2와 R2: R1이 모두 있으면 R1 = R2가 반드시 참이라는 것입니다. 마찬가지로, 다음과 같은 제약 조건이 있다면:

R1: R2
R2: R3
R3: R4
R4: R1

R1 = R2 = R3 = R4가 성립합니다. 곧 설명하겠지만, 이 성질을 활용하면 작업을 훨씬 빠르게 처리할 수 있습니다.

코드에서 outlives 제약 조건의 집합은 영역 추론 컨텍스트를 생성할 때 OutlivesConstraintSet 타입의 매개변수로 전달됩니다. 이 제약 조건 집합은 기본적으로 'a: 'b 제약 조건의 목록일 뿐입니다.

outlives 제약 조건 그래프와 SCC

outlives 제약 조건을 더 효율적으로 다루기 위해 이 제약 조건들은 그래프 형태로 변환되며, 이 그래프의 노드는 영역 변수('a, 'b)이고 각 제약 조건 'a: 'b는 간선 'a -> 'b를 만듭니다. 이 변환은 추론 컨텍스트를 생성하는 RegionInferenceContext::new 함수에서 이루어집니다.

그래프 표현을 사용하면 순환을 찾아 반드시 같아야 하는 영역을 탐지할 수 있습니다. 즉, 다음과 같은 제약 조건이 있다면

'a: 'b
'b: 'c
'c: 'd
'd: 'a

이는 그래프에서 'a...'d 요소를 포함하는 순환에 해당합니다.

따라서 영역 값을 전파할 때 가장 먼저 하는 일 중 하나는 제약 조건 그래프에서 강한 연결 요소(SCC)를 계산하는 것입니다. 그 결과는 constraint_sccs 필드에 저장됩니다. 그러면 constraint_sccs.scc(r)를 호출하여 영역 r이 속한 SCC를 쉽게 찾을 수 있습니다.

SCC 단위로 작업하면 더 효율적입니다. 하나의 SCC에 속하는 영역 집합 'a...'d가 있다면 각 영역의 값을 따로 계산하거나 저장할 필요가 없습니다. 이 영역들은 모두 같아야 하므로 SCC에 대해 값 하나만 저장하면 됩니다.

영역 추론 코드를 살펴보면 여러 필드가 SCC 단위로 정의되어 있음을 알 수 있습니다. 예를 들어 scc_values 필드는 각 SCC의 값을 저장합니다. 따라서 특정 영역 'a의 값을 얻으려면 먼저 그 영역이 속한 SCC를 알아낸 다음 해당 SCC의 값을 찾습니다.

SCC를 계산할 때는 각 SCC에 어떤 영역이 속하는지뿐만 아니라 SCC 사이의 간선도 알아냅니다. 예를 들어 다음과 같은 outlives 제약 조건 집합을 생각해 봅시다.

'a: 'b
'b: 'a

'a: 'c

'c: 'd
'd: 'c

여기에는 SCC가 두 개 있습니다. S0은 'a와 'b를 포함하고, S1은 'c와 'd를 포함합니다. 그러나 이 SCC들은 서로 독립적이지 않습니다. 'a: 'c이므로 S0: S1도 성립합니다. 즉, S0의 값은 S1 값의 상위 집합이어야 합니다. 한 가지 중요한 점은 이 SCC 그래프가 항상 DAG라는 것, 즉 순환이 전혀 없다는 것입니다. 이는 SCC 자체를 형성하는 과정에서 모든 순환이 제거되었기 때문입니다.

SCC에 활성 제약 적용하기

타입 검사기에서 들어오는 활성 제약은 영역 관점에서 표현됩니다. 즉, Liveness: R -> {E}와 같은 맵을 갖게 됩니다. 그러나 최종 결과는 SCC를 기준으로 표현되어야 합니다. 이러한 활성 제약 조건은 합집합을 취하는 것만으로 매우 쉽게 통합할 수 있습니다.

for each region R:
  let S be the SCC that contains R
  Values(S) = Values(S) union Liveness(R)

영역 추론기에서 이 단계는 RegionInferenceContext::new에서 수행됩니다.

outlives 제약 조건 적용

SCC의 DAG를 계산하고 나면, 이를 사용하여 전체 계산을 구조화합니다. 두 SCC 사이에 S1 -> S2 간선이 있다면, 이는 Values(S1) >= Values(S2)가 성립해야 함을 의미합니다. 따라서 S1의 값을 계산하려면 먼저 각 후속 SCC S2의 값을 계산합니다. 그런 다음 그 값들을 모두 합집합으로 합치기만 하면 됩니다. 반복자와 유사한 표기법으로 나타내면 다음과 같습니다.

Values(S1) =
  s1.successors()
    .map(|s2| Values(s2))
    .union()

코드에서 이 작업은 모든 SCC를 순회하는 propagate_constraints 함수에서 시작됩니다. 각 SCC S1에 대해, 먼저 후속 SCC들의 값을 계산한 다음 이를 바탕으로 S1의 값을 계산합니다. SCC는 DAG를 이루므로 순환은 걱정할 필요가 없지만, 특정 SCC를 이미 처리했는지 여부를 추적하기 위한 집합은 유지해야 합니다. 각 후속 SCC S2에 대해, S2의 값을 계산하고 나면 그 원소들을 S1의 값에 합집합으로 합칠 수 있습니다. (다만 이 과정에서 고차 플레이스홀더를 올바르게 처리하도록 주의해야 합니다. S1의 값에는 이미 활성 제약 조건이 포함되어 있다는 점에 유의하십시오. 이 제약 조건은 RegionInferenceContext::new에서 추가되었기 때문입니다.

이 과정이 끝나면, 모든 활성 제약 조건과 outlives 제약 조건을 고려한 S1의 “최소값“을 얻게 됩니다. 그러나 이 과정을 완료하려면 이후 절에서 설명하는 멤버 제약 조건도 고려해야 합니다.