Lifetimes

Concepts

Les concepts abordés dans cet exemple sont:

Pour plus d'informations sur le pattern NewType, vous pouvez vous référer aux chapitres 19.2 et 19.3 du livre. Pour les lifetimes, il y a le chapitre du livre correspondant, ainsi que celui du Rustonomicon.

Discussion

Dans ce chapitre, nous allons voir principalement deux concepts différents qui sont importants en Rust et qu'on retrouve dans beaucoup de code. Les lifetimes, en particulier, sont un sujet complexe et on verra deux applications différentes mais cela constitue la pointe de l'iceberg des applications possibles. Le pattern NewType est lui bien plus simple, et ne nécessite pas une très longue discussion.

Le pattern `NewType`

Le pattern NewType très commun en Rust consiste à encapsuler un type externe à une crate, dans un type local comme dans

#![allow(unused)]
fn main() {
#[derive(Debug)]
pub struct SomethingOrNothing<T>(Option<T>);
}

où on encapsule le type externe Option<T> dans SomethingOrNothing<T>. Ce type a un paramètre générique T et dérive le trait Debug qui permet de faire un affichage détaillé (mais pas très joli) du contenu du type. Ce pattern est nécessaire pour implémenter un trait externe sur un type extern (ce qui est interdit en Rust). Ainsi, il ne nous aurait pas été possible d'implémenter le trait Display (qui permet d'afficher une instance du type), Default (qui permet de créer une instance par défaut), ou PartialEq (qui permet de vérifier l'égalité de deux instance du type) directement pour le type Option<T>, car Display, Default, et PartialEq sont des traits externes tout comme le type Option<T>. Pour des types externes l'implémentation de traits externes est interdite (c'est la orphan rule). Cela interdit de "casser" un code externe en autorisant de multiples implémentations du même trait pour le même type. Ainsi SomethingOrNothing<T> nous permet d'implémenter ces trois traits

impl<T: Display> std::fmt::Display for SomethingOrNothing<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match &self {
            SomethingOrNothing(None) => write!(f, "Nothing.")?,
            SomethingOrNothing(Some(val)) => write!(f, "Something is: {}", val)?,
        }
        Ok(())
    }
}
impl<T> Default for SomethingOrNothing<T> {
    /// By Default a [SomethingOrNothing] is a nothing.
    fn default() -> Self {
        SomethingOrNothing(None)
    }
}
impl<T: PartialEq> PartialEq for SomethingOrNothing<T> {
    fn eq(&self, other: &Self) -> bool {
        match (&self, &other) {
            (SomethingOrNothing(None), SomethingOrNothing(None)) => true,
            (SomethingOrNothing(Some(lhs)), SomethingOrNothing(Some(rhs))) => lhs == rhs,
            _ => false,
        }
    }
}

Nous aimerions attirer votre attention sur une particularité du pattern matching ici. On voit que nous pouvons faire un match sur des types imbriqués comme pour SomethingOrNothing(Some(val)), on va déstructurer les types énumérés jusqu'à obtenir val qui est la valeur qui nous intéresse.

Une deuxième utilité du pattern NewType est qu'elle permet de limiter les fonctionnalités d'un type car cela nécessite de réimplémenter les méthodes qui lui sont propres. Dans notre cas, seule la méthode unwrap() de Option<T> nous intéresse (cette fonction retourne la valeur encapsulée dans la variante Some() ou panique si on a un None). Ainsi, on n'implémente que celle-là

    pub fn unwrap(self) -> T {
        self.0.unwrap()
    }

On peut noter qu'on a à faire à une struct avec des membres anonymes. Ainsi, les membres peuvent être accédés comme pour les tuples et comme il n'y en a qu'un dans un SomethingOrNothing<T>, on y accède avec le sélecteur self.0.

Les lifetimes

Dans cette section nous discutons l'utilisation de l'annotation des lifetimes dans différents cas: les structures, les méthodes, les traits, et les fonctions.

Les structures

