Property-Based Testing for WIO Semantics

[Krever]

Problem Statement

The WIO (Workflow IO) DSL has a combinatorial explosion problem when it comes to testing. We have:

• 20+ WIO variants: Pure, RunIO, HandleSignal, Timer, Fork, Loop, Parallel, ForEach, HandleInterruption, Checkpoint, Retry, Embedded, AndThen, FlatMap, Transform, HandleError, HandleErrorWith, etc.
• 10+ cross-cutting evaluators: SignalEvaluator, EventEvaluator, GetSignalDefsEvaluator, GetStateEvaluator, GetIndexEvaluator, GetWakeupEvaluator, ProceedEvaluator, RunIOEvaluator, ExecutionProgressEvaluator
• Multiple composition patterns: Sequential (>>>), monadic (flatMap), error handling, interruption, parallel, embedded contexts

Each evaluator must work correctly for any valid WIO tree, including deeply nested combinations like "signal inside loop inside error handler with interruption on top inside forEach".

Execution State Explosion

The combinatorial problem is compounded by execution state transitions. Each WIO node can be in multiple states:

WIO Variant	Possible Execution States
AndThen	first pending, first executed (success), first executed (error)
Loop	iteration 0, iteration 1, ..., iteration N, completed
HandleInterruption	base running, interrupted
Fork	no branch selected, branch 1 selected, branch 2 selected, ...
HandleError/With	base succeeded, base failed + handler running, handler completed
Parallel	0 elements done, 1 element done, ..., all elements done
ForEach	0 elements processed, partial, all processed
Timer	not started, started (awaiting), released
Checkpoint	base pending, base done + checkpoint pending, checkpoint recorded
HandleSignal	waiting, executed
RunIO	waiting, executed
Retry	attempt 1, attempt 2, ..., succeeded, exhausted

This means the actual test space is:

WIO Variants × Composition Depth × Execution States = Enormous

For example, testing GetSignalDefsEvaluator for a simple signal1 >>> signal2 requires testing:

• signal1 pending, signal2 pending → expects [signal1]
• signal1 executed, signal2 pending → expects [signal2]
• signal1 executed, signal2 executed → expects []

Now imagine this for loop(signal >>> timer).interruptWith(cancelSignal) where the loop could be on iteration 3, the timer could be awaiting, and the interruption could have fired. Each combination potentially has different expected signals.

Manual testing cannot cover this space. We need property-based testing with generators and laws.

Current Testing Approach

The codebase uses ScalaTest with example-based tests. Each WIO variant has its own test file (e.g., WIOPureTest.scala, WIOHandleSignalTest.scala) testing specific scenarios. This approach has significant gaps:

1. Limited combinatorial coverage - Tests focus on individual operations, few tests for 3+ level nesting
2. No generators - All test data is manually crafted
3. No shrinking - When tests fail, no automatic minimization of failing cases
4. Implicit laws - Properties like "signal redelivery returns same response" are tested by example, not universally

Proposed Solution: Property-Based Testing Framework

1. WIO Generators

Create Arbitrary instances (ScalaCheck) or equivalent generators for building random WIO trees:

// Leaf generators
def genPure[Ctx]: Gen[WIO.Pure[Ctx, TestState, Nothing, TestState]]
def genRunIO[Ctx]: Gen[WIO.RunIO[Ctx, TestState, Nothing, TestState, TestEvent]]
def genSignal[Ctx]: Gen[WIO.HandleSignal[Ctx, TestState, TestState, Nothing, Int, Int, TestEvent]]
def genTimer[Ctx]: Gen[WIO.Timer[Ctx, TestState, Nothing, TestState]]
def genEnd[Ctx]: Gen[WIO.End[Ctx]]

