Support for ZodLazy?

[markandrus]

Very cool project! I hope to use it, but I have a recursive schema using z.lazy. Is it possible to add support for this? I suppose the project would have to use fc.letrec or fc.memo.

[markandrus]

Inspired by this library, I have taken an approach using ts-morph to translate TypeScript types (rather, the subset of TypeScript types I depend on) to fast-check Arbitraries. The translation puts everything inside of an fc.letrec and uses tie wherever a recursive type appears. There is no type checking against the Zod schemas, although that could perhaps be combined…

In case anyone needs such a solution, here is a hacky script demonstrating the idea (with some choices specific to my application)

import { ArrayTypeNode, InterfaceDeclaration, Project, PropertySignature, SyntaxKind, TupleTypeNode, TypeAliasDeclaration, TypeLiteralNode, TypeNode, TypeReferenceNode, UnionTypeNode } from 'ts-morph'

const ifaces = new Set<string>()
const aliases = new Set<string>()

function handleInterfaceDeclaration(node: InterfaceDeclaration): void {
  const name = node.getName()
  if (ifaces.has(name)) throw new Error(`Duplicate interaface ${name}`)
  ifaces.add(name)

  if (node.getExtends().length > 0) throw new Error(`Unsupported extends on interface ${name}`)

  console.log(`  ${name}: fc.record({`)

  for (const member of node.getMembers()) {
    switch (member.getKind()) {
      case SyntaxKind.PropertySignature:
        console.log('    ' + handlePropertySignature(member.asKindOrThrow(SyntaxKind.PropertySignature)) + ',')
        continue
      default:
        throw new Error(`Unhandled kind: ${member.getKindName()}`)
    }
  }

  console.log(`  }),`)
}

function handlePropertySignature(node: PropertySignature): string {
  const name = node.getName()
  const typNode = node.getTypeNodeOrThrow()

  let fcExpr = handleTypeNode(typNode)

  if (node.getQuestionTokenNode() !== undefined) fcExpr = `fc.oneof(${fcExpr}, fc.constant(undefined))`

  return `${name}: ${fcExpr}`
}

function handleTypeNode(node: TypeNode): string {
  const fullText = node.getFullText().trim()

  switch (node.getKind()) {
    case SyntaxKind.ArrayType:
      return handleArrayType(node.asKindOrThrow(SyntaxKind.ArrayType))
    case SyntaxKind.BooleanKeyword:
      return 'fc.boolean()'
    case SyntaxKind.LiteralType:
      return `fc.constant(${fullText})`
    case SyntaxKind.NullKeyword:
      return 'fc.constant(null)'
    case SyntaxKind.NumberKeyword:
      return 'fc.oneof(fc.integer(), fc.float())'
    case SyntaxKind.StringKeyword:
      // return 'fc.stringOf(fc.constantFrom(\'a\', \'z\'), { minLength: 1 })'
      return "fc.asciiString({ minLength: 1 }).filter(_ => _.trim() !== '')"
    case SyntaxKind.TupleType:
      return handleTupleType(node.asKindOrThrow(SyntaxKind.TupleType))
    case SyntaxKind.TypeLiteral:
      return handleTypeLiteral(node.asKindOrThrow(SyntaxKind.TypeLiteral))
    case SyntaxKind.TypeReference:
      return handleTypeReference(node.asKindOrThrow(SyntaxKind.TypeReference))
    case SyntaxKind.UndefinedKeyword:
      return 'fc.constant(undefined)'
    case SyntaxKind.UnionType:
      return handleUnionType(node.asKindOrThrow(SyntaxKind.UnionType))
  }

  throw new Error(`Unsupported kind "${node.getKindName()}": ${fullText}`)
}

function handleArrayType(node: ArrayTypeNode): string {
  const elemTypNode = node.getElementTypeNode()
  return `fc.array(${handleTypeNode(elemTypNode)})`
}

function handleTupleType(node: TupleTypeNode): string {
  const elems = node.getElements()

  let fcExpr = 'fc.tuple('

  for (let i = 0; i < elems.length; i++) {
    if (i > 0) fcExpr += ', '
    if (elems[i].getKind() === SyntaxKind.NamedTupleMember) {
      fcExpr += handleTypeNode(elems[i].asKindOrThrow(SyntaxKind.NamedTupleMember).getTypeNode())
    } else {
      fcExpr += handleTypeNode(elems[i])
    }
  }

  return fcExpr + ')'
}

