Rost. Checker über Iteratoren ausleihen

Hallo Habr!

Ich lerne seit ungefähr einem Jahr und schreibe in meiner Freizeit über das Rast. Mir gefällt, wie die Autoren das Problem der Speicherverwaltung gelöst und auf den Garbage Collector verzichtet haben - durch das Konzept der Ausleihe. In diesem Artikel werde ich mich dieser Idee durch Iteratoren nähern.

In letzter Zeit ist Scala meine Hauptsprache, daher wird es Vergleiche geben, aber es gibt nicht viele davon und alles ist intuitiv, ohne Magie :) Der

Artikel ist für diejenigen gedacht, die etwas über Rost gehört haben, aber nicht auf Details eingegangen sind.


Fotos von hier und von hier gemacht

Vorwort


In JVM-Sprachen ist es üblich, die Arbeit mit Links auszublenden. Das heißt, dort arbeiten wir fast immer mit Referenzdatentypen. Daher haben wir beschlossen, das kaufmännische Und (&) auszublenden.

Die Rasta hat explizite Links, zum Beispiel zu Integer - `& i32`, der Link kann über` *` dereferenziert werden, es kann auch einen Link zum Link geben und dann muss er zweimal dereferenziert werden **.

Iterator


Wenn Sie Code schreiben, müssen Sie die Sammlung sehr oft nach einer Bedingung (Prädikat) filtern. Im Fels würde es ungefähr so ​​aussehen, selbst Elemente aufzunehmen:

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

Schauen wir uns die Sorten an:

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

    b.result
  }

Ohne auf die Details von `newBuilder` einzugehen, ist klar, dass eine neue Sammlung erstellt wird. Wir iterieren über die alte und fügen ein Element hinzu, wenn das Prädikat true zurückgibt. Trotz der Tatsache, dass die Sammlung neu ist, sind ihre Elemente tatsächlich Verknüpfungen zu Elementen aus der ersten Sammlung. Wenn diese Elemente plötzlich veränderbar sind, werden beide Sammlungen gemeinsam geändert.

Versuchen wir nun, dasselbe im Rast zu tun. Ich werde sofort ein funktionierendes Beispiel geben und dann die Unterschiede betrachten.

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

