diff options
Diffstat (limited to 'src/tools/cargo/src/cargo/ops/tree/graph.rs')
| -rw-r--r-- | src/tools/cargo/src/cargo/ops/tree/graph.rs | 685 |
1 files changed, 685 insertions, 0 deletions
diff --git a/src/tools/cargo/src/cargo/ops/tree/graph.rs b/src/tools/cargo/src/cargo/ops/tree/graph.rs new file mode 100644 index 000000000..20a9ca0b6 --- /dev/null +++ b/src/tools/cargo/src/cargo/ops/tree/graph.rs @@ -0,0 +1,685 @@ +//! Code for building the graph used by `cargo tree`. + +use super::TreeOptions; +use crate::core::compiler::{CompileKind, RustcTargetData}; +use crate::core::dependency::DepKind; +use crate::core::resolver::features::{CliFeatures, FeaturesFor, ResolvedFeatures}; +use crate::core::resolver::Resolve; +use crate::core::{FeatureMap, FeatureValue, Package, PackageId, PackageIdSpec, Workspace}; +use crate::util::interning::InternedString; +use crate::util::CargoResult; +use std::collections::{HashMap, HashSet}; + +#[derive(Debug, Clone, Eq, PartialEq, Hash, Ord, PartialOrd)] +pub enum Node { + Package { + package_id: PackageId, + /// Features that are enabled on this package. + features: Vec<InternedString>, + kind: CompileKind, + }, + Feature { + /// Index of the package node this feature is for. + node_index: usize, + /// Name of the feature. + name: InternedString, + }, +} + +/// The kind of edge, for separating dependencies into different sections. +#[derive(Debug, Copy, Hash, Eq, Clone, PartialEq)] +pub enum EdgeKind { + Dep(DepKind), + Feature, +} + +/// Set of outgoing edges for a single node. +/// +/// Edges are separated by the edge kind (`DepKind` or `Feature`). This is +/// primarily done so that the output can easily display separate sections +/// like `[build-dependencies]`. +/// +/// The value is a `Vec` because each edge kind can have multiple outgoing +/// edges. For example, package "foo" can have multiple normal dependencies. +#[derive(Clone)] +struct Edges(HashMap<EdgeKind, Vec<usize>>); + +impl Edges { + fn new() -> Edges { + Edges(HashMap::new()) + } + + /// Adds an edge pointing to the given node. + fn add_edge(&mut self, kind: EdgeKind, index: usize) { + let indexes = self.0.entry(kind).or_default(); + if !indexes.contains(&index) { + indexes.push(index) + } + } +} + +/// A graph of dependencies. +pub struct Graph<'a> { + nodes: Vec<Node>, + /// The indexes of `edges` correspond to the `nodes`. That is, `edges[0]` + /// is the set of outgoing edges for `nodes[0]`. They should always be in + /// sync. + edges: Vec<Edges>, + /// Index maps a node to an index, for fast lookup. + index: HashMap<Node, usize>, + /// Map for looking up packages. + package_map: HashMap<PackageId, &'a Package>, + /// Set of indexes of feature nodes that were added via the command-line. + /// + /// For example `--features foo` will mark the "foo" node here. + cli_features: HashSet<usize>, + /// Map of dependency names, used for building internal feature map for + /// dep_name/feat_name syntax. + /// + /// Key is the index of a package node, value is a map of dep_name to a + /// set of `(pkg_node_index, is_optional)`. + dep_name_map: HashMap<usize, HashMap<InternedString, HashSet<(usize, bool)>>>, +} + +impl<'a> Graph<'a> { + fn new(package_map: HashMap<PackageId, &'a Package>) -> Graph<'a> { + Graph { + nodes: Vec::new(), + edges: Vec::new(), + index: HashMap::new(), + package_map, + cli_features: HashSet::new(), + dep_name_map: HashMap::new(), + } + } + + /// Adds a new node to the graph, returning its new index. + fn add_node(&mut self, node: Node) -> usize { + let from_index = self.nodes.len(); + self.nodes.push(node); + self.edges.push(Edges::new()); + self.index + .insert(self.nodes[from_index].clone(), from_index); + from_index + } + + /// Returns a list of nodes the given node index points to for the given kind. + pub fn connected_nodes(&self, from: usize, kind: &EdgeKind) -> Vec<usize> { + match self.edges[from].0.get(kind) { + Some(indexes) => { + // Created a sorted list for consistent output. + let mut indexes = indexes.clone(); + indexes.sort_unstable_by(|a, b| self.nodes[*a].cmp(&self.nodes[*b])); + indexes + } + None => Vec::new(), + } + } + + /// Returns `true` if the given node has any outgoing edges. + pub fn has_outgoing_edges(&self, index: usize) -> bool { + !self.edges[index].0.is_empty() + } + + /// Gets a node by index. + pub fn node(&self, index: usize) -> &Node { + &self.nodes[index] + } + + /// Given a slice of PackageIds, returns the indexes of all nodes that match. + pub fn indexes_from_ids(&self, package_ids: &[PackageId]) -> Vec<usize> { + let mut result: Vec<(&Node, usize)> = self + .nodes + .iter() + .enumerate() + .filter(|(_i, node)| match node { + Node::Package { package_id, .. } => package_ids.contains(package_id), + _ => false, + }) + .map(|(i, node)| (node, i)) + .collect(); + // Sort for consistent output (the same command should always return + // the same output). "unstable" since nodes should always be unique. + result.sort_unstable(); + result.into_iter().map(|(_node, i)| i).collect() + } + + pub fn package_for_id(&self, id: PackageId) -> &Package { + self.package_map[&id] + } + + fn package_id_for_index(&self, index: usize) -> PackageId { + match self.nodes[index] { + Node::Package { package_id, .. } => package_id, + Node::Feature { .. } => panic!("unexpected feature node"), + } + } + + /// Returns `true` if the given feature node index is a feature enabled + /// via the command-line. + pub fn is_cli_feature(&self, index: usize) -> bool { + self.cli_features.contains(&index) + } + + /// Returns a new graph by removing all nodes not reachable from the + /// given nodes. + pub fn from_reachable(&self, roots: &[usize]) -> Graph<'a> { + // Graph built with features does not (yet) support --duplicates. + assert!(self.dep_name_map.is_empty()); + let mut new_graph = Graph::new(self.package_map.clone()); + // Maps old index to new index. None if not yet visited. + let mut remap: Vec<Option<usize>> = vec![None; self.nodes.len()]; + + fn visit( + graph: &Graph<'_>, + new_graph: &mut Graph<'_>, + remap: &mut Vec<Option<usize>>, + index: usize, + ) -> usize { + if let Some(new_index) = remap[index] { + // Already visited. + return new_index; + } + let node = graph.node(index).clone(); + let new_from = new_graph.add_node(node); + remap[index] = Some(new_from); + // Visit dependencies. + for (edge_kind, edge_indexes) in &graph.edges[index].0 { + for edge_index in edge_indexes { + let new_to_index = visit(graph, new_graph, remap, *edge_index); + new_graph.edges[new_from].add_edge(*edge_kind, new_to_index); + } + } + new_from + } + + // Walk the roots, generating a new graph as it goes along. + for root in roots { + visit(self, &mut new_graph, &mut remap, *root); + } + + new_graph + } + + /// Inverts the direction of all edges. + pub fn invert(&mut self) { + let mut new_edges = vec![Edges::new(); self.edges.len()]; + for (from_idx, node_edges) in self.edges.iter().enumerate() { + for (kind, edges) in &node_edges.0 { + for edge_idx in edges { + new_edges[*edge_idx].add_edge(*kind, from_idx); + } + } + } + self.edges = new_edges; + } + + /// Returns a list of nodes that are considered "duplicates" (same package + /// name, with different versions/features/source/etc.). + pub fn find_duplicates(&self) -> Vec<usize> { + // Graph built with features does not (yet) support --duplicates. + assert!(self.dep_name_map.is_empty()); + + // Collect a map of package name to Vec<(&Node, usize)>. + let mut packages = HashMap::new(); + for (i, node) in self.nodes.iter().enumerate() { + if let Node::Package { package_id, .. } = node { + packages + .entry(package_id.name()) + .or_insert_with(Vec::new) + .push((node, i)); + } + } + + let mut dupes: Vec<(&Node, usize)> = packages + .into_iter() + .filter(|(_name, indexes)| { + indexes + .into_iter() + .map(|(node, _)| { + match node { + Node::Package { + package_id, + features, + .. + } => { + // Do not treat duplicates on the host or target as duplicates. + Node::Package { + package_id: package_id.clone(), + features: features.clone(), + kind: CompileKind::Host, + } + } + _ => unreachable!(), + } + }) + .collect::<HashSet<_>>() + .len() + > 1 + }) + .flat_map(|(_name, indexes)| indexes) + .collect(); + + // For consistent output. + dupes.sort_unstable(); + dupes.into_iter().map(|(_node, i)| i).collect() + } +} + +/// Builds the graph. +pub fn build<'a>( + ws: &Workspace<'_>, + resolve: &Resolve, + resolved_features: &ResolvedFeatures, + specs: &[PackageIdSpec], + cli_features: &CliFeatures, + target_data: &RustcTargetData<'_>, + requested_kinds: &[CompileKind], + package_map: HashMap<PackageId, &'a Package>, + opts: &TreeOptions, +) -> CargoResult<Graph<'a>> { + let mut graph = Graph::new(package_map); + let mut members_with_features = ws.members_with_features(specs, cli_features)?; + members_with_features.sort_unstable_by_key(|e| e.0.package_id()); + for (member, cli_features) in members_with_features { + let member_id = member.package_id(); + let features_for = FeaturesFor::from_for_host(member.proc_macro()); + for kind in requested_kinds { + let member_index = add_pkg( + &mut graph, + resolve, + resolved_features, + member_id, + features_for, + target_data, + *kind, + opts, + ); + if opts.graph_features { + let fmap = resolve.summary(member_id).features(); + add_cli_features(&mut graph, member_index, &cli_features, fmap); + } + } + } + if opts.graph_features { + add_internal_features(&mut graph, resolve); + } + Ok(graph) +} + +/// Adds a single package node (if it does not already exist). +/// +/// This will also recursively add all of its dependencies. +/// +/// Returns the index to the package node. +fn add_pkg( + graph: &mut Graph<'_>, + resolve: &Resolve, + resolved_features: &ResolvedFeatures, + package_id: PackageId, + features_for: FeaturesFor, + target_data: &RustcTargetData<'_>, + requested_kind: CompileKind, + opts: &TreeOptions, +) -> usize { + let node_features = resolved_features.activated_features(package_id, features_for); + let node_kind = match features_for { + FeaturesFor::HostDep => CompileKind::Host, + FeaturesFor::ArtifactDep(target) => CompileKind::Target(target), + FeaturesFor::NormalOrDev => requested_kind, + }; + let node = Node::Package { + package_id, + features: node_features, + kind: node_kind, + }; + if let Some(idx) = graph.index.get(&node) { + return *idx; + } + let from_index = graph.add_node(node); + // Compute the dep name map which is later used for foo/bar feature lookups. + let mut dep_name_map: HashMap<InternedString, HashSet<(usize, bool)>> = HashMap::new(); + let mut deps: Vec<_> = resolve.deps(package_id).collect(); + deps.sort_unstable_by_key(|(dep_id, _)| *dep_id); + let show_all_targets = opts.target == super::Target::All; + for (dep_id, deps) in deps { + let mut deps: Vec<_> = deps + .iter() + // This filter is *similar* to the one found in `unit_dependencies::compute_deps`. + // Try to keep them in sync! + .filter(|dep| { + let kind = match (node_kind, dep.kind()) { + (CompileKind::Host, _) => CompileKind::Host, + (_, DepKind::Build) => CompileKind::Host, + (_, DepKind::Normal) => node_kind, + (_, DepKind::Development) => node_kind, + }; + // Filter out inactivated targets. + if !show_all_targets && !target_data.dep_platform_activated(dep, kind) { + return false; + } + // Filter out dev-dependencies if requested. + if !opts.edge_kinds.contains(&EdgeKind::Dep(dep.kind())) { + return false; + } + if dep.is_optional() { + // If the new feature resolver does not enable this + // optional dep, then don't use it. + if !resolved_features.is_dep_activated( + package_id, + features_for, + dep.name_in_toml(), + ) { + return false; + } + } + true + }) + .collect(); + + // This dependency is eliminated from the dependency tree under + // the current target and feature set. + if deps.is_empty() { + continue; + } + + deps.sort_unstable_by_key(|dep| dep.name_in_toml()); + let dep_pkg = graph.package_map[&dep_id]; + + for dep in deps { + let dep_features_for = if dep.is_build() || dep_pkg.proc_macro() { + FeaturesFor::HostDep + } else { + features_for + }; + let dep_index = add_pkg( + graph, + resolve, + resolved_features, + dep_id, + dep_features_for, + target_data, + requested_kind, + opts, + ); + if opts.graph_features { + // Add the dependency node with feature nodes in-between. + dep_name_map + .entry(dep.name_in_toml()) + .or_default() + .insert((dep_index, dep.is_optional())); + if dep.uses_default_features() { + add_feature( + graph, + InternedString::new("default"), + Some(from_index), + dep_index, + EdgeKind::Dep(dep.kind()), + ); + } + for feature in dep.features().iter() { + add_feature( + graph, + *feature, + Some(from_index), + dep_index, + EdgeKind::Dep(dep.kind()), + ); + } + if !dep.uses_default_features() && dep.features().is_empty() { + // No features, use a direct connection. + graph.edges[from_index].add_edge(EdgeKind::Dep(dep.kind()), dep_index); + } + } else { + graph.edges[from_index].add_edge(EdgeKind::Dep(dep.kind()), dep_index); + } + } + } + if opts.graph_features { + assert!(graph + .dep_name_map + .insert(from_index, dep_name_map) + .is_none()); + } + + from_index +} + +/// Adds a feature node between two nodes. +/// +/// That is, it adds the following: +/// +/// ```text +/// from -Edge-> featname -Edge::Feature-> to +/// ``` +/// +/// Returns a tuple `(missing, index)`. +/// `missing` is true if this feature edge was already added. +/// `index` is the index of the index in the graph of the `Feature` node. +fn add_feature( + graph: &mut Graph<'_>, + name: InternedString, + from: Option<usize>, + to: usize, + kind: EdgeKind, +) -> (bool, usize) { + // `to` *must* point to a package node. + assert!(matches! {graph.nodes[to], Node::Package{..}}); + let node = Node::Feature { + node_index: to, + name, + }; + let (missing, node_index) = match graph.index.get(&node) { + Some(idx) => (false, *idx), + None => (true, graph.add_node(node)), + }; + if let Some(from) = from { + graph.edges[from].add_edge(kind, node_index); + } + graph.edges[node_index].add_edge(EdgeKind::Feature, to); + (missing, node_index) +} + +/// Adds nodes for features requested on the command-line for the given member. +/// +/// Feature nodes are added as "roots" (i.e., they have no "from" index), +/// because they come from the outside world. They usually only appear with +/// `--invert`. +fn add_cli_features( + graph: &mut Graph<'_>, + package_index: usize, + cli_features: &CliFeatures, + feature_map: &FeatureMap, +) { + // NOTE: Recursive enabling of features will be handled by + // add_internal_features. + + // Create a set of feature names requested on the command-line. + let mut to_add: HashSet<FeatureValue> = HashSet::new(); + if cli_features.all_features { + to_add.extend(feature_map.keys().map(|feat| FeatureValue::Feature(*feat))); + } + + if cli_features.uses_default_features { + to_add.insert(FeatureValue::Feature(InternedString::new("default"))); + } + to_add.extend(cli_features.features.iter().cloned()); + + // Add each feature as a node, and mark as "from command-line" in graph.cli_features. + for fv in to_add { + match fv { + FeatureValue::Feature(feature) => { + let index = add_feature(graph, feature, None, package_index, EdgeKind::Feature).1; + graph.cli_features.insert(index); + } + // This is enforced by CliFeatures. + FeatureValue::Dep { .. } => panic!("unexpected cli dep feature {}", fv), + FeatureValue::DepFeature { + dep_name, + dep_feature, + weak, + } => { + let dep_connections = match graph.dep_name_map[&package_index].get(&dep_name) { + // Clone to deal with immutable borrow of `graph`. :( + Some(dep_connections) => dep_connections.clone(), + None => { + // --features bar?/feat where `bar` is not activated should be ignored. + // If this wasn't weak, then this is a bug. + if weak { + continue; + } + panic!( + "missing dep graph connection for CLI feature `{}` for member {:?}\n\ + Please file a bug report at https://github.com/rust-lang/cargo/issues", + fv, + graph.nodes.get(package_index) + ); + } + }; + for (dep_index, is_optional) in dep_connections { + if is_optional { + // Activate the optional dep on self. + let index = + add_feature(graph, dep_name, None, package_index, EdgeKind::Feature).1; + graph.cli_features.insert(index); + } + let index = + add_feature(graph, dep_feature, None, dep_index, EdgeKind::Feature).1; + graph.cli_features.insert(index); + } + } + } + } +} + +/// Recursively adds connections between features in the `[features]` table +/// for every package. +fn add_internal_features(graph: &mut Graph<'_>, resolve: &Resolve) { + // Collect features already activated by dependencies or command-line. + let feature_nodes: Vec<(PackageId, usize, usize, InternedString)> = graph + .nodes + .iter() + .enumerate() + .filter_map(|(i, node)| match node { + Node::Package { .. } => None, + Node::Feature { node_index, name } => { + let package_id = graph.package_id_for_index(*node_index); + Some((package_id, *node_index, i, *name)) + } + }) + .collect(); + + for (package_id, package_index, feature_index, feature_name) in feature_nodes { + add_feature_rec( + graph, + resolve, + feature_name, + package_id, + feature_index, + package_index, + ); + } +} + +/// Recursively add feature nodes for all features enabled by the given feature. +/// +/// `from` is the index of the node that enables this feature. +/// `package_index` is the index of the package node for the feature. +fn add_feature_rec( + graph: &mut Graph<'_>, + resolve: &Resolve, + feature_name: InternedString, + package_id: PackageId, + from: usize, + package_index: usize, +) { + let feature_map = resolve.summary(package_id).features(); + let fvs = match feature_map.get(&feature_name) { + Some(fvs) => fvs, + None => return, + }; + for fv in fvs { + match fv { + FeatureValue::Feature(dep_name) => { + let (missing, feat_index) = add_feature( + graph, + *dep_name, + Some(from), + package_index, + EdgeKind::Feature, + ); + // Don't recursive if the edge already exists to deal with cycles. + if missing { + add_feature_rec( + graph, + resolve, + *dep_name, + package_id, + feat_index, + package_index, + ); + } + } + // Dependencies are already shown in the graph as dep edges. I'm + // uncertain whether or not this might be confusing in some cases + // (like feature `"somefeat" = ["dep:somedep"]`), so maybe in the + // future consider explicitly showing this? + FeatureValue::Dep { .. } => {} + FeatureValue::DepFeature { + dep_name, + dep_feature, + // Note: `weak` is mostly handled when the graph is built in + // `is_dep_activated` which is responsible for skipping + // unactivated weak dependencies. Here it is only used to + // determine if the feature of the dependency name is + // activated on self. + weak, + } => { + let dep_indexes = match graph.dep_name_map[&package_index].get(dep_name) { + Some(indexes) => indexes.clone(), + None => { + log::debug!( + "enabling feature {} on {}, found {}/{}, \ + dep appears to not be enabled", + feature_name, + package_id, + dep_name, + dep_feature + ); + continue; + } + }; + for (dep_index, is_optional) in dep_indexes { + let dep_pkg_id = graph.package_id_for_index(dep_index); + if is_optional && !weak { + // Activate the optional dep on self. + add_feature( + graph, + *dep_name, + Some(from), + package_index, + EdgeKind::Feature, + ); + } + let (missing, feat_index) = add_feature( + graph, + *dep_feature, + Some(from), + dep_index, + EdgeKind::Feature, + ); + if missing { + add_feature_rec( + graph, + resolve, + *dep_feature, + dep_pkg_id, + feat_index, + dep_index, + ); + } + } + } + } + } +} |