Utiliser Box<T> pour pointer sur des données présentes sur le tas
Le pointeur intelligent le plus simple est la boite, dont le type s'écrit
Box<T>. Les boites vous permettent de stocker des données sur le tas plutôt
que sur la pile. La seule chose qui reste sur la pile est le pointeur vers les
données sur le tas. Revenez au chapitre 4 pour vous rappeler la différence entre
la pile et le tas.
Les boites ne provoquent pas de surcharge au niveau des performances, si ce n'est le stockage de leurs données sur le tas plutôt que sur la pile. Mais elles n'ont pas non plus beaucoup plus de fonctionnalités. Vous allez les utiliser principalement dans les situations suivantes :
- Lorsque vous avez un type dont la taille ne peut pas être connu au moment de la compilation et que vous souhaitez une valeur d'un certain type dans un contexte qui nécessite de savoir exactement sa taille
- Lorsque vous avez une grosse quantité de données et que vous souhaitez transférer la possession tout en assurant que les données ne seront pas copiées lorsque vous le ferez
- Lorsque vous voulez prendre possession d'une valeur et que vous souhaitez seulement qu'elle soit d'un type qui implémente un trait particulier plutôt que d'être d'un type spécique
Nous allons expérimenter la première situation dans la section “Pouvoir utiliser des types récursifs grâce aux boites”. Pour la seconde situation, le transfert de possession d'une grosse quantité de données peut prendre beaucoup de temps car les données sont recopiées sur la pile. Pour améliorer les performances dans cette situation, nous pouvons stocker ces données sur le tas grâce à une boite. Ainsi, seul le petit pointeur vers les données est copié sur la pile, alors que les données qu'il pointe restent à leur place sur le tas. La troisième situation décris ce qu'on appelle un objet de trait et le chapitre 17 dédie une section entière à ce sujet. Donc ce que vous apprenez ici, vous le retrouverez à nouveau au chapitre 17 !
Utiliser une Box<T> pour stocker des données sur le tas
Avant de parler de ce cas d'usage de Box<T>, nous devons voir sa syntaxe et
comment interagir avec les valeurs stockées dans un Box<T>.
L'encart 15-1 nous montre comment utiliser une boite pour stocker une valeur
i32 sur le tas :
Fichier : src/main.rs
fn main() { let b = Box::new(5); println!("b = {}", b); }
Encart 15-1 : stocker une valeur i32 sur le tas en
utilisant une boîte
Nous avons défini la variable b pour avoir la valeur d'une Box qui pointe
sur la valeur 5, qui est donc allouée sur le tas. Ce programme va afficher
b = 5 ; dans ce cas, nous pouvons accéder à la donnée présente dans la boite
de la même manière que nous le ferrions si elle était sur la pile. Comme toute
valeur possédée, lorsque une boite sort de la portée, comme lorsque b le fait
à la fin du main, elle sera désallouée. Ce sera la boite qui sera désallouée
en premier (elle est stockée sur la pile), puis ce sera au tour des données sur
lesquelles elle pointait (qui sont stockées sur le tas).
Déposer une seule valeur sur le tas n'est pas très utile, donc vous n'utiliserez
que très rarement les boites de cette manière. Laisser les valeurs comme des i32
indépendantes sur la pile, où elles sont stockées par défaut, reste plus
approprié dans la majeure partie des situations. Regardons un cas où les boites
nous permettent de définir des types que nous ne pourrions pas définir si nous
n'avions pas les boites.
Pouvoir utiliser des types récursifs grâce aux boites
Au moment de la compilation, Rust a besoin de savoir combien d'espace prend un type. Un des types dont la taille ne peut pas être connu au moment de la compilation est le type récursif, dans lequel une valeur peut avoir une partie de sa définition qui a une valeur du même type qu'elle-même. Comme cet emboîtement de valeurs pourrait théoriquement se poursuivre à l'infini, Rust ne sait pas combien d'espace une valeur d'un type récursif peut avoir besoin. Cependant, les boites ont une taille connue, donc en utilisant une boite dans la définition d'un type récursif, vous pouvez créer des types récursifs.
Découvrons maintenant la liste de construction (NdT : cons list), qui est un type de donnée courant dans les langages de programmation fonctionnels, comme étant un exemple de type récursif. Le type liste de construction que nous allons définir est plutôt simple, sauf pour les cas de récursivité ; par conséquent, les concepts dans l'exemple avec lequel nous allons travailler vous seront utiles à chaque fois que vous vous retrouverez dans des situations plus complexes qui impliquent des types récursifs.
En savoir plus sur les listes de construction
Une liste de construction est une structure de donnée qui provient du langage
de programmation Lisp et de ses dérivés. En Lisp, la fonction cons (qui est
une forme contractée de “fonction de construction”) construit une nouvelle paire
à partir de ses deux arguments, qui sont souvent une valeur individuelle et une
autre paire. Ces paires qui contiennent des paires forment des listes.
Le concept de la fonction cons a fait son chemin dans le jargon plus général de la programmation fonctionnelle : "to cons x onto y" signifie de manière informelle de construire une nouvelle instance de conteneur en mettant l'élément x au début de ce nouveau conteneur, suivi du conteneur y.
Chaque élément dans une liste de construction contient deux éléments : la valeur
de l'élément courant et celle de l'élément suivant. Le dernier élément dans la
liste contient seulement une valeur Nil sans aucun élément suivant. Une
liste de construction est produite de manière récursive en appelant la fonction
cons. Le nom canonique pour indiquer le cas de base de la récursion est Nil.
Notez que ce n'est pas la même chose que les concepts “null” ou “nil” du
chapitre 6, qui signale une valeur invalide ou absente.
Bien que les langages de programmation fonctionnels utilisent les listes de
construction fréquemment, la liste de construction n'est pas une structure de
donnée utilisée couramment en Rust. La plupart du temps lorsque vous avez une
liste d'éléments en Rust, Vec<T> s'avère être un meilleur choix à faire.
Autrement, il existe des types de données récursifs plus complexes qui sont
utiles dans d'autres situations, mais en commençant avec les listes de
construction, nous pouvons découvrir comment les boites nous permettent de
définir un type de données récursif sans être trop perturbé par la complexité.
L'encart 15-2 propose une définition d'une énumération pour une liste de
construction. Notez que ce code ne se compile pas encore car le type List n'a
pas encore de taille connue, ce que nous allons voir ensuite.
Fichier : src/main.rs
enum List {
Cons(i32, List),
Nil,
}
fn main() {}
Encart 15-2 : première tentative de définition d'une
énumération pour représenter une structure de données de liste de construction
de valeurs i32
Remarque : nous implémentons une liste de construction qui stocke uniquement des valeurs
i32pour les besoins de cet exemple. Nous aurions pu l'implémenter en utilisant des génériques, que nous avons vu chapitre 10, afin de définir une liste de construction qui pourrait stocker n'importe quel type.
L'utilisation du type List pour stocker la liste 1, 2, 3 ressemblerait au
code dans l'encart 15-3 :
Fichier : src/main.rs
enum List {
Cons(i32, List),
Nil,
}
use crate::List::{Cons, Nil};
fn main() {
let list = Cons(1, Cons(2, Cons(3, Nil)));
}
Encart 15-3 : utilisation de l'énumération List pour
stocker la liste 1, 2, 3
La première valeur Cons stocke 1 et une autre valeur de List. Cette
valeur List est une autre valeur Cons qui stocke 2 et une autre valeur de
List. Cette valeur List n'est rien d'autre qu'une valeur Cons qui stocke
3 et une valeur List, qui finalement est Nil, la variante non récursive
qui signale la fin de la liste.
Si nous essayons de compiler le code de l'encart 15-3, nous avons l'erreur de l'encart 15-4 :
$ 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 {
| ^^^^^^^^^ recursive type has infinite size
2 | Cons(i32, List),
| ---- recursive without indirection
|
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `List` representable
|
2 | Cons(i32, Box<List>),
| ++++ +
error[E0391]: cycle detected when computing drop-check constraints for `List`
--> src/main.rs:1:1
|
1 | enum List {
| ^^^^^^^^^
|
= note: ...which immediately requires computing drop-check constraints for `List` again
= note: cycle used when computing dropck types for `Canonical { max_universe: U0, variables: [], value: ParamEnvAnd { param_env: ParamEnv { caller_bounds: [], reveal: UserFacing }, value: List } }`
Some errors have detailed explanations: E0072, E0391.
For more information about an error, try `rustc --explain E0072`.
error: could not compile `cons-list` due to 2 previous errors
Encart 15-4 : l'erreur que nous obtenons lorsque nous essayons de définir une énumération récursive
L'erreur explique que ce type “a une taille infinie”. La raison est que nous
avons défini List avec une variante qui est récursive : elle stocke
directement une autre valeur d'elle-même. Au final, Rust ne peut pas savoir
combien de place il a besoin pour stocker une valeur List. Analysons
pourquoi nous obtenons cette erreur. D'abord, regardons comment Rust décide de
l'espace dont il a besoin pour stocker une valeur d'un type non récursif.
Calculer la taille d'un type non récursif
Rappelez-vous de l'énumération Message que nous avons défini dans
l'encart 6-2 lorsque nous avons abordé les définitions des énumérations au
chapitre 6 :
enum Message { Quitter, Deplacer { x: i32, y: i32 }, Ecrire(String), ChangerCouleur(i32, i32, i32), } fn main() {}
Pour déterminer combien d'espace allouer pour une valeur Message, Rust
parcourt chaque variante pour voir quelle variante a besoin le plus d'espace.
Rust voit que Message::Quitter n'a pas besoin d'espace, Message::Deplacer a
besoin de suffisamment d'espace pour stocker deux valeurs i32, et ainsi de
suite. Comme une seule variante sera utilisée, le plus grand espace dont une
valeur de Message aura besoin sera l'espace que cela prendra de stocker la
plus grosse de ses variantes.
Comparez cela avec ce qui se passe lorsque Rust essaye de déterminer combien
d'espace un type récursif comme l'énumération List de l'encart 15-2 aurait
besoin. Le compilateur commence par regarder la variante Cons, qui stocke une
valeur de type i32 et une valeur de type List. Ainsi, Cons a besoin d'une
quantité d'espace égale à la taille d'un i32 plus la taille d'une valeur
List. Pour savoir combien de mémoire le type List a besoin, le compilateur
va regarder ses variantes, en commençant avec la variante Cons. La variante
Cons stocke une valeur de type i32 et une valeur de type List, et ce
processus continue à l'infini, comme l'illustration 15-1.
Illustration 15-1 : une List infinie qui contient des
variantes Cons infinies
Utiliser Box<T> pour créer un type récursif avec une taille finie
Rust ne peut pas calculer la quantité d'espace à allouer pour les types définis récursivement, donc le compilateur déclenche l'erreur de l'encart 15-4. Mais l'erreur renferme cette suggestion très utile :
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `List` representable
|
2 | Cons(i32, Box<List>),
| ^^^^ ^
Dans cette suggestion, “indirection” (NdT : redirection) signifie qu'au lieu de stocker une valeur directement, nous devrions changer la structure des données pour stocker à la place un pointeur vers la valeur.
Comme Box<T> est un pointeur, Rust connaît toujours combien d'espace un
Box<T> a besoin : la taille d'un pointeur ne change pas, peu importe la
quantité de données sur lesquelles il pointe. Cela signifie que nous pouvons
insérer un Box<T> à l'intérieur d'une variante Cons au lieu d'y mettre
directement une autre valeur List. Le Box<T> va pointer sur la prochaine
valeur List qui sera sur le tas plutôt que d'être dans la variante Cons.
Théoriquement, nous avons toujours une liste, créée avec des listes qui
“contiennent” d'autres listes, mais cette implémentation ressemble plus à
présent à des éléments placés les uns à côté des autres plutôt que les uns dans
les autres.
Nous pouvons changer la définition de l'énumération List de l'encart 15-2 et
l'utilisation de List dans l'encart 15-3 pour le code de l'encart 15-5, qui
va se compiler :
Filename : 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)))))); }
Encart 15-5 : définition de List qui utilise Box<T>
dans le but d'avoir une taille connue
La variante Cons va avoir besoin de l'espace d'un i32 plus l'espace pour
stocker le pointeur vers la donnée de la boite. La variante Nil ne stocke pas
de valeurs, donc elle a besoin de moins d'espace que la variante Cons. Nous
savons maintenant que chaque valeur List va prendre la taille d'un i32
plus la taille d'un pointeur vers la donnée de la boite. En utilisant une boite,
vous avez arrêté la chaine infinie et récursive, donc le compilateur peut
savoir l'espace dont il a besoin pour stocker une valeur List. L'illustration
15-2 montre à quoi ressemble maintenant la variante Cons.
Illustration 15-2 : une List qui n'a pas de taille
infinie car Cons est une Box
Les boites fournissent uniquement la redirection et l'allocation sur le tas ; elles n'ont pas d'autres fonctionnalités, comme celles que nous verrons sur d'autres types de pointeurs intelligents. Elles n'ont pas non plus de surcoût sur les performances autre que ce qu'offrent ces capacités spéciales, donc elles sont utiles dans des cas comme les listes de construction où la redirection est la seule fonctionnalité que nous avons besoin. Nous verrons aussi plus de cas d'usages pour les boites dans le chapitre 17.
Le type Box<T> est un pointeur intelligent car il implémente le trait
Deref, qui permet aux valeurs Box<T> d'être traitées comme des
références. Lorsque une valeur Box<T> sort de la portée, les données sur le
tas pointées par la boite seront également nettoyées grâce à l'implémentation
du trait Drop. Explorons plus en détail ces deux traits. Ces deux traits
deviendrons encore plus importants pour les fonctionnalités offertes par les
autres pointeurs intelligents que nous verrons dans le reste de ce chapitre.