From 89e142514ae45d793c7dbe38f728b33451261338 Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Tue, 18 Jul 2023 15:38:59 +0200 Subject: Fixing long-standing bug with state based diff cursor. By implementing an InOrderMapCursor cursor, and a MapDiffCursor that synchronize two cursors. --- .../refinery/store/map/VersionedMapStoreImpl.java | 17 +- .../refinery/store/map/internal/ImmutableNode.java | 74 ++++- .../store/map/internal/InOrderMapCursor.java | 141 +++++++++ .../refinery/store/map/internal/MapCursor.java | 59 ---- .../refinery/store/map/internal/MapDiffCursor.java | 316 ++++++++++++--------- .../refinery/store/map/internal/MutableNode.java | 111 +++++--- .../tools/refinery/store/map/internal/Node.java | 2 + .../store/map/internal/VersionedMapImpl.java | 20 +- .../model/internal/VersionedInterpretation.java | 15 +- 9 files changed, 475 insertions(+), 280 deletions(-) create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java (limited to 'subprojects/store/src/main/java/tools') 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 @@ package tools.refinery.store.map; -import tools.refinery.store.map.internal.ImmutableNode; -import tools.refinery.store.map.internal.MapDiffCursor; -import tools.refinery.store.map.internal.Node; -import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.internal.*; import java.util.*; @@ -93,7 +90,7 @@ public class VersionedMapStoreImpl implements VersionedMapStore { } else { ArrayList existingKeys = new ArrayList<>(states.keySet()); Collections.sort(existingKeys); - throw new IllegalArgumentException("Store does not contain state " + state + "! Avaliable states: " + throw new IllegalArgumentException("Store does not contain state " + state + "! Available states: " + Arrays.toString(existingKeys.toArray())); } } @@ -118,10 +115,10 @@ public class VersionedMapStoreImpl implements VersionedMapStore { @Override public DiffCursor getDiffCursor(long fromState, long toState) { - VersionedMap map1 = createMap(fromState); - VersionedMap map2 = createMap(toState); - Cursor cursor1 = map1.getAll(); - Cursor cursor2 = map2.getAll(); - return new MapDiffCursor<>(this.hashProvider, this.defaultValue, cursor1, cursor2); + VersionedMapImpl map1 = (VersionedMapImpl) createMap(fromState); + VersionedMapImpl map2 = (VersionedMapImpl) createMap(toState); + InOrderMapCursor cursor1 = new InOrderMapCursor<>(map1); + InOrderMapCursor cursor2 = new InOrderMapCursor<>(map2); + return new MapDiffCursor<>(this.defaultValue, cursor1, cursor2); } } 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 extends Node { */ final int nodeMap; /** - * Stores Keys, Values, and subnodes. Structure: (K,V)*,NODE; NODES are stored + * Stores Keys, Values, and sub-nodes. Structure: (K,V)*,NODE; NODES are stored * backwards. */ final Object[] content; @@ -65,24 +65,24 @@ public class ImmutableNode extends Node { int resultDataMap = 0; int resultNodeMap = 0; final Object[] resultContent = new Object[size]; - int bitposition = 1; + int bitPosition = 1; for (int i = 0; i < FACTOR; i++) { Object key = node.content[i * 2]; if (key != null) { - resultDataMap |= bitposition; + resultDataMap |= bitPosition; resultContent[datas * 2] = key; resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; datas++; } else { @SuppressWarnings("unchecked") var subnode = (Node) node.content[i * 2 + 1]; if (subnode != null) { - ImmutableNode immutableSubnode = subnode.toImmutable(cache); - resultNodeMap |= bitposition; - resultContent[size - 1 - nodes] = immutableSubnode; + ImmutableNode immutableSubNode = subnode.toImmutable(cache); + resultNodeMap |= bitPosition; + resultContent[size - 1 - nodes] = immutableSubNode; nodes++; } } - bitposition <<= 1; + bitPosition <<= 1; } final int resultHash = node.hashCode(); var newImmutable = new ImmutableNode(resultDataMap, resultNodeMap, resultContent, resultHash); @@ -130,9 +130,9 @@ public class ImmutableNode extends Node { @Override public Node putValue(K key, V value, OldValueBox oldValue, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); - int bitposition = 1 << selectedHashFragment; - if ((dataMap & bitposition) != 0) { - int keyIndex = 2 * index(dataMap, bitposition); + int bitPosition = 1 << selectedHashFragment; + if ((dataMap & bitPosition) != 0) { + int keyIndex = 2 * index(dataMap, bitPosition); @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; if (keyCandidate.equals(key)) { if (value == defaultValue) { @@ -159,8 +159,8 @@ public class ImmutableNode extends Node { return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); } } - } else if ((nodeMap & bitposition) != 0) { - int keyIndex = content.length - 1 - index(nodeMap, bitposition); + } else if ((nodeMap & bitPosition) != 0) { + int keyIndex = content.length - 1 - index(nodeMap, bitPosition); @SuppressWarnings("unchecked") var subNode = (ImmutableNode) content[keyIndex]; int newDepth = incrementDepth(depth); int newHash = newHash(hashProvider, key, hash, newDepth); @@ -253,6 +253,49 @@ public class ImmutableNode extends Node { } } + @Override + @SuppressWarnings("unchecked") + boolean moveToNextInorder(InOrderMapCursor cursor) { + if(cursor.nodeIndexStack.peek()==null) { + throw new IllegalStateException("Cursor moved to the next state when the state is empty."); + } + + int position = cursor.nodeIndexStack.peek(); + for (int index = position + 1; index < FACTOR; index++) { + final int mask = 1< subnode = (Node) this.content[this.content.length - 1 - index(nodeMap, mask)]; + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(index); + cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START); + cursor.nodeStack.push(subnode); + + return subnode.moveToNextInorder(cursor); + } + } + + // nothing found + cursor.nodeStack.pop(); + cursor.nodeIndexStack.pop(); + if (!cursor.nodeStack.isEmpty()) { + Node supernode = cursor.nodeStack.peek(); + return supernode.moveToNextInorder(cursor); + } else { + cursor.key = null; + cursor.value = null; + return false; + } + } + @Override public void prettyPrint(StringBuilder builder, int depth, int code) { builder.append("\t".repeat(Math.max(0, depth))); @@ -348,8 +391,8 @@ public class ImmutableNode extends Node { var mutableSubnode = (Node) mutable.content[i * 2 + 1]; if (mutableSubnode != null) { if (datas * 2 + nodes + 1 <= immutableLength) { - Object immutableSubnode = immutable.content[immutableLength - 1 - nodes]; - if (!mutableSubnode.equals(immutableSubnode)) { + Object immutableSubNode = immutable.content[immutableLength - 1 - nodes]; + if (!mutableSubnode.equals(immutableSubNode)) { return false; } nodes++; @@ -359,6 +402,7 @@ public class ImmutableNode extends Node { } } } - return true; + + return datas * 2 + nodes == immutable.content.length; } } 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 @@ +package tools.refinery.store.map.internal; + +import tools.refinery.store.map.AnyVersionedMap; +import tools.refinery.store.map.ContentHashCode; +import tools.refinery.store.map.Cursor; +import tools.refinery.store.map.VersionedMap; + +import java.util.*; + +public class InOrderMapCursor implements Cursor { + // Constants + static final int INDEX_START = -1; + + // Tree stack + ArrayDeque> nodeStack; + ArrayDeque nodeIndexStack; + + + // Values + K key; + V value; + + // Hash code for checking concurrent modifications + final VersionedMap map; + final int creationHash; + + public InOrderMapCursor(VersionedMapImpl map) { + // Initializing tree stack + super(); + this.nodeStack = new ArrayDeque<>(); + this.nodeIndexStack = new ArrayDeque<>(); + if (map.root != null) { + this.nodeStack.add(map.root); + this.nodeIndexStack.push(INDEX_START); + } + + // Initializing cache + this.key = null; + this.value = null; + + // Initializing state + this.map = map; + this.creationHash = map.contentHashCode(ContentHashCode.APPROXIMATE_FAST); + } + + public K getKey() { + return key; + } + + public V getValue() { + return value; + } + + public boolean isTerminated() { + return this.nodeStack.isEmpty(); + } + + public boolean move() { + if (isDirty()) { + throw new ConcurrentModificationException(); + } + if (!isTerminated()) { + var node = this.nodeStack.peek(); + if (node == null) { + throw new IllegalStateException("Cursor is not terminated but the current node is missing"); + } + boolean result = node.moveToNextInorder(this); + if (this.nodeIndexStack.size() != this.nodeStack.size()) { + throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); + } + return result; + } + return false; + } + + public boolean skipCurrentNode() { + nodeStack.pop(); + nodeIndexStack.pop(); + return move(); + } + + @Override + public boolean isDirty() { + return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; + } + + @Override + public Set getDependingMaps() { + return Set.of(this.map); + } + + public static boolean sameSubNode(InOrderMapCursor cursor1, InOrderMapCursor cursor2) { + Node nodeOfCursor1 = cursor1.nodeStack.peek(); + Node nodeOfCursor2 = cursor2.nodeStack.peek(); + return Objects.equals(nodeOfCursor1, nodeOfCursor2); + } + + /** + * Compares the state of two cursors started on two {@link VersionedMap} of the same + * {@link tools.refinery.store.map.VersionedMapStore}. + * @param Key type + * @param Value type + * @param cursor1 first cursor + * @param cursor2 second cursor + * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the + * same position. + */ + public static int comparePosition(InOrderMapCursor cursor1, InOrderMapCursor cursor2) { + // If the state does not determine the order, then compare @nodeIndexStack. + Iterator nodeIndexStack1 = cursor1.nodeIndexStack.descendingIterator(); + Iterator nodeIndexStack2 = cursor2.nodeIndexStack.descendingIterator(); + + while(nodeIndexStack1.hasNext() && nodeIndexStack2.hasNext()){ + final int index1 = nodeIndexStack1.next(); + final int index2 = nodeIndexStack2.next(); + if(index1 < index2) { + return 1; + } else if(index1 > index2) { + return -1; + } + } + + return 0; + } + + /** + * Compares the depth of two cursors started on @{@link VersionedMap} of the same + * {@link tools.refinery.store.map.VersionedMapStore}. + * @param Key type + * @param Value type + * @param cursor1 first cursor + * @param cursor2 second cursor + * @return Positive number if cursor 1 is deeper, negative number if cursor 2 is deeper, and 0 if they are at the + * same depth. + */ + public static int compareDepth(InOrderMapCursor cursor1, InOrderMapCursor cursor2) { + int d1 = cursor1.nodeIndexStack.size(); + int d2 = cursor2.nodeIndexStack.size(); + return Integer.compare(d1, d2); + } +} 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; import java.util.ArrayDeque; import java.util.ConcurrentModificationException; -import java.util.Iterator; import java.util.Set; public class MapCursor implements Cursor { @@ -79,13 +78,6 @@ public class MapCursor implements Cursor { return false; } - public boolean skipCurrentNode() { - nodeStack.pop(); - nodeIndexStack.pop(); - dataIndex = INDEX_FINISH; - return move(); - } - @Override public boolean isDirty() { return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; @@ -95,55 +87,4 @@ public class MapCursor implements Cursor { public Set getDependingMaps() { return Set.of(this.map); } - - public static boolean sameSubNode(MapCursor cursor1, MapCursor cursor2) { - Node nodeOfCursor1 = cursor1.nodeStack.peek(); - Node nodeOfCursor2 = cursor2.nodeStack.peek(); - if (nodeOfCursor1 != null && nodeOfCursor2 != null) { - return nodeOfCursor1.equals(nodeOfCursor2); - } else { - return false; - } - } - - /** - * Compares the state of two cursors started on two @{@link VersionedMap of the }same - * {@link tools.refinery.store.map.VersionedMapStore}. - * @param Key type - * @param Value type - * @param cursor1 first cursor - * @param cursor2 second cursor - * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the - * same position. - */ - public static int compare(MapCursor cursor1, MapCursor cursor2) { - // Checking the state of the cursors - if(!cursor1.isTerminated() && cursor2.isTerminated()) return -1; - else if(cursor1.isTerminated() && !cursor2.isTerminated()) return 1; - else if(cursor1.isTerminated() && cursor2.isTerminated()) return 0; - - // If the state does not determine the order, then compare @nodeIndexStack. - Iterator stack1 = cursor1.nodeIndexStack.descendingIterator(); - Iterator stack2 = cursor2.nodeIndexStack.descendingIterator(); - if (stack1.hasNext()) { - if (!stack2.hasNext()) { - // stack 2 has no more element, thus stack 1 is deeper - return 1; - } - int val1 = stack1.next(); - int val2 = stack2.next(); - if (val1 < val2) { - return -1; - } else if (val2 < val1) { - return 1; - } - } - if (stack2.hasNext()) { - // stack 2 has more element, thus stack 2 is deeper - return 1; - } - - // two cursors are equally deep decide by data index - return Integer.compare(cursor1.dataIndex, cursor2.dataIndex); - } } 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 @@ package tools.refinery.store.map.internal; import tools.refinery.store.map.AnyVersionedMap; -import tools.refinery.store.map.ContinousHashProvider; import tools.refinery.store.map.Cursor; import tools.refinery.store.map.DiffCursor; @@ -14,37 +13,78 @@ import java.util.stream.Stream; * A cursor representing the difference between two states of a map. * * @author Oszkar Semerath - * */ public class MapDiffCursor implements DiffCursor, Cursor { + private enum State { + /** + * initialized state. + */ + INIT, + /** + * Unstable state. + */ + MOVING_MOVING_SAME_KEY_SAME_VALUE, + /** + * Both cursors are moving, and they are on the same sub-node. + */ + MOVING_MOVING_SAME_NODE, + /** + * Both cursors are moving, cursor 1 is behind. + */ + MOVING_MOVING_BEHIND1, + /** + * Both cursors are moving, cursor 2 is behind. + */ + MOVING_MOVING_BEHIND2, + /** + * Both cursors are moving, cursor 1 is on the same key as cursor 2, values are different + */ + MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE, + /** + * Cursor 1 is moving, Cursor 2 is terminated. + */ + MOVING_TERMINATED, + /** + * Cursor 1 is terminated , Cursor 2 is moving. + */ + TERMINATED_MOVING, + /** + * Both cursors are terminated. + */ + TERMINATED_TERMINATED, + /** + * Both Cursors are moving, and they are on an incomparable position. + * It is resolved by showing Cursor 1. + */ + MOVING_MOVING_HASH1, + /** + * Both Cursors are moving, and they are on an incomparable position. + * It is resolved by showing Cursor 2. + */ + MOVING_MOVING_HASH2 + } + /** * Default nodeId representing missing elements. */ private final V defaultValue; - private final MapCursor cursor1; - private final MapCursor cursor2; - private final ContinousHashProvider hashProvider; + private final InOrderMapCursor cursor1; + private final InOrderMapCursor cursor2; + + // State + State state = State.INIT; // Values private K key; private V fromValue; private V toValue; - // State - /** - * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, - * and 0 if they are at the same position. - */ - private int cursorRelation; - private HashClash hashClash = HashClash.NONE; - public MapDiffCursor(ContinousHashProvider hashProvider, V defaultValue, Cursor cursor1, - Cursor cursor2) { + public MapDiffCursor(V defaultValue, InOrderMapCursor cursor1, InOrderMapCursor cursor2) { super(); - this.hashProvider = hashProvider; this.defaultValue = defaultValue; - this.cursor1 = (MapCursor) cursor1; - this.cursor2 = (MapCursor) cursor2; + this.cursor1 = cursor1; + this.cursor2 = cursor2; } @Override @@ -68,7 +108,7 @@ public class MapDiffCursor implements DiffCursor, Cursor { } public boolean isTerminated() { - return cursor1.isTerminated() && cursor2.isTerminated(); + return this.state == State.TERMINATED_TERMINATED; } @Override @@ -78,148 +118,142 @@ public class MapDiffCursor implements DiffCursor, Cursor { @Override public Set getDependingMaps() { - return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()) - .map(AnyVersionedMap.class::cast) - .collect(Collectors.toUnmodifiableSet()); - } - - protected void updateState() { - if (!isTerminated()) { - this.cursorRelation = MapCursor.compare(cursor1, cursor2); - if (cursorRelation > 0 || cursor2.isTerminated()) { - this.key = cursor1.getKey(); - this.fromValue = cursor1.getValue(); - this.toValue = defaultValue; - } else if (cursorRelation < 0 || cursor1.isTerminated()) { - this.key = cursor2.getKey(); - this.fromValue = defaultValue; - this.toValue = cursor1.getValue(); - } else { - // cursor1 = cursor2 - if (cursor1.getKey().equals(cursor2.getKey())) { - this.key = cursor1.getKey(); - this.fromValue = cursor1.getValue(); - this.toValue = defaultValue; - } else { - resolveHashClashWithFirstEntry(); - } - } - } + return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).map(AnyVersionedMap.class::cast).collect(Collectors.toUnmodifiableSet()); } - protected void resolveHashClashWithFirstEntry() { - int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key); - if (compareResult < 0) { - this.hashClash = HashClash.STUCK_CURSOR_2; - this.cursorRelation = 0; - this.key = cursor1.key; - this.fromValue = cursor1.value; - this.toValue = defaultValue; - } else if (compareResult > 0) { - this.hashClash = HashClash.STUCK_CURSOR_1; - this.cursorRelation = 0; - this.key = cursor2.key; - this.fromValue = defaultValue; - this.toValue = cursor2.value; - } else { - throw new IllegalArgumentException("Inconsistent compare result for diffCursor"); - } + private boolean isInStableState() { + return this.state != State.MOVING_MOVING_SAME_KEY_SAME_VALUE + && this.state != State.MOVING_MOVING_SAME_NODE && this.state != State.INIT; } - protected boolean isInHashClash() { - return this.hashClash != HashClash.NONE; + private boolean updateAndReturnWithResult() { + return switch (this.state) { + case INIT -> throw new IllegalStateException("DiffCursor terminated without starting!"); + case MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_NODE -> + throw new IllegalStateException("DiffCursor terminated in unstable state!"); + case MOVING_MOVING_BEHIND1, MOVING_TERMINATED, MOVING_MOVING_HASH1 -> { + this.key = this.cursor1.getKey(); + this.fromValue = this.cursor1.getValue(); + this.toValue = this.defaultValue; + yield true; + } + case MOVING_MOVING_BEHIND2, TERMINATED_MOVING, MOVING_MOVING_HASH2 -> { + this.key = this.cursor2.getKey(); + this.fromValue = this.defaultValue; + this.toValue = cursor2.getValue(); + yield true; + } + case MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> { + this.key = this.cursor1.getKey(); + this.fromValue = this.cursor1.getValue(); + this.toValue = this.cursor2.getValue(); + yield true; + } + case TERMINATED_TERMINATED -> { + this.key = null; + this.fromValue = null; + this.toValue = null; + yield false; + } + }; } - protected void resolveHashClashWithSecondEntry() { - switch (this.hashClash) { - case STUCK_CURSOR_1 -> { - this.hashClash = HashClash.NONE; - this.cursorRelation = 0; - this.key = cursor1.key; - this.fromValue = cursor1.value; - this.toValue = defaultValue; - } - case STUCK_CURSOR_2 -> { - this.hashClash = HashClash.NONE; - this.cursorRelation = 0; - this.key = cursor2.key; - this.fromValue = defaultValue; - this.toValue = cursor2.value; - } - default -> throw new IllegalArgumentException("Inconsistent compare result for diffCursor"); - } + public boolean move() { + do { + this.state = moveOne(this.state); + } while (!isInStableState()); + return updateAndReturnWithResult(); } - /** - * Checks if two states has the same values, i.e., there is no difference. - * @return whether two states has the same values - */ - protected boolean sameValues() { - if(cursor1.isTerminated() || cursor2.isTerminated()) return false; - else return Objects.equals(this.fromValue, this.toValue); + private State moveOne(State currentState) { + return switch (currentState) { + case INIT, MOVING_MOVING_HASH2, MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> { + boolean cursor1Moved = cursor1.move(); + boolean cursor2Moved = cursor2.move(); + yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved); + } + case MOVING_MOVING_SAME_NODE -> { + boolean cursor1Moved = cursor1.skipCurrentNode(); + boolean cursor2Moved = cursor2.skipCurrentNode(); + yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved); + } + case MOVING_MOVING_BEHIND1 -> { + boolean cursorMoved = cursor1.move(); + if (cursorMoved) { + yield recalculateStateBasedOnCursorRelation(); + } else { + yield State.TERMINATED_MOVING; + } + } + case MOVING_MOVING_BEHIND2 -> { + boolean cursorMoved = cursor2.move(); + if (cursorMoved) { + yield recalculateStateBasedOnCursorRelation(); + } else { + yield State.MOVING_TERMINATED; + } + } + case TERMINATED_MOVING -> { + boolean cursorMoved = cursor2.move(); + if (cursorMoved) { + yield State.TERMINATED_MOVING; + } else { + yield State.TERMINATED_TERMINATED; + } + } + case MOVING_TERMINATED -> { + boolean cursorMoved = cursor1.move(); + if (cursorMoved) { + yield State.MOVING_TERMINATED; + } else { + yield State.TERMINATED_TERMINATED; + } + } + case MOVING_MOVING_HASH1 -> State.MOVING_MOVING_HASH2; + case TERMINATED_TERMINATED -> throw new IllegalStateException("Trying to move while terminated!"); + }; } - protected boolean moveOne() { - if (isTerminated()) { - return false; - } - if (this.cursorRelation > 0 || cursor2.isTerminated()) { - return cursor1.move(); - } else if (this.cursorRelation < 0 || cursor1.isTerminated()) { - return cursor2.move(); + private State recalculateStateAfterCursorMovement(boolean cursor1Moved, boolean cursor2Moved) { + if (cursor1Moved && cursor2Moved) { + return recalculateStateBasedOnCursorRelation(); + } else if (cursor1Moved) { + return State.MOVING_TERMINATED; + } else if (cursor2Moved) { + return State.TERMINATED_MOVING; } else { - boolean moved1 = cursor1.move(); - boolean moved2 = cursor2.move(); - return moved1 && moved2; + return State.TERMINATED_TERMINATED; } } - private boolean skipNode() { - if (isTerminated()) { - throw new IllegalStateException("DiffCursor tries to skip when terminated!"); - } - boolean update1 = cursor1.skipCurrentNode(); - boolean update2 = cursor2.skipCurrentNode(); - updateState(); - return update1 && update2; - } + private State recalculateStateBasedOnCursorRelation() { + final int relation = InOrderMapCursor.comparePosition(cursor1, cursor2); - protected boolean moveToConsistentState() { - if (!isTerminated()) { - boolean changed; - boolean lastResult = true; - do { - changed = false; - if (MapCursor.sameSubNode(cursor1, cursor2)) { - lastResult = skipNode(); - changed = true; - } - if (sameValues()) { - lastResult = moveOne(); - changed = true; - } - updateState(); - } while (changed && !isTerminated()); - return lastResult; - } else { - return false; + if (relation > 0) { + return State.MOVING_MOVING_BEHIND1; + } else if (relation < 0) { + return State.MOVING_MOVING_BEHIND2; } - } - public boolean move() { - if (!isTerminated()) { - if (isInHashClash()) { - this.resolveHashClashWithSecondEntry(); - return true; + if (InOrderMapCursor.sameSubNode(cursor1, cursor2)) { + return State.MOVING_MOVING_SAME_NODE; + } else if (Objects.equals(cursor1.getKey(), cursor2.getKey())) { + if (Objects.equals(cursor1.getValue(), cursor2.getValue())) { + return State.MOVING_MOVING_SAME_KEY_SAME_VALUE; } else { - if (moveOne()) { - return moveToConsistentState(); - } else { - return false; - } + return State.MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE; } + } + + final int depth = InOrderMapCursor.compareDepth(cursor1, cursor2); + + if (depth > 0) { + return State.MOVING_MOVING_BEHIND1; + } else if (depth < 0) { + return State.MOVING_MOVING_BEHIND2; + } else { + return State.MOVING_MOVING_HASH1; + } - } else - return false; } } 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 extends Node { int dataUsed = 0; int nodeUsed = 0; for (int i = 0; i < FACTOR; i++) { - int bitposition = 1 << i; - if ((node.dataMap & bitposition) != 0) { + int bitPosition = 1 << i; + if ((node.dataMap & bitPosition) != 0) { content[2 * i] = node.content[dataUsed * 2]; content[2 * i + 1] = node.content[dataUsed * 2 + 1]; dataUsed++; - } else if ((node.nodeMap & bitposition) != 0) { + } else if ((node.nodeMap & bitPosition) != 0) { content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; nodeUsed++; } @@ -80,7 +80,7 @@ public class MutableNode extends Node { int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment]; if (keyCandidate != null) { - // If has key + // If it has key if (keyCandidate.equals(key)) { // The key is equals to an existing key -> update entry if (value == defaultValue) { @@ -101,24 +101,22 @@ public class MutableNode extends Node { return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); } } + } + // If it does not have key, check for value + @SuppressWarnings("unchecked") var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; + if (nodeCandidate != null) { + // If it has value, it is a sub-node -> update that + int newDepth = incrementDepth(depth); + var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth); + return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); } else { - // If it does not have key, check for value - @SuppressWarnings("unchecked") var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; - if (nodeCandidate != null) { - // If it has value, it is a subnode -> upate that - int newDepth = incrementDepth(depth); - var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth); - return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); + // If it does not have value, put it in the empty place + if (value == defaultValue) { + // don't need to add new key-value pair + oldValueBox.setOldValue(defaultValue); + return this; } else { - // If it does not have value, put it in the empty place - if (value == defaultValue) { - // dont need to add new key-value pair - oldValueBox.setOldValue(defaultValue); - return this; - } else { - return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue); - } - + return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue); } } } @@ -170,7 +168,7 @@ public class MutableNode extends Node { if (immutableNewNode != null) { int orphaned = immutableNewNode.isOrphaned(); if (orphaned >= 0) { - // orphan subnode data is replaced with data + // orphan sub-node data is replaced with data content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; invalidateHash(); @@ -227,11 +225,11 @@ public class MutableNode extends Node { // Pass everything as parameters for performance. @SuppressWarnings("squid:S107") - private MutableNode newNodeWithTwoEntries(ContinousHashProvider hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newdepth) { - int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth); - int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); - int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); - int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth)); + private MutableNode newNodeWithTwoEntries(ContinousHashProvider hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newDepth) { + int newHash1 = newHash(hashProvider, key1, oldHash1, newDepth); + int newHash2 = newHash(hashProvider, key2, oldHash2, newDepth); + int newFragment1 = hashFragment(newHash1, shiftDepth(newDepth)); + int newFragment2 = hashFragment(newHash2, shiftDepth(newDepth)); MutableNode subNode = new MutableNode<>(); if (newFragment1 != newFragment2) { @@ -241,7 +239,7 @@ public class MutableNode extends Node { subNode.content[newFragment2 * 2] = key2; subNode.content[newFragment2 * 2 + 1] = value2; } else { - MutableNode subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newdepth)); + MutableNode subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newDepth)); subNode.content[newFragment1 * 2 + 1] = subSubNode; } subNode.invalidateHash(); @@ -305,13 +303,13 @@ public class MutableNode extends Node { cursor.dataIndex = MapCursor.INDEX_FINISH; } - // 2. look inside the subnodes + // 2. look inside the sub-nodes if(cursor.nodeIndexStack.peek()==null) { throw new IllegalStateException("Cursor moved to the next state when the state is empty."); } for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) { if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) { - // 2.1 found next subnode, move down to the subnode + // 2.1 found next sub-node, move down to the sub-node Node subnode = (Node) this.content[index * 2 + 1]; cursor.dataIndex = MapCursor.INDEX_START; @@ -323,7 +321,7 @@ public class MutableNode extends Node { return subnode.moveToNext(cursor); } } - // 3. no subnode found, move up + // 3. no sub-node found, move up cursor.nodeStack.pop(); cursor.nodeIndexStack.pop(); if (!cursor.nodeStack.isEmpty()) { @@ -336,6 +334,49 @@ public class MutableNode extends Node { } } + @Override + @SuppressWarnings("unchecked") + boolean moveToNextInorder(InOrderMapCursor cursor) { + if(cursor.nodeIndexStack.peek()==null || cursor.nodeStack.peek()==null) { + throw new IllegalStateException("Cursor moved to the next state when the state is empty."); + } + + int position = cursor.nodeIndexStack.peek(); + + for (int index = position + 1; index < FACTOR; index++) { + // data found + if (this.content[index * 2] != null) { + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(index); + + cursor.key = (K) this.content[index * 2]; + cursor.value = (V) this.content[index * 2 + 1]; + return true; + } else if (this.content[index * 2 +1] != null) { + // sub-node found + Node subnode = (Node) this.content[index * 2 +1]; + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(index); + cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START); + cursor.nodeStack.push(subnode); + + return subnode.moveToNextInorder(cursor); + } + } + + // nothing found + cursor.nodeStack.pop(); + cursor.nodeIndexStack.pop(); + if (!cursor.nodeStack.isEmpty()) { + Node supernode = cursor.nodeStack.peek(); + return supernode.moveToNextInorder(cursor); + } else { + cursor.key = null; + cursor.value = null; + return false; + } + } + @Override public void prettyPrint(StringBuilder builder, int depth, int code) { builder.append("\t".repeat(Math.max(0, depth))); @@ -361,7 +402,7 @@ public class MutableNode extends Node { } } builder.append(")"); - // print subnodes + // print sub-nodes for (int i = 0; i < FACTOR; i++) { if (content[2 * i] == null && content[2 * i + 1] != null) { @SuppressWarnings("unchecked") Node subNode = (Node) content[2 * i + 1]; @@ -397,7 +438,7 @@ public class MutableNode extends Node { } } } - // check subnodes + // check sub-nodes for (int i = 0; i < FACTOR; i++) { if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { @SuppressWarnings("unchecked") var subNode = (Node) this.content[2 * i + 1]; @@ -421,13 +462,11 @@ public class MutableNode extends Node { @Override public int hashCode() { - if (this.cachedHashValid) { - return this.cachedHash; - } else { + if (!this.cachedHashValid) { this.cachedHash = Arrays.hashCode(content); this.cachedHashValid = true; - return this.cachedHash; } + return this.cachedHash; } @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 { * @return Whether there was a next value to move on. */ abstract boolean moveToNext(MapCursor cursor); + abstract boolean moveToNextInorder(InOrderMapCursor cursor); ///////// FOR printing public abstract void prettyPrint(StringBuilder builder, int depth, int code); + @Override public String toString() { 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 implements VersionedMap { Iterator keyIterator = keys.iterator(); Iterator valueIterator = values.iterator(); while (keyIterator.hasNext()) { - this.put(keyIterator.next(), valueIterator.next()); + var key = keyIterator.next(); + var value = valueIterator.next(); + this.put(key,value); } } else { while (cursor.move()) { @@ -109,12 +111,10 @@ public class VersionedMapImpl implements VersionedMap { @Override public DiffCursor getDiffCursor(long toVersion) { - - Cursor fromCursor = this.getAll(); - VersionedMap toMap = this.store.createMap(toVersion); - Cursor toCursor = toMap.getAll(); - return new MapDiffCursor<>(this.hashProvider, this.defaultValue, fromCursor, toCursor); - + InOrderMapCursor fromCursor = new InOrderMapCursor<>(this); + VersionedMapImpl toMap = (VersionedMapImpl) this.store.createMap(toVersion); + InOrderMapCursor toCursor = new InOrderMapCursor<>(toMap); + return new MapDiffCursor<>(this.defaultValue, fromCursor, toCursor); } @@ -152,7 +152,11 @@ public class VersionedMapImpl implements VersionedMap { @Override public int contentHashCode(ContentHashCode mode) { // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode. - return Objects.hashCode(root); + if(root == null) { + return 0; + } else { + return root.hashCode(); + } } @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; import tools.refinery.store.map.DiffCursor; import tools.refinery.store.map.VersionedMap; import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.internal.MapDiffCursor; import tools.refinery.store.model.Interpretation; import tools.refinery.store.model.InterpretationListener; import tools.refinery.store.model.Model; -import tools.refinery.store.model.TupleHashProvider; import tools.refinery.store.representation.AnySymbol; import tools.refinery.store.representation.Symbol; import tools.refinery.store.tuple.Tuple; @@ -19,16 +17,13 @@ import java.util.List; public class VersionedInterpretation implements Interpretation { private final ModelImpl model; private final Symbol symbol; - private final VersionedMapStore store; private final VersionedMap map; private final List> listeners = new ArrayList<>(); private final List> restoreListeners = new ArrayList<>(); - private VersionedInterpretation(ModelImpl model, Symbol symbol, VersionedMapStore store, - VersionedMap map) { + private VersionedInterpretation(ModelImpl model, Symbol symbol, VersionedMap map) { this.model = model; this.symbol = symbol; - this.store = store; this.map = map; } @@ -111,9 +106,7 @@ public class VersionedInterpretation implements Interpretation { @Override public DiffCursor getDiffCursor(long to) { - var fromCursor = getAll(); - var toCursor = store.createMap(to).getAll(); - return new MapDiffCursor<>(TupleHashProvider.INSTANCE, symbol.defaultValue(), fromCursor, toCursor); + return map.getDiffCursor(to); } public long commit() { @@ -148,7 +141,7 @@ public class VersionedInterpretation implements Interpretation { @SuppressWarnings("unchecked") var typedSymbol = (Symbol) symbol; var map = store.createMap(); - return new VersionedInterpretation<>(model, typedSymbol, store, map); + return new VersionedInterpretation<>(model, typedSymbol, map); } static VersionedInterpretation of(ModelImpl model, AnySymbol symbol, VersionedMapStore store, @@ -156,6 +149,6 @@ public class VersionedInterpretation implements Interpretation { @SuppressWarnings("unchecked") var typedSymbol = (Symbol) symbol; var map = store.createMap(state); - return new VersionedInterpretation<>(model, typedSymbol, store, map); + return new VersionedInterpretation<>(model, typedSymbol, map); } } -- cgit v1.2.3-70-g09d2