bc_envelope/base/

digest.rs

use std::{collections::HashSet, cell::RefCell, borrow::Cow};

use bc_components::{Digest, DigestProvider};

use crate::Envelope;

use super::{walk::EdgeType, envelope::EnvelopeCase};

/// Support for calculating the digests associated with `Envelope`.
///
/// Envelopes implement the `DigestProvider` trait, which means they can provide
/// cryptographic digests of their contents. This is a fundamental feature of
/// Gordian Envelope that enables privacy-enhancing features like selective disclosure
/// through elision while maintaining verifiable integrity.
impl DigestProvider for Envelope {
    /// Returns the envelope's digest.
    ///
    /// The digest of an envelope uniquely identifies its semantic content, regardless
    /// of whether parts of it are elided, encrypted, or compressed. This is a key property
    /// that enables privacy features while maintaining integrity.
    ///
    /// Two envelopes with the same digest are considered semantically equivalent - they
    /// represent the same information, even if parts of one envelope are elided or obscured.
    ///
    /// # Returns
    ///
    /// A borrowed reference to the digest if it's already computed and stored in the envelope,
    /// or a newly computed digest if needed.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bc_envelope::prelude::*;
    /// # use bc_components::DigestProvider;
    /// let envelope = Envelope::new("Hello.");
    /// let elided = envelope.elide();
    /// 
    /// // Even though the content is elided, the digests match
    /// assert_eq!(envelope.digest(), elided.digest());
    /// ```
    fn digest(&self) -> Cow<'_, Digest> {
        match self.case() {
            EnvelopeCase::Node { digest, .. } => Cow::Borrowed(digest),
            EnvelopeCase::Leaf { digest, .. } => Cow::Borrowed(digest),
            EnvelopeCase::Wrapped { digest, .. } => Cow::Borrowed(digest),
            EnvelopeCase::Assertion(assertion) => assertion.digest(),
            EnvelopeCase::Elided(digest) => Cow::Borrowed(digest),
            #[cfg(feature = "known_value")]
            EnvelopeCase::KnownValue { digest, .. } => Cow::Borrowed(digest),
            #[cfg(feature = "encrypt")]
            EnvelopeCase::Encrypted(encrypted_message) => encrypted_message.digest(),
            #[cfg(feature = "compress")]
            EnvelopeCase::Compressed(compressed) => compressed.digest(),
        }
    }
}

/// Support for working with the digest tree of an `Envelope`.
///
/// Gordian Envelope's structure includes a Merkle-like digest tree where each node
/// has a cryptographic digest representing its content. These methods help navigate
/// and utilize this digest tree.
impl Envelope {
    /// Returns the set of digests contained in the envelope's elements, down to the specified level.
    ///
    /// This method collects all digests from the envelope's structure up to a certain depth.
    /// It's extremely useful for selective elision or revelation, allowing you to
    /// gather digests of specific parts of the structure to target them for operations.
    ///
    /// # Parameters
    ///
    /// * `level_limit` - Maximum level depth to include (0 means no digests, `usize::MAX` means all digests)
    ///
    /// # Returns
    ///
    /// A `HashSet` containing all the digests in the envelope structure up to the specified level.
    /// The digest of the envelope itself and its subject are both included (if they differ).
    ///
    /// # Examples
    ///
    /// ```
    /// # use bc_envelope::prelude::*;
    /// let envelope = Envelope::new("Alice")
    ///     .add_assertion("name", "Alice Smith")
    ///     .add_assertion("age", 30);
    ///     
    /// // Level 0 returns an empty set
    /// assert_eq!(envelope.digests(0).len(), 0);
    /// 
    /// // Level 1 returns just the envelope's digest
    /// assert_eq!(envelope.digests(1).len(), 2); // Envelope and subject digests
    /// 
    /// // A deeper level includes assertion digests
    /// assert!(envelope.digests(3).len() > 4); // Includes assertions plus their predicates and objects
    /// ```
    pub fn digests(&self, level_limit: usize) -> HashSet<Digest> {
        let result = RefCell::new(HashSet::new());
        let visitor = |envelope: Self, level: usize, _: EdgeType, _: Option<&()>| -> _ {
            if level < level_limit {
                let mut result = result.borrow_mut();
                result.insert(envelope.digest().into_owned());
                result.insert(envelope.subject().digest().into_owned());
            }
            None
        };
        self.walk(false, &visitor);
        result.into_inner()
    }

