The magical applications of Zero-Sized Types in Rust

Rust has the concept of zero-sized types, or ZSTs for short. These are types that hold no information as part of their layout. A common misconception, however, is that this makes them trivial. Rather, they offer the necessary properties for a complex interactions between the type system and values. In the following text I will explore how they give rise to mathematical reasoning within Rust, but also show how this provides concrete application. We will work around restrictions in Rust's trait system, or show how libraries can side-step long-term commitments to single dependencies without breaking changes according to Semantic Versioning.

  1. Type basics
  2. Transparent Wrappers
  3. ZSTs are proofs
    1. Limitations of proofs
    2. ZSTs as marker trait replacements
    3. Replacing marker traits in const
    4. Proof instances in interface design
    5. Proof of work
    6. Proof construction
    7. Proofs on relations
  4. Generativity
    1. Generative slice indices
    2. An unfortunate restriction
    3. An escape hatch
    4. Yet more escape hatches
  5. A non-trivial marker type
    1. Types behind references
    2. Proving object-safe trait membership

Type basics

Let us revise some facts around these types first. They can be constructed via any of the usual means. Note that, while the first form is most common, all construction and use obey the typical privacy rules. In particular it is possible for such a type to have one or more private fields which renders them not trivially constructible.

struct Zst;
struct Zst1 ();
struct Zst2 {}
struct AnotherZst (Zst);
struct WoaZst {
  one: Zst1,
  two: Zst2,
}

Note that this also does not imply that any zero-sized type is Copy or that you can create one out of thin air. They are still values and they follow the usual rules. Indeed, this makes it possible to perform some sort of initialization and deinitialization, for example acquire a global lock. It is not the focus of this article, but see below for a section on this kind of usage. For the rest of the article, where not explicitly stated otherwise, all zero-sized types should be read as being annotated with #[derive(Clone, Copy)]. (Or rather, we manually implement these traits without looking at the type parameters as the derive would do). Furthermore, the type might have alignment requirements. This still leaves the construction to introduce and check our type's invariants.

Let's also look at how zero sized types interact with Rust's special reference types, &_ and &mut _. Both of them make aliasing assumptions. That is, memory of a referee of a shared reference must not be changed (apart from referring to UnsafeCell<T>), and the unique reference must be the only pointer through which memory behind it is read and written. However, none of this is concern for zero-sized types. A zero-sized region of memory does not alias with any other region. This means we can move an instance of a zero-sized types to anywhere and get ourselves a unique reference as a result. And if the type is Copy then we can duplicate it arbitrarily to anywhere—except address 0 because references must still never be null, and we must adhere to alignment requirements.

fn leak_zst_at<'a, T>(val: T, at: *const u8) -> Result<&'a mut T, T> {
  assert_eq!(core::mem::size_of::<T>(), 0);
  if at != core::ptr::null() && at.align_offset(core::mem::align_of::<T>()) == 0 {
    let at = at as *mut T;
    unsafe { core::ptr::write(at, val) };
    Some(unsafe { &mut *at })
  } else {
    Err(val)
  }
}

Transparent wrappers

Zero sized types are the basis for one special representation of structs, transparent wrappers. With this attribute we mean a structure that inherits all size, layout and ABI attributes from one of its members. These structs are allowed to have more than one member but only when those extra members are zero-sized types with an alignment requirement of 1 (aka. 1-ZST). Note that the property of being a 1-ZST is implicitly computed for a struct and, technically, it can be observed by downstream crates. Whether you want to treat it as part of your Semantic Versioning guarantees or not is not strictly specified.

Declaring your own wrapper type is simple.

#[repr(transparent)]
pub struct Wrapper<T> {
  field: T,
  zst_field: Zst,
}

struct Zst;

pub fn from_ref<T>(t: &T)
  -> &Wrapper<T>
{
  unsafe { &*(t as *const T as *const Wrapper<T>) }
}

The use of this attribute is to enable sound to conversion between different pointer types and in particular between references. In the above example it is okay to unsafely convert &T to &Wrapper<T> by pointer casting. However, this does not hold in general. Note that, for this to be sound, it must be sound to implicitly create a &Zst as well. More on where this is not okay, where it requires additional steps, and alternatives below.

There are several helper crates that make this safer, however I will only go into bytemuck since it is at 1.0 and likely to be stable for quite some time. Its TransparentWrapper<T> trait, unsurprisingly, allows us to denote the property of wrapping a T via a trait. You must only impl it if for all callers the above conversion is trivial. If it is not, you can use a trick wherein an intermediate type is defined so that neither trait impl is public. This allows your local module to use the safe methods for conversion but it won't expose them to callers. This is perfect for imposing your own invariants and for fallible construction.

