How do I generate a recursive structure with reused objects?

[TomerAberbach]

I've been using fc.letrec to generate recursive structures, which is working well, but I'm wondering how I can generate a recursive object where sometimes objects are reused, and where sometimes those reuses are also circular.

Example non-circular reuse:

const obj1 = { a: 2 };
const obj2 = { a: obj1, b: obj1 }; // obj1 used twice

Example circular reuse:

const obj1 = { a: 2 };
const obj2 = { a: 1, b: obj1 };
obj1.b = obj2; // obj1 and obj2 reference each other

[gruhn]

Yeah, I think everything that's not an "inductive datatype" (aka. tree-like) is gonna be annoying to generate. Objects with circular references are graph-like. One thing you could do is generate random IDs instead of object references directly. And then you replace those IDs with actual objects in a second pass.

Unfortunately, I think the only way to produce a circular reference is with mutation. And mutation breaks shrinking, I think.

Can you maybe give more details on your use case? Maybe there is something else we can do.

[TomerAberbach]

I have seen fc.cloneIfNeeded around, but not sure what it's for. Is it useful for this mutation problem you mentioned?

[gruhn]

I'm writing some code that processes JSON schemas derived from OpenAPI specs

I'm not particularly familiar with either but ...

Before this processing part we resolve $ref properties to the actual schema objects. This can create recursive schemas, where there are circular object references

This sounds similar to what I've suggested, right? Those $ref properties presumably are some kind of ID, right? And they are replaced with proper objects. Is it an option to generate the objects which still contain the $ref part and make your resolve logic part of the test?

I have seen fc.cloneIfNeeded around, but not sure what it's for. Is it useful for this mutation problem you mentioned?

Not sure about that one in particular but yeah now I remember: if you deep clone objects generated by fast-check before mutating them, then shrinking is not affected.

[TomerAberbach]

Okay, so, I was struggling with this so I decided to implement a toy example, which I was able to get working:

import * as fc from 'fast-check'
import { inspect } from 'node:util'

type NodeOrId =
  | { type: 'node'; value: number; left?: NodeOrId; right?: NodeOrId }
  | { type: 'id'; value: number }

type Node = {
  value: number
  left?: Node
  right?: Node
}

const graphArb = fc.nat({ max: 5 }).chain(refCount => {
  const { nodeArb, nodeOrIdArb } = fc.letrec<{
    idArb: NodeOrId & { type: 'id' }
    nodeArb: NodeOrId & { type: 'node' }
    nodeOrIdArb: NodeOrId
  }>(tie => ({
    idArb: fc.record({
      type: fc.constant('id'),
      value: fc.nat({ max: Math.max(0, refCount - 1) }),
    }),
    nodeArb: fc.record({
      type: fc.constant('node'),
      value: fc.integer(),
      left: fc.option(tie('nodeOrIdArb'), { nil: undefined }),
      right: fc.option(tie('nodeOrIdArb'), { nil: undefined }),
    }),
    nodeOrIdArb: fc.oneof(
      tie('nodeArb'),
      ...(refCount === 0 ? [] : [tie('idArb')]),
    ),
  }))
  const nodeRefsArb = fc.array(nodeArb, {
    minLength: refCount,
    maxLength: refCount,
  })
  return fc
    .tuple(nodeOrIdArb, nodeRefsArb)
    .map(([rootNodeOrId, nodeRefs]) => deref(rootNodeOrId, nodeRefs))
})

const deref = (nodeOrId: NodeOrId, nodeRefs: NodeOrId[]): Node => {
  let cached = derefCache.get(nodeOrId)
  if (cached) {
    return cached
  }

  switch (nodeOrId.type) {
    case 'id':
      return deref(nodeRefs[nodeOrId.value]!, nodeRefs)
    case 'node': {
      // Set the new node on the cache now to avoid infinite recursion.
      cached = {} as Node
      derefCache.set(nodeOrId, cached)
      Object.assign(cached, {
        value: nodeOrId.value,
        ...(nodeOrId.left ? { left: deref(nodeOrId.left, nodeRefs) } : {}),
        ...(nodeOrId.right ? { right: deref(nodeOrId.right, nodeRefs) } : {}),
      })
      return cached
    }
  }
}
const derefCache = new WeakMap<NodeOrId, Node>()

