guppy/graph/feature/

graph_impl.rs

// Copyright (c) The cargo-guppy Contributors
// SPDX-License-Identifier: MIT OR Apache-2.0

use crate::{
    DependencyKind, Error, PackageId,
    errors::FeatureGraphWarning,
    graph::{
        DependencyDirection, FeatureIndexInPackage, FeatureIx, PackageGraph, PackageIx,
        PackageLink, PackageMetadata,
        feature::{
            Cycles, FeatureFilter, FeatureList, WeakDependencies, WeakIndex,
            build::{FeatureGraphBuildState, FeaturePetgraph},
        },
    },
    petgraph_support::{scc::Sccs, topo::TopoWithCycles},
    platform::{PlatformStatus, PlatformStatusImpl},
};
use ahash::AHashMap;
use debug_ignore::DebugIgnore;
use once_cell::sync::OnceCell;
use petgraph::{
    algo::has_path_connecting,
    prelude::*,
    visit::{EdgeFiltered, IntoNodeReferences},
};
use smallvec::SmallVec;
use std::{fmt, iter, iter::FromIterator};

// Some general notes about feature graphs:
//
// The set of features for a package is the named features (in the [features] section), plus any
// optional dependencies.
//
// An optional dependency can be either normal or build -- not dev. Note that a dependency can be
// marked optional in one section and required in another. In this context, a dependency is a
// feature if it is marked as optional in any context.
//
// Features are *unified*. See the documentation in add_dependency_edges for more.
//
// There are a few ways features can be enabled. The most common is within a dependency spec. A
// feature can also be specified via the command-line. Finally, named features can specify what
// features a package depends on:
//
// ```toml
// [features]
// foo = ["a/bar", "optional-dep", "baz"]
// baz = []
// ```
//
// Feature names are unique. A named feature and an optional dep cannot have the same names.

impl PackageGraph {
    /// Returns a derived graph representing every feature of every package.
    ///
    /// The feature graph is constructed the first time this method is called. The graph is cached
    /// so that repeated calls to this method are cheap.
    pub fn feature_graph(&self) -> FeatureGraph<'_> {
        let inner = self.get_feature_graph();
        FeatureGraph {
            package_graph: self,
            inner,
        }
    }

    pub(super) fn get_feature_graph(&self) -> &FeatureGraphImpl {
        self.feature_graph
            .get_or_init(|| FeatureGraphImpl::new(self))
    }
}

/// A derived graph representing every feature of every package.
///
/// Constructed through `PackageGraph::feature_graph`.
#[derive(Clone, Copy, Debug)]
pub struct FeatureGraph<'g> {
    pub(crate) package_graph: &'g PackageGraph,
    pub(super) inner: &'g FeatureGraphImpl,
}

assert_covariant!(FeatureGraph);

