Recursive schemas

[james-tindal]

Creating recursive schemas is limited by the need to manually define the type and lose the reliable type-to-value correspondence usually provided by valibot. Our best option at the moment is defining a non-recursive schema and then adding the recursion using lazy and intersection/union/tuple.

We can do better than this, but it would require adding a few bytes to existing operators.

Here's a type that creates recursive types:

const Recur = Symbol('Recur')
type Recur = typeof Recur

type Recursive<RootDesc, SubDesc = RootDesc> = {
  [K in keyof SubDesc]:
    SubDesc[K] extends undefined
      ? undefined :
    SubDesc[K] extends Recur | undefined
      ? Recursive<RootDesc>
      : Recursive<RootDesc, SubDesc[K]>
}

Here are tests that show TreeA = TreeB: Typescript Playground

type TreeA = {
  value: string
  children?: TreeA[]
}

type TreeB = Recursive<{
  value: string
  children?: Recur[]
}>

New operator

Requirements:
There would be an extension of the usual Schema type to also allow the Recur symbol anywhere. Many operators would need to accept this type as input and output. This should be a minor runtime change. Possibly:

if (dataset.value == Recur) return Recur

parse() would not accept this type. recursive() would replace all instances of the symbol with recursion.
parse should be otherwise unchanged, since it's already capable of parsing recursive schemas.

This would allow us the usual composition API.

Usage

const author = pipe(
  object({ 'dc:creator': string() }),
  transform(x => ({ author: x['dc:creator'] }))
)

const children = pipe(
  object({
    spine: object({
      itemref: pipe(
        object({ '@idref': optional(array(Recur)) }),          //  <---  Recur
        transform(x => x['@idref']),
      ),
    }),
  }),
  transform(x => ({ children: x.spine.itemref }))
)

const recursiveSchema = recursive(intersect([author, children]))

// inferred types
type Input = {
  'dc:creator': string
  spine: {
    itemref: {
      '@idref'?: Input[]
    }
  }
}
type Output = {
  author: string
  children?: Output[]
}

Limitation

The Recur symbol must be inside an object, not only a tuple.

Details

This is fine:

type List<T> = [T] | [T, List<T>]

But this doesn't work:

type List<T> = Recursive<[T] | [T, Recur]>

But this does work:

type List<T> = Recursive<{ head: T } | { head: T, tail: Recur }>

Solution

type List<T> = Recursive<[T] | { 0: T, 1: Recur }>

Test here

This could probably built in to Recursive<T>.

[fabian-hiller]

Hey 👋 thank you for creating this issue! I agree, we should fix our recursive type handling. I looked into it a few months ago but couldn't figure it out. What do you think about the way Zod resolved recursive objects? https://zod.dev/v4#recursive-objects

[james-tindal]

Zod's thing is neat. No idea how they got that to work. Maybe the secret is here.
That solves mutual reference/recursion, which mine doesn't.

Zod's solution only allows recursion within the arguments to a single object() call. My proposal (in theory) allows the full flexibility of operator composition by delaying recursion until after defining recursion sites.

Zod's approach is less flexible (playground):

const Category = z.object({
  name: z.string(),
  get subcategories(){
    return z.array(Category)
  }
})
// ^ All good so far
.transform(x => x)
// ^ Type of property 'subcategories' circularly references itself in mapped type

There are various other not insurmountable issues in Zod's Github issues.

Proposed alternative:

const subcategories = v.array(Recur)

const Category = v.pipe(
  v.recursive(
    v.object({
      name: v.string(),
      subcategories
    })
  ),
  v.transform(x => x)
)

const Category = v.recursive(
  v.pipe(
    v.object({
      name: v.string(),
      subcategories
    }),
    v.transform(x => x)
  )
)

The getter approach seems the only way to solve mutual recursion, but maybe lazy() could do that too somehow.

If lazy could work based on the same magic as Zod's getters, strikes me as more intuitive:

const R = object({
  get foo() {
    return optional(array(R))
  }
})

vs

const R = object({
  foo: optional(array(lazy(() => R)))
})

[fabian-hiller]

Sorry for the late reply, and thank you for the additional context. Does the Recur approach have any downsides? Do you think the current type issue of lazy or a getter can be reliably solved, or does Recur always have an advantage here?

[james-tindal]

Recur downsides

The main downside of Recur is people may find it counter-intuitive:

In this example, Category is not a recursive schema. It's not even a schema. It must be passed to v.recursive which turns it into a recursive schema. This is just a description of a recursive schema.

