Recursively traverse a graph/tree while mutating it

help
1

Is there a way of making update() recursively call itself and mutate Graph?

I naively tried to change the signature of update() to update(&mut self, ...) which resulted in errors related in single-mutable-reference constraints.

struct foo {
    val: i16
}
struct bar {
    x: foo
}
struct Graph {
    nodes: Vec<bar>
}

impl Graph {

    pub fn update(&self, item: &foo) -> Result<i16, String> {
        if (/* `item` meets some condition */) {
            return Ok(item.val);
        }
        let idx = compute_an_index(item) // compute an index into `nodes`...
        let node = &self.nodes[idx];
        
        // I want to mutate 'node.x' before the recursive call:
        // node.x.val += 1
        return self.update(&node.x)
 
}

Any input is appreciated.

2

In this case, I think it would be easiest to pass the next index as an argument, not the &foo reference. Another solution, depending on the size of the real foo, would be to pass item by value (self.update(node.x) if it is Copy, otherwise clone it).

1 Like
3

Ah...I'm not looking forward to these kinds of problems as I port a graph data structure myself.

There is the easy way out if it's not too expensive for your needs. Make sure that Foo impls Copy and/or Clone and just copy/clone the node's value before passing it in recursively.

// If Foo: Copy, pass it in by value.
pub fn update1(&mut self, item: Foo) -> Result<i16, String> {
    if item.val == 0 /* `item` meets some condition */ {
        return Ok(item.val);
    }
    let idx = compute_an_index(&item); // compute an index into `nodes`...
    let foo = {
        let node = &mut self.nodes[idx];
        node.x.val += 1;
        node.x
    };
    return self.update1(foo);
}

// If Foo: Clone
pub fn update2(&mut self, item: &Foo) -> Result<i16, String> {
    if item.val == 0 /* `item` meets some condition */ {
        return Ok(item.val);
    }
    let idx = compute_an_index(item); // compute an index into `nodes`...
    let foo = {
        let node = &mut self.nodes[idx];
        node.x.val += 1;
        node.x.clone()
    };
    return self.update2(&foo);
}

But if you really don't want to do that because Foo is some significant payload that you would rather not clone, then you can use unsafe code as long as you can locally guarantee that the mutable reference to Node is neither mutated nor nuked from memory (due to array reallocation). Avoid this option if you can, especially for complex algorithms (see also the Rustonomicon for an extended treatment of all the things to consider). Given that, here goes nothing:

// Unsafe magic ONLY if you really, really, REALLY need it.
unsafe fn self_and_node(&mut self, idx: usize) -> (&mut Self, &mut Bar) {
    let s = self as *mut Self;
    let node = &mut self.nodes[idx];
    (&mut *s, node)
}
pub fn update3(&mut self, item: &Foo) -> Result<i16, String> {
    if item.val == 0 /* `item` meets some condition */ {
        return Ok(item.val);
    }
    let idx = compute_an_index(item); // compute an index into `nodes`...
    let (s, node) = unsafe { self.self_and_node(idx) }; // ~SCARY~ :D
    node.x.val += 1;
    return s.update3(&node.x);
}

Playground link with all of these

1 Like
4

thank you both for your suggestion.
I combined both of your ideas, i.e. went with implementing Clone and using index to traverse the tree.
But indeed implementing these type of data structures seems challenging to me while I am learning the language.