qg/src/registry.rs - pigweed/qg - Git at Google

 // 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
 // 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 std::{
     collections::{HashMap, HashSet},
     fmt,
     sync::Arc,
 };

 use fixedbitset::FixedBitSet;
 use petgraph::{
     dot::{self, Dot},
     graph::{Neighbors, NodeIndex},
     visit::Dfs,
     Directed, Direction, Graph,
 };

 use crate::{
     project::{
         manifest::{self, Manifest},
         File,
     },
     target::{Provider, Target},
     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, "")
     }
 }

 /// An identifier for a node in the dependency graph.
 pub type NodeId = NodeIndex<u32>;

 /// An iterator of target dependencies.
 pub struct Dependencies<'a> {
     registry: &'a Registry,
     dfs: Dfs<NodeIndex, FixedBitSet>,
 }

 impl<'a> Iterator for Dependencies<'a> {
     type Item = &'a Dependency;

     fn next(&mut self) -> Option<Self::Item> {
         self.dfs
             .next(&self.registry.dependency_graph)
             .and_then(|node_id| self.registry.dependency_graph.node_weight(node_id))
     }
 }

 /// A database of packages known to `qg`.
 #[derive(Debug)]
 pub struct Registry {
     /// Mapping of package slug to package. Slugs are globally unique.
     targets: HashMap<String, Arc<Target>>,

     /// All known package providers by name.
     providers: HashMap<String, Provider>,

     /// 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, NodeId>,
 }

 impl Registry {
     /// Initializes an empty package registry.
     #[must_use]
     pub fn new() -> Self {
         Self {
             targets: HashMap::new(),
             providers: HashMap::new(),
             unresolved_dependencies: HashSet::new(),
             dependency_graph: Graph::new(),
             node_id_map: HashMap::new(),
         }
     }

     /// Reads `qg` manifest files starting from the project root into a registry
     /// of available packages.
     ///
     /// # Errors
     /// Returns an error if manifest files could not be read or are improperly
     /// structured.
     pub fn parse_manifests(root_manifest_file: &File) -> Result<Self> {
         let root_manifest = root_manifest_file.deserialize_toml::<Manifest>()?;
         let mut registry = Registry::new();

         let project_provider = Provider::new(
             &root_manifest.project.name,
             root_manifest_file.path(),
             false,
         );
         registry.add_provider(project_provider)?;

         for (name, target) in root_manifest.targets {
             registry.add_target(crate::Target::from_manifest(
                 &name,
                 &root_manifest.project.name,
                 target.namespace.is_global(),
                 target,
             )?)?;
         }

         for (provider, desc) in &root_manifest.providers {
             if let Some(manifest) = &desc.manifest {
                 let provider_file = root_manifest_file.relative_file(manifest);

                 let provider_data = provider_file.deserialize_toml::<manifest::ProviderFile>()?;
                 let global_provider = if let Some(desc) = &provider_data.provider {
                     desc.namespace.is_global()
                 } else {
                     false
                 };

                 registry.add_provider(Provider::new(
                     provider,
                     provider_file.path(),
                     global_provider,
                 ))?;

                 for (name, target) in provider_data.targets {
                     registry.add_target(crate::Target::from_manifest(
                         &name,
                         provider,
                         global_provider || target.namespace.is_global(),
                         target,
                     )?)?;
                 }
             }
         }

         Ok(registry)
     }

     /// Returns the number of registered targets.
     #[must_use]
     pub fn target_count(&self) -> usize {
         self.targets.len()
     }

     /// Returns an iterator over all known targets, in arbitrary order.
     pub fn targets(&self) -> impl Iterator<Item = &Target> {
         self.targets.values().map(Arc::as_ref)
     }

     /// Registers a new provider.
     pub(crate) fn add_provider(&mut self, provider: Provider) -> Result<()> {
         if self.providers.contains_key(&provider.name) {
             // TODO(frolv): Provider names must be unique.
             return Err(Error::GenericErrorPlaceholder);
         }
         self.providers.insert(provider.name.clone(), provider);
         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()) {
             // TODO(frolv): Target must have a known provider.
             return Err(Error::GenericErrorPlaceholder);
         };

         let target_name = target.full_name();
         for dep in target
             .dependencies()
             .filter(|&d| !self.targets.contains_key(d))
         {
             self.unresolved_dependencies.insert(dep.into());
         }

         self.unresolved_dependencies.remove(&target_name);

         let target = Arc::new(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 build target with the specified name, if it exists.
     ///
     /// # Errors
     /// Returns an error if the named target does not exist or is an unresolved
     /// dependency.
     pub fn get_target(&self, name: &str) -> Result<Arc<Target>> {
         self.get_node_id(name)
             .and_then(|id| self.get_target_by_id(id))
     }

     /// 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<NodeId> {
         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: NodeId) -> Neighbors<Edge, u32> {
         self.dependency_graph
             .neighbors_directed(node, Direction::Outgoing)
     }

     /// Returns the `Target` associated with the `node_id`.
     ///
     /// # Errors
     /// Returns an error if:
     /// - `node_id` does not refer to a valid node in the dependency graph.
     /// - the referenced node is an unresolved dependency.
     pub fn get_target_by_id(&self, node_id: NodeId) -> Result<Arc<Target>> {
         let target = self.dependency_graph.node_weight(node_id).ok_or(
             // Node not found.
             Error::GenericErrorPlaceholder,
         )?;
         match target {
             Dependency::Resolved(target) => Ok(target.clone()),
             Dependency::Unresolved(_) => Err(Error::GenericErrorPlaceholder),
         }
     }

     /// Returns an iterator for traversing a target's transitive dependencies.
     ///
     /// # Errors
     /// Returns an error if `target_name` does not name a valid target.
     #[allow(unused)]
     pub fn transitive_dependencies(&self, target_name: &str) -> Result<Dependencies> {
         let node_id = self.get_node_id(target_name)?;
         let dfs = Dfs::new(&self.dependency_graph, node_id);

         Ok(Dependencies {
             registry: self,
             dfs,
         })
     }
 }

 impl Default for Registry {
     fn default() -> Self {
         Self::new()
     }
 }
	// 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
	// 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 std::{
	collections::{HashMap, HashSet},
	fmt,
	sync::Arc,
	};

	use fixedbitset::FixedBitSet;
	use petgraph::{
	dot::{self, Dot},
	graph::{Neighbors, NodeIndex},
	visit::Dfs,
	Directed, Direction, Graph,
	};

	use crate::{
	project::{
	manifest::{self, Manifest},
	File,
	},
	target::{Provider, Target},
	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, "")
	}
	}

	/// An identifier for a node in the dependency graph.
	pub type NodeId = NodeIndex<u32>;

	/// An iterator of target dependencies.
	pub struct Dependencies<'a> {
	registry: &'a Registry,
	dfs: Dfs<NodeIndex, FixedBitSet>,
	}

	impl<'a> Iterator for Dependencies<'a> {
	type Item = &'a Dependency;

	fn next(&mut self) -> Option<Self::Item> {
	self.dfs
	.next(&self.registry.dependency_graph)
	.and_then(\|node_id\| self.registry.dependency_graph.node_weight(node_id))
	}
	}

	/// A database of packages known to `qg`.
	#[derive(Debug)]
	pub struct Registry {
	/// Mapping of package slug to package. Slugs are globally unique.
	targets: HashMap<String, Arc<Target>>,

	/// All known package providers by name.
	providers: HashMap<String, Provider>,

	/// 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, NodeId>,
	}

	impl Registry {
	/// Initializes an empty package registry.
	#[must_use]
	pub fn new() -> Self {
	Self {
	targets: HashMap::new(),
	providers: HashMap::new(),
	unresolved_dependencies: HashSet::new(),
	dependency_graph: Graph::new(),
	node_id_map: HashMap::new(),
	}
	}

	/// Reads `qg` manifest files starting from the project root into a registry
	/// of available packages.
	///
	/// # Errors
	/// Returns an error if manifest files could not be read or are improperly
	/// structured.
	pub fn parse_manifests(root_manifest_file: &File) -> Result<Self> {
	let root_manifest = root_manifest_file.deserialize_toml::<Manifest>()?;
	let mut registry = Registry::new();

	let project_provider = Provider::new(
	&root_manifest.project.name,
	root_manifest_file.path(),
	false,
	);
	registry.add_provider(project_provider)?;

	for (name, target) in root_manifest.targets {
	registry.add_target(crate::Target::from_manifest(
	&name,
	&root_manifest.project.name,
	target.namespace.is_global(),
	target,
	)?)?;
	}

	for (provider, desc) in &root_manifest.providers {
	if let Some(manifest) = &desc.manifest {
	let provider_file = root_manifest_file.relative_file(manifest);

	let provider_data = provider_file.deserialize_toml::<manifest::ProviderFile>()?;
	let global_provider = if let Some(desc) = &provider_data.provider {
	desc.namespace.is_global()
	} else {
	false
	};

	registry.add_provider(Provider::new(
	provider,
	provider_file.path(),
	global_provider,
	))?;

	for (name, target) in provider_data.targets {
	registry.add_target(crate::Target::from_manifest(
	&name,
	provider,
	global_provider \|\| target.namespace.is_global(),
	target,
	)?)?;
	}
	}
	}

	Ok(registry)
	}

	/// Returns the number of registered targets.
	#[must_use]
	pub fn target_count(&self) -> usize {
	self.targets.len()
	}

	/// Returns an iterator over all known targets, in arbitrary order.
	pub fn targets(&self) -> impl Iterator<Item = &Target> {
	self.targets.values().map(Arc::as_ref)
	}

	/// Registers a new provider.
	pub(crate) fn add_provider(&mut self, provider: Provider) -> Result<()> {
	if self.providers.contains_key(&provider.name) {
	// TODO(frolv): Provider names must be unique.
	return Err(Error::GenericErrorPlaceholder);
	}
	self.providers.insert(provider.name.clone(), provider);
	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()) {
	// TODO(frolv): Target must have a known provider.
	return Err(Error::GenericErrorPlaceholder);
	};

	let target_name = target.full_name();
	for dep in target
	.dependencies()
	.filter(\|&d\| !self.targets.contains_key(d))
	{
	self.unresolved_dependencies.insert(dep.into());
	}

	self.unresolved_dependencies.remove(&target_name);

	let target = Arc::new(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 build target with the specified name, if it exists.
	///
	/// # Errors
	/// Returns an error if the named target does not exist or is an unresolved
	/// dependency.
	pub fn get_target(&self, name: &str) -> Result<Arc<Target>> {
	self.get_node_id(name)
	.and_then(\|id\| self.get_target_by_id(id))
	}

	/// 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<NodeId> {
	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: NodeId) -> Neighbors<Edge, u32> {
	self.dependency_graph
	.neighbors_directed(node, Direction::Outgoing)
	}

	/// Returns the `Target` associated with the `node_id`.
	///
	/// # Errors
	/// Returns an error if:
	/// - `node_id` does not refer to a valid node in the dependency graph.
	/// - the referenced node is an unresolved dependency.
	pub fn get_target_by_id(&self, node_id: NodeId) -> Result<Arc<Target>> {
	let target = self.dependency_graph.node_weight(node_id).ok_or(
	// Node not found.
	Error::GenericErrorPlaceholder,
	)?;
	match target {
	Dependency::Resolved(target) => Ok(target.clone()),
	Dependency::Unresolved(_) => Err(Error::GenericErrorPlaceholder),
	}
	}

	/// Returns an iterator for traversing a target's transitive dependencies.
	///
	/// # Errors
	/// Returns an error if `target_name` does not name a valid target.
	#[allow(unused)]
	pub fn transitive_dependencies(&self, target_name: &str) -> Result<Dependencies> {
	let node_id = self.get_node_id(target_name)?;
	let dfs = Dfs::new(&self.dependency_graph, node_id);

	Ok(Dependencies {
	registry: self,
	dfs,
	})
	}
	}

	impl Default for Registry {
	fn default() -> Self {
	Self::new()
	}
	}