Rust, struct, Vec, et borrow checker

Salut tout le monde,

J’ai un problème avec le borrow checker de Rust. Voici un bout de code qui représente ce que j’essaye de faire :

struct Foo {
    bars: Vec<Bar>,
}

impl Foo {
    pub fn create_bar(&mut self) -> &mut Bar {
        bars.push(Bar::new());

        match bars.last_mut() {
            Some(v) => v,
            None => panic!("Can't go here"),
        }
    }
}

fn main() {
    let mut foo = Foo {
        bars: vec![],
    };

    let bar_1 = foo.create_bar();
    let bar_2 = foo.create_bar();

    // some manipulation with bar_1 and bar_2 together
}

• Les Bar sont contenus dans Foo car ils appartiennent à Foo : quand Foo est détruit, ils doivent l’être aussi
• Malgré tout, il faut bien que les Bar soit manipulables, d’où le retour de référence
• Pour une raison qui je pense ne doit pas nous intéresser ici, j’ai besoin après ce code de manipuler les deux Bar ensemble

Ce code ne compile pas, j’obtiens une erreur de ce type :

error[E0499]: cannot borrow `foo` as mutable more than once at a time
  --> main.rs:22
   |
21 |         let bar_1 = foo.create_bar();
   |                     -- first mutable borrow occurs here
22 |         let bar_2 = foo.create_bar();
   |                     ^^ second mutable borrow occurs here
...
24 |         // some manipulation with bar_1 and bar_2 together
   |             --------------- first borrow later used here

Visiblement pour le compilateur, manipuler simultanément deux références mutables sur deux éléments différents et indépendants, contenus d’une manière ou d’une autre dans un même agrégat, revient à manipuler simultanément deux références mutables sur ce même agrégat.

Pourquoi ? En quoi cela a-t-il un intérêt contre les data races ? Je ne comprends pas.

De plus, pour retourner une référence, je n’ai pas d’autre moyen que cet horrible match. Là encore, le compilateur est "trop bête" pour savoir qu’il y a forcément un dernier élément puisque je viens d’en insérer un. Je sens bien que je ne dois pas m’y prendre correctement, mais je ne vois pas d’autre moyen. Si je crée d’abord la valeur, puis que je la déplace dans le Vec via push, puis que je renvoie une référence sur cette valeur, j’ai une erreur car je référence une valeur qui a été déplacée.

Une autre piste que j’ai déjà essayée est d’utiliser des Rc<RefCell<Bar>>. Ça marche, mais ça a plusieurs gros défauts à mes yeux :

• Je trouve qu’on perd un peu l’intérêt de Rust, et de ses vérifications compile-time. Si c’est à la charge du développeur d’écrire minutieusement son code pour éviter que le programme crashe par un panic! de RefCell, ça n’a pas beaucoup de différence avec écrire minutieusement son code pour éviter les data races.
• Utiliser RefCell ajoute du code inutile à l’exécution. En effet, du code est exécuté afin d’apporter les garanties qui sont déjà apportées par le développeur s’il ne veut pas que son programme crashe. Dans le coeur d’une librairie, dans des chemins de code qui seront potentiellement utilisés des centaines de fois par seconde, ces instructions inutiles sont inacceptables pour les performances.
• Le défaut majeur à mes yeux : ça rend surtout le code diablement illisible. Il faut ajouter des Rc::clone, .borrow() et .borrow_mut() partout, y compris dans le code de l’utilisateur de la librairie. La rigidité des borrowing rules empêche de stocker une référence pour effectuer plusieurs opérations d’affilée sur une structure via ses méthodes, il faut ajouter des .borrow() éphémères à chaque ligne. Ce n’est pas maintenable.

Les autres pistes auxquelles j’ai pensées :

• remplacer le Vec par un HashMap avec des IDs uniques à la place des références. On perd tout l’intérêt des références et des garanties qui vont avec, et on ajoute du code inutile à l’exécution
• faire du code unsafe et manipuler des raw pointers, là encore on perd tout l’intérêt de Rust
• renvoyer un slice du Vec au lieu d’une référence sur élément, mais je crois que ça ne change rien au problème, c’est toujours une référence sur une partie de Foo

