relmath/

annotated.rs

//! Additive annotation-domain and annotated-relation foundations.
//!
//! In this G4 slice, an annotation is a value combined by semiring-like
//! operations and stored in a deterministic annotated relation. Facts are kept
//! in a `BTreeMap`, so iteration order follows fact order. Only non-zero
//! annotations are stored; exact support materialization forgets annotation
//! values and keeps only the facts whose stored annotation is not zero.
//!
//! Unlike [`crate::provenance`], this module does not model witness sets or
//! explanation queries. An annotation here is the stored algebraic value for a
//! fact, not a derivation witness. Relation-level exact support materialization
//! for annotated surfaces is also available generically through
//! [`crate::ExactSupport`].
//!
//! Ordinary exact relations correspond to the boolean semiring, where `false`
//! means absence, `true` means presence, `add` models union-like combination,
//! and `mul` models composition-like chaining.

use std::collections::BTreeMap;

use crate::{
    BinaryRelation, NaryRelation, NaryRelationError, UnaryRelation, traits::FiniteRelation,
};

/// Semiring-like annotation domain for additive relation semantics.
///
/// This trait captures the smallest G4 foundation currently needed by the
/// crate:
///
/// - `zero` models absence or additive identity;
/// - `one` models multiplicative identity;
/// - `add` models union-like combination;
/// - `mul` models composition-like chaining.
///
/// In later annotated relation layers, materializing exact support should keep
/// tuples whose annotation is not zero and forget the annotation value itself.
///
/// # Examples
///
/// ```rust
/// use relmath::annotated::{BooleanSemiring, Semiring};
///
/// fn reachable_via_two_hop_or_direct(
///     direct: BooleanSemiring,
///     first_leg: BooleanSemiring,
///     second_leg: BooleanSemiring,
/// ) -> BooleanSemiring {
///     direct.add(&first_leg.mul(&second_leg))
/// }
///
/// let reachable = reachable_via_two_hop_or_direct(
///     BooleanSemiring::FALSE,
///     BooleanSemiring::TRUE,
///     BooleanSemiring::TRUE,
/// );
///
/// assert!(reachable.is_one());
/// assert!(bool::from(reachable));
/// ```
pub trait Semiring: Clone + Eq {
    /// Returns the additive identity for the annotation domain.
    #[must_use]
    fn zero() -> Self;

    /// Returns the multiplicative identity for the annotation domain.
    #[must_use]
    fn one() -> Self;

    /// Combines two annotations with union-like or choice-like semantics.
    #[must_use]
    fn add(&self, rhs: &Self) -> Self;

    /// Combines two annotations with chaining or composition-like semantics.
    #[must_use]
    fn mul(&self, rhs: &Self) -> Self;

    /// Returns `true` when this annotation is the additive identity.
    #[must_use]
    fn is_zero(&self) -> bool {
        self == &Self::zero()
    }

    /// Returns `true` when this annotation is the multiplicative identity.
    #[must_use]
    fn is_one(&self) -> bool {
        self == &Self::one()
    }
}

/// Deterministic annotated facts over a semiring-like annotation domain.
///
/// `AnnotatedRelation<F, A>` stores at most one annotation per fact. Repeated
/// insertion of the same fact combines annotations by `Semiring::add` in
/// insertion order. Only non-zero annotations are stored, so exact support is
/// the set of facts whose current annotation is not zero.
///
/// Inserting a zero annotation for an absent fact does nothing. Inserting a
/// zero annotation for a present fact also leaves the stored annotation
/// unchanged because zero is the additive identity. If a custom annotation
/// domain combines to zero, the fact is removed from the annotated relation.
/// Unlike provenance in [`crate::provenance`], the stored value is the
/// annotation itself rather than a witness or explanation set.
///
/// This first annotated relation slice focuses on deterministic storage,
/// inspection, and exact support materialization. Annotated set algebra,
/// annotated composition, temporal semantics, and broader uncertainty
/// operators remain later work.
///
/// # Examples
///
/// ```rust
/// use relmath::{
///     BinaryRelation,
///     annotated::{AnnotatedRelation, Semiring},
/// };
///
/// #[derive(Clone, 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))
///     }
/// }
///
/// let mut assignments = AnnotatedRelation::new();
///
/// assert!(assignments.insert(("Alice", "Review"), Count(1)));
/// assert!(assignments.insert(("Alice", "Review"), Count(2)));
/// assert_eq!(
///     assignments.annotation_of(&("Alice", "Review")),
///     Some(&Count(3))
/// );
///
/// let support: BinaryRelation<_, _> = assignments.to_binary_relation();
/// assert_eq!(support.to_vec(), vec![("Alice", "Review")]);
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct AnnotatedRelation<F: Ord, A: Semiring> {
    facts: BTreeMap<F, A>,
}

