pubsat 0.1.0

//! Dependency-graph builder.
//!
//! [`DependencyGraphBuilder`] walks a dependency tree starting
//! from a caller-supplied root [`VersionMetadata`], fetching each
//! transitively-reachable package's metadata from the registry and
//! adding nodes and edges to a [`DependencyGraph`] as it goes.
//!
//! ## Concurrency
//!
//! Per parent in the walk, the builder fans out registry fetches
//! for all of that parent's unresolved direct dependencies through
//! [`futures::stream::StreamExt::buffer_unordered`] with
//! [`METADATA_FETCH_CONCURRENCY`] in flight at once. Recursion into
//! a child is then serial — the graph is `&mut`-borrowed during
//! mutation — but every level's siblings still fan out in parallel
//! when control returns to that level. The net effect on real npm
//! graphs is the difference between
//! `O(N)` sequential round-trips and `O(D)` where `D` is graph
//! depth — a 5–10× wall-clock improvement on graphs like `express`.
//!
//! ## Version selection
//!
//! The builder picks the *newest* registry version satisfying each
//! constraint as a fast heuristic. The encoder + solver get the
//! authoritative say: the encoder considers every satisfying
//! version of each package (not just the one the builder walked
//! into), and the resolver uses SAT assumptions to express the
//! "prefer newest" preference. The builder's pick is only the
//! *manifest walk seed* — it's the version whose `dependencies`
//! list we recurse through to discover transitive packages.
//!
//! ## What's intentionally not here
//!
//! Workspace handling, progress callbacks, file-system entry
//! points, and lockfile bridging are all caller-domain concerns.
//! See the architecture doc for why.

use std::collections::{BTreeMap, HashSet};
use std::sync::Arc;

use futures::stream::{self, StreamExt};
use semver::Version;

use crate::error::{ResolutionError, ResolutionResult};
use crate::graph::{
    DependencyEdge, DependencyGraph, DependencyNode, DependencyType, GraphBuildConfig,
};
use crate::registry::{PackageRegistry, VersionMetadata};
use crate::version::VersionSet;

/// Maximum concurrent metadata fetches in flight per parent during
/// graph build. Matches typical HTTP/2 multiplexing caps to a single
/// registry origin. Bumping past ~32 hits diminishing returns on
/// most real graphs (which are depth × RTT bound, not breadth-bound).
pub const METADATA_FETCH_CONCURRENCY: usize = 32;

/// Statistics gathered during a graph build.
#[derive(Debug, Default, Clone)]
pub struct BuildStats {
    pub packages_processed: usize,
    pub dependencies_resolved: usize,
    pub registry_queries: usize,
    pub circular_dependencies: usize,
    pub build_duration_ms: u64,
}

#[derive(Debug, Clone, Default)]
struct BuildContext {
    depth: usize,
    /// Names visited in the current recursion path (for cycle detection).
    path: Vec<String>,
}

/// Walks a registry to produce a [`DependencyGraph`].
///
/// Generic over a [`PackageRegistry`] so callers can wrap with
/// [`CachedRegistry`](crate::registry::CachedRegistry) before
/// passing in to share the cache with the resolver layer.
pub struct DependencyGraphBuilder<R: PackageRegistry> {
    registry: Arc<R>,
    config: GraphBuildConfig,
    stats: BuildStats,
}

