cyrup_release 0.5.4

//! Dependency graph analysis and topological sorting for package publishing.
//!
//! This module builds dependency graphs from workspace information and determines
//! the optimal publishing order to ensure dependencies are available before dependents.

use crate::error::{Result, WorkspaceError};
use crate::workspace::WorkspaceInfo;
use petgraph::algo::{toposort, DfsSpace};
use petgraph::graph::{NodeIndex, UnGraph};
use petgraph::Graph;
use std::collections::HashMap;

/// Dependency graph representing package relationships
#[derive(Debug, Clone)]
pub struct DependencyGraph {
    /// Directed graph where edges point from dependency to dependent
    graph: Graph<String, (), petgraph::Directed>,
    /// Mapping from package names to graph node indices
    node_map: HashMap<String, NodeIndex>,
    /// Reverse mapping from node indices to package names
    index_map: HashMap<NodeIndex, String>,
}

/// Publishing order with packages grouped into tiers
#[derive(Debug, Clone)]
pub struct PublishOrder {
    /// Ordered tiers of packages that can be published in parallel within each tier
    pub tiers: Vec<PublishTier>,
    /// Total number of packages to be published
    pub total_packages: usize,
}

/// A tier of packages that can be published in parallel
#[derive(Debug, Clone)]
pub struct PublishTier {
    /// Package names in this tier
    pub packages: Vec<String>,
    /// Tier number (0-based)
    pub tier_number: usize,
}

impl DependencyGraph {
    /// Build dependency graph from workspace information
    pub fn build(workspace: &WorkspaceInfo) -> Result<Self> {
        let mut graph = Graph::new();
        let mut node_map = HashMap::with_capacity(workspace.packages.len());
        let mut index_map = HashMap::with_capacity(workspace.packages.len());

        // Add all PUBLISHABLE packages as nodes first (skip publish = false)
        for (package_name, package_info) in &workspace.packages {
            // Skip packages with publish = false
            if let Some(toml::Value::Boolean(false)) = package_info.config.other.get("publish") {
                continue;
            }
            
            let node_index = graph.add_node(package_name.clone());
            node_map.insert(package_name.clone(), node_index);
            index_map.insert(node_index, package_name.clone());
        }

        // Add dependency edges (from dependency to dependent)
        for (package_name, dependencies) in &workspace.internal_dependencies {
            // Skip if the dependent package is not in the graph (publish = false)
            let dependent_index = match node_map.get(package_name) {
                Some(idx) => idx,
                None => continue, // Skip non-publishable dependents
            };

            for dependency_name in dependencies {
                // Skip if the dependency is not in the graph (publish = false)
                let dependency_index = match node_map.get(dependency_name) {
                    Some(idx) => idx,
                    None => continue, // Skip non-publishable dependencies
                };

                // Edge from dependency to dependent (dependency must be published first)
                graph.add_edge(*dependency_index, *dependent_index, ());
            }
        }

        Ok(Self {
            graph,
            node_map,
            index_map,
        })
    }

    /// Generate publishing order using topological sorting
    pub fn publish_order(&self) -> Result<PublishOrder> {
        // Detect circular dependencies first
        self.validate_no_cycles()?;

        // Perform topological sort
        let sorted_indices = toposort(&self.graph, None)
            .map_err(|cycle| {
                let cycle_packages: Vec<String> = self.index_map.get(&cycle.node_id())
                    .map(|name| vec![name.clone()])
                    .unwrap_or_else(|| vec!["unknown".to_string()]);

                WorkspaceError::CircularDependency {
                    packages: cycle_packages,
                }
            })?;

        // Convert to package names maintaining topological order
        let ordered_packages: Vec<String> = sorted_indices
            .into_iter()
            .filter_map(|idx| self.index_map.get(&idx).cloned())
            .collect();

        // Group into tiers for parallel publishing within each tier
        let tiers = self.group_into_tiers(&ordered_packages);
        let total_packages = ordered_packages.len();

        Ok(PublishOrder {
            tiers,
            total_packages,
        })
    }

