Skip to content

Commit ea07f15

Browse files
committed
fix(task): harden dead delegation recovery
1 parent 77a7302 commit ea07f15

4 files changed

Lines changed: 343 additions & 18 deletions

File tree

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

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,7 @@ TLA+/PlusCal or Quint with TLC becomes a better fit when the lifecycle needs tem
4646
| Atomic event step | `atomicReadAndUpdate`, `atomicUpdatePair`, and per-parent delegation transition lock |
4747
| Event interleaving | Competing completion, cancellation, abandonment, and new delegation calls |
4848

49-
The model has three fixed task slots, enough to cover competing siblings and a nested parent-child-grandchild chain. It explores every reachable interleaving through depth 12, deduplicating canonical states. Representative checks also exercise rejected operations that do not create a new state: a second concurrent delegation while the first child is active, stale completion after re-delegation, late completion after abandonment, completion after interruption, and nested completion. Named semantic landmarks require the graph to retain interrupted-child re-delegation, nested delegation, and recovery of a dead nested chain even when the raw state total changes. The recovery action represents a delegated intermediate task with no live runtime owner whose awaited chain terminates in an interrupted child.
49+
The model has three fixed task slots, enough to cover competing siblings and a nested parent-child-grandchild chain. It explores every reachable interleaving through depth 12, deduplicating canonical states. Runtime ownership is modeled separately from persisted status: an `owner-loss` fault can remove the live owner of an active or delegated child without changing its history record, matching process termination or session skip. Recovery is enabled only when the awaited delegation chain has no live owner and ends in an interrupted/completed task or a missing awaited record. Representative checks also exercise rejected operations that do not create a new state: a second concurrent delegation while the first child is active, stale completion after re-delegation, late completion after abandonment, completion after interruption, and nested completion. Named semantic landmarks require the graph to retain interrupted-child re-delegation, nested delegation, delegated owner loss, and dead-chain recovery even when the raw state total changes.
5050

5151
Production completion also accepts a recovery-compatible `active` parent that still awaits the returning child, then clears the stale pointers. Normal model transitions never create that intermediate state, so it is covered by a focused reducer test rather than admitted as a generally valid reachable state.
5252

@@ -115,6 +115,7 @@ The task delegation checker currently enforces:
115115
5. Parent-child lineage is acyclic.
116116
6. Completed task records cannot be changed by later lifecycle events.
117117
7. Active-child re-delegation, stale completion after ownership moves to another child, duplicate/late completion, and abandonment of a live child are rejected by the shared production guards. A delegated child may transition to `interrupted` only through dead-chain recovery after runtime liveness checks establish that neither it nor its descendants has a live owner.
118+
8. Runtime owner loss does not mutate persisted status. A delegated chain with no remaining live owner has a reachable recovery transition within the bounded graph, after which its parent can re-delegate.
118119

119120
The completion persistence checker additionally enforces:
120121

‎scripts/check-task-lifecycle.ts‎

Lines changed: 70 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -7,12 +7,13 @@ import {
77
completeDelegatedChild,
88
delegateTaskToChild,
99
interruptDelegatedChild,
10+
isDeadDelegationChain,
1011
recoverDeadDelegatedChild,
1112
} from "../src/core/task-persistence/taskLifecycle"
1213

1314
const taskIds = ["parent", "child-a", "child-b"] as const
1415
type TaskId = (typeof taskIds)[number]
15-
type ModelState = Record<TaskId, HistoryItem | undefined>
16+
type ModelState = Record<TaskId, HistoryItem | undefined> & { liveTaskIds: TaskId[] }
1617

