blob: 0e1d97f4b38f0be232596c7604cfa20d773afab2 [file] [log] [blame]
//! Transforms the output of [`cargo metadata`] into a graph, [`Krates`], where
//! crates are nodes and dependency links are edges.
//!
//! ```no_run
//! use krates::{Builder, Cmd, Krates, cm, petgraph};
//!
//! fn main() -> Result<(), krates::Error> {
//! let mut cmd = Cmd::new();
//! cmd.manifest_path("path/to/a/Cargo.toml");
//! // Enable all features, works for either an entire workspace or a single crate
//! cmd.all_features();
//!
//! let mut builder = Builder::new();
//! // Let's filter out any crates that aren't used by x86_64 windows
//! builder.include_targets(std::iter::once(("x86_64-pc-windows-msvc", vec![])));
//!
//! let krates: Krates = builder.build(cmd, |pkg: cm::Package| {
//! println!("Crate {} was filtered out", pkg.id);
//! })?;
//!
//! // Print a dot graph of the entire crate graph
//! println!("{:?}", petgraph::dot::Dot::new(krates.graph()));
//!
//! Ok(())
//! }
//! ```
pub use cargo_metadata as cm;
pub use cfg_expr;
#[cfg(feature = "targets")]
pub use cfg_expr::target_lexicon;
use cm::DependencyKind as DK;
pub use petgraph;
pub use semver;
pub use cm::camino::{self, Utf8Path, Utf8PathBuf};
use petgraph::{graph::EdgeIndex, graph::NodeIndex, visit::EdgeRef, Direction};
mod builder;
mod errors;
mod pkgspec;
pub use builder::{
features::{Feature, ParsedFeature},
index, Builder, Cmd, LockOptions, NoneFilter, OnFilter, Scope, Target,
};
pub use errors::Error;
pub use pkgspec::PkgSpec;
use std::fmt;
/// A crate's unique identifier
#[derive(Clone, Default)]
pub struct Kid {
/// The full package id string as supplied by cargo
pub repr: String,
/// The subslices for each component in name -> version -> source order
components: [(usize, usize); 3],
}
impl Kid {
/// Gets the name of the package
#[inline]
pub fn name(&self) -> &str {
let (s, e) = self.components[0];
&self.repr[s..e]
}
/// Gets the semver of the package
#[inline]
pub fn version(&self) -> &str {
let (s, e) = self.components[1];
&self.repr[s..e]
}
/// Gets the source url of the package
#[inline]
pub fn source(&self) -> &str {
let (s, e) = self.components[2];
&self.repr[s..e]
}
}
#[allow(clippy::fallible_impl_from)]
impl From<cargo_metadata::PackageId> for Kid {
fn from(pid: cargo_metadata::PackageId) -> Self {
let repr = pid.repr;
let gen = || {
let components = if repr.contains(' ') {
let name = (0, repr.find(' ')?);
let version = (name.1 + 1, repr[name.1 + 1..].find(' ')? + name.1 + 1);
// Note we skip the open and close parentheses as they are superfluous
// as every source has them, as well as not being present in the new
// stabilized format
//
// Note that we also chop off the commit id, it is not present in
// the stabilized format and is not used for package identification anyways
let source = (version.1 + 2, repr.rfind('#').unwrap_or(repr.len() - 1));
[name, version, source]
} else {
let vmn = repr.rfind('#')?;
let (name, version) = if let Some(split) = repr[vmn..].find('@') {
((vmn + 1, vmn + split), (vmn + split + 1, repr.len()))
} else {
let begin = repr.rfind('/')? + 1;
let end = if repr.starts_with("git+") {
repr[begin..].find('?').map_or(vmn, |q| q + begin)
} else {
vmn
};
((begin, end), (vmn + 1, repr.len()))
};
[name, version, (0, vmn)]
};
Some(components)
};
if let Some(components) = gen() {
Self { repr, components }
} else {
panic!("unable to parse package id '{repr}'");
}
}
}
impl fmt::Debug for Kid {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let mut ds = f.debug_struct("Kid");
ds.field("name", &self.name())
.field("version", &self.version());
let src = self.source();
if src != "registry+https://github.com/rust-lang/crates.io-index" {
ds.field("source", &src);
}
ds.finish()
}
}
impl fmt::Display for Kid {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(&self.repr)
}
}
impl std::hash::Hash for Kid {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
state.write(self.repr.as_bytes());
}
}
impl Ord for Kid {
fn cmp(&self, o: &Self) -> std::cmp::Ordering {
let a = &self.repr;
let b = &o.repr;
for (ar, br) in self.components.into_iter().zip(o.components.into_iter()) {
let ord = a[ar.0..ar.1].cmp(&b[br.0..br.1]);
if ord != std::cmp::Ordering::Equal {
return ord;
}
}
std::cmp::Ordering::Equal
}
}
impl PartialOrd for Kid {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl Eq for Kid {}
impl PartialEq for Kid {
fn eq(&self, other: &Self) -> bool {
self.cmp(other) == std::cmp::Ordering::Equal
}
}
/// The set of features that have been enabled on a crate
pub type EnabledFeatures = std::collections::BTreeSet<String>;
/// The dependency kind. A crate can depend on the same crate multiple times
/// with different dependency kinds
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub enum DepKind {
Normal,
Build,
Dev,
}
impl From<DK> for DepKind {
fn from(dk: DK) -> Self {
match dk {
DK::Normal => Self::Normal,
DK::Build => Self::Build,
DK::Development => Self::Dev,
DK::Unknown => unreachable!(),
}
}
}
impl PartialEq<DK> for DepKind {
fn eq(&self, other: &DK) -> bool {
matches!(
(self, *other),
(Self::Normal, DK::Normal) | (Self::Build, DK::Build) | (Self::Dev, DK::Development)
)
}
}
impl fmt::Display for DepKind {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Normal => Ok(()),
Self::Build => f.write_str("build"),
Self::Dev => f.write_str("dev"),
}
}
}
/// A node identifier.
pub type NodeId = NodeIndex<u32>;
pub type EdgeId = EdgeIndex<u32>;
/// A node in the crate graph.
pub enum Node<N> {
Krate {
/// The unique identifier for this node.
id: Kid,
/// Associated user data with the node. Must be From<cargo_metadata::Package>
krate: N,
/// List of features enabled on the crate
features: EnabledFeatures,
},
Feature {
/// The node index for the crate this feature is for
krate_index: NodeId,
name: String,
},
}
impl<N> fmt::Display for Node<N>
where
N: fmt::Display,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Krate { krate, .. } => {
write!(f, "crate {krate}")
}
Self::Feature { name, .. } => {
write!(f, "feature {name}")
}
}
}
}
impl<N> fmt::Debug for Node<N>
where
N: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Krate { id, krate, .. } => {
write!(f, "crate {} {krate:?}", id.repr)
}
Self::Feature { name, .. } => {
write!(f, "feature {name}")
}
}
}
}
/// The default type used for edges in the crate graph.
#[derive(Debug, Clone)]
pub enum Edge {
Dep {
/// The dependency kind for the edge link
kind: DepKind,
/// A possible cfg() or <target-triple> applied to this dependency
cfg: Option<String>,
},
/// An edge from one feature to another
Feature,
DepFeature {
/// The dependency kind for the edge link
kind: DepKind,
/// A possible cfg() or <target-triple> applied to this dependency
cfg: Option<String>,
},
}
impl fmt::Display for Edge {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
if let Self::DepFeature { kind, cfg } | Self::Dep { kind, cfg } = self {
match kind {
DepKind::Normal => {}
DepKind::Build => f.write_str("(build)")?,
DepKind::Dev => f.write_str("(dev)")?,
};
if let Some(cfg) = cfg {
write!(f, " '{cfg}'")?;
}
}
Ok(())
}
}
/// A crate graph. Each unique crate is a node, and each unique dependency
/// between 2 crates is an edge.
pub struct Krates<N = cm::Package, E = Edge> {
graph: petgraph::Graph<Node<N>, E, petgraph::Directed, u32>,
workspace_members: Vec<Kid>,
workspace_root: Utf8PathBuf,
/// We split the graph between crate and feature nodes, but keep the crates
/// grouped together in the front since most queries are against them
krates_end: usize,
}
#[allow(clippy::len_without_is_empty)]
impl<N, E> Krates<N, E> {
/// The number of unique crates in the graph
#[inline]
pub fn len(&self) -> usize {
self.krates_end
}
/// Path to the root of the workspace where the graph metadata was acquired from
#[inline]
pub fn workspace_root(&self) -> &Utf8Path {
&self.workspace_root
}
/// Get access to the raw petgraph
#[inline]
pub fn graph(&self) -> &petgraph::Graph<Node<N>, E> {
&self.graph
}
/// Get an iterator over the crate nodes in the graph. The crates are always
/// ordered lexicographically by their identfier.
///
/// ```no_run
/// use krates::Krates;
///
/// fn print_krates(krates: &Krates) {
/// for (name, version) in krates.krates().map(|krate| (&krate.name, &krate.version)) {
/// println!("Crate {} @ {}", name, version);
/// }
/// }
/// ```
#[inline]
pub fn krates(&self) -> impl Iterator<Item = &N> {
self.graph.raw_nodes()[..self.krates_end]
.iter()
.filter_map(move |node| {
if let Node::Krate { krate, .. } = &node.weight {
Some(krate)
} else {
None
}
})
}
/// Get an iterator over each dependency of the specified crate. The same
/// dependency can be returned multiple times if the crate depends on it
/// with more than 1 dependency kind.
///
/// ```no_run
/// use krates::{Krates, Kid, DepKind};
///
/// fn count_build_deps(krates: &Krates, pkg: &Kid) -> usize {
/// krates.get_deps(krates.nid_for_kid(pkg).unwrap())
/// .filter(|(_, edge)| matches!(
/// edge,
/// krates::Edge::Dep { kind: DepKind::Build, .. } |
/// krates::Edge::DepFeature { kind: DepKind::Build, .. }
/// ))
/// .count()
/// }
/// ```
#[inline]
pub fn get_deps(&self, id: NodeId) -> impl Iterator<Item = (&Node<N>, &E)> {
self.graph
.edges_directed(id, Direction::Outgoing)
.map(move |edge| {
let krate = &self.graph[edge.target()];
(krate, edge.weight())
})
}
/// Gets crates directly depended upon by the specified node
#[inline]
pub fn direct_dependencies(&self, nid: NodeId) -> Vec<DirectDependency<'_, N>> {
let graph = self.graph();
let mut direct_dependencies = Vec::new();
let mut stack = vec![nid];
let mut visited = std::collections::BTreeSet::new();
while let Some(nid) = stack.pop() {
for edge in graph.edges_directed(nid, Direction::Outgoing) {
match &graph[edge.target()] {
Node::Krate { krate, .. } => {
if visited.insert(edge.target()) {
direct_dependencies.push(DirectDependency {
krate,
node_id: edge.target(),
edge_id: edge.id(),
});
}
}
Node::Feature { .. } => {
if visited.insert(edge.target()) {
stack.push(edge.target());
}
}
}
}
}
direct_dependencies
}
/// Gets the crates that have a direct dependency on the specified node
#[inline]
pub fn direct_dependents(&self, nid: NodeId) -> Vec<DirectDependent<'_, N>> {
let graph = self.graph();
let mut direct_dependents = Vec::new();
let mut stack = vec![nid];
let mut visited = std::collections::BTreeSet::new();
while let Some(nid) = stack.pop() {
for edge in graph.edges_directed(nid, Direction::Incoming) {
match &graph[edge.source()] {
Node::Krate { krate, .. } => {
if visited.insert(edge.source()) {
direct_dependents.push(DirectDependent {
krate,
node_id: edge.source(),
edge_id: edge.id(),
});
}
}
Node::Feature { krate_index, .. } => {
if *krate_index == nid && visited.insert(edge.source()) {
stack.push(edge.source());
}
}
}
}
}
direct_dependents
}
/// Get the node identifier for the specified crate identifier
#[inline]
pub fn nid_for_kid(&self, kid: &Kid) -> Option<NodeId> {
self.graph.raw_nodes()[..self.krates_end]
.binary_search_by(|rn| {
if let Node::Krate { id, .. } = &rn.weight {
id.cmp(kid)
} else {
unreachable!();
}
})
.ok()
.map(NodeId::new)
}
/// Get the node for the specified crate identifier
#[inline]
pub fn node_for_kid(&self, kid: &Kid) -> Option<&Node<N>> {
self.nid_for_kid(kid).map(|nid| &self.graph[nid])
}
#[inline]
pub fn get_node(&self, kid: &Kid, feature: Option<&str>) -> Option<(NodeId, &Node<N>)> {
self.nid_for_kid(kid).and_then(|nid| {
if let Some(feat) = feature {
self.graph
.edges_directed(nid, Direction::Incoming)
.find_map(|edge| {
if let Node::Feature { krate_index, name } = &self.graph[edge.source()] {
if *krate_index == nid && name == feat {
return Some((edge.source(), &self.graph[edge.source()]));
}
}
None
})
} else {
Some((nid, &self.graph[nid]))
}
})
}
/// Gets the features enabled for the specified crate
#[inline]
pub fn get_enabled_features(&self, kid: &Kid) -> Option<&EnabledFeatures> {
self.node_for_kid(kid).map(|node| {
if let Node::Krate { features, .. } = node {
features
} else {
unreachable!()
}
})
}
/// Get an iterator over the nodes for the members of the workspace
#[inline]
pub fn workspace_members(&self) -> impl Iterator<Item = &Node<N>> {
self.workspace_members
.iter()
.filter_map(move |pid| self.nid_for_kid(pid).map(|ind| &self.graph[ind]))
}
}
/// A direct dependency of a crate
pub struct DirectDependency<'krates, N> {
/// The crate in the node
pub krate: &'krates N,
/// The crate's node id
pub node_id: NodeId,
/// The edge that links the crate with the crate that depends on it
pub edge_id: EdgeId,
}
/// A crate that has a direct dependency on another crate
pub struct DirectDependent<'krates, N> {
/// The crate in the node
pub krate: &'krates N,
/// The crate's node id
pub node_id: NodeId,
/// The edge that links the crate with the dependency
pub edge_id: EdgeId,
}
/// A trait that can be applied to the type stored in the graph nodes to give
/// additional features on `Krates`.
pub trait KrateDetails {
/// The name of the crate
fn name(&self) -> &str;
/// The version of the crate
fn version(&self) -> &semver::Version;
}
impl KrateDetails for cm::Package {
fn name(&self) -> &str {
&self.name
}
fn version(&self) -> &semver::Version {
&self.version
}
}
impl<N> Krates<N, Edge>
where
N: std::fmt::Debug,
{
/// Removes all of the crates that are only referenced via the specified
/// dependency kind.
///
/// This gives the same output as if the graph had been built by using
/// [`ignore_kind`](crate::Builder::ignore_kind) with [`Scope::all`](crate::Scope::All)
pub fn krates_filtered(&self, filter: DepKind) -> Vec<&N> {
let graph = self.graph();
let mut filtered: std::collections::BTreeMap<_, _> = self
.workspace_members()
.filter_map(|n| {
let Node::Krate { id, krate, .. } = n else {
return None;
};
Some((id, krate))
})
.collect();
let mut stack: Vec<_> = self
.workspace_members
.iter()
.filter_map(|pid| self.nid_for_kid(pid))
.collect();
let mut visited = std::collections::BTreeSet::new();
while let Some(nid) = stack.pop() {
for edge in graph.edges_directed(nid, Direction::Outgoing) {
match edge.weight() {
Edge::Dep { kind, .. } | Edge::DepFeature { kind, .. } => {
if *kind == filter {
continue;
}
}
Edge::Feature => {}
};
match &graph[edge.target()] {
Node::Krate { id, krate, .. } => {
if visited.insert(edge.target()) {
stack.push(edge.target());
filtered.insert(id, krate);
}
}
Node::Feature { .. } => {
if visited.insert(edge.target()) {
stack.push(edge.target());
}
}
}
}
visited.insert(nid);
}
filtered.into_values().collect()
}
}
/// If the node type N supports [`KrateDetails`], we can also iterator over krates
/// of a given name and or version
impl<N, E> Krates<N, E>
where
N: KrateDetails,
{
/// Get an iterator over the crates that match the specified name, as well
/// as satisfy the specified semver requirement.
///
/// ```no_run
/// use krates::{Krates, semver::VersionReq};
///
/// fn print(krates: &Krates, name: &str) {
/// let req = VersionReq::parse("=0.2").unwrap();
/// for vs in krates.search_matches(name, req.clone()).map(|km| &km.krate.version) {
/// println!("found version {vs} matching {req}!");
/// }
/// }
/// ```
pub fn search_matches(
&self,
name: impl Into<String>,
req: semver::VersionReq,
) -> impl Iterator<Item = KrateMatch<'_, N>> {
let raw_nodes = &self.graph.raw_nodes()[0..self.krates_end];
let name = name.into();
raw_nodes
.iter()
.enumerate()
.filter_map(move |(index, node)| {
if let Node::Krate { krate, id, .. } = &node.weight {
if krate.name() == name && req.matches(krate.version()) {
return Some(KrateMatch {
node_id: NodeId::new(index),
krate,
kid: id,
});
}
}
None
})
}
/// Get an iterator over all of the crates in the graph with the given name,
/// in the case there are multiple versions, or sources, of the crate.
///
/// ```
/// use krates::Krates;
///
/// fn print_all_versions(krates: &Krates, name: &str) {
/// for vs in krates.krates_by_name(name).map(|km| &km.krate.version) {
/// println!("found version {vs}");
/// }
/// }
/// ```
pub fn krates_by_name(
&self,
name: impl Into<String>,
) -> impl Iterator<Item = KrateMatch<'_, N>> {
let raw_nodes = &self.graph.raw_nodes()[0..self.krates_end];
let name = name.into();
raw_nodes
.iter()
.enumerate()
.filter_map(move |(index, node)| {
if let Node::Krate { krate, id, .. } = &node.weight {
if krate.name() == name {
return Some(KrateMatch {
node_id: NodeId::new(index),
krate,
kid: id,
});
}
}
None
})
}
}
pub struct KrateMatch<'graph, N> {
pub krate: &'graph N,
pub kid: &'graph Kid,
pub node_id: NodeId,
}
impl<N, E> std::ops::Index<NodeId> for Krates<N, E> {
type Output = N;
#[inline]
fn index(&self, id: NodeId) -> &Self::Output {
match &self.graph[id] {
Node::Krate { krate, .. } => krate,
Node::Feature { .. } => panic!("indexed outside of crate graph"),
}
}
}
impl<N, E> std::ops::Index<usize> for Krates<N, E> {
type Output = N;
#[inline]
fn index(&self, idx: usize) -> &Self::Output {
match &self.graph.raw_nodes()[idx].weight {
Node::Krate { krate, .. } => krate,
Node::Feature { .. } => panic!("indexed outside of crate graph"),
}
}
}
#[cfg(test)]
mod tests {
#[test]
fn converts_package_ids() {
let ids = [
// STABLE
// A typical registry url, source, name, and version are always distinct
("registry+https://github.com/rust-lang/crates.io-index#[email protected]", "ab_glyph", "0.2.22", "registry+https://github.com/rust-lang/crates.io-index"),
// A git url, with a `rev` specifier. For git urls, if the name of the package is the same as the last path component of the source, the name is not repeated after the #, only the version
("git+https://github.com/EmbarkStudios/egui-stylist?rev=3900e8aedc5801e42c1bb747cfd025615bf3b832#0.2.0", "egui-stylist", "0.2.0", "git+https://github.com/EmbarkStudios/egui-stylist?rev=3900e8aedc5801e42c1bb747cfd025615bf3b832"),
// The same as with git urls, the name is only after the # if it is different from the last path component
("path+file:///home/jake/code/ark/components/allocator#[email protected]", "ark-allocator", "0.1.0", "path+file:///home/jake/code/ark/components/allocator"),
// A git url with a `branch` specifier
("git+https://github.com/EmbarkStudios/ash?branch=nv-low-latency2#0.38.0+1.3.269", "ash", "0.38.0+1.3.269", "git+https://github.com/EmbarkStudios/ash?branch=nv-low-latency2"),
// A git url with a `branch` specifier and a different name from the repo
("git+https://github.com/EmbarkStudios/fsr-rs?branch=nv-low-latency2#[email protected]", "fsr", "0.1.7", "git+https://github.com/EmbarkStudios/fsr-rs?branch=nv-low-latency2"),
// A git url that doesn't specify a branch, tag, or revision, defaulting to HEAD
("git+https://github.com/ComunidadAylas/glsl-lang#0.5.2", "glsl-lang", "0.5.2", "git+https://github.com/ComunidadAylas/glsl-lang"),
// A git url that uses a `tag` specifier
("git+https://github.com/vtavernier/glsl-lang?tag=v0.5.2#0.5.2", "glsl-lang", "0.5.2", "git+https://github.com/vtavernier/glsl-lang?tag=v0.5.2"),
// OPAQUE
("fuser 0.4.1 (git+https://github.com/cberner/fuser?branch=master#b2e7622942e52a28ffa85cdaf48e28e982bb6923)", "fuser", "0.4.1", "git+https://github.com/cberner/fuser?branch=master"),
("fuser 0.4.1 (git+https://github.com/cberner/fuser?rev=b2e7622#b2e7622942e52a28ffa85cdaf48e28e982bb6923)", "fuser", "0.4.1", "git+https://github.com/cberner/fuser?rev=b2e7622"),
("a 0.1.0 (path+file:///home/jake/code/krates/tests/ws/a)", "a", "0.1.0", "path+file:///home/jake/code/krates/tests/ws/a"),
("bindgen 0.59.2 (registry+https://github.com/rust-lang/crates.io-index)", "bindgen", "0.59.2", "registry+https://github.com/rust-lang/crates.io-index"),
];
for (repr, name, version, source) in ids {
let kid = super::Kid::from(cargo_metadata::PackageId {
repr: repr.to_owned(),
});
assert_eq!(kid.name(), name);
assert_eq!(kid.version(), version);
assert_eq!(kid.source(), source);
}
}
}