Stack overflow when using deepEqual() on mutually recursive Zod schemas (infinite traversal of z.lazy graph)

[szalapi]

Hey,
Great work on this tool! I wanted to give it a try (deepEqual especially), but with our deeply nested schema it resulted in stack overflow. Error description below:

Calling a deepEqual on a large, mutually recursive object schemas results in RangeError: Maximum call stack size exceeded.
Seems like the walker expands every z.lazy reference and re-enters previously seen schema nodes without effective cycle termination, causing recursion.

[ahrjarrett]

Hey @szalapi, thank you for reporting this.

I'll be able to take a look at this later today.

Would you mind sharing the schema (or a simplified version of it) that's causing the Stack Overflow, so I can write a regression test if/when it gets fixed?

[szalapi]

Thanks for looking into it so quickly :)

Here is a sample one that behaves the same way:

const PersonSchema = z.lazy(() =>
  z.object({
    id: z.number(),
    name: z.string(),
    manager: PersonSchema.optional(),         // self recursion
    teams: z.array(TeamSchema).optional(),    // mutual recursion
  })
)

const TeamSchema = z.lazy(() =>
  z.object({
    id: z.number(),
    label: z.string(),
    members: z.array(PersonSchema).optional(),  // back to Person
    parent: TeamSchema.optional(),              // self recursion
  })
)

const mapA = {
  1: { id: 1, name: 'Alice', manager: undefined, teams: [] },
}

const mapB = {
  1: { id: 1, name: 'Alice', manager: undefined, teams: [] },
}

const personEqual = deepEqual(PersonSchema)
personEqual(mapA, mapB) // -> RangeError: Maximum call stack size exceeded

I've verified it and it also ends up with the same error.

[ahrjarrett]

I haven't forgotten about this, got busy with work stuff. I've been kicking around a couple different ideas, will hopefully have an update for you later tonight

[ahrjarrett]

Repro

[szalapi]

Thanks for looking into it, @ahrjarrett!

Not sure if you've considered, but maybe storing visited schemas for lazy tagged could be one way to go (not sure how about the perf there, though).

[ahrjarrett]

@szalapi that's a good idea. I hadn't really thought about treating z.lazy specially, but that might be a way to make this performant – if we only have to store z.lazy schemas rather than every schema, it might not consume as much memory.

The other part I'm thinking about though is how to generate the string. The way deepEqual works is by building up a string, and passing it into the Function constructor.

I think I have an idea how it could work, but a few details are still fuzzy to me. I was hoping the recursive example here might work?