feat(unstable/npm): support peer dependencies (#16561)

This adds support for peer dependencies in npm packages.

1. If not found higher in the tree (ancestor and ancestor siblings),
peer dependencies are resolved like a dependency similar to npm 7.
2. Optional peer dependencies are only resolved if found higher in the
tree.
3. This creates "copy packages" or duplicates of a package when a
package has different resolution due to peer dependency resolution—see
https://pnpm.io/how-peers-are-resolved. Unlike pnpm though, duplicates
of packages will have `_1`, `_2`, etc. added to the end of the package
version in the directory in order to minimize the chance of hitting the
max file path limit on Windows. This is done for both the local
"node_modules" directory and also the global npm cache. The files are
hard linked in this case to reduce hard drive space.

This is a first pass and the code is definitely more inefficient than it
could be.

Closes #15823

1 files changed, 119 insertions, 55 deletions

diff --git a/cli/npm/resolvers/local.rs b/cli/npm/resolvers/local.rs
index cad940d56..678f776f3 100644
--- a/cli/npm/resolvers/local.rs
+++ b/cli/npm/resolvers/local.rs
@@ -24,12 +24,14 @@ use tokio::task::JoinHandle;
 use crate::fs_util;
 use crate::lockfile::Lockfile;
 use crate::npm::cache::should_sync_download;
+use crate::npm::cache::NpmPackageCacheFolderId;
 use crate::npm::resolution::NpmResolution;
 use crate::npm::resolution::NpmResolutionSnapshot;
 use crate::npm::NpmCache;
 use crate::npm::NpmPackageId;
 use crate::npm::NpmPackageReq;
-use crate::npm::NpmRegistryApi;
+use crate::npm::NpmResolutionPackage;
+use crate::npm::RealNpmRegistryApi;
 
 use super::common::ensure_registry_read_permission;
 use super::common::InnerNpmPackageResolver;
@@ -48,7 +50,7 @@ pub struct LocalNpmPackageResolver {
 impl LocalNpmPackageResolver {
   pub fn new(
     cache: NpmCache,
-    api: NpmRegistryApi,
+    api: RealNpmRegistryApi,
     node_modules_folder: PathBuf,
     initial_snapshot: Option<NpmResolutionSnapshot>,
   ) -> Self {
@@ -101,6 +103,35 @@ impl LocalNpmPackageResolver {
     // it's within the directory, so use it
     specifier.to_file_path().ok()
   }
+
+  fn get_package_id_folder(
+    &self,
+    package_id: &NpmPackageId,
+  ) -> Result<PathBuf, AnyError> {
+    match self.resolution.resolve_package_from_id(package_id) {
+      Some(package) => Ok(self.get_package_id_folder_from_package(&package)),
+      None => bail!(
+        "Could not find package information for '{}'",
+        package_id.as_serialized()
+      ),
+    }
+  }
+
+  fn get_package_id_folder_from_package(
+    &self,
+    package: &NpmResolutionPackage,
+  ) -> PathBuf {
+    // package is stored at:
+    // node_modules/.deno/<package_cache_folder_id_folder_name>/node_modules/<package_name>
+    self
+      .root_node_modules_path
+      .join(".deno")
+      .join(get_package_folder_id_folder_name(
+        &package.get_package_cache_folder_id(),
+      ))
+      .join("node_modules")
+      .join(&package.id.name)
+  }
 }
 
 impl InnerNpmPackageResolver for LocalNpmPackageResolver {
@@ -108,19 +139,8 @@ impl InnerNpmPackageResolver for LocalNpmPackageResolver {
     &self,
     pkg_req: &NpmPackageReq,
   ) -> Result<PathBuf, AnyError> {
-    let resolved_package =
-      self.resolution.resolve_package_from_deno_module(pkg_req)?;
-
-    // it might be at the full path if there are duplicate names
-    let fully_resolved_folder_path = join_package_name(
-      &self.root_node_modules_path,
-      &resolved_package.id.to_string(),
-    );
-    Ok(if fully_resolved_folder_path.exists() {
-      fully_resolved_folder_path
-    } else {
-      join_package_name(&self.root_node_modules_path, &resolved_package.id.name)
-    })
+    let package = self.resolution.resolve_package_from_deno_module(pkg_req)?;
+    Ok(self.get_package_id_folder_from_package(&package))
   }
 
   fn resolve_package_folder_from_package(
@@ -178,19 +198,9 @@ impl InnerNpmPackageResolver for LocalNpmPackageResolver {
   }
 
   fn package_size(&self, package_id: &NpmPackageId) -> Result<u64, AnyError> {
-    match self.resolution.resolve_package_from_id(package_id) {
-      Some(package) => Ok(fs_util::dir_size(
-        // package is stored at:
-        // node_modules/.deno/<package_id>/node_modules/<package_name>
-        &self
-          .root_node_modules_path
-          .join(".deno")
-          .join(package.id.to_string())
-          .join("node_modules")
-          .join(package.id.name),
-      )?),
-      None => bail!("Could not find package folder for '{}'", package_id),
-    }
+    let package_folder_path = self.get_package_id_folder(package_id)?;
+
+    Ok(fs_util::dir_size(&package_folder_path)?)
   }
 
   fn has_packages(&self) -> bool {
@@ -255,10 +265,6 @@ async fn sync_resolution_with_fs(
   registry_url: &Url,
   root_node_modules_dir_path: &Path,
 ) -> Result<(), AnyError> {
-  fn get_package_folder_name(package_id: &NpmPackageId) -> String {
-    package_id.to_string().replace('/', "+")
-  }
-
   let deno_local_registry_dir = root_node_modules_dir_path.join(".deno");
   fs::create_dir_all(&deno_local_registry_dir).with_context(|| {
     format!("Creating '{}'", deno_local_registry_dir.display())
@@ -267,34 +273,45 @@ async fn sync_resolution_with_fs(
   // 1. Write all the packages out the .deno directory.
   //
   // Copy (hardlink in future) <global_registry_cache>/<package_id>/ to
-  // node_modules/.deno/<package_id>/node_modules/<package_name>
+  // node_modules/.deno/<package_folder_id_folder_name>/node_modules/<package_name>
   let sync_download = should_sync_download();
-  let mut all_packages = snapshot.all_packages();
+  let mut package_partitions = snapshot.all_packages_partitioned();
   if sync_download {
     // we're running the tests not with --quiet
     // and we want the output to be deterministic
-    all_packages.sort_by(|a, b| a.id.cmp(&b.id));
+    package_partitions.packages.sort_by(|a, b| a.id.cmp(&b.id));
   }
   let mut handles: Vec<JoinHandle<Result<(), AnyError>>> =
-    Vec::with_capacity(all_packages.len());
-  for package in &all_packages {
-    let folder_name = get_package_folder_name(&package.id);
+    Vec::with_capacity(package_partitions.packages.len());
+  for package in &package_partitions.packages {
+    let folder_name =
+      get_package_folder_id_folder_name(&package.get_package_cache_folder_id());
     let folder_path = deno_local_registry_dir.join(&folder_name);
-    let initialized_file = folder_path.join("deno_initialized");
-    if !initialized_file.exists() {
+    let initialized_file = folder_path.join(".initialized");
+    if !cache.should_use_cache_for_npm_package(&package.id.name)
+      || !initialized_file.exists()
+    {
       let cache = cache.clone();
       let registry_url = registry_url.clone();
       let package = package.clone();
       let handle = tokio::task::spawn(async move {
         cache
-          .ensure_package(&package.id, &package.dist, &registry_url)
+          .ensure_package(
+            (&package.id.name, &package.id.version),
+            &package.dist,
+            &registry_url,
+          )
           .await?;
         let sub_node_modules = folder_path.join("node_modules");
         let package_path =
           join_package_name(&sub_node_modules, &package.id.name);
         fs::create_dir_all(&package_path)
           .with_context(|| format!("Creating '{}'", folder_path.display()))?;
-        let cache_folder = cache.package_folder(&package.id, &registry_url);
+        let cache_folder = cache.package_folder_for_name_and_version(
+          &package.id.name,
+          &package.id.version,
+          &registry_url,
+        );
         // for now copy, but in the future consider hard linking
         fs_util::copy_dir_recursive(&cache_folder, &package_path)?;
         // write out a file that indicates this folder has been initialized
@@ -314,16 +331,51 @@ async fn sync_resolution_with_fs(
     result??; // surface the first error
   }
 
-  // 2. Symlink all the dependencies into the .deno directory.
+  // 2. Create any "copy" packages, which are used for peer dependencies
+  for package in &package_partitions.copy_packages {
+    let package_cache_folder_id = package.get_package_cache_folder_id();
+    let destination_path = deno_local_registry_dir
+      .join(&get_package_folder_id_folder_name(&package_cache_folder_id));
+    let initialized_file = destination_path.join(".initialized");
+    if !initialized_file.exists() {
+      let sub_node_modules = destination_path.join("node_modules");
+      let package_path = join_package_name(&sub_node_modules, &package.id.name);
+      fs::create_dir_all(&package_path).with_context(|| {
+        format!("Creating '{}'", destination_path.display())
+      })?;
+      let source_path = join_package_name(
+        &deno_local_registry_dir
+          .join(&get_package_folder_id_folder_name(
+            &package_cache_folder_id.with_no_count(),
+          ))
+          .join("node_modules"),
+        &package.id.name,
+      );
+      fs_util::hard_link_dir_recursive(&source_path, &package_path)?;
+      // write out a file that indicates this folder has been initialized
+      fs::write(initialized_file, "")?;
+    }
+  }
+
+  let all_packages = package_partitions.into_all();
+
+  // 3. Symlink all the dependencies into the .deno directory.
   //
   // Symlink node_modules/.deno/<package_id>/node_modules/<dep_name> to
   // node_modules/.deno/<dep_id>/node_modules/<dep_package_name>
   for package in &all_packages {
     let sub_node_modules = deno_local_registry_dir
-      .join(&get_package_folder_name(&package.id))
+      .join(&get_package_folder_id_folder_name(
+        &package.get_package_cache_folder_id(),
+      ))
       .join("node_modules");
     for (name, dep_id) in &package.dependencies {
-      let dep_folder_name = get_package_folder_name(dep_id);
+      let dep_cache_folder_id = snapshot
+        .package_from_id(dep_id)
+        .unwrap()
+        .get_package_cache_folder_id();
+      let dep_folder_name =
+        get_package_folder_id_folder_name(&dep_cache_folder_id);
       let dep_folder_path = join_package_name(
         &deno_local_registry_dir
           .join(dep_folder_name)
@@ -337,7 +389,7 @@ async fn sync_resolution_with_fs(
     }
   }
 
-  // 3. Create all the packages in the node_modules folder, which are symlinks.
+  // 4. Create all the packages in the node_modules folder, which are symlinks.
   //
   // Symlink node_modules/<package_name> to
   // node_modules/.deno/<package_id>/node_modules/<package_name>
@@ -353,29 +405,41 @@ async fn sync_resolution_with_fs(
     let root_folder_name = if found_names.insert(package_id.name.clone()) {
       package_id.name.clone()
     } else if is_top_level {
-      package_id.to_string()
+      package_id.display()
     } else {
       continue; // skip, already handled
     };
-    let local_registry_package_path = deno_local_registry_dir
-      .join(&get_package_folder_name(&package_id))
-      .join("node_modules")
-      .join(&package_id.name);
+    let package = snapshot.package_from_id(&package_id).unwrap();
+    let local_registry_package_path = join_package_name(
+      &deno_local_registry_dir
+        .join(&get_package_folder_id_folder_name(
+          &package.get_package_cache_folder_id(),
+        ))
+        .join("node_modules"),
+      &package_id.name,
+    );
 
     symlink_package_dir(
       &local_registry_package_path,
       &join_package_name(root_node_modules_dir_path, &root_folder_name),
     )?;
-    if let Some(package) = snapshot.package_from_id(&package_id) {
-      for id in package.dependencies.values() {
-        pending_packages.push_back((id.clone(), false));
-      }
+    for id in package.dependencies.values() {
+      pending_packages.push_back((id.clone(), false));
     }
   }
 
   Ok(())
 }
 
+fn get_package_folder_id_folder_name(id: &NpmPackageCacheFolderId) -> String {
+  let copy_str = if id.copy_index == 0 {
+    "".to_string()
+  } else {
+    format!("_{}", id.copy_index)
+  };
+  format!("{}@{}{}", id.name, id.version, copy_str).replace('/', "+")
+}
+
 fn symlink_package_dir(
   old_path: &Path,
   new_path: &Path,