From bfc9e33a54985797968708176690a9ecfc207f83 Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Wed, 14 Dec 2022 00:57:24 +0100 Subject: 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. --- .../tools/refinery/store/map/AnyVersionedMap.java | 35 ++++++++++++ .../tools/refinery/store/map/ContentHashCode.java | 19 +++++++ .../refinery/store/map/internal/MapCursor.java | 5 +- .../store/map/internal/VersionedMapImpl.java | 12 ++++ .../map/tests/fuzz/ContentEqualsFuzzTest.java | 56 +++++++----------- .../store/map/tests/utils/MapTestEnvironment.java | 66 +++++++++++++++------- 6 files changed, 135 insertions(+), 58 deletions(-) create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/ContentHashCode.java (limited to 'subprojects') 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 + * hashCode 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 true if this object is the same as the obj 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 hashCode 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 hashCode 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. + *

+ * In the extreme case, {@link AnyVersionedMap#contentHashCode(ContentHashCode)} may return the same + * hashCode irrespectively of the actual contents of the {@link AnyVersionedMap}. + *

+ */ + 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 implements Cursor { // 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 implements Cursor { @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 implements VersionedMap { 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 chp = MapTestEnvironment.prepareHashProvider(evilHash); @@ -31,7 +30,9 @@ class ContentEqualsFuzzTest { iterativeRandomPutsAndCommitsThenCompare(scenario, chp, steps, maxKey, values, r, commitFrequency); } - private void iterativeRandomPutsAndCommitsThenCompare(String scenario, ContinousHashProvider chp, int steps, int maxKey, String[] values, Random r, int commitFrequency) { + private void iterativeRandomPutsAndCommitsThenCompare(String scenario, ContinousHashProvider chp, + int steps, int maxKey, String[] values, Random r, + int commitFrequency) { VersionedMapStore store1 = new VersionedMapStoreImpl(chp, values[0]); VersionedMap sut1 = store1.createMap(); @@ -67,58 +68,43 @@ class ContentEqualsFuzzTest { int index2 = 1; for (SimpleEntry 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) sut1).checkIntegrity(); - ((VersionedMapImpl) sut2).checkIntegrity(); - -// // Compare the two maps - // By size - assertEquals(sut1.getSize(), content.size()); - assertEquals(sut2.getSize(), content.size()); - - // By cursors - Cursor cursor1 = sut1.getAll(); - Cursor 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) sut1).checkIntegrity(); + ((VersionedMapImpl) 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 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 { } - public static void compareTwoMaps(String title, VersionedMapImpl map1, - VersionedMapImpl map2) { + public static void compareTwoMaps(String title, VersionedMap map1, + VersionedMap map2) { compareTwoMaps(title, map1, map2, null); } - public static void compareTwoMaps(String title, VersionedMapImpl map1, - VersionedMapImpl map2, List errors) { + + public static void compareTwoMaps(String title, VersionedMap map1, + VersionedMap map2, List errors) { + assertEqualsList(map1.getSize(), map2.getSize(), title + ": Sizes not equal", errors); + Cursor cursor1 = map1.getAll(); Cursor 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 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 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 sut; Map oracle = new HashMap(); @@ -99,10 +122,10 @@ public class MapTestEnvironment { } 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 { } } - public static void checkOrder(String scenario, VersionedMap versionedMap) { + public static void checkOrder(String scenario, VersionedMap versionedMap) { K previous = null; Cursor cursor = versionedMap.getAll(); - while(cursor.move()) { + while (cursor.move()) { System.out.println(cursor.getKey() + " " + ((VersionedMapImpl) versionedMap).getHashProvider().getHash(cursor.getKey(), 0)); - if(previous != null) { - int comparisonResult = ((VersionedMapImpl) versionedMap).getHashProvider().compare(previous, cursor.getKey()); - assertTrue(comparisonResult<0,scenario+" Cursor order is not incremental!"); + if (previous != null) { + int comparisonResult = ((VersionedMapImpl) versionedMap).getHashProvider().compare(previous, + cursor.getKey()); + assertTrue(comparisonResult < 0, scenario + " Cursor order is not incremental!"); } previous = cursor.getKey(); } -- cgit v1.2.3-70-g09d2