构建向量树

Question

我正在尝试制作一个简单的 LISP 解析器，但我卡在了将标记向量转换为 AST 节点树的步骤。

我创建树的根，然后在我当前要添加下一个节点的树中维护一堆引用。问题是，无论我尝试什么，借用检查器似乎都认为我引用的东西寿命不够长。

这是代码：

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
}

这是编译器输出：

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>> {
   |                                                                                                 ^

稍微研究一下之后，我似乎想做一些完全不符合 Rust 惯用语的事情，但我不确定。有没有简单的方法来完成这项工作，还是我需要重新考虑一下？

我尝试减少问题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
}

Answer 1

如@wimh 所述，您侵犯了所有权。让我试着分解一下，看看它是否有意义。

stack[0][0] 给你一个 Node 包含在 Vec 的可变借用中。然后，您尝试可变借用 Node 的 Node::List 变体中包含的 Vec，并将其作为可变借用添加到外部 Vec（stack).如果这被允许，你现在将拥有外部 Vec 和内部 Vec 能够同时突变 Node 的 Vec。

我会试着重新考虑一下您的设计，看看您是否可以让所有权更明确一些。

Answer 2

阅读 blog post about modeling graphs using vector indices 后，我决定尝试类似的方法。生成的代码有效并且简单得多：

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)
}

构建向量树

Building a tree of vectors

rust

borrow-checker