CODEWITHSUNDEEP
recursionrustborrow-checker
pixatlazaki
pixatlazaki

Reputation: 561

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

I'm writing a parser for a simple tree syntax. In doing so, I need to construct a tree from a series of tokens.

The meat of the code is currently mired with problems due to the borrower checker:

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![] }
    }
}

The resulting error messages:

   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

As you can see above, both token_iter and cur_node move illegally several times in this function, and I'm unsure of how wrap them correctly so as to satisfy the borrow checker. I've attempted using RefCell<Rc<T>>s but I eventually need to unwrap the values so these don't really help. Is what I'm attempting possible in Rust?

Upvotes: 0

Views: 360

Answers (1)

phimuemue
phimuemue

Reputation: 35983

I think it is a bad idea to iterate for token in token_iter and trying to operate on token_iter inside the loop. Thus, I suggest to take token_iter as &mut, and iterate manually.

Additionally, having both cur_node and nodes seems redundant (if I am not mistaken, cur_node is essentially nodes.last). Thus, I'd try the following:

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![] }
    }
}

Upvotes: 2

Related Questions