Recursive Types

If you want a schema to be able to contain itself (recursion), reference it from inside a getter. TypeScript infers the types of getters lazily, which allows the schema’s type to refer to itself:

import * as bin from 'typed-binary';

const LinkedList = bin.struct({
  value: bin.i32,
  get next() {
    return bin.optional(LinkedList);
  },
});

type LinkedList = bin.ExtractOut<typeof LinkedList>;
//   ^? { value: number, next: LinkedList | undefined }

Recursive schemas can nest arbitrarily deep, so their maximum size is unbounded. LinkedList.maxSize is NaN, and LinkedList.measure(value) should be used to measure concrete values instead.

Recursive tagged unions

Variants of a bin.union can reference the union through getters too:

import * as bin from 'typed-binary';

const Expression = bin.union(bin.orderedEnum('int_literal', 'negate', 'multiply'), {
  int_literal: { value: bin.i32 },
  negate: {
    get inner() {
      return Expression;
    },
  },
  multiply: {
    get a() {
      return Expression;
    },
    get b() {
      return Expression;
    },
  },
});

type Expression = bin.ExtractOut<typeof Expression>;

const expr: Expression = {
  type: 'multiply',
  a: { type: 'negate', inner: { type: 'int_literal', value: 15 } },
  b: { type: 'int_literal', value: 2 },
};

Recursion through `bin.pipe`

bin.pipe reads a schema (the head), then decides on the schema of the rest of the data based on its value. It’s lower-level than bin.union, but more flexible. There are two ways to make it recursive.

Variants as separate schemas

Each variant is defined as its own schema, and references the union through getters. The bin.pipe action then only has to pick the right variant:

import * as bin from 'typed-binary';

const IntLiteral = bin.struct({
  type: bin.inherent('int_literal'),
  value: bin.i32,
});

const Negate = bin.struct({
  type: bin.inherent('negate'),
  get inner() {
    return Expression;
  },
});

const Multiply = bin.struct({
  type: bin.inherent('multiply'),
  get a() {
    return Expression;
  },
  get b() {
    return Expression;
  },
});

const Expression = bin.pipe(
  bin.struct({ type: bin.orderedEnum('int_literal', 'negate', 'multiply') }),
  (head) => {
    if (head === bin.MaxValue) {
      // Measuring the max size, any variant will do, as the
      // max size of recursive schemas is unbounded anyway.
      return Multiply;
    }

    switch (head.type) {
      case 'int_literal':
        return IntLiteral;
      case 'negate':
        return Negate;
      case 'multiply':
        return Multiply;
    }
  },
);

type Expression = bin.ExtractOut<typeof Expression>;

const expr: Expression = {
  type: 'multiply',
  a: { type: 'negate', inner: { type: 'int_literal', value: 15 } },
  b: { type: 'int_literal', value: 2 },
};

bin.inherent(value) describes a value that takes up no space, because it is already known. Here, the type was already read as part of the head, so the variants only carry it over to the output.

Variants inside the action

For smaller unions, the variants can be created inside the action itself, as long as the recursive references stay inside getters:

const Expression = bin.pipe(
  bin.struct({ type: bin.orderedEnum('int_literal', 'negate') }),
  (head) =>
    head !== bin.MaxValue && head.type === 'int_literal'
      ? bin.struct({ type: bin.inherent('int_literal'), value: bin.i32 })
      : bin.struct({
          type: bin.inherent('negate'),
          get inner() {
            return Expression;
          },
        }),
);