cannot borrow as immutable because it is also borrowed as mutable immutable borrow occurs here

Question

Learning some rust programming (Leetcode Q3).

Got the error:

cannot borrow `result` as immutable because it is also borrowed as mutable
immutable borrow occurs hererustcE0502
solution.rs(42, 23): mutable borrow occurs here
solution.rs(44, 13): mutable borrow later used here

I can change the program from if result.is_none() { to if current.is_none() { and it'll work. But current and result are not the same thing. current is the last node in a linked list and result is head. How do I do this?

Rust playground link: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=741c07fad8aa730a44ba5773395aed7c

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

#[allow(dead_code)]
struct Solution;

#[allow(dead_code)]
impl Solution {
    pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut carry = 0;
        let mut result: Option<Box<ListNode>> = None;
        let mut current: &mut Option<Box<ListNode>> = &mut None;
        let mut node1 = &l1;
        let mut node2 = &l2;

        while node1.is_some() || node2.is_some() || carry > 0 {
          if node1.is_some() {
            carry += node1.as_ref().unwrap().val;
            node1 = &node1.as_ref().unwrap().next;
          }
          if node2.is_some() {
            carry += node2.as_ref().unwrap().val;
            node2 = &node2.as_ref().unwrap().next;
          }

          if result.is_none() { // solution.rs(42, 23): mutable borrow occurs here
            result = Some(Box::new(ListNode::new(carry % 10)));
            current = &mut result; // solution.rs(44, 13): mutable borrow later used here
          } else {
            current.as_mut().unwrap().next = Some(Box::new(ListNode::new(carry % 10)));
            current = &mut current.as_mut().unwrap().next;
          }
          carry = carry / 10;
        }
        return result;
    }
}


#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn it_works() {
        fn from_vec(l: Vec<i32>) -> Option<Box<ListNode>> {
          let mut start = None;
          let mut current: &mut Option<Box<ListNode>> = &mut None;
          for x in l {
            if current.is_none() {
              start = Some(Box::new(ListNode::new(x)));
              current = &mut start;
            } else {
              current.as_mut().unwrap().next = Some(Box::new(ListNode::new(x)));
              current = &mut current.as_mut().unwrap().next;
            }
          }
          return start;
        }
        fn compute(l1: Vec<i32>, l2: Vec<i32>) -> Vec<i32> {
          let result = Solution::add_two_numbers(from_vec(l1), from_vec(l2));
          let mut node = &result;
          let mut result_vec = Vec::new();
          while node.is_some() {
            result_vec.push(node.as_ref().unwrap().val);
            node = &node.as_ref().unwrap().next;
          }
          return result_vec;
        }
        assert_eq!(compute(vec![2, 4, 3], vec![5, 6, 4]), vec![7, 0, 8]);
        assert_eq!(compute(vec![0], vec![0]), vec![0]);
        assert_eq!(compute(vec![9, 9, 9, 9, 9, 9, 9], vec![9, 9, 9, 9]), vec![8, 9, 9, 9, 0, 0, 0, 1]);
    }
}

Answer 1

Linked lists are notoriously hard to implement in Rust because of these kinds of aliasing problems. The fundamental problem is that you can't take a mutable reference to something owned by result (even indirectly) and then use result again while that reference is alive.

The crux of the problem is that you check if result has a value -- in other words, whether the result list is empty or not. This doesn't work because on the second iteration through the loop, current references result and so result is inaccessible as it's become exclusively borrowed.

The simplest way to fix this issue is to make the check of result.is_some() unnecessary by changing where current points.

Instead of having a reference to the last node in the list, which may or may not exist yet, have a reference to the next node to be populated -- that is, the None at the end -- which always exists somewhere.

let mut result: Option<Box<ListNode>> = None;
let mut current: &mut Option<Box<ListNode>> = &mut result;

Now you don't need to check result because current always points to where you should put the next node. That could be in result or in a node's next field, but you don't have to care about that.

You can replace the if/else blocks with this:

*current = Some(Box::new(ListNode::new(carry % 10)));
current = &mut current.as_mut().unwrap().next;

This works because you do not access result between its declaration and the moment you return it from the function. When you return it, the current reference is no longer considered active because of non-lexical lifetimes.

(Playground)