I've tried to modify the code from rust-unofficial. Its an implementation of a queue. So far, I replaced direct pointer(*mut T) to directly using a mutable reference NotNull<T>. But, NotNull::mut() is an unsafe function and I have to still use the unsafe block. Is there any smart pointer other than NotNull that can make it safe?
use std::ptr::NonNull;
type Link<T> = Option<Box<Node<T>>>;
struct List<T> {
head: Link<T>, tail: Option<NonNull<Node<T>>>,
}
struct Node<T> {
elem: T, next: Link<T>,
}
impl<T> List<T> {
pub fn new() -> Self {
Self {
head: None, tail: None,
}
}
pub fn push(&mut self, elem: T) {
let mut new_node = Box::new(Node {elem, next: None });
let new_tail = Some(NonNull::from(new_node.as_mut()));
//if tail is empty, head is also empty and whole list is empty
if let Some(mut node) = self.tail.take() {
unsafe { node.as_mut().next = Some(new_node); }
} else {
self.head = Some(new_node);
}
self.tail = new_tail;
}
pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|node| {
//i.e. if this node is removed the list will be empty
if node.next.is_none() {
self.tail = None;
} else {
self.head = node.next;
}
node.elem
})
}
}
fn main() {
let mut list = List::new();
assert_eq!(list.pop(), None);
list.push(1);
list.push(2);
list.push(3);
assert_eq!(list.pop().unwrap(), 1);
assert_eq!(list.pop().unwrap(), 2);
assert_eq!(list.pop().unwrap(), 3);
assert_eq!(list.pop(), None);
println!("ended");
}
Warning, this code actually is unsound! You can run unsafe code with the miri interpreter, which can catch not every but many soundness bugs via runtime check. It's available as a cargo command and the playground under the TOOLS tab.
Why this code is unsound? Because the Box<T> requires the unaliased ownership of its content. A pointer to the active Box<T>'s content cannot be aliased, but it is via the tail pointer. Oops!
As always, there's two kind of options to handle the aliasing issue - checked and unchecked. Unchecked option is simple. Just use raw pointers everywhere! The Rust doesn't enforce any aliasing rule to the raw pointer so you can freely alias it. Keep it in mind this is the C-way or for long the trust-me-I-know-everything-I-wrote-and-its-bug-free way. If you made a mistake, BOOM. Sometimes you need to write code in this way like it's so hot code which runs billion times per second and the checked version cannot satisfy the perf budget, but it's pretty uncommon.
More recommended option is to use the checked aliased ownership - Rc<T> or Arc<T>. If you want some hint, this is the version with #![forbid(unsafe_code)].
Thanks a lot for the help. I appreciate that you gave an actual solution with safe rust.
These low level stuff is very new for me. I don't know that much about UB. I was confident since the test cases passed. I'm beginning to feel the complexity now. I have a lot to learn
Undefined Behaviour is just a fancy term for when you violate assumptions that the compiler builds on. The compiler can then generate machine code which leverages these assumptions to improve performance, or these assumptions may be required for correctness.
As an example say I've got an &mut u32 and will be using it to count things. If the compiler knows nobody else can read this value while I'm counting then it can stash the value in a register and do the operations there instead of dereferencing a pointer every time. Register operations are orders of magnitude faster than reading from memory, so this can be a massive performance win.
Now say I've violated that assumption (e.g. by using unsafe and raw pointers) and there is some other code which accesses my counter at the same time. That code may never see my counter get updated because it's looking at the value behind the &mut u32 when the value being updated is in a register on another processor. This might be exposed to the user as the counter sometimes having a different value than you expect, causing logic errors in your program.
Unfortunately things can get worse when other unsafe code is involved. For example, imagine instead of pointing to a u32 we actually had a mutable reference to a pointer. Now reading a different value for our "counter" means you could accidentally access garbage memory and then no-one can predict what will happen.
These sorts of situations are why people make a big deal about Undefined Behaviour, and why it takes a bit more discipline to write unsafe code... That said, while the stakes may be a bit higher writing unsafe code can also be quite satisfying because it gives you a greater understanding of what the CPU is actually doing when you write code. Just make sure you aren't reaching for unsafe as a crutch to work around compile errors.