Recursive use of iterator

help
1

I'm trying to group element from a "flat" structure.

This is an example:

use std::slice::Iter;

#[derive(Debug, Clone)]
struct Node {
    id: u8,
    members: Option<Vec<Node>>,
}

impl Node {
    fn new(id: u8) -> Self {
        Node { id, members: None }
    }

    fn new_with_members(id: u8, members: Vec<Node>) -> Self {
        Node {
            id,
            members: Some(members),
        }
    }
}

#[derive(Clone)]
enum Element {
    Simple(u8),
    Replication(u8, u8),
}

fn iterate(mut iterator: Iter<Element>, n_times: Option<u8>) -> Vec<Node> {
    let mut lst = Vec::new();
    let n_times = match n_times {
        Some(n) => n,
        None => 255,
    };
    for _i in 0..n_times {
        let element = iterator.next();
        match element {
            Some(element) => match element {
                Element::Simple(id) => lst.push(Node::new(*id)),
                Element::Replication(id, n) => {
                    let members = iterate(iterator.clone(), Some(*n));
                    lst.push(Node::new_with_members(*id, members.clone()))
                }
            },
            None => return lst,
        }
    }
    lst
}

fn main() {
    let vec = vec![
        Element::Simple(1),
        Element::Replication(2, 2), // the next two elements will be member of this element
        Element::Simple(3),
        Element::Simple(4),
        Element::Simple(5),
    ];
    let nodes = iterate(vec.iter(), None);
    dbg!(nodes);
}

(Playground)

The result is not that I expected and I suspect that the error came from the iterator.clone() statement.

Expected result:

[src/main.rs:59] nodes = [
    Node {
        id: 1,
        members: None,
    },
    Node {
        id: 2,
        members: Some(
            [
                Node {
                    id: 3,
                    members: None,
                },
                Node {
                    id: 4,
                    members: None,
                },
            ],
        ),
    },
    Node {
        id: 5,
        members: None,
    },
]

But, if I do not clone the iterator, I got this error:

  --> src/main.rs:35:23
   |
28 | fn iterate(mut iterator: Iter<Element>, n_times: Option<u8>) -> Vec<Node> {
   |            ------------ move occurs because `iterator` has type `std::slice::Iter<'_, Element>`, which does not implement the `Copy` trait
...
35 |         let element = iterator.next();
   |                       ^^^^^^^^ value borrowed here after move
...
40 |                     let members = iterate(iterator, Some(*n));
   |                                           -------- value moved here, in previous iteration of loop

Do you have any advice ?

2

The advice would be to avoid giving (and thus losing) ownership of the iterator to the nested call:

- // consumes the iterator: compile error.
- iterate(iterator, …)

- // clones the iterator state / cursor: logic bug
- iterator(iterator.clone(), …)

+ // uses the iterator without taking ownership of it, just _borrowing_ it:
+ iterate(&mut iterator, …)

So basically use iterate(&mut iterator, …), which means you need to change the signature of iterate to:

- fn iterate(mut iterator: Iter<Element> …
+ fn iterate(iterator: &mut Iter<Element> …

Another option would be to have iterate also return the "rest" of its iterator, so as to get ownership back. But this is cumbersome to write; the whole point about borrows is to be more ergonomic than a "give and explicitly take back" pattern.

3

To avoid a clone, do something like this, which seems to give the expected results.

EDIT: Yandros pretty much explained it exactly.

4

Thank you @Yandros and @skysch for your answers. It's perfect.