Building a tree of vectors

2
votes

I'm trying to make a simple LISP parser, but I'm stuck on the step where I convert the vector of tokens into a tree of AST nodes.

I create the root of the tree, and then maintain a stack of references into the tree where I currently want to add the next node. The problem is that no matter what I try, it seems that the borrow checker thinks I'm referencing something that doesn't live long enough.

This is the code:

pub fn parse(tokens: &Vec<Token>) -> Node {
    let mut root: Vec<Node> = vec![];

    {
        tokens.into_iter().fold(vec![&mut root], handle_token);
    }

    Node::List(root)
}

fn handle_token<'a>(mut stack: Vec<&'a mut Vec<Node>>, token: &Token) -> Vec<&'a mut Vec<Node>> {
    if *token == Token::LParen {
        let new_node = Node::List(vec![]); // Create the new node
        stack[0].push(new_node); // Add it to the tree
        match stack[0][0] {
            Node::List(ref mut the_vec) => stack.push(the_vec), // Finally, add a mutable reference to the new vector so that subsequent nodes will become children of this Node
            _ => panic!(),
        };
    } else if *token == Token::RParen {
        stack.pop();
    } else {
        match *token {
            Token::Identifier(ref identifier) => {
                stack[0].push(Node::Identifier(identifier.to_owned()))
            }
            Token::Number(number) => stack[0].push(Node::Number(number)),
            Token::Str(ref s) => stack[0].push(Node::Str(s.to_owned())),
            Token::EOF => {}
            _ => panic!(),
        }
    }

    stack
}

This is the compiler output:

error: `stack` does not live long enough
  --> src/parser.rs:30:15
   |
30 |         match stack[0][0] {
   |               ^^^^^ does not live long enough
...
47 | }
   | - borrowed value only lives until here
   |
note: borrowed value must be valid for the lifetime 'a as defined on the block at 26:96...
  --> src/parser.rs:26:97
   |
26 | fn handle_token<'a>(mut stack: Vec<&'a mut Vec<Node>>, token: &Token) -> Vec<&'a mut Vec<Node>> {
   |                                                                                                 ^

After researching this a bit, it seems like I'm trying to do something completely non-idiomatic to Rust, but I'm not sure. Is there a simple way to make this work, or do I need to rethink this?

I tried to reduce the problem to a minimal example:

enum Token {
    Start,
    End,
    Value(i32),
}

enum Node {
    List(Vec<Node>),
    Value(i32),
}

fn main() {
    let v = vec![Token::Start, Token::Value(1), Token::End];
    parse(&v);
}

fn parse(tokens: &Vec<Token>) -> Node {
    let mut root: Vec<Node> = vec![];

    {
        tokens.into_iter().fold(vec![&mut root], handle_token);
    }

    Node::List(root)
}

fn handle_token<'a>(mut stack: Vec<&'a mut Vec<Node>>, token: &Token) -> Vec<&'a mut Vec<Node>> {
    match *token {
        Token::Start => {
            stack[0].push(Node::List(vec![])); // Add the new node to the tree
            match stack[0][0] {
                Node::List(ref mut the_vec) => stack.push(the_vec), // Add a mutable reference to the new vector so that subsequent nodes will become children of this Node
                _ => panic!(),
            };
        },
        Token::End => { stack.pop(); },
        Token::Value(v) => stack[0].push(Node::Value(v)),
    }

    stack
}
2
rustborrow-checker
It looks like you add something a second time to the stack, without removing the first. But data should have 1 owner, not 2. Can you try to create a Minimal, Complete, and Verifiable Example? That would make it easier to suggest an alternative. – wimh

2 Answers

2
votes

As @wimh mentioned, you're violating ownership. Let me try to break it down a bit, and see if it makes sense.

stack[0][0] gives you a Node contained in a mutable borrow of a Vec. You then try to mutably borrow the Vec contained in the Node::List variant of that Node, and add it as a mutable borrow to the outer Vec (the stack). If this were allowed, you'd now have the outer Vec and the inner Vec able to mutate that Node's Vec at the same time.

I would try to rethink your design a bit, and see if you can make ownership a bit more clearcut.

1
votes

After reading a blog post about modeling graphs using vector indices I decided to try a similar approach. The resulting code works and is a lot simpler:

type NodeIndex = usize;

pub fn parse(tokens: &Vec<Token>) -> Node {
    let mut root: Node = Node::List(vec![]);

    {
        tokens.into_iter().fold((&mut root, vec![]), handle_token);
    }

    root
}

fn add_node(tree: &mut Node, indices: &Vec<NodeIndex>, node: Node) -> NodeIndex {
    let node_to_add_to = get_node(tree, indices);

    match node_to_add_to {
        &mut Node::List(ref mut vec) => {
            vec.push(node);
            vec.len() - 1
        },
        _ => panic!(),
    }
}

fn get_node<'a>(tree: &'a mut Node, indices: &Vec<NodeIndex>) -> &'a mut Node {
    indices.iter().fold(tree, |node, index| match node {
        &mut Node::List(ref mut vec) => &mut vec[*index],
        _ => panic!(),
    })
}

fn handle_token<'a>(state: (&'a mut Node, Vec<NodeIndex>), token: &Token) -> (&'a mut Node, Vec<NodeIndex>) {
    let (tree, mut index_stack) = state;

    match *token {
        Token::LParen => {
            let new_index = add_node(tree, &index_stack, Node::List(vec![]));
            index_stack.push(new_index);
        },
        Token::RParen => { index_stack.pop(); },
        Token::Identifier(ref identifier) => { add_node(tree, &index_stack, Node::Identifier(identifier.to_owned())); },
        Token::Number(number) => { add_node(tree, &index_stack, Node::Number(number)); },
        Token::Str(ref s) => { add_node(tree, &index_stack, Node::Str(s.to_owned())); },
        Token::EOF => { assert!(index_stack.is_empty()); },
    }

    (tree, index_stack)
}