aboutsummaryrefslogtreecommitdiffstats
path: root/subprojects/store
diff options
context:
space:
mode:
authorLibravatar Kristóf Marussy <kristof@marussy.com>2022-02-04 20:18:20 +0100
committerLibravatar GitHub <noreply@github.com>2022-02-04 20:18:20 +0100
commit42db1e8b4dcff3667c5f14e8dd464309c3c2f23e (patch)
treef5f5efe86fb352980cf144cceb68d1a1101b274f /subprojects/store
parentchore(web): fix Sonar issue (diff)
parentchore(frontend): bump frontend dependencies (diff)
downloadrefinery-42db1e8b4dcff3667c5f14e8dd464309c3c2f23e.tar.gz
refinery-42db1e8b4dcff3667c5f14e8dd464309c3c2f23e.tar.zst
refinery-42db1e8b4dcff3667c5f14e8dd464309c3c2f23e.zip
Merge pull request #18 from kris7t/releng-docs
Restructure project
Diffstat (limited to 'subprojects/store')
-rw-r--r--subprojects/store/build.gradle9
-rw-r--r--subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutBenchmark.java77
-rw-r--r--subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java57
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java69
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/Cursor.java14
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/CursorAsIterator.java57
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/DiffCursor.java6
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/MapAsIterable.java26
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java7
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java13
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java14
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java48
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java135
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java18
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java378
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java131
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java221
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java454
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java85
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java19
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java171
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/Model.java20
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/ModelCursor.java25
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/ModelDiffCursor.java26
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java16
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/ModelStoreImpl.java122
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/Tuple.java148
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java65
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java28
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java124
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/internal/SimilarRelationEquivalenceClass.java33
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/representation/AuxilaryData.java22
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/representation/DataRepresentation.java24
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/representation/Relation.java31
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/representation/TruthValue.java51
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/QueriableModel.java30
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/QueriableModelStore.java23
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/QueriableModelStoreImpl.java127
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/building/DNFAnd.java37
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/building/DNFAtom.java33
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/building/DNFPredicate.java72
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/building/EquivalenceAtom.java44
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/building/PredicateAtom.java66
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/building/RelationAtom.java49
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/building/Variable.java22
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/DNF2PQuery.java189
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/DummyBaseIndexer.java59
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/ModelUpdateListener.java103
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/PredicateResult.java24
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/QueriableModelImpl.java212
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/RawPatternMatcher.java57
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalEngineContext.java33
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalQueryMetaContext.java58
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalRuntimeContext.java178
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalScope.java43
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdate.java34
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdateBuffer.java46
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdateTranslator.java57
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/view/FilteredRelationView.java48
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/view/FunctionalRelationView.java50
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/view/KeyOnlyRelationView.java16
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/query/view/RelationView.java85
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/util/CollectionsUtil.java72
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java22
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java96
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java143
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java117
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java97
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java101
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java92
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java89
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java109
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java113
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java64
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java33
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java214
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/model/hashTests/HashEfficiencyTest.java161
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/model/tests/ModelTest.java148
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/query/test/QueryTest.java445
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/query/test/QueryTransactionTest.java58
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/util/CollectionsUtilTests.java78
81 files changed, 6791 insertions, 0 deletions
diff --git a/subprojects/store/build.gradle b/subprojects/store/build.gradle
new file mode 100644
index 00000000..8d091a81
--- /dev/null
+++ b/subprojects/store/build.gradle
@@ -0,0 +1,9 @@
1plugins {
2 id 'refinery-java-library'
3 id 'refinery-jmh'
4}
5
6dependencies {
7 implementation libs.ecore
8 implementation libs.viatra
9}
diff --git a/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutBenchmark.java b/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutBenchmark.java
new file mode 100644
index 00000000..cdf3d3c8
--- /dev/null
+++ b/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutBenchmark.java
@@ -0,0 +1,77 @@
1package tools.refinery.store.map.benchmarks;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.concurrent.TimeUnit;
6
7import org.openjdk.jmh.annotations.Benchmark;
8import org.openjdk.jmh.annotations.BenchmarkMode;
9import org.openjdk.jmh.annotations.Fork;
10import org.openjdk.jmh.annotations.Measurement;
11import org.openjdk.jmh.annotations.Mode;
12import org.openjdk.jmh.annotations.OutputTimeUnit;
13import org.openjdk.jmh.annotations.Warmup;
14import org.openjdk.jmh.infra.Blackhole;
15
16@Fork(1)
17@BenchmarkMode(Mode.AverageTime)
18@OutputTimeUnit(TimeUnit.MILLISECONDS)
19@Measurement(time = 1, timeUnit = TimeUnit.SECONDS)
20@Warmup(time = 1, timeUnit = TimeUnit.SECONDS)
21public class ImmutablePutBenchmark {
22 @Benchmark
23 public void immutablePutBenchmark(ImmutablePutExecutionPlan executionPlan, Blackhole blackhole) {
24 var sut = executionPlan.createSut();
25 for (int i = 0; i < executionPlan.nPut; i++) {
26 sut.put(executionPlan.nextKey(), executionPlan.nextValue());
27 }
28 blackhole.consume(sut);
29 }
30
31 @Benchmark
32 public void immutablePutAndCommitBenchmark(ImmutablePutExecutionPlan executionPlan, Blackhole blackhole) {
33 var sut = executionPlan.createSut();
34 for (int i = 0; i < executionPlan.nPut; i++) {
35 sut.put(executionPlan.nextKey(), executionPlan.nextValue());
36 if (i % 10 == 0) {
37 blackhole.consume(sut.commit());
38 }
39 }
40 blackhole.consume(sut);
41 }
42
43 @Benchmark
44 public void baselinePutBenchmark(ImmutablePutExecutionPlan executionPlan, Blackhole blackhole) {
45 var sut = new HashMap<Integer, String>();
46 for (int i = 0; i < executionPlan.nPut; i++) {
47 var key = executionPlan.nextKey();
48 var value = executionPlan.nextValue();
49 if (executionPlan.isDefault(value)) {
50 sut.remove(key);
51 } else {
52 sut.put(key, value);
53 }
54 }
55 blackhole.consume(sut);
56 }
57
58 @Benchmark
59 public void baselinePutAndCommitBenchmark(ImmutablePutExecutionPlan executionPlan, Blackhole blackhole) {
60 var sut = new HashMap<Integer, String>();
61 var store = new ArrayList<HashMap<Integer, String>>();
62 for (int i = 0; i < executionPlan.nPut; i++) {
63 var key = executionPlan.nextKey();
64 var value = executionPlan.nextValue();
65 if (executionPlan.isDefault(value)) {
66 sut.remove(key);
67 } else {
68 sut.put(key, value);
69 }
70 if (i % 10 == 0) {
71 store.add(new HashMap<>(sut));
72 }
73 }
74 blackhole.consume(sut);
75 blackhole.consume(store);
76 }
77}
diff --git a/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java b/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java
new file mode 100644
index 00000000..756d504e
--- /dev/null
+++ b/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java
@@ -0,0 +1,57 @@
1package tools.refinery.store.map.benchmarks;
2
3import java.util.Random;
4
5import tools.refinery.store.map.ContinousHashProvider;
6import tools.refinery.store.map.VersionedMapStore;
7import tools.refinery.store.map.VersionedMapStoreImpl;
8import tools.refinery.store.map.internal.VersionedMapImpl;
9import tools.refinery.store.map.tests.utils.MapTestEnvironment;
10
11import org.openjdk.jmh.annotations.Level;
12import org.openjdk.jmh.annotations.Param;
13import org.openjdk.jmh.annotations.Scope;
14import org.openjdk.jmh.annotations.Setup;
15import org.openjdk.jmh.annotations.State;
16
17@State(Scope.Benchmark)
18public class ImmutablePutExecutionPlan {
19
20 @Param({ "100", "10000" })
21 public int nPut;
22
23 @Param({ "32", "1000", "100000" })
24 public int nKeys;
25
26 @Param({ "2", "3" })
27 public int nValues;
28
29 private Random random;
30
31 private String[] values;
32
33 private ContinousHashProvider<Integer> hashProvider = MapTestEnvironment.prepareHashProvider(false);
34
35 @Setup(Level.Trial)
36 public void setUpTrial() {
37 random = new Random();
38 values = MapTestEnvironment.prepareValues(nValues);
39 }
40
41 public VersionedMapImpl<Integer, String> createSut() {
42 VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(hashProvider, values[0]);
43 return (VersionedMapImpl<Integer, String>) store.createMap();
44 }
45
46 public Integer nextKey() {
47 return random.nextInt(nKeys);
48 }
49
50 public boolean isDefault(String value) {
51 return value == values[0];
52 }
53
54 public String nextValue() {
55 return values[random.nextInt(nValues)];
56 }
57}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java b/subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java
new file mode 100644
index 00000000..75f1e2ab
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java
@@ -0,0 +1,69 @@
1package tools.refinery.store.map;
2
3import tools.refinery.store.map.internal.Node;
4
5/**
6 * A class representing an equivalence relation for a type {@code K} with a
7 * continuous hash function.
8 *
9 * @author Oszkar Semerath
10 *
11 * @param <K> Target java type.
12 */
13public interface ContinousHashProvider<K> {
14 public static final int EFFECTIVE_BITS = Node.EFFECTIVE_BITS;
15 public static final int EFFECTIVE_BIT_MASK = (1 << (EFFECTIVE_BITS)) - 1;
16
17 /**
18 * Maximal practical depth for differentiating keys. If two keys have the same
19 * hash code until that depth, the algorithm can stop.
20 */
21 public static final int MAX_PRACTICAL_DEPTH = 500;
22
23 /**
24 * Provides a hash code for a object {@code key} with a given {@code index}. It
25 * has the following contracts:
26 * <ul>
27 * <li>If {@link #equals}{@code (key1,key2)}, then
28 * {@code getHash(key1, index) == getHash(key2, index)} for all values of
29 * {@code index}.</li>
30 * <li>If {@code getHash(key1,index) == getHash(key2, index)} for all values of
31 * {@code index}, then {@link #equals}{@code (key1, key2)}</li>
32 * <li>In current implementation, we use only the least significant
33 * {@link #EFFECTIVE_BITS}
34 * </ul>
35 * Check {@link #equals} for further details.
36 *
37 * @param key The target data object.
38 * @param index The depth of the the hash code. Needs to be non-negative.
39 * @return A hash code.
40 */
41 public int getHash(K key, int index);
42
43 public default int getEffectiveHash(K key, int index) {
44 return getHash(key, index) & EFFECTIVE_BIT_MASK;
45 }
46
47 public default int compare(K key1, K key2) {
48 if (key1.equals(key2)) {
49 return 0;
50 } else {
51 for (int i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) {
52 int hash1 = getEffectiveHash(key1, i);
53 int hash2 = getEffectiveHash(key2, i);
54 for(int j = 0; j<Integer.SIZE/Node.BRANCHING_FACTOR_BITS; j++) {
55 final int factorMask = (1<<Node.BRANCHING_FACTOR_BITS)-1;
56 int hashFragment1 = (hash1>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
57 int hashFragment2 = (hash2>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
58 var result = Integer.compare(hashFragment1, hashFragment2);
59 if (result != 0) {
60 return result;
61 }
62 }
63 }
64 throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2
65 + ") have the same hashcode over the practical depth limitation ("
66 + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!");
67 }
68 }
69}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/Cursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/Cursor.java
new file mode 100644
index 00000000..9c465ddc
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/Cursor.java
@@ -0,0 +1,14 @@
1package tools.refinery.store.map;
2
3import java.util.List;
4
5public interface Cursor<K,V> {
6 public K getKey();
7 public V getValue();
8 public boolean isTerminated();
9 public boolean move();
10 public boolean isDirty();
11
12 @SuppressWarnings("squid:S1452")
13 public List<VersionedMap<?,?>> getDependingMaps();
14}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/CursorAsIterator.java b/subprojects/store/src/main/java/tools/refinery/store/map/CursorAsIterator.java
new file mode 100644
index 00000000..65ae6648
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/CursorAsIterator.java
@@ -0,0 +1,57 @@
1package tools.refinery.store.map;
2
3import java.util.Iterator;
4import java.util.NoSuchElementException;
5import java.util.function.BiFunction;
6import java.util.function.BiPredicate;
7
8public class CursorAsIterator<K,V,D> implements Iterator<D> {
9 private final Cursor<K, V> internal;
10 private final BiFunction<K, V, D> entryTransformation;
11 private final BiPredicate<K,V> filtering;
12
13 D lastValidElement;
14
15 public CursorAsIterator(Cursor<K, V> internal, BiFunction<K, V, D> entryTransformation, BiPredicate<K,V> filtering) {
16 this.internal = internal;
17 this.entryTransformation = entryTransformation;
18 this.filtering = filtering;
19
20 moveToNext();
21 }
22 public CursorAsIterator(Cursor<K, V> internal, BiFunction<K, V, D> entryTransformation) {
23 this.internal = internal;
24 this.entryTransformation = entryTransformation;
25 this.filtering = ((k,v)->true);
26
27 moveToNext();
28 }
29
30 private void moveToNext() {
31 internal.move();
32 while(!internal.isTerminated() && !filtering.test(internal.getKey(), internal.getValue())) {
33 internal.move();
34 }
35 if(!internal.isTerminated()) {
36 lastValidElement = entryTransformation.apply(internal.getKey(), internal.getValue());
37 }
38 }
39
40
41 @Override
42 public boolean hasNext() {
43 return !internal.isTerminated();
44 }
45 @Override
46 public D next() {
47 if(hasNext()) {
48 D last = lastValidElement;
49 moveToNext();
50 return last;
51 } else {
52 throw new NoSuchElementException();
53 }
54
55 }
56
57}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/DiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/DiffCursor.java
new file mode 100644
index 00000000..701f3ec8
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/DiffCursor.java
@@ -0,0 +1,6 @@
1package tools.refinery.store.map;
2
3public interface DiffCursor<K, V> extends Cursor<K,V> {
4 public V getFromValue();
5 public V getToValue();
6} \ No newline at end of file
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/MapAsIterable.java b/subprojects/store/src/main/java/tools/refinery/store/map/MapAsIterable.java
new file mode 100644
index 00000000..6b986732
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/MapAsIterable.java
@@ -0,0 +1,26 @@
1package tools.refinery.store.map;
2
3import java.util.Iterator;
4import java.util.function.BiFunction;
5import java.util.function.BiPredicate;
6
7public class MapAsIterable<K,V,D> implements Iterable<D> {
8 private final VersionedMap<K, V> internal;
9 private final BiFunction<K, V, D> entryTransformation;
10 private final BiPredicate<K,V> filtering;
11
12 public MapAsIterable(VersionedMap<K, V> internal, BiFunction<K, V, D> entryTransformation, BiPredicate<K,V> filtering) {
13 this.internal = internal;
14 this.entryTransformation = entryTransformation;
15 this.filtering = filtering;
16 }
17 public MapAsIterable(VersionedMap<K, V> internal, BiFunction<K, V, D> entryTransformation) {
18 this.internal = internal;
19 this.entryTransformation = entryTransformation;
20 this.filtering = ((k,v)->true);
21 }
22 @Override
23 public Iterator<D> iterator() {
24 return new CursorAsIterator<>(internal.getAll(), entryTransformation, filtering);
25 }
26}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java b/subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java
new file mode 100644
index 00000000..6a23e9d5
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java
@@ -0,0 +1,7 @@
1package tools.refinery.store.map;
2
3public interface Versioned {
4 public long commit();
5 //maybe revert()?
6 public void restore(long state);
7}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java
new file mode 100644
index 00000000..a8a64d08
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java
@@ -0,0 +1,13 @@
1package tools.refinery.store.map;
2
3public interface VersionedMap<K,V> extends Versioned{
4 public V get(K key);
5 public Cursor<K,V> getAll();
6
7 public V put(K key, V value);
8 public void putAll(Cursor<K,V> cursor);
9
10 public long getSize();
11
12 public DiffCursor<K,V> getDiffCursor(long state);
13}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java
new file mode 100644
index 00000000..a8d7fb1a
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java
@@ -0,0 +1,14 @@
1package tools.refinery.store.map;
2
3import java.util.Set;
4
5public interface VersionedMapStore<K, V> {
6
7 public VersionedMap<K, V> createMap();
8
9 public VersionedMap<K, V> createMap(long state);
10
11 public Set<Long> getStates();
12
13 public DiffCursor<K,V> getDiffCursor(long fromState, long toState);
14} \ No newline at end of file
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java
new file mode 100644
index 00000000..723e5ec4
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java
@@ -0,0 +1,48 @@
1package tools.refinery.store.map;
2
3public class VersionedMapStoreConfiguration {
4
5 public VersionedMapStoreConfiguration() {
6
7 }
8 public VersionedMapStoreConfiguration(boolean immutableWhenCommiting, boolean sharedNodeCacheInStore,
9 boolean sharedNodeCacheInStoreGroups) {
10 super();
11 this.immutableWhenCommiting = immutableWhenCommiting;
12 this.sharedNodeCacheInStore = sharedNodeCacheInStore;
13 this.sharedNodeCacheInStoreGroups = sharedNodeCacheInStoreGroups;
14 }
15
16 /**
17 * If true root is replaced with immutable node when committed. Frees up memory
18 * by releasing immutable nodes, but it may decrease performance by recreating
19 * immutable nodes upon changes (some evidence).
20 */
21 private boolean immutableWhenCommiting = true;
22 public boolean isImmutableWhenCommiting() {
23 return immutableWhenCommiting;
24 }
25
26 /**
27 * If true, all subnodes are cached within a {@link VersionedMapStore}. It
28 * decreases the memory requirements. It may increase performance by discovering
29 * existing immutable copy of a node (some evidence). Additional overhead may
30 * decrease performance (no example found). The option permits the efficient
31 * implementation of version deletion.
32 */
33 private boolean sharedNodeCacheInStore = true;
34 public boolean isSharedNodeCacheInStore() {
35 return sharedNodeCacheInStore;
36 }
37
38 /**
39 * If true, all subnodes are cached within a group of
40 * {@link VersionedMapStoreImpl#createSharedVersionedMapStores(int, ContinousHashProvider, Object, VersionedMapStoreConfiguration)}.
41 * If {@link VersionedMapStoreConfiguration#sharedNodeCacheInStore} is
42 * <code>false</code>, then it has currently no impact.
43 */
44 private boolean sharedNodeCacheInStoreGroups = true;
45 public boolean isSharedNodeCacheInStoreGroups() {
46 return sharedNodeCacheInStoreGroups;
47 }
48}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java
new file mode 100644
index 00000000..a626a5e8
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java
@@ -0,0 +1,135 @@
1package tools.refinery.store.map;
2
3import java.util.ArrayList;
4import java.util.Arrays;
5import java.util.Collections;
6import java.util.HashMap;
7import java.util.HashSet;
8import java.util.List;
9import java.util.Map;
10import java.util.Set;
11
12import tools.refinery.store.map.internal.ImmutableNode;
13import tools.refinery.store.map.internal.MapDiffCursor;
14import tools.refinery.store.map.internal.Node;
15import tools.refinery.store.map.internal.VersionedMapImpl;
16
17public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> {
18 // Configuration
19 private final boolean immutableWhenCommiting;
20
21 // Static data
22 protected final ContinousHashProvider<K> hashProvider;
23 protected final V defaultValue;
24
25 // Dynamic data
26 protected final Map<Long, ImmutableNode<K, V>> states = new HashMap<>();
27 protected final Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
28 protected long nextID = 0;
29
30 public VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue,
31 VersionedMapStoreConfiguration config) {
32 this.immutableWhenCommiting = config.isImmutableWhenCommiting();
33 this.hashProvider = hashProvider;
34 this.defaultValue = defaultValue;
35 if (config.isSharedNodeCacheInStore()) {
36 nodeCache = new HashMap<>();
37 } else {
38 nodeCache = null;
39 }
40 }
41
42 private VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue,
43 Map<Node<K, V>, ImmutableNode<K, V>> nodeCache, VersionedMapStoreConfiguration config) {
44 this.immutableWhenCommiting = config.isImmutableWhenCommiting();
45 this.hashProvider = hashProvider;
46 this.defaultValue = defaultValue;
47 this.nodeCache = nodeCache;
48 }
49
50 public VersionedMapStoreImpl(ContinousHashProvider<K> hashProvider, V defaultValue) {
51 this(hashProvider, defaultValue, new VersionedMapStoreConfiguration());
52 }
53
54 public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
55 ContinousHashProvider<K> hashProvider, V defaultValue,
56 VersionedMapStoreConfiguration config) {
57 List<VersionedMapStore<K, V>> result = new ArrayList<>(amount);
58 if (config.isSharedNodeCacheInStoreGroups()) {
59 Map<Node<K, V>, ImmutableNode<K, V>> nodeCache;
60 if (config.isSharedNodeCacheInStore()) {
61 nodeCache = new HashMap<>();
62 } else {
63 nodeCache = null;
64 }
65 for (int i = 0; i < amount; i++) {
66 result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, nodeCache, config));
67 }
68 } else {
69 for (int i = 0; i < amount; i++) {
70 result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, config));
71 }
72 }
73 return result;
74 }
75
76 public static <K, V> List<VersionedMapStore<K, V>> createSharedVersionedMapStores(int amount,
77 ContinousHashProvider<K> hashProvider, V defaultValue) {
78 return createSharedVersionedMapStores(amount, hashProvider, defaultValue, new VersionedMapStoreConfiguration());
79 }
80
81 @Override
82 public synchronized Set<Long> getStates() {
83 return new HashSet<>(states.keySet());
84 }
85
86 @Override
87 public VersionedMap<K, V> createMap() {
88 return new VersionedMapImpl<>(this, hashProvider, defaultValue);
89 }
90
91 @Override
92 public VersionedMap<K, V> createMap(long state) {
93 ImmutableNode<K, V> data = revert(state);
94 return new VersionedMapImpl<>(this, hashProvider, defaultValue, data);
95 }
96
97
98 public synchronized ImmutableNode<K, V> revert(long state) {
99 if (states.containsKey(state)) {
100 return states.get(state);
101 } else {
102 ArrayList<Long> existingKeys = new ArrayList<>(states.keySet());
103 Collections.sort(existingKeys);
104 throw new IllegalArgumentException("Store does not contain state " + state + "! Avaliable states: "
105 + Arrays.toString(existingKeys.toArray()));
106 }
107 }
108
109 public synchronized long commit(Node<K, V> data, VersionedMapImpl<K, V> mapToUpdateRoot) {
110 ImmutableNode<K, V> immutable;
111 if (data != null) {
112 immutable = data.toImmutable(this.nodeCache);
113 } else {
114 immutable = null;
115 }
116
117 if (nextID == Long.MAX_VALUE)
118 throw new IllegalStateException("Map store run out of Id-s");
119 long id = nextID++;
120 this.states.put(id, immutable);
121 if (this.immutableWhenCommiting) {
122 mapToUpdateRoot.setRoot(immutable);
123 }
124 return id;
125 }
126
127 @Override
128 public DiffCursor<K, V> getDiffCursor(long fromState, long toState) {
129 VersionedMap<K, V> map1 = createMap(fromState);
130 VersionedMap<K, V> map2 = createMap(toState);
131 Cursor<K, V> cursor1 = map1.getAll();
132 Cursor<K, V> cursor2 = map2.getAll();
133 return new MapDiffCursor<>(this.hashProvider, this.defaultValue, cursor1, cursor2);
134 }
135}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java
new file mode 100644
index 00000000..5402ed4a
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java
@@ -0,0 +1,18 @@
1package tools.refinery.store.map.internal;
2
3enum HashClash {
4 /**
5 * Not stuck.
6 */
7 NONE,
8
9 /**
10 * Clashed, next we should return the key of cursor 1.
11 */
12 STUCK_CURSOR_1,
13
14 /**
15 * Clashed, next we should return the key of cursor 2.
16 */
17 STUCK_CURSOR_2
18}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java
new file mode 100644
index 00000000..f68734ab
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java
@@ -0,0 +1,378 @@
1package tools.refinery.store.map.internal;
2
3import java.util.Arrays;
4import java.util.Map;
5
6import tools.refinery.store.map.ContinousHashProvider;
7
8public class ImmutableNode<K, V> extends Node<K, V> {
9 /**
10 * Bitmap defining the stored key and values.
11 */
12 final int dataMap;
13 /**
14 * Bitmap defining the positions of further nodes.
15 */
16 final int nodeMap;
17 /**
18 * Stores Keys, Values, and subnodes. Structure: (K,V)*,NODE; NODES are stored
19 * backwards.
20 */
21 final Object[] content;
22
23 /**
24 * Hash code derived from immutable hash code
25 */
26 final int precalculatedHash;
27
28 private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) {
29 super();
30 this.dataMap = dataMap;
31 this.nodeMap = nodeMap;
32 this.content = content;
33 this.precalculatedHash = precalculatedHash;
34 }
35
36 /**
37 * Constructor that copies a mutable node to an immutable.
38 *
39 * @param node A mutable node.
40 * @param cache A cache of existing immutable nodes. It can be used to search
41 * and place reference immutable nodes. It can be null, if no cache
42 * available.
43 * @return an immutable version of the input node.
44 */
45 static <K, V> ImmutableNode<K, V> constructImmutable(MutableNode<K, V> node,
46 Map<Node<K, V>, ImmutableNode<K, V>> cache) {
47 // 1. try to return from cache
48 if (cache != null) {
49 ImmutableNode<K, V> cachedResult = cache.get(node);
50 if (cachedResult != null) {
51 // 1.1 Already cached, return from cache.
52 return cachedResult;
53 }
54 }
55
56 // 2. otherwise construct a new ImmutableNode
57 int size = 0;
58 for (int i = 0; i < node.content.length; i++) {
59 if (node.content[i] != null) {
60 size++;
61 }
62 }
63
64 int datas = 0;
65 int nodes = 0;
66 int resultDataMap = 0;
67 int resultNodeMap = 0;
68 final Object[] resultContent = new Object[size];
69 int bitposition = 1;
70 for (int i = 0; i < FACTOR; i++) {
71 Object key = node.content[i * 2];
72 if (key != null) {
73 resultDataMap |= bitposition;
74 resultContent[datas * 2] = key;
75 resultContent[datas * 2 + 1] = node.content[i * 2 + 1];
76 datas++;
77 } else {
78 @SuppressWarnings("unchecked")
79 var subnode = (Node<K, V>) node.content[i * 2 + 1];
80 if (subnode != null) {
81 ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache);
82 resultNodeMap |= bitposition;
83 resultContent[size - 1 - nodes] = immutableSubnode;
84 nodes++;
85 }
86 }
87 bitposition <<= 1;
88 }
89 final int resultHash = node.hashCode();
90 var newImmutable = new ImmutableNode<K, V>(resultDataMap, resultNodeMap, resultContent, resultHash);
91
92 // 3. save new immutable.
93 if (cache != null) {
94 cache.put(newImmutable, newImmutable);
95 }
96 return newImmutable;
97 }
98
99 private int index(int bitmap, int bitpos) {
100 return Integer.bitCount(bitmap & (bitpos - 1));
101 }
102
103 @Override
104 public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
105 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
106 int bitposition = 1 << selectedHashFragment;
107 // If the key is stored as a data
108 if ((dataMap & bitposition) != 0) {
109 int keyIndex = 2 * index(dataMap, bitposition);
110 @SuppressWarnings("unchecked")
111 K keyCandidate = (K) content[keyIndex];
112 if (keyCandidate.equals(key)) {
113 @SuppressWarnings("unchecked")
114 V value = (V) content[keyIndex + 1];
115 return value;
116 } else {
117 return defaultValue;
118 }
119 }
120 // the key is stored as a node
121 else if ((nodeMap & bitposition) != 0) {
122 int keyIndex = content.length - 1 - index(nodeMap, bitposition);
123 @SuppressWarnings("unchecked")
124 var subNode = (ImmutableNode<K, V>) content[keyIndex];
125 int newDepth = depth + 1;
126 int newHash = newHash(hashProvider, key, hash, newDepth);
127 return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth);
128 }
129 // the key is not stored at all
130 else {
131 return defaultValue;
132 }
133 }
134
135 @Override
136 public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider,
137 V defaultValue, int hash, int depth) {
138 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
139 int bitposition = 1 << selectedHashFragment;
140 if ((dataMap & bitposition) != 0) {
141 int keyIndex = 2 * index(dataMap, bitposition);
142 @SuppressWarnings("unchecked")
143 K keyCandidate = (K) content[keyIndex];
144 if (keyCandidate.equals(key)) {
145 if (value == defaultValue) {
146 // delete
147 MutableNode<K, V> mutable = this.toMutable();
148 return mutable.removeEntry(selectedHashFragment, oldValue);
149 } else if (value == content[keyIndex + 1]) {
150 // dont change
151 oldValue.setOldValue(value);
152 return this;
153 } else {
154 // update existing value
155 MutableNode<K, V> mutable = this.toMutable();
156 return mutable.updateValue(value, oldValue, selectedHashFragment);
157 }
158 } else {
159 if (value == defaultValue) {
160 // dont change
161 oldValue.setOldValue(defaultValue);
162 return this;
163 } else {
164 // add new key + value
165 MutableNode<K, V> mutable = this.toMutable();
166 return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
167 }
168 }
169 } else if ((nodeMap & bitposition) != 0) {
170 int keyIndex = content.length - 1 - index(nodeMap, bitposition);
171 @SuppressWarnings("unchecked")
172 var subNode = (ImmutableNode<K, V>) content[keyIndex];
173 int newDepth = depth + 1;
174 int newHash = newHash(hashProvider, key, hash, newDepth);
175 var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth);
176
177 if (subNode == newsubNode) {
178 // nothing changed
179 return this;
180 } else {
181 MutableNode<K, V> mutable = toMutable();
182 return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue));
183 }
184 } else {
185 // add new key + value
186 MutableNode<K, V> mutable = this.toMutable();
187 return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
188 }
189 }
190
191 @Override
192 public long getSize() {
193 int result = Integer.bitCount(this.dataMap);
194 for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) {
195 @SuppressWarnings("unchecked")
196 var subnode = (ImmutableNode<K, V>) this.content[this.content.length - 1 - subnodeIndex];
197 result += subnode.getSize();
198 }
199 return result;
200 }
201
202 @Override
203 protected MutableNode<K, V> toMutable() {
204 return new MutableNode<>(this);
205 }
206
207 @Override
208 public ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache) {
209 return this;
210 }
211
212 @Override
213 protected MutableNode<K, V> isMutable() {
214 return null;
215 }
216
217 @SuppressWarnings("unchecked")
218 @Override
219 boolean moveToNext(MapCursor<K, V> cursor) {
220 // 1. try to move to data
221 int datas = Integer.bitCount(this.dataMap);
222 if (cursor.dataIndex != MapCursor.INDEX_FINISH) {
223 int newDataIndex = cursor.dataIndex + 1;
224 if (newDataIndex < datas) {
225 cursor.dataIndex = newDataIndex;
226 cursor.key = (K) this.content[newDataIndex * 2];
227 cursor.value = (V) this.content[newDataIndex * 2 + 1];
228 return true;
229 } else {
230 cursor.dataIndex = MapCursor.INDEX_FINISH;
231 }
232 }
233
234 // 2. look inside the subnodes
235 int nodes = Integer.bitCount(this.nodeMap);
236 int newNodeIndex = cursor.nodeIndexStack.peek() + 1;
237 if (newNodeIndex < nodes) {
238 // 2.1 found next subnode, move down to the subnode
239 Node<K, V> subnode = (Node<K, V>) this.content[this.content.length - 1 - newNodeIndex];
240 cursor.dataIndex = MapCursor.INDEX_START;
241 cursor.nodeIndexStack.pop();
242 cursor.nodeIndexStack.push(newNodeIndex);
243 cursor.nodeIndexStack.push(MapCursor.INDEX_START);
244 cursor.nodeStack.push(subnode);
245 return subnode.moveToNext(cursor);
246 } else {
247 // 3. no subnode found, move up
248 cursor.nodeStack.pop();
249 cursor.nodeIndexStack.pop();
250 if (!cursor.nodeStack.isEmpty()) {
251 Node<K, V> supernode = cursor.nodeStack.peek();
252 return supernode.moveToNext(cursor);
253 } else {
254 cursor.key = null;
255 cursor.value = null;
256 return false;
257 }
258 }
259 }
260
261 @Override
262 public void prettyPrint(StringBuilder builder, int depth, int code) {
263 for (int i = 0; i < depth; i++) {
264 builder.append("\t");
265 }
266 if (code >= 0) {
267 builder.append(code);
268 builder.append(":");
269 }
270 builder.append("Immutable(");
271 boolean hadContent = false;
272 int dataMask = 1;
273 for (int i = 0; i < FACTOR; i++) {
274 if ((dataMask & dataMap) != 0) {
275 if (hadContent) {
276 builder.append(",");
277 }
278 builder.append(i);
279 builder.append(":[");
280 builder.append(content[2 * index(dataMap, dataMask)].toString());
281 builder.append("]->[");
282 builder.append(content[2 * index(dataMap, dataMask) + 1].toString());
283 builder.append("]");
284 hadContent = true;
285 }
286 dataMask <<= 1;
287 }
288 builder.append(")");
289 int nodeMask = 1;
290 for (int i = 0; i < FACTOR; i++) {
291 if ((nodeMask & nodeMap) != 0) {
292 @SuppressWarnings("unchecked")
293 Node<K, V> subNode = (Node<K, V>) content[content.length - 1 - index(nodeMap, nodeMask)];
294 builder.append("\n");
295 subNode.prettyPrint(builder, depth + 1, i);
296 }
297 nodeMask <<= 1;
298 }
299 }
300
301 @Override
302 public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
303 if (depth > 0) {
304 boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0;
305 if (orphaned) {
306 throw new IllegalStateException("Orphaned node! " + dataMap + ": " + content[0]);
307 }
308 }
309 // check the place of data
310
311 // check subnodes
312 for (int i = 0; i < Integer.bitCount(nodeMap); i++) {
313 @SuppressWarnings("unchecked")
314 var subnode = (Node<K, V>) this.content[this.content.length - 1 - i];
315 if (!(subnode instanceof ImmutableNode<?, ?>)) {
316 throw new IllegalStateException("Immutable node contains mutable subnodes!");
317 } else {
318 subnode.checkIntegrity(hashProvider, defaultValue, depth + 1);
319 }
320 }
321 }
322
323 @Override
324 public int hashCode() {
325 return this.precalculatedHash;
326 }
327
328 @Override
329 public boolean equals(Object obj) {
330 if (this == obj)
331 return true;
332 if (obj == null)
333 return false;
334 if (obj instanceof ImmutableNode<?, ?> other) {
335 return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap
336 && Arrays.deepEquals(content, other.content);
337 } else if (obj instanceof MutableNode<?, ?> mutableObj) {
338 return ImmutableNode.compareImmutableMutable(this, mutableObj);
339 } else {
340 return false;
341 }
342 }
343
344 public static boolean compareImmutableMutable(ImmutableNode<?, ?> immutable, MutableNode<?, ?> mutable) {
345 int datas = 0;
346 int nodes = 0;
347 final int immutableLength = immutable.content.length;
348 for (int i = 0; i < FACTOR; i++) {
349 Object key = mutable.content[i * 2];
350 // For each key candidate
351 if (key != null) {
352 // Check whether a new Key-Value pair can fit into the immutable container
353 if (datas * 2 + nodes + 2 <= immutableLength) {
354 if (!immutable.content[datas * 2].equals(key)
355 || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) {
356 return false;
357 }
358 } else
359 return false;
360 datas++;
361 } else {
362 var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1];
363 if (mutableSubnode != null) {
364 if (datas * 2 + nodes + 1 <= immutableLength) {
365 Object immutableSubnode = immutable.content[immutableLength - 1 - nodes];
366 if (!mutableSubnode.equals(immutableSubnode)) {
367 return false;
368 }
369 nodes++;
370 } else {
371 return false;
372 }
373 }
374 }
375 }
376 return true;
377 }
378}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java
new file mode 100644
index 00000000..b90f5b71
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java
@@ -0,0 +1,131 @@
1package tools.refinery.store.map.internal;
2
3import java.util.ArrayDeque;
4import java.util.ConcurrentModificationException;
5import java.util.Iterator;
6import java.util.List;
7
8import tools.refinery.store.map.Cursor;
9import tools.refinery.store.map.VersionedMap;
10
11public class MapCursor<K,V> implements Cursor<K,V> {
12 // Constants
13 static final int INDEX_START = -1;
14 static final int INDEX_FINISH = -2;
15
16 // Tree stack
17 ArrayDeque<Node<K,V>> nodeStack;
18 ArrayDeque<Integer> nodeIndexStack;
19 int dataIndex;
20
21 // Values
22 K key;
23 V value;
24
25 // Hash code for checking concurrent modifications
26 final VersionedMap<K,V> map;
27 final int creationHash;
28
29 public MapCursor(Node<K, V> root, VersionedMap<K,V> map) {
30 // Initializing tree stack
31 super();
32 this.nodeStack = new ArrayDeque<>();
33 this.nodeIndexStack = new ArrayDeque<>();
34 if(root != null) {
35 this.nodeStack.add(root);
36 this.nodeIndexStack.push(INDEX_START);
37 }
38
39 this.dataIndex = INDEX_START;
40
41 // Initializing cache
42 this.key = null;
43 this.value = null;
44
45 // Initializing state
46 this.map=map;
47 this.creationHash = map.hashCode();
48 }
49
50 public K getKey() {
51 return key;
52 }
53
54 public V getValue() {
55 return value;
56 }
57
58 public boolean isTerminated() {
59 return this.nodeStack.isEmpty();
60 }
61
62 public boolean move() {
63 if(isDirty()) {
64 throw new ConcurrentModificationException();
65 }
66 if(!isTerminated()) {
67 boolean result = this.nodeStack.peek().moveToNext(this);
68 if(this.nodeIndexStack.size() != this.nodeStack.size()) {
69 throw new IllegalArgumentException("Node stack is corrupted by illegal moves!");
70 }
71 return result;
72 }
73 return false;
74 }
75 public boolean skipCurrentNode() {
76 nodeStack.pop();
77 nodeIndexStack.pop();
78 dataIndex = INDEX_FINISH;
79 return move();
80 }
81 @Override
82 public boolean isDirty() {
83 return this.map.hashCode() != this.creationHash;
84 }
85 @Override
86 public List<VersionedMap<?, ?>> getDependingMaps() {
87 return List.of(this.map);
88 }
89
90 public static <K,V> boolean sameSubnode(MapCursor<K,V> cursor1, MapCursor<K,V> cursor2) {
91 Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek();
92 Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek();
93 if(nodeOfCursor1 != null && nodeOfCursor2 != null) {
94 return nodeOfCursor1.equals(nodeOfCursor2);
95 } else {
96 return false;
97 }
98 }
99
100 /**
101 *
102 * @param <K>
103 * @param <V>
104 * @param cursor1
105 * @param cursor2
106 * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position.
107 */
108 public static <K,V> int compare(MapCursor<K,V> cursor1, MapCursor<K,V> cursor2) {
109 // two cursors are equally deep
110 Iterator<Integer> stack1 = cursor1.nodeIndexStack.descendingIterator();
111 Iterator<Integer> stack2 = cursor2.nodeIndexStack.descendingIterator();
112 if(stack1.hasNext()) {
113 if(!stack2.hasNext()) {
114 // stack 2 has no more element, thus stack 1 is deeper
115 return 1;
116 }
117 int val1 = stack1.next();
118 int val2 = stack2.next();
119 if(val1 < val2) {
120 return -1;
121 } else if(val2 < val1) {
122 return 1;
123 }
124 }
125 if(stack2.hasNext()) {
126 // stack 2 has more element, thus stack 2 is deeper
127 return 1;
128 }
129 return Integer.compare(cursor1.dataIndex, cursor2.dataIndex);
130 }
131}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java
new file mode 100644
index 00000000..42333635
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java
@@ -0,0 +1,221 @@
1package tools.refinery.store.map.internal;
2
3import java.util.List;
4import java.util.stream.Stream;
5
6import tools.refinery.store.map.ContinousHashProvider;
7import tools.refinery.store.map.Cursor;
8import tools.refinery.store.map.DiffCursor;
9import tools.refinery.store.map.VersionedMap;
10
11/**
12 * A cursor representing the difference between two states of a map.
13 *
14 * @author Oszkar Semerath
15 *
16 */
17public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> {
18 /**
19 * Default value representing missing elements.
20 */
21 private V defaultValue;
22 private MapCursor<K, V> cursor1;
23 private MapCursor<K, V> cursor2;
24 private ContinousHashProvider<? super K> hashProvider;
25
26 // Values
27 private K key;
28 private V fromValue;
29 private V toValue;
30
31 // State
32 /**
33 * Positive number if cursor 1 is behind, negative number if cursor 2 is behind,
34 * and 0 if they are at the same position.
35 */
36 private int cursorRelation;
37 private HashClash hashClash = HashClash.NONE;
38
39 public MapDiffCursor(ContinousHashProvider<? super K> hashProvider, V defaultValue, Cursor<K, V> cursor1,
40 Cursor<K, V> cursor2) {
41 super();
42 this.hashProvider = hashProvider;
43 this.defaultValue = defaultValue;
44 this.cursor1 = (MapCursor<K, V>) cursor1;
45 this.cursor2 = (MapCursor<K, V>) cursor2;
46 }
47
48 @Override
49 public K getKey() {
50 return key;
51 }
52
53 @Override
54 public V getFromValue() {
55 return fromValue;
56 }
57
58 @Override
59 public V getToValue() {
60 return toValue;
61 }
62
63 @Override
64 public V getValue() {
65 return getToValue();
66 }
67
68 public boolean isTerminated() {
69 return cursor1.isTerminated() && cursor2.isTerminated();
70 }
71
72 @Override
73 public boolean isDirty() {
74 return this.cursor1.isDirty() || this.cursor2.isDirty();
75 }
76
77 @Override
78 public List<VersionedMap<?, ?>> getDependingMaps() {
79 return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).toList();
80 }
81
82 protected void updateState() {
83 if (!isTerminated()) {
84 this.cursorRelation = MapCursor.compare(cursor1, cursor2);
85 if (cursorRelation > 0 || cursor2.isTerminated()) {
86 this.key = cursor1.getKey();
87 this.fromValue = cursor1.getValue();
88 this.toValue = defaultValue;
89 } else if (cursorRelation < 0 || cursor1.isTerminated()) {
90 this.key = cursor2.getKey();
91 this.fromValue = defaultValue;
92 this.toValue = cursor1.getValue();
93 } else {
94 // cursor1 = cursor2
95 if (cursor1.getKey().equals(cursor2.getKey())) {
96 this.key = cursor1.getKey();
97 this.fromValue = cursor1.getValue();
98 this.toValue = defaultValue;
99 } else {
100 resolveHashClashWithFirstEntry();
101 }
102 }
103 }
104 }
105
106 protected void resolveHashClashWithFirstEntry() {
107 int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key);
108 if (compareResult < 0) {
109 this.hashClash = HashClash.STUCK_CURSOR_2;
110 this.cursorRelation = 0;
111 this.key = cursor1.key;
112 this.fromValue = cursor1.value;
113 this.toValue = defaultValue;
114 } else if (compareResult > 0) {
115 this.hashClash = HashClash.STUCK_CURSOR_1;
116 this.cursorRelation = 0;
117 this.key = cursor2.key;
118 this.fromValue = defaultValue;
119 this.toValue = cursor2.value;
120 } else {
121 throw new IllegalArgumentException("Inconsistent compare result for diffcursor");
122 }
123 }
124
125 protected boolean isInHashClash() {
126 return this.hashClash != HashClash.NONE;
127 }
128
129 protected void resolveHashClashWithSecondEntry() {
130 switch (this.hashClash) {
131 case STUCK_CURSOR_1:
132 this.hashClash = HashClash.NONE;
133 this.cursorRelation = 0;
134 this.key = cursor1.key;
135 this.fromValue = cursor1.value;
136 this.toValue = defaultValue;
137 break;
138 case STUCK_CURSOR_2:
139 this.hashClash = HashClash.NONE;
140 this.cursorRelation = 0;
141 this.key = cursor2.key;
142 this.fromValue = defaultValue;
143 this.toValue = cursor2.value;
144 break;
145 default:
146 throw new IllegalArgumentException("Inconsistent compare result for diffcursor");
147 }
148 }
149
150 protected boolean sameValues() {
151 if (this.fromValue == null) {
152 return this.toValue == null;
153 } else {
154 return this.fromValue.equals(this.toValue);
155 }
156 }
157
158 protected boolean moveOne() {
159 if (isTerminated()) {
160 return false;
161 }
162 if (this.cursorRelation > 0 || cursor2.isTerminated()) {
163 return cursor1.move();
164 } else if (this.cursorRelation < 0 || cursor1.isTerminated()) {
165 return cursor2.move();
166 } else {
167 boolean moved1 = cursor1.move();
168 boolean moved2 = cursor2.move();
169 return moved1 && moved2;
170 }
171 }
172
173 private boolean skipNode() {
174 if (isTerminated()) {
175 throw new IllegalStateException("DiffCursor tries to skip when terminated!");
176 }
177 boolean update1 = cursor1.skipCurrentNode();
178 boolean update2 = cursor2.skipCurrentNode();
179 updateState();
180 return update1 && update2;
181 }
182
183 protected boolean moveToConsistentState() {
184 if (!isTerminated()) {
185 boolean changed;
186 boolean lastResult = true;
187 do {
188 changed = false;
189 if (MapCursor.sameSubnode(cursor1, cursor2)) {
190 lastResult = skipNode();
191 changed = true;
192 }
193 if (sameValues()) {
194 lastResult = moveOne();
195 changed = true;
196 }
197 updateState();
198 } while (changed && !isTerminated());
199 return lastResult;
200 } else {
201 return false;
202 }
203 }
204
205 public boolean move() {
206 if (!isTerminated()) {
207 if (isInHashClash()) {
208 this.resolveHashClashWithSecondEntry();
209 return true;
210 } else {
211 if (moveOne()) {
212 return moveToConsistentState();
213 } else {
214 return false;
215 }
216 }
217
218 } else
219 return false;
220 }
221}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java
new file mode 100644
index 00000000..54853010
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java
@@ -0,0 +1,454 @@
1package tools.refinery.store.map.internal;
2
3import java.util.Arrays;
4import java.util.Map;
5
6import tools.refinery.store.map.ContinousHashProvider;
7
8public class MutableNode<K, V> extends Node<K, V> {
9 int cachedHash;
10 protected Object[] content;
11
12 protected MutableNode() {
13 this.content = new Object[2 * FACTOR];
14 updateHash();
15 }
16
17 public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider,
18 V defaultValue) {
19 if (value == defaultValue) {
20 return null;
21 } else {
22 int hash = hashProvider.getHash(key, 0);
23 int fragment = hashFragment(hash, 0);
24 MutableNode<K, V> res = new MutableNode<>();
25 res.content[2 * fragment] = key;
26 res.content[2 * fragment + 1] = value;
27 res.updateHash();
28 return res;
29 }
30 }
31
32 /**
33 * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode}
34 *
35 * @param node
36 */
37 protected MutableNode(ImmutableNode<K, V> node) {
38 this.content = new Object[2 * FACTOR];
39 int dataUsed = 0;
40 int nodeUsed = 0;
41 for (int i = 0; i < FACTOR; i++) {
42 int bitposition = 1 << i;
43 if ((node.dataMap & bitposition) != 0) {
44 content[2 * i] = node.content[dataUsed * 2];
45 content[2 * i + 1] = node.content[dataUsed * 2 + 1];
46 dataUsed++;
47 } else if ((node.nodeMap & bitposition) != 0) {
48 content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed];
49 nodeUsed++;
50 }
51 }
52 this.cachedHash = node.hashCode();
53 }
54
55 @Override
56 public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
57 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
58 @SuppressWarnings("unchecked")
59 K keyCandidate = (K) this.content[2 * selectedHashFragment];
60 if (keyCandidate != null) {
61 if (keyCandidate.equals(key)) {
62 @SuppressWarnings("unchecked")
63 V value = (V) this.content[2 * selectedHashFragment + 1];
64 return value;
65 } else {
66 return defaultValue;
67 }
68 } else {
69 @SuppressWarnings("unchecked")
70 var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
71 if (nodeCandidate != null) {
72 int newDepth = depth + 1;
73 int newHash = newHash(hashProvider, key, hash, newDepth);
74 return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth);
75 } else {
76 return defaultValue;
77 }
78 }
79 }
80
81 @Override
82 public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValueBox, ContinousHashProvider<? super K> hashProvider,
83 V defaultValue, int hash, int depth) {
84 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
85 @SuppressWarnings("unchecked")
86 K keyCandidate = (K) content[2 * selectedHashFragment];
87 if (keyCandidate != null) {
88 // If has key
89 if (keyCandidate.equals(key)) {
90 // The key is equals to an existing key -> update entry
91 if (value == defaultValue) {
92 return removeEntry(selectedHashFragment, oldValueBox);
93 } else {
94 return updateValue(value, oldValueBox, selectedHashFragment);
95 }
96 } else {
97 // The key is not equivalent to an existing key on the same hash bin
98 // -> split entry if it is necessary
99 if (value == defaultValue) {
100 // Value is default -> do not need to add new node
101 oldValueBox.setOldValue(defaultValue);
102 return this;
103 } else {
104 // Value is not default -> Split entry data to a new node
105 oldValueBox.setOldValue(defaultValue);
106 return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment);
107 }
108 }
109 } else {
110 // If it does not have key, check for value
111 @SuppressWarnings("unchecked")
112 var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
113 if (nodeCandidate != null) {
114 // If it has value, it is a subnode -> upate that
115 var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue,
116 newHash(hashProvider, key, hash, depth + 1), depth + 1);
117 return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue));
118 } else {
119 // If it does not have value, put it in the empty place
120 if (value == defaultValue) {
121 // dont need to add new key-value pair
122 oldValueBox.setOldValue(defaultValue);
123 return this;
124 } else {
125 return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue);
126 }
127
128 }
129 }
130 }
131
132 private Node<K, V> addEntry(K key, V value, OldValueBox<V> oldValueBox, int selectedHashFragment, V defaultValue) {
133 content[2 * selectedHashFragment] = key;
134 oldValueBox.setOldValue(defaultValue);
135 content[2 * selectedHashFragment + 1] = value;
136 updateHash();
137 return this;
138 }
139
140 /**
141 * Updates an entry in a selected hash-fragment to a non-default value.
142 *
143 * @param value
144 * @param selectedHashFragment
145 * @return
146 */
147 @SuppressWarnings("unchecked")
148 Node<K, V> updateValue(V value, OldValueBox<V> oldValue, int selectedHashFragment) {
149 oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
150 content[2 * selectedHashFragment + 1] = value;
151 updateHash();
152 return this;
153 }
154
155 /**
156 *
157 * @param selectedHashFragment
158 * @param newNode
159 * @return
160 */
161 Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) {
162 if (deletionHappened) {
163 if (newNode == null) {
164 // Check whether this node become empty
165 content[2 * selectedHashFragment + 1] = null; // i.e. the new node
166 if (hasContent()) {
167 updateHash();
168 return this;
169 } else {
170 return null;
171 }
172 } else {
173 // check whether newNode is orphan
174 MutableNode<K, V> immutableNewNode = newNode.isMutable();
175 if (immutableNewNode != null) {
176 int orphaned = immutableNewNode.isOrphaned();
177 if (orphaned >= 0) {
178 // orphan subnode data is replaced with data
179 content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2];
180 content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1];
181 updateHash();
182 return this;
183 }
184 }
185 }
186 }
187 // normal behaviour
188 content[2 * selectedHashFragment + 1] = newNode;
189 updateHash();
190 return this;
191
192 }
193
194 private boolean hasContent() {
195 for (Object element : this.content) {
196 if (element != null)
197 return true;
198 }
199 return false;
200 }
201
202 @Override
203 protected MutableNode<K, V> isMutable() {
204 return this;
205 }
206
207 protected int isOrphaned() {
208 int dataFound = -2;
209 for (int i = 0; i < FACTOR; i++) {
210 if (content[i * 2] != null) {
211 if (dataFound >= 0) {
212 return -1;
213 } else {
214 dataFound = i;
215 }
216 } else if (content[i * 2 + 1] != null) {
217 return -3;
218 }
219 }
220 return dataFound;
221 }
222
223 @SuppressWarnings("unchecked")
224 private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue,
225 K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) {
226 V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1];
227
228 MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue,
229 hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1);
230
231 content[2 * selectedHashFragmentOfCurrentDepth] = null;
232 content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode;
233 updateHash();
234 return this;
235 }
236
237 // Pass everything as parameters for performance.
238 @SuppressWarnings("squid:S107")
239 private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1,
240 int oldHash1, K key2, V value2, int oldHash2, int newdepth) {
241 int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth);
242 int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth);
243 int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth));
244 int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth));
245
246 MutableNode<K, V> subNode = new MutableNode<>();
247 if (newFragment1 != newFragment2) {
248 subNode.content[newFragment1 * 2] = key1;
249 subNode.content[newFragment1 * 2 + 1] = value1;
250
251 subNode.content[newFragment2 * 2] = key2;
252 subNode.content[newFragment2 * 2 + 1] = value2;
253 } else {
254 MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2,
255 newHash2, newdepth + 1);
256 subNode.content[newFragment1 * 2 + 1] = subSubNode;
257 }
258 subNode.updateHash();
259 return subNode;
260 }
261
262 @SuppressWarnings("unchecked")
263 Node<K, V> removeEntry(int selectedHashFragment, OldValueBox<V> oldValue) {
264 content[2 * selectedHashFragment] = null;
265 oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
266 content[2 * selectedHashFragment + 1] = null;
267 if (hasContent()) {
268 updateHash();
269 return this;
270 } else {
271 return null;
272 }
273 }
274
275 @SuppressWarnings("unchecked")
276 @Override
277 public long getSize() {
278 int size = 0;
279 for (int i = 0; i < FACTOR; i++) {
280 if (content[i * 2] != null) {
281 size++;
282 } else {
283 Node<K, V> nodeCandidate = (Node<K, V>) content[i * 2 + 1];
284 if (nodeCandidate != null) {
285 size += nodeCandidate.getSize();
286 }
287 }
288 }
289 return size;
290 }
291
292 @Override
293 protected MutableNode<K, V> toMutable() {
294 return this;
295 }
296
297 @Override
298 public ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache) {
299 return ImmutableNode.constructImmutable(this, cache);
300 }
301
302 @SuppressWarnings("unchecked")
303 @Override
304 boolean moveToNext(MapCursor<K, V> cursor) {
305 // 1. try to move to data
306 if (cursor.dataIndex != MapCursor.INDEX_FINISH) {
307 for (int index = cursor.dataIndex + 1; index < FACTOR; index++) {
308 if (this.content[index * 2] != null) {
309 // 1.1 found next data
310 cursor.dataIndex = index;
311 cursor.key = (K) this.content[index * 2];
312 cursor.value = (V) this.content[index * 2 + 1];
313 return true;
314 }
315 }
316 cursor.dataIndex = MapCursor.INDEX_FINISH;
317 }
318
319 // 2. look inside the subnodes
320 for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) {
321 if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) {
322 // 2.1 found next subnode, move down to the subnode
323 Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1];
324
325 cursor.dataIndex = MapCursor.INDEX_START;
326 cursor.nodeIndexStack.pop();
327 cursor.nodeIndexStack.push(index);
328 cursor.nodeIndexStack.push(MapCursor.INDEX_START);
329 cursor.nodeStack.push(subnode);
330
331 return subnode.moveToNext(cursor);
332 }
333 }
334 // 3. no subnode found, move up
335 cursor.nodeStack.pop();
336 cursor.nodeIndexStack.pop();
337 if (!cursor.nodeStack.isEmpty()) {
338 Node<K, V> supernode = cursor.nodeStack.peek();
339 return supernode.moveToNext(cursor);
340 } else {
341 cursor.key = null;
342 cursor.value = null;
343 return false;
344 }
345 }
346
347 @Override
348 public void prettyPrint(StringBuilder builder, int depth, int code) {
349 for (int i = 0; i < depth; i++) {
350 builder.append("\t");
351 }
352 if (code >= 0) {
353 builder.append(code);
354 builder.append(":");
355 }
356 builder.append("Mutable(");
357 // print content
358 boolean hadContent = false;
359 for (int i = 0; i < FACTOR; i++) {
360 if (content[2 * i] != null) {
361 if (hadContent) {
362 builder.append(",");
363 }
364 builder.append(i);
365 builder.append(":[");
366 builder.append(content[2 * i].toString());
367 builder.append("]->[");
368 builder.append(content[2 * i + 1].toString());
369 builder.append("]");
370 hadContent = true;
371 }
372 }
373 builder.append(")");
374 // print subnodes
375 for (int i = 0; i < FACTOR; i++) {
376 if (content[2 * i] == null && content[2 * i + 1] != null) {
377 @SuppressWarnings("unchecked")
378 Node<K, V> subNode = (Node<K, V>) content[2 * i + 1];
379 builder.append("\n");
380 subNode.prettyPrint(builder, depth + 1, i);
381 }
382 }
383 }
384
385 @Override
386 public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
387 // check for orphan nodes
388 if (depth > 0) {
389 int orphaned = isOrphaned();
390 if (orphaned >= 0) {
391 throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]);
392 }
393 }
394 // check the place of data
395 for (int i = 0; i < FACTOR; i++) {
396 if (this.content[2 * i] != null) {
397 @SuppressWarnings("unchecked")
398 K key = (K) this.content[2 * i];
399 @SuppressWarnings("unchecked")
400 V value = (V) this.content[2 * i + 1];
401
402 if (value == defaultValue) {
403 throw new IllegalStateException("Node contains default value!");
404 }
405 int hashCode = hashProvider.getHash(key, hashDepth(depth));
406 int shiftDepth = shiftDepth(depth);
407 int selectedHashFragment = hashFragment(hashCode, shiftDepth);
408 if (i != selectedHashFragment) {
409 throw new IllegalStateException("Key " + key + " with hash code " + hashCode
410 + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i);
411 }
412 }
413 }
414 // check subnodes
415 for (int i = 0; i < FACTOR; i++) {
416 if (this.content[2 * i + 1] != null && this.content[2 * i] == null) {
417 @SuppressWarnings("unchecked")
418 var subNode = (Node<K, V>) this.content[2 * i + 1];
419 subNode.checkIntegrity(hashProvider, defaultValue, depth + 1);
420 }
421 }
422 // check the hash
423 int oldHash = this.cachedHash;
424 updateHash();
425 int newHash = this.cachedHash;
426 if (oldHash != newHash) {
427 throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")");
428 }
429 }
430
431 protected void updateHash() {
432 this.cachedHash = Arrays.hashCode(content);
433 }
434
435 @Override
436 public int hashCode() {
437 return this.cachedHash;
438 }
439
440 @Override
441 public boolean equals(Object obj) {
442 if (this == obj)
443 return true;
444 if (obj == null)
445 return false;
446 if (obj instanceof MutableNode<?, ?> mutableObj) {
447 return Arrays.deepEquals(this.content, mutableObj.content);
448 } else if (obj instanceof ImmutableNode<?, ?> immutableObj) {
449 return ImmutableNode.compareImmutableMutable(immutableObj, this);
450 } else {
451 return false;
452 }
453 }
454}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java
new file mode 100644
index 00000000..234a4ff3
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java
@@ -0,0 +1,85 @@
1package tools.refinery.store.map.internal;
2
3import java.util.Map;
4
5import tools.refinery.store.map.ContinousHashProvider;
6
7public abstract class Node<K,V>{
8 public static final int BRANCHING_FACTOR_BITS = 5;
9 public static final int FACTOR = 1<<BRANCHING_FACTOR_BITS;
10 protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS;
11 protected static final int FACTOR_MASK = FACTOR-1;
12 public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS;
13
14 /**
15 * Calculates the index for the continuous hash.
16 * @param depth The depth of the node in the tree.
17 * @return The index of the continuous hash.
18 */
19 protected static int hashDepth(int depth) {
20 return depth/NUMBER_OF_FACTORS;
21 }
22
23 /**
24 * Calculates the which segment of a single hash should be used.
25 * @param depth The depth of the node in the tree.
26 * @return The segment of a hash code.
27 */
28 protected static int shiftDepth(int depth) {
29 return depth%NUMBER_OF_FACTORS;
30 }
31 /**
32 * Selects a segments from a complete hash for a given depth.
33 * @param hash A complete hash.
34 * @param shiftDepth The index of the segment.
35 * @return The segment as an integer.
36 */
37 protected static int hashFragment(int hash, int shiftDepth) {
38 if(shiftDepth<0 || Node.NUMBER_OF_FACTORS<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth);
39 return (hash >>> shiftDepth*BRANCHING_FACTOR_BITS) & FACTOR_MASK;
40 }
41
42 /**
43 * Returns the hash code for a given depth. It may calculate new hash code, or reuse a hash code calculated for depth-1.
44 * @param key The key.
45 * @param hash Hash code for depth-1
46 * @param depth The depth.
47 * @return The new hash code.
48 */
49 protected int newHash(final ContinousHashProvider<? super K> hashProvider, K key, int hash, int depth) {
50 final int hashDepth = hashDepth(depth);
51 if(hashDepth>=ContinousHashProvider.MAX_PRACTICAL_DEPTH) {
52 throw new IllegalArgumentException("Key "+key+" have the clashing hashcode over the practical depth limitation ("+ContinousHashProvider.MAX_PRACTICAL_DEPTH+")!");
53 }
54 return depth%NUMBER_OF_FACTORS == 0?
55 hashProvider.getHash(key, hashDepth) :
56 hash;
57 }
58
59
60 public abstract V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth);
61 public abstract Node<K,V> putValue(K key, V value, OldValueBox<V> old, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth);
62 public abstract long getSize();
63
64 abstract MutableNode<K, V> toMutable();
65 public abstract ImmutableNode<K, V> toImmutable(
66 Map<Node<K, V>,ImmutableNode<K, V>> cache);
67 protected abstract MutableNode<K, V> isMutable();
68 /**
69 * Moves a {@link MapCursor} to its next position.
70 * @param cursor the cursor
71 * @return Whether there was a next value to move on.
72 */
73 abstract boolean moveToNext(MapCursor<K,V> cursor);
74
75 ///////// FOR printing
76 public abstract void prettyPrint(StringBuilder builder, int depth, int code);
77 @Override
78 public String toString() {
79 StringBuilder stringBuilder = new StringBuilder();
80 prettyPrint(stringBuilder, 0, -1);
81 return stringBuilder.toString();
82 }
83 public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {}
84
85}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java
new file mode 100644
index 00000000..5534c703
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java
@@ -0,0 +1,19 @@
1package tools.refinery.store.map.internal;
2
3public class OldValueBox<V>{
4 V oldValue;
5 boolean isSet = false;
6
7 public V getOldValue() {
8 if(!isSet) throw new IllegalStateException();
9 isSet = false;
10 return oldValue;
11 }
12
13 public void setOldValue(V ouldValue) {
14 if(isSet) throw new IllegalStateException();
15 this.oldValue = ouldValue;
16 isSet = true;
17 }
18
19}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
new file mode 100644
index 00000000..346fe596
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
@@ -0,0 +1,171 @@
1package tools.refinery.store.map.internal;
2
3import java.util.Iterator;
4import java.util.LinkedList;
5import java.util.List;
6
7import tools.refinery.store.map.ContinousHashProvider;
8import tools.refinery.store.map.Cursor;
9import tools.refinery.store.map.DiffCursor;
10import tools.refinery.store.map.VersionedMap;
11import tools.refinery.store.map.VersionedMapStoreImpl;
12
13/**
14 * Not threadSafe in itself
15 * @author Oszkar Semerath
16 *
17 * @param <K>
18 * @param <V>
19 */
20public class VersionedMapImpl<K,V> implements VersionedMap<K,V>{
21 protected final VersionedMapStoreImpl<K,V> store;
22
23 protected final ContinousHashProvider<K> hashProvider;
24 protected final V defaultValue;
25 protected Node<K,V> root;
26
27 private OldValueBox<V> oldValueBox = new OldValueBox<>();
28
29 public VersionedMapImpl(
30 VersionedMapStoreImpl<K,V> store,
31 ContinousHashProvider<K> hashProvider,
32 V defaultValue)
33 {
34 this.store = store;
35 this.hashProvider = hashProvider;
36 this.defaultValue = defaultValue;
37 this.root = null;
38 }
39 public VersionedMapImpl(
40 VersionedMapStoreImpl<K,V> store,
41 ContinousHashProvider<K> hashProvider,
42 V defaultValue, Node<K,V> data)
43 {
44 this.store = store;
45 this.hashProvider = hashProvider;
46 this.defaultValue = defaultValue;
47 this.root = data;
48 }
49
50 public V getDefaultValue() {
51 return defaultValue;
52 }
53 public ContinousHashProvider<K> getHashProvider() {
54 return hashProvider;
55 }
56 @Override
57 public V put(K key, V value) {
58 if(root!=null) {
59 root = root.putValue(key, value, oldValueBox, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0);
60 return oldValueBox.getOldValue();
61 } else {
62 root = MutableNode.initialize(key, value, hashProvider, defaultValue);
63 return defaultValue;
64 }
65 }
66
67 @Override
68 public void putAll(Cursor<K, V> cursor) {
69 if(cursor.getDependingMaps().contains(this)) {
70 List<K> keys = new LinkedList<>();
71 List<V> values = new LinkedList<>();
72 while(cursor.move()) {
73 keys.add(cursor.getKey());
74 values.add(cursor.getValue());
75 }
76 Iterator<K> keyIterator = keys.iterator();
77 Iterator<V> valueIterator = values.iterator();
78 while(keyIterator.hasNext()) {
79 this.put(keyIterator.next(), valueIterator.next());
80 }
81 } else {
82 while(cursor.move()) {
83 this.put(cursor.getKey(), cursor.getValue());
84 }
85 }
86 }
87
88 @Override
89 public V get(K key) {
90 if(root!=null) {
91 return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0);
92 } else {
93 return defaultValue;
94 }
95 }
96 @Override
97 public long getSize() {
98 if(root == null) {
99 return 0;
100 } else {
101 return root.getSize();
102 }
103 }
104
105 @Override
106 public Cursor<K, V> getAll() {
107 return new MapCursor<>(this.root,this);
108 }
109 @Override
110 public DiffCursor<K, V> getDiffCursor(long toVersion) {
111 Cursor<K, V> fromCursor = this.getAll();
112 VersionedMap<K, V> toMap = this.store.createMap(toVersion);
113 Cursor<K, V> toCursor = toMap.getAll();
114 return new MapDiffCursor<>(this.hashProvider,this.defaultValue, fromCursor, toCursor);
115
116 }
117
118
119 @Override
120 public long commit() {
121 return this.store.commit(root,this);
122 }
123 public void setRoot(Node<K, V> root) {
124 this.root = root;
125 }
126
127 @Override
128 public void restore(long state) {
129 root = this.store.revert(state);
130 }
131
132 @Override
133 public int hashCode() {
134 final int prime = 31;
135 int result = 1;
136 result = prime * result + ((root == null) ? 0 : root.hashCode());
137 return result;
138 }
139
140 @Override
141 public boolean equals(Object obj) {
142 if (this == obj)
143 return true;
144 if (obj == null)
145 return false;
146 if (getClass() != obj.getClass())
147 return false;
148 VersionedMapImpl<?,?> other = (VersionedMapImpl<?,?>) obj;
149 if (root == null) {
150 if (other.root != null)
151 return false;
152 } else if (!root.equals(other.root))
153 return false;
154 return true;
155 }
156 public void prettyPrint() {
157 StringBuilder s = new StringBuilder();
158 if(this.root != null) {
159 this.root.prettyPrint(s, 0, -1);
160 System.out.println(s.toString());
161 } else {
162 System.out.println("empty tree");
163 }
164 }
165 public void checkIntegrity() {
166 if(this.root != null) {
167 this.root.checkIntegrity(hashProvider, defaultValue, 0);
168 }
169 }
170
171}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/Model.java b/subprojects/store/src/main/java/tools/refinery/store/model/Model.java
new file mode 100644
index 00000000..a42d711a
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/Model.java
@@ -0,0 +1,20 @@
1package tools.refinery.store.model;
2
3import java.util.Set;
4
5import tools.refinery.store.map.Cursor;
6import tools.refinery.store.map.Versioned;
7import tools.refinery.store.model.representation.DataRepresentation;
8
9public interface Model extends Versioned{
10 @SuppressWarnings("squid:S1452")
11 Set<DataRepresentation<?, ?>> getDataRepresentations();
12
13 <K,V> V get(DataRepresentation<K,V> representation, K key);
14 <K,V> Cursor<K,V> getAll(DataRepresentation<K,V> representation);
15 <K,V> V put(DataRepresentation<K,V> representation, K key, V value);
16 <K,V> void putAll(DataRepresentation<K,V> representation, Cursor<K,V> cursor);
17 <K,V> long getSize(DataRepresentation<K,V> representation);
18
19 ModelDiffCursor getDiffCursor(long to);
20}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/ModelCursor.java b/subprojects/store/src/main/java/tools/refinery/store/model/ModelCursor.java
new file mode 100644
index 00000000..a835cf69
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/ModelCursor.java
@@ -0,0 +1,25 @@
1package tools.refinery.store.model;
2
3import java.util.Map;
4
5import tools.refinery.store.map.Cursor;
6import tools.refinery.store.model.representation.DataRepresentation;
7
8public class ModelCursor {
9 final Map<DataRepresentation<?, ?>,Cursor<?,?>> cursors;
10
11 public ModelCursor(Map<DataRepresentation<?, ?>, Cursor<?, ?>> cursors) {
12 super();
13 this.cursors = cursors;
14 }
15
16 @SuppressWarnings("unchecked")
17 public <K,V> Cursor<K,V> getCursor(DataRepresentation<K, V> representation) {
18 Cursor<?, ?> cursor = cursors.get(representation);
19 if(cursor != null) {
20 return (Cursor<K, V>) cursor;
21 } else {
22 throw new IllegalArgumentException("ModelCursor does not contain cursor for representation "+representation);
23 }
24 }
25}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/ModelDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/model/ModelDiffCursor.java
new file mode 100644
index 00000000..91990fa6
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/ModelDiffCursor.java
@@ -0,0 +1,26 @@
1package tools.refinery.store.model;
2
3import java.util.Map;
4
5import tools.refinery.store.map.Cursor;
6import tools.refinery.store.map.DiffCursor;
7import tools.refinery.store.model.representation.DataRepresentation;
8
9public class ModelDiffCursor {
10 final Map<DataRepresentation<?, ?>,DiffCursor<?,?>> diffcursors;
11
12 public ModelDiffCursor(Map<DataRepresentation<?, ?>, DiffCursor<?, ?>> diffcursors) {
13 super();
14 this.diffcursors = diffcursors;
15 }
16
17 @SuppressWarnings("unchecked")
18 public <K,V> DiffCursor<K,V> getCursor(DataRepresentation<K, V> representation) {
19 Cursor<?, ?> cursor = diffcursors.get(representation);
20 if(cursor != null) {
21 return (DiffCursor<K, V>) cursor;
22 } else {
23 throw new IllegalArgumentException("ModelCursor does not contain cursor for representation "+representation);
24 }
25 }
26}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java b/subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java
new file mode 100644
index 00000000..682a0e78
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java
@@ -0,0 +1,16 @@
1package tools.refinery.store.model;
2
3import java.util.Set;
4
5import tools.refinery.store.model.representation.DataRepresentation;
6
7public interface ModelStore {
8 @SuppressWarnings("squid:S1452")
9 Set<DataRepresentation<?, ?>> getDataRepresentations();
10
11 Model createModel();
12 Model createModel(long state);
13
14 Set<Long> getStates();
15 ModelDiffCursor getDiffCursor(long from, long to);
16} \ No newline at end of file
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/ModelStoreImpl.java b/subprojects/store/src/main/java/tools/refinery/store/model/ModelStoreImpl.java
new file mode 100644
index 00000000..97406cbb
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/ModelStoreImpl.java
@@ -0,0 +1,122 @@
1package tools.refinery.store.model;
2
3import java.util.HashMap;
4import java.util.LinkedList;
5import java.util.List;
6import java.util.Map;
7import java.util.Map.Entry;
8
9import tools.refinery.store.map.ContinousHashProvider;
10import tools.refinery.store.map.DiffCursor;
11import tools.refinery.store.map.VersionedMap;
12import tools.refinery.store.map.VersionedMapStore;
13import tools.refinery.store.map.VersionedMapStoreImpl;
14import tools.refinery.store.model.internal.ModelImpl;
15import tools.refinery.store.model.internal.SimilarRelationEquivalenceClass;
16import tools.refinery.store.model.representation.AuxilaryData;
17import tools.refinery.store.model.representation.DataRepresentation;
18import tools.refinery.store.model.representation.Relation;
19
20import java.util.Set;
21
22public class ModelStoreImpl implements ModelStore {
23
24 private final Map<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> stores;
25
26 public ModelStoreImpl(Set<DataRepresentation<?, ?>> dataRepresentations) {
27 stores = initStores(dataRepresentations);
28 }
29
30 private Map<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> initStores(
31 Set<DataRepresentation<?, ?>> dataRepresentations) {
32 Map<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> result = new HashMap<>();
33
34 Map<SimilarRelationEquivalenceClass, List<Relation<?>>> symbolRepresentationsPerHashPerArity = new HashMap<>();
35
36 for (DataRepresentation<?, ?> dataRepresentation : dataRepresentations) {
37 if (dataRepresentation instanceof Relation<?> symbolRepresentation) {
38 addOrCreate(symbolRepresentationsPerHashPerArity,
39 new SimilarRelationEquivalenceClass(symbolRepresentation), symbolRepresentation);
40 } else if (dataRepresentation instanceof AuxilaryData<?, ?>) {
41 VersionedMapStoreImpl<?, ?> store = new VersionedMapStoreImpl<>(dataRepresentation.getHashProvider(),
42 dataRepresentation.getDefaultValue());
43 result.put(dataRepresentation, store);
44 } else {
45 throw new UnsupportedOperationException(
46 "Model store does not have strategy to use " + dataRepresentation.getClass() + "!");
47 }
48 }
49 for (List<Relation<?>> symbolGroup : symbolRepresentationsPerHashPerArity.values()) {
50 initRepresentationGroup(result, symbolGroup);
51 }
52
53 return result;
54 }
55
56 private void initRepresentationGroup(Map<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> result,
57 List<Relation<?>> symbolGroup) {
58 final ContinousHashProvider<Tuple> hashProvider = symbolGroup.get(0).getHashProvider();
59 final Object defaultValue = symbolGroup.get(0).getDefaultValue();
60
61 List<VersionedMapStore<Tuple, Object>> maps = VersionedMapStoreImpl
62 .createSharedVersionedMapStores(symbolGroup.size(), hashProvider, defaultValue);
63
64 for (int i = 0; i < symbolGroup.size(); i++) {
65 result.put(symbolGroup.get(i), maps.get(i));
66 }
67 }
68
69 private static <K, V> void addOrCreate(Map<K, List<V>> map, K key, V value) {
70 List<V> list;
71 if (map.containsKey(key)) {
72 list = map.get(key);
73 } else {
74 list = new LinkedList<>();
75 map.put(key, list);
76 }
77 list.add(value);
78 }
79
80 @Override
81 public Set<DataRepresentation<?, ?>> getDataRepresentations() {
82 return this.stores.keySet();
83 }
84
85 @Override
86 public ModelImpl createModel() {
87 Map<DataRepresentation<?, ?>, VersionedMap<?, ?>> maps = new HashMap<>();
88 for (Entry<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> entry : this.stores.entrySet()) {
89 maps.put(entry.getKey(), entry.getValue().createMap());
90 }
91 return new ModelImpl(this, maps);
92 }
93
94 @Override
95 public synchronized ModelImpl createModel(long state) {
96 Map<DataRepresentation<?, ?>, VersionedMap<?, ?>> maps = new HashMap<>();
97 for (Entry<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> entry : this.stores.entrySet()) {
98 maps.put(entry.getKey(), entry.getValue().createMap(state));
99 }
100 return new ModelImpl(this, maps);
101 }
102
103 @Override
104 public synchronized Set<Long> getStates() {
105 var iterator = stores.values().iterator();
106 if (iterator.hasNext()) {
107 return Set.copyOf(iterator.next().getStates());
108 }
109 return Set.of(0l);
110 }
111
112 @Override
113 public synchronized ModelDiffCursor getDiffCursor(long from, long to) {
114 Map<DataRepresentation<?, ?>, DiffCursor<?, ?>> diffcursors = new HashMap<>();
115 for (Entry<DataRepresentation<?, ?>, VersionedMapStore<?, ?>> entry : stores.entrySet()) {
116 DataRepresentation<?, ?> representation = entry.getKey();
117 DiffCursor<?, ?> diffCursor = entry.getValue().getDiffCursor(from, to);
118 diffcursors.put(representation, diffCursor);
119 }
120 return new ModelDiffCursor(diffcursors);
121 }
122}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/Tuple.java b/subprojects/store/src/main/java/tools/refinery/store/model/Tuple.java
new file mode 100644
index 00000000..0aae3727
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/Tuple.java
@@ -0,0 +1,148 @@
1package tools.refinery.store.model;
2
3import java.util.ArrayList;
4import java.util.Arrays;
5import java.util.List;
6
7public abstract class Tuple {
8 private static final int CUSTOMTUPLESIZE = 2;
9 protected static final List<Tuple1> tuple1Cash = new ArrayList<>(1024);
10
11 public abstract int getSize();
12 public abstract int get(int element);
13 public abstract int[] toArray();
14
15 @Override
16 public String toString() {
17 StringBuilder b = new StringBuilder();
18 b.append("[");
19 for(int i = 0; i<getSize(); i++) {
20 if(i!=0) {
21 b.append(",");
22 }
23 b.append(get(i));
24 }
25 b.append("]");
26 return b.toString();
27 }
28
29 public static Tuple1 of1(int value) {
30 if(value < tuple1Cash.size()) {
31 return tuple1Cash.get(value);
32 } else {
33 Tuple1 newlyCreated = null;
34 while(value >= tuple1Cash.size()) {
35 newlyCreated = new Tuple1(tuple1Cash.size());
36 tuple1Cash.add(newlyCreated);
37 }
38 return newlyCreated;
39 }
40 }
41
42 public static Tuple of(int... values) {
43 if(values.length == 0) {
44 return new Tuple0();
45 } else if(values.length == 1) {
46 return of1(values[0]);
47 } else if(values.length == 2) {
48 return new Tuple2(values[0],values[1]);
49 } else return new TupleN(values);
50 }
51
52 protected IllegalArgumentException doesNotContain(int element) {
53 return new IllegalArgumentException("Tuple does not contain element "+element);
54 }
55
56 public static class Tuple0 extends Tuple{
57 protected Tuple0() { }
58 @Override public int getSize() { return 0; }
59 @Override public int get(int element) {
60 throw doesNotContain(element);
61 }
62 @Override public int[] toArray() {return new int[]{};}
63 @Override public int hashCode() { return TupleHashProvider.singleton().getHash(this, 0); }
64 @Override
65 public boolean equals(Object obj) {
66 if (this == obj)
67 return true;
68 if (obj == null)
69 return false;
70 if (getClass() != obj.getClass())
71 return false;
72 return true;
73 }
74 }
75 public static class Tuple1 extends Tuple{
76 final int value0;
77 protected Tuple1(int value0) { this.value0 = value0; }
78 @Override public int getSize() { return 1; }
79 @Override public int get(int element) {
80 if(element == 0) return value0;
81 throw doesNotContain(element);
82 }
83 @Override public int[] toArray() {return new int[]{ value0 };}
84 @Override public int hashCode() { return TupleHashProvider.singleton().getHash(this, 0); }
85 @Override
86 public boolean equals(Object obj) {
87 if (this == obj)
88 return true;
89 if (obj == null)
90 return false;
91 if (getClass() != obj.getClass())
92 return false;
93 Tuple1 other = (Tuple1) obj;
94 return value0 == other.value0;
95 }
96 }
97 public static class Tuple2 extends Tuple{
98 final int value0;
99 final int value1;
100 protected Tuple2(int value0, int value1) { this.value0 = value0; this.value1 = value1; }
101 @Override public int getSize() { return 2; }
102 @Override public int get(int element) {
103 if(element == 0) return value0;
104 else if(element == 1) return value1;
105 throw doesNotContain(element);
106 }
107 @Override public int[] toArray() {return new int[]{ value0,value1 };}
108 @Override public int hashCode() { return TupleHashProvider.singleton().getHash(this, 0); }
109 @Override
110 public boolean equals(Object obj) {
111 if (this == obj)
112 return true;
113 if (obj == null)
114 return false;
115 if (getClass() != obj.getClass())
116 return false;
117 Tuple2 other = (Tuple2) obj;
118 return value0 == other.value0 && value1 == other.value1;
119 }
120 }
121 public static class TupleN extends Tuple{
122 final int[] values;
123 protected TupleN(int[] values) {
124 if(values.length<CUSTOMTUPLESIZE)
125 throw new IllegalArgumentException();
126 this.values = Arrays.copyOf(values, values.length);
127 }
128 @Override public int getSize() { return values.length; }
129 @Override public int get(int element) {
130 if(0<=element && element < values.length) {
131 return values[element];
132 } else throw doesNotContain(element);
133 }
134 @Override public int[] toArray() { return values; }
135 @Override public int hashCode() { return TupleHashProvider.singleton().getHash(this, 0); }
136 @Override
137 public boolean equals(Object obj) {
138 if (this == obj)
139 return true;
140 if (obj == null)
141 return false;
142 if (getClass() != obj.getClass())
143 return false;
144 TupleN other = (TupleN) obj;
145 return Arrays.equals(values, other.values);
146 }
147 }
148}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java
new file mode 100644
index 00000000..7a01311a
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java
@@ -0,0 +1,65 @@
1package tools.refinery.store.model;
2
3import tools.refinery.store.map.ContinousHashProvider;
4
5public class TupleHashProvider implements ContinousHashProvider<Tuple> {
6 protected static TupleHashProvider instance;
7
8 public static TupleHashProvider singleton() {
9 if (instance == null) {
10 instance = new TupleHashProvider();
11 }
12 return instance;
13 }
14
15 protected static final int[] primes = new int[] { 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
16 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
17 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
18 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461,
19 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
20 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739,
21 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881,
22 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021,
23 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
24 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
25 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429,
26 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549,
27 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
28 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
29 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973,
30 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089,
31 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
32 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
33 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
34 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677,
35 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
36 2797, 2801, 2803, 2819, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217,
37 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359,
38 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517,
39 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637,
40 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793,
41 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911 };
42
43 protected static final long LARGESTPRIME30BITS = 1073741789;
44
45 public TupleHashProvider() {
46 if (primes.length < MAX_PRACTICAL_DEPTH) {
47 throw new UnsupportedOperationException(
48 "Not enough prime numbers to support the practical depth of continuous hash!");
49 }
50 }
51
52 @Override
53 public int getHash(Tuple key, int index) {
54 if (index >= primes.length) {
55 throw new IllegalArgumentException("Not enough prime numbers to support index");
56 }
57 long accumulator = 0;
58 final int prime = primes[index];
59 for (int i = 0; i < key.getSize(); i++) {
60 accumulator = (prime * accumulator + key.get(i)) % LARGESTPRIME30BITS;
61 }
62
63 return (int) accumulator;
64 }
65}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java
new file mode 100644
index 00000000..5b053229
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java
@@ -0,0 +1,28 @@
1package tools.refinery.store.model;
2
3import tools.refinery.store.map.ContinousHashProvider;
4
5public class TupleHashProviderBitMagic implements ContinousHashProvider<Tuple> {
6
7 @Override
8 public int getHash(Tuple key, int index) {
9 if(key.getSize() == 1) {
10 return key.get(0);
11 }
12
13 int result = 0;
14 final int startBitIndex = index*30;
15 final int finalBitIndex = startBitIndex+30;
16 final int arity = key.getSize();
17
18 for(int i = startBitIndex; i<=finalBitIndex; i++) {
19 final int selectedKey = key.get(i%arity);
20 final int selectedPosition = 1<<(i/arity);
21 if((selectedKey&selectedPosition) != 0) {
22 result |= 1<<(i%30);
23 }
24 }
25
26 return result;
27 }
28}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java
new file mode 100644
index 00000000..2a5f2925
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java
@@ -0,0 +1,124 @@
1package tools.refinery.store.model.internal;
2
3import java.util.HashMap;
4import java.util.Map;
5import java.util.Set;
6
7import tools.refinery.store.map.ContinousHashProvider;
8import tools.refinery.store.map.Cursor;
9import tools.refinery.store.map.DiffCursor;
10import tools.refinery.store.map.VersionedMap;
11import tools.refinery.store.map.internal.MapDiffCursor;
12import tools.refinery.store.model.Model;
13import tools.refinery.store.model.ModelDiffCursor;
14import tools.refinery.store.model.ModelStore;
15import tools.refinery.store.model.representation.DataRepresentation;
16
17public class ModelImpl implements Model {
18 private final ModelStore store;
19 private final Map<DataRepresentation<?, ?>, VersionedMap<?, ?>> maps;
20
21 public ModelImpl(ModelStore store, Map<DataRepresentation<?, ?>, VersionedMap<?, ?>> maps) {
22 this.store = store;
23 this.maps = maps;
24 }
25
26 @Override
27 public Set<DataRepresentation<?, ?>> getDataRepresentations() {
28 return maps.keySet();
29 }
30
31 @SuppressWarnings("unchecked")
32 private <K, V> VersionedMap<K, V> getMap(DataRepresentation<K, V> representation) {
33 if (maps.containsKey(representation)) {
34 return (VersionedMap<K, V>) maps.get(representation);
35 } else {
36 throw new IllegalArgumentException("Model does have representation " + representation);
37 }
38 }
39
40 private <K, V> VersionedMap<K, V> getMapValidateKey(DataRepresentation<K, V> representation, K key) {
41 if (representation.isValidKey(key)) {
42 return getMap(representation);
43 } else {
44 throw new IllegalArgumentException(
45 "Key is not valid for representation! (representation=" + representation + ", key=" + key + ");");
46 }
47 }
48
49 @Override
50 public <K, V> V get(DataRepresentation<K, V> representation, K key) {
51 return getMapValidateKey(representation, key).get(key);
52 }
53
54 @Override
55 public <K, V> Cursor<K, V> getAll(DataRepresentation<K, V> representation) {
56 return getMap(representation).getAll();
57 }
58
59 @Override
60 public <K, V> V put(DataRepresentation<K, V> representation, K key, V value) {
61 return getMapValidateKey(representation, key).put(key, value);
62 }
63
64 @Override
65 public <K, V> void putAll(DataRepresentation<K, V> representation, Cursor<K, V> cursor) {
66 getMap(representation).putAll(cursor);
67 }
68
69 @Override
70 public <K, V> long getSize(DataRepresentation<K, V> representation) {
71 return getMap(representation).getSize();
72 }
73
74 @Override
75 public ModelDiffCursor getDiffCursor(long to) {
76 Model toModel = store.createModel(to);
77 Map<DataRepresentation<?, ?>, DiffCursor<?, ?>> diffCursors = new HashMap<>();
78 for (DataRepresentation<?, ?> representation : this.maps.keySet()) {
79 MapDiffCursor<?, ?> diffCursor = constructDiffCursor(toModel, representation);
80 diffCursors.put(representation, diffCursor);
81 }
82 return new ModelDiffCursor(diffCursors);
83 }
84
85 private <K, V> MapDiffCursor<K, V> constructDiffCursor(Model toModel, DataRepresentation<K, V> representation) {
86 @SuppressWarnings("unchecked")
87 Cursor<K, V> fromCursor = (Cursor<K, V>) this.maps.get(representation).getAll();
88 Cursor<K, V> toCursor = toModel.getAll(representation);
89
90 ContinousHashProvider<K> hashProvider = representation.getHashProvider();
91 V defaultValue = representation.getDefaultValue();
92 return new MapDiffCursor<>(hashProvider, defaultValue, fromCursor, toCursor);
93 }
94
95 @Override
96 public long commit() {
97 long version = 0;
98 boolean versionSet = false;
99 for (VersionedMap<?, ?> map : maps.values()) {
100 long newVersion = map.commit();
101 if (versionSet) {
102 if (version != newVersion) {
103 throw new IllegalStateException(
104 "Maps in model have different versions! (" + version + " and" + newVersion + ")");
105 }
106 } else {
107 version = newVersion;
108 versionSet = true;
109 }
110 }
111 return version;
112 }
113
114 @Override
115 public void restore(long state) {
116 if(store.getStates().contains(state)) {
117 for (VersionedMap<?, ?> map : maps.values()) {
118 map.restore(state);
119 }
120 } else {
121 throw new IllegalArgumentException("Map does not contain state "+state+"!");
122 }
123 }
124}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/SimilarRelationEquivalenceClass.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/SimilarRelationEquivalenceClass.java
new file mode 100644
index 00000000..9d1b1dd0
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/SimilarRelationEquivalenceClass.java
@@ -0,0 +1,33 @@
1package tools.refinery.store.model.internal;
2
3import java.util.Objects;
4
5import tools.refinery.store.map.ContinousHashProvider;
6import tools.refinery.store.model.Tuple;
7import tools.refinery.store.model.representation.Relation;
8
9public class SimilarRelationEquivalenceClass {
10 final ContinousHashProvider<Tuple> hashProvider;
11 final Object defaultValue;
12 final int arity;
13 public SimilarRelationEquivalenceClass(Relation<?> representation) {
14 this.hashProvider = representation.getHashProvider();
15 this.defaultValue = representation.getDefaultValue();
16 this.arity = representation.getArity();
17 }
18 @Override
19 public int hashCode() {
20 return Objects.hash(arity, defaultValue, hashProvider);
21 }
22 @Override
23 public boolean equals(Object obj) {
24 if (this == obj)
25 return true;
26 if (!(obj instanceof SimilarRelationEquivalenceClass))
27 return false;
28 SimilarRelationEquivalenceClass other = (SimilarRelationEquivalenceClass) obj;
29 return arity == other.arity && Objects.equals(defaultValue, other.defaultValue)
30 && Objects.equals(hashProvider, other.hashProvider);
31 }
32
33}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/representation/AuxilaryData.java b/subprojects/store/src/main/java/tools/refinery/store/model/representation/AuxilaryData.java
new file mode 100644
index 00000000..ddd8a5f2
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/representation/AuxilaryData.java
@@ -0,0 +1,22 @@
1package tools.refinery.store.model.representation;
2
3import tools.refinery.store.map.ContinousHashProvider;
4
5public class AuxilaryData<K,V> extends DataRepresentation<K, V> {
6 private final String name;
7
8 public AuxilaryData(String name, ContinousHashProvider<K> hashProvider, V defaultValue) {
9 super(hashProvider, defaultValue);
10 this.name = name;
11 }
12
13 @Override
14 public String getName() {
15 return name;
16 }
17
18 @Override
19 public boolean isValidKey(K key) {
20 return true;
21 }
22}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/representation/DataRepresentation.java b/subprojects/store/src/main/java/tools/refinery/store/model/representation/DataRepresentation.java
new file mode 100644
index 00000000..585e7b88
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/representation/DataRepresentation.java
@@ -0,0 +1,24 @@
1package tools.refinery.store.model.representation;
2
3import tools.refinery.store.map.ContinousHashProvider;
4
5public abstract class DataRepresentation<K, V> {
6 protected final ContinousHashProvider<K> hashProvider;
7 protected final V defaultValue;
8
9 protected DataRepresentation(ContinousHashProvider<K> hashProvider, V defaultValue) {
10 this.hashProvider = hashProvider;
11 this.defaultValue = defaultValue;
12 }
13
14 public abstract String getName();
15
16 public ContinousHashProvider<K> getHashProvider() {
17 return hashProvider;
18 }
19 public abstract boolean isValidKey(K key);
20
21 public V getDefaultValue() {
22 return defaultValue;
23 }
24}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/representation/Relation.java b/subprojects/store/src/main/java/tools/refinery/store/model/representation/Relation.java
new file mode 100644
index 00000000..fc2a3185
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/representation/Relation.java
@@ -0,0 +1,31 @@
1package tools.refinery.store.model.representation;
2
3import tools.refinery.store.model.Tuple;
4import tools.refinery.store.model.TupleHashProvider;
5
6public class Relation<D> extends DataRepresentation<Tuple, D> {
7 private final String name;
8 private final int arity;
9
10 public Relation(String name, int arity, D defaultValue) {
11 super(TupleHashProvider.singleton(), defaultValue);
12 this.name = name;
13 this.arity = arity;
14 }
15
16 @Override
17 public String getName() {
18 return name;
19 }
20
21 public int getArity() {
22 return arity;
23 }
24
25 @Override
26 public boolean isValidKey(Tuple key) {
27 if(key == null) {
28 return false;
29 } else return key.getSize() == getArity();
30 }
31}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/representation/TruthValue.java b/subprojects/store/src/main/java/tools/refinery/store/model/representation/TruthValue.java
new file mode 100644
index 00000000..610713f3
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/representation/TruthValue.java
@@ -0,0 +1,51 @@
1package tools.refinery.store.model.representation;
2
3public enum TruthValue {
4 TRUE("true"),
5
6 FALSE("false"),
7
8 UNKNOWN("unknown"),
9
10 ERROR("error");
11
12 private final String name;
13
14 private TruthValue(String name) {
15 this.name = name;
16 }
17
18 public String getName() {
19 return name;
20 }
21
22 public static TruthValue toTruthValue(boolean value) {
23 return value ? TRUE : FALSE;
24 }
25
26 public boolean isConsistent() {
27 return this != ERROR;
28 }
29
30 public boolean isComplete() {
31 return this != UNKNOWN;
32 }
33
34 public boolean must() {
35 return this == TRUE || this == ERROR;
36 }
37
38 public boolean may() {
39 return this == TRUE || this == UNKNOWN;
40 }
41
42 public TruthValue not() {
43 if (this == TRUE) {
44 return FALSE;
45 } else if (this == FALSE) {
46 return TRUE;
47 } else {
48 return this;
49 }
50 }
51}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/QueriableModel.java b/subprojects/store/src/main/java/tools/refinery/store/query/QueriableModel.java
new file mode 100644
index 00000000..f669b3ed
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/QueriableModel.java
@@ -0,0 +1,30 @@
1package tools.refinery.store.query;
2
3import java.util.Optional;
4import java.util.Set;
5import java.util.stream.Stream;
6
7import tools.refinery.store.model.Model;
8import tools.refinery.store.query.building.DNFPredicate;
9
10public interface QueriableModel extends Model{
11 Set<DNFPredicate> getPredicates();
12
13 void flushChanges();
14
15 boolean hasResult(DNFPredicate predicate);
16
17 boolean hasResult(DNFPredicate predicate, Object[] parameters);
18
19 Optional<Object[]> oneResult(DNFPredicate predicate);
20
21 Optional<Object[]> oneResult(DNFPredicate predicate, Object[] parameters);
22
23 Stream<Object[]> allResults(DNFPredicate predicate);
24
25 Stream<Object[]> allResults(DNFPredicate predicate, Object[] parameters);
26
27 int countResults(DNFPredicate predicate);
28
29 int countResults(DNFPredicate predicate, Object[] parameters);
30}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/QueriableModelStore.java b/subprojects/store/src/main/java/tools/refinery/store/query/QueriableModelStore.java
new file mode 100644
index 00000000..3a5b51ff
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/QueriableModelStore.java
@@ -0,0 +1,23 @@
1package tools.refinery.store.query;
2
3import java.util.Set;
4
5import tools.refinery.store.model.ModelDiffCursor;
6import tools.refinery.store.model.ModelStore;
7import tools.refinery.store.model.representation.DataRepresentation;
8import tools.refinery.store.query.building.DNFPredicate;
9import tools.refinery.store.query.view.RelationView;
10
11public interface QueriableModelStore extends ModelStore{
12 @SuppressWarnings("squid:S1452")
13 Set<DataRepresentation<?, ?>> getDataRepresentations();
14 @SuppressWarnings("squid:S1452")
15 Set<RelationView<?>> getViews();
16 Set<DNFPredicate> getPredicates();
17
18 QueriableModel createModel();
19 QueriableModel createModel(long state);
20
21 Set<Long> getStates();
22 ModelDiffCursor getDiffCursor(long from, long to);
23}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/QueriableModelStoreImpl.java b/subprojects/store/src/main/java/tools/refinery/store/query/QueriableModelStoreImpl.java
new file mode 100644
index 00000000..653783dd
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/QueriableModelStoreImpl.java
@@ -0,0 +1,127 @@
1package tools.refinery.store.query;
2
3import java.util.Collections;
4import java.util.HashMap;
5import java.util.Map;
6import java.util.Set;
7
8import org.eclipse.viatra.query.runtime.api.GenericQuerySpecification;
9
10import tools.refinery.store.model.ModelDiffCursor;
11import tools.refinery.store.model.ModelStore;
12import tools.refinery.store.model.ModelStoreImpl;
13import tools.refinery.store.model.representation.DataRepresentation;
14import tools.refinery.store.query.building.DNFAnd;
15import tools.refinery.store.query.building.DNFAtom;
16import tools.refinery.store.query.building.DNFPredicate;
17import tools.refinery.store.query.building.PredicateAtom;
18import tools.refinery.store.query.building.RelationAtom;
19import tools.refinery.store.query.internal.DNF2PQuery;
20import tools.refinery.store.query.internal.QueriableModelImpl;
21import tools.refinery.store.query.internal.RawPatternMatcher;
22import tools.refinery.store.query.internal.DNF2PQuery.SimplePQuery;
23import tools.refinery.store.query.view.RelationView;
24
25public class QueriableModelStoreImpl implements QueriableModelStore {
26 protected final ModelStore store;
27 protected final Set<RelationView<?>> relationViews;
28 protected final Map<DNFPredicate, GenericQuerySpecification<RawPatternMatcher>> predicates;
29
30 public QueriableModelStoreImpl(Set<DataRepresentation<?, ?>> dataRepresentations,
31 Set<RelationView<?>> relationViews, Set<DNFPredicate> predicates) {
32 this.store = new ModelStoreImpl(dataRepresentations);
33 validateViews(dataRepresentations, relationViews);
34 this.relationViews = Collections.unmodifiableSet(relationViews);
35 validatePredicates(relationViews, predicates);
36 this.predicates = initPredicates(predicates);
37 }
38
39 private void validateViews(Set<DataRepresentation<?, ?>> dataRepresentations, Set<RelationView<?>> relationViews) {
40 for (RelationView<?> relationView : relationViews) {
41 // TODO: make it work for non-relation representation?
42 if (!dataRepresentations.contains(relationView.getRepresentation())) {
43 throw new IllegalArgumentException(
44 DataRepresentation.class.getSimpleName() + " " + relationView.getStringID() + " added to "
45 + QueriableModelStore.class.getSimpleName() + " without a referred representation.");
46 }
47 }
48 }
49
50 private void validatePredicates(Set<RelationView<?>> relationViews, Set<DNFPredicate> predicates) {
51 for (DNFPredicate dnfPredicate : predicates) {
52 for (DNFAnd clause : dnfPredicate.getClauses()) {
53 for (DNFAtom atom : clause.getConstraints()) {
54 if (atom instanceof RelationAtom relationAtom) {
55 validateRelationAtom(relationViews, dnfPredicate, relationAtom);
56 } else if (atom instanceof PredicateAtom predicateAtom) {
57 validatePredicateAtom(predicates, dnfPredicate, predicateAtom);
58 }
59 }
60 }
61 }
62 }
63
64 private void validateRelationAtom(Set<RelationView<?>> relationViews, DNFPredicate dnfPredicate,
65 RelationAtom relationAtom) {
66 if (!relationViews.contains(relationAtom.getView())) {
67 throw new IllegalArgumentException(DNFPredicate.class.getSimpleName() + " "
68 + dnfPredicate.getUniqueName() + " contains reference to a view of "
69 + relationAtom.getView().getRepresentation().getName()
70 + " that is not in the model.");
71 }
72 }
73 private void validatePredicateAtom(Set<DNFPredicate> predicates, DNFPredicate dnfPredicate,
74 PredicateAtom predicateAtom) {
75 if (!predicates.contains(predicateAtom.getReferred())) {
76 throw new IllegalArgumentException(
77 DNFPredicate.class.getSimpleName() + " " + dnfPredicate.getUniqueName()
78 + " contains reference to a predicate "
79 + predicateAtom.getReferred().getName()
80 + "that is not in the model.");
81 }
82 }
83
84 private Map<DNFPredicate, GenericQuerySpecification<RawPatternMatcher>> initPredicates(Set<DNFPredicate> predicates) {
85 Map<DNFPredicate, GenericQuerySpecification<RawPatternMatcher>> result = new HashMap<>();
86 Map<DNFPredicate, SimplePQuery> dnf2PQueryMap = new HashMap<>();
87 for (DNFPredicate dnfPredicate : predicates) {
88 GenericQuerySpecification<RawPatternMatcher> query = DNF2PQuery.translate(dnfPredicate,dnf2PQueryMap).build();
89 result.put(dnfPredicate, query);
90 }
91
92 return result;
93 }
94
95 @Override
96 public Set<DataRepresentation<?, ?>> getDataRepresentations() {
97 return store.getDataRepresentations();
98 }
99 @Override
100 public Set<RelationView<?>> getViews() {
101 return this.relationViews;
102 }
103 @Override
104 public Set<DNFPredicate> getPredicates() {
105 return predicates.keySet();
106 }
107
108 @Override
109 public QueriableModel createModel() {
110 return new QueriableModelImpl(this, this.store.createModel(), predicates);
111 }
112
113 @Override
114 public QueriableModel createModel(long state) {
115 return new QueriableModelImpl(this, this.store.createModel(state), predicates);
116 }
117
118 @Override
119 public synchronized Set<Long> getStates() {
120 return this.store.getStates();
121 }
122
123 @Override
124 public synchronized ModelDiffCursor getDiffCursor(long from, long to) {
125 return this.store.getDiffCursor(from, to);
126 }
127}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/building/DNFAnd.java b/subprojects/store/src/main/java/tools/refinery/store/query/building/DNFAnd.java
new file mode 100644
index 00000000..48dabce2
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/building/DNFAnd.java
@@ -0,0 +1,37 @@
1package tools.refinery.store.query.building;
2
3import java.util.HashMap;
4import java.util.HashSet;
5import java.util.List;
6import java.util.Map;
7import java.util.Set;
8
9public class DNFAnd {
10 private Set<Variable> existentiallyQuantified;
11 private List<DNFAtom> constraints;
12 public DNFAnd(Set<Variable> quantifiedVariables, List<DNFAtom> constraints) {
13 super();
14 this.existentiallyQuantified = quantifiedVariables;
15 this.constraints = constraints;
16 }
17 public Set<Variable> getExistentiallyQuantified() {
18 return existentiallyQuantified;
19 }
20 public List<DNFAtom> getConstraints() {
21 return constraints;
22 }
23 void unifyVariables(Map<String,Variable> uniqueVariableMap) {
24 Map<String,Variable> uniqueVariableMapForClause = new HashMap<>(uniqueVariableMap);
25 for(DNFAtom atom : constraints) {
26 atom.unifyVariables(uniqueVariableMapForClause);
27 }
28 }
29 void collectQuantifiedVariables(Set<Variable> parameters) {
30 Set<Variable> result = new HashSet<>();
31 for(DNFAtom constraint : constraints) {
32 constraint.collectAllVariables(result);
33 }
34 result.removeAll(parameters);
35 existentiallyQuantified = result;
36 }
37}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/building/DNFAtom.java b/subprojects/store/src/main/java/tools/refinery/store/query/building/DNFAtom.java
new file mode 100644
index 00000000..b047d7c8
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/building/DNFAtom.java
@@ -0,0 +1,33 @@
1package tools.refinery.store.query.building;
2
3import java.util.Collection;
4import java.util.Iterator;
5import java.util.Map;
6import java.util.Set;
7
8public interface DNFAtom {
9 void unifyVariables(Map<String,Variable> variables);
10 static Variable unifyVariables(Map<String,Variable> unifiedVariables, Variable variable) {
11 if(variable != null) {
12 if(variable.isNamed() && unifiedVariables.containsKey(variable.getName())) {
13 return unifiedVariables.get(variable.getName());
14 }
15 return variable;
16 } else {
17 return null;
18 }
19 }
20 void collectAllVariables(Set<Variable> variables);
21 static void addToCollection(Set<Variable> variables, Variable variable) {
22 if(variable != null) {
23 variables.add(variable);
24 }
25 }
26 static void addToCollection(Set<Variable> variables, Collection<Variable> variableCollection) {
27 Iterator<Variable> iterator = variableCollection.iterator();
28 while(iterator.hasNext()) {
29 Variable variable = iterator.next();
30 addToCollection(variables, variable);
31 }
32 }
33}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/building/DNFPredicate.java b/subprojects/store/src/main/java/tools/refinery/store/query/building/DNFPredicate.java
new file mode 100644
index 00000000..f0c9ac42
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/building/DNFPredicate.java
@@ -0,0 +1,72 @@
1package tools.refinery.store.query.building;
2
3import java.util.HashMap;
4import java.util.HashSet;
5import java.util.List;
6import java.util.Map;
7import java.util.UUID;
8
9public class DNFPredicate {
10 private final String name;
11 private final String uniqueName;
12 private final List<Variable> parameters;
13 private final List<DNFAnd> clauses;
14
15 public DNFPredicate(String name, List<Variable> parameters, List<DNFAnd> clauses) {
16 this.name = name;
17 this.uniqueName = generateUniqueName(name,"predicate");
18 this.parameters = parameters;
19 this.clauses = clauses;
20
21 postProcess();
22 }
23
24 public static String generateUniqueName(String originalName, String defaultPrefix) {
25 UUID uuid = UUID.randomUUID();
26 String uniqueString = uuid.toString().replace('-', '_');
27 if(originalName == null) {
28 return defaultPrefix+uniqueString;
29 } else {
30 return originalName+uniqueString;
31 }
32 }
33
34 public String getName() {
35 return name;
36 }
37 public String getUniqueName() {
38 return uniqueName;
39 }
40 public List<Variable> getVariables() {
41 return parameters;
42 }
43 public List<DNFAnd> getClauses() {
44 return clauses;
45 }
46
47 public void unifyVariables() {
48 Map<String,Variable> uniqueVariableMap = new HashMap<>();
49 for(Variable parameter : this.parameters) {
50 if(parameter.isNamed()) {
51 String parameterName = parameter.getName();
52 if(uniqueVariableMap.containsKey(parameterName)) {
53 throw new IllegalArgumentException("Multiple parameters has the name "+parameterName);
54 } else {
55 uniqueVariableMap.put(parameterName, parameter);
56 }
57 }
58 }
59 for(DNFAnd clause : this.clauses) {
60 clause.unifyVariables(uniqueVariableMap);
61 }
62 }
63 public void collectQuantifiedVariables() {
64 for(DNFAnd clause : this.clauses) {
65 clause.collectQuantifiedVariables(new HashSet<>(parameters));
66 }
67 }
68 public void postProcess() {
69 unifyVariables();
70 collectQuantifiedVariables();
71 }
72}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/building/EquivalenceAtom.java b/subprojects/store/src/main/java/tools/refinery/store/query/building/EquivalenceAtom.java
new file mode 100644
index 00000000..fede2518
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/building/EquivalenceAtom.java
@@ -0,0 +1,44 @@
1package tools.refinery.store.query.building;
2
3import java.util.Map;
4import java.util.Set;
5
6public class EquivalenceAtom implements DNFAtom{
7 private boolean positive;
8 private Variable left;
9 private Variable right;
10 public EquivalenceAtom(boolean positive, Variable left, Variable right) {
11 this.positive = positive;
12 this.left = left;
13 this.right = right;
14 }
15 public boolean isPositive() {
16 return positive;
17 }
18 public void setPositive(boolean positive) {
19 this.positive = positive;
20 }
21 public Variable getLeft() {
22 return left;
23 }
24 public void setLeft(Variable left) {
25 this.left = left;
26 }
27 public Variable getRight() {
28 return right;
29 }
30 public void setRight(Variable right) {
31 this.right = right;
32 }
33
34 @Override
35 public void unifyVariables(Map<String, Variable> variables) {
36 this.left = DNFAtom.unifyVariables(variables,left);
37 this.right = DNFAtom.unifyVariables(variables,right);
38 }
39 @Override
40 public void collectAllVariables(Set<Variable> variables) {
41 DNFAtom.addToCollection(variables, left);
42 DNFAtom.addToCollection(variables, right);
43 }
44}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/building/PredicateAtom.java b/subprojects/store/src/main/java/tools/refinery/store/query/building/PredicateAtom.java
new file mode 100644
index 00000000..42394922
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/building/PredicateAtom.java
@@ -0,0 +1,66 @@
1package tools.refinery.store.query.building;
2
3import java.util.List;
4import java.util.Map;
5import java.util.Set;
6
7public class PredicateAtom implements DNFAtom {
8 private DNFPredicate referred;
9 private List<Variable> substitution;
10 private boolean positive;
11 private boolean transitive;
12
13 public PredicateAtom(boolean positive, boolean transitive, DNFPredicate referred, List<Variable> substitution) {
14 this.positive = positive;
15 this.referred = referred;
16 this.substitution = substitution;
17 this.transitive = transitive;
18 }
19
20 public DNFPredicate getReferred() {
21 return referred;
22 }
23
24 public void setReferred(DNFPredicate referred) {
25 this.referred = referred;
26 }
27
28 public List<Variable> getSubstitution() {
29 return substitution;
30 }
31
32 public void setSubstitution(List<Variable> substitution) {
33 this.substitution = substitution;
34 }
35
36 public boolean isPositive() {
37 return positive;
38 }
39
40 public void setPositive(boolean positive) {
41 this.positive = positive;
42 }
43
44 public boolean isTransitive() {
45 return transitive;
46 }
47
48 public void setTransitive(boolean transitive) {
49 this.transitive = transitive;
50 }
51
52 @Override
53 public void unifyVariables(Map<String, Variable> variables) {
54 for (int i = 0; i < this.substitution.size(); i++) {
55 final Object term = this.substitution.get(i);
56 if (term instanceof Variable variableReference) {
57 this.substitution.set(i, DNFAtom.unifyVariables(variables, variableReference));
58 }
59 }
60 }
61
62 @Override
63 public void collectAllVariables(Set<Variable> variables) {
64 DNFAtom.addToCollection(variables, substitution);
65 }
66}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/building/RelationAtom.java b/subprojects/store/src/main/java/tools/refinery/store/query/building/RelationAtom.java
new file mode 100644
index 00000000..1238f1d7
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/building/RelationAtom.java
@@ -0,0 +1,49 @@
1package tools.refinery.store.query.building;
2
3import java.util.List;
4import java.util.Map;
5import java.util.Set;
6
7import tools.refinery.store.query.view.FilteredRelationView;
8import tools.refinery.store.query.view.RelationView;
9
10public class RelationAtom implements DNFAtom {
11 RelationView<?> view;
12 List<Variable> substitution;
13
14 public RelationAtom(RelationView<?> view, List<Variable> substitution) {
15 this.view = view;
16 this.substitution = substitution;
17 }
18
19 public RelationView<?> getView() {
20 return view;
21 }
22
23 public void setView(FilteredRelationView<?> view) {
24 this.view = view;
25 }
26
27 public List<Variable> getSubstitution() {
28 return substitution;
29 }
30
31 public void setSubstitution(List<Variable> substitution) {
32 this.substitution = substitution;
33 }
34
35 @Override
36 public void unifyVariables(Map<String, Variable> variables) {
37 for (int i = 0; i < this.substitution.size(); i++) {
38 final Object term = this.substitution.get(i);
39 if (term instanceof Variable variableReference) {
40 this.substitution.set(i, DNFAtom.unifyVariables(variables, variableReference));
41 }
42 }
43 }
44
45 @Override
46 public void collectAllVariables(Set<Variable> variables) {
47 DNFAtom.addToCollection(variables, substitution);
48 }
49}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/building/Variable.java b/subprojects/store/src/main/java/tools/refinery/store/query/building/Variable.java
new file mode 100644
index 00000000..9ea7ce83
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/building/Variable.java
@@ -0,0 +1,22 @@
1package tools.refinery.store.query.building;
2
3public class Variable {
4 private final String name;
5 private final String uniqueName;
6
7 public Variable(String name) {
8 super();
9 this.name = name;
10 this.uniqueName = DNFPredicate.generateUniqueName(name, "variable");
11
12 }
13 public String getName() {
14 return name;
15 }
16 public String getUniqueName() {
17 return uniqueName;
18 }
19 public boolean isNamed() {
20 return name != null;
21 }
22}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/DNF2PQuery.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/DNF2PQuery.java
new file mode 100644
index 00000000..bcc03fb4
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/DNF2PQuery.java
@@ -0,0 +1,189 @@
1package tools.refinery.store.query.internal;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.InputMismatchException;
6import java.util.LinkedHashSet;
7import java.util.List;
8import java.util.Map;
9import java.util.Set;
10
11import org.eclipse.viatra.query.runtime.api.GenericQuerySpecification;
12import org.eclipse.viatra.query.runtime.api.ViatraQueryEngine;
13import org.eclipse.viatra.query.runtime.api.scope.QueryScope;
14import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint;
15import org.eclipse.viatra.query.runtime.matchers.psystem.PBody;
16import org.eclipse.viatra.query.runtime.matchers.psystem.PVariable;
17import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.Equality;
18import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.ExportedParameter;
19import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.Inequality;
20import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.NegativePatternCall;
21import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.BinaryTransitiveClosure;
22import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
23import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.TypeConstraint;
24import org.eclipse.viatra.query.runtime.matchers.psystem.queries.BasePQuery;
25import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PParameter;
26import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PVisibility;
27import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
28
29import tools.refinery.store.query.building.DNFAnd;
30import tools.refinery.store.query.building.DNFAtom;
31import tools.refinery.store.query.building.DNFPredicate;
32import tools.refinery.store.query.building.EquivalenceAtom;
33import tools.refinery.store.query.building.PredicateAtom;
34import tools.refinery.store.query.building.RelationAtom;
35import tools.refinery.store.query.building.Variable;
36
37public class DNF2PQuery {
38
39 public static SimplePQuery translate(DNFPredicate predicate, Map<DNFPredicate, SimplePQuery> dnf2PQueryMap) {
40 SimplePQuery query = dnf2PQueryMap.get(predicate);
41 if (query != null) {
42 return query;
43 }
44 query = new DNF2PQuery().new SimplePQuery(predicate.getName());
45 Map<Variable, PParameter> parameters = new HashMap<>();
46
47 predicate.getVariables().forEach(variable -> parameters.put(variable, new PParameter(variable.getName())));
48 List<PParameter> parameterList = new ArrayList<>();
49 for(var param : predicate.getVariables()) {
50 parameterList.add(parameters.get(param));
51 }
52 query.setParameter(parameterList);
53 for (DNFAnd clause : predicate.getClauses()) {
54 PBody body = new PBody(query);
55 List<ExportedParameter> symbolicParameters = new ArrayList<>();
56 for(var param : predicate.getVariables()) {
57 PVariable pVar = body.getOrCreateVariableByName(param.getName());
58 symbolicParameters.add(new ExportedParameter(body, pVar, parameters.get(param)));
59 }
60 body.setSymbolicParameters(symbolicParameters);
61 query.addBody(body);
62 for (DNFAtom constraint : clause.getConstraints()) {
63 translateDNFAtom(constraint, body, dnf2PQueryMap);
64 }
65 }
66 dnf2PQueryMap.put(predicate, query);
67 return query;
68 }
69
70 private static void translateDNFAtom(DNFAtom constraint, PBody body, Map<DNFPredicate, SimplePQuery> dnf2PQueryMap) {
71 if (constraint instanceof EquivalenceAtom equivalence) {
72 translateEquivalenceAtom(equivalence, body);
73 }
74 if (constraint instanceof RelationAtom relation) {
75 translateRelationAtom(relation, body);
76 }
77 if (constraint instanceof PredicateAtom predicate) {
78 translatePredicateAtom(predicate, body, dnf2PQueryMap);
79 }
80 }
81
82 private static void translateEquivalenceAtom(EquivalenceAtom equivalence, PBody body) {
83 PVariable varSource = body.getOrCreateVariableByName(equivalence.getLeft().getName());
84 PVariable varTarget = body.getOrCreateVariableByName(equivalence.getRight().getName());
85 if (equivalence.isPositive())
86 new Equality(body, varSource, varTarget);
87 else
88 new Inequality(body, varSource, varTarget);
89 }
90
91 private static void translateRelationAtom(RelationAtom relation, PBody body) {
92 if (relation.getSubstitution().size() != relation.getView().getArity()) {
93 throw new IllegalArgumentException("Arity (" + relation.getView().getArity()
94 + ") does not match parameter numbers (" + relation.getSubstitution().size() + ")");
95 }
96 Object[] variables = new Object[relation.getSubstitution().size()];
97 for (int i = 0; i < relation.getSubstitution().size(); i++) {
98 variables[i] = body.getOrCreateVariableByName(relation.getSubstitution().get(i).getName());
99 }
100 new TypeConstraint(body, Tuples.flatTupleOf(variables), relation.getView());
101 }
102
103 private static void translatePredicateAtom(PredicateAtom predicate, PBody body, Map<DNFPredicate, SimplePQuery> dnf2PQueryMap) {
104 Object[] variables = new Object[predicate.getSubstitution().size()];
105 for (int i = 0; i < predicate.getSubstitution().size(); i++) {
106 variables[i] = body.getOrCreateVariableByName(predicate.getSubstitution().get(i).getName());
107 }
108 if (predicate.isPositive()) {
109 if (predicate.isTransitive()) {
110 if (predicate.getSubstitution().size() != 2) {
111 throw new IllegalArgumentException("Transitive Predicate Atoms must be binary.");
112 }
113 new BinaryTransitiveClosure(body, Tuples.flatTupleOf(variables),
114 DNF2PQuery.translate(predicate.getReferred(), dnf2PQueryMap));
115 } else {
116 new PositivePatternCall(body, Tuples.flatTupleOf(variables),
117 DNF2PQuery.translate(predicate.getReferred(), dnf2PQueryMap));
118 }
119 } else {
120 if (predicate.isTransitive()) {
121 throw new InputMismatchException("Transitive Predicate Atoms cannot be negative.");
122 } else {
123 new NegativePatternCall(body, Tuples.flatTupleOf(variables),
124 DNF2PQuery.translate(predicate.getReferred(), dnf2PQueryMap));
125 }
126 }
127 }
128
129 public class SimplePQuery extends BasePQuery {
130
131 private String fullyQualifiedName;
132 private List<PParameter> parameters;
133 private LinkedHashSet<PBody> bodies = new LinkedHashSet<>();
134
135 public SimplePQuery(String name) {
136 super(PVisibility.PUBLIC);
137 fullyQualifiedName = name;
138 }
139
140 @Override
141 public String getFullyQualifiedName() {
142 return fullyQualifiedName;
143 }
144
145 public void setParameter(List<PParameter> parameters) {
146 this.parameters = parameters;
147 }
148
149 @Override
150 public List<PParameter> getParameters() {
151 return parameters;
152 }
153
154 public void addBody(PBody body) {
155 bodies.add(body);
156 }
157
158 @Override
159 protected Set<PBody> doGetContainedBodies() {
160 setEvaluationHints(new QueryEvaluationHint(null, QueryEvaluationHint.BackendRequirement.UNSPECIFIED));
161 return bodies;
162 }
163
164 public GenericQuerySpecification<RawPatternMatcher> build() {
165 return new GenericQuerySpecification<RawPatternMatcher>(this) {
166
167 @Override
168 public Class<? extends QueryScope> getPreferredScopeClass() {
169 return RelationalScope.class;
170 }
171
172 @Override
173 protected RawPatternMatcher instantiate(ViatraQueryEngine engine) {
174 RawPatternMatcher matcher = engine.getExistingMatcher(this);
175 if (matcher == null) {
176 matcher = engine.getMatcher(this);
177 }
178 return matcher;
179 }
180
181 @Override
182 public RawPatternMatcher instantiate() {
183 return new RawPatternMatcher(this);
184 }
185
186 };
187 }
188 }
189} \ No newline at end of file
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/DummyBaseIndexer.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/DummyBaseIndexer.java
new file mode 100644
index 00000000..49637071
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/DummyBaseIndexer.java
@@ -0,0 +1,59 @@
1package tools.refinery.store.query.internal;
2
3import java.lang.reflect.InvocationTargetException;
4import java.util.concurrent.Callable;
5
6import org.eclipse.viatra.query.runtime.api.scope.IBaseIndex;
7import org.eclipse.viatra.query.runtime.api.scope.IIndexingErrorListener;
8import org.eclipse.viatra.query.runtime.api.scope.IInstanceObserver;
9import org.eclipse.viatra.query.runtime.api.scope.ViatraBaseIndexChangeListener;
10
11/**
12 * copied from org.eclipse.viatra.query.runtime.tabular.TabularEngineContext;
13 */
14public class DummyBaseIndexer implements IBaseIndex{
15
16 @Override
17 public <V> V coalesceTraversals(Callable<V> callable) throws InvocationTargetException {
18 try {
19 return callable.call();
20 } catch (Exception e) {
21 throw new InvocationTargetException(e);
22 }
23 }
24
25 @Override
26 public void addBaseIndexChangeListener(ViatraBaseIndexChangeListener listener) {
27 // no notification support
28 }
29
30 @Override
31 public void removeBaseIndexChangeListener(ViatraBaseIndexChangeListener listener) {
32 // no notification support
33 }
34
35 @Override
36 public void resampleDerivedFeatures() {
37 throw new UnsupportedOperationException();
38 }
39
40 @Override
41 public boolean addIndexingErrorListener(IIndexingErrorListener listener) {
42 return true;
43 }
44
45 @Override
46 public boolean removeIndexingErrorListener(IIndexingErrorListener listener) {
47 return true;
48 }
49
50 @Override
51 public boolean addInstanceObserver(IInstanceObserver observer, Object observedObject) {
52 return true;
53 }
54
55 @Override
56 public boolean removeInstanceObserver(IInstanceObserver observer, Object observedObject) {
57 return true;
58 }
59}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/ModelUpdateListener.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/ModelUpdateListener.java
new file mode 100644
index 00000000..aa80985f
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/ModelUpdateListener.java
@@ -0,0 +1,103 @@
1package tools.refinery.store.query.internal;
2
3import java.util.HashMap;
4import java.util.HashSet;
5import java.util.Map;
6import java.util.Set;
7
8import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContextListener;
9import org.eclipse.viatra.query.runtime.matchers.tuple.ITuple;
10
11import tools.refinery.store.model.Tuple;
12import tools.refinery.store.model.representation.Relation;
13import tools.refinery.store.query.view.RelationView;
14
15public class ModelUpdateListener {
16 /**
17 * Collections of Relations and their Views.
18 */
19 private final Map<Relation<?>, Set<RelationView<?>>> relation2View;
20 /**
21 * Collection of Views and their buffers.
22 */
23 private final Map<RelationView<?>, Set<ViewUpdateBuffer<?>>> view2Buffers;
24
25 public ModelUpdateListener(Set<RelationView<?>> relationViews) {
26 this.relation2View = new HashMap<>();
27 this.view2Buffers = new HashMap<>();
28
29 for (RelationView<?> relationView : relationViews) {
30 registerView(relationView);
31 }
32 }
33
34 private void registerView(RelationView<?> view) {
35 Relation<?> relation = view.getRepresentation();
36
37 // 1. register views to relations, if necessary
38 var views = relation2View.computeIfAbsent(relation, x->new HashSet<>());
39 views.add(view);
40
41 // 2. register notifier map to views, if necessary
42 view2Buffers.computeIfAbsent(view, x->new HashSet<>());
43 }
44
45 boolean containsRelationalView(RelationView<?> relationalKey) {
46 return view2Buffers.containsKey(relationalKey);
47 }
48
49 <D> void addListener(RelationView<D> relationView, ITuple seed, IQueryRuntimeContextListener listener) {
50 if (view2Buffers.containsKey(relationView)) {
51 ViewUpdateTranslator<D> updateListener = new ViewUpdateTranslator<>(relationView, seed, listener);
52 ViewUpdateBuffer<D> updateBuffer = new ViewUpdateBuffer<>(updateListener);
53 view2Buffers.get(relationView).add(updateBuffer);
54 } else
55 throw new IllegalArgumentException();
56 }
57
58 void removeListener(RelationView<?> relationView, ITuple seed, IQueryRuntimeContextListener listener) {
59 if (view2Buffers.containsKey(relationView)) {
60 Set<ViewUpdateBuffer<?>> buffers = this.view2Buffers.get(relationView);
61 for(var buffer : buffers) {
62 if(buffer.getUpdateListener().key == seed && buffer.getUpdateListener().listener == listener) {
63 // remove buffer and terminate immediately, or it will break iterator.
64 buffers.remove(buffer);
65 return;
66 }
67 }
68 } else
69 throw new IllegalArgumentException();
70 }
71
72 public <D> void addUpdate(Relation<D> relation, Tuple key, D oldValue, D newValue) {
73 var views = this.relation2View.get(relation);
74 if (views != null) {
75 for (var view : views) {
76 var buffers = this.view2Buffers.get(view);
77 for (var buffer : buffers) {
78 @SuppressWarnings("unchecked")
79 var typedBuffer = (ViewUpdateBuffer<D>) buffer;
80 typedBuffer.addChange(key, oldValue, newValue);
81 }
82 }
83 }
84 }
85
86 public boolean hasChange() {
87 for (var bufferCollection : this.view2Buffers.values()) {
88 for (ViewUpdateBuffer<?> buffer : bufferCollection) {
89 if (buffer.hasChange())
90 return true;
91 }
92 }
93 return false;
94 }
95
96 public void flush() {
97 for (var bufferCollection : this.view2Buffers.values()) {
98 for (ViewUpdateBuffer<?> buffer : bufferCollection) {
99 buffer.flush();
100 }
101 }
102 }
103}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/PredicateResult.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/PredicateResult.java
new file mode 100644
index 00000000..65d23eb6
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/PredicateResult.java
@@ -0,0 +1,24 @@
1package tools.refinery.store.query.internal;
2
3import java.util.Optional;
4import java.util.stream.Stream;
5
6public interface PredicateResult {
7
8 boolean hasResult();
9
10 boolean hasResult(Object[] parameters);
11
12 Optional<Object[]> oneResult();
13
14 Optional<Object[]> oneResult(Object[] parameters);
15
16 Stream<Object[]> allResults();
17
18 Stream<Object[]> allResults(Object[] parameters);
19
20 int countResults();
21
22 int countResults(Object[] parameters);
23
24} \ No newline at end of file
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/QueriableModelImpl.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/QueriableModelImpl.java
new file mode 100644
index 00000000..0f4d609f
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/QueriableModelImpl.java
@@ -0,0 +1,212 @@
1package tools.refinery.store.query.internal;
2
3import java.util.HashMap;
4import java.util.Map;
5import java.util.Optional;
6import java.util.Set;
7import java.util.stream.Stream;
8
9import org.eclipse.viatra.query.runtime.api.AdvancedViatraQueryEngine;
10import org.eclipse.viatra.query.runtime.api.GenericQueryGroup;
11import org.eclipse.viatra.query.runtime.api.GenericQuerySpecification;
12import org.eclipse.viatra.query.runtime.api.IQueryGroup;
13
14import tools.refinery.store.map.Cursor;
15import tools.refinery.store.map.DiffCursor;
16import tools.refinery.store.model.Model;
17import tools.refinery.store.model.ModelDiffCursor;
18import tools.refinery.store.model.Tuple;
19import tools.refinery.store.model.representation.DataRepresentation;
20import tools.refinery.store.model.representation.Relation;
21import tools.refinery.store.query.QueriableModel;
22import tools.refinery.store.query.QueriableModelStore;
23import tools.refinery.store.query.building.DNFPredicate;
24
25public class QueriableModelImpl implements QueriableModel {
26 protected final QueriableModelStore store;
27 protected final Model model;
28 protected final Map<DNFPredicate, GenericQuerySpecification<RawPatternMatcher>> predicates2PQuery;
29
30 protected RelationalScope scope;
31 protected AdvancedViatraQueryEngine engine;
32 protected Map<DNFPredicate, RawPatternMatcher> predicate2Matcher;
33
34 public QueriableModelImpl(QueriableModelStore store, Model model,
35 Map<DNFPredicate, GenericQuerySpecification<RawPatternMatcher>> predicates2PQuery) {
36 this.store = store;
37 this.model = model;
38 this.predicates2PQuery = predicates2PQuery;
39 initEngine();
40 }
41
42 private void initEngine() {
43 this.scope = new RelationalScope(this.model, this.store.getViews());
44 this.engine = AdvancedViatraQueryEngine.createUnmanagedEngine(this.scope);
45 this.predicate2Matcher = initMatchers(this.engine, this.predicates2PQuery);
46 }
47
48 private Map<DNFPredicate, RawPatternMatcher> initMatchers(AdvancedViatraQueryEngine engine,
49 Map<DNFPredicate, GenericQuerySpecification<RawPatternMatcher>> predicates2pQuery) {
50 // 1. prepare group
51 IQueryGroup queryGroup = GenericQueryGroup.of(Set.copyOf(predicates2pQuery.values()));
52 engine.prepareGroup(queryGroup, null);
53
54 // 2. then get all matchers
55 Map<DNFPredicate, RawPatternMatcher> result = new HashMap<>();
56 for (var entry : predicates2pQuery.entrySet()) {
57 var matcher = engine.getMatcher(entry.getValue());
58 result.put(entry.getKey(), matcher);
59 }
60 return result;
61 }
62
63 @Override
64 public Set<DataRepresentation<?, ?>> getDataRepresentations() {
65 return model.getDataRepresentations();
66 }
67
68 @Override
69 public Set<DNFPredicate> getPredicates() {
70 return store.getPredicates();
71 }
72
73 @Override
74 public <K, V> V get(DataRepresentation<K, V> representation, K key) {
75 return model.get(representation, key);
76 }
77
78 @Override
79 public <K, V> Cursor<K, V> getAll(DataRepresentation<K, V> representation) {
80 return model.getAll(representation);
81 }
82
83 @SuppressWarnings("unchecked")
84 @Override
85 public <K, V> V put(DataRepresentation<K, V> representation, K key, V value) {
86 V oldValue = this.model.put(representation, key, value);
87 if(representation instanceof Relation<?> relation) {
88 this.scope.processUpdate((Relation<V>)relation, (Tuple)key, oldValue, value);
89 }
90 return oldValue;
91 }
92
93 @Override
94 public <K, V> void putAll(DataRepresentation<K, V> representation, Cursor<K, V> cursor) {
95 if(representation instanceof Relation<?>) {
96 @SuppressWarnings("unchecked")
97 Relation<V> relation = (Relation<V>) representation;
98 while(cursor.move()) {
99 Tuple key = (Tuple) cursor.getKey();
100 V newValue = cursor.getValue();
101 V oldValue = this.model.put(relation, key, newValue);
102 this.scope.processUpdate(relation, key, oldValue, newValue);
103 }
104 } else {
105 this.model.putAll(representation, cursor);
106 }
107 }
108
109 @Override
110 public <K, V> long getSize(DataRepresentation<K, V> representation) {
111 return model.getSize(representation);
112 }
113
114 protected PredicateResult getPredicateResult(DNFPredicate predicate) {
115 var result = this.predicate2Matcher.get(predicate);
116 if (result == null) {
117 throw new IllegalArgumentException("Model does not contain predicate " + predicate.getName() + "!");
118 } else
119 return result;
120 }
121
122 protected void validateParameters(DNFPredicate predicate, Object[] parameters) {
123 int predicateArity = predicate.getVariables().size();
124 int parameterArity = parameters.length;
125 if (parameterArity != predicateArity) {
126 throw new IllegalArgumentException("Predicate " + predicate.getName() + " with " + predicateArity
127 + " arity called with different number of parameters (" + parameterArity + ")!");
128 }
129 }
130
131 @Override
132 public boolean hasResult(DNFPredicate predicate) {
133 return getPredicateResult(predicate).hasResult();
134 }
135
136 @Override
137 public boolean hasResult(DNFPredicate predicate, Object[] parameters) {
138 validateParameters(predicate, parameters);
139 return getPredicateResult(predicate).hasResult(parameters);
140 }
141
142 @Override
143 public Optional<Object[]> oneResult(DNFPredicate predicate){
144 return getPredicateResult(predicate).oneResult();
145 }
146
147 @Override
148 public Optional<Object[]> oneResult(DNFPredicate predicate, Object[] parameters){
149 validateParameters(predicate, parameters);
150 return getPredicateResult(predicate).oneResult(parameters);
151 }
152
153 @Override
154 public Stream<Object[]> allResults(DNFPredicate predicate){
155 return getPredicateResult(predicate).allResults();
156 }
157
158 @Override
159 public Stream<Object[]> allResults(DNFPredicate predicate, Object[] parameters){
160 validateParameters(predicate, parameters);
161 return getPredicateResult(predicate).allResults(parameters);
162 }
163
164 @Override
165 public int countResults(DNFPredicate predicate){
166 return getPredicateResult(predicate).countResults();
167 }
168
169 @Override
170 public int countResults(DNFPredicate predicate, Object[] parameters){
171 validateParameters(predicate, parameters);
172 return getPredicateResult(predicate).countResults(parameters);
173
174 }
175 @Override
176 public void flushChanges() {
177 this.scope.flush();
178 }
179
180 @Override
181 public ModelDiffCursor getDiffCursor(long to) {
182 return model.getDiffCursor(to);
183 }
184
185 @Override
186 public long commit() {
187 return this.model.commit();
188 }
189
190 @Override
191 public void restore(long state) {
192 restoreWithDiffReplay(state);
193 }
194
195 public void restoreWithDiffReplay(long state) {
196 var modelDiffCursor = getDiffCursor(state);
197 for(DataRepresentation<?,?> dataRepresentation : this.getDataRepresentations()) {
198 restoreRepresentationWithDiffReplay(modelDiffCursor, dataRepresentation);
199 }
200 }
201
202 private <K,V> void restoreRepresentationWithDiffReplay(ModelDiffCursor modelDiffCursor,
203 DataRepresentation<K, V> dataRepresentation) {
204 DiffCursor<K,V> diffCursor = modelDiffCursor.getCursor(dataRepresentation);
205 this.putAll(dataRepresentation, diffCursor);
206 }
207
208 public void restoreWithReinit(long state) {
209 model.restore(state);
210 this.initEngine();
211 }
212}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/RawPatternMatcher.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/RawPatternMatcher.java
new file mode 100644
index 00000000..c6d6353c
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/RawPatternMatcher.java
@@ -0,0 +1,57 @@
1package tools.refinery.store.query.internal;
2
3import java.util.Optional;
4import java.util.stream.Stream;
5
6import org.eclipse.viatra.query.runtime.api.GenericPatternMatcher;
7import org.eclipse.viatra.query.runtime.api.GenericQuerySpecification;
8import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
9import org.eclipse.viatra.query.runtime.matchers.tuple.AbstractTuple;
10
11public class RawPatternMatcher extends GenericPatternMatcher implements PredicateResult{
12
13 protected final Object[] empty;
14
15 public RawPatternMatcher(GenericQuerySpecification<? extends GenericPatternMatcher> specification) {
16 super(specification);
17 this.empty = new Object[specification.getParameterNames().size()];
18 }
19
20 @Override
21 public boolean hasResult() {
22 return hasResult(empty);
23 }
24 @Override
25 public boolean hasResult(Object[] parameters) {
26 return this.backend.hasMatch(parameters);
27 }
28 @Override
29 public Optional<Object[]> oneResult() {
30 return oneResult(empty);
31 }
32 @Override
33 public Optional<Object[]> oneResult(Object[] parameters) {
34 Optional<Tuple> tuple = this.backend.getOneArbitraryMatch(parameters);
35 if(tuple.isPresent()) {
36 return Optional.of(tuple.get().getElements());
37 } else {
38 return Optional.empty();
39 }
40 }
41 @Override
42 public Stream<Object[]> allResults() {
43 return allResults(empty);
44 }
45 @Override
46 public Stream<Object[]> allResults(Object[] parameters) {
47 return this.backend.getAllMatches(parameters).map(AbstractTuple::getElements);
48 }
49 @Override
50 public int countResults() {
51 return countResults(empty);
52 }
53 @Override
54 public int countResults(Object[] parameters) {
55 return backend.countMatches(parameters);
56 }
57}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalEngineContext.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalEngineContext.java
new file mode 100644
index 00000000..dfbd8545
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalEngineContext.java
@@ -0,0 +1,33 @@
1package tools.refinery.store.query.internal;
2
3import org.eclipse.viatra.query.runtime.api.scope.IBaseIndex;
4import org.eclipse.viatra.query.runtime.api.scope.IEngineContext;
5import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContext;
6
7import tools.refinery.store.model.Model;
8
9public class RelationalEngineContext implements IEngineContext{
10 private final IBaseIndex baseIndex = new DummyBaseIndexer();
11 private final RelationalRuntimeContext runtimeContext;
12
13
14 public RelationalEngineContext(Model model, ModelUpdateListener updateListener) {
15 runtimeContext = new RelationalRuntimeContext(model, updateListener);
16 }
17
18 @Override
19 public IBaseIndex getBaseIndex() {
20 return this.baseIndex;
21 }
22
23 @Override
24 public void dispose() {
25 //lifecycle not controlled by engine
26 }
27
28 @Override
29 public IQueryRuntimeContext getQueryRuntimeContext() {
30 return runtimeContext;
31 }
32
33}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalQueryMetaContext.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalQueryMetaContext.java
new file mode 100644
index 00000000..05fb0904
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalQueryMetaContext.java
@@ -0,0 +1,58 @@
1package tools.refinery.store.query.internal;
2
3import java.util.Collection;
4import java.util.Collections;
5import java.util.HashMap;
6import java.util.HashSet;
7import java.util.Map;
8import java.util.Set;
9
10import org.eclipse.viatra.query.runtime.matchers.context.AbstractQueryMetaContext;
11import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
12import org.eclipse.viatra.query.runtime.matchers.context.InputKeyImplication;
13
14import tools.refinery.store.query.view.RelationView;
15
16/**
17 * The meta context information for String scopes.
18 */
19public final class RelationalQueryMetaContext extends AbstractQueryMetaContext {
20
21 @Override
22 public boolean isEnumerable(IInputKey key) {
23 ensureValidKey(key);
24 return key.isEnumerable();
25 }
26
27 @Override
28 public boolean isStateless(IInputKey key) {
29 ensureValidKey(key);
30 return key instanceof RelationView<?>;
31 }
32
33 @Override
34 public Collection<InputKeyImplication> getImplications(IInputKey implyingKey) {
35 ensureValidKey(implyingKey);
36 return new HashSet<InputKeyImplication>();
37 }
38
39 @Override
40 public Map<Set<Integer>, Set<Integer>> getFunctionalDependencies(IInputKey key) {
41 ensureValidKey(key);
42 if (key instanceof RelationView) {
43 return new HashMap<Set<Integer>, Set<Integer>>();
44 } else {
45 return Collections.emptyMap();
46 }
47 }
48
49 public void ensureValidKey(IInputKey key) {
50 if (! (key instanceof RelationView<?>))
51 illegalInputKey(key);
52 }
53
54 public void illegalInputKey(IInputKey key) {
55 throw new IllegalArgumentException("The input key " + key + " is not a valid input key.");
56 }
57
58}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalRuntimeContext.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalRuntimeContext.java
new file mode 100644
index 00000000..a186b5dd
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalRuntimeContext.java
@@ -0,0 +1,178 @@
1package tools.refinery.store.query.internal;
2
3import static tools.refinery.store.util.CollectionsUtil.filter;
4import static tools.refinery.store.util.CollectionsUtil.map;
5
6import java.lang.reflect.InvocationTargetException;
7import java.util.Iterator;
8import java.util.Optional;
9import java.util.concurrent.Callable;
10
11import org.eclipse.viatra.query.runtime.base.core.NavigationHelperImpl;
12import org.eclipse.viatra.query.runtime.matchers.context.IInputKey;
13import org.eclipse.viatra.query.runtime.matchers.context.IQueryMetaContext;
14import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContext;
15import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContextListener;
16import org.eclipse.viatra.query.runtime.matchers.context.IndexingService;
17import org.eclipse.viatra.query.runtime.matchers.tuple.ITuple;
18import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
19import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
20import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
21import org.eclipse.viatra.query.runtime.matchers.util.Accuracy;
22
23import tools.refinery.store.model.Model;
24import tools.refinery.store.query.view.RelationView;
25
26public class RelationalRuntimeContext implements IQueryRuntimeContext {
27 private final RelationalQueryMetaContext metaContext = new RelationalQueryMetaContext();
28 private final ModelUpdateListener modelUpdateListener;
29 private final Model model;
30
31 public RelationalRuntimeContext(Model model, ModelUpdateListener relationUpdateListener) {
32 this.model = model;
33 this.modelUpdateListener = relationUpdateListener;
34 }
35
36 @Override
37 public IQueryMetaContext getMetaContext() {
38 return metaContext;
39 }
40
41 /**
42 * TODO: check {@link NavigationHelperImpl#coalesceTraversals(Callable)}
43 */
44 @Override
45 public <V> V coalesceTraversals(Callable<V> callable) throws InvocationTargetException {
46 try {
47 return callable.call();
48 } catch (Exception e) {
49 throw new InvocationTargetException(e);
50 }
51 }
52
53 @Override
54 public boolean isCoalescing() {
55 return true;
56 }
57
58 @Override
59 public boolean isIndexed(IInputKey key, IndexingService service) {
60 if(key instanceof RelationView<?> relationalKey) {
61 return this.modelUpdateListener.containsRelationalView(relationalKey);
62 } else {
63 return false;
64 }
65 }
66
67 @Override
68 public void ensureIndexed(IInputKey key, IndexingService service) {
69 if(!isIndexed(key, service)) {
70 throw new IllegalStateException("Engine tries to index a new key " +key);
71 }
72 }
73 @SuppressWarnings("squid:S1452")
74 RelationView<?> checkKey(IInputKey key) {
75 if(key instanceof RelationView) {
76 RelationView<?> relationViewKey = (RelationView<?>) key;
77 if(modelUpdateListener.containsRelationalView(relationViewKey)) {
78 return relationViewKey;
79 } else {
80 throw new IllegalStateException("Query is asking for non-indexed key");
81 }
82 } else {
83 throw new IllegalStateException("Query is asking for non-relational key");
84 }
85 }
86
87 @Override
88 public int countTuples(IInputKey key, TupleMask seedMask, ITuple seed) {
89 RelationView<?> relationalViewKey = checkKey(key);
90 Iterable<Object[]> allObjects = relationalViewKey.getAll(model);
91 Iterable<Object[]> filteredBySeed = filter(allObjects,objectArray -> isMatching(objectArray,seedMask,seed));
92 Iterator<Object[]> iterator = filteredBySeed.iterator();
93 int result = 0;
94 while(iterator.hasNext()) {
95 iterator.next();
96 result++;
97 }
98 return result;
99 }
100
101 @Override
102 public Optional<Long> estimateCardinality(IInputKey key, TupleMask groupMask, Accuracy requiredAccuracy) {
103 return Optional.empty();
104 }
105
106 @Override
107 public Iterable<Tuple> enumerateTuples(IInputKey key, TupleMask seedMask, ITuple seed) {
108 RelationView<?> relationalViewKey = checkKey(key);
109 Iterable<Object[]> allObjects = relationalViewKey.getAll(model);
110 Iterable<Object[]> filteredBySeed = filter(allObjects,objectArray -> isMatching(objectArray,seedMask,seed));
111 return map(filteredBySeed,Tuples::flatTupleOf);
112 }
113
114 private boolean isMatching(Object[] tuple, TupleMask seedMask, ITuple seed) {
115 for(int i=0; i<seedMask.indices.length; i++) {
116 final Object seedElement = seed.get(i);
117 final Object tupleElement = tuple[seedMask.indices[i]];
118 if(!tupleElement.equals(seedElement)) {
119 return false;
120 }
121 }
122 return true;
123 }
124
125 @Override
126 public Iterable<? extends Object> enumerateValues(IInputKey key, TupleMask seedMask, ITuple seed) {
127 return enumerateTuples(key, seedMask, seed);
128 }
129
130 @Override
131 public boolean containsTuple(IInputKey key, ITuple seed) {
132 RelationView<?> relationalViewKey = checkKey(key);
133 return relationalViewKey.get(model,seed.getElements());
134 }
135
136 @Override
137 public void addUpdateListener(IInputKey key, Tuple seed, IQueryRuntimeContextListener listener) {
138 RelationView<?> relationalKey = checkKey(key);
139 this.modelUpdateListener.addListener(relationalKey, seed, listener);
140
141 }
142
143 @Override
144 public void removeUpdateListener(IInputKey key, Tuple seed, IQueryRuntimeContextListener listener) {
145 RelationView<?> relationalKey = checkKey(key);
146 this.modelUpdateListener.removeListener(relationalKey, seed, listener);
147 }
148
149 @Override
150 public Object wrapElement(Object externalElement) {
151 return externalElement;
152 }
153
154 @Override
155 public Object unwrapElement(Object internalElement) {
156 return internalElement;
157 }
158
159 @Override
160 public Tuple wrapTuple(Tuple externalElements) {
161 return externalElements;
162 }
163
164 @Override
165 public Tuple unwrapTuple(Tuple internalElements) {
166 return internalElements;
167 }
168
169 @Override
170 public void ensureWildcardIndexing(IndexingService service) {
171 throw new UnsupportedOperationException();
172 }
173
174 @Override
175 public void executeAfterTraversal(Runnable runnable) throws InvocationTargetException {
176 runnable.run();
177 }
178}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalScope.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalScope.java
new file mode 100644
index 00000000..e8d45356
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/RelationalScope.java
@@ -0,0 +1,43 @@
1package tools.refinery.store.query.internal;
2
3import java.util.Set;
4
5import org.apache.log4j.Logger;
6import org.eclipse.viatra.query.runtime.api.ViatraQueryEngine;
7import org.eclipse.viatra.query.runtime.api.scope.IEngineContext;
8import org.eclipse.viatra.query.runtime.api.scope.IIndexingErrorListener;
9import org.eclipse.viatra.query.runtime.api.scope.QueryScope;
10
11import tools.refinery.store.model.Model;
12import tools.refinery.store.model.Tuple;
13import tools.refinery.store.model.representation.Relation;
14import tools.refinery.store.query.view.RelationView;
15
16public class RelationalScope extends QueryScope{
17 private final Model model;
18 private final ModelUpdateListener updateListener;
19
20 public RelationalScope(Model model, Set<RelationView<?>> relationViews) {
21 this.model = model;
22 this.updateListener = new ModelUpdateListener(relationViews);
23 //this.changeListener = new
24 }
25
26 public <D> void processUpdate(Relation<D> relation, Tuple key, D oldValue, D newValue) {
27 updateListener.addUpdate(relation, key, oldValue, newValue);
28 }
29
30 public boolean hasChange() {
31 return updateListener.hasChange();
32 }
33
34 public void flush() {
35 updateListener.flush();
36 }
37
38 @Override
39 protected IEngineContext createEngineContext(ViatraQueryEngine engine, IIndexingErrorListener errorListener,
40 Logger logger) {
41 return new RelationalEngineContext(model, updateListener);
42 }
43}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdate.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdate.java
new file mode 100644
index 00000000..7d1a4c05
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdate.java
@@ -0,0 +1,34 @@
1package tools.refinery.store.query.internal;
2
3import java.util.Arrays;
4import java.util.Objects;
5
6record ViewUpdate (Object[] tuple, boolean isInsertion) {
7
8 @Override
9 public int hashCode() {
10 final int prime = 31;
11 int result = 1;
12 result = prime * result + Arrays.deepHashCode(tuple);
13 result = prime * result + Objects.hash(isInsertion);
14 return result;
15 }
16
17 @Override
18 public boolean equals(Object obj) {
19 if (this == obj)
20 return true;
21 if (obj == null)
22 return false;
23 if (getClass() != obj.getClass())
24 return false;
25 ViewUpdate other = (ViewUpdate) obj;
26 return isInsertion == other.isInsertion && Arrays.deepEquals(tuple, other.tuple);
27 }
28
29 @Override
30 public String toString() {
31 return "ViewUpdate [" + Arrays.toString(tuple) + "insertion= "+this.isInsertion+"]";
32 }
33
34}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdateBuffer.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdateBuffer.java
new file mode 100644
index 00000000..6bc4c96a
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdateBuffer.java
@@ -0,0 +1,46 @@
1package tools.refinery.store.query.internal;
2
3import java.util.ArrayList;
4import java.util.Arrays;
5import java.util.List;
6
7import tools.refinery.store.model.Tuple;
8
9public class ViewUpdateBuffer<D> {
10 protected final ViewUpdateTranslator<D> updateListener;
11 protected final List<ViewUpdate> buffer = new ArrayList<>();
12
13 public ViewUpdateBuffer(ViewUpdateTranslator<D> updateListener) {
14 this.updateListener = updateListener;
15 }
16
17 public ViewUpdateTranslator<D> getUpdateListener() {
18 return updateListener;
19 }
20
21 public boolean hasChange() {
22 return ! buffer.isEmpty();
23 }
24
25 public void addChange(Tuple tuple, D oldValue, D newValue) {
26 if(oldValue != newValue) {
27 Object[] oldTuple = updateListener.isMatching(tuple, oldValue);
28 Object[] newTuple = updateListener.isMatching(tuple, newValue);
29 if(!Arrays.equals(oldTuple, newTuple)) {
30 if(oldTuple != null) {
31 buffer.add(new ViewUpdate(oldTuple, false));
32 }
33 if(newTuple != null) {
34 buffer.add(new ViewUpdate(newTuple, true));
35 }
36 }
37 }
38 }
39
40 public void flush() {
41 for (ViewUpdate viewChange : buffer) {
42 updateListener.processChange(viewChange);
43 }
44 buffer.clear();
45 }
46}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdateTranslator.java b/subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdateTranslator.java
new file mode 100644
index 00000000..1c210c5f
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/internal/ViewUpdateTranslator.java
@@ -0,0 +1,57 @@
1package tools.refinery.store.query.internal;
2
3import java.util.Objects;
4
5import org.eclipse.viatra.query.runtime.matchers.context.IQueryRuntimeContextListener;
6import org.eclipse.viatra.query.runtime.matchers.tuple.ITuple;
7import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
8
9import tools.refinery.store.model.Tuple;
10import tools.refinery.store.query.view.RelationView;
11
12public class ViewUpdateTranslator<D> {
13 final RelationView<D> key;
14 final ITuple filter;
15 final IQueryRuntimeContextListener listener;
16
17 public ViewUpdateTranslator(RelationView<D> key, ITuple filter, IQueryRuntimeContextListener listener) {
18 super();
19 this.key = key;
20 this.filter = filter;
21 this.listener = listener;
22 }
23
24 public void processChange(ViewUpdate change) {
25 listener.update(key, Tuples.flatTupleOf(change.tuple()), change.isInsertion());
26 }
27
28 public Object[] isMatching(Tuple tuple, D value){
29 return isMatching(key.getWrappedKey().transform(tuple, value), filter);
30 }
31 @SuppressWarnings("squid:S1168")
32 private Object[] isMatching(Object[] tuple, ITuple filter) {
33 for(int i = 0; i<filter.getSize(); i++) {
34 final Object filterObject = filter.get(i);
35 if(filterObject != null && !filterObject.equals(tuple[i])) {
36 return null;
37 }
38 }
39 return tuple;
40 }
41
42 @Override
43 public int hashCode() {
44 return Objects.hash(filter, key, listener);
45 }
46
47 @Override
48 public boolean equals(Object obj) {
49 if (this == obj)
50 return true;
51 if (!(obj instanceof ViewUpdateTranslator))
52 return false;
53 ViewUpdateTranslator<?> other = (ViewUpdateTranslator<?>) obj;
54 return Objects.equals(filter, other.filter) && Objects.equals(key, other.key)
55 && Objects.equals(listener, other.listener);
56 }
57}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/view/FilteredRelationView.java b/subprojects/store/src/main/java/tools/refinery/store/query/view/FilteredRelationView.java
new file mode 100644
index 00000000..3531195a
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/view/FilteredRelationView.java
@@ -0,0 +1,48 @@
1package tools.refinery.store.query.view;
2
3import java.util.function.BiPredicate;
4
5import tools.refinery.store.model.Model;
6import tools.refinery.store.model.Tuple;
7import tools.refinery.store.model.Tuple.Tuple1;
8import tools.refinery.store.model.representation.Relation;
9
10public class FilteredRelationView<D> extends RelationView<D>{
11 private final BiPredicate<Tuple,D> predicate;
12
13 public FilteredRelationView(Relation<D> representation, BiPredicate<Tuple,D> predicate) {
14 super(representation);
15 this.predicate = predicate;
16 }
17 @Override
18 protected Object[] forwardMap(Tuple key, D value) {
19 return toTuple1Array(key);
20 }
21 @Override
22 public boolean get(Model model, Object[] tuple) {
23 int[] content = new int[tuple.length];
24 for(int i = 0; i<tuple.length; i++) {
25 content[i] =((Tuple1)tuple[i]).get(0);
26 }
27 Tuple key = Tuple.of(content);
28 D value = model.get(representation, key);
29 return filter(key, value);
30 }
31
32 public static Object[] toTuple1Array(Tuple t) {
33 Object[] result = new Object[t.getSize()];
34 for(int i = 0; i<t.getSize(); i++) {
35 result[i] = Tuple.of(t.get(i));
36 }
37 return result;
38 }
39
40 @Override
41 public int getArity() {
42 return this.representation.getArity();
43 }
44 @Override
45 protected boolean filter(Tuple key, D value) {
46 return this.predicate.test(key, value);
47 }
48}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/view/FunctionalRelationView.java b/subprojects/store/src/main/java/tools/refinery/store/query/view/FunctionalRelationView.java
new file mode 100644
index 00000000..db9ba4b8
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/view/FunctionalRelationView.java
@@ -0,0 +1,50 @@
1package tools.refinery.store.query.view;
2
3import tools.refinery.store.model.Model;
4import tools.refinery.store.model.Tuple;
5import tools.refinery.store.model.Tuple.Tuple1;
6import tools.refinery.store.model.representation.Relation;
7
8public class FunctionalRelationView<D> extends RelationView<D> {
9
10 public FunctionalRelationView(Relation<D> representation) {
11 super(representation);
12 }
13
14 @Override
15 protected boolean filter(Tuple key, D value) {
16 return true;
17 }
18
19 @Override
20 protected Object[] forwardMap(Tuple key, D value) {
21 return toTuple1ArrayPlusValue(key, value);
22 }
23
24 @Override
25 public boolean get(Model model, Object[] tuple) {
26 int[] content = new int[tuple.length-1];
27 for(int i = 0; i<tuple.length-1; i++) {
28 content[i] =((Tuple1)tuple[i]).get(0);
29 }
30 Tuple key = Tuple.of(content);
31 @SuppressWarnings("unchecked")
32 D valueInTuple = (D) tuple[tuple.length-1];
33 D valueInMap = model.get(representation, key);
34 return valueInTuple.equals(valueInMap);
35 }
36
37 public static <D> Object[] toTuple1ArrayPlusValue(Tuple t, D value) {
38 Object[] result = new Object[t.getSize()+1];
39 for(int i = 0; i<t.getSize(); i++) {
40 result[i] = Tuple.of(t.get(i));
41 }
42 result[t.getSize()] = value;
43 return result;
44 }
45
46 @Override
47 public int getArity() {
48 return this.representation.getArity()+1;
49 }
50}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/view/KeyOnlyRelationView.java b/subprojects/store/src/main/java/tools/refinery/store/query/view/KeyOnlyRelationView.java
new file mode 100644
index 00000000..6fa387a1
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/view/KeyOnlyRelationView.java
@@ -0,0 +1,16 @@
1package tools.refinery.store.query.view;
2
3import tools.refinery.store.model.Tuple;
4import tools.refinery.store.model.representation.Relation;
5
6public class KeyOnlyRelationView extends FilteredRelationView<Boolean>{
7
8 public KeyOnlyRelationView(Relation<Boolean> representation) {
9 super(representation, (k,v)->true);
10 }
11 @Override
12 protected boolean filter(Tuple key, Boolean value) {
13 return !value.equals(representation.getDefaultValue());
14 }
15
16}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/view/RelationView.java b/subprojects/store/src/main/java/tools/refinery/store/query/view/RelationView.java
new file mode 100644
index 00000000..fd55eed4
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/view/RelationView.java
@@ -0,0 +1,85 @@
1package tools.refinery.store.query.view;
2
3import java.util.Objects;
4
5import org.eclipse.viatra.query.runtime.matchers.context.common.BaseInputKeyWrapper;
6
7import tools.refinery.store.map.CursorAsIterator;
8import tools.refinery.store.model.Model;
9import tools.refinery.store.model.Tuple;
10import tools.refinery.store.model.representation.Relation;
11
12/**
13 * Represents a view of a {@link Relation} that can be queried.
14 *
15 * @author Oszkar Semerath
16 *
17 * @param <D>
18 */
19public abstract class RelationView<D> extends BaseInputKeyWrapper<RelationView<D>> {
20 protected final Relation<D> representation;
21
22 protected RelationView(Relation<D> representation) {
23 super(null);
24 this.wrappedKey = this;
25 this.representation = representation;
26 }
27
28 @Override
29 public String getPrettyPrintableName() {
30 return representation.getName();
31 }
32
33 @Override
34 public String getStringID() {
35 return representation.getName() + this.getClass().getName();
36 }
37
38 public Relation<D> getRepresentation() {
39 return representation;
40 }
41
42 @Override
43 public boolean isEnumerable() {
44 return true;
45 }
46
47 protected abstract boolean filter(Tuple key, D value);
48
49 protected abstract Object[] forwardMap(Tuple key, D value);
50
51 public abstract boolean get(Model model, Object[] tuple);
52
53 @SuppressWarnings("squid:S1168")
54 public Object[] transform(Tuple tuple, D value) {
55 if (filter(tuple, value)) {
56 return forwardMap(tuple, value);
57 } else
58 return null;
59 }
60
61 public Iterable<Object[]> getAll(Model model) {
62 return (() -> new CursorAsIterator<>(model.getAll(representation), (k, v) -> forwardMap(k, v),
63 (k, v) -> filter(k, v)));
64 }
65
66 @Override
67 public int hashCode() {
68 final int prime = 31;
69 int result = 1;
70 result = prime * result + Objects.hash(representation);
71 return result;
72 }
73
74 @Override
75 public boolean equals(Object obj) {
76 if (this == obj)
77 return true;
78 if (!(obj instanceof RelationView))
79 return false;
80 @SuppressWarnings("unchecked")
81 RelationView<D> other = ((RelationView<D>) obj);
82 return Objects.equals(representation, other.representation);
83 }
84
85}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/util/CollectionsUtil.java b/subprojects/store/src/main/java/tools/refinery/store/util/CollectionsUtil.java
new file mode 100644
index 00000000..841d0dfa
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/util/CollectionsUtil.java
@@ -0,0 +1,72 @@
1package tools.refinery.store.util;
2
3import java.util.Iterator;
4import java.util.NoSuchElementException;
5import java.util.function.Function;
6import java.util.function.Predicate;
7
8public final class CollectionsUtil {
9 private CollectionsUtil() {
10 throw new UnsupportedOperationException();
11 }
12
13 public static <S,T> Iterator<T> map(Iterator<S> source, Function<S, T> transformation) {
14 return new Iterator<T>() {
15
16 @Override
17 public boolean hasNext() {
18 return source.hasNext();
19 }
20
21 @Override
22 public T next() {
23 return transformation.apply(source.next());
24 }
25 };
26 }
27
28 public static <S,T> Iterable<T> map(Iterable<S> source, Function<S, T> transformation) {
29 return (()->map(source.iterator(),transformation));
30 }
31
32 public static <T> Iterator<T> filter(Iterator<T> source, Predicate<T> condition) {
33 return new Iterator<T>() {
34 T internalNext = move();
35 boolean internalHasNext;
36
37 private T move() {
38 internalHasNext = source.hasNext();
39 if(internalHasNext) {
40 internalNext = source.next();
41 }
42 while(internalHasNext && !condition.test(internalNext)) {
43 internalHasNext = source.hasNext();
44 if(internalHasNext) {
45 internalNext = source.next();
46 }
47 }
48 return internalNext;
49 }
50
51 @Override
52 public boolean hasNext() {
53 return internalHasNext;
54 }
55
56 @Override
57 public T next() {
58 if(!internalHasNext) {
59 throw new NoSuchElementException();
60 } else {
61 T result = internalNext;
62 move();
63 return result;
64 }
65 }
66 };
67 }
68
69 public static <T> Iterable<T> filter(Iterable<T> source, Predicate<T> condition) {
70 return (()->filter(source.iterator(),condition));
71 }
72}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java
new file mode 100644
index 00000000..f0d5d927
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java
@@ -0,0 +1,22 @@
1package tools.refinery.store.map.tests;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4
5import org.junit.jupiter.api.Test;
6
7import tools.refinery.store.map.VersionedMapStore;
8import tools.refinery.store.map.VersionedMapStoreImpl;
9import tools.refinery.store.model.Tuple;
10import tools.refinery.store.model.TupleHashProvider;
11
12class MapUnitTests {
13 @Test
14 void defaultTest() {
15 VersionedMapStore<Tuple, Boolean> store = new VersionedMapStoreImpl<Tuple, Boolean>(TupleHashProvider.singleton(), false);
16 var map = store.createMap();
17 var out1 = map.put(Tuple.of(0), true);
18 assertEquals(false, out1);
19 var out2 = map.put(Tuple.of(1), true);
20 assertEquals(false, out2);
21 }
22}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java
new file mode 100644
index 00000000..1f9d022f
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java
@@ -0,0 +1,96 @@
1package tools.refinery.store.map.tests.fuzz;
2
3import static org.junit.jupiter.api.Assertions.fail;
4
5import java.util.Random;
6import java.util.stream.Stream;
7
8import org.junit.jupiter.api.Tag;
9import org.junit.jupiter.api.Timeout;
10import org.junit.jupiter.params.ParameterizedTest;
11import org.junit.jupiter.params.provider.Arguments;
12import org.junit.jupiter.params.provider.MethodSource;
13
14import tools.refinery.store.map.ContinousHashProvider;
15import tools.refinery.store.map.VersionedMapStore;
16import tools.refinery.store.map.VersionedMapStoreImpl;
17import tools.refinery.store.map.internal.VersionedMapImpl;
18import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
19import tools.refinery.store.map.tests.utils.MapTestEnvironment;
20
21class CommitFuzzTest {
22 private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
23 boolean evilHash) {
24 String[] values = MapTestEnvironment.prepareValues(maxValue);
25 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
26
27 VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
28 VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap();
29 MapTestEnvironment<Integer, String> e = new MapTestEnvironment<Integer, String>(sut);
30
31 Random r = new Random(seed);
32
33 iterativeRandomPutsAndCommits(scenario, steps, maxKey, values, e, r, commitFrequency);
34 }
35
36 private void iterativeRandomPutsAndCommits(String scenario, int steps, int maxKey, String[] values,
37 MapTestEnvironment<Integer, String> e, Random r, int commitFrequency) {
38 int stopAt = -1;
39 for (int i = 0; i < steps; i++) {
40 int index = i + 1;
41 int nextKey = r.nextInt(maxKey);
42 String nextValue = values[r.nextInt(values.length)];
43 if (index == stopAt) {
44 System.out.println("issue!");
45 System.out.println("State before:");
46 e.printComparison();
47 e.sut.prettyPrint();
48 System.out.println("Next: put(" + nextKey + "," + nextValue + ")");
49 }
50 try {
51 e.put(nextKey, nextValue);
52 if (index == stopAt) {
53 e.sut.prettyPrint();
54 }
55 e.checkEquivalence(scenario + ":" + index);
56 } catch (Exception exception) {
57 exception.printStackTrace();
58 fail(scenario + ":" + index + ": exception happened: " + exception);
59 }
60 MapTestEnvironment.printStatus(scenario, index, steps, null);
61 if (index % commitFrequency == 0) {
62 e.sut.commit();
63 }
64 }
65 }
66
67 @ParameterizedTest(name = "Commit {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
68 @MethodSource
69 @Timeout(value = 10)
70 @Tag("fuzz")
71 void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
72 boolean evilHash) {
73 runFuzzTest("CommitS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
74 commitFrequency, evilHash);
75 }
76
77 static Stream<Arguments> parametrizedFastFuzz() {
78 return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
79 new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
80 new Object[] { false, true });
81 }
82
83 @ParameterizedTest(name = "Commit {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
84 @MethodSource
85 @Tag("fuzz")
86 @Tag("slow")
87 void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
88 boolean evilHash) {
89 runFuzzTest("CommitS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
90 commitFrequency, evilHash);
91 }
92
93 static Stream<Arguments> parametrizedSlowFuzz() {
94 return FuzzTestUtils.changeStepCount(parametrizedFastFuzz(), 1);
95 }
96}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java
new file mode 100644
index 00000000..263cb2cd
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java
@@ -0,0 +1,143 @@
1package tools.refinery.store.map.tests.fuzz;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4import static org.junit.jupiter.api.Assertions.fail;
5
6import java.util.AbstractMap.SimpleEntry;
7import java.util.Collections;
8import java.util.LinkedList;
9import java.util.List;
10import java.util.Random;
11import java.util.stream.Stream;
12
13import org.junit.jupiter.api.Tag;
14import org.junit.jupiter.api.Timeout;
15import org.junit.jupiter.params.ParameterizedTest;
16import org.junit.jupiter.params.provider.Arguments;
17import org.junit.jupiter.params.provider.MethodSource;
18
19import tools.refinery.store.map.ContinousHashProvider;
20import tools.refinery.store.map.Cursor;
21import tools.refinery.store.map.VersionedMap;
22import tools.refinery.store.map.VersionedMapStore;
23import tools.refinery.store.map.VersionedMapStoreImpl;
24import tools.refinery.store.map.internal.VersionedMapImpl;
25import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
26import tools.refinery.store.map.tests.utils.MapTestEnvironment;
27
28class ContentEqualsFuzzTest {
29 private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
30 boolean evilHash) {
31 String[] values = MapTestEnvironment.prepareValues(maxValue);
32 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
33
34 Random r = new Random(seed);
35
36 iterativeRandomPutsAndCommitsThenCompare(scenario, chp, steps, maxKey, values, r, commitFrequency);
37 }
38
39 private void iterativeRandomPutsAndCommitsThenCompare(String scenario, ContinousHashProvider<Integer> chp, int steps, int maxKey, String[] values, Random r, int commitFrequency) {
40
41 VersionedMapStore<Integer, String> store1 = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
42 VersionedMap<Integer, String> sut1 = store1.createMap();
43
44 // Fill one map
45 for (int i = 0; i < steps; i++) {
46 int index1 = i + 1;
47 int nextKey = r.nextInt(maxKey);
48 String nextValue = values[r.nextInt(values.length)];
49 try {
50 sut1.put(nextKey, nextValue);
51 } catch (Exception exception) {
52 exception.printStackTrace();
53 fail(scenario + ":" + index1 + ": exception happened: " + exception);
54 }
55 MapTestEnvironment.printStatus(scenario, index1, steps, "Fill");
56 if (index1 % commitFrequency == 0) {
57 sut1.commit();
58 }
59 }
60
61 // Get the content of the first map
62 List<SimpleEntry<Integer, String>> content = new LinkedList<>();
63 Cursor<Integer, String> cursor = sut1.getAll();
64 while (cursor.move()) {
65 content.add(new SimpleEntry<>(cursor.getKey(), cursor.getValue()));
66 }
67
68 // Randomize the order of the content
69 Collections.shuffle(content, r);
70
71 VersionedMapStore<Integer, String> store2 = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
72 VersionedMap<Integer, String> sut2 = store2.createMap();
73 int index2 = 1;
74 for (SimpleEntry<Integer, String> entry : content) {
75 sut2.put(entry.getKey(), entry.getValue());
76 if(index2++%commitFrequency == 0)
77 sut2.commit();
78 }
79
80 // Check the integrity of the maps
81 ((VersionedMapImpl<Integer,String>) sut1).checkIntegrity();
82 ((VersionedMapImpl<Integer,String>) sut2).checkIntegrity();
83
84// // Compare the two maps
85 // By size
86 assertEquals(sut1.getSize(), content.size());
87 assertEquals(sut2.getSize(), content.size());
88
89
90
91 // By cursors
92 Cursor<Integer, String> cursor1 = sut1.getAll();
93 Cursor<Integer, String> cursor2 = sut2.getAll();
94 int index3 = 1;
95 boolean canMove = true;
96 do{
97 boolean canMove1 = cursor1.move();
98 boolean canMove2 = cursor2.move();
99 assertEquals(canMove1, canMove2, scenario + ":" + index3 +" Cursors stopped at different times!");
100 assertEquals(cursor1.getKey(), cursor2.getKey(), scenario + ":" + index3 +" Cursors have different keys!");
101 assertEquals(cursor1.getValue(), cursor2.getValue(), scenario + ":" + index3 +" Cursors have different values!");
102
103 canMove = canMove1;
104 MapTestEnvironment.printStatus(scenario, index3++, content.size(), "Compare");
105 } while (canMove);
106
107 // By hashcode
108 assertEquals(sut1.hashCode(), sut2.hashCode(), "Hash codes are not equal!");
109
110 // By equals
111 assertEquals(sut1, sut2, "Maps are not equals");
112 }
113
114 @ParameterizedTest(name = "Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
115 @MethodSource
116 @Timeout(value = 10)
117 @Tag("fuzz")
118 void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
119 boolean evilHash) {
120 runFuzzTest("CompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
121 commitFrequency, evilHash);
122 }
123
124 static Stream<Arguments> parametrizedFastFuzz() {
125 return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
126 new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
127 new Object[] { false, true });
128 }
129
130 @ParameterizedTest(name = "Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
131 @MethodSource
132 @Tag("fuzz")
133 @Tag("slow")
134 void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
135 boolean evilHash) {
136 runFuzzTest("CompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
137 commitFrequency, evilHash);
138 }
139
140 static Stream<Arguments> parametrizedSlowFuzz() {
141 return FuzzTestUtils.changeStepCount(parametrizedFastFuzz(), 1);
142 }
143}
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
new file mode 100644
index 00000000..e6334224
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java
@@ -0,0 +1,117 @@
1package tools.refinery.store.map.tests.fuzz;
2
3import static org.junit.jupiter.api.Assertions.fail;
4
5import java.util.Random;
6import java.util.stream.Stream;
7
8import org.junit.jupiter.api.Tag;
9import org.junit.jupiter.api.Timeout;
10import org.junit.jupiter.params.ParameterizedTest;
11import org.junit.jupiter.params.provider.Arguments;
12import org.junit.jupiter.params.provider.MethodSource;
13
14import tools.refinery.store.map.ContinousHashProvider;
15import tools.refinery.store.map.DiffCursor;
16import tools.refinery.store.map.VersionedMapStore;
17import tools.refinery.store.map.VersionedMapStoreImpl;
18import tools.refinery.store.map.internal.VersionedMapImpl;
19import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
20import tools.refinery.store.map.tests.utils.MapTestEnvironment;
21
22class DiffCursorFuzzTest {
23 private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
24 boolean evilHash) {
25 String[] values = MapTestEnvironment.prepareValues(maxValue);
26 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
27
28 VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
29 iterativeRandomPutsAndCommitsThenDiffcursor(scenario, store, steps, maxKey, values, seed, commitFrequency);
30 }
31
32 private void iterativeRandomPutsAndCommitsThenDiffcursor(String scenario, VersionedMapStore<Integer, String> store,
33 int steps, int maxKey, String[] values, int seed, int commitFrequency) {
34 // 1. build a map with versions
35 Random r = new Random(seed);
36 VersionedMapImpl<Integer, String> versioned = (VersionedMapImpl<Integer, String>) store.createMap();
37 int largestCommit = -1;
38
39 for (int i = 0; i < steps; i++) {
40 int index = i + 1;
41 int nextKey = r.nextInt(maxKey);
42 String nextValue = values[r.nextInt(values.length)];
43 try {
44 versioned.put(nextKey, nextValue);
45 } catch (Exception exception) {
46 exception.printStackTrace();
47 fail(scenario + ":" + index + ": exception happened: " + exception);
48 }
49 if (index % commitFrequency == 0) {
50 long version = versioned.commit();
51 largestCommit = (int) version;
52 }
53 if (index % 10000 == 0)
54 System.out.println(scenario + ":" + index + "/" + steps + " building finished");
55 }
56 // 2. create a non-versioned map,
57 VersionedMapImpl<Integer, String> moving = (VersionedMapImpl<Integer, String>) store.createMap();
58 Random r2 = new Random(seed + 1);
59
60 final int diffTravelFrequency = commitFrequency * 2;
61 for (int i = 0; i < steps; i++) {
62 int index = i + 1;
63 if (index % diffTravelFrequency == 0) {
64 // difftravel
65 long travelToVersion = r2.nextInt(largestCommit + 1);
66 DiffCursor<Integer, String> diffCursor = moving.getDiffCursor(travelToVersion);
67 moving.putAll(diffCursor);
68
69 } else {
70 // random puts
71 int nextKey = r2.nextInt(maxKey);
72 String nextValue = values[r2.nextInt(values.length)];
73 try {
74 moving.put(nextKey, nextValue);
75 } catch (Exception exception) {
76 exception.printStackTrace();
77 fail(scenario + ":" + index + ": exception happened: " + exception);
78 }
79 if (index % commitFrequency == 0) {
80 versioned.commit();
81 }
82 if (index % 10000 == 0)
83 System.out.println(scenario + ":" + index + "/" + steps + " building finished");
84 }
85 }
86
87 }
88
89 @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
90 @MethodSource
91 @Timeout(value = 10)
92 @Tag("fuzz")
93 void parametrizedFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
94 boolean evilHash) {
95 runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
96 noKeys, noValues, commitFrequency, evilHash);
97 }
98
99 static Stream<Arguments> parametrizedFuzz() {
100 return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
101 new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
102 new Object[] { false, true });
103 }
104 @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
105 @MethodSource
106 @Tag("fuzz")
107 @Tag("slow")
108 void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
109 boolean evilHash) {
110 runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
111 commitFrequency, evilHash);
112 }
113
114 static Stream<Arguments> parametrizedSlowFuzz() {
115 return FuzzTestUtils.changeStepCount(parametrizedFuzz(), 1);
116 }
117}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java
new file mode 100644
index 00000000..1ab431a8
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java
@@ -0,0 +1,97 @@
1package tools.refinery.store.map.tests.fuzz;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4import static org.junit.jupiter.api.Assertions.fail;
5
6import java.util.Collections;
7import java.util.LinkedList;
8import java.util.List;
9import java.util.stream.Stream;
10
11import org.junit.jupiter.api.Tag;
12import org.junit.jupiter.api.Timeout;
13import org.junit.jupiter.params.ParameterizedTest;
14import org.junit.jupiter.params.provider.Arguments;
15import org.junit.jupiter.params.provider.MethodSource;
16
17import tools.refinery.store.map.ContinousHashProvider;
18import tools.refinery.store.map.VersionedMapStore;
19import tools.refinery.store.map.VersionedMapStoreImpl;
20import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
21import tools.refinery.store.map.tests.utils.MapTestEnvironment;
22
23class MultiThreadFuzzTest {
24 public static final int noThreads = 32;
25
26 private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
27 boolean evilHash) {
28 String[] values = MapTestEnvironment.prepareValues(maxValue);
29 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
30
31 VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
32
33 // initialize runnables
34 MultiThreadTestRunnable[] runnables = new MultiThreadTestRunnable[noThreads];
35 for(int i = 0; i<noThreads; i++) {
36 runnables[i] = new MultiThreadTestRunnable(scenario+"-T"+(i+1), store, steps, maxKey, values, seed, commitFrequency);
37 }
38
39 // initialize threads
40 Thread[] threads = new Thread[noThreads];
41 for(int i = 0; i<noThreads; i++) {
42 threads[i] = new Thread(runnables[i]);
43 }
44
45 // start threads;
46 for(int i = 0; i<noThreads; i++) {
47 threads[i].start();
48 }
49
50 // wait all the threads;
51 for(int i = 0; i<noThreads; i++) {
52 try {
53 threads[i].join();
54 } catch (InterruptedException e) {
55 fail("Thread "+i+" interrupted.");
56 }
57 }
58
59 // collect errors
60 List<Throwable> errors = new LinkedList<>();
61 for(int i = 0; i<noThreads; i++) {
62 errors.addAll(runnables[i].getErrors());
63 }
64
65 assertEquals(Collections.EMPTY_LIST, errors);
66 }
67
68 @ParameterizedTest(name = "Multithread {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
69 @MethodSource
70 @Timeout(value = 10)
71 @Tag("fuzz")
72 void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
73 boolean evilHash) {
74 runFuzzTest("MultithreadS" + steps + "K" + noKeys + "V" + noValues + "CF" + commitFrequency + "s" + seed, seed, steps, noKeys, noValues,
75 commitFrequency, evilHash);
76 }
77
78 static Stream<Arguments> parametrizedFastFuzz() {
79 return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
80 new Object[] { 2, 3 }, new Object[] { 10, 100 }, new Object[] { 1, 2, 3 },
81 new Object[] { false, true });
82 }
83
84 @ParameterizedTest(name = "Multithread {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
85 @MethodSource
86 @Tag("fuzz")
87 @Tag("slow")
88 void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
89 boolean evilHash) {
90 runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
91 commitFrequency, evilHash);
92 }
93
94 static Stream<Arguments> parametrizedSlowFuzz() {
95 return FuzzTestUtils.changeStepCount(RestoreFuzzTest.parametrizedFastFuzz(), 1);
96 }
97}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java
new file mode 100644
index 00000000..f77f9ee5
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java
@@ -0,0 +1,101 @@
1package tools.refinery.store.map.tests.fuzz;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.HashMap;
6import java.util.LinkedList;
7import java.util.List;
8import java.util.Map;
9import java.util.Random;
10
11import tools.refinery.store.map.VersionedMapStore;
12import tools.refinery.store.map.internal.VersionedMapImpl;
13import tools.refinery.store.map.tests.utils.MapTestEnvironment;
14
15public class MultiThreadTestRunnable implements Runnable {
16 String scenario;
17 VersionedMapStore<Integer, String> store;
18 int steps;
19 int maxKey;
20 String[] values;
21 int seed;
22 int commitFrequency;
23 List<Throwable> errors = new LinkedList<>();
24
25 public MultiThreadTestRunnable(String scenario, VersionedMapStore<Integer, String> store, int steps,
26 int maxKey, String[] values, int seed, int commitFrequency) {
27 super();
28 this.scenario = scenario;
29 this.store = store;
30 this.steps = steps;
31 this.maxKey = maxKey;
32 this.values = values;
33 this.seed = seed;
34 this.commitFrequency = commitFrequency;
35 }
36
37 private void logAndThrowError(String message) {
38 AssertionError error = new AssertionError(message);
39 errors.add(error);
40 }
41
42 public List<Throwable> getErrors() {
43 return errors;
44 }
45
46 @Override
47 public void run() {
48 // 1. build a map with versions
49 Random r = new Random(seed);
50 VersionedMapImpl<Integer, String> versioned = (VersionedMapImpl<Integer, String>) store.createMap();
51 Map<Integer, Long> index2Version = new HashMap<>();
52
53 for (int i = 0; i < steps; i++) {
54 int index = i + 1;
55 int nextKey = r.nextInt(maxKey);
56 String nextValue = values[r.nextInt(values.length)];
57 try {
58 versioned.put(nextKey, nextValue);
59 } catch (Exception exception) {
60 exception.printStackTrace();
61 logAndThrowError(scenario + ":" + index + ": exception happened: " + exception);
62 }
63 if (index % commitFrequency == 0) {
64 long version = versioned.commit();
65 index2Version.put(i, version);
66 }
67 MapTestEnvironment.printStatus(scenario, index, steps, "building");
68 }
69 // 2. create a non-versioned
70 VersionedMapImpl<Integer, String> reference = (VersionedMapImpl<Integer, String>) store.createMap();
71 r = new Random(seed);
72 Random r2 = new Random(seed+1);
73
74 for (int i = 0; i < steps; i++) {
75 int index = i + 1;
76 int nextKey = r.nextInt(maxKey);
77 String nextValue = values[r.nextInt(values.length)];
78 try {
79 reference.put(nextKey, nextValue);
80 } catch (Exception exception) {
81 exception.printStackTrace();
82 logAndThrowError(scenario + ":" + index + ": exception happened: " + exception);
83 }
84 // go back to an existing state and compare to the reference
85 if (index % (commitFrequency) == 0) {
86 versioned.restore(index2Version.get(i));
87 MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference, versioned,errors);
88
89 // go back to a random state (probably created by another thread)
90 List<Long> states = new ArrayList<>(store.getStates());
91 Collections.shuffle(states, r2);
92 for(Long state : states.subList(0, Math.min(states.size(), 100))) {
93 versioned.restore(state);
94 }
95 versioned.restore(index2Version.get(i));
96 }
97
98 MapTestEnvironment.printStatus(scenario, index, steps, "comparison");
99 }
100 }
101}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java
new file mode 100644
index 00000000..d40c49c4
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java
@@ -0,0 +1,92 @@
1package tools.refinery.store.map.tests.fuzz;
2
3import static org.junit.jupiter.api.Assertions.fail;
4
5import java.util.Random;
6import java.util.stream.Stream;
7
8import org.junit.jupiter.api.Tag;
9import org.junit.jupiter.api.Timeout;
10import org.junit.jupiter.params.ParameterizedTest;
11import org.junit.jupiter.params.provider.Arguments;
12import org.junit.jupiter.params.provider.MethodSource;
13
14import tools.refinery.store.map.ContinousHashProvider;
15import tools.refinery.store.map.VersionedMapStore;
16import tools.refinery.store.map.VersionedMapStoreImpl;
17import tools.refinery.store.map.internal.VersionedMapImpl;
18import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
19import tools.refinery.store.map.tests.utils.MapTestEnvironment;
20
21class MutableFuzzTest {
22 private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean evilHash) {
23 String[] values = MapTestEnvironment.prepareValues(maxValue);
24 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
25
26 VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
27 VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap();
28 MapTestEnvironment<Integer, String> e = new MapTestEnvironment<Integer, String>(sut);
29
30 Random r = new Random(seed);
31
32 iterativeRandomPuts(scenario, steps, maxKey, values, e, r);
33 }
34
35 private void iterativeRandomPuts(String scenario, int steps, int maxKey, String[] values,
36 MapTestEnvironment<Integer, String> e, Random r) {
37 int stopAt = -1;
38 for (int i = 0; i < steps; i++) {
39 int index = i + 1;
40 int nextKey = r.nextInt(maxKey);
41 String nextValue = values[r.nextInt(values.length)];
42 if (index == stopAt) {
43 System.out.println("issue!");
44 System.out.println("State before:");
45 e.printComparison();
46 e.sut.prettyPrint();
47 System.out.println("Next: put(" + nextKey + "," + nextValue + ")");
48 }
49 try {
50 e.put(nextKey, nextValue);
51 if (index == stopAt) {
52 e.sut.prettyPrint();
53 }
54 e.checkEquivalence(scenario + ":" + index);
55 } catch (Exception exception) {
56 exception.printStackTrace();
57 fail(scenario + ":" + index + ": exception happened: " + exception);
58 }
59 MapTestEnvironment.printStatus(scenario, index, steps, null);
60 }
61 }
62
63 @ParameterizedTest(name = "Mutable {index}/{0} Steps={1} Keys={2} Values={3} seed={4} evil-hash={5}")
64 @MethodSource
65 @Timeout(value = 10)
66 @Tag("fuzz")
67 void parametrizedFuzz(int test, int steps, int noKeys, int noValues, int seed, boolean evilHash) {
68 runFuzzTest(
69 "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed + "H" + (evilHash ? "Evil" : "Normal"),
70 seed, steps, noKeys, noValues, evilHash);
71 }
72
73 static Stream<Arguments> parametrizedFuzz() {
74 return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT },
75 new Object[] { 3, 32, 32 * 32, 32 * 32 * 32 * 32 }, new Object[] { 2, 3 }, new Object[] { 1, 2, 3 },
76 new Object[] { false, true });
77 }
78
79 @ParameterizedTest(name = "Mutable {index}/{0} Steps={1} Keys={2} Values={3} seed={4} evil-hash={5}")
80 @MethodSource
81 @Tag("fuzz")
82 @Tag("slow")
83 void parametrizedSlowFuzz(int test, int steps, int noKeys, int noValues, int seed, boolean evilHash) {
84 runFuzzTest(
85 "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed + "H" + (evilHash ? "Evil" : "Normal"),
86 seed, steps, noKeys, noValues, evilHash);
87 }
88
89 static Stream<Arguments> parametrizedSlowFuzz() {
90 return FuzzTestUtils.changeStepCount(parametrizedFuzz(), 1);
91 }
92}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java
new file mode 100644
index 00000000..410705a2
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java
@@ -0,0 +1,89 @@
1package tools.refinery.store.map.tests.fuzz;
2
3import static org.junit.jupiter.api.Assertions.fail;
4
5import java.util.Random;
6import java.util.stream.Stream;
7
8import org.junit.jupiter.api.Tag;
9import org.junit.jupiter.api.Timeout;
10import org.junit.jupiter.params.ParameterizedTest;
11import org.junit.jupiter.params.provider.Arguments;
12import org.junit.jupiter.params.provider.MethodSource;
13
14import tools.refinery.store.map.ContinousHashProvider;
15import tools.refinery.store.map.VersionedMapStore;
16import tools.refinery.store.map.VersionedMapStoreImpl;
17import tools.refinery.store.map.internal.VersionedMapImpl;
18import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
19import tools.refinery.store.map.tests.utils.MapTestEnvironment;
20
21class MutableImmutableCompareFuzzTest {
22 private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
23 boolean evilHash) {
24 String[] values = MapTestEnvironment.prepareValues(maxValue);
25 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
26
27 VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
28 VersionedMapImpl<Integer, String> immutable = (VersionedMapImpl<Integer, String>) store.createMap();
29 VersionedMapImpl<Integer, String> mutable = (VersionedMapImpl<Integer, String>) store.createMap();
30
31 Random r = new Random(seed);
32
33 iterativeRandomPutsAndCommitsAndCompare(scenario, immutable, mutable, steps, maxKey, values, r,
34 commitFrequency);
35 }
36
37 private void iterativeRandomPutsAndCommitsAndCompare(String scenario, VersionedMapImpl<Integer, String> immutable,
38 VersionedMapImpl<Integer, String> mutable, int steps, int maxKey, String[] values, Random r,
39 int commitFrequency) {
40 for (int i = 0; i < steps; i++) {
41 int index = i + 1;
42 int nextKey = r.nextInt(maxKey);
43 String nextValue = values[r.nextInt(values.length)];
44 try {
45 immutable.put(nextKey, nextValue);
46 mutable.put(nextKey, nextValue);
47 } catch (Exception exception) {
48 exception.printStackTrace();
49 fail(scenario + ":" + index + ": exception happened: " + exception);
50 }
51 if (index % commitFrequency == 0) {
52 immutable.commit();
53 }
54 MapTestEnvironment.compareTwoMaps(scenario + ":" + index, immutable, mutable);
55
56 MapTestEnvironment.printStatus(scenario, index, steps, null);
57 }
58 }
59
60 @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
61 @MethodSource
62 @Timeout(value = 10)
63 @Tag("fuzz")
64 void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
65 boolean evilHash) {
66 runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
67 noKeys, noValues, commitFrequency, evilHash);
68 }
69
70 static Stream<Arguments> parametrizedFastFuzz() {
71 return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
72 new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
73 new Object[] { false, true });
74 }
75
76 @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
77 @MethodSource
78 @Tag("fuzz")
79 @Tag("slow")
80 void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
81 boolean evilHash) {
82 runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
83 noKeys, noValues, commitFrequency, evilHash);
84 }
85
86 static Stream<Arguments> parametrizedSlowFuzz() {
87 return FuzzTestUtils.changeStepCount(MutableImmutableCompareFuzzTest.parametrizedFastFuzz(), 1);
88 }
89}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java
new file mode 100644
index 00000000..2e29a03f
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java
@@ -0,0 +1,109 @@
1package tools.refinery.store.map.tests.fuzz;
2
3import static org.junit.jupiter.api.Assertions.fail;
4
5import java.util.HashMap;
6import java.util.Map;
7import java.util.Random;
8import java.util.stream.Stream;
9
10import org.junit.jupiter.api.Tag;
11import org.junit.jupiter.api.Timeout;
12import org.junit.jupiter.params.ParameterizedTest;
13import org.junit.jupiter.params.provider.Arguments;
14import org.junit.jupiter.params.provider.MethodSource;
15
16import tools.refinery.store.map.ContinousHashProvider;
17import tools.refinery.store.map.VersionedMapStore;
18import tools.refinery.store.map.VersionedMapStoreImpl;
19import tools.refinery.store.map.internal.VersionedMapImpl;
20import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
21import tools.refinery.store.map.tests.utils.MapTestEnvironment;
22
23class RestoreFuzzTest {
24 private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
25 boolean evilHash) {
26 String[] values = MapTestEnvironment.prepareValues(maxValue);
27 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
28
29 VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
30
31 iterativeRandomPutsAndCommitsThenRestore(scenario, store, steps, maxKey, values, seed, commitFrequency);
32 }
33
34 private void iterativeRandomPutsAndCommitsThenRestore(String scenario, VersionedMapStore<Integer, String> store,
35 int steps, int maxKey, String[] values, int seed, int commitFrequency) {
36 // 1. build a map with versions
37 Random r = new Random(seed);
38 VersionedMapImpl<Integer, String> versioned = (VersionedMapImpl<Integer, String>) store.createMap();
39 Map<Integer, Long> index2Version = new HashMap<>();
40
41 for (int i = 0; i < steps; i++) {
42 int index = i + 1;
43 int nextKey = r.nextInt(maxKey);
44 String nextValue = values[r.nextInt(values.length)];
45 try {
46 versioned.put(nextKey, nextValue);
47 } catch (Exception exception) {
48 exception.printStackTrace();
49 fail(scenario + ":" + index + ": exception happened: " + exception);
50 }
51 if (index % commitFrequency == 0) {
52 long version = versioned.commit();
53 index2Version.put(i, version);
54 }
55 MapTestEnvironment.printStatus(scenario, index, steps, "building");
56 }
57 // 2. create a non-versioned and
58 VersionedMapImpl<Integer, String> reference = (VersionedMapImpl<Integer, String>) store.createMap();
59 r = new Random(seed);
60
61 for (int i = 0; i < steps; i++) {
62 int index = i + 1;
63 int nextKey = r.nextInt(maxKey);
64 String nextValue = values[r.nextInt(values.length)];
65 try {
66 reference.put(nextKey, nextValue);
67 } catch (Exception exception) {
68 exception.printStackTrace();
69 fail(scenario + ":" + index + ": exception happened: " + exception);
70 }
71 if (index % commitFrequency == 0) {
72 versioned.restore(index2Version.get(i));
73 MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference, versioned);
74 }
75 MapTestEnvironment.printStatus(scenario, index, steps, "comparison");
76 }
77
78 }
79
80 @ParameterizedTest(name = "Restore {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
81 @MethodSource
82 @Timeout(value = 10)
83 @Tag("smoke")
84 void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
85 boolean evilHash) {
86 runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
87 commitFrequency, evilHash);
88 }
89
90 static Stream<Arguments> parametrizedFastFuzz() {
91 return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
92 new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
93 new Object[] { false, true });
94 }
95
96 @ParameterizedTest(name = "Restore {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
97 @MethodSource
98 @Tag("smoke")
99 @Tag("slow")
100 void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
101 boolean evilHash) {
102 runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
103 commitFrequency, evilHash);
104 }
105
106 static Stream<Arguments> parametrizedSlowFuzz() {
107 return FuzzTestUtils.changeStepCount(RestoreFuzzTest.parametrizedFastFuzz(), 1);
108 }
109}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java
new file mode 100644
index 00000000..914a0f63
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java
@@ -0,0 +1,113 @@
1package tools.refinery.store.map.tests.fuzz;
2
3import java.util.HashMap;
4import java.util.LinkedList;
5import java.util.List;
6import java.util.Map;
7import java.util.Random;
8import java.util.stream.Stream;
9
10import org.junit.jupiter.api.Tag;
11import org.junit.jupiter.api.Timeout;
12import org.junit.jupiter.params.ParameterizedTest;
13import org.junit.jupiter.params.provider.Arguments;
14import org.junit.jupiter.params.provider.MethodSource;
15
16import tools.refinery.store.map.ContinousHashProvider;
17import tools.refinery.store.map.VersionedMapStore;
18import tools.refinery.store.map.VersionedMapStoreImpl;
19import tools.refinery.store.map.internal.VersionedMapImpl;
20import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
21import tools.refinery.store.map.tests.utils.MapTestEnvironment;
22
23class SharedStoreFuzzTest {
24 private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
25 boolean evilHash) {
26 String[] values = MapTestEnvironment.prepareValues(maxValue);
27 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
28
29 List<VersionedMapStore<Integer, String>> stores = VersionedMapStoreImpl.createSharedVersionedMapStores(5, chp, values[0]);
30
31 iterativeRandomPutsAndCommitsThenRestore(scenario, stores, steps, maxKey, values, seed, commitFrequency);
32 }
33
34 private void iterativeRandomPutsAndCommitsThenRestore(String scenario, List<VersionedMapStore<Integer, String>> stores,
35 int steps, int maxKey, String[] values, int seed, int commitFrequency) {
36 // 1. maps with versions
37 Random r = new Random(seed);
38 List<VersionedMapImpl<Integer, String>> versioneds = new LinkedList<>();
39 for(VersionedMapStore<Integer, String> store : stores) {
40 versioneds.add((VersionedMapImpl<Integer, String>) store.createMap());
41 }
42
43 List<Map<Integer, Long>> index2Version = new LinkedList<>();
44 for(int i = 0; i<stores.size(); i++) {
45 index2Version.add(new HashMap<>());
46 }
47
48 for (int i = 0; i < steps; i++) {
49 int stepIndex = i + 1;
50 for (int storeIndex = 0; storeIndex<versioneds.size(); storeIndex++) {
51 int nextKey = r.nextInt(maxKey);
52 String nextValue = values[r.nextInt(values.length)];
53 versioneds.get(storeIndex).put(nextKey, nextValue);
54 if (stepIndex % commitFrequency == 0) {
55 long version = versioneds.get(storeIndex).commit();
56 index2Version.get(storeIndex).put(i, version);
57 }
58 MapTestEnvironment.printStatus(scenario, stepIndex, steps, "building");
59 }
60 }
61 // 2. create a non-versioned and
62 List<VersionedMapImpl<Integer, String>> reference = new LinkedList<>();
63 for(VersionedMapStore<Integer, String> store : stores) {
64 reference.add((VersionedMapImpl<Integer, String>) store.createMap());
65 }
66 r = new Random(seed);
67
68 for (int i = 0; i < steps; i++) {
69 int index = i + 1;
70 for (int storeIndex = 0; storeIndex<versioneds.size(); storeIndex++) {
71 int nextKey = r.nextInt(maxKey);
72 String nextValue = values[r.nextInt(values.length)];
73 reference.get(storeIndex).put(nextKey, nextValue);
74 if (index % commitFrequency == 0) {
75 versioneds.get(storeIndex).restore(index2Version.get(storeIndex).get(i));
76 MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference.get(storeIndex), versioneds.get(storeIndex));
77 }
78 }
79 MapTestEnvironment.printStatus(scenario, index, steps, "comparison");
80 }
81
82 }
83
84 @ParameterizedTest(name = "Shared Store {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
85 @MethodSource
86 @Timeout(value = 10)
87 @Tag("smoke")
88 void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
89 boolean evilHash) {
90 runFuzzTest("SharedS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
91 commitFrequency, evilHash);
92 }
93
94 static Stream<Arguments> parametrizedFastFuzz() {
95 return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 },
96 new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
97 new Object[] { false, true });
98 }
99
100 @ParameterizedTest(name = "Shared Store {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
101 @MethodSource
102 @Tag("smoke")
103 @Tag("slow")
104 void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
105 boolean evilHash) {
106 runFuzzTest("SharedS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
107 commitFrequency, evilHash);
108 }
109
110 static Stream<Arguments> parametrizedSlowFuzz() {
111 return FuzzTestUtils.changeStepCount(RestoreFuzzTest.parametrizedFastFuzz(), 1);
112 }
113}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java
new file mode 100644
index 00000000..e75d7f5a
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java
@@ -0,0 +1,64 @@
1package tools.refinery.store.map.tests.fuzz.utils;
2
3import java.util.Arrays;
4import java.util.LinkedList;
5import java.util.List;
6import java.util.stream.Stream;
7
8import org.junit.jupiter.params.provider.Arguments;
9
10public final class FuzzTestUtils {
11 public static final int FAST_STEP_COUNT = 500;
12 public static final int SLOW_STEP_COUNT = 32 * 32 * 32 * 32;
13
14 private FuzzTestUtils() {
15 throw new IllegalStateException("This is a static utility class and should not be instantiated directly");
16 }
17
18 public static Stream<Arguments> changeStepCount(Stream<Arguments> arguments, int parameterIndex) {
19 return arguments.map(x -> Arguments.of(updatedStepCount(x.get(), parameterIndex)));
20 }
21
22 public static Object[] updatedStepCount(Object[] arguments, int parameterIndex) {
23 Object[] copy = Arrays.copyOf(arguments, arguments.length);
24 copy[parameterIndex] = SLOW_STEP_COUNT;
25 return copy;
26 }
27
28 static List<List<Object>> permutationInternal(int from, Object[]... valueOption) {
29 if (valueOption.length == from) {
30 return List.of(List.of());
31 } else {
32 Object[] permuteThis = valueOption[from];
33 List<List<Object>> otherCombination = permutationInternal(from + 1, valueOption);
34 List<List<Object>> result = new LinkedList<>();
35 for (Object permuteThisElement : permuteThis) {
36 for (List<Object> otherCombinationList : otherCombination) {
37 List<Object> newResult = new LinkedList<>();
38 newResult.add(permuteThisElement);
39 newResult.addAll(otherCombinationList);
40 result.add(newResult);
41 }
42 }
43 return result;
44 }
45 }
46
47 public static Stream<Arguments> permutation(Object[]... valueOption) {
48 List<List<Object>> permutations = permutationInternal(0, valueOption);
49 return permutations.stream().map(x -> Arguments.of(x.toArray()));
50 }
51
52 public static Stream<Arguments> permutationWithSize(Object[]... valueOption) {
53 int size = 1;
54 for (int i = 0; i < valueOption.length; i++) {
55 size *= valueOption[i].length;
56 }
57 Object[][] newValueOption = new Object[valueOption.length + 1][];
58 newValueOption[0] = new Object[] { size };
59 for (int i = 1; i < newValueOption.length; i++) {
60 newValueOption[i] = valueOption[i - 1];
61 }
62 return permutation(newValueOption);
63 }
64}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java
new file mode 100644
index 00000000..72f2a46c
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java
@@ -0,0 +1,33 @@
1package tools.refinery.store.map.tests.fuzz.utils;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4
5import java.util.List;
6
7import org.junit.jupiter.api.Test;
8
9class FuzzTestUtilsTest {
10 @Test
11 void permutationInternalTest() {
12 List<List<Object>> res = FuzzTestUtils.permutationInternal(0, new Object[] { 1, 2, 3 },
13 new Object[] { 'a', 'b', 'c' }, new Object[] { "alpha", "beta", "gamma", "delta" });
14 assertEquals(3 * 3 * 4, res.size());
15 }
16
17 @Test
18 void permutationTest1() {
19 var res = FuzzTestUtils.permutation(new Object[] { 1, 2, 3 }, new Object[] { 'a', 'b', 'c' },
20 new Object[] { "alpha", "beta", "gamma", "delta" });
21 assertEquals(3 * 3 * 4, res.count());
22 }
23
24 @Test
25 void permutationTest2() {
26 var res = FuzzTestUtils.permutation(new Object[] { 1, 2, 3 }, new Object[] { 'a', 'b', 'c' },
27 new Object[] { "alpha", "beta", "gamma", "delta" });
28 var arguments = res.findFirst().get().get();
29 assertEquals(1, arguments[0]);
30 assertEquals('a', arguments[1]);
31 assertEquals("alpha", arguments[2]);
32 }
33}
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
new file mode 100644
index 00000000..991b4f51
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java
@@ -0,0 +1,214 @@
1package tools.refinery.store.map.tests.utils;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4import static org.junit.jupiter.api.Assertions.assertTrue;
5import static org.junit.jupiter.api.Assertions.fail;
6
7import java.util.HashMap;
8import java.util.Iterator;
9import java.util.List;
10import java.util.Map;
11import java.util.Map.Entry;
12
13import tools.refinery.store.map.ContinousHashProvider;
14import tools.refinery.store.map.Cursor;
15import tools.refinery.store.map.VersionedMap;
16import tools.refinery.store.map.internal.VersionedMapImpl;
17
18import java.util.TreeMap;
19
20public class MapTestEnvironment<K, V> {
21 public static String[] prepareValues(int maxValue) {
22 String[] values = new String[maxValue];
23 values[0] = "DEFAULT";
24 for (int i = 1; i < values.length; i++) {
25 values[i] = "VAL" + i;
26 }
27 return values;
28 }
29
30 public static ContinousHashProvider<Integer> prepareHashProvider(final boolean evil) {
31 // Use maxPrime = 2147483629
32
33 ContinousHashProvider<Integer> chp = new ContinousHashProvider<Integer>() {
34
35 @Override
36 public int getHash(Integer key, int index) {
37 if (evil && index < 15 && index < key / 3) {
38 return 7;
39 }
40 int result = 1;
41 final int prime = 31;
42
43 result = prime * result + key;
44 result = prime * result + index;
45
46 return result;
47 }
48 };
49 return chp;
50 }
51
52 public static void printStatus(String scenario, int actual, int max, String stepName) {
53 if (actual % 10000 == 0) {
54 String printStepName = stepName == null ? "" : stepName;
55 System.out.format(scenario + ":%d/%d (%d%%) " + printStepName + "%n", actual, max, actual * 100 / max);
56 }
57
58 }
59
60 public static <K, V> void compareTwoMaps(String title, VersionedMapImpl<K, V> map1,
61 VersionedMapImpl<K, V> map2) {
62 compareTwoMaps(title, map1, map2, null);
63 }
64 public static <K, V> void compareTwoMaps(String title, VersionedMapImpl<K, V> map1,
65 VersionedMapImpl<K, V> map2, List<Throwable> errors) {
66 // 1. Comparing cursors.
67 Cursor<K, V> cursor1 = map1.getAll();
68 Cursor<K, V> cursor2 = map2.getAll();
69 while (!cursor1.isTerminated()) {
70 if (cursor2.isTerminated()) {
71 fail("cursor 2 terminated before cursor1");
72 }
73 assertEqualsList(cursor1.getKey(), cursor2.getKey(),"Keys not equal", errors);
74 assertEqualsList(cursor2.getValue(), cursor2.getValue(), "Values not equal", errors);
75 cursor1.move();
76 cursor2.move();
77 }
78 if (!cursor2.isTerminated())
79 fail("cursor 1 terminated before cursor 2");
80
81 // 2.1. comparing hash codes
82 assertEqualsList(map1.hashCode(), map2.hashCode(), title + ": hash code check",errors);
83 assertEqualsList(map1, map2, title + ": 1.equals(2)",errors);
84 assertEqualsList(map2, map1, title + ": 2.equals(1)",errors);
85 }
86 private static void assertEqualsList(Object o1, Object o2, String message, List<Throwable> errors) {
87 if(errors == null) {
88 assertEquals(o1, o2, message);
89 } else {
90 if(o1 != null) {
91 if(!(o1.equals(o2))) {
92 AssertionError error = new AssertionError((message != null ? message+" " : "") + "expected: " + o1 + " but was : " + o2);
93 errors.add(error);
94 }
95 }
96 }
97 }
98
99 public VersionedMapImpl<K, V> sut;
100 Map<K, V> oracle = new HashMap<K, V>();
101
102 public MapTestEnvironment(VersionedMapImpl<K, V> sut) {
103 this.sut = sut;
104 }
105
106 public void put(K key, V value) {
107 V oldSutValue = sut.put(key, value);
108 V oldOracleValue;
109 if (value != sut.getDefaultValue()) {
110 oldOracleValue = oracle.put(key, value);
111 } else {
112 oldOracleValue = oracle.remove(key);
113 }
114 if(oldSutValue == sut.getDefaultValue() && oldOracleValue != null) {
115 fail("After put, SUT old value was default, but oracle old walue was " + oldOracleValue);
116 }
117 if(oldSutValue != sut.getDefaultValue()) {
118 assertEquals(oldOracleValue, oldSutValue);
119 }
120 }
121
122 public void checkEquivalence(String title) {
123 // 0. Checking integrity
124 try {
125 sut.checkIntegrity();
126 } catch (IllegalStateException e) {
127 fail(title + ": " + e.getMessage());
128 }
129
130 // 1. Checking: if Reference contains <key,value> pair, then SUT contains
131 // <key,value> pair.
132 // Tests get functions
133 for (Entry<K, V> entry : oracle.entrySet()) {
134 V sutValue = sut.get(entry.getKey());
135 V oracleValue = entry.getValue();
136 if (sutValue != oracleValue) {
137 printComparison();
138 fail(title + ": Non-equivalent get(" + entry.getKey() + ") results: SUT=" + sutValue + ", Oracle="
139 + oracleValue + "!");
140 }
141 }
142
143 // 2. Checking: if SUT contains <key,value> pair, then Reference contains
144 // <key,value> pair.
145 // Tests iterators
146 int elementsInSutEntrySet = 0;
147 Cursor<K, V> cursor = sut.getAll();
148 while (cursor.move()) {
149 elementsInSutEntrySet++;
150 K key = cursor.getKey();
151 V sutValue = cursor.getValue();
152 // System.out.println(key + " -> " + sutValue);
153 V oracleValue = oracle.get(key);
154 if (sutValue != oracleValue) {
155 printComparison();
156 fail(title + ": Non-equivalent entry in iterator: SUT=<" + key + "," + sutValue + ">, Oracle=<" + key
157 + "," + oracleValue + ">!");
158 }
159
160 }
161
162 // 3. Checking sizes
163 // Counting of non-default value pairs.
164 int oracleSize = oracle.entrySet().size();
165 long sutSize = sut.getSize();
166 if (oracleSize != sutSize || oracleSize != elementsInSutEntrySet) {
167 printComparison();
168 fail(title + ": Non-eqivalent size() result: SUT.getSize()=" + sutSize + ", SUT.entryset.size="
169 + elementsInSutEntrySet + ", Oracle=" + oracleSize + "!");
170 }
171 }
172
173 public static <K,V> void checkOrder(String scenario, VersionedMap<K,V> versionedMap) {
174 K previous = null;
175 Cursor<K, V> cursor = versionedMap.getAll();
176 while(cursor.move()) {
177 System.out.println(cursor.getKey() + " " + ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().getHash(cursor.getKey(), 0));
178 if(previous != null) {
179 int comparisonResult = ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().compare(previous, cursor.getKey());
180 assertTrue(comparisonResult<0,scenario+" Cursor order is not incremental!");
181 }
182 previous = cursor.getKey();
183 }
184 System.out.println();
185 }
186
187 public void printComparison() {
188 System.out.println("SUT:");
189 printEntrySet(sut.getAll());
190 System.out.println("Oracle:");
191 printEntrySet(oracle.entrySet().iterator());
192 }
193
194 private void printEntrySet(Iterator<Entry<K, V>> iterator) {
195 TreeMap<K, V> treemap = new TreeMap<>();
196 while (iterator.hasNext()) {
197 Entry<K, V> entry = iterator.next();
198 treemap.put(entry.getKey(), entry.getValue());
199 }
200 for (Entry<K, V> e : treemap.entrySet()) {
201 System.out.println("\t" + e.getKey() + " -> " + e.getValue());
202 }
203 }
204
205 private void printEntrySet(Cursor<K, V> cursor) {
206 TreeMap<K, V> treemap = new TreeMap<>();
207 while (cursor.move()) {
208 treemap.put(cursor.getKey(), cursor.getValue());
209 }
210 for (Entry<K, V> e : treemap.entrySet()) {
211 System.out.println("\t" + e.getKey() + " -> " + e.getValue());
212 }
213 }
214}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/model/hashTests/HashEfficiencyTest.java b/subprojects/store/src/test/java/tools/refinery/store/model/hashTests/HashEfficiencyTest.java
new file mode 100644
index 00000000..7d070380
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/model/hashTests/HashEfficiencyTest.java
@@ -0,0 +1,161 @@
1package tools.refinery.store.model.hashTests;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4
5import java.util.ArrayList;
6import java.util.LinkedList;
7import java.util.List;
8import java.util.Random;
9
10import org.junit.jupiter.api.Test;
11
12import tools.refinery.store.map.ContinousHashProvider;
13import tools.refinery.store.model.Tuple;
14import tools.refinery.store.model.TupleHashProvider;
15import tools.refinery.store.model.TupleHashProviderBitMagic;
16
17class HashEfficiencyTest {
18
19 private static List<Tuple> permutations(int range, int arity) {
20 if(arity == 1) {
21 List<Tuple> result = new ArrayList<>(range);
22 for(int i=0; i<range; i++) {
23 result.add(Tuple.of(i));
24 }
25 return result;
26 } else if(arity > 1) {
27 List<Tuple> smallers = permutations(range, arity-1);
28 List<Tuple> result = new ArrayList<>(range*smallers.size());
29 for(Tuple smaller : smallers) {
30 for(int i=0; i<range; i++) {
31 int[] larger = new int[arity];
32 for(int x = 0; x<smaller.getSize(); x++) {
33 larger[x] = smaller.get(x);
34 }
35 larger[arity-1] = i;
36 result.add(Tuple.of(larger));
37 }
38 }
39 return result;
40 } else throw new IllegalArgumentException();
41 }
42
43 private static int amountToRange(int arity, int n) {
44 int range = 1;
45 while(Math.pow(range,arity)<n+0.1) {
46 range++;
47 }
48 return 1024;
49 }
50
51 public static List<Tuple> nPermutations(int arity, int n) {
52 int range = amountToRange(arity, n);
53 List<Tuple> permutations = permutations(range, arity);
54 return permutations.subList(0, n);
55 }
56
57 public static List<Tuple> nRandoms(int arity, int n, int seed) {
58 int range = amountToRange(arity, n);
59 List<Tuple> permutations = new ArrayList<>(n);
60 Random r = new Random(seed);
61 for(int i = 0; i<n; i++) {
62 int[] tuple = new int[arity];
63 for(int j=0; j<arity; j++) {
64 tuple[j] = r.nextInt(range);
65 }
66 permutations.add(Tuple.of(tuple));
67 }
68 return permutations;
69 }
70
71 @Test
72 void permutationTest() {
73 List<Tuple> p = permutations(10, 2);
74 assertEquals(p.size(),10*10);
75 }
76// private void printTuples(List<Tuple> p) {
77// for(Tuple element : p) {
78// System.out.println(element);
79// }
80// }
81 @Test
82 void nPermutationTest() {
83 final int amount = 500;
84 List<Tuple> p = nPermutations(2, amount);
85 assertEquals(amount,p.size());
86 }
87 @Test
88 void nRandomTest() {
89 final int amount = 500;
90 List<Tuple> p = nRandoms(2, amount, 1);;
91 assertEquals(amount,p.size());
92 }
93 private static double calculateHashClashes(List<Tuple> tuples, ContinousHashProvider<Tuple> chp) {
94 int sumClashes = 0;
95
96 for(int i = 0; i<tuples.size(); i++) {
97 int height = 0;
98 for(int j=0; j<tuples.size(); j++) {
99 int clashes = calculateHashClash(chp, tuples.get(i), tuples.get(j));
100 height = Math.max(height, clashes);
101 }
102 sumClashes += height;
103 }
104 return (sumClashes+0.0) / tuples.size();
105 }
106 private static int calculateHashClash(ContinousHashProvider<Tuple> chp, Tuple a, Tuple b) {
107 if(a.equals(b)) return 0;
108 final int bits = 5;
109 final int segments = Integer.SIZE/bits;
110 final int mask = (1<<bits)-1;
111 for(int i = 0;;i++) {
112 int index = i/segments;
113 int depth = i%segments;
114 int aHash = (chp.getHash(a, index)>>(depth*5))&mask;
115 int bHash = (chp.getHash(b, index)>>(depth*5))&mask;
116 if(aHash != bHash) {
117 return i+1;
118 }
119 if(i>400) {
120 throw new IllegalStateException(a+" vs "+b);
121 }
122 }
123 }
124 private static double caclulateOptimalHashClash(int size) {
125 return (Math.log(size)/Math.log(32));
126 }
127 public static void main(String[] args) {
128 List<String> hashNames = new LinkedList<>();
129 List<ContinousHashProvider<Tuple>> hashes = new LinkedList<>();
130 hashNames.add("PrimeGroup");
131 hashes.add(new TupleHashProvider());
132 hashNames.add("BitMagic");
133 hashes.add(new TupleHashProviderBitMagic());
134
135 int[] arities = new int[] {2,3,4,5};
136 int[] sizes = new int[] {32*32,32*32*8};
137
138 System.out.println("Size,Arity,DataSource,Hash,Chashes,Optimal,Badness");
139 for(int size : sizes) {
140 double optimalClashes = caclulateOptimalHashClash(size);
141 for(int arity : arities) {
142 List<String> dataSourceNames = new LinkedList<>();
143 List<List<Tuple>> dataSources = new LinkedList<>();
144
145// dataSourceNames.add("Permutation");
146// dataSources.add(nPermutations(arity, size));
147 dataSourceNames.add("Random");
148 dataSources.add(nRandoms(arity, size, 0));
149
150 for(int dataSourceIndex = 0; dataSourceIndex<dataSourceNames.size(); dataSourceIndex++) {
151 for(int hashIndex = 0; hashIndex<hashNames.size(); hashIndex++) {
152 double clashes = calculateHashClashes(dataSources.get(dataSourceIndex),hashes.get(hashIndex));
153 System.out.println(
154 size+","+arity+","+dataSourceNames.get(dataSourceIndex)+","+hashNames.get(hashIndex)+","+
155 clashes+","+optimalClashes+","+(clashes+0.0)/optimalClashes);
156 }
157 }
158 }
159 }
160 }
161}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/model/tests/ModelTest.java b/subprojects/store/src/test/java/tools/refinery/store/model/tests/ModelTest.java
new file mode 100644
index 00000000..9d90b1e1
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/model/tests/ModelTest.java
@@ -0,0 +1,148 @@
1package tools.refinery.store.model.tests;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4import static org.junit.jupiter.api.Assertions.assertFalse;
5import static org.junit.jupiter.api.Assertions.assertTrue;
6
7import java.util.Set;
8
9import org.junit.jupiter.api.Assertions;
10import org.junit.jupiter.api.Test;
11
12import tools.refinery.store.model.Model;
13import tools.refinery.store.model.ModelStore;
14import tools.refinery.store.model.ModelStoreImpl;
15import tools.refinery.store.model.Tuple;
16import tools.refinery.store.model.representation.Relation;
17
18class ModelTest {
19
20 @Test
21 void modelConstructionTest() {
22 Relation<Boolean> person = new Relation<>("Person", 1, false);
23 Relation<Boolean> friend = new Relation<>("friend", 2, false);
24
25 ModelStore store = new ModelStoreImpl(Set.of(person, friend));
26 Model model = store.createModel();
27
28 assertTrue(store.getDataRepresentations().contains(person));
29 assertTrue(store.getDataRepresentations().contains(friend));
30 assertTrue(model.getDataRepresentations().contains(person));
31 assertTrue(model.getDataRepresentations().contains(friend));
32
33 Relation<Integer> other = new Relation<Integer>("other", 2, null);
34 assertFalse(model.getDataRepresentations().contains(other));
35 }
36
37 @Test
38 void modelBuildingTest() {
39 Relation<Boolean> person = new Relation<>("Person", 1, false);
40 Relation<Integer> age = new Relation<Integer>("age", 1, null);
41 Relation<Boolean> friend = new Relation<>("friend", 2, false);
42
43 ModelStore store = new ModelStoreImpl(Set.of(person, age, friend));
44 Model model = store.createModel();
45
46 model.put(person, Tuple.of(0), true);
47 model.put(person, Tuple.of(1), true);
48 model.put(age, Tuple.of(0), 3);
49 model.put(age, Tuple.of(1), 1);
50 model.put(friend, Tuple.of(0, 1), true);
51 model.put(friend, Tuple.of(1, 0), true);
52
53 assertTrue(model.get(person, Tuple.of(0)));
54 assertTrue(model.get(person, Tuple.of(1)));
55 assertFalse(model.get(person, Tuple.of(2)));
56
57 assertEquals(3, model.get(age, Tuple.of(0)));
58 assertEquals(1, model.get(age, Tuple.of(1)));
59 assertEquals(null, model.get(age, Tuple.of(2)));
60
61 assertTrue(model.get(friend, Tuple.of(0, 1)));
62 assertFalse(model.get(friend, Tuple.of(0, 5)));
63 }
64
65 @Test
66 void modelBuildingArityFailTest() {
67 Relation<Boolean> person = new Relation<>("Person", 1, false);
68 ModelStore store = new ModelStoreImpl(Set.of(person));
69 Model model = store.createModel();
70
71 final Tuple tuple3 = Tuple.of(1, 1, 1);
72 Assertions.assertThrows(IllegalArgumentException.class, () -> model.put(person, tuple3, true));
73 Assertions.assertThrows(IllegalArgumentException.class, () -> model.get(person, tuple3));
74 }
75
76 @Test
77 void modelBuildingNullFailTest() {
78 Relation<Integer> age = new Relation<Integer>("age", 1, null);
79 ModelStore store = new ModelStoreImpl(Set.of(age));
80 Model model = store.createModel();
81
82 model.put(age, Tuple.of(1), null); // valid
83 Assertions.assertThrows(IllegalArgumentException.class, () -> model.put(age, null, 1));
84 Assertions.assertThrows(IllegalArgumentException.class, () -> model.get(age, null));
85
86 }
87
88 @Test
89 void modelUpdateTest() {
90 Relation<Boolean> person = new Relation<>("Person", 1, false);
91 Relation<Integer> age = new Relation<Integer>("age", 1, null);
92 Relation<Boolean> friend = new Relation<>("friend", 2, false);
93
94 ModelStore store = new ModelStoreImpl(Set.of(person, age, friend));
95 Model model = store.createModel();
96
97 model.put(person, Tuple.of(0), true);
98 model.put(person, Tuple.of(1), true);
99 model.put(age, Tuple.of(0), 3);
100 model.put(age, Tuple.of(1), 1);
101 model.put(friend, Tuple.of(0, 1), true);
102 model.put(friend, Tuple.of(1, 0), true);
103
104 assertEquals(3, model.get(age, Tuple.of(0)));
105 assertTrue(model.get(friend, Tuple.of(0, 1)));
106
107 model.put(age, Tuple.of(0), 4);
108 model.put(friend, Tuple.of(0, 1), false);
109
110 assertEquals(4, model.get(age, Tuple.of(0)));
111 assertFalse(model.get(friend, Tuple.of(0, 1)));
112 }
113
114 @Test
115 void restoreTest() {
116 Relation<Boolean> person = new Relation<Boolean>("Person", 1, false);
117 Relation<Boolean> friend = new Relation<Boolean>("friend", 2, false);
118
119 ModelStore store = new ModelStoreImpl(Set.of(person, friend));
120 Model model = store.createModel();
121
122 model.put(person, Tuple.of(0), true);
123 model.put(person, Tuple.of(1), true);
124 model.put(friend, Tuple.of(0, 1), true);
125 model.put(friend, Tuple.of(1, 0), true);
126 long state1 = model.commit();
127
128 assertFalse(model.get(person, Tuple.of(2)));
129 assertFalse(model.get(friend, Tuple.of(0, 2)));
130
131 model.put(person, Tuple.of(2), true);
132 model.put(friend, Tuple.of(0, 2), true);
133 long state2 = model.commit();
134
135 assertTrue(model.get(person, Tuple.of(2)));
136 assertTrue(model.get(friend, Tuple.of(0, 2)));
137
138 model.restore(state1);
139
140 assertFalse(model.get(person, Tuple.of(2)));
141 assertFalse(model.get(friend, Tuple.of(0, 2)));
142
143 model.restore(state2);
144
145 assertTrue(model.get(person, Tuple.of(2)));
146 assertTrue(model.get(friend, Tuple.of(0, 2)));
147 }
148}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/query/test/QueryTest.java b/subprojects/store/src/test/java/tools/refinery/store/query/test/QueryTest.java
new file mode 100644
index 00000000..02381bcd
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/query/test/QueryTest.java
@@ -0,0 +1,445 @@
1package tools.refinery.store.query.test;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4
5import java.util.ArrayList;
6import java.util.Arrays;
7import java.util.Collections;
8import java.util.HashSet;
9import java.util.List;
10import java.util.Set;
11import java.util.stream.Stream;
12
13import org.junit.jupiter.api.Test;
14
15import tools.refinery.store.model.Tuple;
16import tools.refinery.store.model.representation.Relation;
17import tools.refinery.store.model.representation.TruthValue;
18import tools.refinery.store.query.QueriableModel;
19import tools.refinery.store.query.QueriableModelStore;
20import tools.refinery.store.query.QueriableModelStoreImpl;
21import tools.refinery.store.query.building.DNFAnd;
22import tools.refinery.store.query.building.DNFPredicate;
23import tools.refinery.store.query.building.EquivalenceAtom;
24import tools.refinery.store.query.building.PredicateAtom;
25import tools.refinery.store.query.building.RelationAtom;
26import tools.refinery.store.query.building.Variable;
27import tools.refinery.store.query.view.FilteredRelationView;
28import tools.refinery.store.query.view.KeyOnlyRelationView;
29import tools.refinery.store.query.view.RelationView;
30
31class QueryTest {
32
33 static void compareMatchSets(Stream<Object[]> matchSet, Set<List<Tuple>> expected) {
34 Set<List<Tuple>> translatedMatchSet = new HashSet<>();
35 var interator = matchSet.iterator();
36 while (interator.hasNext()) {
37 var element = interator.next();
38 List<Tuple> elementToTranslatedMatchSet = new ArrayList<>();
39 for (int i = 0; i < element.length; i++) {
40 elementToTranslatedMatchSet.add((Tuple) element[i]);
41 }
42 translatedMatchSet.add(elementToTranslatedMatchSet);
43 }
44
45 assertEquals(expected, translatedMatchSet);
46 }
47
48 @Test
49 void typeConstraintTest() {
50 Relation<Boolean> person = new Relation<>("Person", 1, false);
51 Relation<Boolean> asset = new Relation<>("Asset", 1, false);
52 RelationView<Boolean> persionView = new KeyOnlyRelationView(person);
53
54 List<Variable> parameters = Arrays.asList(new Variable("p1"));
55 RelationAtom personRelationAtom = new RelationAtom(persionView, parameters);
56 DNFAnd clause = new DNFAnd(Collections.emptySet(), Arrays.asList(personRelationAtom));
57 DNFPredicate predicate = new DNFPredicate("TypeConstraint", parameters, Arrays.asList(clause));
58
59 QueriableModelStore store = new QueriableModelStoreImpl(Set.of(person, asset), Set.of(persionView),
60 Set.of(predicate));
61 QueriableModel model = store.createModel();
62
63 model.put(person, Tuple.of(0), true);
64 model.put(person, Tuple.of(1), true);
65 model.put(asset, Tuple.of(1), true);
66 model.put(asset, Tuple.of(2), true);
67
68 model.flushChanges();
69 assertEquals(2, model.countResults(predicate));
70 compareMatchSets(model.allResults(predicate), Set.of(List.of(Tuple.of(0)), List.of(Tuple.of(1))));
71 }
72
73 @Test
74 void relationConstraintTest() {
75 Relation<Boolean> person = new Relation<Boolean>("Person", 1, false);
76 Relation<TruthValue> friend = new Relation<>("friend", 2, TruthValue.FALSE);
77 RelationView<Boolean> persionView = new KeyOnlyRelationView(person);
78 RelationView<TruthValue> friendMustView = new FilteredRelationView<TruthValue>(friend, (k, v) -> v.must());
79
80 Variable p1 = new Variable("p1");
81 Variable p2 = new Variable("p2");
82 List<Variable> parameters = Arrays.asList(p1, p2);
83
84 RelationAtom personRelationAtom1 = new RelationAtom(persionView, Arrays.asList(p1));
85 RelationAtom personRelationAtom2 = new RelationAtom(persionView, Arrays.asList(p2));
86 RelationAtom friendRelationAtom = new RelationAtom(friendMustView, Arrays.asList(p1, p2));
87 DNFAnd clause = new DNFAnd(Collections.emptySet(),
88 Arrays.asList(personRelationAtom1, personRelationAtom2, friendRelationAtom));
89 DNFPredicate predicate = new DNFPredicate("RelationConstraint", parameters, Arrays.asList(clause));
90
91 QueriableModelStore store = new QueriableModelStoreImpl(Set.of(person, friend),
92 Set.of(persionView, friendMustView), Set.of(predicate));
93 QueriableModel model = store.createModel();
94
95 assertEquals(0, model.countResults(predicate));
96
97 model.put(person, Tuple.of(0), true);
98 model.put(person, Tuple.of(1), true);
99 model.put(person, Tuple.of(2), true);
100 model.put(friend, Tuple.of(0, 1), TruthValue.TRUE);
101 model.put(friend, Tuple.of(1, 0), TruthValue.TRUE);
102 model.put(friend, Tuple.of(1, 2), TruthValue.TRUE);
103
104 assertEquals(0, model.countResults(predicate));
105
106 model.flushChanges();
107 assertEquals(3, model.countResults(predicate));
108 compareMatchSets(model.allResults(predicate), Set.of(List.of(Tuple.of(0), Tuple.of(1)),
109 List.of(Tuple.of(1), Tuple.of(0)), List.of(Tuple.of(1), Tuple.of(2))));
110 }
111
112 @Test
113 void andTest() {
114 Relation<Boolean> person = new Relation<Boolean>("Person", 1, false);
115 Relation<TruthValue> friend = new Relation<>("friend", 2, TruthValue.FALSE);
116 RelationView<Boolean> persionView = new KeyOnlyRelationView(person);
117 RelationView<TruthValue> friendMustView = new FilteredRelationView<TruthValue>(friend, (k, v) -> v.must());
118
119 Variable p1 = new Variable("p1");
120 Variable p2 = new Variable("p2");
121 List<Variable> parameters = Arrays.asList(p1, p2);
122
123 RelationAtom personRelationAtom1 = new RelationAtom(persionView, Arrays.asList(p1));
124 RelationAtom personRelationAtom2 = new RelationAtom(persionView, Arrays.asList(p2));
125 RelationAtom friendRelationAtom1 = new RelationAtom(friendMustView, Arrays.asList(p1, p2));
126 RelationAtom friendRelationAtom2 = new RelationAtom(friendMustView, Arrays.asList(p2, p1));
127 DNFAnd clause = new DNFAnd(Collections.emptySet(),
128 Arrays.asList(personRelationAtom1, personRelationAtom2, friendRelationAtom1, friendRelationAtom2));
129 DNFPredicate predicate = new DNFPredicate("RelationConstraint", parameters, Arrays.asList(clause));
130
131 QueriableModelStore store = new QueriableModelStoreImpl(Set.of(person, friend),
132 Set.of(persionView, friendMustView), Set.of(predicate));
133 QueriableModel model = store.createModel();
134
135 assertEquals(0, model.countResults(predicate));
136
137 model.put(person, Tuple.of(0), true);
138 model.put(person, Tuple.of(1), true);
139 model.put(person, Tuple.of(2), true);
140
141 model.put(friend, Tuple.of(0, 1), TruthValue.TRUE);
142 model.put(friend, Tuple.of(0, 2), TruthValue.TRUE);
143
144 model.flushChanges();
145 assertEquals(0, model.countResults(predicate));
146
147 model.put(friend, Tuple.of(1, 0), TruthValue.TRUE);
148 model.flushChanges();
149 assertEquals(2, model.countResults(predicate));
150 compareMatchSets(model.allResults(predicate),
151 Set.of(List.of(Tuple.of(0), Tuple.of(1)), List.of(Tuple.of(1), Tuple.of(0))));
152
153 model.put(friend, Tuple.of(2, 0), TruthValue.TRUE);
154 model.flushChanges();
155 assertEquals(4, model.countResults(predicate));
156 compareMatchSets(model.allResults(predicate),
157 Set.of(List.of(Tuple.of(0), Tuple.of(1)), List.of(Tuple.of(1), Tuple.of(0)),
158 List.of(Tuple.of(0), Tuple.of(2)), List.of(Tuple.of(2), Tuple.of(0))));
159 }
160
161 @Test
162 void existTest() {
163 Relation<Boolean> person = new Relation<Boolean>("Person", 1, false);
164 Relation<TruthValue> friend = new Relation<>("friend", 2, TruthValue.FALSE);
165 RelationView<Boolean> persionView = new KeyOnlyRelationView(person);
166 RelationView<TruthValue> friendMustView = new FilteredRelationView<TruthValue>(friend, (k, v) -> v.must());
167
168 Variable p1 = new Variable("p1");
169 Variable p2 = new Variable("p2");
170 List<Variable> parameters = Arrays.asList(p1);
171
172 RelationAtom personRelationAtom1 = new RelationAtom(persionView, Arrays.asList(p1));
173 RelationAtom personRelationAtom2 = new RelationAtom(persionView, Arrays.asList(p2));
174 RelationAtom friendRelationAtom = new RelationAtom(friendMustView, Arrays.asList(p1, p2));
175 DNFAnd clause = new DNFAnd(Set.of(p2),
176 Arrays.asList(personRelationAtom1, personRelationAtom2, friendRelationAtom));
177 DNFPredicate predicate = new DNFPredicate("RelationConstraint", parameters, Arrays.asList(clause));
178
179 QueriableModelStore store = new QueriableModelStoreImpl(Set.of(person, friend),
180 Set.of(persionView, friendMustView), Set.of(predicate));
181 QueriableModel model = store.createModel();
182
183 assertEquals(0, model.countResults(predicate));
184
185 model.put(person, Tuple.of(0), true);
186 model.put(person, Tuple.of(1), true);
187 model.put(person, Tuple.of(2), true);
188 model.put(friend, Tuple.of(0, 1), TruthValue.TRUE);
189 model.put(friend, Tuple.of(1, 0), TruthValue.TRUE);
190 model.put(friend, Tuple.of(1, 2), TruthValue.TRUE);
191
192 assertEquals(0, model.countResults(predicate));
193
194 model.flushChanges();
195 assertEquals(2, model.countResults(predicate));
196 compareMatchSets(model.allResults(predicate), Set.of(List.of(Tuple.of(0)), List.of(Tuple.of(1))));
197 }
198
199 @Test
200 void orTest() {
201 Relation<Boolean> person = new Relation<>("Person", 1, false);
202 Relation<Boolean> animal = new Relation<>("Animal", 1, false);
203 Relation<TruthValue> friend = new Relation<>("friend", 2, TruthValue.FALSE);
204 RelationView<Boolean> persionView = new KeyOnlyRelationView(person);
205 RelationView<Boolean> animalView = new KeyOnlyRelationView(animal);
206 RelationView<TruthValue> friendMustView = new FilteredRelationView<TruthValue>(friend, (k, v) -> v.must());
207
208 Variable p1 = new Variable("p1");
209 Variable p2 = new Variable("p2");
210 List<Variable> parameters = Arrays.asList(p1, p2);
211
212 // Person-Person friendship
213 RelationAtom personRelationAtom1 = new RelationAtom(persionView, Arrays.asList(p1));
214 RelationAtom personRelationAtom2 = new RelationAtom(persionView, Arrays.asList(p2));
215 RelationAtom friendRelationAtom1 = new RelationAtom(friendMustView, Arrays.asList(p1, p2));
216 DNFAnd clause1 = new DNFAnd(Collections.emptySet(),
217 Arrays.asList(personRelationAtom1, personRelationAtom2, friendRelationAtom1));
218
219 // Animal-Animal friendship
220 RelationAtom animalRelationAtom1 = new RelationAtom(animalView, Arrays.asList(p1));
221 RelationAtom animalRelationAtom2 = new RelationAtom(animalView, Arrays.asList(p2));
222 RelationAtom friendRelationAtom2 = new RelationAtom(friendMustView, Arrays.asList(p1, p2));
223 DNFAnd clause2 = new DNFAnd(Collections.emptySet(),
224 Arrays.asList(animalRelationAtom1, animalRelationAtom2, friendRelationAtom2));
225
226 // No inter-species friendship
227
228 DNFPredicate predicate = new DNFPredicate("Or", parameters, Arrays.asList(clause1, clause2));
229
230 QueriableModelStore store = new QueriableModelStoreImpl(Set.of(person, animal, friend),
231 Set.of(persionView, animalView, friendMustView), Set.of(predicate));
232 QueriableModel model = store.createModel();
233
234 model.put(person, Tuple.of(0), true);
235 model.put(person, Tuple.of(1), true);
236 model.put(animal, Tuple.of(2), true);
237 model.put(animal, Tuple.of(3), true);
238 model.put(friend, Tuple.of(0, 1), TruthValue.TRUE);
239 model.put(friend, Tuple.of(0, 2), TruthValue.TRUE);
240 model.put(friend, Tuple.of(2, 3), TruthValue.TRUE);
241 model.put(friend, Tuple.of(3, 0), TruthValue.TRUE);
242
243 model.flushChanges();
244 assertEquals(2, model.countResults(predicate));
245 compareMatchSets(model.allResults(predicate),
246 Set.of(List.of(Tuple.of(0), Tuple.of(1)), List.of(Tuple.of(2), Tuple.of(3))));
247 }
248
249 @Test
250 void equalityTest() {
251 Relation<Boolean> person = new Relation<Boolean>("Person", 1, false);
252 RelationView<Boolean> persionView = new KeyOnlyRelationView(person);
253
254 Variable p1 = new Variable("p1");
255 Variable p2 = new Variable("p2");
256 List<Variable> parameters = Arrays.asList(p1, p2);
257
258 RelationAtom personRelationAtom1 = new RelationAtom(persionView, Arrays.asList(p1));
259 RelationAtom personRelationAtom2 = new RelationAtom(persionView, Arrays.asList(p2));
260 EquivalenceAtom equivalenceAtom = new EquivalenceAtom(true, p1, p2);
261 DNFAnd clause = new DNFAnd(Collections.emptySet(),
262 Arrays.asList(personRelationAtom1, personRelationAtom2, equivalenceAtom));
263 DNFPredicate predicate = new DNFPredicate("Equality", parameters, Arrays.asList(clause));
264
265 QueriableModelStore store = new QueriableModelStoreImpl(Set.of(person), Set.of(persionView), Set.of(predicate));
266 QueriableModel model = store.createModel();
267
268 model.put(person, Tuple.of(0), true);
269 model.put(person, Tuple.of(1), true);
270 model.put(person, Tuple.of(2), true);
271
272 model.flushChanges();
273 assertEquals(3, model.countResults(predicate));
274 compareMatchSets(model.allResults(predicate), Set.of(List.of(Tuple.of(0), Tuple.of(0)),
275 List.of(Tuple.of(1), Tuple.of(1)), List.of(Tuple.of(2), Tuple.of(2))));
276 }
277
278 @Test
279 void inequalityTest() {
280 Relation<Boolean> person = new Relation<Boolean>("Person", 1, false);
281 Relation<TruthValue> friend = new Relation<>("friend", 2, TruthValue.FALSE);
282 RelationView<Boolean> persionView = new KeyOnlyRelationView(person);
283 RelationView<TruthValue> friendMustView = new FilteredRelationView<TruthValue>(friend, (k, v) -> v.must());
284
285 Variable p1 = new Variable("p1");
286 Variable p2 = new Variable("p2");
287 Variable p3 = new Variable("p3");
288 List<Variable> parameters = Arrays.asList(p1, p2, p3);
289
290 RelationAtom personRelationAtom1 = new RelationAtom(persionView, Arrays.asList(p1));
291 RelationAtom personRelationAtom2 = new RelationAtom(persionView, Arrays.asList(p2));
292 RelationAtom friendRelationAtom1 = new RelationAtom(friendMustView, Arrays.asList(p1, p3));
293 RelationAtom friendRelationAtom2 = new RelationAtom(friendMustView, Arrays.asList(p2, p3));
294 EquivalenceAtom inequivalenceAtom = new EquivalenceAtom(false, p1, p2);
295 DNFAnd clause = new DNFAnd(Collections.emptySet(), Arrays.asList(personRelationAtom1, personRelationAtom2,
296 friendRelationAtom1, friendRelationAtom2, inequivalenceAtom));
297 DNFPredicate predicate = new DNFPredicate("Inequality", parameters, Arrays.asList(clause));
298
299 QueriableModelStore store = new QueriableModelStoreImpl(Set.of(person, friend),
300 Set.of(persionView, friendMustView), Set.of(predicate));
301 QueriableModel model = store.createModel();
302
303 model.put(person, Tuple.of(0), true);
304 model.put(person, Tuple.of(1), true);
305 model.put(person, Tuple.of(2), true);
306 model.put(friend, Tuple.of(0, 2), TruthValue.TRUE);
307 model.put(friend, Tuple.of(1, 2), TruthValue.TRUE);
308
309 model.flushChanges();
310 assertEquals(2, model.countResults(predicate));
311 compareMatchSets(model.allResults(predicate),
312 Set.of(List.of(Tuple.of(0), Tuple.of(1), Tuple.of(2)), List.of(Tuple.of(1), Tuple.of(0), Tuple.of(2))));
313 }
314
315 @Test
316 void patternCallTest() {
317 Relation<Boolean> person = new Relation<Boolean>("Person", 1, false);
318 Relation<TruthValue> friend = new Relation<>("friend", 2, TruthValue.FALSE);
319 RelationView<Boolean> persionView = new KeyOnlyRelationView(person);
320 RelationView<TruthValue> friendMustView = new FilteredRelationView<TruthValue>(friend, (k, v) -> v.must());
321
322 Variable p1 = new Variable("p1");
323 Variable p2 = new Variable("p2");
324 List<Variable> parameters = Arrays.asList(p1, p2);
325
326 RelationAtom personRelationAtom1 = new RelationAtom(persionView, Arrays.asList(p1));
327 RelationAtom personRelationAtom2 = new RelationAtom(persionView, Arrays.asList(p2));
328 RelationAtom friendRelationAtom = new RelationAtom(friendMustView, Arrays.asList(p1, p2));
329 DNFAnd clause = new DNFAnd(Collections.emptySet(),
330 Arrays.asList(personRelationAtom1, personRelationAtom2, friendRelationAtom));
331 DNFPredicate friendPredicate = new DNFPredicate("RelationConstraint", parameters, Arrays.asList(clause));
332
333 Variable p3 = new Variable("p3");
334 Variable p4 = new Variable("p4");
335 List<Variable> substitution = Arrays.asList(p3, p4);
336 RelationAtom personRelationAtom3 = new RelationAtom(persionView, Arrays.asList(p3));
337 RelationAtom personRelationAtom4 = new RelationAtom(persionView, Arrays.asList(p4));
338 PredicateAtom friendPredicateAtom = new PredicateAtom(true, false, friendPredicate, substitution);
339 DNFAnd patternCallClause = new DNFAnd(Collections.emptySet(),
340 Arrays.asList(personRelationAtom3, personRelationAtom4, friendPredicateAtom));
341 DNFPredicate predicate = new DNFPredicate("PatternCall", substitution, Arrays.asList(patternCallClause));
342
343 QueriableModelStore store = new QueriableModelStoreImpl(Set.of(person, friend),
344 Set.of(persionView, friendMustView), Set.of(friendPredicate, predicate));
345 QueriableModel model = store.createModel();
346
347 model.put(person, Tuple.of(0), true);
348 model.put(person, Tuple.of(1), true);
349 model.put(person, Tuple.of(2), true);
350 model.put(friend, Tuple.of(0, 1), TruthValue.TRUE);
351 model.put(friend, Tuple.of(1, 0), TruthValue.TRUE);
352 model.put(friend, Tuple.of(1, 2), TruthValue.TRUE);
353
354 model.flushChanges();
355
356 assertEquals(3, model.countResults(friendPredicate));
357 }
358
359 @Test
360 void negativePatternCallTest() {
361 Relation<Boolean> person = new Relation<Boolean>("Person", 1, false);
362 Relation<TruthValue> friend = new Relation<>("friend", 2, TruthValue.FALSE);
363 RelationView<Boolean> persionView = new KeyOnlyRelationView(person);
364 RelationView<TruthValue> friendMustView = new FilteredRelationView<TruthValue>(friend, (k, v) -> v.must());
365
366 Variable p1 = new Variable("p1");
367 Variable p2 = new Variable("p2");
368 List<Variable> parameters = Arrays.asList(p1, p2);
369
370 RelationAtom personRelationAtom1 = new RelationAtom(persionView, Arrays.asList(p1));
371 RelationAtom personRelationAtom2 = new RelationAtom(persionView, Arrays.asList(p2));
372 RelationAtom friendRelationAtom = new RelationAtom(friendMustView, Arrays.asList(p1, p2));
373 DNFAnd clause = new DNFAnd(Collections.emptySet(),
374 Arrays.asList(personRelationAtom1, personRelationAtom2, friendRelationAtom));
375 DNFPredicate friendPredicate = new DNFPredicate("RelationConstraint", parameters, Arrays.asList(clause));
376
377 Variable p3 = new Variable("p3");
378 Variable p4 = new Variable("p4");
379 List<Variable> substitution = Arrays.asList(p3, p4);
380 RelationAtom personRelationAtom3 = new RelationAtom(persionView, Arrays.asList(p3));
381 RelationAtom personRelationAtom4 = new RelationAtom(persionView, Arrays.asList(p4));
382 PredicateAtom friendPredicateAtom = new PredicateAtom(false, false, friendPredicate, substitution);
383 DNFAnd negativePatternCallClause = new DNFAnd(Collections.emptySet(),
384 Arrays.asList(personRelationAtom3, personRelationAtom4, friendPredicateAtom));
385 DNFPredicate predicate = new DNFPredicate("NegativePatternCall", substitution,
386 Arrays.asList(negativePatternCallClause));
387
388 QueriableModelStore store = new QueriableModelStoreImpl(Set.of(person, friend),
389 Set.of(persionView, friendMustView), Set.of(friendPredicate, predicate));
390 QueriableModel model = store.createModel();
391
392 model.put(person, Tuple.of(0), true);
393 model.put(person, Tuple.of(1), true);
394 model.put(person, Tuple.of(2), true);
395 model.put(friend, Tuple.of(0, 1), TruthValue.TRUE);
396 model.put(friend, Tuple.of(1, 0), TruthValue.TRUE);
397 model.put(friend, Tuple.of(1, 2), TruthValue.TRUE);
398
399 model.flushChanges();
400 assertEquals(6, model.countResults(predicate));
401 }
402
403 @Test
404 void transitivePatternCallTest() {
405 Relation<Boolean> person = new Relation<Boolean>("Person", 1, false);
406 Relation<TruthValue> friend = new Relation<>("friend", 2, TruthValue.FALSE);
407 RelationView<Boolean> persionView = new KeyOnlyRelationView(person);
408 RelationView<TruthValue> friendMustView = new FilteredRelationView<TruthValue>(friend, (k, v) -> v.must());
409
410 Variable p1 = new Variable("p1");
411 Variable p2 = new Variable("p2");
412 List<Variable> parameters = Arrays.asList(p1, p2);
413
414 RelationAtom personRelationAtom1 = new RelationAtom(persionView, Arrays.asList(p1));
415 RelationAtom personRelationAtom2 = new RelationAtom(persionView, Arrays.asList(p2));
416 RelationAtom friendRelationAtom = new RelationAtom(friendMustView, Arrays.asList(p1, p2));
417 DNFAnd clause = new DNFAnd(Collections.emptySet(),
418 Arrays.asList(personRelationAtom1, personRelationAtom2, friendRelationAtom));
419 DNFPredicate friendPredicate = new DNFPredicate("RelationConstraint", parameters, Arrays.asList(clause));
420
421 Variable p3 = new Variable("p3");
422 Variable p4 = new Variable("p4");
423 List<Variable> substitution = Arrays.asList(p3, p4);
424 RelationAtom personRelationAtom3 = new RelationAtom(persionView, Arrays.asList(p3));
425 RelationAtom personRelationAtom4 = new RelationAtom(persionView, Arrays.asList(p4));
426 PredicateAtom friendPredicateAtom = new PredicateAtom(true, true, friendPredicate, substitution);
427 DNFAnd patternCallClause = new DNFAnd(Collections.emptySet(),
428 Arrays.asList(personRelationAtom3, personRelationAtom4, friendPredicateAtom));
429 DNFPredicate predicate = new DNFPredicate("TransitivePatternCall", substitution,
430 Arrays.asList(patternCallClause));
431
432 QueriableModelStore store = new QueriableModelStoreImpl(Set.of(person, friend),
433 Set.of(persionView, friendMustView), Set.of(friendPredicate, predicate));
434 QueriableModel model = store.createModel();
435
436 model.put(person, Tuple.of(0), true);
437 model.put(person, Tuple.of(1), true);
438 model.put(person, Tuple.of(2), true);
439 model.put(friend, Tuple.of(0, 1), TruthValue.TRUE);
440 model.put(friend, Tuple.of(1, 2), TruthValue.TRUE);
441
442 model.flushChanges();
443 assertEquals(3, model.countResults(predicate));
444 }
445} \ No newline at end of file
diff --git a/subprojects/store/src/test/java/tools/refinery/store/query/test/QueryTransactionTest.java b/subprojects/store/src/test/java/tools/refinery/store/query/test/QueryTransactionTest.java
new file mode 100644
index 00000000..e72186b9
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/query/test/QueryTransactionTest.java
@@ -0,0 +1,58 @@
1package tools.refinery.store.query.test;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4
5import java.util.Arrays;
6import java.util.Collections;
7import java.util.List;
8import java.util.Set;
9
10import org.junit.jupiter.api.Test;
11
12import tools.refinery.store.model.Tuple;
13import tools.refinery.store.model.representation.Relation;
14import tools.refinery.store.query.QueriableModel;
15import tools.refinery.store.query.QueriableModelStore;
16import tools.refinery.store.query.QueriableModelStoreImpl;
17import tools.refinery.store.query.building.DNFAnd;
18import tools.refinery.store.query.building.DNFPredicate;
19import tools.refinery.store.query.building.RelationAtom;
20import tools.refinery.store.query.building.Variable;
21import tools.refinery.store.query.view.KeyOnlyRelationView;
22import tools.refinery.store.query.view.RelationView;
23
24class QueryTransactionTest {
25 @Test
26 void flushTest() {
27 Relation<Boolean> person = new Relation<>("Person", 1, false);
28 Relation<Boolean> asset = new Relation<>("Asset", 1, false);
29 RelationView<Boolean> persionView = new KeyOnlyRelationView(person);
30
31 List<Variable> parameters = Arrays.asList(new Variable("p1"));
32 RelationAtom personRelationAtom = new RelationAtom(persionView, parameters);
33 DNFAnd clause = new DNFAnd(Collections.emptySet(), Arrays.asList(personRelationAtom));
34 DNFPredicate predicate = new DNFPredicate("TypeConstraint", parameters, Arrays.asList(clause));
35
36 QueriableModelStore store = new QueriableModelStoreImpl(Set.of(person, asset), Set.of(persionView),
37 Set.of(predicate));
38 QueriableModel model = store.createModel();
39
40 assertEquals(0, model.countResults(predicate));
41
42 model.put(person, Tuple.of(0), true);
43 model.put(person, Tuple.of(1), true);
44 model.put(asset, Tuple.of(1), true);
45 model.put(asset, Tuple.of(2), true);
46
47 assertEquals(0, model.countResults(predicate));
48
49 model.flushChanges();
50 assertEquals(2, model.countResults(predicate));
51
52 model.put(person, Tuple.of(4), true);
53 assertEquals(2, model.countResults(predicate));
54
55 model.flushChanges();
56 assertEquals(3, model.countResults(predicate));
57 }
58}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/util/CollectionsUtilTests.java b/subprojects/store/src/test/java/tools/refinery/store/util/CollectionsUtilTests.java
new file mode 100644
index 00000000..171be0e5
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/util/CollectionsUtilTests.java
@@ -0,0 +1,78 @@
1package tools.refinery.store.util;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4import static tools.refinery.store.util.CollectionsUtil.filter;
5import static tools.refinery.store.util.CollectionsUtil.map;
6
7import java.util.ArrayList;
8import java.util.Iterator;
9import java.util.List;
10import java.util.NoSuchElementException;
11
12import org.junit.jupiter.api.Assertions;
13import org.junit.jupiter.api.Test;
14
15class CollectionsUtilTests {
16 List<Integer> list10 = List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
17 List<String> listTen = List.of("1", "2", "3", "4", "5", "6", "7", "8", "9", "10");
18
19 private static <T> void compare(Iterable<T> a, Iterable<T> b) {
20 List<T> listA = toList(a);
21 List<T> listB = toList(b);
22 assertEquals(listA, listB);
23 }
24
25 private static <T> List<T> toList(Iterable<T> a) {
26 List<T> result = new ArrayList<T>();
27 Iterator<T> iterator = a.iterator();
28 while (iterator.hasNext()) {
29 result.add(iterator.next());
30 }
31 return result;
32 }
33
34 @Test
35 void testFilterEven() {
36 compare(List.of(2, 4, 6, 8, 10), filter(list10, (x -> x % 2 == 0)));
37 }
38
39 @Test
40 void testFilterOdd() {
41 compare(List.of(1, 3, 5, 7, 9), filter(list10, (x -> x % 2 == 1)));
42 }
43
44 @Test
45 void testFilterFalse() {
46 compare(List.of(), filter(list10, (x -> false)));
47 }
48
49 @Test
50 void testFilterTrue() {
51 compare(list10, filter(list10, (x -> true)));
52 }
53
54 @Test
55 void testFilterEmpty() {
56 compare(List.of(), filter(List.of(), (x -> true)));
57 }
58
59 @Test()
60 void testNoSuchElement() {
61 Iterable<Integer> iterable = filter(list10, (x -> x % 2 == 0));
62 Iterator<Integer> iterator = iterable.iterator();
63 while (iterator.hasNext()) {
64 iterator.next();
65 }
66 Assertions.assertThrows(NoSuchElementException.class, () -> iterator.next());
67 }
68
69 @Test()
70 void mapTest() {
71 compare(listTen, map(list10, x -> x.toString()));
72 }
73
74 @Test()
75 void mapEmtyTest() {
76 compare(List.of(), map(List.of(), x -> x.toString()));
77 }
78}