Add dependency graph to registry
Change-Id: I6915a82af17bdb256a26fff5e6067c68ee19e3d8
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/qg/+/125198
Reviewed-by: Alexei Frolov <frolv@google.com>
Commit-Queue: Erik Gilling <konkers@google.com>
diff --git a/qg-cli/src/graph.rs b/qg-cli/src/graph.rs
new file mode 100644
index 0000000..d311063
--- /dev/null
+++ b/qg-cli/src/graph.rs
@@ -0,0 +1,30 @@
+// Copyright 2022 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+
+use anyhow::Result;
+use qg::Project;
+use tokio::io::{self, AsyncWriteExt};
+
+/// Dump the dependency graph in graphviz dot format.
+#[derive(clap::Parser, Debug)]
+#[command(about)]
+pub struct Command {}
+
+pub async fn run(_args: &Command) -> Result<()> {
+ let project = Project::locate()?;
+ let graph = project.registry()?.dot_dependency_graph();
+
+ io::stdout().write_all(graph.as_bytes()).await?;
+ Ok(())
+}
diff --git a/qg-cli/src/main.rs b/qg-cli/src/main.rs
index ea1a6d8..41a2414 100644
--- a/qg-cli/src/main.rs
+++ b/qg-cli/src/main.rs
@@ -16,6 +16,7 @@
#![cfg_attr(feature = "strict", deny(warnings))]
#![warn(clippy::pedantic)]
+mod graph;
mod hello;
mod subcommands;
mod target;
diff --git a/qg-cli/src/subcommands.rs b/qg-cli/src/subcommands.rs
index 39bdf66..8d5f42b 100644
--- a/qg-cli/src/subcommands.rs
+++ b/qg-cli/src/subcommands.rs
@@ -14,7 +14,7 @@
use anyhow::Result;
-use crate::{hello, target};
+use crate::{graph, hello, target};
#[cfg(feature = "new_command")]
use crate::new;
@@ -28,6 +28,7 @@
/// struct which derives `clap::Parser` to specify its arguments.
#[derive(clap::Parser, Debug)]
pub enum Subcommands {
+ Graph(graph::Command),
Hello(hello::Command),
Target(target::Command),
@@ -42,6 +43,9 @@
/// Invokes a subcommand with its parsed arguments.
pub async fn run(&self) -> Result<()> {
match self {
+ Self::Graph(args) => {
+ graph::run(args).await?;
+ }
Self::Hello(args) => {
hello::run(args);
}
diff --git a/qg/Cargo.toml b/qg/Cargo.toml
index 182b32f..cb2a8c2 100644
--- a/qg/Cargo.toml
+++ b/qg/Cargo.toml
@@ -11,6 +11,7 @@
futures = "0.3.25"
num-traits = "0.2.15"
once_cell = "1.16.0"
+petgraph = "0.6.2"
regex = "1.7.0"
serde = { version = "1.0.147", features = ["derive"] }
thiserror = "1.0.37"
diff --git a/qg/src/project/mod.rs b/qg/src/project/mod.rs
index 8fe7bb9..af14659 100644
--- a/qg/src/project/mod.rs
+++ b/qg/src/project/mod.rs
@@ -271,6 +271,8 @@
#[cfg(test)]
mod tests {
+ use std::collections::HashSet;
+
use super::*;
#[test]
@@ -354,4 +356,31 @@
// Loads from a project subdirectory fail.
assert!(Project::load("./src/test_projects/simple/subdir/subsubdir").is_err());
}
+
+ #[test]
+ fn simple_dependencies() {
+ let project = Project::load("./src/test_projects/dependency_test").unwrap();
+ assert_eq!(project.name, "dep-test");
+ let registry = project.registry().unwrap();
+ let a_id = registry.get_node_id("dep-test:a").unwrap();
+ let b_id = registry.get_node_id("dep-test:b").unwrap();
+ let c_id = registry.get_node_id("dep-test:c").unwrap();
+ let d_id = registry.get_node_id("dep-test:d").unwrap();
+ let e_id = registry.get_node_id("dep-test:e").unwrap();
+
+ let a_deps: HashSet<_> = registry.node_deps(a_id).collect();
+ assert_eq!(a_deps, [b_id, c_id].into_iter().collect());
+
+ let b_deps: HashSet<_> = registry.node_deps(b_id).collect();
+ assert_eq!(b_deps, [].into_iter().collect());
+
+ let c_deps: HashSet<_> = registry.node_deps(c_id).collect();
+ assert_eq!(c_deps, [d_id, e_id].into_iter().collect());
+
+ let d_deps: HashSet<_> = registry.node_deps(d_id).collect();
+ assert_eq!(d_deps, [].into_iter().collect());
+
+ let e_deps: HashSet<_> = registry.node_deps(e_id).collect();
+ assert_eq!(e_deps, [].into_iter().collect());
+ }
}
diff --git a/qg/src/registry.rs b/qg/src/registry.rs
index 8c3aa74..b75812d 100644
--- a/qg/src/registry.rs
+++ b/qg/src/registry.rs
@@ -1,4 +1,4 @@
-// Copyright 2022 The Pigweed Authors
+// Copyright 2023 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
@@ -14,12 +14,52 @@
use std::{
collections::{HashMap, HashSet},
+ fmt,
sync::Arc,
};
+use petgraph::{
+ dot::{self, Dot},
+ graph::{Neighbors, NodeIndex},
+ Directed, Direction, Graph,
+};
+
use crate::target::{Provider, Target};
use crate::{Error, Result};
+/// A node in the dependency graph.
+#[derive(Debug)]
+pub enum Dependency {
+ /// A resolved dependency.
+ Resolved(Arc<Target>),
+
+ /// An unresolved dependency. This occurs when a target declares a
+ /// dependency for a target that has not been seen.
+ Unresolved(String),
+}
+
+impl fmt::Display for Dependency {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self {
+ Self::Resolved(target) => write!(f, "{}", target.full_name()),
+ Self::Unresolved(name) => write!(f, "{name}"),
+ }
+ }
+}
+
+/// An edge in the dependency graph.
+/// We define an empty struct for edges instead of using the unit type
+/// to allow us to implement `fmt::Display` for it. This is needed for
+/// graphviz output.
+#[derive(Debug)]
+pub struct Edge {}
+
+impl fmt::Display for Edge {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "")
+ }
+}
+
/// A database of packages known to `qg`.
#[derive(Debug)]
pub struct Registry {
@@ -31,6 +71,14 @@
/// Unknown target dependencies.
unresolved_dependencies: HashSet<String>,
+
+ /// Dependency Graph of targets.
+ ///
+ /// Nodes that have a `None` weight are unresolved.
+ dependency_graph: Graph<Dependency, Edge, Directed, u32>,
+
+ /// Map from target full name to dependency graph node IDe.
+ node_id_map: HashMap<String, NodeIndex<u32>>,
}
impl Registry {
@@ -41,6 +89,8 @@
targets: HashMap::new(),
providers: HashMap::new(),
unresolved_dependencies: HashSet::new(),
+ dependency_graph: Graph::new(),
+ node_id_map: HashMap::new(),
}
}
@@ -65,6 +115,15 @@
Ok(())
}
+ /// Returns the dependency graph in graphviz dot format.
+ #[must_use]
+ pub fn dot_dependency_graph(&self) -> String {
+ format!(
+ "{:}",
+ Dot::with_config(&self.dependency_graph, &[dot::Config::EdgeNoLabel])
+ )
+ }
+
/// Inserts a target into the registry.
pub(crate) fn add_target(&mut self, target: Target) -> Result<()> {
if !self.providers.contains_key(target.provider()) {
@@ -73,7 +132,6 @@
};
let target_name = target.full_name();
-
for dep in target
.dependencies()
.filter(|&d| !self.targets.contains_key(d))
@@ -84,10 +142,64 @@
self.unresolved_dependencies.remove(&target_name);
let target = Arc::new(target);
- self.targets.insert(target_name, target);
+ self.update_dependency_graph_for_new_target(&target);
+ self.targets.insert(target_name.clone(), target);
Ok(())
}
+
+ fn update_dependency_graph_for_new_target(&mut self, target: &Arc<Target>) {
+ let target_name = target.full_name();
+
+ let node_id = if let Some(id) = self.node_id_map.get(&target_name) {
+ // If the target is already in the graph, it is because a previous
+ // target as taken an unresolved dependency on it. Update the node
+ // with the resolved target.
+ *self
+ .dependency_graph
+ .node_weight_mut(*id)
+ .expect("node should exist in graph") = Dependency::Resolved(target.clone());
+ *id
+ } else {
+ let id = self
+ .dependency_graph
+ .add_node(Dependency::Resolved(target.clone()));
+ self.node_id_map.insert(target_name, id);
+ id
+ };
+
+ for dep in target.dependencies() {
+ // Get the node id of the dependency. Insert an unresolved
+ // dependency if the node does not already exist.
+ let dep_node_id = *self.node_id_map.entry(dep.to_string()).or_insert_with(|| {
+ self.dependency_graph
+ .add_node(Dependency::Unresolved(dep.to_string()))
+ });
+ self.dependency_graph
+ .add_edge(node_id, dep_node_id, Edge {});
+ }
+ }
+
+ /// Returns the node ID for a node.
+ ///
+ /// # Errors
+ /// Returns an error if the given node name does not exist.
+ pub fn get_node_id(&self, name: &str) -> Result<NodeIndex<u32>> {
+ self.node_id_map
+ .get(name)
+ .ok_or(
+ // Node not found.
+ Error::GenericErrorPlaceholder,
+ )
+ .map(|id| *id)
+ }
+
+ /// Returns an iterator of dependencies for the node.
+ #[must_use]
+ pub fn node_deps(&self, node: NodeIndex<u32>) -> Neighbors<Edge, u32> {
+ self.dependency_graph
+ .neighbors_directed(node, Direction::Outgoing)
+ }
}
impl Default for Registry {
diff --git a/qg/src/test_projects/dependency_test/qg.toml b/qg/src/test_projects/dependency_test/qg.toml
new file mode 100644
index 0000000..b5f2d0c
--- /dev/null
+++ b/qg/src/test_projects/dependency_test/qg.toml
@@ -0,0 +1,25 @@
+[project]
+name = "dep-test"
+
+# a
+# / \
+# b c
+# / \
+# d e
+
+[targets.a]
+type = "dep_only"
+deps = ["dep-test:b", "dep-test:c"]
+
+[targets.b]
+type = "dep_only"
+
+[targets.c]
+type = "dep_only"
+deps = ["dep-test:d", "dep-test:e"]
+
+[targets.d]
+type = "dep_only"
+
+[targets.e]
+type = "dep_only"
diff --git a/qg/src/test_projects/dependency_test/subdir/subsubdir/keepdir b/qg/src/test_projects/dependency_test/subdir/subsubdir/keepdir
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/qg/src/test_projects/dependency_test/subdir/subsubdir/keepdir
