Types auto-référentiels

Pour commencer ce chapitre sur l’asynchronisme, nous devons évoquer un sujet qui n’est pas directement lié à l’asynchronisme, mais qui a émergé dans le cadre du développement de l’infrastructure associée, et dont l’asynchronisme reste aujourd’hui la principale application : les types auto-référentiels, dont les données contiennent des références vers elles-mêmes.

Problème

Considérons la déclaration de type suivante, utilisant une syntaxe imaginaire ressemblant à du Rust :

struct AutoReferentiel {
    /// Données auxquelles on fait référence
    donnee: i32,

    /// Référence vers l'autre membre self.a de la structure
    /// (la syntaxe 'self n'existe pas vraiment en Rust)
    reference: &'self i32,
}

On pourrait penser qu’il est possible de la construire avec la syntaxe Rust standard, mais en réalité ce n’est pas possible avec du code safe, ni de façon simple…

struct AutoReferentiel<'donnees> {
    donnees: i32,
    reference: &'donnees i32,
}

let simple = AutoReferentiel {
    donnees: 42,
    reference: /* ??? */,
};

…ni de façon compliquée…

struct AutoReferentiel<'donnees> {
    donnees: i32,
    reference: &'donnees i32,
}

fn sournois() -> AutoReferentiel</* ??? */> {
    let temporaire = 123;
    let mut resultat = AutoReferentiel {
        donnees: 42,
        reference: &temporaire,
    };
    resultat.temporaire = &resultat.donnees;
    resultat
}

Pour construire un tel type, on est forcé d’utiliser des pointeurs bruts, ce qui veut dire que pour l’utiliser, on aura besoin de code unsafe :

#![allow(unused)]
fn main() {
struct AutoReferentiel {
    donnees: i32,
    pointeur: *const i32,
}

// Construction
let mut autoref = AutoReferentiel {
    donnees: 42,
    pointeur: std::ptr::null(),
};
autoref.pointeur = &autoref.donnees;

// Utilisation (ATTENTION : Lire ce qui suit avant de reprendre ce code !)
println!("{}", unsafe { *autoref.pointeur });
}

Pourquoi a-t’on besoin d’unsafe ici ? Pour le comprendre, il nous faut nous demander ce qui se passerait si la variable autoref était déplacée.

Pour rappel, la façon dont Rust a transformé le déplacement de C++11, qui était une fonctionnalité obscure, mal comprise et peu utilisée, en élément quotidien du langage qui ne pose problème à personne, a été de spécifier que cette opération se comporte comme un memcpy().

Pour la quasi totalité des types qu’on utilise au quotidien, dont les références et pointeurs désignent d’autres données en mémoire c’est une façon correcte de faire. Mais pas pour les données de types auto-référentiels. Lorsqu’on déplace une donnée auto-référentielle en mémoire, on change l’adresse de la donnée, donc on invalide les pointeurs internes qui continuent de pointer vers l’ancienne adresse de la donnée. Si l’on tente d’utiliser ces pointeurs à nouveau, il en résultera du comportement indéfini de type dangling pointer : le programme est invalide et fera n’importe quoi.

L’utilisation d’un type auto-référentiel défini de façon simple doit donc nécessiter du code unsafe en Rust, puisqu’elle est soumise à une précondition de sécurité qui est que les données de ce type ne doivent pas être déplacées entre l’initialisation d’un objet auto-référentiel et la fin de son utilisation.

Historique

Le problème des types auto-référentiels a été soulevé peu de temps après la stabilisation du langage Rust, dès que les programmeurs ont voulu retourner d’une fonction un type qui possède une donnée, mais se comporte comme une référence à cette donnée.

Supposons par exemple qu’on veuille retourner un type qui possède un tableau [T; N], mais se comporte comme un &[T] vers une partie du tableau. La première idée qui vient est de créer un type qui est litéralement composé d’un [T; N] et d’un &[T] vers le tableau, avec un accesseur qui permet d’obtenir une copie du &[T]. Mais malheureusement, un tel type est auto-référentiel.

Cependant, dans la plupart de ces situations, il existe une solution moins élégante que de créer un type auto-référentiel. Par exemple, dans l’exemple ci-dessus, on peut retourner un type composé d’un [T; N] et un Range<usize> d’indices, puis créer un &[T] associé à la demande.

L’absence de types auto-référentiels n’est donc pas bloquante. Mais on a le sentiment de dépenser de l’énergie à contourner les limites du langage et c’est insatisfaisant. Ce qui a amené plus d’un membre de la communauté Rust à chercher une solution plus générale au problème, sous forme d’extension du langage ou de bibliothèque permettant l’utilisation de types auto-référentiels.

Grâce à ces recherches, on a aujourd’hui un certain recul critique vis à vis de ce problème, et de différentes solutions qui ont été historiquement proposées :

