Die Programmiersprache Rust

Mit Box<T> auf Daten im Heap zeigen

Der einfachste intelligente Zeiger ist Box, deren Typ Box<T> lautet. In Boxen kann man Daten im Heap anstatt auf dem Stack speichern. Was auf dem Stack verbleibt, ist der Zeiger auf die Daten im Heap. In Kapitel 4 findest du Informationen zum Unterschied zwischen Stack und Heap.

Boxen haben keinen Performanz-Overhead, außer dass die Daten auf den Heap anstatt auf dem Stack gespeichert werden, aber sie haben auch nicht viele zusätzliche Funktionalitäten. Sie werden am häufigsten in folgenden Situationen verwendet:

• Wenn man einen Typ hat, dessen Größe zum Zeitpunkt der Kompilierung nicht bekannt ist, und man einen Wert dieses Typs in einem Kontext verwenden möchte, für den eine genaue Größe erforderlich ist.
• Wenn man über eine große Datenmenge verfügt und das Eigentum übertragen möchte und sicherstellen will, dass die Daten dabei nicht kopiert werden.
• Wenn man einen Wert besitzen und sich nur darum kümmern möchte, dass es sich um einen Typ handelt, der ein bestimmtes Trait implementiert, anstatt den Typ zu spezifizieren.

Wir werden die erste Situation in „Ermöglichen rekursiver Typen mit Boxen“ zeigen. Im zweiten Fall kann die Übertragung des Eigentums an einer großen Datenmenge lange dauern, da die Daten auf dem Stack kopiert werden. Um die Performanz in dieser Situation zu verbessern, können wir die große Datenmenge auf dem Heap in einer Box speichern. Dann wird nur die kleine Menge von Zeigerdaten auf dem Stack kopiert, während die Daten, die referenziert werden, im Heap an einer Stelle verbleiben. Der dritte Fall ist als Trait-Objekt bekannt, und „Verwendung von Trait-Objekten zur Abstraktion über gemeinsames Verhalten“ in Kapitel 18 widmet sich diesem Thema. Was du hier lernst, wirst du in diesem Abschnitt erneut anwenden!

Daten im Heap speichern

Bevor wir den Heap-Anwendungsfall für Box<T> besprechen, werden wir die Syntax und die Interaktion mit Werten behandeln, die in einer Box<T> gespeichert sind.

Listing 15-1 zeigt, wie man mit einer Box einen i32-Wert auf dem Heap speichert:

Dateiname: src/main.rs

fn main() {
    let b = Box::new(5);
    println!("b = {b}");
}

Listing 15-1: Speichern eines i32-Wertes in einer Box im Heap

Wir definieren die Variable b so, dass sie den Wert einer Box hat, die auf den Wert 5 zeigt, der auf dem Heap allokiert ist. Dieses Programm gibt b = 5 aus, in diesem Fall können wir auf die Daten in der Box zugreifen, ähnlich als würden sich die Daten im Stack befinden. Genau wie bei Werten mit Eigentum wird auch eine Box freigegeben, wenn sie den Gültigkeitsbereich verlässt, wie dies bei b am Ende von main der Fall ist. Die Freigabe erfolgt sowohl für die Box (gespeichert im Stack) als auch für die Daten, auf die sie zeigt (gespeichert im Heap).

Es ist nicht besonders hilfreich, einen einzelnen Wert im Heap zu speichern, daher verwendet man Boxen selten alleine. Meistens ist es besser, Werte wie einen i32 auf dem Stack zu haben, wo sie standardmäßig gespeichert werden. Sehen wir uns einen Fall an, in dem Boxen es uns ermöglichen, Typen zu definieren, die wir nicht hätten, wenn es keine Boxen gäbe.

Ermöglichen rekursiver Typen mit Boxen

