Collecting a vector of references through recursive descent

I'm still having trouble getting lifetimes correct for functions building vectors of references.

The following code builds up a recursive data structure for a family tree using Person node elements.

The problem I'm having is in the method Person::collect() where I wish to build and return a Vec<&Person> collection holding the Person objects where the passed in closure returns true.

At the end of main() this function is used with the hopes of obtaining a Vector holding references to all Person for people in their 50's.

Here's the code and following that the error I get compiling it.

struct Person<'a> {
    name: &'a str,
    age: i32,
    children: Vec<Person<'a>>,
}
impl<'a> Person<'a> {
    fn new(name: &'a str, age: i32) -> Person<'a> {
        Person {
            name: name,
            age,
            children: Vec::new(),
        }
    }
    fn add(&mut self, name: &'a str, age: i32) -> &mut Person<'a> {
        self.children.push(
            Self::new(name, age)
        );
        self
    }
    fn show(&self) {
        self.show_w_tab(0);
    }
    fn show_w_tab(&self, tab: usize) {
        println!("{:>1$}, {age} yrs old",
            self.name, tab + self.name.len(), age=self.age);
    }
    fn show_r(&self, tab: usize) {
        self.show_w_tab(tab);
        for c in self.children.iter() {
            c.show_r(tab + 4);
        }
    }
    fn show_family_tree(&self) {
        self.show_r(0)
    }
    fn collect_r<'b>(&'a self, result: &'b mut Vec<&'a Person<'a>>,
            filter: fn(&'a Person) -> bool) {
        if filter(self) {
            result.push(self);
        }
        for c in self.children.iter() {
            c.collect_r(result, filter);
        }
    }
    fn collect(&self, filter: fn(&Person) -> bool) -> Vec<&Self> {
        let mut result: Vec<&Person>;
        self.collect_r(&mut result, filter);
        result
    }
}

fn main() {
    let mut person1 = Person::new("Ruth", 120);
    person1
        .add("Pat", 91)
        .add("John", 89);
        
    person1.children[0]
        .add("Jim", 65)
        .add("Chuck", 65);
        
    person1.children[1]
        .add("Stan", 57)
        .add("Anne", 55);
        
    person1.children[1].children[1]
        .add("Helena", 21)
        .add("Peter", 19);

    person1.show_family_tree();

    let fifties = person1.collect(|p| p.age >= 50 && p.age < 60);
    println!("fifties...");
    for p in fifties.iter() {
        p.show();
    }
}

Here are the errors, and when I try to fix them I just get more errors that confuse the matter even more.

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/main.rs:49:14
   |
49 |         self.collect_r(&mut result, filter);
   |              ^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime defined on the method body at 47:16...
  --> src/main.rs:47:16
   |
47 |     fn collect(&self, filter: fn(&Person) -> bool) -> Vec<&Self> {
   |                ^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:49:9
   |
49 |         self.collect_r(&mut result, filter);
   |         ^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 8:6...
  --> src/main.rs:8:6
   |
8  | impl<'a> Person<'a> {
   |      ^^
note: ...so that the expression is assignable
  --> src/main.rs:50:9
   |
50 |         result
   |         ^^^^^^
   = note: expected `Vec<&Person<'a>>`
              found `Vec<&Person<'_>>`

error: aborting due to previous error

You have collect_r requiring the total lifetime 'a, but collect has an anonymous &self lifetime that can be shorter. You could make that stricter:

    fn collect(&'a self, filter: fn(&Person) -> bool) -> Vec<&'a Self> {

Or you could relax the other way, borrowing a reference from &self that can be shorter:

    fn collect_r<'s>(&'s self, result: &mut Vec<&'s Person<'a>>,
            filter: fn(&Person) -> bool) {
1 Like

Fantastic! Thank you very much. I was closer than I realized. Below code now compiles and works thanks to your first suggestion. (I cleared up the error due to an uninitialized Vec in collect().)

My next challenge is to make that a vector of mutable references that gets collected, that would allow changing the underlying nodes age by adding one year (for example.) I am afraid that will require unsafe raw pointers however.

struct Person<'a> {
    name: &'a str,
    age: i32,
    children: Vec<Person<'a>>,
}
impl<'a> Person<'a> {
    fn new(name: &'a str, age: i32) -> Person<'a> {
        Person {
            name: name,
            age,
            children: Vec::new(),
        }
    }
    fn add(&mut self, name: &'a str, age: i32) -> &mut Person<'a> {
        self.children.push(
            Self::new(name, age)
        );
        self
    }
    fn show(&self) {
        self.show_w_tab(0);
    }
    fn show_w_tab(&self, tab: usize) {
        println!("{:>1$}, {age} yrs old",
            self.name, tab + self.name.len(), age=self.age);
    }
    fn show_r(&self, tab: usize) {
        self.show_w_tab(tab);
        for c in self.children.iter() {
            c.show_r(tab + 4);
        }
    }
    fn show_family_tree(&self) {
        self.show_r(0)
    }
    fn collect_r<'b>(&'a self, result: &'b mut Vec<&'a Person<'a>>,
            filter: fn(&'a Person) -> bool) {
        if filter(self) {
            result.push(self);
        }
        for c in self.children.iter() {
            c.collect_r(result, filter);
        }
    }
    fn collect(&'a self, filter: fn(&Person) -> bool) -> Vec<&'a Self> {
        let mut result: Vec<&Person> = Vec::new();
        self.collect_r(&mut result, filter);
        result
    }
}

fn main() {
    let mut person1 = Person::new("Ruth", 120);
    person1
        .add("Pat", 91)
        .add("John", 89);
        
    person1.children[0]
        .add("Jim", 65)
        .add("Chuck", 65);
        
    person1.children[1]
        .add("Stan", 57)
        .add("Anne", 55);
        
    person1.children[1].children[1]
        .add("Helena", 21)
        .add("Peter", 19);

    person1.show_family_tree();

    let fifties = person1.collect(|p| p.age >= 50 && p.age < 60);
    println!("fifties...");
    for p in fifties.iter() {
        p.show();
    }
}

Output:

Ruth, 120 yrs old
    Pat, 91 yrs old
        Jim, 65 yrs old
        Chuck, 65 yrs old
    John, 89 yrs old
        Stan, 57 yrs old
        Anne, 55 yrs old
            Helena, 21 yrs old
            Peter, 19 yrs old
fifties...
Stan, 57 yrs old
Anne, 55 yrs old



So here's my attempt to modify the Person::collect() from my last version (which works great as a Vector of immutable Person references) and make it into one that collects a Vector of mutable references. You can see the main code now tries to add one year of age to each Person found in their fifties.

struct Person<'a> {
    name: &'a str,
    age: i32,
    children: Vec<Person<'a>>,
}
impl<'a> Person<'a> {
    fn new(name: &'a str, age: i32) -> Person<'a> {
        Person {
            name: name,
            age,
            children: Vec::new(),
        }
    }
    fn add(&mut self, name: &'a str, age: i32) -> &mut Person<'a> {
        self.children.push(
            Self::new(name, age)
        );
        self
    }
    fn show(&self) {
        self.show_w_tab(0);
    }
    fn show_w_tab(&self, tab: usize) {
        println!("{:>1$}, {age} yrs old",
            self.name, tab + self.name.len(), age=self.age);
    }
    fn show_r(&self, tab: usize) {
        self.show_w_tab(tab);
        for c in self.children.iter() {
            c.show_r(tab + 4);
        }
    }
    fn show_family_tree(&self) {
        self.show_r(0)
    }
    fn collect_r<'b>(&'a mut self, result: &'b mut Vec<&'a mut Person<'a>>,
            filter: fn(&'a Person) -> bool) {
        if filter(self) {
            result.push(self);
        }
        for c in self.children.iter_mut() {
            c.collect_r(result, filter);
        }
    }
    fn collect(&'a mut self, filter: fn(&Person) -> bool) -> Vec<&'a mut Self> {
        let mut result: Vec<&mut Person> = Vec::new();
        self.collect_r(&mut result, filter);
        result
    }
}

fn main() {
    let mut person1 = Person::new("Ruth", 120);
    person1
        .add("Pat", 91)
        .add("John", 89);
        
    person1.children[0]
        .add("Jim", 65)
        .add("Chuck", 65);
        
    person1.children[1]
        .add("Stan", 57)
        .add("Anne", 55);
        
    person1.children[1].children[1]
        .add("Helena", 21)
        .add("Peter", 19);

    person1.show_family_tree();

    let mut fifties = person1.collect(|p| p.age >= 50 && p.age < 60);
    println!("fifties...");
    for p in fifties.iter_mut() {
        p.age += 1;
        p.show();
    }
}

The compiler error below is what makes me think I need to drop into unsafe code to collect a set of mutable raw pointers because the borrow checker doesn't want to keep mutable references around.

error[E0502]: cannot borrow `*self` as mutable because it is also borrowed as immutable
  --> src/main.rs:41:13
   |
8  | impl<'a> Person<'a> {
   |      -- lifetime `'a` defined here
...
40 |         if filter(self) {
   |            ------------
   |            |      |
   |            |      immutable borrow occurs here
   |            argument requires that `*self` is borrowed for `'a`
41 |             result.push(self);
   |             ^^^^^^^^^^^^^^^^^ mutable borrow occurs here

error[E0502]: cannot borrow `self.children` as mutable because it is also borrowed as immutable
  --> src/main.rs:43:18
   |
8  | impl<'a> Person<'a> {
   |      -- lifetime `'a` defined here
...
40 |         if filter(self) {
   |            ------------
   |            |      |
   |            |      immutable borrow occurs here
   |            argument requires that `*self` is borrowed for `'a`
...
43 |         for c in self.children.iter_mut() {
   |                  ^^^^^^^^^^^^^ mutable borrow occurs here

error: aborting due to 2 previous errors

You simply cannot create a mutable reference to a struct (Person<'a>) and also a mutable reference to something inside of one of its fields (e.g. an element of a vector that’s a field of that struct).

If you could, you could then turn the mutable reference to the outer struct into another mutable reference to the Person in it’s children vector. Two mutable references to the same thing equals bad things in Rust / isn’t allowed in Rust.

What you could do is separate the Person<'a> struct, splitting it into two parts, the name+age part and the children part, and then recursively fill a vector of mutable references just the name+age part.

Or, without modifying Person<'a>, you could create a vector of pairs of mutable references (&mut &'a str, &mut i32) referencing those fields that aren’t the children field. You could even turn that into another struct

struct PersonInfoMut<'b, 'a> {
    name: &'b mut &'a str,
    age: &'b mut i32
}

Then try implementing

fn collect<'b>(&'b mut self, filter: fn(&Person) -> bool) -> Vec<PersonInfoMut<'b, 'a>> 

By the way, note that even your shared-reference version

fn collect(&'a self, filter: fn(&Person) -> bool) -> Vec<&'a Self> 

is unnecessarily restrictive, requiring &'a Person<'a> (both lifetimes the same!) (see this playground for an access pattern that this restriction prohibits)

you should definitely change it to

fn collect<'b>(&'b self, filter: fn(&Person) -> bool) -> Vec<&'b Self> 

i.e. requiring self to be &'b Person<'a> (both lifetimes can be different!)

1 Like

Thank you for the information. All very helpful.

This happens to be a toy program and the real program is a Genetic Program where each tree is a Lisp S-Expression.

I wish to do the genetic operation known as crossover, and so the goal is ultimately to do a mem::swap over two tree node references between two different trees. Because of this I'm not able to make use of the suggestion to break off a "subset" of references.

So you want to swap nodes including their children, yet at the same time hold references to those children?

Yes I want to swap the node along with the child nodes.

I want to take two distinct trees, and for each build a "temporary" vector of qualifying references to be used as swap candidates.

I then want to randomly select one member from each temporary vector and perform a swap then drop the temporary vectors because I'm done with them.

I've already got my program able to randomly select one node from each tree and do the swap. I've been stumped for weeks on the seemingly simple "extension" problem to build a set of "candidate" nodes from each tree to do the same thing.

I'm going to try and post a version that does the swap using two candidate nodes, and then pose the problem as a vector of "candidate" swap nodes to make my problem more clear.

Okay here's the expanded example showing my problem. The main function now builds two trees. Picks two swap targets and does the swap.

(For historical purposes I'm leaving in the collect call that just grabs immutable references of people over fifty from tree1.)

Here's the code:

se std::mem;

struct Person<'a> {
    name: &'a str,
    age: i32,
    children: Vec<Person<'a>>,
}
impl<'a> Person<'a> {
    fn new(name: &'a str, age: i32) -> Person<'a> {
        Person {
            name: name,
            age,
            children: Vec::new(),
        }
    }
    fn add(&mut self, name: &'a str, age: i32) -> &mut Person<'a> {
        self.children.push(
            Self::new(name, age)
        );
        self
    }
    fn show(&self) {
        self.show_w_tab(0);
    }
    fn show_w_tab(&self, tab: usize) {
        println!("{:>1$}, {age} yrs old",
            self.name, tab + self.name.len(), age=self.age);
    }
    fn show_r(&self, tab: usize) {
        self.show_w_tab(tab);
        for c in self.children.iter() {
            c.show_r(tab + 4);
        }
    }
    fn show_family_tree(&self) {
        self.show_r(0)
    }
    fn collect_r<'b>(&'a self, result: &'b mut Vec<&'a Person<'a>>,
            filter: fn(&'a Person) -> bool) {
        if filter(self) {
            result.push(self);
        }
        for c in self.children.iter() {
            c.collect_r(result, filter);
        }
    }
    fn collect(&'a self, filter: fn(&Person) -> bool) -> Vec<&'a Self> {
        let mut result: Vec<&Person> = Vec::new();
        self.collect_r(&mut result, filter);
        result
    }
}

fn main() {
    let mut tree1 = Person::new("Ruth", 120);
    tree1
        .add("Pat", 91)
        .add("John", 89);
        
    tree1.children[0]
        .add("Jim", 65)
        .add("Chuck", 65);
        
    tree1.children[1]
        .add("Stan", 57)
        .add("Anne", 55);
        
    tree1.children[1].children[0]
        .add("Mary", 20);

    tree1.children[1].children[1]
        .add("Helena", 21)
        .add("Peter", 19);


    let fifties = tree1.collect(|p| p.age >= 50 && p.age < 60);
    println!("tree1 people in their fifties...");
    for p in fifties.iter() {
        p.show();
    }

    let mut tree2 = Person::new("Murial", 91);
    tree2
        .add("Maya", 55)
        .add("Matt", 59);
        
    tree2.children[0]
        .add("Julia", 26)
        .add("Andria", 28);

    tree2.children[0].children[0]
        .add("Tom", 2);

    println!("Before Swap");

    tree1.show_family_tree();
    tree2.show_family_tree();

    let swap_target1 = &mut tree1.children[1].children[0];
    let swap_target2 = &mut tree2.children[0].children[0];

    print!("swap target 1 is: "); swap_target1.show();
    print!("swap target 2 is: "); swap_target2.show();

    mem::swap(swap_target1, swap_target2);

    println!("After Swap");
    tree1.show_family_tree();
    tree2.show_family_tree();

}

Here's the output:

Before Swap
Ruth, 120 yrs old
    Pat, 91 yrs old
        Jim, 65 yrs old
        Chuck, 65 yrs old
    John, 89 yrs old
        Stan, 57 yrs old
            Mary, 20 yrs old
        Anne, 55 yrs old
            Helena, 21 yrs old
            Peter, 19 yrs old
Murial, 91 yrs old
    Maya, 55 yrs old
        Julia, 26 yrs old
            Tom, 2 yrs old
        Andria, 28 yrs old
    Matt, 59 yrs old
swap target 1 is: Stan, 57 yrs old
swap target 2 is: Julia, 26 yrs old
After Swap
Ruth, 120 yrs old
    Pat, 91 yrs old
        Jim, 65 yrs old
        Chuck, 65 yrs old
    John, 89 yrs old
        Julia, 26 yrs old
            Tom, 2 yrs old
        Anne, 55 yrs old
            Helena, 21 yrs old
            Peter, 19 yrs old
Murial, 91 yrs old
    Maya, 55 yrs old
        Stan, 57 yrs old
            Mary, 20 yrs old
        Andria, 28 yrs old
    Matt, 59 yrs old

The main function does these steps currently:

  1. It builds and displays the two trees.
  2. Picks two swap_target nodes
  3. It shows which nodes they are.
  4. It does the swap
  5. It then shows the trees after the swap is complete.

My goal is to insert a step 1a that builds two vectors of swap candidate nodes from each tree, and modify step 2 to randomly select the swap_targets from those two vectors.

In the worst case, an approach with Rc<RefCell<…>> is always an option. Here’s e.g. a linked list with those

use std::{cell::RefCell, rc::Rc};

struct LinkedList {
    head: Option<NodeRef>,
}

struct Node {
    value: i32,
    tail: Option<NodeRef>,
}

type NodeRef = Rc<RefCell<Node>>;

impl LinkedList {
    fn collect_nodes(&self) -> Vec<NodeRef> {
        let mut current = self.head.clone();
        let mut r = vec![];
        while let Some(node) = current {
            let next = node.borrow().tail.clone();
            r.push(node);
            current = next;
        }
        r
    }
}

fn swap_them(first: &NodeRef, second: &NodeRef) {
    std::mem::swap::<Node>(&mut first.borrow_mut(), &mut second.borrow_mut());
}

Another option is to use an arena with indices, e.g. generational_arena, though you’ll have to delete the elements from the arena manually if those lists/trees are shorter-lived than the arena. (And any trees/lists you want to swap between must be using the same arena.)

use generational_arena::{Arena, Index};

struct LinkedList {
    head: Option<Index>,
}

struct Node {
    value: i32,
    tail: Option<Index>,
}

// not handling creation or deletion in this example code

impl LinkedList {
    fn collect_nodes(&self, arena: &Arena<Node>) -> Vec<Index> {
        let mut current = self.head;
        let mut r = vec![];
        while let Some(node) = current {
            let next = arena[node].tail;
            r.push(node);
            current = next;
        }
        r
    }
}

fn swap_them(arena: &mut Arena<Node>, first: Index, second: Index) {
    let (first, second) = arena.get2_mut(first, second);
    std::mem::swap::<Node>(first.unwrap(), second.unwrap());
}

If you never need to delete anything, you can also use a Vec.

struct LinkedList {
    head: Option<usize>,
}

struct Node {
    value: i32,
    tail: Option<usize>,
}

// not handling creation in this example code
// deletion (usually) only happens when the whole `Vec` is dropped/cleared

impl LinkedList {
    fn collect_nodes(&self, arena: &[Node]) -> Vec<usize> {
        let mut current = self.head;
        let mut r = vec![];
        while let Some(node) = current {
            let next = arena[node].tail;
            r.push(node);
            current = next;
        }
        r
    }
}

fn swap_them(arena: &mut [Node], first: usize, second: usize) {
    arena.swap(first, second);
}

If you want a stronger connection between the indices and the arena, there’s crates like compact_arena, basically like a Vec, but you can’t cross-use indices (and the indices are smaller, too, to save space; OTOH it only supports up to u32-sized arenas)

use compact_arena::{Idx32, SmallArena};

struct LinkedList<'arena> {
    head: Option<Idx32<'arena>>,
}

struct Node<'arena> {
    value: i32,
    tail: Option<Idx32<'arena>>,
}

// not handling creation in this example code
// deletion (usually) only happens when the whole `SmallArena` is dropped/cleared

impl<'arena> LinkedList<'arena> {
    fn collect_nodes(&self, arena: &SmallArena<'arena, Node<'arena>>) -> Vec<Idx32<'arena>> {
        let mut current = self.head;
        let mut r = vec![];
        while let Some(node) = current {
            let next = arena[node].tail;
            r.push(node);
            current = next;
        }
        r
    }
}

fn swap_them<'arena>(
    arena: &mut SmallArena<'arena, Node<'arena>>,
    first: Idx32<'arena>,
    second: Idx32<'arena>,
) {
    // no way to get two mutable references at once :-(
    let dummy = Node {
        value: 0, 
        tail: None,
    };
    let first = std::mem::replace(&mut arena[first], dummy);
    let second = std::mem::replace(&mut arena[second], first);
    arena[first] = second;
}

A similar access pattern like with this last arena can also be done with ghost_cell, or the analogous type qcell::LCell (though, the qcell crate offers some more interesting alternatives, called TCell and QCell with different characteristics).

use qcell::{LCell, LCellOwner};
use std::rc::Rc;

struct LinkedList<'id> {
    head: Option<Rc<LCell<'id, Node<'id>>>>,
}

struct Node<'id> {
    value: i32,
    tail: Option<Rc<LCell<'id, Node<'id>>>>,
}

// deletion works by Rc’s again, also you don’t need the owner involved
// for creation, you only need it *after* creation to access anything

impl<'id> LinkedList<'id> {
    // no cloning of `Rc`s necessary!! :-))
    fn collect_nodes_refs<'a>(
        &'a self,
        owner: &'a LCellOwner<'id>,
    ) -> Vec<&'a Rc<LCell<'id, Node<'id>>>> {
        let mut current = &self.head;
        let mut r = vec![];
        while let Some(node) = current {
            let next = &node.ro(owner).tail;
            r.push(node);
            current = next;
        }
        r
    }

    // of course you *can* clone all those Rcs if you want to
    fn collect_nodes(&self, owner: &LCellOwner<'id>) -> Vec<Rc<LCell<'id, Node<'id>>>> {
        let mut current = self.head.clone();
        let mut r = vec![];
        while let Some(node) = current {
            let next = node.ro(owner).tail.clone();
            r.push(node);
            current = next;
        }
        r
    }
}

// You can use `collect_nodes_refs`, an then just clone just the (randomly
// selected) Rc’s you *need* to modify; drop all the `&'a Rc<…>`s, allowing for
// mutable access to the owner again, then you can swap them:
fn swap_them<'id>(
    owner: &mut LCellOwner<'id>,
    first: &LCell<'id, Node<'id>>,
    second: &LCell<'id, Node<'id>>,
) {
    let (first, second) = owner.rw2(first, second);
    std::mem::swap::<Node>(first, second);
}
1 Like

Thank you very much. I've got some serious learning to do!

So is there a general thread here that I'm missing? That in essence mutable references can be represented as tokens (i.e. indices) which can be in turn stored away for later usage as mutable references? Is that basically what is going on among these approaches?

If so, those tokens are essentially performing the role of what I was thinking I would be using mutable raw pointers for, but it would be up to my code to make sure I was not miss-using them.

It sure sounds as though dropping into unsafe code would NOT be the best solution since this would do the trick.

Took the challenge and tried working with LCell. This is what I came up with, trying to stay ergonomic to some extend

use qcell::{LCell, LCellOwner};
use std::{mem, rc::Rc};

struct PersonData<'a, 'id> {
    name: &'a str,
    age: i32,
    children: Vec<Person<'a, 'id>>,
}

#[derive(Clone)]
struct Person<'a, 'id>(Rc<LCell<'id, PersonData<'a, 'id>>>);
impl<'a, 'id> Person<'a, 'id> {
    fn new(name: &'a str, age: i32) -> Self {
        Person(Rc::new(LCell::new(PersonData {
            name,
            age,
            children: Vec::new(),
        })))
    }
    fn with_owner_mut<'r>(&'r self, owner: &'r mut LCellOwner<'id>) -> PersonMut<'a, 'id, 'r> {
        PersonMut {
            person: self,
            owner,
        }
    }
    fn with_owner<'r>(&'r self, owner: &'r LCellOwner<'id>) -> PersonRef<'a, 'id, 'r> {
        PersonRef {
            person: self,
            owner,
        }
    }
    fn show(&self, owner: &LCellOwner<'id>) {
        self.show_w_tab(owner, 0);
    }
    fn show_w_tab(&self, owner: &LCellOwner<'id>, tab: usize) {
        println!(
            "{:>1$}, {age} yrs old",
            self.0.ro(owner).name,
            tab + self.0.ro(owner).name.len(),
            age = self.0.ro(owner).age
        );
    }
    fn show_r(&self, owner: &LCellOwner<'id>, tab: usize) {
        self.show_w_tab(owner, tab);
        for c in self.0.ro(owner).children.iter() {
            c.show_r(owner, tab + 4);
        }
    }
    fn show_family_tree(&self, owner: &LCellOwner<'id>) {
        self.show_r(owner, 0)
    }
    fn collect_r<'b>(
        &'b self,
        owner: &'b LCellOwner<'id>,
        result: &mut Vec<&'b Self>,
        filter: &mut impl FnMut(&PersonData<'a, 'id>) -> bool,
    ) {
        if filter(self.0.ro(owner)) {
            result.push(self);
        }
        for c in self.0.ro(owner).children.iter() {
            c.collect_r(owner, result, filter);
        }
    }
    fn collect<'b>(
        &'b self,
        owner: &'b LCellOwner<'id>,
        mut filter: impl FnMut(&PersonData<'a, 'id>) -> bool,
    ) -> Vec<&'b Self> {
        let mut result: Vec<&Self> = Vec::new();
        self.collect_r(owner, &mut result, &mut filter);
        result
    }
}

struct PersonMut<'a, 'id, 'r> {
    person: &'r Person<'a, 'id>,
    owner: &'r mut LCellOwner<'id>,
}
impl<'a, 'id, 'r> PersonMut<'a, 'id, 'r> {
    fn add(self, name: &'a str, age: i32) -> Self {
        self.person
            .0
            .rw(self.owner)
            .children
            .push(Person::new(name, age));
        self
    }
}
struct PersonRef<'a, 'id, 'r> {
    person: &'r Person<'a, 'id>,
    owner: &'r LCellOwner<'id>,
}
impl<'a, 'id, 'r> PersonRef<'a, 'id, 'r> {
    fn get_child(&self, ix: usize) -> Option<PersonRef<'a, 'id, '_>> {
        self.person
            .0
            .ro(self.owner)
            .children
            .get(ix)
            .map(|person| PersonRef {
                person,
                owner: self.owner,
            })
    }
    fn clone_person(&self) -> Person<'a, 'id> {
        self.person.clone()
    }
}

