eidetica/entry/

mod.rs

//!
//! Defines the fundamental data unit (`Entry`) and related types.
//!
//! An `Entry` is the core, content-addressable building block of the database,
//! representing a snapshot of data in the main tree and potentially multiple named subtrees.
//! This module also defines the `ID` type and `RawData` type.

mod builder;
pub mod errors;
pub mod id;

#[cfg(test)]
mod tests;

use std::sync::OnceLock;

use serde::{Deserialize, Serialize};

pub use builder::EntryBuilder;
pub use errors::EntryError;
pub use id::ID;

use crate::{Result, auth::types::AuthInfo, constants::ROOT, store::StoreError};

use id::IdError;

/// Opaque payload bytes embedded in an `Entry`.
///
/// Each `Store` owns the format of its own payload (JSON, CBOR, raw binary, etc.);
/// the entry layer treats `RawData` as a byte string and does not interpret it.
///
/// Encoded as a CBOR byte string (major type 2) in DAG-CBOR for IPLD compatibility.
pub type RawData = Vec<u8>;

/// Helper to check if tree height is zero for serde skip_serializing_if
fn is_zero(h: &u64) -> bool {
    *h == 0
}

/// Internal representation of the main tree node within an `Entry`.
#[derive(Default, Clone, Debug, Serialize, Deserialize, PartialEq, Eq)]
pub(super) struct TreeNode {
    /// The ID of the root `Entry` of the tree this node belongs to.
    /// `None` for root entries (they are their own root).
    #[serde(skip_serializing_if = "Option::is_none")]
    pub root: Option<ID>,
    /// IDs of the parent `Entry`s in the main tree history.
    /// The vector is kept sorted in CID order (`ID`'s `Ord`, not lexicographic string order).
    pub parents: Vec<ID>,
    /// Serialized metadata associated with this `Entry` in the main tree.
    /// This data is metadata about this specific entry only and is not merged with other entries.
    ///
    /// Metadata is used to improve the efficiency of certain operations and for experimentation.
    ///
    /// Metadata is optional and may not be present in all entries. Future versions
    /// may extend metadata to include additional information.
    #[serde(default, skip_serializing_if = "Option::is_none", with = "serde_bytes")]
    pub metadata: Option<RawData>,
    /// Height of this entry in the tree DAG (longest path from root).
    /// Root entries have height 0, children have max(parent heights) + 1.
    #[serde(rename = "h", default, skip_serializing_if = "is_zero")]
    pub height: u64,
}

/// Internal representation of a named subtree node within an `Entry`.
#[derive(Default, Clone, Debug, Serialize, Deserialize, PartialEq, Eq)]
pub(super) struct SubTreeNode {
    /// The name of the subtree, analogous to a table name.
    /// Subtrees are _named_, and not identified by an ID.
    pub name: String,
    /// IDs of the parent `Entry`s specific to this subtree's history.
    /// The vector is kept sorted in CID order (`ID`'s `Ord`, not lexicographic string order).
    pub parents: Vec<ID>,
    /// Serialized data specific to this `Entry` within this named subtree.
    ///
    /// `None` indicates that this Entry participates in the subtree but makes no data changes.
    /// This is used when there is information needed for this subtree found somewhere else (e.g. the `_index`)
    ///
    /// `Some(data)` contains the actual serialized data for this subtree.
    #[serde(default, skip_serializing_if = "Option::is_none", with = "serde_bytes")]
    pub data: Option<RawData>,
    /// Height of this entry in the subtree DAG.
    ///
    /// `None` means the subtree inherits the tree's height (not serialized).
    /// `Some(h)` is an independent height for subtrees with their own strategy.
    #[serde(rename = "h", default, skip_serializing_if = "Option::is_none")]
    pub height: Option<u64>,
}

