ZSTs in Rust

Back when I was learning Rust, I found the notion of ZSTs - that is, zero-sized types with no data associated with them, to be interesting. I made a start on this blogpost, but never finished it. Finally, here it is.

To note, none of this is revolutionary or new - I wrote this to better learn the topic myself, all of this is borrowed from other sources (all found below!). Still, hopefully this acts to collate most of the interesting things you can do with ZSTs, and just maybe my wording can give a new perspective.

The ZST you’ve seen before - ()

The empty tuple - the biggest use case (to me, at least) where it’s explicit is if you want a function that can return an error, but doesnt need to return any data on success, which’d look like: Result<(), Err>

() is of course actually much more frequent, because any functions that dont return anything actually return () implicitly.

There’s not too much to talk about for (). But there are several more ZSTs. How can they offer something new without data to differentiate them?

!: Never - To indicate no return

The ! type is used for functions which will never return.

Bailing out of branches

This allows you to do:

fn random_function(v: Result<i32, String>) -> i32 {
    match v {
        Ok(_) => { 10 },
        Err(s) => {
            panic!("{s}");
        },
    }
}

The Err branch of the match statement here obviously doesn’t return an i32 - yet this is valid code. This is because the compiler knows that once it panics, its never returning to this function, thus can ignore this arm not returning an i32.

I will say that panic! is a macro, and we don’t actually know what it’s return type is, so I used cargo expand, and it turned into:

::core::panicking::panic_fmt(format_args!("{0}", s));

For which, the documentation is here. (Of course we can reason that we know it’d expand into a function that doesn’t return, but just to show explicitly).

There’s nothing special about panic! either. Any function that doesn’t return works, such as the basic:

fn never_ending() -> ! {
    loop {}
}

fn random_function(v: Result<i32, String>) -> i32 {
    match v {
        Ok(_) => { 10 },
        Err(_) => {
            NeverEnding();
        },
    }
}

Just to clearly make the difference between ! and () clear, if panic! or NeverEnding returned (), that would imply they do return, just with no data to return - the compiler would see that and then complain that the Err arm doesn’t return the i32 it needs to.

Related to this is a key difference between () and ! - () is always constructible, yet ! is never constructible - that is, it’s an empty type.

This makes sense - if your function returns !, and ! is literally impossible to construct, then of course such a function cannot return.

There does seem to be a bit of compiler magic surrounding ! - it’s possible to define empty types easily, like enum Void {}, but if I do

enum Void {}
fn never_ending() -> Void {
    loop {}
}

fn random_function(v: Result<i32, String>) -> i32 {
    match v {
        Ok(_) => { 10 },
        Err(_) => {
            NeverEnding();
        },
    }
}

The compiler is no longer happy with this code. Though, this isn’t a big deal - there’s little point to do this when ! is much clearer code and works properly.

Deleting enum variants

The inability to construct ! can also be used to delete variants from certain enums.

If a function returns Result<T, !>, that means that it will only return upon succeeding. This particular example doesn’t make much sense - why not just return T? But when handling generics, such as with trait-impls, it can make sense. For example, implementing FromStr for String would logically never fail. FromStr looks like:

trait FromStr: Sized {
    type Err;
    fn from_str(s: &str) -> Result<Self, Self::Err>;
}

You could define a new trait like FromStrInfallible, but anything that works on the FromStr trait (like using it as a trait-bound) wouldn’t work. So instead, when implementing FromStr for String, you can set type Err = !;

Then, whenever you call String::from_str, you can destructure it with just the Ok field, as the Err field can never be constructed. See:

let Ok(s) = String::from_str("hi");

The converse notion, of a function that only returns if it errors, can be represented as Result<!, E>. If you have a web server thats meant to always be running and taking requests, returning if an error occurs.

fn server_loop() -> Result<!, ConnectionError> {
    loop {
        let (client, request) = get_request()?;
        let response = request.process();
        response.send(client);
    }
}

Which we could then destructure as:

let Err(e) = server_loop();

Two more things to say on this:
First - the ! is still experimental, and must be opted into with #![feature(never_type)].
Secondly - we must also enable #![feature(exhaustive_patterns)] to let us destructure stuff like this. An article which seemed to explain a bit about why this isn’t easy to just implement in was this, though I can’t speak for their suggestions as to the solution.

Please note that just because both of these use Result as the example enum to ‘delete options from’, doesn’t imply this doesn’t extend to other enums. If you can specify the type of a generic that a variant takes, it can be deleted by giving it ! or any empty type.

// No generics we can turn into '!'
enum CantDelete {
    Option1,
    Option2,
}

// When constructing can give '!' as 'T' so we can exhaustively match just the first option
enum CanDelete<T> {
    Option1(u32),
    DeletableOption2(T),
}


fn main() {
    let exhaustable : CanDelete<!> = CanDelete::Option1(10);
    let CanDelete::Option1(num) = exhaustable;
}

PhantomData

PhantomData is a ZST associated with a generic T. Sometimes, we have structs which are associated with certain types, but don’t actuall have them as fields. Rust disallows unused parameters for types, so instead we insert a ‘PhantomData’ of that type.