impl<'g> FeatureGraph<'g> {
    /// Returns any non-fatal warnings encountered while constructing the feature graph.
    pub fn build_warnings(&self) -> &'g [FeatureGraphWarning] {
        &self.inner.warnings
    }

    /// Returns the `PackageGraph` from which this feature graph was constructed.
    pub fn package_graph(&self) -> &'g PackageGraph {
        self.package_graph
    }

    /// Returns the total number of (package ID, feature) combinations in this graph.
    ///
    /// Includes the "base" feature for each package.
    pub fn feature_count(&self) -> usize {
        self.dep_graph().node_count()
    }

    /// Returns the number of links in this graph.
    pub fn link_count(&self) -> usize {
        self.dep_graph().edge_count()
    }

    /// Returns true if this feature graph contains the specified feature.
    pub fn contains(&self, feature_id: impl Into<FeatureId<'g>>) -> bool {
        let feature_id = feature_id.into();
        FeatureNode::from_id(self, feature_id).is_some()
    }

    /// Returns metadata for the given feature ID, or `None` if the feature wasn't found.
    pub fn metadata(
        &self,
        feature_id: impl Into<FeatureId<'g>>,
    ) -> Result<FeatureMetadata<'g>, Error> {
        let feature_id = feature_id.into();
        let feature_node = FeatureNode::from_id(self, feature_id)
            .ok_or_else(|| Error::unknown_feature_id(feature_id))?;
        self.metadata_for_node(feature_node)
            .ok_or_else(|| Error::unknown_feature_id(feature_id))
    }

    /// Returns all known features for a package.
    ///
    /// Returns an error if the package ID was unknown.
    pub fn all_features_for(&self, package_id: &PackageId) -> Result<FeatureList<'g>, Error> {
        let package = self.package_graph.metadata(package_id)?;
        let dep_graph = self.dep_graph();
        let features = self
            .feature_ixs_for_package_ix(package.package_ix())
            .map(|feature_ix| FeatureId::node_to_feature(package, &dep_graph[feature_ix]));
        Ok(FeatureList::new(package, features))
    }

    /// Returns true if this feature is included in a package's build by default.
    ///
    /// Returns an error if this feature ID is unknown.
    ///
    /// ## Cycles
    ///
    /// A cyclic dev-dependency may cause additional features to be turned on. This computation
    /// does *not* follow conditional links and will *not* return true for such additional
    /// features.
    pub fn is_default_feature<'a>(
        &self,
        feature_id: impl Into<FeatureId<'a>>,
    ) -> Result<bool, Error> {
        let feature_id = feature_id.into();
        let default_ix = self.feature_ix(
            self.package_graph
                .metadata(feature_id.package_id())?
                .default_feature_id(),
        )?;
        let feature_ix = self.feature_ix(feature_id)?;
        // Do not follow conditional links.
        Ok(self.feature_ix_depends_on_no_conditional(default_ix, feature_ix))
    }

    /// Returns true if `feature_a` depends (directly or indirectly) on `feature_b`.
    ///
    /// In other words, this returns true if `feature_b` is a (possibly transitive) dependency of
    /// `feature_a`.
    ///
    /// This also returns true if `feature_a` is the same as `feature_b`.
    ///
    /// Note that this returns true if `feature_a` [conditionally depends on][ConditionalLink] `feature_b`.
    pub fn depends_on<'a>(
        &self,
        feature_a: impl Into<FeatureId<'a>>,
        feature_b: impl Into<FeatureId<'a>>,
    ) -> Result<bool, Error> {
        let feature_a = feature_a.into();
        let feature_b = feature_b.into();
        let a_ix = self.feature_ix(feature_a)?;
        let b_ix = self.feature_ix(feature_b)?;
        Ok(self.feature_ix_depends_on(a_ix, b_ix))
    }

    /// Returns true if `feature_a` directly depends on `feature_b`.
    ///
    /// In other words, this returns true if `feature_b` is a direct dependency of `feature_a`.
    ///
    /// If `feature_a` is the same as `feature_b`, this returns true only if
    /// the feature has a self-loop edge in the feature graph.
    pub fn directly_depends_on<'a>(
        &self,
        feature_a: impl Into<FeatureId<'a>>,
        feature_b: impl Into<FeatureId<'a>>,
    ) -> Result<bool, Error> {
        let feature_a = feature_a.into();
        let feature_b = feature_b.into();
        let a_ix = self.feature_ix(feature_a)?;
        let b_ix = self.feature_ix(feature_b)?;
        Ok(self.dep_graph().contains_edge(a_ix, b_ix))
    }

    /// Returns information about dependency cycles.
    ///
    /// For more information, see the documentation for `Cycles`.
    pub fn cycles(&self) -> Cycles<'g> {
        Cycles::new(*self)
    }

    // ---
    // Helper methods
    // ---

    /// Verify basic properties of the feature graph.
    #[doc(hidden)]
    pub fn verify(&self) -> Result<(), Error> {
        let feature_set = self.resolve_all();
        for conditional_link in feature_set.conditional_links(DependencyDirection::Forward) {
            let (from, to) = conditional_link.endpoints();
            let is_any = conditional_link.normal().is_present()
                || conditional_link.build().is_present()
                || conditional_link.dev().is_present();

            if !is_any {
                return Err(Error::FeatureGraphInternalError(format!(
                    "{} -> {}: no edge info found",
                    from.feature_id(),
                    to.feature_id()
                )));
            }
        }

        Ok(())
    }

    /// Returns the strongly connected components for this feature graph.
    pub(super) fn sccs(&self) -> &'g Sccs<FeatureIx> {
        self.inner.sccs.get_or_init(|| {
            let edge_filtered =
                EdgeFiltered::from_fn(self.dep_graph(), |edge| match edge.weight() {
                    FeatureEdge::DependenciesSection(link)
                    | FeatureEdge::NamedFeatureDepColon(link)
                    | FeatureEdge::NamedFeatureWithSlash { link, .. } => !link.dev_only(),
                    FeatureEdge::NamedFeature | FeatureEdge::FeatureToBase => true,
                });
            // Sort the entire graph without dev-only edges -- a correct graph would be cycle-free
            // but we don't currently do a consistency check for this so handle cycles.
            // TODO: should we check at construction time? or bubble up a warning somehow?
            let topo = TopoWithCycles::new(&edge_filtered);
            Sccs::new(&self.inner.graph, |scc| {
                topo.sort_nodes(scc);
            })
        })
    }

    fn metadata_impl(&self, feature_id: FeatureId<'g>) -> Option<&'g FeatureMetadataImpl> {
        let feature_node = FeatureNode::from_id(self, feature_id)?;
        self.metadata_impl_for_node(&feature_node)
    }

    pub(in crate::graph) fn metadata_for_ix(
        &self,
        feature_ix: NodeIndex<FeatureIx>,
    ) -> FeatureMetadata<'g> {
        self.metadata_for_node(self.dep_graph()[feature_ix])
            .expect("valid feature ix")
    }

    pub(super) fn metadata_for_node(&self, node: FeatureNode) -> Option<FeatureMetadata<'g>> {
        let inner = self.metadata_impl_for_node(&node)?;
        Some(FeatureMetadata {
            graph: DebugIgnore(*self),
            node,
            inner,
        })
    }

    #[inline]
    fn metadata_impl_for_node(&self, node: &FeatureNode) -> Option<&'g FeatureMetadataImpl> {
        self.inner.map.get(node)
    }

    pub(super) fn dep_graph(&self) -> &'g FeaturePetgraph {
        &self.inner.graph
    }

    /// If this is a conditional edge, returns the link or links it is evaluated
    /// as during a resolve. Otherwise, return None.
    pub(super) fn edge_to_links(
        &self,
        source_ix: NodeIndex<FeatureIx>,
        target_ix: NodeIndex<FeatureIx>,
        edge_ix: EdgeIndex<FeatureIx>,
        edge: Option<&'g FeatureEdge>,
    ) -> Option<EdgeLinks<'g>> {
        let edge = edge.unwrap_or_else(|| &self.dep_graph()[edge_ix]);
        let make = |inner| ConditionalLink::new(*self, source_ix, target_ix, edge_ix, inner);

        match edge {
            FeatureEdge::NamedFeature | FeatureEdge::FeatureToBase => None,
            FeatureEdge::DependenciesSection(link) | FeatureEdge::NamedFeatureDepColon(link) => {
                // Dependency section and dep:foo style conditional links are always non-weak.
                Some(EdgeLinks::NonWeak(make(link)))
            }
            FeatureEdge::NamedFeatureWithSlash { link, slash } => Some(match slash {
                SlashForm::Weak(weak) => EdgeLinks::Weak {
                    required: weak.required.as_ref().map(|half| make(half.get())),
                    optional: make(weak.optional.get()),
                    index: weak.index,
                },
                SlashForm::Strong => EdgeLinks::NonWeak(make(link)),
            }),
        }
    }

    /// If this is a conditional edge, returns the link covering every
    /// declaration it was derived from.
    pub(super) fn edge_to_full_link(
        &self,
        source_ix: NodeIndex<FeatureIx>,
        target_ix: NodeIndex<FeatureIx>,
        edge_ix: EdgeIndex<FeatureIx>,
        edge: Option<&'g FeatureEdge>,
    ) -> Option<ConditionalLink<'g>> {
        let edge = edge.unwrap_or_else(|| &self.dep_graph()[edge_ix]);
        let link = match edge {
            FeatureEdge::NamedFeature | FeatureEdge::FeatureToBase => return None,
            FeatureEdge::DependenciesSection(link)
            | FeatureEdge::NamedFeatureDepColon(link)
            | FeatureEdge::NamedFeatureWithSlash { link, slash: _ } => link,
        };
        Some(ConditionalLink::new(
            *self, source_ix, target_ix, edge_ix, link,
        ))
    }

    fn feature_ix_depends_on(
        &self,
        a_ix: NodeIndex<FeatureIx>,
        b_ix: NodeIndex<FeatureIx>,
    ) -> bool {
        has_path_connecting(self.dep_graph(), a_ix, b_ix, None)
    }

    fn feature_ix_depends_on_no_conditional(
        &self,
        a_ix: NodeIndex<FeatureIx>,
        b_ix: NodeIndex<FeatureIx>,
    ) -> bool {
        // Filter out conditional edges.
        let edge_filtered =
            EdgeFiltered::from_fn(self.dep_graph(), |edge_ref| match edge_ref.weight() {
                FeatureEdge::FeatureToBase | FeatureEdge::NamedFeature => true,
                FeatureEdge::DependenciesSection(_)
                | FeatureEdge::NamedFeatureDepColon(_)
                | FeatureEdge::NamedFeatureWithSlash { .. } => false,
            });
        has_path_connecting(&edge_filtered, a_ix, b_ix, None)
    }

    pub(super) fn feature_ixs_for_package_ix(
        &self,
        package_ix: NodeIndex<PackageIx>,
    ) -> impl Iterator<Item = NodeIndex<FeatureIx>> + use<> {
        let package_ix = package_ix.index();
        let base_ix = self.inner.base_ixs[package_ix].index();
        // base_ixs has (package count + 1) elements so this access is valid.
        let next_base_ix = self.inner.base_ixs[package_ix + 1].index();

        (base_ix..next_base_ix).map(NodeIndex::new)
    }

    pub(super) fn feature_ixs_for_package_ixs<I>(
        &self,
        package_ixs: I,
    ) -> impl Iterator<Item = NodeIndex<FeatureIx>> + 'g + use<'g, I>
    where
        I: IntoIterator<Item = NodeIndex<PackageIx>> + 'g,
    {
        // Create a copy of FeatureGraph that will be moved into the closure below.
        let this = *self;

        package_ixs
            .into_iter()
            .flat_map(move |package_ix| this.feature_ixs_for_package_ix(package_ix))
    }

    pub(in crate::graph) fn feature_ixs_for_package_ixs_filtered<B>(
        &self,
        package_ixs: impl IntoIterator<Item = NodeIndex<PackageIx>>,
        filter: impl FeatureFilter<'g>,
    ) -> B
    where
        B: FromIterator<NodeIndex<FeatureIx>>,
    {
        let mut filter = filter;

        self.feature_ixs_for_package_ixs(package_ixs)
            .filter(|feature_ix| {
                let feature_node = &self.dep_graph()[*feature_ix];
                filter.accept(self, FeatureId::from_node(self.package_graph, feature_node))
            })
            .collect()
    }

    pub(in crate::graph) fn package_ix_for_feature_ix(
        &self,
        feature_ix: NodeIndex<FeatureIx>,
    ) -> NodeIndex<PackageIx> {
        let feature_node = &self.dep_graph()[feature_ix];
        feature_node.package_ix()
    }

    #[allow(dead_code)]
    pub(super) fn feature_ixs<'a, B>(
        &self,
        feature_ids: impl IntoIterator<Item = FeatureId<'g>>,
    ) -> Result<B, Error>
    where
        B: iter::FromIterator<NodeIndex<FeatureIx>>,
    {
        feature_ids
            .into_iter()
            .map(|feature_id| self.feature_ix(feature_id))
            .collect()
    }

    pub(super) fn feature_ix(
        &self,
        feature_id: FeatureId<'g>,
    ) -> Result<NodeIndex<FeatureIx>, Error> {
        let metadata = self
            .metadata_impl(feature_id)
            .ok_or_else(|| Error::unknown_feature_id(feature_id))?;
        Ok(metadata.feature_ix)
    }
}

