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
//! Certifying UNSATISFIABILITY, the half `src/tableaux.rs` could not certify.
//!
//! `ModelOutcome` hands over a finite interpretation when the answer is yes.
//! That works because a model is a finite object and checking it is evaluation.
//! The negative answer has no such object. "This ontology has no model" is a
//! claim about every interpretation, including the infinite ones SHIQ forces,
//! so nothing finite can be exhibited and nothing can be evaluated. What can be
//! exhibited is a DERIVATION: a closed tableau, whose every leaf is a branch no
//! interpretation satisfies and whose every step preserves satisfiability
//! downward. `lean/Dl/Tableau.lean` proves that; `lean/Dl/Refute.lean` checks
//! one; this writes one.
//!
//! # Why this is a second prover rather than instrumentation
//!
//! The obvious move is to record what `Tableau::expand` did and print it. That
//! would be wrong, and not only awkward. The fast reasoner uses blocking,
//! merging, inverse propagation and absorbed GCIs. Blocking and merging are
//! COMPLETENESS devices: they exist so that a search for a model terminates.
//! A refutation needs none of them, and the certified calculus deliberately has
//! neither, so most of what the fast engine records could not be written down
//! here anyway.
//!
//! So this is a small independent search over the certified rules only. It is
//! slower and weaker than `Tableau`, and that is the correct trade: if it finds
//! a refutation, the refutation is checkable; if it does not, `Tableau`'s answer
//! stands exactly as it did before, as testimony. Nothing about this module can
//! make a wrong answer look right, because it does not decide anything. The
//! Lean checker does, from the bytes.
//!
//! # What it cannot do
//!
//! Transitive, symmetric, inverse and inverse-functional roles have no rules in
//! the certified calculus, so an ontology inconsistent only through one of
//! those gets no certificate. The emitter says so rather than guessing.
use crate::tableaux::{axiom_line, name_is_safe, Concept, DlAxiom, Interner};
use std::collections::HashSet;
use std::path::Path;
// ── The Lean-side concept shape ─────────────────────────────────────────
/// A concept as `lean/Dl/Syntax.lean` spells it.
///
/// Not the same type as [`Concept`]. The reasoner's concepts are in negation
/// normal form with n-ary conjunction and disjunction; Lean's have an arbitrary
/// negation and binary connectives. The difference matters because the rules
/// fire on the Lean shape: applying the ∧-rule to `And([c, d, e])` gives two
/// conclusions in Lean, `c` and `and d e`, not three.
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub(crate) enum Lc {
Top,
Bot,
Atom(u32),
Neg(Box<Lc>),
And(Box<Lc>, Box<Lc>),
Or(Box<Lc>, Box<Lc>),
Ex(u32, Box<Lc>),
All(u32, Box<Lc>),
/// `≥n R.C`, written `(n, role, filler)`.
Min(u32, u32, Box<Lc>),
/// `≤n R.C`.
Max(u32, u32, Box<Lc>),
}
/// Fold an n-ary list the way `write_nary` in `src/tableaux.rs` does, which is
/// right-associatively with the connective's unit for the empty list.
///
/// This MUST agree with that function, because the certificate cites concepts
/// that have to be equal, as terms, to the ones in `axioms.tsv`. The agreement
/// is not asserted: `lowering_agrees_with_the_axiom_writer` below renders both
/// ways and compares the strings.
fn lower_nary(cs: &[Concept], and: bool) -> Lc {
match cs.split_first() {
None => {
if and {
Lc::Top
} else {
Lc::Bot
}
}
Some((head, [])) => lower(head),
Some((head, rest)) => {
let (h, t) = (Box::new(lower(head)), Box::new(lower_nary(rest, and)));
if and {
Lc::And(h, t)
} else {
Lc::Or(h, t)
}
}
}
}
pub(crate) fn lower(c: &Concept) -> Lc {
match c {
Concept::Top => Lc::Top,
Concept::Bottom => Lc::Bot,
Concept::Atom(a) => Lc::Atom(*a),
Concept::NegAtom(a) => Lc::Neg(Box::new(Lc::Atom(*a))),
Concept::And(cs) => lower_nary(cs, true),
Concept::Or(cs) => lower_nary(cs, false),
Concept::Exists(r, f) => Lc::Ex(*r, Box::new(lower(f))),
Concept::ForAll(r, f) => Lc::All(*r, Box::new(lower(f))),
Concept::MinCard(r, n, f) => Lc::Min(*n, *r, Box::new(lower(f))),
Concept::MaxCard(r, n, f) => Lc::Max(*n, *r, Box::new(lower(f))),
}
}
/// The one place a name reaches the certificate, and therefore the one place the
/// round-trip guard has to be. Same discipline as the model emitter's
/// `push_name`, and for the same reason: the grammar is space-separated, so a
/// name carrying a space would be read back as two tokens.
fn push_name(out: &mut String, it: &Interner, id: u32, bad: &mut Option<String>) {
let s = it.resolve(id);
if !name_is_safe(s) && bad.is_none() {
*bad = Some(s.to_string());
}
out.push_str(s);
}
fn write_lc(out: &mut String, it: &Interner, c: &Lc, bad: &mut Option<String>) {
match c {
Lc::Top => out.push_str("top"),
Lc::Bot => out.push_str("bot"),
Lc::Atom(a) => {
out.push_str("atom ");
push_name(out, it, *a, bad);
}
Lc::Neg(f) => {
out.push_str("not ");
write_lc(out, it, f, bad);
}
Lc::And(f, g) => {
out.push_str("and ");
write_lc(out, it, f, bad);
out.push(' ');
write_lc(out, it, g, bad);
}
Lc::Or(f, g) => {
out.push_str("or ");
write_lc(out, it, f, bad);
out.push(' ');
write_lc(out, it, g, bad);
}
Lc::Ex(r, f) => {
out.push_str("some ");
push_name(out, it, *r, bad);
out.push(' ');
write_lc(out, it, f, bad);
}
Lc::All(r, f) => {
out.push_str("all ");
push_name(out, it, *r, bad);
out.push(' ');
write_lc(out, it, f, bad);
}
Lc::Min(n, r, f) => {
out.push_str("min ");
out.push_str(&n.to_string());
out.push(' ');
push_name(out, it, *r, bad);
out.push(' ');
write_lc(out, it, f, bad);
}
Lc::Max(n, r, f) => {
out.push_str("max ");
out.push_str(&n.to_string());
out.push(' ');
push_name(out, it, *r, bad);
out.push(' ');
write_lc(out, it, f, bad);
}
}
}
// ── Branches ────────────────────────────────────────────────────────────
/// One entry on a tableau branch, mirroring `Dl.Constraint`.
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
enum C {
Conc(u32, Lc),
Role(u32, u32, u32),
Diff(u32, u32),
}
/// A branch, kept as a set for membership and as a vector for order.
///
/// `fired` records which generating rule applications have already happened, so
/// the ∃ and ≥ rules cannot invent witnesses for the same constraint forever.
/// That is the only thing standing between this search and an infinite one, and
/// it is why this prover is incomplete rather than non-terminating: a genuine
/// SHIQ model can need an infinite chain, and refusing to build one costs
/// nothing here because a refutation never needs it.
#[derive(Clone, Default)]
struct Branch {
set: HashSet<C>,
conc_of: HashSet<u32>,
fired: HashSet<(u32, Lc)>,
fired_ne: HashSet<usize>,
}
impl Branch {
fn has(&self, c: &C) -> bool {
self.set.contains(c)
}
fn add(&mut self, c: C) -> bool {
if let C::Conc(x, _) = &c {
self.conc_of.insert(*x);
}
self.set.insert(c)
}
fn has_conc(&self, x: u32) -> bool {
self.conc_of.contains(&x)
}
fn concepts(&self) -> Vec<(u32, Lc)> {
let mut v: Vec<(u32, Lc)> = self
.set
.iter()
.filter_map(|c| match c {
C::Conc(x, f) => Some((*x, f.clone())),
_ => None,
})
.collect();
v.sort_by_key(|(x, f)| (*x, format!("{f:?}")));
v
}
fn edges(&self) -> Vec<(u32, u32, u32)> {
let mut v: Vec<(u32, u32, u32)> = self
.set
.iter()
.filter_map(|c| match c {
C::Role(r, x, y) => Some((*r, *x, *y)),
_ => None,
})
.collect();
v.sort_unstable();
v
}
}
// ── The certificate tree ────────────────────────────────────────────────
/// A step of a closed tableau, mirroring `Dl.Cert` constructor for constructor.
enum Step {
Bot(u32),
NegC(u32, Lc),
DisjC(u32, Lc, Lc),
DiffC(u32),
MinMax(u32, u32, Lc, u32, u32),
MaxC(u32, u32, Lc, u32, Vec<u32>),
Inst(u32, Lc, Box<Step>),
Rel(u32, u32, u32, Box<Step>),
Sub(u32, Lc, Lc, Box<Step>),
Dom(u32, u32, u32, Lc, Box<Step>),
Rng(u32, u32, u32, Lc, Box<Step>),
SubRole(u32, u32, u32, u32, Box<Step>),
NonEmpty(u32, Lc, Box<Step>),
AndS(u32, Lc, Lc, Box<Step>),
AllS(u32, u32, u32, Lc, Box<Step>),
ExS(u32, u32, u32, Lc, Box<Step>),
MinS(u32, u32, Lc, u32, Vec<u32>, Box<Step>),
OrS(u32, Lc, Lc, Box<Step>, Box<Step>),
}
fn count(s: &Step) -> usize {
match s {
Step::Bot(..)
| Step::NegC(..)
| Step::DisjC(..)
| Step::DiffC(..)
| Step::MinMax(..)
| Step::MaxC(..) => 1,
Step::Inst(_, _, k)
| Step::Rel(_, _, _, k)
| Step::Sub(_, _, _, k)
| Step::Dom(_, _, _, _, k)
| Step::Rng(_, _, _, _, k)
| Step::SubRole(_, _, _, _, k)
| Step::NonEmpty(_, _, k)
| Step::AndS(_, _, _, k)
| Step::AllS(_, _, _, _, k)
| Step::ExS(_, _, _, _, k)
| Step::MinS(_, _, _, _, _, k) => 1 + count(k),
Step::OrS(_, _, _, l, r) => 1 + count(l) + count(r),
}
}
/// Render the tree in the prefix order `Dl.Parse.cert?` reads.
///
/// Indentation is for a human only. Newlines are not significant in the format,
/// because the arities carry the tree shape, so nothing here can become
/// load-bearing by accident.
fn write_step(out: &mut String, it: &Interner, s: &Step, ind: usize, bad: &mut Option<String>) {
let pad = " ".repeat(ind);
let kid = |out: &mut String, k: &Step, bad: &mut Option<String>| {
out.push('\n');
write_step(out, it, k, ind + 1, bad);
};
let n = |out: &mut String, id: u32, bad: &mut Option<String>| {
push_name(out, it, id, bad);
};
out.push_str(&pad);
match s {
Step::Bot(x) => {
out.push_str("bot ");
n(out, *x, bad);
}
Step::DiffC(x) => {
out.push_str("diff ");
n(out, *x, bad);
}
Step::NegC(x, c) => {
out.push_str("neg ");
n(out, *x, bad);
out.push(' ');
write_lc(out, it, c, bad);
}
Step::DisjC(x, c, d) => {
out.push_str("disjoint ");
n(out, *x, bad);
out.push(' ');
write_lc(out, it, c, bad);
out.push(' ');
write_lc(out, it, d, bad);
}
Step::MinMax(x, r, c, m, k) => {
out.push_str("minmax ");
n(out, *x, bad);
out.push(' ');
n(out, *r, bad);
out.push_str(&format!(" {m} {k} "));
write_lc(out, it, c, bad);
}
Step::MaxC(x, r, c, k, ys) => {
out.push_str("maxclash ");
n(out, *x, bad);
out.push(' ');
n(out, *r, bad);
out.push_str(&format!(" {k} {} ", ys.len()));
for y in ys {
n(out, *y, bad);
out.push(' ');
}
write_lc(out, it, c, bad);
}
Step::Inst(a, c, k) => {
out.push_str("inst ");
n(out, *a, bad);
out.push(' ');
write_lc(out, it, c, bad);
kid(out, k, bad);
}
Step::Rel(a, r, b, k) => {
out.push_str("rel ");
n(out, *a, bad);
out.push(' ');
n(out, *r, bad);
out.push(' ');
n(out, *b, bad);
kid(out, k, bad);
}
Step::Sub(x, c, d, k) => {
out.push_str("sub ");
n(out, *x, bad);
out.push(' ');
write_lc(out, it, c, bad);
out.push(' ');
write_lc(out, it, d, bad);
kid(out, k, bad);
}
Step::Dom(x, y, r, c, k) => {
out.push_str("domain ");
n(out, *x, bad);
out.push(' ');
n(out, *y, bad);
out.push(' ');
n(out, *r, bad);
out.push(' ');
write_lc(out, it, c, bad);
kid(out, k, bad);
}
Step::Rng(x, y, r, c, k) => {
out.push_str("range ");
n(out, *x, bad);
out.push(' ');
n(out, *y, bad);
out.push(' ');
n(out, *r, bad);
out.push(' ');
write_lc(out, it, c, bad);
kid(out, k, bad);
}
Step::SubRole(x, y, r, t, k) => {
out.push_str("subrole ");
n(out, *x, bad);
out.push(' ');
n(out, *y, bad);
out.push(' ');
n(out, *r, bad);
out.push(' ');
n(out, *t, bad);
kid(out, k, bad);
}
Step::NonEmpty(y, c, k) => {
out.push_str("nonempty ");
n(out, *y, bad);
out.push(' ');
write_lc(out, it, c, bad);
kid(out, k, bad);
}
Step::AndS(x, c, d, k) => {
out.push_str("and ");
n(out, *x, bad);
out.push(' ');
write_lc(out, it, c, bad);
out.push(' ');
write_lc(out, it, d, bad);
kid(out, k, bad);
}
Step::AllS(x, y, r, c, k) => {
out.push_str("all ");
n(out, *x, bad);
out.push(' ');
n(out, *y, bad);
out.push(' ');
n(out, *r, bad);
out.push(' ');
write_lc(out, it, c, bad);
kid(out, k, bad);
}
Step::ExS(x, y, r, c, k) => {
out.push_str("some ");
n(out, *x, bad);
out.push(' ');
n(out, *y, bad);
out.push(' ');
n(out, *r, bad);
out.push(' ');
write_lc(out, it, c, bad);
kid(out, k, bad);
}
Step::MinS(x, r, c, k, ys, next) => {
out.push_str("min ");
n(out, *x, bad);
out.push(' ');
n(out, *r, bad);
out.push_str(&format!(" {k} {} ", ys.len()));
for y in ys {
n(out, *y, bad);
out.push(' ');
}
write_lc(out, it, c, bad);
kid(out, next, bad);
}
Step::OrS(x, c, d, l, r) => {
out.push_str("or ");
n(out, *x, bad);
out.push(' ');
write_lc(out, it, c, bad);
out.push(' ');
write_lc(out, it, d, bad);
kid(out, l, bad);
kid(out, r, bad);
}
}
}
// ── The axioms, in the shape the rules read them ────────────────────────
/// The axioms the certified calculus has rules for. Everything else is dropped
/// here and named in [`RefuteOutcome::NotFound`] if the search fails, so a
/// reader can tell "no refutation exists" from "no refutation this calculus can
/// write".
struct Rules {
subs: Vec<(Lc, Lc)>,
disjoints: Vec<(Lc, Lc)>,
domains: Vec<(u32, Lc)>,
ranges: Vec<(u32, Lc)>,
subroles: Vec<(u32, u32)>,
insts: Vec<(u32, Lc)>,
rels: Vec<(u32, u32, u32)>,
indivs: HashSet<u32>,
nonempties: Vec<Lc>,
/// Role names the axiom set mentions, which is what `roleNames A` is in
/// Lean and what several rules need to put a target in the carrier.
roles: HashSet<u32>,
/// Individual names the axiom set mentions. Invented witnesses must avoid
/// these, or the assignment the soundness proof builds would disagree with
/// `I.ind` and the rule would be unsound.
inds: HashSet<u32>,
/// Axiom kinds present in the ontology that this calculus cannot use.
unsupported: Vec<&'static str>,
}
fn concept_roles(c: &Concept, out: &mut HashSet<u32>) {
match c {
Concept::Top | Concept::Bottom | Concept::Atom(_) | Concept::NegAtom(_) => {}
Concept::And(cs) | Concept::Or(cs) => cs.iter().for_each(|d| concept_roles(d, out)),
Concept::Exists(r, f) | Concept::ForAll(r, f) => {
out.insert(*r);
concept_roles(f, out);
}
Concept::MinCard(r, _, f) | Concept::MaxCard(r, _, f) => {
out.insert(*r);
concept_roles(f, out);
}
}
}
impl Rules {
fn new(axioms: &[DlAxiom]) -> Rules {
let mut r = Rules {
subs: vec![],
disjoints: vec![],
domains: vec![],
ranges: vec![],
subroles: vec![],
insts: vec![],
rels: vec![],
indivs: HashSet::new(),
nonempties: vec![],
roles: HashSet::new(),
inds: HashSet::new(),
unsupported: vec![],
};
let note = |r: &mut Rules, k: &'static str| {
if !r.unsupported.contains(&k) {
r.unsupported.push(k);
}
};
for a in axioms {
// `roleNames` and `indNames` in `lean/Dl/Syntax.lean`, clause for
// clause. They are computed from EVERY axiom, including the ones
// this calculus has no rule for, because that is what the Lean side
// computes and the two have to agree.
match a {
DlAxiom::Sub(c, d) | DlAxiom::Disjoint(c, d) => {
concept_roles(c, &mut r.roles);
concept_roles(d, &mut r.roles);
}
DlAxiom::Domain(role, c) | DlAxiom::Range(role, c) => {
r.roles.insert(*role);
concept_roles(c, &mut r.roles);
}
DlAxiom::Inst(i, c) => {
r.inds.insert(*i);
concept_roles(c, &mut r.roles);
}
DlAxiom::NonEmpty(c) => concept_roles(c, &mut r.roles),
DlAxiom::SubRole(a1, b1) | DlAxiom::Inv(a1, b1) => {
r.roles.insert(*a1);
r.roles.insert(*b1);
}
DlAxiom::Trans(role) | DlAxiom::Sym(role) | DlAxiom::InvFunc(role) => {
r.roles.insert(*role);
}
DlAxiom::Rel(a1, role, b1) => {
r.roles.insert(*role);
r.inds.insert(*a1);
r.inds.insert(*b1);
}
DlAxiom::Indiv(i) => {
r.inds.insert(*i);
}
}
match a {
DlAxiom::Sub(c, d) => r.subs.push((lower(c), lower(d))),
DlAxiom::Disjoint(c, d) => r.disjoints.push((lower(c), lower(d))),
DlAxiom::Domain(role, c) => r.domains.push((*role, lower(c))),
DlAxiom::Range(role, c) => r.ranges.push((*role, lower(c))),
DlAxiom::SubRole(a1, b1) => r.subroles.push((*a1, *b1)),
DlAxiom::Inst(i, c) => r.insts.push((*i, lower(c))),
DlAxiom::Rel(a1, role, b1) => r.rels.push((*a1, *role, *b1)),
DlAxiom::Indiv(i) => {
r.indivs.insert(*i);
}
DlAxiom::NonEmpty(c) => r.nonempties.push(lower(c)),
DlAxiom::Trans(_) => note(&mut r, "trans"),
DlAxiom::Sym(_) => note(&mut r, "sym"),
DlAxiom::Inv(..) => note(&mut r, "inv"),
DlAxiom::InvFunc(_) => note(&mut r, "invfunc"),
}
}
r
}
}
// ── The search ──────────────────────────────────────────────────────────
struct Prover<'a> {
rules: &'a Rules,
/// Fresh names, interned as they are invented. Checked against `inds`
/// rather than assumed distinct from it.
fresh: Vec<u32>,
next_fresh: usize,
budget: usize,
}
impl<'a> Prover<'a> {
/// A name no axiom mentions. The Lean rules require exactly that, on top of
/// the name being new to the branch.
fn fresh_name(&mut self, it: &mut Interner) -> Option<u32> {
for k in 0..64 {
let id = it.intern(&format!("_oo_w{}_{}", self.next_fresh, k));
if !self.rules.inds.contains(&id) && !self.fresh.contains(&id) {
self.next_fresh += 1;
self.fresh.push(id);
return Some(id);
}
}
None
}
fn spend(&mut self) -> bool {
if self.budget == 0 {
return false;
}
self.budget -= 1;
true
}
/// A clash on this branch, if there is one.
fn clash(&self, br: &Branch) -> Option<Step> {
for (x, c) in br.concepts() {
if c == Lc::Bot {
return Some(Step::Bot(x));
}
if br.has(&C::Conc(x, Lc::Neg(Box::new(c.clone())))) {
return Some(Step::NegC(x, c));
}
if br.has(&C::Diff(x, x)) {
return Some(Step::DiffC(x));
}
if let Lc::Min(m, r, f) = &c {
for (y, d) in br.concepts() {
if y != x {
continue;
}
if let Lc::Max(n, r2, g) = &d
&& r == r2
&& f == g
&& n < m
{
return Some(Step::MinMax(x, *r, (**f).clone(), *m, *n));
}
}
}
}
for (c, d) in &self.rules.disjoints {
for (x, f) in br.concepts() {
if &f == c && br.has(&C::Conc(x, d.clone())) {
return Some(Step::DisjC(x, c.clone(), d.clone()));
}
}
}
// The cardinality clash: more pairwise-distinct successors in the filler
// than the bound allows. The witnesses have to be distinct ON THE
// BRANCH, which is what the ≥ rule's inequalities are for.
for (x, c) in br.concepts() {
let Lc::Max(n, r, f) = &c else { continue };
let mut ys: Vec<u32> = br
.edges()
.into_iter()
.filter(|(rr, xx, _)| rr == r && *xx == x)
.map(|(_, _, y)| y)
.filter(|y| br.has(&C::Conc(*y, (**f).clone())))
.collect();
ys.sort_unstable();
ys.dedup();
let mut picked: Vec<u32> = vec![];
for y in ys {
if picked
.iter()
.all(|&p| br.has(&C::Diff(p, y)) && br.has(&C::Diff(y, p)))
{
picked.push(y);
}
if picked.len() == *n as usize + 1 {
return Some(Step::MaxC(x, *r, (**f).clone(), *n, picked));
}
}
}
None
}
/// The first rule that adds something the branch does not already carry.
/// Every one of these strictly grows the branch, which is what keeps the
/// deterministic phase finite.
#[allow(clippy::type_complexity)]
fn det(&self, br: &Branch) -> Option<(Branch, Box<dyn Fn(Box<Step>) -> Step>)> {
// Conjunction first: it is the cheapest and it feeds everything else.
for (x, c) in br.concepts() {
if let Lc::And(f, g) = &c {
let (a, b) = (C::Conc(x, (**f).clone()), C::Conc(x, (**g).clone()));
if !br.has(&a) || !br.has(&b) {
let mut nb = br.clone();
nb.add(a);
nb.add(b);
let (fc, gc) = ((**f).clone(), (**g).clone());
return Some((nb, Box::new(move |k| Step::AndS(x, fc.clone(), gc.clone(), k))));
}
}
}
for (a, c) in &self.rules.insts {
if !self.rules.indivs.contains(a) {
continue;
}
let goal = C::Conc(*a, c.clone());
if !br.has(&goal) {
let mut nb = br.clone();
nb.add(goal);
let (aa, cc) = (*a, c.clone());
return Some((nb, Box::new(move |k| Step::Inst(aa, cc.clone(), k))));
}
}
for (a, r, b) in &self.rules.rels {
let goal = C::Role(*r, *a, *b);
if !br.has(&goal) {
let mut nb = br.clone();
nb.add(goal);
let (aa, rr, bb) = (*a, *r, *b);
return Some((nb, Box::new(move |k| Step::Rel(aa, rr, bb, k))));
}
}
for (c, d) in &self.rules.subs {
for (x, f) in br.concepts() {
if &f != c {
continue;
}
let goal = C::Conc(x, d.clone());
if !br.has(&goal) {
let mut nb = br.clone();
nb.add(goal);
let (cc, dd) = (c.clone(), d.clone());
return Some((nb, Box::new(move |k| Step::Sub(x, cc.clone(), dd.clone(), k))));
}
}
}
for (r, x, y) in br.edges() {
for (role, c) in &self.rules.domains {
if *role != r || !br.has_conc(x) {
continue;
}
let goal = C::Conc(x, c.clone());
if !br.has(&goal) {
let mut nb = br.clone();
nb.add(goal);
let cc = c.clone();
return Some((nb, Box::new(move |k| Step::Dom(x, y, r, cc.clone(), k))));
}
}
for (role, c) in &self.rules.ranges {
if *role != r || !br.has_conc(x) || !self.rules.roles.contains(&r) {
continue;
}
let goal = C::Conc(y, c.clone());
if !br.has(&goal) {
let mut nb = br.clone();
nb.add(goal);
let cc = c.clone();
return Some((nb, Box::new(move |k| Step::Rng(x, y, r, cc.clone(), k))));
}
}
for (role, t) in &self.rules.subroles {
if *role != r || !br.has_conc(x) {
continue;
}
let goal = C::Role(*t, x, y);
if !br.has(&goal) {
let mut nb = br.clone();
nb.add(goal);
let tt = *t;
return Some((nb, Box::new(move |k| Step::SubRole(x, y, r, tt, k))));
}
}
}
for (x, c) in br.concepts() {
let Lc::All(r, f) = &c else { continue };
if !self.rules.roles.contains(r) {
continue;
}
for (rr, xx, y) in br.edges() {
if rr != *r || xx != x {
continue;
}
let goal = C::Conc(y, (**f).clone());
if !br.has(&goal) {
let mut nb = br.clone();
nb.add(goal);
let (rrr, ff) = (*r, (**f).clone());
return Some((nb, Box::new(move |k| Step::AllS(x, y, rrr, ff.clone(), k))));
}
}
}
None
}
fn close(&mut self, br: &Branch, it: &mut Interner) -> Option<Step> {
if !self.spend() {
return None;
}
if let Some(leaf) = self.clash(br) {
return Some(leaf);
}
if let Some((nb, wrap)) = self.det(br) {
return self.close(&nb, it).map(|k| wrap(Box::new(k)));
}
// Non-emptiness: the only rule that fires on an empty branch, so without
// it a pure TBox question never starts. Once per axiom.
for (i, c) in self.rules.nonempties.iter().enumerate() {
if br.fired_ne.contains(&i) {
continue;
}
let y = self.fresh_name(it)?;
let mut nb = br.clone();
nb.fired_ne.insert(i);
nb.add(C::Conc(y, c.clone()));
let cc = c.clone();
return self
.close(&nb, it)
.map(|k| Step::NonEmpty(y, cc, Box::new(k)));
}
// Disjunction. Both children must close, which is the only reason a
// tableau is a tree rather than a list.
for (x, c) in br.concepts() {
let Lc::Or(f, g) = &c else { continue };
let mut lb = br.clone();
lb.add(C::Conc(x, (**f).clone()));
let mut rb = br.clone();
rb.add(C::Conc(x, (**g).clone()));
let l = self.close(&lb, it)?;
let r = self.close(&rb, it)?;
return Some(Step::OrS(
x,
(**f).clone(),
(**g).clone(),
Box::new(l),
Box::new(r),
));
}
// Generating rules last, and once per constraint.
for (x, c) in br.concepts() {
if br.fired.contains(&(x, c.clone())) {
continue;
}
match &c {
Lc::Ex(r, f) => {
if !self.rules.roles.contains(r) {
continue;
}
let y = self.fresh_name(it)?;
let mut nb = br.clone();
nb.fired.insert((x, c.clone()));
nb.add(C::Role(*r, x, y));
nb.add(C::Conc(y, (**f).clone()));
let (rr, ff) = (*r, (**f).clone());
return self
.close(&nb, it)
.map(|k| Step::ExS(x, y, rr, ff, Box::new(k)));
}
Lc::Min(n, r, f) => {
if !self.rules.roles.contains(r) {
continue;
}
let mut ys = vec![];
for _ in 0..*n {
let y = self.fresh_name(it)?;
ys.push(y);
}
let mut nb = br.clone();
nb.fired.insert((x, c.clone()));
for &y in &ys {
nb.add(C::Role(*r, x, y));
nb.add(C::Conc(y, (**f).clone()));
}
for &a in &ys {
for &b in &ys {
if a != b {
nb.add(C::Diff(a, b));
}
}
}
let (rr, ff, nn, yy) = (*r, (**f).clone(), *n, ys.clone());
return self
.close(&nb, it)
.map(|k| Step::MinS(x, rr, ff, nn, yy, Box::new(k)));
}
_ => {}
}
}
None
}
}
// ── The public face ─────────────────────────────────────────────────────
/// What [`certify_unsatisfiable`] did.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum RefuteOutcome {
/// `axioms.tsv` and `refutation.cert` were written. `oo-dlrefute` is what
/// turns that into a verified statement; this layer only claims to have
/// written a tree it believes closes.
Certified { axioms: usize, steps: usize },
/// The search found no closed tableau within the budget. This is NOT a
/// claim that the ontology is consistent, and the string says what the
/// calculus could not use.
NotFound(String),
/// A certificate could not be written even though a tree was found, because
/// a name would not survive the round trip.
Refused(String),
}
impl RefuteOutcome {
pub fn is_certified(&self) -> bool {
matches!(self, RefuteOutcome::Certified { .. })
}
pub fn describe(&self) -> String {
match self {
RefuteOutcome::Certified { axioms, steps } => {
format!("certified: {axioms} axioms refuted in {steps} steps")
}
RefuteOutcome::NotFound(why) => format!("no certificate: {why}"),
RefuteOutcome::Refused(why) => format!("no certificate: {why}"),
}
}
}
/// The default search budget, in rule applications.
pub const DEFAULT_BUDGET: usize = 20_000;
/// Look for a closed tableau over `axioms`, and write it if one is found.
///
/// Writes two files into `dir`: `axioms.tsv`, which is the same transcription
/// the model certificate uses, and `refutation.cert`. Check them with
/// `oo-dlrefute AXIOMS.tsv REFUTATION.cert`.
pub(crate) fn certify_unsatisfiable(
axioms: &[DlAxiom],
interner: &mut Interner,
dir: &Path,
budget: usize,
) -> anyhow::Result<RefuteOutcome> {
let rules = Rules::new(axioms);
let mut prover = Prover {
rules: &rules,
fresh: vec![],
next_fresh: 0,
budget,
};
let start = Branch::default();
let Some(tree) = prover.close(&start, interner) else {
let mut why = format!("no closed tableau within {budget} steps");
if !rules.unsupported.is_empty() {
why.push_str(&format!(
"; the calculus has no rules for {} and dropped {} axiom kind(s), \
so an inconsistency that needs one of those cannot be written here",
rules.unsupported.join(", "),
rules.unsupported.len()
));
}
return Ok(RefuteOutcome::NotFound(why));
};
// Same discipline as the model emitter: build the text first and let
// `push_name` record the first refusal, so the coverage question cannot
// arise from two loops disagreeing about which names were checked.
let mut bad: Option<String> = None;
let mut axiom_text = String::new();
for a in axioms {
axiom_text.push_str(&axiom_line(interner, a, &mut bad));
axiom_text.push('\n');
}
let mut cert_text = String::new();
write_step(&mut cert_text, interner, &tree, 0, &mut bad);
cert_text.push('\n');
if let Some(name) = bad {
return Ok(RefuteOutcome::Refused(format!(
"the name {name:?} carries a space, a tab, a newline or nothing at all, \
so it would not survive the round trip through the certificate"
)));
}
std::fs::create_dir_all(dir)?;
std::fs::write(dir.join("axioms.tsv"), axiom_text)?;
std::fs::write(dir.join("refutation.cert"), cert_text)?;
Ok(RefuteOutcome::Certified {
axioms: axioms.len(),
steps: count(&tree),
})
}