relmath/

provenance.rs

//! Deterministic exact provenance support.
//!
//! In this first G3 slice, a provenance token or label is an explicit stable
//! identifier attached directly to a stored fact. A witness is the exact,
//! deterministic set of provenance tokens attached to one stored fact. A
//! derived tuple is a tuple produced by later inference or algebraic
//! derivation; this module does not compute derived tuples yet. The first
//! explanation query in this module is
//! [`crate::provenance::ProvenanceRelation::why`], which explains only stored
//! base facts. When a fact is absent, `why` returns `None` rather than an
//! empty [`crate::provenance::ProvenanceSet`]. No public rule API lives in
//! this module yet; the first least-fixed-point rule layer is still
//! documented as later G3 work. Relation-level exact support materialization
//! for provenance surfaces is also available generically through
//! [`crate::ExactSupport`].

use std::collections::{BTreeMap, BTreeSet};

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

/// Deterministic provenance tokens attached to one stored fact.
///
/// `ProvenanceSet<P>` is the user-visible witness for a fact in this first G3
/// slice. It is an exact `BTreeSet`-backed set of tokens or labels, not a
/// derivation DAG.
///
/// # Examples
///
/// ```rust
/// use relmath::provenance::{ProvenanceRelation, ProvenanceSet};
///
/// let empty = ProvenanceSet::<&str>::default();
/// assert!(empty.is_empty());
///
/// let evidence = ProvenanceRelation::from_facts([
///     (("BRCA1", "BreastCancer"), "paper_12"),
///     (("BRCA1", "BreastCancer"), "curated_panel"),
/// ]);
/// let witness = evidence
///     .why(&("BRCA1", "BreastCancer"))
///     .expect("expected explanation");
///
/// assert_eq!(witness.len(), 2);
/// assert!(witness.contains(&"paper_12"));
/// assert!(witness.contains_token(&"curated_panel"));
/// assert_eq!(
///     witness.iter().copied().collect::<Vec<_>>(),
///     vec!["curated_panel", "paper_12"]
/// );
/// assert_eq!(witness.to_vec(), vec!["curated_panel", "paper_12"]);
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ProvenanceSet<P: Ord> {
    tokens: BTreeSet<P>,
}

impl<P: Ord> ProvenanceSet<P> {
    /// Returns the number of provenance tokens in the set.
    #[must_use]
    pub fn len(&self) -> usize {
        self.tokens.len()
    }

    /// Returns `true` when the provenance set contains no tokens.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.tokens.is_empty()
    }

    /// Returns `true` when the set contains the given token.
    #[must_use]
    pub fn contains(&self, token: &P) -> bool {
        self.tokens.contains(token)
    }

    /// Returns `true` when the set contains the given provenance token.
    #[must_use]
    pub fn contains_token(&self, token: &P) -> bool {
        self.contains(token)
    }

    /// Returns an iterator over provenance tokens in deterministic order.
    pub fn iter(&self) -> impl Iterator<Item = &P> {
        self.tokens.iter()
    }

    /// Converts the provenance set into a sorted vector of tokens.
    #[must_use]
    pub fn to_vec(&self) -> Vec<P>
    where
        P: Clone,
    {
        self.tokens.iter().cloned().collect()
    }
}

impl<P: Ord> Default for ProvenanceSet<P> {
    fn default() -> Self {
        Self {
            tokens: BTreeSet::new(),
        }
    }
}

