I have tried to write a tree type that allocates nodes from a bump arena, and frees them all when it is dropped.
This is just for learning purposes btw, not for anything practical, so I'm not looking for general design/coding advice -- I'm specifically asking about whether the code is sound.
#![feature(maybe_uninit_uninit_array)]
use rand::random;
use std::cell::RefCell;
use std::mem::MaybeUninit;
pub struct Node<'a> {
pub left: Option<&'a RefCell<Node<'a>>>,
pub right: Option<&'a RefCell<Node<'a>>>,
}
pub struct Tree<'a> {
pub root: Option<&'a RefCell<Node<'a>>>,
arena: [MaybeUninit<RefCell<Node<'a>>>; 11_000],
idx: usize,
}
impl<'a> Tree<'a> {
pub fn alloc(&mut self) -> &'a RefCell<Node<'a>> {
self.arena[self.idx] = MaybeUninit::new(RefCell::new(Node {
left: None,
right: None,
}));
let p = self.arena[self.idx].as_ptr();
self.idx += 1;
unsafe { &*p }
}
pub fn new() -> Self {
Self {
root: None,
arena: MaybeUninit::uninit_array(),
idx: 0,
}
}
}
fn main() {
let mut t = Tree::new();
t.root = Some(t.alloc());
let mut cur = t.root.unwrap().borrow_mut();
for _ in 0..10 {
let left = random();
let next = if left { &mut cur.left } else { &mut cur.right };
*next = Some(t.alloc());
cur = next.unwrap().borrow_mut();
}
std::mem::drop(cur);
let mut cur = t.root.unwrap().borrow();
loop {
if let Some(left) = cur.left {
println!("Left");
cur = left.borrow();
} else if let Some(right) = cur.right {
println!("Right");
cur = right.borrow();
} else {
break;
}
}
}
I can't tell what I'm doing wrong, but running this with Miri gives the following error:
error: Miri evaluation error: no item granting write access to tag <39151> found in borrow stack.
--> src/main.rs:40:9
|
41 | *next = Some(t.alloc());
| ^^^^^^^^^^^^^^^^^^^^^^^ no item granting write access to tag <39151> found in borrow stack.
|
= note: inside call to `main` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:67:34
= note: inside call to closure at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:73
= note: inside call to closure at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/sys_common/backtrace.rs:129:5
= note: inside call to `std::sys_common::backtrace::__rust_begin_short_backtrace::<[closure@DefId(1:6020 ~ std[5aa8]::rt[0]::lang_start_internal[0]::{{closure}}[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:13
= note: inside call to closure at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:303:40
= note: inside call to `std::panicking::r#try::do_call::<[closure@DefId(1:6019 ~ std[5aa8]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:281:13
= note: inside call to `std::panicking::r#try::<i32, [closure@DefId(1:6019 ~ std[5aa8]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe]>` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panic.rs:394:14
= note: inside call to `std::panic::catch_unwind::<[closure@DefId(1:6019 ~ std[5aa8]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:51:25
= note: inside call to `std::rt::lang_start_internal` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:67:5
= note: inside call to `std::rt::lang_start::<()>`