FerrousPath

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:

  1. buf.ptr es o bien colgante (cuando cap == 0 o T es un ZST) o bien apunta a una reserva para exactamente cap valores de tipo T.
  2. len <= cap.
  3. Los elementos de los índices 0..len están inicializados; los de len..cap no.
  4. La reserva ocupa como máximo isize::MAX bytes.

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 de isize::MAX.
  • Llamar a alloc con un layout de tamaño cero es comportamiento indefinido; de ahí los casos especiales para cap == 0 y 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 push O(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:

  1. 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 IntoIter consumido parcialmente es una evidencia fuerte.
  2. 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 Drop entre en pánico.
  3. Compara con el código fuente. Lee library/alloc/src/raw_vec.rs y vec/mod.rs en 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> y fn(T), y justificar cada una con un exploit que de otro modo compilaría.
  • Explicar qué garantiza Pin y 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

  1. Añade with_capacity, reserve, truncate y clear. ¿Cuáles de ellos deben pensar en los pánicos de los destructores de los elementos?
  2. Implementa drain(..), que devuelva un iterador que extraiga todos los elementos. Hazlo seguro ante fugas: si el Drain se olvida con mem::forget, el vector no debe exponer elementos ya movidos. (Pista: pon len = 0 por adelantado.)
  3. 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.
  4. Implementa Clone for MyVec<T: Clone>. Si el clone del 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.
  5. Escribe un tipo de prueba DropCounter y una prueba de propiedades que ejecute secuencias aleatorias de operaciones sobre MyVec y Vec en paralelo, comprobando que el contenido es igual y que cada valor se libera exactamente una vez. Ejecútala con Miri.
  6. Añade un parámetro de asignador MyVec<T, A: Allocator> en nightly y compáralo con std.

Comprueba lo que has entendido

Elige una respuesta para ver la explicación.

  1. 1.¿Por qué la implementación usa ptr::write(slot, value) en lugar de *slot = value al añadir un elemento?

  2. 2.¿Por qué hay que tratar de forma especial la capacidad para un T de tamaño cero?

  3. 3.En insert, ¿por qué se usa ptr::copy y no ptr::copy_nonoverlapping?

¿Has terminado la lección y los ejercicios?