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.
Comments on Recursive traversal of composite tree of mutable "trait objects"?
Parent
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.
Post
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