// SPDX-FileCopyrightText: 2026 Scientific Computing Studio, LLC // SPDX-License-Identifier: Apache-2.0 // The prover's "proved" must be a proof. Two gates hold it to that: // // 1. The regression programs in library/pseudo/prover/ each name, in a `// MUST-NOT-PROVE: @` // header, an obligation that a run of the program breaks. Each one was proved by an unsound // rule once; the rule is fixed, and the obligation may never be proved again. A program whose // fix was to the language instead (a run that now stops where it used to go on outside what a // proof covers) names where it stops with `// RUN-STOPS: @`. // 2. Across every exercise, every corpus program, every lesson solution and those regression // programs, no obligation the prover marks proved is broken by the fuzzer (matched by kind, // line and column) or by running the program as written (matched by kind and line). // // A regression program that needs input says so one line at a time, `// INPUT: ` (as library/pseudo/programs/ // does), and one that is a call of a subroutine says `// CALL: `. A program may name both an obligation that // must not be proved and where its run stops, when the run reports the failure on another line than the obligation's. // // A failure here is a soundness bug in src/engines/pseudo/vcgen.js or solver.js: fix the rule, // never the test. Add the program that found it to library/pseudo/prover/. import test from 'node:test'; import assert from 'node:assert/strict'; import fs from 'node:fs'; import path from 'node:path'; import { studyOf, runPseudo } from '../dist/services/pseudo.js'; import { verify } from '../dist/engines/pseudo/vcgen.js'; import { checkProperties } from '../dist/engines/pseudo/testing.js'; import { PROBLEMS } from '../dist/common/problems.js'; import { LESSONS, solutionOf } from '../dist/curriculum/index.js'; import { NO_CLOCK } from './helpers/pace.mjs'; const PROVER_DIR = 'library/pseudo/prover'; const CORPUS_DIR = 'library/pseudo/programs'; /** The verifier's obligation kinds against the runtime error kinds a run or the fuzzer reports. */ const RUNTIME_KIND = { index: 'index', slice: 'index', key: 'key', divide: 'divide', argument: 'value', require: 'require', ensure: 'ensure', assert: 'assert', 'invariant-init': 'invariant', 'invariant-keep': 'invariant', 'decreases-bound': 'decreases', 'decreases-step': 'decreases', }; /** What a program's header says a run of it needs: its INPUT lines, and the call to make instead of the main program. */ function runOptions(src) { const input = [...src.matchAll(/^\/\/ INPUT: (.*)$/gm)].map((m) => m[1]); const call = /^\/\/ CALL: (.*)$/m.exec(src)?.[1]; return call ? { input, call } : { input }; } /** The half of a contract an obligation is about, as a runtime error names it. */ const PHASE = { 'invariant-init': 'init', 'invariant-keep': 'keep', 'decreases-bound': 'bound', 'decreases-step': 'step' }; function programs() { const out = []; for (const f of fs.readdirSync(PROVER_DIR).sort()) out.push({ name: `prover/${f}`, src: fs.readFileSync(path.join(PROVER_DIR, f), 'utf8') }); for (const f of fs.readdirSync(CORPUS_DIR).sort()) out.push({ name: `corpus/${f}`, src: fs.readFileSync(path.join(CORPUS_DIR, f), 'utf8') }); for (const p of PROBLEMS) if (p.sources.pseudo) out.push({ name: `exercise ${p.id}`, src: p.sources.pseudo }); for (const L of LESSONS) { if (L.solution?.pseudo) out.push({ name: `lesson ${L.id} solution`, src: solutionOf(L.solution) }); if (L.example?.pseudo) out.push({ name: `lesson ${L.id} example`, src: L.example.pseudo }); } return out; } /** Every proved obligation of a program that a run or the fuzzer breaks, as messages. */ function unsoundIn(src) { const st = studyOf(src); if (!st.ok) return { parsed: false, bad: [], proved: [] }; const program = st.program.program; const r = verify(program, NO_CLOCK); const proved = r.units.filter((u) => !u.partial).flatMap((u) => u.obligations.filter((o) => o.status === 'proved')); const failures = []; for (const sub of program.subs.values()) { try { failures.push(...checkProperties(program, sub.name, { count: 300, maxFailures: 50 }).failures); } catch { /* parameters it cannot generate */ } } let run = null; try { run = runPseudo(st, runOptions(src)); } catch { /* a program that needs input it cannot have */ } if (run?.error) failures.push({ kind: run.error.kind, line: run.error.line, col: undefined, phase: run.raw?.error?.phase, call: '(the program as written)', message: run.error.message }); const bad = []; for (const o of proved) { const kind = RUNTIME_KIND[o.kind] || o.kind; // a failure that says which half of a contract it broke (phase) counts against that obligation only const hit = failures.find((f) => f.kind === kind && f.line === o.line && (f.col === undefined || f.col === o.col) && (!f.phase || !PHASE[o.kind] || f.phase === PHASE[o.kind])); if (hit) bad.push(`${o.kind}@${o.line}:${o.col} "${o.label}" is marked proved, and ${hit.call} breaks it: ${hit.message}`); } return { parsed: true, bad, proved, obligations: r.units.flatMap((u) => u.obligations) }; } test('regression programs: an obligation an unsound rule once proved is never proved again', () => { const files = fs.readdirSync(PROVER_DIR).filter((f) => f.endsWith('.pseudo')); assert.ok(files.length >= 5, 'the regression programs are missing'); for (const f of files) { const src = fs.readFileSync(path.join(PROVER_DIR, f), 'utf8'); const marks = [...src.matchAll(/^\/\/ MUST-NOT-PROVE: ([a-z-]+)@(\d+)\s*$/gm)].map((m) => ({ kind: m[1], line: Number(m[2]) })); const stops = [...src.matchAll(/^\/\/ RUN-STOPS: ([a-z-]+)@(\d+)\s*$/gm)].map((m) => `${m[1]}@${m[2]}`); assert.ok(marks.length || stops.length, `${f} has no MUST-NOT-PROVE or RUN-STOPS line`); if (stops.length) { const run = runPseudo(studyOf(src), runOptions(src)); assert.ok(run.error && stops.includes(`${run.error.kind}@${run.error.line}`), `${f}: the run should stop at ${stops.join(' or ')}, and ${run.error ? `stopped at ${run.error.kind}@${run.error.line}` : 'it finished'}`); } const st = studyOf(src); assert.ok(st.ok, `${f} does not parse`); const r = verify(st.program.program, NO_CLOCK); const all = r.units.flatMap((u) => u.obligations); for (const m of marks) { const o = all.filter((x) => x.kind === m.kind && x.line === m.line); assert.ok(o.length, `${f}: there is no ${m.kind} obligation on line ${m.line}; the checker must ask the question before it can answer it`); for (const x of o) assert.notEqual(x.status, 'proved', `${f}: ${m.kind}@${m.line} "${x.label}" is proved, and a run of this program breaks it`); } } }); test('regression programs stay meaningful: each one, run or fuzzed, really breaks what it names', () => { for (const f of fs.readdirSync(PROVER_DIR).filter((x) => x.endsWith('.pseudo'))) { const src = fs.readFileSync(path.join(PROVER_DIR, f), 'utf8'); const st = studyOf(src); const program = st.program.program; const kinds = []; try { const run = runPseudo(st, runOptions(src)); if (run.error) kinds.push(`${run.error.kind}@${run.error.line}`); } catch { /* none */ } // a program that names where its run stops, and stops there, has shown its failure: the obligation it names sits on another line const stops = [...src.matchAll(/^\/\/ RUN-STOPS: ([a-z-]+)@(\d+)\s*$/gm)].map((m) => `${m[1]}@${m[2]}`); if (stops.some((x) => kinds.includes(x))) continue; for (const sub of program.subs.values()) { try { for (const fl of checkProperties(program, sub.name, { count: 300, maxFailures: 50 }).failures) kinds.push(`${fl.kind}@${fl.line}`); } catch { /* none */ } } for (const m of src.matchAll(/^\/\/ MUST-NOT-PROVE: ([a-z-]+)@(\d+)\s*$/gm)) { const want = `${RUNTIME_KIND[m[1]] || m[1]}@${m[2]}`; assert.ok(kinds.includes(want), `${f}: nothing breaks ${m[1]}@${m[2]} (saw ${kinds.join(', ') || 'no failure'}), so the program no longer tests the rule`); } } }); test('nothing the prover proves is broken by a run or by generated inputs', () => { const problems = []; let proved = 0; let checked = 0; for (const p of programs()) { const r = unsoundIn(p.src); if (!r.parsed) continue; checked++; proved += r.proved.length; for (const b of r.bad) problems.push(`${p.name}: ${b}`); } assert.ok(checked >= 100, `only ${checked} programs were checked`); assert.ok(proved >= 150, `only ${proved} proved obligations were checked`); assert.deepEqual(problems, []); }); test('canary: after a program that runs to its end, ASSERT 1 == 2 is never proved', () => { // A false claim proved at a point every run reaches means the checker holds a contradiction // there: some rule assumed a fact a run can break. This finds such a rule even when no // program happens to assert something false after it (library/pseudo/prover/foreach-empty.pseudo). const problems = []; let canaries = 0; for (const p of programs()) { const st = studyOf(p.src); if (!st.ok || /^\s*INPUT\b/m.test(p.src)) continue; let run; try { run = runPseudo(st, {}); } catch { continue; } if (run.error || run.truncated) continue; const lines = p.src.replace(/\s+$/, '').split('\n'); const line = lines.length + 1; const withCanary = studyOf(`${lines.join('\n')}\nASSERT 1 == 2\n`); if (!withCanary.ok) continue; const r = verify(withCanary.program.program, NO_CLOCK); const main = r.units.find((u) => u.kind === 'main'); const o = main?.obligations.find((x) => x.kind === 'assert' && x.line === line); if (!o) continue; canaries++; if (o.status === 'proved') problems.push(`${p.name}: ASSERT 1 == 2 after the last line is proved`); } assert.ok(canaries >= 60, `only ${canaries} programs carried a canary`); assert.deepEqual(problems, []); }); test('a FUNCTION that RETURNS an ARRAY of written lengths hands back those lengths: known at the call, and checked in the run', () => { // known at the call: the store into G has nothing left to prove (15-game-of-life showed it open) const life = fs.readFileSync(path.join(CORPUS_DIR, '15-game-of-life.pseudo'), 'utf8'); const r = verify(studyOf(life).program.program, NO_CLOCK); assert.deepEqual(r.units.flatMap((u) => u.obligations).filter((o) => o.status !== 'proved').map((o) => `${o.kind}@${o.line} ${o.label}`), []); // and the fact is one a run keeps: a function that would hand back another length stops at its RETURN const wrong = 'FUNCTION Two(N : INTEGER) RETURNS ARRAY[2] OF INTEGER\n DECLARE L : LIST OF INTEGER\n FOR I <- 0 TO N\n APPEND(L, I)\n NEXT I\n RETURN L\nENDFUNCTION\nDECLARE A : ARRAY[2] OF INTEGER\nA <- Two(3)\nASSERT LENGTH(A) == 2\n'; const st = studyOf(wrong); assert.ok(st.ok, st.diagnostics.map((d) => d.message).join('; ')); const run = runPseudo(st, {}); assert.equal(`${run.error?.kind}@${run.error?.line}`, 'value@6', run.error?.message); const obs = verify(st.program.program, NO_CLOCK).units.flatMap((u) => u.obligations); assert.ok(obs.some((o) => o.line === 6 && o.status !== 'proved'), 'the RETURN of a list of unknown length is not proved to have 2 positions'); });