Skip to content

Plan, apply and roll back changes to a production ontology, with a blast radius report and a proof an auditor can re-check.

199 KB
Raw Blame
use std::collections::{HashMap, HashSet};
use std::sync::Arc;

use crate::graph::GraphStore;
use crate::temporal::ScopeRequest;

// Well-known IRIs
const RDF_TYPE: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
const RDFS_SUBCLASS: &str = "<http://www.w3.org/2000/01/rdf-schema#subClassOf>";
const RDFS_SUBPROP: &str = "<http://www.w3.org/2000/01/rdf-schema#subPropertyOf>";
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 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: &str = "<http://www.w3.org/2002/07/owl#inverseOf>";
const OWL_SAMEAS: &str = "<http://www.w3.org/2002/07/owl#sameAs>";
const OWL_EQUIV_CLASS: &str = "<http://www.w3.org/2002/07/owl#equivalentClass>";
const OWL_EQUIV_PROP: &str = "<http://www.w3.org/2002/07/owl#equivalentProperty>";
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_ON_PROPERTY: &str = "<http://www.w3.org/2002/07/owl#onProperty>";
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_ONEOF: &str = "<http://www.w3.org/2002/07/owl#oneOf>";
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>";

// The vocabulary the clash detector reads. None of it drives a rule: nothing in
// the table above concludes a triple from any of these terms. They are read
// once, after the fixpoint, by `find_clashes`.
const OWL_DISJOINT_WITH: &str = "<http://www.w3.org/2002/07/owl#disjointWith>";
const OWL_NOTHING: &str = "<http://www.w3.org/2002/07/owl#Nothing>";
const OWL_COMPLEMENT_OF: &str = "<http://www.w3.org/2002/07/owl#complementOf>";
const OWL_IRREFLEXIVE: &str = "<http://www.w3.org/2002/07/owl#IrreflexiveProperty>";
const OWL_ASYMMETRIC: &str = "<http://www.w3.org/2002/07/owl#AsymmetricProperty>";
const OWL_PROP_DISJOINT_WITH: &str = "<http://www.w3.org/2002/07/owl#propertyDisjointWith>";
const OWL_DIFFERENT_FROM: &str = "<http://www.w3.org/2002/07/owl#differentFrom>";
const OWL_MAX_CARDINALITY: &str = "<http://www.w3.org/2002/07/owl#maxCardinality>";
const OWL_SOURCE_INDIVIDUAL: &str = "<http://www.w3.org/2002/07/owl#sourceIndividual>";
const OWL_ASSERTION_PROPERTY: &str = "<http://www.w3.org/2002/07/owl#assertionProperty>";
const OWL_TARGET_INDIVIDUAL: &str = "<http://www.w3.org/2002/07/owl#targetIndividual>";
const OWL_TARGET_VALUE: &str = "<http://www.w3.org/2002/07/owl#targetValue>";

/// A triple over interned ids.
type Fact = (u32, u32, u32);

/// One line of a certificate: the rule, what it concluded, and the premises
/// it read, in the order `lean/OOCert/Rules.lean` documents for that rule.
struct Derivation {
    rule: &'static str,
    conclusion: Fact,
    premises: Vec<Fact>,
}

// ── Reading the derivation DAG back ─────────────────────────────────────────
//
// `derivations.tsv` records ONE step per inferred triple: the first time the
// fixpoint reached it. That is the right thing for a certificate, because a
// checker re-derives and one derivation is all it needs, and it is the WRONG
// thing for explanation. A triple derived two independent ways has two
// justifications and the certificate shows one of them; a provenance polynomial
// with one monomial where the closure supports two is a false statement about
// where the conclusion came from.
//
// So explanation does not read the file. It asks the fixpoint for every ground
// rule instance it found applicable, which is the whole DAG rather than a
// spanning forest of it. The capture is opt-in, costs one branch per candidate
// triple on a run that did not ask for it, and is memory-proportional to the
// number of applicable instances rather than to the number of conclusions.
//
// The instances collected are those applicable in the FIXPOINT closure. The
// last round of the loop runs every rule over the complete closure and adds
// nothing, so every instance applicable at the fixpoint fires at least once and
// is recorded. Deduplication is by (rule, conclusion, premises).

/// A triple in the store's own N-Triples spelling, byte-identical to what
/// [`GraphStore::all_triples`] yields and to what `asserted.tsv` carries.
pub type Spelled = crate::projection_entailment::Spelled;

/// One ground rule instance the fixpoint found applicable: a rule, what it
/// concluded, and the premises it read in the order
/// `lean/OOCert/Rules.lean` documents for that rule.
///
/// Unlike a certificate line this is NOT unique per conclusion. Two instances
/// with the same conclusion are two independent derivations of it, and that is
/// exactly the fact [`crate::justify`] and [`crate::provenance`] exist to read.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct RuleInstance {
    pub rule: &'static str,
    pub conclusion: Spelled,
    pub premises: Vec<Spelled>,
}

/// One way the closure contradicts itself, spelled out for a consumer that has
/// no interner.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ClashInstance {
    pub rule: &'static str,
    pub premises: Vec<Spelled>,
    /// Whether `lean/OOCert/Refute.lean` holds a semantic condition for this
    /// rule, so that a refutation naming it can be CHECKED rather than merely
    /// asserted. Exactly one rule qualifies; see [`CLASH_RULES_CERTIFIABLE`].
    pub certifiable: bool,
}

/// Everything one forward-chaining run knows about how it got where it got.
///
/// `closure` is what the run believes, `asserted` is what it started from, and
/// `instances` is every ground rule application that connects the two. The
/// three together are the derivation DAG: nodes are triples, and an instance is
/// a hyperedge from its premises to its conclusion.
#[derive(Clone, Debug)]
pub struct DerivationGraph {
    pub profile_used: String,
    /// Every triple the run started from, in store order.
    pub asserted: Vec<Spelled>,
    /// Every triple the run ended with, asserted ones included.
    pub closure: HashSet<Spelled>,
    /// Every applicable ground rule instance, in the order the fixpoint first
    /// found each one. That order is topological: a rule read its premises out
    /// of the closure as it stood at the START of the round, so every premise
    /// was concluded in a strictly earlier round or asserted.
    pub instances: Vec<RuleInstance>,
    /// False when the run stopped at the iteration cap instead of a fixpoint.
    /// The closure is then a LOWER BOUND and every answer computed from it is
    /// an answer about a partial closure.
    pub fixpoint_reached: bool,
    pub iterations: usize,
    /// The clashes [`find_clashes`] found over the closure. Ten of the
    /// seventeen OWL 2 RL rules that conclude `false` are looked for, so an
    /// empty list is NOT a consistency result.
    pub clashes: Vec<ClashInstance>,
    /// Conclusions refused for being unserialisable, and therefore neither
    /// materialised nor available as premises. A run with a non-zero count here
    /// derived LESS than its rule table licenses.
    pub refused_unserialisable: usize,
}

impl DerivationGraph {
    /// Is this triple in the closure?
    pub fn holds(&self, t: &Spelled) -> bool {
        self.closure.contains(t)
    }
    /// Was this triple asserted rather than derived?
    pub fn is_asserted(&self, t: &Spelled) -> bool {
        self.asserted.iter().any(|a| a == t)
    }
}