const Category = 
  v.object({
    name: v.string(),
    subcategories: v.array(Recur)
  })

This is a recursive schema:

const Category = v.recursive(
  v.object({
    name: v.string(),
    subcategories: v.array(Recur)
  })
)

But this also allows this approach to be much more flexible. With getters, you have to do everything in one go, in one statement. Using Recur allows you to compose schemas together like you currently can with all valibot methods. Using getters locks this down to everything having to happen within a single object() parameter object.

[james-tindal]

Revealing the magic trick

How to make getters work:

playground

const object = <Entries extends object>(entries: Entries) => ({ entries })

const b = object({
  get c() { return b }
})

b.entries.c.entries.c.entries.c   // 👍

You must not restrict the type of object values.
You can restrict the keys only:

type Restricted = Partial<Record<'foo' | 'bar' | 'baz', unknown>>
const object = <Entries extends Restricted>(entries: Entries) => ({ entries })

This is how Zod works. (playground)

Proof of concept

https://tsplay.dev/m0rLDw

Even in this simplified form, typescript is giving up on recursion with transformation.
pipe() is just function composition and schemas and transformations are both just functions.

const schema1 = pipe(
  object({
    foo: number(),
    get bar() { return array(schema1) },
  }),
  x => x          // ✅
)

const schema2 = pipe(
  object({
    foo: number(),
    get bar() { return array(schema2) },
  }),
  x => ({ ...x }) // ❌
)

While the getters might not be perfect, there's little reason not to enable them since no runtime code is changed.

recursive object schemas can be transformed

I didn't mean to imply getter recursive schemas can't be transformed.

They can be transformed like this:

const Category = z.object({
  name: z.string(),
  get subcategories(){
    return z.array(Category)
  }
})

const Category2 = Category.transform(x => x)

You just can't write the object schema and the transform in one statement.

[james-tindal]

recursive type inference for lazy()

In order to have typescript infer recursion using lazy():

1. The same requirement as for getters. The entries argument to v.object() must have no narrower restriction than extends object.

2. ...

• v.lazy()'s argument must have no narrower restriction than extends () => any.
• What lazy() returns must not be a subtype of Schema, but a subtype of () => Schema
• () => Schema must remain visible in hover hints. It must always remain a thunk at type level.
  • So the least noisy option is to have hover hints look like this: () => ObjectSchema<...>. The more explicit option is Lazy<() => ObjectSchema<...>>.
• Any function that derives a schema from a schema (array, email, etc.) must put no restriction on the schema parameter, and must handle both cases at runtime:

if (isSchema(arg))
  arg['~run'](input)
if (isLazySchema(arg))
  arg()['~run'](input)

Possibly there would be some way of lying to the type system and having LazySchema be a subtype of Schema at runtime.

Here's a validator with recursive inference for lazy(): https://tsplay.dev/mZAaDN

const schema = object({
  c: array(lazy(() => schema)),
  d: literal(1),
})
const input: unknown = null
const result = schema.run(input)

result.c[0].c[0].c[0].c[0].d       // ✅

[fabian-hiller]

I like v.recursive. Would it still be your preference over v.lazy or a getter? Not sure if I am wrong but it seems like if we design the API like v.recursive((child) => …) we could allow the user to nest multiple v.recursive calls and still refer to the correct children. If we choose v.recursive we might also have the benefit that this function does not only resolves the type but also handles the recursive parsing at run time, which would be great for a modular library like Valibot. What do you think? @dosu please also share your opinion but keep it short.

[dosubot]

Yes, I’d still prefer a v.recursive((child) => ...) API over v.lazy or getter-based recursion for Valibot. This style is more modular and composable—it lets you nest recursive calls, refer to the correct children, and encapsulate both type resolution and runtime parsing in one place, which fits Valibot’s design goals well. Getter-based recursion (like Zod) is less flexible for composition and transformation chaining, and v.lazy (which is functionally similar to v.recursive) requires explicit type annotations due to TypeScript limitations, but doesn’t offer extra ergonomic benefits over a well-designed v.recursive API. Community and maintainer feedback also supports this direction for clarity and modularity [source][source][source].

To reply, just mention @dosu.

---

Docs are dead. Just use Dosu.

[james-tindal]

Yeah I still think v.recursive is the best option. I'll have to make a working proof of concept and then we can see how different options play out.

[fabian-hiller]

Are you interested in working on a PR?