Oxido. Verificador de préstamos a través de iteradores

Hola Habr!

He estado estudiando durante aproximadamente un año y, en mi tiempo libre, escribo en el rast. Me gusta cómo sus autores resolvieron el problema de la gestión de la memoria y prescindieron del recolector de basura, a través del concepto de préstamo. En este artículo abordaré esta idea a través de iteradores.

Últimamente, scala es mi idioma principal, por lo que habrá comparaciones con él, pero no hay muchos y todo es intuitivo, sin magia :) El

artículo está diseñado para aquellos que escucharon algo sobre el óxido, pero no entraron en detalles.


fotos tomadas desde aquí y desde aquí

Prefacio


En los idiomas jvm, se acostumbra ocultar el trabajo con enlaces, es decir, casi siempre trabajamos con tipos de datos de referencia, por lo que decidimos ocultar el ampersand (&).

En el rasta hay enlaces explícitos, por ejemplo, al número entero: `& i32`, el enlace se puede desreferenciar a través de` * `, también puede haber un enlace al enlace y luego deberá desreferenciarse dos veces **.

Iterador


Al escribir código, muy a menudo necesita filtrar la colección por una condición (predicado). En la roca, tomar elementos parecidos se vería así:

    val vec = Vector(1,2,3,4)
    val result = vec.filter(e => e % 2 == 0)

Veamos los tipos:

  private[scala] def filterImpl(p: A => Boolean, isFlipped: Boolean): Repr = {
    val b = newBuilder
    for (x <- this)
      if (p(x) != isFlipped) b += x

    b.result
  }

Sin entrar en los detalles de `newBuilder`, está claro que se está creando una nueva colección, iteramos sobre la anterior y si el predicado devuelve verdadero, entonces agregue un elemento. A pesar de que la colección es nueva, sus elementos son en realidad enlaces a elementos de la primera colección, y si, de repente, estos elementos son mutables, entonces cambiarlos será común a ambas colecciones.

Ahora intentemos hacer lo mismo en el rast. Daré inmediatamente un ejemplo de trabajo y luego consideraré las diferencias.

    let v: Vec<i32> = vec![1, 2, 3, 4];
    let result: Vec<&i32> = v.iter().filter(|e| **e % 2 == 0).collect();

