Ferrugem. Emprestar verificador através de iteradores

Olá Habr!

Eu estudo há cerca de um ano e, nas horas vagas, escrevo sobre o assunto. Gosto de como seus autores resolveram o problema do gerenciamento de memória e dispensaram o coletor de lixo - através do conceito de empréstimo. Neste artigo, abordarei essa idéia por meio de iteradores.

Ultimamente, scala é o meu idioma principal, então haverá comparações com ele, mas não há muitos e tudo é intuitivo, sem mágica :) O

artigo foi criado para aqueles que ouviram algo sobre ferrugem, mas não entraram em detalhes.


fotos tiradas daqui e daqui

Prefácio


Nas linguagens jvm, é habitual ocultar o trabalho com links, ou seja, quase sempre trabalhamos com tipos de dados de referência, por isso decidimos ocultar oe comercial (&).

No rasta existem links explícitos, por exemplo, para inteiro - `& i32`, o link pode ser desreferenciado por` * `, também pode haver um link para o link e, em seguida, será necessário desreferenciado duas vezes **.

Iterador


Ao escrever código, muitas vezes você precisa filtrar a coleção por uma condição (predicado). No rock, pegar elementos pares seria algo assim:

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

Vejamos os 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
  }

Sem entrar nos detalhes do `newBuilder`, é claro que uma nova coleção está sendo criada, iteramos sobre a antiga e, se o predicado retornar verdadeiro, adicione um elemento. Apesar do fato de a coleção ser nova, seus elementos são na verdade links para elementos da primeira coleção e, se, de repente, esses elementos forem mutáveis, sua alteração será comum a ambas as coleções.

Agora vamos tentar fazer o mesmo no passado. Darei imediatamente um exemplo de trabalho e depois considerarei as diferenças.

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

Uau, uau o que? Desreferenciamento de ponteiro duplo? Apenas para filtrar o vetor? Difícil :( Mas há razões para isso.

Vamos destacar como esse código difere do rock:

  1. obtenha explicitamente o iterador no vetor (`iter ()`)
  2. na função predicado, por algum motivo, desreferenciamos o ponteiro duas vezes
  3. chame `collect ()`
  4. também resultou em um vetor de tipos de referência Vec <& i32>, e ints não comuns

Emprestar verificador


Por que chamar explicitamente `iter ()` na coleção? Está claro para qualquer rockman que, se você chamar `.filter (...)`, precisará iterar sobre a coleção. Por que, de maneira explícita, escreva explicitamente o que pode ser feito implicitamente? Porque existem três iteradores diferentes!



Para descobrir por que três? necessidade de tocar em Borrow (emprestado, pedir emprestado) verificador 'a. A mesma coisa pela qual o rast funciona sem um GC e sem alocação / desalocação explícita de memória.

Por que é necessário?

  1. Para evitar situações em que vários ponteiros apontam para a mesma área de memória, permitindo que você a altere. Essa é uma condição de corrida.
  2. Para não desalocar a mesma memória várias vezes.

Como isso é alcançado?

Devido ao conceito de propriedade.

Em geral, o conceito de propriedade é simples - apenas um pode possuir alguma coisa (mesmo intuição).

O proprietário pode mudar, mas ele está sempre sozinho. Quando escrevemos `let x: i32 = 25 ', isso significa que houve uma alocação de memória para 32bit int e um certo` x` é o proprietário. A ideia de propriedade existe apenas na mente do compilador, no verificador de empréstimos. Quando o proprietário, neste caso, `x` sai do escopo (sai do escopo), a memória da qual ele possui será limpa.

Aqui está um código que o emprestador não 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` é algo como` case class X () `- uma estrutura sem borda.

Esse comportamento é super contra-intuitivo, eu acho, para todos. Não conheço outros idiomas nos quais seria impossível "usar" a mesma "variável" duas vezes. É importante sentir esse momento. primeiro não é uma referência a X, é seu proprietário . Mudando o proprietário, nós meio que matamos o anterior, o verificador de empréstimo não permitirá seu uso.

Por que você precisou criar sua própria estrutura, por que não usar um número inteiro 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.

Voltar para os iteradores. O conceito de "captura" entre eles é o IntoIter . Ele "engole" a coleção, dando posse de seus elementos. No código, essa ideia será refletida assim:


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

Ao chamar `into_iter ()` em coll_1, nós o "transformamos" em um iterador, absorvendo todos os seus elementos, como no exemplo anterior, `segundo` absorvido` primeiro`. Depois disso, todas as chamadas para coll_1 serão punidas pelo verificador emprestado durante a compilação. Em seguida, coletamos esses elementos com a função `collect`, criando um novo vetor. A função `collect` é necessária para coletar uma coleção de um iterador, para isso é necessário especificar explicitamente o tipo do que queremos coletar. Portanto, coll_2 indica claramente o tipo.

Ok, em geral, o descrito acima é suficiente para uma linguagem de programação, mas não será muito eficiente copiar / clonar estruturas de dados toda vez que quisermos transferi-las e você também precisará alterar alguma coisa. Então, vamos às dicas.

Ponteiros


O proprietário, como descobrimos, pode ser apenas um. Mas você pode ter qualquer número de links.


#[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 já é válido, porque o proprietário ainda é um. Toda a lógica de propriedade é verificada apenas no estágio de compilação, sem afetar a alocação / movimentação de memória. Além disso, você pode ver que o tipo de segundo foi alterado para `& Y`! Ou seja, a semântica de propriedade e links são refletidos nos tipos, o que permite verificar durante a compilação, por exemplo, a ausência de uma condição de corrida.

Como posso me proteger contra a condição de corrida em tempo de compilação?

Definindo um limite para o número de links mutáveis!

Um link mutável em um momento no tempo pode ser um e apenas um (sem imutável). Ou seja, um / vários imutáveis ​​ou um mutável. O código fica assim:


// 
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;
}

