Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Recursive traversal of composite tree of mutable "trait objects"?
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:
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 are several different concrete types that implement this trait. For example:
#[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. To clarify what I'm after, I have a working example using same concrete type, but the actual system needs a version that works with trait objects.
So, I'm left with something like this (which doesn't work):
impl Component for KeypadModel {
fn components(&self) -> Vec<&dyn Component> {
fn subtree(root: &dyn Component) -> Vec<&dyn Component> {
let mut v = vec![];
root.components // !! Error: See below !!
.iter()
.for_each(|m| v.append(&mut Self::subtree(m)));
v.push(root);
v
}
let mut v = vec![];
self.components
.iter()
.for_each(|m| v.append(&mut Self::subtree(m)));
v
}
fn components_mut(&mut self) -> Vec<&mut dyn Component> {
todo!() // ??
}
}
The error is that the code wants/expects root.components(), 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[2] descendants?
Please, note:
- Trying to use the
root.components()method shows the following error:
Diagnostics:
cannot return value referencing temporary value
returns a value referencing data owned by the current function [E0515]
-
Even if it weren't an error, the recursive logic would be incorrect, b/c deeper leaf nodes would be added more than once. (This is easier for me to show with an initial Python prototype I had, which can be run at https://playground.programiz.com)
-
The composite/container types hold different concrete types in their
componentsvector, which is why the vector must work with trait objects. -
Modifying the
Componenttrait and/or concrete types implementing it might be feasible.
2 answers
A root.components field need not exist, so I'm not sure what you're hoping for. Also, I don't know if it's an issue with your description or your code, but the code will only return mutable references to "leaf" Components while your description talks about "all descendants". It's not clear if "all descendants" is intended to include Components that have children as well.
As far as I can tell, changing to:
match root.components().is_empty() {
true => v.push(root),
false =>
root.components_mut()
.into_iter()
.for_each(|c| v.append(&mut subtree_mut(c))),
}
would compile and work fine other than the unnecessary allocation of the result of root.components() which could be fixed by adding a method to Component to test for this case without needing to return a Vec. This could probably be finessed some other way.
As for
Using
root.components_mut()would create a temporary value owned by the function and trying to return that is an error.
This doesn't matter. This temporary's lifetime isn't really connected to anything. Just the contents of the Vec are attached to the relevant lifetimes. In the above code, this is addressed by consuming that intermediate via into_iter() and then just passing c directly since it is the mutable ref we want.
And for
Even if it weren't an error, the recursive logic would be incorrect and several objects would be added more than once.
I don't quite understand what you're getting at here. In the code I list above, mutable references to all "leaf" Components will be returned (assuming no cycles...). If a This technically can't happen, since it would require a violation of the borrowing rules to get into this situation. That said, if you did want a non-tree-like graph to be possible, you'd need to use something like Component is a child of multiple Components, then its "leaves" will be included multiple times. If this is a problem, then it wouldn't be resolved by directly accessing some component field. You need to detect visited Components and avoid reprocessing them. This could be done by having a visited field that is set or by having a set of visited Components that gets passed along.Rc. Even without that though, you'd likely need something like Rc to be able to return all mutable references to all descendants, since mutably borrowing a KeypadModel would preclude mutably borrowing any element of its component field.
1 comment thread
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| ghost-in-the-zsh |
Thread: Works for me As long as you keep the caveat in mind. |
Oct 24, 2024 at 02:03 |
Here's the solution I ended up with a while back to traverse the (sub-)tree, starting at the given root component. In short, the model's field, components, is used directly and small unsafe blocks are used to push the root's children into the vector-backed queue that's currently being traversed.
While a full working example can be found at this playground link, the minimal/core part of it is below:
impl Component for Model {
fn children(&self) -> Vec<&dyn Component> {
let mut v: Vec<&dyn Component> = self.components
.iter()
.map(|c| c.deref())
.collect();
let q = &mut v as *mut Vec<&dyn Component>;
v.iter().for_each(|c| unsafe {
(*q).append(&mut c.children())
});
v
}
fn children_mut(&mut self) -> Vec<&mut dyn Component> {
let mut v: Vec<&mut dyn Component> = self.components
.iter_mut()
.map(|c| c.deref_mut())
.collect();
let q = &mut v as *mut Vec<&mut dyn Component>;
unsafe {
(*q).iter_mut().for_each(|c| {
(*q).append(&mut c.children_mut())
})
}
v
}
}
The caveat/con here is that, under the experimental "Stacked Borrows" memory model in the nightly toolchain, Miri says the above causes UB inside the Vec implementation:
error: Undefined Behavior: deallocating while item [SharedReadOnly for <9045>] is strongly protected
--> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/raw_vec.rs:776:13
|
776 | alloc.grow(ptr, old_layout, new_layout)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ deallocating while item [SharedReadOnly for <9045>] is strongly protected
|
= help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
= help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
= note: BACKTRACE:
= note: inside `alloc::raw_vec::finish_grow::<std::alloc::Global>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/raw_vec.rs:776:13: 776:52
= note: inside `alloc::raw_vec::RawVecInner::grow_amortized` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/raw_vec.rs:661:19: 661:93
= note: inside `alloc::raw_vec::RawVecInner::<A>::reserve::do_reserve_and_handle::<std::alloc::Global>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/raw_vec.rs:554:31: 554:79
note: inside closure
In short, Miri says the Vec implementation runs into UB while allocating memory for the vector, likely b/c the Vec is being modified while being traversed.
I've not (yet?) been successful in refactoring the above to remove the unsafe blocks. Perhaps some method type signature changes I'm not (currently) aware of would be required.
If you have specific suggestions, please post them in a comment.
0 comment threads