/// Deterministic exact provenance attached to stored facts.
///
/// `ProvenanceRelation<F, P>` maps each stored fact to a deterministic set of
/// provenance tokens. Repeated insertion of the same `(fact, token)` pair is
/// idempotent. Inserting a new token for an existing fact combines provenance
/// by exact set union.
///
/// In this first additive provenance slice, every stored fact is a base fact.
/// The module does not yet derive new tuples. [`Self::why`] explains stored
/// facts only; derived-tuple explanations and `why_not` queries remain later
/// work.
///
/// # Examples
///
/// ```rust
/// use relmath::{UnaryRelation, provenance::ProvenanceRelation};
///
/// let gene_disease = ProvenanceRelation::from_facts([
///     (("BRCA1", "BreastCancer"), "paper_12"),
///     (("BRCA1", "BreastCancer"), "curated_panel"),
///     (("TP53", "BreastCancer"), "paper_77"),
/// ]);
///
/// let supported = gene_disease.to_binary_relation();
/// let brca1 = UnaryRelation::singleton("BRCA1");
///
/// assert_eq!(supported.image(&brca1).to_vec(), vec!["BreastCancer"]);
/// assert_eq!(
///     gene_disease
///         .why(&("BRCA1", "BreastCancer"))
///         .expect("expected explanation")
///         .to_vec(),
///     vec!["curated_panel", "paper_12"]
/// );
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ProvenanceRelation<F: Ord, P: Ord> {
    facts: BTreeMap<F, ProvenanceSet<P>>,
}

impl<F: Ord, P: Ord> ProvenanceRelation<F, P> {
    /// Creates an empty provenance relation.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::provenance::ProvenanceRelation;
    ///
    /// let mut evidence = ProvenanceRelation::new();
    ///
    /// assert!(evidence.insert(("BRCA1", "BreastCancer"), "paper_12"));
    /// assert!(!evidence.insert(("BRCA1", "BreastCancer"), "paper_12"));
    /// assert!(evidence.contains_fact(&("BRCA1", "BreastCancer")));
    /// assert_eq!(
    ///     evidence
    ///         .provenance_of(&("BRCA1", "BreastCancer"))
    ///         .expect("expected explanation")
    ///         .to_vec(),
    ///     vec!["paper_12"]
    /// );
    /// ```
    #[must_use]
    pub fn new() -> Self {
        Self {
            facts: BTreeMap::new(),
        }
    }

    /// Creates a provenance relation from `(fact, token)` entries.
    ///
    /// Repeated facts accumulate tokens by exact set union.
    #[must_use]
    pub fn from_facts<I>(facts: I) -> Self
    where
        I: IntoIterator<Item = (F, P)>,
    {
        facts.into_iter().collect()
    }

    /// Inserts one provenance token for a fact.
    ///
    /// Returns `true` when the token was not already attached to the fact.
    pub fn insert(&mut self, fact: F, token: P) -> bool {
        self.facts.entry(fact).or_default().tokens.insert(token)
    }

    /// Returns `true` when the relation contains the given fact.
    #[must_use]
    pub fn contains_fact(&self, fact: &F) -> bool {
        self.facts.contains_key(fact)
    }

    /// Returns why `fact` is present in this provenance relation.
    ///
    /// When `fact` is present, the returned witness is the deterministic exact
    /// set of provenance tokens attached to that stored fact. When `fact` is
    /// absent, this returns `None`.
    ///
    /// In this first G3 slice, every stored fact is a base fact with at least
    /// one token, so `None` means the relation has no explanation for the fact
    /// because the fact is absent.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::provenance::ProvenanceRelation;
    ///
    /// let evidence = ProvenanceRelation::from_facts([
    ///     (("BRCA1", "BreastCancer"), "paper_12"),
    ///     (("BRCA1", "BreastCancer"), "curated_panel"),
    /// ]);
    ///
    /// let why = evidence
    ///     .why(&("BRCA1", "BreastCancer"))
    ///     .expect("expected explanation");
    ///
    /// assert!(why.contains_token(&"paper_12"));
    /// assert!(why.contains_token(&"curated_panel"));
    /// assert!(evidence.why(&("BRCA1", "Olaparib")).is_none());
    /// ```
    #[must_use]
    pub fn why(&self, fact: &F) -> Option<&ProvenanceSet<P>> {
        self.facts.get(fact)
    }

    /// Returns the deterministic provenance set for one fact.
    ///
    /// Prefer [`Self::why`] for explanation-oriented queries.
    #[must_use]
    pub fn provenance_of(&self, fact: &F) -> Option<&ProvenanceSet<P>> {
        self.why(fact)
    }