fn main() {
    LCellOwner::scope(|mut owner| {
        let tree1 = Person::new("Ruth", 120);
        tree1
            .with_owner_mut(&mut owner)
            .add("Pat", 91)
            .add("John", 89);

        tree1
            .with_owner(&owner)
            .get_child(0)
            .unwrap()
            .clone_person()
            .with_owner_mut(&mut owner)
            .add("Jim", 65)
            .add("Chuck", 65);

        tree1
            .with_owner(&owner)
            .get_child(1)
            .unwrap()
            .clone_person()
            .with_owner_mut(&mut owner)
            .add("Stan", 57)
            .add("Anne", 55);

        tree1
            .with_owner(&owner)
            .get_child(1)
            .unwrap()
            .get_child(0)
            .unwrap()
            .clone_person()
            .with_owner_mut(&mut owner)
            .add("Mary", 20);

        tree1
            .with_owner(&owner)
            .get_child(1)
            .unwrap()
            .get_child(1)
            .unwrap()
            .clone_person()
            .with_owner_mut(&mut owner)
            .add("Helena", 21)
            .add("Peter", 19);

        let fifties = tree1.collect(&owner, |p| p.age >= 50 && p.age < 60);
        println!("tree1 people in their fifties...");
        for p in fifties.iter() {
            p.show(&owner);
        }

        let tree2 = Person::new("Murial", 91);
        tree2
            .with_owner_mut(&mut owner)
            .add("Maya", 55)
            .add("Matt", 59);

        tree2.0.ro(&owner).children[0]
            .clone()
            .with_owner_mut(&mut owner)
            .add("Julia", 26)
            .add("Andria", 28);

        tree2.0.ro(&owner).children[0].0.ro(&owner).children[0]
            .clone()
            .with_owner_mut(&mut owner)
            .add("Tom", 2);

        println!("Before Swap");

        tree1.show_family_tree(&owner);
        tree2.show_family_tree(&owner);

        let swap_target1 = tree1
            .with_owner(&owner)
            .get_child(1)
            .unwrap()
            .get_child(0)
            .unwrap()
            .clone_person();
        let swap_target2 = tree2
            .with_owner(&owner)
            .get_child(0)
            .unwrap()
            .get_child(0)
            .unwrap()
            .clone_person();

        print!("swap target 1 is: ");
        swap_target1.show(&owner);
        print!("swap target 2 is: ");
        swap_target2.show(&owner);

        let (swap_target1_mut, swap_target2_mut) = owner.rw2(&swap_target1.0, &swap_target2.0);
        mem::swap::<PersonData>(swap_target1_mut, swap_target2_mut);

        println!("After Swap");
        tree1.show_family_tree(&owner);
        tree2.show_family_tree(&owner);
    });
}

