질문에 대한 역사:
Rust 1.26에서 언어는 복잡한 구체적 타입(예: 중첩된 반복자 어댑터나 클로저로 생성된 구조체)을 숨길 수 있도록 반환 위치 impl Trait(RPIT)를 도입하여 정적 디스패치의 성능 이점을 유지하도록 했습니다. 이 기능은 컴파일 시 컴파일러가 단일 구체적 구현으로 해결하는 불투명한 존재 타입을 생성하여 구현 세부 정보가 API 경계를 넘어 누출되는 것을 방지합니다. 일반화와 달리 호출자가 선택하는 것이 아니라 RPIT는 함수 구현에 의해 선택되지만, 정확한 크기 및 레이아웃을 아는 것이 여전히 필요합니다.
문제:
함수가 impl Trait를 반환하면서 자기 자신을 재귀 호출하려고 하면, 구체적인 반환 타입은 논리적으로 자신을 포함해야 하므로 무한 크기를 가진 자기 참조 타입 정의를 생성해야 합니다. Rust는 스택에 놓이는 모든 반환 값이 Sized 특성을 구현해야 한다고 엄격히 요구하므로, 컴파일러가 고정된 메모리 레이아웃과 정렬을 컴파일 시간에 계산할 수 있어야 합니다. 재귀 impl Trait 반환은 각 호출 프레임이 이전 것을 중첩하는 무제한 타입 확장을 의미하므로, 컴파일러는 저장 크기나 스택 프레임 오프셋을 결정할 수 없으며, 그 결과 타입 검사 중 순환 감지 오류가 발생합니다.
해결책:
해결책은 메모리 할당을 통한 간접성을 도입하여 재귀적 순환을 명시적으로 깨는 것입니다. Box<dyn Trait>를 반환하면, 함수는 이제 호출 깊이에 관계없이 모두 Sized인 vtable 포인터와 데이터 포인터를 포함하는 fat 포인터를 반환합니다. 또는 recursive enum을 정의하여 각 변형이 Box 또는 다른 포인터 타입으로 자신을 감싸게 하여 재귀 데이터가 힙에 존재한다는 신호를 명시하고 반환 타입 자체가 구체적인 Sized 구조로 남도록 할 수 있습니다.
trait Expr { fn val(&self) -> i32; } struct Literal(i32); impl Expr for Literal { fn val(&self) -> i32 { self.0 } } struct Sum(Box<dyn Expr>, Box<dyn Expr>); impl Expr for Sum { fn val(&self) -> i32 { self.0.val() + self.1.val() } } // 오류: 재귀 불투명 타입 // fn eval(n: u32) -> impl Expr { // if n == 0 { Literal(0) } // else { Sum(Box::new(eval(n-1)), Box::new(Literal(1))) } // } // 성공: Box<dyn Trait>를 통한 명시적 간접성 fn eval(n: u32) -> Box<dyn Expr> { if n == 0 { Box::new(Literal(0)) } else { Box::new(Sum(eval(n-1), Box::new(Literal(1)))) } }
고성능 네트워크 프록시를 위한 구성 파서를 설계하는 동안, 중첩 정책 표현을 위한 재귀 하강 파서를 구현해야 했습니다. 초기 설계엔 파싱된 규칙을 나타내는 Policy 트레이트가 명시되었고, 내부 표현을 하위 소비자로부터 숨기기 위해 impl Policy를 반환하도록 parse 함수를 의도했습니다.
첫 번째 접근법은 직접 재귀가 포함되어 있었습니다: parse 함수는 토큰을 매칭하였고, AND(policy1, policy2)와 같은 복합 표현에 대해 자신을 재귀적으로 호출하여 하위 정책을 파싱하고 이를 impl Policy로 직접 반환했습니다. 이 전략은 monomorphization을 통한 제로 비용 추상화를 제공하고 힙 할당 오버헤드를 피할 수 있었습니다. 그러나 Rust는 재귀 호출이 무한한 타입 크기를 암시하는 순환을 생성한다는 컴파일 오류를 발생시켰습니다.
두 번째 고려된 해결책은 반환 타입을 **Box<dyn Policy>**로 변경하는 것이었습니다. 이 경우 각 재귀 하위 정책이 힙에 할당되고 단지 트레이트 객체 fat 포인터만 반환됩니다. 이 방법은 이제 반환 타입이 중첩 깊이에 관계없이 고정 크기 포인터이므로 성공적으로 컴파일되었습니다. 그러나 이 접근법은 parse 트리의 각 노드에 대한 힙 할당 오버헤드를 도입하였고 정책 평가 중 동적 디스패치를 위해 vtable 조회가 필요했습니다.
세 번째 대안은 Literal, And, Or, Not에 대한 변형이 포함된 명시적 PolicyNode 열거형을 정의하는 것이었습니다. 여기서 재귀 변형은 **Box<PolicyNode>**에 자신을 감쌉니다. 이 접근법은 dyn 디스패치를 피하지만 컴파일 시간에 알려진 노드 타입 집합을 필요로 합니다. 이 정적 디스패치 접근법은 트레이트 객체와 관련된 vtable 오버헤드와 할당을 제거했지만 열거형 정의를 수정하지 않고는 하위 크레이트가 새로운 노드 타입으로 정책 언어를 확장할 수 있는 기능을 희생하게 됩니다.
우리는 Box<dyn Policy> 접근법을 선택했습니다. 정책 엔진은 런타임 플러그인 등록이 필요하고, 제3자가 새로운 정책 타입을 정의할 수 있으므로, 닫힌 열거형은 확장성에 적합하지 않았습니다. 결과적으로 우리는 스택 공간을 힙 안정성 및 동적 유연성으로 교환하는 기능적인 재귀 파서를 얻었고, 이후에는 고처리량 시나리오에서 할당 압력을 줄이기 위해 꼬리 재귀 파싱 패턴을 반복 루프로 변환하여 핫 경로를 최적화했습니다.
async fn 설탕이 재귀 제약 조건과 어떻게 상호작용하는가, 왜냐하면 이것 또한 불투명한 impl Future를 반환하기 때문이다.
async fn은 **Future**를 구현하는 상태 기계로 변환되며, 각 .await 지점은 생성된 열거형에서 저장이 필요한 별도의 일시 중단 상태를 나타냅니다. 재귀 async fn 호출은 생성된 미래가 변형으로 자신을 포함하게 되어 동일한 무한 타입 오류를 발생시킵니다. 후보자들은 종종 컴파일러가 async 재귀를 자동으로 처리한다고 가정하지만, 해결책은 **Box::pin**을 사용하여 미래를 수동으로 박스에 넣거나 **Pin<Box<dyn Future<Output = T>>>**를 반환하여 힙 할당을 강제하고 재귀 미래를 고정된 메모리 위치에 핀하는 것을 요구합니다. 이로 인해 반환된 미래가 'static 또는 적절하게 한정된 상태를 유지해야 하는 복잡성이 추가되며, async fn 재귀는 표준 impl Trait 반환과 동일한 Sized 규칙을 따르는 것을 이해해야 합니다.
인수 위치에서 impl Trait를 사용하는 것이 왜 동일한 재귀 제한을 유발하지 않는가?
인수 위치 impl Trait는 명시된 트레이트에 의해 제한된 익명 제네릭 타입 매개변수에 대한 문법적 설탕입니다. 함수가 APIT로 재귀적으로 자신을 호출할 때, 컴파일러는 각 호출 지점에서 전달된 각 구체적 타입에 대해 별도의 monomorphized 인스턴스를 생성하므로, 재귀 함수는 자신을 불투명하게 반환하지 않고 대신 각 스택 레벨에서 서로 다른 구체적 타입을 수용하는 것입니다. 후보자들은 종종 RPIT와 APIT을 혼동하며, APIT은 반환 타입이 각 인스턴스당 구체적일 수 있으므로 호출 그래프에 참여하는 반면, RPIT는 간접성이 없으면 자기 참조 무한 구조로 해결될 수 없는 함수 본체에 대한 단일 불투명 타입을 정의한다는 것을 놓칩니다.
Wrapper<T>(T)와 같은 구조체에 impl Trait를 래핑하면 재귀적으로 사용할 수 있는가, 여기서 T: Trait이다.
구조체에 impl Trait를 필드로 포함시키는 것은 직접적으로 이름을 지을 수 없기 때문에 **impl Trait**은 함수 반환 위치 또는 인수 위치에서만 유효합니다. 후보자들은 종종 함수 반환 컨텍스트 외부에서 유효하지 않은 문법인 Box<impl Trait>를 작성하려고 시도하여 불투명 타입 별명을 일반 타입 생성자와 혼동합니다. 이 오해는 impl Trait를 제네릭 위치에 사용할 수 있는 1급 타입으로 처리하는 데서 비롯되며, 특정 함수 시그니처 위치에서만 유효한 컴파일러 생성 존재 타입임을 이해하지 못하는 데에서 비롯됩니다. 올바른 접근 방식은 타입 지우기를 위한 **Box<dyn Trait>**를 사용하거나 재귀 열거형 정의에서 구체적인 타입을 명시하여 타입 시스템이 런타임 이전에 Sized 제약을 계산할 수 있도록 해야 합니다.