Nivel 4 · Experto· Lección 9 de 9 · 50 min
Proyecto final: implementar Vec
Construye un array que crece a partir de memoria en bruto — NonNull, Layout, crecimiento, tipos de tamaño cero, Drop, Deref, IntoIter — y audita su corrección.
Este proyecto final reúne todo el nivel 4. Vas a construir MyVec<T> desde el asignador hacia arriba, al estilo del Rustonomicon, y cada decisión de diseño recurrirá a una lección anterior: layout, varianza, drop check, seguridad ante pánicos, memoria sin inicializar.
La implementación completa está abajo como un único programa ejecutable. Lee los comentarios que siguen con el código a la vista, y después ejecútalo, y ejecútalo con Miri en el Playground.
use std::alloc::{self, Layout};
use std::marker::PhantomData;
use std::mem;
use std::ops::{Deref, DerefMut};
use std::ptr::{self, NonNull};
// ───────────────────────── RawVec: dueño de la reserva, no de los elementos ─────────────────────────
struct RawVec<T> {
ptr: NonNull<T>,
cap: usize,
}
impl<T> RawVec<T> {
const IS_ZST: bool = mem::size_of::<T>() == 0;
fn new() -> Self {
// Un vector de ZST nunca reserva memoria y puede contener «infinitos» elementos.
let cap = if Self::IS_ZST { usize::MAX } else { 0 };
RawVec { ptr: NonNull::dangling(), cap }
}
fn grow(&mut self) {
// Con cap == usize::MAX, un vector de ZST solo puede llegar aquí desbordando su longitud.
assert!(!Self::IS_ZST, "capacity overflow");
let (new_cap, new_layout) = if self.cap == 0 {
(4, Layout::array::<T>(4).unwrap())
} else {
let new_cap = self.cap.checked_mul(2).expect("capacity overflow");
// Layout::array falla si el tamaño superaría isize::MAX: un límite estricto
// del que dependen los desplazamientos de punteros.
(new_cap, Layout::array::<T>(new_cap).expect("capacity overflow"))
};
let new_ptr = if self.cap == 0 {
// SAFETY: new_layout tiene tamaño distinto de cero (T no es un ZST, new_cap > 0).
unsafe { alloc::alloc(new_layout) }
} else {
let old_layout = Layout::array::<T>(self.cap).unwrap();
// SAFETY: ptr lo reservó este asignador con old_layout; el tamaño nuevo es
// distinto de cero y no desborda isize al redondearlo a la alineación.
unsafe { alloc::realloc(self.ptr.as_ptr().cast(), old_layout, new_layout.size()) }
};
// Si falla, la reserva antigua queda intacta; aborta en lugar de deshacer la pila.
self.ptr = NonNull::new(new_ptr.cast()).unwrap_or_else(|| alloc::handle_alloc_error(new_layout));
self.cap = new_cap;
}
}
impl<T> Drop for RawVec<T> {
fn drop(&mut self) {
if self.cap != 0 && !Self::IS_ZST {
// SAFETY: reservado en `grow` exactamente con este layout.
unsafe { alloc::dealloc(self.ptr.as_ptr().cast(), Layout::array::<T>(self.cap).unwrap()) };
}
}
}
// ───────────────────────── MyVec: lleva la cuenta de qué elementos están inicializados ─────────────────────────
pub struct MyVec<T> {
buf: RawVec<T>,
len: usize,
_owns: PhantomData<T>, // somos dueños de valores T y los liberaremos
}
// SAFETY: MyVec<T> es dueño único de sus elementos, igual que Vec<T>.
unsafe impl<T: Send> Send for MyVec<T> {}
unsafe impl<T: Sync> Sync for MyVec<T> {}
impl<T> MyVec<T> {
pub fn new() -> Self {
MyVec { buf: RawVec::new(), len: 0, _owns: PhantomData }
}
fn ptr(&self) -> *mut T {
self.buf.ptr.as_ptr()
}
pub fn push(&mut self, value: T) {
if self.len == self.buf.cap {
self.buf.grow();
}
// SAFETY: len < cap, así que el hueco está dentro de la reserva y sin inicializar.
// `write` no libera el contenido anterior (basura).
unsafe { self.ptr().add(self.len).write(value) };
self.len += 1;
}
pub fn pop(&mut self) -> Option<T> {
if self.len == 0 {
return None;
}
self.len -= 1;
// SAFETY: el hueco `len` estaba inicializado; al decrementar len primero, nunca volveremos
// a leerlo ni a liberarlo, así que mover el valor hacia fuera con `read` no es un doble uso.
Some(unsafe { self.ptr().add(self.len).read() })
}
pub fn insert(&mut self, index: usize, value: T) {
assert!(index <= self.len, "index out of bounds");
if self.len == self.buf.cap {
self.buf.grow();
}
// SAFETY: index <= len < cap. Desplazar [index, len) una posición hacia arriba no se sale de los límites.
// Los rangos se solapan, así que debe ser `copy` (memmove), no copy_nonoverlapping.
unsafe {
let p = self.ptr().add(index);
ptr::copy(p, p.add(1), self.len - index);
p.write(value);
}
self.len += 1;
}
pub fn remove(&mut self, index: usize) -> T {
assert!(index < self.len, "index out of bounds");
self.len -= 1;
// SAFETY: index < len anterior. Lee el elemento y después cierra el hueco.
unsafe {
let p = self.ptr().add(index);
let value = p.read();
ptr::copy(p.add(1), p, self.len - index);
value
}
}
}
impl<T> Drop for MyVec<T> {
fn drop(&mut self) {
// SAFETY: los primeros `len` elementos están inicializados y se liberan exactamente una vez.
// Liberarlos como un slice también trata correctamente un destructor de elemento que entre en pánico.
unsafe { ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr(), self.len)) };
// `buf` se libera después (código de liberación de los campos) y devuelve la memoria.
}
}
// Deref a un slice nos da gratis len, iter, sort, indexación, binary_search…
impl<T> Deref for MyVec<T> {
type Target = [T];
fn deref(&self) -> &[T] {
// SAFETY: ptr no es nulo y está alineado (colgante vale para len 0 o para ZST);
// los primeros `len` elementos están inicializados.
unsafe { std::slice::from_raw_parts(self.ptr(), self.len) }
}
}
impl<T> DerefMut for MyVec<T> {
fn deref_mut(&mut self) -> &mut [T] {
// SAFETY: igual que arriba, y &mut self garantiza la unicidad.
unsafe { std::slice::from_raw_parts_mut(self.ptr(), self.len) }
}
}
// ───────────────────────── IntoIter: iteración que consume ─────────────────────────
pub struct IntoIter<T> {
_buf: RawVec<T>, // mantiene viva la reserva; la libera al liberarse
start: *const T,
end: *const T, // para los ZST: start + número de elementos restantes, como dirección
}
impl<T> IntoIterator for MyVec<T> {
type Item = T;
type IntoIter = IntoIter<T>;
fn into_iter(self) -> IntoIter<T> {
// Saca el búfer sin ejecutar el destructor de MyVec (que liberaría los elementos).
let this = mem::ManuallyDrop::new(self);
// SAFETY: `this` no se vuelve a usar ni a liberar, así que el búfer se mueve fuera exactamente una vez.
let buf = unsafe { ptr::read(&this.buf) };
let start = buf.ptr.as_ptr() as *const T;
let end = if RawVec::<T>::IS_ZST {
start.wrapping_byte_add(this.len)
} else {
// SAFETY: len <= cap, así que esto está como mucho una posición después del final de la reserva.
unsafe { start.add(this.len) }
};
IntoIter { _buf: buf, start, end }
}
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.start == self.end {
return None;
}
if RawVec::<T>::IS_ZST {
self.end = self.end.wrapping_byte_sub(1);
// SAFETY: un ZST se puede «leer» desde cualquier puntero no nulo y alineado.
Some(unsafe { NonNull::<T>::dangling().as_ptr().read() })
} else {
let item = self.start;
// SAFETY: start < end, así que `item` está inicializado y start+1 está dentro de los límites.
unsafe {
self.start = self.start.add(1);
Some(item.read())
}
}
}
}
impl<T> Drop for IntoIter<T> {
fn drop(&mut self) {
for _ in &mut *self {} // libera los elementos que no se consumieron
// Después `_buf` libera la reserva.
}
}
// ───────────────────────── poniéndolo a prueba ─────────────────────────
fn main() {
let mut v = MyVec::new();
for word in ["delta", "alpha", "charlie"] {
v.push(String::from(word));
}
v.insert(1, String::from("bravo"));
v.sort(); // método de slice, a través de DerefMut
println!("{:?} len={}", &*v, v.len());
println!("removed {:?}, popped {:?}", v.remove(0), v.pop());
let upper: Vec<String> = v.into_iter().map(|s| s.to_uppercase()).collect();
println!("{upper:?}");
// Elementos de tamaño cero: ninguna reserva en absoluto.
let mut units = MyVec::new();
for _ in 0..1_000 {
units.push(());
}
println!("{} units, then {} via IntoIter", units.len(), units.into_iter().count());
// Iterador consumido parcialmente: el resto debe liberarse igualmente (compruébalo con Miri).
let mut it = {
let mut v = MyVec::new();
for i in 0..5 { v.push(Box::new(i)); }
v.into_iter()
};
println!("{:?} {:?}", it.next(), it.next());
}
Notas de diseño
NonNull<T>, no *mut T
De la lección de varianza: *mut T es invariante, lo que haría que MyVec<&'static str> no se pudiera usar donde se espera un MyVec<&'a str>. NonNull<T> es covariante y da un nicho a Option<MyVec<T>>. También quita Send y Sync, así que los restauramos con unsafe impl con restricciones.
PhantomData<T>
NonNull<T> dice «apunta a un T», no «es dueño de un T». El marcador declara la propiedad para el drop checker. Como nuestro impl de Drop no es #[may_dangle], el compilador ya es conservador; el campo documenta la intención y coincide con lo que hace std.
Separar RawVec de MyVec
RawVec es dueño de la memoria: reservar, crecer, liberar. MyVec e IntoIter son dueños de los elementos: qué huecos están inicializados. Cada uno tiene su propio Drop. Así es exactamente como está organizada la biblioteca estándar, y permite que IntoIter reutilice la lógica de liberación sin duplicarla.
Los invariantes de seguridad
Todo el módulo depende de ellos, y cada método debe restaurarlos antes de retornar o de entrar en pánico:
buf.ptres o bien colgante (cuandocap == 0oTes un ZST) o bien apunta a una reserva para exactamentecapvalores de tipoT.len <= cap.- Los elementos de los índices
0..lenestán inicializados; los delen..capno. - La reserva ocupa como máximo
isize::MAXbytes.
len y buf son campos privados. Esa privacidad soporta carga: si el código seguro de fuera del módulo pudiera cambiar len, todos los bloques unsafe de aquí serían incorrectos. La unidad del razonamiento sobre unsafe es el módulo, no el bloque.
Reserva de memoria
Layout::array::<T>(n)calcula el tamaño y la alineación y falla si se desborda por encima deisize::MAX.- Llamar a
alloccon un layout de tamaño cero es comportamiento indefinido; de ahí los casos especiales paracap == 0y para los ZST. - Si la reserva falla se llama a
handle_alloc_error, que aborta. Deshacer la pila desde una situación de falta de memoria dentro de una colección haría casi imposible la seguridad ante pánicos. - El crecimiento duplica la capacidad, lo que da un
pushO(1) amortizado.
Mover valores hacia dentro y hacia fuera
| Operación | Usa | Porque |
|---|---|---|
| Poner un valor en memoria sin inicializar | ptr.write(v) |
no libera el contenido anterior |
| Sacar un valor, dejando el hueco lógicamente sin inicializar | ptr.read() |
copia bit a bit; debes garantizar que no se vuelve a leer ni a liberar |
| Desplazar un rango | ptr::copy |
memmove; admite solapamiento |
| Liberar en el sitio | ptr::drop_in_place |
ejecuta los destructores sin mover |
En pop y remove, len se decrementa antes de leer el valor. Si el orden fuera el inverso y algo entrara en pánico en medio, el destructor podría liberar el elemento una segunda vez.
Seguridad ante pánicos
¿Qué llamadas de este código pueden entrar en pánico? assert!, expect y, lo que es crucial, nada definido por el usuario mientras la estructura es inconsistente. push, insert y remove no llaman a código del usuario entre que rompen y restauran un invariante. Un extend_from_slice basado en Clone, o un retain con una clausura del usuario, necesitarían la técnica de la guarda de la lección de drop check.
Tipos de tamaño cero
Para un ZST, ptr.add(n) no cambia la dirección, así que siempre se cumpliría start == end y el iterador estaría vacío. La implementación trata en su lugar el puntero como un contador con wrapping_byte_add. Es el mismo truco que usa la biblioteca estándar.
Auditoría
No te fíes del código porque imprima lo correcto. Verifícalo:
- Miri. Copia el programa al Playground y pulsa Miri. Comprueba en cada acceso los límites, la inicialización, el aliasing y las fugas. Una ejecución limpia sobre pruebas que ejerciten el crecimiento, los ZST y un
IntoIterconsumido parcialmente es una evidencia fuerte. - Tipos de elemento adversarios. Prueba con un tipo que cuente las liberaciones (comprueba que cada valor se libera exactamente una vez) y con uno cuyo
Dropentre en pánico. - Compara con el código fuente. Lee
library/alloc/src/raw_vec.rsyvec/mod.rsen el repositorio de Rust. Reconocerás casi todo, y las diferencias —el parámetro del asignador,#[may_dangle], las especializaciones de recogida en el sitio— son instructivas.
Punto de control del nivel 4
Estás listo para el nivel 5 si puedes:
- Calcular el layout de un struct
repr(C)y explicar la optimización de nicho. - Indicar la varianza de
&'a mut T,Cell<T>yfn(T), y justificar cada una con un exploit que de otro modo compilaría. - Explicar qué garantiza
Piny escribir una proyección. - Elegir los órdenes para un protocolo de publicar/consumir y decir qué arista happens-before aporta cada uno.
- Explicar el problema ABA y un esquema de recuperación de memoria.
- Escribir un waker y el bucle de un ejecutor.
- Argumentar la corrección de una abstracción unsafe pequeña en términos de sus invariantes.
Ejercicios
- Añade
with_capacity,reserve,truncateyclear. ¿Cuáles de ellos deben pensar en los pánicos de los destructores de los elementos? - Implementa
drain(..), que devuelva un iterador que extraiga todos los elementos. Hazlo seguro ante fugas: si elDrainse olvida conmem::forget, el vector no debe exponer elementos ya movidos. (Pista: ponlen = 0por adelantado.) - Implementa
retain(&mut self, f: impl FnMut(&T) -> bool)y hazlo seguro ante pánicos con una guarda. Pruébalo con una clausura que entre en pánico a mitad de camino. - Implementa
Clone for MyVec<T: Clone>. Si elclonedel tercer elemento entra en pánico, ¿qué ocurre con los dos clones ya hechos? Asegúrate de que se liberan y de que se devuelve el búfer. - Escribe un tipo de prueba
DropCountery una prueba de propiedades que ejecute secuencias aleatorias de operaciones sobreMyVecyVecen paralelo, comprobando que el contenido es igual y que cada valor se libera exactamente una vez. Ejecútala con Miri. - Añade un parámetro de asignador
MyVec<T, A: Allocator>en nightly y compáralo constd.
Comprueba lo que has entendido
Elige una respuesta para ver la explicación.
1.¿Por qué la implementación usa
ptr::write(slot, value)en lugar de*slot = valueal añadir un elemento?2.¿Por qué hay que tratar de forma especial la capacidad para un
Tde tamaño cero?3.En
insert, ¿por qué se usaptr::copyy noptr::copy_nonoverlapping?