memlink_runtime/

deps.rs

//! Module dependency tracking and composition.
//!
//! Manages dependencies between modules, load order, and nested calls.

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

use dashmap::DashMap;

use crate::error::{Error, Result};

/// Dependency information for a module.
#[derive(Debug, Clone)]
pub struct ModuleDependency {
    /// Name of the required module.
    pub name: String,
    /// Minimum version required (optional).
    pub min_version: Option<String>,
    /// Whether this dependency is optional.
    pub optional: bool,
}

/// Dependency graph node.
#[derive(Debug, Clone)]
pub struct DependencyNode {
    /// Module name.
    pub name: String,
    /// Dependencies this module requires.
    pub dependencies: Vec<ModuleDependency>,
    /// Modules that depend on this one (reverse deps).
    pub dependents: HashSet<String>,
    /// Whether the module is loaded.
    pub loaded: bool,
}

/// Module dependency graph.
#[derive(Debug)]
pub struct DependencyGraph {
    /// All nodes in the graph.
    nodes: DashMap<String, DependencyNode>,
}

impl DependencyGraph {
    /// Creates a new empty dependency graph.
    pub fn new() -> Self {
        Self {
            nodes: DashMap::new(),
        }
    }

    /// Adds a module to the graph.
    pub fn add_module(&self, name: &str, dependencies: Vec<ModuleDependency>) {
        let node = DependencyNode {
            name: name.to_string(),
            dependencies,
            dependents: HashSet::new(),
            loaded: false,
        };
        self.nodes.insert(name.to_string(), node);
    }

    /// Marks a module as loaded.
    pub fn mark_loaded(&self, name: &str) {
        if let Some(mut node) = self.nodes.get_mut(name) {
            node.loaded = true;
        }
    }

    /// Marks a module as unloaded.
    pub fn mark_unloaded(&self, name: &str) {
        if let Some(mut node) = self.nodes.get_mut(name) {
            node.loaded = false;
        }
    }

    /// Checks if all dependencies of a module are satisfied.
    pub fn dependencies_satisfied(&self, name: &str) -> bool {
        let node = match self.nodes.get(name) {
            Some(n) => n,
            None => return false,
        };

        for dep in &node.dependencies {
            if dep.optional {
                continue;
            }

            let dep_node = match self.nodes.get(&dep.name) {
                Some(n) => n,
                None => return false, // Dependency not registered
            };

            if !dep_node.loaded {
                return false; // Dependency not loaded
            }
        }

        true
    }

    /// Returns the load order for all modules (topological sort).
    ///
    /// Returns modules in order they should be loaded (dependencies first).
    pub fn load_order(&self) -> Result<Vec<String>> {
        // Kahn's algorithm for topological sort
        let mut in_degree: HashMap<String, usize> = HashMap::new();
        let mut queue: VecDeque<String> = VecDeque::new();
        let mut result: Vec<String> = Vec::new();

        // Calculate in-degrees
        for entry in self.nodes.iter() {
            let name = entry.key().clone();
            let node = entry.value();
            let required_deps = node.dependencies.iter().filter(|d| !d.optional).count();
            in_degree.insert(name.clone(), required_deps);

            if required_deps == 0 {
                queue.push_back(name.clone());
            }
        }

        // Process queue
        while let Some(name) = queue.pop_front() {
            result.push(name.clone());

            // Reduce in-degree for dependents
            for entry in self.nodes.iter() {
                let node = entry.value();
                if node.dependencies.iter().any(|d| d.name == name && !d.optional) {
                    let in_deg = in_degree.get_mut(entry.key()).unwrap();
                    *in_deg -= 1;
                    if *in_deg == 0 {
                        queue.push_back(entry.key().clone());
                    }
                }
            }
        }

        // Check for cycles
        if result.len() != self.nodes.len() {
            return Err(Error::ModuleCallFailed(-1)); // Would be CircularDependency error
        }

        Ok(result)
    }

    /// Returns the unload order (reverse of load order).
    pub fn unload_order(&self) -> Result<Vec<String>> {
        let mut order = self.load_order()?;
        order.reverse();
        Ok(order)
    }

    /// Detects circular dependencies.
    pub fn has_cycle(&self) -> bool {
        self.load_order().is_err()
    }

    /// Returns all dependencies (transitive) for a module.
    pub fn all_dependencies(&self, name: &str) -> HashSet<String> {
        let mut result = HashSet::new();
        let mut queue: VecDeque<String> = VecDeque::new();

        if let Some(node) = self.nodes.get(name) {
            for dep in &node.dependencies {
                queue.push_back(dep.name.clone());
            }
        }

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

            if let Some(dep_node) = self.nodes.get(&dep_name) {
                for sub_dep in &dep_node.dependencies {
                    queue.push_back(sub_dep.name.clone());
                }
            }
        }

