fix(cli): Prefer npm bin entries provided by packages closer to the root (#24024)

Fixes #24012.

In the case of multiple packages providing a binary with a same name, we
were basically leaving the results undefined (since we set up things in
parallel, and whichever got set up first won). In addition, we were
warning about these cases, even though it's a situation that's expected
to occur.

Instead, in the case of a collision in the binary names, we prefer the
binary provided by the package with the least depth in the dependency
tree.

While I was at it, I also took moved more code to `bin_entries.rs` since
it was starting to get a bit cluttered.

11 files changed, 309 insertions, 63 deletions

diff --git a/cli/npm/managed/resolvers/local.rs b/cli/npm/managed/resolvers/local.rs
index d9cf79c08..f0c2a3f65 100644
--- a/cli/npm/managed/resolvers/local.rs
+++ b/cli/npm/managed/resolvers/local.rs
@@ -292,7 +292,7 @@ async fn sync_resolution_with_fs(
     Vec::with_capacity(package_partitions.packages.len());
   let mut newest_packages_by_name: HashMap<&String, &NpmResolutionPackage> =
     HashMap::with_capacity(package_partitions.packages.len());
-  let bin_entries_to_setup = Arc::new(Mutex::new(Vec::with_capacity(16)));
+  let bin_entries = Arc::new(Mutex::new(bin_entries::BinEntries::new()));
   for package in &package_partitions.packages {
     if let Some(current_pkg) =
       newest_packages_by_name.get_mut(&package.id.nv.name)
@@ -320,7 +320,7 @@ async fn sync_resolution_with_fs(
       let pb = progress_bar.clone();
       let cache = cache.clone();
       let package = package.clone();
-      let bin_entries_to_setup = bin_entries_to_setup.clone();
+      let bin_entries_to_setup = bin_entries.clone();
       let handle = spawn(async move {
         cache.ensure_package(&package.id.nv, &package.dist).await?;
         let pb_guard = pb.update_with_prompt(
@@ -348,7 +348,7 @@ async fn sync_resolution_with_fs(
         if package.bin.is_some() {
           bin_entries_to_setup
             .lock()
-            .push((package.clone(), package_path));
+            .add(package.clone(), package_path);
         }
 
         // finally stop showing the progress bar
@@ -482,46 +482,8 @@ async fn sync_resolution_with_fs(
 
   // 6. Set up `node_modules/.bin` entries for packages that need it.
   {
-    let bin_entries = bin_entries_to_setup.lock();
-    if !bin_entries.is_empty() && !bin_node_modules_dir_path.exists() {
-      fs::create_dir_all(&bin_node_modules_dir_path).with_context(|| {
-        format!("Creating '{}'", bin_node_modules_dir_path.display())
-      })?;
-    }
-    for (package, package_path) in &*bin_entries {
-      let package = snapshot.package_from_id(&package.id).unwrap();
-      if let Some(bin_entries) = &package.bin {
-        match bin_entries {
-          deno_npm::registry::NpmPackageVersionBinEntry::String(script) => {
-            // the default bin name doesn't include the organization
-            let name = package
-              .id
-              .nv
-              .name
-              .rsplit_once('/')
-              .map_or(package.id.nv.name.as_str(), |(_, name)| name);
-            bin_entries::set_up_bin_entry(
-              package,
-              name,
-              script,
-              package_path,
-              &bin_node_modules_dir_path,
-            )?;
-          }
-          deno_npm::registry::NpmPackageVersionBinEntry::Map(entries) => {
-            for (name, script) in entries {
-              bin_entries::set_up_bin_entry(
-                package,
-                name,
-                script,
-                package_path,
-                &bin_node_modules_dir_path,
-              )?;
-            }
-          }
-        }
-      }
-    }
+    let bin_entries = std::mem::take(&mut *bin_entries.lock());
+    bin_entries.finish(snapshot, &bin_node_modules_dir_path)?;
   }
 
   setup_cache.save();
diff --git a/cli/npm/managed/resolvers/local/bin_entries.rs b/cli/npm/managed/resolvers/local/bin_entries.rs
index 8e43cf98b..7890177ee 100644
--- a/cli/npm/managed/resolvers/local/bin_entries.rs
+++ b/cli/npm/managed/resolvers/local/bin_entries.rs
@@ -3,7 +3,193 @@
 use crate::npm::managed::NpmResolutionPackage;
 use deno_core::anyhow::Context;
 use deno_core::error::AnyError;
+use deno_npm::resolution::NpmResolutionSnapshot;
+use deno_npm::NpmPackageId;
+use std::collections::HashMap;
+use std::collections::HashSet;
+use std::collections::VecDeque;
 use std::path::Path;
+use std::path::PathBuf;
+
+#[derive(Default)]
+pub(super) struct BinEntries {
+  /// Packages that have colliding bin names
+  collisions: HashSet<NpmPackageId>,
+  seen_names: HashMap<String, NpmPackageId>,
+  /// The bin entries
+  entries: Vec<(NpmResolutionPackage, PathBuf)>,
+}
+
+/// Returns the name of the default binary for the given package.
+/// This is the package name without the organization (`@org/`), if any.
+fn default_bin_name(package: &NpmResolutionPackage) -> &str {
+  package
+    .id
+    .nv
+    .name
+    .rsplit_once('/')
+    .map_or(package.id.nv.name.as_str(), |(_, name)| name)
+}
+
+impl BinEntries {
+  pub(super) fn new() -> Self {
+    Self::default()
+  }
+
+  /// Add a new bin entry (package with a bin field)
+  pub(super) fn add(
+    &mut self,
+    package: NpmResolutionPackage,
+    package_path: PathBuf,
+  ) {
+    // check for a new collision, if we haven't already
+    // found one
+    match package.bin.as_ref().unwrap() {
+      deno_npm::registry::NpmPackageVersionBinEntry::String(_) => {
+        let bin_name = default_bin_name(&package);
+
+        if let Some(other) = self
+          .seen_names
+          .insert(bin_name.to_string(), package.id.clone())
+        {
+          self.collisions.insert(package.id.clone());
+          self.collisions.insert(other);
+        }
+      }
+      deno_npm::registry::NpmPackageVersionBinEntry::Map(entries) => {
+        for name in entries.keys() {
+          if let Some(other) =
+            self.seen_names.insert(name.to_string(), package.id.clone())
+          {
+            self.collisions.insert(package.id.clone());
+            self.collisions.insert(other);
+          }
+        }
+      }
+    }
+
+    self.entries.push((package, package_path));
+  }
+
+  /// Finish setting up the bin entries, writing the necessary files
+  /// to disk.
+  pub(super) fn finish(
+    mut self,
+    snapshot: &NpmResolutionSnapshot,
+    bin_node_modules_dir_path: &Path,
+  ) -> Result<(), AnyError> {
+    if !self.entries.is_empty() && !bin_node_modules_dir_path.exists() {
+      std::fs::create_dir_all(bin_node_modules_dir_path).with_context(
+        || format!("Creating '{}'", bin_node_modules_dir_path.display()),
+      )?;
+    }
+
+    if !self.collisions.is_empty() {
+      // walking the dependency tree to find out the depth of each package
+      // is sort of expensive, so we only do it if there's a collision
+      sort_by_depth(snapshot, &mut self.entries, &mut self.collisions);
+    }
+
+    let mut seen = HashSet::new();
+
+    for (package, package_path) in &self.entries {
+      if let Some(bin_entries) = &package.bin {
+        match bin_entries {
+          deno_npm::registry::NpmPackageVersionBinEntry::String(script) => {
+            let name = default_bin_name(package);
+            if !seen.insert(name) {
+              // we already set up a bin entry with this name
+              continue;
+            }
+            set_up_bin_entry(
+              package,
+              name,
+              script,
+              package_path,
+              bin_node_modules_dir_path,
+            )?;
+          }
+          deno_npm::registry::NpmPackageVersionBinEntry::Map(entries) => {
+            for (name, script) in entries {
+              if !seen.insert(name) {
+                // we already set up a bin entry with this name
+                continue;
+              }
+              set_up_bin_entry(
+                package,
+                name,
+                script,
+                package_path,
+                bin_node_modules_dir_path,
+              )?;
+            }
+          }
+        }
+      }
+    }
+
+    Ok(())
+  }
+}
+
+// walk the dependency tree to find out the depth of each package
+// that has a bin entry, then sort them by depth
+fn sort_by_depth(
+  snapshot: &NpmResolutionSnapshot,
+  bin_entries: &mut [(NpmResolutionPackage, PathBuf)],
+  collisions: &mut HashSet<NpmPackageId>,
+) {
+  enum Entry<'a> {
+    Pkg(&'a NpmPackageId),
+    IncreaseDepth,
+  }
+
+  let mut seen = HashSet::new();
+  let mut depths: HashMap<&NpmPackageId, u64> =
+    HashMap::with_capacity(collisions.len());
+
+  let mut queue = VecDeque::new();
+  queue.extend(snapshot.top_level_packages().map(Entry::Pkg));
+  seen.extend(snapshot.top_level_packages());
+  queue.push_back(Entry::IncreaseDepth);
+
+  let mut current_depth = 0u64;
+
+  while let Some(entry) = queue.pop_front() {
+    if collisions.is_empty() {
+      break;
+    }
+    let id = match entry {
+      Entry::Pkg(id) => id,
+      Entry::IncreaseDepth => {
+        current_depth += 1;
+        if queue.is_empty() {
+          break;
+        }
+        queue.push_back(Entry::IncreaseDepth);
+        continue;
+      }
+    };
+    if let Some(package) = snapshot.package_from_id(id) {
+      if collisions.remove(&package.id) {
+        depths.insert(&package.id, current_depth);
+      }
+      for dep in package.dependencies.values() {
+        if seen.insert(dep) {
+          queue.push_back(Entry::Pkg(dep));
+        }
+      }
+    }
+  }
+
+  bin_entries.sort_by(|(a, _), (b, _)| {
+    depths
+      .get(&a.id)
+      .unwrap_or(&u64::MAX)
+      .cmp(depths.get(&b.id).unwrap_or(&u64::MAX))
+      .then_with(|| a.id.nv.cmp(&b.id.nv).reverse())
+  });
+}
 
 pub(super) fn set_up_bin_entry(
   package: &NpmResolutionPackage,
@@ -64,29 +250,30 @@ fn symlink_bin_entry(
   package_path: &Path,
   bin_node_modules_dir_path: &Path,
 ) -> Result<(), AnyError> {
+  use std::io;
   use std::os::unix::fs::symlink;
   let link = bin_node_modules_dir_path.join(bin_name);
   let original = package_path.join(bin_script);
 
-  // Don't bother setting up another link if it already exists
-  if link.exists() {
-    let resolved = std::fs::read_link(&link).ok();
-    if let Some(resolved) = resolved {
-      if resolved != original {
+  use std::os::unix::fs::PermissionsExt;
+  let mut perms = match std::fs::metadata(&original) {
+    Ok(metadata) => metadata.permissions(),
+    Err(err) => {
+      if err.kind() == io::ErrorKind::NotFound {
         log::warn!(
-          "{} Trying to set up '{}' bin for \"{}\", but an entry pointing to \"{}\" already exists. Skipping...", 
-          deno_terminal::colors::yellow("Warning"), 
+          "{} Trying to set up '{}' bin for \"{}\", but the entry point \"{}\" doesn't exist.",
+          deno_terminal::colors::yellow("Warning"),
           bin_name,
-          resolved.display(),
+          package_path.display(),
           original.display()
         );
+        return Ok(());
       }
-      return Ok(());
+      return Err(err).with_context(|| {
+        format!("Can't set up '{}' bin at {}", bin_name, original.display())
+      });
     }
-  }
-
-  use std::os::unix::fs::PermissionsExt;
-  let mut perms = std::fs::metadata(&original).unwrap().permissions();
+  };
   if perms.mode() & 0o111 == 0 {
     // if the original file is not executable, make it executable
     perms.set_mode(perms.mode() | 0o111);
@@ -97,13 +284,31 @@ fn symlink_bin_entry(
   let original_relative =
     crate::util::path::relative_path(bin_node_modules_dir_path, &original)
       .unwrap_or(original);
-  symlink(&original_relative, &link).with_context(|| {
-    format!(
-      "Can't set up '{}' bin at {}",
-      bin_name,
-      original_relative.display()
-    )
-  })?;
+
+  if let Err(err) = symlink(&original_relative, &link) {
+    if err.kind() == io::ErrorKind::AlreadyExists {
+      let resolved = std::fs::read_link(&link).ok();
+      if let Some(resolved) = resolved {
+        if resolved != original_relative {
+          log::warn!(
+            "{} Trying to set up '{}' bin for \"{}\", but an entry pointing to \"{}\" already exists. Skipping...", 
+            deno_terminal::colors::yellow("Warning"), 
+            bin_name,
+            resolved.display(),
+            original_relative.display()
+          );
+        }
+        return Ok(());
+      }
+    }
+    return Err(err).with_context(|| {
+      format!(
+        "Can't set up '{}' bin at {}",
+        bin_name,
+        original_relative.display()
+      )
+    });
+  }
 
   Ok(())
 }
diff --git a/tests/registry/npm/@denotest/bin/0.7.0/cli-no-ext b/tests/registry/npm/@denotest/bin/0.7.0/cli-no-ext
new file mode 100644
index 000000000..1cad127ca
--- /dev/null
+++ b/tests/registry/npm/@denotest/bin/0.7.0/cli-no-ext
@@ -0,0 +1,3 @@
+#!/usr/bin/env -S node
+
+console.log("@denotest/bin 0.7.0");
diff --git a/tests/registry/npm/@denotest/bin/0.7.0/cli.mjs b/tests/registry/npm/@denotest/bin/0.7.0/cli.mjs
new file mode 100644
index 000000000..1cad127ca
--- /dev/null
+++ b/tests/registry/npm/@denotest/bin/0.7.0/cli.mjs
@@ -0,0 +1,3 @@
+#!/usr/bin/env -S node
+
+console.log("@denotest/bin 0.7.0");
diff --git a/tests/registry/npm/@denotest/bin/0.7.0/package.json b/tests/registry/npm/@denotest/bin/0.7.0/package.json
new file mode 100644
index 000000000..d66b6e34d
--- /dev/null
+++ b/tests/registry/npm/@denotest/bin/0.7.0/package.json
@@ -0,0 +1,8 @@
+{
+  "name": "@denotest/bin",
+  "version": "0.7.0",
+  "bin": {
+    "cli-esm": "./cli.mjs",
+    "cli-no-ext": "./cli-no-ext"
+  }
+}
diff --git a/tests/registry/npm/@denotest/transitive-bin/1.0.0/cli-cjs.js b/tests/registry/npm/@denotest/transitive-bin/1.0.0/cli-cjs.js
new file mode 100644
index 000000000..f517654b9
--- /dev/null
+++ b/tests/registry/npm/@denotest/transitive-bin/1.0.0/cli-cjs.js
@@ -0,0 +1 @@
+console.log("@denotest/transitive-bin 1.0.0");
diff --git a/tests/registry/npm/@denotest/transitive-bin/1.0.0/package.json b/tests/registry/npm/@denotest/transitive-bin/1.0.0/package.json
new file mode 100644
index 000000000..84d780516
--- /dev/null
+++ b/tests/registry/npm/@denotest/transitive-bin/1.0.0/package.json
@@ -0,0 +1,10 @@
+{
+  "name": "@denotest/transitive-bin",
+  "version": "1.0.0",
+  "dependencies": {
+    "@denotest/bin": "1.0.0"
+  },
+  "bin": {
+    "cli-cjs": "cli-cjs.js"
+  }
+}
\ No newline at end of file
diff --git a/tests/specs/npm/bin_entries_prefer_closer/__test__.jsonc b/tests/specs/npm/bin_entries_prefer_closer/__test__.jsonc
new file mode 100644
index 000000000..90d788518
--- /dev/null
+++ b/tests/specs/npm/bin_entries_prefer_closer/__test__.jsonc
@@ -0,0 +1,26 @@
+{
+  "envs": {
+    "DENO_FUTURE": "1"
+  },
+  "tempDir": true,
+  "steps": [
+    {
+      "args": "install",
+      "output": "install.out"
+    },
+    {
+      "args": "task run-esm",
+      "output": "Task run-esm cli-esm hello world\n@denotest/bin 0.7.0\n"
+    },
+    {
+      "args": "task run-cjs",
+      // @denotest/bin 0.7.0 doesn't have a cli-cjs, so it should use the one from @denotest/transitive-bin
+      // because it's closer than the one from @denotest/bin 1.0.0
+      "output": "Task run-cjs cli-cjs hello world\n@denotest/transitive-bin 1.0.0\n"
+    },
+    {
+      "args": "task run-no-ext",
+      "output": "Task run-no-ext cli-no-ext hello world\n@denotest/bin 0.7.0\n"
+    }
+  ]
+}
diff --git a/tests/specs/npm/bin_entries_prefer_closer/deno.json b/tests/specs/npm/bin_entries_prefer_closer/deno.json
new file mode 100644
index 000000000..176354f98
--- /dev/null
+++ b/tests/specs/npm/bin_entries_prefer_closer/deno.json
@@ -0,0 +1,3 @@
+{
+  "nodeModulesDir": true
+}
diff --git a/tests/specs/npm/bin_entries_prefer_closer/install.out b/tests/specs/npm/bin_entries_prefer_closer/install.out
new file mode 100644
index 000000000..25e06db99
--- /dev/null
+++ b/tests/specs/npm/bin_entries_prefer_closer/install.out
@@ -0,0 +1,11 @@
+⚠️ `deno install` behavior will change in Deno 2. To preserve the current behavior use the `-g` or `--global` flag.
+[UNORDERED_START]
+Download http://localhost:4260/@denotest/transitive-bin
+Download http://localhost:4260/@denotest/bin
+Download http://localhost:4260/@denotest/bin/1.0.0.tgz
+Download http://localhost:4260/@denotest/transitive-bin/1.0.0.tgz
+Download http://localhost:4260/@denotest/bin/0.7.0.tgz
+Initialize @denotest/transitive-bin@1.0.0
+Initialize @denotest/bin@1.0.0
+Initialize @denotest/bin@0.7.0
+[UNORDERED_END]
diff --git a/tests/specs/npm/bin_entries_prefer_closer/package.json b/tests/specs/npm/bin_entries_prefer_closer/package.json
new file mode 100644
index 000000000..af75632ce
--- /dev/null
+++ b/tests/specs/npm/bin_entries_prefer_closer/package.json
@@ -0,0 +1,14 @@
+{
+  "name": "bin_entries_prefer_closer",
+  "dependencies": {
+    "@denotest/bin": "0.7.0",
+    "@denotest/transitive-bin": "1.0.0"
+  },
+
+  "scripts": {
+    "run-esm": "cli-esm hello world",
+    "run-cjs": "cli-cjs hello world",
+    "run-no-ext": "cli-no-ext hello world",
+    "run-ts": "cli-ts"
+  }
+}