/// The fundamental unit of data in Eidetica, representing a finalized, immutable Database Entry.
///
/// An `Entry` represents a snapshot of data within a `Database` and potentially one or more named `Store`s.
/// It is content-addressable, meaning its `ID` is a cryptographic hash of its contents.
/// Entries form a Merkle-DAG (Directed Acyclic Graph) structure through parent references.
///
/// # Authentication
///
/// Each entry contains authentication information (`auth`, an [`AuthInfo`]) with:
/// - `signature`: Base64-encoded cryptographic signature (optional, allows unsigned entry creation)
/// - `key`: Authentication key reference path, either:
///   - A direct key ID defined in this tree's `_settings.auth`
///   - A delegation path as an ordered list of `{"key": "delegated_tree_1", "tips": ["A", "B"]}`
///     where the last element must contain only a `"key"` field
///
/// # Immutability
///
/// `Entry` instances are designed to be immutable once created. To create or modify entries,
/// use the `EntryBuilder` struct, which provides a mutable API for constructing entries.
/// Once an entry is built, its content cannot be changed, and its ID is deterministic
/// based on its content.
///
/// # Example
///
/// ```
/// # use eidetica::Entry;
///
/// // Create a new root entry (standalone entry that starts a new DAG)
/// let entry = Entry::root_builder()
///     .set_subtree_data("users", br#"{"user1":"data"}"#.to_vec())
///     .build()
///     .expect("Entry should build successfully");
///
/// // Access entry data
/// let id = entry.id(); // Calculate content-addressable ID
/// let user_data = entry.data("users").unwrap();
/// ```
///
/// # Builders
///
/// To create an `Entry`, use the associated `EntryBuilder`.
/// The preferred way to get an `EntryBuilder` is via the static methods
/// `Entry::builder()` for regular entries or `Entry::root_builder()` for new top-level tree roots.
///
/// ```
/// # use eidetica::entry::{Entry, ID, RawData};
/// # let root_id = ID::from_bytes("some_root_id");
/// # let data: RawData = b"{}".to_vec();
/// // For a regular entry:
/// let builder = Entry::builder(root_id);
///
/// // For a new top-level tree root:
/// let root_builder = Entry::root_builder();
/// ```
/// The current entry format version.
/// v0 indicates this is an unstable protocol subject to breaking changes.
pub const ENTRY_VERSION: u8 = 0;

/// Helper to check if version is default (0) for serde skip_serializing_if
fn is_v0(v: &u8) -> bool {
    *v == 0
}

/// Validates the entry version during deserialization.
fn validate_entry_version<'de, D>(deserializer: D) -> std::result::Result<u8, D::Error>
where
    D: serde::Deserializer<'de>,
{
    let version = u8::deserialize(deserializer)?;
    if version != ENTRY_VERSION {
        return Err(serde::de::Error::custom(format!(
            "unsupported Entry version {version}; only version {ENTRY_VERSION} is supported"
        )));
    }
    Ok(version)
}

/// Lazily-computed cache of an `Entry`'s content-addressable ID.
///
/// The ID is a pure function of the entry's DAG-CBOR encoding, so it can be computed
/// once and reused. The cache is derived state and deliberately invisible to everything
/// that observes an entry's content: it is skipped by serde (so it never reaches the wire
/// format or the hash input), ignored by equality, and hidden from `Debug`.
///
/// A clone carries the cached value, which is sound because an `Entry` exposes no in-place
/// mutation: content changes go through [`Entry::with_auth`], which consumes the entry and
/// returns a new one with a fresh cache.
#[derive(Clone, Default)]
struct IdCache(OnceLock<ID>);

impl IdCache {
    /// Return the cached ID, computing and storing it on first use.
    fn get_or_init(&self, compute: impl FnOnce() -> ID) -> &ID {
        self.0.get_or_init(compute)
    }
}

impl PartialEq for IdCache {
    fn eq(&self, _other: &Self) -> bool {
        true
    }
}

impl Eq for IdCache {}

impl std::fmt::Debug for IdCache {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str("IdCache")
    }
}

