isolationtest

package
v0.11.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 13, 2026 License: MIT Imports: 16 Imported by: 0

Documentation

Overview

Package isolationtest is a declarative, exhaustive, deterministic harness for concurrent isolation scenarios — GoGraph's analogue of PostgreSQL's src/test/isolation ("isolationtester").

Why it exists

GoGraph already has substantial isolation testing: ~199 test functions across graph/lpg/mvcc_*_test.go and store/txn/, the randomised DST battery in internal/sim, and the crash-injection battery in internal/crashinject. What none of them does is ENUMERATE the interleavings of a scripted scenario. Every concurrent isolation test either fixes one interleaving by hand or samples the space randomly.

That gap is on the record. rmp #2333 was a torn total that could not be reproduced; rmp #2336 exists because a torn-total sighting from 2026-08-06 is still unexplained and has to be chased with a standing randomised search. A randomised search can FIND an anomaly; it cannot certify that a scenario is free of one, and it reproduces badly. This harness answers the complementary question — "over EVERY interleaving of these steps, is the observable outcome the expected one?" — and answers it the same way every run.

The reference, and what was taken from it

Structure adopted from PostgreSQL's src/test/isolation, read at commit 0ec3f048bfc15c8eb9933e8228b847593389da1b (2026-08-07): a spec declares setup, teardown, named sessions each holding named steps, and optional explicit permutations; when no permutation is given the tester runs ALL interleavings with each session's own step order preserved; a step that blocks is reported as waiting rather than hanging; and each permutation's rendered output is compared against a golden file. PostgreSQL ships 135 such specs.

The enumeration is PostgreSQL's "piles" recursion (isolationtester.c, run_all_permutations_recurse): conceptually each session's steps are a pile, and a permutation is produced by drawing from the piles in every order. It is re-implemented here, not transcribed — see Permutations.

THREE THINGS WERE DELIBERATELY NOT COPIED.

  • The lex/yacc spec language. PostgreSQL needs a text format because its steps are SQL strings shipped over libpq to separate backends; GoGraph's steps are Cypher strings run through an in-process cypher.Engine, so a Go literal is exactly as declarative, is type-checked, and costs no scanner or grammar to maintain. The spec is DATA either way, which is the property that matters.

  • Lock-view polling for blocking detection. isolationtester recognises a blocked command by looking for it in pg_locks, and therefore only detects heavyweight-lock waits. GoGraph has no such view, and — more to the point — under MVCC-only concurrency control an ordinary read or write acquires nothing and a write-write collision is REFUSED rather than queued, so there is usually nothing to wait on at all. Blocking is detected here by bounded timeout, which is what an out-of-process observer can actually see, and it still catches the case that genuinely does block: a DDL holding the exclusive schema gate.

  • The stabilisation markers (`(*)`, `(othersteep)`, `notices <n>`). PostgreSQL needs them because it launches the next step as soon as the previous one is "done or deemed blocked", so two steps can be in flight and complete in either order. This harness AWAITS each step before launching the next unless that step is blocked, so within one permutation the order of completions is fixed by construction and there is nothing to stabilise. That is the whole determinism argument; see Runner.Run.

Concurrency

A Spec is immutable data and safe to share. A Runner is NOT safe for concurrent use, and each permutation gets a freshly built graph and engine, so two permutations never observe each other.

Index

Constants

View Source
const DefaultBlockTimeout = 2 * time.Second

DefaultBlockTimeout is how long a step may take before the harness reports it as blocked and moves on.

It is deliberately enormous relative to the work: a step in these specs is a single-node Cypher statement over a graph of a handful of nodes, which is microseconds even on the durable wiring. Two seconds therefore separates "genuinely waiting on something" from "slow", with four orders of magnitude of margin, so a loaded machine cannot turn a completed step into a `<waiting…>` line and flip a golden file.

PostgreSQL's equivalent is 360 s, because its steps are real SQL against a real server. The number differs; the reasoning — pick a bound no healthy step can reach — is the same.

View Source
const DefaultPermutationTimeout = 30 * time.Second

DefaultPermutationTimeout bounds a whole permutation, so a scenario that deadlocks fails the test instead of hanging the package.

Variables

View Source
var ErrNoPermutation = errors.New("isolationtest: no such permutation")

ErrNoPermutation is returned when Only names a permutation the spec does not produce.

Functions

func Check

func Check(t *testing.T, s *Spec, r *Runner)

Check runs the spec and compares its transcript against testdata/<spec name>.golden, failing the test with a permutation-anchored diff on any difference.

