model

package
v0.0.0-...-b8a15ae Latest Latest
Warning

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

 Go to latest Published: Aug 24, 2026 License: Apache-2.0 Imports: 2 Imported by: 0

Documentation

Overview

Package model holds the run and step state machines as pure functions.

Nothing here reads a database, a network, a file or a clock, and the package imports nothing under internal/ (05 section 4). Time arrives as Guards.Now, in unix milliseconds UTC, because internal/clock owns time.Now (M0-09). Every function is deterministic given its arguments, which is what makes the cross table below provable rather than merely tested.

The two machines

A run is queued, running, succeeded, failed or cancelled. A step is pending, running, succeeded, failed, skipped or cancelled. NextRunState and NextStepState take the current state, an event and the guards, and return the next state, the effects the caller has to perform, and an error. The drawn form of both machines, generated from the code, is transitions.golden.md.

Two simplifications shrink the model, and both come from the plans:

  • Deferred is not a state (00 section 3.14, 01 section 4.1). A deferred run is queued, with available_at in the future and a defer reason beside it. IsDeferred computes it, so the command line still shows "deferred (reason)" without two extra states and every transition around them.
  • Retry is not a state either (05 section 6.6). A failed attempt with retries left goes back to pending with a next_attempt_at, which makes the claim gate in SQL the whole retry scheduler.

Effects

A transition returns what has to happen, and the caller performs it inside its own transaction. That keeps the model pure while it stays in charge of the writes a transition implies, including the single run_events row every transition commits with itself (G10). An effect names the column to write; the value comes from the caller when it depends on a clock or on backoff, which the model must not compute.

Refusals

A refusal moves nothing: the state comes back as it went in and no effect is demanded. Refusals carry identity, so callers match them with errors.Is and never with a string:

  • ErrIllegalTransition is a pair the machine does not name at all.
  • ErrNotAvailable, ErrMissingReasonCode, ErrMissingDeferReason, ErrStepsNotTerminal, ErrStaleLease and ErrLeaseStillValid are pairs the machine names and the guards deny.

errors.As on IllegalTransitionError or GuardError gives the state, the event and the outcome that was denied, so a log line and an explain output stand on their own.

The invariants this package holds 

I2   A terminal run has no step in running. EvAllStepsDone is refused
     unless Guards.AllStepsTerminal says every step has finished.
I10  A succeeded run has no failed step, and a failed run has one.
     RunAggregate is the single function that decides it, used by the
     engine (M1-08) and by fsck (M1-12).
I14  A deferred run has a defer reason. EvDeferred is refused without
     one, and a requeue after a crash writes DeferReasonAfterCrash.
     06 section 2.1: a terminal state has a reason code. Every
     transition into one is refused without it.
     02 T14: only EvOperatorRetry leads out of a terminal run. A
     terminal step accepts no event at all.

The same rules are enforced a second time as CHECK constraints in the schema (07 section 7). Two independent enforcements of one rule are cheap, and they catch the case where one side is edited and the other is not.

Index

Constants

View Source 
const DeferReasonAfterCrash = "reconciled_after_crash"

DeferReasonAfterCrash is what a run requeued after a lost lease says about itself. The reason code catalogue is M1-05; this one string is the model's own, because the run it describes is put back by the reaper rather than by anything that could pass a reason in.

View Source 
const DeferReasonAfterShutdown = "requeued_after_shutdown"

DeferReasonAfterShutdown is what a run requeued by its own executor's clean stop says about itself. Like DeferReasonAfterCrash it lives here because the machine demands the effect and nothing else owns the word. A drained run carries no crash: the executor left on purpose, and counting one would make every ordinary restart look like a failing run.

View Source 
const DeferReasonConcurrency = "concurrency"