#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, Eq)]
pub struct Entry {
    /// Protocol version for this entry format.
    /// Used to verify that we support reading this entry.
    #[serde(
        rename = "_v",
        default,
        skip_serializing_if = "is_v0",
        deserialize_with = "validate_entry_version"
    )]
    version: u8,
    /// The main tree node data, including the root ID, parents in the main tree, and associated data.
    ///
    /// Scoped to this module so that a built entry's content cannot be mutated from
    /// elsewhere in the crate, which is what makes [`IdCache`] sound.
    pub(in crate::entry) tree: TreeNode,
    /// A collection of named subtrees this entry contains data for.
    /// The vector is kept sorted alphabetically by subtree name during the build process.
    ///
    /// Scoped for the same reason as [`Entry::tree`].
    pub(in crate::entry) subtrees: Vec<SubTreeNode>,
    /// Authentication information for this entry: the signature and the hint used to
    /// locate the key that produced it.
    ///
    /// Private so that changes go through [`Entry::with_auth`], which rebuilds the entry
    /// rather than mutating it in place. Serialized as `sig` to keep the wire format —
    /// and therefore every existing entry ID — unchanged.
    #[serde(rename = "sig")]
    auth: AuthInfo,
    /// Memoized content-addressable ID. Derived state; see [`IdCache`].
    #[serde(skip)]
    id_cache: IdCache,
}

impl Entry {
    /// Creates a new `EntryBuilder` for an entry associated with a specific tree root.
    /// This is a convenience method and preferred over calling `EntryBuilder::new()` directly.
    ///
    /// # Arguments
    /// * `root` - The `ID` of the root `Entry` of the tree this entry will belong to.
    pub fn builder(root: ID) -> EntryBuilder {
        EntryBuilder::new(root)
    }

    /// Creates a new `EntryBuilder` for a top-level (root) entry for a new tree.
    /// This is a convenience method and preferred over calling `EntryBuilder::new_top_level()` directly.
    ///
    /// Root entries have an empty string as their `root` ID and include a special ROOT subtree marker.
    /// This method is typically used when creating a new tree.
    pub fn root_builder() -> EntryBuilder {
        EntryBuilder::new_top_level()
    }

    /// Get the content-addressable ID of the entry.
    ///
    /// The ID is the CID of the DAG-CBOR serialized representation of the Entry.
    ///
    /// The result is memoized: the encoding and hash are computed on the first call and
    /// reused afterwards. Callers on hot paths (sorting, DAG traversal, map keys) can
    /// therefore call this freely instead of threading an ID alongside the entry.
    pub fn id(&self) -> ID {
        self.id_ref().clone()
    }

    /// Borrow the content-addressable ID of the entry.
    ///
    /// The same value [`Entry::id`] returns, without copying it out of the memo. An [`ID`]
    /// carries a fixed-size digest buffer, so comparison-heavy callers — sorting a slice of
    /// entries, scanning one for a match — avoid a copy per access by borrowing instead.
    pub fn id_ref(&self) -> &ID {
        self.id_cache.get_or_init(|| {
            let bytes = self
                .to_dagcbor()
                .expect("Failed to serialize entry to DAG-CBOR for ID");
            ID::from_dagcbor_bytes(bytes)
        })
    }

    /// Get the authentication information attached to this entry.
    pub fn auth(&self) -> &AuthInfo {
        &self.auth
    }

    /// Return this entry with its authentication information updated by `update`.
    ///
    /// Signature material is part of an entry's content, so the returned entry has a
    /// different ID from the receiver. Consuming `self` and returning a new value is what
    /// keeps that honest: an `Entry` is never mutated in place, so a memoized ID can never
    /// outlive the content it was computed from.
    ///
    /// ```
    /// # use eidetica::entry::Entry;
    /// # fn main() -> eidetica::Result<()> {
    /// let entry = Entry::root_builder().build()?;
    /// let signed = entry.with_auth(|auth| auth.signature = Some("c2lnbmF0dXJl".to_string()));
    /// # Ok(())
    /// # }
    /// ```
    pub fn with_auth(mut self, update: impl FnOnce(&mut AuthInfo)) -> Self {
        update(&mut self.auth);
        self.id_cache = IdCache::default();
        self
    }

    /// Get the ID of the root `Entry` of the tree this entry belongs to.
    /// Returns `None` for root entries.
    pub fn root(&self) -> Option<ID> {
        self.tree.root.clone()
    }

