Nivel 5 · Investigación· Lección 2 de 9 · 45 min
El borrow checker por dentro: NLL y Polonius
MIR, vivacidad e inferencia de regiones en los lifetimes no léxicos, los préstamos en dos fases, y la reformulación basada en préstamos conocida como Polonius.
El borrow checker es un análisis estático con una especificación precisa. Entender esa especificación convierte los mensajes de error, de sentencias de un oráculo, en hechos que se pueden derivar, y es el requisito previo para leer cualquier investigación sobre el sistema de tipos de Rust.
El destino de la compilación: MIR
El borrow checking se ejecuta sobre MIR, la representación intermedia de nivel medio: un grafo de flujo de control cuyos bloques básicos contienen sentencias simples sobre lugares (places: x, x.f, *x, x[i]) y terminan en un terminador (goto, switch, call, drop, return).
fn first_or_insert(v: &mut Vec<i32>) -> &mut i32 {
if v.is_empty() {
v.push(0);
}
&mut v[0]
}
fn main() {
let mut v = vec![];
*first_or_insert(&mut v) += 5;
println!("{v:?}");
}
En el Rust Playground, la herramienta Show MIR imprime el MIR de cualquier programa; en tu máquina, usa cargo rustc -- -Zunpretty=mir en nightly. Busca: los temporales explícitos _1, _2…, los marcadores StorageLive/StorageDead, los terminadores drop explícitos y los reborrows como _5 = &mut (*_1).
MIR es el nivel adecuado para el análisis porque todo lo implícito —las referencias automáticas, los temporales, el orden de liberación, las dos ramas de un match— se ha vuelto explícito.
Qué hay que demostrar
Cada expresión de préstamo &'r p o &'r mut p crea un préstamo (loan). El checker debe mostrar, para cada punto del programa:
- Que ningún acceso a un lugar entra en conflicto con un préstamo que esté vivo en ese punto. Leer entra en conflicto con un préstamo mutable vivo de un lugar que se solape; escribir, mover o tomar prestado de forma mutable entra en conflicto con cualquier préstamo vivo de un lugar que se solape.
- Que ningún préstamo sobrevive al almacenamiento de su lugar (no hay referencias colgantes).
- Que los movimientos se siguen: no se usa un lugar del que se ha movido el valor o que está sin inicializar (una pasada de flujo de datos aparte).
Todo gira en torno a la definición de préstamo vivo.
Lifetimes no léxicos (RFC 2094)
Antes de 2018, el lifetime de una referencia era un ámbito léxico. NLL lo redefinió:
Un lifetime es un conjunto de puntos del grafo de flujo de control.
El algoritmo:
1. Vivacidad. Calcula, con un análisis de flujo de datos hacia atrás estándar, dónde está viva cada variable (dónde puede usarse más adelante). Si una variable está viva en el punto P, toda región que aparezca en su tipo debe contener P.
2. Restricciones de subtipado. Cada asignación, llamada y retorno genera restricciones entre regiones. Asignar un &'a T a un lugar de tipo &'b T exige 'a: 'b en ese punto: el origen debe sobrevivir al destino. La varianza (nivel 4) determina qué restricciones genera un tipo compuesto.
3. Restricciones de reborrow. &'r mut *q, donde q: &'q mut T, añade 'q: 'r, con reglas de prefijos de soporte para las desreferencias anidadas.
4. Resolver. Empieza con cada región vacía y hazla crecer hasta el menor punto fijo que cumpla todas las restricciones: si 'a: 'b, todo punto de 'b debe estar en 'a.
5. Comprobar. Un préstamo con región 'r está vivo en todos los puntos de 'r. Recorre el MIR; informa de un error en cualquier acceso que entre en conflicto con un préstamo vivo.
fn main() {
let mut data = vec![1, 2, 3];
let first = &data[0]; // préstamo L1 de `data`, región 'r
println!("{first}"); // último uso de `first`: 'r termina aquí (vivacidad)
data.push(4); // acceso mutable a `data`: L1 no está vivo → aceptado
println!("{data:?}");
}
Con lifetimes léxicos, 'r se extendería hasta la llave de cierre y el push sería un error.
Préstamos en dos fases
vec.push(vec.len()) se traduce así: toma &mut vec, después evalúa el argumento (que lee vec) y después llama. Una lectura ingenua lo rechaza. Los préstamos en dos fases (two-phase borrows) tratan un &mut tomado automáticamente como reservado (actúa como un préstamo compartido) hasta que la llamada lo activa de verdad.
fn main() {
let mut v = vec![1, 2, 3];
v.push(v.len()); // reserva &mut v, lee v.len() y después activa
println!("{v:?}");
}
Esta pequeña característica tiene consecuencias sorprendentemente profundas para los modelos de aliasing de la próxima lección: Tree Borrows modela directamente la reserva.
Dónde NLL es demasiado estricto
Las restricciones de regiones en NLL son insensibles a la ubicación: 'a: 'b se cumple en todas partes o en ninguna. Eso rechaza un patrón correcto muy conocido, el «caso problemático n.º 3» de la RFC:
use std::collections::HashMap;
fn get_or_insert(map: &mut HashMap<u32, String>, key: u32) -> &String {
match map.get(&key) {
Some(value) => value, // se devuelve: este préstamo debe vivir durante todo el lifetime de la firma
None => {
map.insert(key, String::new()); // ❌ NLL: error[E0502], `map` sigue prestado aquí
&map[&key]
}
}
}
fn main() {
let mut m = HashMap::new();
println!("{:?}", get_or_insert(&mut m, 1));
}
En el brazo Some, el préstamo de map.get fluye hasta el valor de retorno, así que su región debe incluir todo el resto de la función en ese camino. NLL tiene una sola región, así que el préstamo se considera vivo también en el brazo None, y map.insert entra en conflicto. Ejecuta el ejemplo: Rust estable 1.100, con el que se comprobó esta lección, lo rechaza con E0502. Un compilador que lo acepte está usando un análisis al estilo de Polonius. (La solución universal es la API entry, o comprobar antes con contains_key.)
Polonius
Polonius (Matsakis, 2018) reformula el análisis. El cambio de perspectiva clave:
Una región no es un conjunto de puntos. Es un origen: un conjunto de préstamos de los que podría proceder una referencia.
La pregunta ya no es «¿en qué puntos es válida esta referencia?», sino «¿qué préstamos podría contener aquí esta referencia?». El análisis se expresa de forma natural en Datalog. Los hechos de entrada se extraen del MIR:
loan_issued_at(Origin, Loan, Point) // una expresión de préstamo crea Loan y lo coloca en Origin
subset_base(Origin1, Origin2, Point) // subtipado en Point: los préstamos de Origin1 fluyen a Origin2
origin_live_on_entry(Origin, Point) // el tipo de alguna variable viva menciona Origin
loan_killed_at(Loan, Point) // la ruta prestada se sobrescribe
loan_invalidated_at(Loan, Point) // un acceso aquí violaría Loan
cfg_edge(Point1, Point2)
y las reglas centrales (la variante «ingenua») son:
// Las relaciones de subconjunto se cumplen en el punto en que se introducen, son transitivas
// y se propagan por las aristas del CFG solo mientras los dos orígenes están vivos.
subset(O1, O2, P) :- subset_base(O1, O2, P).
subset(O1, O3, P) :- subset(O1, O2, P), subset(O2, O3, P).
subset(O1, O2, Q) :- subset(O1, O2, P), cfg_edge(P, Q),
origin_live_on_entry(O1, Q), origin_live_on_entry(O2, Q).
// ¿Qué préstamos contiene cada origen en cada punto?
origin_contains_loan_on_entry(O, L, P) :- loan_issued_at(O, L, P).
origin_contains_loan_on_entry(O2, L, P) :- origin_contains_loan_on_entry(O1, L, P), subset(O1, O2, P).
origin_contains_loan_on_entry(O, L, Q) :- origin_contains_loan_on_entry(O, L, P), cfg_edge(P, Q),
!loan_killed_at(L, P), origin_live_on_entry(O, Q).
// Un préstamo está vivo si algún origen vivo lo contiene.
loan_live_at(L, P) :- origin_contains_loan_on_entry(O, L, P), origin_live_on_entry(O, P).
// Un error es la invalidación de un préstamo vivo.
errors(L, P) :- loan_invalidated_at(L, P), loan_live_at(L, P).
Como subset está indexado por punto y se propaga por las aristas solo mientras los orígenes están vivos, la relación establecida en el brazo Some de arriba nunca llega al brazo None. El programa se acepta.
Polonius es estrictamente más permisivo que NLL y no acepta ningún programa incorrecto (es el mismo argumento de corrección con un análisis más fino). Además alinea la implementación con los modelos formales —las procedencias de Oxide son conjuntos de préstamos— y da una base más limpia para características futuras como los préstamos autorreferenciales.
Estado. La implementación original en Datalog era demasiado lenta para producción. El equipo del compilador ha estado reimplementando el análisis dentro del propio marco de flujo de datos de rustc, con una pasada sensible a la ubicación que se activa en nightly con -Zpolonius. Que esté activado por defecto depende de la versión que estés usando: consulta la incidencia de seguimiento del proyecto y las notas de la versión de tu toolchain en lugar de fiarte de ningún tutorial, incluido este.
Lo que el borrow checker no hace
- Es intraprocedural. Cada función se comprueba contra las firmas de las funciones a las que llama. Por eso existen las anotaciones de lifetime, y por eso cambiar el cuerpo de una función nunca puede romper a quien la llama.
- Razona sobre lugares, no sobre valores:
a.xya.yson disjuntos, perov[i]yv[j]no se distinguen, y tampoco dos llamadas a métodos que tocan campos distintos. - No razona sobre los valores de las condiciones: un préstamo bajo
if flagentra en conflicto con un uso bajoif !flag. - Es correcto pero incompleto: todo programa aceptado está libre de los errores que persigue (dado un código unsafe correcto); muchos programas seguros se rechazan.
Lista de lecturas
- RFC 2094, «Non-lexical lifetimes»: inusualmente legible; contiene el algoritmo completo.
- Matsakis, «An alias-based formulation of the borrow checker» (blog, 2018): la presentación de Polonius.
- El Polonius book y el repositorio
polonius-engine. - La rustc dev guide, capítulos sobre MIR y sobre el borrow checker.
- Weiss et al., «Oxide: The Essence of Rust».
- Stjerna, «Modelling Rust’s Reference Ownership Analysis Declaratively in Datalog» (tesis de máster, 2020).
Ejercicios
- Imprime el MIR de
first_or_insert. Identifica cada préstamo, el reborrow que produce la referencia devuelta y los terminadoresdrop. - A mano, calcula las regiones de NLL para una función de cinco líneas con un préstamo compartido, un uso y una mutación. Después mueve el uso después de la mutación y localiza el punto en conflicto.
- Para el ejemplo de
get_or_insert, escribe de manera informal los hechos de Polonius de los dos brazos y muestra por quéloan_live_atno se cumple en elinsert. - En nightly, compila el ejemplo con y sin
-Zpoloniusy compara. - Encuentra un programa correcto que tanto NLL como Polonius rechacen porque el checker razona sobre lugares y no sobre valores. Explica qué análisis adicional haría falta para aceptarlo.
Comprueba lo que has entendido
Elige una respuesta para ver la explicación.
1.¿Sobre qué representación se ejecuta el borrow checker?
2.En NLL, ¿qué es un lifetime (una región)?
3.¿Qué sigue Polonius que el NLL insensible a la ubicación no sigue?