I am trying to understand the problem with duplicated code for & and &mut in accessor-type functions. I'm trying to understand whether a particular solution to this problem is sound[1].
The following is an example of the problem. It is taken from the really nice tutorial Learning Rust With Entirely Too Many Linked Lists.
type Link<T> = Option<Box<Node<T>>>;
pub struct List<T> {
head: Link<T>,
}
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
// Other methods left out...
// The implementation of peek is simple, but still long enough
// that you'd like to avoid duplicating it if that is possible.
// Some other accessor-type functions could be much more complex
// so that you'd want to avoid duplication even more.
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|node| {
&node.elem
})
}
// Exact duplicate of `peek`, except for the types
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|node| {
&mut node.elem
})
}
}
The solution
It seems to me like it is possible to implement peek_mut using the return value peek, casting it to *mut and then to a Option<&mut T>. It seems like the implementation is sound and provides a safe interface for an unsafe implementation.
The following is the implementation:
// Implemention of peek_mut by casting return value of `peek()`
pub fn peek_mut(&mut self) -> Option<&mut T> {
let head_raw_mut : *mut T = self.peek().map_or_else(std::ptr::null, |r| r) as *mut T; // (1)
unsafe { head_raw_mut.as_mut() } // (2)
}
This is my reasoning for why I think it is sound:
- No unsafe code is used in
(1), since it is safe to create raw pointers. - At
(2),head_raw_mutis the single pointer to the head element. - The lifetime of the head element is same as self, which is same the as the return value.
-
head_raw_mutgoes out of scope before the new mut ref can be used, so there are never two mutable refs simultanously in use.
Hence the use of the unsafe function pointer::as_mut is sound.
Misc notes
-
The Nomicon strongly asserts that transmuting
&to&mutalways have undefined behaviour, which might by applicable also to this code. But I think Nomicon is talking about code which simultaneously keeps and uses shared and multable references. This code doesn't do that. -
The Rust Reference states that "Breaking the pointer aliasing rules" is UB. To me it seems like this code doesn't do that, for reasons given above.
-
I have posted a similar question about another (but worse) solution attempt on Stack Overflow.
-
There are other kinds of solutions to the problem, such as Abstracting over mutability in Rust. But all other solutions seem to introduce quite a bit of extra complexity to the code.
Super detailed version of the code
The following is the code of the peek_mut, but expanded with separate local variables for the different sub-expressions. In this way it seems even more clear to me that the code doesn't use any unsound combinations of pointers or references.
pub fn peek_mut_exp(&mut self) -> Option<&mut T> {
let head_opt_ref_mut : Option<&mut T>;
{
let head_raw_mut : *mut T;
{
let head_raw_const : *const T;
{
let head_opt_ref : Option<&T> = self.peek();
// Step 1, scope: 1 ref
head_raw_const = head_opt_ref.map_or_else(std::ptr::null, |r| r);
// Step 2, scope: 1 ref, 1 raw const ptr
}
// Step 3, scope: 1 raw const ptr
head_raw_mut = head_raw_const as *mut T;
// Step 4, scope: 1 raw const ptr, 1 raw mut ptr
}
// Step 5, scope: 1 raw mut ptr
head_opt_ref_mut = unsafe { head_raw_mut.as_mut() };
// Step 6, scope: 1 raw mut ptr, 1 mut ref
}
// Step 7, scope: 1 mut ref
head_opt_ref_mut
}
Questions
I have the following questions for people with deeper Rust knowledge than myself:
- Is the provided implementation of
peek_mutsound? - If it is indeed not sound, why is that? Can you give a detailed explanation?
- Is there in that case a variation of the solution that is sound?
[1]: That is, that the code works as intended and doesn't have undefined behaviour, the definition given by Unsafe Code Guidelines.