Wow, wow que? ¿Doble referencia de puntero? ¿Solo para filtrar el vector? Difícil :( Pero hay razones para esto.

Señalemos cómo este código difiere de la roca:

  1. obtener explícitamente el iterador en el vector (`iter ()`)
  2. en la función predicado, por alguna razón, desreferenciamos el puntero dos veces
  3. llame a `collect ()`
  4. también dio como resultado un vector de tipos de referencia Vec <& i32>, y no ints ordinarios

Verificador de préstamos


¿Por qué llamar explícitamente a `iter ()` en la colección? Está claro para cualquier rockman que si llamas a `.filter (...)` entonces necesitas iterar sobre la colección. ¿Por qué en un rast escribe explícitamente lo que se puede hacer implícitamente? ¡Porque hay tres iteradores diferentes!



Para averiguar por qué tres? es necesario tocar el verificador de Préstamo (préstamo, préstamo) 'a. La razón por la cual el rast funciona sin un GC y sin asignación / desasignación de memoria explícita. ¿Por qué es necesario?



  1. Para evitar situaciones en las que varios punteros apuntan a la misma área de memoria, lo que le permite cambiarla. Esa es una condición de carrera.
  2. Para no desasignar la misma memoria varias veces.

¿Cómo se logra esto?

Debido al concepto de propiedad.

En general, el concepto de propiedad es simple: solo uno puede poseer algo (incluso la intuición).

El dueño puede cambiar, pero siempre está solo. Cuando escribimos `let x: i32 = 25`, esto significa que se asignó memoria para un int de 32 bits y que posee una cierta` x`. La idea de propiedad solo existe en la mente del compilador, en el verificador de préstamos. Cuando el propietario, en este caso, `x` abandona el alcance (queda fuera de alcance), se borrará la memoria de la que es propietario.

Aquí hay un código que el verificador de préstamos no perderá:


struct X; // 

fn test_borrow_checker () -> X {
    let first = X; //  
    let second = first; //  
    let third = first; //   ,   first   
//    value used here after move

    return third;
}

`struct X` es algo así como` case class X ()` - una estructura sin bordes.

Este comportamiento es súper contradictorio, creo, para todos. No conozco otros idiomas en los que sería imposible "usar" la misma "variable" dos veces. Es importante sentir este momento. primero no es en absoluto una referencia a X, es su dueño . Cambiando el propietario, matamos al anterior, el verificador de préstamos no permitirá su uso.

¿Por qué necesitabas crear tu propia estructura, por qué no usar un entero regular?
— (`struct X`), , , integer. , , :


fn test_borrow_checker () -> i32 {
    let first = 32;
    let second = first; 
    let third = first; 

    return third;
}

, borrow checker, , . Copy, . `i32` second , ( ), - third . X Copy, .

. , , «» . Clone, , . copy clone.

De vuelta a los iteradores. El concepto de "captura" entre ellos es IntoIter . Él "traga" la colección, dando posesión de sus elementos. En el código, esta idea se reflejará así:


let coll_1 = vec![1,2,3];
let coll_2: Vec<i32> = coll_1.into_iter().collect();
//coll_1 doesn't exists anymore

Al llamar a `into_iter ()` en coll_1 lo "convertimos" en un iterador, absorbimos todos sus elementos, como en el ejemplo anterior, `second` absorbió` first`. Después de eso, cualquier llamada a coll_1 será castigada por el verificador de préstamos durante la compilación. Luego recolectamos estos elementos con la función `collect`, creando un nuevo vector. La función `collect` es necesaria para recopilar una colección de un iterador, para esto debe especificar explícitamente el tipo de lo que queremos recopilar. Por lo tanto, coll_2 indica claramente el tipo.

De acuerdo, en general, lo descrito anteriormente es suficiente para un lenguaje de programación, pero no será muy eficiente copiar / clonar estructuras de datos cada vez que queramos transferirlas, y también debe ser capaz de cambiar algo. Así que vamos a los punteros.

Punteros


El propietario, como hemos descubierto, puede ser solo uno. Pero puedes tener cualquier cantidad de enlaces.


#[derive(Debug)]
struct Y; // 

fn test_borrow_checker() -> Y {
    let first = Y; //  
    let second: &Y = &first; //   ,     
    let third = &first; //    

// 
    println!("{:?}", second);
    println!("{:?}", third);

    return first;
}


Este código ya es válido, porque el propietario sigue siendo uno. Toda la lógica de propiedad se verifica solo en la etapa de compilación, sin afectar la asignación / movimiento de memoria. ¡Además, puede ver que el tipo de segundo ha cambiado a `& Y`! Es decir, la semántica de la propiedad y los enlaces se reflejan en los tipos, lo que le permite verificar durante la compilación, por ejemplo, la ausencia de una condición de carrera.

¿Cómo puedo proteger contra la condición de carrera en tiempo de compilación?

Al establecer un límite en el número de enlaces mutables!

Un enlace mutable en un momento puede ser uno y solo uno (sin inmutable). Es decir, uno / varios inmutables o uno mutable. El código se ve así:


// 
struct X {
    x: i32,
} 

fn test_borrow_checker() -> X {
    let mut first = X { x: 20 }; //  
    let second: &mut X = &mut first; //   
    let third: &mut X = &mut first; //    .        `second`        - .
//    second.x = 33;  //    ,             ,    
    third.x = 33;

    return first;
}

Repasemos los cambios en el ejemplo anterior relativo. Primero, agregamos un campo a la estructura para que hubiera algo que cambiar, porque necesitamos mutabilidad. En segundo lugar, `mut` apareció en la declaración de la variable` let mut first = ...`, este es un marcador para el compilador sobre la mutabilidad, como `val` &` var` en la roca. En tercer lugar, todos los enlaces han cambiado su tipo de `& X` a` & mut X` (parece, por supuesto, monstruoso. Y esto es sin tiempo de vida ...), ahora podemos cambiar el valor almacenado por el enlace.

Pero dije que no podemos crear varios enlaces mutables, dicen que el comprobador de préstamos no dará esto, ¡pero yo mismo creé dos! Sí, pero las comprobaciones allí son muy complicadas, por lo que a veces no es obvio por qué el compilador jura. Él está haciendo todo lo posible para que su programa se compile y si no hay absolutamente ninguna opción para cumplir con las reglas, entonces es un error, y tal vez no el que está esperando, sino el que viola su último intento, el más desesperado y no obvio para un principiante: ) Por ejemplo, se le informa que la estructura no implementa el rasgo Copiar, aunque no llamó a ninguna copia en ninguna parte.

