Fixing long-standing bug with state based diff cursor.

By implementing an InOrderMapCursor cursor, and a MapDiffCursor that synchronize two cursors.

4 files changed, 136 insertions, 63 deletions

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.<Integer,String>builder()
+                                .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE)
+                                .setStateBasedImmutableWhenCommitting(true)
+                                .setHashProvider(MapTestEnvironment.prepareHashProvider(false))
+                                .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE)
+                                .setDefaultValue("x")
+                                .buildOne();
+
+                VersionedMapImpl<Integer,String> map = (VersionedMapImpl<Integer,String>) 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<Integer,String> map, int num) {
+                InOrderMapCursor<Integer,String> cursor = new InOrderMapCursor<>(map);
+                for(int i=0; i<num; i++) {
+                        assertTrue(cursor.move());
+                        assertFalse(cursor.isTerminated());
+                }
+                assertFalse(cursor.move());
+                assertTrue(cursor.isTerminated());
+        }
+}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java
index bf409a74..b087906d 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java
@@ -5,7 +5,10 @@ import org.junit.jupiter.api.Timeout;
 import org.junit.jupiter.params.ParameterizedTest;
 import org.junit.jupiter.params.provider.Arguments;
 import org.junit.jupiter.params.provider.MethodSource;
-import tools.refinery.store.map.*;
+import tools.refinery.store.map.DiffCursor;
+import tools.refinery.store.map.VersionedMap;
+import tools.refinery.store.map.VersionedMapStore;
+import tools.refinery.store.map.VersionedMapStoreBuilder;
 import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
 import tools.refinery.store.map.tests.utils.MapTestEnvironment;
 
@@ -16,87 +19,104 @@ import static org.junit.jupiter.api.Assertions.fail;
 import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*;
 
 class DiffCursorFuzzTest {
-        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue,
-                                                         boolean nullDefault, int commitFrequency, VersionedMapStoreBuilder<Integer, String> builder) {
+        private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault,
+                                                         int commitFrequency, boolean commitBeforeDiffCursor,
+                                                         VersionedMapStoreBuilder<Integer, String> builder) {
                 String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault);
 
                 VersionedMapStore<Integer, String> 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<Integer, String> store,
-                                                                                                                         int steps, int maxKey, String[] values, int seed, int commitFrequency) {
-                // 1. build a map with versions
-                Random r = new Random(seed);
-                VersionedMap<Integer, String> 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<Integer, String> 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<Integer, String> 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<Integer, String> 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<Integer, String> 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<Integer, String> oracle = store.createMap(travelToVersion);
+
+                                        if(commitBeforeDiffCursor) {
+                                                moving.commit();
+                                        }
+                                        DiffCursor<Integer, String> 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<Integer, String> 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<Integer, String> builder) {
+                runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
+                                noKeys, noValues, nullDefault, commitFrequency, commitBeforeDiffCursor, builder);
         }
 
         static Stream<Arguments> 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<Integer, String> builder) {
-                runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
-                                nullDefault, commitFrequency, builder);
+                        int seed, boolean commitBeforeDiffCursor, VersionedMapStoreBuilder<Integer, String> builder) {
+                runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
+                                nullDefault, commitFrequency, commitBeforeDiffCursor, builder);
         }
 
         static Stream<Arguments> 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.<Integer,String>builder()
                                         .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE)
                                         .setStateBasedImmutableWhenCommitting(true)
                                         .setHashProvider(MapTestEnvironment.prepareHashProvider(false))
-                                        .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE),
+                                        .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy
+                                        .SHARED_NODE_CACHE),
                         VersionedMapStoreBuilder.<Integer,String>builder()
                                         .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE)
                                         .setStateBasedImmutableWhenCommitting(true)
                                         .setHashProvider(MapTestEnvironment.prepareHashProvider(true))
-                                        .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE),
+                                        .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy
+                                        .SHARED_NODE_CACHE),
                         VersionedMapStoreBuilder.<Integer,String>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<K, V> {
                                                                                          VersionedMap<K, V> map2, List<Throwable> 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<Throwable> errors) {
@@ -177,7 +179,8 @@ public class MapTestEnvironment<K, V> {
                 K previous = null;
                 Cursor<K, V> cursor = versionedMap.getAll();
                 while (cursor.move()) {
-                        System.out.println(cursor.getKey() + " " + ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().getHash(cursor.getKey(), 0));
+                        //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());
@@ -185,7 +188,6 @@ public class MapTestEnvironment<K, V> {
                         }
                         previous = cursor.getKey();
                 }
-                System.out.println();
         }
 
         public void printComparison() {