A simple way of thinking about it is that at compile time, it looks like that struct has a member of type T, whereas at run time, its actually a ZST.

Associating lifetimes

For an iterator defined for &‘a [T]’, the layout would look something like:

struct Iter<'a, T: 'a> {
    ptr: *const T,
    end: *const T,
}

However as mentioned we can’t have unused parameters - so instead we associate the lifetime using PhantomData.

struct Iter<'a, T: 'a> {
    ptr: *const T,
    end: *const T,
    _marker: marker::PhantomData<&'a T>,
}

Now, the iterator is properly bounded by the lifetime ’a (and is actually covariant over it).

Given that we don’t actually ever make use of the marker, PhantomData is a very nice choice. We could potentially just associate a real &'a T with the struct, but then we’re bloating the size of the struct with fields we won’t actually use - PhantomData doesn’t do this given it compiles down to a ZST.

One thing to note is that you should know the variance you want to associate with the struct in relation to 'a and T. A good read for that is here

Edge cases with destructors

It used to be also necessary to introduce PhantomData to guarantee the correctness of some destructors. For Vec<T>, which may look like:

struct Vec<T> {
    data: *const T, // *const for variance!
    len: usize,
    cap: usize,
}

The compiler used to say that Vec<T> doesnt own any T and doesn’t need to drop them, - we would then add a PhantomData<T> to it. Now however, as long as Vec<T> implements

impl<T> Drop for Vec<T>

The compiler sees that Vec<T> may use values of type T when dropping stuff, and thus does what we want here.

The edge case is, however, that if struct associated with T (Vec<T> here) doesn’t implement Drop, but does have drop-glue because of one of it’s members having drop-glue, a PhantomData is still required for stuff to get dropped properly.

Removing auto-traits (OIBITs)

Auto-traits are traits that are automatically derived for a type given they don’t have any fields that don’t derive them, and don’t opt out themselves.

A common example is Send and Sync. To opt out, in the future you’d do something like:

struct Mytype {
    x: i32
}

impl !Sync for MyType {}

However this is currently still unstable. The stable alternative is to use PhantomData for a type that doesn’t implement the given auto-trait.

struct Mytype {
    x: i32
    _marker: PhantomData<Cell<u8>> // The type `Cell` wraps isn't particularly important - maybe not a ZST itself?
}

State machines

An article I read talked about using ZSTs to implement a state machine.

I will first say that I don’t have a fully formal understanding what exactly a state-machine is and isn’t, so take my thoughts with a grain of salt.

The state machine implemented is very simple, and I don’t think you could get very far without variables to hold data you might need. You could have a struct with all the different variables you might need, as well as a ‘State’ struct, but if a given state has data irrelevant to other states, this becomes bloated. Overall, a better design seemed to be something like this.

I can’t see it being a common need for a ZST-based state-machine unless size truly is critical.

ZST instantiations as proof

Onto some other uses of ZSTs which I do think are genuinely novel, which all come from here.

I recommend reading the full article - though it is a doozy. Centered mostly around the power of rusts type system, where ZST types act as theorums and instantiations of those act as proofs (Where the constructor can have certain invariants needed to construct them). I’ll only be talking about two examples which I like, as I am decently afraid of miswording the article.

Replacing Marker traits

Marker traits act to indicate that a given property holds for a type. A function that requires this can have a trait bound, like fn foo(T: Copy)

However, a ZST with a constructor that requires that trait-bound can instead be provided to the function, removing this trait-bound. See:

Note that for non-marker traits that act to give you actual functions/behaviour to work with, this replacement doesn't really make sense.

For a given interface with competing marker-traits, choosing a specific implementation will lock you into that choice. Instead, proof ZSTs can help.

The example given is the Pod (Plain-old data) marker trait, with several different impls. Instead of having functions with trait bounds like fn foo(T: bytemuck::Pod), we can have a ZST generic over T that has several different constructors depending on your preferred marker trait. Then we define the actual needed behaviour on that ZST, and any functions that need the Pod behaviour for T takes in the ZST.

Proof of work

It’s a common scenario to have a struct that’s expensive to initialise, and we may not necessarily need, and thus only want to initalise when necessary.

Here, we tend to use OnceCell or OnceLock. Because we don’t know if they’re initalised, .get() returns an Option<T>. There is a need to check before each access, which affects performance. We could instead create a ‘tagged’ OnceCell, that when we initialise returns a ZST that implies the initialisation, and have that ZST as an unused argument to .get() to conifently have get return T. See below:

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() }
  }
}

The above is taken from the website listed - I think get_or_init probably ought to return a tuple of the ‘proof ZST’ as well as T, but it should be visible why get is safe, despite having unsafe code.

Unfortunately, having OnceCell/OnceLock ported to the core library, they have removed get_unchecked, so we can’t do this cool trick using the core versions. :(

Conclusion

That’s all I’ve managed to dig up about ZSTs - it was a pretty fun deep dive. Kudos to all the authors of the listed articles, please check them out for a more in-depth discussion of each given topic.

Additionally, thanks to all the people who’ve answered my questions, especially on the rust discord!!!

Resources