6592505740

Committed 20 Oct 2023 08:39PM UTC coverage: 56.621% (+38.1%) from 18.482%

Build # 6592505740

Build Type

push

github

Committed by

robsimmons

Commit Message

Put some very basic engine testing in place

Run Details

143 of 291 branches covered (0.0%)

Branch coverage included in aggregate %.

136 of 136 new or added lines in 3 files covered. (100.0%)

229 of 366 relevant lines covered (62.57%)

11.11 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

76.42

/src/engine.ts

import { Premise, Proposition, propToString } from './syntax';
import { Substitution, Pattern, Data, match, apply, equal, termToString } from './terms';

export interface Program {
  rules: { [name: string]: InternalPartialRule };
  conclusions: { [r: string]: InternalConclusion };
}

export type InternalPartialRule = {
  next: string[];
  shared: string[];
  premise: Premise;
};

export type InternalConclusion =
  | {
      type: 'NewFact';
      name: string;
      args: Pattern[];
      values: Pattern[];
      exhaustive: boolean;
    }
  | { type: 'Contradiction' };

export interface Fact {
  type: 'Fact';
  name: string;
  args: Data[];
}

export interface Prefix {
  type: 'Prefix';
  name: string;
  args: Substitution;
}

export interface Database {
  facts: { [predicate: string]: Data[][] };
  factValues: { [prop: string]: { type: 'is'; value: Data } | { type: 'is not'; value: Data[] } };
  prefixes: { [name: string]: Substitution[] };
  queue: (Fact | Prefix)[];
}

function matchPatterns(
  substitution: Substitution,
  pattern: Pattern[],
  data: Data[],
): null | Substitution {
  if (pattern.length !== data.length) {
    return null;
  }

  for (let i = 0; i < pattern.length; i++) {
    const candidate = match(substitution, pattern[i], data[i]);
    if (candidate === null) return null;
    substitution = candidate;
  }

  return substitution;
}

function matchFact(substitution: Substitution, proposition: Proposition, fact: Fact) {
  if (proposition.name !== fact.name) {
    return null;
  }
  return matchPatterns(substitution, proposition.args, fact.args);
}

export function factToString(fact: Fact): string {
  return propToString({ ...fact, type: 'Proposition' });
}

function substitutionToString(args: Substitution): string {
  if (Object.keys(args).length === 0) return `{}`;
  return `{ ${Object.entries(args)
    .sort(([a], [b]) => a.localeCompare(b))
    .map(([varName, term]) => `${termToString(term)}/${varName}`)
    .join(', ')} }`;
}

function prefixToString(prefix: Prefix): string {
  return `${prefix.name}${substitutionToString(prefix.args)}`;
}

function dbItemToString(item: Fact | Prefix) {
  if (item.type === 'Fact') return factToString(item);
  return prefixToString(item);
}

function stepConclusion(conclusion: InternalConclusion, prefix: Prefix, db: Database): Database[] {
  if (conclusion.type === 'Contradiction') return [];
  const args = conclusion.args.map((arg) => apply(prefix.args, arg));
  let values = conclusion.values.map((value) => apply(prefix.args, value));

  const key = `${conclusion.name}${args.map((arg) => ` ${termToString(arg)}`).join('')}`;
  const knownValue = db.factValues[key];

  if (knownValue?.type === 'is') {
    // Either this conclusion will be redundant or cause a contradiction
    if (conclusion.exhaustive && !values.some((value) => equal(value, knownValue.value))) {
      return [];
    }
    return [db];
  } else {
    // Just have to make sure options are not already excluded from this branch
    let isNot = knownValue ? knownValue.value : [];
    values = values.filter((value) => !isNot.some((excludedValue) => equal(value, excludedValue)));

    // If this conclusion is nonexhaustive, add any new concrete outcomes to the
    // nonexhaustive branch
    isNot = [...isNot, ...values];

    const nonExhaustive: Database[] = conclusion.exhaustive
      ? []
      : [
          {
            ...db,
            factValues: { ...db.factValues, [key]: { type: 'is not', value: isNot } },
          },
        ];

    const existingFacts = db.facts[conclusion.name] || [];
    return nonExhaustive.concat(
      values.map<Database>((value) => ({
        ...db,
        facts: { ...db.facts, [conclusion.name]: [...existingFacts, [...args, value]] },
        factValues: { ...db.factValues, [key]: { type: 'is', value } },
        queue: [...db.queue, { type: 'Fact', name: conclusion.name, args: [...args, value] }],
      })),
    );
  }
}

