Rouille. Emprunter le vérificateur via des itérateurs

Bonjour, Habr!

J'étudie depuis environ un an et, pendant mon temps libre, j'écris sur le rast. J'aime la façon dont ses auteurs ont résolu le problème de la gestion de la mémoire et évité le ramasse-miettes - grâce au concept d'emprunt. Dans cet article, j'aborderai cette idée à travers des itérateurs.

Dernièrement, la scala est ma langue principale, il y aura donc des comparaisons avec elle, mais il n'y en a pas beaucoup et tout est intuitif, sans magie :) L'

article est conçu pour ceux qui ont entendu quelque chose sur la rouille, mais qui ne sont pas entrés dans les détails.


photos prises d'ici et d'ici

Préface


Dans les langages jvm, il est habituel de masquer le travail avec les liens, c'est-à-dire que nous travaillons presque toujours avec les types de données de référence, nous avons donc décidé de masquer l'esperluette (&).

Dans le rasta, il existe des liens explicites, par exemple vers un entier - `& i32`, le lien peut être déréférencé via` *`, il peut également y avoir un lien vers le lien et ensuite il devra être déréférencé deux fois **.

Itérateur


Lors de l'écriture de code, vous devez très souvent filtrer la collection par une condition (prédicat). Dans la roche, prendre même des éléments ressemblerait à ceci:

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

Regardons les sortes:

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

    b.result
  }

Sans entrer dans les détails de `newBuilder`, il est clair qu'une nouvelle collection est en cours de création, nous itérons sur l'ancienne et si le prédicat retourne vrai, alors ajoutez un élément. Malgré le fait que la collection soit nouvelle, ses éléments sont en fait des liens vers des éléments de la première collection, et si, soudainement, ces éléments sont modifiables, leur modification sera commune aux deux collections.

Essayons maintenant de faire de même dans le rast. Je vais immédiatement donner un exemple de travail, puis je considérerai les différences.

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