impl<R: PackageRegistry + 'static> DependencyGraphBuilder<R> {
    pub fn new(registry: Arc<R>) -> Self {
        Self {
            registry,
            config: GraphBuildConfig::default(),
            stats: BuildStats::default(),
        }
    }

    pub fn with_config(registry: Arc<R>, config: GraphBuildConfig) -> Self {
        Self {
            registry,
            config,
            stats: BuildStats::default(),
        }
    }

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

    pub fn stats(&self) -> &BuildStats {
        &self.stats
    }

    /// Borrow the registry the builder is fetching against. Mainly
    /// useful when callers want to share the registry with the
    /// resolver layer for cache reuse.
    pub fn registry(&self) -> &Arc<R> {
        &self.registry
    }

    /// Build a dependency graph rooted at `root`.
    ///
    /// `root` is the entry point — typically a `VersionMetadata`
    /// representing the caller's own package (`my-app@1.0.0` with
    /// its declared dependencies) or a synthetic root that
    /// aggregates a top-level dependency request.
    pub async fn build(&mut self, root: VersionMetadata) -> ResolutionResult<DependencyGraph> {
        let start_time = std::time::Instant::now();
        self.stats = BuildStats::default();

        let mut graph = DependencyGraph::new(self.config.clone());
        let root_node = DependencyNode::with_version(root.name.clone(), root.version.clone());
        let root_index = graph.add_node(root_node);
        self.stats.packages_processed = 1;

        let mut context = BuildContext::default();
        let mut visited_edges: HashSet<String> = HashSet::new();

        self.walk(
            &mut graph,
            root_index,
            &root,
            &mut context,
            &mut visited_edges,
        )
        .await?;

        let cycles = graph.detect_cycles();
        self.stats.circular_dependencies = cycles.len();
        if !cycles.is_empty() && !self.config.allow_cycles {
            let cycle_str = cycles
                .iter()
                .map(|c| c.cycle.join(" -> "))
                .collect::<Vec<_>>()
                .join(", ");
            return Err(ResolutionError::CircularDependency { cycle: cycle_str });
        }

        self.stats.build_duration_ms = start_time.elapsed().as_millis() as u64;
        Ok(graph)
    }

    /// Recursive walk. Each invocation:
    /// 1. (no I/O) Surveys the parent's declared deps that we'd
    ///    need to fetch.
    /// 2. (I/O fanout) Fetches each unresolved dep's metadata
    ///    concurrently.
    /// 3. (no I/O) Applies fetched results to the graph and
    ///    recurses serially into each new node.
    fn walk<'s>(
        &'s mut self,
        graph: &'s mut DependencyGraph,
        parent_index: petgraph::graph::NodeIndex,
        parent_metadata: &'s VersionMetadata,
        context: &'s mut BuildContext,
        visited_edges: &'s mut HashSet<String>,
    ) -> std::pin::Pin<Box<dyn std::future::Future<Output = ResolutionResult<()>> + Send + 's>>
    {
        Box::pin(async move {
            let parent_name = parent_metadata.name.clone();

            if self.config.max_depth > 0 && context.depth >= self.config.max_depth {
                tracing::warn!(
                    "max depth {} reached at package {}",
                    self.config.max_depth,
                    parent_name
                );
                return Ok(());
            }

            if context.path.contains(&parent_name) {
                let cycle = format!("{} -> {}", context.path.join(" -> "), parent_name);
                tracing::warn!("circular dependency on walk path: {}", cycle);
                if !self.config.allow_cycles {
                    return Err(ResolutionError::CircularDependency { cycle });
                }
                return Ok(());
            }

            context.path.push(parent_name.clone());
            context.depth += 1;

            // Phase 1: survey. Build the list of unresolved deps to fetch.
            let dep_groups: Vec<(DependencyType, &BTreeMap<String, VersionSet>)> = vec![
                (DependencyType::Runtime, &parent_metadata.dependencies),
                (DependencyType::Peer, &parent_metadata.peer_dependencies),
                (
                    DependencyType::Optional,
                    &parent_metadata.optional_dependencies,
                ),
            ];

            let mut to_fetch: Vec<(DependencyType, String, VersionSet)> = Vec::new();
            for (dep_type, deps) in dep_groups {
                if !self.should_include_dependency_type(dep_type) {
                    continue;
                }
                for (dep_name, version_set) in deps {
                    let dep_key = format!("{}->{}@{}", parent_name, dep_name, version_set);
                    if !visited_edges.insert(dep_key) {
                        continue;
                    }

                    // If the dep is already a node in the graph, just add the
                    // edge — no fetch needed for the edge itself.
                    if let Some(existing) = graph.get_node(dep_name) {
                        let edge = DependencyEdge::new(dep_type, version_set.clone());
                        graph.add_edge(parent_index, existing, edge);
                        self.stats.dependencies_resolved += 1;
                        continue;
                    }

                    to_fetch.push((dep_type, dep_name.clone(), version_set.clone()));
                }
            }

            // Phase 2: concurrent fetches.
            let registry = self.registry.clone();
            let fetch_results: Vec<(
                DependencyType,
                String,
                VersionSet,
                ResolutionResult<DepFetchResult>,
            )> = stream::iter(to_fetch)
                .map(|(dep_type, dep_name, version_set)| {
                    let registry = registry.clone();
                    let owned_set = version_set.clone();
                    async move {
                        let result = fetch_dep_metadata(registry, &dep_name, &owned_set).await;
                        (dep_type, dep_name, version_set, result)
                    }
                })
                .buffer_unordered(METADATA_FETCH_CONCURRENCY)
                .collect()
                .await;

            self.stats.registry_queries += fetch_results.len();

            // Phase 3: apply + recurse.
            for (dep_type, dep_name, version_set, result) in fetch_results {
                let fetch = match result {
                    Ok(f) => f,
                    Err(e) => {
                        if dep_type == DependencyType::Optional {
                            tracing::debug!(
                                "optional dependency {} failed to resolve: {}",
                                dep_name,
                                e
                            );
                            continue;
                        }
                        return Err(e);
                    }
                };

                // Re-check: a sibling fetched concurrently may have added this package.
                if let Some(existing) = graph.get_node(&dep_name) {
                    let edge = DependencyEdge::new(dep_type, version_set);
                    graph.add_edge(parent_index, existing, edge);
                    self.stats.dependencies_resolved += 1;
                    continue;
                }

                let dep_node =
                    DependencyNode::with_version(dep_name.clone(), fetch.selected_version.clone());
                let dep_index = graph.add_node(dep_node);
                let edge = DependencyEdge::new(dep_type, version_set);
                graph.add_edge(parent_index, dep_index, edge);
                self.stats.packages_processed += 1;
                self.stats.dependencies_resolved += 1;

                let recurse_result = self
                    .walk(graph, dep_index, &fetch.metadata, context, visited_edges)
                    .await;
                if let Err(e) = recurse_result {
                    if dep_type == DependencyType::Optional {
                        tracing::debug!("optional subtree {} failed: {}", dep_name, e);
                    } else {
                        return Err(e);
                    }
                }
            }

            context.path.pop();
            context.depth -= 1;
            Ok(())
        })
    }

    fn should_include_dependency_type(&self, dep_type: DependencyType) -> bool {
        match dep_type {
            DependencyType::Runtime => true,
            DependencyType::Development => self.config.include_dev_dependencies,
            DependencyType::Peer => self.config.include_peer_dependencies,
            DependencyType::Optional => self.config.include_optional_dependencies,
        }
    }
}