DeferReasonConcurrency is what a run materialised under overlap: queue says about itself: it was born queued, but every concurrency slot of its job was already held, so available_at points into the future and this reason names why (#68). It lives beside the other two defer reasons so all three words the schema's CHECK and fsck I14 look for come from one file.

Variables

View Source 
var (
	// ErrIllegalTransition is a pair (state, event) the machine does not
	// name at all.
	ErrIllegalTransition = errors.New("illegal transition")
	// ErrNotAvailable is a claim on a run whose available_at is still in the
	// future. The pair is legal; the run is simply deferred.
	ErrNotAvailable = errors.New("run is not available yet")
	// ErrMissingReasonCode is a transition that needs an explanation and did
	// not get one (06 section 2.1).
	ErrMissingReasonCode = errors.New("missing reason code")
	// ErrMissingDeferReason is a deferral without a reason (I14).
	ErrMissingDeferReason = errors.New("missing defer reason")
	// ErrStepsNotTerminal is a run being finished while a step of it is
	// still active (I2).
	ErrStepsNotTerminal = errors.New("steps are not all terminal")
	// ErrStaleLease is a writer without the run's lease trying to move it.
	ErrStaleLease = errors.New("lease is not held")
	// ErrLeaseStillValid is a lease expiry reported for a lease that has not
	// expired.
	ErrLeaseStillValid = errors.New("lease has not expired")
	// ErrUnknownState is a stored name outside the closed set.
	ErrUnknownState = errors.New("unknown state")
)

The sentinels are what callers match with errors.Is. Every refusal the machines make has one, so no caller has to compare error text, and the detailed types below carry the state and the event that explain the refusal to a person reading a log or running explain.

Functions

func ApplyRun 

func ApplyRun(cur RunState, inputs []Input) (RunState, []Effect, error)

ApplyRun folds a history through the run machine and returns where it ended, every effect it earned on the way, and the first refusal that stopped it. A refused input stops the fold, and the state returned is the last one the run legally reached.

It exists so a property test can drive the model and a real store through the same sequence and compare them (M3-08), and so explain can replay a history without reimplementing the machine.

func ApplyStep 

func ApplyStep(cur StepState, inputs []Input) (StepState, []Effect, error)

ApplyStep is ApplyRun for the step machine.

func IsDeferred 

func IsDeferred(state RunState, availableAt, now int64) bool

IsDeferred is what the six state description called "deferred", computed instead of stored: a queued run that is not allowed to start yet. The caller passes the timestamps because the model never reads a clock (M0-09); both are unix milliseconds UTC, the unit every time column in the database uses.

A run that is exactly available now is not deferred, which is the same comparison the claim gate in SQL makes.

func NextRunState 

func NextRunState(cur RunState, ev Event, g Guards) (RunState, []Effect, error)

NextRunState is the run machine, and the only place that decides what a run may do next. It reads nothing but its arguments: no database, no clock, no package level state, so the same three inputs always give the same three results. The effects it returns say what the caller has to write; the caller performs them in its own transaction (05 section 4).

A refusal moves nothing. The state comes back exactly as it went in and no effect is demanded, so a caller that acts on the state without checking the error cannot half apply a transition.

Guards are read in one order everywhere: fencing first, because a writer that has lost the lease must be shut out before anything it reports is believed; then the precondition of the event itself; then the reason code, which is the last thing that can be missing from an otherwise legal transition.

func NextStepState 

func NextStepState(cur StepState, ev Event, g Guards) (StepState, []Effect, error)

NextStepState is the step machine. It has the same shape and the same rules as NextRunState: pure, refusals move nothing, and every terminal outcome carries a reason code.

Two things it deliberately does not do. It does not read the lease: a step is moved by whoever owns the run, and that ownership is checked once, on the run (I1). It does not know the step graph either: EvUpstreamFailed is the hook a skip arrives through, and which steps it applies to is the transitive closure in M4-03.

Types

type Effect 

type Effect struct {
	Kind EffectKind
	Arg  string
}

Effect is one required action. Arg carries the value the model itself determined: the event name for EffectEmit and the reason for EffectSetDeferReason. It is empty for every other kind, because those name a column to write rather than a value to write into it.

The type is comparable, so a test compares whole effect lists with slices.Equal and a caller can switch on Kind without a type assertion.

type EffectKind 

type EffectKind string

EffectKind is one thing a transition requires its caller to do. The machine decides what has to happen and returns it; the caller performs it inside its own transaction (05 section 4). That is what keeps the model pure while still leaving it in charge of the writes a transition implies. 

const (
	// EffectBumpEpoch raises the run's fencing epoch, so any writer holding
	// the old one is shut out.
	EffectBumpEpoch EffectKind = "bump_epoch"
	// EffectTakeLease and EffectReleaseLease are the ownership of a running
	// run. Only a run that holds a lease releases one.
	EffectTakeLease    EffectKind = "take_lease"
	EffectReleaseLease EffectKind = "release_lease"
	// EffectSetStarted and EffectSetFinished stamp started_at and
	// finished_at, together with the reason code the transition validated.
	// The values come from the caller's clock, never from here.
	EffectSetStarted  EffectKind = "set_started"
	EffectSetFinished EffectKind = "set_finished"
	// EffectKillProcessGroup ends the running process group. It is listed
	// before the writes because a cancelled run that is still executing is
	// the one thing worse than a slow cancel.
	EffectKillProcessGroup EffectKind = "kill_process_group"
	// EffectIncCrashCount counts a run against its crash budget.
	EffectIncCrashCount EffectKind = "inc_crash_count"
	// EffectIncAttempt opens the next attempt of a step.
	EffectIncAttempt EffectKind = "inc_attempt"
	// EffectRestoreAttempt takes an interrupted attempt's increment back off
	// the step. Only the shutdown drain uses it: the attempt never got to
	// produce a verdict, so the retry budget it would have spent stays
	// unspent. It is deliberately distinct from EffectIncAttempt so no caller
	// can "restore" an attempt nothing opened.
	EffectRestoreAttempt EffectKind = "restore_attempt"
	// EffectSetNextAttemptAt and EffectSetAvailableAt write the time a retry
	// or a deferred run becomes runnable. The model names the column; the
	// caller computes the value, because that is backoff (M1-09) and a clock.
	EffectSetNextAttemptAt EffectKind = "set_next_attempt_at"
	EffectSetAvailableAt   EffectKind = "set_available_at"
	// EffectSetDeferReason writes why a run is not running now. Its argument
	// is the reason, so a deferred run can never end up without one (I14).
	EffectSetDeferReason EffectKind = "set_defer_reason"
	// EffectEmit is the run_events row for the transition, exactly one per
	// transition, committed with it (G10). Its argument is the event name.
	EffectEmit EffectKind = "emit"
)

type Event 

type Event string

Event is something that happened to a run or to a step. Events are the whole input alphabet of both machines: nothing changes state except by one of them, and a machine that does not name a pair (state, event) refuses it.

The set is shared by the two machines on purpose. A pair such as (run, step_succeeded) is then a refusal the cross table proves, not a name that happens not to exist. 

const (
	// EvClaim is an executor taking a queued run.
	EvClaim Event = "claim"
	// EvDeferred is the concurrency gate or a backoff pushing a queued run
	// forward in time. It is the event behind "deferred", which is not a
	// state (00 section 3.14).
	EvDeferred Event = "deferred"
	// EvStepStarted is a step beginning an attempt.
	EvStepStarted Event = "step_started"
	// EvStepSucceeded is a step attempt that exited cleanly.
	EvStepSucceeded Event = "step_succeeded"
	// EvStepFailed is a step attempt that did not.
	EvStepFailed Event = "step_failed"
	// EvUpstreamFailed is a step that will never run because a step it needs
	// failed. The model exposes the transition; which steps it applies to is
	// the DAG closure in M4-03.
	EvUpstreamFailed Event = "upstream_failed"
	// EvAllStepsDone is the run's steps having all reached a terminal state.
	EvAllStepsDone Event = "all_steps_done"
	// EvCancelObserved is the owner or the reaper seeing cancel_requested_at.
	// The request is durable before anything is killed (02 section 5.8), so
	// requesting and observing are two different things and only the second
	// one is an event here.
	EvCancelObserved Event = "cancel_observed"
	// EvLeaseExpired is the reaper finding a run whose lease ran out.
	EvLeaseExpired Event = "lease_expired"
	// EvOperatorRetry is a person reopening a finished run. It is the only
	// event that leads out of a terminal state (02 T14).
	EvOperatorRetry Event = "operator_retry"
	// EvShutdownDrain is the daemon giving in flight work back during its own
	// clean stop (05 section 3.2, point 4). On a step it sends the running
	// attempt back to pending with the attempt restored, because a daemon
	// restart is not the user's fault and must not spend a retry. On a run it
	// hands a claimed run back to the queue without counting a crash: the
	// executor left on purpose, which is the opposite of what lease_expired
	// means, so the two share no transition.
	EvShutdownDrain Event = "shutdown_drain"
)

func AllEvents 

func AllEvents() []Event

AllEvents is the closed input alphabet, in the order the cross table prints it. Like the state sets it is a function, so the alphabet cannot be edited underneath a caller.

func (Event) String 

func (e Event) String() string

type GuardError 

type GuardError struct {
	From  State
	Event Event
	To    State
	Want  error
}

GuardError is a transition the machine names but the guards refuse. Want is the sentinel the refusal matches, and the fields say which transition asked for what, so the message names the outcome that was denied rather than only the rule that denied it.

func (GuardError) Error 

func (e GuardError) Error() string

func (GuardError) Unwrap 

func (e GuardError) Unwrap() error

type Guards 

type Guards struct {
	// Now and AvailableAt are unix milliseconds UTC, the unit of every time
	// column in the database. A run is available when AvailableAt is at or
	// before Now, the same comparison the claim gate in SQL makes.
	Now         int64
	AvailableAt int64
	// CancelRequested is cancel_requested_at being set on the run.
	CancelRequested bool
	// LeaseValid is the caller holding the run's lease at the current epoch.
	// A caller whose lease has gone is a stale writer and may not finish or
	// cancel the run; the reaper's EvLeaseExpired is the way that run moves.
	LeaseValid bool
	// AttemptsLeft is the step having retries left under its policy. The
	// backoff itself is M1-09; the model only says the retry transition is
	// allowed.
	AttemptsLeft bool
	// AnyStepFailed and AllStepsTerminal describe the run's steps. Together
	// they are how the run machine enforces I2 and I10 without reading a
	// single step row itself.
	AnyStepFailed    bool
	AllStepsTerminal bool
	// CrashBudgetLeft is the poison quarantine (02 section 5.7): a run that
	// has crashed too often is failed instead of requeued.
	CrashBudgetLeft bool
	// ReasonCode is the explanation for a transition that needs one. Every
	// terminal state does (06 section 2.1), and so does the retry transition,
	// which records why the attempt failed. The catalogue of codes is M1-05;
	// the model only insists that there is one.
	ReasonCode string
	// DeferReason is why a run was pushed forward in time. A deferred run
	// always has one (I14), which is what makes deferral explainable without
	// a state of its own.
	DeferReason string
}

Guards is everything a machine is allowed to know beyond the current state and the event. It is a plain value: the machine reads it, never the database, the filesystem or the clock. Time arrives as Now, because internal/clock owns time.Now and the model must stay deterministic (M0-09).

Every field is read by at least one transition. A field nothing reads would suggest an enforcement that does not exist, so the cross table's outcome columns are the proof that each one carries weight.

type IllegalTransitionError 

type IllegalTransitionError struct {
	From  State
	Event Event
}

IllegalTransitionError is a refusal that names both sides of it, so the message stands on its own in a log and in explain (M5-01).

func (IllegalTransitionError) Error 

func (e IllegalTransitionError) Error() string

func (IllegalTransitionError) Unwrap 

func (e IllegalTransitionError) Unwrap() error

type Input 

type Input struct {
	Event  Event
	Guards Guards
}

Input is one event together with the guards it is judged under. A sequence of them is a history, which is what makes replay possible.

type RunState 

type RunState string

RunState is where a run is in its life. The set is closed, and it is the same set the runs table's CHECK constraint spells out: two independent enforcements of one rule (07 section 7).

There are five states, not six. A deferred run is not a state of its own: it is a queued run whose available_at lies in the future, with a defer reason beside it (00 section 3.14, 01 section 4.1). Two states and every transition around them disappear, and the command line still prints "deferred (reason)" because IsDeferred computes it. 

const (
	RunQueued    RunState = "queued"
	RunRunning   RunState = "running"
	RunSucceeded RunState = "succeeded"
	RunFailed    RunState = "failed"
	RunCancelled RunState = "cancelled"
)

func AllRunStates 

func AllRunStates() []RunState

AllRunStates is the closed set, in life order. It is a function rather than a variable so no caller can rewrite the set for everybody else, and so the package holds no mutable global state at all.

func ParseRunState 

func ParseRunState(name string) (RunState, error)

ParseRunState turns a stored name back into a state. Anything outside the closed set is refused rather than carried, because a row the model cannot interpret is a row nothing downstream can explain.

func RunAggregate 

func RunAggregate(steps []StepState) RunState

RunAggregate is the run state a set of steps implies (I10). It is the same function in the engine (M1-08) and in fsck (M1-12): one that computes the run state and one that checks it cannot disagree if they are the same code.

The order of the tests is the meaning. An active step outranks everything, because a run with work left has not ended, whatever else happened. A failure outranks a cancellation, because a run that failed and was then cancelled still failed. Skipped counts as success: a skip is a decision, not a failure.

A run with no steps has nothing outstanding and nothing failed, so it succeeded. Nothing materialises such a run, because a job with no steps does not validate, and this is what the model says if one ever appears.

func (RunState) IsTerminal 

func (s RunState) IsTerminal() bool

IsTerminal is the end of the run. Only EvOperatorRetry leads out of it (02 T14), which NextRunState enforces and TestOnlyOperatorRetryLeavesTerminal proves for every other event.

func (RunState) Kind 

func (s RunState) Kind() string

func (RunState) RequiresReasonCode 

func (s RunState) RequiresReasonCode() bool

RequiresReasonCode is the rule from 06 section 2.1: nothing reaches an end without an explanation. It is a separate predicate from IsTerminal even though the two agree today, because callers that write "a reason code is required here" should not have to know that terminality is the reason.

func (RunState) String 

func (s RunState) String() string

type State 

type State interface {
	// String is the name stored in the database and printed to people.
	String() string
	// Kind is the machine the state belongs to, "run" or "step".
	Kind() string
	// IsTerminal reports whether the state accepts no further work.
	IsTerminal() bool
	// RequiresReasonCode reports whether a transition into this state has to
	// carry a reason code.
	RequiresReasonCode() bool
}

State is what the two machines have in common. It exists so one error type can name the state it refused, whichever machine produced it, and so a caller that only asks "is this finished" does not need to know which machine it holds.

type StepState 

type StepState string

StepState is where one step of a run is in its life. Six states, and the same closed set as the steps table's CHECK constraint. 

const (
	StepPending   StepState = "pending"
	StepRunning   StepState = "running"
	StepSucceeded StepState = "succeeded"
	StepFailed    StepState = "failed"
	StepSkipped   StepState = "skipped"
	StepCancelled StepState = "cancelled"
)

func AllStepStates 

func AllStepStates() []StepState

AllStepStates is the closed set, in life order.

func ParseStepState 

func ParseStepState(name string) (StepState, error)

ParseStepState turns a stored name back into a step state.

func (StepState) IsTerminal 

func (s StepState) IsTerminal() bool

IsTerminal is the end of the step. Unlike a run, a terminal step accepts no event at all: an operator reopens a run, and the engine materialises its steps again.

func (StepState) Kind 

func (s StepState) Kind() string

func (StepState) RequiresReasonCode 

func (s StepState) RequiresReasonCode() bool

func (StepState) String 

func (s StepState) String() string

type UnknownStateError 

type UnknownStateError struct {
	Kind string
	Name string
}

UnknownStateError is a name that is not in the closed set of either machine.

func (UnknownStateError) Error 

func (e UnknownStateError) Error() string

func (UnknownStateError) Unwrap 

func (e UnknownStateError) Unwrap() error

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.