/// An identifier for a (package, feature) pair in a feature graph.
///
/// Returned by various methods on `FeatureGraph` and `FeatureQuery`.
///
/// `From` impls are available for `(&'g PackageId, &'g str)` and `(&'g PackageId, Option<&'g str>)`
/// tuples.
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct FeatureId<'g> {
    package_id: &'g PackageId,
    label: FeatureLabel<'g>,
}

assert_covariant!(FeatureId);

impl<'g> FeatureId<'g> {
    /// Creates a new `FeatureId` with the given [`PackageId`] and [`FeatureLabel`].
    pub fn new(package_id: &'g PackageId, label: FeatureLabel<'g>) -> Self {
        Self { package_id, label }
    }

    /// Creates a new `FeatureId` representing a named feature in the `[features]` section,
    /// or an implicit named feature created by an optional dependency.
    pub fn named(package_id: &'g PackageId, feature_name: &'g str) -> Self {
        Self {
            package_id,
            label: FeatureLabel::Named(feature_name),
        }
    }

    /// Creates a new `FeatureId` representing an optional dependency.
    pub fn optional_dependency(package_id: &'g PackageId, dep_name: &'g str) -> Self {
        Self {
            package_id,
            label: FeatureLabel::OptionalDependency(dep_name),
        }
    }

    /// Creates a new `FeatureId` representing the base feature for a package.
    pub fn base(package_id: &'g PackageId) -> Self {
        Self {
            package_id,
            label: FeatureLabel::Base,
        }
    }

    pub(super) fn from_node(package_graph: &'g PackageGraph, node: &FeatureNode) -> Self {
        let package_id = &package_graph.dep_graph[node.package_ix];
        let metadata = package_graph
            .metadata(package_id)
            .expect("package ID should have valid metadata");
        let feature = Self::node_to_feature(metadata, node);
        Self {
            package_id,
            label: feature,
        }
    }