Dans notre programme, nous utiliserons le type CustomInt qui est une représentation d'un entier qui peut avoir une taille arbitraire (dans les limites de la mémoire de la machine).

#[derive(Debug)]
pub struct CustomInt<'a> {
    /// The data contains the unsigned integers that are read from right to left
    /// The number 1337 is stored as vec![7, 3, 3, 1]. Each number must be in the range [0,9]
    /// and no trailing 0s are allowed.
    data: &'a Vec<u8>,
    /// Contains the sign of the number +/-1;
    sign: i8,
}

Un tel entier est représenté par un signe i8 (qui peut valoir +1 ou -1), et un Vec<u8>, un tableau dynamique de u8 (les valeurs admissibles vont de 0 à 9), qui contient les chiffres du nombre stockés de droite à gauche: [7,3,3,1] est le nombre 1337.

Ces nombres pouvant être gigantesques, nous voulons éviter de les dupliquer lorsque nous les copions ou les manipulons. Une solution est de stocker uniquement une référence vers les données, c'est-à-dire que data est de type &Vec<u8>. On voit dans le code ci-dessus, qu'il est nécessaire d'annoter la durée de vie de la référence avec 'a. Si on omet l'annotation de durée de vie le compilateur nous préviendra et nous oblige à en spécifier un

error[E0106]: missing lifetime specifier
  --> src/custom_int.rs:13:11
   |
13 |     data: &Vec<u8>,
   |           ^ expected named lifetime parameter
   |
help: consider introducing a named lifetime parameter
   |
9  ~ pub struct CustomInt<'a> {
10 |     /// The data contains the unsigned integers that are read from right to left
11 |     /// The number 1337 is stored as vec![7, 3, 3, 1]. Each number must be in the range [0,9]
12 |     /// and no trailing 0s are allowed.
13 ~     data: &'a Vec<u8>,

Il est en effet impossible pour le compilateur de savoir si la référence vivra assez longtemps pour vivre plus longtemps qu'une instance de CustomInt.

Les méthodes

L'implémentation des méthodes requiert une annotation sous peine d'erreurs

impl<'a> CustomInt<'a>

Il en va de même avec la fonction associée, try_new()

    pub fn try_new(data: &'a Vec<u8>, sign: i8) -> Result<Self, String> {
        if data.is_empty() {
            Err(String::from("Data is empty."))
        } else if sign == 1 || sign == -1 {
            Ok(CustomInt { data, sign })
        } else {
            Err(String::from("Invalid sign."))
        }
    }

qui nécessite une annotation dans la définition du type de data. En effet, l'annotation permet de dire au compilateur que data, l'argument de try_new(), vit suffisamment longtemps pour permettre la création d'une instance de CustomInt.

Les traits

Il y a plusieurs traits qui sont implémentés pour CustomInt<'a>.: PartialEq, Display, et Minumum. Pour PartialEq et Display, il suffit de renseigner l'annotation 'a à l'instruction impl comme pour un paramètre générique, voir

impl<'a> PartialEq for CustomInt<'a>
impl<'a> std::fmt::Display for CustomInt<'a>

Il est possible d'écrire la même chose, en omettant l'annotation 'a et en la remplaçant par '_ pour simplifier la notation

impl PartialEq for CustomInt<'_>

Comme l'annotation n'est utilisée nulle par, Rust offre ce sucre syntaxique pour éviter d'écrire trop d'annotations.

Pour le trait Minimum les choses se compliquent un peu. Pour éviter le copies/clones, on a fait le choix de n'utiliser que des références dans les arguments, comme dans le type de retour du calcul du minimum de deux valeurs

pub trait Minimum<'a> {
    fn min(&'a self, rhs: &'a Self) -> &'a Self;
}

Ainsi, comme il y deux références en argument et une référence en sortie, il est nécessaire d'annoter les références, car sinon le compilateur ne sait pas avec que durée de vie annoter la sortie (les 2 sont possibles). Ainsi nous annotons le trait avec la durée de vie 'a, puis cette durée de vie est utilisée pour toutes les références dans la fonction min(). Ainsi toutes les références ont la même durée de vie que celle annotée dans le trait.