impl<F: Ord, A: Semiring> AnnotatedRelation<F, A> {
    /// Creates an empty annotated relation.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::{AnnotatedRelation, BooleanSemiring};
    /// use relmath::FiniteRelation;
    ///
    /// let relation = AnnotatedRelation::<(&str, &str), BooleanSemiring>::new();
    ///
    /// assert!(relation.is_empty());
    /// ```
    #[must_use]
    pub fn new() -> Self {
        Self {
            facts: BTreeMap::new(),
        }
    }

    /// Creates an annotated relation from `(fact, annotation)` entries.
    ///
    /// Repeated facts combine annotations by `Semiring::add` in iterator order.
    /// Entries with zero annotations do not create stored support.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::{AnnotatedRelation, BooleanSemiring};
    ///
    /// let relation = AnnotatedRelation::from_facts([
    ///     (("alice", "read"), BooleanSemiring::TRUE),
    ///     (("alice", "read"), BooleanSemiring::FALSE),
    ///     (("bob", "approve"), BooleanSemiring::FALSE),
    /// ]);
    ///
    /// assert!(relation.contains_fact(&("alice", "read")));
    /// assert!(!relation.contains_fact(&("bob", "approve")));
    /// ```
    #[must_use]
    pub fn from_facts<I>(facts: I) -> Self
    where
        I: IntoIterator<Item = (F, A)>,
    {
        facts.into_iter().collect()
    }

    /// Inserts one annotation for a fact.
    ///
    /// Returns `true` when the stored support or stored annotation changes.
    ///
    /// Repeated facts combine as `current.add(&annotation)`. Facts whose
    /// resulting annotation is zero are removed from the relation.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::{AnnotatedRelation, BooleanSemiring};
    ///
    /// let mut relation = AnnotatedRelation::new();
    ///
    /// assert!(!relation.insert(("alice", "read"), BooleanSemiring::FALSE));
    /// assert!(relation.insert(("alice", "read"), BooleanSemiring::TRUE));
    /// assert!(!relation.insert(("alice", "read"), BooleanSemiring::FALSE));
    /// assert!(relation.contains_fact(&("alice", "read")));
    /// ```
    pub fn insert(&mut self, fact: F, annotation: A) -> bool {
        match self.facts.entry(fact) {
            std::collections::btree_map::Entry::Vacant(entry) => {
                if annotation.is_zero() {
                    return false;
                }

                entry.insert(annotation);
                true
            }
            std::collections::btree_map::Entry::Occupied(mut entry) => {
                let combined = entry.get().add(&annotation);

                if combined.is_zero() {
                    entry.remove();
                    true
                } else if entry.get() == &combined {
                    false
                } else {
                    *entry.get_mut() = combined;
                    true
                }
            }
        }
    }

    /// Returns `true` when the relation contains the given fact with a
    /// non-zero annotation.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::{AnnotatedRelation, BooleanSemiring};
    ///
    /// let relation = AnnotatedRelation::from_facts([
    ///     (("alice", "read"), BooleanSemiring::TRUE),
    ///     (("bob", "approve"), BooleanSemiring::FALSE),
    /// ]);
    ///
    /// assert!(relation.contains_fact(&("alice", "read")));
    /// assert!(!relation.contains_fact(&("bob", "approve")));
    /// ```
    #[must_use]
    pub fn contains_fact(&self, fact: &F) -> bool {
        self.facts.contains_key(fact)
    }

    /// Returns the stored annotation for one fact.
    ///
    /// When a fact is absent, this returns `None`. Zero annotations are not
    /// stored, so `None` also means there is no stored exact support for that
    /// fact. Unlike [`crate::provenance::ProvenanceRelation::why`], this
    /// returns the stored annotation value itself rather than a witness set.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::{AnnotatedRelation, BooleanSemiring};
    ///
    /// let relation = AnnotatedRelation::from_facts([
    ///     (("alice", "read"), BooleanSemiring::TRUE),
    ///     (("bob", "approve"), BooleanSemiring::FALSE),
    /// ]);
    ///
    /// assert_eq!(
    ///     relation.annotation_of(&("alice", "read")),
    ///     Some(&BooleanSemiring::TRUE)
    /// );
    /// assert_eq!(relation.annotation_of(&("bob", "approve")), None);
    /// ```
    #[must_use]
    pub fn annotation_of(&self, fact: &F) -> Option<&A> {
        self.facts.get(fact)
    }