    /// Check if this entry is a root entry (contains the ROOT marker and has no parents).
    ///
    /// Root entries are the top-level entries in the database and are distinguished by:
    /// 1. Containing a subtree with the ROOT marker
    /// 2. Having no parent entries (they are true tree roots)
    ///
    /// This ensures that root entries are actual starting points of trees in the DAG.
    pub fn is_root(&self) -> bool {
        // FIXME: better identification of root entries
        self.subtrees.iter().any(|node| node.name == ROOT)
            && self.tree.parents.is_empty()
            && self.tree.root.is_none()
    }

    /// Check if this entry contains data for a specific named subtree.
    pub fn in_subtree(&self, subtree_name: impl AsRef<str>) -> bool {
        self.subtrees
            .iter()
            .any(|node| node.name == subtree_name.as_ref())
    }

    /// Check if this entry belongs to a specific tree, identified by its root ID.
    pub fn in_tree(&self, tree_id: &ID) -> bool {
        // Entries that are roots exist in both trees
        self.tree.root.as_ref() == Some(tree_id) || self.id() == *tree_id
    }

    /// Get the names of all subtrees this entry contains data for.
    /// The names are returned in alphabetical order.
    pub fn subtrees(&self) -> Vec<String> {
        self.subtrees
            .iter()
            .map(|subtree| subtree.name.clone())
            .collect()
    }

    /// Get the metadata associated with this entry's tree node.
    ///
    /// Metadata is optional information attached to an entry that is not part of the
    /// main data model and is not merged between entries.
    pub fn metadata(&self) -> Option<&RawData> {
        self.tree.metadata.as_ref()
    }

    /// Get the `RawData` for a specific named subtree within this entry.
    ///
    /// Returns an error if the subtree is not found or if the subtree exists but has no data (`None`).
    pub fn data(&self, subtree_name: impl AsRef<str>) -> Result<&RawData> {
        self.subtrees
            .iter()
            .find(|node| node.name == subtree_name.as_ref())
            .and_then(|node| node.data.as_ref())
            .ok_or_else(|| {
                StoreError::KeyNotFound {
                    store: "entry".to_string(),
                    key: subtree_name.as_ref().to_string(),
                }
                .into()
            })
    }

    /// Get the IDs of the parent entries in the main tree history.
    /// The parent IDs are returned in CID order (`ID`'s `Ord`, not lexicographic string order).
    pub fn parents(&self) -> Result<Vec<ID>> {
        Ok(self.tree.parents.clone())
    }

    /// Get the IDs of the parent entries specific to a named subtree's history.
    /// The parent IDs are returned in CID order (`ID`'s `Ord`, not lexicographic string order).
    pub fn subtree_parents(&self, subtree_name: impl AsRef<str>) -> Result<Vec<ID>> {
        self.subtrees
            .iter()
            .find(|node| node.name == subtree_name.as_ref())
            .map(|node| node.parents.clone())
            .ok_or_else(|| {
                StoreError::KeyNotFound {
                    store: "entry".to_string(),
                    key: subtree_name.as_ref().to_string(),
                }
                .into()
            })
    }

    /// Get the height of this entry in the main tree DAG.
    pub fn height(&self) -> u64 {
        self.tree.height
    }

    /// Get the height of this entry in a specific subtree's DAG.
    ///
    /// If the subtree has an explicit height (`Some(h)`), that value is returned.
    /// If the subtree height is `None`, it inherits from the main tree height.
    ///
    /// This allows subtrees to either track independent heights (for subtrees
    /// with their own height strategy) or share the tree's height (default).
    pub fn subtree_height(&self, subtree_name: impl AsRef<str>) -> Result<u64> {
        self.subtrees
            .iter()
            .find(|node| node.name == subtree_name.as_ref())
            .map(|node| node.height.unwrap_or_else(|| self.height()))
            .ok_or_else(|| {
                StoreError::KeyNotFound {
                    store: "entry".to_string(),
                    key: subtree_name.as_ref().to_string(),
                }
                .into()
            })
    }

    /// Create a canonical representation of this entry for signing purposes.
    ///
    /// This creates a copy of the entry with the signature field removed from auth,
    /// which is necessary for signature generation and verification.
    /// The returned entry has deterministic field ordering for consistent signatures.
    pub fn canonical_for_signing(&self) -> Self {
        self.clone().with_auth(|auth| auth.signature = None)
    }

