use crate::{
errors::FeatureGraphWarning,
graph::{
feature::{build::FeatureGraphBuildState, Cycles, FeatureFilter, FeatureList},
DependencyDirection, FeatureIx, PackageGraph, PackageIx, PackageLink, PackageMetadata,
PlatformStatus, PlatformStatusImpl,
},
petgraph_support::{scc::Sccs, topo::TopoWithCycles},
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 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_cross(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 cross_link in feature_set.cross_links(DependencyDirection::Forward) {
let (from, to) = cross_link.endpoints();
let is_any = cross_link.normal().is_present()
|| cross_link.build().is_present()
|| cross_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::CrossPackage(cross_link) => !cross_link.dev_only(),
FeatureEdge::FeatureDependency | 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: *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 Graph<FeatureNode, FeatureEdge, Directed, FeatureIx> {
&self.inner.graph
}
pub(super) fn edge_to_cross_link(
&self,
source_ix: NodeIndex<FeatureIx>,
target_ix: NodeIndex<FeatureIx>,
edge_ix: EdgeIndex<FeatureIx>,
edge: Option<&'g FeatureEdge>,
) -> Option<CrossLink<'g>> {
match edge.unwrap_or_else(|| &self.dep_graph()[edge_ix]) {
FeatureEdge::FeatureDependency | FeatureEdge::FeatureToBase => None,
FeatureEdge::CrossPackage(inner) => {
Some(CrossLink::new(*self, source_ix, target_ix, edge_ix, &inner))
}
}
}
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_cross(
&self,
a_ix: NodeIndex<FeatureIx>,
b_ix: NodeIndex<FeatureIx>,
) -> bool {
let edge_filtered = EdgeFiltered::from_fn(self.dep_graph(), |edge_ref| {
!matches!(edge_ref.weight(), FeatureEdge::CrossPackage(_))
});
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,
feature: Option<&'g str>,
}
assert_covariant!(FeatureId);
impl<'g> FeatureId<'g> {
pub fn new(package_id: &'g PackageId, feature: &'g str) -> Self {
Self {
package_id,
feature: Some(feature),
}
}
pub fn base(package_id: &'g PackageId) -> Self {
Self {
package_id,
feature: None,
}
}
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,
feature,
}
}
pub(super) fn node_to_feature(
metadata: PackageMetadata<'g>,
node: &FeatureNode,
) -> Option<&'g str> {
Some(metadata.feature_idx_to_name(node.feature_idx?))
}
pub fn package_id(&self) -> &'g PackageId {
self.package_id
}
pub fn feature(&self) -> Option<&'g str> {
self.feature
}
pub fn is_base(&self) -> bool {
self.feature.is_none()
}
}
impl<'g> From<(&'g PackageId, &'g str)> for FeatureId<'g> {
fn from((package_id, feature): (&'g PackageId, &'g str)) -> Self {
FeatureId::new(package_id, feature)
}
}
impl<'g> From<(&'g PackageId, Option<&'g str>)> for FeatureId<'g> {
fn from((package_id, feature): (&'g PackageId, Option<&'g str>)) -> Self {
FeatureId {
package_id,
feature,
}
}
}
impl<'g> From<FeatureId<'g>> for (PackageId, Option<String>) {
fn from(feature_id: FeatureId<'g>) -> Self {
(
feature_id.package_id().clone(),
feature_id.feature().map(|feature| feature.to_string()),
)
}
}
impl<'g> fmt::Display for FeatureId<'g> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let feature_name = self.feature.unwrap_or("[base]");
write!(f, "{}/{}", self.package_id, feature_name)
}
}
#[derive(Clone, Copy, Debug)]
pub struct FeatureMetadata<'g> {
graph: 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 feature_type(&self) -> FeatureType {
self.inner.feature_type
}
#[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: Graph<FeatureNode, FeatureEdge, Directed, FeatureIx>,
pub(super) base_ixs: Vec<NodeIndex<FeatureIx>>,
pub(super) map: HashMap<FeatureNode, FeatureMetadataImpl>,
pub(super) warnings: Vec<FeatureGraphWarning>,
pub(super) sccs: OnceCell<Sccs<FeatureIx>>,
}
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 CrossLink<'g> {
graph: FeatureGraph<'g>,
from: &'g FeatureMetadataImpl,
to: &'g FeatureMetadataImpl,
edge_ix: EdgeIndex<FeatureIx>,
inner: &'g CrossLinkImpl,
}
assert_covariant!(CrossLink);
impl<'g> CrossLink<'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 CrossLinkImpl,
) -> Self {
let dep_graph = graph.dep_graph();
Self {
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: self.graph,
node: self.graph.dep_graph()[self.from.feature_ix],
inner: self.from,
}
}
pub fn to(&self) -> FeatureMetadata<'g> {
FeatureMetadata {
graph: self.graph,
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(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: Option<usize>,
}
impl FeatureNode {
pub(in crate::graph) fn new(package_ix: NodeIndex<PackageIx>, feature_idx: usize) -> Self {
Self {
package_ix,
feature_idx: Some(feature_idx),
}
}
pub(in crate::graph) fn base(package_ix: NodeIndex<PackageIx>) -> Self {
Self {
package_ix,
feature_idx: None,
}
}
pub(in crate::graph) fn new_opt(
package_ix: NodeIndex<PackageIx>,
feature_idx: Option<usize>,
) -> Self {
Self {
package_ix,
feature_idx,
}
}
fn from_id(feature_graph: &FeatureGraph<'_>, id: FeatureId<'_>) -> Option<Self> {
let metadata = feature_graph.package_graph.metadata(id.package_id()).ok()?;
match id.feature() {
Some(feature_name) => Some(FeatureNode::new(
metadata.package_ix(),
metadata.get_feature_idx(feature_name)?,
)),
None => Some(FeatureNode::base(metadata.package_ix())),
}
}
pub(super) fn named_features(package: PackageMetadata<'_>) -> impl Iterator<Item = Self> + '_ {
let package_ix = package.package_ix();
package.named_features_full().map(move |(n, _, _)| Self {
package_ix,
feature_idx: Some(n),
})
}
pub(in crate::graph) fn package_ix(&self) -> NodeIndex<PackageIx> {
self.package_ix
}
}
#[derive(Clone, Debug)]
#[doc(hidden)]
pub enum FeatureEdge {
FeatureToBase,
CrossPackage(CrossLinkImpl),
FeatureDependency,
}
#[derive(Clone, Debug)]
#[doc(hidden)]
pub struct CrossLinkImpl {
pub(super) package_edge_ix: EdgeIndex<PackageIx>,
pub(super) normal: PlatformStatusImpl,
pub(super) build: PlatformStatusImpl,
pub(super) dev: PlatformStatusImpl,
}
impl CrossLinkImpl {
#[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>,
pub(super) feature_type: FeatureType,
}
#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub enum FeatureType {
NamedFeature,
OptionalDep,
BasePackage,
}