Ein Wert eines rekursiven Typs kann einen anderen Wert desselben Typs als Teil von sich selbst haben. Rekursive Typen stellen ein Problem dar, weil Rust zur Kompilierzeit wissen muss, wie viel Platz ein Typ einnimmt. Allerdings könnte die Verschachtelung von Werten rekursiver Typen theoretisch unendlich weitergehen, sodass Rust nicht wissen kann, wie viel Platz der Wert benötigt. Da Boxen eine bekannte Größe haben, können wir rekursive Typen ermöglichen, indem wir eine Box in die Definition des rekursiven Typs einfügen.

Als Beispiel für einen rekursiven Typ wollen wir uns die Cons-Liste ansehen. Dies ist ein Datentyp, den man häufig in funktionalen Programmiersprachen findet. Der Cons-Listen-Typ, den wir definieren werden, ist bis auf die Rekursion einfach; daher werden die Konzepte in dem Beispiel, mit dem wir arbeiten werden, immer dann nützlich sein, wenn du in komplexeren Situationen mit rekursiven Typen arbeitest.

Die Cons-Liste verstehen

Eine Cons-Liste ist eine Datenstruktur, die aus der Programmiersprache Lisp und ihren Dialekten stammt und aus verschachtelten Paaren besteht. Sie ist die Lisp-Version einer verketteten Liste. Ihr Name stammt von der Funktion cons (Kurzform von „construct function“) in Lisp, die aus ihren beiden Argumenten ein neues Paar konstruiert. Durch den Aufruf von cons für ein Paar, das aus einem Wert und einem anderen Paar besteht, können wir Cons-Listen konstruieren, die aus rekursiven Paaren bestehen.

Hier ist zum Beispiel eine Pseudocode-Darstellung einer Cons-Liste, die die Liste 1, 2, 3 enthält, wobei jedes Paar in Klammern steht:

(1, (2, (3, Nil)))

Jedes Element in einer Cons-Liste enthält zwei Elemente: den Wert des aktuellen Elements und das nächste Element. Das letzte Element in der Liste enthält nur ein Element namens Nil ohne ein nächstes Element. Eine Cons-Liste wird durch rekursives Aufrufen der Funktion cons erstellt. Der kanonische Name für den Basisfall der Rekursion lautet Nil. Beachte, dass dies nicht mit dem Konzept „null“ oder „nil“ in Kapitel 6 identisch ist, das einen fehlenden oder ungültigen Wert darstellt.

Die Cons-Liste ist keine häufig verwendete Datenstruktur in Rust. Wenn man in Rust eine Liste von Elementen hat, ist Vec<T> die bessere Wahl. Andere, komplexere rekursive Datentypen sind in verschiedenen Situationen nützlich. Wenn wir jedoch mit der Cons-Liste beginnen, können wir untersuchen, wie Boxen es uns ermöglichen, ohne große Ablenkung einen rekursiven Datentyp zu definieren.

Listing 15-2 enthält eine Aufzählungsdefinition (enum) für eine Cons-Liste. Beachte, dass dieser Code nicht kompiliert werden kann, da der Typ List keine bekannte Größe hat, wie wir nachfolgend sehen werden.

Dateiname: src/main.rs

enum List {
    Cons(i32, List),
    Nil,
}

fn main() {}

Listing 15-2: Der erste Versuch, eine Aufzählung zu definieren, um eine Datenstruktur der Cons-Liste von i32-Werten darzustellen

Hinweis: Für dieses Beispiel implementieren wir eine Cons-Liste, die nur i32-Werte enthält. Wir hätten sie mit generischen Typen implementieren können wie wir es in Kapitel 10 besprochen haben, um eine Cons-Liste zu erstellen, in der Werte eines beliebigen Typs gespeichert werden können.

Die Verwendung des Typs List, um die Liste 1, 2, 3 zu speichern, würde wie in Listing 15-3 aussehen.

Dateiname: src/main.rs

enum List {
    Cons(i32, List),
    Nil,
}

// --abschneiden--

use crate::List::{Cons, Nil};

fn main() {
    let list = Cons(1, Cons(2, Cons(3, Nil)));
}

