fix(npm): support non-all lowercase package names (#16669)

Supports package names that aren't all lowercase.

This stores the package with a leading underscore (since that's not
allowed in npm's registry and no package exists with a leading
underscore) then base32 encoded (A-Z0-9) so it can be lowercased and
avoid collisions.

Global cache dir:

```
$DENO_DIR/npm/registry.npmjs.org/_{base32_encode(package_name).to_lowercase()}/{version}
```

node_modules dir `.deno` folder:

```
node_modules/.deno/_{base32_encode(package_name).to_lowercase()}@{version}/node_modules/<package-name>
```

Within node_modules folder:

```
node_modules/<package-name>
```

So, direct childs of the node_modules folder can have collisions between
packages like `JSON` vs `json`, but this is already something npm itself
doesn't handle well. Plus, Deno doesn't actually ever resolve to the
`node_modules/<package-name>` folder, but just has that for
compatibility. Additionally, packages in the `.deno` dir could have
collissions if they have multiple dependencies that only differ in
casing or a dependency that has different casing, but if someone is
doing that then they're already going to have trouble with npm and they
are asking for trouble in general.

12 files changed, 146 insertions, 20 deletions

diff --git a/cli/Cargo.toml b/cli/Cargo.toml
index 6bc857cae..4a07a0c4a 100644
--- a/cli/Cargo.toml
+++ b/cli/Cargo.toml
@@ -61,6 +61,7 @@ deno_task_shell = "0.7.2"
 napi_sym = { path = "./napi_sym", version = "0.7.0" }
 
 atty = "=0.2.14"
+base32 = "=0.4.0"
 base64 = "=0.13.1"
 cache_control = "=0.2.0"
 chrono = { version = "=0.4.22", default-features = false, features = ["clock"] }
diff --git a/cli/npm/cache.rs b/cli/npm/cache.rs
index e5ce3dfdd..b052f89cd 100644
--- a/cli/npm/cache.rs
+++ b/cli/npm/cache.rs
@@ -1,6 +1,5 @@
 // Copyright 2018-2022 the Deno authors. All rights reserved. MIT license.
 
-use std::borrow::Cow;
 use std::fs;
 use std::path::Path;
 use std::path::PathBuf;
@@ -208,24 +207,18 @@ impl ReadonlyNpmCache {
 
   pub fn package_name_folder(&self, name: &str, registry_url: &Url) -> PathBuf {
     let mut dir = self.registry_folder(registry_url);
-    let parts = name.split('/').map(Cow::Borrowed).collect::<Vec<_>>();
     if name.to_lowercase() != name {
-      // Lowercase package names introduce complications.
-      // When implementing this ensure:
-      // 1. It works on case insensitive filesystems. ex. JSON should not
-      //    conflict with json... yes you read that right, those are separate
-      //    packages.
-      // 2. We can figure out the package id from the path. This is used
-      //    in resolve_package_id_from_specifier
-      // Probably use a hash of the package name at `npm/-/<hash>` then create
-      // a mapping for these package names.
-      todo!("deno currently doesn't support npm package names that are not all lowercase");
-    }
-    // ensure backslashes are used on windows
-    for part in parts {
-      dir = dir.join(&*part);
+      let encoded_name = mixed_case_package_name_encode(name);
+      // Using the encoded directory may have a collision with an actual package name
+      // so prefix it with an underscore since npm packages can't start with that
+      dir.join(format!("_{}", encoded_name))
+    } else {
+      // ensure backslashes are used on windows
+      for part in name.split('/') {
+        dir = dir.join(part);
+      }
+      dir
     }
-    dir
   }
 
   pub fn registry_folder(&self, registry_url: &Url) -> PathBuf {
@@ -262,11 +255,27 @@ impl ReadonlyNpmCache {
       ))
       // this not succeeding indicates a fatal issue, so unwrap
       .unwrap();
-    let relative_url = registry_root_dir.make_relative(specifier)?;
+    let mut relative_url = registry_root_dir.make_relative(specifier)?;
     if relative_url.starts_with("../") {
       return None;
     }
 
+    // base32 decode the url if it starts with an underscore
+    // * Ex. _{base32(package_name)}/
+    if let Some(end_url) = relative_url.strip_prefix('_') {
+      let mut parts = end_url
+        .split('/')
+        .map(ToOwned::to_owned)
+        .collect::<Vec<_>>();
+      match mixed_case_package_name_decode(&parts[0]) {
+        Some(part) => {
+          parts[0] = part;
+        }
+        None => return None,
+      }
+      relative_url = parts.join("/");
+    }
+
     // examples:
     // * chalk/5.0.1/
     // * @types/chalk/5.0.1/
@@ -473,6 +482,21 @@ impl NpmCache {
   }
 }
 
+pub fn mixed_case_package_name_encode(name: &str) -> String {
+  // use base32 encoding because it's reversable and the character set
+  // only includes the characters within 0-9 and A-Z so it can be lower cased
+  base32::encode(
+    base32::Alphabet::RFC4648 { padding: false },
+    name.as_bytes(),
+  )
+  .to_lowercase()
+}
+
+pub fn mixed_case_package_name_decode(name: &str) -> Option<String> {
+  base32::decode(base32::Alphabet::RFC4648 { padding: false }, name)
+    .and_then(|b| String::from_utf8(b).ok())
+}
+
 #[cfg(test)]
 mod test {
   use deno_core::url::Url;
@@ -482,7 +506,7 @@ mod test {
   use crate::npm::semver::NpmVersion;
 
   #[test]
-  fn should_get_lowercase_package_folder() {
+  fn should_get_package_folder() {
     let root_dir = crate::deno_dir::DenoDir::new(None).unwrap().root;
     let cache = ReadonlyNpmCache::new(root_dir.clone());
     let registry_url = Url::parse("https://registry.npmjs.org/").unwrap();
@@ -516,5 +540,35 @@ mod test {
         .join("json")
         .join("1.2.5_1"),
     );
+
+    assert_eq!(
+      cache.package_folder_for_id(
+        &NpmPackageCacheFolderId {
+          name: "JSON".to_string(),
+          version: NpmVersion::parse("2.1.5").unwrap(),
+          copy_index: 0,
+        },
+        &registry_url,
+      ),
+      root_dir
+        .join("registry.npmjs.org")
+        .join("_jjju6tq")
+        .join("2.1.5"),
+    );
+
+    assert_eq!(
+      cache.package_folder_for_id(
+        &NpmPackageCacheFolderId {
+          name: "@types/JSON".to_string(),
+          version: NpmVersion::parse("2.1.5").unwrap(),
+          copy_index: 0,
+        },
+        &registry_url,
+      ),
+      root_dir
+        .join("registry.npmjs.org")
+        .join("_ib2hs4dfomxuuu2pjy")
+        .join("2.1.5"),
+    );
   }
 }
diff --git a/cli/npm/resolvers/local.rs b/cli/npm/resolvers/local.rs
index 367198965..0a47a7ff1 100644
--- a/cli/npm/resolvers/local.rs
+++ b/cli/npm/resolvers/local.rs
@@ -2,6 +2,7 @@
 
 //! Code for local node_modules resolution.
 
+use std::borrow::Cow;
 use std::collections::HashSet;
 use std::collections::VecDeque;
 use std::fs;
@@ -23,6 +24,7 @@ use tokio::task::JoinHandle;
 
 use crate::fs_util;
 use crate::lockfile::Lockfile;
+use crate::npm::cache::mixed_case_package_name_encode;
 use crate::npm::cache::should_sync_download;
 use crate::npm::cache::NpmPackageCacheFolderId;
 use crate::npm::resolution::NpmResolution;
@@ -438,7 +440,12 @@ fn get_package_folder_id_folder_name(id: &NpmPackageCacheFolderId) -> String {
   } else {
     format!("_{}", id.copy_index)
   };
-  format!("{}@{}{}", id.name, id.version, copy_str).replace('/', "+")
+  let name = if id.name.to_lowercase() == id.name {
+    Cow::Borrowed(&id.name)
+  } else {
+    Cow::Owned(format!("_{}", mixed_case_package_name_encode(&id.name)))
+  };
+  format!("{}@{}{}", name, id.version, copy_str).replace('/', "+")
 }
 
 fn symlink_package_dir(
diff --git a/cli/tests/integration/npm_tests.rs b/cli/tests/integration/npm_tests.rs
index 787dab815..a530d7545 100644
--- a/cli/tests/integration/npm_tests.rs
+++ b/cli/tests/integration/npm_tests.rs
@@ -123,6 +123,24 @@ itest!(cjs_module_export_assignment_number {
   http_server: true,
 });
 
+itest!(mixed_case_package_name_global_dir {
+  args: "run npm/mixed_case_package_name/global.ts",
+  output: "npm/mixed_case_package_name/global.out",
+  exit_code: 0,
+  envs: env_vars(),
+  http_server: true,
+});
+
+itest!(mixed_case_package_name_local_dir {
+  args:
+    "run --node-modules-dir -A $TESTDATA/npm/mixed_case_package_name/local.ts",
+  output: "npm/mixed_case_package_name/local.out",
+  exit_code: 0,
+  envs: env_vars(),
+  http_server: true,
+  temp_cwd: true,
+});
+
 // FIXME(bartlomieju): npm: specifiers are not handled in dynamic imports
 // at the moment
 // itest!(dynamic_import {
diff --git a/cli/tests/testdata/npm/mixed_case_package_name/global.out b/cli/tests/testdata/npm/mixed_case_package_name/global.out
new file mode 100644
index 000000000..72417dd71
--- /dev/null
+++ b/cli/tests/testdata/npm/mixed_case_package_name/global.out
@@ -0,0 +1,5 @@
+Download http://localhost:4545/npm/registry/@denotest/MixedCase
+Download http://localhost:4545/npm/registry/@denotest/CAPITALS
+Download http://localhost:4545/npm/registry/@denotest/CAPITALS/1.0.0.tgz
+Download http://localhost:4545/npm/registry/@denotest/MixedCase/1.0.0.tgz
+5
diff --git a/cli/tests/testdata/npm/mixed_case_package_name/global.ts b/cli/tests/testdata/npm/mixed_case_package_name/global.ts
new file mode 100644
index 000000000..a721b3d78
--- /dev/null
+++ b/cli/tests/testdata/npm/mixed_case_package_name/global.ts
@@ -0,0 +1,2 @@
+import value from "npm:@denotest/MixedCase";
+console.log(value);
diff --git a/cli/tests/testdata/npm/mixed_case_package_name/local.out b/cli/tests/testdata/npm/mixed_case_package_name/local.out
new file mode 100644
index 000000000..b61be3d35
--- /dev/null
+++ b/cli/tests/testdata/npm/mixed_case_package_name/local.out
@@ -0,0 +1,7 @@
+Download http://localhost:4545/npm/registry/@denotest/MixedCase
+Download http://localhost:4545/npm/registry/@denotest/CAPITALS
+Download http://localhost:4545/npm/registry/@denotest/CAPITALS/1.0.0.tgz
+Download http://localhost:4545/npm/registry/@denotest/MixedCase/1.0.0.tgz
+5
+true
+true
diff --git a/cli/tests/testdata/npm/mixed_case_package_name/local.ts b/cli/tests/testdata/npm/mixed_case_package_name/local.ts
new file mode 100644
index 000000000..6ca6cb581
--- /dev/null
+++ b/cli/tests/testdata/npm/mixed_case_package_name/local.ts
@@ -0,0 +1,18 @@
+import value from "npm:@denotest/MixedCase";
+console.log(value);
+console.log(pathExists("./node_modules/.deno"));
+console.log(
+  pathExists("./node_modules/.deno/_ibsgk3tporsxg5bpinavaskuifgfg@1.0.0"),
+);
+
+function pathExists(filePath: string) {
+  try {
+    Deno.lstatSync(filePath);
+    return true;
+  } catch (error) {
+    if (error instanceof Deno.errors.NotFound) {
+      return false;
+    }
+    throw error;
+  }
+}
diff --git a/cli/tests/testdata/npm/registry/@denotest/CAPITALS/1.0.0/index.js b/cli/tests/testdata/npm/registry/@denotest/CAPITALS/1.0.0/index.js
new file mode 100644
index 000000000..f4e8d9d29
--- /dev/null
+++ b/cli/tests/testdata/npm/registry/@denotest/CAPITALS/1.0.0/index.js
@@ -0,0 +1 @@
+module.exports = 5;
diff --git a/cli/tests/testdata/npm/registry/@denotest/CAPITALS/1.0.0/package.json b/cli/tests/testdata/npm/registry/@denotest/CAPITALS/1.0.0/package.json
new file mode 100644
index 000000000..e897d0023
--- /dev/null
+++ b/cli/tests/testdata/npm/registry/@denotest/CAPITALS/1.0.0/package.json
@@ -0,0 +1,4 @@
+{
+  "name": "@denotest/CAPITALS",
+  "version": "1.0.0"
+}
diff --git a/cli/tests/testdata/npm/registry/@denotest/MixedCase/1.0.0/index.js b/cli/tests/testdata/npm/registry/@denotest/MixedCase/1.0.0/index.js
new file mode 100644
index 000000000..fe1cfe547
--- /dev/null
+++ b/cli/tests/testdata/npm/registry/@denotest/MixedCase/1.0.0/index.js
@@ -0,0 +1,2 @@
+const value = require("@denotest/CAPITALS");
+module.exports = value;
diff --git a/cli/tests/testdata/npm/registry/@denotest/MixedCase/1.0.0/package.json b/cli/tests/testdata/npm/registry/@denotest/MixedCase/1.0.0/package.json
new file mode 100644
index 000000000..2a36cb357
--- /dev/null
+++ b/cli/tests/testdata/npm/registry/@denotest/MixedCase/1.0.0/package.json
@@ -0,0 +1,7 @@
+{
+  "name": "@denotest/MixedCase",
+  "version": "1.0.0",
+  "dependencies": {
+    "@denotest/CAPITALS": "^1"
+  }
+}