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 +- .../store/query/viatra/OrderedResultSetTest.java | 117 +++++++++++++++++++++ .../store/query/viatra/tests/QueryAssertions.java | 2 +- 8 files changed, 183 insertions(+), 51 deletions(-) create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java create mode 100644 subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java (limited to 'subprojects/store-query-viatra') 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; diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java new file mode 100644 index 00000000..8ede6c80 --- /dev/null +++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java @@ -0,0 +1,117 @@ +/* + * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra; + +import org.junit.jupiter.api.Test; +import tools.refinery.store.model.ModelStore; +import tools.refinery.store.query.ModelQueryAdapter; +import tools.refinery.store.query.dnf.Query; +import tools.refinery.store.query.resultset.OrderedResultSet; +import tools.refinery.store.query.term.Variable; +import tools.refinery.store.query.view.AnySymbolView; +import tools.refinery.store.query.view.KeyOnlyView; +import tools.refinery.store.representation.Symbol; +import tools.refinery.store.tuple.Tuple; + +import static org.hamcrest.MatcherAssert.assertThat; +import static org.hamcrest.Matchers.is; + +class OrderedResultSetTest { + private static final Symbol friend = Symbol.of("friend", 2); + private static final AnySymbolView friendView = new KeyOnlyView<>(friend); + + @Test + void relationalFlushTest() { + var query = Query.of("Relation", (builder, p1, p2) -> builder.clause( + friendView.call(p1, p2) + )); + + var store = ModelStore.builder() + .symbols(friend) + .with(ViatraModelQueryAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var friendInterpretation = model.getInterpretation(friend); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var resultSet = queryEngine.getResultSet(query); + + friendInterpretation.put(Tuple.of(0, 1), true); + friendInterpretation.put(Tuple.of(1, 2), true); + friendInterpretation.put(Tuple.of(1, 1), true); + queryEngine.flushChanges(); + + try (var orderedResultSet = new OrderedResultSet<>(resultSet)) { + assertThat(orderedResultSet.size(), is(3)); + assertThat(orderedResultSet.getKey(0), is(Tuple.of(0, 1))); + assertThat(orderedResultSet.getKey(1), is(Tuple.of(1, 1))); + assertThat(orderedResultSet.getKey(2), is(Tuple.of(1, 2))); + + friendInterpretation.put(Tuple.of(1, 2), false); + friendInterpretation.put(Tuple.of(0, 2), true); + queryEngine.flushChanges(); + + assertThat(orderedResultSet.size(), is(3)); + assertThat(orderedResultSet.getKey(0), is(Tuple.of(0, 1))); + assertThat(orderedResultSet.getKey(1), is(Tuple.of(0, 2))); + assertThat(orderedResultSet.getKey(2), is(Tuple.of(1, 1))); + } + } + + @Test + void functionalFlushTest() { + var query = Query.of("Function", Integer.class, (builder, p1, output) -> builder.clause( + friendView.call(p1, Variable.of()), + output.assign(friendView.count(p1, Variable.of())) + )); + + var store = ModelStore.builder() + .symbols(friend) + .with(ViatraModelQueryAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var friendInterpretation = model.getInterpretation(friend); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var resultSet = queryEngine.getResultSet(query); + + friendInterpretation.put(Tuple.of(0, 1), true); + friendInterpretation.put(Tuple.of(1, 2), true); + friendInterpretation.put(Tuple.of(1, 1), true); + queryEngine.flushChanges(); + + try (var orderedResultSet = new OrderedResultSet<>(resultSet)) { + assertThat(orderedResultSet.size(), is(2)); + assertThat(orderedResultSet.getKey(0), is(Tuple.of(0))); + assertThat(orderedResultSet.getKey(1), is(Tuple.of(1))); + + friendInterpretation.put(Tuple.of(0, 1), false); + friendInterpretation.put(Tuple.of(2, 1), true); + queryEngine.flushChanges(); + + assertThat(orderedResultSet.size(), is(2)); + assertThat(orderedResultSet.getKey(0), is(Tuple.of(1))); + assertThat(orderedResultSet.getKey(1), is(Tuple.of(2))); + + friendInterpretation.put(Tuple.of(1, 1), false); + queryEngine.flushChanges(); + + assertThat(orderedResultSet.size(), is(2)); + assertThat(orderedResultSet.getKey(0), is(Tuple.of(1))); + assertThat(orderedResultSet.getKey(1), is(Tuple.of(2))); + + friendInterpretation.put(Tuple.of(1, 2), false); + friendInterpretation.put(Tuple.of(1, 0), true); + queryEngine.flushChanges(); + + assertThat(orderedResultSet.size(), is(2)); + assertThat(orderedResultSet.getKey(0), is(Tuple.of(1))); + assertThat(orderedResultSet.getKey(1), is(Tuple.of(2))); + } + } +} diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java index 7a25cfdc..ca089a9d 100644 --- a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java +++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java @@ -6,7 +6,7 @@ package tools.refinery.store.query.viatra.tests; import org.junit.jupiter.api.function.Executable; -import tools.refinery.store.query.ResultSet; +import tools.refinery.store.query.resultset.ResultSet; import tools.refinery.store.tuple.Tuple; import java.util.*; -- cgit v1.2.3-54-g00ecf