From 26592fc70a026b850616fc4bc9be5a46ab1179a9 Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Mon, 24 Jul 2023 16:51:47 +0200 Subject: Refactoring packages related to VersionedMapDeltaImpl + VersionedMapStoreStateImpl, update builder. - details of the maps goes to internal packages - ModelStoreBuilderImpl uses VersionedMapStoreFactoryBuilder --- .../map/benchmarks/ImmutablePutExecutionPlan.java | 17 +- .../refinery/store/map/ContinousHashProvider.java | 74 --- .../refinery/store/map/ContinuousHashProvider.java | 74 +++ .../tools/refinery/store/map/IteratorAsCursor.java | 64 +++ .../store/map/VersionedMapStoreConfiguration.java | 53 --- .../store/map/VersionedMapStoreDeltaImpl.java | 99 ---- .../store/map/VersionedMapStoreFactoryBuilder.java | 2 +- .../refinery/store/map/VersionedMapStoreImpl.java | 129 ------ .../DeltaBasedVersionedMapStoreFactory.java | 39 -- .../store/map/internal/DeltaDiffCursor.java | 147 ------ .../refinery/store/map/internal/HashClash.java | 23 - .../refinery/store/map/internal/ImmutableNode.java | 413 ----------------- .../store/map/internal/InOrderMapCursor.java | 146 ------ .../store/map/internal/IteratorAsCursor.java | 66 --- .../refinery/store/map/internal/MapCursor.java | 95 ---- .../refinery/store/map/internal/MapDelta.java | 20 - .../refinery/store/map/internal/MapDiffCursor.java | 264 ----------- .../store/map/internal/MapTransaction.java | 39 -- .../refinery/store/map/internal/MutableNode.java | 499 --------------------- .../tools/refinery/store/map/internal/Node.java | 131 ------ .../refinery/store/map/internal/OldValueBox.java | 24 - .../StateBasedVersionedMapStoreFactory.java | 38 -- .../map/internal/UncommittedDeltaArrayStore.java | 36 -- .../map/internal/UncommittedDeltaMapStore.java | 53 --- .../store/map/internal/UncommittedDeltaStore.java | 29 -- .../store/map/internal/VersionedMapDeltaImpl.java | 219 --------- .../store/map/internal/VersionedMapImpl.java | 171 ------- .../VersionedMapStoreFactoryBuilderImpl.java | 18 +- .../delta/DeltaBasedVersionedMapStoreFactory.java | 38 ++ .../store/map/internal/delta/DeltaDiffCursor.java | 147 ++++++ .../store/map/internal/delta/MapDelta.java | 20 + .../store/map/internal/delta/MapTransaction.java | 39 ++ .../internal/delta/UncommittedDeltaArrayStore.java | 36 ++ .../internal/delta/UncommittedDeltaMapStore.java | 53 +++ .../map/internal/delta/UncommittedDeltaStore.java | 29 ++ .../map/internal/delta/VersionedMapDeltaImpl.java | 220 +++++++++ .../internal/delta/VersionedMapStoreDeltaImpl.java | 101 +++++ .../store/map/internal/state/ImmutableNode.java | 413 +++++++++++++++++ .../store/map/internal/state/InOrderMapCursor.java | 146 ++++++ .../store/map/internal/state/MapCursor.java | 95 ++++ .../store/map/internal/state/MapDiffCursor.java | 264 +++++++++++ .../store/map/internal/state/MutableNode.java | 499 +++++++++++++++++++++ .../refinery/store/map/internal/state/Node.java | 131 ++++++ .../store/map/internal/state/OldValueBox.java | 24 + .../state/StateBasedVersionedMapStoreFactory.java | 38 ++ .../map/internal/state/VersionedMapStateImpl.java | 171 +++++++ .../state/VersionedMapStoreStateConfiguration.java | 56 +++ .../internal/state/VersionedMapStoreStateImpl.java | 129 ++++++ .../refinery/store/model/TupleHashProvider.java | 4 +- .../store/model/TupleHashProviderBitMagic.java | 34 -- .../model/internal/ModelStoreBuilderImpl.java | 12 +- .../store/map/tests/InOrderCursorTest.java | 8 +- .../refinery/store/map/tests/MapUnitTests.java | 4 +- .../fuzz/MutableImmutableCompareFuzzTest.java | 18 +- .../store/map/tests/fuzz/SharedStoreFuzzTest.java | 18 +- .../store/map/tests/utils/MapTestEnvironment.java | 6 +- .../store/model/hashtests/HashEfficiencyTest.java | 13 +- 57 files changed, 2849 insertions(+), 2899 deletions(-) delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/ContinuousHashProvider.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/IteratorAsCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaBasedVersionedMapStoreFactory.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaBasedVersionedMapStoreFactory.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaDiffCursor.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapDelta.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaArrayStore.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaMapStore.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaStore.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/InOrderMapCursor.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapCursor.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapDiffCursor.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MutableNode.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/Node.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/OldValueBox.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java diff --git a/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java b/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java index 7e89cd06..4708e6d3 100644 --- a/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java +++ b/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java @@ -5,12 +5,13 @@ */ package tools.refinery.store.map.benchmarks; +import java.util.Objects; import java.util.Random; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.VersionedMapStoreImpl; -import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.internal.state.VersionedMapStoreStateImpl; +import tools.refinery.store.map.internal.state.VersionedMapStateImpl; import tools.refinery.store.map.tests.utils.MapTestEnvironment; import org.openjdk.jmh.annotations.Level; @@ -35,7 +36,7 @@ public class ImmutablePutExecutionPlan { private String[] values; - private ContinousHashProvider hashProvider = MapTestEnvironment.prepareHashProvider(false); + private ContinuousHashProvider hashProvider = MapTestEnvironment.prepareHashProvider(false); @Setup(Level.Trial) public void setUpTrial() { @@ -43,9 +44,9 @@ public class ImmutablePutExecutionPlan { values = MapTestEnvironment.prepareValues(nValues, true); } - public VersionedMapImpl createSut() { - VersionedMapStore store = new VersionedMapStoreImpl(hashProvider, values[0]); - return (VersionedMapImpl) store.createMap(); + public VersionedMapStateImpl createSut() { + VersionedMapStore store = new VersionedMapStoreStateImpl<>(hashProvider, values[0]); + return (VersionedMapStateImpl) store.createMap(); } public Integer nextKey() { @@ -53,7 +54,7 @@ public class ImmutablePutExecutionPlan { } public boolean isDefault(String value) { - return value == values[0]; + return Objects.equals(value,values[0]); } public String nextValue() { diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java b/subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java deleted file mode 100644 index 8e451230..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java +++ /dev/null @@ -1,74 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map; - -import tools.refinery.store.map.internal.Node; - -/** - * A class representing an equivalence relation for a type {@code K} with a - * continuous hash function. - * - * @author Oszkar Semerath - * - * @param Target java type. - */ -public interface ContinousHashProvider { - public static final int EFFECTIVE_BITS = Node.EFFECTIVE_BITS; - public static final int EFFECTIVE_BIT_MASK = (1 << (EFFECTIVE_BITS)) - 1; - - /** - * Maximal practical depth for differentiating keys. If two keys have the same - * hash code until that depth, the algorithm can stop. - */ - public static final int MAX_PRACTICAL_DEPTH = 500; - - /** - * Provides a hash code for a object {@code key} with a given {@code index}. It - * has the following contracts: - *
    - *
  • If {@link #equals}{@code (key1,key2)}, then - * {@code getHash(key1, index) == getHash(key2, index)} for all values of - * {@code index}.
    • - *
  • If {@code getHash(key1,index) == getHash(key2, index)} for all values of - * {@code index}, then {@link #equals}{@code (key1, key2)}
    • - *
  • In current implementation, we use only the least significant - * {@link #EFFECTIVE_BITS} - *
- * Check {@link #equals} for further details. - * - * @param key The target data object. - * @param index The depth of the the hash code. Needs to be non-negative. - * @return A hash code. - */ - public int getHash(K key, int index); - - public default int getEffectiveHash(K key, int index) { - return getHash(key, index) & EFFECTIVE_BIT_MASK; - } - - public default int compare(K key1, K key2) { - if (key1.equals(key2)) { - return 0; - } else { - for (int i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) { - int hash1 = getEffectiveHash(key1, i); - int hash2 = getEffectiveHash(key2, i); - for(int j = 0; j>>j*Node.BRANCHING_FACTOR_BITS) & factorMask; - int hashFragment2 = (hash2>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask; - var result = Integer.compare(hashFragment1, hashFragment2); - if (result != 0) { - return result; - } - } - } - throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2 - + ") have the same hashcode over the practical depth limitation (" - + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); - } - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/ContinuousHashProvider.java b/subprojects/store/src/main/java/tools/refinery/store/map/ContinuousHashProvider.java new file mode 100644 index 00000000..abc044d0 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/ContinuousHashProvider.java @@ -0,0 +1,74 @@ +/* + * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map; + +import tools.refinery.store.map.internal.state.Node; + +/** + * A class representing an equivalence relation for a type {@code K} with a + * continuous hash function. + * + * @author Oszkar Semerath + * + * @param Target java type. + */ +public interface ContinuousHashProvider { + public static final int EFFECTIVE_BITS = Node.EFFECTIVE_BITS; + public static final int EFFECTIVE_BIT_MASK = (1 << (EFFECTIVE_BITS)) - 1; + + /** + * Maximal practical depth for differentiating keys. If two keys have the same + * hash code until that depth, the algorithm can stop. + */ + public static final int MAX_PRACTICAL_DEPTH = 500; + + /** + * Provides a hash code for a object {@code key} with a given {@code index}. It + * has the following contracts: + *
    + *
  • If {@link #equals}{@code (key1,key2)}, then + * {@code getHash(key1, index) == getHash(key2, index)} for all values of + * {@code index}.
    • + *
  • If {@code getHash(key1,index) == getHash(key2, index)} for all values of + * {@code index}, then {@link #equals}{@code (key1, key2)}
    • + *
  • In current implementation, we use only the least significant + * {@link #EFFECTIVE_BITS} + *
+ * Check {@link #equals} for further details. + * + * @param key The target data object. + * @param index The depth of the hash code. Needs to be non-negative. + * @return A hash code. + */ + public int getHash(K key, int index); + + public default int getEffectiveHash(K key, int index) { + return getHash(key, index) & EFFECTIVE_BIT_MASK; + } + + public default int compare(K key1, K key2) { + if (key1.equals(key2)) { + return 0; + } else { + for (int i = 0; i < ContinuousHashProvider.MAX_PRACTICAL_DEPTH; i++) { + int hash1 = getEffectiveHash(key1, i); + int hash2 = getEffectiveHash(key2, i); + for(int j = 0; j>>j*Node.BRANCHING_FACTOR_BITS) & factorMask; + int hashFragment2 = (hash2>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask; + var result = Integer.compare(hashFragment1, hashFragment2); + if (result != 0) { + return result; + } + } + } + throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2 + + ") have the same hashcode over the practical depth limitation (" + + ContinuousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); + } + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/IteratorAsCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/IteratorAsCursor.java new file mode 100644 index 00000000..29b03edf --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/IteratorAsCursor.java @@ -0,0 +1,64 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map; + +import java.util.Iterator; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; + +public class IteratorAsCursor implements Cursor { + final Iterator> iterator; + final VersionedMap source; + + private boolean terminated; + private K key; + private V value; + + public IteratorAsCursor(VersionedMap source, Map current) { + this.iterator = current.entrySet().iterator(); + this.source = source; + } + + @Override + public K getKey() { + return key; + } + + @Override + public V getValue() { + return value; + } + + @Override + public boolean isTerminated() { + return terminated; + } + + @Override + public boolean move() { + terminated = !iterator.hasNext(); + if (terminated) { + this.key = null; + this.value = null; + } else { + Entry next = iterator.next(); + this.key = next.getKey(); + this.value = next.getValue(); + } + return !terminated; + } + + @Override + public boolean isDirty() { + return false; + } + + @Override + public Set getDependingMaps() { + return Set.of(this.source); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java deleted file mode 100644 index b00cd961..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java +++ /dev/null @@ -1,53 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map; - -public class VersionedMapStoreConfiguration { - - public VersionedMapStoreConfiguration() { - - } - public VersionedMapStoreConfiguration(boolean immutableWhenCommitting, boolean sharedNodeCacheInStore, - boolean sharedNodeCacheInStoreGroups) { - super(); - this.immutableWhenCommitting = immutableWhenCommitting; - this.sharedNodeCacheInStore = sharedNodeCacheInStore; - this.sharedNodeCacheInStoreGroups = sharedNodeCacheInStoreGroups; - } - - /** - * If true root is replaced with immutable node when committed. Frees up memory - * by releasing immutable nodes, but it may decrease performance by recreating - * immutable nodes upon changes (some evidence). - */ - private boolean immutableWhenCommitting = true; - public boolean isImmutableWhenCommitting() { - return immutableWhenCommitting; - } - - /** - * If true, all sub-nodes are cached within a {@link VersionedMapStore}. It - * decreases the memory requirements. It may increase performance by discovering - * existing immutable copy of a node (some evidence). Additional overhead may - * decrease performance (no example found). The option permits the efficient - * implementation of version deletion. - */ - private boolean sharedNodeCacheInStore = true; - public boolean isSharedNodeCacheInStore() { - return sharedNodeCacheInStore; - } - - /** - * If true, all sub-nodes are cached within a group of - * {@link VersionedMapStoreImpl#createSharedVersionedMapStores(int, ContinousHashProvider, Object, VersionedMapStoreConfiguration)}. - * If {@link VersionedMapStoreConfiguration#sharedNodeCacheInStore} is - * false, then it has currently no impact. - */ - private boolean sharedNodeCacheInStoreGroups = true; - public boolean isSharedNodeCacheInStoreGroups() { - return sharedNodeCacheInStoreGroups; - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java deleted file mode 100644 index 0c61bd09..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java +++ /dev/null @@ -1,99 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map; - -import java.util.*; - -import tools.refinery.store.map.internal.*; - -public class VersionedMapStoreDeltaImpl implements VersionedMapStore { - // Configuration - protected final boolean summarizeChanges; - - // Static data - protected final V defaultValue; - - // Dynamic data - protected final Map> states = new HashMap<>(); - protected long nextID = 0; - - public VersionedMapStoreDeltaImpl(boolean summarizeChanges, V defaultValue) { - this.summarizeChanges = summarizeChanges; - this.defaultValue = defaultValue; - } - - @Override - public VersionedMap createMap() { - return new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue); - } - - @Override - public VersionedMap createMap(long state) { - VersionedMapDeltaImpl result = new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue); - result.restore(state); - return result; - } - - public synchronized MapTransaction appendTransaction(MapDelta[] deltas, MapTransaction previous, long[] versionContainer) { - long version = nextID++; - versionContainer[0] = version; - if (deltas == null) { - states.put(version, previous); - return previous; - } else { - MapTransaction transaction = new MapTransaction<>(deltas, version, previous); - states.put(version, transaction); - return transaction; - } - } - - private synchronized MapTransaction getState(long state) { - return states.get(state); - } - - public MapTransaction getPath(long to, List[]> forwardTransactions) { - final MapTransaction target = getState(to); - MapTransaction toTransaction = target; - while (toTransaction != null) { - forwardTransactions.add(toTransaction.deltas()); - toTransaction = toTransaction.parent(); - } - return target; - } - - public MapTransaction getPath(long from, long to, - List[]> backwardTransactions, - List[]> forwardTransactions) { - MapTransaction fromTransaction = getState(from); - final MapTransaction target = getState(to); - MapTransaction toTransaction = target; - - while (fromTransaction != toTransaction) { - if (fromTransaction == null || (toTransaction != null && fromTransaction.version() < toTransaction.version())) { - forwardTransactions.add(toTransaction.deltas()); - toTransaction = toTransaction.parent(); - } else { - backwardTransactions.add(fromTransaction.deltas()); - fromTransaction = fromTransaction.parent(); - } - } - return target; - } - - - @Override - public synchronized Set getStates() { - return new HashSet<>(states.keySet()); - } - - @Override - public DiffCursor getDiffCursor(long fromState, long toState) { - List[]> backwardTransactions = new ArrayList<>(); - List[]> forwardTransactions = new ArrayList<>(); - getPath(fromState, toState, backwardTransactions, forwardTransactions); - return new DeltaDiffCursor<>(backwardTransactions, forwardTransactions); - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java index 6329a2f6..6b4fc2a0 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java @@ -22,7 +22,7 @@ public interface VersionedMapStoreFactoryBuilder { VersionedMapStoreFactoryBuilder strategy(StoreStrategy strategy); VersionedMapStoreFactoryBuilder stateBasedImmutableWhenCommitting(boolean transformToImmutable); VersionedMapStoreFactoryBuilder stateBasedSharingStrategy(SharingStrategy sharingStrategy); - VersionedMapStoreFactoryBuilder stateBasedHashProvider(ContinousHashProvider hashProvider); + VersionedMapStoreFactoryBuilder stateBasedHashProvider(ContinuousHashProvider hashProvider); VersionedMapStoreFactoryBuilder deltaTransactionStrategy(DeltaTransactionStrategy deltaStrategy); VersionedMapStoreFactory build(); 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 deleted file mode 100644 index a934d59e..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java +++ /dev/null @@ -1,129 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map; - -import tools.refinery.store.map.internal.*; - -import java.util.*; - -public class VersionedMapStoreImpl implements VersionedMapStore { - // Configuration - private final boolean immutableWhenCommitting; - - // Static data - protected final ContinousHashProvider hashProvider; - protected final V defaultValue; - - // Dynamic data - protected final Map> states = new HashMap<>(); - protected final Map, ImmutableNode> nodeCache; - protected long nextID = 0; - - public VersionedMapStoreImpl(ContinousHashProvider hashProvider, V defaultValue, - VersionedMapStoreConfiguration config) { - this.immutableWhenCommitting = config.isImmutableWhenCommitting(); - this.hashProvider = hashProvider; - this.defaultValue = defaultValue; - if (config.isSharedNodeCacheInStore()) { - nodeCache = new HashMap<>(); - } else { - nodeCache = null; - } - } - - private VersionedMapStoreImpl(ContinousHashProvider hashProvider, V defaultValue, - Map, ImmutableNode> nodeCache, VersionedMapStoreConfiguration config) { - this.immutableWhenCommitting = config.isImmutableWhenCommitting(); - this.hashProvider = hashProvider; - this.defaultValue = defaultValue; - this.nodeCache = nodeCache; - } - - public VersionedMapStoreImpl(ContinousHashProvider hashProvider, V defaultValue) { - this(hashProvider, defaultValue, new VersionedMapStoreConfiguration()); - } - - public static List> createSharedVersionedMapStores(int amount, - ContinousHashProvider hashProvider, V defaultValue, - VersionedMapStoreConfiguration config) { - List> result = new ArrayList<>(amount); - if (config.isSharedNodeCacheInStoreGroups()) { - Map, ImmutableNode> nodeCache; - if (config.isSharedNodeCacheInStore()) { - nodeCache = new HashMap<>(); - } else { - nodeCache = null; - } - for (int i = 0; i < amount; i++) { - result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, nodeCache, config)); - } - } else { - for (int i = 0; i < amount; i++) { - result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, config)); - } - } - return result; - } - - public static List> createSharedVersionedMapStores(int amount, - ContinousHashProvider hashProvider, V defaultValue) { - return createSharedVersionedMapStores(amount, hashProvider, defaultValue, new VersionedMapStoreConfiguration()); - } - - @Override - public synchronized Set getStates() { - return new HashSet<>(states.keySet()); - } - - @Override - public VersionedMap createMap() { - return new VersionedMapImpl<>(this, hashProvider, defaultValue); - } - - @Override - public VersionedMap createMap(long state) { - ImmutableNode data = revert(state); - return new VersionedMapImpl<>(this, hashProvider, defaultValue, data); - } - - public synchronized ImmutableNode revert(long state) { - if (states.containsKey(state)) { - return states.get(state); - } else { - ArrayList existingKeys = new ArrayList<>(states.keySet()); - Collections.sort(existingKeys); - throw new IllegalArgumentException("Store does not contain state " + state + "! Available states: " - + Arrays.toString(existingKeys.toArray())); - } - } - - public synchronized long commit(Node data, VersionedMapImpl mapToUpdateRoot) { - ImmutableNode immutable; - if (data != null) { - immutable = data.toImmutable(this.nodeCache); - } else { - immutable = null; - } - - if (nextID == Long.MAX_VALUE) - throw new IllegalStateException("Map store run out of Id-s"); - long id = nextID++; - this.states.put(id, immutable); - if (this.immutableWhenCommitting) { - mapToUpdateRoot.setRoot(immutable); - } - return id; - } - - @Override - public DiffCursor getDiffCursor(long fromState, long toState) { - 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/DeltaBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaBasedVersionedMapStoreFactory.java deleted file mode 100644 index fe490f46..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaBasedVersionedMapStoreFactory.java +++ /dev/null @@ -1,39 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.VersionedMapStoreDeltaImpl; -import tools.refinery.store.map.VersionedMapStoreFactory; -import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; - -import java.util.ArrayList; -import java.util.List; - -public class DeltaBasedVersionedMapStoreFactory implements VersionedMapStoreFactory { - private final V defaultValue; - private final boolean summarizeChanges; - - public DeltaBasedVersionedMapStoreFactory(V defaultValue, - VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy deltaTransactionStrategy) { - this.defaultValue = defaultValue; - this.summarizeChanges = deltaTransactionStrategy == VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.SET; - } - - @Override - public VersionedMapStore createOne() { - return new VersionedMapStoreDeltaImpl<>(summarizeChanges, defaultValue); - } - - @Override - public List> createGroup(int amount) { - List> result = new ArrayList<>(amount); - for(int i=0; i(summarizeChanges,defaultValue)); - } - return result; - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java deleted file mode 100644 index cc9003e3..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java +++ /dev/null @@ -1,147 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.AnyVersionedMap; -import tools.refinery.store.map.DiffCursor; - -import java.util.Collections; -import java.util.List; -import java.util.Set; - -public class DeltaDiffCursor implements DiffCursor { - final List[]> backwardTransactions; - final List[]> forwardTransactions; - - boolean started; - /** - * Denotes the direction of traversal. False means backwards, true means - * forward. - */ - boolean direction; - int listIndex; - int arrayIndex; - - public DeltaDiffCursor(List[]> backwardTransactions, List[]> forwardTransactions) { - this.backwardTransactions = backwardTransactions; - this.forwardTransactions = forwardTransactions; - - if (!backwardTransactions.isEmpty()) { - direction = false; - listIndex = 0; - arrayIndex = backwardTransactions.get(listIndex).length - 1; - } else if (!forwardTransactions.isEmpty()) { - direction = true; - listIndex = forwardTransactions.size() - 1; - arrayIndex = 0; - } else { - direction = true; - listIndex = -1; - } - started = false; - } - - protected MapDelta getCurrentDelta() { - final List[]> list; - if (!direction) { - list = this.backwardTransactions; - } else { - list = this.forwardTransactions; - } - return list.get(listIndex)[arrayIndex]; - } - - @Override - public K getKey() { - return getCurrentDelta().getKey(); - } - - @Override - public V getValue() { - return getToValue(); - } - - @Override - public boolean isTerminated() { - return this.direction && listIndex == -1; - } - - - @Override - public boolean move() { - if(!started) { - started = true; - return !isTerminated(); - } else if (isTerminated()) { - return false; - } else { - if (this.direction) { - if (arrayIndex+1 < forwardTransactions.get(listIndex).length) { - arrayIndex++; - return true; - } else { - if (listIndex-1 >= 0) { - listIndex--; - arrayIndex = 0; - return true; - } else { - listIndex = -1; - return false; - } - } - } else { - if (arrayIndex > 0) { - arrayIndex--; - return true; - } else { - if (listIndex+1 < backwardTransactions.size()) { - listIndex++; - this.arrayIndex = backwardTransactions.get(listIndex).length - 1; - return true; - } else { - this.direction = true; - if (!this.forwardTransactions.isEmpty()) { - listIndex = forwardTransactions.size() - 1; - arrayIndex = 0; - return true; - } else { - listIndex = -1; - return false; - } - } - } - } - } - } - - @Override - public boolean isDirty() { - return false; - } - - @Override - public Set getDependingMaps() { - return Collections.emptySet(); - } - - @Override - public V getFromValue() { - if(this.direction) { - return getCurrentDelta().getOldValue(); - } else { - return getCurrentDelta().getNewValue(); - } - } - - @Override - public V getToValue() { - if(this.direction) { - return getCurrentDelta().getNewValue(); - } else { - return getCurrentDelta().getOldValue(); - } - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java deleted file mode 100644 index a357fbce..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java +++ /dev/null @@ -1,23 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -enum HashClash { - /** - * Not stuck. - */ - NONE, - - /** - * Clashed, next we should return the key of cursor 1. - */ - STUCK_CURSOR_1, - - /** - * Clashed, next we should return the key of cursor 2. - */ - STUCK_CURSOR_2 -} 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 deleted file mode 100644 index d052318f..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java +++ /dev/null @@ -1,413 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import java.util.Arrays; -import java.util.Map; - -import tools.refinery.store.map.ContinousHashProvider; - -public class ImmutableNode extends Node { - /** - * Bitmap defining the stored key and values. - */ - final int dataMap; - /** - * Bitmap defining the positions of further nodes. - */ - final int nodeMap; - /** - * Stores Keys, Values, and sub-nodes. Structure: (K,V)*,NODE; NODES are stored - * backwards. - */ - final Object[] content; - - /** - * Hash code derived from immutable hash code - */ - final int precalculatedHash; - - private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) { - super(); - this.dataMap = dataMap; - this.nodeMap = nodeMap; - this.content = content; - this.precalculatedHash = precalculatedHash; - } - - /** - * Constructor that copies a mutable node to an immutable. - * - * @param node A mutable node. - * @param cache A cache of existing immutable nodes. It can be used to search - * and place reference immutable nodes. It can be null, if no cache - * available. - * @return an immutable version of the input node. - */ - static ImmutableNode constructImmutable(MutableNode node, Map, ImmutableNode> cache) { - // 1. try to return from cache - if (cache != null) { - ImmutableNode cachedResult = cache.get(node); - if (cachedResult != null) { - // 1.1 Already cached, return from cache. - return cachedResult; - } - } - - // 2. otherwise construct a new ImmutableNode - int size = 0; - for (int i = 0; i < node.content.length; i++) { - if (node.content[i] != null) { - size++; - } - } - - int datas = 0; - int nodes = 0; - int resultDataMap = 0; - int resultNodeMap = 0; - final Object[] resultContent = new Object[size]; - int bitPosition = 1; - for (int i = 0; i < FACTOR; i++) { - Object key = node.content[i * 2]; - if (key != null) { - 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; - nodes++; - } - } - bitPosition <<= 1; - } - final int resultHash = node.hashCode(); - var newImmutable = new ImmutableNode(resultDataMap, resultNodeMap, resultContent, resultHash); - - // 3. save new immutable. - if (cache != null) { - cache.put(newImmutable, newImmutable); - } - return newImmutable; - } - - private int index(int bitmap, int bitpos) { - return Integer.bitCount(bitmap & (bitpos - 1)); - } - - @Override - public V getValue(K key, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { - int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); - int bitposition = 1 << selectedHashFragment; - // If the key is stored as a data - if ((dataMap & bitposition) != 0) { - int keyIndex = 2 * index(dataMap, bitposition); - @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; - if (keyCandidate.equals(key)) { - @SuppressWarnings("unchecked") V value = (V) content[keyIndex + 1]; - return value; - } else { - return defaultValue; - } - } - // the key is stored as a node - 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); - return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); - } - // the key is not stored at all - else { - return defaultValue; - } - } - - @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); - @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; - if (keyCandidate.equals(key)) { - if (value == defaultValue) { - // delete - MutableNode mutable = this.toMutable(); - return mutable.removeEntry(selectedHashFragment, oldValue); - } else if (value == content[keyIndex + 1]) { - // dont change - oldValue.setOldValue(value); - return this; - } else { - // update existing value - MutableNode mutable = this.toMutable(); - return mutable.updateValue(value, oldValue, selectedHashFragment); - } - } else { - if (value == defaultValue) { - // dont change - oldValue.setOldValue(defaultValue); - return this; - } else { - // add new key + value - MutableNode mutable = this.toMutable(); - return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); - } - } - } 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); - var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); - - if (subNode == newsubNode) { - // nothing changed - return this; - } else { - MutableNode mutable = toMutable(); - return mutable.updateWithSubNode(selectedHashFragment, newsubNode, - (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); - } - } else { - // add new key + value - MutableNode mutable = this.toMutable(); - return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); - } - } - - @Override - public long getSize() { - int result = Integer.bitCount(this.dataMap); - for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { - @SuppressWarnings("unchecked") var subnode = (ImmutableNode) this.content[this.content.length - 1 - subnodeIndex]; - result += subnode.getSize(); - } - return result; - } - - @Override - protected MutableNode toMutable() { - return new MutableNode<>(this); - } - - @Override - public ImmutableNode toImmutable(Map, ImmutableNode> cache) { - return this; - } - - @Override - protected MutableNode isMutable() { - return null; - } - - @SuppressWarnings("unchecked") - @Override - boolean moveToNext(MapCursor cursor) { - // 1. try to move to data - int datas = Integer.bitCount(this.dataMap); - if (cursor.dataIndex != MapCursor.INDEX_FINISH) { - int newDataIndex = cursor.dataIndex + 1; - if (newDataIndex < datas) { - cursor.dataIndex = newDataIndex; - cursor.key = (K) this.content[newDataIndex * 2]; - cursor.value = (V) this.content[newDataIndex * 2 + 1]; - return true; - } else { - cursor.dataIndex = MapCursor.INDEX_FINISH; - } - } - - // 2. look inside the subnodes - int nodes = Integer.bitCount(this.nodeMap); - if(cursor.nodeIndexStack.peek()==null) { - throw new IllegalStateException("Cursor moved to the next state when the state is empty."); - } - int newNodeIndex = cursor.nodeIndexStack.peek() + 1; - if (newNodeIndex < nodes) { - // 2.1 found next subnode, move down to the subnode - Node subnode = (Node) this.content[this.content.length - 1 - newNodeIndex]; - cursor.dataIndex = MapCursor.INDEX_START; - cursor.nodeIndexStack.pop(); - cursor.nodeIndexStack.push(newNodeIndex); - cursor.nodeIndexStack.push(MapCursor.INDEX_START); - cursor.nodeStack.push(subnode); - return subnode.moveToNext(cursor); - } else { - // 3. no subnode found, move up - cursor.nodeStack.pop(); - cursor.nodeIndexStack.pop(); - if (!cursor.nodeStack.isEmpty()) { - Node supernode = cursor.nodeStack.peek(); - return supernode.moveToNext(cursor); - } else { - cursor.key = null; - cursor.value = null; - return false; - } - } - } - - @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))); - if (code >= 0) { - builder.append(code); - builder.append(":"); - } - builder.append("Immutable("); - boolean hadContent = false; - int dataMask = 1; - for (int i = 0; i < FACTOR; i++) { - if ((dataMask & dataMap) != 0) { - if (hadContent) { - builder.append(","); - } - builder.append(i); - builder.append(":["); - builder.append(content[2 * index(dataMap, dataMask)].toString()); - builder.append("]->["); - builder.append(content[2 * index(dataMap, dataMask) + 1].toString()); - builder.append("]"); - hadContent = true; - } - dataMask <<= 1; - } - builder.append(")"); - int nodeMask = 1; - for (int i = 0; i < FACTOR; i++) { - if ((nodeMask & nodeMap) != 0) { - @SuppressWarnings("unchecked") Node subNode = (Node) content[content.length - 1 - index(nodeMap, nodeMask)]; - builder.append("\n"); - subNode.prettyPrint(builder, incrementDepth(depth), i); - } - nodeMask <<= 1; - } - } - - @Override - public void checkIntegrity(ContinousHashProvider hashProvider, V defaultValue, int depth) { - if (depth > 0) { - boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0; - if (orphaned) { - throw new IllegalStateException("Orphaned node! " + dataMap + ": " + content[0]); - } - } - // check the place of data - - // check subnodes - for (int i = 0; i < Integer.bitCount(nodeMap); i++) { - @SuppressWarnings("unchecked") var subnode = (Node) this.content[this.content.length - 1 - i]; - if (!(subnode instanceof ImmutableNode)) { - throw new IllegalStateException("Immutable node contains mutable subnodes!"); - } else { - subnode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); - } - } - } - - @Override - public int hashCode() { - return this.precalculatedHash; - } - - @Override - public boolean equals(Object obj) { - if (this == obj) return true; - if (obj == null) return false; - if (obj instanceof ImmutableNode other) { - return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap && Arrays.deepEquals(content, other.content); - } else if (obj instanceof MutableNode mutableObj) { - return ImmutableNode.compareImmutableMutable(this, mutableObj); - } else { - return false; - } - } - - public static boolean compareImmutableMutable(ImmutableNode immutable, MutableNode mutable) { - int datas = 0; - int nodes = 0; - final int immutableLength = immutable.content.length; - for (int i = 0; i < FACTOR; i++) { - Object key = mutable.content[i * 2]; - // For each key candidate - if (key != null) { - // Check whether a new Key-Value pair can fit into the immutable container - if (datas * 2 + nodes + 2 <= immutableLength) { - if (!immutable.content[datas * 2].equals(key) || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) { - return false; - } - } else return false; - datas++; - } else { - 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)) { - return false; - } - nodes++; - } else { - return false; - } - } - } - } - - 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 deleted file mode 100644 index cb3f366f..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java +++ /dev/null @@ -1,146 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -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/IteratorAsCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java deleted file mode 100644 index d1ab8bb1..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java +++ /dev/null @@ -1,66 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import java.util.*; -import java.util.Map.Entry; - -import tools.refinery.store.map.AnyVersionedMap; -import tools.refinery.store.map.Cursor; -import tools.refinery.store.map.VersionedMap; - -public class IteratorAsCursor implements Cursor { - final Iterator> iterator; - final VersionedMap source; - - private boolean terminated; - private K key; - private V value; - - public IteratorAsCursor(VersionedMap source, Map current) { - this.iterator = current.entrySet().iterator(); - this.source = source; - } - - @Override - public K getKey() { - return key; - } - - @Override - public V getValue() { - return value; - } - - @Override - public boolean isTerminated() { - return terminated; - } - - @Override - public boolean move() { - terminated = !iterator.hasNext(); - if (terminated) { - this.key = null; - this.value = null; - } else { - Entry next = iterator.next(); - this.key = next.getKey(); - this.value = next.getValue(); - } - return !terminated; - } - - @Override - public boolean isDirty() { - return false; - } - - @Override - public Set getDependingMaps() { - return Set.of(this.source); - } -} 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 deleted file mode 100644 index d42519b2..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java +++ /dev/null @@ -1,95 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -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.ArrayDeque; -import java.util.ConcurrentModificationException; -import java.util.Set; - -public class MapCursor implements Cursor { - // Constants - static final int INDEX_START = -1; - static final int INDEX_FINISH = -2; - - // Tree stack - ArrayDeque> nodeStack; - ArrayDeque nodeIndexStack; - int dataIndex; - - // Values - K key; - V value; - - // Hash code for checking concurrent modifications - final VersionedMap map; - final int creationHash; - - public MapCursor(Node root, VersionedMap map) { - // Initializing tree stack - super(); - this.nodeStack = new ArrayDeque<>(); - this.nodeIndexStack = new ArrayDeque<>(); - if (root != null) { - this.nodeStack.add(root); - this.nodeIndexStack.push(INDEX_START); - } - - this.dataIndex = 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.moveToNext(this); - if (this.nodeIndexStack.size() != this.nodeStack.size()) { - throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); - } - return result; - } - return false; - } - - @Override - public boolean isDirty() { - return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; - } - - @Override - public Set getDependingMaps() { - return Set.of(this.map); - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java deleted file mode 100644 index 2674236c..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java +++ /dev/null @@ -1,20 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -public record MapDelta(K key, V oldValue, V newValue) { - public K getKey() { - return key; - } - - public V getOldValue() { - return oldValue; - } - - public V getNewValue() { - return newValue; - } -} 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 deleted file mode 100644 index fb1d5d2b..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java +++ /dev/null @@ -1,264 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.AnyVersionedMap; -import tools.refinery.store.map.Cursor; -import tools.refinery.store.map.DiffCursor; - -import java.util.Objects; -import java.util.Set; -import java.util.stream.Collectors; -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 InOrderMapCursor cursor1; - private final InOrderMapCursor cursor2; - - // State - State state = State.INIT; - - // Values - private K key; - private V fromValue; - private V toValue; - - - public MapDiffCursor(V defaultValue, InOrderMapCursor cursor1, InOrderMapCursor cursor2) { - super(); - this.defaultValue = defaultValue; - this.cursor1 = cursor1; - this.cursor2 = cursor2; - } - - @Override - public K getKey() { - return key; - } - - @Override - public V getFromValue() { - return fromValue; - } - - @Override - public V getToValue() { - return toValue; - } - - @Override - public V getValue() { - return getToValue(); - } - - public boolean isTerminated() { - return this.state == State.TERMINATED_TERMINATED; - } - - @Override - public boolean isDirty() { - return this.cursor1.isDirty() || this.cursor2.isDirty(); - } - - @Override - public Set getDependingMaps() { - return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).map(AnyVersionedMap.class::cast).collect(Collectors.toUnmodifiableSet()); - } - - private boolean isInStableState() { - return this.state != State.MOVING_MOVING_SAME_KEY_SAME_VALUE - && this.state != State.MOVING_MOVING_SAME_NODE && this.state != State.INIT; - } - - 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; - } - }; - } - - public boolean move() { - do { - this.state = moveOne(this.state); - } while (!isInStableState()); - return updateAndReturnWithResult(); - } - - 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!"); - }; - } - - 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 { - return State.TERMINATED_TERMINATED; - } - } - - private State recalculateStateBasedOnCursorRelation() { - final int relation = InOrderMapCursor.comparePosition(cursor1, cursor2); - - if (relation > 0) { - return State.MOVING_MOVING_BEHIND1; - } else if (relation < 0) { - return State.MOVING_MOVING_BEHIND2; - } - - 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 { - 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; - } - - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java deleted file mode 100644 index d63522cd..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java +++ /dev/null @@ -1,39 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import java.util.Arrays; -import java.util.Objects; - -public record MapTransaction(MapDelta[] deltas, long version, MapTransaction parent) { - - @Override - public int hashCode() { - final int prime = 31; - int result = 1; - result = prime * result + Arrays.hashCode(deltas); - result = prime * result + Objects.hash(parent, version); - return result; - } - - @Override - public boolean equals(Object obj) { - if (this == obj) - return true; - if (obj == null) - return false; - if (getClass() != obj.getClass()) - return false; - @SuppressWarnings("unchecked") - MapTransaction other = (MapTransaction) obj; - return Arrays.equals(deltas, other.deltas) && Objects.equals(parent, other.parent) && version == other.version; - } - - @Override - public String toString() { - return "MapTransaction " + version + " " + Arrays.toString(deltas); - } -} 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 deleted file mode 100644 index bb85deb9..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java +++ /dev/null @@ -1,499 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.ContinousHashProvider; - -import java.util.Arrays; -import java.util.Map; - -public class MutableNode extends Node { - int cachedHash; - protected boolean cachedHashValid; - protected Object[] content; - - protected MutableNode() { - this.content = new Object[2 * FACTOR]; - invalidateHash(); - } - - public static MutableNode initialize(K key, V value, ContinousHashProvider hashProvider, V defaultValue) { - if (value == defaultValue) { - return null; - } else { - int hash = hashProvider.getHash(key, 0); - int fragment = hashFragment(hash, 0); - MutableNode res = new MutableNode<>(); - res.content[2 * fragment] = key; - res.content[2 * fragment + 1] = value; - res.invalidateHash(); - return res; - } - } - - /** - * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} - * - * @param node to be transformed - */ - protected MutableNode(ImmutableNode node) { - this.content = new Object[2 * FACTOR]; - int dataUsed = 0; - int nodeUsed = 0; - for (int i = 0; i < FACTOR; i++) { - 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) { - content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; - nodeUsed++; - } - } - this.cachedHashValid = false; - } - - @Override - public V getValue(K key, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { - int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); - @SuppressWarnings("unchecked") K keyCandidate = (K) this.content[2 * selectedHashFragment]; - if (keyCandidate != null) { - if (keyCandidate.equals(key)) { - @SuppressWarnings("unchecked") V value = (V) this.content[2 * selectedHashFragment + 1]; - return value; - } else { - return defaultValue; - } - } else { - @SuppressWarnings("unchecked") var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; - if (nodeCandidate != null) { - int newDepth = incrementDepth(depth); - int newHash = newHash(hashProvider, key, hash, newDepth); - return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); - } else { - return defaultValue; - } - } - } - - @Override - public Node putValue(K key, V value, OldValueBox oldValueBox, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { - int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); - @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment]; - if (keyCandidate != null) { - // If it has key - if (keyCandidate.equals(key)) { - // The key is equals to an existing key -> update entry - if (value == defaultValue) { - return removeEntry(selectedHashFragment, oldValueBox); - } else { - return updateValue(value, oldValueBox, selectedHashFragment); - } - } else { - // The key is not equivalent to an existing key on the same hash bin - // -> split entry if it is necessary - if (value == defaultValue) { - // Value is default -> do not need to add new node - oldValueBox.setOldValue(defaultValue); - return this; - } else { - // Value is not default -> Split entry data to a new node - oldValueBox.setOldValue(defaultValue); - 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 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 { - return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue); - } - } - } - - private Node addEntry(K key, V value, OldValueBox oldValueBox, int selectedHashFragment, V defaultValue) { - content[2 * selectedHashFragment] = key; - oldValueBox.setOldValue(defaultValue); - content[2 * selectedHashFragment + 1] = value; - invalidateHash(); - return this; - } - - /** - * Updates an entry in a selected hash-fragment to a non-default value. - * - * @param value new value - * @param selectedHashFragment position of the value - * @return updated node - */ - @SuppressWarnings("unchecked") - Node updateValue(V value, OldValueBox oldValue, int selectedHashFragment) { - oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); - content[2 * selectedHashFragment + 1] = value; - invalidateHash(); - return this; - } - - /** - * Updates an entry in a selected hash-fragment with a subtree. - * - * @param selectedHashFragment position of the value - * @param newNode the subtree - * @return updated node - */ - Node updateWithSubNode(int selectedHashFragment, Node newNode, boolean deletionHappened) { - if (deletionHappened) { - if (newNode == null) { - // Check whether this node become empty - content[2 * selectedHashFragment + 1] = null; // i.e. the new node - if (hasContent()) { - invalidateHash(); - return this; - } else { - return null; - } - } else { - // check whether newNode is orphan - MutableNode immutableNewNode = newNode.isMutable(); - if (immutableNewNode != null) { - int orphaned = immutableNewNode.isOrphaned(); - if (orphaned >= 0) { - // 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(); - return this; - } - } - } - } - // normal behaviour - content[2 * selectedHashFragment + 1] = newNode; - invalidateHash(); - return this; - } - - private boolean hasContent() { - for (Object element : this.content) { - if (element != null) return true; - } - return false; - } - - @Override - protected MutableNode isMutable() { - return this; - } - - protected int isOrphaned() { - int dataFound = -2; - for (int i = 0; i < FACTOR; i++) { - if (content[i * 2] != null) { - if (dataFound >= 0) { - return -1; - } else { - dataFound = i; - } - } else if (content[i * 2 + 1] != null) { - return -3; - } - } - return dataFound; - } - - @SuppressWarnings("unchecked") - private Node moveDownAndSplit(ContinousHashProvider hashProvider, K newKey, V newValue, K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { - V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1]; - - MutableNode newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, incrementDepth(depth)); - - content[2 * selectedHashFragmentOfCurrentDepth] = null; - content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; - invalidateHash(); - return this; - } - - // 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)); - - MutableNode subNode = new MutableNode<>(); - if (newFragment1 != newFragment2) { - subNode.content[newFragment1 * 2] = key1; - subNode.content[newFragment1 * 2 + 1] = value1; - - subNode.content[newFragment2 * 2] = key2; - subNode.content[newFragment2 * 2 + 1] = value2; - } else { - MutableNode subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newDepth)); - subNode.content[newFragment1 * 2 + 1] = subSubNode; - } - subNode.invalidateHash(); - return subNode; - } - - @SuppressWarnings("unchecked") - Node removeEntry(int selectedHashFragment, OldValueBox oldValue) { - content[2 * selectedHashFragment] = null; - oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); - content[2 * selectedHashFragment + 1] = null; - if (hasContent()) { - invalidateHash(); - return this; - } else { - return null; - } - } - - @SuppressWarnings("unchecked") - @Override - public long getSize() { - int size = 0; - for (int i = 0; i < FACTOR; i++) { - if (content[i * 2] != null) { - size++; - } else { - Node nodeCandidate = (Node) content[i * 2 + 1]; - if (nodeCandidate != null) { - size += nodeCandidate.getSize(); - } - } - } - return size; - } - - @Override - protected MutableNode toMutable() { - return this; - } - - @Override - public ImmutableNode toImmutable(Map, ImmutableNode> cache) { - return ImmutableNode.constructImmutable(this, cache); - } - - @SuppressWarnings("unchecked") - @Override - boolean moveToNext(MapCursor cursor) { - // 1. try to move to data - if (cursor.dataIndex != MapCursor.INDEX_FINISH) { - for (int index = cursor.dataIndex + 1; index < FACTOR; index++) { - if (this.content[index * 2] != null) { - // 1.1 found next data - cursor.dataIndex = index; - cursor.key = (K) this.content[index * 2]; - cursor.value = (V) this.content[index * 2 + 1]; - return true; - } - } - cursor.dataIndex = MapCursor.INDEX_FINISH; - } - - // 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 sub-node, move down to the sub-node - Node subnode = (Node) this.content[index * 2 + 1]; - - cursor.dataIndex = MapCursor.INDEX_START; - cursor.nodeIndexStack.pop(); - cursor.nodeIndexStack.push(index); - cursor.nodeIndexStack.push(MapCursor.INDEX_START); - cursor.nodeStack.push(subnode); - - return subnode.moveToNext(cursor); - } - } - // 3. no sub-node found, move up - cursor.nodeStack.pop(); - cursor.nodeIndexStack.pop(); - if (!cursor.nodeStack.isEmpty()) { - Node supernode = cursor.nodeStack.peek(); - return supernode.moveToNext(cursor); - } else { - cursor.key = null; - cursor.value = null; - return false; - } - } - - @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))); - if (code >= 0) { - builder.append(code); - builder.append(":"); - } - builder.append("Mutable("); - // print content - boolean hadContent = false; - for (int i = 0; i < FACTOR; i++) { - if (content[2 * i] != null) { - if (hadContent) { - builder.append(","); - } - builder.append(i); - builder.append(":["); - builder.append(content[2 * i].toString()); - builder.append("]->["); - builder.append(content[2 * i + 1].toString()); - builder.append("]"); - hadContent = true; - } - } - builder.append(")"); - // 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]; - builder.append("\n"); - subNode.prettyPrint(builder, incrementDepth(depth), i); - } - } - } - - @Override - public void checkIntegrity(ContinousHashProvider hashProvider, V defaultValue, int depth) { - // check for orphan nodes - if (depth > 0) { - int orphaned = isOrphaned(); - if (orphaned >= 0) { - throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]); - } - } - // check the place of data - for (int i = 0; i < FACTOR; i++) { - if (this.content[2 * i] != null) { - @SuppressWarnings("unchecked") K key = (K) this.content[2 * i]; - @SuppressWarnings("unchecked") V value = (V) this.content[2 * i + 1]; - - if (value == defaultValue) { - throw new IllegalStateException("Node contains default value!"); - } - int hashCode = hashProvider.getHash(key, hashDepth(depth)); - int shiftDepth = shiftDepth(depth); - int selectedHashFragment = hashFragment(hashCode, shiftDepth); - if (i != selectedHashFragment) { - throw new IllegalStateException("Key " + key + " with hash code " + hashCode + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); - } - } - } - // 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]; - subNode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); - } - } - // check the hash - if (cachedHashValid) { - int oldHash = this.cachedHash; - invalidateHash(); - int newHash = hashCode(); - if (oldHash != newHash) { - throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); - } - } - } - - protected void invalidateHash() { - this.cachedHashValid = false; - } - - @Override - public int hashCode() { - if (!this.cachedHashValid) { - this.cachedHash = Arrays.hashCode(content); - this.cachedHashValid = true; - } - return this.cachedHash; - } - - @Override - public boolean equals(Object obj) { - if (this == obj) return true; - if (obj == null) return false; - if (obj instanceof MutableNode mutableObj) { - if (obj.hashCode() != this.hashCode()) { - return false; - } else { - for (int i = 0; i < FACTOR * 2; i++) { - Object thisContent = this.content[i]; - if (thisContent != null && !thisContent.equals(mutableObj.content[i])) { - return false; - } - } - return true; - } - } else if (obj instanceof ImmutableNode immutableObj) { - return ImmutableNode.compareImmutableMutable(immutableObj, this); - } else { - return false; - } - } -} 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 deleted file mode 100644 index 4b44f760..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java +++ /dev/null @@ -1,131 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import java.util.Map; - -import tools.refinery.store.map.ContinousHashProvider; - -public abstract class Node { - public static final int BRANCHING_FACTOR_BITS = 5; - public static final int FACTOR = 1 << BRANCHING_FACTOR_BITS; - protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS; - protected static final int FACTOR_MASK = FACTOR - 1; - public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS; - public static final int FACTOR_SELECTION_BITS = 32 - Integer.numberOfLeadingZeros(NUMBER_OF_FACTORS); - public static final int FACTOR_SELECTION_MASK = (1 << FACTOR_SELECTION_BITS) - 1; - public static final int INCREMENT_BIG_STEP = (1 << FACTOR_SELECTION_BITS) - NUMBER_OF_FACTORS; - - /** - * Increments the depth of the search in the tree. The depth parameter has two - * components: the least few bits selects the fragment of the hashcode, the - * other part selects the continuous hash. - * - * @param depth parameter encoding the fragment and the depth - * @return new depth. - */ - protected int incrementDepth(int depth) { - int newDepth = depth + 1; - if ((newDepth & FACTOR_SELECTION_MASK) == NUMBER_OF_FACTORS) { - newDepth += INCREMENT_BIG_STEP; - } - return newDepth; - } - - /** - * Calculates the index for the continuous hash. - * - * @param depth The depth of the node in the tree. - * @return The index of the continuous hash. - */ - protected static int hashDepth(int depth) { - return depth >> FACTOR_SELECTION_BITS; - } - - /** - * Calculates the which segment of a single hash should be used. - * - * @param depth The depth of the node in the tree. - * @return The segment of a hash code. - */ - protected static int shiftDepth(int depth) { - return depth & FACTOR_SELECTION_MASK; - } - - /** - * Selects a segments from a complete hash for a given depth. - * - * @param hash A complete hash. - * @param shiftDepth The index of the segment. - * @return The segment as an integer. - */ - protected static int hashFragment(int hash, int shiftDepth) { - if (shiftDepth < 0 || Node.NUMBER_OF_FACTORS < shiftDepth) - throw new IllegalArgumentException("Invalid shift depth! valid interval=[0;5], input=" + shiftDepth); - return (hash >>> shiftDepth * BRANCHING_FACTOR_BITS) & FACTOR_MASK; - } - - /** - * Returns the hash code for a given depth. It may calculate new hash code, or - * reuse a hash code calculated for depth-1. - * - * @param key The key. - * @param hash Hash code for depth-1 - * @param depth The depth. - * @return The new hash code. - */ - protected int newHash(final ContinousHashProvider hashProvider, K key, int hash, int depth) { - final int shiftDepth = shiftDepth(depth); - if (shiftDepth == 0) { - final int hashDepth = hashDepth(depth); - if (hashDepth >= ContinousHashProvider.MAX_PRACTICAL_DEPTH) { - throw new IllegalArgumentException( - "Key " + key + " have the clashing hashcode over the practical depth limitation (" - + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); - } - return hashProvider.getHash(key, hashDepth); - } else { - return hash; - } - } - - public abstract V getValue(K key, ContinousHashProvider hashProvider, V defaultValue, int hash, - int depth); - - public abstract Node putValue(K key, V value, OldValueBox old, - ContinousHashProvider hashProvider, V defaultValue, int hash, int depth); - - public abstract long getSize(); - - abstract MutableNode toMutable(); - - public abstract ImmutableNode toImmutable(Map, ImmutableNode> cache); - - protected abstract MutableNode isMutable(); - - /** - * Moves a {@link MapCursor} to its next position. - * - * @param cursor the cursor - * @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(); - prettyPrint(stringBuilder, 0, -1); - return stringBuilder.toString(); - } - - public void checkIntegrity(ContinousHashProvider hashProvider, V defaultValue, int depth) { - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java deleted file mode 100644 index 354af51d..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java +++ /dev/null @@ -1,24 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -public class OldValueBox{ - V oldValue; - boolean isSet = false; - - public V getOldValue() { - if(!isSet) throw new IllegalStateException(); - isSet = false; - return oldValue; - } - - public void setOldValue(V ouldValue) { - if(isSet) throw new IllegalStateException(); - this.oldValue = ouldValue; - isSet = true; - } - -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java deleted file mode 100644 index 1c3ab27b..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java +++ /dev/null @@ -1,38 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.*; - -import java.util.List; - -public class StateBasedVersionedMapStoreFactory implements VersionedMapStoreFactory { - private final V defaultValue; - private final ContinousHashProvider continousHashProvider; - private final VersionedMapStoreConfiguration config; - - public StateBasedVersionedMapStoreFactory(V defaultValue, Boolean transformToImmutable, VersionedMapStoreFactoryBuilder.SharingStrategy sharingStrategy, ContinousHashProvider continousHashProvider) { - this.defaultValue = defaultValue; - this.continousHashProvider = continousHashProvider; - - this.config = new VersionedMapStoreConfiguration( - transformToImmutable, - sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE || sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP, - sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP); - } - - @Override - public VersionedMapStore createOne() { - return new VersionedMapStoreImpl<>(continousHashProvider, defaultValue, config); - - } - - @Override - public List> createGroup(int amount) { - return VersionedMapStoreImpl.createSharedVersionedMapStores(amount, continousHashProvider, defaultValue, - config); - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java deleted file mode 100644 index ba59cfef..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java +++ /dev/null @@ -1,36 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import java.util.ArrayList; -import java.util.List; - -public class UncommittedDeltaArrayStore implements UncommittedDeltaStore { - final List> uncommittedOldValues = new ArrayList<>(); - - @Override - public void processChange(K key, V oldValue, V newValue) { - uncommittedOldValues.add(new MapDelta<>(key, oldValue, newValue)); - } - - @Override - public MapDelta[] extractDeltas() { - if (uncommittedOldValues.isEmpty()) { - return null; - } else { - @SuppressWarnings("unchecked") - MapDelta[] result = uncommittedOldValues.toArray(new MapDelta[0]); - return result; - } - } - - @Override - public MapDelta[] extractAndDeleteDeltas() { - MapDelta[] res = extractDeltas(); - this.uncommittedOldValues.clear(); - return res; - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java deleted file mode 100644 index 61a34351..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java +++ /dev/null @@ -1,53 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import java.util.*; -import java.util.Map.Entry; - -import tools.refinery.store.map.VersionedMap; - -public class UncommittedDeltaMapStore implements UncommittedDeltaStore { - final VersionedMap source; - final Map uncommittedOldValues = new HashMap<>(); - - public UncommittedDeltaMapStore(VersionedMap source) { - this.source = source; - } - - @Override - public void processChange(K key, V oldValue, V newValue) { - if(!uncommittedOldValues.containsKey(key)) { - this.uncommittedOldValues.put(key,oldValue); - } - } - - @Override - public MapDelta[] extractDeltas() { - if (uncommittedOldValues.isEmpty()) { - return null; - } else { - @SuppressWarnings("unchecked") - MapDelta[] deltas = new MapDelta[uncommittedOldValues.size()]; - int i = 0; - for (Entry entry : uncommittedOldValues.entrySet()) { - final K key = entry.getKey(); - final V oldValue = entry.getValue(); - final V newValue = source.get(key); - deltas[i++] = new MapDelta<>(key, oldValue, newValue); - } - - return deltas; - } - } - - @Override - public MapDelta[] extractAndDeleteDeltas() { - MapDelta[] res = extractDeltas(); - this.uncommittedOldValues.clear(); - return res; - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java deleted file mode 100644 index 438b5561..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java +++ /dev/null @@ -1,29 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -public interface UncommittedDeltaStore { - void processChange(K key, V oldValue, V newValue); - - MapDelta[] extractDeltas(); - - MapDelta[] extractAndDeleteDeltas(); - - default void checkIntegrity() { - MapDelta[] extractedDeltas = extractDeltas(); - if(extractedDeltas != null) { - for(var uncommittedOldValue : extractedDeltas) { - if(uncommittedOldValue == null) { - throw new IllegalArgumentException("Null entry in deltas!"); - } - if(uncommittedOldValue.getKey() == null) { - throw new IllegalStateException("Null key in deltas!"); - } - } - } - } - -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java deleted file mode 100644 index ae47feda..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java +++ /dev/null @@ -1,219 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import java.util.*; - -import tools.refinery.store.map.*; - -public class VersionedMapDeltaImpl implements VersionedMap { - protected final VersionedMapStoreDeltaImpl store; - - final Map current; - - final UncommittedDeltaStore uncommittedStore; - MapTransaction previous; - - protected final V defaultValue; - - public VersionedMapDeltaImpl(VersionedMapStoreDeltaImpl store, boolean summarizeChanges, V defaultValue) { - this.store = store; - this.defaultValue = defaultValue; - - current = new HashMap<>(); - if (summarizeChanges) { - this.uncommittedStore = new UncommittedDeltaMapStore<>(this); - } else { - this.uncommittedStore = new UncommittedDeltaArrayStore<>(); - } - } - - @Override - public V getDefaultValue() { - return defaultValue; - } - - @Override - public long commit() { - MapDelta[] deltas = uncommittedStore.extractAndDeleteDeltas(); - long[] versionContainer = new long[1]; - this.previous = this.store.appendTransaction(deltas, previous, versionContainer); - return versionContainer[0]; - } - - @Override - public void restore(long state) { - // 1. restore uncommitted states - MapDelta[] uncommitted = this.uncommittedStore.extractAndDeleteDeltas(); - if (uncommitted != null) { - backward(uncommitted); - } - - // 2. get common ancestor - final MapTransaction parent; - List[]> forward = new ArrayList<>(); - if (this.previous == null) { - parent = this.store.getPath(state, forward); - this.forward(forward); - } else { - List[]> backward = new ArrayList<>(); - parent = this.store.getPath(this.previous.version(), state, backward, forward); - this.backward(backward); - this.forward(forward); - } - this.previous = parent; - } - - protected void forward(List[]> changes) { - for (int i = changes.size() - 1; i >= 0; i--) { - forward(changes.get(i)); - } - } - - protected void backward(List[]> changes) { - for (int i = 0; i < changes.size(); i++) { - backward(changes.get(i)); - } - } - - protected void forward(MapDelta[] changes) { - for (int i = 0; i < changes.length; i++) { - final MapDelta change = changes[i]; - K key = change.getKey(); - V newValue = change.getNewValue(); - - if(newValue == defaultValue) { - current.remove(key); - } else { - current.put(key,newValue); - } - } - } - - protected void backward(MapDelta[] changes) { - for (int i = changes.length - 1; i >= 0; i--) { - final MapDelta change = changes[i]; - K key = change.getKey(); - V oldValue = change.oldValue(); - - if(oldValue == defaultValue) { - current.remove(key); - } else { - current.put(key,oldValue); - } - } - } - - @Override - public V get(K key) { - return current.getOrDefault(key, defaultValue); - } - - @Override - public Cursor getAll() { - return new IteratorAsCursor<>(this, current); - } - - @Override - public V put(K key, V value) { - final V oldValue; - if (Objects.equals(value, defaultValue)) { - final V res = current.remove(key); - if (res == null) { - // no changes: default > default - oldValue = defaultValue; - } else { - oldValue = res; - } - } else { - final var mapValue = current.put(key, value); - if (mapValue == null) { - oldValue = defaultValue; - } else { - oldValue = mapValue; - } - } - if(!Objects.equals(oldValue,value)) { - uncommittedStore.processChange(key, oldValue, value); - } - return oldValue; - } - - @Override - public void putAll(Cursor cursor) { - if (cursor.getDependingMaps().contains(this)) { - List keys = new ArrayList<>(); - List values = new ArrayList<>(); - while (cursor.move()) { - keys.add(cursor.getKey()); - values.add(cursor.getValue()); - } - for (int i = 0; i < keys.size(); i++) { - this.put(keys.get(i), values.get(i)); - } - } else { - while (cursor.move()) { - this.put(cursor.getKey(), cursor.getValue()); - } - } - } - - @Override - public long getSize() { - return current.size(); - } - - @Override - public DiffCursor getDiffCursor(long state) { - MapDelta[] backward = this.uncommittedStore.extractDeltas(); - List[]> backwardTransactions = new ArrayList<>(); - List[]> forwardTransactions = new ArrayList<>(); - - if (backward != null) { - backwardTransactions.add(backward); - } - - if (this.previous != null) { - store.getPath(this.previous.version(), state, backwardTransactions, forwardTransactions); - } else { - store.getPath(state, forwardTransactions); - } - - return new DeltaDiffCursor<>(backwardTransactions, forwardTransactions); - } - - @Override - public int contentHashCode(ContentHashCode mode) { - return this.current.hashCode(); - } - - @Override - public boolean contentEquals(AnyVersionedMap other) { - if (other instanceof VersionedMapDeltaImpl versioned) { - if (versioned == this) { - return true; - } else { - return Objects.equals(this.defaultValue, versioned.defaultValue) && Objects.equals(this.current, versioned.current); - } - } else { - throw new UnsupportedOperationException("Comparing different map implementations is ineffective."); - } - } - - @Override - public void checkIntegrity() { - this.uncommittedStore.checkIntegrity(); - - for (var entry : this.current.entrySet()) { - var value = entry.getValue(); - if (value == this.defaultValue) { - throw new IllegalStateException("Default value stored in map!"); - } else if (value == null) { - throw new IllegalStateException("null value stored in map!"); - } - } - } -} 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 deleted file mode 100644 index c107f7e0..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java +++ /dev/null @@ -1,171 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.*; - -import java.util.Iterator; -import java.util.LinkedList; -import java.util.List; -import java.util.Objects; - -/** - * Not threadSafe in itself - * - * @param - * @param - * @author Oszkar Semerath - */ -public class VersionedMapImpl implements VersionedMap { - protected final VersionedMapStoreImpl store; - - protected final ContinousHashProvider hashProvider; - protected final V defaultValue; - protected Node root; - - private final OldValueBox oldValueBox = new OldValueBox<>(); - - public VersionedMapImpl( - VersionedMapStoreImpl store, - ContinousHashProvider hashProvider, - V defaultValue) { - this.store = store; - this.hashProvider = hashProvider; - this.defaultValue = defaultValue; - this.root = null; - } - - public VersionedMapImpl( - VersionedMapStoreImpl store, - ContinousHashProvider hashProvider, - V defaultValue, Node data) { - this.store = store; - this.hashProvider = hashProvider; - this.defaultValue = defaultValue; - this.root = data; - } - - @Override - public V getDefaultValue() { - return defaultValue; - } - - public ContinousHashProvider getHashProvider() { - return hashProvider; - } - - @Override - public V put(K key, V value) { - if (root != null) { - root = root.putValue(key, value, oldValueBox, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); - return oldValueBox.getOldValue(); - } else { - root = MutableNode.initialize(key, value, hashProvider, defaultValue); - return defaultValue; - } - } - - @Override - public void putAll(Cursor cursor) { - if (cursor.getDependingMaps().contains(this)) { - List keys = new LinkedList<>(); - List values = new LinkedList<>(); - while (cursor.move()) { - keys.add(cursor.getKey()); - values.add(cursor.getValue()); - } - Iterator keyIterator = keys.iterator(); - Iterator valueIterator = values.iterator(); - while (keyIterator.hasNext()) { - var key = keyIterator.next(); - var value = valueIterator.next(); - this.put(key,value); - } - } else { - while (cursor.move()) { - this.put(cursor.getKey(), cursor.getValue()); - } - } - } - - @Override - public V get(K key) { - if (root != null) { - return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); - } else { - return defaultValue; - } - } - - @Override - public long getSize() { - if (root == null) { - return 0; - } else { - return root.getSize(); - } - } - - @Override - public Cursor getAll() { - return new MapCursor<>(this.root, this); - } - - @Override - public DiffCursor getDiffCursor(long toVersion) { - InOrderMapCursor fromCursor = new InOrderMapCursor<>(this); - VersionedMapImpl toMap = (VersionedMapImpl) this.store.createMap(toVersion); - InOrderMapCursor toCursor = new InOrderMapCursor<>(toMap); - return new MapDiffCursor<>(this.defaultValue, fromCursor, toCursor); - } - - - @Override - public long commit() { - return this.store.commit(root, this); - } - - public void setRoot(Node root) { - this.root = root; - } - - @Override - public void restore(long state) { - root = this.store.revert(state); - } - - public String prettyPrint() { - if (this.root != null) { - StringBuilder s = new StringBuilder(); - this.root.prettyPrint(s, 0, -1); - return s.toString(); - } else { - return "empty tree"; - } - } - - @Override - public void checkIntegrity() { - if (this.root != null) { - this.root.checkIntegrity(hashProvider, defaultValue, 0); - } - } - - @Override - public int contentHashCode(ContentHashCode mode) { - // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode. - if(root == null) { - return 0; - } else { - return root.hashCode(); - } - } - - @Override - public boolean contentEquals(AnyVersionedMap other) { - return other instanceof VersionedMapImpl otherImpl && Objects.equals(root, otherImpl.root); - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java index cf117d95..47470236 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java @@ -5,9 +5,11 @@ */ package tools.refinery.store.map.internal; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.map.VersionedMapStoreFactory; import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; +import tools.refinery.store.map.internal.delta.DeltaBasedVersionedMapStoreFactory; +import tools.refinery.store.map.internal.state.StateBasedVersionedMapStoreFactory; public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapStoreFactoryBuilder { @@ -16,14 +18,14 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt private StoreStrategy strategy = null; private Boolean transformToImmutable = null; private SharingStrategy sharingStrategy = null; - private ContinousHashProvider continousHashProvider = null; + private ContinuousHashProvider continuousHashProvider = null; private DeltaTransactionStrategy deltaTransactionStrategy = null; private StoreStrategy checkStrategy() { StoreStrategy currentStrategy = strategy; currentStrategy = mergeStrategies(currentStrategy, transformToImmutable, StoreStrategy.STATE); currentStrategy = mergeStrategies(currentStrategy, sharingStrategy, StoreStrategy.STATE); - currentStrategy = mergeStrategies(currentStrategy, continousHashProvider, StoreStrategy.STATE); + currentStrategy = mergeStrategies(currentStrategy, continuousHashProvider, StoreStrategy.STATE); currentStrategy = mergeStrategies(currentStrategy, deltaTransactionStrategy, StoreStrategy.DELTA); return currentStrategy; } @@ -77,8 +79,8 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt } @Override - public VersionedMapStoreFactoryBuilder stateBasedHashProvider(ContinousHashProvider hashProvider) { - this.continousHashProvider = hashProvider; + public VersionedMapStoreFactoryBuilder stateBasedHashProvider(ContinuousHashProvider hashProvider) { + this.continuousHashProvider = hashProvider; checkStrategy(); return this; } @@ -110,13 +112,13 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt } return switch (strategyToUse) { case STATE -> { - if(continousHashProvider == null) { + if(continuousHashProvider == null) { throw new IllegalArgumentException("Continuous hash provider is missing!"); } yield new StateBasedVersionedMapStoreFactory<>(defaultValue, getOrDefault(transformToImmutable,true), getOrDefault(sharingStrategy, SharingStrategy.SHARED_NODE_CACHE_IN_GROUP), - continousHashProvider); + continuousHashProvider); } case DELTA -> new DeltaBasedVersionedMapStoreFactory<>(defaultValue, getOrDefault(deltaTransactionStrategy, DeltaTransactionStrategy.LIST)); @@ -130,7 +132,7 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt ", strategy=" + strategy + ", stateBasedImmutableWhenCommitting=" + transformToImmutable + ", stateBasedNodeSharingStrategy=" + sharingStrategy + - ", hashProvider=" + continousHashProvider + + ", hashProvider=" + continuousHashProvider + ", deltaStorageStrategy=" + deltaTransactionStrategy + '}'; } diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaBasedVersionedMapStoreFactory.java new file mode 100644 index 00000000..cedcdc0b --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaBasedVersionedMapStoreFactory.java @@ -0,0 +1,38 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +import tools.refinery.store.map.VersionedMapStore; +import tools.refinery.store.map.VersionedMapStoreFactory; +import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; + +import java.util.ArrayList; +import java.util.List; + +public class DeltaBasedVersionedMapStoreFactory implements VersionedMapStoreFactory { + private final V defaultValue; + private final boolean summarizeChanges; + + public DeltaBasedVersionedMapStoreFactory(V defaultValue, + VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy deltaTransactionStrategy) { + this.defaultValue = defaultValue; + this.summarizeChanges = deltaTransactionStrategy == VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.SET; + } + + @Override + public VersionedMapStore createOne() { + return new VersionedMapStoreDeltaImpl<>(summarizeChanges, defaultValue); + } + + @Override + public List> createGroup(int amount) { + List> result = new ArrayList<>(amount); + for(int i=0; i(summarizeChanges,defaultValue)); + } + return result; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaDiffCursor.java new file mode 100644 index 00000000..ce10b246 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaDiffCursor.java @@ -0,0 +1,147 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +import tools.refinery.store.map.AnyVersionedMap; +import tools.refinery.store.map.DiffCursor; + +import java.util.Collections; +import java.util.List; +import java.util.Set; + +public class DeltaDiffCursor implements DiffCursor { + final List[]> backwardTransactions; + final List[]> forwardTransactions; + + boolean started; + /** + * Denotes the direction of traversal. False means backwards, true means + * forward. + */ + boolean direction; + int listIndex; + int arrayIndex; + + public DeltaDiffCursor(List[]> backwardTransactions, List[]> forwardTransactions) { + this.backwardTransactions = backwardTransactions; + this.forwardTransactions = forwardTransactions; + + if (!backwardTransactions.isEmpty()) { + direction = false; + listIndex = 0; + arrayIndex = backwardTransactions.get(listIndex).length - 1; + } else if (!forwardTransactions.isEmpty()) { + direction = true; + listIndex = forwardTransactions.size() - 1; + arrayIndex = 0; + } else { + direction = true; + listIndex = -1; + } + started = false; + } + + protected MapDelta getCurrentDelta() { + final List[]> list; + if (!direction) { + list = this.backwardTransactions; + } else { + list = this.forwardTransactions; + } + return list.get(listIndex)[arrayIndex]; + } + + @Override + public K getKey() { + return getCurrentDelta().getKey(); + } + + @Override + public V getValue() { + return getToValue(); + } + + @Override + public boolean isTerminated() { + return this.direction && listIndex == -1; + } + + + @Override + public boolean move() { + if(!started) { + started = true; + return !isTerminated(); + } else if (isTerminated()) { + return false; + } else { + if (this.direction) { + if (arrayIndex+1 < forwardTransactions.get(listIndex).length) { + arrayIndex++; + return true; + } else { + if (listIndex-1 >= 0) { + listIndex--; + arrayIndex = 0; + return true; + } else { + listIndex = -1; + return false; + } + } + } else { + if (arrayIndex > 0) { + arrayIndex--; + return true; + } else { + if (listIndex+1 < backwardTransactions.size()) { + listIndex++; + this.arrayIndex = backwardTransactions.get(listIndex).length - 1; + return true; + } else { + this.direction = true; + if (!this.forwardTransactions.isEmpty()) { + listIndex = forwardTransactions.size() - 1; + arrayIndex = 0; + return true; + } else { + listIndex = -1; + return false; + } + } + } + } + } + } + + @Override + public boolean isDirty() { + return false; + } + + @Override + public Set getDependingMaps() { + return Collections.emptySet(); + } + + @Override + public V getFromValue() { + if(this.direction) { + return getCurrentDelta().getOldValue(); + } else { + return getCurrentDelta().getNewValue(); + } + } + + @Override + public V getToValue() { + if(this.direction) { + return getCurrentDelta().getNewValue(); + } else { + return getCurrentDelta().getOldValue(); + } + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapDelta.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapDelta.java new file mode 100644 index 00000000..0c0cc906 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapDelta.java @@ -0,0 +1,20 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +public record MapDelta(K key, V oldValue, V newValue) { + public K getKey() { + return key; + } + + public V getOldValue() { + return oldValue; + } + + public V getNewValue() { + return newValue; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java new file mode 100644 index 00000000..7f9ccd7f --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java @@ -0,0 +1,39 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +import java.util.Arrays; +import java.util.Objects; + +public record MapTransaction(MapDelta[] deltas, long version, MapTransaction parent) { + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + Arrays.hashCode(deltas); + result = prime * result + Objects.hash(parent, version); + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (getClass() != obj.getClass()) + return false; + @SuppressWarnings("unchecked") + MapTransaction other = (MapTransaction) obj; + return Arrays.equals(deltas, other.deltas) && Objects.equals(parent, other.parent) && version == other.version; + } + + @Override + public String toString() { + return "MapTransaction " + version + " " + Arrays.toString(deltas); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaArrayStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaArrayStore.java new file mode 100644 index 00000000..1f6a9000 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaArrayStore.java @@ -0,0 +1,36 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +import java.util.ArrayList; +import java.util.List; + +public class UncommittedDeltaArrayStore implements UncommittedDeltaStore { + final List> uncommittedOldValues = new ArrayList<>(); + + @Override + public void processChange(K key, V oldValue, V newValue) { + uncommittedOldValues.add(new MapDelta<>(key, oldValue, newValue)); + } + + @Override + public MapDelta[] extractDeltas() { + if (uncommittedOldValues.isEmpty()) { + return null; + } else { + @SuppressWarnings("unchecked") + MapDelta[] result = uncommittedOldValues.toArray(new MapDelta[0]); + return result; + } + } + + @Override + public MapDelta[] extractAndDeleteDeltas() { + MapDelta[] res = extractDeltas(); + this.uncommittedOldValues.clear(); + return res; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaMapStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaMapStore.java new file mode 100644 index 00000000..644884a6 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaMapStore.java @@ -0,0 +1,53 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +import java.util.*; +import java.util.Map.Entry; + +import tools.refinery.store.map.VersionedMap; + +public class UncommittedDeltaMapStore implements UncommittedDeltaStore { + final VersionedMap source; + final Map uncommittedOldValues = new HashMap<>(); + + public UncommittedDeltaMapStore(VersionedMap source) { + this.source = source; + } + + @Override + public void processChange(K key, V oldValue, V newValue) { + if(!uncommittedOldValues.containsKey(key)) { + this.uncommittedOldValues.put(key,oldValue); + } + } + + @Override + public MapDelta[] extractDeltas() { + if (uncommittedOldValues.isEmpty()) { + return null; + } else { + @SuppressWarnings("unchecked") + MapDelta[] deltas = new MapDelta[uncommittedOldValues.size()]; + int i = 0; + for (Entry entry : uncommittedOldValues.entrySet()) { + final K key = entry.getKey(); + final V oldValue = entry.getValue(); + final V newValue = source.get(key); + deltas[i++] = new MapDelta<>(key, oldValue, newValue); + } + + return deltas; + } + } + + @Override + public MapDelta[] extractAndDeleteDeltas() { + MapDelta[] res = extractDeltas(); + this.uncommittedOldValues.clear(); + return res; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaStore.java new file mode 100644 index 00000000..ecd33c5f --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaStore.java @@ -0,0 +1,29 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +public interface UncommittedDeltaStore { + void processChange(K key, V oldValue, V newValue); + + MapDelta[] extractDeltas(); + + MapDelta[] extractAndDeleteDeltas(); + + default void checkIntegrity() { + MapDelta[] extractedDeltas = extractDeltas(); + if(extractedDeltas != null) { + for(var uncommittedOldValue : extractedDeltas) { + if(uncommittedOldValue == null) { + throw new IllegalArgumentException("Null entry in deltas!"); + } + if(uncommittedOldValue.getKey() == null) { + throw new IllegalStateException("Null key in deltas!"); + } + } + } + } + +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java new file mode 100644 index 00000000..5bb864ac --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java @@ -0,0 +1,220 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +import java.util.*; + +import tools.refinery.store.map.*; +import tools.refinery.store.map.IteratorAsCursor; + +public class VersionedMapDeltaImpl implements VersionedMap { + protected final VersionedMapStoreDeltaImpl store; + + final Map current; + + final UncommittedDeltaStore uncommittedStore; + MapTransaction previous; + + protected final V defaultValue; + + public VersionedMapDeltaImpl(VersionedMapStoreDeltaImpl store, boolean summarizeChanges, V defaultValue) { + this.store = store; + this.defaultValue = defaultValue; + + current = new HashMap<>(); + if (summarizeChanges) { + this.uncommittedStore = new UncommittedDeltaMapStore<>(this); + } else { + this.uncommittedStore = new UncommittedDeltaArrayStore<>(); + } + } + + @Override + public V getDefaultValue() { + return defaultValue; + } + + @Override + public long commit() { + MapDelta[] deltas = uncommittedStore.extractAndDeleteDeltas(); + long[] versionContainer = new long[1]; + this.previous = this.store.appendTransaction(deltas, previous, versionContainer); + return versionContainer[0]; + } + + @Override + public void restore(long state) { + // 1. restore uncommitted states + MapDelta[] uncommitted = this.uncommittedStore.extractAndDeleteDeltas(); + if (uncommitted != null) { + backward(uncommitted); + } + + // 2. get common ancestor + final MapTransaction parent; + List[]> forward = new ArrayList<>(); + if (this.previous == null) { + parent = this.store.getPath(state, forward); + this.forward(forward); + } else { + List[]> backward = new ArrayList<>(); + parent = this.store.getPath(this.previous.version(), state, backward, forward); + this.backward(backward); + this.forward(forward); + } + this.previous = parent; + } + + protected void forward(List[]> changes) { + for (int i = changes.size() - 1; i >= 0; i--) { + forward(changes.get(i)); + } + } + + protected void backward(List[]> changes) { + for (int i = 0; i < changes.size(); i++) { + backward(changes.get(i)); + } + } + + protected void forward(MapDelta[] changes) { + for (int i = 0; i < changes.length; i++) { + final MapDelta change = changes[i]; + K key = change.getKey(); + V newValue = change.getNewValue(); + + if(newValue == defaultValue) { + current.remove(key); + } else { + current.put(key,newValue); + } + } + } + + protected void backward(MapDelta[] changes) { + for (int i = changes.length - 1; i >= 0; i--) { + final MapDelta change = changes[i]; + K key = change.getKey(); + V oldValue = change.oldValue(); + + if(oldValue == defaultValue) { + current.remove(key); + } else { + current.put(key,oldValue); + } + } + } + + @Override + public V get(K key) { + return current.getOrDefault(key, defaultValue); + } + + @Override + public Cursor getAll() { + return new IteratorAsCursor<>(this, current); + } + + @Override + public V put(K key, V value) { + final V oldValue; + if (Objects.equals(value, defaultValue)) { + final V res = current.remove(key); + if (res == null) { + // no changes: default > default + oldValue = defaultValue; + } else { + oldValue = res; + } + } else { + final var mapValue = current.put(key, value); + if (mapValue == null) { + oldValue = defaultValue; + } else { + oldValue = mapValue; + } + } + if(!Objects.equals(oldValue,value)) { + uncommittedStore.processChange(key, oldValue, value); + } + return oldValue; + } + + @Override + public void putAll(Cursor cursor) { + if (cursor.getDependingMaps().contains(this)) { + List keys = new ArrayList<>(); + List values = new ArrayList<>(); + while (cursor.move()) { + keys.add(cursor.getKey()); + values.add(cursor.getValue()); + } + for (int i = 0; i < keys.size(); i++) { + this.put(keys.get(i), values.get(i)); + } + } else { + while (cursor.move()) { + this.put(cursor.getKey(), cursor.getValue()); + } + } + } + + @Override + public long getSize() { + return current.size(); + } + + @Override + public DiffCursor getDiffCursor(long state) { + MapDelta[] backward = this.uncommittedStore.extractDeltas(); + List[]> backwardTransactions = new ArrayList<>(); + List[]> forwardTransactions = new ArrayList<>(); + + if (backward != null) { + backwardTransactions.add(backward); + } + + if (this.previous != null) { + store.getPath(this.previous.version(), state, backwardTransactions, forwardTransactions); + } else { + store.getPath(state, forwardTransactions); + } + + return new DeltaDiffCursor<>(backwardTransactions, forwardTransactions); + } + + @Override + public int contentHashCode(ContentHashCode mode) { + return this.current.hashCode(); + } + + @Override + public boolean contentEquals(AnyVersionedMap other) { + if (other instanceof VersionedMapDeltaImpl versioned) { + if (versioned == this) { + return true; + } else { + return Objects.equals(this.defaultValue, versioned.defaultValue) && Objects.equals(this.current, versioned.current); + } + } else { + throw new UnsupportedOperationException("Comparing different map implementations is ineffective."); + } + } + + @Override + public void checkIntegrity() { + this.uncommittedStore.checkIntegrity(); + + for (var entry : this.current.entrySet()) { + var value = entry.getValue(); + if (value == this.defaultValue) { + throw new IllegalStateException("Default value stored in map!"); + } else if (value == null) { + throw new IllegalStateException("null value stored in map!"); + } + } + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java new file mode 100644 index 00000000..7f56ea77 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java @@ -0,0 +1,101 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +import tools.refinery.store.map.DiffCursor; +import tools.refinery.store.map.VersionedMap; +import tools.refinery.store.map.VersionedMapStore; + +import java.util.*; + +public class VersionedMapStoreDeltaImpl implements VersionedMapStore { + // Configuration + protected final boolean summarizeChanges; + + // Static data + protected final V defaultValue; + + // Dynamic data + protected final Map> states = new HashMap<>(); + protected long nextID = 0; + + public VersionedMapStoreDeltaImpl(boolean summarizeChanges, V defaultValue) { + this.summarizeChanges = summarizeChanges; + this.defaultValue = defaultValue; + } + + @Override + public VersionedMap createMap() { + return new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue); + } + + @Override + public VersionedMap createMap(long state) { + VersionedMapDeltaImpl result = new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue); + result.restore(state); + return result; + } + + public synchronized MapTransaction appendTransaction(MapDelta[] deltas, MapTransaction previous, long[] versionContainer) { + long version = nextID++; + versionContainer[0] = version; + if (deltas == null) { + states.put(version, previous); + return previous; + } else { + MapTransaction transaction = new MapTransaction<>(deltas, version, previous); + states.put(version, transaction); + return transaction; + } + } + + private synchronized MapTransaction getState(long state) { + return states.get(state); + } + + public MapTransaction getPath(long to, List[]> forwardTransactions) { + final MapTransaction target = getState(to); + MapTransaction toTransaction = target; + while (toTransaction != null) { + forwardTransactions.add(toTransaction.deltas()); + toTransaction = toTransaction.parent(); + } + return target; + } + + public MapTransaction getPath(long from, long to, + List[]> backwardTransactions, + List[]> forwardTransactions) { + MapTransaction fromTransaction = getState(from); + final MapTransaction target = getState(to); + MapTransaction toTransaction = target; + + while (fromTransaction != toTransaction) { + if (fromTransaction == null || (toTransaction != null && fromTransaction.version() < toTransaction.version())) { + forwardTransactions.add(toTransaction.deltas()); + toTransaction = toTransaction.parent(); + } else { + backwardTransactions.add(fromTransaction.deltas()); + fromTransaction = fromTransaction.parent(); + } + } + return target; + } + + + @Override + public synchronized Set getStates() { + return new HashSet<>(states.keySet()); + } + + @Override + public DiffCursor getDiffCursor(long fromState, long toState) { + List[]> backwardTransactions = new ArrayList<>(); + List[]> forwardTransactions = new ArrayList<>(); + getPath(fromState, toState, backwardTransactions, forwardTransactions); + return new DeltaDiffCursor<>(backwardTransactions, forwardTransactions); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java new file mode 100644 index 00000000..722f9ed7 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java @@ -0,0 +1,413 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import java.util.Arrays; +import java.util.Map; + +import tools.refinery.store.map.ContinuousHashProvider; + +public class ImmutableNode extends Node { + /** + * Bitmap defining the stored key and values. + */ + final int dataMap; + /** + * Bitmap defining the positions of further nodes. + */ + final int nodeMap; + /** + * Stores Keys, Values, and sub-nodes. Structure: (K,V)*,NODE; NODES are stored + * backwards. + */ + final Object[] content; + + /** + * Hash code derived from immutable hash code + */ + final int precalculatedHash; + + private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) { + super(); + this.dataMap = dataMap; + this.nodeMap = nodeMap; + this.content = content; + this.precalculatedHash = precalculatedHash; + } + + /** + * Constructor that copies a mutable node to an immutable. + * + * @param node A mutable node. + * @param cache A cache of existing immutable nodes. It can be used to search + * and place reference immutable nodes. It can be null, if no cache + * available. + * @return an immutable version of the input node. + */ + static ImmutableNode constructImmutable(MutableNode node, Map, ImmutableNode> cache) { + // 1. try to return from cache + if (cache != null) { + ImmutableNode cachedResult = cache.get(node); + if (cachedResult != null) { + // 1.1 Already cached, return from cache. + return cachedResult; + } + } + + // 2. otherwise construct a new ImmutableNode + int size = 0; + for (int i = 0; i < node.content.length; i++) { + if (node.content[i] != null) { + size++; + } + } + + int datas = 0; + int nodes = 0; + int resultDataMap = 0; + int resultNodeMap = 0; + final Object[] resultContent = new Object[size]; + int bitPosition = 1; + for (int i = 0; i < FACTOR; i++) { + Object key = node.content[i * 2]; + if (key != null) { + 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; + nodes++; + } + } + bitPosition <<= 1; + } + final int resultHash = node.hashCode(); + var newImmutable = new ImmutableNode(resultDataMap, resultNodeMap, resultContent, resultHash); + + // 3. save new immutable. + if (cache != null) { + cache.put(newImmutable, newImmutable); + } + return newImmutable; + } + + private int index(int bitmap, int bitpos) { + return Integer.bitCount(bitmap & (bitpos - 1)); + } + + @Override + public V getValue(K key, ContinuousHashProvider hashProvider, V defaultValue, int hash, int depth) { + int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); + int bitposition = 1 << selectedHashFragment; + // If the key is stored as a data + if ((dataMap & bitposition) != 0) { + int keyIndex = 2 * index(dataMap, bitposition); + @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; + if (keyCandidate.equals(key)) { + @SuppressWarnings("unchecked") V value = (V) content[keyIndex + 1]; + return value; + } else { + return defaultValue; + } + } + // the key is stored as a node + 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); + return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); + } + // the key is not stored at all + else { + return defaultValue; + } + } + + @Override + public Node putValue(K key, V value, OldValueBox oldValue, ContinuousHashProvider 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); + @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; + if (keyCandidate.equals(key)) { + if (value == defaultValue) { + // delete + MutableNode mutable = this.toMutable(); + return mutable.removeEntry(selectedHashFragment, oldValue); + } else if (value == content[keyIndex + 1]) { + // don't change + oldValue.setOldValue(value); + return this; + } else { + // update existing value + MutableNode mutable = this.toMutable(); + return mutable.updateValue(value, oldValue, selectedHashFragment); + } + } else { + if (value == defaultValue) { + // don't change + oldValue.setOldValue(defaultValue); + return this; + } else { + // add new key + value + MutableNode mutable = this.toMutable(); + return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); + } + } + } 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); + var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); + + if (subNode == newsubNode) { + // nothing changed + return this; + } else { + MutableNode mutable = toMutable(); + return mutable.updateWithSubNode(selectedHashFragment, newsubNode, + (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); + } + } else { + // add new key + value + MutableNode mutable = this.toMutable(); + return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); + } + } + + @Override + public long getSize() { + int result = Integer.bitCount(this.dataMap); + for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { + @SuppressWarnings("unchecked") var subnode = (ImmutableNode) this.content[this.content.length - 1 - subnodeIndex]; + result += subnode.getSize(); + } + return result; + } + + @Override + protected MutableNode toMutable() { + return new MutableNode<>(this); + } + + @Override + public ImmutableNode toImmutable(Map, ImmutableNode> cache) { + return this; + } + + @Override + protected MutableNode isMutable() { + return null; + } + + @SuppressWarnings("unchecked") + @Override + boolean moveToNext(MapCursor cursor) { + // 1. try to move to data + int datas = Integer.bitCount(this.dataMap); + if (cursor.dataIndex != MapCursor.INDEX_FINISH) { + int newDataIndex = cursor.dataIndex + 1; + if (newDataIndex < datas) { + cursor.dataIndex = newDataIndex; + cursor.key = (K) this.content[newDataIndex * 2]; + cursor.value = (V) this.content[newDataIndex * 2 + 1]; + return true; + } else { + cursor.dataIndex = MapCursor.INDEX_FINISH; + } + } + + // 2. look inside the subnodes + int nodes = Integer.bitCount(this.nodeMap); + if(cursor.nodeIndexStack.peek()==null) { + throw new IllegalStateException("Cursor moved to the next state when the state is empty."); + } + int newNodeIndex = cursor.nodeIndexStack.peek() + 1; + if (newNodeIndex < nodes) { + // 2.1 found next subnode, move down to the subnode + Node subnode = (Node) this.content[this.content.length - 1 - newNodeIndex]; + cursor.dataIndex = MapCursor.INDEX_START; + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(newNodeIndex); + cursor.nodeIndexStack.push(MapCursor.INDEX_START); + cursor.nodeStack.push(subnode); + return subnode.moveToNext(cursor); + } else { + // 3. no subnode found, move up + cursor.nodeStack.pop(); + cursor.nodeIndexStack.pop(); + if (!cursor.nodeStack.isEmpty()) { + Node supernode = cursor.nodeStack.peek(); + return supernode.moveToNext(cursor); + } else { + cursor.key = null; + cursor.value = null; + return false; + } + } + } + + @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))); + if (code >= 0) { + builder.append(code); + builder.append(":"); + } + builder.append("Immutable("); + boolean hadContent = false; + int dataMask = 1; + for (int i = 0; i < FACTOR; i++) { + if ((dataMask & dataMap) != 0) { + if (hadContent) { + builder.append(","); + } + builder.append(i); + builder.append(":["); + builder.append(content[2 * index(dataMap, dataMask)].toString()); + builder.append("]->["); + builder.append(content[2 * index(dataMap, dataMask) + 1].toString()); + builder.append("]"); + hadContent = true; + } + dataMask <<= 1; + } + builder.append(")"); + int nodeMask = 1; + for (int i = 0; i < FACTOR; i++) { + if ((nodeMask & nodeMap) != 0) { + @SuppressWarnings("unchecked") Node subNode = (Node) content[content.length - 1 - index(nodeMap, nodeMask)]; + builder.append("\n"); + subNode.prettyPrint(builder, incrementDepth(depth), i); + } + nodeMask <<= 1; + } + } + + @Override + public void checkIntegrity(ContinuousHashProvider hashProvider, V defaultValue, int depth) { + if (depth > 0) { + boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0; + if (orphaned) { + throw new IllegalStateException("Orphaned node! " + dataMap + ": " + content[0]); + } + } + // check the place of data + + // check subnodes + for (int i = 0; i < Integer.bitCount(nodeMap); i++) { + @SuppressWarnings("unchecked") var subnode = (Node) this.content[this.content.length - 1 - i]; + if (!(subnode instanceof ImmutableNode)) { + throw new IllegalStateException("Immutable node contains mutable subnodes!"); + } else { + subnode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); + } + } + } + + @Override + public int hashCode() { + return this.precalculatedHash; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (obj instanceof ImmutableNode other) { + return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap && Arrays.deepEquals(content, other.content); + } else if (obj instanceof MutableNode mutableObj) { + return ImmutableNode.compareImmutableMutable(this, mutableObj); + } else { + return false; + } + } + + public static boolean compareImmutableMutable(ImmutableNode immutable, MutableNode mutable) { + int datas = 0; + int nodes = 0; + final int immutableLength = immutable.content.length; + for (int i = 0; i < FACTOR; i++) { + Object key = mutable.content[i * 2]; + // For each key candidate + if (key != null) { + // Check whether a new Key-Value pair can fit into the immutable container + if (datas * 2 + nodes + 2 <= immutableLength) { + if (!immutable.content[datas * 2].equals(key) || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) { + return false; + } + } else return false; + datas++; + } else { + 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)) { + return false; + } + nodes++; + } else { + return false; + } + } + } + } + + return datas * 2 + nodes == immutable.content.length; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/InOrderMapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/InOrderMapCursor.java new file mode 100644 index 00000000..7cc91004 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/InOrderMapCursor.java @@ -0,0 +1,146 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +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(VersionedMapStateImpl 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/state/MapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapCursor.java new file mode 100644 index 00000000..0db50d04 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapCursor.java @@ -0,0 +1,95 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +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.ArrayDeque; +import java.util.ConcurrentModificationException; +import java.util.Set; + +public class MapCursor implements Cursor { + // Constants + static final int INDEX_START = -1; + static final int INDEX_FINISH = -2; + + // Tree stack + ArrayDeque> nodeStack; + ArrayDeque nodeIndexStack; + int dataIndex; + + // Values + K key; + V value; + + // Hash code for checking concurrent modifications + final VersionedMap map; + final int creationHash; + + public MapCursor(Node root, VersionedMap map) { + // Initializing tree stack + super(); + this.nodeStack = new ArrayDeque<>(); + this.nodeIndexStack = new ArrayDeque<>(); + if (root != null) { + this.nodeStack.add(root); + this.nodeIndexStack.push(INDEX_START); + } + + this.dataIndex = 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.moveToNext(this); + if (this.nodeIndexStack.size() != this.nodeStack.size()) { + throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); + } + return result; + } + return false; + } + + @Override + public boolean isDirty() { + return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; + } + + @Override + public Set getDependingMaps() { + return Set.of(this.map); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapDiffCursor.java new file mode 100644 index 00000000..083bf8cf --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapDiffCursor.java @@ -0,0 +1,264 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.AnyVersionedMap; +import tools.refinery.store.map.Cursor; +import tools.refinery.store.map.DiffCursor; + +import java.util.Objects; +import java.util.Set; +import java.util.stream.Collectors; +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 InOrderMapCursor cursor1; + private final InOrderMapCursor cursor2; + + // State + State state = State.INIT; + + // Values + private K key; + private V fromValue; + private V toValue; + + + public MapDiffCursor(V defaultValue, InOrderMapCursor cursor1, InOrderMapCursor cursor2) { + super(); + this.defaultValue = defaultValue; + this.cursor1 = cursor1; + this.cursor2 = cursor2; + } + + @Override + public K getKey() { + return key; + } + + @Override + public V getFromValue() { + return fromValue; + } + + @Override + public V getToValue() { + return toValue; + } + + @Override + public V getValue() { + return getToValue(); + } + + public boolean isTerminated() { + return this.state == State.TERMINATED_TERMINATED; + } + + @Override + public boolean isDirty() { + return this.cursor1.isDirty() || this.cursor2.isDirty(); + } + + @Override + public Set getDependingMaps() { + return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).map(AnyVersionedMap.class::cast).collect(Collectors.toUnmodifiableSet()); + } + + private boolean isInStableState() { + return this.state != State.MOVING_MOVING_SAME_KEY_SAME_VALUE + && this.state != State.MOVING_MOVING_SAME_NODE && this.state != State.INIT; + } + + 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; + } + }; + } + + public boolean move() { + do { + this.state = moveOne(this.state); + } while (!isInStableState()); + return updateAndReturnWithResult(); + } + + 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!"); + }; + } + + 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 { + return State.TERMINATED_TERMINATED; + } + } + + private State recalculateStateBasedOnCursorRelation() { + final int relation = InOrderMapCursor.comparePosition(cursor1, cursor2); + + if (relation > 0) { + return State.MOVING_MOVING_BEHIND1; + } else if (relation < 0) { + return State.MOVING_MOVING_BEHIND2; + } + + 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 { + 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; + } + + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MutableNode.java new file mode 100644 index 00000000..408ed62c --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MutableNode.java @@ -0,0 +1,499 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.ContinuousHashProvider; + +import java.util.Arrays; +import java.util.Map; + +public class MutableNode extends Node { + int cachedHash; + protected boolean cachedHashValid; + protected Object[] content; + + protected MutableNode() { + this.content = new Object[2 * FACTOR]; + invalidateHash(); + } + + public static MutableNode initialize(K key, V value, ContinuousHashProvider hashProvider, V defaultValue) { + if (value == defaultValue) { + return null; + } else { + int hash = hashProvider.getHash(key, 0); + int fragment = hashFragment(hash, 0); + MutableNode res = new MutableNode<>(); + res.content[2 * fragment] = key; + res.content[2 * fragment + 1] = value; + res.invalidateHash(); + return res; + } + } + + /** + * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} + * + * @param node to be transformed + */ + protected MutableNode(ImmutableNode node) { + this.content = new Object[2 * FACTOR]; + int dataUsed = 0; + int nodeUsed = 0; + for (int i = 0; i < FACTOR; i++) { + 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) { + content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; + nodeUsed++; + } + } + this.cachedHashValid = false; + } + + @Override + public V getValue(K key, ContinuousHashProvider hashProvider, V defaultValue, int hash, int depth) { + int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); + @SuppressWarnings("unchecked") K keyCandidate = (K) this.content[2 * selectedHashFragment]; + if (keyCandidate != null) { + if (keyCandidate.equals(key)) { + @SuppressWarnings("unchecked") V value = (V) this.content[2 * selectedHashFragment + 1]; + return value; + } else { + return defaultValue; + } + } else { + @SuppressWarnings("unchecked") var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; + if (nodeCandidate != null) { + int newDepth = incrementDepth(depth); + int newHash = newHash(hashProvider, key, hash, newDepth); + return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); + } else { + return defaultValue; + } + } + } + + @Override + public Node putValue(K key, V value, OldValueBox oldValueBox, ContinuousHashProvider hashProvider, V defaultValue, int hash, int depth) { + int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); + @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment]; + if (keyCandidate != null) { + // If it has key + if (keyCandidate.equals(key)) { + // The key is equals to an existing key -> update entry + if (value == defaultValue) { + return removeEntry(selectedHashFragment, oldValueBox); + } else { + return updateValue(value, oldValueBox, selectedHashFragment); + } + } else { + // The key is not equivalent to an existing key on the same hash bin + // -> split entry if it is necessary + if (value == defaultValue) { + // Value is default -> do not need to add new node + oldValueBox.setOldValue(defaultValue); + return this; + } else { + // Value is not default -> Split entry data to a new node + oldValueBox.setOldValue(defaultValue); + 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 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 { + return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue); + } + } + } + + private Node addEntry(K key, V value, OldValueBox oldValueBox, int selectedHashFragment, V defaultValue) { + content[2 * selectedHashFragment] = key; + oldValueBox.setOldValue(defaultValue); + content[2 * selectedHashFragment + 1] = value; + invalidateHash(); + return this; + } + + /** + * Updates an entry in a selected hash-fragment to a non-default value. + * + * @param value new value + * @param selectedHashFragment position of the value + * @return updated node + */ + @SuppressWarnings("unchecked") + Node updateValue(V value, OldValueBox oldValue, int selectedHashFragment) { + oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); + content[2 * selectedHashFragment + 1] = value; + invalidateHash(); + return this; + } + + /** + * Updates an entry in a selected hash-fragment with a subtree. + * + * @param selectedHashFragment position of the value + * @param newNode the subtree + * @return updated node + */ + Node updateWithSubNode(int selectedHashFragment, Node newNode, boolean deletionHappened) { + if (deletionHappened) { + if (newNode == null) { + // Check whether this node become empty + content[2 * selectedHashFragment + 1] = null; // i.e. the new node + if (hasContent()) { + invalidateHash(); + return this; + } else { + return null; + } + } else { + // check whether newNode is orphan + MutableNode immutableNewNode = newNode.isMutable(); + if (immutableNewNode != null) { + int orphaned = immutableNewNode.isOrphaned(); + if (orphaned >= 0) { + // 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(); + return this; + } + } + } + } + // normal behaviour + content[2 * selectedHashFragment + 1] = newNode; + invalidateHash(); + return this; + } + + private boolean hasContent() { + for (Object element : this.content) { + if (element != null) return true; + } + return false; + } + + @Override + protected MutableNode isMutable() { + return this; + } + + protected int isOrphaned() { + int dataFound = -2; + for (int i = 0; i < FACTOR; i++) { + if (content[i * 2] != null) { + if (dataFound >= 0) { + return -1; + } else { + dataFound = i; + } + } else if (content[i * 2 + 1] != null) { + return -3; + } + } + return dataFound; + } + + @SuppressWarnings("unchecked") + private Node moveDownAndSplit(ContinuousHashProvider hashProvider, K newKey, V newValue, K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { + V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1]; + + MutableNode newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, incrementDepth(depth)); + + content[2 * selectedHashFragmentOfCurrentDepth] = null; + content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; + invalidateHash(); + return this; + } + + // Pass everything as parameters for performance. + @SuppressWarnings("squid:S107") + private MutableNode newNodeWithTwoEntries(ContinuousHashProvider 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) { + subNode.content[newFragment1 * 2] = key1; + subNode.content[newFragment1 * 2 + 1] = value1; + + subNode.content[newFragment2 * 2] = key2; + subNode.content[newFragment2 * 2 + 1] = value2; + } else { + MutableNode subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newDepth)); + subNode.content[newFragment1 * 2 + 1] = subSubNode; + } + subNode.invalidateHash(); + return subNode; + } + + @SuppressWarnings("unchecked") + Node removeEntry(int selectedHashFragment, OldValueBox oldValue) { + content[2 * selectedHashFragment] = null; + oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); + content[2 * selectedHashFragment + 1] = null; + if (hasContent()) { + invalidateHash(); + return this; + } else { + return null; + } + } + + @SuppressWarnings("unchecked") + @Override + public long getSize() { + int size = 0; + for (int i = 0; i < FACTOR; i++) { + if (content[i * 2] != null) { + size++; + } else { + Node nodeCandidate = (Node) content[i * 2 + 1]; + if (nodeCandidate != null) { + size += nodeCandidate.getSize(); + } + } + } + return size; + } + + @Override + protected MutableNode toMutable() { + return this; + } + + @Override + public ImmutableNode toImmutable(Map, ImmutableNode> cache) { + return ImmutableNode.constructImmutable(this, cache); + } + + @SuppressWarnings("unchecked") + @Override + boolean moveToNext(MapCursor cursor) { + // 1. try to move to data + if (cursor.dataIndex != MapCursor.INDEX_FINISH) { + for (int index = cursor.dataIndex + 1; index < FACTOR; index++) { + if (this.content[index * 2] != null) { + // 1.1 found next data + cursor.dataIndex = index; + cursor.key = (K) this.content[index * 2]; + cursor.value = (V) this.content[index * 2 + 1]; + return true; + } + } + cursor.dataIndex = MapCursor.INDEX_FINISH; + } + + // 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 sub-node, move down to the sub-node + Node subnode = (Node) this.content[index * 2 + 1]; + + cursor.dataIndex = MapCursor.INDEX_START; + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(index); + cursor.nodeIndexStack.push(MapCursor.INDEX_START); + cursor.nodeStack.push(subnode); + + return subnode.moveToNext(cursor); + } + } + // 3. no sub-node found, move up + cursor.nodeStack.pop(); + cursor.nodeIndexStack.pop(); + if (!cursor.nodeStack.isEmpty()) { + Node supernode = cursor.nodeStack.peek(); + return supernode.moveToNext(cursor); + } else { + cursor.key = null; + cursor.value = null; + return false; + } + } + + @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))); + if (code >= 0) { + builder.append(code); + builder.append(":"); + } + builder.append("Mutable("); + // print content + boolean hadContent = false; + for (int i = 0; i < FACTOR; i++) { + if (content[2 * i] != null) { + if (hadContent) { + builder.append(","); + } + builder.append(i); + builder.append(":["); + builder.append(content[2 * i].toString()); + builder.append("]->["); + builder.append(content[2 * i + 1].toString()); + builder.append("]"); + hadContent = true; + } + } + builder.append(")"); + // 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]; + builder.append("\n"); + subNode.prettyPrint(builder, incrementDepth(depth), i); + } + } + } + + @Override + public void checkIntegrity(ContinuousHashProvider hashProvider, V defaultValue, int depth) { + // check for orphan nodes + if (depth > 0) { + int orphaned = isOrphaned(); + if (orphaned >= 0) { + throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]); + } + } + // check the place of data + for (int i = 0; i < FACTOR; i++) { + if (this.content[2 * i] != null) { + @SuppressWarnings("unchecked") K key = (K) this.content[2 * i]; + @SuppressWarnings("unchecked") V value = (V) this.content[2 * i + 1]; + + if (value == defaultValue) { + throw new IllegalStateException("Node contains default value!"); + } + int hashCode = hashProvider.getHash(key, hashDepth(depth)); + int shiftDepth = shiftDepth(depth); + int selectedHashFragment = hashFragment(hashCode, shiftDepth); + if (i != selectedHashFragment) { + throw new IllegalStateException("Key " + key + " with hash code " + hashCode + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); + } + } + } + // 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]; + subNode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); + } + } + // check the hash + if (cachedHashValid) { + int oldHash = this.cachedHash; + invalidateHash(); + int newHash = hashCode(); + if (oldHash != newHash) { + throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); + } + } + } + + protected void invalidateHash() { + this.cachedHashValid = false; + } + + @Override + public int hashCode() { + if (!this.cachedHashValid) { + this.cachedHash = Arrays.hashCode(content); + this.cachedHashValid = true; + } + return this.cachedHash; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (obj instanceof MutableNode mutableObj) { + if (obj.hashCode() != this.hashCode()) { + return false; + } else { + for (int i = 0; i < FACTOR * 2; i++) { + Object thisContent = this.content[i]; + if (thisContent != null && !thisContent.equals(mutableObj.content[i])) { + return false; + } + } + return true; + } + } else if (obj instanceof ImmutableNode immutableObj) { + return ImmutableNode.compareImmutableMutable(immutableObj, this); + } else { + return false; + } + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/Node.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/Node.java new file mode 100644 index 00000000..0ecf2712 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/Node.java @@ -0,0 +1,131 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import java.util.Map; + +import tools.refinery.store.map.ContinuousHashProvider; + +public abstract class Node { + public static final int BRANCHING_FACTOR_BITS = 5; + public static final int FACTOR = 1 << BRANCHING_FACTOR_BITS; + protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS; + protected static final int FACTOR_MASK = FACTOR - 1; + public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS; + public static final int FACTOR_SELECTION_BITS = 32 - Integer.numberOfLeadingZeros(NUMBER_OF_FACTORS); + public static final int FACTOR_SELECTION_MASK = (1 << FACTOR_SELECTION_BITS) - 1; + public static final int INCREMENT_BIG_STEP = (1 << FACTOR_SELECTION_BITS) - NUMBER_OF_FACTORS; + + /** + * Increments the depth of the search in the tree. The depth parameter has two + * components: the least few bits selects the fragment of the hashcode, the + * other part selects the continuous hash. + * + * @param depth parameter encoding the fragment and the depth + * @return new depth. + */ + protected int incrementDepth(int depth) { + int newDepth = depth + 1; + if ((newDepth & FACTOR_SELECTION_MASK) == NUMBER_OF_FACTORS) { + newDepth += INCREMENT_BIG_STEP; + } + return newDepth; + } + + /** + * Calculates the index for the continuous hash. + * + * @param depth The depth of the node in the tree. + * @return The index of the continuous hash. + */ + protected static int hashDepth(int depth) { + return depth >> FACTOR_SELECTION_BITS; + } + + /** + * Calculates the which segment of a single hash should be used. + * + * @param depth The depth of the node in the tree. + * @return The segment of a hash code. + */ + protected static int shiftDepth(int depth) { + return depth & FACTOR_SELECTION_MASK; + } + + /** + * Selects a segments from a complete hash for a given depth. + * + * @param hash A complete hash. + * @param shiftDepth The index of the segment. + * @return The segment as an integer. + */ + protected static int hashFragment(int hash, int shiftDepth) { + if (shiftDepth < 0 || Node.NUMBER_OF_FACTORS < shiftDepth) + throw new IllegalArgumentException("Invalid shift depth! valid interval=[0;5], input=" + shiftDepth); + return (hash >>> shiftDepth * BRANCHING_FACTOR_BITS) & FACTOR_MASK; + } + + /** + * Returns the hash code for a given depth. It may calculate new hash code, or + * reuse a hash code calculated for depth-1. + * + * @param key The key. + * @param hash Hash code for depth-1 + * @param depth The depth. + * @return The new hash code. + */ + protected int newHash(final ContinuousHashProvider hashProvider, K key, int hash, int depth) { + final int shiftDepth = shiftDepth(depth); + if (shiftDepth == 0) { + final int hashDepth = hashDepth(depth); + if (hashDepth >= ContinuousHashProvider.MAX_PRACTICAL_DEPTH) { + throw new IllegalArgumentException( + "Key " + key + " have the clashing hashcode over the practical depth limitation (" + + ContinuousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); + } + return hashProvider.getHash(key, hashDepth); + } else { + return hash; + } + } + + public abstract V getValue(K key, ContinuousHashProvider hashProvider, V defaultValue, int hash, + int depth); + + public abstract Node putValue(K key, V value, OldValueBox old, + ContinuousHashProvider hashProvider, V defaultValue, int hash, int depth); + + public abstract long getSize(); + + abstract MutableNode toMutable(); + + public abstract ImmutableNode toImmutable(Map, ImmutableNode> cache); + + protected abstract MutableNode isMutable(); + + /** + * Moves a {@link MapCursor} to its next position. + * + * @param cursor the cursor + * @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(); + prettyPrint(stringBuilder, 0, -1); + return stringBuilder.toString(); + } + + public void checkIntegrity(ContinuousHashProvider hashProvider, V defaultValue, int depth) { + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/OldValueBox.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/OldValueBox.java new file mode 100644 index 00000000..1b0a4b0c --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/OldValueBox.java @@ -0,0 +1,24 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +public class OldValueBox{ + V oldValue; + boolean isSet = false; + + public V getOldValue() { + if(!isSet) throw new IllegalStateException(); + isSet = false; + return oldValue; + } + + public void setOldValue(V ouldValue) { + if(isSet) throw new IllegalStateException(); + this.oldValue = ouldValue; + isSet = true; + } + +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java new file mode 100644 index 00000000..9409ace0 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java @@ -0,0 +1,38 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.*; + +import java.util.List; + +public class StateBasedVersionedMapStoreFactory implements VersionedMapStoreFactory { + private final V defaultValue; + private final ContinuousHashProvider continuousHashProvider; + private final VersionedMapStoreStateConfiguration config; + + public StateBasedVersionedMapStoreFactory(V defaultValue, Boolean transformToImmutable, VersionedMapStoreFactoryBuilder.SharingStrategy sharingStrategy, ContinuousHashProvider continuousHashProvider) { + this.defaultValue = defaultValue; + this.continuousHashProvider = continuousHashProvider; + + this.config = new VersionedMapStoreStateConfiguration( + transformToImmutable, + sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE || sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP, + sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP); + } + + @Override + public VersionedMapStore createOne() { + return new VersionedMapStoreStateImpl<>(continuousHashProvider, defaultValue, config); + + } + + @Override + public List> createGroup(int amount) { + return VersionedMapStoreStateImpl.createSharedVersionedMapStores(amount, continuousHashProvider, defaultValue, + config); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java new file mode 100644 index 00000000..817fc70b --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java @@ -0,0 +1,171 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.*; + +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import java.util.Objects; + +/** + * Not threadSafe in itself + * + * @param + * @param + * @author Oszkar Semerath + */ +public class VersionedMapStateImpl implements VersionedMap { + protected final VersionedMapStoreStateImpl store; + + protected final ContinuousHashProvider hashProvider; + protected final V defaultValue; + protected Node root; + + private final OldValueBox oldValueBox = new OldValueBox<>(); + + public VersionedMapStateImpl( + VersionedMapStoreStateImpl store, + ContinuousHashProvider hashProvider, + V defaultValue) { + this.store = store; + this.hashProvider = hashProvider; + this.defaultValue = defaultValue; + this.root = null; + } + + public VersionedMapStateImpl( + VersionedMapStoreStateImpl store, + ContinuousHashProvider hashProvider, + V defaultValue, Node data) { + this.store = store; + this.hashProvider = hashProvider; + this.defaultValue = defaultValue; + this.root = data; + } + + @Override + public V getDefaultValue() { + return defaultValue; + } + + public ContinuousHashProvider getHashProvider() { + return hashProvider; + } + + @Override + public V put(K key, V value) { + if (root != null) { + root = root.putValue(key, value, oldValueBox, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); + return oldValueBox.getOldValue(); + } else { + root = MutableNode.initialize(key, value, hashProvider, defaultValue); + return defaultValue; + } + } + + @Override + public void putAll(Cursor cursor) { + if (cursor.getDependingMaps().contains(this)) { + List keys = new LinkedList<>(); + List values = new LinkedList<>(); + while (cursor.move()) { + keys.add(cursor.getKey()); + values.add(cursor.getValue()); + } + Iterator keyIterator = keys.iterator(); + Iterator valueIterator = values.iterator(); + while (keyIterator.hasNext()) { + var key = keyIterator.next(); + var value = valueIterator.next(); + this.put(key,value); + } + } else { + while (cursor.move()) { + this.put(cursor.getKey(), cursor.getValue()); + } + } + } + + @Override + public V get(K key) { + if (root != null) { + return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); + } else { + return defaultValue; + } + } + + @Override + public long getSize() { + if (root == null) { + return 0; + } else { + return root.getSize(); + } + } + + @Override + public Cursor getAll() { + return new MapCursor<>(this.root, this); + } + + @Override + public DiffCursor getDiffCursor(long toVersion) { + InOrderMapCursor fromCursor = new InOrderMapCursor<>(this); + VersionedMapStateImpl toMap = (VersionedMapStateImpl) this.store.createMap(toVersion); + InOrderMapCursor toCursor = new InOrderMapCursor<>(toMap); + return new MapDiffCursor<>(this.defaultValue, fromCursor, toCursor); + } + + + @Override + public long commit() { + return this.store.commit(root, this); + } + + public void setRoot(Node root) { + this.root = root; + } + + @Override + public void restore(long state) { + root = this.store.revert(state); + } + + public String prettyPrint() { + if (this.root != null) { + StringBuilder s = new StringBuilder(); + this.root.prettyPrint(s, 0, -1); + return s.toString(); + } else { + return "empty tree"; + } + } + + @Override + public void checkIntegrity() { + if (this.root != null) { + this.root.checkIntegrity(hashProvider, defaultValue, 0); + } + } + + @Override + public int contentHashCode(ContentHashCode mode) { + // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode. + if(root == null) { + return 0; + } else { + return root.hashCode(); + } + } + + @Override + public boolean contentEquals(AnyVersionedMap other) { + return other instanceof VersionedMapStateImpl otherImpl && Objects.equals(root, otherImpl.root); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java new file mode 100644 index 00000000..45f30cc7 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java @@ -0,0 +1,56 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.ContinuousHashProvider; +import tools.refinery.store.map.VersionedMapStore; + +public class VersionedMapStoreStateConfiguration { + + public VersionedMapStoreStateConfiguration() { + + } + public VersionedMapStoreStateConfiguration(boolean immutableWhenCommitting, boolean sharedNodeCacheInStore, + boolean sharedNodeCacheInStoreGroups) { + super(); + this.immutableWhenCommitting = immutableWhenCommitting; + this.sharedNodeCacheInStore = sharedNodeCacheInStore; + this.sharedNodeCacheInStoreGroups = sharedNodeCacheInStoreGroups; + } + + /** + * If true root is replaced with immutable node when committed. Frees up memory + * by releasing immutable nodes, but it may decrease performance by recreating + * immutable nodes upon changes (some evidence). + */ + private boolean immutableWhenCommitting = true; + public boolean isImmutableWhenCommitting() { + return immutableWhenCommitting; + } + + /** + * If true, all sub-nodes are cached within a {@link VersionedMapStore}. It + * decreases the memory requirements. It may increase performance by discovering + * existing immutable copy of a node (some evidence). Additional overhead may + * decrease performance (no example found). The option permits the efficient + * implementation of version deletion. + */ + private boolean sharedNodeCacheInStore = true; + public boolean isSharedNodeCacheInStore() { + return sharedNodeCacheInStore; + } + + /** + * If true, all sub-nodes are cached within a group of + * {@link VersionedMapStoreStateImpl#createSharedVersionedMapStores(int, ContinuousHashProvider, Object, VersionedMapStoreStateConfiguration)}. + * If {@link VersionedMapStoreStateConfiguration#sharedNodeCacheInStore} is + * false, then it has currently no impact. + */ + private boolean sharedNodeCacheInStoreGroups = true; + public boolean isSharedNodeCacheInStoreGroups() { + return sharedNodeCacheInStoreGroups; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java new file mode 100644 index 00000000..0651772a --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java @@ -0,0 +1,129 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.*; + +import java.util.*; + +public class VersionedMapStoreStateImpl implements VersionedMapStore { + // Configuration + private final boolean immutableWhenCommitting; + + // Static data + protected final ContinuousHashProvider hashProvider; + protected final V defaultValue; + + // Dynamic data + protected final Map> states = new HashMap<>(); + protected final Map, ImmutableNode> nodeCache; + protected long nextID = 0; + + public VersionedMapStoreStateImpl(ContinuousHashProvider hashProvider, V defaultValue, + VersionedMapStoreStateConfiguration config) { + this.immutableWhenCommitting = config.isImmutableWhenCommitting(); + this.hashProvider = hashProvider; + this.defaultValue = defaultValue; + if (config.isSharedNodeCacheInStore()) { + nodeCache = new HashMap<>(); + } else { + nodeCache = null; + } + } + + private VersionedMapStoreStateImpl(ContinuousHashProvider hashProvider, V defaultValue, + Map, ImmutableNode> nodeCache, VersionedMapStoreStateConfiguration config) { + this.immutableWhenCommitting = config.isImmutableWhenCommitting(); + this.hashProvider = hashProvider; + this.defaultValue = defaultValue; + this.nodeCache = nodeCache; + } + + public VersionedMapStoreStateImpl(ContinuousHashProvider hashProvider, V defaultValue) { + this(hashProvider, defaultValue, new VersionedMapStoreStateConfiguration()); + } + + public static List> createSharedVersionedMapStores(int amount, + ContinuousHashProvider hashProvider, V defaultValue, + VersionedMapStoreStateConfiguration config) { + List> result = new ArrayList<>(amount); + if (config.isSharedNodeCacheInStoreGroups()) { + Map, ImmutableNode> nodeCache; + if (config.isSharedNodeCacheInStore()) { + nodeCache = new HashMap<>(); + } else { + nodeCache = null; + } + for (int i = 0; i < amount; i++) { + result.add(new VersionedMapStoreStateImpl<>(hashProvider, defaultValue, nodeCache, config)); + } + } else { + for (int i = 0; i < amount; i++) { + result.add(new VersionedMapStoreStateImpl<>(hashProvider, defaultValue, config)); + } + } + return result; + } + + public static List> createSharedVersionedMapStores(int amount, + ContinuousHashProvider hashProvider, V defaultValue) { + return createSharedVersionedMapStores(amount, hashProvider, defaultValue, new VersionedMapStoreStateConfiguration()); + } + + @Override + public synchronized Set getStates() { + return new HashSet<>(states.keySet()); + } + + @Override + public VersionedMap createMap() { + return new VersionedMapStateImpl<>(this, hashProvider, defaultValue); + } + + @Override + public VersionedMap createMap(long state) { + ImmutableNode data = revert(state); + return new VersionedMapStateImpl<>(this, hashProvider, defaultValue, data); + } + + public synchronized ImmutableNode revert(long state) { + if (states.containsKey(state)) { + return states.get(state); + } else { + ArrayList existingKeys = new ArrayList<>(states.keySet()); + Collections.sort(existingKeys); + throw new IllegalArgumentException("Store does not contain state " + state + "! Available states: " + + Arrays.toString(existingKeys.toArray())); + } + } + + public synchronized long commit(Node data, VersionedMapStateImpl mapToUpdateRoot) { + ImmutableNode immutable; + if (data != null) { + immutable = data.toImmutable(this.nodeCache); + } else { + immutable = null; + } + + if (nextID == Long.MAX_VALUE) + throw new IllegalStateException("Map store run out of Id-s"); + long id = nextID++; + this.states.put(id, immutable); + if (this.immutableWhenCommitting) { + mapToUpdateRoot.setRoot(immutable); + } + return id; + } + + @Override + public DiffCursor getDiffCursor(long fromState, long toState) { + VersionedMapStateImpl map1 = (VersionedMapStateImpl) createMap(fromState); + VersionedMapStateImpl map2 = (VersionedMapStateImpl) 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/model/TupleHashProvider.java b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java index fdd4425e..3c94541f 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java @@ -5,12 +5,12 @@ */ package tools.refinery.store.model; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.tuple.Tuple; import tools.refinery.store.tuple.Tuple1; import tools.refinery.store.tuple.Tuple2; -public class TupleHashProvider implements ContinousHashProvider { +public class TupleHashProvider implements ContinuousHashProvider { protected static final int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java deleted file mode 100644 index 14116a90..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java +++ /dev/null @@ -1,34 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.model; - -import tools.refinery.store.map.ContinousHashProvider; -import tools.refinery.store.tuple.Tuple; - -public class TupleHashProviderBitMagic implements ContinousHashProvider { - - @Override - public int getHash(Tuple key, int index) { - if(key.getSize() == 1) { - return key.get(0); - } - - int result = 0; - final int startBitIndex = index*30; - final int finalBitIndex = startBitIndex+30; - final int arity = key.getSize(); - - for(int i = startBitIndex; i<=finalBitIndex; i++) { - final int selectedKey = key.get(i%arity); - final int selectedPosition = 1<<(i/arity); - if((selectedKey&selectedPosition) != 0) { - result |= 1<<(i%30); - } - } - - return result; - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java index aafbe130..2cc7b19c 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java @@ -8,10 +8,10 @@ package tools.refinery.store.model.internal; import tools.refinery.store.adapter.AdapterUtils; import tools.refinery.store.adapter.ModelAdapterBuilder; import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.VersionedMapStoreImpl; +import tools.refinery.store.map.VersionedMapStoreFactory; +import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; import tools.refinery.store.model.ModelStore; import tools.refinery.store.model.ModelStoreBuilder; -import tools.refinery.store.model.TupleHashProvider; import tools.refinery.store.representation.AnySymbol; import tools.refinery.store.representation.Symbol; import tools.refinery.store.tuple.Tuple; @@ -77,8 +77,12 @@ public class ModelStoreBuilderImpl implements ModelStoreBuilder { private void createStores(Map> stores, SymbolEquivalenceClass equivalenceClass, List symbols) { int size = symbols.size(); - var storeGroup = VersionedMapStoreImpl.createSharedVersionedMapStores(size, TupleHashProvider.INSTANCE, - equivalenceClass.defaultValue()); + VersionedMapStoreFactory mapFactory = VersionedMapStore + .builder() + .strategy(VersionedMapStoreFactoryBuilder.StoreStrategy.DELTA) + .defaultValue(equivalenceClass.defaultValue()) + .build(); + var storeGroup = mapFactory.createGroup(size); for (int i = 0; i < size; i++) { stores.put(symbols.get(i), storeGroup.get(i)); } 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 index 4ada4ea4..98756460 100644 --- 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 @@ -8,8 +8,8 @@ package tools.refinery.store.map.tests; import org.junit.jupiter.api.Test; import tools.refinery.store.map.VersionedMapStore; import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; -import tools.refinery.store.map.internal.InOrderMapCursor; -import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.internal.state.InOrderMapCursor; +import tools.refinery.store.map.internal.state.VersionedMapStateImpl; import tools.refinery.store.map.tests.utils.MapTestEnvironment; import static org.junit.jupiter.api.Assertions.*; @@ -26,7 +26,7 @@ class InOrderCursorTest { .build() .createOne(); - VersionedMapImpl map = (VersionedMapImpl) store.createMap(); + VersionedMapStateImpl map = (VersionedMapStateImpl) store.createMap(); checkMove(map,0); map.put(1,"A"); @@ -44,7 +44,7 @@ class InOrderCursorTest { } - private void checkMove(VersionedMapImpl map, int num) { + private void checkMove(VersionedMapStateImpl map, int num) { InOrderMapCursor cursor = new InOrderMapCursor<>(map); for(int i=0; i store = new VersionedMapStoreImpl<>(TupleHashProvider.INSTANCE, false); + VersionedMapStore store = new VersionedMapStoreStateImpl<>(TupleHashProvider.INSTANCE, false); var map = store.createMap(); var out1 = map.put(Tuple.of(0), true); assertEquals(false, out1); diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java index 420dade6..abfb4791 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java @@ -17,10 +17,10 @@ import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.Arguments; import org.junit.jupiter.params.provider.MethodSource; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.VersionedMapStoreImpl; -import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.internal.state.VersionedMapStoreStateImpl; +import tools.refinery.store.map.internal.state.VersionedMapStateImpl; import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; import tools.refinery.store.map.tests.utils.MapTestEnvironment; @@ -28,11 +28,11 @@ class MutableImmutableCompareFuzzTest { private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault, int commitFrequency, boolean evilHash) { String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); - ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + ContinuousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); - VersionedMapStore store = new VersionedMapStoreImpl<>(chp, values[0]); - VersionedMapImpl immutable = (VersionedMapImpl) store.createMap(); - VersionedMapImpl mutable = (VersionedMapImpl) store.createMap(); + VersionedMapStore store = new VersionedMapStoreStateImpl<>(chp, values[0]); + VersionedMapStateImpl immutable = (VersionedMapStateImpl) store.createMap(); + VersionedMapStateImpl mutable = (VersionedMapStateImpl) store.createMap(); Random r = new Random(seed); @@ -40,8 +40,8 @@ class MutableImmutableCompareFuzzTest { commitFrequency); } - private void iterativeRandomPutsAndCommitsAndCompare(String scenario, VersionedMapImpl immutable, - VersionedMapImpl mutable, int steps, int maxKey, String[] values, Random r, + private void iterativeRandomPutsAndCommitsAndCompare(String scenario, VersionedMapStateImpl immutable, + VersionedMapStateImpl mutable, int steps, int maxKey, String[] values, Random r, int commitFrequency) { for (int i = 0; i < steps; i++) { int index = i + 1; diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java index 680d962d..b17766b7 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java @@ -18,10 +18,10 @@ import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.Arguments; import org.junit.jupiter.params.provider.MethodSource; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.VersionedMapStoreImpl; -import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.internal.state.VersionedMapStoreStateImpl; +import tools.refinery.store.map.internal.state.VersionedMapStateImpl; import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; import tools.refinery.store.map.tests.utils.MapTestEnvironment; @@ -31,9 +31,9 @@ class SharedStoreFuzzTest { private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault, int commitFrequency, boolean evilHash) { String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); - ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + ContinuousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); - List> stores = VersionedMapStoreImpl.createSharedVersionedMapStores(5, chp, values[0]); + List> stores = VersionedMapStoreStateImpl.createSharedVersionedMapStores(5, chp, values[0]); iterativeRandomPutsAndCommitsThenRestore(scenario, stores, steps, maxKey, values, seed, commitFrequency); } @@ -42,9 +42,9 @@ class SharedStoreFuzzTest { int steps, int maxKey, String[] values, int seed, int commitFrequency) { // 1. maps with versions Random r = new Random(seed); - List> versioneds = new LinkedList<>(); + List> versioneds = new LinkedList<>(); for (VersionedMapStore store : stores) { - versioneds.add((VersionedMapImpl) store.createMap()); + versioneds.add((VersionedMapStateImpl) store.createMap()); } List> index2Version = new LinkedList<>(); @@ -66,9 +66,9 @@ class SharedStoreFuzzTest { } } // 2. create a non-versioned and - List> reference = new LinkedList<>(); + List> reference = new LinkedList<>(); for (VersionedMapStore store : stores) { - reference.add((VersionedMapImpl) store.createMap()); + reference.add((VersionedMapStateImpl) store.createMap()); } r = new Random(seed); 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 e7348370..401f2866 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 @@ -6,7 +6,7 @@ package tools.refinery.store.map.tests.utils; import tools.refinery.store.map.*; -import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.internal.state.VersionedMapStateImpl; import java.util.*; import java.util.Map.Entry; @@ -28,7 +28,7 @@ public class MapTestEnvironment { return values; } - public static ContinousHashProvider prepareHashProvider(final boolean evil) { + public static ContinuousHashProvider prepareHashProvider(final boolean evil) { // Use maxPrime = 2147483629 return (key, index) -> { @@ -187,7 +187,7 @@ public class MapTestEnvironment { //System.out.println(cursor.getKey() + " " + ((VersionedMapImpl) versionedMap).getHashProvider() // .getHash(cursor.getKey(), 0)); if (previous != null) { - int comparisonResult = ((VersionedMapImpl) versionedMap).getHashProvider().compare(previous, + int comparisonResult = ((VersionedMapStateImpl) versionedMap).getHashProvider().compare(previous, cursor.getKey()); assertTrue(comparisonResult < 0, scenario + " Cursor order is not incremental!"); } diff --git a/subprojects/store/src/test/java/tools/refinery/store/model/hashtests/HashEfficiencyTest.java b/subprojects/store/src/test/java/tools/refinery/store/model/hashtests/HashEfficiencyTest.java index 4d4f5e26..5b595da7 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/model/hashtests/HashEfficiencyTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/model/hashtests/HashEfficiencyTest.java @@ -3,7 +3,7 @@ * * SPDX-License-Identifier: EPL-2.0 */ -package tools.refinery.store.model.hashtests; +package tools.refinery.store.model.hashTests; import static org.junit.jupiter.api.Assertions.assertEquals; @@ -14,10 +14,9 @@ import java.util.Random; import org.junit.jupiter.api.Test; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.tuple.Tuple; import tools.refinery.store.model.TupleHashProvider; -import tools.refinery.store.model.TupleHashProviderBitMagic; class HashEfficiencyTest { @@ -95,7 +94,7 @@ class HashEfficiencyTest { List p = nRandoms(2, amount, 1);; assertEquals(amount,p.size()); } - private static double calculateHashClashes(List tuples, ContinousHashProvider chp) { + private static double calculateHashClashes(List tuples, ContinuousHashProvider chp) { int sumClashes = 0; for(int i = 0; i chp, Tuple a, Tuple b) { + private static int calculateHashClash(ContinuousHashProvider chp, Tuple a, Tuple b) { if(a.equals(b)) return 0; final int bits = 5; final int segments = Integer.SIZE/bits; @@ -131,11 +130,9 @@ class HashEfficiencyTest { } public static void main(String[] args) { List hashNames = new LinkedList<>(); - List> hashes = new LinkedList<>(); + List> hashes = new LinkedList<>(); hashNames.add("PrimeGroup"); hashes.add(new TupleHashProvider()); - hashNames.add("BitMagic"); - hashes.add(new TupleHashProviderBitMagic()); int[] arities = new int[] {2,3,4,5}; int[] sizes = new int[] {32*32,32*32*8}; -- cgit v1.2.3-70-g09d2 From c272a44efcff7d35a6ba31ef3cd12d1eb17640a0 Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Wed, 26 Jul 2023 17:48:25 +0200 Subject: Versioned.commit + Versioned.restore uses Version instead of long. When a Version is collected by gc, the store lets the state get collected by gc as well. --- .../java/tools/refinery/store/map/Version.java | 26 +++++++++ .../java/tools/refinery/store/map/Versioned.java | 18 +++++- .../tools/refinery/store/map/VersionedMap.java | 2 +- .../refinery/store/map/VersionedMapStore.java | 8 +-- .../store/map/VersionedMapStoreFactoryBuilder.java | 1 + .../VersionedMapStoreFactoryBuilderImpl.java | 23 ++++++-- .../store/map/internal/delta/MapTransaction.java | 10 ++-- .../map/internal/delta/VersionedMapDeltaImpl.java | 34 ++++++++--- .../internal/delta/VersionedMapStoreDeltaImpl.java | 41 ++++++-------- .../store/map/internal/state/ImmutableNode.java | 3 +- .../state/StateBasedVersionedMapStoreFactory.java | 11 +++- .../map/internal/state/VersionedMapStateImpl.java | 6 +- .../state/VersionedMapStoreStateConfiguration.java | 8 ++- .../internal/state/VersionedMapStoreStateImpl.java | 44 ++++++--------- .../tools/refinery/store/model/Interpretation.java | 3 +- .../java/tools/refinery/store/model/Model.java | 8 +-- .../tools/refinery/store/model/ModelListener.java | 4 +- .../tools/refinery/store/model/ModelStore.java | 8 +-- .../refinery/store/model/internal/ModelImpl.java | 66 +++++++++++----------- .../model/internal/ModelStoreBuilderImpl.java | 6 +- .../store/model/internal/ModelStoreImpl.java | 37 ++++++------ .../store/model/internal/ModelVersion.java | 39 +++++++++++++ .../model/internal/VersionedInterpretation.java | 14 ++--- .../store/map/tests/fuzz/DiffCursorFuzzTest.java | 21 +++---- .../map/tests/fuzz/MultiThreadTestRunnable.java | 16 +++--- .../store/map/tests/fuzz/RestoreFuzzTest.java | 5 +- .../store/map/tests/fuzz/SharedStoreFuzzTest.java | 5 +- .../map/tests/fuzz/utils/FuzzTestCollections.java | 13 ++++- .../store/map/tests/utils/MapTestEnvironment.java | 2 +- .../refinery/store/model/tests/ModelTest.java | 5 +- 30 files changed, 298 insertions(+), 189 deletions(-) create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/Version.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelVersion.java diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/Version.java b/subprojects/store/src/main/java/tools/refinery/store/map/Version.java new file mode 100644 index 00000000..fa2734e4 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/Version.java @@ -0,0 +1,26 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map; + +/** + * Interface denoting versions of {@link Versioned}. + */ +public interface Version { + /** + * Hashcode should be updated in accordance with equals. + * @return a hashcode of the object. + */ + int hashCode(); + + /** + * Equivalence of two {@link Version}. This equivalence must satisfy the following constraint (in addition to the + * constraints of {@link Object#equals(Object)}: if {@code v1} and {@code v2} are {@link Version}s, and {@code v1 + * .equals(v2)}, then {@code versioned.restore(v1)} must be {@code equals} to {@code versioned.restore(v2)}. + * @param o the other object. + * @return weather the two versions are equals. + */ + boolean equals(Object o); +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java b/subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java index 55720db3..da12b0a9 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/Versioned.java @@ -5,8 +5,20 @@ */ package tools.refinery.store.map; +/** + * Object that can save and restore its state. + */ public interface Versioned { - public long commit(); - //maybe revert()? - public void restore(long state); + /** + * Saves the state of the object. + * @return an object that marks the version of the object at the time the function was called. + */ + Version commit(); + + /** + * Restores the state of the object. + * @param state a {@link Version} object that marks the version. The state must be a {@link Version} object + * returned by a previous {@link #commit()}! + */ + void restore(Version state); } diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java index c8226c3e..28194b58 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java @@ -16,5 +16,5 @@ public non-sealed interface VersionedMap extends AnyVersionedMap { void putAll(Cursor cursor); - DiffCursor getDiffCursor(long state); + DiffCursor getDiffCursor(Version state); } diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java index b24c404c..55cf08a5 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java @@ -7,17 +7,13 @@ package tools.refinery.store.map; import tools.refinery.store.map.internal.VersionedMapStoreFactoryBuilderImpl; -import java.util.Set; - public interface VersionedMapStore { VersionedMap createMap(); - VersionedMap createMap(long state); - - Set getStates(); + VersionedMap createMap(Version state); - DiffCursor getDiffCursor(long fromState, long toState); + DiffCursor getDiffCursor(Version fromState, Version toState); static VersionedMapStoreFactoryBuilder builder() { return new VersionedMapStoreFactoryBuilderImpl<>(); diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java index 6b4fc2a0..0ac196f2 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java @@ -20,6 +20,7 @@ public interface VersionedMapStoreFactoryBuilder { VersionedMapStoreFactoryBuilder defaultValue(V defaultValue); VersionedMapStoreFactoryBuilder strategy(StoreStrategy strategy); + VersionedMapStoreFactoryBuilder versionFreeing(boolean enabled); VersionedMapStoreFactoryBuilder stateBasedImmutableWhenCommitting(boolean transformToImmutable); VersionedMapStoreFactoryBuilder stateBasedSharingStrategy(SharingStrategy sharingStrategy); VersionedMapStoreFactoryBuilder stateBasedHashProvider(ContinuousHashProvider hashProvider); diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java index 47470236..9f419ce1 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java @@ -18,6 +18,7 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt private StoreStrategy strategy = null; private Boolean transformToImmutable = null; private SharingStrategy sharingStrategy = null; + private Boolean enableVersionFreeing = null; private ContinuousHashProvider continuousHashProvider = null; private DeltaTransactionStrategy deltaTransactionStrategy = null; @@ -64,6 +65,13 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt return this; } + @Override + public VersionedMapStoreFactoryBuilder versionFreeing(boolean enabled) { + this.enableVersionFreeing = enabled; + checkStrategy(); + return this; + } + @Override public VersionedMapStoreFactoryBuilder stateBasedImmutableWhenCommitting(boolean transformToImmutable) { this.transformToImmutable = transformToImmutable; @@ -118,6 +126,7 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt yield new StateBasedVersionedMapStoreFactory<>(defaultValue, getOrDefault(transformToImmutable,true), getOrDefault(sharingStrategy, SharingStrategy.SHARED_NODE_CACHE_IN_GROUP), + getOrDefault(enableVersionFreeing, true), continuousHashProvider); } case DELTA -> new DeltaBasedVersionedMapStoreFactory<>(defaultValue, @@ -127,13 +136,15 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt @Override public String toString() { - return "VersionedMapStoreBuilder{" + - "defaultValue=" + defaultValue + + return "VersionedMapStoreFactoryBuilderImpl{" + + "defaultSet=" + defaultSet + + ", defaultValue=" + defaultValue + ", strategy=" + strategy + - ", stateBasedImmutableWhenCommitting=" + transformToImmutable + - ", stateBasedNodeSharingStrategy=" + sharingStrategy + - ", hashProvider=" + continuousHashProvider + - ", deltaStorageStrategy=" + deltaTransactionStrategy + + ", transformToImmutable=" + transformToImmutable + + ", sharingStrategy=" + sharingStrategy + + ", enableVersionFreeing=" + enableVersionFreeing + + ", continuousHashProvider=" + continuousHashProvider + + ", deltaTransactionStrategy=" + deltaTransactionStrategy + '}'; } } diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java index 7f9ccd7f..6f3fa6d7 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java @@ -5,17 +5,19 @@ */ package tools.refinery.store.map.internal.delta; +import tools.refinery.store.map.Version; + import java.util.Arrays; import java.util.Objects; -public record MapTransaction(MapDelta[] deltas, long version, MapTransaction parent) { +public record MapTransaction(MapDelta[] deltas, MapTransaction parent, int depth) implements Version { @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + Arrays.hashCode(deltas); - result = prime * result + Objects.hash(parent, version); + result = prime * result + Objects.hash(parent, depth); return result; } @@ -29,11 +31,11 @@ public record MapTransaction(MapDelta[] deltas, long version, MapTra return false; @SuppressWarnings("unchecked") MapTransaction other = (MapTransaction) obj; - return Arrays.equals(deltas, other.deltas) && Objects.equals(parent, other.parent) && version == other.version; + return depth == other.depth && Objects.equals(parent, other.parent) && Arrays.equals(deltas, other.deltas); } @Override public String toString() { - return "MapTransaction " + version + " " + Arrays.toString(deltas); + return "MapTransaction " + depth + " " + Arrays.toString(deltas); } } diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java index 5bb864ac..c19cc817 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java @@ -38,15 +38,15 @@ public class VersionedMapDeltaImpl implements VersionedMap { } @Override - public long commit() { + public Version commit() { MapDelta[] deltas = uncommittedStore.extractAndDeleteDeltas(); - long[] versionContainer = new long[1]; - this.previous = this.store.appendTransaction(deltas, previous, versionContainer); - return versionContainer[0]; + final MapTransaction committedTransaction = this.store.appendTransaction(deltas, previous); + this.previous = committedTransaction; + return committedTransaction; } @Override - public void restore(long state) { + public void restore(Version state) { // 1. restore uncommitted states MapDelta[] uncommitted = this.uncommittedStore.extractAndDeleteDeltas(); if (uncommitted != null) { @@ -61,7 +61,7 @@ public class VersionedMapDeltaImpl implements VersionedMap { this.forward(forward); } else { List[]> backward = new ArrayList<>(); - parent = this.store.getPath(this.previous.version(), state, backward, forward); + parent = this.store.getPath(this.previous, state, backward, forward); this.backward(backward); this.forward(forward); } @@ -75,12 +75,16 @@ public class VersionedMapDeltaImpl implements VersionedMap { } protected void backward(List[]> changes) { + //Currently, this loop statement is faster. + //noinspection ForLoopReplaceableByForEach for (int i = 0; i < changes.size(); i++) { backward(changes.get(i)); } } protected void forward(MapDelta[] changes) { + //Currently, this loop statement is faster. + //noinspection ForLoopReplaceableByForEach for (int i = 0; i < changes.length; i++) { final MapDelta change = changes[i]; K key = change.getKey(); @@ -168,7 +172,7 @@ public class VersionedMapDeltaImpl implements VersionedMap { } @Override - public DiffCursor getDiffCursor(long state) { + public DiffCursor getDiffCursor(Version state) { MapDelta[] backward = this.uncommittedStore.extractDeltas(); List[]> backwardTransactions = new ArrayList<>(); List[]> forwardTransactions = new ArrayList<>(); @@ -178,7 +182,7 @@ public class VersionedMapDeltaImpl implements VersionedMap { } if (this.previous != null) { - store.getPath(this.previous.version(), state, backwardTransactions, forwardTransactions); + store.getPath(this.previous, state, backwardTransactions, forwardTransactions); } else { store.getPath(state, forwardTransactions); } @@ -216,5 +220,19 @@ public class VersionedMapDeltaImpl implements VersionedMap { throw new IllegalStateException("null value stored in map!"); } } + MapTransaction transaction = this.previous; + while(transaction != null) { + MapTransaction parent = transaction.parent(); + if(parent != null) { + if(parent.depth() != transaction.depth()-1) { + throw new IllegalStateException("Parent depths are inconsistent!"); + } + } else { + if(transaction.depth() != 0) { + throw new IllegalArgumentException("Root depth is not 0!"); + } + } + transaction = transaction.parent(); + } } } diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java index 7f56ea77..ed169409 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java @@ -6,6 +6,7 @@ package tools.refinery.store.map.internal.delta; import tools.refinery.store.map.DiffCursor; +import tools.refinery.store.map.Version; import tools.refinery.store.map.VersionedMap; import tools.refinery.store.map.VersionedMapStore; @@ -18,10 +19,6 @@ public class VersionedMapStoreDeltaImpl implements VersionedMapStore // Static data protected final V defaultValue; - // Dynamic data - protected final Map> states = new HashMap<>(); - protected long nextID = 0; - public VersionedMapStoreDeltaImpl(boolean summarizeChanges, V defaultValue) { this.summarizeChanges = summarizeChanges; this.defaultValue = defaultValue; @@ -33,30 +30,32 @@ public class VersionedMapStoreDeltaImpl implements VersionedMapStore } @Override - public VersionedMap createMap(long state) { + public VersionedMap createMap(Version state) { VersionedMapDeltaImpl result = new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue); result.restore(state); return result; } - public synchronized MapTransaction appendTransaction(MapDelta[] deltas, MapTransaction previous, long[] versionContainer) { - long version = nextID++; - versionContainer[0] = version; + public MapTransaction appendTransaction(MapDelta[] deltas, MapTransaction previous) { if (deltas == null) { - states.put(version, previous); return previous; } else { - MapTransaction transaction = new MapTransaction<>(deltas, version, previous); - states.put(version, transaction); - return transaction; + final int depth; + if(previous != null) { + depth = previous.depth()+1; + } else { + depth = 0; + } + return new MapTransaction<>(deltas, previous, depth); } } - private synchronized MapTransaction getState(long state) { - return states.get(state); + @SuppressWarnings("unchecked") + private MapTransaction getState(Version state) { + return (MapTransaction) state; } - public MapTransaction getPath(long to, List[]> forwardTransactions) { + public MapTransaction getPath(Version to, List[]> forwardTransactions) { final MapTransaction target = getState(to); MapTransaction toTransaction = target; while (toTransaction != null) { @@ -66,7 +65,7 @@ public class VersionedMapStoreDeltaImpl implements VersionedMapStore return target; } - public MapTransaction getPath(long from, long to, + public MapTransaction getPath(Version from, Version to, List[]> backwardTransactions, List[]> forwardTransactions) { MapTransaction fromTransaction = getState(from); @@ -74,7 +73,7 @@ public class VersionedMapStoreDeltaImpl implements VersionedMapStore MapTransaction toTransaction = target; while (fromTransaction != toTransaction) { - if (fromTransaction == null || (toTransaction != null && fromTransaction.version() < toTransaction.version())) { + if (fromTransaction == null || (toTransaction != null && fromTransaction.depth() < toTransaction.depth())) { forwardTransactions.add(toTransaction.deltas()); toTransaction = toTransaction.parent(); } else { @@ -85,14 +84,8 @@ public class VersionedMapStoreDeltaImpl implements VersionedMapStore return target; } - - @Override - public synchronized Set getStates() { - return new HashSet<>(states.keySet()); - } - @Override - public DiffCursor getDiffCursor(long fromState, long toState) { + public DiffCursor getDiffCursor(Version fromState, Version toState) { List[]> backwardTransactions = new ArrayList<>(); List[]> forwardTransactions = new ArrayList<>(); getPath(fromState, toState, backwardTransactions, forwardTransactions); diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java index 722f9ed7..5b1d8b77 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java @@ -9,8 +9,9 @@ import java.util.Arrays; import java.util.Map; import tools.refinery.store.map.ContinuousHashProvider; +import tools.refinery.store.map.Version; -public class ImmutableNode extends Node { +public class ImmutableNode extends Node implements Version { /** * Bitmap defining the stored key and values. */ diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java index 9409ace0..ccc791a8 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java @@ -14,14 +14,19 @@ public class StateBasedVersionedMapStoreFactory implements VersionedMapSto private final ContinuousHashProvider continuousHashProvider; private final VersionedMapStoreStateConfiguration config; - public StateBasedVersionedMapStoreFactory(V defaultValue, Boolean transformToImmutable, VersionedMapStoreFactoryBuilder.SharingStrategy sharingStrategy, ContinuousHashProvider continuousHashProvider) { + public StateBasedVersionedMapStoreFactory(V defaultValue, Boolean transformToImmutable, + VersionedMapStoreFactoryBuilder.SharingStrategy sharingStrategy, + boolean versionFreeingEnabled, + ContinuousHashProvider continuousHashProvider) { this.defaultValue = defaultValue; this.continuousHashProvider = continuousHashProvider; this.config = new VersionedMapStoreStateConfiguration( transformToImmutable, - sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE || sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP, - sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP); + sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE + || sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP, + sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP, + versionFreeingEnabled); } @Override diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java index 817fc70b..57eeccf6 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java @@ -115,7 +115,7 @@ public class VersionedMapStateImpl implements VersionedMap { } @Override - public DiffCursor getDiffCursor(long toVersion) { + public DiffCursor getDiffCursor(Version toVersion) { InOrderMapCursor fromCursor = new InOrderMapCursor<>(this); VersionedMapStateImpl toMap = (VersionedMapStateImpl) this.store.createMap(toVersion); InOrderMapCursor toCursor = new InOrderMapCursor<>(toMap); @@ -124,7 +124,7 @@ public class VersionedMapStateImpl implements VersionedMap { @Override - public long commit() { + public Version commit() { return this.store.commit(root, this); } @@ -133,7 +133,7 @@ public class VersionedMapStateImpl implements VersionedMap { } @Override - public void restore(long state) { + public void restore(Version state) { root = this.store.revert(state); } diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java index 45f30cc7..6650f565 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java @@ -14,11 +14,12 @@ public class VersionedMapStoreStateConfiguration { } public VersionedMapStoreStateConfiguration(boolean immutableWhenCommitting, boolean sharedNodeCacheInStore, - boolean sharedNodeCacheInStoreGroups) { + boolean sharedNodeCacheInStoreGroups, boolean versionFreeingEnabled) { super(); this.immutableWhenCommitting = immutableWhenCommitting; this.sharedNodeCacheInStore = sharedNodeCacheInStore; this.sharedNodeCacheInStoreGroups = sharedNodeCacheInStoreGroups; + this.versionFreeingEnabled = versionFreeingEnabled; } /** @@ -53,4 +54,9 @@ public class VersionedMapStoreStateConfiguration { public boolean isSharedNodeCacheInStoreGroups() { return sharedNodeCacheInStoreGroups; } + + private boolean versionFreeingEnabled = true; + public boolean isVersionFreeingEnabled() { + return versionFreeingEnabled; + } } diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java index 0651772a..8ff3f8e7 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java @@ -17,10 +17,7 @@ public class VersionedMapStoreStateImpl implements VersionedMapStore protected final ContinuousHashProvider hashProvider; protected final V defaultValue; - // Dynamic data - protected final Map> states = new HashMap<>(); protected final Map, ImmutableNode> nodeCache; - protected long nextID = 0; public VersionedMapStoreStateImpl(ContinuousHashProvider hashProvider, V defaultValue, VersionedMapStoreStateConfiguration config) { @@ -28,7 +25,7 @@ public class VersionedMapStoreStateImpl implements VersionedMapStore this.hashProvider = hashProvider; this.defaultValue = defaultValue; if (config.isSharedNodeCacheInStore()) { - nodeCache = new HashMap<>(); + nodeCache = createNoteCache(config); } else { nodeCache = null; } @@ -53,7 +50,7 @@ public class VersionedMapStoreStateImpl implements VersionedMapStore if (config.isSharedNodeCacheInStoreGroups()) { Map, ImmutableNode> nodeCache; if (config.isSharedNodeCacheInStore()) { - nodeCache = new HashMap<>(); + nodeCache = createNoteCache(config); } else { nodeCache = null; } @@ -68,39 +65,36 @@ public class VersionedMapStoreStateImpl implements VersionedMapStore return result; } + private static Map createNoteCache(VersionedMapStoreStateConfiguration config) { + if(config.isVersionFreeingEnabled()) { + return new WeakHashMap<>(); + } else { + return new HashMap<>(); + } + } + public static List> createSharedVersionedMapStores(int amount, ContinuousHashProvider hashProvider, V defaultValue) { return createSharedVersionedMapStores(amount, hashProvider, defaultValue, new VersionedMapStoreStateConfiguration()); } - @Override - public synchronized Set getStates() { - return new HashSet<>(states.keySet()); - } - @Override public VersionedMap createMap() { return new VersionedMapStateImpl<>(this, hashProvider, defaultValue); } @Override - public VersionedMap createMap(long state) { + public VersionedMap createMap(Version state) { ImmutableNode data = revert(state); return new VersionedMapStateImpl<>(this, hashProvider, defaultValue, data); } - public synchronized ImmutableNode revert(long state) { - if (states.containsKey(state)) { - return states.get(state); - } else { - ArrayList existingKeys = new ArrayList<>(states.keySet()); - Collections.sort(existingKeys); - throw new IllegalArgumentException("Store does not contain state " + state + "! Available states: " - + Arrays.toString(existingKeys.toArray())); - } + @SuppressWarnings("unchecked") + public synchronized ImmutableNode revert(Version state) { + return (ImmutableNode) state; } - public synchronized long commit(Node data, VersionedMapStateImpl mapToUpdateRoot) { + public synchronized Version commit(Node data, VersionedMapStateImpl mapToUpdateRoot) { ImmutableNode immutable; if (data != null) { immutable = data.toImmutable(this.nodeCache); @@ -108,18 +102,14 @@ public class VersionedMapStoreStateImpl implements VersionedMapStore immutable = null; } - if (nextID == Long.MAX_VALUE) - throw new IllegalStateException("Map store run out of Id-s"); - long id = nextID++; - this.states.put(id, immutable); if (this.immutableWhenCommitting) { mapToUpdateRoot.setRoot(immutable); } - return id; + return immutable; } @Override - public DiffCursor getDiffCursor(long fromState, long toState) { + public DiffCursor getDiffCursor(Version fromState, Version toState) { VersionedMapStateImpl map1 = (VersionedMapStateImpl) createMap(fromState); VersionedMapStateImpl map2 = (VersionedMapStateImpl) createMap(toState); InOrderMapCursor cursor1 = new InOrderMapCursor<>(map1); diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/Interpretation.java b/subprojects/store/src/main/java/tools/refinery/store/model/Interpretation.java index 26ad9a69..72f188d3 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/Interpretation.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/Interpretation.java @@ -7,6 +7,7 @@ package tools.refinery.store.model; import tools.refinery.store.map.Cursor; import tools.refinery.store.map.DiffCursor; +import tools.refinery.store.map.Version; import tools.refinery.store.representation.Symbol; import tools.refinery.store.tuple.Tuple; @@ -22,7 +23,7 @@ public non-sealed interface Interpretation extends AnyInterpretation { void putAll(Cursor cursor); - DiffCursor getDiffCursor(long to); + DiffCursor getDiffCursor(Version to); void addListener(InterpretationListener listener, boolean alsoWhenRestoring); diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/Model.java b/subprojects/store/src/main/java/tools/refinery/store/model/Model.java index d58d91c3..a028b81b 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/Model.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/Model.java @@ -6,6 +6,7 @@ package tools.refinery.store.model; import tools.refinery.store.adapter.ModelAdapter; +import tools.refinery.store.map.Version; import tools.refinery.store.map.Versioned; import tools.refinery.store.representation.AnySymbol; import tools.refinery.store.representation.Symbol; @@ -13,11 +14,10 @@ import tools.refinery.store.representation.Symbol; import java.util.Optional; public interface Model extends Versioned { - long NO_STATE_ID = -1; - + Version NO_STATE_ID = null; ModelStore getStore(); - long getState(); + Version getState(); boolean hasUncommittedChanges(); @@ -27,7 +27,7 @@ public interface Model extends Versioned { Interpretation getInterpretation(Symbol symbol); - ModelDiffCursor getDiffCursor(long to); + ModelDiffCursor getDiffCursor(Version to); Optional tryGetAdapter(Class adapterType); diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/ModelListener.java b/subprojects/store/src/main/java/tools/refinery/store/model/ModelListener.java index a9ad8cfd..703ee10a 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/ModelListener.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/ModelListener.java @@ -5,6 +5,8 @@ */ package tools.refinery.store.model; +import tools.refinery.store.map.Version; + public interface ModelListener { default void beforeCommit() { } @@ -12,7 +14,7 @@ public interface ModelListener { default void afterCommit() { } - default void beforeRestore(long state) { + default void beforeRestore(Version state) { } default void afterRestore() { diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java b/subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java index b10eb8a4..89382b3a 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/ModelStore.java @@ -6,23 +6,21 @@ package tools.refinery.store.model; import tools.refinery.store.adapter.ModelStoreAdapter; +import tools.refinery.store.map.Version; import tools.refinery.store.model.internal.ModelStoreBuilderImpl; import tools.refinery.store.representation.AnySymbol; import java.util.Collection; import java.util.Optional; -import java.util.Set; public interface ModelStore { Collection getSymbols(); Model createEmptyModel(); - Model createModelForState(long state); + Model createModelForState(Version state); - Set getStates(); - - ModelDiffCursor getDiffCursor(long from, long to); + ModelDiffCursor getDiffCursor(Version from, Version to); Optional tryGetAdapter(Class adapterType); diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java index c5475a1a..c2ad9257 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelImpl.java @@ -8,6 +8,7 @@ package tools.refinery.store.model.internal; import tools.refinery.store.adapter.AdapterUtils; import tools.refinery.store.adapter.ModelAdapter; import tools.refinery.store.map.DiffCursor; +import tools.refinery.store.map.Version; import tools.refinery.store.model.*; import tools.refinery.store.representation.AnySymbol; import tools.refinery.store.representation.Symbol; @@ -17,21 +18,21 @@ import java.util.*; public class ModelImpl implements Model { private final ModelStore store; - private long state; - private Map> interpretations; + private Version state; + private LinkedHashMap> interpretations; private final List adapters; private final List listeners = new ArrayList<>(); private boolean uncommittedChanges; private ModelAction pendingAction = ModelAction.NONE; - private long restoringToState = NO_STATE_ID; + private Version restoringToState = null; - ModelImpl(ModelStore store, long state, int adapterCount) { + ModelImpl(ModelStore store, Version state, int adapterCount) { this.store = store; this.state = state; adapters = new ArrayList<>(adapterCount); } - void setInterpretations(Map> interpretations) { + void setInterpretations(LinkedHashMap> interpretations) { this.interpretations = interpretations; } @@ -41,7 +42,7 @@ public class ModelImpl implements Model { } @Override - public long getState() { + public Version getState() { return state; } @@ -57,7 +58,7 @@ public class ModelImpl implements Model { } @Override - public ModelDiffCursor getDiffCursor(long to) { + public ModelDiffCursor getDiffCursor(Version to) { var diffCursors = new HashMap>(interpretations.size()); for (var entry : interpretations.entrySet()) { diffCursors.put(entry.getKey(), entry.getValue().getDiffCursor(to)); @@ -65,7 +66,7 @@ public class ModelImpl implements Model { return new ModelDiffCursor(diffCursors); } - private void setState(long state) { + private void setState(Version state) { this.state = state; uncommittedChanges = false; } @@ -82,11 +83,11 @@ public class ModelImpl implements Model { } private boolean hasPendingAction() { - return pendingAction != ModelAction.NONE || restoringToState != NO_STATE_ID; + return pendingAction != ModelAction.NONE || restoringToState != null; } @Override - public long commit() { + public Version commit() { if (hasPendingAction()) { throw pendingActionError("commit"); } @@ -94,43 +95,40 @@ public class ModelImpl implements Model { try { int listenerCount = listeners.size(); int i = listenerCount; - long version = 0; + + // Before commit message to listeners while (i > 0) { i--; listeners.get(i).beforeCommit(); } - boolean versionSet = false; - for (var interpretation : interpretations.values()) { - long newVersion = interpretation.commit(); - if (versionSet) { - if (version != newVersion) { - throw new IllegalStateException("Interpretations in model have different versions (%d and %d)" - .formatted(version, newVersion)); - } - } else { - version = newVersion; - versionSet = true; - } + + // Doing the commit on the interpretations + Version[] interpretationVersions = new Version[interpretations.size()]; + int j = 0; + for(var interpretationEntry : interpretations.entrySet()) { + interpretationVersions[j++] = interpretationEntry.getValue().commit(); } - setState(version); + ModelVersion modelVersion = new ModelVersion(interpretationVersions); + setState(modelVersion); + + // After commit message to listeners while (i < listenerCount) { listeners.get(i).afterCommit(); i++; } - return version; + + return modelVersion; } finally { pendingAction = ModelAction.NONE; } } @Override - public void restore(long version) { + public void restore(Version version) { if (hasPendingAction()) { - throw pendingActionError("restore to %d".formatted(version)); - } - if (!store.getStates().contains(version)) { - throw new IllegalArgumentException("Store does not contain state %d".formatted(version)); + throw pendingActionError("restore to %s".formatted(version)); } + pendingAction = ModelAction.RESTORE; restoringToState = version; try { @@ -140,9 +138,11 @@ public class ModelImpl implements Model { i--; listeners.get(i).beforeRestore(version); } + int j = 0; for (var interpretation : interpretations.values()) { - interpretation.restore(version); + interpretation.restore(ModelVersion.getInternalVersion(version,j++)); } + setState(version); while (i < listenerCount) { listeners.get(i).afterRestore(); @@ -150,7 +150,7 @@ public class ModelImpl implements Model { } } finally { pendingAction = ModelAction.NONE; - restoringToState = NO_STATE_ID; + restoringToState = null; } } @@ -159,7 +159,7 @@ public class ModelImpl implements Model { case NONE -> throw new IllegalArgumentException("Trying to throw pending action error when there is no " + "pending action"); case COMMIT -> "commit"; - case RESTORE -> "restore to %d".formatted(restoringToState); + case RESTORE -> "restore to %s".formatted(restoringToState); }; return new IllegalStateException("Cannot %s due to pending %s".formatted(currentActionName, pendingActionName)); } diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java index 2cc7b19c..65fa8d24 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java @@ -19,8 +19,8 @@ import tools.refinery.store.tuple.Tuple; import java.util.*; public class ModelStoreBuilderImpl implements ModelStoreBuilder { - private final Set allSymbols = new HashSet<>(); - private final Map, List> equivalenceClasses = new HashMap<>(); + private final LinkedHashSet allSymbols = new LinkedHashSet<>(); + private final LinkedHashMap, List> equivalenceClasses = new LinkedHashMap<>(); private final List adapters = new ArrayList<>(); @Override @@ -59,7 +59,7 @@ public class ModelStoreBuilderImpl implements ModelStoreBuilder { @Override public ModelStore build() { - var stores = new HashMap>(allSymbols.size()); + var stores = new LinkedHashMap>(allSymbols.size()); for (var entry : equivalenceClasses.entrySet()) { createStores(stores, entry.getKey(), entry.getValue()); } diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreImpl.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreImpl.java index 60b735e6..a320a618 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreImpl.java @@ -8,8 +8,8 @@ package tools.refinery.store.model.internal; import tools.refinery.store.adapter.AdapterUtils; import tools.refinery.store.adapter.ModelStoreAdapter; import tools.refinery.store.map.DiffCursor; +import tools.refinery.store.map.Version; import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.model.Model; import tools.refinery.store.model.ModelDiffCursor; import tools.refinery.store.model.ModelStore; import tools.refinery.store.representation.AnySymbol; @@ -18,10 +18,10 @@ import tools.refinery.store.tuple.Tuple; import java.util.*; public class ModelStoreImpl implements ModelStore { - private final Map> stores; + private final LinkedHashMap> stores; private final List adapters; - ModelStoreImpl(Map> stores, int adapterCount) { + ModelStoreImpl(LinkedHashMap> stores, int adapterCount) { this.stores = stores; adapters = new ArrayList<>(adapterCount); } @@ -31,14 +31,14 @@ public class ModelStoreImpl implements ModelStore { return Collections.unmodifiableCollection(stores.keySet()); } - private ModelImpl createModelWithoutInterpretations(long state) { + private ModelImpl createModelWithoutInterpretations(Version state) { return new ModelImpl(this, state, adapters.size()); } @Override public ModelImpl createEmptyModel() { - var model = createModelWithoutInterpretations(Model.NO_STATE_ID); - var interpretations = new HashMap>(stores.size()); + var model = createModelWithoutInterpretations(null); + var interpretations = new LinkedHashMap>(stores.size()); for (var entry : this.stores.entrySet()) { var symbol = entry.getKey(); interpretations.put(symbol, VersionedInterpretation.of(model, symbol, entry.getValue())); @@ -49,13 +49,21 @@ public class ModelStoreImpl implements ModelStore { } @Override - public synchronized ModelImpl createModelForState(long state) { + public synchronized ModelImpl createModelForState(Version state) { var model = createModelWithoutInterpretations(state); - var interpretations = new HashMap>(stores.size()); + var interpretations = new LinkedHashMap>(stores.size()); + + int i=0; for (var entry : this.stores.entrySet()) { var symbol = entry.getKey(); - interpretations.put(symbol, VersionedInterpretation.of(model, symbol, entry.getValue(), state)); + interpretations.put(symbol, + VersionedInterpretation.of( + model, + symbol, + entry.getValue(), + ModelVersion.getInternalVersion(state,i++))); } + model.setInterpretations(interpretations); adaptModel(model); return model; @@ -69,16 +77,7 @@ public class ModelStoreImpl implements ModelStore { } @Override - public synchronized Set getStates() { - var iterator = stores.values().iterator(); - if (iterator.hasNext()) { - return Set.copyOf(iterator.next().getStates()); - } - return Set.of(0L); - } - - @Override - public synchronized ModelDiffCursor getDiffCursor(long from, long to) { + public synchronized ModelDiffCursor getDiffCursor(Version from, Version to) { var diffCursors = new HashMap>(); for (var entry : stores.entrySet()) { var representation = entry.getKey(); diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelVersion.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelVersion.java new file mode 100644 index 00000000..cf3b7fc6 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelVersion.java @@ -0,0 +1,39 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.model.internal; + +import tools.refinery.store.map.Version; + +import java.util.Arrays; + +public record ModelVersion(Version[] mapVersions) implements Version{ + + public static Version getInternalVersion(Version modelVersion, int interpretationIndex) { + return ((ModelVersion)modelVersion).mapVersions()[interpretationIndex]; + } + + @Override + public int hashCode() { + return Arrays.hashCode(mapVersions); + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + ModelVersion that = (ModelVersion) o; + + return Arrays.equals(mapVersions, that.mapVersions); + } + + @Override + public String toString() { + return "ModelVersion{" + + "mapVersions=" + Arrays.toString(mapVersions) + + '}'; + } +} 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 404be65f..76e3baea 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 @@ -5,10 +5,7 @@ */ package tools.refinery.store.model.internal; -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.*; import tools.refinery.store.model.Interpretation; import tools.refinery.store.model.InterpretationListener; import tools.refinery.store.model.Model; @@ -110,15 +107,14 @@ public class VersionedInterpretation implements Interpretation { } @Override - public DiffCursor getDiffCursor(long to) { + public DiffCursor getDiffCursor(Version to) { return map.getDiffCursor(to); } - public long commit() { + Version commit() { return map.commit(); } - - public void restore(long state) { + void restore(Version state) { if (!restoreListeners.isEmpty()) { var diffCursor = getDiffCursor(state); while (diffCursor.move()) { @@ -150,7 +146,7 @@ public class VersionedInterpretation implements Interpretation { } static VersionedInterpretation of(ModelImpl model, AnySymbol symbol, VersionedMapStore store, - long state) { + Version state) { @SuppressWarnings("unchecked") var typedSymbol = (Symbol) symbol; var map = store.createMap(state); 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 5a4f8038..94259edc 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 @@ -10,13 +10,12 @@ import org.junit.jupiter.api.Timeout; import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.Arguments; import org.junit.jupiter.params.provider.MethodSource; -import tools.refinery.store.map.DiffCursor; -import tools.refinery.store.map.VersionedMap; -import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; +import tools.refinery.store.map.*; import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; import tools.refinery.store.map.tests.utils.MapTestEnvironment; +import java.util.HashMap; +import java.util.Map; import java.util.Random; import java.util.stream.Stream; @@ -39,6 +38,7 @@ class DiffCursorFuzzTest { int commitFrequency, boolean commitBeforeDiffCursor) { int largestCommit = -1; + Map index2Version = new HashMap<>(); { // 1. build a map with versions @@ -55,8 +55,9 @@ class DiffCursorFuzzTest { fail(scenario + ":" + index + ": exception happened: " + exception); } if (index % commitFrequency == 0) { - long version = versioned.commit(); - largestCommit = (int) version; + Version version = versioned.commit(); + index2Version.put(index,version); + largestCommit = index; } if (index % 10000 == 0) System.out.println(scenario + ":" + index + "/" + steps + " building finished"); @@ -73,20 +74,20 @@ class DiffCursorFuzzTest { int index = i + 1; if (index % diffTravelFrequency == 0) { // diff-travel - long travelToVersion = r2.nextInt(largestCommit + 1); + int travelToVersion = r2.nextInt(largestCommit + 1); - VersionedMap oracle = store.createMap(travelToVersion); + VersionedMap oracle = store.createMap(index2Version.get(travelToVersion)); if(commitBeforeDiffCursor) { moving.commit(); } - DiffCursor diffCursor = moving.getDiffCursor(travelToVersion); + DiffCursor diffCursor = moving.getDiffCursor(index2Version.get(travelToVersion)); moving.putAll(diffCursor); moving.commit(); MapTestEnvironment.compareTwoMaps(scenario + ":c" + index, oracle, moving); - moving.restore(travelToVersion); + moving.restore(index2Version.get(travelToVersion)); } else { // random puts diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java index 9b2e591a..dfe46bae 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java @@ -13,6 +13,7 @@ import java.util.List; import java.util.Map; import java.util.Random; +import tools.refinery.store.map.Version; import tools.refinery.store.map.VersionedMap; import tools.refinery.store.map.VersionedMapStore; import tools.refinery.store.map.tests.utils.MapTestEnvironment; @@ -61,7 +62,7 @@ public class MultiThreadTestRunnable implements Runnable { // 1. build a map with versions Random r = new Random(seed); VersionedMap versioned = store.createMap(); - Map index2Version = new HashMap<>(); + Map index2Version = new HashMap<>(); for (int i = 0; i < steps; i++) { int index = i + 1; @@ -74,7 +75,7 @@ public class MultiThreadTestRunnable implements Runnable { logAndThrowError(scenario + ":" + index + ": exception happened: " + exception); } if (index % commitFrequency == 0) { - long version = versioned.commit(); + Version version = versioned.commit(); index2Version.put(i, version); } MapTestEnvironment.printStatus(scenario, index, steps, "building"); @@ -100,13 +101,12 @@ public class MultiThreadTestRunnable implements Runnable { MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference, versioned, null); // go back to a random state (probably created by another thread) - List states = new ArrayList<>(store.getStates()); - states.sort(Long::compare); + List states = new ArrayList<>(index2Version.values()); + //states.sort(Long::compare); Collections.shuffle(states, r2); - for (Long state : states.subList(0, Math.min(states.size(), 100))) { - long x = state; - versioned.restore(x); - var clean = store.createMap(x); + for (Version state : states.subList(0, Math.min(states.size(), 100))) { + versioned.restore(state); + var clean = store.createMap(state); MapTestEnvironment.compareTwoMaps(scenario + ":" + index, clean, versioned, null); } versioned.restore(index2Version.get(i)); diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java index 0b399c3a..5c768788 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java @@ -10,6 +10,7 @@ import org.junit.jupiter.api.Timeout; import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.Arguments; import org.junit.jupiter.params.provider.MethodSource; +import tools.refinery.store.map.Version; import tools.refinery.store.map.VersionedMap; import tools.refinery.store.map.VersionedMapStore; import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; @@ -40,7 +41,7 @@ class RestoreFuzzTest { // 1. build a map with versions Random r = new Random(seed); VersionedMap versioned = store.createMap(); - Map index2Version = new HashMap<>(); + Map index2Version = new HashMap<>(); for (int i = 0; i < steps; i++) { int index = i + 1; @@ -53,7 +54,7 @@ class RestoreFuzzTest { fail(scenario + ":" + index + ": exception happened: " + exception); } if (index % commitFrequency == 0) { - long version = versioned.commit(); + Version version = versioned.commit(); index2Version.put(i, version); } MapTestEnvironment.printStatus(scenario, index, steps, "building"); diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java index b17766b7..299c94b1 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java @@ -19,6 +19,7 @@ import org.junit.jupiter.params.provider.Arguments; import org.junit.jupiter.params.provider.MethodSource; import tools.refinery.store.map.ContinuousHashProvider; +import tools.refinery.store.map.Version; import tools.refinery.store.map.VersionedMapStore; import tools.refinery.store.map.internal.state.VersionedMapStoreStateImpl; import tools.refinery.store.map.internal.state.VersionedMapStateImpl; @@ -47,7 +48,7 @@ class SharedStoreFuzzTest { versioneds.add((VersionedMapStateImpl) store.createMap()); } - List> index2Version = new LinkedList<>(); + List> index2Version = new LinkedList<>(); for (int i = 0; i < stores.size(); i++) { index2Version.add(new HashMap<>()); } @@ -59,7 +60,7 @@ class SharedStoreFuzzTest { String nextValue = values[r.nextInt(values.length)]; versioneds.get(storeIndex).put(nextKey, nextValue); if (stepIndex % commitFrequency == 0) { - long version = versioneds.get(storeIndex).commit(); + Version version = versioneds.get(storeIndex).commit(); index2Version.get(storeIndex).put(i, version); } MapTestEnvironment.printStatus(scenario, stepIndex, steps, "building"); 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 4c3ecb09..ec04904e 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 @@ -18,26 +18,35 @@ public final class FuzzTestCollections { public static final Object[] randomSeedOptions = {1}; public static final Object[] storeConfigs = { // State based + // Default VersionedMapStore.builder() - .stateBasedImmutableWhenCommitting(true) .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false)) .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE), + // Evil hash code test VersionedMapStore.builder() - .stateBasedImmutableWhenCommitting(true) .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(true)) .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE), + // No weak hashmap test + VersionedMapStore.builder() + .versionFreeing(false) + .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false)) + .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE), + // Copy when committing, do not hurt the work copy, share between saves. VersionedMapStore.builder() .stateBasedImmutableWhenCommitting(false) .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false)) .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE), + // Copy when committing, do not hurt the work copy, do not share between states. VersionedMapStore.builder() .stateBasedImmutableWhenCommitting(false) .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false)) .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.NO_NODE_CACHE), // Delta based + // Set based transactions VersionedMapStore.builder() .deltaTransactionStrategy(VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.SET), + // List based transactions VersionedMapStore.builder() .deltaTransactionStrategy(VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.LIST) }; 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 401f2866..b84df280 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 @@ -125,7 +125,7 @@ public class MapTestEnvironment { } } - public long commit(){ + public Version commit(){ return sut.commit(); } diff --git a/subprojects/store/src/test/java/tools/refinery/store/model/tests/ModelTest.java b/subprojects/store/src/test/java/tools/refinery/store/model/tests/ModelTest.java index 56b75804..dc7b776e 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/model/tests/ModelTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/model/tests/ModelTest.java @@ -6,6 +6,7 @@ package tools.refinery.store.model.tests; import org.junit.jupiter.api.Test; +import tools.refinery.store.map.Version; import tools.refinery.store.model.Model; import tools.refinery.store.model.ModelStore; import tools.refinery.store.representation.Symbol; @@ -120,7 +121,7 @@ class ModelTest { assertTrue(model.hasUncommittedChanges()); assertEquals(Model.NO_STATE_ID, model.getState()); - long state1 = model.commit(); + Version state1 = model.commit(); assertFalse(model.hasUncommittedChanges()); assertEquals(state1, model.getState()); @@ -134,7 +135,7 @@ class ModelTest { assertTrue(model.hasUncommittedChanges()); assertEquals(state1, model.getState()); - long state2 = model.commit(); + Version state2 = model.commit(); assertFalse(model.hasUncommittedChanges()); assertEquals(state2, model.getState()); -- cgit v1.2.3-70-g09d2