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
//! The goal-free form: which CONCLUSIONS a projection preserves.
//!
//! `src/projection_entailment.rs` asks the question of a supplied goal set, for
//! auditing one answer. This asks it of everything at once, for auditing a
//! retrieval STRATEGY, because a strategy is not evaluated against one question.
//!
//! Every gate here is shown failing on deliberately broken input, and the
//! verdict discipline is enforced over the SERIALISED report rather than over
//! the enum, because the enum is where the discipline is easy and the
//! serialisation is where it leaks.
mod common;
use open_ontologies::closure_diff as cd;
use open_ontologies::closure_diff::DiffOptions;
use open_ontologies::graph::GraphStore;
use std::collections::{HashMap, HashSet};
use std::path::{Path, PathBuf};
use std::process::Command;
use std::sync::{Arc, Mutex, MutexGuard, OnceLock};
/// See `tests/lean_projection_entailment_test.rs`: the iteration cap is a
/// process-wide atomic and one test here moves it.
fn serial() -> MutexGuard<'static, ()> {
static LOCK: Mutex<()> = Mutex::new(());
LOCK.lock().unwrap_or_else(|e| e.into_inner())
}
fn repo() -> PathBuf {
PathBuf::from(env!("CARGO_MANIFEST_DIR"))
}
fn lean_dir() -> PathBuf {
repo().join("lean")
}
fn lake_available() -> bool {
// `.current_dir(lean_dir())`: elan resolves the toolchain from the working
// directory, and the crate root is the one directory with no
// `lean-toolchain` in its ancestry.
Command::new("lake")
.arg("--version")
.current_dir(lean_dir())
.output()
.map(|o| o.status.success())
.unwrap_or(false)
}
fn skip() -> bool {
common::skip_unless(
lake_available(),
"lake (the Lean 4 build tool)",
"install elan from https://github.com/leanprover/elan; lean/lean-toolchain pins the version",
)
}
fn checker() -> &'static Path {
static BUILT: OnceLock<PathBuf> = OnceLock::new();
BUILT.get_or_init(|| {
let out = Command::new("lake")
.arg("build")
.current_dir(lean_dir())
.output()
.expect("run lake build");
assert!(out.status.success(), "lake build failed:\n{}", String::from_utf8_lossy(&out.stderr));
let exe = lean_dir().join(".lake").join("build").join("bin").join("oo-cert");
assert!(exe.exists());
exe
})
}
fn scratch(name: &str) -> PathBuf {
let d = std::env::temp_dir().join(format!("oo-cd-{name}-{}", std::process::id()));
let _ = std::fs::remove_dir_all(&d);
std::fs::create_dir_all(&d).unwrap();
d
}
fn loaded(ttl: &str) -> Arc<GraphStore> {
let g = Arc::new(GraphStore::new());
g.load_turtle(ttl, None).unwrap();
g
}
fn opts(name: &str) -> DiffOptions {
DiffOptions { out: scratch(name), ..Default::default() }
}
const P: &str = "@prefix : <http://ex.org/> .\n@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .\n";
/// A hundred triples on one seed, plus the `rdfs9` chain the answer needs.
fn hundred_plus_chain() -> String {
let mut ttl = String::from(P);
for i in 0..100 {
ttl.push_str(&format!(":a :p{i} :o{i} .\n"));
}
ttl.push_str(":a a :A .\n:A rdfs:subClassOf :B .\n:B rdfs:subClassOf :C .\n");
ttl
}
// ═══════════════════════════════════════════════════════════════════════════
/// The brief's first sentence, as an executable claim.
#[test]
fn a_ninety_nine_percent_slice_that_drops_the_load_bearing_triple_is_not_ok() {
let _s = serial();
if skip() {
return;
}
checker();
let ttl = hundred_plus_chain();
let g = loaded(&ttl);
// Everything except the single `:A rdfs:subClassOf :B` the chain needs.
let slice: String = g
.all_triples()
.unwrap()
.into_iter()
.filter(|t| {
!(t.0 == "<http://ex.org/A>"
&& t.1 == "<http://www.w3.org/2000/01/rdf-schema#subClassOf>")
})
.map(|t| format!("{} {} {} .\n", t.0, t.1, t.2))
.collect();
let mut o = opts("ninety-nine");
o.seed_iris = vec!["http://ex.org/a".into()];
let r = cd::closure_diff(&g, &slice, &o).unwrap();
let ratio = r.coverage_proxy.report.as_ref().unwrap().aggregate_coverage_ratio;
assert!(
ratio > 0.98 && r.lost_in_projection_vocabulary > 0,
"coverage {ratio} over a slice that lost {} conclusion(s) in its own vocabulary\n{}",
r.lost_in_projection_vocabulary,
r.headline
);
// The actionable half: the retriever dropped THIS, and the conclusion went
// with it.
// An asserted triple that was simply not retrieved has no derivation and
// no blocking premises; it is a lookup that is gone. The actionable row is
// a lost INFERENCE, which names the premise the retriever dropped.
let row = r
.entailments_lost
.iter()
.find(|e| e.in_projection_vocabulary && e.rule.is_some())
.expect("a lost INFERENCE over the projection's own terms");
assert!(
!row.blocking_premises.is_empty(),
"a lost inference must name the premises the projection does not hold: {row:?}"
);
assert!(
row.blocking_premises
.iter()
.any(|p| p.1 == "<http://www.w3.org/2000/01/rdf-schema#subClassOf>"),
"and the named premise is the subClassOf link that was dropped: {row:?}"
);
assert_eq!(r.exit_code, 1);
}
/// The converse. Both directions, or the metric is untested.
#[test]
fn a_sixty_percent_slice_that_preserves_every_conclusion_is_ok() {
let _s = serial();
if skip() {
return;
}
checker();
let ttl = hundred_plus_chain();
let g = loaded(&ttl);
// Keep the chain and about half the noise.
let mut slice = String::new();
for (i, t) in g.all_triples().unwrap().into_iter().enumerate() {
let is_chain = t.1 == "<http://www.w3.org/2000/01/rdf-schema#subClassOf>"
|| t.1 == "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
if is_chain || i % 2 == 0 {
slice.push_str(&format!("{} {} {} .\n", t.0, t.1, t.2));
}
}
let mut o = opts("sixty");
o.seed_iris = vec!["http://ex.org/a".into()];
let r = cd::closure_diff(&g, &slice, &o).unwrap();
let ratio = r.coverage_proxy.report.as_ref().unwrap().aggregate_coverage_ratio;
assert!(ratio < 0.75, "the slice really is partial: {ratio}");
assert_eq!(
r.lost_in_projection_vocabulary, 0,
"a slice at {ratio} kept every conclusion over its own vocabulary, and lost {} over terms \
it does not mention: {:?}\n{}",
r.lost_total,
r.entailments_lost.iter().take(3).collect::<Vec<_>>(),
r.headline
);
assert_eq!(r.exit_code, 0);
}
/// The laundering guard. No skip guard: this needs the checker ABSENT, so it is
/// the one gate a machine without Lean still enforces.
#[test]
fn an_unchecked_run_never_prints_the_checked_word() {
let _s = serial();
let g = loaded(&format!("{P}:A rdfs:subClassOf :B . :B rdfs:subClassOf :C . :a a :A .\n"));
let mut o = opts("unchecked");
o.checker = Some(PathBuf::from("/nonexistent/oo-cert"));
let r = cd::closure_diff(&g, &format!("{P}:a a :A .\n"), &o).unwrap();
assert_eq!(r.source_certificate.verdict, "engine_opinion");
assert_eq!(
r.source_certificate.theorem, None,
"a theorem may not be named by a run that never ran the checker"
);
assert!(
r.source_certificate.skipped.as_deref().unwrap().contains("elan"),
"the skip must carry the install line: {:?}",
r.source_certificate
);
assert!(
r.entailments_lost.iter().all(|e| !e.warrant.is_checked()),
"an unchecked result printed the checked word"
);
let json = serde_json::to_string(&r).unwrap();
assert!(
!json.contains("OOCert.certificate_sound"),
"the theorem name must not appear anywhere in an unchecked report: {json}"
);
}
/// A lookup is not a theorem, and folding assertions into the checked count
/// would let a graph of 35,000 assertions and 3 inferences report "35,003
/// checked conclusions" on a machine with no Lean.
#[test]
fn an_assertion_is_never_counted_as_checked() {
let _s = serial();
if skip() {
return;
}
checker();
let g = loaded(&format!("{P}:A rdfs:subClassOf :B . :B rdfs:subClassOf :C . :a a :A .\n"));
let r = cd::closure_diff(&g, &format!("{P}:x a :A .\n"), &opts("warrants")).unwrap();
assert_eq!(r.source_certificate.verdict, "checked");
assert!(r.lost_by_warrant.contains_key("asserted_in_source"), "{:?}", r.lost_by_warrant);
assert!(r.lost_by_warrant.contains_key("checked"), "{:?}", r.lost_by_warrant);
assert!(
!r.lost_by_warrant.contains_key("total"),
"the three counts are never summed into one: {:?}",
r.lost_by_warrant
);
for e in &r.entailments_lost {
assert_eq!(e.theorem.is_some(), e.warrant.is_checked());
}
}
/// A rejected source certificate demotes EVERY row at once. Clean rule, no
/// per-step bookkeeping.
#[test]
#[cfg(unix)]
fn a_rejected_source_certificate_demotes_every_row() {
let _s = serial();
if skip() {
return;
}
checker();
let dir = scratch("rejecting");
let stub = dir.join("always-no");
std::fs::write(&stub, "#!/bin/sh\necho '{\"ok\":false}'\nexit 1\n").unwrap();
{
use std::os::unix::fs::PermissionsExt;
std::fs::set_permissions(&stub, std::fs::Permissions::from_mode(0o755)).unwrap();
}
let g = loaded(&format!("{P}:A rdfs:subClassOf :B . :B rdfs:subClassOf :C . :a a :A .\n"));
let mut o = opts("rejected-src");
o.checker = Some(stub);
let r = cd::closure_diff(&g, &format!("{P}:x a :A .\n"), &o).unwrap();
assert_eq!(r.source_certificate.verdict, "rejected");
assert_eq!(r.source_certificate.checker_exit, Some(1));
assert_eq!(r.source_certificate.theorem, None);
assert!(
r.entailments_lost.iter().all(|e| !e.warrant.is_checked()),
"a rejected certificate leaves nothing checked"
);
let json = serde_json::to_string(&r).unwrap();
assert!(!json.contains("OOCert.certificate_sound"), "{json}");
}
/// The engine cannot be made unsound on demand, so the gate is shown able to
/// fire by building a source closure with a hole the projection's closure
/// fills.
#[test]
fn the_monotonicity_gate_fires() {
let _s = serial();
let t = |s: &str, o: &str| (s.to_string(), "<p>".to_string(), o.to_string());
let src: HashSet<cd::NtTriple> = [t("<a>", "<b>")].into_iter().collect();
let prj: HashSet<cd::NtTriple> = [t("<a>", "<b>"), t("<a>", "<ghost>")].into_iter().collect();
let r = open_ontologies::projection_entailment::differential(
&src,
&prj,
open_ontologies::projection_entailment::Guards {
subset_verified: true,
blank_nodes_unmatched: false,
both_reached_fixpoint: true,
},
);
assert_eq!(r.status, "armed");
assert_eq!(r.violation_count, 1);
let d = r.disagreement.expect("a violation is a disagreement");
assert_eq!(d.severity, "STOP_THE_LINE");
assert!(d.means.contains("SOUNDNESS BUG IN THE ENGINE"), "{}", d.means);
// And `from_parts` exists so the same hole can be built at the report level.
let verdict = cd::CertificateVerdict {
verdict: open_ontologies::verdict::ClosureVerdict::EngineOpinion,
theorem: None,
asserted: 1,
derivations: 0,
checker_report: None,
checker_exit: None,
skipped: Some("hand-built".into()),
reached_fixpoint: true,
iterations: 1,
iteration_cap: 64,
};
let sc = cd::SourceClosure::from_parts(src, HashSet::new(), HashMap::new(), verdict);
assert_eq!(sc.closure_size(), 1);
assert_eq!(sc.verdict().verdict, "engine_opinion");
}
/// The trap, pinned on real data. RDFC-1.0 labels are a function of the WHOLE
/// graph, so canonicalising a source and a slice SEPARATELY and then diffing
/// them is not a fix for blank nodes: it is strictly worse than doing nothing.
///
/// Measured here on `benchmark/reference/pizza-reference.owl`, taking a genuine
/// subgraph (every triple not mentioning one class): canonicalising both sides
/// and diffing reports hundreds of triples of the SUBGRAPH as absent from the
/// SOURCE, while comparing the store's own labels reports none at all.
///
/// This test exists to stop a future implementer replacing `skolemise` with
/// `GraphStore::canonicalize_blank_nodes`, which is already in the repository,
/// is correct for "are these two graphs isomorphic", and looks principled.
#[test]
fn canonicalising_both_sides_separately_is_worse_than_doing_nothing() {
let _s = serial();
let g = Arc::new(GraphStore::new());
g.load_file(
&repo()
.join("benchmark/reference/pizza-reference.owl")
.display()
.to_string(),
)
.unwrap();
let full = g.all_triples().unwrap();
let sub: Vec<_> = full
.iter()
.filter(|t| !t.0.contains("Veneziana") && !t.2.contains("Veneziana"))
.cloned()
.collect();
assert!(sub.len() < full.len(), "the subgraph must really be smaller");
let nt = |v: &Vec<(String, String, String)>| -> String {
v.iter().map(|t| format!("{} {} {} .\n", t.0, t.1, t.2)).collect()
};
let a = GraphStore::new();
a.load_ntriples(&nt(&full)).unwrap();
let b = GraphStore::new();
b.load_ntriples(&nt(&sub)).unwrap();
let ca: HashSet<_> = a.canonicalize_blank_nodes().unwrap().all_triples().unwrap().into_iter().collect();
let cb: HashSet<_> = b.canonicalize_blank_nodes().unwrap().all_triples().unwrap().into_iter().collect();
let canonical_extras = cb.difference(&ca).count();
let sa: HashSet<_> = full.iter().cloned().collect();
let sb: HashSet<_> = sub.iter().cloned().collect();
let raw_extras = sb.difference(&sa).count();
assert_eq!(raw_extras, 0, "the store's own labels make the subgraph a subset, as it is");
assert!(
canonical_extras > 100,
"canonicalising each side separately produced {canonical_extras} spurious extras on a \
real subgraph, against {raw_extras} for the store's own labels. If this number is now \
small, say what changed in RDFC-1.0 or in this repository; until then, canonicalising \
both sides and diffing is worse than not canonicalising at all, and it looks \
principled, which is why the trap needs a test rather than a comment"
);
eprintln!(
"RDFC-1.0 SEPARATELY: {canonical_extras} spurious extras out of {} subgraph triples; \
store labels: {raw_extras}",
cb.len()
);
}
/// A re-parsed slice mints fresh blank node labels, so every blank-node-bearing
/// triple looks like an addition. Skolemising the source first is what makes
/// the comparison possible at all. This is the test that decides whether the
/// free differential is usable on real ontologies.
#[test]
fn a_relabelled_blank_node_is_not_a_monotonicity_violation() {
let _s = serial();
if skip() {
return;
}
checker();
let ttl = "@prefix : <http://ex.org/> .\n\
@prefix owl: <http://www.w3.org/2002/07/owl#> .\n\
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .\n\
:C rdfs:subClassOf [ a owl:Restriction ; owl:onProperty :p ; owl:someValuesFrom :D ] .\n\
:E rdfs:subClassOf :C .\n";
let g = loaded(ttl);
// Without skolemising: the slice is the same graph, re-serialised, and its
// blank nodes are new. Nothing may be accused of anything.
let mut o = opts("bnode-off");
o.skolemise_source = false;
let slice = g.serialize("turtle").unwrap();
let r = cd::closure_diff(&g, &slice, &o).unwrap();
assert!(r.monotonicity_violations.is_empty(), "{:?}", r.monotonicity_violations);
assert!(
r.monotonicity_gate_skipped.is_some(),
"an empty violation list must never mean 'we did not look'"
);
assert!(r.not_compared.projection_triples > 0, "{:?}", r.not_compared);
assert!(r.not_compared.why.contains("NP-complete"), "{}", r.not_compared.why);
// With skolemising: nothing is uncompared and nothing is lost.
let mut o2 = opts("bnode-on");
o2.skolemise_source = true;
let src = cd::SourceClosure::build(&g, &o2).unwrap();
let slice2 = src.store().serialize("turtle").unwrap();
let r2 = src.diff(&slice2, &o2).unwrap();
assert_eq!(r2.not_compared.projection_triples, 0, "{:?}", r2.not_compared);
assert_eq!(r2.not_compared.source_triples, 0, "{:?}", r2.not_compared);
assert_eq!(r2.lost_total, 0, "{:?}", r2.entailments_lost);
assert!(r2.monotonicity_gate_skipped.is_none(), "{:?}", r2.monotonicity_gate_skipped);
assert!(r2.skolemised > 0);
}
/// "The retriever produced it from the source, so it is a subset" is false in
/// practice. Retrievers normalise IRIs, re-prefix, inline an imported
/// vocabulary, and add a tidy declaration nobody wrote.
#[test]
fn a_projection_that_is_not_a_subset_is_a_retrieval_finding() {
let _s = serial();
if skip() {
return;
}
checker();
let g = loaded(&format!("{P}:A rdfs:subClassOf :B .\n"));
let r = cd::closure_diff(
&g,
&format!("{P}:A rdfs:subClassOf :B .\n:Invented rdfs:subClassOf :Nonsense .\n"),
&opts("non-subset"),
)
.unwrap();
assert!(!r.subset.verified);
assert_eq!(r.subset.extra_count, 1);
assert!(
r.subset.extra_triples.iter().any(|t| t.contains("Invented")),
"the extra triple must be listed: {:?}",
r.subset
);
assert!(r.monotonicity_violations.is_empty(), "a non-subset accuses nobody of unsoundness");
let why = r.monotonicity_gate_skipped.expect("the gate must say why it did not run");
assert!(why.contains("not a subset"), "{why}");
assert!(why.contains("RETRIEVAL finding"), "{why}");
}
/// A truncated source closure would fire a false STOP_THE_LINE on every long
/// subclass chain.
#[test]
fn the_iteration_cap_suppresses_the_soundness_alarm() {
let _s = serial();
if skip() {
return;
}
checker();
let mut ttl = String::from(P);
for i in 0..8 {
ttl.push_str(&format!(":C{i} rdfs:subClassOf :C{}.\n", i + 1));
}
ttl.push_str(":a a :C0 .\n");
let g = loaded(&ttl);
let previous = open_ontologies::runtime::reasoner_max_iterations();
open_ontologies::runtime::set_reasoner_max_iterations(1);
let r = cd::closure_diff(&g, &ttl, &opts("cap"));
open_ontologies::runtime::set_reasoner_max_iterations(previous);
let r = r.unwrap();
assert!(!r.source_certificate.reached_fixpoint, "one round cannot close an eight-link chain");
assert_eq!(r.source_certificate.iteration_cap, 1);
let why = r.monotonicity_gate_skipped.expect("the gate must say why it did not run");
assert!(why.contains("cap"), "{why}");
assert!(r.monotonicity_violations.is_empty());
}
#[test]
fn owl_dl_is_refused() {
let _s = serial();
let g = loaded(&format!("{P}:A rdfs:subClassOf :B .\n"));
let mut o = opts("owl-dl");
o.profile = "owl-dl".into();
let err = cd::closure_diff(&g, &format!("{P}:A rdfs:subClassOf :B .\n"), &o)
.expect_err("owl-dl has no rule trace and must say so");
let m = err.to_string();
assert!(m.contains("no rule trace"), "{m}");
assert!(m.contains("owl-rl-ext"), "the message must name the profiles that do work: {m}");
}
/// Mechanical, cheap, and the only thing that stops the warning being dropped
/// by a future renderer.
#[test]
fn the_coverage_warning_travels_with_the_number() {
let _s = serial();
if skip() {
return;
}
checker();
let g = loaded(&format!("{P}:A rdfs:subClassOf :B .\n"));
let mut o = opts("label");
o.seed_iris = vec!["http://ex.org/A".into()];
let r = cd::closure_diff(&g, &format!("{P}:A rdfs:subClassOf :B .\n"), &o).unwrap();
let json = serde_json::to_string(&r).unwrap();
assert!(json.contains("coverage_ratio"), "the number is present: {json}");
assert!(
json.contains("neither necessary nor sufficient"),
"and so is the label: {json}"
);
assert!(json.contains("\"is_a_warrant\":false"), "{json}");
assert!(
json.contains("gaming direction"),
"the headline's own gaming direction must be in the PAYLOAD, not only the docs: {json}"
);
}
/// The closure diff reads `all_triples` and the certificate TSVs, so it
/// inherits none of `neighbourhood_pairs`'s `LIMIT 1000`.
#[test]
fn a_seed_with_more_than_a_thousand_triples_is_counted_in_full() {
let _s = serial();
if skip() {
return;
}
checker();
let mut ttl = String::from(P);
for i in 0..1500 {
ttl.push_str(&format!(":a :p{i} :o{i} .\n"));
}
let g = loaded(&ttl);
let mut o = opts("limit");
o.seed_iris = vec!["http://ex.org/a".into()];
let r = cd::closure_diff(&g, &format!("{P}:a :p0 :o0 .\n"), &o).unwrap();
assert_eq!(
r.lost_total, 1499,
"the closure diff counts every triple, not the first thousand: {}",
r.headline
);
// And the proxy, which does truncate, says so.
assert_eq!(
r.coverage_proxy.truncated_seeds.len(),
1,
"the seed whose ratio was computed against a truncated source must be named: {:?}",
r.coverage_proxy
);
}
/// A cached verdict read off disk would be an unchecked result wearing the
/// checked word one indirection away, so `load` re-runs the checker.
#[test]
fn a_reloaded_cache_re_runs_the_checker() {
let _s = serial();
if skip() {
return;
}
checker();
let g = loaded(&format!("{P}:A rdfs:subClassOf :B . :B rdfs:subClassOf :C . :a a :A .\n"));
let o = opts("reload");
let built = cd::SourceClosure::build(&g, &o).unwrap();
assert_eq!(built.verdict().verdict, "checked");
let mut o2 = DiffOptions { out: o.out.clone(), ..Default::default() };
o2.checker = Some(PathBuf::from("/nonexistent/oo-cert"));
let reloaded = cd::SourceClosure::load(&o.out.join("source"), &o2).unwrap();
assert_eq!(
reloaded.verdict().verdict,
"engine_opinion",
"a reload with no checker must NOT inherit the checked word from the directory"
);
assert_eq!(
reloaded.asserted_digest(),
built.asserted_digest(),
"the digest identifies the graph the cache was built from"
);
}