Wow, wow quoi? Déréférencement de double pointeur? Juste pour filtrer le vecteur? Difficile :( Mais il y a des raisons à cela.

Voyons comment ce code diffère du rock:

  1. obtenir explicitement l'itérateur sur le vecteur (`iter ()`)
  2. dans la fonction prédicat, pour une raison quelconque, nous déréférencer le pointeur deux fois
  3. appelez `collect ()`
  4. cela a également donné lieu à un vecteur de types de référence Vec <& i32>, et non à des nombres ordinaires

Vérificateur d'emprunt


Pourquoi appeler explicitement `iter ()` sur la collection? Il est clair pour tout rockman que si vous appelez `.filter (...)` alors vous devez parcourir la collection. Pourquoi dans un rast écrire explicitement ce qui peut être fait implicitement? Parce qu'il y a trois itérateurs différents!



Pour comprendre pourquoi trois? besoin de toucher sur Emprunter (emprunter, emprunter) vérificateur 'a. La raison même pour laquelle le rast fonctionne sans GC et sans allocation / désallocation de mémoire explicite.

Pourquoi est-il nécessaire?

  1. Pour éviter les situations où plusieurs pointeurs pointent vers la même zone mémoire, ce qui vous permet de la modifier. C'est une condition de course.
  2. Afin de ne pas désallouer plusieurs fois la même mémoire.

Comment y parvient-on?

En raison du concept de propriété.

En général, le concept de propriété est simple - un seul peut posséder quelque chose (même l'intuition).

Le propriétaire peut changer, mais il est toujours seul. Lorsque nous écrivons `let x: i32 = 25`, cela signifie qu'il y avait une allocation de mémoire pour 32bit int et qu'un certain` x` en est propriétaire. L'idée de propriété n'existe que dans l'esprit du compilateur, dans le vérificateur d'emprunt. Lorsque le propriétaire, dans ce cas, «x» quitte la portée (sort de la portée), la mémoire dont il est propriétaire sera effacée.

Voici un code que le vérificateur d'emprunt ne manquera pas:


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` est quelque chose comme` case class X ()` - une structure sans bordure.

Ce comportement est super contre-intuitif, je pense, pour tout le monde. Je ne connais pas d'autres langues dans lesquelles il serait impossible "d'utiliser" deux fois la même "variable". Il est important de ressentir ce moment. le premier n'est pas du tout une référence à X, c'est son propriétaire . En changeant le propriétaire, nous tuons en quelque sorte le précédent, le vérificateur d'emprunt ne permettra pas son utilisation.

Pourquoi avez-vous eu besoin de créer votre propre structure, pourquoi ne pas utiliser un entier régulier?
— (`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.

Revenons aux itérateurs. Le concept de «capture» parmi eux est IntoIter . Il «avale» la collection, en donnant possession de ses éléments. Dans le code, cette idée sera reflétée comme ceci:


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

En appelant `into_iter ()` à coll_1, nous l'avons "transformé" en itérateur, absorbé tous ses éléments, comme dans l'exemple précédent, "second" absorbé "premier". Après cela, tous les appels à coll_1 seront punis par le vérificateur d'emprunt lors de la compilation. Ensuite, nous avons collecté ces éléments avec la fonction `collect`, créant un nouveau vecteur. La fonction `collect` est nécessaire pour collecter une collection à partir d'un itérateur, pour cela vous devez spécifier explicitement le type de ce que nous voulons collecter. Par conséquent, coll_2 indique clairement le type.

D'accord, en général, ce qui est décrit ci-dessus est suffisant pour un langage de programmation, mais il ne sera pas très efficace de copier / cloner des structures de données chaque fois que nous voulons les transférer, et vous devez également pouvoir changer quelque chose. Nous passons donc aux pointeurs.

Pointeurs


Le propriétaire, comme nous l'avons découvert, ne peut être qu'un seul. Mais vous pouvez avoir n'importe quel nombre de liens.


#[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;
}


Ce code est déjà valide, car le propriétaire en est toujours un. Toute la logique de propriété est vérifiée uniquement au stade de la compilation, sans affecter l'allocation / le déplacement de la mémoire. De plus, vous pouvez voir que le type de seconde a changé en «& Y»! Autrement dit, la sémantique de la propriété et des liens se reflète dans les types, ce qui vous permet de vérifier lors de la compilation, par exemple, l'absence de condition de concurrence.

Comment puis-je me protéger contre les conditions de concurrence lors de la compilation?

En fixant une limite au nombre de liens mutables!

Un lien mutable à un moment donné peut être un et un seul (sans immuable). C'est-à-dire soit un / plusieurs immuable, soit un mutable. Le code ressemble à ceci:


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

Passons en revue les changements dans l'exemple précédent relatif. Tout d'abord, nous avons ajouté un champ à la structure afin qu'il y ait quelque chose à changer, car nous avons besoin de mutabilité. Deuxièmement, `mut` est apparu dans la déclaration de la variable` let mut first = ...`, c'est un marqueur pour le compilateur sur la mutabilité, comme `val` &` var` dans la roche. Troisièmement, tous les liens ont changé leur type de `& X` à` & mut X` (cela semble, bien sûr, monstrueux. Et cela est sans durée de vie ...), maintenant nous pouvons changer la valeur stockée par le lien.

Mais j'ai dit que nous ne pouvons pas créer plusieurs liens mutables, ils disent que le vérificateur d'emprunt ne donnera pas cela, mais j'en ai créé deux moi-même! Oui, mais les vérifications y sont très délicates, c'est pourquoi il n'est parfois pas évident pourquoi le compilateur jure. Il s'efforce de s'assurer que votre programme compile et s'il n'y a absolument aucune option pour respecter les règles, alors une erreur, et peut-être pas celle que vous attendez, mais celle qui viole sa dernière tentative, la plus désespérée et pas évidente pour un débutant: ) Par exemple, vous êtes informé que la structure n'implémente pas le trait Copier, bien que vous n'ayez appelé aucune copie nulle part.

Dans ce cas, l'existence de deux liens mutables en même temps est autorisée car nous n'en utilisons qu'un, c'est-à-dire que le second peut être jeté et rien ne changera. «Second» peut également être utilisé jusqu'àcréer un "troisième" et tout ira bien. Mais, si vous décommentez `second.x = 33;`, il s'avère que deux liens mutables existent simultanément et vous ne pouvez pas sortir d'ici de toute façon - erreur de compilation.

Itérateurs


Nous avons donc trois types de transmission:

  1. Absorption, emprunt, déménagement
  2. Lien
  3. Lien mutable

Chaque type a besoin de son propre itérateur.

  1. IntoIter absorbe les objets de la collection originale
  2. Iter s'exécute sur des liens d'objet
  3. IterMut s'exécute sur des références d'objets mutables

La question se pose - quand utiliser lequel. Il n'y a pas de solution miracle - vous devez vous entraîner, lire le code, les articles de quelqu'un d'autre. Je vais donner un exemple illustrant l'idée.

Supposons qu'il y ait une école, une classe et des élèves dans la classe.


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

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

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

Nous avons pris le vecteur des écoliers en interrogeant la base de données, par exemple. Ensuite, je devais compter le nombre de filles dans la classe. Si nous «avalons» le vecteur via «into_iter ()», après le comptage, nous ne pouvons plus utiliser cette collection pour compter les garçons:


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

Il y aura une erreur «valeur utilisée ici après le déménagement» sur la ligne pour compter les garçons. Il est également évident que l'itérateur mutable ne nous est d'aucune utilité. C'est pourquoi c'est juste `iter ()` et travailler avec un double lien:


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

Ici, pour augmenter le nombre de recrues potentielles dans le pays, un itérateur mutable est déjà requis:


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

En développant l'idée, nous pouvons faire des soldats des «gars» et démontrer l'itérateur «absorbant»:


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

Sur cette merveilleuse note, c'est peut-être tout.

La dernière question demeure - d'où vient le double déréférencement des liens dans «filtre». Le fait est qu'un prédicat est une fonction qui prend une référence à un argument (pour ne pas le capturer):


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

le prédicat est FnMut (en gros, une fonction), qui prend une référence à son (auto) élément et renvoie bool. Comme nous avions déjà un lien depuis l'itérateur `.iter ()`, le second est apparu dans le filtre. Lorsqu'il est absorbé par un itérateur (`into_iter`), le double déréférencement du lien se transforme en un lien régulier.

Continuation


Je n'ai pas beaucoup d'expérience dans la rédaction d'articles, donc je serai heureux de critiquer.
Si cela m'intéresse, je peux continuer. Options pour les sujets:

  • comment et quand la désallocation de mémoire se produit
  • durée de vie du lien
  • programmation asynchrone
  • écrire un petit service web, vous pouvez même proposer des api

Liens


  • livre de rouille
  • En raison du concept de propriété, la mise en œuvre d'éléments de base tels que, par exemple, une liste chaînée n'est plus anodine. Voici plusieurs façons de les implémenter.

All Articles