fraiseql_core/cache/

cascade_invalidator.rs

//! Cascading cache invalidation for transitive view dependencies.
//!
//! Tracks view-to-view dependencies and propagates invalidation through the dependency graph.
//! When a view is invalidated, all dependent views are also invalidated.

use std::collections::{HashMap, HashSet, VecDeque};

use serde::{Deserialize, Serialize};

#[allow(unused_imports)] // Reason: used only in doc links for `# Errors` sections
use crate::error::FraiseQLError;
use crate::error::Result;

/// Tracks transitive view-to-view dependencies for cascading invalidation.
///
/// # Architecture
///
/// When `v_user` depends on `v_raw_user`, and `v_analytics` depends on `v_user`:
///
/// ```text
/// v_raw_user (source)
///    ↓ (depends on)
/// v_user (intermediate)
///    ↓ (depends on)
/// v_analytics (leaf)
/// ```
///
/// Invalidating `v_raw_user` cascades to invalidate `v_user` and `v_analytics`.
///
/// # Example
///
/// ```rust
/// use fraiseql_core::cache::cascade_invalidator::CascadeInvalidator;
///
/// let mut invalidator = CascadeInvalidator::new();
///
/// // Register that v_user depends on v_raw_user
/// invalidator.add_dependency("v_user", "v_raw_user").unwrap();
///
/// // Register that v_analytics depends on v_user
/// invalidator.add_dependency("v_analytics", "v_user").unwrap();
///
/// // Invalidate v_raw_user - cascades to v_user and v_analytics
/// let affected = invalidator.cascade_invalidate("v_raw_user").unwrap();
/// assert_eq!(affected.len(), 3); // v_raw_user, v_user, v_analytics
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct CascadeInvalidator {
    /// Dependent view → list of views it depends on.
    /// Example: `v_user` → [`v_raw_user`]
    view_dependencies: HashMap<String, HashSet<String>>,

    /// View → list of views that depend on it (reverse mapping).
    /// Example: `v_raw_user` → [`v_user`]
    dependents: HashMap<String, HashSet<String>>,

    /// Statistics for monitoring.
    stats: InvalidationStats,
}

/// Statistics for cascade invalidation operations.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct InvalidationStats {
    /// Total number of cascade invalidations performed.
    pub total_cascades: u64,

    /// Total views invalidated across all cascades.
    pub total_invalidated: u64,

    /// Average views affected per cascade.
    pub average_affected: f64,

    /// Maximum views affected in a single cascade.
    pub max_affected: usize,
}

impl Default for InvalidationStats {
    fn default() -> Self {
        Self {
            total_cascades:    0,
            total_invalidated: 0,
            average_affected:  0.0,
            max_affected:      0,
        }
    }
}

impl CascadeInvalidator {
    /// Create new cascade invalidator.
    #[must_use]
    pub fn new() -> Self {
        Self {
            view_dependencies: HashMap::new(),
            dependents:        HashMap::new(),
            stats:             InvalidationStats::default(),
        }
    }

    /// Register a view dependency.
    ///
    /// Declares that `dependent_view` depends on `dependency_view`.
    /// When `dependency_view` is invalidated, `dependent_view` will also be invalidated.
    ///
    /// # Arguments
    ///
    /// * `dependent_view` - View that depends on another
    /// * `dependency_view` - View that is depended upon
    ///
    /// # Errors
    ///
    /// Returns [`FraiseQLError::Validation`] if `dependent_view` and
    /// `dependency_view` are the same (self-dependency), or if adding the edge
    /// would create a cycle in the dependency graph.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fraiseql_core::cache::cascade_invalidator::CascadeInvalidator;
    ///
    /// let mut invalidator = CascadeInvalidator::new();
    /// invalidator.add_dependency("v_analytics", "v_user").unwrap();
    /// ```
    pub fn add_dependency(&mut self, dependent_view: &str, dependency_view: &str) -> Result<()> {
        if dependent_view == dependency_view {
            return Err(crate::error::FraiseQLError::Validation {
                message: "View cannot depend on itself".to_string(),
                path:    Some("cascade_invalidator::add_dependency".to_string()),
            });
        }

        // Check for indirect cycles: would adding dependent → dependency create a cycle?
        // That happens if dependency_view can already reach dependent_view via existing edges.
        // We traverse the `dependents` graph (reverse edges) from dependency_view and check
        // whether we ever reach dependent_view.
        if self.can_reach(dependency_view, dependent_view) {
            return Err(crate::error::FraiseQLError::Validation {
                message: format!(
                    "Adding dependency '{}' → '{}' would create a cycle",
                    dependent_view, dependency_view
                ),
                path:    Some("cascade_invalidator::add_dependency".to_string()),
            });
        }

        let dependent = dependent_view.to_string();
        let dependency = dependency_view.to_string();

        // Add forward mapping: dependent → dependency
        self.view_dependencies
            .entry(dependent.clone())
            .or_default()
            .insert(dependency.clone());

        // Add reverse mapping: dependency → dependent
        self.dependents.entry(dependency).or_default().insert(dependent);

        Ok(())
    }

