Unsafe Rust
Concepts
Les concepts abordés dans cet exemple sont:
Une partie des exemples sont très fortement inspirés ou même tirés de l'excellent livre Learn Rust With Entirely Too Many Linked Lists. Je vous recommande d'ailleurs le blog de l'auteure Aria Beingessner aka Gankra.
Discussion
Le Rust est un langage avec des contraintes de sécurité mémoire très fortes et un compilateur pointilleux.
Il possède donc des règles très strictes qui ne sont pas toujours applicables pour avoir un
code sûr et ergonomique. Ses créateurs·trices ont donc pensé à laisser la possibilité
de relaxer les contraintes dans un environnement particulier: le unsafe Rust.
Pour plus d'informations et une description plus complète, vous pouvez vous référer:
- À la section 19.1 du livre.
- Au Rustonomicon.
Pour illustrer les concepts unsafe, nous allons discuter de l'une des structures de données
les plus "simples" de l'informatique, mais qui est très difficile à implémenter en Rust: la liste simplement chaînée.
Une discussion très détaillée de l'implémentation de la liste chaînée se trouve sur
l'excellent Learn Rust With Entirely Too Many Linked Lists.
Rappelez vous également que la liste simplement chaînée est une structure de donnée permettant de représenter
une pile (structure de donnée abstraite bien connue).
Pour commencer, nous allons voir son implémentation sûre, et les efforts qu'il faut consentir pour faire l'implémentation,
puis une implémentation unsafe ou pas sûre.
La liste chaînée
Pour simplifier, nous allons nous limiter à l'implémentations de 6 fonctionnalité dans notre liste chaînée:
- La fonction
new()qui crée une nouvelle liste. - La fonction
is_empty()qui nous dit si la liste est vide. - La fonction
push()qui ajoute un élément en tête de liste. - La fonction
pop()qui retire l'élément de tête de la liste et retourne la valeur stockée. - La fonction
print()qui affiche tous les éléments de la liste.
Avant de voir l'implémentation de ces fonctions, nous devons définir la structure de données utilisée pour la liste chaînée. Pour rappel, une liste chaînée est une suite de nœuds ou éléments qui sont reliés entre eux par des pointeurs:
val1 --> val2 --> val3 --> fin
Ainsi chaque élément contient les données et un pointeur vers l'élément suivant. En Rust, on serait donc tenté de faire
#![allow(unused)] fn main() { struct Element { data: i32, next: Element, } }
Comme pour le C cette construction ne peut pas fonctionner, car nous avons à faire à un type récursif et dont on ne peut connaître la taille à la compilation.
error[E0072]: recursive type `Element` has infinite size
--> src/main.rs:3:1
|
3 | struct Element {
| ^^^^^^^^^^^^^^
4 | data: i32,
5 | next: Element,
| ------- recursive without indirection
|
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
|
5 | next: Box<Element>,
| ++++ +
For more information about this error, try `rustc --explain E0072`.
error: could not compile `playground` (bin "playground") due to previous error
Ainsi, comme nous le recommande le compilateur, il faut utiliser un Box (voir le chapitre 10) pour faire une allocation sur le tas de next.
#![allow(unused)] fn main() { struct Element { data: i32, next: Box<Element>, } }
Nous ne sommes pas encore sortis d'affaire, car notre type élément ne permet pas de représenter la fin de la chaîne. Il faudrait que
next soit un élément suivant soit pas d'élément suivant (indiquant ainsi la fin de la chaîne). Mais on connaît un tel type non?
Le type Option<T> (voir le chapitre 7) fait exactement ce que nous voulons: la variante Some(element) indique la présence
d'un élément suivant, alors que la variante None indique son absence.
#![allow(unused)] fn main() { struct Element { data: i32, next: Option<Box<Element>>, } }
Il ne nous reste plus qu'à créer la structure de liste chaînée, qui va juste avoir la forme suivante:
pub struct LinkedList {
head: Option<Box<Element>>,
}Et juste posséder la tête de la liste chaînée.
La philosophie générale de l'implémentation purement safe de la liste chaînée est qu'on ne va jamais emprunter les instances de la liste chaînée, mais toujours
en prendre la propriété. Cela aura des effets non négligeables sur l'ergonomie du code (qui n'est pas forcément nécessaire), mais que l'on accepte à des fins éducatives.
La fonction associée new()
La fonction new() est triviale à écrire
pub fn new() -> Self {
Self { head: None }
}Il faut juste noter que new() retourne une nouvelle instance de LinkedList dont la tête est None (il n'y a aucun élément dans la liste).
La méthode is_empty()
La méthode is_empty() est un poil moins triviale à écrire. Pour déterminer si la liste est vide, il faut juste vérifier que que l'instance
de la liste chaînée à head soit égale à None. On peut faire cela avec du pattern matching
match self.head {
None => true,
_ => false,
}Mais cela ne suffit pas complètement, car il faut également retourner self (l'instance de la liste chaînée sinon elle serait détruite à la fin de is_empty()).
Ainsi on retourne non seulement le booléen qui nous dit si la liste est vide ou non, mais également la list (self).
En fait, on peut faire beaucoup plus court et pratique en utilisant la
méthode is_none() de la librairie standard de Rust. Mais cela reviendrait à
emprunter self ce qui contreviendrait au principe qu'on s'est fixé pour cette implémentation
un peu étrange.
pub fn is_empty(self) -> (bool, Self) {
match self.head {
None => (true, self),
_ => (false, self),
}
}La méthode push()
La fonction push(value) doit créer un élément à placer en tête de liste qui aura comme next l'ancienne tête de liste.
Il y a différentes façons de l'implémenter. Ici, nous allons prendre possession de l'instance de la liste, et retourner
une nouvelle liste avec le nouvel élément ajouté
pub fn push(self, data: i32) -> Self {
let elem = Box::new(Element::new(data, self.head));
Self { head: Some(elem) }
}Dans cette implémentation on voit que self est "move" dans la fonction push (on prend en argument self et non &self ou &mut self). Puis ont crée un nouvel élément
contenant data et la tête actuelle de la liste. Le nouvel élément elem a donc
la propriété de la mémoire de self.head.
La fonction pop()
La fonction pop()
pub fn pop(self) -> (Option<i32>, Self) {
if let Some(elem) = self.head {
(Some(elem.data), Self { head: elem.next })
} else {
(None, Self { head: None })
}
}retourne une Option<i32> avec éventuellement une valeur si la liste n'est pas vide, et retourne une nouvelle liste où la tête
est soit l'élément suivant soit une liste vide (si on est à la fin de la liste).
Il faut noter la syntaxe if let Some(elem) = self.head ... else qui permet de se passer
du pattern matching et raccourcir sensiblement le code.
La fonction print()
Finalement, la fonction print() est probablement la plus étrange de toutes.
pub fn print(self) -> Self {
let mut new_list = Self::new();
let mut current = self.head;
while let Some(tmp) = current {
print!("{} --> ", tmp.data);
new_list = new_list.push(tmp.data);
current = tmp.next;
}
println!("∅");
new_list
}En effet, on aimerait ne pas avoir à détruire notre liste en entier lorsque nous la parcourons.
Ainsi, la fonction print() prend en argument self et retourne Self.
Cette fonction va créer une nouvelle instance de LinkedList mutable,
puis parcourir tous les éléments de la liste self à l'aide de la boucle
let mut current = self.head;
while let Some(tmp) = current {
print!("{} --> ", tmp.data);
new_list = new_list.push(tmp.data);
current = tmp.next;
}
println!("∅");où on va parcourir la liste en "consommant" les éléments: lors de l'assignation
de current à tmp.next, l'ancienne valeur de current sort de la portée et est détruite automatiquement. Ainsi, il est nécessaire de push() la valeur tmp.data
sur la liste nouvellement créée précédemment new_list. Dans la boucle, nous affichons
également chaque valeur avec un formatage astucieux. Finalement,
nous retournons la nouvelle liste.
Les défauts de cette implémentation
On constate tout d'abord que cette implémentation n'est pas très ergonomique.
En effet, à chaque utilisation de la liste, il faut toujours faire un assignation
à une nouvelle liste ce qui est encore acceptable pour push(). En revanche pour
pop() ou print() on voit clairement que c'est pas pratique du tout.
Un autre problème plus complexe apparaît et concerne la libération de la mémoire
de notre liste chaînée. Il s'avère que la libération automatique est impossible
à faire en garantissant qu'on ne va pas faire exploser la pile. Comme expliqué
sur ce lien
la libération de la mémoire se fait de façon récursive. Ainsi, on n'a aucune garantie
que la pile d'appel de la fonction de libération de la mémoire (drop()) par le compilateur
ne va pas dépasser sa capacité.
fn main() {
// Exemple de stack overflow
let mut immutable_list = ImmutableList::new();
for i in 0..1_000_000 {
immutable_list = immutable_list.push(i);
}
}Si vous compilez et exécutez ce programme, vous constaterez probablement une erreur de type stack overflow.
Vous me direz qu'il suffit d'implémenter le trait Drop comme dans "Too many linked
lists..." mais... cela ne fonctionne pas non plus pour des raisons trop complexes à
expliquer ici. La seule solution est d'implémenter une fonction vidant la liste et de l'appeler à la main et perd un peu la raison d'être du Rust.
pub fn clear(self) {
let mut current = self.head;
while let Some(tmp) = current {
current = tmp.next;
}
}
fn main() {
// Exemple de stack overflow
let mut immutable_list = ImmutableList::new();
for i in 0..1_000_000 {
immutable_list = immutable_list.push(i);
}
immutable_list.clear();
}Le Rust unsafe
Tous les efforts du chapitre précédent peuvent être largement évités
avec un tout petit peu de Rust unsafe. Le Rust un peu moins sûr
nous permet de relaxer certaines contraintes du compilateur et d'écrire un code
plus joli tout en annotant les régions problématiques. Nous créons ici
deux codes différents:
- Un code
safequi est inspiré de Learn Rust With Entirely Too Many Linked Lists mais qui on le verra n'est pas complètementsafequand on gratte un peu. - Un code
unsafequi ressemble à la liste simplement chaînée que nous écririons enC.
Les deux contraintes qui nous intéressent ici, et qui sont relaxées sont:
- Le déréférencement d'un "pointeur cru" (raw pointer).
- L'appel à une fonction
unsafe.
Ainsi tout code qui fait l'une ou l'autre de ces opérations, doit être annoté unsafe
suivit par un bloc:
unsafe {
// les opérations pas sûres ici
}Comme tout bloc, il peut ainsi retourner une valeur.
Il a d'autres contraintes qui sont relaxées, mais nous n'en profiterons pas ici, donc nous ne les mentionnons pas. En revanche toutes les règles concernant la propriété et les prêts restent valides. On peut pas faire n'importe quoi tout de même!
La version safe
La structure de données de la liste chaînée reste identique à celle que nous avons vue plus haut, ainsi que la création d'une nouvelle liste.
struct Element {
data: i32,
next: Option<Box<Element>>,
}
pub struct LinkedList {
head: Option<Box<Element>>,
}
pub fn new() -> Self {
Self { head: None }
}Ici, nous ne nous interdisons pas d'utiliser des références et d'emprunter les instances
de notre liste. Ainsi, la fonction is_empty() est simplement
pub fn is_empty(&self) -> bool {
self.head.is_none()
}où on a bien une référence vers self en argument de is_empty.
La fonction push()
La fonction dont nous discuterons le plus en détails est la fonction push().
Au fur et à mesure que nous la modifierons, nous étudierons ce qu'elle fait.
Naïvement, nous voudrions que push() fasse
fn push(&mut self, data: i32) {
let new_element = Box::new(Element::new(data, self.head));
self.head = Some(new_element);
}Évidemment, cela ne peut pas être aussi simple, car on "move" self.head dans
new_element ce qui est interdit, car self est derrière une référence mutable...
On doit donc ruser beaucoup plus pour faire croire à l'infâme compilateur que ce qu'on fait est sûr.
La solution simple et élégante est d'utiliser la méthode take() implémentée pour
les Option<T> qui retourne la valeur de l'option et la remplace par None.
Ainsi, le compilateur est content: on a pas move self.head, mais on l'a juste muté.
pub fn push(&mut self, data: i32) {
// let new_element = Box::new(Element::new(data, self.head));
// Cela ne peut pas fonctionner, pace qu'on est derrière une référence partagée
// et donc on peut pas "move" self.head
let new_head = Box::new(Element::new(data, self.head.take()));
// take retourne la valeur qui se trouve dans Some et laisse un None
// à la place de l'option.
// C'est strictement équivalent au replace (ci-dessous)
self.head = Some(new_head);
}On a donc un push() fonctionnel. Mais on ne sait pas vraiment ce qui se passe
dans le take() et ça semble un peu trop "magique" pour être safe.
En étudiant l'implémentation de take() on se rencontre que `
self.head.take()est équivalent à
std::mem::replace(&mut self.head, None)qui lui-même est équivalent à
unsafe {
let result = std::ptr::read(&self.head);
std::ptr::write(&mut self.head, None);
result
}En fait, tout au fond des choses, take() effectue des appels aux fonctions unsafe
read() et write(). En fait read() crée un copie "bit à bit" de self.head et
comme self.head n'est pas Copy on a deux moyens d'accéder à la mémoire: soit par
self.head soit par result (c'est de l'aliasing, ce qui est pas super sûr...). En particulier, si on essaie
d'assigner self.head (self.head = ...) le compilateur va libérer la mémoire qui était
liée à self.head et ainsi rendre les données de result invalides! Pour empêcher cela
on doit utiliser la fonction write() qui va écrire sans libérer la mémoire
les données liées à self.head (ce qui non plus n'est pas très sûr, parce qu'on
gère pas la libération de la mémoire de self.head).
Combinées ces deux opérations read()/write() sont sûres, mais le compilateur n'a aucun moyen de le déduire et nous avons dû recourir à des opérations unsafe bien qu'emballées dans des fonctions parfaitement safe! Nous n'avons donc plus de garantie de la part du compilateur,
et par conséquent, la responsabilité de la gestion de la mémoire nous revient (cf. les travaux du Pr. Ben).
pub fn push_replace(&mut self, data: i32) {
let old_head = std::mem::replace(&mut self.head, None);
let new_head = Box::new(Element::new(data, old_head));
// replace retourne self.head et remplace l'ancienne valeur par None (comme ça le compilateur est content)
self.head = Some(new_head);
}
pub fn push_unsafe(&mut self, data: i32) {
let old_head = unsafe {
// De la documentation:
// `read` crée une copie bit à bit de `T`, que `T` soit [`Copy`] ou non.
// Si `T` n'est pas [`Copy`], utiliser à la fois la valeur renvoyée et la valeur de
// `*src` peut violer la sécurité de la mémoire. Notez que l'assignation à `*src` compte comme une
// utilisation parce qu'elle tentera de `drop` la valeur à `*src`.
let result = std::ptr::read(&self.head);
std::ptr::write(&mut self.head, None);
// Ce `write` est en fait un "truc" pour enlever l'aliasing entre
// self.head et result. Il écrase la valeur à self.head avec None
// sans `drop` self.head et donc result.
result
};
let new_head = Box::new(Element::new(data, old_head));
self.head = Some(new_head);
}Dans ce code, nous voyons dans le commentaire l'utilisation d'un mot peut-être inconnu: aliasing.
L'aliasing décrit une situation dans laquelle un emplacement de données en mémoire peut être accessible
par différents noms dans le programme: dans notre cas result et self.head.
La morale de cette histoire est qu'il et très important d'essayer de faire son maximum pour faire du
code safe. Comme on peut le voir dans le code ci-dessus, certaines fois cela est impossible (ou impose une complexité beaucoup trop grande
à la personne qui développe),
car les règles du compilateur sont telles qu'il ne peut
garantir que ce qu'on fait est sûr. Dans ces rares cas,
après avoir bien réfléchi et qu'on s'est assuré que le code est sûr quoi qu'il
arrive, on peut écrire des parties de code unsafe. Une bonne pratique reste d'emballer ce
code dans une fonction safe afin de limiter les cas d'utilisation.
La fonction pop()
La fonction pop() prend en argument &mut self et modifie donc l'instance de la liste chaînée sur laquelle elle s'applique. Elle a aussi recours à la fonction take() comme push().
pub fn pop(&mut self) -> Option<i32> {
// map prend la valeur dans Some, lui applique la fonction anonyme
// et remballe la valeur obtenue dans un Some. Si l'Option
// originale est None, il se passe rien.
self.head.take().map(|element| {
self.head = element.next;
element.data
})
}Si nous nous limitions à self.head.take(), nous retournerions la tête de la liste,
après l'avoir remplacée par None. Cela casserait évidemment la liste chaînée de
plus d'un élément... Ainsi, nous utilisons la fonction map() qui va appliquer
la fonction anonyme qui lui est donnée en argument à la variante Some(elem)
et emballer le retour dans une variante Some() (elle ne fera rien si
l'option est None). Ici, nous retournons les données stockées dans l'élément de la tête, puis assignons l'élément suivant à la tête.
La fonction print()
La fonction print() est également bien plus élégante que celle vue précédemment.
pub fn print(&self) {
let mut current = &self.head;
while let Some(tmp) = ¤t {
print!("{} --> ", tmp.data);
current = &tmp.next;
}
println!("∅");
}En effet, elle ne prend qu'une référence vers la liste et va se contenter de parcourir tous les éléments sans libérer la mémoire.
La version unsafe
Nous avons utilisé l'appel de fonctions unsafe à l'intérieur de fonction safe pour
faire le code précédent. Dans cette partie, nous allons manipuler des "raw" pointers,
qui ressemblent beaucoup aux pointeurs du C.
Les pointeurs sont très semblables aux références, sauf qu'ils n'obéissent pas aux mêmes
règles de sûreté ou de durée de vie. C'est pour cela que ce genre de pointeurs sont utilisés
bien souvent pour faire du Rust unsafe. Ces pointeurs se créent communément à partir de références
#![allow(unused)] fn main() { let value = 2; let p_to_value: *const i32 = &value; }
Ici, nous partons d'une variable immutable value dont nous prenons la référence (immutable)
et nous l'assignons à un pointeur constant de i32. Ce type de pointeur peut uniquement être lu et il est impossible de modifier la valeur pointée (le code suivant ne compile pas).
#![allow(unused)] fn main() { let value = 2; let p_to_value: *const i32 = &value; *p_to_value = 3; // argl }
Pour créer un pointeur pouvant modifier les données sur lesquelles il pointe, il est nécessaire que value et la référence créée
sur value soient mutables. Mais il faut également se rappeler que pour modifier une valeur, il faut déréférencer le pointeur
ce qui est une opération très dangereuse. Ainsi, il faut annoter tout code contenant le déréférencement d'un pointeur cru
avec unsafe
#![allow(unused)] fn main() { let mut value = 2; let p_to_value: *mut i32 = &mut value; unsafe { *p_to_value = 10; } }
Sans l'annotation unsafe on a l'erreur suivante
error[E0133]: dereference of raw pointer is unsafe and requires unsafe function or block
--> /tmp/mdbook-1nmQ54/unsafe.md:450:5
|
5 | *p_to_value = 10;
| ^^^^^^^^^^^^^^^^ dereference of raw pointer
|
= note: raw pointers may be null, dangling or unaligned; they can violate aliasing rules and cause data races: all of these are undefined behavior
error: aborting due to previous error
For more information about this error, try `rustc --explain E0133`
La structure de données
La structure de données d'un élément ressemble beaucoup à ce qu'on écrirait en C
#![allow(unused)] fn main() { struct Element { data: i32, next: *mut Element, } }
Un Element contient, data, les données qui sont stockées dans chaque élément (un i32 ici)
et un raw pointer mutable sur l'élément suivant: next. Il est très important que ce pointeur
soit mutable pour qu'on puisse le modifier (pour ajouter ou supprimer les éléments).
Notez qu'en comparaison avec les Element des sections précédentes, nous n'utilisons pas de
type Option pour signaler la présence ou absence d'un élément suivant. Cela sera représenté,
comme en C, par un pointeur null.
Un nouvel Element est créé à l'aide de la fonction new()
fn new(data: i32, next: *mut Element) -> *mut Element {
let layout = Layout::new::<Element>();
let e = unsafe { alloc(layout) as *mut Element };
if e.is_null() {
handle_alloc_error(layout);
}
unsafe {
(*e).data = data;
(*e).next = next;
}
e
}qui prend en argument les données à stocker dans l'élément et le pointeur suivant.
On constate que pour allouer un élément, on doit préciser son "layout" en mémoire,
puis utiliser la fonction alloc() qui est une fonction unsafe qui
alloue un espace mémoire correspondant au layout spécifié et retourne un pointeur
d'octets (u8). Ce pointeur est immédiatement converti en pointeur mutable
d'Element. Lors d'une tentative d'allocation manuelle, si l'allocation échoue le
programme panique par défaut. Ici, on doit gérer l'échec de l'allocation manuellement
en vérifiant si le pointeur est nul e.is_null(). Ensuite, il est nécessaire de déréférencer le nouvel élément e et d'assigner chacun de ses champs à data et next respectivement. Cette opération nécessitant un déréférencement est
unsafe et est annotée de façon adéquate.
L'allocation manuelle nécessite également une libération de la mémoire manuelle à
l'aide de la fonction dealloc(). Cette opération est faite dans le trait Drop qui
implémente la fonction drop(). Pour des raw pointers, la fonction drop() n'est pas appelée automatiquement et il faut l'appeler explicitement lors de la sortie de la portée du pointeur (voir la section sur pop()). De plus, pour la plupart des types, la fonction drop() est implémentée automatiquement, mais ici
il est nécessaire d'appeler dealloc() manuellement et donc il est nécessaire
de faire l'implémentation explicitement.
impl Drop for Element {
fn drop(&mut self) {
let elem = self as *mut Element;
if !elem.is_null() {
let layout = Layout::new::<Element>();
unsafe {
dealloc(elem as *mut u8, layout);
}
}
}
}On voit que pour libérer la mémoire, on doit vérifier que le pointeur
qu'on essaie de libérer n'est pas null afin d'éviter de tenter de désallouer
une zone mémoire interdite, puis on appelle la fonction dealloc()
qui est de façon inhérente
unsafe (on a aucune garantie que la mémoire qu'on libère est toujours valide) il
est nécessaire d'annoter le code unsafe également (comme pour alloc() on a besoin de connaître le layout mémoire de ce qu'on va libérer).
Les fonctions new() et drop() sont deux fonctions qui appellent du code unsafe
, mais n'ont pas besoin d'être annotées unsafe: c'est des abstractions permettant
de cacher la dangerosité, tout en permettant à l'utilisateur·trice de chercher
les bugs mémoire plus facilement, car ils se trouvent toujours liés à ces parties unsafe.
Maintenant que nous pouvons créer des nouveaux éléments (et les détruire), nous pouvons passer à la liste chaînée qui n'est rien d'autre qu'un pointeur d'Element mutable nommé astucieusement head.
pub struct LinkedList {
head: *mut Element,
}Pour créer une nouvelle liste chaînée, nous avons uniquement besoin de signaler
que la liste est vide en assignant à head un pointeur nul mutable (ptr::nul_mut()).
pub fn new() -> LinkedList {
LinkedList {
head: ptr::null_mut(),
}
}La fonction is_empty()
Naturellement, la fonction is_empty() va uniquement vérifier que la tête de la liste
est nulle et est trivialement implémentée
fn is_empty(&self) -> bool {
self.head.is_null()
}La fonction push()
La fonction push() est très simple à écrire et équivalente à ce qu'on ferait en C
pub fn push(&mut self, data: i32) {
let new_head = Element::new(data, self.head);
self.head = new_head;
}La relaxation des règles très strictes sur les références permet de déplacer le pointeur de tête dans le nouvel élément qui devient ainsi la nouvelle tête de la liste.
La fonction pop()
La fonction pop() est un peu plus complexe, mais également très similaire à ce qu'on
ferait en C.
pub fn pop(&mut self) -> Option<i32> {
if self.is_empty() {
None
} else {
let old_head = self.head;
unsafe {
self.head = (*self.head).next;
}
let val = unsafe { (*old_head).data };
unsafe {
old_head.drop_in_place();
}
Some(val)
}
}Si la liste est vide, on retourne un None (aucune valeur) car il n'y a rien à retourner.
En revanche, si un élément est présent en tête de liste on garde un pointeur sur la copie de l'élément de tête, old_head, puis on déplace le pointeur de tête sur l'élément suivant
(cette dernière opération nécessite un déréférencement et est donc unsafe).
Puis ont récupère la data stockée dans old_head (opération unsafe car on fait un déréférencement) et finalement on appelle explicitement drop_in_place() (qui appelle drop()). Suite à la libération de la mémoire (qui empêche les fuites mémoire)
on termine par retourner la valeur qui était stockée au sommet de la liste chaînée.
La fonction print()
La fonction print() est relativement simple et très similaire à ce qu'on fait en C
pub fn print(&self) {
let mut current_head = self.head;
while !current_head.is_null() {
unsafe {
print!("{} --> ", (*current_head).data);
current_head = (*current_head).next;
}
}
println!("∅");
}On crée un pointeur mutable qui va parcourir tous les éléments de la liste chaînée et en afficher le contenu, jusqu'à atteindre la fin de la liste (le pointeur devient null). Les raw pointers n'appelant jamais drop() quand ils sortent de la portée
ne libèrent jamais la mémoire sur laquelle ils pointent donc la liste chaînée reste intacte.
La fonction drop()
Comme on l'a dit tout à l'heure pour les Element, il est nécessaire d'implémenter
le trait Drop
impl Drop for LinkedList {
fn drop(&mut self) {
while !self.is_empty() {
let _ = self.pop();
}
}
}Ici toutes les désallocations sont cachées dans la fonction pop(), et on parcourt
toute la liste comme on l'a fait pour la fonction print().
Aller plus loin
Il y a plusieurs exercices que vous pouvez effectuer à partir de ces codes. Dans un ordre aléatoire:
- Rendez-la liste générique (transformez
i32enT), - Ajoutez la fonction
peek()qui permet de jeter un œil à la tête de la liste, - Ajoutez une fonction
remove(i)permettant d'enlever lei-ème élément de la liste, - Ajoutez une fonction
insert(i, data)permettant d'ajouterdataà lai-ème place dans la liste, - Ajouter les fonctions permettant d'itérer sur la liste en implémentant les trait
IteretIntoIter.
Rustlings
Les rustlings à faire dans ce chapitre sont les suivants:
Les Box
$ rustlings run box1