pubsat 0.1.0

//! Dependency-graph types.
//!
//! The graph is a directed graph (petgraph-backed) whose nodes are
//! `(package, optional-version)` pairs and whose edges carry a
//! version-set constraint plus a [`DependencyType`] tag
//! (runtime / dev / peer / optional).
//!
//! Callers populate this graph through the [`builder`](crate::builder)
//! module (which fans out registry fetches and walks the dep tree)
//! or by hand for tests and specialized workflows. The encoder
//! reads the graph to produce a [`SatProblem`](crate::sat::SatProblem).
//!
//! `DependencyNode` is intentionally lean — just name and optional
//! version. Callers who need per-node side metadata (workspace
//! paths, install hints, custom flags) should keep a parallel map
//! keyed by [`petgraph::graph::NodeIndex`] rather than expecting
//! the graph type to carry it. This keeps the graph type
//! ecosystem-neutral.

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

use petgraph::graph::{EdgeIndex, NodeIndex};
use petgraph::visit::EdgeRef;
use petgraph::{Direction, Graph};
use semver::Version;
use serde::{Deserialize, Serialize};

use crate::version::VersionSet;

/// The kind of relationship a dependency edge represents.
///
/// `Runtime`, `Development`, `Peer`, and `Optional` correspond
/// (loosely) to the dependency buckets most package ecosystems
/// distinguish. Callers can decide which kinds to actually walk
/// during graph building via [`GraphBuildConfig`].
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub enum DependencyType {
    Runtime,
    Development,
    Peer,
    Optional,
}

impl fmt::Display for DependencyType {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Runtime => write!(f, "runtime"),
            Self::Development => write!(f, "dev"),
            Self::Peer => write!(f, "peer"),
            Self::Optional => write!(f, "optional"),
        }
    }
}

/// A node in the dependency graph.
///
/// `version` is `Some(v)` once a concrete version has been chosen
/// (either pre-pinned by the caller or filled in by the resolver)
/// and `None` while the node is still a placeholder representing
/// "some satisfying version of this package, to be picked".
#[derive(Debug, Clone)]
pub struct DependencyNode {
    pub name: String,
    pub version: Option<Version>,
}

impl DependencyNode {
    pub fn new<N: Into<String>>(name: N) -> Self {
        Self {
            name: name.into(),
            version: None,
        }
    }

    pub fn with_version<N: Into<String>>(name: N, version: Version) -> Self {
        Self {
            name: name.into(),
            version: Some(version),
        }
    }

    /// `"name@version"` if version is known; otherwise just the name.
    pub fn identifier(&self) -> String {
        match &self.version {
            Some(v) => format!("{}@{}", self.name, v),
            None => self.name.clone(),
        }
    }
}

/// A dependency edge in the graph: which kind of dep, what
/// version-range satisfies it, and whether it's optional.
#[derive(Debug, Clone)]
pub struct DependencyEdge {
    pub dependency_type: DependencyType,
    pub version_set: VersionSet,
    pub optional: bool,
}

impl DependencyEdge {
    pub fn new(dependency_type: DependencyType, version_set: VersionSet) -> Self {
        Self {
            dependency_type,
            version_set,
            optional: dependency_type == DependencyType::Optional,
        }
    }

    pub fn optional(dependency_type: DependencyType, version_set: VersionSet) -> Self {
        Self {
            dependency_type,
            version_set,
            optional: true,
        }
    }
}

/// One detected dependency cycle.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CircularDependency {
    pub cycle: Vec<String>,
    pub edge_types: Vec<DependencyType>,
}

/// Configuration knobs for graph construction.
#[derive(Debug, Clone)]
pub struct GraphBuildConfig {
    pub include_dev_dependencies: bool,
    pub include_optional_dependencies: bool,
    pub include_peer_dependencies: bool,
    /// Maximum recursive walk depth; `0` means unlimited.
    pub max_depth: usize,
    /// If `false`, the builder treats detected cycles as an error.
    pub allow_cycles: bool,
}

impl Default for GraphBuildConfig {
    fn default() -> Self {
        Self {
            include_dev_dependencies: false,
            include_optional_dependencies: true,
            include_peer_dependencies: true,
            max_depth: 0,
            allow_cycles: false,
        }
    }
}

/// A dependency graph: petgraph-backed DAG (or DG-with-cycles)
/// of [`DependencyNode`] linked by [`DependencyEdge`].
#[derive(Debug, Clone)]
pub struct DependencyGraph {
    graph: Graph<DependencyNode, DependencyEdge>,
    node_indices: HashMap<String, NodeIndex>,
    config: GraphBuildConfig,
    circular_dependencies: Vec<CircularDependency>,
}