    /// Returns an iterator over facts and provenance in deterministic order.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::provenance::ProvenanceRelation;
    ///
    /// let evidence = ProvenanceRelation::from_facts([
    ///     (("BRCA1", "BreastCancer"), "paper_12"),
    ///     (("BRCA1", "BreastCancer"), "curated_panel"),
    ///     (("TP53", "BreastCancer"), "paper_77"),
    /// ]);
    ///
    /// assert_eq!(
    ///     evidence
    ///         .iter()
    ///         .map(|(fact, witness)| (*fact, witness.to_vec()))
    ///         .collect::<Vec<_>>(),
    ///     vec![
    ///         (("BRCA1", "BreastCancer"), vec!["curated_panel", "paper_12"]),
    ///         (("TP53", "BreastCancer"), vec!["paper_77"]),
    ///     ]
    /// );
    /// ```
    pub fn iter(&self) -> impl Iterator<Item = (&F, &ProvenanceSet<P>)> {
        self.facts.iter()
    }

    /// Returns the exact support relation of stored facts as a unary relation.
    ///
    /// This support forgets provenance and keeps only which facts are present.
    /// Generic code can access the same relation-level boundary through
    /// [`crate::ExactSupport::exact_support`].
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::provenance::ProvenanceRelation;
    ///
    /// let evidence = ProvenanceRelation::from_facts([
    ///     (("BRCA1", "BreastCancer"), "paper_12"),
    ///     (("BRCA1", "BreastCancer"), "curated_panel"),
    ///     (("TP53", "BreastCancer"), "paper_77"),
    /// ]);
    ///
    /// assert_eq!(
    ///     evidence.support().to_vec(),
    ///     vec![("BRCA1", "BreastCancer"), ("TP53", "BreastCancer")]
    /// );
    /// ```
    #[must_use]
    pub fn support(&self) -> UnaryRelation<F>
    where
        F: Clone,
    {
        self.facts.keys().cloned().collect()
    }
}

impl<F: Ord, P: Ord> Default for ProvenanceRelation<F, P> {
    fn default() -> Self {
        Self::new()
    }
}

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

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

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

impl<T: Ord + Clone, P: Ord> ProvenanceRelation<T, P> {
    /// 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::provenance::ProvenanceRelation;
    ///
    /// let concepts = ProvenanceRelation::from_facts([
    ///     ("Relations", "lecture_1"),
    ///     ("Relations", "worksheet"),
    ///     ("Closure", "lecture_2"),
    /// ]);
    ///
    /// assert_eq!(concepts.to_unary_relation().to_vec(), vec!["Closure", "Relations"]);
    /// ```
    #[must_use]
    pub fn to_unary_relation(&self) -> UnaryRelation<T> {
        self.support()
    }
}

impl<A: Ord + Clone, B: Ord + Clone, P: Ord> ProvenanceRelation<(A, B), P> {
    /// 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::provenance::ProvenanceRelation;
    ///
    /// let evidence = ProvenanceRelation::from_facts([
    ///     (("Alice", "Reader"), "directory"),
    ///     (("Bob", "Editor"), "directory"),
    /// ]);
    ///
    /// assert_eq!(
    ///     evidence.to_binary_relation().to_vec(),
    ///     vec![("Alice", "Reader"), ("Bob", "Editor")]
    /// );
    /// ```
    #[must_use]
    pub fn to_binary_relation(&self) -> BinaryRelation<A, B> {
        self.facts.keys().cloned().collect()
    }
}

impl<T: Ord + Clone, P: Ord> ProvenanceRelation<Vec<T>, P> {
    /// 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::provenance::ProvenanceRelation;
    ///
    /// let rows = ProvenanceRelation::from_facts([
    ///     (vec!["Alice", "Math", "passed"], "gradebook"),
    ///     (vec!["Alice", "Math", "passed"], "reviewed"),
    ///     (vec!["Bob", "Physics", "passed"], "gradebook"),
    /// ]);
    ///
    /// let relation = rows
    ///     .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())
    }
}