Paradigmes 2023-2024 - TP 3

Etienne Lozes

Exercice 1. Pile non mutable partageable

Traduire en Rust le code Caml suivant. Vous utiliserez le pointeur intelligent Rc pour permettre le partage, un trait pour représenter la signature PersistentStack, et un type (struct/enum) de Rust pour le module ListStack.

Vous n'avez pas droit aux Vec, il faut implémenter la pile avec une liste chaînée, comme en Caml.

Testez votre code avec le test ci-dessous.

Code OCaml à traduire

module type PersistentStack = sig
    type 'a t
    val empty: 'a t
    val is_empty: 'a t -> bool
    val push: 'a -> 'a t -> 'a t
    val pop: 'a t -> ('a * 'a t) option
end

module ListStack : PersistentStack = struct
    type 'a t = 'a list
    let empty = []
    let is_empty s = s = []
    let push x s = x :: s
    let pop = function
        | [] -> None
        | x :: xs -> Some (x, xs)
end

Test Rust à faire passer

#[cfg(test)]
mod test_list_stack {
    use super::{PersistentStack, ListStack};
    
    #[test]
    fn test_empty() {
        let s1 : ListStack<i8> = <_>::empty();
        let s2 = s1.push(1);
        let (_, s3) = s2.pop().unwrap();
        assert!(s1.is_empty());
        assert!(!s2.is_empty());
        assert!(s3.is_empty());
    }
    #[test]
    fn test_push_pop() {
        let s1: ListStack<i8> = ListStack::empty();
        let s2 = s1.push(1);
        let (one, _) = s2.pop().unwrap();
        assert_eq!(one, 1);
    }
    #[test]
    fn test_push_push_pop_pop() {
        let s1: ListStack<i8> = ListStack::empty();
        let s2 = s1.push(1).push(2);
        let (two, s3) = s2.pop().unwrap();
        let (one, s4) = s3.pop().unwrap();
        assert_eq!(one, 1);
        assert_eq!(two, 2);
        assert!(s4.pop().is_none());
    }
}

Exercice 2. Chargeur de fichiers

Le but de cet exercice est d'implémenter le trait suivant

use std::error::Error;

trait FileLoader {

    // allocates a new file loader
    fn new() -> Self;

    // returns the entire content of the (text) file
    fn load(&self, path: &str) -> Result<Rc<str>, Box<dyn Error>>;

}

1. Donnez une implémentation triviale BasicFileLoader de ce trait avec un struct sans champs. Vous pourrez utiliser la fonction read_to_string du module std::fs.

Testez votre code (par exemple, en créant un fichier et en affichant son contenu via le code suivant).

let fl = BasicFileLoader::new();
let content = fl.load("exemple.txt")?;
print!("{content}");

2. Donnez une implémentation CachedFileLoader du trait FileLoader qui met en cache le contenu du fichier, de sorte que si on charge deux fois de suite le même fichier avec load, on puisse renvoyer le contenu du fichier la deuxième fois sans le lire à nouveau via fs::read_to_string.

Vous ajouterez un champs privé (en définissant CachedFileLoader dans un module) que vous appelerez cache et dont le type sera "à peu près" HashMap<&str, Rc<str>>. Si vous ne voyez pas pourquoi je dis "à peu près", essayez avec ce type exactement. Quel patron de mutabilité vous semble-t-il nécessaire de mettre en oeuvre? Le cours vous suggère au moins deux solutions à l'aide des deux pointeurs intelligents Cell et RefCell. Choisissez, et si vous avez le temps, testez les deux.

3. [Optionnel] Notre chargeur de fichier a un petit défaut: si le fichier a été modifié depuis la mise en cache, il faudrait le relire et mettre le cache à jour. Proposez une solution pour détecter lorsqu'il est nécessaire de mettre le cache à jour.

Exercice 3. Fuite et fin

1. Reprenez l'exemple de fuite mémoire avec une liste circulaire non mutable partageable via des Rc vu en cours. En redéfinissant la méthode drop des cellules de listes pour espionner le moment où elles sont relâchées, vérifiez qu'il y a bien une fuite mémoire.

2. Définissez une structure de donnée pour représenter un liste circulaire dont la première cellule (pointée par une variable) est référencée par la dernière cellule via un pointeur faible. Construisez une telle liste, et vérifiez la liste est bien désallouée lorsque la variable la contenant est lâchée.