impl DependencyGraph {
    pub fn new(config: GraphBuildConfig) -> Self {
        Self {
            graph: Graph::new(),
            node_indices: HashMap::new(),
            config,
            circular_dependencies: Vec::new(),
        }
    }

    /// Add a node. If a node with this name already exists, its
    /// existing `NodeIndex` is returned and no new node is inserted —
    /// the graph keeps one node per package name.
    pub fn add_node(&mut self, node: DependencyNode) -> NodeIndex {
        if let Some(&existing) = self.node_indices.get(&node.name) {
            return existing;
        }
        let name = node.name.clone();
        let index = self.graph.add_node(node);
        self.node_indices.insert(name, index);
        index
    }

    pub fn get_node(&self, name: &str) -> Option<NodeIndex> {
        self.node_indices.get(name).copied()
    }

    pub fn node_data(&self, index: NodeIndex) -> Option<&DependencyNode> {
        self.graph.node_weight(index)
    }

    pub fn node_data_mut(&mut self, index: NodeIndex) -> Option<&mut DependencyNode> {
        self.graph.node_weight_mut(index)
    }

    pub fn add_edge(&mut self, from: NodeIndex, to: NodeIndex, edge: DependencyEdge) -> EdgeIndex {
        self.graph.add_edge(from, to, edge)
    }

    pub fn dependencies(&self, node: NodeIndex) -> Vec<(NodeIndex, &DependencyEdge)> {
        self.graph
            .edges_directed(node, Direction::Outgoing)
            .map(|edge| (edge.target(), edge.weight()))
            .collect()
    }

    pub fn dependents(&self, node: NodeIndex) -> Vec<(NodeIndex, &DependencyEdge)> {
        self.graph
            .edges_directed(node, Direction::Incoming)
            .map(|edge| (edge.source(), edge.weight()))
            .collect()
    }

    pub fn all_nodes(&self) -> Vec<NodeIndex> {
        self.graph.node_indices().collect()
    }

    pub fn package_count(&self) -> usize {
        self.graph.node_count()
    }

    pub fn dependency_count(&self) -> usize {
        self.graph.edge_count()
    }

    /// DFS-based cycle detection. Re-runs on every call; the
    /// detected cycles are also cached for [`Self::circular_dependencies`].
    pub fn detect_cycles(&mut self) -> &[CircularDependency] {
        self.circular_dependencies.clear();

        let mut visited = HashSet::new();
        let mut rec_stack = HashSet::new();
        let mut path = Vec::new();

        for node in self.graph.node_indices() {
            if !visited.contains(&node) {
                self.dfs_cycle_detection(node, &mut visited, &mut rec_stack, &mut path);
            }
        }

        &self.circular_dependencies
    }

    fn dfs_cycle_detection(
        &mut self,
        node: NodeIndex,
        visited: &mut HashSet<NodeIndex>,
        rec_stack: &mut HashSet<NodeIndex>,
        path: &mut Vec<NodeIndex>,
    ) {
        visited.insert(node);
        rec_stack.insert(node);
        path.push(node);

        let targets: Vec<_> = self
            .graph
            .edges_directed(node, Direction::Outgoing)
            .map(|edge| edge.target())
            .collect();

        for target in targets {
            if !visited.contains(&target) {
                self.dfs_cycle_detection(target, visited, rec_stack, path);
            } else if rec_stack.contains(&target) {
                if let Some(cycle_start) = path.iter().position(|&n| n == target) {
                    let cycle_nodes = &path[cycle_start..];
                    let mut cycle = Vec::new();
                    let mut edge_types = Vec::new();

                    for &node_idx in cycle_nodes {
                        if let Some(node_data) = self.graph.node_weight(node_idx) {
                            cycle.push(node_data.name.clone());
                        }
                    }

                    for i in 0..cycle_nodes.len() {
                        let from = cycle_nodes[i];
                        let to = cycle_nodes[(i + 1) % cycle_nodes.len()];

                        if let Some(edge) = self.graph.find_edge(from, to) {
                            if let Some(edge_data) = self.graph.edge_weight(edge) {
                                edge_types.push(edge_data.dependency_type);
                            }
                        }
                    }

                    self.circular_dependencies
                        .push(CircularDependency { cycle, edge_types });
                }
            }
        }

        path.pop();
        rec_stack.remove(&node);
    }

    pub fn circular_dependencies(&self) -> &[CircularDependency] {
        &self.circular_dependencies
    }

    pub fn has_cycles(&self) -> bool {
        !self.circular_dependencies.is_empty()
    }