struct DepFetchResult {
    selected_version: Version,
    metadata: VersionMetadata,
}

/// Standalone fetch: pick the newest satisfying version, then fetch
/// that version's metadata. Lives outside the `&mut self` impl so it
/// can run concurrently across many deps without borrow-checker
/// trouble.
async fn fetch_dep_metadata<R: PackageRegistry>(
    registry: Arc<R>,
    dep_name: &str,
    version_set: &VersionSet,
) -> ResolutionResult<DepFetchResult> {
    let versions = registry
        .get_satisfying_versions(dep_name, version_set)
        .await?;
    if versions.is_empty() {
        return Err(ResolutionError::PackageNotFound {
            package: dep_name.to_string(),
            version: version_set.to_string(),
        });
    }
    // Newest-wins as the manifest-walk seed; the resolver gets the final
    // word via SAT (see module docs).
    let selected_version = versions.into_iter().max().unwrap();
    let metadata = registry
        .get_version_metadata(dep_name, &selected_version)
        .await?;
    Ok(DepFetchResult {
        selected_version,
        metadata,
    })
}

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

    fn vs(s: &str) -> VersionSet {
        s.parse().unwrap()
    }

    #[tokio::test]
    async fn build_walks_single_dependency() {
        let registry = MockRegistry::new().with_versions("dep", &["1.0.0", "1.1.0"]);
        let mut builder = DependencyGraphBuilder::new(Arc::new(registry));

        let root = VersionMetadata::new("root", Version::new(1, 0, 0))
            .with_dependency("dep", vs("^1.0.0"));
        let graph = builder.build(root).await.unwrap();

        assert_eq!(graph.package_count(), 2);
        assert_eq!(graph.dependency_count(), 1);
        let dep_index = graph.get_node("dep").unwrap();
        assert_eq!(
            graph.node_data(dep_index).unwrap().version,
            Some(Version::new(1, 1, 0)),
            "builder should pick newest satisfying version"
        );
    }

    #[tokio::test]
    async fn build_walks_transitively() {
        let registry = MockRegistry::new()
            .with_versions("a", &["1.0.0"])
            .with_versions("b", &["2.0.0"])
            .with_dependency("a", "1.0.0", "b", vs("^2.0.0"));
        let mut builder = DependencyGraphBuilder::new(Arc::new(registry));

        let root =
            VersionMetadata::new("root", Version::new(1, 0, 0)).with_dependency("a", vs("^1.0.0"));
        let graph = builder.build(root).await.unwrap();

        assert_eq!(graph.package_count(), 3, "root + a + b");
        assert!(graph.get_node("a").is_some());
        assert!(graph.get_node("b").is_some());
    }

    #[tokio::test]
    async fn build_dedupes_diamond_dependencies() {
        // root → a → c
        // root → b → c
        // c should be one node, not two.
        let registry = MockRegistry::new()
            .with_versions("a", &["1.0.0"])
            .with_versions("b", &["1.0.0"])
            .with_versions("c", &["1.0.0"])
            .with_dependency("a", "1.0.0", "c", vs("^1.0.0"))
            .with_dependency("b", "1.0.0", "c", vs("^1.0.0"));
        let mut builder = DependencyGraphBuilder::new(Arc::new(registry));

        let root = VersionMetadata::new("root", Version::new(1, 0, 0))
            .with_dependency("a", vs("^1.0.0"))
            .with_dependency("b", vs("^1.0.0"));
        let graph = builder.build(root).await.unwrap();

        assert_eq!(
            graph.package_count(),
            4,
            "root + a + b + c (one c, not two)"
        );
    }

    #[tokio::test]
    async fn build_errors_on_unreachable_dependency() {
        let registry = MockRegistry::new().with_versions("dep", &["1.0.0"]);
        let mut builder = DependencyGraphBuilder::new(Arc::new(registry));

        let root = VersionMetadata::new("root", Version::new(1, 0, 0))
            .with_dependency("dep", vs("^2.0.0"));
        let err = builder.build(root).await.unwrap_err();
        assert!(matches!(err, ResolutionError::PackageNotFound { .. }));
    }

    #[tokio::test]
    async fn build_tolerates_missing_optional_dep() {
        let registry = MockRegistry::new().with_versions("present", &["1.0.0"]);
        let mut builder = DependencyGraphBuilder::new(Arc::new(registry));

        let mut root = VersionMetadata::new("root", Version::new(1, 0, 0));
        root.dependencies.insert("present".into(), vs("^1.0.0"));
        root.optional_dependencies
            .insert("missing".into(), vs("^1.0.0"));
        let graph = builder.build(root).await.unwrap();

        assert!(graph.get_node("present").is_some());
        assert!(graph.get_node("missing").is_none());
    }

    #[tokio::test]
    async fn build_detects_cycles_and_errors_by_default() {
        // a depends on b, b depends on a.
        let registry = MockRegistry::new()
            .with_versions("a", &["1.0.0"])
            .with_versions("b", &["1.0.0"])
            .with_dependency("a", "1.0.0", "b", vs("^1.0.0"))
            .with_dependency("b", "1.0.0", "a", vs("^1.0.0"));
        let mut builder = DependencyGraphBuilder::new(Arc::new(registry));

        let root =
            VersionMetadata::new("root", Version::new(1, 0, 0)).with_dependency("a", vs("^1.0.0"));
        let err = builder.build(root).await.unwrap_err();
        assert!(matches!(err, ResolutionError::CircularDependency { .. }));
    }

    #[tokio::test]
    async fn build_allows_cycles_when_configured() {
        let registry = MockRegistry::new()
            .with_versions("a", &["1.0.0"])
            .with_versions("b", &["1.0.0"])
            .with_dependency("a", "1.0.0", "b", vs("^1.0.0"))
            .with_dependency("b", "1.0.0", "a", vs("^1.0.0"));
        let config = GraphBuildConfig {
            allow_cycles: true,
            ..Default::default()
        };
        let mut builder = DependencyGraphBuilder::with_config(Arc::new(registry), config);

        let root =
            VersionMetadata::new("root", Version::new(1, 0, 0)).with_dependency("a", vs("^1.0.0"));
        let graph = builder.build(root).await.unwrap();
        assert!(graph.has_cycles());
    }
}