Shared empty vector - is this safe?

code review
1

I am writing a generic radix tree. Nodes without children are very frequent in my implementation. So I would like to prevent allocating lots of nodes with empty children.

I came up with this. A generic empty Arc<Vec<T>> that can be used whenever you want one and don't want to allocate.

Is this safe? It seems to me that an empty Vec<T> should have the same in memory repesentation no matter what T is. But I am not sure.

lazy_static! {
    static ref EMPTY_ARC_VEC: Arc<Vec<u8>> = Arc::new(Vec::new());
}

fn empty_arc<T>() -> Arc<Vec<T>> {
    unsafe { std::mem::transmute(EMPTY_ARC_VEC.clone()) }
}

fn wrap_in_arc<T>(data: Vec<T>) -> Arc<Vec<T>> {
    if data.is_empty() {
        empty_arc()
    } else {
        Arc::new(data)
    }
}
2

This is technically unsound because of alignment requirements. Miri will complain, for example, for this usage (playground):

fn main() {
    let v: Arc<Vec<u32>> = wrap_in_arc(vec![]);
    let _: &[u32] = &**v;
}
4 Likes
3

Thanks.

So how do I run miri to detect this? And is there a way to salvage the approach?

4

In playground it is available under Tools. Locally - via cargo miri.

5

transmuteing Vec (or doing essentially that via pointer casting) is UB because it's repr(Rust), and thus offers no layout guarantees. The compiler is allowed to pick a different ordering for the fields even if just between Vec<i32> and Vec<u32>.

Most standard library types are like this -- not promising their layouts -- and the exceptions discuss it in their documentation.

7 Likes
7

BTreeMap was struggling with a similar problem, the bug was here: BTreeSet causes UB by having (partially) dangling shared reference · Issue #54957 · rust-lang/rust · GitHub When looking at the solution of that, it's also important to look at what happened after that, since it was probably improved (and maybe even revisisted with new eyes for soundness?)

1 Like
8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.