diff --git a/Cargo.lock b/Cargo.lock index 2369ff25141b8..8048a3b173f92 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -3819,12 +3819,12 @@ dependencies = [ [[package]] name = "petgraph" -version = "0.6.3" +version = "0.6.5" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "4dd7d28ee937e54fe3080c91faa1c3a46c06de6252988a7f4592ba2310ef22a4" +checksum = "b4c5cc86750666a3ed20bdaf5ca2a0344f9c67674cae0515bec2da16fbaa47db" dependencies = [ "fixedbitset", - "indexmap 1.9.3", + "indexmap 2.2.6", ] [[package]] diff --git a/Cargo.toml b/Cargo.toml index c8dfd610286f6..b82a1ee342023 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -127,7 +127,7 @@ oxc_resolver = { version = "2.1.0" } parking_lot = "0.12.1" path-clean = "1.0.1" pathdiff = "0.2.1" -petgraph = "0.6.3" +petgraph = "0.6.5" pin-project-lite = "0.2.9" port_scanner = "0.1.5" predicates = "2.1.5" diff --git a/crates/turborepo-lib/src/query/mod.rs b/crates/turborepo-lib/src/query/mod.rs index 037470493388c..34bdf06103037 100644 --- a/crates/turborepo-lib/src/query/mod.rs +++ b/crates/turborepo-lib/src/query/mod.rs @@ -2,6 +2,7 @@ mod boundaries; mod external_package; mod file; mod package; +mod package_graph; mod server; mod task; @@ -15,6 +16,7 @@ use async_graphql::{http::GraphiQLSource, *}; use axum::{response, response::IntoResponse}; use external_package::ExternalPackage; use package::Package; +use package_graph::{Edge, PackageGraph}; pub use server::run_server; use thiserror::Error; use tokio::select; @@ -153,6 +155,7 @@ impl RepositoryQuery { #[graphql(concrete(name = "Files", params(File)))] #[graphql(concrete(name = "ExternalPackages", params(ExternalPackage)))] #[graphql(concrete(name = "Diagnostics", params(Diagnostic)))] +#[graphql(concrete(name = "Edges", params(Edge)))] pub struct Array { items: Vec, length: usize, @@ -571,6 +574,14 @@ impl RepositoryQuery { } } + async fn package_graph( + &self, + center: Option, + filter: Option, + ) -> PackageGraph { + PackageGraph::new(self.run.clone(), center, filter) + } + async fn file(&self, path: String) -> Result { let abs_path = AbsoluteSystemPathBuf::from_unknown(self.run.repo_root(), path); diff --git a/crates/turborepo-lib/src/query/package_graph.rs b/crates/turborepo-lib/src/query/package_graph.rs index 8b137891791fe..b1526a945f1b2 100644 --- a/crates/turborepo-lib/src/query/package_graph.rs +++ b/crates/turborepo-lib/src/query/package_graph.rs @@ -1 +1,154 @@ +use std::sync::Arc; +use async_graphql::{Object, SimpleObject}; +use itertools::Itertools; +use petgraph::graph::NodeIndex; +use turborepo_repository::package_graph::{PackageName, PackageNode}; + +use crate::{ + query::{package::Package, Array, Error, PackagePredicate}, + run::Run, +}; + +pub struct PackageGraph { + run: Arc, + center: Option, + filter: Option, +} + +impl PackageGraph { + pub fn new(run: Arc, center: Option, filter: Option) -> Self { + let center = center.map(|center| PackageNode::Workspace(PackageName::from(center))); + + Self { + run, + center, + filter, + } + } +} + +#[derive(Clone)] +pub(crate) struct Node { + idx: NodeIndex, + run: Arc, +} + +#[derive(Debug, Clone, SimpleObject, Hash, PartialEq, Eq)] +pub(crate) struct Edge { + source: String, + target: String, +} + +#[Object] +impl PackageGraph { + async fn nodes(&self) -> Result, Error> { + let direct_dependencies = self + .center + .as_ref() + .and_then(|center| self.run.pkg_dep_graph().immediate_dependencies(center)); + + let mut nodes = self + .run + .pkg_dep_graph() + .node_indices() + .filter_map(|idx| { + let package_node = self.run.pkg_dep_graph().get_package_by_index(idx)?; + if let Some(center) = &self.center { + if center == package_node { + return Some(Package::new( + self.run.clone(), + package_node.as_package_name().clone(), + )); + } + } + + if matches!(package_node, PackageNode::Root) + || matches!(package_node, PackageNode::Workspace(PackageName::Root)) + { + return None; + } + if let Some(dependencies) = direct_dependencies.as_ref() { + if !dependencies.contains(package_node) { + return None; + } + } + + let package = + match Package::new(self.run.clone(), package_node.as_package_name().clone()) { + Ok(package) => package, + Err(err) => { + return Some(Err(err)); + } + }; + + if let Some(filter) = &self.filter { + if !filter.check(&package) { + return None; + } + } + + Some(Ok(package)) + }) + .collect::, _>>()?; + + nodes.sort_by(|a, b| a.get_name().cmp(b.get_name())); + + Ok(nodes) + } + + async fn edges(&self) -> Array { + let direct_dependencies = self + .center + .as_ref() + .and_then(|center| self.run.pkg_dep_graph().immediate_dependencies(center)); + self.run + .pkg_dep_graph() + .edges() + .iter() + .filter_map(|edge| { + if edge.source() == edge.target() { + return None; + } + let source_node = self + .run + .pkg_dep_graph() + .get_package_by_index(edge.source())?; + let target_node = self + .run + .pkg_dep_graph() + .get_package_by_index(edge.target())?; + + if matches!( + source_node, + PackageNode::Root | PackageNode::Workspace(PackageName::Root) + ) || matches!( + target_node, + PackageNode::Root | PackageNode::Workspace(PackageName::Root) + ) { + return None; + } + + if let Some(center) = &self.center { + if center == source_node || center == target_node { + return Some(Edge { + source: source_node.as_package_name().to_string(), + target: target_node.as_package_name().to_string(), + }); + } + } + if let Some(dependencies) = direct_dependencies.as_ref() { + if !dependencies.contains(source_node) || !dependencies.contains(target_node) { + return None; + } + } + + Some(Edge { + source: source_node.as_package_name().to_string(), + target: target_node.as_package_name().to_string(), + }) + }) + .dedup() + .collect() + } +} diff --git a/crates/turborepo-repository/src/package_graph/mod.rs b/crates/turborepo-repository/src/package_graph/mod.rs index aae4acd04e514..446332aef78dc 100644 --- a/crates/turborepo-repository/src/package_graph/mod.rs +++ b/crates/turborepo-repository/src/package_graph/mod.rs @@ -4,6 +4,7 @@ use std::{ }; use itertools::Itertools; +use petgraph::graph::{Edge, NodeIndex}; use serde::Serialize; use tracing::debug; use turbopath::{ @@ -219,10 +220,26 @@ impl PackageGraph { self.packages.get(package) } + pub fn get_package_by_index(&self, index: NodeIndex) -> Option<&PackageNode> { + self.graph.node_weight(index) + } + + pub fn node_indices(&self) -> impl Iterator { + self.graph.node_indices() + } + + pub fn edges(&self) -> &[Edge<()>] { + self.graph.raw_edges() + } + pub fn packages(&self) -> impl Iterator { self.packages.iter() } + pub fn get_page_rank(&self) -> Vec { + petgraph::algo::page_rank::page_rank(&self.graph, 0.85, 1) + } + pub fn root_package_json(&self) -> &PackageJson { self.package_json(&PackageName::Root) .expect("package graph was built without root package.json") diff --git a/crates/turborepo/tests/query.rs b/crates/turborepo/tests/query.rs index 4bc695744e6df..baa96f068170b 100644 --- a/crates/turborepo/tests/query.rs +++ b/crates/turborepo/tests/query.rs @@ -9,6 +9,7 @@ fn test_query() -> Result<(), anyhow::Error> { "get package that doesn't exist" => "query { package(name: \"doesnotexist\") { path } }", "get packages with less than 1 dependents" => "query { packages(filter: {lessThan: {field: DIRECT_DEPENDENT_COUNT, value: 1}}) { items { name directDependents { length } } } }", "get packages with more than 0 dependents" => "query { packages(filter: {greaterThan: {field: DIRECT_DEPENDENT_COUNT, value: 0}}) { items { name directDependents { length } } } }", + "get package graph" => "query { packageGraph { nodes { items { name } } edges { items { source target } } } }", ); Ok(()) diff --git a/crates/turborepo/tests/snapshots/query__basic_monorepo_get_package_graph_(npm@10.5.0).snap b/crates/turborepo/tests/snapshots/query__basic_monorepo_get_package_graph_(npm@10.5.0).snap new file mode 100644 index 0000000000000..f8b234e7247e8 --- /dev/null +++ b/crates/turborepo/tests/snapshots/query__basic_monorepo_get_package_graph_(npm@10.5.0).snap @@ -0,0 +1,31 @@ +--- +source: crates/turborepo/tests/query.rs +expression: query_output +--- +{ + "data": { + "packageGraph": { + "nodes": { + "items": [ + { + "name": "another" + }, + { + "name": "my-app" + }, + { + "name": "util" + } + ] + }, + "edges": { + "items": [ + { + "source": "my-app", + "target": "util" + } + ] + } + } + } +}