    /// Returns the set of all digests in the envelope, at all levels.
    ///
    /// This is a convenience method that retrieves every digest in the envelope structure,
    /// no matter how deeply nested. It's useful when you need to work with the complete
    /// digest tree, such as when verifying integrity or preparing for comprehensive elision.
    ///
    /// # Returns
    ///
    /// A `HashSet` containing all digests in the envelope structure.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bc_envelope::prelude::*;
    /// let envelope = Envelope::new("Alice")
    ///     .add_assertion("name", "Alice Smith")
    ///     .add_assertion("age", 30)
    ///     .add_assertion("address", Envelope::new("Address")
    ///         .add_assertion("city", "Boston")
    ///         .add_assertion("zip", "02108"));
    ///     
    /// // Gets all digests from the entire structure
    /// let digests = envelope.deep_digests();
    /// 
    /// // This includes nested assertions digests
    /// assert!(digests.len() > 10);
    /// ```
    pub fn deep_digests(&self) -> HashSet<Digest> {
        self.digests(usize::MAX)
    }

    /// Returns the set of digests in the envelope, down to its second level only.
    ///
    /// This is a convenience method that retrieves just the top-level digests in the envelope,
    /// including the envelope itself, its subject, and its immediate assertions, but not
    /// deeper nested content. It's useful when you want to work with just the top-level
    /// structure without getting into nested details.
    ///
    /// # Returns
    ///
    /// A `HashSet` containing digests from the envelope's first two levels.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bc_envelope::prelude::*;
    /// let envelope = Envelope::new("Alice")
    ///     .add_assertion("name", "Alice Smith")
    ///     .add_assertion("address", Envelope::new("Address")
    ///         .add_assertion("city", "Boston")
    ///         .add_assertion("zip", "02108"));
    ///     
    /// // Gets just the shallow digests
    /// let shallow = envelope.shallow_digests();
    /// 
    /// // Gets all digests
    /// let deep = envelope.deep_digests();
    /// 
    /// // The shallow set is smaller than the deep set
    /// assert!(shallow.len() < deep.len());
    /// ```
    pub fn shallow_digests(&self) -> HashSet<Digest> {
        self.digests(2)
    }

    /// Returns a digest that captures the structural form of an envelope, not just its semantic content.
    ///
    /// While the regular `digest()` method provides a value for comparing semantic equivalence
    /// (whether two envelopes contain the same information), this method produces a digest
    /// that additionally captures the structural form of the envelope, including its 
    /// elision patterns, encryption, and compression.
    ///
    /// This allows distinguishing between envelopes that contain the same information
    /// but differ in how that information is structured or obscured.
    ///
    /// # Semantic vs. Structural Comparison
    ///
    /// - **Semantic equivalence** (using `digest()` or `is_equivalent_to()`) - Two envelopes
    ///   contain the same information in their unobscured form, complexity O(1)
    ///   
    /// - **Structural identity** (using `structural_digest()` or `is_identical_to()`) - Two envelopes
    ///   not only contain the same information but also have the same structure, including elision
    ///   patterns, encryption, compression, etc., complexity O(m + n) where m and n are the 
    ///   number of elements in each envelope
    ///
    /// # Returns
    ///
    /// A `Digest` that uniquely identifies the envelope's structure as well as its content.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bc_envelope::prelude::*;
    /// # use bc_components::DigestProvider;
    /// // Two envelopes with the same content but different structure
    /// let envelope1 = Envelope::new("Alice")
    ///     .add_assertion("name", "Alice Smith");
    ///     
    /// let envelope2 = Envelope::new("Alice")
    ///     .add_assertion("name", "Alice Smith")
    ///     .elide_removing_target(&Envelope::new("Alice"));
    ///     
    /// // They are semantically equivalent
    /// assert!(envelope1.is_equivalent_to(&envelope2));
    /// assert_eq!(envelope1.digest(), envelope2.digest());
    /// 
    /// // But they are structurally different
    /// assert!(!envelope1.is_identical_to(&envelope2));
    /// assert_ne!(envelope1.structural_digest(), envelope2.structural_digest());
    /// ```
    pub fn structural_digest(&self) -> Digest {
        let image = RefCell::new(Vec::new());
        let visitor = |envelope: Self, _: usize, _: EdgeType, _: Option<&()>| -> _ {
            // Add a discriminator to the image for the obscured cases.
            match envelope.case() {
                EnvelopeCase::Elided(_) => image.borrow_mut().push(1),
                #[cfg(feature = "encrypt")]
                EnvelopeCase::Encrypted(_) => image.borrow_mut().push(0),
                #[cfg(feature = "compress")]
                EnvelopeCase::Compressed(_) => image.borrow_mut().push(2),
                _ => {}
            }
            image.borrow_mut().extend_from_slice(envelope.digest().data());
            None
        };
        self.walk(false, &visitor);
        Digest::from_image(image.into_inner())
    }

