How to return an iterator from function, when the concrete iterator type may differ?

help
1

Suppose I have a struct like this

#[derive(Debug)]
pub struct QueryString<'buf> {
    data: HashMap<Cow<'buf, str>, Value<'buf>>,
}

#[derive(Debug)]
pub enum Value<'buf> {
    Single(Cow<'buf, str>),
    Multiple(Vec<Cow<'buf, str>>),
}

How would I implement a function that returns an iterator over the values for a key?

impl<'buf> QueryString<'buf> {
    pub fn get_ex(&'buf self, key: &str) -> Option<impl Iterator<Item = &'buf str>> {
        /* ... */
    }
}

I tried the following, but it does not compile:

impl<'buf> QueryString<'buf> {
    pub fn get_ex(&'buf self, key: &str) -> Option<impl Iterator<Item = &'buf str>> {
        match self.data.get(key) {
            Some(value) => match value {
                Value::Single(single) => Some(iter::once(single).map(Cow::as_ref)),
                Value::Multiple(multiple) => Some(multiple.iter().map(Cow::as_ref)),
            },
            None => None
        }
    }
}

Error is:

mismatched types
   --> server\src\http\query_string.rs:29:51
    = note: expected struct `Map<std::iter::Once<&Cow<'_, str>>, for<'a> fn(&'a Cow<'_, str>) -> &'a str {<Cow<'_, str> as AsRef<str>>::as_ref}>`
               found struct `Map<std::slice::Iter<'_, Cow<'_, str>>, for<'a> fn(&'a Cow<'_, str>) -> &'a str {<Cow<'_, str> as AsRef<str>>::as_ref}>`

So, it seems the problem is that the iterators are not the exactly same type.

But why would they have to be?

We only require the return type to implement the Iterator trait, which they both do! :thinking:

Is there any solution for this use case?

Thank you!

2

You have two choices in general: either you can 'forget' some type information and use trait objects (dyn Iterator<Item = X>), or you can return an enum with the different iterators in each variant. Since there's only two types using the enum is fairly straightforward. In the itertools crate there is an Either type that does this for you (use Either::Left for one iterator and Either::Right for the other). You see this pattern in FP languages like Haskell as well.

3 Likes
3

Can you give a minimal example how I would use itertools::Either here?

Also, it seems like dyn is not allowed in the return type... :expressionless:

4

I can :slight_smile:

impl<'buf> QueryString<'buf> {
    pub fn get_ex(&'buf self, key: &str) -> Option<impl Iterator<Item = &'buf str>> {
        match self.data.get(key) {
            Some(value) => match value {
                Value::Single(single) => Some(Either::Left(iter::once(single).map(Cow::as_ref))),
                Value::Multiple(multiple) => Some(Either::Right(multiple.iter().map(Cow::as_ref))),
            },
            None => None
        }
    }
}

I haven't tested it but it should work. If it doesn't I'm happy to make one on play.rust-lang.org.

EDIT Sorry I should have answered your other question: a dyn object doesn't have a known size (because it could be anything that implements the trait) so it needs to be behind a pointer, in this case you would use a Box<dyn Iterator<Item=X>> (When the objects exist somewhere else you can use references (&)).

1 Like
5

return position impl Trait (RPIT, -> impl Trait ...) is an opaque alias to a single, concrete type [1]. That's why your different match arms have to have the same iterator type.

As @derekdreery said, dyn Trait (a trait object) is how you type-erase multiple types into one type. dyn Trait is dynamically sized ("unsized"), because the type-erased iterators may have different sizes, for example. So you'll usually see dyn Trait behind a pointer of some sort -- most commonly Box<dyn Trait> or Box<dyn Trait + '_> for owned trait objects. (Sometimes &dyn Trait for borrowed trait objects, occasionally Arc<dyn Trait> or whatever else.)

So the signature would probably be

pub fn get_ex(&'buf self, _key: &str) -> Option<Box<dyn Iterator<Item = &str> + '_>> {

And you'll need to put the iterators into a Box.

=> Some(Box::new(iter::once(single).map(Cow::as_ref)))

(dyn Trait is a large topic, but the last thing I'll note is that dyn Trait is, itself, a singular concrete statically-known type, despite being dynamically sized and facilitating dynamic dispatch.)

  1. that is, single after taking into account input parameters, like for example 'buf ↩ī¸Ž

1 Like
6

Oh and argument position impl Trait (APIT: fn foo(t: impl Trait)) is mostly the same as generics (fn foo<T: Trait>(t: T)), where the caller chooses the type and the function body must support any type that meets the bounds.

(With RPIT the function writer chooses the one opaquely aliased type.)

So even though they look the same, they are quite different.

7

Thanks!

The solution with itertools::Either works fine, so it seems preferable over using Box<dyn ...>.

Too bad this isn't in the standard library... :face_with_raised_eyebrow:

8

There's quite a lot of itertools that could be in the standard library, but there's normally a reason it isn't. I think the reason here is that it's not clear that Either is the best name for the type (it comes from Haskell IIUC), and it would be nice to provide a single type that did this for all traits, not just Iterator, which isn't possible currently (or maybe ever).

9

The Either type in itertools is just a re-export from the either crate by the way. A bit more lightweight as a dependency on case the Either type is all you need: Either in either - Rust

1 Like
10

Either was in standard pre-1.0 but got removed. I think the coherency issue is a bigger hurdle: it would have to be opinionated over implementing e.g. Iterator or IntoIterator.

You need some impl<T, U, trait X> X for Either<T, U> where T: X, U: X ability... arbitrary trait delegation. Or specialization could get you partway there I guess.

Prior discussion.

11

Incidentally you can get a single type in this case without type erasure.

Playground.

2 Likes
12

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.