refactor(store): compare VersionedMap instances

The Java hashCode and equals API is inappropriate here, because an
AnyVersionedMap is mutable. Added new methods to hash and compare
AnyVersionedMap instances by their contents and marked the built-in Java
methods as deprecated.

6 files changed, 135 insertions, 58 deletions

diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java b/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java
index b94b9f38..f82a8bb1 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java
@@ -2,4 +2,39 @@ package tools.refinery.store.map;
 
 public sealed interface AnyVersionedMap extends Versioned permits VersionedMap {
         long getSize();
+
+        int contentHashCode(ContentHashCode mode);
+
+        boolean contentEquals(AnyVersionedMap other);
+
+        /**
+         * Returns a hash code value for the object.
+         *
+         * @return A hash code value for this object.
+         * @deprecated {@link AnyVersionedMap} instances are mutable, and it is inappropriate to use them as keys in
+         * hash-based collections. Use {@link AnyVersionedMap#contentHashCode(ContentHashCode)} to compute a
+         * <code>hashCode</code> for a {@link AnyVersionedMap} instance according to its contents.
+         */
+        @Override
+        // This method is mark as @Deprecated to prevent inappropriate use of built-in Java API.
+        // Therefore, we don't follow normal procedures for removing deprecated code.
+        @SuppressWarnings("squid:S1133")
+        @Deprecated(since = "0.0.0")
+        int hashCode();
+
+        /**
+         * Compares two objects by reference.
+         *
+         * @param obj The reference object with which to compare.
+         * @return <code>true</code> if this object is the same as the <code>obj</code> argument.
+         * @deprecated {@link AnyVersionedMap} instances are mutable, and it is inappropriate to use them as keys in
+         * hash-based collections. Use {@link AnyVersionedMap#contentEquals(AnyVersionedMap)} to compare two
+         * {@link AnyVersionedMap} instances by their contents.
+         */
+        @Override
+        // This method is mark as @Deprecated to prevent inappropriate use of built-in Java API.
+        // Therefore, we don't follow normal procedures for removing deprecated code.
+        @SuppressWarnings("squid:S1133")
+        @Deprecated(since = "0.0.0")
+        boolean equals(Object obj);
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/ContentHashCode.java b/subprojects/store/src/main/java/tools/refinery/store/map/ContentHashCode.java
new file mode 100644
index 00000000..8deeab23
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/ContentHashCode.java
@@ -0,0 +1,19 @@
+package tools.refinery.store.map;
+
+public enum ContentHashCode {
+        /**
+         * Calculate the <code>hashCode</code> of the contents of this {@link AnyVersionedMap} to reduce hash collisions as
+         * much as possible, even iterating over the full contents in necessary.
+         */
+        PRECISE_SLOW,
+
+        /**
+         * Compute an approximate <code>hashCode</code> of the contents of this {@link AnyVersionedMap} that may have a
+         * large number of hash collisions, but can be calculated without iterating over the full contents.
+         * <p>
+         *     In the extreme case, {@link AnyVersionedMap#contentHashCode(ContentHashCode)} may return the same
+         *     <code>hashCode</code> irrespectively of the actual contents of the {@link AnyVersionedMap}.
+         * </p>
+         */
+        APPROXIMATE_FAST
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java
index 1698830f..91a71e3d 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java
@@ -1,6 +1,7 @@
 package tools.refinery.store.map.internal;
 
 import tools.refinery.store.map.AnyVersionedMap;
+import tools.refinery.store.map.ContentHashCode;
 import tools.refinery.store.map.Cursor;
 import tools.refinery.store.map.VersionedMap;
 
@@ -45,7 +46,7 @@ public class MapCursor<K, V> implements Cursor<K, V> {
 
                 // Initializing state
                 this.map = map;
-                this.creationHash = map.hashCode();
+                this.creationHash = map.contentHashCode(ContentHashCode.APPROXIMATE_FAST);
         }
 
         public K getKey() {
@@ -87,7 +88,7 @@ public class MapCursor<K, V> implements Cursor<K, V> {
 
         @Override
         public boolean isDirty() {
-                return this.map.hashCode() != this.creationHash;
+                return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash;
         }
 
         @Override
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
index 866e7b33..301bcb95 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
@@ -5,6 +5,7 @@ import tools.refinery.store.map.*;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Objects;
 
 /**
  * Not threadSafe in itself
@@ -145,4 +146,15 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
                         this.root.checkIntegrity(hashProvider, defaultValue, 0);
                 }
         }
+
+        @Override
+        public int contentHashCode(ContentHashCode mode) {
+                // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode.
+                return Objects.hashCode(root);
+        }
+
+        @Override
+        public boolean contentEquals(AnyVersionedMap other) {
+                return other instanceof VersionedMapImpl<?, ?> otherImpl && Objects.equals(root, otherImpl.root);
+        }
 }
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java
index d7f77d1a..93ecfec3 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java
@@ -17,12 +17,11 @@ import java.util.List;
 import java.util.Random;
 import java.util.stream.Stream;
 
-import static org.junit.jupiter.api.Assertions.assertEquals;
-import static org.junit.jupiter.api.Assertions.fail;
+import static org.junit.jupiter.api.Assertions.*;
 
 class ContentEqualsFuzzTest {
         private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
-                        boolean evilHash) {
+                                                         boolean evilHash) {
                 String[] values = MapTestEnvironment.prepareValues(maxValue);
                 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
 
@@ -31,7 +30,9 @@ class ContentEqualsFuzzTest {
                 iterativeRandomPutsAndCommitsThenCompare(scenario, chp, steps, maxKey, values, r, commitFrequency);
         }
 
-        private void iterativeRandomPutsAndCommitsThenCompare(String scenario, ContinousHashProvider<Integer> chp, int steps, int maxKey, String[] values, Random r, int commitFrequency) {
+        private void iterativeRandomPutsAndCommitsThenCompare(String scenario, ContinousHashProvider<Integer> chp,
+                                                                                                                  int steps, int maxKey, String[] values, Random r,
+                                                                                                                  int commitFrequency) {
                 VersionedMapStore<Integer, String> store1 = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
                 VersionedMap<Integer, String> sut1 = store1.createMap();
 
@@ -67,58 +68,43 @@ class ContentEqualsFuzzTest {
                 int index2 = 1;
                 for (SimpleEntry<Integer, String> entry : content) {
                         sut2.put(entry.getKey(), entry.getValue());
-                        if(index2++%commitFrequency == 0)
+                        if (index2++ % commitFrequency == 0)
                                 sut2.commit();
                 }
 
                 // Check the integrity of the maps
-                ((VersionedMapImpl<Integer,String>) sut1).checkIntegrity();
-                ((VersionedMapImpl<Integer,String>) sut2).checkIntegrity();
-
-//              // Compare the two maps
-                // By size
-                assertEquals(sut1.getSize(), content.size());
-                assertEquals(sut2.getSize(), content.size());
-
-                // By cursors
-                Cursor<Integer, String> cursor1 = sut1.getAll();
-                Cursor<Integer, String> cursor2 = sut2.getAll();
-                int index3 = 1;
-                boolean canMove = true;
-                do{
-                        boolean canMove1 = cursor1.move();
-                        boolean canMove2 = cursor2.move();
-                        assertEquals(canMove1, canMove2, scenario + ":" + index3 +" Cursors stopped at different times!");
-                        assertEquals(cursor1.getKey(), cursor2.getKey(), scenario + ":" + index3 +" Cursors have different keys!");
-                        assertEquals(cursor1.getValue(), cursor2.getValue(), scenario + ":" + index3 +" Cursors have different values!");
-
-                        canMove = canMove1;
-                        MapTestEnvironment.printStatus(scenario, index3++, content.size(), "Compare");
-                } while (canMove);
+                ((VersionedMapImpl<Integer, String>) sut1).checkIntegrity();
+                ((VersionedMapImpl<Integer, String>) sut2).checkIntegrity();
+
+                // Compare the two maps
+                MapTestEnvironment.compareTwoMaps(scenario, sut1, sut2);
         }
 
-        @ParameterizedTest(name = "Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        @ParameterizedTest(name = "Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} " +
+                        "evil-hash={6}")
         @MethodSource
         @Timeout(value = 10)
         @Tag("fuzz")
         void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
+                                                          boolean evilHash) {
                 runFuzzTest("CompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
                                 commitFrequency, evilHash);
         }
 
         static Stream<Arguments> parametrizedFastFuzz() {
-                return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
-                                new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
-                                new Object[] { false, true });
+                return FuzzTestUtils.permutationWithSize(new Object[]{FuzzTestUtils.FAST_STEP_COUNT}, new Object[]{3, 32,
+                                                32 * 32},
+                                new Object[]{2, 3}, new Object[]{1, 10, 100}, new Object[]{1, 2, 3},
+                                new Object[]{false, true});
         }
 
-        @ParameterizedTest(name = "Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
+        @ParameterizedTest(name = "Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} " +
+                        "evil-hash={6}")
         @MethodSource
         @Tag("fuzz")
         @Tag("slow")
         void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
-                        boolean evilHash) {
+                                                          boolean evilHash) {
                 runFuzzTest("CompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
                                 commitFrequency, evilHash);
         }
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java
index b73f8b32..2d03ebaf 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java
@@ -1,8 +1,6 @@
 package tools.refinery.store.map.tests.utils;
 
-import tools.refinery.store.map.ContinousHashProvider;
-import tools.refinery.store.map.Cursor;
-import tools.refinery.store.map.VersionedMap;
+import tools.refinery.store.map.*;
 import tools.refinery.store.map.internal.VersionedMapImpl;
 
 import java.util.*;
@@ -50,40 +48,65 @@ public class MapTestEnvironment<K, V> {
 
         }
 
-        public static <K, V> void compareTwoMaps(String title, VersionedMapImpl<K, V> map1,
-                        VersionedMapImpl<K, V> map2) {
+        public static <K, V> void compareTwoMaps(String title, VersionedMap<K, V> map1,
+                                                                                         VersionedMap<K, V> map2) {
                 compareTwoMaps(title, map1, map2, null);
         }
-        public static <K, V> void compareTwoMaps(String title, VersionedMapImpl<K, V> map1,
-                        VersionedMapImpl<K, V> map2, List<Throwable> errors) {
+
+        public static <K, V> void compareTwoMaps(String title, VersionedMap<K, V> map1,
+                                                                                         VersionedMap<K, V> map2, List<Throwable> errors) {
+                assertEqualsList(map1.getSize(), map2.getSize(), title + ": Sizes not equal", errors);
+
                 Cursor<K, V> cursor1 = map1.getAll();
                 Cursor<K, V> cursor2 = map2.getAll();
                 while (!cursor1.isTerminated()) {
                         if (cursor2.isTerminated()) {
                                 fail("cursor 2 terminated before cursor1");
                         }
-                        assertEqualsList(cursor1.getKey(), cursor2.getKey(),"Keys not equal", errors);
-                        assertEqualsList(cursor2.getValue(), cursor2.getValue(), "Values not equal", errors);
+                        assertEqualsList(cursor1.getKey(), cursor2.getKey(), title + ": Keys not equal", errors);
+                        assertEqualsList(cursor2.getValue(), cursor2.getValue(), title + ": Values not equal", errors);
                         cursor1.move();
                         cursor2.move();
                 }
-                if (!cursor2.isTerminated())
+                if (!cursor2.isTerminated()) {
                         fail("cursor 1 terminated before cursor 2");
+                }
+
+                for (var mode : ContentHashCode.values()) {
+                        assertEqualsList(map1.contentHashCode(mode), map2.contentHashCode(mode),
+                                        title + ": " + mode + " hashCode check", errors);
+                }
+                assertContentEqualsList(map1, map2, title + ": map1.contentEquals(map2)", errors);
+                assertContentEqualsList(map2, map1, title + ": map2.contentEquals(map1)", errors);
         }
 
         private static void assertEqualsList(Object o1, Object o2, String message, List<Throwable> errors) {
-                if(errors == null) {
+                if (errors == null) {
                         assertEquals(o1, o2, message);
                 } else {
-                        if(o1 != null) {
-                                if(!(o1.equals(o2))) {
-                                        AssertionError error = new AssertionError((message != null ? message+" " : "") + "expected: " + o1 + " but was : " + o2);
+                        if (o1 != null) {
+                                if (!(o1.equals(o2))) {
+                                        AssertionError error =
+                                                        new AssertionError((message != null ? message + " " : "") + "expected: " + o1 + " but was " +
+                                                                        ": " + o2);
                                         errors.add(error);
                                 }
                         }
                 }
         }
 
+        private static void assertContentEqualsList(AnyVersionedMap o1, AnyVersionedMap o2, String message,
+                                                                                                List<Throwable> errors) {
+                boolean result = o1.contentEquals(o2);
+                if (errors == null) {
+                        assertTrue(result, message);
+                } else if (!result) {
+                        AssertionError error =
+                                        new AssertionError((message != null ? message + " " : "") + "expected: true but was: false");
+                        errors.add(error);
+                }
+        }
+
         public VersionedMapImpl<K, V> sut;
         Map<K, V> oracle = new HashMap<K, V>();
 
@@ -99,10 +122,10 @@ public class MapTestEnvironment<K, V> {
                 } else {
                         oldOracleValue = oracle.remove(key);
                 }
-                if(oldSutValue == sut.getDefaultValue() && oldOracleValue != null) {
+                if (oldSutValue == sut.getDefaultValue() && oldOracleValue != null) {
                         fail("After put, SUT old nodeId was default, but oracle old value was " + oldOracleValue);
                 }
-                if(oldSutValue != sut.getDefaultValue()) {
+                if (oldSutValue != sut.getDefaultValue()) {
                         assertEquals(oldOracleValue, oldSutValue);
                 }
         }
@@ -158,14 +181,15 @@ public class MapTestEnvironment<K, V> {
                 }
         }
 
-        public static <K,V> void checkOrder(String scenario, VersionedMap<K,V> versionedMap) {
+        public static <K, V> void checkOrder(String scenario, VersionedMap<K, V> versionedMap) {
                 K previous = null;
                 Cursor<K, V> cursor = versionedMap.getAll();
-                while(cursor.move()) {
+                while (cursor.move()) {
                         System.out.println(cursor.getKey() + " " + ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().getHash(cursor.getKey(), 0));
-                        if(previous != null) {
-                                int comparisonResult = ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().compare(previous, cursor.getKey());
-                                assertTrue(comparisonResult<0,scenario+" Cursor order is not incremental!");
+                        if (previous != null) {
+                                int comparisonResult = ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().compare(previous,
+                                                cursor.getKey());
+                                assertTrue(comparisonResult < 0, scenario + " Cursor order is not incremental!");
                         }
                         previous = cursor.getKey();
                 }