관계 - Polonius - RosettaLens 번역

입력 관계

Polonius는 "입력 팩트"로부터 분석을 시작합니다. 이는 러스트 코드(대부분: 하나의 함수)에 대한 작은 정보 데이터베이스로 볼 수 있습니다.

이 비유에서 데이터베이스는 테이블(혹은 관계) 형태로 모든 데이터를 담고 있는 AllFacts 구조체이며, 여기서는 몇 개의 행을 담은 Vec들로 표현됩니다. 테이블의 행이 바로 이 "팩트"입니다. 이 용어는 Polonius가 계산에 사용하는 Datalog에서 유래했으며(그리고 rustc 플래그가 이 데이터를 출력할 때 -Znll-facts로 불리는 이유와, 파일 자체가 *.facts인 이유이기도 합니다),

여러 환경에서 사용될 수 있도록(주로: rustc에서 메모리 상으로, 그리고 Polonius 저장소의 디스크 상 테스트 파일로부터) 이 구조체는 팩트의 타입에 대해 제네릭하며, 단지 그것들이 Atom임만을 요구합니다. 목표는 Polonius 계산에서 숫자로 표현된 interning된 값을 사용하는 것입니다.

이러한 제네릭한 팩트 타입은 Polonius가 조작하는 개념들입니다: CFG의 특정 points에서 loans를 담는 추상적 origins(활성 분석과 이동/덮어쓰기 분석에서는 variables와 paths도 있습니다)이며, 관계는 그들의 의미(서로 다른 팩트들 간의 구체적 관계 포함)입니다. 이러한 atom들에 대한 자세한 내용은 전용 장에서 확인할 수 있습니다.

가장 단순한 관계부터 시작해 봅시다: cfg_edge 관계로 표현되는 제어 흐름 그래프(Control Flow Graph).

1. `cfg_edge`

cfg_edge(point1, point2): 이름에서 알 수 있듯, 이 관계는 지점 point1과 지점 point2 사이에 CFG 엣지가 있음을 저장합니다.

각 MIR 문장 위치마다 Polonius의 지점(point)이 2개 생성됩니다: "Start" 지점과 "Mid" 지점(다른 Polonius 입력들 중 일부는 나중에 각 지점에 기록됩니다). 이 두 지점은 이 관계에 기록된 엣지로 연결됩니다.

그 다음, 또 다른 엣지가 기록되어 이 MIR 문장을 그 후속 문장과 연결합니다: 현재 위치의 mid 지점에서 후속 위치의 start 지점으로. MIR에서 인코딩은 다를 수 있지만, 후속 위치가 다른 블록에 있을 때에도 동일하게 적용되어, 현재 위치의 mid 지점을 후속 블록의 시작 위치의 start 지점과 연결합니다.

예를 들어, 이 MIR의 경우(예시를 명확히 하기 위해 편집했고, CFG와 관련된 부분만 보여줍니다):

#![allow(unused)]
fn main() {
bb0: {
  ...          // bb0[0]
  ...          // bb0[1]
  goto -> bb3; // bb0[2]
}

...

bb3: {
  ... // bb3[0]
}

}

cfg_edge 관계에 다음과 같은 입력 팩트를 기록합니다(앞서 언급했듯, 내부적으로 interning됩니다). 여기서는 의사 Rust로 보여줍니다:

#![allow(unused)]
fn main() {
cfg_edge = vec![
  // 위치 bb0[0]의 문장:
  (bb0-0-start, bb0-0-mid),
  (bb0-0-mid, bb0-1-start),
  
  // 위치 bb0[1]의 문장:
  (bb0-1-start, bb0-1-mid),
  (bb0-1-mid, bb0-2-start),
  
  // 위치 bb0[2]의 terminator:
  (bb0-2-start, bb0-2-mid),
  (bb0-2-mid, bb3-0-start),
];
}

2. `loan_issued_at`