Garder le memcpy() comme comportement par défaut du déplacement, mais permettre d’injecter un comportement plus compliqué si besoin à la manière des move constructors et move assignments de C++11.
- C’est impossible sans briser la compatibilité avec une partie du code unsafe existant qui présume qu’un memcpy() qui supprime l’accès à la source est toujours autorisé.
Interdire le déplacement des données auto-référentielles.
- Si c’était fait de façon générale, dès la construction des données, cela rendrait ces données très difficiles à utiliser et nécessiterait d’autres ajouts complexes au langage, du même genre que le placement new et la return value optimization de C++.
- Néanmoins, on peut utiliser une variante moins contraignante de cette idée, comme on va le voir dans un instant.
Utiliser des pointeurs relatifs (offsets) plutôt que des pointeurs absolus dans les structures de données auto-référentielles.
- C’est possible et élégant, mais ça veut dire que les pointeurs relatifs vivent dans leur monde à eux et que l’interopérabilité avec les autres types pointeurs et références du langage Rust va nécessairement être difficile.
Allouer systématiquement les données auto-référentielles sur le tas via Box<T> ou autre, et exposer une API limitée qui ne permet pas de déplacer les données situées à l’intérieur.
- L’allocation systématique sur le tas n’est pas quelque chose qu’on souhaite imposer sans alternative comme primitive de base au niveau du langage, d’autant plus que certaines utilisations des données allouées sur la pile sont en réalité légales.
- Quand on limite l’API pour éviter les déplacements (qui sont possibles dès lors qu’on dispose d’un &mut sur les données intérieures, via des APIs comme std::mem::replace()), on tend à se restreindre à un certain domaine d’applications.
- De très nombreuses bibliothèques ont tenté de produire une abstraction safe générale et se sont révélées plus tard avoir du comportement indéfini quand elles sont utilisées de la mauvaise façon. Si une solution existe, elle nécessite clairement du code très subtil. Et si vous comptez utiliser une de ces bibliothèques, prenez bien le temps de vous assurer qu’elle a été passée en revue par des experts indépendants sensibilisés au risques de comportement indéfini lié aux types auto-référentiels…

Toutes ces réflexions historiques ont fait que plus tard, quand les fonctions asynchrones se sont révélées nécessiter l’utilisation de types auto-référentiels, la communauté Rust avait déjà un bon recul critique sur ce problème. Ce qui a permis l’émergence d’une nouvelle façon d’aborder le problème, qui est devenue standard dans le domaine de l’asynchronisme en Rust : le pinning.

Pinning

Le type générique Pin<P>, où P est un genre de pointeur (&, &mut, *const, *mut, NonNull, Box, Arc, etc.), se base sur les observations suivantes :

Si on n’arrive pas à discipliner les données auto-référentielles elles-mêmes, on peut essayer de discipliner les pointeurs vers ces données à la place.
Si le coût ergonomique d’une interdiction permanente des déplacements est inacceptable, on peut interdire les déplacements seulement pendant la phase du programme où la partie auto-référentielle du type est en train d’être utilisée.
Si on n’arrive pas à prouver automatiquement l’absence de mouvement à la compilation, on peut se rabattre sur une preuve manuelle, avec une interface unsafe.
Si on accepte l’ensemble des observations ci-dessus, alors il n’y a pas besoin de beaucoup de support au niveau du compilateur, on peut presque tout faire dans une bibliothèque.

Partant de là, Pin<P> agit comme un wrapper de P qui limite l’utilisation de P de la façon suivante :

Toutes les méthodes de Pin<P> qui pourraient exposer un &mut T sur la valeur cible (donc permettre son déplacement) ou déplacer directement la valeur sont unsafe par défaut. Leur utilisateur doit garantir qu’aucun déplacement incorrect ne sera effectué.
Le compilateur implémente automatiquement un trait marqueur Unpin pour tous les types qui ne sont pas auto-référentiels (donc presque tous les types, avec quelques exceptions importantes que nous allons aborder plus loin).
Lorsqu’un type implémente Unpin, il n’y a pas de risques liés au déplacement, donc des variantes safe des méthodes permettant le déplacement et exposant &mut T sont exposées.

Ces bases simples cachent un monde de complexité au niveau du détail, qui font que la documentation du module std::pin est de celles qu’on utilise pour faire peur aux enfants. Mais en pratique, l’abstraction suffit pour les besoins de la programmation asynchrone. Et on a rarement besoin de la manipuler directement dans ce cadre, ce qui fait que ce n’est pas trop gênant en pratique qu’elle soit difficile à bien utiliser.

Certains comme moi entretiennent toujours l’espoir qu’un jour, un théoricien plus brillant que les autres trouvera une meilleure solution pour rendre les types auto-référentiels plus faciles à utiliser en Rust. Mais pour l’heure, Pin est la solution qui existe, et qui permet une programmation asynchrone à la fois performante et relativement ergonomique en Rust. Il est donc nécessaire de comprendre un minimum sa logique pour faire de l’asynchronisme en Rust.

Rust vu du C++

Types auto-référentiels

Problème

Historique

Pinning