Rewriting Box<dyn SomeTrait> as &dyn SomeTrait

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<_>>());
}

Bonus points for any suggestions on how to clean up that MyItemDiff::Remove arm :smiley:

This is absolutely possible.

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).

1 Like

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))

Playground

2 Likes

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.

Actually, my original solution despite being ugly and hard to read shows that indeed it is possible to get around the use of the additional Vec.

Another solution with just filter and the once variable that you maybe find slightly more readable would be using bool's then method. Playground.

1 Like

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.

1 Like

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 }
});

Playground

2 Likes

Why not use a Vec as the accumulator? Playground

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.

Right, it should be measured. A multiset could also be an option if order is irrelevant, again depending on the kind of operations being done.

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.

The iterators themselves don't, but every Box::new is an allocation

1 Like

once || { once = true; false } is equivalent to std::mem::replace(&mut once, true)

3 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.