Suppose, for example, I have a linked list which does not allow removal of nodes.
Would it be possible to return shared references to values which have already been inserted, while still allowing the relative order of the nodes to be changed, or new nodes inserted?
Even mutation through one of the nodes should be safe "on paper" as long as only one node is used to mutate the list at a time. Is it possible to represent this in rust's ownership system?
I'm specifically interested in doing so without runtime overhead (potentially using unsafe in the implementation, but not in the interface).
EDIT: As requested, here is an example that gives the outline of what I am thinking of.
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);
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.
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.
The idea to deal with such spatial partitioning is to introduce a different "key" for each partition; it's easy since they are static. This has been dubbed the PassKey pattern.
In the absence of brands, it will still require a run-time check: verifying that the elements-key is tied to this specific list instance is mandatory for safety. This is, however, a read-only comparison that will always be true, so the performance is about as good as it gets as far as run-time checks go.
The idea, in a nutshell:
let (handles, elements) = list.keys();
let h0 = handles.create(4);
handles.swap(h0, h1);
let e = elements.get(h0);
In your usecase:
elements.The full implementation can be found here. It heavily uses unsafe, and I make no promise that it is fully safe, however it is hopefully sufficient for a demonstration.
In this implementation, I have opted for dumb handles and implemented the operations on the key types themselves. This limited the number of types who needed to borrow from the main list, and simplified borrowing.
The core idea, then:
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> will act as the storage, however will implement only 3 operations:
The two keys Handles and Elements will both borrow the list mutably, guaranteeing that a single of (each of them) can exist simultaneously. Borrow-checking will prevent a new Handles or Elements from being created if any instance of them still lives for this list:
list: grants access to the list storage; Elements will only use it for checking (necessary) run-time invariants and never dereference it._marker: is the key to the borrow-checking actually guaranteeing exclusitivity.Sounds cool so far? For completion, the last two structures then:
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 is the most obvious representation of a doubly-linked list ever, so we're doing something right. The list in Handle<T> is there for the exact same purpose as the one in Elements: verifying that both Handle and Handles/Elements are talking about the same instance of list. It's critical for get_mut to be safe, and otherwise helps avoiding bugs.
There's a subtle reason for Handle<'a, T> having a lifetime tying to the LinkedList. I was tempted to remove it, however this would allow creating a handle from a list, destroying the list, then recreating a list at the same address... and handle.node would now be dangling!
And with, we only need to implement the methods we need on Handles and Elements. A few samples:
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
})
}
}
And:
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
}
}
And this should be safe because:
Handles, after creating a new handle, only ever accesses its links.Elements only ever returns references to data, and the links cannot be modified while it accesses them.Example of usage:
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));
}
}