FerrousPath

Nivel 5 · Investigación· Lección 4 de 9 · 45 min

Resolución de traits y coherencia

Los traits como programación lógica — cláusulas de Horn, búsqueda de demostraciones, coinducción, normalización, el resolutor de nueva generación y los agujeros de corrección conocidos.

Cuando escribes x.clone() o T: Iterator<Item = u32>, el compilador tiene que demostrar algo. El componente que lo hace —el resolutor de traits (trait solver)— es un demostrador de teoremas para una lógica restringida, y su diseño determina qué código genérico puede expresar Rust, qué mensajes de error ves y dónde se esconden los errores de corrección.

Los traits son predicados; los impls son reglas

trait Describe { fn describe(&self) -> String; }

impl Describe for u32 {
    fn describe(&self) -> String { format!("u32 {self}") }
}
impl<T: Describe> Describe for Vec<T> {
    fn describe(&self) -> String {
        format!("[{}]", self.iter().map(|x| x.describe()).collect::<Vec<_>>().join(", "))
    }
}
impl<A: Describe, B: Describe> Describe for (A, B) {
    fn describe(&self) -> String { format!("({} & {})", self.0.describe(), self.1.describe()) }
}

fn main() {
    let value = vec![(1u32, vec![2u32, 3]), (4, vec![])];
    println!("{}", value.describe());
}

Leído como lógica:

Describe(u32).
Describe(Vec<T>)  :- Describe(T).
Describe((A, B))  :- Describe(A), Describe(B).

Para comprobar los tipos de value.describe(), el resolutor debe demostrar el objetivo Describe(Vec<(u32, Vec<u32>)>). Encuentra la regla cuya cabeza unifica y demuestra recursivamente el cuerpo: una búsqueda de demostración en profundidad, exactamente como en Prolog. El árbol de demostración que construye es también la receta para la generación de código: qué impl hay que llamar en cada nodo.

Por eso el sistema de traits puede calcular (los números de Peano del nivel 4), por eso tiene un límite de recursión y por eso los mensajes de error tienen la forma «the trait bound … is not satisfied, required by a bound in …»: eso es una demostración fallida, impresa.

Las piezas de la lógica

Entre los objetivos que trata el resolutor están:

  • T: Trait<Args>: un predicado de trait.
  • <T as Trait>::Assoc == U: un predicado de proyección.
  • T: 'a, 'a: 'b: predicados de supervivencia (se recogen como restricciones y los resuelve la inferencia de regiones del borrow checker).
  • WF(T): el tipo está bien formado.

Las hipótesis vienen del entorno: las cláusulas where del elemento que se está comprobando (ParamEnv). Dentro de fn f<T: Clone>(), T: Clone simplemente se da por supuesto.

Variables de inferencia. Los objetivos contienen incógnitas: Vec<?X>: IntoIterator<Item = ?Y>. La resolución se intercala con la inferencia de tipos: un objetivo puede ser ambiguo ahora y reintentarse cuando se sepa más. Por eso añadir un impl puede romper la inferencia de tipos en el código que depende de ti: un objetivo que tenía un solo candidato, y que por tanto guiaba la inferencia, ahora tiene dos.

Candidatos. Para un objetivo de trait, el resolutor reúne candidatos a partir de los impls, las cláusulas where, las reglas incorporadas (Sized, Copy para las tuplas, las clausuras que implementan Fn) y las restricciones de objetos y de alias; después elige uno o informa de la ambigüedad. Los candidatos de las cláusulas where se prefieren a los impls: una regla con consecuencias visibles cuando se aplican los dos.

Tipos asociados y normalización

Los tipos asociados hacen la lógica mucho más difícil. <T as Iterator>::Item es una aplicación de función a nivel de tipos, y el resolutor debe ser capaz de normalizarla —reescribirla como un tipo concreto cuando se conoce el impl— y de tratarla como un alias rígido y opaco cuando no se conoce (dentro de una función genérica, T::Item es simplemente T::Item).

fn sum_all<I>(iter: I) -> I::Item
where
    I: Iterator,
    I::Item: std::ops::Add<Output = I::Item> + Default,
{
    iter.fold(I::Item::default(), |a, b| a + b)
}

fn main() {
    // Aquí el resolutor normaliza <std::vec::IntoIter<f64> as Iterator>::Item a f64.
    println!("{}", sum_all(vec![1.5, 2.5].into_iter()));
}

La igualdad de tipos es por tanto módulo normalización, y decidirla exige resolver objetivos de trait, lo que exige comparar tipos. Hacer bien esa recursión mutua —sobre todo de forma perezosa, bajo ligaduras y con tipos de rango superior— ha sido el origen de muchos errores del compilador y es una motivación central para reescribir el resolutor.

Inducción, coinducción y ciclos

¿Qué debe hacer el resolutor cuando demostrar un objetivo exige demostrar el mismo objetivo?

