How can I clone a Vec>?

Question

I want to implement a function that takes an immutable &Vec reference, makes a copy, sorts the values and prints them.

This is the main code.

trait Foo {
    fn value(&self) -> i32;
}

struct Bar {
    x: i32,
}

impl Foo for Bar {
    fn value(&self) -> i32 {
        self.x
    }
}

fn main() {
    let mut a: Vec<Box<dyn Foo>> = Vec::new();
    a.push(Box::new(Bar { x: 3 }));
    a.push(Box::new(Bar { x: 5 }));
    a.push(Box::new(Bar { x: 4 }));

    let b = &a;
    sort_and_print(&b);
}

The only way I was able to make it work was this

fn sort_and_print(v: &Vec<Box<dyn Foo>>) {
    let mut v_copy = Vec::new();
    for val in v {
        v_copy.push(val);
    }
    v_copy.sort_by_key(|o| o.value());
    for val in v_copy {
        println!("{}", val.value());
    }
}

However I want to understand what's happening here and also to make the code shorter.

Question 1

If I try to change let mut v_copy = Vec::new(); to let mut v_copy: Vec<Box<dyn Foo>> = Vec::new(); however that results in various errors that I don't know how to fix.

How do I make this version work and why is it different than the first version?

Attempt 2

Something closer to what I'm looking for is something like this. let mut v_copy = v.clone(); but this doesn't work. Can this version be fixed?

Answer 1

First, let's annotate the types:

fn sort_and_print(v: &Vec<Box<dyn Foo>>) {
    let mut v_copy: Vec<&Box<dyn Foo>> = Vec::new();
    for val /* : &Box<dyn Foo> */ in v {
        v_copy.push(val);
    }
    v_copy.sort_by_key(|o: &&Box<dyn Foo>| <dyn Foo>::value(&***o));
    for val /* : &Box<dyn Foo> */ in v_copy {
        println!("{}", <dyn Foo>::value(&**val));
    }
}

Iterating over &Vec<T> produces an iterator over &T (the same as the .iter() method).

Now we can see we can convert it into iterator, by either calling .into_iter() on v and then .collect() (which is what the for loop does), or replace into_iter() with iter() (which is more idiomatic since we're iterating over references):

fn sort_and_print(v: &Vec<Box<dyn Foo>>) {
    let mut v_copy: Vec<&Box<dyn Foo>> = v.iter().collect(); // You can omit the `&Box<dyn Foo>` and replace it with `_`, I put it here for clarity.
    v_copy.sort_by_key(|o| o.value());
    for val in v_copy {
        println!("{}", val.value());
    }
}

However, we still only have a copy of the reference (&Box<dyn Foo>). Why can't we just clone the vector?

If we try...

fn sort_and_print(v: &Vec<Box<dyn Foo>>) {
    let mut v_copy = v.clone();
    v_copy.sort_by_key(|o| o.value());
    for val in v_copy {
        println!("{}", val.value());
    }
}

...the compiler yell at us:

warning: variable does not need to be mutable
  --> src/main.rs:45:9
   |
45 |     let mut v_copy = v.clone();
   |         ----^^^^^^
   |         |
   |         help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

error[E0596]: cannot borrow `*v_copy` as mutable, as it is behind a `&` reference
  --> src/main.rs:46:5
   |
45 |     let mut v_copy = v.clone();
   |         ---------- help: consider changing this to be a mutable reference: `&mut Vec<Box<dyn Foo>>`
46 |     v_copy.sort_by_key(|o| o.value());
   |     ^^^^^^ `v_copy` is a `&` reference, so the data it refers to cannot be borrowed as mutable

WHAT???????????

Well, let's try to specify the type. It can make the compiler smarter.

fn sort_and_print(v: &Vec<Box<dyn Foo>>) {
    let mut v_copy: Vec<Box<dyn Foo>> = v.clone();
    v_copy.sort_by_key(|o| o.value());
    for val in v_copy {
        println!("{}", val.value());
    }
}

Nope.

error[E0308]: mismatched types
  --> src/main.rs:45:41
   |
45 |     let mut v_copy: Vec<Box<dyn Foo>> = v.clone();
   |                     -----------------   ^^^^^^^^^
   |                     |                   |
   |                     |                   expected struct `Vec`, found reference
   |                     |                   help: try using a conversion method: `v.to_vec()`
   |                     expected due to this
   |
   = note: expected struct `Vec<Box<dyn Foo>>`
           found reference `&Vec<Box<dyn Foo>>`

Well, let's use the compiler's suggestion:

fn sort_and_print(v: &Vec<Box<dyn Foo>>) {
    let mut v_copy: Vec<Box<dyn Foo>> = v.to_vec();
    v_copy.sort_by_key(|o| o.value());
    for val in v_copy {
        println!("{}", val.value());
    }
}

Grrr!!

error[E0277]: the trait bound `dyn Foo: Clone` is not satisfied
  --> src/main.rs:45:43
   |
45 |     let mut v_copy: Vec<Box<dyn Foo>> = v.to_vec();
   |                                           ^^^^^^ the trait `Clone` is not implemented for `dyn Foo`
   |
   = note: required because of the requirements on the impl of `Clone` for `Box<dyn Foo>`

At least we now have some clues.

What happened here?

Well, like the compiler said, dyn Foo does not implement the Clone trait. Which means that neither does Box<dyn Foo>, and so is Vec<Box<dyn Foo>>.

However, &Vec<Box<dyn Foo>> actually does impl Clone. This is because you can have as many shared references as you want - shared (non-mutable) references are Copy, and every Copy is also Clone. Try it:

fn main() {
    let i: i32 = 123;
    let r0: &i32 = &i;
    let r1: &i32 = <&i32 as Clone>::clone(&r0);
}

So, when we write v.clone(), the compiler asks "is there a method named clone() that takes self of type &Vec<Box<dyn Foo>> (v)?" it first looks for such method on the Clone impl for Vec<Box<dyn Foo>> (because the Clone::clone() takes &self, so for Vec<Box<dyn Foo>> it takes &Vec<Box<dyn Foo>>). Unfortunately, such impl doesn't exist, so it does the magic of autoref (part the process of trying to adjust a method receiver in Rust, you can read more here), and asks the same question for &&Vec<Box<dyn Foo>>. Now we did find a match - <&Vec<Box<dyn Foo>> as Clone>::clone()! So this is what the compiler calls.

What is the return type of the method? Well, &Vec<Box<dyn Foo>>. This will be the type of v_copy. Now we understand why when we specified another type, the compiler got crazy! We can also decrypt the error message when we didn't specify a type: we asked the compiler to call sort_by_key() on a &Vec<Box<dyn Foo>>, but this method requires a &mut Vec<Box<dyn Foo>> (&mut [Box<dyn Foo>], to be precise, but it doesn't matter because Vec<T> can coerce to [T])!