Listing 15-3: Verwendung der List-Aufzählung, um die Liste 1, 2, 3 zu speichern

Der erste Cons-Wert enthält 1 und einen anderen List-Wert. Dieser List-Wert ist ein weiterer Cons-Wert, der 2 und einen anderen List-Wert enthält. Dieser List-Wert ist wiederum ein Cons-Wert, der 3 enthält und ein List, das schließlich Nil ist – die nicht-rekursive Variante, die das Ende der Liste signalisiert.

Wenn wir versuchen, den Programmcode in Listing 15-3 zu kompilieren, erhalten wir den Fehler der in Listing 15-4 gezeigt wird.

Dateiname: output.txt

$ cargo run
   Compiling cons-list v0.1.0 (file:///projects/cons-list)
error[E0072]: recursive type `List` has infinite size
 --> src/main.rs:1:1
  |
1 | enum List {
  | ^^^^^^^^^
2 |     Cons(i32, List),
  |               ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
2 |     Cons(i32, Box<List>),
  |               ++++    +

error[E0391]: cycle detected when computing when `List` needs drop
 --> src/main.rs:1:1
  |
1 | enum List {
  | ^^^^^^^^^
  |
  = note: ...which immediately requires computing when `List` needs drop again
  = note: cycle used when computing whether `List` needs drop
  = note: see https://rustc-dev-guide.rust-lang.org/overview.html#queries and https://rustc-dev-guide.rust-lang.org/query.html for more information

Some errors have detailed explanations: E0072, E0391.
For more information about an error, try `rustc --explain E0072`.
error: could not compile `cons-list` (bin "cons-list") due to 2 previous errors

Listing 15-4: Fehler, den wir erhalten, wenn wir versuchen, eine rekursive Aufzählung zu definieren

Der Fehler zeigt, dass dieser Typ „unendlich groß“ ist. Der Grund dafür ist, dass wir List mit einer rekursiven Variante definiert haben, sie enthält direkt einen anderen Wert von sich selbst, daher kann Rust nicht herausfinden, wie viel Speicherplatz zum Speichern eines Listenwerts erforderlich ist. Lass uns zusammenfassen, warum wir diesen Fehler bekommen. Schauen wir uns zunächst an, wie Rust ermittelt, wie viel Speicherplatz zum Speichern des Werts eines nicht-rekursiven Typs benötigt wird.

Die Größe eines nicht-rekursiven Typs berechnen

Erinnere dich an die in Listing 6-2 definierte Message-Aufzählung, als wir die Definition von Aufzählungen in Kapitel 6 besprochen haben:

enum Message {
    Quit,
    Move { x: i32, y: i32 },
    Write(String),
    ChangeColor(i32, i32, i32),
}

fn main() {}

Um zu bestimmen, wie viel Speicherplatz für einen Message-Wert benötigt wird, analysiert Rust alle Varianten, um festzustellen, welche Variante den meisten Speicherplatz benötigt. Rust erkennt, dass Message::Quit keinen Speicherplatz benötigt, und Message::Move so viel Speicherplatz braucht, um zwei i32-Werte zu speichern, und so weiter. Da nur eine Variante verwendet wird, ist der Speicherbedarf, den ein Message-Wert benötigt, gleich dem Speicherplatz, der zum Speichern der größten Variante benötigt wird.

Übertrage das auf den Fall, bei dem Rust zu bestimmen versucht, wie viel Speicherplatz ein rekursiver Typ wie die Aufzählung List in Listing 15-2 benötigt. Der Compiler betrachtet zunächst die Variante Cons, die einen Typ i32 und einen Wert vom Typ List enthält. Daher benötigt Cons Speicherplatz, der der Größe eines i32 plus der Größe einer List entspricht. Um herauszufinden, wie viel Speicher der Typ List benötigt, betrachtet der Compiler die Varianten, beginnend mit der Variante Cons. Die Variante Cons enthält einen Typ i32 und einen Wert vom Typ List. Dieser Vorgang wird wie in Abbildung 15-1 dargestellt, unendlich fortgesetzt.

Abbildung 15-1: Ein unendlicher List-Typ, der aus unendlichen Cons-Varianten besteht

Einen rekursiven Typ mit einer bekannten Größe erhalten

Da Rust nicht herausfinden kann, wie viel Speicherplatz für rekursiv definierte Typen reserviert werden muss, gibt der Compiler eine Fehlermeldung mit diesem hilfreichen Vorschlag aus:

help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
2 |     Cons(i32, Box<List>),
  |               ++++    +

In diesem Hinweis bedeutet „indirection“ (Umweg), dass die Datenstruktur den Wert nicht direkt speichern soll, sondern indirekt, indem stattdessen ein Zeiger auf den Wert gespeichert wird.

Da eine Box<T> ein Zeiger ist, weiß Rust immer, wie viel Platz eine Box<T> benötigt: Die Größe eines Zeigers ändert sich nicht basierend auf der Datenmenge, auf die er zeigt. Dies bedeutet, dass wir anstelle eines anderen List-Wertes direkt eine Box<T> in die Cons-Variante einfügen können. Die Box<T> zeigt auf den nächsten List-Wert, der sich auf dem Heap befindet und nicht in der Cons-Variante. Konzeptionell haben wir immer noch eine Liste, die mit Listen erstellt wurde, die andere Listen enthalten. Diese Implementierung ähnelt nun eher dem Platzieren der Elemente nebeneinander als ineinander.

Wir können die Definition der Liste List in Listing 15-2 und die Verwendung von List in Listing 15-3 in den Programmcode von Listing 15-5 ändern, der kompilieren wird.

Dateiname: src/main.rs

enum List {
    Cons(i32, Box<List>),
    Nil,
}

use crate::List::{Cons, Nil};

fn main() {
    let list = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil))))));
}