Wow, wow was? Doppelzeiger-Dereferenzierung? Nur um den Vektor zu filtern? Schwer :( Aber es gibt Gründe dafür.

Lassen Sie uns herausgreifen, wie sich dieser Code vom Fels unterscheidet:

  1. Holen Sie sich explizit den Iterator auf den Vektor (`iter ()`)
  2. In der Prädikatfunktion dereferenzieren wir aus irgendeinem Grund den Zeiger zweimal
  3. Rufen Sie `collect ()` auf
  4. es ergab sich auch ein Vektor der Referenztypen Vec <& i32> und nicht gewöhnlicher Ints

Checker ausleihen


Warum explizit "iter ()" für die Sammlung aufrufen? Jedem Rockman ist klar, dass Sie die Sammlung durchlaufen müssen, wenn Sie ".filter (...)" aufrufen. Warum in einem Rast explizit schreiben, was implizit getan werden kann? Weil es drei verschiedene Iteratoren gibt!



Um herauszufinden, warum drei? Bedarf an berühren Borrow (borrow, borrow) checker ‚ein. Genau das, aufgrund dessen der Rast ohne GC und ohne explizite Speicherzuweisung / Freigabe funktioniert.

Warum wird es benötigt?

  1. Um Situationen zu vermeiden, in denen mehrere Zeiger auf denselben Speicherbereich zeigen, können Sie ihn ändern. Das ist eine Rennbedingung.
  2. Um den Speicher nicht mehrmals freizugeben.

Wie wird das erreicht?

Aufgrund des Eigentumsbegriffs.

Im Allgemeinen ist das Konzept des Eigentums einfach - nur einer kann etwas besitzen (sogar Intuition).

Der Besitzer kann wechseln, aber er ist immer allein. Wenn wir `let x: i32 = 25` schreiben, bedeutet dies, dass es eine Speicherzuordnung für 32bit int gab und ein bestimmtes` x` es besitzt. Die Idee des Eigentums existiert nur im Kopf des Compilers, im Leihprüfer. Wenn der Eigentümer in diesem Fall "x" den Bereich verlässt (verlässt den Bereich), wird der Speicher, dessen Eigentümer er ist, gelöscht.

Hier ist ein Code, den der Leihprüfer nicht verpassen wird:


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` ist so etwas wie` case class X ()` - eine randlose Struktur.

Ich denke, dieses Verhalten ist für alle sehr intuitiv. Ich kenne keine anderen Sprachen, in denen es unmöglich wäre, dieselbe "Variable" zweimal zu "verwenden". Es ist wichtig, diesen Moment zu fühlen. Erstens ist es überhaupt kein Verweis auf X, es ist sein Besitzer . Wenn wir den Besitzer wechseln, töten wir den vorherigen. Der Leihprüfer erlaubt seine Verwendung nicht.

Warum mussten Sie Ihre eigene Struktur erstellen, warum nicht eine reguläre Ganzzahl verwenden?
— (`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.

Zurück zu den Iteratoren. Das Konzept der "Erfassung" unter ihnen ist IntoIter . Er "schluckt" die Sammlung und gibt ihre Elemente in Besitz. Im Code wird diese Idee folgendermaßen wiedergegeben:


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

Durch Aufrufen von "into_iter ()" bei coll_1 "verwandelten" wir es in einen Iterator, der alle seine Elemente absorbierte, wie im vorherigen Beispiel "second" absorbierte "first". Danach werden alle Aufrufe von coll_1 während der Kompilierung vom Ausleihprüfer bestraft. Dann haben wir diese Elemente mit der Funktion "sammeln" gesammelt und einen neuen Vektor erstellt. Die Funktion `collect` wird benötigt, um eine Sammlung von einem Iterator zu sammeln. Dazu müssen Sie explizit den Typ angeben, den wir sammeln möchten. Daher gibt coll_2 den Typ eindeutig an.

Okay, im Allgemeinen reicht das oben Beschriebene für eine Programmiersprache aus, aber es ist nicht sehr effizient, Datenstrukturen jedes Mal zu kopieren / klonen, wenn wir sie übertragen möchten, und Sie müssen auch in der Lage sein, etwas zu ändern. Also gehen wir zu den Zeigern.

Zeiger


Der Besitzer kann, wie wir herausgefunden haben, nur einer sein. Sie können jedoch beliebig viele Links haben.


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


Dieser Code ist bereits gültig, da der Eigentümer noch einer ist. Die gesamte Besitzlogik wird nur in der Kompilierungsphase überprüft, ohne die Speicherzuweisung / -verschiebung zu beeinflussen. Außerdem können Sie sehen, dass sich der Typ der Sekunde in "& Y" geändert hat! Das heißt, die Semantik von Besitz und Links spiegelt sich in den Typen wider, sodass Sie während der Kompilierung beispielsweise das Fehlen einer Racebedingung überprüfen können.

Wie kann ich mich beim Kompilieren vor Race-Bedingungen schützen?

Indem Sie die Anzahl der veränderlichen Links begrenzen!

Eine veränderbare Verbindung zu einem bestimmten Zeitpunkt kann eine und nur eine sein (ohne unveränderliche). Das heißt, entweder eine / mehrere unveränderliche oder eine veränderliche. Der Code sieht folgendermaßen aus:


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

Lassen Sie uns die Änderungen im vorherigen Beispiel durchgehen. Zuerst haben wir der Struktur ein Feld hinzugefügt, damit sich etwas ändern kann, da wir Veränderbarkeit benötigen. Zweitens erschien `mut` in der Deklaration der Variablen` let mut first = ...`, dies ist ein Marker für den Compiler über Mutabilität, wie` val` & `var` im Gestein. Drittens haben alle Links ihren Typ von "& X" in "& mut X" geändert (es sieht natürlich monströs aus. Und dies ohne Lebenszeit ...). Jetzt können wir den vom Link gespeicherten Wert ändern.

Aber ich sagte, dass wir nicht mehrere veränderbare Links erstellen können, sie sagen, dass der Leihprüfer dies nicht geben wird, aber ich habe selbst zwei erstellt! Ja, aber die Überprüfungen dort sind sehr schwierig, weshalb es manchmal nicht offensichtlich ist, warum der Compiler schwört. Er ist bemüht sicherzustellen, dass Ihr Programm kompiliert wird und wenn es absolut keine Optionen gibt, um die Regeln zu erfüllen, dann ein Fehler, und vielleicht nicht der, auf den Sie warten, sondern der, der seinen letzten Versuch verletzt, der verzweifeltste und für einen Anfänger nicht offensichtliche: ) Sie werden beispielsweise darüber informiert, dass die Struktur das Kopiermerkmal nicht implementiert, obwohl Sie nirgendwo Kopien aufgerufen haben.

