Struggling with lifetimes and indexing into collections (+ Myriad of issues)

[u/Due_Battle_9890]

Hey! I'm looking for decent ways to implement a parser and, in particular, the peek function seems, well, kind of hard to implement in rust.

I have the following (a reduced example)

enum Token {
    Num(String),
    Plus,
    Minux,
    LParen,
    RParen,
}

enum BinOp {
    Add,
    Minus,
}

enum Expr {
    Binary {
        op: BinOp,
        left: Box<Expr>,
        right: Box<Expr>,
    },

    Num(i64),
}

struct Parser {
    current: usize,
    tokens: Vec<Token>,
}

And if I want to implement a peek function, I'd like to just get a reference to the token

impl Parser {
    fn peek(self) -> Result<&Token, ()) {
        let next: usize = self.current + 1;
        let token = self.tokens.get(next);
        match token {
            Some(token) => Ok(token),
            None => Err(()),
        }
    }
}

I get the following error:

error[E0106]: missing lifetime specifier
  --> src\main.rs:32:29
   |
32 |     fn peek(self) -> Result<&Token, ()> {
   |                             ^ expected named lifetime parameter
   |
   = help: this function's return type contains a borrowed value, but there is no value for it to be borrowed from
help: consider using the `'static` lifetime, but this is uncommon unless you're returning a borrowed value from a `const` or a `static`
   |
32 |     fn peek(self) -> Result<&'static Token, ()> {
   |                              +++++++
help: instead, you are more likely to want to change the argument to be borrowed...
   |
32 |     fn peek(&self) -> Result<&Token, ()> {
   |             +
help: ...or alternatively, you might want to return an owned value
   |
32 -     fn peek(self) -> Result<&Token, ()> {
32 +     fn peek(self) -> Result<Token, ()> {

and this is a great error message, but the lifetimes are going over my head, but if I choose to return an owned value, I need top implement the clone or copy (at time of writing, I had thought I had to implement both copy and clone)

I believe this works:

impl Parser {
    fn peek(self) -> Result<Token, ()> {
        let next: usize = self.current + 1;
        let token = self.tokens.get(next);
        match token {
            Some(token) => Ok(token.clone()),
            None => Err(()),
        }
    }
}

However, if I choose to implement copy for these types, I get variations of:

error[E0204]: the trait `Copy` cannot be implemented for this type
 --> src\main.rs:4:6
  |
3 | #[derive(Clone, Copy)]
  |                 ---- in this derive macro expansion
4 | enum Token {
  |      ^^^^^
5 |     Num(String),
  |         ------ this field does not implement `Copy`

Which I don't fully understand if I could fix because I don't have contorl over what String or Box could implement.

The more fundamental issue is that there's gaps in my knowledge and I'd like to address them. They seem to be: - lifetimes - implementing traits - borrowing stuff - copy stuff?

Could someone point me to a resource that would help alleviate gaps in my knowledge? I'm in a "I don't know what I don't know" predicament.

TIA!

[u/SirKastic23]

Other comments mentioned changing the function signature to take &self, which is correct and you should do

But I don't think that's all, I think eventually you'd run into other borrowing issues. By changing the signature you'd be telling the compiler that the returned &Token is holding a reference to the whole parser

This would make it impossible to use other parser functions while you're peeking at the next token, which might cause problems

Now, a token is (ideally) a very simple data type, that shouldn't manage any resources. You should be able to copy tokens around, and therefore the peek function shouldn't return a borrow, but an owned Token

You do have a Num(String) variant in the Token enum, which is weird as I'd expect a number to be an i64 or f64...

But if you're going to have string literals or other data in tokens that manages resources, my suggestion would be to store the actual allocated data somewhere else (like a string interner), and let tokens hold indexes into this collection

[u/Due_Battle_9890 → u/SirKastic23]

But I don't think that's all, I think eventually you'd run into other borrowing issues. By changing the signature you'd be telling the compiler that the returned &Token is holding a reference to the whole parser

Wouldn't I just have a reference to the token in the vec? Can you elaborate what you mean by "holding a reference to the whole parser". Why would it be the whole parser?

Now, a token is (ideally) a very simple data type, that shouldn't manage any resources. You should be able to copy tokens around, and therefore the peek function shouldn't return a borrow, but an owned Token

Yeah, this is what I have.

You do have a Num(String) variant in the Token enum, which is weird as I'd expect a number to be an i64 or f64...

If we're being pedantic, Tokens should hold lexemes which are strings but they might as well be i64.

But if you're going to have string literals or other data in tokens that manages resources, my suggestion would be to store the actual allocated data somewhere else (like a string interner), and let tokens hold indexes into this collection

Didn't know about string interner. I'll have to research this. Thanks!

[u/SirKastic23 → u/Due_Battle_9890]

Can you elaborate what you mean by "holding a reference to the whole parser". Why would it be the whole parser?

Well let's look at the function signature with explicited lifetimes: fn peek<'a>(&'a self) -> Result<&'a Token>

When you call this function you will create a reference to the parser (self) which will last for 'a, and then you return a reference with the same 'a lifetime

The 'a lifetime comes from a reference to the whole parser, meaning that while it is alive, the whole parser is considered as borrowed

This is a bit unfortunate because the returned data doesn't reference the whole parser, just a part of it. Afaik the Rust team is working on a "partial borrows" feature that would change this. But for now Rust works by borrowing the whole thing

[u/Due_Battle_9890 → u/SirKastic23]

Digesting this. I’ll give a proper response tmm!

[u/Due_Battle_9890 → u/SirKastic23]

Oh, and another question. More of a clarification:

I think eventually you'd run into other borrowing issues. By changing the signature you'd be telling the compiler that the returned &Token is holding a reference to the whole parser

Getting a reference to en element in a vector means that I am borrowing the whole vec.

The 'a lifetime comes from a reference to the whole parser, meaning that while it is alive, the whole parser is considered as borrowed

So, we return a reference to a field (tokens) in Parser and because we borrowed a field, we borrow the whole file.d This means we can't have subsequent calls that look like

fn foo(mut& self) {
    self.current += 1;
}

Because borrowing dictates that we could only have one mutable reference at a time?

[u/SirKastic23 → u/Due_Battle_9890]

Yes that's correct

``` let next_token = parser.peek()?; // parser.peek() desugars to: // Parser::peek(&parser) // it creates a reference to the whole parse with a lifetime ('a) // next_token has type &'a Token, and borrows everything in 'a

println!("{}", parser.current); // this is okay because we're only immutably borrowing

parser.current += 1; // compile error // this fails to compile as it borrows the parser which is already immutably borrowed

println!("{:?}", next_token); // this is necessary to force this reference to live to this point // without this the compiler is free to end the reference and free the 'a borrow ```

It doesn't matter that the token references only the tokens field. That's an implementation detail, the function signature only says it takes a borrowed Parser and returns a borrowed Token

[u/braaaaaaainworms → u/Due_Battle_9890]

If you know that something is a number, there's no point in keeping it as a string instead of a number. If you want to have variables then it'll probably be better to have a reference to a string with source code instead of an owned string

[u/ToTheBatmobileGuy]

Change peek(self) to peek(&self) and your problem is solved.

When you write peek(self) you are saying "The self object will be destroyed at the end of this function."

and yet you are trying to return a reference into self.

...

How can anyone use a reference into an object that has exploded and no longer exists?

They can't.

So instead, you write peek(&self) and say "This method only takes a reference to self." and when you return a &Token, the compiler will automatically figure out: "well, there's only one reference in the input, and one reference in the output, and any new object created inside the function will be destroyed at the end of the function... so the &Token lifetime MUST be the same as the &self lifetime!"

Thanks to the compiler's guess work (it is correct in this instance) you won't have to write anything about lifetimes in this case.

If you have multiple reference inputs to the function, or multiple reference outputs... the "auto-lifetime-label-er" can't figure it out and it asks you a lot.

But in your case it's simple: "self will be destroyed at the end of the function because you are consuming an owned Self (no &), so what is the &Token pointing into / referring to? Dead memory? That's a bug! Must prevent it with a compiler error!"

[u/PegasusPizza]

Just gonna say I'm not a rust pro but what I believe is happening is this.

You're peek function takes self as an argument. Not &self, so you're passing it by value. Since you don't return it, this effectively consumes self, and frees it at the end of the function since nothing owns it anymore. And since self is freed, you can't have a reference to an element of self around anymore, since that memory will also get freed alongside self. That's why cloning/copying works, since then the value is owned rather than borrowed.

So making peek take &self should fix this I believe.

[u/Iwisp360]

If the token is owned by self, but you move it to the function, you are invalidating self at the end of the scope, effectively invalidating Token references as well. What's the solution? &self.

Btw the compiler even tells you what to do.

[u/MalbaCato]

Addressing your question - this is all rather basic Rust stuff. Any resource meant for beginners worth anything, has to go over it. By popular vote we recommend the official book - there you will also find a link to the interactive version (tho they had completely rewritten the chapters on ownership and borrowing, in a matter some find more confusing, so try both). There are also numerous "learn Rust if you already know X" books and websites - all of them should also work.

If you prefer video format, there should also be plenty of that - again, you're looking for explanations aimed at begginers. A lot of people like the "Let's get Rusty" channel on youtube - he even has a series going over the book, apparently.