Depiction of walnuts, some cracked open and others not.

Type systems are tools for modeling some aspect of reality. Some types need to represent one of several different choices.

  • Sometimes, all the choices may be known in advance and will likely never change—this is often called a closed universe of values.
  • Other times, the set of options will change over time, and the type needs to represent an open universe.

How should these different kinds of choices be modeled?


Aside: this matters more for libraries than for applications

If you’re writing an end-user application, none of this matters. You have full control over all aspects of your code, so use whatever is most convenient. However, if you’re writing a library that other developers will use, you may care about API stability and forward compatibility.


Closed universes as enums

A simple example is the Option type in Rust, or its analogs like Maybe in Haskell. Option is defined as:

pub enum Option<T> {
    None,
    Some(T),
}

Part of the definition of Option is that it can only be either Some or None. This is never going to change, so Option values form a closed universe. A simple enum is appropriate for such cases.

The main advantage of this approach is that it minimizes the burden on consumers: they know that an Option can only be Some or None, and only have to care about such cases.

The main disadvantage is that any sort of new addition would constitute API breakage. You’re expanding a universe you formerly assumed to be closed, and everyone who depends on you needs to be made aware of this.

Semi-open and fully open universes

As a library author, you may run into two kinds of open universes:

  1. Open with respect to the library itself: new choices can be defined by library authors in the future, but not by downstream consumers. I’m going to call these semi-open universes.
  2. Open with respect to users of the library: new choices can be defined by both library authors and consumers. These might be described as fully open universes.

Non-exhaustive enums

If you’re trying to model semi-open universes, consider using a non-exhaustive enum.

For example, you may have an error type in a library that bubbles up other errors. One way to write this is:

pub enum Error {
    Io(std::io::Error),
    Json(serde_json::Error),
}

The problem with this approach is that errors typically do not form a closed universe. A future version may depend on some other library, for example toml, and you’d have to add a new option to the Error type:

pub enum Error {
    Io(std::io::Error),
    Json(serde_json::Error),
    Toml(toml::de::Error),
}

Anyone matching on the Error type would have to handle this new, additional case… unless they’ve specified a wildcard pattern.

Some programming languages allow library developers to force consumers to specify a wildcard pattern. In Rust, you can annotate a type with #[non_exhaustive]:

#[non_exhaustive]
pub enum Error {
    Io(std::io::Error),
    Json(serde_json::Error),
    Toml(toml::de::Error),
}

Anyone matching against the error type would have to add an additional wildcard pattern:

match err {
    Io(err) => // ...
    Json(err) => // ...
    Toml(err) => // ...
    // The match statement will fail to compile without this last wildcard pattern
    _ => // ...
}

This ensures that the library developer can continue to add more options over time without causing breakages. The main downside is that all consumers need to handle the additional wildcard pattern and do something sensible with it1.

Many strings

The non-exhaustive enum approach is best suited for semi-open universes. What about situations where consumers should have the ability to add new choices?

The best way is often to use a string, or a newtype wrapper around it. For example, one may wish to represent a choice between computer architectures such as i386, amd64, and aarch64. More architectures may be added in the future, too, but often the library just needs to pass the architecture down to some other tool without doing much processing on it. One way to represent this is2:

use std::borrow::Cow;

pub struct Architecture(Cow<'static, str>);

impl Architecture {
    pub fn new(name: impl Into<Cow<'static, str>>) -> Self {
        Architecture(name.into())
    }
}

Well-known strings can be represented as constants:

impl Architecture {
    pub const fn new_const(name: &'static str) -> Self {
        Architecture(Cow::Borrowed(name))
    }
    
    pub const I386: Self = Architecture::new_const("i386");
    pub const AMD64: Self = Architecture::new_const("amd64");
    pub const AARCH64: Self = Architecture::new_const("aarch64");
}

This allows known choices to not be stringly-typed, and currently-unknown ones to be used without having to change the library.

The format doesn’t have to be restricted to strings. For example, an Architecture may wish to also carry its bitness.

pub struct Architecture {
    name: Cow<'static, str>,
    bitness: usize,
}

impl Architecture {
    pub fn new(name: impl Into<Cow<'static, str>>, bitness: usize) -> Self {
        Architecture { name: name.into(), bitness }
    }

    pub const fn new_const(name: &'static str, bitness: usize) -> Self {
        Architecture { name: Cow::Borrowed(name), bitness }
    }

    pub const I386: Self = Architecture::new_const("i386", 32);
    pub const AMD64: Self = Architecture::new_const("amd64", 64);
    pub const AARCH64: Self = Architecture::new_const("aarch64", 64);
}

In general, this works best for choices that are:

  • used as input types to a library that doesn’t do much processing on them, and
  • the data associated with each choice doesn’t vary by choice.

A pattern to avoid: Unknown or Other variants

One pattern I’ve seen is to use another variant that represents an unknown value. For example:

pub enum Architecture {
    I386,
    Amd64,
    Aarch64,
    Unknown(Cow<'static, str>),
}

The problem with this approach is that it becomes very hard to define equality and comparisons on these types. Are Architecture::I386 and Architecture::Unknown("i386") the same, or are they different? In practice, this becomes tricky very quickly.

In general, this approach is best avoided.

Traits

The final, most general approach is to use traits, typeclasses or other interface mechanisms. For example, architectures can be represented as a trait in Rust:

pub trait Architecture {
    fn name(&self) -> Cow<'static, str>;
}

pub struct I386;

impl Architecture for I386 {
    fn name(&self) -> Cow<'static, str> {
        Cow::Borrowed("i386")
    }
}

pub struct Amd64;

impl Architecture for Amd64 {
    fn name(&self) -> Cow<'static, str> {
        Cow::Borrowed("amd64")
    }
}

