Created
March 1, 2024 08:46
-
-
Save oconnor663/a8d795b0055d04e055bdfe348ee0ff20 to your computer and use it in GitHub Desktop.
Too Many Linked Lists, Miri failure
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::ptr; | |
pub struct List<T> { | |
head: Link<T>, | |
tail: *mut Node<T>, // DANGER DANGER | |
} | |
type Link<T> = Option<Box<Node<T>>>; | |
struct Node<T> { | |
elem: T, | |
next: Link<T>, | |
} | |
impl<T> List<T> { | |
pub fn new() -> Self { | |
List { | |
head: None, | |
tail: ptr::null_mut(), | |
} | |
} | |
pub fn push(&mut self, elem: T) { | |
let mut new_tail = Box::new(Node { elem, next: None }); | |
let raw_tail: *mut _ = &mut *new_tail; | |
if !self.tail.is_null() { | |
// Hello Compiler, I Know I Am Doing Something Dangerous And | |
// I Promise To Be A Good Programmer Who Never Makes Mistakes. | |
unsafe { | |
(*self.tail).next = Some(new_tail); | |
} | |
} else { | |
self.head = Some(new_tail); | |
} | |
self.tail = raw_tail; | |
} | |
pub fn pop(&mut self) -> Option<T> { | |
self.head.take().map(|head| { | |
let head = *head; | |
self.head = head.next; | |
if self.head.is_none() { | |
self.tail = ptr::null_mut(); | |
} | |
head.elem | |
}) | |
} | |
} | |
#[cfg(test)] | |
mod test { | |
use super::List; | |
#[test] | |
fn basics() { | |
let mut list = List::new(); | |
// Check empty list behaves right | |
assert_eq!(list.pop(), None); | |
// Populate list | |
list.push(1); | |
list.push(2); | |
list.push(3); | |
// Check normal removal | |
assert_eq!(list.pop(), Some(1)); | |
assert_eq!(list.pop(), Some(2)); | |
// Push some more just to make sure nothing's corrupted | |
list.push(4); | |
list.push(5); | |
// Check normal removal | |
assert_eq!(list.pop(), Some(3)); | |
assert_eq!(list.pop(), Some(4)); | |
// Check exhaustion | |
assert_eq!(list.pop(), Some(5)); | |
assert_eq!(list.pop(), None); | |
// Check the exhaustion case fixed the pointer right | |
list.push(6); | |
list.push(7); | |
// Check normal removal | |
assert_eq!(list.pop(), Some(6)); | |
assert_eq!(list.pop(), Some(7)); | |
assert_eq!(list.pop(), None); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment