From a155f6ba02e08a75ce6e474a86900b8363f506e8 Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Wed, 29 Sep 2021 02:45:57 +0200 Subject: build: migration to Gradle 7 --- .../solver/data/map/tests/fuzz/CommitFuzzTest.java | 95 +++++++++ .../data/map/tests/fuzz/ContentEqualsFuzzTest.java | 142 ++++++++++++++ .../data/map/tests/fuzz/DiffCursorFuzzTest.java | 116 +++++++++++ .../data/map/tests/fuzz/MultiThreadFuzzTest.java | 96 ++++++++++ .../map/tests/fuzz/MultiThreadTestRunnable.java | 101 ++++++++++ .../data/map/tests/fuzz/MutableFuzzTest.java | 91 +++++++++ .../fuzz/MutableImmutableCompareFuzzTest.java | 88 +++++++++ .../data/map/tests/fuzz/RestoreFuzzTest.java | 108 +++++++++++ .../data/map/tests/fuzz/SharedStoreFuzzTest.java | 112 +++++++++++ .../data/map/tests/fuzz/utils/FuzzTestUtils.java | 64 +++++++ .../map/tests/fuzz/utils/FuzzTestUtilsTest.java | 33 ++++ .../data/map/tests/utils/MapTestEnvironment.java | 213 +++++++++++++++++++++ .../data/model/hashTests/HashEfficiencyTest.java | 160 ++++++++++++++++ .../viatra/solver/data/model/tests/ModelTest.java | 147 ++++++++++++++ .../viatra/solver/data/query/test/QueryTest.java | 89 +++++++++ .../solver/data/util/CollectionsUtilTests.java | 77 ++++++++ 16 files changed, 1732 insertions(+) create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/CommitFuzzTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/ContentEqualsFuzzTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/DiffCursorFuzzTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MultiThreadFuzzTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MultiThreadTestRunnable.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MutableFuzzTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MutableImmutableCompareFuzzTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/RestoreFuzzTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/SharedStoreFuzzTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/utils/FuzzTestUtils.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/utils/FuzzTestUtilsTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/map/tests/utils/MapTestEnvironment.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/model/hashTests/HashEfficiencyTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/model/tests/ModelTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/query/test/QueryTest.java create mode 100644 store/src/test/java/org/eclipse/viatra/solver/data/util/CollectionsUtilTests.java (limited to 'store/src/test/java') diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/CommitFuzzTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/CommitFuzzTest.java new file mode 100644 index 00000000..e160df2b --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/CommitFuzzTest.java @@ -0,0 +1,95 @@ +package org.eclipse.viatra.solver.data.map.tests.fuzz; + +import static org.junit.jupiter.api.Assertions.fail; + +import java.util.Random; +import java.util.stream.Stream; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.map.VersionedMapStore; +import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl; +import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; +import org.eclipse.viatra.solver.data.map.tests.fuzz.utils.FuzzTestUtils; +import org.eclipse.viatra.solver.data.map.tests.utils.MapTestEnvironment; +import org.junit.jupiter.api.Tag; +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; + +class CommitFuzzTest { + private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, + boolean evilHash) { + String[] values = MapTestEnvironment.prepareValues(maxValue); + ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + + VersionedMapStore store = new VersionedMapStoreImpl(chp, values[0]); + VersionedMapImpl sut = (VersionedMapImpl) store.createMap(); + MapTestEnvironment e = new MapTestEnvironment(sut); + + Random r = new Random(seed); + + iterativeRandomPutsAndCommits(scenario, steps, maxKey, values, e, r, commitFrequency); + } + + private void iterativeRandomPutsAndCommits(String scenario, int steps, int maxKey, String[] values, + MapTestEnvironment e, Random r, int commitFrequency) { + int stopAt = -1; + for (int i = 0; i < steps; i++) { + int index = i + 1; + int nextKey = r.nextInt(maxKey); + String nextValue = values[r.nextInt(values.length)]; + if (index == stopAt) { + System.out.println("issue!"); + System.out.println("State before:"); + e.printComparison(); + e.sut.prettyPrint(); + System.out.println("Next: put(" + nextKey + "," + nextValue + ")"); + } + try { + e.put(nextKey, nextValue); + if (index == stopAt) { + e.sut.prettyPrint(); + } + e.checkEquivalence(scenario + ":" + index); + } catch (Exception exception) { + exception.printStackTrace(); + fail(scenario + ":" + index + ": exception happened: " + exception); + } + MapTestEnvironment.printStatus(scenario, index, steps, null); + if (index % commitFrequency == 0) { + e.sut.commit(); + } + } + } + + @ParameterizedTest(name = "Commit {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) { + runFuzzTest("CommitS" + 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 }); + } + + @ParameterizedTest(name = "Commit {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) { + runFuzzTest("CommitS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, + commitFrequency, evilHash); + } + + static Stream parametrizedSlowFuzz() { + return FuzzTestUtils.changeStepCount(parametrizedFastFuzz(), 1); + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/ContentEqualsFuzzTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/ContentEqualsFuzzTest.java new file mode 100644 index 00000000..5004c152 --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/ContentEqualsFuzzTest.java @@ -0,0 +1,142 @@ +package org.eclipse.viatra.solver.data.map.tests.fuzz; + +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.fail; + +import java.util.AbstractMap.SimpleEntry; +import java.util.Collections; +import java.util.LinkedList; +import java.util.List; +import java.util.Random; +import java.util.stream.Stream; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.map.Cursor; +import org.eclipse.viatra.solver.data.map.VersionedMap; +import org.eclipse.viatra.solver.data.map.VersionedMapStore; +import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl; +import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; +import org.eclipse.viatra.solver.data.map.tests.fuzz.utils.FuzzTestUtils; +import org.eclipse.viatra.solver.data.map.tests.utils.MapTestEnvironment; +import org.junit.jupiter.api.Tag; +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; + +class ContentEqualsFuzzTest { + private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, + boolean evilHash) { + String[] values = MapTestEnvironment.prepareValues(maxValue); + ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + + Random r = new Random(seed); + + 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) { + + VersionedMapStore store1 = new VersionedMapStoreImpl(chp, values[0]); + VersionedMap sut1 = store1.createMap(); + + // Fill one map + for (int i = 0; i < steps; i++) { + int index1 = i + 1; + int nextKey = r.nextInt(maxKey); + String nextValue = values[r.nextInt(values.length)]; + try { + sut1.put(nextKey, nextValue); + } catch (Exception exception) { + exception.printStackTrace(); + fail(scenario + ":" + index1 + ": exception happened: " + exception); + } + MapTestEnvironment.printStatus(scenario, index1, steps, "Fill"); + if (index1 % commitFrequency == 0) { + sut1.commit(); + } + } + + // Get the content of the first map + List> content = new LinkedList<>(); + Cursor cursor = sut1.getAll(); + while (cursor.move()) { + content.add(new SimpleEntry<>(cursor.getKey(), cursor.getValue())); + } + + // Randomize the order of the content + Collections.shuffle(content, r); + + VersionedMapStore store2 = new VersionedMapStoreImpl(chp, values[0]); + VersionedMap sut2 = store2.createMap(); + int index2 = 1; + for (SimpleEntry entry : content) { + sut2.put(entry.getKey(), entry.getValue()); + 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); + + // By hashcode + assertEquals(sut1.hashCode(), sut2.hashCode(), "Hash codes are not equal!"); + + // By equals + assertEquals(sut1, sut2, "Maps are not equals"); + } + + @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) { + 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 }); + } + + @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) { + runFuzzTest("CompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, + commitFrequency, evilHash); + } + + static Stream parametrizedSlowFuzz() { + return FuzzTestUtils.changeStepCount(parametrizedFastFuzz(), 1); + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/DiffCursorFuzzTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/DiffCursorFuzzTest.java new file mode 100644 index 00000000..4b79a98a --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/DiffCursorFuzzTest.java @@ -0,0 +1,116 @@ +package org.eclipse.viatra.solver.data.map.tests.fuzz; + +import static org.junit.jupiter.api.Assertions.fail; + +import java.util.Random; +import java.util.stream.Stream; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.map.DiffCursor; +import org.eclipse.viatra.solver.data.map.VersionedMapStore; +import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl; +import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; +import org.eclipse.viatra.solver.data.map.tests.fuzz.utils.FuzzTestUtils; +import org.eclipse.viatra.solver.data.map.tests.utils.MapTestEnvironment; +import org.junit.jupiter.api.Tag; +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; + +class DiffCursorFuzzTest { + private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, + boolean evilHash) { + String[] values = MapTestEnvironment.prepareValues(maxValue); + ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + + VersionedMapStore store = new VersionedMapStoreImpl(chp, values[0]); + iterativeRandomPutsAndCommitsThenDiffcursor(scenario, store, steps, maxKey, values, seed, commitFrequency); + } + + 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); + VersionedMapImpl versioned = (VersionedMapImpl) store.createMap(); + 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, + VersionedMapImpl moving = (VersionedMapImpl) 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) { + // difftravel + 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)]; + try { + moving.put(nextKey, nextValue); + } catch (Exception exception) { + exception.printStackTrace(); + fail(scenario + ":" + index + ": exception happened: " + exception); + } + if (index % commitFrequency == 0) { + versioned.commit(); + } + if (index % 10000 == 0) + System.out.println(scenario + ":" + index + "/" + steps + " building finished"); + } + } + + } + + @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") + @MethodSource + @Timeout(value = 10) + @Tag("fuzz") + void parametrizedFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, + boolean evilHash) { + runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, + noKeys, noValues, commitFrequency, evilHash); + } + + static Stream parametrizedFuzz() { + 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 = "Mutable-Immutable 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) { + runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, + commitFrequency, evilHash); + } + + static Stream parametrizedSlowFuzz() { + return FuzzTestUtils.changeStepCount(parametrizedFuzz(), 1); + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MultiThreadFuzzTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MultiThreadFuzzTest.java new file mode 100644 index 00000000..c3a3e8ea --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MultiThreadFuzzTest.java @@ -0,0 +1,96 @@ +package org.eclipse.viatra.solver.data.map.tests.fuzz; + +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.fail; + +import java.util.Collections; +import java.util.LinkedList; +import java.util.List; +import java.util.stream.Stream; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.map.VersionedMapStore; +import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl; +import org.eclipse.viatra.solver.data.map.tests.fuzz.utils.FuzzTestUtils; +import org.eclipse.viatra.solver.data.map.tests.utils.MapTestEnvironment; +import org.junit.jupiter.api.Tag; +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; + +class MultiThreadFuzzTest { + public static final int noThreads = 32; + + private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, + boolean evilHash) { + String[] values = MapTestEnvironment.prepareValues(maxValue); + ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + + VersionedMapStore store = new VersionedMapStoreImpl(chp, values[0]); + + // initialize runnables + MultiThreadTestRunnable[] runnables = new MultiThreadTestRunnable[noThreads]; + for(int i = 0; i errors = new LinkedList<>(); + for(int i = 0; i parametrizedFastFuzz() { + return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 }, + new Object[] { 2, 3 }, new Object[] { 10, 100 }, new Object[] { 1, 2, 3 }, + new Object[] { false, true }); + } + + @ParameterizedTest(name = "Multithread {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) { + runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, + commitFrequency, evilHash); + } + + static Stream parametrizedSlowFuzz() { + return FuzzTestUtils.changeStepCount(RestoreFuzzTest.parametrizedFastFuzz(), 1); + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MultiThreadTestRunnable.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MultiThreadTestRunnable.java new file mode 100644 index 00000000..a18298a2 --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MultiThreadTestRunnable.java @@ -0,0 +1,101 @@ +package org.eclipse.viatra.solver.data.map.tests.fuzz; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.Random; + +import org.eclipse.viatra.solver.data.map.VersionedMapStore; +import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; +import org.eclipse.viatra.solver.data.map.tests.utils.MapTestEnvironment; + +public class MultiThreadTestRunnable implements Runnable { + String scenario; + VersionedMapStore store; + int steps; + int maxKey; + String[] values; + int seed; + int commitFrequency; + List errors = new LinkedList<>(); + + public MultiThreadTestRunnable(String scenario, VersionedMapStore store, int steps, + int maxKey, String[] values, int seed, int commitFrequency) { + super(); + this.scenario = scenario; + this.store = store; + this.steps = steps; + this.maxKey = maxKey; + this.values = values; + this.seed = seed; + this.commitFrequency = commitFrequency; + } + + private void logAndThrowError(String message) { + AssertionError error = new AssertionError(message); + errors.add(error); + } + + public List getErrors() { + return errors; + } + + @Override + public void run() { + // 1. build a map with versions + Random r = new Random(seed); + VersionedMapImpl versioned = (VersionedMapImpl) store.createMap(); + Map index2Version = new HashMap<>(); + + 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(); + logAndThrowError(scenario + ":" + index + ": exception happened: " + exception); + } + if (index % commitFrequency == 0) { + long version = versioned.commit(); + index2Version.put(i, version); + } + MapTestEnvironment.printStatus(scenario, index, steps, "building"); + } + // 2. create a non-versioned + VersionedMapImpl reference = (VersionedMapImpl) store.createMap(); + r = new Random(seed); + Random r2 = new Random(seed+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 { + reference.put(nextKey, nextValue); + } catch (Exception exception) { + exception.printStackTrace(); + logAndThrowError(scenario + ":" + index + ": exception happened: " + exception); + } + // go back to an existing state and compare to the reference + if (index % (commitFrequency) == 0) { + versioned.restore(index2Version.get(i)); + MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference, versioned,errors); + + // go back to a random state (probably created by another thread) + List states = new ArrayList<>(store.getStates()); + Collections.shuffle(states, r2); + for(Long state : states.subList(0, Math.min(states.size(), 100))) { + versioned.restore(state); + } + versioned.restore(index2Version.get(i)); + } + + MapTestEnvironment.printStatus(scenario, index, steps, "comparison"); + } + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MutableFuzzTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MutableFuzzTest.java new file mode 100644 index 00000000..2d589dc9 --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MutableFuzzTest.java @@ -0,0 +1,91 @@ +package org.eclipse.viatra.solver.data.map.tests.fuzz; + +import static org.junit.jupiter.api.Assertions.fail; + +import java.util.Random; +import java.util.stream.Stream; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.map.VersionedMapStore; +import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl; +import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; +import org.eclipse.viatra.solver.data.map.tests.fuzz.utils.FuzzTestUtils; +import org.eclipse.viatra.solver.data.map.tests.utils.MapTestEnvironment; +import org.junit.jupiter.api.Tag; +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; + +class MutableFuzzTest { + private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean evilHash) { + String[] values = MapTestEnvironment.prepareValues(maxValue); + ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + + VersionedMapStore store = new VersionedMapStoreImpl(chp, values[0]); + VersionedMapImpl sut = (VersionedMapImpl) store.createMap(); + MapTestEnvironment e = new MapTestEnvironment(sut); + + Random r = new Random(seed); + + iterativeRandomPuts(scenario, steps, maxKey, values, e, r); + } + + private void iterativeRandomPuts(String scenario, int steps, int maxKey, String[] values, + MapTestEnvironment e, Random r) { + int stopAt = -1; + for (int i = 0; i < steps; i++) { + int index = i + 1; + int nextKey = r.nextInt(maxKey); + String nextValue = values[r.nextInt(values.length)]; + if (index == stopAt) { + System.out.println("issue!"); + System.out.println("State before:"); + e.printComparison(); + e.sut.prettyPrint(); + System.out.println("Next: put(" + nextKey + "," + nextValue + ")"); + } + try { + e.put(nextKey, nextValue); + if (index == stopAt) { + e.sut.prettyPrint(); + } + e.checkEquivalence(scenario + ":" + index); + } catch (Exception exception) { + exception.printStackTrace(); + fail(scenario + ":" + index + ": exception happened: " + exception); + } + MapTestEnvironment.printStatus(scenario, index, steps, null); + } + } + + @ParameterizedTest(name = "Mutable {index}/{0} Steps={1} Keys={2} Values={3} seed={4} evil-hash={5}") + @MethodSource + @Timeout(value = 10) + @Tag("fuzz") + void parametrizedFuzz(int test, int steps, int noKeys, int noValues, int seed, boolean evilHash) { + runFuzzTest( + "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed + "H" + (evilHash ? "Evil" : "Normal"), + seed, steps, noKeys, noValues, evilHash); + } + + static Stream parametrizedFuzz() { + return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, + new Object[] { 3, 32, 32 * 32, 32 * 32 * 32 * 32 }, new Object[] { 2, 3 }, new Object[] { 1, 2, 3 }, + new Object[] { false, true }); + } + + @ParameterizedTest(name = "Mutable {index}/{0} Steps={1} Keys={2} Values={3} seed={4} evil-hash={5}") + @MethodSource + @Tag("fuzz") + @Tag("slow") + void parametrizedSlowFuzz(int test, int steps, int noKeys, int noValues, int seed, boolean evilHash) { + runFuzzTest( + "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed + "H" + (evilHash ? "Evil" : "Normal"), + seed, steps, noKeys, noValues, evilHash); + } + + static Stream parametrizedSlowFuzz() { + return FuzzTestUtils.changeStepCount(parametrizedFuzz(), 1); + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MutableImmutableCompareFuzzTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MutableImmutableCompareFuzzTest.java new file mode 100644 index 00000000..cc2abfe4 --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/MutableImmutableCompareFuzzTest.java @@ -0,0 +1,88 @@ +package org.eclipse.viatra.solver.data.map.tests.fuzz; + +import static org.junit.jupiter.api.Assertions.fail; + +import java.util.Random; +import java.util.stream.Stream; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.map.VersionedMapStore; +import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl; +import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; +import org.eclipse.viatra.solver.data.map.tests.fuzz.utils.FuzzTestUtils; +import org.eclipse.viatra.solver.data.map.tests.utils.MapTestEnvironment; +import org.junit.jupiter.api.Tag; +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; + +class MutableImmutableCompareFuzzTest { + private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, + boolean evilHash) { + String[] values = MapTestEnvironment.prepareValues(maxValue); + ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + + VersionedMapStore store = new VersionedMapStoreImpl(chp, values[0]); + VersionedMapImpl immutable = (VersionedMapImpl) store.createMap(); + VersionedMapImpl mutable = (VersionedMapImpl) store.createMap(); + + Random r = new Random(seed); + + iterativeRandomPutsAndCommitsAndCompare(scenario, immutable, mutable, steps, maxKey, values, r, + commitFrequency); + } + + private void iterativeRandomPutsAndCommitsAndCompare(String scenario, VersionedMapImpl immutable, + VersionedMapImpl mutable, int steps, int maxKey, String[] values, Random r, + int commitFrequency) { + for (int i = 0; i < steps; i++) { + int index = i + 1; + int nextKey = r.nextInt(maxKey); + String nextValue = values[r.nextInt(values.length)]; + try { + immutable.put(nextKey, nextValue); + mutable.put(nextKey, nextValue); + } catch (Exception exception) { + exception.printStackTrace(); + fail(scenario + ":" + index + ": exception happened: " + exception); + } + if (index % commitFrequency == 0) { + immutable.commit(); + } + MapTestEnvironment.compareTwoMaps(scenario + ":" + index, immutable, mutable); + + MapTestEnvironment.printStatus(scenario, index, steps, null); + } + } + + @ParameterizedTest(name = "Mutable-Immutable 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) { + runFuzzTest("MutableImmutableCompareS" + 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 }); + } + + @ParameterizedTest(name = "Mutable-Immutable 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) { + runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, + noKeys, noValues, commitFrequency, evilHash); + } + + static Stream parametrizedSlowFuzz() { + return FuzzTestUtils.changeStepCount(MutableImmutableCompareFuzzTest.parametrizedFastFuzz(), 1); + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/RestoreFuzzTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/RestoreFuzzTest.java new file mode 100644 index 00000000..7d9f5372 --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/RestoreFuzzTest.java @@ -0,0 +1,108 @@ +package org.eclipse.viatra.solver.data.map.tests.fuzz; + +import static org.junit.jupiter.api.Assertions.fail; + +import java.util.HashMap; +import java.util.Map; +import java.util.Random; +import java.util.stream.Stream; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.map.VersionedMapStore; +import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl; +import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; +import org.eclipse.viatra.solver.data.map.tests.fuzz.utils.FuzzTestUtils; +import org.eclipse.viatra.solver.data.map.tests.utils.MapTestEnvironment; +import org.junit.jupiter.api.Tag; +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; + +class RestoreFuzzTest { + private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, + boolean evilHash) { + String[] values = MapTestEnvironment.prepareValues(maxValue); + ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + + VersionedMapStore store = new VersionedMapStoreImpl(chp, values[0]); + + iterativeRandomPutsAndCommitsThenRestore(scenario, store, steps, maxKey, values, seed, commitFrequency); + } + + private void iterativeRandomPutsAndCommitsThenRestore(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); + VersionedMapImpl versioned = (VersionedMapImpl) store.createMap(); + Map index2Version = new HashMap<>(); + + 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(); + index2Version.put(i, version); + } + MapTestEnvironment.printStatus(scenario, index, steps, "building"); + } + // 2. create a non-versioned and + VersionedMapImpl reference = (VersionedMapImpl) store.createMap(); + r = new Random(seed); + + for (int i = 0; i < steps; i++) { + int index = i + 1; + int nextKey = r.nextInt(maxKey); + String nextValue = values[r.nextInt(values.length)]; + try { + reference.put(nextKey, nextValue); + } catch (Exception exception) { + exception.printStackTrace(); + fail(scenario + ":" + index + ": exception happened: " + exception); + } + if (index % commitFrequency == 0) { + versioned.restore(index2Version.get(i)); + MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference, versioned); + } + MapTestEnvironment.printStatus(scenario, index, steps, "comparison"); + } + + } + + @ParameterizedTest(name = "Restore {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") + @MethodSource + @Timeout(value = 10) + @Tag("smoke") + void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, + boolean evilHash) { + runFuzzTest("RestoreS" + 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 }); + } + + @ParameterizedTest(name = "Restore {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") + @MethodSource + @Tag("smoke") + @Tag("slow") + void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, + boolean evilHash) { + runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, + commitFrequency, evilHash); + } + + static Stream parametrizedSlowFuzz() { + return FuzzTestUtils.changeStepCount(RestoreFuzzTest.parametrizedFastFuzz(), 1); + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/SharedStoreFuzzTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/SharedStoreFuzzTest.java new file mode 100644 index 00000000..800308b4 --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/SharedStoreFuzzTest.java @@ -0,0 +1,112 @@ +package org.eclipse.viatra.solver.data.map.tests.fuzz; + +import java.util.HashMap; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.Random; +import java.util.stream.Stream; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.map.VersionedMapStore; +import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl; +import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; +import org.eclipse.viatra.solver.data.map.tests.fuzz.utils.FuzzTestUtils; +import org.eclipse.viatra.solver.data.map.tests.utils.MapTestEnvironment; +import org.junit.jupiter.api.Tag; +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; + +class SharedStoreFuzzTest { + private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, + boolean evilHash) { + String[] values = MapTestEnvironment.prepareValues(maxValue); + ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + + List> stores = VersionedMapStoreImpl.createSharedVersionedMapStores(5, chp, values[0]); + + iterativeRandomPutsAndCommitsThenRestore(scenario, stores, steps, maxKey, values, seed, commitFrequency); + } + + private void iterativeRandomPutsAndCommitsThenRestore(String scenario, List> stores, + int steps, int maxKey, String[] values, int seed, int commitFrequency) { + // 1. maps with versions + Random r = new Random(seed); + List> versioneds = new LinkedList<>(); + for(VersionedMapStore store : stores) { + versioneds.add((VersionedMapImpl) store.createMap()); + } + + List> index2Version = new LinkedList<>(); + for(int i = 0; i()); + } + + for (int i = 0; i < steps; i++) { + int stepIndex = i + 1; + for (int storeIndex = 0; storeIndex> reference = new LinkedList<>(); + for(VersionedMapStore store : stores) { + reference.add((VersionedMapImpl) store.createMap()); + } + r = new Random(seed); + + for (int i = 0; i < steps; i++) { + int index = i + 1; + for (int storeIndex = 0; storeIndex 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 }); + } + + @ParameterizedTest(name = "Shared Store {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") + @MethodSource + @Tag("smoke") + @Tag("slow") + void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, + boolean evilHash) { + runFuzzTest("SharedS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, + commitFrequency, evilHash); + } + + static Stream parametrizedSlowFuzz() { + return FuzzTestUtils.changeStepCount(RestoreFuzzTest.parametrizedFastFuzz(), 1); + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/utils/FuzzTestUtils.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/utils/FuzzTestUtils.java new file mode 100644 index 00000000..ec21bb7b --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/utils/FuzzTestUtils.java @@ -0,0 +1,64 @@ +package org.eclipse.viatra.solver.data.map.tests.fuzz.utils; + +import java.util.Arrays; +import java.util.LinkedList; +import java.util.List; +import java.util.stream.Stream; + +import org.junit.jupiter.params.provider.Arguments; + +public final class FuzzTestUtils { + public static final int FAST_STEP_COUNT = 500; + public static final int SLOW_STEP_COUNT = 32 * 32 * 32 * 32; + + private FuzzTestUtils() { + throw new IllegalStateException("This is a static utility class and should not be instantiated directly"); + } + + public static Stream changeStepCount(Stream arguments, int parameterIndex) { + return arguments.map(x -> Arguments.of(updatedStepCount(x.get(), parameterIndex))); + } + + public static Object[] updatedStepCount(Object[] arguments, int parameterIndex) { + Object[] copy = Arrays.copyOf(arguments, arguments.length); + copy[parameterIndex] = SLOW_STEP_COUNT; + return copy; + } + + static List> permutationInternal(int from, Object[]... valueOption) { + if (valueOption.length == from) { + return List.of(List.of()); + } else { + Object[] permuteThis = valueOption[from]; + List> otherCombination = permutationInternal(from + 1, valueOption); + List> result = new LinkedList<>(); + for (Object permuteThisElement : permuteThis) { + for (List otherCombinationList : otherCombination) { + List newResult = new LinkedList<>(); + newResult.add(permuteThisElement); + newResult.addAll(otherCombinationList); + result.add(newResult); + } + } + return result; + } + } + + public static Stream permutation(Object[]... valueOption) { + List> permutations = permutationInternal(0, valueOption); + return permutations.stream().map(x -> Arguments.of(x.toArray())); + } + + public static Stream permutationWithSize(Object[]... valueOption) { + int size = 1; + for (int i = 0; i < valueOption.length; i++) { + size *= valueOption[i].length; + } + Object[][] newValueOption = new Object[valueOption.length + 1][]; + newValueOption[0] = new Object[] { size }; + for (int i = 1; i < newValueOption.length; i++) { + newValueOption[i] = valueOption[i - 1]; + } + return permutation(newValueOption); + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/utils/FuzzTestUtilsTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/utils/FuzzTestUtilsTest.java new file mode 100644 index 00000000..3f4214bc --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/fuzz/utils/FuzzTestUtilsTest.java @@ -0,0 +1,33 @@ +package org.eclipse.viatra.solver.data.map.tests.fuzz.utils; + +import static org.junit.jupiter.api.Assertions.assertEquals; + +import java.util.List; + +import org.junit.jupiter.api.Test; + +class FuzzTestUtilsTest { + @Test + void permutationInternalTest() { + List> res = FuzzTestUtils.permutationInternal(0, new Object[] { 1, 2, 3 }, + new Object[] { 'a', 'b', 'c' }, new Object[] { "alpha", "beta", "gamma", "delta" }); + assertEquals(3 * 3 * 4, res.size()); + } + + @Test + void permutationTest1() { + var res = FuzzTestUtils.permutation(new Object[] { 1, 2, 3 }, new Object[] { 'a', 'b', 'c' }, + new Object[] { "alpha", "beta", "gamma", "delta" }); + assertEquals(3 * 3 * 4, res.count()); + } + + @Test + void permutationTest2() { + var res = FuzzTestUtils.permutation(new Object[] { 1, 2, 3 }, new Object[] { 'a', 'b', 'c' }, + new Object[] { "alpha", "beta", "gamma", "delta" }); + var arguments = res.findFirst().get().get(); + assertEquals(1, arguments[0]); + assertEquals('a', arguments[1]); + assertEquals("alpha", arguments[2]); + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/utils/MapTestEnvironment.java b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/utils/MapTestEnvironment.java new file mode 100644 index 00000000..4c043350 --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/map/tests/utils/MapTestEnvironment.java @@ -0,0 +1,213 @@ +package org.eclipse.viatra.solver.data.map.tests.utils; + +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.assertTrue; +import static org.junit.jupiter.api.Assertions.fail; + +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.TreeMap; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.map.Cursor; +import org.eclipse.viatra.solver.data.map.VersionedMap; +import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; + +public class MapTestEnvironment { + public static String[] prepareValues(int maxValue) { + String[] values = new String[maxValue]; + values[0] = "DEFAULT"; + for (int i = 1; i < values.length; i++) { + values[i] = "VAL" + i; + } + return values; + } + + public static ContinousHashProvider prepareHashProvider(final boolean evil) { + // Use maxPrime = 2147483629 + + ContinousHashProvider chp = new ContinousHashProvider() { + + @Override + public int getHash(Integer key, int index) { + if (evil && index < 15 && index < key / 3) { + return 7; + } + int result = 1; + final int prime = 31; + + result = prime * result + key; + result = prime * result + index; + + return result; + } + }; + return chp; + } + + public static void printStatus(String scenario, int actual, int max, String stepName) { + if (actual % 10000 == 0) { + String printStepName = stepName == null ? "" : stepName; + System.out.format(scenario + ":%d/%d (%d%%) " + printStepName + "%n", actual, max, actual * 100 / max); + } + + } + + public static void compareTwoMaps(String title, VersionedMapImpl map1, + VersionedMapImpl map2) { + compareTwoMaps(title, map1, map2, null); + } + public static void compareTwoMaps(String title, VersionedMapImpl map1, + VersionedMapImpl map2, List errors) { + // 1. Comparing cursors. + 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); + cursor1.move(); + cursor2.move(); + } + if (!cursor2.isTerminated()) + fail("cursor 1 terminated before cursor 2"); + + // 2.1. comparing hash codes + assertEqualsList(map1.hashCode(), map2.hashCode(), title + ": hash code check",errors); + assertEqualsList(map1, map2, title + ": 1.equals(2)",errors); + assertEqualsList(map2, map1, title + ": 2.equals(1)",errors); + } + private static void assertEqualsList(Object o1, Object o2, String message, List errors) { + 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); + errors.add(error); + } + } + } + } + + public VersionedMapImpl sut; + Map oracle = new HashMap(); + + public MapTestEnvironment(VersionedMapImpl sut) { + this.sut = sut; + } + + public void put(K key, V value) { + V oldSutValue = sut.put(key, value); + V oldOracleValue; + if (value != sut.getDefaultValue()) { + oldOracleValue = oracle.put(key, value); + } else { + oldOracleValue = oracle.remove(key); + } + if(oldSutValue == sut.getDefaultValue() && oldOracleValue != null) { + fail("After put, SUT old value was default, but oracle old walue was " + oldOracleValue); + } + if(oldSutValue != sut.getDefaultValue()) { + assertEquals(oldOracleValue, oldSutValue); + } + } + + public void checkEquivalence(String title) { + // 0. Checking integrity + try { + sut.checkIntegrity(); + } catch (IllegalStateException e) { + fail(title + ": " + e.getMessage()); + } + + // 1. Checking: if Reference contains pair, then SUT contains + // pair. + // Tests get functions + for (Entry entry : oracle.entrySet()) { + V sutValue = sut.get(entry.getKey()); + V oracleValue = entry.getValue(); + if (sutValue != oracleValue) { + printComparison(); + fail(title + ": Non-equivalent get(" + entry.getKey() + ") results: SUT=" + sutValue + ", Oracle=" + + oracleValue + "!"); + } + } + + // 2. Checking: if SUT contains pair, then Reference contains + // pair. + // Tests iterators + int elementsInSutEntrySet = 0; + Cursor cursor = sut.getAll(); + while (cursor.move()) { + elementsInSutEntrySet++; + K key = cursor.getKey(); + V sutValue = cursor.getValue(); + // System.out.println(key + " -> " + sutValue); + V oracleValue = oracle.get(key); + if (sutValue != oracleValue) { + printComparison(); + fail(title + ": Non-equivalent entry in iterator: SUT=<" + key + "," + sutValue + ">, Oracle=<" + key + + "," + oracleValue + ">!"); + } + + } + + // 3. Checking sizes + // Counting of non-default value pairs. + int oracleSize = oracle.entrySet().size(); + long sutSize = sut.getSize(); + if (oracleSize != sutSize || oracleSize != elementsInSutEntrySet) { + printComparison(); + fail(title + ": Non-eqivalent size() result: SUT.getSize()=" + sutSize + ", SUT.entryset.size=" + + elementsInSutEntrySet + ", Oracle=" + oracleSize + "!"); + } + } + + public static void checkOrder(String scenario, VersionedMap versionedMap) { + K previous = null; + Cursor cursor = versionedMap.getAll(); + 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!"); + } + previous = cursor.getKey(); + } + System.out.println(); + } + + public void printComparison() { + System.out.println("SUT:"); + printEntrySet(sut.getAll()); + System.out.println("Oracle:"); + printEntrySet(oracle.entrySet().iterator()); + } + + private void printEntrySet(Iterator> iterator) { + TreeMap treemap = new TreeMap<>(); + while (iterator.hasNext()) { + Entry entry = iterator.next(); + treemap.put(entry.getKey(), entry.getValue()); + } + for (Entry e : treemap.entrySet()) { + System.out.println("\t" + e.getKey() + " -> " + e.getValue()); + } + } + + private void printEntrySet(Cursor cursor) { + TreeMap treemap = new TreeMap<>(); + while (cursor.move()) { + treemap.put(cursor.getKey(), cursor.getValue()); + } + for (Entry e : treemap.entrySet()) { + System.out.println("\t" + e.getKey() + " -> " + e.getValue()); + } + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/model/hashTests/HashEfficiencyTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/model/hashTests/HashEfficiencyTest.java new file mode 100644 index 00000000..c4d98a43 --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/model/hashTests/HashEfficiencyTest.java @@ -0,0 +1,160 @@ +package org.eclipse.viatra.solver.data.model.hashTests; + +import static org.junit.jupiter.api.Assertions.assertEquals; + +import java.util.ArrayList; +import java.util.LinkedList; +import java.util.List; +import java.util.Random; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.model.Tuple; +import org.eclipse.viatra.solver.data.model.TupleHashProvider; +import org.eclipse.viatra.solver.data.model.TupleHashProviderBitMagic; +import org.junit.jupiter.api.Test; + +class HashEfficiencyTest { + + private static List permutations(int range, int arity) { + if(arity == 1) { + List result = new ArrayList<>(range); + for(int i=0; i 1) { + List smallers = permutations(range, arity-1); + List result = new ArrayList<>(range*smallers.size()); + for(Tuple smaller : smallers) { + for(int i=0; i nPermutations(int arity, int n) { + int range = amountToRange(arity, n); + List permutations = permutations(range, arity); + return permutations.subList(0, n); + } + + public static List nRandoms(int arity, int n, int seed) { + int range = amountToRange(arity, n); + List permutations = new ArrayList<>(n); + Random r = new Random(seed); + for(int i = 0; i p = permutations(10, 2); + assertEquals(p.size(),10*10); + } +// private void printTuples(List p) { +// for(Tuple element : p) { +// System.out.println(element); +// } +// } + @Test + void nPermutationTest() { + final int amount = 500; + List p = nPermutations(2, amount); + assertEquals(amount,p.size()); + } + @Test + void nRandomTest() { + final int amount = 500; + List p = nRandoms(2, amount, 1);; + assertEquals(amount,p.size()); + } + private static double calculateHashClashes(List tuples, ContinousHashProvider chp) { + int sumClashes = 0; + + for(int i = 0; i chp, Tuple a, Tuple b) { + if(a.equals(b)) return 0; + final int bits = 5; + final int segments = Integer.SIZE/bits; + final int mask = (1<>(depth*5))&mask; + int bHash = (chp.getHash(b, index)>>(depth*5))&mask; + if(aHash != bHash) { + return i+1; + } + if(i>400) { + throw new IllegalStateException(a+" vs "+b); + } + } + } + private static double caclulateOptimalHashClash(int size) { + return (Math.log(size)/Math.log(32)); + } + public static void main(String[] args) { + List hashNames = new LinkedList<>(); + List> hashes = new LinkedList<>(); + hashNames.add("PrimeGroup"); + hashes.add(new TupleHashProvider()); + hashNames.add("BitMagic"); + hashes.add(new TupleHashProviderBitMagic()); + + int[] arities = new int[] {2,3,4,5}; + int[] sizes = new int[] {32*32,32*32*8}; + + System.out.println("Size,Arity,DataSource,Hash,Chashes,Optimal,Badness"); + for(int size : sizes) { + double optimalClashes = caclulateOptimalHashClash(size); + for(int arity : arities) { + List dataSourceNames = new LinkedList<>(); + List> dataSources = new LinkedList<>(); + +// dataSourceNames.add("Permutation"); +// dataSources.add(nPermutations(arity, size)); + dataSourceNames.add("Random"); + dataSources.add(nRandoms(arity, size, 0)); + + for(int dataSourceIndex = 0; dataSourceIndex person = new Relation<>("Person", 1, false); + Relation friend = new Relation<>("friend", 2, false); + + ModelStore store = new ModelStoreImpl(Set.of(person, friend)); + Model model = store.createModel(); + + assertTrue(store.getDataRepresentations().contains(person)); + assertTrue(store.getDataRepresentations().contains(friend)); + assertTrue(model.getDataRepresentations().contains(person)); + assertTrue(model.getDataRepresentations().contains(friend)); + + Relation other = new Relation("other", 2, null); + assertFalse(model.getDataRepresentations().contains(other)); + } + + @Test + void modelBuildingTest() { + Relation person = new Relation<>("Person", 1, false); + Relation age = new Relation("age", 1, null); + Relation friend = new Relation<>("friend", 2, false); + + ModelStore store = new ModelStoreImpl(Set.of(person, age, friend)); + Model model = store.createModel(); + + model.put(person, Tuple.of(0), true); + model.put(person, Tuple.of(1), true); + model.put(age, Tuple.of(0), 3); + model.put(age, Tuple.of(1), 1); + model.put(friend, Tuple.of(0, 1), true); + model.put(friend, Tuple.of(1, 0), true); + + assertTrue(model.get(person, Tuple.of(0))); + assertTrue(model.get(person, Tuple.of(1))); + assertFalse(model.get(person, Tuple.of(2))); + + assertEquals(3, model.get(age, Tuple.of(0))); + assertEquals(1, model.get(age, Tuple.of(1))); + assertEquals(null, model.get(age, Tuple.of(2))); + + assertTrue(model.get(friend, Tuple.of(0, 1))); + assertFalse(model.get(friend, Tuple.of(0, 5))); + } + + @Test + void modelBuildingArityFailTest() { + Relation person = new Relation<>("Person", 1, false); + ModelStore store = new ModelStoreImpl(Set.of(person)); + Model model = store.createModel(); + + final Tuple tuple3 = Tuple.of(1, 1, 1); + Assertions.assertThrows(IllegalArgumentException.class, () -> model.put(person, tuple3, true)); + Assertions.assertThrows(IllegalArgumentException.class, () -> model.get(person, tuple3)); + } + + @Test + void modelBuildingNullFailTest() { + Relation age = new Relation("age", 1, null); + ModelStore store = new ModelStoreImpl(Set.of(age)); + Model model = store.createModel(); + + model.put(age, Tuple.of(1), null); // valid + Assertions.assertThrows(IllegalArgumentException.class, () -> model.put(age, null, 1)); + Assertions.assertThrows(IllegalArgumentException.class, () -> model.get(age, null)); + + } + + @Test + void modelUpdateTest() { + Relation person = new Relation<>("Person", 1, false); + Relation age = new Relation("age", 1, null); + Relation friend = new Relation<>("friend", 2, false); + + ModelStore store = new ModelStoreImpl(Set.of(person, age, friend)); + Model model = store.createModel(); + + model.put(person, Tuple.of(0), true); + model.put(person, Tuple.of(1), true); + model.put(age, Tuple.of(0), 3); + model.put(age, Tuple.of(1), 1); + model.put(friend, Tuple.of(0, 1), true); + model.put(friend, Tuple.of(1, 0), true); + + assertEquals(3, model.get(age, Tuple.of(0))); + assertTrue(model.get(friend, Tuple.of(0, 1))); + + model.put(age, Tuple.of(0), 4); + model.put(friend, Tuple.of(0, 1), false); + + assertEquals(4, model.get(age, Tuple.of(0))); + assertFalse(model.get(friend, Tuple.of(0, 1))); + } + + @Test + void restoreTest() { + Relation person = new Relation("Person", 1, false); + Relation friend = new Relation("friend", 2, false); + + ModelStore store = new ModelStoreImpl(Set.of(person, friend)); + Model model = store.createModel(); + + model.put(person, Tuple.of(0), true); + model.put(person, Tuple.of(1), true); + model.put(friend, Tuple.of(0, 1), true); + model.put(friend, Tuple.of(1, 0), true); + long state1 = model.commit(); + + assertFalse(model.get(person, Tuple.of(2))); + assertFalse(model.get(friend, Tuple.of(0, 2))); + + model.put(person, Tuple.of(2), true); + model.put(friend, Tuple.of(0, 2), true); + long state2 = model.commit(); + + assertTrue(model.get(person, Tuple.of(2))); + assertTrue(model.get(friend, Tuple.of(0, 2))); + + model.restore(state1); + + assertFalse(model.get(person, Tuple.of(2))); + assertFalse(model.get(friend, Tuple.of(0, 2))); + + model.restore(state2); + + assertTrue(model.get(person, Tuple.of(2))); + assertTrue(model.get(friend, Tuple.of(0, 2))); + } +} diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/query/test/QueryTest.java b/store/src/test/java/org/eclipse/viatra/solver/data/query/test/QueryTest.java new file mode 100644 index 00000000..182f6c94 --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/query/test/QueryTest.java @@ -0,0 +1,89 @@ +package org.eclipse.viatra.solver.data.query.test; + +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.assertFalse; +import static org.junit.jupiter.api.Assertions.assertTrue; + +import java.util.Collection; +import java.util.Set; + +import org.eclipse.viatra.query.runtime.api.AdvancedViatraQueryEngine; +import org.eclipse.viatra.query.runtime.api.GenericPatternMatch; +import org.eclipse.viatra.query.runtime.api.GenericPatternMatcher; +import org.eclipse.viatra.query.runtime.api.GenericQuerySpecification; +import org.eclipse.viatra.query.runtime.api.ViatraQueryEngine; +import org.eclipse.viatra.solver.data.model.Model; +import org.eclipse.viatra.solver.data.model.ModelStore; +import org.eclipse.viatra.solver.data.model.ModelStoreImpl; +import org.eclipse.viatra.solver.data.model.Tuple; +import org.eclipse.viatra.solver.data.model.representation.Relation; +import org.eclipse.viatra.solver.data.model.representation.TruthValue; +import org.eclipse.viatra.solver.data.query.RelationalScope; +import org.eclipse.viatra.solver.data.query.internal.PredicateTranslator; +import org.eclipse.viatra.solver.data.query.view.FilteredRelationView; +import org.eclipse.viatra.solver.data.query.view.FunctionalRelationView; +import org.eclipse.viatra.solver.data.query.view.RelationView; +import org.eclipse.viatra.solver.data.query.view.KeyOnlyRelationView; +import org.junit.jupiter.api.Test; + +class QueryTest { + @Test + void minimalTest() { + Relation person = new Relation<>("Person", 1, false); + + RelationView persionView = new KeyOnlyRelationView(person); + GenericQuerySpecification personQuery = (new PredicateTranslator("PersonQuery")) + .addParameter("p", persionView).addConstraint(persionView, "p").build(); + + ModelStore store = new ModelStoreImpl(Set.of(person)); + Model model = store.createModel(); + + model.put(person, Tuple.of(0), true); + model.put(person, Tuple.of(1), true); + + RelationalScope scope = new RelationalScope(model, Set.of(persionView)); + + ViatraQueryEngine engine = AdvancedViatraQueryEngine.on(scope); + GenericPatternMatcher personMatcher = engine.getMatcher(personQuery); + + assertEquals(2, personMatcher.countMatches()); + } + + void modelBuildingTest() { + Relation person = new Relation<>("Person", 1, false); + Relation age = new Relation("age", 1, null); + Relation friend = new Relation<>("friend", 2, TruthValue.False); + + ModelStore store = new ModelStoreImpl(Set.of(person, age, friend)); + Model model = store.createModel(); + + model.put(person, Tuple.of(0), true); + model.put(person, Tuple.of(1), true); + model.put(age, Tuple.of(0), 3); + model.put(age, Tuple.of(1), 1); + model.put(friend, Tuple.of(0, 1), TruthValue.True); + model.put(friend, Tuple.of(1, 0), TruthValue.Unknown); + + // Sanity check + assertTrue(model.get(person, Tuple.of(0))); + assertTrue(model.get(person, Tuple.of(1))); + assertFalse(model.get(person, Tuple.of(2))); + + RelationView persionView = new KeyOnlyRelationView(person); + RelationView ageView = new FunctionalRelationView<>(age); + RelationView friendMustView = new FilteredRelationView(friend, (k, v) -> v.must()); + RelationView friendMayView = new FilteredRelationView(friend, (k, v) -> v.may()); + + RelationalScope scope = new RelationalScope(model, Set.of(persionView, ageView, friendMustView, friendMayView)); + + GenericQuerySpecification personQuery = (new PredicateTranslator("PersonQuery")) + .addParameter("p", persionView).addConstraint(persionView, "p").build(); + + ViatraQueryEngine engine = AdvancedViatraQueryEngine.on(scope); + GenericPatternMatcher personMatcher = engine.getMatcher(personQuery); + Collection personMatches = personMatcher.getAllMatches(); + for (GenericPatternMatch personMatch : personMatches) { + System.out.println(personMatch); + } + } +} \ No newline at end of file diff --git a/store/src/test/java/org/eclipse/viatra/solver/data/util/CollectionsUtilTests.java b/store/src/test/java/org/eclipse/viatra/solver/data/util/CollectionsUtilTests.java new file mode 100644 index 00000000..16368912 --- /dev/null +++ b/store/src/test/java/org/eclipse/viatra/solver/data/util/CollectionsUtilTests.java @@ -0,0 +1,77 @@ +package org.eclipse.viatra.solver.data.util; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; + +import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.api.Test; + +import static org.eclipse.viatra.solver.data.util.CollectionsUtil.*; +import static org.junit.jupiter.api.Assertions.assertEquals; + +class CollectionsUtilTests { + List list10 = List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); + List listTen = List.of("1", "2", "3", "4", "5", "6", "7", "8", "9", "10"); + + private static void compare(Iterable a, Iterable b) { + List listA = toList(a); + List listB = toList(b); + assertEquals(listA, listB); + } + + private static List toList(Iterable a) { + List result = new ArrayList(); + Iterator iterator = a.iterator(); + while (iterator.hasNext()) { + result.add(iterator.next()); + } + return result; + } + + @Test + void testFilterEven() { + compare(List.of(2, 4, 6, 8, 10), filter(list10, (x -> x % 2 == 0))); + } + + @Test + void testFilterOdd() { + compare(List.of(1, 3, 5, 7, 9), filter(list10, (x -> x % 2 == 1))); + } + + @Test + void testFilterFalse() { + compare(List.of(), filter(list10, (x -> false))); + } + + @Test + void testFilterTrue() { + compare(list10, filter(list10, (x -> true))); + } + + @Test + void testFilterEmpty() { + compare(List.of(), filter(List.of(), (x -> true))); + } + + @Test() + void testNoSuchElement() { + Iterable iterable = filter(list10, (x -> x % 2 == 0)); + Iterator iterator = iterable.iterator(); + while (iterator.hasNext()) { + iterator.next(); + } + Assertions.assertThrows(NoSuchElementException.class, () -> iterator.next()); + } + + @Test() + void mapTest() { + compare(listTen, map(list10, x -> x.toString())); + } + + @Test() + void mapEmtyTest() { + compare(List.of(), map(List.of(), x -> x.toString())); + } +} -- cgit v1.2.3-70-g09d2