pub struct Aarch64;

impl Architecture for Aarch64 {
    fn name(&self) -> Cow<'static, str> {
        Cow::Borrowed("aarch64")
    }
}

Then, other library methods could use:

// This could take the architecture as a type parameter as well.
pub fn process_architecture(arch: &dyn Architecture) {
    // ...
    let name = arch.name();
    // ...
}

And custom architectures can be defined as:

pub struct MyArchitecture(String);

impl Architecture for MyArchitecture {
    fn name(&self) -> Cow<'static, str> {
        Cow::Owned(self.0.clone())
    }
}

This also works for output types such as returned errors.

pub fn read_u64() -> Result<u64, Box<dyn Error + Send + Sync + 'static>>

You can try and downcast the error into a more specific type:

match read_u64() {
    Ok(value) => // ...
    Err(err) => {
        // The function might have returned an IO error.
        match err.downcast::<std::io::Error>() {
            Ok(io_error) => // ...
            Err(err) => {
                // Could be a TOML error.
                match err.downcast::<toml::de::Error>() {
                    Ok(toml_error) => // ...,
                    Err(err) => {
                        // Some other sort of error. Handle appropriately.
                    }
                }
            }
        }
    }
}

but this turns a formerly compile-time check into a runtime one. A common bug that happens with this approach is version skew: for example, let’s say the library had originally been using toml 0.4. In a minor release, it upgrades to toml 0.5 and return errors from the new version, while the consumer continues to downcast to the old toml 0.4 version. Such cases will fail silently3.

Traits vs many strings

Traits are similar to the many-strings approach because they both model fully open universes. However, there are some tradeoffs between the two.

One benefit of traits is that they offer greater implementation flexibility: trait methods allow for custom behavior on user-defined types.

A downside is that traits make each choice in an open universe a type, not a value, so operations like equality become harder to define. It isn’t impossible, though: the trait could require a key method which returns a many-strings type.

#[derive(Eq, PartialEq)]
struct ArchitectureKey(pub Cow<'static, str>);

pub trait Architecture {
    // ...
    fn key(&self) -> ArchitectureKey;
}

The contents of ArchitectureKey can then be used for equality checks.

Another downside is ergonomics: traits and interfaces are more awkward than values. A sufficiently complex trait may even require some sort of code generation to use effectively. Rust has declarative and procedural macros to help, which work okay but add even more complexity on top.

Whether strings are sufficient or full-blown traits are required is a case-by-case decision. In general, the many-strings approach is much simpler and is powerful enough for many kinds of choices; traits provide greater power and are always worth keeping in mind, though.

Sealed traits

A trait can also model a semi-open universe if you seal it:

pub trait MyTrait: private::Sealed {
    // ...
}

pub struct MyType;

impl MyTrait for MyType {
    // ...
}

mod private {
    pub(crate) trait Sealed {}

    impl Sealed for super::MyType {}
}

The library itself may add new implementations of the trait, but downstream consumers cannot because they do not have access to Sealed4.

Conclusion

Stylized representation of Buzz Lightyear from Pixar's Toy Story, with the text "To infinity... and beyond!" on it. Print by Evan Troutt, courtesy Gallery1988.
Print by Evan Troutt, courtesy Gallery1988.

Type systems are often used to represent one of several choices. The choices can either be fixed (closed universe), or might continue to change over time (open universe). These are different situations that usually need to be handled in different ways.

Hope this helps!


The idea of writing this post arose from several conversations with members of the Rust community. Thanks to Munin, Jane Lusby, Manish Goregaokar, Michael Gattozzi and Izzy Muerte for reviewing drafts of this post.


Updated 2021-08-04: edited some text, and corrected the footnote about Cow to indicate that it is required.

Updated 2021-08-13: added a note about more complex versions of the many-strings pattern, expanded on the difference between it and traits, and expanded on what it would mean to unify sealed traits and non-exhaustive enums. Thanks to Manish for the inspiration.


  1. I wish that Rust had a way to lint, but not fail to compile, on missing patterns in a non-exhaustive match. ↩︎

  2. This implementation uses the Cow type, which with the 'static lifetime stands for either a borrowed string that lasts the duration of the entire program—typically one embedded in the binary—or an owned String created at runtime. If this were just a String, then the const implementation below wouldn’t be possible because const fns can’t allocate memory. ↩︎

  3. With static types, this sort of version skew error is usually caught at compile time. With dynamic casting it can only be caught at runtime.

    You might argue that if the error type comes from a public dependency, an incompatible upgrade to the dependency constitutes a semantic version breakage. However, this is a bit of a boundary case; the library authors might disagree with you and say that their stability guarantees don’t extend to downcasting. Semantic versioning is primarily a low-bandwidth way for library developers and consumers to communicate about relative burdens in the event of a library upgrade. ↩︎

  4. Given that both sealed traits and non-exhaustive enums model the same kinds of semi-open universes in fairly similar fashions, a direction languages can evolve in is to unify the two. Scala has already done something similar.

    Rust could gain several features that bring non-exhaustive enums and sealed traits incrementally closer to each other:

    • Allow match statements to match sealed traits if a wildcard match is specified.
    • Make enum variants their own types rather than just data constructors.
    • Automatically convert the return values of functions like fn foo() -> impl Trait into enums if necessary. (The trait doesn’t need to be sealed in this case, because the enum would be anonymous and matching on its variants wouldn’t be possible.)
    • Inherent methods on an enum would need to be “lifted up” to become trait methods. As of Rust 1.54, there are several kinds of methods that can be specified on enums but not on traits. Features like existential types help narrow that gap.
     ↩︎