A Type Is a Set: Why Human Has Two Members and Option of Human Has Three

Investigation · Part 3 of 10 · Types under the hood

A type is a set of allowed values, so it has a size in the mathematical sense: a number of members. bool has two. Human has two. Option<Human> has three, the two humans plus None.

Once I started counting, two things the compiler does became easy to predict.

The number of bytes a type needs follows the count, with two exceptions that I measure below. And the "non-exhaustive patterns" error is the compiler counting members and finding one I did not handle.

This is a spoke of What Is a Type?, the first article of this series, which introduced the shape half of a type, the set of values it allows. Here I take that half literally and count. The programs and a script that reproduces every output are in the types-under-the-hood fixture of the site repository. I used rustc 1.95 nightly and TypeScript 5.9 on x86-64 Linux, and I checked the Rust results on stable 1.98 as well.

The counting rules

There are only two rules, and they come from how types are built.

When a type is one of several alternatives, the counts add up. An enum with two variants has 2 members. Option<T> is T or None, so it has the members of T plus one. Result<T, E> has the members of T plus the members of E.

When a type is several values together, the counts multiply. A tuple (bool, Human) has 2 times 2 members, every combination of both. A struct with three bool fields has 8.

Two special cases sit at the ends. The unit type () has exactly one member, the empty tuple. And a type with no variants at all, which I call Void below, has zero members. No value of it can be built.

The compiler agrees, with two exceptions

I wrote the counts by hand and asked rustc for the bytes with std::mem::size_of. One row uses NonZeroU8, a byte that cannot be 0, so it has 255 members:

type                          members  bytes
Void                                0      0
()                                  1      0
bool                                2      1
Human                               2      1
Option<Human>                       3      1
(bool, Human)                       4      2
Result<Human, bool>                 4      2
u8                                256      1
Option<NonZeroU8>                 256      1
Option<u8>                        257      2
(u8, bool)                        512      2
Result<u8, Void>                  256      1
u16                             65536      2
(u8, u32)                        2^40      8

Read the table from top to bottom. Zero or one member needs zero bytes, because there is nothing to distinguish. Two or three members need one byte. Two hundred and fifty-six fit in one byte exactly. Two hundred and fifty-seven do not, so Option<u8> jumps to two bytes for a single extra member.

The first exception is the pair. (bool, Human) has four members and would fit in one byte, but it takes two. A type made of several values does not pack its parts into bits. It places them side by side, and each part keeps its own bytes. Result<Human, bool> is in the same situation: an enum with a payload stores a tag next to that payload, so it is also parts side by side, unless the compiler can hide the tag in a value the payload cannot take.

The last row shows the same rule with alignment added: (u8, u32) needs five bytes to tell its members apart, and it takes eight, because a u32 must sit at an address that is a multiple of four and the whole size must be a multiple of that too.

The second exception goes the other way. Option<NonZeroU8> has 256 members and fits in one byte, because the compiler uses the excluded value 0 to mean None. This one is a promise: the standard library documents that Option<NonZeroU8> has the same size as u8, and that it can even cross into C code as a plain byte.

Option<Human> gets the same treatment, None becomes 2, but that is not promised by anything. It is what rustc does today, and the rules of when it happens are the subject of "Rust Enum Niches", which this site publishes a few days after this article.

There is a third thing in the table that I did not expect. Result<u8, Void> has 256 members, the same as u8, and it needs one byte, the same as u8.

An error type that cannot be built adds nothing. The compiler counted, found the Err side empty, and did not reserve space for it.

So the size of a type starts from the number of bits needed to tell its members apart. It goes up for alignment and for parts stored side by side, and it comes down when the compiler can reuse a value that a member cannot take.

The exhaustiveness error is counting

Now the other consequence. Here is a match that handles two of the three members of Option<Human>, and one that handles three of the four members of (bool, Human):

fn label(h: Option<Human>) -> &'static str {
    match h {
        Some(Human::Man) => "sir",
        None => "nobody",
    }
}

