1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688
//! 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;
}
// Filter out proc-macrcos if requested.
if opts.no_proc_macro && graph.package_for_id(dep_id).proc_macro() {
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 Some(fvs) = feature_map.get(&feature_name) else {
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 => {
tracing::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,
);
}
}
}
}
}
}