Historique de la question :
Dans Rust 1.26, le langage a introduit impl Trait en position de retour (RPIT) pour permettre aux développeurs de cacher des types concrets complexes — tels que des adaptateurs d'itérateur imbriqués ou des structures générées par des closures — tout en conservant les avantages de performance de la dispatch statique grâce à la monomorphisation. Cette fonctionnalité crée un type existentiel opaque que le compilateur résout en une seule implémentation concrète lors de la compilation, empêchant les détails d'implémentation de fuiter à travers les frontières d'API. Contrairement aux génériques, qui sont choisis par l'appelant, RPIT est sélectionné par l'implémentation de la fonction, mais il nécessite toujours que le compilateur connaisse la taille exacte et la structure du type concret pour générer un code machine approprié.
Problème :
Lorsqu'une fonction tente de s'appeler récursivement tout en retournant impl Trait, le type de retour concret devrait logiquement contenir lui-même, créant une définition de type autoréférentielle de taille infinie. Rust exige strictement que toutes les valeurs de retour placées sur la pile implémentent le trait Sized, imposant ainsi au compilateur de pouvoir calculer une disposition de mémoire fixe et un alignement à la compilation. Étant donné qu'un retour impl Trait récursif implique une expansion de type illimitée où chaque cadre d'appel imbrique le précédent, le compilateur ne peut pas déterminer la taille de stockage ou les décalages de cadre de pile, ce qui entraîne une erreur de détection de cycle pendant la vérification de type.
Solution :
La résolution nécessite de rompre explicitement le cycle récursif en introduisant de l'indirection par le biais d'une allocation sur le tas, ce qui convertit la structure récursive de taille infinie en un pointeur de taille fixe. En retournant Box<dyn Trait>, la fonction retourne plutôt un pointeur large contenant un pointeur de vtable et un pointeur de données, qui sont tous deux Sized indépendamment de la profondeur de la récursion sous-jacente. Alternativement, on peut définir une énumération récursive où des variantes s'enroulent explicitement dans Box ou d'autres types de pointeurs, signalant explicitement que les données récursives résident sur le tas et que le type de retour lui-même reste une structure concrète et 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() } } // ERREUR : type opaque récursif // fn eval(n: u32) -> impl Expr { // if n == 0 { Literal(0) } // else { Sum(Box::new(eval(n-1)), Box::new(Literal(1))) } // } // SUCCÈS : Indirection explicite 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)))) } }
Lors de l'architecture d'un parseur de configuration pour un proxy réseau haute performance, j'ai dû implémenter un parseur de descente récursive pour des expressions de politique imbriquées. Le design initial spécifiait un trait Policy représentant des règles analysées, avec une fonction parse censée retourner impl Policy pour cacher la représentation interne des nœuds logiques AND/OR/NOT des consommateurs en aval.
La première approche impliquait une récursion directe : la fonction parse faisait correspondre des jetons, et pour des expressions composites comme AND(policy1, policy2), elle s'appelait récursivement pour analyser les sous-politiques et les retournait directement en tant que impl Policy. Cette stratégie offrait l'avantage des abstractions sans coût grâce à la monomorphisation et évitait la surcharge d'allocation sur le tas. Cependant, Rust a émis une erreur de compilation indiquant que l'appel récursif crée un cycle impliquant une taille de type infinie, car le type de retour concret nécessiterait de contenir des instances imbriquées de lui-même sans limite.
La seconde solution envisagée a impliqué le changement du type de retour en Box<dyn Policy>, qui allouait chaque sous-politique récursive sur le tas et retournait uniquement un pointeur de trait large. Cette approche a réussi à compiler car le type de retour était désormais un pointeur de taille fixe indépendamment de la profondeur d'imbrication. Cependant, cela a introduit la surcharge d'allocation sur le tas pour chaque nœud dans l'arbre de parse et nécessitait une dispatch dynamique via des recherches de vtable pendant l'évaluation des politiques.
Une troisième alternative a exploré la définition d'une énumération explicite PolicyNode avec des variantes pour Literal, And, Or et Not, où les variantes récursives s'enroulaient elles-mêmes dans Box<PolicyNode>, évitant la dispatch dyn mais nécessitant un ensemble fermé de types de nœuds connus à la compilation. Cette approche de dispatch statique a éliminé la surcharge de vtable et les allocations associées aux objets de trait, bien qu'elle ait sacrifié la capacité des crates en aval à étendre le langage de politique avec de nouveaux types de nœuds sans modifier la définition de l'énumération.
Nous avons choisi l'approche Box<dyn Policy> car le moteur de politique nécessitait une inscription de plugin à l'exécution où des extensions tierces pouvaient définir de nouveaux types de politique, rendant une énumération fermée impraticable pour l'extensibilité. Le résultat était un parseur récursif fonctionnel qui a échangé l'espace de pile contre la stabilité du tas et la flexibilité dynamique, bien que nous ayons ensuite optimisé les chemins chauds en transformant les modèles de parsing récursifs en boucles itératives pour réduire la pression d'allocation dans des scénarios à fort débit.
Comment le sucre async fn interagit-il avec les contraintes de récursion, étant donné qu'il retourne également un impl Future opaque ?
async fn se transforme en une machine d'état implémentant Future, où chaque point .await représente un état de suspension distinct nécessitant un stockage dans l'énumération générée. Les appels récursifs async fn déclenchent la même erreur de type infini car le futur généré contiendrait lui-même comme variante, violant la contrainte Sized. Les candidats supposent souvent que le compilateur gère la récursion asynchrone automatiquement, mais la solution nécessite de mettre manuellement le futur dans une boîte en utilisant Box::pin ou de retourner Pin<Box<dyn Future<Output = T>>>>, ce qui force l'allocation sur le tas et fixe le futur récursif à un emplacement mémoire fixe. Cela introduit la complexité supplémentaire de s'assurer que le futur retourné reste 'static ou correctement limité, et de comprendre que la récursion async fn suit les mêmes règles Sized que les retours impl Trait standard.
Pourquoi l'utilisation de impl Trait en position d'argument (APIT) ne déclenche-t-elle pas les mêmes limitations de récursion ?
L'impl Trait en position d'argument est un sucre syntaxique pour un paramètre de type générique anonyme limité par le trait spécifié. Lorsque une fonction s'appelle récursivement avec APIT, le compilateur génère une instance monomorphisée distincte pour chaque type concret passé à chaque site d'appel, ce qui signifie que la fonction récursive ne retourne pas une version opaque d'elle-même mais accepte plutôt différents types concrets à chaque niveau de pile. Les candidats confondent souvent RPIT et APIT, manquant de comprendre qu'APIT participe à la monomorphisation au graphe d'appel où le type de retour (s'il est concret par instanciation) est connu, alors que RPIT définit un type opaque unique pour le corps de la fonction qui ne peut pas se résoudre en une structure infinie autoréférentielle sans indirection.
Impl Trait peut-il être utilisé de manière récursive s'il est enveloppé dans une structure comme Wrapper<T>(T) où T: Trait ?
Une structure contenant impl Trait en tant que champ ne peut pas être nommée directement car impl Trait n'est valide qu'en tant que position de retour de fonction ou position d'argument, pas dans des définitions de type ou des champs de structure. Les candidats tentent souvent d'écrire Box<impl Trait> qui est une syntaxe invalide en dehors des contextes de retour de fonction, confondant l'alias de type opaque avec un constructeur de type concret. Ce malentendu découle du fait de traiter impl Trait comme un type de première classe qui peut être utilisé dans des positions génériques, plutôt que de comprendre qu'il s'agit d'un type existentiel généré par le compilateur disponible uniquement dans des positions de signature de fonction spécifiques. L'approche correcte nécessite soit Box<dyn Trait> pour l'effacement de type soit une définition d'énumération récursive où le type concret est explicite, garantissant que le système de types puisse calculer la contrainte Sized avant l'exécution.