use bytemuck::TransparentWrapper;

#[repr(transparent)]
struct Private<T: ?Sized>(T);

#[repr(transparent)]
pub struct Wrapper<T: ?Sized> {
  field: Private<T>,
  zst_field: Zst,
}

unsafe impl<T: ?Sized> TransparentWrapper<T>
  for Private<T> {}
unsafe impl<T: ?Sized> TransparentWrapper<Private<T>>
  for Wrapper<T> {}

impl<T: ?Sized> Wrapper {
  pub fn from_ref(t: &T) -> Option<&Wrapper<T>> {
    // here any checks you want to do..
    if !Self::check_type::<T>() {
      None
    } else {
      Some(Wrapper::from_ref(Private::from_ref(t)))
    }
  }
}

ZSTs are proofs

We've now seen twice already that creating an instance of a zero-sized type from thin air is not, in general, sound. We can liken this to mathematical proofs. A zero-sized type is, in other words, a statement that might be inhabited (read: provable). It is up to the author of a type to define any invariants (read: proposition to be proven) and constructors (read: the script of the proof, depending on the logic system that the author chooses) and up to the caller to actually instantiate this proof to create an instance (read: proof term).

The two most basic proofs are:

struct True;
// aka. Void, Infallible, Never, !
enum False {}

Note how reasoning about their construction is trivial, i.e. True is a tautology that anyone can create, and False has no representation and therefore can not ever hold. Further, observe that a ZST, by definition, can not hold any state. This means that all proof terms of a particular fact are equivalent, though not definitionally because we do not necessarily have a transcript of how they were derived. Indeed, there might be many constructors for a proof that require alternate prerequisites. This more or less parallels extensional propositional equality. For now, observe that we can construct the basic logical combinators:

pub struct And<A, B>(PhantomData<A, B>);

impl<A, B> And<A, B> {
  pub fn new(_: A, _: B) -> Self {
    And(PhantomData)
  }
}

pub struct Or<A, B>(PhantomData<A, B>);

impl<A, B> Or<A, B> {
  pub fn left(_: A) -> Self {
    Or(PhantomData)
  }
  pub fn right(_: B) -> Self {
    Or(PhantomData)
  }
}

Limitations of proofs

There is, sadly, no proof type for Not<A>. This would typically be constructed from some function Fn(A) -> False but since all functions can just panic it would be unsound to use this as a proof to the uninhabitedness of the type A. This is also relevant for the usage of values in generics, or more specifically why the soon-to-be-stabilized min_const_generics does not allow functions to be called. In this context a panic would fail the compilation of a program. But this can not be detected before fully type checking the program as you can only evaluate the function when a concrete value is provided. This fault, where an instantiation of a generic type fails even though its definition was allowed, is referred to as 'post-monomorphization error' and it would make it hard to trust the interface provided by a library. If, in the future, the totality of a function can be expressed we can also introduce a Not type.

It might of course be possible for proofs to not be zero sized and to hold additional state, and in particular to keep record of the construction or even remember values that were provided as parameters. However, without the ability to use these values as type parameters the actual usefulness is severely limited. I would like to explore this further in the future (can we model dependent typing? Intuitionistic Type Theory per Martin-Löf?) but apart from one section we will discuss only ZSTs in this article.

Integration of proofs with the type system

You've already been given an example of how the endeavour gets more interesting if we consider structs with type parameters. Here we depart a moment from a pure mathematical view to see a practical interaction with Rust's type system. Since the standard properties on types are in fact pure, do not panic and give consistent results we can testify to the evaluation of such a method without the need to actually store the result.

// PhantomData<T> is essentially True, but with a type parameter.
use core::marker::PhantomData;

// This refines `True`, it is only constructible when the type has size 2.
struct TypeHasSize2<T>(PhantomData<T>);

impl<T> TypeHasSize2 {
  pub fn check() -> Option<Self> {
    if core::mem::size_of::<T>() == 2 {
      Some(TypeHasSize2(PhantomData))
    } else {
      None
    }
  }
}

We can obviously encode any property that we can check within a const-fn. For example, we might require that the size is a prime, or that the size is a multiple of another type's size, or that the alignment is at most a specific constant. This combines to a pretty powerful tool that moves certain soundness checks to compile time. In the next sections we will go into more detail.

ZSTs as marker trait replacements

