Les notes de cGuille

Introduction

À des fins d'apprentissage, je me suis intéressé au type std::collections::BinaryHeap de la bibliothèque standard.
Le type std::collections::BinaryHeap, ou tas binaire en français, est une structure de données idéale pour mettre en place une file de priorité.

L'implémentation standard fournie par Rust permet de mettre dans la file n'importe quel type de données à condition que ledit type implémente le trait std::cmp::Ord, c'est-à-dire si les valeurs de ce type peuvent être ordonnées.
Du coup je me suis dit que ce serait sympa de pouvoir ajouter facilement une notion de priorité à un type existant, afin de pouvoir les mettre dans une file priorisée sans obligé le type existant à être ordonné sur la priorité.

Exemple : une file de jobs priorisée

Si on prend l'exemple d'une file priorisée permettant de traiter des tâches d'envoi d'email, on peut imaginer qu'on ait un type EmailJob représentant ces tâches. Voici à quoi il pourrait ressembler :

type UserId = String;

#[derive(Debug)]
enum EmailKind {
    Welcome,
    OrderInvoice,
    Marketing,
}

#[derive(Debug)]
struct EmailJob {
    kind: EmailKind,
    user_id: UserId,
}

On a également une fonction chargée de traiter ces jobs :

fn process_email_job(job: &EmailJob) {
    // Perform the job
    println!("Processing job: {:?}", job);
}

On voudrait maintenant disposer d'une file de jobs, qu'on pourrait remplir avec des valeurs de type EmailJob, afin de les traiter de la manière suivante:

let mut queue = BinaryHeap::new();

// Let's enqueue some jobs:
queue.push(EmailJob { kind: EmailKind::Welcome, user_id: "user#1".to_string() });
queue.push(EmailJob { kind: EmailKind::Marketing, user_id: "user#1".to_string() });
queue.push(EmailJob { kind: EmailKind::OrderInvoice, user_id: "user#1".to_string() });
queue.push(EmailJob { kind: EmailKind::Welcome, user_id: "user#2".to_string() });

// And then we dequeue & process every job:
while let Some(job) = queue.pop() {
    process_email_job(&job);
}

Sauf que ça ne suffit pas ! Si on essaie de faire tourner tout ça, le compilateur nous signale que notre type EmailJob n'implémente pas le trait std::cmp::Ord. En effet, il n'est pas ordonnable sur la priorité.

Décorons avec la priorité

Comment pourrait-on décorer notre job avec une priorité, sans trop changer le type de job en lui-même ni son utilisation ? Nous allons essayer de l'enrober dans un type qui sera lui-même ordonnable sur une notion de priorité :

struct Prioritized<T, P> {
    inner: T, // contain the actual data
    priority: P, // carries the priority
}

Notez l'utilisation de types génériques : peu m'importe le type qui représentera la priorité, et encore moins celui qui sera decoré.

Ajoutons une petite fonction permettant de créer facilement des décorations :

fn prioritize<T, P>(value: T, priority: P) -> Prioritized<T, P> {
    Prioritized { inner: value, priority }
}

Et enfin, implémentions le trait Ord ainsi que ceux qui lui sont nécessaires, en délégant le calcul de l'ordre au champ priority :

impl<T, P: PartialEq> PartialEq for Prioritized<T, P> {
    fn eq(&self, other: &Self) -> bool {
        self.priority == other.priority
    }
}

impl<T, P: Eq> Eq for Prioritized<T, P> {}

impl<T, P: PartialOrd> PartialOrd for Prioritized<T, P> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.priority.partial_cmp(&other.priority)
    }
}

impl<T, P: Ord> Ord for Prioritized<T, P> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority.cmp(&other.priority)
    }
}

Pour terminer, on met à jour l'utilisation de la file pour prioriser nos jobs :

let mut queue = BinaryHeap::new();

queue.push(prioritize(EmailJob { kind: EmailKind::Welcome, user_id: "user#1".to_string() }, 1));
queue.push(prioritize(EmailJob { kind: EmailKind::Marketing, user_id: "user#1".to_string() }, -1));
queue.push(prioritize(EmailJob { kind: EmailKind::OrderInvoice, user_id: "user#1".to_string() }, 0));
queue.push(prioritize(EmailJob { kind: EmailKind::Welcome, user_id: "user#2".to_string() }, 1));

while let Some(prioritized_job) = queue.pop() {
    let job = &prioritized_job.inner;
    process_email_job(job);
}

Hourra, cela fonctionne ! Les jobs sont bien traités dans l'ordre de leur priorité : ceux enrobés dans une priorité plus grande en premier, jusqu'à traiter celui à la plus faible priorité.

Obtenir la valeur enrobée avec Deref

Il reste un petit truc qui me chagrine : j'ai dû changer la façon de dépiler les jobs, car je dois désormais aller extraire le job de son enrobage de priorisation.
Or, si ça ne me gêne pas trop d'enrober dans la priorité lorsque j'envoie le job dans le file d'attente, j'aimerais que ce soit un peu plus transparent au dépilage, car la notion de priorité est probablement moins intéressante à ce moment-là.

Pour obtenir ce comportement, je me suis inspiré du type standard Box, que l'on peut déréférencer pour obtenir le contenu de la boîte.
Il est possible de permettre ce déréférencement en implémentant nous-même les traits Deref (et le cas échéant DerefMut), comme le fait le type Box :

impl<T, P> Deref for Prioritized<T, P> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        &self.inner
    }
}

impl<T, P> DerefMut for Prioritized<T, P> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.inner
    }
}

Nous pouvons ensuite rétablir la boucle du dépilage des jobs comme nous l'avions écrit précédemment, sans avoir à nous préoccuper du fait que notre job est décoré par le type Prioritized : la valeur est implicitement déréférencée.

while let Some(job) = queue.pop() {
    process_email_job(&job);
}

Voici le résultat final.

À noter que je ne suis pas certain que cette utilisation des traits Deref et DerefMut soit nécessairement une bonne idée. Cela permet certes de manipuler des valeurs décorées un peu comme si elles ne l'étaient pas, mais parfois, l'explicite est une meilleure idée que l'implicite.
Peut-être l'opérateur de déréférencement devrait-il être réservé aux types du genre smart pointers comme l'est le type Box.

Si on souhaite présenter une API simple tout en conservant le mécanisme de décoration, on devrait peut-être plutôt encapsuler le BinaryHeap dans une structure dédiée, et exposer des méthodes permettant d'ajouter et récupérer les données dedans. Ce serait alors le rôle de ces méthodes de gérer la décoration et l'extraction des valeurs de la file (tiens, voilà une autre idée de billet de blog…).

Dans tous les cas, ce petit exemple aura au moins eu le mérite de me faire mieux comprendre ce qu'il se passe lorsqu'on utilise le type Box, et comment mettre en place ce comportement dans mes propres types en implémentant les bons traits.

Apprenons Rust : décorer nos types

En utilisant les traits Deref et DerefMut

Introduction

Exemple : une file de jobs priorisée

Décorons avec la priorité

Obtenir la valeur enrobée avec Deref