    pub(super) fn node_to_feature(
        metadata: PackageMetadata<'g>,
        node: &FeatureNode,
    ) -> FeatureLabel<'g> {
        metadata.feature_idx_to_label(node.feature_idx)
    }

    /// Returns the package ID.
    pub fn package_id(&self) -> &'g PackageId {
        self.package_id
    }

    /// Returns the [`FeatureLabel`] associated with the feature.
    pub fn label(&self) -> FeatureLabel<'g> {
        self.label
    }

    /// Returns true if this is the base feature for the package.
    #[inline]
    pub fn is_base(&self) -> bool {
        self.label.kind().is_base()
    }

    /// Returns true if this is an optional dependency.
    #[inline]
    pub fn is_optional_dependency(self) -> bool {
        self.label.kind().is_optional_dependency()
    }

    /// Returns true if this is a named feature.
    #[inline]
    pub fn is_named(self) -> bool {
        self.label.kind().is_named()
    }
}

impl<'g> From<(&'g PackageId, FeatureLabel<'g>)> for FeatureId<'g> {
    fn from((package_id, label): (&'g PackageId, FeatureLabel<'g>)) -> Self {
        FeatureId { package_id, label }
    }
}

/// The `Display` impl prints out:
///
/// * `{package-id}/[base]` for base features.
/// * `{package-id}/feature-name` for named features.
/// * `{package-id}/dep:dep-name` for optional dependencies.
///
/// ## Examples
///
/// ```
/// use guppy::PackageId;
/// use guppy::graph::feature::FeatureId;
///
/// let package_id = PackageId::new("region 2.1.2 (registry+https://github.com/rust-lang/crates.io-index)");
///
/// assert_eq!(
///     format!("{}", FeatureId::base(&package_id)),
///     "region 2.1.2 (registry+https://github.com/rust-lang/crates.io-index)/[base]"
/// );
///
/// assert_eq!(
///     format!("{}", FeatureId::named(&package_id, "foo")),
///     "region 2.1.2 (registry+https://github.com/rust-lang/crates.io-index)/foo"
/// );
///
/// assert_eq!(
///     format!("{}", FeatureId::optional_dependency(&package_id, "bar")),
///     "region 2.1.2 (registry+https://github.com/rust-lang/crates.io-index)/dep:bar"
/// );
/// ```
impl fmt::Display for FeatureId<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}/{}", self.package_id, self.label)
    }
}

/// A unique identifier for a feature within a specific package. Forms part of a [`FeatureId`].
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub enum FeatureLabel<'g> {
    /// The "base" feature. Every package has one such feature.
    Base,

    /// This is a named feature in the `[features]` section, or an implicit feature that corresponds to
    /// an optional dependency.
    ///
    /// For versions of Cargo prior to 1.60, optional dependencies always create implicit features
    /// by the same name. For versions 1.60 and greater, optional dependencies may create implicit
    /// features if the dependency doesn't exist with the name "dep" in it.
    Named(&'g str),

    /// This is an optional dependency.
    OptionalDependency(&'g str),
}

impl FeatureLabel<'_> {
    /// Returns the kind of feature this is.
    ///
    /// The kind of a feature is simply the enum variant without any associated data.
    #[inline]
    pub fn kind(self) -> FeatureKind {
        match self {
            Self::Base => FeatureKind::Base,
            Self::Named(_) => FeatureKind::Named,
            Self::OptionalDependency(_) => FeatureKind::OptionalDependency,
        }
    }
}

/// The `Display` impl for `FeatureLabel` prints out:
///
/// * `[base]` for base labels.
/// * `feature-name` for optional dependencies.
/// * `dep:dep-name` for named features.
///
/// ## Examples
///
/// ```
/// use guppy::graph::feature::FeatureLabel;
///
/// assert_eq!(format!("{}", FeatureLabel::Base), "[base]");
/// assert_eq!(format!("{}", FeatureLabel::Named("foo")), "foo");
/// assert_eq!(format!("{}", FeatureLabel::OptionalDependency("bar")), "dep:bar");
/// ```
impl fmt::Display for FeatureLabel<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Base => write!(f, "[base]"),
            Self::Named(feature_name) => write!(f, "{feature_name}"),
            Self::OptionalDependency(dep_name) => write!(f, "dep:{dep_name}"),
        }
    }
}

/// Metadata for a feature within a package.
#[derive(Clone, Copy)]
pub struct FeatureMetadata<'g> {
    graph: DebugIgnore<FeatureGraph<'g>>,
    node: FeatureNode,
    inner: &'g FeatureMetadataImpl,
}

assert_covariant!(FeatureMetadata);

impl<'g> FeatureMetadata<'g> {
    /// Returns the feature ID corresponding to this metadata.
    pub fn feature_id(&self) -> FeatureId<'g> {
        FeatureId::from_node(self.graph.package_graph, &self.node)
    }

    /// Returns the package ID corresponding to this metadata.
    pub fn package_id(&self) -> &'g PackageId {
        &self.graph.package_graph.dep_graph[self.package_ix()]
    }

    /// Returns the package metadata corresponding to this feature metadata.
    pub fn package(&self) -> PackageMetadata<'g> {
        self.graph
            .package_graph
            .metadata(self.package_id())
            .expect("valid package ID")
    }

    /// Returns the label for this feature.
    pub fn label(&self) -> FeatureLabel<'g> {
        self.feature_id().label()
    }

    // ---
    // Helper methods
    // ---

    #[inline]
    pub(in crate::graph) fn package_ix(&self) -> NodeIndex<PackageIx> {
        self.node.package_ix
    }

    #[inline]
    pub(in crate::graph) fn feature_ix(&self) -> NodeIndex<FeatureIx> {
        self.inner.feature_ix
    }
}

impl fmt::Debug for FeatureMetadata<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("FeatureMetadata")
            .field("id", &self.feature_id())
            .finish()
    }
}

