Rust의 동적 크기 타입(DST)을 다형적 제네릭의 관점에서 설명하고, 메타데이터와 Value Witness의 관계, 그리고 여러 메타데이터를 갖는 미래의 확장 가능성을 살펴본다.
Faultlore
Faultlore
Aria Desires
2022년 3월 30일
이 글은 eddyb를 대신해 작성되었으며, 그들이 Rust의 설계 세부 사항 중 근본적으로 참이라고 이해하고 있지만 어디에서도 제대로 설명되거나 문서화되지 않은 내용을 표현할 수 있도록 돕기 위한 것이다. 도움이 되기를 바란다!
Rust에는 DST(“동적 크기 타입”)라는 기능이 있으며, 이를 통해 컴파일 시점에는 크기를 알 수 없는 어떤 데이터에 대한 포인터를 가질 수 있다. 이것은 “슬라이스”(&mut [T], &str)에서 사실상 어디에나 사용되며, “트레이트 객체”(Box<dyn MyTrait>)의 핵심 구성 요소이기도 하다.
DST 포인터는 예상하는 일반 포인터 그리고 DST를 다룰 수 있게 해주는 동적인 Metadata 를 모두 담아야 하므로 “wide”하다. 그 결과 DST 포인터는 사실상 구조체가 변장한 형태이며, 여기서는 이를 (&void, Metadata)로 줄여 쓰겠다.
현재 Metadata에는 3가지 종류가 있다:
usize&'static VTable이 두 가지 비자명한 Metadata는 언어 자체에 내장된 두 가지 Fundamental DST, 즉 [T]와 dyn Trait에서 온다(extern type는 Thin이다). Rust 사용자는 두 가지 방법 중 하나로 새로운 DST를 만들 수 있다:
전자에 대한 예시로는 str을 볼 수 있는데, 이것은 단지 struct str([u8])이며 올바른 슬라이스 포인터를 만든 뒤 transmute해서 구성된다(&[u8] =>&str).
후자에 대한 예시로는 다음과 같은 것을 정의할 수 있다:
struct MyGeneric<T> {
some_field: bool,
data: T,
}
그리고 &MyGeneric<[T; N]>를 &MyGeneric<[T]>로 Unsize 할 수 있다.
어느 경우든, 이를 감싸는 추가 구조체를 도입함으로써 Fundamental DST로부터 어느 정도의 “거리”를 만들어냈다. 이러한 래핑 구조체는 어쩔 수 없이 DST가 되지만, 중요하게도 Metadata는 바뀌지 않는다. Rust는 여전히 Fundamental DST에 대한 Metadata만 저장하며, 그로부터 나머지를 모두 알아낼 수 있다.
현재 모든 DST는 다음 규칙을 따라야 한다:
&, *mut, Box, …) “완성”되어야 한다이 글에서는 첫 번째 조건은 다루지 않는다. 값으로서의 DST를 사랑하는 이들에게는 미안하다. 하지만 나머지 조건을 느슨하게 만드는 것이 무엇을 의미하는지는 살펴볼 것이다.
Trailing 규칙은 대체로 단순성을 위해 존재하며, 이를 지원하도록 컴파일러에 충분한 작업을 하면 겉보기에는 “그냥” 없앨 수 있을 것처럼 보인다. 하지만 한 가지 경우는 예외인데, 바로 제네릭 이다. 제네릭은 하나의 타입 이름을 붙이고 그것을 구조체 안에서 여러 번 반복할 수 있게 해준다. 가장 단순한 예가 배열이다: &[dyn MyTrait; 8]은 “하나의” DST를 “여덟 개”로 바꾼다. 이것이 무엇을 의미할까? 더 많은 Metadata가 필요할까?
이 지점에서 Solitary 규칙으로 넘어가게 된다. Solitary 조건을 깨는 방법은 두 가지다: 여러 Fundamental DST가 서로 이웃 하거나 중첩 되는 경우다.
(dyn MyTrait1, dyn MyTrait2) 같은 타입은 이웃한 Fundamental DST들을 가진다.
[dyn Trait] 같은 타입은 중첩된 Fundamental DST를 가진다.
어느 경우든 우리는 분명 여러 개의 Metadata가 필요하고, 그러면 포인터는 점점 더 넓어지게 된다. 거의 SIMD 수준으로 넓어진다고 할 수 있다. 아니, 사실은 VLDSTM 포인터(Very Large Dynamically Sized Type Metadata)와 함께라면 Itanium 수준으로 넓어진다고 해야 할지도 모르겠다!
그런데 이런 타입들은 실제로 몇 개의 Metadata를 담고 있을까? &[&dyn Trait] 같은 타입을 보면 임의로 많은 Metadata가 있다. 왜냐하면 중첩된 각 &dyn Trait가 Trait의 서로 다른 구현자일 수 있기 때문이다. 그렇다면 &[dyn Trait]는 무한히 넓어야 할까? 결과적으로는 그렇지 않다! Metadata가 임의로 많아지는 이유는 포인터 가 임의로 많기 때문이다. 각 포인터는 자기만의 독립적인 Metadata를 갖는다. 하지만 &[dyn Trait] 같은 타입에는 포인터가 하나뿐이므로, 모두가 공유해야 한다.
이 점을 이해하기 위해 간단한 제네릭 함수를 생각해보자:
fn my_generic<T: Clone>(val: T) {
let a = val.clone();
let b = val.clone();
}
이 코드는 Clone을 구현하는 어떤 타입 T도 처리할 수 있다. 그런데 잠깐, 이것을 값으로 전달하고 있지 않은가! Indirection 규칙에 따르면 Rust는 이것이 “불가능”하다고 생각하는 것 아닌가? 실제로 그렇고, 그래서 Rust는 요령을 쓴다. Rust는 제네릭을 단형화(monomorphize) 해서 없애버리는데, 이는 거창하게 말한 것일 뿐이고 실제로는 이 함수를 호출할 때마다 Rust가 T를 실제 사용하는 타입으로 치환한 복사본을 생성한다는 뜻이다. 그래서 여기에 u32를 넘기면, Rust는 그냥 다음을 만든다:
fn my_generic_u32(val: u32) {
let a = val.clone();
let b = val.clone();
}
물론 이런 것은 Rust가 아주 잘 다룰 수 있다. Rust는 제네릭 타입 에 대해서도 정확히 같은 전략을 적용한다. 끝까지 복사-붙여넣기인 셈이다. 이것은 단순하지만 효과적인 접근법이지만, 한 가지 단점이 있다: 제네릭 함수 포인터를 가질 수 없다는 점이다!
Rust는 my_generic_u32를 fn(u32) -> ()로 바꾸는 것은 기꺼이 허용하지만, my_generic를 fn<T: Clone>(T) -> ()로 만드는 것은 허용하지 않는다. 모든 단형화는 정적으로 (컴파일 시점에) 처리되며, 각 타입 치환마다 새로운 함수 포인터를 만든다. 설령 vtable로 “여러 함수 포인터” 문제를 해결한다고 해도, 그것만으로는 충분하지 않다. 함수 포인터는 동적인 (런타임) 구성물이기 때문에, 컴파일러는 가능한 모든 단형화를 예측할 수 없기 때문이다.
Java 같은 언어는 이 문제를 모든 타입을 항상 간접 참조하게 만드는 방식으로 해결한다. 그리고 바로 그 이유 때문에 Rust처럼 인라인 레이아웃을 갖는 언어는 다형적 제네릭을 가질 수 없다.
어, 거기 있었네 Swift! 이런 문제가 우리 같은 인라인 레이아웃 언어에는 참 성가시지 않나? 뭐라고? 다형적 제네릭이 있다고??? 어째서??? 방금 그게 불가능하다고 설명을 끝낸 참인데!
Swift는 실제로 다형적인 스택 변수를 boxing으로 간접화해야 하지만, 스택의 “루트”만 지나고 나면 실제 값들은 단형화했을 때와 같은 레이아웃을 가진다! Swift는 이를 위해 Value Witness Tables 라고 부르는 것을 사용한다. Value Witness Tables는 타입에 대한 정보로 가득 찬 vtable일 뿐이다: 크기, 정렬, stride(매콤한 크기), clone 구현, move 구현 등.
다음과 같은 제네릭 함수가 있을 때
func SwiftyGeneric<T, U, V>(arg1: T, arg2: U)
Swift에게 이것을 함수 포인터로 바꾸라고 요청하면, 실제로 생성되는 것 은 대략 다음과 같은 형태다:
func SwiftyGeneric<T, U, V>(
arg1: Pointer<T>,
arg2: Pointer<U>,
witness_T: ValueWitnessTable,
witness_U: ValueWitnessTable,
witness_V: ValueWitnessTable
)
이제 SwiftyGeneric의 본문 안에서는, 제네릭 타입의 인스턴스를 다뤄야 할 때마다 Value Witness Table에 필요한 정보를 물어보기만 하면 되고, 심지어 그것을 다른 제네릭 코드에 전달 할 수도 있다. SwiftyGeneric 안에서 Array<T>를 만들어야 한다고? 문제없다. Array 코드에 witness_T를 넘겨주기만 하면, 그 코드는 witness_T.size/align/stride를 사용해서 얼마나 많은 메모리를 할당해야 하는지와 모든 오프셋을 알아낼 수 있다!
내 설명이 간단해 보이게 만들고 있지만, 이것을 실제로 구현하는 데 얼마나 많은 일이 필요한지는 아무리 강조해도 지나치지 않다. 특히 제네릭 함수 포인터 내부에서 제네릭 타입이 인스턴스화될 수 있다는 사실은, 런타임에 Value Witness Table을 생성할 수 있어야 한다 는 뜻이다 🙀. Rust는 초기 1.0 이전 시절에 다형적 제네릭을 가지려고 시도 했지만, 너무 많은 작업이 필요했기 때문에 지극히 합리적으로 포기했다. 진심으로 Swift, 이 모든 것을 작동하게 만든 것은 정말 엄청난 일이다!
흠, 좀 딴길로 새 버렸나? 아니, 물론 아니다! 이 절의 제목을 보라! Metadata는 그냥 Value Witness일 뿐이다. dyn Trait의 Metadata는 문자 그대로 끝에 Trait의 메서드들을 덧붙인 Value Witness Table이다! 슬라이스는 그렇게 많은 것이 필요 없으므로, 우리에게 필요한 것은 그저 Value Witness Length(usize)뿐이다.
중요한 점은, 이런 다형적 제네릭은 완전한 다형적 함수 포인터에 비하면 훨씬 얌전하다 는 것이다. “런타임에 Value Witness Table 생성하기”라는 문제는 완전히 사라지고, 실제로 모든 Metadata(Value Witness)를 미리 생성해 둘 수 있다. 이것은… 훨씬 더 다루기 쉬운 일이다!
이제 이 점을 확립했으니, 여러 Metadata에 대한 까다로운 질문으로 다시 돌아갈 수 있다. &[dyn Trait]는 무엇을 의미하는가? 이것은 다음을 의미한다:
&<T: Trait, const N: usize>[T; N]
그냥 다형적 제네릭일 뿐이다! DST는 그냥 다형적 제네릭일 뿐이다! 물론 우리는 타입 변수를 이름 붙이는 것이 “허용되지” 않으므로, 실제로는 다음에 더 가깝다:
&[impl Trait; impl const usize]
하지만 이것은 첫 번째 버전에 대한 “그냥” 문법 설탕일 뿐이다. DST를 제네릭으로 디슈가링하면, 모든 답은 비교적 단순해진다.
모든 것이 제네릭이므로, 중첩은 모든 복사본이 동일해지게 만든다:
syntax: &[dyn Trait],
meaning: (&[T; N], (T: &VTable, N: usize)),
repr: (&void, (&VTable, usize)),
문제가 되는 비후행 경우는 단지 중첩의 특별한 경우다:
syntax: &[dyn Trait; 8],
meaning: (&[T, 8], (T: &VTable)),
repr: (&void, (&Vtable)),
이웃한 경우는 각 Fundamental DST마다 새로운 타입 변수를 갖는 것일 뿐이다:
syntax: &(dyn Trait, dyn Trait),
meaning: (&(T, U), (T: &VTable, U: &VTable)),
repr: (&void, (&VTable, &VTable)),
중첩된 슬라이스는 그냥 중첩된 배열이며(따라서 반드시 “직사각형”이어야 한다):
syntax: &[[[u8]]],
meaning: (&[[[u8; A]; B]; C], (A: usize, B: usize, C: usize)),
repr: (&void, (usize, usize, usize)),
그리고 나면 임의의 구조로 이것들을 마음껏 조합할 수 있다:
syntax: &(dyn Trait, u32, [dyn Trait], bool),
meaning: (&(T, u32, [U; N], bool), (T: &VTable, U: &VTable, N: usize)),
repr: (&void, (&VTable, &VTable, usize)),
이것이 전부다! Rust가 제한을 느슨하게 하고 VLDSTM의 세계로 들어간다는 것이 의미하는 것 은 바로 이것이다: 새 제네릭 하나마다 추가 Metadata가 하나씩 생기고, 배열 stride보다 더 복잡한 것을 처리하기 위해 Trailing 규칙에 의존하는 대신 Metadata를 사용해 임의의 필드 오프셋을 동적으로 계산해야 한다는 점이다.
주의 깊은 독자라면 내가 “안쪽” Metadata를 “바깥쪽” Metadata보다 앞에 두고 있다는 점을 눈치챘을지도 모른다. 이것은 순전히 &my_dst.field가 &my_dst의 접두사 가 되도록 만들고 싶다는 내 미적 집착 때문이며, 그렇게 하면 메타데이터를 전혀 재배치할 필요가 없다. 이 점은 &[[[u8]]]를 인덱싱하는 경우에서 가장 쉽게 볼 수 있다.
현실에서는 Metadata가 내가 보여준 것보다 더 중첩되고 구조화되어 있을 가능성이 크다. 그러면 Metadata 표현을 파고들어 DST Wizard Magic을 하고 싶은 라이브러리 코드가 그것을 이해할 수 있게 된다.
그래서 마지막의 초복잡한 예시는 아마 다음과 같은 구조를 가질 수도 있다:
// let super_complex: &(dyn Trait, u32, [dyn Trait], bool) = ...;
DST {
pointer: &void,
metadata: Aggregate(
0: TraitObject(&VTable),
1: Slice {
len: usize,
elem: TraitObject(&VTable),
},
),
}
그리고 &super_complex.0라는 표현식은 실제로는 다음과 같은 표현식일 수도 있다:
// &super_complex.0
DST {
pointer: &(*super_complex.pointer).0,
metadata: super_complex.metadata.0.clone(),
}
이 역시 모든 타입이 다음과 같은 멋지고 작은 제네릭 조합 가능한 조각들로 이루어져 있다는, 그보다도 더 깊은 현실 위에 덧씌워진 문법 설탕일 뿐이다:
struct DST<P, M: Metadata> {
pointer: P,
metadata: M,
}
struct SliceMetadata<T: Metadata> {
len: usize,
elem: T,
}
...
하지만 이런 세부 사항은 내 급여 수준을 넘어서는 일이고, 이것은 어디까지나 개념 에 대한 스케치일 뿐이다.
(면책 조항: 나는 Metadata와 DST에 관한 최신 작업을 계속 추적하고 있지는 않지만, 내 이해로는 이것이 적어도 개념적으로는 그 작업과 양립 가능하다. 여기서는 주로 eddyb의 메모와 내 자신의 기억에 의존하고 있다.)