Battling lifetimes, copying, and collections

help
1

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!

2

taking ownership of whole self means it ceases to exist in the caller, exists only inside the function, and because you don't have anywhere to store it, it will be destroyed at the end of the function.

References don't exist on their own, they're a permission to view something that is stored permanently.

So you can't return a permission to view something in self when self is getting destroyed.

If you take &self, you'll e able to return a reference to anything that is guaranteed to stay around.

or you can return an owned value, so that it doesn't matter if its previous owner got destroyed, because an owned value survives independently.

3

taking ownership of whole self means it ceases to exist in the caller, exists only inside the function, and because you don't have anywhere to store it, it will be destroyed at the end of the function.

Thanks for the explanation. I just want to make sure I understand. If I have:

let tokens = vec![Token::Num(String::from("1")), Token::Plus, Token::Num(String::from("2"))];
let parser = Parser::from(tokens);
let peeked_value = parser.peek();
let peeked_value2 = parser.peek(); // Error

So, parser is invalid at the peeked_value2 line because we moved the value into the calling function. There is no way to move the value back.

Thanks!!

4

One of the ideas behind ownership is that values (such as variables) have scopes. If a value isn't moved or destructed by the end of the scope, it gets destructed at that point. Things work this way so that resources (memory allocations, file handles, ...) can be cleaned up (memory freed, files closed, ...) automatically, without a garbage collecting runtime.

By default, types have move semantics -- when you assign them or pass them by value, they get moved into the new variable or function, and the place (variable, field, ...) the value got moved out of becomes uninitialized (and thus can no longer be used[1]). In particular, any type that has a destructor has move semantics. This way you can, for example, pass a File around and it won't get destructed twice -- which would close the same file handle twice, which is UB. And you can pass a String around without freeing it twice (UB again) and without implicitly cloning it all the time (which would be expensive).

Copy is a special trait which can only be implemented if

  • The type has no destructor
  • No field type has a destructor
  • Moreover, every field type has also opted into being Copy

You can think of Copy as being about the definite lack of a destructor. Copy types have copy semantics instead of move semantics, which means you can still use the original value after the assignment / pass by value / etc.[2]

Your Parser has a destructor -- the Vec<_> needs freed when a Parser goes away -- so it cannot be Copy.

Despite the name, Rust lifetimes -- 'a things -- are about the duration of borrows, more than being about when a value gets destructed. The main connection is that a value cannot be borrowed when it is destructed, such as when it goes out of scope.[3]

Lifetime annotations on functions are largely about how borrows flow from the inputs to the outputs. Your OP compiles with this signature:

    fn peek(&self) -> Result<&Token, ()> {
    // Desugared:
    fn peek<'s>(&'s self) -> Result<&'s Token, ()> {

The signature implies that the Token is borrowed from *self somewhere. The compiler will enforce that uses of the &Token keep *self borrowed. That way, you can't destroy *self and make the &Token dangle, say.

With your original signature, there's nowhere for the borrow to "come from" other than static resources or leaked memory. An output lifetime appearing "from nowhere" is usually a sign something about the signature is off. If you had added an annotation like so...

    fn peek<'from_nowhere>(self) -> Result<&'from_nowhere Token, ()> {

...you would have gotten an error like this:

error[E0515]: cannot return value referencing local data `self.tokens`
  --> src/lib.rs:34:28
   |
32 |         let token = self.tokens.get(next);
   |                     ----------- `self.tokens` is borrowed here
33 |         match token {
34 |             Some(token) => Ok(token),
   |                            ^^^^^^^^^ returns a value referencing data owned by the current function

The problem is that you're trying to return a reference that can be used after the function call, but that reference is within the value in self, that goes out of scope at the end of a function. That is, you're trying to return something that requires self to be borrowed. It's an error for something to be borrowed when it goes out of scope, so you get the error. More generally, you can never return references to local variables, or which require local variables to be borrowed. The reason is that local variables are always moved or go out of scope by the end of the function body.

Or more concretely: If you forced the code to compile with unsafe, the Vec would get deallocated at the end of the method and the returned &Token would be pointing at deallocated memory, and you would have ended up with a use-after-free (which is UB).

(With the &self method, *self is what is borrowed, and it is not a local variable.)

I've written some more introductory material about borrow errors and related topics over here.

Moved it into peek, right.

Well, you could technically do something like...

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

...but don't do that, just use &self instead :slightly_smiling_face:.

  1. unless reinitialized ↩︎

  2. Note: variables that go out of scope are considered uninitialized, even if they are Copy and no actual code gets ran due to going out of scope. So you cannot use a reference to a Copy value which has gone out of scope, for example. ↩︎

  3. It also cannot be borrowed when it is moved, or when a &mut to it is created. A value is allowed to be shared-borrowed when copied, though. ↩︎