js maps: add more tests and fix stuff

3 files changed, 103 insertions, 37 deletions

diff --git a/src/gleam_stdlib.mjs b/src/gleam_stdlib.mjs
index 62e1ad6..81304fe 100644
--- a/src/gleam_stdlib.mjs
+++ b/src/gleam_stdlib.mjs
@@ -244,7 +244,7 @@ export function trim_right(string) {
 }
 
 export function bit_string_from_string(string) {
-  return new toBitString([stringBits(string)]);
+  return toBitString([stringBits(string)]);
 }
 
 export function bit_string_concat(bit_strings) {
diff --git a/src/persistent-hash-map.mjs b/src/persistent-hash-map.mjs
index f2b7e81..dc3db31 100644
--- a/src/persistent-hash-map.mjs
+++ b/src/persistent-hash-map.mjs
@@ -1,7 +1,7 @@
 import { isEqual } from "./gleam.mjs";
 
 const referenceMap = new WeakMap();
-let referenceUID = 1;
+let referenceUID = 0;
 
 /** hash the object by reference using a weak map and incrementing uid */
 function hashByReference(o) {
@@ -11,22 +11,15 @@ function hashByReference(o) {
   }
   const hash = referenceUID++;
   if (referenceUID === 0x7fffffff) {
-    referenceUID = 1;
+    referenceUID = 0;
   }
   referenceMap.set(o, hash);
   return hash;
 }
-/** taken from immutable.js */
+/** merge two hashes in an order sensitive way */
 function hashMerge(a, b) {
   return (a ^ (b + 0x9e3779b9 + (a << 6) + (a >> 2))) | 0;
 }
-/** scrambles an integer to make it more randomly distributed */
-function hashInteger(i) {
-  i = Math.imul(0x45d9f3b, (i >>> 16) ^ i);
-  i = Math.imul(0x45d9f3b, (i >>> 16) ^ i);
-  i = (i >>> 16) ^ i;
-  return i;
-}
 /** standard string hash popularised by java */
 function hashString(s) {
   let hash = 0;
@@ -55,7 +48,9 @@ function hashObject(o) {
     return hashNumber(o.getTime());
   }
   let h = 0;
-  if (o instanceof ArrayBuffer) o = new Uint8Array(o);
+  if (o instanceof ArrayBuffer) {
+    o = new Uint8Array(o);
+  }
   if (Array.isArray(o) || o instanceof Uint8Array) {
     for (let i = 0; i < o.length; i++) {
       h = (Math.imul(31, h) + getHash(o[i])) | 0;
@@ -73,7 +68,7 @@ function hashObject(o) {
     for (let i = 0; i < keys.length; i++) {
       const k = keys[i];
       const v = o[k];
-      h = (h + hashMerge(getHash(v), hashInteger(hashString(k)))) | 0;
+      h = (h + hashMerge(getHash(v), hashString(k))) | 0;
     }
   }
   return h;
@@ -86,17 +81,17 @@ export function getHash(u) {
   if (u === false) return 0x42108420;
   switch (typeof u) {
     case "number":
-      return hashInteger(hashNumber(u));
+      return hashNumber(u);
     case "string":
-      return hashInteger(hashString(u));
+      return hashString(u);
     case "bigint":
-      return hashInteger(hashNumber(u));
+      return hashNumber(u);
     case "object":
-      return hashInteger(hashObject(u));
+      return hashObject(u);
     case "symbol":
-      return hashInteger(hashByReference(u));
+      return hashByReference(u);
     case "function":
-      return hashInteger(hashByReference(u));
+      return hashByReference(u);
   }
 }
 const SHIFT = 5; // number of bits you need to shift by to get the next bucket
@@ -396,7 +391,7 @@ function find(root, shift, hash, key) {
     case INDEX_NODE:
       return findIndex(root, shift, hash, key);
     case COLLISION_NODE:
-      return findCollision(root, shift, hash, key);
+      return findCollision(root, key);
   }
 }
 function findArray(root, shift, hash, key) {
@@ -422,7 +417,7 @@ function findIndex(root, shift, hash, key) {
   }
   return undefined;
 }
-function findCollision(root, _shift, _hash, key) {
+function findCollision(root, key) {
   const idx = collisionIndexOf(root, key);
   if (idx < 0) {
     return undefined;
@@ -440,7 +435,7 @@ function without(root, shift, hash, key) {
     case INDEX_NODE:
       return withoutIndex(root, shift, hash, key);
     case COLLISION_NODE:
-      return withoutCollision(root, shift, hash, key);
+      return withoutCollision(root, key);
   }
 }
 function withoutArray(root, shift, hash, key) {
@@ -545,10 +540,10 @@ function withoutIndex(root, shift, hash, key) {
   }
   return root;
 }
-function withoutCollision(root, _shift, _hash, key) {
+function withoutCollision(root, key) {
   const idx = collisionIndexOf(root, key);
   // if the key not found, no changes
-  if (idx === -1) {
+  if (idx < 0) {
     return root;
   }
   // otherwise the entry was found, remove it
@@ -583,22 +578,21 @@ function forEach(root, fn) {
 }
 /** Extra wrapper to keep track of map size */
 export class PMap {
-  static NOT_FOUND = Symbol();
   constructor(root, size) {
     this.root = root;
     this.size = size;
   }
   hashCode() {
     let h = 0;
-    forEach(this, (v, k) => {
+    forEach(this.root, (v, k) => {
       h = (h + hashMerge(getHash(v), getHash(k))) | 0;
     });
     return h;
   }
   equals(o) {
     let equal = true;
-    forEach(this, (v, k) => {
-      equal = equal && isEqual(v, getWithDefault(o, k, PMap.NOT_FOUND));
+    forEach(this.root, (v, k) => {
+      equal = equal && isEqual(getWithDefault(o, k, !v), v);
     });
     return equal;
   }
@@ -606,12 +600,6 @@ export class PMap {
 export function create() {
   return new PMap(undefined, 0);
 }
-export function get(map, key) {
-  if (map.root === undefined) {
-    return undefined;
-  }
-  return find(map.root, 0, getHash(key), key)?.v;
-}
 export function getWithDefault(map, key, notFound) {
   if (map.root === undefined) {
     return notFound;
@@ -658,6 +646,4 @@ export function entries(map) {
   forEach(map.root, (v, k) => result.push([k, v]));
   return result;
 }
-export function __include_me() {
-  // blank
-}
+export function __include_me() {}
diff --git a/test/gleam/map_test.gleam b/test/gleam/map_test.gleam
index 34f3ee6..cd669f9 100644
--- a/test/gleam/map_test.gleam
+++ b/test/gleam/map_test.gleam
@@ -204,3 +204,83 @@ pub fn fold_test() {
   |> map.fold(0, add)
   |> should.equal(0)
 }
+
+fn range(start, end, a) {
+  case end - start {
+    n if n < 1 -> a
+    _ -> range(start, end - 1, [end - 1, ..a])
+  }
+}
+
+fn list_to_map(list) {
+  list
+  |> list.map(fn(n) { #(n, n) })
+  |> map.from_list
+}
+
+fn grow_and_shrink_map(initial_size, final_size) {
+  range(0, initial_size, [])
+  |> list_to_map
+  |> list.fold(
+    range(final_size, initial_size, []),
+    _,
+    fn(map, item) { map.delete(map, item) },
+  )
+}
+
+// maps should be equal even if the insert/removal order was different
+pub fn insert_order_equality_test() {
+  grow_and_shrink_map(8, 2)
+  |> should.equal(grow_and_shrink_map(4, 2))
+  grow_and_shrink_map(17, 10)
+  |> should.equal(grow_and_shrink_map(12, 10))
+  grow_and_shrink_map(2000, 1000)
+  |> should.equal(grow_and_shrink_map(1000, 1000))
+}
+
+// ensure operations on a map don't mutate it
+pub fn persistence_test() {
+  let a = list_to_map([0])
+  map.insert(a, 0, 5)
+  map.insert(a, 1, 6)
+  map.delete(a, 0)
+  map.get(a, 0)
+  |> should.equal(Ok(0))
+}
+
+// using maps as keys should work (tests hash function)
+pub fn map_as_key_test() {
+  let l = range(0, 1000, [])
+  let a = list_to_map(l)
+  let a2 = list_to_map(list.reverse(l))
+  let a3 = grow_and_shrink_map(2000, 1000)
+  let b = grow_and_shrink_map(60, 50)
+  let c = grow_and_shrink_map(50, 20)
+  let d = grow_and_shrink_map(2, 2)
+
+  let map1 =
+    map.new()
+    |> map.insert(a, "a")
+    |> map.insert(b, "b")
+    |> map.insert(c, "c")
+    |> map.insert(d, "d")
+
+  map.get(map1, a)
+  |> should.equal(Ok("a"))
+  map.get(map1, a2)
+  |> should.equal(Ok("a"))
+  map.get(map1, a3)
+  |> should.equal(Ok("a"))
+  map.get(map1, b)
+  |> should.equal(Ok("b"))
+  map.get(map1, c)
+  |> should.equal(Ok("c"))
+  map.get(map1, d)
+  |> should.equal(Ok("d"))
+  map.insert(map1, a2, "a2")
+  |> map.get(a)
+  |> should.equal(Ok("a2"))
+  map.insert(map1, a3, "a3")
+  |> map.get(a)
+  |> should.equal(Ok("a3"))
+}