Geschiedenis van de vraag:
In Rust 1.26 introduceerde de taal return-position impl Trait (RPIT) om ontwikkelaars in staat te stellen complexe concrete types te verbergen—zoals genestelde iterator-adapters of door closures gegenereerde structuren—terwijl de prestatievoordelen van statische dispatch via monomorfisatie behouden blijven. Deze functie creëert een ondoorzichtige existentiële type dat de compiler oplost naar een enkele concrete implementatie tijdens de compilatie, wat voorkomt dat implementatiedetails leks over API-grenzen. In tegenstelling tot generics, die door de aanroeper worden gekozen, wordt RPIT geselecteerd door de functie-implementatie, maar het vereist nog steeds dat de compiler de exacte grootte en indeling van het concrete type kent om de juiste machinecode te genereren.
Probleem:
Wanneer een functie probeert zichzelf recursief aan te roepen terwijl deze impl Trait retourneert, zou het concrete retourtype logisch zelfbevatting moeten bevatten, wat een zelf-referentiële type definitie van oneindige grootte creëert. Rust vereist strikt dat alle retourwaarden die op de stack worden geplaatst de Sized trait implementeren, waardoor het verplicht is dat de compiler een vaste geheugengrootte en -uitlijning kan berekenen tijdens de compilatie. Omdat een recursieve impl Trait retour impliceert dat er een onbegrensde type-expansie is waarbij elk oproep-frame het vorige nestelt, kan de compiler de opslaggrootte of stack frame-offsets niet bepalen, wat resulteert in een cyclusdetectiefout tijdens typechecking.
Oplossing:
De oplossing vereist expliciet het doorbreken van de recursieve cyclus door het introduceren van indirectie via heapallocatie, wat de onbegrensde recursieve structuur omzet in een vaste grootte pointer. Door Box<dyn Trait> te retourneren, retourneert de functie in plaats daarvan een vetpointer die een vtable-pointer en een datapointer bevat, die beide Sized zijn, ongeacht de onderliggende recursiediepte. Alternatief kan men een recursieve enum definiëren waarbij varianten zichzelf expliciet in Box of andere pointertypes wikkelen, wat expliciet aangeeft dat de recursieve gegevens op de heap verblijven en het retourtype zelf een concrete, Sized structuur blijft.
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() } } // FOUT: recursieve ondoorzichtige type // fn eval(n: u32) -> impl Expr { // if n == 0 { Literal(0) } // else { Sum(Box::new(eval(n-1)), Box::new(Literal(1))) } // } // SUCCES: Expliciete indirectie via 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)))) } }
Bij het architecten van een configuratie-parser voor een high-performance netwerkproxy, moest ik een recursieve afdaal-parser implementeren voor geneste beleidsuitdrukkingen. Het initiële ontwerp specificeerde een Policy trait die de geparste regels vertegenwoordigt, met een parse functie die bedoeld was om impl Policy te retourneren om de interne representatie van EN/OF/NIKS-logica knooppunten voor downstream-consumenten te verbergen.
De eerste benadering omvatte directe recursie: de parse functie matchede op tokens, en voor samengestelde expressies zoals AND(policy1, policy2), riep het zichzelf recursief aan om sub-beleidsregels te parseren en retourneerde deze direct als impl Policy. Deze strategie bood het voordeel van kostenloze abstracties via monomorfisatie en vermijdde overhead van heapallocatie. Echter, Rust gaf een compilatiefout aan die stelde dat de recursieve aanroep een cyclus creëert die impliceert dat er een oneindige typegrootte is, omdat het concrete retourtype geneste instanties van zichzelf zonder grenzen zou moeten bevatten.
De tweede overwogen oplossing hield in om het retourtype te veranderen naar Box<dyn Policy>, dat elke recursieve sub-beleidsregel op de heap allocaties en alleen een trait-object vetpointer retourneerde. Deze aanpak compileerde succesvol omdat het retourtype nu een vaste-grootte pointer was ongeacht de nestdiepte. Echter, het introduceerde de overhead van heapallocatie voor elk knooppunt in de parse-boom en vereiste dynamische dispatch via vtable-lookups tijdens de beleidsbeoordeling.
Een derde alternatief verkende het definiëren van een expliciete PolicyNode enum met varianten voor Literal, And, Or, en Not, waarbij de recursieve varianten zichzelf in Box<PolicyNode> wikkelden, wat dyn dispatch vermeed, maar een gesloten set van knooppunttypes vereiste die bekend was tijdens compilatie. Deze statische dispatch-aanpak elimineerde vtable-overhead en allocaties die verband hielden met trait-objecten, hoewel het de mogelijkheid opofferde voor downstream-kratten om de beleids taal uit te breiden met nieuwe knooppunttypes zonder de enum-definitie te wijzigen.
We selecteerden de Box<dyn Policy> aanpak omdat de beleidsengine runtime plugin-registratie vereiste waarbij derde partijen nieuwe beleids-types konden definiëren, waardoor een gesloten enum onpraktisch was voor uitbreidbaarheid. Het resultaat was een functionele recursieve parser die stackruimte inruilde voor heapstabiliteit en dynamische flexibiliteit, hoewel we later warme paden optimaliseerden door tail-recursieve parserpatronen om te zetten in iteratorloops om de allocatiedruk in situaties met hoge doorvoer te verminderen.
Hoe werkt de async fn suiker samen met recursiebeperkingen, gezien het ook een ondoorzichtige impl Future retourneert?
async fn desugars naar een toestandsmachine die Future implementeert, waar elk .await punt een afzonderlijke opschortingstoestand vertegenwoordigt die opslag vereist in de gegenereerde enum. Recursieve async fn aanroepen veroorzaken dezelfde oneindige type fout omdat de gegenereerde toekomst zichzelf als een variant zou bevatten, wat de Sized beperking schendt. Kandidaten gaan vaak ervan uit dat de compiler async recursie automatisch afhandelt, maar de oplossing vereist handmatig het boxen van de toekomst met behulp van Box::pin of retourneren van Pin<Box<dyn Future<Output = T>>>>, wat heapallocatie afdwingt en de recursieve toekomst op een vaste geheugenslocatie bevestigt. Dit introduceert de extra complexiteit van het waarborgen dat de geretourneerde toekomst 'static blijft of correct begrensd is, en het begrijpen dat async fn recursie dezelfde Sized regels volgt als standaard impl Trait retouren.
Waarom triggert het gebruik van impl Trait in argumentpositie (APIT) niet dezelfde recursiebeperkingen?
Argumentpositie impl Trait is syntactische suiker voor een anonieme generieke typeparameter die wordt begrensd door de gespecificeerde trait. Wanneer een functie zichzelf recursief aanroept met APIT, genereert de compiler een afzonderlijke monomorfized instantie voor elk concreet type dat op elke aanroepplaats wordt doorgegeven, wat betekent dat de recursieve functie niet een ondoorzichtige versie van zichzelf retourneert, maar eerder verschillende concrete types accepteert op elk stackniveau. Kandidaten verwarren vaak RPIT en APIT, waarbij ze missen dat APIT deelneemt aan monomorfisatie in de aanroepgrafiek waar het retourtype (indien concreet per instantie) bekend is, terwijl RPIT een enkel ondoorzichtig type definieert voor de functiebody dat niet kan worden opgelost naar een zelf-referentiële oneindige structuur zonder indirectie.
Kan impl Trait recursief worden gebruikt als het gewikkeld is in een struct zoals Wrapper<T>(T) waar T: Trait?
Een struct die impl Trait als een veld bevat kan niet direct worden genoemd omdat impl Trait alleen geldig is in functie retourposities of argumentposities, niet in type-definities of structvelden. Kandidaten proberen vaak te schrijven Box<impl Trait> wat ongeldige syntaxis is buiten functie retourcontexten, de ondoorzichtige type alias verwarrend met een concrete type constructor. Dit misverstand komt voort uit het beschouwen van impl Trait als een first-class type dat in generieke posities kan worden gebruikt, in plaats van het begrijpen als een door de compiler gegenereerd existentiëel type dat alleen beschikbaar is in specifieke functiehandtekeningposities. De juiste benadering vereist ofwel Box<dyn Trait> voor type-erasure of een recursieve enum-definitie waar het concrete type expliciet is, zodat ervoor gezorgd wordt dat het type-systeem de Sized beperking kan berekenen voordat het runtime is.