/// A graph representing every possible feature of every package, and the connections between them.
#[derive(Clone, Debug)]
pub(in crate::graph) struct FeatureGraphImpl {
    pub(super) graph: FeaturePetgraph,
    // base ixs consists of the base (start) feature indexes for each package.
    pub(super) base_ixs: Vec<NodeIndex<FeatureIx>>,
    pub(super) map: AHashMap<FeatureNode, FeatureMetadataImpl>,
    pub(super) warnings: Vec<FeatureGraphWarning>,
    // The strongly connected components of the feature graph. Computed on demand.
    pub(super) sccs: OnceCell<Sccs<FeatureIx>>,
    pub(super) weak: WeakDependencies,
}

impl FeatureGraphImpl {
    /// Creates a new `FeatureGraph` from this `PackageGraph`.
    pub(super) fn new(package_graph: &PackageGraph) -> Self {
        let mut build_state = FeatureGraphBuildState::new(package_graph);

        // Graph returns its node references in order -- check this in debug builds.
        let mut prev_ix = None;
        for (package_ix, package_id) in package_graph.dep_graph.node_references() {
            if let Some(prev_ix) = prev_ix {
                debug_assert_eq!(package_ix.index(), prev_ix + 1, "package ixs are in order");
            }
            prev_ix = Some(package_ix.index());

            let metadata = package_graph
                .metadata(package_id)
                .expect("valid package ID");
            build_state.add_nodes(metadata);
        }

        build_state.end_nodes();

        // The choice of bottom-up for this loop and the next is pretty arbitrary.
        for metadata in package_graph
            .resolve_all()
            .packages(DependencyDirection::Reverse)
        {
            build_state.add_named_feature_edges(metadata);
        }

        for link in package_graph
            .resolve_all()
            .links(DependencyDirection::Reverse)
        {
            build_state.add_dependency_edges(link);
        }

        build_state.build()
    }
}

/// A feature dependency that is conditionally activated.
///
/// A `ConditionalLink` is typically a link across packages. For example:
///
/// ```toml
/// [package]
/// name = "main"
///
/// [dependencies]
/// dep = { ... }
///
/// [dev-dependencies]
/// dev-dep = { ... }
///
/// [target.'cfg(unix)'.dependencies]
/// unix-dep = { ... }
///
/// [features]
/// feat = ["dep/feat", "dev-dep/feat", "unix-dep/feat"]
/// ```
///
/// In this example, there are `ConditionalLink`s from `main/feat` to `dep/feat`, `dev-dep/feat` and
/// `unix-dep/feat`. Each link is only activated if the conditions for it are met. For example,
/// the link to `dev-dep/feat` is only followed if Cargo is interested in dev-dependencies of `main`.
///
/// If a dependency, for example `unix-dep` above, is optional, an implicit feature is created in
/// the package `main` with the name `unix-dep`. In this case, the dependency from `main/feat` to
/// `main/unix-dep` is also a `ConditionalLink` representing the same `cfg(unix)` condition.
#[derive(Copy, Clone)]
pub struct ConditionalLink<'g> {
    graph: DebugIgnore<FeatureGraph<'g>>,
    from: &'g FeatureMetadataImpl,
    to: &'g FeatureMetadataImpl,
    edge_ix: EdgeIndex<FeatureIx>,
    inner: &'g ConditionalLinkImpl,
}

assert_covariant!(ConditionalLink);

impl<'g> ConditionalLink<'g> {
    #[allow(dead_code)]
    pub(super) fn new(
        graph: FeatureGraph<'g>,
        source_ix: NodeIndex<FeatureIx>,
        target_ix: NodeIndex<FeatureIx>,
        edge_ix: EdgeIndex<FeatureIx>,
        inner: &'g ConditionalLinkImpl,
    ) -> Self {
        let dep_graph = graph.dep_graph();
        Self {
            graph: DebugIgnore(graph),
            from: graph
                .metadata_impl_for_node(&dep_graph[source_ix])
                .expect("valid source ix"),
            to: graph
                .metadata_impl_for_node(&dep_graph[target_ix])
                .expect("valid target ix"),
            edge_ix,
            inner,
        }
    }

