Historia de la pregunta:
En Rust 1.26, el lenguaje introdujo impl Trait en la posición de retorno (RPIT) para permitir a los desarrolladores ocultar tipos concretos complejos—como adaptadores de iteradores anidados o estructuras generadas por cierres—mientras conservan los beneficios de rendimiento del despachado estático a través de la monomorfización. Esta característica crea un tipo existencial opaco que el compilador resuelve a una única implementación concreta durante la compilación, evitando que los detalles de implementación se filtren a través de las fronteras de la API. A diferencia de los genéricos, que son elegidos por el llamador, RPIT es seleccionado por la implementación de la función, pero aún requiere que el compilador conozca el tamaño y el diseño exactos del tipo concreto para generar el código máquina adecuado.
Problema:
Cuando una función intenta llamarse a sí misma recursivamente mientras devuelve impl Trait, el tipo de retorno concreto lógicamente necesitaría contenerse a sí mismo, creando una definición de tipo auto-referencial de tamaño infinito. Rust requiere estrictamente que todos los valores de retorno colocados en la pila implementen el rasgo Sized, exigiendo que el compilador pueda calcular un diseño y alineación de memoria fijos en tiempo de compilación. Debido a que un retorno recursivo de impl Trait implica una expansión de tipo no acotada donde cada marco de llamada anida el anterior, el compilador no puede determinar el tamaño de almacenamiento o los desfaces de los marcos de pila, resultando en un error de detección de ciclos durante la comprobación de tipos.
Solución:
La resolución requiere romper explícitamente el ciclo recursivo introduciendo indirección a través de la asignación dinámica, lo que convierte la estructura recursiva de tamaño infinito en un puntero de tamaño fijo. Al devolver Box<dyn Trait>, la función en su lugar devuelve un puntero grueso que contiene un puntero a vtable y un puntero de datos, ambos de los cuales son Sized independientemente de la profundidad de la recursión subyacente. Alternativamente, uno puede definir un enum recursivo donde los variantes se envuelven explícitamente a sí mismos en Box u otros tipos de punteros, señalando explícitamente que los datos recursivos residen en la pila y que el tipo de retorno en sí mismo sigue siendo una estructura concreta, 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() } } // ERROR: tipo opaco recursivo // fn eval(n: u32) -> impl Expr { // if n == 0 { Literal(0) } // else { Sum(Box::new(eval(n-1)), Box::new(Literal(1))) } // } // ÉXITO: Indirección explícita a través de 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)))) } }
Mientras arquitectaba un analizador de configuración para un proxy de red de alto rendimiento, necesitaba implementar un analizador de descenso recursivo para expresiones de políticas anidadas. El diseño inicial especificaba un rasgo Policy que representaba reglas analizadas, con una función parse destinada a devolver impl Policy para ocultar la representación interna de los nodos de lógica AND/OR/NOT de los consumidores posteriores.
El primer enfoque involucró la recursión directa: la función parse coincidía con los tokens, y para expresiones compuestas como AND(policy1, policy2), se llamaba recursivamente a sí misma para analizar sub-políticas y las devolvía directamente como impl Policy. Esta estrategia ofreció el beneficio de abstracciones de costo cero a través de la monomorfización y evitó la sobrecarga de asignación dinámica. Sin embargo, Rust emitió un error de compilación indicando que la llamada recursiva crea un ciclo que implica un tamaño de tipo infinito, porque el tipo de retorno concreto necesitaría contener instancias anidadas de sí mismo sin límite.
La segunda solución considerada involucró cambiar el tipo de retorno a Box<dyn Policy>, lo que asignaba cada sub-política recursiva en el heap y devolvía solo un puntero grueso del objeto trait. Este enfoque se compiló con éxito porque el tipo de retorno era ahora un puntero de tamaño fijo independientemente de la profundidad de anidamiento. Sin embargo, introdujo la sobrecarga de la asignación dinámica para cada nodo en el árbol de análisis y requirió despachado dinámico a través de búsquedas en la vtable durante la evaluación de políticas.
Una tercera alternativa exploró definir un enum explícito PolicyNode con variantes para Literal, And, Or, y Not, donde las variantes recursivas se envolvían a sí mismas en Box<PolicyNode>, evitando el despachado dyn pero requiriendo un conjunto cerrado de tipos de nodo conocidos en tiempo de compilación. Este enfoque de despachado estático eliminó la sobrecarga de la vtable y las asignaciones asociadas con objetos trait, aunque sacrificó la capacidad de que los crates posteriores extendieran el lenguaje de políticas con nuevos tipos de nodo sin modificar la definición del enum.
Elegimos el enfoque Box<dyn Policy> porque el motor de políticas requería registro de plugins en tiempo de ejecución donde extensiones de terceros podían definir nuevos tipos de políticas, lo que hacía impráctico un enum cerrado para extensibilidad. El resultado fue un analizador recursivo funcional que intercambió espacio de pila por estabilidad en el heap y flexibilidad dinámica, aunque luego optimizamos rutas críticas transformando patrones de análisis recursivos en la cola en bucles iterativos para reducir la presión de asignación en escenarios de alto rendimiento.
¿Cómo interactúa el azúcar de async fn con las restricciones de recursión, dado que también devuelve un opaco impl Future?
async fn se descompone en una máquina de estados que implementa Future, donde cada punto de .await representa un estado de suspensión distinto que requiere almacenamiento en el enum generado. Las llamadas recursivas a async fn desencadenan el mismo error de tipo infinito porque el futuro generado contendría a sí mismo como variante, violando la restricción Sized. Los candidatos a menudo asumen que el compilador maneja la recursión async automáticamente, pero la solución requiere enmarcar manualmente el futuro utilizando Box::pin o devolviendo Pin<Box<dyn Future<Output = T>>>>, que obliga a la asignación dinámica y fija el futuro recursivo a una ubicación de memoria fija. Esto introduce la complejidad adicional de asegurar que el futuro devuelto permanezca 'static o adecuadamente limitado, y de entender que la recursión de async fn sigue las mismas reglas Sized que los retornos estándar de impl Trait.
¿Por qué el uso de impl Trait en la posición de argumento (APIT) no desencadena las mismas limitaciones de recursión?
impl Trait en posición de argumento es azúcar sintáctico para un parámetro de tipo genérico anónimo limitado por el rasgo especificado. Cuando una función se llama a sí misma recursivamente con APIT, el compilador genera una instancia monomorfizada distinta para cada tipo concreto pasado en cada punto de llamada, lo que significa que la función recursiva no está devolviendo una versión opaca de sí misma sino que acepta diferentes tipos concretos en cada nivel de la pila. Los candidatos a menudo confunden RPIT y APIT, perdiendo de vista que APIT participa en la monomorfización en el gráfico de llamadas donde el tipo de retorno (si es concreto por instancia) es conocido, mientras que RPIT define un único tipo opaco para el cuerpo de la función que no puede resolverse en una estructura infinita auto-referencial sin indirección.
¿Se puede usar impl Trait recursivamente si está envuelto en una estructura como Wrapper<T>(T) donde T: Trait?
Una estructura que contiene impl Trait como campo no puede nombrarse directamente porque impl Trait solo es válido en posiciones de retorno de función o posiciones de argumentos, no en definiciones de tipo o campos de estructura. Los candidatos a menudo intentan escribir Box<impl Trait> que es una sintaxis inválida fuera de los contextos de retorno de función, confundiendo el alias de tipo opaco con un constructor de tipo concreto. Este malentendido proviene de tratar impl Trait como un tipo de primera clase que se puede usar en posiciones genéricas, en lugar de entenderlo como un tipo existencial generado por el compilador disponible solo en posiciones de firma de función específicas. El enfoque correcto requiere ya sea Box<dyn Trait> para la eliminación de tipos o una definición de enum recursiva donde el tipo concreto sea explícito, asegurando que el sistema de tipos pueda calcular la restricción Sized antes de tiempo de ejecución.