Recursive Schema Refs That Stall PBT Generators

Property-based testing stalls aren't always a Hypothesis bug or a slow strategy — sometimes the generator just never returns. You kick off a @given suite, the process pins a CPU core, and twenty minutes later you kill it. The culprit is usually a recursive $ref in your JSON Schema: a TreeNode that references itself, a Comment that embeds a list of Comments, or a medical record schema where Encounter nests Encounter as a sub-encounter. Hypothesis's from_schema() and Schemathesis both try to fully resolve the reference graph before drawing values, and an unbounded cycle means infinite expansion.

This article is specifically about property-based validation in Python — the failure mode where recursive schemas silently hang data generation, and how to fix it without neutering your schema's expressiveness. By the end you'll have concrete techniques for bounding recursion depth, detecting cycles at schema-load time, and writing reproducible data pipeline validation that doesn't fall apart on self-referential structures.

Why Recursive $ref Cycles Break Property-Based Data Validation

JSON Schema 2020-12 allows a schema to reference itself via $ref or $defs, which is the correct way to model recursive data structures. The problem isn't the schema — it's that most property-based generators are eager: they attempt to construct a concrete value by fully expanding every reference before returning anything. When the reference graph has a cycle with no mandatory base case (i.e., no if/then branch or minItems: 0 that short-circuits expansion), the generator recurses indefinitely. Hypothesis's hypothesis-jsonschema and Schemathesis's internal resolver both exhibit this behaviour on unbounded cycles.

This sits at the intersection of property-based testing for data validation and schema design: the schema is technically valid, the tooling is technically correct, and the result is a hung process. It's not a flaky test — it's a structural incompatibility between eager generation strategies and schemas that have no guaranteed finite expansion path. Understanding that distinction is what separates a targeted fix from a workaround that breaks coverage.

Bounding Recursion: Detection, Depth Limits, and Reproducible Generation

The first step is detecting cycles at schema-load time rather than at generation time. A depth-first traversal of the $defs graph catches the problem before Hypothesis ever sees it:

import json, sys
from pathlib import Path

def find_cycles(schema: dict, defs_key: str = "$defs") -> list[list[str]]:
    defs = schema.get(defs_key, {})
    graph: dict[str, set[str]] = {k: set() for k in defs}

    def collect_refs(node, target_set):
        if isinstance(node, dict):
            if "$ref" in node:
                ref = node["$ref"]
                name = ref.split("/")[-1]
                if name in defs:
                    target_set.add(name)
            for v in node.values():
                collect_refs(v, target_set)
        elif isinstance(node, list):
            for item in node:
                collect_refs(item, target_set)

    for name, subschema in defs.items():
        collect_refs(subschema, graph[name])

    cycles = []
    visited, stack = set(), []

    def dfs(node):
        visited.add(node); stack.append(node)
        for neighbour in graph.get(node, []):
            if neighbour not in visited:
                dfs(neighbour)
            elif neighbour in stack:
                cycle_start = stack.index(neighbour)
                cycles.append(stack[cycle_start:])
        stack.pop()

    for node in list(graph):
        if node not in visited:
            dfs(node)
    return cycles

schema = json.loads(Path("comment.schema.json").read_text())
print(find_cycles(schema))  # [['Comment', 'Comment']] → unbounded self-ref

Run this in CI as a schema lint step. A cycle isn't automatically a bug, but an unguarded one is. The fix is to add an explicit base case that gives the generator a finite exit: set minItems: 0 on any array that holds recursive items, or wrap the recursive branch in an if that resolves to a leaf type at depth zero. For generating test data from JSON Schema with Hypothesis, the max_examples knob won't help — you need the schema itself to be finitely expandable.

When you can't modify the schema (third-party contract, published spec), inject a depth-limiting wrapper schema at test time:

# Patch the recursive ref to a bounded stub at depth > N
import copy, hypothesis_jsonschema as hjs
from hypothesis import given, settings

BASE_COMMENT = {
    "type": "object",
    "properties": {
        "text": {"type": "string"},
        "replies": {"type": "array", "maxItems": 0}  # leaf node
    },
    "required": ["text", "replies"]
}

def bounded_comment_schema(max_depth: int = 2) -> dict:
    schema = copy.deepcopy(BASE_COMMENT)
    node = schema
    for _ in range(max_depth):
        child = copy.deepcopy(BASE_COMMENT)
        node["properties"]["replies"] = {
            "type": "array", "items": child, "maxItems": 3
        }
        node = child
    return schema

@given(hjs.from_schema(bounded_comment_schema(max_depth=2)))
@settings(max_examples=200)
def test_comment_roundtrip(comment):
    assert isinstance(comment["text"], str)

This approach keeps generation fast — dropping from a hung process to sub-second draws — and keeps examples structurally realistic. For reproducible data pipeline validation, pin the depth constant in a shared fixture so every environment generates structurally identical shapes. Combine this with Hypothesis's deriving or a Pydantic model validator to assert invariants across the full recursive structure, not just the root. A real benchmark: a healthcare pipeline using a self-referential Encounter schema (similar in structure to the kind of nesting you see in lab test data models) went from a hung 20-minute run to a 4-second suite after adding maxItems: 0 at the leaf level and capping depth at 3.

Mistakes Engineers Make When Debugging Hung PBT Generators

The most common mistake is blaming Hypothesis settings. Engineers bump max_examples down to 10, see the hang persist, then assume it's a Hypothesis bug and file an issue. The real problem is that the generator never produces even one example — settings that control example count are irrelevant when the draw loop never exits. A second mistake is using @settings(deadline=None) as a fix: removing the deadline hides the symptom (a DeadlineExceeded error) while the CPU-pinning hang continues. Both mistakes share the same mental model error — treating generation time as a performance problem rather than a structural one.

A subtler mistake is assuming that $defs with no direct self-reference are safe. Mutual recursion — A references B, B references A — is just as lethal to eager generators and is harder to spot in a large schema. The cycle-detection script above handles mutual recursion because it builds the full reference graph before traversing. Run it as part of schema CI, not just locally, so new $defs added by other teams don't silently introduce cycles that only manifest when the PBT suite runs.

Myths About Recursive Schemas and Property-Based Test Coverage

Myth 1: Bounding recursion depth reduces test coverage. In practice, the alternative is zero coverage — a hung generator produces nothing. A depth-2 or depth-3 bounded schema still exercises the recursive path, the leaf-node path, and the transition between them. That's the coverage that matters for most validation logic. Unbounded generation sounds more thorough but is operationally useless. Myth 2: Removing the $ref and inlining the schema fixes the problem. Inlining a self-referential schema just moves the cycle into a different representation — JSON Schema resolvers will still follow the structural loop. The fix is always a finite base case, not a syntactic refactor.

Myth 3: This is only a problem with complex domain schemas. Simple event schemas in Kafka pipelines often carry recursive metadata objects — a map of key/value pairs where a value can itself be a metadata map. Engineers treat these as trivially simple and skip schema linting. The result is the same hung generator. Treat any schema that allows a type to appear within itself — at any nesting level, through any number of intermediate refs — as a recursion risk, and apply the cycle-detection step unconditionally.

Recursive $ref cycles are a structural problem that no generator setting can paper over. Add the cycle-detection script to your schema CI pipeline, enforce a finite base case on every recursive branch, and use depth-bounded wrapper schemas when you can't modify the source. If you're building out broader schema validation hygiene, the patterns around keyword interactions that silently widen validation boundaries are the natural next problem to address — they compound badly with recursive structures.

Note: This article is for informational purposes only and is not a substitute for professional advice. If you need guidance on specific situations described in this article, consider consulting a qualified professional.