Rust 컴파일러 팀이 트레이트 솔버를 재작성해 타입 시스템의 향후 변경을 단순화하고, 미묘한 건전성 버그를 수정하며, 컴파일 시간을 단축하려 하고 있다. 거의 완성 단계에 이른 이 차세대 솔버는 순환적인 트레이트 의무 처리와 더 나은 캐싱, 향상된 오류 메시지를 약속한다.
기사로 이동 Rust의 컴파일러 팀은 트레이트 솔버를 재작성하는 장기 프로젝트를 진행해 왔다. 트레이트 솔버는 프로그래머가 여러 타입에 대해 구현된 트레이트 메서드를 사용할 때 어떤 구체적인 함수를 호출해야 하는지를 결정하는 컴파일러의 부분이다. 이 재작성의 목적은 트레이트 시스템의 향후 변경을 단순화하고, 까다로운 건전성 버그 몇 가지를 수정하며, 더 빠른 컴파일 시간을 제공하는 것이다. 또한 이 작업은 거의 마무리 단계에 있으며, 남아 있는 차단 버그의 수도 비교적 적다.
Rust의 트레이트는 Haskell의 typeclasses나 Java의 interfaces와 비슷하다. 즉, 서로 다른 타입에 대해 구현될 수 있는 연관 함수들의 집합이다. 라이브러리 코드는 어떤 타입이 그 트레이트를 구현하기만 하면, 그 타입이 라이브러리 외부에서 정의된 것이라 해도 트레이트의 함수를 사용할 수 있다. 그러나 실제로 코드를 생성할 시점이 되면, 컴파일러는 어떤 구체적인 타입이 사용되고 있는지, 그리고 그 타입의 트레이트 구현이 어디에 있는지를 알아야 올바른 함수를 호출할 수 있다. 트레이트 구현은 제네릭일 수 있으므로 여러 구체 타입에 적용될 수 있다. 특정 타입에 어떤 트레이트 구현이 해당하는지를 알아내는 일이 컴파일러의 트레이트 솔버 역할이다.
대부분의 경우 이것은 간단하다. 컴파일러는 그저 impl Trait for Type {...} 형태의 트레이트 구현을 찾으면 된다. 문제는 제네릭 타입을 고려할 때 더 복잡해진다. 예를 들어 Vec는 그 안에 담긴 원소의 타입이 cloned될 수 있을 때에만 복제될 수 있다. 표준 라이브러리에는 트레이트 구현 블록이 하나 있으며, 이는 다음과 동등하다. 일부 문법적 설탕을 펼치고 관련 없는 A 매개변수는 무시한 형태다.
impl<T> Clone for Vec<T>
where T: Clone
{ ... }
이 선언은 트레이트 솔버에 대한 지시로 볼 수 있다. 즉 Vec<Foo>에 대한 Clone 구현을 찾으려면 먼저 Foo에 대한 Clone 구현을 찾아야 한다는 뜻이다. 그 구현을 사용해 Vec<Foo>에 대한 동작하는 구현을 구성할 수 있다. 현재의 트레이트 솔버는 이런 지시의 사슬을 따라가며 비교적 단순한 방식으로 처리한다. 찾아야 하는 각 트레이트 구현마다, impl 문을 찾는 것이 가장 적절한지 아니면 where-bound, 즉 어떤 제네릭 타입이 트레이트를 구현한다고 주장하는 where 절을 사용하는 것이 가장 적절한지를 결정한다. 이들은 Vec 예시처럼 다른 트레이트 구현의 존재에 의존할 수 있으며, 그런 경우 컴파일러는 그것들을 작업 목록에 추가한다. 논리 프로그래밍에서는 다른 목표에 도달하기 위해 충족되어야 하는 이런 종류의 선행 조건을 obligation이라고 부른다. 컴파일러는 작업 목록에서 obligation을 계속 꺼내 처리하여 모두 제거될 때까지 진행한다. 제거할 수 없다면 오류가 표시된다.
하지만 더 복잡한 타입에서는 이 접근법이 무너진다. 해소해야 할 obligation이 루프를 이루는 상황을 만들 수 있기 때문이다. 다만 그렇게 만드는 것은 다소 복잡해서 최소 예제조차도 조금 길다.
// Create a trait that has an associated generic type. Types that implement
// Wrap correspond to a particular choice of Wrapper.
trait Wrap {
type Wrapper<T>;
}
// A singly linked list structure, with the payload omitted for brevity.
// Each 'next' pointer goes to another list node wrapped in the Wrapper type
// for some generic type W that must implement Wrap
struct Link<W: Wrap> {
next: Option<Box<W::Wrapper<Link<W>>>>
}
// Link structures can be formatted for debug print statements when their
// contents can be — the omitted implementation calls the Debug
// implementation for next's type, hence the second requirement.
impl<W> Debug for Link<W>
where W: Wrap,
Option<Box<W::Wrapper<Link<W>>>>: Debug {
...
}
// My Wrapper is a structure that wraps some other type T as its only field.
struct MyWrapper<T = ()>(T);
// And its associated wrapper type is just itself.
impl Wrap for MyWrapper {
type Wrapper<T> = MyWrapper<T>;
}
// Finally, wrappers can be formatted for debug print statements when the
// wrapped value can be.
impl<T> Debug for MyWrapper<T>
where T: Debug { ... }
컴파일러가 Link<MyWrapper>가 Debug를 구현한다는 것을 증명하려면, 다음과 같은 요구사항의 연쇄 전체가 성립함을 보여야 한다.
Link<MyWrapper>: Debug ->
Option<Box<MyWrapper::Wrapper<Link<MyWrapper>>>>: Debug ->
Box<MyWrapper::Wrapper<Link<MyWrapper>>>: Debug ->
MyWrapper::Wrapper<Link<MyWrapper>>: Debug ->
Link<MyWrapper>: Debug
…하지만 그 연쇄는 결국 컴파일러를 다시 출발점으로 되돌려 보낸다. Link의 Debug 구현을 사용하는 Rust 프로그램을 컴파일하려 하면 "overflow evaluating the requirement Link<MyWrapper>: Debug"라는 오류가 발생한다.
하지만 이 경우에는 이론적으로 컴파일러가 Debug 구현을 생성할 수 있어야 한다. 자기 자신의 주소를 참조하는 명령을 어셈블러가 처리할 수 있는 것과 같은 이유다. 컴파일러는 우선 구현 생성을 시작하면서 주소에 대한 자리표시자를 남겨 두고, 그 주소를 알게 되면 나중에 채워 넣을 수 있다. 트레이트 솔버가 동작하는 단계에서는 실제 주소를 다루는 것이 아니지만, 같은 아이디어가 적용된다. Link<MyWrapper>에 대한 Debug 구현을 작성하는 것은 생성할 코드를 나타내는 데이터 구조에서 스스로를 참조하는 구조를 만들도록 “매듭을 묶는” 문제다.
위 예시는 인위적이지만, 그것은 언어의 이런 한계가 대체로 복잡하고 매우 제네릭한 코드에서 나타나기 때문이다. 자기 참조 타입 자체는 새로운 것이 아니다. 문제는 트레이트로 그것들을 추상화하려고 할 때 생긴다. 그런 코드는 모든 프로그래머가 반드시 작성해야 하는 것은 아니지만, Rust 라이브러리를 더 유연하게 만들 수 있다. 현재 크레이트 작성자는 트레이트 솔버에 루프가 생기지 않도록 인터페이스를 재구성하여 이 트레이트 해석 문제를 우회해야 한다.
하지만 트레이트 솔버의 동작 방식이 문제 자체의 본질적인 측면인 것은 아니다. 이것은 언어의 트레이트 시스템이 서서히 복잡해지는 과정에서 사실상 기본 선택으로 채택된 구현상의 선택이다. 트레이트 솔버 재작성 프로젝트는 2015년에 Chalk와 함께 시작되었다. Chalk는 Rust의 타입 시스템을 형식화하려는 시도다. 그것은 트레이트 풀이의 메커니즘 같은 타입 시스템의 규칙을 Prolog와 비슷한 논리 추론 규칙 체계로 컴파일한 뒤, 잘 알려진 논리 프로그래밍 기법으로 일반적으로 풀 수 있게 한다. Chalk에는 각기 장단점을 지닌 두 가지 내부 논리 추론 구현이 있다. SLG 솔버와 재귀 솔버다. SLG 솔버는 Prolog의 tabling에 기반한 접근을 사용하고, 재귀 솔버는 Rust의 원래 트레이트 솔버 동작에 더 가깝다. SLG 솔버는 재귀 솔버가 처리하지 못하는 몇몇 종류의 루프를 다룰 수 있다.
하지만 Rust 개발자들은 Chalk가 Rust 컴파일러에 잘 맞지 않는다고 판단했다. 큰 우려 중 하나는 오류 메시지의 유용성을 유지하는 문제였다. 현재 구현은 단순한 실수에 대해 좋은 오류 메시지를 내지만, Chalk의 오류 메시지는 그에 뒤처져 있었다. 2023년에 이 프로젝트는 결정했다. 첫 번째 구현과 Chalk에서 얻은 교훈을 활용해, 컴파일러 내부에서 트레이트 솔버를 다시 작성하기로 한 것이다.
차세대 트레이트 솔버라고 불리는 이 재작성은 트레이트 풀이를 빠르게 하고 순환을 극복하기 위해 캐싱을 사용한다. 어떤 타입에 대한 트레이트 구현을 찾기 시작하라는 요청을 받으면, 먼저 그런 구현이 발견될 것이라고 가정하고 캐시에 그 자리를 만든다. 이 항목은 잠정적으로 참으로 표시되지만, 아직 완전히 신뢰할 수는 없다. 그런 다음 솔버는 현재 솔버와 거의 같은 방식으로 논리 추론의 사슬을 따라가되, 가능한 경우 캐시에서 결과를 조회한다. 새로운 정보를 도출하면 그것을 캐시에 추가하고, 그 새 정보를 도출하는 데 잠정적 캐시 항목이 사용되었다면 새 항목 역시 잠정적으로 표시된다.
트레이트 솔버가 어느 시점에 도달했을 때 남은 논리 obligation이 모두 잠정적으로 참인 캐시 항목만을 가리킨다면, 그 항목들은 실제로 참으로 승격되어 다른 타입 검사 작업에서 참조할 수 있게 된다. 반대로 그런 시점에 도달하지 못하면, 잠정적 캐시 항목은 무효화되고 그 계산 분기는 실패한 것으로 간주된다. 그 결과 전체가 실패하여 사용자에게 오류를 보여 주거나, 다른 가능한 대안 해법을 계속 시도하게 된다.
위 예시의 경우, 새 솔버가 두 번째로 Link<MyWrapper>가 Debug를 구현함을 증명해야 하는 상태에 도달하면, 이전 탐색에서 그 트레이트 구현이 잠정적으로 참으로 캐시되어 있음을 보고 다른 논리 obligation이 없으므로 Link<MyWrapper>가 실제로 Debug를 구현한다고 결론내릴 것이다.
현재 차세대 트레이트 솔버는 잠정적 캐시 항목이라는 개념을 Send 같은 제한된 수의 내장 트레이트에만 확장하고 있지만, 계획은 결국 이 동작을 모든 트레이트에 대해 활성화하는 것이다. Rust 개발자들은 이 기능을 활성화하면 지금은 컴파일되지 않는 일부 코드, 예를 들어 위 예시 같은 코드가 동작하게 될 뿐이라고 상당히 확신하고 있다. 하지만 이것은 타입 시스템의 정확성이 의존하는 논리적으로 매우 미묘한 코드 조각이므로 너무 서두르고 싶어 하지는 않는다. 거의 같은 이유로 차세대 트레이트 솔버 자체도 현재는 실험적 기능으로 표시되어 있다.
차세대 트레이트 솔버의 또 다른 흥미로운 측면은 canonicalization이다. 설계가 캐싱에 크게 의존하기 때문에, 캐시에 넣을 수 있는 타입이 많을수록 새 트레이트 솔버를 사용할 때 컴파일은 더 빨라진다. 그래서 트레이트 풀이 과정에서 마주치는 논리 obligation은 가능한 한 많은 타입 변수와 중간 결과를 제거하는 형식으로 다시 작성된다. 이것은 또 하나의 장점도 있다. 컴파일러가 특정 답에 어떻게 도달했는지를 설명하는 증명 트리를 쉽게 재구성할 수 있게 해 준다. 이런 증명 트리는 어떤 선택지들을 시도했고 왜 작동하지 않았는지를 설명함으로써 더 자세한 오류 메시지를 만드는 데 사용된다. 증명 트리는 오류 메시지를 보여 줄 필요가 있을 때에만 생성하면 되므로, 캐시에서 이를 재구성할 수 있으면 실제로 컴파일되는 코드에 대해서는 그 트리를 구성하는 오버헤드를 피할 수 있다.
차세대 트레이트 솔버는 이미 안정화된 Rust에서 일관성 검사, 즉 트레이트 구현이 서로 겹치지 않는지 확인하는 용도로는 이미 사용되고 있지만, 아직 일반적인 트레이트 풀이에는 사용되지 않는다. 컴파일러의 nightly 릴리스에서는 -Znext-solver=globally 플래그를 사용하면 모든 트레이트 관련 타입 시스템 계산에 차세대 트레이트 솔버가 사용된다. Rust 개발자들은 이미 Crater를 사용해 이 플래그가 crates.io에 공개 배포된 크레이트들에 대해 컴파일 오류를 일으키지 않는다는 점을 확인했지만, 안정화 전에 이 플래그가 누군가의 코드에서 문제를 일으키는지 알고 싶어 한다.
현재 새 트레이트 솔버와 관련된 열린 버그는 76개이고, 닫힌 버그는 78개다. 하지만 이 기능은 그 숫자가 시사하는 것보다 더 많은 진전을 이뤘다. 닫힌 버그 중 몇몇은 꽤 큰 것이고, 남은 버그는 대부분 Rust 개발자들이 해결되길 바라는 내부 컴파일러 오류나 성능 문제이기 때문이다. 새 트레이트 솔버는 이전 구현보다 더 빠르고 유지보수가 쉬우도록 의도되었지만, 그 약속이 실제로 입증될지는 아직 지켜봐야 한다. 어느 쪽이든 Rust 개발자들은 머지않아 더 복잡한 자기 참조적 트레이트 기반 인터페이스를 작성할 수 있는 선택지를 갖게 될지도 모른다.
이 기사가 마음에 드셨나요?? 지금 구독하세요특별 할인 요금으로 더 많은 이런 기사를 받아보실 수 있습니다.