    /// Returns the feature which depends on the `to` feature.
    pub fn from(&self) -> FeatureMetadata<'g> {
        FeatureMetadata {
            graph: DebugIgnore(self.graph.0),
            node: self.graph.dep_graph()[self.from.feature_ix],
            inner: self.from,
        }
    }

    /// Returns the feature which is depended on by the `from` feature.
    pub fn to(&self) -> FeatureMetadata<'g> {
        FeatureMetadata {
            graph: DebugIgnore(self.graph.0),
            node: self.graph.dep_graph()[self.to.feature_ix],
            inner: self.to,
        }
    }

    /// Returns the endpoints as a pair of features `(from, to)`.
    pub fn endpoints(&self) -> (FeatureMetadata<'g>, FeatureMetadata<'g>) {
        (self.from(), self.to())
    }

    /// Returns details about this feature dependency from the `[dependencies]` section.
    pub fn normal(&self) -> PlatformStatus<'g> {
        PlatformStatus::new(&self.inner.normal)
    }

    /// Returns details about this feature dependency from the `[build-dependencies]` section.
    pub fn build(&self) -> PlatformStatus<'g> {
        PlatformStatus::new(&self.inner.build)
    }

    /// Returns details about this feature dependency from the `[dev-dependencies]` section.
    pub fn dev(&self) -> PlatformStatus<'g> {
        PlatformStatus::new(&self.inner.dev)
    }

    /// Returns details about this feature dependency from the section specified by the given
    /// dependency kind.
    pub fn status_for_kind(&self, kind: DependencyKind) -> PlatformStatus<'g> {
        match kind {
            DependencyKind::Normal => self.normal(),
            DependencyKind::Build => self.build(),
            DependencyKind::Development => self.dev(),
        }
    }

    /// Returns true if this edge is dev-only, i.e. code from this edge will not
    /// be included in normal builds.
    ///
    /// This is scoped to the declarations for this link. For example, a
    /// dependency might be optional as a normal dependency but required as a
    /// dev-dependency. In that case, the
    /// [`Required`](LinkDeclarations::Required) version of the link is dev-only
    /// while the [`Optional`](LinkDeclarations::Optional) half is not.
    /// [`Unsplit`](LinkDeclarations::Unsplit) is the union of both, so it
    /// isn't dev-only either.
    pub fn dev_only(&self) -> bool {
        self.inner.dev_only()
    }

    /// Returns the declarations of the dependency that this link's platform
    /// statuses were derived from.
    ///
    /// A package can declare the same dependency more than once, and some of
    /// those declarations can be optional while others are required. For
    /// example:
    ///
    /// ```toml
    /// [dependencies]
    /// foo = { version = "1" }
    ///
    /// [build-dependencies]
    /// foo = { version = "1", optional = true }
    ///
    /// [features]
    /// weak = ["foo?/std"]
    /// ```
    ///
    /// Cargo applies `foo?/std` to each declaration separately.
    ///
    /// * The required normal dependency gets `std` as soon as `weak` is
    ///   enabled.
    /// * The optional build dependency gets `std` only if `dep:foo` is
    ///   also activated.
    ///
    /// To model this, [`FeatureQuery::resolve_with`] may call the visitor twice
    /// for the link from `main/weak` to `foo/std`:
    ///
    /// * Once with a [`Required`](LinkDeclarations::Required) link. Here,
    ///   [`normal`](Self::normal) is always enabled and
    ///   [`build`](Self::build) is never enabled.
    /// * Once with an [`Optional`](LinkDeclarations::Optional) link. Here,
    ///   `normal` is never enabled and `build` is always enabled.
    ///
    /// Both links have the same [`from`](Self::from) and [`to`](Self::to); this
    /// method is the way to tell them apart. The link is followed if the
    /// visitor accepts either one.
    ///
    /// If `foo` has no required declarations for this package, the required
    /// link is skipped.
    /// When each link is offered depends on the query's direction; see
    /// [`FeatureLinkVisitor::visit_link`].
    ///
    /// Outside of a resolve, the same edge is a single link.
    /// [`FeatureSet::conditional_links`] returns it once, with
    /// [`Unsplit`](LinkDeclarations::Unsplit) and the union of both sets of
    /// statuses.
    ///
    /// For other kinds of links, the return value is fixed:
    ///
    /// * A link from a feature with `foo/std` to `foo`'s `std` feature is
    ///   `Unsplit`, since `foo/std` applies to every declaration of `foo` that
    ///   resolves to that package.
    /// * A link from a feature with `foo/std` to `dep:foo`, or to a feature
    ///   named `foo` in the same package, is `Optional`, since only optional
    ///   declarations of `foo` activate these.
    /// * A link from a feature with `dep:foo` to `dep:foo` is `Unsplit`, since
    ///   `dep:foo` activates every declaration of `foo`.
    /// * A link from a package's base feature into a dependency is `Required`.
    /// * A link from `dep:foo` into `foo` is `Optional`.
    ///
    /// [`FeatureQuery::resolve_with`]: crate::graph::feature::FeatureQuery::resolve_with
    /// [`FeatureSet::conditional_links`]: crate::graph::feature::FeatureSet::conditional_links
    /// [`FeatureLinkVisitor::visit_link`]: crate::graph::feature::FeatureLinkVisitor::visit_link
    pub fn declarations(&self) -> LinkDeclarations {
        self.inner.declarations
    }

    /// Returns the `PackageLink`s this `ConditionalLink` was derived from.
    ///
    /// This is usually one link, but in some circumstances a single name can
    /// resolve to several packages. For example, consider this `Cargo.toml`:
    ///
    /// ```toml
    /// [package]
    /// name = "main"
    ///
    /// [dependencies]
    /// serde = { package = "serde_core", version = "1", optional = true }
    ///
    /// # Never enabled on any platform, but still resolved and locked.
    /// [target.'cfg(any())'.dependencies]
    /// serde = { version = "1", optional = true }
    ///
    /// [features]
    /// serde = ["dep:serde", "serde/std"]
    /// ```
    ///
    /// The package graph has two links out of `main`, `main -> serde_core` and
    /// `main -> serde`, both with the dependency name `serde`. The feature
    /// `serde` produces three conditional links:
    ///
    /// * `main/serde -> main/dep:serde`, from `dep:serde`. This activates the
    ///   dependency name, so this method returns both `main -> serde_core` and
    ///   `main -> serde`. The link's platform status is the union of theirs.
    /// * `main/serde -> serde_core/std`, from `serde/std`. This method returns
    ///   only `main -> serde_core`.
    /// * `main/serde -> serde/std`, also from `serde/std`. This method returns
    ///   only `main -> serde`.
    ///
    /// A link that covers only some declarations (see
    /// [`declarations`](Self::declarations)) omits packages with none of those
    /// declarations. For example, a link from `foo/std` to `dep:foo` covers
    /// only optional declarations, so it omits a package that is only ever a
    /// required dependency named `foo`.
    ///
    /// The order in which links are returned is unspecified.
    pub fn package_links(&self) -> impl ExactSizeIterator<Item = PackageLink<'g>> + 'g {
        let package_graph = self.graph.package_graph;
        self.inner
            .package_edge_ixs
            .iter()
            .map(move |edge_ix| package_graph.edge_ix_to_link(edge_ix))
    }

    // ---
    // Helper methods
    // ---

    #[allow(dead_code)]
    pub(super) fn edge_ix(&self) -> EdgeIndex<FeatureIx> {
        self.edge_ix
    }

    pub(super) fn endpoints_in(
        &self,
        direction: DependencyDirection,
    ) -> (FeatureMetadata<'g>, FeatureMetadata<'g>) {
        match direction {
            DependencyDirection::Forward => (self.from(), self.to()),
            DependencyDirection::Reverse => (self.to(), self.from()),
        }
    }
}

impl fmt::Debug for ConditionalLink<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("ConditionalLink")
            .field("from", &self.from())
            .field("to", &self.to())
            .field("declarations", &self.declarations())
            .field("normal", &self.normal())
            .field("build", &self.build())
            .field("dev", &self.dev())
            .finish()
    }
}

// ---

