Struggling to return a struct holding a generic Iterator field

[drmason13]

So I sort of figured this out while writing this up, but heck!
I got this far maybe this will help someone else I also could be wrong still. EDIT: I was wrong

I'm pretty sure my mistake was thinking I could return a struct that is generic over some type

I: Iterator<Item = Thing>

by giving it one concrete type that satisfied that bound.
EDIT: See the solution for how to do this
The problem was I made that type inside the function body. The function body which promised to be generic over I in its signature... (because I had to get an I from somewhere right?) Woops!

I think what threw me was that the error only said the types didn't match... which is true but doesn't highlight the bigger problem of
"You claim to be generic over {Generic Type} but you are using {concrete type}. No concrete type is going to match {Generic Type}. Help: Introduce a parameter of type {Generic Type}"
Maybe there's a diagnostic improvement to be made here?

I also made a minimal example, here: Rust Playground , during which I realised my mistake!
EDIT: Quinedot's Rust Playground is much better though!

I have a somewhat complicated concrete Iterator type*, but it can be very simply described as a generic Iterator: Iterator<Item = Token>. Here's my method that tries to return a struct holding that generic iterator in a field:

    pub fn parse_tokens<I>(&self) -> Parser<I>
    where
        I: Iterator<Item = Token>,
    {
        let token_stream: Peekaboo<I> = self.get_token_stream().filter_map(/* elided for brevity */).peekaboo();
        Parser::new(token_stream)
    }

Peekaboo is an Iterator I wrote for peeking up to twice (which was really fun!).

The above method (of a struct that isn't Parser) fails to compile, the error message confuses me though:

mismatched types
expected struct `Peekaboo<I>`
   found struct `Peekaboo<FilterMap<TokenStream<'_>, fn(Result<Token, Error>) -> Option<Token> {token_filter_map}>>`rustcE0308
lexer.rs(29, 25): this type parameter
lexer.rs(33, 21): expected due to this

It wants specifically the Generic type, but it found a concrete type.
How have I run into this problem? I feel like I've passed concrete types to generic functions all the time.
What do I even do to make Rust "find" Peekaboo<I>? Why isn't a concrete type satisfying the generic sufficient here? I can't build a Generic type can I? Something doesn't feel right.

This case is a bit odd (I probably need to sleep on it and make some better architectural decisions )
because the type being returned is a generic struct:

pub struct Parser<I>
where
    I: Iterator<Item = Token>,
{
    tokens: Peekaboo<I>, // this lets me peek up to 2 Tokens ahead
    current: usize,
}

Peekaboo is generic over Iterators as you might expect (this is in a different crate):

pub struct Peekaboo<I: Iterator> {
    iter: I,
    // ...
}

I can use token_stream in more "normal" or simple situations with the same I.
This compiles fine:

    pub fn parse_tokens<I>(&'source self) -> Parser<I>
    where
        I: Iterator<Item = Token> + 'source,
    {
        let tokens = self.scan_tokens().filter_map(token_filter_map).peekaboo();
        wants_token_iter(tokens);
        todo!();
        // Parser::new(tokens)
    }
}

fn wants_token_iter<I>(_want: Peekaboo<I>)
where
    I: Iterator<Item = Token>,
{
}

Amusingly enough, so this compiles fine too:

        let tokens: Peekaboo<I> = (|| todo!())();
        Parser::new(tokens)

So maybe there is some way to make this work. That's still on my todo list!
Everything else Parser side compiles fine with this in place.

EDIT: post solution me here! Post "Epiphany me is going to talk some nonsense! Now I would advise "impl Trait in return position"

Post epiphany me again. Pretty sure there isn't a way to make this work without introducing a parameter to parse_tokens of type I. So I wouldn't advise actually using this!

[quinedot]

Let me make sure I understand what you ran into. In your playground I added a function and altered main like so:

pub fn parse_tokens<I>() -> Parser<I>
where
    I: Iterator<Item = Token>,
{
    let token_stream = std::iter::repeat(Ok(Token))
        .take(3)
        .filter_map(|t: Result<Token, SomeError>| t.ok())
        .peekable();

    // concrete type that implements Iterator<Item = Token>
    Parser::new(token_stream)
}


fn main() {
    let mut parser = parse_tokens();
    assert_eq!(Some(Token), parser.iter.next());
}

Is this like what you were trying to do? If so, you could do this:

-pub fn parse_tokens<I>() -> Parser<I>
-where
-    I: Iterator<Item = Token>,
-{
+pub fn parse_tokens() -> Parser<impl Iterator<Item = Token>> {

The "impl in return position" is saying, "I'm going to return some concrete iterator here, but all I'm letting anyone else know is the trait bound. They can't even name the type."

[steffahn]

@drmason13

Pretty sure there isn't a way to make this work without introducing a parameter to parse_tokens of type I .

Some impl Trait return types might help you. Something like

pub fn parse_tokens(&'source self) -> Parser<impl Iterator<Item=…> + 'source>

could work. (I don't have your actual code to test it.)

Edit: Yeah, @quinedot was slightly faster with a similar suggestion xD

[drmason13]

Ah ha! Than you both so much. That's exactly what I want! I'm glad my instincts at first weren't completely wrong. It felt like I ought to be able to give a concrete type to meet a generic requirement.

I didn't think to change the return type to an impl Trait, I've not done that in this exact way yet (inside a generic type parameter of a struct)

Knowing that signatures like this work is great:

pub fn parse_tokens(&'source self) -> Parser<impl Iterator<Item=…> + 'source>

Aside: I hope those lifetimes work out

I'm not even sure why I didn't think of it, I've used plenty of impl Trait before. Mostly in argument position though. It might be because sometimes you can't use impl Trait in return position, i.e trait methods.

This is great, iterative parsing shall continue. I was about to hold my nose and collect into a Vec to pass it over and iterate again. Glad I won't need to!

Maybe the diagnostic could somehow suggest changing the return type? I think a heuristic night be:

1. Is the return type Generic over some T?
2. Is there a trait bound on T?
3. Does the function lack an argument Generic over T?
4. Is there a type conflict between the return type and a concrete type?

If all 4 of these are true, then it could suggest:

Hint: Consider using `impl Trait` in return position instead of a generic return type.

It might be sufficient for only 1 and 3 to be true to mention:

Hint: No concrete type will ever be equal to {Generic Type}.

It should include both hints when applicable I think.

I have a feeling I might be missing something again in this more general case (no pun intended).

[steffahn]

@drmason13

I was about to hold my nose and collect into a Vec

The more direct workaround if we wouldn't have the impl Trait return type feature or in cases where you can't use it (e. g. as you mentioned in trait methods) is to Box the iterator and then turn it into a trait object. Parser<Box<dyn Iterator<Item=…> + 'lifetime>>

[drmason13]

That's a good point! I should probably be less averse to dynamic dispatch