How to safely store immutable, aliasing copies of a generic value?

Question

Summary

For optimization purposes I wish to create a data structure that stores single values in multiple, distinct places. The data structure will only ever let these values be used through immutable reference, or by removing them from the data structure entirely.

How can I ensure that this is safe for a generic type?

Simplified example

To give a trivial (but somewhat unrealistic) example for context, consider a slice that caches the most recently used value:

struct Pair<'a> {
    values: &'a [T],
    last_accessed: &'a T,
}

Accessing the last accessed element, however, still incurs a pointer dereference, so the code would like a by-value cache:

struct Pair<'a> {
    values: &'a [T],
    last_accessed: NoDrop<T>,
}

In most cases this seems to be safe. For example, if T is a u32, the cache is just a simple copy of the data.

Even if T is a Vec<U>, this seems to be safe as any access through &last_accessed cannot change any of the direct members of the vector. The heap allocation is transitively immutable and not duplicated, so there is no obvious aliasing problem.

Why is this hard?

This is not safe for all values. A value containing a Cell could invoke interior mutability and end up violating internal constraints that causes unsafe behavior when accessed through a value that hasn't propagated that change.

The question is what constraints can I put on a generic T that would make this safe? As far as I know, all I need is that it contains no UnsafeCell except through a pointer.

What about T: Copy?

T: Copy looks like a decent solution, but there are two major drawbacks:

• "there's no absolutely fundamental reason why [UnsafeCell] does not implement Copy" - Alex Crichton. The Copy requirement seems coincidental rather than guaranteed.

• Copy bans far too much; Vec is not Copy but does not need to be banned.

What about T: Sync

Sync is close to the right idea, since

Types that are not Sync are those that have "interior mutability" in a non-thread-safe way, such as Cell and RefCell in std::cell.

However, several types, like atomics, have interior mutability that is thread-safe.

Answer 1

You can enforce the constraint against UnsafeCell with an auto trait. These are defined by default, but can be opted out of with a special syntax for specific types - you want to opt out just for UnsafeCell.

These were previously called Opt-In Built-In Traits (OIBITs), but were renamed since they are neither opt-in nor necessarily built-in, and are in fact opt-out traits that can be defined in ordinary user code.

First you enable it, create the trait and make it implemented by default. This uses some magic syntax.

#![feature(optin_builtin_traits)]

pub unsafe trait CopyRef {}
unsafe impl CopyRef for .. {}

Then you opt-out for UnsafeCell.

// Opt out of interior mutability
impl<T: ?Sized> !CopyRef for UnsafeCell<T> {}

You will then want to re-enable UnsafeCell behind pointers and PhantomData.

use std::marker::PhantomData;
use std::cell::UnsafeCell;

// Opt in for indirect interior mutability
unsafe impl<'a, T: ?Sized> CopyRef for *const T {}
unsafe impl<'a, T: ?Sized> CopyRef for *mut T {}
unsafe impl<'a, T: ?Sized> CopyRef for &'a T {}
unsafe impl<'a, T: ?Sized> CopyRef for &'a mut T {}

// Box is special and needs its own opt-in
unsafe impl<T: ?Sized> CopyRef for Box<T> {}

// And fake interior mutability
unsafe impl<T: ?Sized> CopyRef for PhantomData<T> {}

Voilà. Your very own user-defined opt-out Opt-In Built-In auto Trait.