Il y a trois implémentation de ce trait: la première est pour les i32, la seconde pour SomthingOrNothing<T>, et finalement pour CustomInt.

Pour l'implémentation pour les i32

impl<'a> Minimum<'a> for i32 {
    fn min(&'a self, rhs: &'a Self) -> &'a Self {
        if self < rhs {
            self
        } else {
            rhs
        }
    }
}

l'implémentation est triviale, il y a uniquement besoin de reprendre l'annotation pour l'implémentation dans les références en argument de la fonction et dans le retour de la fonction. En effet, comme les deux arguments peuvent être retournés, il est nécessaire de préciser au compilateur que la durée de vie sera la même, sinon il met automatiquement une durée de vie à chaque argument et reprend celle à &self comme la durée de vie de la sortie. En d'autres termes, sans annotations, on aurait

fn min(&self, rhs: &Self) -> &Self

qui serait converti automatiquement par le compilateur en

fn min(&'a self, rhs: &'b Self) -> &'a Self {
    if self < rhs {
        self
    } else {
        rhs
    }
}

et la durée de vie 'a du retour est pas compatible avec la durée de vie qui serait retournée au moment de retourner rhs (qui est 'b). Ce qui entraînerait une erreur de compilation (on aime pas ça les erreurs nous). 2. Pour l'implémentation pour SomethingOrNothing<T>, nous avons un paramètre générique.

impl<'a, T: Minimum<'a> + PartialEq> Minimum<'a> for SomethingOrNothing<T>
{
    fn min(&'a self, rhs: &'a Self) -> &'a Self {
        match (self, rhs) {
            (SomethingOrNothing(None), SomethingOrNothing(None)) => self,
            (SomethingOrNothing(Some(l)), SomethingOrNothing(Some(r))) => {
                if *l == *l.min(r) {
                    self
                } else {
                    rhs
                }
            }
            (SomethingOrNothing(None), SomethingOrNothing(Some(_))) => rhs,
            (SomethingOrNothing(Some(_)), SomethingOrNothing(None)) => self,
        }
    }
}

Ainsi nous constatons, que la ligne correspondant à la déclaration de l'implémentation du trait Minimum nécessite la déclaration de la durée de vie 'a, ainsi que du type générique T. On voit dans l'implémentation de la fonction min(), que nous faisons appel à min() sur le type T, et que donc celui-ci doit implémenter le trait Minimum (tout comme le trait PartialEq). On doit ainsi répercuter la durée de vie sur tous les Minimum présents sur la ligne impl

impl<'a, T: Minimum<'a> + PartialEq> Minimum<'a> for SomethingOrNothing<T>

Nous ne discutons pas l'implémentation à proprement parler qui est assez raisonnable pour trouver le minimum de deux valeur encapsulées dans un NewType. 3. Finalement, on a l'implémentation pour CustomInt qui n'a rien de vraiment nouveau par rapport aux implémentation précédentes (on réutilise l'annotation 'a dans min() directement), à part la complexité monumentale de la fonction (elle fait plein de lignes)

    fn min(&'a self, rhs: &'a Self) -> &'a Self {
        match self.sign.cmp(&rhs.sign) {
            Ordering::Less => return self,
            Ordering::Greater => return rhs,
            Ordering::Equal => match self.data.len().cmp(&rhs.data.len()) {
                Ordering::Less => {
                    if self.sign == 1 {
                        return self;
                    } else {
                        return rhs;
                    }
                }
                Ordering::Greater => {
                    if self.sign == 1 {
                        return rhs;
                    } else {
                        return self;
                    }
                }
                Ordering::Equal => {
                    for (l, r) in self.data.iter().rev().zip(rhs.data.iter().rev()) {
                        let ls = (*l as i8) * self.sign;
                        let rs = (*r as i8) * self.sign;
                        match ls.cmp(&rs) {
                            Ordering::Less => return self,
                            Ordering::Greater => return rhs,
                            Ordering::Equal => {}
                        }
                    }
                }
            },
        }
        self
    }