export function insertFact(name: string, args: Data[], value: Data, db: Database): Database {
  const key = `${name}${args.map((arg) => ` ${termToString(arg)}`).join('')}`;
  const existingFacts = db.facts[name] || [];
  return {
    ...db,
    facts: { ...db.facts, [name]: [...existingFacts, [...args, value]] },
    factValues: { ...db.factValues, [key]: { type: 'is', value } },
    queue: [...db.queue, { type: 'Fact', name, args: [...args, value] }],
  };
}

function stepPrefix(
  rules: { [name: string]: InternalPartialRule },
  prefix: Prefix,
  db: Database,
): Database {
  const rule = rules[prefix.name];
  if (!rule) {
    throw new Error(`Internal: expected rule '${prefix.name}' in rules.`);
  }

  const newPrefixes: Prefix[] = [];

  if (rule.premise.type === 'Inequality') {
    const a = apply(prefix.args, rule.premise.a);
    const b = apply(prefix.args, rule.premise.b);

    if (!equal(a, b)) {
      newPrefixes.push(
        ...rule.next.map<Prefix>((next) => ({
          type: 'Prefix',
          name: next,
          args: prefix.args,
        })),
      );
    }
  }

  if (rule.premise.type === 'Equality') {
    const a = apply(prefix.args, rule.premise.a);
    const candidate = matchPatterns(prefix.args, [rule.premise.b], [a]);

    if (candidate !== null) {
      newPrefixes.push(
        ...rule.next.map<Prefix>((next) => ({
          type: 'Prefix',
          name: next,
          args: candidate,
        })),
      );
    }
  }

  if (rule.premise.type === 'Proposition') {
    const knownFacts = db.facts[rule.premise.name] || [];

    for (const fact of knownFacts) {
      const candidate = matchPatterns(prefix.args, rule.premise.args, fact);

      if (candidate !== null) {
        newPrefixes.push(
          ...rule.next.map<Prefix>((next) => ({
            type: 'Prefix',
            name: next,
            args: candidate,
          })),
        );
      }
    }
  }

  return extendDbWithPrefixes(newPrefixes, db);
}

function stepFact(
  rules: { [name: string]: InternalPartialRule },
  fact: Fact,
  db: Database,
): Database {
  const newPrefixes: Prefix[] = [];
  for (const ruleName of Object.keys(rules)) {
    const rule = rules[ruleName];
    if (rule.premise.type === 'Proposition') {
      const substitution = matchFact({}, rule.premise, fact);
      if (substitution !== null) {
        for (const item of db.prefixes[ruleName] || []) {
          if (rule.shared.every((varName) => equal(substitution[varName], item[varName]))) {
            newPrefixes.push(
              ...rule.next.map<Prefix>((next) => ({
                type: 'Prefix',
                name: next,
                args: { ...substitution, ...item },
              })),
            );
          }
        }
      }
    }
  }

  return extendDbWithPrefixes(newPrefixes, db);
}

