Lockstep.Shrink (Lockstep v0.1.0)

Reduce a failing schedule to a minimal one that still triggers the same bug, deterministically.

When Lockstep finds a bug, the failing trace can be hundreds or thousands of events. Most of those events are necessary setup but obscure the actual race. Shrinking searches for a shorter replay_pid_order (subset of the original) that still triggers the same bug signature (deadlock, child crash, assertion failure, etc.) under the strict Lockstep.Strategy.Replay -- no random fill, no nondeterminism.

Algorithm

Two-pass shrink, repeated to fixed point:

Truncation -- try shorter prefixes of the original schedule. The smallest prefix that still triggers the bug becomes the new baseline. We accept only prefixes whose strict replay (no fallback) raises the matching bug before the schedule diverges.
Decimation -- inside the truncated prefix, try removing individual positions. Keep removals that still reproduce.

Both passes use fallback: :raise -- the shrunk schedule must faithfully drive the controller to the bug without falling back to random scheduling. That way the result is a guaranteed-deterministic repro, suitable for mix lockstep.replay.

Bug-signature comparison is intentionally lenient: two schedules match if they raise the same category of bug (:deadlock, :timeout, :child_crash, {:exception, ExType}, etc.). Exact pids, refs, and step numbers don't need to match -- the shrunk trace is meant to be a cleaner repro of the same class of bug.

Usage

{:ok, info} = Lockstep.Shrink.shrink(
  fn -> MyTest.lost_update_body() end,
  "traces/counter_race-iter5-seed42.lockstep"
)

info.original_length  # => 87 scheduling decisions
info.new_length       # => 9
info.new_trace_path   # => "traces/counter_race-iter5-seed42.shrunk.lockstep"

Then mix lockstep.replay --trace ...shrunk.lockstep plays back the minimal repro.

Summary

Types

opt()

Functions

shrink(test_fun, trace_path, opts \\ [])

Shrink the schedule recorded in trace_path against a runnable test_fun. Returns {:ok, info} with the original / new lengths and the path to the saved shrunk trace, or {:error, reason} if the original doesn't reproduce or shrinking found nothing smaller.

Types

opt()

@type opt() ::
  {:max_attempts, pos_integer()}
  | {:iter_timeout, pos_integer()}
  | {:verbose, boolean()}

Functions

shrink(test_fun, trace_path, opts \\ [])

@spec shrink((-> any()), Path.t(), [opt()]) ::
  {:ok, %{required(atom()) => any()}} | {:error, term()}