/// Collector threaded through the fixpoint when a caller asked for the DAG.
#[derive(Default)]
struct Capture {
    seen: HashSet<(&'static str, Fact, Vec<Fact>)>,
    instances: Vec<(&'static str, Fact, Vec<Fact>)>,
    out: Option<DerivationGraph>,
}


// ── The rules that conclude `false` ─────────────────────────────────────────
//
// Seventeen rules of the OWL 2 RL profile conclude `false` rather than a
// triple: `eq-diff1`, `eq-diff2`, `eq-diff3`, `prp-irp`, `prp-asyp`,
// `prp-pdw`, `prp-adp`, `prp-npa1`, `prp-npa2`, `cls-nothing2`, `cls-com`,
// `cls-maxc1`, `cls-maxqc1`, `cls-maxqc2`, `cax-dw`, `cax-adc` and
// `dt-not-type`. (Seventeen is the count extracted mechanically from the W3C
// tables, and `lean/OOCert/Refute.lean` now agrees; it said sixteen until the
// list was checked against the source. `dt-not-type` is the one that is not
// merely absent from the Lean but INEXPRESSIBLE there, because that semantics
// has no datatype value space and a literal is its spelling like any other
// term.)
//
// None of them is in the fixpoint's rule table, and none of them could be:
// `Derivation.conclusion` is a triple. They are looked for HERE, once, over
// the closure the fixpoint reached, and reported in the separate `oo-refute/1`
// format.
//
// **Twelve of the seventeen can now be certified, and this engine finds ten of
// those twelve.** `OOCert.RefuteConditions` in `lean/OOCert/Refute.lean` carries
// twelve semantic fields and `OOCert.checkRefuteStep` twelve arms, so a
// refutation naming any of the twelve is CHECKED rather than refused. It used to
// carry one.
//
// The two numbers differ and the difference is not a defect. `cls-maxqc1` and
// `cls-maxqc2` have a condition in the Lean and no detector here: the checker
// would accept a refutation naming them, and this engine never writes one,
// because nothing looks for them. The five that have no condition at all are
// `cax-adc`, `prp-adp`, `eq-diff2` and `eq-diff3`, which state their members in
// an RDF list that the step format cannot carry, and `dt-not-type`, which needs
// a datatype value space this development does not have. The first four are NOT
// IMPLEMENTED and the fifth is NOT EXPRESSIBLE.
//
// A clash of a rule outside the twelve is still an engine opinion with nothing
// behind it, still reported under a different word from the certified one, and
// still written to no refutation file.

/// One way the closure contradicts itself: the OWL 2 RL rule that concludes
/// `false` from it, and the premises that rule reads, in the order the W3C
/// table writes them (which is also the order `OOCert.checkRefuteStep` matches
/// on, and a refutation with the right triples in the wrong order is rejected).
struct Clash {
    rule: &'static str,
    premises: Vec<Fact>,
}

/// The clash rules `lean/` holds a semantic condition for AND this engine
/// detects, so that a refutation naming one can be CHECKED rather than merely
/// asserted.
///
/// Ten names, and the list is not this file's to extend: adding a name here
/// without a matching field in `OOCert.RefuteConditions` and a matching arm in
/// `OOCert.checkRefuteStep` would make the engine write a file the checker
/// exits 2 on, which is the one failure mode this layer exists to prevent.
/// `tests/refutation_producer_test.rs` asserts the two lists agree, so the
/// mistake is a test failure rather than a bad file.
///
/// The Lean certifies TWELVE. `cls-maxqc1` and `cls-maxqc2` are absent here
/// because nothing in this file looks for them, not because the checker would
/// refuse them, and they are listed with that reason in
/// `CLASH_RULES_NOT_DETECTED` below.
///
/// One constant, read both by the emitter and by the report, so the two cannot
/// drift into disagreeing about what was certified.
const CLASH_RULES_CERTIFIABLE: &[&str] = &[
    "cax-dw", "cls-com", "cls-nothing2", "eq-diff1", "prp-irp", "prp-asyp",
    "prp-pdw", "cls-maxc1", "prp-npa1", "prp-npa2",
];

fn clash_is_certifiable(rule: &str) -> bool {
    CLASH_RULES_CERTIFIABLE.contains(&rule)
}

/// The clash rules this engine does NOT look for, each with the reason. Listed
/// so that "no clash found" is never read as "consistent": the honest reading
/// of a clean run is that none of the rules below was even tried.
///
/// `pub` because `src/dlp.rs` subtracts this list from the seventeen OWL 2 RL
/// rules that conclude `false` to arrive at the ten that ARE detected. That
/// number is then derived from this file rather than typed a second time
/// somewhere else, which is the only way two copies of a figure stay equal.
pub const CLASH_RULES_NOT_DETECTED: &[(&str, &str)] = &[
    ("cax-adc", "owl:AllDisjointClasses states its members in an RDF list, and this detector reads \
                 no lists. The pairwise owl:disjointWith spelling of the same axiom IS detected."),
    ("prp-adp", "owl:AllDisjointProperties states its members in an RDF list, and this detector \
                 reads no lists. The pairwise owl:propertyDisjointWith spelling IS detected."),
    ("eq-diff2", "owl:AllDifferent with owl:members is an RDF list. The pairwise owl:differentFrom \
                  spelling IS detected, by eq-diff1."),
    ("eq-diff3", "owl:AllDifferent with owl:distinctMembers is an RDF list, as above."),
    ("cls-maxqc1", "owl:maxQualifiedCardinality needs the qualifying owl:onClass and a type check \
                    on the value. NOT DETECTED HERE, though the Lean checker does hold a condition \
                    for it: a refutation naming it would be accepted, and this engine writes none \
                    because nothing looks for it. owl:maxCardinality 0 IS detected, by cls-maxc1."),
    ("cls-maxqc2", "the owl:Thing case of the same rule. Also certifiable and also not detected."),
    ("dt-not-type", "an ill-typed literal needs a datatype VALUE space. This engine, and the Lean \
                     semantics under it, read a literal as its N-Triples spelling and compare \
                     nothing by value, so there is no notion here of a literal outside its type."),
];

/// Every rule the forward-chaining fixpoint evaluates, with the profile that
/// switches it on, spelled exactly as the `emit` call in this file spells it.
///
/// **This is the rule table, written down.** Twenty-nine names, and the figure
/// "29 of OWL 2 RL's 78 rules" that six other files repeat is this list's
/// length rather than a number somebody typed. `src/dlp.rs` reads it to decide
/// whether an axiom a user wrote is one the rule engine can actually see, and
/// `the_evaluated_rule_list_is_the_rules_this_file_emits` in
/// `tests/dlp_boundary_test.rs` greps THIS FILE for its `emit` calls and fails
/// if the two disagree. So a rule added below without an `emit`, or an `emit`
/// added without a line here, is a test failure and not a silent drift.
///
/// The six RDFS spellings are OWL 2 RL rules under other names: `rdfs2` is
/// `prp-dom`, `rdfs3` is `prp-rng`, `rdfs5` is `scm-spo`, `rdfs7` is
/// `prp-spo1`, `rdfs9` is `cax-sco` and `rdfs11` is `scm-sco`. `src/dlp.rs`
/// carries that map, because a user reading a W3C rule name has to be able to
/// find it here.
///
/// The profile matters and is not decoration: a run at `rdfs` evaluates SIX of
/// these and a report that said 29 to such a run would be describing a table
/// the run never used.
pub const RULES_EVALUATED: &[(&str, &str)] = &[
    ("rdfs2", "rdfs"),
    ("rdfs3", "rdfs"),
    ("rdfs5", "rdfs"),
    ("rdfs7", "rdfs"),
    ("rdfs9", "rdfs"),
    ("rdfs11", "rdfs"),
    ("eq-sym", "owl-rl"),
    ("prp-inv1", "owl-rl"),
    ("prp-inv2", "owl-rl"),
    ("prp-symp", "owl-rl"),
    ("prp-trp", "owl-rl"),
    ("scm-dom1", "owl-rl"),
    ("scm-dom2", "owl-rl"),
    ("scm-eqc1", "owl-rl"),
    ("scm-eqp1", "owl-rl"),
    ("scm-rng1", "owl-rl"),
    ("scm-rng2", "owl-rl"),
    ("cls-avf", "owl-rl-ext"),
    ("cls-hv1", "owl-rl-ext"),
    ("cls-hv2", "owl-rl-ext"),
    ("cls-int1", "owl-rl-ext"),
    ("cls-int2", "owl-rl-ext"),
    ("cls-oo", "owl-rl-ext"),
    ("cls-svf1", "owl-rl-ext"),
    ("cls-uni", "owl-rl-ext"),
    ("scm-avf1", "owl-rl-ext"),
    ("scm-avf2", "owl-rl-ext"),
    ("scm-svf1", "owl-rl-ext"),
    ("scm-svf2", "owl-rl-ext"),
];

/// The interned vocabulary [`find_clashes`] reads. Gathered into one value so
/// the detector takes three arguments rather than eighteen.
struct ClashVocab {
    rdf_type: u32,
    disjoint_with: u32,
    nothing: u32,
    complement_of: u32,
    irreflexive: u32,
    asymmetric: u32,
    prop_disjoint_with: u32,
    same_as: u32,
    different_from: u32,
    max_cardinality: u32,
    on_property: u32,
    source_individual: u32,
    assertion_property: u32,
    target_individual: u32,
    target_value: u32,
}

/// Zero, in whichever spelling the store hands back for a
/// `xsd:nonNegativeInteger` zero. Only the lexical form is read, because
/// nothing else in this engine compares a literal by value and a detector that
/// did would be claiming a datatype semantics the checker underneath it does
/// not have.
fn literal_is_zero(term: &str) -> bool {
    let Some(rest) = term.strip_prefix('"') else {
        return false;
    };
    let Some(end) = rest.find('"') else {
        return false;
    };
    rest[..end].trim().parse::<i128>().map(|n| n == 0).unwrap_or(false)
}

/// Look for a contradiction in the closure the fixpoint reached.
///
/// Deterministic: the result is sorted on the N-Triples spelling of the
/// premises and duplicates are dropped, so two runs over one store produce the
/// same refutation file byte for byte.
fn find_clashes(closure: &HashSet<Fact>, interner: &Interner, v: &ClashVocab) -> Vec<Clash> {
    // One pass for every index, because the closure is the large thing here.
    let mut by_class: HashMap<u32, Vec<u32>> = HashMap::new();
    let mut disjoint: Vec<Fact> = Vec::new();
    let mut complement: Vec<Fact> = Vec::new();
    let mut irreflexive: HashSet<u32> = HashSet::new();
    let mut asymmetric: HashSet<u32> = HashSet::new();
    let mut prop_disjoint: Vec<Fact> = Vec::new();
    let mut different: Vec<Fact> = Vec::new();
    let mut on_property: HashMap<u32, u32> = HashMap::new();
    let mut max_zero: Vec<(u32, u32)> = Vec::new();
    let mut npa_source: HashMap<u32, u32> = HashMap::new();
    let mut npa_prop: HashMap<u32, u32> = HashMap::new();
    let mut npa_target_ind: HashMap<u32, u32> = HashMap::new();
    let mut npa_target_val: HashMap<u32, u32> = HashMap::new();
    for &(s, p, o) in closure.iter() {
        if p == v.rdf_type {
            by_class.entry(o).or_default().push(s);
            if o == v.irreflexive {
                irreflexive.insert(s);
            }
            if o == v.asymmetric {
                asymmetric.insert(s);
            }
        } else if p == v.disjoint_with {
            disjoint.push((s, p, o));
        } else if p == v.complement_of {
            complement.push((s, p, o));
        } else if p == v.prop_disjoint_with {
            prop_disjoint.push((s, p, o));
        } else if p == v.different_from {
            different.push((s, p, o));
        } else if p == v.on_property {
            on_property.insert(s, o);
        } else if p == v.max_cardinality && literal_is_zero(interner.resolve(o)) {
            max_zero.push((s, o));
        } else if p == v.source_individual {
            npa_source.insert(s, o);
        } else if p == v.assertion_property {
            npa_prop.insert(s, o);
        } else if p == v.target_individual {
            npa_target_ind.insert(s, o);
        } else if p == v.target_value {
            npa_target_val.insert(s, o);
        }
    }

    let mut out: Vec<Clash> = Vec::new();

    // cax-dw: c1 owl:disjointWith c2, x rdf:type c1, x rdf:type c2.
    // The one rule a refutation can be written for.
    for &(c1, dw, c2) in &disjoint {
        let Some(xs) = by_class.get(&c1) else { continue };
        for &x in xs {
            if closure.contains(&(x, v.rdf_type, c2)) {
                out.push(Clash {
                    rule: "cax-dw",
                    premises: vec![(c1, dw, c2), (x, v.rdf_type, c1), (x, v.rdf_type, c2)],
                });
            }
        }
    }

    // cls-com: the same shape, over owl:complementOf.
    for &(c1, co, c2) in &complement {
        let Some(xs) = by_class.get(&c1) else { continue };
        for &x in xs {
            if closure.contains(&(x, v.rdf_type, c2)) {
                out.push(Clash {
                    rule: "cls-com",
                    premises: vec![(c1, co, c2), (x, v.rdf_type, c1), (x, v.rdf_type, c2)],
                });
            }
        }
    }

    // cls-nothing2: x rdf:type owl:Nothing.
    if let Some(xs) = by_class.get(&v.nothing) {
        for &x in xs {
            out.push(Clash {
                rule: "cls-nothing2",
                premises: vec![(x, v.rdf_type, v.nothing)],
            });
        }
    }

    // eq-diff1: x owl:sameAs y, x owl:differentFrom y. The spec's pattern
    // exactly, with both premises on the same subject.
    for &(x, df, y) in &different {
        if closure.contains(&(x, v.same_as, y)) {
            out.push(Clash {
                rule: "eq-diff1",
                premises: vec![(x, v.same_as, y), (x, df, y)],
            });
        }
    }

    // prp-irp, prp-asyp and prp-pdw each need a second scan over the closure,
    // and the scan is skipped entirely when none of their vocabulary is
    // present, which is the case for every ontology this repository ships.
    if !irreflexive.is_empty() || !asymmetric.is_empty() || !prop_disjoint.is_empty() {
        for &(x, p, y) in closure.iter() {
            // prp-irp: p rdf:type owl:IrreflexiveProperty, x p x.
            if x == y && irreflexive.contains(&p) {
                out.push(Clash {
                    rule: "prp-irp",
                    premises: vec![(p, v.rdf_type, v.irreflexive), (x, p, y)],
                });
            }
            // prp-asyp: p rdf:type owl:AsymmetricProperty, x p y, y p x.
            if asymmetric.contains(&p) && closure.contains(&(y, p, x)) {
                out.push(Clash {
                    rule: "prp-asyp",
                    premises: vec![(p, v.rdf_type, v.asymmetric), (x, p, y), (y, p, x)],
                });
            }
            // prp-pdw: p1 owl:propertyDisjointWith p2, x p1 y, x p2 y.
            for &(p1, pdw, p2) in &prop_disjoint {
                if p == p1 && closure.contains(&(x, p2, y)) {
                    out.push(Clash {
                        rule: "prp-pdw",
                        premises: vec![(p1, pdw, p2), (x, p1, y), (x, p2, y)],
                    });
                }
            }
        }
    }

    // cls-maxc1: x owl:maxCardinality 0, x owl:onProperty p, u rdf:type x, u p y.
    // The (subject, predicate) index is built only when the vocabulary is
    // present, so an ontology with no cardinality-zero restriction pays for
    // none of it.
    if !max_zero.is_empty() {
        let mut values: HashMap<(u32, u32), Vec<u32>> = HashMap::new();
        for &(s, p, o) in closure.iter() {
            values.entry((s, p)).or_default().push(o);
        }
        for &(r, zero) in &max_zero {
            let Some(&prop) = on_property.get(&r) else { continue };
            let Some(us) = by_class.get(&r) else { continue };
            for &u in us {
                let Some(ys) = values.get(&(u, prop)) else { continue };
                for &y in ys {
                    out.push(Clash {
                        rule: "cls-maxc1",
                        premises: vec![
                            (r, v.max_cardinality, zero),
                            (r, v.on_property, prop),
                            (u, v.rdf_type, r),
                            (u, prop, y),
                        ],
                    });
                }
            }
        }
    }

    // prp-npa1 / prp-npa2: a negative property assertion its own graph
    // contradicts. One assertion per node is read; a node carrying two
    // owl:sourceIndividual triples is malformed and the last one seen wins.
    for (&node, &i) in &npa_source {
        let Some(&p) = npa_prop.get(&node) else { continue };
        if let Some(&j) = npa_target_ind.get(&node)
            && closure.contains(&(i, p, j))
        {
            out.push(Clash {
                rule: "prp-npa1",
                premises: vec![
                    (node, v.source_individual, i),
                    (node, v.assertion_property, p),
                    (node, v.target_individual, j),
                    (i, p, j),
                ],
            });
        }
        if let Some(&lt) = npa_target_val.get(&node)
            && closure.contains(&(i, p, lt))
        {
            out.push(Clash {
                rule: "prp-npa2",
                premises: vec![
                    (node, v.source_individual, i),
                    (node, v.assertion_property, p),
                    (node, v.target_value, lt),
                    (i, p, lt),
                ],
            });
        }
    }

    // Deterministic order, so the refutation file does not depend on hash
    // iteration order and two runs over one store agree byte for byte.
    let mut keyed: Vec<(String, Clash)> = out
        .into_iter()
        .map(|c| {
            let mut k = String::from(c.rule);
            for &(s, p, o) in &c.premises {
                k.push('\t');
                k.push_str(interner.resolve(s));
                k.push('\t');
                k.push_str(interner.resolve(p));
                k.push('\t');
                k.push_str(interner.resolve(o));
            }
            (k, c)
        })
        .collect();
    keyed.sort_by(|a, b| a.0.cmp(&b.0));
    keyed.dedup_by(|a, b| a.0 == b.0);
    keyed.into_iter().map(|(_, c)| c).collect()
}

/// The derivation steps a refutation must carry so that every premise it cites
/// is either asserted or concluded by a step BEFORE it.
///
/// Returns indices into `derivations`, ascending, which is a valid order:
/// `derivations` records each conclusion the first time the fixpoint reached
/// it, and every premise of that step was in the closure of an earlier
/// iteration, so the recorded order is already a topological one.
///
/// `None` when a premise is neither asserted nor derived, which cannot happen
/// for a clash found in the closure of a certified run and would be a bug here
/// rather than a refutation.
fn refutation_prefix(
    premises: &[Fact],
    derivations: &[Derivation],
    asserted: &HashSet<Fact>,
) -> Option<Vec<usize>> {
    let mut first: HashMap<Fact, usize> = HashMap::new();
    for (i, d) in derivations.iter().enumerate() {
        first.entry(d.conclusion).or_insert(i);
    }
    let mut needed: HashSet<usize> = HashSet::new();
    let mut work: Vec<Fact> = premises.to_vec();
    while let Some(t) = work.pop() {
        if asserted.contains(&t) {
            continue;
        }
        let &i = first.get(&t)?;
        if !needed.insert(i) {
            continue;
        }
        work.extend(derivations[i].premises.iter().copied());
    }
    let mut ids: Vec<usize> = needed.into_iter().collect();
    ids.sort_unstable();
    Some(ids)
}

/// Can this triple be written by an RDF serialiser?
///
/// A literal cannot be a subject and only an IRI can be a predicate, in every
/// RDF 1.1 serialisation. A rule that concludes otherwise has produced
/// something the store cannot hold, and the materialiser does not find out
/// until it is halfway through inserting the batch.
///
/// Both positions, and ONE definition, because the previous attempt was four
/// targeted guards and it missed two things.
///
/// The subject case was found on 30 August 2026 and guarded at `prp-symp`,
/// `prp-inv1`, `prp-inv2` and `eq-sym`. It was still open at `cls-avf`, which
/// concludes `y rdf:type c` from `x type ∀P.c` and `x P y`, so an
/// `owl:allValuesFrom` restriction on a property with a literal value derived
/// `"x" rdf:type :D`. That needs no unusual modelling at all.
///
/// The predicate case was never guarded anywhere outside `run_horn`. It is
/// reachable from `rdfs7`, `prp-inv1`, `prp-inv2` and `cls-hv1`, each of which
/// takes its conclusion's predicate from an object position where RDF permits a
/// blank node or a literal. `:p rdfs:subPropertyOf [ owl:inverseOf :q ]` is
/// enough, and that is what the OWL 2 mapping to RDF produces for
/// `SubObjectPropertyOf(:p ObjectInverseOf(:q))`. Found by
/// `tests/certificate_boundary_proptest.rs` on 14 September 2026 and pinned by
/// `tests/reason_unwritable_predicate_test.rs`, which also pins that `prp-symp`
/// and `prp-trp` CANNOT reach it, because their property must already be the
/// predicate of a stored triple and is therefore an IRI.
///
/// Terms arrive in their N-Triples spelling, so a literal begins with `"` and
/// an IRI with `<`.
///
/// The body is `crate::boundary_core::writable_triple_bytes`, which is the
/// function Aeneas translates into Lean. `OOBoundary.writable_triple_bytes_eq`
/// proves it decides both positions for terms of EVERY length, which is the
/// unbounded form of what `writable_triple_decides_both_positions` proves at a
/// fixed four bytes. `str::starts_with` with an ASCII `char` and a leading-byte
/// test agree on every `&str`, because no ASCII byte occurs inside a multi-byte
/// UTF-8 sequence; `tcb_wrappers_agree_with_the_char_level_predicates` pins it.
fn writable_triple(subject: &str, predicate: &str) -> bool {
    crate::boundary_core::writable_triple_bytes(subject.as_bytes(), predicate.as_bytes())
}

/// Which position of a certificate line refused to be written.
///
/// Deliberately a bare enum and not an `anyhow::Error`. The writers below are
/// the functions the Kani harnesses at the bottom of this file prove things
/// about, and a formatted error inside a function is what put CBMC inside the
/// formatting machinery and killed the first `parse_pat` harness. The message a
/// user reads is built by the caller, from this and the term.
///
/// Defined in `crate::boundary_core` so that Aeneas translates it with the
/// writers that return it, and re-exported here so `reason::Position` is still
/// the path it always was.
pub use crate::boundary_core::Position;

/// The canonical bytes of `asserted.tsv` for a selection of triples.
///
/// Issue #158: `asserted.tsv` is a list of triples with nothing in it that says
/// which graph they came from, so a certificate proves that its conclusions
/// follow from the assertions IN it, and cannot tell a reader those assertions
/// are the ones in their database. Closing that needs one thing a reader can
/// recompute, so there is exactly ONE function that turns a selection into
/// bytes. The writer uses it, and [`asserted_digest`] uses it. Two
/// implementations would be two answers.
pub fn asserted_bytes(triples: &[(String, String, String)]) -> anyhow::Result<Vec<u8>> {
    let mut out: Vec<u8> = Vec::with_capacity(triples.len() * 96);
    for (s, p, o) in triples {
        push_asserted_line(&mut out, s, p, o).map_err(|pos| {
            anyhow::anyhow!(
                "{} cannot be written to asserted.tsv",
                match pos {
                    Position::Subject => s,
                    Position::Predicate => p,
                    Position::Object => o,
                }
            )
        })?;
    }
    Ok(out)
}

/// The digest of the assertions a store yields under `request`, and how many
/// there were.
///
/// This is the number a certificate records. A reader who holds a store can
/// recompute it and learn whether the certificate in front of them is about
/// that store. It is not a proof of anything: a digest binds a certificate to a
/// SELECTION OF BYTES, not to a state of the world, and a store that changed
/// and changed back gives the same answer.
pub fn asserted_digest(
    graph: &Arc<GraphStore>,
    request: &ScopeRequest,
) -> anyhow::Result<(String, usize)> {
    use sha2::{Digest, Sha256};
    let (scope, _) = crate::temporal::resolve(graph, request)?;
    let (triples, _) = graph.triples_in_scope(&scope)?;
    let bytes = asserted_bytes(&triples)?;
    let mut h = Sha256::new();
    h.update(&bytes);
    Ok((format!("{:x}", h.finalize()), triples.len()))
}

/// Does the certificate in `dir` describe the assertions this store yields?
///
/// Reads `asserted.sha256` from the certificate directory, recomputes the
/// digest from `graph` under `request`, and reports both. The answer is
/// `matches: false` when the certificate is about a different selection, which
/// is the case issue #158 is about: a correct proof over the wrong graph.
/// The scope a certificate RECORDED, read back from its own `scope.tsv`.
///
/// Issue #159: `scope.tsv` is written into every certificate directory and no
/// checker reads it, so a run can record a scope that has nothing to do with
/// the graph it actually read and nothing catches it. Reading it here turns the
/// manifest from ATTESTED into DERIVED for anyone holding the store: apply the
/// recorded scope to that store, and the digest either reproduces or it does
/// not. A scope that was invented cannot select the triples the run hashed.
///
/// `None` when the file is absent or carries no `graph` line, which is the
/// certificate this check cannot speak about.
pub fn scope_from_manifest(text: &str) -> Option<crate::graph::ReadScope> {
    use crate::graph::ReadScope;
    let mut default_graph = true;
    let mut named: Vec<String> = Vec::new();
    let mut all = false;
    let mut saw_graph_line = false;
    for line in text.lines() {
        let mut f = line.split('\t');
        match (f.next(), f.next()) {
            (Some("default_graph"), Some(v)) => default_graph = v.trim() == "true",
            (Some("graph"), Some("*")) => {
                all = true;
                saw_graph_line = true;
            }
            (Some("graph"), Some(g)) => {
                named.push(g.trim().to_string());
                saw_graph_line = true;
            }
            _ => {}
        }
    }
    if !saw_graph_line {
        return None;
    }
    Some(if all {
        ReadScope::AllGraphs
    } else {
        ReadScope::Graphs { default_graph, named }
    })
}

pub fn certificate_binds_to_store(
    graph: &Arc<GraphStore>,
    dir: &std::path::Path,
    request: &ScopeRequest,
) -> anyhow::Result<serde_json::Value> {
    use sha2::{Digest, Sha256};
    let recorded_path = dir.join("asserted.sha256");
    let recorded = std::fs::read_to_string(&recorded_path)
        .map_err(|e| {
            anyhow::anyhow!(
                "cannot read {}: {e}. A certificate written before this check existed \
                 does not carry a digest, and nothing can bind it to a store after the fact",
                recorded_path.display()
            )
        })?
        .split_whitespace()
        .next()
        .unwrap_or_default()
        .to_string();

    // Prefer the scope the CERTIFICATE recorded over the one the caller asked
    // for (issue #159). The caller's scope is a second opinion about what the
    // run did; the certificate's is the run's own claim, and applying it is what
    // turns that claim into something the digest can refute.
    let manifest_text = std::fs::read_to_string(dir.join("scope.tsv")).unwrap_or_default();
    let (scope, scope_source) = match scope_from_manifest(&manifest_text) {
        Some(s) => (s, "certificate"),
        None => (crate::temporal::resolve(graph, request)?.0, "caller"),
    };
    let (triples, _) = graph.triples_in_scope(&scope)?;
    let bytes = asserted_bytes(&triples)?;
    let mut h = Sha256::new();
    h.update(&bytes);
    let actual = format!("{:x}", h.finalize());
    let matches = recorded == actual;

    // A boolean is not enough, and the first end-to-end run showed why: `reason`
    // MATERIALISES its inferences into the store by default, so re-reading the
    // same store afterwards yields the assertions plus the derivations, and a
    // bare "no" would send a reader looking for a wrong graph they do not have.
    // So the two selections are compared as sets, and the report says which way
    // they differ.
    let in_store: std::collections::BTreeSet<String> = String::from_utf8_lossy(&bytes)
        .lines()
        .map(|l| l.to_string())
        .collect();
    let in_cert: std::collections::BTreeSet<String> = std::fs::read_to_string(dir.join("asserted.tsv"))
        .unwrap_or_default()
        .lines()
        .map(|l| l.to_string())
        .collect();
    let extra: Vec<&String> = in_store.difference(&in_cert).collect();
    let missing: Vec<&String> = in_cert.difference(&in_store).collect();

    // "The store is a superset" is NOT enough to call it materialisation: a
    // genuinely different graph can be a superset too, and the first version of
    // this said "materialised" for one that merely added a triple the run
    // happened to derive. So the extra triples are checked against the
    // conclusions this very certificate recorded. If every one of them is a
    // conclusion of THIS run, materialisation explains the difference; if even
    // one is not, it does not, whatever the sizes are.
    let concluded: std::collections::BTreeSet<String> =
        std::fs::read_to_string(dir.join("derivations.tsv"))
            .unwrap_or_default()
            .lines()
            .filter_map(|l| {
                let f: Vec<&str> = l.split('\t').collect();
                (f.len() >= 4).then(|| format!("{}\t{}\t{}", f[1], f[2], f[3]))
            })
            .collect();
    let materialised =
        !extra.is_empty() && missing.is_empty() && extra.iter().all(|t| concluded.contains(*t));

    Ok(serde_json::json!({
        "matches": matches,
        "recorded": recorded,
        "recomputed": actual,
        "asserted_in_store": triples.len(),
        "scope_source": scope_source,
        "scope_means": if scope_source == "certificate" {
            "the scope came from the certificate's own scope.tsv and was APPLIED to this store. \
             A run that recorded a scope unrelated to the graph it read cannot reproduce the \
             digest, so the manifest is checked here rather than trusted (issue #159)"
        } else {
            "this certificate carries no readable scope.tsv, so the scope came from the caller. \
             Nothing here checks what the run actually read"
        },
        "asserted_in_certificate": in_cert.len(),
        "in_store_only": extra.len(),
        "in_certificate_only": missing.len(),
        "sample_in_store_only": extra.iter().take(3).collect::<Vec<_>>(),
        "sample_in_certificate_only": missing.iter().take(3).collect::<Vec<_>>(),
        "in_store_only_are_all_conclusions_of_this_run": !extra.is_empty()
            && extra.iter().all(|t| concluded.contains(*t)),
        "means": if matches {
            "the assertions this store yields under this scope hash to the digest the \
             certificate recorded. The certificate is about THIS selection of triples"
        } else if materialised {
            "the store CONTAINS every assertion the certificate lists, and more. The usual \
             cause is that the run materialised its inferences into this store, so what you \
             are comparing is the graph AFTER reasoning against the assertions BEFORE it. \
             Re-run the check against the store as it was, or reason with materialisation off"
        } else {
            "THE CERTIFICATE IS ABOUT A DIFFERENT GRAPH. Its derivations may well follow from \
             the assertions listed inside it, and a checker will say so; those assertions are \
             not the ones this store yields under this scope"
        },
        "likely_cause": if matches {
            serde_json::Value::Null
        } else if materialised {
            serde_json::json!("materialised_inferences")
        } else {
            serde_json::json!("different_graph")
        },
        "does_not_mean": "a digest binds a certificate to bytes, not to a state of the world. \
                          It cannot tell you the store was right, only that it is the one the \
                          certificate describes",
    }))
}

impl Position {
    fn name(self) -> &'static str {
        match self {
            Position::Subject => "subject",
            Position::Predicate => "predicate",
            Position::Object => "object",
        }
    }
}

/// Whether a term can be written to a certificate file without forging it.
///
/// This is TCB-4 and TCB-5, enforced here rather than observed of `oxrdf`.
///
/// The files are tab separated with one record per line and have no escaping
/// layer of their own, so a term carrying a tab gains a field, a term carrying a
/// newline splits a record in two, and either forges a triple the store never
/// held. Until 15 September 2026 the only thing standing between a tab and
/// `asserted.tsv` was `oxrdf`'s `print_quoted_str` for a literal and `oxiri`
/// refusing to parse for an IRI: `NamedNodeRef`'s `Display` is
/// `write!(f, "<{}>", self.as_str())` and escapes nothing at all. That is a
/// dependency's behaviour, pinned by a test that an upgrade would break loudly
/// but that cannot make it hold. This function makes it hold, in the refusing
/// direction: a term that does not fit the format means no certificate, not a
/// certificate a reader cannot trust.
///
/// The leading-byte condition is TCB-5. A literal is quoted and an IRI is
/// bracketed, so a literal whose lexical form is spelled exactly like an IRI
/// cannot collide with that IRI in a file where the two checkers compare terms
/// as opaque strings. Every term `GraphStore::all_triples` yields satisfies it
/// (`oxrdf`'s `Display` brackets a `NamedNode`, prefixes a `BlankNode` with
/// `_:` and quotes a `Literal`), and so does every constant `parse_pat` accepts,
/// so this refuses nothing the engine has any business writing.
fn term_fits_the_format(t: &str) -> bool {
    crate::boundary_core::term_fits_the_format(t.as_bytes())
}

/// The half of [`term_fits_the_format`] that is about the FORMAT and not about
/// N-Triples: a field is non-empty and carries no separator.
///
/// `horn.tsv` also writes variable names, which are not terms and have no
/// N-Triples spelling, and this is what they have to satisfy.
fn field_fits_the_format(f: &str) -> bool {
    crate::boundary_core::field_fits_the_format(f.as_bytes())
}

/// Append one line of `asserted.tsv`: `s TAB p TAB o NEWLINE`.
///
/// This is the whole of that file's grammar, and it is the narrowest point of
/// the trusted computing base: `OOCert.certificate_sound` is conditional on the
/// asserted graph, `OOCert.Parse.parseTriples` recovers it by splitting on
/// those two characters, and nothing between the two escapes anything. It lives
/// in one function so that the claim "a line is exactly three fields" is a
/// claim about one place, verified in `kani_harnesses` below rather than only
/// sampled.
///
/// Every term is checked BEFORE anything is appended, so a refusal leaves `out`
/// byte for byte as it was. A writer that appended a subject and then refused
/// the object would leave a half-line in the buffer, which is the same defect
/// the non-atomic materialiser had.
///
/// The buffer is a `Vec<u8>` and not a `String` because the body is
/// `crate::boundary_core::push_asserted_line_bytes`, the function Aeneas
/// translates. Nothing downstream notices: `std::fs::write` takes
/// `AsRef<[u8]>`, and every byte appended here comes from a `&str`.
fn push_asserted_line(out: &mut Vec<u8>, s: &str, p: &str, o: &str) -> Result<(), Position> {
    crate::boundary_core::push_asserted_line_bytes(out, s.as_bytes(), p.as_bytes(), o.as_bytes())
}

/// Append a triple as three further fields of a line already begun, the shape
/// `derivations.tsv` and `horn.tsv` use after their header fields. Same guard
/// and same all-or-nothing discipline as [`push_asserted_line`].
fn push_triple_fields(out: &mut Vec<u8>, s: &str, p: &str, o: &str) -> Result<(), Position> {
    crate::boundary_core::push_triple_fields_bytes(out, s.as_bytes(), p.as_bytes(), o.as_bytes())
}

// ─────────────────────────────────────────────────────────────────────────────
// The built-in rules, as data
//
// TCB-14 used to read: "`OOCert.checkStep` pattern-matches the premises
// positionally per rule. The emitter passes them in a hand-written order at
// each of the thirty-one `emit` call sites. A wrong order is a rejection, not a
// false pass, and `tests/lean_certificate_test.rs` covers every rule, but
// nothing derives the order from a single source."
//
// This is the single source. Each rule is a pattern over numbered variables,
// in the order `lean/OOCert/Rules.lean` matches them, and the emitter computes
// both the premise list AND the conclusion from it. A call site supplies the
// BINDING and nothing else, so it has no order to get wrong: the twenty-seven
// fixed-arity rules cannot drift from the checker by a mistake at the site.
// `tests/lean_certificate_test.rs` still runs the real checker over the corpus,
// and `tests/premise_order_test.rs` parses the arms out of `Rules.lean` and
// compares them with this table, so a change to either side that the other does
// not follow fails at `cargo test` rather than at a user's certificate.
//
// The four list rules (`cls-int1`, `cls-int2`, `cls-uni`, `cls-oo`) are not
// here. Their premises include an RDF list chain whose length is the length of
// the list, so they are not a fixed pattern and the checker matches them with
// `takeChain` rather than positionally. They keep an explicit premise vector
// and say so at the site.
// ─────────────────────────────────────────────────────────────────────────────

/// A vocabulary term a built-in rule's pattern fixes.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Kw {
    Type,
    SubClassOf,
    SubPropertyOf,
    Domain,
    Range,
    SameAs,
    InverseOf,
    TransitiveProperty,
    SymmetricProperty,
    EquivalentClass,
    EquivalentProperty,
    OnProperty,
    SomeValuesFrom,
    AllValuesFrom,
    HasValue,
}

impl Kw {
    /// The IRI, in the N-Triples spelling the store uses. Reading this out is
    /// how `tests/premise_order_test.rs` maps a `V.foo` in the Lean source onto
    /// a row of this table.
    pub fn iri(self) -> &'static str {
        match self {
            Kw::Type => RDF_TYPE,
            Kw::SubClassOf => RDFS_SUBCLASS,
            Kw::SubPropertyOf => RDFS_SUBPROP,
            Kw::Domain => RDFS_DOMAIN,
            Kw::Range => RDFS_RANGE,
            Kw::SameAs => OWL_SAMEAS,
            Kw::InverseOf => OWL_INVERSE,
            Kw::TransitiveProperty => OWL_TRANSITIVE,
            Kw::SymmetricProperty => OWL_SYMMETRIC,
            Kw::EquivalentClass => OWL_EQUIV_CLASS,
            Kw::EquivalentProperty => OWL_EQUIV_PROP,
            Kw::OnProperty => OWL_ON_PROPERTY,
            Kw::SomeValuesFrom => OWL_SOME_VALUES,
            Kw::AllValuesFrom => OWL_ALL_VALUES,
            Kw::HasValue => OWL_HAS_VALUE,
        }
    }

    /// The name `lean/OOCert/Semantics.lean` gives it, without the `V.`.
    pub fn lean_name(self) -> &'static str {
        match self {
            Kw::Type => "type",
            Kw::SubClassOf => "subClassOf",
            Kw::SubPropertyOf => "subPropertyOf",
            Kw::Domain => "domain",
            Kw::Range => "range",
            Kw::SameAs => "sameAs",
            Kw::InverseOf => "inverseOf",
            Kw::TransitiveProperty => "transitiveProperty",
            Kw::SymmetricProperty => "symmetricProperty",
            Kw::EquivalentClass => "equivalentClass",
            Kw::EquivalentProperty => "equivalentProperty",
            Kw::OnProperty => "onProperty",
            Kw::SomeValuesFrom => "someValuesFrom",
            Kw::AllValuesFrom => "allValuesFrom",
            Kw::HasValue => "hasValue",
        }
    }
}