function handleTypeLiteral(node: TypeLiteralNode): string {
  let fcExpr = `fc.record({ `

  const members = node.getMembers()
  for (let i = 0; i < members.length; i++) {
    if (i > 0) fcExpr += ', '
    switch (members[i].getKind()) {
      case SyntaxKind.PropertySignature:
        fcExpr += handlePropertySignature(members[i].asKindOrThrow(SyntaxKind.PropertySignature))
        continue
      default:
        throw new Error(`Unhandled kind: ${members[i].getKindName()}`)
    }
  }

  return fcExpr + ` })`
}

function handleTypeReference(node: TypeReferenceNode): string {
  const typName = node.getTypeName().getFullText().trim()

  switch (typName) {
    case 'Array': {
      const typArgs = node.getTypeArguments()
      if (typArgs.length !== 1) throw new Error('Expected exactly one type argument to Array')
      return `fc.array(${handleTypeNode(typArgs[0])})`
    }
    case 'NonEmptyArray': {
      const typArgs = node.getTypeArguments()
      if (typArgs.length !== 1) throw new Error('Expected exactly one type argument to NonEmptyArray')
      return `fc.array(${handleTypeNode(typArgs[0])}, { minLength: 1 })`
    }
    default:
      // HACK(mroberts): We just expect anything else is a recursive type.
      return `tie(${JSON.stringify(typName)})`
  }
}

function handleUnionType(node: UnionTypeNode): string {
  const elems = node.getTypeNodes()

  let fcExpr = 'fc.oneof('

  for (let i = 0; i < elems.length; i++) {
    if (i > 0) fcExpr += ', '
    fcExpr += handleTypeNode(elems[i])
  }

  return fcExpr + ')'
}

function handleTypeAliasDeclaration(node: TypeAliasDeclaration): void {
  const name = node.getName()
  if (aliases.has(name)) throw new Error(`Duplicate type alias ${name}`)
  aliases.add(name)

  if (name === 'NonEmptyArray') return

  if (node.getTypeParameters().length > 0) throw new Error(`Unsupported type parameters on type alias ${name}`)

  const typNode = node.getTypeNodeOrThrow()

  console.log('  ' + name + ': ' + handleTypeNode(typNode) + ',')
}

// ---

const project = new Project()

const srcFile = project.addSourceFileAtPath('src/ast/index.ts')

console.log(`import fc from 'fast-check'

export const arb = fc.letrec(tie => ({`)

for (const node of srcFile.getChildSyntaxListOrThrow().getChildren()) {
  switch (node.getKind()) {
    case SyntaxKind.InterfaceDeclaration:
      handleInterfaceDeclaration(node.asKindOrThrow(SyntaxKind.InterfaceDeclaration))
      continue
    case SyntaxKind.TypeAliasDeclaration:
      handleTypeAliasDeclaration(node.asKindOrThrow(SyntaxKind.TypeAliasDeclaration))
      continue
    case SyntaxKind.MultiLineCommentTrivia:
    case SyntaxKind.SingleLineCommentTrivia:
      continue
    default:
      throw new Error(`Unhandled kind: ${node.getKindName()}`)
  }
}

console.log(`}))`)

[DavidTimms]

Hi Mark. Thanks for the kind words.

I think I'd rather avoid every generated arbitrary being wrapped in fc.letrec. In theory, an implementation based on fc.memo should be possible. I anticipate that stopping it from generating infinite structures will a challenge though, which might require solving the halting problem 😄

I'll leave this issue open and have a go at implementing it when I next get an opportunity to work on this lib.

[markandrus]

I anticipate that stopping it from generating infinite structures will a challenge though, which might require solving the halting problem 😄

Yes! In fact I ran into this today and needed to reorder fc.oneof entries so that the first one wasn't recursive: dubzzz/fast-check#5218

I'll leave this issue open and have a go at implementing it when I next get an opportunity to work on this lib.

GL, and I'll be happy to try it out later 🙏