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 i32 pour 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.

Une liste de construction infinie

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 est ressemble plus maintenant à 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.

Une liste de construction finie

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 que la boite pointait est aussi nettoyé grâce au 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.