aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--gradle/java-common.gradle4
-rw-r--r--gradle/xtext-common.gradle4
-rw-r--r--language/build.gradle4
-rw-r--r--model-data/build.gradle7
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/BooleanValue.java17
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/DataSymbol.java5
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/DefinedSymbol.java11
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/Logic2Valued.java9
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/Logic4Valued.java22
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/Model.java10
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/ModelObject.java5
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/NamedTruthValue.java13
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/PrimitiveSymbol.java5
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/Symbol.java5
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/TruthValue.java5
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java64
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java13
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java5
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java7
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java11
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java10
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java27
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java162
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java366
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java131
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java208
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java411
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java86
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java168
-rw-r--r--model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/CommitSmokeTest.java79
-rw-r--r--model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/DiffCursorSmokeTest.java101
-rw-r--r--model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/MutableImmutableCompareSmokeTest.java72
-rw-r--r--model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/MutableSmokeTest.java76
-rw-r--r--model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/RestoreSmokeTest.java92
-rw-r--r--model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/slow/SlowSmokeTest.java77
-rw-r--r--model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/utils/TestPermuter.java46
-rw-r--r--model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/utils/TestPermuterTest.java33
-rw-r--r--model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/support/MapTestEnvironment.java174
-rw-r--r--settings.gradle1
39 files changed, 2540 insertions, 6 deletions
diff --git a/gradle/java-common.gradle b/gradle/java-common.gradle
index 0cc09a4f..8a267e6f 100644
--- a/gradle/java-common.gradle
+++ b/gradle/java-common.gradle
@@ -27,6 +27,10 @@ jar {
27 } 27 }
28} 28}
29 29
30test {
31 useJUnitPlatform()
32}
33
30clean.doLast { 34clean.doLast {
31 delete 'src/main/xtend-gen' 35 delete 'src/main/xtend-gen'
32 delete 'src/test/xtend-gen' 36 delete 'src/test/xtend-gen'
diff --git a/gradle/xtext-common.gradle b/gradle/xtext-common.gradle
index cf6a5831..7fb2b2b5 100644
--- a/gradle/xtext-common.gradle
+++ b/gradle/xtext-common.gradle
@@ -10,8 +10,8 @@ sourceSets {
10 resources.srcDirs += ['src/main/xtext-gen'] 10 resources.srcDirs += ['src/main/xtext-gen']
11 } 11 }
12 test { 12 test {
13 java.srcDirs = ['src/test/xtext-gen'] 13 java.srcDirs += ['src/test/xtext-gen']
14 resources.srcDirs = ['src/test/xtext-gen'] 14 resources.srcDirs += ['src/test/xtext-gen']
15 } 15 }
16} 16}
17 17
diff --git a/language/build.gradle b/language/build.gradle
index 5ad5ab1f..a78eb24e 100644
--- a/language/build.gradle
+++ b/language/build.gradle
@@ -39,9 +39,5 @@ task generateXtextLanguage(type: JavaExec) {
39 args += "rootPath=/${projectDir}/.." 39 args += "rootPath=/${projectDir}/.."
40} 40}
41 41
42test {
43 useJUnitPlatform()
44}
45
46generateXtext.dependsOn(generateXtextLanguage) 42generateXtext.dependsOn(generateXtextLanguage)
47clean.dependsOn(cleanGenerateXtextLanguage) 43clean.dependsOn(cleanGenerateXtextLanguage)
diff --git a/model-data/build.gradle b/model-data/build.gradle
new file mode 100644
index 00000000..49056339
--- /dev/null
+++ b/model-data/build.gradle
@@ -0,0 +1,7 @@
1apply from: "${rootDir}/gradle/java-common.gradle"
2
3dependencies {
4 testCompile "org.junit.jupiter:junit-jupiter-api:${junitVersion}"
5 testRuntime "org.junit.jupiter:junit-jupiter-engine:${junitVersion}"
6 testCompile "org.junit.jupiter:junit-jupiter-params:${junitVersion}"
7}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/BooleanValue.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/BooleanValue.java
new file mode 100644
index 00000000..7b0e565b
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/BooleanValue.java
@@ -0,0 +1,17 @@
1package org.eclipse.viatra.solver.data;
2
3public class BooleanValue implements TruthValue {
4 private final boolean value;
5 protected BooleanValue(final boolean value) {
6 this.value = value;
7 }
8 public static final BooleanValue trueValue = new BooleanValue(true);
9 public static final BooleanValue falseValue = new BooleanValue(false);
10
11 @Override
12 public String getName() {
13 // TODO Auto-generated method stub
14 return Boolean.toString(value);
15 }
16
17}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/DataSymbol.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/DataSymbol.java
new file mode 100644
index 00000000..74624db6
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/DataSymbol.java
@@ -0,0 +1,5 @@
1package org.eclipse.viatra.solver.data;
2
3public class DataSymbol {
4
5}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/DefinedSymbol.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/DefinedSymbol.java
new file mode 100644
index 00000000..40d01721
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/DefinedSymbol.java
@@ -0,0 +1,11 @@
1package org.eclipse.viatra.solver.data;
2
3public class DefinedSymbol extends Symbol {
4 private final String name;
5 public DefinedSymbol(String name) {
6 this.name = name;
7 }
8 public String getName() {
9 return name;
10 }
11}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic2Valued.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic2Valued.java
new file mode 100644
index 00000000..7a807155
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic2Valued.java
@@ -0,0 +1,9 @@
1package org.eclipse.viatra.solver.data;
2
3public class Logic2Valued {
4 protected static final String trueName = "true";
5 protected static final String falseName = "false";
6
7 public static final TruthValue trueValue = new NamedTruthValue(trueName);
8 public static final TruthValue falseValue = new NamedTruthValue(falseName);
9}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic4Valued.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic4Valued.java
new file mode 100644
index 00000000..5f1e2bd8
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/Logic4Valued.java
@@ -0,0 +1,22 @@
1package org.eclipse.viatra.solver.data;
2
3public class Logic4Valued extends Logic2Valued {
4 protected static final String unknownName = "unknown";
5 protected static final String errorName = "error";
6
7 public static final TruthValue unknownValue = new NamedTruthValue(unknownName);
8 public static final TruthValue errorValue = new NamedTruthValue(errorName);
9
10// public TruthValue getImplMin(TruthValue a, TruthValue b) {
11//
12// }
13// public TruthValue getImplMax(TruthValue a, TruthValue b) {
14//
15// }
16// public TruthValue getInfoMin(TruthValue a, TruthValue b) {
17//
18// }
19// public TruthValue getInfoMax(TruthValue a, TruthValue b) {
20//
21// }
22}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/Model.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/Model.java
new file mode 100644
index 00000000..6f5c58ce
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/Model.java
@@ -0,0 +1,10 @@
1package org.eclipse.viatra.solver.data;
2
3import java.util.List;
4import java.util.Map;
5import java.util.Set;
6
7public class Model {
8 Set<ModelObject> objects;
9 Map<String,Map<List<ModelObject>,TruthValue>> interpretation;
10}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/ModelObject.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/ModelObject.java
new file mode 100644
index 00000000..73607f82
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/ModelObject.java
@@ -0,0 +1,5 @@
1package org.eclipse.viatra.solver.data;
2
3public class ModelObject {
4
5}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/NamedTruthValue.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/NamedTruthValue.java
new file mode 100644
index 00000000..be3a2351
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/NamedTruthValue.java
@@ -0,0 +1,13 @@
1package org.eclipse.viatra.solver.data;
2
3public class NamedTruthValue implements TruthValue {
4 private final String name;
5 public NamedTruthValue(String name) {
6 this.name = name;
7 }
8 @Override
9 public String getName() {
10 return this.name;
11 }
12
13}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/PrimitiveSymbol.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/PrimitiveSymbol.java
new file mode 100644
index 00000000..6bf0b195
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/PrimitiveSymbol.java
@@ -0,0 +1,5 @@
1package org.eclipse.viatra.solver.data;
2
3public class PrimitiveSymbol {
4
5}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/Symbol.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/Symbol.java
new file mode 100644
index 00000000..d403e181
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/Symbol.java
@@ -0,0 +1,5 @@
1package org.eclipse.viatra.solver.data;
2
3public class Symbol {
4
5}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/TruthValue.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/TruthValue.java
new file mode 100644
index 00000000..5dbde11c
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/TruthValue.java
@@ -0,0 +1,5 @@
1package org.eclipse.viatra.solver.data;
2
3interface TruthValue {
4 public String getName();
5}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java
new file mode 100644
index 00000000..79ca4412
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java
@@ -0,0 +1,64 @@
1package org.eclipse.viatra.solver.data.map;
2
3import org.eclipse.viatra.solver.data.map.internal.Node;
4
5/**
6 * A class representing an equivalence relation for a type {@code KEY} 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.effectiveBits;
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 (var i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) {
52 int hash1 = getEffectiveHash(key1, i);
53 int hash2 = getEffectiveHash(key2, i);
54 var result = Integer.compare(hash1, hash2);
55 if (result != 0) {
56 return result;
57 }
58 }
59 throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2
60 + ") have the same hashcode over the practical depth limitation ("
61 + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!");
62 }
63 }
64}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java
new file mode 100644
index 00000000..969f96c9
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Cursor.java
@@ -0,0 +1,13 @@
1package org.eclipse.viatra.solver.data.map;
2
3import java.util.List;
4
5public interface Cursor<KEY,VALUE> {
6 public KEY getKey();
7 public VALUE getValue();
8 public boolean isTerminated();
9 public boolean move();
10 public boolean isDirty();
11
12 public List<VersionedMap<KEY,VALUE>> getDependingMaps();
13}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java
new file mode 100644
index 00000000..2be2e024
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/DiffCursor.java
@@ -0,0 +1,5 @@
1package org.eclipse.viatra.solver.data.map;
2
3public interface DiffCursor<KEY, VALUE> extends Cursor<KEY,VALUE> {
4
5} \ No newline at end of file
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java
new file mode 100644
index 00000000..68970a94
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/Versioned.java
@@ -0,0 +1,7 @@
1package org.eclipse.viatra.solver.data.map;
2
3public interface Versioned {
4 public long commit();
5 //public void revert();
6 public void restore(long state);
7}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java
new file mode 100644
index 00000000..11077dca
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMap.java
@@ -0,0 +1,11 @@
1package org.eclipse.viatra.solver.data.map;
2
3public interface VersionedMap<KEY,VALUE> extends Versioned{
4 public void put(KEY key, VALUE value);
5 public VALUE get(KEY key);
6 public long getSize();
7
8 public Cursor<KEY,VALUE> getCursor();
9 public DiffCursor<KEY,VALUE> getDiffCursor(long state);
10 public void putAll(Cursor<KEY,VALUE> cursor);
11}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java
new file mode 100644
index 00000000..d92e5ad6
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStore.java
@@ -0,0 +1,10 @@
1package org.eclipse.viatra.solver.data.map;
2
3public interface VersionedMapStore<KEY, VALUE> {
4
5 public VersionedMap<KEY, VALUE> createMap();
6
7 public VersionedMap<KEY, VALUE> createMap(long state) throws IllegalAccessException;
8
9 public DiffCursor<KEY,VALUE> getDiffCursor(long fromState, long toState);
10} \ No newline at end of file
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java
new file mode 100644
index 00000000..196adf2c
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreConfiguration.java
@@ -0,0 +1,27 @@
1package org.eclipse.viatra.solver.data.map;
2
3public class VersionedMapStoreConfiguration {
4 /**
5 * If true root is replaced with immutable node when committed. Frees up memory
6 * by releasing immutable nodes, but it may decrease performance by recreating
7 * immutable nodes upon changes (some evidence).
8 */
9 public boolean immutableWhenCommiting = true;
10
11 /**
12 * If true, all subnodes are cached within a {@link VersionedMapStore}. It
13 * decreases the memory requirements. It may increase performance by discovering
14 * existing immutable copy of a node (some evidence). Additional overhead may
15 * decrease performance (no example found). The option permits the efficient
16 * implementation of version deletion.
17 */
18 public boolean sharedNodeCacheInStore = true;
19
20 /**
21 * If true, all subnodes are cached within a group of
22 * {@link VersionedMapStoreImpl#createSharedVersionedMapStores(int, ContinousHashProvider, Object, VersionedMapStoreConfiguration)}.
23 * If {@link VersionedMapStoreConfiguration#sharedNodeCacheInStore} is
24 * <code>false</code>, then it has currently no impact.
25 */
26 public boolean sharedNodeCacheInStoreGroups = true;
27}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java
new file mode 100644
index 00000000..c551ffe7
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java
@@ -0,0 +1,162 @@
1package org.eclipse.viatra.solver.data.map;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.HashMap;
6import java.util.List;
7import java.util.Map;
8import java.util.Set;
9
10import org.eclipse.viatra.solver.data.map.internal.ImmutableNode;
11import org.eclipse.viatra.solver.data.map.internal.MapDiffCursor;
12import org.eclipse.viatra.solver.data.map.internal.Node;
13import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
14
15public class VersionedMapStoreImpl<KEY,VALUE> implements VersionedMapStore<KEY, VALUE> {
16 // Configuration
17 final private boolean immutableWhenCommiting;
18
19 // Static data
20 protected final ContinousHashProvider<? super KEY> hashProvider;
21 protected final VALUE defaultValue;
22
23 // Dynamic data
24 final protected Map<Long, ImmutableNode<KEY,VALUE>> states;
25 final protected Map<Node<KEY,VALUE>, ImmutableNode<KEY,VALUE>> nodeCache;
26 protected long nextID;
27
28 public VersionedMapStoreImpl(
29 ContinousHashProvider<? super KEY> hashProvider,
30 VALUE defaultValue,
31 VersionedMapStoreConfiguration config)
32 {
33 this.immutableWhenCommiting = config.immutableWhenCommiting;
34
35 this.hashProvider = hashProvider;
36 this.defaultValue = defaultValue;
37
38 states = new HashMap<>();
39 nextID = 0;
40 if(config.sharedNodeCacheInStore) {
41 nodeCache = new HashMap<>();
42 } else {
43 nodeCache = null;
44 }
45 }
46 private VersionedMapStoreImpl(
47 ContinousHashProvider<? super KEY> hashProvider,
48 VALUE defaultValue,
49 Map<Node<KEY,VALUE>, ImmutableNode<KEY,VALUE>> nodeCache,
50 VersionedMapStoreConfiguration config)
51 {
52 this.immutableWhenCommiting = config.immutableWhenCommiting;
53
54 this.hashProvider = hashProvider;
55 this.defaultValue = defaultValue;
56
57 states = new HashMap<>();
58 nextID = 0;
59 this.nodeCache = nodeCache;
60 }
61
62 public VersionedMapStoreImpl(ContinousHashProvider<KEY> hashProvider, VALUE defaultValue) {
63 this(hashProvider,defaultValue,new VersionedMapStoreConfiguration());
64 }
65
66 public static <MAP,KEY,VALUE> List<VersionedMapStore<KEY,VALUE>> createSharedVersionedMapStores(
67 int amount,
68 ContinousHashProvider<? super KEY> hashProvider,
69 VALUE defaultValue,
70 VersionedMapStoreConfiguration config)
71 {
72 List<VersionedMapStore<KEY,VALUE>> result = new ArrayList<>(amount);
73 if(config.sharedNodeCacheInStoreGroups) {
74 Map<Node<KEY,VALUE>, ImmutableNode<KEY,VALUE>> nodeCache;
75 if(config.sharedNodeCacheInStore) {
76 nodeCache = new HashMap<>();
77 } else {
78 nodeCache = null;
79 }
80 for (int i = 0; i < amount; i++) {
81 result.add(new VersionedMapStoreImpl<KEY, VALUE>(hashProvider, defaultValue, nodeCache, config));
82 }
83 } else {
84 for (int i = 0; i < amount; i++) {
85 result.add(new VersionedMapStoreImpl<KEY, VALUE>(hashProvider, defaultValue, config));
86 }
87 }
88 return result;
89 }
90 public static <MAP,KEY,VALUE> List<VersionedMapStore<KEY,VALUE>> createSharedVersionedMapStores(
91 int amount,
92 ContinousHashProvider<? super KEY> hashProvider,
93 VALUE defaultValue)
94 {
95 return createSharedVersionedMapStores(amount,hashProvider,defaultValue,new VersionedMapStoreConfiguration());
96 }
97
98 synchronized Set<Long> getStates() {
99 return states.keySet();
100 }
101
102 @Override
103 public VersionedMap<KEY,VALUE> createMap() {
104 return new VersionedMapImpl<KEY,VALUE>(this,hashProvider,defaultValue);
105 }
106 @Override
107 public VersionedMap<KEY,VALUE> createMap(long state) {
108 ImmutableNode<KEY, VALUE> data = revert(state);
109 return new VersionedMapImpl<KEY,VALUE>(this,hashProvider,defaultValue,data);
110 }
111
112 synchronized public ImmutableNode<KEY,VALUE> revert(long state) {
113 if(states.containsKey(state)) {
114 return states.get(state);
115 } else {
116 ArrayList<Long> existingKeys = new ArrayList<Long>(states.keySet());
117 Collections.sort(existingKeys);
118 throw new IllegalArgumentException(
119 "Store does not contain state "+state+"! Avaliable states: "+existingKeys.toArray().toString());
120 }
121 }
122 synchronized public long commit(Node<KEY,VALUE> data, VersionedMapImpl<KEY, VALUE> mapToUpdateRoot) {
123 ImmutableNode<KEY,VALUE> immutable;
124 if(data != null) {
125 if(this.nodeCache != null) {
126 immutable = data.toImmutable(this.nodeCache);
127 } else {
128 immutable = data.toImmutable();
129 }
130 } else {
131 immutable = null;
132 }
133
134
135 if(nextID == Long.MAX_VALUE) throw new IllegalStateException(
136 "Map store run out of Id-s");
137 long id = nextID++;
138 this.states.put(id, immutable);
139 if(this.immutableWhenCommiting) {
140 mapToUpdateRoot.setRoot(immutable);
141 }
142 return id;
143 }
144
145// public Map<Node<KEY,VALUE>, ImmutableNode<KEY,VALUE>> getStore() {
146// return this.nodeCache;
147// }
148// public long addState(ImmutableNode<KEY,VALUE> data) {
149//
150// states.put(id,data);
151// return id;
152// }
153
154 @Override
155 public DiffCursor<KEY, VALUE> getDiffCursor(long fromState, long toState) {
156 VersionedMap<KEY, VALUE> map1 = createMap(fromState);
157 VersionedMap<KEY, VALUE> map2 = createMap(toState);
158 Cursor<KEY, VALUE> cursor1 = map1.getCursor();
159 Cursor<KEY, VALUE> cursor2 = map2.getCursor();
160 return new MapDiffCursor<KEY, VALUE>(this.hashProvider,this.defaultValue,cursor1,cursor2);
161 }
162}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
new file mode 100644
index 00000000..087c12a1
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
@@ -0,0 +1,366 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.Arrays;
4import java.util.Map;
5
6import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
7
8public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
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: (KEY,VALUE)*,NODE; NODES are stored backwards.
19 */
20 final Object[] content;
21
22 /**
23 * Hash code derived from immutable hash code
24 */
25 final int precalculatedHash;
26
27 private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) {
28 super();
29 this.dataMap = dataMap;
30 this.nodeMap = nodeMap;
31 this.content = content;
32 this.precalculatedHash = precalculatedHash;
33 }
34
35 /**
36 * Constructor that copies a mutable node to an immutable.
37 *
38 * @param node A mutable node.
39 * @param cache A cache of existing immutable nodes. It can be used to search
40 * and place reference immutable nodes. It can be null, if no cache
41 * available.
42 * @return an immutable version of the input node.
43 */
44 @SuppressWarnings("unchecked")
45 static <KEY,VALUE> ImmutableNode<KEY,VALUE> constructImmutable(MutableNode<KEY,VALUE> node, Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) {
46 // 1. try to return from cache
47 if(cache != null) {
48 ImmutableNode<KEY, VALUE> cachedResult = cache.get(node);
49 if(cachedResult != null) {
50 // 1.1 Already cached, return from cache.
51 return cachedResult;
52 }
53 }
54
55 // 2. otherwise construct a new ImmutableNode
56 int size = 0;
57 for(int i = 0; i<node.content.length; i++) {
58 if(node.content[i]!=null) {
59 size++;
60 }
61 }
62
63 int datas = 0;
64 int nodes = 0;
65 int resultDataMap = 0;
66 int resultNodeMap = 0;
67 final Object[] resultContent = new Object[size];
68 int bitposition = 1;
69 for(int i = 0; i<factor; i++) {
70 Object key = node.content[i*2];
71 if(key != null) {
72 resultDataMap |= bitposition;
73 resultContent[datas*2] = key;
74 resultContent[datas*2+1] = node.content[i*2+1];
75 datas++;
76 } else {
77 Node<KEY,VALUE> subnode = (Node<KEY, VALUE>) node.content[i*2+1];
78 if(subnode != null) {
79 ImmutableNode<KEY, VALUE> immutableSubnode = subnode.toImmutable(cache);
80 resultNodeMap |=bitposition;
81 resultContent[size-1-nodes] = immutableSubnode;
82 nodes++;
83 }
84 }
85 bitposition<<=1;
86 }
87 final int resultHash = node.hashCode();
88 ImmutableNode<KEY,VALUE> newImmutable = new ImmutableNode<>(resultDataMap, resultNodeMap, resultContent, resultHash);
89
90 // 3. save new immutable.
91 if(cache != null) {
92 cache.put(newImmutable, newImmutable);
93 }
94 return newImmutable;
95 }
96
97 private int index(int bitmap, int bitpos) {
98 return Integer.bitCount(bitmap & (bitpos-1));
99 }
100
101 @SuppressWarnings("unchecked")
102 @Override
103 public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) {
104 int selectedHashFragment = hashFragment(hash,shiftDepth(depth));
105 int bitposition = 1 << selectedHashFragment;
106 // If the key is stored as a data
107 if((dataMap & bitposition) != 0) {
108 int keyIndex = 2*index(dataMap, bitposition);
109 KEY keyCandidate = (KEY) content[keyIndex];
110 if(keyCandidate.equals(key)) {
111 return (VALUE) content[keyIndex+1];
112 } else {
113 return defaultValue;
114 }
115 }
116 // the key is stored as a node
117 else if((nodeMap & bitposition) != 0) {
118 int keyIndex = content.length-1-index(nodeMap, bitposition);
119 ImmutableNode<KEY,VALUE> subNode = (ImmutableNode<KEY,VALUE>) content[keyIndex];
120 int newDepth = depth+1;
121 int newHash = newHash(hashProvider, key, hash, newDepth);
122 return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth);
123 }
124 // the key is not stored at all
125 else {
126 return defaultValue;
127 }
128 }
129
130 @SuppressWarnings("unchecked")
131 @Override
132 public Node<KEY,VALUE> putValue(KEY key, VALUE value, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) {
133 int selectedHashFragment = hashFragment(hash,shiftDepth(depth));
134 int bitposition = 1 << selectedHashFragment;
135 if((dataMap & bitposition) != 0) {
136 int keyIndex = 2*index(dataMap, bitposition);
137 KEY keyCandidate = (KEY) content[keyIndex];
138 if(keyCandidate.equals(key)) {
139 if(value == defaultValue) {
140 // delete
141 MutableNode<KEY, VALUE> mutable = this.toMutable();
142 Node<KEY, VALUE> result = mutable.removeEntry(selectedHashFragment);
143 return result;
144 } else if(value == content[keyIndex+1]) {
145 // dont change
146 return this;
147 } else {
148 // update existing value
149 MutableNode<KEY, VALUE> mutable = this.toMutable();
150 Node<KEY, VALUE> result = mutable.updateValue(value, selectedHashFragment);
151 return result;
152 }
153 } else {
154 if(value == defaultValue) {
155 // dont change
156 return this;
157 } else {
158 // add new key + value
159 MutableNode<KEY, VALUE> mutable = this.toMutable();
160 Node<KEY, VALUE> result = mutable.putValue(key, value, hashProvider, defaultValue, hash, depth);
161 return result;
162 }
163 }
164 } else if((nodeMap & bitposition)!=0) {
165
166 int keyIndex = content.length-1-index(nodeMap, bitposition);
167 ImmutableNode<KEY,VALUE> subNode = (ImmutableNode<KEY,VALUE>) content[keyIndex];
168 int newDepth = depth+1;
169 int newHash = newHash(hashProvider, key, hash, newDepth);
170 Node<KEY,VALUE> newsubNode = subNode.putValue(key, value, hashProvider, defaultValue, newHash, newDepth);
171
172 if(subNode == newsubNode) {
173 // nothing changed
174 return this;
175 } else {
176 MutableNode<KEY, VALUE> mutable = toMutable();
177 Node<KEY, VALUE> result = mutable.updateSubNode(selectedHashFragment, newsubNode);
178 return result;
179 }
180 } else {
181 // add new key + value
182 MutableNode<KEY, VALUE> mutable = this.toMutable();
183 Node<KEY, VALUE> result = mutable.putValue(key, value, hashProvider, defaultValue, hash, depth);
184 return result;
185 }
186 }
187
188
189 @SuppressWarnings("unchecked")
190 @Override
191 public long getSize() {
192 int result = Integer.bitCount(this.dataMap);
193 for(int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) {
194 ImmutableNode<KEY,VALUE> subnode =
195 (ImmutableNode<KEY, VALUE>) this.content[this.content.length-1-subnodeIndex];
196 result += subnode.getSize();
197 }
198 return result;
199 }
200
201 @Override
202 protected MutableNode<KEY,VALUE> toMutable() {
203 return new MutableNode<KEY,VALUE>(this);
204 }
205
206 @Override
207 public ImmutableNode<KEY,VALUE> toImmutable() {
208 return this;
209 }
210
211 @Override
212 public ImmutableNode<KEY, VALUE> toImmutable(
213 Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) {
214 return this;
215 }
216
217 @SuppressWarnings("unchecked")
218 @Override
219 boolean moveToNext(MapCursor<KEY, VALUE> cursor) {
220 // 1. try to move to data
221 int datas = Integer.bitCount(this.dataMap);
222 if(cursor.dataIndex != MapCursor.IndexFinish) {
223 int newDataIndex = cursor.dataIndex + 1;
224 if(newDataIndex < datas) {
225 cursor.dataIndex = newDataIndex;
226 cursor.key = (KEY) this.content[newDataIndex*2];
227 cursor.value = (VALUE) this.content[newDataIndex*2+1];
228 return true;
229 } else {
230 cursor.dataIndex = MapCursor.IndexFinish;
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<KEY, VALUE> subnode = (Node<KEY, VALUE>) this.content[this.content.length-1-newNodeIndex];
240 cursor.dataIndex = MapCursor.IndexStart;
241 cursor.nodeIndexStack.pop();
242 cursor.nodeIndexStack.push(newNodeIndex);
243 cursor.nodeIndexStack.push(MapCursor.IndexStart);
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<KEY, VALUE> 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<KEY,VALUE> subNode = (Node<KEY, VALUE>) 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 int hashCode() {
303 return this.precalculatedHash;
304 }
305
306 @Override
307 public boolean equals(Object obj) {
308 if (this == obj)
309 return true;
310 if (obj == null)
311 return false;
312 if (obj instanceof ImmutableNode<?,?>) {
313 ImmutableNode<?,?> other = (ImmutableNode<?,?>) obj;
314 if (precalculatedHash != other.precalculatedHash)
315 return false;
316 if (dataMap != other.dataMap)
317 return false;
318 if (nodeMap != other.nodeMap)
319 return false;
320 if (!Arrays.deepEquals(content, other.content))
321 return false;
322 return true;
323 } else if(obj instanceof MutableNode<?,?>) {
324 return ImmutableNode.compareImmutableMutable(this, (MutableNode<?, ?>) obj);
325 } else {
326 return false;
327 }
328 }
329 public static boolean compareImmutableMutable(
330 ImmutableNode<?, ?> immutable,
331 MutableNode<?, ?> mutable)
332 {
333 int datas = 0;
334 int nodes = 0;
335 final int immutableLength = immutable.content.length;
336 for(int i = 0; i<factor; i++) {
337 Object key = mutable.content[i*2];
338 // For each key candidate
339 if(key != null) {
340 // Check whether a new Key-Value pair can fit into the immutable container
341 if(datas*2+nodes+2 <= immutableLength) {
342 if( !immutable.content[datas*2].equals(key) ||
343 !immutable.content[datas*2+1].equals(mutable.content[i*2+1]))
344 {
345 return false;
346 }
347 } else return false;
348 datas++;
349 } else {
350 Node<?,?> mutableSubnode = (Node<?, ?>) mutable.content[i*2+1];
351 if(mutableSubnode != null) {
352 if(datas*2+nodes+1 <= immutableLength) {
353 Object immutableSubnode = immutable.content[immutableLength-1-nodes];
354 if(!mutableSubnode.equals(immutableSubnode)) {
355 return false;
356 }
357 nodes++;
358 } else {
359 return false;
360 }
361 }
362 }
363 }
364 return true;
365 }
366}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
new file mode 100644
index 00000000..6c177611
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
@@ -0,0 +1,131 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.ArrayDeque;
4import java.util.ConcurrentModificationException;
5import java.util.Iterator;
6import java.util.List;
7
8import org.eclipse.viatra.solver.data.map.Cursor;
9import org.eclipse.viatra.solver.data.map.VersionedMap;
10
11public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> {
12 // Constants
13 static int IndexStart = -1;
14 static int IndexFinish = -2;
15
16 // Tree stack
17 ArrayDeque<Node<KEY,VALUE>> nodeStack;
18 ArrayDeque<Integer> nodeIndexStack;
19 int dataIndex;
20
21 // Values
22 KEY key;
23 VALUE value;
24
25 // Hash code for checking concurrent modifications
26 final VersionedMap<KEY,VALUE> map;
27 final int creationHash;
28
29 public MapCursor(Node<KEY, VALUE> root, VersionedMap<KEY,VALUE> 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(IndexStart);
37 }
38
39 this.dataIndex = IndexStart;
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 KEY getKey() {
51 return key;
52 }
53
54 public VALUE 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 = IndexFinish;
79 return move();
80 }
81 @Override
82 public boolean isDirty() {
83 return this.map.hashCode() != this.creationHash;
84 }
85 @Override
86 public List<VersionedMap<KEY, VALUE>> getDependingMaps() {
87 return List.of(this.map);
88 }
89
90 public static <KEY,VALUE> boolean sameSubnode(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> cursor2) {
91 Node<KEY, VALUE> nodeOfCursor1 = cursor1.nodeStack.peek();
92 Node<KEY, VALUE> 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 <KEY>
103 * @param <VALUE>
104 * @param cursor1
105 * @param cursor2
106 * @returnv 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 <KEY,VALUE> int compare(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> 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/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
new file mode 100644
index 00000000..8d7cda14
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java
@@ -0,0 +1,208 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.List;
4import java.util.stream.Collectors;
5import java.util.stream.Stream;
6
7import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
8import org.eclipse.viatra.solver.data.map.Cursor;
9import org.eclipse.viatra.solver.data.map.DiffCursor;
10import org.eclipse.viatra.solver.data.map.VersionedMap;
11
12/**
13 * A cursor representing the difference between two states of a map.
14 * @author Oszkar Semerath
15 *
16 */
17public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE>, Cursor<KEY,VALUE>{
18 /**
19 * Default value representing missing elements.
20 */
21 private VALUE defaultValue;
22 private MapCursor<KEY,VALUE> cursor1;
23 private MapCursor<KEY,VALUE> cursor2;
24 private ContinousHashProvider<? super KEY> hashProvider;
25
26 // Values
27 private KEY key;
28 private VALUE fromValue;
29 private VALUE toValue;
30
31 // State
32 /**
33 * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position.
34 */
35 private int cursorRelation;
36 /**
37 * Denotes a state when two cursors are in the same position, but they contain different keys.
38 * Possible values:
39 * <ul>
40 * <li>0: not stuck</li>
41 * <li>1: hashClash, next it should return the key of cursor 1.</li>
42 * <li>2: hashClash, next it should return the key of cursor 2.</li>
43 * </ul>
44 */
45 private int hashClash=0;
46
47 public MapDiffCursor(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, Cursor<KEY, VALUE> cursor1, Cursor<KEY, VALUE> cursor2) {
48 super();
49 this.hashProvider = hashProvider;
50 this.defaultValue = defaultValue;
51 this.cursor1 = (MapCursor<KEY, VALUE>) cursor1;
52 this.cursor2 = (MapCursor<KEY, VALUE>) cursor2;
53 }
54
55 public KEY getKey() {
56 return key;
57 }
58 public VALUE getFromValue() {
59 return fromValue;
60 }
61 public VALUE getToValue() {
62 return toValue;
63 }
64 @Override
65 public VALUE getValue() {
66 return getToValue();
67 }
68 public boolean isTerminated() {
69 return cursor1.isTerminated() && cursor2.isTerminated();
70 }
71 @Override
72 public boolean isDirty() {
73 return this.cursor1.isDirty() || this.cursor2.isDirty();
74 }
75 @Override
76 public List<VersionedMap<KEY, VALUE>> getDependingMaps() {
77 return Stream.concat(
78 cursor1.getDependingMaps().stream(),
79 cursor2.getDependingMaps().stream()
80 ).collect(Collectors.toList());
81 }
82
83 protected void updateState() {
84 if(!isTerminated()) {
85 this.cursorRelation = MapCursor.compare(cursor1, cursor2);
86 if(cursorRelation > 0 || cursor2.isTerminated()) {
87 this.key = cursor1.getKey();
88 this.fromValue = cursor1.getValue();
89 this.toValue = defaultValue;
90 } else if(cursorRelation < 0 || cursor1.isTerminated()){
91 this.key = cursor2.getKey();
92 this.fromValue = defaultValue;
93 this.toValue = cursor1.getValue();
94 } else {
95 // cursor1 = cursor2
96 if(cursor1.getKey().equals(cursor2.getKey())) {
97 this.key = cursor1.getKey();
98 this.fromValue = cursor1.getValue();
99 this.toValue = defaultValue;
100 } else {
101 resolveHashClash1();
102 }
103 }
104 }
105 }
106 protected void resolveHashClash1() {
107 int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key);
108 if(compareResult<0) {
109 this.hashClash = 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 = 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 protected boolean isInHashClash() {
125 return this.hashClash != 0;
126 }
127 protected void resolveHashClash2() {
128 if(hashClash == 1) {
129 this.hashClash = 0;
130 this.cursorRelation = 0;
131 this.key = cursor1.key;
132 this.fromValue = cursor1.value;
133 this.toValue = defaultValue;
134 } else if(hashClash == 2) {
135 this.hashClash = 0;
136 this.cursorRelation = 0;
137 this.key = cursor2.key;
138 this.fromValue = defaultValue;
139 this.toValue = cursor2.value;
140 } else throw new IllegalArgumentException("Inconsistent compare result for diffcursor");
141 }
142
143
144 protected boolean sameValues() {
145 return this.fromValue == this.toValue;
146 }
147 protected boolean moveOne() {
148 if(isTerminated()) {
149 return false;
150 }
151 if(this.cursorRelation > 0 || cursor2.isTerminated()) {
152 return cursor1.move();
153 } else if(this.cursorRelation < 0 || cursor1.isTerminated()) {
154 return cursor2.move();
155 } else {
156 boolean moved1 = cursor1.move();
157 boolean moved2 = cursor2.move();
158 return moved1 && moved2;
159 }
160 }
161 private boolean skipNode() {
162 if(isTerminated()) {
163 throw new IllegalStateException("DiffCursor tries to skip when terminated!");
164 }
165 boolean update1 = cursor1.skipCurrentNode();
166 boolean update2 = cursor2.skipCurrentNode();
167 updateState();
168 return update1 && update2;
169 }
170
171 protected boolean moveToConsistentState() {
172 if(!isTerminated()) {
173 boolean changed;
174 boolean lastResult = true;
175 do {
176 changed = false;
177 if(MapCursor.sameSubnode(cursor1, cursor2)) {
178 lastResult = skipNode();
179 changed = true;
180 }
181 if(sameValues()) {
182 lastResult = moveOne();
183 changed = true;
184 }
185 updateState();
186 } while(changed && !isTerminated());
187 return lastResult;
188 } else {
189 return false;
190 }
191 }
192
193 public boolean move() {
194 if(!isTerminated()) {
195 if(isInHashClash()) {
196 this.resolveHashClash2();
197 return true;
198 } else {
199 if(moveOne()) {
200 return moveToConsistentState();
201 } else {
202 return false;
203 }
204 }
205
206 } else return false;
207 }
208}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
new file mode 100644
index 00000000..963ce111
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
@@ -0,0 +1,411 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.Arrays;
4import java.util.Map;
5
6import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
7
8public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
9 int cachedHash;
10 protected Object[] content;
11
12 protected MutableNode() {
13 this.content = new Object[2*factor];
14 updateHash();
15 }
16 public static <KEY,VALUE> MutableNode<KEY,VALUE> initialize(
17 KEY key, VALUE value,
18 ContinousHashProvider<? super KEY> hashProvider,
19 VALUE defaultValue)
20 {
21 if(value == defaultValue) {
22 return null;
23 } else {
24 int hash = hashProvider.getHash(key, 0);
25 int fragment = hashFragment(hash, 0);
26 MutableNode<KEY, VALUE> res = new MutableNode<KEY, VALUE>();
27 res.content[2*fragment] = key;
28 res.content[2*fragment+1] = value;
29 res.updateHash();
30 return res;
31 }
32 }
33
34 /**
35 * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode}
36 * @param node
37 */
38 protected MutableNode(ImmutableNode<KEY,VALUE> node) {
39 this.content = new Object[2*factor];
40 int dataUsed=0;
41 int nodeUsed=0;
42 for(int i=0; i<factor; i++) {
43 int bitposition = 1 << i;
44 if((node.dataMap & bitposition) != 0) {
45 content[2*i] = node.content[dataUsed*2];
46 content[2*i+1] = node.content[dataUsed*2+1];
47 dataUsed++;
48 } else if((node.nodeMap & bitposition) != 0) {
49 content[2*i+1] = node.content[node.content.length-1-nodeUsed];
50 nodeUsed++;
51 }
52 }
53 this.cachedHash = node.hashCode();
54 }
55
56 @SuppressWarnings("unchecked")
57 @Override
58 public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) {
59 int selectedHashFragment = hashFragment(hash,shiftDepth(depth));
60 KEY keyCandidate = (KEY) this.content[2*selectedHashFragment];
61 if(keyCandidate != null) {
62 if(keyCandidate.equals(key)) {
63 return (VALUE) this.content[2*selectedHashFragment+1];
64 } else {
65 return defaultValue;
66 }
67 } else {
68 Node<KEY,VALUE> nodeCandidate = (Node<KEY,VALUE>) content[2*selectedHashFragment+1];
69 if(nodeCandidate != null) {
70 int newDepth = depth+1;
71 int newHash = newHash(hashProvider, key, hash, newDepth);
72 return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth);
73 } else {
74 return defaultValue;
75 }
76 }
77 }
78
79 private boolean hasContent() {
80 for(Object element : this.content) {
81 if(element != null) return true;
82 }
83 return false;
84 }
85
86 @SuppressWarnings("unchecked")
87 @Override
88 public Node<KEY,VALUE> putValue(KEY key, VALUE value, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) {
89 int selectedHashFragment = hashFragment(hash,shiftDepth(depth));
90 KEY keyCandidate = (KEY) content[2*selectedHashFragment];
91 if(keyCandidate != null) {
92 // If has key
93 if(keyCandidate.equals(key)) {
94 // The key is equals to an existing key -> update entry
95 if(value == defaultValue) {
96 return removeEntry(selectedHashFragment);
97 } else {
98 return updateValue(value,selectedHashFragment);
99 }
100 } else {
101 // The key is not equivalent to an existing key on the same hash bin
102 // -> split entry if it is necessary
103 if(value == defaultValue) {
104 // Value is default -> do not need to add new node
105 return this;
106 } else {
107 // Value is not default -> Split entry data to a new node
108 return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment);
109 }
110 }
111 } else {
112 // If it does not have key, check for value
113 Node<KEY,VALUE> nodeCandidate = (Node<KEY,VALUE>) content[2*selectedHashFragment+1];
114 if(nodeCandidate != null) {
115 // If it has value, it is a subnode -> upate that
116 Node<KEY, VALUE> newNode = nodeCandidate.putValue(key, value, hashProvider, defaultValue, newHash(hashProvider, key, hash, depth+1), depth+1);
117 return updateSubNode(selectedHashFragment,newNode);
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 return this;
123 } else {
124 return addEntry(key, value, selectedHashFragment);
125 }
126
127 }
128 }
129 }
130
131
132
133 private Node<KEY, VALUE> addEntry(KEY key, VALUE value, int selectedHashFragment) {
134 content[2*selectedHashFragment] = key;
135 content[2*selectedHashFragment+1] = value;
136 updateHash();
137 return this;
138 }
139 /**
140 * Updates an entry in a selected hash-fragment to a non-default value.
141 * @param value
142 * @param selectedHashFragment
143 * @return
144 */
145 Node<KEY, VALUE> updateValue(VALUE value, int selectedHashFragment) {
146 content[2*selectedHashFragment+1] = value;
147 updateHash();
148 return this;
149 }
150
151 /**
152 *
153 * @param selectedHashFragment
154 * @param newNode
155 * @return
156 */
157 Node<KEY, VALUE> updateSubNode(int selectedHashFragment, Node<KEY, VALUE> newNode) {
158 content[2*selectedHashFragment+1] = newNode;
159 for(int i = 0; i<this.content.length; i++) {
160 if(content[i]!=null) {
161 updateHash();
162 return this;
163 }
164 }
165 return null;
166 }
167
168 @SuppressWarnings("unchecked")
169 private Node<KEY, VALUE> moveDownAndSplit(
170 ContinousHashProvider<? super KEY> hashProvider,
171 KEY newKey, VALUE newValue, KEY previousKey,
172 int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth)
173 {
174 VALUE previousValue = (VALUE) content[2*selectedHashFragmentOfCurrentDepth+1];
175
176 //final int newHash = newHash(hashProvider, newKey, hashOfNewKey, newDepth);
177 MutableNode<KEY,VALUE> newSubNode = newNodeWithTwoEntries(
178 hashProvider,
179 previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)),
180 newKey, newValue, hashOfNewKey,
181 depth+1);
182
183 content[2*selectedHashFragmentOfCurrentDepth] = null;
184 content[2*selectedHashFragmentOfCurrentDepth+1] = newSubNode;
185 updateHash();
186 return this;
187 }
188 private MutableNode<KEY,VALUE> newNodeWithTwoEntries(
189 ContinousHashProvider<? super KEY> hashProvider,
190 KEY key1, VALUE value1, int oldHash1,
191 KEY key2, VALUE value2, int oldHash2,
192 int newdepth)
193 {
194// final int depthLimit = 4000;
195// if(newdepth>depthLimit) {
196// final int newHashes = 4000/numberOfFactors;
197// throw new IllegalArgumentException(
198// "Continuous hash was same " + newHashes + " times for non-equivalent objects " + key1 + " and " + key2 +".");
199// }
200 int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth);
201 int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth);
202 int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth));
203 int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth));
204
205 MutableNode<KEY,VALUE> subNode = new MutableNode<KEY,VALUE>();
206 if(newFragment1 != newFragment2) {
207 subNode.content[newFragment1*2]=key1;
208 subNode.content[newFragment1*2+1]=value1;
209
210 subNode.content[newFragment2*2]=key2;
211 subNode.content[newFragment2*2+1]=value2;
212 } else {
213 MutableNode<KEY,VALUE> subSubNode = newNodeWithTwoEntries(
214 hashProvider,
215 key1, value1, newHash1,
216 key2, value2, newHash2,
217 newdepth+1);
218 subNode.content[newFragment1*2+1] = subSubNode;
219 }
220 subNode.updateHash();
221 return subNode;
222 }
223
224 Node<KEY, VALUE> removeEntry(int selectedHashFragment) {
225 content[2*selectedHashFragment] = null;
226 content[2*selectedHashFragment+1] = null;
227 if(hasContent()) {
228 updateHash();
229 return this;
230 } else {
231 return null;
232 }
233 }
234
235 @SuppressWarnings("unchecked")
236 @Override
237 public long getSize() {
238 int size = 0;
239 for(int i=0; i<factor; i++) {
240 if(content[i*2]!=null) {
241 size++;
242 } else{
243 Node<KEY,VALUE> nodeCandidate = (Node<KEY, VALUE>) content[i*2+1];
244 if(nodeCandidate!=null) {
245 size+=nodeCandidate.getSize();
246 }
247 }
248 }
249 return size;
250 }
251
252 @Override
253 protected MutableNode<KEY,VALUE> toMutable() {
254 return this;
255 }
256
257 @Override
258 public ImmutableNode<KEY,VALUE> toImmutable() {
259 return ImmutableNode.constructImmutable(this,null);
260 }
261
262 @Override
263 public ImmutableNode<KEY, VALUE> toImmutable(Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) {
264 return ImmutableNode.constructImmutable(this,cache);
265 }
266
267 @SuppressWarnings("unchecked")
268 @Override
269 boolean moveToNext(MapCursor<KEY, VALUE> cursor) {
270 // 1. try to move to data
271 if(cursor.dataIndex != MapCursor.IndexFinish) {
272 for(int index = cursor.dataIndex+1; index < factor; index++) {
273 if(this.content[index*2]!=null) {
274 // 1.1 found next data
275 cursor.dataIndex = index;
276 cursor.key = (KEY) this.content[index*2];
277 cursor.value = (VALUE) this.content[index*2+1];
278 return true;
279 }
280 }
281 cursor.dataIndex = MapCursor.IndexFinish;
282 }
283
284 // 2. look inside the subnodes
285 for(int index = cursor.nodeIndexStack.peek()+1; index < factor; index++) {
286 if(this.content[index*2]==null && this.content[index*2+1] !=null) {
287 // 2.1 found next subnode, move down to the subnode
288 Node<KEY, VALUE> subnode = (Node<KEY, VALUE>) this.content[index*2+1];
289
290 cursor.dataIndex = MapCursor.IndexStart;
291 cursor.nodeIndexStack.pop();
292 cursor.nodeIndexStack.push(index);
293 cursor.nodeIndexStack.push(MapCursor.IndexStart);
294 cursor.nodeStack.push(subnode);
295
296
297 return subnode.moveToNext(cursor);
298 }
299 }
300 // 3. no subnode found, move up
301 cursor.nodeStack.pop();
302 cursor.nodeIndexStack.pop();
303 if(!cursor.nodeStack.isEmpty()) {
304 Node<KEY, VALUE> supernode = cursor.nodeStack.peek();
305 return supernode.moveToNext(cursor);
306 } else {
307 cursor.key = null;
308 cursor.value = null;
309 return false;
310 }
311 }
312
313 @Override
314 public void prettyPrint(StringBuilder builder, int depth, int code) {
315 for(int i = 0; i<depth; i++) {
316 builder.append("\t");
317 }
318 if(code>=0) {
319 builder.append(code);
320 builder.append(":");
321 }
322 builder.append("Mutable(");
323 // print content
324 boolean hadContent = false;
325 for(int i = 0; i<factor; i++) {
326 if(content[2*i] != null) {
327 if(hadContent) {
328 builder.append(",");
329 }
330 builder.append(i);
331 builder.append(":[");
332 builder.append(content[2*i].toString());
333 builder.append("]->[");
334 builder.append(content[2*i+1].toString());
335 builder.append("]");
336 hadContent = true;
337 }
338 }
339 builder.append(")");
340 // print subnodes
341 for(int i = 0; i<factor; i++) {
342 if(content[2*i] == null && content[2*i+1]!=null) {
343 @SuppressWarnings("unchecked")
344 Node<KEY,VALUE> subNode = (Node<KEY, VALUE>) content[2*i+1];
345 builder.append("\n");
346 subNode.prettyPrint(builder, depth+1, i);
347 }
348 }
349 }
350 @SuppressWarnings({"unchecked"})
351 @Override
352 public void checkIntegrity(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int depth) {
353 for(int i = 0; i<factor; i++) {
354 if(this.content[2*i] != null) {
355 KEY key = (KEY) this.content[2*i];
356 VALUE value = (VALUE) this.content[2*i+1];
357
358 if(value == defaultValue) {
359 throw new IllegalStateException("Node contains default value!");
360 }
361 int hashCode = hashProvider.getHash(key, hashDepth(depth));
362 int shiftDepth = shiftDepth(depth);
363 int selectedHashFragment = hashFragment(hashCode, shiftDepth);
364 if(i != selectedHashFragment) {
365 throw new IllegalStateException(
366 "Key "+key+" with hash code "+hashCode+" is in bad place! Fragment=" + selectedHashFragment +", Place="+i);
367 }
368 }
369 }
370 for(int i = 0; i<factor; i++) {
371 if(this.content[2*i+1] != null && this.content[2*i] == null) {
372 Node<KEY,VALUE> subNode = (Node<KEY, VALUE>) this.content[2*i+1];
373 subNode.checkIntegrity(hashProvider, defaultValue, depth+1);
374 }
375 }
376 int oldHash = this.cachedHash;
377 updateHash();
378 int newHash = this.cachedHash;
379 if(oldHash != newHash) {
380 throw new IllegalStateException("Hash code was not up to date! (old="+oldHash+",new="+newHash+")");
381 }
382 }
383
384
385 protected void updateHash() {
386 this.cachedHash = Arrays.hashCode(content);
387 }
388
389 @Override
390 public int hashCode() {
391 return this.cachedHash;
392 }
393
394
395 @Override
396 public boolean equals(Object obj) {
397 if (this == obj)
398 return true;
399 if (obj == null)
400 return false;
401 if (obj instanceof MutableNode<?, ?>) {
402 MutableNode<?,?> other = (MutableNode<?,?>) obj;
403 return Arrays.deepEquals(this.content, other.content);
404 } else if(obj instanceof ImmutableNode<?,?>) {
405 ImmutableNode<?,?> other = (ImmutableNode<?,?>) obj;
406 return ImmutableNode.compareImmutableMutable(other, this);
407 } else {
408 return false;
409 }
410 }
411}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java
new file mode 100644
index 00000000..3695825d
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java
@@ -0,0 +1,86 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.Map;
4
5import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
6
7public abstract class Node<KEY,VALUE>{
8 protected static final int branchingFactorBit = 5;
9 protected static final int factor = 1<<branchingFactorBit;
10 protected static final int numberOfFactors = Integer.SIZE / branchingFactorBit;
11 protected static final int factorMask = factor-1;
12 public static final int effectiveBits = branchingFactorBit * numberOfFactors;
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/numberOfFactors;
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%numberOfFactors;
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 && 5<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth);
39 return (hash >>> shiftDepth*branchingFactorBit) & factorMask;
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 KEY> hashProvider, KEY 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%numberOfFactors == 0?
55 hashProvider.getHash(key, hashDepth) :
56 hash;
57 }
58
59
60 abstract public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth);
61 abstract public Node<KEY,VALUE> putValue(KEY key, VALUE value, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth);
62 abstract public long getSize();
63
64 abstract MutableNode<KEY, VALUE> toMutable();
65 public abstract ImmutableNode<KEY, VALUE> toImmutable();
66 public abstract ImmutableNode<KEY, VALUE> toImmutable(
67 Map<Node<KEY, VALUE>,ImmutableNode<KEY, VALUE>> cache);
68
69 /**
70 * Moves a {@link MapCursor} to its next position.
71 * @param cursor the cursor
72 * @return Whether there was a next value to move on.
73 */
74 abstract boolean moveToNext(MapCursor<KEY,VALUE> cursor);
75
76 ///////// FOR printing
77 abstract public void prettyPrint(StringBuilder builder, int depth, int code);
78 @Override
79 public String toString() {
80 StringBuilder stringBuilder = new StringBuilder();
81 prettyPrint(stringBuilder, 0, -1);
82 return stringBuilder.toString();
83 }
84 public void checkIntegrity(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int depth) {}
85
86}
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java
new file mode 100644
index 00000000..715a9d74
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java
@@ -0,0 +1,168 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.Iterator;
4import java.util.LinkedList;
5import java.util.List;
6
7import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
8import org.eclipse.viatra.solver.data.map.Cursor;
9import org.eclipse.viatra.solver.data.map.DiffCursor;
10import org.eclipse.viatra.solver.data.map.VersionedMap;
11import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl;
12
13/**
14 * Not threadSafe in itself
15 * @author Oszkar Semerath
16 *
17 * @param <KEY>
18 * @param <VALUE>
19 */
20public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{
21 protected final VersionedMapStoreImpl<KEY,VALUE> store;
22
23 protected final ContinousHashProvider<? super KEY> hashProvider;
24 protected final VALUE defaultValue;
25 protected Node<KEY,VALUE> root;
26
27 public VersionedMapImpl(
28 VersionedMapStoreImpl<KEY,VALUE> store,
29 ContinousHashProvider<? super KEY> hashProvider,
30 VALUE defaultValue)
31 {
32 this.store = store;
33 this.hashProvider = hashProvider;
34 this.defaultValue = defaultValue;
35 this.root = null;
36 }
37 public VersionedMapImpl(
38 VersionedMapStoreImpl<KEY,VALUE> store,
39 ContinousHashProvider<? super KEY> hashProvider,
40 VALUE defaultValue, Node<KEY,VALUE> data)
41 {
42 this.store = store;
43 this.hashProvider = hashProvider;
44 this.defaultValue = defaultValue;
45 this.root = data;
46 }
47
48 public VALUE getDefaultValue() {
49 return defaultValue;
50 }
51 public ContinousHashProvider<? super KEY> getHashProvider() {
52 return hashProvider;
53 }
54 @Override
55 public void put(KEY key, VALUE value) {
56 if(root!=null) {
57 root = root.putValue(key, value, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0);
58 } else {
59 root = MutableNode.initialize(key, value, hashProvider, defaultValue);
60 }
61 }
62
63 @Override
64 public void putAll(Cursor<KEY, VALUE> cursor) {
65 if(cursor.getDependingMaps().contains(this)) {
66 List<KEY> keys = new LinkedList<>();
67 List<VALUE> values = new LinkedList<>();
68 while(cursor.move()) {
69 keys.add(cursor.getKey());
70 values.add(cursor.getValue());
71 }
72 Iterator<KEY> keyIterator = keys.iterator();
73 Iterator<VALUE> valueIterator = values.iterator();
74 while(keyIterator.hasNext()) {
75 this.put(keyIterator.next(), valueIterator.next());
76 }
77 } else {
78 while(cursor.move()) {
79 this.put(cursor.getKey(), cursor.getValue());
80 }
81 }
82 }
83
84 @Override
85 public VALUE get(KEY key) {
86 if(root!=null) {
87 return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0);
88 } else {
89 return defaultValue;
90 }
91 }
92 @Override
93 public long getSize() {
94 if(root == null) {
95 return 0;
96 } else {
97 return root.getSize();
98 }
99 }
100
101 @Override
102 public Cursor<KEY, VALUE> getCursor() {
103 MapCursor<KEY,VALUE> cursor = new MapCursor<>(this.root,this);
104 return cursor;
105 }
106 @Override
107 public DiffCursor<KEY, VALUE> getDiffCursor(long toVersion) {
108 Cursor<KEY, VALUE> fromCursor = this.getCursor();
109 VersionedMap<KEY, VALUE> toMap = this.store.createMap(toVersion);
110 Cursor<KEY, VALUE> toCursor = toMap.getCursor();
111 return new MapDiffCursor<KEY, VALUE>(this.hashProvider,this.defaultValue, fromCursor, toCursor);
112
113 }
114
115
116 @Override
117 public long commit() {
118 return this.store.commit(root,this);
119 }
120 public void setRoot(Node<KEY, VALUE> root) {
121 this.root = root;
122 }
123
124 @Override
125 public void restore(long state) {
126 root = this.store.revert(state);
127 }
128
129 @Override
130 public int hashCode() {
131 final int prime = 31;
132 int result = 1;
133 result = prime * result + ((root == null) ? 0 : root.hashCode());
134 return result;
135 }
136
137 @Override
138 public boolean equals(Object obj) {
139 if (this == obj)
140 return true;
141 if (obj == null)
142 return false;
143 if (getClass() != obj.getClass())
144 return false;
145 VersionedMapImpl<?,?> other = (VersionedMapImpl<?,?>) obj;
146 if (root == null) {
147 if (other.root != null)
148 return false;
149 } else if (!root.equals(other.root))
150 return false;
151 return true;
152 }
153 public void prettyPrint() {
154 StringBuilder s = new StringBuilder();
155 if(this.root != null) {
156 this.root.prettyPrint(s, 0, -1);
157 System.out.println(s.toString());
158 } else {
159 System.out.println("empty tree");
160 }
161 }
162 public void checkIntegrity() {
163 if(this.root != null) {
164 this.root.checkIntegrity(hashProvider, defaultValue, 0);
165 }
166 }
167
168}
diff --git a/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/CommitSmokeTest.java b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/CommitSmokeTest.java
new file mode 100644
index 00000000..5c340090
--- /dev/null
+++ b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/CommitSmokeTest.java
@@ -0,0 +1,79 @@
1package org.eclipse.viatra.solver.data.map.tests.smoke.fast;
2
3import static org.junit.jupiter.api.Assertions.fail;
4
5import java.util.Random;
6import java.util.stream.Stream;
7
8import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
9import org.eclipse.viatra.solver.data.map.VersionedMapStore;
10import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl;
11import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
12import org.eclipse.viatra.solver.data.map.tests.smoke.utils.TestPermuter;
13import org.eclipse.viatra.solver.data.map.tests.support.MapTestEnvironment;
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
19public class CommitSmokeTest {
20 public void runSmokeTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
21 boolean evilHash) {
22 String[] values = MapTestEnvironment.prepareValues(maxValue);
23 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
24
25 VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
26 VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap();
27 MapTestEnvironment<Integer, String> e = new MapTestEnvironment<Integer, String>(sut);
28
29 Random r = new Random(seed);
30
31 iterativeRandomPutsAndCommits(scenario, steps, maxKey, values, e, r, commitFrequency);
32 }
33
34 private void iterativeRandomPutsAndCommits(String scenario, int steps, int maxKey, String[] values,
35 MapTestEnvironment<Integer, String> e, Random r, int commitFrequency) {
36 int stopAt = -1;
37 for (int i = 0; i < steps; i++) {
38 int index = i + 1;
39 int nextKey = r.nextInt(maxKey);
40 String nextValue = values[r.nextInt(values.length)];
41 if (index == stopAt) {
42 System.out.println("issue!");
43 System.out.println("State before:");
44 e.printComparison();
45 e.sut.prettyPrint();
46 System.out.println("Next: put(" + nextKey + "," + nextValue + ")");
47 }
48 try {
49 e.put(nextKey, nextValue);
50 if (index == stopAt) {
51 e.sut.prettyPrint();
52 }
53 e.checkEquivalence(scenario + ":" + index);
54 } catch (Exception exception) {
55 exception.printStackTrace();
56 fail(scenario + ":" + index + ": exception happened: " + exception);
57 }
58 MapTestEnvironment.printStatus(scenario, index, steps, null);
59 if (index % commitFrequency == 0) {
60 e.sut.commit();
61 }
62 }
63 }
64
65 @ParameterizedTest(name = "Immutable Smoke {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
66 @MethodSource
67 @Timeout(value = 10)
68 public void parametrizedSmoke(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
69 boolean evilHash) {
70 runSmokeTest("SmokeCommitS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
71 commitFrequency, evilHash);
72 }
73
74 public static Stream<Arguments> parametrizedSmoke() {
75 return TestPermuter.permutationWithSize(new Object[] { 1000 }, new Object[] { 3, 32, 32 * 32 },
76 new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
77 new Object[] { false, true });
78 }
79}
diff --git a/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/DiffCursorSmokeTest.java b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/DiffCursorSmokeTest.java
new file mode 100644
index 00000000..ef51d05e
--- /dev/null
+++ b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/DiffCursorSmokeTest.java
@@ -0,0 +1,101 @@
1package org.eclipse.viatra.solver.data.map.tests.smoke.fast;
2
3import static org.junit.jupiter.api.Assertions.fail;
4
5import java.util.Random;
6import java.util.stream.Stream;
7
8import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
9import org.eclipse.viatra.solver.data.map.DiffCursor;
10import org.eclipse.viatra.solver.data.map.VersionedMapStore;
11import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl;
12import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
13import org.eclipse.viatra.solver.data.map.tests.smoke.utils.TestPermuter;
14import org.eclipse.viatra.solver.data.map.tests.support.MapTestEnvironment;
15import org.junit.jupiter.api.Timeout;
16import org.junit.jupiter.params.ParameterizedTest;
17import org.junit.jupiter.params.provider.Arguments;
18import org.junit.jupiter.params.provider.MethodSource;
19
20public class DiffCursorSmokeTest {
21 public void runSmokeTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
22 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 iterativeRandomPutsAndCommitsThenDiffcursor(scenario, store, steps, maxKey, values, seed, commitFrequency);
28 }
29
30 void iterativeRandomPutsAndCommitsThenDiffcursor(String scenario, VersionedMapStore<Integer, String> store,
31 int steps, int maxKey, String[] values, int seed, int commitFrequency) {
32 // 1. build a map with versions
33 Random r = new Random(seed);
34 VersionedMapImpl<Integer, String> versioned = (VersionedMapImpl<Integer, String>) store.createMap();
35 int largestCommit = -1;
36
37 for (int i = 0; i < steps; i++) {
38 int index = i + 1;
39 int nextKey = r.nextInt(maxKey);
40 String nextValue = values[r.nextInt(values.length)];
41 try {
42 versioned.put(nextKey, nextValue);
43 } catch (Exception exception) {
44 exception.printStackTrace();
45 fail(scenario + ":" + index + ": exception happened: " + exception);
46 }
47 if (index % commitFrequency == 0) {
48 long version = versioned.commit();
49 largestCommit = (int) version;
50 }
51 if (index % 10000 == 0)
52 System.out.println(scenario + ":" + index + "/" + steps + " building finished");
53 }
54 // 2. create a non-versioned map,
55 VersionedMapImpl<Integer, String> moving = (VersionedMapImpl<Integer, String>) store.createMap();
56 Random r2 = new Random(seed + 1);
57
58 final int diffTravelFrequency = commitFrequency * 2;
59 for (int i = 0; i < steps; i++) {
60 int index = i + 1;
61 if (index % diffTravelFrequency == 0) {
62 // difftravel
63 long travelToVersion = r2.nextInt(largestCommit + 1);
64 DiffCursor<Integer, String> diffCursor = moving.getDiffCursor(travelToVersion);
65 moving.putAll(diffCursor);
66
67 } else {
68 // random puts
69 int nextKey = r2.nextInt(maxKey);
70 String nextValue = values[r2.nextInt(values.length)];
71 try {
72 moving.put(nextKey, nextValue);
73 } catch (Exception exception) {
74 exception.printStackTrace();
75 fail(scenario + ":" + index + ": exception happened: " + exception);
76 }
77 if (index % commitFrequency == 0) {
78 versioned.commit();
79 }
80 if (index % 10000 == 0)
81 System.out.println(scenario + ":" + index + "/" + steps + " building finished");
82 }
83 }
84
85 }
86
87 @ParameterizedTest(name = "Mutable-Immutable Compare Smoke {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
88 @MethodSource
89 @Timeout(value = 10)
90 void parametrizedSmoke(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
91 boolean evilHash) {
92 runSmokeTest("SmokeMutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
93 noKeys, noValues, commitFrequency, evilHash);
94 }
95
96 public static Stream<Arguments> parametrizedSmoke() {
97 return TestPermuter.permutationWithSize(new Object[] { 1000 }, new Object[] { 3, 32, 32 * 32 },
98 new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
99 new Object[] { false, true });
100 }
101}
diff --git a/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/MutableImmutableCompareSmokeTest.java b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/MutableImmutableCompareSmokeTest.java
new file mode 100644
index 00000000..ac5571b3
--- /dev/null
+++ b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/MutableImmutableCompareSmokeTest.java
@@ -0,0 +1,72 @@
1package org.eclipse.viatra.solver.data.map.tests.smoke.fast;
2
3import static org.junit.jupiter.api.Assertions.fail;
4
5import java.util.Random;
6import java.util.stream.Stream;
7
8import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
9import org.eclipse.viatra.solver.data.map.VersionedMapStore;
10import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl;
11import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
12import org.eclipse.viatra.solver.data.map.tests.smoke.utils.TestPermuter;
13import org.eclipse.viatra.solver.data.map.tests.support.MapTestEnvironment;
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
19public class MutableImmutableCompareSmokeTest {
20 public void runSmokeTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency,
21 boolean evilHash) {
22 String[] values = MapTestEnvironment.prepareValues(maxValue);
23 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
24
25 VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
26 VersionedMapImpl<Integer, String> immutable = (VersionedMapImpl<Integer, String>) store.createMap();
27 VersionedMapImpl<Integer, String> mutable = (VersionedMapImpl<Integer, String>) store.createMap();
28
29 Random r = new Random(seed);
30
31 iterativeRandomPutsAndCommitsAndCompare(scenario, immutable, mutable, steps, maxKey, values, r,
32 commitFrequency);
33 }
34
35 void iterativeRandomPutsAndCommitsAndCompare(String scenario, VersionedMapImpl<Integer, String> immutable,
36 VersionedMapImpl<Integer, String> mutable, int steps, int maxKey, String[] values, Random r,
37 int commitFrequency) {
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 try {
43 immutable.put(nextKey, nextValue);
44 mutable.put(nextKey, nextValue);
45 } catch (Exception exception) {
46 exception.printStackTrace();
47 fail(scenario + ":" + index + ": exception happened: " + exception);
48 }
49 if (index % commitFrequency == 0) {
50 immutable.commit();
51 }
52 MapTestEnvironment.compareTwoMaps(scenario + ":" + index, immutable, mutable);
53
54 MapTestEnvironment.printStatus(scenario, index, steps, null);
55 }
56 }
57
58 @ParameterizedTest(name = "Mutable-Immutable Compare Smoke {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
59 @MethodSource
60 @Timeout(value = 10)
61 void parametrizedSmoke(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
62 boolean evilHash) {
63 runSmokeTest("SmokeMutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
64 noKeys, noValues, commitFrequency, evilHash);
65 }
66
67 public static Stream<Arguments> parametrizedSmoke() {
68 return TestPermuter.permutationWithSize(new Object[] { 1000 }, new Object[] { 3, 32, 32 * 32 },
69 new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
70 new Object[] { false, true });
71 }
72}
diff --git a/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/MutableSmokeTest.java b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/MutableSmokeTest.java
new file mode 100644
index 00000000..c24c220d
--- /dev/null
+++ b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/MutableSmokeTest.java
@@ -0,0 +1,76 @@
1package org.eclipse.viatra.solver.data.map.tests.smoke.fast;
2
3import static org.junit.jupiter.api.Assertions.fail;
4
5import java.util.Random;
6import java.util.stream.Stream;
7
8import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
9import org.eclipse.viatra.solver.data.map.VersionedMapStore;
10import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl;
11import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
12import org.eclipse.viatra.solver.data.map.tests.smoke.utils.TestPermuter;
13import org.eclipse.viatra.solver.data.map.tests.support.MapTestEnvironment;
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
19public class MutableSmokeTest {
20
21 public void runSmokeTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean evilHash) {
22 String[] values = MapTestEnvironment.prepareValues(maxValue);
23 ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash);
24
25 VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]);
26 VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap();
27 MapTestEnvironment<Integer, String> e = new MapTestEnvironment<Integer, String>(sut);
28
29 Random r = new Random(seed);
30
31 iterativeRandomPuts(scenario, steps, maxKey, values, e, r);
32 }
33
34 void iterativeRandomPuts(String scenario, int steps, int maxKey, String[] values,
35 MapTestEnvironment<Integer, String> e, Random r) {
36 int stopAt = -1;
37 for (int i = 0; i < steps; i++) {
38 int index = i + 1;
39 int nextKey = r.nextInt(maxKey);
40 String nextValue = values[r.nextInt(values.length)];
41 if (index == stopAt) {
42 System.out.println("issue!");
43 System.out.println("State before:");
44 e.printComparison();
45 e.sut.prettyPrint();
46 System.out.println("Next: put(" + nextKey + "," + nextValue + ")");
47 }
48 try {
49 e.put(nextKey, nextValue);
50 if (index == stopAt) {
51 e.sut.prettyPrint();
52 }
53 e.checkEquivalence(scenario + ":" + index);
54 } catch (Exception exception) {
55 exception.printStackTrace();
56 fail(scenario + ":" + index + ": exception happened: " + exception);
57 }
58 MapTestEnvironment.printStatus(scenario, index, steps, null);
59 }
60 }
61
62 @ParameterizedTest(name = "Mutable Smoke {index}/{0} Steps={1} Keys={2} Values={3} seed={4} evil-hash={5}")
63 @MethodSource
64 @Timeout(value = 10)
65 void parametrizedSmoke(int test, int steps, int noKeys, int noValues, int seed, boolean evilHash) {
66 runSmokeTest(
67 "SmokeS" + steps + "K" + noKeys + "V" + noValues + "s" + seed + "H" + (evilHash ? "Evil" : "Normal"),
68 seed, steps, noKeys, noValues, evilHash);
69 }
70
71 public static Stream<Arguments> parametrizedSmoke() {
72 return TestPermuter.permutationWithSize(new Object[] { 1000 },
73 new Object[] { 3, 32, 32 * 32, 32 * 32 * 32 * 32 }, new Object[] { 2, 3 }, new Object[] { 1, 2, 3 },
74 new Object[] { false, true });
75 }
76}
diff --git a/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/RestoreSmokeTest.java b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/RestoreSmokeTest.java
new file mode 100644
index 00000000..4ca9b088
--- /dev/null
+++ b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/fast/RestoreSmokeTest.java
@@ -0,0 +1,92 @@
1package org.eclipse.viatra.solver.data.map.tests.smoke.fast;
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.eclipse.viatra.solver.data.map.ContinousHashProvider;
11import org.eclipse.viatra.solver.data.map.VersionedMapStore;
12import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl;
13import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
14import org.eclipse.viatra.solver.data.map.tests.smoke.utils.TestPermuter;
15import org.eclipse.viatra.solver.data.map.tests.support.MapTestEnvironment;
16import org.junit.jupiter.api.Timeout;
17import org.junit.jupiter.params.ParameterizedTest;
18import org.junit.jupiter.params.provider.Arguments;
19import org.junit.jupiter.params.provider.MethodSource;
20
21public class RestoreSmokeTest {
22 public void runSmokeTest(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
29 iterativeRandomPutsAndCommitsThenRestore(scenario, store, steps, maxKey, values, seed, commitFrequency);
30 }
31
32 void iterativeRandomPutsAndCommitsThenRestore(String scenario, VersionedMapStore<Integer, String> store, int steps,
33 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 Map<Integer, Long> index2Version = new HashMap<>();
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 index2Version.put(i, version);
52 }
53 MapTestEnvironment.printStatus(scenario, index, steps, "building");
54 }
55 // 2. create a non-versioned and
56 VersionedMapImpl<Integer, String> reference = (VersionedMapImpl<Integer, String>) store.createMap();
57 r = new Random(seed);
58
59 for (int i = 0; i < steps; i++) {
60 int index = i + 1;
61 int nextKey = r.nextInt(maxKey);
62 String nextValue = values[r.nextInt(values.length)];
63 try {
64 reference.put(nextKey, nextValue);
65 } catch (Exception exception) {
66 exception.printStackTrace();
67 fail(scenario + ":" + index + ": exception happened: " + exception);
68 }
69 if (index % commitFrequency == 0) {
70 versioned.restore(index2Version.get(i));
71 MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference, versioned);
72 }
73 MapTestEnvironment.printStatus(scenario, index, steps, "comparison");
74 }
75
76 }
77
78 @ParameterizedTest(name = "Mutable-Immutable Compare Smoke {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
79 @MethodSource
80 @Timeout(value = 10)
81 void parametrizedSmoke(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed,
82 boolean evilHash) {
83 runSmokeTest("SmokeMutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
84 noKeys, noValues, commitFrequency, evilHash);
85 }
86
87 public static Stream<Arguments> parametrizedSmoke() {
88 return TestPermuter.permutationWithSize(new Object[] { 1000 }, new Object[] { 3, 32, 32 * 32 },
89 new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 },
90 new Object[] { false, true });
91 }
92}
diff --git a/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/slow/SlowSmokeTest.java b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/slow/SlowSmokeTest.java
new file mode 100644
index 00000000..004d30d9
--- /dev/null
+++ b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/slow/SlowSmokeTest.java
@@ -0,0 +1,77 @@
1package org.eclipse.viatra.solver.data.map.tests.smoke.slow;
2
3import java.util.Arrays;
4import java.util.stream.Stream;
5
6import org.eclipse.viatra.solver.data.map.tests.smoke.fast.CommitSmokeTest;
7import org.eclipse.viatra.solver.data.map.tests.smoke.fast.MutableImmutableCompareSmokeTest;
8import org.eclipse.viatra.solver.data.map.tests.smoke.fast.MutableSmokeTest;
9import org.eclipse.viatra.solver.data.map.tests.smoke.fast.RestoreSmokeTest;
10import org.junit.jupiter.api.Disabled;
11import org.junit.jupiter.params.ParameterizedTest;
12import org.junit.jupiter.params.provider.Arguments;
13import org.junit.jupiter.params.provider.MethodSource;
14
15@Disabled
16public class SlowSmokeTest {
17
18 private static int slowStepCount = 32 * 32 * 32 * 32;
19
20 private static Stream<Arguments> changeStepCount(Stream<Arguments> arguments) {
21 return arguments.map(x -> Arguments.of(updatedStepCount(x.get())));
22
23 }
24
25 private static Object[] updatedStepCount(Object[] arguments) {
26 Object[] copy = Arrays.copyOf(arguments, arguments.length);
27 copy[1] = slowStepCount;
28 return copy;
29 }
30
31 @ParameterizedTest(name = "Mutable Smoke {index}/{0} Steps={1} Keys={2} Values={3} seed={4} evil-hash={5}")
32 @MethodSource
33 void smoke1(int test, int steps, int noKeys, int noValues, int seed, boolean evilHash) {
34 (new MutableSmokeTest()).runSmokeTest(
35 "SmokeS" + steps + "K" + noKeys + "V" + noValues + "s" + seed + "H" + (evilHash ? "Evil" : "Normal"),
36 seed, steps, noKeys, noValues, evilHash);
37 }
38
39 private static Stream<Arguments> smoke1() {
40 return changeStepCount(MutableSmokeTest.parametrizedSmoke());
41 }
42
43 @ParameterizedTest(name = "Immutable Smoke {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
44 @MethodSource
45 void smoke2(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, boolean evilHash) {
46 (new CommitSmokeTest()).runSmokeTest("SmokeCommitS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed,
47 steps, noKeys, noValues, commitFrequency, evilHash);
48 }
49
50 private static Stream<Arguments> smoke2() {
51 return changeStepCount(CommitSmokeTest.parametrizedSmoke());
52 }
53
54 @ParameterizedTest(name = "Mutable-Immutable Compare Smoke {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
55 @MethodSource
56 void smoke3(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, boolean evilHash) {
57 (new MutableImmutableCompareSmokeTest()).runSmokeTest(
58 "SmokeMutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
59 noKeys, noValues, commitFrequency, evilHash);
60 }
61
62 private static Stream<Arguments> smoke3() {
63 return changeStepCount(MutableImmutableCompareSmokeTest.parametrizedSmoke());
64 }
65
66 @ParameterizedTest(name = "Mutable-Immutable Compare Smoke {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}")
67 @MethodSource
68 void smoke4(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, boolean evilHash) {
69 (new RestoreSmokeTest()).runSmokeTest(
70 "SmokeMutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
71 noKeys, noValues, commitFrequency, evilHash);
72 }
73
74 private static Stream<Arguments> smoke4() {
75 return changeStepCount(RestoreSmokeTest.parametrizedSmoke());
76 }
77}
diff --git a/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/utils/TestPermuter.java b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/utils/TestPermuter.java
new file mode 100644
index 00000000..0f7b4642
--- /dev/null
+++ b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/utils/TestPermuter.java
@@ -0,0 +1,46 @@
1package org.eclipse.viatra.solver.data.map.tests.smoke.utils;
2
3import java.util.LinkedList;
4import java.util.List;
5import java.util.stream.Stream;
6
7import org.junit.jupiter.params.provider.Arguments;
8
9public class TestPermuter {
10 static List<List<Object>> permutationInternal(int from, Object[]... valueOption) {
11 if (valueOption.length == from) {
12 return List.of(List.of());
13 } else {
14 Object[] permuteThis = valueOption[from];
15 List<List<Object>> otherCombination = permutationInternal(from + 1, valueOption);
16 List<List<Object>> result = new LinkedList<>();
17 for (Object permuteThisElement : permuteThis) {
18 for (List<Object> otherCombinationList : otherCombination) {
19 List<Object> newResult = new LinkedList<>();
20 newResult.add(permuteThisElement);
21 newResult.addAll(otherCombinationList);
22 result.add(newResult);
23 }
24 }
25 return result;
26 }
27 }
28
29 public static Stream<Arguments> permutation(Object[]... valueOption) {
30 List<List<Object>> permutations = permutationInternal(0, valueOption);
31 return permutations.stream().map(x -> Arguments.of(x.toArray()));
32 }
33
34 public static Stream<Arguments> permutationWithSize(Object[]... valueOption) {
35 int size = 1;
36 for (int i = 0; i < valueOption.length; i++) {
37 size *= valueOption[i].length;
38 }
39 Object[][] newValueOption = new Object[valueOption.length + 1][];
40 newValueOption[0] = new Object[] { size };
41 for (int i = 1; i < newValueOption.length; i++) {
42 newValueOption[i] = valueOption[i - 1];
43 }
44 return permutation(newValueOption);
45 }
46}
diff --git a/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/utils/TestPermuterTest.java b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/utils/TestPermuterTest.java
new file mode 100644
index 00000000..91f1c2e0
--- /dev/null
+++ b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/smoke/utils/TestPermuterTest.java
@@ -0,0 +1,33 @@
1package org.eclipse.viatra.solver.data.map.tests.smoke.utils;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4
5import java.util.List;
6
7import org.junit.jupiter.api.Test;
8
9class TestPermuterTest {
10 @Test
11 void permutationInternalTest() {
12 List<List<Object>> res = TestPermuter.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 = TestPermuter.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 = TestPermuter.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/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/support/MapTestEnvironment.java b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/support/MapTestEnvironment.java
new file mode 100644
index 00000000..6c55be62
--- /dev/null
+++ b/model-data/src/test/java/org/eclipse/viatra/solver/data/map/tests/support/MapTestEnvironment.java
@@ -0,0 +1,174 @@
1package org.eclipse.viatra.solver.data.map.tests.support;
2
3import static org.junit.jupiter.api.Assertions.assertEquals;
4import static org.junit.jupiter.api.Assertions.fail;
5
6import java.util.HashMap;
7import java.util.Iterator;
8import java.util.Map;
9import java.util.Map.Entry;
10import java.util.TreeMap;
11
12import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
13import org.eclipse.viatra.solver.data.map.Cursor;
14import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl;
15
16public class MapTestEnvironment<KEY, VALUE> {
17 public static String[] prepareValues(int maxValue) {
18 String[] values = new String[maxValue];
19 values[0] = "DEFAULT";
20 for (int i = 1; i < values.length; i++) {
21 values[i] = "VAL" + i;
22 }
23 return values;
24 }
25
26 public static ContinousHashProvider<Integer> prepareHashProvider(final boolean evil) {
27 // Use maxPrime = 2147483629
28
29 ContinousHashProvider<Integer> chp = new ContinousHashProvider<Integer>() {
30
31 @Override
32 public int getHash(Integer key, int index) {
33 if (evil && index < 15 && index < key / 3) {
34 return 7;
35 }
36 int result = 1;
37 final int prime = 31;
38
39 result = prime * result + key;
40 result = prime * result + index;
41
42 return result;
43 }
44 };
45 return chp;
46 }
47
48 public static void printStatus(String scenario, int actual, int max, String stepName) {
49 if (actual % 10000 == 0) {
50 String printStepName = stepName == null ? "" : stepName;
51 System.out.format(scenario + ":%d/%d (%d%%) " + printStepName + "%n", actual, max, actual * 100 / max);
52 }
53
54 }
55
56 public static <KEY, VALUE> void compareTwoMaps(String title, VersionedMapImpl<KEY, VALUE> map1,
57 VersionedMapImpl<KEY, VALUE> map2) {
58 // 1. Comparing cursors.
59 Cursor<KEY, VALUE> cursor1 = map1.getCursor();
60 Cursor<KEY, VALUE> cursor2 = map2.getCursor();
61 while (!cursor1.isTerminated()) {
62 if (cursor2.isTerminated()) {
63 fail("cursor 2 terminated before cursor1");
64 }
65 assertEquals(cursor1.getKey(), cursor2.getKey());
66 assertEquals(cursor2.getValue(), cursor2.getValue());
67 cursor1.move();
68 cursor2.move();
69 }
70 if (!cursor2.isTerminated())
71 fail("cursor 1 terminated before cursor 2");
72
73 // 2.1. comparing hash codes
74 assertEquals(map1.hashCode(), map2.hashCode(), title + ": hash code check");
75 assertEquals(map1, map2, title + ": 1.equals(2)");
76 assertEquals(map2, map1, title + ": 2.equals(1)");
77 }
78
79 public VersionedMapImpl<KEY, VALUE> sut;
80 Map<KEY, VALUE> oracle = new HashMap<KEY, VALUE>();
81
82 public MapTestEnvironment(VersionedMapImpl<KEY, VALUE> sut) {
83 this.sut = sut;
84 }
85
86 public void put(KEY key, VALUE value) {
87 sut.put(key, value);
88 if (value != sut.getDefaultValue()) {
89 oracle.put(key, value);
90 } else {
91 oracle.remove(key);
92 }
93 }
94
95 public void checkEquivalence(String title) {
96 // 0. Checking integrity
97 try {
98 sut.checkIntegrity();
99 } catch (IllegalStateException e) {
100 fail(title + ": " + e.getMessage());
101 }
102
103 // 1. Checking: if Reference contains <key,value> pair, then SUT contains
104 // <key,value> pair.
105 // Tests get functions
106 for (Entry<KEY, VALUE> entry : oracle.entrySet()) {
107 VALUE sutValue = sut.get(entry.getKey());
108 VALUE oracleValue = entry.getValue();
109 if (sutValue != oracleValue) {
110 printComparison();
111 fail(title + ": Non-equivalent get(" + entry.getKey() + ") results: SUT=" + sutValue + ", Oracle="
112 + oracleValue + "!");
113 }
114 }
115
116 // 2. Checking: if SUT contains <key,value> pair, then Reference contains
117 // <key,value> pair.
118 // Tests iterators
119 // TODO: Counts the number of elements in the entryset
120 int elementsInSutEntrySet = 0;
121 Cursor<KEY, VALUE> cursor = sut.getCursor();
122 while (cursor.move()) {
123 elementsInSutEntrySet++;
124 KEY key = cursor.getKey();
125 VALUE sutValue = cursor.getValue();
126 // System.out.println(key + " -> " + sutValue);
127 VALUE oracleValue = oracle.get(key);
128 if (sutValue != oracleValue) {
129 printComparison();
130 fail(title + ": Non-equivalent entry in iterator: SUT=<" + key + "," + sutValue + ">, Oracle=<" + key
131 + "," + oracleValue + ">!");
132 }
133
134 }
135
136 // 3. Checking sizes
137 // Counting of non-default value pairs.
138 int oracleSize = oracle.entrySet().size();
139 long sutSize = sut.getSize();
140 if (oracleSize != sutSize || oracleSize != elementsInSutEntrySet) {
141 printComparison();
142 fail(title + ": Non-eqivalent size() result: SUT.getSize()=" + sutSize + ", SUT.entryset.size="
143 + elementsInSutEntrySet + ", Oracle=" + oracleSize + "!");
144 }
145 }
146
147 public void printComparison() {
148 System.out.println("SUT:");
149 printEntrySet(sut.getCursor());
150 System.out.println("Oracle:");
151 printEntrySet(oracle.entrySet().iterator());
152 }
153
154 private void printEntrySet(Iterator<Entry<KEY, VALUE>> iterator) {
155 TreeMap<KEY, VALUE> treemap = new TreeMap<>();
156 while (iterator.hasNext()) {
157 Entry<KEY, VALUE> entry = iterator.next();
158 treemap.put(entry.getKey(), entry.getValue());
159 }
160 for (Entry<KEY, VALUE> e : treemap.entrySet()) {
161 System.out.println("\t" + e.getKey() + " -> " + e.getValue());
162 }
163 }
164
165 private void printEntrySet(Cursor<KEY, VALUE> cursor) {
166 TreeMap<KEY, VALUE> treemap = new TreeMap<>();
167 while (cursor.move()) {
168 treemap.put(cursor.getKey(), cursor.getValue());
169 }
170 for (Entry<KEY, VALUE> e : treemap.entrySet()) {
171 System.out.println("\t" + e.getKey() + " -> " + e.getValue());
172 }
173 }
174}
diff --git a/settings.gradle b/settings.gradle
index 94abfdbe..78f06a61 100644
--- a/settings.gradle
+++ b/settings.gradle
@@ -3,3 +3,4 @@ include 'language-ide'
3include 'language-model' 3include 'language-model'
4include 'language-mwe2' 4include 'language-mwe2'
5include 'language-web' 5include 'language-web'
6include 'model-data' \ No newline at end of file
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-07-03 08:11:43 +0000