I would like to know whether it is possible, in general, to rewrite code using Box<dyn SomeTrait> with &dyn SomeTrait instead.
For example, the following code is uses type erasure to produce an iterator that applies a vector of MyItemDiffs to a vector of MyItems. Is it possible to remove the use of Box in this code?
use std::iter;
#[derive(Clone, Debug, PartialEq, Eq)]
struct MyItem(u32);
#[derive(Clone)]
enum MyItemDiff {
Add(MyItem),
Remove(MyItem)
}
fn main() {
let items = vec![MyItem(1), MyItem(2), MyItem(3)];
let diffs = vec![
MyItemDiff::Remove(MyItem(1)),
MyItemDiff::Add(MyItem(4)),
MyItemDiff::Add(MyItem(4)),
MyItemDiff::Add(MyItem(5)),
MyItemDiff::Remove(MyItem(4)),
];
let items_diff = diffs
.iter()
.fold(Box::new(items.iter()) as Box<dyn Iterator<Item = &MyItem>>, |iterator, my_item_diff| {
match my_item_diff {
MyItemDiff::Add(add) => {
Box::new(iterator.chain(iter::once(add)))
},
MyItemDiff::Remove(remove) => {
let mut once = true;
let filtered = iterator
.filter(move |my_item| match once && remove == *my_item {
true => {
once = false;
false
}
false => true,
});
Box::new(filtered)
}
}
});
assert_eq!(vec![&MyItem(2), &MyItem(3), &MyItem(4), &MyItem(5)], items_diff.collect::<Vec<_>>());
}
No, but that is not due to trait objects, but general ownership rules. You create temporary values when you call iterator.chain(iter::once(add)) and iterator.filter(...). You must take ownership of these temporary values (with Box).
No. Not in general. You can rewrite boxed trait objects to regular references when you don't need the ownership. This mostly happens in function arguments.
I tried to perform the old "store the statically-typed object in a separately-initialized local variable" trick on your code, and it didn't work. This seems to be fundamental: every new iterator you create must be stored somewhere, and they can't all be stored in the same local variable.
Oh, that's easy:
let head: Vec<_> = iterator.by_ref().take_while(|item| *item != remove).collect();
// if the last item matched `remove`, then it was already consumed; use the rest!
Box::new(head.into_iter().chain(iterator))
That's a nice trick with the by_ref and take_while. It seems that it's not possible to avoid the use of the Vec, although I am wondering whether there is a fundamental reason for this or whether it is just a limitation in the API.
It's fundamental. Your original solution tracks the state separately. The stateless solution needs to collect, as performing the take_while needs to "split" the iterator – and since the iterator yields its items one by one, this is not possible without retrieving all elements of the first half first; otherwise, there would be a need to mutably borrow the iterator twice.
An even shorter (but only arguably "simpler") solution is to directly depend on short-circuiting behavior. (Not recommended in production code, obviously).
let filtered = iterator.filter(move |item| {
*item != remove || once || { once = true; false }
});
There's a trade-off here between just preallocating the complete buffer and allocating a couple of iterators (ie. between the length of the data and the length of the diff). Whether either is significantly faster/less memory-hungry should likely be measured in the context of the concrete use case.
Do iterators allocate memory? The Iterator trait and its methods are in core::iter, I was under the impression that everything inside of core does not need an allocator.