summaryrefslogtreecommitdiff
path: root/cli/npm/resolution
diff options
context:
space:
mode:
Diffstat (limited to 'cli/npm/resolution')
-rw-r--r--cli/npm/resolution/graph.rs47
-rw-r--r--cli/npm/resolution/mod.rs220
-rw-r--r--cli/npm/resolution/snapshot.rs32
-rw-r--r--cli/npm/resolution/specifier.rs666
4 files changed, 252 insertions, 713 deletions
diff --git a/cli/npm/resolution/graph.rs b/cli/npm/resolution/graph.rs
index 966e1f010..87579dad3 100644
--- a/cli/npm/resolution/graph.rs
+++ b/cli/npm/resolution/graph.rs
@@ -159,6 +159,9 @@ impl ResolvedNodeIds {
}
}
+// todo(dsherret): for some reason the lsp errors when using an Rc<RefCell<NodeId>> here
+// instead of an Arc<Mutex<NodeId>>. We should investigate and fix.
+
/// A pointer to a specific node in a graph path. The underlying node id
/// may change as peer dependencies are created.
#[derive(Clone, Debug)]
@@ -297,6 +300,8 @@ pub struct Graph {
// This will be set when creating from a snapshot, then
// inform the final snapshot creation.
packages_to_copy_index: HashMap<NpmPackageId, usize>,
+ /// Packages that the resolver should resolve first.
+ pending_unresolved_packages: Vec<NpmPackageNv>,
}
impl Graph {
@@ -359,6 +364,7 @@ impl Graph {
.map(|(id, p)| (id.clone(), p.copy_index))
.collect(),
package_reqs: snapshot.package_reqs,
+ pending_unresolved_packages: snapshot.pending_unresolved_packages,
..Default::default()
};
let mut created_package_ids =
@@ -375,10 +381,18 @@ impl Graph {
Ok(graph)
}
+ pub fn take_pending_unresolved(&mut self) -> Vec<NpmPackageNv> {
+ std::mem::take(&mut self.pending_unresolved_packages)
+ }
+
pub fn has_package_req(&self, req: &NpmPackageReq) -> bool {
self.package_reqs.contains_key(req)
}
+ pub fn has_root_package(&self, id: &NpmPackageNv) -> bool {
+ self.root_packages.contains_key(id)
+ }
+
fn get_npm_pkg_id(&self, node_id: NodeId) -> NpmPackageId {
let resolved_id = self.resolved_node_ids.get(node_id).unwrap();
self.get_npm_pkg_id_from_resolved_id(resolved_id, HashSet::new())
@@ -596,6 +610,7 @@ impl Graph {
.collect(),
packages,
package_reqs: self.package_reqs,
+ pending_unresolved_packages: self.pending_unresolved_packages,
})
}
@@ -714,11 +729,43 @@ impl<'a> GraphDependencyResolver<'a> {
}
}
+ pub fn add_root_package(
+ &mut self,
+ package_nv: &NpmPackageNv,
+ package_info: &NpmPackageInfo,
+ ) -> Result<(), AnyError> {
+ if self.graph.root_packages.contains_key(package_nv) {
+ return Ok(()); // already added
+ }
+
+ // todo(dsherret): using a version requirement here is a temporary hack
+ // to reuse code in a large refactor. We should resolve the node directly
+ // from the package name and version
+ let version_req =
+ VersionReq::parse_from_specifier(&format!("{}", package_nv.version))
+ .unwrap();
+ let (pkg_id, node_id) = self.resolve_node_from_info(
+ &package_nv.name,
+ &version_req,
+ package_info,
+ None,
+ )?;
+ self.graph.root_packages.insert(pkg_id.clone(), node_id);
+ self
+ .pending_unresolved_nodes
+ .push_back(GraphPath::for_root(node_id, pkg_id));
+ Ok(())
+ }
+
pub fn add_package_req(
&mut self,
package_req: &NpmPackageReq,
package_info: &NpmPackageInfo,
) -> Result<(), AnyError> {
+ if self.graph.package_reqs.contains_key(package_req) {
+ return Ok(()); // already added
+ }
+
let (pkg_id, node_id) = self.resolve_node_from_info(
&package_req.name,
package_req
diff --git a/cli/npm/resolution/mod.rs b/cli/npm/resolution/mod.rs
index c95124b61..8584958b5 100644
--- a/cli/npm/resolution/mod.rs
+++ b/cli/npm/resolution/mod.rs
@@ -4,19 +4,26 @@ use std::cmp::Ordering;
use std::collections::BTreeMap;
use std::collections::HashMap;
use std::collections::HashSet;
+use std::sync::Arc;
use deno_core::anyhow::Context;
use deno_core::error::AnyError;
+use deno_core::parking_lot::Mutex;
use deno_core::parking_lot::RwLock;
use deno_graph::npm::NpmPackageNv;
+use deno_graph::npm::NpmPackageNvReference;
use deno_graph::npm::NpmPackageReq;
+use deno_graph::npm::NpmPackageReqReference;
use deno_graph::semver::Version;
+use log::debug;
use serde::Deserialize;
use serde::Serialize;
use thiserror::Error;
use crate::args::Lockfile;
+use crate::npm::resolution::common::LATEST_VERSION_REQ;
+use self::common::resolve_best_package_version_and_info;
use self::graph::GraphDependencyResolver;
use self::snapshot::NpmPackagesPartitioned;
@@ -27,11 +34,9 @@ use super::registry::NpmRegistryApi;
mod common;
mod graph;
mod snapshot;
-mod specifier;
use graph::Graph;
pub use snapshot::NpmResolutionSnapshot;
-pub use specifier::resolve_graph_npm_info;
#[derive(Debug, Error)]
#[error("Invalid npm package id '{text}'. {message}")]
@@ -230,15 +235,19 @@ impl NpmResolutionPackage {
}
}
-pub struct NpmResolution {
+#[derive(Clone)]
+pub struct NpmResolution(Arc<NpmResolutionInner>);
+
+struct NpmResolutionInner {
api: NpmRegistryApi,
snapshot: RwLock<NpmResolutionSnapshot>,
update_semaphore: tokio::sync::Semaphore,
+ maybe_lockfile: Option<Arc<Mutex<Lockfile>>>,
}
impl std::fmt::Debug for NpmResolution {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
- let snapshot = self.snapshot.read();
+ let snapshot = self.0.snapshot.read();
f.debug_struct("NpmResolution")
.field("snapshot", &snapshot)
.finish()
@@ -249,26 +258,35 @@ impl NpmResolution {
pub fn new(
api: NpmRegistryApi,
initial_snapshot: Option<NpmResolutionSnapshot>,
+ maybe_lockfile: Option<Arc<Mutex<Lockfile>>>,
) -> Self {
- Self {
+ Self(Arc::new(NpmResolutionInner {
api,
snapshot: RwLock::new(initial_snapshot.unwrap_or_default()),
update_semaphore: tokio::sync::Semaphore::new(1),
- }
+ maybe_lockfile,
+ }))
}
pub async fn add_package_reqs(
&self,
package_reqs: Vec<NpmPackageReq>,
) -> Result<(), AnyError> {
+ let inner = &self.0;
+
// only allow one thread in here at a time
- let _permit = self.update_semaphore.acquire().await?;
- let snapshot = self.snapshot.read().clone();
+ let _permit = inner.update_semaphore.acquire().await?;
+ let snapshot = inner.snapshot.read().clone();
- let snapshot =
- add_package_reqs_to_snapshot(&self.api, package_reqs, snapshot).await?;
+ let snapshot = add_package_reqs_to_snapshot(
+ &inner.api,
+ package_reqs,
+ snapshot,
+ self.0.maybe_lockfile.clone(),
+ )
+ .await?;
- *self.snapshot.write() = snapshot;
+ *inner.snapshot.write() = snapshot;
Ok(())
}
@@ -276,9 +294,10 @@ impl NpmResolution {
&self,
package_reqs: HashSet<NpmPackageReq>,
) -> Result<(), AnyError> {
+ let inner = &self.0;
// only allow one thread in here at a time
- let _permit = self.update_semaphore.acquire().await?;
- let snapshot = self.snapshot.read().clone();
+ let _permit = inner.update_semaphore.acquire().await?;
+ let snapshot = inner.snapshot.read().clone();
let has_removed_package = !snapshot
.package_reqs
@@ -291,22 +310,46 @@ impl NpmResolution {
snapshot
};
let snapshot = add_package_reqs_to_snapshot(
- &self.api,
+ &inner.api,
package_reqs.into_iter().collect(),
snapshot,
+ self.0.maybe_lockfile.clone(),
)
.await?;
- *self.snapshot.write() = snapshot;
+ *inner.snapshot.write() = snapshot;
Ok(())
}
- pub fn resolve_package_from_id(
+ pub async fn resolve_pending(&self) -> Result<(), AnyError> {
+ let inner = &self.0;
+ // only allow one thread in here at a time
+ let _permit = inner.update_semaphore.acquire().await?;
+ let snapshot = inner.snapshot.read().clone();
+
+ let snapshot = add_package_reqs_to_snapshot(
+ &inner.api,
+ Vec::new(),
+ snapshot,
+ self.0.maybe_lockfile.clone(),
+ )
+ .await?;
+
+ *inner.snapshot.write() = snapshot;
+
+ Ok(())
+ }
+
+ pub fn pkg_req_ref_to_nv_ref(
&self,
- id: &NpmPackageId,
- ) -> Option<NpmResolutionPackage> {
- self.snapshot.read().package_from_id(id).cloned()
+ req_ref: NpmPackageReqReference,
+ ) -> Result<NpmPackageNvReference, AnyError> {
+ let node_id = self.resolve_pkg_id_from_pkg_req(&req_ref.req)?;
+ Ok(NpmPackageNvReference {
+ nv: node_id.nv,
+ sub_path: req_ref.sub_path,
+ })
}
pub fn resolve_package_cache_folder_id_from_id(
@@ -314,6 +357,7 @@ impl NpmResolution {
id: &NpmPackageId,
) -> Option<NpmPackageCacheFolderId> {
self
+ .0
.snapshot
.read()
.package_from_id(id)
@@ -326,6 +370,7 @@ impl NpmResolution {
referrer: &NpmPackageCacheFolderId,
) -> Result<NpmResolutionPackage, AnyError> {
self
+ .0
.snapshot
.read()
.resolve_package_from_package(name, referrer)
@@ -333,36 +378,100 @@ impl NpmResolution {
}
/// Resolve a node package from a deno module.
- pub fn resolve_package_from_deno_module(
+ pub fn resolve_pkg_id_from_pkg_req(
&self,
- package: &NpmPackageReq,
- ) -> Result<NpmResolutionPackage, AnyError> {
+ req: &NpmPackageReq,
+ ) -> Result<NpmPackageId, AnyError> {
self
+ .0
.snapshot
.read()
- .resolve_package_from_deno_module(package)
- .cloned()
+ .resolve_pkg_from_pkg_req(req)
+ .map(|pkg| pkg.pkg_id.clone())
+ }
+
+ pub fn resolve_pkg_id_from_deno_module(
+ &self,
+ id: &NpmPackageNv,
+ ) -> Result<NpmPackageId, AnyError> {
+ self
+ .0
+ .snapshot
+ .read()
+ .resolve_package_from_deno_module(id)
+ .map(|pkg| pkg.pkg_id.clone())
+ }
+
+ /// Resolves a package requirement for deno graph. This should only be
+ /// called by deno_graph's NpmResolver.
+ pub fn resolve_package_req_for_deno_graph(
+ &self,
+ pkg_req: &NpmPackageReq,
+ ) -> Result<NpmPackageNv, AnyError> {
+ let inner = &self.0;
+ // we should always have this because it should have been cached before here
+ let package_info =
+ inner.api.get_cached_package_info(&pkg_req.name).unwrap();
+
+ let mut snapshot = inner.snapshot.write();
+ let version_req =
+ pkg_req.version_req.as_ref().unwrap_or(&*LATEST_VERSION_REQ);
+ let version_and_info =
+ match snapshot.packages_by_name.get(&package_info.name) {
+ Some(existing_versions) => resolve_best_package_version_and_info(
+ version_req,
+ &package_info,
+ existing_versions.iter().map(|p| &p.nv.version),
+ )?,
+ None => resolve_best_package_version_and_info(
+ version_req,
+ &package_info,
+ Vec::new().iter(),
+ )?,
+ };
+ let id = NpmPackageNv {
+ name: package_info.name.to_string(),
+ version: version_and_info.version,
+ };
+ debug!(
+ "Resolved {}@{} to {}",
+ pkg_req.name,
+ version_req.version_text(),
+ id.to_string(),
+ );
+ snapshot.package_reqs.insert(pkg_req.clone(), id.clone());
+ let packages_with_name = snapshot
+ .packages_by_name
+ .entry(package_info.name.clone())
+ .or_default();
+ if !packages_with_name.iter().any(|p| p.nv == id) {
+ packages_with_name.push(NpmPackageId {
+ nv: id.clone(),
+ peer_dependencies: Vec::new(),
+ });
+ }
+ snapshot.pending_unresolved_packages.push(id.clone());
+ Ok(id)
}
pub fn all_packages_partitioned(&self) -> NpmPackagesPartitioned {
- self.snapshot.read().all_packages_partitioned()
+ self.0.snapshot.read().all_packages_partitioned()
}
pub fn has_packages(&self) -> bool {
- !self.snapshot.read().packages.is_empty()
+ !self.0.snapshot.read().packages.is_empty()
}
pub fn snapshot(&self) -> NpmResolutionSnapshot {
- self.snapshot.read().clone()
+ self.0.snapshot.read().clone()
}
pub fn lock(&self, lockfile: &mut Lockfile) -> Result<(), AnyError> {
- let snapshot = self.snapshot.read();
+ let snapshot = self.0.snapshot.read();
for (package_req, nv) in snapshot.package_reqs.iter() {
- let package_id = snapshot.root_packages.get(nv).unwrap();
lockfile.insert_npm_specifier(
package_req.to_string(),
- package_id.as_serialized(),
+ snapshot.root_packages.get(nv).unwrap().as_serialized(),
);
}
for package in snapshot.all_packages() {
@@ -376,10 +485,12 @@ async fn add_package_reqs_to_snapshot(
api: &NpmRegistryApi,
package_reqs: Vec<NpmPackageReq>,
snapshot: NpmResolutionSnapshot,
+ maybe_lockfile: Option<Arc<Mutex<Lockfile>>>,
) -> Result<NpmResolutionSnapshot, AnyError> {
- if package_reqs
- .iter()
- .all(|req| snapshot.package_reqs.contains_key(req))
+ if snapshot.pending_unresolved_packages.is_empty()
+ && package_reqs
+ .iter()
+ .all(|req| snapshot.package_reqs.contains_key(req))
{
return Ok(snapshot); // already up to date
}
@@ -390,39 +501,72 @@ async fn add_package_reqs_to_snapshot(
"Failed creating npm state. Try recreating your lockfile."
)
})?;
+ let pending_unresolved = graph.take_pending_unresolved();
// avoid loading the info if this is already in the graph
let package_reqs = package_reqs
.into_iter()
.filter(|r| !graph.has_package_req(r))
.collect::<Vec<_>>();
+ let pending_unresolved = pending_unresolved
+ .into_iter()
+ .filter(|p| !graph.has_root_package(p))
+ .collect::<Vec<_>>();
- // go over the top level package names first, then down the tree
- // one level at a time through all the branches
+ // cache the packages in parallel
api
.cache_in_parallel(
package_reqs
.iter()
- .map(|r| r.name.clone())
+ .map(|req| req.name.clone())
+ .chain(pending_unresolved.iter().map(|id| id.name.clone()))
+ .collect::<HashSet<_>>()
.into_iter()
.collect::<Vec<_>>(),
)
.await?;
+ // go over the top level package names first (npm package reqs and pending unresolved),
+ // then down the tree one level at a time through all the branches
let mut resolver = GraphDependencyResolver::new(&mut graph, api);
- // The package reqs should already be sorted
+ // The package reqs and ids should already be sorted
// in the order they should be resolved in.
for package_req in package_reqs {
let info = api.package_info(&package_req.name).await?;
resolver.add_package_req(&package_req, &info)?;
}
+ for pkg_id in pending_unresolved {
+ let info = api.package_info(&pkg_id.name).await?;
+ resolver.add_root_package(&pkg_id, &info)?;
+ }
+
resolver.resolve_pending().await?;
let result = graph.into_snapshot(api).await;
api.clear_memory_cache();
- result
+
+ if let Some(lockfile_mutex) = maybe_lockfile {
+ let mut lockfile = lockfile_mutex.lock();
+ match result {
+ Ok(snapshot) => {
+ for (package_req, nv) in snapshot.package_reqs.iter() {
+ lockfile.insert_npm_specifier(
+ package_req.to_string(),
+ snapshot.root_packages.get(nv).unwrap().as_serialized(),
+ );
+ }
+ for package in snapshot.all_packages() {
+ lockfile.check_or_insert_npm_package(package.into())?;
+ }
+ Ok(snapshot)
+ }
+ Err(err) => Err(err),
+ }
+ } else {
+ result
+ }
}
#[cfg(test)]
diff --git a/cli/npm/resolution/snapshot.rs b/cli/npm/resolution/snapshot.rs
index 3fc82cbb8..e986294ec 100644
--- a/cli/npm/resolution/snapshot.rs
+++ b/cli/npm/resolution/snapshot.rs
@@ -54,6 +54,9 @@ pub struct NpmResolutionSnapshot {
pub(super) packages_by_name: HashMap<String, Vec<NpmPackageId>>,
#[serde(with = "map_to_vec")]
pub(super) packages: HashMap<NpmPackageId, NpmResolutionPackage>,
+ /// Ordered list based on resolution of packages whose dependencies
+ /// have not yet been resolved
+ pub(super) pending_unresolved_packages: Vec<NpmPackageNv>,
}
impl std::fmt::Debug for NpmResolutionSnapshot {
@@ -76,6 +79,10 @@ impl std::fmt::Debug for NpmResolutionSnapshot {
"packages",
&self.packages.iter().collect::<BTreeMap<_, _>>(),
)
+ .field(
+ "pending_unresolved_packages",
+ &self.pending_unresolved_packages,
+ )
.finish()
}
}
@@ -120,22 +127,28 @@ mod map_to_vec {
}
impl NpmResolutionSnapshot {
- /// Resolve a node package from a deno module.
- pub fn resolve_package_from_deno_module(
+ /// Resolve a package from a package requirement.
+ pub fn resolve_pkg_from_pkg_req(
&self,
req: &NpmPackageReq,
) -> Result<&NpmResolutionPackage, AnyError> {
- match self
- .package_reqs
- .get(req)
- .and_then(|nv| self.root_packages.get(nv))
- .and_then(|id| self.packages.get(id))
- {
- Some(id) => Ok(id),
+ match self.package_reqs.get(req) {
+ Some(id) => self.resolve_package_from_deno_module(id),
None => bail!("could not find npm package directory for '{}'", req),
}
}
+ /// Resolve a package from a deno module.
+ pub fn resolve_package_from_deno_module(
+ &self,
+ id: &NpmPackageNv,
+ ) -> Result<&NpmResolutionPackage, AnyError> {
+ match self.root_packages.get(id) {
+ Some(id) => Ok(self.packages.get(id).unwrap()),
+ None => bail!("could not find npm package directory for '{}'", id),
+ }
+ }
+
pub fn top_level_packages(&self) -> Vec<NpmPackageId> {
self.root_packages.values().cloned().collect::<Vec<_>>()
}
@@ -342,6 +355,7 @@ impl NpmResolutionSnapshot {
root_packages,
packages_by_name,
packages,
+ pending_unresolved_packages: Default::default(),
})
}
}
diff --git a/cli/npm/resolution/specifier.rs b/cli/npm/resolution/specifier.rs
deleted file mode 100644
index 29d65c747..000000000
--- a/cli/npm/resolution/specifier.rs
+++ /dev/null
@@ -1,666 +0,0 @@
-// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license.
-
-use std::cmp::Ordering;
-use std::collections::HashMap;
-use std::collections::HashSet;
-use std::collections::VecDeque;
-
-use deno_ast::ModuleSpecifier;
-use deno_graph::npm::NpmPackageReq;
-use deno_graph::npm::NpmPackageReqReference;
-use deno_graph::ModuleGraph;
-
-pub struct GraphNpmInfo {
- /// The order of these package requirements is the order they
- /// should be resolved in.
- pub package_reqs: Vec<NpmPackageReq>,
- /// Gets if the graph had a built-in node specifier (ex. `node:fs`).
- pub has_node_builtin_specifier: bool,
-}
-
-/// Resolves npm specific information from the graph.
-///
-/// This function will analyze the module graph for parent-most folder
-/// specifiers of all modules, then group npm specifiers together as found in
-/// those descendant modules and return them in the order found spreading out
-/// from the root of the graph.
-///
-/// For example, given the following module graph:
-///
-/// file:///dev/local_module_a/mod.ts
-/// ├── npm:package-a@1
-/// ├─┬ https://deno.land/x/module_d/mod.ts
-/// │ └─┬ https://deno.land/x/module_d/other.ts
-/// │ └── npm:package-a@3
-/// ├─┬ file:///dev/local_module_a/other.ts
-/// │ └── npm:package-b@2
-/// ├─┬ file:///dev/local_module_b/mod.ts
-/// │ └── npm:package-b@2
-/// └─┬ https://deno.land/x/module_a/mod.ts
-/// ├── npm:package-a@4
-/// ├── npm:package-c@5
-/// ├─┬ https://deno.land/x/module_c/sub_folder/mod.ts
-/// │ ├── https://deno.land/x/module_c/mod.ts
-/// │ ├─┬ https://deno.land/x/module_d/sub_folder/mod.ts
-/// │ │ └── npm:package-other@2
-/// │ └── npm:package-c@5
-/// └── https://deno.land/x/module_b/mod.ts
-///
-/// The graph above would be grouped down to the topmost specifier folders like
-/// so and npm specifiers under each path would be resolved for that group
-/// prioritizing file specifiers and sorting by end folder name alphabetically:
-///
-/// file:///dev/local_module_a/
-/// ├── file:///dev/local_module_b/
-/// ├─┬ https://deno.land/x/module_a/
-/// │ ├── https://deno.land/x/module_b/
-/// │ └─┬ https://deno.land/x/module_c/
-/// │ └── https://deno.land/x/module_d/
-/// └── https://deno.land/x/module_d/
-///
-/// Then it would resolve the npm specifiers in each of those groups according
-/// to that tree going by tree depth.
-pub fn resolve_graph_npm_info(graph: &ModuleGraph) -> GraphNpmInfo {
- fn collect_specifiers<'a>(
- graph: &'a ModuleGraph,
- module: &'a deno_graph::Module,
- ) -> Vec<&'a ModuleSpecifier> {
- let mut specifiers = Vec::with_capacity(module.dependencies.len() * 2 + 1);
- let maybe_types = module
- .maybe_types_dependency
- .as_ref()
- .map(|d| &d.dependency);
- if let Some(specifier) = maybe_types.and_then(|d| d.maybe_specifier()) {
- specifiers.push(specifier);
- }
- for dep in module.dependencies.values() {
- #[allow(clippy::manual_flatten)]
- for resolved in [&dep.maybe_code, &dep.maybe_type] {
- if let Some(specifier) = resolved.maybe_specifier() {
- specifiers.push(specifier);
- }
- }
- }
-
- // flatten any data urls into this list of specifiers
- for i in (0..specifiers.len()).rev() {
- if specifiers[i].scheme() == "data" {
- let data_specifier = specifiers.swap_remove(i);
- if let Some(module) = graph.get(data_specifier) {
- specifiers.extend(collect_specifiers(graph, module));
- }
- }
- }
-
- specifiers
- }
-
- fn analyze_module(
- module: &deno_graph::Module,
- graph: &ModuleGraph,
- specifier_graph: &mut SpecifierTree,
- seen: &mut HashSet<ModuleSpecifier>,
- has_node_builtin_specifier: &mut bool,
- ) {
- if !seen.insert(module.specifier.clone()) {
- return; // already visited
- }
-
- let parent_specifier = get_folder_path_specifier(&module.specifier);
- let leaf = specifier_graph.get_leaf(&parent_specifier);
-
- let specifiers = collect_specifiers(graph, module);
-
- // fill this leaf's information
- for specifier in &specifiers {
- if let Ok(npm_ref) = NpmPackageReqReference::from_specifier(specifier) {
- leaf.reqs.insert(npm_ref.req);
- } else if !specifier.as_str().starts_with(parent_specifier.as_str()) {
- leaf
- .dependencies
- .insert(get_folder_path_specifier(specifier));
- }
-
- if !*has_node_builtin_specifier && specifier.scheme() == "node" {
- *has_node_builtin_specifier = true;
- }
- }
-
- // now visit all the dependencies
- for specifier in &specifiers {
- if let Some(module) = graph.get(specifier) {
- analyze_module(
- module,
- graph,
- specifier_graph,
- seen,
- has_node_builtin_specifier,
- );
- }
- }
- }
-
- let root_specifiers = graph
- .roots
- .iter()
- .map(|url| graph.resolve(url))
- .collect::<Vec<_>>();
- let mut seen = HashSet::new();
- let mut specifier_graph = SpecifierTree::default();
- let mut has_node_builtin_specifier = false;
- for root in &root_specifiers {
- if let Some(module) = graph.get(root) {
- analyze_module(
- module,
- graph,
- &mut specifier_graph,
- &mut seen,
- &mut has_node_builtin_specifier,
- );
- }
- }
-
- let mut seen = HashSet::new();
- let mut pending_specifiers = VecDeque::new();
- let mut result = Vec::new();
-
- for specifier in &root_specifiers {
- match NpmPackageReqReference::from_specifier(specifier) {
- Ok(npm_ref) => result.push(npm_ref.req),
- Err(_) => {
- pending_specifiers.push_back(get_folder_path_specifier(specifier))
- }
- }
- }
-
- while let Some(specifier) = pending_specifiers.pop_front() {
- let leaf = specifier_graph.get_leaf(&specifier);
- if !seen.insert(leaf.specifier.clone()) {
- continue; // already seen
- }
-
- let reqs = std::mem::take(&mut leaf.reqs);
- let mut reqs = reqs.into_iter().collect::<Vec<_>>();
- reqs.sort();
- result.extend(reqs);
-
- let mut deps = std::mem::take(&mut leaf.dependencies)
- .into_iter()
- .collect::<Vec<_>>();
- deps.sort_by(cmp_folder_specifiers);
-
- for dep in deps {
- pending_specifiers.push_back(dep);
- }
- }
-
- GraphNpmInfo {
- has_node_builtin_specifier,
- package_reqs: result,
- }
-}
-
-fn get_folder_path_specifier(specifier: &ModuleSpecifier) -> ModuleSpecifier {
- let mut specifier = specifier.clone();
- specifier.set_query(None);
- specifier.set_fragment(None);
- if !specifier.path().ends_with('/') {
- // remove the last path part, but keep the trailing slash
- let mut path_parts = specifier.path().split('/').collect::<Vec<_>>();
- let path_parts_len = path_parts.len(); // make borrow checker happy for some reason
- if path_parts_len > 0 {
- path_parts[path_parts_len - 1] = "";
- }
- specifier.set_path(&path_parts.join("/"));
- }
- specifier
-}
-
-#[derive(Debug)]
-enum SpecifierTreeNode {
- Parent(SpecifierTreeParentNode),
- Leaf(SpecifierTreeLeafNode),
-}
-
-impl SpecifierTreeNode {
- pub fn mut_to_leaf(&mut self) {
- if let SpecifierTreeNode::Parent(node) = self {
- let node = std::mem::replace(
- node,
- SpecifierTreeParentNode {
- specifier: node.specifier.clone(),
- dependencies: Default::default(),
- },
- );
- *self = SpecifierTreeNode::Leaf(node.into_leaf());
- }
- }
-}
-
-#[derive(Debug)]
-struct SpecifierTreeParentNode {
- specifier: ModuleSpecifier,
- dependencies: HashMap<String, SpecifierTreeNode>,
-}
-
-impl SpecifierTreeParentNode {
- pub fn into_leaf(self) -> SpecifierTreeLeafNode {
- fn fill_new_leaf(
- deps: HashMap<String, SpecifierTreeNode>,
- new_leaf: &mut SpecifierTreeLeafNode,
- ) {
- for node in deps.into_values() {
- match node {
- SpecifierTreeNode::Parent(node) => {
- fill_new_leaf(node.dependencies, new_leaf)
- }
- SpecifierTreeNode::Leaf(leaf) => {
- for dep in leaf.dependencies {
- // don't insert if the dependency is found within the new leaf
- if !dep.as_str().starts_with(new_leaf.specifier.as_str()) {
- new_leaf.dependencies.insert(dep);
- }
- }
- new_leaf.reqs.extend(leaf.reqs);
- }
- }
- }
- }
-
- let mut new_leaf = SpecifierTreeLeafNode {
- specifier: self.specifier,
- reqs: Default::default(),
- dependencies: Default::default(),
- };
- fill_new_leaf(self.dependencies, &mut new_leaf);
- new_leaf
- }
-}
-
-#[derive(Debug)]
-struct SpecifierTreeLeafNode {
- specifier: ModuleSpecifier,
- reqs: HashSet<NpmPackageReq>,
- dependencies: HashSet<ModuleSpecifier>,
-}
-
-#[derive(Default)]
-struct SpecifierTree {
- root_nodes: HashMap<ModuleSpecifier, SpecifierTreeNode>,
-}
-
-impl SpecifierTree {
- pub fn get_leaf(
- &mut self,
- specifier: &ModuleSpecifier,
- ) -> &mut SpecifierTreeLeafNode {
- let root_specifier = {
- let mut specifier = specifier.clone();
- specifier.set_path("");
- specifier
- };
- let root_node = self
- .root_nodes
- .entry(root_specifier.clone())
- .or_insert_with(|| {
- SpecifierTreeNode::Parent(SpecifierTreeParentNode {
- specifier: root_specifier.clone(),
- dependencies: Default::default(),
- })
- });
- let mut current_node = root_node;
- if !matches!(specifier.path(), "" | "/") {
- let mut current_parts = Vec::new();
- let path = specifier.path();
- for part in path[1..path.len() - 1].split('/') {
- current_parts.push(part);
- match current_node {
- SpecifierTreeNode::Leaf(leaf) => return leaf,
- SpecifierTreeNode::Parent(node) => {
- current_node = node
- .dependencies
- .entry(part.to_string())
- .or_insert_with(|| {
- SpecifierTreeNode::Parent(SpecifierTreeParentNode {
- specifier: {
- let mut specifier = root_specifier.clone();
- specifier.set_path(&current_parts.join("/"));
- specifier
- },
- dependencies: Default::default(),
- })
- });
- }
- }
- }
- }
- current_node.mut_to_leaf();
- match current_node {
- SpecifierTreeNode::Leaf(leaf) => leaf,
- _ => unreachable!(),
- }
- }
-}
-
-// prefer file: specifiers, then sort by folder name, then by specifier
-fn cmp_folder_specifiers(a: &ModuleSpecifier, b: &ModuleSpecifier) -> Ordering {
- fn order_folder_name(path_a: &str, path_b: &str) -> Option<Ordering> {
- let path_a = path_a.trim_end_matches('/');
- let path_b = path_b.trim_end_matches('/');
- match path_a.rfind('/') {
- Some(a_index) => match path_b.rfind('/') {
- Some(b_index) => match path_a[a_index..].cmp(&path_b[b_index..]) {
- Ordering::Equal => None,
- ordering => Some(ordering),
- },
- None => None,
- },
- None => None,
- }
- }
-
- fn order_specifiers(a: &ModuleSpecifier, b: &ModuleSpecifier) -> Ordering {
- match order_folder_name(a.path(), b.path()) {
- Some(ordering) => ordering,
- None => a.as_str().cmp(b.as_str()), // fallback to just comparing the entire url
- }
- }
-
- if a.scheme() == "file" {
- if b.scheme() == "file" {
- order_specifiers(a, b)
- } else {
- Ordering::Less
- }
- } else if b.scheme() == "file" {
- Ordering::Greater
- } else {
- order_specifiers(a, b)
- }
-}
-
-#[cfg(test)]
-mod tests {
- use pretty_assertions::assert_eq;
-
- use super::*;
-
- #[test]
- fn sorting_folder_specifiers() {
- fn cmp(a: &str, b: &str) -> Ordering {
- let a = ModuleSpecifier::parse(a).unwrap();
- let b = ModuleSpecifier::parse(b).unwrap();
- cmp_folder_specifiers(&a, &b)
- }
-
- // prefer file urls
- assert_eq!(
- cmp("file:///test/", "https://deno.land/x/module/"),
- Ordering::Less
- );
- assert_eq!(
- cmp("https://deno.land/x/module/", "file:///test/"),
- Ordering::Greater
- );
-
- // sort by folder name
- assert_eq!(
- cmp(
- "https://deno.land/x/module_a/",
- "https://deno.land/x/module_b/"
- ),
- Ordering::Less
- );
- assert_eq!(
- cmp(
- "https://deno.land/x/module_b/",
- "https://deno.land/x/module_a/"
- ),
- Ordering::Greater
- );
- assert_eq!(
- cmp(
- "https://deno.land/x/module_a/",
- "https://deno.land/std/module_b/"
- ),
- Ordering::Less
- );
- assert_eq!(
- cmp(
- "https://deno.land/std/module_b/",
- "https://deno.land/x/module_a/"
- ),
- Ordering::Greater
- );
-
- // by specifier, since folder names match
- assert_eq!(
- cmp(
- "https://deno.land/std/module_a/",
- "https://deno.land/x/module_a/"
- ),
- Ordering::Less
- );
- }
-
- #[test]
- fn test_get_folder_path_specifier() {
- fn get(a: &str) -> String {
- get_folder_path_specifier(&ModuleSpecifier::parse(a).unwrap()).to_string()
- }
-
- assert_eq!(get("https://deno.land/"), "https://deno.land/");
- assert_eq!(get("https://deno.land"), "https://deno.land/");
- assert_eq!(get("https://deno.land/test"), "https://deno.land/");
- assert_eq!(get("https://deno.land/test/"), "https://deno.land/test/");
- assert_eq!(
- get("https://deno.land/test/other"),
- "https://deno.land/test/"
- );
- assert_eq!(
- get("https://deno.land/test/other/"),
- "https://deno.land/test/other/"
- );
- assert_eq!(
- get("https://deno.land/test/other/test?test#other"),
- "https://deno.land/test/other/"
- );
- }
-
- #[tokio::test]
- async fn test_resolve_npm_package_reqs() {
- let mut loader = deno_graph::source::MemoryLoader::new(
- vec![
- (
- "file:///dev/local_module_a/mod.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "file:///dev/local_module_a/mod.ts".to_string(),
- content: concat!(
- "import 'https://deno.land/x/module_d/mod.ts';",
- "import 'file:///dev/local_module_a/other.ts';",
- "import 'file:///dev/local_module_b/mod.ts';",
- "import 'https://deno.land/x/module_a/mod.ts';",
- "import 'npm:package-a@local_module_a';",
- "import 'https://deno.land/x/module_e/';",
- )
- .to_string(),
- maybe_headers: None,
- },
- ),
- (
- "file:///dev/local_module_a/other.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "file:///dev/local_module_a/other.ts".to_string(),
- content: "import 'npm:package-b@local_module_a';".to_string(),
- maybe_headers: None,
- },
- ),
- (
- "file:///dev/local_module_b/mod.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "file:///dev/local_module_b/mod.ts".to_string(),
- content: concat!(
- "export * from 'npm:package-b@local_module_b';",
- "import * as test from 'data:application/typescript,export%20*%20from%20%22npm:package-data%40local_module_b%22;';",
- ).to_string(),
- maybe_headers: None,
- },
- ),
- (
- "https://deno.land/x/module_d/mod.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "https://deno.land/x/module_d/mod.ts".to_string(),
- content: concat!(
- "import './other.ts';",
- "import 'npm:package-a@module_d';",
- )
- .to_string(),
- maybe_headers: None,
- },
- ),
- (
- "https://deno.land/x/module_d/other.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "https://deno.land/x/module_d/other.ts".to_string(),
- content: "import 'npm:package-c@module_d'".to_string(),
- maybe_headers: None,
- },
- ),
- (
- "https://deno.land/x/module_a/mod.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "https://deno.land/x/module_a/mod.ts".to_string(),
- content: concat!(
- "import 'npm:package-a@module_a';",
- "import 'npm:package-b@module_a';",
- "import '../module_c/sub/sub/mod.ts';",
- "import '../module_b/mod.ts';",
- )
- .to_string(),
- maybe_headers: None,
- },
- ),
- (
- "https://deno.land/x/module_b/mod.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "https://deno.land/x/module_b/mod.ts".to_string(),
- content: "import 'npm:package-a@module_b'".to_string(),
- maybe_headers: None,
- },
- ),
- (
- "https://deno.land/x/module_c/sub/sub/mod.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "https://deno.land/x/module_c/sub/sub/mod.ts"
- .to_string(),
- content: concat!(
- "import 'npm:package-a@module_c';",
- "import '../../mod.ts';",
- )
- .to_string(),
- maybe_headers: None,
- },
- ),
- (
- "https://deno.land/x/module_c/mod.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "https://deno.land/x/module_c/mod.ts".to_string(),
- content: concat!(
- "import 'npm:package-b@module_c';",
- "import '../module_d/sub_folder/mod.ts';",
- )
- .to_string(),
- maybe_headers: None,
- },
- ),
- (
- "https://deno.land/x/module_d/sub_folder/mod.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "https://deno.land/x/module_d/sub_folder/mod.ts"
- .to_string(),
- content: "import 'npm:package-b@module_d';".to_string(),
- maybe_headers: None,
- },
- ),
- (
- // ensure a module at a directory is treated as being at a directory
- "https://deno.land/x/module_e/".to_string(),
- deno_graph::source::Source::Module {
- specifier: "https://deno.land/x/module_e/"
- .to_string(),
- content: "import 'npm:package-a@module_e';".to_string(),
- maybe_headers: Some(vec![(
- "content-type".to_string(),
- "application/javascript".to_string(),
- )]),
- },
- ),
- // redirect module
- (
- "https://deno.land/x/module_redirect/mod.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "https://deno.land/x/module_redirect@0.0.1/mod.ts".to_string(),
- content: concat!(
- "import 'npm:package-a@module_redirect';",
- // try another redirect here
- "import 'https://deno.land/x/module_redirect/other.ts';",
- ).to_string(),
- maybe_headers: None,
- }
- ),
- (
- "https://deno.land/x/module_redirect/other.ts".to_string(),
- deno_graph::source::Source::Module {
- specifier: "https://deno.land/x/module_redirect@0.0.1/other.ts".to_string(),
- content: "import 'npm:package-b@module_redirect';".to_string(),
- maybe_headers: None,
- }
- ),
- ],
- Vec::new(),
- );
- let analyzer = deno_graph::CapturingModuleAnalyzer::default();
- let mut graph = deno_graph::ModuleGraph::default();
- graph
- .build(
- vec![
- ModuleSpecifier::parse("file:///dev/local_module_a/mod.ts").unwrap(),
- // test redirect at root
- ModuleSpecifier::parse("https://deno.land/x/module_redirect/mod.ts")
- .unwrap(),
- ],
- &mut loader,
- deno_graph::BuildOptions {
- module_analyzer: Some(&analyzer),
- ..Default::default()
- },
- )
- .await;
- let reqs = resolve_graph_npm_info(&graph)
- .package_reqs
- .into_iter()
- .map(|r| r.to_string())
- .collect::<Vec<_>>();
-
- assert_eq!(
- reqs,
- vec![
- "package-a@local_module_a",
- "package-b@local_module_a",
- "package-a@module_redirect",
- "package-b@module_redirect",
- "package-b@local_module_b",
- "package-data@local_module_b",
- "package-a@module_a",
- "package-b@module_a",
- "package-a@module_d",
- "package-b@module_d",
- "package-c@module_d",
- "package-a@module_e",
- "package-a@module_b",
- "package-a@module_c",
- "package-b@module_c",
- ]
- );
- }
-}
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-24 04:58:12 +0000