This features a lot of access pattern like

        tree1
            .with_owner(&owner)
            .get_child(1)
            .unwrap()
            .get_child(1)
            .unwrap()
            .clone_person()
            .with_owner_mut(&mut owner)
            .add("Helena", 21)
            .add("Peter", 19);

where the top part uses shared-reference access to move down the tree to some person, then it clones the Rc and ends the shared-reference access, so that it can borrow &mut owner and do some modification.


This can then be done with something like

        // candidates

        let fifties1 = tree1.collect(&owner, |p| p.age >= 50 && p.age < 60);

        let fifties2 = tree2.collect(&owner, |p| p.age >= 50 && p.age < 60);

        // random selection

        // TODO: replace the `0` with a (valid) random index
        let swap_target1 = fifties1[0].clone();
        let swap_target2 = fifties2[0].clone();
2 Likes

Are you sure you don't want Person to store its name?

In 99% of cases & in structs is an error, and you should have name: String (or Box<str>, which is a non-temporary not-haunting-with-annoying-lifetimes-everywhere equivalent of &str).

3 Likes

In my real program the nodes also have names, however all names are from a lazy static vector and exist at compile time, so I am storing them as &str. These trees represent Lisp S-expressions and if I were to build a real Lisp compiler I would want to have user defined symbols of course and so those would be names. I would probaby create an enum at that point and names known at compile time (e.g. keywords) would remain static and user defined names would become Strings.

