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
//! SHIQ Tableaux Reasoner with Agent-Based Classification
//!
//! A native Rust implementation of a tableaux decision procedure for
//! the SHIQ Description Logic: ALC extended with transitive roles, role
//! hierarchies, inverse roles and qualified number restrictions. Nominals are
//! not implemented, so this is a strict fragment of OWL 2 DL. `owl:oneOf` is
//! not parsed, `owl:hasValue` is approximated as an atomic concept named after
//! the individual, and datatype ranges are skipped.
//!
//! ## Description Logic Coverage
//!
//! | DL | OWL Construct | Status |
//! |--------|----------------------------|--------|
//! | ¬A | complementOf | ✅ |
//! | C ⊓ D | intersectionOf | ✅ |
//! | C ⊔ D | unionOf | ✅ |
//! | ∃R.C | someValuesFrom | ✅ |
//! | ∀R.C | allValuesFrom | ✅ |
//! | ≥n R.C | minQualifiedCardinality | ✅ |
//! | ≤n R.C | maxQualifiedCardinality | ✅ |
//! | R ⊑ S | subPropertyOf | ✅ |
//! | Trans | TransitiveProperty | ✅ |
//! | R⁻ | inverseOf | ✅ |
//! | Sym | SymmetricProperty | ✅ |
//! | Fun | FunctionalProperty | ✅ |
//! | InvFun | InverseFunctionalProperty | ✅ |
//! | ABox | NamedIndividual | ✅ |
//! | | AsymmetricProperty | ❌ |
//! | | ReflexiveProperty | ❌ |
//! | | IrreflexiveProperty | ❌ |
//!
//! The ❌ rows are constraints on an EDGE or a pair of edges rather than on a
//! node's concept membership, and SHIQ without nominals has no label that says
//! them. They are reported by `DlReasoner::unmodelled_constructs`, which is how
//! a reader learns that an answer did not take them into account. That reporting
//! is the whole point: `owl:AsymmetricProperty` used to be in neither column, so
//! an ontology using it got a clean verdict and no warning.
//!
//! A ✅ in this table is a claim about behaviour and has been wrong. `Fun` and
//! `InvFun` carried one for a long time while the rule that enforces them could
//! not fire: functionality is encoded as `≤1 R.⊤`, `add_label` refuses to store
//! `⊤`, and the ≤-rule counted successors by testing whether the label set
//! contains the filler, which for `⊤` is false on every node. Both now go
//! through the `MaxCard` path with `Top` special-cased at the counting step, and
//! `tests/tableaux_role_characteristics_test.rs` pins the negative — an
//! inconsistent ontology that used to come back consistent — rather than only a
//! positive.
//!
//! ## Architecture
//!
//! Uses agent-based decomposition for classification:
//! - **Satisfiability Agent**: Parallel sat testing via rayon worker pool
//! - **Subsumption Agent**: Parallel pairwise subsumption with told-subsumer pruning
//! - **Explanation Agent**: Clash tracing and justification extraction
//! - **ABox Agent**: Individual consistency checking and type inference
use std::collections::{BTreeSet, HashMap, HashSet};
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
use std::time::Instant;
use rayon::prelude::*;
use crate::graph::GraphStore;
// ── Well-known IRIs (with <> brackets, matching Oxigraph output) ────────
const RDF_TYPE: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
const RDF_FIRST: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#first>";
const RDF_REST: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#rest>";
const RDF_NIL: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#nil>";
const RDFS_SUBCLASS: &str = "<http://www.w3.org/2000/01/rdf-schema#subClassOf>";
const RDFS_DOMAIN: &str = "<http://www.w3.org/2000/01/rdf-schema#domain>";
const RDFS_RANGE: &str = "<http://www.w3.org/2000/01/rdf-schema#range>";
const RDFS_SUBPROP: &str = "<http://www.w3.org/2000/01/rdf-schema#subPropertyOf>";
const OWL_CLASS: &str = "<http://www.w3.org/2002/07/owl#Class>";
const OWL_THING: &str = "<http://www.w3.org/2002/07/owl#Thing>";
const OWL_NOTHING: &str = "<http://www.w3.org/2002/07/owl#Nothing>";
const OWL_RESTRICTION: &str = "<http://www.w3.org/2002/07/owl#Restriction>";
const OWL_ON_PROPERTY: &str = "<http://www.w3.org/2002/07/owl#onProperty>";
const OWL_SOME_VALUES: &str = "<http://www.w3.org/2002/07/owl#someValuesFrom>";
const OWL_ALL_VALUES: &str = "<http://www.w3.org/2002/07/owl#allValuesFrom>";
const OWL_HAS_VALUE: &str = "<http://www.w3.org/2002/07/owl#hasValue>";
const OWL_COMPLEMENT: &str = "<http://www.w3.org/2002/07/owl#complementOf>";
const OWL_INTERSECTION: &str = "<http://www.w3.org/2002/07/owl#intersectionOf>";
const OWL_UNION: &str = "<http://www.w3.org/2002/07/owl#unionOf>";
const OWL_EQUIV_CLASS: &str = "<http://www.w3.org/2002/07/owl#equivalentClass>";
const OWL_DISJOINT_WITH: &str = "<http://www.w3.org/2002/07/owl#disjointWith>";
const OWL_ALL_DISJOINT_CLASSES: &str = "<http://www.w3.org/2002/07/owl#AllDisjointClasses>";
const OWL_MEMBERS: &str = "<http://www.w3.org/2002/07/owl#members>";
const OWL_DISJOINT_UNION_OF: &str = "<http://www.w3.org/2002/07/owl#disjointUnionOf>";
const OWL_EQUIV_PROPERTY: &str = "<http://www.w3.org/2002/07/owl#equivalentProperty>";
const OWL_TRANSITIVE: &str = "<http://www.w3.org/2002/07/owl#TransitiveProperty>";
const OWL_SYMMETRIC: &str = "<http://www.w3.org/2002/07/owl#SymmetricProperty>";
const OWL_INVERSE_OF: &str = "<http://www.w3.org/2002/07/owl#inverseOf>";
const OWL_FUNCTIONAL: &str = "<http://www.w3.org/2002/07/owl#FunctionalProperty>";
const OWL_INV_FUNCTIONAL: &str = "<http://www.w3.org/2002/07/owl#InverseFunctionalProperty>";
const OWL_OBJECT_PROPERTY: &str = "<http://www.w3.org/2002/07/owl#ObjectProperty>";
const OWL_NAMED_INDIVIDUAL: &str = "<http://www.w3.org/2002/07/owl#NamedIndividual>";
const OWL_MIN_CARD: &str = "<http://www.w3.org/2002/07/owl#minCardinality>";
const OWL_MAX_CARD: &str = "<http://www.w3.org/2002/07/owl#maxCardinality>";
const OWL_EXACT_CARD: &str = "<http://www.w3.org/2002/07/owl#cardinality>";
const OWL_EXACT_QCARD: &str = "<http://www.w3.org/2002/07/owl#qualifiedCardinality>";
const OWL_MIN_QCARD: &str = "<http://www.w3.org/2002/07/owl#minQualifiedCardinality>";
const OWL_MAX_QCARD: &str = "<http://www.w3.org/2002/07/owl#maxQualifiedCardinality>";
const OWL_ON_CLASS: &str = "<http://www.w3.org/2002/07/owl#onClass>";
// Tableaux safety limits live in `crate::runtime` (initialised from
// `[reasoner] tableaux_max_depth` / `tableaux_max_nodes` in config.toml).
// ── Concept (Negation Normal Form) ──────────────────────────────────────
/// Description Logic concept in NNF (Negation Normal Form).
/// All negations pushed to atomic level. Covers SHIQ. There is no nominal
/// constructor in this enum, so `owl:oneOf` has no representation and
/// `owl:hasValue` is carried as an atomic concept named after the individual.
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum Concept {
Top,
Bottom,
Atom(u32),
NegAtom(u32),
And(Vec<Concept>),
Or(Vec<Concept>),
Exists(u32, Box<Concept>), // ∃R.C
ForAll(u32, Box<Concept>), // ∀R.C
MinCard(u32, u32, Box<Concept>), // ≥n R.C (role, n, filler)
MaxCard(u32, u32, Box<Concept>), // ≤n R.C (role, n, filler)
}
impl Concept {
/// Push negation inward to produce NNF.
pub fn negate(&self) -> Concept {
match self {
Concept::Top => Concept::Bottom,
Concept::Bottom => Concept::Top,
Concept::Atom(a) => Concept::NegAtom(*a),
Concept::NegAtom(a) => Concept::Atom(*a),
Concept::And(cs) => {
let mut parts: Vec<_> = cs.iter().map(|c| c.negate()).collect();
parts.sort();
Concept::Or(parts)
}
Concept::Or(cs) => {
let mut parts: Vec<_> = cs.iter().map(|c| c.negate()).collect();
parts.sort();
Concept::And(parts)
}
Concept::Exists(r, c) => Concept::ForAll(*r, Box::new(c.negate())),
Concept::ForAll(r, c) => Concept::Exists(*r, Box::new(c.negate())),
// ¬(≥n R.C) = ≤(n-1) R.C
Concept::MinCard(r, n, c) => {
if *n == 0 {
Concept::Bottom // ≥0 is always true, ¬⊤ = ⊥
} else {
Concept::MaxCard(*r, n - 1, c.clone())
}
}
// ¬(≤n R.C) = ≥(n+1) R.C
Concept::MaxCard(r, n, c) => Concept::MinCard(*r, n + 1, c.clone()),
}
}
}
/// Pre-NNF concept used during OWL parsing.
#[derive(Clone, Debug)]
enum RawConcept {
Top,
Bottom,
Named(u32),
Not(Box<RawConcept>),
And(Vec<RawConcept>),
Or(Vec<RawConcept>),
Exists(u32, Box<RawConcept>),
ForAll(u32, Box<RawConcept>),
MinCard(u32, u32, Box<RawConcept>),
MaxCard(u32, u32, Box<RawConcept>),
}
impl RawConcept {
fn to_nnf(&self) -> Concept {
match self {
RawConcept::Top => Concept::Top,
RawConcept::Bottom => Concept::Bottom,
RawConcept::Named(id) => Concept::Atom(*id),
RawConcept::Not(inner) => inner.to_nnf().negate(),
RawConcept::And(cs) => {
let mut parts: Vec<_> = cs.iter().map(|c| c.to_nnf()).collect();
parts.sort();
match parts.len() {
0 => Concept::Top,
1 => parts.remove(0),
_ => Concept::And(parts),
}
}
RawConcept::Or(cs) => {
let mut parts: Vec<_> = cs.iter().map(|c| c.to_nnf()).collect();
parts.sort();
match parts.len() {
0 => Concept::Bottom,
1 => parts.remove(0),
_ => Concept::Or(parts),
}
}
RawConcept::Exists(r, c) => Concept::Exists(*r, Box::new(c.to_nnf())),
RawConcept::ForAll(r, c) => Concept::ForAll(*r, Box::new(c.to_nnf())),
RawConcept::MinCard(r, n, c) => Concept::MinCard(*r, *n, Box::new(c.to_nnf())),
RawConcept::MaxCard(r, n, c) => Concept::MaxCard(*r, *n, Box::new(c.to_nnf())),
}
}
}
// ── String Interner ─────────────────────────────────────────────────────
#[derive(Clone)]
pub struct Interner {
to_id: HashMap<String, u32>,
to_str: Vec<String>,
}
impl Interner {
fn new() -> Self {
Self {
to_id: HashMap::new(),
to_str: Vec::new(),
}
}
pub(crate) fn intern(&mut self, s: &str) -> u32 {
if let Some(&id) = self.to_id.get(s) {
return id;
}
let id = self.to_str.len() as u32;
self.to_str.push(s.to_string());
self.to_id.insert(s.to_string(), id);
id
}
pub fn resolve(&self, id: u32) -> &str {
&self.to_str[id as usize]
}
}
// ── Triple Index ────────────────────────────────────────────────────────
/// A by-subject view of a graph, with the one RDF list reader this crate has.
///
/// `pub(crate)` rather than private because `rulesyntax.rs` reads SWRL atom
/// lists, which are `rdf:List`s exactly as `owl:intersectionOf`'s operand list
/// is. A second traversal of `rdf:first`/`rdf:rest` would be a second thing to
/// keep right; there is one, and `walk_list_checked` is it.
pub(crate) struct TripleIndex {
/// Ordered, not hashed. Every pass of the parser walks this map, and the
/// order it walks in is the order IRIs are interned, which fixes the
/// numeric ids concepts are sorted by, which fixes the order the tableau
/// tries disjuncts in. With a `HashMap` that order changed from run to run
/// of one input, and once backjumping and early disjointness made the
/// search order matter, so did the number of steps a run took (#161).
by_subject: std::collections::BTreeMap<String, Vec<(String, String)>>,
}
/// Why a traversal of an `rdf:List` did not reach `rdf:nil`.
///
/// `walk_list` drops this, which is right for the DL parser: a malformed
/// `owl:intersectionOf` list yields a shorter conjunction, the reasoner derives
/// less, and deriving less is the sound direction. It is NOT right for a rule
/// importer, where a truncated body is a DIFFERENT RULE that fires more often
/// than the one the user wrote. So the defect is returned and the caller
/// decides.
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum ListDefect {
/// A cell with no `rdf:first`. Its position in the list is lost.
NoFirst(String),
/// A cell with no `rdf:rest`, so the list never reaches `rdf:nil`.
Unterminated(String),
/// Still walking after `MAX_LIST_CELLS` cells: a cycle, or a list longer
/// than anything this reads.
TooLong,
}
impl ListDefect {
pub(crate) fn describe(&self) -> String {
match self {
ListDefect::NoFirst(cell) => {
format!("the list cell {cell} has no rdf:first, so an element is missing")
}
ListDefect::Unterminated(cell) => format!(
"the list cell {cell} has no rdf:rest, so the list never reaches rdf:nil and its \
remaining elements are unknown"
),
ListDefect::TooLong => format!(
"the list did not reach rdf:nil within {MAX_LIST_CELLS} cells, which means a \
cycle through rdf:rest or a list longer than this reads"
),
}
}
}
/// The cell budget both list readers share.
pub(crate) const MAX_LIST_CELLS: usize = 1000;
impl TripleIndex {
pub(crate) fn new(triples: &[(String, String, String)]) -> Self {
let mut by_subject: std::collections::BTreeMap<String, Vec<(String, String)>> =
std::collections::BTreeMap::new();
for (s, p, o) in triples {
by_subject
.entry(s.clone())
.or_default()
.push((p.clone(), o.clone()));
}
// The store's own iteration order is not part of the ontology either.
for pairs in by_subject.values_mut() {
pairs.sort_unstable();
}
Self { by_subject }
}
pub(crate) fn objects(&self, subject: &str, predicate: &str) -> Vec<String> {
self.by_subject
.get(subject)
.map(|pairs| {
pairs
.iter()
.filter(|(p, _)| p == predicate)
.map(|(_, o)| o.clone())
.collect()
})
.unwrap_or_default()
}
pub(crate) fn object(&self, subject: &str, predicate: &str) -> Option<String> {
self.objects(subject, predicate).into_iter().next()
}
/// Walk an `rdf:List`, reporting the FIRST thing that stopped it reaching
/// `rdf:nil` cleanly. The items are gathered exactly as `walk_list` has
/// always gathered them, so the two readings differ only in what they SAY,
/// never in what they collect.
pub(crate) fn walk_list_checked(&self, head: &str) -> (Vec<String>, Option<ListDefect>) {
let mut items = Vec::new();
let mut defect: Option<ListDefect> = None;
let mut current = head.to_string();
for _ in 0..MAX_LIST_CELLS {
if current == RDF_NIL {
return (items, defect);
}
match self.object(¤t, RDF_FIRST) {
Some(first) => items.push(first),
// Skipped, not fatal: that is what this reader has always done.
None => {
defect.get_or_insert_with(|| ListDefect::NoFirst(current.clone()));
}
}
match self.object(¤t, RDF_REST) {
Some(rest) => current = rest,
None => {
defect.get_or_insert(ListDefect::Unterminated(current));
return (items, defect);
}
}
}
(items, Some(defect.unwrap_or(ListDefect::TooLong)))
}
/// The DL parser's reading: take what there is and say nothing about a
/// malformed tail. A short `owl:intersectionOf` list yields a smaller
/// conjunction and the reasoner derives less, which is the sound direction
/// there. Behaviour is unchanged.
fn walk_list(&self, head: &str) -> Vec<String> {
self.walk_list_checked(head).0
}
}
// ── OWL Parser ──────────────────────────────────────────────────────────
struct OwlParser {
index: TripleIndex,
interner: Interner,
/// Every role's inverse, both directions, from `owl:inverseOf` between two
/// IRIs and from the anonymous inverse expressions `role_of` reads.
inverse: HashMap<u32, u32>,
}
/// The name minted for the inverse of a role that has no named inverse.
///
/// An IRI under a scheme no ontology uses, so it can never collide with a
/// declared property, and readable in an output that names it.
fn minted_inverse_name(role: &str) -> String {
format!("<urn:x-oo:inverse-of:{}>", role.trim_start_matches('<').trim_end_matches('>'))
}
impl OwlParser {
fn new(triples: Vec<(String, String, String)>) -> Self {
Self {
index: TripleIndex::new(&triples),
interner: Interner::new(),
inverse: HashMap::new(),
}
}
/// The role a property node denotes, reading `[ owl:inverseOf p ]` as the
/// inverse of `p`.
///
/// The inverse of a role is ONE role however many blank nodes write it.
/// Interning each blank node as a role of its own, and relying on the
/// generic `owl:inverseOf` collector to link it back, linked only one of
/// them: that collector keeps a single inverse per role, so with two
/// `[ owl:inverseOf hasChild ]` nodes `hasChild`'s inverse was whichever came
/// last, and a `∀` through the other never reached a parent.
fn role_of(&mut self, node: &str) -> u32 {
if node.starts_with("_:")
&& let Some(of) = self.index.object(node, OWL_INVERSE_OF)
&& of != node
{
let r = self.role_of(&of);
return self.inverse_of(r);
}
self.interner.intern(node)
}
/// `r`'s inverse, minting a name for it when the ontology names none.
fn inverse_of(&mut self, r: u32) -> u32 {
if let Some(&inv) = self.inverse.get(&r) {
return inv;
}
let name = minted_inverse_name(self.interner.resolve(r));
let inv = self.interner.intern(&name);
self.inverse.insert(r, inv);
self.inverse.insert(inv, r);
inv
}
fn parse(mut self) -> ParseResult {
let mut axioms: Vec<(Concept, Concept)> = Vec::new();
let mut named_classes: HashSet<u32> = HashSet::new();
let mut transitive_roles: HashSet<u32> = HashSet::new();
let mut sub_to_super: HashMap<u32, HashSet<u32>> = HashMap::new();
let mut disjoint_pairs: Vec<(Concept, Concept)> = Vec::new();
let mut inverse_roles: HashMap<u32, u32> = HashMap::new();
let mut functional_roles: HashSet<u32> = HashSet::new();
let mut inv_functional_roles: HashSet<u32> = HashSet::new();
let mut object_properties: HashSet<u32> = HashSet::new();
let mut individual_types: HashMap<u32, HashSet<u32>> = HashMap::new();
let mut individual_anon_types: HashMap<u32, Vec<Concept>> = HashMap::new();
let mut role_assertions: Vec<(u32, u32, u32)> = Vec::new();
let mut data_assertions: Vec<(u32, u32, u32)> = Vec::new();
let mut role_domains: Vec<(u32, Concept)> = Vec::new();
let mut role_ranges: Vec<(u32, Concept)> = Vec::new();
// Collect all subjects with their types for classification
// Ordered for the same reason as `TripleIndex::by_subject`.
let mut subject_types: std::collections::BTreeMap<String, Vec<String>> =
std::collections::BTreeMap::new();
for (s, pairs) in &self.index.by_subject {
for (p, o) in pairs {
if p == RDF_TYPE {
subject_types.entry(s.clone()).or_default().push(o.clone());
}
}
}
// Collect class declarations
// IRIs only, as in every other discovery pass below. An anonymous class
// expression written as `<owl:Class><owl:oneOf …>` also carries
// `rdf:type owl:Class`, and taking its blank node for a named class put
// it in the satisfiability sweep and in the output: Pizza reported
// `Country ⊑ _:…`, its own `owl:oneOf` enumeration.
let class_subjects: Vec<String> = subject_types
.iter()
.filter(|(s, types)| s.starts_with('<') && types.iter().any(|t| t == OWL_CLASS))
.map(|(s, _)| s.clone())
.collect();
for s in &class_subjects {
let id = self.interner.intern(s);
named_classes.insert(id);
}
// Collect object properties
let obj_prop_subjects: Vec<String> = subject_types
.iter()
.filter(|(_, types)| types.iter().any(|t| t == OWL_OBJECT_PROPERTY))
.map(|(s, _)| s.clone())
.collect();
for s in &obj_prop_subjects {
object_properties.insert(self.interner.intern(s));
}
// Collect transitive roles
let trans_subjects: Vec<String> = subject_types
.iter()
.filter(|(_, types)| types.iter().any(|t| t == OWL_TRANSITIVE))
.map(|(s, _)| s.clone())
.collect();
for s in trans_subjects {
transitive_roles.insert(self.interner.intern(&s));
}
// Collect symmetric roles → inverse of self
let sym_subjects: Vec<String> = subject_types
.iter()
.filter(|(_, types)| types.iter().any(|t| t == OWL_SYMMETRIC))
.map(|(s, _)| s.clone())
.collect();
for s in sym_subjects {
let id = self.interner.intern(&s);
inverse_roles.insert(id, id); // symmetric = own inverse
}
// Collect functional properties
let func_subjects: Vec<String> = subject_types
.iter()
.filter(|(_, types)| types.iter().any(|t| t == OWL_FUNCTIONAL))
.map(|(s, _)| s.clone())
.collect();
for s in func_subjects {
functional_roles.insert(self.interner.intern(&s));
}
// Collect inverse-functional properties
let inv_func_subjects: Vec<String> = subject_types
.iter()
.filter(|(_, types)| types.iter().any(|t| t == OWL_INV_FUNCTIONAL))
.map(|(s, _)| s.clone())
.collect();
for s in inv_func_subjects {
inv_functional_roles.insert(self.interner.intern(&s));
}
// Collect owl:inverseOf pairs (bidirectional)
let inverse_pairs_raw: Vec<(String, String)> = self
.index
.by_subject
.iter()
.flat_map(|(s, pairs)| {
pairs
.iter()
.filter(|(p, _)| p == OWL_INVERSE_OF)
.map(move |(_, o)| (s.clone(), o.clone()))
})
.collect();
for (a_str, b_str) in inverse_pairs_raw {
// A blank-node subject is an inverse-property EXPRESSION, read by
// `role_of` where it is used, not a property of its own.
if a_str.starts_with("_:") {
continue;
}
let a = self.interner.intern(&a_str);
let b = self.role_of(&b_str);
inverse_roles.insert(a, b);
inverse_roles.insert(b, a);
}
// `role_of` consults `self.inverse`, so the declared pairs go in first.
for (&a, &b) in &inverse_roles {
self.inverse.insert(a, b);
}
// owl:{Transitive,Symmetric,Functional,InverseFunctional}Property and any
// property named by owl:inverseOf are object properties by OWL semantics,
// whether or not they are also explicitly typed owl:ObjectProperty. Without
// this, a role declared only by its characteristic has its ABox role
// assertions dropped at edge-building time and the characteristic is inert.
for &r in transitive_roles
.iter()
.chain(functional_roles.iter())
.chain(inv_functional_roles.iter())
{
object_properties.insert(r);
}
for (&a, &b) in &inverse_roles {
object_properties.insert(a);
object_properties.insert(b);
}
// Collect sub-property relations
let subprop_pairs: Vec<(String, String)> = self
.index
.by_subject
.iter()
.flat_map(|(s, pairs)| {
pairs
.iter()
.filter(|(p, _)| p == RDFS_SUBPROP)
.map(move |(_, o)| (s.clone(), o.clone()))
})
.collect();
for (sub, sup) in subprop_pairs {
let sub_id = self.role_of(&sub);
let sup_id = self.role_of(&sup);
sub_to_super.entry(sub_id).or_default().insert(sup_id);
}
// `owl:equivalentProperty` is `rdfs:subPropertyOf` both ways. It was not
// read at all, so a role named only through its equivalent carried none
// of the other's edges, domains or ranges.
let equiv_props: Vec<(String, String)> = self
.index
.by_subject
.iter()
.flat_map(|(s, pairs)| {
pairs
.iter()
.filter(|(p, _)| p == OWL_EQUIV_PROPERTY)
.map(move |(_, o)| (s.clone(), o.clone()))
})
.collect();
for (a, b) in equiv_props {
let a_id = self.role_of(&a);
let b_id = self.role_of(&b);
if a_id != b_id {
sub_to_super.entry(a_id).or_default().insert(b_id);
sub_to_super.entry(b_id).or_default().insert(a_id);
}
}
inverse_roles.extend(self.inverse.iter().map(|(&a, &b)| (a, b)));
// Close the role hierarchy under inverses: `r ⊑ s` entails `r⁻ ⊑ s⁻`.
//
// In every model, `(x,y) ∈ r` implies `(x,y) ∈ s`, and `(y,x) ∈ r⁻` iff
// `(x,y) ∈ r`, so `(y,x) ∈ r⁻` implies `(y,x) ∈ s⁻`. That is the whole
// proof; the entailment is not subtle, it was simply never computed.
//
// What it was costing: each role's `rdfs:domain` and `rdfs:range` lists
// are folded over its transitive SUPER-roles once, in `ProcessedTBox::new`,
// and consulted per edge. A domain stated directly on `s` therefore already
// reached an `r` edge. A domain stated on `s⁻` did not, because `r⁻` was
// not known to be a sub-role of `s⁻`, so `s⁻`'s domain never folded into
// `r⁻`'s list and the constraint never reached the two individuals the
// edge actually binds. The same gap closed `successors()` off from
// sub-role edges reached through an inverse.
//
// ONE pass suffices, and that is not an optimisation, it is the closure.
// `inverse_roles` holds both directions of every `owl:inverseOf` pair and
// maps a symmetric role to itself, so on a well-formed ontology it is an
// involution: for any pair `(inv a, inv b)` this loop adds, applying the
// rule again yields `(inv inv a, inv inv b) = (a, b)`, already present.
// The result is closed after a single sweep, with no fixpoint to iterate
// and no chance of divergence.
//
// The map holds ONE inverse per role, so an ontology declaring two
// different inverses for the same property keeps only the last and the
// involution does not hold there. That under-closes: some entailed
// `r⁻ ⊑ s⁻` is missed. It never OVER-closes, because every pair added
// here is entailed by the pair it came from whatever else the map says,
// so the failure mode is a missed constraint and never a fabricated one.
// `onto_defects` reports that ontology shape as `inverse_not_mutual`.
//
// Transitivity is deliberately left to the existing downstream closure:
// it runs over this enlarged DIRECT relation, so `r ⊑ s ⊑ t` still yields
// `r⁻ ⊑ t⁻` through `s⁻`.
let inverse_subprops: Vec<(u32, u32)> = sub_to_super
.iter()
.flat_map(|(sub, sups)| sups.iter().map(move |sup| (*sub, *sup)))
.filter_map(|(sub, sup)| {
match (inverse_roles.get(&sub), inverse_roles.get(&sup)) {
(Some(&sub_inv), Some(&sup_inv)) if sub_inv != sup_inv => {
Some((sub_inv, sup_inv))
}
_ => None,
}
})
.collect();
for (sub_inv, sup_inv) in inverse_subprops {
sub_to_super.entry(sub_inv).or_default().insert(sup_inv);
}
// Collect SubClassOf axioms
let subclass_pairs: Vec<(String, String)> = self
.index
.by_subject
.iter()
.flat_map(|(s, pairs)| {
pairs
.iter()
.filter(|(p, _)| p == RDFS_SUBCLASS)
.map(move |(_, o)| (s.clone(), o.clone()))
})
.collect();
// A class is a class because axioms treat it as one, not because someone remembered
// to type it `owl:Class`. Real ontologies routinely declare a class only through
// rdfs:subClassOf / owl:equivalentClass / owl:disjointWith; gating discovery on the
// explicit typing silently dropped such classes from the satisfiability sweep, so an
// unsatisfiable class could be reported satisfiable by omission. Blank-node class
// expressions are excluded: only IRIs name checkable classes.
for (a, b) in &subclass_pairs {
for side in [a, b] {
if side.starts_with('<') && side != OWL_THING && side != OWL_NOTHING {
let id = self.interner.intern(side);
named_classes.insert(id);
}
}
}
for (sub_str, sup_str) in subclass_pairs {
let sub = self.parse_class_expr(&sub_str);
let sup = self.parse_class_expr(&sup_str);
axioms.push((sub.to_nnf(), sup.to_nnf()));
}
// Collect EquivalentClass axioms (→ bidirectional SubClassOf)
let mut definitions: HashMap<u32, Concept> = HashMap::new();
let equiv_pairs: Vec<(String, String)> = self
.index
.by_subject
.iter()
.flat_map(|(s, pairs)| {
pairs
.iter()
.filter(|(p, _)| p == OWL_EQUIV_CLASS)
.map(move |(_, o)| (s.clone(), o.clone()))
})
.collect();
for (a, b) in &equiv_pairs {
for side in [a, b] {
if side.starts_with('<') && side != OWL_THING && side != OWL_NOTHING {
let id = self.interner.intern(side);
named_classes.insert(id);
}
}
}
for (a_str, b_str) in equiv_pairs {
let a = self.parse_class_expr(&a_str);
let b = self.parse_class_expr(&b_str);
let a_nnf = a.to_nnf();
let b_nnf = b.to_nnf();
// Keep the definition in structural form. Realization needs to know that a
// named class IS a particular conjunction, which cannot be recovered from the
// GCI encoding once negation has been pushed through it.
if let Concept::Atom(id) = a_nnf {
definitions.insert(id, b_nnf.clone());
} else if let Concept::Atom(id) = b_nnf {
definitions.insert(id, a_nnf.clone());
}
axioms.push((a_nnf.clone(), b_nnf.clone()));
axioms.push((b_nnf, a_nnf));
}
// A NAMED class that carries owl:unionOf, owl:intersectionOf or
// owl:complementOf is DEFINED by that expression, and the definition
// used to be dropped on the floor.
//
// `parse_class_expr` reaches `try_parse_complex` only for blank nodes,
// so the three set constructors were read out of anonymous class
// expressions and nowhere else. A named IRI carrying one came back as an
// opaque atom, the definition vanished, and nothing recorded the loss:
// `unmodelled_constructs` returned empty and the table at the top of
// this file claimed `unionOf ✅`. That is the UNSOUND direction. An
// ontology inconsistent through such a definition was reported
// consistent, and a class unsatisfiable through one was reported
// satisfiable. Missing an entailment is incompleteness and this codebase
// says where it is incomplete; calling a contradiction fine is telling
// the reader something false.
//
// The OWL 2 Mapping to RDF Graphs settles the reading. The pattern
// `*:x rdf:type owl:Class . *:x owl:unionOf T(SEQ CE1 ... CEn)` with
// `*:x` an IRI maps to `EquivalentClasses(*:x ObjectUnionOf(...))`, so
// both directions go in, exactly as the `owl:equivalentClass` pass above
// does. A one-way `subClassOf` would lose the half that puts each
// disjunct inside the union.
//
// The atom is kept as the head rather than being replaced by its
// expansion, because the satisfiability sweep and the certificate layer
// both address classes by name and a class rewritten into a disjunction
// is no longer a name they can ask about.
let mut defined_named: Vec<String> = self
.index
.by_subject
.iter()
.filter(|(s, pairs)| {
s.starts_with('<')
&& s.as_str() != OWL_THING
&& s.as_str() != OWL_NOTHING
&& pairs.iter().any(|(p, _)| {
p == OWL_UNION || p == OWL_INTERSECTION || p == OWL_COMPLEMENT
})
})
.map(|(s, _)| s.clone())
.collect();
// `by_subject` is a HashMap, so its iteration order is not the file's.
// Sorted for the same reason the node traversals are: the axiom list
// reaches the tableau in this order and two runs over one ontology must
// not differ.
defined_named.sort();
for subject in defined_named {
let Some(raw) = self.try_parse_complex(&subject) else {
continue;
};
let body = raw.to_nnf();
let id = self.interner.intern(&subject);
named_classes.insert(id);
let head = Concept::Atom(id);
// Realization needs the structural form, same as the equivalence
// pass, and for the same reason: it cannot be recovered once
// negation has been pushed through the GCI encoding.
definitions.entry(id).or_insert_with(|| body.clone());
axioms.push((head.clone(), body.clone()));
axioms.push((body, head));
}
// Collect DisjointWith axioms
let disjoint_raw: Vec<(String, String)> = self
.index
.by_subject
.iter()
.flat_map(|(s, pairs)| {
pairs
.iter()
.filter(|(p, _)| p == OWL_DISJOINT_WITH)
.map(move |(_, o)| (s.clone(), o.clone()))
})
.collect();
for (a, b) in &disjoint_raw {
for side in [a, b] {
if side.starts_with('<') && side != OWL_THING && side != OWL_NOTHING {
let id = self.interner.intern(side);
named_classes.insert(id);
}
}
}
for (a_str, b_str) in disjoint_raw {
let a = self.parse_class_expr(&a_str).to_nnf();
let b = self.parse_class_expr(&b_str).to_nnf();
disjoint_pairs.push((a, b));
}
// `owl:AllDisjointClasses` with an `owl:members` list, which is how the
// OWL 2 mapping writes `DisjointClasses` of three or more classes, and
// `owl:disjointUnionOf`, which is `C ≡ C₁ ⊔ … ⊔ Cₙ` with the `Cᵢ`
// pairwise disjoint. Neither was read. Only the binary `owl:disjointWith`
// was, so an n-ary disjointness, the usual way an ontology says its
// siblings do not overlap, was silently absent. Measured on ORE 2015
// `ore_ont_16461`: the five affected joints of `Patient1` are in one
// 40-member `DisjointClasses`, so they could be merged, `≥4
// hasAffectedJoint.Joint` could not be proved, and `Patient1 ⊑
// Systemic_JIA_Patient` (which HermiT finds) was missing from a run that
// reported itself complete.
let mut all_disjoint: Vec<String> = subject_types
.iter()
.filter(|(_, types)| types.iter().any(|t| t == OWL_ALL_DISJOINT_CLASSES))
.map(|(s, _)| s.clone())
.collect();
all_disjoint.sort();
for node in all_disjoint {
let Some(head) = self.index.object(&node, OWL_MEMBERS) else { continue };
let members: Vec<Concept> = self
.index
.walk_list(&head)
.iter()
.map(|m| {
if m.starts_with('<') && m != OWL_THING && m != OWL_NOTHING {
let id = self.interner.intern(m);
named_classes.insert(id);
}
self.parse_class_expr(m).to_nnf()
})
.collect();
for i in 0..members.len() {
for j in (i + 1)..members.len() {
disjoint_pairs.push((members[i].clone(), members[j].clone()));
}
}
}
let mut disjoint_unions: Vec<(String, String)> = self
.index
.by_subject
.iter()
.flat_map(|(s, pairs)| {
pairs
.iter()
.filter(|(p, _)| p == OWL_DISJOINT_UNION_OF)
.map(move |(_, o)| (s.clone(), o.clone()))
})
.collect();
disjoint_unions.sort();
for (class, head) in disjoint_unions {
let members_raw = self.index.walk_list(&head);
let id = self.interner.intern(&class);
named_classes.insert(id);
let members: Vec<Concept> = members_raw
.iter()
.map(|m| {
if m.starts_with('<') && m != OWL_THING && m != OWL_NOTHING {
let mid = self.interner.intern(m);
named_classes.insert(mid);
}
self.parse_class_expr(m).to_nnf()
})
.collect();
let union = match members.len() {
0 => Concept::Bottom,
1 => members[0].clone(),
_ => {
let mut parts = members.clone();
parts.sort();
Concept::Or(parts)
}
};
axioms.push((Concept::Atom(id), union.clone()));
axioms.push((union, Concept::Atom(id)));
for i in 0..members.len() {
for j in (i + 1)..members.len() {
disjoint_pairs.push((members[i].clone(), members[j].clone()));
}
}
}
// Collect rdfs:domain / rdfs:range as GCIs.
//
// These are ordinary DL axioms and were previously not read at all, so every
// incoherence arising from a property's domain or range colliding with a
// disjointness axiom was reported satisfiable. Measured on the GCHQ-published
// hqdm.owl: HermiT finds 39 unsatisfiable classes, this reasoner found 0,
// because that file carries 265 domain and 260 range declarations and nothing
// consumed them. The failure direction is the dangerous one - it answers
// "satisfiable" when it cannot tell - so a coherence gate built on it passes
// everything.
//
// domain(p, D) => exists p.Top [= D
// range(p, R) => Top [= forall p.R
//
// Datatype ranges are skipped: xsd:* and rdfs:Literal are not concepts, and
// asserting Top [= forall p.xsd:string would be a type error, not an axiom.
let domain_range_raw: Vec<(String, String, bool)> = self
.index
.by_subject
.iter()
.flat_map(|(s, pairs)| {
pairs.iter().filter_map(move |(p, o)| {
if p == RDFS_DOMAIN {
Some((s.clone(), o.clone(), true))
} else if p == RDFS_RANGE {
Some((s.clone(), o.clone(), false))
} else {
None
}
})
})
.collect();
for (prop_str, cls_str, is_domain) in domain_range_raw {
if cls_str.starts_with("<http://www.w3.org/2001/XMLSchema#")
|| cls_str == "<http://www.w3.org/2000/01/rdf-schema#Literal>"
|| cls_str == OWL_THING
{
continue;
}
let role = self.role_of(&prop_str);
let cls = self.parse_class_expr(&cls_str).to_nnf();
if cls_str.starts_with('<') && cls_str != OWL_NOTHING {
let id = self.interner.intern(&cls_str);
named_classes.insert(id);
}
if is_domain {
role_domains.push((role, cls));
} else {
role_ranges.push((role, cls));
}
}
// Collect individuals and their types + role assertions.
//
// An individual is discovered two ways: the explicit `owl:NamedIndividual` typing,
// or an rdf:type pointing at a known class. Instance data in the wild almost never
// carries the explicit typing, and gating on it meant the ABox check received no
// individuals at all, so a textbook inconsistency - one individual typed into two
// disjoint classes - sailed through as consistent. Subjects that are themselves
// schema declarations are excluded, so a class or property never doubles as an
// individual by accident.
let schema_markers: [&str; 10] = [
OWL_CLASS,
OWL_OBJECT_PROPERTY,
OWL_TRANSITIVE,
"<http://www.w3.org/2002/07/owl#DatatypeProperty>",
"<http://www.w3.org/2002/07/owl#AnnotationProperty>",
"<http://www.w3.org/2002/07/owl#FunctionalProperty>",
"<http://www.w3.org/2002/07/owl#InverseFunctionalProperty>",
"<http://www.w3.org/2002/07/owl#SymmetricProperty>",
"<http://www.w3.org/2002/07/owl#Ontology>",
"<http://www.w3.org/2000/01/rdf-schema#Class>",
];
let mut individual_subjects: Vec<String> = Vec::new();
for (subject, types) in &subject_types {
if types.iter().any(|t| schema_markers.contains(&t.as_str())) {
continue;
}
let explicit = types.iter().any(|t| t == OWL_NAMED_INDIVIDUAL);
let typed_by_known_class = types.iter().any(|t| {
t.starts_with('<') && {
let id = self.interner.intern(t);
named_classes.contains(&id)
}
});
// An individual typed only by an anonymous class expression is still an
// individual, and its constraint still has to be checked.
let typed_by_anon_class = types.iter().any(|t| t.starts_with("_:"));
if explicit || typed_by_known_class || typed_by_anon_class {
individual_subjects.push(subject.clone());
}
}
// A subject that makes role assertions is an individual whether or not
// anybody typed it.
//
// The loop above walks `subject_types`, which only has an entry for a
// subject carrying an `rdf:type` at all, and then keeps it only if that
// type is recognisable as a class. So an IRI that is never typed, or is
// typed only by a vocabulary this reasoner does not treat as a class (a
// `skos:Concept`, say), contributed NOTHING: not its edges, not itself.
// Now that `add_role_edge` applies `rdfs:domain` and `rdfs:range` to
// asserted edges, that is a false clean with a very short witness — an
// individual with two role assertions whose domains are disjoint classes
// is inconsistent on those two triples alone, and the check never saw
// them. The object side of exactly this hole was already closed, in
// `build_abox_tableau`, which builds a node for any individual named as
// the OBJECT of a role assertion. This is the subject side.
//
// The filter is deliberately narrow, because the cost of being wrong
// here is sweeping schema into the ABox:
// - IRIs only, matching the rule used for class discovery. A blank node
// subject is a parsed class expression, not an individual.
// - Not already an individual, and not a declared class or property, so
// `:p a owl:ObjectProperty` can never double as an instance.
// - At least one predicate that is a DECLARED object property. That is
// the only reason this individual is wanted: it is the thing that
// produces an edge. A subject carrying nothing but `rdfs:label` or a
// `rdfs:subClassOf` is schema and stays out.
// `object_properties` is complete by this point: it is filled from the
// explicit typing, from the four characteristic types and from both sides
// of every `owl:inverseOf` pair, all above.
let already: HashSet<&str> = individual_subjects.iter().map(|s| s.as_str()).collect();
let mut untyped_role_subjects: Vec<String> = Vec::new();
for (subject, pairs) in &self.index.by_subject {
if !subject.starts_with('<') || already.contains(subject.as_str()) {
continue;
}
let id = self.interner.intern(subject);
if named_classes.contains(&id) || object_properties.contains(&id) {
continue;
}
if subject_types
.get(subject)
.is_some_and(|ts| ts.iter().any(|t| schema_markers.contains(&t.as_str())))
{
continue;
}
let asserts_a_role = pairs.iter().any(|(p, _)| {
p != RDF_TYPE && object_properties.contains(&self.interner.intern(p))
});
if asserts_a_role {
untyped_role_subjects.push(subject.clone());
}
}
individual_subjects.extend(untyped_role_subjects);
individual_subjects.sort_unstable();
individual_subjects.dedup();
for ind_str in &individual_subjects {
let ind_id = self.interner.intern(ind_str);
let types = self.index.objects(ind_str, RDF_TYPE);
for t in &types {
if t.starts_with("_:") {
// Anonymous class expression: parse it and attach the concept
// so the constraint reaches the tableau. A blank node is never a
// named class, so this is disjoint from the branch below.
let concept = self.parse_class_expr(t).to_nnf();
individual_anon_types.entry(ind_id).or_default().push(concept);
continue;
}
let t_id = self.interner.intern(t);
if named_classes.contains(&t_id) {
individual_types.entry(ind_id).or_default().insert(t_id);
}
}
// Role assertions
if let Some(pairs) = self.index.by_subject.get(ind_str) {
for (p, o) in pairs {
if p == RDF_TYPE {
continue;
}
let p_id = self.interner.intern(p);
if object_properties.contains(&p_id) {
let o_id = self.interner.intern(o);
role_assertions.push((ind_id, p_id, o_id));
} else {
// Datatype assertions are kept apart from role assertions on purpose.
// They must not become tableau edges, since a literal is not a node,
// but realization needs them: owl:hasValue on a datatype property is
// how a defined class picks out individuals by a flag, and dropping
// these made every such class permanently empty.
let o_id = self.interner.intern(o);
data_assertions.push((ind_id, p_id, o_id));
}
}
}
}
// Anonymous inverse expressions met while parsing class expressions,
// domains and ranges minted inverses after the role hierarchy was closed
// under inverses above, so the minted ones join the map and the closure
// runs again. It is idempotent on the pairs it has already added.
inverse_roles.extend(self.inverse.iter().map(|(&a, &b)| (a, b)));
let late_inverse_subprops: Vec<(u32, u32)> = sub_to_super
.iter()
.flat_map(|(sub, sups)| sups.iter().map(move |sup| (*sub, *sup)))
.filter_map(|(sub, sup)| match (inverse_roles.get(&sub), inverse_roles.get(&sup)) {
(Some(&sub_inv), Some(&sup_inv)) if sub_inv != sup_inv => Some((sub_inv, sup_inv)),
_ => None,
})
.collect();
for (sub_inv, sup_inv) in late_inverse_subprops {
sub_to_super.entry(sub_inv).or_default().insert(sup_inv);
}
for &r in transitive_roles.clone().iter() {
if let Some(&inv) = inverse_roles.get(&r) {
transitive_roles.insert(inv);
}
}
// Ensure owl:Thing and owl:Nothing are interned
let thing_id = self.interner.intern(OWL_THING);
let nothing_id = self.interner.intern(OWL_NOTHING);
named_classes.insert(thing_id);
ParseResult {
interner: self.interner,
axioms,
role_domains,
role_ranges,
named_classes,
thing_id,
nothing_id,
transitive_roles,
sub_to_super,
disjoint_pairs,
inverse_roles,
functional_roles,
inv_functional_roles,
individual_types,
individual_anon_types,
role_assertions,
data_assertions,
definitions,
}
}
fn parse_class_expr(&mut self, node: &str) -> RawConcept {
if node == OWL_THING {
return RawConcept::Top;
}
if node == OWL_NOTHING {
return RawConcept::Bottom;
}
// Blank nodes: check for complex class expressions
if node.starts_with("_:")
&& let Some(c) = self.try_parse_complex(node) {
return c;
}
// Named class
let id = self.interner.intern(node);
RawConcept::Named(id)
}
fn try_parse_complex(&mut self, node: &str) -> Option<RawConcept> {
// Restriction
if self
.index
.objects(node, RDF_TYPE)
.iter()
.any(|t| t == OWL_RESTRICTION)
{
return Some(self.parse_restriction(node));
}
// intersectionOf
if let Some(list_head) = self.index.object(node, OWL_INTERSECTION) {
let items = self.index.walk_list(&list_head);
let concepts: Vec<_> = items.iter().map(|i| self.parse_class_expr(i)).collect();
return Some(if concepts.is_empty() {
RawConcept::Top
} else {
RawConcept::And(concepts)
});
}
// unionOf
if let Some(list_head) = self.index.object(node, OWL_UNION) {
let items = self.index.walk_list(&list_head);
let concepts: Vec<_> = items.iter().map(|i| self.parse_class_expr(i)).collect();
return Some(if concepts.is_empty() {
RawConcept::Bottom
} else {
RawConcept::Or(concepts)
});
}
// complementOf
if let Some(comp) = self.index.object(node, OWL_COMPLEMENT) {
return Some(RawConcept::Not(Box::new(self.parse_class_expr(&comp))));
}
None
}
/// A restriction this parser does not model, as an opaque atom named by its
/// own blank node.
///
/// This used to be `RawConcept::Top`, which is a sound weakening on the
/// right of an inclusion and an unsound strengthening on the left. An
/// `owl:equivalentClass` puts each side on the left once, so `Narcissist ≡
/// ∃loves.Self` became `⊤ ⊑ Narcissist` and every class in the ontology was
/// reported a subclass of `Narcissist`. A fresh name is sound in both
/// places: every model of the ontology extends to a model of the rewritten
/// one by giving the name the expression's extension, so whatever the
/// rewritten ontology entails over the original names, the original
/// entails. The same blank node always gets the same atom, which keeps the
/// two directions of an equivalence talking about one thing.
fn opaque_restriction(&mut self, node: &str) -> RawConcept {
RawConcept::Named(self.interner.intern(node))
}
fn parse_restriction(&mut self, node: &str) -> RawConcept {
let prop = match self.index.object(node, OWL_ON_PROPERTY) {
Some(p) => self.role_of(&p),
None => return self.opaque_restriction(node),
};
// someValuesFrom → ∃R.C
if let Some(filler) = self.index.object(node, OWL_SOME_VALUES) {
return RawConcept::Exists(prop, Box::new(self.parse_class_expr(&filler)));
}
// allValuesFrom → ∀R.C
if let Some(filler) = self.index.object(node, OWL_ALL_VALUES) {
return RawConcept::ForAll(prop, Box::new(self.parse_class_expr(&filler)));
}
// hasValue → ∃R.{a} (approximated as ∃R.Named(a))
if let Some(value) = self.index.object(node, OWL_HAS_VALUE) {
let val_id = self.interner.intern(&value);
return RawConcept::Exists(prop, Box::new(RawConcept::Named(val_id)));
}
// Qualified cardinality restrictions
let on_class = self.index.object(node, OWL_ON_CLASS);
let filler = match on_class {
Some(ref cls) => self.parse_class_expr(cls),
None => RawConcept::Top,
};
// minQualifiedCardinality / minCardinality → ≥n R.C
if let Some(val) = self
.index
.object(node, OWL_MIN_QCARD)
.or_else(|| self.index.object(node, OWL_MIN_CARD))
&& let Some(n) = parse_card_value(&val) {
return RawConcept::MinCard(prop, n, Box::new(filler));
}
// maxQualifiedCardinality / maxCardinality → ≤n R.C
if let Some(val) = self
.index
.object(node, OWL_MAX_QCARD)
.or_else(|| self.index.object(node, OWL_MAX_CARD))
&& let Some(n) = parse_card_value(&val) {
return RawConcept::MaxCard(prop, n, Box::new(filler));
}
// qualifiedCardinality / cardinality → ≥n R.C ⊓ ≤n R.C
//
// The qualified form was missing while min and max both had it, so an
// `owl:qualifiedCardinality` restriction fell through to Top: no
// successor was ever generated and nothing downstream of it could
// clash. That is how hqdm.owl's `defined_relationship` reads as
// satisfiable — its =1 member_of_kind successor, which rdfs:range and
// owl:onClass place in two disjoint classes, was never created.
if let Some(val) = self
.index
.object(node, OWL_EXACT_QCARD)
.or_else(|| self.index.object(node, OWL_EXACT_CARD))
&& let Some(n) = parse_card_value(&val) {
return RawConcept::And(vec![
RawConcept::MinCard(prop, n, Box::new(filler.clone())),
RawConcept::MaxCard(prop, n, Box::new(filler)),
]);
}
// `owl:hasSelf`, a cardinality whose literal does not parse, or anything
// else this reader does not know.
self.opaque_restriction(node)
}
}
/// Parse cardinality value from OWL literal (e.g., "2"^^<xsd:nonNegativeInteger>).
fn parse_card_value(literal: &str) -> Option<u32> {
if let Some(rest) = literal.strip_prefix('"')
&& let Some(end) = rest.find('"')
{
return rest[..end].parse().ok();
}
literal.parse().ok()
}
pub(crate) struct ParseResult {
pub(crate) interner: Interner,
pub(crate) axioms: Vec<(Concept, Concept)>,
pub(crate) named_classes: HashSet<u32>,
pub(crate) thing_id: u32,
pub(crate) nothing_id: u32,
pub(crate) transitive_roles: HashSet<u32>,
pub(crate) sub_to_super: HashMap<u32, HashSet<u32>>,
pub(crate) disjoint_pairs: Vec<(Concept, Concept)>,
pub(crate) inverse_roles: HashMap<u32, u32>,
pub(crate) functional_roles: HashSet<u32>,
pub(crate) inv_functional_roles: HashSet<u32>,
/// rdfs:domain / rdfs:range, kept as ROLE METADATA rather than GCIs.
/// Encoding them as axioms puts a non-atomic left-hand side into the GCI
/// list, which lands a disjunction on every node and multiplies branching.
pub(crate) role_domains: Vec<(u32, Concept)>,
pub(crate) role_ranges: Vec<(u32, Concept)>,
pub(crate) individual_types: HashMap<u32, HashSet<u32>>,
/// Individuals typed directly by an ANONYMOUS class expression
/// (`:a rdf:type [ owl:Restriction … ]`, an intersection/union/complement).
/// These carry no named-class id, so they cannot live in `individual_types`,
/// but the constraint they impose is real and an inconsistency arising from
/// it must be found rather than silently dropped.
pub(crate) individual_anon_types: HashMap<u32, Vec<Concept>>,
pub(crate) role_assertions: Vec<(u32, u32, u32)>,
/// Datatype-property assertions, for realization only; never tableau edges.
pub(crate) data_assertions: Vec<(u32, u32, u32)>,
/// Named class → the concept it is defined as being equivalent to.
pub(crate) definitions: HashMap<u32, Concept>,
}
/// The OWL parser's reading of a triple set, before `ProcessedTBox` absorbs it.
///
/// `onto_classify_el` normalises these axioms for EL completion rather than
/// writing a second RDF-to-DL reader: one parser means the tableau and the EL
/// saturation disagree only where their rules do, never where their reading
/// of `owl:Restriction` or `rdf:List` does.
pub(crate) fn parse_owl(triples: Vec<(String, String, String)>) -> ParseResult {
OwlParser::new(triples).parse()
}
// ── Absorption ──────────────────────────────────────────────────────────
/// Rewrites a TBox so that as few axioms as possible sit on every node.
///
/// An inclusion whose left-hand side is not a single named class used to go
/// into the GCI list as `¬C ⊔ D`, and every GCI is added to EVERY node of every
/// tableau. Each one is a disjunction, so each one can double the branching of
/// the whole search. That is what kept three different inputs from terminating:
/// the four-nominal LUBM repro in `benchmark/reasoner/regressions/` (each
/// `C ≡ ∃worksFor.{d}` puts `∀worksFor.¬{d} ⊔ C` on every node), the ORE 2015 EL
/// files (thirty-odd `∃r.⊤ ⊑ C` axioms), and the canonical Pizza ontology,
/// whose defined classes (`CheeseyPizza ≡ Pizza ⊓ ∃hasTopping.CheeseTopping`)
/// each contribute one reverse half of that shape.
///
/// The rewrites are the standard ones (Horrocks, *Optimising Tableaux Decision
/// Procedures for Description Logics*, 1997; Hudek and Weddell, *Binary
/// Absorption in Tableaux-Based Reasoning for Description Logics*, 2006), and
/// each one replaces an axiom by axioms that ENTAIL it over the original names
/// and are entailed by it once the fresh names are read as the sub-expressions
/// they stand for. So a model of the rewritten TBox is a model of the original,
/// and every model of the original extends to one of the rewritten TBox: the
/// rewrite neither adds nor loses an entailment over the ontology's own names.
///
/// - `⊤ ⊑ D` is `D` on every node, with no disjunction.
/// - `∃r.⊤ ⊑ D` is a DOMAIN of `r`, applied when an `r` edge is made.
/// - `∃r.F ⊑ X`, with `F` a named class, is `F ⊑ ∀r⁻.X`: whatever is an
/// `r`-successor in `F` puts `X` on its predecessor. A complex `F` is first
/// named by a fresh atom.
/// - `A₁ ⊓ … ⊓ Aₙ ⊑ D` over named classes is a BINARY rule, fired only on a
/// node that already carries both conjuncts, chained through fresh atoms
/// when there are more than two.
/// - `¬A ⊓ C ⊑ D` is `C ⊑ A ⊔ D`, which moves the negation to where a
/// disjunction is only met on `C`-nodes.
/// - Anything else in a conjunctive left-hand side stays a disjunction, but
/// only on the nodes that carry the absorbed part, not on every node.
///
/// The fresh atoms are named `_:oo-absorb-N`, a blank-node label, so no output
/// that lists NAMED classes can ever report one.
struct Absorber<'a> {
interner: &'a mut Interner,
inverse: HashMap<u32, u32>,
concept_defs: HashMap<u32, Vec<Concept>>,
/// `a → [(b, D)]`: a node carrying both `a` and `b` gets `D`. Stored under
/// both conjuncts, so whichever arrives second fires the rule.
binary_defs: HashMap<u32, Vec<(u32, Concept)>>,
gcis: Vec<Concept>,
domains: Vec<(u32, Concept)>,
/// One fresh atom per distinct `∃r.F` on a left-hand side, so the reverse
/// halves of many definitions that share a restriction share its name.
exists_names: HashMap<(u32, Concept), u32>,
/// One fresh atom per distinct conjunction of named classes.
and_names: HashMap<Vec<u32>, u32>,
fresh: usize,
}
impl<'a> Absorber<'a> {
fn fresh_atom(&mut self) -> u32 {
let id = self.interner.intern(&format!("_:oo-absorb-{}", self.fresh));
self.fresh += 1;
id
}
/// `r`'s inverse, minting one under the parser's naming scheme when the
/// ontology has none.
fn inverse_of(&mut self, r: u32) -> u32 {
if let Some(&inv) = self.inverse.get(&r) {
return inv;
}
let name = minted_inverse_name(self.interner.resolve(r));
let inv = self.interner.intern(&name);
self.inverse.insert(r, inv);
self.inverse.insert(inv, r);
inv
}
fn add_def(&mut self, a: u32, d: Concept) {
if d != Concept::Top {
self.concept_defs.entry(a).or_default().push(d);
}
}
fn universal(&mut self, d: Concept) {
match d {
Concept::Top => {}
Concept::And(parts) => {
for p in parts {
self.universal(p);
}
}
other => self.gcis.push(other),
}
}
/// The single atom that stands for `a₁ ⊓ … ⊓ aₙ`, wiring the binary rules
/// that put it on exactly the nodes carrying every conjunct.
fn conjunction(&mut self, mut atoms: Vec<u32>) -> u32 {
atoms.sort_unstable();
atoms.dedup();
if atoms.len() == 1 {
return atoms[0];
}
if let Some(&t) = self.and_names.get(&atoms) {
return t;
}
let mut acc = atoms[0];
for (i, &next) in atoms.iter().enumerate().skip(1) {
let prefix = atoms[..=i].to_vec();
let t = match self.and_names.get(&prefix) {
Some(&t) => t,
None => {
let t = self.fresh_atom();
self.binary_defs.entry(acc).or_default().push((next, Concept::Atom(t)));
self.binary_defs.entry(next).or_default().push((acc, Concept::Atom(t)));
self.and_names.insert(prefix, t);
t
}
};
acc = t;
}
acc
}
/// The atom `X` with `∃r.F ⊑ X`, wired so that `X` lands on every node that
/// has an `r`-successor in `F`.
fn exists_name(&mut self, r: u32, f: Concept) -> u32 {
if let Some(&x) = self.exists_names.get(&(r, f.clone())) {
return x;
}
let x = self.fresh_atom();
self.exists_names.insert((r, f.clone()), x);
match f {
Concept::Top => self.domains.push((r, Concept::Atom(x))),
Concept::Atom(c) => {
let inv = self.inverse_of(r);
self.add_def(c, Concept::ForAll(inv, Box::new(Concept::Atom(x))));
}
other => {
let y = self.fresh_atom();
self.absorb(other, Concept::Atom(y));
let inv = self.inverse_of(r);
self.add_def(y, Concept::ForAll(inv, Box::new(Concept::Atom(x))));
}
}
x
}
fn absorb(&mut self, sub: Concept, sup: Concept) {
if sup == Concept::Top {
return;
}
let mut parts: Vec<Concept> = Vec::new();
let mut stack = vec![sub];
while let Some(c) = stack.pop() {
match c {
Concept::And(cs) => stack.extend(cs),
other => parts.push(other),
}
}
let mut atoms: Vec<u32> = Vec::new();
let mut rest: Vec<Concept> = Vec::new();
let mut moved: Vec<Concept> = Vec::new();
for part in parts {
match part {
Concept::Top => {}
// `⊥ ⊓ … ⊑ D` holds of nothing and constrains nothing.
Concept::Bottom => return,
Concept::Atom(a) => atoms.push(a),
Concept::NegAtom(a) => moved.push(Concept::Atom(a)),
Concept::Exists(r, f) | Concept::MinCard(r, 1, f) => {
let x = self.exists_name(r, *f);
atoms.push(x);
}
other => rest.push(other),
}
}
let rhs = if moved.is_empty() {
sup
} else {
moved.push(sup);
disjunction(moved)
};
if !rest.is_empty() {
let unabsorbed = if rest.len() == 1 { rest.remove(0) } else { Concept::And(rest) };
let body = disjunction(vec![unabsorbed.negate(), rhs]);
if atoms.is_empty() {
self.gcis.push(body);
} else {
let t = self.conjunction(atoms);
self.add_def(t, body);
}
return;
}
if atoms.is_empty() {
self.universal(rhs);
} else {
let t = self.conjunction(atoms);
self.add_def(t, rhs);
}
}
}
/// Every role a concept mentions.
fn collect_roles(c: &Concept, out: &mut BTreeSet<u32>) {
match c {
Concept::Top | Concept::Bottom | Concept::Atom(_) | Concept::NegAtom(_) => {}
Concept::And(cs) | Concept::Or(cs) => {
for x in cs {
collect_roles(x, out);
}
}
Concept::Exists(r, f) | Concept::ForAll(r, f) => {
out.insert(*r);
collect_roles(f, out);
}
Concept::MinCard(r, _, f) | Concept::MaxCard(r, _, f) => {
out.insert(*r);
collect_roles(f, out);
}
}
}
/// `C₁ ⊔ … ⊔ Cₙ`, flattened, with `⊥` dropped and `⊤` absorbing the rest.
fn disjunction(cs: Vec<Concept>) -> Concept {
let mut out: Vec<Concept> = Vec::new();
let mut stack = cs;
while let Some(c) = stack.pop() {
match c {
Concept::Or(inner) => stack.extend(inner),
Concept::Bottom => {}
Concept::Top => return Concept::Top,
other => out.push(other),
}
}
out.sort();
out.dedup();
match out.len() {
0 => Concept::Bottom,
1 => out.remove(0),
_ => Concept::Or(out),
}
}
// ── Processed TBox ──────────────────────────────────────────────────────
#[derive(Clone)]
struct ProcessedTBox {
/// Atomic LHS definitions: when Atom(A) appears, add these concepts.
concept_defs: HashMap<u32, Vec<Concept>>,
/// General Concept Inclusions for complex LHS: ¬C ⊔ D.
gcis: Vec<Concept>,
/// Binary absorption rules: `a → [(b, D)]` puts `D` on a node carrying
/// both `a` and `b`. See `Absorber`.
binary_defs: HashMap<u32, Vec<(u32, Concept)>>,
/// Disjointness pairs.
disjoint_pairs: Vec<(Concept, Concept)>,
/// Transitive roles.
transitive_roles: HashSet<u32>,
/// Role hierarchy: super-role → every sub-role, transitively.
super_to_sub: HashMap<u32, HashSet<u32>>,
/// Inverse role mapping (bidirectional): R → R⁻ and R⁻ → R.
inverse_roles: HashMap<u32, u32>,
/// Transitive closure of asserted Atom ⊑ Atom subsumption, used to decide
/// cardinality clashes whose fillers are related by subsumption rather than
/// syntactically equal.
class_closure: HashMap<u32, HashSet<u32>>,
/// Effective rdfs:domain per role, super-role constraints already folded in.
/// Applied to the SOURCE node when an edge is created.
role_domain: HashMap<u32, Vec<Concept>>,
/// Effective rdfs:range per role, likewise. Applied to the TARGET node.
role_range: HashMap<u32, Vec<Concept>>,
}
/// Role-level axioms, grouped so `ProcessedTBox::new` keeps a workable
/// argument count as more role metadata (domains, ranges) is absorbed out of
/// the GCI list.
struct RoleAxioms<'a> {
transitive_roles: HashSet<u32>,
sub_to_super: &'a HashMap<u32, HashSet<u32>>,
inverse_roles: HashMap<u32, u32>,
functional_roles: &'a HashSet<u32>,
inv_functional_roles: &'a HashSet<u32>,
role_domains: &'a [(u32, Concept)],
role_ranges: &'a [(u32, Concept)],
}
impl ProcessedTBox {
fn new(
axioms: &[(Concept, Concept)],
disjoint_pairs: &[(Concept, Concept)],
roles: RoleAxioms<'_>,
interner: &mut Interner,
) -> Self {
let RoleAxioms {
mut transitive_roles,
sub_to_super,
inverse_roles,
functional_roles,
inv_functional_roles,
role_domains,
role_ranges,
} = roles;
// ── GCI absorption ──────────────────────────────────────────────
//
// An axiom with a non-atomic left-hand side becomes ¬sub ⊔ sup and is
// added to EVERY node, so each one doubles the branching factor of the
// whole tableau. Two standard rewrites turn most of them into atomic
// left-hand sides, which absorb into concept_defs and fire only when
// the class actually appears in a label:
//
// (C₁ ⊔ C₂) ⊑ D ==> C₁ ⊑ D and C₂ ⊑ D
// C ⊑ (D₁ ⊓ D₂) ==> C ⊑ D₁ and C ⊑ D₂
//
// The first is what hqdm.owl needs: `abstract_object ≡ class ⊔
// relationship` produces a disjunctive left-hand side that kept the
// whole ontology undecidable within budget.
let mut work: Vec<(Concept, Concept)> = axioms.to_vec();
let mut absorbed: Vec<(Concept, Concept)> = Vec::new();
let mut guard = 0usize;
while let Some((sub, sup)) = work.pop() {
guard += 1;
if guard > 100_000 {
absorbed.push((sub, sup));
continue;
}
match (&sub, &sup) {
(Concept::Or(parts), _) if !parts.is_empty() => {
for part in parts {
work.push((part.clone(), sup.clone()));
}
}
(_, Concept::And(parts)) if !parts.is_empty() => {
for part in parts {
work.push((sub.clone(), part.clone()));
}
}
_ => absorbed.push((sub, sup)),
}
}
let axioms: &[(Concept, Concept)] = &absorbed;
let mut absorber = Absorber {
interner,
inverse: inverse_roles,
concept_defs: HashMap::new(),
binary_defs: HashMap::new(),
gcis: Vec::new(),
domains: Vec::new(),
exists_names: HashMap::new(),
and_names: HashMap::new(),
fresh: 0,
};
for (sub, sup) in axioms {
absorber.absorb(sub.clone(), sup.clone());
}
// `A disjointWith B` is `A ⊓ B ⊑ ⊥`, and absorbed as such it is a binary
// rule that puts `⊥` on a node the moment both labels meet there. The
// list `disjoint_pairs` is still checked, but only once a branch has
// otherwise finished expanding, so a ≤-merge that fused two disjoint
// successors went on expanding everything below them, further merges
// included, before the clash was seen. On Pizza that is every
// `X ⊑ InterestingPizza` test, which has to rule out every way of
// merging four or five pairwise-disjoint toppings down to two.
for (a, b) in disjoint_pairs {
absorber.absorb(Concept::And(vec![a.clone(), b.clone()]), Concept::Bottom);
}
// Functional properties: R functional → every node gets ≤1 R.⊤
for &role in functional_roles {
absorber.gcis.push(Concept::MaxCard(role, 1, Box::new(Concept::Top)));
}
// A `∀r⁻` that absorption put on a node reaches its `r`-predecessors
// through the stored inverse edge `add_role_edge` writes, and through
// sub-roles of `r⁻`. So once any inverse is in play, every role the TBox
// names needs one, or an edge on a sub-role of `r` would have no
// inverse edge for the `∀` to follow.
let mut roles_named: BTreeSet<u32> = BTreeSet::new();
for (&sub, sups) in sub_to_super {
roles_named.insert(sub);
roles_named.extend(sups.iter().copied());
}
roles_named.extend(transitive_roles.iter().copied());
roles_named.extend(functional_roles.iter().copied());
roles_named.extend(inv_functional_roles.iter().copied());
roles_named.extend(role_domains.iter().map(|(r, _)| *r));
roles_named.extend(role_ranges.iter().map(|(r, _)| *r));
for (sub, sup) in axioms {
collect_roles(sub, &mut roles_named);
collect_roles(sup, &mut roles_named);
}
for (a, b) in disjoint_pairs {
collect_roles(a, &mut roles_named);
collect_roles(b, &mut roles_named);
}
for r in roles_named {
absorber.inverse_of(r);
}
// Inverse-functional: R inv-functional → ≤1 R⁻.⊤. Every role now has
// an inverse, so this no longer depends on the ontology naming one;
// before, an inverse-functional property with no declared inverse was
// silently unconstrained.
for &role in inv_functional_roles {
let inv = absorber.inverse_of(role);
absorber.gcis.push(Concept::MaxCard(inv, 1, Box::new(Concept::Top)));
}
let Absorber { inverse: inverse_roles, concept_defs, binary_defs, gcis, domains, .. } =
absorber;
// The role hierarchy, closed under inverses (`r ⊑ s` gives `r⁻ ⊑ s⁻`)
// and then transitively, which is what `successors` and the domain
// and range folds below both need.
let mut direct_roles: HashMap<u32, HashSet<u32>> = sub_to_super.clone();
let pairs: Vec<(u32, u32)> = direct_roles
.iter()
.flat_map(|(sub, sups)| sups.iter().map(move |sup| (*sub, *sup)))
.collect();
for (sub, sup) in pairs {
if let (Some(&si), Some(&pi)) = (inverse_roles.get(&sub), inverse_roles.get(&sup))
&& si != pi
{
direct_roles.entry(si).or_default().insert(pi);
}
}
for &r in transitive_roles.clone().iter() {
if let Some(&inv) = inverse_roles.get(&r) {
transitive_roles.insert(inv);
}
}
let mut super_of: HashMap<u32, HashSet<u32>> = HashMap::new();
for (&sub, sups) in &direct_roles {
let mut seen: HashSet<u32> = HashSet::new();
let mut stack: Vec<u32> = sups.iter().copied().collect();
while let Some(x) = stack.pop() {
if seen.insert(x)
&& let Some(next) = direct_roles.get(&x)
{
stack.extend(next.iter().copied());
}
}
seen.remove(&sub);
super_of.insert(sub, seen);
}
let mut super_to_sub_map: HashMap<u32, HashSet<u32>> = HashMap::new();
for (&sub, sups) in &super_of {
for &sup in sups {
super_to_sub_map.entry(sup).or_default().insert(sub);
}
}
// Transitive closure of asserted Atom ⊑ Atom subsumption. Needed because a
// cardinality bound stated on a superclass constrains its subclasses too,
// which a syntactic filler comparison cannot see.
let mut direct: HashMap<u32, HashSet<u32>> = HashMap::new();
for (sub, sup) in axioms {
if let (Concept::Atom(a), Concept::Atom(b)) = (sub, sup)
&& a != b
{
direct.entry(*a).or_default().insert(*b);
}
}
let mut class_closure: HashMap<u32, HashSet<u32>> = HashMap::new();
for sub in direct.keys().copied().collect::<Vec<_>>() {
let mut seen: HashSet<u32> = HashSet::new();
let mut stack: Vec<u32> = direct
.get(&sub)
.map(|v| v.iter().copied().collect())
.unwrap_or_default();
while let Some(x) = stack.pop() {
if seen.insert(x)
&& let Some(next) = direct.get(&x)
{
stack.extend(next.iter().copied());
}
}
class_closure.insert(sub, seen);
}
// Domain and range are role metadata, applied when an edge is created,
// NOT axioms. As GCIs they are `∃p.⊤ ⊑ D` and `⊤ ⊑ ∀p.R`, both with a
// non-atomic left-hand side, so both land a disjunction on every node
// and branching grows with the number of property declarations. hqdm.owl
// alone carries 525 of them.
//
// A constraint on a super-role binds its sub-roles, so each role's list
// is closed over its transitive super-roles once, here, rather than
// walked on every edge.
let fold = |src: &[(u32, Concept)]| -> HashMap<u32, Vec<Concept>> {
let mut direct: HashMap<u32, Vec<Concept>> = HashMap::new();
for (r, c) in src {
direct.entry(*r).or_default().push(c.clone());
}
let mut out = direct.clone();
for (role, sups) in &super_of {
for sup in sups {
if let Some(cs) = direct.get(sup) {
out.entry(*role).or_default().extend(cs.iter().cloned());
}
}
}
for v in out.values_mut() {
v.sort();
v.dedup();
}
out
};
let mut all_domains: Vec<(u32, Concept)> = role_domains.to_vec();
all_domains.extend(domains);
let role_domain = fold(&all_domains);
let role_range = fold(role_ranges);
Self {
concept_defs,
gcis,
binary_defs,
disjoint_pairs: disjoint_pairs.to_vec(),
transitive_roles,
super_to_sub: super_to_sub_map,
inverse_roles,
class_closure,
role_domain,
role_range,
}
}
}
// ── Tableau Node ────────────────────────────────────────────────────────
/// The choice points a label, an edge or a clash depends on.
///
/// Dependency-directed backjumping (Horrocks, 1997, section 6.3.2; Baader et
/// al., *The Description Logic Handbook*, chapter 9). Every label records the
/// `⊔` and `≤` choices it was derived under. When a branch clashes, the clash's
/// dependency set is the union of the clashing labels' sets, and a choice point
/// that is NOT in it did not cause the clash, so trying its other alternatives
/// cannot remove it: the search jumps straight past it.
///
/// Chronological backtracking, which this replaces, re-tried every later
/// choice before revisiting the one that failed. On the Pizza ontology a pizza
/// with five toppings carries one closure-axiom disjunction per topping, and a
/// wrong guess on the pizza itself (say `VegetarianPizza` on `AmericanHot`) only
/// clashes once a topping is expanded, so every combination of the toppings'
/// own disjuncts was re-tried first. That is exponential in the topping count
/// and it is why the three pizzas with the most toppings never finished.
///
/// THE SAFETY RULE: a set may be too LARGE and never too small. A set that is
/// too large only stops a jump the search could have made, which costs time.
/// A set that is too small jumps past a choice whose other alternative would
/// have found a model, and turns a satisfiable test into a proof of
/// unsatisfiability, which is a false subsumption. So anything this code does
/// not track precisely (a merge, an edge redirected by one, a label read
/// without a recorded set) is charged to EVERY open choice point.
type Dep = BTreeSet<u32>;
#[derive(Clone)]
struct TNode {
labels: HashSet<Concept>,
/// The choice points each label depends on. See `Dep`.
deps: HashMap<Concept, Dep>,
processed: HashSet<Concept>,
edges: HashMap<u32, HashSet<u32>>,
/// The choice points each outgoing edge depends on, keyed by role and
/// target. An edge with no entry is read as depending on every open choice.
edge_deps: HashMap<(u32, u32), Dep>,
parent: Option<u32>,
/// Which role created this node from its parent (for inverse propagation).
parent_role: Option<u32>,
/// The choice points this node's existence depends on: those of the `∃`
/// or `≥` label that generated it.
created: Dep,
blocked: bool,
/// The node that blocks this one directly, as `update_blocking` last
/// decided. `None` for an unblocked node AND for an indirectly blocked one,
/// which has no blocker of its own: an ancestor is blocked.
blocker: Option<u32>,
}
impl TNode {
fn new(parent: Option<u32>, parent_role: Option<u32>) -> Self {
Self {
labels: HashSet::new(),
deps: HashMap::new(),
processed: HashSet::new(),
edges: HashMap::new(),
edge_deps: HashMap::new(),
parent,
parent_role,
created: Dep::new(),
blocked: false,
blocker: None,
}
}
/// The union of the dependency sets of `labels`, or `None` if one of them
/// has no recorded set, in which case the caller must charge every open
/// choice point.
fn deps_of<'a>(&self, labels: impl IntoIterator<Item = &'a Concept>) -> Option<Dep> {
let mut out = Dep::new();
for l in labels {
out.extend(self.deps.get(l)?.iter().copied());
}
Some(out)
}
/// `has_clash`, with the choice points the clash depends on.
///
/// The outer `Option` is whether there is a clash; the inner one is
/// `None` when a clashing label carries no recorded set.
fn clash_dep(&self) -> Option<Option<Dep>> {
if self.labels.contains(&Concept::Bottom) {
return Some(self.deps_of([&Concept::Bottom]));
}
// Sorted, so the clash reported, and so the dependency set a backjump
// follows, does not depend on the label set's random hash seed.
let mut sorted: Vec<&Concept> = self.labels.iter().collect();
sorted.sort_unstable();
for &label in &sorted {
if let Concept::Atom(a) = label {
let neg = Concept::NegAtom(*a);
if self.labels.contains(&neg) {
return Some(self.deps_of([label, &neg]));
}
}
}
for &label in &sorted {
if let Concept::MinCard(r1, n1, f1) = label {
for &other in &sorted {
if let Concept::MaxCard(r2, n2, f2) = other
&& r1 == r2 && n1 > n2 && (f1 == f2 || **f2 == Concept::Top)
{
return Some(self.deps_of([label, other]));
}
}
}
if let Concept::Exists(r1, f1) = label {
for &other in &sorted {
if let Concept::MaxCard(r2, n2, f2) = other
&& r1 == r2 && *n2 == 0 && (f1 == f2 || **f2 == Concept::Top)
{
return Some(self.deps_of([label, other]));
}
}
}
}
None
}
}
// ── Explanation Trace ───────────────────────────────────────────────────
/// Records reasoning steps for clash explanation.
#[derive(Clone, Default)]
struct ExplanationTrace {
steps: Vec<String>,
enabled: bool,
}
impl ExplanationTrace {
fn new(enabled: bool) -> Self {
Self {
steps: Vec::new(),
enabled,
}
}
fn record(&mut self, step: &str) {
if self.enabled {
self.steps.push(step.to_string());
}
}
}
// ── Tableau ─────────────────────────────────────────────────────────────
/// Outcome of a satisfiability test.
///
/// A two-valued `bool` cannot express the difference between "I constructed a
/// clash, this concept is impossible" and "I ran out of budget before I could
/// decide". Conflating them is a soundness bug: the caller turns exhaustion
/// into an asserted `owl:Nothing` subsumption. This enum makes the third
/// outcome unavoidable at the type level.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Verdict {
/// A complete, clash-free model was constructed.
Satisfiable,
/// Every branch clashed. This is a proof.
Unsatisfiable,
/// A resource budget was hit first. Nothing is proven either way.
Unknown,
}
impl Verdict {
/// True only when the concept is PROVEN satisfiable. `Unknown` is not.
///
/// Note that this is NOT the negation of [`Verdict::is_unsat`]: both return
/// false for `Unknown`. Callers must handle the third case explicitly,
/// which is the whole point of the type.
pub fn is_sat(self) -> bool {
matches!(self, Verdict::Satisfiable)
}
/// True only when unsatisfiability is PROVEN. `Unknown` is not.
pub fn is_unsat(self) -> bool {
matches!(self, Verdict::Unsatisfiable)
}
/// True when no decision was reached. Callers that treat this as either
/// answer are reintroducing the bug this enum exists to prevent.
pub fn is_unknown(self) -> bool {
matches!(self, Verdict::Unknown)
}
}
/// Why a tableau run stopped short of a decision.
// Not `Copy` any more: the step counter is an `Arc` so that the branches of one
// run share it. A `Copy` budget would hand every disjunct its own counter and
// bound nothing.
#[derive(Debug, Clone)]
struct Budget {
/// Wall-clock cut-off for a single satisfiability test.
///
/// NONDETERMINISTIC by construction, which is why the step budget beside
/// it exists. A run bounded only by a clock gives different answers on a
/// fast machine and a loaded one, and `#161` is what that costs: a
/// soundness test that failed roughly three runs in five against an
/// unmodified baseline, which teaches a reader to discount red.
deadline: Option<Instant>,
/// Steps taken, SHARED across the branches of one run.
///
/// The clock is here because the node and depth budgets do not bound the
/// number of BRANCHES explored: a tableau can stay small and shallow while
/// backtracking exponentially. This counts that work directly. It is an
/// `Arc<AtomicU64>` and not a field because `Tableau` is cloned per
/// disjunct, and a per-clone counter would reset at every branch and bound
/// nothing at all.
steps: Arc<AtomicU64>,
/// The step ceiling, or `None` for no step bound.
max_steps: Option<u64>,
/// Set when any budget was hit during expansion.
exhausted: bool,
/// Which bound stopped the run, for the report. A run that ran out of
/// steps and a run that ran out of time are different facts, and a caller
/// deciding whether to retry with a bigger budget needs to know which.
stopped_by: Option<&'static str>,
}
impl Default for Budget {
fn default() -> Self {
Budget {
deadline: None,
steps: Arc::new(AtomicU64::new(0)),
max_steps: crate::runtime::tableaux_max_steps(),
exhausted: false,
stopped_by: None,
}
}
}
impl Budget {
/// Charge one step and report whether any bound has been reached.
///
/// Charging and testing are one call, and there is deliberately no way to
/// do one without the other. A separate `expired()` invites a loop that
/// tests without charging, which is how a step budget quietly stops
/// bounding anything; this type had one and it is gone.
fn spend(&mut self) -> bool {
let n = self.steps.fetch_add(1, Ordering::Relaxed) + 1;
if let Some(max) = self.max_steps
&& n >= max
{
self.stopped_by = Some("steps");
return true;
}
if self.deadline.is_some_and(|d| Instant::now() >= d) {
self.stopped_by = Some("time");
return true;
}
false
}
}
#[derive(Clone)]
struct Tableau {
nodes: HashMap<u32, TNode>,
next_id: u32,
tbox: Arc<ProcessedTBox>,
trace: ExplanationTrace,
budget: Budget,
/// Keep the completion graph of the branch that succeeded.
///
/// The ⊔-rule explores a disjunct in a CLONE and returns `true` from the
/// clone's expansion without copying it back, so after a successful run
/// `self.nodes` is the state as it was BEFORE the last disjunction, not the
/// model that was found. Every existing caller reads only the boolean, so
/// this stays off by default and nothing changes; the model emitter turns it
/// on because it has to hand over the graph, not the verdict.
capture: bool,
/// The choice points the label being added right now depends on. Every
/// rule sets it to the set of the label that fired it before adding
/// anything; between rules it is every open choice point, which is the
/// safe value for anything that forgets. See `Dep`.
ctx: Dep,
/// The `⊔` and `≤` choice points open on the path to this tableau.
open: Vec<u32>,
/// The id the next choice point will take.
next_choice: u32,
/// Why the last `expand` that returned `false` failed: the choice points
/// its clash depends on. Meaningless after a `true`.
fail_dep: Dep,
/// Whether any `⊔` branch or `≤` merge has been chosen on the path to
/// the graph this tableau holds. See `ClassModel`.
nondeterministic: bool,
}
impl Tableau {
fn new(tbox: Arc<ProcessedTBox>) -> Self {
Self {
nodes: HashMap::new(),
next_id: 0,
tbox,
trace: ExplanationTrace::new(false),
budget: Budget::default(),
capture: false,
ctx: Dep::new(),
open: Vec::new(),
next_choice: 0,
fail_dep: Dep::new(),
nondeterministic: false,
}
}
fn with_deadline(tbox: Arc<ProcessedTBox>, deadline: Option<Instant>) -> Self {
let mut t = Self::new(tbox);
t.budget.deadline = deadline;
t
}
fn new_with_tracing(tbox: Arc<ProcessedTBox>) -> Self {
Self {
nodes: HashMap::new(),
next_id: 0,
tbox,
trace: ExplanationTrace::new(true),
budget: Budget::default(),
capture: false,
ctx: Dep::new(),
open: Vec::new(),
next_choice: 0,
fail_dep: Dep::new(),
nondeterministic: false,
}
}
fn decide(&mut self, concept: &Concept) -> Verdict {
let root = self.fresh_node(None, None);
self.add_label(root, concept.clone());
// Add GCIs to root
for gci in self.tbox.gcis.clone() {
self.add_label(root, gci);
}
if self.expand(0) {
Verdict::Satisfiable
} else if self.budget.exhausted {
// We never completed the search, so we have proven nothing.
Verdict::Unknown
} else {
Verdict::Unsatisfiable
}
}
fn fresh_node(&mut self, parent: Option<u32>, parent_role: Option<u32>) -> u32 {
let id = self.next_id;
self.next_id += 1;
self.nodes.insert(id, TNode::new(parent, parent_role));
id
}
/// Every open choice point: the safe dependency set for anything whose
/// real set is not tracked.
fn all_open(&self) -> Dep {
self.open.iter().copied().collect()
}
/// The set of a label on a node, or every open choice point if none is
/// recorded.
fn label_dep(&self, node_id: u32, c: &Concept) -> Dep {
self.nodes
.get(&node_id)
.and_then(|n| n.deps.get(c).cloned())
.unwrap_or_else(|| self.all_open())
}
/// The set of the edge `from --role--> to`, read through the sub-roles of
/// `role` and the parent back-link the way `successors` reads them, or
/// every open choice point if none is recorded.
fn edge_dep(&self, from: u32, role: u32, to: u32) -> Dep {
let Some(n) = self.nodes.get(&from) else {
return self.all_open();
};
let mut roles = vec![role];
if let Some(subs) = self.tbox.super_to_sub.get(&role) {
roles.extend(subs.iter().copied());
}
for r in roles {
if n.edges.get(&r).is_some_and(|t| t.contains(&to))
&& let Some(d) = n.edge_deps.get(&(r, to))
{
return d.clone();
}
}
if n.parent == Some(to) {
return n.created.clone();
}
self.all_open()
}
fn add_label(&mut self, node_id: u32, concept: Concept) -> bool {
if concept == Concept::Top {
return false;
}
let dep = self.ctx.clone();
let node = self.nodes.get_mut(&node_id).unwrap();
if !node.labels.insert(concept.clone()) {
return false;
}
node.deps.insert(concept.clone(), dep.clone());
// Trigger concept definitions for atomic labels
if let Concept::Atom(a) = &concept {
if let Some(defs) = self.tbox.concept_defs.get(a).cloned() {
for d in defs {
self.add_label(node_id, d);
}
}
// A binary rule fires on whichever of its two conjuncts arrives
// second, so it is checked from both sides. See `Absorber`. What
// it adds depends on BOTH conjuncts.
if let Some(rules) = self.tbox.binary_defs.get(a).cloned() {
for (other, d) in rules {
let other_dep = self.nodes.get(&node_id).and_then(|n| {
n.labels
.contains(&Concept::Atom(other))
.then(|| n.deps.get(&Concept::Atom(other)).cloned())
});
if let Some(other_dep) = other_dep {
let saved = self.ctx.clone();
let mut both = dep.clone();
both.extend(other_dep.unwrap_or_else(|| self.all_open()));
self.ctx = both;
self.add_label(node_id, d);
self.ctx = saved;
}
}
}
}
true
}
/// Does the node `s` satisfy the filler concept `filler`?
///
/// This is the test every role-counting rule needs, and it is one function
/// because it was three copies of `labels.contains(&filler)` and all three
/// were wrong in the same way.
///
/// `⊤` is satisfied by EVERY element of the domain. `add_label` refuses to
/// store `Concept::Top` — correctly, since there is nothing to propagate from
/// it and carrying it would bloat every label set in the tableau — so
/// `labels.contains(&Top)` is false on every node that will ever exist. The
/// ≤-rule, the ≥-rule and the ∃-rule all counted successors with a bare
/// `contains`, so on a `⊤` filler the ≤-rule counted ZERO matching successors
/// and its bound could not be violated, while the ≥- and ∃-rules also counted
/// zero and manufactured successors they already had.
///
/// `owl:FunctionalProperty` is encoded as the GCI `≤1 R.⊤` and
/// `owl:InverseFunctionalProperty` as `≤1 R⁻.⊤`, so BOTH were completely
/// inert: no merge could ever fire, and an ABox with two distinct fillers of
/// a functional property in disjoint classes came back `consistent: true,
/// undecided: false`. The module documentation claimed both as supported.
/// `has_clash` already special-cased `⊤` when comparing two cardinality
/// LABELS on one node; the successor-counting sites were simply missed.
fn node_satisfies(&self, s: u32, filler: &Concept) -> bool {
match self.nodes.get(&s) {
Some(n) => *filler == Concept::Top || n.labels.contains(filler),
None => false,
}
}
/// Get successors via a role, considering sub-roles and inverse relationships.
fn successors(&self, node_id: u32, role: u32) -> HashSet<u32> {
let node = &self.nodes[&node_id];
let mut result = HashSet::new();
// Direct successors
if let Some(succs) = node.edges.get(&role) {
result.extend(succs);
}
// Sub-role successors
if let Some(sub_roles) = self.tbox.super_to_sub.get(&role) {
for &sub in sub_roles {
if let Some(succs) = node.edges.get(&sub) {
result.extend(succs);
}
}
}
// Inverse: if parent_role has inverse == role, parent is a role-successor
if let Some(parent_id) = node.parent
&& let Some(parent_role) = node.parent_role
&& let Some(&inv_of_parent) = self.tbox.inverse_roles.get(&parent_role)
&& role == inv_of_parent {
result.insert(parent_id);
}
result
}
/// Add a role edge, and apply everything the edge itself entails.
///
/// `rdfs:domain` binds the SOURCE and `rdfs:range` binds the TARGET. The
/// inverse edge `to inv(role) from` holds in every model in which `from role
/// to` does, so the inverse role's domain and range bind the same two nodes
/// the other way round. A symmetric role is its own inverse in
/// `inverse_roles`, so that clause covers it too.
///
/// This is the ONLY sanctioned way to add an edge, and that is the whole
/// point of it existing. `create_successor` used to be the only place
/// `role_domain` and `role_range` were consulted, while `build_abox_tableau`
/// wrote asserted role assertions straight into the edge map. A GENERATED
/// successor therefore carried its domain and its range and an ASSERTED edge
/// carried neither, so an ABox that is inconsistent precisely because an
/// asserted edge forces its subject into a class disjoint from one it
/// already has came back `consistent: true, undecided: false` — the
/// strongest answer this checker can give, and wrong. The defect was the
/// split between the two edge-creating paths, not either path on its own, so
/// the repair is a single primitive both of them go through.
///
/// Termination is unaffected. This adds labels to nodes that already exist
/// and creates none, and the labels are drawn from the same finite
/// sub-concept closure every other rule draws on, so no node's label set can
/// grow without bound and blocking still fires on the same condition.
fn add_role_edge(&mut self, from: u32, role: u32, to: u32) {
if !self.nodes.contains_key(&from) || !self.nodes.contains_key(&to) {
return;
}
let dep = self.ctx.clone();
let from_node = self.nodes.get_mut(&from).unwrap();
from_node.edges.entry(role).or_default().insert(to);
from_node.edge_deps.entry((role, to)).or_insert_with(|| dep.clone());
// The inverse edge holds in every model in which this one does, and it
// is stored rather than inferred because a `∀r⁻` placed by absorption
// has to reach an `r`-predecessor that is not a tree parent: an ABox
// neighbour, or a parent reached through a sub-role of `r`. The parent
// back-link in `successors` covered only the second case's simplest
// form.
if let Some(&inv) = self.tbox.inverse_roles.get(&role) {
let to_node = self.nodes.get_mut(&to).unwrap();
to_node.edges.entry(inv).or_default().insert(from);
to_node.edge_deps.entry((inv, from)).or_insert(dep);
}
// Keeping domain and range out of the GCI list is deliberate: as GCIs
// they are `∃p.⊤ ⊑ D` and `⊤ ⊑ ∀p.R`, both with a non-atomic left-hand
// side, so both land a disjunction on every node in the tableau. Applied
// here they cost one label each on the two nodes actually involved.
if let Some(ds) = self.tbox.role_domain.get(&role).cloned() {
for c in ds {
self.add_label(from, c);
}
}
if let Some(rs) = self.tbox.role_range.get(&role).cloned() {
for c in rs {
self.add_label(to, c);
}
}
if let Some(&inv) = self.tbox.inverse_roles.get(&role) {
if let Some(ds) = self.tbox.role_domain.get(&inv).cloned() {
for c in ds {
self.add_label(to, c);
}
}
if let Some(rs) = self.tbox.role_range.get(&inv).cloned() {
for c in rs {
self.add_label(from, c);
}
}
}
}
/// Create a new successor node and set up edges (including inverse back-edges).
fn create_successor(&mut self, parent_id: u32, role: u32, filler: Concept) -> u32 {
let succ = self.fresh_node(Some(parent_id), Some(role));
// The node exists only under the choices its generating `∃` or `≥`
// label depends on, which is what the caller left in `ctx`.
self.nodes.get_mut(&succ).unwrap().created = self.ctx.clone();
// The edge goes in through the shared primitive, which is what applies
// rdfs:domain to this node and rdfs:range to the new one.
self.add_role_edge(parent_id, role, succ);
self.add_label(succ, filler);
// Add GCIs to new node
for gci in self.tbox.gcis.clone() {
self.add_label(succ, gci);
}
// Propagate ∀ labels from parent to new successor. What lands depends
// on the `∀` label as well as on the edge.
let edge_ctx = self.ctx.clone();
let mut parent_labels: Vec<Concept> = self.nodes[&parent_id].labels.iter().cloned().collect();
parent_labels.sort_unstable();
for label in &parent_labels {
match label {
Concept::ForAll(r, f) if *r == role => {
let mut d = edge_ctx.clone();
d.extend(self.label_dep(parent_id, label));
self.ctx = d;
self.add_label(succ, *f.clone());
if self.tbox.transitive_roles.contains(r) {
self.add_label(succ, Concept::ForAll(*r, f.clone()));
}
self.ctx = edge_ctx.clone();
}
_ => {}
}
}
// Also propagate ∀S.C where S is a super-role of 'role'
// (if role ⊑ S, then an R-edge counts as an S-edge for ∀S propagation)
// Build super-roles of 'role'
let super_roles: Vec<u32> = self
.tbox
.super_to_sub
.iter()
.filter(|(_, subs)| subs.contains(&role))
.map(|(&sup, _)| sup)
.collect();
for sup_role in super_roles {
for label in &parent_labels {
if let Concept::ForAll(r, f) = label
&& *r == sup_role {
let mut d = edge_ctx.clone();
d.extend(self.label_dep(parent_id, label));
self.ctx = d;
self.add_label(succ, *f.clone());
self.ctx = edge_ctx.clone();
}
}
}
// The forward edge was added by `add_role_edge` above, together with the
// domain and range it entails.
self.trace.record(&format!(
"∃-rule: node {} creates successor {} via role {}",
parent_id, succ, role
));
succ
}
/// Merge two nodes (for ≤-rule / MaxCard). Combines labels, edges, redirects.
fn merge_nodes(&mut self, keep_id: u32, remove_id: u32) {
self.trace.record(&format!(
"≤-merge: merging node {} into node {}",
remove_id, keep_id
));
// Everything the merge moves depends on the merge itself, which the
// caller left in `ctx` (the choice, the `≤` label, and the edges and
// filler labels that made the two nodes candidates), and on whatever
// the moved thing depended on where it was.
let merge_ctx = self.ctx.clone();
// 1. Merge labels
let mut remove_labels: Vec<Concept> = self.nodes[&remove_id].labels.iter().cloned().collect();
remove_labels.sort_unstable();
for label in remove_labels {
let mut d = merge_ctx.clone();
d.extend(self.label_dep(remove_id, &label));
self.ctx = d;
self.add_label(keep_id, label);
}
self.ctx = merge_ctx.clone();
// 2. Merge edges
let remove_edges = self.nodes[&remove_id].edges.clone();
for (role, targets) in remove_edges {
for target in targets {
if target != keep_id && target != remove_id {
let mut d = merge_ctx.clone();
match self.nodes[&remove_id].edge_deps.get(&(role, target)) {
Some(e) => d.extend(e.iter().copied()),
None => d.extend(self.all_open()),
}
let keep = self.nodes.get_mut(&keep_id).unwrap();
keep.edges.entry(role).or_default().insert(target);
keep.edge_deps.entry((role, target)).or_insert(d);
}
}
}
// 3. Redirect references: in all other nodes, replace remove_id with keep_id
let mut all_ids: Vec<u32> = self.nodes.keys().copied().collect();
// Sorted: HashMap iteration order is seeded per process, so an unsorted
// traversal makes expansion order (and therefore which checks finish
// inside budget) vary run to run. Node ids are assigned sequentially, so
// sorting by id is creation order.
all_ids.sort_unstable();
for &nid in &all_ids {
if nid == remove_id {
continue;
}
let open = self.all_open();
let node = self.nodes.get_mut(&nid).unwrap();
let mut moved: Vec<u32> = Vec::new();
for (&role, targets) in node.edges.iter_mut() {
if targets.remove(&remove_id)
&& nid != keep_id {
targets.insert(keep_id);
moved.push(role);
}
}
// An edge redirected to the survivor exists there only because of
// the merge.
for role in moved {
let mut d = merge_ctx.clone();
match node.edge_deps.remove(&(role, remove_id)) {
Some(e) => d.extend(e),
None => d.extend(open.iter().copied()),
}
node.edge_deps.insert((role, keep_id), d);
}
// Update parent references
if node.parent == Some(remove_id) {
node.parent = Some(keep_id);
node.created.extend(merge_ctx.iter().copied());
}
}
// 4. Remove merged node
self.nodes.remove(&remove_id);
// 5. Clear processed set for keep_id so rules are re-applied
self.nodes.get_mut(&keep_id).unwrap().processed.clear();
}
/// Main expansion with backtracking for disjunctions and MaxCard merging.
fn expand(&mut self, depth: usize) -> bool {
let max_depth = crate::runtime::tableaux_max_depth();
let max_nodes = crate::runtime::tableaux_max_nodes();
// Hitting a budget is NOT a clash. Record it so the caller can report
// Unknown instead of asserting unsatisfiability, then unwind. The
// `false` return here means only "this branch produced no model".
// One step per call to `expand`, charged BEFORE the test, so the count
// measures work attempted rather than work that happened to finish.
let out_of_budget = self.budget.spend();
if depth > max_depth || self.nodes.len() > max_nodes || out_of_budget {
self.budget.exhausted = true;
// An exhausted branch refuted nothing, so it may not license a
// jump past any choice point.
self.fail_dep = self.all_open();
return false;
}
// Apply deterministic rules until fixpoint
loop {
// The deadline must be checked HERE, not only on entry to expand().
// This fixpoint loop can run for a very long time on a single call
// (every iteration re-runs blocking over every node), so a check
// only at function entry lets one expansion overrun the budget
// without bound.
// And one per turn of the fixpoint, which is where the expensive
// work is: every iteration re-runs blocking over every node.
if self.budget.spend() {
self.budget.exhausted = true;
self.fail_dep = self.all_open();
return false;
}
if let Some(d) = self.clash() {
self.fail_dep = d;
return false;
}
let mut changed = false;
let mut node_ids: Vec<u32> = self.nodes.keys().copied().collect();
// Sorted: HashMap iteration order is seeded per process, so an unsorted
// traversal makes expansion order (and therefore which checks finish
// inside budget) vary run to run. Node ids are assigned sequentially, so
// sorting by id is creation order.
node_ids.sort_unstable();
for &nid in &node_ids {
if !self.nodes.contains_key(&nid) || self.nodes[&nid].blocked {
continue;
}
let mut labels: Vec<Concept> = self.nodes[&nid]
.labels
.iter()
.filter(|l| !self.nodes[&nid].processed.contains(l))
.cloned()
.collect();
// Sorted, like the node traversals. A label set is a HashSet
// with a per-instance random seed, and the order rules fire in
// decides node ids, which clash is met first and therefore the
// dependency set a backjump follows. Unsorted, the number of
// branches explored moved between runs of one input (#161).
labels.sort_unstable();
for label in labels {
// Everything this rule adds depends on the label that
// fired it.
self.ctx = self.label_dep(nid, &label);
match &label {
// ⊓-rule: expand conjunction
Concept::And(cs) => {
let cs = cs.clone();
self.nodes.get_mut(&nid).unwrap().processed.insert(label);
for c in cs {
if self.add_label(nid, c) {
changed = true;
}
}
}
// ∃-rule: create successor if needed (≥1 R.C)
Concept::Exists(role, filler) => {
let role = *role;
let filler = *filler.clone();
let succs = self.successors(nid, role);
let has_matching =
succs.iter().any(|&s| self.node_satisfies(s, &filler));
if !has_matching {
self.create_successor(nid, role, filler);
changed = true;
}
self.nodes.get_mut(&nid).unwrap().processed.insert(label);
}
// ≥-rule: ensure at least n R-successors with C
Concept::MinCard(role, n, filler) => {
let role = *role;
let n = *n as usize;
let filler = *filler.clone();
let succs = self.successors(nid, role);
let matching: usize = succs
.iter()
.filter(|&&s| self.node_satisfies(s, &filler))
.count();
if matching < n {
// Guard EVERY iteration: n comes from an owl:minCardinality
// literal with no magnitude cap, so an ingested value in the
// billions would allocate that many nodes before the outer
// fixpoint check (which only runs between passes) ever sees
// them. Hitting the node budget is not a clash; record it and
// unwind so the caller reports Unknown, not a fabricated answer.
let max_nodes = crate::runtime::tableaux_max_nodes();
for _ in 0..(n - matching) {
if self.nodes.len() > max_nodes || self.budget.spend() {
self.budget.exhausted = true;
self.fail_dep = self.all_open();
return false;
}
self.create_successor(nid, role, filler.clone());
}
changed = true;
}
self.nodes.get_mut(&nid).unwrap().processed.insert(label);
}
// ∀-rule: apply filler to all successors + inverse propagation
Concept::ForAll(role, filler) => {
let role = *role;
let filler = *filler.clone();
let is_transitive = self.tbox.transitive_roles.contains(&role);
let succs = self.successors(nid, role);
let forall_dep = self.ctx.clone();
for s in succs {
if !self.nodes.contains_key(&s) {
continue;
}
let mut d = forall_dep.clone();
d.extend(self.edge_dep(nid, role, s));
self.ctx = d;
if self.add_label(s, filler.clone()) {
changed = true;
}
if is_transitive {
let forall = Concept::ForAll(role, Box::new(filler.clone()));
if self.add_label(s, forall) {
changed = true;
}
}
}
self.nodes.get_mut(&nid).unwrap().processed.insert(label);
}
// Atomic labels: already handled by add_label
Concept::Atom(_)
| Concept::NegAtom(_)
| Concept::Top
| Concept::Bottom => {
self.nodes.get_mut(&nid).unwrap().processed.insert(label);
}
// ⊔-rule and ≤-rule: handled below (non-deterministic)
Concept::Or(_) | Concept::MaxCard(..) => {}
}
}
}
self.ctx = self.all_open();
self.update_blocking();
if !changed {
break;
}
}
if let Some(d) = self.clash() {
self.fail_dep = d;
return false;
}
// ── ≤-rule (MaxCard) with node merging ──────────────────────────
// Check for MaxCard violations and merge nodes
let mut node_ids: Vec<u32> = self.nodes.keys().copied().collect();
// Sorted: HashMap iteration order is seeded per process, so an unsorted
// traversal makes expansion order (and therefore which checks finish
// inside budget) vary run to run. Node ids are assigned sequentially, so
// sorting by id is creation order.
node_ids.sort_unstable();
for &nid in &node_ids {
if !self.nodes.contains_key(&nid) || self.nodes[&nid].blocked {
continue;
}
let mut max_labels: Vec<(u32, u32, Concept)> = self.nodes[&nid]
.labels
.iter()
.filter(|l| !self.nodes[&nid].processed.contains(l))
.filter_map(|l| match l {
Concept::MaxCard(r, n, f) => Some((*r, *n, *f.clone())),
_ => None,
})
.collect();
max_labels.sort_unstable();
for (role, n, filler) in max_labels {
let succs = self.successors(nid, role);
let mut matching: Vec<u32> = succs
.iter()
.filter(|&&s| self.node_satisfies(s, &filler))
.copied()
.collect();
matching.sort_unstable();
if matching.len() as u32 > n {
self.trace.record(&format!(
"≤-rule: node {} has {} {}-successors with filler but max is {}",
nid,
matching.len(),
role,
n
));
// The bound is NOT marked processed here, and that is the
// second half of making functional properties work.
//
// This used to insert the `MaxCard` label into `nid.processed`
// before cloning, so every branch below inherited the mark and
// the rule could fire at most ONCE per node. One firing is one
// merge, which removes one successor. With three successors
// under `≤1` that leaves two, the bound is still violated, and
// the rule is already spent — so the branch completes and is
// returned as a MODEL of a constraint it visibly breaks. While
// `≤1 R.⊤` could never fire at all that was unreachable; the
// moment functionality started firing, three fillers of a
// functional property became an ordinary input.
//
// ── TERMINATION ──
//
// The measure that decreases is the recursion depth remaining,
// and it decreases by one on every merge with nothing that can
// give it back. Each firing of this rule performs exactly one
// `merge_nodes` and then recurses as `expand(depth + 1)`;
// `expand` returns `false` on entry once `depth >
// tableaux_max_depth`. So a chain of merges cannot be infinite,
// whatever the merges do to the graph. That is the guarantee,
// and it does not depend on the argument below being right.
//
// The argument below is why the bound is not reached in
// practice. `merge_nodes` removes a node, so each merge
// strictly decreases `self.nodes.len()`; the only rule that
// increases it is `create_successor`, driven by the ∃- and
// ≥-rules. Those cannot form a yo-yo with this one, because
// `merge_nodes` UNIONS the two label sets into the survivor: if
// `∃R.C` and `∃R.D` forced the two successors that were just
// identified, the survivor carries both `C` and `D`, so the
// ∃-rule's `has_matching` test is satisfied for both and it
// creates nothing. A new successor appears only for an
// existential that is genuinely unsatisfied, and each
// existential marks itself processed on its node, so it fires
// at most once there.
//
// ── WHY BLOCKING STILL FIRES ──
//
// `update_blocking()` runs at the end of every pass of the
// deterministic fixpoint loop, and the recursive
// `expand(depth + 1)` on the merged branch re-enters that loop
// from the top. So blocking is recomputed against the
// POST-MERGE graph before this rule looks at the graph again,
// and the `blocked` test at the head of this loop sees the
// fresh answer. The condition is pairwise ancestor blocking
// (Horrocks and Sattler, JAR 39), which is the variant that
// stays sound with inverse roles and number restrictions
// together — which is exactly the combination merging puts in
// play, since an inverse-functional bound is a bound on `R⁻`.
// Merging changes node labels and edges, which is precisely
// what that condition is computed from, so recomputing it after
// every merge is not an optimisation, it is required: a node
// blocked before a merge may not be blocked after it.
//
// ── AND IF THE ARGUMENT IS WRONG ANYWAY ──
//
// Depth, node count and a wall clock are all checked, the clock
// inside the inner fixpoint loop. Exhausting any of them sets
// `budget.exhausted`, which callers turn into `Verdict::Unknown`
// and `undecided: true`. The degraded answer is "I did not
// finish", never a verdict.
// A merge is a choice point. What it moves is charged to
// the choice, to the `≤` label and to each candidate's
// edge and filler label, on top of what it depended on
// before; see `merge_nodes`.
let choice = self.next_choice;
self.next_choice += 1;
let alternatives = matching.len() * (matching.len() - 1) / 2;
// Why the rule fired at all: the bound, and each candidate's
// edge and its filler label.
let max_label = Concept::MaxCard(role, n, Box::new(filler.clone()));
let mut rule_dep = self.label_dep(nid, &max_label);
for &m in &matching {
rule_dep.extend(self.edge_dep(nid, role, m));
if filler != Concept::Top {
rule_dep.extend(self.label_dep(m, &filler));
}
}
let mut failed = rule_dep.clone();
for i in 0..matching.len() {
for j in (i + 1)..matching.len() {
let mut branch = self.clone();
branch.open.push(choice);
if alternatives > 1 {
branch.nondeterministic = true;
}
let mut d = rule_dep.clone();
d.insert(choice);
branch.ctx = d;
branch.merge_nodes(matching[i], matching[j]);
branch.ctx = branch.all_open();
if branch.expand(depth + 1) {
*self = branch;
return true;
}
// Carry the budget flag back: a branch that ran out
// of room does not license "all merges clash".
self.budget.exhausted |= branch.budget.exhausted;
if self.budget.stopped_by.is_none() {
self.budget.stopped_by = branch.budget.stopped_by;
}
// Backjump, as for a disjunction: a clash that does
// not depend on this merge recurs under every other.
if !branch.fail_dep.contains(&choice) {
self.fail_dep = branch.fail_dep;
return false;
}
failed.extend(branch.fail_dep.iter().copied().filter(|&c| c != choice));
}
}
self.fail_dep = failed;
return false; // All merges lead to clash
} else {
// No violation, mark as processed
let mc_label = Concept::MaxCard(role, n, Box::new(filler));
self.nodes
.get_mut(&nid)
.unwrap()
.processed
.insert(mc_label);
}
}
}
// ── ⊔-rule: find unprocessed disjunction → branch ──────────────
let mut node_ids: Vec<u32> = self.nodes.keys().copied().collect();
// Sorted: HashMap iteration order is seeded per process, so an unsorted
// traversal makes expansion order (and therefore which checks finish
// inside budget) vary run to run. Node ids are assigned sequentially, so
// sorting by id is creation order.
node_ids.sort_unstable();
for &nid in &node_ids {
if !self.nodes.contains_key(&nid) || self.nodes[&nid].blocked {
continue;
}
let mut pending_ors: Vec<Concept> = self.nodes[&nid]
.labels
.iter()
.filter(|l| matches!(l, Concept::Or(_)))
.filter(|l| !self.nodes[&nid].processed.contains(l))
.cloned()
.collect();
pending_ors.sort_unstable();
for or_concept in pending_ors {
if let Concept::Or(ref disjuncts) = or_concept {
let already_has = disjuncts
.iter()
.any(|d| self.nodes[&nid].labels.contains(d));
if already_has {
self.nodes
.get_mut(&nid)
.unwrap()
.processed
.insert(or_concept);
continue;
}
// Branch: try each disjunct
self.nodes
.get_mut(&nid)
.unwrap()
.processed
.insert(or_concept.clone());
let or_dep = self.label_dep(nid, &or_concept);
let choice = self.next_choice;
self.next_choice += 1;
// Why every disjunct failed, less this choice itself.
let mut failed = or_dep.clone();
for disjunct in disjuncts {
let mut branch = self.clone();
branch.open.push(choice);
branch.nondeterministic = true;
let mut d = or_dep.clone();
d.insert(choice);
branch.ctx = d;
branch.add_label(nid, disjunct.clone());
branch.ctx = branch.all_open();
if branch.expand(depth + 1) {
// Only the model emitter asks for the graph back. See
// `Tableau::capture`.
if self.capture {
*self = branch;
} else {
self.nondeterministic = true;
}
return true;
}
// Same here: an exhausted disjunct is not a refuted one.
self.budget.exhausted |= branch.budget.exhausted;
if self.budget.stopped_by.is_none() {
self.budget.stopped_by = branch.budget.stopped_by;
}
// Backjump: a clash that does not depend on this
// choice would recur under every other disjunct.
if !branch.fail_dep.contains(&choice) {
self.fail_dep = branch.fail_dep;
return false;
}
failed.extend(branch.fail_dep.iter().copied().filter(|&c| c != choice));
}
self.fail_dep = failed;
return false; // All branches clash
}
}
}
// Check disjointness constraints
let mut disjoint_clash: Option<Dep> = None;
let mut by_id: Vec<u32> = self.nodes.keys().copied().collect();
by_id.sort_unstable();
for (a, b) in &self.tbox.disjoint_pairs {
for node in by_id.iter().map(|id| &self.nodes[id]) {
if node.blocked {
continue;
}
if node.labels.contains(a) && node.labels.contains(b) {
self.trace
.record(&format!("Clash: disjoint concepts {:?} and {:?}", a, b));
disjoint_clash = Some(node.deps_of([a, b]).unwrap_or_else(|| self.all_open()));
break;
}
}
if disjoint_clash.is_some() {
break;
}
}
if let Some(d) = disjoint_clash {
self.fail_dep = d;
return false;
}
true // Complete, clash-free
}
/// The first clash on an unblocked node, with the choice points it
/// depends on. Nodes are visited in id order so the answer does not depend
/// on `HashMap` iteration.
fn clash(&self) -> Option<Dep> {
let mut ids: Vec<u32> = self.nodes.keys().copied().collect();
ids.sort_unstable();
for id in ids {
let n = &self.nodes[&id];
if n.blocked {
continue;
}
if let Some(d) = n.clash_dep() {
return Some(d.unwrap_or_else(|| self.all_open()));
}
if let Some(d) = self.card_clash_via_hierarchy(n) {
return Some(d.unwrap_or_else(|| self.all_open()));
}
}
None
}
/// ≥n1 R.C against ≤n2 R.D where n1 > n2 and C ⊑ D.
///
/// `TNode::has_clash` only fires when the two fillers are syntactically equal
/// or the max's filler is ⊤. That misses the common shape where a class
/// asserts ≥2 R.C while inheriting ≤1 R.D from an ancestor with C ⊑ D: every
/// C-successor is also a D-successor, so the bound is violated and the class
/// is unsatisfiable.
///
/// Measured on the GCHQ-published hqdm.owl, whose 39 unsatisfiable classes
/// are all of this shape. Ablating its cardinality axioms takes the count to
/// 0, while ablating rdfs:domain, rdfs:range or owl:disjointWith each leave
/// all 39 standing.
fn card_clash_via_hierarchy(&self, n: &TNode) -> Option<Option<Dep>> {
let subsumed = |a: &Concept, b: &Concept| -> bool {
match (a, b) {
(Concept::Atom(x), Concept::Atom(y)) => {
x == y
|| self
.tbox
.class_closure
.get(x)
.is_some_and(|anc| anc.contains(y))
}
_ => false,
}
};
let mut sorted: Vec<&Concept> = n.labels.iter().collect();
sorted.sort_unstable();
for &label in &sorted {
let (r1, n1, f1) = match label {
Concept::MinCard(r, k, f) => (*r, *k, f.as_ref()),
Concept::Exists(r, f) => (*r, 1u32, f.as_ref()),
_ => continue,
};
for &other in &sorted {
if let Concept::MaxCard(r2, n2, f2) = other
&& r1 == *r2
&& n1 > *n2
&& subsumed(f1, f2)
{
return Some(n.deps_of([label, other]));
}
}
}
None
}
/// Applies pairwise ANYWHERE blocking to every node, and marks the
/// descendants of a blocked node indirectly blocked.
///
/// The blocker used to have to be an ANCESTOR. On an EL ontology with long
/// chains of existentials over distinct classes (ORE 2015 `ore_ont_11497`,
/// an anatomy ontology whose developmental stages are each `preceded_by`
/// the last, with about three existentials per class) no ancestor ever
/// repeats a label before the chain ends, so every distinct path was
/// expanded separately and the tree grew exponentially with the chain's
/// depth: 21 s, one class undetermined, and a different answer on each run
/// as the budget fell in a different place. Anywhere blocking lets ANY
/// earlier node with the same pairwise signature block, so each signature
/// is expanded once. It is sound for SHIQ with the pairwise condition
/// below (Motik, Shearer and Horrocks, *Hypertableau Reasoning for
/// Description Logics*, JAIR 36, 2009, section 5), and it is what HermiT
/// does.
///
/// Nodes are visited in id order, which is creation order, so a blocker is
/// always older than the node it blocks and never its descendant. Only an
/// unblocked, blockable node goes into the index, so no blocker is itself
/// blocked. A node whose parent is blocked, directly or indirectly, is
/// indirectly blocked and gets no rule, which is what makes the unravelled
/// model well defined. A merge can point a node at a parent with a larger
/// id; that parent's status is not yet known when the child is visited, so
/// the child is simply not treated as indirectly blocked. Blocking less only
/// costs expansion, never soundness.
fn update_blocking(&mut self) {
let mut node_ids: Vec<u32> = self.nodes.keys().copied().collect();
node_ids.sort_unstable();
let mut blocked_now: HashSet<u32> = HashSet::new();
let mut decided: HashMap<u32, Option<u32>> = HashMap::new();
let mut index: HashMap<Vec<Concept>, Vec<u32>> = HashMap::new();
for &nid in &node_ids {
let node = &self.nodes[&nid];
let Some(parent) = node.parent else {
// A root is never blocked and never blocks.
decided.insert(nid, None);
continue;
};
if blocked_now.contains(&parent) {
blocked_now.insert(nid);
decided.insert(nid, None);
continue;
}
let mut sig: Vec<Concept> = node.labels.iter().cloned().collect();
sig.sort_unstable();
let blocker = index
.get(&sig)
.and_then(|cands| cands.iter().copied().find(|&t| self.pairwise_blocks(t, nid)));
match blocker {
Some(t) => {
blocked_now.insert(nid);
decided.insert(nid, Some(t));
}
None => {
decided.insert(nid, None);
index.entry(sig).or_default().push(nid);
}
}
}
for (nid, blocker) in decided {
let n = self.nodes.get_mut(&nid).unwrap();
n.blocked = blocked_now.contains(&nid);
n.blocker = blocker;
}
}
/// Whether `t` blocks `s` under the pairwise condition, labels of the two
/// nodes already known to be equal.
///
/// Horrocks and Sattler, *A Tableau Decision Procedure for SHOIQ* (JAR 39,
/// 2007): once a logic has BOTH inverse roles and number restrictions,
/// single-node blocking is not sound, because unravelling replicates the
/// fragment between a blocked node and its blocker, and with inverse roles a
/// node constrains its predecessor, so the contexts have to match too. For
/// `s` a blockable successor of `s'` and `t` one of `t'`, `t` blocks `s`
/// iff `L(s) = L(t)`, `L(s') = L(t')`, `L(s,s') = L(t,t')` and
/// `L(s',s) = L(t',t)`. Equality, not inclusion.
fn pairwise_blocks(&self, t: u32, s: u32) -> bool {
let (Some(sn), Some(tn)) = (self.nodes.get(&s), self.nodes.get(&t)) else {
return false;
};
let (Some(sp), Some(tp)) = (sn.parent, tn.parent) else {
return false;
};
let (Some(spn), Some(tpn)) = (self.nodes.get(&sp), self.nodes.get(&tp)) else {
return false;
};
t < s
&& tn.labels == sn.labels
&& tpn.labels == spn.labels
&& self.roles_between(tp, t) == self.roles_between(sp, s)
&& self.roles_between(t, tp) == self.roles_between(s, sp)
}
/// The set of roles labelling the edge from `from` to `to`.
fn roles_between(&self, from: u32, to: u32) -> BTreeSet<u32> {
match self.nodes.get(&from) {
Some(n) => n
.edges
.iter()
.filter(|(_, targets)| targets.contains(&to))
.map(|(r, _)| *r)
.collect(),
None => BTreeSet::new(),
}
}
/// The node that directly blocks `s`, as `update_blocking` last decided.
/// Split out so that the model emitter can fold a blocked node into the
/// node that blocks it, which is the only way a completion graph with
/// blocking becomes a finite interpretation. One decision, one place: the
/// emitter reads the blocker the expansion used rather than recomputing
/// one under a condition that could drift from it.
fn blocker_of(&self, s: u32) -> Option<u32> {
self.nodes.get(&s).and_then(|n| n.blocker)
}
}
// ── DL Reasoner (Public API) ────────────────────────────────────────────
pub struct DlReasoner {
interner: Interner,
tbox: Arc<ProcessedTBox>,
named_classes: HashSet<u32>,
thing_id: u32,
nothing_id: u32,
individual_types: HashMap<u32, HashSet<u32>>,
individual_anon_types: HashMap<u32, Vec<Concept>>,
role_assertions: Vec<(u32, u32, u32)>,
data_assertions: Vec<(u32, u32, u32)>,
definitions: HashMap<u32, Concept>,
/// Sub-class closure over asserted rdfs:subClassOf, used by realization.
subclass_closure: HashMap<u32, HashSet<u32>>,
/// How LONG a phase of the run may take, in milliseconds. `None` means no
/// time limit (the node/depth budgets still apply).
///
/// A DURATION, not an instant, and the difference was a defect. This used to
/// hold one `Instant` computed when the reasoner was CONSTRUCTED, shared by
/// the satisfiability sweep, the subsumption sweep and the ABox check. One
/// shared instant is not a per-test budget and it is not a per-phase budget:
/// it is a budget for the whole run, handed out oldest-first. A
/// classification that used the clock up left the ABox check starting already
/// expired, and it reported `undecided` on an ABox it decides in
/// microseconds. Honest, but a loaded machine silently degraded an answer
/// that was there for the taking, and the output gave a reader no way to see
/// that classification was what spent it.
///
/// Each phase now opens its own from this duration, and no cap was raised:
/// the number is unchanged and the node and depth caps are untouched. Which
/// phase ran out is reported in `budget_exhausted_in`. See `phase_deadline`
/// for why the unit is a phase rather than a single test, which is what the
/// setting's own name says, and `phase_deadline_within` for how
/// `classify_timeout_ms` is intersected into it so that no phase can outlive
/// the run's ceiling.
budget_ms: Option<u64>,
/// The axioms as the OWL parser read them, before `ProcessedTBox` absorbed,
/// rewrote and folded them. A model certificate is written against these, so
/// that what the checker verifies is the ontology's own axioms rather than
/// the reasoner's internal encoding of them.
source: Arc<AxiomSource>,
}
/// The parsed axioms, kept whole for the model emitter.
///
/// `ProcessedTBox` is a compilation target: it absorbs atomic left-hand sides
/// into `concept_defs`, turns the rest into `¬C ⊔ D`, splits disjunctive
/// left-hand sides and lifts domain and range out of the axiom list entirely.
/// Certifying a model against THAT would certify the reasoner's encoding
/// against itself. This is the input to that compilation, kept so the checker
/// can be pointed at the axioms instead.
struct AxiomSource {
axioms: Vec<(Concept, Concept)>,
disjoint_pairs: Vec<(Concept, Concept)>,
role_domains: Vec<(u32, Concept)>,
role_ranges: Vec<(u32, Concept)>,
sub_to_super: HashMap<u32, HashSet<u32>>,
transitive_roles: HashSet<u32>,
inverse_roles: HashMap<u32, u32>,
functional_roles: HashSet<u32>,
inv_functional_roles: HashSet<u32>,
}
impl DlReasoner {
pub fn from_graph(graph: &Arc<GraphStore>) -> anyhow::Result<Self> {
let triples = graph.all_triples()?;
let parser = OwlParser::new(triples);
let mut result = parser.parse();
// Transitive closure of asserted CLASS subsumption, so an individual typed
// EnumerationTerm satisfies a conjunct requiring ClassTerm.
//
// Built from the axiom list, not from `sub_to_super`: that map is the ROLE hierarchy
// (rdfs:subPropertyOf). Using it here silently produced an empty class closure and
// no individual ever matched a definition naming a superclass.
let mut direct: HashMap<u32, HashSet<u32>> = HashMap::new();
for (sub, sup) in &result.axioms {
if let (Concept::Atom(a), Concept::Atom(b)) = (sub, sup)
&& a != b {
direct.entry(*a).or_default().insert(*b);
}
}
let mut closure: HashMap<u32, HashSet<u32>> = HashMap::new();
for sub in direct.keys().copied().collect::<Vec<_>>() {
let mut seen: HashSet<u32> = HashSet::new();
let mut stack: Vec<u32> = direct.get(&sub).map(|v| v.iter().copied().collect()).unwrap_or_default();
while let Some(x) = stack.pop() {
if seen.insert(x)
&& let Some(next) = direct.get(&x) {
stack.extend(next.iter().copied());
}
}
closure.insert(sub, seen);
}
let source = Arc::new(AxiomSource {
axioms: result.axioms.clone(),
disjoint_pairs: result.disjoint_pairs.clone(),
role_domains: result.role_domains.clone(),
role_ranges: result.role_ranges.clone(),
sub_to_super: result.sub_to_super.clone(),
transitive_roles: result.transitive_roles.clone(),
inverse_roles: result.inverse_roles.clone(),
functional_roles: result.functional_roles.clone(),
inv_functional_roles: result.inv_functional_roles.clone(),
});
let tbox = Arc::new(ProcessedTBox::new(
&result.axioms,
&result.disjoint_pairs,
RoleAxioms {
transitive_roles: result.transitive_roles,
sub_to_super: &result.sub_to_super,
inverse_roles: result.inverse_roles,
functional_roles: &result.functional_roles,
inv_functional_roles: &result.inv_functional_roles,
role_domains: &result.role_domains,
role_ranges: &result.role_ranges,
},
&mut result.interner,
));
Ok(Self {
interner: result.interner,
tbox,
named_classes: result.named_classes,
thing_id: result.thing_id,
nothing_id: result.nothing_id,
individual_types: result.individual_types,
individual_anon_types: result.individual_anon_types,
role_assertions: result.role_assertions,
data_assertions: result.data_assertions,
definitions: result.definitions,
subclass_closure: closure,
budget_ms: crate::runtime::tableaux_test_timeout_ms(),
source,
})
}
/// A fresh cut-off for a PHASE that is about to start, counted from now.
///
/// Call this once when a phase begins and hand the result to every tableau
/// in that phase. Never store it on the reasoner: storing it is exactly what
/// made the ABox check start on whatever the classification had left.
///
/// A phase, not a test, and the distinction is a deliberate cost decision
/// rather than a reading of the setting's name. `tableaux_test_timeout_ms`
/// does say "a single tableau satisfiability test", and minting it per
/// tableau is the literal reading — but the two sweeps run one tableau per
/// class and one per ORDERED PAIR of classes, and the shape that bounds them
/// as a whole is a budget per sweep rather than one per test. Minting per
/// tableau is also what would make `classify_timeout_ms` the bound that
/// fires, since with 10s per tableau a sweep runs until the 180s ceiling
/// stops it — and it costs what it says
/// it costs: MEASURED on this machine, a 20-ontology corpus went from 67s to
/// over 600s, with the five ontologies that hit the cap moving from ~10s each
/// to ~180s each and NO change in any verdict — the same classes stayed
/// undetermined, just after eighteen times the work. Per phase fixes the
/// defect that was reported (the ABox check inheriting a spent clock) and
/// bounds the change at 3x the old worst case instead of 18x. The cost of
/// that choice is that at the defaults the ceiling is not expected to be the
/// bound that fires, and every `owl-dl` run now says which bound did fire in
/// its `budget` block rather than leaving a reader to infer it from two
/// settings and a phase count.
///
/// THAT 67s NUMBER CANNOT BE REPRODUCED FROM THIS REPOSITORY and is kept only
/// as the reason a route was abandoned. The corpus it was taken over is not
/// written down anywhere: it is not the twenty case-study ontologies, which
/// run in 0.10s and reach no budget at all, and it is not the ten hard ones,
/// of which two reach a budget rather than five. Both of those ARE written
/// down, in `tests/reasoner_budget_corpus_bench.rs`, which exists so that the
/// next person to change a budget can measure rather than cite this
/// paragraph. Cite the bench.
///
/// `classify_timeout_ms` is now a CEILING over every phase, not a fifth
/// budget beside them: see `phase_deadline_within`, which is what every
/// phase inside a run actually calls. A bare `phase_deadline` is for a
/// caller running one phase on its own with no run around it.
fn phase_deadline(&self) -> Option<Instant> {
self.budget_ms
.map(|ms| Instant::now() + std::time::Duration::from_millis(ms))
}
/// A phase budget under a run's global ceiling: whichever expires first.
///
/// This is the whole of the cheap half of making `classify_timeout_ms` real.
/// A tableau already checks ONE deadline inside its expansion loop, so
/// handing it the earlier of the two costs nothing at all — no second clock
/// read, no extra branch — while making it impossible for any phase to
/// outlive the global budget. The expensive half, minting a fresh budget per
/// TABLEAU so that the global one is what eventually stops the sweep, is what
/// took the corpus from 67s to over 600s (a number `phase_deadline` flags as
/// unreproducible) and is not what this does.
///
/// `None` on either side means "that one imposes nothing", so with the global
/// budget switched off this is the phase budget unchanged, and with the phase
/// budget switched off it is the global deadline, which is the case that used
/// to leave a sweep with no clock at all.
fn phase_deadline_within(&self, global: Option<Instant>) -> Option<Instant> {
match (self.phase_deadline(), global) {
(Some(phase), Some(global)) => Some(phase.min(global)),
(Some(phase), None) => Some(phase),
(None, global) => global,
}
}
/// The ceiling for one whole run, opened now from `classify_timeout_ms`.
///
/// Open it ONCE per run and pass it down. Opening it per phase is what made
/// the setting vacuous: four phases each opening a fresh 180s meant a run
/// could take 720s under a budget that says 180.
fn global_deadline() -> Option<Instant> {
crate::runtime::classify_timeout_ms()
.map(|ms| Instant::now() + std::time::Duration::from_millis(ms))
}
/// Three-valued satisfiability test — each call creates its own Tableau.
///
/// Returns `Unknown` when a resource budget was hit before a decision was
/// reached. Callers MUST NOT read `Unknown` as either answer.
///
/// A bare call is its own phase and gets its own budget. Inside a sweep, use
/// `decide_satisfiable_within` and pass the deadline the sweep opened with,
/// so the thousands of tableaux in one sweep share one budget rather than
/// taking one each.
pub fn decide_satisfiable(&self, concept: &Concept) -> Verdict {
self.decide_satisfiable_within(concept, self.phase_deadline())
}
/// `decide_satisfiable` against a deadline the caller already opened.
fn decide_satisfiable_within(&self, concept: &Concept, deadline: Option<Instant>) -> Verdict {
let mut tableau = Tableau::with_deadline(Arc::clone(&self.tbox), deadline);
tableau.decide(concept)
}
/// `decide_satisfiable` for a named class, keeping what its model says about
/// the class's subsumers. See `ClassModel`.
fn satisfiable_with_model(&self, cls: u32, deadline: Option<Instant>) -> (Verdict, Option<ClassModel>) {
let mut tableau = Tableau::with_deadline(Arc::clone(&self.tbox), deadline);
// The graph of the branch that succeeded is the model; without
// `capture` the ⊔-rule hands back the state before the last choice.
tableau.capture = true;
let verdict = tableau.decide(&Concept::Atom(cls));
if !matches!(verdict, Verdict::Satisfiable) {
return (verdict, None);
}
// Node 0 is the root `decide` created. A merge can in principle remove
// it, and then there is no root to read, so the class falls back to
// pairwise testing rather than being read off the wrong node.
let Some(root) = tableau.nodes.get(&0) else {
return (verdict, None);
};
let mut root_classes: Vec<u32> = root
.labels
.iter()
.filter_map(|l| match l {
Concept::Atom(a)
if *a != cls
&& *a != self.thing_id
&& *a != self.nothing_id
&& self.named_classes.contains(a) =>
{
Some(*a)
}
_ => None,
})
.collect();
root_classes.sort_unstable();
(verdict, Some(ClassModel { root_classes, deterministic: !tableau.nondeterministic }))
}
/// `decide_subsumption` against a deadline the caller already opened.
fn decide_subsumption_within(
&self,
sub: &Concept,
sup: &Concept,
deadline: Option<Instant>,
) -> Verdict {
let mut test = vec![sub.clone(), sup.negate()];
test.sort();
self.decide_satisfiable_within(&Concept::And(test), deadline)
}
/// Thread-safe satisfiability test.
///
/// Collapses `Unknown` to `true`, which is the SAFE direction: an
/// undecided class is left in the hierarchy rather than being declared
/// impossible. Prefer `decide_satisfiable` where the distinction matters.
pub fn is_satisfiable(&self, concept: &Concept) -> bool {
!self.decide_satisfiable(concept).is_unsat()
}
/// Check if sub ⊑ sup (sub is subsumed by sup).
///
/// A subsumption is asserted ONLY when the negated test concept is proven
/// unsatisfiable. `Unknown` yields `false`: we decline to claim a
/// subsumption we could not establish.
pub fn is_subsumed(&self, sub: &Concept, sup: &Concept) -> bool {
self.decide_subsumption(sub, sup).is_unsat()
}
/// Subsumption as a three-valued verdict. `Unsatisfiable` on the negated
/// test concept means the subsumption holds.
pub fn decide_subsumption(&self, sub: &Concept, sup: &Concept) -> Verdict {
let mut test = vec![sub.clone(), sup.negate()];
test.sort();
self.decide_satisfiable(&Concept::And(test))
}
/// Check TBox consistency. An undecided run reports consistent, which is
/// the safe direction: we do not condemn an ontology we failed to refute.
pub fn is_consistent(&self) -> bool {
self.is_consistent_within(Self::global_deadline())
}
/// `is_consistent` under a ceiling the caller already opened. This is the
/// first phase of a run and used to be outside the global budget entirely.
pub fn is_consistent_within(&self, global: Option<Instant>) -> bool {
!self
.decide_satisfiable_within(&Concept::Top, self.phase_deadline_within(global))
.is_unsat()
}
/// Explain why a class is unsatisfiable. Returns None if satisfiable.
pub fn explain_unsatisfiable(&self, class_id: u32) -> Option<Vec<String>> {
self.explain_unsatisfiable_within(class_id, self.phase_deadline())
}
/// `explain_unsatisfiable` against a deadline the caller already opened.
///
/// `Tableau::new_with_tracing` left `Budget::deadline` at `None`, so an
/// explanation was the one tableau in this engine that ran under no
/// wall-clock budget at all — and `run` performs one per unsatisfiable
/// class, in a loop, immediately after a classification that may have been
/// cut short for want of exactly that budget. The node and depth caps still
/// applied; nothing stopped the branching.
///
/// An expired deadline yields `None`, which is the honest degradation: the
/// tableau returns `Unknown`, and `Unknown` is not a proof of
/// unsatisfiability, so there is no clash trace to report.
pub fn explain_unsatisfiable_within(
&self,
class_id: u32,
deadline: Option<Instant>,
) -> Option<Vec<String>> {
let concept = Concept::Atom(class_id);
let mut tableau = Tableau::new_with_tracing(Arc::clone(&self.tbox));
tableau.budget.deadline = deadline;
if !tableau.decide(&concept).is_unsat() {
return None;
}
Some(tableau.trace.steps)
}
/// Check subsumption with explanation trace.
pub fn check_subsumption_explained(
&self,
sub: &Concept,
sup: &Concept,
) -> (bool, Vec<String>) {
let mut test = vec![sub.clone(), sup.negate()];
test.sort();
let test_concept = Concept::And(test);
let mut tableau = Tableau::new_with_tracing(Arc::clone(&self.tbox));
let verdict = tableau.decide(&test_concept);
(verdict.is_unsat(), tableau.trace.steps)
}
/// Compute told-subsumer transitive closure (for pruning).
fn compute_told_subsumers(&self) -> HashMap<u32, HashSet<u32>> {
let mut told: HashMap<u32, HashSet<u32>> = HashMap::new();
for (&cls, defs) in &self.tbox.concept_defs {
for def in defs {
if let Concept::Atom(sup) = def {
told.entry(cls).or_default().insert(*sup);
}
}
}
let mut changed = true;
while changed {
changed = false;
let keys: Vec<u32> = told.keys().copied().collect();
for cls in keys {
let supers: Vec<u32> = told
.get(&cls)
.cloned()
.unwrap_or_default()
.into_iter()
.collect();
for sup in supers {
if let Some(grand) = told.get(&sup).cloned() {
for g in grand {
if told.entry(cls).or_default().insert(g) {
changed = true;
}
}
}
}
}
}
told
}
/// Agent-based parallel classification using rayon worker pool.
///
/// Phase 1 — Satisfiability Agent: parallel sat testing for all named classes.
/// Phase 2 — Subsumption Agent: parallel pairwise subsumption with told-pruning.
/// Phase 3 — Equivalence detection from mutual subsumptions.
pub fn classify_parallel(&self) -> AgentClassificationResult {
self.classify_parallel_within(Self::global_deadline())
}
/// `classify_parallel` under a ceiling the caller already opened, so that
/// classification and the phases around it share ONE global budget instead
/// of opening one each.
pub fn classify_parallel_within(
&self,
global_deadline: Option<Instant>,
) -> AgentClassificationResult {
let start = Instant::now();
// Sorted for the same reason as the node traversals: `named_classes` is a
// HashSet, so its iteration order is seeded per process. That order fixes
// the order of `satisfiable`, which fixes the order of `pairs`, which
// decides which subsumption checks are reached before a budget runs out.
// Unsorted, classification is not a function of the ontology alone.
let mut classes: Vec<u32> = self
.named_classes
.iter()
.filter(|&&c| c != self.thing_id && c != self.nothing_id)
.copied()
.collect();
classes.sort_unstable();
// The ceiling for the whole run, opened by the caller.
//
// The per-test deadline bounds one satisfiability check. It does not
// bound classification, which runs one check per class plus one per
// ordered pair of classes. On the Pizza ontology that is ~100 classes
// and ~10,000 pairs; at the 10s per-test budget the worst case is over
// a day. A global deadline is what actually stops that.
//
// It is folded into each phase's own deadline by `phase_deadline_within`,
// and that folded deadline is checked at the head of each task, which is
// the cheap place, AND inside every tableau, which is the place that
// makes it a ceiling rather than a suggestion. The head-of-task check
// used to read the GLOBAL deadline alone (#340). A tableau opened after
// its phase deadline returns `Unknown` from its first step, so every
// task reached after the phase ran out still paid for building one, and
// with an undetermined class contributing a pair for every satisfiable
// class the sweep ran for 26 times its phase budget on nothing but
// those. Checking the folded deadline skips exactly the tableaux that
// could only have returned `Unknown`, so no verdict changes.
let expired = |d: Option<Instant>| d.is_some_and(|d| Instant::now() >= d);
// ── Satisfiability Agent ─────────────────────────────────────
let sat_start = Instant::now();
// One budget for this phase, opened here. The subsumption sweep below
// opens its own, and `check_abox` opens a third when it runs. Before
// that, all three drew on a single instant fixed when the reasoner was
// constructed, so whichever phase ran first spent the clock and the ABox
// check — which runs last and is the one a user reads for their own data
// — routinely reported `undecided` on an ABox it decides in microseconds.
let sat_deadline = self.phase_deadline_within(global_deadline);
let sat_full: Vec<(u32, Verdict, Option<ClassModel>)> = classes
.par_iter()
.map(|&cls| {
if expired(sat_deadline) {
// Budget gone: report Unknown rather than guessing. This is
// the verdict the tableau would return from its first step.
return (cls, Verdict::Unknown, None);
}
let (verdict, model) = self.satisfiable_with_model(cls, sat_deadline);
(cls, verdict, model)
})
.collect();
let sat_results: Vec<(u32, Verdict)> = sat_full.iter().map(|(c, v, _)| (*c, *v)).collect();
// Only PROVEN unsatisfiable classes go in the unsatisfiable list.
// Classes we ran out of budget on are undetermined, and are kept in
// the satisfiable set for downstream subsumption testing so they stay
// in the hierarchy rather than silently vanishing.
let satisfiable: Vec<u32> = sat_results
.iter()
.filter(|(_, v)| !v.is_unsat())
.map(|(c, _)| *c)
.collect();
// Reported separately from `satisfiable`. That vector deliberately carries
// the undetermined classes so they stay in the hierarchy for the
// subsumption sweep, but counting them as "satisfiable_found" in the
// output claims a proof that was never constructed. On a 234-class
// ontology where every class is undetermined, the old field read
// "satisfiable_found: 234", which is indistinguishable from a coherent
// result.
let proven_satisfiable = sat_results
.iter()
.filter(|(_, v)| matches!(v, Verdict::Satisfiable))
.count();
let unsatisfiable: Vec<u32> = sat_results
.iter()
.filter(|(_, v)| v.is_unsat())
.map(|(c, _)| *c)
.collect();
let undetermined: Vec<u32> = sat_results
.iter()
.filter(|(_, v)| matches!(v, Verdict::Unknown))
.map(|(c, _)| *c)
.collect();
let sat_clock = if undetermined.is_empty() {
None
} else {
expired_clock(sat_deadline, global_deadline)
};
let sat_time = sat_start.elapsed();
// ── Subsumption Agent ────────────────────────────────────────
let sub_start = Instant::now();
let told = self.compute_told_subsumers();
// What each class's own model already settles, and the pairs left to
// test. See `ClassModel`: a named class missing from the root label of
// a model of `A` is a proven non-subsumer and is never tested; when the
// model was built with no choice, every named class in the root label
// is a proven subsumer and is not tested either. Only a class with no
// model (undetermined) falls back to testing every pair, which is what
// every class used to do.
//
// That fallback is NOT written out pair by pair (#340). `k` classes with
// no model against `n` satisfiable ones is `k x n` pairs, 27 million on
// a 6,000-class ontology whose satisfiability phase ran out, and the old
// sweep materialised every one, then a verdict for every one. A row
// with no model now carries only its class and a count, and its
// candidates are generated while the phase budget lasts; whatever the
// budget does not reach is counted undetermined in bulk.
let sat_set: HashSet<u32> = satisfiable.iter().copied().collect();
let mut rows: Vec<PairRow<'_>> = Vec::new();
let mut from_models: Vec<(u32, u32)> = Vec::new();
for (sub, verdict, model) in &sat_full {
if verdict.is_unsat() {
continue;
}
let told_sup = |sup: u32| told.get(sub).is_some_and(|s| s.contains(&sup));
match model {
Some(m) => {
let mut listed = Vec::new();
for &sup in &m.root_classes {
if !sat_set.contains(&sup) || told_sup(sup) {
continue;
}
if m.deterministic {
from_models.push((*sub, sup));
} else {
listed.push(sup);
}
}
if !listed.is_empty() {
rows.push(PairRow::listed(*sub, listed));
}
}
None => {
rows.push(PairRow::every(*sub, &satisfiable, &sat_set, told.get(sub)));
}
}
}
// This phase's own budget, opened now rather than inherited from the
// satisfiability sweep that just finished.
let sub_deadline = self.phase_deadline_within(global_deadline);
let sweep = sweep_pairs(
&rows,
|| expired(sub_deadline),
|sub, sup| {
self.decide_subsumption_within(
&Concept::Atom(sub),
&Concept::Atom(sup),
sub_deadline,
)
},
);
let pairs_scheduled: usize = rows.iter().map(|r| r.count).sum();
let subsumptions_from_models = from_models.len();
let mut inferred = from_models;
inferred.extend(sweep.inferred);
let undetermined_pairs = sweep.undetermined;
let pairs_not_reached = sweep.not_reached;
let pairs_tested = sweep.tested;
let subsumption_cut_short = !undetermined_pairs.is_empty() || pairs_not_reached > 0;
let sub_clock = if subsumption_cut_short {
expired_clock(sub_deadline, global_deadline)
} else {
None
};
let sub_time = sub_start.elapsed();
// Build hierarchy (told + inferred)
let mut hierarchy: HashMap<u32, HashSet<u32>> = HashMap::new();
for (&cls, supers) in &told {
if sat_set.contains(&cls) {
for &sup in supers {
if sat_set.contains(&sup) {
hierarchy.entry(cls).or_default().insert(sup);
}
}
}
}
for (sub, sup) in &inferred {
hierarchy.entry(*sub).or_default().insert(*sup);
}
// Detect equivalences
let mut equivalences: Vec<(u32, u32)> = Vec::new();
for (&a, a_supers) in &hierarchy {
for &b in a_supers {
if a < b
&& hierarchy.get(&b).is_some_and(|bs| bs.contains(&a)) {
equivalences.push((a, b));
}
}
}
let total_time = start.elapsed();
AgentClassificationResult {
hierarchy,
unsatisfiable,
undetermined,
subsumption_cut_short,
undetermined_pairs,
pairs_not_reached,
pairs_scheduled,
satisfiability_clock: sat_clock,
subsumption_clock: sub_clock,
subsumptions_from_models,
equivalences,
inferred_subsumptions: inferred.len(),
agents: AgentMetrics {
satisfiability: AgentTaskMetrics {
tasks: classes.len(),
results: proven_satisfiable,
time_ms: sat_time.as_millis() as u64,
},
subsumption: AgentTaskMetrics {
tasks: pairs_tested,
results: inferred.len(),
time_ms: sub_time.as_millis() as u64,
},
total_time_ms: total_time.as_millis() as u64,
parallel_workers: rayon::current_num_threads(),
},
}
}
/// ABox Agent: check individual consistency and infer types.
/// Realize individuals into classes that are DEFINED by an owl:equivalentClass axiom.
///
/// `check_abox` reads concept labels off one completed tableau. That is sound for
/// detecting inconsistency but it is not realization: a concept satisfied in the single
/// model the expansion happened to find is not thereby entailed, and the branch that
/// would have added a defined class is usually not the branch recorded. The practical
/// consequence was that a class defined by owl:equivalentClass stayed permanently empty,
/// so the whole idiom of defining a class and letting the reasoner find its members did
/// not work at all.
///
/// Full realization would test, for every individual and every class, whether asserting
/// the negated class makes the ABox inconsistent. That is one tableau expansion over the
/// entire ABox per pair, which is not affordable: a few thousand individuals against a
/// few dozen classes is tens of thousands of full expansions.
///
/// This instead matches definitions structurally against asserted facts, which is linear
/// in individuals and is complete for the fragment it accepts: a conjunction whose
/// conjuncts are named classes and existential restrictions whose filler is a named class
/// or a nominal. That covers `owl:hasValue` and `owl:someValuesFrom` inside an
/// `owl:intersectionOf`, which is how defined classes are written in practice. Anything
/// outside the fragment is declined rather than guessed at, so a definition using
/// negation, cardinality or a nested anonymous class yields no members here rather than
/// wrong ones. Cardinality-based definitions in particular are closed-world questions and
/// belong in SHACL.
fn realize_definitions(&self) -> HashMap<u32, HashSet<u32>> {
let mut out: HashMap<u32, HashSet<u32>> = HashMap::new();
if std::env::var("OO_DEBUG_REALIZE").is_ok() {
eprintln!("[realize] definitions={} individuals={} roles={}",
self.definitions.len(), self.individual_types.len(), self.role_assertions.len());
for (c, d) in &self.definitions {
eprintln!("[realize] {} := {:?}", self.interner.resolve(*c), d);
}
}
if self.definitions.is_empty() {
return out;
}
// role assertions indexed by subject for a linear scan per individual
let mut by_subject: HashMap<u32, Vec<(u32, u32)>> = HashMap::new();
for &(a, r, b) in &self.role_assertions {
by_subject.entry(a).or_default().push((r, b));
}
for &(a, r, b) in &self.data_assertions {
by_subject.entry(a).or_default().push((r, b));
}
// Every individual, not only the ones carrying a NAMED rdf:type.
//
// This used to iterate `individual_types`, which is keyed by exactly
// those. An individual with no rdf:type at all — named only by its own
// role assertions — and an individual typed ONLY by an anonymous class
// expression both have no entry there, so neither was ever realized into
// a defined class however completely it met the definition.
// `build_abox_tableau` has given both a node for some time, because a
// domain constraint binds them and a disjointness axiom can refute them:
// the consistency check saw them and the realizer did not.
//
// The universe is built the same way `build_abox_tableau` builds its
// node set, so the individuals realization considers and the individuals
// the consistency check ran on are one set rather than two that can
// drift. Widening it cannot widen what counts as a match: `satisfies`
// declines everything outside its fragment, so an empty named-type set
// can only fail to match.
let mut individuals: Vec<u32> = self.individual_types.keys().copied().collect();
for &ind in self.individual_anon_types.keys() {
if !self.individual_types.contains_key(&ind) {
individuals.push(ind);
}
}
for &(a, _, b) in &self.role_assertions {
individuals.push(a);
individuals.push(b);
}
individuals.sort_unstable();
individuals.dedup();
let empty: HashSet<u32> = HashSet::new();
for ind in individuals {
// Conjuncts of an anonymous rdf:type are assertions in their own
// right, and the atomic ones are named types this individual has
// exactly as if they had been written as an ordinary rdf:type.
let asserted = self.asserted_concepts(ind);
let declared = self.individual_types.get(&ind).unwrap_or(&empty);
// Borrowed unless an anonymous type actually contributes a named
// one. Widening the universe to every individual means this runs
// once per individual rather than once per TYPED individual, and a
// SKOS vocabulary is tens of thousands of individuals with no
// anonymous type at all; a HashSet clone each would be a real cost
// for nothing.
let types: std::borrow::Cow<'_, HashSet<u32>> =
if asserted.iter().any(|c| matches!(c, Concept::Atom(_))) {
std::borrow::Cow::Owned(
declared
.iter()
.copied()
.chain(asserted.iter().filter_map(|c| match c {
Concept::Atom(a) => Some(*a),
_ => None,
}))
.collect(),
)
} else {
std::borrow::Cow::Borrowed(declared)
};
for (&cls, def) in &self.definitions {
if types.contains(&cls) {
continue;
}
if self.satisfies(ind, &types, &asserted, def, &by_subject) {
out.entry(ind).or_default().insert(cls);
}
}
}
out
}
/// Every concept `ind` is DIRECTLY asserted to belong to by an anonymous
/// `rdf:type`, flattened through conjunction.
///
/// `x rdf:type C ⊓ D` entails `x rdf:type C` and `x rdf:type D`, so each
/// conjunct is an assertion on its own. Nothing else is unfolded: no axiom is
/// applied and no subsumption is followed here, so this stays a reading of
/// what the graph SAYS rather than an inference from it, which is the same
/// discipline the rest of this function keeps.
fn asserted_concepts(&self, ind: u32) -> Vec<Concept> {
let mut out = Vec::new();
let Some(anon) = self.individual_anon_types.get(&ind) else {
return out;
};
let mut stack: Vec<Concept> = anon.clone();
while let Some(c) = stack.pop() {
match c {
Concept::And(parts) => stack.extend(parts),
other => out.push(other),
}
}
out
}
/// True when the asserted facts about `ind` entail `concept`, for the accepted fragment.
/// Returns false for anything outside it, which keeps unsupported definitions empty
/// rather than unsound.
///
/// `types` is the individual's named types, `asserted` the conjuncts of its
/// anonymous ones. Either may be empty; an individual with neither is decided
/// entirely on its role assertions, which is the whole point of considering it.
fn satisfies(
&self,
ind: u32,
types: &HashSet<u32>,
asserted: &[Concept],
concept: &Concept,
by_subject: &HashMap<u32, Vec<(u32, u32)>>,
) -> bool {
// An assertion discharges the conjunct it is spelled the same as. Both
// sides are in NNF and come from the same interner, so structural
// equality here is concept identity, and `x : C` entails `C` for any `C`
// whatever — including the shapes the match below declines.
if asserted.iter().any(|a| a == concept) {
return true;
}
match concept {
Concept::Top => true,
Concept::Atom(c) => self.has_type(types, *c),
Concept::And(parts) => parts
.iter()
.all(|p| self.satisfies(ind, types, asserted, p, by_subject)),
Concept::Exists(role, filler) => {
let Concept::Atom(target) = **filler else {
return false;
};
by_subject.get(&ind).is_some_and(|edges| {
edges.iter().any(|&(r, o)| {
if !self.role_matches(r, *role) {
return false;
}
// nominal: the filler names the object itself
// class filler: the object is typed by it
o == target
|| self
.individual_types
.get(&o)
.is_some_and(|ot| self.has_type(ot, target))
})
})
}
_ => false,
}
}
fn has_type(&self, types: &HashSet<u32>, target: u32) -> bool {
types.contains(&target)
|| types.iter().any(|t| {
self.subclass_closure
.get(t)
.is_some_and(|sups| sups.contains(&target))
})
}
fn role_matches(&self, asserted: u32, required: u32) -> bool {
asserted == required
|| self
.tbox
.super_to_sub
.get(&required)
.is_some_and(|subs| subs.contains(&asserted))
}
/// Build the single tableau the ABox check runs on, with one node per named
/// individual and the asserted role assertions as edges.
///
/// Extracted verbatim out of `check_abox` so the model emitter runs on the
/// SAME graph the consistency answer came from. Two copies of this setup
/// would let the certificate drift away from the verdict it is supposed to
/// certify, which is precisely the failure this whole layer exists to catch.
///
/// Returns the tableau, the individual-to-node map, and the number of
/// individuals the check actually ran on, which is one per node in that map.
///
/// That count USED TO BE the number of individuals carrying a type, taken
/// before the nodes for role-assertion endpoints were added, so it undercounted
/// by exactly the individuals this reasoner had the least information about. It
/// is a reported number a reader uses to sanity-check that the check saw their
/// data, and a node that can carry a label, a GCI and a clash has been checked
/// whatever its `rdf:type` says. It matters more now: an untyped subject of a
/// role assertion is a node that a domain constraint binds and a disjointness
/// axiom can refute, and reporting `individuals_checked: 0` for an ABox made
/// entirely of those also suppressed the whole `abox` block from the output.
fn build_abox_tableau(&self, global: Option<Instant>) -> (Tableau, HashMap<u32, u32>, usize) {
// The ABox check builds ONE tableau containing every named individual,
// so it is the largest single expansion the reasoner ever performs and it
// must be under a budget, or it is an unbounded hole in one. It opens its
// OWN, which is the point of `phase_deadline`: sharing an instant with
// classification is what had this phase reporting `undecided` on ABoxes
// it decides in microseconds, because classification had already spent it.
let mut tableau =
Tableau::with_deadline(Arc::clone(&self.tbox), self.phase_deadline_within(global));
let mut ind_to_node: HashMap<u32, u32> = HashMap::new();
// Create nodes for each individual carrying a named-class OR an anonymous
// class type. An individual typed only by an anonymous class expression
// (`:a rdf:type [ owl:Restriction … ]`) has no entry in individual_types,
// and dropping it here is how a restriction-borne inconsistency was missed.
let mut all_individuals: Vec<u32> = self.individual_types.keys().copied().collect();
for &ind in self.individual_anon_types.keys() {
if !self.individual_types.contains_key(&ind) {
all_individuals.push(ind);
}
}
all_individuals.sort_unstable();
// Counted at the end, off `ind_to_node`, not here off `all_individuals`.
for ind in all_individuals {
let node_id = tableau.fresh_node(None, None);
ind_to_node.insert(ind, node_id);
if let Some(types) = self.individual_types.get(&ind) {
for &cls in types {
tableau.add_label(node_id, Concept::Atom(cls));
}
}
// Anonymous class expressions the individual is directly typed by.
if let Some(anon) = self.individual_anon_types.get(&ind) {
for concept in anon {
tableau.add_label(node_id, concept.clone());
}
}
// The nominal {a} is approximated as the atomic concept named by a's own IRI
// (see RawConcept::Named). That approximation only works if a's node actually
// carries that atom: without it an owl:hasValue restriction can never be
// satisfied, so every class DEFINED by one stays empty and no individual is
// ever realized into it.
tableau.add_label(node_id, Concept::Atom(ind));
// Add GCIs
for gci in tableau.tbox.gcis.clone() {
tableau.add_label(node_id, gci);
}
}
// An individual may be named only by a role assertion, typed by a
// vocabulary this reasoner does not treat as a class (a skos:Concept, say) and never
// declared owl:NamedIndividual. It still has to exist as a node, or the edge that
// names it leads nowhere and the restriction that depends on it silently fails.
//
// BOTH endpoints, and the subject half is the newer one. The object half
// was here already; the subject half was unreachable, because an untyped
// subject's assertions were dropped during parsing and never became
// `role_assertions` at all. Now that they survive, the subject needs a
// node for the same reason the object does — and it needs one MORE than
// the object does, because `rdfs:domain` binds the source of the edge, so
// the subject is where a domain clash actually lands.
let referenced: Vec<u32> = self
.role_assertions
.iter()
.flat_map(|&(a, _, b)| [a, b])
.filter(|x| !ind_to_node.contains_key(x))
.collect();
for ind in referenced {
// `referenced` can name the same individual twice, once as a subject
// and once as an object, so this is not redundant with the filter.
if ind_to_node.contains_key(&ind) {
continue;
}
let node_id = tableau.fresh_node(None, None);
ind_to_node.insert(ind, node_id);
tableau.add_label(node_id, Concept::Atom(ind));
// A GCI holds of EVERY element of the domain, so a node that does not
// carry the GCIs is a hole this check cannot see into. These nodes were
// the only ones in the tableau created without them — the loop above
// adds them to every typed individual and `create_successor` adds them
// to every generated successor — and the omission was a second false
// clean of the same shape as the domain/range one: an ABox whose only
// contradiction lands on an individual named just by a role assertion
// was reported consistent.
for gci in tableau.tbox.gcis.clone() {
tableau.add_label(node_id, gci);
}
}
// Add role assertions as edges. An asserted edge a R b also means b has an
// R-inverse edge to a: without it, a ForAll or cardinality constraint on b
// never propagates backward across the edge, and an inconsistency reachable
// only through the inverse (or, since a symmetric role is its own inverse in
// `inverse_roles`, a symmetric) role is silently missed. Unlike the tree
// tableau, ABox individuals form an arbitrary graph, so the parent back-link
// successors() uses cannot stand in for the inverse neighbour. Materialise it.
//
// Both edges go in through `add_role_edge`, which is what applies rdfs:domain
// and rdfs:range. Writing them into the edge map directly, as this used to,
// is what made an asserted edge weaker than a generated one.
for &(a, r, b) in &self.role_assertions {
if let (Some(&a_node), Some(&b_node)) = (ind_to_node.get(&a), ind_to_node.get(&b)) {
let r_inv = tableau.tbox.inverse_roles.get(&r).copied();
tableau.add_role_edge(a_node, r, b_node);
if let Some(r_inv) = r_inv {
tableau.add_role_edge(b_node, r_inv, a_node);
}
}
}
let individuals_checked = ind_to_node.len();
(tableau, ind_to_node, individuals_checked)
}
pub fn check_abox(&self) -> ABoxResult {
self.check_abox_within(Self::global_deadline())
}
/// `check_abox` under a ceiling the caller already opened.
///
/// This phase used to be outside `classify_timeout_ms` entirely: the setting
/// was read inside `classify_parallel` and nowhere else, so a run that spent
/// the whole global budget classifying went on to open a fresh phase budget
/// here. A knob a run can exceed is not a ceiling.
pub fn check_abox_within(&self, global: Option<Instant>) -> ABoxResult {
// "No ABox" has to mean no ABox, and a role assertion is ABox. An
// ontology whose entire instance data is untyped individuals related by
// a property with a domain still states something refutable, and this
// guard used to return `consistent: true` on it without building
// anything, which is the same false clean one level up from the one
// `add_role_edge` closed.
if self.individual_types.is_empty()
&& self.individual_anon_types.is_empty()
&& self.role_assertions.is_empty()
{
return ABoxResult {
consistent: true,
undecided: false,
individuals_checked: 0,
steps: 0,
stopped_by: None,
clock: None,
inferred_types: HashMap::new(),
};
}
let (mut tableau, ind_to_node, individuals_checked) = self.build_abox_tableau(global);
// Same three-valued discipline as everywhere else: exhausting the
// budget is not a proof of inconsistency. Declaring an ABox
// inconsistent is a strong, user-visible claim and must never be the
// by-product of giving up. Default to consistent when undecided.
let expanded = tableau.expand(0);
let abox_undecided = !expanded && tableau.budget.exhausted;
let consistent = expanded || abox_undecided;
// Infer additional types for each individual. Only when the expansion
// genuinely completed: a partial tableau's labels are not conclusions.
let mut inferred: HashMap<u32, HashSet<u32>> = HashMap::new();
if expanded {
for (&ind, &node_id) in &ind_to_node {
if let Some(node) = tableau.nodes.get(&node_id) {
for label in &node.labels {
if let Concept::Atom(cls) = label
&& *cls != ind
&& !self.individual_types.get(&ind).is_some_and(|t| t.contains(cls)) {
inferred.entry(ind).or_default().insert(*cls);
}
}
}
}
}
// Structural realization runs regardless of which model the expansion found, and is
// what actually populates classes defined by owl:equivalentClass.
for (ind, classes) in self.realize_definitions() {
inferred.entry(ind).or_default().extend(classes);
}
ABoxResult {
consistent,
undecided: abox_undecided,
individuals_checked,
inferred_types: inferred,
steps: tableau.budget.steps.load(Ordering::Relaxed),
stopped_by: tableau.budget.stopped_by,
clock: if abox_undecided && tableau.budget.stopped_by == Some("time") {
expired_clock(tableau.budget.deadline, global)
} else {
None
},
}
}
/// Entry point for integration with the existing reasoner.
pub fn run(graph: &Arc<GraphStore>, materialize: bool) -> anyhow::Result<String> {
let reasoner = Self::from_graph(graph)?;
let initial_triples = graph.triple_count();
// ONE ceiling for the whole run, opened here and passed to every phase.
//
// `classify_timeout_ms` used to be read inside `classify_parallel` and
// nowhere else, so the three phases around it — the consistency check
// before, the ABox check after, the explanation loop after that — each
// opened a budget of their own and none of them was under it. A run
// could exceed the ceiling it was given by three further phase budgets,
// and the explanation loop had no wall clock at all.
let global_deadline = Self::global_deadline();
let tbox_consistent = reasoner.is_consistent_within(global_deadline);
let result = reasoner.classify_parallel_within(global_deadline);
let abox_result = reasoner.check_abox_within(global_deadline);
// The headline flag answers for the whole knowledge base. Reporting the TBox alone
// while the ABox check has PROVEN an inconsistency in the same output is a false
// claim; the three-valued discipline is preserved because an undecided ABox already
// defaults to consistent inside check_abox.
let consistent = tbox_consistent && abox_result.consistent;
// Collect explanations for unsatisfiable classes. One phase, one budget,
// under the same ceiling as the three before it.
let explain_deadline = reasoner.phase_deadline_within(global_deadline);
let mut explanations: Vec<serde_json::Value> = Vec::new();
for &cls in &result.unsatisfiable {
if let Some(steps) = reasoner.explain_unsatisfiable_within(cls, explain_deadline) {
explanations.push(serde_json::json!({
"class": reasoner.interner.resolve(cls),
"trace": steps,
}));
}
}
let unsat_names: Vec<&str> = result
.unsatisfiable
.iter()
.map(|&id| reasoner.interner.resolve(id))
.collect();
// Completeness signal. A caller must be able to tell a proof from a
// run that gave up; without this the two are indistinguishable in the
// output and every consumer silently over-trusts the result.
let undetermined_names: Vec<&str> = result
.undetermined
.iter()
.map(|&id| reasoner.interner.resolve(id))
.collect();
// A search that finished is not a classification that is complete. An
// axiom this engine reads only approximately, or not at all, can carry
// an entailment the search never had a chance to find, and the list of
// such axioms used to be computed only when a model certificate was
// requested. So `complete: true` was printed over runs that had
// approximated nominals or dropped a property chain, and a reader had
// no way to tell. Measured on ORE 2015 `ore_ont_5107`: seven
// `ObjectOneOf`, every phase decided, `complete: true`, and none of the
// six subsumptions HermiT infers.
let unmodelled = DlReasoner::unmodelled_constructs(graph);
let search_finished = undetermined_names.is_empty()
&& !result.subsumption_cut_short
&& !abox_result.undecided;
let complete = search_finished && unmodelled.is_empty();
// WHICH phase ran out, not merely THAT something did.
//
// `complete: false` says the run is not a proof. It does not say which of
// the three phases to give more room. Every phase now draws on the same
// two settings — its own `tableaux_test_timeout_ms` budget, under the
// `[reasoner] classify_timeout_ms` ceiling for the whole run — and the
// `budget` block below says which of the two is the one that fires. The
// ABox check used to be under the phase budget ALONE, outside the ceiling
// entirely. A reader who is told only "incomplete" cannot act, and before
// each phase got its own budget
// the phase that hit the wall was usually not the phase that spent the
// time — classification would eat the clock and the ABox check would be
// the one reporting `undecided`. Naming the phases makes that visible
// rather than leaving it to be inferred.
let mut budget_exhausted_in: Vec<&str> = Vec::new();
if !undetermined_names.is_empty() {
budget_exhausted_in.push("satisfiability");
}
if result.subsumption_cut_short {
budget_exhausted_in.push("subsumption");
}
if abox_result.undecided {
budget_exhausted_in.push("abox");
}
// WHICH budget was in force, in words, in the output.
//
// `classify_timeout_ms` defaults to 180 000 ms and its own documentation
// called it "the budget that actually bounds the run". It had never
// bounded one. Each phase opens its own deadline from
// `tableaux_test_timeout_ms`, which defaults to 10 000 ms; five phases is
// a worst case of 50 000 ms of tableau time, so at the defaults the
// 180 000 ms ceiling is not expected to fire. Handing the global budget
// the run instead means minting a deadline per TABLEAU, which was
// measured and took a 20-ontology corpus from 67s to over 600s, and was
// abandoned. That number is unreproducible from this tree;
// `phase_deadline` says why and names the bench that is.
//
// What is left is the thing that was missing: SAYING SO. A knob that
// reads as a safety limit may not enforce nothing, and the arithmetic
// that decides whether it can fire is two settings and a phase count,
// which is not something a reader of the output can be expected to do.
// The ceiling is now genuinely enforced over every phase — see
// `phase_deadline_within`.
//
// TWO answers, and they used to be one (#340). `configured_bound` is the
// bound the settings predict, from that arithmetic. `binding_bound` is
// the bound that ACTUALLY stopped this run, read off the phases that
// were cut short: `"global"` if the ceiling's deadline had passed when
// one of them ran out, `"phase"` if only a phase budget had, `"none"` if
// no wall clock stopped anything. The prediction is not an observation:
// it said "the ceiling cannot be the bound" over a run whose subsumption
// sweep had outlived its phase budget by 26 times and was heading for
// the ceiling, because the arithmetic assumed every phase ends at its
// own deadline and the sweep did not.
let phase_names = ["consistency", "satisfiability", "subsumption", "abox", "explanation"];
let global_ms = crate::runtime::classify_timeout_ms();
let phase_ms = crate::runtime::tableaux_test_timeout_ms();
let phase_worst_case_ms = phase_ms.map(|ms| ms * phase_names.len() as u64);
let (configured_bound, configured_note) = match (global_ms, phase_worst_case_ms) {
(None, None) => (
"none",
format!(
"No wall-clock bound of any kind is in force: classify_timeout_ms and \
tableaux_test_timeout_ms are both 0. The only limits left are the node \
cap ({}) and the depth cap ({}), and neither bounds the number of \
BRANCHES a tableau explores.",
crate::runtime::tableaux_max_nodes(),
crate::runtime::tableaux_max_depth()
),
),
(None, Some(worst)) => (
"phase",
format!(
"No global bound is in force: classify_timeout_ms is 0. Each of the {} \
phases opens its own {} ms budget, so the tableau work in this run is \
bounded at {worst} ms.",
phase_names.len(),
phase_ms.unwrap_or(0)
),
),
(Some(g), None) => (
"global",
format!(
"classify_timeout_ms ({g} ms) is the only wall-clock bound: \
tableaux_test_timeout_ms is 0, so no phase budget can expire before it \
and every tableau runs to the global deadline."
),
),
(Some(g), Some(worst)) if g <= worst => (
"global",
format!(
"classify_timeout_ms ({g} ms) is at or below the worst case the phase \
budgets permit ({} phases x {} ms = {worst} ms), so it is the bound \
expected to stop a run that needs it.",
phase_names.len(),
phase_ms.unwrap_or(0)
),
),
(Some(g), Some(worst)) => (
"phase",
format!(
"At these settings classify_timeout_ms ({g} ms) is not expected to be the \
bound: {} phases at {} ms each bound the tableau work at {worst} ms. It \
is enforced as a ceiling over every phase and fires only if the work \
between tableaux (building pair lists and the hierarchy) takes the rest; \
lower it below {worst} ms to make it the expected bound.",
phase_names.len(),
phase_ms.unwrap_or(0)
),
),
};
let stopped_by_clock: Vec<(&str, &str)> = [
("satisfiability", result.satisfiability_clock),
("subsumption", result.subsumption_clock),
("abox", abox_result.clock),
]
.into_iter()
.filter_map(|(phase, clock)| clock.map(|c| (phase, c)))
.collect();
let phases_stopped_by = |clock: &str| -> Vec<&str> {
stopped_by_clock
.iter()
.filter(|(_, c)| *c == clock)
.map(|(p, _)| *p)
.collect()
};
let by_global = phases_stopped_by("global");
let by_phase = phases_stopped_by("phase");
let by_cap: Vec<&str> = budget_exhausted_in
.iter()
.copied()
.filter(|p| !stopped_by_clock.iter().any(|(q, _)| q == p))
.collect();
let binding_bound = if !by_global.is_empty() {
"global"
} else if !by_phase.is_empty() {
"phase"
} else {
"none"
};
let mut outcome = match binding_bound {
"global" => format!(
"The classify_timeout_ms ceiling ({} ms) stopped this run: it had passed \
when {} ran out of time.",
global_ms.unwrap_or(0),
by_global.join(", ")
),
"phase" => format!(
"A phase budget ({} ms) stopped this run, in {}; the classify_timeout_ms \
ceiling did not.",
phase_ms.unwrap_or(0),
by_phase.join(", ")
),
_ if by_cap.is_empty() => {
"No bound stopped this run: every phase finished inside its budget.".to_string()
}
_ => "No wall clock stopped this run.".to_string(),
};
if binding_bound == "global" && !by_phase.is_empty() {
outcome.push_str(&format!(
" {} had already run out of its own phase budget.",
by_phase.join(", ")
));
}
if !by_cap.is_empty() {
outcome.push_str(&format!(
" {} {} cut short by the step, node or depth cap, not by a clock.",
by_cap.join(", "),
if by_cap.len() == 1 { "was" } else { "were" }
));
}
let note = format!("{outcome} {configured_note}");
let mut hierarchy_json: Vec<serde_json::Value> = Vec::new();
for (&cls, supers) in &result.hierarchy {
let cls_name = reasoner.interner.resolve(cls);
let super_names: Vec<&str> = supers
.iter()
.map(|&id| reasoner.interner.resolve(id))
.collect();
hierarchy_json.push(serde_json::json!({
"class": cls_name,
"superclasses": super_names,
}));
}
let equiv_json: Vec<serde_json::Value> = result
.equivalences
.iter()
.map(|&(a, b)| {
serde_json::json!({
"class_a": reasoner.interner.resolve(a),
"class_b": reasoner.interner.resolve(b),
})
})
.collect();
// ABox results
let abox_json = if abox_result.individuals_checked > 0 {
let mut ind_json: Vec<serde_json::Value> = Vec::new();
for (&ind, types) in &abox_result.inferred_types {
let type_names: Vec<&str> = types
.iter()
.map(|&id| reasoner.interner.resolve(id))
.collect();
ind_json.push(serde_json::json!({
"individual": reasoner.interner.resolve(ind),
"inferred_types": type_names,
}));
}
serde_json::json!({
"consistent": abox_result.consistent,
"undecided": abox_result.undecided,
"individuals_checked": abox_result.individuals_checked,
"inferred": ind_json,
})
} else {
serde_json::json!(null)
};
// Materialize all hierarchy subsumptions
let mut materialized = 0;
if materialize && !result.hierarchy.is_empty() {
let mut ntriples = String::new();
for (&cls, supers) in &result.hierarchy {
let cls_str = reasoner.interner.resolve(cls);
for &sup in supers {
let sup_str = reasoner.interner.resolve(sup);
ntriples.push_str(cls_str);
ntriples.push(' ');
ntriples.push_str(RDFS_SUBCLASS);
ntriples.push(' ');
ntriples.push_str(sup_str);
ntriples.push_str(" .\n");
materialized += 1;
}
}
if !ntriples.is_empty() {
graph.load_ntriples(&ntriples)?;
}
}
let mut output = serde_json::json!({
"profile_used": "owl-dl",
"algorithm": "tableaux",
"description_logic": "SHIQ",
"consistent": consistent,
"tbox_consistent": tbox_consistent,
"named_classes": reasoner.named_classes.len(),
"unsatisfiable_classes": unsat_names,
"complete": complete,
"search_finished": search_finished,
"constructs_not_modelled": unmodelled
.iter()
.map(|(k, n)| serde_json::json!({"construct": k, "occurrences": n}))
.collect::<Vec<_>>(),
"budget_exhausted_in": budget_exhausted_in,
"budget": {
"classify_timeout_ms": global_ms,
"phase_timeout_ms": phase_ms,
"phases": phase_names,
"phase_worst_case_ms": phase_worst_case_ms,
"binding_bound": binding_bound,
"configured_bound": configured_bound,
"note": note,
},
"undetermined_classes": undetermined_names,
"subsumption_sweep_cut_short": result.subsumption_cut_short,
"inferred_subsumptions": result.inferred_subsumptions,
"equivalences": equiv_json,
"classification": hierarchy_json,
"initial_triples": initial_triples,
"final_triples": graph.triple_count(),
"inferred_count": materialized,
"agents": {
"satisfiability_agent": {
"classes_checked": result.agents.satisfiability.tasks,
"satisfiable_found": result.agents.satisfiability.results,
"undetermined": result.undetermined.len(),
"time_ms": result.agents.satisfiability.time_ms,
},
"subsumption_agent": {
"pairs_tested": result.agents.subsumption.tasks,
"pairs_scheduled": result.pairs_scheduled,
"pairs_not_reached": result.pairs_not_reached,
"subsumptions_found": result.agents.subsumption.results,
"undetermined": result.undetermined_pair_count(),
"read_from_models": result.subsumptions_from_models,
"time_ms": result.agents.subsumption.time_ms,
},
"parallel_workers": result.agents.parallel_workers,
"total_time_ms": result.agents.total_time_ms,
},
});
// Opt-in model certificates. Off unless `OO_DL_MODEL_DIR` names a
// directory, so the default behaviour of `owl-dl` is exactly what it
// was. Only the POSITIVE answers are certified: an inconsistent TBox or
// an unsatisfiable class produces `Refuted` here, which means "no
// certificate", not "certified unsatisfiable".
if let Ok(root) = std::env::var("OO_DL_MODEL_DIR") {
let root = std::path::PathBuf::from(root);
let describe = |r: anyhow::Result<ModelOutcome>| match r {
Ok(o) => o.describe(),
Err(e) => format!("no certificate: {e}"),
};
// Per class as well as per ontology. TBox consistency is honestly
// witnessed by a single point with empty extensions, which really
// is what consistency means and is a weak-looking artefact; the
// per-class certificates are the informative ones, and the sweep
// that validated this layer used them.
let mut classes = serde_json::Map::new();
for (i, class) in reasoner.named_class_names().iter().enumerate() {
let sub = root.join("classes").join(i.to_string());
classes.insert(
class.clone(),
serde_json::json!(describe(reasoner.certify_class_satisfiable(class, &sub))),
);
}
output["model_certificate"] = serde_json::json!({
"dir": root.display().to_string(),
"tbox": describe(reasoner.certify_tbox_consistent(&root.join("tbox"))),
"abox": describe(reasoner.certify_abox_consistent(&root.join("abox"))),
"classes": classes,
"checker": "oo-dlmodel",
"theorem": "Dl.satisfiable_of_checkModel",
// The constructs below are IN THE GRAPH and NOT in the axioms
// the certificate is about, so where this list is non-empty the
// certificate describes a weaker axiom set than the ontology
// states. Read the verdict against this list, not on its own.
"certifies_a_weaker_axiom_set": !unmodelled.is_empty(),
"constructs_not_modelled": unmodelled
.iter()
.map(|(k, n)| serde_json::json!({"construct": k, "occurrences": n}))
.collect::<Vec<_>>(),
"not_covered": "unsatisfiability and inconsistency carry no certificate",
});
}
if !explanations.is_empty() {
output["explanations"] = serde_json::json!(explanations);
}
if !abox_json.is_null() {
output["abox"] = abox_json;
}
if !materialize {
output["dry_run"] = serde_json::json!(true);
}
Ok(output.to_string())
}
/// Explain why a named class is unsatisfiable. For agent-friendly MCP tools.
pub fn explain_class(graph: &Arc<GraphStore>, class_iri: &str) -> anyhow::Result<String> {
let reasoner = Self::from_graph(graph)?;
let class_id = reasoner
.interner
.to_id
.get(class_iri)
.copied()
.ok_or_else(|| anyhow::anyhow!("Unknown class: {}", class_iri))?;
match reasoner.explain_unsatisfiable(class_id) {
Some(steps) => Ok(serde_json::json!({
"class": class_iri,
"satisfiable": false,
"explanation": steps,
})
.to_string()),
None => Ok(serde_json::json!({
"class": class_iri,
"satisfiable": true,
"explanation": "Class is satisfiable — no clash found.",
})
.to_string()),
}
}
/// Check if class_a ⊑ class_b. For agent-friendly MCP tools.
pub fn check_subsumption(
graph: &Arc<GraphStore>,
sub_iri: &str,
sup_iri: &str,
) -> anyhow::Result<String> {
let reasoner = Self::from_graph(graph)?;
let sub_id = reasoner
.interner
.to_id
.get(sub_iri)
.copied()
.ok_or_else(|| anyhow::anyhow!("Unknown class: {}", sub_iri))?;
let sup_id = reasoner
.interner
.to_id
.get(sup_iri)
.copied()
.ok_or_else(|| anyhow::anyhow!("Unknown class: {}", sup_iri))?;
let (subsumed, trace) = reasoner.check_subsumption_explained(
&Concept::Atom(sub_id),
&Concept::Atom(sup_id),
);
Ok(serde_json::json!({
"sub_class": sub_iri,
"super_class": sup_iri,
"subsumed": subsumed,
"trace": trace,
})
.to_string())
}
}
// ── Subsumption sweep ───────────────────────────────────────────────────
/// What one satisfiability test's model says about a class's subsumers.
///
/// A complete, clash-free completion graph for `A` is a model of the TBox in
/// which the root is an instance of `A`, and in that model the root belongs to
/// a named class `B` exactly when `B` is in the root's label. So every named
/// class NOT in the root label is a proven non-subsumer of `A`: the model is a
/// witness that `A ⊓ ¬B` is satisfiable. That half needs nothing else.
///
/// The other half needs the run to have made no choice. When no `⊔` branch was
/// taken and no `≤` merge was chosen, every label in the graph was forced by
/// deterministic rules from `A` and the TBox, so it holds of the root in EVERY
/// model of `A`, and every named class in the root label is a subsumer. When a
/// choice was made, the label is only one model's answer, and each class in it
/// is a candidate that still needs its own `A ⊓ ¬B` test.
struct ClassModel {
/// Named classes in the root label, the class itself excluded.
root_classes: Vec<u32>,
/// True when no `⊔` branch and no `≤` merge was taken.
deterministic: bool,
}
/// Which wall clock a phase deadline belongs to, if that deadline has passed.
///
/// `phase_deadline_within` hands every phase the earlier of its own budget and
/// the run's ceiling, so a passed deadline is the ceiling exactly when it IS the
/// ceiling's instant. Read at the end of a phase that was cut short, this is the
/// bound that actually stopped it, which is what `budget.binding_bound` reports.
/// It used to report the bound the settings predicted instead, and said
/// `"phase"` over a run the ceiling had stopped (#340).
fn expired_clock(deadline: Option<Instant>, global: Option<Instant>) -> Option<&'static str> {
let d = deadline?;
if Instant::now() < d {
return None;
}
Some(if global == Some(d) { "global" } else { "phase" })
}
/// The candidate superclasses of one class in the subsumption sweep.
enum Candidates<'a> {
/// Read off a nondeterministic model of the class: every named class in
/// its root label that is not already settled.
Listed(Vec<u32>),
/// No model to read, so every class in `pool` except the class itself and
/// `exclude`. Never written out: see `PairRow::every`.
Every {
pool: &'a [u32],
exclude: Option<&'a HashSet<u32>>,
},
}
/// One class's share of the subsumption sweep, with its pair count known
/// before any pair is generated, so pairs the budget never reaches can be
/// counted without being built.
struct PairRow<'a> {
sub: u32,
candidates: Candidates<'a>,
/// How many pairs `(sub, sup)` this row stands for.
count: usize,
}
impl<'a> PairRow<'a> {
fn listed(sub: u32, sups: Vec<u32>) -> Self {
let count = sups.len();
PairRow { sub, candidates: Candidates::Listed(sups), count }
}
/// Every class in `pool` other than `sub` and the members of `exclude`.
///
/// `pool` must hold no duplicate and `pool_set` must be exactly its
/// members. The count is then `|pool|`, less one if `sub` is in it, less
/// the members of `exclude` other than `sub` that are in it, which costs
/// `|exclude|` rather than `|pool|`. That difference is the point: for
/// `k` classes with no model, counting by walking the pool is the `k x n`
/// walk this row exists to avoid.
fn every(
sub: u32,
pool: &'a [u32],
pool_set: &HashSet<u32>,
exclude: Option<&'a HashSet<u32>>,
) -> Self {
let excluded = exclude.map_or(0, |e| {
e.iter().filter(|&&x| x != sub && pool_set.contains(&x)).count()
});
let count = pool.len() - usize::from(pool_set.contains(&sub)) - excluded;
PairRow { sub, candidates: Candidates::Every { pool, exclude }, count }
}
}
/// What a sweep of subsumption tests established, kept three-valued.
#[derive(Default)]
struct PairSweep {
/// Pairs whose test proved `sub ⊓ ¬sup` unsatisfiable, so `sub ⊑ sup`.
inferred: Vec<(u32, u32)>,
/// Pairs whose test was run and came back `Unknown`. Neither a
/// subsumption nor a refutation of one.
undetermined: Vec<(u32, u32)>,
/// Pairs whose test was run: one tableau each.
tested: usize,
/// Pairs never tested because the sweep's deadline had passed before they
/// were reached. Undetermined exactly as `undetermined` is, but counted
/// rather than listed, because there can be tens of millions of them.
not_reached: usize,
}
impl PairSweep {
fn merge(mut self, other: PairSweep) -> PairSweep {
self.inferred.extend(other.inferred);
self.undetermined.extend(other.undetermined);
self.tested += other.tested;
self.not_reached += other.not_reached;
self
}
}
/// Run `decide` over every pair the rows stand for, until `expired` says the
/// sweep's deadline has passed, and keep the three answers apart.
///
/// This used to be a `filter` that kept a pair when its verdict `.is_unsat()`,
/// which folds `Unknown` into "not subsumed". The sweep only flagged itself
/// incomplete when the run's GLOBAL ceiling had passed before a pair was
/// reached; a test whose own phase budget ran out inside it returned
/// `Unknown`, was dropped exactly as a refuted pair is, and left no trace. The
/// phase budget is shared by every pair in the sweep, so once it expires every
/// remaining pair fails that way at once.
///
/// Measured on ORE 2015 `ore_ont_8937` (37 classes, 1,326 pairs): the sweep hit
/// its 10 s phase budget, two runs of one binary returned 36 and then 57
/// subsumptions against HermiT's 329, and both reported
/// `budget_exhausted_in: []`, `complete: true`. A result that is wrong and says
/// it is finished is the failure this codebase exists to rule out.
///
/// And once the deadline has passed it STOPS (#340). It used to call `decide`
/// on every remaining pair, and each call built a tableau that returned
/// `Unknown` from its first step, so the sweep's wall time grew with the pair
/// count rather than the budget: 5,042 ms under a 200 ms phase budget, over
/// 27.5 million pairs, on the issue's 6,000-class ontology. Now a pair reached
/// after `expired` first says yes is counted in `not_reached` without a call,
/// and a row reached after that is counted in bulk from its `count` without
/// generating its pairs. Since the skipped calls could only have returned
/// `Unknown`, which is what they are counted as, no verdict changes.
///
/// Both outputs are sorted, so the result does not depend on how the thread
/// pool happened to split the work.
///
/// Taking the verdict and the clock as functions is what lets a test hand the
/// sweep an `Unknown` or an expiry deterministically. The real failure needs a
/// wall clock to run out partway through a sweep, and a test that depends on a
/// wall clock is the flake `#161` removed.
fn sweep_pairs<E, F>(rows: &[PairRow<'_>], expired: E, decide: F) -> PairSweep
where
E: Fn() -> bool + Sync,
F: Fn(u32, u32) -> Verdict + Sync,
{
// A latch, so that once one worker has seen the deadline pass no worker
// reads the clock again.
let stopped = AtomicBool::new(false);
let stop = || {
if stopped.load(Ordering::Relaxed) {
return true;
}
if expired() {
stopped.store(true, Ordering::Relaxed);
return true;
}
false
};
let test = |mut acc: PairSweep, sub: u32, sup: u32| {
if stop() {
acc.not_reached += 1;
return acc;
}
acc.tested += 1;
match decide(sub, sup) {
Verdict::Unsatisfiable => acc.inferred.push((sub, sup)),
Verdict::Unknown => acc.undetermined.push((sub, sup)),
Verdict::Satisfiable => {}
}
acc
};
let mut sweep = rows
.par_iter()
.map(|row| {
if stop() {
return PairSweep { not_reached: row.count, ..PairSweep::default() };
}
let sub = row.sub;
match &row.candidates {
Candidates::Listed(sups) => sups
.par_iter()
.fold(PairSweep::default, |acc, &sup| test(acc, sub, sup))
.reduce(PairSweep::default, PairSweep::merge),
Candidates::Every { pool, exclude } => pool
.par_iter()
.filter(|&&sup| sup != sub && !exclude.is_some_and(|e| e.contains(&sup)))
.fold(PairSweep::default, |acc, &sup| test(acc, sub, sup))
.reduce(PairSweep::default, PairSweep::merge),
}
})
.reduce(PairSweep::default, PairSweep::merge);
sweep.inferred.sort_unstable();
sweep.undetermined.sort_unstable();
sweep
}
// ── Agent Result Types ──────────────────────────────────────────────────
pub struct AgentClassificationResult {
pub hierarchy: HashMap<u32, HashSet<u32>>,
/// Classes PROVEN to have no instances.
pub unsatisfiable: Vec<u32>,
/// Classes on which a resource budget was hit before a decision. Neither
/// proven satisfiable nor proven unsatisfiable. Their presence means the
/// classification as a whole is incomplete.
pub undetermined: Vec<u32>,
/// True when any subsumption test came back undecided, so the hierarchy
/// may be missing pairs. Absence of a subsumption in the output is then
/// not evidence that it does not hold.
pub subsumption_cut_short: bool,
/// The ordered pairs `(sub, sup)` whose test was run and came back
/// `Unknown`, because a budget expired inside the test. See `sweep_pairs`.
pub undetermined_pairs: Vec<(u32, u32)>,
/// Pairs never tested because the sweep's deadline (its phase budget, or
/// the run's ceiling if that came first) had passed before they were
/// reached. Every one is undetermined; they are counted, not listed. See
/// `undetermined_pair_count`.
pub pairs_not_reached: usize,
/// Every pair the sweep had to decide: tested plus not reached. Pairs
/// settled by a model or by a told axiom are not in it.
pub pairs_scheduled: usize,
/// The wall clock that cut the satisfiability phase short, if one did:
/// `"phase"` or `"global"`. `None` when the phase finished, or was cut
/// short only by a step, node or depth cap.
pub satisfiability_clock: Option<&'static str>,
/// The same, for the subsumption sweep.
pub subsumption_clock: Option<&'static str>,
/// Subsumptions read off a satisfiability model built with no choice, so
/// never tested pairwise. See `ClassModel`.
pub subsumptions_from_models: usize,
pub equivalences: Vec<(u32, u32)>,
pub inferred_subsumptions: usize,
pub agents: AgentMetrics,
}
impl AgentClassificationResult {
/// Every pair left undecided: tested and `Unknown`, plus never reached.
pub fn undetermined_pair_count(&self) -> usize {
self.undetermined_pairs.len() + self.pairs_not_reached
}
}
pub struct AgentMetrics {
pub satisfiability: AgentTaskMetrics,
pub subsumption: AgentTaskMetrics,
pub total_time_ms: u64,
pub parallel_workers: usize,
}
pub struct AgentTaskMetrics {
pub tasks: usize,
pub results: usize,
pub time_ms: u64,
}
pub struct ABoxResult {
/// Reported consistent unless inconsistency was PROVEN. See `undecided`.
pub consistent: bool,
/// True when the ABox expansion ran out of budget. `consistent` is then a
/// default, not a finding.
pub undecided: bool,
pub individuals_checked: usize,
pub inferred_types: HashMap<u32, HashSet<u32>>,
/// Expansion steps this run took.
///
/// The same ontology takes the same number on every machine, which is what
/// makes a step budget a budget rather than a race. A test can assert on
/// this; a clock-bounded run has no such number.
pub steps: u64,
/// Which budget stopped the run, if one did: `"steps"` or `"time"`.
///
/// `undecided` alone says a run was cut short and not which bound cut it.
/// Those call for different responses, and a reader deciding whether to
/// raise a limit needs to know which limit.
pub stopped_by: Option<&'static str>,
/// When `stopped_by` is `"time"`, which wall clock that was: `"phase"` or
/// `"global"`. See `expired_clock`.
pub clock: Option<&'static str>,
}
pub struct ClassificationResult {
pub hierarchy: HashMap<u32, HashSet<u32>>,
pub unsatisfiable: Vec<u32>,
pub equivalences: Vec<(u32, u32)>,
pub inferred_subsumptions: usize,
}
// ── Model certificates ──────────────────────────────────────────────────
//
// Every verdict above is a bare verdict. A consumer who wants to know whether
// the reasoner was right has to trust the reasoner. This section closes half of
// that gap, and only half, deliberately.
//
// A tableaux run gives two kinds of answer and they are not equally hard to
// certify. SATISFIABLE is easy: the procedure builds a completion graph, and a
// completion graph either is a finite model or folds into one. A finite model is
// a finite object, and checking that a finite interpretation satisfies a set of
// axioms is decidable and provable. UNSATISFIABLE is hard: it needs the closed
// tableau, every branch, every clash and the blocking argument, which is a
// proof-checking problem and is not attempted here.
//
// So the positive answers carry a certificate and the negative ones do not. When
// the reasoner reports a class unsatisfiable or an ontology inconsistent, it
// still just says so, and the report says that plainly rather than blurring the
// two.
//
// The certificate is two tab-separated files, `axioms.tsv` and `model.tsv`, read
// by `oo-dlmodel` (`lean/DlMain.lean`). `lean/Dl/Syntax.lean` documents the
// format and is the normative description of it. `Dl.satisfiable_of_checkModel`
// is the machine-checked statement the exit code stands for: an interpretation
// the checker accepts is a model, so the axiom set is satisfiable.
//
// Three things this does NOT do, stated here so no reader has to discover them:
//
// 1. The OWL parser is outside the theorem. The axioms written out are the
// axioms `OwlParser` read, not the ontology. A triple the parser ignores is
// absent from the certificate and the checker never sees it.
// 2. Nothing is emitted for an answer that is not positive, and nothing is
// emitted when the completion graph cannot be turned into a finite
// interpretation. `ModelOutcome::Refused` says which, and no file is
// written. Emitting something that will not check would be worse than
// emitting nothing.
// 3. The self-check below decides whether to emit. It is the same semantics
// `lean/Dl/Check.lean` implements, written twice on purpose: the Rust copy
// is a gate on the emitter, and the Lean copy is the one with the proof. A
// disagreement between them shows up as `oo-dlmodel` rejecting a certificate
// this side thought was fine, which is a failure, not a shrug.
use std::path::Path;
/// An axiom in the fragment `lean/Dl/` covers, over interned identifiers.
#[derive(Clone, Debug)]
pub(crate) enum DlAxiom {
Sub(Concept, Concept),
Disjoint(Concept, Concept),
Domain(u32, Concept),
Range(u32, Concept),
SubRole(u32, u32),
Trans(u32),
Sym(u32),
Inv(u32, u32),
InvFunc(u32),
Inst(u32, Concept),
Rel(u32, u32, u32),
Indiv(u32),
NonEmpty(Concept),
}
/// A folded completion graph: the node identifiers that survived, and the edges
/// between them, each written `(source, role, target)`.
type FoldedGraph = (Vec<u32>, Vec<(u32, u32, u32)>);
/// A finite interpretation whose domain elements are tableau node identifiers.
#[derive(Default)]
struct FiniteModel {
dom: Vec<u32>,
domset: HashSet<u32>,
/// Atomic concept identifier → the nodes in its extension. Closed world on
/// atoms: a node is in `A` exactly when `Atom(A)` is in its label. That is
/// the canonical reading of a completion graph, and it is what makes the
/// negated atoms in the labels mean anything.
cext: HashMap<u32, HashSet<u32>>,
/// (role, source) → deduplicated targets.
rext: HashMap<(u32, u32), Vec<u32>>,
/// Individual identifier → the node that denotes it.
ind: HashMap<u32, u32>,
}
/// What `DlReasoner::certify_*` did.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ModelOutcome {
/// `axioms.tsv` and `model.tsv` were written and pass the emitter's own
/// check. `oo-dlmodel` is what turns that into a verified statement.
Certified {
axioms: usize,
domain: usize,
edges: usize,
},
/// The reasoner PROVED the negative answer. There is no model to hand over,
/// and this layer says nothing about whether the proof is right.
Refuted,
/// A resource budget was hit. Nothing was proven either way.
Undetermined,
/// A positive answer was reached but the completion graph could not be
/// turned into a finite interpretation that satisfies the axioms. No file
/// was written. The string says why.
Refused(String),
}
impl ModelOutcome {
/// True only when files were written.
pub fn is_certified(&self) -> bool {
matches!(self, ModelOutcome::Certified { .. })
}
/// A one-line description, for logs and for the `owl-dl` JSON output.
pub fn describe(&self) -> String {
match self {
ModelOutcome::Certified {
axioms,
domain,
edges,
} => format!("certified: {axioms} axioms, {domain} elements, {edges} edges"),
ModelOutcome::Refuted => "no certificate: the answer was negative".to_string(),
ModelOutcome::Undetermined => "no certificate: the run was undetermined".to_string(),
ModelOutcome::Refused(why) => format!("no certificate: {why}"),
}
}
}
/// A name that survives the round trip through the two files.
///
/// The concept grammar is space-separated and the files are tab-separated, so a
/// term carrying either would be read back as a different term. N-Triples IRIs
/// and blank node labels never do. A literal can, and `owl:hasValue` is
/// approximated here by an atomic concept named after the individual, which may
/// be a literal. Refusing is the only honest answer for one of those.
///
/// The body is `crate::boundary_core::name_is_safe_bytes`, which is the
/// function Aeneas translates into Lean. `OOBoundary.name_is_safe_bytes_iff`
/// proves it accepts a name IF AND ONLY IF the name is non-empty and carries
/// none of those four bytes, for names of every length, which is what the
/// proptest below can only sample. All four are ASCII and no ASCII byte occurs
/// inside a multi-byte UTF-8 sequence, so the byte-level test and
/// `str::contains` over a `char` array agree on every `&str`.
pub(crate) fn name_is_safe(s: &str) -> bool {
crate::boundary_core::name_is_safe_bytes(s.as_bytes())
}
// ── Serialisation ───────────────────────────────────────────────────────
/// The ONE place a name enters either file, and therefore the one place the
/// guard has to be.
///
/// TCB-26 used to read: "the `names` vector is built by walking every axiom
/// variant, every role in `model.rext` and every class in `model.cext`.
/// Individuals in `model.ind` are covered only because `DlAxiom::Indiv(i)` is
/// emitted for every individual that reaches the model. That is an argument
/// about two separate loops agreeing, not a check." The separate loop is gone.
/// A name is checked as it is written, so "the guard covers every name that is
/// written" is true by construction: there is no other way to write one.
///
/// `bad` records the FIRST refused name and the caller refuses the whole
/// certificate. It is a sink rather than a `Result` so the serialisers stay
/// total and keep their shape; a certificate is written only after the caller
/// has looked at it.
pub(crate) fn push_name(out: &mut String, interner: &Interner, id: u32, bad: &mut Option<String>) {
let s = interner.resolve(id);
if !name_is_safe(s) && bad.is_none() {
*bad = Some(s.to_string());
}
out.push_str(s);
}
fn write_concept(out: &mut String, interner: &Interner, c: &Concept, bad: &mut Option<String>) {
match c {
Concept::Top => out.push_str("top"),
Concept::Bottom => out.push_str("bot"),
Concept::Atom(a) => {
out.push_str("atom ");
push_name(out, interner, *a, bad);
}
Concept::NegAtom(a) => {
out.push_str("not atom ");
push_name(out, interner, *a, bad);
}
// `lean/Dl` has binary conjunction and disjunction, so the n-ary OWL
// constructors are folded right-associatively here. An empty list is the
// unit of the connective, which is how `RawConcept::to_nnf` already
// reads it.
Concept::And(cs) => write_nary(out, interner, cs, "and", &Concept::Top, bad),
Concept::Or(cs) => write_nary(out, interner, cs, "or", &Concept::Bottom, bad),
Concept::Exists(r, f) => {
out.push_str("some ");
push_name(out, interner, *r, bad);
out.push(' ');
write_concept(out, interner, f, bad);
}
Concept::ForAll(r, f) => {
out.push_str("all ");
push_name(out, interner, *r, bad);
out.push(' ');
write_concept(out, interner, f, bad);
}
Concept::MinCard(r, n, f) => {
out.push_str("min ");
out.push_str(&n.to_string());
out.push(' ');
push_name(out, interner, *r, bad);
out.push(' ');
write_concept(out, interner, f, bad);
}
Concept::MaxCard(r, n, f) => {
out.push_str("max ");
out.push_str(&n.to_string());
out.push(' ');
push_name(out, interner, *r, bad);
out.push(' ');
write_concept(out, interner, f, bad);
}
}
}
fn write_nary(
out: &mut String,
interner: &Interner,
cs: &[Concept],
op: &str,
unit: &Concept,
bad: &mut Option<String>,
) {
match cs.split_first() {
None => write_concept(out, interner, unit, bad),
Some((head, [])) => write_concept(out, interner, head, bad),
Some((head, rest)) => {
out.push_str(op);
out.push(' ');
write_concept(out, interner, head, bad);
out.push(' ');
write_nary(out, interner, rest, op, unit, bad);
}
}
}
pub(crate) fn concept_string(interner: &Interner, c: &Concept, bad: &mut Option<String>) -> String {
let mut s = String::new();
write_concept(&mut s, interner, c, bad);
s
}
pub(crate) fn axiom_line(interner: &Interner, a: &DlAxiom, bad: &mut Option<String>) -> String {
// Every name in the line goes through `push_name`, including the ones that
// are not inside a concept, so `bad` is set by the time the line exists.
let cs = |c: &Concept, bad: &mut Option<String>| concept_string(interner, c, bad);
let r = |id: &u32, bad: &mut Option<String>| {
let mut s = String::new();
push_name(&mut s, interner, *id, bad);
s
};
match a {
DlAxiom::Sub(c, d) => format!("sub\t{}\t{}", cs(c, bad), cs(d, bad)),
DlAxiom::Disjoint(c, d) => format!("disjoint\t{}\t{}", cs(c, bad), cs(d, bad)),
DlAxiom::Domain(role, c) => format!("domain\t{}\t{}", r(role, bad), cs(c, bad)),
DlAxiom::Range(role, c) => format!("range\t{}\t{}", r(role, bad), cs(c, bad)),
DlAxiom::SubRole(a1, b1) => format!("subrole\t{}\t{}", r(a1, bad), r(b1, bad)),
DlAxiom::Trans(role) => format!("trans\t{}", r(role, bad)),
DlAxiom::Sym(role) => format!("sym\t{}", r(role, bad)),
DlAxiom::Inv(a1, b1) => format!("inv\t{}\t{}", r(a1, bad), r(b1, bad)),
DlAxiom::InvFunc(role) => format!("invfunc\t{}", r(role, bad)),
DlAxiom::Inst(i, c) => format!("inst\t{}\t{}", r(i, bad), cs(c, bad)),
DlAxiom::Rel(a1, role, b1) => {
format!("rel\t{}\t{}\t{}", r(a1, bad), r(role, bad), r(b1, bad))
}
DlAxiom::Indiv(i) => format!("indiv\t{}", r(i, bad)),
DlAxiom::NonEmpty(c) => format!("nonempty\t{}", cs(c, bad)),
}
}
// ── The finite interpretation, and the check on it ──────────────────────
impl FiniteModel {
fn successors(&self, role: u32, x: u32) -> &[u32] {
self.rext
.get(&(role, x))
.map(|v| v.as_slice())
.unwrap_or(&[])
}
fn in_class(&self, class: u32, x: u32) -> bool {
self.cext.get(&class).is_some_and(|s| s.contains(&x))
}
/// The same clauses as `Dl.sat` in `lean/Dl/Check.lean`. `rext` entries are
/// deduplicated when the model is built, so the counting cases compare
/// against a count of DISTINCT successors, which is what `Dl.AtLeast` and
/// `Dl.AtMost` mean.
fn sat(&self, c: &Concept, x: u32) -> bool {
match c {
Concept::Top => true,
Concept::Bottom => false,
Concept::Atom(a) => self.in_class(*a, x),
Concept::NegAtom(a) => !self.in_class(*a, x),
Concept::And(cs) => cs.iter().all(|d| self.sat(d, x)),
Concept::Or(cs) => cs.iter().any(|d| self.sat(d, x)),
Concept::Exists(r, f) => self.successors(*r, x).iter().any(|&y| self.sat(f, y)),
Concept::ForAll(r, f) => self.successors(*r, x).iter().all(|&y| self.sat(f, y)),
Concept::MinCard(r, n, f) => {
self.successors(*r, x).iter().filter(|&&y| self.sat(f, y)).count() >= *n as usize
}
Concept::MaxCard(r, n, f) => {
self.successors(*r, x).iter().filter(|&&y| self.sat(f, y)).count() <= *n as usize
}
}
}
/// The same clauses as `Dl.holds`.
fn holds(&self, a: &DlAxiom) -> bool {
match a {
DlAxiom::Sub(c, d) => self.dom.iter().all(|&x| !self.sat(c, x) || self.sat(d, x)),
DlAxiom::Disjoint(c, d) => {
self.dom.iter().all(|&x| !(self.sat(c, x) && self.sat(d, x)))
}
DlAxiom::Domain(r, c) => self
.dom
.iter()
.all(|&x| self.successors(*r, x).is_empty() || self.sat(c, x)),
DlAxiom::Range(r, c) => self
.dom
.iter()
.all(|&x| self.successors(*r, x).iter().all(|&y| self.sat(c, y))),
DlAxiom::SubRole(r, s) => self.dom.iter().all(|&x| {
self.successors(*r, x)
.iter()
.all(|y| self.successors(*s, x).contains(y))
}),
DlAxiom::Trans(r) => self.dom.iter().all(|&x| {
self.successors(*r, x).iter().all(|&y| {
self.successors(*r, y)
.iter()
.all(|z| self.successors(*r, x).contains(z))
})
}),
DlAxiom::Sym(r) => self.dom.iter().all(|&x| {
self.successors(*r, x)
.iter()
.all(|&y| self.successors(*r, y).contains(&x))
}),
DlAxiom::Inv(r, s) => {
self.dom.iter().all(|&x| {
self.successors(*r, x)
.iter()
.all(|&y| self.successors(*s, y).contains(&x))
}) && self.dom.iter().all(|&x| {
self.successors(*s, x)
.iter()
.all(|&y| self.successors(*r, y).contains(&x))
})
}
DlAxiom::InvFunc(r) => self.dom.iter().all(|&y| {
self.dom
.iter()
.filter(|&&x| self.successors(*r, x).contains(&y))
.count()
<= 1
}),
DlAxiom::Inst(i, c) => self.ind.get(i).is_some_and(|&x| self.sat(c, x)),
DlAxiom::Rel(a1, r, b1) => match (self.ind.get(a1), self.ind.get(b1)) {
(Some(&x), Some(&y)) => self.successors(*r, x).contains(&y),
_ => false,
},
DlAxiom::Indiv(i) => self.ind.get(i).is_some_and(|x| self.domset.contains(x)),
DlAxiom::NonEmpty(c) => self.dom.iter().any(|&x| self.sat(c, x)),
}
}
/// The same clauses as `Dl.checkWF`. Returns the first failure.
fn well_formed(&self, axioms: &[DlAxiom]) -> Result<(), String> {
if self.dom.is_empty() {
return Err("the domain is empty".to_string());
}
for (class, members) in &self.cext {
if let Some(bad) = members.iter().find(|m| !self.domset.contains(m)) {
return Err(format!(
"class {class} has member n{bad} outside the domain"
));
}
}
for (&(role, from), targets) in &self.rext {
if !self.domset.contains(&from) {
return Err(format!("role {role} has an edge from n{from}, outside the domain"));
}
if let Some(bad) = targets.iter().find(|t| !self.domset.contains(t)) {
return Err(format!("role {role} has an edge to n{bad}, outside the domain"));
}
}
for a in axioms {
let inds: Vec<u32> = match a {
DlAxiom::Inst(i, _) | DlAxiom::Indiv(i) => vec![*i],
DlAxiom::Rel(x, _, y) => vec![*x, *y],
_ => vec![],
};
for i in inds {
match self.ind.get(&i) {
Some(x) if self.domset.contains(x) => {}
_ => {
return Err(format!(
"individual {i} has no denotation inside the domain"
));
}
}
}
}
Ok(())
}
}
// ── Reading a completion graph off a finished tableau ────────────────────
impl Tableau {
/// Fold blocked nodes into the nodes that block them, and return the
/// surviving nodes with their labels and edges.
///
/// A blocked node is never expanded, so its label can carry an `∃R.C` with
/// no `R`-successor: the completion graph as it stands is NOT an
/// interpretation. The standard repair is to send the edge that reaches the
/// blocked node to its blocker instead. Pairwise blocking requires the two
/// labels to be EQUAL, not merely included, so the redirect moves the edge
/// to a node carrying exactly the same constraints.
///
/// That argument is why the fold is worth doing at all. It is not why the
/// result is trusted: the caller checks the folded interpretation against
/// the axioms and refuses to emit if it does not hold. SHIQ has no finite
/// model property, so for some inputs no fold can work, and refusing is the
/// correct outcome there rather than a bug.
fn folded_graph(&self) -> Result<FoldedGraph, String> {
let resolve = |mut n: u32| -> Result<u32, String> {
let mut steps = 0usize;
while let Some(b) = self.blocker_of(n) {
n = b;
steps += 1;
if steps > self.nodes.len() + 1 {
return Err("a blocking chain did not terminate".to_string());
}
}
Ok(n)
};
let mut roots: Vec<u32> = self
.nodes
.iter()
.filter(|(_, n)| n.parent.is_none())
.map(|(&id, _)| id)
.collect();
roots.sort_unstable();
if roots.is_empty() {
return Err("the completion graph has no root node".to_string());
}
let mut kept: Vec<u32> = Vec::new();
let mut seen: HashSet<u32> = HashSet::new();
let mut edges: Vec<(u32, u32, u32)> = Vec::new();
let mut queue: Vec<u32> = Vec::new();
for r in roots {
let r = resolve(r)?;
if seen.insert(r) {
kept.push(r);
queue.push(r);
}
}
while let Some(x) = queue.pop() {
let Some(node) = self.nodes.get(&x) else {
return Err(format!("node {x} is referenced but absent"));
};
let mut roles: Vec<u32> = node.edges.keys().copied().collect();
roles.sort_unstable();
for role in roles {
let mut targets: Vec<u32> = node.edges[&role].iter().copied().collect();
targets.sort_unstable();
for t in targets {
let t = resolve(t)?;
edges.push((x, role, t));
if seen.insert(t) {
kept.push(t);
queue.push(t);
}
}
}
}
kept.sort_unstable();
edges.sort_unstable();
edges.dedup();
Ok((kept, edges))
}
}
// ── Closing the role extensions ─────────────────────────────────────────
/// Add every edge the role axioms force: super-roles, inverses (a symmetric role
/// is its own inverse here) and transitive closure.
///
/// The completion graph carries only the edges the tableau rules created, and
/// `Tableau::successors` reads the rest off the role hierarchy and the parent
/// back-link as it goes. A finite interpretation has to carry them, because
/// `subrole`, `inv`, `sym` and `trans` are axioms the checker will evaluate.
///
/// The cap is not a nicety. Closing a transitive role over a completion graph
/// can square the edge count, and a certificate nobody can read is no better
/// than none.
fn close_roles(
src: &AxiomSource,
raw: &[(u32, u32, u32)],
cap: usize,
) -> Result<HashSet<(u32, u32, u32)>, String> {
let mut super_of: HashMap<u32, HashSet<u32>> = HashMap::new();
for (&sub, sups) in &src.sub_to_super {
let mut seen: HashSet<u32> = HashSet::new();
let mut stack: Vec<u32> = sups.iter().copied().collect();
while let Some(x) = stack.pop() {
if seen.insert(x)
&& let Some(next) = src.sub_to_super.get(&x)
{
stack.extend(next.iter().copied());
}
}
seen.remove(&sub);
super_of.insert(sub, seen);
}
let mut all: HashSet<(u32, u32, u32)> = raw.iter().copied().collect();
let mut work: Vec<(u32, u32, u32)> = all.iter().copied().collect();
while let Some((x, r, y)) = work.pop() {
if all.len() > cap {
return Err(format!(
"closing the role extensions passed {cap} edges; no finite interpretation \
small enough to certify was produced"
));
}
let mut add: Vec<(u32, u32, u32)> = Vec::new();
if let Some(sups) = super_of.get(&r) {
for &s in sups {
add.push((x, s, y));
}
}
if let Some(&inv) = src.inverse_roles.get(&r) {
add.push((y, inv, x));
}
if src.transitive_roles.contains(&r) {
for &(a, rr, b) in all.iter() {
if rr != r {
continue;
}
if b == x {
add.push((a, r, y));
}
if a == y {
add.push((x, r, b));
}
}
}
for e in add {
if all.insert(e) {
work.push(e);
}
}
}
Ok(all)
}
// ── The public entry points ─────────────────────────────────────────────
impl DlReasoner {
/// The TBox axioms, as the OWL parser read them, in the `lean/Dl` fragment.
fn tbox_axioms(&self) -> Vec<DlAxiom> {
let s = &self.source;
let mut out: Vec<DlAxiom> = Vec::new();
for (sub, sup) in &s.axioms {
out.push(DlAxiom::Sub(sub.clone(), sup.clone()));
}
for (a, b) in &s.disjoint_pairs {
out.push(DlAxiom::Disjoint(a.clone(), b.clone()));
}
for (r, c) in &s.role_domains {
out.push(DlAxiom::Domain(*r, c.clone()));
}
for (r, c) in &s.role_ranges {
out.push(DlAxiom::Range(*r, c.clone()));
}
let mut subrole: Vec<(u32, u32)> = Vec::new();
for (&sub, sups) in &s.sub_to_super {
for &sup in sups {
if sub != sup {
subrole.push((sub, sup));
}
}
}
subrole.sort_unstable();
for (sub, sup) in subrole {
out.push(DlAxiom::SubRole(sub, sup));
}
let mut trans: Vec<u32> = s.transitive_roles.iter().copied().collect();
trans.sort_unstable();
for r in trans {
out.push(DlAxiom::Trans(r));
}
// `inverse_roles` holds both directions, and a symmetric role appears as
// its own inverse. Emit each pair once, and a symmetric role as `sym`,
// which is the same condition stated in the form a reader expects.
let mut invs: Vec<(u32, u32)> = s.inverse_roles.iter().map(|(&a, &b)| (a, b)).collect();
invs.sort_unstable();
for (a, b) in invs {
if a == b {
out.push(DlAxiom::Sym(a));
} else if a < b {
out.push(DlAxiom::Inv(a, b));
}
}
// A functional role is exactly `⊤ ⊑ ≤1 R.⊤`, so it needs no constructor
// of its own. Inverse functionality does: `≤1 R⁻.⊤` is not expressible
// as a concept unless `R` happens to have a named inverse.
let mut func: Vec<u32> = s.functional_roles.iter().copied().collect();
func.sort_unstable();
for r in func {
out.push(DlAxiom::Sub(
Concept::Top,
Concept::MaxCard(r, 1, Box::new(Concept::Top)),
));
}
let mut invfunc: Vec<u32> = s.inv_functional_roles.iter().copied().collect();
invfunc.sort_unstable();
for r in invfunc {
out.push(DlAxiom::InvFunc(r));
}
out
}
/// The TBox axioms plus the ABox: class assertions, role assertions, and one
/// `indiv` line per named individual so that a model is forced to contain it.
fn abox_axioms(&self) -> Vec<DlAxiom> {
let mut out = self.tbox_axioms();
let mut inds: Vec<u32> = self.individual_types.keys().copied().collect();
for &i in self.individual_anon_types.keys() {
inds.push(i);
}
for &(a, _, b) in &self.role_assertions {
inds.push(a);
inds.push(b);
}
inds.sort_unstable();
inds.dedup();
for i in inds {
out.push(DlAxiom::Indiv(i));
}
let mut typed: Vec<(u32, Vec<u32>)> = self
.individual_types
.iter()
.map(|(&i, ts)| {
let mut v: Vec<u32> = ts.iter().copied().collect();
v.sort_unstable();
(i, v)
})
.collect();
typed.sort_unstable();
for (i, ts) in typed {
for t in ts {
out.push(DlAxiom::Inst(i, Concept::Atom(t)));
}
}
let mut anon: Vec<(u32, Vec<Concept>)> = self
.individual_anon_types
.iter()
.map(|(&i, cs)| (i, cs.clone()))
.collect();
anon.sort_unstable_by_key(|(i, _)| *i);
for (i, cs) in anon {
for c in cs {
out.push(DlAxiom::Inst(i, c));
}
}
let mut rels: Vec<(u32, u32, u32)> = self.role_assertions.clone();
rels.sort_unstable();
rels.dedup();
for (a, r, b) in rels {
out.push(DlAxiom::Rel(a, r, b));
}
out
}
/// Build the finite interpretation, check it here, and write the two files.
/// Nothing is written unless the check passes.
fn emit(
&self,
tableau: &Tableau,
ind_to_node: &HashMap<u32, u32>,
axioms: Vec<DlAxiom>,
dir: &Path,
) -> anyhow::Result<ModelOutcome> {
let (kept, raw_edges) = match tableau.folded_graph() {
Ok(v) => v,
Err(e) => return Ok(ModelOutcome::Refused(e)),
};
if kept.is_empty() {
return Ok(ModelOutcome::Refused(
"the completion graph is empty, so there is no interpretation to hand over"
.to_string(),
));
}
let domset: HashSet<u32> = kept.iter().copied().collect();
let closed = match close_roles(&self.source, &raw_edges, 200_000) {
Ok(v) => v,
Err(e) => return Ok(ModelOutcome::Refused(e)),
};
let mut rext: HashMap<(u32, u32), Vec<u32>> = HashMap::new();
for (x, r, y) in closed {
if !domset.contains(&x) || !domset.contains(&y) {
return Ok(ModelOutcome::Refused(format!(
"closing the role extensions produced an edge outside the folded domain \
(n{x} to n{y}); the completion graph does not fold into a finite model"
)));
}
rext.entry((r, x)).or_default().push(y);
}
for v in rext.values_mut() {
v.sort_unstable();
v.dedup();
}
let mut cext: HashMap<u32, HashSet<u32>> = HashMap::new();
for &n in &kept {
let Some(node) = tableau.nodes.get(&n) else {
return Ok(ModelOutcome::Refused(format!("node {n} vanished")));
};
for label in &node.labels {
if let Concept::Atom(a) = label {
cext.entry(*a).or_default().insert(n);
}
}
}
let mut ind: HashMap<u32, u32> = HashMap::new();
for (&i, &n) in ind_to_node {
// An individual whose node was folded away denotes the node it was
// folded into. Roots are never blocked, and every individual is a
// root, so in practice this is the identity; it is written out
// rather than assumed.
let mut cur = n;
let mut steps = 0usize;
while let Some(b) = tableau.blocker_of(cur) {
cur = b;
steps += 1;
if steps > tableau.nodes.len() + 1 {
return Ok(ModelOutcome::Refused(
"a blocking chain under a named individual did not terminate".to_string(),
));
}
}
if !domset.contains(&cur) {
return Ok(ModelOutcome::Refused(format!(
"individual {} has no node in the folded domain",
self.interner.resolve(i)
)));
}
ind.insert(i, cur);
}
let model = FiniteModel {
dom: kept.clone(),
domset,
cext,
rext,
ind,
};
// Every name that appears in either file has to survive the round trip.
// `owl:hasValue` is approximated by an atom named after the individual,
// and that individual can be a literal with a space in it.
//
// The check is AT THE POINT OF WRITING. It used to be a separate walk
// over every axiom variant plus `model.rext` and `model.cext`, with
// individuals in `model.ind` covered only because `DlAxiom::Indiv(i)`
// happens to be emitted for every individual that reaches the model:
// TCB-26, an argument about two loops agreeing rather than a check.
// Building the text first and letting `push_name` record the first
// refusal makes the coverage question disappear, because `push_name` is
// the only way a name reaches either buffer.
let mut bad: Option<String> = None;
let mut axiom_text = String::new();
for a in &axioms {
axiom_text.push_str(&axiom_line(&self.interner, a, &mut bad));
axiom_text.push('\n');
}
let mut model_text = String::new();
for &n in &model.dom {
model_text.push_str(&format!("domain\tn{n}\n"));
}
let mut classes: Vec<(u32, Vec<u32>)> = model
.cext
.iter()
.map(|(&c, ms)| {
let mut v: Vec<u32> = ms.iter().copied().collect();
v.sort_unstable();
(c, v)
})
.collect();
classes.sort_unstable();
for (c, ms) in classes {
for m in ms {
model_text.push_str("class\t");
push_name(&mut model_text, &self.interner, c, &mut bad);
model_text.push_str(&format!("\tn{m}\n"));
}
}
let mut edge_lines: Vec<(u32, u32, u32)> = Vec::new();
for (&(r, x), ys) in &model.rext {
for &y in ys {
edge_lines.push((x, r, y));
}
}
edge_lines.sort_unstable();
let edge_count = edge_lines.len();
for (x, r, y) in edge_lines {
model_text.push_str(&format!("edge\tn{x}\t"));
push_name(&mut model_text, &self.interner, r, &mut bad);
model_text.push_str(&format!("\tn{y}\n"));
}
let mut ind_lines: Vec<(u32, u32)> = model.ind.iter().map(|(&i, &n)| (i, n)).collect();
ind_lines.sort_unstable();
for (i, n) in ind_lines {
model_text.push_str("ind\t");
push_name(&mut model_text, &self.interner, i, &mut bad);
model_text.push_str(&format!("\tn{n}\n"));
}
// Nothing has been written yet, so a refusal here writes nothing. The
// order is the order it always was: the name guard decides before the
// semantics gate does.
if let Some(bad) = bad {
return Ok(ModelOutcome::Refused(format!(
"the name {bad:?} carries whitespace, so it would not survive the \
tab-and-space separated format; nothing was written"
)));
}
// The gate. A certificate that will not check is worse than no
// certificate, so the emitter runs the same semantics the checker does
// and refuses when it does not hold.
if let Err(why) = model.well_formed(&axioms) {
return Ok(ModelOutcome::Refused(format!(
"the folded completion graph is not a finite interpretation: {why}"
)));
}
if let Some(bad) = axioms.iter().find(|a| !model.holds(a)) {
return Ok(ModelOutcome::Refused(format!(
"the folded completion graph does not satisfy the axiom `{}`",
axiom_line(&self.interner, bad, &mut None).replace('\t', " ")
)));
}
std::fs::create_dir_all(dir)?;
std::fs::write(dir.join("axioms.tsv"), axiom_text)?;
std::fs::write(dir.join("model.tsv"), model_text)?;
Ok(ModelOutcome::Certified {
axioms: axioms.len(),
domain: model.dom.len(),
edges: edge_count,
})
}
/// Certify that `class_iri` is satisfiable with respect to the TBox.
///
/// The claim is written into the axiom set as `nonempty`, so a checker that
/// accepts the certificate has verified the reasoner's actual answer and not
/// merely that the TBox has some model. The ABox is NOT part of this
/// certificate: classification in this reasoner is a TBox question, the
/// completion graph has no named individuals in it, and pretending otherwise
/// would produce a certificate that cannot check.
pub fn certify_class_satisfiable(
&self,
class_iri: &str,
dir: &Path,
) -> anyhow::Result<ModelOutcome> {
let Some(&cid) = self.interner.to_id.get(class_iri) else {
anyhow::bail!("no class named {class_iri} in this ontology");
};
let concept = Concept::Atom(cid);
let mut tableau = Tableau::with_deadline(Arc::clone(&self.tbox), self.phase_deadline());
tableau.capture = true;
match tableau.decide(&concept) {
Verdict::Unsatisfiable => return Ok(ModelOutcome::Refuted),
Verdict::Unknown => return Ok(ModelOutcome::Undetermined),
Verdict::Satisfiable => {}
}
let mut axioms = self.tbox_axioms();
axioms.push(DlAxiom::NonEmpty(concept));
self.emit(&tableau, &HashMap::new(), axioms, dir)
}
/// The internal id of a named class, by IRI, for callers that hold a name
/// and need the id `explain_unsatisfiable` takes. Matches the spelling
/// `named_class_names` returns, angle brackets and all, and also the bare
/// IRI, because a caller that has one rarely has the other.
pub fn named_class_id(&self, iri: &str) -> Option<u32> {
let bare = iri.trim_start_matches('<').trim_end_matches('>');
self.named_classes
.iter()
.copied()
.find(|&id| self.interner.resolve(id).trim_start_matches('<').trim_end_matches('>') == bare)
}
/// The named classes, in the interner's order, so a caller can certify each
/// one. `run` uses it because TBox consistency alone is witnessed by a
/// single point with empty extensions, which is honest and uninformative.
pub fn named_class_names(&self) -> Vec<String> {
let mut v: Vec<String> = self
.named_classes
.iter()
.map(|id| self.interner.resolve(*id).to_string())
.collect();
v.sort();
v
}
/// The OWL constructs present in the graph that this certificate layer does
/// not model, with a count of each.
///
/// This matters more than it looks. The emitter certifies that a finite
/// interpretation satisfies THE AXIOMS IT EMITTED, and a construct the
/// parser does not recognise is absent from both sides. So an ontology
/// leaning on nominals, role chains, `owl:sameAs` or datatypes gets a
/// perfectly valid certificate about a WEAKER axiom set than the one it
/// actually states, and a reader who is not told that will draw a stronger
/// conclusion than the proof supports. Naming them in a source comment is
/// not enough: it has to be in the report, next to the verdict.
pub fn unmodelled_constructs(graph: &Arc<GraphStore>) -> Vec<(String, u64)> {
// `owl:AsymmetricProperty` sits here rather than in the tableau, and the
// choice is worth stating. Asymmetry is a constraint on a PAIR of edges
// (`a r b` forbids `b r a`), not a concept membership, so unlike every
// characteristic the tableau does model it cannot be expressed as a label
// on a node in SHIQ without nominals — the ALCOIQ encoding needs `{a}` to
// say "the r-successor that is this individual". Modelling it would mean
// a new edge-level clash rule and a new termination argument. Declaring it
// costs a line and is honest, which is what this list is for. Until it was
// added here it was in NEITHER place: not implemented, and not declared,
// so an ontology leaning on asymmetry got a clean verdict with no sign
// that a constraint had been dropped. That is the one outcome this list
// exists to prevent.
const NOT_MODELLED: [(&str, &str); 13] = [
("owl:sameAs", "http://www.w3.org/2002/07/owl#sameAs"),
("owl:differentFrom", "http://www.w3.org/2002/07/owl#differentFrom"),
("owl:oneOf", "http://www.w3.org/2002/07/owl#oneOf"),
("owl:hasValue", "http://www.w3.org/2002/07/owl#hasValue"),
// Read as an opaque atom, which is sound and says nothing about
// the individual being its own successor.
("owl:hasSelf", "http://www.w3.org/2002/07/owl#hasSelf"),
("owl:propertyChainAxiom", "http://www.w3.org/2002/07/owl#propertyChainAxiom"),
("owl:hasKey", "http://www.w3.org/2002/07/owl#hasKey"),
("owl:ReflexiveProperty", "http://www.w3.org/2002/07/owl#ReflexiveProperty"),
("owl:IrreflexiveProperty", "http://www.w3.org/2002/07/owl#IrreflexiveProperty"),
("owl:AsymmetricProperty", "http://www.w3.org/2002/07/owl#AsymmetricProperty"),
// Disjointness of ROLES is an edge-level constraint, like asymmetry.
("owl:propertyDisjointWith", "http://www.w3.org/2002/07/owl#propertyDisjointWith"),
("owl:AllDisjointProperties", "http://www.w3.org/2002/07/owl#AllDisjointProperties"),
// The n-ary form of `owl:differentFrom`, already listed above.
("owl:AllDifferent", "http://www.w3.org/2002/07/owl#AllDifferent"),
];
let mut found = Vec::new();
for (label, iri) in NOT_MODELLED {
let q = format!(
"SELECT (COUNT(*) AS ?n) WHERE {{ {{ ?s <{iri}> ?o }} UNION {{ ?s ?p <{iri}> }} }}"
);
let Ok(raw) = graph.sparql_select_union(&q) else { continue };
let Ok(v) = serde_json::from_str::<serde_json::Value>(&raw) else { continue };
let n = v["results"][0]["n"]
.as_str()
.and_then(|s| s.trim_matches('"').split('"').next())
.and_then(|s| s.parse::<u64>().ok())
.unwrap_or(0);
if n > 0 {
found.push((label.to_string(), n));
}
}
let q = "SELECT (COUNT(*) AS ?n) WHERE { ?r <http://www.w3.org/2002/07/owl#onProperty> ?p . \
?p a <http://www.w3.org/2002/07/owl#DatatypeProperty> }";
if let Ok(raw) = graph.sparql_select_union(q)
&& let Ok(v) = serde_json::from_str::<serde_json::Value>(&raw)
{
let n = v["results"][0]["n"]
.as_str()
.and_then(|s| s.trim_matches('"').split('"').next())
.and_then(|s| s.parse::<u64>().ok())
.unwrap_or(0);
if n > 0 {
// Read as a role to an opaque class: sound, and blind to
// values, so no datatype clash or value count is ever found.
found.push(("datatype restriction".to_string(), n));
}
}
found
}
/// Certify that the TBox is consistent.
///
/// No `nonempty` line is needed: `Dl.WellFormed` already requires the domain
/// to be non-empty, so a model of the axiom set alone is exactly what TBox
/// consistency asserts.
///
/// This paragraph was stranded: it sat above `named_class_names`, four
/// hundred lines from the function it describes and joined to that
/// function's own doc comment with no blank line, so `cargo doc` printed a
/// block about certification to a reader of a method that returns a list of
/// names, and this method was documented nowhere. It is back where it
/// belongs.
pub fn certify_tbox_consistent(&self, dir: &Path) -> anyhow::Result<ModelOutcome> {
let mut tableau = Tableau::with_deadline(Arc::clone(&self.tbox), self.phase_deadline());
tableau.capture = true;
match tableau.decide(&Concept::Top) {
Verdict::Unsatisfiable => return Ok(ModelOutcome::Refuted),
Verdict::Unknown => return Ok(ModelOutcome::Undetermined),
Verdict::Satisfiable => {}
}
self.emit(&tableau, &HashMap::new(), self.tbox_axioms(), dir)
}
/// Certify that a class is UNSATISFIABLE, which is the answer `emit` cannot
/// certify and never could.
///
/// `certify_class_satisfiable` hands over a model. There is no model to hand
/// over here, so what is handed over is a closed tableau, and the checker
/// that reads it is `oo-dlrefute` rather than `oo-dlmodel`. The two verdicts
/// are different sentences and the two files must never be confused.
///
/// The search that writes the tableau is NOT this reasoner. It is the small
/// independent one in `crate::dl_refute`, over the certified rules only,
/// because blocking and merging are completeness devices a refutation does
/// not need and the certified calculus deliberately lacks. So this can fail
/// to certify an unsatisfiability this reasoner decided, and when it does,
/// the reasoner's answer is unchanged and uncertified, exactly as before.
pub fn certify_class_unsatisfiable(
&self,
class_iri: &str,
dir: &Path,
) -> anyhow::Result<crate::dl_refute::RefuteOutcome> {
let Some(&cid) = self.interner.to_id.get(class_iri) else {
anyhow::bail!("no class named {class_iri} in this ontology");
};
let concept = Concept::Atom(cid);
let mut tableau = Tableau::with_deadline(Arc::clone(&self.tbox), self.phase_deadline());
match tableau.decide(&concept) {
Verdict::Unsatisfiable => {}
Verdict::Unknown => {
return Ok(crate::dl_refute::RefuteOutcome::NotFound(
"the run was undetermined, so there is no negative answer to certify"
.to_string(),
))
}
Verdict::Satisfiable => {
return Ok(crate::dl_refute::RefuteOutcome::NotFound(
"the class is satisfiable; certify the model instead".to_string(),
))
}
}
let mut axioms = self.tbox_axioms();
axioms.push(DlAxiom::NonEmpty(concept));
let mut interner = self.interner.clone();
crate::dl_refute::certify_unsatisfiable(
&axioms,
&mut interner,
dir,
crate::dl_refute::DEFAULT_BUDGET,
)
}
/// Certify that the TBox is INCONSISTENT. The mirror of
/// `certify_tbox_consistent`, and the same caveats apply.
pub fn certify_tbox_inconsistent(
&self,
dir: &Path,
) -> anyhow::Result<crate::dl_refute::RefuteOutcome> {
let mut tableau = Tableau::with_deadline(Arc::clone(&self.tbox), self.phase_deadline());
match tableau.decide(&Concept::Top) {
Verdict::Unsatisfiable => {}
Verdict::Unknown => {
return Ok(crate::dl_refute::RefuteOutcome::NotFound(
"the run was undetermined".to_string(),
))
}
Verdict::Satisfiable => {
return Ok(crate::dl_refute::RefuteOutcome::NotFound(
"the TBox is consistent; certify the model instead".to_string(),
))
}
}
let mut axioms = self.tbox_axioms();
axioms.push(DlAxiom::NonEmpty(Concept::Top));
let mut interner = self.interner.clone();
crate::dl_refute::certify_unsatisfiable(
&axioms,
&mut interner,
dir,
crate::dl_refute::DEFAULT_BUDGET,
)
}
/// Certify that the ABox is INCONSISTENT with the TBox.
pub fn certify_abox_inconsistent(
&self,
dir: &Path,
) -> anyhow::Result<crate::dl_refute::RefuteOutcome> {
let (mut tableau, _, _) = self.build_abox_tableau(Self::global_deadline());
if tableau.expand(0) {
return Ok(crate::dl_refute::RefuteOutcome::NotFound(
"the ABox is consistent; certify the model instead".to_string(),
));
}
if tableau.budget.exhausted {
return Ok(crate::dl_refute::RefuteOutcome::NotFound(
"the run was undetermined".to_string(),
));
}
let mut interner = self.interner.clone();
crate::dl_refute::certify_unsatisfiable(
&self.abox_axioms(),
&mut interner,
dir,
crate::dl_refute::DEFAULT_BUDGET,
)
}
/// Certify that the ABox is consistent with the TBox.
pub fn certify_abox_consistent(&self, dir: &Path) -> anyhow::Result<ModelOutcome> {
// Same three-part test as `check_abox`, and it has to be the same or the
// certificate layer silently declines to certify an ABox the reasoner
// decided. `abox_axioms` already emits one `indiv` line per role-assertion
// endpoint, so refusing here left those axioms with nothing to certify.
if self.individual_types.is_empty()
&& self.individual_anon_types.is_empty()
&& self.role_assertions.is_empty()
{
return Ok(ModelOutcome::Refused(
"this ontology has no ABox, so there is nothing to certify beyond the TBox"
.to_string(),
));
}
let (mut tableau, ind_to_node, _) = self.build_abox_tableau(Self::global_deadline());
tableau.capture = true;
if !tableau.expand(0) {
return Ok(if tableau.budget.exhausted {
ModelOutcome::Undetermined
} else {
ModelOutcome::Refuted
});
}
self.emit(&tableau, &ind_to_node, self.abox_axioms(), dir)
}
}
// ─────────────────────────────────────────────────────────────────────────────
// The model certificate's serialisation boundary
//
// `axioms.tsv` is tab separated at the top level and SPACE separated inside a
// concept, and it carries IRIs and literals. `docs/trusted-computing-base.md`
// calls that TCB-25 and TCB-26: `name_is_safe` is the only explicit injection
// guard in this codebase, and the argument that it covers every name that gets
// written is an argument about two loops agreeing rather than a check.
// ─────────────────────────────────────────────────────────────────────────────
#[cfg(test)]
mod certificate_boundary_tests {
use super::*;
use proptest::prelude::*;
/// Names drawn from exactly the two sides of `name_is_safe`: some that must
/// pass, some that must not, and the grammar's own keywords, which must be
/// harmless because the encoding is prefix and positional rather than
/// delimited.
fn name() -> impl Strategy<Value = String> {
prop_oneof![
Just("<http://e/A>".to_string()),
Just("\"lit\"".to_string()),
Just("_:b0".to_string()),
// Keywords of the concept grammar.
Just("atom".to_string()),
Just("top".to_string()),
Just("not".to_string()),
Just("some".to_string()),
Just("min".to_string()),
Just("2".to_string()),
// Must be refused.
Just("a b".to_string()),
Just("a\tb".to_string()),
Just("a\nb".to_string()),
Just("a\rb".to_string()),
Just(String::new()),
"[^ \t\n\r]{1,5}",
]
}
/// A concept over name SLOTS rather than interned ids, so the shape can be
/// generated once and instantiated against whatever names the case drew.
#[derive(Clone, Debug)]
enum Shape {
Top,
Bot,
Atom(usize),
NegAtom(usize),
And(Vec<Shape>),
Or(Vec<Shape>),
Exists(usize, Box<Shape>),
ForAll(usize, Box<Shape>),
Min(usize, u32, Box<Shape>),
Max(usize, u32, Box<Shape>),
}
fn shape() -> impl Strategy<Value = Shape> {
let leaf = prop_oneof![
Just(Shape::Top),
Just(Shape::Bot),
(0usize..6).prop_map(Shape::Atom),
(0usize..6).prop_map(Shape::NegAtom),
];
leaf.prop_recursive(3, 12, 3, |inner| {
prop_oneof![
prop::collection::vec(inner.clone(), 0..3).prop_map(Shape::And),
prop::collection::vec(inner.clone(), 0..3).prop_map(Shape::Or),
(0usize..6, inner.clone()).prop_map(|(r, f)| Shape::Exists(r, Box::new(f))),
(0usize..6, inner.clone()).prop_map(|(r, f)| Shape::ForAll(r, Box::new(f))),
(0usize..6, 0u32..3, inner.clone())
.prop_map(|(r, n, f)| Shape::Min(r, n, Box::new(f))),
(0usize..6, 0u32..3, inner).prop_map(|(r, n, f)| Shape::Max(r, n, Box::new(f))),
]
})
}
fn build(s: &Shape, ids: &[u32]) -> Concept {
let pick = |i: usize| ids[i % ids.len()];
match s {
Shape::Top => Concept::Top,
Shape::Bot => Concept::Bottom,
Shape::Atom(i) => Concept::Atom(pick(*i)),
Shape::NegAtom(i) => Concept::NegAtom(pick(*i)),
Shape::And(cs) => Concept::And(cs.iter().map(|c| build(c, ids)).collect()),
Shape::Or(cs) => Concept::Or(cs.iter().map(|c| build(c, ids)).collect()),
Shape::Exists(r, f) => Concept::Exists(pick(*r), Box::new(build(f, ids))),
Shape::ForAll(r, f) => Concept::ForAll(pick(*r), Box::new(build(f, ids))),
Shape::Min(r, n, f) => Concept::MinCard(pick(*r), *n, Box::new(build(f, ids))),
Shape::Max(r, n, f) => Concept::MaxCard(pick(*r), *n, Box::new(build(f, ids))),
}
}
/// How many space-separated tokens the encoding in `write_concept` must
/// produce for a concept, derived from the shape alone. Written out here so
/// it is an independent statement of the grammar rather than a second call
/// to the same code.
fn tokens(c: &Concept) -> usize {
match c {
Concept::Top | Concept::Bottom => 1,
Concept::Atom(_) => 2,
Concept::NegAtom(_) => 3,
Concept::And(cs) => nary_tokens(cs, &Concept::Top),
Concept::Or(cs) => nary_tokens(cs, &Concept::Bottom),
Concept::Exists(_, f) | Concept::ForAll(_, f) => 2 + tokens(f),
Concept::MinCard(_, _, f) | Concept::MaxCard(_, _, f) => 3 + tokens(f),
}
}
fn nary_tokens(cs: &[Concept], unit: &Concept) -> usize {
match cs.split_first() {
None => tokens(unit),
Some((head, [])) => tokens(head),
Some((head, rest)) => 1 + tokens(head) + nary_tokens(rest, unit),
}
}
/// TCB-26, as a statement about this file rather than about a run.
///
/// The guard covers every name that is written because `push_name` is the
/// only thing that writes one. This reads the source of the two writers and
/// requires it: no `interner.resolve` may append to a certificate buffer.
/// It is a crude check and it is the one that matches the claim. The
/// previous arrangement — a `names` vector built by one loop and the files
/// written by another — could not be checked this way at all, which is why
/// TCB-26 was listed as trusted rather than tested.
#[test]
fn tcb_26_only_push_name_writes_a_name() {
// Normalise line endings before any of the anchors below are matched.
// git on Windows checks this file out with CRLF by default, and the
// `fn emit(\n` anchor wants a newline immediately after the paren, so
// without this the anchor misses, `expect` fires, and the test fails on
// Windows alone while passing on Linux and macOS. It did exactly that.
let src = std::fs::read_to_string(concat!(env!("CARGO_MANIFEST_DIR"), "/src/tableaux.rs"))
.expect("this file is readable")
.replace("\r\n", "\n");
// The two regions that build certificate text: the serialisers, and the
// emitter that assembles `axioms.tsv` and `model.tsv` out of them.
let ser_start = src.find("// ── Serialisation ──").expect("the serialisation section");
let ser_end = src[ser_start..]
.find("\n// ── The finite interpretation")
.expect("the section after it")
+ ser_start;
let emit_start = src.find(" fn emit(\n").expect("the emitter");
let emit_end = src[emit_start..]
.find("\n /// Certify that `class_iri` is satisfiable")
.expect("the method after it")
+ emit_start;
let regions = [&src[ser_start..ser_end], &src[emit_start..emit_end]];
assert!(regions[0].contains("fn push_name("), "the guard left the serialisers");
assert!(regions[1].contains("axioms.tsv"), "the emitter region is not the emitter");
let mut offenders: Vec<&str> = Vec::new();
for region in regions {
for line in region.lines() {
let t = line.trim();
if !t.contains("resolve(") || t.starts_with("//") {
continue;
}
// The one inside `push_name`, and the one that names an
// individual in an ERROR MESSAGE rather than in a line.
if t == "let s = interner.resolve(id);" || t == "self.interner.resolve(i)" {
continue;
}
offenders.push(line);
}
}
assert!(
offenders.is_empty(),
"a name reaches a certificate buffer without passing `push_name`:\n{}",
offenders.join("\n")
);
}
proptest! {
#![proptest_config(ProptestConfig { cases: 512, ..ProptestConfig::default() })]
/// TCB-25. `name_is_safe` refuses exactly the names that would break the
/// format: empty, or carrying a space, tab, carriage return or newline.
#[test]
fn tcb_25_name_is_safe_refuses_every_separator(n in name()) {
let safe = name_is_safe(&n);
prop_assert_eq!(
safe,
!n.is_empty() && !n.contains([' ', '\t', '\n', '\r'])
);
}
/// TCB-25. Given names the guard accepts, a concept serialises to
/// exactly the number of space-separated tokens its shape determines.
///
/// This is the property that makes the encoding readable back: the
/// grammar is prefix and positional, so a name that happens to be a
/// keyword (`atom`, `top`, `min`) is harmless, and a name carrying a
/// space is not. If the guard ever stopped refusing one, the token count
/// would drift from the shape and the checker would read a different
/// concept from the one the reasoner decided about.
#[test]
fn tcb_25_a_safe_concept_serialises_to_the_tokens_its_shape_demands(
ns in prop::collection::vec(name(), 1..6),
sh in shape(),
) {
let mut interner = Interner::new();
let ids: Vec<u32> = ns.iter().map(|n| interner.intern(n)).collect();
let c = build(&sh, &ids);
let mut bad = None;
let s = concept_string(&interner, &c, &mut bad);
// The condition is now the GUARD's verdict, not the test author's
// recollection of which names the concept happens to mention. That
// is TCB-26: `push_name` is the only way a name reaches the buffer,
// so `bad` is set exactly when the buffer carries an unsafe one.
if bad.is_none() {
prop_assert_eq!(
s.split(' ').count(), tokens(&c),
"token count drifted from the shape: {:?}", s
);
prop_assert!(!s.contains('\t') && !s.contains('\n') && !s.contains('\r'));
} else {
prop_assert!(
ns.iter().any(|n| !name_is_safe(n)),
"the guard refused {:?} but every name is safe", s
);
}
}
/// TCB-25 for `axiom_line`. Every axiom is a tab-separated record whose
/// field count its variant fixes, so a name carrying a tab would add a
/// field and the checker would read a different axiom.
#[test]
fn tcb_25_an_axiom_line_has_the_fields_its_variant_fixes(n in name()) {
let mut interner = Interner::new();
let id = interner.intern(&n);
let c = Concept::Atom(id);
let cases: Vec<(DlAxiom, usize)> = vec![
(DlAxiom::Sub(c.clone(), c.clone()), 3),
(DlAxiom::Disjoint(c.clone(), c.clone()), 3),
(DlAxiom::Domain(id, c.clone()), 3),
(DlAxiom::Range(id, c.clone()), 3),
(DlAxiom::SubRole(id, id), 3),
(DlAxiom::Trans(id), 2),
(DlAxiom::Sym(id), 2),
(DlAxiom::Inv(id, id), 3),
(DlAxiom::InvFunc(id), 2),
(DlAxiom::Inst(id, c.clone()), 3),
(DlAxiom::Rel(id, id, id), 4),
(DlAxiom::Indiv(id), 2),
(DlAxiom::NonEmpty(c), 2),
];
for (a, want) in cases {
let mut bad = None;
let line = axiom_line(&interner, &a, &mut bad);
// Every one of these variants mentions the generated name, so
// the guard's verdict and the name's safety have to agree. That
// is the TCB-26 claim: no variant writes a name the guard did
// not see, and none reports one it did not write.
prop_assert_eq!(bad.is_none(), name_is_safe(&n), "{:?}", line);
if bad.is_none() {
prop_assert_eq!(
line.split('\t').count(), want,
"{:?} is not {} tab-separated fields", line, want
);
prop_assert!(!line.contains('\n') && !line.contains('\r'));
}
}
}
}
}
#[cfg(test)]
mod pair_sweep_tests {
use super::*;
use std::sync::atomic::AtomicUsize;
fn never() -> bool {
false
}
/// The pairs listed rows stand for, in the order given.
fn rows_of(pairs: &[(u32, u32)]) -> Vec<PairRow<'static>> {
pairs.iter().map(|&(sub, sup)| PairRow::listed(sub, vec![sup])).collect()
}
/// An undecided subsumption test is reported as undecided, not dropped.
///
/// The old sweep kept a pair when its verdict `.is_unsat()` and discarded
/// everything else, so the `Unknown` pair below vanished exactly as the
/// refuted one did and the sweep could not say it had been cut short.
#[test]
fn an_unknown_pair_is_kept_apart_from_a_refuted_one() {
let rows = rows_of(&[(1, 2), (1, 3), (2, 3), (3, 1)]);
let sweep = sweep_pairs(&rows, never, |sub, sup| match (sub, sup) {
(1, 2) => Verdict::Unsatisfiable,
(1, 3) => Verdict::Unknown,
(3, 1) => Verdict::Unknown,
_ => Verdict::Satisfiable,
});
assert_eq!(sweep.inferred, vec![(1, 2)]);
assert_eq!(sweep.undetermined, vec![(1, 3), (3, 1)]);
assert_eq!((sweep.tested, sweep.not_reached), (4, 0));
}
/// A sweep in which every test was decided has nothing to report.
#[test]
fn a_fully_decided_sweep_reports_no_undetermined_pair() {
let rows = rows_of(&[(1, 2), (2, 1)]);
let sweep = sweep_pairs(&rows, never, |sub, _| {
if sub == 1 { Verdict::Unsatisfiable } else { Verdict::Satisfiable }
});
assert_eq!(sweep.inferred, vec![(1, 2)]);
assert!(sweep.undetermined.is_empty());
assert_eq!(sweep.not_reached, 0);
}
/// A row with no model stands for every other class in the pool that is
/// not excluded, and its count says so without walking the pool.
#[test]
fn a_row_with_no_model_counts_exactly_the_pairs_it_would_generate() {
let pool: Vec<u32> = (0..50).collect();
let pool_set: HashSet<u32> = pool.iter().copied().collect();
// 7 is the class itself, 99 is outside the pool, 3 and 7 are in it.
let exclude: HashSet<u32> = [3, 7, 99].into_iter().collect();
let row = PairRow::every(7, &pool, &pool_set, Some(&exclude));
assert_eq!(row.count, 48, "50 classes, less 7 itself, less 3");
let sweep = sweep_pairs(&[row], never, |_, _| Verdict::Satisfiable);
assert_eq!(sweep.tested, 48);
assert_eq!(sweep.not_reached, 0);
let row = PairRow::every(7, &pool, &pool_set, None);
assert_eq!(row.count, 49);
}
/// #340: once the deadline has passed, the sweep stops building tableaux.
///
/// The old sweep called `decide` on every pair, and after the phase
/// deadline each call built a tableau that returned `Unknown` from its
/// first step: 27.5 million of them under a 200 ms budget. Here the clock
/// expires after `BUDGET` calls. A call already in flight on another
/// worker when it expires may still complete, so the bound is `BUDGET`
/// plus one per worker, and everything else must be counted, not tested.
#[test]
fn a_sweep_whose_deadline_passes_stops_deciding_and_counts_the_rest() {
const BUDGET: usize = 100;
let pool: Vec<u32> = (0..2_000).collect();
let pool_set: HashSet<u32> = pool.iter().copied().collect();
let mut rows: Vec<PairRow<'_>> = (0..2_000)
.map(|sub| PairRow::every(sub, &pool, &pool_set, None))
.collect();
rows.push(PairRow::listed(5, vec![6, 7, 8]));
let total: usize = rows.iter().map(|r| r.count).sum();
assert_eq!(total, 2_000 * 1_999 + 3);
let calls = AtomicUsize::new(0);
let sweep = sweep_pairs(
&rows,
|| calls.load(Ordering::SeqCst) >= BUDGET,
|sub, sup| {
calls.fetch_add(1, Ordering::SeqCst);
// Never a proof: nothing below may be reported as inferred
// unless a decided call said so.
if sub == 0 && sup == 1 { Verdict::Unsatisfiable } else { Verdict::Satisfiable }
},
);
let made = calls.load(Ordering::SeqCst);
let workers = rayon::current_num_threads();
assert!(
made <= BUDGET + workers,
"{made} tableaux built after a deadline that passed at {BUDGET}; the sweep \
kept deciding pairs it could only have answered Unknown"
);
assert_eq!(sweep.tested, made, "every call is counted as tested");
assert_eq!(
sweep.tested + sweep.not_reached,
total,
"every pair is either tested or counted as not reached"
);
assert!(sweep.not_reached >= total - BUDGET - workers);
assert!(sweep.undetermined.is_empty(), "no tested pair came back Unknown");
assert!(
sweep.inferred.iter().all(|&p| p == (0, 1)),
"only a decided Unsatisfiable may be inferred: {:?}",
sweep.inferred
);
}
/// A deadline already gone when the sweep starts: no tableau at all, and
/// every pair counted from the rows' counts.
#[test]
fn a_sweep_that_starts_after_its_deadline_builds_nothing() {
let pool: Vec<u32> = (0..300).collect();
let pool_set: HashSet<u32> = pool.iter().copied().collect();
let rows: Vec<PairRow<'_>> =
(0..300).map(|sub| PairRow::every(sub, &pool, &pool_set, None)).collect();
let sweep = sweep_pairs(&rows, || true, |_, _| {
panic!("a tableau was built after the deadline had passed")
});
assert_eq!(sweep.tested, 0);
assert_eq!(sweep.not_reached, 300 * 299);
assert!(sweep.inferred.is_empty() && sweep.undetermined.is_empty());
}
/// The clock a phase deadline belongs to is read off the instant itself.
#[test]
fn an_expired_deadline_names_its_clock() {
let past = Instant::now() - std::time::Duration::from_millis(5);
let later = Instant::now() + std::time::Duration::from_secs(3600);
assert_eq!(expired_clock(Some(past), Some(past)), Some("global"));
assert_eq!(expired_clock(Some(past), Some(later)), Some("phase"));
assert_eq!(expired_clock(Some(past), None), Some("phase"));
assert_eq!(expired_clock(Some(later), Some(later)), None);
assert_eq!(expired_clock(None, Some(past)), None);
}
}