A marker trait is a stateless signal that a certain property of a type holds. Note how this closely relates to the stateless nature of a ZST. A type parameter bound, fn foo<T: Bound>, is typically used to require the caller to show that such a property holds for the type. Now, consider that we achieve the same effect via require the caller to demonstrate the proof via construction of a zero-sized type with the invariant that the property holds. This removes the need for a trait bound!

fn some_op_that_requires_copy<T: Copy>() {
  // ..
}

#[derive(Clone, Copy)].
struct IsCopy<T>(PhantomData<T>);

impl<T: Copy> IsCopy {
  // The constructor is gated by T: Copy
  pub fn new() -> Self { IsCopy(PhantomData) }
}

// But the method itself has _no_ bound.
fn some_op_that_requires_copy<T>(_: IsCopy<T>) {
  // ..
}

Replacing marker traits in const

This is useful for the current, minimal, const fn system in Rust. You are not yet allowed to declared generic methods to be const if any of their parameter types has a bound. This includes having any of the marker bounds. It is nevertheless possible to declare the value variant const. Note that for constructor to be available in const, you can use an associated constant instead.

impl<T: Copy> IsCopy {
  pub const PROOF: Self = IsCopy(PhantomData);
}

const fn some_op_that_requires_copy<T>(_: IsCopy<T>) {
  // ..
}

Proof instances in interface design

Still, do not be fooled to think that this is only of temporary usefulness, and that it will be inevitably replaced by more powerful const methods and trait bounds. In many ways the 'proof instance' system is far more flexible. Any type parameter bound becomes part of the SemVer guarantees of a method. In minor version updates, you can at most relax it but you can not strengthen it or change it to a different bound. In particular, you can not swap it for a trait from another crate.

Consider a marker trait that might eventually be added to std, or that has competing implementations. A wide-spread example might be the Pod trait connected to memory transmutation. It stands for Plain-Old data, a concept with heritage in C, and marks types that are safe to be inspect as bytes and to be constructed from bytes. A very useful concept for protocols and serialization where these are effectively zero-cost mechanism for semantically interpreting some byte buffer.

There is no standardized mechanism as of yet, and at least five different crates provide a reasonable close approximation of this trait, with differing degrees of support for the standard library and the ecosystem, and cough differing soundness. In other words, when one creates a library based on the concept of Pods then its interface chooses one of these crates and a major version will ossify the choice for a long time.

Proof instances offer an alternative way. Since the use does not mention any particular bound we can keep the impact of our choice to construction. Furthermore, we can offer different constructors and add to our set over time, based on user demand. What's more, an unsafe constructor might allow the user to choose another implementation of the trait concept for themselves! The last point in particular has no clear equivalent method in traits.

#[derive(Clone, Copy)]
pub struct Pod<T>(PhantomData<T>);

impl Pod<T> {
  pub const unsafe fn new_unchecked() -> Self {
    Pod(PhantomData)
  }

  pub fn with_bytemuck() -> Self
    where Self: bytemuck::Pod,
  {
    Pod(PhantomData)
  }

  pub fn with_zerocopy() -> Self
    where Self: zerocopy::FromBytes + zerocopy::AsBytes,
  {
    Pod(PhantomData)
  }

  pub fn cast_mut<'t>(self, buf: &'t mut [u8]) -> Option<&'t mut T> {
    if buf.as_ptr().align_offset(mem::align_of::<T>()) != 0 {
      None
    } else if buf.len() < mem::size_of::<T>() {
      None
    } else {
      Some(unsafe { &mut *(buf.as_mut_ptr() as *mut T) })
    }
  }
}

pub fn validate<T>(buf: &mut [u8], proof: Pod<T>)
  -> Option<&mut T>
{
  let t = proof.cast_mut(buf)?;
  // ...
  Some(t)
}

Proof of work

In some cases a library wants to depend on an initialization routine having been ran. Consider a static, global Once<T> structure which is used to generate lookup tables that is too large to embed in the binary or to gather static system information (e.g. on the CPU architecture) that is not available at compile time, or any other reason where the const mechanism of Rust is not good enough yet. The first access to these global resources must initialize them, otherwise we read uninitialized data or even race another thread's initialization, which is UB. However, this also implies that there must be a check on every access.

The common method for implementing this check is a synchronous runtime state, for example an atomic variable. Without even going into the intricate details of ensuring that checks and updates of such a shared variable are ordered in such a way to avoid stalls, races, and initializedness, this approach has measurable costs associated with each access. The simple advantage is that it can be encapsulated into the cell type, i.e. Once, and offer a purely safe interface.

