Ein Zeiger ist eine Variable, die die Speicheradresse einer anderen Variable als Wert enthält.
Ein Array ist im Speicher als Sequenz seiner Elemente dargestellt. Ein Zeiger auf das Array enthält die Speicheradresse des ersten Elements. Addiert man zu der Adresse nun eine Zahl, ergibt sich eine neue Adresse, die einen verschobenen Zeiger darstellt.
Damit diese Verschiebung einwandfrei funktioniert, darf zur Adresse immer nur ein ganzzahliges Vielfaches der Elementgröße addiert werden. Erreicht wird dies, indem die Zahl vor der Addition implizit mit der Elementgröße multipliziert wird.
Die Arithmetik von Zeigern umfasst die folgenden Konzepte:
Eine Analogie aus der Mathematik sind Punkte und Vektoren. Der Zeiger entspricht einem Punkt im euklidischen Raum, die Zahl einem Vektor. So wie man zum Zeiger eine Zahl addieren kann, kann man zum Punkt einen Vektor addieren, wodurch sich eine Verschiebung des Punktes um diesen Vektor ergibt. Die Ordnungsrelation ist nur auf einem eindimensionalen Raum definierbar.
In Rust ist die Arithmetik für einfache Zeiger definiert. Die folgende Tabelle listet die wesentlichen Operationen auf.
| Operation | Erklärung |
|---|---|
p.add(i)
| Verschiebt den Zeiger p um i Elemente.
|
p.offset(i)
| Verschiebt p um i Elemente, wobei i auch negativ sein darf.
|
p1.offset_from(p2)
| Vorzeichen-behafteter Abstand der Zeiger. |
p1 == p2
| Die beiden Zeiger zeigen auf dieselbe Speicherzelle. |
p1 < p2
| Der zweite Zeiger zeigt auf eine spätere Speicherzelle. |
Die in Hochsprache formulierte Funktion
fn print_array(a: &[char]) {
for x in a {
println!("{}", x);
}
}
nimmt nach Absenkung diese Gestalt an:
fn print_array(a: &[char]) {
let mut p = a.as_ptr();
let p_end = unsafe {p.add(a.len())};
while p != p_end {
println!("{}", unsafe {*p});
p = unsafe {p.add(1)};
}
}
Oder alternativ:
fn print_array(a: &[char]) {
let mut p = a.as_ptr();
let mut n = a.len();
while n > 0 {
println!("{}", unsafe {*p});
p = unsafe {p.add(1)};
n -= 1;
}
}
Die Formulierung
fn print_array(a: &[char]) {
for i in 0..a.len() {
println!("{}", a[i]);
}
}
entspricht
fn print_array(a: &[char]) {
let p = a.as_ptr();
let n = a.len();
let mut i = 0;
while i < n {
println!("{}", unsafe {*p.add(i)});
i += 1;
}
}
Zeigerarithmetik ist ein auf einfache Zeiger beschränktes Konzept. Weder Leihgaben noch Smart-Pointer unterstützen sie. Das muss auch so sein, denn diese Typen besitzen keine Möglichkeit zur Prüfung, ob das Ergebnis einer Verschiebung im gültigen Bereich bleibt, womit per se keine Sicherheit gewährleistet werden kann.
Ausschnitt-Leihgaben bieten allerdings tatsächlich die Möglichkeit
einer Arithmetik, denn diese sind Paare aus Zeiger und Länge.
Durch Prüfung der Länge ist eine sichere Dereferenzierung
realisierbar. Die folgende Formulierung von print_array
verdeutlicht die Überlegung.
fn print_array(a: &[char]) {
let mut p = &a[..];
while !p.is_empty() {
println!("{}", p[0]);
p = &p[1..];
}
}
Hier entspricht p[0] der Dereferenzierung
und &p[1..] der Inkrementierung.
Die Daten, die ein Programm verarbeitet, müssen notgedrungen auf irgendeine Art im RAM-Speicher des Computers untergebracht werden. Dafür gibt es zwei Verfahren:
Die folgende Funktion new_data gibt ein Array
zurück, das bspw. Bilddaten eines Bildes mit Breite 480 Pixel
und Höhe 300 Pixel aufnehmen soll.
const DATA_LEN: usize = 480*300;
fn new_data() -> [u32; DATA_LEN] {
[0; DATA_LEN]
}
Nun ist der Stack in nativen Laufzeitsystemen begrenzt. Typische Werte für die Begrenzung liegen bei 1 bis 10 MB. Zwar lässt sich dies ändern, bspw. indem das Hauptprogramm in einem neuen Thread mit größerem Stack ausgeführt wird, nehmen wir aber zunächst an, dies wäre uns nicht gegeben. Wollen wir nun ein größeres Array speichern, oder ein Array von Arrays, ist der Stapel bald aufgebraucht.
Für gewöhnlich wird für solche Datenmengen stattdessen
Haldenspeicher zugewiesen. Dafür zuständig ist die Funktion
Box::new, die einen Zeiger auf den zugewiesenen
Speicher zurückgibt.
fn new_data() -> Box<[u32; DATA_LEN]> {
Box::new([0; DATA_LEN])
}
Bei einem Zeiger vom Typ Box handelt es sich um einen
sogenannten Smart-Pointer. Ein solcher zeichnet sich durch die
Eigenschaft aus, dass der Speicher automatisch wieder freigegeben wird,
sobald die Lebenszeit des Zeigerwertes endet.
Stellt man sich Zeiger als Speicheradressen vor, liegt der Gedanke
nicht fern, mehrere Zeiger auf den gleichen Wert zeigen zu lassen.
Der Typ Box schließt dies jedoch aus, weil ein Zeiger
dieses Typs der Besitzer des Wertes ist. Wir müssen uns hierzu
daran erinnern, dass die Unteilbarkeit von Besitzerschaft eine
entscheidende Eigenschaft des Typsystems ist.
Was man ohne Frage tun kann, ist die Erstellung beliebig
vieler Zeiger vom Typ &Box<T>, da diese
nur Leihgaben darstellen. Dies bringt jedoch eine Reihe von
Problemen mit sich:
Eine Lösung für die Problematik bestünde in der Benutzung eines sogenannten Arena-Allokators. Bei diesem dauert die Lebenszeit aller erstellten Werte genau so lange an wie die des Allokators. Das heißt, im Unterschied zu einem gewöhnlichen Allokator sind Freigaben nicht zu beliebigen Zeitpunkten möglich. Eines Besitzers bedarf es nicht mehr, weil die Arena der eigentliche Besitzer ist. An dieser Stelle soll nicht näher auf dieses Konzept eingegangen werden.
Eigentlich ist die Forderung nach Unteilbarkeit von Besitzerschaft zu streng. Solange einem Wert keine Veränderung widerfährt, dürfte es mehrere Zeiger auf diesen geben. Nur dann muss der Wert solange erhalten bleiben, bis der letzte Zeiger verschwunden ist. Allerdings wissen wir nicht immer, in welcher Reihenfolge die Zeiger kommen und gehen. Diesem Umstand trägt die Benutzung eines Referenzzählers Rechnung, der dem Wert hinzugefügt wird. Der Referenzzähler zählt die Anzahl vorhandener Zeiger. Bei der Erstellung eines neuen Zeigers wird dieser um eins erhöht, beim Verschwinden eines Zeigers um eins erniedrigt.
Der Mechanismus der Referenzzählung ist durch den Typ
Rc implementiert, das steht für reference counted.
So wie bei Box ist der Speicherplatz, auf den der
Zeiger zeigt, auf der Halde alloziert. Erstellt wird eine neue
Allokation mit Rc::new oder Rc::from.
Die Methode Rc::clone bewirkt gerade nicht eine
Kopie der Daten, sondern nur eine Kopie des Zeigers und entsprechend
eine Inkrementation des Referenzzählers.
Ein Beispiel zur Benutzung von Rc bieten
Ausschnitte mit Besitzerschaft. Betrachten wir zunächst
folgendes Programm.
fn main() {
let slice: &[u8] = &[0, 0, 0, 0, 1, 1, 1, 1];
let sub_slice = &slice[4..8];
println!("{:?}", sub_slice);
}
Die Ausschnitte bedingen hier Leihgaben der zugrunde liegenden
Bytesequenz. Stattdessen wollen wir nun Ausschnitte mit gemeinsamer
Besitzerschaft an der Bytesequenz haben. Um dies zu erreichen,
konstruieren wir für diese Ausschnitte den neuen Typ Slice,
dessen Eintrag data eine gezählte Referenz auf die
Bytesequenz ist.
use std::{fmt, rc::Rc, ops::Range};
struct Slice {
data: Rc<[u8]>,
start: usize,
len: usize
}
impl Slice {
fn new(data: Rc<[u8]>) -> Self {
let len = data.len();
Self {data, start: 0, len}
}
fn slice(&self, r: Range<usize>) -> Self {
let start = self.start + r.start;
let len = r.end - r.start;
Self {data: self.data.clone(), start, len}
}
}
impl fmt::Debug for Slice {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let start = self.start;
write!(f, "{:?}", &self.data[start..start+self.len])
}
}
fn main() {
let data: Rc<[u8]> = Rc::from([0, 0, 0, 0, 1, 1, 1, 1]);
let slice = Slice::new(data);
let sub_slice = slice.slice(4..8);
println!("{:?}", sub_slice);
}
Wir müssen näher darauf blicken, was hier gemacht wurde. Der Typ
&[u8] ist eigentlich über Lebenszeiten
parametrisiert, die Notation unterdrückt dies bloß. Bei der Definition
eines Aliastypen tritt die Abhängigkeit von der Lebenszeit
explizit hervor:
type BorrowSlice<'a> = &'a [u8];
Im Typ Slice ist diese Parametrisierung verloren
gegangen. Der Typ Slice ist demnach nicht mehr von
der Lebenszeit eines anderen Datums abhängig.
Brauchbar ist Rc auch zur Erzeugung von Symbolen.
Unter einem Symbolvorrat wollen wir schlicht einen Wertebereich
verstehen, dessen Elemente schnell zu kopieren und zu vergleichen
sind. Ist der Symbolvorrat bereits zur Kompilierzeit bekannt, würde man
diesen als Enumeration darstellen. Ist der Vorrat allerdings erst
zur Laufzeit bekannt, muss man sich eine andere Darstellung überlegen.
Eine Idee ist die Darstellung von Symbolen als Zeiger. Zwei
Symbole sind genau dann gleich, wenn die Zeiger auf dasselbe
Objekt zeigen. Demnach wird mit Rc::new einmalig ein
neues Symbol erzeugt, das irgendwo in der Laufzeitumgebung oder
einer zugänglichen Datenstruktur hinterlegt werden muss. Von diesem
lassen sich nun mit Rc::clone beliebig viele Kopien
anfertigen. Zum Vergleich zweier Symbole wird Rc::ptr_eq
genutzt.
use std::rc::Rc;
fn main() {
let a = Rc::new(());
let b = a.clone();
assert!(Rc::ptr_eq(&a, &b));
}
Durchaus bestehen noch andere Wege zur Darstellung von Symbolen. Effizient ist bspw. ein Zähler in der Laufzeitumgebung. Zur Erzeugung eines neuen Symbols wird das Symbol als Zählerwert dargestellt und der Zähler zudem inkrementiert, womit garantiert ist, dass jedes mal ein neues, einmaliges – d. h. zu allen anderen verschiedenes – Symbol geschaffen wird.
Allerdings bietet Rc zusätzlich die Möglichkeit,
Symbole mit einem Namen zu versehen. Zu beachten ist hierbei,
dass unterschiedliche Symbole den gleichen Namen tragen
dürfen, was zur Verwirrung führen kann.
use std::rc::Rc;
fn main() {
let a: Rc<str> = Rc::from("A");
let b = a.clone();
assert!(Rc::ptr_eq(&a, &b));
println!("{}", a);
}
Zur Bemerkung sei noch erwähnt, dass Rc::ptr_eq
bei Rc<str> sowohl den Zeiger als auch die
Länge vergleicht. Effizienter ist für unseren Zweck der reine
Vergleich der Zeiger. Dies wird durch die folgende
Funktion ptr_eq_plain erreicht.
fn ptr_eq_plain<T: ?Sized>(p: &Rc<T>, q: &Rc<T>) -> bool {
let p = &**p as *const T as *const ();
let q = &**q as *const T as *const ();
std::ptr::eq(p, q)
}
Wie man Symbole im Zusammenhang mit Hashtabellen benutzt, wurde im Abschnitt ›Behälter: Hashtabellen: Äquivalenz per Zeigervergleich‹ schon erläutert.
Der Typ Rc gewährt nur gemeinsame Referenzen, womit
die Daten darunter unveränderlich bleiben. Infolge liegt die gesamte
Datenstruktur immerwährend fest wie ein Kristall. Einem gleichartigen
Problem steht man auch in anderen Situationen gegenüber, –
überall dort, wo man nur gemeinsame Referenzen bekommt. Dem Ziel
der Programmierung von dynamischen Datenstrukturen läuft diese
Einschränkung offensichtlich zuwider. Zur Auflösung dieser
Einschränkung stehen daher ausgeklügelte Mechanismen zur Verfügung.
Erinnern wir uns daran, dass bei gemeinsamen Referenzen Veränderungen an den Daten verboten sind, weil es sonst zu Aliasing und Use after free kommen kann. Einen Teil der Daten unter einer gemeinsamen Referenz wollen wir nun dennoch verändern dürfen. Angenommen, wir verbieten Zeiger auf diesen Teil, womit dieser Teil nur als Ganzes gelesen und geschrieben werden darf, dann dürfte es niemals zu den genannten Problemen kommen.
Mit der technischen Ausgestaltung dieser Idee ist der Typ
Cell entstanden. Einen Zeiger auf das Innere eines
Wertes dieses Typs kann man nicht bekommen. Lediglich ist es gestattet,
die Zelle mit der Methode Cell::get gänzlich zu
lesen oder mit Cell:set gänzlich zu schreiben.
Außerdem gibt es noch ein paar Hilfsmethoden zum flexibleren
Ausreizen der zugrundeliegenden Idee.
Eine Anwendung von Cell zeigt die folgende
Implementierung eines Zählers, der sich auch dann verändern
darf, wenn man nur »veränderungslosen« Zugriff auf ihn hat.
use std::{rc::Rc, cell::Cell};
struct Counter {
value: Cell<u32>
}
impl Counter {
fn new() -> Self {
Self {value: Cell::new(0)}
}
fn next(&self) -> u32 {
let value = self.value.get();
self.value.set(value + 1);
value
}
}
fn main() {
// Scheinbar absurd: Veränderung hinter einer
// gemeinsamen Referenz.
let counter = &Counter::new();
println!("{}", counter.next());
println!("{}", counter.next());
// Entsprechend erlaubt.
let counter = Rc::new(Counter::new());
println!("{}", counter.next());
println!("{}", counter.next());
}
Zu Produkttypen wie Strukturen, Tupeln und Feldern gehören Projektionen auf ihre Elemente. Zum Zugriff über Leihgaben muss hierbei auch die Projektion über Leihgaben formuliert sein. Für Ausschnitte ist die Projektion so definiert:
fn proj<T>(a: &[T], i: usize) -> &T {
&a[i]
}
Entsprechend ist definiert:
fn proj_mut<T>(a: &mut [T], i: usize) -> &mut T {
&mut a[i]
}
Nun lässt sich zu jedem Typ T der Typ
&mut T als in einer Subtyp-ähnlichen Beziehung zu
&Cell<T> betrachten. Die Rolle des Upcasts
nimmt hierbei Cell::from_mut mit der Signatur
fn from_mut(t: &mut T) -> &Cell<T>
ein. Speziell können wir &mut [T] in
&Cell<[T]> umwandeln. Nun würden wir den
Ausschnitt gerne indizieren. Das heißt, wir brauchen nicht den
Zugriff auf den Ausschnitt als Ganzes, sondern die Projektionen
auf dessen Elemente. Das notwendige Hilfsmittel dafür ist die Methode
as_slice_of_cells, die &Cell<[T]>
weiter in &[Cell<T>] umwandelt.
Der Nutzen liegt darin, gleichzeitig mit Zeigern über ein Feld iterieren zu können, während dessen Elemente modifiziert werden. Betrachten wir bspw. die folgende Implementierung von Buble sort.
fn bubble_sort<T: Ord>(a: &mut [T]) {
let n = a.len();
for _ in 0..n {
for i in 1..n {
if a[i] < a[i-1] {a.swap(i, i-1);}
}
}
}
Bei der Indizierung tritt für gewöhnlich eine Bereichsprüfung auf. Manchmal sieht sich der Compiler auch in der Lage, diese während der Optimierung zu entfernen. Ein alternativer Weg ist die Benutzung von Zeigern anstelle von Indizes. Wir würden gerne schreiben:
fn bubble_sort<T: Ord>(a: &mut [T]) {
for _ in 0..a.len() {
let mut y = &mut a[0];
for x in &mut a[1..] {
if x < y {std::mem::swap(x, y);}
y = x;
}
}
}
Jedoch ist dieses Programm nicht kompilierbar, weil zwei alleinige Leihgaben des gleichen Ausschnitts verboten sind. Der beschriebene Formalismus eröffnet nun eine Formulierung, bei welcher stattdessen gemeinsame Leihgaben auftreten.
use std::cell::Cell;
fn bubble_sort<T: Ord + Copy>(a: &mut [T]) {
let a = Cell::from_mut(a).as_slice_of_cells();
for _ in 0..a.len() {
let mut y = &a[0];
for x in &a[1..] {
if x.get() < y.get() {Cell::swap(x, y);}
y = x;
}
}
}
Ein praktischeres Beispiel bietet die folgende Implementierung
von Vec::retain.1
Da das Prädikat für die Betrachtung nicht wesentlich ist,
sei es zur Vereinfachung auf is_even festgelegt.
Die Formulierung mit Indizierung:
fn retain_even(a: &mut Vec<i32>) {
let mut i = 0;
for j in 0..a.len() {
if is_even(a[j]) {
a[i] = a[j];
i += 1;
}
}
a.truncate(i);
}
Die Formulierung mit einem Zeiger:
use std::cell::Cell;
fn retain_even(a: &mut Vec<i32>) {
let s = Cell::from_mut(&mut a[..]).as_slice_of_cells();
let mut i = 0;
for x in s.iter().filter(|x| is_even(x.get())) {
s[i].set(x.get());
i += 1;
}
a.truncate(i);
}
Leider ist Cell nur für kleine Typen mit Trait
Copy effizient, womit Cell auf
spezielle Situationen beschränkt bleibt. Ein allgemeiner
Mechanismus liegt mit RefCell vor. So wie
Cell gewährt eine Zelle vom Typ RefCell
Veränderungen innerhalb von gemeinsamen Leihgaben. Im Unterschied
zu Cell erlaubt RefCell das
eigentlich Verbotene – eine alleinige Leihgabe eines Teils
einer gemeinsamen Leihgabe.
Wie kann das möglich sein? Der Compiler verhindert Aliasing
normalerweise, indem zur Kompilierzeit geprüft wird, dass für
Veränderungen immer nur eine einzige alleinige Leihgabe vorhanden ist.
Der Mechanismus von RefCell besteht nun gerade darin,
diese Prüfung stattdessen zur Laufzeit vorzunehmen, womit wir einen
großen Sprung an Flexibilität gewinnen. Zur Umsetzung fügt
RefCell<T> dem Wert des Typs T
einen Referenzzähler hinzu. Man kann dann mit borrow
beliebig viele gemeinsame Leihgaben bekommen, oder mit
borrow_mut eine alleinige Leihgabe. Die technische
Umsetzung kann man so konstruieren:
borrow wird der Referenzzähler um eins
erhöht, aber nur falls er nicht-negativ ist. Andernfalls kommt
es zum Programmabbruch.
borrow_mut wird der Referenzzähler auf −1
erniedrigt, aber nur falls er null war. Andernfalls kommt es
zum Programmabbruch.
Es folgt ein erstes einfaches Beispiel, – die Implementierung
des bereits zuvor beschriebenen Zählers Counter, aber
dieses Mal mit RefCell anstelle von Cell.
use std::cell::RefCell;
struct Counter {
value: RefCell<u32>
}
impl Counter {
fn new() -> Self {
Self {value: RefCell::new(0)}
}
fn next(&self) -> u32 {
let mut p = self.value.borrow_mut();
let value = *p;
*p = value + 1;
value
}
}
Die Methoden borrow und borrow_mut
besitzen die totalen Pendants try_borrow und
try_borrow_mut, die Rückgabe vom Typ Result
haben, anstelle mit panic den Programmabbruch
einzuleiten.
Die folgende Anwendung zeigt eine Funktion, die bestimmt ob ein Graph mindestens einen Zyklus enthält. Die Überlegung dazu ist eigentlich recht einfach. Man schreibt naiv die rekursive Traversierung des Graphen, als wäre es ein Baum oder ein gerichteter azyklischer Graph. Ein Zyklus ist genau dann vorhanden, wenn das Programm beim Traversieren auf einen bereits zuvor ausgeliehenen Knoten trifft.
use std::{rc::Rc, cell::RefCell};
type RcNode = Rc<RefCell<Node>>;
struct Node {
data: i32, links: Vec<RcNode>
}
impl Node {
fn new(data: i32, links: Vec<RcNode>) -> RcNode {
Rc::new(RefCell::new(Node {data, links}))
}
}
fn is_cyclic(graph: &RcNode) -> bool {
if let Ok(node) = graph.try_borrow_mut() {
for link in &node.links {
if is_cyclic(link) {return true}
}
false
} else {
true
}
}
Einige Algorithmen besitzen hinsichtlich alleinigen Leihgaben
eine gewissen Komplexität, so dass es sich schwierig gestalten
kann, eine Formulierung zu finden, die vom Leihgabe-Prüfer
durchgewunken wird. Weiß man sich nicht anders zu helfen,
kann man das Programm mit RefCell letztendlich
aus dieser Problematik entziehen.
Betrachten wir dazu die folgende Implementierung eines abstrakten Stapels.
use std::{rc::Rc, cell::RefCell};
fn new_stack<T>() -> (impl Fn(T), impl Fn() -> Option<T>) {
let a = Rc::new(RefCell::new(vec![]));
let b = a.clone();
(move |x| a.borrow_mut().push(x), move || b.borrow_mut().pop())
}
fn main() {
let (push, pop) = new_stack();
push(1);
push(2);
println!("{:?}, {:?}, {:?}", pop(), pop(), pop());
}
Die Benutzung von Rc ist hierbei nicht wesentlich.
Eine Umformulierung, bei welcher der Speicher in einer extra Variable
gehalten wird, kommt auch ohne Rc aus.
use std::cell::RefCell;
struct Stack<T>(RefCell<Vec<T>>);
impl<T> Stack<T> {
fn new() -> Self {
Stack(RefCell::new(vec![]))
}
fn methods<'a>(&'a self)
-> (impl 'a + Fn(T), impl 'a + Fn()->Option<T>)
{
(move |x| self.0.borrow_mut().push(x),
move || self.0.borrow_mut().pop())
}
}
fn main() {
let stack = Stack::new();
let (push, pop) = stack.methods();
push(1);
push(2);
println!("{:?}, {:?}, {:?}", pop(), pop(), pop());
}
In einem nicht-nebenläufigen Programm sind die Funktionsaufrufe
zudem sequenziell, so dass push und pop
niemals gleichzeitig auf den Stapel zugreifen. Allerdings sind alleinige
Leihgaben nicht kopierbar, womit uns die Erstellung beider Closures
ohne RefCell verwehrt bliebe. Um auszudrücken dass die
Leihgaben nur abwechselnd stattfinden, bliebe uns nichts anderes übrig,
als den Stapel aus dem Closure herauszunehmen und auf die übliche
Art als Argument an die Methoden zu übergeben.
Ein gewöhnlicher Typ besitzt eine feste Größe, d. h. dessen
Werte belegen im Speicher eine feste Zahl von Bytes. Zur
Ermittlung der Größe eines Typs steht die Funktion
size_of zur Verfügung.
use std::mem::size_of;
fn main() {
println!("{}", size_of::<u8>());
}
Es gibt in Rust jedoch auch Typen ohne feste Größe.
Ein Beispiel dafür ist [u8], bei dem die Abfrage
size_of::<[u8]>()
entsprechend verwehrt bleibt. Werte von solchen Typen sind nicht
direkt verwendbar, sondern erfordern Zeiger. Bspw. ist
[u8] als &[u8] oder
Box<[u8]> verwendbar.
Sei DST – das steht für dynamically sized
type – ein Typ dynamischer Größe. Man darf zu diesem
die folgenden Typen konstruieren, welche infolge ebenfalls von
dynamischer Größe sind:
struct S(DST).
DST enthalten ist.
Die basalen Typen dynamischer Größe sind die folgenden:
| Typ | Erklärung |
|---|---|
[T]
| Ausschnitt eines Feldes vom Typ T
|
dyn Trait
| Typ des Trait-Objektes vom Trait Trait
|
Die Standardbibliothek enthält unter anderem die folgenden Konstruktionen:
| Typ | Konstruktion |
|---|---|
str
| (1) von [u8] — wird allerdings als primitiver Typ gehandhabt
|
OsStr
| (1) von [u8] — allerdings ein Implementationsdetail
|
Path
| (1) von OsStr
|
RefCell<DST>
|
Die folgenden Zeiger-Typen wandeln einen Typ dynamischer Größe in einen Typ fester Größe um, wobei zu beachten ist, dass dabei ein dicker Zeiger entsteht. Dicke Zeiger kommen in zwei Varianten vor. Bei einem Ausschnitt entsteht ein Paar aus Zeiger und Länge, bei Trait-Objekt-Typen ein Paar aus Zeiger und Zeiger auf die Dispatch-Tabelle.
| Typ | Kommentar |
|---|---|
*const DST | einfacher Zeiger auf unveränderbare Daten |
*mut DST | einfacher Zeiger auf veränderbare Daten |
&'a DST | gemeinsame Leihgabe |
&'a mut DST | alleinige Leihgabe |
Box<DST> | besitzender Zeiger |
Rc<DST> | Referenz-gezählter Zeiger |
Arc<DST> | atomar Referenz-gezählter Zeiger |
In einigen Situationen bekommt eine Prozedur lediglich eine
alleinige Leihgabe eines Eintrages oder Elementes, ohne den Besitz
darüber zu erlangen. Dennoch erreichbar ist vermittels Ersetzung die
Übertragung des Wertes an einen anderen Besitzer. Möglich gemacht
wird dies durch die Funktion replace, die einen anderen
Wert anstelle des ursprünglichen Wertes einsetzt. Notwendig ist
das, weil die Speicherzelle andernfalls ungültig wäre wie eine
uninitialisierte Variable es ist. Dieser Zustand darf nicht sein,
weil die Speichersicherheit in Konsequenz nicht mehr
gewährleistet wäre.
Die Funktion hat die Signatur
fn replace<T>(dest: &mut T, src: T) -> T.
Sie gibt den begehrten Wert von dest
(destination, dt. Ziel) zurück und fügt dafür den Wert
von src (source, dt. Quelle) in
dest ein.
Einfaches Beispiel:
fn main() {
let s1 = &mut String::from("Tee");
let s2 = std::mem::replace(s1, String::new());
println!("s1 = '{}', s2 = '{}'", s1, s2);
}
Im Beispiel wurde der Wert von s1 gegen einen
Dummy-Wert ersetzt, das ist oft eine leere Datenstruktur.
Bemerkenswert ist hierbei, dass die Erzeugung von leeren Dummy-Werten
wie String::new() oder Vec::new()
keiner Allokation von Haldenspeicher bedarf, womit
replace recht flott bleibt.
Weil die Einsetzung von Dummy-Werten recht oft vorkommt, wurde
dafür extra die Komfort-Funktion take geschaffen.
Es ist so, dass String::new() der Vorgabewert
des Typs String ist. Man kann für jeden neuen
Typ durch Implementierung des Traits Default einen
frei wählbaren Vorgabewert erzeugen lassen. So wie
replace beschafft take den begehrten Wert,
fügt an dessen Stelle aber den Vorgabewert ein. Die Implementierung
von take ist denkbar einfach:
fn take<T: Default>(dest: &mut T) -> T {
replace(dest, T::default())
}
Äquivalent zum dargestellten Beispiel ist daher:
fn main() {
let s1 = &mut String::from("Tee");
let s2 = std::mem::take(s1);
println!("s1 = '{}', s2 = '{}'", s1, s2);
}
Manchmal liegt ein Typ vor, für den es keinen Dummy-Wert gibt, oder
für den dessen Erzeugung zu Aufwändig wäre. Eine Notlösung besteht
dann darin, den Wert in einer Option einzuhüllen,
denn für Option ist immer der Wert None
als effizienter Dummy verfügbar. Erwartungsgemäß ist None
zudem der Vorgabewert von Option.
Ersetzung macht es außerdem möglich, Typen ohne Trait
Copy in Cell einzuhüllen. Allerdings ist
dies verglichen mit RefCell nicht unbedingt vorteilhaft,
denn zur Modifikation müsste man den Wert erst raus- und dann wieder
reinschieben. Und nicht vergessen: Zudem braucht es dafür
einen effizient erzeugbaren Dummy.
Spitzfindigen wird umgehend auffallen, dass bei
Cell eine separate Ausführung von replace
gebraucht wird. Nämlich um die Hülle abzustreifen, denn andernfalls
bräuchte man für mem::replace eine alleinige Leihgabe
des Inneren von Cell, die es ja nicht geben darf.
use std::cell::Cell;
fn main() {
let s1 = Cell::new(String::from("Tee"));
let s2 = s1.replace(String::new());
println!("{}", s2);
}
Die Komfort-Funktion take ist auch mit dabei.
Anstelle s1.replace(String::new()) darf man
s1.take() schreiben.
Gelegentlich notwendig ist die Vertauschung von Werten,
bspw. bei Sortier-Algorithmen. Zwar ist die Vertauschung der
Ersetzung ähnlich, im Unterschied zu dieser kann sie jedoch auch
ohne Dummy-Werte vorgenommen werden. Hat man Besitz, könnte man eine
Vertauschung von Werten mit einer Hilfsvariable h
vornehmen. Betrachten wir dazu die Vertauschung der Komponenten
eines Paares:
fn main() {
let mut t = (String::from("Tag"), String::from("Nacht"));
let h = t.0;
t.0 = t.1;
t.1 = h;
println!("{:?}", t);
}
In vielen Situationen hat man nun wieder keinen Besitz des Wertes, sondern nur eine alleinige Leihgabe an diesem. Wir brauchen nur die Zeile
let mut t = (String::from("Tag"), String::from("Nacht"));
zu
let t = &mut (String::from("Tag"), String::from("Nacht"));
abändern, und schon verweigert sich der Compiler. Eine Möglichkeit
zur Umgehung der Problematik ist replace. Wir gelangen
zu dieser Formulierung:
fn main() {
let t = &mut (String::from("Tag"), String::from("Nacht"));
let h = std::mem::take(&mut t.0);
t.0 = std::mem::replace(&mut t.1, h);
println!("{:?}", t);
}
Lieber würden wir take vermeiden und
fn main() {
let mut t = (String::from("Tag"), String::from("Nacht"));
t.0 = std::mem::replace(&mut t.1, t.0);
println!("{:?}", t);
}
schreiben. Bei der Leihgabe geht das allerdings ebenfalls nicht.
Aufgrund der beschriebenen Problematik und zur Erhöhung der Effizienz
wurde daher die Funktion swap geschaffen, mit der wir
die vernünftige Formulierung
fn main() {
let t = &mut (String::from("Tag"), String::from("Nacht"));
std::mem::swap(&mut t.0, &mut t.1);
println!("{:?}", t);
}
erhalten.
Die Funktion swap stellt sogar eine Verallgemeinerung
von replace dar, denn replace lässt
sich mit swap ausdrücken:
fn replace<T>(dest: &mut T, mut src: T) -> T {
std::mem::swap(dest, &mut src);
src
}
Hin und wieder kommt eine Situation vor, wo bestimmte Werte eines Definitionsbereichs auf andere abgebildet werden, ein Großteil hingegen unverändert bleibt. Betrachten wir dazu die Funktion
fn replace_hyphen(s: &str) -> String {
s.replace("-", "_")
}
die Bindestriche in Zeichenketten gegen Unterstriche ersetzt. Bei der Anwendung dieser Funktion findet in jedem Fall eine Speicherallokation und eine Kopie der Daten statt, auch dann wenn die Kette keine Bindestriche enthält. Nun sind Allokationen und Kopien ineffizient, und daher möglichst zu vermeiden. Es wäre also schön, wenn die Funktion das unterlassen würde, solange es nicht notwendig ist.
Bewerkstelligen tut dies der Typ Cow, der den
Mechanismus Copy-On-Write implementiert, oder genau
genommen Clone-On-Write. Die erste ist die allgemeine
Bezeichnung, die zweite ein Rust-spezifischer Terminus, der
aus der Unterscheidung zwischen Clone und
Copy entspringt.
Mit Hilfe von Cow gelingt die
gewünschte Adaptierung von replace_hyphen.
use std::borrow::Cow;
fn replace_hyphen(s: &str) -> Cow<str> {
if let Some(_) = s.find('-') {
Cow::from(s.replace("-", "_"))
} else {
Cow::from(s)
}
}
fn cow_variant(s: &Cow<str>) -> &'static str {
if let Cow::Owned(_) = s {"Owned"} else {"Borrowed"}
}
fn main() {
let a = ["Suppe", "Kartoffel-Brokkoli-Suppe"];
for s in &a {
let s = replace_hyphen(s);
println!("{} ({})", s, cow_variant(&s));
}
}
Die Ausgabe:
Suppe (Borrowed) Kartoffel_Brokkoli_Suppe (Owned)
Der Mechanismus von Cow ist eigentlich kein
großes Geheimnis. Zur Unterscheidung von Borrowed
und Owned dient schlicht eine Enumeration, deren
Nachbildung ohne weitere Umstände machbar ist:
#[derive(Debug)]
enum CowStr<'a> {
Borrowed(&'a str),
Owned(String)
}
fn replace_hyphen(s: &str) -> CowStr {
if let Some(_) = s.find('-') {
CowStr::Owned(s.replace("-", "_"))
} else {
CowStr::Borrowed(s)
}
}
fn main() {
let a = ["Suppe", "Kartoffel-Brokkoli-Suppe"];
for s in &a {
let s = replace_hyphen(s);
println!("{:?}", s);
}
}
Verliert ein Wert sämtliche seiner Besitzer, wird dieser schließlich
verworfen. Bei Smart-Pointern wie Box und Rc
wird der vom Wert belegte Speicher hierbei automatisch
freigegeben.
Genau genommen ist jedem Typ je nach seiner Struktur ein
Destruktor zugeordnet. Zum Einen ist in diesem ein vom Compiler
automatisch erzeugter Code enthalten, welcher die entsprechenden
Destruktoren der Bestandteile aufruft. Zum Anderen kann man diesem
Code zusätzliche Funktionalität voranstellen, indem
der Trait Drop implementiert wird.
Bei lokalen Variablen findet der Destruktor-Aufruf statt, sobald die Variable out of scope geht, d. h. ihr lexikalischer Bereich endet. Betrachten wir dazu dieses Programm:
struct Duck {name: String}
impl Duck {
fn dive(&self) {
println!("{} taucht.", self.name);
}
}
impl Drop for Duck {
fn drop(&mut self) {
println!("{} fliegt davon!", self.name);
}
}
fn main() {
let duck = Duck {name: String::from("Donald")};
duck.dive();
println!("Programm endet.");
}
Die Ausgabe ist:
Donald taucht. Programm endet. Donald fliegt davon!
Man kann einen vorzeitigen Destruktor-Aufruf durch
Besitzübergabe an mem::drop erzwingen:
fn main() {
let duck = Duck {name: String::from("Donald")};
duck.dive();
std::mem::drop(duck);
println!("Programm endet.");
}
Oder durch Einschließung des Programmteils in einen kürzeren Bereich:
fn main() {
{
let duck = Duck {name: String::from("Donald")};
duck.dive();
}
println!("Programm endet.");
}
Die Ausgabe ist dann von dieser Reihenfolge:
Donald taucht. Donald fliegt davon! Programm endet.
Auch Smart-Pointer-Typen wie Rc besitzen einen
Destruktor. Bei Rc übernimmt drop die
Dekrementierung des Referenz-Zählers. Der Aufruf des Destruktors der
eigentlichen Daten findet hierbei erst dann statt, wenn der
Referenz-Zähler den Wert null erreicht.
Die freistehende Funktion mem::drop ist streng von
der Methode drop zu unterscheiden. Während
mem::drop ihr Argument aufisst und dadurch den
vollen Destruktor ausführt, enthält die Methode
drop nur die zusätzliche Funktionalität, die lediglich
einen Teil des Destruktors darstellt.
Statische Variablen müssen normalerweise bei ihrer Einführung initialisiert werden. Unter Umständen ist dies jedoch unmöglich oder ineffizient. Betrachten wir zunächst die folgende statische Tabelle, die dem Symbol eines chemischen Elements seine Ordnungszahl zuordnet.
static ELEMENTS: &[(&'static str, u32)] = &[
("B", 5), ("Be", 4), ("C", 6), ("F", 9), ("H", 1),
("He", 2), ("Li", 3), ("N", 7), ("Ne", 10), ("O", 8)
];
fn atomic_number(symbol: &str) -> u32 {
match ELEMENTS.binary_search_by_key(&symbol, |&(x, _)| x) {
Ok(index) => ELEMENTS[index].1,
_ => panic!("symbol {} not found", symbol)
}
}
fn main() {
println!("{}", atomic_number("H"));
}
Wir würden die binäre Suche gern gegen eine Hashtabelle ersetzen dürfen. Man steht dabei jedoch vor dem Problem, dass die Initialisierung einer Hashtabelle dafür als konstante Funktion formulierbar sein müsste, was unmöglich ist.
Eine Umgehung dieses Problems ermöglichen die Zellen vom Typ
OnceLock. Sie machen es durchführbar, die Initialisierung
einer statischen Variable bis zu dem Punkt der Ausführung
des Programms zu verzögern, wo sie das erste Mal gelesen wird.
use std::sync::OnceLock;
use std::collections::HashMap;
type Elements = HashMap<&'static str, u32>;
fn elements() -> &'static Elements {
static ELEMENTS: OnceLock<Elements> = OnceLock::new();
ELEMENTS.get_or_init(|| {
HashMap::from([
("H", 1), ("He", 2), ("Li", 3), ("Be", 4), ("B", 5),
("C", 6), ("N", 7), ("O", 8), ("F", 9), ("Ne", 10)
])
})
}
fn main() {
let atomic_number = elements();
println!("{}", atomic_number["H"]);
}