tools/crates/gnrt/lib/deps.rs - chromium/src - Git at Google

 // Copyright 2022 The Chromium Authors
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 //! Utilities to process `cargo metadata` dependency graph.

 use crate::crates::{self, Epoch};
 use crate::platforms::{self, Platform, PlatformSet};

 use std::collections::{hash_map::Entry, HashMap, HashSet};
 use std::iter;
 use std::path::PathBuf;

 pub use cargo_metadata::DependencyKind;
 pub use semver::Version;

 /// Uniquely identifies a `Package` in a particular set of dependencies. The
 /// representation is an implementation detail and may not be unique between
 /// different sets of metadata.
 pub use cargo_metadata::PackageId;

 /// A single transitive dependency of a root crate. Includes information needed
 /// for generating build files later.
 #[derive(Clone, Debug)]
 pub struct Package {
     /// Package ID in a particular set of dependencies.
     pub id: PackageId,
     /// The package name as used by cargo.
     pub package_name: String,
     /// The package version as used by cargo.
     pub version: Version,
     pub description: Option<String>,
     pub authors: Vec<String>,
     pub edition: String,
     /// This package's dependencies. Each element cross-references another
     /// `Package` by name and version.
     pub dependencies: Vec<DepOfDep>,
     /// Same as the above, but for build script deps.
     pub build_dependencies: Vec<DepOfDep>,
     /// Same as the above, but for test deps.
     pub dev_dependencies: Vec<DepOfDep>,
     /// A package can be depended upon in different ways: as a normal
     /// dependency, just for build scripts, or just for tests. `kinds` contains
     /// an entry for each way this package is depended on.
     pub dependency_kinds: HashMap<DependencyKind, PerKindInfo>,
     /// The package's lib target, or `None` if it doesn't have one.
     pub lib_target: Option<LibTarget>,
     /// List of binaries provided by the package.
     pub bin_targets: Vec<BinTarget>,
     /// The build script's absolute path, or `None` if the package does not use
     /// one.
     pub build_script: Option<PathBuf>,
     /// The path in the dependency graph to this package. This is intended for
     /// human consumption when debugging missing packages.
     pub dependency_path: Vec<String>,
     /// Whether the source is a local path. Is `false` if cargo resolved this
     /// dependency from a registry (e.g. crates.io) or git. If `false` the
     /// package may still be locally vendored through cargo configuration (see
     /// https://doc.rust-lang.org/cargo/reference/source-replacement.html)
     pub is_local: bool,
     /// Whether this package is a member of the cargo workspace the metadata
     /// came from, as opposed to a third-party dependency.
     pub is_workspace_member: bool,
 }

 impl Package {
     pub fn third_party_crate_id(&self) -> crates::ChromiumVendoredCrate {
         crates::ChromiumVendoredCrate {
             name: self.package_name.clone(),
             epoch: Epoch::from_version(&self.version),
         }
     }
 }

 /// A dependency of a `Package`. Cross-references another `Package` entry in the
 /// resolved list.
 #[derive(Clone, Debug, Eq, PartialEq)]
 pub struct DepOfDep {
     /// This dependency's package name as used by cargo.
     pub package_name: String,
     /// The name of the lib crate as `use`d by the dependent. This may be the
     /// same or different than `package_name`.
     pub use_name: String,
     /// The resolved version of this dependency.
     pub version: Version,
     /// A platform constraint for this dependency, or `None` if it's used on all
     /// platforms.
     pub platform: Option<Platform>,
 }

 impl DepOfDep {
     pub fn third_party_crate_id(&self) -> crates::ChromiumVendoredCrate {
         crates::ChromiumVendoredCrate {
             name: self.package_name.clone(),
             epoch: Epoch::from_version(&self.version),
         }
     }
 }

 /// Information specific to the dependency kind: for normal, build script, or
 /// test dependencies.
 #[derive(Clone, Debug)]
 pub struct PerKindInfo {
     /// The set of platforms this kind is needed on.
     pub platforms: PlatformSet,
     /// The resovled feature set for this kind.
     pub features: Vec<String>,
 }

 /// Description of a package's lib target.
 #[derive(Clone, Debug)]
 pub struct LibTarget {
     /// The absolute path of the lib target's `lib.rs`.
     pub root: PathBuf,
     /// The type of the lib target. This is "rlib" for normal dependencies and
     /// "proc-macro" for proc macros.
     pub lib_type: LibType,
 }

 /// A binary provided by a package.
 #[derive(Clone, Debug)]
 pub struct BinTarget {
     /// The absolute path of the binary's root source file (e.g. `main.rs`).
     pub root: PathBuf,
     /// The binary name.
     pub name: String,
 }

 /// The type of lib target. Only includes types supported by this tool.
 #[derive(Clone, Copy, Debug)]
 pub enum LibType {
     /// A normal Rust rlib library.
     Rlib,
     /// A Rust dynamic library. See
     /// https://doc.rust-lang.org/reference/linkage.html for details and the
     /// distinction between dylib and cdylib.
     Dylib,
     /// A C-compatible dynamic library. See
     /// https://doc.rust-lang.org/reference/linkage.html for details and the
     /// distinction between dylib and cdylib.
     Cdylib,
     /// A procedural macro.
     ProcMacro,
 }

 impl std::fmt::Display for LibType {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match *self {
             Self::Rlib => f.write_str("rlib"),
             Self::Dylib => f.write_str("dylib"),
             Self::Cdylib => f.write_str("cdylib"),
             Self::ProcMacro => f.write_str("proc-macro"),
         }
     }
 }

 /// Process the dependency graph in `metadata` to a flat list of transitive
 /// dependencies. Each element in the result corresponds to a cargo package. A
 /// package may have multiple crates, each of which corresponds to a single
 /// rustc invocation: e.g. a package may have a lib crate as well as multiple
 /// binary crates.
 ///
 /// `roots` optionally specifies from which packages to traverse the dependency
 /// graph (likely the root packages to generate build files for). This overrides
 /// the usual behavior, which traverses from all workspace members and the root
 /// workspace package. The package names in `roots` should still only contain
 /// workspace members.
 ///
 /// `exclude` optionally lists packages to exclude from dependency resolution.
 /// Listed packages will still be included in upstream dependency lists, but
 /// downstream dependencies will not be explored. E.g. if `bar` is listed, and
 /// `foo` -> `bar` -> `baz` is in the dependency graph, `foo` will have `bar` as
 /// a `DepOfDep` entry, but neither `bar` nor `baz` will be included in the
 /// output. The intended use-case is when build rules for certain packages must
 /// be written manually.
 pub fn collect_dependencies(
     metadata: &cargo_metadata::Metadata,
     roots: Option<Vec<String>>,
     exclude: Option<Vec<String>>,
 ) -> Vec<Package> {
     // The metadata is split into two parts:
     // 1. A list of packages and associated info: targets (e.g. lib, bin,
     //    tests), source path, etc. This includes all workspace members and all
     //    transitive dependencies. Deps are not filtered based on platform or
     //    features: it is the maximal set of dependencies.
     // 2. Resolved dependency graph. There is a node for each package pointing
     //    to its dependencies in each configuration (normal, build, dev), and
     //    the resolved feature set. This includes platform-specific info so one
     //    can filter based on target platform. Nodes include an ID that uniquely
     //    refers to a package in both (1) and (2).
     //
     // We need info from both parts. Traversing the graph tells us exactly which
     // crates are needed for a given configuration and platform. In the process,
     // we must collect package IDs then look up other data in (1).
     //
     // Note the difference between "packages" and "crates" as described in
     // https://doc.rust-lang.org/book/ch07-01-packages-and-crates.html

     // `metadata`'s structures are flattened into lists. Make it easy to index
     // by package ID.
     let dep_graph: MetadataGraph = build_graph(metadata);

     // `cargo metadata`'s resolved dependency graph.
     let resolved_graph: &cargo_metadata::Resolve = metadata.resolve.as_ref().unwrap();

     // The ID of the fake root package. Do not include it in the dependency list
     // since it is not actually built.
     let fake_root: &cargo_metadata::PackageId = resolved_graph.root.as_ref().unwrap();

     let exclude = match exclude {
         Some(exclude) => metadata
             .packages
             .iter()
             .filter_map(|pkg| if exclude.contains(&pkg.name) { Some(&pkg.id) } else { None })
             .collect(),
         None => HashSet::new(),
     };

     // `explore_node`, our recursive depth-first traversal function, needs to
     // share state between stack frames. Construct the shared state.
     let mut traversal_state = TraversalState {
         dep_graph: &dep_graph,
         root: fake_root,
         exclude,
         visited: HashSet::new(),
         path: Vec::new(),
         dependencies: HashMap::new(),
     };

     let traversal_roots: Vec<&cargo_metadata::PackageId> = match roots {
         Some(roots) => metadata
             .packages
             .iter()
             .filter_map(|pkg| if roots.contains(&pkg.name) { Some(&pkg.id) } else { None })
             .collect(),
         None => dep_graph.roots.clone(),
     };

     // Do a depth-first traversal of the graph to find all relevant
     // dependencies. Start from each workspace package ("chromium" and
     // additional binary members used in the build).
     for root_id in traversal_roots.iter() {
         let node_map: &HashMap<&cargo_metadata::PackageId, &cargo_metadata::Node> =
             &dep_graph.nodes;
         explore_node(&mut traversal_state, node_map.get(*root_id).unwrap());
     }

     // `traversal_state.dependencies` is the output of `explore_node`. Pull it
     // out for processing.
     let mut dependencies = traversal_state.dependencies;

     // Fill in the per-package data for each dependency.
     for (id, dep) in dependencies.iter_mut() {
         let node: &cargo_metadata::Node = traversal_state.dep_graph.nodes.get(id).unwrap();
         let package: &cargo_metadata::Package = traversal_state.dep_graph.packages.get(id).unwrap();

         dep.id = package.id.clone();
         dep.package_name = package.name.clone();
         dep.description = package.description.clone();
         dep.authors = package.authors.clone();
         dep.edition = package.edition.clone();

         // TODO(crbug.com/1291994): Resolve features independently per kind
         // and platform. This may require using the unstable unit-graph feature:
         // https://doc.rust-lang.org/cargo/reference/unstable.html#unit-graph
         for (_, mut kind_info) in dep.dependency_kinds.iter_mut() {
             kind_info.features = node.features.clone();
             // Remove "default" feature to match behavior of crates.py. Note
             // that this is technically not correct since a crate's code may
             // choose to check "default" directly, but virtually none actually
             // do this.
             //
             // TODO(crbug.com/1291994): Revisit this behavior and maybe keep
             // "default" features.
             if let Some(pos) = kind_info.features.iter().position(|x| x == "default") {
                 kind_info.features.remove(pos);
             }
         }

         for target in package.targets.iter() {
             let src_root = target.src_path.clone().into_std_path_buf();
             let target_type = match target.kind.iter().find_map(|s| TargetType::from_name(s)) {
                 Some(target_type) => target_type,
                 // Skip other targets, such as test, example, etc.
                 None => continue,
             };

             match target_type {
                 TargetType::Lib(lib_type) => {
                     // There can only be one lib target.
                     assert!(
                         dep.lib_target.is_none(),
                         "found duplicate lib target:\n{:?}\n{:?}",
                         dep.lib_target,
                         target
                     );
                     dep.lib_target = Some(LibTarget { root: src_root, lib_type });
                 }
                 TargetType::Bin => {
                     dep.bin_targets.push(BinTarget { root: src_root, name: target.name.clone() });
                 }
                 TargetType::BuildScript => {
                     assert_eq!(
                         dep.build_script, None,
                         "found duplicate build script target {:?}",
                         target
                     );
                     dep.build_script = Some(src_root);
                 }
             }
         }

         dep.version = package.version.clone();

         // Collect this package's list of resolved dependencies which will be
         // needed for build file generation later.
         for node_dep in iter_node_deps(node) {
             let dep_pkg = dep_graph.packages.get(node_dep.pkg).unwrap();
             let mut platform = node_dep.target;
             if let Some(p) = platform {
                 assert!(platforms::matches_supported_target(&p));
                 platform = platforms::filter_unsupported_platform_terms(p);
             }
             let dep_of_dep = DepOfDep {
                 package_name: dep_pkg.name.clone(),
                 use_name: node_dep.lib_name.to_string(),
                 version: dep_pkg.version.clone(),
                 platform,
             };

             match node_dep.kind {
                 DependencyKind::Normal => dep.dependencies.push(dep_of_dep),
                 DependencyKind::Build => dep.build_dependencies.push(dep_of_dep),
                 DependencyKind::Development => dep.dev_dependencies.push(dep_of_dep),
                 DependencyKind::Unknown => unreachable!(),
             }
         }

         // Make sure the package comes from our vendored source. If not, report
         // the error for later.
         dep.is_local = package.source == None;

         // Determine whether it's a workspace member or third-party dependency.
         dep.is_workspace_member = dep_graph.workspace_members.contains(&package.id);
     }

     // Return a flat list of dependencies.
     dependencies.into_iter().map(|(_, v)| v).collect()
 }

 /// Graph traversal state shared by recursive calls of `explore_node`.
 struct TraversalState<'a> {
     /// The graph from "cargo metadata", processed for indexing by package id.
     dep_graph: &'a MetadataGraph<'a>,
     /// The fake root package that we exclude from `dependencies`.
     root: &'a cargo_metadata::PackageId,
     /// Set of packages to exclude from traversal.
     exclude: HashSet<&'a cargo_metadata::PackageId>,
     /// Set of packages already visited by `explore_node`.
     visited: HashSet<&'a cargo_metadata::PackageId>,
     /// The path of package IDs to the current node. For human consumption.
     path: Vec<String>,
     /// The final set of dependencies.
     dependencies: HashMap<&'a cargo_metadata::PackageId, Package>,
 }

 /// Recursively explore a particular node in the dependency graph. Fills data in
 /// `state`. The final output is in `state.dependencies`.
 fn explore_node<'a>(state: &mut TraversalState<'a>, node: &'a cargo_metadata::Node) {
     // Mark the node as visited, or continue if it's already visited.
     if !state.visited.insert(&node.id) {
         return;
     }

     if state.exclude.contains(&node.id) {
         return;
     }

     // Helper to insert a placeholder `Dependency` into a map. We fill in the
     // fields later.
     let init_dep = |path| Package {
         id: PackageId { repr: String::new() },
         package_name: String::new(),
         version: Version::new(0, 0, 0),
         description: None,
         authors: Vec::new(),
         edition: String::new(),
         dependencies: Vec::new(),
         build_dependencies: Vec::new(),
         dev_dependencies: Vec::new(),
         dependency_kinds: HashMap::new(),
         lib_target: None,
         bin_targets: Vec::new(),
         build_script: None,
         dependency_path: path,
         is_local: false,
         is_workspace_member: false,
     };

     state.path.push(node.id.repr.clone());

     // Each node contains a list of enabled features plus a list of
     // dependencies. Each dependency has a platform filter if applicable.
     for dep_edge in iter_node_deps(node) {
         // Explore the target of this edge next. Note that we may visit the same
         // node multiple times, but this is OK since we'll skip it in the
         // recursive call.
         let target_node: &cargo_metadata::Node = state.dep_graph.nodes.get(&dep_edge.pkg).unwrap();
         if state.exclude.contains(&target_node.id) {
             continue;
         }

         explore_node(state, target_node);

         // Merge this with the existing entry for the dep.
         let dep: &mut Package =
             state.dependencies.entry(dep_edge.pkg).or_insert_with(|| init_dep(state.path.clone()));
         let info: &mut PerKindInfo = dep
             .dependency_kinds
             .entry(dep_edge.kind)
             .or_insert(PerKindInfo { platforms: PlatformSet::empty(), features: Vec::new() });
         info.platforms.add(dep_edge.target);
     }

     state.path.pop();

     // Initialize the dependency entry for this node's package if it's not our
     // fake root.
     if &node.id != state.root {
         state.dependencies.entry(&node.id).or_insert_with(|| init_dep(state.path.clone()));
     }
 }

 struct DependencyEdge<'a> {
     pkg: &'a cargo_metadata::PackageId,
     lib_name: &'a str,
     kind: DependencyKind,
     target: Option<Platform>,
 }

 /// Iterates over the dependencies of `node`, filtering out platforms we don't
 /// support.
 fn iter_node_deps(node: &cargo_metadata::Node) -> impl Iterator<Item = DependencyEdge<'_>> + '_ {
     node.deps
         .iter()
         .map(|node_dep| {
             // Each NodeDep has information about the package depended on, as
             // well as the kinds of dependence: as a normal, build script, or
             // test dependency. For each kind there is an optional platform
             // filter.
             //
             // Filter out kinds for unsupported platforms while mapping the
             // dependency edges to our own type.
             //
             // Cargo may also have duplicates in the dep_kinds list, which may
             // or may not be a Cargo bug, but we want to filter them out too.
             // See crbug.com/1393600.
             let mut seen = HashSet::new();
             node_dep.dep_kinds.iter().filter_map(move |dep_kind_info| {
                 // Filter if it's for a platform we don't support.
                 match &dep_kind_info.target {
                     None => (),
                     Some(platform) => {
                         if !platforms::matches_supported_target(platform) {
                             return None;
                         }
                     }
                 };

                 if seen.contains(&(&dep_kind_info.kind, &dep_kind_info.target)) {
                     return None;
                 }
                 seen.insert((&dep_kind_info.kind, &dep_kind_info.target));

                 Some(DependencyEdge {
                     pkg: &node_dep.pkg,
                     lib_name: &node_dep.name,
                     kind: dep_kind_info.kind,
                     target: dep_kind_info.target.clone(),
                 })
             })
         })
         .flatten()
 }

 /// Indexable representation of the `cargo_metadata::Metadata` fields we need.
 struct MetadataGraph<'a> {
     nodes: HashMap<&'a cargo_metadata::PackageId, &'a cargo_metadata::Node>,
     packages: HashMap<&'a cargo_metadata::PackageId, &'a cargo_metadata::Package>,
     workspace_members: HashSet<&'a cargo_metadata::PackageId>,
     roots: Vec<&'a cargo_metadata::PackageId>,
 }

 /// Convert the flat lists in `metadata` to maps indexable by PackageId.
 fn build_graph<'a>(metadata: &'a cargo_metadata::Metadata) -> MetadataGraph<'a> {
     // `metadata` always has `resolve` unless cargo was explicitly asked not to
     // output the dependency graph.
     let resolve = metadata.resolve.as_ref().unwrap();
     let mut graph = HashMap::new();
     for node in resolve.nodes.iter() {
         match graph.entry(&node.id) {
             Entry::Vacant(e) => e.insert(node),
             Entry::Occupied(_) => panic!("duplicate entries in dependency graph"),
         };
     }

     let packages = metadata.packages.iter().map(|p| (&p.id, p)).collect();

     let roots = iter::once(resolve.root.as_ref().unwrap())
         .chain(metadata.workspace_members.iter())
         .collect();

     MetadataGraph {
         nodes: graph,
         packages,
         workspace_members: metadata.workspace_members.iter().collect(),
         roots,
     }
 }

 /// A crate target type we support.
 #[derive(Clone, Copy, Debug)]
 enum TargetType {
     Lib(LibType),
     Bin,
     BuildScript,
 }

 impl TargetType {
     fn from_name(name: &str) -> Option<Self> {
         match name {
             "lib" | "rlib" => Some(Self::Lib(LibType::Rlib)),
             "dylib" => Some(Self::Lib(LibType::Dylib)),
             "cdylib" => Some(Self::Lib(LibType::Cdylib)),
             "bin" => Some(Self::Bin),
             "custom-build" => Some(Self::BuildScript),
             "proc-macro" => Some(Self::Lib(LibType::ProcMacro)),
             _ => None,
         }
     }
 }

 impl std::fmt::Display for TargetType {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match *self {
             Self::Lib(typ) => typ.fmt(f),
             Self::Bin => f.write_str("bin"),
             Self::BuildScript => f.write_str("custom-build"),
         }
     }
 }
	// Copyright 2022 The Chromium Authors
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	//! Utilities to process `cargo metadata` dependency graph.

	use crate::crates::{self, Epoch};
	use crate::platforms::{self, Platform, PlatformSet};

	use std::collections::{hash_map::Entry, HashMap, HashSet};
	use std::iter;
	use std::path::PathBuf;

	pub use cargo_metadata::DependencyKind;
	pub use semver::Version;

	/// Uniquely identifies a `Package` in a particular set of dependencies. The
	/// representation is an implementation detail and may not be unique between
	/// different sets of metadata.
	pub use cargo_metadata::PackageId;

	/// A single transitive dependency of a root crate. Includes information needed
	/// for generating build files later.
	#[derive(Clone, Debug)]
	pub struct Package {
	/// Package ID in a particular set of dependencies.
	pub id: PackageId,
	/// The package name as used by cargo.
	pub package_name: String,
	/// The package version as used by cargo.
	pub version: Version,
	pub description: Option<String>,
	pub authors: Vec<String>,
	pub edition: String,
	/// This package's dependencies. Each element cross-references another
	/// `Package` by name and version.
	pub dependencies: Vec<DepOfDep>,
	/// Same as the above, but for build script deps.
	pub build_dependencies: Vec<DepOfDep>,
	/// Same as the above, but for test deps.
	pub dev_dependencies: Vec<DepOfDep>,
	/// A package can be depended upon in different ways: as a normal
	/// dependency, just for build scripts, or just for tests. `kinds` contains
	/// an entry for each way this package is depended on.
	pub dependency_kinds: HashMap<DependencyKind, PerKindInfo>,
	/// The package's lib target, or `None` if it doesn't have one.
	pub lib_target: Option<LibTarget>,
	/// List of binaries provided by the package.
	pub bin_targets: Vec<BinTarget>,
	/// The build script's absolute path, or `None` if the package does not use
	/// one.
	pub build_script: Option<PathBuf>,
	/// The path in the dependency graph to this package. This is intended for
	/// human consumption when debugging missing packages.
	pub dependency_path: Vec<String>,
	/// Whether the source is a local path. Is `false` if cargo resolved this
	/// dependency from a registry (e.g. crates.io) or git. If `false` the
	/// package may still be locally vendored through cargo configuration (see
	/// https://doc.rust-lang.org/cargo/reference/source-replacement.html)
	pub is_local: bool,
	/// Whether this package is a member of the cargo workspace the metadata
	/// came from, as opposed to a third-party dependency.
	pub is_workspace_member: bool,
	}

	impl Package {
	pub fn third_party_crate_id(&self) -> crates::ChromiumVendoredCrate {
	crates::ChromiumVendoredCrate {
	name: self.package_name.clone(),
	epoch: Epoch::from_version(&self.version),
	}
	}
	}

	/// A dependency of a `Package`. Cross-references another `Package` entry in the
	/// resolved list.
	#[derive(Clone, Debug, Eq, PartialEq)]
	pub struct DepOfDep {
	/// This dependency's package name as used by cargo.
	pub package_name: String,
	/// The name of the lib crate as `use`d by the dependent. This may be the
	/// same or different than `package_name`.
	pub use_name: String,
	/// The resolved version of this dependency.
	pub version: Version,
	/// A platform constraint for this dependency, or `None` if it's used on all
	/// platforms.
	pub platform: Option<Platform>,
	}

	impl DepOfDep {
	pub fn third_party_crate_id(&self) -> crates::ChromiumVendoredCrate {
	crates::ChromiumVendoredCrate {
	name: self.package_name.clone(),
	epoch: Epoch::from_version(&self.version),
	}
	}
	}

	/// Information specific to the dependency kind: for normal, build script, or
	/// test dependencies.
	#[derive(Clone, Debug)]
	pub struct PerKindInfo {
	/// The set of platforms this kind is needed on.
	pub platforms: PlatformSet,
	/// The resovled feature set for this kind.
	pub features: Vec<String>,
	}

	/// Description of a package's lib target.
	#[derive(Clone, Debug)]
	pub struct LibTarget {
	/// The absolute path of the lib target's `lib.rs`.
	pub root: PathBuf,
	/// The type of the lib target. This is "rlib" for normal dependencies and
	/// "proc-macro" for proc macros.
	pub lib_type: LibType,
	}

	/// A binary provided by a package.
	#[derive(Clone, Debug)]
	pub struct BinTarget {
	/// The absolute path of the binary's root source file (e.g. `main.rs`).
	pub root: PathBuf,
	/// The binary name.
	pub name: String,
	}

	/// The type of lib target. Only includes types supported by this tool.
	#[derive(Clone, Copy, Debug)]
	pub enum LibType {
	/// A normal Rust rlib library.
	Rlib,
	/// A Rust dynamic library. See
	/// https://doc.rust-lang.org/reference/linkage.html for details and the
	/// distinction between dylib and cdylib.
	Dylib,
	/// A C-compatible dynamic library. See
	/// https://doc.rust-lang.org/reference/linkage.html for details and the
	/// distinction between dylib and cdylib.
	Cdylib,
	/// A procedural macro.
	ProcMacro,
	}

	impl std::fmt::Display for LibType {
	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
	match *self {
	Self::Rlib => f.write_str("rlib"),
	Self::Dylib => f.write_str("dylib"),
	Self::Cdylib => f.write_str("cdylib"),
	Self::ProcMacro => f.write_str("proc-macro"),
	}
	}
	}

	/// Process the dependency graph in `metadata` to a flat list of transitive
	/// dependencies. Each element in the result corresponds to a cargo package. A
	/// package may have multiple crates, each of which corresponds to a single
	/// rustc invocation: e.g. a package may have a lib crate as well as multiple
	/// binary crates.
	///
	/// `roots` optionally specifies from which packages to traverse the dependency
	/// graph (likely the root packages to generate build files for). This overrides
	/// the usual behavior, which traverses from all workspace members and the root
	/// workspace package. The package names in `roots` should still only contain
	/// workspace members.
	///
	/// `exclude` optionally lists packages to exclude from dependency resolution.
	/// Listed packages will still be included in upstream dependency lists, but
	/// downstream dependencies will not be explored. E.g. if `bar` is listed, and
	/// `foo` -> `bar` -> `baz` is in the dependency graph, `foo` will have `bar` as
	/// a `DepOfDep` entry, but neither `bar` nor `baz` will be included in the
	/// output. The intended use-case is when build rules for certain packages must
	/// be written manually.
	pub fn collect_dependencies(
	metadata: &cargo_metadata::Metadata,
	roots: Option<Vec<String>>,
	exclude: Option<Vec<String>>,
	) -> Vec<Package> {
	// The metadata is split into two parts:
	// 1. A list of packages and associated info: targets (e.g. lib, bin,
	// tests), source path, etc. This includes all workspace members and all
	// transitive dependencies. Deps are not filtered based on platform or
	// features: it is the maximal set of dependencies.
	// 2. Resolved dependency graph. There is a node for each package pointing
	// to its dependencies in each configuration (normal, build, dev), and
	// the resolved feature set. This includes platform-specific info so one
	// can filter based on target platform. Nodes include an ID that uniquely
	// refers to a package in both (1) and (2).
	//
	// We need info from both parts. Traversing the graph tells us exactly which
	// crates are needed for a given configuration and platform. In the process,
	// we must collect package IDs then look up other data in (1).
	//
	// Note the difference between "packages" and "crates" as described in
	// https://doc.rust-lang.org/book/ch07-01-packages-and-crates.html

	// `metadata`'s structures are flattened into lists. Make it easy to index
	// by package ID.
	let dep_graph: MetadataGraph = build_graph(metadata);

	// `cargo metadata`'s resolved dependency graph.
	let resolved_graph: &cargo_metadata::Resolve = metadata.resolve.as_ref().unwrap();

	// The ID of the fake root package. Do not include it in the dependency list
	// since it is not actually built.
	let fake_root: &cargo_metadata::PackageId = resolved_graph.root.as_ref().unwrap();

	let exclude = match exclude {
	Some(exclude) => metadata
	.packages
	.iter()
	.filter_map(\|pkg\| if exclude.contains(&pkg.name) { Some(&pkg.id) } else { None })
	.collect(),
	None => HashSet::new(),
	};

	// `explore_node`, our recursive depth-first traversal function, needs to
	// share state between stack frames. Construct the shared state.
	let mut traversal_state = TraversalState {
	dep_graph: &dep_graph,
	root: fake_root,
	exclude,
	visited: HashSet::new(),
	path: Vec::new(),
	dependencies: HashMap::new(),
	};

	let traversal_roots: Vec<&cargo_metadata::PackageId> = match roots {
	Some(roots) => metadata
	.packages
	.iter()
	.filter_map(\|pkg\| if roots.contains(&pkg.name) { Some(&pkg.id) } else { None })
	.collect(),
	None => dep_graph.roots.clone(),
	};

	// Do a depth-first traversal of the graph to find all relevant
	// dependencies. Start from each workspace package ("chromium" and
	// additional binary members used in the build).
	for root_id in traversal_roots.iter() {
	let node_map: &HashMap<&cargo_metadata::PackageId, &cargo_metadata::Node> =
	&dep_graph.nodes;
	explore_node(&mut traversal_state, node_map.get(*root_id).unwrap());
	}

	// `traversal_state.dependencies` is the output of `explore_node`. Pull it
	// out for processing.
	let mut dependencies = traversal_state.dependencies;

	// Fill in the per-package data for each dependency.
	for (id, dep) in dependencies.iter_mut() {
	let node: &cargo_metadata::Node = traversal_state.dep_graph.nodes.get(id).unwrap();
	let package: &cargo_metadata::Package = traversal_state.dep_graph.packages.get(id).unwrap();

	dep.id = package.id.clone();
	dep.package_name = package.name.clone();
	dep.description = package.description.clone();
	dep.authors = package.authors.clone();
	dep.edition = package.edition.clone();

	// TODO(crbug.com/1291994): Resolve features independently per kind
	// and platform. This may require using the unstable unit-graph feature:
	// https://doc.rust-lang.org/cargo/reference/unstable.html#unit-graph
	for (_, mut kind_info) in dep.dependency_kinds.iter_mut() {
	kind_info.features = node.features.clone();
	// Remove "default" feature to match behavior of crates.py. Note
	// that this is technically not correct since a crate's code may
	// choose to check "default" directly, but virtually none actually
	// do this.
	//
	// TODO(crbug.com/1291994): Revisit this behavior and maybe keep
	// "default" features.
	if let Some(pos) = kind_info.features.iter().position(\|x\| x == "default") {
	kind_info.features.remove(pos);
	}
	}

	for target in package.targets.iter() {
	let src_root = target.src_path.clone().into_std_path_buf();
	let target_type = match target.kind.iter().find_map(\|s\| TargetType::from_name(s)) {
	Some(target_type) => target_type,
	// Skip other targets, such as test, example, etc.
	None => continue,
	};

	match target_type {
	TargetType::Lib(lib_type) => {
	// There can only be one lib target.
	assert!(
	dep.lib_target.is_none(),
	"found duplicate lib target:\n{:?}\n{:?}",
	dep.lib_target,
	target
	);
	dep.lib_target = Some(LibTarget { root: src_root, lib_type });
	}
	TargetType::Bin => {
	dep.bin_targets.push(BinTarget { root: src_root, name: target.name.clone() });
	}
	TargetType::BuildScript => {
	assert_eq!(
	dep.build_script, None,
	"found duplicate build script target {:?}",
	target
	);
	dep.build_script = Some(src_root);
	}
	}
	}

	dep.version = package.version.clone();

	// Collect this package's list of resolved dependencies which will be
	// needed for build file generation later.
	for node_dep in iter_node_deps(node) {
	let dep_pkg = dep_graph.packages.get(node_dep.pkg).unwrap();
	let mut platform = node_dep.target;
	if let Some(p) = platform {
	assert!(platforms::matches_supported_target(&p));
	platform = platforms::filter_unsupported_platform_terms(p);
	}
	let dep_of_dep = DepOfDep {
	package_name: dep_pkg.name.clone(),
	use_name: node_dep.lib_name.to_string(),
	version: dep_pkg.version.clone(),
	platform,
	};

	match node_dep.kind {
	DependencyKind::Normal => dep.dependencies.push(dep_of_dep),
	DependencyKind::Build => dep.build_dependencies.push(dep_of_dep),
	DependencyKind::Development => dep.dev_dependencies.push(dep_of_dep),
	DependencyKind::Unknown => unreachable!(),
	}
	}

	// Make sure the package comes from our vendored source. If not, report
	// the error for later.
	dep.is_local = package.source == None;

	// Determine whether it's a workspace member or third-party dependency.
	dep.is_workspace_member = dep_graph.workspace_members.contains(&package.id);
	}

	// Return a flat list of dependencies.
	dependencies.into_iter().map(\|(_, v)\| v).collect()
	}

	/// Graph traversal state shared by recursive calls of `explore_node`.
	struct TraversalState<'a> {
	/// The graph from "cargo metadata", processed for indexing by package id.
	dep_graph: &'a MetadataGraph<'a>,
	/// The fake root package that we exclude from `dependencies`.
	root: &'a cargo_metadata::PackageId,
	/// Set of packages to exclude from traversal.
	exclude: HashSet<&'a cargo_metadata::PackageId>,
	/// Set of packages already visited by `explore_node`.
	visited: HashSet<&'a cargo_metadata::PackageId>,
	/// The path of package IDs to the current node. For human consumption.
	path: Vec<String>,
	/// The final set of dependencies.
	dependencies: HashMap<&'a cargo_metadata::PackageId, Package>,
	}

	/// Recursively explore a particular node in the dependency graph. Fills data in
	/// `state`. The final output is in `state.dependencies`.
	fn explore_node<'a>(state: &mut TraversalState<'a>, node: &'a cargo_metadata::Node) {
	// Mark the node as visited, or continue if it's already visited.
	if !state.visited.insert(&node.id) {
	return;
	}

	if state.exclude.contains(&node.id) {
	return;
	}

	// Helper to insert a placeholder `Dependency` into a map. We fill in the
	// fields later.
	let init_dep = \|path\| Package {
	id: PackageId { repr: String::new() },
	package_name: String::new(),
	version: Version::new(0, 0, 0),
	description: None,
	authors: Vec::new(),
	edition: String::new(),
	dependencies: Vec::new(),
	build_dependencies: Vec::new(),
	dev_dependencies: Vec::new(),
	dependency_kinds: HashMap::new(),
	lib_target: None,
	bin_targets: Vec::new(),
	build_script: None,
	dependency_path: path,
	is_local: false,
	is_workspace_member: false,
	};

	state.path.push(node.id.repr.clone());

	// Each node contains a list of enabled features plus a list of
	// dependencies. Each dependency has a platform filter if applicable.
	for dep_edge in iter_node_deps(node) {
	// Explore the target of this edge next. Note that we may visit the same
	// node multiple times, but this is OK since we'll skip it in the
	// recursive call.
	let target_node: &cargo_metadata::Node = state.dep_graph.nodes.get(&dep_edge.pkg).unwrap();
	if state.exclude.contains(&target_node.id) {
	continue;
	}

	explore_node(state, target_node);

	// Merge this with the existing entry for the dep.
	let dep: &mut Package =
	state.dependencies.entry(dep_edge.pkg).or_insert_with(\|\| init_dep(state.path.clone()));
	let info: &mut PerKindInfo = dep
	.dependency_kinds
	.entry(dep_edge.kind)
	.or_insert(PerKindInfo { platforms: PlatformSet::empty(), features: Vec::new() });
	info.platforms.add(dep_edge.target);
	}

	state.path.pop();

	// Initialize the dependency entry for this node's package if it's not our
	// fake root.
	if &node.id != state.root {
	state.dependencies.entry(&node.id).or_insert_with(\|\| init_dep(state.path.clone()));
	}
	}

	struct DependencyEdge<'a> {
	pkg: &'a cargo_metadata::PackageId,
	lib_name: &'a str,
	kind: DependencyKind,
	target: Option<Platform>,
	}

	/// Iterates over the dependencies of `node`, filtering out platforms we don't
	/// support.
	fn iter_node_deps(node: &cargo_metadata::Node) -> impl Iterator<Item = DependencyEdge<'_>> + '_ {
	node.deps
	.iter()
	.map(\|node_dep\| {
	// Each NodeDep has information about the package depended on, as
	// well as the kinds of dependence: as a normal, build script, or
	// test dependency. For each kind there is an optional platform
	// filter.
	//
	// Filter out kinds for unsupported platforms while mapping the
	// dependency edges to our own type.
	//
	// Cargo may also have duplicates in the dep_kinds list, which may
	// or may not be a Cargo bug, but we want to filter them out too.
	// See crbug.com/1393600.
	let mut seen = HashSet::new();
	node_dep.dep_kinds.iter().filter_map(move \|dep_kind_info\| {
	// Filter if it's for a platform we don't support.
	match &dep_kind_info.target {
	None => (),
	Some(platform) => {
	if !platforms::matches_supported_target(platform) {
	return None;
	}
	}
	};

	if seen.contains(&(&dep_kind_info.kind, &dep_kind_info.target)) {
	return None;
	}
	seen.insert((&dep_kind_info.kind, &dep_kind_info.target));

	Some(DependencyEdge {
	pkg: &node_dep.pkg,
	lib_name: &node_dep.name,
	kind: dep_kind_info.kind,
	target: dep_kind_info.target.clone(),
	})
	})
	})
	.flatten()
	}

	/// Indexable representation of the `cargo_metadata::Metadata` fields we need.
	struct MetadataGraph<'a> {
	nodes: HashMap<&'a cargo_metadata::PackageId, &'a cargo_metadata::Node>,
	packages: HashMap<&'a cargo_metadata::PackageId, &'a cargo_metadata::Package>,
	workspace_members: HashSet<&'a cargo_metadata::PackageId>,
	roots: Vec<&'a cargo_metadata::PackageId>,
	}

	/// Convert the flat lists in `metadata` to maps indexable by PackageId.
	fn build_graph<'a>(metadata: &'a cargo_metadata::Metadata) -> MetadataGraph<'a> {
	// `metadata` always has `resolve` unless cargo was explicitly asked not to
	// output the dependency graph.
	let resolve = metadata.resolve.as_ref().unwrap();
	let mut graph = HashMap::new();
	for node in resolve.nodes.iter() {
	match graph.entry(&node.id) {
	Entry::Vacant(e) => e.insert(node),
	Entry::Occupied(_) => panic!("duplicate entries in dependency graph"),
	};
	}

	let packages = metadata.packages.iter().map(\|p\| (&p.id, p)).collect();

	let roots = iter::once(resolve.root.as_ref().unwrap())
	.chain(metadata.workspace_members.iter())
	.collect();

	MetadataGraph {
	nodes: graph,
	packages,
	workspace_members: metadata.workspace_members.iter().collect(),
	roots,
	}
	}

	/// A crate target type we support.
	#[derive(Clone, Copy, Debug)]
	enum TargetType {
	Lib(LibType),
	Bin,
	BuildScript,
	}

	impl TargetType {
	fn from_name(name: &str) -> Option<Self> {
	match name {
	"lib" \| "rlib" => Some(Self::Lib(LibType::Rlib)),
	"dylib" => Some(Self::Lib(LibType::Dylib)),
	"cdylib" => Some(Self::Lib(LibType::Cdylib)),
	"bin" => Some(Self::Bin),
	"custom-build" => Some(Self::BuildScript),
	"proc-macro" => Some(Self::Lib(LibType::ProcMacro)),
	_ => None,
	}
	}
	}

	impl std::fmt::Display for TargetType {
	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
	match *self {
	Self::Lib(typ) => typ.fmt(f),
	Self::Bin => f.write_str("bin"),
	Self::BuildScript => f.write_str("custom-build"),
	}
	}
	}