1718
interface Transition {
1819
name: string
@@ -26,7 +27,7 @@ interface TraceStep {
2627

2728
const MAX_DEPTH = 12
2829
const MAX_STATES = 10_000
29-
const expectedActions = ["delegate", "interrupt", "recover", "complete", "abandon"] as const
30+
const expectedActions = ["delegate", "owner-loss", "interrupt", "recover", "complete", "abandon"] as const
3031
const semanticLandmarks = {
3132
"interrupted-child-redelegation": (state: ModelState) =>
3233
state.parent?.status === "delegated" &&
@@ -37,6 +38,8 @@ const semanticLandmarks = {
3738
state.parent.awaitingChildId === "child-a" &&
3839
state["child-a"]?.status === "delegated" &&
3940
state["child-a"].awaitingChildId === "child-b",
41+
"delegated-owner-loss": (state: ModelState) =>
42+
state["child-a"]?.status === "delegated" && !state.liveTaskIds.includes("child-a"),
4043
"dead-nested-chain-recovered": (state: ModelState) =>
4144
state.parent?.status === "delegated" &&
4245
state.parent.awaitingChildId === "child-a" &&
@@ -62,7 +65,7 @@ function task(id: TaskId, parentTaskId?: TaskId): HistoryItem {
6265
}
6366

6467
function initialState(): ModelState {
65-
return { parent: task("parent"), "child-a": undefined, "child-b": undefined }
68+
return { parent: task("parent"), "child-a": undefined, "child-b": undefined, liveTaskIds: ["parent"] }
6669
}
6770

6871
function replace(state: ModelState, ...updates: HistoryItem[]): ModelState {
@@ -71,6 +74,10 @@ function replace(state: ModelState, ...updates: HistoryItem[]): ModelState {
7174
return next
7275
}
7376

77+
function withLiveTasks(state: ModelState, ...liveTaskIds: TaskId[]): ModelState {
78+
return { ...state, liveTaskIds: Array.from(new Set(liveTaskIds)).sort() }
79+
}
80+
7481
function transitions(state: ModelState): Transition[] {
7582
const result: Transition[] = []
7683
for (const parentId of taskIds) {
@@ -84,9 +91,20 @@ function transitions(state: ModelState): Transition[] {
8491
continue
8592
}
8693
const delegated = delegateTaskToChild(parent, childId, awaitedStatus)
94+
const next = replace(state, delegated, task(childId, parentId))
8795
result.push({
8896
name: `delegate(${parentId}, ${childId})`,
89-
next: replace(state, delegated, task(childId, parentId)),
97+
next: withLiveTasks(next, ...state.liveTaskIds, childId),
98+
})
99+
}
100+
}
101+
102+
for (const taskId of state.liveTaskIds) {
103+
const current = state[taskId]
104+
if (current && current.parentTaskId && (current.status === "active" || current.status === "delegated")) {
105+
result.push({
106+
name: `owner-loss(${taskId})`,
107+
next: withLiveTasks(state, ...state.liveTaskIds.filter((id) => id !== taskId)),
90108
})
91109
}
92110
}
@@ -99,15 +117,23 @@ function transitions(state: ModelState): Transition[] {
99117

100118
if (parent.status === "delegated" && parent.awaitingChildId === child.id && child.status === "active") {
101119
const interrupted = interruptDelegatedChild(parent, child)
102-
result.push({ name: `interrupt(${childId})`, next: replace(state, interrupted) })
120+
result.push({
121+
name: `interrupt(${childId})`,
122+
next: withLiveTasks(replace(state, interrupted), ...state.liveTaskIds.filter((id) => id !== childId)),
123+
})
103124
}
104125

105-
if (parent.status === "delegated" && parent.awaitingChildId === child.id && child.status === "delegated") {
106-
const awaitedChild = child.awaitingChildId ? state[child.awaitingChildId as TaskId] : undefined
107-
if (awaitedChild?.status === "interrupted") {
108-
const recovered = recoverDeadDelegatedChild(parent, child)
109-
result.push({ name: `recover(${childId})`, next: replace(state, recovered) })
110-
}
126+
if (
127+
parent.status === "delegated" &&
128+
parent.awaitingChildId === child.id &&
129+
isDeadDelegationChain(
130+
child,
131+
(id) => state[id as TaskId],
132+
(id) => state.liveTaskIds.includes(id as TaskId),
133+
)
134+
) {
135+
const recovered = recoverDeadDelegatedChild(parent, child)
136+
result.push({ name: `recover(${childId})`, next: replace(state, recovered) })
111137
}
112138

113139
if (
@@ -118,20 +144,45 @@ function transitions(state: ModelState): Transition[] {
118144
const completed = completeDelegatedChild(parent, child, `${childId} result`)
119145
result.push({
120146
name: `complete(${childId})`,
121-
next: replace(state, completed.parent, completed.child),
147+
next: withLiveTasks(
148+
replace(state, completed.parent, completed.child),
149+
...state.liveTaskIds.filter((id) => id !== childId),
150+
child.parentTaskId as TaskId,
151+
),
122152
})
123153
}
124154

125155
if (parent.status === "delegated" && parent.awaitingChildId === child.id && child.status === "interrupted") {
126156
const abandoned = abandonDelegatedChild(parent, child)
127157
result.push({
128158
name: `abandon(${childId})`,
129-
next: replace(state, abandoned.parent, abandoned.child),
159+
next: withLiveTasks(
160+
replace(state, abandoned.parent, abandoned.child),
161+
...state.liveTaskIds.filter((id) => id !== childId),
162+
child.parentTaskId as TaskId,
163+
),
130164
})
131165
}
132166
}
167+
133168
return result
134169
}
170+
function deadDelegatedChildren(state: ModelState): TaskId[] {
171+
return taskIds.filter((childId) => {
172+
const child = state[childId]
173+
if (!child?.parentTaskId) return false
174+
const parent = state[child.parentTaskId as TaskId]
175+
return (
176+
parent?.status === "delegated" &&
177+
parent.awaitingChildId === child.id &&
178+
isDeadDelegationChain(
179+
child,
180+
(id) => state[id as TaskId],
181+
(id) => state.liveTaskIds.includes(id as TaskId),
182+
)
183+
)
184+
})
185+
}
135186

136187
function invariantViolations(state: ModelState): string[] {
137188
const violations: string[] = []
@@ -173,11 +224,16 @@ function invariantViolations(state: ModelState): string[] {
173224
cursor = state[cursor as TaskId]?.parentTaskId
174225
}
175226
}
227+
for (const childId of deadDelegatedChildren(state)) {
228+
if (!transitions(state).some((transition) => transition.name === `recover(${childId})`)) {
229+
violations.push(`${childId}: dead delegated chain must be recoverable in the next transition`)
230+
}
231+
}
176232
return violations
177233
}
178234

179235
function canonical(state: ModelState): string {
180-
return JSON.stringify(taskIds.map((id) => state[id] ?? null))
236+
return JSON.stringify({ tasks: taskIds.map((id) => state[id] ?? null), liveTaskIds: state.liveTaskIds })
181237
}
182238

183239
function formatCounterexample(message: string, trace: TraceStep[]): string {

0 commit comments

Comments
 (0)