// Copyright (c) The cargo-guppy Contributors
// SPDX-License-Identifier: MIT OR Apache-2.0
use crate::{
debug_ignore::DebugIgnore,
graph::{
feature::{FeatureFilter, FeatureSet},
resolve_core::{ResolveCore, Topo},
DependencyDirection, PackageGraph, PackageIx, PackageLink, PackageLinkImpl,
PackageMetadata, PackageQuery,
},
petgraph_support::{
dot::{DotFmt, DotVisitor, DotWrite},
edge_ref::GraphEdgeRef,
IxBitSet,
},
sorted_set::SortedSet,
Error, PackageId,
};
use camino::Utf8Path;
use fixedbitset::FixedBitSet;
use petgraph::{
prelude::*,
visit::{NodeFiltered, NodeRef},
};
use std::fmt;
impl PackageGraph {
/// Creates a new `PackageSet` consisting of all members of this package graph.
///
/// This is normally the same as `query_workspace().resolve()`, but can differ if packages have
/// been replaced with `[patch]` or `[replace]`.
///
/// In most situations, `query_workspace` is preferred. Use `resolve_all` if you know you need
/// parts of the graph that aren't accessible from the workspace.
pub fn resolve_all(&self) -> PackageSet {
PackageSet {
graph: DebugIgnore(self),
core: ResolveCore::all_nodes(&self.dep_graph),
}
}
/// Creates a new, empty `PackageSet` associated with this package graph.
pub fn resolve_none(&self) -> PackageSet {
PackageSet {
graph: DebugIgnore(self),
core: ResolveCore::empty(),
}
}
/// Creates a new `PackageSet` consisting of the specified package IDs.
///
/// This does not include transitive dependencies. To do so, use the `query_` methods.
///
/// Returns an error if any package IDs are unknown.
pub fn resolve_ids<'a>(
&self,
package_ids: impl IntoIterator<Item = &'a PackageId>,
) -> Result<PackageSet, Error> {
Ok(PackageSet {
graph: DebugIgnore(self),
core: ResolveCore::from_included::<IxBitSet>(self.package_ixs(package_ids)?),
})
}
/// Creates a new `PackageSet` consisting of all packages in this workspace.
///
/// This does not include transitive dependencies. To do so, use `query_workspace`.
pub fn resolve_workspace(&self) -> PackageSet {
let included: IxBitSet = self
.workspace()
.iter_by_path()
.map(|(_, package)| package.package_ix())
.collect();
PackageSet {
graph: DebugIgnore(self),
core: ResolveCore::from_included(included),
}
}
/// Creates a new `PackageSet` consisting of the specified workspace packages by path.
///
/// This does not include transitive dependencies. To do so, use `query_workspace_paths`.
///
/// Returns an error if any workspace paths are unknown.
pub fn resolve_workspace_paths(
&self,
paths: impl IntoIterator<Item = impl AsRef<Utf8Path>>,
) -> Result<PackageSet, Error> {
let workspace = self.workspace();
let included: IxBitSet = paths
.into_iter()
.map(|path| {
workspace
.member_by_path(path.as_ref())
.map(|package| package.package_ix())
})
.collect::<Result<_, Error>>()?;
Ok(PackageSet {
graph: DebugIgnore(self),
core: ResolveCore::from_included(included),
})
}
/// Creates a new `PackageSet` consisting of the specified workspace packages by name.
///
/// This does not include transitive dependencies. To do so, use `query_workspace_names`.
///
/// Returns an error if any workspace names are unknown.
pub fn resolve_workspace_names(
&self,
names: impl IntoIterator<Item = impl AsRef<str>>,
) -> Result<PackageSet, Error> {
let workspace = self.workspace();
let included: IxBitSet = names
.into_iter()
.map(|name| {
workspace
.member_by_name(name.as_ref())
.map(|package| package.package_ix())
})
.collect::<Result<_, _>>()?;
Ok(PackageSet {
graph: DebugIgnore(self),
core: ResolveCore::from_included(included),
})
}
/// Creates a new `PackageSet` consisting of packages with the given name.
///
/// The result is empty if there are no packages with the given name.
pub fn resolve_package_name(&self, name: impl AsRef<str>) -> PackageSet {
// Turns out that for reasonably-sized graphs, a linear search across package names is
// extremely fast: much faster than trying to do something fancy like use an FST or trie.
//
// TODO: optimize this in the future, possibly through some sort of hashmap variant that
// doesn't require a borrow.
let name = name.as_ref();
let included: IxBitSet = self
.packages()
.filter_map(|package| {
if package.name() == name {
Some(package.package_ix())
} else {
None
}
})
.collect();
PackageSet::from_included(self, included)
}
}
/// A set of resolved packages in a package graph.
///
/// Created by `PackageQuery::resolve`.
#[derive(Clone, Debug)]
pub struct PackageSet<'g> {
graph: DebugIgnore<&'g PackageGraph>,
core: ResolveCore<PackageGraph>,
}
assert_covariant!(PackageSet);
impl<'g> PackageSet<'g> {
pub(super) fn new(query: PackageQuery<'g>) -> Self {
let graph = query.graph;
Self {
graph: DebugIgnore(graph),
core: ResolveCore::new(graph.dep_graph(), query.params),
}
}
pub(super) fn from_included(graph: &'g PackageGraph, included: impl Into<FixedBitSet>) -> Self {
Self {
graph: DebugIgnore(graph),
core: ResolveCore::from_included(included),
}
}
pub(super) fn with_resolver(
query: PackageQuery<'g>,
mut resolver: impl PackageResolver<'g>,
) -> Self {
let graph = query.graph;
let params = query.params.clone();
Self {
graph: DebugIgnore(graph),
core: ResolveCore::with_edge_filter(graph.dep_graph(), params, |edge| {
let link = graph.edge_ref_to_link(edge);
resolver.accept(&query, link)
}),
}
}
/// Returns the number of packages in this set.
pub fn len(&self) -> usize {
self.core.len()
}
/// Returns true if no packages were resolved in this set.
pub fn is_empty(&self) -> bool {
self.core.is_empty()
}
/// Returns true if this package ID is contained in this resolve set.
///
/// Returns an error if the package ID is unknown.
pub fn contains(&self, package_id: &PackageId) -> Result<bool, Error> {
Ok(self.contains_ix(self.graph.package_ix(package_id)?))
}
/// Creates a new `PackageQuery` from this set in the specified direction.
///
/// This is equivalent to constructing a query from all the `package_ids`.
pub fn to_package_query(&self, direction: DependencyDirection) -> PackageQuery<'g> {
let package_ixs = SortedSet::new(
self.core
.included
.ones()
.map(NodeIndex::new)
.collect::<Vec<_>>(),
);
self.graph.query_from_parts(package_ixs, direction)
}
// ---
// Set operations
// ---
/// Returns a `PackageSet` that contains all packages present in at least one of `self`
/// and `other`.
///
/// ## Panics
///
/// Panics if the package graphs associated with `self` and `other` don't match.
pub fn union(&self, other: &Self) -> Self {
assert!(
::std::ptr::eq(self.graph.0, other.graph.0),
"package graphs passed into union() match"
);
let mut res = self.clone();
res.core.union_with(&other.core);
res
}
/// Returns a `PackageSet` that contains all packages present in both `self` and `other`.
///
/// ## Panics
///
/// Panics if the package graphs associated with `self` and `other` don't match.
pub fn intersection(&self, other: &Self) -> Self {
assert!(
::std::ptr::eq(self.graph.0, other.graph.0),
"package graphs passed into intersection() match"
);
let mut res = self.clone();
res.core.intersect_with(&other.core);
res
}
/// Returns a `PackageSet` that contains all packages present in `self` but not `other`.
///
/// ## Panics
///
/// Panics if the package graphs associated with `self` and `other` don't match.
pub fn difference(&self, other: &Self) -> Self {
assert!(
::std::ptr::eq(self.graph.0, other.graph.0),
"package graphs passed into difference() match"
);
Self {
graph: self.graph,
core: self.core.difference(&other.core),
}
}
/// Returns a `PackageSet` that contains all packages present in exactly one of `self` and
/// `other`.
///
/// ## Panics
///
/// Panics if the package graphs associated with `self` and `other` don't match.
pub fn symmetric_difference(&self, other: &Self) -> Self {
assert!(
::std::ptr::eq(self.graph.0, other.graph.0),
"package graphs passed into symmetric_difference() match"
);
let mut res = self.clone();
res.core.symmetric_difference_with(&other.core);
res
}
/// Returns a `PackageSet` on which a filter has been applied.
///
/// Filters out all values for which the callback returns false.
///
/// ## Cycles
///
/// For packages within a dependency cycle, the callback will be called in non-dev order. When
/// the direction is forward, if package Foo has a dependency on Bar, and Bar has a cyclic
/// dev-dependency on Foo, then Foo is returned before Bar.
pub fn filter(
&self,
direction: DependencyDirection,
mut callback: impl FnMut(PackageMetadata<'g>) -> bool,
) -> Self {
let graph = *self.graph;
let included: IxBitSet = self
.packages(direction)
.filter_map(move |package| {
let package_ix = package.package_ix();
if callback(package) {
Some(package_ix)
} else {
None
}
})
.collect();
Self::from_included(graph, included)
}
/// Partitions this `PackageSet` into two.
///
/// The first `PackageSet` contains packages for which the callback returned true, and the
/// second one contains packages for which the callback returned false.
///
/// ## Cycles
///
/// For packages within a dependency cycle, the callback will be called in non-dev order. When
/// the direction is forward, if package Foo has a dependency on Bar, and Bar has a cyclic
/// dev-dependency on Foo, then Foo is returned before Bar.
pub fn partition(
&self,
direction: DependencyDirection,
mut callback: impl FnMut(PackageMetadata<'g>) -> bool,
) -> (Self, Self) {
let graph = *self.graph;
let mut left = IxBitSet::with_capacity(self.core.included.len());
let mut right = left.clone();
self.packages(direction).for_each(|package| {
let package_ix = package.package_ix();
match callback(package) {
true => left.insert_node_ix(package_ix),
false => right.insert_node_ix(package_ix),
}
});
(
Self::from_included(graph, left),
Self::from_included(graph, right),
)
}
/// Performs filtering and partitioning at the same time.
///
/// The first `PackageSet` contains packages for which the callback returned `Some(true)`, and
/// the second one contains packages for which the callback returned `Some(false)`. Packages
/// for which the callback returned `None` are dropped.
///
/// ## Cycles
///
/// For packages within a dependency cycle, the callback will be called in non-dev order. When
/// the direction is forward, if package Foo has a dependency on Bar, and Bar has a cyclic
/// dev-dependency on Foo, then Foo is returned before Bar.
pub fn filter_partition(
&self,
direction: DependencyDirection,
mut callback: impl FnMut(PackageMetadata<'g>) -> Option<bool>,
) -> (Self, Self) {
let graph = *self.graph;
let mut left = IxBitSet::with_capacity(self.core.included.len());
let mut right = left.clone();
self.packages(direction).for_each(|package| {
let package_ix = package.package_ix();
match callback(package) {
Some(true) => left.insert_node_ix(package_ix),
Some(false) => right.insert_node_ix(package_ix),
None => {}
}
});
(
Self::from_included(graph, left),
Self::from_included(graph, right),
)
}
// ---
// Conversion to FeatureSet
// ---
/// Creates a new `FeatureSet` consisting of all packages in this `PackageSet`, using the given
/// feature filter.
///
/// This will cause the feature graph to be constructed if it hasn't been done so already.
pub fn to_feature_set(&self, filter: impl FeatureFilter<'g>) -> FeatureSet<'g> {
let feature_graph = self.graph.feature_graph();
let included: IxBitSet = feature_graph.feature_ixs_for_package_ixs_filtered(
// The direction of iteration doesn't matter.
self.ixs(DependencyDirection::Forward),
filter,
);
FeatureSet::from_included(feature_graph, included)
}
// ---
// Iterators
// ---
/// Iterates over package IDs, in topological order in the direction specified.
///
/// ## Cycles
///
/// The packages within a dependency cycle will be returned in non-dev order. When the direction
/// is forward, if package Foo has a dependency on Bar, and Bar has a cyclic dev-dependency on
/// Foo, then Foo is returned before Bar.
pub fn package_ids<'a>(
&'a self,
direction: DependencyDirection,
) -> impl Iterator<Item = &'g PackageId> + ExactSizeIterator + 'a {
let graph = self.graph;
self.core
.topo(self.graph.sccs(), direction)
.map(move |package_ix| &graph.dep_graph[package_ix])
}
pub(super) fn ixs(&'g self, direction: DependencyDirection) -> Topo<'g, PackageGraph> {
self.core.topo(self.graph.sccs(), direction)
}
/// Iterates over package metadatas, in topological order in the direction specified.
///
/// ## Cycles
///
/// The packages within a dependency cycle will be returned in non-dev order. When the direction
/// is forward, if package Foo has a dependency on Bar, and Bar has a cyclic dev-dependency on
/// Foo, then Foo is returned before Bar.
pub fn packages<'a>(
&'a self,
direction: DependencyDirection,
) -> impl Iterator<Item = PackageMetadata<'g>> + ExactSizeIterator + 'a {
let graph = self.graph;
self.package_ids(direction)
.map(move |package_id| graph.metadata(package_id).expect("known package IDs"))
}
/// Returns the set of "root package" IDs in the specified direction.
///
/// * If direction is Forward, return the set of packages that do not have any dependencies
/// within the selected graph.
/// * If direction is Reverse, return the set of packages that do not have any dependents within
/// the selected graph.
///
/// ## Cycles
///
/// If a root consists of a dependency cycle, all the packages in it will be returned in
/// non-dev order (when the direction is forward).
pub fn root_ids<'a>(
&'a self,
direction: DependencyDirection,
) -> impl Iterator<Item = &'g PackageId> + ExactSizeIterator + 'a {
let dep_graph = &self.graph.dep_graph;
self.core
.roots(self.graph.dep_graph(), self.graph.sccs(), direction)
.into_iter()
.map(move |package_ix| &dep_graph[package_ix])
}
/// Returns the set of "root package" metadatas in the specified direction.
///
/// * If direction is Forward, return the set of packages that do not have any dependencies
/// within the selected graph.
/// * If direction is Reverse, return the set of packages that do not have any dependents within
/// the selected graph.
///
/// ## Cycles
///
/// If a root consists of a dependency cycle, all the packages in it will be returned in
/// non-dev order (when the direction is forward).
pub fn root_packages<'a>(
&'a self,
direction: DependencyDirection,
) -> impl Iterator<Item = PackageMetadata<'g>> + ExactSizeIterator + 'a {
let package_graph = self.graph;
self.core
.roots(self.graph.dep_graph(), self.graph.sccs(), direction)
.into_iter()
.map(move |package_ix| {
package_graph
.metadata(&package_graph.dep_graph[package_ix])
.expect("invalid node index")
})
}
/// Creates an iterator over `PackageLink` instances.
///
/// If the iteration is in forward order, for any given package, at least one link where the
/// package is on the `to` end is returned before any links where the package is on the
/// `from` end.
///
/// If the iteration is in reverse order, for any given package, at least one link where the
/// package is on the `from` end is returned before any links where the package is on the `to`
/// end.
///
/// ## Cycles
///
/// The links in a dependency cycle will be returned in non-dev order. When the direction is
/// forward, if package Foo has a dependency on Bar, and Bar has a cyclic dev-dependency on Foo,
/// then the link Foo -> Bar is returned before the link Bar -> Foo.
pub fn links<'a>(
&'a self,
direction: DependencyDirection,
) -> impl Iterator<Item = PackageLink<'g>> + 'a {
let graph = self.graph.0;
self.core
.links(graph.dep_graph(), graph.sccs(), direction)
.map(move |(source_ix, target_ix, edge_ix)| {
PackageLink::new(graph, source_ix, target_ix, edge_ix, None)
})
}
/// Constructs a representation of the selected packages in `dot` format.
pub fn display_dot<'a, V: PackageDotVisitor + 'g>(
&'a self,
visitor: V,
) -> impl fmt::Display + 'a {
let node_filtered = NodeFiltered(self.graph.dep_graph(), &self.core.included);
DotFmt::new(node_filtered, VisitorWrap::new(self.graph.0, visitor))
}
// ---
// Helper methods
// ---
/// Returns all the package ixs without topologically sorting them.
#[allow(dead_code)]
pub(super) fn ixs_unordered(&self) -> impl Iterator<Item = NodeIndex<PackageIx>> + '_ {
self.core.included.ones().map(NodeIndex::new)
}
pub(super) fn contains_ix(&self, package_ix: NodeIndex<PackageIx>) -> bool {
self.core.contains(package_ix)
}
}
impl<'g> PartialEq for PackageSet<'g> {
fn eq(&self, other: &Self) -> bool {
::std::ptr::eq(self.graph.0, other.graph.0) && self.core == other.core
}
}
impl<'g> Eq for PackageSet<'g> {}
/// Represents whether a particular link within a package graph should be followed during a
/// resolve operation.
pub trait PackageResolver<'g> {
/// Returns true if this link should be followed during a resolve operation.
///
/// Returning false does not prevent the `to` package (or `from` package with `query_reverse`)
/// from being included if it's reachable through other means.
fn accept(&mut self, query: &PackageQuery<'g>, link: PackageLink<'g>) -> bool;
}
impl<'g, 'a, T> PackageResolver<'g> for &'a mut T
where
T: PackageResolver<'g>,
{
fn accept(&mut self, query: &PackageQuery<'g>, link: PackageLink<'g>) -> bool {
(**self).accept(query, link)
}
}
impl<'g, 'a> PackageResolver<'g> for Box<dyn PackageResolver<'g> + 'a> {
fn accept(&mut self, query: &PackageQuery<'g>, link: PackageLink<'g>) -> bool {
(**self).accept(query, link)
}
}
impl<'g, 'a> PackageResolver<'g> for &'a mut dyn PackageResolver<'g> {
fn accept(&mut self, query: &PackageQuery<'g>, link: PackageLink<'g>) -> bool {
(**self).accept(query, link)
}
}
pub(super) struct ResolverFn<F>(pub(super) F);
impl<'g, F> PackageResolver<'g> for ResolverFn<F>
where
F: FnMut(&PackageQuery<'g>, PackageLink<'g>) -> bool,
{
fn accept(&mut self, query: &PackageQuery<'g>, link: PackageLink<'g>) -> bool {
(self.0)(query, link)
}
}
/// A visitor used for formatting `dot` graphs.
pub trait PackageDotVisitor {
/// Visits this package. The implementation may output a label for this package to the given
/// `DotWrite`.
fn visit_package(&self, package: PackageMetadata<'_>, f: &mut DotWrite<'_, '_>) -> fmt::Result;
/// Visits this dependency link. The implementation may output a label for this link to the
/// given `DotWrite`.
fn visit_link(&self, link: PackageLink<'_>, f: &mut DotWrite<'_, '_>) -> fmt::Result;
}
struct VisitorWrap<'g, V> {
graph: &'g PackageGraph,
inner: V,
}
impl<'g, V> VisitorWrap<'g, V> {
fn new(graph: &'g PackageGraph, inner: V) -> Self {
Self { graph, inner }
}
}
impl<'g, V, NR, ER> DotVisitor<NR, ER> for VisitorWrap<'g, V>
where
V: PackageDotVisitor,
NR: NodeRef<NodeId = NodeIndex<PackageIx>, Weight = PackageId>,
ER: GraphEdgeRef<'g, PackageLinkImpl, PackageIx>,
{
fn visit_node(&self, node: NR, f: &mut DotWrite<'_, '_>) -> fmt::Result {
let metadata = self
.graph
.metadata(node.weight())
.expect("visited node should have associated metadata");
self.inner.visit_package(metadata, f)
}
fn visit_edge(&self, edge: ER, f: &mut DotWrite<'_, '_>) -> fmt::Result {
let link = self.graph.edge_ref_to_link(edge.into_edge_reference());
self.inner.visit_link(link, f)
}
}