relmath-rs 0.7.0

//! Integration tests for the first G4 annotation foundations.

use std::collections::BTreeSet;

use relmath::{
    FiniteRelation, NaryRelation, UnaryRelation,
    annotated::{AnnotatedRelation, BooleanSemiring, Semiring},
};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Count(u8);

impl Semiring for Count {
    fn zero() -> Self {
        Self(0)
    }

    fn one() -> Self {
        Self(1)
    }

    fn add(&self, rhs: &Self) -> Self {
        Self(self.0.saturating_add(rhs.0))
    }

    fn mul(&self, rhs: &Self) -> Self {
        Self(self.0.saturating_mul(rhs.0))
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Parity(bool);

impl Semiring for Parity {
    fn zero() -> Self {
        Self(false)
    }

    fn one() -> Self {
        Self(true)
    }

    fn add(&self, rhs: &Self) -> Self {
        Self(self.0 ^ rhs.0)
    }

    fn mul(&self, rhs: &Self) -> Self {
        Self(self.0 && rhs.0)
    }
}

fn reachable_via_two_hop_or_direct<S: Semiring>(direct: S, first_leg: S, second_leg: S) -> S {
    direct.add(&first_leg.mul(&second_leg))
}

#[test]
fn boolean_semiring_zero_and_one_match_exact_presence_and_identity() {
    let zero = BooleanSemiring::zero();
    let one = BooleanSemiring::one();

    assert_eq!(zero, BooleanSemiring::FALSE);
    assert_eq!(one, BooleanSemiring::TRUE);
    assert!(zero.is_zero());
    assert!(!zero.is_one());
    assert!(one.is_one());
    assert!(!one.is_zero());
    assert!(!bool::from(zero));
    assert!(bool::from(one));
}

#[test]
fn boolean_semiring_add_and_mul_follow_union_and_chaining_meaning() {
    assert_eq!(
        BooleanSemiring::FALSE.add(&BooleanSemiring::TRUE),
        BooleanSemiring::TRUE
    );
    assert_eq!(
        BooleanSemiring::TRUE.add(&BooleanSemiring::TRUE),
        BooleanSemiring::TRUE
    );
    assert_eq!(
        BooleanSemiring::TRUE.mul(&BooleanSemiring::TRUE),
        BooleanSemiring::TRUE
    );
    assert_eq!(
        BooleanSemiring::TRUE.mul(&BooleanSemiring::FALSE),
        BooleanSemiring::FALSE
    );

    let reachable = reachable_via_two_hop_or_direct(
        BooleanSemiring::FALSE,
        BooleanSemiring::TRUE,
        BooleanSemiring::TRUE,
    );
    assert_eq!(reachable, BooleanSemiring::TRUE);
}

#[test]
fn boolean_semiring_values_iterate_in_deterministic_order() {
    let ordered = BTreeSet::from([BooleanSemiring::TRUE, BooleanSemiring::FALSE])
        .into_iter()
        .collect::<Vec<_>>();

    assert_eq!(ordered, vec![BooleanSemiring::FALSE, BooleanSemiring::TRUE]);
}

#[test]
fn annotated_relations_combine_repeated_facts_and_iterate_in_fact_order() {
    let relation = AnnotatedRelation::from_facts([
        (("bob", "reviewer"), Count(1)),
        (("alice", "admin"), Count(2)),
        (("alice", "admin"), Count(3)),
        (("carol", "guest"), Count(0)),
    ]);

    assert_eq!(relation.len(), 2);
    assert!(relation.contains_fact(&("alice", "admin")));
    assert!(!relation.contains_fact(&("carol", "guest")));
    assert_eq!(relation.annotation_of(&("alice", "admin")), Some(&Count(5)));
    assert_eq!(
        relation
            .iter()
            .map(|(fact, annotation)| (*fact, *annotation))
            .collect::<Vec<_>>(),
        vec![
            (("alice", "admin"), Count(5)),
            (("bob", "reviewer"), Count(1)),
        ]
    );
}

#[test]
fn annotated_relations_treat_zero_as_absence_and_drop_zero_results() {
    let mut relation = AnnotatedRelation::<&str, Parity>::new();

    assert!(!relation.insert("draft", Parity::zero()));
    assert!(relation.annotation_of(&"draft").is_none());
    assert!(relation.insert("draft", Parity::one()));
    assert!(relation.contains_fact(&"draft"));
    assert!(relation.insert("draft", Parity::one()));
    assert!(!relation.contains_fact(&"draft"));
    assert!(relation.annotation_of(&"draft").is_none());
    assert!(relation.is_empty());
}

#[test]
fn boolean_annotated_relations_keep_or_semantics_and_skip_zero_support() {
    let relation = AnnotatedRelation::from_facts([
        (("alice", "read"), BooleanSemiring::TRUE),
        (("alice", "read"), BooleanSemiring::FALSE),
        (("bob", "approve"), BooleanSemiring::FALSE),
        (("carol", "review"), BooleanSemiring::TRUE),
    ]);

    assert_eq!(
        relation.annotation_of(&("alice", "read")),
        Some(&BooleanSemiring::TRUE)
    );
    assert_eq!(relation.annotation_of(&("bob", "approve")), None);
    assert_eq!(
        relation
            .iter()
            .map(|(fact, annotation)| (*fact, *annotation))
            .collect::<Vec<_>>(),
        vec![
            (("alice", "read"), BooleanSemiring::TRUE),
            (("carol", "review"), BooleanSemiring::TRUE),
        ]
    );
}

#[test]
fn annotated_relations_materialize_exact_unary_and_binary_support() {
    let concepts = AnnotatedRelation::from_facts([
        ("Relations", Count(1)),
        ("Closure", Count(2)),
        ("Relations", Count(3)),
    ]);

    assert_eq!(
        concepts.to_unary_relation().to_vec(),
        vec!["Closure", "Relations"]
    );

    let permissions = AnnotatedRelation::from_facts([
        (("alice", "read"), Count(2)),
        (("alice", "read"), Count(1)),
        (("bob", "approve"), Count(1)),
    ]);
    let support = permissions.to_binary_relation();

    assert_eq!(
        permissions.support().to_vec(),
        vec![("alice", "read"), ("bob", "approve")]
    );
    assert_eq!(
        support.image(&UnaryRelation::singleton("alice")).to_vec(),
        vec!["read"]
    );
}

#[test]
fn empty_annotated_relations_materialize_empty_exact_support() {
    let scalar = AnnotatedRelation::<&str, BooleanSemiring>::new();
    let pairs = AnnotatedRelation::<(&str, &str), BooleanSemiring>::new();
    let rows = AnnotatedRelation::<Vec<&str>, BooleanSemiring>::new();

    assert!(scalar.support().is_empty());
    assert!(pairs.to_binary_relation().is_empty());

    let relation = rows
        .to_nary_relation(["student", "course"])
        .expect("expected valid empty support relation");
    assert_eq!(
        relation.schema(),
        &["student".to_string(), "course".to_string()]
    );
    assert!(relation.is_empty());
}

#[test]
fn annotated_relations_materialize_exact_nary_support() {
    let completion = AnnotatedRelation::from_facts([
        (vec!["Alice", "Math", "passed"], Count(2)),
        (vec!["Bob", "Physics", "passed"], Count(1)),
        (vec!["Alice", "Math", "passed"], Count(1)),
    ]);

    let relation = completion
        .to_nary_relation(["student", "course", "status"])
        .expect("expected valid support relation");

    assert_eq!(
        relation,
        NaryRelation::from_rows(
            ["student", "course", "status"],
            [["Alice", "Math", "passed"], ["Bob", "Physics", "passed"],],
        )
        .expect("expected valid exact relation")
    );
}