guppy/graph/feature/
graph_impl.rs

1// Copyright (c) The cargo-guppy Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use crate::{
5    DependencyKind, Error, PackageId,
6    debug_ignore::DebugIgnore,
7    errors::FeatureGraphWarning,
8    graph::{
9        DependencyDirection, FeatureIndexInPackage, FeatureIx, PackageGraph, PackageIx,
10        PackageLink, PackageMetadata,
11        feature::{
12            Cycles, FeatureFilter, FeatureList, WeakDependencies, WeakIndex,
13            build::{FeatureGraphBuildState, FeaturePetgraph},
14        },
15    },
16    petgraph_support::{scc::Sccs, topo::TopoWithCycles},
17    platform::{PlatformStatus, PlatformStatusImpl},
18};
19use ahash::AHashMap;
20use once_cell::sync::OnceCell;
21use petgraph::{
22    algo::has_path_connecting,
23    prelude::*,
24    visit::{EdgeFiltered, IntoNodeReferences},
25};
26use std::{fmt, iter, iter::FromIterator};
27
28// Some general notes about feature graphs:
29//
30// The set of features for a package is the named features (in the [features] section), plus any
31// optional dependencies.
32//
33// An optional dependency can be either normal or build -- not dev. Note that a dependency can be
34// marked optional in one section and required in another. In this context, a dependency is a
35// feature if it is marked as optional in any context.
36//
37// Features are *unified*. See the documentation in add_dependency_edges for more.
38//
39// There are a few ways features can be enabled. The most common is within a dependency spec. A
40// feature can also be specified via the command-line. Finally, named features can specify what
41// features a package depends on:
42//
43// ```toml
44// [features]
45// foo = ["a/bar", "optional-dep", "baz"]
46// baz = []
47// ```
48//
49// Feature names are unique. A named feature and an optional dep cannot have the same names.
50
51impl PackageGraph {
52    /// Returns a derived graph representing every feature of every package.
53    ///
54    /// The feature graph is constructed the first time this method is called. The graph is cached
55    /// so that repeated calls to this method are cheap.
56    pub fn feature_graph(&self) -> FeatureGraph {
57        let inner = self.get_feature_graph();
58        FeatureGraph {
59            package_graph: self,
60            inner,
61        }
62    }
63
64    pub(super) fn get_feature_graph(&self) -> &FeatureGraphImpl {
65        self.feature_graph
66            .get_or_init(|| FeatureGraphImpl::new(self))
67    }
68}
69
70/// A derived graph representing every feature of every package.
71///
72/// Constructed through `PackageGraph::feature_graph`.
73#[derive(Clone, Copy, Debug)]
74pub struct FeatureGraph<'g> {
75    pub(crate) package_graph: &'g PackageGraph,
76    pub(super) inner: &'g FeatureGraphImpl,
77}
78
79assert_covariant!(FeatureGraph);
80
81impl<'g> FeatureGraph<'g> {
82    /// Returns any non-fatal warnings encountered while constructing the feature graph.
83    pub fn build_warnings(&self) -> &'g [FeatureGraphWarning] {
84        &self.inner.warnings
85    }
86
87    /// Returns the `PackageGraph` from which this feature graph was constructed.
88    pub fn package_graph(&self) -> &'g PackageGraph {
89        self.package_graph
90    }
91
92    /// Returns the total number of (package ID, feature) combinations in this graph.
93    ///
94    /// Includes the "base" feature for each package.
95    pub fn feature_count(&self) -> usize {
96        self.dep_graph().node_count()
97    }
98
99    /// Returns the number of links in this graph.
100    pub fn link_count(&self) -> usize {
101        self.dep_graph().edge_count()
102    }
103
104    /// Returns true if this feature graph contains the specified feature.
105    pub fn contains(&self, feature_id: impl Into<FeatureId<'g>>) -> bool {
106        let feature_id = feature_id.into();
107        FeatureNode::from_id(self, feature_id).is_some()
108    }
109
110    /// Returns metadata for the given feature ID, or `None` if the feature wasn't found.
111    pub fn metadata(
112        &self,
113        feature_id: impl Into<FeatureId<'g>>,
114    ) -> Result<FeatureMetadata<'g>, Error> {
115        let feature_id = feature_id.into();
116        let feature_node = FeatureNode::from_id(self, feature_id)
117            .ok_or_else(|| Error::unknown_feature_id(feature_id))?;
118        self.metadata_for_node(feature_node)
119            .ok_or_else(|| Error::unknown_feature_id(feature_id))
120    }
121
122    /// Returns all known features for a package.
123    ///
124    /// Returns an error if the package ID was unknown.
125    pub fn all_features_for(&self, package_id: &PackageId) -> Result<FeatureList<'g>, Error> {
126        let package = self.package_graph.metadata(package_id)?;
127        let dep_graph = self.dep_graph();
128        let features = self
129            .feature_ixs_for_package_ix(package.package_ix())
130            .map(|feature_ix| FeatureId::node_to_feature(package, &dep_graph[feature_ix]));
131        Ok(FeatureList::new(package, features))
132    }
133
134    /// Returns true if this feature is included in a package's build by default.
135    ///
136    /// Returns an error if this feature ID is unknown.
137    ///
138    /// ## Cycles
139    ///
140    /// A cyclic dev-dependency may cause additional features to be turned on. This computation
141    /// does *not* follow conditional links and will *not* return true for such additional
142    /// features.
143    pub fn is_default_feature<'a>(
144        &self,
145        feature_id: impl Into<FeatureId<'a>>,
146    ) -> Result<bool, Error> {
147        let feature_id = feature_id.into();
148        let default_ix = self.feature_ix(
149            self.package_graph
150                .metadata(feature_id.package_id())?
151                .default_feature_id(),
152        )?;
153        let feature_ix = self.feature_ix(feature_id)?;
154        // Do not follow conditional links.
155        Ok(self.feature_ix_depends_on_no_conditional(default_ix, feature_ix))
156    }
157
158    /// Returns true if `feature_a` depends (directly or indirectly) on `feature_b`.
159    ///
160    /// In other words, this returns true if `feature_b` is a (possibly transitive) dependency of
161    /// `feature_a`.
162    ///
163    /// This also returns true if `feature_a` is the same as `feature_b`.
164    ///
165    /// Note that this returns true if `feature_a` [conditionally depends on][ConditionalLink] `feature_b`.
166    pub fn depends_on<'a>(
167        &self,
168        feature_a: impl Into<FeatureId<'a>>,
169        feature_b: impl Into<FeatureId<'a>>,
170    ) -> Result<bool, Error> {
171        let feature_a = feature_a.into();
172        let feature_b = feature_b.into();
173        let a_ix = self.feature_ix(feature_a)?;
174        let b_ix = self.feature_ix(feature_b)?;
175        Ok(self.feature_ix_depends_on(a_ix, b_ix))
176    }
177
178    /// Returns true if `feature_a` directly depends on `feature_b`.
179    ///
180    /// In other words, this returns true if `feature_a` is a direct dependency of `feature_b`.
181    ///
182    /// This returns false if `feature_a` is the same as `feature_b`.
183    pub fn directly_depends_on<'a>(
184        &self,
185        feature_a: impl Into<FeatureId<'a>>,
186        feature_b: impl Into<FeatureId<'a>>,
187    ) -> Result<bool, Error> {
188        let feature_a = feature_a.into();
189        let feature_b = feature_b.into();
190        let a_ix = self.feature_ix(feature_a)?;
191        let b_ix = self.feature_ix(feature_b)?;
192        Ok(self.dep_graph().contains_edge(a_ix, b_ix))
193    }
194
195    /// Returns information about dependency cycles.
196    ///
197    /// For more information, see the documentation for `Cycles`.
198    pub fn cycles(&self) -> Cycles<'g> {
199        Cycles::new(*self)
200    }
201
202    // ---
203    // Helper methods
204    // ---
205
206    /// Verify basic properties of the feature graph.
207    #[doc(hidden)]
208    pub fn verify(&self) -> Result<(), Error> {
209        let feature_set = self.resolve_all();
210        for conditional_link in feature_set.conditional_links(DependencyDirection::Forward) {
211            let (from, to) = conditional_link.endpoints();
212            let is_any = conditional_link.normal().is_present()
213                || conditional_link.build().is_present()
214                || conditional_link.dev().is_present();
215
216            if !is_any {
217                return Err(Error::FeatureGraphInternalError(format!(
218                    "{} -> {}: no edge info found",
219                    from.feature_id(),
220                    to.feature_id()
221                )));
222            }
223        }
224
225        Ok(())
226    }
227
228    /// Returns the strongly connected components for this feature graph.
229    pub(super) fn sccs(&self) -> &'g Sccs<FeatureIx> {
230        self.inner.sccs.get_or_init(|| {
231            let edge_filtered =
232                EdgeFiltered::from_fn(self.dep_graph(), |edge| match edge.weight() {
233                    FeatureEdge::DependenciesSection(link)
234                    | FeatureEdge::NamedFeatureDepColon(link)
235                    | FeatureEdge::NamedFeatureWithSlash { link, .. } => !link.dev_only(),
236                    FeatureEdge::NamedFeature | FeatureEdge::FeatureToBase => true,
237                });
238            // Sort the entire graph without dev-only edges -- a correct graph would be cycle-free
239            // but we don't currently do a consistency check for this so handle cycles.
240            // TODO: should we check at construction time? or bubble up a warning somehow?
241            let topo = TopoWithCycles::new(&edge_filtered);
242            Sccs::new(&self.inner.graph, |scc| {
243                topo.sort_nodes(scc);
244            })
245        })
246    }
247
248    fn metadata_impl(&self, feature_id: FeatureId<'g>) -> Option<&'g FeatureMetadataImpl> {
249        let feature_node = FeatureNode::from_id(self, feature_id)?;
250        self.metadata_impl_for_node(&feature_node)
251    }
252
253    pub(in crate::graph) fn metadata_for_ix(
254        &self,
255        feature_ix: NodeIndex<FeatureIx>,
256    ) -> FeatureMetadata<'g> {
257        self.metadata_for_node(self.dep_graph()[feature_ix])
258            .expect("valid feature ix")
259    }
260
261    pub(super) fn metadata_for_node(&self, node: FeatureNode) -> Option<FeatureMetadata<'g>> {
262        let inner = self.metadata_impl_for_node(&node)?;
263        Some(FeatureMetadata {
264            graph: DebugIgnore(*self),
265            node,
266            inner,
267        })
268    }
269
270    #[inline]
271    fn metadata_impl_for_node(&self, node: &FeatureNode) -> Option<&'g FeatureMetadataImpl> {
272        self.inner.map.get(node)
273    }
274
275    pub(super) fn dep_graph(&self) -> &'g FeaturePetgraph {
276        &self.inner.graph
277    }
278
279    /// If this is a conditional edge, return the conditional link. Otherwise, return None.
280    pub(super) fn edge_to_conditional_link(
281        &self,
282        source_ix: NodeIndex<FeatureIx>,
283        target_ix: NodeIndex<FeatureIx>,
284        edge_ix: EdgeIndex<FeatureIx>,
285        edge: Option<&'g FeatureEdge>,
286    ) -> Option<(ConditionalLink<'g>, Option<WeakIndex>)> {
287        let edge = edge.unwrap_or_else(|| &self.dep_graph()[edge_ix]);
288
289        match edge {
290            FeatureEdge::NamedFeature | FeatureEdge::FeatureToBase => None,
291            FeatureEdge::DependenciesSection(link) | FeatureEdge::NamedFeatureDepColon(link) => {
292                let link = ConditionalLink::new(*self, source_ix, target_ix, edge_ix, link);
293                // Dependency section and dep:foo style conditional links are always non-weak.
294                let weak_index = None;
295                Some((link, weak_index))
296            }
297            FeatureEdge::NamedFeatureWithSlash { link, weak_index } => {
298                let link = ConditionalLink::new(*self, source_ix, target_ix, edge_ix, link);
299                Some((link, *weak_index))
300            }
301        }
302    }
303
304    fn feature_ix_depends_on(
305        &self,
306        a_ix: NodeIndex<FeatureIx>,
307        b_ix: NodeIndex<FeatureIx>,
308    ) -> bool {
309        has_path_connecting(self.dep_graph(), a_ix, b_ix, None)
310    }
311
312    fn feature_ix_depends_on_no_conditional(
313        &self,
314        a_ix: NodeIndex<FeatureIx>,
315        b_ix: NodeIndex<FeatureIx>,
316    ) -> bool {
317        // Filter out conditional edges.
318        let edge_filtered =
319            EdgeFiltered::from_fn(self.dep_graph(), |edge_ref| match edge_ref.weight() {
320                FeatureEdge::FeatureToBase | FeatureEdge::NamedFeature => true,
321                FeatureEdge::DependenciesSection(_)
322                | FeatureEdge::NamedFeatureDepColon(_)
323                | FeatureEdge::NamedFeatureWithSlash { .. } => false,
324            });
325        has_path_connecting(&edge_filtered, a_ix, b_ix, None)
326    }
327
328    pub(super) fn feature_ixs_for_package_ix(
329        &self,
330        package_ix: NodeIndex<PackageIx>,
331    ) -> impl Iterator<Item = NodeIndex<FeatureIx>> + use<> {
332        let package_ix = package_ix.index();
333        let base_ix = self.inner.base_ixs[package_ix].index();
334        // base_ixs has (package count + 1) elements so this access is valid.
335        let next_base_ix = self.inner.base_ixs[package_ix + 1].index();
336
337        (base_ix..next_base_ix).map(NodeIndex::new)
338    }
339
340    pub(super) fn feature_ixs_for_package_ixs<I>(
341        &self,
342        package_ixs: I,
343    ) -> impl Iterator<Item = NodeIndex<FeatureIx>> + 'g + use<'g, I>
344    where
345        I: IntoIterator<Item = NodeIndex<PackageIx>> + 'g,
346    {
347        // Create a copy of FeatureGraph that will be moved into the closure below.
348        let this = *self;
349
350        package_ixs
351            .into_iter()
352            .flat_map(move |package_ix| this.feature_ixs_for_package_ix(package_ix))
353    }
354
355    pub(in crate::graph) fn feature_ixs_for_package_ixs_filtered<B>(
356        &self,
357        package_ixs: impl IntoIterator<Item = NodeIndex<PackageIx>>,
358        filter: impl FeatureFilter<'g>,
359    ) -> B
360    where
361        B: FromIterator<NodeIndex<FeatureIx>>,
362    {
363        let mut filter = filter;
364
365        self.feature_ixs_for_package_ixs(package_ixs)
366            .filter(|feature_ix| {
367                let feature_node = &self.dep_graph()[*feature_ix];
368                filter.accept(self, FeatureId::from_node(self.package_graph, feature_node))
369            })
370            .collect()
371    }
372
373    pub(in crate::graph) fn package_ix_for_feature_ix(
374        &self,
375        feature_ix: NodeIndex<FeatureIx>,
376    ) -> NodeIndex<PackageIx> {
377        let feature_node = &self.dep_graph()[feature_ix];
378        feature_node.package_ix()
379    }
380
381    #[allow(dead_code)]
382    pub(super) fn feature_ixs<'a, B>(
383        &self,
384        feature_ids: impl IntoIterator<Item = FeatureId<'g>>,
385    ) -> Result<B, Error>
386    where
387        B: iter::FromIterator<NodeIndex<FeatureIx>>,
388    {
389        feature_ids
390            .into_iter()
391            .map(|feature_id| self.feature_ix(feature_id))
392            .collect()
393    }
394
395    pub(super) fn feature_ix(
396        &self,
397        feature_id: FeatureId<'g>,
398    ) -> Result<NodeIndex<FeatureIx>, Error> {
399        let metadata = self
400            .metadata_impl(feature_id)
401            .ok_or_else(|| Error::unknown_feature_id(feature_id))?;
402        Ok(metadata.feature_ix)
403    }
404}
405
406/// An identifier for a (package, feature) pair in a feature graph.
407///
408/// Returned by various methods on `FeatureGraph` and `FeatureQuery`.
409///
410/// `From` impls are available for `(&'g PackageId, &'g str)` and `(&'g PackageId, Option<&'g str>)`
411/// tuples.
412#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
413pub struct FeatureId<'g> {
414    package_id: &'g PackageId,
415    label: FeatureLabel<'g>,
416}
417
418assert_covariant!(FeatureId);
419
420impl<'g> FeatureId<'g> {
421    /// Creates a new `FeatureId` with the given [`PackageId`] and [`FeatureLabel`].
422    pub fn new(package_id: &'g PackageId, label: FeatureLabel<'g>) -> Self {
423        Self { package_id, label }
424    }
425
426    /// Creates a new `FeatureId` representing a named feature in the `[features]` section,
427    /// or an implicit named feature created by an optional dependency.
428    pub fn named(package_id: &'g PackageId, feature_name: &'g str) -> Self {
429        Self {
430            package_id,
431            label: FeatureLabel::Named(feature_name),
432        }
433    }
434
435    /// Creates a new `FeatureId` representing an optional dependency.
436    pub fn optional_dependency(package_id: &'g PackageId, dep_name: &'g str) -> Self {
437        Self {
438            package_id,
439            label: FeatureLabel::OptionalDependency(dep_name),
440        }
441    }
442
443    /// Creates a new `FeatureId` representing the base feature for a package.
444    pub fn base(package_id: &'g PackageId) -> Self {
445        Self {
446            package_id,
447            label: FeatureLabel::Base,
448        }
449    }
450
451    pub(super) fn from_node(package_graph: &'g PackageGraph, node: &FeatureNode) -> Self {
452        let package_id = &package_graph.dep_graph[node.package_ix];
453        let metadata = package_graph
454            .metadata(package_id)
455            .expect("package ID should have valid metadata");
456        let feature = Self::node_to_feature(metadata, node);
457        Self {
458            package_id,
459            label: feature,
460        }
461    }
462
463    pub(super) fn node_to_feature(
464        metadata: PackageMetadata<'g>,
465        node: &FeatureNode,
466    ) -> FeatureLabel<'g> {
467        metadata.feature_idx_to_label(node.feature_idx)
468    }
469
470    /// Returns the package ID.
471    pub fn package_id(&self) -> &'g PackageId {
472        self.package_id
473    }
474
475    /// Returns the [`FeatureLabel`] associated with the feature.
476    pub fn label(&self) -> FeatureLabel<'g> {
477        self.label
478    }
479
480    /// Returns true if this is the base feature for the package.
481    #[inline]
482    pub fn is_base(&self) -> bool {
483        self.label.kind().is_base()
484    }
485
486    /// Returns true if this is an optional dependency.
487    #[inline]
488    pub fn is_optional_dependency(self) -> bool {
489        self.label.kind().is_optional_dependency()
490    }
491
492    /// Returns true if this is a named feature.
493    #[inline]
494    pub fn is_named(self) -> bool {
495        self.label.kind().is_named()
496    }
497}
498
499impl<'g> From<(&'g PackageId, FeatureLabel<'g>)> for FeatureId<'g> {
500    fn from((package_id, label): (&'g PackageId, FeatureLabel<'g>)) -> Self {
501        FeatureId { package_id, label }
502    }
503}
504
505/// The `Display` impl prints out:
506///
507/// * `{package-id}/[base]` for base features.
508/// * `{package-id}/feature-name` for named features.
509/// * `{package-id}/dep:dep-name` for optional dependencies.
510///
511/// ## Examples
512///
513/// ```
514/// use guppy::PackageId;
515/// use guppy::graph::feature::FeatureId;
516///
517/// let package_id = PackageId::new("region 2.1.2 (registry+https://github.com/rust-lang/crates.io-index)");
518///
519/// assert_eq!(
520///     format!("{}", FeatureId::base(&package_id)),
521///     "region 2.1.2 (registry+https://github.com/rust-lang/crates.io-index)/[base]"
522/// );
523///
524/// assert_eq!(
525///     format!("{}", FeatureId::named(&package_id, "foo")),
526///     "region 2.1.2 (registry+https://github.com/rust-lang/crates.io-index)/foo"
527/// );
528///
529/// assert_eq!(
530///     format!("{}", FeatureId::optional_dependency(&package_id, "bar")),
531///     "region 2.1.2 (registry+https://github.com/rust-lang/crates.io-index)/dep:bar"
532/// );
533/// ```
534impl fmt::Display for FeatureId<'_> {
535    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
536        write!(f, "{}/{}", self.package_id, self.label)
537    }
538}
539
540/// A unique identifier for a feature within a specific package. Forms part of a [`FeatureId`].
541#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
542pub enum FeatureLabel<'g> {
543    /// The "base" feature. Every package has one such feature.
544    Base,
545
546    /// This is a named feature in the `[features]` section, or an implicit feature that corresponds to
547    /// an optional dependency.
548    ///
549    /// For versions of Cargo prior to 1.60, optional dependencies always create implicit features
550    /// by the same name. For versions 1.60 and greater, optional dependencies may create implicit
551    /// features if the dependency doesn't exist with the name "dep" in it.
552    Named(&'g str),
553
554    /// This is an optional dependency.
555    OptionalDependency(&'g str),
556}
557
558impl FeatureLabel<'_> {
559    /// Returns the kind of feature this is.
560    ///
561    /// The kind of a feature is simply the enum variant without any associated data.
562    #[inline]
563    pub fn kind(self) -> FeatureKind {
564        match self {
565            Self::Base => FeatureKind::Base,
566            Self::Named(_) => FeatureKind::Named,
567            Self::OptionalDependency(_) => FeatureKind::OptionalDependency,
568        }
569    }
570}
571
572/// The `Display` impl for `FeatureLabel` prints out:
573///
574/// * `[base]` for base labels.
575/// * `feature-name` for optional dependencies.
576/// * `dep:dep-name` for named features.
577///
578/// ## Examples
579///
580/// ```
581/// use guppy::graph::feature::FeatureLabel;
582///
583/// assert_eq!(format!("{}", FeatureLabel::Base), "[base]");
584/// assert_eq!(format!("{}", FeatureLabel::Named("foo")), "foo");
585/// assert_eq!(format!("{}", FeatureLabel::OptionalDependency("bar")), "dep:bar");
586/// ```
587impl fmt::Display for FeatureLabel<'_> {
588    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
589        match self {
590            Self::Base => write!(f, "[base]"),
591            Self::Named(feature_name) => write!(f, "{feature_name}"),
592            Self::OptionalDependency(dep_name) => write!(f, "dep:{dep_name}"),
593        }
594    }
595}
596
597/// Metadata for a feature within a package.
598#[derive(Clone, Copy)]
599pub struct FeatureMetadata<'g> {
600    graph: DebugIgnore<FeatureGraph<'g>>,
601    node: FeatureNode,
602    inner: &'g FeatureMetadataImpl,
603}
604
605assert_covariant!(FeatureMetadata);
606
607impl<'g> FeatureMetadata<'g> {
608    /// Returns the feature ID corresponding to this metadata.
609    pub fn feature_id(&self) -> FeatureId<'g> {
610        FeatureId::from_node(self.graph.package_graph, &self.node)
611    }
612
613    /// Returns the package ID corresponding to this metadata.
614    pub fn package_id(&self) -> &'g PackageId {
615        &self.graph.package_graph.dep_graph[self.package_ix()]
616    }
617
618    /// Returns the package metadata corresponding to this feature metadata.
619    pub fn package(&self) -> PackageMetadata<'g> {
620        self.graph
621            .package_graph
622            .metadata(self.package_id())
623            .expect("valid package ID")
624    }
625
626    /// Returns the label for this feature.
627    pub fn label(&self) -> FeatureLabel<'g> {
628        self.feature_id().label()
629    }
630
631    // ---
632    // Helper methods
633    // ---
634
635    #[inline]
636    pub(in crate::graph) fn package_ix(&self) -> NodeIndex<PackageIx> {
637        self.node.package_ix
638    }
639
640    #[inline]
641    pub(in crate::graph) fn feature_ix(&self) -> NodeIndex<FeatureIx> {
642        self.inner.feature_ix
643    }
644}
645
646impl fmt::Debug for FeatureMetadata<'_> {
647    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
648        f.debug_struct("FeatureMetadata")
649            .field("id", &self.feature_id())
650            .finish()
651    }
652}
653
654/// A graph representing every possible feature of every package, and the connections between them.
655#[derive(Clone, Debug)]
656pub(in crate::graph) struct FeatureGraphImpl {
657    pub(super) graph: FeaturePetgraph,
658    // base ixs consists of the base (start) feature indexes for each package.
659    pub(super) base_ixs: Vec<NodeIndex<FeatureIx>>,
660    pub(super) map: AHashMap<FeatureNode, FeatureMetadataImpl>,
661    pub(super) warnings: Vec<FeatureGraphWarning>,
662    // The strongly connected components of the feature graph. Computed on demand.
663    pub(super) sccs: OnceCell<Sccs<FeatureIx>>,
664    pub(super) weak: WeakDependencies,
665}
666
667impl FeatureGraphImpl {
668    /// Creates a new `FeatureGraph` from this `PackageGraph`.
669    pub(super) fn new(package_graph: &PackageGraph) -> Self {
670        let mut build_state = FeatureGraphBuildState::new(package_graph);
671
672        // Graph returns its node references in order -- check this in debug builds.
673        let mut prev_ix = None;
674        for (package_ix, package_id) in package_graph.dep_graph.node_references() {
675            if let Some(prev_ix) = prev_ix {
676                debug_assert_eq!(package_ix.index(), prev_ix + 1, "package ixs are in order");
677            }
678            prev_ix = Some(package_ix.index());
679
680            let metadata = package_graph
681                .metadata(package_id)
682                .expect("valid package ID");
683            build_state.add_nodes(metadata);
684        }
685
686        build_state.end_nodes();
687
688        // The choice of bottom-up for this loop and the next is pretty arbitrary.
689        for metadata in package_graph
690            .resolve_all()
691            .packages(DependencyDirection::Reverse)
692        {
693            build_state.add_named_feature_edges(metadata);
694        }
695
696        for link in package_graph
697            .resolve_all()
698            .links(DependencyDirection::Reverse)
699        {
700            build_state.add_dependency_edges(link);
701        }
702
703        build_state.build()
704    }
705}
706
707/// A feature dependency that is conditionally activated.
708///
709/// A `ConditionalLink` is typically a link across packages. For example:
710///
711/// ```toml
712/// [package]
713/// name = "main"
714///
715/// [dependencies]
716/// dep = { ... }
717///
718/// [dev-dependencies]
719/// dev-dep = { ... }
720///
721/// [target.'cfg(unix)'.dependencies]
722/// unix-dep = { ... }
723///
724/// [features]
725/// feat = ["dep/feat", "dev-dep/feat", "unix-dep/feat"]
726/// ```
727///
728/// In this example, there are `ConditionalLink`s from `main/feat` to `dep/feat`, `dev-dep/feat` and
729/// `unix-dep/feat`. Each link is only activated if the conditions for it are met. For example,
730/// the link to `dev-dep/feat` is only followed if Cargo is interested in dev-dependencies of `main`.
731///
732/// If a dependency, for example `unix-dep` above, is optional, an implicit feature is created in
733/// the package `main` with the name `unix-dep`. In this case, the dependency from `main/feat` to
734/// `main/unix-dep` is also a `ConditionalLink` representing the same `cfg(unix)` condition.
735#[derive(Copy, Clone)]
736pub struct ConditionalLink<'g> {
737    graph: DebugIgnore<FeatureGraph<'g>>,
738    from: &'g FeatureMetadataImpl,
739    to: &'g FeatureMetadataImpl,
740    edge_ix: EdgeIndex<FeatureIx>,
741    inner: &'g ConditionalLinkImpl,
742}
743
744assert_covariant!(ConditionalLink);
745
746impl<'g> ConditionalLink<'g> {
747    #[allow(dead_code)]
748    pub(super) fn new(
749        graph: FeatureGraph<'g>,
750        source_ix: NodeIndex<FeatureIx>,
751        target_ix: NodeIndex<FeatureIx>,
752        edge_ix: EdgeIndex<FeatureIx>,
753        inner: &'g ConditionalLinkImpl,
754    ) -> Self {
755        let dep_graph = graph.dep_graph();
756        Self {
757            graph: DebugIgnore(graph),
758            from: graph
759                .metadata_impl_for_node(&dep_graph[source_ix])
760                .expect("valid source ix"),
761            to: graph
762                .metadata_impl_for_node(&dep_graph[target_ix])
763                .expect("valid target ix"),
764            edge_ix,
765            inner,
766        }
767    }
768
769    /// Returns the feature which depends on the `to` feature.
770    pub fn from(&self) -> FeatureMetadata<'g> {
771        FeatureMetadata {
772            graph: DebugIgnore(self.graph.0),
773            node: self.graph.dep_graph()[self.from.feature_ix],
774            inner: self.from,
775        }
776    }
777
778    /// Returns the feature which is depended on by the `from` feature.
779    pub fn to(&self) -> FeatureMetadata<'g> {
780        FeatureMetadata {
781            graph: DebugIgnore(self.graph.0),
782            node: self.graph.dep_graph()[self.to.feature_ix],
783            inner: self.to,
784        }
785    }
786
787    /// Returns the endpoints as a pair of features `(from, to)`.
788    pub fn endpoints(&self) -> (FeatureMetadata<'g>, FeatureMetadata<'g>) {
789        (self.from(), self.to())
790    }
791
792    /// Returns details about this feature dependency from the `[dependencies]` section.
793    pub fn normal(&self) -> PlatformStatus<'g> {
794        PlatformStatus::new(&self.inner.normal)
795    }
796
797    /// Returns details about this feature dependency from the `[build-dependencies]` section.
798    pub fn build(&self) -> PlatformStatus<'g> {
799        PlatformStatus::new(&self.inner.build)
800    }
801
802    /// Returns details about this feature dependency from the `[dev-dependencies]` section.
803    pub fn dev(&self) -> PlatformStatus<'g> {
804        PlatformStatus::new(&self.inner.dev)
805    }
806
807    /// Returns details about this feature dependency from the section specified by the given
808    /// dependency kind.
809    pub fn status_for_kind(&self, kind: DependencyKind) -> PlatformStatus<'g> {
810        match kind {
811            DependencyKind::Normal => self.normal(),
812            DependencyKind::Build => self.build(),
813            DependencyKind::Development => self.dev(),
814        }
815    }
816
817    /// Returns true if this edge is dev-only, i.e. code from this edge will not be included in
818    /// normal builds.
819    pub fn dev_only(&self) -> bool {
820        self.inner.dev_only()
821    }
822
823    /// Returns the `PackageLink` from which this `ConditionalLink` was derived.
824    pub fn package_link(&self) -> PackageLink<'g> {
825        self.graph
826            .package_graph
827            .edge_ix_to_link(self.inner.package_edge_ix)
828    }
829
830    // ---
831    // Helper methods
832    // ---
833
834    #[allow(dead_code)]
835    pub(super) fn edge_ix(&self) -> EdgeIndex<FeatureIx> {
836        self.edge_ix
837    }
838
839    #[allow(dead_code)]
840    pub(in crate::graph) fn package_edge_ix(&self) -> EdgeIndex<PackageIx> {
841        self.inner.package_edge_ix
842    }
843}
844
845impl fmt::Debug for ConditionalLink<'_> {
846    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
847        f.debug_struct("ConditionalLink")
848            .field("from", &self.from())
849            .field("to", &self.to())
850            .field("normal", &self.normal())
851            .field("build", &self.build())
852            .field("dev", &self.dev())
853            .finish()
854    }
855}
856
857// ---
858
859/// A combination of a package ID and a feature name, forming a node in a `FeatureGraph`.
860#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
861pub(in crate::graph) struct FeatureNode {
862    package_ix: NodeIndex<PackageIx>,
863    feature_idx: FeatureIndexInPackage,
864}
865
866impl FeatureNode {
867    /// Returns a new feature node.
868    pub(in crate::graph) fn new(
869        package_ix: NodeIndex<PackageIx>,
870        feature_idx: FeatureIndexInPackage,
871    ) -> Self {
872        Self {
873            package_ix,
874            feature_idx,
875        }
876    }
877
878    /// Base feature node.
879    pub(in crate::graph) fn base(package_ix: NodeIndex<PackageIx>) -> Self {
880        Self {
881            package_ix,
882            feature_idx: FeatureIndexInPackage::Base,
883        }
884    }
885
886    pub(in crate::graph) fn optional_dep(package_ix: NodeIndex<PackageIx>, dep_idx: usize) -> Self {
887        Self {
888            package_ix,
889            feature_idx: FeatureIndexInPackage::OptionalDependency(dep_idx),
890        }
891    }
892
893    pub(in crate::graph) fn named_feature(
894        package_ix: NodeIndex<PackageIx>,
895        named_idx: usize,
896    ) -> Self {
897        Self {
898            package_ix,
899            feature_idx: FeatureIndexInPackage::Named(named_idx),
900        }
901    }
902
903    fn from_id(feature_graph: &FeatureGraph<'_>, id: FeatureId<'_>) -> Option<Self> {
904        let metadata = feature_graph.package_graph.metadata(id.package_id()).ok()?;
905        Some(FeatureNode::new(
906            metadata.package_ix(),
907            metadata.get_feature_idx(id.label())?,
908        ))
909    }
910
911    pub(super) fn named_features(package: PackageMetadata<'_>) -> impl Iterator<Item = Self> + '_ {
912        let package_ix = package.package_ix();
913        package
914            .named_features_full()
915            .map(move |(feature_idx, _, _)| Self {
916                package_ix,
917                feature_idx,
918            })
919    }
920
921    pub(super) fn optional_deps(package: PackageMetadata<'_>) -> impl Iterator<Item = Self> + '_ {
922        let package_ix = package.package_ix();
923        package
924            .optional_deps_full()
925            .map(move |(feature_idx, _)| Self {
926                package_ix,
927                feature_idx,
928            })
929    }
930
931    pub(in crate::graph) fn package_ix(&self) -> NodeIndex<PackageIx> {
932        self.package_ix
933    }
934
935    pub(in crate::graph) fn package_id_and_feature_label<'g>(
936        &self,
937        graph: &'g PackageGraph,
938    ) -> (&'g PackageId, FeatureLabel<'g>) {
939        let package_id = &graph.dep_graph[self.package_ix];
940        let metadata = graph.metadata(package_id).unwrap();
941        let feature_label = metadata.feature_idx_to_label(self.feature_idx);
942        (package_id, feature_label)
943    }
944}
945
946/// Information about why a feature depends on another feature.
947///
948/// Not part of the stable API -- only exposed for FeatureSet::links().
949#[derive(Clone, Debug)]
950#[doc(hidden)]
951pub enum FeatureEdge {
952    /// This edge is from a feature to its base package.
953    FeatureToBase,
954
955    /// This is a dependency edge, e.g.:
956    ///
957    /// ```toml
958    /// [dependencies]
959    /// foo = { version = "1", features = ["a", "b"] }
960    /// ```
961    ///
962    /// (The above is conditional in that it isn't a build dependency. Similarly, it could be
963    /// a target-specific dependency.)
964    ///
965    /// This also includes optional dependencies, for which the "from" node is
966    /// `FeatureLabel::OptionalDependency` rather than `FeatureLabel::Base`.
967    ///
968    /// ```toml
969    /// [dependencies]
970    /// foo = { version = "1", features = ["a", "b"], optional = true }
971    /// ```
972    DependenciesSection(ConditionalLinkImpl),
973
974    /// This edge is from a feature depending on other features within the same package:
975    ///
976    /// ```toml
977    /// [features]
978    /// a = ["b"]
979    /// ```
980    NamedFeature,
981
982    /// This edge is from a feature to an optional dependency.
983    ///
984    /// ```toml
985    /// [features]
986    /// a = ["dep:foo"]
987    /// ```
988    NamedFeatureDepColon(ConditionalLinkImpl),
989
990    /// This is a named feature line of the form
991    ///
992    /// ```toml
993    /// [features]
994    /// a = ["foo/b"]
995    /// # or
996    /// a = ["foo?/b"]
997    /// ```
998    NamedFeatureWithSlash {
999        link: ConditionalLinkImpl,
1000        weak_index: Option<WeakIndex>,
1001    },
1002}
1003
1004/// Not part of the stable API -- only exposed for FeatureSet::links().
1005#[derive(Clone, Debug)]
1006#[doc(hidden)]
1007pub struct ConditionalLinkImpl {
1008    pub(super) package_edge_ix: EdgeIndex<PackageIx>,
1009    pub(super) normal: PlatformStatusImpl,
1010    pub(super) build: PlatformStatusImpl,
1011    pub(super) dev: PlatformStatusImpl,
1012}
1013
1014impl ConditionalLinkImpl {
1015    #[inline]
1016    fn dev_only(&self) -> bool {
1017        self.normal.is_never() && self.build.is_never()
1018    }
1019}
1020
1021/// Metadata for a particular feature node.
1022#[derive(Clone, Debug, Eq, Hash, PartialEq)]
1023pub(super) struct FeatureMetadataImpl {
1024    pub(super) feature_ix: NodeIndex<FeatureIx>,
1025}
1026
1027/// The kind of a particular feature within a package.
1028///
1029/// Returned by `FeatureMetadata`.
1030#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
1031pub enum FeatureKind {
1032    /// The "base" feature. Every package has one such feature.
1033    Base,
1034
1035    /// This is a named feature in the `[features]` section, or an implicit feature that corresponds to
1036    /// an optional dependency.
1037    ///
1038    /// For versions of Cargo prior to 1.60, optional dependencies always create implicit features
1039    /// by the same name. For versions 1.60 and greater, optional dependencies may create implicit
1040    /// features if the dependency doesn't exist with the name "dep" in it.
1041    Named,
1042
1043    /// This is an optional dependency.
1044    OptionalDependency,
1045}
1046
1047impl FeatureKind {
1048    /// Returns true if this is the base feature.
1049    #[inline]
1050    pub fn is_base(self) -> bool {
1051        matches!(self, Self::Base)
1052    }
1053
1054    /// Returns true if this is a named feature.
1055    #[inline]
1056    pub fn is_named(self) -> bool {
1057        matches!(self, Self::Named)
1058    }
1059
1060    /// Returns true if this is an optional dependency.
1061    #[inline]
1062    pub fn is_optional_dependency(self) -> bool {
1063        matches!(self, Self::OptionalDependency)
1064    }
1065}