pub(crate) mod features;
use crate::{DepKind, Edge, Error, Kid, Krates};
use cargo_metadata as cm;
use features::{Feature, ParsedFeature};
use std::{
collections::HashMap,
path::{Path, PathBuf},
};
/// An alternative to [`cargo_metadata::MetadataCommand`] which allows correct
/// feature usage, as well as ensuring that the command can run successfully
/// regardless of where it is executed and on what.
#[derive(Default, Debug)]
pub struct Cmd {
cargo_path: Option<PathBuf>,
manifest_path: Option<PathBuf>,
current_dir: Option<PathBuf>,
features: Vec<String>,
other_options: Vec<String>,
all_features: bool,
no_default_features: bool,
frozen: bool,
locked: bool,
offline: bool,
}
#[derive(Copy, Clone)]
pub struct LockOptions {
/// Requires that the Cargo.lock file is up-to-date. If the lock file is
/// missing, or it needs to be updated, Cargo will exit with an error.
/// Prevents Cargo from attempting to access the network to determine if it
/// is out-of-date.
pub frozen: bool,
/// Requires that the Cargo.lock file is up-to-date. If the lock file is
/// missing, or it needs to be updated, Cargo will exit with an error.
pub locked: bool,
/// Prevents Cargo from accessing the network for any reason. Without this
/// flag, Cargo will stop with an error if it needs to access the network
/// and the network is not available. With this flag, Cargo will attempt to
/// proceed without the network if possible.
///
/// Beware that this may result in different dependency resolution than
/// online mode. Cargo will restrict itself to crates that are downloaded
/// locally, even if there might be a newer version as indicated in the
/// local copy of the index. See the [cargo fetch](https://doc.rust-lang.org/cargo/commands/cargo-fetch.html)
/// command to download dependencies before going offline.
pub offline: bool,
}
impl Cmd {
pub fn new() -> Self {
Self::default()
}
/// Path to `cargo` executable. If not set, this will use the the `$CARGO`
/// environment variable, and if that is not set, will simply be `cargo`.
pub fn cargo_path(&mut self, path: impl Into<PathBuf>) -> &mut Self {
self.cargo_path = Some(path.into());
self
}
/// Path to a `Cargo.toml` manifest
pub fn manifest_path(&mut self, path: impl Into<PathBuf>) -> &mut Self {
self.manifest_path = Some(path.into());
self
}
/// Current directory of the `cargo metadata` process.
pub fn current_dir(&mut self, path: impl Into<PathBuf>) -> &mut Self {
self.current_dir = Some(path.into());
self
}
/// Disables default features.
///
/// **NOTE**: This has **no effect** if used on a workspace. You must
/// specify a working directory or manifest path to a specific crate if used
/// on a crate inside a workspace.
pub fn no_default_features(&mut self) -> &mut Self {
self.no_default_features = true;
self
}
/// Enables all features for all workspace crates. Usable on both individual
/// crates and on an entire workspace.
pub fn all_features(&mut self) -> &mut Self {
self.all_features = true;
self
}
/// Enables specific features. See the **NOTE** for `no_default_features`
pub fn features(&mut self, feats: impl IntoIterator<Item = String>) -> &mut Self {
self.features.extend(feats);
self
}
/// Sets the various [lock options](https://doc.rust-lang.org/cargo/commands/cargo-metadata.html#manifest-options)
/// for determining if cargo can access the network and if the lockfile must
/// be present and can be modified
pub fn lock_opts(&mut self, lopts: LockOptions) -> &mut Self {
self.frozen = lopts.frozen;
self.locked = lopts.locked;
self.offline = lopts.offline;
self
}
/// Arbitrary command line flags to pass to `cargo`. These will be added to
/// the end of the command line invocation.
pub fn other_options(&mut self, options: impl IntoIterator<Item = String>) -> &mut Self {
self.other_options.extend(options);
self
}
}
#[allow(clippy::fallible_impl_from)]
impl From<Cmd> for cm::MetadataCommand {
fn from(mut cmd: Cmd) -> cm::MetadataCommand {
let mut mdc = cm::MetadataCommand::new();
if let Some(cp) = cmd.cargo_path {
mdc.cargo_path(cp);
}
// If the manifest path is set, we force set the current working
// directory to its parent and use the relative path, this is to fix an
// edge case where you can run cargo metadata from a directory outside
// of a workspace which could fail if eg. there is a reference to a
// registry that is defined in the workspace's .cargo/config
if let Some(mp) = cmd.manifest_path {
cmd.current_dir = Some(mp.parent().unwrap().to_owned());
mdc.manifest_path("Cargo.toml");
}
if let Some(cd) = cmd.current_dir {
mdc.current_dir(cd);
}
// Everything else we specify as additional options, as MetadataCommand
// does not handle features correctly, eg. you cannot disable default
// and set specific ones at the same time
// https://github.com/oli-obk/cargo_metadata/issues/79
cmd.features.sort();
cmd.features.dedup();
let mut opts = Vec::with_capacity(
cmd.features.len()
+ cmd.other_options.len()
+ usize::from(cmd.no_default_features)
+ usize::from(cmd.all_features),
);
if cmd.no_default_features {
opts.push("--no-default-features".to_owned());
}
if cmd.all_features {
opts.push("--all-features".to_owned());
}
if !cmd.features.is_empty() {
opts.push("--features".to_owned());
opts.push(cmd.features.join(" "));
}
if cmd.frozen {
opts.push("--frozen".to_owned());
}
if cmd.locked {
opts.push("--locked".to_owned());
}
if cmd.offline {
opts.push("--offline".to_owned());
}
opts.append(&mut cmd.other_options);
mdc.other_options(opts);
mdc
}
}
#[derive(Clone)]
pub enum Target {
Builtin(&'static cfg_expr::targets::TargetInfo),
#[cfg(feature = "targets")]
Triple(cfg_expr::target_lexicon::Triple),
Unknown(String),
}
impl<T> From<T> for Target
where
T: AsRef<str>,
{
fn from(triple: T) -> Self {
let triple = triple.as_ref();
match cfg_expr::targets::get_builtin_target_by_triple(triple) {
Some(bi) => Self::Builtin(bi),
None => {
#[cfg(feature = "targets")]
{
match triple.parse() {
Ok(triple) => Self::Triple(triple),
Err(_) => Self::Unknown(triple.to_owned()),
}
}
#[cfg(not(feature = "targets"))]
Self::Unknown(triple.to_owned())
}
}
}
}
use std::fmt;
impl fmt::Display for Target {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Builtin(bi) => f.write_str(bi.triple.as_str()),
#[cfg(feature = "targets")]
Self::Triple(trip) => write!(f, "{}", trip),
Self::Unknown(unknown) => f.write_str(unknown),
}
}
}
struct TargetFilter {
inner: Target,
features: Vec<String>,
}
impl TargetFilter {
fn eval(&self, predicate: &cfg_expr::Predicate<'_>) -> bool {
match predicate {
cfg_expr::expr::Predicate::Target(tp) => match &self.inner {
Target::Builtin(bi) => tp.matches(*bi),
#[cfg(feature = "targets")]
Target::Triple(trip) => tp.matches(trip),
Target::Unknown(_) => false,
},
cfg_expr::expr::Predicate::TargetFeature(feat) => {
// TODO: target_features are extremely rare in cargo.toml
// files, it might be a good idea to inform the user of this
// somehow, if they are unsure why a particular dependency
// is being filtered
self.features.iter().any(|f| f == feat)
}
// We *could* warn here about an invalid expression, but
// presumably cargo will be responsible for that, so don't bother
_ => false,
}
}
fn matches_triple(&self, triple: &str) -> bool {
match &self.inner {
Target::Builtin(bi) => bi.triple.as_str() == triple,
#[cfg(feature = "targets")]
Target::Triple(trip) => {
let as_triple = format!("{}", trip);
as_triple == triple
}
Target::Unknown(unknown) => unknown == triple,
}
}
}
/// The scope for which a dependency kind will be ignored
#[derive(Clone, Copy)]
pub enum Scope {
/// Will match a dependency from a crate in the workspace
Workspace,
/// Will match a dependency from any crate not in the workspace
NonWorkspace,
/// Will ignore a dependency from any crate
All,
}
/// Trait used to report back any crates that are completely ignored in the
/// final crate graph that is built. This occurs when the crate has no
/// dependents any longer due to the applied filters.
pub trait OnFilter {
fn filtered(&mut self, krate: cm::Package);
}
/// For when you just want to satisfy [`OnFilter`] without doing anything
pub struct NoneFilter;
impl OnFilter for NoneFilter {
fn filtered(&mut self, _: cm::Package) {}
}
impl<F> OnFilter for F
where
F: FnMut(cm::Package),
{
fn filtered(&mut self, krate: cm::Package) {
self(krate);
}
}
/// A builder used to create a Krates graph, either by running a cargo metadata
/// command, or using an already deserialized [`cargo_metadata::Metadata`]
#[derive(Default)]
pub struct Builder {
target_filters: Vec<TargetFilter>,
workspace_filters: Vec<PathBuf>,
exclude: Vec<crate::PkgSpec>,
workspace: bool,
ignore_kinds: u32,
}
impl Builder {
pub fn new() -> Self {
Self::default()
}
/// Ignores a specific dependency kind in the given scope.
///
/// ```
/// # use krates::{Builder, DepKind, Scope};
/// Builder::new().ignore_kind(DepKind::Build, Scope::NonWorkspace);
/// ```
///
/// In the above example, let's say we depended on `zstd`. zstd depends on
/// the `cc` crate (`zstd -> zstd-safe -> zstd-sys -> cc`) for building
/// C code. By ignoring the `build` kind for non-workspace crates, the link
/// from `zstd-sys` -> `cc` will be filtered out. If the same `cc` is not
/// depended on by a crate in the workspace, `cc` will not end up in the
/// final `Krates` graph.
///
/// Note that ignoring [`DepKind::Dev`] for [`Scope::NonWorkspace`] is
/// meaningless as dev dependencies are not resolved by cargo for transitive
/// dependencies.
pub fn ignore_kind(&mut self, kind: DepKind, scope: Scope) -> &mut Self {
let kind_flag = match kind {
DepKind::Normal => 0x1,
DepKind::Dev => 0x8,
DepKind::Build => 0x40,
};
self.ignore_kinds |= kind_flag;
self.ignore_kinds |= match scope {
Scope::Workspace => kind_flag << 1,
Scope::NonWorkspace => kind_flag << 2,
Scope::All => kind_flag << 1 | kind_flag << 2,
};
self
}
/// By default, the response from `cargo metadata` determines what the
/// root(s) of the crate graph will be. If the Cargo.toml path used is a
/// virtual manifest, then each workspace member will be used as a root. If
/// the manifest path is for a single crate, or a non-virtual manifest
/// inside a workspace, then only that single crate will be used as the
/// root, and in the workspace case, only other workspace members that are
/// dependencies of that root crate, directly or indirectly, will be
/// included in the final graph.
///
/// Setting workspace = true will change that default behavior, and instead
/// include all workspace crates (unless they are filtered via other
/// methods) even if the manifest path is not a virtual manifest inside
/// a workspace
///
/// ```
/// # use krates::Builder;
/// Builder::new().workspace(true);
/// ```
pub fn workspace(&mut self, workspace: bool) -> &mut Self {
self.workspace = workspace;
self
}
/// Package specification(s) to exclude from the final graph. Unlike with
/// cargo, each exclusion spec can apply to more than 1 instance of a
/// package, eg if multiple crates are sourced from the same url, or
/// multiple versions of the same crate
///
/// ```
/// # use krates::Builder;
/// Builder::new().exclude(["a-crate:0.1.0"].iter().map(|spec| spec.parse().unwrap()));
/// ```
pub fn exclude<I>(&mut self, exclude: I) -> &mut Self
where
I: IntoIterator<Item = crate::PkgSpec>,
{
self.exclude.extend(exclude);
self
}
/// By default, every workspace crate is treated as a root node and
/// implicitly added to the graph if the graph is built from a workspace
/// context and not a specific crate in the workspace.
///
/// By using this method, only the workspace crates whose Cargo.toml path
/// matches one of the specified crates will be added as root nodes, meaning
/// that any workspace crate not in the list that doesn't have any
/// dependendents on a workspace crate that does, will no longer appear in
/// the graph.
///
/// If you specify only a single path, and that path is actually to a
/// a workspace's virtual manifest, the graph will be the same as if
/// [`Builder::include_workspace_crates`] was not specified.
///
/// ```
/// # use krates::{Builder, DepKind, Scope};
/// Builder::new().include_workspace_crates(&["path/to/some/crate"]);
/// ```
pub fn include_workspace_crates<P, I>(&mut self, crates: I) -> &mut Self
where
P: AsRef<Path>,
I: IntoIterator<Item = P>,
{
self.workspace_filters.extend(crates.into_iter().map(|p| {
// It's the users's responsibility to give proper paths here, as
// we can't rely on eg canonicalization since we might not be on
// the same filesystem any more. We do fixup the ensure they point
// at a Cargo.toml however
let p = p.as_ref();
// Attempt to canonicalize the path, which might not work if the
// user is attempting to add a path to filter from another
// filesystem or similar
let p = p.canonicalize().unwrap_or_else(|_| p.to_owned());
if !p.ends_with("Cargo.toml") {
p.join("Cargo.toml")
} else {
p
}
}));
self
}
/// By default, cargo resolves all target specific dependencies. Optionally,
/// you can use the `--filter-platform` option on `cargo metadata` to
/// resolve only dependencies that match the specified target, but it can
/// only do this for one platlform.
///
/// By using this method, you can specify one or more targets by their
/// triple, as well as any [`target_features`](https://doc.rust-lang.org/reference/attributes/codegen.html#the-target_feature-attribute)
/// that you [promise](https://doc.rust-lang.org/reference/behavior-considered-undefined.html)
/// are enabled for that target to filter dependencies by. If any of the
/// specified targets matches a target specific dependency, it will be
/// included in the graph.
///
/// When specifying a target triple, only builtin targets of rustc can be
/// used to evaluate `cfg()` expressions. If the triple is not recognized,
/// it will only be evaluated against `[target.<triple-or-json>.<|build-|dev->dependencies]`.
///
/// ```
/// # use krates::{Builder, DepKind, Scope};
/// let targets = [
/// // the big 3
/// "x86_64-unknown-linux-gnu",
/// "x86_64-pc-windows-msvc",
/// "x86_64-apple-darwin",
/// // and musl!
/// "x86_64-unknown-linux-musl",
/// // and wasm (with the fancy atomics feature!)
/// "wasm32-unknown-unknown",
/// ];
///
/// Builder::new().include_targets(targets.iter().map(|triple| {
/// if triple.starts_with("wasm32") {
/// (*triple, vec!["atomics".to_owned()])
/// } else {
/// (*triple, vec![])
/// }
/// }));
/// ```
pub fn include_targets<S: Into<Target>>(
&mut self,
targets: impl IntoIterator<Item = (S, Vec<String>)>,
) -> &mut Self {
self.target_filters
.extend(targets.into_iter().map(|(triple, features)| TargetFilter {
inner: triple.into(),
features,
}));
self
}
/// Builds a [`Krates`] graph using metadata that be retrieved via the
/// specified metadata command. If `on_filter` is specified, it will be
/// called with each package that was filtered from the graph, if any.
///
/// This method will fail if the metadata command fails for some reason, or
/// if the command specifies `--no-deps` which means there will be no
/// resolution graph to build our graph from.
///
/// ```no_run
/// # use krates::cm::Package;
/// let mut mdc = krates::Cmd::new();
/// mdc.manifest_path("path/to/Cargo.toml");
///
/// if /*no_default_features*/ true {
/// mdc.no_default_features();
/// }
///
/// if /*cfg.all_features*/ false {
/// mdc.all_features();
/// }
///
/// mdc.features(
/// ["cool-feature", "cooler-feature", "coolest-feature"]
/// .iter()
/// .map(|s| s.to_string()),
/// );
///
/// let mut builder = krates::Builder::new();
///
/// if /*cfg.ignore_build_dependencies*/ false {
/// builder.ignore_kind(krates::DepKind::Build, krates::Scope::All);
/// }
///
/// if /*cfg.ignore_dev_dependencies*/ true {
/// builder.ignore_kind(krates::DepKind::Dev, krates::Scope::All);
/// }
///
/// let graph: krates::Krates = builder.build(
/// mdc,
/// |filtered: Package| match filtered.source {
/// Some(src) => {
/// if src.is_crates_io() {
/// println!("filtered {} {}", filtered.name, filtered.version);
/// } else {
/// println!("filtered {} {} {}", filtered.name, filtered.version, src);
/// }
/// }
/// None => println!("filtered crate {} {}", filtered.name, filtered.version),
/// },
/// ).unwrap();
/// ```
pub fn build<N, E, F>(
self,
cmd: impl Into<cm::MetadataCommand>,
on_filter: F,
) -> Result<Krates<N, E>, Error>
where
N: From<cargo_metadata::Package>,
E: From<Edge>,
F: OnFilter,
{
let metadata = cmd.into().exec()?;
self.build_with_metadata(metadata, on_filter)
}
/// Builds a [`Krates`] graph using the specified metadata. If `on_filter` is
/// specified, it will be called with each package that was filtered from
/// the graph, if any.
///
/// The metadata **must** have resolved dependencies for the graph to be
/// built, so not having it is the only way this method will fail.
///
/// ```no_run
/// # use krates::{Krates, Builder, DepKind, Scope, cm::Package};
/// let contents = std::fs::read_to_string("metadata.json")
/// .map_err(|e| format!("failed to load metadata file: {}", e)).unwrap();
///
/// let md: krates::cm::Metadata = serde_json::from_str(&contents)
/// .map_err(|e| format!("failed to deserialize metadata: {}", e)).unwrap();
///
/// let krates: Krates = Builder::new().build_with_metadata(
/// md,
/// |pkg: Package| println!("filtered {}", pkg.id)
/// ).unwrap();
///
/// println!("found {} unique crates", krates.len());
/// ```
pub fn build_with_metadata<N, E, F>(
self,
md: cargo_metadata::Metadata,
mut on_filter: F,
) -> Result<Krates<N, E>, Error>
where
N: From<cargo_metadata::Package>,
E: From<Edge>,
F: OnFilter,
{
let resolved = md.resolve.ok_or(Error::NoResolveGraph)?;
let mut packages = md.packages;
packages.sort_by(|a, b| a.id.cmp(&b.id));
let mut workspace_members = md.workspace_members;
workspace_members.sort();
let mut pid_stack = Vec::with_capacity(workspace_members.len());
// Only include workspaces members the user wants if they have specified
// any, this is to take into account scenarios where you have a large
// workspace, but only want to get the crates used by a subset of the
// workspace
if self.workspace_filters.is_empty() {
// If the resolve graph specifies a root, it means the user
// specified a particular crate in a workspace, so we'll only use
// that single root for the entire graph rather than a root for each
// workspace member crate
if !self.workspace {
if let Some(root) = &resolved.root {
pid_stack.push(root);
}
}
if pid_stack.is_empty() {
pid_stack.extend(workspace_members.iter());
}
} else {
// If the filters only contain 1 path, and it is the path to a
// workspace toml, then we disregard the filters
if self.workspace_filters.len() == 1
&& Some(md.workspace_root.as_ref()) == self.workspace_filters[0].parent()
{
pid_stack.extend(workspace_members.iter());
} else {
for wm in &workspace_members {
if let Ok(i) = packages.binary_search_by(|pkg| pkg.id.cmp(wm)) {
if self
.workspace_filters
.iter()
.any(|wf| wf == &packages[i].manifest_path)
{
pid_stack.push(wm);
}
}
}
}
}
let exclude = self.exclude;
let include_all_targets = self.target_filters.is_empty();
let ignore_kinds = self.ignore_kinds;
let targets = self.target_filters;
// For features, we need to know what the root crates are in the graph,
// as the features enabled on those crates are the real source of truth,
// as all features of non-root crates can be made inaccurate due to
// graph pruning
let roots: std::collections::BTreeSet<_> = pid_stack.iter().cloned().collect();
let is_root_crate = |pid: &cm::PackageId| -> bool { roots.contains(&pid) };
#[derive(Debug)]
struct DepKindInfo {
kind: DepKind,
cfg: Option<String>,
}
#[derive(Debug)]
// We use our resolution nodes because cargo_metadata uses
// non-exhaustive everywhere :p
struct NodeDep {
/// The name of the dependency, which could be a different name than the crate itself
name: String,
pkg: Kid,
dep_kinds: Vec<DepKindInfo>,
}
#[derive(Debug)]
struct Node {
id: Kid,
deps: Vec<NodeDep>,
features: Vec<String>,
}
let mut nodes: Vec<_> = resolved
.nodes
.into_iter()
.map(|rn| {
if let Err(i) = packages.binary_search_by(|k| k.id.cmp(&rn.id)) {
// In the case of git dependencies, the package ids may not line up exactly, due to the
// user facing id containing the revision specifier (eg ?branch=master), whereas the id used to
// reference it as a dependency in other parts of the graph only use the fully resolved
// id with the #<rev>
let probable = &packages[i];
let prepr = DecomposedRepr::build(&probable.id);
let drepr = DecomposedRepr::build(&rn.id);
if prepr != drepr {
panic!("Unable to find dependency {} in list of packages", rn.id);
}
}
let deps = rn
.deps
.into_iter()
.map(|dn| {
// This requires 1.41+
let dep_kinds = dn
.dep_kinds
.into_iter()
.map(|dk| DepKindInfo {
kind: dk.kind.into(),
cfg: dk.target.map(|t| t.to_string()),
})
.collect();
NodeDep {
name: dn.name,
pkg: dn.pkg,
dep_kinds,
}
})
.collect();
let mut features = rn.features;
// Note that cargo metadata _currently_ always outputs these in
// lexicographic order, but I don't know if that is actually
// guaranteed at all and might just be due to the implementation
// (eg stored in a Btree), so we just perform our own sort to
// guarantee that this is indeed always sorted since we rely on
// that attribute
features.sort();
Node {
id: rn.id,
deps,
features,
}
})
.collect();
nodes.sort_by(|a, b| a.id.cmp(&b.id));
#[derive(Debug)]
enum FeatureEdgeName {
Feature(String),
Rename(String),
Krate,
}
#[derive(Debug)]
struct FeatureEdge<'nodes> {
kid: &'nodes Kid,
name: FeatureEdgeName,
}
#[inline]
fn crate_name_from_pid(pid: &cm::PackageId) -> &str {
let name_end = pid.repr.find(' ').unwrap();
&pid.repr[..name_end]
}
let mut dep_edge_map = HashMap::new();
let mut feature_edge_map = std::collections::BTreeMap::new();
#[derive(Debug)]
struct DependencyEdge {
kind: DepKind,
cfg: Option<String>,
features: Vec<String>,
uses_default_features: bool,
}
#[derive(Debug)]
struct KrateDependency<'p> {
pkg: &'p cm::PackageId,
edges: Vec<DependencyEdge>,
features: Vec<String>,
}
#[cfg(feature = "crates-index")]
let index = crates_index::Index::new_cargo_default().ok();
while let Some(pid) = pid_stack.pop() {
let is_in_workspace = workspace_members.binary_search(pid).is_ok();
let krate_index = nodes.binary_search_by(|n| n.id.cmp(pid)).unwrap();
let rnode = &nodes[krate_index];
let krate = &mut packages[krate_index];
if exclude.iter().any(|exc| exc.matches(krate)) {
continue;
}
#[cfg(debug_assertions)]
{
let rrepr = DecomposedRepr::build(&rnode.id);
let krepr = DecomposedRepr::build(&krate.id);
debug_assert_eq!(rrepr, krepr);
}
let get_dep_id = |dep_name: &str| -> Option<&Kid> {
let kid = rnode.deps.iter().find_map(|ndep| {
let pkg_name = crate_name_from_pid(&ndep.pkg);
if dep_names_match(dep_name, &ndep.name) || dep_name == pkg_name {
Some(&ndep.pkg)
} else {
None
}
});
if let Some(kid) = kid {
Some(kid)
} else {
//dbg!("failed to find {dep_name} {:#?}", &rnode.deps);
None
}
};
#[cfg(feature = "prefer-index")]
if let Some(index) = &index {
fix_features(index, krate);
}
// Cargo puts out a flat list of the enabled features, but we need
// to use the declared features on the crate itself to figure out
// the actual chain of features from one crate to another
// package features:
// "features": {
// "blocking": [
// "simple",
// "reqwest?/blocking"
// ],
// "default": [
// "simple"
// ],
// "json": [
// "reqwest?/json"
// ],
// "multipart": [
// "reqwest?/multipart"
// ],
// "reqwest": [
// "dep:reqwest"
// ],
// "rgb": [
// "dep:rgb"
// ],
// "serde": [
// "dep:serde",
// "rgb?/serde"
// ],
// "simple": [
// "json"
// ],
// "ssh": [
// "git/ssh",
// "git/ssh_key_from_memory"
// ],
// "stream": [
// "reqwest/stream"
// ],
// "zlib": [
// "git/zlib-ng-compat",
// "reqwest?/deflate"
// ]
// },
// resolved features:
// "features": [
// "blocking",
// "json",
// "reqwest",
// "simple",
// "stream"
// ]
let enabled_features: Vec<_> = rnode
.features
.iter()
.filter_map(|feat| {
// This _should_ never fail in normal cases, however if the
// `prefer-index` feature is not enabled, it's possible for
// the resolved features to mention features that aren't in
// the actual crate manifest
let sub_feats: Vec<_> = krate
.features
.get(feat)?
.iter()
.filter_map(|sub_feat| {
let sf = ParsedFeature::from(sub_feat.as_str());
match sf.feat() {
Feature::Krate(krate_name) => {
let kid = get_dep_id(krate_name)?;
let real_name = crate_name_from_pid(kid);
Some(FeatureEdge {
kid,
name: if real_name != krate_name {
FeatureEdgeName::Rename(krate_name.to_owned())
} else {
FeatureEdgeName::Krate
},
})
}
Feature::Simple(s) => Some(FeatureEdge {
kid: pid,
name: FeatureEdgeName::Feature(s.to_owned()),
}),
Feature::Strong {
krate: krate_name,
feature,
} => Some(FeatureEdge {
kid: get_dep_id(krate_name)?,
name: FeatureEdgeName::Feature(feature.to_owned()),
}),
Feature::Weak {
krate: krate_name,
feature,
} => {
if rnode.features.iter().any(|kn| kn == krate_name) {
Some(FeatureEdge {
kid: get_dep_id(krate_name)?,
name: FeatureEdgeName::Feature(feature.to_owned()),
})
} else {
None
}
}
}
})
.collect();
Some((feat.clone(), sub_feats))
})
.collect();
// Though each unique dependency can only be resolved once, it's possible
// for the crate to list the same dependency multiple times, with different
// dependency kinds, or different target configurations, so each one gets its
// own edge
let deps: Vec<_> = rnode
.deps
.iter()
.filter_map(|rdep| {
let targets = &targets;
let pkg = &rdep.pkg;
// We also have to take into account that a package
// can rename its own library output, eg.
// ```ini
// [package]
// name = "coreaudio-rs"
//
// [lib]
// name = "coreaudio"
// ```
let maybe_real_name = crate_name_from_pid(pkg);
// Dependencies will default to saying "uses_default_features" on edges,
// even if the crate in question doesn't actually have a "default" feature,
// so check that it actually does
let has_default_feature = {
let krate_index = nodes.binary_search_by(|n| n.id.cmp(pkg)).unwrap();
let rnode = &nodes[krate_index];
// We've already guaranteed this list is sorted
rnode.features.binary_search_by(|f| f.as_str().cmp("default")).is_ok()
};
let edges: Vec<_> = rdep.dep_kinds.iter().filter_map(|dk| {
let mask = match dk.kind {
DepKind::Normal => 0x1,
DepKind::Dev => 0x8,
DepKind::Build => 0x40,
};
let mask = mask | mask << if is_in_workspace { 1 } else { 2 };
if mask & ignore_kinds == mask {
return None;
}
let dep = krate
.dependencies
.iter()
.find(|dep| {
if dk.kind != dep.kind {
return false;
}
// Crates can rename the dependency package themselves
let dep_name = dep.rename.as_deref().unwrap_or(&dep.name);
dep_names_match(dep_name, &rdep.name) || maybe_real_name == dep_name
})
.unwrap_or_else(|| panic!("cargo metadata resolved a dependency for a dependency not specified by the crate: {rdep:?}"));
// We also need to account for a bug in cargo, where weak
// dependencies that aren't explicitly enabled still end
// up as resolved in the graph.
// https://github.com/EmbarkStudios/krates/issues/41
// https://github.com/rust-lang/cargo/issues/10801
if dep.optional && !enabled_features
.iter()
.any(|(_feat, sub_feats)| {
sub_feats.iter().any(|sf| {
sf.kid == &rdep.pkg
})
}) {
return None;
}
let cfg = if let Some(cfg) = &dk.cfg {
if !include_all_targets {
let matched = if cfg.starts_with("cfg(") {
match cfg_expr::Expression::parse(cfg) {
Ok(expr) => {
// We only need to focus on target predicates because they are
// the only type of predicate allowed by cargo at the moment
// While it might be nicer to evaluate all the targets for each predicate
// it would lead to weird situations where an expression could evaluate to true
// (or false) with a combination of platform, that would otherwise be impossible,
// eg cfg(all(windows, target_env = "musl")) could evaluate to true
targets
.iter()
.any(|target| expr.eval(|pred| target.eval(pred)))
}
Err(_pe) => {
// TODO: maybe log a warning if we somehow fail to parse the cfg?
true
}
}
} else {
// If it's not a cfg expression, it's just a fully specified target triple,
// so we just do a string comparison
targets.iter().any(|target| target.matches_triple(cfg))
};
if !matched {
return None;
}
}
Some(cfg.clone())
} else {
None
};
Some(DependencyEdge {
kind: dk.kind,
cfg,
features: dep.features.clone(),
uses_default_features: dep.uses_default_features && has_default_feature,
})
}).collect();
// If we pruned all of the edges we can just discard the dependency altogether
if edges.is_empty() {
return None;
}
// Given the top level features enabled for the parent crate,
// determine the additional features that may be enabled for
// this dependency in addition to the features that may be
// enabled explicitly on each edge
let mut feature_stack: Vec<_> = rnode.features.iter().map(|s| s.as_str()).collect();
// Apparently features can have cycles, so we need to ensure we don't enter an
// infinite loop https://github.com/EmbarkStudios/krates/issues/48
let mut simple_features = std::collections::BTreeSet::new();
let mut features: Vec<String> = Vec::new();
while let Some(feat) = feature_stack.pop() {
// This _should_ never fail in normal cases, however if the
// `prefer-index` feature is not enabled, it's possible for
// the resolved features to mention features that aren't in
// the actual crate manifest
let fs = if let Some(fs) = krate.features.get(feat) {
fs
} else {
// TODO: Show the user a warning, or just fail?
continue;
};
for sf in fs {
let pf = ParsedFeature::from(sf.as_str());
let (krate, feature) = match pf.feat() {
Feature::Simple(feat) => {
if simple_features.insert(feat) {
feature_stack.push(feat);
}
continue;
},
Feature::Krate(_krate) => { continue; }
Feature::Strong { krate, feature } | Feature::Weak { krate, feature } => {
(krate, feature)
}
};
if !dep_names_match(krate, &rdep.name) && krate != maybe_real_name {
continue;
}
if let Err(i) = features.binary_search_by(|feat| feat.as_str().cmp(feature)) {
features.insert(i, feature.to_owned());
}
}
}
Some(KrateDependency {
pkg,
edges,
features,
})
})
.collect();
feature_edge_map.insert(pid, enabled_features);
for pid in deps.iter().map(|dep| dep.pkg) {
if !dep_edge_map.contains_key(pid) {
pid_stack.push(pid);
}
}
dep_edge_map.insert(pid, deps);
}
// Sanity check, it's possible the user could exclude all of the
// possible workspace root nodes leaving themselves with an empty graph,
// which isn't much use to anyone
if dep_edge_map.is_empty() {
return Err(Error::NoRootKrates);
}
let mut graph = petgraph::Graph::<crate::Node<N>, E>::new();
graph.reserve_nodes(dep_edge_map.len());
let mut edge_count = 0;
// Preserve the ordering of the krates when inserting them into the graph
// so that we can easily binary search for the crates based on their
// package id with just the graph and no ancillary tables
for krate in packages {
if let Some(edges) = dep_edge_map.get(&krate.id) {
let id = krate.id.clone();
// If the crate is a root then the features it has enabled are
// accurate, however if it is not a root then we need to manually
// build up the list of enabled features as each edge is added
let features = if is_root_crate(&id) {
let krate_index = nodes.binary_search_by(|n| n.id.cmp(&id)).unwrap();
let rnode = &nodes[krate_index];
rnode.features.iter().cloned().collect()
} else {
crate::EnabledFeatures::new()
};
let krate = crate::Node::Krate {
id,
krate: N::from(krate),
features,
};
graph.add_node(krate);
edge_count += edges.len();
} else {
on_filter.filtered(krate);
}
}
let krates_end = graph.node_count();
// Reserve space for each edge from a crate to another crate's feature(s)
graph.reserve_edges(edge_count);
let get = |graph: &petgraph::Graph<crate::Node<N>, E>,
kid: &Kid,
feature: Option<&str>|
-> Option<crate::NodeId> {
if let Some(feat) = feature {
graph.raw_nodes()[krates_end..]
.iter()
.enumerate()
.find_map(|(i, n)| {
if let crate::Node::Feature { krate_index, name } = &n.weight {
if let crate::Node::Krate { id, .. } = &graph[*krate_index] {
if id == kid && name == feat {
return Some(crate::NodeId::new(i + krates_end));
}
}
}
None
})
} else {
graph.raw_nodes()[..krates_end]
.iter()
.enumerate()
.find_map(|(i, n)| {
if let crate::Node::Krate { id, .. } = &n.weight {
if id == kid {
return Some(crate::NodeId::new(i));
}
}
None
})
}
};
// Now that we have all of the actual crate nodes, we can link all of the
// features exposed by each crate
let (node_count, edge_count) =
feature_edge_map
.values()
.fold((0usize, 0usize), |(nc, ec), feats| {
let nc = nc + feats.len() * 2;
let ec = ec + feats.iter().map(|(_, sf)| sf.len()).sum::<usize>();
(nc, ec)
});
graph.reserve_nodes(node_count);
graph.reserve_edges(edge_count);
// Keep edges between crates ordered as well, though we don't depend on this
for srcind in 0..graph.node_count() {
let srcid = crate::NodeId::new(srcind);
let pid = if let crate::Node::Krate { id, .. } = &graph[srcid] {
id
} else {
continue;
};
if let Some(deps) = dep_edge_map.remove(pid) {
use std::borrow::Cow;
// Attach an edge for each crate dependency, note that there might not
// actually be a target crate for the edge since crates can be pruned
// due to target configuration
for dep in deps {
let target_krate = if let Some(tk) = get(&graph, dep.pkg, None) {
tk
} else {
continue;
};
let attach = |graph: &mut petgraph::Graph<crate::Node<N>, E>,
feat: Cow<'static, str>,
edge: Edge| {
let feat_node = if let Some(feat_node) = get(graph, dep.pkg, Some(&feat)) {
feat_node
} else {
let feat_node = graph.add_node(crate::Node::Feature {
krate_index: target_krate,
name: feat.clone().into_owned(),
});
if let crate::Node::Krate { features, .. } = &mut graph[target_krate] {
if !features.contains(feat.as_ref()) {
features.insert(feat.into_owned());
}
}
feat_node
};
graph.add_edge(srcid, feat_node, edge.into());
};
// Add the features that were explicitly enabled by the specific
// normal/dev/build dependency
for edge in dep.edges {
let attach_direct_edge =
!edge.uses_default_features && edge.features.is_empty();
if edge.uses_default_features {
attach(
&mut graph,
Cow::Borrowed("default"),
Edge::DepFeature {
kind: edge.kind,
cfg: edge.cfg.clone(),
},
);
}
for feat in edge.features {
if feat != "default" {
attach(
&mut graph,
Cow::Owned(feat),
Edge::DepFeature {
kind: edge.kind,
cfg: edge.cfg.clone(),
},
);
}
}
if attach_direct_edge {
graph.add_edge(
srcid,
target_krate,
Edge::Dep {
kind: edge.kind,
cfg: edge.cfg,
}
.into(),
);
}
}
// Add the features that were toggled on via a parent crate feature
for feat in dep.features {
attach(&mut graph, Cow::Owned(feat), Edge::Feature);
}
}
}
}
// Now attach edges between all of features and their parent crate
for (pid, mut features) in feature_edge_map {
let (kind, mut feature_stack) = if let Some(kind) = get(&graph, pid, None) {
if let crate::Node::Krate { features, .. } = &graph[kind] {
(kind, features.iter().cloned().collect::<Vec<_>>())
} else {
continue;
}
} else {
continue;
};
let get_or_insert = |graph: &mut petgraph::Graph<crate::Node<N>, E>,
kid: &Kid,
feature: &str|
-> crate::NodeId {
let node_id =
graph.raw_nodes()[krates_end..]
.iter()
.enumerate()
.find_map(|(i, n)| {
if let crate::Node::Feature { krate_index, name } = &n.weight {
if let crate::Node::Krate { id, .. } = &graph[*krate_index] {
if id == kid && name == feature {
return Some(crate::NodeId::new(i + krates_end));
}
}
}
None
});
node_id.unwrap_or_else(|| {
let krate_index = get(graph, kid, None).unwrap();
graph.add_node(crate::Node::Feature {
krate_index,
name: feature.to_owned(),
})
})
};
// Since we can prune crates either by kind, target, or user specification,
// the actual set of features might not be the same as those that
// the crate thinks they were, so we use the top level features that
// have been enabled by the known edges to recursively add all of
// the sub features
while let Some(feat) = feature_stack.pop() {
let (_parent, sub_features) =
if let Some(i) = features.iter().position(|(k, _)| *k == feat) {
features.swap_remove(i)
} else {
continue;
};
let src_id = get_or_insert(&mut graph, pid, &feat);
// Also add an edge from each feature to the crate node it belongs to
graph.add_edge(src_id, kind, E::from(crate::Edge::Feature));
for sub_feat in sub_features {
if sub_feat.kid != pid && get(&graph, sub_feat.kid, None).is_none() {
//println!("skipped sub-features {sub_feat:?}, krate not in graph");
continue;
}
let feat_name = match sub_feat.name {
FeatureEdgeName::Feature(feat) => Some(feat),
FeatureEdgeName::Rename(kname) => Some(kname),
FeatureEdgeName::Krate => None,
};
let target_id =
if let Some(target_id) = get(&graph, sub_feat.kid, feat_name.as_deref()) {
target_id
} else {
let feat_name = feat_name
.unwrap_or_else(|| crate_name_from_pid(sub_feat.kid).to_owned());
let target_id = graph.add_node(crate::Node::Feature {
krate_index: kind,
name: feat_name.clone(),
});
// Ensure that all of the subfeatures enabled by the parent feature are added to the
// flat list of enabled features for the crate
if let crate::Node::Krate { features, .. } = &mut graph[kind] {
if !features.contains(&feat_name) {
features.insert(feat_name.clone());
feature_stack.push(feat_name);
}
}
target_id
};
graph.add_edge(src_id, target_id, E::from(crate::Edge::Feature));
}
}
}
Ok(Krates {
graph,
workspace_members,
lock_file: md.workspace_root.join("Cargo.lock"),
krates_end,
})
}
}
#[derive(PartialEq, Eq, Debug)]
struct DecomposedRepr<'a> {
name: &'a str,
version: &'a str,
rev: Option<&'a str>,
}
impl<'a> DecomposedRepr<'a> {
fn build(id: &'a cm::PackageId) -> Self {
let repr = &id.repr[..];
let mut riter = repr.split(' ');
let name = riter.next().unwrap();
let version = riter.next().unwrap();
let src = riter.next().unwrap();
let rev = if src.starts_with("(git+") {
src.find('#').map(|i| &src[i + 1..])
} else {
None
};
Self { name, version, rev }
}
}
/// When renaming dependencies to something with a `-` in a Cargo.toml file,
/// the actual resolved name in the metadata will replace the `-` with a `_` so
/// we need to take that into account when comparing the names as declared in
/// the crate metadata with the dependencies in the resolved graph
#[inline]
fn dep_names_match(krate_dep_name: &str, resolved_name: &str) -> bool {
if krate_dep_name.len() != resolved_name.len() {
false
} else {
krate_dep_name
.chars()
.zip(resolved_name.chars())
.all(|(kn, rn)| kn == rn || kn == '-' && rn == '_')
}
}
/// Due to <https://github.com/rust-lang/cargo/issues/11319>, we can't actually
/// trust cargo to give us the correct package metadata, so we instead use the
/// (presumably) correct data from the the index
#[cfg(feature = "prefer-index")]
fn fix_features(index: &crates_index::Index, krate: &mut cm::Package) {
if krate
.source
.as_ref()
.map_or(true, |src| !src.is_crates_io())
{
return;
}
if let Some(entry) = index.crate_(&krate.name) {
let features = entry.versions().iter().find_map(|v| {
if let Ok(iv) = v.version().parse::<semver::Version>() {
if iv == krate.version {
Some(v.features())
} else {
None
}
} else {
None
}
});
if let Some(features) = features {
for (ikey, ivalue) in features {
if !krate.features.contains_key(ikey) {
krate.features.insert(ikey.clone(), ivalue.clone());
}
}
// The index entry features might not have the `dep:<crate>`
// used with weak features if the crate version was
// published with cargo <1.60.0 version, so we need to
// manually fix that up since we depend on that format
let missing_deps: Vec<_> = krate
.features
.iter()
.flat_map(|(_, sf)| sf.iter())
.filter_map(|sf| {
let pf = ParsedFeature::from(sf.as_str());
if let Feature::Simple(simple) = pf.feat() {
if krate.features.contains_key(simple) {
None
} else {
Some(simple.to_owned())
}
} else {
None
}
})
.collect();
for missing in missing_deps {
let dep_feature = format!("dep:{missing}");
krate.features.insert(missing, vec![dep_feature]);
}
}
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn decompose_matches() {
let lock_repr = cm::PackageId {
repr: "fuser 0.4.1 (git+https://github.com/cberner/fuser?branch=master#b2e7622942e52a28ffa85cdaf48e28e982bb6923)".to_owned(),
};
let dep_repr = cm::PackageId {
repr: "fuser 0.4.1 (git+https://github.com/cberner/fuser#b2e7622942e52a28ffa85cdaf48e28e982bb6923)".to_owned(),
};
assert_eq!(
DecomposedRepr::build(&lock_repr),
DecomposedRepr::build(&dep_repr)
);
}
}