    /// Topological sort. Returns `Err` if the graph has a cycle.
    /// Caller is responsible for calling [`Self::detect_cycles`]
    /// first if they want the cycle list populated.
    pub fn topological_sort(&self) -> Result<Vec<NodeIndex>, Vec<CircularDependency>> {
        if self.has_cycles() {
            return Err(self.circular_dependencies.clone());
        }
        petgraph::algo::toposort(&self.graph, None).map_err(|_| self.circular_dependencies.clone())
    }

    /// Nodes that are the *target* of an edge with the given dep type.
    /// Deduplicated and sorted by `NodeIndex` for deterministic output.
    pub fn packages_by_type(&self, dep_type: DependencyType) -> Vec<NodeIndex> {
        let mut result: Vec<NodeIndex> = self
            .graph
            .edge_references()
            .filter(|e| e.weight().dependency_type == dep_type)
            .map(|e| e.target())
            .collect();
        result.sort_unstable();
        result.dedup();
        result
    }

    /// BFS distance of every node from a root node (a node with no
    /// incoming edges). If a node is unreachable from any root, it's
    /// not included in the result.
    pub fn package_depths(&self) -> HashMap<NodeIndex, usize> {
        let mut depths = HashMap::new();
        let mut queue = VecDeque::new();

        for node in self.graph.node_indices() {
            let has_incoming = self
                .graph
                .edges_directed(node, Direction::Incoming)
                .next()
                .is_some();
            if !has_incoming {
                depths.insert(node, 0);
                queue.push_back((node, 0));
            }
        }

        while let Some((current, depth)) = queue.pop_front() {
            for edge in self.graph.edges_directed(current, Direction::Outgoing) {
                let target = edge.target();
                let new_depth = depth + 1;
                if depths
                    .get(&target)
                    .is_none_or(|&existing| existing > new_depth)
                {
                    depths.insert(target, new_depth);
                    queue.push_back((target, new_depth));
                }
            }
        }

        depths
    }

    /// Render the graph as Graphviz DOT for visualization.
    pub fn to_dot(&self) -> String {
        use std::fmt::Write;

        let mut dot = String::new();
        writeln!(&mut dot, "digraph DependencyGraph {{").unwrap();
        writeln!(&mut dot, "  rankdir=LR;").unwrap();
        writeln!(&mut dot, "  node [shape=box];").unwrap();

        for node in self.graph.node_indices() {
            if let Some(node_data) = self.graph.node_weight(node) {
                let label = match &node_data.version {
                    Some(v) => format!("{}\\nv{}", node_data.name, v),
                    None => node_data.name.clone(),
                };
                writeln!(&mut dot, "  {} [label=\"{}\"];", node.index(), label).unwrap();
            }
        }

        for edge in self.graph.edge_references() {
            let edge_data = edge.weight();
            let color = match edge_data.dependency_type {
                DependencyType::Runtime => "black",
                DependencyType::Development => "blue",
                DependencyType::Peer => "red",
                DependencyType::Optional => "gray",
            };
            let style = if edge_data.optional {
                "dashed"
            } else {
                "solid"
            };
            writeln!(
                &mut dot,
                "  {} -> {} [color={},style={},label=\"{}\"];",
                edge.source().index(),
                edge.target().index(),
                color,
                style,
                edge_data.dependency_type,
            )
            .unwrap();
        }

        writeln!(&mut dot, "}}").unwrap();
        dot
    }

    pub fn config(&self) -> &GraphBuildConfig {
        &self.config
    }

    /// Borrow the underlying petgraph. Useful for callers that want
    /// to use petgraph algorithms not exposed through this type's
    /// methods.
    pub fn inner(&self) -> &Graph<DependencyNode, DependencyEdge> {
        &self.graph
    }
}