The golden file IS the assertion. It records, for every interleaving, exactly what each step returned — so a change in isolation behaviour shows up as a diff naming the permutation and the step. That is the property a randomised search cannot give (see the package doc, and rmp #2333 / #2336).

Comparison and updating go through goldens.Assert, the project's existing golden-file helper, so `-update` and `GOGRAPH_UPDATE_GOLDENS=1` behave here exactly as they do everywhere else in the module. READ THE DIFF BEFORE UPDATING: these transcripts exist to make an isolation change impossible to merge unnoticed, and blanket-updating them is the one action that defeats them.

The pre-diff below runs only when the transcripts differ and the run is NOT an update; it costs nothing on the passing path and turns goldens.Assert's line diff into something that names a re-runnable permutation.

func CountPermutations

func CountPermutations(s *Spec) *big.Int

CountPermutations returns how many interleavings Permutations would produce, WITHOUT building them.

It exists so a spec's test-layer assignment can be justified by its real size rather than by eyeballing the step counts: the multinomial grows fast enough that a spec which looks small can be six figures. Computed in big.Int because the intermediate factorials overflow int64 well before the answer does.

Types

type Control

type Control string

Control is a step body that drives the session's transaction lifecycle rather than the graph. PostgreSQL expresses these as ordinary SQL (`BEGIN;`, `COMMIT;`) because they ARE SQL there; in GoGraph they are API calls on cypher.Engine / cypher.ExplicitTx, so the harness names them explicitly.

const (
	// Begin opens an explicit read-write transaction on the session.
	Begin Control = "BEGIN"
	// BeginRead opens an explicit read-only transaction on the session.
	BeginRead Control = "BEGIN READ"
	// Commit commits the session's open transaction.
	Commit Control = "COMMIT"
	// Rollback rolls the session's open transaction back.
	Rollback Control = "ROLLBACK"
)

type Engine

type Engine struct {
	Eng   *cypher.Engine
	Close func() error
}

Engine is what a spec runs against: one freshly built engine plus whatever must be closed after. The harness builds a NEW one for every permutation, so no permutation can observe another's state — which is what makes a failing permutation reproducible in isolation.

type EngineFactory

type EngineFactory func() (*Engine, error)

EngineFactory builds the engine for one permutation. Supplying it rather than hard-wiring a wiring is what lets the same spec run against the in-memory engine and the WAL-backed one, which serialise on different mechanisms.

type Observation

type Observation struct {
	// Permutation is the interleaving in force, and is the exact string
	// [Runner.Only] takes to replay it.
	Permutation string
	// Step is the step's name.
	Step string
	// Cols and Rows are the step's result, as rendered strings. Strings rather
	// than typed values because the transcript is the contract: an invariant
	// must be checking the same thing the golden file records, not a parallel
	// view of it that could disagree.
	Cols []string
	Rows [][]string
	// Err is the step's error, if any.
	Err error
}

Observation is one completed step's structured outcome, handed to an Observer so a spec can assert a PROPERTY rather than only diff a transcript.

type Observer

type Observer func(Observation) error

Observer is called once per completed step. Returning an error marks the invariant violated; the runner records it and keeps going, so ONE run reports EVERY interleaving that breaks the property instead of only the first.

This is what makes the harness an assertion and not just a recorder. A golden file pins that behaviour did not CHANGE; an Observer pins that behaviour is CORRECT — and the two fail for different reasons, which is the point.

type Permutation

type Permutation struct {
	// Steps are the step names in execution order.
	Steps []string
	// Owner[i] is the session index that owns Steps[i].
	Owner []int
}

Permutation is one interleaving: a flat sequence of steps, each tagged with the index of the session that must run it.

func Permutations

func Permutations(s *Spec) []Permutation

Permutations returns every interleaving of the spec's steps that preserves each session's own step order — or, when the spec names permutations explicitly, exactly those.

The enumeration is PostgreSQL's "piles" recursion (src/test/isolation/isolationtester.c, run_all_permutations_recurse, read at 0ec3f048): each session's remaining steps are a pile, and at every position the next step may be drawn from any non-empty pile. Drawing in every order yields every order-preserving interleaving exactly once, because a permutation is fully determined by WHICH pile each position drew from.

The count is the multinomial coefficient (Σnᵢ)! / Πnᵢ!, which grows fast: two sessions of four steps is 70, three sessions of 4/4/2 is 3150, and three of five is 756 756. CountPermutations exists so a spec can be assigned to a test layer from its real size instead of a guess.

The emission order is deterministic and is fixed by the session declaration order in the spec, so a golden file is stable.

func (Permutation) Name

func (p Permutation) Name() string

Name is the permutation's identity, and it is what makes a failing permutation re-runnable: it is stable across runs (the enumeration order is deterministic) and it is the exact string the golden output prints after "starting permutation: ".

type Runner

type Runner struct {
	// NewEngine builds the per-permutation engine. Required.
	NewEngine EngineFactory
	// BlockTimeout overrides [DefaultBlockTimeout] when non-zero.
	BlockTimeout time.Duration
	// PermutationTimeout overrides [DefaultPermutationTimeout] when non-zero.
	PermutationTimeout time.Duration
	// Only, when non-empty, restricts the run to the single permutation with
	// this name — the exact string a golden file prints after "starting
	// permutation: ". This is the re-runnability contract: a failing
	// permutation is named in the diff and can be replayed on its own.
	Only string
	// Observe, when non-nil, is called for every completed step. See [Observer].
	Observe Observer
	// contains filtered or unexported fields
}

Runner executes a spec.

Runner is NOT safe for concurrent use.

func (*Runner) Run

func (r *Runner) Run(ctx context.Context, s *Spec, out io.Writer) error

Run executes the spec and writes the rendered transcript to w.

The transcript is the artefact under test: it is compared against a golden file, so anything nondeterministic in it is a defect in this harness rather than a fact about the engine.

Why the transcript is deterministic

Within one permutation the runner LAUNCHES a step and then AWAITS it before launching the next. Only a step that is still running after BlockTimeout is left in flight, and it is reported as `<waiting …>` at that point; its completion is reported later, at the first point the transcript reaches where it has been observed to finish. So the order of the transcript's lines is fixed by the permutation, not by the scheduler, and the only way two runs can differ is if a step's own RESULT differs — which is exactly the thing the golden file is there to catch.

This is why the harness needs none of PostgreSQL's stabilisation markers: it buys determinism by serialising the observation, where isolationtester buys throughput by overlapping it.

func (*Runner) Violations

func (r *Runner) Violations() []string

Violations returns every invariant breach Runner.Observe reported during the last Runner.Run, each naming the permutation and step it occurred in.

It is a slice rather than a bool because a scenario that breaks its invariant usually breaks it in a FAMILY of interleavings, and which ones is the whole diagnosis: "s2 tears whenever it reads between the debit and the credit" is actionable, "some permutation failed" is not.

type Session

type Session struct {
	// Name identifies the session in the rendered output.
	Name string
	// Setup runs once per permutation, on this session, before any of its steps.
	// Typically a single Begin.
	Setup []Step
	// Steps are the session's units of work, in the order this session must run
	// them. Every enumerated permutation preserves this order.
	Steps []Step
	// Teardown runs once per permutation, on this session, after the permutation
	// completes. Errors here are rendered but do not fail the permutation, so a
	// COMMIT of an already-finished transaction is a harmless no-op to script.
	Teardown []Step
}

Session is one scripted actor. Every step of a session runs on that session's own goroutine against its own cypher.Session, so a transaction opened by one step is the transaction the next step of the same session sees.

type Spec

type Spec struct {
	// Name is the spec's identity; the golden file is testdata/<Name>.golden.
	Name string
	// Doc is prose describing what the scenario is FOR. It is rendered into the
	// golden output, so the file explains itself to whoever reads the diff.
	Doc string
	// Setup runs once per permutation on a control session, before any session
	// setup. Build the fixture here.
	Setup []Step
	// Teardown runs once per permutation on the control session, last.
	Teardown []Step
	// Sessions are the scripted actors. Their declaration order is the tie-break
	// the enumeration uses, so it fixes the order permutations are emitted in.
	Sessions []*Session
	// Permutations, when non-empty, are the ONLY interleavings run, each given
	// as a list of step names. When empty every valid interleaving is
	// enumerated. This mirrors PostgreSQL's rule exactly, and it is the escape
	// hatch for a scenario whose full enumeration is too large for its test
	// layer or whose steps genuinely block.
	Permutations [][]string
}

Spec is a complete isolation scenario.

func (*Spec) Validate

func (s *Spec) Validate() error

Validate reports whether the spec is well-formed. It is called by Runner.Run before anything executes, because every failure mode it catches would otherwise surface as a confusing mid-permutation error.

type Step

type Step struct {
	// Name identifies the step and MUST be unique across the whole spec: it is
	// what makes a failing permutation re-runnable by name.
	Name string
	// Query is the Cypher this step executes. Empty when Ctl is set.
	Query string
	// Ctl is the transaction-control verb this step performs. Empty when Query
	// is set.
	Ctl Control
	// Hook is an escape hatch: a step body written in Go rather than in Cypher.
	//
	// It exists for the things a query language cannot express and an isolation
	// harness nevertheless has to script — a rendezvous between two sessions, a
	// deliberate wait, a fault injected at a precise point in an interleaving.
	// PostgreSQL needs no equivalent because SQL has pg_sleep and advisory
	// locks; GoGraph's step vocabulary is Cypher, which has neither.
	//
	// A Hook runs on its session's goroutine exactly where a Query would, so it
	// participates in blocking detection identically: a Hook that does not
	// return within the block timeout is reported as `<waiting …>` and its
	// completion is reported when it is observed. Label is what the transcript
	// prints in place of the query text, so a Hook step renders deterministically
	// (a Go closure has no stable text).
	Hook  func(ctx context.Context) error
	Label string
	// Params are the query parameters, if any. Rendered into the output so a
	// golden file records what was actually run.
	Params map[string]any
}

Step is one named unit of work inside a session.

Exactly one of Query and Ctl is set. A step with a Query and no open transaction runs as an autocommit statement, which is the same thing a bare statement does outside a transaction block in PostgreSQL.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL