How to implement trait once for all iterables of &T (e.g. Vec and &[T])

Question

I have a trait method that finds a reference to an element in a collection by linearly scanning through its elements.

I'd like to be able to implement this once for both Vec<Tag> and &'a [Tag] (and ideally support other iterable data structures too).

In the code below, the instances of TagFinder are identically implemented for Vec<Tag> and &'a [Tag], but I can't find a way to express this generically. Is it possible?

This other question seems relevant, but I have an extra level of indirection here in that I'm dealing with "iterables" and not iterators.

Relatedly, it seems it would be handy if there were a trait like IntoIterator that exposed an iterator of references (i.e. Vec<T> and &[T] would both iterate over &T, rather than Vec<T> exposing an owning iterator). I'm not sure why such a thing doesn't exist.

struct Tag {
    key: String,
    value: String,
}

trait TagFinder {
    fn find_tag(&self, key: &str) -> Option<&str>;
}

impl<'a> TagFinder for &'a [Tag] {
    fn find_tag(&self, key: &str) -> Option<&str> {
        find_tag(self.into_iter(), key)
    }
}

impl TagFinder for Vec<Tag> {
    fn find_tag(&self, key: &str) -> Option<&str> {
        find_tag(self.into_iter(), key)
    }
}

fn find_tag<'a, I>(tags: I, key: &str) -> Option<&'a str>
where
    I: Iterator<Item = &'a Tag>,
{
    tags.filter_map(|tag| match tag {
        &Tag {
            key: ref k,
            value: ref v,
        } if k == key =>
        {
            Some(v as &str)
        }
        _ => None,
    }).next()
}

fn main() {
    let v = vec![
        Tag {
            key: "a".to_owned(),
            value: "1".to_owned(),
        },
        Tag {
            key: "b".to_owned(),
            value: "2".to_owned(),
        },
    ];

    let s: &[Tag] = &v;

    assert!(v.find_tag("b") == Some("2"));
    assert!(s.find_tag("b") == Some("2"));
}

Edit

After some playing around I've come up with the following. It works, but I'm not really comfortable with why it works.

1. The trait now consumes self, which would not be at all desirable, except for the fact that the only implementers of IntoIterator<Item = &'a Tag> seem to be borrowing types, so the self that is destroyed is only a reference. I'm a bit wary because there is nothing (except convention) stopping someone implementing that for an owning type like Vec.

2. Moving the lifetime parameter from the method (elided) to the trait is weird. I'm finding it hard to understand how the return value ends up with a sensible lifetime.

3. Why does v.find_tag(...) work? The receiver here is a Vec not a reference. How is Rust converting it to a reference?

Thanks. :)

trait TagFinder<'a> {
    fn find_tag(self, key: &str) -> Option<&'a str>;
}

impl<'a, T> TagFinder<'a> for T
where
    T: IntoIterator<Item = &'a Tag>,
{
    fn find_tag(self, key: &str) -> Option<&'a str> {
        find_tag(self.into_iter(), key)
    }
}

Answer 1

How to implement trait once for all iterables of &T

Pretty much as you've specified:

trait Foo {}

impl<'a, T: 'a, I> Foo for I
where
    I: Iterator<Item = &'a T>,
{
}

You can substitute IntoIterator for Iterator if you'd like.

For your specific case:

trait TagFinder<'a> {
    fn find_tag(self, key: &str) -> Option<&'a str>;
}

impl<'a, I> TagFinder<'a> for I
where
    I: IntoIterator<Item = &'a Tag>,
{
    fn find_tag(self, key: &str) -> Option<&'a str> {
        self.into_iter()
            .filter(|tag| tag.key == key)
            .map(|tag| tag.value.as_ref())
            .next()
    }
}

The trait now consumes self, which would not be at all desirable, except for the fact that the only implementers of IntoIterator<Item = &'a Tag> seem to be borrowing types, so the self that is destroyed is only a reference. I'm a bit wary because there is nothing (except convention) stopping someone implementing that for an owning type like Vec.

If you can find some way to take an owning value and return a reference to it, then you've found a critical hole in Rust's memory safety. See Is there any way to return a reference to a variable created in a function?.

Moving the lifetime parameter from the method (elided) to the trait is weird. I'm finding it hard to understand how the return value ends up with a sensible lifetime.

I don't understand the confusion. You've explicitly specified the lifetime, so in what manner would it not be reasonable? You aren't removing it from the method, you are just adding it to the trait because now the trait has to know that 'a is something from "outside" the trait itself.

Why does v.find_tag(...) work? The receiver here is a Vec not a reference. How is Rust converting it to a reference?

The same way any other method call that takes a reference works when called on a value. See What are Rust's exact auto-dereferencing rules?