In diesem Fall ist die Existenz von zwei veränderlichen Links gleichzeitig zulässig, da wir nur einen verwenden, dh der zweite kann weggeworfen werden und nichts wird sich ändern. Auch `second` kann bis zu verwendet werdenErstelle ein "drittes" und dann wird alles in Ordnung sein. Wenn Sie jedoch "second.x = 33;" auskommentieren, stellt sich heraus, dass zwei veränderbare Links gleichzeitig vorhanden sind und Sie hier sowieso nicht raus können - Fehler beim Kompilieren.

Iteratoren


Wir haben also drei Arten der Übertragung:

  1. Absorption, Ausleihe, Bewegung
  2. Verknüpfung
  3. Veränderliche Verbindung

Jeder Typ benötigt einen eigenen Iterator.

  1. IntoIter absorbiert Objekte aus der Originalsammlung
  2. Iter läuft auf Objektverknüpfungen
  3. IterMut wird auf veränderlichen Objektreferenzen ausgeführt

Es stellt sich die Frage, wann welche zu verwenden sind. Es gibt keine Silberkugel - Sie müssen üben, den Code eines anderen lesen, Artikel. Ich werde ein Beispiel geben, das die Idee demonstriert.

Angenommen, es gibt eine Schule, eine Klasse und Schüler in der Klasse.


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

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

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

Wir haben den Vektor von Schulkindern genommen, indem wir zum Beispiel die Datenbank abgefragt haben. Als nächstes musste ich die Anzahl der Mädchen in der Klasse zählen. Wenn wir den Vektor durch "into_iter ()" "schlucken", können wir diese Sammlung nach dem Zählen nicht mehr zum Zählen der Jungen verwenden:


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

In der Zeile zum Zählen der Jungen wird der Fehler "Hier nach dem Verschieben verwendet" angezeigt. Es ist auch offensichtlich, dass der veränderbare Iterator für uns keinen Nutzen hat. Deshalb ist es nur "iter ()" und arbeitet mit einem doppelten Link:


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

Um die Anzahl potenzieller Rekruten im Land zu erhöhen, ist bereits ein veränderlicher Iterator erforderlich:


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

Wenn wir die Idee entwickeln, können wir aus den „Jungs“ Soldaten machen und den „absorbierenden“ Iterator demonstrieren:


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

In diesem wunderbaren Sinne ist das vielleicht alles.

Die letzte Frage bleibt - woher kommt die doppelte Dereferenzierung der Links in "Filter"? Tatsache ist, dass ein Prädikat eine Funktion ist, die auf ein Argument verweist (um es nicht zu erfassen):


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

Das Prädikat ist FnMut (grob gesagt eine Funktion), das auf sein (Selbst-) Element verweist und bool zurückgibt. Da wir bereits einen Link vom Iterator ".iter ()" hatten, erschien der zweite im Filter. Wenn es von einem Iterator (`into_iter`) absorbiert wird, wird die doppelte Dereferenzierung der Verbindung zu einer regulären.

Fortsetzung


Ich habe nicht viel Erfahrung im Schreiben von Artikeln, daher werde ich gerne kritisieren.
Bei Interesse kann ich weitermachen. Optionen für Themen:

  • wie und wann Speicherfreigabe erfolgt
  • Link-Lebensdauer
  • asynchrone Programmierung
  • Wenn Sie einen kleinen Webdienst schreiben, können Sie sogar API anbieten

Links


  • Rostbuch
  • Aufgrund des Eigentumskonzepts ist die Implementierung grundlegender Dinge wie beispielsweise einer verknüpften Liste nicht mehr trivial. Hier sind verschiedene Möglichkeiten, wie Sie sie implementieren können.

All Articles