From 89e142514ae45d793c7dbe38f728b33451261338 Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Tue, 18 Jul 2023 15:38:59 +0200 Subject: Fixing long-standing bug with state based diff cursor. By implementing an InOrderMapCursor cursor, and a MapDiffCursor that synchronize two cursors. --- .../store/map/tests/InOrderCursorTest.java | 49 ++++++++ .../store/map/tests/fuzz/DiffCursorFuzzTest.java | 128 ++++++++++++--------- .../map/tests/fuzz/utils/FuzzTestCollections.java | 12 +- .../store/map/tests/utils/MapTestEnvironment.java | 10 +- 4 files changed, 136 insertions(+), 63 deletions(-) create mode 100644 subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java (limited to 'subprojects/store/src/test') diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java new file mode 100644 index 00000000..05cf5a74 --- /dev/null +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java @@ -0,0 +1,49 @@ +package tools.refinery.store.map.tests; + +import org.junit.jupiter.api.Test; +import tools.refinery.store.map.VersionedMapStoreBuilder; +import tools.refinery.store.map.internal.InOrderMapCursor; +import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.tests.utils.MapTestEnvironment; + +import static org.junit.jupiter.api.Assertions.*; + +class InOrderCursorTest { + @Test + void testCursor() { + var store = VersionedMapStoreBuilder.builder() + .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) + .setStateBasedImmutableWhenCommitting(true) + .setHashProvider(MapTestEnvironment.prepareHashProvider(false)) + .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE) + .setDefaultValue("x") + .buildOne(); + + VersionedMapImpl map = (VersionedMapImpl) store.createMap(); + checkMove(map,0); + + map.put(1,"A"); + map.commit(); + checkMove(map,1); + + + map.put(2,"B"); + map.commit(); + checkMove(map,2); + + map.put(3,"C"); + map.commit(); + checkMove(map,3); + + } + + private void checkMove(VersionedMapImpl map, int num) { + InOrderMapCursor cursor = new InOrderMapCursor<>(map); + for(int i=0; i builder) { + private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault, + int commitFrequency, boolean commitBeforeDiffCursor, + VersionedMapStoreBuilder builder) { String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); VersionedMapStore store = builder.setDefaultValue(values[0]).buildOne(); - iterativeRandomPutsAndCommitsThenDiffCursor(scenario, store, steps, maxKey, values, seed, commitFrequency); + iterativeRandomPutsAndCommitsThenDiffCursor(scenario, store, steps, maxKey, values, seed, commitFrequency, + commitBeforeDiffCursor); } private void iterativeRandomPutsAndCommitsThenDiffCursor(String scenario, VersionedMapStore store, - int steps, int maxKey, String[] values, int seed, int commitFrequency) { - // 1. build a map with versions - Random r = new Random(seed); - VersionedMap versioned = store.createMap(); + int steps, int maxKey, String[] values, int seed, + int commitFrequency, boolean commitBeforeDiffCursor) { + int largestCommit = -1; - for (int i = 0; i < steps; i++) { - int index = i + 1; - int nextKey = r.nextInt(maxKey); - String nextValue = values[r.nextInt(values.length)]; - try { - versioned.put(nextKey, nextValue); - } catch (Exception exception) { - exception.printStackTrace(); - fail(scenario + ":" + index + ": exception happened: " + exception); - } - if (index % commitFrequency == 0) { - long version = versioned.commit(); - largestCommit = (int) version; - } - if (index % 10000 == 0) - System.out.println(scenario + ":" + index + "/" + steps + " building finished"); - } - // 2. create a non-versioned map, - VersionedMap moving = store.createMap(); - Random r2 = new Random(seed + 1); - - final int diffTravelFrequency = commitFrequency * 2; - for (int i = 0; i < steps; i++) { - int index = i + 1; - if (index % diffTravelFrequency == 0) { - // diff-travel - long travelToVersion = r2.nextInt(largestCommit + 1); - DiffCursor diffCursor = moving.getDiffCursor(travelToVersion); - moving.putAll(diffCursor); - - } else { - // random puts - int nextKey = r2.nextInt(maxKey); - String nextValue = values[r2.nextInt(values.length)]; + { + // 1. build a map with versions + Random r = new Random(seed); + VersionedMap versioned = store.createMap(); + for (int i = 0; i < steps; i++) { + int index = i + 1; + int nextKey = r.nextInt(maxKey); + String nextValue = values[r.nextInt(values.length)]; try { - moving.put(nextKey, nextValue); + versioned.put(nextKey, nextValue); } catch (Exception exception) { exception.printStackTrace(); fail(scenario + ":" + index + ": exception happened: " + exception); } if (index % commitFrequency == 0) { - versioned.commit(); + long version = versioned.commit(); + largestCommit = (int) version; } if (index % 10000 == 0) System.out.println(scenario + ":" + index + "/" + steps + " building finished"); } } + { + // 2. create a non-versioned map, + VersionedMap moving = store.createMap(); + Random r2 = new Random(seed + 1); + + final int diffTravelFrequency = commitFrequency * 2; + for (int i = 0; i < steps; i++) { + int index = i + 1; + if (index % diffTravelFrequency == 0) { + // diff-travel + long travelToVersion = r2.nextInt(largestCommit + 1); + + VersionedMap oracle = store.createMap(travelToVersion); + + if(commitBeforeDiffCursor) { + moving.commit(); + } + DiffCursor diffCursor = moving.getDiffCursor(travelToVersion); + moving.putAll(diffCursor); + moving.commit(); + + MapTestEnvironment.compareTwoMaps(scenario + ":c" + index, oracle, moving); + + moving.restore(travelToVersion); + + } else { + // random puts + int nextKey = r2.nextInt(maxKey); + String nextValue = values[r2.nextInt(values.length)]; + try { + moving.put(nextKey, nextValue); + } catch (Exception exception) { + exception.printStackTrace(); + fail(scenario + ":" + index + ": exception happened: " + exception); + } + if (index % 10000 == 0) + System.out.println(scenario + ":" + index + "/" + steps + " building finished"); + } + } + } } public static final String title = "DiffCursor {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} " + - "commit frequency={5} seed={6} config={7}"; + "commit frequency={5} seed={6} commit before diff={7} config={8}"; @ParameterizedTest(name = title) @MethodSource @Timeout(value = 10) @Tag("fuzz") - void parametrizedFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, - int seed, VersionedMapStoreBuilder builder) { - runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, - noKeys, noValues, nullDefault, commitFrequency, builder); + void parametrizedFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, + int commitFrequency, int seed, boolean commitBeforeDiffCursor, + VersionedMapStoreBuilder builder) { + runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, + noKeys, noValues, nullDefault, commitFrequency, commitBeforeDiffCursor, builder); } static Stream parametrizedFuzz() { - return FuzzTestUtils.permutationWithSize(new Object[]{100}, keyCounts, valueCounts, nullDefaultOptions, - commitFrequencyOptions, randomSeedOptions, storeConfigs); + return FuzzTestUtils.permutationWithSize(new Object[]{500}, keyCounts, valueCounts, nullDefaultOptions, + commitFrequencyOptions, randomSeedOptions, new Object[]{false,true}, storeConfigs); } @ParameterizedTest(name = title) @@ -104,9 +124,9 @@ class DiffCursorFuzzTest { @Tag("fuzz") @Tag("slow") void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, - int seed, VersionedMapStoreBuilder builder) { - runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, - nullDefault, commitFrequency, builder); + int seed, boolean commitBeforeDiffCursor, VersionedMapStoreBuilder builder) { + runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, + nullDefault, commitFrequency, commitBeforeDiffCursor, builder); } static Stream parametrizedSlowFuzz() { diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java index fb6b28d8..b344d9b9 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java @@ -5,23 +5,25 @@ import tools.refinery.store.map.tests.utils.MapTestEnvironment; public final class FuzzTestCollections { public static final Object[] stepCounts = {FuzzTestUtils.FAST_STEP_COUNT}; - public static final Object[] keyCounts = {1, 32, 32 * 32}; + public static final Object[] keyCounts = {1 , 32, 32 * 32}; public static final Object[] valueCounts = {2, 3}; public static final Object[] nullDefaultOptions = {false, true}; - public static final Object[] commitFrequencyOptions = {10, 10, 100}; - public static final Object[] randomSeedOptions = {1/*, 2, 3*/}; + public static final Object[] commitFrequencyOptions = {1, 10, 100}; + public static final Object[] randomSeedOptions = {1}; public static final Object[] storeConfigs = { // State based VersionedMapStoreBuilder.builder() .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) .setStateBasedImmutableWhenCommitting(true) .setHashProvider(MapTestEnvironment.prepareHashProvider(false)) - .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE), + .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy + .SHARED_NODE_CACHE), VersionedMapStoreBuilder.builder() .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) .setStateBasedImmutableWhenCommitting(true) .setHashProvider(MapTestEnvironment.prepareHashProvider(true)) - .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE), + .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy + .SHARED_NODE_CACHE), VersionedMapStoreBuilder.builder() .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) .setStateBasedImmutableWhenCommitting(false) 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 69ae811e..0e695aaa 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 @@ -57,13 +57,15 @@ public class MapTestEnvironment { VersionedMap map2, List errors) { map1.checkIntegrity(); map2.checkIntegrity(); + + assertContentEqualsList(map1, map2, title + ": map1.contentEquals(map2)", errors); + assertContentEqualsList(map2, map1, title + ": map2.contentEquals(map1)", errors); assertEqualsList(map1.getSize(), map2.getSize(), title + ": Sizes not equal", errors); + 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) { @@ -177,7 +179,8 @@ public class MapTestEnvironment { K previous = null; Cursor cursor = versionedMap.getAll(); while (cursor.move()) { - System.out.println(cursor.getKey() + " " + ((VersionedMapImpl) versionedMap).getHashProvider().getHash(cursor.getKey(), 0)); + //System.out.println(cursor.getKey() + " " + ((VersionedMapImpl) versionedMap).getHashProvider() + // .getHash(cursor.getKey(), 0)); if (previous != null) { int comparisonResult = ((VersionedMapImpl) versionedMap).getHashProvider().compare(previous, cursor.getKey()); @@ -185,7 +188,6 @@ public class MapTestEnvironment { } previous = cursor.getKey(); } - System.out.println(); } public void printComparison() { -- cgit v1.2.3-70-g09d2