use crate::{
debug_ignore::DebugIgnore,
errors::FeatureGraphWarning,
graph::{
feature::{
build::{FeatureGraphBuildState, FeaturePetgraph},
Cycles, FeatureFilter, FeatureList, WeakDependencies, WeakIndex,
},
DependencyDirection, FeatureIndexInPackage, FeatureIx, PackageGraph, PackageIx,
PackageLink, PackageMetadata,
},
petgraph_support::{scc::Sccs, topo::TopoWithCycles},
platform::{PlatformStatus, PlatformStatusImpl},
DependencyKind, Error, PackageId,
};
use once_cell::sync::OnceCell;
use petgraph::{
algo::has_path_connecting,
prelude::*,
visit::{EdgeFiltered, IntoNodeReferences},
};
use std::{collections::HashMap, fmt, iter, iter::FromIterator};
impl PackageGraph {
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))
}
}
#[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> {
pub fn build_warnings(&self) -> &'g [FeatureGraphWarning] {
&self.inner.warnings
}
pub fn package_graph(&self) -> &'g PackageGraph {
self.package_graph
}
pub fn feature_count(&self) -> usize {
self.dep_graph().node_count()
}
pub fn link_count(&self) -> usize {
self.dep_graph().edge_count()
}
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()
}
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))
}
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))
}
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)?;
Ok(self.feature_ix_depends_on_no_conditional(default_ix, feature_ix))
}
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))
}
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))
}
pub fn cycles(&self) -> Cycles<'g> {
Cycles::new(*self)
}
#[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(())
}
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,
});
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
}
pub(super) fn edge_to_conditional_link(
&self,
source_ix: NodeIndex<FeatureIx>,
target_ix: NodeIndex<FeatureIx>,
edge_ix: EdgeIndex<FeatureIx>,
edge: Option<&'g FeatureEdge>,
) -> Option<(ConditionalLink<'g>, Option<WeakIndex>)> {
let edge = edge.unwrap_or_else(|| &self.dep_graph()[edge_ix]);
match edge {
FeatureEdge::NamedFeature | FeatureEdge::FeatureToBase => None,
FeatureEdge::DependenciesSection(link) | FeatureEdge::NamedFeatureDepColon(link) => {
let link = ConditionalLink::new(*self, source_ix, target_ix, edge_ix, link);
let weak_index = None;
Some((link, weak_index))
}
FeatureEdge::NamedFeatureWithSlash { link, weak_index } => {
let link = ConditionalLink::new(*self, source_ix, target_ix, edge_ix, link);
Some((link, *weak_index))
}
}
}
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 {
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>> {
let package_ix = package_ix.index();
let base_ix = self.inner.base_ixs[package_ix].index();
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(
&self,
package_ixs: impl IntoIterator<Item = NodeIndex<PackageIx>> + 'g,
) -> impl Iterator<Item = NodeIndex<FeatureIx>> + 'g {
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)
}
}
#[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> {
pub fn new(package_id: &'g PackageId, label: FeatureLabel<'g>) -> Self {
Self { package_id, label }
}
pub fn named(package_id: &'g PackageId, feature_name: &'g str) -> Self {
Self {
package_id,
label: FeatureLabel::Named(feature_name),
}
}
pub fn optional_dependency(package_id: &'g PackageId, dep_name: &'g str) -> Self {
Self {
package_id,
label: FeatureLabel::OptionalDependency(dep_name),
}
}
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)
}
pub fn package_id(&self) -> &'g PackageId {
self.package_id
}
pub fn label(&self) -> FeatureLabel<'g> {
self.label
}
#[inline]
pub fn is_base(&self) -> bool {
self.label.kind().is_base()
}
#[inline]
pub fn is_optional_dependency(self) -> bool {
self.label.kind().is_optional_dependency()
}
#[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 }
}
}
impl<'g> fmt::Display for FeatureId<'g> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}/{}", self.package_id, self.label)
}
}
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub enum FeatureLabel<'g> {
Base,
Named(&'g str),
OptionalDependency(&'g str),
}
impl<'g> FeatureLabel<'g> {
#[inline]
pub fn kind(self) -> FeatureKind {
match self {
Self::Base => FeatureKind::Base,
Self::Named(_) => FeatureKind::Named,
Self::OptionalDependency(_) => FeatureKind::OptionalDependency,
}
}
}
impl<'g> fmt::Display for FeatureLabel<'g> {
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),
}
}
}
#[derive(Clone, Copy, Debug)]
pub struct FeatureMetadata<'g> {
graph: DebugIgnore<FeatureGraph<'g>>,
node: FeatureNode,
inner: &'g FeatureMetadataImpl,
}
assert_covariant!(FeatureMetadata);
impl<'g> FeatureMetadata<'g> {
pub fn feature_id(&self) -> FeatureId<'g> {
FeatureId::from_node(self.graph.package_graph, &self.node)
}
pub fn package_id(&self) -> &'g PackageId {
&self.graph.package_graph.dep_graph[self.package_ix()]
}
pub fn package(&self) -> PackageMetadata<'g> {
self.graph
.package_graph
.metadata(self.package_id())
.expect("valid package ID")
}
pub fn label(&self) -> FeatureLabel<'g> {
self.feature_id().label()
}
#[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
}
}
#[derive(Clone, Debug)]
pub(in crate::graph) struct FeatureGraphImpl {
pub(super) graph: FeaturePetgraph,
pub(super) base_ixs: Vec<NodeIndex<FeatureIx>>,
pub(super) map: HashMap<FeatureNode, FeatureMetadataImpl>,
pub(super) warnings: Vec<FeatureGraphWarning>,
pub(super) sccs: OnceCell<Sccs<FeatureIx>>,
pub(super) weak: WeakDependencies,
}
impl FeatureGraphImpl {
pub(super) fn new(package_graph: &PackageGraph) -> Self {
let mut build_state = FeatureGraphBuildState::new(package_graph);
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();
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()
}
}
#[derive(Copy, Clone, Debug)]
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,
}
}
pub fn from(&self) -> FeatureMetadata<'g> {
FeatureMetadata {
graph: DebugIgnore(self.graph.0),
node: self.graph.dep_graph()[self.from.feature_ix],
inner: self.from,
}
}
pub fn to(&self) -> FeatureMetadata<'g> {
FeatureMetadata {
graph: DebugIgnore(self.graph.0),
node: self.graph.dep_graph()[self.to.feature_ix],
inner: self.to,
}
}
pub fn endpoints(&self) -> (FeatureMetadata<'g>, FeatureMetadata<'g>) {
(self.from(), self.to())
}
pub fn normal(&self) -> PlatformStatus<'g> {
PlatformStatus::new(&self.inner.normal)
}
pub fn build(&self) -> PlatformStatus<'g> {
PlatformStatus::new(&self.inner.build)
}
pub fn dev(&self) -> PlatformStatus<'g> {
PlatformStatus::new(&self.inner.dev)
}
pub fn status_for_kind(&self, kind: DependencyKind) -> PlatformStatus<'g> {
match kind {
DependencyKind::Normal => self.normal(),
DependencyKind::Build => self.build(),
DependencyKind::Development => self.dev(),
}
}
pub fn dev_only(&self) -> bool {
self.inner.dev_only()
}
pub fn package_link(&self) -> PackageLink<'g> {
self.graph
.package_graph
.edge_ix_to_link(self.inner.package_edge_ix)
}
#[allow(dead_code)]
pub(super) fn edge_ix(&self) -> EdgeIndex<FeatureIx> {
self.edge_ix
}
#[allow(dead_code)]
pub(in crate::graph) fn package_edge_ix(&self) -> EdgeIndex<PackageIx> {
self.inner.package_edge_ix
}
}
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub(in crate::graph) struct FeatureNode {
package_ix: NodeIndex<PackageIx>,
feature_idx: FeatureIndexInPackage,
}
impl FeatureNode {
pub(in crate::graph) fn new(
package_ix: NodeIndex<PackageIx>,
feature_idx: FeatureIndexInPackage,
) -> Self {
Self {
package_ix,
feature_idx,
}
}
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
}
}
#[derive(Clone, Debug)]
#[doc(hidden)]
pub enum FeatureEdge {
FeatureToBase,
DependenciesSection(ConditionalLinkImpl),
NamedFeature,
NamedFeatureDepColon(ConditionalLinkImpl),
NamedFeatureWithSlash {
link: ConditionalLinkImpl,
weak_index: Option<WeakIndex>,
},
}
#[derive(Clone, Debug)]
#[doc(hidden)]
pub struct ConditionalLinkImpl {
pub(super) package_edge_ix: EdgeIndex<PackageIx>,
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()
}
}
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
pub(super) struct FeatureMetadataImpl {
pub(super) feature_ix: NodeIndex<FeatureIx>,
}
#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub enum FeatureKind {
Base,
Named,
OptionalDependency,
}
impl FeatureKind {
#[inline]
pub fn is_base(self) -> bool {
matches!(self, Self::Base)
}
#[inline]
pub fn is_named(self) -> bool {
matches!(self, Self::Named)
}
#[inline]
pub fn is_optional_dependency(self) -> bool {
matches!(self, Self::OptionalDependency)
}
}