Trait object discrepancy between Vec and HashMap

I've been struggling to understand why the following code behaves the way it does (Playground):

use std::collections::HashMap;

trait Trait<'a> {
    fn get_enum(&'a self) -> Enum<'a>;
}

#[derive(Clone)]
enum Enum<'a> {
    Arr(Vec<&'a dyn Trait<'a>>),
    Map(HashMap<String, &'a dyn Trait<'a>>)
}

impl<'a> Trait<'a> for Enum<'a> {
    fn get_enum(&'a self) -> Enum<'a> {
        self.clone()
    }
}

fn process<'a>(val: &'a dyn Trait<'a>) -> Vec<&'a dyn Trait<'a>> {
    let mut traits: Vec<&dyn Trait> = vec![];
    match val.get_enum() {
        Enum::Arr(v) => {
            for elem in v {
                traits.push(elem);
            }
        },
        Enum::Map(m) => {
            for elem in m.values() {
                traits.push(elem);
            }
        }
    }
    traits
}

This throws the error:

error[E0277]: the trait bound `&dyn Trait<'_>: Trait<'_>` is not satisfied
  --> src/main.rs:29:29
   |
29 |                 traits.push(elem);
   |                             ^^^^ the trait `Trait<'_>` is not implemented for `&dyn Trait<'_>`
   |
   = note: required for the cast to the object type `dyn Trait<'_>`

The thing that's strange to me isn't exactly the error as much as the fact that the error only shows up listing values from the HashMap and not from Vec's iterator. Can someone explain to me:

Why the two structures' iterators behave so differently
How I can pass values from my map into my array

I have found the same phenomenon occurs retrieving any value via the get call as well.

Solution

The difference is not between Vec and HashMap, but in how you iterate over them. for loops use IntoIterator internally (see Why is iterating over a collection via `for` loop considered a "move" in Rust?), so the type of elem depends on the iterable.

for elem in v {
    traits.push(elem);
}

Vec<T> implements IntoIterator<Item = T>, so inside the loop elem is &'a dyn Trait<'a>.

for elem in m.values() {
    traits.push(elem);
}

HashMap<_, T>::values borrows self to create an Iterator<Item = &T> (which implements IntoIterator<Item = &T>). Since the value type of m is a reference already, inside the loop elem is something like &'b &'a dyn Trait<'a> (where 'b is the lifetime of the borrow of m).

The reason you get the error the trait bound `&dyn Trait<'_>: Trait<'_>` is not satisfied is because the compiler is trying to coerce &'b &'a dyn Trait to &'b dyn Trait, but it can't because &'a dyn Trait does not implement Trait. But even if it did that would not solve the problem -- you would just get a borrowing error instead when you tried to return references of lifetime 'b from the function.

How I can pass values from my map into my array?

I mentioned in the comments that you can iterate over m by value, which is similar to what you're doing with v:

for (_key, elem) in m {
    traits.push(elem);
}

This is destructive iteration because you can't use m afterwards. Another option, since shared references implement Copy, is to copy them out of the map as you iterate over it:

for elem in m.values() {
    traits.push(*elem);          // using * to dereference
}

for &elem in m.values() {        // using & to destructure
    traits.push(elem);
}

These loops do the same thing; the only difference is the type of elem.