DEV Community

Rasmus Larsson
Rasmus Larsson

Posted on • Edited on

On Making Impossible States Impossible

#elm #gleam #typescript #statictyping

"Impossible!" - Vizzini

"You Keep Using That Word, I Do Not Think It Means What You Think It Means" - Inigo Montoya

Dog year ages ago Richard Feldman held a great talk about making impossible states impossible that has influenced my thinking on this topic since, including how I at the time modeled the XML we were using in the app I was working on.

Here I aim to dig into and list some of the symptoms I've come across and how to remove them.

The examples are in TypeScript and Gleam but the concepts should be broadly applicable to any language/specification that has a decently strong type system.

If you dig Elm or Gleam like me but these concepts are new to you, I can recommend checking out either Gleam's opaque types and phantom types, or Elm's opaque types and phantom types.

If you're more TypeScript inclined then it's worth reading up on how branded types work in TypeScript.

If you find any errors or have any examples that I haven't covered, please let me know.

Table of contents

Gentle Introduction

Now, a gentle introduction to what is meant by impossible states for those of you who didn't take the time to watch the talk.

// ❌
type Payment = { method: "card" | "cash"; cardNumber?: string };

// allows an impossible state
const p: Payment = { method: "cash", cardNumber: "1234" };
Enter fullscreen mode Exit fullscreen mode

What happens if a downstream system forgets to check method and only looks for cardNumber? And can we avoid this all together?

// ✅ Better type safety.
type Payment = { type: "cash" } | { type: "card"; cardNumber: string };

const p: Payment = { type: "cash", cardNumber: "1234" };
//                                 ^^^^^^^^^^
// Object literal may only specify known properties,
// and 'cardNumber' does not exist in type '{ type: "cash"; }'.ts(2353)
Enter fullscreen mode Exit fullscreen mode

The Gleam version actually turns out shorter and simpler in the more refactored version unlike TypeScript's.

// ❌
pub type Payment {
  Payment(
    method: PaymentMethod,
    card_number: Option(String),
  )
}

pub type PaymentMethod {
  Card
  Cash
}

// allows an impossible state
pub fn bad_cash_payment() -> Payment {
  Payment(Cash, Some("1234"))
}

// ✅ Better type safety.
pub type BetterPayment {
  Cash
  Card(card_number: String)
}

// Cash can never have a card number.
pub fn cash_payment() -> BetterPayment {
  Cash
}
Enter fullscreen mode Exit fullscreen mode

Patterns of Impossible States

Even though the idea may now be clear, to actually get into the mindset when producing code, and also spotting them, it helps having patterns. I've attempted to categorize them as best as possible.

Impossible Data Structures

Impossible data structures can usually be re-modeled to eliminate the impossible states. Often these impossible states can be spotted by the existence/over-existence of optional fields.

Different Entity States/Sub-types with Different Field Requirements

Common with fields like 'state' or 'status' or when sub-typing class hierarchies (vehicles, animals etc.).

// ❌ too many optional fields ⇒ impossible states allowed
interface Article {
  state: "draft" | "published" | "archived";
  title: string;
  body: string;
  publishedAt?: string;
  comments: Comment[];
  archivedReason?: string;
  archivedAt?: string;
}

// ✅ Impossible states eliminated
type Article =
  | {
      state: "draft";
      title: string;
      body: string;
    }
  | {
      state: "published";
      title: string;
      body: string;
      publishedAt: string;
      comments: Comment[];
    }
  | {
      state: "archived";
      archivedReason: string;
      archivedAt: string;
    };
Enter fullscreen mode Exit fullscreen mode 
// ❌ too many optional fields ⇒ impossible states allowed
pub type BadArticle {
  BadArticle(
    state: ArticleState,
    title: String,
    body: String,
    published_at: Option(String),
    comments: List(Comment),
    archived_reason: Option(String),
    archived_at: Option(String),
  )
}

pub type ArticleState {
  DraftState
  PublishedState
  ArchivedState
}

pub type Comment {
  Comment(body: String)
}

// ✅ Impossible states eliminated
pub type Article {
  Draft(title: String, body: String)
  Published(title: String, body: String, published_at: String, comments: List(Comment))
  Archived(archived_reason: String, archived_at: String)
}
Enter fullscreen mode Exit fullscreen mode

Mutually Exclusive Fields 

// ❌ mutually exclusive optional fields that can co-exist
interface Auth {
  password?: string;
  oauthToken?: string;
}

// ✅ Impossible states eliminated
type Auth = { method: "password"; password: string } | { method: "oauth"; oauthToken: string };
Enter fullscreen mode Exit fullscreen mode 
// ❌ mutually exclusive optional fields that can co-exist
pub type BadAuth {
  BadAuth(password: Option(String), oauth_token: Option(String))
}

// ✅ Impossible states eliminated
pub type Auth {
  Password(password: String)
  Oauth(oauth_token: String)
}
Enter fullscreen mode Exit fullscreen mode