fn pair(p: (bool, Human)) -> u8 {
    match p {
        (true, Human::Man) => 0,
        (false, Human::Man) => 1,
        (true, Human::Woman) => 2,
    }
}

rustc refuses both, and names the member I forgot. The output is shortened to the first line of each error and the note that names the type:

error[E0004]: non-exhaustive patterns: `Some(Human::Woman)` not covered
    = note: the matched value is of type `Option<Human>`
error[E0004]: non-exhaustive patterns: `(false, Human::Woman)` not covered
    = note: the matched value is of type `(bool, Human)`

The compiler did not guess. It enumerated the set, three members for the first and four for the second, crossed out the ones my arms cover, and printed what was left.

This is also why match on a u8 needs a _ arm in practice. The set has 256 members, and the compiler will ask for every one of them unless I write a pattern that covers the rest.

Zero members: the arm you do not have to write

The zero-member type turns the same rule around:

enum Void {}

fn unreachable_value(v: Void) -> u8 {
    match v {}
}

fn parse(text: &str) -> Result<u8, Void> {
    Ok(text.len() as u8)
}

fn main() {
    let Ok(n) = parse("four");
    println!("parsed {n}, and the Err arm was not needed");
}

This compiles and prints:

parsed 4, and the Err arm was not needed

Two things happened. A match with no arms at all is complete, because there are zero members to cover. And let Ok(n) = parse(...) is allowed without an Err case, for the same reason: the compiler counted the members of Result<u8, Void>, found that all 256 of them are Ok, and let me skip the pattern.

This works on stable Rust since version 1.82, which allowed leaving out patterns for empty types. The old rule still applies when the empty type sits behind a reference, a raw pointer, or a union field, and there the Err arm has to be written.

Rust has a built-in spelling of the empty type, !, called the never type, but on stable Rust it can only appear as a function return type today. What libraries use instead is std::convert::Infallible, an empty type from the standard library that is being turned into an alias for !. It works exactly like my Void. The fixture parses the word "three" this time, so the length is 5:

parsed 5 with Infallible, same thing
size of Result<u8, Infallible>: 1

A function that returns Result<T, Infallible> is saying "this cannot fail" in a form the compiler can count, and callers do not need an Err arm.

The same counting in TypeScript

TypeScript has the same sets under different names. "man" | "woman" has two members, "man" | "woman" | undefined has three, and the empty set is called never. TypeScript does not force a switch to be exhaustive, but it will do the counting if I ask, with a small trick:

type Human = "man" | "woman";

function label(h: Human | undefined): string {
  switch (h) {
    case "man": return "sir";
    case undefined: return "nobody";
  }
  const missing: never = h;
  return missing;
}

After the two cases, h can only be what is left of the set. If I handled everything, what is left is never, and the assignment is fine. I did not, so the compiler reports the leftover member. The file position at the start of the line is dropped here:

error TS2322: Type '"woman"' is not assignable to type 'never'.

It is the same subtraction, reported through the empty set instead of a dedicated error. Adding case "woman" makes the leftover never and the file compiles.

The model I take from this

A type is a set, and its members can be counted. Alternatives add, combinations multiply, () is one, an empty enum is zero.
The bytes follow the count, up for alignment and side-by-side parts, down when the compiler can reuse a value a member cannot take. Only some of those reuses are promised.
Exhaustiveness is subtraction. The compiler enumerates the set and prints what my patterns did not cover.
A set with zero members needs zero bytes and zero match arms, and it is a useful way to say "cannot happen" that the compiler can verify.

As in the first article of this series, none of this reaches the processor. The count is used to choose a size and to check my patterns, and then only the bytes remain.

What I check when I design a type

How many members does it have? If the number is far above what the program needs, the extra members are states I will have to handle or exclude.
Am I using Option on a type that already has an impossible value? If yes, the Option may be free, and for the standard NonZero types it is promised to be.
Does an error type exist that can never be built? Then Result<T, Infallible> says so, and callers do not need an Err arm.
In TypeScript, do I end every switch over a union with a never assignment? It is the only way to make the compiler count.