構建一個向量樹

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

這個研究了一下後，就好像我試圖做一些完全不地道，以鐵鏽，但我不確定。有沒有簡單的方法來完成這項工作，還是我需要重新考慮這個問題？

我試圖減少的問題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的可變借款中。然後，您嘗試可變地借用變體中包含的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) 
}