/// One position of a built-in rule's pattern: a slot in the binding, or a
/// vocabulary term the rule fixes.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Slot {
    Var(usize),
    Fixed(Kw),
}

const V0: Slot = Slot::Var(0);
const V1: Slot = Slot::Var(1);
const V2: Slot = Slot::Var(2);
const V3: Slot = Slot::Var(3);
const V4: Slot = Slot::Var(4);
const TYPE: Slot = Slot::Fixed(Kw::Type);
const SUBCLASS: Slot = Slot::Fixed(Kw::SubClassOf);
const SUBPROP: Slot = Slot::Fixed(Kw::SubPropertyOf);
const DOMAIN: Slot = Slot::Fixed(Kw::Domain);
const RANGE: Slot = Slot::Fixed(Kw::Range);
const SAMEAS: Slot = Slot::Fixed(Kw::SameAs);
const INVERSE: Slot = Slot::Fixed(Kw::InverseOf);
const TRANSITIVE: Slot = Slot::Fixed(Kw::TransitiveProperty);
const SYMMETRIC: Slot = Slot::Fixed(Kw::SymmetricProperty);
const EQ_CLASS: Slot = Slot::Fixed(Kw::EquivalentClass);
const EQ_PROP: Slot = Slot::Fixed(Kw::EquivalentProperty);
const ON_PROP: Slot = Slot::Fixed(Kw::OnProperty);
const SVF: Slot = Slot::Fixed(Kw::SomeValuesFrom);
const AVF: Slot = Slot::Fixed(Kw::AllValuesFrom);
const HAS_VALUE: Slot = Slot::Fixed(Kw::HasValue);

/// A built-in rule with a fixed premise arity, as a pattern.
pub struct BuiltinRule {
    /// The rule id written into `derivations.tsv`, which `OOCert.Rule.ofName?`
    /// has to accept. Two rows may share a name: `scm-eqc1` and `scm-eqp1` each
    /// license two conclusions from one premise, and the checker accepts
    /// either.
    pub name: &'static str,
    /// Names for the binding slots, for readability and for the error a
    /// mis-sized binding produces. The LENGTH is the arity.
    pub vars: &'static [&'static str],
    /// The premises, in the order the checker matches them.
    pub body: &'static [[Slot; 3]],
    pub head: [Slot; 3],
}

/// The rows of [`BUILTIN_RULES`], by name, so a call site names a rule rather
/// than an index. `builtin_rule_table_is_indexed_by_its_enum` pins the
/// correspondence.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Rl {
    Rdfs2,
    Rdfs3,
    Rdfs5,
    Rdfs7,
    Rdfs9,
    Rdfs11,
    PrpTrp,
    PrpSymp,
    PrpInv1,
    PrpInv2,
    EqSym,
    ScmEqc1Fwd,
    ScmEqc1Rev,
    ScmEqp1Fwd,
    ScmEqp1Rev,
    ClsSvf1,
    ClsAvf,
    ClsHv1,
    ClsHv2,
    ScmSvf1,
    ScmSvf2,
    ScmAvf1,
    ScmAvf2,
    ScmDom1,
    ScmDom2,
    ScmRng1,
    ScmRng2,
}

impl Rl {
    /// Every row, in table order. `each_row_is_at_its_own_index` pins that
    /// `Rl::X as usize` really is the index of `X`'s row, which is the whole
    /// basis of `BUILTIN_RULES[r as usize]`.
    pub const ALL: &'static [Rl] = &[
        Rl::Rdfs2, Rl::Rdfs3, Rl::Rdfs5, Rl::Rdfs7, Rl::Rdfs9, Rl::Rdfs11,
        Rl::PrpTrp, Rl::PrpSymp, Rl::PrpInv1, Rl::PrpInv2, Rl::EqSym,
        Rl::ScmEqc1Fwd, Rl::ScmEqc1Rev, Rl::ScmEqp1Fwd, Rl::ScmEqp1Rev,
        Rl::ClsSvf1, Rl::ClsAvf, Rl::ClsHv1, Rl::ClsHv2,
        Rl::ScmSvf1, Rl::ScmSvf2, Rl::ScmAvf1, Rl::ScmAvf2,
        Rl::ScmDom1, Rl::ScmDom2, Rl::ScmRng1, Rl::ScmRng2,
    ];
}

/// Every fixed-arity built-in rule, in `Rl` order.
///
/// Read this against the table in the module docstring of
/// `lean/OOCert/Rules.lean`. They are the same table; `tests/premise_order_test.rs`
/// checks that mechanically against the `checkStep` arms rather than against
/// the prose.
pub const BUILTIN_RULES: &[BuiltinRule] = &[
    BuiltinRule { name: "rdfs2", vars: &["s", "p", "o", "c"],
        body: &[[V0, V1, V2], [V1, DOMAIN, V3]], head: [V0, TYPE, V3] },
    BuiltinRule { name: "rdfs3", vars: &["s", "p", "o", "c"],
        body: &[[V0, V1, V2], [V1, RANGE, V3]], head: [V2, TYPE, V3] },
    BuiltinRule { name: "rdfs5", vars: &["a", "b", "c"],
        body: &[[V0, SUBPROP, V1], [V1, SUBPROP, V2]], head: [V0, SUBPROP, V2] },
    BuiltinRule { name: "rdfs7", vars: &["s", "p", "o", "q"],
        body: &[[V0, V1, V2], [V1, SUBPROP, V3]], head: [V0, V3, V2] },
    BuiltinRule { name: "rdfs9", vars: &["x", "a", "b"],
        body: &[[V0, TYPE, V1], [V1, SUBCLASS, V2]], head: [V0, TYPE, V2] },
    BuiltinRule { name: "rdfs11", vars: &["a", "b", "c"],
        body: &[[V0, SUBCLASS, V1], [V1, SUBCLASS, V2]], head: [V0, SUBCLASS, V2] },
    BuiltinRule { name: "prp-trp", vars: &["p", "x", "y", "z"],
        body: &[[V0, TYPE, TRANSITIVE], [V1, V0, V2], [V2, V0, V3]], head: [V1, V0, V3] },
    BuiltinRule { name: "prp-symp", vars: &["p", "x", "y"],
        body: &[[V0, TYPE, SYMMETRIC], [V1, V0, V2]], head: [V2, V0, V1] },
    BuiltinRule { name: "prp-inv1", vars: &["p", "q", "x", "y"],
        body: &[[V0, INVERSE, V1], [V2, V0, V3]], head: [V3, V1, V2] },
    BuiltinRule { name: "prp-inv2", vars: &["p", "q", "x", "y"],
        body: &[[V0, INVERSE, V1], [V2, V1, V3]], head: [V3, V0, V2] },
    BuiltinRule { name: "eq-sym", vars: &["a", "b"],
        body: &[[V0, SAMEAS, V1]], head: [V1, SAMEAS, V0] },
    BuiltinRule { name: "scm-eqc1", vars: &["a", "b"],
        body: &[[V0, EQ_CLASS, V1]], head: [V0, SUBCLASS, V1] },
    BuiltinRule { name: "scm-eqc1", vars: &["a", "b"],
        body: &[[V0, EQ_CLASS, V1]], head: [V1, SUBCLASS, V0] },
    BuiltinRule { name: "scm-eqp1", vars: &["a", "b"],
        body: &[[V0, EQ_PROP, V1]], head: [V0, SUBPROP, V1] },
    BuiltinRule { name: "scm-eqp1", vars: &["a", "b"],
        body: &[[V0, EQ_PROP, V1]], head: [V1, SUBPROP, V0] },
    BuiltinRule { name: "cls-svf1", vars: &["r", "p", "c", "x", "y"],
        body: &[[V0, ON_PROP, V1], [V0, SVF, V2], [V3, V1, V4], [V4, TYPE, V2]],
        head: [V3, TYPE, V0] },
    BuiltinRule { name: "cls-avf", vars: &["r", "p", "c", "x", "y"],
        body: &[[V0, ON_PROP, V1], [V0, AVF, V2], [V3, TYPE, V0], [V3, V1, V4]],
        head: [V4, TYPE, V2] },
    BuiltinRule { name: "cls-hv1", vars: &["r", "p", "v", "x"],
        body: &[[V0, ON_PROP, V1], [V0, HAS_VALUE, V2], [V3, TYPE, V0]],
        head: [V3, V1, V2] },
    BuiltinRule { name: "cls-hv2", vars: &["r", "p", "v", "x"],
        body: &[[V0, ON_PROP, V1], [V0, HAS_VALUE, V2], [V3, V1, V2]],
        head: [V3, TYPE, V0] },
    BuiltinRule { name: "scm-svf1", vars: &["c1", "y1", "p", "c2", "y2"],
        body: &[[V0, SVF, V1], [V0, ON_PROP, V2], [V3, SVF, V4], [V3, ON_PROP, V2],
                [V1, SUBCLASS, V4]],
        head: [V0, SUBCLASS, V3] },
    BuiltinRule { name: "scm-svf2", vars: &["c1", "y", "p1", "c2", "p2"],
        body: &[[V0, SVF, V1], [V0, ON_PROP, V2], [V3, SVF, V1], [V3, ON_PROP, V4],
                [V2, SUBPROP, V4]],
        head: [V0, SUBCLASS, V3] },
    BuiltinRule { name: "scm-avf1", vars: &["c1", "y1", "p", "c2", "y2"],
        body: &[[V0, AVF, V1], [V0, ON_PROP, V2], [V3, AVF, V4], [V3, ON_PROP, V2],
                [V1, SUBCLASS, V4]],
        head: [V0, SUBCLASS, V3] },
    // The conclusion is the other way round, and it is the one place in this
    // table where that is true. A universal restriction is antitone in its
    // property, so `all p2 y` is the SMALLER class; writing this row the way
    // `scm-svf2` is written gives a step no model supports, and
    // `OOCert.the_natural_avf2_direction_is_not_entailed` is the refutation.
    BuiltinRule { name: "scm-avf2", vars: &["c1", "y", "p1", "c2", "p2"],
        body: &[[V0, AVF, V1], [V0, ON_PROP, V2], [V3, AVF, V1], [V3, ON_PROP, V4],
                [V2, SUBPROP, V4]],
        head: [V3, SUBCLASS, V0] },
    BuiltinRule { name: "scm-dom1", vars: &["p", "c1", "c2"],
        body: &[[V0, DOMAIN, V1], [V1, SUBCLASS, V2]], head: [V0, DOMAIN, V2] },
    BuiltinRule { name: "scm-dom2", vars: &["p2", "c", "p1"],
        body: &[[V0, DOMAIN, V1], [V2, SUBPROP, V0]], head: [V2, DOMAIN, V1] },
    BuiltinRule { name: "scm-rng1", vars: &["p", "c1", "c2"],
        body: &[[V0, RANGE, V1], [V1, SUBCLASS, V2]], head: [V0, RANGE, V2] },
    BuiltinRule { name: "scm-rng2", vars: &["p2", "c", "p1"],
        body: &[[V0, RANGE, V1], [V2, SUBPROP, V0]], head: [V2, RANGE, V1] },
];

/// The rule names the four list rules use. Not in [`BUILTIN_RULES`] because
/// their premises are a variable-length chain, listed here so a test can assert
/// that the two sets together are exactly the checker's rule set and that
/// nothing fell between them.
pub const CHAINED_RULES: &[&str] = &["cls-int1", "cls-int2", "cls-uni", "cls-oo"];

/// The interned id of each vocabulary term a rule pattern can fix.
struct RuleVocab {
    type_: u32,
    subclass: u32,
    subprop: u32,
    domain: u32,
    range: u32,
    sameas: u32,
    inverse: u32,
    transitive: u32,
    symmetric: u32,
    equiv_class: u32,
    equiv_prop: u32,
    on_property: u32,
    svf: u32,
    avf: u32,
    has_value: u32,
}

/// What a rule site hands the emitter.
///
/// `Bound` is a row of [`BUILTIN_RULES`] plus the binding for its variables:
/// the site chooses the terms, the table chooses the order and the conclusion.
/// `Chained` is one of the four list rules, whose premises are a constructor
/// triple, an RDF list chain of the list's own length, and the typings, and
/// which therefore has no fixed pattern to be a row of.
enum Fired<'a> {
    Bound(Rl, &'a [u32]),
    Chained(&'static str, Fact, &'a [Fact]),
}

impl RuleVocab {
    fn id(&self, k: Kw) -> u32 {
        match k {
            Kw::Type => self.type_,
            Kw::SubClassOf => self.subclass,
            Kw::SubPropertyOf => self.subprop,
            Kw::Domain => self.domain,
            Kw::Range => self.range,
            Kw::SameAs => self.sameas,
            Kw::InverseOf => self.inverse,
            Kw::TransitiveProperty => self.transitive,
            Kw::SymmetricProperty => self.symmetric,
            Kw::EquivalentClass => self.equiv_class,
            Kw::EquivalentProperty => self.equiv_prop,
            Kw::OnProperty => self.on_property,
            Kw::SomeValuesFrom => self.svf,
            Kw::AllValuesFrom => self.avf,
            Kw::HasValue => self.has_value,
        }
    }

    fn fill(&self, a: &[Slot; 3], b: &[u32]) -> Fact {
        let one = |s: Slot| match s {
            Slot::Var(i) => b[i],
            Slot::Fixed(k) => self.id(k),
        };
        (one(a[0]), one(a[1]), one(a[2]))
    }
}

/// The message a refused term produces. One place, so the four writers say the
/// same thing, and outside the functions Kani reasons about.
fn unwritable_term(file: &str, pos: Position, term: &str) -> anyhow::Error {
    anyhow::anyhow!(
        "internal: the {} of a triple bound for {file} is {term:?}, which does not fit the \
         certificate format: a term must be non-empty, must carry no tab, newline or carriage \
         return, and must be in N-Triples spelling (<iri>, _:blank or a quoted literal). Writing \
         it would let the term forge a field or a record, so no certificate was written. See \
         TCB-4 and TCB-5 in docs/trusted-computing-base.md",
        pos.name()
    )
}

/// Intern strings to u32 IDs for efficient reasoning.
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(),
        }
    }

    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
    }

    fn resolve(&self, id: u32) -> &str {
        &self.to_str[id as usize]
    }
}

/// OWL2-RL reasoner using interned u32 triples and fixpoint iteration.
///
/// Profiles:
///   "rdfs"       — RDFS rules (subclass, domain/range, subproperty)
///   "owl-rl"     — RDFS + core OWL-RL (transitive, symmetric, inverse,
///                  sameAs, equivalentClass/Property) + the schema rules that
///                  move a domain or a range along the class and property
///                  hierarchies (scm-dom1, scm-dom2, scm-rng1, scm-rng2)
///   "owl-rl-ext" — All above + someValuesFrom, allValuesFrom, hasValue,
///                  intersectionOf (both directions), unionOf, oneOf, and the
///                  four rules that order two restrictions by their filler or
///                  by their property (scm-svf1, scm-svf2, scm-avf1, scm-avf2)
///
/// Twenty-nine rule ids in all, every one of them with an arm in
/// `lean/OOCert/Rules.lean` and a lemma in `lean/OOCert/Soundness.lean`. A rule
/// the checker cannot prove sound is a rule this file does not run: that is the
/// contract, and `tests/lean_certificate_test.rs` walks the whole corpus to
/// enforce it.
///
/// What is deliberately NOT here, with the reason, because "not implemented" and
/// "not sound" are different statements and a reader is owed which one applies:
///
///   * `eq-ref` is sound and useless. It asserts `owl:sameAs` reflexivity for
///     every term in every position. Measured on the largest file this
///     repository ships, `benchmark/oaei/data/anatomy/human.owl`, that is
///     17,194 triples of no consequence added to a graph of 35,354. It would
///     also put a derivation into the empty-graph case that
///     `OOCert.not_everything_is_entailed` depends on staying empty.
///   * The `eq-rep-s`, `eq-rep-p`, `eq-rep-o` family is sound and quadratic in
///     the size of a `owl:sameAs` clique. Counted by SPARQL over every RDF file
///     this repository tracks that parses and is under the size cap, the corpus
///     contains ZERO `owl:sameAs` triples, so the cost is certain and the
///     benefit here is nothing at all. Three files mention `sameAs` inside an
///     `rdfs:comment` and none of them asserts one.
///   * `scm-cls`, `scm-op` and `scm-dp` are sound and emit reflexive trivia
///     (`c rdfs:subClassOf c`, `c owl:equivalentClass c`) of exactly the kind
///     the `a != b` guards elsewhere in this file exist to suppress.
///   * The `dt-*` family needs a datatype VALUE space. `OOCert.Semantics`
///     reads a literal as its N-Triples spelling and says so, so there is no
///     condition here for those rules to be sound against.
///   * Nothing concludes `false`. Every rule above concludes a triple, which
///     is what the `oo-cert/1` format can carry. The seventeen rules of the
///     profile that conclude `false` are handled AFTER the fixpoint instead,
///     by [`find_clashes`], and written in the separate `oo-refute/1` format
///     that `lean/OOCert/Refute.lean` checks. Only `cax-dw` earns a
///     certificate there, because it is the only clash rule the Lean checker
///     has a semantic condition for; the rest are reported as found and
///     uncertified, and the two must never share a word.
///
/// The graph materialised inferences are written to when the caller asks for
/// them to be kept apart from what was asserted.
pub const INFERRED_GRAPH: &str = "https://open-ontologies.org/graph/inferred";

/// Where `reason` puts the triples it materialises.
///
/// The choice is a failure-direction one, not a matter of taste. A marker
/// triple on statements sitting in the default graph obliges every consumer to
/// filter, and the one that forgets publishes an inference as an assertion. A
/// separate graph fails the other way: a consumer that forgets sees fewer
/// triples, never wrong ones.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum InferenceTarget {
    /// Merge into the default graph beside the asserted statements. The
    /// historical behaviour, kept so existing callers keep their contract.
    DefaultGraph,
    /// Keep them in [`INFERRED_GRAPH`], where nothing downstream can mistake
    /// an inference for an assertion.
    Inferred,
}

pub struct Reasoner;

impl Reasoner {
    pub fn run(
        graph: &Arc<GraphStore>,
        profile: &str,
        materialize: bool,
    ) -> anyhow::Result<String> {
        Self::run_with_target(graph, profile, materialize, InferenceTarget::DefaultGraph)
    }

    pub fn run_with_target(
        graph: &Arc<GraphStore>,
        profile: &str,
        materialize: bool,
        target: InferenceTarget,
    ) -> anyhow::Result<String> {
        Self::run_full(graph, profile, materialize, target, None)
    }

    /// Run the forward-chaining reasoner and, when `certificate_dir` is given,
    /// write a derivation certificate beside the result.
    ///
    /// The certificate is three tab-separated files: `asserted.tsv`, every
    /// triple the run started from, `derivations.tsv`, one line per inferred
    /// triple naming the rule that produced it and the premises the rule read,
    /// and `scope.tsv`, which graphs those triples were read from. The Lean
    /// checker reads the first two and cannot read the third: see
    /// [`run_scoped`](Self::run_scoped). `lean/` holds a checker for that format whose soundness is a
    /// machine-checked theorem (`OOCert.certificate_sound`): a certificate it
    /// accepts contains only triples entailed by the asserted graph under the
    /// RDF-based semantics of the vocabulary the rules use. The engine's own
    /// correctness is therefore not the thing a consumer has to trust; the
    /// checker's is, and the checker is a few hundred lines with a proof.
    ///
    /// The first thing the checker caught was in this file: `cls-svf1` used
    /// to derive membership in a subclass from membership in its restriction
    /// superclass, the converse of the axiom
    /// (tests/reason_rl_ext_soundness_test.rs).
    ///
    /// Not available for `owl-dl`: the tableaux path has no rule trace.
    ///
    /// Reads the whole store. Over a store that uses the temporal vocabulary
    /// that is now REFUSED rather than done silently — see
    /// [`run_scoped`](Self::run_scoped), which this delegates to.
    pub fn run_full(
        graph: &Arc<GraphStore>,
        profile: &str,
        materialize: bool,
        target: InferenceTarget,
        certificate_dir: Option<&std::path::Path>,
    ) -> anyhow::Result<String> {
        Self::run_scoped(
            graph,
            profile,
            materialize,
            target,
            certificate_dir,
            &ScopeRequest::Unscoped,
        )
    }

    /// The whole derivation DAG of a run: every asserted triple, every triple
    /// the fixpoint reached, and EVERY applicable ground rule instance rather
    /// than one per conclusion.
    ///
    /// This is the substrate [`crate::justify`] and [`crate::provenance`] read.
    /// Nothing is materialised and no certificate is written: the caller gets
    /// the structure and decides what to do with it.
    ///
    /// Refuses `owl-dl` for the same reason `--certificate` does: the tableaux
    /// path has no rule trace, so there is no DAG to hand back and an empty one
    /// would read as "nothing was derived".
    ///
    /// It asks for no scope, which is not the same as escaping the scope
    /// gate: `ScopeRequest::Unscoped` still goes through
    /// [`crate::temporal::resolve`], so over a versioned store naming no
    /// instant this is REFUSED like any other run. A DAG over the union of
    /// every version would explain a state that held at no instant.
    pub fn derivation_graph(
        graph: &Arc<GraphStore>,
        profile: &str,
    ) -> anyhow::Result<DerivationGraph> {
        if profile == "owl-dl" {
            anyhow::bail!(
                "the owl-dl tableaux path records no rule applications, so there is no derivation \
                 DAG to explain from; run rdfs, owl-rl or owl-rl-ext"
            );
        }
        let mut cap = Capture::default();
        Self::run_scoped_capturing(
            graph,
            profile,
            false,
            InferenceTarget::DefaultGraph,
            None,
            &ScopeRequest::Unscoped,
            Some(&mut cap),
        )?;
        cap.out.ok_or_else(|| {
            anyhow::anyhow!("the reasoner returned without filling the derivation DAG; this is a bug")
        })
    }