Mutually Inclusive Fields 

// ❌ Config is required if enabled is true
interface X {
  enabled?: boolean;
  config?: { foo: number };
}

// ✅ Impossible states eliminated
type X = { enabled: false } | { enabled: true; config: { foo: number } };
Enter fullscreen mode Exit fullscreen mode 
// ❌ Config is required if enabled is true
pub type BadConfig {
  BadConfig(enabled: Option(Bool), config: Option(Config))
}

pub type Config {
  Config(foo: Int)
}

// ✅ Impossible states eliminated
pub type X {
  Disabled
  Enabled(config: Config)
}
Enter fullscreen mode Exit fullscreen mode

Triple Value Boolean 

// ❌ What does 'hasAcceptedTerms: null' mean?
interface User {
  hasAcceptedTerms?: boolean;
}

// ✅ Clear communication of meaning
interface User {
  termsStatus: "accepted" | "rejected" | "pending";
}
Enter fullscreen mode Exit fullscreen mode 
// ❌ What does `has_accepted_terms: None` mean?
pub type BadUser {
  BadUser(has_accepted_terms: Option(Bool))
}

// ✅ Clear communication of meaning
pub type TermsStatus {
  Accepted
  Rejected
  Pending
}

pub type User {
  User(terms_status: TermsStatus)
}
Enter fullscreen mode Exit fullscreen mode

Illegal (Boolean) Combinations

The boolean combinations are probably the easiest to spot but other illegal combinations can occur too, such as enums (a model of exchange rates like EUR/USD should disallow EUR/EUR).

// ❌ Can a door be open and locked at the same time?
interface Door {
  isOpen: boolean;
  isLocked: boolean;
}
// ✅ No it cannot
type Door = { state: "open" } | { state: "closed" } | { state: "locked" };
Enter fullscreen mode Exit fullscreen mode 
// ❌ Can a door be open and locked at the same time?
pub type BadDoor {
  BadDoor(is_open: Bool, is_locked: Bool)
}

// ✅ No it cannot
pub type Door {
  Open
  Closed
  Locked
}
Enter fullscreen mode Exit fullscreen mode

The Failure State

In some cases it's handy to actually model the failure state instead of bubbling up an Exception or similar, especially when working in the frontend and you want to show something meaningful to the user.

Case in point from a TypeScript project I'm working on. An entity can have a template associated with it and we want to show a button if it does, but the template comes from a different endpoint. In our frontend the evolution was:

// ❌ doesn't really cover all the cases
const hasTemplate: boolean | undefined

// ⚠️ Somewhat better
const hasTemplate: 'loading' | 'not-found' | 'found'

// ✅ Covers all the states
const templateState: 'loading' | 'not-found' | 'found' | 'failed'
Enter fullscreen mode Exit fullscreen mode

Now we can show something useful regardless of the outcome and we don't have to guess what undefined means.

This scenario is so common that there are ready-made libraries for this such as Elm's RemoteData:

type RemoteData e a
    = NotAsked
    | Loading
    | Failure e
    | Success a
Enter fullscreen mode Exit fullscreen mode

Constrained Values

Constrained values, values that typically have constraints that are outside the reach of the type system, tend to require specialized functions/constructors to solve.

Collections with Mandatory Values

Collections that have mandatory values can usually be re-modeled as records with mandatory fields.

// ❌ Still allows an empty array.
type NonEmptyArray<T> = T[];

// ✅ Impossible states eliminated
type NonEmptyArray<T> = { first: T; rest: T[] };

// Implement the functions you need.
/**
 * Returns the last element if length > 1,
 * else undefined.
 */
function new_non_empty_array<T>(first: T, rest: T[]): NonEmptyArray<T> {
  return { first, rest };
}

function to_array<T>(nea: NonEmptyArray<T>): T[] {
  return [nea.first, ...nea.rest];
}
Enter fullscreen mode Exit fullscreen mode 
// ❌ Still allows an empty list.
pub type BadNonEmptyList(a) {
  BadNonEmptyList(List(a))
}

// ✅ Impossible states eliminated
pub opaque type NonEmptyList(a) {
  NonEmptyList(first: a, rest: List(a))
}

pub fn new(first: a, rest: List(a)) -> NonEmptyList(a) {
  NonEmptyList(first, rest)
}

pub fn to_list(nea: NonEmptyList(a)) -> List(a) {
  [nea.first, ..nea.rest]
}
Enter fullscreen mode Exit fullscreen mode

Context Dependency

When a certain context is required, such as in a child-parent relationship.

// ❌ Child can exist without parent
interface Child {
  parentId?: string;
  value: number;
}

// ✅ Require constructor that supplies the parent
interface Parent {
  id: string;
}

interface Child {
  parent: Parent;
  value: number;
}

function makeChild(parent: Parent, value: number): Child {
  return { parent, value };
}
Enter fullscreen mode Exit fullscreen mode 
// ❌ Child can exist without parent
pub type BadChild {
  BadChild(parent_id: Option(String), value: Int)
}

