refactor: use deno_graph for npm specifiers (#17858)

This changes npm specifiers to be handled by deno_graph and resolved to
an npm package name and version when the specifier is encountered. It
also slightly changes how npm specifier resolution occurs—previously it
would collect all the npm specifiers and resolve them all at once, but
now it resolves them on the fly as they are encountered in the module
graph.

https://github.com/denoland/deno_graph/pull/232

---------

Co-authored-by: Bartek Iwańczuk <biwanczuk@gmail.com>

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",
-      ]
-    );
-  }
-}