injectable_rs_graph/

graph.rs

//! The dependency graph — a collection of nodes with validation.

use crate::{GraphNode, ValidationError};

/// A dependency graph of all injectable types in the application.
///
/// The graph is constructed from metadata generated by the proc macros
/// and is validated once at container build time. After validation,
/// the graph is not used during runtime resolution — providers resolve
/// dependencies through static dispatch.
///
/// # Construction
///
/// The graph is typically built automatically by the container builder:
///
/// ```rust,ignore
/// let graph = DependencyGraph::new(vec![
///     GraphNode::new("UserService", &["Database", "Cache"]),
///     GraphNode::leaf("Database"),
///     GraphNode::leaf("Cache"),
/// ]);
/// graph.validate()?;
/// ```
#[derive(Debug, Clone)]
pub struct DependencyGraph {
    nodes: Vec<GraphNode>,
}

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

    /// Create a new dependency graph from a list of nodes.
    pub fn new(nodes: Vec<GraphNode>) -> Self {
        Self { nodes }
    }

    /// Add a node to the graph.
    pub fn add_node(&mut self, node: GraphNode) {
        self.nodes.push(node);
    }

    /// Get all nodes in the graph.
    pub fn nodes(&self) -> &[GraphNode] {
        &self.nodes
    }

    /// Get the number of nodes in the graph.
    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    /// Returns `true` if the graph contains no nodes.
    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    /// Find a node by name.
    pub fn find_node(&self, name: &str) -> Option<&GraphNode> {
        self.nodes.iter().find(|n| n.name == name)
    }

    /// Validate the entire dependency graph.
    ///
    /// Checks for:
    /// - Circular dependencies (via DFS)
    /// - Missing dependencies (references to types not in the graph)
    /// - Duplicate node definitions
    /// - Scope mismatches (wider-scope types depending on narrower-scope types)
    ///
    /// Returns a list of validation errors. An empty list means the graph is valid.
    pub fn validate(&self) -> Result<(), Vec<ValidationError>> {
        let mut errors = Vec::new();

        // Check for duplicate nodes
        self.check_duplicates(&mut errors);

        // Check for missing dependencies
        self.check_missing(&mut errors);

        // Check for circular dependencies
        self.check_cycles(&mut errors);

        // Check for scope mismatches
        self.check_scope_mismatches(&mut errors);

        if errors.is_empty() {
            Ok(())
        } else {
            Err(errors)
        }
    }

    fn check_duplicates(&self, errors: &mut Vec<ValidationError>) {
        let mut seen = std::collections::HashSet::new();
        for node in &self.nodes {
            if !seen.insert(node.name) {
                errors.push(ValidationError::DuplicateNode {
                    name: node.name.to_string(),
                });
            }
        }
    }

    fn check_missing(&self, errors: &mut Vec<ValidationError>) {
        let names: std::collections::HashSet<&str> = self.nodes.iter().map(|n| n.name).collect();

        for node in &self.nodes {
            for dep in node.dependencies {
                if !names.contains(dep) {
                    // Skip path-qualified names (containing `::` or `<`): these are
                    // external types provided via DynProvider and are not in the graph.
                    if dep.contains("::") || dep.contains('<') {
                        continue;
                    }
                    errors.push(ValidationError::MissingDependency {
                        source: node.name.to_string(),
                        missing: dep.to_string(),
                    });
                }
            }
        }
    }

    fn check_cycles(&self, errors: &mut Vec<ValidationError>) {
        let mut visited = std::collections::HashSet::new();
        let mut in_stack = std::collections::HashSet::new();
        let mut path = Vec::new();

        for node in &self.nodes {
            if !visited.contains(node.name) {
                self.dfs(node.name, &mut visited, &mut in_stack, &mut path, errors);
            }
        }
    }

    fn dfs<'a>(
        &self,
        current: &'a str,
        visited: &mut std::collections::HashSet<&'a str>,
        in_stack: &mut std::collections::HashSet<&'a str>,
        path: &mut Vec<&'a str>,
        errors: &mut Vec<ValidationError>,
    ) {
        visited.insert(current);
        in_stack.insert(current);
        path.push(current);

        if let Some(node) = self.find_node(current) {
            for dep in node.dependencies {
                if !visited.contains(dep) {
                    self.dfs(dep, visited, in_stack, path, errors);
                } else if in_stack.contains(dep) {
                    // Found a cycle — record the cycle path
                    let cycle_start = path.iter().position(|n| *n == *dep).unwrap_or(0);
                    // Panic Safety: cycle_start comes from position() which returns an index < path.len(),
                    // or 0 as fallback; either way cycle_start <= path.len().
                    let cycle: Vec<String> = path
                        .get(cycle_start..)
                        .unwrap_or(&[])
                        .iter()
                        .map(|s| s.to_string())
                        .chain(std::iter::once(dep.to_string()))
                        .collect();

                    errors.push(ValidationError::CircularDependency { chain: cycle });
                }
            }
        }

        path.pop();
        in_stack.remove(current);
    }

    /// Check for scope mismatches.
    ///
    /// A scope mismatch occurs when a wider-scope type (e.g., singleton)
    /// depends on a narrower-scope type (e.g., transient). This is
    /// problematic because the narrower-scope instance would be captured
    /// by the wider-scope instance for its entire lifetime, violating
    /// the narrower scope's semantics.
    ///
    /// # Scope Ordering
    ///
    /// From widest to narrowest:
    /// - `singleton` (widest — lives for the entire application lifetime)
    /// - `transient` (narrowest — new instance per resolution)
    ///
    /// # Valid Combinations
    ///
    /// - singleton → singleton: OK
    /// - transient → singleton: OK (transient gets a shared singleton)
    /// - transient → transient: OK (each gets a fresh instance)
    /// - singleton → transient: ERROR (singleton captures a single transient forever)
    fn check_scope_mismatches(&self, errors: &mut Vec<ValidationError>) {
        for node in &self.nodes {
            for dep_name in node.dependencies {
                if let Some(dep) = self.find_node(dep_name) {
                    if is_wider_scope(node.scope, dep.scope) {
                        errors.push(ValidationError::ScopeMismatch {
                            source: node.name.to_string(),
                            source_scope: node.scope.to_string(),
                            dependency: dep_name.to_string(),
                            dependency_scope: dep.scope.to_string(),
                        });
                    }
                }
            }
        }
    }

    /// Compute the topological order of the dependency graph.
    ///
    /// Returns nodes in construction order (dependencies before dependents).
    /// Returns an error if the graph contains cycles.
    pub fn topological_order(&self) -> Result<Vec<&str>, Vec<ValidationError>> {
        self.validate()?;

        let mut result = Vec::new();
        let mut visited = std::collections::HashSet::new();
        let mut temp_marked = std::collections::HashSet::new();

        for node in &self.nodes {
            if !visited.contains(node.name) {
                self.topo_visit(node.name, &mut visited, &mut temp_marked, &mut result);
            }
        }

        Ok(result)
    }

    fn topo_visit<'a>(
        &self,
        current: &'a str,
        visited: &mut std::collections::HashSet<&'a str>,
        temp_marked: &mut std::collections::HashSet<&'a str>,
        result: &mut Vec<&'a str>,
    ) {
        if visited.contains(current) {
            return;
        }
        if temp_marked.contains(current) {
            return; // Cycle — already validated above
        }

        temp_marked.insert(current);

        if let Some(node) = self.find_node(current) {
            for dep in node.dependencies {
                self.topo_visit(dep, visited, temp_marked, result);
            }
        }

        temp_marked.remove(current);
        visited.insert(current);
        result.push(current);
    }

    /// Compute the destruction order (reverse topological).
    ///
    /// Dependencies are destroyed after their dependents.
    pub fn destruction_order(&self) -> Result<Vec<&str>, Vec<ValidationError>> {
        let mut order = self.topological_order()?;
        order.reverse();
        Ok(order)
    }
}