1 Like

Thank you very much for the work and again showing I have much to learn!

I'm still motivated to search for a simpler solution and am not happy with the need to change the original architecture. (Along with rather complex code I've already written that creates the initial population of trees.) Your work has convinced me the solution I seek most likely will involve unsafe raw ptrs.

So here's my solution using unsafe rust. I was surprised how little code it took. I created an unsafe method Person::get_mut() that takes an immutable reference to Person and returns a mutable one. You already helped me build a vector of immutable references with collect(). So all I needed to do was grab a random element two vectors from collect() pass the get_mut() of each of those to mem::swap.

Here's the code. Please let me know if you think it'll be unsafe to use. As long as I take care to avoid operating on the same trees concurrently I believe it should work fine.

use std::mem;
use rand::Rng;

struct Person<'a> {
    name: &'a str,
    age: i32,
    children: Vec<Person<'a>>,
}
impl<'a> Person<'a> {
    fn new(name: &'a str, age: i32) -> Person<'a> {
        Person {
            name: name,
            age,
            children: Vec::new(),
        }
    }
    fn add(&mut self, name: &'a str, age: i32) -> &mut Person<'a> {
        self.children.push(
            Self::new(name, age)
        );
        self
    }
    fn show(&self) {
        self.show_w_tab(0);
    }
    fn show_w_tab(&self, tab: usize) {
        println!("{:>1$}, {age} yrs old",
            self.name, tab + self.name.len(), age=self.age);
    }
    fn show_r(&self, tab: usize) {
        self.show_w_tab(tab);
        for c in self.children.iter() {
            c.show_r(tab + 4);
        }
    }
    fn show_family_tree(&self) {
        self.show_r(0)
    }
    fn collect_r<'b>(&'a self, result: &'b mut Vec<&'a Person<'a>>,
            filter: fn(&'a Person) -> bool) {
        if filter(self) {
            result.push(self);
        }
        for c in self.children.iter() {
            c.collect_r(result, filter);
        }
    }
    fn collect(&'a self, filter: fn(&Person) -> bool) -> Vec<&'a Self> {
        let mut result: Vec<&Person> = Vec::new();
        self.collect_r(&mut result, filter);
        result
    }
    fn to_addr<'b>(&'b self) -> usize {
        let p: *const Self = self as *const Self;
        let addr: usize = p as usize;
        addr
    }
    unsafe fn mut_from_addr<'b>(address: usize) -> &'b mut Person<'a> {
        &mut *(address as *mut Self)
    }
    unsafe fn get_mut<'b>(&'b self) -> &'b mut Person<'a> {
        let addr = self.to_addr();
        Person::mut_from_addr(addr)
    }
}