Vamos examinar as mudanças no exemplo anterior relativo. Primeiro, adicionamos um campo à estrutura para que houvesse algo para mudar, porque precisamos de mutabilidade. Em segundo lugar, `mut` apareceu na declaração da variável` let mut first = ... `, este é um marcador para o compilador sobre mutabilidade, como` val` e `var` na rocha. Em terceiro lugar, todos os links mudaram de tipo de `& X` para` & mut X` (parece, é claro, monstruoso. E isso é sem tempo de vida ...), agora podemos alterar o valor armazenado pelo link.

Mas eu disse que não podemos criar vários links mutáveis, eles dizem que o emprestador não dará isso, mas eu mesmo criei dois! Sim, mas as verificações lá são muito complicadas, e é por isso que às vezes não é óbvio porque o compilador jura. Ele está se esforçando para garantir que seu programa seja compilado e se não houver absolutamente nenhuma opção para cumprir as regras, um erro e talvez não o que você está esperando, mas aquele que viola sua última tentativa, a mais desesperada e não óbvia para um iniciante: ) Por exemplo, você é informado de que a estrutura não implementa a característica de Cópia, embora você não tenha chamado cópias em nenhum lugar.

Nesse caso, a existência de dois links mutáveis ​​é permitida ao mesmo tempo, porque usamos apenas um, ou seja, o segundo pode ser descartado e nada muda. Também o `segundo` pode ser usado atécrie um terceiro e então tudo ficará bem. Mas, se você descomentar `second.x = 33;`, acontece que dois links mutáveis ​​existem simultaneamente e você não pode sair daqui de qualquer maneira - compile um erro de tempo.

Iteradores


Portanto, temos três tipos de transmissão:

  1. Absorção, empréstimo, movimento
  2. Ligação
  3. Link mutável

Cada tipo precisa de seu próprio iterador.

  1. O IntoIter absorve objetos da coleção original
  2. Iter é executado em links de objetos
  3. O IterMut é executado em referências de objetos mutáveis

Surge a questão - quando usar qual. Não existe uma bala de prata - você precisa praticar, ler o código de alguém, artigos. Vou dar um exemplo demonstrando a ideia.

Suponha que exista uma escola, que haja uma classe nela e os alunos na classe.


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

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

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

Pegamos o vetor de crianças em idade escolar consultando o banco de dados, por exemplo. Em seguida, eu precisava contar o número de meninas na classe. Se "engolimos" o vetor através de `into_iter ()`, depois de contar, não podemos mais usar esta coleção para contar os meninos:


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();
}

Haverá um erro "valor usado aqui após o movimento" na linha para contar meninos. Também é óbvio que o iterador mutável não é útil para nós. É por isso que é apenas `iter ()` e trabalhando com um link duplo:


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();
}

Aqui, para aumentar o número de recrutas em potencial no país, um iterador mutável já é necessário:


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

Desenvolvendo a idéia, podemos transformar soldados em "caras" e demonstrar o iterador "absorvente":


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,    
}

Nesta nota maravilhosa, talvez seja tudo.

A última pergunta permanece - de onde veio a dupla desreferenciação dos links no `filter`. O fato é que um predicado é uma função que faz referência a um argumento (para não capturá-lo):


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

o predicado é FnMut (a grosso modo uma função), que faz uma referência ao seu item (próprio) e retorna bool. Como já tínhamos um link do iterador `.iter ()`, o segundo apareceu no filtro. Quando absorvido por um iterador (`into_iter`), a desreferenciação dupla do link se torna regular.

Continuação


Como não tenho muita experiência em escrever artigos, ficarei feliz em criticar.
Se estiver interessado, eu posso continuar. Opções para tópicos:

  • como e quando ocorre a desalocação de memória
  • vida útil do link
  • programação assíncrona
  • escrevendo um pequeno serviço web, você pode até oferecer API

Ligações


  • livro de ferrugem
  • Devido ao conceito de propriedade, a implementação de itens básicos como, por exemplo, uma lista vinculada não é mais trivial. Aqui estão várias maneiras de implementá-las.

All Articles