Post History

Recursive traversal of composite tree of mutable "trait objects"?

Recursive traversal of composite tree of mutable "trait objects"

Hi,

I'm working on a background service/daemon for an embedded device, in Rust. The daemon manages several hardware components and these are structured using the Composite design pattern. The composite type from the pattern is called `Component` in the service:

```rust
pub trait Component:
    // ...
    + Debug
    + Sync
    + Send
    + 'static
{
    fn components(&self) -> Vec<&dyn Component> {
        vec![]
    }

    fn components_mut(&mut self) -> Vec<&mut dyn Component> {
        vec![]
    }
}
```

There're several different concrete types that implement this trait. For example:

```rust
#[derive(Debug)]
pub struct KeypadModel {
    components: Vec<Box<dyn Component>>,
}
// ...
impl KeypadModel {
    pub fn new() -> Self {
        debug!("Creating {} ...", stringify!(KeypadModel));
        Self {
            components: vec![
                Box::new(ButtonGroupModel::new()),
                Box::new(NumberpadModel::new()),
            ],
        }
    }
}
```

The problem is that the elements of the `components` vector are *not concrete types*; they *must be trait objects*. I have a working example (not listed) when using a vector of the same concrete type, but that's not feasible in this system.

So, I'm left with something like this (which doesn't work):

```
impl Component for KeypadModel {
    fn components(&self) -> Vec<&dyn Component> {
        todo!()
    }

    fn components_mut(&mut self) -> Vec<&mut dyn Component> {
        fn subtree_mut(root: &mut dyn Component) -> Vec<&mut dyn Component> {
            let mut v = vec![];
            // !! Error Here: Explanation below !!
            match root.components.is_empty() {
                true => v.push(root),
                false => root.components 
                    .iter_mut()
                    .for_each(|c| v.append(&mut subtree_mut(c.deref_mut())))
            }
            v
        }

        let mut v = vec![];
        self.components
            .iter_mut()
            .for_each(|c| v.append(&mut subtree_mut(c.deref_mut())));
        v
    }
}
```

The error is that the code wants/expects `root.components_mut()`, which is the *method* that belongs to the trait, but I need access to the `root.components` *field*, which belongs to the concrete type.

**The question is:** How can I traverse[^1] the trait object tree structure, starting at an arbitrary `root` node, to generate a vector of *all* descendants objects?

Please, note the following:

1. Using `root.components_mut()` would create a temporary value owned by the function and trying to return that is an error.
2. Even if it weren't an error, the recursive logic would be incorrect and several objects would be added more than once.
3. The composite/container types hold *different* concrete types in their `components` vector, which is why the vector *must* work with trait objects.
4. Modifying the `Component` trait and/or concrete types implementing it may be feasible.

I hope this is clear enough, but I can add clarifications, and a working example that uses concrete (not trait) types, if needed.

Thank you in advance for the help.


[^1]: Recursively is likely more natural, but an iterative solution is also OK.