function extendDbWithPrefixes(candidatePrefixList: Prefix[], db: Database): Database {
  let copied = false;
  for (const prefix of candidatePrefixList) {
    if (!db.prefixes[prefix.name]) {
      db.prefixes[prefix.name] = [];
    }

    // Filter out prefixes that are already in the database
    // Relies on the fact that all prefixes with the same name
    // have the same set of variables that they ground
    if (
      !db.prefixes[prefix.name].some((substitution) => {
        return Object.keys(substitution).every((varName) =>
          equal(substitution[varName], prefix.args[varName]),
        );
      })
    ) {
      // copy on write
      if (!copied) {
        copied = true;
        db = { ...db, prefixes: { ...db.prefixes }, queue: [...db.queue] };
      }

      db.prefixes[prefix.name] = [...db.prefixes[prefix.name], prefix.args];
      db.queue.push(prefix);
    }
  }

  return db;
}

export function dbToString(db: Database) {
  return `Queue: ${db.queue.map((item) => dbItemToString(item)).join(', ')}
Prefixes: 
${Object.keys(db.prefixes)
  .sort()
  .map((key) => `${key}: ${db.prefixes[key].map(substitutionToString).join(', ')}`)
  .join('\n')}
Facts:
${Object.keys(db.factValues)
  .sort()
  .map((fact) => {
    const entry = db.factValues[fact];
    if (entry.type === 'is') {
      return entry.value.type === 'triv' ? fact : `${fact} is ${termToString(entry.value)}`;
    } else {
      return `${fact} is not ${entry.value.map(termToString).join(' or ')}`;
    }
  })
  .join('\n')}
`;
}

export function step(program: Program, db: Database): Database[] {
  const [current, ...rest] = db.queue;
  db = { ...db, queue: rest };
  if (current.type === 'Fact') {
    return [stepFact(program.rules, current, db)];
  } else if (program.conclusions[current.name]) {
    return stepConclusion(program.conclusions[current.name], current, db);
  } else {
    return [stepPrefix(program.rules, current, db)];
  }
}

export interface Solution {
  facts: Fact[];
  unfacts: [string, Data[]][];
}

export function execute(
  program: Program,
  db: Database,
): { solutions: Solution[]; steps: number; deadEnds: number; splits: number; highWater: number } {
  const dbStack: Database[] = [db];
  const solutions: Solution[] = [];
  let steps = 0;
  let deadEnds = 0;
  let highWater = 0;
  let splits = 0;
  while (dbStack.length > 0) {
    if (dbStack.length > highWater) highWater = dbStack.length;

    const db = dbStack.pop()!;
    if (db.queue.length === 0) {
      solutions.push({
        facts: ([] as Fact[]).concat(
          ...Object.entries(db.facts).map(([name, argses]) =>
            argses.map<Fact>((args) => ({ type: 'Fact', name: name, args })),
          ),
        ),
        unfacts: Object.entries(db.factValues)
          .filter(
            (arg): arg is [string, { type: 'is not'; value: Data[] }] => arg[1].type === 'is not',
          )
          .map(([attribute, { value }]) => [attribute, value]),
      });
    } else {
      steps += 1;
      const newDbs = step(program, db);
      if (newDbs.length === 0) deadEnds += 1;
      if (newDbs.length > 1) splits += 1;
      dbStack.push(...newDbs);
    }
  }

  return { solutions, steps, deadEnds, splits, highWater };
}