    /// Check whether `from` can reach `target` by following the forward dependency graph.
    ///
    /// Uses BFS over `view_dependencies` (from dependent to what it depends on). Returns
    /// `true` if `target` is reachable from `from`, meaning `from` transitively depends on
    /// `target`.
    ///
    /// This is used to detect cycles before adding a new edge: if `dependency_view` can
    /// already reach `dependent_view`, adding `dependent_view → dependency_view` would
    /// create a cycle.
    fn can_reach(&self, from: &str, target: &str) -> bool {
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        queue.push_back(from.to_string());

        while let Some(current) = queue.pop_front() {
            if current == target {
                return true;
            }
            if !visited.insert(current.clone()) {
                continue; // already visited
            }
            // Follow forward edges: what does `current` depend on?
            if let Some(deps) = self.view_dependencies.get(&current) {
                for dep in deps {
                    if !visited.contains(dep.as_str()) {
                        queue.push_back(dep.clone());
                    }
                }
            }
        }

        false
    }

    /// Cascade invalidate a view and all dependent views.
    ///
    /// Uses breadth-first search to find all views that transitively depend on
    /// the given view, and returns the complete set of invalidated views.
    ///
    /// # Algorithm
    ///
    /// 1. Start with the target view
    /// 2. Find all views that directly depend on it
    /// 3. For each dependent, recursively find views that depend on it
    /// 4. Return complete set (target + all transitive dependents)
    ///
    /// # Arguments
    ///
    /// * `view` - View to invalidate
    ///
    /// # Returns
    ///
    /// Set of all invalidated views (including the target)
    ///
    /// # Errors
    ///
    /// Currently infallible — always returns `Ok`. The `Result` return type is
    /// reserved for future cycle-detection logic that may return
    /// [`FraiseQLError::Validation`] on circular dependency graphs.
    ///
    /// # Example
    ///
    /// ```rust
    /// use fraiseql_core::cache::cascade_invalidator::CascadeInvalidator;
    ///
    /// let mut invalidator = CascadeInvalidator::new();
    /// invalidator.add_dependency("v_user_stats", "v_user").unwrap();
    /// invalidator.add_dependency("v_dashboard", "v_user_stats").unwrap();
    ///
    /// let invalidated = invalidator.cascade_invalidate("v_user").unwrap();
    /// assert!(invalidated.contains("v_user"));
    /// assert!(invalidated.contains("v_user_stats"));
    /// assert!(invalidated.contains("v_dashboard"));
    /// ```
    pub fn cascade_invalidate(&mut self, view: &str) -> Result<HashSet<String>> {
        let mut invalidated = HashSet::new();
        let mut queue = VecDeque::new();

        queue.push_back(view.to_string());
        invalidated.insert(view.to_string());

        // BFS to find all transitive dependents
        while let Some(current_view) = queue.pop_front() {
            if let Some(dependent_views) = self.dependents.get(&current_view) {
                for dependent in dependent_views {
                    if !invalidated.contains(dependent) {
                        invalidated.insert(dependent.clone());
                        queue.push_back(dependent.clone());
                    }
                }
            }
        }

        // Update statistics
        self.stats.total_cascades += 1;
        #[allow(clippy::cast_possible_truncation)]
        // Reason: invalidated.len() is a usize which fits in u64 on all supported 64-bit platforms
        {
            self.stats.total_invalidated += invalidated.len() as u64;
        }
        self.stats.max_affected = self.stats.max_affected.max(invalidated.len());
        if self.stats.total_cascades > 0 {
            #[allow(clippy::cast_precision_loss)]
            // Reason: average_affected is a display metric; f64 precision loss on u64 counters is
            // acceptable
            {
                self.stats.average_affected =
                    self.stats.total_invalidated as f64 / self.stats.total_cascades as f64;
            }
        }

        Ok(invalidated)
    }

