Repository: denoland/deno
Pull request: fix: make .setup-cache.bin in node_modules more reproducible

This PR will make vendored dependencies more deterministic. The `node_modules/.deno/.setup-cache.bin` is currently not deterministic because it consists of serialized `HashMap`s which have a random order of elements. By switching them out for `BTreeMap`s, which are sorted in memory, deno generates the same file every time.

According to the Rust documentation `BTreeMap` might provide slightly less performance than `HashMap`, but I wasn't able to reproduce lower performance in deno. I think even for large projects, our maps are way too small for this to have any performance impact.

related issue: #24479

<!--
Before submitting a PR, please read https://docs.deno.com/runtime/manual/references/contributing

1. Give the PR a descriptive title.
  Examples of good title:
    - fix(std/http): Fix race condition in server
    - docs(console): Update docstrings
    - feat(doc): Handle nested reexports

  Examples of bad title:
    - fix #7123
    - update docs
    - fix bugs

2. Ensure there is a related issue and it is referenced in the PR text.
3. Ensure there are tests that cover the changes.
4. Ensure `cargo test` passes.
5. Ensure `./tools/format.js` passes without changing files.
6. Ensure `./tools/lint.js` passes.
7. Open as a draft PR if your work is still in progress. The CI won't run
   all steps, but you can add '[ci]' to a commit message to force it to.
8. If you would like to run the benchmarks on the CI, add the 'ci-bench' label.
-->


Changed files:
filename: cli/npm/managed/resolvers/local.rs
patch: @@ -7,6 +7,7 @@ mod bin_entries;
 use std::borrow::Cow;
 use std::cell::RefCell;
 use std::cmp::Ordering;
+use std::collections::BTreeMap;
 use std::collections::HashMap;
 use std::collections::HashSet;
 use std::fs;
@@ -515,10 +516,13 @@ async fn sync_resolution_with_fs(
   Ok(())
 }
 
+// Uses BTreeMap to preserve the ordering of the elements in memory, to ensure
+// the file generated from this datastructure is deterministic.
+// See: https://github.com/denoland/deno/issues/24479
 /// Represents a dependency at `node_modules/.deno/<package_id>/`
 struct SetupCacheDep<'a> {
-  previous: Option<&'a HashMap<String, String>>,
-  current: &'a mut HashMap<String, String>,
+  previous: Option<&'a BTreeMap<String, String>>,
+  current: &'a mut BTreeMap<String, String>,
 }
 
 impl<'a> SetupCacheDep<'a> {
@@ -534,11 +538,14 @@ impl<'a> SetupCacheDep<'a> {
   }
 }
 
+// Uses BTreeMap to preserve the ordering of the elements in memory, to ensure
+// the file generated from this datastructure is deterministic.
+// See: https://github.com/denoland/deno/issues/24479
 #[derive(Debug, Default, Serialize, Deserialize, PartialEq, Eq)]
 struct SetupCacheData {
-  root_symlinks: HashMap<String, String>,
-  deno_symlinks: HashMap<String, String>,
-  dep_symlinks: HashMap<String, HashMap<String, String>>,
+  root_symlinks: BTreeMap<String, String>,
+  deno_symlinks: BTreeMap<String, String>,
+  dep_symlinks: BTreeMap<String, BTreeMap<String, String>>,
 }
 
 /// It is very slow to try to re-setup the symlinks each time, so this will