Seeded Deterministic Interleaving Tests for Lifecycle Operations, With Auto-Mocks Derived From Declarations

Pitch

A seed is the tape a deterministic chooser reads at every scheduling decision, so a failing lifecycle interleaving is a short integer vector that replays to the same schedule, and a greedy shrink over that vector reached one non-canonical choice in the worked example.

Abstract

Concurrent compositions of components fail for a reason that failure-point testing does not cover: independent lifecycle operations, activation and teardown of different components, run in an order the author never pictured. Existing schedule explorers (CHESS, PCT, Loom, Shuttle) need to control a nondeterministic runtime, and most capture-and-replay tools fix an order after the fact. We describe schedule testing in revl, a language whose reference runtime has no wall clock, no threads, and cooperative waits only. A seeded PRNG indexes the canonically sorted ready set at each decision; the sequence of chosen indices is the schedule, so the same seed replays the identical interleaving. For each completed schedule the harness checks residue (reusing the fault sweep's four snapshot deltas plus unreleased host resources), deadlock (a fiber that can never activate), and stability of the observable end state against the canonical sequential run, which includes the order of irreversible emissions. A failing choice vector is shrunk by a greedy pass in the delta-debugging style, toward the canonical index 0, and printed as the reproduction. Separately, the auto-mock facility derives in-memory providers from service declarations, where emissions are counted and never crossed; schedule testing does not yet run against those mocks. The scheduler ships on the Python reference tier with 17 tests; its alphabet is two operations (activate, teardown), exploration is sampled rather than exhaustive, and the capability and use-after-withdrawal checks are not yet substantive. We report the design, the checked properties, the limits, and a worked two-consumer example whose emission-order divergence minimizes to a single non-canonical choice.

Problem and claim

Lifecycle bugs in a plugin-style composition (leaked registrations, order-dependent emissions, stranded consumers) depend on which independent component comes up or goes down first. A fault sweep that splices a fail into every step finds failure points but runs one fixed order. Testing interleavings normally needs either a controlled scheduler over a nondeterministic runtime, or flaky stress runs.

The claim: when the runtime is deterministic by construction, interleaving testing reduces to choosing an order for the harness-issued lifecycle operations. A seed then is a complete, replayable description of the schedule, the ready set has a canonical order so index 0 means the same thing on every replay, and the properties to check are the ones the language already defines oracles for (residue, deadlock, observable end state).

The claim is deliberately narrow. It covers two lifecycle atoms on one tier, with sampling, not a proof that no interleaving violates a property. The design doc says so itself (see limits).

Contributions

1. A seed-as-tape scheduler: a seeded PRNG indexes the ready set sorted by (operation-kind rank, fiber load-order index, name), with a canonical always-index-0 baseline and a replay chooser built from a saved choice vector (src/revl/schedule.py:92-105, src/revl/schedule.py:199-234).
2. A per-schedule property check over completed schedules: residue-free, no deadlock, stable observable end state versus the canonical run, where the fingerprint includes the ordered emission sequence (src/revl/schedule.py:269-325, docs/schedule-testing.md:62-92).
3. A greedy shrink over the choice vector in the delta-debugging style: drop trailing choices, then reset each choice toward index 0, keeping a change only if it fails with the same signature (src/revl/schedule.py:463 (minimize), docs/schedule-testing.md:94-115). The code is one-choice-at-a-time, not ddmin.
4. A teardown gate that restricts explored schedules to valid reverse-dependency orders, so every explored schedule is a legal one (docs/schedule-testing.md:49-55).
5. Auto-mocks: a typed, seeded, deterministic in-memory provider per service declaration, with emission operations counted and not crossed (src/revl/mocks.py:1-34, src/revl/mocks.py:97-158, docs/auto-mocks.md:1-10).

Related work

Evidence on main

Tree: revl main at commit 45bec431f.

Numbers that exist

• tests/test_schedule_testing.py has 17 test functions (counted by rg -c "^def test"). tests/test_auto_mocks.py has 29. Whether they pass in CI was not checked here.
• The fixtures: ORDERED (3 components) and CLEAN (3 components) in tests/test_schedule_testing.py:33-47. The doc's worked example reports a minimized vector [0, 1, 0, 0, 0, 0] (docs/schedule-testing.md:105-108); the test asserts exactly one non-zero entry.
• Sampling sizes used in tests: 40 and 60 seeds. Default is 200 (src/revl/schedule.py:510).
• No measurements of bug-finding rate, schedule coverage, minimization ratio or runtime cost.

Paper outline

1. Introduction: lifecycle interleavings as a missing test axis; the claim and its narrow scope.
2. Background: the deterministic py reference runtime, the fault sweep and its oracles.
3. Design: atoms, ready-set order, seed tape, teardown gate, properties.
4. Minimization and reproduction: delta-debugging over the choice vector, the worked example.
5. Auto-mocks: derived providers, counted-not-crossed emissions, how they would compose with the scheduler.
6. Evaluation: mutants, detection rate, coverage against full enumeration (to be run).
7. Related work, limits, and the partial-order-reduction follow-on.

Threats to validity and limits

• Sampled, not exhaustive. The design doc: v1 "does not enumerate the full state space or apply partial-order reduction" (docs/design/295-schedule-testing.md:261-264). A clean run says "we did not hit one", not "none exists".
• Two atoms only. The finer turns (resume of an in-flight await, completion of a Job, firing of a timer) are the documented follow-on (docs/schedule-testing.md:57-60). Whether most real concurrency bugs live there is not measured.
• Capability and use-after-withdrawal checks are not substantive today (see the evidence table) and are not claimed.
• The stability property is strict equality with the sequential run. Two independent components that each emit once will be reported as divergent, since the fixture ORDERED is exactly that. Whether this is a bug or an intended order-independence is the author's call; the design lists this as open question 2 (docs/design/295-schedule-testing.md:319-330).
• Python tier only; determinism rests on the cordis-py cooperative substrate. Other tiers are not covered.
• A comment in the fault module still lists schedule exploration as out of scope (src/revl/fault.py:597-600); it is stale relative to this feature.
• The py prototype's dependency on an earlier runtime slice is described in docs/design/295-schedule-testing.md:102-119. The code exists, so the paper cites the code, not the roadmap tick (docs/roadmap-archive/12-post-v2-0-horizon-strategy-review.md:595).

Fact-check

Claims in this draft were checked against revl main at commit 45bec431f: 30 checked, 12 corrected.

Cite this draft

@misc{revlp17,
  author       = {Thomas Moussajee},
  title        = {Seeded Deterministic Interleaving Tests for Lifecycle Operations, With Auto-Mocks Derived From Declarations},
  year         = {2026},
  howpublished = {\url{https://inso1337.github.io/revl/research/P17.html}},
  note         = {Research draft, not peer reviewed. Written against revl commit 45bec431f. Licensed CC BY 4.0.}
}

Text licensed CC BY 4.0, author Thomas Moussajee.