    /// Get all views that depend on a given view (direct dependents only).
    ///
    /// For transitive dependents, use `cascade_invalidate()`.
    ///
    /// # Arguments
    ///
    /// * `view` - View to query
    ///
    /// # Returns
    ///
    /// Set of views that directly depend on the given view
    pub fn get_direct_dependents(&self, view: &str) -> HashSet<String> {
        self.dependents.get(view).cloned().unwrap_or_default()
    }

    /// Get all views that a given view depends on (direct dependencies only).
    ///
    /// # Arguments
    ///
    /// * `view` - View to query
    ///
    /// # Returns
    ///
    /// Set of views that the given view depends on
    pub fn get_direct_dependencies(&self, view: &str) -> HashSet<String> {
        self.view_dependencies.get(view).cloned().unwrap_or_default()
    }

    /// Get all views that transitively depend on a given view.
    ///
    /// Like `cascade_invalidate()` but non-mutating (for queries).
    ///
    /// # Arguments
    ///
    /// * `view` - View to query
    ///
    /// # Returns
    ///
    /// Set of all transitive dependents (including the view itself)
    pub fn get_transitive_dependents(&self, view: &str) -> HashSet<String> {
        let mut result = HashSet::new();
        let mut queue = VecDeque::new();

        queue.push_back(view.to_string());
        result.insert(view.to_string());

        while let Some(current) = queue.pop_front() {
            if let Some(deps) = self.dependents.get(&current) {
                for dep in deps {
                    if !result.contains(dep) {
                        result.insert(dep.clone());
                        queue.push_back(dep.clone());
                    }
                }
            }
        }

        result
    }

    /// Check if there's a dependency path between two views.
    ///
    /// Returns true if `dependent` transitively depends on `dependency`.
    ///
    /// # Arguments
    ///
    /// * `dependent` - Potentially dependent view
    /// * `dependency` - Potentially depended-upon view
    ///
    /// # Returns
    ///
    /// true if there's a transitive dependency
    pub fn has_dependency_path(&self, dependent: &str, dependency: &str) -> bool {
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();

        queue.push_back(dependent.to_string());

        while let Some(current) = queue.pop_front() {
            if visited.contains(&current) {
                continue;
            }
            visited.insert(current.clone());

            if let Some(deps) = self.view_dependencies.get(&current) {
                for dep in deps {
                    if dep == dependency {
                        return true;
                    }
                    queue.push_back(dep.clone());
                }
            }
        }

        false
    }

    /// Get cascade invalidation statistics.
    pub fn stats(&self) -> InvalidationStats {
        self.stats.clone()
    }

    /// Clear all registered dependencies.
    pub fn clear(&mut self) {
        self.view_dependencies.clear();
        self.dependents.clear();
        self.stats = InvalidationStats::default();
    }

    /// Get total number of views tracked.
    pub fn view_count(&self) -> usize {
        let mut views = HashSet::new();
        views.extend(self.dependents.keys().cloned());
        views.extend(self.view_dependencies.keys().cloned());
        views.len()
    }

    /// Get total number of dependency edges.
    pub fn dependency_count(&self) -> usize {
        self.view_dependencies.values().map(|deps| deps.len()).sum()
    }
}

impl Default for CascadeInvalidator {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    #![allow(clippy::unwrap_used)] // Reason: test code, panics are acceptable

    use super::*;

    #[test]
    fn test_add_single_dependency() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();

