Delta store commit

9 files changed, 572 insertions, 0 deletions

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
new file mode 100644
index 00000000..2bd758e2
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java
@@ -0,0 +1,90 @@
+package tools.refinery.store.map;
+
+import java.util.*;
+
+import tools.refinery.store.map.internal.DeltaDiffCursor;
+import tools.refinery.store.map.internal.MapDelta;
+import tools.refinery.store.map.internal.MapTransaction;
+import tools.refinery.store.map.internal.VersionedMapDeltaImpl;
+
+public class VersionedMapStoreDeltaImpl<K, V> implements VersionedMapStore<K, V>{
+        // Static data
+        protected final V defaultValue;
+
+        // Dynamic data
+        protected final Map<Long,MapTransaction<K, V>> states = new HashMap<>();
+        protected long nextID = 0;
+
+        public VersionedMapStoreDeltaImpl(V defaultValue) {
+                super();
+                this.defaultValue = defaultValue;
+        }
+
+        @Override
+        public VersionedMap<K, V> createMap() {
+                return new VersionedMapDeltaImpl<>(this, defaultValue);
+        }
+
+        @Override
+        public VersionedMap<K, V> createMap(long state) {
+                VersionedMapDeltaImpl<K, V> result = new VersionedMapDeltaImpl<>(this, defaultValue);
+                result.restore(state);
+                return result;
+        }
+
+        public synchronized MapTransaction<K, V> appendTransaction(MapDelta<K, V>[] deltas, MapTransaction<K, V> previous, long[] versionContainer) {
+                long version = nextID++;
+                versionContainer[0] = version;
+                if(deltas == null) {
+                        states.put(version, previous);
+                        return previous;
+                } else {
+                        MapTransaction<K, V> transaction = new MapTransaction<>(deltas, version, previous);
+                        states.put(version, transaction);
+                        return transaction;
+                }
+        }
+
+        private synchronized MapTransaction<K,V> getState(long state) {
+                return states.get(state);
+        }
+
+        public void getPath(long to, List<MapDelta<K, V>[]> forwardTransactions) {
+                MapTransaction<K,V> toTransaction = getState(to);
+                while(toTransaction != null) {
+                        forwardTransactions.add(toTransaction.deltas());
+                        toTransaction = toTransaction.parent();
+                }
+        }
+
+        public void getPath(long from, long to,
+                        List<MapDelta<K, V>[]> backwardTransactions,
+                        List<MapDelta<K, V>[]> forwardTransactions)
+        {
+                MapTransaction<K,V> fromTransaction = getState(from);
+                MapTransaction<K,V> toTransaction = getState(to);
+                while(fromTransaction != toTransaction) {
+                        if(fromTransaction == null || fromTransaction.version() < toTransaction.version()) {
+                                forwardTransactions.add(toTransaction.deltas());
+                                toTransaction = toTransaction.parent();
+                        } else {
+                                backwardTransactions.add(fromTransaction.deltas());
+                                fromTransaction = fromTransaction.parent();
+                        }
+                }
+        }
+
+
+        @Override
+        public synchronized Set<Long> getStates() {
+                return states.keySet();
+        }
+
+        @Override
+        public DiffCursor<K, V> getDiffCursor(long fromState, long toState) {
+                List<MapDelta<K, V>[]> backwardTransactions = new ArrayList<>();
+                List<MapDelta<K, V>[]> 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/DeltaDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java
new file mode 100644
index 00000000..75180bf9
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java
@@ -0,0 +1,127 @@
+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<K, V> implements DiffCursor<K, V> {
+        final List<MapDelta<K, V>[]> backwardTransactions;
+        final List<MapDelta<K, V>[]> forwardTransactions;
+
+        /**
+         * Denotes the direction of traversal. False means backwards, true means
+         * forward.
+         */
+        boolean direction;
+        int listIndex;
+        int arrayIndex;
+
+        public DeltaDiffCursor(List<MapDelta<K, V>[]> backwardTransactions, List<MapDelta<K, V>[]> 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;
+                }
+        }
+
+        protected MapDelta<K, V> getCurrentDelta() {
+                final List<MapDelta<K, V>[]> 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 (isTerminated()) {
+                        return false;
+                } else {
+                        if (this.direction) {
+                                if (arrayIndex+1 < forwardTransactions.get(listIndex).length) {
+                                        arrayIndex++;
+                                        return true;
+                                } else {
+                                        if (listIndex-1 >= 0) {
+                                                listIndex--;
+                                                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<AnyVersionedMap> getDependingMaps() {
+                return Collections.emptySet();
+        }
+
+        @Override
+        public V getFromValue() {
+                return getCurrentDelta().getOldValue();
+        }
+
+        @Override
+        public V getToValue() {
+                return getCurrentDelta().getNewValue();
+        }
+}
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
new file mode 100644
index 00000000..4a8e9709
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java
@@ -0,0 +1,62 @@
+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<K, V> implements Cursor<K, V> {
+        final Iterator<Entry<K, V>> iterator;
+        final VersionedMap<K, V> source;
+
+        private boolean terminated;
+        private K key;
+        private V value;
+
+        public IteratorAsCursor(VersionedMap<K, V> source, Map<K, V> current) {
+                this.iterator = current.entrySet().iterator();
+                this.source = source;
+                move();
+        }
+
+        @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<K, V> next = iterator.next();
+                        this.key = next.getKey();
+                        this.value = next.getValue();
+                }
+                return !terminated;
+        }
+
+        @Override
+        public boolean isDirty() {
+                return false;
+        }
+
+        @Override
+        public Set<AnyVersionedMap> getDependingMaps() {
+                return Set.of(this.source);
+        }
+}
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
new file mode 100644
index 00000000..86e9fe62
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java
@@ -0,0 +1,15 @@
+package tools.refinery.store.map.internal;
+
+public record MapDelta<K, V>(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/MapTransaction.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java
new file mode 100644
index 00000000..5996048e
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java
@@ -0,0 +1,34 @@
+package tools.refinery.store.map.internal;
+
+import java.util.Arrays;
+import java.util.Objects;
+
+public record MapTransaction<K, V>(MapDelta<K, V>[] deltas, long version, MapTransaction<K, V> 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<K, V> other = (MapTransaction<K, V>) 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/UncommittedDeltaArrayStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java
new file mode 100644
index 00000000..3b3f94ae
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java
@@ -0,0 +1,31 @@
+package tools.refinery.store.map.internal;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class UncommittedDeltaArrayStore<K, V> implements UncommittedDeltaStore<K, V> {
+        final List<MapDelta<K, V>> uncommittedOldValues = new ArrayList<>();
+
+        @Override
+        public void processChange(K key, V oldValue, V newValue) {
+                uncommittedOldValues.add(new MapDelta<>(key, oldValue, newValue));
+        }
+
+        @Override
+        public MapDelta<K, V>[] extractDeltas() {
+                if (uncommittedOldValues.isEmpty()) {
+                        return null;
+                } else {
+                        @SuppressWarnings("unchecked")
+                        MapDelta<K, V>[] result = uncommittedOldValues.toArray(new MapDelta[0]);
+                        return result;
+                }
+        }
+
+        @Override
+        public MapDelta<K, V>[] extractAndDeleteDeltas() {
+                MapDelta<K, V>[] 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
new file mode 100644
index 00000000..73df5080
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java
@@ -0,0 +1,47 @@
+package tools.refinery.store.map.internal;
+
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Map.Entry;
+
+import tools.refinery.store.map.VersionedMap;
+
+public class UncommittedDeltaMapStore<K, V> implements UncommittedDeltaStore<K, V> {
+        final VersionedMap<K, V> source;
+        final Map<K, V> uncommittedOldValues = new HashMap<>();
+
+        public UncommittedDeltaMapStore(VersionedMap<K, V> source) {
+                this.source = source;
+        }
+
+        @Override
+        public void processChange(K key, V oldValue, V newValue) {
+                this.uncommittedOldValues.putIfAbsent(key, oldValue);
+        }
+
+        @Override
+        public MapDelta<K, V>[] extractDeltas() {
+                if (uncommittedOldValues.isEmpty()) {
+                        return null;
+                } else {
+                        @SuppressWarnings("unchecked")
+                        MapDelta<K, V>[] deltas = new MapDelta[uncommittedOldValues.size()];
+                        int i = 0;
+                        for (Entry<K, V> 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<K, V>[] extractAndDeleteDeltas() {
+                MapDelta<K, V>[] 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
new file mode 100644
index 00000000..37e5817c
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java
@@ -0,0 +1,10 @@
+package tools.refinery.store.map.internal;
+
+public interface UncommittedDeltaStore<K, V> {
+        void processChange(K key, V oldValue, V newValue);
+
+        MapDelta<K, V>[] extractDeltas();
+
+        MapDelta<K, V>[] extractAndDeleteDeltas();
+
+}
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
new file mode 100644
index 00000000..deedf134
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java
@@ -0,0 +1,156 @@
+package tools.refinery.store.map.internal;
+
+import java.util.*;
+
+import tools.refinery.store.map.*;
+
+public class VersionedMapDeltaImpl<K, V> implements VersionedMap<K, V> {
+        protected final VersionedMapStoreDeltaImpl<K, V> store;
+
+        final Map<K, V> current;
+
+        final UncommittedDeltaStore<K, V> uncommittedStore;
+        MapTransaction<K, V> previous;
+
+        protected final V defaultValue;
+
+        public VersionedMapDeltaImpl(VersionedMapStoreDeltaImpl<K, V> store, V defaultValue) {
+                this.store = store;
+                this.defaultValue = defaultValue;
+
+                current = new HashMap<>();
+                uncommittedStore = new UncommittedDeltaArrayStore<>();
+        }
+
+        @Override
+        public long commit() {
+                MapDelta<K, V>[] 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<K, V>[] uncommitted = this.uncommittedStore.extractAndDeleteDeltas();
+                if (uncommitted != null) {
+                        backward(uncommitted);
+                }
+
+                // 2. get common ancestor
+                List<MapDelta<K, V>[]> forward = new ArrayList<>();
+                if (this.previous == null) {
+                        this.store.getPath(state, forward);
+                        this.forward(forward);
+                } else {
+                        List<MapDelta<K, V>[]> backward = new ArrayList<>();
+                        this.store.getPath(this.previous.version(), state, backward, forward);
+                        this.backward(backward);
+                        this.forward(forward);
+                }
+        }
+
+        protected void forward(List<MapDelta<K, V>[]> changes) {
+                for (int i = changes.size() - 1; i >= 0; i--) {
+                        forward(changes.get(i));
+                }
+        }
+
+        protected void backward(List<MapDelta<K, V>[]> changes) {
+                for (int i = 0; i < changes.size(); i++) {
+                        backward(changes.get(i));
+                }
+        }
+
+        protected void forward(MapDelta<K, V>[] changes) {
+                for (int i = 0; i < changes.length; i++) {
+                        final MapDelta<K, V> change = changes[i];
+                        current.put(change.getKey(), change.getNewValue());
+                }
+        }
+
+        protected void backward(MapDelta<K, V>[] changes) {
+                for (int i = changes.length - 1; i >= 0; i--) {
+                        final MapDelta<K, V> change = changes[i];
+                        current.put(change.getKey(), change.getOldValue());
+                }
+        }
+
+        @Override
+        public V get(K key) {
+                return current.getOrDefault(key, defaultValue);
+        }
+
+        @Override
+        public Cursor<K, V> getAll() {
+                return new IteratorAsCursor<>(this, current);
+        }
+
+        @Override
+        public V put(K key, V value) {
+                if (value == defaultValue) {
+                        V res = current.remove(key);
+                        if (res == null) {
+                                // no changes
+                                return defaultValue;
+                        } else {
+                                uncommittedStore.processChange(key, res, value);
+                                return res;
+                        }
+                } else {
+                        V oldValue = current.put(key, value);
+                        uncommittedStore.processChange(key, oldValue, value);
+                        return oldValue;
+                }
+        }
+
+        @Override
+        public void putAll(Cursor<K, V> cursor) {
+                throw new UnsupportedOperationException();
+
+        }
+
+        @Override
+        public long getSize() {
+                return current.size();
+        }
+
+        @Override
+        public DiffCursor<K, V> getDiffCursor(long state) {
+                MapDelta<K, V>[] backward = this.uncommittedStore.extractDeltas();
+                List<MapDelta<K, V>[]> backwardTransactions = new ArrayList<>();
+                List<MapDelta<K, V>[]> 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.");
+                }
+        }
+}