Files
alexm 401084bab3
Test / gate (push) Failing after 19m0s
Initial commit
2026-11-12 22:23:54 -05:00

668 lines
43 KiB
JavaScript

// SPDX-FileCopyrightText: 2026 Scientific Computing Studio, LLC
// SPDX-License-Identifier: Apache-2.0
/**
* The generator behind `node scripts/mojo/fuzz.mjs --statements`: small whole pseudo programs, typed, so that most
* of what it writes is a program the pseudo's checker accepts and a run takes to its end. A program is a list of
* nodes (a statement, or a few that belong together) so the fuzzer can leave nodes out to repair or shrink it.
*
* programGenerator(rand).program() the top-level nodes of one program, from a seeded rand() in [0, 1)
* render(nodes, removed) its text without the removed nodes, and each line's chain of nodes
* allNodes(nodes) every node, outermost first
*
* What it keeps out, because the notation and Mojo do not share it: the order a SET or a map is visited in (a FOR
* EACH over one only adds things up), whole numbers past 2^53 (values stay small; a run that stops is left out),
* division by zero (the same), and printing a record or a map of collections, which Mojo cannot print or prints in
* its own order.
*/
/* ------------------------------------------------------------------ */
/* Random whole programs (--statements) */
/* ------------------------------------------------------------------ */
/**
* A statement is a node: the lines it writes at its own indentation and the blocks under it, in order, so a
* program can be repaired and shrunk by dropping nodes. `label` names what made it, for grouping findings.
*/
export const node = (label, ...parts) => ({ label, parts });
/** The text of a program with some nodes left out, and for each line the innermost node it belongs to. */
export function render(top, removed = new Set()) {
const lines = []; const owner = [];
const walk = (nodes, indent, parentStack) => {
for (const n of nodes) {
if (removed.has(n)) continue;
const stack = [...parentStack, n];
for (const p of n.parts) {
if (typeof p === 'string') { lines.push(`${' '.repeat(indent)}${p}`); owner.push(stack); }
else walk(p, indent + 1, stack);
}
}
};
walk(top, 0, []);
return { text: `${lines.join('\n')}\n`, owner };
}
/** Every node of a program, outermost first. */
export function allNodes(top) {
const out = [];
const walk = (nodes) => { for (const n of nodes) { out.push(n); for (const p of n.parts) if (typeof p !== 'string') walk(p); } };
walk(top);
return out;
}
const SCALAR = ['INTEGER', 'FLOAT', 'STRING', 'CHAR', 'BOOL'];
const SIZED_T = ['INT8', 'INT16', 'INT32', 'INT64', 'UINT8', 'UINT16', 'UINT32', 'UINT64', 'FLOAT32', 'FLOAT64'];
const isInt = (t) => t.k === 'INTEGER' || /^U?INT\d+$/.test(t.k);
const isNum = (t) => isInt(t) || t.k === 'FLOAT' || t.k === 'FLOAT32' || t.k === 'FLOAT64';
const isScalar = (t) => SCALAR.includes(t.k) || SIZED_T.includes(t.k);
const tt = (t) => {
switch (t.k) {
case 'LIST': return `LIST OF ${tt(t.of)}`;
case 'ARRAY': return `ARRAY[${t.dims.join(', ')}] OF ${tt(t.of)}`;
case 'HASHMAP': return `HASHMAP OF ${tt(t.key)} : ${tt(t.val)}`;
case 'SET': return `SET OF ${tt(t.of)}`;
case 'REC': return t.rec.name;
default: return t.k;
}
};
const same = (a, b) => tt(a) === tt(b);
const printable = (t) => isScalar(t) || ((t.k === 'LIST' || t.k === 'ARRAY' || t.k === 'SET') && printable(t.of) && t.of.k !== 'REC')
|| (t.k === 'HASHMAP' && isScalar(t.val));
/** Element types a SORT or SORTED puts in order the same way in both languages. */
const sortable = (t) => ['INTEGER', 'FLOAT', 'STRING', 'CHAR'].includes(t.k);
/** Names Mojo or its standard library gives a meaning to; a pseudo name may be one of them. */
const ODD_NAMES = ['Await', 'Async', 'Borrowed', 'Nonlocal', 'Origin', 'Some', 'Never', 'Swap', 'Hash', 'Iter', 'Zip', 'Any', 'All', 'Reversed',
'Enumerate', 'Exit', 'Rebind', 'Abort', 'Span', 'Pointer', 'Tuple', 'Optional', 'Variant', 'Error', 'Writer', 'Scalar', 'Simd', 'Object',
'Constrained', 'Lambda', 'Escaping', 'Capturing', 'Where', 'Isinstance', 'Let', 'Debug_assert', 'Bitcast', 'Materialize', 'Dict', 'Range', 'Slice', 'Iterator',
'Hashable', 'Copyable', 'Movable', 'Sized', 'Writable', 'Stringable', 'Equatable', 'Comparable', 'Defaultable', 'Absolute', 'Uint', 'Element', 'Value', 'Size', 'Count'];
const CAMEL = ['RunTotal', 'BestScore', 'MaxSeen', 'LastWord', 'GcCount', 'StepSize', 'HitCount', 'WordList', 'NextPos', 'TopItem'];
const snakeCaps = (n) => n.replace(/([a-z0-9])([A-Z])/g, '$1_$2').toUpperCase();
class TooDeep extends Error { }
export function programGenerator(rand) {
const pick = (xs) => xs[Math.floor(rand() * xs.length)];
const some = (p) => rand() < p;
const int = (lo, hi) => lo + Math.floor(rand() * (hi - lo + 1));
const weighted = (pairs) => { const total = pairs.reduce((n, [, w]) => n + w, 0); let r = rand() * total; for (const [x, w] of pairs) { r -= w; if (r < 0) return x; } return pairs[0][0]; };
let counter = 0; let tags = 0;
const used = new Set();
const twins = [];
/** A name for something new: mostly a stem and a number, sometimes CamelCase, a word Mojo knows, or the snake-case twin of a name already made. */
const fresh = (stem) => {
if (some(0.04) && twins.length) { const t = twins.shift(); if (!used.has(t.toUpperCase())) { used.add(t.toUpperCase()); return t; } }
if (some(0.05)) { const w = pick(ODD_NAMES); if (!used.has(w.toUpperCase())) { used.add(w.toUpperCase()); return w; } }
let n;
if (some(0.08)) { n = `${pick(CAMEL)}${++counter}`; twins.push(snakeCaps(n)); } else n = `${stem}${++counter}`;
used.add(n.toUpperCase());
return n;
};
const records = []; const subs = []; const constants = [];
/* ---------- types ---------- */
const scalarT = () => ({ k: weighted([['INTEGER', 5], ['FLOAT', 3], ['STRING', 3], ['CHAR', 1], ['BOOL', 1.5], [pick(SIZED_T), 1.2]]) });
const elemT = () => weighted([[{ k: 'INTEGER' }, 4], [{ k: 'FLOAT' }, 1.5], [{ k: 'STRING' }, 2], [{ k: 'CHAR' }, 0.5], [{ k: 'BOOL' }, 0.5],
[{ k: 'LIST', of: { k: 'INTEGER' } }, 1], ...(records.length ? [[{ k: 'REC', rec: pick(records) }, 1.2]] : [])]);
const keyT = () => ({ k: pick(['STRING', 'INTEGER', 'CHAR']) });
const anyT = () => weighted([
[scalarT(), 9], [{ k: 'LIST', of: elemT() }, 6], [{ k: 'ARRAY', of: { k: pick(['INTEGER', 'FLOAT', 'STRING', 'BOOL']) }, dims: [int(2, 4)] }, 1],
[{ k: 'ARRAY', of: { k: pick(['INTEGER', 'CHAR']) }, dims: [int(2, 3), int(2, 3)] }, 1],
[{ k: 'HASHMAP', key: keyT(), val: weighted([[{ k: 'INTEGER' }, 3], [{ k: 'STRING' }, 1], [{ k: 'FLOAT' }, 1], [{ k: 'LIST', of: { k: 'INTEGER' } }, 1]]) }, 2.5],
[{ k: 'SET', of: { k: pick(['INTEGER', 'STRING', 'CHAR']) } }, 2], ...(records.length ? [[{ k: 'REC', rec: pick(records) }, 2.5]] : []),
]);
/* ---------- expressions ---------- */
const lit = {
INTEGER: () => String(pick([0, 1, 2, 3, 4, 5, 7, 10, 12, 100, -1, -3])),
FLOAT: () => pick(['0.5', '1.5', '2.25', '-0.75', '3.0', '10.0', '0.1', '-2.5', '4']),
STRING: () => pick(['"ab"', '"GATTACA"', '"x,y,z"', '""', '"Hello"', '"a"', '"tac"', '"b,a"']),
CHAR: () => pick(["'a'", "'G'", "'z'", "'b'", "','", "'T'"]),
BOOL: () => pick(['TRUE', 'FALSE']),
};
const keyLit = (t) => (t.k === 'STRING' ? pick(['"a"', '"b"', '"c"', '"ab"']) : t.k === 'CHAR' ? pick(["'a'", "'b'", "'c'", "'d'"]) : String(int(0, 4)));
const paren = (s) => (/^[\w."']+$|^\w+\(.*\)$/.test(s) && !/^-/.test(s) ? s : `(${s})`);
const neg = (s) => (s.startsWith('-') ? `(${s})` : s);
/** An expression of type t over what `env` holds; d bounds its depth. A chain of calls and records that does not end is given up on. */
let nest = 0;
function ex(env, t, d = 1) {
if (nest > 40) throw new TooDeep();
nest++;
try { return ex1(env, t, d); } finally { nest--; }
}
function ex1(env, t, d) {
const vars = env.filter((v) => same(v.t, t));
const v = () => pick(vars).name;
const has = (pred) => env.filter((x) => pred(x.t));
const pickVar = (pred) => { const xs = has(pred); return xs.length ? pick(xs) : null; };
const fns = subs.filter((s) => s.returns && same(s.returns, t) && s.callable(env));
const call = () => { const f = pick(fns); return `${f.name}(${f.params.map((p) => (p.small ? `(${ex(env, p.t, -1)}) MOD 5` : ex(env, p.t, -1))).join(', ')})`; };
const idx = (len) => `(${ex(env, { k: 'INTEGER' }, -1)}) MOD ${len}`;
// an element of a list or array of type t, a field of type t
const elem = () => {
const opts = [];
for (const x of has((u) => u.k === 'LIST' && same(u.of, t))) opts.push(() => `${x.name}[${idx(`LENGTH(${x.name})`)}]`);
for (const x of has((u) => u.k === 'ARRAY' && same(u.of, t))) opts.push(() => (x.t.dims.length === 2 ? `${x.name}[${idx(x.t.dims[0])}, ${idx(x.t.dims[1])}]` : `${x.name}[${idx(x.t.dims[0])}]`));
for (const x of has((u) => u.k === 'REC')) for (const [f, ft] of x.t.rec.fields) { if (same(ft, t)) opts.push(() => `${x.name}.${f}`); else if (ft.k === 'REC') for (const [g, gt] of ft.rec.fields) if (same(gt, t)) opts.push(() => `${x.name}.${f}.${g}`); }
for (const x of has((u) => u.k === 'LIST' && u.of.k === 'REC')) for (const [f, ft] of x.t.of.rec.fields) if (same(ft, t)) opts.push(() => `${x.name}[${idx(`LENGTH(${x.name})`)}].${f}`);
for (const x of has((u) => u.k === 'LIST' && u.of.k === 'LIST' && same(u.of.of, t))) opts.push(() => `${x.name}[${idx(`LENGTH(${x.name})`)}][0]`);
return opts;
};
const leaf = () => {
const opts = [[() => lit[t.k](), 2]];
if (vars.length) opts.push([v, 5]);
// below depth 0 only a literal or a variable, so an index or an argument does not grow without end
if (d < 0) return weighted(opts)();
const el = elem(); if (el.length) opts.push([() => pick(el)(), 2]);
if (fns.length) opts.push([call, 1]);
return weighted(opts)();
};
if (d < 0 && !isScalar(t) && vars.length) return v();
// below depth 0, a collection with no variable to come from is a literal of literals and variables
if (d < 0 && t.k === 'LIST') return `[${ex(env, t.of, -1)}]`;
if (d < 0 && t.k === 'SET') return `{${keyLit(t.of)}}`;
if (d < 0 && t.k === 'HASHMAP') return `{${keyLit(t.key)}: ${ex(env, t.val, -1)}}`;
if (d < 0 && SIZED_T.includes(t.k)) return vars.length && some(0.6) ? v() : t.k.startsWith('FLOAT') ? '0.5' : String(int(0, 9));
if (isScalar(t) && SIZED_T.includes(t.k)) {
// a sized value: a variable of the type, a small literal, a conversion of a small whole number, or + and * among its own kind
const small = () => (t.k === 'FLOAT32' || t.k === 'FLOAT64' ? pick(['0.5', '1.25', '3.0', '0.1']) : String(int(0, 9)));
const opts = [[small, 2], [() => `${t.k}(${t.k.startsWith('FLOAT') ? ex(env, { k: 'FLOAT' }, 0) : `(${ex(env, { k: 'INTEGER' }, 0)}) MOD 7 + 3`})`, 2]];
if (vars.length) opts.push([v, 4]);
if (d > 0) opts.push([() => `${paren(ex(env, t, d - 1))} + ${paren(ex(env, t, d - 1))}`, 2], [() => `${paren(ex(env, t, d - 1))} * ${small()}`, 1]);
if (t.k === 'FLOAT64') return weighted(opts)();
return weighted(opts)();
}
if (d <= 0 || some(0.3)) {
if (t.k === 'INTEGER' || t.k === 'FLOAT' || t.k === 'STRING' || t.k === 'CHAR' || t.k === 'BOOL') return leaf();
}
const I = (dd = d - 1) => ex(env, { k: 'INTEGER' }, dd);
const F = (dd = d - 1) => ex(env, { k: 'FLOAT' }, dd);
const S = (dd = d - 1) => ex(env, { k: 'STRING' }, dd);
const lists = (pred) => has((u) => (u.k === 'LIST' || u.k === 'ARRAY') && pred(u.of));
switch (t.k) {
case 'INTEGER': {
const opts = [
[() => `${paren(I())} + ${paren(I())}`, 3], [() => `${paren(I())} - ${paren(I())}`, 2], [() => `${paren(I())} * ${paren(I())}`, 2],
[() => `${paren(I())} DIV ${pick(['2', '3', '(-2)', '5'])}`, 1], [() => `${paren(I())} MOD ${pick(['2', '3', '(-4)', '7'])}`, 1],
[() => `LENGTH(${S()})`, 1], [() => `ABS(${I()})`, 0.5], [() => `MIN(${I()}, ${I()})`, 0.5], [() => `MAX(${I()}, ${I()})`, 0.5], [() => `INT(${F()})`, 0.3],
[() => `ROUND(${F()})`, 0.3], [() => leaf(), 2],
];
const ls = lists((o) => o.k === 'INTEGER'); if (ls.length) opts.push([() => `SUM_OF(${pick(ls).name})`, 0.7], [() => `INDEX_OF(${pick(ls).name}, ${I(0)})`, 0.5], [() => `MAX(${pick(ls).name})`, 0.3]);
const any = has((u) => ['LIST', 'SET', 'HASHMAP', 'ARRAY'].includes(u.k)); if (any.length) opts.push([() => `LENGTH(${pick(any).name})`, 1.5]);
const cs = has((u) => u.k === 'CHAR'); if (cs.length) opts.push([() => `ORD(${pick(cs).name})`, 0.3]);
const ss = has((u) => u.k === 'STRING'); if (ss.length) opts.push([() => `INDEX_OF(${pick(ss).name}, ${pick(['"a"', "'T'", '","'])})`, 0.4]);
const sz = has((u) => /^U?INT\d+$/.test(u.k)); if (sz.length) opts.push([() => `INTEGER(${pick(sz).name})`, 0.4]);
return weighted(opts)();
}
case 'FLOAT': {
const opts = [[() => `${paren(F())} + ${paren(F())}`, 2], [() => `${paren(F())} * ${paren(F())}`, 1.5], [() => `${paren(F())} - ${paren(I())}`, 1],
[() => `${paren(I())} / ${pick(['2', '4', '8', '(-5)'])}`, 1], [() => `TO_FLOAT(${I()})`, 0.5], [() => `${paren(I())} * 0.5`, 1], [() => `ABS(${F()})`, 0.4], [() => `MAX(${F()}, ${I()})`, 0.4], [() => leaf(), 2]];
const ls = lists((o) => o.k === 'FLOAT'); if (ls.length) opts.push([() => `SUM_OF(${pick(ls).name})`, 0.5], [() => `MEAN_OF(${pick(ls).name})`, 0.5], [() => `MIN(${pick(ls).name})`, 0.3]);
const f32 = has((u) => u.k === 'FLOAT32'); if (f32.length) opts.push([() => `FLOAT(${pick(f32).name})`, 0.4]);
return weighted(opts)();
}
case 'BOOL': {
const cmp = () => pick(['==', '!=', '<', '<=', '>', '>=']);
const opts = [[() => `${paren(I())} ${cmp()} ${paren(I())}`, 3], [() => `${paren(F())} ${cmp()} ${paren(F())}`, 1], [() => `${paren(S())} ${pick(['==', '!=', '<'])} ${paren(S())}`, 1],
[() => `${paren(ex(env, t, d - 1))} AND ${paren(ex(env, t, d - 1))}`, 1], [() => `${paren(ex(env, t, d - 1))} OR ${paren(ex(env, t, d - 1))}`, 1], [() => `NOT (${ex(env, t, d - 1)})`, 0.7], [() => leaf(), 2]];
const cols = has((u) => ['LIST', 'SET'].includes(u.k) && isScalar(u.of)); if (cols.length) opts.push([() => { const c = pick(cols); return `${ex(env, c.t.of, 0)} IN ${c.name}`; }, 1]);
const maps = has((u) => u.k === 'HASHMAP'); if (maps.length) opts.push([() => { const m = pick(maps); return `${keyLit(m.t.key)} IN ${m.name}`; }, 1]);
const cs = has((u) => u.k === 'CHAR'); if (cs.length) opts.push([() => `${pick(cs).name} IN ${S(0)}`, 0.4]);
return weighted(opts)();
}
case 'STRING': {
const opts = [[() => `${paren(S())} & ${paren(S())}`, 3], [() => `${paren(S())} & TO_STRING(${I()})`, 1], [() => `UPPER(${S()})`, 0.6], [() => `LOWER(${S()})`, 0.4],
[() => { const s = S(0); return `SLICE(${s}, 0, MIN(2, LENGTH(${s})))`; }, 0.6], [() => `REPLACE(${S()}, "a", "o")`, 0.4], [() => `TO_STRING(${I()})`, 0.5], [() => leaf(), 2]];
const ls = lists((o) => o.k === 'STRING'); if (ls.length) opts.push([() => `JOIN(${pick(ls).name}, "-")`, 0.6]);
const cs = has((u) => u.k === 'CHAR'); if (cs.length) opts.push([() => `${pick(cs).name} & ""`, 0.5]);
return weighted(opts)();
}
case 'CHAR': {
const ss = has((u) => u.k === 'STRING');
const opts = [[() => leaf(), 3]];
if (ss.length) opts.push([() => { const s = pick(ss).name; return `${s}[${idx(`LENGTH(${s})`)}]`; }, 2]);
return weighted(opts)();
}
case 'LIST': {
const opts = [];
if (vars.length) opts.push([v, 5]);
const items = () => Array.from({ length: int(1, 3) }, () => ex(env, t.of, 0));
opts.push([() => `[${items().join(', ')}]`, 2.5]);
if (vars.length && sortable(t.of)) opts.push([() => `SORTED(${v()})`, 1]);
if (vars.length) opts.push([() => { const x = v(); return `SLICE(${x}, 0, MIN(${int(1, 3)}, LENGTH(${x})))`; }, 1]);
if (isScalar(t.of)) opts.push([() => `FILL(${int(0, 3)}, ${ex(env, t.of, 0)})`, 0.6]);
if (t.of.k === 'STRING') opts.push([() => `SPLIT(${S(0)}, ",")`, 1]);
const maps = has((u) => u.k === 'HASHMAP' && same(u.key, t.of)); if (maps.length) opts.push([() => `KEYS(${pick(maps).name})`, 1]);
const sets = has((u) => u.k === 'SET' && same(u.of, t.of)); if (sets.length) opts.push([() => `SORTED(${pick(sets).name})`, 1]);
if (fns.length) opts.push([call, 1]);
return weighted(opts)();
}
case 'HASHMAP': {
const opts = [[() => `{${Array.from({ length: int(1, 2) }, () => `${keyLit(t.key)}: ${ex(env, t.val, 0)}`).filter((x, i, a) => a.findIndex((y) => y.split(':')[0] === x.split(':')[0]) === i).join(', ')}}`, 1]];
if (vars.length) opts.push([v, 3]);
if (fns.length) opts.push([call, 1]);
return weighted(opts)();
}
case 'SET': {
const opts = [[() => `{${[...new Set(Array.from({ length: int(1, 3) }, () => keyLit(t.of)))].join(', ')}}`, 1]];
if (vars.length) opts.push([v, 3]);
if (fns.length) opts.push([call, 1]);
return weighted(opts)();
}
case 'REC': {
const opts = [];
if (vars.length) opts.push([v, 4]);
const el = elem(); if (el.length) opts.push([() => pick(el)(), 2]);
if (fns.length) opts.push([call, 1]);
if (!opts.length) return null;
return weighted(opts)();
}
case 'ARRAY': return vars.length ? v() : null;
default: return leaf();
}
}
/** Can `ex` make a value of type t from this env? (A record or an array needs a variable to come from.) */
const canMake = (env, t) => !(t.k === 'ARRAY' || t.k === 'REC') || env.some((x) => same(x.t, t)) || subs.some((s) => s.returns && same(s.returns, t) && s.callable(env));
/* ---------- statements ---------- */
const writable = (env, pred = () => true) => env.filter((x) => !x.ro && pred(x.t));
const tagged = (env, values, label = 'output') => {
const tag = ++tags;
if (values.length === 1 && some(0.2)) return node(label, `OUTPUT ${values[0]}`);
return { ...node(label, `OUTPUT "@${tag} ", ${values.join(', " ", ')}`), tag };
};
const printables = (env) => env.filter((x) => printable(x.t));
const showSome = (env, label) => {
const ps = printables(env);
const vals = [];
for (let i = int(1, 3); i > 0; i--) vals.push(ps.length && some(0.6) ? pick(ps).name : ex(env, scalarT(), 1));
return tagged(env, vals, label);
};
/** DECLARE, with its value: the one-line form, the two-line form, several names, an ARRAY filled by a loop, a record field by field. */
function declare(env, ctx, t = anyT()) {
const name = fresh({ INTEGER: 'N', FLOAT: 'X', STRING: 'S', CHAR: 'C', BOOL: 'Ok', LIST: 'Xs', ARRAY: 'A', HASHMAP: 'H', SET: 'Seen', REC: 'R' }[t.k] ?? 'W');
const out = [];
if (t.k === 'ARRAY') {
out.push(node('declare-array', `DECLARE ${name} : ${tt(t)}`));
const i = fresh('I');
const inner = [...env, { name: i, t: { k: 'INTEGER' }, ro: true }];
if (t.dims.length === 1) out.push(node('fill-array', `FOR ${i} <- 0 TO ${t.dims[0]}`, [node('fill-array', `${name}[${i}] <- ${ex(inner, t.of, 1)}`)], `NEXT ${i}`));
else {
const j = fresh('J');
const inner2 = [...inner, { name: j, t: { k: 'INTEGER' }, ro: true }];
out.push(node('fill-array', `FOR ${i} <- 0 TO ${t.dims[0]}`, [node('fill-array', `FOR ${j} <- 0 TO ${t.dims[1]}`, [node('fill-array', `${name}[${i}, ${j}] <- ${ex(inner2, t.of, 1)}`)], `NEXT ${j}`)], `NEXT ${i}`));
}
} else if (t.k === 'REC') {
const value = canMake(env, t) && some(0.4) ? ex(env, t, 1) : null;
if (value) out.push(node('declare-record', `DECLARE ${name} : ${tt(t)} <- ${value}`));
else {
out.push(node('declare-record', `DECLARE ${name} : ${tt(t)}`));
for (const [f, ft] of t.rec.fields) {
if (ft.k === 'REC') { for (const [g, gt] of ft.rec.fields) out.push(node('field', `${name}.${f}.${g} <- ${ex(env, gt, 1)}`)); }
else out.push(node('field', `${name}.${f} <- ${ex(env, ft, 1)}`));
}
}
} else if (some(0.65) && canMake(env, t)) out.push(node('declare', `DECLARE ${name} : ${tt(t)} <- ${ex(env, t, 1)}`));
else if (some(0.3) && isScalar(t)) {
const other = fresh(t.k === 'INTEGER' ? 'M' : 'V');
out.push(node('declare-two', `DECLARE ${name}, ${other} : ${tt(t)}`), node('assign', `${name} <- ${ex(env, t, 1)}`), node('assign', `${other} <- ${ex(env, t, 1)}`));
env.push({ name: other, t });
} else {
out.push(node('declare', `DECLARE ${name} : ${tt(t)}`));
if (t.k !== 'LIST' || some(0.7)) out.push(node('assign', `${name} <- ${ex(env, t, 1)}`));
}
env.push({ name, t });
return out;
}
/** A place of type t to assign to, or null: a variable, an element, a field, a map entry. */
function place(env) {
const opts = [];
for (const x of writable(env)) {
if (x.t.k !== 'ARRAY') opts.push([() => [x.name, x.t], 3]);
if (x.t.k === 'LIST') opts.push([() => [`${x.name}[(${ex(env, { k: 'INTEGER' }, 0)}) MOD LENGTH(${x.name})]`, x.t.of], 2]);
if (x.t.k === 'LIST' && x.t.of.k === 'LIST') opts.push([() => [`${x.name}[(${ex(env, { k: 'INTEGER' }, 0)}) MOD LENGTH(${x.name})][0]`, x.t.of.of], 1]);
if (x.t.k === 'ARRAY') opts.push([() => [x.t.dims.length === 2 ? `${x.name}[${int(0, x.t.dims[0] - 1)}, ${int(0, x.t.dims[1] - 1)}]` : `${x.name}[(${ex(env, { k: 'INTEGER' }, 0)}) MOD ${x.t.dims[0]}]`, x.t.of], 2]);
if (x.t.k === 'HASHMAP') opts.push([() => [`${x.name}[${keyLit(x.t.key)}]`, x.t.val], 2]);
if (x.t.k === 'REC') for (const [f, ft] of x.t.rec.fields) {
opts.push([() => [`${x.name}.${f}`, ft], 1.5]);
if (ft.k === 'LIST') opts.push([() => [`${x.name}.${f}[(${ex(env, { k: 'INTEGER' }, 0)}) MOD LENGTH(${x.name}.${f})]`, ft.of], 0.7]);
if (ft.k === 'REC') for (const [g, gt] of ft.rec.fields) opts.push([() => [`${x.name}.${f}.${g}`, gt], 0.7]);
}
if (x.t.k === 'LIST' && x.t.of.k === 'REC') for (const [f, ft] of x.t.of.rec.fields) opts.push([() => [`${x.name}[(${ex(env, { k: 'INTEGER' }, 0)}) MOD LENGTH(${x.name})].${f}`, ft], 1]);
}
return opts.length ? weighted(opts)() : null;
}
function assign(env) {
const p = place(env);
if (!p || !canMake(env, p[1])) return [];
const [target, t] = p;
// a running update reads the place it writes
if (isNum(p[1]) && some(0.4)) return [node('update', `${target} <- ${target} ${pick(['+', '-', '*'])} ${neg(ex(env, t, 0))}`)];
if (t.k === 'STRING' && some(0.3)) return [node('update', `${target} <- ${pick([`${target} & ${ex(env, t, 0)}`, `${ex(env, t, 0)} & ${target}`])}`)];
return [node('assign', `${target} <- ${ex(env, t, 1)}`)];
}
/** The collection built-ins: APPEND, INSERT, REMOVE, SORT, ADD, DELETE, and a tally into a map. */
function builtin(env) {
const opts = [];
for (const x of writable(env, (u) => u.k === 'LIST')) {
if (canMake(env, x.t.of)) opts.push([() => [node('append', `APPEND(${x.name}, ${ex(env, x.t.of, 1)})`)], 3]);
if (canMake(env, x.t.of)) opts.push([() => [node('insert', `INSERT(${x.name}, (${ex(env, { k: 'INTEGER' }, 0)}) MOD (LENGTH(${x.name}) + 1), ${ex(env, x.t.of, 1)})`)], 1.5]);
opts.push([() => [node('remove', `IF LENGTH(${x.name}) > 1 THEN`, [node('remove', `REMOVE(${x.name}, (${ex(env, { k: 'INTEGER' }, 0)}) MOD LENGTH(${x.name}))`)], 'ENDIF')], 1.5]);
if (sortable(x.t.of)) opts.push([() => [node('sort', `SORT(${x.name})`)], 1]);
if (x.t.of.k === 'LIST') opts.push([() => [node('append-inner', `IF LENGTH(${x.name}) > 0 THEN`, [node('append-inner', `APPEND(${x.name}[0], ${ex(env, x.t.of.of, 0)})`)], 'ENDIF')], 1]);
}
for (const x of writable(env, (u) => u.k === 'REC')) for (const [f, ft] of x.t.rec.fields) if (ft.k === 'LIST') opts.push([() => [node('append-field', `APPEND(${x.name}.${f}, ${ex(env, ft.of, 1)})`)], 1]);
for (const x of writable(env, (u) => u.k === 'SET')) {
opts.push([() => [node('add', `ADD(${x.name}, ${keyLit(x.t.of)})`)], 2]);
opts.push([() => [node('delete-set', `DELETE(${x.name}, ${keyLit(x.t.of)})`)], 1]);
}
for (const x of writable(env, (u) => u.k === 'HASHMAP')) {
const k = keyLit(x.t.key);
if (x.t.val.k === 'INTEGER') opts.push([() => [node('tally', `IF ${k} IN ${x.name} THEN`, [node('tally', `${x.name}[${k}] <- ${x.name}[${k}] + 1`)], 'ELSE', [node('tally', `${x.name}[${k}] <- 1`)], 'ENDIF')], 2]);
if (x.t.val.k === 'LIST') opts.push([() => [node('map-list', `IF NOT (${k} IN ${x.name}) THEN`, [node('map-list', `${x.name}[${k}] <- []`)], 'ENDIF'), node('map-list', `APPEND(${x.name}[${k}], ${ex(env, x.t.val.of, 0)})`)], 2]);
opts.push([() => [node('delete-map', `DELETE(${x.name}, ${k})`)], 1]);
opts.push([() => { const y = writable(env, (u) => same(u, x.t.val)); return y.length ? [node('read-map', `IF ${k} IN ${x.name} THEN`, [node('read-map', `${pick(y).name} <- ${x.name}[${k}]`)], 'ENDIF')] : [node('read-map', `IF ${k} IN ${x.name} THEN`, [tagged(env, [`${x.name}[${k}]`], 'read-map')], 'ENDIF')]; }, 1.5]);
}
return opts.length ? weighted(opts)() : [];
}
/** Copies: a list, a record, a list in a list or in a map, changed after the copy is made, and both shown. */
function copies(env) {
const opts = [];
for (const x of writable(env, (u) => u.k === 'LIST' && isScalar(u.of) && printable(u))) opts.push(() => {
const m = fresh('Copy');
const out = [node('copy-list', `DECLARE ${m} : ${tt(x.t)} <- ${x.name}`), node('copy-list', `APPEND(${x.name}, ${ex(env, x.t.of, 0)})`)];
out.push(tagged(env, [m, x.name], 'copy-list'));
env.push({ name: m, t: x.t });
return out;
});
for (const x of writable(env, (u) => u.k === 'REC')) opts.push(() => {
const m = fresh('Twin');
const [f, ft] = pick(x.t.rec.fields);
const out = [node('copy-record', `DECLARE ${m} : ${tt(x.t)}`), node('copy-record', `${m} <- ${x.name}`)];
if (ft.k === 'LIST') out.push(node('copy-record', `APPEND(${x.name}.${f}, ${ex(env, ft.of, 0)})`));
else if (ft.k === 'REC') { const [g, gt] = pick(ft.rec.fields); out.push(node('copy-record', `${x.name}.${f}.${g} <- ${ex(env, gt, 0)}`)); }
else out.push(node('copy-record', `${x.name}.${f} <- ${ex(env, ft, 0)}`));
const show = (r) => (ft.k === 'REC' ? `${r}.${f}.${ft.rec.fields[0][0]}` : `${r}.${f}`);
if (printable(ft.k === 'REC' ? ft.rec.fields[0][1] : ft)) out.push(tagged(env, [show(m), show(x.name)], 'copy-record'));
env.push({ name: m, t: x.t });
return out;
});
for (const x of writable(env, (u) => u.k === 'LIST' && u.of.k === 'LIST')) for (const y of writable(env, (u) => same(u, x.t.of))) opts.push(() => [
node('copy-nested', `APPEND(${x.name}, ${y.name})`), node('copy-nested', `APPEND(${y.name}, ${ex(env, y.t.of, 0)})`), tagged(env, [x.name, y.name], 'copy-nested')]);
for (const x of writable(env, (u) => u.k === 'LIST' && u.of.k === 'REC')) for (const y of writable(env, (u) => same(u, x.t.of))) opts.push(() => {
const [f, ft] = pick(y.t.rec.fields);
if (!isScalar(ft)) return [];
return [node('copy-into-list', `APPEND(${x.name}, ${y.name})`), node('copy-into-list', `${y.name}.${f} <- ${ex(env, ft, 0)}`), tagged(env, [`${x.name}[LENGTH(${x.name}) - 1].${f}`, `${y.name}.${f}`], 'copy-into-list')];
});
for (const x of writable(env, (u) => u.k === 'HASHMAP' && u.val.k === 'LIST')) for (const y of writable(env, (u) => same(u, x.t.val))) opts.push(() => {
const k = keyLit(x.t.key);
return [node('copy-map', `${x.name}[${k}] <- ${y.name}`), node('copy-map', `APPEND(${y.name}, ${ex(env, y.t.of, 0)})`), tagged(env, [`${x.name}[${k}]`, y.name], 'copy-map')];
});
return opts.length ? pick(opts)() : [];
}
function cond(env) { return ex(env, { k: 'BOOL' }, int(1, 2)); }
function block(env, ctx, n) {
const inner = [...env];
const out = [];
for (let i = 0; i < n; i++) out.push(...stmt(inner, ctx));
return out.length ? out : [showSome(inner, 'output')];
}
function ifStmt(env, ctx) {
const parts = [`IF ${cond(env)} THEN`, block(env, { ...ctx, depth: ctx.depth + 1 }, int(1, 3))];
for (let i = int(0, 2); i > 0; i--) parts.push(`ELSEIF ${cond(env)} THEN`, block(env, { ...ctx, depth: ctx.depth + 1 }, int(1, 2)));
if (some(0.5)) parts.push('ELSE', block(env, { ...ctx, depth: ctx.depth + 1 }, int(1, 2)));
parts.push('ENDIF');
return [node('if', ...parts)];
}
function caseStmt(env, ctx) {
const kind = weighted([['INTEGER', 4], ['CHAR', 1], ['STRING', 1], ['FLOAT', 1]]);
const subj = ex(env, { k: kind }, 1);
const parts = [`CASE OF ${subj}`];
const lab = () => {
if (kind === 'INTEGER') return weighted([[() => String(int(-2, 12)), 3], [() => `${int(0, 4)}, ${int(5, 9)}`, 2], [() => { const a = int(-5, 6); return `${a} TO ${a + int(1, 8)}`; }, 3]])();
if (kind === 'FLOAT') { const a = int(-3, 5); return weighted([[`${a} TO ${a + int(1, 6)}`, 3], [`${a}.5 TO ${a + 2}.25`, 1], [`${a}.5`, 1]]); }
if (kind === 'CHAR') return weighted([[lit.CHAR(), 2], [`${lit.CHAR()}, ${lit.CHAR()}`, 1], ["'a' TO 'n'", 1]]);
return weighted([[lit.STRING(), 2], [`${lit.STRING()}, ${lit.STRING()}`, 1]]);
};
const seen = new Set();
for (let i = int(1, 3); i > 0; i--) {
const l = lab();
if (seen.has(l)) continue;
seen.add(l);
if (some(0.5)) { const b = stmt([...env], { ...ctx, depth: ctx.depth + 1, oneLine: true }); if (b.length === 1 && b[0].parts.length === 1) { parts.push(node('case-arm', `${l} : ${b[0].parts[0]}`)); continue; } }
parts.push(node('case-arm', `${l} :`, block(env, { ...ctx, depth: ctx.depth + 1 }, int(1, 2))));
}
if (some(0.6)) parts.push(node('case-arm', 'OTHERWISE :', block(env, { ...ctx, depth: ctx.depth + 1 }, int(1, 2))));
parts.push('ENDCASE');
// the arms are nodes of their own, each at the CASE's indentation plus one; the labels are lines of theirs
return [{ label: 'case', parts: [parts[0], parts.slice(1, -1), parts.at(-1)] }];
}
function loopBody(env, ctx, label, n) {
const body = block(env, { ...ctx, depth: ctx.depth + 1, loop: label }, n);
// a BREAK or CONTINUE under a condition, somewhere in the body
if (some(0.35)) { const at = int(0, body.length); body.splice(at, 0, node('jump', `IF ${cond(env)} THEN`, [node('jump', pick(['BREAK', 'CONTINUE']))], 'ENDIF')); }
return body;
}
function forStmt(env, ctx) {
const i = fresh('I');
const inner = [...env, { name: i, t: { k: 'INTEGER' }, ro: true }];
let head;
const r = rand();
if (r < 0.15) {
// the bound is a variable the body changes: the notation works the bounds out once
const ns = writable(env, (u) => u.k === 'INTEGER');
if (ns.length) {
const n = pick(ns).name;
const body = loopBody(inner, ctx, 'for', int(1, 2));
body.unshift(node('for-bound', `${n} <- ${n} + 1`));
return [node('for-bound', `FOR ${i} <- 0 TO MIN(${n}, 6)`, body, `NEXT ${i}`)];
}
}
if (r < 0.4) { const a = int(4, 9); head = `FOR ${i} <- ${a} TO ${a - int(2, 6)} STEP ${pick(['-1', '-2', '-3'])}`; }
else if (r < 0.6) head = `FOR ${i} <- ${int(-2, 2)} TO ${int(3, 9)} STEP ${pick(['2', '3'])}`;
else if (r < 0.8) head = `FOR ${i} <- 0 TO ${int(0, 5)}`;
else {
const ls = env.filter((x) => ['LIST', 'STRING'].includes(x.t.k));
head = ls.length ? `FOR ${i} <- 0 TO LENGTH(${pick(ls).name})` : `FOR ${i} <- 1 TO ${int(2, 5)}`;
}
return [node('for', head, loopBody(inner, ctx, 'for', int(1, 3)), `NEXT ${i}`)];
}
function forEach(env, ctx) {
const x = fresh('E');
const opts = [];
for (const c of env.filter((u) => u.t.k === 'LIST' || u.t.k === 'ARRAY' || u.t.k === 'STRING')) opts.push([c, 3]);
opts.push([{ name: lit.STRING(), t: { k: 'STRING' }, literal: true }, 0.5], [{ name: `[${int(-2, 2)}, ${int(2, 6)})`, t: { k: 'RANGE' }, literal: true }, 1]);
for (const c of env.filter((u) => u.t.k === 'HASHMAP' || u.t.k === 'SET')) opts.push([c, 2]);
const c = weighted(opts);
const elT = c.t.k === 'STRING' ? { k: 'CHAR' } : c.t.k === 'RANGE' ? { k: 'INTEGER' } : c.t.k === 'HASHMAP' ? c.t.key : c.t.of;
// the notation walks a one-dimensional collection only
if (c.t.k === 'ARRAY' && c.t.dims.length === 2) return [];
const inner = [...env, { name: x, t: elT, ro: true }];
if (c.t.k === 'HASHMAP' || c.t.k === 'SET') {
// a SET or a map is visited in an order the notation does not promise: the body only adds things up
const acc = fresh('Acc');
const contrib = elT.k === 'INTEGER' ? pick([x, `${x} * ${x}`, `${x} MOD 3`]) : elT.k === 'STRING' ? `LENGTH(${x})` : `ORD(${x})`;
const val = c.t.k === 'HASHMAP' && c.t.val.k === 'INTEGER' ? ` + ${c.name}[${x}]` : c.t.k === 'HASHMAP' && c.t.val.k === 'LIST' ? ` + LENGTH(${c.name}[${x}])` : '';
const body = [node('each-unordered', `${acc} <- ${acc} + ${contrib}${val}`)];
if (some(0.4)) body.push(node('each-unordered', `IF ${contrib} > 1 THEN`, [node('each-unordered', `${acc} <- ${acc} + 100`)], 'ENDIF'));
// the body changes what it walks, in a way whose end does not depend on the order
if (!c.ro && some(0.3)) {
if (c.t.k === 'HASHMAP' && c.t.val.k === 'INTEGER') body.push(node('each-change', `${c.name}[${x}] <- ${c.name}[${x}] * 2`));
if (c.t.k === 'SET') body.push(node('each-change', `ADD(${c.name}, ${keyLit(c.t.of)})`));
}
env.push({ name: acc, t: { k: 'INTEGER' } });
return [node('each-unordered', `DECLARE ${acc} : INTEGER <- 0`), node('each-unordered', `FOR EACH ${x} IN ${c.name}`, body, `NEXT ${x}`), tagged(env, [acc], 'each-unordered')];
}
const body = loopBody(inner, ctx, 'each', int(1, 3));
// the body changes what it walks: the notation walks it as it was when the loop began
if (!c.literal && !c.ro && some(0.3)) {
if (c.t.k === 'LIST' && canMake(inner, c.t.of)) body.push(node('each-change', `APPEND(${c.name}, ${ex(inner, c.t.of, 0)})`));
if (c.t.k === 'STRING') body.push(node('each-change', `${c.name} <- ${pick([`"z" & ${c.name}`, `SLICE(${c.name}, 1, LENGTH(${c.name}))`, `${c.name} & "q"`])}`));
if (c.t.k === 'ARRAY' && c.t.dims.length === 1) body.push(node('each-change', `${c.name}[0] <- ${ex(inner, c.t.of, 0)}`));
}
return [node(`each-${c.t.k.toLowerCase()}`, `FOR EACH ${x} IN ${c.name}`, body, `NEXT ${x}`)];
}
function whileStmt(env, ctx) {
const k = fresh('K');
const inner = [...env, { name: k, t: { k: 'INTEGER' }, ro: true }];
const limit = int(1, 5);
const body = loopBody(inner, ctx, 'while', int(1, 3));
body.unshift(node('while', `${k} <- ${k} + 1`));
const extra = some(0.4) ? ` AND ${paren(cond(env))}` : '';
env.push({ name: k, t: { k: 'INTEGER' }, ro: true });
return [node('while', `DECLARE ${k} : INTEGER <- 0`), node('while', `WHILE ${k} < ${limit}${extra}`, body, 'ENDWHILE')];
}
function repeatStmt(env, ctx) {
const k = fresh('K');
const inner = [...env, { name: k, t: { k: 'INTEGER' }, ro: true }];
const body = loopBody(inner, ctx, 'repeat', int(1, 3));
body.unshift(node('repeat', `${k} <- ${k} + 1`));
const extra = some(0.4) ? ` OR ${paren(cond(env))}` : '';
env.push({ name: k, t: { k: 'INTEGER' }, ro: true });
return [node('repeat', `DECLARE ${k} : INTEGER <- 0`), node('repeat', 'REPEAT', body, `UNTIL ${k} >= ${int(1, 5)}${extra}`)];
}
function callStmt(env) {
const procs = subs.filter((s) => !s.returns && s.callable(env));
if (!procs.length) return [];
const p = pick(procs);
const taken = new Set();
const args = [];
for (const q of p.params) {
if (q.byref) {
const vs = writable(env, (u) => same(u, q.t)).filter((x) => !taken.has(x.name));
if (!vs.length) return [];
const x = pick(vs); taken.add(x.name); args.push(x.name);
} else if (!isScalar(q.t) && some(0.6) && env.some((u) => same(u.t, q.t))) {
// a collection or a record passed by value: the routine's changes must not reach it
const x = pick(env.filter((u) => same(u.t, q.t))); args.push(x.name);
} else args.push(ex(env, q.t, 1));
}
const out = [node('call', `CALL ${p.name}(${args.join(', ')})`)];
const shown = p.params.map((q, i) => (printable(q.t) && env.some((u) => u.name === args[i]) ? args[i] : null)).filter(Boolean);
if (shown.length) out.push(tagged(env, shown, 'call'));
return out;
}
/** One statement (or a few that belong together), for a body whose names are `env`. */
function stmt(env, ctx) {
const deep = ctx.depth >= 2;
const opts = [
[() => declare(env, ctx), ctx.depth ? 1 : 3], [() => assign(env), 4], [() => [showSome(env, 'output')], 5], [() => builtin(env), 3],
[() => callStmt(env), 2.5], [() => copies(env), ctx.depth ? 0.5 : 1.5],
];
// compound statements, fewer the deeper the body
const w = ctx.depth === 0 ? 1 : 0.4;
if (!ctx.oneLine && !deep) opts.push([() => ifStmt(env, ctx), 2 * w], [() => caseStmt(env, ctx), 1 * w], [() => forStmt(env, ctx), 1.5 * w], [() => forEach(env, ctx), 1.5 * w],
[() => whileStmt(env, ctx), 0.8 * w], [() => repeatStmt(env, ctx), 0.8 * w]);
if (ctx.sub?.returns && ctx.depth > 0 && !ctx.oneLine) opts.push([() => (canMake(env, ctx.sub.returns) ? [node('return', `RETURN ${ex(env, ctx.sub.returns, 1)}`)] : []), 0.6]);
if (ctx.sub && !ctx.sub.returns && ctx.depth > 0) opts.push([() => [node('return', 'RETURN')], 0.4]);
for (let tries = 0; tries < 5; tries++) {
try {
const got = weighted(opts)();
if (got.length) return got;
} catch (e) { if (!(e instanceof TooDeep)) throw e; }
}
return [showSome(env, 'output')];
}
/* ---------- records, constants, routines ---------- */
function record() {
const name = some(0.15) ? pick(ODD_NAMES.filter((w) => !used.has(w.toUpperCase()))) ?? fresh('Rec') : fresh(pick(['Point', 'Item', 'Cell', 'Pair', 'Node']));
used.add(name.toUpperCase());
const fields = [];
const fnames = new Set();
for (let i = int(2, 4); i > 0; i--) {
let f = some(0.15) ? pick(['Copy', 'Hash', 'Value', 'Len', 'Pop', 'Items', 'Self', 'Init', 'Write_to', 'Count', 'Size', 'Name', 'Data']) : pick(['X', 'Y', 'Name', 'Score', 'Tags', 'Flag', 'Total', 'Label']);
if (fnames.has(f.toUpperCase())) f = `${f}${i}`;
fnames.add(f.toUpperCase());
const ft = weighted([[{ k: 'INTEGER' }, 3], [{ k: 'FLOAT' }, 1], [{ k: 'STRING' }, 2], [{ k: 'BOOL' }, 1], [{ k: 'LIST', of: { k: 'INTEGER' } }, 1.5],
[{ k: 'LIST', of: { k: 'STRING' } }, 0.5], ...(records.length ? [[{ k: 'REC', rec: pick(records) }, 1]] : [])]);
fields.push([f, ft]);
}
const rec = { name, fields };
records.push(rec);
return node('type', `TYPE ${name}`, fields.map(([f, ft]) => node('type', `DECLARE ${f} : ${tt(ft)}`)), 'ENDTYPE');
}
function constant(globals) {
const t = { k: pick(['INTEGER', 'INTEGER', 'FLOAT', 'STRING']) };
const name = fresh(pick(['Lim', 'Rate', 'Word', 'Base']));
const v = t.k === 'INTEGER' ? String(int(2, 9)) : t.k === 'FLOAT' ? pick(['0.5', '2.5', '1.25']) : pick(['"ab"', '"GC"']);
globals.push({ name, t, ro: true });
return node('constant', `CONSTANT ${name} = ${v}`);
}
const paramT = () => weighted([[{ k: 'INTEGER' }, 4], [{ k: 'FLOAT' }, 1.5], [{ k: 'STRING' }, 2], [{ k: 'BOOL' }, 0.7], [{ k: 'CHAR' }, 0.5], [{ k: pick(SIZED_T) }, 0.5],
[{ k: 'LIST', of: { k: 'INTEGER' } }, 2.5], [{ k: 'LIST', of: { k: 'STRING' } }, 1], [{ k: 'LIST', of: { k: 'LIST', of: { k: 'INTEGER' } } }, 0.4],
[{ k: 'HASHMAP', key: { k: 'STRING' }, val: { k: 'INTEGER' } }, 0.8], [{ k: 'SET', of: { k: 'INTEGER' } }, 0.5], ...(records.length ? [[{ k: 'REC', rec: pick(records) }, 1.5]] : [])]);
/** A routine: a FUNCTION (by-value parameters, an answer, an early RETURN) or a PROCEDURE (BYREF and by-value parameters), sometimes recursive with a bound. */
function routine(globals) {
const isFn = some(0.55);
const name = fresh(isFn ? pick(['Calc', 'Score', 'Pick', 'Build', 'Mix']) : pick(['Update', 'Grow', 'Bump', 'Fill', 'Walk']));
const recursive = some(0.25);
const params = [];
if (recursive) params.push({ name: fresh('Depth'), t: { k: 'INTEGER' } });
for (let i = int(recursive ? 0 : 1, 3); i > 0; i--) params.push({ name: fresh('P'), t: paramT(), byref: !isFn && some(0.55) });
const returns = isFn ? weighted([[{ k: 'INTEGER' }, 4], [{ k: 'FLOAT' }, 1], [{ k: 'STRING' }, 1.5], [{ k: 'BOOL' }, 1], [{ k: 'LIST', of: { k: 'INTEGER' } }, 1.5],
...(records.length ? [[{ k: 'REC', rec: pick(records) }, 1]] : [])]) : null;
const me = { name, params, returns, index: subs.length, callable: () => true };
const env = [...globals, ...params.map((p) => ({ name: p.name, t: p.t }))];
const ctx = { depth: 0, sub: me, loop: null };
const body = [];
if (recursive) {
const n = params[0].name;
const stop = isFn ? (canMake(env, returns) ? `RETURN ${ex(env, returns, 0)}` : null) : 'RETURN';
if (!stop) return null;
body.push(node('recursion', `IF ${n} <= 0 THEN`, [node('recursion', stop)], 'ENDIF'));
}
for (let i = int(1, 4); i > 0; i--) body.push(...stmt(env, ctx));
if (recursive) {
const args = params.map((p, i) => (i === 0 ? `${p.name} - 1` : p.byref ? p.name : ex(env, p.t, 0)));
// a call to itself; in a FUNCTION its answer is used
subs.push(me);
if (isFn) {
if (isNum(returns)) body.push(node('recursion', `RETURN ${name}(${args.join(', ')}) ${pick(['+', '-', '*'])} ${neg(ex(env, returns, 0))}`));
else if (returns.k === 'STRING') body.push(node('recursion', `RETURN ${ex(env, returns, 0)} & ${name}(${args.join(', ')})`));
else body.push(node('recursion', `RETURN ${name}(${args.join(', ')})`));
} else body.push(node('recursion', `CALL ${name}(${args.join(', ')})`));
subs.pop();
} else if (isFn) {
if (!canMake(env, returns)) return null;
body.push(node('return', `RETURN ${ex(env, returns, 1)}`));
}
const head = `${isFn ? 'FUNCTION' : 'PROCEDURE'} ${name}(${params.map((p) => `${p.byref ? 'BYREF ' : ''}${p.name} : ${tt(p.t)}`).join(', ')})${isFn ? ` RETURNS ${tt(returns)}` : ''}`;
// a recursive routine is called with a small first argument only
if (recursive) me.params = [{ name: params[0].name, t: { k: 'INTEGER' }, small: true }, ...params.slice(1)];
subs.push(me);
return node(isFn ? 'function' : 'procedure', head, body, isFn ? 'ENDFUNCTION' : 'ENDPROCEDURE');
}
/** A whole program: records, constants, routines, then the main lines. */
function program() {
const top = [];
const globals = [];
for (let i = weighted([[0, 1], [1, 3], [2, 2]]); i > 0; i--) top.push(record());
for (let i = int(0, 2); i > 0; i--) top.push(constant(globals));
const tried = (fn) => { try { return fn(); } catch (e) { if (e instanceof TooDeep) return null; throw e; } };
for (let i = weighted([[0, 1], [1, 2], [2, 3], [3, 2]]); i > 0; i--) { const n = subs.length; const r = tried(() => routine(globals)); if (r) top.push(r); else subs.length = n; }
const env = [...globals];
const ctx = { depth: 0, sub: null, loop: null };
// a few values to work with, then statements until the program is long enough
for (let i = int(2, 4); i > 0; i--) top.push(...(tried(() => declare(env, ctx)) ?? []));
const want = int(20, 55);
while (render(top).text.split('\n').length < want) top.push(...stmt(env, ctx));
return top;
}
return { program };
}