    /// Returns an iterator over facts and annotations in deterministic fact
    /// order.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::{AnnotatedRelation, BooleanSemiring};
    ///
    /// let relation = AnnotatedRelation::from_facts([
    ///     (("alice", "admin"), BooleanSemiring::TRUE),
    ///     (("bob", "reviewer"), BooleanSemiring::TRUE),
    /// ]);
    ///
    /// assert_eq!(
    ///     relation
    ///         .iter()
    ///         .map(|(fact, annotation)| (*fact, *annotation))
    ///         .collect::<Vec<_>>(),
    ///     vec![
    ///         (("alice", "admin"), BooleanSemiring::TRUE),
    ///         (("bob", "reviewer"), BooleanSemiring::TRUE),
    ///     ]
    /// );
    /// ```
    pub fn iter(&self) -> impl Iterator<Item = (&F, &A)> {
        self.facts.iter()
    }

    /// Returns the exact support relation of stored facts as a unary relation.
    ///
    /// This materialization forgets annotation values and keeps only which
    /// facts are currently present with a non-zero annotation. Generic code
    /// can access the same relation-level boundary through
    /// [`crate::ExactSupport::exact_support`].
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::{AnnotatedRelation, BooleanSemiring};
    ///
    /// let relation = AnnotatedRelation::from_facts([
    ///     (("alice", "admin"), BooleanSemiring::TRUE),
    ///     (("bob", "reviewer"), BooleanSemiring::TRUE),
    ///     (("bob", "reviewer"), BooleanSemiring::FALSE),
    /// ]);
    ///
    /// assert_eq!(
    ///     relation.support().to_vec(),
    ///     vec![("alice", "admin"), ("bob", "reviewer")]
    /// );
    /// ```
    #[must_use]
    pub fn support(&self) -> UnaryRelation<F>
    where
        F: Clone,
    {
        self.facts.keys().cloned().collect()
    }
}

impl<F: Ord, A: Semiring> Default for AnnotatedRelation<F, A> {
    fn default() -> Self {
        Self::new()
    }
}

impl<F: Ord, A: Semiring> FiniteRelation for AnnotatedRelation<F, A> {
    fn len(&self) -> usize {
        self.facts.len()
    }
}

impl<F: Ord, A: Semiring> FromIterator<(F, A)> for AnnotatedRelation<F, A> {
    fn from_iter<I: IntoIterator<Item = (F, A)>>(iter: I) -> Self {
        let mut relation = Self::new();
        relation.extend(iter);
        relation
    }
}

impl<F: Ord, A: Semiring> Extend<(F, A)> for AnnotatedRelation<F, A> {
    fn extend<I: IntoIterator<Item = (F, A)>>(&mut self, iter: I) {
        for (fact, annotation) in iter {
            self.insert(fact, annotation);
        }
    }
}

impl<T: Ord + Clone, A: Semiring> AnnotatedRelation<T, A> {
    /// Converts scalar facts into a unary relation support set.
    ///
    /// Generic code can access the same unary materialization boundary through
    /// [`crate::ToExactUnaryRelation`].
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::{AnnotatedRelation, BooleanSemiring};
    ///
    /// let concepts = AnnotatedRelation::from_facts([
    ///     ("Closure", BooleanSemiring::TRUE),
    ///     ("Relations", BooleanSemiring::TRUE),
    /// ]);
    ///
    /// assert_eq!(
    ///     concepts.to_unary_relation().to_vec(),
    ///     vec!["Closure", "Relations"]
    /// );
    /// ```
    #[must_use]
    pub fn to_unary_relation(&self) -> UnaryRelation<T> {
        self.support()
    }
}

