aboutsummaryrefslogtreecommitdiffstats
path: root/subprojects
diff options
context:
space:
mode:
authorLibravatar OszkarSemerath <semerath@mit.bme.hu>2023-07-18 15:38:59 +0200
committerLibravatar OszkarSemerath <semerath@mit.bme.hu>2023-07-18 15:38:59 +0200
commit89e142514ae45d793c7dbe38f728b33451261338 (patch)
tree17cebb157c5b3e65871384a0d71eb7f2dd54625b /subprojects
parentInitialization bugs with empty DeltaDiffCursor fixed (diff)
downloadrefinery-89e142514ae45d793c7dbe38f728b33451261338.tar.gz
refinery-89e142514ae45d793c7dbe38f728b33451261338.tar.zst
refinery-89e142514ae45d793c7dbe38f728b33451261338.zip
Fixing long-standing bug with state based diff cursor.
By implementing an InOrderMapCursor cursor, and a MapDiffCursor that synchronize two cursors.
Diffstat (limited to 'subprojects')
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java17
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java74
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java141
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java59
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java316
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java111
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java2
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java20
-rw-r--r--subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java15
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java49
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java128
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java12
-rw-r--r--subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java10
13 files changed, 611 insertions, 343 deletions
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java
index 113874e7..beeed110 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java
@@ -1,9 +1,6 @@
1package tools.refinery.store.map; 1package tools.refinery.store.map;
2 2
3import tools.refinery.store.map.internal.ImmutableNode; 3import tools.refinery.store.map.internal.*;
4import tools.refinery.store.map.internal.MapDiffCursor;
5import tools.refinery.store.map.internal.Node;
6import tools.refinery.store.map.internal.VersionedMapImpl;
7 4
8import java.util.*; 5import java.util.*;
9 6
@@ -93,7 +90,7 @@ public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> {
93 } else { 90 } else {
94 ArrayList<Long> existingKeys = new ArrayList<>(states.keySet()); 91 ArrayList<Long> existingKeys = new ArrayList<>(states.keySet());
95 Collections.sort(existingKeys); 92 Collections.sort(existingKeys);
96 throw new IllegalArgumentException("Store does not contain state " + state + "! Avaliable states: " 93 throw new IllegalArgumentException("Store does not contain state " + state + "! Available states: "
97 + Arrays.toString(existingKeys.toArray())); 94 + Arrays.toString(existingKeys.toArray()));
98 } 95 }
99 } 96 }
@@ -118,10 +115,10 @@ public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> {
118 115
119 @Override 116 @Override
120 public DiffCursor<K, V> getDiffCursor(long fromState, long toState) { 117 public DiffCursor<K, V> getDiffCursor(long fromState, long toState) {
121 VersionedMap<K, V> map1 = createMap(fromState); 118 VersionedMapImpl<K, V> map1 = (VersionedMapImpl<K, V>) createMap(fromState);
122 VersionedMap<K, V> map2 = createMap(toState); 119 VersionedMapImpl<K, V> map2 = (VersionedMapImpl<K, V>) createMap(toState);
123 Cursor<K, V> cursor1 = map1.getAll(); 120 InOrderMapCursor<K, V> cursor1 = new InOrderMapCursor<>(map1);
124 Cursor<K, V> cursor2 = map2.getAll(); 121 InOrderMapCursor<K, V> cursor2 = new InOrderMapCursor<>(map2);
125 return new MapDiffCursor<>(this.hashProvider, this.defaultValue, cursor1, cursor2); 122 return new MapDiffCursor<>(this.defaultValue, cursor1, cursor2);
126 } 123 }
127} 124}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java
index 914bab08..92446711 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java
@@ -15,7 +15,7 @@ public class ImmutableNode<K, V> extends Node<K, V> {
15 */ 15 */
16 final int nodeMap; 16 final int nodeMap;
17 /** 17 /**
18 * Stores Keys, Values, and subnodes. Structure: (K,V)*,NODE; NODES are stored 18 * Stores Keys, Values, and sub-nodes. Structure: (K,V)*,NODE; NODES are stored
19 * backwards. 19 * backwards.
20 */ 20 */
21 final Object[] content; 21 final Object[] content;
@@ -65,24 +65,24 @@ public class ImmutableNode<K, V> extends Node<K, V> {
65 int resultDataMap = 0; 65 int resultDataMap = 0;
66 int resultNodeMap = 0; 66 int resultNodeMap = 0;
67 final Object[] resultContent = new Object[size]; 67 final Object[] resultContent = new Object[size];
68 int bitposition = 1; 68 int bitPosition = 1;
69 for (int i = 0; i < FACTOR; i++) { 69 for (int i = 0; i < FACTOR; i++) {
70 Object key = node.content[i * 2]; 70 Object key = node.content[i * 2];
71 if (key != null) { 71 if (key != null) {
72 resultDataMap |= bitposition; 72 resultDataMap |= bitPosition;
73 resultContent[datas * 2] = key; 73 resultContent[datas * 2] = key;
74 resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; 74 resultContent[datas * 2 + 1] = node.content[i * 2 + 1];
75 datas++; 75 datas++;
76 } else { 76 } else {
77 @SuppressWarnings("unchecked") var subnode = (Node<K, V>) node.content[i * 2 + 1]; 77 @SuppressWarnings("unchecked") var subnode = (Node<K, V>) node.content[i * 2 + 1];
78 if (subnode != null) { 78 if (subnode != null) {
79 ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache); 79 ImmutableNode<K, V> immutableSubNode = subnode.toImmutable(cache);
80 resultNodeMap |= bitposition; 80 resultNodeMap |= bitPosition;
81 resultContent[size - 1 - nodes] = immutableSubnode; 81 resultContent[size - 1 - nodes] = immutableSubNode;
82 nodes++; 82 nodes++;
83 } 83 }
84 } 84 }
85 bitposition <<= 1; 85 bitPosition <<= 1;
86 } 86 }
87 final int resultHash = node.hashCode(); 87 final int resultHash = node.hashCode();
88 var newImmutable = new ImmutableNode<K, V>(resultDataMap, resultNodeMap, resultContent, resultHash); 88 var newImmutable = new ImmutableNode<K, V>(resultDataMap, resultNodeMap, resultContent, resultHash);
@@ -130,9 +130,9 @@ public class ImmutableNode<K, V> extends Node<K, V> {
130 @Override 130 @Override
131 public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { 131 public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
132 int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); 132 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
133 int bitposition = 1 << selectedHashFragment; 133 int bitPosition = 1 << selectedHashFragment;
134 if ((dataMap & bitposition) != 0) { 134 if ((dataMap & bitPosition) != 0) {
135 int keyIndex = 2 * index(dataMap, bitposition); 135 int keyIndex = 2 * index(dataMap, bitPosition);
136 @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; 136 @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex];
137 if (keyCandidate.equals(key)) { 137 if (keyCandidate.equals(key)) {
138 if (value == defaultValue) { 138 if (value == defaultValue) {
@@ -159,8 +159,8 @@ public class ImmutableNode<K, V> extends Node<K, V> {
159 return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); 159 return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
160 } 160 }
161 } 161 }
162 } else if ((nodeMap & bitposition) != 0) { 162 } else if ((nodeMap & bitPosition) != 0) {
163 int keyIndex = content.length - 1 - index(nodeMap, bitposition); 163 int keyIndex = content.length - 1 - index(nodeMap, bitPosition);
164 @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex]; 164 @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex];
165 int newDepth = incrementDepth(depth); 165 int newDepth = incrementDepth(depth);
166 int newHash = newHash(hashProvider, key, hash, newDepth); 166 int newHash = newHash(hashProvider, key, hash, newDepth);
@@ -254,6 +254,49 @@ public class ImmutableNode<K, V> extends Node<K, V> {
254 } 254 }
255 255
256 @Override 256 @Override
257 @SuppressWarnings("unchecked")
258 boolean moveToNextInorder(InOrderMapCursor<K, V> cursor) {
259 if(cursor.nodeIndexStack.peek()==null) {
260 throw new IllegalStateException("Cursor moved to the next state when the state is empty.");
261 }
262
263 int position = cursor.nodeIndexStack.peek();
264 for (int index = position + 1; index < FACTOR; index++) {
265 final int mask = 1<<index;
266 if((this.dataMap & mask) != 0) {
267 // data found
268 cursor.nodeIndexStack.pop();
269 cursor.nodeIndexStack.push(index);
270
271 cursor.key = (K) this.content[2 * index(dataMap, mask)];
272 cursor.value = (V) this.content[2 * index(dataMap, mask) +1];
273 return true;
274 } else if((this.nodeMap & mask) != 0) {
275 // node found
276 Node<K,V> subnode = (Node<K, V>) this.content[this.content.length - 1 - index(nodeMap, mask)];
277 cursor.nodeIndexStack.pop();
278 cursor.nodeIndexStack.push(index);
279 cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START);
280 cursor.nodeStack.push(subnode);
281
282 return subnode.moveToNextInorder(cursor);
283 }
284 }
285
286 // nothing found
287 cursor.nodeStack.pop();
288 cursor.nodeIndexStack.pop();
289 if (!cursor.nodeStack.isEmpty()) {
290 Node<K, V> supernode = cursor.nodeStack.peek();
291 return supernode.moveToNextInorder(cursor);
292 } else {
293 cursor.key = null;
294 cursor.value = null;
295 return false;
296 }
297 }
298
299 @Override
257 public void prettyPrint(StringBuilder builder, int depth, int code) { 300 public void prettyPrint(StringBuilder builder, int depth, int code) {
258 builder.append("\t".repeat(Math.max(0, depth))); 301 builder.append("\t".repeat(Math.max(0, depth)));
259 if (code >= 0) { 302 if (code >= 0) {
@@ -348,8 +391,8 @@ public class ImmutableNode<K, V> extends Node<K, V> {
348 var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1]; 391 var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1];
349 if (mutableSubnode != null) { 392 if (mutableSubnode != null) {
350 if (datas * 2 + nodes + 1 <= immutableLength) { 393 if (datas * 2 + nodes + 1 <= immutableLength) {
351 Object immutableSubnode = immutable.content[immutableLength - 1 - nodes]; 394 Object immutableSubNode = immutable.content[immutableLength - 1 - nodes];
352 if (!mutableSubnode.equals(immutableSubnode)) { 395 if (!mutableSubnode.equals(immutableSubNode)) {
353 return false; 396 return false;
354 } 397 }
355 nodes++; 398 nodes++;
@@ -359,6 +402,7 @@ public class ImmutableNode<K, V> extends Node<K, V> {
359 } 402 }
360 } 403 }
361 } 404 }
362 return true; 405
406 return datas * 2 + nodes == immutable.content.length;
363 } 407 }
364} 408}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java
new file mode 100644
index 00000000..c559d9ad
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java
@@ -0,0 +1,141 @@
1package tools.refinery.store.map.internal;
2
3import tools.refinery.store.map.AnyVersionedMap;
4import tools.refinery.store.map.ContentHashCode;
5import tools.refinery.store.map.Cursor;
6import tools.refinery.store.map.VersionedMap;
7
8import java.util.*;
9
10public class InOrderMapCursor<K, V> implements Cursor<K, V> {
11 // Constants
12 static final int INDEX_START = -1;
13
14 // Tree stack
15 ArrayDeque<Node<K, V>> nodeStack;
16 ArrayDeque<Integer> nodeIndexStack;
17
18
19 // Values
20 K key;
21 V value;
22
23 // Hash code for checking concurrent modifications
24 final VersionedMap<K, V> map;
25 final int creationHash;
26
27 public InOrderMapCursor(VersionedMapImpl<K, V> map) {
28 // Initializing tree stack
29 super();
30 this.nodeStack = new ArrayDeque<>();
31 this.nodeIndexStack = new ArrayDeque<>();
32 if (map.root != null) {
33 this.nodeStack.add(map.root);
34 this.nodeIndexStack.push(INDEX_START);
35 }
36
37 // Initializing cache
38 this.key = null;
39 this.value = null;
40
41 // Initializing state
42 this.map = map;
43 this.creationHash = map.contentHashCode(ContentHashCode.APPROXIMATE_FAST);
44 }
45
46 public K getKey() {
47 return key;
48 }
49
50 public V getValue() {
51 return value;
52 }
53
54 public boolean isTerminated() {
55 return this.nodeStack.isEmpty();
56 }
57
58 public boolean move() {
59 if (isDirty()) {
60 throw new ConcurrentModificationException();
61 }
62 if (!isTerminated()) {
63 var node = this.nodeStack.peek();
64 if (node == null) {
65 throw new IllegalStateException("Cursor is not terminated but the current node is missing");
66 }
67 boolean result = node.moveToNextInorder(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
76 public boolean skipCurrentNode() {
77 nodeStack.pop();
78 nodeIndexStack.pop();
79 return move();
80 }
81
82 @Override
83 public boolean isDirty() {
84 return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash;
85 }
86
87 @Override
88 public Set<AnyVersionedMap> getDependingMaps() {
89 return Set.of(this.map);
90 }
91
92 public static <K, V> boolean sameSubNode(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) {
93 Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek();
94 Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek();
95 return Objects.equals(nodeOfCursor1, nodeOfCursor2);
96 }
97
98 /**
99 * Compares the state of two cursors started on two {@link VersionedMap} of the same
100 * {@link tools.refinery.store.map.VersionedMapStore}.
101 * @param <K> Key type
102 * @param <V> Value type
103 * @param cursor1 first cursor
104 * @param cursor2 second cursor
105 * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the
106 * same position.
107 */
108 public static <K, V> int comparePosition(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) {
109 // If the state does not determine the order, then compare @nodeIndexStack.
110 Iterator<Integer> nodeIndexStack1 = cursor1.nodeIndexStack.descendingIterator();
111 Iterator<Integer> nodeIndexStack2 = cursor2.nodeIndexStack.descendingIterator();
112
113 while(nodeIndexStack1.hasNext() && nodeIndexStack2.hasNext()){
114 final int index1 = nodeIndexStack1.next();
115 final int index2 = nodeIndexStack2.next();
116 if(index1 < index2) {
117 return 1;
118 } else if(index1 > index2) {
119 return -1;
120 }
121 }
122
123 return 0;
124 }
125
126 /**
127 * Compares the depth of two cursors started on @{@link VersionedMap} of the same
128 * {@link tools.refinery.store.map.VersionedMapStore}.
129 * @param <K> Key type
130 * @param <V> Value type
131 * @param cursor1 first cursor
132 * @param cursor2 second cursor
133 * @return Positive number if cursor 1 is deeper, negative number if cursor 2 is deeper, and 0 if they are at the
134 * same depth.
135 */
136 public static <K, V> int compareDepth(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) {
137 int d1 = cursor1.nodeIndexStack.size();
138 int d2 = cursor2.nodeIndexStack.size();
139 return Integer.compare(d1, d2);
140 }
141}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java
index 50fcfcd3..7e4f82e8 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java
@@ -7,7 +7,6 @@ import tools.refinery.store.map.VersionedMap;
7 7
8import java.util.ArrayDeque; 8import java.util.ArrayDeque;
9import java.util.ConcurrentModificationException; 9import java.util.ConcurrentModificationException;
10import java.util.Iterator;
11import java.util.Set; 10import java.util.Set;
12 11
13public class MapCursor<K, V> implements Cursor<K, V> { 12public class MapCursor<K, V> implements Cursor<K, V> {
@@ -79,13 +78,6 @@ public class MapCursor<K, V> implements Cursor<K, V> {
79 return false; 78 return false;
80 } 79 }
81 80
82 public boolean skipCurrentNode() {
83 nodeStack.pop();
84 nodeIndexStack.pop();
85 dataIndex = INDEX_FINISH;
86 return move();
87 }
88
89 @Override 81 @Override
90 public boolean isDirty() { 82 public boolean isDirty() {
91 return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; 83 return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash;
@@ -95,55 +87,4 @@ public class MapCursor<K, V> implements Cursor<K, V> {
95 public Set<AnyVersionedMap> getDependingMaps() { 87 public Set<AnyVersionedMap> getDependingMaps() {
96 return Set.of(this.map); 88 return Set.of(this.map);
97 } 89 }
98
99 public static <K, V> boolean sameSubNode(MapCursor<K, V> cursor1, MapCursor<K, V> cursor2) {
100 Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek();
101 Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek();
102 if (nodeOfCursor1 != null && nodeOfCursor2 != null) {
103 return nodeOfCursor1.equals(nodeOfCursor2);
104 } else {
105 return false;
106 }
107 }
108
109 /**
110 * Compares the state of two cursors started on two @{@link VersionedMap of the }same
111 * {@link tools.refinery.store.map.VersionedMapStore}.
112 * @param <K> Key type
113 * @param <V> Value type
114 * @param cursor1 first cursor
115 * @param cursor2 second cursor
116 * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the
117 * same position.
118 */
119 public static <K, V> int compare(MapCursor<K, V> cursor1, MapCursor<K, V> cursor2) {
120 // Checking the state of the cursors
121 if(!cursor1.isTerminated() && cursor2.isTerminated()) return -1;
122 else if(cursor1.isTerminated() && !cursor2.isTerminated()) return 1;
123 else if(cursor1.isTerminated() && cursor2.isTerminated()) return 0;
124
125 // If the state does not determine the order, then compare @nodeIndexStack.
126 Iterator<Integer> stack1 = cursor1.nodeIndexStack.descendingIterator();
127 Iterator<Integer> stack2 = cursor2.nodeIndexStack.descendingIterator();
128 if (stack1.hasNext()) {
129 if (!stack2.hasNext()) {
130 // stack 2 has no more element, thus stack 1 is deeper
131 return 1;
132 }
133 int val1 = stack1.next();
134 int val2 = stack2.next();
135 if (val1 < val2) {
136 return -1;
137 } else if (val2 < val1) {
138 return 1;
139 }
140 }
141 if (stack2.hasNext()) {
142 // stack 2 has more element, thus stack 2 is deeper
143 return 1;
144 }
145
146 // two cursors are equally deep decide by data index
147 return Integer.compare(cursor1.dataIndex, cursor2.dataIndex);
148 }
149} 90}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java
index 6c076ce5..59e8d738 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java
@@ -1,7 +1,6 @@
1package tools.refinery.store.map.internal; 1package tools.refinery.store.map.internal;
2 2
3import tools.refinery.store.map.AnyVersionedMap; 3import tools.refinery.store.map.AnyVersionedMap;
4import tools.refinery.store.map.ContinousHashProvider;
5import tools.refinery.store.map.Cursor; 4import tools.refinery.store.map.Cursor;
6import tools.refinery.store.map.DiffCursor; 5import tools.refinery.store.map.DiffCursor;
7 6
@@ -14,37 +13,78 @@ import java.util.stream.Stream;
14 * A cursor representing the difference between two states of a map. 13 * A cursor representing the difference between two states of a map.
15 * 14 *
16 * @author Oszkar Semerath 15 * @author Oszkar Semerath
17 *
18 */ 16 */
19public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> { 17public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> {
18 private enum State {
19 /**
20 * initialized state.
21 */
22 INIT,
23 /**
24 * Unstable state.
25 */
26 MOVING_MOVING_SAME_KEY_SAME_VALUE,
27 /**
28 * Both cursors are moving, and they are on the same sub-node.
29 */
30 MOVING_MOVING_SAME_NODE,
31 /**
32 * Both cursors are moving, cursor 1 is behind.
33 */
34 MOVING_MOVING_BEHIND1,
35 /**
36 * Both cursors are moving, cursor 2 is behind.
37 */
38 MOVING_MOVING_BEHIND2,
39 /**
40 * Both cursors are moving, cursor 1 is on the same key as cursor 2, values are different
41 */
42 MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE,
43 /**
44 * Cursor 1 is moving, Cursor 2 is terminated.
45 */
46 MOVING_TERMINATED,
47 /**
48 * Cursor 1 is terminated , Cursor 2 is moving.
49 */
50 TERMINATED_MOVING,
51 /**
52 * Both cursors are terminated.
53 */
54 TERMINATED_TERMINATED,
55 /**
56 * Both Cursors are moving, and they are on an incomparable position.
57 * It is resolved by showing Cursor 1.
58 */
59 MOVING_MOVING_HASH1,
60 /**
61 * Both Cursors are moving, and they are on an incomparable position.
62 * It is resolved by showing Cursor 2.
63 */
64 MOVING_MOVING_HASH2
65 }
66
20 /** 67 /**
21 * Default nodeId representing missing elements. 68 * Default nodeId representing missing elements.
22 */ 69 */
23 private final V defaultValue; 70 private final V defaultValue;
24 private final MapCursor<K, V> cursor1; 71 private final InOrderMapCursor<K, V> cursor1;
25 private final MapCursor<K, V> cursor2; 72 private final InOrderMapCursor<K, V> cursor2;
26 private final ContinousHashProvider<? super K> hashProvider; 73
74 // State
75 State state = State.INIT;
27 76
28 // Values 77 // Values
29 private K key; 78 private K key;
30 private V fromValue; 79 private V fromValue;
31 private V toValue; 80 private V toValue;
32 81
33 // State
34 /**
35 * Positive number if cursor 1 is behind, negative number if cursor 2 is behind,
36 * and 0 if they are at the same position.
37 */
38 private int cursorRelation;
39 private HashClash hashClash = HashClash.NONE;
40 82
41 public MapDiffCursor(ContinousHashProvider<? super K> hashProvider, V defaultValue, Cursor<K, V> cursor1, 83 public MapDiffCursor(V defaultValue, InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) {
42 Cursor<K, V> cursor2) {
43 super(); 84 super();
44 this.hashProvider = hashProvider;
45 this.defaultValue = defaultValue; 85 this.defaultValue = defaultValue;
46 this.cursor1 = (MapCursor<K, V>) cursor1; 86 this.cursor1 = cursor1;
47 this.cursor2 = (MapCursor<K, V>) cursor2; 87 this.cursor2 = cursor2;
48 } 88 }
49 89
50 @Override 90 @Override
@@ -68,7 +108,7 @@ public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> {
68 } 108 }
69 109
70 public boolean isTerminated() { 110 public boolean isTerminated() {
71 return cursor1.isTerminated() && cursor2.isTerminated(); 111 return this.state == State.TERMINATED_TERMINATED;
72 } 112 }
73 113
74 @Override 114 @Override
@@ -78,148 +118,142 @@ public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> {
78 118
79 @Override 119 @Override
80 public Set<AnyVersionedMap> getDependingMaps() { 120 public Set<AnyVersionedMap> getDependingMaps() {
81 return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()) 121 return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).map(AnyVersionedMap.class::cast).collect(Collectors.toUnmodifiableSet());
82 .map(AnyVersionedMap.class::cast)
83 .collect(Collectors.toUnmodifiableSet());
84 }
85
86 protected void updateState() {
87 if (!isTerminated()) {
88 this.cursorRelation = MapCursor.compare(cursor1, cursor2);
89 if (cursorRelation > 0 || cursor2.isTerminated()) {
90 this.key = cursor1.getKey();
91 this.fromValue = cursor1.getValue();
92 this.toValue = defaultValue;
93 } else if (cursorRelation < 0 || cursor1.isTerminated()) {
94 this.key = cursor2.getKey();
95 this.fromValue = defaultValue;
96 this.toValue = cursor1.getValue();
97 } else {
98 // cursor1 = cursor2
99 if (cursor1.getKey().equals(cursor2.getKey())) {
100 this.key = cursor1.getKey();
101 this.fromValue = cursor1.getValue();
102 this.toValue = defaultValue;
103 } else {
104 resolveHashClashWithFirstEntry();
105 }
106 }
107 }
108 } 122 }
109 123
110 protected void resolveHashClashWithFirstEntry() { 124 private boolean isInStableState() {
111 int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key); 125 return this.state != State.MOVING_MOVING_SAME_KEY_SAME_VALUE
112 if (compareResult < 0) { 126 && this.state != State.MOVING_MOVING_SAME_NODE && this.state != State.INIT;
113 this.hashClash = HashClash.STUCK_CURSOR_2;
114 this.cursorRelation = 0;
115 this.key = cursor1.key;
116 this.fromValue = cursor1.value;
117 this.toValue = defaultValue;
118 } else if (compareResult > 0) {
119 this.hashClash = HashClash.STUCK_CURSOR_1;
120 this.cursorRelation = 0;
121 this.key = cursor2.key;
122 this.fromValue = defaultValue;
123 this.toValue = cursor2.value;
124 } else {
125 throw new IllegalArgumentException("Inconsistent compare result for diffCursor");
126 }
127 } 127 }
128 128
129 protected boolean isInHashClash() { 129 private boolean updateAndReturnWithResult() {
130 return this.hashClash != HashClash.NONE; 130 return switch (this.state) {
131 case INIT -> throw new IllegalStateException("DiffCursor terminated without starting!");
132 case MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_NODE ->
133 throw new IllegalStateException("DiffCursor terminated in unstable state!");
134 case MOVING_MOVING_BEHIND1, MOVING_TERMINATED, MOVING_MOVING_HASH1 -> {
135 this.key = this.cursor1.getKey();
136 this.fromValue = this.cursor1.getValue();
137 this.toValue = this.defaultValue;
138 yield true;
139 }
140 case MOVING_MOVING_BEHIND2, TERMINATED_MOVING, MOVING_MOVING_HASH2 -> {
141 this.key = this.cursor2.getKey();
142 this.fromValue = this.defaultValue;
143 this.toValue = cursor2.getValue();
144 yield true;
145 }
146 case MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> {
147 this.key = this.cursor1.getKey();
148 this.fromValue = this.cursor1.getValue();
149 this.toValue = this.cursor2.getValue();
150 yield true;
151 }
152 case TERMINATED_TERMINATED -> {
153 this.key = null;
154 this.fromValue = null;
155 this.toValue = null;
156 yield false;
157 }
158 };
131 } 159 }
132 160
133 protected void resolveHashClashWithSecondEntry() { 161 public boolean move() {
134 switch (this.hashClash) { 162 do {
135 case STUCK_CURSOR_1 -> { 163 this.state = moveOne(this.state);
136 this.hashClash = HashClash.NONE; 164 } while (!isInStableState());
137 this.cursorRelation = 0; 165 return updateAndReturnWithResult();
138 this.key = cursor1.key;
139 this.fromValue = cursor1.value;
140 this.toValue = defaultValue;
141 }
142 case STUCK_CURSOR_2 -> {
143 this.hashClash = HashClash.NONE;
144 this.cursorRelation = 0;
145 this.key = cursor2.key;
146 this.fromValue = defaultValue;
147 this.toValue = cursor2.value;
148 }
149 default -> throw new IllegalArgumentException("Inconsistent compare result for diffCursor");
150 }
151 } 166 }
152 167
153 /** 168 private State moveOne(State currentState) {
154 * Checks if two states has the same values, i.e., there is no difference. 169 return switch (currentState) {
155 * @return whether two states has the same values 170 case INIT, MOVING_MOVING_HASH2, MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> {
156 */ 171 boolean cursor1Moved = cursor1.move();
157 protected boolean sameValues() { 172 boolean cursor2Moved = cursor2.move();
158 if(cursor1.isTerminated() || cursor2.isTerminated()) return false; 173 yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved);
159 else return Objects.equals(this.fromValue, this.toValue); 174 }
175 case MOVING_MOVING_SAME_NODE -> {
176 boolean cursor1Moved = cursor1.skipCurrentNode();
177 boolean cursor2Moved = cursor2.skipCurrentNode();
178 yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved);
179 }
180 case MOVING_MOVING_BEHIND1 -> {
181 boolean cursorMoved = cursor1.move();
182 if (cursorMoved) {
183 yield recalculateStateBasedOnCursorRelation();
184 } else {
185 yield State.TERMINATED_MOVING;
186 }
187 }
188 case MOVING_MOVING_BEHIND2 -> {
189 boolean cursorMoved = cursor2.move();
190 if (cursorMoved) {
191 yield recalculateStateBasedOnCursorRelation();
192 } else {
193 yield State.MOVING_TERMINATED;
194 }
195 }
196 case TERMINATED_MOVING -> {
197 boolean cursorMoved = cursor2.move();
198 if (cursorMoved) {
199 yield State.TERMINATED_MOVING;
200 } else {
201 yield State.TERMINATED_TERMINATED;
202 }
203 }
204 case MOVING_TERMINATED -> {
205 boolean cursorMoved = cursor1.move();
206 if (cursorMoved) {
207 yield State.MOVING_TERMINATED;
208 } else {
209 yield State.TERMINATED_TERMINATED;
210 }
211 }
212 case MOVING_MOVING_HASH1 -> State.MOVING_MOVING_HASH2;
213 case TERMINATED_TERMINATED -> throw new IllegalStateException("Trying to move while terminated!");
214 };
160 } 215 }
161 216
162 protected boolean moveOne() { 217 private State recalculateStateAfterCursorMovement(boolean cursor1Moved, boolean cursor2Moved) {
163 if (isTerminated()) { 218 if (cursor1Moved && cursor2Moved) {
164 return false; 219 return recalculateStateBasedOnCursorRelation();
165 } 220 } else if (cursor1Moved) {
166 if (this.cursorRelation > 0 || cursor2.isTerminated()) { 221 return State.MOVING_TERMINATED;
167 return cursor1.move(); 222 } else if (cursor2Moved) {
168 } else if (this.cursorRelation < 0 || cursor1.isTerminated()) { 223 return State.TERMINATED_MOVING;
169 return cursor2.move();
170 } else { 224 } else {
171 boolean moved1 = cursor1.move(); 225 return State.TERMINATED_TERMINATED;
172 boolean moved2 = cursor2.move();
173 return moved1 && moved2;
174 } 226 }
175 } 227 }
176 228
177 private boolean skipNode() { 229 private State recalculateStateBasedOnCursorRelation() {
178 if (isTerminated()) { 230 final int relation = InOrderMapCursor.comparePosition(cursor1, cursor2);
179 throw new IllegalStateException("DiffCursor tries to skip when terminated!");
180 }
181 boolean update1 = cursor1.skipCurrentNode();
182 boolean update2 = cursor2.skipCurrentNode();
183 updateState();
184 return update1 && update2;
185 }
186 231
187 protected boolean moveToConsistentState() { 232 if (relation > 0) {
188 if (!isTerminated()) { 233 return State.MOVING_MOVING_BEHIND1;
189 boolean changed; 234 } else if (relation < 0) {
190 boolean lastResult = true; 235 return State.MOVING_MOVING_BEHIND2;
191 do {
192 changed = false;
193 if (MapCursor.sameSubNode(cursor1, cursor2)) {
194 lastResult = skipNode();
195 changed = true;
196 }
197 if (sameValues()) {
198 lastResult = moveOne();
199 changed = true;
200 }
201 updateState();
202 } while (changed && !isTerminated());
203 return lastResult;
204 } else {
205 return false;
206 } 236 }
207 }
208 237
209 public boolean move() { 238 if (InOrderMapCursor.sameSubNode(cursor1, cursor2)) {
210 if (!isTerminated()) { 239 return State.MOVING_MOVING_SAME_NODE;
211 if (isInHashClash()) { 240 } else if (Objects.equals(cursor1.getKey(), cursor2.getKey())) {
212 this.resolveHashClashWithSecondEntry(); 241 if (Objects.equals(cursor1.getValue(), cursor2.getValue())) {
213 return true; 242 return State.MOVING_MOVING_SAME_KEY_SAME_VALUE;
214 } else { 243 } else {
215 if (moveOne()) { 244 return State.MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE;
216 return moveToConsistentState();
217 } else {
218 return false;
219 }
220 } 245 }
246 }
247
248 final int depth = InOrderMapCursor.compareDepth(cursor1, cursor2);
249
250 if (depth > 0) {
251 return State.MOVING_MOVING_BEHIND1;
252 } else if (depth < 0) {
253 return State.MOVING_MOVING_BEHIND2;
254 } else {
255 return State.MOVING_MOVING_HASH1;
256 }
221 257
222 } else
223 return false;
224 } 258 }
225} 259}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java
index cdc66a10..81bf6188 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java
@@ -39,12 +39,12 @@ public class MutableNode<K, V> extends Node<K, V> {
39 int dataUsed = 0; 39 int dataUsed = 0;
40 int nodeUsed = 0; 40 int nodeUsed = 0;
41 for (int i = 0; i < FACTOR; i++) { 41 for (int i = 0; i < FACTOR; i++) {
42 int bitposition = 1 << i; 42 int bitPosition = 1 << i;
43 if ((node.dataMap & bitposition) != 0) { 43 if ((node.dataMap & bitPosition) != 0) {
44 content[2 * i] = node.content[dataUsed * 2]; 44 content[2 * i] = node.content[dataUsed * 2];
45 content[2 * i + 1] = node.content[dataUsed * 2 + 1]; 45 content[2 * i + 1] = node.content[dataUsed * 2 + 1];
46 dataUsed++; 46 dataUsed++;
47 } else if ((node.nodeMap & bitposition) != 0) { 47 } else if ((node.nodeMap & bitPosition) != 0) {
48 content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; 48 content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed];
49 nodeUsed++; 49 nodeUsed++;
50 } 50 }
@@ -80,7 +80,7 @@ public class MutableNode<K, V> extends Node<K, V> {
80 int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); 80 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
81 @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment]; 81 @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment];
82 if (keyCandidate != null) { 82 if (keyCandidate != null) {
83 // If has key 83 // If it has key
84 if (keyCandidate.equals(key)) { 84 if (keyCandidate.equals(key)) {
85 // The key is equals to an existing key -> update entry 85 // The key is equals to an existing key -> update entry
86 if (value == defaultValue) { 86 if (value == defaultValue) {
@@ -101,24 +101,22 @@ public class MutableNode<K, V> extends Node<K, V> {
101 return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); 101 return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment);
102 } 102 }
103 } 103 }
104 }
105 // If it does not have key, check for value
106 @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
107 if (nodeCandidate != null) {
108 // If it has value, it is a sub-node -> update that
109 int newDepth = incrementDepth(depth);
110 var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth);
111 return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue)));
104 } else { 112 } else {
105 // If it does not have key, check for value 113 // If it does not have value, put it in the empty place
106 @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; 114 if (value == defaultValue) {
107 if (nodeCandidate != null) { 115 // don't need to add new key-value pair
108 // If it has value, it is a subnode -> upate that 116 oldValueBox.setOldValue(defaultValue);
109 int newDepth = incrementDepth(depth); 117 return this;
110 var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth);
111 return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue)));
112 } else { 118 } else {
113 // If it does not have value, put it in the empty place 119 return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue);
114 if (value == defaultValue) {
115 // dont need to add new key-value pair
116 oldValueBox.setOldValue(defaultValue);
117 return this;
118 } else {
119 return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue);
120 }
121
122 } 120 }
123 } 121 }
124 } 122 }
@@ -170,7 +168,7 @@ public class MutableNode<K, V> extends Node<K, V> {
170 if (immutableNewNode != null) { 168 if (immutableNewNode != null) {
171 int orphaned = immutableNewNode.isOrphaned(); 169 int orphaned = immutableNewNode.isOrphaned();
172 if (orphaned >= 0) { 170 if (orphaned >= 0) {
173 // orphan subnode data is replaced with data 171 // orphan sub-node data is replaced with data
174 content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; 172 content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2];
175 content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; 173 content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1];
176 invalidateHash(); 174 invalidateHash();
@@ -227,11 +225,11 @@ public class MutableNode<K, V> extends Node<K, V> {
227 225
228 // Pass everything as parameters for performance. 226 // Pass everything as parameters for performance.
229 @SuppressWarnings("squid:S107") 227 @SuppressWarnings("squid:S107")
230 private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newdepth) { 228 private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newDepth) {
231 int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth); 229 int newHash1 = newHash(hashProvider, key1, oldHash1, newDepth);
232 int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); 230 int newHash2 = newHash(hashProvider, key2, oldHash2, newDepth);
233 int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); 231 int newFragment1 = hashFragment(newHash1, shiftDepth(newDepth));
234 int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth)); 232 int newFragment2 = hashFragment(newHash2, shiftDepth(newDepth));
235 233
236 MutableNode<K, V> subNode = new MutableNode<>(); 234 MutableNode<K, V> subNode = new MutableNode<>();
237 if (newFragment1 != newFragment2) { 235 if (newFragment1 != newFragment2) {
@@ -241,7 +239,7 @@ public class MutableNode<K, V> extends Node<K, V> {
241 subNode.content[newFragment2 * 2] = key2; 239 subNode.content[newFragment2 * 2] = key2;
242 subNode.content[newFragment2 * 2 + 1] = value2; 240 subNode.content[newFragment2 * 2 + 1] = value2;
243 } else { 241 } else {
244 MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newdepth)); 242 MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newDepth));
245 subNode.content[newFragment1 * 2 + 1] = subSubNode; 243 subNode.content[newFragment1 * 2 + 1] = subSubNode;
246 } 244 }
247 subNode.invalidateHash(); 245 subNode.invalidateHash();
@@ -305,13 +303,13 @@ public class MutableNode<K, V> extends Node<K, V> {
305 cursor.dataIndex = MapCursor.INDEX_FINISH; 303 cursor.dataIndex = MapCursor.INDEX_FINISH;
306 } 304 }
307 305
308 // 2. look inside the subnodes 306 // 2. look inside the sub-nodes
309 if(cursor.nodeIndexStack.peek()==null) { 307 if(cursor.nodeIndexStack.peek()==null) {
310 throw new IllegalStateException("Cursor moved to the next state when the state is empty."); 308 throw new IllegalStateException("Cursor moved to the next state when the state is empty.");
311 } 309 }
312 for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) { 310 for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) {
313 if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) { 311 if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) {
314 // 2.1 found next subnode, move down to the subnode 312 // 2.1 found next sub-node, move down to the sub-node
315 Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1]; 313 Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1];
316 314
317 cursor.dataIndex = MapCursor.INDEX_START; 315 cursor.dataIndex = MapCursor.INDEX_START;
@@ -323,7 +321,7 @@ public class MutableNode<K, V> extends Node<K, V> {
323 return subnode.moveToNext(cursor); 321 return subnode.moveToNext(cursor);
324 } 322 }
325 } 323 }
326 // 3. no subnode found, move up 324 // 3. no sub-node found, move up
327 cursor.nodeStack.pop(); 325 cursor.nodeStack.pop();
328 cursor.nodeIndexStack.pop(); 326 cursor.nodeIndexStack.pop();
329 if (!cursor.nodeStack.isEmpty()) { 327 if (!cursor.nodeStack.isEmpty()) {
@@ -337,6 +335,49 @@ public class MutableNode<K, V> extends Node<K, V> {
337 } 335 }
338 336
339 @Override 337 @Override
338 @SuppressWarnings("unchecked")
339 boolean moveToNextInorder(InOrderMapCursor<K,V> cursor) {
340 if(cursor.nodeIndexStack.peek()==null || cursor.nodeStack.peek()==null) {
341 throw new IllegalStateException("Cursor moved to the next state when the state is empty.");
342 }
343
344 int position = cursor.nodeIndexStack.peek();
345
346 for (int index = position + 1; index < FACTOR; index++) {
347 // data found
348 if (this.content[index * 2] != null) {
349 cursor.nodeIndexStack.pop();
350 cursor.nodeIndexStack.push(index);
351
352 cursor.key = (K) this.content[index * 2];
353 cursor.value = (V) this.content[index * 2 + 1];
354 return true;
355 } else if (this.content[index * 2 +1] != null) {
356 // sub-node found
357 Node<K,V> subnode = (Node<K, V>) this.content[index * 2 +1];
358 cursor.nodeIndexStack.pop();
359 cursor.nodeIndexStack.push(index);
360 cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START);
361 cursor.nodeStack.push(subnode);
362
363 return subnode.moveToNextInorder(cursor);
364 }
365 }
366
367 // nothing found
368 cursor.nodeStack.pop();
369 cursor.nodeIndexStack.pop();
370 if (!cursor.nodeStack.isEmpty()) {
371 Node<K, V> supernode = cursor.nodeStack.peek();
372 return supernode.moveToNextInorder(cursor);
373 } else {
374 cursor.key = null;
375 cursor.value = null;
376 return false;
377 }
378 }
379
380 @Override
340 public void prettyPrint(StringBuilder builder, int depth, int code) { 381 public void prettyPrint(StringBuilder builder, int depth, int code) {
341 builder.append("\t".repeat(Math.max(0, depth))); 382 builder.append("\t".repeat(Math.max(0, depth)));
342 if (code >= 0) { 383 if (code >= 0) {
@@ -361,7 +402,7 @@ public class MutableNode<K, V> extends Node<K, V> {
361 } 402 }
362 } 403 }
363 builder.append(")"); 404 builder.append(")");
364 // print subnodes 405 // print sub-nodes
365 for (int i = 0; i < FACTOR; i++) { 406 for (int i = 0; i < FACTOR; i++) {
366 if (content[2 * i] == null && content[2 * i + 1] != null) { 407 if (content[2 * i] == null && content[2 * i + 1] != null) {
367 @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[2 * i + 1]; 408 @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[2 * i + 1];
@@ -397,7 +438,7 @@ public class MutableNode<K, V> extends Node<K, V> {
397 } 438 }
398 } 439 }
399 } 440 }
400 // check subnodes 441 // check sub-nodes
401 for (int i = 0; i < FACTOR; i++) { 442 for (int i = 0; i < FACTOR; i++) {
402 if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { 443 if (this.content[2 * i + 1] != null && this.content[2 * i] == null) {
403 @SuppressWarnings("unchecked") var subNode = (Node<K, V>) this.content[2 * i + 1]; 444 @SuppressWarnings("unchecked") var subNode = (Node<K, V>) this.content[2 * i + 1];
@@ -421,13 +462,11 @@ public class MutableNode<K, V> extends Node<K, V> {
421 462
422 @Override 463 @Override
423 public int hashCode() { 464 public int hashCode() {
424 if (this.cachedHashValid) { 465 if (!this.cachedHashValid) {
425 return this.cachedHash;
426 } else {
427 this.cachedHash = Arrays.hashCode(content); 466 this.cachedHash = Arrays.hashCode(content);
428 this.cachedHashValid = true; 467 this.cachedHashValid = true;
429 return this.cachedHash;
430 } 468 }
469 return this.cachedHash;
431 } 470 }
432 471
433 @Override 472 @Override
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java
index c49be280..3dd332da 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java
@@ -108,10 +108,12 @@ public abstract class Node<K, V> {
108 * @return Whether there was a next value to move on. 108 * @return Whether there was a next value to move on.
109 */ 109 */
110 abstract boolean moveToNext(MapCursor<K, V> cursor); 110 abstract boolean moveToNext(MapCursor<K, V> cursor);
111 abstract boolean moveToNextInorder(InOrderMapCursor<K, V> cursor);
111 112
112 ///////// FOR printing 113 ///////// FOR printing
113 public abstract void prettyPrint(StringBuilder builder, int depth, int code); 114 public abstract void prettyPrint(StringBuilder builder, int depth, int code);
114 115
116
115 @Override 117 @Override
116 public String toString() { 118 public String toString() {
117 StringBuilder stringBuilder = new StringBuilder(); 119 StringBuilder stringBuilder = new StringBuilder();
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
index fb359431..2ceca463 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
@@ -75,7 +75,9 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
75 Iterator<K> keyIterator = keys.iterator(); 75 Iterator<K> keyIterator = keys.iterator();
76 Iterator<V> valueIterator = values.iterator(); 76 Iterator<V> valueIterator = values.iterator();
77 while (keyIterator.hasNext()) { 77 while (keyIterator.hasNext()) {
78 this.put(keyIterator.next(), valueIterator.next()); 78 var key = keyIterator.next();
79 var value = valueIterator.next();
80 this.put(key,value);
79 } 81 }
80 } else { 82 } else {
81 while (cursor.move()) { 83 while (cursor.move()) {
@@ -109,12 +111,10 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
109 111
110 @Override 112 @Override
111 public DiffCursor<K, V> getDiffCursor(long toVersion) { 113 public DiffCursor<K, V> getDiffCursor(long toVersion) {
112 114 InOrderMapCursor<K, V> fromCursor = new InOrderMapCursor<>(this);
113 Cursor<K, V> fromCursor = this.getAll(); 115 VersionedMapImpl<K, V> toMap = (VersionedMapImpl<K, V>) this.store.createMap(toVersion);
114 VersionedMap<K, V> toMap = this.store.createMap(toVersion); 116 InOrderMapCursor<K, V> toCursor = new InOrderMapCursor<>(toMap);
115 Cursor<K, V> toCursor = toMap.getAll(); 117 return new MapDiffCursor<>(this.defaultValue, fromCursor, toCursor);
116 return new MapDiffCursor<>(this.hashProvider, this.defaultValue, fromCursor, toCursor);
117
118 } 118 }
119 119
120 120
@@ -152,7 +152,11 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
152 @Override 152 @Override
153 public int contentHashCode(ContentHashCode mode) { 153 public int contentHashCode(ContentHashCode mode) {
154 // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode. 154 // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode.
155 return Objects.hashCode(root); 155 if(root == null) {
156 return 0;
157 } else {
158 return root.hashCode();
159 }
156 } 160 }
157 161
158 @Override 162 @Override
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java
index 6d82f5d7..c850d334 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java
@@ -4,11 +4,9 @@ import tools.refinery.store.map.Cursor;
4import tools.refinery.store.map.DiffCursor; 4import tools.refinery.store.map.DiffCursor;
5import tools.refinery.store.map.VersionedMap; 5import tools.refinery.store.map.VersionedMap;
6import tools.refinery.store.map.VersionedMapStore; 6import tools.refinery.store.map.VersionedMapStore;
7import tools.refinery.store.map.internal.MapDiffCursor;
8import tools.refinery.store.model.Interpretation; 7import tools.refinery.store.model.Interpretation;
9import tools.refinery.store.model.InterpretationListener; 8import tools.refinery.store.model.InterpretationListener;
10import tools.refinery.store.model.Model; 9import tools.refinery.store.model.Model;
11import tools.refinery.store.model.TupleHashProvider;
12import tools.refinery.store.representation.AnySymbol; 10import tools.refinery.store.representation.AnySymbol;
13import tools.refinery.store.representation.Symbol; 11import tools.refinery.store.representation.Symbol;
14import tools.refinery.store.tuple.Tuple; 12import tools.refinery.store.tuple.Tuple;
@@ -19,16 +17,13 @@ import java.util.List;
19public class VersionedInterpretation<T> implements Interpretation<T> { 17public class VersionedInterpretation<T> implements Interpretation<T> {
20 private final ModelImpl model; 18 private final ModelImpl model;
21 private final Symbol<T> symbol; 19 private final Symbol<T> symbol;
22 private final VersionedMapStore<Tuple, T> store;
23 private final VersionedMap<Tuple, T> map; 20 private final VersionedMap<Tuple, T> map;
24 private final List<InterpretationListener<T>> listeners = new ArrayList<>(); 21 private final List<InterpretationListener<T>> listeners = new ArrayList<>();
25 private final List<InterpretationListener<T>> restoreListeners = new ArrayList<>(); 22 private final List<InterpretationListener<T>> restoreListeners = new ArrayList<>();
26 23
27 private VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMapStore<Tuple, T> store, 24 private VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMap<Tuple, T> map) {
28 VersionedMap<Tuple, T> map) {
29 this.model = model; 25 this.model = model;
30 this.symbol = symbol; 26 this.symbol = symbol;
31 this.store = store;
32 this.map = map; 27 this.map = map;
33 } 28 }
34 29
@@ -111,9 +106,7 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
111 106
112 @Override 107 @Override
113 public DiffCursor<Tuple, T> getDiffCursor(long to) { 108 public DiffCursor<Tuple, T> getDiffCursor(long to) {
114 var fromCursor = getAll(); 109 return map.getDiffCursor(to);
115 var toCursor = store.createMap(to).getAll();
116 return new MapDiffCursor<>(TupleHashProvider.INSTANCE, symbol.defaultValue(), fromCursor, toCursor);
117 } 110 }
118 111
119 public long commit() { 112 public long commit() {
@@ -148,7 +141,7 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
148 @SuppressWarnings("unchecked") 141 @SuppressWarnings("unchecked")
149 var typedSymbol = (Symbol<T>) symbol; 142 var typedSymbol = (Symbol<T>) symbol;
150 var map = store.createMap(); 143 var map = store.createMap();
151 return new VersionedInterpretation<>(model, typedSymbol, store, map); 144 return new VersionedInterpretation<>(model, typedSymbol, map);
152 } 145 }
153 146
154 static <T> VersionedInterpretation<T> of(ModelImpl model, AnySymbol symbol, VersionedMapStore<Tuple, T> store, 147 static <T> VersionedInterpretation<T> of(ModelImpl model, AnySymbol symbol, VersionedMapStore<Tuple, T> store,
@@ -156,6 +149,6 @@ public class VersionedInterpretation<T> implements Interpretation<T> {
156 @SuppressWarnings("unchecked") 149 @SuppressWarnings("unchecked")
157 var typedSymbol = (Symbol<T>) symbol; 150 var typedSymbol = (Symbol<T>) symbol;
158 var map = store.createMap(state); 151 var map = store.createMap(state);
159 return new VersionedInterpretation<>(model, typedSymbol, store, map); 152 return new VersionedInterpretation<>(model, typedSymbol, map);
160 } 153 }
161} 154}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java
new file mode 100644
index 00000000..05cf5a74
--- /dev/null
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java
@@ -0,0 +1,49 @@
1package tools.refinery.store.map.tests;
2
3import org.junit.jupiter.api.Test;
4import tools.refinery.store.map.VersionedMapStoreBuilder;
5import tools.refinery.store.map.internal.InOrderMapCursor;
6import tools.refinery.store.map.internal.VersionedMapImpl;
7import tools.refinery.store.map.tests.utils.MapTestEnvironment;
8
9import static org.junit.jupiter.api.Assertions.*;
10
11class InOrderCursorTest {
12 @Test
13 void testCursor() {
14 var store = VersionedMapStoreBuilder.<Integer,String>builder()
15 .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE)
16 .setStateBasedImmutableWhenCommitting(true)
17 .setHashProvider(MapTestEnvironment.prepareHashProvider(false))
18 .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE)
19 .setDefaultValue("x")
20 .buildOne();
21
22 VersionedMapImpl<Integer,String> map = (VersionedMapImpl<Integer,String>) store.createMap();
23 checkMove(map,0);
24
25 map.put(1,"A");
26 map.commit();
27 checkMove(map,1);
28
29
30 map.put(2,"B");
31 map.commit();
32 checkMove(map,2);
33
34 map.put(3,"C");
35 map.commit();
36 checkMove(map,3);
37
38 }
39
40 private void checkMove(VersionedMapImpl<Integer,String> map, int num) {
41 InOrderMapCursor<Integer,String> cursor = new InOrderMapCursor<>(map);
42 for(int i=0; i<num; i++) {
43 assertTrue(cursor.move());
44 assertFalse(cursor.isTerminated());
45 }
46 assertFalse(cursor.move());
47 assertTrue(cursor.isTerminated());
48 }
49}
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java
index bf409a74..b087906d 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java
@@ -5,7 +5,10 @@ import org.junit.jupiter.api.Timeout;
5import org.junit.jupiter.params.ParameterizedTest; 5import org.junit.jupiter.params.ParameterizedTest;
6import org.junit.jupiter.params.provider.Arguments; 6import org.junit.jupiter.params.provider.Arguments;
7import org.junit.jupiter.params.provider.MethodSource; 7import org.junit.jupiter.params.provider.MethodSource;
8import tools.refinery.store.map.*; 8import tools.refinery.store.map.DiffCursor;
9import tools.refinery.store.map.VersionedMap;
10import tools.refinery.store.map.VersionedMapStore;
11import tools.refinery.store.map.VersionedMapStoreBuilder;
9import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; 12import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils;
10import tools.refinery.store.map.tests.utils.MapTestEnvironment; 13import tools.refinery.store.map.tests.utils.MapTestEnvironment;
11 14
@@ -16,87 +19,104 @@ import static org.junit.jupiter.api.Assertions.fail;
16import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; 19import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*;
17 20
18class DiffCursorFuzzTest { 21class DiffCursorFuzzTest {
19 private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, 22 private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault,
20 boolean nullDefault, int commitFrequency, VersionedMapStoreBuilder<Integer, String> builder) { 23 int commitFrequency, boolean commitBeforeDiffCursor,
24 VersionedMapStoreBuilder<Integer, String> builder) {
21 String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); 25 String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault);
22 26
23 VersionedMapStore<Integer, String> store = builder.setDefaultValue(values[0]).buildOne(); 27 VersionedMapStore<Integer, String> store = builder.setDefaultValue(values[0]).buildOne();
24 iterativeRandomPutsAndCommitsThenDiffCursor(scenario, store, steps, maxKey, values, seed, commitFrequency); 28 iterativeRandomPutsAndCommitsThenDiffCursor(scenario, store, steps, maxKey, values, seed, commitFrequency,
29 commitBeforeDiffCursor);
25 } 30 }
26 31
27 private void iterativeRandomPutsAndCommitsThenDiffCursor(String scenario, VersionedMapStore<Integer, String> store, 32 private void iterativeRandomPutsAndCommitsThenDiffCursor(String scenario, VersionedMapStore<Integer, String> store,
28 int steps, int maxKey, String[] values, int seed, int commitFrequency) { 33 int steps, int maxKey, String[] values, int seed,
29 // 1. build a map with versions 34 int commitFrequency, boolean commitBeforeDiffCursor) {
30 Random r = new Random(seed); 35
31 VersionedMap<Integer, String> versioned = store.createMap();
32 int largestCommit = -1; 36 int largestCommit = -1;
33 37
34 for (int i = 0; i < steps; i++) { 38 {
35 int index = i + 1; 39 // 1. build a map with versions
36 int nextKey = r.nextInt(maxKey); 40 Random r = new Random(seed);
37 String nextValue = values[r.nextInt(values.length)]; 41 VersionedMap<Integer, String> versioned = store.createMap();
38 try { 42 for (int i = 0; i < steps; i++) {
39 versioned.put(nextKey, nextValue); 43 int index = i + 1;
40 } catch (Exception exception) { 44 int nextKey = r.nextInt(maxKey);
41 exception.printStackTrace(); 45 String nextValue = values[r.nextInt(values.length)];
42 fail(scenario + ":" + index + ": exception happened: " + exception);
43 }
44 if (index % commitFrequency == 0) {
45 long version = versioned.commit();
46 largestCommit = (int) version;
47 }
48 if (index % 10000 == 0)
49 System.out.println(scenario + ":" + index + "/" + steps + " building finished");
50 }
51 // 2. create a non-versioned map,
52 VersionedMap<Integer, String> moving = store.createMap();
53 Random r2 = new Random(seed + 1);
54
55 final int diffTravelFrequency = commitFrequency * 2;
56 for (int i = 0; i < steps; i++) {
57 int index = i + 1;
58 if (index % diffTravelFrequency == 0) {
59 // diff-travel
60 long travelToVersion = r2.nextInt(largestCommit + 1);
61 DiffCursor<Integer, String> diffCursor = moving.getDiffCursor(travelToVersion);
62 moving.putAll(diffCursor);
63
64 } else {
65 // random puts
66 int nextKey = r2.nextInt(maxKey);
67 String nextValue = values[r2.nextInt(values.length)];
68 try { 46 try {
69 moving.put(nextKey, nextValue); 47 versioned.put(nextKey, nextValue);
70 } catch (Exception exception) { 48 } catch (Exception exception) {
71 exception.printStackTrace(); 49 exception.printStackTrace();
72 fail(scenario + ":" + index + ": exception happened: " + exception); 50 fail(scenario + ":" + index + ": exception happened: " + exception);
73 } 51 }
74 if (index % commitFrequency == 0) { 52 if (index % commitFrequency == 0) {
75 versioned.commit(); 53 long version = versioned.commit();
54 largestCommit = (int) version;
76 } 55 }
77 if (index % 10000 == 0) 56 if (index % 10000 == 0)
78 System.out.println(scenario + ":" + index + "/" + steps + " building finished"); 57 System.out.println(scenario + ":" + index + "/" + steps + " building finished");
79 } 58 }
80 } 59 }
81 60
61 {
62 // 2. create a non-versioned map,
63 VersionedMap<Integer, String> moving = store.createMap();
64 Random r2 = new Random(seed + 1);
65
66 final int diffTravelFrequency = commitFrequency * 2;
67 for (int i = 0; i < steps; i++) {
68 int index = i + 1;
69 if (index % diffTravelFrequency == 0) {
70 // diff-travel
71 long travelToVersion = r2.nextInt(largestCommit + 1);
72
73 VersionedMap<Integer, String> oracle = store.createMap(travelToVersion);
74
75 if(commitBeforeDiffCursor) {
76 moving.commit();
77 }
78 DiffCursor<Integer, String> diffCursor = moving.getDiffCursor(travelToVersion);
79 moving.putAll(diffCursor);
80 moving.commit();
81
82 MapTestEnvironment.compareTwoMaps(scenario + ":c" + index, oracle, moving);
83
84 moving.restore(travelToVersion);
85
86 } else {
87 // random puts
88 int nextKey = r2.nextInt(maxKey);
89 String nextValue = values[r2.nextInt(values.length)];
90 try {
91 moving.put(nextKey, nextValue);
92 } catch (Exception exception) {
93 exception.printStackTrace();
94 fail(scenario + ":" + index + ": exception happened: " + exception);
95 }
96 if (index % 10000 == 0)
97 System.out.println(scenario + ":" + index + "/" + steps + " building finished");
98 }
99 }
100 }
82 } 101 }
83 102
84 public static final String title = "DiffCursor {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} " + 103 public static final String title = "DiffCursor {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} " +
85 "commit frequency={5} seed={6} config={7}"; 104 "commit frequency={5} seed={6} commit before diff={7} config={8}";
86 105
87 @ParameterizedTest(name = title) 106 @ParameterizedTest(name = title)
88 @MethodSource 107 @MethodSource
89 @Timeout(value = 10) 108 @Timeout(value = 10)
90 @Tag("fuzz") 109 @Tag("fuzz")
91 void parametrizedFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, 110 void parametrizedFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault,
92 int seed, VersionedMapStoreBuilder<Integer, String> builder) { 111 int commitFrequency, int seed, boolean commitBeforeDiffCursor,
93 runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, 112 VersionedMapStoreBuilder<Integer, String> builder) {
94 noKeys, noValues, nullDefault, commitFrequency, builder); 113 runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps,
114 noKeys, noValues, nullDefault, commitFrequency, commitBeforeDiffCursor, builder);
95 } 115 }
96 116
97 static Stream<Arguments> parametrizedFuzz() { 117 static Stream<Arguments> parametrizedFuzz() {
98 return FuzzTestUtils.permutationWithSize(new Object[]{100}, keyCounts, valueCounts, nullDefaultOptions, 118 return FuzzTestUtils.permutationWithSize(new Object[]{500}, keyCounts, valueCounts, nullDefaultOptions,
99 commitFrequencyOptions, randomSeedOptions, storeConfigs); 119 commitFrequencyOptions, randomSeedOptions, new Object[]{false,true}, storeConfigs);
100 } 120 }
101 121
102 @ParameterizedTest(name = title) 122 @ParameterizedTest(name = title)
@@ -104,9 +124,9 @@ class DiffCursorFuzzTest {
104 @Tag("fuzz") 124 @Tag("fuzz")
105 @Tag("slow") 125 @Tag("slow")
106 void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, 126 void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency,
107 int seed, VersionedMapStoreBuilder<Integer, String> builder) { 127 int seed, boolean commitBeforeDiffCursor, VersionedMapStoreBuilder<Integer, String> builder) {
108 runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, 128 runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues,
109 nullDefault, commitFrequency, builder); 129 nullDefault, commitFrequency, commitBeforeDiffCursor, builder);
110 } 130 }
111 131
112 static Stream<Arguments> parametrizedSlowFuzz() { 132 static Stream<Arguments> parametrizedSlowFuzz() {
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java
index fb6b28d8..b344d9b9 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java
@@ -5,23 +5,25 @@ import tools.refinery.store.map.tests.utils.MapTestEnvironment;
5 5
6public final class FuzzTestCollections { 6public final class FuzzTestCollections {
7 public static final Object[] stepCounts = {FuzzTestUtils.FAST_STEP_COUNT}; 7 public static final Object[] stepCounts = {FuzzTestUtils.FAST_STEP_COUNT};
8 public static final Object[] keyCounts = {1, 32, 32 * 32}; 8 public static final Object[] keyCounts = {1 , 32, 32 * 32};
9 public static final Object[] valueCounts = {2, 3}; 9 public static final Object[] valueCounts = {2, 3};
10 public static final Object[] nullDefaultOptions = {false, true}; 10 public static final Object[] nullDefaultOptions = {false, true};
11 public static final Object[] commitFrequencyOptions = {10, 10, 100}; 11 public static final Object[] commitFrequencyOptions = {1, 10, 100};
12 public static final Object[] randomSeedOptions = {1/*, 2, 3*/}; 12 public static final Object[] randomSeedOptions = {1};
13 public static final Object[] storeConfigs = { 13 public static final Object[] storeConfigs = {
14 // State based 14 // State based
15 VersionedMapStoreBuilder.<Integer,String>builder() 15 VersionedMapStoreBuilder.<Integer,String>builder()
16 .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) 16 .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE)
17 .setStateBasedImmutableWhenCommitting(true) 17 .setStateBasedImmutableWhenCommitting(true)
18 .setHashProvider(MapTestEnvironment.prepareHashProvider(false)) 18 .setHashProvider(MapTestEnvironment.prepareHashProvider(false))
19 .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE), 19 .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy
20 .SHARED_NODE_CACHE),
20 VersionedMapStoreBuilder.<Integer,String>builder() 21 VersionedMapStoreBuilder.<Integer,String>builder()
21 .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) 22 .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE)
22 .setStateBasedImmutableWhenCommitting(true) 23 .setStateBasedImmutableWhenCommitting(true)
23 .setHashProvider(MapTestEnvironment.prepareHashProvider(true)) 24 .setHashProvider(MapTestEnvironment.prepareHashProvider(true))
24 .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE), 25 .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy
26 .SHARED_NODE_CACHE),
25 VersionedMapStoreBuilder.<Integer,String>builder() 27 VersionedMapStoreBuilder.<Integer,String>builder()
26 .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) 28 .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE)
27 .setStateBasedImmutableWhenCommitting(false) 29 .setStateBasedImmutableWhenCommitting(false)
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java
index 69ae811e..0e695aaa 100644
--- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java
+++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java
@@ -57,13 +57,15 @@ public class MapTestEnvironment<K, V> {
57 VersionedMap<K, V> map2, List<Throwable> errors) { 57 VersionedMap<K, V> map2, List<Throwable> errors) {
58 map1.checkIntegrity(); 58 map1.checkIntegrity();
59 map2.checkIntegrity(); 59 map2.checkIntegrity();
60
61 assertContentEqualsList(map1, map2, title + ": map1.contentEquals(map2)", errors);
62 assertContentEqualsList(map2, map1, title + ": map2.contentEquals(map1)", errors);
60 assertEqualsList(map1.getSize(), map2.getSize(), title + ": Sizes not equal", errors); 63 assertEqualsList(map1.getSize(), map2.getSize(), title + ": Sizes not equal", errors);
64
61 for (var mode : ContentHashCode.values()) { 65 for (var mode : ContentHashCode.values()) {
62 assertEqualsList(map1.contentHashCode(mode), map2.contentHashCode(mode), 66 assertEqualsList(map1.contentHashCode(mode), map2.contentHashCode(mode),
63 title + ": " + mode + " hashCode check", errors); 67 title + ": " + mode + " hashCode check", errors);
64 } 68 }
65 assertContentEqualsList(map1, map2, title + ": map1.contentEquals(map2)", errors);
66 assertContentEqualsList(map2, map1, title + ": map2.contentEquals(map1)", errors);
67 } 69 }
68 70
69 private static void assertEqualsList(Object o1, Object o2, String message, List<Throwable> errors) { 71 private static void assertEqualsList(Object o1, Object o2, String message, List<Throwable> errors) {
@@ -177,7 +179,8 @@ public class MapTestEnvironment<K, V> {
177 K previous = null; 179 K previous = null;
178 Cursor<K, V> cursor = versionedMap.getAll(); 180 Cursor<K, V> cursor = versionedMap.getAll();
179 while (cursor.move()) { 181 while (cursor.move()) {
180 System.out.println(cursor.getKey() + " " + ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().getHash(cursor.getKey(), 0)); 182 //System.out.println(cursor.getKey() + " " + ((VersionedMapImpl<K, V>) versionedMap).getHashProvider()
183 // .getHash(cursor.getKey(), 0));
181 if (previous != null) { 184 if (previous != null) {
182 int comparisonResult = ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().compare(previous, 185 int comparisonResult = ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().compare(previous,
183 cursor.getKey()); 186 cursor.getKey());
@@ -185,7 +188,6 @@ public class MapTestEnvironment<K, V> {
185 } 188 }
186 previous = cursor.getKey(); 189 previous = cursor.getKey();
187 } 190 }
188 System.out.println();
189 } 191 }
190 192
191 public void printComparison() { 193 public void printComparison() {
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-07-04 21:46:52 +0000