/// A combination of a package ID and a feature name, forming a node in a `FeatureGraph`.
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub(in crate::graph) struct FeatureNode {
    package_ix: NodeIndex<PackageIx>,
    feature_idx: FeatureIndexInPackage,
}

impl FeatureNode {
    /// Returns a new feature node.
    pub(in crate::graph) fn new(
        package_ix: NodeIndex<PackageIx>,
        feature_idx: FeatureIndexInPackage,
    ) -> Self {
        Self {
            package_ix,
            feature_idx,
        }
    }

    /// Base feature node.
    pub(in crate::graph) fn base(package_ix: NodeIndex<PackageIx>) -> Self {
        Self {
            package_ix,
            feature_idx: FeatureIndexInPackage::Base,
        }
    }

    pub(in crate::graph) fn optional_dep(package_ix: NodeIndex<PackageIx>, dep_idx: usize) -> Self {
        Self {
            package_ix,
            feature_idx: FeatureIndexInPackage::OptionalDependency(dep_idx),
        }
    }

    pub(in crate::graph) fn named_feature(
        package_ix: NodeIndex<PackageIx>,
        named_idx: usize,
    ) -> Self {
        Self {
            package_ix,
            feature_idx: FeatureIndexInPackage::Named(named_idx),
        }
    }

    fn from_id(feature_graph: &FeatureGraph<'_>, id: FeatureId<'_>) -> Option<Self> {
        let metadata = feature_graph.package_graph.metadata(id.package_id()).ok()?;
        Some(FeatureNode::new(
            metadata.package_ix(),
            metadata.get_feature_idx(id.label())?,
        ))
    }

    pub(super) fn named_features(package: PackageMetadata<'_>) -> impl Iterator<Item = Self> + '_ {
        let package_ix = package.package_ix();
        package
            .named_features_full()
            .map(move |(feature_idx, _, _)| Self {
                package_ix,
                feature_idx,
            })
    }

    pub(super) fn optional_deps(package: PackageMetadata<'_>) -> impl Iterator<Item = Self> + '_ {
        let package_ix = package.package_ix();
        package
            .optional_deps_full()
            .map(move |(feature_idx, _)| Self {
                package_ix,
                feature_idx,
            })
    }

    pub(in crate::graph) fn package_ix(&self) -> NodeIndex<PackageIx> {
        self.package_ix
    }

    pub(in crate::graph) fn package_id_and_feature_label<'g>(
        &self,
        graph: &'g PackageGraph,
    ) -> (&'g PackageId, FeatureLabel<'g>) {
        let package_id = &graph.dep_graph[self.package_ix];
        let metadata = graph.metadata(package_id).unwrap();
        let feature_label = metadata.feature_idx_to_label(self.feature_idx);
        (package_id, feature_label)
    }
}

/// The conditional link or links an edge is evaluated as during a resolve.
pub(super) enum EdgeLinks<'g> {
    /// A non-weak conditional link, evaluated once.
    NonWeak(ConditionalLink<'g>),

    /// A weak link, `a = ["foo?/b"]`.
    Weak {
        /// The link covering required declarations of this dependency.
        ///
        /// This is `None` if the dependency is never declared as required.
        required: Option<ConditionalLink<'g>>,

        /// The link covering optional declarations of this dependency.
        optional: ConditionalLink<'g>,

        /// The index of the buffer that holds `optional` back in a forward
        /// query.
        index: WeakIndex,
    },
}

/// Information about why a feature depends on another feature.
///
/// Not part of the stable API -- only exposed for FeatureSet::links().
#[derive(Clone, Debug)]
#[doc(hidden)]
pub enum FeatureEdge {
    /// This edge is from a feature to its base package.
    FeatureToBase,

    /// This is a dependency edge, e.g.:
    ///
    /// ```toml
    /// [dependencies]
    /// foo = { version = "1", features = ["a", "b"] }
    /// ```
    ///
    /// (The above is conditional in that it isn't a build dependency. Similarly, it could be
    /// a target-specific dependency.)
    ///
    /// This also includes optional dependencies, for which the "from" node is
    /// `FeatureLabel::OptionalDependency` rather than `FeatureLabel::Base`.
    ///
    /// ```toml
    /// [dependencies]
    /// foo = { version = "1", features = ["a", "b"], optional = true }
    /// ```
    DependenciesSection(ConditionalLinkImpl),

    /// This edge is from a feature depending on other features within the same package:
    ///
    /// ```toml
    /// [features]
    /// a = ["b"]
    /// ```
    NamedFeature,

    /// This edge is from a feature to an optional dependency.
    ///
    /// ```toml
    /// [features]
    /// a = ["dep:foo"]
    /// ```
    NamedFeatureDepColon(ConditionalLinkImpl),

    /// This is a named feature line of the form
    ///
    /// ```toml
    /// [features]
    /// a = ["foo/b"]
    /// # or
    /// a = ["foo?/b"]
    /// ```
    NamedFeatureWithSlash {
        link: ConditionalLinkImpl,
        slash: SlashForm,
    },
}

/// Which form a [`FeatureEdge::NamedFeatureWithSlash`] takes. Not part of the
/// stable API.
#[derive(Clone, Debug)]
#[doc(hidden)]
pub enum SlashForm {
    /// The feature applies to every declaration of the dependency as soon as it
    /// is enabled. There are three ways to get here:
    ///
    /// * The feature is written without the `?`, as `a = ["foo/b"]`.
    /// * It is written as `foo?/b`, but `foo` has no optional declarations for
    ///   this package, so `foo?/b` means the same as `foo/b` here.
    /// * `a` has both forms, as in `a = ["foo?/b", "foo/b"]`. Both map to the
    ///   same edge, and the non-weak form wins.
    Strong,

    /// The weak form, `a = ["foo?/b"]`, on a package that `foo` has at least
    /// one optional declaration for. For those declarations, the feature only
    /// applies once `foo` is activated.
    Weak(Box<WeakSlashImpl>),
}

/// Extra data carried by a weak [`FeatureEdge::NamedFeatureWithSlash`]
/// (`foo?/b`). Not part of the stable API.
#[derive(Clone, Debug)]
#[doc(hidden)]
pub struct WeakSlashImpl {
    /// The half covering the link's required declarations. Absent if there are
    /// no required declarations.
    pub(super) required: Option<EnabledLink>,

