Peekable argument - there has to be a simpler way

1

I'm a Rust newbie, and I started exploring Rust by creating a simple calculator-like program. To parse simple arithmetic I wrote a LR(1) parser that peeks one token ahead. To write my first instinct was to write my own wrapper around Iterator to cache peeked value, fortunately I tried to look into stdlib and found Peekable. It works just fine, except one thing: it's really mouthful to pass it around.

Here's what I'm using now:

    fn parse_multiplier<'a, I>(tokens: &mut std::iter::Peekable<I>) -> Tree where
        I: std::iter::Iterator<Item = &'a Token> { ...

It does work, but there has to be a simpler way. I expected something like

    fn parse_multiplier(tokens: &mut std::iter::Peekable<Item = Token>) -> Tree { ...

to work.

After reading docs, fiddling with it and reading libcore sources I understand why it doesn't work, it just isn't what I expected.

So my questions are:

  1. Am I doing this the right way?
  2. Is there a simpler way for this in Rust currently?
  3. Can there be a simpler way for this in Rust in the future?
2

Since Peekable provides an extended interface compared to Iterator, there should really be a trait for this.
But there isn't, so you have to do it yourself, like:

pub trait PeekableIterator : std::iter::Iterator {
    fn peek(&mut self) -> Option<&Self::Item>;
}

impl<I: std::iter::Iterator> PeekableIterator for std::iter::Peekable<I> {
    fn peek(&mut self) -> Option<&Self::Item> {
        std::iter::Peekable::peek(self)
    }
}

Then you can use it either as a generic function:

fn parse_multiplier<P>(tokens: &mut P) -> Tree
    where P: PeekableIterator<Item=Token>
{...}

Or as a trait object:

fn parse_multiplier_obj<P>(tokens: &mut PeekableIterator<Item=Token>) -> Tree
{...}
3 Likes
3

Am I doing this the right way?

Do you really need the parser to be generic over the iterator? You can make it generic, but it does not mean that you have to =) You can define a type alias to abstract over the precise iterator:

type Tokens = Peekable<slice::Iter<Token>>

If you do want to make this generic, you can define your own trait for this:

struct Token;

trait TokenIterator<'a>: Iterator<Item = &'a Token> {
    fn peek(&mut self) -> Option<&'a Token>;
}

impl<'a, I> TokenIterator<'a> for Peekable<I> where I: Iterator<Item = &'a Token> {
    fn peek(&mut self) -> Option<&'a Token> {
        self.peek().map(|t| *t)
    }
}

Also, I would suggest to make token a Copy type:

#[derive(Clone, Copy)]
struct Token {
    start_offset: usize,
    end_offset: usize,
    kind: TokenKind
}
4

Ok, this works and looks way nicer. It's like you've hidden all that where clause in the trait and its implementation.

Why isn't this done in libcore though? Is there some reason behind it?

I also don't quite understand: why did compiler force me to add a 'a lifetime specifier in generic arguments? With your code I use PeekableIterator<Item = &Token> and it works just fine w/o explicit lifetime specifier.

5

Not that I need to but I really want to :slight_smile:
I want to be able to make tokenizer lazy in future (make it return Iterator<Token> instead of Vec<Token> as it does now).

@troplin's solution does basically the same as it seems, but it's more abstract, so I like it more :slight_smile:

My Token is an enum:

#[derive(Debug)]
enum Token {
    Number(f32),
    BinOp(BinOp),
}

What would Copy trait give?

6

Really? When I tried it with references, I also had to add the lifetime specifier:

fn parse_multiplier<'a, P>(tokens: &mut P) -> Tree
    where P: PeekableIterator<Item=&'a Token>
{...}

Here on Playground:

both functions give the same error

7

Just a marginally simpler code, because there would be less lifetimes.

but it's more abstract, so I like it more :slight_smile:

That's exactly my point: it seems to be easier to start with non generic clone everything code and add generics and zero copy later, when the basic structure is working and you have some tests. I wish I followed this advice myself: I usually start all generic, code myself into a corner with a borrowchecker, flip the table and admit that I don't need a general solution yet :smile:

8

Oh, I used the shortest form you suggested - with type written directly in argument list

fn parse_multiplier (tokens: &mut PeekableIterator<Item = &Token>) -> Tree {

and it works: Rust Playground - your variants want lifetime specifier, but the this one doesn't.

9

Well, with fn parse_multiplier (tokens: &mut PeekableIterator<Item = &Token>) -> Tree { I don't need any lifetime specifiers (somehow).

BTW, even if I have Copy, I still have to deal with references since Vec<Token> yields &Tokens, not plain Tokens. I wonder if there is an option for that.

Yeah, I'm not it the corner yet, I just have too many details in function definition, more than I like. So generic approach FTW! :smile:

10

Just be aware, that this is not just a shorter form, it's a trait object (i.e. dynamic dispatch).
The template form uses static dispatch, which is usually preferred in Rust.

1 Like
11

Ah, that's the catch. Well, while static dispatch is cool, if dynamic dispatch allows for simpler code for a price of some performance, it might fit some niche.

Thanks for clarification!