    /// Group packages into publishing tiers
    fn group_into_tiers(&self, ordered_packages: &[String]) -> Vec<PublishTier> {
        let mut tiers = Vec::new();
        let mut remaining_packages: std::collections::VecDeque<_> = ordered_packages.iter().collect();
        let mut tier_number = 0;

        while !remaining_packages.is_empty() {
            let mut current_tier = Vec::new();
            let mut indices_to_remove = Vec::new();

            // Find packages with no remaining dependencies in the current set
            for (index, package_name) in remaining_packages.iter().enumerate() {
                if self.can_publish_in_current_tier(package_name, &remaining_packages) {
                    current_tier.push((*package_name).clone());
                    indices_to_remove.push(index);
                }
            }

            // Remove processed packages (in reverse order to maintain indices)
            for &index in indices_to_remove.iter().rev() {
                remaining_packages.remove(index);
            }

            // If no packages can be published, there might be a subtle circular dependency
            if current_tier.is_empty() && !remaining_packages.is_empty() {
                // Take the first remaining package to break potential deadlock
                if let Some(package) = remaining_packages.pop_front() {
                    current_tier.push(package.clone());
                }
            }

            if !current_tier.is_empty() {
                tiers.push(PublishTier {
                    packages: current_tier,
                    tier_number,
                });
                tier_number += 1;
            }
        }

        tiers
    }

    /// Check if a package can be published in the current tier
    fn can_publish_in_current_tier(
        &self,
        package_name: &str,
        remaining_packages: &std::collections::VecDeque<&String>,
    ) -> bool {
        let package_index = match self.node_map.get(package_name) {
            Some(idx) => *idx,
            None => return false,
        };

        // Check if any dependencies are still in the remaining packages
        let neighbors = self.graph.neighbors_directed(package_index, petgraph::Direction::Incoming);
        
        for dependency_index in neighbors {
            if let Some(dependency_name) = self.index_map.get(&dependency_index) {
                if remaining_packages.iter().any(|&name| name == dependency_name) {
                    return false; // Dependency still needs to be published
                }
            }
        }

        true
    }

    /// Validate that the dependency graph has no circular dependencies
    fn validate_no_cycles(&self) -> Result<()> {
        // Convert to undirected graph for cycle detection
        let _undirected: UnGraph<String, ()> = self.graph.clone().into_edge_type();
        
        // Use DFS to detect cycles more efficiently
        let mut dfs_space = DfsSpace::new(&self.graph);
        
        // Check each strongly connected component
        for node_index in self.graph.node_indices() {
            if let Some(cycle_path) = self.find_cycle_from_node(node_index, &mut dfs_space) {
                let cycle_packages: Vec<String> = cycle_path
                    .into_iter()
                    .filter_map(|idx| self.index_map.get(&idx).cloned())
                    .collect();

                return Err(WorkspaceError::CircularDependency {
                    packages: cycle_packages,
                }.into());
            }
        }

        Ok(())
    }

    /// Find cycle starting from a specific node using DFS
    fn find_cycle_from_node(
        &self,
        start_node: NodeIndex,
        _dfs_space: &mut DfsSpace<NodeIndex, fixedbitset::FixedBitSet>,
    ) -> Option<Vec<NodeIndex>> {
        let mut visited = std::collections::HashSet::new();
        let mut recursion_stack = std::collections::HashSet::new();
        let mut path = Vec::new();

        self.dfs_cycle_detection(start_node, &mut visited, &mut recursion_stack, &mut path)
    }

    /// DFS-based cycle detection with path tracking
    fn dfs_cycle_detection(
        &self,
        node: NodeIndex,
        visited: &mut std::collections::HashSet<NodeIndex>,
        recursion_stack: &mut std::collections::HashSet<NodeIndex>,
        path: &mut Vec<NodeIndex>,
    ) -> Option<Vec<NodeIndex>> {
        visited.insert(node);
        recursion_stack.insert(node);
        path.push(node);

        // Visit all neighbors
        let neighbors: Vec<_> = self.graph.neighbors_directed(node, petgraph::Direction::Outgoing).collect();
        for neighbor in neighbors {
            if !visited.contains(&neighbor) {
                if let Some(cycle) = self.dfs_cycle_detection(neighbor, visited, recursion_stack, path) {
                    return Some(cycle);
                }
            } else if recursion_stack.contains(&neighbor) {
                // Found a cycle - extract the cycle path
                let cycle_start = path.iter().position(|&n| n == neighbor)?;
                return Some(path[cycle_start..].to_vec());
            }
        }

        recursion_stack.remove(&node);
        path.pop();
        None
    }