1	import { Premise, Proposition, propToString } from './syntax';	2✔
2	import { Substitution, Pattern, Data, match, apply, equal, termToString } from './terms';	2✔
3
4	export interface Program {
5	rules: { [name: string]: InternalPartialRule };
6	conclusions: { [r: string]: InternalConclusion };
7	}
8
9	export type InternalPartialRule = {
10	next: string[];
11	shared: string[];
12	premise: Premise;
13	};
14
15	export type InternalConclusion =
16	\| {
17	type: 'NewFact';
18	name: string;
19	args: Pattern[];
20	values: Pattern[];
21	exhaustive: boolean;
22	}
23	\| { type: 'Contradiction' };
24
25	export interface Fact {
26	type: 'Fact';
27	name: string;
28	args: Data[];
29	}
30
31	export interface Prefix {
32	type: 'Prefix';
33	name: string;
34	args: Substitution;
35	}
36
37	export interface Database {
38	facts: { [predicate: string]: Data[][] };
39	factValues: { [prop: string]: { type: 'is'; value: Data } \| { type: 'is not'; value: Data[] } };
40	prefixes: { [name: string]: Substitution[] };
41	queue: (Fact \| Prefix)[];
42	}
43
44	function matchPatterns(
45	substitution: Substitution,
46	pattern: Pattern[],
47	data: Data[],
48	): null \| Substitution {
49	if (pattern.length !== data.length) {	18!
50	return null;	×
51	}
52
53	for (let i = 0; i < pattern.length; i++) {	18✔
54	const candidate = match(substitution, pattern[i], data[i]);	18✔
55	if (candidate === null) return null;	18✔
56	substitution = candidate;	16✔
57	}
58
59	return substitution;	16✔
60	}
61
62	function matchFact(substitution: Substitution, proposition: Proposition, fact: Fact) {
63	if (proposition.name !== fact.name) {	36✔
64	return null;	26✔
65	}
66	return matchPatterns(substitution, proposition.args, fact.args);	10✔
67	}
68
69	export function factToString(fact: Fact): string {	2✔
70	return propToString({ ...fact, type: 'Proposition' });	30✔
71	}
72
73	function substitutionToString(args: Substitution): string {
74	if (Object.keys(args).length === 0) return `{}`;	×
75	return `{ ${Object.entries(args)	×
76	.sort(([a], [b]) => a.localeCompare(b))	×
77	.map(([varName, term]) => `${termToString(term)}/${varName}`)	×
78	.join(', ')} }`;
79	}
80
81	function prefixToString(prefix: Prefix): string {
82	return `${prefix.name}${substitutionToString(prefix.args)}`;	×
83	}
84
85	function dbItemToString(item: Fact \| Prefix) {
86	if (item.type === 'Fact') return factToString(item);	×
87	return prefixToString(item);	×
88	}
89
90	function stepConclusion(conclusion: InternalConclusion, prefix: Prefix, db: Database): Database[] {
91	if (conclusion.type === 'Contradiction') return [];	16!
92	const args = conclusion.args.map((arg) => apply(prefix.args, arg));	16✔
93	let values = conclusion.values.map((value) => apply(prefix.args, value));	24✔
94
95	const key = `${conclusion.name}${args.map((arg) => ` ${termToString(arg)}`).join('')}`;	16✔
96	const knownValue = db.factValues[key];	16✔
97
98	if (knownValue?.type === 'is') {	16!
99	// Either this conclusion will be redundant or cause a contradiction
100	if (conclusion.exhaustive && !values.some((value) => equal(value, knownValue.value))) {	×
101	return [];	×
102	}
103	return [db];	×
104	} else {
105	// Just have to make sure options are not already excluded from this branch
106	let isNot = knownValue ? knownValue.value : [];	16!
107	values = values.filter((value) => !isNot.some((excludedValue) => equal(value, excludedValue)));	24✔
108
109	// If this conclusion is nonexhaustive, add any new concrete outcomes to the
110	// nonexhaustive branch
111	isNot = [...isNot, ...values];	16✔
112
113	const nonExhaustive: Database[] = conclusion.exhaustive	16✔
114	? []
115	: [
116	{
117	...db,
118	factValues: { ...db.factValues, [key]: { type: 'is not', value: isNot } },
119	},
120	];
121
122	const existingFacts = db.facts[conclusion.name] \|\| [];	16✔
123	return nonExhaustive.concat(	16✔
124	values.map<Database>((value) => ({	24✔
125	...db,
126	facts: { ...db.facts, [conclusion.name]: [...existingFacts, [...args, value]] },
127	factValues: { ...db.factValues, [key]: { type: 'is', value } },
128	queue: [...db.queue, { type: 'Fact', name: conclusion.name, args: [...args, value] }],
129	})),
130	);
131	}
132	}
133
134	export function insertFact(name: string, args: Data[], value: Data, db: Database): Database {	2✔
135	const key = `${name}${args.map((arg) => ` ${termToString(arg)}`).join('')}`;	×
136	const existingFacts = db.facts[name] \|\| [];	×
137	return {	×
138	...db,
139	facts: { ...db.facts, [name]: [...existingFacts, [...args, value]] },
140	factValues: { ...db.factValues, [key]: { type: 'is', value } },
141	queue: [...db.queue, { type: 'Fact', name, args: [...args, value] }],
142	};
143	}
144
145	function stepPrefix(
146	rules: { [name: string]: InternalPartialRule },
147	prefix: Prefix,
148	db: Database,
149	): Database {
150	const rule = rules[prefix.name];	20✔
151	if (!rule) {	20!
152	throw new Error(`Internal: expected rule '${prefix.name}' in rules.`);	×
153	}
154
155	const newPrefixes: Prefix[] = [];	20✔
156
157	if (rule.premise.type === 'Inequality') {	20✔
158	const a = apply(prefix.args, rule.premise.a);	2✔
159	const b = apply(prefix.args, rule.premise.b);	2✔
160
161	if (!equal(a, b)) {	2✔
162	newPrefixes.push(	2✔
163	...rule.next.map<Prefix>((next) => ({	2✔
164	type: 'Prefix',
165	name: next,
166	args: prefix.args,
167	})),
168	);
169	}
170	}
171
172	if (rule.premise.type === 'Equality') {	20✔
173	const a = apply(prefix.args, rule.premise.a);	4✔
174	const candidate = matchPatterns(prefix.args, [rule.premise.b], [a]);	4✔
175
176	if (candidate !== null) {	4✔
177	newPrefixes.push(	2✔
178	...rule.next.map<Prefix>((next) => ({	2✔
179	type: 'Prefix',
180	name: next,
181	args: candidate,
182	})),
183	);
184	}
185	}
186
187	if (rule.premise.type === 'Proposition') {	20✔
188	const knownFacts = db.facts[rule.premise.name] \|\| [];	14✔
189
190	for (const fact of knownFacts) {	14✔
191	const candidate = matchPatterns(prefix.args, rule.premise.args, fact);	4✔
192
193	if (candidate !== null) {	4✔
194	newPrefixes.push(	4✔
195	...rule.next.map<Prefix>((next) => ({	4✔
196	type: 'Prefix',
197	name: next,
198	args: candidate,
199	})),
200	);
201	}
202	}
203	}
204
205	return extendDbWithPrefixes(newPrefixes, db);	20✔
206	}
207
208	function stepFact(
209	rules: { [name: string]: InternalPartialRule },
210	fact: Fact,
211	db: Database,
212	): Database {
213	const newPrefixes: Prefix[] = [];	28✔
214	for (const ruleName of Object.keys(rules)) {	28✔
215	const rule = rules[ruleName];	54✔
216	if (rule.premise.type === 'Proposition') {	54✔
217	const substitution = matchFact({}, rule.premise, fact);	36✔
218	if (substitution !== null) {	36✔
219	for (const item of db.prefixes[ruleName] \|\| []) {	10✔
220	if (rule.shared.every((varName) => equal(substitution[varName], item[varName]))) {	8✔
221	newPrefixes.push(	8✔
222	...rule.next.map<Prefix>((next) => ({	8✔
223	type: 'Prefix',
224	name: next,
225	args: { ...substitution, ...item },
226	})),
227	);
228	}
229	}
230	}
231	}
232	}
233
234	return extendDbWithPrefixes(newPrefixes, db);	28✔
235	}
236
237	function extendDbWithPrefixes(candidatePrefixList: Prefix[], db: Database): Database {
238	let copied = false;	48✔
239	for (const prefix of candidatePrefixList) {	48✔
240	if (!db.prefixes[prefix.name]) {	16✔
241	db.prefixes[prefix.name] = [];	14✔
242	}
243
244	// Filter out prefixes that are already in the database
245	// Relies on the fact that all prefixes with the same name
246	// have the same set of variables that they ground
247	if (	16✔
248	!db.prefixes[prefix.name].some((substitution) => {
249	return Object.keys(substitution).every((varName) =>	2✔
250	equal(substitution[varName], prefix.args[varName]),	×
251	);
252	})
253	) {
254	// copy on write
255	if (!copied) {	14✔
256	copied = true;	14✔
257	db = { ...db, prefixes: { ...db.prefixes }, queue: [...db.queue] };	14✔
258	}
259
260	db.prefixes[prefix.name] = [...db.prefixes[prefix.name], prefix.args];	14✔
261	db.queue.push(prefix);	14✔
262	}
263	}
264
265	return db;	48✔
266	}
267
268	export function dbToString(db: Database) {	2✔
269	return `Queue: ${db.queue.map((item) => dbItemToString(item)).join(', ')}	×
270	Prefixes:
271	${Object.keys(db.prefixes)
272	.sort()
273	.map((key) => `${key}: ${db.prefixes[key].map(substitutionToString).join(', ')}`)	×
274	.join('\n')}
275	Facts:
276	${Object.keys(db.factValues)
277	.sort()
278	.map((fact) => {
279	const entry = db.factValues[fact];	×
280	if (entry.type === 'is') {	×
281	return entry.value.type === 'triv' ? fact : `${fact} is ${termToString(entry.value)}`;	×
282	} else {
283	return `${fact} is not ${entry.value.map(termToString).join(' or ')}`;	×
284	}
285	})
286	.join('\n')}
287	`;
288	}
289
290	export function step(program: Program, db: Database): Database[] {	2✔
291	const [current, ...rest] = db.queue;	64✔
292	db = { ...db, queue: rest };	64✔
293	if (current.type === 'Fact') {	64✔
294	return [stepFact(program.rules, current, db)];	28✔
295	} else if (program.conclusions[current.name]) {	36✔
296	return stepConclusion(program.conclusions[current.name], current, db);	16✔
297	} else {
298	return [stepPrefix(program.rules, current, db)];	20✔
299	}
300	}
301
302	export interface Solution {
303	facts: Fact[];
304	unfacts: [string, Data[]][];
305	}
306
307	export function execute(	2✔
308	program: Program,
309	db: Database,
310	): { solutions: Solution[]; steps: number; deadEnds: number; splits: number; highWater: number } {
311	const dbStack: Database[] = [db];	6✔
312	const solutions: Solution[] = [];	6✔
313	let steps = 0;	6✔
314	let deadEnds = 0;	6✔
315	let highWater = 0;	6✔
316	let splits = 0;	6✔
317	while (dbStack.length > 0) {	6✔
318	if (dbStack.length > highWater) highWater = dbStack.length;	80✔
319
320	const db = dbStack.pop()!;	80✔
321	if (db.queue.length === 0) {	80✔
322	solutions.push({	16✔
323	facts: ([] as Fact[]).concat(
324	...Object.entries(db.facts).map(([name, argses]) =>
325	argses.map<Fact>((args) => ({ type: 'Fact', name: name, args })),	30✔
326	),
327	),
328	unfacts: Object.entries(db.factValues)
329	.filter(
330	(arg): arg is [string, { type: 'is not'; value: Data[] }] => arg[1].type === 'is not',	32✔
331	)
332	.map(([attribute, { value }]) => [attribute, value]),	2✔
333	});
334	} else {
335	steps += 1;	64✔
336	const newDbs = step(program, db);	64✔
337	if (newDbs.length === 0) deadEnds += 1;	64!
338	if (newDbs.length > 1) splits += 1;	64✔
339	dbStack.push(...newDbs);	64✔
340	}
341	}
342
343	return { solutions, steps, deadEnds, splits, highWater };	6✔
344	}

robsimmons / aspis / 6592505740

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous