Historia pytania:
W Rust 1.26 język wprowadził impl Trait w pozycji zwracanej (RPIT), aby umożliwić programistom ukrywanie złożonych, konkretnych typów—takich jak zagnieżdżone adaptery iteratorów czy struktury generowane przez zamknięcia—przy jednoczesnym zachowaniu korzyści wydajnościowych dzięki statycznemu ropropagowywaniu przez monomorfizm. Ta funkcja tworzy nieprzezroczysty egzemplarzy type, który kompilator rozwiązuje do jednego konkretnego wdrożenia podczas kompilacji, zapobiegając wyciekom szczegółów implementacyjnych na granicach API. W przeciwieństwie do generyków, które są wybierane przez wywołującego, RPIT jest wybierany przez implementację funkcji, ale nadal wymaga, aby kompilator znał dokładny rozmiar i układ konkretnego typu, aby wygenerować odpowiedni kod maszynowy.
Problem:
Gdy funkcja próbuje wywołać samą siebie rekurencyjnie, zwracając impl Trait, konkretna typ zwrotny logicznie musiałby zawierać sam siebie, tworząc samoreferencyjną definicję typu o nieograniczonym rozmiarze. Rust ściśle wymaga, aby wszystkie wartości zwracane umieszczane na stosie implementowały trait Sized, co zobowiązuje kompilator do obliczenia stałej układu pamięci i wyrównania w czasie kompilacji. Ponieważ rekurencyjny zwrot impl Trait implikuje nieograniczone powiększenie typu, w którym każda klatka wywołania zagnieżdża poprzednią, kompilator nie jest w stanie określić rozmiaru magazynu ani przesunięć klatek stosu, co skutkuje błędem wykrywania cykli podczas sprawdzania typów.
Rozwiązanie:
Rozwiązanie wymaga jawnego złamania cyklu rekurencyjnego poprzez wprowadzenie indirekcji za pomocą alokacji na stercie, co przekształca rekurencyjny struktura o nieograniczonym rozmiarze w wskaźnik o stałym rozmiarze. Zwracając Box<dyn Trait>, funkcja zamiast tego zwraca gruby wskaźnik zawierający wskaźnik na vtable oraz wskaźnik na dane, które są Sized, niezależnie od głębokości rekurencji. Alternatywnie, można zdefiniować rekurencyjny enum, w którym warianty jawnie owijają się w Box lub inne typy wskaźników, sygnalizując w ten sposób, że rekurencyjne dane znajdują się na stercie, a typ zwracany pozostaje konkretną strukturą 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() } } // BŁĄD: rekurencyjny nieprzezroczysty typ // fn eval(n: u32) -> impl Expr { // if n == 0 { Literal(0) } // else { Sum(Box::new(eval(n-1)), Box::new(Literal(1))) } // } // SUKCES: Jawna indirekcja przez 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)))) } }
Podczas projektowania parsera konfiguracji dla wysokowydajnego proxy sieciowego, musiałem zaimplementować parser zstępujący dla zagnieżdżonych wyrażeń polityki. Początkowy projekt przewidywał Policy trait reprezentujący reguły analizowane, z funkcją parse, która miała zwracać impl Policy, aby ukryć wewnętrzną reprezentację węzłów logiki AND/OR/NOT przed konsumentami końcowymi.
Pierwsze podejście polegało na bezpośredniej rekurencji: funkcja parse dopasowywała się do tokenów, a dla złożonych wyrażeń jak AND(policy1, policy2), rekurencyjnie wywoływała samą siebie, aby analizować pod-polityki i zwracała je bezpośrednio jako impl Policy. Ta strategia oferowała korzyść zerowego kosztu abstrakcji poprzez monomorfizm i unikała kosztów związanych z alokacją na stercie. Jednak Rust zgłosił błąd kompilacji stwierdzając, że rekurencyjne wywołanie tworzy cykl implikujący nieskończony rozmiar typu, ponieważ konkretny typ zwracany musiałby zawierać zagnieżdżone instancje samego siebie bez ograniczeń.
Drugie rozważane rozwiązanie polegało na zmianie typu zwracanego na Box<dyn Policy>, co alokowało każdą rekurencyjną pod-politykę na stercie i zwracało tylko gruby wskaźnik na obiekt trait. To podejście z powodzeniem kompilowało się, ponieważ typ zwracany stał się teraz wskaźnikiem o stałym rozmiarze, niezależnie od głębokości zagnieżdżenia. Niemniej jednak wprowadziło to dodatkowy koszt alokacji na stercie dla każdego węzła w drzewie analizy i wymagało dynamicznego wywoływania przez przeszukiwanie vtable podczas oceny polityki.
Trzecią alternatywą było zdefiniowanie jawnego enum PolicyNode z wariantami dla Literal, And, Or i Not, gdzie rekurencyjne warianty owijały się w Box<PolicyNode>, unikając dynamicznego wywoływania, ale wymagając zamkniętego zestawu typów węzłów znanych w czasie kompilacji. To podejście statycznego wywoływania eliminowało narzuty związane z vtable i alokacjami związanymi z obiektami trait, chociaż poświęcało zdolność do rozszerzania języka polityki o nowe typy węzłów bez modyfikowania definicji enum.
Wybrano podejście Box<dyn Policy>, ponieważ silnik polityk wymagał rejestracji wtyczek w czasie działania, gdzie zewnętrzne rozszerzenia mogły definiować nowe typy polityk, co sprawiało, że zamknięty enum był niepraktyczny dla elastyczności. Rezultatem był funkcjonalny rekurencyjny parser, który wymieniał miejsce na stosie na stabilność sterty i elastyczność dynamiczną, chociaż później zoptymalizowaliśmy gorące ścieżki, przekształcając wzorce rekurencyjne w pętle iteracyjne, aby zmniejszyć ciśnienie alokacji w scenariuszach o wysokiej wydajności.
Jak async fn wpłynąć na ograniczenia rekurencji, biorąc pod uwagę, że również zwraca nieprzezroczysty impl Future?
async fn dekomponuje się do maszyny stanowej implementującej Future, gdzie każdy punkt .await reprezentuje odrębny stan zawieszenia wymagający przechowywania w generowanym enum. Rekurencyjne wywołania async fn wywołują ten sam błąd nieskończonego typu, ponieważ generowana przyszłość zawierałaby siebie jako wariant, naruszając ograniczenie Sized. Kandydaci często zakładają, że kompilator automatycznie obsługuje asynchroniczną rekurencję, ale rozwiązanie wymaga ręcznego opakowywania przyszłości za pomocą Box::pin lub zwracania Pin<Box<dyn Future<Output = T>>>>, co wymusza alokację na stercie i przypina rekurencyjną przyszłość do określonej lokalizacji w pamięci. To wprowadza dodatkową złożoność zapewnienia, że zwrócona przyszłość pozostanie 'static lub prawidłowo ograniczona oraz zrozumienia, że rekurencja async fn podlega identycznym zasadom Sized co standardowe zwroty impl Trait.
Dlaczego użycie impl Trait w pozycji argumentu (APIT) nie wywołuje tych samych ograniczeń rekurencyjnych?
impl Trait w pozycji argumentu jest syntaktycznym cukrem dla anonimowego parametru typu generycznego ograniczonego przez określony trait. Gdy funkcja wywołuje samą siebie rekurencyjnie z APIT, kompilator generuje odrębną instancję monomorfizowaną dla każdego konkretnego typu przekazanego w każdym miejscu wywołania, co oznacza, że rekurencyjna funkcja nie zwraca nieprzezroczystej wersji siebie, ale akceptuje różne konkretne typy na każdym poziomie stosu. Kandydaci często mylą RPIT z APIT, nie zauważając, że APIT uczestniczy w monomorfizacji w grafie wywołań, gdzie typ zwracany (jeśli konkretny dla instancji) jest znany, podczas gdy RPIT definiuje pojedynczy nieprzezroczysty typ dla ciała funkcji, który nie może rozwiązać się do samoreferencyjnej nieskończonej struktury bez indirekcji.
Czy impl Trait może być używane rekurencyjnie, gdy jest opakowane w strukturę taką jak Wrapper<T>(T), gdzie T: Trait?
Struktura zawierająca impl Trait jako pole nie może być nazwana bezpośrednio, ponieważ impl Trait jest ważne tylko w pozycjach zwracanych funkcji lub pozycji argumentów, a nie w definicjach typów lub polach struktur. Kandydaci często próbują napisać Box<impl Trait>, co jest nieprawidłową składnią poza kontekstem zwracania z funkcji, myląc nieprzezroczysty typ alias z konstruktorem konkretnego typu. To nieporozumienie wynika z traktowania impl Trait jako typu pierwszej klasy, który może być używany w pozycjach generycznych, a nie rozumienia go jako generowanego przez kompilator egzystycznego typu dostępnego tylko w określonych pozycjach sygnatury funkcji. Odpowiednie podejście wymaga albo Box<dyn Trait> do kasowania typów, albo definicji rekurencyjnego enum, gdzie konkretny typ jest jawny, zapewniając, że system typów może obliczyć ograniczenie Sized przed czasem wykonywania.