Mapping Between Circular Types in TypeScript

Question

This question is regarding statically inferring the signature of runtime types (seen in libraries such as zod and io-ts).

The following example can be seen in action at this TS playground link.

Let's say we're trying to model some type information for runtime use. We can declare the following Type enum to get us started:

enum Type {
  Boolean = "Boolean",
  Int = "Int",
  List = "List",
  Union = "Union",
}

Our runtime type system should support booleans, integers, unions, and lists.

The base type looks like this:

interface Codec<T extends Type> {
  type: T;
}

The boolean and integer types use that base type like so.

Boolean:

class BooleanCodec implements Codec<Type.Boolean> {
  type = Type.Boolean as const;
}

Integer:

class IntCodec implements Codec<Type.Int> {
  type = Type.Int as const;
}

The union type accepts an array of types to unite:

class UnionCodec<C extends Codec<Type>> implements Codec<Type.Union> {
  type = Type.Union as const;
  constructor(public of: C[]) {}
}

And the list type accepts the type of which its elements are comprised:

class ListCodec<C extends Codec<Type>> implements Codec<Type.List> {
  type = Type.List as const;
  constructor(public of: C) {}
}

Let's construct a list of booleans or integers:

const listOfBooleanOrIntCodec = new ListCodec(
  new UnionCodec([
    new BooleanCodec(),
    new IntCodec(),
  ]),
);

This evaluates to the following object:

{
  type: Type.List,
  of: {
    type: Type.Union,
    of: [
      {
        type: Type.Boolean,
      },
      {
        type: Type.Int,
      },
    ]
  }
}

This codec would carry a signature of ListCodec<UnionCodec<BooleanCodec | IntCodec>>.

We might even see cycles within a given codec, and as such, mapping the type signature gets tricky. How would we get from the above to (boolean | number)[]? And does it account for deep nesting of codecs?

For BooleanCodec or IntCodec, working backwards is fairly easy... but the UnionCodec and ListCodec decoding needs to be recursive. I tried the following:

type Decode<C extends Codec<Type>> =
  // if it's a list
  C extends ListCodec<Codec<Type>>
    ? // and we can infer what it's a list of
      C extends ListCodec<infer O>
      ? // and the elements are of type codec
        O extends Codec<Type>
        ? // recurse to get an array of the element(s') type
          Decode<O>[]
        : never
      : never
    : // if it's a union
    C extends UnionCodec<Codec<Type>>
    // and we can infer what it's a union of
    ? C extends UnionCodec<infer U>
      // and it's a union of codecs
      ? U extends Codec<Type>
        // recurse to return that type (which will be inferred as the union)
        ? Decode<U>
        : never
      : never
      // if it's a boolean codec
    : C extends BooleanCodec
    // return the boolean type
    ? boolean
    // if it's ant integer codec
    : C extends IntCodec
    // return the number type
    ? number
    : never;

It regrettably errors with Type alias 'Decode' circularly references itself and Type 'Decode' is not generic.

I'm wondering if it's possible to accomplish this kind of cyclical type-mapping, and how I might make such a utility as Decode work? Any help would be greatly appreciated. Thank you!

Answer 1

I usually define types and then derive a generic codec from it, rather than constructing codecs explicitly.

For example: First, define your types with some data and encode their relationships (list item and union values):

type Type = Integer | List<any> | Union<any>;
interface Integer {
  type: 'integer';
}
interface List<T extends Type> {
  type: 'list';
  item: T;
}
type UnionValues = Type[];
interface Union<T extends UnionValues> {
  type: 'union';
  values: T;
}

It's nice to also provide helpers for creating these types:

const integer: Integer = { type: 'integer' };
const list = <T extends Type>(item: T): List<T> => ({
  type: 'list',
  item
});
const union = <T extends UnionValues>(...values: T): Union<T> => ({
  type: 'union',
  values
});

You can then write a recursive type-mapping function. This will map a Type to its corresponding JS type:

type Decode<T> =
  // terminal recursion: Integer is represented as a number
  T extends Integer ? number :
  // extract the Item from the list and construct an Array recursively
  T extends List<infer I> ? Decode<I>[] :
  // union is an array of types, so loop through and decode them
  T extends Union<infer U> ? {
    [i in Extract<keyof U, number>]: Decode<U[i]>;
  }[[Extract<keyof U, number>]] :
  never
  ;

Define your codec as a read from Type => Value:

interface Codec<T extends Type, V> {
  type: T;
  read(value: any): V;
}

Write a function that maps a type instance to its Codec:

function codec<T extends Type>(type: T): Codec<T, Decode<T>> {
  // todo
}

Now you can safely map between your type system and JS types:

const i = codec(integer);
const number: number = i.read('1');

const l = codec(list(integer));
const numberArray: number[] = l.read('[1, 2]');

const u = codec(union(integer, list(integer)));
const numberOrArrayOfNumbers: number | number[] = u.read('1');

I tried to recreate your example where developers write codecs which encode their type. I think this is loosely what you're trying to do. It was a bit more complicated because you need to map over tuples.

Integer codec is a straight mapping of Integer -> number.

class IntegerCodec implements Codec<Integer, number> {
  public readonly type: Integer = integer;

  public read(value: any): number {
    return parseInt(value, 10);
  }
}

ListCodec recursively computes a mapping of List -> ItemValue[]

namespace Codec {
  // helper type function for grabbing the JS type from a Codec<any, any>
  export type GetValue<C extends Codec<any, any>> = C extends Codec<any, infer V> ? V : never;
}
// this is where we recurse and compute the Type and JSType from the provided Item codec
class ListCodec<Item extends Codec<any, any>> implements Codec<List<Item['type']>, Codec.GetValue<Item>[]> {
  public readonly type: List<Item['type']>;
  constructor(public readonly item: Item)  {
    this.type = list(item.type);
  }

  public read(value: any): Codec.GetValue<Item>[] {
    return value.map((v: any) => this.item.read(v));
  }
}

Union is a bit more difficult because we need to map over a tuple of codecs to compute types and values.

First utility: Compute the Union Type from tuple of Codecs

type ComputeUnionType<V extends Codec<any, any>[]> = Union<Type[] & {
  [i in Extract<keyof V, number>]: V[i]['type']
}>;

Second utility: Compute the Union JS Type from a Tuple of Codecs:

type ComputeUnionValue<V extends Codec<any, any>[]> = {
  [i in Extract<keyof V, number>]: Codec.GetValue<V[i]>;
}[Extract<keyof V, number>];

Then we write a UnionCodec which recursively computes the Type and JS Type of a Union:

class UnionCodec<V extends Codec<any, any>[]> implements Codec<
  ComputeUnionType<V>,
  ComputeUnionValue<V>
> {
  public readonly type: ComputeUnionType<V>;

  constructor(public readonly codecs: V) {}
  public read(value: any): ComputeUnionValue<V> {
    throw new Error("Method not implemented.");
  }
}

Now your example type-checks:

const ic = new IntegerCodec();
const lc: ListCodec<IntegerCodec> = new ListCodec(new IntegerCodec());
const uc: UnionCodec<[ListCodec<IntegerCodec>, IntegerCodec]> = new UnionCodec([lc, ic]);

const listValue: number | number[] = uc.read('1');