Geschichte der Frage:
In Rust 1.26 führte die Sprache impl Trait in der Rückgabe-Position (RPIT) ein, um Entwicklern zu ermöglichen, komplexe konkrete Typen—wie verschachtelte Iterator-Adapter oder durch Closures erzeugte Strukturen—zu verbergen, während die Leistungsmerkmale statischer Dispatch durch Monomorphisierung erhalten bleiben. Dieses Feature erstellt einen opaken existenziellen Typ, den der Compiler während der Kompilierung in eine konkrete Implementierung auflöst, wodurch die Implementierungsdetails nicht über API-Grenzen hinausdringen. Im Gegensatz zu Generika, die vom Aufrufer ausgewählt werden, wird RPIT von der Funktionsimplementierung ausgewählt, jedoch erfordert es dennoch, dass der Compiler die genaue Größe und das Layout des konkreten Typs kennt, um den entsprechenden Maschinencode zu generieren.
Problem:
Wenn eine Funktion versucht, sich selbst rekursiv aufzurufen, während sie impl Trait zurückgibt, müsste der konkrete Rückgabetyp logischerweise sich selbst enthalten, was eine selbstreferenzielle Typdefinition unendlicher Größe erzeugen würde. Rust verlangt streng, dass alle Rückgabewerte, die auf dem Stack platziert werden, das Sized-Trait implementieren, was vorschreibt, dass der Compiler eine feste Speicheranordnung und -ausrichtung zur Kompilierungszeit berechnen kann. Da eine rekursive impl Trait Rückgabe eine unbegrenzte Typexpansion impliziert, bei der jeder Aufrufframe den vorherigen schachtelt, kann der Compiler die Speichergröße oder die Stack-Offset für die Typüberprüfung nicht ermitteln, was zu einem Fehler bei der Zyklusüberprüfung führt.
Lösung:
Die Lösung erfordert, den rekursiven Zyklus explizit zu unterbrechen, indem Indirektion durch Heap-Allokation eingeführt wird, was die unendliche rekursive Struktur in einen festspeichers Makipointer umwandelt. Indem die Funktion Box<dyn Trait> zurückgibt, gibt die Funktion stattdessen einen fetten Zeiger zurück, der einen vtable-Zeiger und einen Datenzeiger enthält, die beide Sized sind, unabhängig von der zugrunde liegenden Rekursionstiefe. Alternativ kann man ein rekursives enum definieren, bei dem die Varianten sich explizit in Box oder andere Zeigertypen einwickeln, was dem Compiler signalisiert, dass die rekursiven Daten im Heap wohnen und der Rückgabetyp selbst eine konkrete, Sized Struktur bleibt.
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() } } // FEHLER: rekursiver opaker Typ // fn eval(n: u32) -> impl Expr { // if n == 0 { Literal(0) } // else { Sum(Box::new(eval(n-1)), Box::new(Literal(1))) } // } // ERFOLG: Explizite Indirektion 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)))) } }
Bei der Architektur eines Konfigurationsparsers für einen Hochleistungsnetzwerkproxy musste ich einen rekursiven Abstiegsparser für verschachtelte Richtlinienausdrücke implementieren. Das ursprüngliche Design spezifizierte ein Policy-Trait, das die geparsten Regeln darstellt, wobei eine parse-Funktion vorgesehen war, die impl Policy zurückgibt, um die interne Darstellung von UND/ODER/NICHT-Logik-Knoten vor nachfolgenden Konsumenten zu verbergen.
Der erste Ansatz umfasste direkte Rekursion: Die parse-Funktion passte auf Tokens ab, und bei zusammengesetzten Ausdrücken wie AND(policy1, policy2) rief sie sich rekursiv auf, um Unterrichtsrichtlinien zu parsen und gab sie direkt als impl Policy zurück. Diese Strategie bot den Vorteil der Nullkostenabstraktionen durch Monomorphisierung und vermied Overhead durch Heap-Allokation. Allerdings gab Rust einen Kompilierungsfehler aus, der besagte, dass der rekursive Aufruf einen Zyklus erschaffe, der eine unendliche Typgröße impliziert, da der konkrete Rückgabetyp erforderlich wäre, um geschachtelte Instanzen von sich selbst ohne Grenze zu enthalten.
Die zweite in Betracht gezogene Lösung bestand darin, den Rückgabetyp auf Box<dyn Policy> zu ändern, wodurch jede rekursive Unterrichtsrichtlinie im Heap allokiert und nur ein Trait-Objekt fetter Zeiger zurückgegeben wurde. Dieser Ansatz wurde erfolgreich kompiliert, da der Rückgabetyp nun ein fester Zeiger war, unabhängig von der Verschachtelungstiefe. Allerdings wurde dadurch der Overhead der Heap-Allokation für jeden Knoten im Parse-Baum eingeführt und erforderte dynamischen Dispatch via vtable-Lookups während der Richtlinienauswertung.
Eine dritte Alternative bestand darin, ein explizites PolicyNode-Enum mit Varianten für Literal, And, Or und Not zu definieren, bei denen die rekursiven Varianten sich in Box<PolicyNode> einwickelten, wodurch dyn Dispatch vermieden wurde, jedoch eine abgeschlossene Menge von Knotentypen nötig war, die zur Kompilierungszeit bekannt waren. Dieser Ansatz des statischen Dispatchs beseitigte den vtable-Overhead und die mit Trait-Objekten verbundenen Allokationen, obwohl er die Fähigkeit opferte, dass nachgelagerte Crates die Policysprache mit neuen Knotentypen erweitern konnten, ohne die Enum-Definition zu ändern.
Wir wählten den Ansatz Box<dyn Policy>, da die Policy-Engine eine Registrierung von Plugins zur Laufzeit erforderte, bei der Drittanbietererweiterungen neue Policy-Typen definieren konnten, wodurch ein geschlossenes Enum für die Erweiterbarkeit unpraktisch wäre. Das Ergebnis war ein funktionierender rekursiver Parser, der den Stackplatz gegen Heap-Stabilität und dynamische Flexibilität eintauschte, obwohl wir später heiße Pfade optimierten, indem wir tail-rekursive Parsing-Muster in iterative Schleifen umwandelten, um den Allokationsdruck in Hochdurchsatzszenarien zu verringern.
Wie interagiert der async fn-Zucker mit Rekursionsbeschränkungen, da er auch ein opakes impl Future zurückgibt?
async fn wird in eine Zustandsmaschine umgewandelt, die Future implementiert, wobei jeder .await-Punkt einen bestimmten Suspendierungszustand darstellt, der Speicher im generierten Enum erfordert. Rekursive async fn-Aufrufe lösen denselben Fehler der unendlichen Typgröße aus, da die generierte Zukunft sich selbst als Variante enthalten würde, was das Sized-Kriterium verletzt. Kandidaten nehmen häufig an, dass der Compiler die Async-Rekursion automatisch behandelt, aber die Lösung erfordert, die Zukunft manuell mit Box::pin zu boxen oder Pin<Box<dyn Future<Output = T>>>> zurückzugeben, was eine Heap-Allokation erzwingt und die rekursive Zukunft an einem festen Speicherort fixiert. Dies bringt die zusätzliche Komplexität mit sich, sicherzustellen, dass die zurückgegebene Zukunft 'static bleibt oder ordnungsgemäß gebunden ist, und zu verstehen, dass async fn-Rekursion denselben Sized-Regeln folgt wie Standard-impl Trait-Rückgaben.
Warum löst die Verwendung von impl Trait in der Argumentposition (APIT) nicht dieselben Rekursionseinschränkungen aus?
impl Trait in der Argumentposition ist syntaktischer Zucker für einen anonymen generischen Typparameter, der durch das angegebene Trait begrenzt wird. Wenn eine Funktion sich rekursiv mit APIT aufruft, generiert der Compiler eine unterschiedliche monomorphisierte Instanz für jeden konkreten Typ, der an jedem Aufrufort übergeben wird, was bedeutet, dass die rekursive Funktion nicht eine opake Version von sich selbst zurückgibt, sondern in jedem Stack-Level unterschiedliche konkrete Typen akzeptiert. Kandidaten verwechseln häufig RPIT und APIT, und übersehen, dass APIT an der Aufrufgraf-Monomorphisierung teilnimmt, wo der Rückgabetyp (wenn konkret pro Instanziierung) bekannt ist, während RPIT einen einzelnen opaken Typ für den Funktionskörper definiert, der sich nicht ohne Indirektion in eine selbstreferenzielle unendliche Struktur auflösen kann.
Kann impl Trait rekursiv verwendet werden, wenn es in einer Struktur wie Wrapper<T>(T) eingebettet ist, wobei T: Trait?
Eine Struktur, die impl Trait als Feld enthält, kann nicht direkt benannt werden, da impl Trait nur in Funktionsrückgabepositionen oder Argumentpositionen gültig ist, nicht in Typdefinitionen oder Strukturfeldern. Kandidaten versuchen oft, Box<impl Trait> zu schreiben, was eine ungültige Syntax außerhalb von Funktionsrückgabekontexten ist und die opake Typaliasierung mit einem konkreten Typschöpfer verwechselt. Dieses Missverständnis ergibt sich aus der Annahme, dass impl Trait als erstklassiger Typ in generischen Positionen verwendet werden kann, anstatt zu verstehen, dass es sich um einen vom Compiler generierten existenziellen Typ handelt, der nur in bestimmten Funktionssignaturpositionen verfügbar ist. Der korrekte Ansatz erfordert entweder Box<dyn Trait> für die Typausweichung oder eine rekursive Enum-Definition, bei der der konkrete Typ explizit ist, um sicherzustellen, dass das Typsystem das Sized-Kriterium vor der Laufzeit berechnen kann.