En este caso, se permite la existencia de dos enlaces mutables al mismo tiempo porque usamos solo uno, es decir, el segundo se puede tirar y nada cambiará. También `second` puede usarse hastacrear un 'tercero' y luego todo estará bien. Pero, si descomenta `second.x = 33;`, resulta que existen dos enlaces mutables simultáneamente y no puede salir de aquí de todos modos: error de tiempo de compilación.

Iteradores


Entonces, tenemos tres tipos de transmisión:

  1. Absorción, préstamo, mudanza.
  2. Enlace
  3. Enlace mutable

Cada tipo necesita su propio iterador.

  1. IntoIter absorbe objetos de la colección original.
  2. Iter se ejecuta en enlaces de objetos
  3. IterMut se ejecuta en referencias de objetos mutables

Surge la pregunta: cuándo usar cuál. No hay una bala de plata: necesitas práctica, leer el código de otra persona, artículos. Daré un ejemplo que demuestre la idea.

Supongamos que hay una escuela, hay una clase en ella y estudiantes en la clase.


#[derive(PartialEq, Eq)]
enum Sex {
    Male,
    Female
}

struct Scholar {
    name: String,
    age: i32,
    sex: Sex
}

let scholars: Vec<Scholar> = ...;

Tomamos el vector de escolares al consultar la base de datos, por ejemplo. Luego, necesitaba contar la cantidad de chicas en la clase. Si "tragamos" el vector a través de `into_iter ()`, luego de contar ya no podemos usar esta colección para contar a los niños:


fn bad_idea() {
    let scholars: Vec<Scholar> = Vec::new();
    let girls_c = scholars
        .into_iter()
        .filter(|s| (*s).sex == Sex::Female)
        .count();

    let boys_c = scholars 
        .into_iter()
        .filter(|s| (*s).sex == Sex::Male)
        .count();
}

Habrá un error "valor utilizado aquí después del movimiento" en la línea para contar niños. También es obvio que el iterador mutable no nos sirve de nada. Es por eso que es solo `iter ()` y funciona con un doble enlace:


fn good_idea() {
    let scholars: Vec<Scholar> = Vec::new();
    let girls_c = scholars.iter().filter(|s| (**s).sex == Sex::Female).count();
    let boys_c = scholars.iter().filter(|s| (**s).sex == Sex::Male).count();
}

Aquí, para aumentar el número de reclutas potenciales en el país, ya se requiere un iterador mutable:


fn very_good_idea() {
    let mut scholars: Vec<Scholar> = Vec::new();
    scholars.iter_mut().for_each(|s| (*s).sex = Sex::Male);
}

Desarrollando la idea, podemos hacer soldados con los "muchachos" y demostrar el iterador "absorbente":


impl Scholar {
    fn to_soldier(self) -> Soldier {
        Soldier { forgotten_name: self.name, number: some_random_number_generator() }
    }
}

struct Soldier {
    forgotten_name: String,
    number: i32
}

fn good_bright_future() {
    let mut scholars: Vec<Scholar> = Vec::new();
    scholars.iter_mut().for_each(|s| (*s).sex = Sex::Male);
    let soldiers: Vec<Soldier> = scholars.into_iter().map(|s| s.to_soldier()).collect();
    //   scholars,    
}

En esta maravillosa nota, tal vez eso es todo.

La última pregunta sigue siendo: ¿de dónde vino la doble desreferenciación de los enlaces en `filter`. El hecho es que un predicado es una función que toma una referencia a un argumento (para no capturarlo):


    fn filter<P>(self, predicate: P) -> Filter<Self, P> where
        Self: Sized, P: FnMut(&Self::Item) -> bool,

el predicado es FnMut (más o menos una función), que toma una referencia a su elemento (self) y devuelve bool. Como ya teníamos un enlace desde el iterador `.iter ()`, el segundo apareció en el filtro. Cuando es absorbido por un iterador (`into_iter`), la doble desreferenciación del enlace se convirtió en una normal.

Continuación


No tengo mucha experiencia en la redacción de artículos, por lo que me complacerá criticar.
Si está interesado, puedo continuar. Opciones para temas:

  • cómo y cuándo ocurre la desasignación de memoria
  • enlace de por vida
  • programación asincrónica
  • escribiendo un pequeño servicio web, incluso puedes ofrecer API

Enlaces


  • libro de óxido
  • Debido al concepto de propiedad, la implementación de cosas básicas como, por ejemplo, una lista vinculada ya no es trivial. Aquí hay varias formas de implementarlas.

All Articles