/// Determine if `source_scope` is wider than `dep_scope`.
///
/// Returns `true` when a scope mismatch would occur — i.e., when a
/// wider-scope type depends on a narrower-scope type.
///
/// # Scope Width Ordering
///
/// - `singleton` is the widest scope
/// - `transient` is narrower than `singleton`
///
/// Any unrecognized scope is treated as equivalent to `singleton` (no mismatch).
fn is_wider_scope(source_scope: &str, dep_scope: &str) -> bool {
    match (source_scope, dep_scope) {
        // singleton depending on transient is the canonical mismatch
        ("singleton", "transient") => true,
        // All other combinations are valid
        _ => false,
    }
}

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

    #[test]
    fn test_is_wider_scope() {
        assert!(is_wider_scope("singleton", "transient"));
        assert!(!is_wider_scope("singleton", "singleton"));
        assert!(!is_wider_scope("transient", "singleton"));
        assert!(!is_wider_scope("transient", "transient"));
        assert!(!is_wider_scope("request", "transient"));
        assert!(!is_wider_scope("singleton", "request"));
    }

    #[test]
    fn empty_graph_is_valid() {
        let g = DependencyGraph::empty();
        assert!(g.is_empty());
        assert_eq!(g.len(), 0);
        assert!(g.validate().is_ok());
    }

    #[test]
    fn valid_linear_graph() {
        let g = DependencyGraph::new(vec![
            GraphNode::leaf("Database"),
            GraphNode::new("UserService", &["Database"]),
        ]);
        assert!(g.validate().is_ok());
    }

    #[test]
    fn circular_dependency_detected() {
        let g = DependencyGraph::new(vec![
            GraphNode::new("A", &["B"]),
            GraphNode::new("B", &["A"]),
        ]);
        let errs = g.validate().unwrap_err();
        assert!(
            errs.iter()
                .any(|e| matches!(e, ValidationError::CircularDependency { .. }))
        );
    }

    #[test]
    fn three_node_cycle_detected() {
        let g = DependencyGraph::new(vec![
            GraphNode::new("A", &["B"]),
            GraphNode::new("B", &["C"]),
            GraphNode::new("C", &["A"]),
        ]);
        let errs = g.validate().unwrap_err();
        assert!(
            errs.iter()
                .any(|e| matches!(e, ValidationError::CircularDependency { .. }))
        );
    }

    #[test]
    fn missing_dependency_detected() {
        let g = DependencyGraph::new(vec![GraphNode::new("UserService", &["MissingDep"])]);
        let errs = g.validate().unwrap_err();
        assert!(
            errs.iter()
                .any(|e| matches!(e, ValidationError::MissingDependency { .. }))
        );
    }

    #[test]
    fn duplicate_node_detected() {
        let g = DependencyGraph::new(vec![
            GraphNode::leaf("Database"),
            GraphNode::leaf("Database"),
        ]);
        let errs = g.validate().unwrap_err();
        assert!(
            errs.iter()
                .any(|e| matches!(e, ValidationError::DuplicateNode { .. }))
        );
    }

    #[test]
    fn scope_mismatch_detected() {
        let g = DependencyGraph::new(vec![
            GraphNode::leaf("Transient").then_with_scope("transient"),
            GraphNode::with_scope("Singleton", &["Transient"], "singleton"),
        ]);
        let errs = g.validate().unwrap_err();
        assert!(
            errs.iter()
                .any(|e| matches!(e, ValidationError::ScopeMismatch { .. }))
        );
    }

    #[test]
    fn topological_order_valid_graph() {
        let g = DependencyGraph::new(vec![
            GraphNode::leaf("Database"),
            GraphNode::new("UserService", &["Database"]),
        ]);
        let order = g.topological_order().unwrap();
        let db_pos = order.iter().position(|n| *n == "Database").unwrap();
        let svc_pos = order.iter().position(|n| *n == "UserService").unwrap();
        assert!(db_pos < svc_pos);
    }

    #[test]
    fn destruction_order_is_reverse_topo() {
        let g = DependencyGraph::new(vec![
            GraphNode::leaf("Database"),
            GraphNode::new("UserService", &["Database"]),
        ]);
        let topo = g.topological_order().unwrap();
        let destruct = g.destruction_order().unwrap();
        assert_eq!(topo, destruct.iter().rev().cloned().collect::<Vec<_>>());
    }

    #[test]
    fn find_node_existing() {
        let g = DependencyGraph::new(vec![GraphNode::leaf("Database")]);
        assert!(g.find_node("Database").is_some());
        assert!(g.find_node("Missing").is_none());
    }

    #[test]
    fn add_node_increases_len() {
        let mut g = DependencyGraph::empty();
        g.add_node(GraphNode::leaf("Foo"));
        assert_eq!(g.len(), 1);
        assert!(!g.is_empty());
    }

    #[test]
    fn path_qualified_dep_not_missing() {
        // Dependencies with '::' are external types, not graph nodes
        let g = DependencyGraph::new(vec![GraphNode::new("MyService", &["sqlx::SqlitePool"])]);
        assert!(g.validate().is_ok());
    }
}

// Helper for tests: create a node with a scope override via builder pattern
#[allow(dead_code)]
trait NodeScopeExt {
    fn then_with_scope(self, scope: &'static str) -> GraphNode;
}

impl NodeScopeExt for GraphNode {
    fn then_with_scope(self, scope: &'static str) -> GraphNode {
        GraphNode::with_scope(self.name, self.dependencies, scope)
    }
}