1 //! Code for building the graph used by `cargo tree`.
3 use super::TreeOptions
;
4 use crate::core
::compiler
::{CompileKind, RustcTargetData}
;
5 use crate::core
::dependency
::DepKind
;
6 use crate::core
::resolver
::features
::{CliFeatures, FeaturesFor, ResolvedFeatures}
;
7 use crate::core
::resolver
::Resolve
;
8 use crate::core
::{FeatureMap, FeatureValue, Package, PackageId, PackageIdSpec, Workspace}
;
9 use crate::util
::interning
::InternedString
;
10 use crate::util
::CargoResult
;
11 use std
::collections
::{HashMap, HashSet}
;
13 #[derive(Debug, Clone, Eq, PartialEq, Hash, Ord, PartialOrd)]
16 package_id
: PackageId
,
17 /// Features that are enabled on this package.
18 features
: Vec
<InternedString
>,
22 /// Index of the package node this feature is for.
24 /// Name of the feature.
29 /// The kind of edge, for separating dependencies into different sections.
30 #[derive(Debug, Copy, Hash, Eq, Clone, PartialEq)]
36 /// Set of outgoing edges for a single node.
38 /// Edges are separated by the edge kind (`DepKind` or `Feature`). This is
39 /// primarily done so that the output can easily display separate sections
40 /// like `[build-dependencies]`.
42 /// The value is a `Vec` because each edge kind can have multiple outgoing
43 /// edges. For example, package "foo" can have multiple normal dependencies.
45 struct Edges(HashMap
<EdgeKind
, Vec
<usize>>);
52 /// Adds an edge pointing to the given node.
53 fn add_edge(&mut self, kind
: EdgeKind
, index
: usize) {
54 let indexes
= self.0.entry(kind
).or_default();
55 if !indexes
.contains(&index
) {
61 /// A graph of dependencies.
62 pub struct Graph
<'a
> {
64 /// The indexes of `edges` correspond to the `nodes`. That is, `edges[0]`
65 /// is the set of outgoing edges for `nodes[0]`. They should always be in
68 /// Index maps a node to an index, for fast lookup.
69 index
: HashMap
<Node
, usize>,
70 /// Map for looking up packages.
71 package_map
: HashMap
<PackageId
, &'a Package
>,
72 /// Set of indexes of feature nodes that were added via the command-line.
74 /// For example `--features foo` will mark the "foo" node here.
75 cli_features
: HashSet
<usize>,
76 /// Map of dependency names, used for building internal feature map for
77 /// dep_name/feat_name syntax.
79 /// Key is the index of a package node, value is a map of dep_name to a
80 /// set of `(pkg_node_index, is_optional)`.
81 dep_name_map
: HashMap
<usize, HashMap
<InternedString
, HashSet
<(usize, bool
)>>>,
85 fn new(package_map
: HashMap
<PackageId
, &'a Package
>) -> Graph
<'a
> {
89 index
: HashMap
::new(),
91 cli_features
: HashSet
::new(),
92 dep_name_map
: HashMap
::new(),
96 /// Adds a new node to the graph, returning its new index.
97 fn add_node(&mut self, node
: Node
) -> usize {
98 let from_index
= self.nodes
.len();
99 self.nodes
.push(node
);
100 self.edges
.push(Edges
::new());
102 .insert(self.nodes
[from_index
].clone(), from_index
);
106 /// Returns a list of nodes the given node index points to for the given kind.
107 pub fn connected_nodes(&self, from
: usize, kind
: &EdgeKind
) -> Vec
<usize> {
108 match self.edges
[from
].0.get(kind
) {
110 // Created a sorted list for consistent output.
111 let mut indexes
= indexes
.clone();
112 indexes
.sort_unstable_by(|a
, b
| self.nodes
[*a
].cmp(&self.nodes
[*b
]));
119 /// Returns `true` if the given node has any outgoing edges.
120 pub fn has_outgoing_edges(&self, index
: usize) -> bool
{
121 !self.edges
[index
].0.is_empty
()
124 /// Gets a node by index.
125 pub fn node(&self, index
: usize) -> &Node
{
129 /// Given a slice of PackageIds, returns the indexes of all nodes that match.
130 pub fn indexes_from_ids(&self, package_ids
: &[PackageId
]) -> Vec
<usize> {
131 let mut result
: Vec
<(&Node
, usize)> = self
135 .filter(|(_i
, node
)| match node
{
136 Node
::Package { package_id, .. }
=> package_ids
.contains(package_id
),
139 .map(|(i
, node
)| (node
, i
))
141 // Sort for consistent output (the same command should always return
142 // the same output). "unstable" since nodes should always be unique.
143 result
.sort_unstable();
144 result
.into_iter().map(|(_node
, i
)| i
).collect()
147 pub fn package_for_id(&self, id
: PackageId
) -> &Package
{
148 self.package_map
[&id
]
151 fn package_id_for_index(&self, index
: usize) -> PackageId
{
152 match self.nodes
[index
] {
153 Node
::Package { package_id, .. }
=> package_id
,
154 Node
::Feature { .. }
=> panic
!("unexpected feature node"),
158 /// Returns `true` if the given feature node index is a feature enabled
159 /// via the command-line.
160 pub fn is_cli_feature(&self, index
: usize) -> bool
{
161 self.cli_features
.contains(&index
)
164 /// Returns a new graph by removing all nodes not reachable from the
166 pub fn from_reachable(&self, roots
: &[usize]) -> Graph
<'a
> {
167 // Graph built with features does not (yet) support --duplicates.
168 assert
!(self.dep_name_map
.is_empty());
169 let mut new_graph
= Graph
::new(self.package_map
.clone());
170 // Maps old index to new index. None if not yet visited.
171 let mut remap
: Vec
<Option
<usize>> = vec
![None
; self.nodes
.len()];
175 new_graph
: &mut Graph
<'_
>,
176 remap
: &mut Vec
<Option
<usize>>,
179 if let Some(new_index
) = remap
[index
] {
183 let node
= graph
.node(index
).clone();
184 let new_from
= new_graph
.add_node(node
);
185 remap
[index
] = Some(new_from
);
186 // Visit dependencies.
187 for (edge_kind
, edge_indexes
) in &graph
.edges
[index
].0 {
188 for edge_index
in edge_indexes
{
189 let new_to_index
= visit(graph
, new_graph
, remap
, *edge_index
);
190 new_graph
.edges
[new_from
].add_edge(*edge_kind
, new_to_index
);
196 // Walk the roots, generating a new graph as it goes along.
198 visit(self, &mut new_graph
, &mut remap
, *root
);
204 /// Inverts the direction of all edges.
205 pub fn invert(&mut self) {
206 let mut new_edges
= vec
![Edges
::new(); self.edges
.len()];
207 for (from_idx
, node_edges
) in self.edges
.iter().enumerate() {
208 for (kind
, edges
) in &node_edges
.0 {
209 for edge_idx
in edges
{
210 new_edges
[*edge_idx
].add_edge(*kind
, from_idx
);
214 self.edges
= new_edges
;
217 /// Returns a list of nodes that are considered "duplicates" (same package
218 /// name, with different versions/features/source/etc.).
219 pub fn find_duplicates(&self) -> Vec
<usize> {
220 // Graph built with features does not (yet) support --duplicates.
221 assert
!(self.dep_name_map
.is_empty());
223 // Collect a map of package name to Vec<(&Node, usize)>.
224 let mut packages
= HashMap
::new();
225 for (i
, node
) in self.nodes
.iter().enumerate() {
226 if let Node
::Package { package_id, .. }
= node
{
228 .entry(package_id
.name())
229 .or_insert_with(Vec
::new
)
234 let mut dupes
: Vec
<(&Node
, usize)> = packages
236 .filter(|(_name
, indexes
)| indexes
.len() > 1)
237 .flat_map(|(_name
, indexes
)| indexes
)
239 // For consistent output.
240 dupes
.sort_unstable();
241 dupes
.into_iter().map(|(_node
, i
)| i
).collect()
245 /// Builds the graph.
249 resolved_features
: &ResolvedFeatures
,
250 specs
: &[PackageIdSpec
],
251 cli_features
: &CliFeatures
,
252 target_data
: &RustcTargetData
<'_
>,
253 requested_kinds
: &[CompileKind
],
254 package_map
: HashMap
<PackageId
, &'a Package
>,
256 ) -> CargoResult
<Graph
<'a
>> {
257 let mut graph
= Graph
::new(package_map
);
258 let mut members_with_features
= ws
.members_with_features(specs
, cli_features
)?
;
259 members_with_features
.sort_unstable_by_key(|e
| e
.0.package_id());
260 for (member
, cli_features
) in members_with_features
{
261 let member_id
= member
.package_id();
262 let features_for
= FeaturesFor
::from_for_host(member
.proc_macro());
263 for kind
in requested_kinds
{
264 let member_index
= add_pkg(
274 if opts
.graph_features
{
275 let fmap
= resolve
.summary(member_id
).features();
276 add_cli_features(&mut graph
, member_index
, &cli_features
, fmap
);
280 if opts
.graph_features
{
281 add_internal_features(&mut graph
, resolve
);
286 /// Adds a single package node (if it does not already exist).
288 /// This will also recursively add all of its dependencies.
290 /// Returns the index to the package node.
292 graph
: &mut Graph
<'_
>,
294 resolved_features
: &ResolvedFeatures
,
295 package_id
: PackageId
,
296 features_for
: FeaturesFor
,
297 target_data
: &RustcTargetData
<'_
>,
298 requested_kind
: CompileKind
,
301 let node_features
= resolved_features
.activated_features(package_id
, features_for
);
302 let node_kind
= match features_for
{
303 FeaturesFor
::HostDep
=> CompileKind
::Host
,
304 FeaturesFor
::NormalOrDev
=> requested_kind
,
306 let node
= Node
::Package
{
308 features
: node_features
,
311 if let Some(idx
) = graph
.index
.get(&node
) {
314 let from_index
= graph
.add_node(node
);
315 // Compute the dep name map which is later used for foo/bar feature lookups.
316 let mut dep_name_map
: HashMap
<InternedString
, HashSet
<(usize, bool
)>> = HashMap
::new();
317 let mut deps
: Vec
<_
> = resolve
.deps(package_id
).collect();
318 deps
.sort_unstable_by_key(|(dep_id
, _
)| *dep_id
);
319 let show_all_targets
= opts
.target
== super::Target
::All
;
320 for (dep_id
, deps
) in deps
{
321 let mut deps
: Vec
<_
> = deps
323 // This filter is *similar* to the one found in `unit_dependencies::compute_deps`.
324 // Try to keep them in sync!
326 let kind
= match (node_kind
, dep
.kind()) {
327 (CompileKind
::Host
, _
) => CompileKind
::Host
,
328 (_
, DepKind
::Build
) => CompileKind
::Host
,
329 (_
, DepKind
::Normal
) => node_kind
,
330 (_
, DepKind
::Development
) => node_kind
,
332 // Filter out inactivated targets.
333 if !show_all_targets
&& !target_data
.dep_platform_activated(dep
, kind
) {
336 // Filter out dev-dependencies if requested.
337 if !opts
.edge_kinds
.contains(&EdgeKind
::Dep(dep
.kind())) {
340 if dep
.is_optional() {
341 // If the new feature resolver does not enable this
342 // optional dep, then don't use it.
343 if !resolved_features
.is_dep_activated(
355 // This dependency is eliminated from the dependency tree under
356 // the current target and feature set.
361 deps
.sort_unstable_by_key(|dep
| dep
.name_in_toml());
362 let dep_pkg
= graph
.package_map
[&dep_id
];
365 let dep_features_for
= if dep
.is_build() || dep_pkg
.proc_macro() {
370 let dep_index
= add_pkg(
380 if opts
.graph_features
{
381 // Add the dependency node with feature nodes in-between.
383 .entry(dep
.name_in_toml())
385 .insert((dep_index
, dep
.is_optional()));
386 if dep
.uses_default_features() {
389 InternedString
::new("default"),
392 EdgeKind
::Dep(dep
.kind()),
395 for feature
in dep
.features().iter() {
401 EdgeKind
::Dep(dep
.kind()),
404 if !dep
.uses_default_features() && dep
.features().is_empty() {
405 // No features, use a direct connection.
406 graph
.edges
[from_index
].add_edge(EdgeKind
::Dep(dep
.kind()), dep_index
);
409 graph
.edges
[from_index
].add_edge(EdgeKind
::Dep(dep
.kind()), dep_index
);
413 if opts
.graph_features
{
416 .insert(from_index
, dep_name_map
)
423 /// Adds a feature node between two nodes.
425 /// That is, it adds the following:
428 /// from -Edge-> featname -Edge::Feature-> to
431 graph
: &mut Graph
<'_
>,
432 name
: InternedString
,
437 // `to` *must* point to a package node.
438 assert
!(matches
! {graph.nodes[to], Node::Package{..}
});
439 let node
= Node
::Feature
{
443 let node_index
= match graph
.index
.get(&node
) {
445 None
=> graph
.add_node(node
),
447 if let Some(from
) = from
{
448 graph
.edges
[from
].add_edge(kind
, node_index
);
450 graph
.edges
[node_index
].add_edge(EdgeKind
::Feature
, to
);
454 /// Adds nodes for features requested on the command-line for the given member.
456 /// Feature nodes are added as "roots" (i.e., they have no "from" index),
457 /// because they come from the outside world. They usually only appear with
460 graph
: &mut Graph
<'_
>,
461 package_index
: usize,
462 cli_features
: &CliFeatures
,
463 feature_map
: &FeatureMap
,
465 // NOTE: Recursive enabling of features will be handled by
466 // add_internal_features.
468 // Create a set of feature names requested on the command-line.
469 let mut to_add
: HashSet
<FeatureValue
> = HashSet
::new();
470 if cli_features
.all_features
{
471 to_add
.extend(feature_map
.keys().map(|feat
| FeatureValue
::Feature(*feat
)));
473 if cli_features
.uses_default_features
{
474 to_add
.insert(FeatureValue
::Feature(InternedString
::new("default")));
476 to_add
.extend(cli_features
.features
.iter().cloned());
479 // Add each feature as a node, and mark as "from command-line" in graph.cli_features.
482 FeatureValue
::Feature(feature
) => {
483 let index
= add_feature(graph
, feature
, None
, package_index
, EdgeKind
::Feature
);
484 graph
.cli_features
.insert(index
);
486 // This is enforced by CliFeatures.
487 FeatureValue
::Dep { .. }
=> panic
!("unexpected cli dep feature {}", fv
),
488 FeatureValue
::DepFeature
{
494 let dep_connections
= match graph
.dep_name_map
[&package_index
].get(&dep_name
) {
495 // Clone to deal with immutable borrow of `graph`. :(
496 Some(dep_connections
) => dep_connections
.clone(),
498 // --features bar?/feat where `bar` is not activated should be ignored.
499 // If this wasn't weak, then this is a bug.
504 "missing dep graph connection for CLI feature `{}` for member {:?}\n\
505 Please file a bug report at https://github.com/rust-lang/cargo/issues",
507 graph
.nodes
.get(package_index
)
511 for (dep_index
, is_optional
) in dep_connections
{
513 // Activate the optional dep on self.
515 add_feature(graph
, dep_name
, None
, package_index
, EdgeKind
::Feature
);
516 graph
.cli_features
.insert(index
);
518 let index
= add_feature(graph
, dep_feature
, None
, dep_index
, EdgeKind
::Feature
);
519 graph
.cli_features
.insert(index
);
526 /// Recursively adds connections between features in the `[features]` table
527 /// for every package.
528 fn add_internal_features(graph
: &mut Graph
<'_
>, resolve
: &Resolve
) {
529 // Collect features already activated by dependencies or command-line.
530 let feature_nodes
: Vec
<(PackageId
, usize, usize, InternedString
)> = graph
534 .filter_map(|(i
, node
)| match node
{
535 Node
::Package { .. }
=> None
,
536 Node
::Feature { node_index, name }
=> {
537 let package_id
= graph
.package_id_for_index(*node_index
);
538 Some((package_id
, *node_index
, i
, *name
))
543 for (package_id
, package_index
, feature_index
, feature_name
) in feature_nodes
{
555 /// Recursively add feature nodes for all features enabled by the given feature.
557 /// `from` is the index of the node that enables this feature.
558 /// `package_index` is the index of the package node for the feature.
560 graph
: &mut Graph
<'_
>,
562 feature_name
: InternedString
,
563 package_id
: PackageId
,
565 package_index
: usize,
567 let feature_map
= resolve
.summary(package_id
).features();
568 let fvs
= match feature_map
.get(&feature_name
) {
574 FeatureValue
::Feature(dep_name
) => {
575 let feat_index
= add_feature(
591 // Dependencies are already shown in the graph as dep edges. I'm
592 // uncertain whether or not this might be confusing in some cases
593 // (like feature `"somefeat" = ["dep:somedep"]`), so maybe in the
594 // future consider explicitly showing this?
595 FeatureValue
::Dep { .. }
=> {}
596 FeatureValue
::DepFeature
{
600 // `weak` is ignored, because it will be skipped if the
601 // corresponding dependency is not found in the map, which
602 // means it wasn't activated. Skipping is handled by
603 // `is_dep_activated` when the graph was built.
606 let dep_indexes
= match graph
.dep_name_map
[&package_index
].get(dep_name
) {
607 Some(indexes
) => indexes
.clone(),
610 "enabling feature {} on {}, found {}/{}, \
611 dep appears to not be enabled",
620 for (dep_index
, is_optional
) in dep_indexes
{
621 let dep_pkg_id
= graph
.package_id_for_index(dep_index
);
622 if is_optional
&& !dep_prefix
{
623 // Activate the optional dep on self.
632 let feat_index
= add_feature(