Recursively traverse a tree to just mutate some fields

[Jinjiang]

A new comer, I'm trying to traverse a tree recursively to mutate some item fields without mutating the tree structure. The exec fn was expected with item, index, and the parent. Only the item fields need to be mutable.

So far what I've tried (some code was suggested by GitHub Copilot however):

fn main() {

    // data structure
    
    #[derive(Debug)]
    enum Extra {
        A(Bar),
        B(Baz),
    }
    #[derive(Debug)]
    struct Foo {
        a: i32,
        b: Extra,
    }
    #[derive(Debug)]
    struct Bar {
        c: i32,
        d: i32,
    }
    #[derive(Debug)]
    struct Baz {
        children: Vec<Foo>,
    }
    
    // iterate function
    
    fn iterate_foo(foo: &mut Foo, exec: fn(&mut Foo, usize, &Foo)) {
        match &mut foo.b {
            Extra::B(baz) => {
                baz.children.iter_mut().enumerate().for_each(|(index, child)| {
                    exec(child, index, foo);
                    iterate_foo(child, exec)
                });
            },
            _ => {},
        }
    }
    
    // test
    
    let mut foo_1 = Foo {
        a: 1,
        b: Extra::B(Baz {
            children: vec![
                Foo { a: 2, b: Extra::A(Bar { c: 3, d: 4 }) },
                Foo { a: 5, b: Extra::A(Bar { c: 6, d: 7 }) },
            ],
        }),
    };
    
    fn exec_foo(foo: &mut Foo, index: usize, parent: &Foo) {
        foo.a += 1;
        println!("foo.a: {:?}", foo.a);
        println!("index: {:?}", index);
        println!("parent: {:?}", parent);
    }
    
    iterate_foo(&mut foo_1, exec_foo);
}

Playground

The error message:

   Compiling playground v0.0.1 (/playground)
error[E0502]: cannot borrow `*foo` as immutable because it is also borrowed as mutable
  --> src/main.rs:30:62
   |
28 |         match &mut foo.b {
   |               ---------- mutable borrow occurs here
29 |             Extra::B(baz) => {
30 |                 baz.children.iter_mut().enumerate().for_each(|(index, child)| {
   |                                                     -------- ^^^^^^^^^^^^^^^^ immutable borrow occurs here
   |                                                     |
   |                                                     mutable borrow later used by call
31 |                     exec(child, index, foo);
   |                                        --- second borrow occurs due to use of `*foo` in closure

For more information about this error, try `rustc --explain E0502`.
error: could not compile `playground` (bin "playground") due to 1 previous error

any idea on how to make it works?

Thanks ahead.

[quinedot]

Despite the spelling, &mut _ aren't just mutable references, they are exclusive references. It's UB to have an exclusive reference which is aliased -- e.g. to have an active &mut _ that points to some location which you read through something that's not the &mut _.

In exec_foo, you're free to read all the data reachable from both foo: &mut Foo and parent: &Foo. So the compiler must not let you call exec_foo when the foo is reachable from the parent. And that's what the error is doing: preventing aliasing of the exclusive reference.

---

In this case instead of taking parent: &Foo you could take parent_data: i32 (or &ActualDataType or even &mut ActualDataType) in exec_foo.

    fn iterate_foo(foo: &mut Foo, exec: fn(&mut Foo, usize, &mut i32)) {
        match &mut foo.b {
            Extra::B(baz) => {
                baz.children.iter_mut().enumerate().for_each(|(index, child)| {
                    exec(child, index, &mut foo.a);
                    iterate_foo(child, exec)
                });
            },
            _ => {},
        }
    }

If you want access to the siblings of child in exec you'll need something more elaborate.

[quinedot]

Incidentally, learning Rust via implementing a pointer-based data structure is a notoriously bad way to learn Rust. If you choose to stick with it anyway, read this classic linked-list exploration. The considerations and problems explored in the first two chapters in particular will be a subset of what you'll encounter (basically if you had Box instead of Vec).

[Jinjiang]

@quinedot I see. Thanks for the advice and the explanation. I will take a read the links your shared further.