fix(npm): improve peer dependency resolution (#17835)

This PR fixes peer dependency resolution to only resolve peers based on
the current graph traversal path. Previously, it would resolve a peers
by looking at a graph node's ancestors, which is not correct because
graph nodes are shared by different resolutions.

It also stores more information about peer dependency resolution in the
lockfile.

1 files changed, 68 insertions, 83 deletions

diff --git a/cli/npm/resolution/snapshot.rs b/cli/npm/resolution/snapshot.rs
index c717e74a8..bdc204ce8 100644
--- a/cli/npm/resolution/snapshot.rs
+++ b/cli/npm/resolution/snapshot.rs
@@ -8,21 +8,19 @@ use deno_core::anyhow::anyhow;
 use deno_core::anyhow::bail;
 use deno_core::anyhow::Context;
 use deno_core::error::AnyError;
-use deno_core::futures;
 use deno_core::parking_lot::Mutex;
+use deno_graph::npm::NpmPackageNv;
 use deno_graph::npm::NpmPackageReq;
 use deno_graph::semver::VersionReq;
 use serde::Deserialize;
 use serde::Serialize;
 
 use crate::args::Lockfile;
-use crate::npm::cache::should_sync_download;
 use crate::npm::cache::NpmPackageCacheFolderId;
 use crate::npm::registry::NpmPackageVersionDistInfo;
 use crate::npm::registry::NpmRegistryApi;
-use crate::npm::registry::RealNpmRegistryApi;
 
-use super::NpmPackageNodeId;
+use super::NpmPackageId;
 use super::NpmResolutionPackage;
 
 /// Packages partitioned by if they are "copy" packages or not.
@@ -44,13 +42,17 @@ impl NpmPackagesPartitioned {
   }
 }
 
-#[derive(Debug, Clone, Default, Serialize, Deserialize)]
+#[derive(Debug, Clone, Default, Serialize, Deserialize, PartialEq, Eq)]
 pub struct NpmResolutionSnapshot {
+  /// The unique package requirements map to a single npm package name and version.
   #[serde(with = "map_to_vec")]
-  pub(super) package_reqs: HashMap<NpmPackageReq, NpmPackageNodeId>,
-  pub(super) packages_by_name: HashMap<String, Vec<NpmPackageNodeId>>,
+  pub(super) package_reqs: HashMap<NpmPackageReq, NpmPackageNv>,
+  // Each root level npm package name and version maps to an exact npm package node id.
   #[serde(with = "map_to_vec")]
-  pub(super) packages: HashMap<NpmPackageNodeId, NpmResolutionPackage>,
+  pub(super) root_packages: HashMap<NpmPackageNv, NpmPackageId>,
+  pub(super) packages_by_name: HashMap<String, Vec<NpmPackageId>>,
+  #[serde(with = "map_to_vec")]
+  pub(super) packages: HashMap<NpmPackageId, NpmResolutionPackage>,
 }
 
 // This is done so the maps with non-string keys get serialized and deserialized as vectors.
@@ -98,25 +100,24 @@ impl NpmResolutionSnapshot {
     &self,
     req: &NpmPackageReq,
   ) -> Result<&NpmResolutionPackage, AnyError> {
-    match self.package_reqs.get(req) {
-      Some(id) => Ok(self.packages.get(id).unwrap()),
+    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),
       None => bail!("could not find npm package directory for '{}'", req),
     }
   }
 
