在 Rust 中的迭代期间将迭代器传递给递归调用

Question

我正在为简单的树语法编写解析器。为此，我需要从一系列标记构建一棵树。

由于借用者检查器，代码的主体目前陷入了问题：

use std::vec;

fn parse_iter(token_iter: vec::IntoIter<Token>) -> Result<Vec<Node>, String>
{
    let mut nodes: Vec<Node> = vec![];
    let mut cur_node: Option<Node> = None;
    for token in token_iter {
        match token {
            Token::ParenOpen => {
                if let Some(mut node) = cur_node {
                    let mut children = parse_iter(token_iter)?;
                    node.children.append(&mut children);
                } else {
                    return Err("invalid token sequence".to_string());
                }
            }
            Token::ParenClose => {
                break;
            }
            Token::Name(name) => {
                let node = Node::new(name);
                nodes.push(node);
                cur_node = Some(node);
            }
            Token::Comma => {}
        }
    }
    Ok(nodes)
}


pub enum Token {
    ParenOpen,
    ParenClose,
    Comma,
    Name(String),
}

pub struct Node {
    pub name: String,
    pub children: Vec<Node>,
}

impl Node {
    pub fn new<'a>(name: String) -> Node {
        Node { name: name, children: vec![] }
    }
}

产生的错误信息：

   Compiling playground v0.0.1 (/playground)
error[E0382]: use of moved value
  --> src/lib.rs:10:29
   |
10 |                 if let Some(mut node) = cur_node {
   |                             ^^^^^^^^ value moved here, in previous iteration of loop
   |
   = note: move occurs because value has type `Node`, which does not implement the `Copy` trait

error[E0382]: use of moved value: `token_iter`
  --> src/lib.rs:11:60
   |
3  | fn parse_iter(token_iter: vec::IntoIter<Token>) -> Result<(Vec<Node>, vec::IntoIter<Token>), String>
   |               ---------- move occurs because `token_iter` has type `std::vec::IntoIter<Token>`, which does not implement the `Copy` trait
...
7  |     for token in token_iter {
   |                  ----------
   |                  |
   |                  value moved here
   |                  help: consider borrowing to avoid moving into the for loop: `&token_iter`
...
11 |                     let mut children_and_iter = parse_iter(token_iter)?;
   |                                                            ^^^^^^^^^^ value moved here, in previous iteration of loop

error[E0382]: use of moved value: `node`
  --> src/lib.rs:23:33
   |
21 |                 let node = Node::new(name);
   |                     ---- move occurs because `node` has type `Node`, which does not implement the `Copy` trait
22 |                 nodes.push(node);
   |                            ---- value moved here
23 |                 cur_node = Some(node);
   |                                 ^^^^ value used here after move

正如你在上面看到的，token_iter 和 cur_node 都在这个函数中非法移动了几次，我不确定如何正确地包装它们以满足借用检查器。我曾尝试使用 RefCell<Rc<T>>s，但我最终需要解包这些值，所以这些并没有真正帮助。我正在尝试的 Rust 可行吗？

Answer 1

我认为迭代 for token in token_iter 和试图在循环内对 token_iter 进行操作是个坏主意。因此，我建议将token_iter当成&mut，然后手动迭代。

此外，同时拥有 cur_node 和 nodes 似乎是多余的（如果我没记错的话，cur_node 本质上是 nodes.last）。因此，我会尝试以下操作：

use std::vec;

fn parse_iter(token_iter: &mut vec::IntoIter<Token>) -> Result<(Vec<Node>, &mut vec::IntoIter<Token>), String>
{
    let mut nodes: Vec<Node> = vec![];
    while let Some(token)=token_iter.next() {
        match token {
            Token::ParenOpen => {
                if let Some(ref mut node) = nodes.last_mut() {
                    let mut children_and_iter = parse_iter(token_iter)?;
                    node.children.append(&mut children_and_iter.0);
                } else {
                    return Err("invalid token sequence".to_string());
                }
            }
            Token::ParenClose => {
                break;
            }
            Token::Name(name) => {
                nodes.push(Node::new(name));
            }
            Token::Comma => {}
        }
    }
    Ok((nodes, token_iter))
}


pub enum Token {
    ParenOpen,
    ParenClose,
    Comma,
    Name(String),
}

pub struct Node {
    pub name: String,
    pub children: Vec<Node>,
}

impl Node {
    pub fn new<'a>(name: String) -> Node {
        Node { name: name, children: vec![] }
    }
}

在 Rust 中的迭代期间将迭代器传递给递归调用

Passing an iterator into a recursive call during an iteration in Rust

recursion

rust

borrow-checker