    /// [`run_full`](Self::run_full) over a stated set of graphs (#108).
    ///
    /// Every entry point above funnels here, so the scope gate cannot be
    /// evaded by picking an older signature. What the gate does is in
    /// [`crate::temporal::resolve`]; what it means for THIS path is:
    ///
    ///  * A store with no temporal vocabulary is unaffected under every
    ///    request, and produces the same bytes it produced at 1.3.0.
    ///  * A bi-temporal store with no instant named is refused. Nothing else
    ///    in this engine would have caught that run: the reasoner would have
    ///    computed a correct closure over the union of every version, the
    ///    certificate would have been a true statement about the graph in
    ///    `asserted.tsv`, and the Lean checker would have accepted it. The
    ///    graph in `asserted.tsv` is the thing that would have been wrong, and
    ///    the checker cannot see that far.
    ///  * NO run over a versioned store MATERIALISES, and it says so rather
    ///    than dropping the flag. There is nowhere in such a store that a
    ///    conclusion can be written without becoming an axiom of every
    ///    snapshot: the default graph is in scope at every instant by being
    ///    timeless, and so is a named inference graph that carries no validity
    ///    description. That bites both ways round. A snapshot's conclusions
    ///    held at ONE instant and would be read at all of them; an
    ///    `all_versions` run's held at NONE, and writing those in is the leak
    ///    this issue is about arriving through the exit rather than the
    ///    entrance. The precedent is `rules_file`, refused for the same shape
    ///    of reason.
    ///  * The scope is recorded, in the report and, when a certificate is
    ///    written, in `scope.tsv` beside `asserted.tsv`.
    pub fn run_scoped(
        graph: &Arc<GraphStore>,
        profile: &str,
        materialize: bool,
        target: InferenceTarget,
        certificate_dir: Option<&std::path::Path>,
        request: &ScopeRequest,
    ) -> anyhow::Result<String> {
        Self::run_scoped_capturing(
            graph,
            profile,
            materialize,
            target,
            certificate_dir,
            request,
            None,
        )
    }

    /// [`run_scoped`](Self::run_scoped) with somewhere to put the derivation
    /// DAG. Private because `Capture` is, which is why the public form above
    /// exists rather than this taking an `Option` nobody outside can build.
    #[allow(clippy::too_many_arguments)]
    fn run_scoped_capturing(
        graph: &Arc<GraphStore>,
        profile: &str,
        materialize: bool,
        target: InferenceTarget,
        certificate_dir: Option<&std::path::Path>,
        request: &ScopeRequest,
        capture: Option<&mut Capture>,
    ) -> anyhow::Result<String> {
        let (scope, manifest) = crate::temporal::resolve(graph, request)?;
        if !scope.is_all_graphs() && profile == "owl-dl" {
            anyhow::bail!(
                "the owl-dl tableaux path reads the whole store and has no scoped form yet \
                 (src/tableaux.rs reads GraphStore::all_triples), so a snapshot argument here \
                 would be accepted and ignored. Run rdfs, owl-rl or owl-rl-ext for a scoped run"
            );
        }
        if manifest.store_has_versions() && materialize {
            anyhow::bail!(
                "a run over a versioned store does not materialise. There is nowhere in such a \
                 store that a conclusion can be written without becoming an axiom of every \
                 snapshot: the default graph is in scope at every instant because it is \
                 timeless, and so is an inference graph carrying no validity description. That \
                 bites both ways round. A SNAPSHOT's conclusions held at one instant and would \
                 be read at all of them; a run over EVERY VERSION at once (all_versions) draws \
                 its conclusions from a state that held at no instant, and writing those into \
                 the timeless graph is the leak of #108 arriving through the exit rather than \
                 the entrance. Run with materialize=false and read the inferences from the \
                 report, or describe a destination graph with temporal:validFrom / validTo \
                 yourself and load them into it"
            );
        }
        Self::run_in_scope(
            graph,
            profile,
            materialize,
            target,
            certificate_dir,
            &scope,
            &manifest,
            capture,
        )
    }