    /// Tests if this envelope is semantically equivalent to another envelope.
    ///
    /// Two envelopes are semantically equivalent if they contain the same information
    /// in their unobscured form, even if they have different structures (e.g., one is
    /// partially elided and the other is not).
    ///
    /// This comparison has a complexity of O(1) as it simply compares the top-level digests.
    ///
    /// # Parameters
    ///
    /// * `other` - The other envelope to compare with
    ///
    /// # Returns
    ///
    /// `true` if the envelopes are semantically equivalent, `false` otherwise.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bc_envelope::prelude::*;
    /// // Create two envelopes with the same semantic content but different structure
    /// let original = Envelope::new("Hello world");
    /// let elided = original.elide();
    /// 
    /// // They are semantically equivalent (contain the same information)
    /// assert!(original.is_equivalent_to(&elided));
    /// 
    /// // But they have different structures
    /// assert!(!original.is_identical_to(&elided));
    /// ```
    pub fn is_equivalent_to(&self, other: &Self) -> bool {
        self.digest() == other.digest()
    }

    /// Tests if two envelopes are structurally identical.
    ///
    /// This function determines whether two envelopes are structurally identical.
    /// The comparison follows these rules:
    ///
    /// 1. If the envelopes are *not* semantically equivalent (different digests),
    ///    returns `false` - different content means they cannot be identical
    /// 
    /// 2. If the envelopes are semantically equivalent (same digests), then it
    ///    compares their structural digests to check if they have the same structure
    ///    (elision patterns, encryption, etc.)
    ///
    /// The comparison has a complexity of O(1) if the envelopes are not semantically
    /// equivalent, and O(m + n) if they are, where m and n are the number of elements
    /// in each envelope.
    ///
    /// # Parameters
    ///
    /// * `other` - The other envelope to compare with
    ///
    /// # Returns
    ///
    /// `true` if and only if the envelopes have both the same content (semantically equivalent)
    /// AND the same structure, `false` otherwise.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bc_envelope::prelude::*;
    /// // Two envelopes with identical structure
    /// let env1 = Envelope::new("Alice");
    /// let env2 = Envelope::new("Alice");
    /// let env3 = Envelope::new("Bob");
    ///     
    /// // Semantically different envelopes are not identical
    /// assert!(!env1.is_identical_to(&env3));
    /// 
    /// // Two envelopes with same content and structure are identical
    /// assert!(env1.is_identical_to(&env2));
    /// 
    /// // Envelopes with same content but different structure (one elided) are not identical
    /// let elided = env1.elide();
    /// assert!(env1.is_equivalent_to(&elided));  // semantically the same
    /// assert!(!env1.is_identical_to(&elided));  // but structurally different
    /// ```
    pub fn is_identical_to(&self, other: &Self) -> bool {
        if !self.is_equivalent_to(other) {
            return false;  // Different content means not identical
        }
        self.structural_digest() == other.structural_digest()
    }
}

/// Implementation of `PartialEq` for `Envelope` to allow for structural comparison.
///
/// This implements the `==` operator for envelopes using the `is_identical_to()`
/// method, which checks for both semantic equivalence and structural identity.
/// Following the corrected behavior of that method:
/// 
/// 1. Envelopes with different content (not semantically equivalent) are not equal (!=)
/// 2. Envelopes with the same content but different structure are not equal (!=)
/// 3. Only envelopes with both the same content and structure are equal (==)
///
/// Note that we deliberately do *not* also implement `Eq` as this comparison
/// for structural identity is potentially expensive (O(m + n) in the worst case),
/// and data structures like `HashMap` expect `Eq` to be a fast operation.
///
/// # Usage with Hash Maps and Sets
///
/// If you want to use envelopes as keys in hash-based collections like `HashMap`
/// or `HashSet`, you should pre-compute the envelope's `structural_digest()` and
/// use that as the key instead, as this will be more efficient.
///
/// # Examples
///
/// ```
/// # use bc_envelope::prelude::*;
/// let env1 = Envelope::new("Alice");
/// let env2 = Envelope::new("Alice");
/// let env3 = Envelope::new("Bob");
/// 
/// // Same content and structure are equal
/// assert!(env1 == env2);
/// 
/// // Different content means not equal
/// assert!(env1 != env3);
/// 
/// // Same content but different structure (one elided) are not equal
/// assert!(env1 != env1.elide());
/// ```
impl PartialEq for Envelope {
    /// Compares two envelopes for structural identity.
    ///
    /// This is equivalent to calling `self.is_identical_to(other)`.
    fn eq(&self, other: &Self) -> bool {
        self.is_identical_to(other)
    }
}