-  pub fn top_level_packages(&self) -> Vec<NpmPackageNodeId> {
-    self
-      .package_reqs
-      .values()
-      .cloned()
-      .collect::<HashSet<_>>()
-      .into_iter()
-      .collect::<Vec<_>>()
+  pub fn top_level_packages(&self) -> Vec<NpmPackageId> {
+    self.root_packages.values().cloned().collect::<Vec<_>>()
   }
 
   pub fn package_from_id(
     &self,
-    id: &NpmPackageNodeId,
+    id: &NpmPackageId,
   ) -> Option<&NpmResolutionPackage> {
     self.packages.get(id)
   }
@@ -129,13 +130,13 @@ impl NpmResolutionSnapshot {
     // todo(dsherret): do we need an additional hashmap to get this quickly?
     let referrer_package = self
       .packages_by_name
-      .get(&referrer.name)
+      .get(&referrer.nv.name)
       .and_then(|packages| {
         packages
           .iter()
-          .filter(|p| p.version == referrer.version)
-          .filter_map(|id| {
-            let package = self.packages.get(id)?;
+          .filter(|p| p.nv.version == referrer.nv.version)
+          .filter_map(|node_id| {
+            let package = self.packages.get(node_id)?;
             if package.copy_index == referrer.copy_index {
               Some(package)
             } else {
@@ -153,7 +154,7 @@ impl NpmResolutionSnapshot {
       return Ok(self.packages.get(id).unwrap());
     }
 
-    if referrer_package.id.name == name {
+    if referrer_package.pkg_id.nv.name == name {
       return Ok(referrer_package);
     }
 
@@ -198,19 +199,19 @@ impl NpmResolutionSnapshot {
     &self,
     name: &str,
     version_req: &VersionReq,
-  ) -> Option<NpmPackageNodeId> {
+  ) -> Option<NpmPackageId> {
     // todo(dsherret): this is not exactly correct because some ids
     // will be better than others due to peer dependencies
-    let mut maybe_best_id: Option<&NpmPackageNodeId> = None;
-    if let Some(ids) = self.packages_by_name.get(name) {
-      for id in ids {
-        if version_req.matches(&id.version) {
+    let mut maybe_best_id: Option<&NpmPackageId> = None;
+    if let Some(node_ids) = self.packages_by_name.get(name) {
+      for node_id in node_ids.iter() {
+        if version_req.matches(&node_id.nv.version) {
           let is_best_version = maybe_best_id
             .as_ref()
-            .map(|best_id| best_id.version.cmp(&id.version).is_lt())
+            .map(|best_id| best_id.nv.version.cmp(&node_id.nv.version).is_lt())
             .unwrap_or(true);
           if is_best_version {
-            maybe_best_id = Some(id);
+            maybe_best_id = Some(node_id);
           }
         }
       }
@@ -220,11 +221,12 @@ impl NpmResolutionSnapshot {
 
   pub async fn from_lockfile(
     lockfile: Arc<Mutex<Lockfile>>,
-    api: &RealNpmRegistryApi,
+    api: &NpmRegistryApi,
   ) -> Result<Self, AnyError> {
-    let mut package_reqs: HashMap<NpmPackageReq, NpmPackageNodeId>;
-    let mut packages_by_name: HashMap<String, Vec<NpmPackageNodeId>>;
-    let mut packages: HashMap<NpmPackageNodeId, NpmResolutionPackage>;
+    let mut package_reqs: HashMap<NpmPackageReq, NpmPackageNv>;
+    let mut root_packages: HashMap<NpmPackageNv, NpmPackageId>;
+    let mut packages_by_name: HashMap<String, Vec<NpmPackageId>>;
+    let mut packages: HashMap<NpmPackageId, NpmResolutionPackage>;
     let mut copy_index_resolver: SnapshotPackageCopyIndexResolver;
 
     {
@@ -233,6 +235,8 @@ impl NpmResolutionSnapshot {
       // pre-allocate collections
       package_reqs =
         HashMap::with_capacity(lockfile.content.npm.specifiers.len());
+      root_packages =
+        HashMap::with_capacity(lockfile.content.npm.specifiers.len());
       let packages_len = lockfile.content.npm.packages.len();
       packages = HashMap::with_capacity(packages_len);
       packages_by_name = HashMap::with_capacity(packages_len); // close enough
@@ -244,31 +248,32 @@ impl NpmResolutionSnapshot {
       for (key, value) in &lockfile.content.npm.specifiers {
         let package_req = NpmPackageReq::from_str(key)
           .with_context(|| format!("Unable to parse npm specifier: {key}"))?;
-        let package_id = NpmPackageNodeId::from_serialized(value)?;
-        package_reqs.insert(package_req, package_id.clone());
+        let package_id = NpmPackageId::from_serialized(value)?;
+        package_reqs.insert(package_req, package_id.nv.clone());
+        root_packages.insert(package_id.nv.clone(), package_id.clone());
         verify_ids.insert(package_id.clone());
       }
 
       // then the packages
       for (key, value) in &lockfile.content.npm.packages {
-        let package_id = NpmPackageNodeId::from_serialized(key)?;
+        let package_id = NpmPackageId::from_serialized(key)?;
 
         // collect the dependencies
         let mut dependencies = HashMap::default();
 
         packages_by_name
-          .entry(package_id.name.to_string())
+          .entry(package_id.nv.name.to_string())
           .or_default()
           .push(package_id.clone());
 
         for (name, specifier) in &value.dependencies {
-          let dep_id = NpmPackageNodeId::from_serialized(specifier)?;
+          let dep_id = NpmPackageId::from_serialized(specifier)?;
           dependencies.insert(name.to_string(), dep_id.clone());
           verify_ids.insert(dep_id);
         }
 
         let package = NpmResolutionPackage {
-          id: package_id.clone(),
+          pkg_id: package_id.clone(),
           copy_index: copy_index_resolver.resolve(&package_id),
           // temporary dummy value
           dist: NpmPackageVersionDistInfo::default(),
@@ -288,40 +293,20 @@ impl NpmResolutionSnapshot {
       }
     }
 
-    let mut unresolved_tasks = Vec::with_capacity(packages_by_name.len());
-
-    // cache the package names in parallel in the registry api
-    // unless synchronous download should occur
-    if should_sync_download() {
-      let mut package_names = packages_by_name.keys().collect::<Vec<_>>();
-      package_names.sort();
-      for package_name in package_names {
-        api.package_info(package_name).await?;
-      }
-    } else {
-      for package_name in packages_by_name.keys() {
-        let package_name = package_name.clone();
-        let api = api.clone();
-        unresolved_tasks.push(tokio::task::spawn(async move {
-          api.package_info(&package_name).await?;
-          Result::<_, AnyError>::Ok(())
-        }));
-      }
-    }
-    for result in futures::future::join_all(unresolved_tasks).await {
-      result??;
-    }
+    api
+      .cache_in_parallel(packages_by_name.keys().cloned().collect())
+      .await?;
 
     // ensure the dist is set for each package
     for package in packages.values_mut() {
       // this will read from the memory cache now
       let version_info = match api
-        .package_version_info(&package.id.name, &package.id.version)
+        .package_version_info(&package.pkg_id.nv)
         .await?
       {
         Some(version_info) => version_info,
         None => {
-          bail!("could not find '{}' specified in the lockfile. Maybe try again with --reload", package.id.display());
+          bail!("could not find '{}' specified in the lockfile. Maybe try again with --reload", package.pkg_id.nv);
         }
       };
       package.dist = version_info.dist;
@@ -329,6 +314,7 @@ impl NpmResolutionSnapshot {
 
     Ok(Self {
       package_reqs,
+      root_packages,
       packages_by_name,
       packages,
     })
@@ -336,8 +322,8 @@ impl NpmResolutionSnapshot {
 }
 
 pub struct SnapshotPackageCopyIndexResolver {
-  packages_to_copy_index: HashMap<NpmPackageNodeId, usize>,
-  package_name_version_to_copy_count: HashMap<(String, String), usize>,
+  packages_to_copy_index: HashMap<NpmPackageId, usize>,
+  package_name_version_to_copy_count: HashMap<NpmPackageNv, usize>,
 }
 
 impl SnapshotPackageCopyIndexResolver {
@@ -349,7 +335,7 @@ impl SnapshotPackageCopyIndexResolver {
   }
 
   pub fn from_map_with_capacity(
-    mut packages_to_copy_index: HashMap<NpmPackageNodeId, usize>,
+    mut packages_to_copy_index: HashMap<NpmPackageId, usize>,
     capacity: usize,
   ) -> Self {
     let mut package_name_version_to_copy_count =
@@ -358,9 +344,9 @@ impl SnapshotPackageCopyIndexResolver {
       packages_to_copy_index.reserve(capacity - packages_to_copy_index.len());
     }
 
-    for (id, index) in &packages_to_copy_index {
+    for (node_id, index) in &packages_to_copy_index {
       let entry = package_name_version_to_copy_count
-        .entry((id.name.to_string(), id.version.to_string()))
+        .entry(node_id.nv.clone())
         .or_insert(0);
       if *entry < *index {
         *entry = *index;
@@ -372,18 +358,18 @@ impl SnapshotPackageCopyIndexResolver {
     }
   }
 
-  pub fn resolve(&mut self, id: &NpmPackageNodeId) -> usize {
-    if let Some(index) = self.packages_to_copy_index.get(id) {
+  pub fn resolve(&mut self, node_id: &NpmPackageId) -> usize {
+    if let Some(index) = self.packages_to_copy_index.get(node_id) {
       *index
     } else {
       let index = *self
         .package_name_version_to_copy_count
-        .entry((id.name.to_string(), id.version.to_string()))
+        .entry(node_id.nv.clone())
         .and_modify(|count| {
           *count += 1;
         })
         .or_insert(0);
-      self.packages_to_copy_index.insert(id.clone(), index);
+      self.packages_to_copy_index.insert(node_id.clone(), index);
       index
     }
   }
@@ -422,24 +408,24 @@ mod tests {
       SnapshotPackageCopyIndexResolver::with_capacity(10);
     assert_eq!(
       copy_index_resolver
-        .resolve(&NpmPackageNodeId::from_serialized("package@1.0.0").unwrap()),
+        .resolve(&NpmPackageId::from_serialized("package@1.0.0").unwrap()),
       0
     );
     assert_eq!(
       copy_index_resolver
-        .resolve(&NpmPackageNodeId::from_serialized("package@1.0.0").unwrap()),
+        .resolve(&NpmPackageId::from_serialized("package@1.0.0").unwrap()),
       0
     );
     assert_eq!(
       copy_index_resolver.resolve(
-        &NpmPackageNodeId::from_serialized("package@1.0.0_package-b@1.0.0")
+        &NpmPackageId::from_serialized("package@1.0.0_package-b@1.0.0")
           .unwrap()
       ),
       1
     );
     assert_eq!(
       copy_index_resolver.resolve(
-        &NpmPackageNodeId::from_serialized(
+        &NpmPackageId::from_serialized(
           "package@1.0.0_package-b@1.0.0__package-c@2.0.0"
         )
         .unwrap()
@@ -448,15 +434,14 @@ mod tests {
     );
     assert_eq!(
       copy_index_resolver.resolve(
-        &NpmPackageNodeId::from_serialized("package@1.0.0_package-b@1.0.0")
+        &NpmPackageId::from_serialized("package@1.0.0_package-b@1.0.0")
           .unwrap()
       ),
       1
     );
     assert_eq!(
-      copy_index_resolver.resolve(
-        &NpmPackageNodeId::from_serialized("package-b@1.0.0").unwrap()
-      ),
+      copy_index_resolver
+        .resolve(&NpmPackageId::from_serialized("package-b@1.0.0").unwrap()),
       0
     );
   }