|
| 1 | +/** Independent bounded abstraction; see docs/architecture/file-replacement-restart-model.md. */ |
| 2 | +import assert from "node:assert/strict" |
| 3 | + |
| 4 | +type Version = 0 | 1 | 2 |
| 5 | +type Phase = "publishing" | "idle" | "temp" | "backup" | "committed" | "crashed" | "reading" | "read" | "deleted" |
| 6 | +interface FileState { |
| 7 | + canonical: Version |
| 8 | + backup: Version |
| 9 | + temp: Version |
| 10 | + committed: Version |
| 11 | +} |
| 12 | +interface State { |
| 13 | + files: FileState[] |
| 14 | + phase: Phase |
| 15 | + target: number |
| 16 | + acknowledged: boolean |
| 17 | + lock: "none" | "live" | "fresh-crashed" | "stale" |
| 18 | + readIndex: number |
| 19 | + recoveryFailed: boolean |
| 20 | + deleted: boolean |
| 21 | +} |
| 22 | +interface Edge { |
| 23 | + action: string |
| 24 | + state: State |
| 25 | +} |
| 26 | +const FILES = ["ui", "api", "history"] as const |
| 27 | +const MAX_STATES = 10_000 |
| 28 | +const landmarks = new Set<string>() |
| 29 | + |
| 30 | +function edges(state: State, fixed: boolean): Edge[] { |
| 31 | + const result: Edge[] = [] |
| 32 | + function add(action: string, change: (next: State) => void) { |
| 33 | + const next = structuredClone(state) |
| 34 | + change(next) |
| 35 | + result.push({ action, state: next }) |
| 36 | + } |
| 37 | + if (state.phase === "publishing") { |
| 38 | + // Separate file publications: UI visibility does not acknowledge history publication. |
| 39 | + for (const [index, file] of state.files.entries()) { |
| 40 | + if (!file.canonical) |
| 41 | + add(`publish-${FILES[index]}`, (next) => { |
| 42 | + next.files[index] = { canonical: 1, backup: 0, temp: 0, committed: 1 } |
| 43 | + if (next.files.every((entry) => entry.canonical)) next.phase = "idle" |
| 44 | + }) |
| 45 | + } |
| 46 | + } |
| 47 | + if (state.phase === "idle" && !state.acknowledged) { |
| 48 | + add("acknowledge-all-three-files", (next) => { |
| 49 | + next.acknowledged = true |
| 50 | + }) |
| 51 | + } |
| 52 | + if (state.phase === "idle" && state.acknowledged) { |
| 53 | + for (const index of [0, 1, 2]) |
| 54 | + add(`stage-replacement-${FILES[index]}`, (next) => { |
| 55 | + next.target = index |
| 56 | + next.files[index].temp = 2 |
| 57 | + next.phase = "temp" |
| 58 | + next.lock = "live" |
| 59 | + }) |
| 60 | + } |
| 61 | + if (state.phase === "temp") { |
| 62 | + if (fixed) |
| 63 | + add("atomic-commit", (next) => { |
| 64 | + next.files[next.target].canonical = 2 |
| 65 | + next.files[next.target].committed = 2 |
| 66 | + next.files[next.target].temp = 0 |
| 67 | + next.phase = "committed" |
| 68 | + }) |
| 69 | + add(fixed ? "eperm-backup-rename" : "old-backup-rename", (next) => { |
| 70 | + const file = next.files[next.target] |
| 71 | + file.backup = file.canonical |
| 72 | + file.canonical = 0 |
| 73 | + next.phase = "backup" |
| 74 | + }) |
| 75 | + } |
| 76 | + if (state.phase === "backup") |
| 77 | + add("fallback-commit", (next) => { |
| 78 | + const file = next.files[next.target] |
| 79 | + file.canonical = file.temp |
| 80 | + file.committed = file.temp |
| 81 | + file.temp = 0 |
| 82 | + next.phase = "committed" |
| 83 | + }) |
| 84 | + // One process crash, at every publication/replacement boundary, including post-commit cleanup. |
| 85 | + if (["publishing", "idle", "temp", "backup", "committed"].includes(state.phase)) { |
| 86 | + add("process-crash", (next) => { |
| 87 | + next.phase = "crashed" |
| 88 | + next.lock = state.lock === "live" ? "fresh-crashed" : "none" |
| 89 | + }) |
| 90 | + } |
| 91 | + if (state.lock === "fresh-crashed") |
| 92 | + add("lock-becomes-stale", (next) => { |
| 93 | + next.lock = "stale" |
| 94 | + }) |
| 95 | + if (state.phase === "crashed") |
| 96 | + add("fresh-host-startup", (next) => { |
| 97 | + next.phase = "reading" |
| 98 | + }) |
| 99 | + if (state.phase === "reading") { |
| 100 | + const file = state.files[state.readIndex] |
| 101 | + if (file.canonical || !fixed || (!file.backup && !file.temp)) { |
| 102 | + add(`read-${FILES[state.readIndex]}`, (next) => { |
| 103 | + next.readIndex++ |
| 104 | + if (next.readIndex === FILES.length) next.phase = "read" |
| 105 | + }) |
| 106 | + } else if (state.lock !== "fresh-crashed") { |
| 107 | + // Failed scan/access/stat/rename preserves every committed byte and permits retry. |
| 108 | + if (!state.recoveryFailed) |
| 109 | + add("recovery-io-failure", (next) => { |
| 110 | + next.recoveryFailed = true |
| 111 | + }) |
| 112 | + add("locked-reader-recovery", (next) => { |
| 113 | + const recovering = next.files[next.readIndex] |
| 114 | + recovering.canonical = recovering.backup |
| 115 | + recovering.backup = 0 |
| 116 | + recovering.temp = 0 |
| 117 | + next.lock = "none" |
| 118 | + }) |
| 119 | + } |
| 120 | + } |
| 121 | + if (["crashed", "read"].includes(state.phase) && state.lock !== "fresh-crashed") { |
| 122 | + add("explicit-delete-under-lock", (next) => { |
| 123 | + next.files = next.files.map(() => ({ canonical: 0, backup: 0, temp: 0, committed: 0 })) |
| 124 | + next.phase = "deleted" |
| 125 | + next.deleted = true |
| 126 | + next.lock = "none" |
| 127 | + }) |
| 128 | + } |
| 129 | + if (state.phase === "deleted") |
| 130 | + add("read-after-delete", (next) => { |
| 131 | + next.phase = "read" |
| 132 | + }) |
| 133 | + return result |
| 134 | +} |
| 135 | + |
| 136 | +function violation(state: State): string | undefined { |
| 137 | + if (state.deleted && state.files.some((file) => file.canonical || file.backup)) return "deleted history resurrected" |
| 138 | + if (state.acknowledged && !state.deleted) { |
| 139 | + if (state.files.some((file) => file.canonical !== file.committed && file.backup !== file.committed)) { |
| 140 | + return "last committed content lost" |
| 141 | + } |
| 142 | + if (state.phase === "read" && state.files.some((file) => file.canonical !== file.committed)) { |
| 143 | + return "acknowledged task not discoverable/recoverable on fresh startup (#2130)" |
| 144 | + } |
| 145 | + } |
| 146 | + return undefined |
| 147 | +} |
| 148 | + |
| 149 | +function explore(fixed: boolean): number { |
| 150 | + const initial: State = { |
| 151 | + files: FILES.map(() => ({ canonical: 0, backup: 0, temp: 0, committed: 0 })), |
| 152 | + phase: "publishing", |
| 153 | + target: 0, |
| 154 | + acknowledged: false, |
| 155 | + lock: "none", |
| 156 | + readIndex: 0, |
| 157 | + recoveryFailed: false, |
| 158 | + deleted: false, |
| 159 | + } |
| 160 | + const queue = [{ state: initial, trace: [] as string[] }] |
| 161 | + const seen = new Set([JSON.stringify(initial)]) |
| 162 | + for (let index = 0; index < queue.length; index++) { |
| 163 | + const { state, trace } = queue[index] |
| 164 | + const error = violation(state) |
| 165 | + if (error) { |
| 166 | + if (!fixed && error.includes("#2130")) { |
| 167 | + console.log(`Old protocol #2130 counterexample: ${trace.join(" -> ")}`) |
| 168 | + return seen.size |
| 169 | + } |
| 170 | + throw new Error(`${error}: ${trace.join(" -> ")}\n${JSON.stringify(state)}`) |
| 171 | + } |
| 172 | + if (fixed) { |
| 173 | + if (state.phase === "crashed" && state.files[0].canonical && !state.files[2].canonical) |
| 174 | + landmarks.add("ui-visible-history-pending") |
| 175 | + if (state.phase === "read" && state.acknowledged && !state.deleted) landmarks.add("acknowledged-restart") |
| 176 | + if (state.phase === "read" && state.recoveryFailed && !state.deleted) |
| 177 | + landmarks.add("retry-after-recovery-failure") |
| 178 | + if (state.phase === "read" && state.deleted) landmarks.add("no-resurrection") |
| 179 | + if (state.phase === "committed" && !state.files[state.target].backup) landmarks.add("atomic-success") |
| 180 | + if (state.phase === "committed" && state.files[state.target].backup) landmarks.add("fallback-success") |
| 181 | + } |
| 182 | + for (const edge of edges(state, fixed)) { |
| 183 | + if (fixed && edge.action === "recovery-io-failure") assert.deepEqual(edge.state.files, state.files) |
| 184 | + const key = JSON.stringify(edge.state) |
| 185 | + if (seen.has(key)) continue |
| 186 | + seen.add(key) |
| 187 | + assert.ok(seen.size <= MAX_STATES, "Replacement/restart state budget exceeded") |
| 188 | + queue.push({ state: edge.state, trace: [...trace, edge.action] }) |
| 189 | + } |
| 190 | + } |
| 191 | + assert.ok(fixed, "Old protocol must reproduce #2130") |
| 192 | + return seen.size |
| 193 | +} |
| 194 | + |
| 195 | +explore(false) |
| 196 | +const checked = explore(true) |
| 197 | +assert.equal(landmarks.size, 6, `Unreachable replacement/restart landmarks: ${[...landmarks]}`) |
| 198 | +console.log( |
| 199 | + `File replacement/restart model passed: ${checked} states, 3 files, initial publication + 1 replacement, 1 crash, 6/6 landmarks`, |
| 200 | +) |
0 commit comments