shifty_engine/

lib.rs

//! Validation + SHACL-AF inference execution (Layers 3, 6, 7).
//!
//! Layer 3 lives here: the naive denotational evaluator that is the conformance
//! oracle — relational path evaluation ([`path`]), value-type checks
//! ([`value`]), and shape/schema satisfaction ([`validate`]). The rule/fixpoint
//! inference engine (Layer 6) and compiled executors (Layer 7) come later; every
//! execution mode must agree with this oracle.

pub mod enumerate;
pub mod frozen;
pub mod gate;
pub mod infer;
mod native_exec;
pub mod path;
mod path_plan;
pub mod profile;
pub mod report;
mod sparql;
pub mod synthesize;
pub mod validate;
pub mod value;
pub mod witness;

pub use enumerate::{
    EnumOptions, FixpointResult, RepairSolution, candidates, enumerate_repair, repair_to_fixpoint,
};
pub use gate::{RepairOutcome, apply, gate};
pub use infer::{
    InferenceOutcome, infer, infer_graphs, infer_with_context, infer_with_context_and_options,
    infer_with_options,
};
pub use report::{
    PropertyWitness, ValidationReport, ValidationResult, evaluate_function_expression,
    property_witnesses_graphs_with_mode, property_witnesses_graphs_with_mode_and_options,
    report_to_graph, validate_report, validate_report_graphs, validate_report_graphs_with_mode,
    validate_report_graphs_with_mode_and_options, validate_report_with_options,
};
pub use synthesize::{synthesize, synthesize_focus};
pub use validate::{
    EngineOptions, NonStratifiable, Reason, UnsupportedPolicy, ValidationGraphMode,
    ValidationOptions, ValidationOutcome, Violation, focus_nodes, graph_union, validate,
    validate_graphs, validate_graphs_with_mode, validate_graphs_with_mode_and_options,
    validate_plan, validate_plan_graphs, validate_plan_graphs_with_mode,
    validate_plan_graphs_with_mode_and_options, validate_plan_with_context,
    validate_plan_with_context_and_options, validate_plan_with_options, validate_with_context,
    validate_with_context_and_options, validate_with_options,
};
pub use witness::{
    BlockReason, FocusSat, FocusWitness, PathSupport, RelKind, SatTrace, Witness, satisfy_shape,
    shape_id_for_iri, witness_node, witness_shape, witness_violations,
};

#[cfg(test)]
mod tests {
    use super::*;
    use oxrdf::Graph;
    use shifty_parse::parse_turtle;

    fn run(shapes_and_data: &str) -> ValidationOutcome {
        let out = parse_turtle(shapes_and_data.as_bytes(), None).unwrap();
        // data graph = the same graph (shapes + data coexist), as in the suite.
        let loaded = shifty_parse::load_turtle(shapes_and_data.as_bytes(), None).unwrap();
        validate(&loaded.graph, &out.schema).expect("stratifiable schema")
    }

    /// Like [`run`], but validates the *normalized* schema — the schema the CLI
    /// and wasm front-ends actually run, where NNF rewriting can reshape the IR
    /// that reporting inspects.
    fn run_normalized(shapes_and_data: &str) -> ValidationOutcome {
        let out = parse_turtle(shapes_and_data.as_bytes(), None).unwrap();
        let loaded = shifty_parse::load_turtle(shapes_and_data.as_bytes(), None).unwrap();
        let normalized = shifty_opt::normalize(&out.schema);
        validate(&loaded.graph, &normalized).expect("stratifiable schema")
    }

    const PREFIXES: &str = r#"
        @prefix sh:  <http://www.w3.org/ns/shacl#> .
        @prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
        @prefix ex:  <http://ex/> .
        @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
    "#;

    /// A `sh:class` value constraint on a property is the universal
    /// `∀path.(instance of C)`, lowered to `∃≤0 path.¬(instance of C)`. After
    /// NNF normalization the inner `¬(instance of C)` becomes an `∃≤0` class
    /// count rather than a bare `Not`, which used to defeat the drill-in and
    /// leave the raw "at most 0 value(s) … found 1" message. The offender should
    /// instead be told which class the value must be an instance of.
    #[test]
    fn normalized_class_universal_names_the_required_class() {
        let ttl = format!(
            "{PREFIXES}
            ex:SensorShape a sh:NodeShape ;
                sh:targetClass ex:Sensor ;
                sh:property [ sh:path ex:hasKind ; sh:class ex:QuantityKind ] .

            ex:s1 a ex:Sensor ; ex:hasKind ex:Temperature .
            # ex:Temperature is deliberately untyped (as if its ontology import
            # were missing), so it fails the class check.
            "
        );

        let outcome = run_normalized(&ttl);
        let messages: Vec<&str> = outcome
            .violations
            .iter()
            .flat_map(|v| v.reasons.iter())
            .map(|r| r.message.as_str())
            .collect();

        assert!(
            messages.contains(&"must be an instance of <http://ex/QuantityKind>"),
            "expected an intuitive class message, got: {messages:?}"
        );
        // The old double-negated structural phrasing must not surface.
        assert!(
            !messages.iter().any(|m| m.contains("at most 0")),
            "raw ∃≤0 message leaked: {messages:?}"
        );

        // The offending value node and path are carried on the reason.
        let reason = outcome
            .violations
            .iter()
            .flat_map(|v| &v.reasons)
            .find(|r| r.message.starts_with("must be an instance of"))
            .expect("class reason present");
        assert_eq!(reason.value.to_string(), "<http://ex/Temperature>");
        assert_eq!(reason.path.as_deref(), Some("<http://ex/hasKind>"));
    }

    /// A universal whose `¬φ` normalizes to a non-`Not`, non-class form — here a
    /// complemented `sh:nodeKind` — still names the positive requirement (the
    /// general `describe_negation` path) instead of the raw `∃≤0` count message.
    #[test]
    fn normalized_nodekind_universal_names_the_requirement() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetClass ex:T ;
                sh:property [ sh:path ex:p ; sh:nodeKind sh:IRI ] .