// ✅ Require constructor that supplies the parent
pub type Parent {
  Parent(id: String)
}

pub type Child {
  Child(parent: Parent, value: Int)
}

pub fn make_child(parent: Parent, value: Int) -> Child {
  Child(parent, value)
}
Enter fullscreen mode Exit fullscreen mode

Constrained Value or Mutually Constrained Values

These are values that are by themselves or collectively required to satisfy some business rule.

// ❌ Not guaranteed to be positive
interface X {
  quantity: number;
}

// ✅ Uses brand types to ensure
type Positive = number & { __brand: "Positive" };

function makePositive(n: number): Positive | Error {
  return n > 0 ? (n as Positive) : new Error("Not positive");
}

interface X {
  quantity: Positive;
}

// ❌ Does not guarantee start <= end in and of itself
interface Interval {
  start: Date;
  end: Date;
}

// ✅ combine with a branded type
function makeInterval(start: Date, end: Date): Interval | Error {
  if (end < start) return new Error("Invalid interval");
  return { start, end };
}
Enter fullscreen mode Exit fullscreen mode 
// ❌ Not guaranteed to be positive
pub type BadX {
  BadX(quantity: Int)
}

// ✅ Uses an opaque type to ensure positivity
pub opaque type Positive {
  Positive(Int)
}

pub fn make_positive(n: Int) -> Result(Positive, String) {
  if n > 0 {
    Ok(Positive(n))
  } else {
    Error("Not positive")
  }
}

pub type X {
  X(quantity: Positive)
}

// ❌ Does not guarantee start <= end in and of itself
pub type Interval {
  Interval(start: Int, end: Int)
}

// ✅ smart constructor enforces the invariant
pub fn make_interval(start: Int, end: Int) -> Result(Interval, String) {
  if end < start {
    Error("Invalid interval")
  } else {
    Ok(Interval(start, end))
  }
}
Enter fullscreen mode Exit fullscreen mode

Private Data

Data that should not be exposed/available. This can be solved using branded types or private fields in TypeScript, and opaque types in Gleam/Elm.

// using branded types
type UserId = string & { readonly brand: unique symbol };

function makeUserId(s: string): UserId {
  return s as UserId;
}

// using TypeScript's private keyword
class BankAccount {
  private balance = 100;
}

new BankAccount().balance; // ❌ Compile-time error
// ⚠️ but still available at runtime so JSON.stringify(bankAccount) will leak it

// using ECMAscript private
class Person {
  #ssn: string;
  constructor(ssn: string) {
    this.#ssn = ssn;
  }

  getLast4() {
    return this.#ssn.slice(-4);
  }
}

const p = new Person("123-45-6789");
p.#ssn; // ❌ Error
Enter fullscreen mode Exit fullscreen mode 
// using an opaque type
pub opaque type UserId {
  UserId(String)
}

pub fn user_id_from_string(s: String) -> UserId {
  UserId(s)
}

// callers can never see the inner String
pub fn user_id_to_string(id: UserId) -> String {
  let UserId(inner) = id
  inner
}
Enter fullscreen mode Exit fullscreen mode

Invalid State Transitions

Invalid state transitions can be protected using types.

interface Doc {
  state: "draft" | "submitted" | "approved";
  // ...
}

function approve(doc: Doc) {
  // ⚠️ requires validation and test cases
  if (doc.state !== "submitted") throw new Error("Invalid state");
}
Enter fullscreen mode Exit fullscreen mode 
// ✅ Eliminates validation and test cases
// ---- States ----

export interface Draft {
  state: "draft";
  content: string;
}

export interface Submitted {
  state: "submitted";
  content: string;
  submittedAt: Date;
}

export interface Approved {
  state: "approved";
  content: string;
  approvedAt: Date;
}

// ---- Valid transitions ----

// Only a Draft can be submitted
export function submit(draft: Draft): Submitted;

// Only a Submitted can be approved
export function approve(submitted: Submitted): Approved;
Enter fullscreen mode Exit fullscreen mode 
// ❌ single type with a flag field
pub type Doc {
  Doc(state: DocState, content: String)
}

pub type DocState {
  DraftState
  SubmittedState
  ApprovedState
}

pub fn bad_approve(doc: Doc) -> Result(Doc, String) {
  case doc.state {
    SubmittedState -> Ok(Doc(ApprovedState, doc.content))
    _ -> Error("Invalid state")
  }
}

// ✅ Separate types for each state.
// A phantom type `Article(state)` could also be used.
pub type Draft {
  Draft(content: String)
}

pub type Submitted {
  Submitted(content: String, submitted_at: String)
}

pub type Approved {
  Approved(content: String, approved_at: String)
}

pub fn submit(draft: Draft, now: String) -> Submitted {
  let Draft(content) = draft
  Submitted(content, now)
}

pub fn approve(submitted: Submitted, now: String) -> Approved {
  let Submitted(content, _) = submitted
  Approved(content, now)
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)