Is it possible to allow alias of mutable reference in a safe function?

help
1

I was building up a linked list, and I faced a problem related to the borrow checker.

Suppose there are two immutable reference of two locations (i.e. pointers) in the list (probably by iterations, or some search functions), and now I need to swap the two nodes, (or delete all the nodes between the two locations). However, I cannot borrow the same list in both mutable and immutable ways.

Here is a brief description of how I make this operation.

struct List<T> {/* a linked list*/}

struct Cursor<'a, T: 'a> {
    list: &'a List<T>,
    ptr: NonNull<Node<T>>,
}

// `node1` and `node2` are two nodes in `list`, and they both
// have a `&'a List<T>` reference inside.
// 
// To make this function safe, `node1.list` and `node2.list` are necessary
// because without these immutable borrows, we cannot guarantee that 
// `list` must not have been modified before this function is called.
// 
// However, since `list`, `node1.list` and `node2.list` are the same
// address, the borrow checker will not allow both immutable borrow
// and mutable borrow exists.
// 
// Actually in this function, `node1.list` and `node2.list` are never
// used (or saying dereferenced), and dropped before `list` the mutable
// reference is used. Is there anyway to let the borrow checker to allow
// both mutable and immutable borrow in function arguments and
// check it later inside the function body where the references are
// actually used?
//
// It is possible to achieve this if this function call is manually
// "inlined", because the NLL borrow checker knows exactly 
// where the mutable reference is actually used. But, how to
// do with such a function call?
fn swap_nodes<'a: 'b + 'c, 'b, 'c, T>(
    // Is it possible to add an annotation to tell the compiler
    // that `list` might have alias? such as `#[with_alias(node1, node2)]`
    list: &'a mut List<T>, 
    node1: Cursor<'b, T>,
    node2: Cursor<'c, T>,
) {
    // Here the mutable reference `list` is used but it is not
    // dereferenced.
    if ptr::eq(list, node1.list) && ptr::eq(list.node2.list) {
        let (ptr1, ptr2) = (node1.ptr, node2.ptr);
        drop(node1);
        drop(node2);
        // Make sure `node1.list` and `node2.list` is no longer used.
        unsafe {
            // Do swap node1 and node2 ...
        }
    }
}
2

No, there is no way to allow aliases to exclusive references. In fact it looks like you don't need to take the reference to the list at all, you already have two references to the list in the cursors.

3

I do need the reference to the list.

Without this immutable reference to the list, I cannot make sure that the list is not changed. What if the two nodes are deleted? Suppose there is another call like list.clear() before this function call:

let mut list = List::from([1, 2, 3]);
let cursor1 = list.cursor_at(1);
let cursor2 = list.cursor_at(2);
list.clear();
list.swap_nodes(cursor1, cursor2); // cursor1 and cursor2 is invalid here
4 
struct Cursor<'a, T: 'a> {
    list: &'a List<T>, // < you have a reference here
    ptr: NonNull<Node<T>>,
}

So shouldn't be able to clear the list

That's the while point of an immutable reference...

Edit: I think we're talking past each other. I meant this

fn swap_nodes<'a: 'b + 'c, 'b, 'c, T>(
    // Is it possible to add an annotation to tell the compiler
    // that `list` might have alias? such as `#[with_alias(node1, node2)]`
-   list: &'a mut List<T>, 
    node1: Cursor<'b, T>,
    node2: Cursor<'c, T>,
) {
5

I didn't describe it clear. You mentioned that:

In fact it looks like you don't need to take the reference to the list at all, you already have two references to the list in the cursors.

I think you meant this:

fn swap_nodes<T>(
    list: &mut List<T>, 
    node1: NonNull<Node<T>>,
    node2: NonNull<Node<T>>,
) {
    // ...
}

Then how about this?

let mut list = List::from([1, 2, 3]);
let cursor1 = list.cursor_at(1).ptr;
let cursor2 = list.cursor_at(2).ptr;
list.clear(); // no immutable reference yet, so this statement is allowed.
list.swap_nodes(cursor1, cursor2); // cursor1 and cursor2 is invalid here
6 
fn swap_nodes<'a: 'b + 'c, 'b, 'c, T>(
    // Is it possible to add an annotation to tell the compiler
    // that `list` might have alias? such as `#[with_alias(node1, node2)]`
-   list: &'a mut List<T>, 
    node1: Cursor<'b, T>,
    node2: Cursor<'c, T>,
) {

I don't think removing list: &'a mut List<T> can still keep this function safe, because if there are somewhere else who holds an immutable reference of this list, after this function, his reference might be invalid.

7

In case you didn't catch my edit :stuck_out_tongue_closed_eyes:

Have you read Learn Rust With Entirely Too Many Linked Lists or the Nomicon? I'd say that the Nomicon Is required reading before writing any unsafe.

The thing about linked lists is that links are inherently shared. This means that you must have some amount of interior mutability in in order to safely mutate the list (assuming you're writing a doubly linked list). And swapping doesn't destroy any nodes, so it should be safe. Granted &_ no longer means immutable now, but that's the price to pay.

8

Honestly, I haven't learnt Nomicon carefully yet but I have learnt the codes in std::collections::LinkedList, and have started to write my own (cyclic_list - Rust) based on my understanding of std::collections::LinkedList.

The std::collections::LinkedList is hard to use because the cursors are unstable yet, and have limited functions (e.g., there is no sort, and even impossible to implement it using the CursorMut of current version).

In my opinion, std::collections::LinkedList is designed not to be have internal mutabilities by default (i.e., you cannot modify it with an immutable reference via a safe function). So I think my example code made sence for std::collections::LinkedList. It is similar with my version of linked list (as least it is designed to be).

I need a linked list to implement a GC based on the RC system.

Let me read the materials you provided more carefully, and talk with you about this.

9

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.