Построение дерева векторов

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, содержащуюся в варианте Node::List этого Node, и добавить его как изменяемый заимствование на внешний Vec (stack). Если бы это было разрешено, у вас теперь были бы внешние Vec и внутренний Vec, способный мутировать этот NodeVec в то же время.

Я бы попытался немного переосмыслить ваш дизайн и посмотреть, можете ли вы сделать собственность более четкой.

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