Listing 15-5: Definition von List, die Box<T> benutzt, um eine bekannte Größe zu haben

Die Cons-Variante benötigt die Größe eines i32 plus Platz zum Speichern der Zeigerdaten der Box. Die Nil-Variante speichert keine Werte und benötigt daher weniger Speicher als die Cons-Variante. Wir wissen nun, dass jeder List-Wert die Größe eines i32 plus die Größe der Zeigerdaten einer Box annimmt. Durch Verwenden einer Box haben wir die unendliche, rekursive Kette unterbrochen, sodass der Compiler die Größe ermitteln kann, die zum Speichern eines Listenwerts erforderlich ist. Abbildung 15-2 zeigt, wie die Variante Cons jetzt aussieht.

Abbildung 15-2: Ein List-Typ, der keine unendliche Größe hat, da Cons eine Box enthält

Boxen kümmern sich nur um die Dereferenzierung und Speicherallokation auf dem Heap, haben aber keine weiteren speziellen Funktionalitäten, wie wir sie bei anderen intelligenten Zeigertypen sehen werden. Sie haben aber auch keinen Performanz-Overhead, der mit diesen zusätzlichen Funktionalitäten verbunden ist. Daher können sie in Fällen wie der Cons-Liste nützlich sein, in denen die Dereferenzierung die einzige Funktionalität ist, die wir benötigen. Weitere Anwendungsfälle für Boxen werden wir uns auch in Kapitel 18 ansehen.

Der Typ Box<T> ist ein intelligenter Zeiger, da er das Trait Deref implementiert, mit dem Box<T>-Werte wie Referenzen behandelt werden können. Wenn ein Box<T>-Wert den Gültigkeitsbereich verlässt, werden die Daten am Heap, auf die die Box zeigt, aufgrund der Implementierung des Traits Drop ebenfalls aufgeräumt. Diese beiden Traits sind für die Funktionalität der anderen intelligenten Zeigertypen, die wir im restlichen Kapitel erläutern, noch wichtiger. Lass uns diese beiden Traits genauer untersuchen.