        assert!(invalidator.get_direct_dependencies("v_user").contains("v_raw_user"));
        assert!(invalidator.get_direct_dependents("v_raw_user").contains("v_user"));
    }

    #[test]
    fn test_self_dependency_fails() {
        let mut invalidator = CascadeInvalidator::new();
        let result = invalidator.add_dependency("v_user", "v_user");
        assert!(
            matches!(result, Err(crate::error::FraiseQLError::Validation { .. })),
            "expected Validation error for self-dependency, got: {result:?}"
        );
    }

    #[test]
    fn test_cascade_invalidate_single_level() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();

        let invalidated = invalidator.cascade_invalidate("v_raw_user").unwrap();
        assert_eq!(invalidated.len(), 2);
        assert!(invalidated.contains("v_raw_user"));
        assert!(invalidated.contains("v_user"));
    }

    #[test]
    fn test_cascade_invalidate_multiple_levels() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();
        invalidator.add_dependency("v_analytics", "v_user").unwrap();
        invalidator.add_dependency("v_dashboard", "v_analytics").unwrap();

        let invalidated = invalidator.cascade_invalidate("v_raw_user").unwrap();
        assert_eq!(invalidated.len(), 4);
        assert!(invalidated.contains("v_raw_user"));
        assert!(invalidated.contains("v_user"));
        assert!(invalidated.contains("v_analytics"));
        assert!(invalidated.contains("v_dashboard"));
    }

    #[test]
    fn test_cascade_invalidate_branching() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();
        invalidator.add_dependency("v_post", "v_raw_user").unwrap();
        invalidator.add_dependency("v_analytics", "v_user").unwrap();
        invalidator.add_dependency("v_dashboard", "v_post").unwrap();

        let invalidated = invalidator.cascade_invalidate("v_raw_user").unwrap();
        assert_eq!(invalidated.len(), 5);
        assert!(invalidated.contains("v_raw_user"));
        assert!(invalidated.contains("v_user"));
        assert!(invalidated.contains("v_post"));
        assert!(invalidated.contains("v_analytics"));
        assert!(invalidated.contains("v_dashboard"));
    }

    #[test]
    fn test_get_direct_dependents() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();
        invalidator.add_dependency("v_post", "v_raw_user").unwrap();

        let dependents = invalidator.get_direct_dependents("v_raw_user");
        assert_eq!(dependents.len(), 2);
        assert!(dependents.contains("v_user"));
        assert!(dependents.contains("v_post"));
    }

    #[test]
    fn test_get_direct_dependencies() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_analytics", "v_user").unwrap();
        invalidator.add_dependency("v_analytics", "v_post").unwrap();

        let deps = invalidator.get_direct_dependencies("v_analytics");
        assert_eq!(deps.len(), 2);
        assert!(deps.contains("v_user"));
        assert!(deps.contains("v_post"));
    }

    #[test]
    fn test_get_transitive_dependents() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();
        invalidator.add_dependency("v_analytics", "v_user").unwrap();
        invalidator.add_dependency("v_dashboard", "v_analytics").unwrap();

        let transitive = invalidator.get_transitive_dependents("v_raw_user");
        assert_eq!(transitive.len(), 4);
        assert!(transitive.contains("v_raw_user"));
        assert!(transitive.contains("v_user"));
        assert!(transitive.contains("v_analytics"));
        assert!(transitive.contains("v_dashboard"));
    }

    #[test]
    fn test_has_dependency_path() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();
        invalidator.add_dependency("v_analytics", "v_user").unwrap();

        assert!(invalidator.has_dependency_path("v_analytics", "v_raw_user"));
        assert!(invalidator.has_dependency_path("v_analytics", "v_user"));
        assert!(invalidator.has_dependency_path("v_user", "v_raw_user"));
        assert!(!invalidator.has_dependency_path("v_raw_user", "v_analytics"));
        assert!(!invalidator.has_dependency_path("v_raw_user", "v_user"));
    }

    #[test]
    fn test_stats_tracking() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();
        invalidator.add_dependency("v_analytics", "v_user").unwrap();

        invalidator.cascade_invalidate("v_raw_user").unwrap();
        invalidator.cascade_invalidate("v_user").unwrap();

        let stats = invalidator.stats();
        assert_eq!(stats.total_cascades, 2);
        assert_eq!(stats.total_invalidated, 5); // 3 (raw_user + user + analytics) + 2 (user + analytics)
        assert_eq!(stats.max_affected, 3);
    }

    #[test]
    fn test_clear() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();
        assert_eq!(invalidator.view_count(), 2);

        invalidator.clear();
        assert_eq!(invalidator.view_count(), 0);
        assert_eq!(invalidator.dependency_count(), 0);
    }

    #[test]
    fn test_view_and_dependency_count() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();
        invalidator.add_dependency("v_post", "v_raw_user").unwrap();
        invalidator.add_dependency("v_analytics", "v_user").unwrap();

        assert_eq!(invalidator.view_count(), 4);
        assert_eq!(invalidator.dependency_count(), 3);
    }

    #[test]
    fn test_diamond_dependency() {
        let mut invalidator = CascadeInvalidator::new();
        // Diamond: raw → [user, post] → analytics
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();
        invalidator.add_dependency("v_post", "v_raw_user").unwrap();
        invalidator.add_dependency("v_analytics", "v_user").unwrap();
        invalidator.add_dependency("v_analytics", "v_post").unwrap();

        let invalidated = invalidator.cascade_invalidate("v_raw_user").unwrap();
        // raw_user, user, post, analytics (4 total)
        assert_eq!(invalidated.len(), 4);
        assert!(invalidated.contains("v_raw_user"));
        assert!(invalidated.contains("v_user"));
        assert!(invalidated.contains("v_post"));
        assert!(invalidated.contains("v_analytics"));
    }

    #[test]
    fn test_multiple_independent_chains() {
        let mut invalidator = CascadeInvalidator::new();
        // Chain 1: raw1 → user1 → analytics1
        invalidator.add_dependency("v_user_1", "v_raw_1").unwrap();
        invalidator.add_dependency("v_analytics_1", "v_user_1").unwrap();
        // Chain 2: raw2 → user2 → analytics2
        invalidator.add_dependency("v_user_2", "v_raw_2").unwrap();
        invalidator.add_dependency("v_analytics_2", "v_user_2").unwrap();

        let invalidated = invalidator.cascade_invalidate("v_raw_1").unwrap();
        assert_eq!(invalidated.len(), 3); // Only chain 1
        assert!(!invalidated.contains("v_raw_2"));
        assert!(!invalidated.contains("v_user_2"));
    }

    #[test]
    fn test_cycle_detection_via_has_dependency_path() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();
        invalidator.add_dependency("v_analytics", "v_user").unwrap();

        // Verify no forward path from leaf to root
        assert!(!invalidator.has_dependency_path("v_raw_user", "v_analytics"));
    }

    #[test]
    fn test_indirect_cycle_detection() {
        let mut invalidator = CascadeInvalidator::new();
        // Build chain: A depends on B, B depends on C
        invalidator.add_dependency("B", "A").unwrap();
        invalidator.add_dependency("C", "B").unwrap();

        // Adding C → A would create the cycle C→B→A→...→C — must be rejected.
        // (C depends on B which depends on A; adding A→C would close the loop)
        let result = invalidator.add_dependency("A", "C");
        assert!(
            matches!(result, Err(crate::error::FraiseQLError::Validation { .. })),
            "expected Validation error for indirect cycle A→C→B→A, got: {result:?}"
        );
        let msg = result.unwrap_err().to_string();
        assert!(msg.contains("cycle"), "error message should mention cycle, got: {msg}");
    }

    #[test]
    fn test_three_node_cycle_rejected() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("B", "A").unwrap(); // B depends on A
        invalidator.add_dependency("C", "B").unwrap(); // C depends on B
        // A depends on C would close: A→C→B→A
        let result = invalidator.add_dependency("A", "C");
        assert!(
            matches!(result, Err(crate::error::FraiseQLError::Validation { .. })),
            "expected Validation error for three-node cycle A→C→B→A, got: {result:?}"
        );
    }

    #[test]
    fn test_serialization() {
        let mut invalidator = CascadeInvalidator::new();
        invalidator.add_dependency("v_user", "v_raw_user").unwrap();

        let json = serde_json::to_string(&invalidator).expect("serialize should work");
        let restored: CascadeInvalidator =
            serde_json::from_str(&json).expect("deserialize should work");

        assert_eq!(
            restored.get_direct_dependents("v_raw_user"),
            invalidator.get_direct_dependents("v_raw_user")
        );
    }

    #[test]
    fn cascade_invalidator_is_send_sync() {
        // Invariant: CascadeInvalidator is read-only (graph data) after construction.
        // Stats use an internal Mutex for thread-safe writes.
        fn assert_send_sync<T: Send + Sync>() {}
        assert_send_sync::<CascadeInvalidator>();
    }

    #[test]
    fn cascade_invalidate_takes_shared_ref() {
        let mut inv = CascadeInvalidator::new();
        inv.add_dependency("v_b", "v_a").unwrap();
        // Should work with &inv (not &mut inv) — cascade_invalidate takes &self.
        let result = inv.cascade_invalidate("v_a").unwrap();
        assert!(result.contains("v_b"));
    }
}