    /// Get all packages that depend on the given package
    pub fn dependents(&self, package_name: &str) -> Vec<String> {
        let package_index = match self.node_map.get(package_name) {
            Some(idx) => *idx,
            None => return Vec::new(),
        };

        self.graph
            .neighbors_directed(package_index, petgraph::Direction::Outgoing)
            .filter_map(|idx| self.index_map.get(&idx).cloned())
            .collect()
    }

    /// Get all dependencies of the given package
    pub fn dependencies(&self, package_name: &str) -> Vec<String> {
        let package_index = match self.node_map.get(package_name) {
            Some(idx) => *idx,
            None => return Vec::new(),
        };

        self.graph
            .neighbors_directed(package_index, petgraph::Direction::Incoming)
            .filter_map(|idx| self.index_map.get(&idx).cloned())
            .collect()
    }

    /// Check if package A depends on package B (directly or transitively)
    pub fn depends_on(&self, package_a: &str, package_b: &str) -> bool {
        let start_index = match self.node_map.get(package_a) {
            Some(idx) => *idx,
            None => return false,
        };

        let target_index = match self.node_map.get(package_b) {
            Some(idx) => *idx,
            None => return false,
        };

        // Use petgraph's has_path_connecting for efficient path detection
        petgraph::algo::has_path_connecting(&self.graph, start_index, target_index, None)
    }

    /// Get the dependency depth of a package (longest path from any root)
    pub fn dependency_depth(&self, package_name: &str) -> usize {
        let package_index = match self.node_map.get(package_name) {
            Some(idx) => *idx,
            None => return 0,
        };

        self.calculate_depth_recursive(package_index, &mut std::collections::HashSet::new())
    }

    /// Recursively calculate dependency depth with cycle prevention
    fn calculate_depth_recursive(
        &self,
        node: NodeIndex,
        visited: &mut std::collections::HashSet<NodeIndex>,
    ) -> usize {
        if visited.contains(&node) {
            return 0; // Cycle detected, return 0 to avoid infinite recursion
        }

        visited.insert(node);

        let max_dependency_depth = self.graph
            .neighbors_directed(node, petgraph::Direction::Incoming)
            .map(|dep_idx| self.calculate_depth_recursive(dep_idx, visited))
            .max()
            .unwrap_or(0);

        visited.remove(&node);
        max_dependency_depth + 1
    }
}

impl PublishOrder {
    /// Get the tier number for a specific package
    pub fn tier_for_package(&self, package_name: &str) -> Option<usize> {
        self.tiers
            .iter()
            .find(|tier| tier.packages.contains(&package_name.to_string()))
            .map(|tier| tier.tier_number)
    }

    /// Get all packages in a specific tier
    pub fn packages_in_tier(&self, tier_number: usize) -> Vec<String> {
        self.tiers
            .get(tier_number)
            .map(|tier| tier.packages.clone())
            .unwrap_or_default()
    }

    /// Get the total number of tiers
    pub fn tier_count(&self) -> usize {
        self.tiers.len()
    }

    /// Check if a package exists in the publish order
    pub fn contains_package(&self, package_name: &str) -> bool {
        self.tiers
            .iter()
            .any(|tier| tier.packages.contains(&package_name.to_string()))
    }

    /// Iterate over all packages in publishing order
    pub fn ordered_packages(&self) -> impl Iterator<Item = &String> {
        self.tiers.iter().flat_map(|tier| tier.packages.iter())
    }
}

impl PublishTier {
    /// Check if this tier contains the specified package
    pub fn contains(&self, package_name: &str) -> bool {
        self.packages.contains(&package_name.to_string())
    }

    /// Get the number of packages in this tier
    pub fn package_count(&self) -> usize {
        self.packages.len()
    }

    /// Check if this tier can be published in parallel
    pub fn is_parallel_publishable(&self) -> bool {
        self.packages.len() > 1
    }
}