    #[allow(clippy::too_many_arguments)]
    fn run_in_scope(
        graph: &Arc<GraphStore>,
        profile: &str,
        materialize: bool,
        target: InferenceTarget,
        certificate_dir: Option<&std::path::Path>,
        scope: &crate::graph::ReadScope,
        manifest: &crate::temporal::ScopeManifest,
        capture: Option<&mut Capture>,
    ) -> anyhow::Result<String> {
        // Delegate OWL-DL to tableaux reasoner
        if profile == "owl-dl" {
            if certificate_dir.is_some() {
                anyhow::bail!(
                    "the owl-dl tableaux path emits no derivation certificate; \
                     run rdfs, owl-rl or owl-rl-ext for a certified run"
                );
            }
            if target == InferenceTarget::Inferred {
                // Say so rather than materialise into the default graph while
                // the caller believes the inferences were kept apart.
                anyhow::bail!(
                    "the owl-dl tableaux path does not yet write to {INFERRED_GRAPH}; \
                     run it with the default target, or use owl-rl / owl-rl-ext"
                );
            }
            // Only ever reached with the whole store, since `run_scoped`
            // refuses a snapshot here. It still says so: "the scope key is on
            // every report" is a sentence a reader has to be able to rely on,
            // and a tool that omits it on one profile makes its absence
            // ambiguous between "read everything" and "older build".
            let raw = crate::tableaux::DlReasoner::run(graph, materialize)?;
            let mut parsed: serde_json::Value = serde_json::from_str(&raw)?;
            if parsed.is_object() {
                parsed["scope"] = manifest.to_json();
                return Ok(parsed.to_string());
            }
            return Ok(raw);
        }

        let profile_used = match profile {
            "owl-rl" => "owl-rl",
            "owl-rl-ext" => "owl-rl-ext",
            _ => "rdfs",
        };
        let include_owl = profile_used == "owl-rl" || profile_used == "owl-rl-ext";
        let include_ext = profile_used == "owl-rl-ext";

        // Extract and intern the triples of the graphs THIS RUN MAY READ. For
        // `ReadScope::AllGraphs` that is `all_triples()` and the same bytes as
        // before; for a snapshot it is the default graph plus the in-scope
        // named graphs, and `asserted.tsv` below is written from exactly this
        // list, so the certificate is about the graph the scope selected and
        // `scope.tsv` says which one that was.
        let (raw_triples, graphs_read) = graph.triples_in_scope(scope)?;
        let mut interner = Interner::new();
        let mut facts: Vec<(u32, u32, u32)> = Vec::with_capacity(raw_triples.len());
        for (s, p, o) in &raw_triples {
            facts.push((interner.intern(s), interner.intern(p), interner.intern(o)));
        }

        // Intern well-known IRIs
        let rdf_type = interner.intern(RDF_TYPE);
        let rdfs_subclass = interner.intern(RDFS_SUBCLASS);
        let rdfs_subprop = interner.intern(RDFS_SUBPROP);
        let owl_sameas = interner.intern(OWL_SAMEAS);
        // Every well-known id is interned once, before the loop, so the
        // schema indices below can be rebuilt from the closure each iteration
        // without borrowing the interner mutably inside it.
        let rdfs_domain = interner.intern(RDFS_DOMAIN);
        let rdfs_range = interner.intern(RDFS_RANGE);
        let owl_transitive = interner.intern(OWL_TRANSITIVE);
        let owl_symmetric = interner.intern(OWL_SYMMETRIC);
        let owl_inverse = interner.intern(OWL_INVERSE);
        let owl_equiv_class = interner.intern(OWL_EQUIV_CLASS);
        let owl_equiv_prop = interner.intern(OWL_EQUIV_PROP);
        let owl_on_property = interner.intern(OWL_ON_PROPERTY);
        let owl_some_values = interner.intern(OWL_SOME_VALUES);
        let owl_all_values = interner.intern(OWL_ALL_VALUES);
        let owl_has_value = interner.intern(OWL_HAS_VALUE);
        let owl_intersection = interner.intern(OWL_INTERSECTION);
        let owl_union = interner.intern(OWL_UNION);
        let owl_oneof = interner.intern(OWL_ONEOF);
        let rdf_first = interner.intern(RDF_FIRST);
        let rdf_rest = interner.intern(RDF_REST);
        let rdf_nil = interner.intern(RDF_NIL);

        // The same well-known ids, in the shape `BUILTIN_RULES` reads them.
        // Every fixed term in every built-in rule pattern resolves through
        // this, so a rule's vocabulary is not restated at its call site either.
        let rule_vocab = RuleVocab {
            type_: rdf_type,
            subclass: rdfs_subclass,
            subprop: rdfs_subprop,
            domain: rdfs_domain,
            range: rdfs_range,
            sameas: owl_sameas,
            inverse: owl_inverse,
            transitive: owl_transitive,
            symmetric: owl_symmetric,
            equiv_class: owl_equiv_class,
            equiv_prop: owl_equiv_prop,
            on_property: owl_on_property,
            svf: owl_some_values,
            avf: owl_all_values,
            has_value: owl_has_value,
        };

        // The clash detector's vocabulary. Nothing below drives a rule in the
        // fixpoint: it is read once, after it, by `find_clashes`. Interning a
        // term the graph never mentions costs one entry and makes every lookup
        // a u32 comparison, the same as every other well-known id here.
        let clash_vocab = ClashVocab {
            rdf_type,
            disjoint_with: interner.intern(OWL_DISJOINT_WITH),
            nothing: interner.intern(OWL_NOTHING),
            complement_of: interner.intern(OWL_COMPLEMENT_OF),
            irreflexive: interner.intern(OWL_IRREFLEXIVE),
            asymmetric: interner.intern(OWL_ASYMMETRIC),
            prop_disjoint_with: interner.intern(OWL_PROP_DISJOINT_WITH),
            same_as: owl_sameas,
            different_from: interner.intern(OWL_DIFFERENT_FROM),
            max_cardinality: interner.intern(OWL_MAX_CARDINALITY),
            on_property: owl_on_property,
            source_individual: interner.intern(OWL_SOURCE_INDIVIDUAL),
            assertion_property: interner.intern(OWL_ASSERTION_PROPERTY),
            target_individual: interner.intern(OWL_TARGET_INDIVIDUAL),
            target_value: interner.intern(OWL_TARGET_VALUE),
        };

        // ── Fixpoint iteration ──────────────────────────────────────
        let mut triple_set: HashSet<Fact> = facts.iter().copied().collect();
        let initial_size = triple_set.len();
        let mut iterations = 0;
        // Which of the two break conditions ended the loop. A run that stopped
        // at the cap has a closure that is a LOWER BOUND, and every consumer
        // that compares two closures has to be able to see that: a truncated
        // closure(G) missing a conclusion closure(P) reached looks exactly like
        // an unsoundness in the engine. `run_horn` already reports the same
        // field, so this is consistency rather than novelty.
        let mut fixpoint_reached = false;

        // Certificate bookkeeping. A conclusion is recorded the first time it
        // is derived and never again, so the certificate has exactly one line
        // per inferred triple and `derivations.len() == inferred_count` is an
        // invariant the tests pin. Nothing here runs unless a certificate was
        // asked for: the hot path pays one branch per candidate triple.
        //
        // A capture asks for the same premise lists, so it turns `certify` on
        // too: the per-rule premise vectors are built behind that flag, and a
        // DAG whose hyperedges carried no premises would be a set of
        // disconnected nodes wearing the word "derivation".
        let mut capture = capture;
        let certify = certificate_dir.is_some() || capture.is_some();
        let mut derivations: Vec<Derivation> = Vec::new();
        let mut recorded: HashSet<Fact> = HashSet::new();

        // Conclusions refused for being unwritable, and up to three of them to
        // show. A set rather than a counter, for the reason `run_horn` gives:
        // a refused conclusion never enters `triple_set`, so every later round
        // derives it again and a counter would report attempts.
        let mut refused: HashSet<Fact> = HashSet::new();
        let mut skipped_samples: Vec<String> = Vec::new();

        loop {
            iterations += 1;
            let before = triple_set.len();
            let mut new: Vec<Fact> = Vec::new();

            // Schema indices, rebuilt from the closure on every iteration.
            //
            // These used to be filtered ONCE out of the pre-loop snapshot while
            // only the three data indices below were rebuilt, so the run was
            // not a fixpoint of its own rule set: a `rdfs:domain` triple that
            // the reasoner itself derived, by rdfs7 over a subproperty of
            // rdfs:domain or by scm-eqp, was never used, and running `reason` a
            // second time derived more than running it once. The number of runs
            // needed was the length of the longest chain of such rules, not two.
            //
            // For certificates that mattered more than for query answers.
            // Materialising turns run N's conclusions into run N+1's premises,
            // so `asserted.tsv` could list the reasoner's own output as an
            // axiom with nothing marking it as derived, and the soundness
            // theorem is conditional on the assertions. Reaching the fixpoint
            // in one run is what makes a single certificate the whole story.
            //
            // The cost is a constant factor on a scan the loop already does.
            let domain_map: Vec<(u32, u32)> = triple_set.iter()
                .filter(|&&(_, p, _)| p == rdfs_domain)
                .map(|&(s, _, o)| (s, o)).collect();
            let range_map: Vec<(u32, u32)> = triple_set.iter()
                .filter(|&&(_, p, _)| p == rdfs_range)
                .map(|&(s, _, o)| (s, o)).collect();
            let transitive_set: HashSet<u32> = triple_set.iter()
                .filter(|&&(_, p, o)| p == rdf_type && o == owl_transitive)
                .map(|&(s, _, _)| s).collect();
            let symmetric_set: HashSet<u32> = triple_set.iter()
                .filter(|&&(_, p, o)| p == rdf_type && o == owl_symmetric)
                .map(|&(s, _, _)| s).collect();
            let inverse_pairs: Vec<(u32, u32)> = triple_set.iter()
                .filter(|&&(_, p, _)| p == owl_inverse)
                .map(|&(s, _, o)| (s, o)).collect();
            let equiv_class: Vec<(u32, u32)> = triple_set.iter()
                .filter(|&&(_, p, _)| p == owl_equiv_class)
                .map(|&(s, _, o)| (s, o)).collect();
            let equiv_prop: Vec<(u32, u32)> = triple_set.iter()
                .filter(|&&(_, p, _)| p == owl_equiv_prop)
                .map(|&(s, _, o)| (s, o)).collect();

            // OWL restriction structures and RDF lists (owl-rl-ext only).
            let mut restr_prop: HashMap<u32, u32> = HashMap::new();
            let mut restr_svf: HashMap<u32, u32> = HashMap::new();
            let mut restr_hv: HashMap<u32, u32> = HashMap::new();
            let mut intersection_classes: Vec<(u32, u32, Vec<Fact>, Vec<u32>)> = Vec::new();
            let mut union_classes: Vec<(u32, u32, Vec<Fact>, Vec<u32>)> = Vec::new();
            let mut oneof_classes: Vec<(u32, u32, Vec<Fact>, Vec<u32>)> = Vec::new();
            let mut svf_rules: Vec<(u32, u32, u32)> = Vec::new();
            let mut hv_rules: Vec<(u32, u32, u32)> = Vec::new();
            let mut avf_rules: Vec<(u32, u32, u32)> = Vec::new();
            if include_ext {
                let mut restr_avf: HashMap<u32, u32> = HashMap::new();
                for &(s, p, o) in triple_set.iter() {
                    if p == owl_on_property { restr_prop.insert(s, o); }
                    if p == owl_some_values { restr_svf.insert(s, o); }
                    if p == owl_all_values { restr_avf.insert(s, o); }
                    if p == owl_has_value { restr_hv.insert(s, o); }
                }
                avf_rules = restr_avf.iter()
                    .filter_map(|(&r, &filler)| restr_prop.get(&r).map(|&prop| (prop, filler, r)))
                    .collect();
                svf_rules = restr_svf.iter()
                    .filter_map(|(&r, &filler)| restr_prop.get(&r).map(|&prop| (prop, filler, r)))
                    .collect();
                hv_rules = restr_hv.iter()
                    .filter_map(|(&r, &val)| restr_prop.get(&r).map(|&prop| (prop, val, r)))
                    .collect();

                // A list is read only when it is well formed: every node carries
                // the rdf:first and rdf:rest the certificate checker will look
                // for, and the chain reaches rdf:nil. It used to be read
                // leniently and the class rules fired on whatever came back. The
                // checker has no rule for a list it cannot walk, so the reasoner
                // no longer derives from one either; deriving less from
                // malformed input is the sound direction. Each entry keeps the
                // head node and the chain triples so a certificate can cite them.
                let first_map: HashMap<u32, u32> = triple_set.iter()
                    .filter(|&&(_, p, _)| p == rdf_first)
                    .map(|&(s, _, o)| (s, o)).collect();
                let rest_map: HashMap<u32, u32> = triple_set.iter()
                    .filter(|&&(_, p, _)| p == rdf_rest)
                    .map(|&(s, _, o)| (s, o)).collect();
                let walk_list = |head: u32| -> Option<(Vec<Fact>, Vec<u32>)> {
                    let mut chain = Vec::new();
                    let mut items = Vec::new();
                    let mut cur = head;
                    // Bounded so that a cyclic rdf:rest cannot spin.
                    for _ in 0..100_000 {
                        if cur == rdf_nil {
                            return Some((chain, items));
                        }
                        let item = *first_map.get(&cur)?;
                        let next = *rest_map.get(&cur)?;
                        chain.push((cur, rdf_first, item));
                        chain.push((cur, rdf_rest, next));
                        items.push(item);
                        cur = next;
                    }
                    None
                };
                for &(s, p, o) in triple_set.iter() {
                    if p == owl_intersection
                        && let Some((chain, items)) = walk_list(o)
                        && !items.is_empty()
                    {
                        intersection_classes.push((s, o, chain, items));
                    }
                    if p == owl_union
                        && let Some((chain, items)) = walk_list(o)
                        && !items.is_empty()
                    {
                        union_classes.push((s, o, chain, items));
                    }
                    if p == owl_oneof
                        && let Some((chain, items)) = walk_list(o)
                        && !items.is_empty()
                    {
                        oneof_classes.push((s, o, chain, items));
                    }
                }
            }

            // Build per-iteration indices
            let type_idx: Vec<(u32, u32)> = triple_set.iter()
                .filter(|&&(_, p, _)| p == rdf_type)
                .map(|&(s, _, o)| (s, o)).collect();
            let subclass_idx: Vec<(u32, u32)> = triple_set.iter()
                .filter(|&&(_, p, _)| p == rdfs_subclass)
                .map(|&(s, _, o)| (s, o)).collect();
            let subprop_idx: Vec<(u32, u32)> = triple_set.iter()
                .filter(|&&(_, p, _)| p == rdfs_subprop)
                .map(|&(s, _, o)| (s, o)).collect();

            // Build a subclass lookup: sub → [super]
            let mut sub_to_super: HashMap<u32, Vec<u32>> = HashMap::new();
            for &(sub, sup) in &subclass_idx {
                sub_to_super.entry(sub).or_default().push(sup);
            }

            // Every rule goes through this. It pushes the candidate and, when a
            // certificate was asked for, records the first derivation of each
            // triple not already in the closure, with the premises in the
            // order the checker expects for that rule.
            //
            // THE ORDER IS NOT THE CALL SITE'S. A fixed-arity rule fires as
            // `Fired::Bound(rule, binding)`, and the conclusion and the premise
            // list are both computed from that rule's row in `BUILTIN_RULES`,
            // which is the table `tests/premise_order_test.rs` checks against
            // the `checkStep` arms in `lean/OOCert/Rules.lean`. A site that got
            // the order wrong used to produce a certificate the checker
            // rejected for a reason no user could act on; there is now no order
            // at a site to get wrong. The four list rules keep an explicit
            // premise vector, because an RDF list chain is not a fixed pattern,
            // and they say so where they fire.
            //
            // It is also the one place that refuses a conclusion no RDF
            // serialiser can write. Four rules below guard the subject position
            // themselves and are left alone; this guard is central because the
            // per-rule approach is what left the PREDICATE position open, and a
            // rule added later gets the guard without its author remembering.
            // Deriving less is the sound direction, and the count is reported
            // rather than swallowed.
            let interner_ref = &interner;
            let refused_ref = &mut refused;
            let samples_ref = &mut skipped_samples;
            let mut cap_ref = capture.as_mut();
            let rv = &rule_vocab;
            let mut emit = |f: Fired| {
                let (rule, t) = match &f {
                    Fired::Bound(r, b) => {
                        let row = &BUILTIN_RULES[*r as usize];
                        // A real assert and not a `debug_assert`. The cost is
                        // one comparison beside two interner lookups the next
                        // lines already do, and the alternative in a release
                        // build is an index panic inside `fill` with nothing
                        // naming the rule.
                        assert_eq!(
                            row.vars.len(),
                            b.len(),
                            "{} takes a binding of {} terms",
                            row.name,
                            row.vars.len()
                        );
                        (row.name, rv.fill(&row.head, b))
                    }
                    Fired::Chained(name, t, _) => (*name, *t),
                };
                let (s, p, _) = t;
                if !writable_triple(interner_ref.resolve(s), interner_ref.resolve(p)) {
                    if refused_ref.insert(t) && samples_ref.len() < 3 {
                        samples_ref.push(format!(
                            "{} {} {} (by {rule})",
                            interner_ref.resolve(t.0),
                            interner_ref.resolve(t.1),
                            interner_ref.resolve(t.2)
                        ));
                    }
                    return;
                }
                // Computed ONCE, because two consumers need it and they need
                // the same value: the certificate records the first derivation
                // of a triple, and the DAG records every one. Deriving it twice
                // would let them disagree. Skipped entirely when neither asked,
                // so a run that wants no certificate and no DAG pays one branch.
                let premises: Vec<Fact> = if certify || cap_ref.is_some() {
                    match &f {
                        Fired::Bound(r, b) => BUILTIN_RULES[*r as usize]
                            .body
                            .iter()
                            .map(|a| rv.fill(a, b))
                            .collect(),
                        Fired::Chained(_, _, ps) => ps.to_vec(),
                    }
                } else {
                    Vec::new()
                };
                if certify && !triple_set.contains(&t) && recorded.insert(t) {
                    derivations.push(Derivation { rule, conclusion: t, premises: premises.clone() });
                }
                // The DAG, when one was asked for. Recorded whether or not the
                // conclusion is new, because the SECOND way a triple can be
                // derived is the whole point: it is a second justification and
                // a second monomial, and a log that keeps only firsts cannot
                // see either.
                if let Some(cap) = cap_ref.as_mut() {
                    let key = (rule, t, premises.clone());
                    if cap.seen.insert(key.clone()) {
                        cap.instances.push(key);
                    }
                }
                new.push(t);
            };

            // ── RDFS rules ──────────────────────────────────────────

            // rdfs9: x type sub, sub subClassOf super → x type super
            for &(x, sub) in &type_idx {
                if let Some(supers) = sub_to_super.get(&sub) {
                    for &sup in supers {
                        if sub != sup {
                            emit(Fired::Bound(Rl::Rdfs9, &[x, sub, sup]));
                        }
                    }
                }
            }

            // rdfs11: a subClassOf b, b subClassOf c → a subClassOf c
            for &(a, b) in &subclass_idx {
                if let Some(cs) = sub_to_super.get(&b) {
                    for &c in cs {
                        if a != b && b != c && a != c {
                            emit(Fired::Bound(Rl::Rdfs11, &[a, b, c]));
                        }
                    }
                }
            }

            // rdfs2: s p o, p domain class → s type class
            for &(prop, cls) in &domain_map {
                for &(s, p, o) in triple_set.iter() {
                    if p == prop {
                        emit(Fired::Bound(Rl::Rdfs2, &[s, p, o, cls]));
                    }
                }
            }

            // rdfs3: s p o, p range class → o type class (IRI only)
            for &(prop, cls) in &range_map {
                for &(s, p, o) in triple_set.iter() {
                    // The guard has to exclude LITERALS, which cannot be the
                    // subject of the conclusion, and nothing else. Requiring an
                    // IRI also dropped every range inference onto a blank node,
                    // so a blank-node value never got typed, rdfs9 starved
                    // behind it, and a SHACL shape targeting that class found
                    // no focus nodes. rdfs2 twelve lines up has no such guard.
                    if p == prop && !interner.resolve(o).starts_with('"') {
                        emit(Fired::Bound(Rl::Rdfs3, &[s, p, o, cls]));
                    }
                }
            }

            // rdfs5: subproperty transitivity
            let mut subp_to_super: HashMap<u32, Vec<u32>> = HashMap::new();
            for &(sub, sup) in &subprop_idx {
                subp_to_super.entry(sub).or_default().push(sup);
            }
            for &(a, b) in &subprop_idx {
                if let Some(cs) = subp_to_super.get(&b) {
                    for &c in cs {
                        if a != b && b != c && a != c {
                            emit(Fired::Bound(Rl::Rdfs5, &[a, b, c]));
                        }
                    }
                }
            }

            // rdfs7: s sub o, sub subPropertyOf super → s super o
            for &(sub, sup) in &subprop_idx {
                if sub != sup {
                    for &(s, p, o) in triple_set.iter() {
                        if p == sub {
                            emit(Fired::Bound(Rl::Rdfs7, &[s, sub, o, sup]));
                        }
                    }
                }
            }

            // Four rules below conclude a triple whose SUBJECT comes from an
            // object position, so a literal object would produce a triple no
            // RDF serialisation can express. The materialiser then failed on
            // the whole batch with "The subject of a triple must be an IRI or a
            // blank node", at a line number that moved between runs because it
            // depends on hash iteration order, and every inference from that
            // run was lost. OWL 2 RL scopes prp-symp, prp-inv1, prp-inv2 and
            // eq-sym to what can legally appear as a subject; this is that
            // scope, made explicit. Pinned by `tests/reason_literal_subject_test.rs`.
            let is_literal = |id: u32| interner.resolve(id).starts_with('"');

            // ── OWL-RL rules ────────────────────────────────────────
            if include_owl {
                // prp-trp: x P y, y P z → x P z
                for &tp in &transitive_set {
                    let pairs: Vec<(u32, u32)> = triple_set.iter()
                        .filter(|&&(_, p, _)| p == tp)
                        .map(|&(s, _, o)| (s, o)).collect();
                    let mut by_subj: HashMap<u32, Vec<u32>> = HashMap::new();
                    for &(s, o) in &pairs {
                        by_subj.entry(s).or_default().push(o);
                    }
                    for &(x, y) in &pairs {
                        if let Some(zs) = by_subj.get(&y) {
                            for &z in zs {
                                if x != z {
                                    emit(Fired::Bound(Rl::PrpTrp, &[tp, x, y, z]));
                                }
                            }
                        }
                    }
                }

                // prp-symp: s P o → o P s
                for &sp in &symmetric_set {
                    for &(s, p, o) in triple_set.iter() {
                        if p == sp && !is_literal(o) {
                            emit(Fired::Bound(Rl::PrpSymp, &[sp, s, o]));
                        }
                    }
                }

                // prp-inv1, prp-inv2: s P o, P inverseOf Q → o Q s (both directions)
                for &(p, q) in &inverse_pairs {
                    for &(s, pred, o) in triple_set.iter() {
                        if is_literal(o) {
                            continue;
                        }
                        if pred == p {
                            emit(Fired::Bound(Rl::PrpInv1, &[p, q, s, o]));
                        }
                        if pred == q {
                            emit(Fired::Bound(Rl::PrpInv2, &[p, q, s, o]));
                        }
                    }
                }

                // eq-sym: sameAs symmetry
                for &(s, p, o) in triple_set.iter() {
                    if p == owl_sameas && !is_literal(o) {
                        emit(Fired::Bound(Rl::EqSym, &[s, o]));
                    }
                }

                // scm-eqc1, scm-eqc2: equivalentClass → bidirectional subClassOf
                // Both conclusions are W3C scm-eqc1, which licenses two of them
                // from one premise. The second used to be emitted as "scm-eqc2",
                // which is a DIFFERENT W3C rule: it concludes owl:equivalentClass
                // from two subClassOf triples, the opposite direction. An auditor
                // reading that id and looking it up found the wrong rule, which
                // is precisely what the cls-hv1 comment below forbids. Emitting
                // both steps under the rule that licenses them also frees the
                // name for the real scm-eqc2 when it is implemented.
                for &(a, b) in &equiv_class {
                    emit(Fired::Bound(Rl::ScmEqc1Fwd, &[a, b]));
                    emit(Fired::Bound(Rl::ScmEqc1Rev, &[a, b]));
                }

                // scm-eqp1, scm-eqp2: equivalentProperty → bidirectional subPropertyOf
                // Same for scm-eqp1 and the name scm-eqp2.
                for &(a, b) in &equiv_prop {
                    emit(Fired::Bound(Rl::ScmEqp1Fwd, &[a, b]));
                    emit(Fired::Bound(Rl::ScmEqp1Rev, &[a, b]));
                }

                // scm-dom1, scm-dom2, scm-rng1, scm-rng2: a declared domain or
                // range moved along the class and the property hierarchy.
                //
                // These four add no ANSWERS. Everything they license at the
                // instance level is already reachable: rdfs2 over the original
                // domain gives `s rdf:type c1` and rdfs9 carries it up to `c2`,
                // which is what scm-dom1 followed by rdfs2 gives, and scm-dom2
                // is rdfs7 up to the superproperty followed by rdfs2. What they
                // add is the SCHEMA those answers are consequences of. A
                // consumer reading the materialised graph for "what is the
                // domain of this property" saw the declaration and not its
                // consequences, and a second reasoner run over the output
                // derived them, so the output was not a fixpoint of the
                // profile.
                //
                // They also fire on schema alone, so unlike almost everything
                // else in the extended profile they fire on a schema-only file
                // with no instances at all, which is most of this repository's
                // corpus.

                // scm-dom1: p rdfs:domain c1, c1 subClassOf c2 → p rdfs:domain c2
                for &(p, c1) in &domain_map {
                    if let Some(supers) = sub_to_super.get(&c1) {
                        for &c2 in supers {
                            if c1 != c2 {
                                emit(Fired::Bound(Rl::ScmDom1, &[p, c1, c2]));
                            }
                        }
                    }
                }

                // scm-dom2: p2 rdfs:domain c, p1 subPropertyOf p2 → p1 rdfs:domain c
                for &(p1, p2) in &subprop_idx {
                    if p1 == p2 {
                        continue;
                    }
                    for &(pd, c) in &domain_map {
                        if pd == p2 {
                            emit(Fired::Bound(Rl::ScmDom2, &[p2, c, p1]));
                        }
                    }
                }

                // scm-rng1: p rdfs:range c1, c1 subClassOf c2 → p rdfs:range c2
                for &(p, c1) in &range_map {
                    if let Some(supers) = sub_to_super.get(&c1) {
                        for &c2 in supers {
                            if c1 != c2 {
                                emit(Fired::Bound(Rl::ScmRng1, &[p, c1, c2]));
                            }
                        }
                    }
                }

                // scm-rng2: p2 rdfs:range c, p1 subPropertyOf p2 → p1 rdfs:range c
                for &(p1, p2) in &subprop_idx {
                    if p1 == p2 {
                        continue;
                    }
                    for &(pr, c) in &range_map {
                        if pr == p2 {
                            emit(Fired::Bound(Rl::ScmRng2, &[p2, c, p1]));
                        }
                    }
                }
            }

            // ── OWL-RL extended (someValuesFrom, hasValue, intersection, union)
            if include_ext {
                // Build type lookup: instance → set of classes
                let mut inst_types: HashMap<u32, HashSet<u32>> = HashMap::new();
                for &(x, cls) in &type_idx {
                    inst_types.entry(x).or_default().insert(cls);
                }

                // cls-svf1: x P y, y type filler, restriction(P, svf=filler)
                //           → x type restriction
                //
                // Two derivations this rule used to make are gone, both found
                // when every rule had to correspond to one the Lean checker
                // can prove sound (tests/reason_rl_ext_soundness_test.rs):
                //   * `x type C` for every `C rdfs:subClassOf restriction`.
                //     That is the converse of the axiom. Membership in a
                //     superclass never gives membership in a subclass; the
                //     equivalentClass case that made it look right is carried
                //     by rdfs9 over the subClassOf triple scm-eqc emits.
                //   * `x type restriction` from `x P filler`, where the
                //     object is the filler class IRI itself. A class in
                //     object position is a resource, not an instance of
                //     itself.
                for &(prop, filler, restr) in &svf_rules {
                    let prop_pairs: Vec<(u32, u32)> = triple_set.iter()
                        .filter(|&&(_, p, _)| p == prop)
                        .map(|&(s, _, o)| (s, o)).collect();

                    let filler_insts: HashSet<u32> = type_idx.iter()
                        .filter(|&&(_, cls)| cls == filler)
                        .map(|&(inst, _)| inst).collect();

                    for &(x, y) in &prop_pairs {
                        if filler_insts.contains(&y) {
                            emit(Fired::Bound(Rl::ClsSvf1, &[restr, prop, filler, x, y]));
                        }
                    }
                }

                // cls-avf: x type restriction(P, allValuesFrom c), x P y
                //          → y type c
                //
                // The restriction was parsed and the parse was thrown away, so
                // 123 owl:allValuesFrom axioms across six shipped files licensed
                // nothing. It is the cheapest missing rule in the OWL 2 RL
                // profile on both axes: the Rust is the cls-svf1 loop with the
                // premises the other way round, and the semantic condition is
                // the mirror of `svf`.
                for &(prop, filler, restr) in &avf_rules {
                    let in_restr: HashSet<u32> = type_idx.iter()
                        .filter(|&&(_, cls)| cls == restr)
                        .map(|&(inst, _)| inst).collect();
                    if in_restr.is_empty() {
                        continue;
                    }
                    for &(x, p, y) in triple_set.iter() {
                        if p == prop && in_restr.contains(&x) {
                            emit(Fired::Bound(Rl::ClsAvf, &[restr, prop, filler, x, y]));
                        }
                    }
                }

                // cls-hv1: x type restriction(P, hasValue v) → x P v
                // cls-hv2: x P v, restriction(P, hasValue v) → x type restriction
                //
                // The rule emitted under the name `cls-hv1` used to be the
                // composite of `cax-sco` and W3C `cls-hv1`: it demanded an
                // explicit `k rdfs:subClassOf r` hop and fired on `x type k`,
                // so an individual typed with the restriction DIRECTLY derived
                // nothing. The engine reached the restriction class by its own
                // rdfs9 and then refused to use it, and a certificate could
                // carry `rdfs9  <k> rdf:type <R>` right next to a cls-hv1 step
                // that ignored it. Putting a W3C rule name in front of an
                // auditor obliges the rule to be that rule. The W3C form is
                // used here and loses nothing: the composite case is rdfs9
                // followed by this.
                for &(prop, val, restr) in &hv_rules {
                    for &(x, c) in &type_idx {
                        if c == restr {
                            emit(Fired::Bound(Rl::ClsHv1, &[restr, prop, val, x]));
                        }
                    }
                    for &(s, p, o) in triple_set.iter() {
                        if p == prop && o == val {
                            emit(Fired::Bound(Rl::ClsHv2, &[restr, prop, val, s]));
                        }
                    }
                }

                // scm-svf1, scm-svf2, scm-avf1, scm-avf2: two restrictions
                // ordered by their fillers or by their properties.
                //
                // These are the rules that reach subsumptions no instance-level
                // rule can. `cls-svf1` needs an individual with a witness before
                // it says anything, and a schema-only ontology has none, so a
                // pizza-style file full of restrictions licensed nothing at all
                // from them. These four run on the schema.
                //
                // Two indices per restriction kind: (property, filler) → the
                // restrictions with both, and property → its (filler,
                // restriction) pairs. The first is the lookup and the second is
                // the scan, which keeps each rule linear in the hierarchy it
                // walks rather than quadratic in the restriction count.
                let mut svf_by_pf: HashMap<(u32, u32), Vec<u32>> = HashMap::new();
                let mut svf_by_filler: HashMap<u32, Vec<(u32, u32)>> = HashMap::new();
                let mut svf_by_prop: HashMap<u32, Vec<(u32, u32)>> = HashMap::new();
                for &(prop, filler, restr) in &svf_rules {
                    svf_by_pf.entry((prop, filler)).or_default().push(restr);
                    svf_by_filler.entry(filler).or_default().push((prop, restr));
                    svf_by_prop.entry(prop).or_default().push((filler, restr));
                }
                let mut avf_by_pf: HashMap<(u32, u32), Vec<u32>> = HashMap::new();
                let mut avf_by_filler: HashMap<u32, Vec<(u32, u32)>> = HashMap::new();
                let mut avf_by_prop: HashMap<u32, Vec<(u32, u32)>> = HashMap::new();
                for &(prop, filler, restr) in &avf_rules {
                    avf_by_pf.entry((prop, filler)).or_default().push(restr);
                    avf_by_filler.entry(filler).or_default().push((prop, restr));
                    avf_by_prop.entry(prop).or_default().push((filler, restr));
                }

                // scm-svf1: c1 svf y1, c1 onProperty p, c2 svf y2,
                //           c2 onProperty p, y1 subClassOf y2 → c1 subClassOf c2
                for &(y1, y2) in &subclass_idx {
                    let Some(ones) = svf_by_filler.get(&y1) else { continue };
                    for &(p, r1) in ones {
                        let Some(twos) = svf_by_pf.get(&(p, y2)) else { continue };
                        for &r2 in twos {
                            if r1 != r2 {
                                emit(Fired::Bound(Rl::ScmSvf1, &[r1, y1, p, r2, y2]));
                            }
                        }
                    }
                }

                // scm-svf2: c1 svf y, c1 onProperty p1, c2 svf y,
                //           c2 onProperty p2, p1 subPropertyOf p2 → c1 subClassOf c2
                for &(p1, p2) in &subprop_idx {
                    let Some(ones) = svf_by_prop.get(&p1) else { continue };
                    for &(y, r1) in ones {
                        let Some(twos) = svf_by_pf.get(&(p2, y)) else { continue };
                        for &r2 in twos {
                            if r1 != r2 {
                                emit(Fired::Bound(Rl::ScmSvf2, &[r1, y, p1, r2, p2]));
                            }
                        }
                    }
                }

                // scm-avf1: the same shape with owl:allValuesFrom, and the same
                // direction: a wider filler makes a wider class.
                for &(y1, y2) in &subclass_idx {
                    let Some(ones) = avf_by_filler.get(&y1) else { continue };
                    for &(p, r1) in ones {
                        let Some(twos) = avf_by_pf.get(&(p, y2)) else { continue };
                        for &r2 in twos {
                            if r1 != r2 {
                                emit(Fired::Bound(Rl::ScmAvf1, &[r1, y1, p, r2, y2]));
                            }
                        }
                    }
                }

                // scm-avf2: c1 avf y, c1 onProperty p1, c2 avf y,
                //           c2 onProperty p2, p1 subPropertyOf p2
                //           → c2 subClassOf c1
                //
                // THE CONCLUSION IS THE OTHER WAY ROUND. The W3C table reads
                // `T(?c2, rdfs:subClassOf, ?c1)` where scm-svf2 reads
                // `T(?c1, rdfs:subClassOf, ?c2)`, because a universal
                // restriction is antitone in its property: `all p2 y` has more
                // values to constrain than `all p1 y`, so it is the smaller
                // class. Writing it the way scm-svf2 is written gives a step no
                // model supports, and `OOCert.the_natural_avf2_direction_is_not_entailed`
                // is the refutation.
                for &(p1, p2) in &subprop_idx {
                    let Some(ones) = avf_by_prop.get(&p1) else { continue };
                    for &(y, r1) in ones {
                        let Some(twos) = avf_by_pf.get(&(p2, y)) else { continue };
                        for &r2 in twos {
                            if r1 != r2 {
                                emit(Fired::Bound(Rl::ScmAvf2, &[r1, y, p1, r2, p2]));
                            }
                        }
                    }
                }

                // cls-int1: x type ALL members → x type intersection class
                for (cls, head, chain, members) in &intersection_classes {
                    for (&x, x_types) in &inst_types {
                        if members.iter().all(|m| x_types.contains(m)) {
                            let premises: Vec<Fact> = if certify {
                                let mut v = vec![(*cls, owl_intersection, *head)];
                                v.extend(chain.iter().copied());
                                v.extend(members.iter().map(|&m| (x, rdf_type, m)));
                                v
                            } else {
                                Vec::new()
                            };
                            emit(Fired::Chained("cls-int1", (x, rdf_type, *cls), &premises));
                        }
                    }
                }

                // cls-int2: x type intersection class → x type EVERY member
                //
                // The mirror of cls-int1, and the only high-count rule in the
                // measured gap that produces genuinely new instance typings
                // rather than schema. One step per member, each repeating the
                // constructor triple and the chain, because a certificate step
                // carries one conclusion.
                for (cls, head, chain, members) in &intersection_classes {
                    for &(x, c) in &type_idx {
                        if c != *cls {
                            continue;
                        }
                        let premises: Vec<Fact> = if certify {
                            let mut v = vec![(*cls, owl_intersection, *head)];
                            v.extend(chain.iter().copied());
                            v.push((x, rdf_type, *cls));
                            v
                        } else {
                            Vec::new()
                        };
                        for &m in members {
                            emit(Fired::Chained("cls-int2", (x, rdf_type, m), &premises));
                        }
                    }
                }

                // cls-oo: every member of an owl:oneOf list is an instance of
                // the enumerated class. The only rule here with no instance
                // premise at all: an enumeration types its members on schema
                // alone. A literal member is skipped for the same reason the
                // four rules above skip one, since it would be the subject of
                // the conclusion.
                for (cls, head, chain, members) in &oneof_classes {
                    let premises: Vec<Fact> = if certify {
                        let mut v = vec![(*cls, owl_oneof, *head)];
                        v.extend(chain.iter().copied());
                        v
                    } else {
                        Vec::new()
                    };
                    for &m in members {
                        if !is_literal(m) {
                            emit(Fired::Chained("cls-oo", (m, rdf_type, *cls), &premises));
                        }
                    }
                }

                // cls-uni: x type ANY member → x type union class
                for (cls, head, chain, members) in &union_classes {
                    for &(x, c) in &type_idx {
                        if members.contains(&c) {
                            let premises: Vec<Fact> = if certify {
                                let mut v = vec![(*cls, owl_union, *head)];
                                v.extend(chain.iter().copied());
                                v.push((x, rdf_type, c));
                                v
                            } else {
                                Vec::new()
                            };
                            emit(Fired::Chained("cls-uni", (x, rdf_type, *cls), &premises));
                        }
                    }
                }
            }

            // Insert new triples (dedup against existing)
            for t in new {
                triple_set.insert(t);
            }

            if triple_set.len() == before {
                fixpoint_reached = true;
                break;
            }
            if iterations >= crate::runtime::reasoner_max_iterations() {
                break;
            }
        }

        let inferred_count = triple_set.len() - initial_size;

        // Materialize inferred triples
        if materialize && inferred_count > 0 {
            let original: HashSet<Fact> = facts.iter().copied().collect();
            let mut lines = String::new();
            for &(s, p, o) in &triple_set {
                if !original.contains(&(s, p, o)) {
                    lines.push_str(interner.resolve(s));
                    lines.push(' ');
                    lines.push_str(interner.resolve(p));
                    lines.push(' ');
                    lines.push_str(interner.resolve(o));
                    if target == InferenceTarget::Inferred {
                        lines.push_str(" <");
                        lines.push_str(INFERRED_GRAPH);
                        lines.push('>');
                    }
                    lines.push_str(" .\n");
                }
            }
            match target {
                InferenceTarget::DefaultGraph => graph.load_ntriples(&lines)?,
                InferenceTarget::Inferred => graph.load_nquads(&lines)?,
            };
        }

        // Sample
        let original: HashSet<Fact> = facts.iter().copied().collect();
        let sample: Vec<String> = triple_set.iter()
            .filter(|t| !original.contains(t))
            .filter(|&&(_, p, _)| p == rdf_type)
            .take(10)
            .map(|&(s, _, o)| format!("{} a {}", interner.resolve(s), interner.resolve(o)))
            .collect();

        let mut result = serde_json::json!({
            "profile_used": profile_used,
            "inferred_count": inferred_count,
            "iterations": iterations,
            "fixpoint_reached": fixpoint_reached,
            "initial_triples": initial_size,
            "final_triples": triple_set.len(),
            "sample_inferences": sample,
            // Which graphs this closure was computed over. Present on every
            // run, scoped or not: a number with no units is what an unlabelled
            // verdict is, and the run where the scope first matters must not
            // be the run where the key first appears.
            "scope": manifest.to_json(),
        });
        if let Some(w) = &manifest.warning {
            result["warning"] = serde_json::json!(w);
        }
        if manifest.graphs.as_ref().is_some_and(Vec::is_empty) {
            // The default graph alone: the schema, and whatever else sits
            // outside a named graph. A closure over that is a real answer to a
            // question about the TBox and is NOT an answer about the data,
            // and an `inferred_count` with nothing saying so reads as one.
            result["warning"] = serde_json::json!(
                "no graphs in scope at that instant: this closure was computed over the default \
                 graph alone, so it says nothing about the assertions. See scope."
            );
        }
        if !materialize {
            result["dry_run"] = serde_json::json!(true);
        }
        if target == InferenceTarget::Inferred {
            // A caller cannot ask the inferences back unless it is told where
            // they were put.
            result["inference_graph"] = serde_json::json!(INFERRED_GRAPH);
        }
        if !refused.is_empty() {
            // Said out loud, because this run derived LESS than its rule set
            // licenses and a reader comparing two runs' counts is entitled to
            // know why.
            result["skipped_unserialisable"] = serde_json::json!(refused.len());
            result["skipped_examples"] = serde_json::json!(skipped_samples);
            result["skipped_reason"] = serde_json::json!(
                "the rule concluded a triple no RDF serialiser can write (a literal in subject \
                 position, or a non-IRI in predicate position). Such conclusions are neither \
                 materialised nor certified nor used as premises. Before this was guarded the \
                 materialiser failed partway through inserting the batch, which left the store \
                 holding an arbitrary, run-dependent prefix of the inferences with no certificate \
                 covering any of them"
            );
        }

        if let Some(dir) = certificate_dir {
            std::fs::create_dir_all(dir)?;
            let mut asserted: Vec<u8> = Vec::with_capacity(facts.len() * 96);
            for &(s, p, o) in &facts {
                push_asserted_line(
                    &mut asserted,
                    interner.resolve(s),
                    interner.resolve(p),
                    interner.resolve(o),
                )
                .map_err(|pos| unwritable_term("asserted.tsv", pos, interner.resolve(match pos {
                    Position::Subject => s,
                    Position::Predicate => p,
                    Position::Object => o,
                })))?;
            }
            // Issue #158. The digest of exactly these bytes, beside them, so a
            // reader who holds a store can ask whether this certificate is
            // about it. `asserted_digest` rebuilds the same bytes from a store
            // through `asserted_bytes`, which is the function this loop is the
            // inlined form of; the test pins that the two agree.
            let asserted_sha256 = {
                use sha2::{Digest, Sha256};
                let mut h = Sha256::new();
                h.update(&asserted);
                format!("{:x}", h.finalize())
            };
            std::fs::write(dir.join("asserted.tsv"), asserted)?;
            std::fs::write(dir.join("asserted.sha256"), format!("{asserted_sha256}\n"))?;

            let mut by_rule: std::collections::BTreeMap<&str, usize> = std::collections::BTreeMap::new();
            let mut lines: Vec<u8> = Vec::with_capacity(derivations.len() * 256);
            for d in &derivations {
                *by_rule.entry(d.rule).or_default() += 1;
                lines.extend_from_slice(d.rule.as_bytes());
                for &(s, p, o) in std::iter::once(&d.conclusion).chain(d.premises.iter()) {
                    push_triple_fields(
                        &mut lines,
                        interner.resolve(s),
                        interner.resolve(p),
                        interner.resolve(o),
                    )
                    .map_err(|pos| unwritable_term("derivations.tsv", pos, interner.resolve(match pos {
                        Position::Subject => s,
                        Position::Predicate => p,
                        Position::Object => o,
                    })))?;
                }
                lines.push(b'\n');
            }
            std::fs::write(dir.join("derivations.tsv"), lines)?;

            // A refutation left behind by an earlier run into this directory
            // would be checked against THIS run's asserted.tsv, which is a
            // different graph. It would almost certainly be rejected, and
            // "almost certainly" is not the standard here: the stale file goes
            // before the clash detector below decides whether to write a new
            // one. Ignoring the error is correct; the usual case is that there
            // is no such file.
            let _ = std::fs::remove_file(dir.join("refutation.tsv"));

            // The scope, beside the files it selected. `asserted.tsv` is a
            // list of triples with nothing in it that says where they came
            // from, and the Lean checker has no way to ask: it verifies that
            // the derivations follow from the triples in front of it, which
            // stays true whatever scope chose them. A certificate over a
            // snapshot and a certificate over the union of every version are
            // indistinguishable as files, and only one of them is about a
            // state that existed. This file is what tells them apart.
            std::fs::write(dir.join("scope.tsv"), manifest.to_tsv())?;

            result["certificate"] = serde_json::json!({
                "dir": dir.display().to_string(),
                "format": "oo-cert/1",
                "asserted": facts.len(),
                "derivations": derivations.len(),
                "by_rule": by_rule,
                // Which graphs the assertions came from, and which were held
                // back. A certificate that does not say this cannot be checked
                // against the store it claims to be about.
                "graphs_read": graphs_read,
                "graphs_excluded": [INFERRED_GRAPH],
                "check_with": "cd lean && lake exe oo-cert <dir>/asserted.tsv <dir>/derivations.tsv",
                "asserted_sha256": asserted_sha256,
                "asserted_sha256_means": "the digest of asserted.tsv, written beside it as \
                                          asserted.sha256. A holder of a store recomputes it \
                                          with `certificate-check <dir>` and learns whether \
                                          this certificate is about that store (issue #158). \
                                          It binds the certificate to a selection of BYTES, \
                                          not to a state of the world",
                "scope": manifest.to_json(),
                "scope_file": dir.join("scope.tsv").display().to_string(),
                "scope_means": "oo-cert verifies that every derivation follows from the triples \
                                in asserted.tsv. It does not and cannot check that asserted.tsv \
                                is the graph you meant to reason over. scope.tsv records which \
                                graphs were read; a reader who cares whether this answer is \
                                about a state that existed has to read it.",
            });
        }

        // ── Inconsistency ───────────────────────────────────────────────────
        //
        // The clash rules, looked for over the closure the fixpoint reached.
        // The key appears only when something was found, so a run over a graph
        // with no clash is byte for byte the run it always was.
        let clashes = find_clashes(&triple_set, &interner, &clash_vocab);
        if !clashes.is_empty() {
            let show = |t: &Fact| {
                serde_json::json!([
                    interner.resolve(t.0),
                    interner.resolve(t.1),
                    interner.resolve(t.2)
                ])
            };
            let mut by_rule: std::collections::BTreeMap<&str, usize> =
                std::collections::BTreeMap::new();
            for c in &clashes {
                *by_rule.entry(c.rule).or_default() += 1;
            }
            let listed: Vec<serde_json::Value> = clashes
                .iter()
                .take(10)
                .map(|c| {
                    serde_json::json!({
                        "rule": c.rule,
                        "certifiable": clash_is_certifiable(c.rule),
                        "premises": c.premises.iter().map(show).collect::<Vec<_>>(),
                    })
                })
                .collect();
            let uncertifiable: Vec<&str> = by_rule
                .keys()
                .copied()
                .filter(|r| !clash_is_certifiable(r))
                .collect();
            let mut inconsistency = serde_json::json!({
                "found": true,
                // THIS ENGINE'S WORD, and deliberately not the checker's.
                // `oo-refute` says `unsatisfiable_under_disjointness` when it
                // has accepted a refutation. Nothing here may say that, or an
                // engine opinion and a machine-checked result share a string
                // and a consumer cannot tell them apart.
                //
                // The word comes from `verdict::EngineRefutation`, whose
                // vocabulary is asserted disjoint from
                // `verdict::CHECKER_OWNED_WORDS`, and which has no certified
                // variant to reach for: nothing in the Rust tree runs
                // `oo-refute`, so there is no evidence any code here could
                // mint.
                "verdict": crate::verdict::EngineRefutation::ClashFoundByThisEngine,
                "checked_by_lean": false,
                "clash_count": clashes.len(),
                "by_rule": by_rule,
                "clashes_listed": listed.len(),
                "clashes": listed,
                "certifiable_rules": CLASH_RULES_CERTIFIABLE,
                "uncertifiable_rules_found": uncertifiable,
                "rules_not_detected": CLASH_RULES_NOT_DETECTED
                    .iter()
                    .map(|(r, why)| serde_json::json!({"rule": r, "why": why}))
                    .collect::<Vec<_>>(),
                "means": "this engine found a contradiction in the closure it computed, and \
                          NOTHING HAS CHECKED THAT. A refutation the Lean checker accepted is a \
                          different kind of result with a different word for it: run `oo-refute \
                          check` and read its verdict, which is `unsatisfiable_under_disjointness` \
                          and is never stated here.",
                "limits": "cax-dw needs an INDIVIDUAL in two disjoint classes, so a TBox that is \
                           unsatisfiable with no individual asserted is invisible to this route \
                           entirely: it is a boundary of rule-based reasoning, not a bug. The SHIQ \
                           tableau in src/tableaux.rs (--profile owl-dl) does see that case, and \
                           its unsatisfiability finding carries NO certificate, which the owl-dl \
                           report states as `unsatisfiability and inconsistency carry no \
                           certificate`. Nothing found by the rules listed under \
                           rules_not_detected was looked for at all, so a clean run is not a \
                           consistency result.",
            });

            if let Some(dir) = certificate_dir {
                // A refutation file is written for the one rule the checker can
                // judge, and for nothing else. The engine's own detection of
                // any other clash rule stays a report, because a file naming a
                // rule `OOCert.RefuteConditions` has no field for is refused by
                // `oo-refute` with exit 2 and would be a certificate-shaped
                // object that certifies nothing.
                let certifiable = clashes.iter().find(|c| clash_is_certifiable(c.rule));
                match certifiable {
                    Some(c) => match refutation_prefix(&c.premises, &derivations, &original) {
                        Some(ids) => {
                            let mut text = String::from("oo-refute/1\n");
                            for &i in &ids {
                                let d = &derivations[i];
                                text.push_str(d.rule);
                                for &(s, p, o) in
                                    std::iter::once(&d.conclusion).chain(d.premises.iter())
                                {
                                    text.push('\t');
                                    text.push_str(interner.resolve(s));
                                    text.push('\t');
                                    text.push_str(interner.resolve(p));
                                    text.push('\t');
                                    text.push_str(interner.resolve(o));
                                }
                                text.push('\n');
                            }
                            text.push_str("refute\t");
                            text.push_str(c.rule);
                            for &(s, p, o) in &c.premises {
                                text.push('\t');
                                text.push_str(interner.resolve(s));
                                text.push('\t');
                                text.push_str(interner.resolve(p));
                                text.push('\t');
                                text.push_str(interner.resolve(o));
                            }
                            text.push('\n');
                            std::fs::write(dir.join("refutation.tsv"), text)?;
                            inconsistency["refutation"] = serde_json::json!({
                                "written": true,
                                "file": dir.join("refutation.tsv").display().to_string(),
                                "format": "oo-refute/1",
                                "rule": c.rule,
                                "prefix": ids.len(),
                                "premises": c.premises.iter().map(show).collect::<Vec<_>>(),
                                // Written, not checked. The word for a checked
                                // one is `oo-refute`'s to say, and this crate
                                // has no vocabulary that can say it.
                                "verdict": crate::verdict::EngineRefutation::RefutationWrittenNotYetChecked,
                                "check_with": format!(
                                    "cd lean && lake exe oo-refute check {a} {r}",
                                    a = dir.join("asserted.tsv").display(),
                                    r = dir.join("refutation.tsv").display()
                                ),
                                "guard_with": format!(
                                    "cd lean && lake exe oo-refute guard {a} {d} {r}",
                                    a = dir.join("asserted.tsv").display(),
                                    d = dir.join("derivations.tsv").display(),
                                    r = dir.join("refutation.tsv").display()
                                ),
                                "means": "a file in the format OOCert.RefuteParse.parseRefutation \
                                          reads. Exit 0 from `oo-refute check` is the result that \
                                          means anything; this engine writing the file means only \
                                          that it wrote it.",
                            });
                        }
                        None => {
                            inconsistency["refutation"] = serde_json::json!({
                                "written": false,
                                "why": "a premise of the clash is neither asserted nor recorded in \
                                        the derivation log, so no checkable prefix could be built. \
                                        That is a defect in this producer, not a property of the \
                                        ontology; please report it.",
                            });
                        }
                    },
                    None => {
                        inconsistency["refutation"] = serde_json::json!({
                            "written": false,
                            "why": "every clash found is of a rule the Lean checker has no \
                                    semantic condition for. `OOCert.RefuteConditions` carries one \
                                    field, for cax-dw, and `oo-refute` refuses a refutation naming \
                                    any other rule with exit 2 rather than judging it. Writing one \
                                    anyway would produce a certificate-shaped file that certifies \
                                    nothing.",
                        });
                    }
                }
            } else {
                inconsistency["refutation"] = serde_json::json!({
                    "written": false,
                    "why": "no certificate directory was given. Pass --certificate DIR (or \
                            certificate_dir over MCP) and a refutation is written there for the \
                            one clash rule the Lean checker can judge.",
                });
            }

            // A derivation certificate over a graph with a clash in it is worth
            // nothing under the disjointness reading, and the certificate block
            // must not be read without that.
            // `OOCert.a_certificate_adds_nothing_when_the_graph_is_refuted`.
            if let Some(cert) = result.get_mut("certificate")
                && let Some(obj) = cert.as_object_mut()
            {
                obj.insert("graph_has_a_clash".into(), serde_json::json!(true));
                obj.insert(
                    "read_with".into(),
                    serde_json::json!(
                        "this graph contradicts itself, so under the disjointness reading EVERY \
                         triple is entailed and this certificate carries no information. \
                         `oo-cert` will still accept it and will still be telling the truth, \
                         because its verdict quantifies over a model class that ignores \
                         disjointness. Run `oo-refute guard` instead of `oo-cert`."
                    ),
                );
            }

            result["inconsistency"] = inconsistency;
        }

        // The DAG, spelled out, for a caller that has no interner. Built here
        // rather than in the loop so that `clashes` and the fixpoint flag are
        // the ones the run finished with.
        if let Some(cap) = capture.as_mut() {
            let spell = |f: &Fact| {
                (
                    interner.resolve(f.0).to_string(),
                    interner.resolve(f.1).to_string(),
                    interner.resolve(f.2).to_string(),
                )
            };
            let instances: Vec<RuleInstance> = cap
                .instances
                .iter()
                .map(|(rule, c, ps)| RuleInstance {
                    rule,
                    conclusion: spell(c),
                    premises: ps.iter().map(&spell).collect(),
                })
                .collect();
            cap.out = Some(DerivationGraph {
                profile_used: profile_used.to_string(),
                asserted: facts.iter().map(&spell).collect(),
                closure: triple_set.iter().map(&spell).collect(),
                instances,
                fixpoint_reached,
                iterations,
                clashes: clashes
                    .iter()
                    .map(|c| ClashInstance {
                        rule: c.rule,
                        premises: c.premises.iter().map(&spell).collect(),
                        certifiable: clash_is_certifiable(c.rule),
                    })
                    .collect(),
                refused_unserialisable: refused.len(),
            });
        }

        Ok(result.to_string())
    }
}