However, if we are to initialize a truly global resource we can do better. Indeed, each access implicitly yields, on return, a proof that the initialization has been performed. This is commonly directly consumed to provide a shared reference to the cell's content instead. However, if we keep it as an explicit zero-sized type instead then we can use it again to provide zero-cost access again in the future.

use core::marker::PhantomData;
use once_cell::sync::OnceCell;

pub struct TaggedOnceCell<T, Tag> {
  cell: OnceCell<T>,
  tag: PhantomData<Tag>,
}

/// A marker proving that the unique cell with tag `Tag` is initialized.
#[derive(Clone, Copy)]
pub struct Init<Tag>(PhantomData<Tag>);

impl<T, Tag> TaggedOnceCell<T, Tag> {
  /// Make an uninitialized cell.
  /// This must only be called once for each `Tag` type.
  pub const unsafe fn new() -> Self {
    TaggedOnceCell { cell: OnceCell::new(), tag: PhantomData }
  }

  pub fn get_or_init<F>(&self, f: F) -> Init<Tag>
  where
    F: FnOnce() -> T
  {
    let _ = self.cell.get_or_init(f);
    Init(self.tag)
  }

  pub fn get(&self, _: Init<Tag>) -> &T {
    // SAFETY: Init proves that `get_or_init` has successfully 
    // returned before, initializing the cell.
    unsafe { self.cell.get_unchecked() }
  }
}

In order to make this more ergonomic to use we can provide a macro that defines a unique new type on every use, which satisfies the requirements of the new constructor. With const generics we might also have the option to create this new type utilizing the current source location instead which would avoid any name conflict.

macro_rules! tagged_cell {
  (static $name:ident : TaggedOnceCell<$type:ty, _> = TaggedOnceCell::new();) => {
    mod $name {
      #[allow(dead_code)]
      pub struct NewType;
    }

    static $name : TaggedOnceCell<$type, self::$name::NewType> = unsafe {
      TaggedOnceCell::new()  
    };
  }
}

tagged_cell! {
  static CELL: TaggedOnceCell<u32, _> = TaggedOnceCell::new();
}

Proof construction

Another reason to have a marker ZST instead of a trait is that when you opt-in to a marker trait you are still required to uphold the rules of an impl, in particular that they must not intersect. This rule can prove to be quite difficult to fulfill since you can not perform any negative reasoning, there is no such bound as T: !Trait1 + Trait2. In comparison, this is no issue for marker types that allow proof instances to be constructed from existing proofs. We had already seen one instance of this above, where the Pod marker can be constructed from marker traits of bytemuck and zerocopy even though a type might well implement both of them.

It turns out, we can imagine yet more. Consider the Pod types again, realize that that if T is Pod then so is any array of it. In terms of traits we might want to write:

impl<T, const N: usize> Pod for [T; N] {}

But, a similar line of thought will lead us to the conclusion that any zero-sized type, and in particular empty arrays, is also a Pod. And this would be:

impl<T> Pod for [T; 0] {}

These two trivially overlap. And indeed, a very similar issue has caused some fallout in the standard library where [T; 0] was Default for any type which conflicts with the generalization of [T; N] where T: Default. Luckily, this is within the compiler's infrastructure and can be solved with specialization, a feature that is ordinarily only available on nightly and does permit these with a conflict resolution mechanism. (However, that same feature has been responsible for a few soundness issues).

Compare this with the clean approach for marker ZSTs, where we simply offer two more constructors, one of which requires the proof for the element type while the other does not and can be invoked for any chosen type.

pub fn empty<T>() -> Pod<[T; 0]> {
  Pod(PhantomData)
}

pub fn array<T, const N: usize>(_: Pod<T>) -> Pod<[T; N]> {
  Pod(PhantomData)
}

Proofs on relations

This extra flexibility of extraneous constructors and dynamic checks makes marker types excellent at checking arbitrary relation between two types. Consider as a motivating example the requirements on Vec<T>::from_raw_parts and Box<T>::from_raw, core methods for reusing the allocation of a vector or box for a different type.

T needs to have the same size and alignment as what ptr was allocated with. (T having a less strict alignment is not sufficient, the alignment really needs to be equal to satisfy the dealloc requirement that memory must be allocated and deallocated with the same layout.)

We recognize that this check is constant, depends only on consts, but still we can not express it as a trait bound. This is prime time for marker types.

#[derive(Debug, PartialEq, Eq, Hash)]
pub struct SameLayout<A, B>(PhantomData<(A, B)>);