// Composition generators (recursive)
def genAndThen[Ctx](depth: Int): Gen[WIO.AndThen[Ctx, ...]]
def genFlatMap[Ctx](depth: Int): Gen[WIO.FlatMap[Ctx, ...]]
def genFork[Ctx](depth: Int): Gen[WIO.Fork[Ctx, ...]]
def genLoop[Ctx](depth: Int): Gen[WIO.Loop[Ctx, ...]]
def genHandleInterruption[Ctx](depth: Int): Gen[WIO.HandleInterruption[Ctx, ...]]
def genParallel[Ctx](depth: Int): Gen[WIO.Parallel[Ctx, ...]]
def genForEach[Ctx](depth: Int): Gen[WIO.ForEach[Ctx, ...]]
def genEmbedded[Ctx](depth: Int): Gen[WIO.Embedded[Ctx, ...]]

// Master generator with depth control
def genWIO[Ctx](maxDepth: Int): Gen[WIO[TestState, Nothing, TestState, Ctx]]

The generators should:

• Control maximum depth to avoid stack overflow
• Weight simpler structures more heavily (smaller trees more likely)
• Ensure type consistency through composition
• Generate valid event handlers and signal handlers

Execution State Generators

Critically, we also need to generate partially executed WIO trees, not just fresh ones:

// Generate a WIO wrapped in Executed node (already ran)
def genExecuted[Ctx](wio: Gen[WIO[...]]): Gen[WIO.Executed[Ctx, ...]]

// Generate AndThen with first step potentially executed
def genAndThenWithState[Ctx](depth: Int): Gen[WIO.AndThen[Ctx, ...]] = for {
  first <- genWIO(depth - 1)
  second <- genWIO(depth - 1)
  executeFirst <- Gen.boolean
  executedFirst <- if (executeFirst) genExecuted(first) else Gen.const(first)
} yield AndThen(executedFirst, second)

// Generate Loop with N iterations already completed
def genLoopWithHistory[Ctx](depth: Int): Gen[WIO.Loop[Ctx, ...]] = for {
  body <- genWIO(depth - 1)
  iterations <- Gen.choose(0, 5)
  history <- Gen.listOfN(iterations, genExecutedIteration(body))
  currentState <- genLoopState  // Forward, Backward, Finished
} yield Loop(body, history, currentState, ...)

// Generate HandleInterruption with possible interruption triggered
def genInterruptionWithState[Ctx](depth: Int): Gen[WIO.HandleInterruption[Ctx, ...]] = for {
  base <- genWIO(depth - 1)
  interruption <- genInterruption(depth - 1)
  status <- Gen.oneOf(Pending, TimerStarted, Interrupted)
  // If Interrupted, wrap base appropriately
} yield HandleInterruption(base, interruption, status)

// Generate Parallel with some elements completed
def genParallelWithProgress[Ctx](depth: Int): Gen[WIO.Parallel[Ctx, ...]] = for {
  numElements <- Gen.choose(2, 4)
  elements <- Gen.listOfN(numElements, genWIO(depth - 1))
  completedMask <- Gen.listOfN(numElements, Gen.boolean)
  elementsWithState <- elements.zip(completedMask).traverse {
    case (elem, true) => genExecuted(elem)
    case (elem, false) => Gen.const(elem)
  }
} yield Parallel(elementsWithState, ...)

This allows testing evaluators against workflows "mid-flight" - e.g., testing GetSignalDefsEvaluator on a loop that's already on iteration 3 with some signals executed.

2. Laws / Properties to Test

The following are example laws to illustrate the kinds of properties we should test. The actual set of laws should be discovered and refined during implementation.

A. Signal Handling Laws (examples)

• Signal delivery determinism: Same WIO + same request → same event
• Signal redelivery idempotency: Delivering same signal twice returns same response
• expectedSignals accuracy: All signals in expectedSignals() are actually deliverable
• Unexpected signal rejection: Signals not in expectedSignals() return UnexpectedSignal

B. State & Index Laws (examples)

• State monotonicity: State only advances, never regresses
• GetStateEvaluator consistency: Evaluator result matches actual workflow state
• Index monotonicity: Execution indices never decrease
• Index uniqueness: No duplicate indices in a workflow tree

C. Timer/Wakeup Laws (examples)