impl fmt::Display for DependencyGraph {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "DependencyGraph {{")?;
        writeln!(f, "  packages: {}", self.package_count())?;
        writeln!(f, "  dependencies: {}", self.dependency_count())?;
        writeln!(f, "  has_cycles: {}", self.has_cycles())?;

        if !self.circular_dependencies.is_empty() {
            writeln!(f, "  cycles:")?;
            for (i, cycle) in self.circular_dependencies.iter().enumerate() {
                writeln!(f, "    {}: {}", i + 1, cycle.cycle.join(" -> "))?;
            }
        }

        write!(f, "}}")
    }
}

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

    fn exact(major: u64, minor: u64, patch: u64) -> VersionSet {
        VersionSet::exact(Version::new(major, minor, patch))
    }

    #[test]
    fn dependency_node_creation() {
        let node = DependencyNode::new("lodash");
        assert_eq!(node.name, "lodash");
        assert_eq!(node.version, None);
        assert_eq!(node.identifier(), "lodash");

        let pinned = DependencyNode::with_version("lodash", Version::new(4, 17, 21));
        assert_eq!(pinned.identifier(), "lodash@4.17.21");
    }

    #[test]
    fn dependency_edge_creation() {
        let edge = DependencyEdge::new(DependencyType::Runtime, exact(1, 0, 0));
        assert_eq!(edge.dependency_type, DependencyType::Runtime);
        assert!(!edge.optional);

        let optional = DependencyEdge::optional(DependencyType::Runtime, exact(1, 0, 0));
        assert!(optional.optional);

        let auto_optional = DependencyEdge::new(DependencyType::Optional, exact(1, 0, 0));
        assert!(auto_optional.optional);
    }

    #[test]
    fn add_node_dedupes_by_name() {
        let mut graph = DependencyGraph::new(GraphBuildConfig::default());
        let first = graph.add_node(DependencyNode::new("a"));
        let second = graph.add_node(DependencyNode::new("a"));
        assert_eq!(first, second);
        assert_eq!(graph.package_count(), 1);
    }

    #[test]
    fn basic_operations() {
        let mut graph = DependencyGraph::new(GraphBuildConfig::default());
        let a = graph.add_node(DependencyNode::new("a"));
        let b = graph.add_node(DependencyNode::new("b"));

        graph.add_edge(
            a,
            b,
            DependencyEdge::new(DependencyType::Runtime, exact(1, 0, 0)),
        );

        assert_eq!(graph.package_count(), 2);
        assert_eq!(graph.dependency_count(), 1);
        let deps = graph.dependencies(a);
        assert_eq!(deps.len(), 1);
        assert_eq!(deps[0].0, b);
    }

    #[test]
    fn cycle_detection() {
        let mut graph = DependencyGraph::new(GraphBuildConfig::default());
        let a = graph.add_node(DependencyNode::new("a"));
        let b = graph.add_node(DependencyNode::new("b"));
        let c = graph.add_node(DependencyNode::new("c"));
        let edge = DependencyEdge::new(DependencyType::Runtime, exact(1, 0, 0));
        graph.add_edge(a, b, edge.clone());
        graph.add_edge(b, c, edge.clone());
        graph.add_edge(c, a, edge);

        let cycles = graph.detect_cycles();
        assert!(!cycles.is_empty());
        assert!(graph.has_cycles());
    }

    #[test]
    fn topological_sort_on_dag() {
        let mut graph = DependencyGraph::new(GraphBuildConfig::default());
        let a = graph.add_node(DependencyNode::new("a"));
        let b = graph.add_node(DependencyNode::new("b"));
        let c = graph.add_node(DependencyNode::new("c"));
        let edge = DependencyEdge::new(DependencyType::Runtime, exact(1, 0, 0));
        graph.add_edge(a, b, edge.clone());
        graph.add_edge(b, c, edge);

        let order = graph.topological_sort().unwrap();
        assert_eq!(order.len(), 3);
    }

    #[test]
    fn packages_by_type_filters() {
        let mut graph = DependencyGraph::new(GraphBuildConfig::default());
        let a = graph.add_node(DependencyNode::new("a"));
        let b = graph.add_node(DependencyNode::new("b"));
        let c = graph.add_node(DependencyNode::new("c"));
        graph.add_edge(
            a,
            b,
            DependencyEdge::new(DependencyType::Runtime, exact(1, 0, 0)),
        );
        graph.add_edge(
            a,
            c,
            DependencyEdge::new(DependencyType::Development, exact(1, 0, 0)),
        );

        let runtime = graph.packages_by_type(DependencyType::Runtime);
        let dev = graph.packages_by_type(DependencyType::Development);
        assert_eq!(runtime, vec![b]);
        assert_eq!(dev, vec![c]);
    }

    #[test]
    fn package_depths_from_root() {
        let mut graph = DependencyGraph::new(GraphBuildConfig::default());
        let root = graph.add_node(DependencyNode::new("root"));
        let mid = graph.add_node(DependencyNode::new("mid"));
        let leaf = graph.add_node(DependencyNode::new("leaf"));
        let edge = DependencyEdge::new(DependencyType::Runtime, exact(1, 0, 0));
        graph.add_edge(root, mid, edge.clone());
        graph.add_edge(mid, leaf, edge);

        let depths = graph.package_depths();
        assert_eq!(depths.get(&root), Some(&0));
        assert_eq!(depths.get(&mid), Some(&1));
        assert_eq!(depths.get(&leaf), Some(&2));
    }
}