1const key = (x, y) => `${x},${y}`;2const directions = [[1, 0], [0, 1]];34// Stacked words intentionally enumerate every valid alternative, but an5// authored board must not be able to make the browser allocate an unbounded6// number of paths or spans. These limits are high enough for ordinary puzzle7// stacks and low enough to cap memory used by span indexing.8export const MAX_RULE_PATHS = 16_384;9export const MAX_RULE_SPANS = 65_536;1011export class RuleParseLimitError extends RangeError {12 constructor(kind, limit) {13 super(`rule parse ${kind} exceeded the limit of ${limit}`);14 this.name = 'RuleParseLimitError';15 this.kind = kind;16 this.limit = limit;17 }18}1920/**21 * Keep only physical sentence spans that are not contained by a longer span.22 * Process longer spans first and index their source IDs so containment checks23 * intersect only candidate spans that share every source ID.24 */25function maximalSpans(spans) {26 const indexKey = (span, id) => `${span.axis}\u0000${id}`;27 const ordered = [...spans].sort((a, b) => b.ids.length - a.ids.length || a.spanOrder - b.spanOrder);28 const containingById = new Map();29 const hidden = new Set();30 for (const span of ordered) {31 const candidates = span.ids.map(id => containingById.get(indexKey(span, id))).filter(Boolean);32 if (candidates.length === span.ids.length) {33 const smallest = candidates.reduce((best, set) => set.size < best.size ? set : best);34 for (const candidate of smallest) {35 if (candidate.ids.length > span.ids.length && candidates.every(set => set.has(candidate))) {36 hidden.add(span);37 break;38 }39 }40 }41 for (const id of span.ids) {42 const key = indexKey(span, id);43 let indexed = containingById.get(key);44 if (!indexed) containingById.set(key, indexed = new Set());45 indexed.add(span);46 }47 }48 return spans.filter(span => !hidden.has(span));49}5051/**52 * Parse physical word objects into dynamic rules and sentence spans.53 *54 * This function is deliberately pure: callers provide the settled object55 * list and semantic properties, and the returned arrays contain new rule and56 * span records. Object order remains the source of deterministic tie breaks.57 */58export function parseRules(objects, semanticProperties) {59 const words = new Map();60 for (const object of objects) if (object.kind === 'word') {61 const cell = key(object.x, object.y);62 const entries = words.get(cell);63 const entry = { text: object.text, id: object.id };64 if (entries) entries.push(entry);65 else words.set(cell, [entry]);66 }67 const at = (x, y) => words.get(key(x, y)) || [];68 const noun = text => text && text !== 'IS' && text !== 'AND' && !semanticProperties.has(text);69 const predicate = text => noun(text) || semanticProperties.has(text);70 const found = new Map();71 const spans = [];72 let pathExpansions = 0;73 const countPath = () => {74 pathExpansions += 1;75 if (pathExpansions > MAX_RULE_PATHS) throw new RuleParseLimitError('paths', MAX_RULE_PATHS);76 };77 const countSpan = () => {78 if (spans.length >= MAX_RULE_SPANS) throw new RuleParseLimitError('spans', MAX_RULE_SPANS);79 };8081 // Map insertion follows authored object order, which is not a rule-reading82 // order. Sort cells by row, then column; stack order remains the stable tie83 // break for alternatives sharing one physical cell.84 const origins = [...words.entries()].sort(([a], [b]) => {85 const [ax, ay] = a.split(',').map(Number);86 const [bx, by] = b.split(',').map(Number);87 return ay - by || ax - bx;88 });89 const originOrder = new Map(origins.map(([origin], index) => [origin, index]));90 for (const [origin, starts] of origins) {91 const [ox, oy] = origin.split(',').map(Number);92 for (const first of starts.filter(entry => noun(entry.text))) for (const [dx, dy] of directions) {93 // Parse the grammar as a sequence of cell choices. A path selects one94 // token from each cell; a stacked AND+IS cell therefore tries both95 // alternatives instead of greedily consuming AND.96 const emit = (subjectPath, predicatePath, is) => {97 countSpan();98 spans.push({ ids: [...subjectPath.sourceIds, is.id, ...predicatePath.sourceIds], axis: dx ? 'h' : 'v', originOrder: originOrder.get(origin), spanOrder: spans.length });99 for (const subject of subjectPath.names) for (const predicateName of predicatePath.names) {100 const ruleKey = `${subject} IS ${predicateName}`;101 if (!found.has(ruleKey)) found.set(ruleKey, {102 subject,103 predicate: predicateName,104 text: ruleKey,105 sourceIds: [...subjectPath.sourceIds, is.id, ...predicatePath.sourceIds],106 axis: dx ? 'h' : 'v',107 });108 }109 };110 const parsePredicates = (x, y, subjectPath, is, predicatePath) => {111 countPath();112 for (const token of at(x, y)) {113 if (predicate(token.text)) {114 const nextPath = { names: [...predicatePath.names, token.text], sourceIds: [...predicatePath.sourceIds, token.id] };115 emit(subjectPath, nextPath, is);116 for (const connector of at(x + dx, y + dy).filter(next => next.text === 'AND')) {117 parsePredicates(x + 2 * dx, y + 2 * dy, subjectPath, is, {118 names: nextPath.names,119 sourceIds: [...nextPath.sourceIds, connector.id],120 });121 }122 }123 }124 };125 const parseSubject = (x, y, subjectPath) => {126 countPath();127 for (const token of at(x, y)) {128 if (token.text === 'IS') {129 parsePredicates(x + dx, y + dy, subjectPath, token, { names: [], sourceIds: [] });130 } else if (token.text === 'AND') {131 for (const next of at(x + dx, y + dy).filter(entry => noun(entry.text))) {132 parseSubject(x + 2 * dx, y + 2 * dy, {133 names: [...subjectPath.names, next.text],134 sourceIds: [...subjectPath.sourceIds, token.id, next.id],135 });136 }137 }138 }139 };140 parseSubject(ox + dx, oy + dy, { names: [first.text], sourceIds: [first.id] });141 }142 }143144 const sentences = maximalSpans(spans)145 .sort((a, b) => a.originOrder - b.originOrder || a.spanOrder - b.spanOrder)146 .map(({ originOrder: _originOrder, spanOrder: _spanOrder, ...span }) => span);147 return { rules: [...found.values()], sentences };148}