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, 137 insertions, 128 deletions

diff --git a/cli/npm/resolution/mod.rs b/cli/npm/resolution/mod.rs
index ec6ee0dda..90bf16c43 100644
--- a/cli/npm/resolution/mod.rs
+++ b/cli/npm/resolution/mod.rs
@@ -1,11 +1,13 @@
 // Copyright 2018-2023 the Deno authors. All rights reserved. MIT license.
 
+use std::cmp::Ordering;
 use std::collections::HashMap;
 use std::collections::HashSet;
 
+use deno_core::anyhow::Context;
 use deno_core::error::AnyError;
-use deno_core::futures;
 use deno_core::parking_lot::RwLock;
+use deno_graph::npm::NpmPackageNv;
 use deno_graph::npm::NpmPackageReq;
 use deno_graph::semver::Version;
 use serde::Deserialize;
@@ -17,12 +19,11 @@ use crate::args::Lockfile;
 use self::graph::GraphDependencyResolver;
 use self::snapshot::NpmPackagesPartitioned;
 
-use super::cache::should_sync_download;
 use super::cache::NpmPackageCacheFolderId;
 use super::registry::NpmPackageVersionDistInfo;
-use super::registry::RealNpmRegistryApi;
-use super::NpmRegistryApi;
+use super::registry::NpmRegistryApi;
 
+mod common;
 mod graph;
 mod snapshot;
 mod specifier;
