From 64f8706af45647b3015abc1bb1378c6be22a515c Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Sat, 29 Jul 2023 16:16:02 +0200 Subject: Initial prototype of the StateCoderAdapter based on NeighbourhoodCalculator. No tests yet. --- subprojects/store/build.gradle.kts | 5 + .../store/statecoding/StateCodeCalculator.java | 10 ++ .../store/statecoding/StateCoderAdapter.java | 12 ++ .../store/statecoding/StateCoderBuilder.java | 29 +++++ .../store/statecoding/StateCoderStoreAdapter.java | 14 +++ .../internal/StateCoderAdapterImpl.java | 47 ++++++++ .../internal/StateCoderBuilderImpl.java | 48 ++++++++ .../internal/StateCoderStoreAdapterImpl.java | 34 ++++++ .../neighbourhood/NeighbourhoodCalculator.java | 129 +++++++++++++++++++++ .../statecoding/neighbourhood/ObjectCode.java | 55 +++++++++ 10 files changed, 383 insertions(+) create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculator.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderAdapter.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderBuilder.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderStoreAdapter.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderAdapterImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCode.java diff --git a/subprojects/store/build.gradle.kts b/subprojects/store/build.gradle.kts index 2c485020..d653f01d 100644 --- a/subprojects/store/build.gradle.kts +++ b/subprojects/store/build.gradle.kts @@ -8,3 +8,8 @@ plugins { id("tools.refinery.gradle.java-library") id("tools.refinery.gradle.jmh") } + +dependencies { + implementation(libs.eclipseCollections) + implementation(libs.eclipseCollections.api) +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculator.java new file mode 100644 index 00000000..479b61ed --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCodeCalculator.java @@ -0,0 +1,10 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding; + +public interface StateCodeCalculator { + +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderAdapter.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderAdapter.java new file mode 100644 index 00000000..8795fb68 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderAdapter.java @@ -0,0 +1,12 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding; + +import tools.refinery.store.adapter.ModelAdapter; + +public interface StateCoderAdapter extends ModelAdapter { + int calculateHashCode(); +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderBuilder.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderBuilder.java new file mode 100644 index 00000000..2f37584f --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderBuilder.java @@ -0,0 +1,29 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding; + +import tools.refinery.store.adapter.ModelAdapterBuilder; +import tools.refinery.store.model.ModelStore; +import tools.refinery.store.representation.AnySymbol; + +import java.util.Collection; +import java.util.List; + +public interface StateCoderBuilder extends ModelAdapterBuilder { + StateCoderBuilder exclude(AnySymbol symbol); + default StateCoderBuilder excludeAll(Collection symbols) { + for(var symbol : symbols) { + exclude(symbol); + } + return this; + } + default StateCoderBuilder excludeAll(AnySymbol... symbols) { + return excludeAll(List.of(symbols)); + } + + @Override + StateCoderStoreAdapter build(ModelStore store); +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderStoreAdapter.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderStoreAdapter.java new file mode 100644 index 00000000..5946a162 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/StateCoderStoreAdapter.java @@ -0,0 +1,14 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding; + +import tools.refinery.store.adapter.ModelStoreAdapter; +import tools.refinery.store.model.Model; + +public interface StateCoderStoreAdapter extends ModelStoreAdapter { + @Override + StateCoderAdapter createModelAdapter(Model model); +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderAdapterImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderAdapterImpl.java new file mode 100644 index 00000000..689db2e3 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderAdapterImpl.java @@ -0,0 +1,47 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.internal; + +import tools.refinery.store.adapter.ModelStoreAdapter; +import tools.refinery.store.model.Interpretation; +import tools.refinery.store.model.Model; +import tools.refinery.store.representation.Symbol; +import tools.refinery.store.statecoding.StateCoderAdapter; +import tools.refinery.store.statecoding.neighbourhood.NeighbourhoodCalculator; + +import java.util.Collection; +import java.util.List; + +public class StateCoderAdapterImpl implements StateCoderAdapter { + final ModelStoreAdapter storeAdapter; + final Model model; + final NeighbourhoodCalculator calculator; + + StateCoderAdapterImpl(ModelStoreAdapter storeAdapter, Model model, Collection> symbols) { + this.storeAdapter = storeAdapter; + this.model = model; + + List> interpretations = symbols.stream().map(model::getInterpretation).toList(); + calculator = new NeighbourhoodCalculator(interpretations); + } + + @Override + public Model getModel() { + return model; + } + + @Override + public ModelStoreAdapter getStoreAdapter() { + return storeAdapter; + } + + @Override + public int calculateHashCode() { + return calculator.calculate(); + } + + +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java new file mode 100644 index 00000000..700723f4 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java @@ -0,0 +1,48 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.internal; + +import tools.refinery.store.model.ModelStore; +import tools.refinery.store.model.ModelStoreBuilder; +import tools.refinery.store.representation.AnySymbol; +import tools.refinery.store.representation.Symbol; +import tools.refinery.store.statecoding.StateCoderBuilder; +import tools.refinery.store.statecoding.StateCoderStoreAdapter; + +import java.util.HashSet; +import java.util.LinkedHashSet; +import java.util.Set; + +public class StateCoderBuilderImpl implements StateCoderBuilder { + Set excluded = new HashSet<>(); + + @Override + public StateCoderBuilder exclude(AnySymbol symbol) { + excluded.add(symbol); + return this; + } + + @Override + public boolean isConfigured() { + return true; + } + + @Override + public void configure(ModelStoreBuilder storeBuilder) { + // It does not modify the build process + } + + @Override + public StateCoderStoreAdapter build(ModelStore store) { + Set> symbols = new LinkedHashSet<>(); + for (AnySymbol symbol : store.getSymbols()) { + if (!excluded.contains(symbol) && (symbol instanceof Symbol typed)) { + symbols.add(typed); + } + } + return new StateCoderStoreAdapterImpl(store, symbols); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java new file mode 100644 index 00000000..77d36e96 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderStoreAdapterImpl.java @@ -0,0 +1,34 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.internal; + +import tools.refinery.store.model.Model; +import tools.refinery.store.model.ModelStore; +import tools.refinery.store.representation.Symbol; +import tools.refinery.store.statecoding.StateCoderAdapter; +import tools.refinery.store.statecoding.StateCoderStoreAdapter; + +import java.util.Collection; + +public class StateCoderStoreAdapterImpl implements StateCoderStoreAdapter { + final ModelStore store; + final Collection> symbols; + + StateCoderStoreAdapterImpl(ModelStore store, Collection> symbols) { + this.store = store; + this.symbols = symbols; + } + + @Override + public ModelStore getStore() { + return store; + } + + @Override + public StateCoderAdapter createModelAdapter(Model model) { + return new StateCoderAdapterImpl(this,model,symbols); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java new file mode 100644 index 00000000..24a7122e --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java @@ -0,0 +1,129 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.neighbourhood; + +import org.eclipse.collections.api.set.primitive.MutableLongSet; +import org.eclipse.collections.impl.set.mutable.primitive.LongHashSet; +import tools.refinery.store.model.Interpretation; +import tools.refinery.store.tuple.Tuple; +import tools.refinery.store.tuple.Tuple0; + +import java.util.ArrayList; +import java.util.LinkedHashMap; +import java.util.List; +import java.util.Random; + +public class NeighbourhoodCalculator { + final List> nullImpactValues; + final LinkedHashMap, long[]> impactValues; + + public NeighbourhoodCalculator(List> interpretations) { + this.nullImpactValues = new ArrayList<>(); + this.impactValues = new LinkedHashMap<>(); + Random random = new Random(1); + + for (Interpretation interpretation : interpretations) { + int arity = interpretation.getSymbol().arity(); + if (arity == 0) { + nullImpactValues.add(interpretation); + } else { + long[] impact = new long[arity]; + for (int i = 0; i < arity; i++) { + impact[i] = random.nextLong(); + } + impactValues.put(interpretation, impact); + } + } + } + + public int calculate() { + ObjectCode previous = new ObjectCode(); + ObjectCode next = new ObjectCode(); + + int previousSize = 1; + long lastSum; + boolean grows; + + do{ + for (var impactValueEntry : this.impactValues.entrySet()) { + Interpretation interpretation = impactValueEntry.getKey(); + long[] impact = impactValueEntry.getValue(); + var cursor = interpretation.getAll(); + while (cursor.move()) { + Tuple tuple = cursor.getKey(); + Object value = cursor.getValue(); + long tupleHash = getTupleHash(tuple, value, previous); + addHash(next, tuple, impact, tupleHash); + } + } + + previous = next; + next = null; + lastSum = 0; + MutableLongSet codes = new LongHashSet(); + for (int i = 0; i < previous.getSize(); i++) { + long objectHash = previous.get(i); + codes.add(objectHash); + + final long shifted1 = objectHash>>> 32; + final long shifted2 = objectHash << 32; + lastSum += shifted1 + shifted2; + } + int nextSize = codes.size(); + grows = previousSize < nextSize; + previousSize = nextSize; + + if(grows) { + next = new ObjectCode(previous); + } + } while (grows); + + long result = 1; + for (var nullImpactValue : nullImpactValues) { + result = result * 31 + nullImpactValue.get(Tuple0.INSTANCE).hashCode(); + } + result += lastSum; + + return (int) result; + } + + protected long getTupleHash(Tuple tuple, Object value, ObjectCode objectCode) { + long result = (long) value; + int arity = tuple.getSize(); + if (arity == 1) { + result = result * 31 + objectCode.get(tuple.get(0)); + } else if (arity == 2) { + result = result * 31 + objectCode.get(tuple.get(0)); + result = result * 31 + objectCode.get(tuple.get(1)); + if (tuple.get(0) == tuple.get(1)) { + result++; + } + } else if (arity > 2) { + for (int i = 0; i < arity; i++) { + result = result * 31 + objectCode.get(tuple.get(i)); + } + } + return result; + } + + protected void addHash(ObjectCode objectCode, Tuple tuple, long[] impact, long tupleHashCode) { + if (tuple.getSize() == 1) { + addHash(objectCode, tuple.get(0), impact[0], tupleHashCode); + } else if (tuple.getSize() == 2) { + addHash(objectCode, tuple.get(0), impact[0], tupleHashCode); + addHash(objectCode, tuple.get(1), impact[1], tupleHashCode); + } else if (tuple.getSize() > 2) { + for (int i = 0; i < tuple.getSize(); i++) { + addHash(objectCode, tuple.get(i), impact[i], tupleHashCode); + } + } + } + + protected void addHash(ObjectCode objectCode, int o, long impact, long tupleHash) { + objectCode.set(o, objectCode.get(o) + tupleHash * impact); + } + +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCode.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCode.java new file mode 100644 index 00000000..594d2b3a --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCode.java @@ -0,0 +1,55 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.neighbourhood; + +public class ObjectCode { + private long[] vector; + private int size; + + public ObjectCode() { + vector = new long[10]; + size = 0; + } + + public ObjectCode(ObjectCode sameSize) { + this.vector = new long[sameSize.size]; + this.size = sameSize.size; + } + + private void ensureSize(int object) { + if(object >= size) { + size = object+1; + } + + if(object >= vector.length) { + int newLength = vector.length*2; + while(object >= newLength) { + newLength*=2; + } + + long[] newVector = new long[newLength]; + System.arraycopy(vector, 0, newVector, 0, vector.length); + this.vector = newVector; + } + } + + public long get(int object) { + if(object < vector.length) { + return vector[object]; + } else { + return 0; + } + } + + public void set(int object, long value) { + ensureSize(object); + vector[object]=value; + } + + public int getSize() { + return this.size; + } +} -- cgit v1.2.3-70-g09d2