• Wakeup is minimum: GetWakeupEvaluator returns earliest pending timer
• Timer triggers on wakeup: Advancing time past wakeup releases the timer

D. Event Handling Laws (examples)

• Single event match: Each event matches at most one node in the tree
• Event recovery consistency: Replaying same events produces same state

E. Composition Laws (examples)

• AndThen associativity: (a >>> b) >>> c ≡ a >>> (b >>> c)
• FlatMap monad laws: Left identity, right identity, associativity

F. Interruption Laws (examples)

• Interruption signal precedence: Interruption signals always in expectedSignals() while base is running
• Interrupted base unreachable: After interruption, base signals no longer available

G. Execution State Transition Laws (examples)

• Proceed reduces pending work: Each proceed step reduces pending signals/timers (or opens new branch)
• Executed nodes are stable: Once a node is executed, it remains in the tree
• Error path consistency: Errors trigger error handlers
• Loop history consistency: Loop history matches actual iteration count

H. ForEach/Embedded Laws (examples)

• ForEach signal routing: Inner signals correctly wrapped and routable
• Embedded context roundtrip: State conversion is reversible

3. Test Infrastructure

A. Semantic Equivalence

Define what it means for two WIOs to be "semantically equivalent":

def semanticallyEquivalent[Ctx](wio1: WIO[...], wio2: WIO[...]): Boolean = {
  val scenarios = genScenarios(wio1, wio2)  // Generate execution scenarios

  scenarios.forall { scenario =>
    val instance1 = createInstance(wio1)
    val instance2 = createInstance(wio2)

    scenario.execute(instance1)
    scenario.execute(instance2)

    instance1.queryState() == instance2.queryState() &&
    instance1.expectedSignals() == instance2.expectedSignals() &&
    instance1.getWakeup() == instance2.getWakeup()
  }
}

B. Execution Scenario Generator

sealed trait ExecutionAction
case class DeliverSignal(signalDef: SignalDef[_, _], request: Any) extends ExecutionAction
case class DeliverEvent(event: Any) extends ExecutionAction
case class AdvanceTime(duration: FiniteDuration) extends ExecutionAction
case object Proceed extends ExecutionAction
case object Wakeup extends ExecutionAction

def genScenario(wio: WIO[...]): Gen[List[ExecutionAction]]

C. Shrinking

Implement custom shrinkers that preserve WIO validity:

implicit def shrinkWIO[Ctx]: Shrink[WIO[...]] = Shrink { wio =>
  wio match {
    case AndThen(first, second) => Stream(first, second) ++ shrinkWIO(first) ++ shrinkWIO(second)
    case Loop(body, _, _) => Stream(body) ++ shrinkWIO(body)
    case Fork(branches) => branches.map(_.wio).toStream ++ branches.flatMap(b => shrinkWIO(b.wio))
    // ... etc
  }
}

4. Open Questions

1. Type complexity: WIO has many type parameters. Should we use a simplified TestWIO with fixed types, or try to maintain full generality?

2. Effect handling: RunIO and signal handlers produce IO effects. Should we:

   • Mock all effects to return predetermined values?
   • Use a test interpreter that tracks effects?
   • Actually run effects in tests?

3. Depth vs coverage tradeoff: Deeper trees find more bugs but are slower and harder to shrink. What's the right balance?

4. Evaluator-specific vs holistic: Should we test each evaluator in isolation, or focus on end-to-end workflow behavior?

5. Existing framework: Should we use ScalaCheck, Hedgehog, or something else? ScalaCheck has better ecosystem, Hedgehog has better shrinking.

5. Expected Benefits

1. Bug discovery: Find edge cases in deeply nested structures that manual tests miss
2. Regression prevention: Properties catch regressions that example tests might not cover
3. Documentation: Laws serve as executable specification of WIO semantics
4. Refactoring confidence: Can refactor evaluators knowing properties will catch semantic changes
5. New feature validation: When adding new WIO variants, properties ensure they integrate correctly