@@ -40,25 +41,20 @@ pub struct NpmPackageNodeIdDeserializationError {
 
 /// A resolved unique identifier for an npm package. This contains
 /// the resolved name, version, and peer dependency resolution identifiers.
-#[derive(
-  Debug, Clone, PartialOrd, Ord, PartialEq, Eq, Hash, Serialize, Deserialize,
-)]
-pub struct NpmPackageNodeId {
-  pub name: String,
-  pub version: Version,
-  pub peer_dependencies: Vec<NpmPackageNodeId>,
+#[derive(Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
+pub struct NpmPackageId {
+  pub nv: NpmPackageNv,
+  pub peer_dependencies: Vec<NpmPackageId>,
 }
 
-impl NpmPackageNodeId {
-  #[allow(unused)]
-  pub fn scope(&self) -> Option<&str> {
-    if self.name.starts_with('@') && self.name.contains('/') {
-      self.name.split('/').next()
-    } else {
-      None
-    }
+// Custom debug implementation for more concise test output
+impl std::fmt::Debug for NpmPackageId {
+  fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+    write!(f, "{}", self.as_serialized())
   }
+}
 
+impl NpmPackageId {
   pub fn as_serialized(&self) -> String {
     self.as_serialized_with_level(0)
   }
@@ -68,11 +64,11 @@ impl NpmPackageNodeId {
     let mut result = format!(
       "{}@{}",
       if level == 0 {
-        self.name.to_string()
+        self.nv.name.to_string()
       } else {
-        self.name.replace('/', "+")
+        self.nv.name.replace('/', "+")
       },
-      self.version
+      self.nv.version
     );
     for peer in &self.peer_dependencies {
       // unfortunately we can't do something like `_3` when
@@ -136,7 +132,7 @@ impl NpmPackageNodeId {
 
     fn parse_peers_at_level<'a>(
       level: usize,
-    ) -> impl Fn(&'a str) -> ParseResult<'a, Vec<NpmPackageNodeId>> {
+    ) -> impl Fn(&'a str) -> ParseResult<'a, Vec<NpmPackageId>> {
       move |mut input| {
         let mut peers = Vec::new();
         while let Ok((level_input, _)) = parse_level_at_level(level)(input) {
@@ -151,7 +147,7 @@ impl NpmPackageNodeId {
 
     fn parse_id_at_level<'a>(
       level: usize,
-    ) -> impl Fn(&'a str) -> ParseResult<'a, NpmPackageNodeId> {
+    ) -> impl Fn(&'a str) -> ParseResult<'a, NpmPackageId> {
       move |input| {
         let (input, (name, version)) = parse_name_and_version(input)?;
         let name = if level > 0 {
@@ -163,9 +159,8 @@ impl NpmPackageNodeId {
           parse_peers_at_level(level + 1)(input)?;
         Ok((
           input,
-          NpmPackageNodeId {
-            name,
-            version,
+          NpmPackageId {
+            nv: NpmPackageNv { name, version },
             peer_dependencies,
           },
         ))
@@ -179,17 +174,26 @@ impl NpmPackageNodeId {
       }
     })
   }
+}
+
+impl Ord for NpmPackageId {
+  fn cmp(&self, other: &Self) -> Ordering {
+    match self.nv.cmp(&other.nv) {
+      Ordering::Equal => self.peer_dependencies.cmp(&other.peer_dependencies),
+      ordering => ordering,
+    }
+  }
+}
 
-  pub fn display(&self) -> String {
-    // Don't implement std::fmt::Display because we don't
-    // want this to be used by accident in certain scenarios.
-    format!("{}@{}", self.name, self.version)
+impl PartialOrd for NpmPackageId {
+  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+    Some(self.cmp(other))
   }
 }
 
 #[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
 pub struct NpmResolutionPackage {
-  pub id: NpmPackageNodeId,
+  pub pkg_id: NpmPackageId,
   /// The peer dependency resolution can differ for the same
   /// package (name and version) depending on where it is in
   /// the resolution tree. This copy index indicates which
@@ -198,21 +202,20 @@ pub struct NpmResolutionPackage {
   pub dist: NpmPackageVersionDistInfo,
   /// Key is what the package refers to the other package as,
   /// which could be different from the package name.
-  pub dependencies: HashMap<String, NpmPackageNodeId>,
+  pub dependencies: HashMap<String, NpmPackageId>,
 }
 
 impl NpmResolutionPackage {
   pub fn get_package_cache_folder_id(&self) -> NpmPackageCacheFolderId {
     NpmPackageCacheFolderId {
-      name: self.id.name.clone(),
-      version: self.id.version.clone(),
+      nv: self.pkg_id.nv.clone(),
       copy_index: self.copy_index,
     }
   }
 }
 
 pub struct NpmResolution {
-  api: RealNpmRegistryApi,
+  api: NpmRegistryApi,
   snapshot: RwLock<NpmResolutionSnapshot>,
   update_semaphore: tokio::sync::Semaphore,
 }
@@ -228,7 +231,7 @@ impl std::fmt::Debug for NpmResolution {
 
 impl NpmResolution {
   pub fn new(
-    api: RealNpmRegistryApi,
+    api: NpmRegistryApi,
     initial_snapshot: Option<NpmResolutionSnapshot>,
   ) -> Self {
     Self {
@@ -246,9 +249,8 @@ impl NpmResolution {
     let _permit = self.update_semaphore.acquire().await?;
     let snapshot = self.snapshot.read().clone();
 
-    let snapshot = self
-      .add_package_reqs_to_snapshot(package_reqs, snapshot)
-      .await?;
+    let snapshot =
+      add_package_reqs_to_snapshot(&self.api, package_reqs, snapshot).await?;
 
     *self.snapshot.write() = snapshot;
     Ok(())
@@ -272,88 +274,28 @@ impl NpmResolution {
     } else {
       snapshot
     };
-    let snapshot = self
-      .add_package_reqs_to_snapshot(
-        package_reqs.into_iter().collect(),
-        snapshot,
-      )
-      .await?;
+    let snapshot = add_package_reqs_to_snapshot(
+      &self.api,
+      package_reqs.into_iter().collect(),
+      snapshot,
+    )
+    .await?;
 
     *self.snapshot.write() = snapshot;
 
     Ok(())
   }
 
-  async fn add_package_reqs_to_snapshot(
-    &self,
-    package_reqs: Vec<NpmPackageReq>,
-    snapshot: NpmResolutionSnapshot,
-  ) -> Result<NpmResolutionSnapshot, AnyError> {
-    // convert the snapshot to a traversable graph
-    let mut graph = Graph::from_snapshot(snapshot);
-
-    // go over the top level package names first, then down the
-    // tree one level at a time through all the branches
-    let mut unresolved_tasks = Vec::with_capacity(package_reqs.len());
-    let mut resolving_package_names =
-      HashSet::with_capacity(package_reqs.len());
-    for package_req in &package_reqs {
-      if graph.has_package_req(package_req) {
-        // skip analyzing this package, as there's already a matching top level package
-        continue;
-      }
-      if !resolving_package_names.insert(package_req.name.clone()) {
-        continue; // already resolving
-      }
-
-      // cache the package info up front in parallel
-      if should_sync_download() {
-        // for deterministic test output
-        self.api.package_info(&package_req.name).await?;
-      } else {
-        let api = self.api.clone();
-        let package_name = package_req.name.clone();
-        unresolved_tasks.push(tokio::task::spawn(async move {
-          // This is ok to call because api will internally cache
-          // the package information in memory.
-          api.package_info(&package_name).await
-        }));
-      };
-    }
-
-    for result in futures::future::join_all(unresolved_tasks).await {
-      result??; // surface the first error
-    }
-
-    let mut resolver = GraphDependencyResolver::new(&mut graph, &self.api);
-
-    // These package_reqs should already be sorted in the order they should
-    // be resolved in.
-    for package_req in package_reqs {
-      // avoid loading the info if this is already in the graph
-      if !resolver.has_package_req(&package_req) {
-        let info = self.api.package_info(&package_req.name).await?;
-        resolver.add_package_req(&package_req, &info)?;
-      }
-    }
-
-    resolver.resolve_pending().await?;
-
-    let result = graph.into_snapshot(&self.api).await;
-    self.api.clear_memory_cache();
-    result
-  }
-
   pub fn resolve_package_from_id(
     &self,
-    id: &NpmPackageNodeId,
+    id: &NpmPackageId,
   ) -> Option<NpmResolutionPackage> {
     self.snapshot.read().package_from_id(id).cloned()
   }
 
   pub fn resolve_package_cache_folder_id_from_id(
     &self,
-    id: &NpmPackageNodeId,
+    id: &NpmPackageId,
   ) -> Option<NpmPackageCacheFolderId> {
     self
       .snapshot
@@ -400,7 +342,8 @@ impl NpmResolution {
 
   pub fn lock(&self, lockfile: &mut Lockfile) -> Result<(), AnyError> {
     let snapshot = self.snapshot.read();
-    for (package_req, package_id) in snapshot.package_reqs.iter() {
+    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(),
@@ -413,40 +356,106 @@ impl NpmResolution {
   }
 }
 
+async fn add_package_reqs_to_snapshot(
+  api: &NpmRegistryApi,
+  package_reqs: Vec<NpmPackageReq>,
+  snapshot: NpmResolutionSnapshot,
+) -> Result<NpmResolutionSnapshot, AnyError> {
+  if package_reqs
+    .iter()
+    .all(|req| snapshot.package_reqs.contains_key(req))
+  {
+    return Ok(snapshot); // already up to date
+  }
+
+  // convert the snapshot to a traversable graph
+  let mut graph = Graph::from_snapshot(snapshot).with_context(|| {
+    deno_core::anyhow::anyhow!(
+      "Failed creating npm state. Try recreating your lockfile."
+    )
+  })?;
+
+  // 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<_>>();
+
+  // go over the top level package names first, then down the tree
+  // one level at a time through all the branches
+  api
+    .cache_in_parallel(
+      package_reqs
+        .iter()
+        .map(|r| r.name.clone())
+        .into_iter()
+        .collect::<Vec<_>>(),
+    )
+    .await?;
+
+  let mut resolver = GraphDependencyResolver::new(&mut graph, api);
+
+  // The package reqs 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)?;
+  }
+
+  resolver.resolve_pending().await?;
+
+  let result = graph.into_snapshot(api).await;
+  api.clear_memory_cache();
+  result
+}
+
 #[cfg(test)]
 mod test {
+  use deno_graph::npm::NpmPackageNv;
   use deno_graph::semver::Version;
 
-  use super::NpmPackageNodeId;
+  use super::NpmPackageId;
 
   #[test]
   fn serialize_npm_package_id() {
-    let id = NpmPackageNodeId {
-      name: "pkg-a".to_string(),
-      version: Version::parse_from_npm("1.2.3").unwrap(),
+    let id = NpmPackageId {
+      nv: NpmPackageNv {
+        name: "pkg-a".to_string(),
+        version: Version::parse_from_npm("1.2.3").unwrap(),
+      },
       peer_dependencies: vec![
-        NpmPackageNodeId {
-          name: "pkg-b".to_string(),
-          version: Version::parse_from_npm("3.2.1").unwrap(),
+        NpmPackageId {
+          nv: NpmPackageNv {
+            name: "pkg-b".to_string(),
+            version: Version::parse_from_npm("3.2.1").unwrap(),
+          },
           peer_dependencies: vec![
-            NpmPackageNodeId {
-              name: "pkg-c".to_string(),
-              version: Version::parse_from_npm("1.3.2").unwrap(),
+            NpmPackageId {
+              nv: NpmPackageNv {
+                name: "pkg-c".to_string(),
+                version: Version::parse_from_npm("1.3.2").unwrap(),
+              },
               peer_dependencies: vec![],
             },
-            NpmPackageNodeId {
-              name: "pkg-d".to_string(),
-              version: Version::parse_from_npm("2.3.4").unwrap(),
+            NpmPackageId {
+              nv: NpmPackageNv {
+                name: "pkg-d".to_string(),
+                version: Version::parse_from_npm("2.3.4").unwrap(),
+              },
               peer_dependencies: vec![],
             },
           ],
         },
-        NpmPackageNodeId {
-          name: "pkg-e".to_string(),
-          version: Version::parse_from_npm("2.3.1").unwrap(),
-          peer_dependencies: vec![NpmPackageNodeId {
-            name: "pkg-f".to_string(),
+        NpmPackageId {
+          nv: NpmPackageNv {
+            name: "pkg-e".to_string(),
             version: Version::parse_from_npm("2.3.1").unwrap(),
+          },
+          peer_dependencies: vec![NpmPackageId {
+            nv: NpmPackageNv {
+              name: "pkg-f".to_string(),
+              version: Version::parse_from_npm("2.3.1").unwrap(),
+            },
             peer_dependencies: vec![],
           }],
         },
@@ -456,6 +465,6 @@ mod test {
     // this shouldn't change because it's used in the lockfile
     let serialized = id.as_serialized();
     assert_eq!(serialized, "pkg-a@1.2.3_pkg-b@3.2.1__pkg-c@1.3.2__pkg-d@2.3.4_pkg-e@2.3.1__pkg-f@2.3.1");
-    assert_eq!(NpmPackageNodeId::from_serialized(&serialized).unwrap(), id);
+    assert_eq!(NpmPackageId::from_serialized(&serialized).unwrap(), id);
   }
 }