        result
    }

    /// Returns all modules that depend on the given module (transitive).
    pub fn all_dependents(&self, name: &str) -> HashSet<String> {
        let mut result = HashSet::new();
        let mut queue: VecDeque<String> = VecDeque::new();

        // Find direct dependents
        for entry in self.nodes.iter() {
            let node = entry.value();
            if node.dependencies.iter().any(|d| d.name == name) {
                queue.push_back(entry.key().clone());
            }
        }

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

            // Find dependents of this dependent
            for entry in self.nodes.iter() {
                let node = entry.value();
                if node.dependencies.iter().any(|d| d.name == dep_name) {
                    queue.push_back(entry.key().clone());
                }
            }
        }

        result
    }

    /// Checks if a module can be safely unloaded (no loaded dependents).
    pub fn can_unload(&self, name: &str) -> bool {
        let dependents = self.all_dependents(name);

        for dep_name in &dependents {
            if let Some(node) = self.nodes.get(dep_name) {
                if node.loaded {
                    return false; // Has loaded dependent
                }
            }
        }

        true
    }

    /// Returns the number of registered modules.
    pub fn module_count(&self) -> usize {
        self.nodes.len()
    }

    /// Returns all module names.
    pub fn all_modules(&self) -> Vec<String> {
        self.nodes.iter().map(|e| e.key().clone()).collect()
    }

    /// Returns information about a specific module.
    pub fn get_module(&self, name: &str) -> Option<DependencyNode> {
        self.nodes.get(name).map(|e| e.value().clone())
    }
}

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

/// Context for nested module calls.
#[derive(Debug, Clone)]
pub struct CallContext {
    /// The calling module (if any).
    pub caller: Option<String>,
    /// The target module.
    pub target: String,
    /// Current call depth.
    pub depth: usize,
    /// Maximum allowed depth.
    pub max_depth: usize,
    /// Trace ID for distributed tracing.
    pub trace_id: Option<u128>,
}

impl CallContext {
    /// Creates a new root call context.
    pub fn new(target: String) -> Self {
        Self {
            caller: None,
            target,
            depth: 0,
            max_depth: 10,
            trace_id: None,
        }
    }

    /// Creates a child context for a nested call.
    pub fn child(&self, target: String) -> Option<Self> {
        if self.depth >= self.max_depth {
            return None; // Max depth exceeded
        }

        Some(Self {
            caller: Some(self.target.clone()),
            target,
            depth: self.depth + 1,
            max_depth: self.max_depth,
            trace_id: self.trace_id,
        })
    }

    /// Returns whether this is a root call (not nested).
    pub fn is_root(&self) -> bool {
        self.caller.is_none()
    }

    /// Returns whether this is a nested call.
    pub fn is_nested(&self) -> bool {
        self.caller.is_some()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dependency_graph_basic() {
        let graph = DependencyGraph::new();

        graph.add_module("A", vec![]);
        graph.add_module("B", vec![
            ModuleDependency { name: "A".to_string(), min_version: None, optional: false }
        ]);
        graph.add_module("C", vec![
            ModuleDependency { name: "B".to_string(), min_version: None, optional: false }
        ]);

        // Load order should be A, B, C
        let order = graph.load_order().unwrap();
        assert_eq!(order, vec!["A", "B", "C"]);

        // Unload order should be C, B, A
        let order = graph.unload_order().unwrap();
        assert_eq!(order, vec!["C", "B", "A"]);
    }

    #[test]
    fn test_dependency_graph_optional() {
        let graph = DependencyGraph::new();

        graph.add_module("A", vec![]);
        graph.add_module("B", vec![
            ModuleDependency { name: "A".to_string(), min_version: None, optional: true }
        ]);

        // B can load even if A is not loaded (optional dependency)
        graph.mark_loaded("B");
        assert!(graph.dependencies_satisfied("B"));
    }

    #[test]
    fn test_dependency_graph_cycle_detection() {
        let graph = DependencyGraph::new();

        graph.add_module("A", vec![
            ModuleDependency { name: "B".to_string(), min_version: None, optional: false }
        ]);
        graph.add_module("B", vec![
            ModuleDependency { name: "A".to_string(), min_version: None, optional: false }
        ]);

        // Should detect cycle
        assert!(graph.has_cycle());
        assert!(graph.load_order().is_err());
    }

    #[test]
    fn test_call_context_depth() {
        let root = CallContext::new("A".to_string());
        assert_eq!(root.depth, 0);
        assert!(root.is_root());

        let child1 = root.child("B".to_string()).unwrap();
        assert_eq!(child1.depth, 1);
        assert!(child1.is_nested());

        let child2 = child1.child("C".to_string()).unwrap();
        assert_eq!(child2.depth, 2);

        // Test max depth
        let mut ctx = root;
        for i in 0..10 {
            if let Some(next) = ctx.child(format!("M{}", i)) {
                ctx = next;
            }
        }
        // 11th level should fail
        assert!(ctx.child("M10".to_string()).is_none());
    }

    #[test]
    fn test_transitive_dependencies() {
        let graph = DependencyGraph::new();

        graph.add_module("A", vec![]);
        graph.add_module("B", vec![
            ModuleDependency { name: "A".to_string(), min_version: None, optional: false }
        ]);
        graph.add_module("C", vec![
            ModuleDependency { name: "B".to_string(), min_version: None, optional: false }
        ]);

        // C's transitive dependencies should include A and B
        let deps = graph.all_dependencies("C");
        assert!(deps.contains("A"));
        assert!(deps.contains("B"));
        assert_eq!(deps.len(), 2);
    }

    #[test]
    fn test_can_unload() {
        let graph = DependencyGraph::new();

        graph.add_module("A", vec![]);
        graph.add_module("B", vec![
            ModuleDependency { name: "A".to_string(), min_version: None, optional: false }
        ]);

        graph.mark_loaded("A");
        graph.mark_loaded("B");

        // Can't unload A because B depends on it and is loaded
        assert!(!graph.can_unload("A"));

        // Can unload B
        assert!(graph.can_unload("B"));

        // After unloading B, can unload A
        graph.mark_unloaded("B");
        assert!(graph.can_unload("A"));
    }
}