struct List<T> {
    value: T,
    next: Option<Box<List<T>>>,
}

fn assert_send<T: Send>() {}

fn main() {
    // Send(List<u8>) necesita Send(Option<Box<List<u8>>>), que necesita otra vez Send(List<u8>).
    assert_send::<List<u8>>();
    println!("List<u8> is Send");
}
  • Para los traits normales la lógica es inductiva: una demostración debe ser finita, y un ciclo es un fallo (o un desbordamiento).
  • Para los auto traits (Send, Sync, Unpin) y para la buena formación, la lógica es coinductiva: un ciclo cuenta como éxito. La lectura que se busca es «no hay ningún campo que no sea Send»: un punto fijo mayor, no menor.

Mezclar objetivos inductivos y coinductivos en un mismo ciclo, con caché, es sutil; un tratamiento incorrecto permitiría al resolutor «demostrar» cosas falsas. El resolutor nuevo tiene un algoritmo de punto fijo diseñado cuidadosamente justo para esto.

Objetivos de rango superior

for<'a> F: Fn(&'a str) -> &'a str cuantifica sobre todos los lifetimes. Para demostrar un objetivo for<'a>, el resolutor instancia 'a con un marcador de posición (placeholder) nuevo —una región de la que no se sabe nada— en un universo nuevo, y demuestra el cuerpo. Para usar una hipótesis de rango superior, la instancia con una variable de inferencia. Los universos impiden que un marcador de posición se filtre a una variable de inferencia creada antes de que él existiera. Es maquinaria estándar de la unificación de orden superior; su implementación incompleta es lo que hay detrás del error «implementation is not general enough».

Coherencia

La coherencia garantiza que una referencia a un trait tiene como máximo un impl aplicable en todo el grafo de crates. Es lo que hace correcto que un HashMap<K, V> construido en un crate se use en otro: los dos tienen que coincidir en el Hash de K. Tiene dos partes:

Comprobación de solapamiento. Dos impls se solapan si sus cabeceras unifican y las cláusulas where unificadas podrían cumplirse. Lo crucial es que la comprobación debe ser conservadora respecto al futuro: un crate del que dependes puede añadir impls más adelante. Así que impl<T: Display> Foo for T e impl Foo for Vec<u8> se consideran solapados, porque Vec<u8> podría implementar Display algún día. Las excepciones son los tipos #[fundamental] y los casos en los que la regla del huérfano demuestra que un impl así nunca podrá escribirse en otro sitio.

Comprobación del huérfano. impl<P1..Pn> Trait<T1..Tn> for T0 solo se permite si el trait es local, o si algún Ti es un tipo local y no aparece ningún parámetro de tipo descubierto en T0..Ti-1. Esto garantiza que dos crates que no se conocen entre sí no pueden escribir los dos el mismo impl.

Juntas dan una garantía modular: añadir una dependencia nunca puede producir impls en conflicto. El coste es la expresividad —no puedes implementar un trait ajeno para un tipo ajeno— y una restricción sobre la evolución de las bibliotecas: un nuevo impl genérico es un cambio incompatible.

El razonamiento negativo («T no implementa Trait») es lo que la coherencia necesita en el fondo y lo que a la lógica le falta en gran medida. Los impls negativos (impl !Send for X) existen para los auto traits; las restricciones negativas generales siguen siendo inestables porque una restricción T: !Trait convierte añadir un impl en un cambio incompatible.

La especialización y su problema de corrección

La especialización permitiría impls solapados cuando uno es más específico:

// Solo en nightly: #![feature(specialization)] — e incorrecto tal como está escrito.
impl<T> Describe for T { default fn describe(&self) -> String { "something".into() } }
impl Describe for &'static str { fn describe(&self) -> String { "a static string".into() } }

El segundo impl se aplica solo cuando el lifetime es 'static. Pero los lifetimes se borran antes de la monomorfización: el generador de código ve &str y no puede saber qué impl eligió el comprobador de tipos. Con los tipos asociados, las dos fases pueden discrepar sobre un tipo, lo que rompe la seguridad de memoria. La versión restringida min_specialization que se usa dentro de la biblioteca estándar prohíbe especializar sobre lifetimes y sobre la mayoría de los traits (solo admite impls «siempre aplicables»). Un diseño general y correcto es un problema de investigación abierto.

