vercel · NicholasLYang · Feb 5, 2025 · Sep 24, 2024 · Sep 30, 2024 · Sep 30, 2024
@@ -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"

@@ -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<T: OutputType> {
     items: Vec<T>,
     length: usize,
@@ -571,6 +574,14 @@ impl RepositoryQuery {
         }
     }
 
+    async fn package_graph(
+        &self,
+        center: Option<String>,
+        filter: Option<PackagePredicate>,
+    ) -> PackageGraph {
+        PackageGraph::new(self.run.clone(), center, filter)
+    }
+
     async fn file(&self, path: String) -> Result<File, Error> {
         let abs_path = AbsoluteSystemPathBuf::from_unknown(self.run.repo_root(), path);
 

@@ -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<Run>,
+    center: Option<PackageNode>,
+    filter: Option<PackagePredicate>,
+}
+
+impl PackageGraph {
+    pub fn new(run: Arc<Run>, center: Option<String>, filter: Option<PackagePredicate>) -> 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<Run>,
+}
+
+#[derive(Debug, Clone, SimpleObject, Hash, PartialEq, Eq)]
+pub(crate) struct Edge {
+    source: String,
+    target: String,
+}
+
+#[Object]
+impl PackageGraph {
+    async fn nodes(&self) -> Result<Array<Package>, 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::<Result<Array<_>, _>>()?;
+
+        nodes.sort_by(|a, b| a.get_name().cmp(b.get_name()));
+
+        Ok(nodes)
+    }
+
+    async fn edges(&self) -> Array<Edge> {
+        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()
+    }
+}
@@ -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<Item = NodeIndex> {
+        self.graph.node_indices()
+    }
+
+    pub fn edges(&self) -> &[Edge<()>] {
+        self.graph.raw_edges()
+    }
+
     pub fn packages(&self) -> impl Iterator<Item = (&PackageName, &PackageInfo)> {
         self.packages.iter()
     }
 
+    pub fn get_page_rank(&self) -> Vec<f64> {
+        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")

@@ -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(())

@@ -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"
+          }
+        ]
+      }
+    }
+  }
+}