// ── User-supplied Horn rules ────────────────────────────────────────────────
//
// Everything above this line applies a rule set this file hardcodes. The
// checker in `lean/OOCert/Horn.lean` accepts a certificate over ANY rule table,
// proved once by `OOCert.horn_certificate_sound`, and until now nothing could
// produce one: the generic layer had a consumer and no producer, and a user
// with a rule table had nothing to hand it.
//
// What follows reads a rule table in the `rules.tsv` format
// `OOCert.HornParse.parseRules` accepts, evaluates it to a fixpoint over the
// loaded graph, and writes a certificate in the `horn.tsv` format
// `OOCert.HornParse.parseHornSteps` accepts.
//
// # This path states no verdict, and that is deliberate
//
// A certificate over the built-in table earns `entailed`: true in every model
// of the asserted graph, because `OOCert.Builtin.asHorn_sound` discharges those
// rules against the semantics. A certificate over a table a user wrote earns
// `entailed_under_supplied_rules`: true in every model of the graph THAT ALSO
// SATISFIES THOSE RULES. The rules are assumed and never checked, so a rule
// reading "every supplier is compliant" produces steps that check green for
// ever.
//
// `oo-horn` decides which of the two a run earned, by comparing the table it
// was given against the built-in one. This engine does not repeat that
// judgement in its own output and does not print either verdict word, because a
// second place where the two could be confused is exactly the hazard decision
// 0003 exists to prevent. What the engine reports is the table it used, a
// hash of it, and the command that pronounces.

/// One position of a triple pattern: a fixed term in its N-Triples spelling, or
/// a variable. Mirrors `OOCert.Pat`.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Pat {
    Const(String),
    Var(String),
}

impl Pat {
    /// The `rules.tsv` spelling: `?x` for a variable, the term itself for a
    /// constant. Inverse of the parse below, and byte-identical to
    /// `OOCert.HornParse.patStr`.
    ///
    /// The variable arm builds the string rather than `format!`-ing it, and the
    /// reason is verification and not speed: `format!` drags the whole
    /// `core::fmt` machinery into any function that calls it, and CBMC flattens
    /// a function before it solves. With `format!` here,
    /// `kani_harnesses::pat_of_and_render_are_inverse` measures the formatter.
    /// The bytes it produces are the same either way.
    fn render(&self) -> String {
        match self {
            Pat::Const(c) => c.clone(),
            Pat::Var(v) => {
                let mut s = String::with_capacity(v.len() + 1);
                s.push('?');
                s.push_str(v);
                s
            }
        }
    }
}

/// A triple pattern. Any of the three positions may be a variable, predicate
/// position included: `Interp` has one ternary extension, so a property is a
/// domain element like any other and the language stays first-order.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct AtomPat {
    pub s: Pat,
    pub p: Pat,
    pub o: Pat,
}

/// `forall vars. body -> head`, the quantifier left implicit. Mirrors
/// `OOCert.RulePattern`.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct RulePattern {
    pub name: String,
    pub body: Vec<AtomPat>,
    pub head: AtomPat,
}

impl RulePattern {
    fn atoms(&self) -> impl Iterator<Item = &AtomPat> {
        self.body.iter().chain(std::iter::once(&self.head))
    }
}

fn pat_vars<'a>(a: &'a AtomPat, out: &mut Vec<&'a str>) {
    for p in [&a.s, &a.p, &a.o] {
        if let Pat::Var(v) = p
            && !out.contains(&v.as_str())
        {
            out.push(v.as_str());
        }
    }
}

/// Parse one field of a rule table.
///
/// A field beginning with `?` is a variable, anything else a term, which is the
/// encoding `HornParse` documents: N-Triples terms begin with `<`, `_:` or `"`,
/// so nothing is ambiguous. This is stricter than `HornParse` on exactly one
/// point, and the strictness is the "reject rather than guess" direction: a
/// constant that is not in N-Triples spelling can never equal a term the store
/// holds, so a rule carrying one silently never fires. That is a typo, not a
/// rule, and it is refused rather than run.
/// The classification half of [`parse_pat`], with no error value and no
/// formatting.
///
/// Split out on 15 September 2026 for one reason, and it is a verification
/// reason rather than a style one. `parse_pat` returns `anyhow::Result` and
/// every refusal formats a message naming the line and the position, so the
/// function body carries the whole formatting machinery; CBMC flattens a
/// function before it solves, so a Kani harness on `parse_pat` was measuring
/// `format!` and never returned a verdict (14 minutes, 9.5 GB, and worse when
/// the input was constrained). This function is pure, total and allocates only
/// the `Pat` it returns, and `kani_harnesses::pat_of_and_render_are_inverse`
/// proves TCB-20 over every byte pattern at a bound. The messages stayed where
/// they were.
fn pat_of(field: &str) -> Option<Pat> {
    if let Some(name) = field.strip_prefix('?') {
        if name.is_empty() {
            return None;
        }
        return Some(Pat::Var(name.to_string()));
    }
    if field.starts_with('<') || field.starts_with("_:") || field.starts_with('"') {
        return Some(Pat::Const(field.to_string()));
    }
    None
}

fn parse_pat(field: &str, line: usize, which: &str) -> anyhow::Result<Pat> {
    if let Some(p) = pat_of(field) {
        return Ok(p);
    }
    if field == "?" {
        anyhow::bail!("rules line {line}: {which} is '?' with no variable name");
    }
    if field.is_empty() {
        anyhow::bail!("rules line {line}: {which} is empty");
    }
    anyhow::bail!(
        "rules line {line}: {which} is '{field}', which is neither a variable (?x) nor an \
         N-Triples term (<iri>, _:blank, or a quoted literal). The store spells every term in \
         N-Triples, so a constant in any other spelling would match nothing and the rule would \
         silently never fire"
    )
}

/// Read a rule table in the `rules.tsv` format `OOCert.HornParse.parseRules`
/// accepts: `name TAB bodyLength TAB (s TAB p TAB o)* TAB hs TAB hp TAB ho`.
///
/// Malformed input is an error naming the line and what was wrong, never a
/// guess. Two rejections go beyond what the Lean parser refuses, both because
/// this side has to PRODUCE bindings rather than check them:
///
/// * A head variable that does not occur in the body. The checker is right to
///   accept a certificate over such a rule, because `SatRule` quantifies over
///   every substitution, but the engine would have to invent a term to bind it
///   to. Refusing is the only honest option.
/// * A carriage return. `HornParse` splits on `\n` alone, so a CRLF file would
///   put a `\r` inside the last term of every line. Stripping it is a guess
///   about what the user meant; the error says to convert the file.
pub fn parse_rules(content: &str) -> anyhow::Result<Vec<RulePattern>> {
    let mut out: Vec<RulePattern> = Vec::new();
    for (i, line) in content.split('\n').enumerate() {
        let n = i + 1;
        if line.is_empty() {
            continue;
        }
        if line.contains('\r') {
            anyhow::bail!(
                "rules line {n}: the line contains a carriage return. The format is tab \
                 separated with LF endings, and a CR would become part of a term; convert the \
                 file rather than have it stripped silently"
            );
        }
        let fields: Vec<&str> = line.split('\t').collect();
        if fields.len() < 2 {
            anyhow::bail!(
                "rules line {n}: expected a name, a body length and then the patterns, got \
                 {} tab-separated field(s)",
                fields.len()
            );
        }
        let name = fields[0];
        if name.is_empty() {
            anyhow::bail!("rules line {n}: the rule name is empty");
        }
        let len_field = fields[1];
        if len_field.is_empty() || !len_field.bytes().all(|b| b.is_ascii_digit()) {
            anyhow::bail!("rules line {n}: body length '{len_field}' is not a number");
        }
        let m: usize = len_field
            .parse()
            .map_err(|_| anyhow::anyhow!("rules line {n}: body length '{len_field}' is too large"))?;
        let rest = &fields[2..];
        let want = m
            .checked_mul(3)
            .and_then(|x| x.checked_add(3))
            .ok_or_else(|| anyhow::anyhow!("rules line {n}: body length '{len_field}' is too large"))?;
        if rest.len() != want {
            anyhow::bail!(
                "rules line {n}: a body of {m} atom(s) plus a head needs {want} pattern fields, \
                 got {}",
                rest.len()
            );
        }
        let mut pats: Vec<Pat> = Vec::with_capacity(want);
        for (k, f) in rest.iter().enumerate() {
            let which = if k < 3 * m {
                format!("body atom {} position {}", k / 3 + 1, k % 3 + 1)
            } else {
                format!("head position {}", k - 3 * m + 1)
            };
            pats.push(parse_pat(f, n, &which)?);
        }
        let head = AtomPat {
            o: pats.pop().expect("head object"),
            p: pats.pop().expect("head predicate"),
            s: pats.pop().expect("head subject"),
        };
        let mut body: Vec<AtomPat> = Vec::with_capacity(m);
        let mut it = pats.into_iter();
        for _ in 0..m {
            let s = it.next().expect("body subject");
            let p = it.next().expect("body predicate");
            let o = it.next().expect("body object");
            body.push(AtomPat { s, p, o });
        }
        let rule = RulePattern { name: name.to_string(), body, head };

        let mut body_vars: Vec<&str> = Vec::new();
        for a in &rule.body {
            pat_vars(a, &mut body_vars);
        }
        let mut head_vars: Vec<&str> = Vec::new();
        pat_vars(&rule.head, &mut head_vars);
        for v in head_vars {
            if !body_vars.contains(&v) {
                anyhow::bail!(
                    "rules line {n}: rule '{}' has head variable ?{v}, which does not occur in \
                     the body. The engine has nothing to bind it to, so the table is refused \
                     rather than run with a term invented for it",
                    rule.name
                );
            }
        }
        out.push(rule);
    }
    Ok(out)
}

