安全地 return 对内部节点的多个引用，同时仍然允许其他节点的变异

Question

假设，例如，我有一个不允许删除节点的链表。

是否可以 return 共享对已插入值的引用，同时仍允许更改节点的相对顺序或插入新节点？

只要一次只使用一个节点对列表进行变异，即使通过其中一个节点进行变异也应该是安全的"on paper"。是否可以在 rust 的所有权系统中表示这一点？

我特别感兴趣的是在没有运行时开销的情况下这样做（可能在实现中使用 unsafe，但在接口中不使用）。

编辑：根据要求，这里有一个示例，概述了我的想法。

let list = MyLinkedList::<i32>::new()
let handle1 = list.insert(1); // Returns a handle to the inserted element.
let handle2 = list.insert(2);

let value1 : &i32 = handle1.get();
let value2 : &i32 = handle2.prev().get(); // Ok to have two immutable references to the same element.
list.insert(3); // Also ok to insert and swap nodes, while the references are held.
list.swap(handle1,handl2);
foo(value1,value2);

let exclusive_value: &mut i32 = handle1.get_mut(); // While this reference is held, no other handles can be used, but insertion and permutation are ok 
handle5 = list.insert(4);
list.swap(handle1, handle2);

换句话说，列表节点内部包含的数据被视为一种可以借用的资源shared/mutably，节点之间的链接是另一种可以借用的资源shared/mutably.

Answer 1

In other words, the data contained inside the nodes of the list is treated as one resource that can be borrowed shared/mutably, and the links between the nodes are another resource that can be borrowed shared/mutably.

处理这种空间分区的想法是为每个分区引入不同的"key"；这很容易，因为它们是静态的。这被称为密码模式。

在没有 brands 的情况下，它仍然需要运行次检查：验证元素键是否绑定到此特定列表实例是强制性的为了安全。然而，这是一个始终为 true 的只读比较，因此就运行时间检查而言，性能与它得到的一样好。

这个想法，简而言之：

let (handles, elements) = list.keys();
let h0 = handles.create(4);
handles.swap(h0, h1);
let e = elements.get(h0);

在您的用例中：

总是可以更改链接，因此我们将为此使用内部可变性。
句柄内元素的借用检查将通过借用elements。

可以找到完整的实现 here。它大量使用 unsafe，我不保证它是完全安全的，但希望足以进行演示。

在这个实现中，我选择了哑句柄并在键类型本身上实现了操作。这限制了需要从主列表中借用的类型数量，并简化了借用。

核心思想，那么：

struct LinkedList<T> {
    head: *mut Node<T>,
    tail: *mut Node<T>
}

struct Handles<'a, T> {
    list: ptr::NonNull<LinkedList<T>>,
    _marker: PhantomData<&'a mut LinkedList<T>>,
}

struct Elements<'a, T> {
    list: ptr::NonNull<LinkedList<T>>,
    _marker: PhantomData<&'a mut LinkedList<T>>,
}

LinkedList<T> 将充当存储，但只会执行 3 个操作：

施工，
毁灭，
分发钥匙。

Handles 和 Elements 这两个键都将可变地借用列表，保证其中一个（每个）可以同时存在。借用检查将阻止创建新的 Handles 或 Elements，如果它们的任何实例仍然存在于此列表中：

list：授予对列表存储的访问权限； Elements 只会将它用于检查（必要的）运行-时间不变量，并且永远不会取消引用它。
_marker：是借用检查实际保证排他性的关键。

到目前为止听起来很酷？为了完成，最后两个结构然后：

struct Handle<'a, T> {
    node: ptr::NonNull<Node<T>>,
    list: ptr::NonNull<LinkedList<T>>,
    _marker: PhantomData<&'a LinkedList<T>>,
}

struct Node<T> {
    data: T,
    prev: *mut Node<T>,
    next: *mut Node<T>,
}

Node 是双向链表最明显的表示，所以我们做对了。 Handle<T> 中的 list 与 Elements 中的目的完全相同：验证 Handle 和 Handles/Elements 是谈论 list 的同一个实例。 get_mut 安全至关重要，否则有助于避免错误。

Handle<'a, T> 的一生与 LinkedList 联系在一起是有微妙原因的。我很想删除它，但是这将允许从列表创建句柄，销毁列表，然后在同一地址重新创建列表......现在 handle.node 将悬空！

而有了，我们只需要在Handles和Elements上实现我们需要的方法即可。几个样本：

impl<'a, T> Handles<'a, T> {
    pub fn push_front(&self, data: T) -> Handle<'a, T> {
        let list = unsafe { &mut *self.list.as_ptr() };

        let node = Box::into_raw(Box::new(Node { data, prev: ptr::null_mut(), next: list.head }));
        unsafe { &mut *node }.set_neighbours();

        list.head = node;

        if list.tail.is_null() {
            list.tail = node;
        }

        Handle {
            node: unsafe { ptr::NonNull::new_unchecked(node) },
            list: self.list, _marker: PhantomData,
        }
    }

    pub fn prev(&self, handle: Handle<'a, T>) -> Option<Handle<'a, T>> {
        unsafe { handle.node.as_ref() }.prev().map(|node| Handle {
            node,
            list: self.list,
            _marker: PhantomData
        })
    }
}

并且：

impl<'a, T> Elements<'a, T> {
    pub fn get<'b>(&'b self, handle: Handle<'a, T>) -> &'b T {
        assert_eq!(self.list, handle.list);

        let node = unsafe { &*handle.node.as_ptr() };
        &node.data
    }

    pub fn get_mut<'b>(&'b mut self, handle: Handle<'a, T>) -> &'b mut T {
        assert_eq!(self.list, handle.list);

        let node = unsafe { &mut *handle.node.as_ptr() };
        &mut node.data
    }
}

这应该是安全的，因为：

Handles，创建新句柄后，只访问其链接。
Elements 仅 returns 引用 data，并且在访问它们时无法修改链接。

用法示例：

fn main() {
    let mut linked_list = LinkedList::default();
    {
        let (handles, mut elements) = linked_list.access();
        let h0 = handles.push_front("Hello".to_string());

        assert!(handles.prev(h0).is_none());
        assert!(handles.next(h0).is_none());

        println!("{}", elements.get(h0));

        let h1 = {
            let first = elements.get_mut(h0);
            first.replace_range(.., "Hallo");

            let h1 = handles.push_front("World".to_string());
            assert!(handles.prev(h0).is_some());

            first.replace_range(.., "Goodbye");

            h1
        };

        println!("{} {}", elements.get(h0), elements.get(h1));

        handles.swap(h0, h1);

        println!("{} {}", elements.get(h0), elements.get(h1));
    }
    {
        let (handles, elements) = linked_list.access();

        let h0 = handles.front().unwrap();
        let h1 = handles.back().unwrap();
        let h2 = handles.push_back("And thanks for the fish!".to_string());

        println!("{} {}! {}", elements.get(h0), elements.get(h1), elements.get(h2));
    }
}

安全地 return 对内部节点的多个引用，同时仍然允许其他节点的变异

Safely return multiple references to internal nodes, while still allowing mutation of other nodes

data-structures

rust

mutability

interior-mutability