impl<A, B> SameLayout<A, B> {
  pub const fn new() -> Option<Self> {
    let layout_a = Layout::new::<A>();
    let layout_b = Layout::new::<B>();
    // Direct comparison requires `ops::Eq` which obviously is NOT yet const fn.
    // Also this is exactly what we required for allocators, as documented there.
    if layout_a.size() == layout_b.size() && layout_a.align() == layout_b.align() {
        Some(SameLayout(PhantomData))
    } else {
        None
    }
  }
}

The marker type can be embellished with a number of derivative constructors. We'll best just make a list here as the implementations themselves are trivial and do not require any checks. This list is of course not exhaustive.

  • array(SameLayout<A, B>) -> SameLayout<[A; N], [B; N]>
  • transpose(SameLayout<A, B>) -> SameLayout<B, A>
  • chain(SameLayout<A, B>, SameLayout<B, C>) -> SameLayout<A, C>
  • id() -> SameLayout<A, A>
  • for_ref() -> SameLayout<*const A, &'a A>
  • for_mut() -> SameLayout<*const A, &'a mut A>
  • for_ref_opt() -> SameLayout<*const A, Option<&'a A>>
  • for_mut_opt() -> SameLayout<*const A, Option<&'a mut A>>
  • for_ptr_mut() -> SameLayout<*const A, *mut A>
  • for_box() -> SameLayout<*const A, Box<A>>

This marker type proves one of the core requirements. We can work around all other requirements as necessary. For example, in the case of a vector we can ensure that the produced value is empty which ensures that no elements are required. In the case of Box, which requires its element to be valid, we can wrap it as MaybeUninit instead.

impl<A, B> SameLayout<A, B> {
  /// 'Transmute' a vector by reusing its buffer.
  /// NOTE: For simplicity this will forget all elements. This affords more
  /// flexibility for the caller as they might want to use As as an initializer
  /// for Bs which would be invalid if we dropped them. Manually drain the 
  /// vector if this is not desirable.
  pub fn forget_vec(self, vec: Vec<A>) -> Vec<B> {
    let mut vec = core::mem::ManuallyDrop::new(vec);
    let cap = vec.capacity();
    let ptr = vec.as_mut_ptr();
    // SAFETY:
    // - ptr was previously allocated with Vec.
    // - B has the same alignment and size as per our invariants.
    // - 0 is less than or equal to capacity.
    // - capacity is the capacity the Vec was allocated with.
    // - All elements (there are none) as initialized.
    unsafe { Vec::from_raw_parts(ptr as *mut B, 0, cap) }
  }

  /// 'Transmute' a box by reusing its buffer.
  /// NOTE: for the same flexibility as Vec, forget about the returned `A`.
  pub fn deinit_box(self, boxed: Box<A>) -> (A, Box<MaybeUninit<B>>) {
    let ptr = Box::into_raw(boxed);
    // SAFETY: just was a valid box..
    let a = unsafe { core::ptr::read(ptr) };
    // SAFETY:
    // - ptr was previously allocated with Box.
    // - The ptr is valid for reads and writes as it comes from a Box.
    // - B has the same alignment and size as per our invariants.
    // - Any instance of MaybeUninit is always valid.
    (a, unsafe { Box::from_raw(ptr as *mut MaybeUninit<B>) })
  }
}

This trait has been published as part of the same-alloc crate, which also offers a buffer reuse mechanism based on the trait. Due to the SemVer advantages laid out earlier, it can be moved to a separate crate (or the standard library) as desirable. We only need a simple converter that allows construction from such an external marker type.

Generativity

A very special use for a marker type is when we want to assert a property for a value. However, the only mechanism available to perform such an assertion at compile time is the type checker. This paradox can be solved by observing that there exist a way to have the compiler virtually generate a new, unique type out of thin air by using lifetimes.

/// A marker type for a lifetime.
/// This type need not be Copy or Clone.
struct Generative<'lt>(PhantomData<*const &'lt ()>);

fn generative(cb: impl FnOnce(Generative)) {
  cb(Generative::<'static>(PhantomData))
}

Wait, but 'static isn't unique? No, the idea is that the lifetime is opaque within the callback. If we desugar the type then then the actual parameter has the expanded form _F: for<'a> FnOnce(Generative<'a>). That is, the function must be prepared to handle an argument with any possible lifetime. To avoid the ability to assume any relation to an existing lifetime, internally it can only be treated as a completely new one that is 'generated' for this method.

The only way to name such a lifetime is by calling a method with a generic lifetime parameter, and a corresponding function parameter that contains a Generative, and then pass the value itself to have the generic parameter deduced. In other words, the lifetime acts as a tag uniquely identifying a single call to the generative function.

