Background

I wanted to showcase a fascinating TypeScript puzzle I encountered during a project with AWS Step Functions. For those unfamiliar, Step Functions are state machines with each state containing a certain function. These functions can be making a Lambda call, querying DynamoDB tables, broadcasting events to SQS, etc.

Naturally, each state in the machine had an input and output interface. The core rule is that if stateA feeds into stateB, then the input interface of stateB must be a subset of the output interface of stateA. Conversely, the output interface of stateA is a superset of the input interface of stateB.

I worked on an SDK for AWS Step Functions built on TypeScript. My goal was to leverage the power of TypeScript's static typing to help developers manage the input and output interfaces for the states in their state machine. For instance, I wanted the IDE to warn the developer if their state IO interfaces did not match up correctly.

Therefore, I need to design a notion of "subset" and "superset" type relationships using TypeScript.

Subset

Designing subset was pretty straightforward. I started with:

type Subset<T> = {
  [K in keyof T]?: T[K];
};

This requires that fields in Subset<T> only come from fields in T. Here's a demo of this:

interface Foo {
  foo: string
  bar: number
}

// this is good!
const subset: Subset<Foo> = {
  foo: 'foo'
}

// this is bad, field `moo` doesn't exist in `Foo`
const notSubset: Subset<Foo> = {
  foo: 'foo'
  moo: false // IDE underlines this
}

But we've only designed subset logic on the first layer for these interfaces. In other words, this won't work:

interface Foo {
  foo: {
    bar: number;
    moo: boolean;
  };
}

// should be good, but IDE says we're missing field `bar` in `Foo`
const shouldBeSubset: Subset<Foo> = {
  foo: {
    bar: 1,
  },
};

Hence, we need to apply our subset logic to every level, recursively. We can easily do this because TypeScript offers recursive typing!

type Subset<T> = {
  [K in keyof T]?: Subset<T[K]>;
};

Now this finally works at any depth level. Here's a playground to demo.

Superset

Designing the superset type was tricky. I started with:

type Superset<T> = {
  [K in keyof T]: Superset<T[K]>;
} & {
  [ExtraField: string]: unknown;
};

This is saying that the superset needs to contain all of the fields in T, along with any extra fields handled with unknown. However, we now need to handle "base cases" in recursive typing where values are of boolean, number, string, or Array. Why? These base cases can't be resolved with Superset<T[K]> because Superset<T> only handles objects.

type Superset<T> = {
  [K in keyof T]: Superset<T[K]> | T[K];
} & {
  [ExtraField: string]: unknown;
};

By simply adding the | T[K] base case, we handle the base cases for primitive types. Now this works! Try it in this playground.