Plan, apply and roll back changes to a production ontology, with a blast radius report and a proof an auditor can re-check.
Rust ai-nativedescription-logicsformal-verificationinfrastructure-as-codeisabelle-languageknowledge-graphleanlean4mcpmcp-serverontologyowlowl2reasoningrustshaclsparqltheorem-proving
//! Reading the derivation a prover emits, and re-checking what can honestly be
//! re-checked.
//!
//! Decision 0005 item 5 says an ATP verdict is an ORACLE OPINION, and decision
//! 0006 says a refutation is not a certificate. Neither sentence is retracted
//! here, and this module does not move the boundary: what it does is stop the
//! oracle's answer being a single word. A prover that says `SZS status Theorem`
//! also prints, on request, the derivation it found. That derivation is a
//! finite object. Reading it back turns one unexaminable word into evidence
//! that can be inspected, and some of it into evidence that can be RECOMPUTED.
//!
//! # The three things this earns, in increasing order of what they cost
//!
//! 1. **The prover refuted OUR problem.** Every leaf of the derivation is
//! matched, by name and by parsed formula, against the problem file this
//! repository's exporter produced. A prover pointed at the wrong file, a
//! stale file, or a file whose conjecture was smuggled in as an axiom is
//! caught here and nowhere else in this codebase. This is the cheapest
//! check and by some distance the most valuable, because it is the one that
//! an `AGREE` row in `tools/fol_differential.py` silently assumed.
//! 2. **The derivation is a well-founded DAG ending in `$false`.** Every
//! parent reference resolves to a node that exists, the parent relation is
//! acyclic, and the node nothing else cites is the empty clause.
//! 3. **Some steps are replayed.** Binary resolution, factoring, duplicate
//! literal removal, trivial inequality removal, equality resolution,
//! associative flattening and the negation of the conjecture are recomputed
//! from the premises with a small unifier and compared with what the prover
//! printed. Everything else is NAMED AND COUNTED as unchecked.
//!
//! # What this is NOT
//!
//! It is not a proof of unsatisfiability, and no word in the report says it
//! is. Three separate reasons, all of them live:
//!
//! - **The calculus is not verified.** Even a derivation whose every step this
//! module recomputes is only a derivation in a calculus whose soundness is
//! written down nowhere in `lean/`. `Fol.satisfiable_of_check` has a theorem
//! behind it; this has a Rust program behind it.
//! - **The replayer is not verified either.** The unifier below is ordinary
//! Rust with ordinary tests. A bug in it makes a wrong step look right.
//! - **Clausification is not checked at all.** `cnf_transformation`,
//! `ennf_transformation`, `nnf_transformation`, skolemisation, AVATAR
//! splitting and every SAT-solver step are unchecked and are reported as
//! unchecked, by rule, with a count. On a real proof they are the majority
//! of the steps, which is why [`Report::verdict`] reaches
//! `refutation_partially_replayed` and stops there.
//!
//! The strongest word this module can print is `refutation_fully_replayed`,
//! it requires that NOTHING was left unchecked, and it still is not
//! `unsatisfiable`. The ladder exists so that the distance between what was
//! read and what was recomputed is visible in the output rather than in a
//! footnote.
//!
//! # Why a failed reconstruction is its own word
//!
//! A step whose rule this module implements, whose premises and conclusion are
//! clause-shaped, and which still does not reconstruct is EITHER a defect in
//! the derivation OR a gap in this checker. It is reported as
//! `refutation_step_not_reconstructed` and never as either of those two, for
//! the same reason `tools/fol_differential.py` reports a disagreement and does
//! not adjudicate it. Collapsing it into "unchecked" would let a forged step
//! hide behind a rule name, and collapsing it into "rejected" would claim a
//! defect in someone else's prover on this module's word alone.
//!
//! # Subsumption resolution is checked as binary resolution, and that is exact
//!
//! Vampire prints `forward_subsumption_resolution` for a step whose premises
//! are `C ∨ L` and `D ∨ ¬L'` and whose conclusion is `C`, where `D'σ ⊆ C`. The
//! binary resolvent of those two premises is `C ∪ D'σ`, and `D'σ ⊆ C` makes
//! that exactly `C`. So the conclusion of a subsumption resolution IS the
//! binary resolvent of its premises, and one check covers both rules without
//! weakening either. The same identity is why the check still passes on
//! AVATAR's printed clauses, where the side premise's assertion literals are
//! carried into the conclusion and the classical side condition does not hold
//! of the printed form.
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::fmt::Write as _;
use std::path::{Path, PathBuf};
use std::process::{Command, Stdio};
use std::time::{Duration, Instant};
// ── The term and formula language ──────────────────────────────────────────
/// A first-order term as a prover prints it.
///
/// Deliberately WIDER than [`crate::tptp::Term`], which has no function
/// application because the translation never emits one. A prover's output
/// does: Skolem functions, AVATAR's introduced propositional symbols and
/// TPTP's distinct objects all arrive here. A reader that could not represent
/// them would have to drop them, and a dropped subterm is a different formula.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Term {
/// A TPTP variable: an upper word. The name is kept verbatim, because
/// renaming on the way in would make the alpha-equivalence levels in
/// [`LeafMatch`] impossible to report separately.
Var(String),
/// A function application. Arity 0 is a constant.
Fun(String, Vec<Term>),
}
impl Term {
fn vars(&self, out: &mut BTreeSet<String>) {
match self {
Term::Var(v) => {
out.insert(v.clone());
}
Term::Fun(_, args) => args.iter().for_each(|a| a.vars(out)),
}
}
fn render(&self, s: &mut String) {
match self {
Term::Var(v) => s.push_str(v),
Term::Fun(f, args) => {
s.push_str(f);
if !args.is_empty() {
s.push('(');
for (i, a) in args.iter().enumerate() {
if i > 0 {
s.push(',');
}
a.render(s);
}
s.push(')');
}
}
}
}
}
/// A first-order formula as a prover prints it.
///
/// `<~>`, `~|` and `~&` are read as `Not(Iff …)`, `Not(Or …)` and
/// `Not(And …)`, and `A <= B` as `Imp(B, A)`. Those are definitional
/// rewritings of the TPTP connectives and not normalisations of the formula:
/// nothing here reorders, flattens or simplifies on the way in, because the
/// leaf check's job is to notice a difference rather than to absorb one.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum Formula {
True,
False,
Pred(String, Vec<Term>),
Eq(Term, Term),
Not(Box<Formula>),
And(Box<Formula>, Box<Formula>),
Or(Box<Formula>, Box<Formula>),
Imp(Box<Formula>, Box<Formula>),
Iff(Box<Formula>, Box<Formula>),
All(String, Box<Formula>),
Ex(String, Box<Formula>),
}
impl Formula {
/// A canonical one-line rendering. Used for the problem digest and for
/// naming a mismatch in a report, never for re-parsing.
pub fn render(&self) -> String {
let mut s = String::new();
self.write(&mut s);
s
}
fn write(&self, s: &mut String) {
match self {
Formula::True => s.push_str("$true"),
Formula::False => s.push_str("$false"),
Formula::Pred(p, args) => {
s.push_str(p);
if !args.is_empty() {
s.push('(');
for (i, a) in args.iter().enumerate() {
if i > 0 {
s.push(',');
}
a.render(s);
}
s.push(')');
}
}
Formula::Eq(a, b) => {
a.render(s);
s.push('=');
b.render(s);
}
Formula::Not(f) => {
s.push_str("~(");
f.write(s);
s.push(')');
}
Formula::And(a, b) => binary(s, a, "&", b),
Formula::Or(a, b) => binary(s, a, "|", b),
Formula::Imp(a, b) => binary(s, a, "=>", b),
Formula::Iff(a, b) => binary(s, a, "<=>", b),
Formula::All(v, f) => {
let _ = write!(s, "![{v}]:(");
f.write(s);
s.push(')');
}
Formula::Ex(v, f) => {
let _ = write!(s, "?[{v}]:(");
f.write(s);
s.push(')');
}
}
}
/// Reassociate `&` and `|` to the right, everywhere.
///
/// Associativity of conjunction and disjunction is not in question, and a
/// prover's printer is free to bracket an n-ary `&` however it likes. This
/// exists so that a leaf that differs ONLY in bracketing is reported as
/// matched at the `associativity_normalised` level rather than as a
/// mismatch, and so that the level is visible in the report.
pub fn assoc_normalised(&self) -> Formula {
fn flat(f: &Formula, and: bool, out: &mut Vec<Formula>) {
match f {
Formula::And(a, b) if and => {
flat(a, and, out);
flat(b, and, out);
}
Formula::Or(a, b) if !and => {
flat(a, and, out);
flat(b, and, out);
}
other => out.push(other.assoc_normalised()),
}
}
match self {
Formula::And(_, _) | Formula::Or(_, _) => {
let and = matches!(self, Formula::And(_, _));
let mut parts = Vec::new();
flat(self, and, &mut parts);
let mut it = parts.into_iter().rev();
let mut acc = it.next().expect("a binary node flattens to at least two parts");
for p in it {
acc = if and {
Formula::And(Box::new(p), Box::new(acc))
} else {
Formula::Or(Box::new(p), Box::new(acc))
};
}
acc
}
Formula::Not(f) => Formula::Not(Box::new(f.assoc_normalised())),
Formula::Imp(a, b) => Formula::Imp(
Box::new(a.assoc_normalised()),
Box::new(b.assoc_normalised()),
),
Formula::Iff(a, b) => Formula::Iff(
Box::new(a.assoc_normalised()),
Box::new(b.assoc_normalised()),
),
Formula::All(v, f) => Formula::All(v.clone(), Box::new(f.assoc_normalised())),
Formula::Ex(v, f) => Formula::Ex(v.clone(), Box::new(f.assoc_normalised())),
other => other.clone(),
}
}
}
fn binary(s: &mut String, a: &Formula, op: &str, b: &Formula) {
s.push('(');
a.write(s);
s.push_str(op);
b.write(s);
s.push(')');
}
/// Equality up to renaming of BOUND variables. Free variables must agree by
/// name, because a free variable in a TPTP clause is implicitly universally
/// quantified over the clause and its name is the only thing linking its
/// occurrences.
pub fn alpha_eq(a: &Formula, b: &Formula) -> bool {
fn go(a: &Formula, b: &Formula, l: &mut Vec<String>, r: &mut Vec<String>) -> bool {
// A bound variable is identified by its distance from the binder, so a
// name that shadows an outer binder resolves to the inner one, which
// is what `rposition` gives.
fn same_term(x: &Term, y: &Term, l: &[String], r: &[String]) -> bool {
match (x, y) {
(Term::Var(u), Term::Var(v)) => {
match (l.iter().rposition(|n| n == u), r.iter().rposition(|n| n == v)) {
(Some(i), Some(j)) => i == j,
(None, None) => u == v,
_ => false,
}
}
(Term::Fun(f, xs), Term::Fun(g, ys)) => {
f == g
&& xs.len() == ys.len()
&& xs.iter().zip(ys).all(|(x, y)| same_term(x, y, l, r))
}
_ => false,
}
}
match (a, b) {
(Formula::True, Formula::True) | (Formula::False, Formula::False) => true,
(Formula::Pred(p, xs), Formula::Pred(q, ys)) => {
p == q
&& xs.len() == ys.len()
&& xs.iter().zip(ys).all(|(x, y)| same_term(x, y, l, r))
}
(Formula::Eq(x1, y1), Formula::Eq(x2, y2)) => {
same_term(x1, x2, l, r) && same_term(y1, y2, l, r)
}
(Formula::Not(f), Formula::Not(g)) => go(f, g, l, r),
(Formula::And(f1, g1), Formula::And(f2, g2))
| (Formula::Or(f1, g1), Formula::Or(f2, g2))
| (Formula::Imp(f1, g1), Formula::Imp(f2, g2))
| (Formula::Iff(f1, g1), Formula::Iff(f2, g2)) => {
go(f1, f2, l, r) && go(g1, g2, l, r)
}
(Formula::All(u, f), Formula::All(v, g)) | (Formula::Ex(u, f), Formula::Ex(v, g)) => {
l.push(u.clone());
r.push(v.clone());
let ok = go(f, g, l, r);
l.pop();
r.pop();
ok
}
_ => false,
}
}
go(a, b, &mut Vec::new(), &mut Vec::new())
}
// ── Lexer ──────────────────────────────────────────────────────────────────
#[derive(Clone, Debug, PartialEq, Eq)]
enum Tok {
LParen,
RParen,
LBrack,
RBrack,
Comma,
Dot,
Colon,
Op(&'static str),
/// A lower word, a dollar word or a number. Names, roles, rules and
/// predicate symbols all arrive as this.
Word(String),
/// A single-quoted TPTP atom, with `\'` and `\\` already unescaped. This
/// is how every IRI in this repository's export travels.
Quoted(String),
/// A double-quoted TPTP DISTINCT OBJECT. Kept with its quotes so that it
/// can never compare equal to a single-quoted atom of the same text: a
/// distinct object is pairwise unequal to every other by fiat, which is
/// exactly the trap decision 0005 records for the TPTP writer.
Distinct(String),
Var(String),
}
/// Every operator token, longest-first where one is a prefix of another:
/// `!=` before `!`, `<=>` before `<=`, `~|` before `~`. The lexer scans this
/// list in order and takes the first hit, so the order is the disambiguation.
const OPS: [&str; 13] =
["<=>", "<~>", "~|", "~&", "!=", "=>", "<=", "&", "|", "~", "=", "!", "?"];
fn lex(src: &str) -> Result<Vec<Tok>, String> {
let b: Vec<char> = src.chars().collect();
let mut i = 0usize;
let mut out = Vec::new();
while i < b.len() {
let c = b[i];
if c.is_whitespace() {
i += 1;
continue;
}
// `%` is TPTP's line comment. `#` is E's: it prefixes every line of
// its own commentary, including the `# SZS output start` marker and
// the `# SZS output end` one that closes the block, so a reader that
// did not skip it would choke on the last line of every E proof. A
// `#` inside an IRI is safe, because a quoted atom is lexed by the
// branch below and this one never sees the inside of one.
if c == '%' || c == '#' {
while i < b.len() && b[i] != '\n' {
i += 1;
}
continue;
}
if c == '/' && i + 1 < b.len() && b[i + 1] == '*' {
i += 2;
while i + 1 < b.len() && !(b[i] == '*' && b[i + 1] == '/') {
i += 1;
}
i = (i + 2).min(b.len());
continue;
}
if c == '\'' || c == '"' {
let quote = c;
let mut s = String::new();
i += 1;
loop {
if i >= b.len() {
return Err(format!("unterminated {quote} at end of input"));
}
if b[i] == '\\' && i + 1 < b.len() {
s.push(b[i + 1]);
i += 2;
continue;
}
if b[i] == quote {
i += 1;
break;
}
s.push(b[i]);
i += 1;
}
out.push(if quote == '\'' { Tok::Quoted(s) } else { Tok::Distinct(format!("\"{s}\"")) });
continue;
}
match c {
'(' => {
out.push(Tok::LParen);
i += 1;
continue;
}
')' => {
out.push(Tok::RParen);
i += 1;
continue;
}
'[' => {
out.push(Tok::LBrack);
i += 1;
continue;
}
']' => {
out.push(Tok::RBrack);
i += 1;
continue;
}
',' => {
out.push(Tok::Comma);
i += 1;
continue;
}
'.' => {
out.push(Tok::Dot);
i += 1;
continue;
}
':' => {
out.push(Tok::Colon);
i += 1;
continue;
}
_ => {}
}
// `!=` must be tried before `!`, `<=>` before `<=`, and `~|` before
// `~`; OPS is in that order and is scanned in it.
if let Some(op) = OPS.iter().find(|op| {
b[i..].len() >= op.len() && b[i..i + op.len()].iter().collect::<String>() == **op
}) {
out.push(Tok::Op(op));
i += op.len();
continue;
}
if c == '$' || c.is_ascii_alphabetic() || c == '_' || c.is_ascii_digit() {
let start = i;
if c == '$' {
i += 1;
if i < b.len() && b[i] == '$' {
i += 1;
}
}
while i < b.len() && (b[i].is_ascii_alphanumeric() || b[i] == '_') {
i += 1;
}
let w: String = b[start..i].iter().collect();
let first = w.chars().find(|ch| ch.is_ascii_alphabetic());
if first.is_some_and(|ch| ch.is_ascii_uppercase()) && !w.starts_with('$') {
out.push(Tok::Var(w));
} else {
out.push(Tok::Word(w));
}
continue;
}
if c == '+' || c == '-' {
let start = i;
i += 1;
while i < b.len() && b[i].is_ascii_digit() {
i += 1;
}
if i == start + 1 {
return Err(format!("unexpected character {c:?}"));
}
out.push(Tok::Word(b[start..i].iter().collect()));
continue;
}
return Err(format!("unexpected character {c:?}"));
}
Ok(out)
}
// ── The annotated-formula list ─────────────────────────────────────────────
/// One `inference(RULE, [status(…)], [parents])` record.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Inference {
pub rule: String,
pub parents: Vec<Parent>,
}
/// A parent of an inference step.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Parent {
/// A reference to another annotated formula, by name.
Named(String),
/// An inference record written INLINE in the parent position, which E does
/// routinely. It has a rule and parents of its own and NO FORMULA, so
/// nothing about it or about the step it feeds can be replayed. It is
/// given a synthetic node so that its own parent references are still
/// resolved and its rule is still counted.
Inline(Box<Inference>),
/// Anything else in a parent position, kept verbatim so a report can name
/// it rather than pretend it was understood.
Other(String),
}
/// The provenance a prover attaches to an annotated formula.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Source {
/// `file('path', name)`. The second argument is the name the formula had
/// in the problem file, which is what makes the leaf check possible.
File { path: String, name: Option<String> },
Inference(Inference),
/// `introduced(definition, …)`. A symbol the prover invented. It is NOT
/// from the problem, it is not derived from the problem, and no
/// conservativity argument is checked here.
Introduced { rule: String, detail: String },
/// A bare name, which some printers use for a trivial re-statement.
Name(String),
/// A source this reader did not understand, kept verbatim.
Other(String),
}
/// One `fof(…)` or `cnf(…)` line.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Annotated {
pub name: String,
pub role: String,
pub formula: Formula,
pub source: Option<Source>,
}
/// A general term, the TPTP grammar's catch-all for annotations.
#[derive(Clone, Debug, PartialEq, Eq)]
enum GTerm {
Word(String),
Func(String, Vec<GTerm>),
List(Vec<GTerm>),
Other(String),
}
impl GTerm {
fn word(&self) -> Option<&str> {
match self {
GTerm::Word(w) | GTerm::Func(w, _) => Some(w),
_ => None,
}
}
fn render(&self) -> String {
match self {
GTerm::Word(w) => w.clone(),
GTerm::Other(w) => w.clone(),
GTerm::Func(f, args) => {
format!("{f}({})", args.iter().map(GTerm::render).collect::<Vec<_>>().join(","))
}
GTerm::List(xs) => {
format!("[{}]", xs.iter().map(GTerm::render).collect::<Vec<_>>().join(","))
}
}
}
}
struct Parser {
toks: Vec<Tok>,
at: usize,
}
impl Parser {
fn peek(&self) -> Option<&Tok> {
self.toks.get(self.at)
}
fn bump(&mut self) -> Option<Tok> {
let t = self.toks.get(self.at).cloned();
if t.is_some() {
self.at += 1;
}
t
}
fn eat(&mut self, t: &Tok) -> bool {
if self.peek() == Some(t) {
self.at += 1;
true
} else {
false
}
}
fn expect(&mut self, t: &Tok) -> Result<(), String> {
if self.eat(t) {
Ok(())
} else {
Err(format!("expected {:?}, found {:?}", t, self.peek()))
}
}
fn name(&mut self) -> Result<String, String> {
match self.bump() {
Some(Tok::Word(w)) | Some(Tok::Quoted(w)) => Ok(w),
other => Err(format!("expected a name, found {other:?}")),
}
}
fn term(&mut self) -> Result<Term, String> {
match self.bump() {
Some(Tok::Var(v)) => Ok(Term::Var(v)),
Some(Tok::Distinct(d)) => Ok(Term::Fun(d, Vec::new())),
Some(Tok::Word(w)) | Some(Tok::Quoted(w)) => {
let mut args = Vec::new();
if self.eat(&Tok::LParen) {
loop {
args.push(self.term()?);
if self.eat(&Tok::Comma) {
continue;
}
self.expect(&Tok::RParen)?;
break;
}
}
Ok(Term::Fun(w, args))
}
other => Err(format!("expected a term, found {other:?}")),
}
}
/// A unitary formula: a bracketed formula, a negation, a quantification,
/// or an atom. TPTP makes a quantifier's body unitary, so the body is
/// parsed here rather than at the binary level.
fn unit(&mut self) -> Result<Formula, String> {
match self.peek().cloned() {
Some(Tok::LParen) => {
self.at += 1;
let f = self.formula(0)?;
self.expect(&Tok::RParen)?;
Ok(f)
}
Some(Tok::Op("~")) => {
self.at += 1;
Ok(Formula::Not(Box::new(self.unit()?)))
}
Some(Tok::Op(q @ ("!" | "?"))) => {
self.at += 1;
self.expect(&Tok::LBrack)?;
let mut vars = Vec::new();
loop {
match self.bump() {
Some(Tok::Var(v)) => vars.push(v),
other => return Err(format!("expected a variable, found {other:?}")),
}
// TFF writes `X : $i`; the sort is read and discarded,
// because this reader is about FOF and an untyped reading
// of a typed binder is the same binder.
if self.eat(&Tok::Colon) {
self.bump();
}
if self.eat(&Tok::Comma) {
continue;
}
break;
}
self.expect(&Tok::RBrack)?;
self.expect(&Tok::Colon)?;
let body = self.unit()?;
Ok(vars.into_iter().rev().fold(body, |acc, v| {
if q == "!" {
Formula::All(v, Box::new(acc))
} else {
Formula::Ex(v, Box::new(acc))
}
}))
}
Some(Tok::Word(w)) if w == "$true" => {
self.at += 1;
Ok(Formula::True)
}
Some(Tok::Word(w)) if w == "$false" => {
self.at += 1;
Ok(Formula::False)
}
_ => {
let lhs = self.term()?;
match self.peek().cloned() {
Some(Tok::Op("=")) => {
self.at += 1;
Ok(Formula::Eq(lhs, self.term()?))
}
Some(Tok::Op("!=")) => {
self.at += 1;
Ok(Formula::Not(Box::new(Formula::Eq(lhs, self.term()?))))
}
_ => match lhs {
Term::Fun(p, args) => Ok(Formula::Pred(p, args)),
Term::Var(v) => {
Err(format!("a bare variable {v} is not a formula in FOF"))
}
},
}
}
}
}
fn formula(&mut self, min: u8) -> Result<Formula, String> {
let mut left = self.unit()?;
loop {
let (op, prec) = match self.peek() {
Some(Tok::Op(o @ ("<=>" | "<~>"))) => (*o, 10u8),
Some(Tok::Op(o @ ("=>" | "<="))) => (*o, 20),
Some(Tok::Op(o @ ("|" | "~|"))) => (*o, 30),
Some(Tok::Op(o @ ("&" | "~&"))) => (*o, 40),
_ => break,
};
if prec < min {
break;
}
self.at += 1;
// Right-associative throughout. `&` and `|` are associative, so
// the choice is arbitrary for them; `=>` is right-associative in
// TPTP. `Form::conj` in src/tptp.rs right-associates too, which is
// what makes a leaf of this repository's own export come back
// structurally identical rather than merely equivalent.
let right = self.formula(prec)?;
left = match op {
"<=>" => Formula::Iff(Box::new(left), Box::new(right)),
"<~>" => Formula::Not(Box::new(Formula::Iff(Box::new(left), Box::new(right)))),
"=>" => Formula::Imp(Box::new(left), Box::new(right)),
"<=" => Formula::Imp(Box::new(right), Box::new(left)),
"|" => Formula::Or(Box::new(left), Box::new(right)),
"~|" => Formula::Not(Box::new(Formula::Or(Box::new(left), Box::new(right)))),
"&" => Formula::And(Box::new(left), Box::new(right)),
"~&" => Formula::Not(Box::new(Formula::And(Box::new(left), Box::new(right)))),
_ => unreachable!("the operator table above lists every arm"),
};
}
Ok(left)
}
/// A general term. Never fails: anything it does not recognise is consumed
/// as balanced tokens and returned as [`GTerm::Other`], so one odd
/// annotation cannot make a whole derivation unreadable.
fn general(&mut self) -> GTerm {
match self.peek().cloned() {
Some(Tok::LBrack) => {
self.at += 1;
let mut xs = Vec::new();
if self.eat(&Tok::RBrack) {
return GTerm::List(xs);
}
loop {
xs.push(self.general());
if self.eat(&Tok::Comma) {
continue;
}
let _ = self.eat(&Tok::RBrack);
break;
}
GTerm::List(xs)
}
Some(Tok::Word(w)) | Some(Tok::Quoted(w)) => {
self.at += 1;
if self.eat(&Tok::LParen) {
let mut args = Vec::new();
if self.eat(&Tok::RParen) {
return GTerm::Func(w, args);
}
loop {
args.push(self.general());
if self.eat(&Tok::Comma) {
continue;
}
let _ = self.eat(&Tok::RParen);
break;
}
let mut g = GTerm::Func(w, args);
if self.eat(&Tok::Colon) {
let inner = self.general();
g = GTerm::Other(format!("{}:{}", g.render(), inner.render()));
}
return g;
}
if self.eat(&Tok::Colon) {
let inner = self.general();
return GTerm::Other(format!("{w}:{}", inner.render()));
}
GTerm::Word(w)
}
Some(Tok::Var(v)) | Some(Tok::Distinct(v)) => {
self.at += 1;
GTerm::Word(v)
}
_ => {
// Balanced skip. Stops at a top-level comma or a closing
// bracket, which is where a general term always ends.
let start = self.at;
let mut depth = 0i32;
while let Some(t) = self.peek() {
match t {
Tok::LParen | Tok::LBrack => depth += 1,
Tok::RParen | Tok::RBrack => {
if depth == 0 {
break;
}
depth -= 1;
}
Tok::Comma if depth == 0 => break,
Tok::Dot if depth == 0 => break,
_ => {}
}
self.at += 1;
}
if self.at == start {
self.at += 1;
}
GTerm::Other(format!("{:?}", &self.toks[start..self.at.min(self.toks.len())]))
}
}
}
}
fn parents_of(g: >erm) -> Vec<Parent> {
let items: &[GTerm] = match g {
GTerm::List(xs) => xs,
single => std::slice::from_ref(single),
};
items
.iter()
.map(|p| match p {
GTerm::Word(w) => Parent::Named(w.clone()),
GTerm::Func(f, args) if f == "inference" => match inference_of(args) {
Some(inf) => Parent::Inline(Box::new(inf)),
None => Parent::Other(p.render()),
},
other => Parent::Other(other.render()),
})
.collect()
}
fn inference_of(args: &[GTerm]) -> Option<Inference> {
let rule = args.first()?.word()?.to_string();
let parents = args.get(2).map(parents_of).unwrap_or_default();
Some(Inference { rule, parents })
}
fn source_of(g: >erm) -> Source {
match g {
GTerm::Func(f, args) if f == "file" => Source::File {
path: args.first().map(GTerm::render).unwrap_or_default(),
name: args.get(1).and_then(|n| n.word()).map(|s| s.to_string()),
},
GTerm::Func(f, args) if f == "inference" => match inference_of(args) {
Some(inf) => Source::Inference(inf),
None => Source::Other(g.render()),
},
GTerm::Func(f, args) if f == "introduced" => Source::Introduced {
rule: args.first().and_then(|r| r.word()).unwrap_or("introduced").to_string(),
detail: args.iter().skip(1).map(GTerm::render).collect::<Vec<_>>().join(","),
},
GTerm::Word(w) => Source::Name(w.clone()),
other => Source::Other(other.render()),
}
}
/// The SZS status the prover printed, if it printed one.
///
/// The LAST status line wins: E prints an input status before its result, and
/// taking the first would report the wrong one. The word is ECHOED and never
/// acted on as though it were evidence.
pub fn szs_status(text: &str) -> Option<String> {
let mut last = None;
for line in text.lines() {
if let Some(i) = line.find("SZS status") {
let rest = line[i + "SZS status".len()..].trim_start();
let word: String =
rest.chars().take_while(|c| c.is_ascii_alphanumeric() || *c == '_').collect();
if !word.is_empty() {
last = Some(word);
}
}
}
last
}
/// Read every `fof(…)` / `cnf(…)` annotated formula out of a prover's output.
///
/// When the text carries an `SZS output start` / `SZS output end` pair, ONLY
/// what lies between them is read. E prints its saturation state before the
/// proof, in the same `cnf(…)` syntax and with names it reuses, and a reader
/// that swallowed those would build a derivation out of clauses the prover had
/// abandoned.
pub fn parse_derivation(text: &str) -> Result<Vec<Annotated>, String> {
let body = match (text.find("SZS output start"), text.find("SZS output end")) {
(Some(a), Some(b)) if b > a => {
let after = &text[a..];
let nl = after.find('\n').map(|n| a + n + 1).unwrap_or(a);
&text[nl..b]
}
_ => text,
};
parse_annotated_list(body)
}
/// Read every annotated formula in a plain TPTP file. Used for the problem
/// side, where there is no SZS block.
pub fn parse_problem(text: &str) -> Result<Vec<Annotated>, String> {
parse_annotated_list(text)
}
fn parse_annotated_list(text: &str) -> Result<Vec<Annotated>, String> {
let toks = lex(text)?;
let mut p = Parser { toks, at: 0 };
let mut out = Vec::new();
while let Some(t) = p.peek().cloned() {
let kind = match &t {
Tok::Word(w) => w.clone(),
_ => {
return Err(format!(
"expected `fof` or `cnf` at the start of an annotated formula, found {t:?}"
));
}
};
match kind.as_str() {
"fof" | "cnf" => {}
"tff" | "thf" | "tcf" | "tpi" => {
return Err(format!(
"`{kind}` is outside this reader's language. Only untyped first-order (fof \
and cnf) is read, because that is what src/tptp.rs emits and what the \
adequacy theorem is about"
));
}
other => return Err(format!("unknown annotated-formula kind `{other}`")),
}
p.at += 1;
p.expect(&Tok::LParen)?;
let name = p.name()?;
p.expect(&Tok::Comma)?;
let role = p.name()?;
p.expect(&Tok::Comma)?;
let formula = p.formula(0)?;
let mut source = None;
if p.eat(&Tok::Comma) {
source = Some(source_of(&p.general()));
// Useful-info fields, e.g. E's trailing `['proof']`. Read and
// discarded: nothing in them is load-bearing here.
while p.eat(&Tok::Comma) {
let _ = p.general();
}
}
p.expect(&Tok::RParen)?;
p.expect(&Tok::Dot)?;
out.push(Annotated { name, role, formula, source });
}
Ok(out)
}
/// The problem this repository's exporter emits, embedded into the reader's
/// wider language.
///
/// Used by `tests/tstp_parser_test.rs` to pin the reader against the emitter:
/// parsing `fof::form(f)` must give back exactly `from_tptp_form(f)`. A reader
/// that silently normalised on the way in would pass a leaf check it should
/// have failed, which is the one thing this module must not do.
pub fn from_tptp_form(f: &crate::tptp::Form) -> Formula {
use crate::tptp::{Form, Term as T, sym};
fn term(t: &T) -> Term {
match t {
T::Var(n) => Term::Var(format!("X{n}")),
T::Const(a) => Term::Fun(sym::constant(a), Vec::new()),
}
}
match f {
Form::App1(p, t) => Formula::Pred(sym::p1(p), vec![term(t)]),
Form::App2(p, t, u) => Formula::Pred(sym::p2(p), vec![term(t), term(u)]),
Form::Eq(t, u) => Formula::Eq(term(t), term(u)),
Form::Tru => Formula::True,
Form::Fls => Formula::False,
Form::Neg(g) => Formula::Not(Box::new(from_tptp_form(g))),
Form::And(g, h) => {
Formula::And(Box::new(from_tptp_form(g)), Box::new(from_tptp_form(h)))
}
Form::Or(g, h) => Formula::Or(Box::new(from_tptp_form(g)), Box::new(from_tptp_form(h))),
Form::Imp(g, h) => {
Formula::Imp(Box::new(from_tptp_form(g)), Box::new(from_tptp_form(h)))
}
Form::All(n, g) => Formula::All(format!("X{n}"), Box::new(from_tptp_form(g))),
Form::Ex(n, g) => Formula::Ex(format!("X{n}"), Box::new(from_tptp_form(g))),
}
}
// ── Clause view, unification, and the resolvent ────────────────────────────
/// An atom in a clause. Equality is stored with its arguments in a canonical
/// order, because `s = t` and `t = s` are the same literal and a set
/// comparison that treated them as two would refuse correct steps.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum Atom {
Pred(String, Vec<Term>),
Eq(Term, Term),
}
impl Atom {
fn eq_canon(a: Term, b: Term) -> Atom {
if a <= b { Atom::Eq(a, b) } else { Atom::Eq(b, a) }
}
fn vars(&self, out: &mut BTreeSet<String>) {
match self {
Atom::Pred(_, args) => args.iter().for_each(|a| a.vars(out)),
Atom::Eq(a, b) => {
a.vars(out);
b.vars(out);
}
}
}
fn render(&self) -> String {
let mut s = String::new();
match self {
Atom::Pred(p, args) => {
s.push_str(p);
if !args.is_empty() {
s.push('(');
for (i, a) in args.iter().enumerate() {
if i > 0 {
s.push(',');
}
a.render(&mut s);
}
s.push(')');
}
}
Atom::Eq(a, b) => {
a.render(&mut s);
s.push('=');
b.render(&mut s);
}
}
s
}
}
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Lit {
positive: bool,
atom: Atom,
}
impl Lit {
fn render(&self) -> String {
if self.positive { self.atom.render() } else { format!("~{}", self.atom.render()) }
}
}
/// A formula seen as a clause: a set of literals under an implicit universal
/// prefix.
///
/// `$false` disjuncts are DROPPED and a `$true` disjunct makes the whole thing
/// a tautology. Both are ordinary clause normalisations and both are needed on
/// real output: Vampire prints AVATAR conclusions as `$false | (spl1 | ~spl2)`,
/// where the `$false` is the empty clause part and the rest is the assertion.
#[derive(Clone, Debug, PartialEq, Eq)]
struct Clause {
lits: Vec<Lit>,
tautology: bool,
}
impl Clause {
fn render(&self) -> String {
if self.tautology {
return "$true".into();
}
if self.lits.is_empty() {
return "$false".into();
}
self.lits.iter().map(Lit::render).collect::<Vec<_>>().join(" | ")
}
fn normalise(mut lits: Vec<Lit>, tautology: bool) -> Clause {
lits.sort();
lits.dedup();
Clause { lits, tautology }
}
fn vars(&self) -> BTreeSet<String> {
let mut v = BTreeSet::new();
self.lits.iter().for_each(|l| l.atom.vars(&mut v));
v
}
}
/// Read a formula as a clause, or say why it is not one.
fn clause_view(f: &Formula) -> Result<Clause, &'static str> {
fn body<'a>(f: &'a Formula, bound: &mut Vec<&'a str>) -> &'a Formula {
match f {
Formula::All(v, g) => {
bound.push(v);
body(g, bound)
}
other => other,
}
}
fn lits(f: &Formula, out: &mut Vec<Lit>, taut: &mut bool) -> Result<(), &'static str> {
match f {
Formula::Or(a, b) => {
lits(a, out, taut)?;
lits(b, out, taut)
}
Formula::False => Ok(()),
Formula::True => {
*taut = true;
Ok(())
}
Formula::Pred(p, args) => {
out.push(Lit { positive: true, atom: Atom::Pred(p.clone(), args.clone()) });
Ok(())
}
Formula::Eq(a, b) => {
out.push(Lit { positive: true, atom: Atom::eq_canon(a.clone(), b.clone()) });
Ok(())
}
Formula::Not(g) => match &**g {
Formula::Pred(p, args) => {
out.push(Lit { positive: false, atom: Atom::Pred(p.clone(), args.clone()) });
Ok(())
}
Formula::Eq(a, b) => {
out.push(Lit {
positive: false,
atom: Atom::eq_canon(a.clone(), b.clone()),
});
Ok(())
}
Formula::True => Ok(()),
Formula::False => {
*taut = true;
Ok(())
}
_ => Err("a negation over a compound formula is not a literal"),
},
_ => Err("a connective other than disjunction appears in the clause body"),
}
}
let mut bound = Vec::new();
let inner = body(f, &mut bound);
if matches!(inner, Formula::Ex(_, _) | Formula::All(_, _)) {
return Err("a quantifier appears below the universal prefix");
}
let mut out = Vec::new();
let mut taut = false;
lits(inner, &mut out, &mut taut)?;
Ok(Clause::normalise(out, taut))
}
type Subst = HashMap<String, Term>;
fn walk(t: &Term, s: &Subst) -> Term {
match t {
Term::Var(v) => match s.get(v) {
Some(b) => walk(b, s),
None => t.clone(),
},
Term::Fun(f, args) => Term::Fun(f.clone(), args.iter().map(|a| walk(a, s)).collect()),
}
}
fn occurs(v: &str, t: &Term, s: &Subst) -> bool {
match walk(t, s) {
Term::Var(u) => u == v,
Term::Fun(_, args) => args.iter().any(|a| occurs(v, a, s)),
}
}
/// Syntactic first-order unification with an occurs check. No theory, no
/// ordering, no AC: a most general unifier or nothing.
fn unify(a: &Term, b: &Term, s: &mut Subst) -> bool {
let (x, y) = (walk(a, s), walk(b, s));
match (&x, &y) {
(Term::Var(u), Term::Var(v)) if u == v => true,
(Term::Var(u), other) | (other, Term::Var(u)) => {
if occurs(u, other, s) {
return false;
}
s.insert(u.clone(), other.clone());
true
}
(Term::Fun(f, xs), Term::Fun(g, ys)) => {
f == g && xs.len() == ys.len() && xs.iter().zip(ys).all(|(p, q)| unify(p, q, s))
}
}
}
fn unify_atoms(a: &Atom, b: &Atom) -> Option<Subst> {
let mut s = Subst::new();
match (a, b) {
(Atom::Pred(p, xs), Atom::Pred(q, ys)) => {
if p != q || xs.len() != ys.len() {
return None;
}
for (x, y) in xs.iter().zip(ys) {
if !unify(x, y, &mut s) {
return None;
}
}
Some(s)
}
(Atom::Eq(x1, y1), Atom::Eq(x2, y2)) => {
// Equality is symmetric, so both orientations are tried. The
// canonical storage order is a comparison convenience and must not
// become a restriction on what unifies.
for (p, q) in [(x2, y2), (y2, x2)] {
let mut t = Subst::new();
if unify(x1, p, &mut t) && unify(y1, q, &mut t) {
return Some(t);
}
}
None
}
_ => None,
}
}
fn apply_atom(a: &Atom, s: &Subst) -> Atom {
match a {
Atom::Pred(p, args) => Atom::Pred(p.clone(), args.iter().map(|t| walk(t, s)).collect()),
Atom::Eq(x, y) => Atom::eq_canon(walk(x, s), walk(y, s)),
}
}
fn apply_clause(c: &[Lit], s: &Subst) -> Vec<Lit> {
c.iter().map(|l| Lit { positive: l.positive, atom: apply_atom(&l.atom, s) }).collect()
}
/// Rename every variable of a clause with a prefix nothing else uses, so two
/// premises cannot share a variable by accident.
fn rename_apart(c: &Clause, tag: &str) -> Clause {
let mut s = Subst::new();
for v in c.vars() {
s.insert(v.clone(), Term::Var(format!("{tag}{v}")));
}
Clause::normalise(apply_clause(&c.lits, &s), c.tautology)
}
/// Are two clauses the same up to a BIJECTIVE renaming of their variables?
///
/// The fast path is exact set equality, which is what nearly every real step
/// hits because provers keep their variable names. The slow path pairs
/// literals with backtracking under a budget; the budget is reported rather
/// than silently treated as a mismatch, because "too big to check" and "does
/// not check out" are different facts.
fn variant(a: &Clause, b: &Clause) -> Result<bool, &'static str> {
if a.tautology != b.tautology {
return Ok(false);
}
if a.tautology {
return Ok(true);
}
if a.lits == b.lits {
return Ok(true);
}
if a.lits.len() != b.lits.len() {
return Ok(false);
}
const BUDGET: u32 = 200_000;
let mut used = vec![false; b.lits.len()];
let mut fwd: HashMap<String, String> = HashMap::new();
let mut bwd: HashMap<String, String> = HashMap::new();
let mut spent = 0u32;
let ok = pair(&a.lits, &b.lits, 0, &mut used, &mut fwd, &mut bwd, &mut spent, BUDGET);
match ok {
Some(v) => Ok(v),
None => Err("the variant check ran out of budget"),
}
}
#[allow(clippy::too_many_arguments)]
fn pair(
a: &[Lit],
b: &[Lit],
i: usize,
used: &mut Vec<bool>,
fwd: &mut HashMap<String, String>,
bwd: &mut HashMap<String, String>,
spent: &mut u32,
budget: u32,
) -> Option<bool> {
if i == a.len() {
return Some(true);
}
for j in 0..b.len() {
if used[j] {
continue;
}
*spent += 1;
if *spent > budget {
return None;
}
let (f0, b0) = (fwd.clone(), bwd.clone());
if match_lit(&a[i], &b[j], fwd, bwd) {
used[j] = true;
match pair(a, b, i + 1, used, fwd, bwd, spent, budget) {
None => return None,
Some(true) => return Some(true),
Some(false) => {}
}
used[j] = false;
}
*fwd = f0;
*bwd = b0;
}
Some(false)
}
fn match_lit(
x: &Lit,
y: &Lit,
fwd: &mut HashMap<String, String>,
bwd: &mut HashMap<String, String>,
) -> bool {
if x.positive != y.positive {
return false;
}
match (&x.atom, &y.atom) {
(Atom::Pred(p, xs), Atom::Pred(q, ys)) => {
p == q
&& xs.len() == ys.len()
&& xs.iter().zip(ys).all(|(u, v)| match_term(u, v, fwd, bwd))
}
(Atom::Eq(x1, y1), Atom::Eq(x2, y2)) => {
let (f0, b0) = (fwd.clone(), bwd.clone());
if match_term(x1, x2, fwd, bwd) && match_term(y1, y2, fwd, bwd) {
return true;
}
*fwd = f0;
*bwd = b0;
match_term(x1, y2, fwd, bwd) && match_term(y1, x2, fwd, bwd)
}
_ => false,
}
}
fn match_term(
x: &Term,
y: &Term,
fwd: &mut HashMap<String, String>,
bwd: &mut HashMap<String, String>,
) -> bool {
match (x, y) {
(Term::Var(u), Term::Var(v)) => {
match (fwd.get(u).cloned(), bwd.get(v).cloned()) {
(Some(a), Some(b)) => a == *v && b == *u,
(None, None) => {
fwd.insert(u.clone(), v.clone());
bwd.insert(v.clone(), u.clone());
true
}
_ => false,
}
}
(Term::Fun(f, xs), Term::Fun(g, ys)) => {
f == g
&& xs.len() == ys.len()
&& xs.iter().zip(ys).all(|(u, v)| match_term(u, v, fwd, bwd))
}
_ => false,
}
}
// ── The derivation ─────────────────────────────────────────────────────────
/// How closely a leaf of the derivation matched the problem formula it names.
///
/// Three levels rather than a boolean, because they cost different amounts of
/// belief. `Identical` means the prover echoed our formula unchanged.
/// `AlphaEquivalent` means it renamed bound variables, which E does on every
/// axiom it reads. `AssociativityNormalised` means it also rebracketed an
/// n-ary `&` or `|`. Nothing below that is accepted.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum LeafMatch {
Identical,
AlphaEquivalent,
AssociativityNormalised,
/// Both sides are clauses and are the same clause: the same SET of
/// literals up to a renaming of variables. Needed the day CNF input
/// arrived: a prover echoes a `cnf(` axiom back in ITS literal order and
/// under an explicit `![X]:`, so `~thing | ~A | B` comes back as
/// `![X0]: (~A | ~thing | B)`. That is the same clause, and it is exact
/// under clause semantics, not a leniency: a clause IS a set.
ClauseVariant,
}
impl LeafMatch {
pub fn name(self) -> &'static str {
match self {
LeafMatch::Identical => "identical",
LeafMatch::AlphaEquivalent => "alpha_equivalent",
LeafMatch::AssociativityNormalised => "associativity_normalised",
LeafMatch::ClauseVariant => "clause_variant",
}
}
}
fn leaf_match(proof: &Formula, problem: &Formula) -> Option<LeafMatch> {
if proof == problem {
return Some(LeafMatch::Identical);
}
if alpha_eq(proof, problem) {
return Some(LeafMatch::AlphaEquivalent);
}
if alpha_eq(&proof.assoc_normalised(), &problem.assoc_normalised()) {
return Some(LeafMatch::AssociativityNormalised);
}
// Last: both read as clauses, and are the same clause as a SET of
// literals up to variable renaming. `variant` returns Err when its
// backtracking budget runs out; that is "not established", not "no".
if let (Ok(a), Ok(b)) = (clause_view(proof), clause_view(problem))
&& variant(&a, &b).unwrap_or(false)
{
return Some(LeafMatch::ClauseVariant);
}
None
}
/// A leaf that is not a formula of the problem. The reason is carried because
/// "the name is not in the problem" and "the name is there and the formula is
/// different" are different accusations.
#[derive(Clone, Debug, serde::Serialize)]
pub struct LeafFailure {
pub node: String,
pub why: String,
}
/// A symbol or a formula the prover invented. Not from the problem, not
/// derived from it, and nothing here checks that the extension is
/// conservative.
#[derive(Clone, Debug, serde::Serialize)]
pub struct Introduced {
pub node: String,
pub rule: String,
pub detail: String,
}
/// A rule this checker did not replay, with the count and the reason.
#[derive(Clone, Debug, serde::Serialize)]
pub struct Unchecked {
pub rule: String,
pub count: usize,
pub why: String,
}
/// A step whose rule IS implemented, whose shapes DO apply, and which still
/// did not reconstruct. Either the derivation is wrong or this checker is
/// incomplete for that rule; the report says both and decides neither.
#[derive(Clone, Debug, serde::Serialize)]
pub struct NotReconstructed {
pub node: String,
pub rule: String,
pub expected: String,
pub found: String,
}
/// What a checked run of this module establishes, field by field, with nothing
/// collapsed into anything else.
///
/// The shape follows `fol_solve::Outcome`, which decision 0006 item 4 fixes at
/// five never-collapsed fields: what the oracle said, what it was asked, what
/// the checker did, the one verdict word, and the reading that rides on the
/// unproved translation. The same discipline applies here and for the same
/// reason: a reader who has never opened a decision record still must not be
/// able to mistake an oracle's word for a checked one.
#[derive(Clone, Debug, serde::Serialize)]
pub struct Report {
/// What the prover said about itself. ECHOED, UNTRUSTED, and never used to
/// decide anything below.
pub szs_status: Option<String>,
/// Why the problem file could not be read, when it could not.
pub problem_error: Option<String>,
/// Why the derivation could not be read, when it could not.
pub derivation_error: Option<String>,
pub problem_formulas: usize,
/// FNV-1a 64 over the canonical rendering of the PARSED problem, so a
/// report can be tied to the file it is about. It identifies and does not
/// commit, which is decision 0006 item 7 in the same words.
pub problem_digest: String,
pub derivation_nodes: usize,
/// Every parent reference resolves and the parent relation is acyclic.
pub derivation_wellformed: bool,
pub wellformedness_failures: Vec<String>,
/// Some node is the empty clause and nothing cites it.
pub root_is_false: bool,
pub nodes_outside_the_refutation: usize,
pub leaves_total: usize,
/// Every leaf reachable from the empty clause is a formula of the problem,
/// under the name the prover gave for it and with the role the problem
/// gave it.
pub leaves_match_problem: bool,
pub leaf_match_levels: BTreeMap<&'static str, usize>,
pub leaf_failures: Vec<LeafFailure>,
pub leaves_introduced: Vec<Introduced>,
/// The conjecture's name in the problem, when the problem has one.
pub conjecture_in_problem: Option<String>,
/// The refutation uses it.
pub conjecture_used: bool,
/// The step that negates it was replayed: the child IS the negation of the
/// problem's conjecture and of nothing else.
pub conjecture_negation_checked: bool,
/// `axioms_and_the_negated_conjecture` or `axioms_alone`. Null unless the
/// structure holds, because it is a statement about a derivation this
/// module has read and not about a theory.
pub what_was_refuted: Option<&'static str>,
pub steps_total: usize,
pub steps_checked: usize,
pub steps_checked_by_rule: BTreeMap<String, usize>,
pub steps_unchecked: Vec<Unchecked>,
pub steps_not_reconstructed: Vec<NotReconstructed>,
/// The one word. See [`verdict_means`].
pub verdict: &'static str,
/// What became of the attempt to have the derivation CHECKED BY A THEOREM
/// rather than replayed. `None` when no attempt was made because the
/// structure did not hold or the leaves were not ours; otherwise says
/// either which theorem accepted it or exactly why none did.
pub certificate: Option<CertificateOutcome>,
}
/// The outcome of offering a derivation to `oo-resolution`.
///
/// `Certified` can only be built from a [`crate::verdict::Certified`] token,
/// and that token only exists after a checker exited zero naming the theorem,
/// so the word `refutation_certified` cannot be printed by any path that did
/// not run the checker.
#[derive(Clone, Debug, serde::Serialize)]
#[serde(tag = "status", rename_all = "snake_case")]
pub enum CertificateOutcome {
/// `oo-resolution` accepted. `theorem` is read from the token, which read it
/// from the checker's stdout.
Certified { theorem: &'static str, checker: String, steps: usize, certificate: String },
/// The problem was exported as FOF because it is outside the clausal
/// fragment, so the prover clausified and no resolution-only derivation
/// exists to translate. `why` is `to_cnf`'s refusal, naming the axiom.
OutsideClausalFragment { why: String },
/// Some step of the derivation is not resolution or factoring. Named, with
/// the rule, so a reader knows what kind of reasoning cost the certificate.
StepsUntranslated { untranslated: Vec<(String, String)>, translated: usize },
/// Every step translated but the chain does not reach the empty clause.
DoesNotReachFalse { translated: usize },
/// The certificate was written and `oo-resolution` is not installed to read it.
CheckerAbsent { certificate: String },
/// `oo-resolution` REFUSED a certificate this translator produced. Either a
/// defect in the translation or in the derivation; both stop the line.
CheckerRefused { exit: i32, output: String, certificate: String },
}
/// One sentence per word, so a report is readable without this file open
/// beside it.
pub fn verdict_means(v: &str) -> &'static str {
match v {
"problem_unparsed" => "the TPTP problem could not be read, so there was nothing to \
check the derivation against. Not a statement about the prover",
"derivation_unparsed" => "the prover's output could not be read as a TSTP derivation. \
Run the prover with a proof-printing option (vampire \
`--proof tptp`, eprover `--proof-object`); without one there \
is only a word",
"no_refutation_offered" => "the output contains no empty clause, so there is no \
refutation to check. This is the normal outcome of a \
satisfiable problem, a timeout or a give-up, and it is \
evidence of nothing in either direction",
"derivation_rejected" => "THE CHECKER SAID NO. Either a parent reference does not \
resolve, or the parent relation has a cycle, or a leaf of the \
refutation is not a formula of the problem. A refutation of \
something else is not a refutation of this",
"refutation_step_not_reconstructed" => "the structure holds and every leaf is ours, and \
at least one step whose rule this checker \
implements did not reconstruct from its \
premises. EITHER the derivation is wrong OR \
this checker is incomplete for that rule. This \
module does not decide which, and the step is \
named",
"refutation_structure_checked" => "the derivation is a well-founded DAG from the \
problem's own formulas to the empty clause, and NO \
inference step was replayed. It rules out a prover \
answering about a different file; it says nothing \
about whether the steps are sound",
"refutation_partially_replayed" => "the structure holds and SOME steps were recomputed \
from their premises. The unchecked rules are named \
and counted. This is the normal outcome, because \
clausification and AVATAR splitting are not checked",
"refutation_certified" => "the derivation was translated into lean/Fo's certificate format \
and oo-resolution ACCEPTED it, discharging Fo.unsat_of_check: the \
clause set in the derivation's leaves has no model, over any \
carrier. The leaves are the formulas this engine emitted \
(leaves_match_problem), so that is a refutation of OUR problem. \
This is the only word in this vocabulary that rests on a theorem",
"mu" => "the question was returned UNASKED. It puts in class position a term this ontology \
never uses as a class: undeclared, or only ever an individual, or typed skos:Concept \
and never classified with. Neither `entailed` nor `refuted` applies to a question \
outside the file's language; a prover would still answer it, with a countermodel \
to a symbol nobody constrained, and that answer would be about nothing. What is \
refused is the presupposition, not the claim",
"refutation_fully_replayed" => "the structure holds and EVERY step was recomputed. This \
is the strongest word here and it is still NOT a proof \
of unsatisfiability: the calculus's soundness is not \
machine-checked anywhere in lean/, and the replayer in \
src/tstp.rs is ordinary unverified Rust",
_ => "unrecognised verdict",
}
}
/// A node of the derivation as the checker sees it.
struct Node {
role: String,
/// `None` for a synthetic node standing for an inline inference record,
/// which carries a rule and parents but no formula of its own.
formula: Option<Formula>,
source: Option<Source>,
rule: Option<String>,
parents: Vec<String>,
}
/// The reasons a step is not replayed, written once so a report cannot end up
/// with two phrasings for the same fact.
const WHY_NO_CHECK: &str =
"this checker implements no replay for this rule. Clausification, Skolemisation, AVATAR \
splitting and every SAT-solver step are in this class";
const WHY_NOT_CLAUSE: &str =
"a premise or the conclusion is not clause-shaped, so the clause-level replay does not \
apply to this occurrence";
const WHY_NO_FORMULA: &str =
"a premise is an inline inference record and carries no formula of its own, so neither it \
nor the step it feeds can be replayed";
const WHY_ARITY: &str = "the rule was given a number of premises this replay does not handle";
const WHY_BUDGET: &str = "the clause is larger than the variant check's backtracking budget";
/// Read a problem and a prover's output, and say exactly what checks out.
pub fn check(problem_text: &str, proof_text: &str) -> Report {
let mut r = Report {
szs_status: szs_status(proof_text),
problem_error: None,
derivation_error: None,
problem_formulas: 0,
problem_digest: String::new(),
derivation_nodes: 0,
derivation_wellformed: false,
wellformedness_failures: Vec::new(),
root_is_false: false,
nodes_outside_the_refutation: 0,
leaves_total: 0,
leaves_match_problem: false,
leaf_match_levels: BTreeMap::new(),
leaf_failures: Vec::new(),
leaves_introduced: Vec::new(),
conjecture_in_problem: None,
conjecture_used: false,
conjecture_negation_checked: false,
what_was_refuted: None,
steps_total: 0,
steps_checked: 0,
steps_checked_by_rule: BTreeMap::new(),
steps_unchecked: Vec::new(),
steps_not_reconstructed: Vec::new(),
verdict: "problem_unparsed",
certificate: None,
};
// ── The problem ────────────────────────────────────────────────────────
let problem = match parse_problem(problem_text) {
Ok(p) => p,
Err(e) => {
r.problem_error = Some(e);
return r;
}
};
let mut by_name: HashMap<&str, &Annotated> = HashMap::new();
let mut canonical = String::new();
for a in &problem {
by_name.insert(a.name.as_str(), a);
let _ = writeln!(canonical, "{}\t{}", a.role, a.formula.render());
if a.role == "conjecture" {
r.conjecture_in_problem = Some(a.name.clone());
}
}
r.problem_formulas = problem.len();
r.problem_digest =
crate::tptp::checkfmt::hex16(crate::tptp::checkfmt::fnv1a64(canonical.trim_end()));
// ── The derivation ─────────────────────────────────────────────────────
let annotated = match parse_derivation(proof_text) {
Ok(a) => a,
Err(e) => {
r.derivation_error = Some(e);
r.verdict = "derivation_unparsed";
return r;
}
};
if annotated.is_empty() {
r.derivation_error = Some(
"the output carries no annotated formula. A prover asked for a verdict and not for \
a proof prints one line and no derivation; run it with vampire `--proof tptp` or \
eprover `--proof-object`"
.into(),
);
r.verdict = "derivation_unparsed";
return r;
}
let mut nodes: HashMap<String, Node> = HashMap::new();
let mut order: Vec<String> = Vec::new();
let mut duplicates: Vec<String> = Vec::new();
for a in &annotated {
let mut parents = Vec::new();
let mut rule = None;
if let Some(Source::Inference(inf)) = &a.source {
rule = Some(inf.rule.clone());
flatten_parents(&a.name, &inf.parents, &mut parents, &mut nodes, &mut order);
}
if nodes.contains_key(&a.name) {
duplicates.push(a.name.clone());
continue;
}
order.push(a.name.clone());
nodes.insert(
a.name.clone(),
Node {
role: a.role.clone(),
formula: Some(a.formula.clone()),
source: a.source.clone(),
rule,
parents,
},
);
}
r.derivation_nodes = nodes.len();
// Every parent resolves.
let mut dangling: Vec<String> = Vec::new();
for name in &order {
for p in &nodes[name].parents {
if !nodes.contains_key(p) {
dangling.push(format!("{name} cites {p}, which is not in the derivation"));
}
}
}
// The parent relation is acyclic.
let cycle = find_cycle(&order, &nodes);
for d in &duplicates {
r.wellformedness_failures
.push(format!("the name {d} is used by more than one annotated formula, so a \
parent reference to it is ambiguous"));
}
r.wellformedness_failures.extend(dangling.iter().cloned());
if let Some(c) = &cycle {
r.wellformedness_failures
.push(format!("the parent relation has a cycle: {}", c.join(" -> ")));
}
r.derivation_wellformed = r.wellformedness_failures.is_empty();
// ── The root, and what is reachable from it ────────────────────────────
let cited: HashSet<&str> =
order.iter().flat_map(|n| nodes[n].parents.iter().map(String::as_str)).collect();
let false_roots: Vec<String> = order
.iter()
.filter(|n| !cited.contains(n.as_str()))
.filter(|n| nodes[*n].formula.as_ref() == Some(&Formula::False))
.cloned()
.collect();
r.root_is_false = !false_roots.is_empty();
let mut reachable: BTreeSet<String> = BTreeSet::new();
if r.derivation_wellformed {
let mut stack: Vec<String> = false_roots.clone();
while let Some(n) = stack.pop() {
if !reachable.insert(n.clone()) {
continue;
}
for p in &nodes[&n].parents {
stack.push(p.clone());
}
}
}
r.nodes_outside_the_refutation = nodes.len().saturating_sub(reachable.len());
if !r.root_is_false {
r.verdict = if r.derivation_wellformed { "no_refutation_offered" } else { "derivation_rejected" };
return r;
}
if !r.derivation_wellformed {
r.verdict = "derivation_rejected";
return r;
}
// ── Leaves ─────────────────────────────────────────────────────────────
let mut leaves_ok = true;
// Keyed on the rule AND the reason, not on the rule alone. Two
// occurrences of `rw` can be unchecked for different reasons, and a map
// that kept only the first reason would report the other occurrences under
// a sentence that is not true of them.
let mut unchecked: BTreeMap<(String, &'static str), usize> = BTreeMap::new();
for name in &reachable {
let node = &nodes[name];
if node.rule.is_some() {
continue;
}
r.leaves_total += 1;
match &node.source {
Some(Source::Introduced { rule, detail }) => {
r.leaves_introduced.push(Introduced {
node: name.clone(),
rule: rule.clone(),
detail: detail.clone(),
});
*unchecked
.entry((
format!("introduced:{rule}"),
"the prover invented this formula and its symbols. It is not from the \
problem, and no conservativity argument is checked here",
))
.or_insert(0) += 1;
}
Some(Source::File { name: Some(orig), .. }) => {
check_leaf(name, orig, node, &by_name, &mut r, &mut leaves_ok);
}
_ => {
// No usable name. Fall back to matching the formula itself
// against the problem, and say that is what happened.
let f = node.formula.as_ref();
let hit = f.and_then(|f| {
problem.iter().find_map(|a| leaf_match(f, &a.formula).map(|m| (a, m)))
});
match hit {
Some((a, m)) => {
*r.leaf_match_levels.entry(m.name()).or_insert(0) += 1;
if a.role == "conjecture" {
r.conjecture_used = true;
}
}
None => {
leaves_ok = false;
r.leaf_failures.push(LeafFailure {
node: name.clone(),
why: format!(
"the leaf carries no `file(…)` provenance this reader \
understands and its formula `{}` is not a formula of the \
problem",
f.map(Formula::render).unwrap_or_else(|| "?".into())
),
});
}
}
}
}
}
r.leaves_match_problem = leaves_ok;
// ── Steps ──────────────────────────────────────────────────────────────
for name in &reachable {
let node = &nodes[name];
let Some(rule) = node.rule.clone() else { continue };
r.steps_total += 1;
match check_step(name, &rule, node, &nodes, &by_name, &mut r) {
StepResult::Checked(kind) => {
r.steps_checked += 1;
*r.steps_checked_by_rule.entry(kind.to_string()).or_insert(0) += 1;
}
StepResult::Unchecked(why) => {
*unchecked.entry((rule.clone(), why)).or_insert(0) += 1;
}
StepResult::NotReconstructed(nr) => r.steps_not_reconstructed.push(nr),
}
}
r.steps_unchecked = unchecked
.into_iter()
.map(|((rule, why), count)| Unchecked { rule, count, why: why.to_string() })
.collect();
// ── The verdict ────────────────────────────────────────────────────────
r.what_was_refuted = Some(if r.conjecture_used {
"axioms_and_the_negated_conjecture"
} else {
"axioms_alone"
});
r.verdict = if !r.leaves_match_problem {
"derivation_rejected"
} else if !r.steps_not_reconstructed.is_empty() {
"refutation_step_not_reconstructed"
} else if r.steps_unchecked.is_empty() && r.steps_checked == r.steps_total {
"refutation_fully_replayed"
} else if r.steps_checked > 0 {
"refutation_partially_replayed"
} else {
"refutation_structure_checked"
};
r
}
/// Give every inline inference record a node of its own, so that its parent
/// references are still resolved and its rule is still counted.
fn flatten_parents(
owner: &str,
parents: &[Parent],
out: &mut Vec<String>,
nodes: &mut HashMap<String, Node>,
order: &mut Vec<String>,
) {
for (i, p) in parents.iter().enumerate() {
match p {
Parent::Named(n) => out.push(n.clone()),
Parent::Other(o) => {
let name = format!("{owner}::other{i}");
order.push(name.clone());
nodes.insert(
name.clone(),
Node {
role: "plain".into(),
formula: None,
source: Some(Source::Other(o.clone())),
rule: Some(format!("unreadable_parent:{o}")),
parents: Vec::new(),
},
);
out.push(name);
}
Parent::Inline(inf) => {
let name = format!("{owner}::inline{i}");
let mut inner = Vec::new();
flatten_parents(&name, &inf.parents, &mut inner, nodes, order);
order.push(name.clone());
nodes.insert(
name.clone(),
Node {
role: "plain".into(),
formula: None,
source: None,
rule: Some(inf.rule.clone()),
parents: inner,
},
);
out.push(name);
}
}
}
}
fn find_cycle(order: &[String], nodes: &HashMap<String, Node>) -> Option<Vec<String>> {
#[derive(Clone, Copy, PartialEq)]
enum Mark {
White,
Grey,
Black,
}
let mut mark: HashMap<String, Mark> =
order.iter().map(|n| (n.clone(), Mark::White)).collect();
let mut path: Vec<String> = Vec::new();
// Iterative depth-first search. A derivation from a real prover can be
// thousands of nodes deep and a recursive walk would overflow the stack on
// the one input that matters.
for start in order {
if mark.get(start) != Some(&Mark::White) {
continue;
}
let mut stack: Vec<(String, usize)> = vec![(start.clone(), 0)];
mark.insert(start.clone(), Mark::Grey);
path.push(start.clone());
while let Some((node, idx)) = stack.pop() {
let parents = nodes.get(&node).map(|n| n.parents.clone()).unwrap_or_default();
if idx < parents.len() {
stack.push((node, idx + 1));
let child = parents[idx].clone();
match mark.get(&child) {
Some(Mark::Grey) => {
let mut c = path.clone();
c.push(child);
return Some(c);
}
Some(Mark::White) => {
mark.insert(child.clone(), Mark::Grey);
path.push(child.clone());
stack.push((child, 0));
}
_ => {}
}
} else {
mark.insert(node, Mark::Black);
path.pop();
}
}
}
None
}
fn check_leaf(
name: &str,
orig: &str,
node: &Node,
by_name: &HashMap<&str, &Annotated>,
r: &mut Report,
leaves_ok: &mut bool,
) {
let Some(problem_formula) = by_name.get(orig) else {
*leaves_ok = false;
r.leaf_failures.push(LeafFailure {
node: name.to_string(),
why: format!(
"the leaf says it came from `{orig}` in the problem file, and the problem has \
no formula of that name. The prover was given a different file"
),
});
return;
};
let Some(f) = &node.formula else {
*leaves_ok = false;
r.leaf_failures.push(LeafFailure {
node: name.to_string(),
why: "the leaf carries no formula".into(),
});
return;
};
match leaf_match(f, &problem_formula.formula) {
None => {
*leaves_ok = false;
r.leaf_failures.push(LeafFailure {
node: name.to_string(),
why: format!(
"the leaf says it is `{orig}` from the problem, and it is a different \
formula. Problem: {}. Derivation: {}",
problem_formula.formula.render(),
f.render()
),
});
}
Some(m) => {
if node.role != problem_formula.role {
// A conjecture presented as an axiom would make the refutation
// prove nothing about entailment, so this is a rejection and
// not a note.
*leaves_ok = false;
r.leaf_failures.push(LeafFailure {
node: name.to_string(),
why: format!(
"the leaf is `{orig}` from the problem with role `{}`, and the problem \
gives it role `{}`. A conjecture used as an axiom refutes nothing",
node.role, problem_formula.role
),
});
return;
}
*r.leaf_match_levels.entry(m.name()).or_insert(0) += 1;
if problem_formula.role == "conjecture" {
r.conjecture_used = true;
}
}
}
}
enum StepResult {
Checked(&'static str),
Unchecked(&'static str),
NotReconstructed(NotReconstructed),
}
/// The rules this module replays, and the shape of each replay.
///
/// Anything not named here is unchecked and is reported as unchecked. The list
/// is short on purpose: a rule is in it only when the check is exact.
fn check_step(
name: &str,
rule: &str,
node: &Node,
nodes: &HashMap<String, Node>,
by_name: &HashMap<&str, &Annotated>,
r: &mut Report,
) -> StepResult {
let Some(child) = &node.formula else {
return StepResult::Unchecked(WHY_NO_FORMULA);
};
let premises: Vec<Option<&Formula>> =
node.parents.iter().map(|p| nodes[p].formula.as_ref()).collect();
match rule {
// The negation of the conjecture. Checked exactly, and it is the step
// that makes the refutation say something about ENTAILMENT rather than
// about the axioms alone.
"negated_conjecture" | "assume_negation" => {
if premises.len() != 1 {
return StepResult::Unchecked(WHY_ARITY);
}
let Some(parent) = premises[0] else {
return StepResult::Unchecked(WHY_NO_FORMULA);
};
let negated = Formula::Not(Box::new(parent.clone()));
if leaf_match(child, &negated).is_some() {
let parent_name = &node.parents[0];
let is_conjecture = nodes
.get(parent_name)
.is_some_and(|p| p.role == "conjecture")
|| by_name
.get(parent_name.as_str())
.is_some_and(|a| a.role == "conjecture");
if is_conjecture {
r.conjecture_negation_checked = true;
}
StepResult::Checked("negation_of_the_conjecture")
} else {
StepResult::NotReconstructed(NotReconstructed {
node: name.to_string(),
rule: rule.to_string(),
expected: negated.render(),
found: child.render(),
})
}
}
// Binary resolution, and the simplification rules whose conclusion IS
// the binary resolvent. See the module docstring for why subsumption
// resolution is exactly this check and not a weaker one.
"resolution"
| "subsumption_resolution"
| "forward_subsumption_resolution"
| "backward_subsumption_resolution" => {
if premises.len() != 2 {
return StepResult::Unchecked(WHY_ARITY);
}
let (Some(p0), Some(p1)) = (premises[0], premises[1]) else {
return StepResult::Unchecked(WHY_NO_FORMULA);
};
let (Ok(a), Ok(b), Ok(c)) = (clause_view(p0), clause_view(p1), clause_view(child))
else {
return StepResult::Unchecked(WHY_NOT_CLAUSE);
};
match resolvent_matches(&a, &b, &c) {
Ok(true) => StepResult::Checked("binary_resolvent"),
Ok(false) => StepResult::NotReconstructed(NotReconstructed {
node: name.to_string(),
rule: rule.to_string(),
expected: format!(
"a binary resolvent of `{}` and `{}`",
a.render(),
b.render()
),
found: c.render(),
}),
Err(_) => StepResult::Unchecked(WHY_BUDGET),
}
}
// Factoring: two literals of one premise unified and merged.
"factoring" | "factor" => one_premise(name, rule, &premises, child, |p, c| {
for i in 0..p.lits.len() {
for j in (i + 1)..p.lits.len() {
if p.lits[i].positive != p.lits[j].positive {
continue;
}
if let Some(s) = unify_atoms(&p.lits[i].atom, &p.lits[j].atom) {
let cand = Clause::normalise(apply_clause(&p.lits, &s), p.tautology);
if variant(&cand, c)? {
return Ok(true);
}
}
}
}
Ok(false)
})
.map_checked("factor"),
// The clause is the same set of literals as its premise. Covers
// duplicate literal removal and Vampire's `flattening`, which
// reassociates a disjunction and changes nothing else.
"duplicate_literal_removal" | "flattening" => {
one_premise(name, rule, &premises, child, variant).map_checked("same_clause")
}
// Literals `s != s` with syntactically identical sides, deleted.
"trivial_inequality_removal" => one_premise(name, rule, &premises, child, |p, c| {
let kept: Vec<Lit> = p
.lits
.iter()
.filter(|l| !matches!(&l.atom, Atom::Eq(x, y) if !l.positive && x == y))
.cloned()
.collect();
variant(&Clause::normalise(kept, p.tautology), c)
})
.map_checked("trivial_inequality_removed"),
// `C ∨ s ≠ t` with σ = mgu(s, t) gives `Cσ`.
"equality_resolution" => one_premise(name, rule, &premises, child, |p, c| {
for (i, l) in p.lits.iter().enumerate() {
if l.positive {
continue;
}
let Atom::Eq(x, y) = &l.atom else { continue };
let mut s = Subst::new();
if !unify(x, y, &mut s) {
continue;
}
let rest: Vec<Lit> =
p.lits.iter().enumerate().filter(|(k, _)| *k != i).map(|(_, l)| l.clone()).collect();
let cand = Clause::normalise(apply_clause(&rest, &s), p.tautology);
if variant(&cand, c)? {
return Ok(true);
}
}
Ok(false)
})
.map_checked("equality_resolved"),
_ => StepResult::Unchecked(WHY_NO_CHECK),
}
}
/// The outcome of a one-premise replay before it is given a name.
enum OneOf {
Ok,
No(NotReconstructed),
Skip(&'static str),
}
impl OneOf {
fn map_checked(self, kind: &'static str) -> StepResult {
match self {
OneOf::Ok => StepResult::Checked(kind),
OneOf::Skip(why) => StepResult::Unchecked(why),
OneOf::No(nr) => StepResult::NotReconstructed(nr),
}
}
}
fn one_premise(
name: &str,
rule: &str,
premises: &[Option<&Formula>],
child: &Formula,
f: impl Fn(&Clause, &Clause) -> Result<bool, &'static str>,
) -> OneOf {
if premises.len() != 1 {
return OneOf::Skip(WHY_ARITY);
}
let Some(p) = premises[0] else {
return OneOf::Skip(WHY_NO_FORMULA);
};
let (Ok(pc), Ok(cc)) = (clause_view(p), clause_view(child)) else {
return OneOf::Skip(WHY_NOT_CLAUSE);
};
match f(&pc, &cc) {
Ok(true) => OneOf::Ok,
Ok(false) => OneOf::No(NotReconstructed {
node: name.to_string(),
rule: rule.to_string(),
expected: format!("a `{rule}` conclusion of `{}`", pc.render()),
found: cc.render(),
}),
Err(why) => OneOf::Skip(why),
}
}
/// Is `c` a binary resolvent of `a` and `b`?
///
/// Every complementary literal pair is tried, on standardised-apart copies.
/// The resolvent is taken as a SET, which is what makes the check agree with
/// a prover that factors the resolvent on the way out.
fn resolvent_matches(a: &Clause, b: &Clause, c: &Clause) -> Result<bool, &'static str> {
let a = rename_apart(a, "_a");
let b = rename_apart(b, "_b");
for (i, la) in a.lits.iter().enumerate() {
for (j, lb) in b.lits.iter().enumerate() {
if la.positive == lb.positive {
continue;
}
let Some(s) = unify_atoms(&la.atom, &lb.atom) else { continue };
let mut rest: Vec<Lit> = Vec::new();
rest.extend(a.lits.iter().enumerate().filter(|(k, _)| *k != i).map(|(_, l)| l.clone()));
rest.extend(b.lits.iter().enumerate().filter(|(k, _)| *k != j).map(|(_, l)| l.clone()));
let cand =
Clause::normalise(apply_clause(&rest, &s), a.tautology || b.tautology);
if variant(&cand, c)? {
return Ok(true);
}
}
}
Ok(false)
}
// ── Translating a derivation into an Fo certificate ────────────────────────
//
// `lean/Fo` checks a resolution refutation and proves `Fo.unsat_of_check`. This
// turns the part of a prover's derivation that IS resolution into that
// certificate format, so the part that can be checked by a machine-checked
// theorem is checked by one rather than replayed by the unverified Rust above.
//
// What does NOT translate is named and counted, never skipped. Clausification,
// Skolemisation, AVATAR splitting and every form of equality reasoning are
// outside the calculus, and a certificate covering only some steps does not
// reach the empty clause, so `oo-resolution` refuses it. That refusal is the
// correct answer and the honest one: a partial translation is not a proof.
/// A certificate in `lean/Fo`'s format, and what had to be left out of it.
#[derive(Debug, Clone)]
pub struct FoCertificate {
/// The certificate text, ready for `oo-resolution`.
pub text: String,
/// Steps turned into resolution inferences.
pub translated: usize,
/// Steps that are not resolution, by name and rule. Never silently dropped.
pub untranslated: Vec<(String, String)>,
/// Does the certificate reach the empty clause through translated steps
/// alone? Only then can `oo-resolution` accept it.
pub reaches_false: bool,
}
/// Numbers for the names a derivation uses. `Fo` indexes its symbols, because
/// a checker comparing terms should compare numbers rather than strings.
#[derive(Default)]
struct SymTab {
preds: std::collections::HashMap<String, usize>,
funs: std::collections::HashMap<String, usize>,
vars: std::collections::HashMap<String, usize>,
}
impl SymTab {
fn pred(&mut self, n: &str) -> usize {
let k = self.preds.len();
*self.preds.entry(n.to_string()).or_insert(k)
}
fn fun(&mut self, n: &str) -> usize {
let k = self.funs.len();
*self.funs.entry(n.to_string()).or_insert(k)
}
fn var(&mut self, n: &str) -> usize {
let k = self.vars.len();
*self.vars.entry(n.to_string()).or_insert(k)
}
}
/// The variable-renaming prefixes `resolvent_witness` uses, stripped back off
/// when a substitution is split between the two parents.
fn strip_tag(v: &str) -> &str {
v.strip_prefix("_a").or_else(|| v.strip_prefix("_b")).unwrap_or(v)
}
fn render_term(t: &Term, st: &mut SymTab) -> String {
match t {
Term::Var(v) => format!("v{}", st.var(strip_tag(v))),
Term::Fun(f, args) => {
let n = st.fun(f);
if args.is_empty() {
format!("f{n}")
} else {
let inner: Vec<String> = args.iter().map(|a| render_term(a, st)).collect();
format!("f{n}[{}]", inner.join(","))
}
}
}
}
fn render_lit(l: &Lit, st: &mut SymTab) -> String {
let sign = if l.positive { '+' } else { '-' };
match &l.atom {
Atom::Pred(p, args) => {
let n = st.pred(p);
if args.is_empty() {
format!("{sign}p{n}")
} else {
let inner: Vec<String> = args.iter().map(|a| render_term(a, st)).collect();
format!("{sign}p{n}[{}]", inner.join(","))
}
}
// Equality is rendered as an ordinary predicate. That is sound for
// RESOLUTION on equality atoms and says nothing about equality
// REASONING: paramodulation and equality resolution are not in this
// calculus, and steps using them are reported untranslated.
Atom::Eq(a, b) => {
let n = st.pred("$equals");
format!("{sign}p{n}[{},{}]", render_term(a, st), render_term(b, st))
}
}
}
fn render_clause(c: &Clause, st: &mut SymTab) -> String {
c.lits.iter().map(|l| render_lit(l, st)).collect::<Vec<_>>().join(" ")
}
fn render_subst(s: &Subst, tag: &str, st: &mut SymTab) -> String {
let mut parts: Vec<String> = Vec::new();
let mut keys: Vec<&String> = s.keys().collect();
keys.sort();
for k in keys {
if let Some(bare) = k.strip_prefix(tag) {
parts.push(format!("{}={}", st.var(bare), render_term(&walk(&s[k], s), st)));
}
}
parts.join(";")
}
/// Like `resolvent_matches`, but returns the witness instead of a verdict: the
/// two literals resolved and the substitution that made them complementary.
fn resolvent_witness(
a: &Clause,
b: &Clause,
c: &Clause,
) -> Option<(Clause, Clause, usize, usize, Subst)> {
let ra = rename_apart(a, "_a");
let rb = rename_apart(b, "_b");
for (i, la) in ra.lits.iter().enumerate() {
for (j, lb) in rb.lits.iter().enumerate() {
if la.positive == lb.positive {
continue;
}
let Some(s) = unify_atoms(&la.atom, &lb.atom) else { continue };
let mut rest: Vec<Lit> = Vec::new();
rest.extend(ra.lits.iter().enumerate().filter(|(k, _)| *k != i).map(|(_, l)| l.clone()));
rest.extend(rb.lits.iter().enumerate().filter(|(k, _)| *k != j).map(|(_, l)| l.clone()));
let cand = Clause::normalise(apply_clause(&rest, &s), ra.tautology || rb.tautology);
if variant(&cand, c).unwrap_or(false) {
return Some((ra, rb, i, j, s));
}
}
}
None
}
/// Turn the resolution part of a derivation into an `Fo` certificate.
pub fn to_fo_certificate(proof_text: &str) -> Result<FoCertificate, String> {
let nodes = parse_derivation(proof_text)?;
let mut clauses: std::collections::HashMap<String, Clause> = std::collections::HashMap::new();
let mut ids: std::collections::HashMap<String, usize> = std::collections::HashMap::new();
let mut st = SymTab::default();
let mut out = String::new();
let mut lines = String::new();
let mut translated = 0usize;
let mut untranslated: Vec<(String, String)> = Vec::new();
let mut next = 1usize;
let mut reaches_false = false;
for n in &nodes {
let Ok(cl) = clause_view(&n.formula) else {
untranslated.push((n.name.clone(), "not a clause".into()));
continue;
};
match &n.source {
Some(Source::File { .. }) => {
let id = next;
next += 1;
ids.insert(n.name.clone(), id);
clauses.insert(n.name.clone(), cl.clone());
out.push_str(&format!("c\t{id}\t{}\n", render_clause(&cl, &mut st)));
}
Some(Source::Inference(inf)) => {
let parents: Vec<&String> = inf
.parents
.iter()
.filter_map(|p| match p {
Parent::Named(s) => Some(s),
_ => None,
})
.collect();
// The rule NAME is a hint and not a gate. E calls every
// inference `spm`, including ones that are ordinary binary
// resolution, and Vampire spells subsumption resolution four
// ways. Rather than keep a list of spellings, every two-parent
// step is offered to `resolvent_witness`, and a step is
// resolution exactly when a witness is found. That is a check
// rather than a belief about what a prover calls things.
//
// A ONE-parent step whose conclusion is a variant of its
// parent is a re-statement: E emits several per proof
// (`fof_simplification`, `cn`). It carries no inference, so it
// is recorded as an alias rather than a line.
if parents.len() == 1
&& let Some(pc) = clauses.get(parents[0])
&& variant(pc, &cl).unwrap_or(false)
&& let Some(&pid) = ids.get(parents[0])
{
ids.insert(n.name.clone(), pid);
clauses.insert(n.name.clone(), cl.clone());
continue;
}
if parents.len() != 2 {
untranslated.push((n.name.clone(), inf.rule.clone()));
continue;
}
let (Some(a), Some(b)) = (clauses.get(parents[0]), clauses.get(parents[1])) else {
untranslated.push((n.name.clone(), format!("{} (a parent is untranslated)", inf.rule)));
continue;
};
let (Some(&ia), Some(&ib)) = (ids.get(parents[0]), ids.get(parents[1])) else {
untranslated.push((n.name.clone(), format!("{} (a parent has no id)", inf.rule)));
continue;
};
let Some((ra, rb, i, j, s)) = resolvent_witness(a, b, &cl) else {
untranslated.push((n.name.clone(), format!("{} (no resolvent witness)", inf.rule)));
continue;
};
let id = next;
next += 1;
ids.insert(n.name.clone(), id);
clauses.insert(n.name.clone(), cl.clone());
let restc: Vec<Lit> =
ra.lits.iter().enumerate().filter(|(k, _)| *k != i).map(|(_, l)| l.clone()).collect();
let restd: Vec<Lit> =
rb.lits.iter().enumerate().filter(|(k, _)| *k != j).map(|(_, l)| l.clone()).collect();
let lc = render_lit(&ra.lits[i], &mut st);
let ld = render_lit(&rb.lits[j], &mut st);
let sc = render_subst(&s, "_a", &mut st);
let sd = render_subst(&s, "_b", &mut st);
let rc = restc.iter().map(|l| render_lit(l, &mut st)).collect::<Vec<_>>().join(" ");
let rd = restd.iter().map(|l| render_lit(l, &mut st)).collect::<Vec<_>>().join(" ");
let concl = render_clause(&cl, &mut st);
lines.push_str(&format!(
"r\t{id}\t{concl}\t{ia}\t{lc}\t{sc}\t{rc}\t{ib}\t{ld}\t{sd}\t{rd}\n"
));
translated += 1;
if cl.lits.is_empty() && !cl.tautology {
reaches_false = true;
}
}
// `cnf(c_0_7, …, c_0_5).` A bare name in the source position is a
// re-statement that some printers use; E emits them freely. Same
// clause, same identifier, no inference.
Some(Source::Name(parent)) => {
if let (Some(&pid), Some(pc)) = (ids.get(parent), clauses.get(parent))
&& variant(pc, &cl).unwrap_or(false)
{
ids.insert(n.name.clone(), pid);
clauses.insert(n.name.clone(), cl.clone());
continue;
}
untranslated.push((n.name.clone(), format!("restated from {parent}")));
}
_ => untranslated.push((n.name.clone(), "introduced".into())),
}
}
out.push_str(&lines);
Ok(FoCertificate { text: out, translated, untranslated, reaches_false })
}
/// The JSON one check reports, with the vocabulary written out beside the
/// verdict, the way `fol_solve::outcome_json` does.
pub fn report_json(r: &Report) -> serde_json::Value {
serde_json::json!({
"szs_status": r.szs_status,
"szs_status_means": "WHAT THE PROVER SAID ABOUT ITSELF. Echoed, untrusted, and used to \
decide nothing in this report",
"problem_error": r.problem_error,
"derivation_error": r.derivation_error,
"problem_formulas": r.problem_formulas,
"problem_digest": r.problem_digest,
"derivation_nodes": r.derivation_nodes,
"derivation_wellformed": r.derivation_wellformed,
"wellformedness_failures": r.wellformedness_failures,
"root_is_false": r.root_is_false,
"nodes_outside_the_refutation": r.nodes_outside_the_refutation,
"leaves_total": r.leaves_total,
"leaves_match_problem": r.leaves_match_problem,
"leaf_match_levels": r.leaf_match_levels,
"leaf_failures": r.leaf_failures,
"leaves_introduced": r.leaves_introduced,
"conjecture_in_problem": r.conjecture_in_problem,
"conjecture_used": r.conjecture_used,
"conjecture_negation_checked": r.conjecture_negation_checked,
"what_was_refuted": r.what_was_refuted,
"steps_total": r.steps_total,
"steps_checked": r.steps_checked,
"steps_checked_by_rule": r.steps_checked_by_rule,
"steps_unchecked": r.steps_unchecked,
"steps_unchecked_total": r.steps_unchecked.iter().map(|u| u.count).sum::<usize>(),
"steps_not_reconstructed": r.steps_not_reconstructed,
"verdict": r.verdict,
"verdict_means": verdict_means(r.verdict),
"certificate": r.certificate,
"checked_by": if matches!(r.certificate, Some(CertificateOutcome::Certified { .. })) {
"lean/Fo via oo-resolution, whose acceptance discharges Fo.unsat_of_check (axioms propext, \
Classical.choice, Quot.sound; no sorry). The replay in src/tstp.rs ran too and is \
reported above, but the verdict rests on the theorem and not on the replay. What is \
still Rust: the TSTP parser, the translation into the certificate, and the \
leaf-match that ties the certificate's clauses to the problem this engine emitted; \
a defect in any of them can fail to produce a certificate, never make an accepted \
one unsound"
} else {
"src/tstp.rs, an UNVERIFIED Rust replayer. lean/ is not involved and no \
theorem is cited. A refutation remains an ORACLE OPINION (decision \
0005); what this adds is that the opinion is now about a derivation \
somebody can read, over the problem this engine emitted. The `certificate` field \
says why no theorem was reached"
},
})
}
// ── Driving a prover ───────────────────────────────────────────────────────
/// Which prover to run. Both read TPTP FOF and both print TSTP on request.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Prover {
Vampire,
Eprover,
}
impl Prover {
pub fn parse(s: &str) -> anyhow::Result<Prover> {
match s.to_ascii_lowercase().as_str() {
"vampire" => Ok(Prover::Vampire),
"eprover" | "e" => Ok(Prover::Eprover),
other => anyhow::bail!("unknown prover {other:?}; expected `vampire` or `eprover`"),
}
}
pub fn name(self) -> &'static str {
match self {
Prover::Vampire => "vampire",
Prover::Eprover => "eprover",
}
}
/// The argument vector, WITH the proof-printing option.
///
/// It is not optional here. A run without it returns an SZS word and no
/// derivation, which is the state this module exists to leave behind.
pub fn argv(self, file: &Path, secs: u32) -> Vec<String> {
let f = file.display().to_string();
match self {
Prover::Vampire => {
vec!["--proof".into(), "tptp".into(), "-t".into(), format!("{secs}"), f]
}
Prover::Eprover => vec![
"--auto".into(),
"--tptp3-format".into(),
"--proof-object".into(),
format!("--cpu-limit={secs}"),
f,
],
}
}
pub fn install_line(self) -> &'static str {
match self {
Prover::Vampire => "install Vampire: `brew install vampire` (macOS) or \
https://github.com/vprover/vampire",
Prover::Eprover => "install E: `brew install eprover` (macOS), \
`apt-get install eprover`, or https://github.com/eprover/eprover",
}
}
pub fn available(self) -> bool {
which(self.name()).is_some()
}
}
fn which(bin: &str) -> Option<PathBuf> {
std::env::var_os("PATH").and_then(|paths| {
std::env::split_paths(&paths).find_map(|dir| {
let p = dir.join(bin);
if p.is_file() { Some(p) } else { None }
})
})
}
/// How to run the pipeline.
#[derive(Clone, Debug)]
pub struct ProveOptions {
pub prover: Prover,
/// Seconds per prover invocation.
pub timeout_secs: u32,
}
impl Default for ProveOptions {
fn default() -> Self {
ProveOptions { prover: Prover::Vampire, timeout_secs: 30 }
}
}
fn run_prover(prover: Prover, file: &Path, out: &Path, secs: u32) -> std::io::Result<String> {
let f = std::fs::File::create(out)?;
let f2 = f.try_clone()?;
let mut cmd = Command::new(prover.name());
cmd.args(prover.argv(file, secs))
.stdout(Stdio::from(f))
.stderr(Stdio::from(f2))
.stdin(Stdio::null());
let mut child = cmd.spawn()?;
let start = Instant::now();
let limit = Duration::from_secs((secs as u64).max(1) + 15);
loop {
match child.try_wait()? {
Some(_) => break,
None => {
if start.elapsed() > limit {
let _ = child.kill();
let _ = child.wait();
break;
}
std::thread::sleep(Duration::from_millis(20));
}
}
}
std::fs::read_to_string(out)
}
/// One problem: write it, run the prover, check what comes back.
/// How the problem reached the prover, which decides whether a certificate
/// can even be attempted.
#[derive(Clone, Debug)]
pub enum ProblemForm {
/// `to_cnf` succeeded: clauses only, so the prover's derivation is
/// resolution end to end and can be translated.
Cnf,
/// `to_cnf` refused, naming the axiom; the prover got FOF and clausified.
Fof { why: String },
}
fn prove_one(
problem_text: &str,
form: &ProblemForm,
dir: &Path,
stem: &str,
opts: &ProveOptions,
) -> anyhow::Result<Report> {
std::fs::create_dir_all(dir)?;
let p = dir.join(format!("{stem}.p"));
std::fs::write(&p, problem_text)?;
let out = dir.join(format!("{stem}.tstp"));
let text = run_prover(opts.prover, &p, &out, opts.timeout_secs)?;
let mut r = check(problem_text, &text);
r.certificate = certify(&r, form, &text, dir, stem);
if matches!(r.certificate, Some(CertificateOutcome::Certified { .. })) {
r.verdict = "refutation_certified";
}
Ok(r)
}
fn find_fores() -> Option<PathBuf> {
// An explicit OO_RESOLUTION is an instruction. If it points nowhere the answer
// is "absent", not "fall back to whatever else is lying around": the same
// rule `shacl_verified::resolve_checker` applies, for the same reason. A
// test that sets it to a missing path is asking to see the absent branch.
if let Ok(p) = std::env::var("OO_RESOLUTION") {
let p = PathBuf::from(p);
return p.exists().then_some(p);
}
let built = PathBuf::from(env!("CARGO_MANIFEST_DIR")).join("lean/.lake/build/bin/oo-resolution");
if built.exists() {
return Some(built);
}
std::env::split_paths(&std::env::var_os("PATH")?).map(|d| d.join("oo-resolution")).find(|p| p.is_file())
}
/// Offer the derivation to `oo-resolution`, and say exactly what happened.
///
/// Only when the replay found a well-founded refutation whose leaves are OUR
/// formulas. A certificate over some other clause set would be a proof of
/// something, and `leaves_match_problem` is what makes it a proof of the
/// problem this engine emitted; that check is Rust, and the first addendum to
/// decision 0005 says so.
fn certify(r: &Report, form: &ProblemForm, proof_text: &str, dir: &Path, stem: &str) -> Option<CertificateOutcome> {
if !(r.root_is_false && r.leaves_match_problem && r.derivation_wellformed) {
return None;
}
if let ProblemForm::Fof { why } = form {
return Some(CertificateOutcome::OutsideClausalFragment { why: why.clone() });
}
let cert = match to_fo_certificate(proof_text) {
Ok(c) => c,
Err(e) => return Some(CertificateOutcome::CheckerRefused { exit: -1, output: e, certificate: String::new() }),
};
if !cert.untranslated.is_empty() {
return Some(CertificateOutcome::StepsUntranslated { untranslated: cert.untranslated, translated: cert.translated });
}
if !cert.reaches_false {
return Some(CertificateOutcome::DoesNotReachFalse { translated: cert.translated });
}
let path = dir.join(format!("{stem}.fo.cert"));
let _ = std::fs::write(&path, &cert.text);
let shown = path.display().to_string();
let Some(bin) = find_fores() else {
return Some(CertificateOutcome::CheckerAbsent { certificate: shown });
};
let mut cmd = Command::new(&bin);
cmd.arg(&path);
let run = match crate::verdict::CheckerRun::spawn(
&crate::verdict::CheckerBinary::found_at(bin.clone()),
cmd,
&[&path],
) {
Ok(run) => run,
Err(e) => return Some(CertificateOutcome::CheckerRefused { exit: -1, output: e.to_string(), certificate: shown }),
};
match run.accepted_naming(&["Fo.unsat_of_check"]) {
Some(tok) => Some(CertificateOutcome::Certified {
theorem: tok.theorem(),
checker: bin.display().to_string(),
steps: cert.translated,
certificate: shown,
}),
None => Some(CertificateOutcome::CheckerRefused { exit: run.exit(), output: run.output(), certificate: shown }),
}
}
/// Run the prover over the loaded ontology and, optionally, one problem per
/// goal, and check every derivation it prints.
///
/// The shape is `fol_solve::solve_export`'s, deliberately: the two are the
/// refutation half and the model half of the same question and a reader should
/// not have to learn two report formats.
pub fn prove_export(
graph: &std::sync::Arc<crate::graph::GraphStore>,
dir: &Path,
opts: &ProveOptions,
goals: Option<&Path>,
goals_skip_columns: usize,
) -> anyhow::Result<String> {
if !opts.prover.available() {
return Ok(serde_json::json!({
"prover": opts.prover.name(),
"skipped": format!(
"{} is not on PATH, so no derivation was produced and nothing was checked. \
That is the ABSENCE of a second opinion and not agreement with one. {}",
opts.prover.name(),
opts.prover.install_line()
),
})
.to_string());
}
let triples = graph.all_triples()?;
// What the file declares and types, gathered before the triples are consumed:
// the unasked check below needs them and `ReadOntology` keeps neither.
let declared = crate::tptp::declared_classes(&triples);
let types = crate::tptp::types_of(&triples);
let read = crate::tptp::read_graph(triples);
std::fs::create_dir_all(dir)?;
// CNF when the fragment allows it, FOF otherwise, and the report says
// which. A prover handed FOF clausifies before it resolves, and that
// derivation cannot be translated; handed clauses, it resolves from the
// first step and can be. Measured on one derived goal: FOF 18 steps, 13
// of them clausification, 0 translated; CNF 5 steps, 5 translated.
let render = |p: &crate::tptp::FolProblem| -> (String, ProblemForm) {
match p.to_cnf() {
Ok(t) => (t, ProblemForm::Cnf),
Err(e) => (p.to_tptp(), ProblemForm::Fof { why: e.to_string() }),
}
};
let base = crate::tptp::FolProblem::build(&read.axioms, None)?;
let (btext, bform) = render(&base);
let ontology = prove_one(&btext, &bform, &dir.join("ontology"), "ontology", opts)?;
let mut counts: BTreeMap<&'static str, usize> = BTreeMap::new();
*counts.entry(ontology.verdict).or_default() += 1;
let mut goal_reports = Vec::new();
let mut not_asked: Vec<serde_json::Value> = Vec::new();
if let Some(path) = goals {
let text = std::fs::read_to_string(path)?;
for (i, line) in text.lines().enumerate() {
if line.trim().is_empty() {
continue;
}
let cols: Vec<&str> = line.split('\t').collect();
if cols.len() < goals_skip_columns + 3 {
not_asked.push(serde_json::json!({
"line": line,
"why": format!("fewer than {} tab-separated columns", goals_skip_columns + 3),
}));
continue;
}
let (s, p, o) = (
cols[goals_skip_columns],
cols[goals_skip_columns + 1],
cols[goals_skip_columns + 2],
);
// Before the translation: a goal that puts in class position a term
// the ontology never uses as a class is returned UNASKED. The
// translator would accept it and the prover would answer, about a
// symbol no axiom constrains, and the answer would be filed as
// "not entailed" as if the file had said no.
if let Some(u) = crate::tptp::unasked(&read, &declared, &types, s, p, o) {
*counts.entry("mu").or_default() += 1;
goal_reports.push(serde_json::json!({
"triple": [s, p, o],
"report": {
"verdict": "mu",
"verdict_means": verdict_means("mu"),
"term": u.term,
"position": u.position,
"kind": u.kind,
"why": u.why,
},
}));
continue;
}
let ax = match crate::tptp::triple_as_axiom(&read, s, p, o) {
Ok(ax) => ax,
Err(why) => {
not_asked.push(serde_json::json!({"triple": [s, p, o], "why": why}));
continue;
}
};
let gp = crate::tptp::FolProblem::build(&read.axioms, Some(&ax))?;
let (gtext, gform) = render(&gp);
let rep = prove_one(
>ext,
&gform,
&dir.join(format!("goal_{i:05}")),
&format!("goal_{i:05}"),
opts,
)?;
*counts.entry(rep.verdict).or_default() += 1;
goal_reports.push(serde_json::json!({
"triple": [s, p, o],
"report": report_json(&rep),
}));
}
}
let rejected = counts.get("derivation_rejected").copied().unwrap_or(0);
let unreconstructed = counts.get("refutation_step_not_reconstructed").copied().unwrap_or(0);
let certified = counts.get("refutation_certified").copied().unwrap_or(0);
let unasked = counts.get("mu").copied().unwrap_or(0);
Ok(serde_json::json!({
"prover": opts.prover.name(),
"timeout_secs": opts.timeout_secs,
"dir": dir.display().to_string(),
"ontology": report_json(&ontology),
"goals": goal_reports,
"not_asked": not_asked,
"not_asked_means": "no axiom form in OwlLean/Syntax.lean corresponds to the triple, so \
the question could not be put at all. Listed rather than skipped, \
so a run cannot report a clean sweep over a subset nobody chose",
"verdict_counts": counts,
"stop_the_line": rejected + unreconstructed,
"stop_the_line_means": "a derivation was REJECTED (a dangling parent, a cycle, or a \
leaf that is not a formula of the problem this engine emitted), \
or a step whose rule this checker implements did not \
reconstruct. The first means the prover refuted something other \
than what it was given; the second is either a defect in the \
derivation or a gap in this checker and needs a human. The \
command exits non-zero on either",
"problem_form": match &bform { ProblemForm::Cnf => "cnf", ProblemForm::Fof { .. } => "fof" },
"unasked": unasked,
"unasked_means": "goals returned with the verdict `mu`: each puts in class position a term \
this ontology never uses as a class (undeclared, or only ever an individual, \
or typed skos:Concept and nothing more). No prover was asked, because its \
answer would have been about a symbol no axiom mentions and would have been \
filed as `not entailed` as if the file had said no. The report names the \
term, its position and what the file does call it",
"certified": certified,
"certified_means": if certified > 0 {
"this many refutations were CHECKED BY A THEOREM: translated into lean/Fo's \
certificate format and accepted by oo-resolution (Fo.unsat_of_check). Every other \
refutation in this run is an oracle opinion and its `certificate` field says why"
} else {
"NOTHING HERE IS CERTIFIED. A refutation is an ORACLE OPINION (decision 0005) \
unless it was exported in the clausal fragment, every step translated, and \
oo-resolution exited 0. None did; each report's `certificate` field says which of \
those failed. The MODEL direction is the other one that can be certified; see \
decision 0006 and onto_fol_model"
},
})
.to_string())
}
/// Check a problem file and a recorded prover output, with no store and no
/// prover run. This is what `tools/fol_differential.py` calls once it already
/// has both.
pub fn check_files(problem: &Path, proof: &Path) -> anyhow::Result<String> {
let p = std::fs::read_to_string(problem)
.map_err(|e| anyhow::anyhow!("cannot read problem {}: {e}", problem.display()))?;
let d = std::fs::read_to_string(proof)
.map_err(|e| anyhow::anyhow!("cannot read proof {}: {e}", proof.display()))?;
let r = check(&p, &d);
let mut v = report_json(&r);
if let Some(o) = v.as_object_mut() {
o.insert("problem".into(), serde_json::json!(problem.display().to_string()));
o.insert("proof".into(), serde_json::json!(proof.display().to_string()));
o.insert(
"stop_the_line".into(),
serde_json::json!(usize::from(matches!(
r.verdict,
"derivation_rejected" | "refutation_step_not_reconstructed"
))),
);
}
Ok(v.to_string())
}