We can use this unique lifetime to link different functions parameters with each other. This means that other code can rely on multiple, independent values originating from the same callback call by virtue of them having the same lifetime parameter, i.e. containing an instance of the same Generative type. We can even compute values based on an argument and then supply the callback with the result, tagged with the same generative lifetime, such that we can later trust this result value to be have correctly computed and unmodified for that specific argument.

(edited )

This concept has also been explored in literature, in Aria Beingeisser's Master Thesis or the GhostCell paper for a push-only vector with accompanying formalized correctness proofs.

Generative slice indices

To exemplify, we can compute the length of a slice and, without requiring this slice by value, safely encapsulate valid indices into it, then later use those indices while having absolute certainty that those indices are valid for the slice. In other words, we can use the indices for unchecked access. This is very valuable for code that computes indices in a different module than its use.

pub struct Length<'tag>(Gen<'tag>, usize);
pub struct Slice<'tag, 'data, T>(Generative<'tag>, &'data [T]);
pub struct Idx<'tag>(Gen<'tag>, usize);


pub fn with_ref<'slice, T>(
  slice: &'slice [T],
  cb: impl for<'tag> FnOnce(Length<'tag>, Slice<'tag, 'slice, T>),
) {
    generative(|tag| {
        let len = slice.len();
        cb(Length(tag, len), Slice(tag, slice))
    })
}

impl<'a> Length<'a> {
  pub fn idx(&self, idx: usize) -> Option<Idx<'a>> {
    if idx < self.1 {
      Some(Idx(self.0, idx))
    } else {
      None
    }
  }
}

impl<'tag, T> core::ops::Index<Idx<'tag>> for Slice<'tag, '_, T> {
  type Output = T;
  fn index(&self, idx: Idx<'tag>) -> &T {
    unsafe { self.1.get_unchecked(idx.1) }
  }
}

This construct can be useful for constructing indices in one part of the code, and using them in a different module where the compiler wouldn't usually be able to track the value relationship between index and length. For example, this sometimes isn't the case when you've stored the indices into memory that is reallocated such as appending them to a vector, then later pass this as a slice and want to use indices from the slice.

// Usage:
with_ref(slice, |length, slice| {
  let idx = length.idx(1).unwrap();
  // Look ma, no bounds check here.
  let _ = &slice[idx];
})

Don't be fooled thinking that this merely moves the bounds check to construction. In the face of an optimizing compiler such as LLVM this can fundamentally alter the effort required for a fast program. For example, the construction of an index compares it against the length, a purely arithmetic relation that LLVM is great at checking. However, by the time it is used this relation might no longer be obvious as the optimizer needs certainty that the length nor the index value has changed. In a sense, we move this value tracking from the compiler backend into the Rust type checker which gives us a much more reliable outcome. Furthermore, this approach can guarantee the absence of panics which is interesting for a variety of applications such as hard real time systems, safety requirements, etc.

I hadn't found a comprehensive crate that focusses on this use case in particular and so I've written index-ext which greatly expands on the above sketch to provide a number of index modification methods (e.g. min, checked_sub) and more index types (e.g. RangeTo, Range) as well as dynamic checks for mixing different slice tags with the exact same length associated to their tags. If you want to do formal proofs for those, or add parts of it to std please contact me.

An unfortunate restriction

The Rust type checker however is too strict with this approach. Any lifetime parameter restricts the assumed lifetime of the whole struct. This does NOT work even though of course the lifetime of a function is completely independent of the lifetime of its parameters.

struct Invariant<'lt> {
    _tagged: PhantomData<fn(&'lt ())>,
}

fn check<'a>(_: &'a ())
    where Invariant<'a>: 'static,
{}

fn main() {
    let a = ();
    // error[E0597]: `a` does not live long enough
    check(&a);
}

This property will infect all other structs that contain such a field.

An escape hatch

An alternate tag design is not to rely on lifetimes. We must ensure that each tag belongs to some unique value, modelling a constraint on it. And each value of our tag type belongs to the same value and constraint instance. In the simplest case the constraint does not dynamically depend on the value.

However, if the requirement for long slices is static, say at least 256 such that all u8 indices are safe, then we have an alternate approach. We can use a trait with an associated constant to enforce that all values of a tag type refer to the same constraint. Then subsequently we can check the slices against this reference before tagging them.

/// A user-defined length constant.
trait ContantSource {
  const LEN: usize;
}

/// A tag referring to a particular length, without storing it.
struct Constant<C>(PhantomData<fn(C) -> C>);

