rust - 构建向量树

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(堆栈)。如果允许这样做，您现在将拥有外部 Vec 和内部 Vec 能够改变 Node 的 Vec 同时。

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