Value moved here, in previous iteration of loop

Question

This is what I wrote for LeetCode: Add Two Numbers

//2. Add Two Numbers
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

struct Solution;

impl Solution {
    pub fn list_to_num(ls: &Option<Box<ListNode>>) -> i64 {
        let mut vec = vec![];
        let mut head = ls;

        while let Some(node) = head {
            vec.push(node.val);
            head = &node.next;
        }

        vec.reverse();

        let mut num = 0i64;

        for x in vec {
            num *= 10;
            num += x as i64;
        }

        num
    }

    pub fn num_to_list(num: i64) -> Option<Box<ListNode>> {
        let num_str = num.to_string();
        let vec = num_str
            .chars()
            .map(|x| x.to_digit(10).unwrap() as i32)
            .collect::<Vec<_>>();

        let mut res = None;
        for x in vec {
            let mut one = ListNode::new(x);
            one.next = res;
            res = Some(Box::new(one));
        }

        res
    }

    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut vec = vec![] as Vec<i32>;
        let mut step = 0;
        let mut left = l1;
        let mut right = l2;
        loop {
            match (left, right) {
                (None, None) => {
                    if step != 0 {
                        vec.push(step);
                    }
                    break;
                }
                (Some(leftN), None) => {
                    let curr = leftN.val + step;
                    if curr >= 10 {
                        vec.push(curr - 10);
                        step = 1
                    } else {
                        vec.push(curr);
                        step = 0
                    }
                    left = leftN.next
                }
                (None, Some(rightN)) => {
                    let curr = rightN.val + step;
                    if curr >= 10 {
                        vec.push(curr - 10);
                        step = 1
                    } else {
                        vec.push(curr);
                        step = 0
                    }
                    right = rightN.next
                }
                (Some(leftN), Some(rightN)) => {
                    let curr = leftN.val + rightN.val + step;
                    if curr >= 10 {
                        vec.push(curr - 10);
                        step = 1
                    } else {
                        vec.push(curr);
                        step = 0
                    }
                    right = rightN.next;
                    left = leftN.next
                }
            }
        }

        vec.reverse();

        let mut res = None;

        for x in vec {
            let mut next = ListNode::new(x);
            next.next = res;
            res = Some(Box::new(next));
        }
        res
    }
}

fn main() {
    let list1 = Solution::num_to_list(9);
    let list2 = Solution::num_to_list(991);
    println!("list1 {:?}", list1);
    println!("list2 {:?}", list2);
    let res = Solution::add_two_numbers(list1, list2);
    println!("summed {:#?}", res);
}

I get a compile error

error[E0382]: use of moved value: `left`
  --> src/main.rs:66:20
   |
63 |         let mut left = l1;
   |             -------- move occurs because `left` has type `std::option::Option<std::boxed::Box<ListNode>>`, which does not implement the `Copy` trait
...
66 |             match (left, right) {
   |                    ^^^^ value moved here, in previous iteration of loop

error[E0382]: use of moved value: `right`
  --> src/main.rs:66:26
   |
64 |         let mut right = l2;
   |             --------- move occurs because `right` has type `std::option::Option<std::boxed::Box<ListNode>>`, which does not implement the `Copy` trait
65 |         loop {
66 |             match (left, right) {
   |                          ^^^^^ value moved here, in previous iteration of loop

I think each iteration is independent, and if the value is borrowed by a previous iteration, it should be returned in "this" iteration.

If I replace match (left, right) { with match (left.clone(), right.clone()) {, the code compiles, but it might consume more memory than necessary. What is the better way to make it compile and be memory economical?

Answer 1

You're not borrowing the nodes, you're moving them.

In order to use references, you should replace

let mut left = l1;
let mut right = l2;

with

let mut left = &l1;
let mut right = &l2;

and then later

right = rightN.next;

with

right = &rightN.next;

etc.

playground