            ex:a a ex:T ; ex:p \"not-an-iri\" .
            "
        );

        let outcome = run_normalized(&ttl);
        let messages: Vec<&str> = outcome
            .violations
            .iter()
            .flat_map(|v| v.reasons.iter())
            .map(|r| r.message.as_str())
            .collect();

        assert!(
            messages.contains(&"must satisfy `nodeKind(IRI)`"),
            "expected a nodeKind requirement message, got: {messages:?}"
        );
        assert!(
            !messages.iter().any(|m| m.contains("at most 0")),
            "raw ∃≤0 message leaked: {messages:?}"
        );
    }

    /// A source shape's `sh:message` rides through lowering + normalization on
    /// `Shape::Annotated` and is stamped onto each reason (with `{$this}`
    /// resolved to the focus node), while the generated `message` stays as a
    /// fallback. Shapes without one leave `author_message` unset.
    #[test]
    fn author_sh_message_is_carried_onto_reasons() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetClass ex:T ;
                sh:property [ sh:path ex:hasKind ; sh:class ex:QuantityKind ;
                    sh:message \"{{$this}} needs a known QuantityKind\" ] .

            ex:a a ex:T ; ex:hasKind ex:Temperature .
            "
        );

        let outcome = run_normalized(&ttl);
        let reason = outcome
            .violations
            .iter()
            .flat_map(|v| &v.reasons)
            .find(|r| r.author_message.is_some())
            .expect("author message present");

        // `{$this}` resolved to the focus node, generated message kept as fallback.
        assert_eq!(
            reason.author_message.as_deref(),
            Some("<http://ex/a> needs a known QuantityKind")
        );
        assert_eq!(
            reason.message,
            "must be an instance of <http://ex/QuantityKind>"
        );
    }

    /// Without `sh:message`, `author_message` stays `None` (generated only).
    #[test]
    fn absent_sh_message_leaves_author_message_unset() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetClass ex:T ;
                sh:property [ sh:path ex:hasKind ; sh:class ex:QuantityKind ] .

            ex:a a ex:T ; ex:hasKind ex:Temperature .
            "
        );

        let outcome = run_normalized(&ttl);
        assert!(
            outcome
                .violations
                .iter()
                .flat_map(|v| &v.reasons)
                .all(|r| r.author_message.is_none()),
            "no author message expected"
        );
    }

    #[test]
    fn inference_rules_fire_for_implicit_class_targets() {
        let ttl = br#"
            @prefix rdf:   <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
            @prefix rdfs:  <http://www.w3.org/2000/01/rdf-schema#> .
            @prefix owl:   <http://www.w3.org/2002/07/owl#> .
            @prefix sh:    <http://www.w3.org/ns/shacl#> .
            @prefix ex:    <http://ex/> .

            ex:Parent a owl:Class, sh:NodeShape ;
                sh:rule [
                    a sh:TripleRule ;
                    sh:subject sh:this ;
                    sh:predicate ex:hasTag ;
                    sh:object ex:Tag
                ] .

            ex:Child rdfs:subClassOf ex:Parent .
            ex:item a ex:Child .
        "#;
        let loaded = shifty_parse::load_turtle(ttl, None).unwrap();
        let parsed = shifty_parse::parse_loaded(&loaded);
        let normalized = shifty_opt::normalize(&parsed.schema);

        let outcome = infer(&loaded.graph, &normalized).expect("stratifiable schema");

        assert!(outcome.graph.contains(&oxrdf::Triple::new(
            oxrdf::NamedNode::new_unchecked("http://ex/item"),
            oxrdf::NamedNode::new_unchecked("http://ex/hasTag"),
            oxrdf::NamedNode::new_unchecked("http://ex/Tag"),
        )));
    }

    /// Parse + normalize + infer, asserting the parser emitted no diagnostics
    /// (so the node expressions under test were actually lowered, not skipped).
    fn infer_ttl(ttl: &[u8]) -> InferenceOutcome {
        let loaded = shifty_parse::load_turtle(ttl, None).unwrap();
        let parsed = shifty_parse::parse_loaded(&loaded);
        assert!(
            parsed.diagnostics.is_empty(),
            "parse diagnostics: {:?}",
            parsed.diagnostics
        );
        let normalized = shifty_opt::normalize(&parsed.schema);
        infer(&loaded.graph, &normalized).expect("stratifiable schema")
    }

    fn triple_term(s: &str, p: &str, o: impl Into<oxrdf::Term>) -> oxrdf::Triple {
        oxrdf::Triple::new(
            oxrdf::NamedNode::new_unchecked(s),
            oxrdf::NamedNode::new_unchecked(p),
            o,
        )
    }

    #[test]
    fn rule_object_union_node_expression() {
        // sh:union of two paths: both reachable values are inferred.
        let outcome = infer_ttl(
            br#"
            @prefix sh: <http://www.w3.org/ns/shacl#> .
            @prefix ex: <http://ex/> .
            ex:PersonShape a sh:NodeShape ;
                sh:targetClass ex:Person ;
                sh:rule [
                    a sh:TripleRule ;
                    sh:subject sh:this ;
                    sh:predicate ex:contact ;
                    sh:object [ sh:union ( [ sh:path ex:email ] [ sh:path ex:phone ] ) ]
                ] .
            ex:alice a ex:Person ; ex:email "a@x.org" ; ex:phone "555-1234" .
        "#,
        );
        let email = oxrdf::Literal::new_simple_literal("a@x.org");
        let phone = oxrdf::Literal::new_simple_literal("555-1234");
        assert!(outcome.graph.contains(&triple_term(
            "http://ex/alice",
            "http://ex/contact",
            email
        )));
        assert!(outcome.graph.contains(&triple_term(
            "http://ex/alice",
            "http://ex/contact",
            phone
        )));
    }

    #[test]
    fn rule_object_intersection_node_expression() {
        // sh:intersection of two paths: only the value reachable by both is inferred.
        let outcome = infer_ttl(
            br#"
            @prefix sh: <http://www.w3.org/ns/shacl#> .
            @prefix ex: <http://ex/> .
            ex:S a sh:NodeShape ;
                sh:targetClass ex:T ;
                sh:rule [
                    a sh:TripleRule ;
                    sh:subject sh:this ;
                    sh:predicate ex:both ;
                    sh:object [ sh:intersection ( [ sh:path ex:a ] [ sh:path ex:b ] ) ]
                ] .
            ex:x a ex:T ; ex:a ex:shared, ex:onlyA ; ex:b ex:shared, ex:onlyB .
        "#,
        );
        let both = "http://ex/both";
        assert!(outcome.graph.contains(&triple_term(
            "http://ex/x",
            both,
            oxrdf::NamedNode::new_unchecked("http://ex/shared")
        )));
        assert!(!outcome.graph.contains(&triple_term(
            "http://ex/x",
            both,
            oxrdf::NamedNode::new_unchecked("http://ex/onlyA")
        )));
        assert!(!outcome.graph.contains(&triple_term(
            "http://ex/x",
            both,
            oxrdf::NamedNode::new_unchecked("http://ex/onlyB")
        )));
    }

    #[test]
    fn rule_object_filter_node_expression() {
        // sh:filterShape + sh:nodes: keep only the values that conform to the shape.
        let outcome = infer_ttl(
            br#"
            @prefix sh:  <http://www.w3.org/ns/shacl#> .
            @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
            @prefix ex:  <http://ex/> .
            ex:IntShape a sh:NodeShape ; sh:datatype xsd:integer .
            ex:S a sh:NodeShape ;
                sh:targetClass ex:T ;
                sh:rule [
                    a sh:TripleRule ;
                    sh:subject sh:this ;
                    sh:predicate ex:intValue ;
                    sh:object [ sh:filterShape ex:IntShape ; sh:nodes [ sh:path ex:value ] ]
                ] .
            ex:x a ex:T ; ex:value 42, "hello" .
        "#,
        );
        let int_value = "http://ex/intValue";
        assert!(outcome.graph.contains(&triple_term(
            "http://ex/x",
            int_value,
            oxrdf::Literal::new_typed_literal(
                "42",
                oxrdf::NamedNode::new_unchecked("http://www.w3.org/2001/XMLSchema#integer")
            )
        )));
        assert!(!outcome.graph.contains(&triple_term(
            "http://ex/x",
            int_value,
            oxrdf::Literal::new_simple_literal("hello")
        )));
    }

    #[test]
    fn planned_validation_preserves_severity_and_applies_threshold() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode ex:x ;
                sh:property ex:InfoShape, ex:WarningShape .
            ex:InfoShape a sh:PropertyShape ;
                sh:path ex:required ;
                sh:minCount 1 ;
                sh:severity sh:Info .
            ex:WarningShape a sh:PropertyShape ;
                sh:path ex:required ;
                sh:minCount 1 ;
                sh:severity sh:Warning .
            "
        );
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();
        let parsed = shifty_parse::parse_loaded(&loaded);
        let normalized = shifty_opt::normalize(&parsed.schema);
        let plan = shifty_opt::plan(&normalized);

        let info = validate_plan_with_options(
            &loaded.graph,
            &plan,
            &ValidationOptions {
                minimum_severity: shifty_algebra::Severity::Info,
                sort_results: true,
                ..Default::default()
            },
        )
        .unwrap();
        assert!(!info.conforms);
        assert_eq!(info.violations.len(), 1);
        assert_eq!(
            info.violations[0].severity,
            shifty_algebra::Severity::Warning
        );
        let mut severities: Vec<_> = info.violations[0]
            .reasons
            .iter()
            .map(|reason| reason.severity.clone())
            .collect();
        severities.sort_by_key(shifty_algebra::Severity::rank);
        assert_eq!(
            severities,
            vec![
                shifty_algebra::Severity::Info,
                shifty_algebra::Severity::Warning
            ]
        );

        let warning = validate_plan_with_options(
            &loaded.graph,
            &plan,
            &ValidationOptions {
                minimum_severity: shifty_algebra::Severity::Warning,
                sort_results: true,
                ..Default::default()
            },
        )
        .unwrap();
        assert!(!warning.conforms);

        let violation = validate_plan_with_options(
            &loaded.graph,
            &plan,
            &ValidationOptions {
                minimum_severity: shifty_algebra::Severity::Violation,
                sort_results: true,
                ..Default::default()
            },
        )
        .unwrap();
        assert!(violation.conforms);
        assert_eq!(violation.violations.len(), 1);

        let report = validate_report_with_options(
            &loaded,
            &loaded.graph,
            &ValidationOptions {
                minimum_severity: shifty_algebra::Severity::Violation,
                sort_results: true,
                ..Default::default()
            },
        );
        assert!(report.conforms);
        assert_eq!(report.results.len(), 2);
    }

    #[test]
    fn validation_findings_sort_by_severity_then_focus_node() {
        let ttl = format!(
            "{PREFIXES}
            ex:InfoShape a sh:NodeShape ;
                sh:targetNode ex:a ;
                sh:nodeKind sh:Literal ;
                sh:severity sh:Info .
            ex:WarningShape a sh:NodeShape ;
                sh:targetNode ex:z ;
                sh:nodeKind sh:Literal ;
                sh:severity sh:Warning .
            ex:ViolationShape a sh:NodeShape ;
                sh:targetNode ex:m ;
                sh:nodeKind sh:Literal .
            "
        );
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();
        let parsed = shifty_parse::parse_loaded(&loaded);
        let plan = shifty_opt::plan(&shifty_opt::normalize(&parsed.schema));
        let outcome = validate_plan(&loaded.graph, &plan).unwrap();

        let ordered: Vec<_> = outcome
            .violations
            .iter()
            .map(|finding| (finding.severity.clone(), finding.focus.to_string()))
            .collect();
        assert_eq!(
            ordered,
            vec![
                (
                    shifty_algebra::Severity::Violation,
                    "<http://ex/m>".to_string()
                ),
                (
                    shifty_algebra::Severity::Warning,
                    "<http://ex/z>".to_string()
                ),
                (shifty_algebra::Severity::Info, "<http://ex/a>".to_string()),
            ]
        );
    }

    #[test]
    fn reports_specific_failing_constraints() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode ex:x ;
                sh:closed true ;
                sh:ignoredProperties ( rdf:type ) ;
                sh:property [ sh:path ex:age ; sh:datatype xsd:integer ; sh:maxCount 1 ] .
            ex:x ex:age \"foo\" , 5 ; ex:extra 1 .
            "
        );
        let outcome = run(&ttl);
        assert!(!outcome.conforms);
        assert_eq!(outcome.violations.len(), 1);
        let msgs: Vec<&str> = outcome.violations[0]
            .reasons
            .iter()
            .map(|r| r.message.as_str())
            .collect();
        // each distinct constraint is reported, not just "the node failed"
        assert!(
            msgs.iter().any(|m| m.contains("datatype(xsd:integer)")),
            "missing datatype reason: {msgs:?}"
        );
        assert!(
            msgs.iter().any(|m| m.contains("at most 1")),
            "missing maxCount reason: {msgs:?}"
        );
        assert!(
            msgs.iter()
                .any(|m| m.contains("closed") && m.contains("extra")),
            "missing closed reason: {msgs:?}"
        );
    }

    #[test]
    fn cardinality_and_datatype() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode ex:alice, ex:bob ;
                sh:property [ sh:path ex:age ; sh:maxCount 1 ; sh:datatype xsd:integer ] .
            ex:alice ex:age 30 .
            ex:bob   ex:age 30 ; ex:age 40 .
            "
        );
        let outcome = run(&ttl);
        assert!(!outcome.conforms);
        // only ex:bob violates maxCount 1
        let bad: Vec<_> = outcome
            .violations
            .iter()
            .map(|r| r.focus.to_string())
            .collect();
        assert_eq!(bad, vec!["<http://ex/bob>".to_string()]);
    }

    #[test]
    fn qualified_value_shape_disjoint_uses_all_sibling_property_shapes() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode ex:x ;
                sh:property ex:A, ex:B .
            ex:A a sh:PropertyShape ;
                sh:path ex:p ;
                sh:qualifiedValueShape [ sh:class ex:TypeA ] ;
                sh:qualifiedValueShapesDisjoint true ;
                sh:qualifiedMinCount 1 .
            ex:B a sh:PropertyShape ;
                sh:path ex:q ;
                sh:qualifiedValueShape [ sh:class ex:TypeB ] ;
                sh:qualifiedValueShapesDisjoint true ;
                sh:qualifiedMaxCount 10 .
            ex:x ex:p ex:value .
            ex:value a ex:TypeA, ex:TypeB .
            "
        );
        let parsed = parse_turtle(ttl.as_bytes(), None).unwrap();
        assert!(
            parsed.diagnostics.is_empty(),
            "diags: {:?}",
            parsed.diagnostics
        );
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();

        let algebra = validate(&loaded.graph, &parsed.schema).unwrap();
        assert!(!algebra.conforms);

        let report = validate_report(&loaded, &loaded.graph);
        assert!(!report.conforms);
        assert_eq!(report.results.len(), 1);
        assert_eq!(
            report.results[0].component.as_str(),
            "http://www.w3.org/ns/shacl#QualifiedMinCountConstraintComponent"
        );
    }

    #[test]
    fn disjoint_on_node_shape_uses_the_focus_node_as_the_value() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode ex:valid, ex:invalid ;
                sh:disjoint ex:p .
            ex:valid ex:p ex:other .
            ex:invalid ex:p ex:invalid .
            "
        );
        let parsed = parse_turtle(ttl.as_bytes(), None).unwrap();
        assert!(
            parsed.diagnostics.is_empty(),
            "diags: {:?}",
            parsed.diagnostics
        );
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();

        let algebra = validate(&loaded.graph, &parsed.schema).unwrap();
        assert!(!algebra.conforms);
        assert_eq!(algebra.violations.len(), 1);
        assert_eq!(
            algebra.violations[0].focus.to_string(),
            "<http://ex/invalid>"
        );

        let normalized = shifty_opt::normalize(&parsed.schema);
        let plan = shifty_opt::plan(&normalized);
        let planned = validate_plan(&loaded.graph, &plan).unwrap();
        assert_eq!(planned.conforms, algebra.conforms);
        assert_eq!(planned.violations.len(), algebra.violations.len());

        let report = validate_report(&loaded, &loaded.graph);
        assert!(!report.conforms);
        assert_eq!(report.results.len(), 1);
        assert_eq!(
            report.results[0].component.as_str(),
            "http://www.w3.org/ns/shacl#DisjointConstraintComponent"
        );
        assert_eq!(
            report.results[0].value.as_ref().map(ToString::to_string),
            Some("<http://ex/invalid>".to_string())
        );
    }

    #[test]
    fn expression_constraint_reports_non_true_values() {
        // The W3C booleans-001 shape: sh:expression sh:this over boolean foci.
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode true, false ;
                sh:expression sh:this .
            "
        );
        let parsed = parse_turtle(ttl.as_bytes(), None).unwrap();
        assert!(
            parsed.diagnostics.is_empty(),
            "diags: {:?}",
            parsed.diagnostics
        );
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();

        // algebra path: only the `false` focus violates.
        let algebra = validate(&loaded.graph, &parsed.schema).unwrap();
        assert!(!algebra.conforms);
        assert_eq!(algebra.violations.len(), 1);
        assert_eq!(
            algebra.violations[0].focus,
            oxrdf::Term::Literal(oxrdf::Literal::new_typed_literal(
                "false",
                oxrdf::vocab::xsd::BOOLEAN
            ))
        );

        // planned path agrees with the algebra oracle.
        let normalized = shifty_opt::normalize(&parsed.schema);
        let plan = shifty_opt::plan(&normalized);
        let planned = validate_plan(&loaded.graph, &plan).unwrap();
        assert_eq!(planned.conforms, algebra.conforms);
        assert_eq!(planned.violations.len(), algebra.violations.len());

        // W3C report path: one ExpressionConstraintComponent result, sh:value false.
        let report = validate_report(&loaded, &loaded.graph);
        assert!(!report.conforms);
        assert_eq!(report.results.len(), 1);
        let result = &report.results[0];
        assert_eq!(
            result.component.as_str(),
            "http://www.w3.org/ns/shacl#ExpressionConstraintComponent"
        );
        assert_eq!(result.path, None);
        assert_eq!(
            result.value.as_ref().map(ToString::to_string),
            Some("\"false\"^^<http://www.w3.org/2001/XMLSchema#boolean>".to_string())
        );
    }

    #[test]
    fn expression_constraint_with_path_and_filter() {
        // The expression traverses a path from the focus and filters the values
        // by a shape; only nodes passing the filter must (here, fail to) be true,
        // exercising Path + Filter node expressions on the report path.
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode ex:x ;
                sh:expression [
                    sh:filterShape [ sh:datatype xsd:boolean ] ;
                    sh:nodes [ sh:path ex:flag ] ;
                ] .
            ex:x ex:flag true, false, \"not-a-bool\" .
            "
        );
        let parsed = parse_turtle(ttl.as_bytes(), None).unwrap();
        assert!(
            parsed.diagnostics.is_empty(),
            "diags: {:?}",
            parsed.diagnostics
        );
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();

        // The boolean values that survive the filter are {true, false}; `false`
        // is the lone non-true value, so exactly one result, sh:value false.
        let report = validate_report(&loaded, &loaded.graph);
        assert!(!report.conforms);
        assert_eq!(report.results.len(), 1);
        assert_eq!(
            report.results[0].component.as_str(),
            "http://www.w3.org/ns/shacl#ExpressionConstraintComponent"
        );
        assert_eq!(
            report.results[0].value.as_ref().map(ToString::to_string),
            Some("\"false\"^^<http://www.w3.org/2001/XMLSchema#boolean>".to_string())
        );

        // algebra path agrees on (non-)conformance.
        let algebra = validate(&loaded.graph, &parsed.schema).unwrap();
        assert!(!algebra.conforms);
        assert_eq!(algebra.violations.len(), 1);
    }

    #[test]
    fn expression_constraint_with_function_is_diagnosed() {
        // A function application inside sh:expression cannot be evaluated by the
        // validation paths yet, so it is diagnosed rather than silently dropped.
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode ex:x ;
                sh:expression [ ex:fn ( sh:this ) ] .
            "
        );
        let parsed = parse_turtle(ttl.as_bytes(), None).unwrap();
        assert!(
            parsed
                .diagnostics
                .iter()
                .any(|d| d.message.contains("sh:expression")),
            "expected an unsupported-expression diagnostic, got: {:?}",
            parsed.diagnostics
        );
    }

    #[test]
    fn sparql_function_expression_evaluates() {
        // The W3C simpleSPARQLFunction shapes: a no-arg ASK function and a
        // two-argument SELECT function, called via dash:expression strings.
        let ttl = br#"
            @prefix sh: <http://www.w3.org/ns/shacl#> .
            @prefix ex: <http://ex/> .
            @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
            ex:booleanFunction a sh:SPARQLFunction ;
                sh:returnType xsd:boolean ;
                sh:ask "ASK { FILTER (true) }" .
            ex:withArguments a sh:SPARQLFunction ;
                sh:parameter [ sh:name "arg1" ; sh:path ex:arg1 ] ,
                             [ sh:name "arg2" ; sh:path ex:arg2 ] ;
                sh:returnType xsd:string ;
                sh:select "SELECT ?result WHERE { BIND (CONCAT($arg1, \"-\", $arg2) AS ?result) }" .
        "#;
        let loaded = shifty_parse::load_turtle(ttl, None).unwrap();

        let b = evaluate_function_expression(&loaded, "ex:booleanFunction()").unwrap();
        assert_eq!(b, Some(oxrdf::Term::Literal(oxrdf::Literal::from(true))));

        let s = evaluate_function_expression(&loaded, "ex:withArguments(\"A\", \"B\")").unwrap();
        assert_eq!(
            s,
            Some(oxrdf::Term::Literal(oxrdf::Literal::new_simple_literal(
                "A-B"
            )))
        );
    }

    #[test]
    fn sparql_function_called_from_sparql_constraint() {
        // A SHACL function is callable inside a sh:sparql constraint query: the
        // constraint flags values for which ex:isOk returns false.
        let ttl = br#"
            @prefix sh: <http://www.w3.org/ns/shacl#> .
            @prefix ex: <http://ex/> .
            @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
            ex:isOk a sh:SPARQLFunction ;
                sh:parameter [ sh:path ex:arg ] ;
                sh:returnType xsd:boolean ;
                sh:ask "ASK { FILTER (STR($arg) = \"ok\") }" .
            ex:S a sh:NodeShape ;
                sh:targetNode ex:x, ex:y ;
                sh:sparql [ sh:select """SELECT $this ?value WHERE {
                    $this <http://ex/val> ?value .
                    FILTER (! <http://ex/isOk>(?value))
                }""" ] .
            ex:x <http://ex/val> "ok" .
            ex:y <http://ex/val> "bad" .
        "#;
        let loaded = shifty_parse::load_turtle(ttl, None).unwrap();
        let report = validate_report(&loaded, &loaded.graph);
        assert!(!report.conforms);
        assert_eq!(report.results.len(), 1, "results: {:?}", report.results);
        assert_eq!(report.results[0].focus.to_string(), "<http://ex/y>");
        assert_eq!(
            report.results[0].value.as_ref().map(ToString::to_string),
            Some("\"bad\"".to_string())
        );
    }

    #[test]
    fn graph_reading_function_policy_gates_loud_failure() {
        // `ex:exists` reads the data graph, so from a SPARQL context it can only
        // be evaluated over an empty dataset. The UnsupportedPolicy decides what
        // happens when it is called from a sh:sparql constraint.
        let ttl = br#"
            @prefix sh: <http://www.w3.org/ns/shacl#> .
            @prefix ex: <http://ex/> .
            @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
            ex:exists a sh:SPARQLFunction ;
                sh:returnType xsd:boolean ;
                sh:ask "ASK { ?s <http://ex/marker> ?o }" .
            ex:S a sh:NodeShape ;
                sh:targetNode ex:x ;
                sh:sparql [ sh:select
                    "SELECT $this WHERE { $this a <http://ex/T> . FILTER (<http://ex/exists>()) }" ] .
            ex:x a <http://ex/T> .
            ex:y <http://ex/marker> "m" .
        "#;
        let loaded = shifty_parse::load_turtle(ttl, None).unwrap();

        // Ignore (default): the function runs over an empty dataset (best-effort);
        // here it returns false, so the constraint silently conforms.
        let lenient = validate_report(&loaded, &loaded.graph);
        assert!(lenient.conforms, "results: {:?}", lenient.results);

        // Error: the graph-reading function is not registered, so the SPARQL call
        // fails and the constraint fails closed (loud) rather than silently wrong.
        let strict_opts = ValidationOptions {
            engine: EngineOptions {
                unsupported: UnsupportedPolicy::Error,
            },
            ..Default::default()
        };
        let strict = validate_report_with_options(&loaded, &loaded.graph, &strict_opts);
        assert!(!strict.conforms);
        assert_eq!(strict.results.len(), 1, "results: {:?}", strict.results);
    }

    #[test]
    fn custom_component_ask_validator() {
        // A two-parameter ASK component (the W3C validator-001 shape): a value
        // conforms iff it is the concatenation of the two parameters.
        let ttl = br#"
            @prefix sh: <http://www.w3.org/ns/shacl#> .
            @prefix ex: <http://ex/> .
            ex:TestConstraintComponent a sh:ConstraintComponent ;
                sh:parameter [ sh:path ex:test1 ] , [ sh:path ex:test2 ] ;
                sh:validator [ a sh:SPARQLAskValidator ;
                    sh:ask "ASK { FILTER (?value = CONCAT($test1, $test2)) }" ] .
            ex:TestShape a sh:NodeShape ;
                ex:test1 "Hello " ;
                ex:test2 "World" ;
                sh:targetNode "Hallo Welt", "Hello World" .
        "#;
        let loaded = shifty_parse::load_turtle(ttl, None).unwrap();
        let report = validate_report(&loaded, &loaded.graph);
        assert!(!report.conforms);
        assert_eq!(report.results.len(), 1);
        let r = &report.results[0];
        assert_eq!(r.component.as_str(), "http://ex/TestConstraintComponent");
        assert_eq!(r.focus.to_string(), "\"Hallo Welt\"");
        assert_eq!(
            r.value.as_ref().map(ToString::to_string),
            Some("\"Hallo Welt\"".to_string())
        );
        assert_eq!(r.source_shape.to_string(), "<http://ex/TestShape>");
        assert_eq!(r.path, None);

        // The algebra path now evaluates components too: "Hallo Welt" should
        // still be the only violation.
        let parse_out = shifty_parse::parse_loaded(&loaded);
        let schema = shifty_opt::normalize(&parse_out.schema);
        let plan = shifty_opt::plan(&schema);
        let outcome = validate_plan_graphs(&loaded.graph, &loaded.graph, &plan).unwrap();
        assert!(!outcome.conforms, "algebra: Hallo Welt must still violate");
        assert_eq!(
            outcome.violations.len(),
            1,
            "algebra: exactly one violation: {:?}",
            outcome.violations
        );
        assert_eq!(
            outcome.violations[0].focus.to_string(),
            "\"Hallo Welt\"",
            "algebra: wrong focus node"
        );
    }

    #[test]
    fn custom_component_select_node_validator() {
        // A SELECT node validator with a required parameter: a focus violates
        // when it lacks an ex:property edge equal to the bound $requiredParam.
        let ttl = br#"
            @prefix sh: <http://www.w3.org/ns/shacl#> .
            @prefix ex: <http://ex/> .
            ex:C a sh:ConstraintComponent ;
                sh:parameter [ sh:path ex:requiredParam ] ;
                sh:nodeValidator [ a sh:SPARQLSelectValidator ;
                    sh:select """SELECT $this WHERE {
                        $this ?p ?o .
                        FILTER NOT EXISTS { $this <http://ex/property> $requiredParam }
                    }""" ] .
            ex:S a sh:NodeShape ;
                ex:requiredParam "Value" ;
                sh:targetNode ex:Good, ex:Bad .
            ex:Good <http://ex/property> "Value" .
            ex:Bad <http://ex/property> "Other" .
        "#;
        let loaded = shifty_parse::load_turtle(ttl, None).unwrap();
        let report = validate_report(&loaded, &loaded.graph);
        assert!(!report.conforms);
        assert_eq!(report.results.len(), 1);
        let r = &report.results[0];
        assert_eq!(r.component.as_str(), "http://ex/C");
        assert_eq!(r.focus.to_string(), "<http://ex/Bad>");
        assert_eq!(
            r.value.as_ref().map(ToString::to_string),
            Some("<http://ex/Bad>".to_string())
        );
    }

    #[test]
    fn custom_component_not_activated_when_mandatory_param_absent() {
        // The component is only activated for shapes that supply every mandatory
        // parameter; a shape missing it produces no results (and no diagnostic).
        let ttl = br#"
            @prefix sh: <http://www.w3.org/ns/shacl#> .
            @prefix ex: <http://ex/> .
            ex:C a sh:ConstraintComponent ;
                sh:parameter [ sh:path ex:requiredParam ] ;
                sh:validator [ a sh:SPARQLAskValidator ; sh:ask "ASK { FILTER (false) }" ] .
            ex:S a sh:NodeShape ;
                sh:targetNode ex:x .
            ex:x ex:other "z" .
        "#;
        let loaded = shifty_parse::load_turtle(ttl, None).unwrap();
        let report = validate_report(&loaded, &loaded.graph);
        assert!(report.conforms, "results: {:?}", report.results);

        let parsed = parse_turtle(ttl, None).unwrap();
        assert!(
            !parsed
                .diagnostics
                .iter()
                .any(|d| d.message.contains("custom constraint component")),
            "an inactive component must not be diagnosed: {:?}",
            parsed.diagnostics
        );
    }

    #[test]
    fn custom_component_property_validator_complex_path() {
        // A property shape with a *sequence* path activates a SELECT property
        // validator: `$PATH` is pre-bound to ex:a/ex:b, so the validator reaches
        // the value nodes two hops away and flags the forbidden one.
        let ttl = br#"
            @prefix sh: <http://www.w3.org/ns/shacl#> .
            @prefix ex: <http://ex/> .
            ex:ForbidComponent a sh:ConstraintComponent ;
                sh:parameter [ sh:path ex:forbidden ] ;
                sh:propertyValidator [ a sh:SPARQLSelectValidator ;
                    sh:select """SELECT $this ?value WHERE {
                        $this $PATH ?value .
                        FILTER (STR(?value) = STR($forbidden))
                    }""" ] .
            ex:S a sh:NodeShape ;
                sh:targetNode ex:x ;
                sh:property [ sh:path ( ex:a ex:b ) ; ex:forbidden "bad" ] .
            ex:x ex:a ex:m .
            ex:m ex:b "bad", "ok" .
        "#;
        let loaded = shifty_parse::load_turtle(ttl, None).unwrap();
        let report = validate_report(&loaded, &loaded.graph);
        assert!(!report.conforms);
        assert_eq!(report.results.len(), 1, "results: {:?}", report.results);
        let r = &report.results[0];
        assert_eq!(r.component.as_str(), "http://ex/ForbidComponent");
        assert_eq!(r.focus.to_string(), "<http://ex/x>");
        assert_eq!(
            r.value.as_ref().map(ToString::to_string),
            Some("\"bad\"".to_string())
        );
    }

    #[test]
    fn custom_component_property_validator_inverse_path() {
        // An inverse path `^ex:parent`: the value nodes are the subjects that
        // point at the focus via ex:parent. The ASK validator runs per value node
        // with `$PATH` pre-bound, flagging values whose label is not "ok".
        let ttl = br#"
            @prefix sh: <http://www.w3.org/ns/shacl#> .
            @prefix ex: <http://ex/> .
            ex:OkComponent a sh:ConstraintComponent ;
                sh:parameter [ sh:path ex:want ] ;
                sh:validator [ a sh:SPARQLAskValidator ;
                    sh:ask "ASK { $value <http://ex/label> $want }" ] .
            ex:S a sh:NodeShape ;
                sh:targetNode ex:p ;
                sh:property [ sh:path [ sh:inversePath ex:parent ] ; ex:want "ok" ] .
            ex:c1 ex:parent ex:p ; ex:label "ok" .
            ex:c2 ex:parent ex:p ; ex:label "no" .
        "#;
        let loaded = shifty_parse::load_turtle(ttl, None).unwrap();
        let report = validate_report(&loaded, &loaded.graph);
        // Value nodes of ex:p along ^ex:parent are {ex:c1, ex:c2}; only ex:c2
        // lacks `ex:label "ok"`, so the ASK is false there → one violation.
        assert!(!report.conforms);
        assert_eq!(report.results.len(), 1, "results: {:?}", report.results);
        assert_eq!(
            report.results[0].component.as_str(),
            "http://ex/OkComponent"
        );
        assert_eq!(
            report.results[0].value.as_ref().map(ToString::to_string),
            Some("<http://ex/c2>".to_string())
        );
    }

    #[test]
    fn custom_component_ask_validator_subquery_count() {
        // ASK validator that counts graph-wide instances of $class and checks
        // the total equals $exactCount (the BuildingMOTIF exactCount pattern).
        // The correct SPARQL uses a subquery to aggregate, then FILTER in the
        // outer query — avoiding the invalid `SELECT * … HAVING (aggregate)`
        // pattern that spargebra rightly rejects.
        let shapes_ttl = br#"
            @prefix sh:  <http://www.w3.org/ns/shacl#> .
            @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
            @prefix ex:  <urn:ex/> .

            ex:countComponent a sh:ConstraintComponent ;
                sh:parameter [ sh:path ex:exactCount ; sh:datatype xsd:integer ] ;
                sh:parameter [ sh:path ex:class ] ;
                sh:validator ex:hasExactCount .

            ex:hasExactCount a sh:SPARQLAskValidator ;
                sh:message "Wrong count" ;
                sh:ask """
                    ASK {
                        {
                            SELECT (COUNT(DISTINCT ?i) AS ?count)
                            WHERE { ?i a $class . }
                        }
                        FILTER (?count = $exactCount)
                    }
                """ .

            ex:shape a sh:NodeShape ;
                sh:targetNode ex:sentinel ;
                ex:class ex:Thing ;
                ex:exactCount 1 .
        "#;
        let shapes = shifty_parse::load_turtle(shapes_ttl, None).unwrap();

        // Zero instances → violates
        let data_none =
            shifty_parse::load_turtle(b"@prefix ex: <urn:ex/> . ex:sentinel a ex:Sentinel .", None)
                .unwrap();
        let report = validate_report_graphs(&shapes, &data_none.graph);
        assert!(
            !report.conforms,
            "zero Things with exactCount=1 must not conform: {:?}",
            report.results
        );

        // Exactly one instance → conforms
        let data_one = shifty_parse::load_turtle(
            b"@prefix ex: <urn:ex/> . ex:sentinel a ex:Sentinel . ex:t1 a ex:Thing .",
            None,
        )
        .unwrap();
        let report_ok = validate_report_graphs(&shapes, &data_one.graph);
        assert!(
            report_ok.conforms,
            "exactly one Thing with exactCount=1 must conform: {:?}",
            report_ok.results
        );

        // Two instances → violates
        let data_two = shifty_parse::load_turtle(
            b"@prefix ex: <urn:ex/> . ex:sentinel a ex:Sentinel . ex:t1 a ex:Thing . ex:t2 a ex:Thing .",
            None,
        )
        .unwrap();
        let report_two = validate_report_graphs(&shapes, &data_two.graph);
        assert!(
            !report_two.conforms,
            "two Things with exactCount=1 must not conform: {:?}",
            report_two.results
        );

        // Same checks via the algebra path.
        let parse_out = shifty_parse::parse_loaded(&shapes);
        let schema = shifty_opt::normalize(&parse_out.schema);
        let plan = shifty_opt::plan(&schema);
        let alg_none = validate_plan_graphs(&data_none.graph, &shapes.graph, &plan).unwrap();
        assert!(!alg_none.conforms, "algebra: zero Things must not conform");
        let alg_one = validate_plan_graphs(&data_one.graph, &shapes.graph, &plan).unwrap();
        assert!(alg_one.conforms, "algebra: one Thing must conform");
        let alg_two = validate_plan_graphs(&data_two.graph, &shapes.graph, &plan).unwrap();
        assert!(!alg_two.conforms, "algebra: two Things must not conform");
    }

    #[test]
    fn custom_component_invalid_sparql_ignored_by_default() {
        // A validator whose sh:ask is invalid SPARQL (SELECT * with an implicit
        // GROUP BY from HAVING) is silently skipped under the default Ignore
        // policy, so the component is not enforced and the shape appears to
        // conform even when the data does not.  This documents the known
        // silent-skip behaviour; use on_unsupported="error" to surface it.
        let shapes_ttl = br#"
            @prefix sh:  <http://www.w3.org/ns/shacl#> .
            @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
            @prefix ex:  <urn:ex/> .

            ex:badComponent a sh:ConstraintComponent ;
                sh:parameter [ sh:path ex:exactCount ; sh:datatype xsd:integer ] ;
                sh:parameter [ sh:path ex:class ] ;
                sh:validator [ a sh:SPARQLAskValidator ;
                    sh:ask """
                        ASK WHERE {
                            {
                                SELECT *
                                WHERE { ?i a $class . }
                                HAVING (COUNT(DISTINCT ?i) = $exactCount)
                            }
                        }
                    """ ] .

            ex:shape a sh:NodeShape ;
                sh:targetNode ex:sentinel ;
                ex:class ex:Thing ;
                ex:exactCount 1 .
        "#;
        let shapes = shifty_parse::load_turtle(shapes_ttl, None).unwrap();
        let data =
            shifty_parse::load_turtle(b"@prefix ex: <urn:ex/> . ex:sentinel a ex:Sentinel .", None)
                .unwrap();

        // Ignore policy (default): bad query silently skipped → appears to conform
        let report = validate_report_graphs(&shapes, &data.graph);
        assert!(
            report.conforms,
            "bad validator query silently skipped under Ignore: {:?}",
            report.results
        );
    }

    #[test]
    fn equals_on_node_shape_uses_the_focus_node_as_the_value() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode ex:valid, ex:extra, ex:missing ;
                sh:equals ex:p .
            ex:valid ex:p ex:valid .
            ex:extra ex:p ex:extra, ex:other .
            "
        );
        let parsed = parse_turtle(ttl.as_bytes(), None).unwrap();
        assert!(
            parsed.diagnostics.is_empty(),
            "diags: {:?}",
            parsed.diagnostics
        );
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();

        let algebra = validate(&loaded.graph, &parsed.schema).unwrap();
        assert!(!algebra.conforms);
        let mut foci: Vec<_> = algebra
            .violations
            .iter()
            .map(|violation| violation.focus.to_string())
            .collect();
        foci.sort();
        assert_eq!(
            foci,
            [
                "<http://ex/extra>".to_string(),
                "<http://ex/missing>".to_string()
            ]
        );

        let normalized = shifty_opt::normalize(&parsed.schema);
        let plan = shifty_opt::plan(&normalized);
        let planned = validate_plan(&loaded.graph, &plan).unwrap();
        assert_eq!(planned.conforms, algebra.conforms);
        assert_eq!(planned.violations.len(), algebra.violations.len());

        let report = validate_report(&loaded, &loaded.graph);
        assert!(!report.conforms);
        assert_eq!(report.results.len(), 2);
        assert!(report.results.iter().all(|result| result.component.as_str()
            == "http://www.w3.org/ns/shacl#EqualsConstraintComponent"));
    }

    #[test]
    fn datatype_violation() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode ex:x ;
                sh:property [ sh:path ex:p ; sh:datatype xsd:integer ] .
            ex:x ex:p \"hello\" .
            "
        );
        assert!(!run(&ttl).conforms);
    }

    #[test]
    fn nodekind_and_class_target() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetClass ex:Person ;
                sh:property [ sh:path ex:knows ; sh:nodeKind sh:IRI ] .
            ex:alice a ex:Person ; ex:knows ex:bob .
            ex:carol a ex:Person ; ex:knows \"notaniri\" .
            "
        );
        let outcome = run(&ttl);
        assert!(!outcome.conforms);
        let bad: Vec<_> = outcome
            .violations
            .iter()
            .map(|r| r.focus.to_string())
            .collect();
        assert_eq!(bad, vec!["<http://ex/carol>".to_string()]);
    }

    #[test]
    fn recursion_over_cyclic_data_terminates() {
        // S requires every ex:knows neighbour to also satisfy S; data is a cycle.
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode ex:a ;
                sh:property [ sh:path ex:knows ; sh:node ex:S ; sh:nodeKind sh:IRI ] .
            ex:a ex:knows ex:b .
            ex:b ex:knows ex:a .
            "
        );
        // Must terminate; with all-IRI neighbours it conforms under the
        // provisional cycle-breaking semantics.
        assert!(run(&ttl).conforms);
    }

    #[test]
    fn empty_graph_conforms() {
        let outcome = validate(&Graph::new(), &shifty_algebra::Schema::new()).unwrap();
        assert!(outcome.conforms);
    }

    #[test]
    fn non_stratifiable_schema_is_diagnosed() {
        // S := ¬∃p.S — recursion through negation; no defined 2-valued semantics.
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ;
                sh:targetNode ex:x ;
                sh:not [ sh:path ex:p ; sh:qualifiedValueShape ex:S ; sh:qualifiedMinCount 1 ] .
            ex:x ex:p ex:y .
            "
        );
        let out = parse_turtle(ttl.as_bytes(), None).unwrap();
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();
        assert!(validate(&loaded.graph, &out.schema).is_err());
    }

    fn triple(s: &str, p: &str, o: &str) -> oxrdf::Triple {
        use oxrdf::NamedNode;
        oxrdf::Triple::new(
            NamedNode::new(s).unwrap(),
            NamedNode::new(p).unwrap(),
            NamedNode::new(o).unwrap(),
        )
    }

    #[test]
    fn triple_rule_infers_from_path() {
        // copy each ex:knows value to ex:knows2
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ; sh:targetClass ex:Person ;
                sh:rule [ a sh:TripleRule ;
                    sh:subject sh:this ; sh:predicate ex:knows2 ;
                    sh:object [ sh:path ex:knows ] ] .
            ex:a a ex:Person ; ex:knows ex:b .
            "
        );
        let out = parse_turtle(ttl.as_bytes(), None).unwrap();
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();
        let outcome = infer(&loaded.graph, &out.schema).unwrap();
        assert_eq!(outcome.inferred.len(), 1);
        assert!(
            outcome
                .graph
                .contains(&triple("http://ex/a", "http://ex/knows2", "http://ex/b"))
        );
    }

    #[test]
    fn inference_reaches_a_fixpoint() {
        // ex:reaches := ex:knows ∪ (ex:knows / ex:reaches) — transitive closure
        // a→b→c, so a reaches c is derivable only after b reaches c.
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ; sh:targetClass ex:Person ;
                sh:rule [ a sh:TripleRule ;
                    sh:subject sh:this ; sh:predicate ex:reaches ;
                    sh:object [ sh:path [ sh:alternativePath ( ex:knows ( ex:knows ex:reaches ) ) ] ] ] .
            ex:a a ex:Person ; ex:knows ex:b .
            ex:b a ex:Person ; ex:knows ex:c .
            ex:c a ex:Person .
            "
        );
        let out = parse_turtle(ttl.as_bytes(), None).unwrap();
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();
        let outcome = infer(&loaded.graph, &out.schema).unwrap();
        assert!(
            outcome
                .graph
                .contains(&triple("http://ex/a", "http://ex/reaches", "http://ex/b"))
        );
        assert!(
            outcome
                .graph
                .contains(&triple("http://ex/b", "http://ex/reaches", "http://ex/c"))
        );
        // the fixpoint result: a reaches c (only via b reaches c)
        assert!(
            outcome
                .graph
                .contains(&triple("http://ex/a", "http://ex/reaches", "http://ex/c"))
        );
    }

    #[test]
    fn later_order_output_reactivates_an_earlier_rule() {
        let ttl = format!(
            "{PREFIXES}
            ex:S a sh:NodeShape ; sh:targetNode ex:x ;
                sh:rule [
                    a sh:TripleRule ; sh:order 0 ;
                    sh:subject sh:this ; sh:predicate ex:done ;
                    sh:object [ sh:path ex:ready ]
                ] ;
                sh:rule [
                    a sh:TripleRule ; sh:order 1 ;
                    sh:subject sh:this ; sh:predicate ex:ready ;
                    sh:object ex:y
                ] .
            "
        );
        let out = parse_turtle(ttl.as_bytes(), None).unwrap();
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();
        let outcome = infer(&loaded.graph, &out.schema).unwrap();

        assert!(
            outcome
                .graph
                .contains(&triple("http://ex/x", "http://ex/ready", "http://ex/y"))
        );
        assert!(
            outcome
                .graph
                .contains(&triple("http://ex/x", "http://ex/done", "http://ex/y"))
        );
    }

    #[test]
    fn inferred_triples_can_create_new_rule_targets() {
        let ttl = format!(
            "{PREFIXES}
            ex:Seed a sh:NodeShape ; sh:targetNode ex:x ;
                sh:rule [
                    a sh:TripleRule ;
                    sh:subject sh:this ; sh:predicate ex:eligible ;
                    sh:object ex:y
                ] .
            ex:Eligible a sh:NodeShape ; sh:targetSubjectsOf ex:eligible ;
                sh:rule [
                    a sh:TripleRule ;
                    sh:subject sh:this ; sh:predicate ex:classified ;
                    sh:object ex:yes
                ] .
            "
        );
        let out = parse_turtle(ttl.as_bytes(), None).unwrap();
        let loaded = shifty_parse::load_turtle(ttl.as_bytes(), None).unwrap();
        let outcome = infer(&loaded.graph, &out.schema).unwrap();

        assert!(outcome.graph.contains(&triple(
            "http://ex/x",
            "http://ex/classified",
            "http://ex/yes",
        )));
    }

    #[test]
    fn split_inference_uses_shapes_graph_as_rule_context() {
        let shapes_ttl = format!(
            "{PREFIXES}
            ex:InverseShape a sh:NodeShape ;
                sh:targetClass ex:Thing ;
                sh:rule [
                    a sh:SPARQLRule ;
                    sh:construct \"\"\"
                        CONSTRUCT {{ ?o ?inverse $this }}
                        WHERE {{
                            $this ?predicate ?o .
                            ?predicate ex:inverseOf ?inverse .
                        }}
                    \"\"\"
                ] .
            ex:p ex:inverseOf ex:q .
            "
        );
        let data_ttl = format!(
            "{PREFIXES}
            ex:a a ex:Thing ; ex:p ex:b .
            "
        );
        let shapes = shifty_parse::load_turtle(shapes_ttl.as_bytes(), None).unwrap();
        let parsed = shifty_parse::parse_loaded(&shapes);
        let data = shifty_parse::load_turtle(data_ttl.as_bytes(), None).unwrap();

        let outcome = infer_graphs(&data.graph, &shapes.graph, &parsed.schema).unwrap();

        assert!(
            outcome
                .graph
                .contains(&triple("http://ex/b", "http://ex/q", "http://ex/a"))
        );
        assert_eq!(outcome.inferred.len(), 1);
    }
}