Problems on get list of nodes from linklist due to mutable/immutable ownership

[Bladeliu]

Hi,

I'm a C/C++ developer and new to Rust; I'm coding linklist as an exercise.

In C/C++, it's a common practice to pass a vector's reference as function parameter to modify the vector, e..g,

void get_nodes(linklist *list, &vector<Node*> v)
{
     // get a bunch of nodes as pointers, node0 and node1 are pointers to node
     v.push_back(node0);
     v.push_back(node1);
}

In Rust, I do the same but encountered some problems related to mutable/immutable ownership. Appreciate your help!

Here is a reproducible code (also available in Playground)

use std::cell::RefCell;

struct MyNode
{
    val: i32,
    desc: String,
    next: Option<Box<MyNode>>
}

impl MyNode
{
    pub fn new(i: i32, d: &Option<String>) -> Self
    {
        MyNode
        {
            val: I,
            desc: match(d) {None=>{"".to_string()} Some(dd)=>{dd.clone()}},
            next: None
        }
    }
}

struct MyList
{
    root: Option<Box<MyNode>>
}

impl MyList
{
    pub fn new() -> MyList
    {
        MyList
        {
            root: Some( Box::new( MyNode::new( 0, &Some( "root".to_string() ) ) ) )
        }
    }

    pub fn get_root(&mut self) -> &mut Option<Box<MyNode>>
    {
        return (&mut self.root);
    }

    pub fn get_range_node<'a>(&'a mut self, v2: &'a mut Vec<&'a Option<Box<MyNode>>>) // &mut Vec<&mut Box<MyNode>>
    {
        let mut head = self.get_root();
        let mut curr = head.as_ref();

        loop
        {
            // https://web.stanford.edu/class/cs110l/lecture-notes/lecture-06/
            if (curr.is_none())
            {
                break;
            }

            // print!("*** {}\n", curr.unwrap().val);
            let mut next = &curr.unwrap().next;
            v2.push (&mut next);
            curr = next.as_ref();
        }

        for i in 0..v2.len()
        {
            if (v2[i].is_some())
            {
                // println!("###{}:{}", i, v2[i].as_ref().unwrap().val);
            }
        }
    }

    pub fn get_tail(&mut self) -> &mut Option<Box<MyNode>>
    {
        let mut curr = self.get_root();

        loop
        {
            if curr.as_ref().unwrap().next.is_none()
            {
                break;
            }
            else
            {
                curr = &mut curr.as_mut().unwrap().next;
            }
        }

        return curr;
    }

    pub fn insert(&mut self, i: i32)
    {
        let new_node = Some( Box::new(MyNode::new(i, &Some(i.to_string() ))));
        let tail = self.get_tail();
        tail.as_mut().unwrap().next = new_node;
    }

    pub fn traverse(&mut self)
    {
        let mut curr = self.get_root();
        let mut i = 0;
        loop
        {
            if (curr.is_none())
            {
                break;
            }
            else
            {
                println!("[{}]: {}, desc:{:?}", i, curr.as_ref().unwrap().val, curr.as_ref().unwrap().desc);
                curr = &mut curr.as_mut().unwrap().next;
                i += 1;
            }
        }
    }
}

#[test]
fn test_clean_list()
{

    let n0 = MyNode::new(0, &Some("node0".to_string()));
    let mut list = MyList::new();

    let mut len:usize = 5;

    // insert
    for i in 0..len
    {
        list.insert(i as i32);
    }

    println!("Traverse list...");
    list.traverse();

    // Option1: access v
    let mut v = vec![];
    list.get_range_node(&mut v);

    // Compiler error: immutable borrow occurs here;  mutable borrow later used here
    let v_len = &v.len();

    // Option2: use RefCell
    let mut v2 = RefCell::new(vec![]);
    let mut v2_0 = v2.borrow_mut();

    // Compiler error:  borrowed value does not live long enough
    list.get_range_node(&mut v2_0);
    let v2_len = v2_0.len();
}

[kpreid]

There are two problems.

@Bladeliu

    pub fn get_range_node<'a>(&'a mut self, v2: &'a mut Vec<&'a Option<Box<MyNode>>>) // &mut Vec<&mut Box<MyNode>>

You've given too many things the same lifetime here. Writing &'a mut SomeType<... 'a ...> is nearly always a mistake, because you're saying that the SomeType in this case, Vec) is exclusively borrowed for as long as its contents are valid — so it becomes permanently borrowed and useless (you can use it exactly once).

To fix this, stop setting the &mut Vec's lifetime equal to the borrows of self — let it be a different lifetime. If you change this line as follows, it will compile.

pub fn get_range_node<'a>(&'a mut self, v2: &mut Vec<&'a Option<Box<MyNode>>>)

But I also changed the element type from &'a mut Option... to &'a Option. It is impossible to collect a vector of &mut MyNodes (with or without a Box or Option around them), because each &mut MyNode constitutes access to mutate the rest of the list, which would violate the uniqueness/non-aliasing of mutable references because there'd be two paths to mutate the same data.

You can, if you like, build a vector of &mut i32s that point to the data of each node. But you can't return multiple &muts that all let you mutate the spine of the list.

[Bladeliu]

@kpreid Thanks so much, very helpful.

By the way, I have a couple of other related questions.

1. To modify a vector, which one is better? Pass by reference from caller(code posted before), or let callee return a new vector? e.g,

pub fn get_nodes(&mut self)-> Vec<& Option<Box<MyNode>>>
{
    let v = vec![];
    ...
   return v;  
}

In C++, return a vector from caller is not sound for performance and ownership; but as ownership is 'moved' from caller to callee in Rust, it's a good practice to return vector?

2. For the previous code I posted, suppose the returning node is going to be modified, how to do this that does not make copy of the node.

Option<& Box<MyNode>> changes to Option<&mut Box<MyNode>>

If there is a c: &Option<Box<MyNode>>, we can use c.as_mut(). But the '&' is inside here.

[kpreid]

To modify a vector, which one is better? Pass by reference from caller(code posted before), or let callee return a new vector?

When possible (and it is in this case), the best choice is to return an iterator. This allows the caller to decide whether the iterator's items should be collected into a new vector, an existing vector, used in a loop, or anything else.

For the previous code I posted, suppose the returning node is going to be modified, how to do this that does not make copy of the node.

As I said, you cannot return mutable references to more than one entire node. But you can return references to the data. For this purpose, splitting your struct into two parts may be useful:

struct Node {
    data: Data,
    next: Option<Box<Node>>,
}
struct Data {
    val: i32,
    desc: String,
}

Given this split, you can return an iterator (or vector) of &mut Data. There is no borrow conflict because the nexts are not reachable from that.

[quinedot]

Mandatory notice: linked lists^[1] are a notoriously bad way to learn Rust.

---

1. and other traditionally pointer-heavy data structures ↩︎

[Bladeliu]

Thanks. To manipulate data structures such as binary trees, is there a better approach using Rust?

[kpreid]

The thing is that linked lists (and to a lesser extent trees, yes) tend towards needing techniques that are tricky or even require unsafe. Whether they actually do in the specific case depends on which operations you want to implement.

If you do specifically want to use a linked list as an exercise, I concur with the implied recommendation to read Learn Rust With Entirely Too Many Linked Lists — it's a good tutorial for these specific ideas.

But if you're not attached to learning with linked lists in particular, you should consider doing something else. Linked lists are more often than not a bad choice of data structure (if they're not specialized for a particular purpose like being concurrent or intrusive), so by choosing them you're making something particularly difficult and particularly unlike the usual run of Rust programming.

[Bladeliu]

@kpreid Thank you very much for the insightful suggestion.