En effet, on doit faire attention au signe, à la longueur de notre CustomInt et à plusieurs autres joyeusetés. Ici, on peut utiliser le trait Ord (la fonction cmp()) pour faire les comparaisons entre le signe et les digits de nos nombres. Le trait Ord représente les opérateurs <, >, =, <=, >=, via la fonction cmp() qui retourne trois types correspondants

Ordering::Less
Ordering::Greater
Ordering::Equal

L'utilisation d'un type énuméré pour gérer chacun des cas peut sembler verbeux et complexe. Cependant, il permet de garantir à la compilation qu'on a pas oublié de traiter un cas par accident. Et ça, ça n'a pas de prix.

Les fonctions

Finalement, on utilise les lifetimes dans une fonction qui permet le calcul du minimum dans un tableau et retourne un SomethingOrNothing<&T> contenant une référence vers l'élément le plus petit.

Cette fonction est générique avec le paramètre T et prend en argument une référence qui doivent être annotée.

pub fn find_min<'a, T: Minimum<'a>>(tab: &'a [T]) -> SomethingOrNothing<&'a T> {
    // A very elegant fold applied on an iterator
    tab.iter().fold(SomethingOrNothing::default(), |res, x| {
        let r = match res {
            SomethingOrNothing(None) => x,
            SomethingOrNothing(Some(r)) => r.min(x),
        };
        SomethingOrNothing::new(r)
    })
}

La fonction find_min() prend en argument un slice de type générique T qui doit implémenter Minimum. Comme le type de retour est SomethingOrNothing<&T>, donc on encapsule une référence vers la valeur minimale, il est nécessaire d'annoter les durées de vies car sinon elles auraient deux valeur différentes ce qui poserait problème au compilateur (car elles doivent être les mêmes).

L'implémentation de cette fonction, n'est pas très complexe, mais est très intéressante. En premier lieu, pour des question de généricité de l'implémentation nous passons en argument un slice de T: cette façon de procéder permet d'avoir un argument qui serait une référence vers un tableau statique ou vers un Vec<T> sans changer l'implémentation. De plus, nous utilisons ici un itérateur sur le tableau est faisons un fold() sur cet itérateur. Le fold() prend en argument un élément neutre (quel est la valeur initiale stockée dans le fold()). Ici c'est

SomethingOrNothing::default()

puis une fonction anonyme prenant deux arguments

|res, x| {}

où la valeur retournée par cette fonction écrase la valeur de res à chaque next() de l'itérateur et qui doit avoir le même type que l'élément neutre, et où x est la valeur courante de l'itérateur. Ici, le type de res est SomethingOrNothing<&T> et le type de x est &T. La fonction anonyme

let r = match res {
    SomethingOrNothing(None) => x,
    SomethingOrNothing(Some(r)) => r.min(x),
};
SomethingOrNothing::new(r)

calcule le minimum entre la valeur actuelle stockée dans res et x en utilisant la fonction min() ce qui implique que T doit implémenter Minimum.

En pratique

Dans la fonction main() de notre programme

pub fn find_min<'a, T: Minimum<'a>>(tab: &'a [T]) -> SomethingOrNothing<&'a T> {
    // A very elegant fold applied on an iterator
    tab.iter().fold(SomethingOrNothing::default(), |res, x| {
        let r = match res {
            SomethingOrNothing(None) => x,
            SomethingOrNothing(Some(r)) => r.min(x),
        };
        SomethingOrNothing::new(r)
    })
}

on crée un tableau de CustomInt qui sont créés à partir de références sur les tableau v1, v2, etc. qui vivrons ainsi jusqu'à la fin de notre programme et qui seront promenées sans qu'on ait besoin de les copier à aucun moment. Les liens entre les durées de vie des références que nous nous sommes efforcés d'annoter dan tout au long ce code sont vérifiées par le compilateur qui vérifie qu'elles sont toutes valides à la compilation.

Rust-101: Université d'été