#
cargo/ops/tree/
graph.rs

    1//! Code for building the graph used by `cargo tree`.
    2
    3use super::TreeOptions;
    4use crate::core::compiler::{CompileKind, RustcTargetData};
    5use crate::core::dependency::DepKind;
    6use crate::core::resolver::features::{CliFeatures, FeaturesFor, ResolvedFeatures};
    7use crate::core::resolver::Resolve;
    8use crate::core::{FeatureMap, FeatureValue, Package, PackageId, PackageIdSpec, Workspace};
    9use crate::util::interning::{InternedString, INTERNED_DEFAULT};
    10use crate::util::CargoResult;
    11use std::collections::{HashMap, HashSet};
    12
    13#[derive(Debug, Copy, Clone)]
    14pub struct NodeId {
    15    index: usize,
    16    #[allow(dead_code)] // intended for `derive(Debug)`
    17    debug: InternedString,
    18}
    19
    20impl NodeId {
    21    fn new(index: usize, debug: InternedString) -> Self {
    22        Self { index, debug }
    23    }
    24}
    25
    26impl PartialEq for NodeId {
    27    fn eq(&self, other: &Self) -> bool {
    28        self.index == other.index
    29    }
    30}
    31
    32impl Eq for NodeId {}
    33
    34impl PartialOrd for NodeId {
    35    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
    36        Some(self.cmp(other))
    37    }
    38}
    39
    40impl Ord for NodeId {
    41    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
    42        self.index.cmp(&other.index)
    43    }
    44}
    45
    46impl std::hash::Hash for NodeId {
    47    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
    48        self.index.hash(state)
    49    }
    50}
    51
    52#[derive(Debug, Clone, Eq, PartialEq, Hash, Ord, PartialOrd)]
    53pub enum Node {
    54    Package {
    55        package_id: PackageId,
    56        /// Features that are enabled on this package.
    57        features: Vec<InternedString>,
    58        kind: CompileKind,
    59    },
    60    Feature {
    61        /// Index of the package node this feature is for.
    62        node_index: NodeId,
    63        /// Name of the feature.
    64        name: InternedString,
    65    },
    66}
    67
    68impl Node {
    69    fn name(&self) -> InternedString {
    70        match self {
    71            Self::Package { package_id, .. } => package_id.name(),
    72            Self::Feature { name, .. } => *name,
    73        }
    74    }
    75}
    76
    77#[derive(Debug, Copy, Hash, Eq, Clone, PartialEq)]
    78pub struct Edge {
    79    kind: EdgeKind,
    80    node: NodeId,
    81    public: bool,
    82}
    83
    84impl Edge {
    85    pub fn kind(&self) -> EdgeKind {
    86        self.kind
    87    }
    88
    89    pub fn node(&self) -> NodeId {
    90        self.node
    91    }
    92
    93    pub fn public(&self) -> bool {
    94        self.public
    95    }
    96}
    97
    98/// The kind of edge, for separating dependencies into different sections.
    99#[derive(Debug, Copy, Hash, Eq, Clone, PartialEq)]
    100pub enum EdgeKind {
    101    Dep(DepKind),
    102    Feature,
    103}
    104
    105/// Set of outgoing edges for a single node.
    106///
    107/// Edges are separated by the edge kind (`DepKind` or `Feature`). This is
    108/// primarily done so that the output can easily display separate sections
    109/// like `[build-dependencies]`.
    110///
    111/// The value is a `Vec` because each edge kind can have multiple outgoing
    112/// edges. For example, package "foo" can have multiple normal dependencies.
    113#[derive(Clone, Debug)]
    114struct Edges(HashMap<EdgeKind, Vec<Edge>>);
    115
    116impl Edges {
    117    fn new() -> Edges {
    118        Edges(HashMap::new())
    119    }
    120
    121    /// Adds an edge pointing to the given node.
    122    fn add_edge(&mut self, edge: Edge) {
    123        let indexes = self.0.entry(edge.kind()).or_default();
    124        if !indexes.contains(&edge) {
    125            indexes.push(edge)
    126        }
    127    }
    128
    129    fn all(&self) -> impl Iterator<Item = &Edge> + '_ {
    130        self.0.values().flatten()
    131    }
    132
    133    fn of_kind(&self, kind: &EdgeKind) -> &[Edge] {
    134        self.0.get(kind).map(Vec::as_slice).unwrap_or_default()
    135    }
    136
    137    fn is_empty(&self) -> bool {
    138        self.0.is_empty()
    139    }
    140}
    141
    142/// A graph of dependencies.
    143#[derive(Debug)]
    144pub struct Graph<'a> {
    145    nodes: Vec<Node>,
    146    /// The indexes of `edges` correspond to the `nodes`. That is, `edges[0]`
    147    /// is the set of outgoing edges for `nodes[0]`. They should always be in
    148    /// sync.
    149    edges: Vec<Edges>,
    150    /// Index maps a node to an index, for fast lookup.
    151    index: HashMap<Node, NodeId>,
    152    /// Map for looking up packages.
    153    package_map: HashMap<PackageId, &'a Package>,
    154    /// Set of indexes of feature nodes that were added via the command-line.
    155    ///
    156    /// For example `--features foo` will mark the "foo" node here.
    157    cli_features: HashSet<NodeId>,
    158    /// Map of dependency names, used for building internal feature map for
    159    /// `dep_name/feat_name` syntax.
    160    ///
    161    /// Key is the index of a package node, value is a map of `dep_name` to a
    162    /// set of `(pkg_node_index, is_optional)`.
    163    dep_name_map: HashMap<NodeId, HashMap<InternedString, HashSet<(NodeId, bool)>>>,
    164}
    165
    166impl<'a> Graph<'a> {
    167    fn new(package_map: HashMap<PackageId, &'a Package>) -> Graph<'a> {
    168        Graph {
    169            nodes: Vec::new(),
    170            edges: Vec::new(),
    171            index: HashMap::new(),
    172            package_map,
    173            cli_features: HashSet::new(),
    174            dep_name_map: HashMap::new(),
    175        }
    176    }
    177
    178    /// Adds a new node to the graph, returning its new index.
    179    fn add_node(&mut self, node: Node) -> NodeId {
    180        let from_index = NodeId::new(self.nodes.len(), node.name());
    181        self.nodes.push(node);
    182        self.edges.push(Edges::new());
    183        self.index.insert(self.node(from_index).clone(), from_index);
    184        from_index
    185    }
    186
    187    /// Returns a list of nodes the given node index points to for the given kind.
    188    pub fn edges_of_kind(&self, from: NodeId, kind: &EdgeKind) -> Vec<Edge> {
    189        let edges = self.edges(from).of_kind(kind);
    190        // Created a sorted list for consistent output.
    191        let mut edges = edges.to_owned();
    192        edges.sort_unstable_by(|a, b| self.node(a.node()).cmp(&self.node(b.node())));
    193        edges
    194    }
    195
    196    fn edges(&self, from: NodeId) -> &Edges {
    197        &self.edges[from.index]
    198    }
    199
    200    fn edges_mut(&mut self, from: NodeId) -> &mut Edges {
    201        &mut self.edges[from.index]
    202    }
    203
    204    /// Returns `true` if the given node has any outgoing edges.
    205    pub fn has_outgoing_edges(&self, index: NodeId) -> bool {
    206        !self.edges(index).is_empty()
    207    }
    208
    209    /// Gets a node by index.
    210    pub fn node(&self, index: NodeId) -> &Node {
    211        &self.nodes[index.index]
    212    }
    213
    214    /// Given a slice of `PackageIds`, returns the indexes of all nodes that match.
    215    pub fn indexes_from_ids(&self, package_ids: &[PackageId]) -> Vec<NodeId> {
    216        let mut result: Vec<(&Node, NodeId)> = self
    217            .nodes
    218            .iter()
    219            .enumerate()
    220            .filter(|(_i, node)| match node {
    221                Node::Package { package_id, .. } => package_ids.contains(package_id),
    222                _ => false,
    223            })
    224            .map(|(i, node)| (node, NodeId::new(i, node.name())))
    225            .collect();
    226        // Sort for consistent output (the same command should always return
    227        // the same output). "unstable" since nodes should always be unique.
    228        result.sort_unstable();
    229        result.into_iter().map(|(_node, i)| i).collect()
    230    }
    231
    232    pub fn package_for_id(&self, id: PackageId) -> &Package {
    233        self.package_map[&id]
    234    }
    235
    236    fn package_id_for_index(&self, index: NodeId) -> PackageId {
    237        match self.node(index) {
    238            Node::Package { package_id, .. } => *package_id,
    239            Node::Feature { .. } => panic!("unexpected feature node"),
    240        }
    241    }
    242
    243    /// Returns `true` if the given feature node index is a feature enabled
    244    /// via the command-line.
    245    pub fn is_cli_feature(&self, index: NodeId) -> bool {
    246        self.cli_features.contains(&index)
    247    }
    248
    249    /// Returns a new graph by removing all nodes not reachable from the
    250    /// given nodes.
    251    pub fn from_reachable(&self, roots: &[NodeId]) -> Graph<'a> {
    252        // Graph built with features does not (yet) support --duplicates.
    253        assert!(self.dep_name_map.is_empty());
    254        let mut new_graph = Graph::new(self.package_map.clone());
    255        // Maps old index to new index. None if not yet visited.
    256        let mut remap: Vec<Option<NodeId>> = vec![None; self.nodes.len()];
    257
    258        fn visit(
    259            graph: &Graph<'_>,
    260            new_graph: &mut Graph<'_>,
    261            remap: &mut Vec<Option<NodeId>>,
    262            index: NodeId,
    263        ) -> NodeId {
    264            if let Some(new_index) = remap[index.index] {
    265                // Already visited.
    266                return new_index;
    267            }
    268            let node = graph.node(index).clone();
    269            let new_from = new_graph.add_node(node);
    270            remap[index.index] = Some(new_from);
    271            // Visit dependencies.
    272            for edge in graph.edges(index).all() {
    273                let new_to_index = visit(graph, new_graph, remap, edge.node());
    274                let new_edge = Edge {
    275                    kind: edge.kind(),
    276                    node: new_to_index,
    277                    public: edge.public(),
    278                };
    279                new_graph.edges_mut(new_from).add_edge(new_edge);
    280            }
    281            new_from
    282        }
    283
    284        // Walk the roots, generating a new graph as it goes along.
    285        for root in roots {
    286            visit(self, &mut new_graph, &mut remap, *root);
    287        }
    288
    289        new_graph
    290    }
    291
    292    /// Inverts the direction of all edges.
    293    pub fn invert(&mut self) {
    294        let mut new_edges = vec![Edges::new(); self.edges.len()];
    295        for (from_idx, node_edges) in self.edges.iter().enumerate() {
    296            for edge in node_edges.all() {
    297                let new_edge = Edge {
    298                    kind: edge.kind(),
    299                    node: NodeId::new(from_idx, self.nodes[from_idx].name()),
    300                    public: edge.public(),
    301                };
    302                new_edges[edge.node().index].add_edge(new_edge);
    303            }
    304        }
    305        self.edges = new_edges;
    306    }
    307
    308    /// Returns a list of nodes that are considered "duplicates" (same package
    309    /// name, with different versions/features/source/etc.).
    310    pub fn find_duplicates(&self) -> Vec<NodeId> {
    311        // Graph built with features does not (yet) support --duplicates.
    312        assert!(self.dep_name_map.is_empty());
    313
    314        // Collect a map of package name to Vec<(&Node, NodeId)>.
    315        let mut packages = HashMap::new();
    316        for (i, node) in self.nodes.iter().enumerate() {
    317            if let Node::Package { package_id, .. } = node {
    318                packages
    319                    .entry(package_id.name())
    320                    .or_insert_with(Vec::new)
    321                    .push((node, NodeId::new(i, node.name())));
    322            }
    323        }
    324
    325        let mut dupes: Vec<(&Node, NodeId)> = packages
    326            .into_iter()
    327            .filter(|(_name, indexes)| {
    328                indexes
    329                    .into_iter()
    330                    .map(|(node, _)| {
    331                        match node {
    332                            Node::Package {
    333                                package_id,
    334                                features,
    335                                ..
    336                            } => {
    337                                // Do not treat duplicates on the host or target as duplicates.
    338                                Node::Package {
    339                                    package_id: package_id.clone(),
    340                                    features: features.clone(),
    341                                    kind: CompileKind::Host,
    342                                }
    343                            }
    344                            _ => unreachable!(),
    345                        }
    346                    })
    347                    .collect::<HashSet<_>>()
    348                    .len()
    349                    > 1
    350            })
    351            .flat_map(|(_name, indexes)| indexes)
    352            .collect();
    353
    354        // For consistent output.
    355        dupes.sort_unstable();
    356        dupes.into_iter().map(|(_node, i)| i).collect()
    357    }
    358}
    359
    360/// Builds the graph.
    361pub fn build<'a>(
    362    ws: &Workspace<'_>,
    363    resolve: &Resolve,
    364    resolved_features: &ResolvedFeatures,
    365    specs: &[PackageIdSpec],
    366    cli_features: &CliFeatures,
    367    target_data: &RustcTargetData<'_>,
    368    requested_kinds: &[CompileKind],
    369    package_map: HashMap<PackageId, &'a Package>,
    370    opts: &TreeOptions,
    371) -> CargoResult<Graph<'a>> {
    372    let mut graph = Graph::new(package_map);
    373    let mut members_with_features = ws.members_with_features(specs, cli_features)?;
    374    members_with_features.sort_unstable_by_key(|(member, _)| member.package_id());
    375    for (member, cli_features) in members_with_features {
    376        let member_id = member.package_id();
    377        let features_for = FeaturesFor::from_for_host(member.proc_macro());
    378        for kind in requested_kinds {
    379            let member_index = add_pkg(
    380                &mut graph,
    381                resolve,
    382                resolved_features,
    383                member_id,
    384                features_for,
    385                target_data,
    386                *kind,
    387                opts,
    388            );
    389            if opts.graph_features {
    390                let fmap = resolve.summary(member_id).features();
    391                add_cli_features(&mut graph, member_index, &cli_features, fmap);
    392            }
    393        }
    394    }
    395    if opts.graph_features {
    396        add_internal_features(&mut graph, resolve);
    397    }
    398    Ok(graph)
    399}
    400
    401/// Adds a single package node (if it does not already exist).
    402///
    403/// This will also recursively add all of its dependencies.
    404///
    405/// Returns the index to the package node.
    406fn add_pkg(
    407    graph: &mut Graph<'_>,
    408    resolve: &Resolve,
    409    resolved_features: &ResolvedFeatures,
    410    package_id: PackageId,
    411    features_for: FeaturesFor,
    412    target_data: &RustcTargetData<'_>,
    413    requested_kind: CompileKind,
    414    opts: &TreeOptions,
    415) -> NodeId {
    416    let node_features = resolved_features.activated_features(package_id, features_for);
    417    let node_kind = match features_for {
    418        FeaturesFor::HostDep => CompileKind::Host,
    419        FeaturesFor::ArtifactDep(target) => CompileKind::Target(target),
    420        FeaturesFor::NormalOrDev => requested_kind,
    421    };
    422    let node = Node::Package {
    423        package_id,
    424        features: node_features,
    425        kind: node_kind,
    426    };
    427    if let Some(idx) = graph.index.get(&node) {
    428        return *idx;
    429    }
    430    let from_index = graph.add_node(node);
    431    // Compute the dep name map which is later used for foo/bar feature lookups.
    432    let mut dep_name_map: HashMap<InternedString, HashSet<(NodeId, bool)>> = HashMap::new();
    433    let mut deps: Vec<_> = resolve.deps(package_id).collect();
    434    deps.sort_unstable_by_key(|(dep_id, _)| *dep_id);
    435    let show_all_targets = opts.target == super::Target::All;
    436    for (dep_id, deps) in deps {
    437        let mut deps: Vec<_> = deps
    438            .iter()
    439            // This filter is *similar* to the one found in `unit_dependencies::compute_deps`.
    440            // Try to keep them in sync!
    441            .filter(|dep| {
    442                let kind = match (node_kind, dep.kind()) {
    443                    (CompileKind::Host, _) => CompileKind::Host,
    444                    (_, DepKind::Build) => CompileKind::Host,
    445                    (_, DepKind::Normal) => node_kind,
    446                    (_, DepKind::Development) => node_kind,
    447                };
    448                // Filter out inactivated targets.
    449                if !show_all_targets && !target_data.dep_platform_activated(dep, kind) {
    450                    return false;
    451                }
    452                // Filter out dev-dependencies if requested.
    453                if !opts.edge_kinds.contains(&EdgeKind::Dep(dep.kind())) {
    454                    return false;
    455                }
    456                // Filter out proc-macrcos if requested.
    457                if opts.no_proc_macro && graph.package_for_id(dep_id).proc_macro() {
    458                    return false;
    459                }
    460                if dep.is_optional() {
    461                    // If the new feature resolver does not enable this
    462                    // optional dep, then don't use it.
    463                    if !resolved_features.is_dep_activated(
    464                        package_id,
    465                        features_for,
    466                        dep.name_in_toml(),
    467                    ) {
    468                        return false;
    469                    }
    470                }
    471                true
    472            })
    473            .collect();
    474
    475        // This dependency is eliminated from the dependency tree under
    476        // the current target and feature set.
    477        if deps.is_empty() {
    478            continue;
    479        }
    480
    481        deps.sort_unstable_by_key(|dep| (dep.kind(), dep.name_in_toml()));
    482        let dep_pkg = graph.package_map[&dep_id];
    483
    484        for dep in deps {
    485            let dep_features_for = match dep
    486                .artifact()
    487                .and_then(|artifact| artifact.target())
    488                .and_then(|target| target.to_resolved_compile_target(requested_kind))
    489            {
    490                // Dependency has a `{ …, target = <triple> }`
    491                Some(target) => FeaturesFor::ArtifactDep(target),
    492                // Get the information of the dependent crate from `features_for`.
    493                // If a dependent crate is
    494                //
    495                // * specified as an artifact dep with a `target`, or
    496                // * a host dep,
    497                //
    498                // its transitive deps, including build-deps, need to be built on that target.
    499                None if features_for != FeaturesFor::default() => features_for,
    500                // Dependent crate is a normal dep, then back to old rules:
    501                //
    502                // * normal deps, dev-deps -> inherited target
    503                // * build-deps -> host
    504                None => {
    505                    if dep.is_build() || dep_pkg.proc_macro() {
    506                        FeaturesFor::HostDep
    507                    } else {
    508                        features_for
    509                    }
    510                }
    511            };
    512            let dep_index = add_pkg(
    513                graph,
    514                resolve,
    515                resolved_features,
    516                dep_id,
    517                dep_features_for,
    518                target_data,
    519                requested_kind,
    520                opts,
    521            );
    522            let new_edge = Edge {
    523                kind: EdgeKind::Dep(dep.kind()),
    524                node: dep_index,
    525                public: dep.is_public(),
    526            };
    527            if opts.graph_features {
    528                // Add the dependency node with feature nodes in-between.
    529                dep_name_map
    530                    .entry(dep.name_in_toml())
    531                    .or_default()
    532                    .insert((dep_index, dep.is_optional()));
    533                if dep.uses_default_features() {
    534                    add_feature(graph, INTERNED_DEFAULT, Some(from_index), new_edge);
    535                }
    536                for feature in dep.features().iter() {
    537                    add_feature(graph, *feature, Some(from_index), new_edge);
    538                }
    539                if !dep.uses_default_features() && dep.features().is_empty() {
    540                    // No features, use a direct connection.
    541                    graph.edges_mut(from_index).add_edge(new_edge);
    542                }
    543            } else {
    544                graph.edges_mut(from_index).add_edge(new_edge);
    545            }
    546        }
    547    }
    548    if opts.graph_features {
    549        assert!(graph
    550            .dep_name_map
    551            .insert(from_index, dep_name_map)
    552            .is_none());
    553    }
    554
    555    from_index
    556}
    557
    558/// Adds a feature node between two nodes.
    559///
    560/// That is, it adds the following:
    561///
    562/// ```text
    563/// from -Edge-> featname -Edge::Feature-> to
    564/// ```
    565///
    566/// Returns a tuple `(missing, index)`.
    567/// `missing` is true if this feature edge was already added.
    568/// `index` is the index of the index in the graph of the `Feature` node.
    569fn add_feature(
    570    graph: &mut Graph<'_>,
    571    name: InternedString,
    572    from: Option<NodeId>,
    573    to: Edge,
    574) -> (bool, NodeId) {
    575    // `to` *must* point to a package node.
    576    assert!(matches! {graph.node(to.node()), Node::Package{..}});
    577    let node = Node::Feature {
    578        node_index: to.node(),
    579        name,
    580    };
    581    let (missing, node_index) = match graph.index.get(&node) {
    582        Some(idx) => (false, *idx),
    583        None => (true, graph.add_node(node)),
    584    };
    585    if let Some(from) = from {
    586        let from_edge = Edge {
    587            kind: to.kind(),
    588            node: node_index,
    589            public: to.public(),
    590        };
    591        graph.edges_mut(from).add_edge(from_edge);
    592    }
    593    let to_edge = Edge {
    594        kind: EdgeKind::Feature,
    595        node: to.node(),
    596        public: true,
    597    };
    598    graph.edges_mut(node_index).add_edge(to_edge);
    599    (missing, node_index)
    600}
    601
    602/// Adds nodes for features requested on the command-line for the given member.
    603///
    604/// Feature nodes are added as "roots" (i.e., they have no "from" index),
    605/// because they come from the outside world. They usually only appear with
    606/// `--invert`.
    607fn add_cli_features(
    608    graph: &mut Graph<'_>,
    609    package_index: NodeId,
    610    cli_features: &CliFeatures,
    611    feature_map: &FeatureMap,
    612) {
    613    // NOTE: Recursive enabling of features will be handled by
    614    // add_internal_features.
    615
    616    // Create a set of feature names requested on the command-line.
    617    let mut to_add: HashSet<FeatureValue> = HashSet::new();
    618    if cli_features.all_features {
    619        to_add.extend(feature_map.keys().map(|feat| FeatureValue::Feature(*feat)));
    620    }
    621
    622    if cli_features.uses_default_features {
    623        to_add.insert(FeatureValue::Feature(INTERNED_DEFAULT));
    624    }
    625    to_add.extend(cli_features.features.iter().cloned());
    626
    627    // Add each feature as a node, and mark as "from command-line" in graph.cli_features.
    628    for fv in to_add {
    629        match fv {
    630            FeatureValue::Feature(feature) => {
    631                let feature_edge = Edge {
    632                    kind: EdgeKind::Feature,
    633                    node: package_index,
    634                    public: true,
    635                };
    636                let index = add_feature(graph, feature, None, feature_edge).1;
    637                graph.cli_features.insert(index);
    638            }
    639            // This is enforced by CliFeatures.
    640            FeatureValue::Dep { .. } => panic!("unexpected cli dep feature {}", fv),
    641            FeatureValue::DepFeature {
    642                dep_name,
    643                dep_feature,
    644                weak,
    645            } => {
    646                let dep_connections = match graph.dep_name_map[&package_index].get(&dep_name) {
    647                    // Clone to deal with immutable borrow of `graph`. :(
    648                    Some(dep_connections) => dep_connections.clone(),
    649                    None => {
    650                        // --features bar?/feat where `bar` is not activated should be ignored.
    651                        // If this wasn't weak, then this is a bug.
    652                        if weak {
    653                            continue;
    654                        }
    655                        panic!(
    656                            "missing dep graph connection for CLI feature `{}` for member {:?}\n\
    657                             Please file a bug report at https://github.com/rust-lang/cargo/issues",
    658                            fv,
    659                            graph.nodes.get(package_index.index)
    660                        );
    661                    }
    662                };
    663                for (dep_index, is_optional) in dep_connections {
    664                    if is_optional {
    665                        // Activate the optional dep on self.
    666                        let feature_edge = Edge {
    667                            kind: EdgeKind::Feature,
    668                            node: package_index,
    669                            public: true,
    670                        };
    671                        let index = add_feature(graph, dep_name, None, feature_edge).1;
    672                        graph.cli_features.insert(index);
    673                    }
    674                    let dep_edge = Edge {
    675                        kind: EdgeKind::Feature,
    676                        node: dep_index,
    677                        public: true,
    678                    };
    679                    let index = add_feature(graph, dep_feature, None, dep_edge).1;
    680                    graph.cli_features.insert(index);
    681                }
    682            }
    683        }
    684    }
    685}
    686
    687/// Recursively adds connections between features in the `[features]` table
    688/// for every package.
    689fn add_internal_features(graph: &mut Graph<'_>, resolve: &Resolve) {
    690    // Collect features already activated by dependencies or command-line.
    691    let feature_nodes: Vec<(PackageId, NodeId, NodeId, InternedString)> = graph
    692        .nodes
    693        .iter()
    694        .enumerate()
    695        .filter_map(|(i, node)| match node {
    696            Node::Package { .. } => None,
    697            Node::Feature { node_index, name } => {
    698                let package_id = graph.package_id_for_index(*node_index);
    699                Some((package_id, *node_index, NodeId::new(i, *name), *name))
    700            }
    701        })
    702        .collect();
    703
    704    for (package_id, package_index, feature_index, feature_name) in feature_nodes {
    705        add_feature_rec(
    706            graph,
    707            resolve,
    708            feature_name,
    709            package_id,
    710            feature_index,
    711            package_index,
    712        );
    713    }
    714}
    715
    716/// Recursively add feature nodes for all features enabled by the given feature.
    717///
    718/// `from` is the index of the node that enables this feature.
    719/// `package_index` is the index of the package node for the feature.
    720fn add_feature_rec(
    721    graph: &mut Graph<'_>,
    722    resolve: &Resolve,
    723    feature_name: InternedString,
    724    package_id: PackageId,
    725    from: NodeId,
    726    package_index: NodeId,
    727) {
    728    let feature_map = resolve.summary(package_id).features();
    729    let Some(fvs) = feature_map.get(&feature_name) else {
    730        return;
    731    };
    732    for fv in fvs {
    733        match fv {
    734            FeatureValue::Feature(dep_name) => {
    735                let feature_edge = Edge {
    736                    kind: EdgeKind::Feature,
    737                    node: package_index,
    738                    public: true,
    739                };
    740                let (missing, feat_index) = add_feature(graph, *dep_name, Some(from), feature_edge);
    741                // Don't recursive if the edge already exists to deal with cycles.
    742                if missing {
    743                    add_feature_rec(
    744                        graph,
    745                        resolve,
    746                        *dep_name,
    747                        package_id,
    748                        feat_index,
    749                        package_index,
    750                    );
    751                }
    752            }
    753            // Dependencies are already shown in the graph as dep edges. I'm
    754            // uncertain whether or not this might be confusing in some cases
    755            // (like feature `"somefeat" = ["dep:somedep"]`), so maybe in the
    756            // future consider explicitly showing this?
    757            FeatureValue::Dep { .. } => {}
    758            FeatureValue::DepFeature {
    759                dep_name,
    760                dep_feature,
    761                // Note: `weak` is mostly handled when the graph is built in
    762                // `is_dep_activated` which is responsible for skipping
    763                // unactivated weak dependencies. Here it is only used to
    764                // determine if the feature of the dependency name is
    765                // activated on self.
    766                weak,
    767            } => {
    768                let dep_indexes = match graph.dep_name_map[&package_index].get(dep_name) {
    769                    Some(indexes) => indexes.clone(),
    770                    None => {
    771                        tracing::debug!(
    772                            "enabling feature {} on {}, found {}/{}, \
    773                             dep appears to not be enabled",
    774                            feature_name,
    775                            package_id,
    776                            dep_name,
    777                            dep_feature
    778                        );
    779                        continue;
    780                    }
    781                };
    782                for (dep_index, is_optional) in dep_indexes {
    783                    let dep_pkg_id = graph.package_id_for_index(dep_index);
    784                    if is_optional && !weak {
    785                        // Activate the optional dep on self.
    786                        let feature_edge = Edge {
    787                            kind: EdgeKind::Feature,
    788                            node: package_index,
    789                            public: true,
    790                        };
    791                        add_feature(graph, *dep_name, Some(from), feature_edge);
    792                    }
    793                    let dep_edge = Edge {
    794                        kind: EdgeKind::Feature,
    795                        node: dep_index,
    796                        public: true,
    797                    };
    798                    let (missing, feat_index) =
    799                        add_feature(graph, *dep_feature, Some(from), dep_edge);
    800                    if missing {
    801                        add_feature_rec(
    802                            graph,
    803                            resolve,
    804                            *dep_feature,
    805                            dep_pkg_id,
    806                            feat_index,
    807                            dep_index,
    808                        );
    809                    }
    810                }
    811            }
    812        }
    813    }
    814}