    /// Create canonical bytes for signing or ID generation.
    ///
    /// This method serializes the entry to DAG-CBOR with deterministic field ordering.
    /// For signing purposes, call `canonical_for_signing()` first.
    pub fn canonical_bytes(&self) -> Result<Vec<u8>> {
        self.to_dagcbor()
    }

    /// Create canonical bytes for signing (convenience method).
    ///
    /// This combines `canonical_for_signing()` and `canonical_bytes()` for convenience.
    pub fn signing_bytes(&self) -> Result<Vec<u8>> {
        self.canonical_for_signing().canonical_bytes()
    }

    /// Serialize this entry to DAG-CBOR bytes.
    ///
    /// Returns the canonical DAG-CBOR encoding for CID computation.
    pub fn to_dagcbor(&self) -> Result<Vec<u8>> {
        serde_ipld_dagcbor::to_vec(self).map_err(|e| {
            EntryError::SerializationFailed {
                context: format!("DAG-CBOR serialization failed: {e}"),
            }
            .into()
        })
    }

    /// Validate the structural integrity of this entry.
    ///
    /// This method performs lightweight structural validation that can be done
    /// without access to the backend database. It checks for obvious structural
    /// issues while deferring complex DAG relationship validation to the transaction
    /// and backend layers where full database access is available.
    ///
    /// # Validation Rules
    ///
    /// ## Critical Main Tree Parent Validation (Prevents "No Common Ancestor" Errors)
    /// - **Root entries** (containing "_root" subtree): May have empty parents
    /// - **Non-root entries**: MUST have at least one parent - **HARD REQUIREMENT**
    /// - **Empty parent IDs**: Always rejected as invalid
    ///
    /// This strict enforcement prevents orphaned entries that cause sync failures.
    ///
    /// ## Subtree Parent Relationships
    /// - For root entries: Subtrees may have empty parents (they establish the subtree roots)
    /// - For non-root entries: Empty subtree parents require deeper validation:
    ///   - Could be legitimate (first entry in a new subtree)
    ///   - Could indicate broken relationships (needs DAG traversal to verify)
    ///
    /// ## Multi-Layer Validation System
    /// Complex validation happens at multiple layers:
    /// 1. **Entry Layer** (this method): Structural validation, main tree parent enforcement
    /// 2. **Transaction Layer**: Parent discovery, subtree parent validation with DAG access
    /// 3. **Backend Storage**: Final validation gate before persistence
    /// 4. **Sync Operations**: Validation of entries received from peers
    ///
    /// # Special Cases
    /// - The "_root" marker subtree has special handling and skips validation
    /// - The "_settings" subtree follows standard validation rules
    /// - Empty subtree parents are logged but deferred to transaction layer
    ///
    /// # Returns
    ///
    /// - `Ok(())` if the entry is structurally valid
    /// - `Err(InstanceError::EntryValidationFailed)` if validation fails with specific reason
    ///
    /// # Examples
    ///
    /// ```rust,no_run
    /// # use eidetica::Entry;
    /// # let entry: Entry = unimplemented!();
    /// // Validate an entry before storage or sync
    /// match entry.validate() {
    ///     Ok(()) => {
    ///         // Entry is valid, safe to store/sync
    ///         println!("Entry is valid");
    ///     }
    ///     Err(e) => {
    ///         // Entry is invalid, reject it
    ///         eprintln!("Invalid entry: {}", e);
    ///     }
    /// }
    /// ```
    /// Validates that an ID contains a valid CID.
    fn validate_id_format(id: &ID, context: &str) -> Result<()> {
        if id.as_cid().is_none() {
            return Err(
                IdError::InvalidFormat(format!("Invalid ID in {context}: ID is empty")).into(),
            );
        }
        Ok(())
    }

