Help with borrow checker issues, using arenas for Ast's

help
1

Using the 'bumpalo' crate to have arena's with AST nodes allocated in them.
I use the parser to maintain a state, which contains a reference to this arena.

I've made it such that the AST owns the arena.

use bumpalo::Bump;

use crate::lexer::TokenType;
use crate::lexer::Token;

#[derive(Debug)]
enum Op { ... }

#[derive(Debug)]
enum Expr<'a> {
    Constant(u64),
    Variable(&'a str),
    Binary { lhs: &'a Expr<'a>, rhs: &'a Expr<'a>, op: Op },
    Unary { lhs: &'a Expr<'a>, op: Op },
}

#[derive(Debug)]
pub struct Ast<'a> {
    arena: Bump,
    nodes: &'a Expr<'a>,
}

struct Parser<'a> {
    tokens: &'a [Token<'a>],
    arena: &'a Bump,
    current: usize,
}

impl Parser<'_> {
    fn peek(&self) -> Option<&Token> {
        self.tokens.get(self.current)
    }

    fn swallow(&mut self) -> Option<&Token> {
        self.current += 1;
        self.tokens.get(self.current)
    }

    fn consume(&mut self, expected: TokenType, msg: &str) {
        if let Some(t) = self.peek() {
            if t.kind != expected {
                eprintln!("{}", msg);
                panic!("Unexpected token");
            }
        } else {
            panic!("Unexpected end of file");
        }

        self.current += 1;
    }
}

fn expr<'a>(parser: &mut Parser<'a>) -> &'a Expr<'a> {
    parser.arena.alloc(Expr::Constant(42))
}

pub fn parse<'a>(tokens: Vec<Token<'a>>) -> Ast<'a> {
    let arena = Bump::new();

    let mut parser = Parser {
        tokens: &tokens,
        arena: &arena,
        current: 0,
    };

    let expr = expr(&mut parser);

    Ast { arena, nodes: expr }
}

But I get the following errors with the borrow checker

error[E0515]: cannot return value referencing local variable `arena`
  --> src/parser.rs:76:5
   |
70 |         arena: &arena,
   |                ------ `arena` is borrowed here
...
76 |     Ast { arena, nodes: expr }
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^ returns a value referencing data owned by the current function

error[E0515]: cannot return value referencing local variable `arena`
  --> src/parser.rs:76:5
   |
70 |         arena: &arena,
   |                ------ `arena` is borrowed here
...
76 |     Ast { arena, nodes: expr }
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^ returns a value referencing data owned by the current function

error[E0515]: cannot return value referencing function parameter `tokens`
  --> src/parser.rs:76:5
   |
69 |         tokens: &tokens,
error[E0515]: cannot return value referencing function parameter `tokens`
  --> src/parser.rs:76:5
   |
69 |         tokens: &tokens,
   |                 ------- `tokens` is borrowed here
...
76 |     Ast { arena, nodes: expr }
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^ returns a value referencing data owned by the current function

   |                 ------- `tokens` is borrowed here
...
76 |     Ast { arena, nodes: expr }
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^ returns a value referencing data owned by the current function

error[E0505]: cannot move out of `arena` because it is borrowed
  --> src/parser.rs:76:11
   |
65 | pub fn parse<'a>(tokens: Vec<Token<'a>>) -> Ast<'a> {
   |              -- lifetime `'a` defined here
66 |     let arena = Bump::new();
   |         ----- binding `arena` declared here
...
70 |         arena: &arena,
   |                ------ borrow of `arena` occurs here
...
76 |     Ast { arena, nodes: expr }
   |     ------^^^^^---------------
   |     |     |
   |     |     move out of `arena` occurs here
   |     returning this value requires that `arena` is borrowed for `'a`

error[E0505]: cannot move out of `arena` because it is borrowed
  --> src/parser.rs:76:11
   |
65 | pub fn parse<'a>(tokens: Vec<Token<'a>>) -> Ast<'a> {
   |              -- lifetime `'a` defined here
66 |     let arena = Bump::new();
   |         ----- binding `arena` declared here
...
70 |         arena: &arena,
   |                ------ borrow of `arena` occurs here
...
76 |     Ast { arena, nodes: expr }
   |     ------^^^^^---------------
   |     |     |
   |     |     move out of `arena` occurs here
   |     returning this value requires that `arena` is borrowed for `'a`

Some errors have detailed explanations: E0505, E0515.
For more information about an error, try `rustc --explain E0505`.
Some errors have detailed explanations: E0505, E0515.
For more information about an error, try `rustc --explain E0505`.

from what I understand 'expr' requires the references to last longer due to which I'm unable to return them?

2

If i understand you correctly the lifetime 'a in your Ast struct always refers to the Bump arena field, correct? That means that you have created a self-referential struct, which is really hard / pretty much impossible to use in safe rust.
The borrow checker complains about this, because when you try to return both the data and a reference to the data from the parse function you move the data, which could invalidate the reference. Here this doesn't happen, because it is heap allocated, but the borrow checker can't know that.

The best way to deal with this is probably to redesign your data structures so that doesn't happen. If that isn't possible you can also use something like ouroboros or a similar crate.

1 Like
3

In addition to what @luca3s said, you're also equating the lifetime of the parser Vec with the lifetime of the arena. These must be separate lifetimes. Or if you want them to have the same lifetime, allocate the parser Vec from the arena.

1 Like
5

@luca3s @jumpnbrownweasel
Ah I see! Ouroboros seems useful...
Anyways I chose to redo my data structures. Opted for a Flat Ast instead.

Thanks for the detailed reply!

1 Like