/// Render a rule table back to `rules.tsv`. Byte-identical to
/// `OOCert.HornParse.ruleStr` per line, so `oo-horn rules` and this agree and a
/// table read here and written back out digests to the same value it came in
/// with.
pub fn rules_tsv(rules: &[RulePattern]) -> String {
    let mut out = String::new();
    for r in rules {
        out.push_str(&r.name);
        out.push('\t');
        out.push_str(&r.body.len().to_string());
        for a in r.atoms() {
            for p in [&a.s, &a.p, &a.o] {
                out.push('\t');
                out.push_str(&p.render());
            }
        }
        out.push('\n');
    }
    out
}

/// A rule pattern position over interned ids, with variables resolved to a slot
/// in the rule's environment.
enum CPat {
    Const(u32),
    Var(usize),
}

struct CAtom {
    s: CPat,
    p: CPat,
    o: CPat,
}

struct CRule {
    vars: Vec<String>,
    body: Vec<CAtom>,
    head: CAtom,
}

/// One line of a Horn certificate: the rule index, the binding the engine used,
/// the premises it matched in the rule's body order, and what it concluded.
struct HornStepOut {
    rule: usize,
    binds: Vec<(String, u32)>,
    premises: Vec<Fact>,
    conclusion: Fact,
}

fn resolve_pat(p: &CPat, env: &[Option<u32>]) -> Option<u32> {
    match p {
        CPat::Const(id) => Some(*id),
        CPat::Var(i) => env[*i],
    }
}

/// Match one position against one term, binding a fresh variable and recording
/// the slot so the caller can undo it on backtracking.
fn unify_pat(p: &CPat, val: u32, env: &mut [Option<u32>], bound: &mut [usize; 3], nb: &mut usize) -> bool {
    match p {
        CPat::Const(id) => *id == val,
        CPat::Var(i) => match env[*i] {
            Some(existing) => existing == val,
            None => {
                env[*i] = Some(val);
                bound[*nb] = *i;
                *nb += 1;
                true
            }
        },
    }
}

/// Enumerate every way to match the body against the known facts, calling
/// `on_match` once per complete binding.
///
/// Plain backtracking, one atom at a time, left to right. An atom whose
/// predicate is already fixed (a constant, or a variable bound by an earlier
/// atom) is matched against the facts with that predicate; otherwise every fact
/// is a candidate. That is the whole optimisation, and it is not semi-naive
/// evaluation: each iteration re-derives what the last one did, and the
/// duplicate is dropped when its conclusion is found to be known. Correctness
/// first, as the task said. The cost is a constant factor per iteration on a
/// scan the loop does anyway, and `derived_triples` is unaffected.
fn match_body(
    atoms: &[CAtom],
    i: usize,
    env: &mut Vec<Option<u32>>,
    all: &[Fact],
    by_pred: &HashMap<u32, Vec<Fact>>,
    on_match: &mut dyn FnMut(&[Option<u32>]),
) {
    if i == atoms.len() {
        on_match(env);
        return;
    }
    let a = &atoms[i];
    let candidates: &[Fact] = match resolve_pat(&a.p, env) {
        Some(pid) => by_pred.get(&pid).map(Vec::as_slice).unwrap_or(&[]),
        None => all,
    };
    for &(s, p, o) in candidates {
        let mut bound = [0usize; 3];
        let mut nb = 0usize;
        let ok = unify_pat(&a.s, s, env, &mut bound, &mut nb)
            && unify_pat(&a.p, p, env, &mut bound, &mut nb)
            && unify_pat(&a.o, o, env, &mut bound, &mut nb);
        if ok {
            match_body(atoms, i + 1, env, all, by_pred, on_match);
        }
        for slot in bound.iter().take(nb) {
            env[*slot] = None;
        }
    }
}

fn inst_atom(a: &CAtom, env: &[Option<u32>]) -> Fact {
    const WHY: &str = "every variable of a matched rule is bound: the body is matched in full and \
                       parse_rules refuses a head variable that does not occur in the body";
    (
        resolve_pat(&a.s, env).expect(WHY),
        resolve_pat(&a.p, env).expect(WHY),
        resolve_pat(&a.o, env).expect(WHY),
    )
}

impl Reasoner {
    /// Evaluate a SUPPLIED Horn rule table over the loaded graph and write a
    /// certificate `lean`'s `oo-horn` can check.
    ///
    /// Three files land in `certificate_dir`:
    ///
    /// * `rules.tsv`, the table as the engine parsed it. The checker is given
    ///   this rather than the user's file, so what it checks and what the run
    ///   used are the same table.
    /// * `asserted.tsv`, every triple the run started from.
    /// * `horn.tsv`, one line per derived triple:
    ///   `ruleIndex TAB bindCount TAB (var TAB term)* TAB cs TAB cp TAB co TAB (ps TAB pp TAB po)*`.
    ///   The binding is written out in full and the premises are the body
    ///   instantiated, in the body's order, because that is what
    ///   `OOCert.checkHornStep` demands: a binding that does not instantiate
    ///   the body, or premises in the wrong order, is rejected.
    ///
    /// Steps are written in derivation order, and a step's premises are always
    /// facts that were known before the round that derived it, so every premise
    /// is asserted or concluded by an EARLIER line. That is the ordering
    /// `OOCert.checkHornAll` requires, and no step can cite itself.
    ///
    /// Nothing is materialised into the store. A conclusion under a supplied
    /// table holds only in models that satisfy that table, and writing it in
    /// beside the assertions would lose exactly the distinction decision 0003
    /// is about.
    ///
    /// Reads the whole store; refused over a bi-temporal store with no instant
    /// named, exactly as [`run_full`](Self::run_full) is. A certificate over a
    /// user's own rule table has the same blind spot as one over the built-in
    /// table and for the same reason: `oo-horn` verifies the steps against the
    /// triples in `asserted.tsv` and cannot ask where they came from.
    pub fn run_horn(
        graph: &Arc<GraphStore>,
        rules_path: &std::path::Path,
        certificate_dir: &std::path::Path,
    ) -> anyhow::Result<String> {
        Self::run_horn_scoped(graph, rules_path, certificate_dir, &ScopeRequest::Unscoped)
    }

    /// [`run_horn`](Self::run_horn) over a stated set of graphs (#108).
    pub fn run_horn_scoped(
        graph: &Arc<GraphStore>,
        rules_path: &std::path::Path,
        certificate_dir: &std::path::Path,
        request: &ScopeRequest,
    ) -> anyhow::Result<String> {
        let (scope, manifest) = crate::temporal::resolve(graph, request)?;
        let rules_text = std::fs::read_to_string(rules_path)
            .map_err(|e| anyhow::anyhow!("cannot read rule table {}: {e}", rules_path.display()))?;
        let rules = parse_rules(&rules_text)
            .map_err(|e| anyhow::anyhow!("{} is not a rule table: {e}", rules_path.display()))?;
        if rules.is_empty() {
            anyhow::bail!(
                "{} holds no rules. An empty table derives nothing, so there is no certificate \
                 to write",
                rules_path.display()
            );
        }

        let (raw_triples, graphs_read) = graph.triples_in_scope(&scope)?;
        let mut interner = Interner::new();
        let mut facts: Vec<Fact> = Vec::with_capacity(raw_triples.len());
        for (s, p, o) in &raw_triples {
            facts.push((interner.intern(s), interner.intern(p), interner.intern(o)));
        }

        // Compile the table over the interner. A constant the graph never
        // mentions still gets an id; it simply matches nothing, which is what
        // it should do.
        let mut crules: Vec<CRule> = Vec::with_capacity(rules.len());
        for r in &rules {
            let mut vars: Vec<String> = Vec::new();
            for a in r.atoms() {
                for p in [&a.s, &a.p, &a.o] {
                    if let Pat::Var(v) = p
                        && !vars.iter().any(|x| x == v)
                    {
                        vars.push(v.clone());
                    }
                }
            }
            let mut compile = |p: &Pat| match p {
                Pat::Const(c) => CPat::Const(interner.intern(c)),
                Pat::Var(v) => CPat::Var(vars.iter().position(|x| x == v).expect("var listed")),
            };
            let body: Vec<CAtom> = r
                .body
                .iter()
                .map(|a| CAtom { s: compile(&a.s), p: compile(&a.p), o: compile(&a.o) })
                .collect();
            let head = CAtom { s: compile(&r.head.s), p: compile(&r.head.p), o: compile(&r.head.o) };
            crules.push(CRule { vars, body, head });
        }

        // A rule whose head puts a literal in subject position, or anything but
        // an IRI in predicate position, produces something no RDF serialiser
        // can write. Both are refused, the count is reported, and the
        // conclusion is not used as a premise for anything else. Deriving less
        // is the sound direction, but it means the emitted set is the fixpoint
        // of the table over WRITABLE triples, which is what
        // `skipped_unserialisable` in the response is there to say.
        //
        // `run_full` now shares the predicate (`writable_triple`). It used to
        // have its own guard on the subject position only, at four rule sites,
        // and this path was the only one that refused a non-IRI predicate.
        let serialisable = |interner: &Interner, (s, p, _o): Fact| -> bool {
            writable_triple(interner.resolve(s), interner.resolve(p))
        };

        let mut known: HashSet<Fact> = facts.iter().copied().collect();
        let asserted_count = known.len();
        let mut steps: Vec<HornStepOut> = Vec::new();
        // Distinct conclusions refused for being unwritable. A set rather than
        // a counter because a refused conclusion is never added to `known`, so
        // every later round matches the same body again and re-derives it: a
        // counter would report attempts and grow with the iteration count,
        // which is not what a reader takes "skipped 2" to mean.
        let mut refused: HashSet<Fact> = HashSet::new();
        let mut skipped_samples: Vec<String> = Vec::new();
        let mut iterations = 0usize;
        let mut fixpoint = false;
        let max_iterations = crate::runtime::reasoner_max_iterations();

        while iterations < max_iterations {
            iterations += 1;

            // Sorted so the candidate order, and therefore the order of the
            // lines in `horn.tsv`, does not depend on hash iteration order.
            let mut all: Vec<Fact> = known.iter().copied().collect();
            all.sort_unstable();
            let mut by_pred: HashMap<u32, Vec<Fact>> = HashMap::new();
            for &f in &all {
                by_pred.entry(f.1).or_default().push(f);
            }

            let mut round: Vec<HornStepOut> = Vec::new();
            let mut pending: HashSet<Fact> = HashSet::new();
            for (ri, rule) in crules.iter().enumerate() {
                let mut env: Vec<Option<u32>> = vec![None; rule.vars.len()];
                let known_ref = &known;
                let interner_ref = &interner;
                let round_ref = &mut round;
                let pending_ref = &mut pending;
                let refused_ref = &mut refused;
                let samples_ref = &mut skipped_samples;
                match_body(&rule.body, 0, &mut env, &all, &by_pred, &mut |env| {
                    let conclusion = inst_atom(&rule.head, env);
                    if known_ref.contains(&conclusion) || pending_ref.contains(&conclusion) {
                        return;
                    }
                    if !serialisable(interner_ref, conclusion) {
                        if refused_ref.insert(conclusion) && samples_ref.len() < 3 {
                            samples_ref.push(format!(
                                "{} {} {}",
                                interner_ref.resolve(conclusion.0),
                                interner_ref.resolve(conclusion.1),
                                interner_ref.resolve(conclusion.2)
                            ));
                        }
                        return;
                    }
                    pending_ref.insert(conclusion);
                    round_ref.push(HornStepOut {
                        rule: ri,
                        binds: rule
                            .vars
                            .iter()
                            .enumerate()
                            .map(|(i, v)| (v.clone(), env[i].expect("matched body binds every body variable")))
                            .collect(),
                        premises: rule.body.iter().map(|a| inst_atom(a, env)).collect(),
                        conclusion,
                    });
                });
            }

            if round.is_empty() {
                fixpoint = true;
                break;
            }
            for st in round {
                known.insert(st.conclusion);
                steps.push(st);
            }
        }

        // Write the three files.
        std::fs::create_dir_all(certificate_dir)?;
        let canonical_rules = rules_tsv(&rules);
        // The checker verifies the steps against the FILE, and the run
        // evaluated the table in memory. If the rendering lost or changed
        // anything the two would be different rule sets, and a step would be
        // checked against a rule nobody ran. Reading the file back and
        // comparing costs nothing and closes that gap; a mismatch is a bug in
        // this file, so it stops the run rather than writing a certificate
        // whose meaning is not the run's.
        match parse_rules(&canonical_rules) {
            Ok(reparsed) if reparsed == rules => {}
            Ok(_) => anyhow::bail!(
                "internal: the rule table this engine writes does not read back as the table it \
                 evaluated, so the certificate would be checked against different rules. Refusing \
                 to write it"
            ),
            Err(e) => anyhow::bail!(
                "internal: the rule table this engine writes does not parse ({e}), so the checker \
                 could not read it. Refusing to write it"
            ),
        }
        std::fs::write(certificate_dir.join("rules.tsv"), &canonical_rules)?;

        let mut asserted: Vec<u8> = Vec::with_capacity(facts.len() * 96);
        for &(s, p, o) in &facts {
            push_asserted_line(
                &mut asserted,
                interner.resolve(s),
                interner.resolve(p),
                interner.resolve(o),
            )
            .map_err(|pos| unwritable_term("asserted.tsv", pos, interner.resolve(match pos {
                Position::Subject => s,
                Position::Predicate => p,
                Position::Object => o,
            })))?;
        }
        std::fs::write(certificate_dir.join("asserted.tsv"), asserted)?;

        let mut horn: Vec<u8> = Vec::with_capacity(steps.len() * 256);
        let mut by_rule: Vec<usize> = vec![0; rules.len()];
        for st in &steps {
            by_rule[st.rule] += 1;
            horn.extend_from_slice(st.rule.to_string().as_bytes());
            horn.push(b'\t');
            horn.extend_from_slice(st.binds.len().to_string().as_bytes());
            for (v, term) in &st.binds {
                // A variable name is not a term and has no N-Triples spelling,
                // so it gets the format half of the guard. `parse_rules` cannot
                // produce one carrying a separator, which is exactly why this
                // is cheap: it enforces here what is argued there.
                if !field_fits_the_format(v) {
                    anyhow::bail!(
                        "internal: the rule variable name {v:?} does not fit the certificate \
                         format, so no certificate was written"
                    );
                }
                let bound = interner.resolve(*term);
                if !term_fits_the_format(bound) {
                    return Err(unwritable_term("horn.tsv", Position::Object, bound));
                }
                horn.push(b'\t');
                horn.extend_from_slice(v.as_bytes());
                horn.push(b'\t');
                horn.extend_from_slice(bound.as_bytes());
            }
            for &(s, p, o) in std::iter::once(&st.conclusion).chain(st.premises.iter()) {
                push_triple_fields(
                    &mut horn,
                    interner.resolve(s),
                    interner.resolve(p),
                    interner.resolve(o),
                )
                .map_err(|pos| unwritable_term("horn.tsv", pos, interner.resolve(match pos {
                    Position::Subject => s,
                    Position::Predicate => p,
                    Position::Object => o,
                })))?;
            }
            horn.push(b'\n');
        }
        std::fs::write(certificate_dir.join("horn.tsv"), horn)?;

        let digest = {
            use sha2::{Digest, Sha256};
            format!("{:x}", Sha256::digest(canonical_rules.as_bytes()))
        };
        let per_rule: Vec<serde_json::Value> = rules
            .iter()
            .enumerate()
            .map(|(i, r)| {
                serde_json::json!({"index": i, "name": r.name, "derivations": by_rule[i]})
            })
            .collect();
        let sample: Vec<String> = steps
            .iter()
            .take(10)
            .map(|st| {
                format!(
                    "{} {} {}",
                    interner.resolve(st.conclusion.0),
                    interner.resolve(st.conclusion.1),
                    interner.resolve(st.conclusion.2)
                )
            })
            .collect();
        let dir = certificate_dir.display().to_string();

        let mut result = serde_json::json!({
            "mode": "horn",
            "rules_file": rules_path.display().to_string(),
            "rules": rules.len(),
            "asserted_triples": facts.len(),
            "distinct_asserted_triples": asserted_count,
            "graphs_read": graphs_read,
            "graphs_excluded": [INFERRED_GRAPH],
            "derived_triples": steps.len(),
            "iterations": iterations,
            "fixpoint_reached": fixpoint,
            "skipped_unserialisable": refused.len(),
            "materialized": false,
            "why_not_materialized":
                "a conclusion drawn under a supplied rule table holds only in models that satisfy \
                 that table, so it is not written into the store beside the assertions. The \
                 certificate is the output of this run",
            "conditional_on":
                format!("the rules in {}, which this run ASSUMED and never checked. A certificate \
                         is only as good as the table it cites: a rule saying every supplier is \
                         compliant produces steps that check green for ever",
                        rules_path.display()),
            "sample_derivations": sample,
            "certificate": {
                "dir": dir,
                "format": "oo-horn/1",
                "rules": rules.len(),
                "rules_tsv_sha256": digest,
                "asserted": facts.len(),
                "derivations": steps.len(),
                "by_rule": per_rule,
                "check_with": format!(
                    "cd lean && lake exe oo-horn check {d}/rules.tsv {d}/asserted.tsv {d}/horn.tsv",
                    d = certificate_dir.display()
                ),
                "pronounced_by":
                    "lean/, through `oo-horn check`, which decides what this run earned by \
                     comparing the table against the built-in one. This engine emits the \
                     certificate and states no verdict of its own",
                "scope": manifest.to_json(),
                "scope_file": certificate_dir.join("scope.tsv").display().to_string(),
                "scope_means": "oo-horn verifies the steps against the triples in asserted.tsv. \
                                It does not and cannot check that asserted.tsv is the graph you \
                                meant. scope.tsv records which graphs were read.",
            },
            "scope": manifest.to_json(),
        });
        std::fs::write(certificate_dir.join("scope.tsv"), manifest.to_tsv())?;
        if let Some(w) = &manifest.warning {
            result["warning"] = serde_json::json!(w);
        }
        if !fixpoint {
            // An iteration cap reached with work still to do is not a fixpoint,
            // and a count from such a run is a lower bound. Say it in the
            // result rather than let the caller read `derived_triples` as the
            // closure.
            result["incomplete"] = serde_json::json!(format!(
                "the run stopped at the {max_iterations}-iteration cap with rules still firing. \
                 Every step in the certificate is still a step the checker can verify, but \
                 derived_triples is a LOWER BOUND on the closure of this table, not the closure"
            ));
        }
        if !refused.is_empty() {
            result["skipped_examples"] = serde_json::json!(skipped_samples);
            result["skipped_reason"] = serde_json::json!(
                "the rule head instantiated to a triple no RDF serialiser can write (a literal in \
                 subject position, or a non-IRI in predicate position). Such conclusions are \
                 neither certified nor used as premises, so this run derives LESS than the table \
                 licenses"
            );
        }
        Ok(result.to_string())
    }
}

// ─────────────────────────────────────────────────────────────────────────────
// The trusted boundary, verified
//
// `docs/trusted-computing-base.md` enumerates what `lean/` assumes about this
// file. `tests/certificate_boundary_proptest.rs` property-tests the parts that
// need a store. What is left is a handful of pure functions, and those are
// small enough to do better than sample: the Kani harnesses below prove the
// same statements over EVERY input up to a length bound, rather than over the
// inputs a generator happened to draw.
// ─────────────────────────────────────────────────────────────────────────────

#[cfg(test)]
mod boundary_tests {
    use super::*;
    use proptest::prelude::*;

    /// `BUILTIN_RULES[r as usize]` is `r`'s row. Everything the emitter does
    /// with the table rests on this one line of arithmetic, and a row inserted
    /// in the middle without a matching enum variant would silently give every
    /// rule after it the next rule's premises.
    #[test]
    fn each_row_is_at_its_own_index() {
        assert_eq!(Rl::ALL.len(), BUILTIN_RULES.len());
        for (i, r) in Rl::ALL.iter().enumerate() {
            assert_eq!(*r as usize, i, "{r:?} is not at index {i}");
        }
        // The two rules that license two conclusions from one premise are the
        // only names that appear twice.
        let mut names: Vec<&str> = BUILTIN_RULES.iter().map(|r| r.name).collect();
        names.sort_unstable();
        let mut dups: Vec<&str> = names.windows(2).filter(|w| w[0] == w[1]).map(|w| w[0]).collect();
        dups.dedup();
        assert_eq!(dups, vec!["scm-eqc1", "scm-eqp1"]);
    }

    /// Terms that carry no separator, so the writer's precondition holds and
    /// the round trip is the thing under test.
    fn term() -> impl Strategy<Value = String> {
        prop_oneof![
            Just(String::new()),
            Just("<http://e/a>".to_string()),
            Just("\"lit\"".to_string()),
            Just("\"a\\tb\"".to_string()),
            Just("_:b0".to_string()),
            Just("e\u{0301}".to_string()),
            Just("\u{0000}".to_string()),
            "[^\t\n\r]{0,6}",
        ]
    }