const circularGraphArb = graphArb.filter(graph => {
  let count = 0
  const visited = new WeakSet()
  const stack = [graph]
  do {
    const node = stack.pop()!
    if (visited.has(node)) {
      count++
      continue
    }
    visited.add(node)

    if (node.left) {
      stack.push(node.left)
    }
    if (node.right) {
      stack.push(node.right)
    }
  } while (stack.length > 0)

  return count >= 4
})

for (const graph of fc.sample(circularGraphArb, 4)) {
  console.log(inspect(graph, { depth: Infinity }))
}

Here's an example this printed out:

{
  value: 28,
  left: {
    value: -525472813,
    left: {
      value: -1944989553,
      left: {
        value: 2147483634,
        left: <ref *1> {
          value: 12,
          left: {
            value: -2147483620,
            right: {
              value: 2147483645,
              left: {
                value: 722036063,
                left: {
                  value: 1238819036,
                  right: {
                    value: -477336740,
                    right: {
                      value: 16,
                      right: {
                        value: 24,
                        left: { value: 1705220184 },
                        right: {
                          value: -8250968,
                          left: {
                            value: -651315135,
                            left: { value: -1618205423 }
                          }
                        }
                      }
                    }
                  }
                },
                right: {
                  value: -6,
                  left: { value: -4, right: { value: 27 } }
                }
              },
              right: {
                value: 1737635832,
                left: {
                  value: -24,
                  left: <ref *2> {
                    value: 2088903436,
                    left: [Circular *1],
                    right: [Circular *2]
                  }
                },
                right: [Circular *1]
              }
            }
          },
          right: [Circular *1]
        }
      },
      right: {
        value: 1693125779,
        right: {
          value: -443166795,
          left: <ref *2> {
            value: 2088903436,
            left: <ref *1> {
              value: 12,
              left: {
                value: -2147483620,
                right: {
                  value: 2147483645,
                  left: {
                    value: 722036063,
                    left: {
                      value: 1238819036,
                      right: {
                        value: -477336740,
                        right: {
                          value: 16,
                          right: {
                            value: 24,
                            left: { value: 1705220184 },
                            right: {
                              value: -8250968,
                              left: {
                                value: -651315135,
                                left: { value: -1618205423 }
                              }
                            }
                          }
                        }
                      }
                    },
                    right: {
                      value: -6,
                      left: { value: -4, right: { value: 27 } }
                    }
                  },
                  right: {
                    value: 1737635832,
                    left: { value: -24, left: [Circular *2] },
                    right: [Circular *1]
                  }
                }
              },
              right: [Circular *1]
            },
            right: [Circular *2]
          }
        }
      }
    },
    right: {
      value: 2147483626,
      left: {
        value: -2147483629,
        left: <ref *3> {
          value: -2147483620,
          right: {
            value: 2147483645,
            left: {
              value: 722036063,
              left: {
                value: 1238819036,
                right: {
                  value: -477336740,
                  right: {
                    value: 16,
                    right: {
                      value: 24,
                      left: { value: 1705220184 },
                      right: {
                        value: -8250968,
                        left: {
                          value: -651315135,
                          left: { value: -1618205423 }
                        }
                      }
                    }
                  }
                }
              },
              right: { value: -6, left: { value: -4, right: { value: 27 } } }
            },
            right: {
              value: 1737635832,
              left: {
                value: -24,
                left: <ref *2> {
                  value: 2088903436,
                  left: <ref *1> {
                    value: 12,
                    left: [Circular *3],
                    right: [Circular *1]
                  },
                  right: [Circular *2]
                }
              },
              right: <ref *1> {
                value: 12,
                left: [Circular *3],
                right: [Circular *1]
              }
            }
          }
        }
      },
      right: <ref *2> {
        value: 2088903436,
        left: <ref *1> {
          value: 12,
          left: <ref *3> {
            value: -2147483620,
            right: {
              value: 2147483645,
              left: {
                value: 722036063,
                left: {
                  value: 1238819036,
                  right: {
                    value: -477336740,
                    right: {
                      value: 16,
                      right: {
                        value: 24,
                        left: { value: 1705220184 },
                        right: {
                          value: -8250968,
                          left: {
                            value: -651315135,
                            left: { value: -1618205423 }
                          }
                        }
                      }
                    }
                  }
                },
                right: {
                  value: -6,
                  left: { value: -4, right: { value: 27 } }
                }
              },
              right: {
                value: 1737635832,
                left: { value: -24, left: [Circular *2] },
                right: [Circular *1]
              }
            }
          },
          right: [Circular *1]
        },
        right: [Circular *2]
      }
    }
  },
  right: {
    value: -2142937012,
    left: {
      value: 1185936645,
      left: <ref *2> {
        value: 2088903436,
        left: <ref *1> {
          value: 12,
          left: <ref *3> {
            value: -2147483620,
            right: {
              value: 2147483645,
              left: {
                value: 722036063,
                left: {
                  value: 1238819036,
                  right: {
                    value: -477336740,
                    right: {
                      value: 16,
                      right: {
                        value: 24,
                        left: { value: 1705220184 },
                        right: {
                          value: -8250968,
                          left: {
                            value: -651315135,
                            left: { value: -1618205423 }
                          }
                        }
                      }
                    }
                  }
                },
                right: {
                  value: -6,
                  left: { value: -4, right: { value: 27 } }
                }
              },
              right: {
                value: 1737635832,
                left: { value: -24, left: [Circular *2] },
                right: [Circular *1]
              }
            }
          },
          right: [Circular *1]
        },
        right: [Circular *2]
      },
      right: {
        value: 11,
        left: {
          value: -562337528,
          left: {
            value: 623640025,
            right: {
              value: 2147483619,
              left: { value: 297231294, right: { value: 16 } }
            }
          }
        }
      }
    },
    right: <ref *1> {
      value: 12,
      left: <ref *3> {
        value: -2147483620,
        right: {
          value: 2147483645,
          left: {
            value: 722036063,
            left: {
              value: 1238819036,
              right: {
                value: -477336740,
                right: {
                  value: 16,
                  right: {
                    value: 24,
                    left: { value: 1705220184 },
                    right: {
                      value: -8250968,
                      left: {
                        value: -651315135,
                        left: { value: -1618205423 }
                      }
                    }
                  }
                }
              }
            },
            right: { value: -6, left: { value: -4, right: { value: 27 } } }
          },
          right: {
            value: 1737635832,
            left: {
              value: -24,
              left: <ref *2> {
                value: 2088903436,
                left: [Circular *1],
                right: [Circular *2]
              }
            },
            right: [Circular *1]
          }
        }
      },
      right: [Circular *1]
    }
  }
}