Los resolutores: el antiguo, Chalk y el de nueva generación

  • El resolutor original creció de forma orgánica: maquinaria separada para la selección, el cumplimiento y la proyección, cada una con sus propias cachés. Su comportamiento en torno a la normalización, la coinducción y las restricciones de rango superior está poco especificado, y varios errores de corrección de larga duración vienen de él.
  • Chalk (2017–) fue un experimento para implementar el sistema de traits como un motor lógico explícito: bajar Rust a cláusulas de programa, resolver con un resolutor SLG al estilo de Prolog, canonizar los objetivos para la caché. Aclaró la teoría y se usó en rust-analyzer; ya no se persigue como resolutor de rustc.
  • El resolutor de traits de nueva generación (-Znext-solver) es la reescritura que llevó las lecciones de Chalk a la propia representación de tipos de rustc: un único resolutor recursivo y uniforme, consultas canónicas con un punto fijo correcto para el tratamiento de ciclos, y normalización perezosa. Se usa para la comprobación de coherencia en estable desde Rust 1.84, y el resto de la comprobación de tipos se está trasladando de forma incremental. Es el requisito previo de una lista de características bloqueadas: restricciones implícitas, objetivos de trait coinductivos, un mejor tratamiento de los tipos opacos y de los GAT.
  • a-mir-formality modela estas reglas de forma ejecutable, como candidata a especificación.

Agujeros de corrección conocidos

Estudiar las incidencias abiertas de incorrección es una de las formas más rápidas de entender un sistema de tipos. La más famosa es rust-lang/rust#25860 (2015), que explota las restricciones implícitas (implied bounds) junto con la contravarianza:

static UNIT: &'static &'static () = &&();

// El tipo `&'a &'b ()` solo está bien formado si 'b: 'a, así que esa restricción está *implícita*
// para el cuerpo de la función y no hace falta escribirla.
fn helper<'a, 'b, T>(_: &'a &'b (), v: &'b T) -> &'a T { v }

fn extend<'a, 'b, T>(x: &'a T) -> &'b T {
    // Convertir a un puntero a función con 'static en el primer argumento descarta en silencio
    // la restricción implícita: nada vuelve a comprobar 'b: 'a para los lifetimes reales.
    let f: fn(&'static &'static (), &'a T) -> &'b T = helper;
    f(UNIT, x)
}
// `extend` convierte cualquier referencia en una de cualquier lifetime, en código seguro.

La restricción implícita se usa al comprobar el cuerpo de helper, pero no se conserva cuando la función se convierte a un tipo de puntero a función con un primer argumento distinto. El resultado es una función segura que fabrica lifetimes arbitrarios: un uso después de liberar sin unsafe. Arreglarlo como es debido exige tratar las restricciones implícitas como cláusulas where reales y de rango superior, algo que el resolutor antiguo no puede representar; es uno de los problemas que motivaron el nuevo. La incidencia estuvo abierta una década, no se sabe que haya ocurrido por accidente en código real, y es un caso de estudio excelente de lo sutil que es la interacción entre la varianza, la buena formación y los tipos de rango superior.

Pruébalo: Rust 1.100, con el que se comprobó esta lección, rechaza la conversión de extend con «lifetime may not live long enough»: la restricción implícita ahora se vuelve a comprobar. Los compiladores de los años en que el agujero estuvo abierto aceptan el programa tal como está escrito.

Lista de lecturas

  1. La rustc dev guide: «Trait solving», «The next-generation trait solver», «Coherence».
  2. Matsakis, «Lowering Rust traits to logic» y las entradas de blog posteriores (2017); el Chalk book.
  3. RFC 1023 (reglas del huérfano), RFC 2451 (reequilibrado de la coherencia), RFC 1210 (especialización).
  4. Matsakis, «Maximally minimal specialization: always applicable impls» (2018).
  5. Wadler y Blott, «How to make ad-hoc polymorphism less ad hoc» (POPL 1989): de donde vienen las clases de tipos.
  6. Chakravarty, Keller, Peyton Jones y Marlow, «Associated types with class» (POPL 2005).
  7. El repositorio a-mir-formality; la etiqueta de incidencias I-unsound de rust-lang.

Ejercicios

  1. Escribe las cláusulas de programa de impl<T: Ord> Ord for Option<T> e impl<T: PartialOrd> PartialOrd for [T], y después dibuja el árbol de demostración de Option<Option<u8>>: Ord.
  2. Construye dos impls que la comprobación de solapamiento rechace aunque ningún tipo cumpla actualmente los dos. Explica el razonamiento de «compatibilidad futura».
  3. Crea un tipo recursivo que no sea Send y sigue la demostración coinductiva hasta la hoja que falla.
  4. Lee la incidencia #25860 y los arreglos propuestos. Explica dónde se pierde exactamente la restricción implícita.
  5. Da un ejemplo en el que añadir un impl a una biblioteca rompa la inferencia de tipos en un crate dependiente sin ningún error de coherencia.

Comprueba lo que has entendido

Elige una respuesta para ver la explicación.

  1. 1.Como regla lógica, ¿cómo se lee impl<T: Clone> Clone for Vec<T>?

  2. 2.¿Por qué los auto traits como Send se resuelven de forma coinductiva?

  3. 3.¿Por qué es incorrecta (unsound) la especialización sin restricciones?

Términos clave de esta lección

¿Has terminado la lección y los ejercicios?