92 lines
5.8 KiB
JavaScript
92 lines
5.8 KiB
JavaScript
// SPDX-FileCopyrightText: 2026 Scientific Computing Studio, LLC
|
|
// SPDX-License-Identifier: Apache-2.0
|
|
// The fuzzer behind the Tests view (core/fuzz.ts): it says what it tried and what it checked, and what it reports
|
|
// is what the engines do. Run on every exercise, in pseudo and in Mojo.
|
|
import test from 'node:test';
|
|
import assert from 'node:assert/strict';
|
|
import { STRATEGY } from '../dist/common/fuzz.js';
|
|
import { Workspace } from '../dist/common/workspace.js';
|
|
import { PROBLEMS, problemById, workForProblem } from '../dist/common/problems.js';
|
|
|
|
|
|
const open = (p, lang, call) => { const st = workForProblem(p); st.lang = lang; if (call) st.call = call; return new Workspace(st); };
|
|
const ALL = [];
|
|
for (const p of PROBLEMS) for (const lang of ['pseudo', 'mojo']) if ((p.sources?.[lang] ?? '').trim()) ALL.push({ p, lang, s: open(p, lang) });
|
|
|
|
test('every report says what it tried, what it checked, and what happened, and adds up', () => {
|
|
let routines = 0;
|
|
for (const { p, lang, s } of ALL) {
|
|
for (const r of s.fuzz({ budget: 120 })) {
|
|
routines++;
|
|
const id = `${p.id} ${lang} ${r.name}`;
|
|
if (!r.cases.length) { assert.ok(r.problem, `${id}: an untested routine says why`); continue; }
|
|
assert.ok(r.checks.length >= 3, `${id}: the checks are listed`);
|
|
assert.equal(r.params.length, (r.signature.match(/\(([^)]*)\)/)?.[1].trim() ? r.signature.match(/\(([^)]*)\)/)[1].split(',').length : 0), `${id}: one generator per parameter`);
|
|
for (const prm of r.params) assert.ok(prm.how.length > 10, `${id}: ${prm.name}'s generator is described`);
|
|
assert.equal(r.strategies.reduce((a, x) => a + x.count, 0), r.cases.length, `${id}: the strategies' counts add up to the cases`);
|
|
for (const x of r.strategies) assert.ok(STRATEGY[x.id], `${id}: ${x.id} is a known strategy`);
|
|
assert.equal(Object.values(r.counts).reduce((a, b) => a + b, 0), r.cases.length, `${id}: the outcomes add up`);
|
|
const tried = r.cases.filter((c) => c.strategy !== 'shrink' && c.strategy !== 'repeat');
|
|
assert.ok(tried.length <= r.budget, `${id}: the budget holds`);
|
|
assert.equal(new Set(r.cases.filter((c) => c.strategy !== 'repeat').map((c) => c.call)).size, r.cases.filter((c) => c.strategy !== 'repeat').length, `${id}: no input is tried twice (except to repeat it)`);
|
|
r.cases.forEach((c, i) => assert.equal(c.n, i + 1));
|
|
for (const c of r.coverage) assert.ok(c.inputs <= r.cases.length && (c.inputs === 0) === (c.hits === 0), `${id}: line ${c.line}'s coverage`);
|
|
if (r.cases.some((c) => c.outcome === 'pass')) assert.ok(r.coverage.some((c) => c.inputs > 0), `${id}: passing inputs reach lines`);
|
|
for (const c of r.cases) if (c.outcome === 'fail') assert.ok(c.message, `${id}: a failed case says what went wrong`);
|
|
for (const f of r.failures) {
|
|
assert.equal(f.shrink[0], f.found, `${id}: shrinking starts at the input that found it`);
|
|
assert.equal(f.shrink[f.shrink.length - 1], f.call, `${id}: and ends at the one reported`);
|
|
}
|
|
}
|
|
}
|
|
assert.ok(routines >= 30, `the exercises have routines to fuzz (${routines})`);
|
|
});
|
|
|
|
test('the same seed makes the same inputs; another seed makes others', () => {
|
|
const s = open(problemById('count-base'), 'pseudo');
|
|
const a = s.fuzz({ seed: 7, budget: 100 })[0].cases.map((c) => c.call);
|
|
const b = new Workspace(s.state).fuzz({ seed: 7, budget: 100 })[0].cases.map((c) => c.call);
|
|
const c = s.fuzz({ seed: 8, budget: 100 })[0].cases.map((c) => c.call);
|
|
assert.deepEqual(a, b);
|
|
assert.notDeepEqual(a, c);
|
|
// the edge cases and every short string do not depend on the seed; only the random and mutated ones do
|
|
const first = (xs) => xs.slice(0, 40);
|
|
assert.deepEqual(first(a), first(c));
|
|
});
|
|
|
|
test('the off-by-one bug is found, shrunk to its smallest input, and stepping that input fails the same way', () => {
|
|
const s = open(problemById('match-off-by-one'), 'pseudo');
|
|
const [r] = s.fuzz();
|
|
assert.ok(r.failures.length >= 1, 'the bug is found');
|
|
const f = r.failures[0];
|
|
assert.match(f.call, /^MATCH\(/);
|
|
assert.ok(f.shrink.length >= 1);
|
|
// shrinking never makes an input bigger
|
|
const size = (call) => call.replace(/[^ACGTN]/g, '').length;
|
|
for (let i = 1; i < f.shrink.length; i++) assert.ok(size(f.shrink[i]) <= size(f.shrink[i - 1]), 'each step is no bigger');
|
|
// the stepper on that call stops with the same kind of error, on the same line
|
|
const run = open(problemById('match-off-by-one'), 'pseudo', f.call).trace();
|
|
assert.ok(run.error, 'the run stops');
|
|
assert.equal(run.error.line, f.line);
|
|
// and the brief report the home page reads agrees
|
|
assert.ok(s.tests()[0].failures.some((x) => x.call === f.call));
|
|
});
|
|
|
|
test('coverage-guided mutation: the inputs that reached new lines are the ones mutated', () => {
|
|
const [r] = open(problemById('tally'), 'mojo').fuzz();
|
|
const fresh = r.cases.filter((c) => c.newLines?.length);
|
|
assert.ok(fresh.length >= 1, 'some inputs reach lines nothing earlier reached');
|
|
assert.ok(r.cases.some((c) => c.strategy === 'mutate'), 'and mutations of them are tried');
|
|
const reached = new Set(fresh.flatMap((c) => c.newLines));
|
|
for (const c of r.coverage) if (c.inputs) assert.ok(reached.has(c.line), `line ${c.line} was first reached by a case marked new`);
|
|
});
|
|
|
|
test('a REQUIRE skips an input instead of failing it, and says so', () => {
|
|
const withRequire = ALL.filter(({ lang, s }) => lang === 'pseudo' && s.fuzz({ budget: 120 }).some((r) => r.checks.some((c) => /break a REQUIRE \(/.test(c))));
|
|
for (const { s } of withRequire) for (const r of s.fuzz({ budget: 120 })) for (const c of r.cases) if (c.outcome === 'skip') assert.ok(c.kind === 'require' || c.kind === 'declined');
|
|
});
|
|
|
|
test('every report repeats some inputs to check the answer does not change', () => {
|
|
for (const { s } of ALL.slice(0, 12)) for (const r of s.fuzz({ budget: 120 })) if (r.counts.pass > 8) assert.ok(r.cases.some((c) => c.strategy === 'repeat'), r.name);
|
|
});
|