Seems pretty legit! Maybe makes sense to include this as an example somewhere, if we think this is the "right way" to do it. cc @dubzzz

[dubzzz]

I could suggest several options:

• a snippet in examples/
• an example in the documentation of letrec
• a blog post with the whole story of this snippet and how you finally reached it and why

I'd rather go for 1 or 3.

[gruhn]

Nice! I think we could even drop letrec at this point and handle all links over the node IDs. And I think we can also avoid fc.nat({ max: 5 }).chain(refCount => .... chain is worse at shrinking. E.g. like this:

import * as fc from 'fast-check'
import { inspect } from 'node:util'

type NodeWithRefs = {
  value: number
  left?: NodeWithRefs | number
  right?: NodeWithRefs | number
}

type Node = {
  value: number
  left?: Node
  right?: Node
}

const circularGraphArb = (maxRef: number): fc.Arbitrary<Node> => {
  const refArb = fc.nat({ max: maxRef })

  const nodeArb: fc.Arbitrary<NodeWithRefs> = fc.record({
    type: fc.constant('node'),
    value: fc.integer(),
    left: fc.option(refArb, { nil: undefined }),
    right: fc.option(refArb, { nil: undefined }),
  })

  // Generate a flat list of nodes in the graph. A nodes own ID is determined by the index in the array:
  const nodeListArb = fc.array(nodeArb, {
    // We need to generate at least as many nodes as the maximum ID, otherwise we might get an ID which 
    // has no corresponding node:
    minLength: maxRef
  });

  return nodeListArb.map(nodeList => {
    // Make a deep copy of the node list because we're about to mutate it and that otherwise
    // breaks shrinking:
    const nodeListCopy = JSON.parse(JSON.stringify(nodeList)) as NodeWithRefs[]

    // Now dereference left and right by replacing the ID with the actual node object:
    for (const node of nodeListCopy) {
      // At this point `node.left` and `node.right` should always be IDs and not objects yet:
      if (node.left !== undefined) {
        node.left = nodeListCopy[node.left as number]
      }
      if (node.right !== undefined) {
        node.right = nodeListCopy[node.right as number]
      }
    }

    // At this point all refs should be eliminated:
    const nodesDerefed = nodeListCopy as Node[]

    // Now it's a bit arbitrary which node should be the root node. For example, if there are two 
    // nodes referencing each other then both could be the root: 
    // 
    //             A <-> B
    //
    // But some nodes can definitely never be the root node if they can't "reach" all other nodes like C here:
    //    
    //              A <-> B -> C
    // 
    // So we'll need to filter those nodes out and pick one of the root node candidates (here A or B):
    return pickRootNode(nodesDerefed)
  })
}

const pickRootNode = (nodes: Node[]): Node => {
  if (nodes.length === 0) {
    throw new Error('cant pick root node from empty array')
  }
  
  // start with all nodes being root-node-candidates:
  const candidates = new Set<Node>(nodes);
  let candidatesChangedLastIteration = true;

  const isDeadEnd = (node: Node | undefined) => {
    return node === undefined || !candidates.has(node)
  }

  // iteratively filter out nodes that are "dead ends":
  while (candidatesChangedLastIteration) {
    candidatesChangedLastIteration = false;

    for (const node of candidates) {
      if (isDeadEnd(node.left) && isDeadEnd(node.right)) {
        candidates.delete(node);
        candidatesChangedLastIteration = true;
      }
    }
  }

  // This shouldn't happen:
  if (candidates.size === 0) {
    throw new Error('logic error: couldnt any root node')
  }

  // But candidates can be >1. Either because the graph is circular:
  // 
  //       A <-> B
  //
  // Or because there are disconnected "islands" of nodes:
  //
  //       A -> B        C -> D
  //
  // Maybe something more clever is possible here, but just pick the
  // first candidate works:
  return candidates.values().next().value
}

for (const graph of fc.sample(circularGraphArb(10), 4)) {
  console.log(inspect(graph, { depth: Infinity }))
}

[ahrjarrett]

I'd also be interested in figuring out a clean way to do this.

I've worked on an OpenAPI (v3) arbitrary that generates arbitrary OpenAPI documents, and I had to use a bunch of hacks to get the document to be "self-referencing".

Here's the code for that (although it's not nearly as elegant as @gruhn's ideas).

It also uses chaining to get the job done, which is a less than ideal.

Would be curious to hear if anyone else has attempted this kind of thing, since it would be great to shrinkable arbitrary (although I'm not sure it's possible).

[TomerAberbach]

I'm actually working on one here :)

#6040

[dubzzz]

@TomerAberbach did propose an awesome option in #6040 for letrec, unfortunately it comes with too many gotchas to keep it. Most of the issues are linked to the fact that we don't really control how the outputs of tie will be used.

As such I came up with an alternate options that will have to be refine but that will allow our users to provide fast-check with a schema of the entities they want and the links they have between each others. The proposed API is visible on #6333. So far many features are missing: reverse-links, ability to constrain links so that they can be exclusive or only refer to next entries to avoid cycles or any other ideas that could make a strategy, shrinking...

[TomerAberbach]

This looks amazing!!! Thanks for cleaning up my code lol