loan_issued_at(origin, loan, point): 이 관계는 loan loan이 주어진 지점 point에서 "발급(issued)"되어, origin이라는 원천을 가진 참조를 만들었음을 저장합니다. origin은 point 시점부터 loan의 데이터를 참조할 수 있습니다(보통 차용 rvalue의 이후 지점). loan이 발급되는 origin을 "발급 origin(issuing origin)"이라고 부르며(과거에는 borrow_region이라고 불렀기 때문에, Polonius나 rustc에서 이 용어를 여전히 접할 수 있습니다).

각 차용 표현식마다 loan이 만들어지고, 이 loan을 차용 표현식의 origin과 연결하는 팩트가 이 관계에 저장됩니다.

예를 들어,

#![allow(unused)]
fn main() {
let mut a = 0;
let r = &mut a; // 여기서 loan L0가 생성됨
//      ^ 이를 'a라고 합시다
}

이 지점에서 L0를 'a에 연결하는 loan_issued_at 팩트가 생깁니다. 이 loan은 CFG와 origin 사이의 부분집합 관계를 따라 흐르고, 계산 과정은 그 조건이 지켜지도록 요구하며, 그렇지 않으면 불법 접근 오류를 생성합니다.

3. `placeholder` (및 `universal_region`)

placeholder(origin, loan): origin이 플레이스홀더 origin이며, 그에 연관된 플레이스홀더 loan이 loan임을 저장합니다(현재는 universal_region(origin)도 여전히 존재하며, loan 없이 origin에 대해 같은 사실을 서술하고 있는데, 점차 폐지되는 중입니다). 이 origin들은 역사적으로, 특히 rustc에서 "보편 수명(universal region)"이나 "자유 수명(free region)" 등으로 불렸지만, 우리가 검사하는 MIR 본문 안에서 정의되지 않은 origin을 나타냅니다. 이들은 이 함수의 호출자 쪽에 속합니다: 그 loan들은 현재 함수에겐 알려져 있지 않으며, 함수는 그 origin에 대해(아래의 known_placeholder_subset 관계에서 보게 될, 서로 다른 플레이스홀더 origin 간의 관계를 제외하고는) 가정할 수 없습니다. 이러한 플레이스홀더에서 온 loan이 유용할 수 있는 계산(예: 불법 부분집합 관계 오류)에서는, 해당 연관 플레이스홀더 loan을 사용할 수 있습니다.

