Skip to content

Commit 75f29c5

Browse files
committed
test(run-state): cover the turn events in the kernel model checker
1 parent e3e37ed commit 75f29c5

2 files changed

Lines changed: 117 additions & 3 deletions

File tree

‎docs/architecture/task-lifecycle-model.md‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -271,21 +271,22 @@ Add E2E coverage only when a lifecycle change crosses one of those runtime bound
271271

272272
`scripts/check-run-state-kernel.ts` explores the pure `nextRunState` in `src/core/task/run-state/runState.ts`. It is an independent submodel. It does not use `taskLifecycle.ts` and does not share state with the persisted graph.
273273

274-
The checker applies every event in every reachable state, within the generation and ask-timestamp caps. The budget is 20,000 states and the depth bound is 20. The stream generation and the ask timestamp are each at most 3. At each step it checks:
274+
The checker applies every event except the seven turn events in every reachable state, within the generation and ask-timestamp caps. The budget is 20,000 states and the depth bound is 20. The stream generation and the ask timestamp are each at most 3. At each step it checks:
275275

276276
- the result of the kernel against a transcription of the guard and effect table ([Transitions](task-lifecycle-target-architecture.md#transitions)), including that a rejection leaves the state unchanged;
277277
- the seven design-doc invariants (same document, Invariants);
278278
- the kernel does not mutate its state or its event, and the transition checks that hold without the table (latches, generation, phase, stream, and ask rules).
279279

280280
The checker also requires:
281281

282+
- the seven turn events (`turnStarted`, `firstChunkAwaitStarted`, `firstChunkAwaitEnded`, `toolRejected`, `toolUsed`, `toolFailed`, `streamReadCompleted`) to be accepted and to match the table in each of the 32 turn states, and in one state of every distinct shape of the reachable states. Every other event is also applied to the same shape states with all five turn fields true, so no other event may change the turn. The search does not include turn events, because they would multiply the state count by 32;
282283
- the event tags in `runState.ts` to equal the event tags in the table (once, at startup, as a text scan of `case` labels);
283284
- every event to be reachable, with the `askSettledStale` no-op, a settle for an ask that a newer pending ask replaced, as its own action;
284285
- every guard clause to be the only failing clause in some rejected event;
285286
- named witnesses, each tied to an event and the states around it: abort during a pending approval in a live stream, an ask after the stream ends, abandon after the stream ends, dispose after completion, a new stream after a failure cleanup without abort, a stream that starts without user input, an approval before the first stream, and a rejected late completion accept after a newer ask;
286287
- every ordered pair of the stream, ask, cancel, and dispose event sources to follow each other, where both events change the state;
287288
- no unseen successor at the depth bound;
288-
- thirty-one known-unsafe kernels, each of which the checker must reject. They include a throwing kernel, a kernel that returns nothing, and one kernel for each check that runs at every search step without the table; and
289+
- thirty-three known-unsafe kernels, each of which the checker must reject. They include a throwing kernel, a kernel that returns nothing, and one kernel for each check that runs at every search step without the table; and
289290
- self-tests that a small depth bound and a small state budget each fail the checker.
290291

291292
The kernel has no resume event. A resumed task is `initialized` followed by `streamStarted` or `askStarted`. The witnesses `first-stream-without-ask` and `approval-before-first-stream` cover those paths.

‎scripts/check-run-state-kernel.ts‎

Lines changed: 114 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@ import { fileURLToPath } from "node:url"
55
import { nextRunState, initialRunState } from "../src/core/task/run-state/runState"
66
import type { AbortReason, Ask, RunEvent, RunState, Transition } from "../src/core/task/run-state/runState"
77

8-
type Source = "init" | "stream" | "ask" | "cancel" | "dispose"
8+
type Source = "init" | "stream" | "ask" | "cancel" | "dispose" | "turn"
99
type EventTag = RunEvent["tag"]
1010
type StartedAsk = Exclude<Ask, { tag: "none" }>
1111
type Step = (state: RunState, event: RunEvent) => Transition | undefined
@@ -62,6 +62,20 @@ const askBuilders: Record<string, (askTs: number) => StartedAsk> = {
6262
other: (askTs) => ({ tag: "other", askTs }),
6363
}
6464
const eventSources = ["stream", "ask", "cancel", "dispose"] as const
65+
const turnTags = [
66+
"turnStarted",
67+
"firstChunkAwaitStarted",
68+
"firstChunkAwaitEnded",
69+
"toolRejected",
70+
"toolUsed",
71+
"toolFailed",
72+
"streamReadCompleted",
73+
] as const
74+
const turnEvent = (tag: (typeof turnTags)[number]): ModelEvent => ({
75+
name: `${tag}()`,
76+
source: "turn",
77+
event: { tag },
78+
})
6579

6680
// One field per cell of the state described in the target-architecture doc, so rows read like the doc table.
6781
interface Flat {
@@ -70,6 +84,11 @@ interface Flat {
7084
streamLive: boolean
7185
streamGeneration: number | null
7286
cleanupFinished: boolean | null
87+
waitingForFirstChunk: boolean
88+
toolRejected: boolean
89+
toolUsed: boolean
90+
toolFailed: boolean
91+
streamReadComplete: boolean
7392
askTag: Ask["tag"]
7493
askTs: number | null
7594
toolCallId: string | null
@@ -89,6 +108,7 @@ function flatten(run: RunState): Flat {
89108
streamLive: run.stream.tag === "live",
90109
streamGeneration: run.stream.tag === "live" ? run.stream.generation : null,
91110
cleanupFinished: run.stream.tag === "live" ? run.stream.cleanupFinished : null,
111+
...run.turn,
92112
askTag: ask.tag,
93113
askTs: ask.tag === "none" ? null : ask.askTs,
94114
toolCallId: ("toolCallId" in ask && ask.toolCallId) || null,
@@ -119,6 +139,17 @@ const rows: Rows = {
119139
guard: { uninitialized: (f) => f.phase === "uninitialized" },
120140
effect: (f) => void (f.phase = "running"),
121141
},
142+
turnStarted: {
143+
effect: (f) => {
144+
f.toolRejected = f.toolUsed = f.toolFailed = f.streamReadComplete = false
145+
},
146+
},
147+
firstChunkAwaitStarted: { effect: (f) => void (f.waitingForFirstChunk = true) },
148+
firstChunkAwaitEnded: { effect: (f) => void (f.waitingForFirstChunk = false) },
149+
toolRejected: { effect: (f) => void (f.toolRejected = true) },
150+
toolUsed: { effect: (f) => void (f.toolUsed = true) },
151+
toolFailed: { effect: (f) => void (f.toolFailed = true) },
152+
streamReadCompleted: { effect: (f) => void (f.streamReadComplete = true) },
122153
streamStarted: {
123154
guard: { running: (f) => f.phase === "running", "no live stream": (f) => !f.streamLive },
124155
effect: (f) => {
@@ -424,6 +455,62 @@ function formatCounterexample(message: string, trace: TraceStep[], options: Opti
424455
].join("\n")
425456
}
426457

458+
const dirtyTurn = {
459+
waitingForFirstChunk: true,
460+
toolRejected: true,
461+
toolUsed: true,
462+
toolFailed: true,
463+
streamReadComplete: true,
464+
}
465+
466+
const shapeOf = ({ run }: ModelState) =>
467+
canonical({
468+
phase: run.phase,
469+
generation: run.generation > 0,
470+
stream: run.stream.tag === "live" ? run.stream.cleanupFinished : "none",
471+
ask: run.ask.tag,
472+
latches: run.latches,
473+
lastCompletionAskTs: run.lastCompletionAskTs !== undefined,
474+
})
475+
476+
function checkTurnRegion(options: Options, searched: ModelState[], reachedActions: Set<string>): void {
477+
const shapes = new Map(searched.map((state) => [shapeOf(state), state]))
478+
const cases = [...shapes.values()].flatMap((state) => [
479+
{ state, events: [...eventsFor(state), ...turnTags.map(turnEvent)] },
480+
{ state: { ...state, run: { ...state.run, turn: dirtyTurn } }, events: eventsFor(state) },
481+
])
482+
const everyTurn = Array.from({ length: 32 }, (_, bits) => ({
483+
waitingForFirstChunk: Boolean(bits & 1),
484+
toolRejected: Boolean(bits & 2),
485+
toolUsed: Boolean(bits & 4),
486+
toolFailed: Boolean(bits & 8),
487+
streamReadComplete: Boolean(bits & 16),
488+
}))
489+
for (const turn of everyTurn) {
490+
const state = initialState()
491+
cases.push({ state: { ...state, run: { ...state.run, turn } }, events: turnTags.map(turnEvent) })
492+
}
493+
494+
for (const { state, events } of cases) {
495+
for (const modelEvent of events) {
496+
const applied = apply(options, state, modelEvent)
497+
const turnEventRejected = modelEvent.source === "turn" && !applied.accepted
498+
const problems = [
499+
...applied.problems,
500+
...(turnEventRejected ? [`${modelEvent.event.tag} was rejected`] : []),
501+
]
502+
if (problems.length) {
503+
const trace = [
504+
{ action: "initial", source: "initial" as const, state },
505+
{ action: modelEvent.name, source: modelEvent.source, state: applied.next },
506+
]
507+
throw new Error(formatCounterexample(problems.join("; "), trace, options))
508+
}
509+
if (modelEvent.source === "turn") reachedActions.add(modelEvent.event.tag)
510+
}
511+
}
512+
}
513+
427514
interface CheckResult {
428515
states: number
429516
deepest: number
@@ -490,6 +577,12 @@ function runModelCheck(options: Options): CheckResult {
490577
}
491578
}
492579

580+
checkTurnRegion(
581+
options,
582+
queue.map((node) => node.state),
583+
reachedActions,
584+
)
585+
493586
const assertNoneMissing = (label: string, names: string[]) => {
494587
if (names.length) throw new Error(`Run-state kernel model has ${label}: ${names.join(", ")}`)
495588
}
@@ -707,6 +800,26 @@ const unsafeKernels: Record<string, UnsafeKernel> = {
707800
caughtBy: /unreachable actions: disposeRequested$/,
708801
useTable: false,
709802
},
803+
"turn-start-clears-first-chunk-wait": {
804+
step: (state, event) => {
805+
const result = nextRunState(state, event)
806+
return event.tag === "turnStarted" && "ok" in result
807+
? { ok: { ...result.ok, turn: { ...result.ok.turn, waitingForFirstChunk: false } } }
808+
: result
809+
},
810+
caughtBy: differsFor("turnStarted"),
811+
useTable: true,
812+
},
813+
"stream-start-resets-turn": {
814+
step: (state, event) => {
815+
const result = nextRunState(state, event)
816+
return event.tag === "streamStarted" && "ok" in result
817+
? { ok: { ...result.ok, turn: { ...result.ok.turn, toolUsed: false } } }
818+
: result
819+
},
820+
caughtBy: differsFor("streamStarted"),
821+
useTable: true,
822+
},
710823
"completion-keeps-ask": {
711824
step: (state, event) => {
712825
const result = nextRunState(state, event)

0 commit comments

Comments
 (0)