    /// The half covering the link's optional declarations. Always present: an
    /// edge with no optional declarations is [`SlashForm::Strong`].
    pub(super) optional: EnabledLink,

    pub(super) index: WeakIndex,
}

/// A [`ConditionalLinkImpl`] that is enabled for at least one dependency kind
/// on at least one platform. Not part of the stable API.
#[derive(Clone, Debug)]
#[doc(hidden)]
pub struct EnabledLink(ConditionalLinkImpl);

impl EnabledLink {
    pub(super) fn new(link: ConditionalLinkImpl) -> Option<Self> {
        (!link.is_never()).then_some(Self(link))
    }

    pub(super) fn get(&self) -> &ConditionalLinkImpl {
        &self.0
    }
}

/// Not part of the stable API -- only exposed for FeatureSet::links().
#[derive(Clone, Debug)]
#[doc(hidden)]
pub struct ConditionalLinkImpl {
    pub(super) package_edge_ixs: PackageEdgeIxs,
    pub(super) declarations: LinkDeclarations,
    pub(super) normal: PlatformStatusImpl,
    pub(super) build: PlatformStatusImpl,
    pub(super) dev: PlatformStatusImpl,
}

impl ConditionalLinkImpl {
    #[inline]
    fn dev_only(&self) -> bool {
        self.normal.is_never() && self.build.is_never()
    }

    #[inline]
    pub(super) fn is_never(&self) -> bool {
        self.normal.is_never() && self.build.is_never() && self.dev.is_never()
    }

    /// Unions two links for the same dependency name.
    ///
    /// A link that is never enabled contributes nothing, including its package
    /// edges, so [`ConditionalLink::package_links`] omits it.
    pub(super) fn union(mut self, other: Self) -> Self {
        debug_assert_eq!(
            self.declarations, other.declarations,
            "unioned links cover the same declarations"
        );
        if other.is_never() {
            return self;
        }
        if self.is_never() {
            return other;
        }
        for edge_ix in other.package_edge_ixs.iter() {
            debug_assert!(
                !self.package_edge_ixs.0.contains(&edge_ix),
                "unioned links have distinct package edges"
            );
        }
        self.package_edge_ixs.0.extend(other.package_edge_ixs.0);
        self.normal.extend(&other.normal);
        self.build.extend(&other.build);
        self.dev.extend(&other.dev);
        self
    }
}

/// The declarations of a dependency that a [`ConditionalLink`] was derived
/// from.
///
/// Returned by [`ConditionalLink::declarations`]. For more information, see the
/// docs for that method.
#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
pub enum LinkDeclarations {
    /// The link was not split by declaration, so it covers every declaration
    /// of the dependency.
    Unsplit,

    /// Only the declarations without `optional = true`.
    Required,

    /// Only the declarations with `optional = true`.
    Optional,
}

impl LinkDeclarations {
    /// Returns true if these declarations include the ones without
    /// `optional = true`: that is, for [`Unsplit`](Self::Unsplit) and
    /// [`Required`](Self::Required).
    ///
    /// Prefer this to simply checking equality against `Required`. A link that
    /// was not split by declaration is `Unsplit`, even if every declaration it
    /// covers is a required one. For example, with:
    ///
    /// ```toml
    /// [dependencies]
    /// foo = { version = "1" }
    ///
    /// [features]
    /// a = ["foo/std"]
    /// ```
    ///
    /// the link from `a` to `foo/std` is `Unsplit`, not `Required`.
    pub fn includes_required(self) -> bool {
        match self {
            Self::Unsplit | Self::Required => true,
            Self::Optional => false,
        }
    }

    /// Returns true if these declarations include the ones with
    /// `optional = true`: that is, for [`Unsplit`](Self::Unsplit) and
    /// [`Optional`](Self::Optional).
    ///
    /// As with [`includes_required`](Self::includes_required), prefer this to
    /// checking equality against `Optional`.
    pub fn includes_optional(self) -> bool {
        match self {
            Self::Unsplit | Self::Optional => true,
            Self::Required => false,
        }
    }
}

/// The package edges a conditional link was derived from.
///
/// This is always non-empty by construction.
#[derive(Clone, Debug)]
pub(super) struct PackageEdgeIxs(SmallVec<[EdgeIndex<PackageIx>; 4]>);

impl PackageEdgeIxs {
    pub(super) fn single(edge_ix: EdgeIndex<PackageIx>) -> Self {
        Self(iter::once(edge_ix).collect())
    }

    pub(super) fn iter(&self) -> impl ExactSizeIterator<Item = EdgeIndex<PackageIx>> + '_ {
        self.0.iter().copied()
    }
}

/// Metadata for a particular feature node.
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
pub(super) struct FeatureMetadataImpl {
    pub(super) feature_ix: NodeIndex<FeatureIx>,
}

/// The kind of a particular feature within a package.
///
/// Returned by `FeatureMetadata`.
#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub enum FeatureKind {
    /// The "base" feature. Every package has one such feature.
    Base,

    /// This is a named feature in the `[features]` section, or an implicit feature that corresponds to
    /// an optional dependency.
    ///
    /// For versions of Cargo prior to 1.60, optional dependencies always create implicit features
    /// by the same name. For versions 1.60 and greater, optional dependencies may create implicit
    /// features if the dependency doesn't exist with the name "dep" in it.
    Named,

    /// This is an optional dependency.
    OptionalDependency,
}

impl FeatureKind {
    /// Returns true if this is the base feature.
    #[inline]
    pub fn is_base(self) -> bool {
        matches!(self, Self::Base)
    }

    /// Returns true if this is a named feature.
    #[inline]
    pub fn is_named(self) -> bool {
        matches!(self, Self::Named)
    }

    /// Returns true if this is an optional dependency.
    #[inline]
    pub fn is_optional_dependency(self) -> bool {
        matches!(self, Self::OptionalDependency)
    }
}