Une autre piste que j’ai également explorée : inverser l’appartenance. Au lieu d’avoir l’appartenance à l’intérieur et des références à l’extérieur, laisser l’appartenance à l’extérieur et avoir des références à l’intérieur garantissant que Bar ne survit pas à Foo. Cela implique d’utiliser des lifetimes. Mais cela me pose deux problèmes :

• Ça a sémantiquement moins de sens : conceptuellement Bar appartient à Foo et l’utilisateur l’emprunte pour effectuer des opérations, mais dans l’implémentation c’est l’inverse
• C’est peut-être moi, mais je trouve l’utilisation des lifetimes encore moins maintenable que des Rc<RefCell>… Là encore, cela implique de mettre des lifetimes absolument partout, les lifetimes c’est compliqué (pour l’ensemble de ma librairie, qui va un peu au-delà du problème que j’ai décrit ici, je n’ai pas encore réussi à aboutir à une version qui compile), et cela se propage dans toutes les structures parentes, y compris les éventuelles structures de l’utilisateur de la librairie dans lesquelles il voudrait stocker des objets de la librairie.

Tout cela semble indiquer que de manière générale, ma modélisation n’est pas adaptée. Stocker des enfants dans un Vec et y donner accès par références pour permettre de les manipuler en-dehors de la structure ne semble pas être un pattern permis en Rust, à moins de produire, pour un problème vraiment basique, du code illisible et/ou extraordinairement compliqué à base de Rc<RefCell> ou de lifetimes. Mais dans ce cas, comment exprimer l’appartenance et garantir la libération des ressources ?

Merci d’avance et bonne soirée !

Salut !

Visiblement pour le compilateur, manipuler simultanément deux références mutables sur deux éléments différents et indépendants, contenus d’une manière ou d’une autre dans un même agrégat, revient à manipuler simultanément deux références mutables sur ce même agrégat.

Pourquoi ? En quoi cela a-t-il un intérêt contre les data races ? Je ne comprends pas.

Il arrive effectivement que le programmeur soit plus intelligent que le compilateur et élimine un "faux positif" (une situation où le compilateur détecte une erreur qui n’existe pas). Mais dans le cas présent, imagine que lors de la création de bar_2, self.bars doit être redimensionné. Tu ne risque alors pas un data race mais bar_1 est une référence pointant sur un espace mémoire anciennement alloué et potentiellement libéré, hors, en Rust, une référence est toujours valide. Ce serait effectivement dangereux d’utiliser bar_1 dans ce cas de figure.

Une piste serait de ne pas renvoyer une référence mais un indice dans bars (la taille de bars avant l’insertion). Tu peux même cacher cet indice dans un type opaque comme ceci pour mieux respecter le principe d’encapsulation.

struct Reference {
    index: usize,
}

// Ou  encore
struct Reference(usize);

Évidemment, ça implique d’avoir accès au parent pour pouvoir les utiliser. Enfin, cette approche n’est pas la seule possible, évite simplement d’utiliser des références.

De plus, pour retourner une référence, je n’ai pas d’autre moyen que cet horrible match. Là encore, le compilateur est "trop bête" pour savoir qu’il y a forcément un dernier élément puisque je viens d’en insérer un. Je sens bien que je ne dois pas m’y prendre correctement, mais je ne vois pas d’autre moyen. Si je crée d’abord la valeur, puis que je la déplace dans le Vec via push, puis que je renvoie une référence sur cette valeur, j’ai une erreur car je référence une valeur qui a été déplacée.

Tu peux utiliser la méthode Option::unwrap qui est équivalente à ton match mais en bien plus lisible.

Hello,

Merci pour ta réponse. Effectivement, la mémoire d’un vecteur peut être réallouée. Je n’y avais pas pensé, mais tu m’as fait réaliser que j’aurais en fait le même problème en C++.

