feat(unstable): ability to `npm install` then `deno run main.ts` (#20967)

This PR adds a new unstable "bring your own node_modules" (BYONM)
functionality currently behind a `--unstable-byonm` flag (`"unstable":
["byonm"]` in a deno.json).

This enables users to run a separate install command (ex. `npm install`,
`pnpm install`) then run `deno run main.ts` and Deno will respect the
layout of the node_modules directory as setup by the separate install
command. It also works with npm/yarn/pnpm workspaces.

For this PR, the behaviour is opted into by specifying
`--unstable-byonm`/`"unstable": ["byonm"]`, but in the future we may
make this the default behaviour as outlined in
https://github.com/denoland/deno/issues/18967#issuecomment-1761248941

This is an extremely rough initial implementation. Errors are
terrible in this and the LSP requires frequent restarts. Improvements
will be done in follow up PRs.

5 files changed, 313 insertions, 64 deletions

diff --git a/cli/npm/byonm.rs b/cli/npm/byonm.rs
new file mode 100644
index 000000000..7aba83915
--- /dev/null
+++ b/cli/npm/byonm.rs
@@ -0,0 +1,274 @@
+// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license.
+
+use std::borrow::Cow;
+use std::path::Path;
+use std::path::PathBuf;
+use std::sync::Arc;
+
+use deno_ast::ModuleSpecifier;
+use deno_core::anyhow::bail;
+use deno_core::error::AnyError;
+use deno_core::serde_json;
+use deno_runtime::deno_fs::FileSystem;
+use deno_runtime::deno_node::NodePermissions;
+use deno_runtime::deno_node::NodeResolutionMode;
+use deno_runtime::deno_node::NpmResolver;
+use deno_runtime::deno_node::PackageJson;
+use deno_semver::package::PackageReq;
+
+use crate::args::package_json::get_local_package_json_version_reqs;
+use crate::args::NpmProcessState;
+use crate::args::NpmProcessStateKind;
+use crate::util::fs::canonicalize_path_maybe_not_exists;
+use crate::util::path::specifier_to_file_path;
+
+use super::common::types_package_name;
+use super::CliNpmResolver;
+use super::InnerCliNpmResolverRef;
+
+pub struct CliNpmResolverByonmCreateOptions {
+  pub fs: Arc<dyn FileSystem>,
+  pub root_node_modules_dir: PathBuf,
+}
+
+pub fn create_byonm_npm_resolver(
+  options: CliNpmResolverByonmCreateOptions,
+) -> Arc<dyn CliNpmResolver> {
+  Arc::new(ByonmCliNpmResolver {
+    fs: options.fs,
+    root_node_modules_dir: options.root_node_modules_dir,
+  })
+}
+
+#[derive(Debug)]
+pub struct ByonmCliNpmResolver {
+  fs: Arc<dyn FileSystem>,
+  root_node_modules_dir: PathBuf,
+}
+
+impl NpmResolver for ByonmCliNpmResolver {
+  fn resolve_package_folder_from_package(
+    &self,
+    name: &str,
+    referrer: &ModuleSpecifier,
+    mode: NodeResolutionMode,
+  ) -> Result<PathBuf, AnyError> {
+    fn inner(
+      fs: &dyn FileSystem,
+      name: &str,
+      package_root_path: &Path,
+      referrer: &ModuleSpecifier,
+      mode: NodeResolutionMode,
+    ) -> Result<PathBuf, AnyError> {
+      let mut current_folder = package_root_path;
+      loop {
+        let node_modules_folder = if current_folder.ends_with("node_modules") {
+          Cow::Borrowed(current_folder)
+        } else {
+          Cow::Owned(current_folder.join("node_modules"))
+        };
+
+        // attempt to resolve the types package first, then fallback to the regular package
+        if mode.is_types() && !name.starts_with("@types/") {
+          let sub_dir =
+            join_package_name(&node_modules_folder, &types_package_name(name));
+          if fs.is_dir_sync(&sub_dir) {
+            return Ok(sub_dir);
+          }
+        }
+
+        let sub_dir = join_package_name(&node_modules_folder, name);
+        if fs.is_dir_sync(&sub_dir) {
+          return Ok(sub_dir);
+        }
+
+        if let Some(parent) = current_folder.parent() {
+          current_folder = parent;
+        } else {
+          break;
+        }
+      }
+
+      bail!(
+        "could not find package '{}' from referrer '{}'.",
+        name,
+        referrer
+      );
+    }
+
+    let package_root_path =
+      self.resolve_package_folder_from_path(referrer)?.unwrap(); // todo(byonm): don't unwrap
+    let path = inner(&*self.fs, name, &package_root_path, referrer, mode)?;
+    Ok(self.fs.realpath_sync(&path)?)
+  }
+
+  fn resolve_package_folder_from_path(
+    &self,
+    specifier: &deno_core::ModuleSpecifier,
+  ) -> Result<Option<PathBuf>, AnyError> {
+    let path = specifier.to_file_path().unwrap(); // todo(byonm): don't unwrap
+    let path = self.fs.realpath_sync(&path)?;
+    if self.in_npm_package(specifier) {
+      let mut path = path.as_path();
+      while let Some(parent) = path.parent() {
+        if parent
+          .file_name()
+          .and_then(|f| f.to_str())
+          .map(|s| s.to_ascii_lowercase())
+          .as_deref()
+          == Some("node_modules")
+        {
+          return Ok(Some(path.to_path_buf()));
+        } else {
+          path = parent;
+        }
+      }
+    } else {
+      // find the folder with a package.json
+      // todo(dsherret): not exactly correct, but good enough for a first pass
+      let mut path = path.as_path();
+      while let Some(parent) = path.parent() {
+        if parent.join("package.json").exists() {
+          return Ok(Some(parent.to_path_buf()));
+        } else {
+          path = parent;
+        }
+      }
+    }
+    Ok(None)
+  }
+
+  fn in_npm_package(&self, specifier: &ModuleSpecifier) -> bool {
+    specifier.scheme() == "file"
+      && specifier
+        .path()
+        .to_ascii_lowercase()
+        .contains("/node_modules/")
+  }
+
+  fn ensure_read_permission(
+    &self,
+    permissions: &dyn NodePermissions,
+    path: &Path,
+  ) -> Result<(), AnyError> {
+    if !path
+      .components()
+      .any(|c| c.as_os_str().to_ascii_lowercase() == "node_modules")
+    {
+      permissions.check_read(path)?;
+    }
+    Ok(())
+  }
+}
+
+impl CliNpmResolver for ByonmCliNpmResolver {
+  fn into_npm_resolver(self: Arc<Self>) -> Arc<dyn NpmResolver> {
+    self
+  }
+
+  fn clone_snapshotted(&self) -> Arc<dyn CliNpmResolver> {
+    Arc::new(Self {
+      fs: self.fs.clone(),
+      root_node_modules_dir: self.root_node_modules_dir.clone(),
+    })
+  }
+
+  fn as_inner(&self) -> InnerCliNpmResolverRef {
+    InnerCliNpmResolverRef::Byonm(self)
+  }
+
+  fn root_node_modules_path(&self) -> Option<std::path::PathBuf> {
+    Some(self.root_node_modules_dir.clone())
+  }
+
+  fn resolve_pkg_folder_from_deno_module_req(
+    &self,
+    req: &PackageReq,
+    referrer: &ModuleSpecifier,
+  ) -> Result<PathBuf, AnyError> {
+    fn resolve_from_package_json(
+      req: &PackageReq,
+      fs: &dyn FileSystem,
+      path: PathBuf,
+    ) -> Result<PathBuf, AnyError> {
+      let package_json = PackageJson::load_skip_read_permission(fs, path)?;
+      let deps = get_local_package_json_version_reqs(&package_json);
+      for (key, value) in deps {
+        if let Ok(value) = value {
+          if value.name == req.name
+            && value.version_req.intersects(&req.version_req)
+          {
+            let package_path = package_json
+              .path
+              .parent()
+              .unwrap()
+              .join("node_modules")
+              .join(key);
+            return Ok(canonicalize_path_maybe_not_exists(&package_path)?);
+          }
+        }
+      }
+      bail!(
+        concat!(
+          "Could not find a matching package for 'npm:{}' in '{}'. ",
+          "You must specify this as a package.json dependency when the ",
+          "node_modules folder is not managed by Deno.",
+        ),
+        req,
+        package_json.path.display()
+      );
+    }
+
+    // attempt to resolve the npm specifier from the referrer's package.json,
+    // but otherwise fallback to the project's package.json
+    if let Ok(file_path) = specifier_to_file_path(referrer) {
+      let mut current_path = file_path.as_path();
+      while let Some(dir_path) = current_path.parent() {
+        let package_json_path = dir_path.join("package.json");
+        if self.fs.exists_sync(&package_json_path) {
+          return resolve_from_package_json(
+            req,
+            self.fs.as_ref(),
+            package_json_path,
+          );
+        }
+        current_path = dir_path;
+      }
+    }
+
+    resolve_from_package_json(
+      req,
+      self.fs.as_ref(),
+      self
+        .root_node_modules_dir
+        .parent()
+        .unwrap()
+        .join("package.json"),
+    )
+  }
+
+  fn get_npm_process_state(&self) -> String {
+    serde_json::to_string(&NpmProcessState {
+      kind: NpmProcessStateKind::Byonm,
+      local_node_modules_path: Some(
+        self.root_node_modules_dir.to_string_lossy().to_string(),
+      ),
+    })
+    .unwrap()
+  }
+
+  fn check_state_hash(&self) -> Option<u64> {
+    // it is very difficult to determine the check state hash for byonm
+    // so we just return None to signify check caching is not supported
+    None
+  }
+}
+
+fn join_package_name(path: &Path, package_name: &str) -> PathBuf {
+  let mut path = path.to_path_buf();
+  // ensure backslashes are used on windows
+  for part in package_name.split('/') {
+    path = path.join(part);
+  }
+  path
+}
diff --git a/cli/npm/managed/mod.rs b/cli/npm/managed/mod.rs
index b85f1130f..68b5c2134 100644
--- a/cli/npm/managed/mod.rs
+++ b/cli/npm/managed/mod.rs
@@ -27,6 +27,7 @@ use deno_semver::package::PackageReq;
 
 use crate::args::Lockfile;
 use crate::args::NpmProcessState;
+use crate::args::NpmProcessStateKind;
 use crate::args::PackageJsonDepsProvider;
 use crate::cache::FastInsecureHasher;
 use crate::util::fs::canonicalize_path_maybe_not_exists_with_fs;
@@ -508,7 +509,18 @@ impl NpmResolver for ManagedCliNpmResolver {
     &self,
     specifier: &ModuleSpecifier,
   ) -> Result<Option<PathBuf>, AnyError> {
-    self.resolve_pkg_folder_from_specifier(specifier)
+    let Some(path) = self
+      .fs_resolver
+      .resolve_package_folder_from_specifier(specifier)?
+    else {
+      return Ok(None);
+    };
+    log::debug!(
+      "Resolved package folder of {} to {}",
+      specifier,
+      path.display()
+    );
+    Ok(Some(path))
   }
 
   fn in_npm_package(&self, specifier: &ModuleSpecifier) -> bool {
@@ -568,27 +580,6 @@ impl CliNpmResolver for ManagedCliNpmResolver {
     self.fs_resolver.node_modules_path()
   }
 
-  /// Resolve the root folder of the package the provided specifier is in.
-  ///
-  /// This will error when the provided specifier is not in an npm package.
-  fn resolve_pkg_folder_from_specifier(
-    &self,
-    specifier: &ModuleSpecifier,
-  ) -> Result<Option<PathBuf>, AnyError> {
-    let Some(path) = self
-      .fs_resolver
-      .resolve_package_folder_from_specifier(specifier)?
-    else {
-      return Ok(None);
-    };
-    log::debug!(
-      "Resolved package folder of {} to {}",
-      specifier,
-      path.display()
-    );
-    Ok(Some(path))
-  }
-
   fn resolve_pkg_folder_from_deno_module_req(
     &self,
     req: &PackageReq,
@@ -601,10 +592,12 @@ impl CliNpmResolver for ManagedCliNpmResolver {
   /// Gets the state of npm for the process.
   fn get_npm_process_state(&self) -> String {
     serde_json::to_string(&NpmProcessState {
-      snapshot: self
-        .resolution
-        .serialized_valid_snapshot()
-        .into_serialized(),
+      kind: NpmProcessStateKind::Snapshot(
+        self
+          .resolution
+          .serialized_valid_snapshot()
+          .into_serialized(),
+      ),
       local_node_modules_path: self
         .fs_resolver
         .node_modules_path()
diff --git a/cli/npm/managed/resolvers/local.rs b/cli/npm/managed/resolvers/local.rs
index 2d774518a..a4a8550f1 100644
--- a/cli/npm/managed/resolvers/local.rs
+++ b/cli/npm/managed/resolvers/local.rs
@@ -36,7 +36,6 @@ use deno_runtime::deno_core::futures;
 use deno_runtime::deno_fs;
 use deno_runtime::deno_node::NodePermissions;
 use deno_runtime::deno_node::NodeResolutionMode;
-use deno_runtime::deno_node::PackageJson;
 use deno_semver::package::PackageNv;
 use serde::Deserialize;
 use serde::Serialize;
@@ -181,23 +180,8 @@ impl NpmPackageFsResolver for LocalNpmPackageResolver {
       } else {
         Cow::Owned(current_folder.join("node_modules"))
       };
-      let sub_dir = join_package_name(&node_modules_folder, name);
-      if self.fs.is_dir_sync(&sub_dir) {
-        // if doing types resolution, only resolve the package if it specifies a types property
-        if mode.is_types() && !name.starts_with("@types/") {
-          let package_json = PackageJson::load_skip_read_permission(
-            &*self.fs,
-            sub_dir.join("package.json"),
-          )?;
-          if package_json.types.is_some() {
-            return Ok(sub_dir);
-          }
-        } else {
-          return Ok(sub_dir);
-        }
-      }
 
-      // if doing type resolution, check for the existence of a @types package
+      // attempt to resolve the types package first, then fallback to the regular package
       if mode.is_types() && !name.starts_with("@types/") {
         let sub_dir =
           join_package_name(&node_modules_folder, &types_package_name(name));
@@ -206,6 +190,11 @@ impl NpmPackageFsResolver for LocalNpmPackageResolver {
         }
       }
 
+      let sub_dir = join_package_name(&node_modules_folder, name);
+      if self.fs.is_dir_sync(&sub_dir) {
+        return Ok(sub_dir);
+      }
+
       if current_folder == self.root_node_modules_path {
         bail!(
           "could not find package '{}' from referrer '{}'.",
diff --git a/cli/npm/managed/tarball.rs b/cli/npm/managed/tarball.rs
index e72b1afc8..17ab7711f 100644
--- a/cli/npm/managed/tarball.rs
+++ b/cli/npm/managed/tarball.rs
@@ -52,15 +52,15 @@ fn verify_tarball_integrity(
       let mut hash_ctx = Context::new(algo);
       hash_ctx.update(data);
       let digest = hash_ctx.finish();
-      let tarball_checksum = base64::encode(digest.as_ref()).to_lowercase();
-      (tarball_checksum, base64_hash.to_lowercase())
+      let tarball_checksum = base64::encode(digest.as_ref());
+      (tarball_checksum, base64_hash)
     }
     NpmPackageVersionDistInfoIntegrity::LegacySha1Hex(hex) => {
       let mut hash_ctx = Context::new(&ring::digest::SHA1_FOR_LEGACY_USE_ONLY);
       hash_ctx.update(data);
       let digest = hash_ctx.finish();
-      let tarball_checksum = hex::encode(digest.as_ref()).to_lowercase();
-      (tarball_checksum, hex.to_lowercase())
+      let tarball_checksum = hex::encode(digest.as_ref());
+      (tarball_checksum, hex)
     }
     NpmPackageVersionDistInfoIntegrity::UnknownIntegrity(integrity) => {
       bail!(
@@ -71,7 +71,7 @@ fn verify_tarball_integrity(
     }
   };
 
-  if tarball_checksum != expected_checksum {
+  if tarball_checksum != *expected_checksum {
     bail!(
       "Tarball checksum did not match what was provided by npm registry for {}.\n\nExpected: {}\nActual: {}",
       package,
@@ -158,7 +158,7 @@ mod test {
       version: Version::parse_from_npm("1.0.0").unwrap(),
     };
     let actual_checksum =
-      "z4phnx7vul3xvchq1m2ab9yg5aulvxxcg/spidns6c5h0ne8xyxysp+dgnkhfuwvy7kxvudbeoglodj6+sfapg==";
+      "z4PhNX7vuL3xVChQ1m2AB9Yg5AULVxXcg/SpIdNs6c5H0NE8XYXysP+DGNKHfuwvY7kxvUdBeoGlODJ6+SfaPg==";
     assert_eq!(
       verify_tarball_integrity(
         &package,
@@ -195,7 +195,7 @@ mod test {
       .to_string(),
       concat!(
         "Tarball checksum did not match what was provided by npm ",
-        "registry for package@1.0.0.\n\nExpected: test\nActual: 2jmj7l5rsw0yvb/vlwaykk/ybwk=",
+        "registry for package@1.0.0.\n\nExpected: test\nActual: 2jmj7l5rSw0yVb/vlWAYkK/YBwk=",
       ),
     );
     assert_eq!(
diff --git a/cli/npm/mod.rs b/cli/npm/mod.rs
index 81f46419e..761c99dba 100644
--- a/cli/npm/mod.rs
+++ b/cli/npm/mod.rs
@@ -1,5 +1,6 @@
 // Copyright 2018-2023 the Deno authors. All rights reserved. MIT license.
 
+mod byonm;
 mod cache_dir;
 mod common;
 mod managed;
@@ -12,17 +13,18 @@ use deno_core::error::AnyError;
 use deno_runtime::deno_node::NpmResolver;
 use deno_semver::package::PackageReq;
 
+pub use self::byonm::CliNpmResolverByonmCreateOptions;
 pub use self::cache_dir::NpmCacheDir;
 pub use self::managed::CliNpmResolverManagedCreateOptions;
 pub use self::managed::CliNpmResolverManagedPackageJsonInstallerOption;
 pub use self::managed::CliNpmResolverManagedSnapshotOption;
 pub use self::managed::ManagedCliNpmResolver;
 
+use self::byonm::ByonmCliNpmResolver;
+
 pub enum CliNpmResolverCreateOptions {
   Managed(CliNpmResolverManagedCreateOptions),
-  // todo(dsherret): implement this
-  #[allow(dead_code)]
-  Byonm,
+  Byonm(CliNpmResolverByonmCreateOptions),
 }
 
 pub async fn create_cli_npm_resolver_for_lsp(
@@ -33,7 +35,7 @@ pub async fn create_cli_npm_resolver_for_lsp(
     Managed(options) => {
       managed::create_managed_npm_resolver_for_lsp(options).await
     }
-    Byonm => todo!(),
+    Byonm(options) => byonm::create_byonm_npm_resolver(options),
   }
 }
 
@@ -43,7 +45,7 @@ pub async fn create_cli_npm_resolver(
   use CliNpmResolverCreateOptions::*;
   match options {
     Managed(options) => managed::create_managed_npm_resolver(options).await,
-    Byonm => todo!(),
+    Byonm(options) => Ok(byonm::create_byonm_npm_resolver(options)),
   }
 }
 
@@ -76,12 +78,6 @@ pub trait CliNpmResolver: NpmResolver {
 
   fn root_node_modules_path(&self) -> Option<PathBuf>;
 
-  /// Resolve the root folder of the package the provided specifier is in.
-  fn resolve_pkg_folder_from_specifier(
-    &self,
-    specifier: &ModuleSpecifier,
-  ) -> Result<Option<PathBuf>, AnyError>;
-
   fn resolve_pkg_folder_from_deno_module_req(
     &self,
     req: &PackageReq,
@@ -95,6 +91,3 @@ pub trait CliNpmResolver: NpmResolver {
   /// or `None` if the state currently can't be determined.
   fn check_state_hash(&self) -> Option<u64>;
 }
-
-// todo(#18967): implement this
-pub struct ByonmCliNpmResolver;