struct Slice<C, T>(Constant<C>, [T]);
struct Idx<C>(Constant<C>, usize);

impl<C: ConstantSource> Constant<T> {
  pub fn with_ref<'a, T>(slice: &'a [T]) -> Option<&'a Slice<C, T>> {
    if slice.len() >= C::LEN {
      Some(unsafe { &*(slice as *const Slice<C, T>) })
    } else {
      None
    }
  }

  pub fn idx(idx: usize) -> Option<Idx<C>> {
    if idx < C::LEN {
      Some(Idx(Constant(PhantomData), idx))
    } else {
      None
    }
  }
}

This kind of tagging scheme was also implemented in the index-ext crate.

Yet more escape hatches

For the motivating example, of proving a fact for a single static, we might also touch on another mechanism that ensures that each type is associated with a single value: a global atomic. The difficulty in this approach is that the caller can define their own atomic, based on the type of the label. This can get awkward quickly if we try to provide it as a library. Luckily, we anticipate that such code is only ever used in setup and thus none of the code is performance critical. Remember that any future attempt should copy the Tag instead.

extern crate once_cell; // 1.7.2
use once_cell::sync::OnceCell;

pub struct Tag<T>(PhantomData<T>);

pub struct Tagged<T, V>(Tag<T>, V);

impl<T: 'static> Tag<T> {
    fn try_get_token() -> bool {
        static TOKENS: OnceCell<Mutex<HashMap<TypeId, AtomicBool>>> =
            OnceCell::new();
        let map = TOKENS.get_or_init(|| Mutex::new(HashMap::new()));
        
        let mut lock = map.lock().unwrap();
        let entry = lock.entry(TypeId::of::<T>())
            .or_insert(AtomicBool::new(false));
        !entry.fetch_or(true, Ordering::Relaxed)
    }
    
    /// Tag a value with type T.
    /// Might fail if another value has already been tagged.
    pub fn take<V>(val: V) -> Option<(Self, Tagged<T, V>)> {
        if !Self::try_get_token() {
            return None;
        }
        
        let tag = Tag(PhantomData);
        Some((tag, Tagged(Tag(PhantomData), val)))
    }
}

An alternative would be to provide only an unsafe construct for Tag, which requires the caller to only use private types and only for one value. This is slightly less safe but also far less involved (and works in base-bones, no_std in particular). A macro-based solution might also ensure that the usage itself is safe and perform this single unsafe call internally. Indeed, we might even attempt to hide the private type within it.

A non-trivial marker type

In this last chapter let us consider what happens if we relax our initial assumptions about the marker types. In the introduction we had seen that the Clone, Copy derive is still a very useful subset but it is by no means required. This is not required however and there are many applications where it is a requirement that the caller must go through a fallible, dynamic check to duplicate instances.

It is possible to represent the acquisition of a resource with a zero-sized type, if it is either global or implicit. An example for this kind of usage is Python's global interpret lock. This lock synchronizes access to Python's internal runtime state in the face of parallel execution (threads) within the same process and you're required to hold it while calling most operations.

This binary, shared resource can be modelled perfectly with a marker type. This is very similar to the previously discussed marker for initialization of a OnceCell, however now our type must not be duplicated. The constructor will try to grab hold of the lock, and its Drop impl will again release it. Since the lock itself is global we do not need to store any guard object itself, contrary to Rust's standard Mutex. If you intend to build a similar runtime yourself, the parking_lot/lock_api crates might be useful in its stead.

static GIL: Mutex<Runtime> = …;

struct GilGuard { _private: () }

impl GilGuard {
  pub fn new() -> Self {
    core::mem::forget(GIL.lock());
    GilGuard { _private: () }
  }
  pub fn as_mut(&mut self) -> &mut Runtime {
    // 'Restore' the guard and pointer
    let ptr = GIL.data_ptr();
    unsafe { &mut *ptr }
  }
}
impl Drop for GilGuard {
  fn drop(&mut self) {
    unsafe { GIL.force_unlock() }
  }
}

Types behind references

What's slight odd, to the brink of being non-secure, about the previous interface is that we can control the guard arbitrarily. That is, we can forget it, or move it off the stack and arbitrarily prolong its lifetime and delay its destruction. While this isn't unsound per-se, at least if the interface is designed correctly around the safety of leaking, the loss of control associated with it can be an inconvenience.

This can be avoided by designing the system such that no instance is exposed to the user. Luckily, zero-sized types are perfect for this job. As we had previously seen, we can pretend to have them allocated at any suitably aligned location. This includes the ability to create Box without actually dealing with any allocator. For advance uses, this also in turn allows us to construct a pinned instance for basically free as well by using Pin<Box<Zst>>.