Je n’aime pas la solution qui consiste à utiliser un index. Si je donne un index au développeur final, impossible de mettre à jour cet index si le vecteur est modifié. Charge à lui de savoir qu’il obtient un index et qu’il doit mettre à jour tous ses indexes en adéquation avec les opérations effectuées. Si c’est pour faire ça, autant faire du C.

Mais du coup, comme je me suis rendu compte que j’aurais le même problème en C++, je me suis demandé comment je ferais en C++. Ce que je ferais, c’est stocker un vecteur de pointeurs et allouer chaque élément indépendamment, ce qui permet de renvoyer des pointeurs qui restent valides indépendamment des opérations effectuées sur le vecteur.

J’ai donc essayé cette solution, à base de Box :

struct Foo {
    bars: Vec<Box<Bar>>,
}

impl Foo {
    pub fn create_bar(&mut self) -> &mut Bar {
        bars.push(Box::new(Bar::new()));

        &mut *self.bars.last_mut().unwrap() // merci pour le tip ! ça me semble toujours un peu absurde, mais au moins c'est concis
    }
}

fn main() {
    let mut foo = Foo {
        bars: vec![],
    };

    let bar_1 = foo.create_bar();
    let bar_2 = foo.create_bar();

    // some manipulation with bar_1 and bar_2 together
}

Et… j’ai le même problème malgré tout. Rust continue de penser que je borrow plusieurs fois foo en même temps.

Wtf !?

EDIT : Après quelques recherches, j’ai compris pourquoi cela pose problème. Si je mutable borrow foo, je peux potentiellement modifier le vecteur pour par exemple supprimer un élément que j’ai référencé, donc potentiellement créer une dangling reference. Le fait est que je mutable borrow foo pour ajouter un élément, pas pour en supprimer un, mais le compilateur n’en sait rien. J’ai compris le problème, je n’ai par contre toujours pas la solution.

Pour le coup, oui, c’est un problème inhérent à Rust. Le fait est que rustc part du principe que si tu borrow un objet avec une référence mutable, tu peux alors invalider une référence, ou encore accéder en écriture à des objets enfants quel que soit le code de la fonction appelée. Rendre le borrow-checker plus intelligent fait partie des défis auxquels est confronté Rust et il a déjà bien évolué depuis la première version stable. Mais pour l’instant, on est effectivement coincés à devoir faire avec les règles actuelles. Tu risques effectivement de devoir utiliser du code unsafe en exposant à l’utilisateur une interface safe.

Mais je vois mal comment. En fait, c’est assez dur de déterminer ce qu’il y a de mieux étant donné que je ne sais pas ce que tu veux faire. C’est relativement peu courant de vouloir garder longtemps une référence sur un objet possédé par une collection, généralement quand on utilise une collection, c’est justement car on ne veut pas garder de référence sur l’objet en dehors de la collection. Est-ce Foo ou le code appelant qui est "vraiment" censé posséder l’objet référencé ? Ou est-ce une propriété collective (qui pourrait être implémentée avec Rc ou Arc dans le cas d’un contexte multithread).

C’est peu courant ? C’est pourtant le cas dès qu’on a une hiérarchie d’objets avec des relations 1-N non ?

En l’occurrence, mon objet Bar représente une ressource externe qui doit être détruite soit quand Foo est détruit, soit prématurément par l’utilisateur. En gros dès que le compteur de références tombe à 1.

Ah, mais c’est qu’une référence n’est pas du tout adaptée à ton cas de figure dans ce cas. Détruire une référence mutable ne détruit pas l’objet pointé parce qu’on n’a pas l'ownership de cet objet. Il faudrait partir sur un type personnalisé utilisant la mutabilité interne (comme Box ou Rc) qui donnerait accès à Some(ref) avec ref une référence mutable sur l’objet géré ou None s’il a été détruit parce que le compteur de référence est tombé à 1. Enfin, là encore, c’est difficile d’en dire plus.

Et implémenter ce genre de structure risque d’être plus ou moins compliqué, donc je pense qu’il vaudrait peut-être mieux partir sur un autre design, mais, comme dit plus tôt, impossible d’en dire plus sans savoir ce que tu veux faire.