Runtime type-checker that supports cyclic data structures

Typescript has only compile-time type-checking. To perform runtime type-checking we often use a library like zod, typebox or valibot. Although none of these libraries support cyclic data structures.

Let's take this example cyclic data structure:

        
interface User {
    books: Book[]
}

interface Book {
    user: User
}
        
        

The implementation in zod looks like this:

            
import * as z from 'zod'

const user = z.object({
  books: z.array(z.lazy(() => book))
})

const book = z.object({
  user,
})
            
        

But we encounter the following error message:

        
'user' implicitly has type 'any' because it does not have a type annotation and is referenced
directly or indirectly in its own initializer.(7022)
        
    

This is the same for typebox and valibot, I tested all of them.

Home-made type-checker

As I was searching for a solution, I discovered that it was easy to make my own type-checker supporting type inference.

We just need to create data structures that can then infer the correct type. Let's define these data structures:

        
const string = (): String => ({ $$type: 'string' })
const number = (): Number => ({ $$type: 'number' })
const boolean = (): Boolean => ({ $$type: 'boolean' })
const literal = <const V>(value: V): Literal<V> => ({ $$type: 'literal', value })

interface String {
    $$type: 'string'
}

interface Number {
    $$type: 'number'
}

interface Boolean {
    $$type: 'boolean'
}

interface Literal<V> {
    $$type: 'literal'
    value: V
}
        
    

Then we can build a utility type to perform inference:

        
type Infer<S> =
    S extends String ? string :
    S extends Number ? number :
    S extends Boolean ? boolean :
    S extends Literal<infer V> ? V :
    never

const a = string()
type A = Infer<typeof a> // infers string

const b = literal(2)
type B = Infer<typeof b> // infers 2
        
    

Let's add support for objects, arrays and lazy:

        
const object = <P>(properties: P): Object<P> => { $$type: 'object', properties }

const array = <I>(item: I): Array<I> => { $$type: 'array', item }

const lazy = <T>(value: T): Lazy<T> => { $$type: 'lazy', value }

interface Object<P> {
    $$type: 'object'
    properties: P
}

interface Array>I< {
    $$type: 'array'
    item: I
}

interface Lazy>T< {
    $$type: 'lazy'
    value: T
}

type Infer<S> =
    S extends String ? string :
    S extends Number ? number :
    S extends Boolean ? boolean :
    S extends Literal<infer V> ? V :
    // 
    S extends Array<infer I> ? Infer<I>[] :
    S extends Object<infer P> ? {[key in keyof P]: Infer<P>} :
    S extends Lazy<() => infer S> ? Infer<S> :
    never
        
    

Now let's see if it supports a cyclic data structure:

        
const user = object({
    books: array(lazy(() => book)),
})

const book = object({
    user,
})

type User = Infer<typeof user> // infers { books: Book[] }
type Book = Infer<typeof book> // infers { user: User }
        
    

It turns out it works perfectly! User and Book types are well inferred despite the structure being cyclic.

How is this possible? I believe that is because we haven't put any constraints on generics. As soon as we add constraints on generics the example above fails.

I guess zod, typebox and valibot all have constraints on generics for DX, at the expense of not supporting cyclic data structures.

Now we just need to implement the runtime validation by iterating on these structures and we're good.