If no resource needs to be released, the same technique can be used to safely create any kind of reference with any desired lifetime by leaking such a box. Contrary to normal use of Box::leak, this won't actually leak any memory and is just for the sake of the borrow checker! This allows an interface to provide more precise control, i.e. restrictions, to scope the usage of the ZST.

Such a token might be wrapped in another struct, or indeed in another zero-sized type that only declares a PhantomData or holding this reference, for the sake clarity and also Send, Sync correctness. This is the basic concept behind pyo3's global interpreter lock representation. It should be noted that this approach works together with the usual coercion rules. This can be utilized when desired or it must be explicitly disabled by also having an invariant lifetime field.

Proving object-safe trait membership

In a previous section we had seen the advantages of representing trait bounds without statically requiring those bounds. Here we will see one more, exemplified with the standard io traits. Suppose that you're writing a encoder of some sort for a compressed format. (This choice is not removed from reality. A similar issue arose in image and it has been worked around by other means). You being by wrapping an output stream, which implements std::io::Write, and you write the first version and you happily publish it.

However, soon enough, someone brings to your attention that some cases only work (or at least could be much more efficient) if the output stream is seekable! Oh no, what do you do? You don't want to ask all users to provide a seekable stream, after all there already quite a few users who might pipe your output through networks. So you can not add a trait bound for std::io::Seek. Having read all of this article, you wonder: Can proof instances help?

Keep in mind that this section is much more experimental (you'll see by the usage of unstable features). I've not actually published a crate on this yet, I'd value any soundness review. But the proposition is: Of course they can. Only, in this case need them to hold data that allows us to reconstruct the trait membership instance. Observe that an instantiation of an object-safe trait can be modelled by a dyn Trait. This makes it apparent how to construct our type:

#![feature(set_ptr_value)]
use core::marker::PhantomData;

struct IsSeek<T>(PhantomData<T>, *mut dyn std::io::Seek);

impl<T> IsSeek<T> {
    pub fn new<'a>() -> Self
        where T: std::io::Seek + 'a,
    {
        let short = core::ptr::null_mut::<T>()
            as *mut (dyn std::io::Seek + 'a);
        IsSeek(
            PhantomData,
            // Cast away the lifetime. Keep the fat pointer vtable.
            unsafe { core::mem::transmute(short) },
        )
    }
    
    pub fn redeem_mut<'t>(&self, t: &'t mut T)
        -> &'t mut (dyn std::io::Seek + 't)
    {
        unsafe { &mut *(self.1.set_ptr_value(t as *mut T as *mut u8)) }
    }
}

Now we can construct a wrapper type for an output stream that is optionally seekable, with constructors such that the caller can choose whether they have proof of this requirement or not. Keep in mind we only get a dynamic trait object, not a concrete impl, but the overhead of a single indirection can be easily trumped by any algorithmic win.

struct Stream<'a, T> {
  inner: &'a mut T,
  seek: Option<IsSeek<T>>,
}

impl<'a, T> Stream<'a, T> {
  /// Construct an unseekable stream.
  pub fn new(inner: &'a mut T) -> Self {
    Stream { inner, seek: None }
  }

  /// Construct a seekable stream.
  pub fn seekable(inner: &'a mut T) -> Self
    where T: std::io::Seek,
  {
    Stream { inner, seek: Some(IsSeek::new::<'a>()) }
  }

  pub fn as_seek(&mut self) -> Option<&mut dyn std::io::Seek> {
    match &self.seek {
      Some(seek) => Some(seek.redeem_mut(&mut self.inner)),
      None => None,
    }
  }
}

Consistent with the other proof types, we can also separate the construction of IsSeek. For example, if we had previously wrapped a stream we can simply add a field IsSeek<T> together with a setter instead. This preserves our existing interface perfectly which still allowing for the seek optimization internally.

Conclusion

My first conclusion is that this article has gotten far longer than I had originally planned, and still it is missing some details. It has presented an overview of different techniques with zero sized types, as an alternative to marker traits, as an implementation of proof logic, and as a resource guard.

This shows how the orthogonality of Rust's features allows us to compose even the type checker's power in a non-obvious manner. We've seen that types can be highly useful even when they hold no runtime state of their own. This greatly benefits a variety of ideas for enforcing a program's requirements at compile time, far beyond the built-in possibilities of the language and the standard library. We've also seen how we might make interface built on those concepts interoperable such that it might be widely use even without a single, normative implementation in core.

Published on
Last updated