From 8d79e7f39df0fde9b4f0ba8e6264f2900e9024c6 Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Thu, 29 Jun 2023 02:08:40 +0200 Subject: feat: ordered query ResultSet Enable deterministic state-space exploration by ordering activations in lexicographic order. This preliminary implementation adds oredering as a wrapper for ResultSet instances, but more sophisticated support could be built directly into query engine adapters if a query engine supports deterministic output by default. * Implements Comparable for tuples with loops unrolled for small tuples by hand. * Cleans up the contents of the (root of the) tools.refinery.query package. * Adds ResultSetListener to notify clients about ResultSet changes. * Adds OrderStatisticTree data structure for determinisitc ordering of keys. --- .../internal/ViatraModelQueryAdapterImpl.java | 6 ++-- .../internal/matcher/AbstractViatraMatcher.java | 32 ++++++++++++++++++++ .../internal/matcher/FunctionalViatraMatcher.java | 34 +++++++++------------- .../viatra/internal/matcher/MatcherUtils.java | 10 +++++-- .../internal/matcher/RelationalViatraMatcher.java | 29 +++++------------- .../internal/matcher/UnsafeFunctionalCursor.java | 4 +-- 6 files changed, 65 insertions(+), 50 deletions(-) create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java (limited to 'subprojects/store-query-viatra/src/main') diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java index 7103a561..5f3e86b4 100644 --- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java @@ -13,9 +13,9 @@ import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackend; import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory; import tools.refinery.store.model.Model; import tools.refinery.store.model.ModelListener; -import tools.refinery.store.query.AnyResultSet; -import tools.refinery.store.query.EmptyResultSet; -import tools.refinery.store.query.ResultSet; +import tools.refinery.store.query.resultset.AnyResultSet; +import tools.refinery.store.query.resultset.EmptyResultSet; +import tools.refinery.store.query.resultset.ResultSet; import tools.refinery.store.query.dnf.AnyQuery; import tools.refinery.store.query.dnf.FunctionalQuery; import tools.refinery.store.query.dnf.Query; diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java new file mode 100644 index 00000000..99b0a3d8 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java @@ -0,0 +1,32 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.matcher; + +import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider; +import org.eclipse.viatra.query.runtime.matchers.backend.IUpdateable; +import tools.refinery.store.query.dnf.Query; +import tools.refinery.store.query.resultset.AbstractResultSet; +import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl; + +public abstract class AbstractViatraMatcher extends AbstractResultSet implements IUpdateable { + protected final IQueryResultProvider backend; + + protected AbstractViatraMatcher(ViatraModelQueryAdapterImpl adapter, Query query, + RawPatternMatcher rawPatternMatcher) { + super(adapter, query); + backend = rawPatternMatcher.getBackend(); + } + + @Override + protected void startListeningForChanges() { + backend.addUpdateListener(this, this, false); + } + + @Override + protected void stopListeningForChanges() { + backend.removeUpdateListener(this); + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java index f018288b..db4740cd 100644 --- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java @@ -5,16 +5,12 @@ */ package tools.refinery.store.query.viatra.internal.matcher; -import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider; import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask; import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples; import org.eclipse.viatra.query.runtime.rete.index.IterableIndexer; import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher; import tools.refinery.store.map.Cursor; -import tools.refinery.store.query.ModelQueryAdapter; -import tools.refinery.store.query.ResultSet; import tools.refinery.store.query.dnf.FunctionalQuery; -import tools.refinery.store.query.dnf.Query; import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl; import tools.refinery.store.tuple.Tuple; @@ -28,23 +24,18 @@ import tools.refinery.store.tuple.Tuple; * implementation for these methods. * Using this class with any other runtime context may lead to undefined behavior. */ -public class FunctionalViatraMatcher implements ResultSet { - private final ViatraModelQueryAdapterImpl adapter; - private final FunctionalQuery query; +public class FunctionalViatraMatcher extends AbstractViatraMatcher { private final TupleMask emptyMask; private final TupleMask omitOutputMask; - private final IQueryResultProvider backend; private final IterableIndexer omitOutputIndexer; public FunctionalViatraMatcher(ViatraModelQueryAdapterImpl adapter, FunctionalQuery query, RawPatternMatcher rawPatternMatcher) { - this.adapter = adapter; - this.query = query; + super(adapter, query, rawPatternMatcher); int arity = query.arity(); int arityWithOutput = arity + 1; emptyMask = TupleMask.empty(arityWithOutput); omitOutputMask = TupleMask.omit(arity, arityWithOutput); - backend = rawPatternMatcher.getBackend(); if (backend instanceof RetePatternMatcher reteBackend) { var maybeIterableOmitOutputIndexer = IndexerUtils.getIndexer(reteBackend, omitOutputMask); if (maybeIterableOmitOutputIndexer instanceof IterableIndexer iterableOmitOutputIndexer) { @@ -57,16 +48,6 @@ public class FunctionalViatraMatcher implements ResultSet { } } - @Override - public ModelQueryAdapter getAdapter() { - return adapter; - } - - @Override - public Query getQuery() { - return query; - } - @Override public T get(Tuple parameters) { var tuple = MatcherUtils.toViatraTuple(parameters); @@ -93,4 +74,15 @@ public class FunctionalViatraMatcher implements ResultSet { } return omitOutputIndexer.getBucketCount(); } + + @Override + public void update(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple updateElement, boolean isInsertion) { + var key = MatcherUtils.keyToRefineryTuple(updateElement); + var value = MatcherUtils.getValue(updateElement); + if (isInsertion) { + notifyChange(key, null, value); + } else { + notifyChange(key, value, null); + } + } } diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java index 1c784492..6e24812a 100644 --- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java @@ -86,6 +86,13 @@ final class MatcherUtils { return getWrapper(viatraTuple, index).value0(); } + public static T getValue(ITuple match) { + // This is only safe if we know for sure that match came from a functional query of type {@code T}. + @SuppressWarnings("unchecked") + var result = (T) match.get(match.getSize() - 1); + return result; + } + public static T getSingleValue(@Nullable Iterable viatraTuples) { if (viatraTuples == null) { return null; @@ -98,8 +105,7 @@ final class MatcherUtils { return null; } var match = iterator.next(); - @SuppressWarnings("unchecked") - var result = (T) match.get(match.getSize() - 1); + var result = MatcherUtils.getValue(match); if (iterator.hasNext()) { var input = keyToRefineryTuple(match); throw new IllegalStateException("Query is not functional for input tuple: " + input); diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java index d1476920..ac95dcc0 100644 --- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java @@ -5,16 +5,12 @@ */ package tools.refinery.store.query.viatra.internal.matcher; -import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider; import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask; import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples; import org.eclipse.viatra.query.runtime.rete.index.Indexer; import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher; import tools.refinery.store.map.Cursor; import tools.refinery.store.map.Cursors; -import tools.refinery.store.query.ModelQueryAdapter; -import tools.refinery.store.query.ResultSet; -import tools.refinery.store.query.dnf.Query; import tools.refinery.store.query.dnf.RelationalQuery; import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl; import tools.refinery.store.tuple.Tuple; @@ -29,22 +25,17 @@ import tools.refinery.store.tuple.Tuple; * implementation for these methods. * Using this class with any other runtime context may lead to undefined behavior. */ -public class RelationalViatraMatcher implements ResultSet { - private final ViatraModelQueryAdapterImpl adapter; - private final RelationalQuery query; +public class RelationalViatraMatcher extends AbstractViatraMatcher { private final TupleMask emptyMask; private final TupleMask identityMask; - private final IQueryResultProvider backend; private final Indexer emptyMaskIndexer; public RelationalViatraMatcher(ViatraModelQueryAdapterImpl adapter, RelationalQuery query, RawPatternMatcher rawPatternMatcher) { - this.adapter = adapter; - this.query = query; + super(adapter, query, rawPatternMatcher); int arity = query.arity(); emptyMask = TupleMask.empty(arity); identityMask = TupleMask.identity(arity); - backend = rawPatternMatcher.getBackend(); if (backend instanceof RetePatternMatcher reteBackend) { emptyMaskIndexer = IndexerUtils.getIndexer(reteBackend, emptyMask); } else { @@ -52,16 +43,6 @@ public class RelationalViatraMatcher implements ResultSet { } } - @Override - public ModelQueryAdapter getAdapter() { - return adapter; - } - - @Override - public Query getQuery() { - return query; - } - @Override public Boolean get(Tuple parameters) { var tuple = MatcherUtils.toViatraTuple(parameters); @@ -90,4 +71,10 @@ public class RelationalViatraMatcher implements ResultSet { var matches = emptyMaskIndexer.get(Tuples.staticArityFlatTupleOf()); return matches == null ? 0 : matches.size(); } + + @Override + public void update(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple updateElement, boolean isInsertion) { + var key = MatcherUtils.toRefineryTuple(updateElement); + notifyChange(key, !isInsertion, isInsertion); + } } diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java index 4a41d724..b0b507fe 100644 --- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java @@ -46,9 +46,7 @@ class UnsafeFunctionalCursor implements Cursor { if (!terminated && tuplesIterator.hasNext()) { var match = tuplesIterator.next(); key = MatcherUtils.keyToRefineryTuple(match); - @SuppressWarnings("unchecked") - var typedValue = (T) match.get(match.getSize() - 1); - value = typedValue; + value = MatcherUtils.getValue(match); return true; } terminated = true; -- cgit v1.2.3-70-g09d2