    pub fn validate(&self) -> Result<()> {
        use crate::constants::{ROOT, SETTINGS};
        use crate::instance::errors::InstanceError;

        // CRITICAL VALIDATION: Root entries (with _root marker) cannot have parents
        // This enforces that root entries are true starting points of trees
        let has_root_marker = self.subtrees.iter().any(|node| node.name == ROOT);
        if has_root_marker && !self.tree.parents.is_empty() {
            return Err(InstanceError::EntryValidationFailed {
                reason: format!(
                    "Entry {} has _root marker but also has parents. Root entries cannot have parent relationships as they are the starting points of trees.",
                    self.id()
                ),
            }.into());
        }

        // Check if this is a root entry (will be true only if has ROOT marker AND no parents AND no root)
        let is_root_entry =
            has_root_marker && self.tree.parents.is_empty() && self.tree.root.is_none();

        // Validate root ID format (when present)
        if let Some(root_id) = &self.tree.root {
            Self::validate_id_format(root_id, "tree root ID")?;
        }

        // Validate each subtree
        for subtree_node in &self.subtrees {
            let subtree_name = &subtree_node.name;
            let subtree_parents = &subtree_node.parents;

            // Empty string is not allowed as a subtree name
            if subtree_name.is_empty() {
                return Err(InstanceError::EntryValidationFailed {
                    reason: format!(
                        "Entry {} has a subtree with empty name. Store names must be non-empty.",
                        self.id()
                    ),
                }
                .into());
            }

            // Skip validation for the special "_root" marker subtree
            if subtree_name == ROOT {
                continue;
            }

            // For non-root entries with empty subtree parents, this is only valid if:
            // 1. The entry has no main parents (making it a legitimate subtree root), OR
            // 2. The subtree is genuinely being established for the first time within the tree
            //
            // Note: We can't perform deep validation here without access to the backend,
            // so we defer complex validation to transaction/backend layers where full
            // DAG traversal is possible. This basic validation catches obvious structural errors.
            if !is_root_entry && subtree_parents.is_empty() {
                // This is a lightweight structural check - more comprehensive validation
                // happens in transaction/backend layers with full DAG access
                tracing::debug!(
                    entry_id = %self.id(),
                    subtree = subtree_name,
                    "Entry has empty subtree parents - will be validated in transaction layer"
                );
            }

            // Special validation for the critical "_settings" subtree
            // Note: Settings subtree follows the same rules as other subtrees - empty parents
            // are valid for the first entry in the subtree. Comprehensive validation happens
            // in transaction/backend layers with full DAG access.
            if subtree_name == SETTINGS && !is_root_entry && subtree_parents.is_empty() {
                tracing::debug!(
                    entry_id = %self.id(),
                    "Settings subtree has empty parents - will be validated in transaction layer"
                );
            }

            // Validate that subtree parents are not empty strings and have valid format
            for parent_id in subtree_parents {
                if parent_id.is_empty() {
                    return Err(InstanceError::EntryValidationFailed {
                        reason: format!(
                            "Entry {} has subtree '{}' with empty parent ID. Parent IDs must be non-empty valid entry IDs.",
                            self.id(),
                            subtree_name
                        ),
                    }.into());
                }
                // Validate parent ID format
                Self::validate_id_format(
                    parent_id,
                    &format!("subtree '{subtree_name}' parent ID"),
                )?;
            }
        }

        // Enforce main tree parent requirements
        if !is_root_entry {
            let main_parents = self.tree.parents.clone();
            if main_parents.is_empty() {
                // This is a HARD FAILURE - reject the entry completely
                // Empty main tree parents create orphaned nodes that break LCA calculations
                return Err(InstanceError::EntryValidationFailed {
                    reason: format!(
                        "Non-root entry {} has empty main tree parents. All non-root entries must have valid parent relationships in the main tree.",
                        self.id()
                    ),
                }.into());
            }

            // Validate that main parents are not empty strings and have valid format
            for parent_id in &main_parents {
                if parent_id.is_empty() {
                    return Err(InstanceError::EntryValidationFailed {
                        reason: format!(
                            "Entry {} has empty parent ID in main tree. Parent IDs must be non-empty valid entry IDs.",
                            self.id()
                        ),
                    }.into());
                }
                // Validate parent ID format
                Self::validate_id_format(parent_id, "main tree parent ID")?;
            }
        }

        Ok(())
    }
}