We can also understand the warning about a redundant mut: we never change the reference, so no need to declare it as mutable!

When we called to_vec(), OTOH, the compiler didn't get confused: to_vec() requires the vector's item to implement Clone (where T: Clone), which doesn't happen for Box<dyn Foo>. BOOM.

Now the solution should be clear: we just need Box<dyn Foo> to impl Clone.

Just?...

The first thing we may think about is to give Foo a supertrait Clone:

trait Foo: Clone {
    fn value(&self) -> i32;
}

#[derive(Clone)]
struct Bar { /* ... */ }

Not working:

error[E0038]: the trait `Foo` cannot be made into an object
  --> src/main.rs:33:31
   |
33 | fn sort_and_print(v: &Vec<Box<dyn Foo>>) {
   |                               ^^^^^^^ `Foo` cannot be made into an object
   |
note: for a trait to be "object safe" it needs to allow building a vtable to allow the call to be resolvable dynamically; for more information visit <https://doc.rust-lang.org/reference/items/traits.html#object-safety>
  --> src/main.rs:1:12
   |
1  | trait Foo: Clone {
   |       ---  ^^^^^ ...because it requires `Self: Sized`
   |       |
   |       this trait cannot be made into an object...

Hmm, looks like Clone indeed requires Sized. Why?

Well, because in order to clone something, we need to return itself. Can we return dyn Foo? No, because it can be of any size.

So, let's try to impl Clone for Box<dyn Foo> by hand (we can do that even though Box is not defined in our crate because it is a fundamental type and Foo is local (defined in our crate)).

impl Clone for Box<dyn Foo> {
    fn clone(self: &Box<dyn Foo>) -> Box<dyn Foo> {
        // Now... What, actually?
    }
}

How can we even clone something that can be anything? Clearly we need to forward it to someone else. Who else? Someone who knows how to clone this thing. A method on Foo?

trait Foo {
    fn value(&self) -> i32;
    fn clone_dyn(&self) -> Box<dyn Foo>;
}

impl Foo for Bar {
    fn value(&self) -> i32 {
        self.x
    }
    
    fn clone_dyn(&self) -> Box<dyn Foo> {
        Box::new(self.clone()) // Forward to the derive(Clone) impl
    }
}

NOW!

impl Clone for Box<dyn Foo> {
    fn clone(&self) -> Self {
        self.clone_dyn()
    }
}

IT WORKS!!

fn sort_and_print(v: &Vec<Box<dyn Foo>>) {
    let mut v_copy = v.clone();
    v_copy.sort_by_key(|o| o.value());
    for val in v_copy {
        println!("{}", val.value());
    }
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=d6e871711146bc3f34d9710211b4a1dd

Note: The dyn-clone crate from @dtonlay generalizes this idea.

Answer 2

You can make sort_and_print() shorter using Iterator::collect():

fn sort_and_print(v: &[Box<dyn Foo>]) {
    let mut v_copy: Vec<_> = v.iter().collect();
    v_copy.sort_by_key(|o| o.value());
    for val in v_copy {
        println!("{}", val.value());
    }
}

Playground

As an aside, accepting a vector by reference is usually better expressed as accepting a slice, as explained here, so the above answer accepts a slice.

You can make it even shorter by using the sorted() method from the itertools crate, or in this case its cousin sorted_by_key():

use itertools::Itertools;

fn sort_and_print(v: &[Box<dyn Foo>]) {
    for val in v.iter().sorted_by_key(|o| o.value()) {
        println!("{}", val.value());
    }
}

You almost certainly don't want to clone the vector because it would involve a deep copy, i.e. cloning each Box<dyn Foo>, which is unnecessary, potentially expensive, as well as complicated (as explained in the other answer).