impl<A0: Ord + Clone, B0: Ord + Clone, A: Semiring> AnnotatedRelation<(A0, B0), A> {
    /// Converts pair facts into a binary relation support set.
    ///
    /// Generic code can access the same binary materialization boundary
    /// through [`crate::ToExactBinaryRelation`].
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::{AnnotatedRelation, BooleanSemiring};
    ///
    /// let permissions = AnnotatedRelation::from_facts([
    ///     (("Alice", "read"), BooleanSemiring::TRUE),
    ///     (("Bob", "approve"), BooleanSemiring::TRUE),
    /// ]);
    ///
    /// assert_eq!(
    ///     permissions.to_binary_relation().to_vec(),
    ///     vec![("Alice", "read"), ("Bob", "approve")]
    /// );
    /// ```
    #[must_use]
    pub fn to_binary_relation(&self) -> BinaryRelation<A0, B0> {
        self.facts.keys().cloned().collect()
    }
}

impl<T: Ord + Clone, A: Semiring> AnnotatedRelation<Vec<T>, A> {
    /// Converts row facts into an n-ary relation with the given schema.
    ///
    /// The explicit schema preserves the current exact n-ary boundary where row
    /// values do not themselves encode column names. This method reuses the
    /// current `NaryRelation` validation rules, so duplicate or blank column
    /// names and row-arity mismatches return `NaryRelationError`. Generic code
    /// can access the same n-ary materialization boundary through
    /// [`crate::ToExactNaryRelation`].
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::{AnnotatedRelation, BooleanSemiring};
    ///
    /// let completion = AnnotatedRelation::from_facts([
    ///     (vec!["Alice", "Math", "passed"], BooleanSemiring::TRUE),
    ///     (vec!["Bob", "Physics", "passed"], BooleanSemiring::TRUE),
    /// ]);
    ///
    /// let relation = completion
    ///     .to_nary_relation(["student", "course", "status"])
    ///     .expect("expected valid support relation");
    ///
    /// assert_eq!(
    ///     relation.to_rows(),
    ///     vec![
    ///         vec!["Alice", "Math", "passed"],
    ///         vec!["Bob", "Physics", "passed"],
    ///     ]
    /// );
    /// ```
    pub fn to_nary_relation<I, S>(&self, schema: I) -> Result<NaryRelation<T>, NaryRelationError>
    where
        I: IntoIterator<Item = S>,
        S: Into<String>,
    {
        NaryRelation::from_rows(schema, self.facts.keys().cloned())
    }
}

/// Boolean semiring for ordinary exact relation semantics.
///
/// `BooleanSemiring` is the first built-in annotation family in G4. It keeps
/// the exact meaning already used by the published unary, binary, and n-ary
/// relations:
///
/// - `false` is zero and represents absence;
/// - `true` is one and represents presence or identity;
/// - `add` uses logical OR;
/// - `mul` uses logical AND.
///
/// # Examples
///
/// ```rust
/// use relmath::annotated::{BooleanSemiring, Semiring};
///
/// let direct = BooleanSemiring::FALSE;
/// let first_leg = BooleanSemiring::TRUE;
/// let second_leg = BooleanSemiring::TRUE;
///
/// assert_eq!(direct.add(&first_leg), BooleanSemiring::TRUE);
/// assert_eq!(first_leg.mul(&second_leg), BooleanSemiring::TRUE);
/// assert!(BooleanSemiring::zero().is_zero());
/// assert!(BooleanSemiring::one().is_one());
/// ```
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct BooleanSemiring(bool);

impl BooleanSemiring {
    /// The additive identity and absence value for the boolean semiring.
    pub const FALSE: Self = Self(false);

    /// The multiplicative identity and present value for the boolean semiring.
    pub const TRUE: Self = Self(true);

    /// Creates a boolean semiring value from a raw boolean.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::BooleanSemiring;
    ///
    /// assert_eq!(BooleanSemiring::new(false), BooleanSemiring::FALSE);
    /// assert_eq!(BooleanSemiring::new(true), BooleanSemiring::TRUE);
    /// ```
    #[must_use]
    pub const fn new(value: bool) -> Self {
        Self(value)
    }

    /// Returns the raw boolean stored by this semiring value.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::annotated::BooleanSemiring;
    ///
    /// assert!(!BooleanSemiring::FALSE.value());
    /// assert!(BooleanSemiring::TRUE.value());
    /// ```
    #[must_use]
    pub const fn value(self) -> bool {
        self.0
    }
}

impl From<bool> for BooleanSemiring {
    fn from(value: bool) -> Self {
        Self::new(value)
    }
}

impl From<BooleanSemiring> for bool {
    fn from(value: BooleanSemiring) -> Self {
        value.value()
    }
}

impl Semiring for BooleanSemiring {
    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)
    }
}