fn main() {
    let mut tree1 = Person::new("Ruth", 120);
    tree1
        .add("Pat", 91)
        .add("John", 89);
        
    tree1.children[0]
        .add("Jim", 65)
        .add("Chuck", 65);
        
    tree1.children[1]
        .add("Stan", 57)
        .add("Anne", 55);
        
    tree1.children[1].children[0]
        .add("Mary", 20);

    tree1.children[1].children[1]
        .add("Helena", 21)
        .add("Peter", 19);

    let mut tree2 = Person::new("Murial", 91);
    tree2
        .add("Maya", 55)
        .add("Matt", 59);
        
    tree2.children[0]
        .add("Julia", 26)
        .add("Andria", 28);

    tree2.children[0].children[0]
        .add("Tom", 2);

    println!("Before Swap");
    tree1.show_family_tree();
    tree2.show_family_tree();

    // get people in their fifties for swap candidates
    let (fifties1, fifties2) =
        (tree1.collect(|p| p.age >= 50 && p.age < 60),
         tree2.collect(|p| p.age >= 50 && p.age < 60));

    println!("tree1 people in their fifties...");
    for p in fifties1.iter() {
        p.show();
    }

    println!("tree2 people in their fifties...");
    for p in fifties2.iter() {
        p.show();
    }

    let mut rng = rand::thread_rng();
    let swap_target1 =
        fifties1[rng.gen_range(0..fifties1.len())];
    let swap_target2 =
        fifties2[rng.gen_range(0..fifties2.len())];

    print!("swap target 1 is: "); swap_target1.show();
    print!("swap target 2 is: "); swap_target2.show();

    unsafe {
        mem::swap(swap_target1.get_mut(), swap_target2.get_mut());
    }

    println!("After Swap");

    tree1.show_family_tree();
    tree2.show_family_tree();
}

Next thing you'll be surprised about is how easy it is to run into undefined behavior in unsafe rust. Converting a &Person to &mut Person is absolutely forbidden even in unsafe rust even when going through an intermediate usize. Every instance of interior mutability in Rust must use UnsafeCell.

A good demonstration of the fact that there's a problem: run miri (under “Tools”) in this playground containing your code.

2 Likes

Interesting. Thanks for the advice. I'll take a look.

One thing worth mentioning is that even though I am forcing mutable from an immutable reference, the underlying memory that it points to is part of the recursive Person structure which is all mutable as far as rust is concerned. I.e. tree1 and tree2 are mutable variables-- and the mem swap works as long as the references are obtained and used as scalars.

This feels a lot like the case mentioned here: Borrow Splitting. Where the borrow checker just doesn't have enough information, but the optimizer will treat the structure I'm modifying as mutable internally. So it would seem mutating is safe here.

I did run miri and got a ton of output, but I'm not seeing or understanding the problem you refer to unfortunately. I'll keep looking.