    proptest! {
        #![proptest_config(ProptestConfig { cases: 1024, ..ProptestConfig::default() })]

        /// Every slot a rule pattern mentions is within the arity it declares,
        /// and every variable it declares is actually used. An unused slot is a
        /// binding a call site has to invent a term for; an out-of-range slot
        /// is a panic on a graph nobody happened to test.
        #[test]
        fn every_rule_slot_is_within_its_arity(i in 0usize..BUILTIN_RULES.len()) {
            let r = &BUILTIN_RULES[i];
            let mut seen = vec![false; r.vars.len()];
            for a in r.body.iter().chain(std::iter::once(&r.head)) {
                for s in a {
                    if let Slot::Var(k) = s {
                        prop_assert!(*k < r.vars.len(), "{} slot {k} of {}", r.name, r.vars.len());
                        seen[*k] = true;
                    }
                }
            }
            for (k, used) in seen.iter().enumerate() {
                prop_assert!(*used, "{} declares {} and never uses it", r.name, r.vars[k]);
            }
        }

        /// TCB-15 and TCB-16. The interner is a bijection between the strings it
        /// has seen and the ids it has issued. Every term in every certificate
        /// file passes through it, so if it were not, two different terms would
        /// print the same and a step would be checked against a triple the
        /// engine never used.
        #[test]
        fn tcb_15_16_the_interner_is_a_bijection(ss in prop::collection::vec(term(), 0..16)) {
            let mut i = Interner::new();
            let ids: Vec<u32> = ss.iter().map(|s| i.intern(s)).collect();
            for (s, &id) in ss.iter().zip(&ids) {
                prop_assert_eq!(i.resolve(id), s.as_str());
            }
            for a in 0..ss.len() {
                for b in 0..ss.len() {
                    prop_assert_eq!(ids[a] == ids[b], ss[a] == ss[b]);
                }
            }
        }

        /// TCB-17. An id keeps its meaning as more strings arrive. The
        /// certificate writers resolve ids long after the reasoning that
        /// created them.
        #[test]
        fn tcb_17_interning_more_does_not_move_an_id(
            early in prop::collection::vec(term(), 1..8),
            late in prop::collection::vec(term(), 0..8),
        ) {
            let mut i = Interner::new();
            let ids: Vec<u32> = early.iter().map(|s| i.intern(s)).collect();
            for s in &late {
                i.intern(s);
            }
            for (s, &id) in early.iter().zip(&ids) {
                prop_assert_eq!(i.resolve(id), s.as_str());
            }
        }

        /// TCB-1, as a statement about the writer alone. The writer accepts
        /// exactly the terms that fit the format, and what it accepts splits
        /// back into exactly those three terms. A refusal leaves the buffer
        /// untouched.
        ///
        /// This used to be a statement about terms the generator kept
        /// separator-free, because the writer took anything. The writer now
        /// decides, so the test covers both verdicts. The Kani harnesses below
        /// prove the same statement over every byte pattern up to a bound; this
        /// one runs in CI without a model checker installed and samples the
        /// lengths, including the empty string.
        #[test]
        fn tcb_1_an_asserted_line_splits_back_into_its_three_terms(
            s in term(), p in term(), o in term(),
        ) {
            let mut out: Vec<u8> = "<a>\t<b>\t<c>\n".as_bytes().to_vec();
            let before = out.clone();
            let r = push_asserted_line(&mut out, &s, &p, &o);
            let fits = term_fits_the_format(&s)
                && term_fits_the_format(&p)
                && term_fits_the_format(&o);
            prop_assert_eq!(r.is_ok(), fits);
            if r.is_err() {
                prop_assert_eq!(out, before, "a refused line left a fragment behind");
                return Ok(());
            }
            let out = String::from_utf8(out).expect("every byte came from a &str");
            let before = String::from_utf8(before).expect("every byte came from a &str");
            prop_assert!(out.ends_with('\n'));
            let line = out.strip_prefix(&before).expect("the line was appended");
            let body = &line[..line.len() - 1];
            prop_assert!(!body.contains('\n'));
            let f: Vec<&str> = body.split('\t').collect();
            prop_assert_eq!(f, vec![s.as_str(), p.as_str(), o.as_str()]);
        }

        /// TCB-2 and TCB-3, as a statement about the writer alone.
        #[test]
        fn tcb_2_3_triple_fields_append_exactly_three_fields(
            head in "[a-z0-9-]{1,8}",
            ts in prop::collection::vec((term(), term(), term()), 1..4),
        ) {
            let mut out: Vec<u8> = Vec::new();
            out.extend_from_slice(head.as_bytes());
            let mut written = 0usize;
            for (s, p, o) in &ts {
                let fits = term_fits_the_format(s)
                    && term_fits_the_format(p)
                    && term_fits_the_format(o);
                let before = out.clone();
                let r = push_triple_fields(&mut out, s, p, o);
                prop_assert_eq!(r.is_ok(), fits);
                if r.is_err() {
                    prop_assert_eq!(out.clone(), before);
                } else {
                    written += 1;
                }
            }
            let out = String::from_utf8(out).expect("every byte came from a &str");
            let f: Vec<&str> = out.split('\t').collect();
            prop_assert_eq!(f.len(), 1 + 3 * written);
            prop_assert_eq!(f[0], head.as_str());
            let mut i = 0usize;
            for (s, p, o) in ts.iter() {
                if !(term_fits_the_format(s) && term_fits_the_format(p) && term_fits_the_format(o)) {
                    continue;
                }
                prop_assert_eq!(f[1 + 3 * i], s.as_str());
                prop_assert_eq!(f[2 + 3 * i], p.as_str());
                prop_assert_eq!(f[3 + 3 * i], o.as_str());
                i += 1;
            }
        }

        /// TCB-4 and TCB-5, as a statement about the guard alone. A term the
        /// guard accepts carries no separator and is in one of the three
        /// N-Triples spellings, and two accepted terms of different spellings
        /// are different strings, which is what lets the two checkers compare
        /// terms as opaque strings.
        ///
        /// The Kani harness `term_guard_is_exact` proves this over every byte
        /// pattern at a bound rather than over a sample.
        #[test]
        fn tcb_4_5_the_guard_decides_separators_and_spelling(a in term(), b in term()) {
            for t in [&a, &b] {
                if term_fits_the_format(t) {
                    prop_assert!(!t.contains(['\t', '\n', '\r']));
                    prop_assert!(!t.is_empty());
                    prop_assert!(t.starts_with('<') || t.starts_with('"') || t.starts_with("_:"));
                }
            }
            if term_fits_the_format(&a) && term_fits_the_format(&b) {
                let kind = |t: &str| t.as_bytes()[0];
                if kind(&a) != kind(&b) {
                    prop_assert_ne!(&a, &b);
                }
            }
        }

        /// The `&str` wrappers agree with the `char`-level predicates they
        /// replaced.
        ///
        /// `writable_triple`, `field_fits_the_format`, `term_fits_the_format`
        /// and `name_is_safe` are now one line each, delegating to
        /// `crate::boundary_core`, which is the file Aeneas translates into the
        /// Lean model under `aeneas/`. The delegation is `as_bytes()` and the
        /// argument that it changes nothing is that every byte those functions
        /// look for is ASCII and no ASCII byte occurs inside a multi-byte UTF-8
        /// sequence. That is an argument. This is the test: the ORIGINAL bodies
        /// are written out here and required to agree with the shipped
        /// wrappers on the same adversarial generator, including a combining
        /// character, a NUL and a lexical form spelled like an IRI.
        #[test]
        fn tcb_wrappers_agree_with_the_char_level_predicates(t in term(), u in term()) {
            for s in [&t, &u] {
                // As `field_fits_the_format` was written before the extraction.
                let field_before = !s.is_empty() && !s.contains(['\t', '\n', '\r']);
                prop_assert_eq!(field_fits_the_format(s), field_before, "{:?}", s);

                // As `term_fits_the_format` was written before the extraction.
                let term_before = field_before && {
                    let b = s.as_bytes();
                    b[0] == b'<' || b[0] == b'"' || (b[0] == b'_' && b.len() > 1 && b[1] == b':')
                };
                prop_assert_eq!(term_fits_the_format(s), term_before, "{:?}", s);

                // As `tableaux::name_is_safe` was written before the extraction.
                let name_before = !s.is_empty() && !s.contains([' ', '\t', '\n', '\r']);
                prop_assert_eq!(
                    crate::boundary_core::name_is_safe_bytes(s.as_bytes()),
                    name_before,
                    "{:?}", s
                );
            }
            // As `writable_triple` was written before the extraction.
            let writable_before = !t.starts_with('"') && u.starts_with('<');
            prop_assert_eq!(writable_triple(&t, &u), writable_before, "{:?} {:?}", t, u);
        }

        /// TCB-20 at one rule position. `parse_pat` and `Pat::render` are
        /// inverse, so a constant never renders to something that reads back as
        /// a variable. `run_horn`'s re-parse guard rests on this.
        ///
        /// Both directions, and `pat_of` is the classifier `parse_pat` is now
        /// built on, so this also pins that the refactor did not move the
        /// boundary between accept and refuse.
        #[test]
        fn tcb_20_parse_pat_and_render_are_inverse(field in "[^\t\n\r]{0,8}") {
            let via_pat_of = pat_of(&field);
            prop_assert_eq!(
                parse_pat(&field, 1, "position").ok(),
                via_pat_of.clone(),
                "parse_pat and pat_of disagree on {:?}", field
            );
            if let Some(p) = via_pat_of {
                prop_assert_eq!(p.render(), field);
            }
        }

        /// TCB-20, the other direction: a pattern renders to a field that reads
        /// back as the same pattern. This is the direction `rules_tsv` needs,
        /// because it renders the table the checker then parses.
        #[test]
        fn tcb_20_render_then_parse_returns_the_pattern(
            name in "[^\t\n\r]{1,8}",
            c in prop_oneof![
                Just("<http://e/a>".to_string()),
                Just("\"lit\"".to_string()),
                Just("_:b0".to_string()),
            ],
            is_var in any::<bool>(),
        ) {
            let p = if is_var { Pat::Var(name) } else { Pat::Const(c) };
            prop_assert_eq!(pat_of(&p.render()), Some(p));
        }
    }
}

/// Bounded model checking of the pure functions on the trusted boundary.
///
/// Run with `cargo kani --harness <name>`. Not part of `cargo test`: Kani
/// compiles the crate with its own toolchain, and a `#[cfg(kani)]` block is
/// invisible to a normal build. What each harness proves and what it does NOT
/// prove is written on it, because a bounded proof read as an unbounded one is
/// the same defect this whole layer exists to attack.
#[cfg(kani)]
mod kani_harnesses {
    use super::*;

    /// An ASCII string of EXACTLY `N` bytes, every byte unconstrained below
    /// 0x80. `kani::any` cannot produce a `String`; ASCII because every byte
    /// below 0x80 is valid UTF-8 on its own.
    ///
    /// Two decisions here are what make these harnesses terminate, and both are
    /// worth recording because the first attempts did not.
    ///
    /// `from_utf8_unchecked` rather than `from_utf8`. With the checked version
    /// CBMC symbolically executes `core::str::validations::run_utf8_validation`
    /// once per buffer, and that loop, not the function under test, becomes
    /// what the harness measures: seventeen minutes and three gigabytes with no
    /// verdict, the log a wall of `Unwinding loop ... run_utf8_validation`. The
    /// `assume` below already establishes exactly what `from_utf8` would check.
    ///
    /// A FIXED length rather than a symbolic one. A symbolic `n` makes every
    /// offset in the produced line symbolic, every slice bound a case split,
    /// and the cost compounds across three terms: two bytes per term with a
    /// symbolic length reached fifteen gigabytes without a verdict. The length
    /// dimension is covered instead by INSTANTIATING the generic harnesses
    /// below at several lengths, `0` included, so the claim is "every byte
    /// pattern at each of these lengths" rather than "every byte pattern at one
    /// length". That is still a bound and it is stated on each harness.
    fn any_ascii<const N: usize>(buf: &mut [u8; N]) -> &str {
        *buf = kani::any();
        for b in buf.iter() {
            kani::assume(*b < 0x80);
        }
        // SAFETY: every byte is assumed below 0x80, so the buffer is ASCII and
        // therefore valid UTF-8. The assumption is the model checker's, so it
        // holds on every path it explores.
        unsafe { core::str::from_utf8_unchecked(&buf[..]) }
    }

    /// TCB-1 and TCB-4, over every byte pattern at length `N` rather than over
    /// a sample, and with no assumption that the terms are separator-free.
    ///
    /// The writer now DECIDES that, so the harness proves the decision as well
    /// as the layout: `push_asserted_line` returns `Ok` exactly when all three
    /// terms fit the format, and when it does, the line it wrote carries
    /// exactly two tabs and one newline, the newline last, with the three terms
    /// at the offsets those separators imply. When it refuses, the buffer is
    /// byte for byte what it was, so a refusal cannot leave half a line behind.
    ///
    /// Until 15 September 2026 this harness ASSUMED separator-freedom, because
    /// nothing in this repository enforced it: it was a property of `oxrdf`'s
    /// `Display` and of `oxiri` refusing to parse. The assumption is now a
    /// branch of the function under test.
    ///
    /// The claim is about the BYTES, not about Rust's `split`. The reader is
    /// `OOCert.Parse.parseTriples`, which is Lean's `String.splitOn`, so a proof
    /// about `str::split` would be a proof about the wrong splitter. Asserting
    /// on `body.split('\t')` also put CBMC inside `CharSearcher` and ran ten
    /// minutes to two gigabytes without a verdict. The `split` formulation is
    /// kept as a property test in `boundary_tests`, where it is free.
    fn asserted_line_layout<const N: usize>() {
        let (mut a, mut b, mut c) = ([0u8; N], [0u8; N], [0u8; N]);
        let s = any_ascii(&mut a);
        let p = any_ascii(&mut b);
        let o = any_ascii(&mut c);

        // A non-empty buffer, so "nothing was appended" is a real claim and not
        // "the buffer is still empty".
        let mut out: Vec<u8> = Vec::with_capacity(4 * N + 8);
        out.push(b'x');
        let r = push_asserted_line(&mut out, s, p, o);

        let fits =
            term_fits_the_format(s) && term_fits_the_format(p) && term_fits_the_format(o);
        assert!(r.is_ok() == fits);
        if !fits {
            assert!(out.len() == 1);
            assert!(out[0] == b'x');
            return;
        }

        let w = &out[1..];

        // Nothing added and nothing lost: three terms, two tabs, one newline.
        assert!(w.len() == 3 * N + 3);

        // The separators are where the grammar says.
        assert!(w[N] == b'\t');
        assert!(w[2 * N + 1] == b'\t');
        assert!(w[3 * N + 2] == b'\n');

        // And nowhere else, so any correct splitter finds exactly three fields.
        let mut tabs = 0usize;
        let mut newlines = 0usize;
        let mut i = 0usize;
        while i < w.len() {
            if w[i] == b'\t' {
                tabs += 1;
            }
            if w[i] == b'\n' {
                newlines += 1;
            }
            i += 1;
        }
        assert!(tabs == 2);
        assert!(newlines == 1);

        // The three terms are at the offsets those separators imply, byte for
        // byte, so no term was altered on the way out.
        let mut k = 0usize;
        while k < N {
            assert!(w[k] == s.as_bytes()[k]);
            assert!(w[N + 1 + k] == p.as_bytes()[k]);
            assert!(w[2 * N + 2 + k] == o.as_bytes()[k]);
            k += 1;
        }
    }

    /// The empty term. Every position is refused and nothing is written.
    #[kani::proof]
    #[kani::unwind(24)]
    fn asserted_line_round_trips_at_0() {
        asserted_line_layout::<0>();
    }

    #[kani::proof]
    #[kani::unwind(24)]
    fn asserted_line_round_trips_at_1() {
        asserted_line_layout::<1>();
    }

    #[kani::proof]
    #[kani::unwind(24)]
    fn asserted_line_round_trips_at_2() {
        asserted_line_layout::<2>();
    }

    /// The length the original harness was fixed at. Renamed from
    /// `asserted_line_round_trips` because `cargo kani --harness NAME` selects
    /// by SUBSTRING: the bare name matched all five of these and ran them
    /// together, which is how `_at_4` first failed inside a run reported under
    /// another harness's heading. Every harness name here is now a full name.
    #[kani::proof]
    #[kani::unwind(24)]
    fn asserted_line_round_trips_at_3() {
        asserted_line_layout::<3>();
    }

    #[kani::proof]
    #[kani::unwind(24)]
    fn asserted_line_round_trips_at_4() {
        asserted_line_layout::<4>();
    }

    /// TCB-2, TCB-3 and TCB-4. Three fields appended to a line already begun
    /// come back as three fields, so a step's conclusion and its premises
    /// cannot run into one another, and the writer refuses exactly the terms
    /// that do not fit the format.
    fn triple_fields_layout<const N: usize>() {
        let (mut a, mut b, mut c) = ([0u8; N], [0u8; N], [0u8; N]);
        let s = any_ascii(&mut a);
        let p = any_ascii(&mut b);
        let o = any_ascii(&mut c);

        let mut out: Vec<u8> = Vec::with_capacity(4 * N + 8);
        out.push(b'r');
        let r = push_triple_fields(&mut out, s, p, o);

        let fits =
            term_fits_the_format(s) && term_fits_the_format(p) && term_fits_the_format(o);
        assert!(r.is_ok() == fits);
        if !fits {
            assert!(out.len() == 1);
            assert!(out[0] == b'r');
            return;
        }

        let w = out.as_slice();
        assert!(w.len() == 1 + 3 * N + 3);
        assert!(w[0] == b'r');
        assert!(w[1] == b'\t');
        assert!(w[2 + N] == b'\t');
        assert!(w[3 + 2 * N] == b'\t');

        // Exactly three tabs are added and no newline, so the header field
        // keeps its position and the triple occupies exactly the next three.
        let mut tabs = 0usize;
        let mut i = 0usize;
        while i < w.len() {
            if w[i] == b'\t' {
                tabs += 1;
            }
            assert!(w[i] != b'\n');
            i += 1;
        }
        assert!(tabs == 3);

        let mut k = 0usize;
        while k < N {
            assert!(w[2 + k] == s.as_bytes()[k]);
            assert!(w[3 + N + k] == p.as_bytes()[k]);
            assert!(w[4 + 2 * N + k] == o.as_bytes()[k]);
            k += 1;
        }
    }

    #[kani::proof]
    #[kani::unwind(24)]
    fn triple_fields_append_exactly_three_at_0() {
        triple_fields_layout::<0>();
    }

    #[kani::proof]
    #[kani::unwind(24)]
    fn triple_fields_append_exactly_three_at_2() {
        triple_fields_layout::<2>();
    }

    #[kani::proof]
    #[kani::unwind(24)]
    fn triple_fields_append_exactly_three_at_3() {
        triple_fields_layout::<3>();
    }

    #[kani::proof]
    #[kani::unwind(24)]
    fn triple_fields_append_exactly_three_at_4() {
        triple_fields_layout::<4>();
    }

    /// TCB-4. A term the guard accepts carries NO separator, anywhere.
    ///
    /// Stated over a symbolic index rather than as a loop, so it is the
    /// universally quantified claim the Lean parser needs and not a
    /// restatement of the implementation's own scan. This is the property that
    /// used to be an observation about `oxrdf`: the certificate writers are now
    /// the place it is decided, and this is the proof that the decision is the
    /// right one.
    fn term_guard_admits_no_separator<const N: usize>() {
        let mut buf = [0u8; N];
        let t = any_ascii(&mut buf);
        if !term_fits_the_format(t) {
            return;
        }
        assert!(N > 0);
        let i: usize = kani::any();
        kani::assume(i < N);
        let b = t.as_bytes()[i];
        assert!(b != b'\t' && b != b'\n' && b != b'\r');
    }

    #[kani::proof]
    #[kani::unwind(16)]
    fn term_guard_admits_no_separator_at_3() {
        term_guard_admits_no_separator::<3>();
    }

    #[kani::proof]
    #[kani::unwind(24)]
    fn term_guard_admits_no_separator_at_6() {
        term_guard_admits_no_separator::<6>();
    }

    /// TCB-5. The spellings do not collide.
    ///
    /// An accepted term is an IRI, a blank node or a literal and never two of
    /// them, the kind is decided by the leading byte, and two accepted terms of
    /// different kinds are therefore different strings. That is what entitles
    /// `oo-cert` and `oo-horn` to compare terms as opaque strings: a literal
    /// whose lexical form is spelled exactly like an IRI cannot be that IRI,
    /// because the literal is quoted and the IRI is bracketed.
    #[kani::proof]
    #[kani::unwind(16)]
    fn term_guard_separates_the_three_spellings() {
        let (mut x, mut y) = ([0u8; 3], [0u8; 3]);
        let a = any_ascii(&mut x);
        let b = any_ascii(&mut y);
        kani::assume(term_fits_the_format(a));
        kani::assume(term_fits_the_format(b));

        let kinds = |t: &str| -> u8 {
            (t.starts_with('<') as u8)
                + (t.starts_with('"') as u8)
                + (t.starts_with("_:") as u8)
        };
        // Exactly one kind, so the partition is a partition.
        assert!(kinds(a) == 1);
        assert!(kinds(b) == 1);

        if a.as_bytes()[0] != b.as_bytes()[0] {
            assert!(a != b);
        }
    }

    /// The guard that fixed the unwritable-predicate defect. For ANY pair of
    /// strings it decides both positions and never panics. The statement is
    /// small because the function is; its value is that the engine now has
    /// exactly one of these, so this is the only place the question is decided.
    #[kani::proof]
    #[kani::unwind(12)]
    fn writable_triple_decides_both_positions() {
        let (mut a, mut b) = ([0u8; 4], [0u8; 4]);
        let s = any_ascii(&mut a);
        let p = any_ascii(&mut b);
        let ok = writable_triple(s, p);
        assert!(ok == (s.as_bytes()[0] != b'"' && p.as_bytes()[0] == b'<'));
    }

    /// TCB-20. `pat_of` and `Pat::render` are inverse, so a constant never
    /// renders to something that reads back as a variable and a variable name
    /// never renders to something that reads back as a constant. `run_horn`'s
    /// re-parse guard, and therefore the claim that the checker reads the table
    /// the engine evaluated, rests on this.
    ///
    /// **This is the harness the previous version of this file reported as NOT
    /// TERMINATING.** It targeted `parse_pat`, which returns `anyhow::Result`
    /// and formats a message naming the line and the position on every refusal,
    /// so the function body carried the whole formatting machinery. CBMC
    /// flattens a function before it solves, so an `assume` that makes the
    /// refusal paths infeasible is a constraint for the solver and not a cut in
    /// the program: constraining the input made it worse, not better. Measured
    /// then, with nothing else competing: four unconstrained ASCII bytes, no
    /// verdict at 7 minutes and 3.0 GB; two bytes, no verdict at 8 minutes and
    /// 2.8 GB; two bytes with the first constrained to the three spellings the
    /// function accepts, no verdict at 14 minutes and 9.5 GB.
    ///
    /// What that harness said would close it was "lifting the classification
    /// out of `parse_pat` into a pure `Option<Pat>` function, leaving the
    /// messages where they are". That is `pat_of`, and this is the harness. The
    /// input is unconstrained, both verdicts are explored, and the refusal
    /// branch is proved to be exactly the fields that are neither a named
    /// variable nor an N-Triples term.
    fn pat_of_and_render_are_inverse<const N: usize>() {
        let mut buf = [0u8; N];
        let field = any_ascii(&mut buf);
        let b = field.as_bytes();
        let named_var = N > 1 && b[0] == b'?';
        let nt_term = N > 0
            && (b[0] == b'<' || b[0] == b'"' || (b[0] == b'_' && N > 1 && b[1] == b':'));
        match pat_of(field) {
            Some(p) => {
                assert!(named_var || nt_term);
                assert!(p.render() == field);
            }
            None => assert!(!named_var && !nt_term),
        }
    }

    #[kani::proof]
    #[kani::unwind(12)]
    fn pat_of_and_render_are_inverse_at_2() {
        pat_of_and_render_are_inverse::<2>();
    }

    #[kani::proof]
    #[kani::unwind(12)]
    fn pat_of_and_render_are_inverse_at_3() {
        pat_of_and_render_are_inverse::<3>();
    }
}