이는 기본 플레이스홀더 origin('static)과, 수명에 대해 제네릭한 함수에 정의된 origin들을 포함합니다. 예를 들어,

#![allow(unused)]
fn main() {
fn my_function<'a, 'b>(x: &'a u32, y: &'b u32) {
    ...
}
}

placeholder 관계에는 'a와 'b에 대한 팩트도 포함됩니다.

4. `loan_killed_at`

loan_killed_at(loan, point): 이 관계는 loan loan에서 차용된 경로의 접두 경로(prefix)가 지점 point에서 할당/덮어써졌음을 저장합니다. 이는 loan이 차용한 경로가 어떤 방식으로든 변경되어, 더 이상 그 loan을 추적할 필요가 없음을 나타냅니다. (특히, 차용된 경로에 대한 변형이 더 이상 그 loan을 무효화하지 않습니다)

예를 들어,

#![allow(unused)]
fn main() {
let mut a = 1;
let mut b = 2;
let mut q = &mut a;
let r = &mut *q; // `*q`에 대한 loan L0
// `q`는 여기서 사용할 수 없고, 반드시 `r`을 통해야 함
q = &mut b; // killed(L0)
// 이제 `q`와 `r`을 사용할 수 있음
}

할당으로 인해 loan L0가 "kill"되며, 이 사실이 loan_killed_at 관계에 저장됩니다. CFG를 따라 origin이 담는 loan들을 계산할 때, loan_killed_at 지점은 이 loan이 다음 CFG 지점으로 전파되는 것을 막습니다.

5. `subset_base`

subset_base(origin1, origin2, point): 이 관계는 지점 point에서 origin origin1이 origin origin2보다 오래 산다는(outlives) 사실을 저장합니다.

이는 표준 러스트 문법인 'a: 'b로, 수명 'a가 수명 'b보다 오래 산다는 뜻입니다. origin을 loan의 집합으로 보는 관점에서는, 이것을 부분집합 관계로 봅니다: 'a의 모든 loan이 'b로 흘러 들어가므로, 'a가 담는 loan은 'b가 담는 loan의 부분집합입니다.

타입 시스템은 참조에 대한 서브타이핑 규칙을 정의하며, 이는 참조 타입을 피참조 타입과 subset으로 연관 짓는 "오래 산다(outlives)" 팩트를 생성합니다.

(_base 접미사는 이 관계가 추이적이지 않으며, 추이 폐쇄(transitive closure) 계산의 기반이 됨을 나타냅니다)

예를 들어:

#![allow(unused)]
fn main() {
let a: u32 = 1;
let b: &u32 = &a;
//            ^ 이를 'a라고 합시다
//     ^ 그리고 이를 'b라고 합시다
}

이 마지막 표현식이 유효하려면, 타입 &'a u32가 &'b u32의 서브타입이어야 합니다. 이는 'a: 'b를 요구하며, subset_base 관계는 이 지점에서 'a가 'b보다 오래 산다/부분집합이다/'b로 흘러 들어간다는 기본 사실을 포함하게 됩니다.

6. `origin_live_at`

origin_live_at(origin, point): 이 관계는 origin origin이 지점 point에서 라이브 변수에 나타남을 저장합니다.

이 팩트들은 liveness 계산에 의해 생성되며, 그 팩트와 관계는 나중에 더 자세히 설명됩니다. 그 사이 구현은 여기 liveness.rs에서 볼 수 있습니다.

7. `loan_invalidated_at`

loan_invalidated_at(point, loan): 이 관계는 지점 point에서 발생한 어떤 동작에 의해 loan loan이 무효화(invalidate)되었음을 저장합니다.

loan에는 지켜야 할 조건이 있습니다: 공유 loan은 읽기 전용이어야 하고 쓰기나 변형에 사용되면 안 되며, 가변 loan은 참조 대상에 접근하는 유일한 방법이어야 합니다. loan이 차용한 경로에 대한 불법 접근은 그 loan의 조건을 _무효화_한다고 하며, 이 사실은 loan_invalidated_at 관계에 기록됩니다. _라이브_한 loan에 대해 이러한 동작이 발생하면 오류입니다.

차용 검사 분석의 목표가 이러한 가능한 오류를 찾는 것이므로, 이 관계는 계산에서 중요합니다. 이 관계가 담는 모든 loan, 그리고 그 결과 해당 loan을 담는 모든 origin은, 계산이 추적하는 핵심 팩트입니다.

8. `known_placeholder_subset`

known_placeholder_subset(origin1, origin2): 이 관계는 두 플레이스홀더 origin 사이의 관계, 즉 플레이스홀더 origin origin1이 플레이스홀더 origin origin2의 부분집합임을 저장합니다. 이 관계는 사용자가 함수 선언에서 명시적으로 선언할 수도 있고, 암시 경계(implied bounds)를 통해 추론될 수도 있습니다.

예를 들어, 다음 함수는:

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

두 개의 known_placeholder_subset 엔트리를 갖게 됩니다:

사용자 지정 부분집합인 'b: 'a에 대한 것 하나
매개변수 x로부터의 암시 경계인 'a: 'c에 대한 것 하나

이 두 엔트리로부터 나오는 추이적 부분집합 'b: 'c는 반드시 이 관계에 명시적으로 포함되어 있지는 않을 수 있습니다. Polonius는 불법 부분집합 관계 오류 분석을 위해 모든 추이적 부분집합을 추론합니다: 함수 분석에서 두 플레이스홀더가 서로 연관되어 있다고 판단되는데, 이 사실이 알려진 부분집합에 선언되어 있지 않다면, 그것은 오류가 됩니다.

입력 관계

Polonius는 "입력 팩트"로부터 분석을 시작합니다. 이는 러스트 코드(대부분: 하나의 함수)에 대한 작은 정보 데이터베이스로 볼 수 있습니다.

가장 단순한 관계부터 시작해 봅시다: cfg_edge 관계로 표현되는 제어 흐름 그래프(Control Flow Graph).

1. `cfg_edge`

cfg_edge(point1, point2): 이름에서 알 수 있듯, 이 관계는 지점 point1과 지점 point2 사이에 CFG 엣지가 있음을 저장합니다.

예를 들어, 이 MIR의 경우(예시를 명확히 하기 위해 편집했고, CFG와 관련된 부분만 보여줍니다):

#![allow(unused)]
fn main() {
bb0: {
  ...          // bb0[0]
  ...          // bb0[1]
  goto -> bb3; // bb0[2]
}

...

bb3: {
  ... // bb3[0]
}

}

cfg_edge 관계에 다음과 같은 입력 팩트를 기록합니다(앞서 언급했듯, 내부적으로 interning됩니다). 여기서는 의사 Rust로 보여줍니다:

#![allow(unused)]
fn main() {
cfg_edge = vec![
  // 위치 bb0[0]의 문장:
  (bb0-0-start, bb0-0-mid),
  (bb0-0-mid, bb0-1-start),
  
  // 위치 bb0[1]의 문장:
  (bb0-1-start, bb0-1-mid),
  (bb0-1-mid, bb0-2-start),
  
  // 위치 bb0[2]의 terminator:
  (bb0-2-start, bb0-2-mid),
  (bb0-2-mid, bb3-0-start),
];
}

2. `loan_issued_at`

각 차용 표현식마다 loan이 만들어지고, 이 loan을 차용 표현식의 origin과 연결하는 팩트가 이 관계에 저장됩니다.

예를 들어,

#![allow(unused)]
fn main() {
let mut a = 0;
let r = &mut a; // 여기서 loan L0가 생성됨
//      ^ 이를 'a라고 합시다
}

3. `placeholder` (및 `universal_region`)

이는 기본 플레이스홀더 origin('static)과, 수명에 대해 제네릭한 함수에 정의된 origin들을 포함합니다. 예를 들어,

#![allow(unused)]
fn main() {
fn my_function<'a, 'b>(x: &'a u32, y: &'b u32) {
    ...
}
}

placeholder 관계에는 'a와 'b에 대한 팩트도 포함됩니다.

4. `loan_killed_at`

예를 들어,

#![allow(unused)]
fn main() {
let mut a = 1;
let mut b = 2;
let mut q = &mut a;
let r = &mut *q; // `*q`에 대한 loan L0
// `q`는 여기서 사용할 수 없고, 반드시 `r`을 통해야 함
q = &mut b; // killed(L0)
// 이제 `q`와 `r`을 사용할 수 있음
}

5. `subset_base`

subset_base(origin1, origin2, point): 이 관계는 지점 point에서 origin origin1이 origin origin2보다 오래 산다는(outlives) 사실을 저장합니다.

(_base 접미사는 이 관계가 추이적이지 않으며, 추이 폐쇄(transitive closure) 계산의 기반이 됨을 나타냅니다)

예를 들어:

#![allow(unused)]
fn main() {
let a: u32 = 1;
let b: &u32 = &a;
//            ^ 이를 'a라고 합시다
//     ^ 그리고 이를 'b라고 합시다
}

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

두 개의 known_placeholder_subset 엔트리를 갖게 됩니다:

사용자 지정 부분집합인 'b: 'a에 대한 것 하나
매개변수 x로부터의 암시 경계인 'a: 'c에 대한 것 하나